(57)【特許請求の範囲】
【請求項１】
複数の演算装置が並列に演算を行う並列演算装置において、
各演算装置は、
集合通信の開始から前記集合通信に関する受信までの時間が所定の閾値以下であるか否かを判定する判定部と、
前記判定部により前記時間が所定の閾値以下であると判定された場合に、前記集合通信に関する待ち方式を変更する対象演算装置を決定する決定部と、
前記決定部により決定された対象演算装置に前記集合通信に関する待ち方式の変更指示を送信する送信部と
を有することを特徴とする並列演算装置。
【請求項２】
前記送信部は、前記集合通信に関する待ち方式について割込み方式からポーリング方式への変更指示を送信することを特徴とする請求項１に記載の並列演算装置。
【請求項３】
前記送信部は、ＲＤＭＡを用いて前記変更指示を送信することを特徴とする請求項１又は２に記載の並列演算装置。
【請求項４】
前記決定部は、前記集合通信のアルゴリズムに基づいて前記対象演算装置を決定することを特徴とする請求項１、２又は３に記載の並列演算装置。
【請求項５】
並列に演算を行う複数の演算装置と前記複数の演算装置が接続されたスイッチとを有する並列演算システムにおいて、
各演算装置は、
集合通信の開始から前記集合通信に関する受信までの時間が所定の閾値以下であるか否かを判定する判定部と、
前記判定部により前記時間が所定の閾値以下であると判定された場合に、前記集合通信に関する待ち方式を変更する対象演算装置を決定する決定部と、
前記決定部により決定された対象演算装置に前記集合通信に関する待ち方式の変更指示を送信する送信部と
を有することを特徴とする並列演算システム。
【請求項６】
他の演算装置と並列に演算を行う演算装置による集合通信方法において、
集合通信の開始から前記集合通信に関する受信までの時間が所定の閾値以下であるか否かを判定し、
前記時間が所定の閾値以下であると判定した場合に、前記集合通信に関する待ち方式を変更する対象演算装置を決定し、
決定した対象演算装置に前記集合通信に関する待ち方式の変更指示を送信する
処理を実行することを特徴とする集合通信方法。
【請求項７】
他の演算装置と並列に演算を行う演算装置で実行される集合通信プログラムにおいて、
集合通信の開始から前記集合通信に関する受信までの時間が所定の閾値以下であるか否かを判定し、
前記時間が所定の閾値以下であると判定した場合に、前記集合通信に関する待ち方式を変更する対象演算装置を決定し、
決定した対象演算装置に前記集合通信に関する待ち方式の変更指示を送信する
処理を前記演算装置に実行させることを特徴とする集合通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列演算装置、並列演算システム、集合通信方法及び集合通信プログラムに関する。
【背景技術】
【０００２】
並列計算機システムでは、プロセス間の通信にＭＰＩ（Message  Passing  Interface）が利用される。ＭＰＩを利用した通信には、２つのプロセス間で行われる１対１通信、２つ以上の複数のプロセスが同じ通信に同時に関与する集合通信等がある。
【０００３】
集合通信の例としてBarrier命令がある。Barrier命令はプロセス間の同期に用いられる命令であり、Barrier命令に参加する全プロセスがBarrier命令に到達するまで待つ。図１３は、Barrier命令を説明するための図である。図１３は、通信アルゴリズムにDisseminationアルゴリズムが用いられる場合を示す。
【０００４】
図１３に示すように、プロセスの数が４の場合、Barrier命令は２ステップで実施される。ステップ＃１では、各プロセスは、（（自身のランク番号＋２＾０）％プロセス数）のプロセスにBarrier命令への到達を通知する到達通知を送信する。ここで、「ランク番号」は、プロセスを識別する識別番号であり、４プロセスの場合は、０〜３である。「＾」はべき乗演算を表し、「ｘ％ｙ」はｘをｙで割った余りを表す。ステップ＃２では、各プロセスは、（（自身のランク番号＋２＾１）％プロセス数）のプロセスに到達通知を送信する。
【０００５】
例えば、プロセス＃０は、ステップ＃１でプロセス＃３より到達通知を受信し、プロセス＃３がBarrier命令に到達していることがわかる。そして、プロセス＃０は、ステップ＃２でプロセス＃２より到達通知を受信し、プロセス＃２もBarrier命令に到達していることがわかる。ここで、プロセス＃２はステップ＃１でプロセス＃１から到達通知を受信しているので、プロセス＃０は、プロセス＃１もBarrier命令に到達していることがわかる。他のプロセスも同様にBarrier命令への到達を認識することができる。したがって、全プロセスがBarrier命令に到達し、Barrier命令は２つのステップで完了する。
【０００６】
なお、マルチプロセッサコアシステムにおけるネットワークＩ／Ｏ要求の処理において、静的構成切替え規則に基づいて割込みモードとポーリングモードとの間でプロセッサコアを切り替えて、処理効率を改善する技術がある。
【０００７】
また、画像処理を行うプロセッサによる処理時間が算出可能な処理は画像処理を制御するＣＰＵからプロセッサへのポーリング処理により制御を行い、それ以外はプロセッサからＣＰＵへの割込みにより制御を行うことで、ＣＰＵにかかる負荷を軽減する技術がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特表２０１４−５３１０８１号公報
【特許文献２】特開２００６−２６８０９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
図１３に示したBarrier命令のように、集合通信では、理想的には全プロセスが同じタイミングで完了することが望ましいが、実際にはノイズ（割込みやデーモンプロセス等の処理）により、特定のプロセスにおいて集合通信の開始が遅れることがある。図１４は、集合通信における特定のプロセスの遅れを説明するための図である。図１４において、０〜３は、ランク番号が０〜３であるプロセスを表す。
【００１０】
図１４（ａ）に示すように、ノイズなしのケースでは、プロセス＃０〜プロセス＃３が同時に集合通信を開始し、同時に集合通信を完了する。一方、図１４（ｂ）に示すように、ノイズありのケースでは、プロセス＃０〜プロセス＃３が異なる時刻に集合通信を開始し、異なる時刻に集合通信を完了する。図１４（ｂ）では、プロセス＃２の集合通信の完了が遅れる。このように、集合通信には、一部のプロセスの通信完了が遅れるという問題がある。一部のプロセスで集合通信の完了が遅れると、集合通信を利用するアプリケーションの性能が低下する。
【００１１】
本発明は、１つの側面では、集合通信における一部のプロセスの遅延を抑えることを目的とする。
【課題を解決するための手段】
【００１２】
本願の開示する並列演算装置は、１つの態様において、判定部と決定部と送信部とを有する。前記判定部は、集合通信の開始から前記集合通信に関する受信までの時間が所定の閾値以下であるか否かを判定する。前記決定部は、前記判定部により前記時間が所定の閾値以下であると判定された場合に、前記集合通信に関する待ち方式を変更する対象演算装置を決定する。前記送信部は、前記決定部により決定された対象演算装置に前記集合通信に関する待ち方式の変更指示を送信する。
【発明の効果】
【００１３】
１実施態様によれば、集合通信における一部のプロセスの遅延を抑えることができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施例に係るプロセスによる通信完了待ち方式の変更を説明するための図である。
【図２】図２は、実施例に係るＰＣクラスタシステムの構成を示す図である。
【図３】図３は、実施例に係るプロセスの機能構成を示す図である。
【図４】図４は、８プロセスの場合の変更対象を説明するための図である。
【図５】図５は、ＲＤＭＡを説明するための図である。
【図６】図６は、平均値算出処理のフローを示すフローチャートである。
【図７】図７は、変更制御処理のフローを示すフローチャートである。
【図８】図８は、対象決定処理のフローを示すフローチャートである。
【図９】図９は、通信完了待ち処理のフローを示すフローチャートである。
【図１０】図１０は、Binomial  Treeアルゴリズムを説明するための図である。
【図１１】図１１は、Bruck'sアルゴリズムを説明するための図である。
【図１２】図１２は、Recursive  Doublingアルゴリズムを説明するための図である。
【図１３】図１３は、Barrier命令を説明するための図である。
【図１４】図１４は、集合通信における特定のプロセスの遅れを説明するための図である。
【発明を実施するための形態】
【００１５】
以下に、本願の開示する並列演算装置、並列演算システム、集合通信方法及び集合通信プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例】
【００１６】
まず、実施例に係るプロセスによる通信完了待ち方式の変更について説明する。なお、実施例における通信アルゴリズムは、Disseminationアルゴリズムである。図１は、実施例に係るプロセスによる通信完了待ち方式の変更を説明するための図である。図１において、０〜３は、ランク番号が０〜３であるプロセスを表す。また、ｔ０＿１〜ｔ３＿１は、プロセス＃０〜プロセス＃３がそれぞれ集合通信を開始する時刻であり、ｔ０＿２〜ｔ３＿２は、プロセス＃０〜プロセス＃３がそれぞれ集合通信の到達通知を受信した時刻である。
【００１７】
図１に示すように、集合通信開始から到達通知を受信するまでの時間ｔｉ＿２−ｔｉ＿１（０≦ｉ≦３）が短いプロセスは、他のプロセスと比較して、処理が遅れている。図１では、プロセス＃３が集合通信開始から到達通知を受信するまでの時間ｔ３＿２−ｔ３＿１が他のプロセスと比較して短い。
【００１８】
ステップ＃１においてプロセス＃３が到達通知を送信するプロセスは、（３＋２＾０）％４＝０であるので、プロセス＃０であり、ステップ＃２においてプロセス＃０が到達通知を送信するプロセスは、（０＋２＾１）％４＝２であるので、プロセス＃２である。したがって、プロセス＃２の集合通信完了が遅くなる。
【００１９】
そこで、プロセス＃３は、集合通信開始から到達通知を受信するまでの時間ｔ３＿２−ｔ３＿１が所定の閾値以下である場合に、プロセス＃２の集合通信完了を早くするために、プロセス＃２の通信完了待ち方式を割込み方式からポーリング方式に変更する。ここで、所定の閾値は、集合通信開始から到達通知を受信するまでの時間の平均値に基づく値であり、例えば、平均値の１／３である。
【００２０】
割込み方式は、通信装置が通信を完了するとＣＰＵへの割込みを発生して通信の完了を通知する方式であり、ＯＳに制御が渡るため処理遅延が発生するが消費電力は少ない。一方、ポーリング方式は、定期的に通信完了を調査する方式であり、割込み方式と比較して低遅延であるが、ＣＰＵリソースを消費するため消費電力は高い。通常は、消費電力を少なくするため、割込み方式が用いられる。
【００２１】
したがって、通信完了待ち方式を割込み方式からポーリング方式に変更することによって、プロセスは通信完了を早めることができる。図１では、プロセス＃２の通信完了時刻が、点線の矢頭で示される時刻から実線の矢頭で示される時刻へ早まる。
【００２２】
このように、実施例に係るプロセスは、集合通信の完了が遅れると思われるプロセスの集合通信の完了待ち方式を割込み方式からポーリング方式に変更することによって、集合通信における一部のプロセスの遅延を抑えることができる。
【００２３】
次に、実施例に係るＰＣクラスタシステムの構成について説明する。ここで、ＰＣクラスタシステムとは、複数のＰＣサーバで構成される並列計算機システムである。図２は、実施例に係るＰＣクラスタシステムの構成を示す図である。図２に示すように、ＰＣクラスタシステム１０は、複数のＰＣサーバ１と、複数のＰＣサーバ１を接続するスイッチ２とを有する。ＰＣサーバ１間の通信はインフィニバンドが用いられる。
【００２４】
なお、ここでは、１台のスイッチ２のみを示したが、ＰＣクラスタシステム１０は、複数のスイッチ２で複数のＰＣサーバ１を接続してもよい。また、ＰＣサーバ１間の通信方式は、インフィニバンド以外の通信方式でもよい。
【００２５】
ＰＣサーバ１は、ＨＣＡ（Host  Channel  Adapter）１１と、ＣＰＵ１２と、メモリ１３と、ＬＡＮ（Local  Area  Network）インタフェース１４と、ＨＤＤ（Hard  Disk  Drive）１５と、ＯＤＤ（Optical  Disk  Drive）１６とを有する。
【００２６】
ＨＣＡ１１は、他のＨＣＡ１１又はスイッチ２に接続するための装置である。ＣＰＵ１２は、メモリ１３からプログラムを読み出して実行する中央処理装置である。ＣＰＵ１２では、並列プログラムの複数のプロセスのうち１つのプロセスが実行される。メモリ１３は、プログラムやプログラムの実行途中結果などを記憶するＲＡＭ（Random  Access  Memory）である。
【００２７】
ＬＡＮインタフェース１４は、ＰＣサーバ１をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。ＨＤＤ１５は、プログラムやデータを格納するディスク装置であり、ＯＤＤ１６は、ＤＶＤの読み書きを行う装置である。
【００２８】
ＰＣサーバ１において実行されるプログラムは、ＤＶＤに記憶され、ＯＤＤ１６によってＤＶＤから読み出されてＰＣサーバ１にインストールされる。あるいは、ＰＣサーバ１において実行されるプログラムは、ＬＡＮインタフェース１４を介して接続された他のコンピュータシステムのデータベースなどに記憶され、これらのデータベースから読み出されてＰＣサーバ１にインストールされる。そして、インストールされたプログラムは、ＨＤＤ１５に記憶され、メモリ１３に読み出されてＣＰＵ１２によって実行される。
【００２９】
次に、実施例に係るプロセスの機能構成について説明する。図３は、実施例に係るプロセスの機能構成を示す図である。図３に示すように、プロセス３は、平均算出部３１と、変更制御部３２と、完了待部３３とを有する。
【００３０】
平均算出部３１は、集合通信開始から到達通知を受信するまでの時間の平均値を算出する。並列プログラムが実行される場合には、集合通信が複数回行われる。平均算出部３１は、最初に集合通信が行われたときに集合通信開始から到達通知を受信するまでの時間の平均値を算出し、メモリ１３に格納する。
【００３１】
変更制御部３２は、集合通信開始から到達通知を受信するまでの時間を計測する。そして、変更制御部３２は、集合通信開始から到達通知を受信するまでの時間が所定の閾値以下である場合に、集合通信の完了が遅れると思われるプロセスの集合通信の完了待ち方式を割込み方式からポーリング方式に変更する。
【００３２】
変更制御部３２は、判定部３２ａと、対象決定部３２ｂと、指示送信部３２ｃとを有する。判定部３２ａは、集合通信開始から到達通知を受信するまでの時間を計測し、計測した時間が所定の閾値以下であるか否かを判定する。ここで、所定の閾値は、平均算出部３１により算出された平均値の１／３である。なお、所定の閾値は、平均値に基づく値であえば、平均値の１／３以外の値でもよい。あるいは、所定の閾値は、平均値以外に中央値など他の値に基づく値でもよい。
【００３３】
対象決定部３２ｂは、計測した時間が所定の閾値以下であると判定部３２ａにより判定された場合に、通信完了待ち方式をポーリング方式に変更する変更対象のプロセスを特定する。図１では、プロセス数が４であり、プロセス＃２だけが変更対象のプロセスであったが、プロセス数が多い場合には、対象決定部３２ｂは、変更対象として複数のプロセスを特定する。
【００３４】
図４は、８プロセスの場合の変更対象を説明するための図である。図４において、０〜７は、ランク番号が０〜７であるプロセスを表す。また、プロセス数が８の場合は、集合通信は、ｌｏｇ(８)＝３ステップで集合通信が完了する。ｌｏｇの底は２である。
【００３５】
図４では、プロセス＃４の通信完了が遅れる。プロセス＃４が遅れるのは、ステップ＃３において、プロセス＃０の送信が遅れるためであり、プロセス＃０が遅れるのは、ステップ＃２において、プロセス＃６の送信が遅れるためである。また、プロセス＃６が遅れるのは、ステップ＃１において、プロセス＃５の送信が遅れるためである。
【００３６】
そこで、プロセス＃５は、例えば、ステップ＃１において、ステップ＃２のプロセス＃０とステップ＃３のプロセス＃４を変更対象として特定する。あるいは、プロセス＃５は、ステップ＃１において、ステップ＃３のプロセス＃４だけを変更対象として特定してもよい。
【００３７】
一般的に、プロセス数をｎとし、ステップ数をｌｏｇ(ｎ)とすると、対象決定部３２ｂは、ｘ（２≦ｘ≦ｌｏｇ(ｎ)）ステップ以降のステップで遅れるプロセスを変更対象として特定する。ｘは、アプリケーション、ＣＰＵ１２の消費電力等により決められる数である。ｘ≦ｉ≦ｌｏｇ(ｎ)とすると、対象決定部３２ｂは、ｉステップで遅れるプロセスを、（（自身のランク番号＋２＾（ｉ−１））％ｎ）で特定する。
【００３８】
指示送信部３２ｃは、対象決定部３２ｂが特定したプロセスに、通信完了待ち方式をポーリング方式に変更する指示を送信する。指示送信部３２ｃは、ＲＤＭＡ（Remote  Direct  Memory  Access）により変更指示を送信する。図５は、ＲＤＭＡを説明するための図である。
【００３９】
図５に示すように、ＣＰＵ１２は、ＭＣ（Memory  Controller）１２ａとコア１２ｂとを有する。ＭＣ１２ａは、コア１２ｂがメモリ１３にアクセスするための制御装置である。コア１２ｂは、演算処理を行う処理装置である。
【００４０】
コア１２ｂで実行されるプロセス３は、自身が動作するＰＣサーバ１のＨＣＡ１１、スイッチ２、変更先ＰＣサーバ１のＨＣＡ１１、及び、変更先ＰＣサーバ１のＭＣ１２ａを経由して、変更先ＰＣサーバ１のメモリ１３の領域１３ａにアクセスする。ここで、変更先ＰＣサーバ１とは、変更対象のプロセス３が動作するＰＣサーバ１である。
【００４１】
完了待部３３は、集合通信の完了待ちの処理を行う。具体的には、完了待部３３は、方式変更フラグが設定されている場合には、集合通信の完了待ちをポーリング方式に変更し、方式変更フラグが設定されていない場合には、集合通信の完了待ちを割込み方式により行う。なお、方式変更フラグは、図５に示した領域１３ａに設定される。
【００４２】
次に、平均値算出処理のフローについて説明する。図６は、平均値算出処理のフローを示すフローチャートである。図６に示すように、平均値算出部３１は、集合通信開始から最初に到達通知を受信するまでの時間を計測する（ステップＳ１）。平均値算出部３１は、計測した時間のプロセス間の平均値を算出し（ステップＳ２）、算出した平均値をメモリ１３に格納する。
【００４３】
このように、平均値算出部３１が、集合通信開始から最初に到達通知を受信するまでの時間を計測し、計測した時間のプロセス間の平均値を算出することで、判定部３２ａは、判定に用いる所定の閾値を算出することができる。
【００４４】
次に、集合通信の完了待ち方式の変更を制御する変更制御処理のフローについて説明する。図７は、変更制御処理のフローを示すフローチャートである。図７に示すように、変更制御部３２は、集合通信開始から到達通知を受信するまでの時間を計測する（ステップＳ１１）。
【００４５】
そして、変更制御部３２は、計測した時間は、所定の閾値以下であるか否かを判定し（ステップＳ１２）、所定の閾値以下でない場合には、処理を終了する。一方、所定の閾値以下である場合には、変更制御部３２は、変更対象を決定する対象決定処理を行う（ステップＳ１３）。
【００４６】
そして、変更制御部３２は、変更対象リストより対象のプロセスの番号を順に取り出し、取り出した番号のプロセスにＲＤＭＡにより集合通信の完了待ち方式の変更を指示する（ステップＳ１４）。ここで、変更対象リストは、変更対象のプロセスの番号のリストである。
【００４７】
このように、変更制御部３２が、集合通信開始から到達通知を受信するまでの時間に基づいて集合通信の完了待ち方式の変更を制御することで、集合通信における一部のプロセスの遅延を抑えることができる。
【００４８】
次に、対象決定処理のフローについて説明する。図８は、対象決定処理のフローを示すフローチャートである。図８に示すように、対象決定部３２ｂは、集合通信に参加しているプロセスの数ｎを取得し（ステップＳ２１）、ｉの値をｘとする（ステップＳ２２）。ここで、ｉは、繰り返し数を記憶する変数であり、ｘは、集合通信のステップのうち遅れるプロセスを変更対象として特定する最初のステップを示す。
【００４９】
そして、対象決定部３２ｂは、ｉがｌｏｇ(ｎ)以下であるか否かを判定し（ステップＳ２３）、ｉがｌｏｇ(ｎ)以下でない場合には、処理を終了する。一方、ｉがｌｏｇ(ｎ)以下である場合には、対象決定部３２ｂは、ｉステップ目の到達通知の送信先すなわち（自身のランク番号＋２＾（ｉ−１））％ｎを計算する（ステップＳ２４）。そして、対象決定部３２ｂは、計算結果を変更対象リストに追加し（ステップＳ２５）、ｉに１を加え（ステップＳ２６）、ステップＳ２３へ戻る。
【００５０】
このように、対象決定部３２ｂが変更対象リストを作成することで、変更制御部３２は、集合通信の完了待ち方式を変更すべきプロセスへ指示を送信することができる。
【００５１】
次に、集合通信の完了を待つ処理である通信完了待ち処理のフローについて説明する。図９は、通信完了待ち処理のフローを示すフローチャートである。なお、プロセス３は、集合通信の到達通知を送信後にスリープする前に通信完了待ち処理を行う。
【００５２】
図９に示すように、完了待部３３は、方式変更フラグをチェックし（ステップＳ３１）、通信完了待ち方式に変更があるか否かを判定する（ステップＳ３２）。その結果、変更がない場合には、処理を終了し、通信完了待ち方式を変更することなく、割込み方式により通信の完了を待つ。一方、通信完了待ち方式に変更がある場合には、ポーリングにより通信完了を検知する（ステップＳ３３）。
【００５３】
このように、通信完了待ち方式に変更がある場合に、完了待部３３がポーリングにより通信完了を検知することによって、プロセス３は集合通信の遅れを抑制することができる。
【００５４】
上述してきたように、実施例では、判定部３２ａが、集合通信開始から到達通知を受信するまでの時間を計測し、計測した時間が所定の閾値以下であるか否かを判定する。そして、計測した時間が所定の閾値以下であると判定部３２ａにより判定された場合に、対象決定部３２ｂが、通信完了待ち方式をポーリング方式に変更する変更対象のプロセスを特定する。そして、対象決定部３２ｂが特定したプロセス３に、指示送信部３２ｃが、通信完了待ち方式をポーリング方式に変更する指示を送信する。したがって、集合通信の開始が遅れたプロセス３は、開始の遅れに影響を受ける一部のプロセス３の遅延を抑えることができる。
【００５５】
また、実施例では、ＲＤＭＡにより集合通信の完了待ち方式の変更を指示するので、異なるＰＣサーバ１のメモリ１３に方式変更フラグを設定することができる。ただし、ＲＤＭＡによる指示では、通信完了待ち方式の変更が間に合わない場合がある。
【００５６】
例えば、図１に示した例では、プロセス＃２が到達通知をプロセス＃０に送信する前に変更指示が行われるので、プロセス＃２はスリープする前に通信完了待ち方式の変更を行うことができる。しかしながら、プロセス＃２が到達通知をプロセス＃０に送信してスリープした後に変更指示が行われると、プロセス＃２はスリープしてしまうため、通信完了待ち方式の変更を行うことができない。
【００５７】
このようなタイミングに起因する問題を避けるには、プロセス３は、ＲＤＭＡにより集合通信の完了待ち方式の変更を指示する代わりに、割込みにより集合通信の完了待ち方式の変更を指示すればよい。割込みにより集合通信の完了待ち方式の変更を指示することによって、スリープしてしまったプロセス３も通信完了待ち方式をポーリング方式に変更することができる。
【００５８】
また、実施例では、通信アルゴリズムがDisseminationアルゴリズムである場合について説明したが、例えば、Binomial  Treeアルゴリズム、Bruck'sアルゴリズム、Recursive  Doublingアルゴリズム等、通信アルゴリズムは他のアルゴリズムでもよい。
【００５９】
図１０は、Binomial  Treeアルゴリズムを説明するための図である。Binomial  Treeアルゴリズムは、例えば、Broadcast通信命令で利用される。Broadcast通信命令は、あるプロセスが保持するデータをBroadcast通信命令に参加する他のすべてのプロセスに配布する命令である。Binomial  Treeアルゴリズムは、プロセス数がｎのとき、ｌｏｇ(ｎ)ステップで実施される。
【００６０】
例えば、Broadcast通信命令は、図１０に示すように、プロセス＃０〜＃７の８プロセスで、プロセス＃０のデータをプロセス＃１〜＃７に配布する際に利用される。８プロセスの場合、データはｌｏｇ(８)＝３ステップで実施される。
【００６１】
１ステップ目・・・プロセス＃０からプロセス＃１へ送信
２ステップ目・・・プロセス＃０からプロセス＃２へ送信、プロセス＃１からプロセス＃３へ送信
３ステップ目・・・プロセス＃０からプロセス＃４へ送信、プロセス＃１からプロセス＃５へ送信、プロセス＃２からプロセス＃６へ送信、プロセス＃３からプロセス＃７へ送信
【００６２】
Binomial  Treeアルゴリズムの場合、図８のステップＳ２４における送信先は、Disseminationアルゴリズムと同様に、（自身のランク番号＋２＾（ｉ−１））％ｎによって算出される。例えば、
プロセス＃０は、１ステップ目で、（０＋２＾（１−１））＝１すなわちプロセス＃１へ送信、
プロセス＃０は、２ステップ目で、（０＋２＾（２−１））＝２すなわちプロセス＃２へ送信、
プロセス＃０は、３ステップ目で、（０＋２＾（３−１））＝４すなわちプロセス＃４へ送信、
プロセス＃１は、２ステップ目で、（１＋２＾（２−１））＝３すなわちプロセス＃３へ送信、等である。
【００６３】
図１１は、Bruck'sアルゴリズムを説明するための図である。Bruck'sアルゴリズムは、例えば、MPI＿Alltoall、MPI＿Allgather等の命令で利用される。Bruck'sアルゴリズムは、プロセス数がｎのとき、ｌｏｇ(ｎ)ステップで実施される。例えば、図１１に示すように、８プロセスの場合、Bruck'sアルゴリズムは、ｌｏｇ(８)＝３ステップで実施される。
【００６４】
１ステップ目・・・プロセス＃０は＃７へ送信、プロセス＃１は＃０へ送信、プロセス２は＃１へ送信、プロセス＃３は＃２へ送信、プロセス＃４は＃３へ送信、プロセス＃５は＃４へ送信、プロセス＃６は＃５へ送信、プロセス＃７は＃６へ送信
２ステップ目・・・プロセス＃０は＃６へ送信、プロセス＃１は＃７へ送信、プロセス＃２は＃０へ送信、プロセス＃３は＃１へ送信、プロセス＃４は＃２へ送信、プロセス＃５は＃３へ送信、プロセス＃６は＃４へ送信、プロセス＃７は＃５へ送信
３ステップ目・・・プロセス＃０は＃４へ送信、プロセス＃１は＃５へ送信、プロセス＃２は＃６へ送信、プロセス＃３は＃７へ送信、プロセス＃４は＃０へ送信、プロセス＃５は＃１へ送信、プロセス＃６は＃２へ送信、プロセス＃７は＃３へ送信
【００６５】
Bruck'sアルゴリズムの場合、図８のステップＳ２４における送信先は、（自身のランク番号−２＾（ｉ−１））％ｎによって算出される。
【００６６】
図１２は、Recursive  Doublingアルゴリズムを説明するための図である。Recursive  Doublingアルゴリズムは、例えば、MPI＿Alltoall、MPI＿Allgather等の命令で利用される。Recursive  Doublingアルゴリズムは、プロセス数がｎのとき、ｌｏｇ(ｎ)ステップで実施される。例えば、図１２に示すように、８プロセスの場合、データはｌｏｇ(８)＝３ステップで実施される。
【００６７】
１ステップ目・・・プロセス＃０とプロセス＃１間で交換（プロセス＃０はプロセス＃１へ、プロセス＃１はプロセス＃０へ送信）、プロセス＃２とプロセス＃３間で交換、プロセス＃４とプロセス＃５間で交換、プロセス＃６とプロセス＃７間で交換
２ステップ目・・・プロセス＃０とプロセス＃２間で交換、プロセス＃１とプロセス＃３間で交換、プロセス＃４とプロセス＃６間で交換、プロセス＃５とプロセス＃７間で交換
３ステップ目・・・プロセス＃０とプロセス＃４間で交換、プロセス＃１とプロセス＃５間で交換、プロセス＃２とプロセス＃６間で交換、プロセス＃３とプロセス＃７間で交換
【００６８】
Recursive  Doublingアルゴリズムの場合、図８のステップＳ２４における送信先は、（自身のランク番号＋２＾（ｉ−１））％（２＾ｉ）＋（２＾ｉ）＊［自身のランク番号／（２＾ｉ）］によって算出される。ここで、「＊」は乗算を表し、［ｙ］はｙを超えない最大の整数である。
【００６９】
１ステップ目・・・プロセス＃ｐ(ｐは０〜７)は(ｐ+２＾（１−１）)％（２＾１）＋（２＾１）＊［ｐ／（２＾１）］
２ステップ目・・・プロセス＃ｐ(ｐは０〜７)は(ｐ+２＾（２−１）)％（２＾２）＋（２＾２）＊［ｐ／（２＾２）］
３ステップ目・・・プロセス＃ｐ(ｐは０〜７)は(ｐ+２＾（３−１）)％（２＾３）＋（２＾３）＊［ｐ／（２＾３）］
【００７０】
このように、通信アルゴリズムがDisseminationアルゴリズム以外である場合にも、本発明は同様に適用することができる。
【００７１】
また、実施例では、ＰＣクラスタシステムについて説明したが、本発明はこれに限定されるものではなく、他の並列計算機システムにも同様に適用することができる。また、実施例では、並列プログラムの１つのプロセスがＣＰＵ１２で実行される場合について説明したが、ＣＰＵが複数のコアを有し、１つのプロセスがコアで実行され、１つのＣＰＵで複数のプロセスが実行されてもよい。
【符号の説明】
【００７２】
１    ＰＣサーバ
２    スイッチ
３    プロセス
１０    ＰＣクラスタシステム
１１    ＨＣＡ
１２    ＣＰＵ
１２ａ    ＭＣ
１２ｂ    コア
１３    メモリ
１３ａ    領域
１４    ＬＡＮインタフェース
１５    ＨＤＤ
１６    ＯＤＤ
３１    平均算出部
３２    変更制御部
３２ａ    判定部
３２ｂ    対象決定部
３２ｃ    指示送信部
３３    完了待部
【図１】
0006468066.tif 000002
【図２】
0006468066.tif 000003
【図３】
0006468066.tif 000004
【図４】
0006468066.tif 000005
【図５】
0006468066.tif 000006
【図６】
0006468066.tif 000007
【図７】
0006468066.tif 000008
【図８】
0006468066.tif 000009
【図９】
0006468066.tif 000010
【図１０】
0006468066.tif 000011
【図１１】
0006468066.tif 000012
【図１２】
0006468066.tif 000013
【図１３】
0006468066.tif 000014
【図１４】
0006468066.tif 000015