(57)【特許請求の範囲】
【請求項１】
所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラムであって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手順と、
前記情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手順と、
前記通信順序最適化手順によって並び替えられた通信順序を、前記１対１通信を最初に実行し、かつ、前記通信順序を他のプロセスへ伝送可能なプロセスのみへ配信する通信順序情報配信手順と、
をコンピュータに実行させることを特徴とする集団通信最適化プログラム。
【請求項２】
各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいものを選択して前記経過時間情報収集手順に取得させる経過時間情報選択手順をさらにコンピュータに実行させることを特徴とする請求項１に記載の集団通信最適化プログラム。
【請求項３】
所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラムであって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手順と、
前記情報に基づいて、通信順序が遅い側のプロセスにおいて経過時間が計測される場合には、各プロセスが受信可能になってから受信完了までの経過時間を各プロセスの遅延時間として算出する一方で、通信順序が早い側のプロセスにおいて経過時間が計測される場合には、各プロセスが送信可能になってから送信完了までの経過時間を各プロセスの遅延時間として算出し、該遅延時間に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手順と、
をコンピュータに実行させることを特徴とする集団通信最適化プログラム。
【請求項４】
所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、
前記情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段と、
前記通信順序最適化手段によって並び替えられた通信順序を、前記１対１通信を最初に実行し、かつ、前記通信順序を他のプロセスへ伝送可能なプロセスのみへ配信する通信順序情報配信手段と、
を備えたことを特徴とする集団通信最適化装置。
【請求項５】
所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化方法であって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集工程と、
前記情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化工程と、
前記通信順序最適化工程によって並び替えられた通信順序を、前記１対１通信を最初に実行し、かつ、前記通信順序を他のプロセスへ伝送可能なプロセスのみへ配信する通信順序情報配信工程と、
を含んだことを特徴とする集団通信最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法に関し、特に、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法に関する。
【背景技術】
【０００２】
近年、マルチプロセッサシステムの普及にともなって、複数のプロセッサ上で処理を並列実行する並列コンピューティングに対応したアプリケーションプログラムが多く開発されるようになっている。並列コンピューティングに対応したアプリケーションプログラムは、各プロセッサ上で動作するプロセスが他のプロセッサ上で動作するプロセスと情報をやりとりしながら処理を進めるように構成されている。
【０００３】
プロセス間の情報のやりとりは、プロセス間通信によって実現される。並列コンピューティングにおけるプロセス間通信を実現するための仕組みの代表的なものにＭＰＩ（Message Passing Interface）がある。ＭＰＩは、様々なタイプのマルチプロセッサシステムに対応できるように設計されており、標準化されたＡＰＩ（Application Programming Interface）を有している。
【０００４】
ＭＰＩによって定義されているプロセス間通信は、２種類に大別される。１つは、２つのプロセス間で情報をやりとりする１対１通信であり、もう１つは、複数のプロセス間で情報をやりとりする集団通信である。集団通信は、内部的には１対１通信を組み合わせて実行することによって実現されており、１対１通信に比べて、処理時間をより多く要する。このため、集団通信の処理時間を短縮することは、並列コンピューティングに対応したアプリケーションプログラムの性能を向上させるために非常に重要である。
【０００５】
集団通信を高速化するための技術は、特許文献１や非特許文献１〜３において開示されている。特許文献１において開示されている技術は、集団通信の内部処理として実行される１対１通信の組合せを工夫することによって処理時間の短縮を図るものである。また、非特許文献１〜３において開示されている技術は、集団通信の内部処理として実行される１対１通信の順序を決定する木構造を最適化することによって処理時間の短縮を図るものである。
【０００６】
【特許文献１】特開平１１−１１０３６２号公報
【非特許文献１】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>.
【非特許文献２】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>.
【非特許文献３】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>.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の特許文献１において開示されている技術は、各プロセスがほぼ同時に集団通信を実行できる状態になることを前提としており、一部のプロセスの処理が遅延した場合に、集団通信の完了がその分だけ遅延してしまうという問題がある。また、上記の非特許文献１〜３には、このような遅延の影響を軽減するために、木構造を最適化して１対１通信の通信順序を入れ換える概念が示されているが、具体的に何を基準としてどのように通信順序を入れ換えるかは示されていない。
【０００８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本願の開示する集団通信最適化装置は、一つの態様において、所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、前記経過時間情報収集手段によって収集された情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段とを備える。
【００１０】
この態様によれば、集団通信を実行する各プロセスから集団通信の内部処理として実行される１対１通信の実行時の経過時間に関する情報を収集し、この情報に基づいて遅延が発生しているプロセスが１対１通信を実行するタイミングが遅くなるように通信順序を並び替えることとしたので、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる。
【００１１】
なお、上記の集団通信最適化装置の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも上述した課題を解決するために有効である。
【発明の効果】
【００１２】
本願の開示する集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法によれば、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１３】
以下に添付図面を参照して、本発明に係る集団通信最適化プログラム、集団通信最適化装置および集団通信最適化方法の好適な実施の形態を詳細に説明する。なお、以下の実施例では、集団通信の仕組みとしてＭＰＩを用いる場合を例にして説明するが、本発明は、ＭＰＩ以外の仕組みを用いて集団通信を行う場合にも有効である。
【００１４】
また、以下の実施例では、１つのプロセスから複数のプロセスへ同一のデータを送信するための集団通信であるブロードキャスト通信（ＭＰＩにおけるＭＰＩ＿ＢＣＡＳＴに相当）の場合を例にして本発明について説明するが、本発明は、１つのプロセスから複数のプロセスへそれぞれ異なるデータを送信するための集団通信であるスキャッタ通信（ＭＰＩにおけるＭＰＩ＿ＳＣＡＴＴＥＲに相当）や、複数のプロセスに散在しているデータを１つのプロセスに集めるための通信であるギャザー通信（ＭＰＩにおけるＭＰＩ＿ＧＡＴＨＥＲに相当）のような他の種類の集団通信においても有効である。
【実施例】
【００１５】
まず、本実施例に係る集団通信最適化方法の概要について説明する。本実施例に係る集団通信最適化方法では、予め決められた通信順序に従って１対１通信を複数回実行することによって集団通信が実現される。また、集団通信の実行時間を短縮させるため、通信順序に対応する木構造に基づいて、１対１通信が並列に実行される。
【００１６】
図１は、本実施例に係る集団通信最適化方法における通信順序と木構造について説明するための説明図である。同図は、ルートプロセスであるプロセス＃０からプロセス＃１〜＃７に対してブロードキャスト通信が行われる場合の例を示している。通信順序情報１ａは、通信順序を保持する情報であり、１対１通信の対象となるべきタイミングが、プロセス＃４、プロセス＃２、プロセス＃６、プロセス＃１、プロセス＃３、プロセス＃５、プロセス＃７の順に早いことを示している。
【００１７】
木構造２は、通信順序情報１ａに対応して生成されるｂｉｎｏｍｉｎａｌツリー（２項木）であり、実際にどのような組合せの１対１通信をどのような順序で行うかを決定するために用いられる。木構造２は、１対１通信が下記のように行われることを示している。
【００１８】
（フェーズ１）
プロセス＃０からプロセス＃４へデータが伝送される。
【００１９】
（フェーズ２）
プロセス＃０からプロセス＃２へデータが伝送される。
また、プロセス＃４からプロセス＃６へデータが伝送される。
【００２０】
（フェーズ３）
プロセス＃０からプロセス＃１へデータが伝送される。
また、プロセス＃２からプロセス＃３へデータが伝送される。
また、プロセス＃４からプロセス＃５へデータが伝送される。
また、プロセス＃６からプロセス＃７へデータが伝送される。
【００２１】
このように、木構造２に基づいて１対１通信を実行していくことにより、プロセス＃０が保持するデータが、ブロードキャスト通信によって、最短３フェーズでプロセス＃１〜＃７へ伝送される。しかしながら、一部のプロセスにおいて処理の遅延が発生していると、そのプロセスが１対１通信に対応するタイミングが遅くなり、ブロードキャスト通信が完了するまでに要する時間が長くなってしまう。この問題を解決するため、本実施例に係る集団通信最適化方法では、集団通信実行時における経過時間がプロセス毎に計測され、その計測結果に基づいて、通信順序の並べ替えが動的に行われる。
【００２２】
この経過時間に基づく通信順序の並べ替えについて具体例を示して説明する。図２は、集団通信実行時における時間経過の一例を示す図である。同図において、「固有処理」は、集団通信に先立って行われるプロセス固有の処理を示している。そして、「送信処理」と「受信処理」は、集団通信の内部処理として実行される１対１通信における送信側の処理と受信側の処理を示しており、点線の矢印は、１対１通信における「送信処理」と「受信処理」の対応を示している。また、黒丸は、プロセスが「受信処理」に対応できるようになったタイミングを示し、黒丸から伸びている実線の矢印は、対応が可能になってから「受信処理」が開始されるまでの経過時間を示している。なお、この例における「受信処理」に対応できるようになったタイミングは、プロセスが、集団通信を実行するための手続（例えば、ＭＰＩ＿ＢＣＡＳＴ）を呼び出したタイミングと一致する。
【００２３】
図２に示す例は、図１に示した通信順序情報１ａに従ってブロードキャスト通信が行われる場合を示している。この例では、いずれのプロセスも「固有処理」において遅延が発生しておらず、全てのプロセスが、ほぼ同一のタイミング集団通信を実行可能な状態となっている。このため、各１対１通信が待ち時間を経ることなく実行され、最小限の時間で集団通信の実行が完了している。
【００２４】
図３は、一部のプロセスに処理遅延が発生した場合の時間経過の一例を示す図である。同図に示す例では、プロセス＃６の「固有処理」において遅延が発生している。このため、プロセス＃４は、プロセス＃０との１対１通信が完了した後、プロセス＃６との１対１通信をすぐに実行することができず、待ち時間が生じてしまっている。そして、この待ち時間の分だけ集団通信が完了する時間が遅れてしまっている。
【００２５】
このように一部のプロセスに処理遅延が発生すると、集団通信の内部処理において待ち時間が必要になり、集団通信の実行完了が遅れてしまう。一般に、処理遅延が一度発生したプロセスは、その後も処理遅延を繰り返し発生させる習慣性があることが知られており、そのプロセスが原因となって集団通信の実行完了が毎回遅れてしまうことになる。
【００２６】
本実施例に係る集団通信最適化方法は、集団通信実行時における経過時間をプロセス毎に計測し、その計測結果に基づいて、処理遅延が発生しているプロセスが１対１通信を行うタイミングが遅くなるように通信順序の並び替えを行う。例えば、図３における実線の矢印の部分の長さ、すなわち、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間を各プロセスが測定し、その結果に基づいて通信順序の並び替えが行われる。
【００２７】
図３の例では、プロセス＃６が「固有処理」を実行している最中に、プロセス＃４はプロセス＃６に対して「送信処理」を実行することができる状態になっている。このため、プロセス＃６が「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間は非常に短くなっている。このように、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間は、処理遅延が発生しているプロセスにおいて非常に短くなる。
【００２８】
そこで、本実施例に係る集団通信最適化方法の一態様では、「受信処理」に対応できるようになってから「受信処理」が開始されるまでの経過時間が最も短いプロセスと、この経過時間が最も長いプロセスの通信順序を入れ換えることによって、実行時間が最短化されるように集団通信の最適化が図られる。例えば、図３の例では、プロセス＃６とプロセス＃７の通信順序が入れ換えられる。
【００２９】
図４は、通信順序の入れ換え後の集団通信の一例を示す図である。同図に示す通信順序情報１ｂのように、通信順序情報１ａにおけるプロセス＃６とプロセス＃７の順序を入れ換えることにより、プロセス＃６を対向プロセスとして１対１通信が開始されるタイミングが遅くなる。このため、同図の例のように、プロセス＃６に図３の例と同様の遅延が発生しても、その遅延が１対１通信に影響を与えない可能性が高くなる。
【００３０】
このように、本実施例に係る集団通信最適化方法は、各プロセスが集団通信の実行時に計測した経過時間に基づいて通信順序を最適化する。これによって、一部のプロセスに処理遅延が発生した場合であっても、集団通信の実行時間を最短に抑えることが可能になる。
【００３１】
次に、本実施例に係る集団通信最適化方法を実行する情報処理システムについて説明する。図５は、本実施例に係る集団通信最適化方法を実行する情報処理システムの一例を示す図である。同図に示す情報処理システムは、情報処理装置１０ａ〜１０ｄを、高速で情報の伝送が可能な接続手段２０によって相互接続して構成されている。なお、集団通信最適化方法を実行する情報処理システムの物理的な態様は、図５に示したものに限定されることはなく、複数のプロセスを並列的に実行可能な各種態様を含む。
【００３２】
情報処理装置１０ａ〜１０ｄのそれぞれでは、集団通信を行うプロセス１２２が稼動している。また、情報処理装置１０ａでは、コントローラ１２１が稼動している。コントローラ１２１は、集団関数の実行時における経過時間に関する情報を各プロセス１２２から収集し、収集した情報に基づいて通信順序を最適化する機能部である。なお、コントローラ１２１は、情報処理装置１０ａ〜１０ｄのいずれにおいて稼動していてもよい。
【００３３】
図６は、図５に示した情報処理装置１０ａの構成を示す機能ブロック図である。なお、コントローラ１２１が稼動していないことを除いて、情報処理装置１０ｂ〜１０ｄは、情報処理装置１０ａと同様の構成を有する。同図に示すように、情報処理装置１０ａは、ＣＰＵ（Central Processing Unit）１１と、メモリ１２と、ハードディスク装置１３と、媒体読取装置１４と、ネットワークインターフェース装置１５とを、バス１６で接続して構成されている。
【００３４】
ＣＰＵ１１は、各種演算処理を実行することにより、様々な機能を実現することができる演算回路である。メモリ１２は、ＣＰＵ１１によって実行される命令コード列や、データが一時的に記憶される記憶回路である。ハードディスク装置１３は、各種データやプログラムを記憶する記憶装置である。媒体読取装置１４は、ＣＤ−ＲＯＭ等の各種記憶媒体から情報を読み取る装置である。ネットワークインターフェース装置１５は、他の情報処理装置と情報をやりとりするためのインターフェース装置である。
【００３５】
ＣＰＵ１１は、ハードディスク装置１３に記憶されている集団通信最適化プログラム１３１を読み出してメモリ１２に展開し、展開後の領域から命令コード列やデータを適宜読み出して演算処理することにより、コントローラ１２１の機能を実現する。同様に、ＣＰＵ１１は、ハードディスク装置１３に記憶されているアプリケーションプログラム１３２を読み出してメモリ１２に展開し、展開後の領域から命令コード列やデータを適宜読み出して演算処理することにより、プロセス１２２の機能を実現する。
【００３６】
なお、集団通信最適化プログラム１３１およびアプリケーションプログラム１３２は、必ずしもハードディスク装置１３に記憶されている必要はなく、媒体読取装置１４によって読み取られる記憶媒体や、ネットワークインターフェース装置１５を通じてアクセス可能な他の情報処理装置に記憶されていてもよい。
【００３７】
コントローラ１２１は、通信順序の最適化を行う機能部であり、経過時間情報収集部１２１ａと、通信順序最適化部１２１ｂと、通信順序情報配信部１２１ｃと、通信順序情報１２１ｄとを含む。なお、コントローラ１２１は、独立したプロセスとして実現されていてもよいし、情報処理装置１０ａの基本的な動作を管理するオペレーティングシステムの一部として実現されていてもよいし、プロセス１２２の一部として実現されていてもよい。
【００３８】
経過時間情報収集部１２１ａは、各プロセスが集団関数の実行時に計測した経過時間に関する情報を収集する処理部である。通信順序最適化部１２１ｂは、経過時間情報収集部１２１ａによって収集された情報に基づいて、遅延の大きかったプロセスの通信順序が遅くなるように通信順序情報１２１ｄに格納されている通信順序を最適化する処理部である。具体的には、通信順序最適化部１２１ｂは、経過時間情報収集部１２１ａによって収集された情報に基づいて最も遅延が大きいと判断されたプロセスと、最も遅延が小さいと判断されたプロセスの順序を入れ換えることによって通信順序を最適化する。
【００３９】
一般に、集団通信は、ループ処理の一部として何度も繰り返して実行される。そのため、上記のように遅延が最も大きいと判断されたプロセスと遅延が最も小さいと判断されたプロセスの実行順序を入れ換えるだけであっても、集団通信が何度か実行されるうちに通信順序の最適化が適応的に進んでいき、集団通信に要する時間の短縮化が達成される。なお、遅延が大きい順に選択した所定数のプロセスの順序と、遅延が小さい順に選択した所定数のプロセスの順序とを通信順序情報１２１ｄにおいて入れ換えるように通信順序最適化部１２１ｂを構成してもよい。
【００４０】
また、最適化の際にｂｉｎｏｍｉｎａｌツリーの構造を利用して受信しかしてしないもの同士を入れ換えることを避けるように通信順序最適化部１２１ｂを構成してもよい。具体的には、ツリーの構造から送信を行わない（子を持たない）プロセス番号（図１におけるプロセス＃１，３，５，７）を通信順序最適化部１２１ｂで保持しておき、保持しているプロセス番号については、通信順序が最も早かったとしても遅いものと入れ換えないようにする。
【００４１】
さらに経過時間によるプロセスの実行順序の入れ替えと共に、最適化の際にｂｉｎｏｍｉｎａｌツリーの構造を利用して、各ノードの送信回数によって重み付けして特定ノードを入れ替え易く（あるいは入れ換え難く）するように通信順序最適化部１２１ｂを構成してもよい。具体的には、通信順序最適化部１２１ｂに各プロセス番号が行う送信処理の回数を保持し、送信回数の多いプロセスの経過時間に重み付けをつけることにより、実行順序の入れ替えを行う。
【００４２】
このように、一部のプロセスの順序のみを入れ換えることは、全てのプロセスの順序を入れ換える場合と比べて、短時間で処理を完了することができるという点において優れている。通信順序の最適化に要する時間を短縮することは、通信順序の最適化のために時間を長く消費して、却って集団通信に要する時間を長くしてしまうことを防止するために重要である。
【００４３】
ここで、経過時間の計測と、遅延の大きさの判定について説明しておく。経過時間の計測は、１対１通信における通信順序が早い側もしくは通信順序が遅い側の少なくとも一方のプロセスにおいて行われる。どちらの側のプロセスにおいてどの部分の経過時間の計測が行われるかは統一されている必要がある。
【００４４】
通信順序が遅い側のプロセスにおいて経過時間を計測する場合、１対１通信の対応が可能になってから１対１通信が開始されるまで（もしくは完了するまで）の時間が短いと、通信順序が遅い側のプロセスの遅延が大きいと判定される。一方、通信順序が早い側のプロセスにおいて経過時間を計測する場合、１対１通信の対応が可能になってから１対１通信が開始されるまで（もしくは完了するまで）の時間が長いと、通信順序が遅い側のプロセスの遅延が大きいと判定される。
【００４５】
また、通信順序が遅い側のプロセスと通信順序が早い側のプロセスの両方において経過時間を計測する場合、１対１通信の対応が可能になってから１対１通信が完了するまでの時間を全てのプロセスから収集することにより、後述するように各プロセスの遅延の大きさを正確に算出することができる。
【００４６】
上述した経過時間の計測と、遅延の大きさの判定について具体例を示して説明する。図７は、経過時間の計測について説明するための説明図である。同図は、ブロードキャスト通信の内部処理として、相対的に通信順序が早いプロセス＃０から相対的に通信順序が遅いプロセス＃１へデータを伝送する１対１通信が行われる場面を示している。
【００４７】
同図において、黒丸は、プロセス＃１が「受信処理」に対応できるようになったタイミングを示し、黒丸から伸びている実線の矢印は、対応が可能になってから「受信処理」が開始されるまでの経過時間を示している。また、白丸は、プロセス＃０が「送信処理」に対応できるようになったタイミングを示し、白丸から伸びている実線の矢印は、対応が可能になってから「送信処理」が開始されるまでの経過時間を示している。
【００４８】
通信順序が遅い側のプロセスにおいて経過時間を計測する場合、「受信処理」への対応が可能になってから「受信処理」が開始されるまでの経過時間であるｔｒ０１、もしくは、「受信処理」への対応が可能になってから「受信処理」が完了するまでの経過時間であるＴＲ０１が計測される。そして、ｔｒ０１もしくはＴＲ０１が短い場合に、プロセス＃１の遅延が大きいと判定される。ｔｒ０１を計測して遅延を判定する方式は、図１〜４の説明において述べた方式である。
【００４９】
また、通信順序が早い側のプロセスにおいて経過時間を計測する場合、「送信処理」への対応が可能になってから「送信処理」が開始されるまでの経過時間であるｔｓ０１、もしくは、「送信処理」への対応が可能になってから「送信処理」が完了するまでの経過時間であるＴＳ０１が計測される。そして、ｔｓ０１もしくはＴＳ０１が長い場合に、プロセス＃１の遅延が大きいと判定される。
【００５０】
図８は、経過時間の計測結果に基づいて遅延時間を算出する処理を説明するための説明図である。同図は、ルートプロセスであるプロセス＃０からプロセス＃１〜＃３に対してブロードキャスト通信が行われる場面を示しており、プロセス＃０からプロセス＃２へデータが送信された後、プロセス＃０からプロセス＃１へデータが送信されるとともにプロセス＃２からプロセス＃３へデータが送信されるように通信順序が設定されている。
【００５１】
この例における各プロセスの遅延時間の長さは、各プロセスが１対１通信に対応できるようになってから１対１通信が完了するまでの時間を全て収集することにより算出することができる。
【００５２】
例えば、プロセス＃１の遅延時間であるＴＤ０１は、プロセス＃０がプロセス＃２への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるＴＳ０２と、プロセス＃０がプロセス＃１への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるＴＳ０１との和から、プロセス＃１がプロセス＃０からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるＴＲ０１を減じることによって算出できる。
【００５３】
また、プロセス＃２の遅延時間であるＴＤ０２は、プロセス＃０がプロセス＃２への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるＴＳ０２から、プロセス＃２がプロセス＃０からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるＴＲ０２を減じることによって算出できる。
【００５４】
また、プロセス＃３の遅延時間であるＴＤ０３は、プロセス＃０がプロセス＃２への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるＴＳ０２と、プロセス＃２がプロセス＃３への「送信処理」に対応できるようになってから「送信処理」が完了するまでの時間であるＴＳ０３との和から、プロセス＃３がプロセス＃２からの「受信処理」に対応できるようになってから「受信処理」が完了するまでの時間であるＴＲ０３を減じることによって算出できる。
【００５５】
このように、各プロセスの遅延時間を正確に算出することにより、通信順序の最適化を精密に行うことが可能になる。なお、遅延時間を計算するための計算式は、通信順序に対応する木構造から導出することができる。
【００５６】
上記のいずれの方式で経過時間を計測する場合であっても、経過時間の計測はプロセス毎に独立して行うことが可能である。このことは、タイマの時間合わせ等の目的で各プロセスの同期を取る必要がないことを意味し、簡易な仕組みで通信順序の最適化を行うことを可能にしている。
【００５７】
図６の説明に戻って、通信順序情報配信部１２１ｃは、通信順序情報１２１ｄに含まれる通信順序を、集団通信を実行するプロセス１２２へ配信する処理部である。通信順序情報１２１ｄは、集団通信の内部処理として実行される１対１通信の通信順序をコミュニケータ毎に保持する。コミュニケータとは、集団通信を実行するプロセスのグループであり、任意に作成できる。コントローラ１２１は、コミュニケータ毎に独立して経過時間情報の収集と通信順序の最適化を行って、その結果をコミュニケータ毎に通信順序情報１２１ｄに保存し、集団通信を実行するコミュニケータに対応する通信順序を通信順序情報１２１ｄから取得して配信する。
【００５８】
なお、通信順序の配信、経過時間情報の収集および通信順序の最適化の実行間隔は動的に変更可能である。
【００５９】
プロセス１２２は、通信順序情報更新部１２２ａと、集団通信実行部１２２ｂと、経過時間計測部１２２ｃと、経過時間情報通知部１２２ｄと、通信順序情報１２２ｅとを含む。通信順序情報更新部１２２ａは、配信された通信時間を通信順序情報１２２ｅとして記憶させる処理部である。集団通信実行部１２２ｂは、通信順序情報１２２ｅに格納された通信順序に従って集団通信を実行する処理部である。経過時間計測部１２２ｃは、集団通信実行部１２２ｂによって実行される集団通信の実行時間の経過を計測する処理部である。経過時間情報通知部１２２ｄは、経過時間計測部１２２ｃによって計測された経過時間情報をコントローラ１２１へ通知する処理部である。
【００６０】
通信順序情報１２２ｅは、集団通信の内部処理として実行される１対１通信の通信順序をコミュニケータ毎に保持する。プロセス１２２は、コミュニケータ毎に通信順序を通信順序情報１２２ｅに保持し、コミュニケータ毎に独立して集団通信の実行時間の経過を計測し、その結果をコントローラ１２１へ通知する。
【００６１】
次に、図５に示した情報処理システムの動作について説明する。図９は、図５に示した情報処理システムの動作を示すフローチャートである。同図に示すように、コントローラ１２１の通信順序最適化部１２１ｂは、まず、通信順序情報１２１ｄを初期生成する（ステップＳ１０１）。そして、プロセス１２２において集団実行を実行するための手続が呼び出されたタイミングで、通信順序情報配信部１２１ｃが通信順序情報１２１ｄに格納されている通信順序を各プロセス１２２へ配信する（ステップＳ１０２）。
【００６２】
通信順序の配信後、経過時間情報収集部１２１ａは、集団関数の実行時の経過時間に関する情報をプロセス１２２から収集する（ステップＳ１０３）。そして、いずれかのプロセス１２２から経過時間に関する情報の通知があった場合は（ステップＳ１０４肯定）、経過時間に関する情報を解析し、その結果に基づいて通信順序情報１２１ｄに保持されている通信順序を並び替える（ステップＳ１０５）。その後、コントローラ１２１は、ステップＳ１０２から処理を再開する。
【００６３】
一方、プロセス１２２においては、集団実行を実行するための手続であるＭＰＩ＿ＢＣＡＳＴ等の集団通信関数が呼び出されると（ステップＳ２０１）、通信順序情報更新部１２２ａが、コントローラ１２１から配信された通信順序を受信して、通信順序情報１２２ｅとして保存する（ステップＳ２０２）。そして、集団通信実行部１２２ｂが、通信順序情報１２２ｅに含まれる通信順序に従って集団通信を実行し、その経過時間を経過時間計測部１２２ｃが計測する（ステップＳ２０３）。
【００６４】
そして、経過時間情報通知部１２２ｄは、経過時間計測部１２２ｃによって計測された値を前回集団通信が実行されたときに計測された値と比較し（ステップＳ２０４）、その差が閾値よりも大きければ（ステップＳ２０５肯定）、経過時間計測部１２２ｃによって計測された値をコントローラ１２１へ通知する（ステップＳ２０６）。このように、変動が大きい場合のみ経過時間に関する情報を通知することにより、通信量とコントローラ１２１の処理量を小さくすることができるとともに、効果がほとんどない無意味な通信順の並び替えが行われることを回避することができる。
【００６５】
経過時間計測部１２２ｃが比較する値は、計測された値だけではなく、今までに取った待ち時間の平均あるいは重み付けなどの評価式を使った値を使ってもよいし、待ち時間以外の付加情報（例えば、何回目のブロードキャスト通信の際に取ったデータであることを示す情報）を記憶してもよい。
【００６６】
そして、プロセス１２２は、集団通信関数から復帰して他の処理を実行し（ステップＳ２０７）、再び集団通信関数が呼び出されれば、ステップＳ２０１〜２０７の処理を再実行する。
【００６７】
なお、通信順序情報配信部１２１ｃによる通信順序の配信は、各プロセス１２２に対して個別に行うのではなく、集団通信の内部処理として実行される１対１通信を最初に実行するプロセス１２２に対してのみ行うこととしてもよい。どのプロセスが１対１通信を最初に実行するかは、通信順序情報１２１ｄから判断することができる。この場合、集団通信の内部処理として実行される１対１通信の中で通信順序が対向のプロセス１２２へ順次伝送される。こうすることにより、コントローラ１２１とプロセス１２２間、および、プロセス１２２同士の間の通信回数を最少に抑制することができる。
【００６８】
なお、上述した実施例では、集団通信の内部処理として実行される１対１通信の組合せと順序が木構造に基づいて決定されることとしたが、本実施例に係る集団通信最適化方法等は、直列に１対１通信が実行される場合のように他のトポロジーに基づいて１対１通信の組合せと順序が決定される場合にも有効である。
【００６９】
上述してきたように、本実施例では、集団通信を実行する各プロセスから集団通信の内部処理として実行される１対１通信の実行時の経過時間に関する情報を収集し、この情報に基づいて遅延が発生しているプロセスが１対１通信を実行するタイミングが遅くなるように通信順序を並び替えることとしたので、一部のプロセスに遅延が発生している場合でも集団通信の実行時間を最短にすることができる。
【００７０】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７１】
（付記１）所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化プログラムであって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手順と、
前記情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手順と
をコンピュータに実行させることを特徴とする集団通信最適化プログラム。
【００７２】
（付記２）前記通信順序最適化手順によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信手順をさらにコンピュータに実行させることを特徴とする付記１に記載の集団通信最適化プログラム。
【００７３】
（付記３）前記通信順序情報配信手順は、集団通信を構成する１対１通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記２に記載の集団通信最適化プログラム。
【００７４】
（付記４）前記経過時間情報収集手順は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記１〜３のいずれか１つに記載の集団通信最適化プログラム。
【００７５】
（付記５）前記通信順序最適化手順は、各プロセスが１対１通信に対応できるようになってから１対１通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記１〜４のいずれか１つに記載の集団通信最適化プログラム。
【００７６】
（付記６）所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化装置であって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集手段と、
前記経過時間情報収集手段によって収集された情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化手段と
を備えたことを特徴とする集団通信最適化装置。
【００７７】
（付記７）前記通信順序最適化手段によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信手段をさらに備えたことを特徴とする付記６に記載の集団通信最適化装置。
【００７８】
（付記８）前記通信順序情報配信手段は、集団通信を構成する１対１通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記７に記載の集団通信最適化装置。
【００７９】
（付記９）前記経過時間情報収集手段は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記６〜８のいずれか１つに記載の集団通信最適化装置。
【００８０】
（付記１０）前記通信順序最適化手段は、前記経過時間情報収集手段によって収集された各プロセスが１対１通信に対応できるようになってから１対１通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記６〜９のいずれか１つに記載の集団通信最適化装置。
【００８１】
（付記１１）所定の通信順序でプロセス間の１対１通信を実行することによって実現される集団通信を最適化する集団通信最適化方法であって、
前記１対１通信の実行時における経過時間に関する情報を収集する経過時間情報収集工程と、
前記経過時間情報収集工程によって収集された情報に基づいて、前記１対１通信において情報伝送が開始されるまでに対向プロセスを待たせた時間が他のプロセスよりも長かったプロセスほど、次回の集団通信の実行時に前記１対１通信の対向プロセスとなる順序が遅くなるように前記通信順序を並び替える通信順序最適化工程と
を含んだことを特徴とする集団通信最適化方法。
【００８２】
（付記１２）前記通信順序最適化工程によって並び替えられた通信順序を、前記集団通信を実行するプロセスへ配信する通信順序情報配信工程をさらに含んだことを特徴とする付記１１に記載の集団通信最適化方法。
【００８３】
（付記１３）前記通信順序情報配信工程は、集団通信を構成する１対１通信を最初に実行するプロセスのみへ前記通信順序を配信することを特徴とする付記１２に記載の集団通信最適化方法。
【００８４】
（付記１４）前記経過時間情報収集工程は、各プロセスにおいて計測された前記経過時間のうち、前回の集団通信の実行時からの変動が閾値よりも大きいもののみを収集することを特徴とする付記１１〜１３のいずれか１つに記載の集団通信最適化方法。
【００８５】
（付記１５）前記通信順序最適化工程は、前記経過時間情報収集工程によって収集された各プロセスが１対１通信に対応できるようになってから１対１通信が完了するまでの経過時間を組み合わせることによって各プロセスの遅延時間を算出し、該遅延時間に基づいて前記通信順序を並び替えることを特徴とする付記１１〜１４のいずれか１つに記載の集団通信最適化方法。
【図面の簡単な説明】
【００８６】
【図１】本実施例に係る集団通信最適化方法における通信順序と木構造について説明するための説明図である。
【図２】集団通信実行時における時間経過の一例を示す説明図である。
【図３】一部のプロセスに処理遅延が発生した場合の時間経過の一例を示す説明図である。
【図４】通信順序の入れ換え後の集団通信の一例を示す図である。
【図５】本実施例に係る集団通信最適化方法を実行する情報処理システムの一例を示す図である。
【図６】図５に示した情報処理装置の構成を示す機能ブロック図である。
【図７】経過時間の計測について説明するための説明図である。
【図８】経過時間の計測結果に基づいて遅延時間を算出する処理を説明するための説明図である。
【図９】図５に示した情報処理システムの動作を示すフローチャートである。
【符号の説明】
【００８７】
１ａ、１ｂ  通信順序情報
２    木構造 
１０ａ〜１０ｄ  情報処理装置
１１    ＣＰＵ
１２    メモリ
１２１    コントローラ
１２１ａ  経過時間情報収集部
１２１ｂ  通信順序最適化部
１２１ｃ  通信順序情報配信部
１２１ｄ  通信順序情報
１２２    プロセス
１２２ａ  通信順序情報更新部
１２２ｂ  集団通信実行部
１２２ｃ  経過時間計測部
１２２ｄ  経過時間情報通知部
１２２ｅ  通信順序情報
１３    ハードディスク装置
１３１    集団通信最適化プログラム
１３２    アプリケーションプログラム
１４    媒体読取装置
１５    ネットワークインターフェース装置
１６    バス
２０    接続手段
【図１】
0004978500.tif 000002
【図２】
0004978500.tif 000003
【図３】
0004978500.tif 000004
【図４】
0004978500.tif 000005
【図５】
0004978500.tif 000006
【図６】
0004978500.tif 000007
【図７】
0004978500.tif 000008
【図８】
0004978500.tif 000009
【図９】
0004978500.tif 000010