(57)【特許請求の範囲】
【請求項１】
格子トーラス結合ネットワークの機能を包含するハイパキューブネットワークあるいはＮ次元クロスバネットワークを有し、プロセッサ台数Ｎが素数ｘ（≧２）のｎ乗で表せる並列計算機における問題領域分割・割り当て方法であって、
ｎを超えない範囲で問題領域の次元数ｍの設定入力を受け付けて決定するステップと、
物理空間の各次元の格子点数をｎ1，ｎ2，ｎ3，……，ｎm、としたとき、
logxＮ≧logx（ｎ1×ｎ2×ｎ3×……×ｎm）
ｎ1，ｎ2，ｎ3，……，ｎm＝ｘ（≧２）の冪乗    …  （式１）
を満たす領域分割方法候補を選択するステップと、
前記候補の中から使用する領域分割方法を決定するステップと、
１次元表示した分割領域番号と同じ物理番号を有するプロセッサに分割領域を割り当てるステップ
を備えたことを特徴とする問題領域分割・割り当て方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は複数のプロセッサ間でネットワークを介してデータを転送する並列計算機に関する。
【０００２】
【従来の技術】
複数のプロセッサをネットワークで接続した並列計算機の発展に伴い、自然現象を解析する数値シミュレーションが実用化されつつある。自然現象(物理現象)を支配している基本原理の一つは近接作用である。近接作用問題は、数値解法において隣りあった格子点の値のみを使用して計算を進める。並列計算機では、物理空間（問題領域）を分割して、分割したデータ領域をそれぞれプロセッサに割り当てた場合に、隣接するプロセッサ間でのみデータ転送が発生することを意味する。
【０００３】
例えば、２次元格子状に配置されたプロセッサが座標ＰＥ［Ｘ，Ｙ］で表されるとすると、ＰＥ［Ｘ，Ｙ］は、ＰＥ［Ｘ＋１，Ｙ］，ＰＥ［Ｘ−１，Ｙ］，ＰＥ［Ｘ，Ｙ＋１］およびＰＥ［Ｘ，Ｙ−１］に格納されたデータを用いて計算を進める。この隣接転送にもっとも適したネットワークとして、格子結合および格子の端と端を接続したトーラス結合のネットワークがある。格子トーラス結合は、隣接転送の高速処理を対象とした最も単純なネットワークであるため、ネットワークの直径（最も離れたプロセッサ間の距離）が大きく、隣接転送以外の転送パターンになると転送経路の競合が発生し性能が低下する。
【０００４】
一方、ネットワークの直径を小さくし、隣接転送以外の転送パターンでも性能をだすことを目的としたハイパキューブネットワーク，Ｎ次元クロスバネットワークが提案されている。
【０００５】
ハイパキューブネットワークは、２のｍ乗個のプロセッサを２×２×２×……×２とｍ個の因数に分解し、これらの因数の各々を一辺の格子点数とするｍ次元格子空間上にプロセッサを並べ、それらを直接結合してデータ転送経路を構成する。
【０００６】
Ｎ次元クロスバネットワークは、特開平1−267763 号公報に開示されているように、ｎ台のプロセッサをｎ＝ｎ1×ｎ2×ｎ3×……×ｎmと因数分解し、これらの因数の各々を一辺の格子点数とするｍ次元格子空間上にプロセッサを並べ、その各辺をクロスバスイッチからなる部分ネットワークで結合してデータ転送経路を構成する。
【０００７】
ハイパキューブネットワーク，Ｎ次元クロスバネットワークとも格子トーラス結合を包含するネットワークであるため、隣接転送であれば経路の競合がなくデータを最高性能で転送できる。また、格子トーラス結合に比べてより多くの経路を持つため、隣接転送以外の転送パターンでも格子トーラス結合よりも転送経路の競合は少なくなる。
【０００８】
従来、近接作用問題を扱う並列アプリケーションユーザは、プロセッサ間通信を高速にするために、並列計算機の台数，構成を意識し、データ転送で最も高い性能を得られるように（近接作用＝隣接転送になるように）問題領域を分割し、各プロセッサに割り付けてきた。
【０００９】
図９は、従来の分割・割り当て方式を示している。９−２は並列計算機であり、９−１は対象とする問題領域である。並列計算機９−２は２次元構成であり、各プロセッサは２次元座標のプロセッサ番号を有する。従来、ユーザは、図９に示すように対象とする問題領域９−１を並列計算機９−２と同じ次元構成に分割して、分割領域を対応するプロセッサにそのまま割り当てていた。並列計算機がｌ×ｍの２次元構成であれば、問題領域をｌ×ｍの２次元に分割して各プロセッサに割り当てる。並列計算機がｌ×ｍ×ｎ個のプロセッサを持つ３次元構成である場合には、問題領域をｌ×ｍ×ｎの３次元に分割して、分割データ領域を対応するプロセッサにそのまま割り当てる。このように並列計算機の台数と構成を意識して問題領域を分割し、プロセッサに分割データ領域を割り当て、近接作用をそのまま隣接転送に対応させていた。
【００１０】
【発明が解決しようとする課題】
従来の分割方法および割り当て方法では、物理空間における問題領域が並列計算機と同じ次元構成になるように分割し、プロセッサに割り当てている。そのため、使用する並列計算機のネットワークが格子トーラス結合より多くの転送経路を持っていても、隣接転送に使用する経路以外は使用していない。
【００１１】
一方、実際の物理空間には１次元，２次元，３次元，４次元…といったようにさまざまな次元がありえる。一般に、並列計算機の次元構成は動的に変更できない。そのため、問題領域の次元構成が並列計算機の次元構成と異なると、ユーザの労力が増大するだけでなく、領域の分割方法および分割データ領域の割り当て方法によっては隣接転送以外のデータ転送が発生し、その結果、経路の競合が発生して通信性能が低下してしまう。
【００１２】
本発明の目的は、格子トーラス結合を包含するネットワークを効率良く用いて、並列計算機の次元構成が、対象とする近接作用問題領域の次元構成と同じであるかのようにユーザにイメージさせ、そのイメージのままで近接作用問題においてデータ転送を行っても、経路の競合を発生することなく隣接転送を行った場合と同等の通信性能を得られるような問題領域分割方式と、各プロセッサへの領域割り当て方式とそれを備えるライブラリを提供することにある。
【００１３】
【課題を解決するための手段】
上記の目的を達成するために、格子トーラス結合を包含するネットワークを有し、プロセッサ台数Ｎが素数ｘ（≧２）のｎ乗で表せる並列計算機において、本願発明は、
（１）ｎを超えない範囲で問題領域の次元数ｍを決める手段
（２）物理空間の各次元の格子点数をｎ1，ｎ2，ｎ3，……，ｎm、としたとき、
【００１４】
【数３】
logxＮ≧logx（ｎ1×ｎ2×ｎ3×……×ｎm）                    …（式１）
ｎ1，ｎ2，ｎ3，……，ｎm＝ｘ（≧２）の冪乗
を満たす領域分割方法候補の選択手段
（３）候補の中から使用する領域分割方法を決定する手段
（４）１次元表示した分割領域番号と同じ物理番号を有するプロセッサに分割領
域を割り当てる手段
を備える。これらの手段により、近接作用問題領域の次元を並列計算機の次元構成にあわせずに自由に領域を分割し、分割領域間でデータ転送をしても、ネットワーク中の転送経路の競合なしに高速データ転送を実現できる。
【００１５】
【発明の実施の形態】
以下、本発明にかかわる問題領域分割・割り当て方式を図面を参照して説明する。
【００１６】
本発明は、格子トーラス結合を包含するネットワーク（Ｎ次元クロスバネットワーク，ハイパキューブネットワーク，完全クロスバ結合，多段結合等）を有し、プロセッサ台数Ｎが素数ｘ（≧２）のｎ乗で表せる並列計算機に適用できる。また、この並列計算機のネットワークは全２重の経路を持ち、ルーティング方式は固定ルーティングを用いることを前提としている。また、プロセッサは１からＮまでの物理番号を持つ。
【００１７】
図１は本発明の問題領域分割・割り当て方式を備えた計算機ライブラリの全体構成を示したものである。図中、１−１は問題領域次元決定手段、１−２は、領域分割方法候補選択手段、１−３は、分割方法決定手段、１−４は、分割領域割り当て手段である。
【００１８】
問題領域次元決定手段１−１は、物理空間の問題領域の次元数を決定する。次の領域分割方法候補選択手段１−２では、問題領域の次元数とプロセッサ台数から問題領域の分割方法の候補をあげる。分割方法決定手段１−３では、候補の中から分割方法を一つ選び、問題領域を分割する。分割領域割り当て手段１−４では、分割した領域をプロセッサに割り当てる。
【００１９】
図２に各手段の処理内容を示す。問題領域を割り当てるべきプロセッサ台数Ｎが素数ｘ（≧２）のｎ乗で表せるとき（２−１）、問題領域次元決定手段１−１は、物理空間の問題領域の次元数ｍを入力とする（２−２）。決定にあたっては次元数ｍがｎを超えないようにする（２−３）。もし、次元数ｍがｎを超えた場合は、条件を満たすまで再入力を繰り返す。
【００２０】
次に、領域分割方法候補選択手段１−２で、問題領域の各次元の格子点数を
ｎ1，ｎ2，ｎ3，……，ｎm、としたとき、
【００２１】
【数４】
logxＮ≧logx（ｎ1×ｎ2×ｎ3×……×ｎm）                    …（式１）
ｎ1，ｎ2，ｎ3，……，ｎm＝ｘ（≧２）の冪乗
を満たすｎ1，ｎ2，ｎ3，……，ｎmの組合せを求める（２−４）。
【００２２】
分割方法決定手段１−３では、領域分割方法候補選択手段１−２で求めた組合せの中から最も適当と思われるものを選択し（２−５）、問題の分割方法とする。そして、分割方法に従い問題領域を分割する（２−６）。
【００２３】
最後に、分割領域割り当て手段１−４で、１次元表示した分割領域番号と同じ物理番号を有するプロセッサに分割領域を割り当てる（２−７）。
【００２４】
図３に問題領域を３次元に分割し、分割領域を２9 個のプロセッサに割り当てる例を示す。
【００２５】
３次元に分割する場合、ｍ＝３とする（３−２）。プロセッサ台数Ｎが２9 であるため、領域の次元数ｍをｍ＝１〜９まで９通り選択可能である（３−３）。分割方法候補を決めるために(ｎ1，ｎ2，ｎ3）の組合せを求める（３−４）。組合せは、（２7，２1，２1)（２6，２1，２2)（２3，２3，２3)（２2，２3，２4)……のようになる。上述の例で、問題領域を立方体として扱う場合は（８，８，８）の組合せを選択し（３−５）、２3×２3×２3にと分割する(３−６）。最後に、分割領域（Ｎｕｍ＝Ｘ＋８×（Ｙ−１）＋６４×（Ｚ−１）：１≦Ｘ≦８，１≦Ｙ≦８，１≦Ｚ≦８）をプロセッサ（Ｎｕｍ）に割り当てる（３−７）。
【００２６】
以上、四つの手段を用いることで、問題領域の次元構成が並列計算機の次元構成と異なる場合でも経路の競合を発生することなく隣接転送を行っている時と同等の通信性能を得られる。また、分割した領域を単純に同じ番号を持つプロセッサに割り当てればよいため、ユーザが問題領域と並列計算機の次元構成が異なることを意識する必要がない。この実施例では、これらの手段をライブラリとして提供しているが、ユーザ自身がプログラミングするときにこの手順に従い問題領域を分割し、プロセッサに分割領域を割りつけてもよい。
【００２７】
次に、本発明の２次元クロスバネットワークへの具体的な適用例を示す。問題領域を３次元に分割して、２次元クロスバネットワークを有する６４（８×８）プロセッサからなる並列計算機に分割領域を割り当てることを考える。
【００２８】
図４は本実施例で用いる並列計算機の構成を示したものである。図４で４−１〜４−６４はプロセッサ（以下ＰＥと略する）である。４−６５〜４−７２までは、Ｘ方向のクロスバスイッチ（以下Ｘ−ＸＢと略する）、４−７３〜４−８０は、Ｙ方向のクロスバスイッチ（以下Ｙ−ＸＢと略する）である。これらのクロスバスイッチを区別しない場合には、単にＸＢと呼ぶことがある。４−８１〜４−１４４は各Ｘ−ＸＢと各Ｙ−ＸＢの交点に設けられた中継スイッチ（以下ＥＸと略する）である。各ＸＢおよびＥＸは、各入力ポートが全出力ポートに直接結合する完全クロスバスイッチである。ＸＢとＥＸとの組合せをまとめて２次元クロスバネットワークと呼ぶ。
【００２９】
各ＰＥは、２次元座標空間の一つの格子点のＸ座標，Ｙ座標と、その座標から求められる物理番号をあらかじめそのＰＥ番号として与えられている。例えば、この例では、各ＰＥは［Ｘ，Ｙ］，Ｘ＋８×（Ｙ−１）という値を番号として持っている。ルーティング方法は固定ルーティングを用いており、まず、データをＸ方向に転送し、次にＹ方向に転送する。
【００３０】
まず、図１の問題領域次元決定手段１−１により、問題領域の次元数を決定する。本実施例では、ＰＥ数６４は２6 とも表せるため、問題領域の次元数は６次元以下であればいずれでもよい。ここでは問題領域の次元数を３次元にし、それを入力とする。
【００３１】
次に、図１の領域分割方法候補選択手段１−２により条件を満たす分割方法の候補を選び、分割方法決定手段１−３により分割方法を決定する。問題領域の各次元の格子点数をｎ1，ｎ2，ｎ3（２の冪乗）としたとき、logx２6≧logx(ｎ1×ｎ2×ｎ3）を満たす問題領域分割方法は分割領域数がプロセッサ台数と等しい場合でも計１０種類あり、Ｘ次元×Ｙ次元×Ｚ次元をそれぞれ１６×２×２，２×１６×２，２×２×１６，８×４×２，８×２×４，４×８×２，４×２×８，２×８×４，２×４×８，４×４×４のように分割する。どの分割方法を選択するかは自由であるので、ここでは、複数の候補の中から問題領域を１６×２×２に分割する方法を選択する。
【００３２】
図５は問題領域を分割した様子を示す。この問題は、３次元であるので、Ｘ座標，Ｙ座標，Ｚ座標の三つをＸ＋１６×（Ｙ−１）＋３２×（Ｚ−１）に代入して１次元表示し、各分割領域に図５の５−１に示すように１次元の番号を付ける。
【００３３】
最後に、図１の分割領域割り当て手段１−４により図４の同じ番号を持つプロセッサに図５の問題領域を割り当てる。例えば、問題領域［１］はＰＥ［１］に問題領域［１６］はＰＥ［１６］に割り当てる。
【００３４】
上述の分割割り当て方式による近接作用問題のデータ転送の様子を図６，図７および図８に示す。ユーザは、並列計算機の次元構成が問題領域の次元構成と同じであるとイメージしたままで、データ転送を行う。問題領域が３次元構成であるため、通信は計６方向で発生する。
【００３５】
図６は、１６×２×２に分割した問題領域における３方向のデータ転送パターンを示している。６−１は、＋Ｘ方向の近接作用であり、６−２は＋Ｙ方向の近接作用、６−３は＋Ｚ方向の近接作用を示す。端は反対側の端を隣としている。
【００３６】
図７および図８は、この問題領域を、本発明の手段を用いてプロセッサに割り当てた場合のデータ転送の様子を示している。図７は、＋Ｘ方向の近接作用の場合のデータ転送の様子、図８は、＋Ｙ方向の近接作用の場合のデータ転送の様子である。この二つの図を見てもわかるように、上述の分割・割り当て方式を用いたことで、２次元クロスバスイッチにおける隣接転送以外に使用する転送経路を用いて効率良くデータを転送することが可能になる。
【００３７】
ここでは、問題領域を１６×２×２に分割して、プロセッサに割り当てる例について説明したが、領域分割方法候補選択手段１−２から求まる候補であれば、隣接転送以外に使用する転送経路を用いて効率良く高速にデータを転送することが可能である。
【００３８】
また、ここでは、３次元の問題領域を２次元クロスバネットワークに割り当てる例を示したが、同様な方法でｍ次元の問題領域をＮ次元クロスバネットワークに割り当てても、高速なデータ転送が可能である。
【００３９】
以上の説明では、２次元クロスバネットワークを用いたが、これらに代えて図１０に示すような多数の中継スイッチで構成されるハイパキューブネットワーク（１０−１）や多段結合ネットワーク（１０−２），完全クロスバ結合ネットワークに対しても適用できる。
【００４０】
【発明の効果】
本発明によれば問題領域の次元構成が並列計算機の次元構成と異なる場合でも、次元構成を同一にした場合と同等の通信性能を得られる。
【図面の簡単な説明】
【図１】本発明の問題領域分割・割り当て方式のブロック図。
【図２】本発明の問題領域分割・割り当て方式の処理のフローチャート。
【図３】本発明の具体的なフローチャート。
【図４】本発明を適用する２次元クロスバネットワークのブロック図。
【図５】本発明の領域分割の説明図。
【図６】本発明のデータ転送パターンの説明図。
【図７】本発明の２次元クロスバネットワークにおけるデータのブロック図。
【図８】本発明の２次元クロスバネットワークにおけるデータのブロック図。
【図９】従来の問題領域分割・割り当て方式を示す説明図。
【図１０】本発明を適用可能なネットワークの説明図。
【符号の説明】
１−１…問題領域次元決定手段、１−２…領域分割方法候補選択手段、１−３…分割方法決定手段、１−４…分割領域割り当て手段。
【図１】
0003653841.tif 000002
【図２】
0003653841.tif 000003
【図３】
0003653841.tif 000004
【図４】
0003653841.tif 000005
【図５】
0003653841.tif 000006
【図６】
0003653841.tif 000007
【図７】
0003653841.tif 000008
【図８】
0003653841.tif 000009
【図９】
0003653841.tif 000010
【図１０】
0003653841.tif 000011