説明

集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法

【課題】一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすること。
【解決手段】集団通信の最適化を実行するコントローラ121は、集団通信の内部処理として実行される1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集部121aと、経過時間情報収集部121aによって収集された情報に基づいて、前記の1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように1対1通信の通信順序を並び替える通信順序最適化部121bとを備える。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法に関し、特に、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法に関する。
【背景技術】
【0002】
近年、マルチプロセッサシステムの普及にともなって、複数のプロセッサ上で処理を並列実行する並列コンピューティングに対応したアプリケーションプログラムが多く開発されるようになっている。並列コンピューティングに対応したアプリケーションプログラムは、各プロセッサ上で動作するプロセスが他のプロセッサ上で動作するプロセスと情報をやりとりしながら処理を進めるように構成されている。
【0003】
プロセス間の情報のやりとりは、プロセス間通信によって実現される。並列コンピューティングにおけるプロセス間通信を実現するための仕組みの代表的なものにMPI(Message Passing Interface)がある。MPIは、様々なタイプのマルチプロセッサシステムに対応できるように設計されており、標準化されたAPI(Application Programming Interface)を有している。
【0004】
MPIによって定義されているプロセス間通信は、2種類に大別される。1つは、2つのプロセス間で情報をやりとりする1対1通信であり、もう1つは、複数のプロセス間で情報をやりとりする集団通信である。集団通信は、内部的には1対1通信を組み合わせて実行することによって実現されており、1対1通信に比べて、処理時間をより多く要する。このため、集団通信の処理時間を短縮することは、並列コンピューティングに対応したアプリケーションプログラムの性能を向上させるために非常に重要である。
【0005】
集団通信を高速化するための技術は、特許文献1や非特許文献1〜3において開示されている。特許文献1において開示されている技術は、集団通信の内部処理として実行される1対1通信の組合せを工夫することによって処理時間の短縮を図るものである。また、非特許文献1〜3において開示されている技術は、集団通信の内部処理として実行される1対1通信の順序を決定する木構造を最適化することによって処理時間の短縮を図るものである。
【0006】
【特許文献1】特開平11−110362号公報
【非特許文献1】Sathish S. Vadhiyar, Graham E. Fagg, Jack J. Dongarra. Automatically Tuned Collective Communications. [online]. Proceedings of the IEEE/ACM SC2000 Conference (SC'00). [retrieved on 2007-11-29]. Retrieved from the Internet: <URL: http://ieeexplore.ieee.org/iel5/10616/33525/01592716.pdf>.
【非特許文献2】Sathish S. Vadhiyar, Graham E. Fagg, Jack J. Dongarra. Performance Modeling for Self Adapting Collective Communications for MPI. [online]. [retrieved on 2007-11-29]. Retrieved from the Internet: <URL: http://icl.cs.utk.edu/news_pub/submissions/coll-lacsi-2001.pdf>.
【非特許文献3】Gupta, R.; Vadhiyar, S.; Application-oriented adaptive MPI_Bcast for grids. [online]. Parallel and Distributed Processing Symposium, 2006. IPDPS 2006. 20th International 25-29 April 2006 Page(s):10 pp. [retrieved on 2007-11-29]. Retrieved from the Internet: <URL: http://ieeexplore.ieee.org/iel5/10917/34366/01639363.pdf?tp=&arnumber=1639363&isnumber=34366>.
【発明の開示】
【発明が解決しようとする課題】
【0007】
しかしながら、上記の特許文献1において開示されている技術は、各プロセスがほぼ同時に集団通信を実行できる状態になることを前提としており、一部のプロセスの処理が遅延した場合に、集団通信の完了がその分だけ遅延してしまうという問題がある。また、上記の非特許文献1〜3には、このような遅延の影響を軽減するために、木構造を最適化して1対1通信の通信順序を入れ換える概念が示されているが、具体的に何を基準としてどのように通信順序を入れ換えるかは示されていない。
【0008】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法を提供することを目的とする。
【課題を解決するための手段】
【0009】
上述した課題を解決し、目的を達成するため、本願の開示する集団通信最適化装置は、一つの態様において、所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、前記経過時間情報収集手段によって収集された情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段とを備える。
【0010】
この態様によれば、集団通信を実行する各プロセスから集団通信の内部処理として実行される1対1通信の実行時の経過時間に関する情報を収集し、この情報に基づいて遅延が発生しているプロセスが1対1通信を実行するタイミングが遅くなるように通信順序を並び替えることとしたので、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる。
【0011】
なお、上記の集団通信最適化装置の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも上述した課題を解決するために有効である。
【発明の効果】
【0012】
本願の開示する集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法によれば、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができるという効果を奏する。
【発明を実施するための最良の形態】
【0013】
以下に添付図面を参照して、本発明に係る集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法の好適な実施の形態を詳細に説明する。なお、以下の実施例では、集団通信の仕組みとしてMPIを用いる場合を例にして説明するが、本発明は、MPI以外の仕組みを用いて集団通信を行う場合にも有効である。
【0014】
また、以下の実施例では、1つのプロセスから複数のプロセスへ同一のデータを送信するための集団通信であるブロードキャスト通信(MPIにおけるMPI_BCASTに相当)の場合を例にして本発明について説明するが、本発明は、1つのプロセスから複数のプロセスへそれぞれ異なるデータを送信するための集団通信であるスキャッタ通信(MPIにおけるMPI_SCATTERに相当)や、複数のプロセスに散在しているデータを1つのプロセスに集めるための通信であるギャザー通信(MPIにおけるMPI_GATHERに相当)のような他の種類の集団通信においても有効である。
【実施例】
【0015】
まず、本実施例に係る集団通信最適化方法の概要について説明する。本実施例に係る集団通信最適化方法では、予め決められた通信順序に従って1対1通信を複数回実行することによって集団通信が実現される。また、集団通信の実行時間を短縮させるため、通信順序に対応する木構造に基づいて、1対1通信が並列に実行される。
【0016】
図1は、本実施例に係る集団通信最適化方法における通信順序と木構造について説明するための説明図である。同図は、ルートプロセスであるプロセス#0からプロセス#1〜#7に対してブロードキャスト通信が行われる場合の例を示している。通信順序情報1aは、通信順序を保持する情報であり、1対1通信の対象となるべきタイミングが、プロセス#4、プロセス#2、プロセス#6、プロセス#1、プロセス#3、プロセス#5、プロセス#7の順に早いことを示している。
【0017】
木構造2は、通信順序情報1aに対応して生成されるbinominalツリー(2項木)であり、実際にどのような組合せの1対1通信をどのような順序で行うかを決定するために用いられる。木構造2は、1対1通信が下記のように行われることを示している。
【0018】
(フェーズ1)
プロセス#0からプロセス#4へデータが伝送される。
【0019】
(フェーズ2)
プロセス#0からプロセス#2へデータが伝送される。
また、プロセス#4からプロセス#6へデータが伝送される。
【0020】
(フェーズ3)
プロセス#0からプロセス#1へデータが伝送される。
また、プロセス#2からプロセス#3へデータが伝送される。
また、プロセス#4からプロセス#5へデータが伝送される。
また、プロセス#6からプロセス#7へデータが伝送される。
【0021】
このように、木構造2に基づいて1対1通信を実行していくことにより、プロセス#0が保持するデータが、ブロードキャスト通信によって、最短3フェーズでプロセス#1〜#7へ伝送される。しかしながら、一部のプロセスにおいて処理の遅延が発生していると、そのプロセスが1対1通信に対応するタイミングが遅くなり、ブロードキャスト通信が完了するまでに要する時間が長くなってしまう。この問題を解決するため、本実施例に係る集団通信最適化方法では、集団通信実行時における経過時間がプロセス毎に計測され、その計測結果に基づいて、通信順序の並べ替えが動的に行われる。
【0022】
この経過時間に基づく通信順序の並べ替えについて具体例を示して説明する。図2は、集団通信実行時における時間経過の一例を示す図である。同図において、「固有処理」は、集団通信に先立って行われるプロセス固有の処理を示している。そして、「送信処理」と「受信処理」は、集団通信の内部処理として実行される1対1通信における送信側の処理と受信側の処理を示しており、点線の矢印は、1対1通信における「送信処理」と「受信処理」の対応を示している。また、黒丸は、プロセスが「受信処理」に対応できるようになったタイミングを示し、黒丸から伸びている実線の矢印は、対応が可能になってから「受信処理」が開始されるまでの経過時間を示している。なお、この例における「受信処理」に対応できるようになったタイミングは、プロセスが、集団通信を実行するための手続(例えば、MPI_BCAST)を呼び出したタイミングと一致する。
【0023】
図2に示す例は、図1に示した通信順序情報1aに従ってブロードキャスト通信が行われる場合を示している。この例では、いずれのプロセスも「固有処理」において遅延が発生しておらず、全てのプロセスが、ほぼ同一のタイミング集団通信を実行可能な状態となっている。このため、各1対1通信が待ち時間を経ることなく実行され、最小限の時間で集団通信の実行が完了している。
【0024】
図3は、一部のプロセスに処理遅延が発生した場合の時間経過の一例を示す図である。同図に示す例では、プロセス#6の「固有処理」において遅延が発生している。このため、プロセス#4は、プロセス#0との1対1通信が完了した後、プロセス#6との1対1通信をすぐに実行することができず、待ち時間が生じてしまっている。そして、この待ち時間の分だけ集団通信が完了する時間が遅れてしまっている。
【0025】
このように一部のプロセスに処理遅延が発生すると、集団通信の内部処理において待ち時間が必要になり、集団通信の実行完了が遅れてしまう。一般に、処理遅延が一度発生したプロセスは、その後も処理遅延を繰り返し発生させる習慣性があることが知られており、そのプロセスが原因となって集団通信の実行完了が毎回遅れてしまうことになる。
【0026】
本実施例に係る集団通信最適化方法は、集団通信実行時における経過時間をプロセス毎に計測し、その計測結果に基づいて、処理遅延が発生しているプロセスが1対1通信を行うタイミングが遅くなるように通信順序の並び替えを行う。例えば、図3における実線の矢印の部分の長さ、すなわち、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間を各プロセスが測定し、その結果に基づいて通信順序の並び替えが行われる。
【0027】
図3の例では、プロセス#6が「固有処理」を実行している最中に、プロセス#4はプロセス#6に対して「送信処理」を実行することができる状態になっている。このため、プロセス#6が「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間は非常に短くなっている。このように、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間は、処理遅延が発生しているプロセスにおいて非常に短くなる。
【0028】
そこで、本実施例に係る集団通信最適化方法の一態様では、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間が最も短いプロセスと、この経過時間が最も長いプロセスの通信順序を入れ換えることによって、実行時間が最短化されるように集団通信の最適化が図られる。例えば、図3の例では、プロセス#6とプロセス#7の通信順序が入れ換えられる。
【0029】
図4は、通信順序の入れ換え後の集団通信の一例を示す図である。同図に示す通信順序情報1bのように、通信順序情報1aにおけるプロセス#6とプロセス#7の順序を入れ換えることにより、プロセス#6を対向プロセスとして1対1通信が開始されるタイミングが遅くなる。このため、同図の例のように、プロセス#6に図3の例と同様の遅延が発生しても、その遅延が1対1通信に影響を与えない可能性が高くなる。
【0030】
このように、本実施例に係る集団通信最適化方法は、各プロセスが集団通信の実行時に計測した経過時間に基づいて通信順序を最適化する。これによって、一部のプロセスに処理遅延が発生した場合であっても、集団通信の実行時間を最短に抑えることが可能になる。
【0031】
次に、本実施例に係る集団通信最適化方法を実行する情報処理システムについて説明する。図5は、本実施例に係る集団通信最適化方法を実行する情報処理システムの一例を示す図である。同図に示す情報処理システムは、情報処理装置10a〜10dを、高速で情報の伝送が可能な接続手段20によって相互接続して構成されている。なお、集団通信最適化方法を実行する情報処理システムの物理的な態様は、図5に示したものに限定されることはなく、複数のプロセスを並列的に実行可能な各種態様を含む。
【0032】
情報処理装置10a〜10dのそれぞれでは、集団通信を行うプロセス122が稼動している。また、情報処理装置10aでは、コントローラ121が稼動している。コントローラ121は、集団関数の実行時における経過時間に関する情報を各プロセス122から収集し、収集した情報に基づいて通信順序を最適化する機能部である。なお、コントローラ121は、情報処理装置10a〜10dのいずれにおいて稼動していてもよい。
【0033】
図6は、図5に示した情報処理装置10aの構成を示す機能ブロック図である。なお、コントローラ121が稼動していないことを除いて、情報処理装置10b〜10dは、情報処理装置10aと同様の構成を有する。同図に示すように、情報処理装置10aは、CPU(Central Processing Unit)11と、メモリ12と、ハードディスク装置13と、媒体読取装置14と、ネットワークインターフェース装置15とを、バス16で接続して構成されている。
【0034】
CPU11は、各種演算処理を実行することにより、様々な機能を実現することができる演算回路である。メモリ12は、CPU11によって実行される命令コード列や、データが一時的に記憶される記憶回路である。ハードディスク装置13は、各種データやプログラムを記憶する記憶装置である。媒体読取装置14は、CD−ROM等の各種記憶媒体から情報を読み取る装置である。ネットワークインターフェース装置15は、他の情報処理装置と情報をやりとりするためのインターフェース装置である。
【0035】
CPU11は、ハードディスク装置13に記憶されている集団通信最適化プログラム131を読み出してメモリ12に展開し、展開後の領域から命令コード列やデータを適宜読み出して演算処理することにより、コントローラ121の機能を実現する。同様に、CPU11は、ハードディスク装置13に記憶されているアプリケーションプログラム132を読み出してメモリ12に展開し、展開後の領域から命令コード列やデータを適宜読み出して演算処理することにより、プロセス122の機能を実現する。
【0036】
なお、集団通信最適化プログラム131およびアプリケーションプログラム132は、必ずしもハードディスク装置13に記憶されている必要はなく、媒体読取装置14によって読み取られる記憶媒体や、ネットワークインターフェース装置15を通じてアクセス可能な他の情報処理装置に記憶されていてもよい。
【0037】
コントローラ121は、通信順序の最適化を行う機能部であり、経過時間情報収集部121aと、通信順序最適化部121bと、通信順序情報配信部121cと、通信順序情報121dとを含む。なお、コントローラ121は、独立したプロセスとして実現されていてもよいし、情報処理装置10aの基本的な動作を管理するオペレーティングシステムの一部として実現されていてもよいし、プロセス122の一部として実現されていてもよい。
【0038】
経過時間情報収集部121aは、各プロセスが集団関数の実行時に計測した経過時間に関する情報を収集する処理部である。通信順序最適化部121bは、経過時間情報収集部121aによって収集された情報に基づいて、遅延の大きかったプロセスの通信順序が遅くなるように通信順序情報121dに格納されている通信順序を最適化する処理部である。具体的には、通信順序最適化部121bは、経過時間情報収集部121aによって収集された情報に基づいて最も遅延が大きいと判断されたプロセスと、最も遅延が小さいと判断されたプロセスの順序を入れ換えることによって通信順序を最適化する。
【0039】
一般に、集団通信は、ループ処理の一部として何度も繰り返して実行される。そのため、上記のように遅延が最も大きいと判断されたプロセスと遅延が最も小さいと判断されたプロセスの実行順序を入れ換えるだけであっても、集団通信が何度か実行されるうちに通信順序の最適化が適応的に進んでいき、集団通信に要する時間の短縮化が達成される。なお、遅延が大きい順に選択した所定数のプロセスの順序と、遅延が小さい順に選択した所定数のプロセスの順序とを通信順序情報121dにおいて入れ換えるように通信順序最適化部121bを構成してもよい。
【0040】
また、最適化の際にbinominalツリーの構造を利用して受信しかしてしないもの同士を入れ換えることを避けるように通信順序最適化部121bを構成してもよい。具体的には、ツリーの構造から送信を行わない(子を持たない)プロセス番号(図1におけるプロセス#1,3,5,7)を通信順序最適化部121bで保持しておき、保持しているプロセス番号については、通信順序が最も早かったとしても遅いものと入れ換えないようにする。
【0041】
さらに経過時間によるプロセスの実行順序の入れ替えと共に、最適化の際にbinominalツリーの構造を利用して、各ノードの送信回数によって重み付けして特定ノードを入れ替え易く(あるいは入れ換え難く)するように通信順序最適化部121bを構成してもよい。具体的には、通信順序最適化部121bに各プロセス番号が行う送信処理の回数を保持し、送信回数の多いプロセスの経過時間に重み付けをつけることにより、実行順序の入れ替えを行う。
【0042】
このように、一部のプロセスの順序のみを入れ換えることは、全てのプロセスの順序を入れ換える場合と比べて、短時間で処理を完了することができるという点において優れている。通信順序の最適化に要する時間を短縮することは、通信順序の最適化のために時間を長く消費して、却って集団通信に要する時間を長くしてしまうことを防止するために重要である。
【0043】
ここで、経過時間の計測と、遅延の大きさの判定について説明しておく。経過時間の計測は、1対1通信における通信順序が早い側もしくは通信順序が遅い側の少なくとも一方のプロセスにおいて行われる。どちらの側のプロセスにおいてどの部分の経過時間の計測が行われるかは統一されている必要がある。
【0044】
通信順序が遅い側のプロセスにおいて経過時間を計測する場合、1対1通信の対応が可能になってから1対1通信が開始されるまで(もしくは完了するまで)の時間が短いと、通信順序が遅い側のプロセスの遅延が大きいと判定される。一方、通信順序が早い側のプロセスにおいて経過時間を計測する場合、1対1通信の対応が可能になってから1対1通信が開始されるまで(もしくは完了するまで)の時間が長いと、通信順序が遅い側のプロセスの遅延が大きいと判定される。
【0045】
また、通信順序が遅い側のプロセスと通信順序が早い側のプロセスの両方において経過時間を計測する場合、1対1通信の対応が可能になってから1対1通信が完了するまでの時間を全てのプロセスから収集することにより、後述するように各プロセスの遅延の大きさを正確に算出することができる。
【0046】
上述した経過時間の計測と、遅延の大きさの判定について具体例を示して説明する。図7は、経過時間の計測について説明するための説明図である。同図は、ブロードキャスト通信の内部処理として、相対的に通信順序が早いプロセス#0から相対的に通信順序が遅いプロセス#1へデータを伝送する1対1通信が行われる場面を示している。
【0047】
同図において、黒丸は、プロセス#1が「受信処理」に対応できるようになったタイミングを示し、黒丸から伸びている実線の矢印は、対応が可能になってから「受信処理」が開始されるまでの経過時間を示している。また、白丸は、プロセス#0が「送信処理」に対応できるようになったタイミングを示し、白丸から伸びている実線の矢印は、対応が可能になってから「送信処理」が開始されるまでの経過時間を示している。
【0048】
通信順序が遅い側のプロセスにおいて経過時間を計測する場合、「受信処理」への対応が可能になってから「受信処理」が開始されるまでの経過時間であるtr01、もしくは、「受信処理」への対応が可能になってから「受信処理」が完了するまでの経過時間であるTR01が計測される。そして、tr01もしくはTR01が短い場合に、プロセス#1の遅延が大きいと判定される。tr01を計測して遅延を判定する方式は、図1〜4の説明において述べた方式である。
【0049】
また、通信順序が早い側のプロセスにおいて経過時間を計測する場合、「送信処理」への対応が可能になってから「送信処理」が開始されるまでの経過時間であるts01、もしくは、「送信処理」への対応が可能になってから「送信処理」が完了するまでの経過時間であるTS01が計測される。そして、ts01もしくはTS01が長い場合に、プロセス#1の遅延が大きいと判定される。
【0050】
図8は、経過時間の計測結果に基づいて遅延時間を算出する処理を説明するための説明図である。同図は、ルートプロセスであるプロセス#0からプロセス#1〜#3に対してブロードキャスト通信が行われる場面を示しており、プロセス#0からプロセス#2へデータが送信された後、プロセス#0からプロセス#1へデータが送信されるとともにプロセス#2からプロセス#3へデータが送信されるように通信順序が設定されている。
【0051】
この例における各プロセスの遅延時間の長さは、各プロセスが1対1通信に対応できるようになってから1対1通信が完了するまでの時間を全て収集することにより算出することができる。
【0052】
例えば、プロセス#1の遅延時間であるTD01は、プロセス#0がプロセス#2への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるTS02と、プロセス#0がプロセス#1への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるTS01との和から、プロセス#1がプロセス#0からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるTR01を減じることによって算出できる。
【0053】
また、プロセス#2の遅延時間であるTD02は、プロセス#0がプロセス#2への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるTS02から、プロセス#2がプロセス#0からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるTR02を減じることによって算出できる。
【0054】
また、プロセス#3の遅延時間であるTD03は、プロセス#0がプロセス#2への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるTS02と、プロセス#2がプロセス#3への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるTS03との和から、プロセス#3がプロセス#2からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるTR03を減じることによって算出できる。
【0055】
このように、各プロセスの遅延時間を正確に算出することにより、通信順序の最適化を精密に行うことが可能になる。なお、遅延時間を計算するための計算式は、通信順序に対応する木構造から導出することができる。
【0056】
上記のいずれの方式で経過時間を計測する場合であっても、経過時間の計測はプロセス毎に独立して行うことが可能である。このことは、タイマの時間合わせ等の目的で各プロセスの同期を取る必要がないことを意味し、簡易な仕組みで通信順序の最適化を行うことを可能にしている。
【0057】
図6の説明に戻って、通信順序情報配信部121cは、通信順序情報121dに含まれる通信順序を、集団通信を実行するプロセス122へ配信する処理部である。通信順序情報121dは、集団通信の内部処理として実行される1対1通信の通信順序をコミュニケータ毎に保持する。コミュニケータとは、集団通信を実行するプロセスのグループであり、任意に作成できる。コントローラ121は、コミュニケータ毎に独立して経過時間情報の収集と通信順序の最適化を行って、その結果をコミュニケータ毎に通信順序情報121dに保存し、集団通信を実行するコミュニケータに対応する通信順序を通信順序情報121dから取得して配信する。
【0058】
なお、通信順序の配信、経過時間情報の収集および通信順序の最適化の実行間隔は動的に変更可能である。
【0059】
プロセス122は、通信順序情報更新部122aと、集団通信実行部122bと、経過時間計測部122cと、経過時間情報通知部122dと、通信順序情報122eとを含む。通信順序情報更新部122aは、配信された通信時間を通信順序情報122eとして記憶させる処理部である。集団通信実行部122bは、通信順序情報122eに格納された通信順序に従って集団通信を実行する処理部である。経過時間計測部122cは、集団通信実行部122bによって実行される集団通信の実行時間の経過を計測する処理部である。経過時間情報通知部122dは、経過時間計測部122cによって計測された経過時間情報をコントローラ121へ通知する処理部である。
【0060】
通信順序情報122eは、集団通信の内部処理として実行される1対1通信の通信順序をコミュニケータ毎に保持する。プロセス122は、コミュニケータ毎に通信順序を通信順序情報122eに保持し、コミュニケータ毎に独立して集団通信の実行時間の経過を計測し、その結果をコントローラ121へ通知する。
【0061】
次に、図5に示した情報処理システムの動作について説明する。図9は、図5に示した情報処理システムの動作を示すフローチャートである。同図に示すように、コントローラ121の通信順序最適化部121bは、まず、通信順序情報121dを初期生成する(ステップS101)。そして、プロセス122において集団実行を実行するための手続が呼び出されたタイミングで、通信順序情報配信部121cが通信順序情報121dに格納されている通信順序を各プロセス122へ配信する(ステップS102)。
【0062】
通信順序の配信後、経過時間情報収集部121aは、集団関数の実行時の経過時間に関する情報をプロセス122から収集する(ステップS103)。そして、いずれかのプロセス122から経過時間に関する情報の通知があった場合は(ステップS104肯定)、経過時間に関する情報を解析し、その結果に基づいて通信順序情報121dに保持されている通信順序を並び替える(ステップS105)。その後、コントローラ121は、ステップS102から処理を再開する。
【0063】
一方、プロセス122においては、集団実行を実行するための手続であるMPI_BCAST等の集団通信関数が呼び出されると(ステップS201)、通信順序情報更新部122aが、コントローラ121から配信された通信順序を受信して、通信順序情報122eとして保存する(ステップS202)。そして、集団通信実行部122bが、通信順序情報122eに含まれる通信順序に従って集団通信を実行し、その経過時間を経過時間計測部122cが計測する(ステップS203)。
【0064】
そして、経過時間情報通知部122dは、経過時間計測部122cによって計測された値を前回集団通信が実行されたときに計測された値と比較し(ステップS204)、その差が閾値よりも大きければ(ステップS205肯定)、経過時間計測部122cによって計測された値をコントローラ121へ通知する(ステップS206)。このように、変動が大きい場合のみ経過時間に関する情報を通知することにより、通信量とコントローラ121の処理量を小さくすることができるとともに、効果がほとんどない無意味な通信順の並び替えが行われることを回避することができる。
【0065】
経過時間計測部122cが比較する値は、計測された値だけではなく、今までに取った待ち時間の平均あるいは重み付けなどの評価式を使った値を使ってもよいし、待ち時間以外の付加情報(例えば、何回目のブロードキャスト通信の際に取ったデータであることを示す情報)を記憶してもよい。
【0066】
そして、プロセス122は、集団通信関数から復帰して他の処理を実行し(ステップS207)、再び集団通信関数が呼び出されれば、ステップS201〜207の処理を再実行する。
【0067】
なお、通信順序情報配信部121cによる通信順序の配信は、各プロセス122に対して個別に行うのではなく、集団通信の内部処理として実行される1対1通信を最初に実行するプロセス122に対してのみ行うこととしてもよい。どのプロセスが1対1通信を最初に実行するかは、通信順序情報121dから判断することができる。この場合、集団通信の内部処理として実行される1対1通信の中で通信順序が対向のプロセス122へ順次伝送される。こうすることにより、コントローラ121とプロセス122間、および、プロセス122同士の間の通信回数を最少に抑制することができる。
【0068】
なお、上述した実施例では、集団通信の内部処理として実行される1対1通信の組合せと順序が木構造に基づいて決定されることとしたが、本実施例に係る集団通信最適化方法等は、直列に1対1通信が実行される場合のように他のトポロジーに基づいて1対1通信の組合せと順序が決定される場合にも有効である。
【0069】
上述してきたように、本実施例では、集団通信を実行する各プロセスから集団通信の内部処理として実行される1対1通信の実行時の経過時間に関する情報を収集し、この情報に基づいて遅延が発生しているプロセスが1対1通信を実行するタイミングが遅くなるように通信順序を並び替えることとしたので、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる。
【0070】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【0071】
(付記1)所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラムであって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集手順と、
前記情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手順と
をコンピュータに実行させることを特徴とする集団通信最適化プログラム。
【0072】
(付記2)前記通信順序最適化手順によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信手順をさらにコンピュータに実行させることを特徴とする付記1に記載の集団通信最適化プログラム。
【0073】
(付記3)前記通信順序情報配信手順は、集団通信を構成する1対1通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記2に記載の集団通信最適化プログラム。
【0074】
(付記4)前記経過時間情報収集手順は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記1〜3のいずれか1つに記載の集団通信最適化プログラム。
【0075】
(付記5)前記通信順序最適化手順は、各プロセスが1対1通信に対応できるようになってから1対1通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記1〜4のいずれか1つに記載の集団通信最適化プログラム。
【0076】
(付記6)所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、
前記経過時間情報収集手段によって収集された情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段と
を備えたことを特徴とする集団通信最適化装置。
【0077】
(付記7)前記通信順序最適化手段によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信手段をさらに備えたことを特徴とする付記6に記載の集団通信最適化装置。
【0078】
(付記8)前記通信順序情報配信手段は、集団通信を構成する1対1通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記7に記載の集団通信最適化装置。
【0079】
(付記9)前記経過時間情報収集手段は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記6〜8のいずれか1つに記載の集団通信最適化装置。
【0080】
(付記10)前記通信順序最適化手段は、前記経過時間情報収集手段によって収集された各プロセスが1対1通信に対応できるようになってから1対1通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記6〜9のいずれか1つに記載の集団通信最適化装置。
【0081】
(付記11)所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化方法であって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集工程と、
前記経過時間情報収集工程によって収集された情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化工程と
を含んだことを特徴とする集団通信最適化方法。
【0082】
(付記12)前記通信順序最適化工程によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信工程をさらに含んだことを特徴とする付記11に記載の集団通信最適化方法。
【0083】
(付記13)前記通信順序情報配信工程は、集団通信を構成する1対1通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記12に記載の集団通信最適化方法。
【0084】
(付記14)前記経過時間情報収集工程は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記11〜13のいずれか1つに記載の集団通信最適化方法。
【0085】
(付記15)前記通信順序最適化工程は、前記経過時間情報収集工程によって収集された各プロセスが1対1通信に対応できるようになってから1対1通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記11〜14のいずれか1つに記載の集団通信最適化方法。
【図面の簡単な説明】
【0086】
【図1】本実施例に係る集団通信最適化方法における通信順序と木構造について説明するための説明図である。
【図2】集団通信実行時における時間経過の一例を示す説明図である。
【図3】一部のプロセスに処理遅延が発生した場合の時間経過の一例を示す説明図である。
【図4】通信順序の入れ換え後の集団通信の一例を示す図である。
【図5】本実施例に係る集団通信最適化方法を実行する情報処理システムの一例を示す図である。
【図6】図5に示した情報処理装置の構成を示す機能ブロック図である。
【図7】経過時間の計測について説明するための説明図である。
【図8】経過時間の計測結果に基づいて遅延時間を算出する処理を説明するための説明図である。
【図9】図5に示した情報処理システムの動作を示すフローチャートである。
【符号の説明】
【0087】
1a、1b 通信順序情報
2 木構造
10a〜10d 情報処理装置
11 CPU
12 メモリ
121 コントローラ
121a 経過時間情報収集部
121b 通信順序最適化部
121c 通信順序情報配信部
121d 通信順序情報
122 プロセス
122a 通信順序情報更新部
122b 集団通信実行部
122c 経過時間計測部
122d 経過時間情報通知部
122e 通信順序情報
13 ハードディスク装置
131 集団通信最適化プログラム
132 アプリケーションプログラム
14 媒体読取装置
15 ネットワークインターフェース装置
16 バス
20 接続手段

【特許請求の範囲】
【請求項1】
所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラムであって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集手順と、
前記情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手順と
をコンピュータに実行させることを特徴とする集団通信最適化プログラム。
【請求項2】
前記通信順序最適化手順によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信手順をさらにコンピュータに実行させることを特徴とする請求項1に記載の集団通信最適化プログラム。
【請求項3】
前記通信順序情報配信手順は、集団通信を構成する1対1通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする請求項2に記載の集団通信最適化プログラム。
【請求項4】
前記経過時間情報収集手順は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする請求項1〜3のいずれか1つに記載の集団通信最適化プログラム。
【請求項5】
前記通信順序最適化手順は、各プロセスが1対1通信に対応できるようになってから1対1通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする請求項1〜4のいずれか1つに記載の集団通信最適化プログラム。
【請求項6】
所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、
前記経過時間情報収集手段によって収集された情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段と
を備えたことを特徴とする集団通信最適化装置。
【請求項7】
所定の通信順序でプロセス間の1対1通信を実行することによって実現される集団通信を最適化する集団通信最適化方法であって、
前記1対1通信の実行時における経過時間に関する情報を収集する経過時間情報収集工程と、
前記経過時間情報収集工程によって収集された情報に基づいて、前記1対1通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記1対1通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化工程と
を含んだことを特徴とする集団通信最適化方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate


【公開番号】特開2009−193255(P2009−193255A)
【公開日】平成21年8月27日(2009.8.27)
【国際特許分類】
【出願番号】特願2008−32284(P2008−32284)
【出願日】平成20年2月13日(2008.2.13)
【国等の委託研究の成果に係る記載事項】(出願人による申告)平成19年度、文部科学省、科学技術試験研究委託事業、「ぺタスケール・システムインターコネクト技術の開発」委託研究、産業技術力強化法第19条の適用を受ける特許出願
【出願人】(000005223)富士通株式会社 (25,993)
【出願人】(391043332)財団法人福岡県産業・科学技術振興財団 (53)
【出願人】(504145342)国立大学法人九州大学 (960)