(57)【特許請求の範囲】
【請求項１】
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する並列情報処理装置であって、
前記ラテン方陣のトポロジーに対応する有限射影平面内の格子構造に含まれるスイッチ群からｎ×ｋ個のスイッチを特定し、さらに、特定したスイッチのそれぞれに対応するブロックのそれぞれからなるｎ×ｋ個のブロックを特定する特定部と、
特定されたｎ×ｋ個の前記ブロックのそれぞれに含まれる、スイッチに接続されたｍ（ｍ≦ｋ）個のノードのそれぞれについて、有限射影平面内の格子構造において、当該ノードが送信元となる通信が有する傾きと、有限射影平面内の格子構造において、当該ノードが送信元となる通信が有するホップ数を含む通信手順情報を作成する作成部であって、同じフェーズにおいては、ｍ個のノードの間で前記傾きは互いに異なるものである、前記作成部と、
前記通信手順情報に基づき、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信元とし、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信先とする通信を行うことで、ｎ×ｋ×ｍ個のノード間にて部分対部分通信を行う通信部と、
を有する、並列情報処理装置。
【請求項２】
前記作成部は、フェーズの時間間隔毎に前記通信手順情報を作成する、
請求項１に記載の並列情報処理装置。
【請求項３】
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する前記ラテン方陣のトポロジーに対応する有限射影平面内の格子構造に含まれるスイッチ群からｎ×ｋ個のスイッチを特定し、さらに、特定したスイッチのそれぞれに対応するブロックのそれぞれからなるｎ×ｋ個のブロックを特定し、
特定されたｎ×ｋ個の前記ブロックのそれぞれに含まれる、スイッチに接続されたｍ（ｍ≦ｋ）個のノードのそれぞれについて、有限射影平面の格子構造において、当該ノードが送信元となる通信が有する傾きと、有限射影平面の格子構造において、当該ノードが送信元となる通信が有するホップ数を含む通信手順情報であって、同じフェーズにおいては、ｍ個のノードの間で前記傾きは互いに異なるものである、前記通信手順情報を作成し、
前記通信手順情報に基づき、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信元とし、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信先とする通信を行うことで、ｎ×ｋ×ｍ個のノード間にて部分対部分通信を行う、
処理をコンピュータが実行する通信手順決定方法。
【請求項４】
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する前記ラテン方陣のトポロジーに対応する有限射影平面内の格子構造に含まれるスイッチ群からｎ×ｋ個のスイッチを特定し、さらに、特定したスイッチのそれぞれに対応するブロックのそれぞれからなるｎ×ｋ個のブロックを特定し、
特定されたｎ×ｋ個の前記ブロックのそれぞれに含まれる、スイッチに接続されたｍ（ｍ≦ｋ）個のノードのそれぞれについて、有限射影平面の格子構造において、当該ノードが送信元となる通信が有する傾きと、有限射影平面の格子構造において、当該ノードが送信元となる通信が有するホップ数を含む通信手順情報であって、同じフェーズにおいては、ｍ個のノードの間で前記傾きは互いに異なるものである、前記通信手順情報を作成し、
前記通信手順情報に基づき、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信元とし、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信先とする通信を行うことで、ｎ×ｋ×ｍ個のノード間にて部分対部分通信を行う、
処理をコンピュータに実行させる通信手順決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列情報処理装置、通信手順決定方法及び通信手順決定プログラムに関する。
【背景技術】
【０００２】
複数のノード（以下、「サーバ」ともいう。）が並列して計算を行う並列分散処理システムにおいて、全対全通信の信号伝送における広い帯域の確保と低い遅延とを両立するネットワーク管理技術が知られている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１３−２５５０５号公報
【特許文献２】米国特許第５１４２６８６号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、並列分散処理においてすべてのノードを対象に全対全通信を行うと、コストが高くなったり、効率が低下したりするという課題が生じる場合がある。低コストでより効率的にデータのやりとりを行うためには、より少ないスイッチ数でより多くのノードをつなぐトポロジー構造が重要になってくる。
【０００５】
そこで、一側面では、本発明は、ノード間の部分対部分通信において経路競合を抑止することを目的とする。
【課題を解決するための手段】
【０００６】
一つの案では、ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する並列情報処理装置であって、前記ラテン方陣のトポロジーに対応する有限射影平面内の格子構造に含まれるスイッチ群からｎ×ｋ個のスイッチを特定し、さらに、特定したスイッチのそれぞれに対応するブロックのそれぞれからなるｎ×ｋ個のブロックを特定する特定部と、特定されたｎ×ｋ個の前記ブロックのそれぞれに含まれる、スイッチに接続されたｍ（ｍ≦ｋ）個のノードのそれぞれについて、有限射影平面内の格子構造において、当該ノードが送信元となる通信が有する傾きと、有限射影平面内の格子構造において、当該ノードが送信元となる通信が有するホップ数を含む通信手順情報を作成する作成部であって、同じフェーズにおいては、ｍ個のノードの間で前記傾きは互いに異なるものである、前記作成部と、前記通信手順情報に基づき、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信元とし、ｎ×ｋ個の前記ブロックのそれぞれに含まれる、前記ｍ個のノードを送信先とする通信を行うことで、ｎ×ｋ×ｍ個のノード間にて部分対部分通信を行う通信部と、を有する、並列情報処理装置が提供される。
【発明の効果】
【０００７】
一側面によれば、ノード間の部分対部分通信において経路競合を抑止することができる。
【図面の簡単な説明】
【０００８】
【図１】各種トポロジー構造の一例を示す図。
【図２】全対全通信において競合が発生する場合と発生しない場合との一例を示す図。
【図３】有限射影平面の構造を説明するための図。
【図４】一実施形態にかかるラテン方陣Ｆａｔ−Ｔｒｅｅの構造の一例を示す図。
【図５】有限射影平面の格子構造の特徴を説明するための図。
【図６】一実施形態にかかる並列情報処理装置の機能構成の一例を示す図。
【図７】一実施形態にかかるスケジューリング方法の第一段階の一例を示す図。
【図８】一実施形態にかかるスケジューリング方法の第二段階の一例を示す図。
【図９】一実施形態にかかるベクトル表の一例を示す図。
【図１０】一実施形態にかかる通信パターン表の一例を示す図。
【図１１】一実施形態にかかる通信手順情報に基づく通信経路の一例を示す図。
【図１２】一実施形態の変形例にかかるベクトル表の一例を示す図。
【図１３】一実施形態にかかる通信手順決定方法とオーバーヘッドの一例を示す図。
【図１４】一実施形態にかかる通信手順決定方法の評価の一例を示す図。
【図１５】一実施形態にかかる通信手順決定方法の評価の一例を示す図。
【図１６】一実施形態にかかる通信手順決定方法の評価の一例を示す図。
【図１７】一実施形態にかかる並列情報処理装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【０００９】
以下、本発明の一実施形態について添付の図面を参照しながら説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複した説明を省く。
（はじめに）
近年、複数のノードが並列して計算を行う並列分散処理システム（クラスタシステム）は大規模化の傾向にあり、より多くのノードを接続して並列に処理するシステムが普及している。ノードを接続する際のトポロジー構造としてはＦａｔ−Ｔｒｅｅが広く用いられている。例えば、図１（ｂ）は、２段構成のＦａｔ−Ｔｒｅｅの一例を示す。ＳｐｉｎｅスイッチＳは、ｌｅａｆスイッチＬに繋がるスイッチである。ＬｅａｆスイッチＬは、ノードＮ（サーバ）に繋がっているスイッチである。
【００１０】
Ｆａｔ−Ｔｒｅｅでは、ｓｐｉｎｅスイッチＳのそれぞれがすべてのｌｅａｆスイッチＬに接続される。例えば、図１（ｂ）の２段のＦａｔ−Ｔｒｅｅの例では、３つのｓｐｉｎｅスイッチＳのそれぞれが３つのｌｅａｆスイッチＬに接続されている。また、ｌｅａｆスイッチＬのそれぞれは３つのノードＮに接続されている。
【００１１】
例えば、図２（ａ）のＴｒｅｅ構造では、ｌｅａｆスイッチＬと繋がる３つのノードＮから出力された情報（メッセージ）が１段目のｌｅａｆスイッチＬから２段目のｓｐｉｎｅスイッチＳ２に送られる際に経路競合が発生する。また、２段目のｓｐｉｎｅスイッチＳ２から３段目のｓｐｉｎｅスイッチＳ１に送られる際に経路競合が発生する。これに対して、図２（ｂ）のＦａｔ−Ｔｒｅｅ構造では、Ｔｒｅｅ構造リンクＣが多重化された構造になっているため、経路競合は発生しない。つまり、図２（ｂ）のＦａｔ−Ｔｒｅｅ構造では、経路競合が生じることなく、ノード間においてＡｌｌ−ｔｏ−ａｌｌ通信（「全対全通信」ともいう。）を行うことができる。なお、Ｆａｔ−Ｔｒｅｅ構造のトポロジーにおいて全ノードＮから全ノードに対して情報の送受信を行う通信をＡｌｌ−ｔｏ−ａｌｌ通信（全対全通信）という。
【００１２】
ノードＮを接続する際に必要なスイッチのコストは高いため、出来るだけスイッチ数を削減したい。図２（ｂ）のＦａｔ−Ｔｒｅｅ構造でノードＮを接続すると、ノードＮ間の経路が複数あることからネットワークの性能は高いものの、多くのスイッチを必要とするためコストが高くなる。
【００１３】
そこで、図１（ｂ）のＦａｔ−Ｔｒｅｅと比較して少ないスイッチ数で多くのノードを接続可能なラテン方陣Ｆａｔ−Ｔｒｅｅ（「有限射影平面Ｆａｔ−Ｔｒｅｅ」ともいう。）のトポロジー構造が提案されている。図１（ａ）は、ラテン方陣Ｆａｔ−Ｔｒｅｅの一例を示す。ＳｐｉｎｅスイッチＳのそれぞれは、３つのｌｅａｆスイッチＬに接続され、すべてのｌｅａｆスイッチＬには接続されていない。このため、このトポロジー構造は、ノードＮを接続する際のスイッチの台数が少なくて済む。一方で、ノードＮ間の経路が疎であり、ｌｅａｆスイッチＬに接続されているすべてのノードＮ間にて行われるＡｌｌ−ｔｏ−ａｌｌ通信などの高負荷な通信処理を行う際に経路競合を起こしやすい。
【００１４】
しかし、実際には、並列分散処理システム全体に一つの計算ジョブを割り当てることはまれであり、並列分散処理システムの一部のノードを部分的に切り出して、切り出されたノード群におけるＡｌｌ−ｔｏ−ａｌｌ通信によりジョブの並列処理が実現可能である。
【００１５】
以下では、並列分散処理システムにおいてラテン方陣Ｆａｔ−Ｔｒｅｅのトポロジーを用いて、部分的にノードＮ群を切り出してジョブを投入するため、部分的なノード群におけるＡｌｌ−ｔｏ−ａｌｌ通信の経路競合を抑制する方法を提案する。以下、部分的に切り出したノードＮ群におけるＡｌｌ−ｔｏ−ａｌｌ通信を「部分対部分通信」ともいう。
【００１６】
以下に説明する本実施形態にかかる通信手順決定方法では、部分対部分通信の際に経路競合を起こさないように、ノードの切り出し及び切り出したノードにおいて経路競合させないスケジューリングが行われる。これにより、経路競合を抑制し、部分対部分通信にかかる時間を抑制できる。
【００１７】
［有限射影平面の構造］
まず、本実施形態にて使用するラテン方陣Ｆａｔ−Ｔｒｅｅの構造における有限射影平面の構造を述べる。図３（ａ）に示すように、ＳｐｉｎｅスイッチＳＬとＬｅａｆスイッチＬＡ、ＬＢ，ＬＣとがリンクＣで接続されている場合、点をＬｅａｆスイッチＬＡ、ＬＢ、ＬＣ、直線をＳｐｉｎｅスイッチＳＬに対応させる。これにより、図３（ａ）の左側に示すラテン方陣Ｆａｔ−Ｔｒｅｅの構造は、右側に示すトポロジー構造の有限射影平面に置き換えられる。同様にして、図３（ｂ）の左側に示すラテン方陣Ｆａｔ−Ｔｒｅｅの構造は、右側に示す有限射影平面に置き換えられる。
【００１８】
有限射影平面とは、平面に無限遠点をいくつか加え、"平行な２直線"をなくした平面をいう。例えば、有限射影平面では、図３（ｃ）に示す無限遠点において直線は必ず交わり、平行な２直線は存在しない。図３（ｃ）では無限遠点以外においてｎ×ｎ（ｎ＝２）の格子構造が形成される。形成される格子構造は、図３（ｃ）の実線にて示したｎ×ｎ格子構造に限らず、図３（ｃ）の２つの点線にて示した各格子構造であってもよい。
【００１９】
上記ｎは素数である。素数ｎの有限射影平面とは、（ｎ２＋ｎ＋１）個の点とそれらの点のうちｎ＋１個を結ぶ（ｎ２＋ｎ＋１）本の直線からなる平面である。図３（ｃ）の点を結ぶ円も直線と考える。具体的には有限射影平面は、以下で定義される。
【００２０】
・点の構成
一点Ｐを用意する。
ｎ個の点を用意し、ｃ＝０、・・・、ｎ−１に応じてＰ（ｃ）と書く。
同様にｎ２個の点をＰ（ｃ、ｒ）（ｃ、ｒ＝０、・・・、ｎ−１）とする。
【００２１】
・直線の構成
直線および直線が通る点は（ｎ２＋ｎ＋１）本とする。
一本の直線がＬ＝｛Ｐ，Ｐ（０），・・・，Ｐ（ｎ-１）｝で与えられる。
ｎ本の直線を、ｃ＝０，・・・，ｎ-１に応じて、Ｌ（ｃ）＝｛Ｐ，Ｐ（ｃ，０），・・・，Ｐ（ｃ，ｎ-１）｝とする。
ｎ２本の直線をＬ（ｃ，ｒ）＝｛Ｐ（ｃ）およびＰ（ｉ，（ｒ＋ｃｉ）ｍｏｄ  ｎ）｝（ｉ，ｃ，ｒ＝０，・・・，ｎ-１）とする。
【００２２】
・制約
ｎは素数でなければならない。
【００２３】
・特徴
ｎ２＋ｎ＋１点からなる。
ｎ２＋ｎ＋１本の直線が存在する。
任意の２直線は１点で交わる。
任意の２点を結ぶ直線がただ一つ存在する。
【００２４】
Ｐ（ｃ、ｒ）（ｃ、ｒ＝０、・・・、ｎ−１）の部分を格子部分と定義する。点Ｐ、Ｐ（ｃ）は無限遠点と呼ばれ、格子構造では交わらない２直線の交点となっている。これにより、射影平面内ではどの２直線も交わるという性質をもつ。
【００２５】
次に、有限射影平面内の格子構造の特徴について、図４を参照しながら説明する。図４（ａ）は、ｎ＝５、ｎ＝３のそれぞれの格子構造において、左下の１点を通る、異なる傾き方向（傾き０、傾き１、傾き２）の直線及び垂直方向の直線を示す。図４（ｂ）は、同じ傾き（ここでは傾き１）の直線は格子内では交わらないことを示す。ただし、同じ傾きの直線は格子構造外の無限遠点で交わる。
【００２６】
［ラテン方陣Ｆａｔ−Ｔｒｅｅの構造］
ラテン方陣Ｆａｔ−Ｔｒｅｅの構造は、ｎの有限射影平面に対して以下の１〜３の変換を施すことで得られる。
１．直線ＬをＳｐｉｎｅスイッチＳ、点ＰをＬｅａｆスイッチＬに対応させる。
２．直線Ｌ上に点Ｐがある場合、またその場合に限りＳｐｉｎｅスイッチＳとＬｅａｆスイッチＬとをリンクＣで結ぶ。
３．ＬｅａｆスイッチＬの配下にｎ＋１本のノードをつなげる。
【００２７】
このようにして得られるトポロジー構造をラテン方陣Ｆａｔ−Ｔｒｅｅと定義する。ｎ＝３の場合の有限射影平面と、これに対するラテン方陣Ｆａｔ−Ｔｒｅｅの構造を図５に示す。
【００２８】
［ノードの切り出し方法］
部分対部分通信では、全対全通信のノードから、所定範囲のノードを切り出す。その際、ラテン方陣Ｆａｔ−Ｔｒｅｅに対応する有限射影平面の格子構造の部分に注目する。図５の左側に示す有限射影平面の格子構造（ｎ×ｎの形状：ｎ＝３）では、ｎ×ｋ（ｋは任意の自然数）個の矩形が切り出されている。
【００２９】
切り出した矩形内の点にて示されるＬｅａｆスイッチ配下のノードのうちｍ台（ｍはｍ≦ｋをみたす自然数）のノードを取り出す。これにより、格子構造のうち縦ｎ台及び横ｋ台の矩形状のスイッチ群とその配下のノードのうちのｍ台での合計ｍｎｋ台での部分対部分通信が可能である。ここで、ｍ，ｋは１以上ｎ以下の整数であり、ｋ≧ｍの関係が成り立つ。
【００３０】
本実施形態では、ｍ≦ｋ≦ｎなる自然数ｎ、ｋを用いてＤ＝ｍｎｋと表せるようなＤ台を用いたジョブが実行でき、Ｄ台のノード間のＡｌｌ−ｔｏ−ａｌｌ通信、すなわち、部分対部分通信が可能となる。なお、以降の説明のため、各Ｌｅａｆスイッチ配下のノードｍ台に０、１、２、・・・ｍ−１というＬｅａｆスイッチ配下内のノードＩＤを割り当てる。
【００３１】
［並列情報処理装置］
各ノード及び各スイッチには、ＭＰＵ１１１やＣＰＵ１１２が設けられている。部分対部分通信を管理する並列情報処理装置１０は、ＳｐｉｎｅスイッチＳ内のＭＰＵ１１１、ＬｅａｆスイッチＬのＭＰＵ１１１及びｍ台のノードＮのＣＰＵ１１２が共同で動作することにより実行されてもよい。あるいは、スイッチやノード外に設けられた並列情報処理装置１０が、ＳｐｉｎｅスイッチＳ等に設けられたプロセッサとは別に部分対部分通信を制御してもよい。
【００３２】
次に、一実施形態にかかる並列情報処理装置１０の機能構成の一例について、図６を参照しながら説明する。並列情報処理装置１０は、ジョブ受付部１１、特定部１２、作成部１３、記録部１４、ジョブ実行部１５及び通信部１６を有する。
【００３３】
ジョブ受付部１１は、ユーザからジョブが投入されたことに対して、ジョブに関する情報を受け付ける。ジョブに関する情報には、実行に利用するノード数、実行コマンド、並列演算に必要なパワー等の情報が含まれる。
【００３４】
特定部１２は、ラテン方陣のトポロジー内の格子構造に含まれるスイッチ群からｎｋ個のブロックを特定する。ＬｅａｆスイッチＬとその直下のノードＮで構成される部分をブロックと呼ぶ。例えば、特定部１２が、図７の格子構造に含まれるｎｋ個のブロックＵを特定すると、図７のラテン方陣Ｆａｔ−Ｔｒｅｅの構造に含まれる６つのブロックが特定されたことになる。
【００３５】
図６に戻り、作成部１３は、特定されたｎｋ個のブロックのそれぞれのスイッチに接続されたｍ（ｍ≦ｋ）個のノードの異なる傾きの通信方向と、その異なる傾きの通信方向毎に設定したホップ数とを含む通信手順情報を作成する。記録部１４は、通信手順情報を通信手順情報テーブル１４ａに記録する。
【００３６】
ジョブ実行部１５は、Ｄ台（Ｄ＝ｍｎｋ）を用いたジョブを実行する。通信部１６は、通信手順情報に基づき各ブロック内のＬｅａｆスイッチ配下のｍ個のノードＮ毎に通信を行うことで、ノードＮ間にて部分対部分通信を実行する。これにより、Ｄ台を用いたジョブの並列演算処理が実行される。
【００３７】
［スケジューリング方法］
並列情報処理装置１０は、切り出したノードにおいて経路競合させないようにスケジューリングを行う。これにより、経路競合を抑制し、部分対部分通信にかかる時間を抑制できる。
【００３８】
図７の左側に示す格子構造において、並列情報処理装置１０は、ｍｎｋ台の部分対部分通信をスケジューリングする。本実施形態では、ｎ＝３、ｋ＝２、ｍ＝２の１２台の部分対部分通信を一例として挙げる。しかしながら、ｋとｍとは可変とすることができる。これにより、部分対部分通信で使用するノード数とスイッチ数とを柔軟に設定でき、ジョブ毎に適正な台数を使用して並列処理を行うことができる。
【００３９】
まず、並列情報処理装置１０は、図７に示すように、ＬｅａｆスイッチＬ直下の部分対部分通信に参加するノードｍ台を順番に０，１・・・，ｍ−１とＩＤ付けする。後述するように、各フェーズで同一ＩＤのノードは同一の直線方向（傾き）及び同一のホップ数で情報を送る。
【００４０】
送信経路は、送信元ノードＮ→直上のＬｅａｆスイッチＬ→ＳｐｉｎｅスイッチＳ→ＬｅａｆスイッチＬ→直下の宛先（送信先）のノードＮとなる。本実施形態では、この送信経路を経由した送信を２つの段階に分ける。
【００４１】
第一段階では、並列情報処理装置１０は、送信元ノードＮ→直上のＬｅａｆスイッチＬ→ＳｐｉｎｅスイッチＳ→ＬｅａｆスイッチＬ、つまり、ブロックを統括するＬｅａｆスイッチＬまで情報を送信する。
【００４２】
第二段階では、並列情報処理装置１０は、ブロックを統括するＬｅａｆスイッチＬ→宛先（送信先）のノードＮ、つまり、各ブロック内のＬｅａｆスイッチＬから直下のノードＮへ情報を送信する。
【００４３】
第一段階の送信では、例えば、図７の左側に示す格子構造のＩＤ０のノードＮは、垂直方向に２ホップで情報を送る。この場合、図７のラテン方陣Ｆａｔ−Ｔｒｅｅでは、情報は、ＩＤ０のノードＮ→Ｐ（０，０）のＬｅａｆスイッチＬ→Ｌ（０）のＳｐｉｎｅスイッチＳ→Ｐ（０，２）のＬｅａｆスイッチＬに送信される。
【００４４】
図７の左側に示す格子構造のＩＤ１のノードＮは、傾き１の方向に１ホップで情報を送る。この場合、図７のラテン方陣Ｆａｔ−Ｔｒｅｅでは、情報は、ＩＤ１のノードＮ→Ｐ（０，０）のＬｅａｆスイッチＬ→Ｌ（１、０）のＳｐｉｎｅスイッチＳ→Ｐ（１，１）のＬｅａｆスイッチＬに送信される。
【００４５】
以上から、並列情報処理装置１０は、格子構造のスイッチ群の傾きとホップ数を決めれば、ＳｐｉｎｅスイッチＳ及びＬｅａｆスイッチＬを介したノード間の通信経路を決定することができる。
【００４６】
各ＬｅａｆスイッチＬの直下にはｍ台のノードＮがあり、これらは同一のＬｅａｆスイッチＬを経由する。したがって、経路競合を抑制するためには同一のＳｐｉｎｅスイッチＳを経由してはならない。言い換えれば、ｍ台のノードＮから送信される情報は、同一の傾きに送信してはならない。すなわち、ｍ台のノードＮから送信される情報を、異なる傾きに送信すれば、同一のＳｐｉｎｅスイッチＳを経由せずに宛先のノードＮが含まれるブロックを統括するＬｅａｆスイッチＬまで情報を送信でき、経路競合が生じないようにすることができる。
【００４７】
よって、並列情報処理装置１０は、各フェーズにおいて異なる傾きになるようにスイッチ群の傾きとホップ数を決めるようにスケジューリングを行う。このスケジューリングは、後述されるｍｎｋのベクトル表を作成することで実現される。
【００４８】
第二段階の送信では、例えば、第一段階が終了した時点で各ブロック内のＬｅａｆスイッチＬはｍ個の通信を受け取っているので、これを直下のノードＮに配分する。この配分にｍフェーズが必要となる。
【００４９】
ここで、第一段階では、各ＬｅａｆスイッチＬに接続されたｍ個のノードＮが同時にブロックを統括するｌｅａｆスイッチＬに情報を送る。第二段階において、各ＬｅａｆスイッチＬが受信したｍ個の情報は、１フェーズ群のｍフェーズにおいて巡回的に配下のノードＮに送られる。例えば、ｍｎｋ台の部分対部分通信の場合、ｎｋ（＝ｍｎｋ／ｍ）のフェーズ群がある。１つずつの送信をフェーズといい、ｍ個の送信であるｍフェーズをまとめてフェーズ群という。
【００５０】
第二段階では、１フェーズ群のｍフェーズにおいて巡回的に配下への送信を行う。例えば、図８（ａ）では、ｍ＝２のとき、ＩＤ０、ＩＤ１の送信元のノードＮから２個の情報を受信したＬｅａｆスイッチＬがＩＤ０、ＩＤ１の送信先のノードＮに送信する場合、２フェーズにおいて巡回的にブロック内のノードＮに情報を送る。これにより、ＩＤ０、ＩＤ１の送信先のノードＮは、２フェーズ（フェーズ群）でＩＤ０、ＩＤ１の送信元のノードＮから２個の情報を受信する。
【００５１】
同様に、図８（ｂ）では、ｍ＝３のとき、ＩＤ０〜ＩＤ２の送信元のノードＮから３個の情報を受信したＬｅａｆスイッチＬがＩＤ０〜ＩＤ２の送信先のノードＮに送信する場合、３フェーズにおいて巡回的にブロック内のノードＮに情報を送る。これにより、ＩＤ０の送信先のノードＮは、３フェーズ（フェーズ群）でＩＤ０〜ＩＤ２の送信元のノードＮから３個の情報を受信する。
【００５２】
［ベクトル表の作成］
並列情報処理装置１０は、一実施形態にかかる通信手順情報（以下、「ベクトル表」ともいう。）を作成する。以下では、ベクトル表の作成方法の一例について、図９〜図１２を参照しながら説明する。なお、以下のベクトル表の作成は、並列情報処理装置１０の作成部１３が行う。
【００５３】
図７に示すように、ラテン方陣のトポロジー内の格子構造に含まれるスイッチ群からｎｋ個のブロックが特定されている。作成部１３は、特定されたｎｋ個のブロックのｍ個のノードＮがどの傾きとホップ数とを指定して送信をするかを表したｎｋ（ブロック数）×ｍのベクトル表を作成する。
【００５４】
図９（ａ）に示すベクトル表のどの列（同一ブロック）においても、傾きが重複してはならない。ホップ数については特に制限はなく、重複のないように設定することができる。傾きの個数は以下のようになる。
・傾き０〜ｎ−１の個数は、自分自身を除いて（ｋ−１）個ずつ
・垂直方向の個数は、自分自身を除いて（ｎ−１）
・自分自身の傾きの個数は、１個（自分自身のノードに情報を送る場合）
・傾きの個数の合計は、ｎ（ｋ−１）＋（ｎ−１）＋１＝ｎ×ｋ個
作成部１３は、ベクトル表の各行（サーバＩＤ）に下記の個数の傾きがもれなく書き入れられるようにベクトル表を作成する。ここで、通信パターンを具体的なベクトル表で表現する。図９（ｂ）に（ｎ，ｋ，ｍ）＝（３，２，２）の場合のベクトル表の一例を示す。図９（ｂ）に一例を示すように、ベクトル表は、ある送信元Ｌｅａｆスイッチ配下内のノードＩＤが０〜ｍ−１に対応するノードＮから各フェーズ群における、宛先Ｌｅａｆスイッチを決定する表である。
【００５５】
図９（ｂ）のベクトル表の行方向はＬｅａｆ配下内のノードＩＤ、列方向はフェーズ群が示される。ベクトル表は、Ｌｅａｆ配下内のノードＩＤにおけるｎｋのフェーズ群での宛先Ｌｅａｆスイッチをベクトルで指定する。このベクトルはすべての送信元Ｌｅａｆスイッチにおいて、その送信元Ｌｅａｆを始点としたベクトルであり、これによって対応する宛先が定まる。
【００５６】
Ｌｅａｆ配下内のノードＩＤ０の列には順に、傾きが垂直のベクトル（ｎ−１本：図９では垂直（１）、垂直（２））、各ｓ＝０，１、・・・、ｎ−１について、傾きがＳであるベクトル（ｋ−１本ずつ：図９では０（１）、１（１）、２（１））が設定される。そして、最後にゼロベクトル（１本：図９では自（自分自身のノードを示す））が設定される。図９（ｂ）のベクトル表の（）内は、ホップ数を示す。
【００５７】
Ｌｅａｆ配下内のノードＩＤ１の列に関しては、Ｌｅａｆ配下内のノードＩＤ０の列を垂直方向へ下向きにｎ−１個シフトした列を作成する。ただし、下のｎ−１マスに関しては上に移動させる。以下、各列は左隣の列を垂直方向へ下向きにｎ−１個シフトした列として作成する。
【００５８】
ただし、ベクトル表の各列は、左隣の列を垂直方向下向きにｎ−１個シフトした列として作成することとは限らない。（ｍ−１）（ｎ−１）＜ｎｋ−（ｎ−１）が成り立つため、ベクトル表は、例えば、各列は左隣の列を垂直方向へ下向きにｎ−１個からｎｋ−（ｎ−１）個の間のいずれかの個数だけシフトした列として作成することができる。
【００５９】
（ｎ，ｋ，ｍ）＝（３，２，２）の場合、図８（ａ）に示すフェーズ群内の通信パターンと図９のベクトル表から全フェーズの通信パターンを作成すると、図１０に示す表のようになる。通信パターン表に示す通信手順情報は、通信手順情報テーブル１４ａに記録される。
【００６０】
なお、作成部１３は、フェーズの時間間隔毎に通信手順情報を作成する。通信手順情報は、フェーズの時間間隔毎に通信手順情報テーブル１４ａに記録される。
【００６１】
通信部１６は、上記のように作成された通信手順情報に基づきＬｅａｆスイッチＬのそれぞれに接続されたｍ個のノード毎に通信を行うことで、ｍ個のノード間にて経路競合せずに部分対部分通信を行うことができる。
【００６２】
例えば、第０フェーズ群の０番目のフェーズでは図１１のような通信が行われる。まず、ＩＤが０番のノードＮの通信経路について説明する。図９（ｂ）のベクトル表によると、第０フェーズ群ではＬｅａｆ配下内のノードＩＤが０のノードには垂直（１）（すなわち、垂直方向にホップ１）が指定されている。したがって、図１１にて実線で示すように、ノードＩＤが０のノードから出力された情報は、直上のＬｅａｆスイッチＰ（０，０）を経由してｌｅａｆスイッチＰ（０，１）に到達する。ここで、図８（ａ）のｍ＝２の場合によって、送信元Ｌｅａｆ配下内のノードＩＤが０の通信は宛先Ｌｅａｆ配下内のノードＩＤが０に転送されるので、最終的にノード４に転送される。
【００６３】
この通信パターン表に示す通信手順情報では、どの行もどの列も０〜１１が一度ずつ現れる。すなわち、切り出したノード間において経路競合を抑制した部分対部分通信が成立することがわかる。以上から、本実施形態にかかる並列情報処理装置１０及び並列情報処理装置１０による通信手順決定方法によれば、ノード間の部分対部分通信において経路競合を抑制することで部分対部分通信にかかる時間を抑制できる。
【００６４】
［ベクトル表の作成の変形例］
ベクトル表の作成の変形例について、図１２を参照しながら説明する。上記で説明したベクトル表の作成では、ｋ及びｍは任意の数に設定できる。これに対して、変形例にかかるベクトル表の作成では、ｋはｍの倍数の場合に限られる。
【００６５】
図１２（ａ）に示すベクトル表では、各フェーズ群において、ノードＩＤが０番に垂直方向送信を割り当て、残った領域を順に０，１，２，・・・，ｎ−１を割り当てる。最後に自分自身への送信を行う。このようにしてできた表を横方向に巡回的に回してｍ個複製する。図１２（ｂ）ベクトル表は、ｎ＝３，ｋ＝２，ｍ＝２の例である。これによれば、どの行にも同じ数字（又は文字）は現れない。よって、変形例にかかるベクトル表に基づき作成された通信手順情報によっても切り出したノード間において経路競合を抑制した部分対部分通信が成立する。
【００６６】
以上に説明したように、一実施形態に係る本実施形態及び変形例にかかる並列情報処理装置１０及び通信手順決定方法によれば、ノード間の部分対部分通信において衝突を抑止し、経路競合を抑制することができる。これにより、部分対部分通信にかかる時間を抑制できる。また、ポート利用効率が最適なトポロジー構造を用いて、低コストを維持しつつ、部分的なノードを柔軟に選び出して部分対部分通信を行うことができる。
【００６７】
［評価結果の一例］
最後に、評価結果の一例を、図１３〜図１６を参照しながら説明する。ｎ＝１７の場合、ラテン方陣Ｆａｔ−Ｔｒｅｅ構造での接続サーバ台数は５５２６台である。まず、ちょうど必要な台数分のみ切り出すことを許す場合を考える。部分切り出し可能な台数は１１４通りあるため、全体の２.０６％の台数でこのような切り出しが可能となる。
【００６８】
次に、必要な台数よりも多くの台数を切り出して用いることを許す場合を考える。余分に必要となった台数を本来の必要台数で割った比率をオーバーヘッドとする。例えば、１０００台でのＡｌｌ−ｔｏ−ａｌｌ通信を行いたい場合に１０００台以上で実現可能な台数である１０２０（＝１７×１２×５）台でのＡｌｌ−ｔｏ−ａｌｌ通信を行う場合について考察する。この場合、２％（２０台）のノードは必要でないにも関わらずＡｌｌ−ｔｏ−ａｌｌ通信に参加させなくてはならず、オーバーヘッドとなる。
【００６９】
台数の区間別のオーバーヘッドの平均値は図１３のようになる。どの区間でもオーバーヘッドの平均値は高々２．９６％であり、実用上の問題は低いと考えられる。
【００７０】
次に、シミュレーションによる評価結果について説明する。評価方法としてはトポロジー構造としてＦａｔ−Ｔｒｅｅとラテン方陣Ｆａｔ−Ｔｒｅｅの２種類について、次数と通信パターン（３種類）から決まるそれぞれの事例について一部を切り出した部分対部分通信によるスループットをシミュレーションにより計測する。部分対部分通信は、切り出したノード間での「Ａｌｌ−ｔｏ−ａｌｌ通信」を意味する。
【００７１】
評価対象トポロジーは、次数とラテン方陣Ｆａｔ−Ｔｒｅｅにおけるパラメータ（ｎ、ｍ、ｋ）とＦａｔ−Ｔｒｅｅの台数を下記の３種類とした。ラテン方陣Ｆａｔ−Ｔｒｅｅにおけるパラメータから切り出したノード間でのＡｌｌ−ｔｏ−ａｌｌ通信に参加する台数が決定し、この台数とＦａｔ−Ｔｒｅｅでの台数がほぼ同じ値となるように調整した。構成の詳細を図１４に示す。図１４に示す次数とは、各スイッチが他のスイッチと接続しているポート数であり、スイッチ全体のポート数の１／２である。
【００７２】
通信パターンとしては、以下の３つの通信パターンを用いる。
１．シフト通信パターン：シフト通信パターンとは，ｉ番目のフェーズでノード番号Ｓのノードは（Ｓ＋ｉ）％Ｎに送信する、という通信パターンである。ただし、Ｎは切り出したノード数である。
２．本実施形態にかかる通信パターン：これについては、ラテン方陣Ｆａｔ−Ｔｒｅｅのみ評価した。
３．ランダム通信パターン：各送信フェーズにおける送信先は、異なるフェーズで同一のノードが同一の宛先に送信しないようにランダムに送信する。
【００７３】
スループットの計算方法では、各通信フェーズにおいて、各リンクを同時に通る通信の本数をそのリンクに対する経路競合数と定義する。経路競合数が１であれば、そのリンク上で経路競合が発生していないことを表している。各ノード間通信において、途中で通るそれぞれのリンクの経路競合数の最大値を算出し、これを最大経路競合数と呼ぶ。この最大経路競合数の逆数を平均した数値を通信フェーズにおけるスループットと定義し、このスループットを全フェーズで平均した数値をＡｌｌ−ｔｏ−ａｌｌ通信時のスループットと定義する。
【００７４】
評価結果を図１５に示す。図１５に基づき、Ｆａｔ−Ｔｒｅｅとラテン方陣Ｆａｔ−Ｔｒｅｅでのシフト通信方式と本実施形態のスループットを比較する。Ｆａｔ−Ｔｒｅｅでシフト通信パターンを採用すると、スループットが１．０であることから、競合なく通信できている。これに対して、ラテン方陣Ｆａｔ−Ｔｒｅｅでシフト通信パターンを採用してしまうと、スループットが低下し、競合が起こっていることがわかる。本実施形態にかかる通信手順決定方法による通信パターンでは、スループットが１．０であり、これにより、ラテン方陣Ｆａｔ−Ｔｒｅｅでも競合なく切り出したノード間での「Ａｌｌ−ｔｏ−ａｌｌ通信」Ａｌｌ−ｔｏ−ａｌｌ通信ができていることが確認された。
【００７５】
ランダム通信パターンを用い、Ｆａｔ−Ｔｒｅｅとラテン方陣Ｆａｔ−Ｔｒｅｅでのスループットを比較する。また、Ｆａｔ−Ｔｒｅｅで選択する台数の比率をラテン方陣Ｆａｔ−Ｔｒｅｅと同程度になるように調整した場合のスループットも比較する。図１６を参照すると、いずれのトポロジー構造でもランダム通信パターンを用いることで一定のスループット（０．８程度）を期待することができるが、ランダム通信パターンでは競合を完全になくすことはできない。ネットワークの規模が大きくなると性能は低下する傾向にある。
【００７６】
使用ノード数が同程度の場合、Ｆａｔ−Ｔｒｅｅはラテン方陣Ｆａｔ−Ｔｒｅｅよりもスループットが悪いという結果となった。これはＦａｔ−Ｔｒｅｅがラテン方陣Ｆａｔ−Ｔｒｅｅに比べて全体のノード数が少ないために通信が密になることが原因と考えられる。
【００７７】
Ｆａｔ−Ｔｒｅｅにおいて、ノード選択率をラテン方陣Ｆａｔ−Ｔｒｅｅの選択率と同程度になるように調整した場合、スループットはＦａｔ−Ｔｒｅｅの方が良いという結果となった。
【００７８】
（ハードウェア構成例）
最後に、本実施形態に係る並列情報処理装置１０のハードウェア構成について、図１７を参照して説明する。並列情報処理装置１０は、入力装置１０１、表示装置１０２、外部Ｉ／Ｆ１０３、ＲＡＭ（Random Access Memory）１０４、ＲＯＭ（Read Only Memory）１０５、ＣＰＵ（Central Processing Unit）１０６、通信Ｉ／Ｆ１０７、及びＨＤＤ（Hard Disk Drive）１０８などを備え、それぞれがバスＢで相互に接続されている。
【００７９】
入力装置１０１は、キーボードやマウスなどを含み、並列情報処理装置１０に各操作信号を入力するために用いられる。表示装置１０２は、ディスプレイなどを含み、各種の処理結果を表示する。通信Ｉ／Ｆ１０７は、並列情報処理装置１０をネットワークに接続するインタフェースである。これにより、並列情報処理装置１０は、通信Ｉ／Ｆ１０７を介して、ノード群とデータ通信を行うことができる。
【００８０】
ＨＤＤ１０８は、プログラムやデータを格納している不揮発性の記憶装置である。格納されるプログラムやデータには、並列情報処理装置１０の全体を制御する基本ソフトウェア及びアプリケーションソフトウェアがある。例えば、ＨＤＤ１０８には、各種のデータベースやノード割当プログラム等のプログラムが格納されてもよい。
【００８１】
外部Ｉ／Ｆ１０３は、外部装置とのインタフェースである。外部装置には、記録媒体１０３ａなどがある。これにより、並列情報処理装置１０は、外部Ｉ／Ｆ１０３を介して記録媒体１０３ａの読み取り及び／又は書き込みを行うことができる。記録媒体１０３ａには、ＣＤ（Compact Disk）、及びＤＶＤ（Digital Versatile Disk）、ならびに、ＳＤメモリカード（SD Memory card）やＵＳＢメモリ（Universal Serial Bus memory）等がある。
【００８２】
ＲＯＭ１０５は、電源を切っても内部データを保持することができる不揮発性の半導体メモリ（記憶装置）である。ＲＯＭ１０５には、プログラム及びデータが格納されている。ＲＡＭ１０４は、ノード割当プログラム等のプログラムやデータを一時保持する揮発性の半導体メモリ（記憶装置）である。ＣＰＵ１０６は、上記記憶装置（例えば「ＨＤＤ１０８」や「ＲＯＭ１０５」など）から、ノード割当プログラム等のプログラムやデータをＲＡＭ１０４上に読み出し、通信手順決定プログラムを実行する。これにより、ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続されたノードとを有する並列情報処理装置において、通信の際の競合を抑制しながら、並列演算を実現することができる。
【００８３】
以上の説明に関し、更に以下の項を開示する。
（付記１）
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する並列情報処理装置であって、
前記ラテン方陣のトポロジー内の格子構造に含まれるスイッチ群からｎ×ｋ個のブロックを特定する特定部と、
特定されたｎ×ｋ個の前記ブロック内のスイッチに接続されたｍ（ｍ≦ｋ）個のノードの異なる傾きの通信方向と、該異なる傾きの通信方向毎に設定したホップ数とを含む通信手順情報を作成する作成部と、
前記通信手順情報に基づきｎ×ｋ個の前記ブロックの前記ｍ個のノード毎に通信を行うことで、前記ｎ×ｋ個の前記ブロックのそれぞれのｍ個のノード間にて部分対部分通信を行う通信部と、
を有する、並列情報処理装置。
（付記２）
前記作成部は、フェーズの時間間隔毎に前記通信手順情報を作成する、
付記１に記載の並列情報処理装置。
（付記３）
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する前記ラテン方陣のトポロジー内の格子構造に含まれるスイッチ群からｎ×ｋ個のブロックを特定し、
特定されたｎ×ｋ個の前記ブロック内のスイッチに接続されたｍ（ｍ≦ｋ）個のノードの異なる傾きの通信方向と、該異なる傾きの通信方向毎に設定したホップ数とを含む通信手順情報を作成し、
前記通信手順情報に基づきｎ×ｋ個の前記ブロックの前記ｍ個のノード毎に通信を行うことで、前記ｎ×ｋ個の前記ブロックのそれぞれのｍ個のノード間にて部分対部分通信を行う、
処理をコンピュータが実行する通信手順決定方法。
（付記４）
フェーズの時間間隔毎に前記通信手順情報を作成する、
付記３に記載の通信手順決定方法。
（付記５）
ラテン方陣のトポロジーで構成されたスイッチ群と、該スイッチ群のうちのいずれかに接続された複数のノードとを有する前記ラテン方陣のトポロジー内の格子構造に含まれるスイッチ群からｎ×ｋ個のブロックを特定し、
特定されたｎ×ｋ個の前記ブロック内のスイッチに接続されたｍ（ｍ≦ｋ）個のノードの異なる傾きの通信方向と、該異なる傾きの通信方向毎に設定したホップ数とを含む通信手順情報を作成し、
前記通信手順情報に基づきｎ×ｋ個の前記ブロックの前記ｍ個のノード毎に通信を行うことで、前記ｎ×ｋ個の前記ブロックのそれぞれのｍ個のノード間にて部分対部分通信を行う、
処理をコンピュータに実行させる通信手順決定プログラム。
（付記６）
フェーズの時間間隔毎に前記通信手順情報を作成する、
付記５に記載の通信手順決定プログラム。
【符号の説明】
【００８４】
１０：並列情報処理装置
１１：ジョブ受付部
１２：特定部
１３：作成部
１４：記録部
１４ａ：通信手順情報テーブル
１５：ジョブ実行部
１６：通信部
【図１】
0006597105.tif 000002
【図２】
0006597105.tif 000003
【図３】
0006597105.tif 000004
【図４】
0006597105.tif 000005
【図５】
0006597105.tif 000006
【図６】
0006597105.tif 000007
【図７】
0006597105.tif 000008
【図８】
0006597105.tif 000009
【図９】
0006597105.tif 000010
【図１０】
0006597105.tif 000011
【図１１】
0006597105.tif 000012
【図１２】
0006597105.tif 000013
【図１３】
0006597105.tif 000014
【図１４】
0006597105.tif 000015
【図１５】
0006597105.tif 000016
【図１６】
0006597105.tif 000017
【図１７】
0006597105.tif 000018