(57)【要約】集団通信での通信フェーズを合わせるためのプロセッサ間同期のオーバヘッドを削減して、集団通信を高速化する通信方法を提供することである。並列コンピュータの各プロセッサは、プロセッサ間ネットワークを介して、プロセッサ間で同時に通信を行う集団通信フェーズに入る手前の処理をそれぞれ開始する。手前の処理を、所定時間ｔぶんだけ残した時点で、各プロセッサは、同期命令を先行してそれぞれ実行する。同期条件が成立したならば、プロセッサ間同期管理部は、複数のプロセッサへそれぞれ同期完了を送信する。この間、各プロセッサは、手前の処理をオーバラップさせて実行する。その後、複数のプロセッサは、集団通信フェーズに入る。
2009028231.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサと、
前記複数のプロセッサを接続するプロセッサ間ネットワークと、
前記複数のプロセッサの間でプロセッサ間同期をとるためのプロセッサ間同期管理部と
を有する並列コンピュータにおける通信方法であって、
（１ａ）前記複数のプロセッサにおける各プロセッサが、前記プロセッサ間ネットワークを介して、プロセッサ間で同時に通信を行う集団通信フェーズに入る手前の処理をそれぞれ開始することと、
（１ｂ）前記手前の処理を、所定時間ｔ１ぶんだけ残した時点で、前記各プロセッサが、同期命令を先行してそれぞれ実行することと、
（１ｃ）前記同期命令の実行では、前記各プロセッサが、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出することと、
（１ｄ）前記プロセッサ間同期管理部が、前記各プロセッサからそれぞれ前記同期要求を受信することと、
（１ｅ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記プロセッサ間同期管理部が、前記複数のプロセッサへそれぞれ同期完了を送信することと、
（１ｆ）前記各プロセッサが、前記同期完了をそれぞれ受信することと、
（１ｇ）前記各プロセッサが、前記（１ｂ）〜（１ｆ）と並行して、前記手前の処理を実行することと、
（１ｈ）前記（１ｇ）を行った後、前記同期完了の受信を確認後、前記複数のプロセッサが、前記集団通信フェーズに入ることとを備える
通信方法。
【請求項２】
前記所定時間ｔ１として、
前記並列コンピュータの構成により、予め決定される時間であって、
前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲１記載の通信方法。
【請求項３】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ１として、
前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲１記載の通信方法。
【請求項４】
前記（１ｅ）は、
前記最後に前記同期命令を実行するプロセッサが、前記手前の処理に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記プロセッサ間同期管理部は、前記複数のプロセッサへそれぞれ同期完了を送信することを備える
請求の範囲３記載の通信方法。
【請求項５】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ１として、
前記各プロセッサがそれぞれ行う前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲１記載の通信方法。
【請求項６】
前記（１ｅ）は、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記プロセッサ間同期管理部が、前記複数のプロセッサへ前記同期完了をそれぞれ送信することを備える
請求の範囲５記載の通信方法。
【請求項７】
（２ａ）複数の部分通信フェーズに分かれる集団通信フェーズに入ることと、
（２ｂ）前記複数の部分通信フェーズの中の一つの部分通信フェーズに入ることと、
（２ｃ）前記複数のプロセッサにおける各プロセッサが、前記複数のプロセッサにおける他のプロセッサと１対１の通信を行う部分通信をそれぞれ開始することと、
（２ｄ）前記部分通信を、所定時間ｔ２ぶんだけ残した時点で、前記各プロセッサが、同期命令を先行してそれぞれ実行することと、
（２ｅ）前記同期命令の実行では、前記各プロセッサが、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出することと、
（２ｆ）前記プロセッサ間同期管理部が、前記各プロセッサからそれぞれ前記同期要求を受信することと、
（２ｇ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記プロセッサ間同期管理部が、前記複数のプロセッサへそれぞれ同期完了を送信することと、
（２ｈ）前記各プロセッサが、前記同期完了をそれぞれ受信することと、
（２ｉ）前記各プロセッサが、前記（２ｄ）〜（２ｈ）と並行して、前記部分通信を継続して実行することと、
（２ｊ）前記（２ｉ）を行った後、前記同期完了の受信を確認後、前記複数のプロセッサが、次の部分通信フェーズに入ることとを更に備える
請求の範囲１記載の通信方法。
【請求項８】
前記所定時間ｔ２として、
前記並列コンピュータの構成により、予め決定される時間であって、
前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲７記載の通信方法。
【請求項９】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ２として、
前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲７記載の通信方法。
【請求項１０】
前記（２ｇ）は、
前記最後に前記同期命令を実行するプロセッサが、前記部分通信に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記プロセッサ間同期管理部は、前記複数のプロセッサへそれぞれ同期完了を送信することを備える
請求の範囲９記載の通信方法。
【請求項１１】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ２として、
前記各プロセッサがそれぞれ行う前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲７記載の通信方法。
【請求項１２】
前記（２ｇ）は、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記プロセッサ間同期管理部が、前記複数のプロセッサへ前記同期完了をそれぞれ送信することを備える
請求の範囲１１記載の通信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサがネットワークに接続された並列コンピュータにおける通信方法に関し、特に複数のプロセッサが同時に通信を行う集団通信を高速化するための方法に関する。この出願は、２００７年８月２４日に出願された特許出願番号２００７−２１８３２３号の日本特許出願に基づいており、その出願による優先権の利益を主張し、その出願の開示は、引用することにより、そっくりそのままここに組み込まれている。
【背景技術】
【０００２】
複数のプロセッサがネットワークによって接続された並列コンピュータで並列処理をするには、複数のプロセッサが同時に通信を行う集団通信を行う必要がある。特許第２６０１５９１号公報には、並列コンピュータの全プロセッサが全プロセッサに通信するための方法について書かれている。この公報の図１１には方法の処理フローがあげられており、特定の通信の宛先に通信するフェーズ（部分通信フェーズと呼ぶ）間に全プロセッサでプロセッサ間同期を行って、全プロセッサのフェーズを合わせている。これは、フェーズを合わせることにより、全プロセッサで通信の宛先を同時に切り替えるためである。そうしない場合には、プロセッサ間でフェーズがずれてしまい、本来は通信経路上でのぶつかりがない通信であるはずなのに、通信経路上でのぶつかりが発生するためである。たとえば、公報の図９にあるフェーズ管理テーブルには、フェーズ２のＰＥ２からＰＥ３への通信と、フェーズ３のＰＥ８からＰＥ３への通信が存在することが記載されている。もしも、ＰＥ２がフェーズ２のＰＥ３への通信を行っているときに、ＰＥ８がフェーズ３に入ってしまいＰＥ３への通信を行うと、ＰＥ３への通信が２つ発生するため性能は半分になる。公報では、通信経路上でのぶつかりが起こらないようにフェーズ管理テーブルを作って、フェーズとフェーズの間に全プロセッサでプロセッサ間同期を行う。全プロセッサでのフェーズを合わせることにより、全プロセッサから全プロセッサへの通信を高速に行う方法を提案している。【０００３】
この関連技術が有する問題点の一つは、部分通信のフェーズと部分通信フェーズの間に、集団通信に参加する全プロセッサでプロセッサ間同期をとる必要があるため、プロセッサ間同期にかかる時間が本来の通信のオーバヘッドとなり、集団通信の性能が劣化することである。その理由は、複数のプロセッサ間でプロセッサ間同期をとるには何らかの通信を伴うので、何らかの時間がかかることに起因する。もしもプロセッサ間同期をとる複数のプロセッサが同時にプロセッサ間同期命令を実行したとしても、同期完了には何らかの時間がかかる。このプロセッサ間同期にかかる時間は、一般にプロセッサ数が多くなれば多くなるほど大きくなる。なぜなら、プロセッサ数が多い場合には物理的にプロセッサ間の距離が大きくなり、その間の通信の距離が長くなるからである。従って、並列コンピュータの規模が大規模になるほど、プロセッサ間同期にかかる時間が大きくなり、関連技術での部分通信フェーズと部分通信フェーズ間のプロセッサ間同期のオーバヘッドが大きくなり、集団通信の性能は劣化する。
【発明の開示】
【０００４】
本発明の目的は、集団通信での通信フェーズを合わせるためのプロセッサ間同期のオーバヘッドを削減して、集団通信を高速化する通信方法を提供することにある。
【０００５】
本発明の一つのアスペクトによる通信方法は、複数のプロセッサと、複数のプロセッサを接続するプロセッサ間ネットワークと、複数のプロセッサの間でプロセッサ間同期をとるためのプロセッサ間同期管理部とを有する並列コンピュータにおける通信方法である。（１ａ）複数のプロセッサにおける各プロセッサは、プロセッサ間ネットワークを介して、プロセッサ間で同時に通信を行う集団通信フェーズに入る手前の処理をそれぞれ開始する。（１ｂ）手前の処理を、所定時間ｔ１ぶんだけ残した時点で、各プロセッサは、同期命令を先行してそれぞれ実行する。（１ｃ）同期命令の実行では、各プロセッサは、プロセッサ間同期管理部へ、同期要求をそれぞれ送出する。（１ｄ）プロセッサ間同期管理部は、各プロセッサからそれぞれ同期要求を受信する。（１ｅ）複数のプロセッサの全てから同期要求を受信して、同期条件が成立したならば、プロセッサ間同期管理部が、複数のプロセッサへそれぞれ同期完了を送信する。（１ｆ）各プロセッサは、同期完了をそれぞれ受信する。（１ｇ）各プロセッサは、（１ｂ）〜（１ｆ）と並行して、手前の処理を実行する。（１ｈ）上記（１ｇ）を行った後、同期完了の受信を確認後、複数のプロセッサは、集団通信フェーズに入る。
【０００６】
本発明によれば、集団通信での通信フェーズを合わせるためのプロセッサ間同期のオーバヘッドを削減して、集団通信を高速化する通信方法を提供することができる。
【図面の簡単な説明】
【０００７】
【図１】図１は、実施例１の並列コンピュータを示す図である。
【図２】図２は、実施例１におけるプロセッサ間同期管理部の構成例を示す図である。
【図３】図３は、実施例１におけるプロセッサ間同期管理部の動きを説明する図である。
【図４】図４は、実施例１におけるプロセッサの動きを説明するフローチャートである。
【図５】図５は、プロセッサ間同期にかかる時間Ｔと、残りの処理（通信）にかかる時間との関係を示す図である。
【図６】図６は、実施例２の並列コンピュータを示す図である。
【図７】図７は、実施例２におけるプロセッサ間同期管理部の構成例を示す図である。
【図８】図８は、実施例２におけるプロセッサ間同期管理部の動きを説明する図である。
【図９】図９は、実施例２におけるプロセッサの動きを説明するフローチャートである。
【図１０】図１０は、関連技術における通信フェーズを説明するタイムチャートである。
【図１１】図１１は、実施例１〜３における通信フェーズを説明するタイムチャートである。
【図１２】図１２は、実施例３の並列コンピュータを示す図である。
【図１３】図１３は、実施例３におけるプロセッサ間同期管理部の構成例を示す図である。
【図１４】図１４は、実施例３におけるプロセッサ間同期管理部の動きを説明する図である。
【図１５】図１５は、実施例３におけるプロセッサの動きを説明するフローチャートである。
【発明を実施するための最良の形態】
【０００８】
本発明では、プロセッサ間同期にかかる時間分、先行してプロセッサ間同期命令を実行することにより、関連技術ではオーバヘッドとなっていたプロセッサ間同期の時間を隠蔽でき、集団通信を高速化することができる。以下、図面を参照して詳細に説明する。【０００９】
〔実施例１〕
図１を参照すると、本発明による一つ目の実施例としての並列コンピュータが示されている。図１において、並列コンピュータは、プロセッサ０  １０１、プロセッサ１〜プロセッサＮ−１の複数のプロセッサを有している。複数のプロセッサは、プロセッサ間ネットワーク１０２によって接続されている。また、複数のプロセッサはプロセッサ間同期管理部１０３に接続されている。プロセッサ０  １０１がプロセッサ間同期命令を実行すると、同期要求１０４がプロセッサ間同期管理部１０３に送られる。プロセッサ間同期管理部１０３は、すべてのプロセッサから同期要求を受信した時点で、プロセッサ０  １０１に同期完了１０５を送ると共に、他のすべてのプロセッサに対しても同期完了を送る。【００１０】
図２を参照すると、図１に示すプロセッサ間同期管理部１０３の１つの構成例が示されている。プロセッサ間同期管理部２０１にはカウンタ２０２が内蔵されており、初期値としてプロセッサ数Ｎ  ２０３が設定されている。プロセッサから同期要求２０４が送られてくるとカウンタ２０２を１ずつ減算していく。カウンタ２０２の値は比較器２０５でゼロと比較されており、カウンタ２０２の値がゼロになれば、その信号が同期完了送信部２０６に送られ、同期完了送信部２０６からＮ個のプロセッサに対して同期完了２０７を送信する。また、カウンタ２０２の値を初期値のＮ  ２０３にする。【００１１】
図３に、図１のプロセッサ間同期管理部１０３の動作を示す。図中、上から下へ時間が流れている。図３において、プロセッサ０  ３０１、プロセッサ１〜プロセッサＩ−１、プロセッサＩ  ３０４、プロセッサＩ＋１〜プロセッサＮ−１のＮ個のプロセッサがプロセッサ間同期管理部３０２に接続されている。プロセッサ０  ３０１からは同期要求３０３が送信され、他のプロセッサからも同期要求が送信され、最後にプロセッサＩ  ３０４がＮ個目の同期要求３０５を送信している。また、同期成立後、プロセッサ０  ３０１は、同期完了３０６を受信し、他のプロセッサも同期完了を受信している。ここで、プロセッサＩ  ３０４がプロセッサ間同期命令を実行し、最後の同期要求３０５を送信してから、その同期完了が到着するまでの時間はＴ  ３０７となっている。時間Ｔ  ３０７は、プロセッサ間同期管理部１０３など並列コンピュータの構成により、あらかじめ決定される値である。【００１２】
次に、図４のタイムチャートを用いて、すべてのプロセッサで行われる処理を説明する。まず、集団通信フェーズ４０１に入る前に関して説明を行う。集団通信フェーズに入る時間Ｔ前までの処理４０２を行う。残りの処理時間が時間Ｔになった時点で、プロセッサ間同期命令４０３を実行する。これにより、同期要求４０４が送信される。その後、時間Ｔ分の残りの処理４０５を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了４０６を受信するまで待つ  ４０７。プロセッサ間同期が成立すれば、集団通信フェーズ４０１に入る。【００１３】
集団通信フェーズ４０１では、部分通信フェーズの終了時間Ｔ前までの通信４０８を行う。その部分通信フェーズがあと時間Ｔで終了する時点で、プロセッサ間同期命令４０９を実行する。これにより、同期要求４１０が送信される。その後、時間Ｔ分の残りの部分通信フェーズの通信４１１を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了４１２を受信するまで待つ  ４１３。プロセッサ間同期が成立すれば、次の部分通信フェーズに入る。これを最後の部分通信フェーズまで、つまり、集団通信フェーズの終わりまで繰り返す。【００１４】
このように、実施例１では、プロセッサ間同期命令を先行して実行することにより、処理や通信とプロセッサ間同期をオーバラップすることができ、プロセッサ間同期にかかる時間を隠蔽することができる。その結果、集団通信を高速化することができる。【００１５】
図５に、時間Ｔ分の残りの処理や通信に実際にかかった時間が時間Ｔ以下の場合（（Ａ））と、時間Ｔより大きい場合（（Ｂ））の動きを示す。実際にかかった時間が時間Ｔ以下の場合（（Ａ））には、同期完了待ちの時間分がオーバヘッドとなる。一方、実際にかかった時間が時間Ｔより大きい場合（（Ｂ））には、最後に同期命令を実行したプロセッサＩ  ３０４だけが、次の部分通信フェーズに移る時点が遅れている  ５０１。つまり、次の部分通信フェーズとフェーズが重なる時間ができる。しかしながら、この重なりの時間はプロセッサ間同期にかかる時間に比べて小さいので、関連技術のようにプロセッサ間同期時間全体がオーバヘッドになる場合よりも性能劣化は少ない。【００１６】
〔実施例２〕
図６を参照すると、本発明による二つ目の実施例としての並列コンピュータが示されている。図６において、並列コンピュータは、プロセッサ０  ６０１、プロセッサ１〜プロセッサＮ−１の複数のプロセッサを有している。複数のプロセッサは、プロセッサ間ネットワーク６０２によって接続されている。また、複数のプロセッサはプロセッサ間同期管理部６０３に接続されている。プロセッサ０  ６０１がプロセッサ間同期にかかる時間Ｃを引数とするプロセッサ間同期命令を実行すると、同期要求（Ｃ）６０４がプロセッサ間同期管理部６０３に送られる。プロセッサ間同期管理部６０３は、すべてのプロセッサから同期要求（Ｃ）を受信した時点で、最後の同期要求（Ｃ）に付加されたＣとプロセッサ間同期管理部６０３を使った場合のプロセッサ間同期にかかる時間Ｔとの差だけ待ってから、プロセッサ０  ６０１に同期完了６０５を送ると共に、他のすべてのプロセッサに対しても同期完了を送る。【００１７】
従って、実施例２においては、プロセッサ間同期にかかる時間はＣとなる。時間Ｔは、実施例１と同じく、プロセッサ間同期管理部６０３などの並列コンピュータの構成により、あらかじめ決定できる値である。また、同期要求（Ｃ）６０４の引数であるＣは、プロセッサ間同期命令を実行するタイミングにより決定される値である。プロセッサ間同期命令は実行中の処理（演算または、通信）中に実行されるため、どのタイミングでプロセッサ間同期命令を実行するかは、実行中の処理に依存する。たとえば、Ｃの値はフェーズごとに異なる可能性がある。ただし、実施例２では、各プロセッサはほぼ同様の処理を行っていて、あるフェーズでの同期要求（Ｃ）６０４の引数Ｃはすべてのプロセッサで同じ値となることを仮定している。【００１８】
図７を参照すると、図６に示すプロセッサ間同期管理部６０３の１つの構成例が示されている。プロセッサ間同期管理部７０１にはカウンタ７０２が内蔵されており、初期値としてプロセッサ数Ｎ  ７０３が設定されている。プロセッサから同期要求（Ｃ）７０４が送られてくると、その遅延値Ｃを遅延値レジスタ７０５に格納し、カウンタ７０２を１ずつ減算していく。カウンタ７０２の値は比較器７０６でゼロと比較されており、カウンタ７０２の値がゼロになれば、その信号が遅延回路７０７に送られる。遅延回路７０７では、遅延値レジスタ７０５の値からプロセッサ間同期管理部７０１を使った場合のプロセッサ間同期にかかる時間Ｔを引いた値だけ、遅延させて、同期完了送信部７０８にカウンタ７０２がゼロになったことを伝える。そして、同期完了送信部７０８からＮ個のプロセッサに対して同期完了７０９を送信する。また、カウンタ７０２の値を初期値のＮ  ７０３にする。【００１９】
図８に、図６のプロセッサ間同期管理部６０３の動作を示す。図中、上から下へ時間が流れている。図８において、プロセッサ０  ８０１、プロセッサ１〜プロセッサＩ−１、プロセッサＩ  ８０４、プロセッサＩ＋１〜プロセッサＮ−１のＮ個のプロセッサがプロセッサ間同期管理部８０２に接続されている。プロセッサ０  ８０１からは同期要求（Ｃ）８０３が送信され、他のプロセッサからも同期要求（Ｃ）が送信され、最後にプロセッサＩ  ８０４がＮ個目の同期要求（Ｃ）８０５を送信している。図示するように、実施例２では、プロセッサ間同期管理部８０２でプロセッサ間同期にかかる時間をＴとすると、同期要求（Ｃ）８０５に指定された時間Ｃと時間Ｔの差である時間Ｃ−Ｔ  ８０６だけ、同期成立から遅延させている。遅延時間経過後、プロセッサ間同期管理部８０２は、プロセッサ０  ８０１へ同期完了８０７を送信し、他のプロセッサに対しても同期完了を送信している。最後の同期要求（Ｃ）８０５を発行したプロセッサＩ  ８０４がプロセッサ間同期命令を実行して、同期要求（Ｃ）８０５を送信し、その同期完了が到着するまでの時間はＣ  ８０８となる。【００２０】
次に、図９のタイムチャートを用いて、すべてのプロセッサで行われる処理を説明する。まず、集団通信フェーズ９０１に入る前に関して説明を行う。集団通信フェーズに入る時間Ｃ前までの処理９０２を行う。残りの処理時間が時間Ｃになった時点で、時間Ｃを指定してプロセッサ間同期命令９０３を実行する。これにより、同期要求（Ｃ）９０４が送信される。その後、時間Ｃ分の残りの処理９０５を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了９０６を受信するまで待つ  ９０７。プロセッサ間同期が成立すれば、集団通信フェーズ９０１に入る。【００２１】
集団通信フェーズ９０１では、部分通信フェーズの終了時間Ｃ前までの通信９０８を行う。その部分通信フェーズがあと時間Ｃで終了する時点で、時間Ｃを指定してプロセッサ間同期命令９０９を実行する。これにより、同期要求（Ｃ）９１０が送信される。その後、時間Ｃ分の残りの部分通信フェーズの通信９１１を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了９１２を受信するまで待つ９１３。プロセッサ間同期が成立すれば、次の部分通信フェーズに入る。これを最後の部分通信フェーズまで、つまり、集団通信フェーズの終わりまで繰り返す。【００２２】
図６の説明で述べたように、値Ｃはフェーズごとに異なる値になる可能性がある。つまり、集団通信フェーズ９０１に入る前の同期要求（Ｃ）９０４の値Ｃと、集団通信フェーズ９０１での同期要求（Ｃ）９１０の値Ｃとは異なる可能性がある。また、集団通信フェーズ９０１での同期要求（Ｃ）９１０もフェーズごとに処理が異なるのなら、フェーズごとにＣの値が異なる可能性もある。【００２３】
実施例２のプロセッサ間同期管理部は、プロセッサ間同期にかかる時間Ｃを指定できる。これにより、プロセッサ間同期にかかる時間Ｔに関係なく、プロセッサ間同期命令を実行するタイミングを、処理内容によって、任意に設定することが可能となる。【００２４】
〔実施例３〕
図１２を参照すると、本発明による三つ目の実施例としての並列コンピュータが示されている。図１２において、並列コンピュータは、プロセッサ０  １２０１、プロセッサ１  １２０２〜プロセッサＮ−１  １２０３の複数のプロセッサを有している。複数のプロセッサは、プロセッサ間ネットワーク１２０４によって接続されている。また、複数のプロセッサはプロセッサ間同期管理部１２０５に接続されている。プロセッサ０  １２０１がプロセッサ間同期にかかる時間Ｃ０を引数とするプロセッサ間同期命令を実行すると、同期要求（Ｃ０）１２０６がプロセッサ間同期管理部１２０５に送られる。プロセッサ１  １２０２がプロセッサ間同期にかかる時間Ｃ１を引数とするプロセッサ間同期命令を実行すると、同期要求（Ｃ１）１２０７がプロセッサ間同期管理部１２０５に送られる。プロセッサＮ−１  １２０３がプロセッサ間同期にかかる時間ＣＮ−１を引数とするプロセッサ間同期命令を実行すると、同期要求（ＣＮ−１）１２０８がプロセッサ間同期管理部１２０５に送られる。プロセッサ間同期管理部１２０５は、すべてのプロセッサから同期要求（Ｃ＃）を受信した時点で、最もプロセッサ間同期までにかかる時間が大きいプロセッサＪから送られてきたＣＪ’とプロセッサ間同期管理部１２０５を使った場合のプロセッサ間同期にかかる時間Ｔとの差ＣＪ’−Ｔだけ待ってから、プロセッサ０  １２０１に同期完了１２０９を送ると共に、他のすべてのプロセッサに対しても同期完了を送る。【００２５】
ここで、時間Ｔは、実施例１、実施例２と同じく、プロセッサ間同期管理部１２０５などの並列コンピュータの構成により、あらかじめ決定できる値である。また、実施例３では、同期要求（Ｃ０）１２０６、同期要求（Ｃ１）１２０７、同期要求（ＣＮ−１）１２０８の引数である、Ｃ０、Ｃ１、ＣＮ−１は、それぞれのプロセッサでの処理の中で、それぞれのプロセッサがプロセッサ間同期命令を実行するタイミングにより決まる値である。それぞれのプロセッサでの処理内容が異なる場合には、それぞれのプロセッサでプロセッサ間同期命令を実行するタイミングが異なり、Ｃ０、Ｃ１、ＣＮ−１の値が異なる可能性がある。さらに、同じプロセッサでもフェーズにより処理が異なる場合があり、フェーズごとにプロセッサ間同期命令の実行のタイミングが異なる可能性がある。【００２６】
図１３を参照すると、図１２に示すプロセッサ間同期管理部１２０５の１つの構成例が示されている。プロセッサ間同期管理部１３０１にはカウンタ１３０２が内蔵されており、初期値としてプロセッサ数Ｎ  １３０３が設定されている。また、プロセッサ間同期管理部１３０１には遅延値カウンタ１３０５があり、初期値として０  １３１０が設定されている。あるプロセッサＫから同期要求（ＣＫ）１３０４が送られてくると、その遅延値ＣＫと遅延値カウンタ１３０５の値を比較器１３１１で比較し、「ＣＫ＞遅延値カウンタ１３０５の値」の場合には、遅延値ＣＫを遅延値カウンタ１３０５に格納する。「ＣＫ＞遅延値カウンタ１３０５の値」でない場合は遅延値カウンタ１３０５を書き換えない。そして、カウンタ１３０２を１減算する。ここで、遅延値カウンタ１３０５の値は時間の経過により０になるまでカウントダウンされる。一方、カウンタ１３０２の値は比較器１３０６でゼロと比較されており、Ｎ個のプロセッサすべてから同期要求が到着し、カウンタ１３０２の値がゼロになれば、その信号が遅延回路１３０７に送られる。遅延回路１３０７では、その時点での遅延値カウンタ１３０５の値ＣＪ’から、この並列コンピュータでプロセッサ間同期を行った場合のプロセッサ間同期にかかる時間Ｔを引いた値（ＣＪ’−Ｔ）だけ、遅延させて、同期完了送信部１３０８にカウンタ１３０２がゼロになったことを伝える。そして、同期完了送信部１３０８からＮ個のプロセッサに対して同期完了１３０９を送信する。また、カウンタ１３０２の値を初期値のＮ  １３０３に、かつ、遅延値カウンタの値を初期値の０  １３１０にする。【００２７】
図１４に、図１３のプロセッサ間同期管理部１３０１の動作を示す。図中、上から下へ時間が流れている。図１４において、Ｎ個のプロセッサ、すなわち、プロセッサ０  １４０１、プロセッサ１  １４０２、…、プロセッサＮ−１  １４０４がプロセッサ間同期管理部１４０５に接続されている。プロセッサ０  １４０１、プロセッサ１  １４０２、…、プロセッサＮ−１  １４０４からは、それぞれ、同期要求（Ｃ０）１４０６、同期要求（Ｃ１）１４０７、…、同期要求（ＣＮ−１）１４０８が送信され、最後にプロセッサＩ  １４０３がＮ個目の同期要求（ＣＩ）１４０９を送信している。ここで、プロセッサ間同期管理部１４０５内の遅延値カウンタのその時点での値をＣＪ’（時間の経過によりＣＪからカウントダウンされた値）とし、この並列コンピュータでプロセッサ間同期にかかる時間をＴとすると、プロセッサ間同期管理部１４０５は、ＣＪ’とＣＩとの大きい方から時間Ｔを引いた値だけ遅延時間を設ける。プロセッサ間同期管理部１４０５は、最後の同期要求（ＣＩ）１４０９に指定された時間ＣＩと、遅延値カウンタのその時点での値ＣＪ’とを比較する。「ＣＩ  ＜  ＣＪ’」であった場合、図示するように、プロセッサ間同期管理部１４０５は、ＣＪ’から時間Ｔを引いた値だけ遅延時間を設ける。遅延時間経過後、プロセッサ間同期管理部１４０５は、プロセッサ０  １４０１へ同期完了１４１１を送信し、他のプロセッサに対しても同期完了を送信する。プロセッサＪが遅延値ＣＪの同期要求（ＣＪ）を送信してから、同期完了がプロセッサＪに到着するまでの時間はＣＪとなる。【００２８】
次に、図１５のタイムチャートを用いて、すべてのプロセッサで行われる処理を説明する。ここではプロセッサＫとして説明する。まず、集団通信フェーズ１５０１に入る前に関して説明を行う。集団通信フェーズに入る時間ＣＫ前までの処理１５０２を行う。集団通信フェーズに入るまでの残りの処理時間が時間ＣＫになった時点で、時間ＣＫを指定してプロセッサ間同期命令１５０３を実行する。これにより、同期要求（ＣＫ）１５０４が送信される。その後、時間ＣＫ分の残りの処理１５０５を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了１５０６を受信するまで待つ  １５０７。プロセッサ間同期が成立すれば、集団通信フェーズ１５０１に入る。【００２９】
集団通信フェーズ１５０１では、部分通信フェーズの終了の時間ＣＫ前までの通信１５０８を行う。その部分通信フェーズがあと時間ＣＫで終了する時点で、時間ＣＫを指定してプロセッサ間同期命令１５０９を実行する。これにより、同期要求（ＣＫ）１５１０が送信される。その後、時間ＣＫ分の残りの部分通信フェーズの通信１５１１を行う。そして、プロセッサ間同期が成立するまで、つまり、同期完了１５１２を受信するまで待つ  １５１３。プロセッサ間同期が成立すれば、次の部分通信フェーズに入る。これを最後の部分通信フェーズまで、つまり、集団通信フェーズの終わりまで繰り返す。【００３０】
実施例３のプロセッサ間同期管理部は、プロセッサ間同期にかかる時間ＣＫをプロセッサごとに指定できる。これにより、並列コンピュータにおけるプロセッサ間同期にかかる時間Ｔに関係なく、プロセッサ間同期命令を実行する時刻をプロセッサごとに任意に設定することが可能となる。図１２の説明で述べたように、値ＣＫはフェーズごとに異なる値になる可能性がある。つまり、集団通信フェーズ１５０１に入る前の同期要求（ＣＫ）１５０４の値ＣＫと、集団通信フェーズ１５０１での同期要求（ＣＫ）１５１０の値ＣＫは異なる可能性がある。また、集団通信フェーズ１５０１での同期要求（ＣＫ）１５１０もフェーズごとに処理が異なるのなら、フェーズごとにＣＫの値が異なる可能性もある。【００３１】
〔実施例１〜３の効果〕
実施例１〜３では、プロセッサ間同期命令を先行して実行しているので、処理や通信とプロセッサ間同期をオーバラップすることができ、プロセッサ間同期にかかる時間を隠蔽することができる。その結果、集団通信を高速化することができる。【００３２】
すなわち、実施例１〜３の一つの効果は、集団通信のフェーズに入る時刻や部分通信フェーズに入る時刻を集団通信に参加している全プロセッサで合わせるときのオーバヘッドとなっていたプロセッサ間同期の時間が削減され、集団通信が高速に行えることである。その理由は、時刻あわせに必要であったプロセッサ間同期をそれに要する時間分先行して行って、集団通信フェーズの直前の処理や、部分通信フェーズの直前の通信を、プロセッサ間同期とオーバラップさせて実行することにより、プロセッサ間同期にかかる時間を隠蔽しているからである。【００３３】
本来のプロセッサ間同期では、処理が同期点に到達していること、つまり、同期点以前の処理が完了していることを保証する必要がある。一方、実施例１〜３のプロセッサ間同期では、各プロセッサが次のフェーズに入る時刻をできるだけ合わせることが目標であり、場合によっては、プロセッサ間同期が成立した時点で、すべてのプロセッサの処理が完了していること、すなわち、次のフェーズに入れることを必ずしも保証するものではない。従って、あるプロセッサは次のフェーズに入る時刻が他のプロセッサよりも少し遅れる可能性があり得る。しかし、遅れる時間は短く、上記関連技術のようにプロセッサ間同期にかかる時間全体がオーバヘッドになる場合に比べて性能劣化は非常に少ないと考えられる。【００３４】
図１０に、特許第２６０１５９１号公報に記載の関連技術における集団通信のタイムチャートを示す。関連技術では、集団通信フェーズ１００３に入る前の処理１００１の後、集団通信フェーズ１００３の部分通信フェーズ１  １００４の前にプロセッサ間同期１００２を行って、部分通信フェーズ１  １００４を開始する時刻を合わせている。【００３５】
図１１に、実施例１〜３における通信のタイムチャートを示す。図中、プロセッサ間同期１１０３の時間が処理１１０１にオーバラップしている。プロセッサ間同期は、部分通信フェーズ１  １１０２の通信の時間にもオーバラップしている。図示されるように、集団通信が高速化されている。【００３６】
本発明の活用例として、大規模な並列コンピュータで、プロセッサ間同期の処理に時間がかかる場合などがあげられる。【００３７】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解しうる様々な変更をすることができる。
【図１】
2009028231.tif 000003
【図２】
2009028231.tif 000004
【図３】
2009028231.tif 000005
【図４】
2009028231.tif 000006
【図５】
2009028231.tif 000007
【図６】
2009028231.tif 000008
【図７】
2009028231.tif 000009
【図８】
2009028231.tif 000010
【図９】
2009028231.tif 000011
【図１０】
2009028231.tif 000012
【図１１】
2009028231.tif 000013
【図１２】
2009028231.tif 000014
【図１３】
2009028231.tif 000015
【図１４】
2009028231.tif 000016
【図１５】
2009028231.tif 000017
【手続補正書】
【提出日】平成20年10月21日(2008.10.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のプロセッサと、
前記複数のプロセッサを接続するプロセッサ間ネットワークと、
前記複数のプロセッサの間でプロセッサ間同期をとるためのプロセッサ間同期管理部と
を有する並列コンピュータにおける通信方法であって、
（１ａ）前記複数のプロセッサにおける各プロセッサが、前記プロセッサ間ネットワークを介して、プロセッサ間で同時に通信を行う集団通信フェーズに入る手前の処理をそれぞれ開始することと、
（１ｂ）前記手前の処理を、所定時間ｔ１ぶんだけ残した時点で、前記各プロセッサが、同期命令を先行してそれぞれ実行することと、
（１ｃ）前記同期命令の実行では、前記各プロセッサが、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出することと、
（１ｄ）前記プロセッサ間同期管理部が、前記各プロセッサからそれぞれ前記同期要求を受信することと、
（１ｅ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記プロセッサ間同期管理部が、前記複数のプロセッサへそれぞれ同期完了を送信することと、
（１ｆ）前記各プロセッサが、前記同期完了をそれぞれ受信することと、
（１ｇ）前記各プロセッサが、前記（１ｂ）〜（１ｆ）と並行して、前記手前の処理を実行することと、
（１ｈ）前記（１ｇ）を行った後、前記同期完了の受信を確認後、前記複数のプロセッサが、前記集団通信フェーズに入ることとを備える
通信方法。
【請求項２】
前記所定時間ｔ１として、
前記並列コンピュータの構成により、予め決定される時間であって、
前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲１記載の通信方法。
【請求項３】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ１として、
前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲１記載の通信方法。
【請求項４】
前記（１ｅ）は、
前記最後に前記同期命令を実行するプロセッサが、前記手前の処理に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記プロセッサ間同期管理部は、前記複数のプロセッサへそれぞれ同期完了を送信することを備える
請求の範囲３記載の通信方法。
【請求項５】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ１として、
前記各プロセッサがそれぞれ行う前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲１記載の通信方法。
【請求項６】
前記（１ｅ）は、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記プロセッサ間同期管理部が、前記複数のプロセッサへ前記同期完了をそれぞれ送信することを備える
請求の範囲５記載の通信方法。
【請求項７】
（２ａ）複数の部分通信フェーズに分かれる集団通信フェーズに入ることと、
（２ｂ）前記複数の部分通信フェーズの中の一つの部分通信フェーズに入ることと、
（２ｃ）前記複数のプロセッサにおける各プロセッサが、前記複数のプロセッサにおける他のプロセッサと１対１の通信を行う部分通信をそれぞれ開始することと、
（２ｄ）前記部分通信を、所定時間ｔ２ぶんだけ残した時点で、前記各プロセッサが、同期命令を先行してそれぞれ実行することと、
（２ｅ）前記同期命令の実行では、前記各プロセッサが、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出することと、
（２ｆ）前記プロセッサ間同期管理部が、前記各プロセッサからそれぞれ前記同期要求を受信することと、
（２ｇ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記プロセッサ間同期管理部が、前記複数のプロセッサへそれぞれ同期完了を送信することと、
（２ｈ）前記各プロセッサが、前記同期完了をそれぞれ受信することと、
（２ｉ）前記各プロセッサが、前記（２ｄ）〜（２ｈ）と並行して、前記部分通信を継続して実行することと、
（２ｊ）前記（２ｉ）を行った後、前記同期完了の受信を確認後、前記複数のプロセッサが、次の部分通信フェーズに入ることとを更に備える
請求の範囲１記載の通信方法。
【請求項８】
前記所定時間ｔ２として、
前記並列コンピュータの構成により、予め決定される時間であって、
前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲７記載の通信方法。
【請求項９】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ２として、
前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲７記載の通信方法。
【請求項１０】
前記（２ｇ）は、
前記最後に前記同期命令を実行するプロセッサが、前記部分通信に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記プロセッサ間同期管理部は、前記複数のプロセッサへそれぞれ同期完了を送信することを備える
請求の範囲９記載の通信方法。
【請求項１１】
前記並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ２として、
前記各プロセッサがそれぞれ行う前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲７記載の通信方法。
【請求項１２】
前記（２ｇ）は、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記プロセッサ間同期管理部が、前記複数のプロセッサへ前記同期完了をそれぞれ送信することを備える
請求の範囲１１記載の通信方法。
【請求項１３】
複数のプロセッサと、
前記複数のプロセッサを接続するプロセッサ間ネットワークと、
前記複数のプロセッサの間でプロセッサ間同期をとるためのプロセッサ間同期管理部とを有し、
前記複数のプロセッサにおける各プロセッサは、
（３ａ）前記プロセッサ間ネットワークを介して、プロセッサ間で同時に通信を行う集団通信フェーズに入る手前の処理をそれぞれ開始し、
（３ｂ）前記手前の処理を、所定時間ｔ３ぶんだけ残した時点で、同期命令を先行してそれぞれ実行し、
（３ｃ）前記同期命令の実行では、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出し、
前記プロセッサ間同期管理部は、
（３ｄ）前記各プロセッサからそれぞれ前記同期要求を受信し、
（３ｅ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記複数のプロセッサへそれぞれ同期完了を送信し、
前記各プロセッサは、更に、
（３ｆ）前記同期完了をそれぞれ受信し、
（３ｇ）前記（３ｂ）〜（３ｆ）と並行して、前記手前の処理を実行し、
前記複数のプロセッサは、
（３ｈ）前記（３ｇ）が行われた後、前記同期完了の受信を確認後、前記集団通信フェーズに入る
並列コンピュータ。
【請求項１４】
前記各プロセッサは、
前記所定時間ｔ３として、
請求の範囲１３記載の並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲１３記載の並列コンピュータ。
【請求項１５】
前記各プロセッサは、
請求の範囲１３記載の並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ３として、
前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲１３記載の並列コンピュータ。
【請求項１６】
前記プロセッサ間同期管理部は、
前記（３ｅ）を行う場合に、
前記最後に前記同期命令を実行するプロセッサが、前記手前の処理に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記複数のプロセッサへそれぞれ同期完了を送信する
請求の範囲１５記載の並列コンピュータ。
【請求項１７】
前記各プロセッサは、
請求の範囲１３記載の並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ３として、
前記各プロセッサがそれぞれ行う前記手前の処理に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲１３記載の並列コンピュータ。
【請求項１８】
前記プロセッサ間同期管理部は、
前記（３ｅ）を行う場合に、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記複数のプロセッサへ前記同期完了をそれぞれ送信する
請求の範囲１７記載の並列コンピュータ。
【請求項１９】
前記複数のプロセッサは、
（４ａ）複数の部分通信フェーズに分かれる集団通信フェーズに入り、
（４ｂ）前記複数の部分通信フェーズの中の一つの部分通信フェーズに入り、
前記複数のプロセッサにおける各プロセッサは、
（４ｃ）前記（４ｂ）の後、前記複数のプロセッサにおける他のプロセッサと１対１の通信を行う部分通信をそれぞれ開始し、
（４ｄ）前記部分通信を、所定時間ｔ４ぶんだけ残した時点で、同期命令を先行してそれぞれ実行し、
（４ｅ）前記同期命令の実行では、前記プロセッサ間同期管理部へ、同期要求をそれぞれ送出し、
前記プロセッサ間同期管理部は、
（４ｆ）前記各プロセッサからそれぞれ前記同期要求を受信し、
（４ｇ）前記複数のプロセッサの全てから前記同期要求を受信して、同期条件が成立したならば、前記複数のプロセッサへそれぞれ同期完了を送信し、
前記各プロセッサは、更に、
（４ｈ）前記同期完了をそれぞれ受信し、
（４ｉ）前記（４ｄ）〜（４ｈ）と並行して、前記部分通信を継続して実行し、
前記複数のプロセッサは、更に、
（４ｊ）前記（４ｉ）が行われた後、前記同期完了の受信を確認後、次の部分通信フェーズに入る
請求の範囲１３記載の並列コンピュータ。
【請求項２０】
前記各プロセッサは、
前記所定時間ｔ４として、
請求の範囲１９記載の並列コンピュータの構成により、予め決定される時間であって、
前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間のＴを用いる
請求の範囲１９記載の並列コンピュータ。
【請求項２１】
前記各プロセッサは、
請求の範囲１９記載の並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ４として、
前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣを用いる
請求の範囲１９記載の並列コンピュータ。
【請求項２２】
前記プロセッサ間同期管理部は、
前記（４ｇ）を行う場合に、
前記最後に前記同期命令を実行するプロセッサが、前記部分通信に依存して、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記Ｃと同じ時間になるように、前記複数のプロセッサへそれぞれ同期完了を送信する
請求の範囲２１記載の並列コンピュータ。
【請求項２３】
前記各プロセッサは、
請求の範囲１９記載の並列コンピュータの構成により、予め決定される時間であって、前記複数のプロセッサの中で、最後に前記同期命令を実行するプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間をＴとした場合に、
前記所定時間ｔ４として、
前記各プロセッサがそれぞれ行う前記部分通信に依存して、前記同期命令を実行するタイミングにより決定される時間であって、
前記Ｔと同じ又は前記Ｔよりも大きな値のＣＪを用い、
前記ＣＪは、前記複数のプロセッサにおけるＪ番目のプロセッサの場合の時間であり、
前記複数のプロセッサの数がＮのとき、Ｊ＝０，１，・・・，Ｎ−１であり、ＣＪ＝Ｃ０，Ｃ１，・・・，ＣＮ−１である
請求の範囲１９記載の並列コンピュータ。
【請求項２４】
前記プロセッサ間同期管理部は、
前記（４ｇ）を行う場合に、
前記複数のプロセッサの中で、前記同期命令を実行した時刻に、前記ＣＪを加えた時刻が最も遅いものがＫ番目のプロセッサであった場合、前記Ｋ番目のプロセッサが、前記同期命令を実行してから、前記同期完了を受信するまでの時間が、前記ＣＪ（但し、Ｊ＝Ｋとする。）と同じ時間になるように、前記複数のプロセッサへ前記同期完了をそれぞれ送信する
請求の範囲２３記載の並列コンピュータ。
【国際調査報告】
2009028231.tif 000018
2009028231.tif 000019
2009028231.tif 000020
2009028231.tif 000021