(57)【要約】【課題】ｎ次元トーラス型分散処理システムにおける転送時間、転送回数を少なくする。【解決手段】２次元方向に配列された複数のプロセスが、自己が所持するデータの少なくとも一部を、第１方向に隣接するプロセスに順次転送して予め所持していた元データを、第１方向に並ぶ全プロセスに所持させ（Ｓ１２〜Ｓ１６）、また、第２方向に隣接するプロセスに自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送処理の後に自己が所持していたデータの少なくとも一部を、第２方向に並ぶ全プロセスに所持させる（Ｓ１８〜Ｓ２２）。これにより、システム上でのデータ衝突による転送待ち時間の発生を無くすことができる。この場合、ｎ次元（ｎ＞２）であっても、前記２方向以外に方向を異ならせながら同様のデータ転送を（ｎ−１）回繰り返すことにより、同様のデータ転送が可能である。【選択図】図２
2010211553.tif 000002
【特許請求の範囲】
【請求項１】
ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムであって、
前記各プロセッサは、
自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送処理と、
前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送処理の後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送処理と、を実行することを特徴とするｎ次元トーラス型分散処理システム。
【請求項２】
前記ｎ次元方向のそれぞれに配列されるプロセッサは、任意の数であることを特徴とする請求項１に記載のｎ次元トーラス型分散処理システム。
【請求項３】
前記第１、第２データ転送処理では、
前記各プロセッサは、自己が所持しているデータを隣接するプロセッサに転送する第１転送と、新たに転送されてきたデータを、前記隣接するプロセッサに転送する第２転送と、を実行することを特徴とする請求項１又は２に記載のｎ次元トーラス型分散処理システム。
【請求項４】
前記各プロセッサは、他の全てのプロセッサそれぞれに転送する必要のあるデータを所持しており、
前記第１、第２データ転送処理では、
前記各プロセッサが、自己から前記一方向側又は他方向側に存在する任意の目標プロセッサに向けて転送する必要のある目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第１転送と、
前記目標データを受信したプロセッサが、当該目標データと、自己が有する前記目標プロセッサに対して転送する必要のあるデータとを加算した新たな目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第２転送と、を実行することを特徴とする請求項１又は２に記載のｎ次元トーラス型分散処理システム。
【請求項５】
前記各プロセッサは、前記第２データ転送処理を、前記他方向を異ならせつつ（ｎ−１）回繰り返すことを特徴とする請求項１〜４のいずれか一項に記載のｎ次元トーラス型分散処理システム。
【請求項６】
前記一方向及び前記他方向は、前記ｎ次元方向それぞれにおける前記データの転送可能速度に応じて決定することを特徴とする請求項１〜５のいずれか一項に記載のｎ次元トーラス型分散処理システム。
【請求項７】
ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムにおける集団通信方法であって、
前記各プロセッサが、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程と、
前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程と、を含む集団通信方法。
【請求項８】
ｎ次元トーラス型分散処理システムに属するｎ次元（ｎは２以上）方向に配列された複数のプロセッサに、
自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程、及び
前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程、を実行させることを特徴とする集団通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、ｎ次元トーラス型分散処理システム、集団通信方法及び集団通信プログラムに関し、特にｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システム、当該ｎ次元トーラス型分散処理システムにおける集団通信方法及び集団通信プログラムに関する。
【背景技術】
【０００２】
最近の科学技術計算における高並列の分散処理システムでは、個々の演算器（ＣＰＵ（プロセッサ））を多数連結し、各ＣＰＵに演算とデータを分担させることによって、全体として大規模な演算を高速処理する超並列処理が実行されている。このような分散処理システムでは、各ＣＰＵで動作している、処理の実行に寄与するプロセス間のデータ通信の方式として、種々の集団通信方式、例えば、Recursive halvingや、Recursive doubling法が採用されている。これらは、データ通信方式の標準化された規格であるＭＰＩ（Message Passing Interface）において定められるReduce_scatter転送やAllgather転送、及びこれらを続けて行うAllreduce転送を実現する。
【０００３】
具体的には、図３３に示すように、プロセス１〜プロセス４まで存在する分散処理システムにおいて、各プロセスがその他のプロセスに転送すべきデータを有している場合には、以下のようにしてデータ転送（Reduce_scatter転送）を行う。
【０００４】
まず、図３３（ａ）、図３３（ｂ）に点線にて示すように、プロセス１〜４を前半と後半に分けて、前半に属するプロセス（１及び２）からは後半に属するプロセス（３及び４）に自己の有する後半のデータ（添え字「３」、「４」が付されたデータ）を転送する。具体的には、プロセス１からプロセス３に、データＡ3、Ａ4を転送し、プロセス２からプロセス４に、データＢ3、Ｂ4を転送する。また、後半に属するプロセスからは前半に属するプロセスに自己の有する前半のデータ（添え字「１」、「２」が付されたデータ）を転送する。具体的には、プロセス３からプロセス１に、データＣ1、Ｃ2を転送し、プロセス４からプロセス２に、データＤ1、Ｄ2を転送する。なお、各プロセスでは、受信したデータと、自己が保有していたデータとを加算して（添え字が共通するデータ同士を加算して）保持する。更に、図３３（ｂ）、図３３（ｃ）に示すように、前半のプロセス１，２間で、転送先のプロセス番号と一致するデータを転送しあうとともに、後半のプロセス３，４間で、転送先のプロセス番号と一致するデータを転送しあう。
【０００５】
一方、図３４に示すように、プロセス１〜４まで存在する分散処理システムにおいて、各プロセスが、自己が演算したデータ（Ａ〜Ｄ）をそれぞれ有している場合に、そのデータを全プロセスに共有させるには、以下のデータ転送（Allgather転送）を行う。
【０００６】
まず、図３４（ａ）、図３４（ｂ）に示すように、プロセス１とプロセス２との間、プロセス３とプロセス４との間で、自己が保有するデータを転送しあう。次いで、図３４（ｂ）、図３４（ｃ）に点線にて示すように、プロセス１〜４を前半と後半に分け、前半に属するプロセスからは後半に属するプロセスに自己の有するデータすべてを転送する。また、後半に属するプロセスからは前半に属するプロセスに自己の有するデータすべてを転送する。
【０００７】
これら図３３，図３４の転送方式は、他の転送方式に比べて転送の回数および総転送量が少なくて済むという利点を有する。なお、その他の転送方法としては、特許文献１のような方法が提案されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平１１−３４５２２０号公報
【特許文献２】特開平６−１２４２７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
最近では、分散処理システムにおける計算能力の向上を図るため、プロセスを数万個といった規模で多数連結するシステムが出現してきている。この種のシステムでは、隣接するプロセス間及び両端に位置するプロセス間を連結する方式のネットワーク、すなわちトーラス型のネットワークが比較的多く採用される。
【００１０】
このようなトーラス型のネットワークを採用した場合、データの転送方法として図３３や図３４の方法を用いると、隣接するプロセス以外の遠方のプロセスへの直接の転送が発生するため、複数の転送データ間で衝突が生じ、効率的でない。なお、特許文献２に記載の技術は隣接するプロセスにおけるデータ転送に関するものではあるが、転送アルゴリズムの改善策に関するものではない。
【００１１】
そこで本発明は上記の課題に鑑みてなされたものであり、少ない手順でプロセッサ間のデータ転送を実現可能なｎ次元トーラス型分散処理システム、集団通信方法及び集団通信プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本明細書に記載のｎ次元トーラス型分散処理システムは、ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムであって、前記各プロセッサは、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送処理と、前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送処理の後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送処理と、を実行するものである。
【００１３】
ここで、「隣接するプロセッサ」とは、トーラス型ネットワーク内で通信可能なプロセッサを意味する。すなわち、トーラス型ネットワークでは、実際に隣接するプロセッサ同士のほか、ある方向の両端に位置するプロセッサ同士も通信可能とされているので、これら両端に位置するプロセッサ同士も「隣接するプロセッサ」であるといえる。
【００１４】
本明細書に記載の集団通信方法は、ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムにおける集団通信方法であって、前記各プロセッサが、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程と、前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程と、を含んでいる。
【００１５】
本明細書に記載の集団通信プログラムは、ｎ次元トーラス型分散処理システムに属するｎ次元（ｎは２以上）方向に配列された複数のプロセッサに、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程、及び前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程、を実行させるものである。
【発明の効果】
【００１６】
本明細書に記載のｎ次元トーラス型分散処理システム、集団通信方法及び集団通信プログラムは、少ない手順でプロセッサ間のデータ転送を実現できるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】第１の実施形態に係る２次元トーラス型分散処理システムの構成を概略的に示す図である。
【図２】図１のシステムの処理内容を示すフローチャートである。
【図３】図３（ａ）は、各プロセスにおける演算処理結果を示す図であり、図３（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その１）である。
【図４】図４（ａ）、図４（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その２、その３）である。
【図５】図５（ａ）、図５（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その４、その５）である。
【図６】図６（ａ）、図６（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その６、その７）である。
【図７】図７（ａ）、図７（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その８、その９）である。
【図８】図８（ａ）、図８（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その１０、その１１）である。
【図９】図９（ａ）、図９（ｂ）は、第１の実施形態における隣接プロセスへのデータ転送手順を示す図（その１２、その１３）である。
【図１０】図９（ａ）のデータを纏めた状態を示す図である。
【図１１】第１の実施形態の変形例に係る３次元トーラス型分散処理システムの構成を概略的に示す図である。
【図１２】図１１のシステムにおける隣接プロセスへのデータ転送手順を示す図（その１）である。
【図１３】図１１のシステムにおける隣接プロセスへのデータ転送手順を示す図（その２）である。
【図１４】第１の実施形態の変形例に係る４次元トーラス型分散処理システムの構成を概略的に示す図である。
【図１５】第２の実施形態に係る２次元トーラス型分散処理システムの構成を概略的に示す図である。
【図１６】図１５のシステムの処理内容を示すフローチャートである。
【図１７】各プロセスにおける演算処理結果を示す図である。
【図１８】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その１）である。
【図１９】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その２）である。
【図２０】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その３）である。
【図２１】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その４）である。
【図２２】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その５）である。
【図２３】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その６）である。
【図２４】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その７）である。
【図２５】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その８）である。
【図２６】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その９）である。
【図２７】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その１０）である。
【図２８】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その１１）である。
【図２９】第２の実施形態における隣接プロセスへのデータ転送手順を示す図（その１２）である。
【図３０】図２９を簡略化して示す図である。
【図３１】第２の実施形態のデータ転送を実行した後において各プロセスが所持するデータを示す図である。
【図３２】第２実施形態の比較例を示す図である。
【図３３】従来のデータ転送方法を示す図（その１）である。
【図３４】従来のデータ転送方法を示す図（その２）である。
【発明を実施するための形態】
【００１８】
≪第１の実施形態≫
以下、ｎ次元トーラス型分散処理システム、集団通信方法及び集団通信プログラムの第１の実施形態について、図１〜図１０に基づいて詳細に説明する。
【００１９】
図１には、本第１の実施形態に係る２次元トーラス型分散処理システム１００の構成が概略的に示されている。この図１に示すように、２次元トーラス型分散処理システム１００は、プロセスが動作する複数（ここでは、２５個）のＣＰＵ（プロセッサ）１１〜１５、２１〜２５、３１〜３５、４１〜４５、５１〜５５を有しており、第１方向及び第２方向に隣接するプロセッサ間においてデータ通信可能とされている。また、システム１００では、第１方向及び第２方向の両端に位置するプロセッサ間においてもデータ通信が可能とされている。なお、本実施形態では、各ＣＰＵ（プロセッサ）においてそれぞれ動作している「プロセス」が処理を実行するので、本実施形態では、ＣＰＵ（プロセッサ）１１〜５５を、「プロセス１１〜５５」と表記するものとする。
【００２０】
なお、本第１の実施形態では、第２方向に関して隣接するプロセス間の転送速度が、第１方向に関して隣接するプロセス間の転送速度よりも速いものとする。
【００２１】
以下、図１のシステム１００におけるデータ演算及び転送に関する手順について、図２のフローチャートに沿って説明する。なお、図２の処理を実現するためのプログラムは、当該プログラムを記録する記録媒体（ディスク）から１つのプロセスに含まれるメモリに展開された後、全プロセスに組み込まれるものである。
【００２２】
まず、図２のステップＳ１０では、各プロセスにおいて所定の演算処理を実行する。この演算処理により得られた結果が図３に模式的に示されている。なお、図３以降では、各プロセス間の接続線の図示を省略している。
【００２３】
本第１の実施形態では、図３（ａ）に示すように、プロセス１１の演算処理結果がデータＡであり、プロセス１２の演算処理結果がデータＢであり、…、プロセス５５の演算処理結果がデータＹであるものとする。なお、ステップＳ１０以降に行われるデータ転送処理では、図１０に示すように、図３（ａ）において各プロセスが保持していたデータを、全プロセスに行き渡らせる（Allgather転送）。
【００２４】
次のステップＳ１２では、各プロセスが、第１方向の一側（ここでは、図１における右側）に隣接するプロセスに対して、自己の所持するデータを一斉に転送する（図３（ｂ）参照）。なお、最右端に位置するプロセス１５〜５５は、自己の所持するデータを最左端に位置するプロセス１１〜５１に転送する。このステップＳ１２の処理により、各プロセスは、図４（ａ）に示すように、データを２つずつ所持することになる。
【００２５】
次いで、ステップＳ１４では、各プロセスが、第１方向の一側（ここでは、図１における右側）に隣接するプロセスに対して、新たに受け取ったデータを一斉に転送する。すなわち、図４（ｂ）に下線を付して示すデータを、隣接するプロセスに転送する。この転送後の状態が、図５（ａ）に示されている。
【００２６】
次いで、ステップＳ１６では、各プロセスが、第１方向の全てのデータを受け取ったか否かを判断する。この判断は、例えば、各プロセスが所持するデータ数が、第１方向に配列されたプロセス数と一致した場合に肯定され、データ数が、第１方向に配列されたプロセス数よりも少ない場合に否定される。なお、図５（ａ）の段階では、各プロセスが、第１方向の全てのデータを受け取っていないので、ステップＳ１６の判断は否定され、ステップＳ１４に戻る。
【００２７】
その後、ステップＳ１４を２度繰り返し、図５（ｂ）の状態を経て、図６（ａ）の状態となった段階で、ステップＳ１６の判断が肯定される。なお、図６（ａ）の状態は、図６（ｂ）のように表すことができ、この状態では、第１方向に並ぶプロセスそれぞれが、共通のデータを所持している。
【００２８】
次のステップＳ１８では、各プロセスが、第２方向の一側（ここでは、図１等における下側）に隣接するプロセスに対して、自己の所持するデータ（５プロセス分のデータ）を一斉に転送する（図７（ａ）参照）。なお、最下端に位置するプロセス５１〜５５は、自己の所持するデータを最上端に位置するプロセス１１〜１５に転送する。このステップＳ１８の処理により、各プロセスは、図７（ｂ）に示すようなデータを所持することになる。
【００２９】
次いで、ステップＳ２０では、各プロセスが、第２方向の一側（ここでは、図１等における下側）に隣接するプロセスに対して、新たに受け取ったデータ（５プロセス分のデータ）を一斉に転送する。すなわち、図８（ａ）に下線を付して示すデータを、隣接するプロセスに転送する。この転送後の状態が、図８（ｂ）に示されている。
【００３０】
次いで、ステップＳ２２では、各プロセスが、第２方向の全てのデータを受け取ったか否かを判断する。この判断は、例えば、各プロセスが所持するデータ数が、第１方向及び第２方向に配列されたプロセスの合計（ここでは２５）と一致した場合に肯定され、データ数がプロセスの合計よりも小さい場合に否定される。なお、この図８（ｂ）の段階では、各プロセスが、全てのデータを受け取っていないので、ステップＳ２２の判断は否定され、ステップＳ２０に戻る。
【００３１】
その後、ステップＳ２０を２度繰り返し、図９（ａ）の状態を経て、図９（ｂ）の状態となった段階で、ステップＳ２２の判断が肯定され、図２の全処理を終了する。なお、図９（ｂ）の状態は、図１０のように表すことができる。この状態では、全プロセスが元々有していたデータの全て（データＡ〜Ｙ）を、各プロセスが所持していることになる。
【００３２】
ここで、本第１の実施形態では、第１方向に１プロセス分のデータを４回送り、第２方向に５プロセス分のデータを４回送ることで全てのデータ転送が完了する。したがって、２５個のプロセスを有するシステムにおける最小限の転送量である２４（＝１×４＋５×４）プロセス分のデータを、８回のデータ転送により送ることができることになる。
【００３３】
以上、詳細に説明したように、本第１の実施形態によると、２次元方向に配列された複数のプロセス１１〜５５が、自己が所持するデータの少なくとも一部を第１方向に隣接するプロセスに順次転送して、自己が予め所持していたデータ（演算結果）を、第１方向に並ぶプロセスの全てに所持させ、第１方向の転送が終了した後、自己が所持するデータの少なくとも一部を、第２方向に隣接するプロセスに順次転送して、第１方向へのデータ転送処理の後に自己が所持していたデータを、第２方向に並ぶプロセスの全てに所持させる。このように、全プロセスが同時に実行する隣接転送を行うことにより、システム上（又はネットワーク上）におけるデータの衝突を無くすことができる。これにより、データの衝突による待ち時間が発生しないことから、転送時間、転送回数を少なくすることが可能である。
【００３４】
また、本第１の実施形態の集団通信方法（データ転送方法）を用いれば、プロセスの第１方向に関するプロセス数及び第２方向に関するプロセス数を任意に設定しても、問題なくデータ転送を行うことができる。これにより、プロセス数が例えば２のべき乗などに限定されることがないので、システム設計を簡易に行うことが可能である。すなわち、プロセス数は上記第１の実施形態で説明した５×５である場合に限られるものではなく、プロセス数としては、任意の数を採用することが可能である。
【００３５】
また、本第１の実施形態では、第１方向のデータ転送又は第２方向のデータ転送において、各プロセスが所持しているデータを第１方向又は第２方向に隣接するプロセスに転送する処理（ステップＳ１２又はＳ１８）と、新たに受信したデータを第１方向又は第２方向に隣接するプロセスに転送する処理（ステップＳ１４又はＳ２０）と、を実行するので、簡易な方法で、各プロセスの演算結果を全プロセスに所持させること（Allgather転送）が可能である。
【００３６】
また、本第１の実施形態では、第２方向に関して隣接するプロセス間の転送速度が第１方向に関して隣接するプロセス間の転送速度よりも速く、第１方向のデータ転送を第２方向のデータ転送よりも先に実行することとしているので、転送速度の遅い方向に少ないデータ（１プロセス分のデータ）を転送し、転送速度の速い方向に多いデータ（５プロセス分のデータ）を転送することにより、効率的なデータ転送が可能である。ただし、これに限られるものではなく、図１の上下方向を第１方向に設定し、左右方向を第２方向に設定することとしても良い。
【００３７】
なお、上記第１の実施形態では、ｎ次元トーラス型分散処理システムが２次元トーラス型分散処理システムである場合について説明したが、これに限らず、３次元以上のトーラス型分散処理システムであっても良い。
【００３８】
図１１には、３次元トーラス型分散処理システム１００’が模式的に示されている。なお、図１１では３×３×３の３次元トーラス型分散処理システムを図示している。この図１１に示すように、下から１層目のプロセスは、データＡ１、Ｂ１、…Ｉ１をそれぞれ有し、下から２層目のプロセスは、データＡ２、Ｂ２、…Ｉ２をそれぞれ有し、下から３層目のプロセスは、データＡ３、Ｂ３、…Ｉ３をそれぞれ有している。このシステム１００’では、各層において、上記第１の実施形態と同様に、第１方向及び第２方向へのデータ転送を行う。これにより、図１２に示すように、下から１層目のプロセスの全てが、データＡ１〜Ｉ１を所持することになり、下から２層目のプロセスの全てが、データＡ２〜Ｉ２を所持することになり、下から３層目のプロセスの全てが、データＡ３〜Ｉ３を所持することになる。
【００３９】
また、図１２の状態から、第３方向（紙面上下方向）に隣接するプロセスに対し、上記第１の実施形態と同様に、データを転送することにより、図１３に示すように、３次元トーラス型分散処理システム１００’を構成する全てのプロセスが、全てのデータＡ１〜Ｉ３を所持することができるようになる。
【００４０】
なお、図１４に示すように、３次元トーラス型分散処理システム１００’と同様の３次元トーラス型分散処理システム１００”を更に備える、４次元トーラス型分散システム１００’においても、同様のデータ転送により、全プロセスにデータを行き渡らせることができる。具体的には、各システム１００’、１００”内で、図１１〜図１３と同様に、各プロセスにデータを行き渡らせた後、システム１００’と１００”の対応するプロセス（システム内における位置が同一のプロセス）にデータを転送しあえば良い。
【００４１】
なお、２次元〜４次元トーラス型分散処理システムに限らず、５次元、６次元…トーラス型分散処理システムでも、同様のデータ転送により、全プロセスに全データを所持させることが可能である。
【００４２】
なお、３次元、４次元…トーラス型分散処理システムにおいても、転送速度が遅い方向には、早い段階（転送データ量が少ない段階）で少ないデータを送り、転送速度が速い方向には、１度に大量のデータを送るようにすることが好ましい。
【００４３】
≪第２の実施形態≫
次に、ｎ次元トーラス型分散処理システム、集団通信方法及び集団通信プログラムの第２の実施形態について、図１５〜図３１に基づいて詳細に説明する。
【００４４】
図１５には、本第２の実施形態に係る２次元トーラス型分散処理システム２００の構成が概略的に示されている。図１５に示すように、２次元トーラス型分散処理システム２００は、複数（ここでは、２５個）のプロセス１１〜１５、２１〜２５、３１〜３５、４１〜４５、５１〜５５を有しており、第１方向及び第２方向に隣接するプロセス間においてデータ通信可能とされている。また、システム２００では、第１方向及び第２方向の両端に位置するプロセス間においてもデータ通信が可能とされている。
【００４５】
なお、本第２の実施形態においては、図１５の上下方向が第１方向であり、左右方向が第２方向であるものとする。また、第１方向に関して隣接するプロセス間の転送速度が、第２方向に関して隣接するプロセス間の転送速度よりも速いものとする。
【００４６】
以下、図１５のシステム２００におけるデータ演算及び転送に関する手順について、図１６のフローチャートに沿って説明する。なお、図１６の処理を実現するためのプログラムは、当該プログラムを記録する記録媒体（ディスク）から１つのプロセスに含まれるメモリに展開された後、全プロセスに組み込まれるものである。
【００４７】
まず、図１６のステップＳ１１０では、各プロセスにおいて所定の演算処理を実行する。この演算処理により得られた結果が図１７に模式的に示されている。
【００４８】
図１７に示すように、プロセス１１では、演算処理の結果、データＡ１１〜Ａ１５、Ａ２１〜Ａ２５、Ａ３１〜Ａ３５、Ａ４１〜Ａ４５、Ａ５１〜Ａ５５（以下、簡単のため、「データＡ１１〜Ａ５５」のように記述する）が得られ、プロセス１２では、演算処理の結果、データＢ１１〜Ｂ５５が得られ、…、プロセス５５では、演算処理の結果、データＹ１１〜Ｙ５５が得られる。なお、以降で行われるデータ転送では、図３１に示すように、プロセス１１にデータ＜Ａ１１〜Ｙ１１＞、プロセス１２にデータ＜Ａ１２〜Ｙ１２＞、…、プロセス５４にデータ＜Ａ５４〜Ｙ５４＞、プロセス５５にデータ＜Ａ５５〜Ｙ５５＞を所持させるように、データのやりとりを行う（Reduce_scatter転送）。なお、本第２の実施形態における「データ＜Ａ１１〜Ｙ１１＞」という表記は、データＡ１１、Ｂ１１、…、Ｘ１１、Ｙ１１の全てを加算した１つの合算データを意味する。
【００４９】
次のステップＳ１１１では、各プロセスが、方向を示すパラメータｍを１に設定するとともに、加算回数カウンタｋを０に設定する。
【００５０】
次のステップＳ１１２では、各プロセスが、第ｍ方向（ここでは、第１方向（図１５の上下方向））に隣接するプロセス（ここでは、下方向に隣接するプロセスであるものとする）に対して、転送目標のプロセスに送るべきデータを転送する。なお、この場合の転送目標のプロセスとは、例えば、自己から下側に２プロセス離れた位置に存在するプロセスであるものとする。すなわち、例えば、プロセス１１の転送目標のプロセスはプロセス３１であり、プロセス２１の転送目標のプロセスはプロセス４１であり、プロセス３１の転送目標のプロセスはプロセス５１である。また、プロセス４１の転送目標のプロセスは１つ下側のプロセス５１の更に下側にプロセスが無いので、最上段のプロセス１１となる。また、プロセス５１の転送目標のプロセスは、プロセス２１である。その他のプロセスについても同様に、転送目標プロセスが設定されている。
【００５１】
したがって、ステップＳ１１２では、プロセス１１、２１，３１，４１，５１のみを取り出して示す図１８のように、プロセス１１が、プロセス３１に送るべきデータ（太線枠で囲んだデータＡ３１〜Ａ３５）を隣接するプロセス２１に転送する。また、プロセス１１の上記転送とほぼ同時に、プロセス２１が、プロセス４１に送るべきデータ（太線枠で囲んだデータＦ４１〜Ｆ４５）を隣接するプロセス３１に転送し、プロセス３１が、プロセス５１に送るべきデータ（太線枠で囲んだデータＫ５１〜Ｋ５５）を隣接するプロセス４１に転送し、プロセス４１が、プロセス１１に送るべきデータ（太線枠で囲んだデータＰ１１〜Ｐ１５）を隣接するプロセス５１に転送し、プロセス５１が、プロセス２１に送るべきデータ（太線枠で囲んだデータＵ２１〜Ｕ２５）を隣接するプロセス１１に転送する。なお、図１８に示されていないその他の列のプロセス（プロセス１２、１３…）も、同様のデータ転送をほぼ一斉に行う。
【００５２】
次いで、ステップＳ１１４では、各プロセスが、新たに受け取ったデータと、このデータに対応する自己が元々所持していたデータ、すなわち新たに受け取ったデータの番号と一致する番号を有するデータと、を加算（合算）する。
【００５３】
具体的には、プロセス１１では、図１９においてハッチングを付した領域に存在するデータ同士、データＡ２１とデータＵ２１とを加算し１つのデータとする。また、データＡ２２とＵ２２、データＡ２３とＵ２３，データＡ２４とＵ２４データＡ２５とＵ２５についても加算し、それぞれ１つのデータとする。その他のプロセスにおいても同様の加算処理を行う。
【００５４】
次いで、ステップＳ１１５では、各プロセスが、加算回数カウンタｋを１インクリメントして（ここではｋ＝１にして）、ステップＳ１１６に移行する。
【００５５】
次いで、ステップＳ１１６では、各プロセスが、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、プロセス１１が加算したデータの中に、番号「１１」を含むデータはなく、その他のプロセスにおいても同様であるので、ここでの判断は否定され、ステップＳ１１８に移行する。
【００５６】
ステップＳ１１８では、各プロセスが、ステップＳ１１４にて加算したデータを第１方向の一側（下側）に隣接するプロセスにほぼ同時に転送する。具体的には、図２０に示すように、各プロセスが、太線枠で囲んだデータを下側に隣接するプロセスに転送する。なお、図２０では、ステップＳ１１８のデータ転送直後の状態が示されている。そして、次のステップＳ１１４では、新たに受け取ったデータと、このデータに対応するデータ（図２０においてハッチングを付した領域内にあるデータ）を加算する。
【００５７】
次いで、ステップＳ１１５では、各プロセスが、ｋを１インクリメント（ｋ＝２）し、ステップＳ１１６において、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、図２０に示すように、プロセス１１が加算したデータの中に、番号「１１」を含むデータがあり、その他のプロセスにおいても同様であるので、ここでの判断は肯定され、ステップＳ１２０に移行する。
【００５８】
次のステップＳ１２０では、各プロセスが、ｋの値を参照し、ｋが第１方向に並ぶプロセス数（ここでは５）から１を引いた回数（ここでは４回）と一致するか否かを判断する。現段階では、ｋ＝２であるので、判断は否定され、ステップＳ１２２に移行する。
【００５９】
ステップＳ１２２では、各プロセスが、次の転送目標のプロセスを設定するとともに、データの転送方向を変更（下方向から上方向へ反転）する。ここでは、次の転送目標のプロセスを、前に設定されていた転送目標のプロセスの１つ下側、具体的には自己の２つ上側に位置するプロセスに設定するものとする。すなわち、プロセス５１の転送目標のプロセスはプロセス３１であり、プロセス４１の転送目標のプロセスはプロセス２１であり、プロセス３１の転送目標のプロセスはプロセス１１であり、プロセス２１の転送目標のプロセスは１つ上側のプロセス１１の更に上側にプロセスが無いので、最下段のプロセス５１であり、プロセス１１の転送目標のプロセスはプロセス４１である。その他の列のプロセスにおいても、同様に転送目標のプロセスが設定される。
【００６０】
次いで、ステップＳ１１２では、各プロセスが、第１方向の上側に隣接するプロセスに対して、転送目標のプロセスに送るべきデータをほぼ同時に転送する。具体的には、図２１に示すように、プロセス５１が、プロセス３１に送るべきデータ（太線枠で囲んだデータＵ３１〜Ｕ３５）をプロセス４１に転送する。また、これとほぼ同時に、プロセス４１が、プロセス２１に送るべきデータ（太線枠で囲んだデータＰ２１〜Ｐ２５）を隣接するプロセス３１に転送し、プロセス３１が、プロセス１１に送るべきデータ（太線枠で囲んだデータＫ１１〜Ｋ１５）を隣接するプロセス２１に転送し、プロセス２１が、プロセス５１に送るべきデータ（太線枠で囲んだデータＦ５１〜Ｆ５５）を隣接するプロセス１１に転送し、プロセス１１が、プロセス４１に送るべきデータ（太線枠で囲んだデータＡ４１〜Ａ４５）をプロセス５１に転送する。なお、その他の列のプロセスにおいても、同様の転送が行われる。
【００６１】
次いで、ステップＳ１１４では、各プロセスが、新たに受け取ったデータと、このデータに対応するデータ（番号が合致するデータ）を加算する。すなわち、プロセス１１では、図２１においてハッチングを付した領域に存在するデータ同士、データＡ５１とＵ５１、データＡ５２とＵ５２、データＡ５３とＵ５３、データＡ５４とＵ５４、データＡ５５とＵ５５とを加算し、それぞれ１つの合算データとする。なお、その他のプロセスにおいても同様の加算処理を行う。
【００６２】
次いで、ステップＳ１１５では、各プロセスが、ｋを１インクリメント（ｋ＝３）し、ステップＳ１１６において、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、図２１に示すように、プロセス１１が加算したデータの中に、番号「１１」を含むデータがなく、その他のプロセスにおいても同様であるので、ここでの判断は否定され、ステップＳ１１８に移行する。
【００６３】
ステップＳ１１８では、各プロセスが、ステップＳ１１４において加算したデータを第１方向上側に隣接するプロセスに転送する。具体的には、各プロセスが、図２２において太線枠で囲んだデータを上側に隣接するプロセスに転送する。なお、図２２では、ステップＳ１１８のデータ転送後の状態が示されている。そして、次のステップＳ１１４では、新たに受け取ったデータと、このデータに対応するデータ（図２２においてハッチングを付した領域内に存在するデータ）を加算する。
【００６４】
上記処理の結果、図２２に示すように、プロセス１１は、データＡ１１、Ｆ１１、Ｋ１１、Ｐ１１、Ｕ１１の合算データ＜Ａ１１、Ｆ１１、Ｋ１１、Ｐ１１、Ｕ１１＞を含むデータを所持することになる。また、プロセス２１は、データＡ２１、Ｆ２１、Ｋ２１、Ｐ２１、Ｕ２１の合算データ＜Ａ２１、Ｆ２１、Ｋ２１、Ｐ２１、Ｕ２１＞を含むデータを所持し、…、プロセス５１は、データＡ５１、Ｆ５１、Ｋ５１、Ｐ５１、Ｕ５１の合算データ＜Ａ５１、Ｆ５１、Ｋ５１、Ｐ５１、Ｕ５１＞を含むデータを所持することになる。
【００６５】
次いで、ステップＳ１１５ではｋを１インクリメント（ｋ＝４）し、ステップＳ１１６において、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、図２２に示すように、プロセス１１が加算したデータの中に、番号「１１」を含むデータがあり、その他のプロセスにおいても同様であるので、ここでの判断は肯定され、ステップＳ１２０に移行する。
【００６６】
次のステップＳ１２０では、各プロセスが、ｋの値を参照し、ｋが第１方向に並ぶプロセス数（ここでは５）から１を引いた回数（ここでは４回）と一致するか否かを判断する。現段階では、ｋ＝４であるので、判断は肯定され、ステップＳ１２４に移行する。
【００６７】
次のステップＳ１２４では、ｍ＝ｎであるか、すなわち、ｎ次元方向の全ての方向にデータを転送したか否かを判断する。本実施形態では、ｎが２であるのに対し、ここでは、ｍ＝１であるので判断は否定される。次いで、ステップＳ１２６では、各プロセスが、ｍを１インクリメントし、次のステップＳ１２８においてｋを０に設定した後、ステップＳ１１２に戻る。
【００６８】
これ以降は、第２方向に関するデータ転送が実行される。なお、第２方向に関するデータ転送を開始する前の段階では、プロセス１１〜１５を取り出して示す図２３のように、各プロセスが５つのデータを加算したデータを５つずつ所持している。
【００６９】
次のステップＳ１１２では、各プロセスが、転送目標のプロセスに送るべきデータを第２方向（ここでは右側）に隣接するプロセスに転送する。なお、ここでの転送目標のプロセスとしては、自己のプロセスから２プロセスだけ右側に位置するプロセスが設定されるものとする。すなわち、ステップＳ１１２では、図２４において太線枠で囲まれたデータを、図２５に示すように右隣のプロセスに送信する。次いで、ステップＳ１１４では、各プロセスが、新たに受け取ったデータと、このデータに対応するデータとを加算する。具体的には、図２５にハッチングを付して示す領域内に属するデータを加算する。
【００７０】
次のステップＳ１１５では、各プロセスがｋを１インクリメント（ｋ＝１）し、ステップＳ１１６では、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、図２５に示すように、プロセス１１が加算したデータの中に、番号「１１」を含むデータがなく、その他のプロセスにおいても同様であるので、判断は否定され、ステップＳ１１８に移行する。
【００７１】
次いで、ステップＳ１１８では、各プロセスが、ステップＳ１１４において加算したデータを右隣のプロセスに転送する。具体的には、各プロセスが、図２６において太線枠で囲んだデータを図２７に示すように右隣のプロセスに転送する。そして、次のステップＳ１１４では、新たに受け取ったデータと、このデータに対応するデータ（図２７においてハッチングを付した領域内に存在するデータ）を加算する。
【００７２】
次いで、ステップＳ１１５において、各プロセスが、ｋを１インクリメント（ｋ＝２）すると、次のステップＳ１１６では、直前に加算したデータの番号の中に、自己のプロセスの番号と一致する番号が存在するか否かを判断する。ここでは、図２７に示すように、プロセス１１が加算したデータの中に、番号「１１」を含むデータがあり、その他のプロセスにおいても同様であるので、判断は肯定され、ステップＳ１２０に移行する。
【００７３】
次いで、ステップＳ１２０では、各プロセスが、ｋの値を参照し、ｋが第２方向に並ぶプロセス数（ここでは５）から１を引いた回数（ここでは４回）と一致するか否かを判断する。現段階では、ｋ＝２であるので、判断は否定され、ステップＳ１２２に移行する。
【００７４】
次のステップＳ１２２では、各プロセスが、次の転送目標のプロセスを設定するとともに、データの転送方向を変更（右方向から左方向へ反転）する。ここでは、次の転送目標のプロセスを、前に設定されていた転送目標のプロセスの１つ右側、具体的には自己の２つ左側に位置するプロセスに設定するものとする。すなわち、プロセス１５の転送目標のプロセスがプロセス１３、プロセス１４の転送目標のプロセスがプロセス１２、プロセス１３の転送目標のプロセスがプロセス１１に設定される。また、プロセス１２の転送目標のプロセスは、１つ左側のプロセス１１の更に左側にプロセスが無いので、右端のプロセス１５が設定され、プロセス１１の転送目標のプロセスは、プロセス１４に設定される。その他の行のプロセスにおいても、同様に転送目標のプロセスが設定される。
【００７５】
その後は、図２８に示すように、各プロセスが、転送目標のプロセスに送るべきデータを左隣のプロセスに送り（ステップＳ１１２）、新たに受け取ったデータと、このデータに対応するデータとを加算、すなわち図２８のハッチング領域内のデータを加算し（ステップＳ１１４）、ｋを３にする（ステップＳ１１５）。また、直前に加算したデータを図２９に示すように更に左隣のプロセスに転送し（ステップＳ１１８）、当該転送したデータと、このデータに対応するデータとを加算し（ステップＳ１１４）、ｋを４にする（ステップＳ１１５）。このような処理を行うことにより、図３０に示すように、プロセス１１がＡ１１〜Ｙ１１までの合算データ＜Ａ１１〜Ｙ１１＞を所持し、プロセス１２がＡ１２〜Ｙ１２までの合算データ＜Ａ１２〜Ｙ１２＞を所持し、…プロセス１５がＡ１５〜Ｙ１５までの合算データ＜Ａ１５〜Ｙ１５＞を所持することになる。また、図３１に示すように、システム２００全体においても、各プロセスがプロセス番号ｘｘに対応した合算データ＜Ａｘｘ〜Ｙｘｘ＞を所持することになる。
【００７６】
以上の処理が終了すると、各パラメータは、ｋ＝４、ｍ＝２となっており、ｎは２であるので、ステップＳ１１６の判断、ステップＳ１２０の判断、及びステップＳ１２４の判断の全てが肯定され、図１６の全処理が終了する。
【００７７】
ここで、本第２の実施形態では、第１方向に５プロセス分のデータを下側２回（図１８、図２０）、上側２回（図２１、図２２）の計４回送り、第２方向に１プロセス分のデータを右側に２回（図２５、図２７）、左側に２回（図２８、図２９）の計４回送ることで全てのプロセスｘｘに合算データ＜Ａｘｘ〜Ｙｘｘ＞を所持させることができる。したがって、２５個のプロセスを有するシステムにおける最小限の転送量である２４（＝５×４＋１×４）プロセス分のデータを、８回のデータ転送により送ることができることになる。
【００７８】
図３２には、４×４の２次元トーラス型分散処理システム３００において、従来から行われているReduce_scatter転送を実施した場合の例（比較例）が示されている。
【００７９】
この図３２に示されている比較例では、隣接するトーラス型のシステム（ネットワーク）上で、Reduce_scatter転送（図３３参照）を実施するため、一点鎖線で示されるシステムの上半分と下半分とを超えたデータ転送が必要となる。しかしながら、この場合には、プロセス１１と３１との間や、プロセス２１と４１との間が、直接接続されていないため、符号（１）で示すデータ転送を行っている間は、符合（２）で示すデータ転送を行えないことになる。すなわち、比較例の場合には、データ衝突による待機時間が発生し、データ転送時間が２倍になる。これに対し、本第２の実施形態では、全プロセスが同時に実行する隣接転送のみを行うので、データの衝突は生じない。
【００８０】
以上、詳細に説明したように、本第２の実施形態によると、２次元方向に配列された複数のプロセス１１〜５５が、自己が所持するデータの少なくとも一部を、第１方向に隣接するプロセスに順次転送し、自己が予め所持していたデータ（演算結果）を、第１方向に並ぶプロセスの全てに所持させ、第１方向の転送が終了した後、自己が所持するデータの少なくとも一部を、第２方向に隣接するプロセスに順次転送して、第１方向へのデータ転送処理の後に自己が所持していたデータを、第２方向に並ぶプロセスの全てに所持させるので、全プロセスが同時に実行する隣接転送により、システム上におけるデータの衝突を無くすことができる。これにより、データの衝突による待ち時間が発生しないことから、転送時間、転送回数を少なくすることが可能である。
【００８１】
また、本第２の実施形態によると、各プロセスが他の全てのプロセスに転送すべきデータを所持している状態から、転送目標に対して転送するデータを、隣接するプロセスに転送するとともに、当該データを受信した隣接するプロセスが、受信したデータとこれに対応するデータとを加算して、隣接するプロセスに転送するので、簡易な方法により、２次元トーラス型分散処理システムにおけるReduce_scatter転送を実現することができる。
【００８２】
また、本第２の実施形態によると、プロセスの第１方向に関するプロセス数及び第２方向に関するプロセス数を任意に設定しても、問題なくデータ転送を行うことができる。これにより、プロセス数が例えば２のべき乗などに限定されることがないので、システム設計を簡易に行うことが可能である。すなわち、プロセス数は上記第２の実施形態で説明した５×５である場合に限られるものではなく、プロセス数としては、任意の数を採用することが可能である。
【００８３】
また、本第２の実施形態では、第１方向に関して隣接するプロセス間の転送速度が第２方向に関して隣接するプロセス間の転送速度よりも速く、第１方向のデータ転送を第２方向のデータ転送よりも先に実行することとしているので、転送速度の速い方向に多いデータ（５プロセス分のデータ）を転送し、転送速度の遅い方向に少ないデータ（１プロセス分のデータ）を転送することにより、効率的なデータ転送が可能である。ただし、これに限られるものではなく、図１５の左右方向を第１方向に設定し、上下方向を第２方向に設定することとしても良い。
【００８４】
なお、上記第２の実施形態では、転送目標のプロセスを、自己よりもプロセス２つ分離れた位置にあるプロセスに設定する場合について説明したが、これに限られるものではなく、任意のプロセスを設定することができる。例えば、自己のプロセスから４つ離れたプロセスを転送目標のプロセスに設定した場合、図１６のステップＳ１１２〜ステップＳ１１６を４回繰り返すことで、第ｍ方向に関するデータ転送の全てが完了し、ステップＳ１２０が肯定されることになる。この場合、ステップＳ１２２を省略することができる。また、例えば、最初の転送目標のプロセスを第１方向の下側に隣接するプロセスに設定し、次の転送目標のプロセスを第１方向の上側に３プロセス分だけ離れた位置にあるプロセスを設定するようにしても良い。この場合でも、図１６の処理手順により、問題なくデータ転送を行うことができる。
【００８５】
なお、上記第２の実施形態では、ｎ次元トーラス型分散処理システムが２次元トーラス型分散処理システムである場合について説明したが、これに限られるものではない。例えば、３次元トーラス型分散処理システムにも適用可能である。具体的には、例えば、５×５×５の計１２５個のプロセスを有する３次元トーラス型分散処理システムの場合には、各プロセスが演算結果として１２５個のデータを有している。この場合、上記第２実施形態と同様の手順により、第１方向に２５プロセス分のデータを計４回、第２方向に５プロセス分のデータを計４回、第３方向に１プロセス分のデータを計４回転送（及び加算）すれば、全てのプロセスに対して、データを１２５個合算した合算データを所持させることができるようになる。したがって、１２５個のプロセスを有するシステムにおける最小限の転送量である１２４（＝２５×４＋５×４＋１×４）プロセス分のデータを、１２回のデータ転送により送ることができることになる。
【００８６】
なお、４次元以上のトーラス型分散処理システムにおいても、上記と同様のデータ転送を適用することが可能である。なお、３次元以上のトーラス型分散処理システムにおいても、方向別の転送順を、各方向の転送速度に基づいて決定することが好ましい。
【００８７】
なお、上記各実施形態では、図２や図１６の処理をシステム内に存在する全プロセスに実行させるプログラムを、全プロセスに組み込む場合について説明したが、これに限られるものではない。例えば、システム内において、全プロセスを統括制御するコントローラが存在する場合には、図２や図１６の処理を全プロセスに実行させるためのプログラムを、コントローラのみに組み込むこととしても良い。また、システム内のプロセスの１つが、コントローラの役割を果たすこととしても良い。
【００８８】
なお、上記においては、各実施形態を別々に実施する態様について説明したが、これに限らず、第１の実施形態及び第２の実施形態を連続的に実施することとしても良い。この場合、Allreduce転送と全く等価な転送を行うことができる。
【００８９】
上述した各実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【００９０】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムであって、前記各プロセッサは、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送処理と、前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送処理の後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送処理と、を実行することを特徴とするｎ次元トーラス型分散処理システム。
（付記２）前記ｎ次元方向のそれぞれに配列されるプロセッサは、任意の数であることを特徴とする付記１に記載のｎ次元トーラス型分散処理システム。
（付記３）前記第１、第２データ転送処理では、前記各プロセッサは、自己が所持しているデータを隣接するプロセッサに転送する第１転送と、新たに転送されてきたデータを、前記隣接するプロセッサに転送する第２転送と、を実行することを特徴とする付記１又は２に記載のｎ次元トーラス型分散処理システム。
（付記４）前記各プロセッサは、他の全てのプロセッサそれぞれに転送する必要のあるデータを所持しており、前記第１、第２データ転送処理では、前記各プロセッサが、自己から前記一方向側又は他方向側に存在する任意の目標プロセッサに向けて転送する必要のある目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第１転送と、前記目標データを受信したプロセッサが、当該目標データと、自己が有する前記目標プロセッサに対して転送する必要のあるデータとを加算した新たな目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第２転送と、を実行することを特徴とする付記１又は２に記載のｎ次元トーラス型分散処理システム。
（付記５）前記各プロセッサは、前記第２データ転送処理を、前記他方向を異ならせつつ（ｎ−１）回繰り返すことを特徴とする付記１〜４のいずれかに記載のｎ次元トーラス型分散処理システム。
（付記６）前記一方向及び前記他方向は、前記ｎ次元方向それぞれにおける前記データの転送可能速度に応じて決定することを特徴とする付記１〜５のいずれかに記載のｎ次元トーラス型分散処理システム。
（付記７）ｎ次元（ｎは２以上）方向に配列された複数のプロセッサを有するｎ次元トーラス型分散処理システムにおける集団通信方法であって、
前記各プロセッサが、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程と、
前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程と、を含む集団通信方法。
（付記８）前記ｎ次元方向のそれぞれに配列されるプロセッサは、任意の数であることを特徴とする付記７に記載の集団通信方法。
（付記９）前記第１、第２データ転送工程では、前記各プロセッサは、自己が所持しているデータを隣接するプロセッサに転送する第１転送と、新たに転送されてきたデータを、前記隣接するプロセッサに転送する第２転送と、を実行することを特徴とする付記７又は８に記載の集団通信方法。
（付記１０）前記各プロセッサは、他の全てのプロセッサそれぞれに転送する必要のあるデータを所持しており、前記第１、第２データ転送工程では、前記各プロセッサが、自己から前記一方向側又は他方向側に存在する任意の目標プロセッサに向けて転送する必要のある目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第１転送と、前記目標データを受信したプロセッサが、当該目標データと、自己が有する前記目標プロセッサに対して転送する必要のあるデータとを加算した新たな目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送する第２転送と、を実行することを特徴とする付記７又は８に記載の集団通信方法。
（付記１１）前記第２データ転送工程は、前記他方向を異ならせつつ（ｎ−１）回繰り返されることを特徴とする付記７〜１０のいずれかに記載の集団通信方法。
（付記１２）前記一方向及び前記他方向は、前記ｎ次元方向それぞれにおける前記データの転送可能速度に応じて決定されることを特徴とする付記７〜１１のいずれかに記載の集団通信方法。
（付記１３）ｎ次元トーラス型分散処理システムに属するｎ次元（ｎは２以上）方向に配列された複数のプロセッサに、自己が所持するデータの少なくとも一部を、前記ｎ次元方向のうちの一方向に隣接するプロセッサに順次転送して、自己が予め所持していた元データの少なくとも一部を、前記一方向に並ぶプロセッサの全てに所持させる第１データ転送工程、及び前記ｎ次元方向のうちの他方向に隣接するプロセッサに、自己が所持しているデータの少なくとも一部を順次転送して、直前に行われたデータ転送工程後に自己が所持していたデータの少なくとも一部を、前記他方向に並ぶプロセッサの全てに所持させる第２データ転送工程、を実行させることを特徴とする集団通信プログラム。
（付記１４）前記ｎ次元方向のそれぞれに配列されるプロセッサは、任意の数であることを特徴とする付記１３に記載の集団通信プログラム。
（付記１５）前記第１、第２データ転送工程は、前記各プロセッサに、自己が所持しているデータを隣接するプロセッサに転送させる第１転送と、新たに転送されてきたデータを、前記隣接するプロセッサに転送させる第２転送と、を含むことを特徴とする付記１３又は１４に記載の集団通信プログラム。
（付記１６）前記各プロセッサは、他の全てのプロセッサそれぞれに転送する必要のあるデータを所持しており、前記第１、第２データ転送工程は、前記各プロセッサに、自己から前記一方向側又は他方向側に存在する任意の目標プロセッサに向けて転送する必要のある目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送させる第１転送と、前記目標データを受信したプロセッサに、当該目標データと、自己が有する前記目標プロセッサに対して転送する必要のあるデータとを加算した新たな目標データを、前記目標プロセッサに近づく方向において隣接するプロセッサに転送させる第２転送と、を含むことを特徴とする付記１３又は１４に記載の集団通信プログラム。
（付記１７）前記第２データ転送工程を、前記各プロセッサに、前記他方向を異ならせつつ（ｎ−１）回実行させることを特徴とする付記１３〜１６のいずれかに記載の集団通信プログラム。
（付記１８）前記一方向及び前記他方向は、前記ｎ次元方向それぞれにおける前記データの転送可能速度に応じて決定されることを特徴とする付記１３〜１７のいずれかに記載の集団通信プログラム。
【符号の説明】
【００９１】
１１〜５５  プロセス（プロセッサ）
１００  ２次元トーラス型分散処理システム
２００  ２次元トーラス型分散処理システム
【図１】
2010211553.tif 000003
【図２】
2010211553.tif 000004
【図３】
2010211553.tif 000005
【図４】
2010211553.tif 000006
【図５】
2010211553.tif 000007
【図６】
2010211553.tif 000008
【図７】
2010211553.tif 000009
【図８】
2010211553.tif 000010
【図９】
2010211553.tif 000011
【図１０】
2010211553.tif 000012
【図１１】
2010211553.tif 000013
【図１２】
2010211553.tif 000014
【図１３】
2010211553.tif 000015
【図１４】
2010211553.tif 000016
【図１５】
2010211553.tif 000017
【図１６】
2010211553.tif 000018
【図１７】
2010211553.tif 000019
【図１８】
2010211553.tif 000020
【図１９】
2010211553.tif 000021
【図２０】
2010211553.tif 000022
【図２１】
2010211553.tif 000023
【図２２】
2010211553.tif 000024
【図２３】
2010211553.tif 000025
【図２４】
2010211553.tif 000026
【図２５】
2010211553.tif 000027
【図２６】
2010211553.tif 000028
【図２７】
2010211553.tif 000029
【図２８】
2010211553.tif 000030
【図２９】
2010211553.tif 000031
【図３０】
2010211553.tif 000032
【図３１】
2010211553.tif 000033
【図３２】
2010211553.tif 000034
【図３３】
2010211553.tif 000035
【図３４】
2010211553.tif 000036