ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：ａｌｌ−ｔｏ−ａｌｌｃｏｍｍｕｎｉｃａｔｉｏｎ）を含む、複数の計算処理をスケジューリングする方法、プログラム及び並列計算機システム。
【課題】ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、最適にスケジューリングすること。
【解決手段】ネットワークを構成している複数のノード（プロセッサ）を、第１の部分グループに含まれる複数のノード間のみについての全対全通信に要する通信（計算処理）フェーズ（Ａ２Ａ−Ｌ）と、第２の部分グループに含まれる複数のノード間のみについての全対全通信に要する通信（計算処理）フェーズ（Ａ２Ａ−Ｐとに分け、複数のスレッド（スレッド１、スレッド２、スレッド３、スレッド４）にわたって、それぞれのフェーズをオーバーラップさせて並列処理する。ＦＦＴ（Fast Fourier Transform）（高速フーリエ変換）やＴ（transpose）（（内部：internal）転置）という複数の計算処理についてもあわせて、並列処理することができる。
【解決手段】ネットワークを構成している複数のノード（プロセッサ）を、第１の部分グループに含まれる複数のノード間のみについての全対全通信に要する通信（計算処理）フェーズ（Ａ２Ａ−Ｌ）と、第２の部分グループに含まれる複数のノード間のみについての全対全通信に要する通信（計算処理）フェーズ（Ａ２Ａ−Ｐとに分け、複数のスレッド（スレッド１、スレッド２、スレッド３、スレッド４）にわたって、それぞれのフェーズをオーバーラップさせて並列処理する。ＦＦＴ（Fast Fourier Transform）（高速フーリエ変換）やＴ（transpose）（（内部：internal）転置）という複数の計算処理についてもあわせて、並列処理することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、最適にスケジューリングすることに関する。
【背景技術】
【０００２】
トーラスまたはメッシュなどのネットワークで接続された並列計算機においては、複数のノード（プロセッサ）間の通信の性能が計算処理の速度に大きく影響する。代表的な通信のパターンとして、全てのノードが他の全てのノードにノードごとに異なるデータを送信する全対全通信（all-to-all communication、略して「Ａ２Ａ」）が知られており、最も多くの通信転送量を必要とする。全対全通信は、行列または配列（マトリックス）の転置（transpose、略して「Ｔ」）や高速フーリエ変換（Fast FourierTransform、略して「ＦＦＴ」）などの多くの計算において、頻繁に利用される通信の形態であることが知られている。
【０００３】
特許文献１は、ＦＦＴの計算において、配列を転置することや、１次元（１Ｄ）ＦＦＴの計算において２次元（２Ｄ）ＦＦＴとして処理することが、一般的技術水準であることを示している。第１次元を複数のプロセッサにまたがって処理し、第２次元を複数のプロセッサにまたがって処理する。
【０００４】
特許文献２は、ｎ次元トーラスにおける全対全通信内部の処理において、フェーズを重ね合わせて効率化を図る工夫について記載している。ここで、特許文献２と本発明との対比説明をしておく。本発明は、全対全通信を複数の部分的な全対全通信に変換し全対全通信単位でパイプライン化するもので、全対全通信内部の実装方式を含まず、発明の適用対象が異なる。また、スケジュールの対象が異なり、本発明のような全対全通信以外の処理と全対全通信内の処理の重ね合わせは、特許文献2には含まれない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３６７５５３７号
【特許文献２】特許第２６０１５９１号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、さらに効率化することが望まれる。
【課題を解決するための手段】
【０００７】
ネットワークを構成している複数のノード（プロセッサ）を、第１の部分グループに含まれる複数のノード間のみについての全対全通信に要する計算処理フェーズ（Ａ２Ａ−Ｌ）と、第２の部分グループに含まれる複数のノード間のみについての全対全通信に要する計算処理フェーズ（Ａ２Ａ−Ｐとに分け、Nt個の複数のスレッド（スレッド１、スレッド２、スレッド３、スレッド４、．．．スレッドNt）にわたって、それぞれのフェーズをオーバーラップさせて並列処理する。
【発明の効果】
【０００８】
ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、最適にスケジューリングすることができ、計算性能を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機において計算処理することを説明する模式図である。
【図２】ノード（プロセッサ）の構成を示す模式図である。
【図３】ネットワークの次元と最長の軸を説明するための模式図として4次元トーラスネットワークを図示したものである。
【図４】トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【図５】本発明を適用して、複数のノード（プロセッサ）間において 全対全通信（Ａ２Ａ：all-to-allcommunication）を含む複数の計算処理をスケジューリングする方法を示す図である。
【図６】本発明を適用した場合の効果として、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【発明を実施するための形態】
【００１０】
図１は、１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機において計算処理することを説明する模式図である。
【００１１】
図１の（Ａ）は、１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機で計算処理するために、２次元（２Ｄ）ＦＦＴ（Ｎ１，Ｎ２）（Ｎ＝Ｎ１×Ｎ２）という形に変形して、Ｎ１とＮ２の長さの2つのＦＦＴに分けて並列処理することを示す。言い換えると、Ｎ１とＮ２との２次元（２Ｄ）として、並列処理の方向を変えて処理することを示す。ここで、ｎｐは、プロセッサ（ノード）の数（number of processor）である。
【００１２】
図１の（Ｂ）は、並列化１次元（１Ｄ）ＦＦＴアルゴリズムを示す。並列化された１次元（１Ｄ）ＦＦＴにおける計算処理においては、入力から出力を得る過程において３回の転置（transpose「Ｔ」）が必要となることが知られている。このことは、例えば特許文献１においても、一般的技術水準として示されている。
【００１３】
図１の（Ｃ）は、転置（transpose「Ｔ」）が、行と列とが入れ替るような処理であることを示す。ｉを行番号としｊを列番号とした場合に、ｉｊに相当する模様の箇所が、ｊｉに相当する模様の箇所へと置き換わることが図示されている。第１段階としては、全体全通信（Ａ２Ａ：all-to-all communication）を用いて模様の箇所を単位としてブロック化されて処理されているため、第２段階として、そのブロックの内部においても内部転置（internal transpose 「ＩＴ」）をする必要がある。
【００１４】
図２は、ノード（プロセッサ）の構成を示す模式図である。図２の（Ａ）では、１つのノードを、立方体（cubic）のイメージとして表現している。このような表現に従うと、空間的に隣接する他のノード（プロセッサ）との間において、立方体の６つの面から通信する６本の双方向通信路（１２本の片方向通信路でもよい）をイメージし易く、３次元ネットワークの構成がイメージし易い。
【００１５】
図２の（Ｂ）では、ノード（プロセッサ）の内部構成を示す。並列計算機の特徴として、スレッドが複数存在しており、マルチスレッドと呼ばれるものがある。類似するものとして、マルチコア、マルチプロセッサ、など、様々な表現で呼ばれるものがあって、それらが必ずしも一義的に区別されて用いられてはいない。もっとも、本発明の適用は、ノード（プロセッサ）内において、並列に処理（パイプライン化）でき、処理すべき内容をオーバーラップさせることができるということにあるため、本発明を適用することができる対象としては、これらをあえて区別する意義はない。
【００１６】
１つのノード（プロセッサ）内におけるスレッドの数については、様々な製品が存在していることが知られている。ここでは、４つのスレッドとして、スレッド１、スレッド２、スレッド３、スレッド４が示される。スレッドは、典型的にはハードウエアであるが、ハードウエアを共有するように工夫されたソフトウエアとして、または、ハードウエアとソフトウエアとの組合せとして具現化することができる。
【００１７】
さらに、ノード（プロセッサ）内にはメモリがあって、現時点において、どの通信処理がスレッドを専有している状態にあるのかについての情報、次にはどの通信処理をスレッドに実行させるかについての情報（例えば、テーブルのようなもの）等を記憶している。メモリは、典型的にはハードウエアとして具現化されるが、ソフトウエアとの組合せにおいて仮想的な領域を形成することもできる。
【００１８】
また、ノード（プロセッサ）内にはコントローラがあって、通信路を通じて送受信されるメッセージのアクセス許可の制御を行なっている。コントローラは、ハードウエアとして、ソフトウエアとして、または、ハードウエアとソフトウエアとの組合せとして、具現化することができる。
【００１９】
本発明のスケジューリング方法は、単数のノード（プロセッサ）毎に自律的に動作することも可能であるし、部分グループを構成する隣接する複数のノード（プロセッサ）との間で協働して動作することも可能である。スケジューリング方法は、各ノード（プロセッサ）が動作できるような複数のコードを有するプログラム（またはプログラム製品）として提供することもできる。また、複数のノード（プロセッサ）のグループとして、本発明のスケジューリングを可能とする、並列計算機システムとして提供することもできる。
【００２０】
図３は、ネットワークの次元と最長の軸を説明するための模式図として4次元トーラスネットワークを図示したものである。既に説明したように、３次元ネットワークであれば、図２の立方体（cubic）の６面を通じて通信する６本の双方向通信路として、直感的にもイメージし易いであろう。
【００２１】
ここでは、隣接する８つの立方体が１つの部分グループ（サブグループ）を形成していて、その部分グループが横に３つ並んでいる。１つの部分グループあたりの軸の数は、ｘ軸、ｙ軸、ｚ軸という馴染みのある座標系に沿って、Ｌ個、Ｍ個、Ｎ個、というようにノード（プロセッサ）の数を数えて、ｘ軸に２、ｙ軸に２、ｚ軸に２、と数える。ここでは、全ての軸の長さが等しく２×２×２と表現され、これら３軸は同じ長さの軸である。
【００２２】
さらに、４次元ネットワークを説明する。ここでは、横に３つ並んだ部分グループ間を結ぶ双方向通信路として、１つのノード（プロセッサ）からさらに２本の双方向通信路が追加されて（３次元空間でも見える態様で）示されており、１つのノード（プロセッサ）については、８本の双方向通信路をイメージすることができる。新たに追加された双方向通信路に沿う軸をｔ軸としてノード（プロセッサ）の数を数えると３になり２×２×２×３と表現されるため、この例における最長の軸は、この４次元目にあたる軸である３ということになる。本発明において、「最長の軸」は重要な意義を有する。さらに、ｎ次元ネットワークについては、当業者であれば、本発明を容易に拡張して適用することが可能であろう。
【００２３】
図４は、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【００２４】
まず、点線内において、３次元ネットワークの立方体（cubic）イメージとして、２×２×２（＝８）の立方体（cubic）トーラスと、２×２×４（＝１６）の非立方体（non-cubic）トーラスとを図示している。ノード（プロセッサ）の数の制限があると、例えば、３×３×３（＝２７）の立方体（cubic）に構成できるとは限らないので、非立方体（non-cubic）の構成を利用する状況は多い。
【００２５】
２×１×１の構成における、メッシュとトーラスとの区別は、点線内に図示したように立体の各軸の両端のノード（プロセッサ）を結ぶ双方向通信路が存在しているかどうかの差である。グループを形成している状態では表現上煩雑になるため、これら双方向通信路は図示しないこととする。
【００２６】
性能比較のために、並列化１次元（１Ｄ）ＦＦＴの性能を、８×８×８（＝５１２）のトーラスと、８×８×１６（＝１０２４）の非立方体（non-cubic）トーラスとで比較している。「次元による形状」というのが、この図では「３次元に依る形状」なのであって、立方体（cubic）であったり、非立方体（non-cubic）であったりする。
【００２７】
Blue Gene /P(Blue Gene およびBlue Gene /Pは、IBM Corporation の商標)においてその性能を測定した。ＧＦＬＯＰＳは、ギガフロップスの単位である。本来であれば５１２→１０２４と利用できるノード（プロセッサ）の数が２倍になっているのであるから、性能も２倍になることが期待されるが、ピーク性能は維持されたままになってしまっている。
【００２８】
また、全体の通信におけるall-to-all 通信が占める割合は５４％から７０％へと増大してしまっており、最長の軸の長さが１６と、８の２倍になるため、 all-to-all 通信のバンド幅は半分以下になってしまっている。
【００２９】
図５は、本発明を適用して、複数のノード（プロセッサ）間において 全対全通信（Ａ２Ａ：all-to-allcommunication）を含む複数の計算処理をスケジューリングする方法を示す図である。図１の（Ｂ）の並列化１Ｄ（１次元）ＦＦＴアルゴリズムに従って、図示のように、フェーズ１と、フェーズ２とに分けて処理を行なう。その際、図２の（Ｂ）のノード（プロセッサ）の内部構成に従って、４つのスレッドがあることを想定して、複数のスレッドを用いたパイプライン処理をスケジューリングする。
【００３０】
３次元ネットワークを複数のノード（プロセッサ）４×４×８（＝１２８）で構成している非立方体（non-cubic）トーラスについて、最長の軸は８であるが、軸状内にある８つの複数のノード（プロセッサ）が最長の軸を含む第１の部分グループとして選択される。この第１の部分グループに含まれる８つの複数のノード（プロセッサ）間のみについての全対全通信を処理するための通信フェーズを、Ａ２Ａ−Ｌ（Ｌは、Longest の頭文字をとったもの）と呼ぶことにする。
【００３１】
３次元ネットワークを複数のノード（プロセッサ）４×４×８（＝１２８）で構成している非立方体（non-cubic）トーラスについて、最長の軸以外の全ての軸（４×４）を含む第２の部分グループ内のノード（プロセッサ）は平面（すなわち、軸の数である２として２次元であることに依る形状）になるが、この第２の部分グループに含まれる１６（４×４）の複数のノード（プロセッサ）間のみについての全対全通信を処理するための通信フェーズを、Ａ２Ａ−Ｐ（Ｐは、Plane の頭文字をとったもの）と呼ぶことにする。
【００３２】
最長となる軸が１つでない場合は最長となる軸の数を次元数とすることに依る形状の第１の部分グループになるが、ここでは図示しない。同様に、複数の最長となる軸がある場合、第２の部分グループの形状は平面や多次元の立体ではなく、軸あるいは空集合（０次元）となることもあるが、ここでは図示しない。
【００３３】
ここで、第１の部分グループに含まれるノード（プロセッサ）と、第２の部分グループに含まれるノード（プロセッサ）との両方に共通して含まれるノード（プロセッサ）があることに注意されたい。この場合には１つのノード（プロセッサ）のみであるが、ここを通じて、第１の部分グループの計算処理の結果と、第２の部分グループの計算処理の結果とが、つながりを持つことになる。
【００３４】
次に、フェーズ１とフェーズ２とのパイプライン処理のスケジューリングであるが、スレッド１、スレッド２、スレッド３、スレッド４にわけて、複数の計算処理を並列に処理（パイプライン化）できるように（オーバーラップさせ）していることが見てとれる。
【００３５】
また、１つのスレッドのみが１度にＡ２Ａ−Ｌを実行できるようにスケジューリングされていることが特徴的である。点線で示すように、Ａ２Ａ−Ｌの処理の完了を待って次の処理へ進むようにスケジューリングされている。典型的には、点線で示す部分に継ぎ目無く、シーケンシャルに（またはシームレスに）実行されるようにスケジューリングされる。
【００３６】
Ａ２Ａ−ＬとＡ２Ａ−Ｐとがオーバーラップされていることも特徴的であり、このことによってＡ２Ａ−Ｌに要してしまう時間をうまく有効利用することができる。例えば、ＦＦＴの計算処理や、Ｔ（転置、ここでは内部転置（internal transpose））の計算処理をはめ込んで有効利用することができる。
【００３７】
図６は、本発明を適用した場合の効果として、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。表の一部は、図４におけるものと共通している。
【００３８】
本発明を用いた場合には、本発明を用いない場合に比べて、処理速度が上がっていることがわかる。特に、ノード（プロセッサ）の軸が、非立方体（non-cubic）トーラスとして構成された場合において、特にその優位さが目立っている。
【技術分野】
【０００１】
本発明は、ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、最適にスケジューリングすることに関する。
【背景技術】
【０００２】
トーラスまたはメッシュなどのネットワークで接続された並列計算機においては、複数のノード（プロセッサ）間の通信の性能が計算処理の速度に大きく影響する。代表的な通信のパターンとして、全てのノードが他の全てのノードにノードごとに異なるデータを送信する全対全通信（all-to-all communication、略して「Ａ２Ａ」）が知られており、最も多くの通信転送量を必要とする。全対全通信は、行列または配列（マトリックス）の転置（transpose、略して「Ｔ」）や高速フーリエ変換（Fast FourierTransform、略して「ＦＦＴ」）などの多くの計算において、頻繁に利用される通信の形態であることが知られている。
【０００３】
特許文献１は、ＦＦＴの計算において、配列を転置することや、１次元（１Ｄ）ＦＦＴの計算において２次元（２Ｄ）ＦＦＴとして処理することが、一般的技術水準であることを示している。第１次元を複数のプロセッサにまたがって処理し、第２次元を複数のプロセッサにまたがって処理する。
【０００４】
特許文献２は、ｎ次元トーラスにおける全対全通信内部の処理において、フェーズを重ね合わせて効率化を図る工夫について記載している。ここで、特許文献２と本発明との対比説明をしておく。本発明は、全対全通信を複数の部分的な全対全通信に変換し全対全通信単位でパイプライン化するもので、全対全通信内部の実装方式を含まず、発明の適用対象が異なる。また、スケジュールの対象が異なり、本発明のような全対全通信以外の処理と全対全通信内の処理の重ね合わせは、特許文献2には含まれない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第３６７５５３７号
【特許文献２】特許第２６０１５９１号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、さらに効率化することが望まれる。
【課題を解決するための手段】
【０００７】
ネットワークを構成している複数のノード（プロセッサ）を、第１の部分グループに含まれる複数のノード間のみについての全対全通信に要する計算処理フェーズ（Ａ２Ａ−Ｌ）と、第２の部分グループに含まれる複数のノード間のみについての全対全通信に要する計算処理フェーズ（Ａ２Ａ−Ｐとに分け、Nt個の複数のスレッド（スレッド１、スレッド２、スレッド３、スレッド４、．．．スレッドNt）にわたって、それぞれのフェーズをオーバーラップさせて並列処理する。
【発明の効果】
【０００８】
ｎ次元の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信（Ａ２Ａ：all-to-all communication）を含む複数の計算処理を、最適にスケジューリングすることができ、計算性能を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機において計算処理することを説明する模式図である。
【図２】ノード（プロセッサ）の構成を示す模式図である。
【図３】ネットワークの次元と最長の軸を説明するための模式図として4次元トーラスネットワークを図示したものである。
【図４】トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【図５】本発明を適用して、複数のノード（プロセッサ）間において 全対全通信（Ａ２Ａ：all-to-allcommunication）を含む複数の計算処理をスケジューリングする方法を示す図である。
【図６】本発明を適用した場合の効果として、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【発明を実施するための形態】
【００１０】
図１は、１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機において計算処理することを説明する模式図である。
【００１１】
図１の（Ａ）は、１次元（１Ｄ）ＦＦＴ（長さＮ）を並列計算機で計算処理するために、２次元（２Ｄ）ＦＦＴ（Ｎ１，Ｎ２）（Ｎ＝Ｎ１×Ｎ２）という形に変形して、Ｎ１とＮ２の長さの2つのＦＦＴに分けて並列処理することを示す。言い換えると、Ｎ１とＮ２との２次元（２Ｄ）として、並列処理の方向を変えて処理することを示す。ここで、ｎｐは、プロセッサ（ノード）の数（number of processor）である。
【００１２】
図１の（Ｂ）は、並列化１次元（１Ｄ）ＦＦＴアルゴリズムを示す。並列化された１次元（１Ｄ）ＦＦＴにおける計算処理においては、入力から出力を得る過程において３回の転置（transpose「Ｔ」）が必要となることが知られている。このことは、例えば特許文献１においても、一般的技術水準として示されている。
【００１３】
図１の（Ｃ）は、転置（transpose「Ｔ」）が、行と列とが入れ替るような処理であることを示す。ｉを行番号としｊを列番号とした場合に、ｉｊに相当する模様の箇所が、ｊｉに相当する模様の箇所へと置き換わることが図示されている。第１段階としては、全体全通信（Ａ２Ａ：all-to-all communication）を用いて模様の箇所を単位としてブロック化されて処理されているため、第２段階として、そのブロックの内部においても内部転置（internal transpose 「ＩＴ」）をする必要がある。
【００１４】
図２は、ノード（プロセッサ）の構成を示す模式図である。図２の（Ａ）では、１つのノードを、立方体（cubic）のイメージとして表現している。このような表現に従うと、空間的に隣接する他のノード（プロセッサ）との間において、立方体の６つの面から通信する６本の双方向通信路（１２本の片方向通信路でもよい）をイメージし易く、３次元ネットワークの構成がイメージし易い。
【００１５】
図２の（Ｂ）では、ノード（プロセッサ）の内部構成を示す。並列計算機の特徴として、スレッドが複数存在しており、マルチスレッドと呼ばれるものがある。類似するものとして、マルチコア、マルチプロセッサ、など、様々な表現で呼ばれるものがあって、それらが必ずしも一義的に区別されて用いられてはいない。もっとも、本発明の適用は、ノード（プロセッサ）内において、並列に処理（パイプライン化）でき、処理すべき内容をオーバーラップさせることができるということにあるため、本発明を適用することができる対象としては、これらをあえて区別する意義はない。
【００１６】
１つのノード（プロセッサ）内におけるスレッドの数については、様々な製品が存在していることが知られている。ここでは、４つのスレッドとして、スレッド１、スレッド２、スレッド３、スレッド４が示される。スレッドは、典型的にはハードウエアであるが、ハードウエアを共有するように工夫されたソフトウエアとして、または、ハードウエアとソフトウエアとの組合せとして具現化することができる。
【００１７】
さらに、ノード（プロセッサ）内にはメモリがあって、現時点において、どの通信処理がスレッドを専有している状態にあるのかについての情報、次にはどの通信処理をスレッドに実行させるかについての情報（例えば、テーブルのようなもの）等を記憶している。メモリは、典型的にはハードウエアとして具現化されるが、ソフトウエアとの組合せにおいて仮想的な領域を形成することもできる。
【００１８】
また、ノード（プロセッサ）内にはコントローラがあって、通信路を通じて送受信されるメッセージのアクセス許可の制御を行なっている。コントローラは、ハードウエアとして、ソフトウエアとして、または、ハードウエアとソフトウエアとの組合せとして、具現化することができる。
【００１９】
本発明のスケジューリング方法は、単数のノード（プロセッサ）毎に自律的に動作することも可能であるし、部分グループを構成する隣接する複数のノード（プロセッサ）との間で協働して動作することも可能である。スケジューリング方法は、各ノード（プロセッサ）が動作できるような複数のコードを有するプログラム（またはプログラム製品）として提供することもできる。また、複数のノード（プロセッサ）のグループとして、本発明のスケジューリングを可能とする、並列計算機システムとして提供することもできる。
【００２０】
図３は、ネットワークの次元と最長の軸を説明するための模式図として4次元トーラスネットワークを図示したものである。既に説明したように、３次元ネットワークであれば、図２の立方体（cubic）の６面を通じて通信する６本の双方向通信路として、直感的にもイメージし易いであろう。
【００２１】
ここでは、隣接する８つの立方体が１つの部分グループ（サブグループ）を形成していて、その部分グループが横に３つ並んでいる。１つの部分グループあたりの軸の数は、ｘ軸、ｙ軸、ｚ軸という馴染みのある座標系に沿って、Ｌ個、Ｍ個、Ｎ個、というようにノード（プロセッサ）の数を数えて、ｘ軸に２、ｙ軸に２、ｚ軸に２、と数える。ここでは、全ての軸の長さが等しく２×２×２と表現され、これら３軸は同じ長さの軸である。
【００２２】
さらに、４次元ネットワークを説明する。ここでは、横に３つ並んだ部分グループ間を結ぶ双方向通信路として、１つのノード（プロセッサ）からさらに２本の双方向通信路が追加されて（３次元空間でも見える態様で）示されており、１つのノード（プロセッサ）については、８本の双方向通信路をイメージすることができる。新たに追加された双方向通信路に沿う軸をｔ軸としてノード（プロセッサ）の数を数えると３になり２×２×２×３と表現されるため、この例における最長の軸は、この４次元目にあたる軸である３ということになる。本発明において、「最長の軸」は重要な意義を有する。さらに、ｎ次元ネットワークについては、当業者であれば、本発明を容易に拡張して適用することが可能であろう。
【００２３】
図４は、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。
【００２４】
まず、点線内において、３次元ネットワークの立方体（cubic）イメージとして、２×２×２（＝８）の立方体（cubic）トーラスと、２×２×４（＝１６）の非立方体（non-cubic）トーラスとを図示している。ノード（プロセッサ）の数の制限があると、例えば、３×３×３（＝２７）の立方体（cubic）に構成できるとは限らないので、非立方体（non-cubic）の構成を利用する状況は多い。
【００２５】
２×１×１の構成における、メッシュとトーラスとの区別は、点線内に図示したように立体の各軸の両端のノード（プロセッサ）を結ぶ双方向通信路が存在しているかどうかの差である。グループを形成している状態では表現上煩雑になるため、これら双方向通信路は図示しないこととする。
【００２６】
性能比較のために、並列化１次元（１Ｄ）ＦＦＴの性能を、８×８×８（＝５１２）のトーラスと、８×８×１６（＝１０２４）の非立方体（non-cubic）トーラスとで比較している。「次元による形状」というのが、この図では「３次元に依る形状」なのであって、立方体（cubic）であったり、非立方体（non-cubic）であったりする。
【００２７】
Blue Gene /P(Blue Gene およびBlue Gene /Pは、IBM Corporation の商標)においてその性能を測定した。ＧＦＬＯＰＳは、ギガフロップスの単位である。本来であれば５１２→１０２４と利用できるノード（プロセッサ）の数が２倍になっているのであるから、性能も２倍になることが期待されるが、ピーク性能は維持されたままになってしまっている。
【００２８】
また、全体の通信におけるall-to-all 通信が占める割合は５４％から７０％へと増大してしまっており、最長の軸の長さが１６と、８の２倍になるため、 all-to-all 通信のバンド幅は半分以下になってしまっている。
【００２９】
図５は、本発明を適用して、複数のノード（プロセッサ）間において 全対全通信（Ａ２Ａ：all-to-allcommunication）を含む複数の計算処理をスケジューリングする方法を示す図である。図１の（Ｂ）の並列化１Ｄ（１次元）ＦＦＴアルゴリズムに従って、図示のように、フェーズ１と、フェーズ２とに分けて処理を行なう。その際、図２の（Ｂ）のノード（プロセッサ）の内部構成に従って、４つのスレッドがあることを想定して、複数のスレッドを用いたパイプライン処理をスケジューリングする。
【００３０】
３次元ネットワークを複数のノード（プロセッサ）４×４×８（＝１２８）で構成している非立方体（non-cubic）トーラスについて、最長の軸は８であるが、軸状内にある８つの複数のノード（プロセッサ）が最長の軸を含む第１の部分グループとして選択される。この第１の部分グループに含まれる８つの複数のノード（プロセッサ）間のみについての全対全通信を処理するための通信フェーズを、Ａ２Ａ−Ｌ（Ｌは、Longest の頭文字をとったもの）と呼ぶことにする。
【００３１】
３次元ネットワークを複数のノード（プロセッサ）４×４×８（＝１２８）で構成している非立方体（non-cubic）トーラスについて、最長の軸以外の全ての軸（４×４）を含む第２の部分グループ内のノード（プロセッサ）は平面（すなわち、軸の数である２として２次元であることに依る形状）になるが、この第２の部分グループに含まれる１６（４×４）の複数のノード（プロセッサ）間のみについての全対全通信を処理するための通信フェーズを、Ａ２Ａ−Ｐ（Ｐは、Plane の頭文字をとったもの）と呼ぶことにする。
【００３２】
最長となる軸が１つでない場合は最長となる軸の数を次元数とすることに依る形状の第１の部分グループになるが、ここでは図示しない。同様に、複数の最長となる軸がある場合、第２の部分グループの形状は平面や多次元の立体ではなく、軸あるいは空集合（０次元）となることもあるが、ここでは図示しない。
【００３３】
ここで、第１の部分グループに含まれるノード（プロセッサ）と、第２の部分グループに含まれるノード（プロセッサ）との両方に共通して含まれるノード（プロセッサ）があることに注意されたい。この場合には１つのノード（プロセッサ）のみであるが、ここを通じて、第１の部分グループの計算処理の結果と、第２の部分グループの計算処理の結果とが、つながりを持つことになる。
【００３４】
次に、フェーズ１とフェーズ２とのパイプライン処理のスケジューリングであるが、スレッド１、スレッド２、スレッド３、スレッド４にわけて、複数の計算処理を並列に処理（パイプライン化）できるように（オーバーラップさせ）していることが見てとれる。
【００３５】
また、１つのスレッドのみが１度にＡ２Ａ−Ｌを実行できるようにスケジューリングされていることが特徴的である。点線で示すように、Ａ２Ａ−Ｌの処理の完了を待って次の処理へ進むようにスケジューリングされている。典型的には、点線で示す部分に継ぎ目無く、シーケンシャルに（またはシームレスに）実行されるようにスケジューリングされる。
【００３６】
Ａ２Ａ−ＬとＡ２Ａ−Ｐとがオーバーラップされていることも特徴的であり、このことによってＡ２Ａ−Ｌに要してしまう時間をうまく有効利用することができる。例えば、ＦＦＴの計算処理や、Ｔ（転置、ここでは内部転置（internal transpose））の計算処理をはめ込んで有効利用することができる。
【００３７】
図６は、本発明を適用した場合の効果として、トーラスを構成するノード（プロセッサ）の軸の数の構成によって、並列化１次元（１Ｄ）ＦＦＴの性能がどのように違うかを示す図である。表の一部は、図４におけるものと共通している。
【００３８】
本発明を用いた場合には、本発明を用いない場合に比べて、処理速度が上がっていることがわかる。特に、ノード（プロセッサ）の軸が、非立方体（non-cubic）トーラスとして構成された場合において、特にその優位さが目立っている。
【特許請求の範囲】
【請求項１】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理をスケジューリングする方法であって、
最長の軸を含むグループ（最長の軸が1つであれば軸状、それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択するステップと、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供するステップと、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択するステップと、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供するステップと、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングするステップとを有する、
前記方法。
【請求項２】
全ての軸の長さが等しい場合は、全てのノードを含むグループを第一のグループとして選択し、第１の部分グループにおける全対全通信が、シーケンシャルに実行されるようにスケジューリングするステップとを有する、
請求項１に記載の方法。
【請求項３】
さらに、第１の通信フェーズ（Ａ２Ａ−Ｌ）と、ＦＦＴの計算処理または行列転置の計算処理とが並列に処理（パイプライン化）できるように（オーバーラップさせ）、スケジューリングするステップとを有する、
請求項１に記載の方法。
【請求項４】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、単数または複数のノード（プロセッサ）に対して、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理をスケジューリングして実行させるプログラムであって、
最長の軸を含むグループ（最長の軸が1つであれば軸状,それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択することを実行させるコードと、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供することを実行させるコードと、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択することを実行させるコードと、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供することを実行させるコードと、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングすることを実行させるコードとを有する
前記プログラム。
【請求項５】
全ての軸の長さが等しい場合は、全てのノードを含むグループを第一のグループとして選択し、第１の部分グループにおける全対全通信が、シーケンシャルに実行されるようにスケジューリングすることを実行させるコードを有する、
請求項４に記載のプログラム。
【請求項６】
さらに、第１の通信フェーズ（Ａ２Ａ−Ｌ）と、ＦＦＴの計算処理または行列転置の計算処理とが並列に処理（パイプライン化）できるように（オーバーラップさせ）、スケジューリングすることを実行させるコードを有する、
請求項４に記載のプログラム。
【請求項７】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理を並列に処理する並列計算機システムであって、
最長の軸を含むグループ（最長の軸が1つであれば軸状,それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択し、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供し、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択し、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供し、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングして並列に処理する、
前記並列計算機システム。
【請求項１】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理をスケジューリングする方法であって、
最長の軸を含むグループ（最長の軸が1つであれば軸状、それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択するステップと、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供するステップと、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択するステップと、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供するステップと、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングするステップとを有する、
前記方法。
【請求項２】
全ての軸の長さが等しい場合は、全てのノードを含むグループを第一のグループとして選択し、第１の部分グループにおける全対全通信が、シーケンシャルに実行されるようにスケジューリングするステップとを有する、
請求項１に記載の方法。
【請求項３】
さらに、第１の通信フェーズ（Ａ２Ａ−Ｌ）と、ＦＦＴの計算処理または行列転置の計算処理とが並列に処理（パイプライン化）できるように（オーバーラップさせ）、スケジューリングするステップとを有する、
請求項１に記載の方法。
【請求項４】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、単数または複数のノード（プロセッサ）に対して、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理をスケジューリングして実行させるプログラムであって、
最長の軸を含むグループ（最長の軸が1つであれば軸状,それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択することを実行させるコードと、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供することを実行させるコードと、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択することを実行させるコードと、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供することを実行させるコードと、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングすることを実行させるコードとを有する
前記プログラム。
【請求項５】
全ての軸の長さが等しい場合は、全てのノードを含むグループを第一のグループとして選択し、第１の部分グループにおける全対全通信が、シーケンシャルに実行されるようにスケジューリングすることを実行させるコードを有する、
請求項４に記載のプログラム。
【請求項６】
さらに、第１の通信フェーズ（Ａ２Ａ−Ｌ）と、ＦＦＴの計算処理または行列転置の計算処理とが並列に処理（パイプライン化）できるように（オーバーラップさせ）、スケジューリングすることを実行させるコードを有する、
請求項４に記載のプログラム。
【請求項７】
ｎ（ｎ＞２）次元の軸上にその次元に依る形状の（トーラスまたはメッシュ）ネットワークを構成している複数のノード（プロセッサ）間において、全対全通信(Ａ２Ａ：all-to-all communication)を含む、複数の計算処理を並列に処理する並列計算機システムであって、
最長の軸を含むグループ（最長の軸が1つであれば軸状,それ以外の場合は最長の軸の数を次元数とすることに依る形状）内の複数のノードを、第１の部分グループとして選択し、
この第１の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第１の通信フェーズ（Ａ２Ａ−Ｌ）を提供し、
最長の軸以外の残りの全ての軸を含むグループ内の複数のノードを、第２の部分グループとして選択し、
この第２の部分グループに含まれる複数のノード間のみについての全対全通信を処理するための、第２の通信フェーズ（Ａ２Ａ−Ｐ）を提供し、
第１の通信フェーズ（Ａ２Ａ−Ｌ）と第２の通信フェーズ（Ａ２Ａ−Ｐ） とがノード内で並列に処理（パイプライン化）できるように（オーバーラップさせ）、かつ、第１の部分グループにおける全ての全対全通信が完了するのを待って次の処理に進むことができるように、複数の計算処理をスケジューリングして並列に処理する、
前記並列計算機システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１３−３７７２３（Ｐ２０１３−３７７２３Ａ）
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願番号】特願２０１２−２３０７３０（Ｐ２０１２−２３０７３０）
【出願日】平成２４年１０月１８日（２０１２．１０．１８）
【分割の表示】特願２０１１−５４０５７６（Ｐ２０１１−５４０５７６）の分割
【原出願日】平成２２年１１月１５日（２０１０．１１．１５）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２５年２月２１日（２０１３．２．２１）
【国際特許分類】
【出願日】平成２４年１０月１８日（２０１２．１０．１８）
【分割の表示】特願２０１１−５４０５７６（Ｐ２０１１−５４０５７６）の分割
【原出願日】平成２２年１１月１５日（２０１０．１１．１５）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]