JP2012128809A - 並列計算機システム、同期装置、並列計算機システムの制御方法 - Google Patents

Abstract

【課題】バリア同期において、複数のノードの間における同期の成立のばらつきを低減した並列計算機システムを提供する。
【解決手段】遅延部６２４は、データを所定時間だけ遅延させる。制御部６２１は、受信装置６１が抽出した同期情報と自制御部６２１からの同期情報を、制御レジスタ６２２に保持する。制御部６２１は、制御レジスタ６２２に受信装置６１が抽出した同期情報と自制御部６２１からの同期情報が揃った場合に、他ノードへのデータを送信装置６３に送信させ、自ノードへのデータを、遅延部６２４を介して自制御部６２１へ戻す。
【選択図】図３

Description

本発明は、並列計算機システム、同期装置、並列計算機システムの制御方法に関する。

並列計算機システムにおいて、複数のノード間で並列処理されている複数のプロセス間の同期をとる方法として、バリア同期が知られている。バリア同期では同期を取るポイント、つまりバリアポイントがプロセスの処理の進行段階（ステージ）に応じて設定され、バリア同期を行なうプロセスはバリアポイントにプロセスの処理が到達した場合、プロセスの処理を一時的に停止することにより他のノードにおけるプロセスの処理の進行を待ち合わせる。バリア同期を行なうプロセスは、バリア同期を行なう、並列処理されている全てのプロセスがバリアポイントに到着した時点で、待ち合わせ状態を終了して停止した処理を再開する。これにより、複数のノード間で並列処理されている複数のプロセス間で、並列処理の同期をとることができる。

バリア同期装置においては、バリア同期を実行する際、アルゴリズムによっては、プロセスはバリアポイントに到着した旨の信号又はメッセージ（バリア同期メッセージ）の送信先をステージ毎に変更する必要がある。そこで、バリア同期における送信先変更処理をハードウェアによって実現するバリア同期装置が提案されている。このバリア同期装置によれば、ステージ毎のＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の介在をなくし、バリア同期の高速化を実現することができる。更に、このバリア同期装置においては、複数組の信号又はメッセージの同期をとる同期部が設けられる。これにより、複数のノードをネットワークにより接続する場合においてノード間のネットワークの構成が限定されないようにして、高速でバリア同期を実行することができる。

なお、ノード内バリア同期機構が、自装置内に設けたＣＰＵからの同期リクエストに基づいて自装置内でのバリア同期が成立したことを検出すると共に、この自装置内でのバリア同期成立の情報を、並列処理を実行する全ノード装置に通知し、一方、ノード間バリア同期機構２２０ａは、この並列処理を実行する他のノード装置から通知される他装置内でのバリア同期成立の情報に基づいて、並列処理が完了したことを検出し、バリア同期機構の複雑化を招かずしかも特別な通信機構を設けずに、自装置内でのバリア同期成立の情報を送受信することによって並列処理の完了を検出することが提案されている。

特開２０１０−１２２８４８号公報 特開２００１−０５１９６６号公報

並列計算機システムにおいては、システム全体に含まれる複数のノード間の時刻合わせ処理のため、グローバルクロックが用いられる。複数のノード間で同期したグローバルクロックを実現するため、バリア同期装置を用いることが考えられる。すなわち、ステージ毎のＣＰＵの介在をなくしてバリア同期を高速化したバタフライアルゴリズムによるバリア同期装置を用いて、バリア同期装置である各ノード間で同期したグローバルクロックを実現することが考えられる。しかし、ステージ毎のＣＰＵの介在をなくしてバリア同期を高速化したバタフライアルゴリズムによるバリア同期においては、各プロセスからの同期メッセージの到着時期のばらつきにより、複数のノード間において、同期の成立がばらつく。この複数のノード間における同期の成立のばらつきにより、グローバルクロックにおいては各ノードのグローバルクロック間に位相差が生じることになる。このため、ステージ毎のＣＰＵの介在をなくしてバリア同期を高速化したバタフライアルゴリズムによるバリア同期装置を用いてグローバルクロックを実現する場合には、複数のノード間における同期の成立のばらつきを低減する必要がある。

本発明は、バリア同期において、複数のノードの間における同期の成立のばらつきを低減した並列計算機システムを提供することを目的とする。

開示の並列計算機システムは、複数のノードを有する並列計算機システムである。複数のノードは、受けるデータの待ち合わせを行ない、待ち合わせたデータが揃った場合にデータを送信することにより同期を行う同期装置をそれぞれ備える。複数の同期装置の各々は、受信部と、送信部と、受信状態レジスタと、遅延部と、制御部とを含む。受信部は、複数の同期装置のうち、自ノードと同期を行う他ノードの同期装置からのデータを受信し、受信した他ノードの同期装置からのデータから同期情報を抽出する。送信部は、複数の同期装置のうち、自ノードと同期を行う他ノードの同期装置へのデータを送信する。送信部と、受信状態レジスタは、抽出した同期情報を保持する。遅延部は、データを所定時間だけ遅延させる。制御部は、受信部が抽出した同期情報と自制御部からの同期情報を、受信状態レジスタに保持するとともに、受信状態レジスタに受信部が抽出した同期情報と自制御部からの同期情報が揃った場合に、他ノードへのデータを送信部に送信させ、自ノードへのデータを、遅延部を介して自制御部へ戻す。

開示の並列計算機システムによれば、バリア同期において、複数のノードの間における同期の成立のばらつきをほぼ無くすことができ、ステージ毎のＣＰＵの介在をなくしてバリア同期を高速化したバタフライアルゴリズムによるバリア同期装置を用いてグローバルクロックを実現することができる。

並列計算機システムの構成の一例を示す図である。 バリア同期装置を含むノードの構成の一例を示す図である。 バリア同期装置の構成の一例を示す図である。 遅延計算の一例の説明図である。 パケットのフォーマットを示す図である。 遅延部の構成の一例を示す図である。 遅延部の構成の他の一例を示す図である。 バリア同期実行時の処理フローチャートである。 バタフライによるバリア同期での信号の流れを示す図である。 リダクション演算装置を含むノードの構成の一例を示す図である。 リダクション演算装置の構成の一例を示す図である。 リダクション演算実行時の処理フローチャートである。 リダクション演算実行時の処理フローチャートである。 バリア同期装置を含むノードの構成の他の一例を示す図である。 バリア同期装置を含むノードの構成の更に他の一例を示す図である。 バリア同期の概要を示す説明図である。 ４個のプロセスでのバタフライによるバリア同期の例を示す図である。 リダクション演算の概要を示す説明図である。 同期の成立の遅延時間について検討した図である。

最初に、バリア同期と、リダクション演算とについて簡単に説明する。

バリア同期においては、図１６に示すように、バリア同期を行なう複数のプロセス＃０〜＃３の各々は、その処理が同期をとるポイントつまりバリアポイントに到着した場合、自身の処理を停止する。即ち、複数のプロセス＃０〜＃３の各々は処理がバリアポイントに到達した場合、他のプロセスがバリアポイントに到着するのを待ち合わせる。複数のプロセス＃０〜＃３は、各々、バリア同期を行なう全てのプロセス＃０〜＃３がバリアポイントに到着した時点で、即ち、バリア同期が成立した時点で、待ち合わせ状態を解除し、停止した処理を再開する。これにより、並列処理されている複数のプロセス間で、並列処理の同期をとることができる。

このようなバリア同期を実現するアルゴリズムの一つに、バタフライ演算がある。以下、バタフライ演算を単に「バタフライ」と称する。バタフライにおいては、処理を複数のステージに分割し、ステージ毎に他のプロセスとバリア同期メッセージの通信を行なう。この例においては、バリア同期のアルゴリズムとして、バタフライが用いられる。

図１７（Ａ）は、４個のプロセス＃０〜＃３の間において、バタフライによるバリア同期を行なう例を示す。図１７（Ａ）における個々のプロセスは、図１７（Ｂ）に示すように表される。図１７（Ｂ）において、左上の数字は送信元プロセスを表し、左下の数字は送信元プロセスを表し、中央の数字は自プロセスを表し、右上の数字は送信先プロセス又は宛先プロセスを表し、右下の数字は送信先プロセス又は宛先プロセスを表す。プロセスは、プロセスを識別する識別情報であるプロセス番号で表される。

各々のステージにおけるバリアポイントに到着した旨を表すバリア同期メッセージ（以下、単に「メッセージ」と省略する場合がある）の送信先は、ステージ番号をｋ、自プロセス又は自ノード１のプロセス番号をｉとすると、ｉ ＸＯＲ ２＾（ｋ−１）となる。ＸＯＲは、排他的論理和演算を表す。ステージ数は、プロセス数Ｎが２のべき乗のとき、ｌｏｇ（Ｎ）となる。

図１８（Ａ）は、４個のプロセス＃０〜＃３の間において、バタフライによるバリア同期を利用してリダクション演算を行なう例を示す。リダクション演算は、図１７（Ａ）に示すバタフライによるバリア同期を利用して実行される。従って、図１８（Ａ）は、基本的には、図１７（Ａ）と同様の処理の流れを示す。

図１８（Ａ）における個々のプロセスは、図１８（Ｂ）に示すように表される。図１８（Ｂ）は、基本的には図１７（Ｂ）と同様の記号を表すが、さらに、リダクション演算の演算途中データを含む点のみが図１７（Ｂ）と異なる。図１８（Ｂ）において、中央の自プロセスを表すプロセス番号の下部に、演算途中データが示される。バリアポイント到着時のデータ及びバリア同期成立時のデータも、演算途中データとして表される。

以下、主として、バタフライによるバリア同期について説明する。

例えば、図１７（Ａ）において、プロセス＃０に着目すると、以下のように送信先が予め定められる。即ち、ステージ＃１において、バリアポイント到着を示すメッセージの送信先はプロセス＃１である。ステージ＃２において、プロセス＃０からのバリアポイント到達を示すメッセージの受信元はプロセス＃１であり、プロセス＃０からのバリアポイント到達を示すメッセージの送信先はプロセス＃２である。

これらのメッセージの送信先及び受信元は、設定条件において、バリア同期のアルゴリズム及び実行条件つまりプロセスの構成が定まることにより、一意に定めることができる。この例においては、バリア同期のアルゴリズムはバタフライであり、実行条件は４個のプロセスであるので、前述したように定めることができる。

各プロセスは、ステージ毎に他のプロセスとの間で同期メッセージを通信し合う。例えば、最初のステージ＃１において、各プロセスは、バリア同期ポイントに到着する。到着のタイミングは、各プロセスで異なる。この場合、各プロセスは、バタフライネットワーク上における次ステージの予め設定されたプロセスに同期メッセージを送る。

次のステージ＃２において、各プロセスは、バタフライネットワークの前のステージ＃１の予め設定されたプロセスからの同期メッセージを待ち合わせる。各プロセスは、他のプロセスから同期メッセージを受信した場合、次のステージ＃３の予め設定されたプロセスに同期メッセージを送る。

最後のステージ＃３において、各プロセスは、前ステージ＃２の予め設定されたプロセスからの同期メッセージを待ち合わせる。各プロセスが他のプロセスからの同期メッセージを受けると、全てのプロセス＃０〜＃３がバリアポイントに到着した後にバリア同期が成立した事を知る。この後、各プロセスは、バリア同期が成立したので、次の処理を開始する。

なお、リダクション演算においては、同期メッセージに代えて、同期メッセージ及びリダクション演算の演算対象である演算途中データが、各プロセスの間において送受信され、待ち合わせられる。演算途中データを受信したプロセスは、リダクション演算を実行して、リダクション演算により算出したデータを演算途中データとする。バリア同期の成立により、リダクション演算も完了する。

ここで、図１９に示すように、４個のプロセス＃０〜＃３の各々が、異なる４個のノード１０１の上でそれぞれ動作しているとする。この場合において、例えばノード＃０上で動作するプロセス＃０に着目すると、プロセス＃０のステージ＃２は、自ノード＃０のステージ＃１からの同期メッセージと、他ノード＃１のステージ＃１からの同期メッセージとを、受信する。

自ノード＃０のステージ＃１からの同期メッセージは、例えばノード＃０のバリア同期装置１０６内で送受信されるので、異なるノード間で同期メッセージを送受信する場合よりも短時間でプロセス＃０のステージ＃２に到達する。一方、他ノード＃１のステージ＃１からの同期メッセージは、自ノード＃０と他ノード＃１との間を、ネットワーク１０２を介して送受信されるので、自ノード＃０のステージ＃１からの同期メッセージよりも遅れてプロセス＃０のステージ＃２に到達する。他のノード１０１の他のステージについても、ネットワーク１０２を経由する同期メッセージは、バリア同期装置１０６内で送受信される同期メッセージに対して遅れる。従って、複数のノード＃０〜＃３の各ステージの間において、各プロセスからの同期メッセージの到着時間がばらつくことにより、同期の成立が各ノード間でばらつき、このばらつきがグローバルクロックにおいて位相差を生じる原因となる。

開示の並列計算機システム、同期装置、並列計算機システムの制御方法は、バリア同期において、複数のノードの間における同期の成立のばらつきをほぼ無くす。

図１は、バリア同期装置を含むノードを複数有するコンピュータネットワーク、換言すれば、並列計算機システムの構成の一例を示す。

並列計算機システムは、複数のノードつまりコンピュータ１と、これらのノードを接続するネットワーク２とを含む。図１の例においては、４個のノード＃０〜ノード＃３が並列計算機システムに設けられる。複数のノード１は、例えば、相互結合網であるネットワーク２を介して、相互に接続される。ネットワーク２により接続された複数のノード１は、並列演算を実行する。複数のノード１は、各々、並列演算におけるバリア同期のために、バリア同期装置６を含む。換言すれば、並列計算機システムは、複数のバリア同期装置６を含む。バリア同期装置６は高速でバリア同期を行う。

図１の並列計算機システムは、複数のノード１が相互に接続される一例として、ノード＃０が、ノード＃１〜ノード＃３の各々と接続された状態を示す。また、図１においては、個々のノード１が、ＣＰＵ３とバリア同期装置６とを含むことを、模式的に表している。

図２は、バタフライによりバリア同期を行うバリア同期装置を含むノードの構成の一例を示す。

ノード１は、ＣＰＵ３と、メモリ４と、システム制御部５と、バリア同期装置６と、ＩＯ（Ｉｎｐｕｔ Ｏｕｔｐｕｔ）インタフェース部７と、ネットワークインタフェース部９とを含む。システム制御部５はノード１を制御する。即ち、システム制御部５は、ＣＰＵ３、メモリ４、バリア同期装置６、ＩＯ（Ｉｎｐｕｔ Ｏｕｔｐｕｔ）装置１１を制御する。ＣＰＵ３は、設定処理部３１を含む。システム制御部５は、ＩＯインタフェース部７を介して、ＩＯ装置１１に接続される。ＩＯインタフェース部７は、システム制御部５に設けられるようにしても良い。バリア同期装置６は、ネットワークインタフェース部９を介して、ネットワーク２に接続される。ネットワークインタフェース部９は、バリア同期装置６に設けられるようにしても良い。

設定処理部３１は、システム制御部５及びＩＯインタフェース部７を介して、ＩＯ装置１１との間において、必要なデータの送受信を行う。これにより、ＩＯ装置１１は、バリア同期のアルゴリズムと実行条件とを含む設定条件を、ＣＰＵ３の設定処理部３１に入力する。また、ＩＯ装置１１は、必要に応じて、設定処理部３１から出力されたデータを出力する。

設定処理部３１は、システム制御部５を介して、バリア同期装置６に対してバリアポイント到達のメッセージを送信し、また、バリア同期装置６からバリア同期成立のメッセージを受信する。これにより、設定処理部３１は、ＩＯ装置１１から入力された設定条件に従って、バリア同期装置６における第１のバリア同期メッセージの送信先及び第２のバリア同期メッセージの送信先を、バリア同期装置６に設定する。バリア同期装置６は、設定条件に従って、ネットワーク２及びネットワークインタフェース部９を介して、他ノード１のバリア同期装置６との間で通信を行ない、当該通信に基づいて、バリア同期を行なう。

バリア同期装置６は、バタフライによるバリア同期を実行する。換言すれば、バリア同期装置６は、受けるデータの待ち合わせを行ない、前記待ち合わせたデータが揃った場合にデータを送信することにより同期を行う。具体的には、図１の並列計算機システムにおいて、複数のバリア同期装置６のうち、同期を行う第１の複数のバリア同期装置６の組の各々の間で、同期が実行される。更に、第１の複数の同期装置の組の各々の間で同期を完了した後、第１の複数の同期装置の組とは異なる第２の複数のバリア同期装置６の組の各々の間で、同期が実行される。

ＣＰＵ３は、システム制御部５を介して、メモリ４との間において、必要なデータの送受信を行う。これにより、ＣＰＵ３は、メモリ４にデータを書き込み、また、設定制御部３１はメモリ４からデータを読み出す。このデータは、例えば、後述するリダクション演算に用いられるデータである。

図３は、バリア同期装置の構成の一例を示す。

バリア同期装置６は、受信装置６１と、同期装置６２と、送信装置６３とを含む。従って、並列計算機システムは、複数の同期装置６２を含む。同期装置６２は、バリア同期装置６の主要部であるが、バリア同期装置６と区別するために、以下の説明においては、「同期部６２」と言うこととする。

同期部６２は、制御部６２１と、複数の制御レジスタ６２２と、ループ経路６２３と、遅延部６２４とを含む。制御部６２１は、チェック回路６２１１と、シーケンス回路６２１２と、レジスタアクセス回路６２１３と、遅延計算回路６２１４とを含む。複数の制御レジスタ６２２の各々は、後述するように、更に、図３に示す、複数のレジスタを含むレジスタ群である。

ループ経路６２３は、制御部６２１から送信された自ノード１へのデータを制御部６２１へ戻す通信経路である。遅延部６２４は、データを所定時間だけ遅延させる遅延回路であり、ループ経路６２３に設けられる。従って、制御部６２１は、自ノード１へのデータを送信する場合、ループ経路６２３及び遅延部６２４を介して、データを送信する。

複数の制御レジスタ６２２は、例えば、ｎ個の同期メッセージの組＃０〜＃ｎ−１に対応するように、ｎ個設けられる。換言すれば、１個の制御レジスタ６２２は、１個のプロセスの１個のステージに対応する。複数の制御レジスタ６２２を含むことにより、各々の演算毎に同期メッセージを制御レジスタ６２２に保持し、バリア同期を実行することが可能となる。従って、１組の演算がｎ個の第１の同期メッセージで構成される場合、同期部６２は、各々がｎ個の第１の同期メッセージで構成される複数の組について、各々、バリア同期を実行する。この場合、１個のノード１上で複数のプロセスが動作する。

図２の例においては、１個のノード１上で複数のプロセスが動作し、また、１組の演算が実行され、この１組の演算についてバリア同期を実行することができる。また、図２の例においては、１個のノード１上で複数のプロセスが動作する実施態様に代えて、１個のノード１上で１個のプロセスを動作させることができる。この場合、プロセスとノード１とは同様に取り扱っても良い。

図３に戻って、各々の制御レジスタ６２２は、シグナルレジスタ６２２１と、宛先レジスタ６２２２とを含む。宛先レジスタ６２２２は、実際には、複数のレジスタを含むレジスタ群である。例えば、各々の制御レジスタ６２２には、受信状態レジスタ、換言すれば、シグナルレジスタ６２２１と、宛先レジスタ６２２２とが含まれる。

制御部６２１は、同期を行う２以上の同期装置からの同期情報を、シグナルレジスタ６２２１に保持する。同期を行う２以上のバリア同期装置６は、自ノード１を含む。制御部６２１は、シグナルレジスタ６２２１に同期を行う２以上のバリア同期装置６からの同期情報を全て保持した場合に、自ノード１を含む同期を行う２以上のバリア同期装置６へのデータを送信する。換言すれば、制御部６２１は、制御レジスタ６２２に受信装置６１により抽出された同期情報と自制御部６２１からの同期情報とが揃った場合（全ての同期情報が揃った場合）に、他ノード１へのデータを送信装置６３に送信させ、自ノード１へのデータを遅延部６２４を介して自制御部６２１へ戻す。

具体的には、制御部６２１は、シグナルレジスタ６２２１に保持された同期情報に基づき、同期を行う２以上の同期装置のうち、他ノード１へのデータを送信装置６３に送信させる。また、制御部６２１は、シグナルレジスタ６２２１に保持された同期情報に基づき、同期を行う２以上の同期装置のうち、自ノード１へのデータを、遅延部６２４を介することにより他ノード１へのデータに対して所定時間だけ遅延させて、自制御部へ戻す。

制御部６２１は、チェック回路６２１１において、各プロセスが受信したパケットの整合性のチェック処理を実行する。チェック回路６２１１は、受信装置６１からの同期メッセージ及び宛先情報を取り込んで、これらに基づいて、パケットの整合性のチェック処理を実行する。チェック回路６２１１は、パケットの整合性のチェック結果を、シーケンス回路６２１２に入力する。例えば、チェック回路６２１１は、同期メッセージ及び宛先情報に基づいて、受信したパケットのシーケンス番号が正しいか否かを判断する。シーケンス番号が正しい場合にのみ、実際に、シグナルレジスタ６２２１に同期メッセージが保持される。チェック回路６２１１は、シーケンス番号が正しい場合に、バリア同期が成立しているか否かを判断する判断処理の実行を、シーケンス回路６２１２へ指示する。

制御部６２１は、シーケンス回路６２１２において、バリア同期のメッセージの送信指示を送信装置６３へ出力する。これにより、送信装置６３は、バリア同期のメッセージを、例えば他のノード１へ送信する。シーケンス回路６２１２は、レジスタアクセス回路６２１３による制御レジスタ６２２の参照結果と、ＣＰＵ３からのバリア発行指示とを取り込んで、両者に基づいて、バリア同期が成立しているか否かを判断する。制御部６２１は、シーケンス回路６２１２において、バリア同期が成立している場合、バリア同期のメッセージの送信指示を送信装置６３へ出力し、バリア同期の成立通知をＣＰＵ３へ送信する。

また、制御部６２１は、シーケンス回路６２１２において、バリア同期が成立している場合、バリア同期のメッセージの送信指示を、ループ経路６２３及び遅延部６２４を介して、自制御部へ戻す、換言すれば、再入力する。これにより、制御部６２１は、バリア同期のメッセージを自ノード１へ送信する。シーケンス回路６２１２は、レジスタアクセス回路６２１３による制御レジスタ６２２の参照結果と、ＣＰＵ３からのバリア発行指示とを取り込んで、両者に基づいて、バリア同期のメッセージを自己に送信する。

シーケンス回路６２１２は、バリア同期のメッセージを自ノード１へ送信する場合、遅延計算回路６２１４へ遅延値の算出を指示する。この時、レジスタアクセス回路６２１３は、シーケンス回路６２１２の指示に従って、制御レジスタ６２２の参照結果を遅延計算回路６２１４へ送信する。

制御部６２１は、レジスタアクセス回路６２１３において、制御レジスタ６２２の宛先レジスタ６２２２に設定情報を設定する。設定情報は、ライトデータとしてＣＰＵ３の設定処理部３１から入力される。設定情報を設定する制御レジスタ６２２は、ライトアドレスを含むライト制御信号としてＣＰＵ３の設定処理部３１から入力される。

制御部６２１は、レジスタアクセス回路６２１３において制御レジスタ６２２を参照し、制御レジスタ６２２の参照結果に基づいてシーケンス回路６２１２においてバリア同期のための同期メッセージを送信する。レジスタアクセス回路６２１３は、シーケンス回路６２１２において制御レジスタ６２２を参照する。同期メッセージの送信は、実際には、シーケンス回路６２１２の指示により、送信装置６３が行う。制御レジスタ６２２において、シグナルレジスタ６２２１は、以下に説明する制御レジスタ６２２に対応するプロセス又はノードから同期メッセージを受信したか否かを示す同期情報を格納する。換言すれば、シグナルレジスタ６２２１は、同期メッセージの待ち合わせ状況を示す同期情報を格納する。宛先レジスタ６２２２は、制御レジスタ６２２が同期メッセージを送信すべき宛先であるプロセス又はノードを示す送信先情報と、制御レジスタ６２２に対応し同期メッセージを送信する送信元であるプロセス又はノードを示す送信元情報と、を含む設定情報を格納する。換言すれば、宛先レジスタ６２２２は、同期成立の後に同期メッセージの送信先及び送信元を示す情報を格納する。

同期情報は、同期メッセージに含まれる同期信号に基づいて定まる同期の状態を示す情報であり、シグナルレジスタ６２２１に保持される情報である。同期メッセージに含まれる同期信号は、バリア同期のメッセージに含まれる情報であって、図５を参照して後述するように、例えば、タイプ、宛先ノードアドレス、送信元ノードアドレス、送信元ステージ番号、宛先ステージ番号、シーケンス番号である。同期信号は、バリア同期のメッセージに含まれた形態で送受信される。従って、同期信号の送受信を行うことは、同期信号を含むバリア同期のメッセージの送受信を行うことである。バリア同期のメッセージに含まれた同期信号は、バリア同期のメッセージから抽出される。

宛先レジスタ６２２２は、設定情報を格納する。具体的には、宛先レジスタ６２２２は、「宛先ノードアドレス」「宛先ステージ番号」「送信元ノードアドレス」「送信元ステージ番号」を含む設定情報を格納する。なお、宛先レジスタ６２２２において、「宛先ノードアドレス」及び「宛先ステージ番号」を格納するレジスタを「Dest.」と表示し、「送信元ノードアドレス」及び「送信元ステージ番号」を格納するレジスタを「Address」と表示している。宛先ノードアドレス等については、図５を参照して後述する。設定情報を指定することにより、１個のノード１における１個の制御レジスタ６２２が定まる。

宛先レジスタ６２２２は、同期メッセージの送信先が自ノード１である場合、自プロセス又は自ノード１の制御レジスタ６２２を指定する設定情報を格納する。

バリア同期の実行に先立って、ＩＯ装置１１から設定処理部３１に、設定条件が入力される。この例においては、設定条件において、バリア同期のアルゴリズムはバタフライとされ、実行条件は例えば４個のプロセスとされる。これに加えて、実行条件として、当該演算つまりバリア同期におけるステージ数ｋと、各々のプロセス自身つまり自ノード１のプロセス番号ｉも入力される。

なお、設定処理部３１への設定条件の入力は、これに限られない。例えば、いずれか１個のノード１が、ネットワーク２を介して、他ノード１に各々の設定条件を入力するようにしても良い。また、ネットワーク２に接続された管理用のコンピュータが、ネットワーク２を介して、全てのノード１に各々の設定条件を入力するようにしても良い。

また、バリア同期の実行に先立って、ＣＰＵ３の設定処理部３１は、制御部６２１を介して、制御レジスタ６２２に、設定条件に基づいて、前述の設定情報を設定する。前述したように、設定条件は、バリア同期のアルゴリズムと実行条件とを含む。

この設定の後、設定処理部３１が、制御部６２１にバリア同期開始信号を送信することにより、バリア同期が開始される。プロセスの最後のステージにおいて同期が成立した場合、同期部６２は、バリア同期成立、つまりバリア同期完了を示す信号を設定処理部３１に送る。

制御部６２１は、遅延計算回路６２１４において、シーケンス回路６２１２の指示に従って、レジスタアクセス回路６２１３からの制御レジスタ６２２の参照結果に基づいて、遅延値を算出する。遅延計算回路６２１４は、算出した遅延値を遅延部６２４に送信する。
算出した遅延値は、遅延部６２４における遅延の実時間である。

遅延計算回路６２１４は、以下のようにして、遅延値を算出する。

例えば、並列計算機システムが、図４に示すように、論理的に２次元トーラス結合された複数のノード１を含むコンピュータネットワーク１００を含むとする。複数のノード１の間はネットワーク２により接続される。図４の並列計算機システムにおいて、論理的に隣接するノード１の間の距離が「１ホップ」である。１ホップ当りの通信遅延時間が「Ｔｄ」であるものとする。通信遅延時間Ｔｄは、バリア同期装置６が、他ノード１のバリア同期装置６へのデータ、換言すれば、バリア同期のメッセージの送信に要する時間に等しい時間であり、経験的に予め知ることができる。

図４に示すように、並列計算機システムにおいて、論理ネットワーク上の自ノードアドレスが（Ｘ，Ｙ）＝（２，５）であり、宛先ノードアドレスが（Ｘ，Ｙ）＝（２，７）であるとする。ここで、Ｘ及びＹは、各々、２次元の論理ネットワークにおけるネットワークアドレスのｘ座標及びｙ座標である。

この場合、自ノード１と宛先ノード１との間における、Ｘ軸方向のホップ数は、２−２＝０である。また、自ノード１と宛先ノード１との間における、Ｙ軸方向のホップ数は、７−５＝２である。従って、自ノード１と宛先ノード１との間におけるホップ数は、Ｙ軸方向に「２ホップ」である。これにより、図４の例における、自ノード１と宛先ノード１との間における遅延値は、（ホップ数）×（１ホップ当りの通信遅延時間）＝２Ｔｄとなる。

遅延計算回路６２１４は、バリア同期のメッセージに含まれる自ノードアドレス及び宛先ノードアドレスに基づいて自ノード１と宛先ノード１との間におけるホップ数を算出する。更に、遅延計算回路６２１４は、算出したホップ数に１ホップ当りの通信遅延時間を乗じて、遅延値を算出し、算出した遅延値を遅延部６２４に設定する。

なお、並列計算機システムは、３次元メッシュ結合されたコンピュータネットワークのように、論理的に隣接するノード１のみが接続されるｎ次元のコンピュータネットワークであって良い。ここで、ｎは２以上の整数である。

受信装置６１は、ネットワーク２及びネットワークインタフェース部９を介して他ノード１と接続される受信部である。受信装置６１は、並列計算機システムにおける複数のバリア同期装置６のうち、自ノード１と同期を行う他ノード１のバリア同期装置６からのデータを受信し、受信した他ノード１のバリア同期装置６からのデータから同期情報を抽出する。

具体的には、受信装置６１は、他ノード１からのバリア同期のためのパケット、換言すれば、バリア同期のためのデータを受信する。受信装置６１は、バリア同期のアルゴリズムと実行条件とを含む設定条件に従ってその送信先が予め設定された第１のバリア同期メッセージを受信した場合、受信した第１のバリア同期メッセージを同期部６２に送信する。このため、受信装置６１は、ネットワーク２を介して、他ノード１のバリア同期装置６から、バリア同期のためのパケットを受信する。

一方、前述したように、自ノード１からのバリア同期のためのパケット、換言すれば、バリア同期のためのデータは、ループ経路６２３及び遅延部６２４を介して送受信される。従って、受信装置６１は、自ノード１からのバリア同期のためのパケットを受信しない。

パケットを受信した場合、受信装置６１は、受信したパケットに基づいて、同期信号及び宛先情報を生成して、同期部６２に送信する。具体的には、受信装置６１は、受信したパケットに含まれる同期信号及び宛先情報を取り出し、同期部６２に送信する。同期信号及び宛先情報については、図５を参照して後述する。

なお、送信元のノードが複数存在する場合において、受信装置６１が送信元となるノード１の数に対応した数だけのネットワークインタフェース部９を含む場合、複数の受信装置６１を用いて複数のノードから送信されるパケットを同時に受信することができる。これは送信装置６３においても同様である。

図５は、パケットのフォーマットを示す図である。

プロセス＃０〜プロセス＃３の間において相互に送受信されるパケットは、例えば、図５に示すようなフォーマットを有する。パケットは、例えば、ヘッダＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）、ルーティングヘッダ、タイプ、宛先ノードアドレス、送信元ノードアドレス、送信元ステージ番号、宛先ステージ番号、シーケンス番号、パケットＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）を含む。パケットに含まれる同期信号は、例えば、タイプ、宛先ノードアドレス、送信元ノードアドレス、送信元ステージ番号、宛先ステージ番号、シーケンス番号である。宛先情報は、例えば、宛先ノードアドレス、宛先ステージ番号である。

ヘッダＣＲＣは、ルーティングヘッダ用の誤り検出符号である。ルーティングヘッダは、ルータが、パケットの送信において、次の宛先を決定するための情報である。ルータは、ネットワーク２において、パケットの転送を実行するネットワークインタフェースに含まれる中継装置である。

タイプは、パケットのタイプを示す情報である。換言すれば、タイプがバリアを示すタイプである場合に、パケットがバリア同期のメッセージであることを示す。

宛先ノードアドレスは、パケットの宛先ノード１のネットワーク２上のアドレスを示す。バリア同期装置６が、各ステージでバリアパケットを送信する際に、バリア同期装置６の設定情報レジスタに予め設定されている宛先ノードアドレスをパケットに埋め込む。

送信元ノードアドレスは、パケットの送信元ノード１のネットワーク２上のアドレスを示す。バリア同期装置６が、各ステージでバリアパケットを送信する際に、自ノードアドレスをパケットに埋め込む。パケットを受信したバリア同期装置６（の制御部６２１）が、本フィールドの値と、バリア同期装置６の設定情報レジスタに予め設定されている送信元ノードアドレスとを比較して、パケットの受信可/不可の判定に使用される。

送信元ステージ番号は、パケット送信元ノード１のバリア同期装置６でのステージ番号である。バリア同期装置６が、各ステージでバリア同期メッセージに対応するバリアパケットを送信する際に、ステージ番号を送信元ステージ番号としてパケットに埋め込む。パケットを受信したバリア同期装置６（の制御部６２１）が、本フィールドの値と、バリア同期装置６の設定情報レジスタに予め設定されている送信元ステージ番号とを比較して、パケットの受信可/不可の判定に使用される。

送信先ステージ番号は、パケット送信先ノードバリア同期装置６でのステージ番号を示す。バリア同期装置６が、各ステージでバリア同期メッセージに対応するバリアパケットを送信する際に、バリア同期装置６の設定情報レジスタに予め設定されている宛先ステージ番号をパケットに埋め込む。パケットを受信したバリア同期装置６（の制御部６２１）が、本フィールドの値を参照して、設定情報レジスタの選択（ステージ選択）に使用される。

シーケンス番号は、バリア同期装置６が各ステージでバリア同期メッセージに対応するバリアパケットを送信する際に付加する番号である。

パケットＣＲＣは、パケット全体の誤り検出符号である。

図３に戻って、同期部６２は、受信装置６１及び自ノード１の制御部６２１からの同期信号及び宛先情報に基づいて、バリア同期の処理を行なう。このために、同期部６２は、複数組の同期信号（バリア同期メッセージ）の待ち合わせを行ない、各組で同期成立の後、同期信号としてのバリア同期のメッセージを宛先情報により指定された送信先に送信する。これにより、バリア同期を行なうアルゴリズムにおいて、ステージ毎にバリアポイント到着の信号の送信先を変更する処理を高速に行なうことができる。同期信号（バリア同期メッセージ）の各組に対しては、一意に定まる設定情報が割り当てられる。同期部６２は、同期信号としてのバリア同期のメッセージを受信し、同期が成立した組について、対応する同期信号を出力する。

例えば、同期部６２は、各々の同期信号（バリア同期メッセージ）の組について、設定条件に従って予め設定されたｎ（ｎは正の整数）個の第１のバリア同期メッセージについての同期を取る。各組において、ｎ個のバリア同期メッセージが入力された場合、同期成立となる。同期部６２は、同期成立の後に、第２のバリア同期メッセージの送信を送信装置６３に指示する。第２のバリア同期メッセージは、ｍ（ｍは正の整数）個とされ、各々について設定条件に従ってその送信先が予め設定される。

同期が成立した場合、同期部６２は、各組について、予め設定された送信先にバリア同期メッセージを送信する。送信先は、他ノード１の同期部６２、又は、自ノード１の制御部６２１である。バリア同期メッセージの送信先が他ノード１である場合、送信先ノード１の宛先ノードアドレスを含む設定情報が同期部６２に予め設定されている。この場合、同期部６２は、送信装置６３にパケットの送信指示の信号を送る。同期部６２からのパケット送信指示を受けた送信装置６３は、ネットワーク２を介して、宛先ノードアドレスで指定される他ノード１のバリア同期装置６に、バリア同期のためのパケットを送信する。

一方、バリア同期メッセージの送信先が自ノードである場合、同期部６２には自ノード１の制御部６２１を指示する設定情報が予め設定されている。同期部６２は、自プロセス又は自ノード１の制御部６２１の指定された制御レジスタ６２２にバリア同期メッセージを送信する。自ノード１の制御部６２１へのバリア同期メッセージの送信が実行されると、バリア同期メッセージは、実際には、制御部６２１からループ経路６２３を介して遅延部６２４へ送信される。これにより、バリア同期メッセージが制御部６２１へ入力されるまでの時間が、所定時間だけ遅延される。自ノード１へのバリア同期メッセージは、例えば、図５のパケットにおける同期信号の部分のみを含む。

なお、同期部６２は、ＣＰＵ３の設定処理部３１からバリア同期開始の信号を受信した場合、指定された送信先に対してバリア同期メッセージを送る。同期部６２は、バリア同期メッセージの最後の組で同期が成立した場合、バリア同期完了の信号をＣＰＵ３の設定処理部３１に通知する。

送信装置６３は、ネットワーク２及びネットワークインタフェース部９を介して他ノード１と接続される送信部である。送信装置６３は、並列計算機システムにおける複数のバリア同期装置６のうち、自ノード１と同期を行う他ノード１のバリア同期装置６へのデータを送信する。同期を行う２以上のバリア同期装置６には、自ノード１のバリア同期装置６が含まれる。

具体的には、送信装置６３は、他ノード１へのバリア同期のためのパケット、換言すれば、バリア同期のためのデータを送信する。送信装置６３は、バリア同期のアルゴリズムと実行条件とを含む設定条件に従ってその送信先が予め設定された第１のバリア同期メッセージを送信した場合、送信した第１のバリア同期メッセージを同期部６２に送信する。このため、送信装置６３は、ネットワーク２を介して、他ノード１のバリア同期装置６へ、バリア同期のためのパケットを送信する。

また、送信装置６３は、自ノード１のバリア同期装置６の制御部６２１へ、バリア同期のためのパケット、換言すれば、バリア同期のためのデータを送信する。この場合、バリア同期のためのパケットは、前述したように、ループ経路６２３及び遅延部６２４を介して、送受信される。従って、前述したように、送信装置６３が自ノード１へのバリア同期のメッセージを送信することはない。

送信装置６３は、同期部６２からの送信の指示を受信した場合、予め設定されたｍ個の送信先に、第２のバリア同期メッセージを送信する。このため、送信装置６３は、同期部６２からパケット送信指示の信号を受け取り、指定された送信先に基づいて、パケットを生成して、ネットワーク２を介して、他ノード１に送信する。前述したように、送信先となるノード１は、設定情報に基づいて定められる。

図６は、遅延部の構成の一例を示す図である。

遅延部６２４は、１個の遅延回路６２４１を含む。遅延回路６２４１は、同期信号記憶部６２４２と、タイマ部６２４３とを含む。同期信号記憶部６２４２は、制御部６２１から自ノード１宛てのバリア同期のメッセージを受信し、受信したバリア同期のメッセージを一時的に記憶するレジスタである。タイマ部６２４３は、制御部６２１から指示された遅延値をカウントする。

例えば、同期信号記憶部６２４２は、制御部６２１から自ノード１宛てのバリア同期のメッセージを受信する。自ノード１宛てのバリア同期のメッセージを受信した同期信号記憶部６２４２は、バリア同期のメッセージの受信通知をタイマ部６２４３に出力すると共に、自ノード１宛てのバリア同期のメッセージを一時的に記憶する。受信通知を受信したタイマ部６２４３は、カウントを開始して、カウント値が遅延値に達すると、バリア同期のメッセージの送信指示を同期信号記憶部６２４２に出力する。タイマ部６２４３は、カウント値が遅延値に達すると、カウント値が再度「０」とされる。

バリア同期のメッセージの送信指示を受信した同期信号記憶部６２４２は、一時的に記憶している自ノード１宛てのバリア同期のメッセージを、制御部６２１に出力する。この出力の後、同期信号記憶部６２４２は、一時的に記憶している自ノード１宛てのバリア同期のメッセージを消去する。

遅延部６２４の構成は、図６の構成に限られず、種々の構成とすることができる。

例えば、図７に示すように、遅延部６２４’が、１個の入力回路６２４４と、複数の遅延回路６２４１と、１個の出力回路６２４５とを含むようにしても良い。各々の遅延回路６２４１は、同期信号記憶部６２４２と、タイマ部６２４３とを含む。

図７において、複数の遅延回路６２４１の各々は、複数の制御レジスタ６２２の各々に対応するように設けられる。入力回路６２４４は、受信したバリア同期のメッセージに基づいて、受信したバリア同期のメッセージを処理する制御レジスタ６２２に対応する遅延回路６２４１を選択し、選択した遅延回路６２４１に受信したバリア同期のメッセージを入力する。出力回路６２４５は、複数の遅延回路６２４１から出力されたバリア同期のメッセージをマルチプレクスして、制御部６２１に出力する。

これにより、１個のノード１上において複数のプロセスが動作する場合において、複数のプロセスの各々について、プロセス毎に異なる遅延値を用いてプロセス毎に適した遅延処理を実現することができる。この結果、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

遅延部６２４は、同期部６２の内部以外に設けるようにしても良い。例えば、遅延部６２４は、制御部６２１の内部に設けても良い。また、遅延部６２４は、同期部６２の外部であって、バリア同期装置６の内部に設けても良い。

図８は、図３のバリア同期装置が実行する、バタフライによるバリア同期処理の処理フローを示す。

ＣＰＵ内に設定された設定処理部３１は、バリア同期を開始する前に、バリア同期のアルゴリズムと設定条件とに基づいて、各々の制御レジスタ６２２の宛先レジスタ６２２２に、バタフライでの次ステージに対応した宛先ノードアドレスと宛先ステージ番号を設定する（ステップＳ１１）。宛先ノードアドレスと宛先ステージ番号を設定することにより、前述したように、１個のプロセスの１個のステージに対応する１個の制御レジスタ６２２が定まる。

このために、設定処理部３１は、宛先ノードアドレス及び宛先ステージ番号を設定すべき制御レジスタ６２２の宛先ステージ番号を、ライトアドレスとして同期部６２に入力する。また、設定処理部３１は、制御レジスタ６２２の宛先レジスタ６２２２に設定すべき宛先ノードアドレスと宛先ステージ番号とを、ライトデータとして同期部６２の制御部６２１に入力する。ライトアドレス及びライトデータは、制御レジスタ６２２毎に入力される。これに応じて、制御部６２１は、入力されたライトデータである宛先ノードアドレス及び宛先ステージ番号を、ライトアドレスにより指定された制御レジスタ６２２の宛先レジスタ６２２２に格納する。ライトデータの格納は、実際には、設定処理部３１からのライトアドレス及びライトデータを受信した制御部６２１により実行される。一方、これとは別に、シグナルレジスタ６２２１の初期値は、例えば予め「０」とされる。

宛先ノードアドレスと宛先ステージ番号との設定は、例えば以下のように行われる。ノード数が２のべき乗である場合、バタフライにおいては、同期成立の後、自プロセス又は自ノードの次ステージと、他ノードでの次ステージの２箇所に対して、バリア同期メッセージが送信される。従って、宛先レジスタ６２２２に指定する宛先は、自プロセス又は自ノードの宛先ステージ番号、又は、他ノードの宛先ノードアドレス及び宛先ステージ番号のいずれかである。

最初のステージにおいては、バリア同期メッセージの待ち合わせを行なわないので、シグナルレジスタ６２２１は使用しない。一方、最後のステージにおいては、宛先レジスタ６２２２は使用しない。従って、最初のステージと最後のステージにおいて、使用するレジスタは重複しない。そのため、最初と最後のステージにおいては同一の制御レジスタ６２２が指定される。なお、最初のステージと最後のステージにおいて使用するレジスタが重複しない場合でも、最初と最後のステージにおいて異なる制御レジスタ６２２が指定されるようにしても良い。

ノード数が２のべき乗でない場合、ノード数を２のべき乗にするためにネットワーク２に追加される追加ノードが持つ制御レジスタ６２２を、他のノードに持たせる。例えば、図９でノード＃０〜＃３でバリア同期を取りたい場合は、ノードの持つ制御レジスタ６２２をノード＃０〜＃３のいずれかに持たせる。この場合、必要となるのは中継ステージに相当する制御レジスタのみであるので、中継ステージに相当する制御レジスタ＃２をノード＃１〜＃３のいずれかのノードに持たせる。更に、最初のステージにおいて、制御レジスタの送信先のシグナルレジスタ６２２１の値を予め「１」に設定する。最後のステージにおいて、制御レジスタの送信元の宛先レジスタ６２２２から最初のステージの制御レジスタを外す。

設定処理部３１は、プロセスがバリアポイントに到達した場合、バリア同期装置６の同期部６２に対しバリア同期開始の信号を送る（ステップＳ１２）。バリア同期開始信号は最初のステージに対応する制御レジスタ６２２の番号を含む。最初のステージにおいては、他のプロセスからバリア同期メッセージを含むパケットを受信することは無いので、受信装置６１から同期信号及び宛先が制御部６２１に送信されることも無い。

同期部６２の制御部６２１は、バリア同期開始の信号を受信すると、バリア同期開始信号にて指定された番号に対応する制御レジスタ６２２の宛先レジスタ６２２２の値「Destination」を読む（ステップＳ１３）。この読取のために、制御部６２１は、バリア同期開始信号にて指定された宛先ステージ番号をリードアドレスとして用いて、当該アドレスの制御レジスタ６２２の宛先レジスタ６２２２の値をリードデータとして読み出す。最初のステージに対応する制御レジスタ６２２のシグナルレジスタ６２２１は使用されず、従って、バリア同期メッセージの待ち合せも行われない。

制御部６２１は、宛先レジスタ６２２２の値の中の他ノード１の制御レジスタ６２２を指定する値に基づいて、送信装置６３に対しパケット送信指示の信号を出すと共に、宛先レジスタ６２２２の値の中の自ノード１の制御レジスタ６２２を指定する値に基づいて、遅延部６２４へバリア同期メッセージを送信する（ステップＳ１４）。パケット送信指示は、他ノード１を指示する宛先レジスタ６２２２の値を含む。

送信装置６３は、制御部６２１からのパケット送信指示で指定された宛先ノードアドレスおよび宛先ステージ番号に基づいて、パケットを生成し、パケットをネットワーク２へ送信する。このパケットは、他ノード１宛のバリア同期のメッセージ、換言すれば、同期信号を含む同期メッセージである。このパケットの送信先は、指定された宛先ノードアドレスおよび宛先ステージ番号である。一方、制御部６２１が遅延部６２４へ送信する同期信号は、自ノード１宛のバリア同期のメッセージに相当する。例えば、制御部６２１が遅延部６２４へ送信する同期信号は、図５のパケットから、ヘッダＣＲＣ、ルーティングヘッダ、パケットＣＲＣを除いたものである。

遅延部６２４は、制御部６２１から受信した遅延値に相当する時間だけ、制御部６２１から受信した同期信号の送信を保留し（ステップＳ１５）、遅延値に相当する時間、換言すれば、遅延時間が経過したか否かを判断する（ステップＳ１６）。遅延時間が経過しない場合（ステップＳ１６ Ｎｏ）、遅延部６２４は、ステップＳ１５を繰り返す。遅延時間が経過した場合（ステップＳ１６ Ｙｅｓ）、遅延部６２４は、保持している同期信号を、制御部６２１へ送信する（ステップＳ１７）。

制御部６２１は、宛先レジスタ６２２２の値の中の自ノードの制御レジスタ６２２を指定する値に基づいて、宛先レジスタ６２２２において指定された制御レジスタ６２２のシグナルレジスタ６２２１の値を読む（ステップＳ１８）。換言すれば、自ノードの次ステージにおける制御レジスタ６２２のシグナルレジスタ６２２１の値「signal」が読み出される。これは、自ノードの同期部６２に同期信号を送り、自ノードでの同期の待ち合わせを行うためである。

続いて、制御部６２１が、次ステージのシグナルレジスタ６２２１に同期状態を示す「１」が設定されているか否かを調べる（ステップＳ１９）。シグナルレジスタ６２２１に「１」が設定されている場合（ステップＳ１９ Ｙｅｓ）、同期成立となる。一方、シグナルレジスタ６２２１に「１」が設定されていない場合（ステップＳ１９ Ｎｏ）、同期は成立していない。

同期が成立していない場合（ステップＳ１９ Ｎｏ）、同期部６２が、次ステージの制御レジスタ６２２のシグナルレジスタ６２２１の値Signalを「１」に設定し、これ以後、パケットの受信を待ち合わせる（ステップＳ１１０）。この設定のために、制御部６２１は、読み出した宛先レジスタ６２２２の値の中の自ノードを指定する値をライトアドレスとして用いて、当該アドレスの制御レジスタ６２２のシグナルレジスタ６２２１に「１」をライトデータとして書き込む。これにより、待ち合わせすべき同期信号の一方を受信したことが示される。

この後、受信装置６１は、パケットを受信した場合、受信したパケットに基づいて、同期信号と宛先となる宛先ノードアドレスと宛先ステージ番号とを取り出し、同期部６２に送信する（ステップＳ１１１）。

同期部６２の制御部６２１は、受信装置６１からの信号を受信した場合、指定された制御レジスタ６２２のシグナルレジスタ６２２１の値を読み取る（ステップＳ１１２）。この後、ステップＳ１９を繰り返す。例えば、制御部６２１は、受信装置６１からの同期信号と宛先とを受信すると、受信した宛先ステージ番号に基づいて、制御レジスタ６２２のシグナルレジスタ６２２１の値を読取る。この読取のために、制御部６２１は、指定された宛先ステージ番号をリードアドレスとして用いて、当該アドレスの制御レジスタ６２２のシグナルレジスタ６２２１の値を、リードデータとして読み出す。

一方、ステップＳ１９において同期が成立している場合（ステップＳ１９ Ｙｅｓ）、制御部６２１は、更に、制御レジスタ６２２が最後のステージに対応したものか否かを調べる（ステップＳ１１３）。例えば、先にステップＳ１１０が実行された後に再度ステップＳ１９が実行された場合には、制御レジスタ６２２のシグナルレジスタ６２２１の値は、「１」である。従って、この場合、同期が成立する。

最後のステージに対応する制御レジスタ６２２で同期が成立した場合（ステップＳ１１３ Ｙｅｓ）、制御部６２１は、バリア同期成立の信号をＣＰＵの設定処理部３１に送る（ステップＳ１１４）。設定処理部３１は、制御部６２１からのバリア同期成立の信号を受け取り、バリア同期成立を知る（ステップＳ１１５）。

ステップＳ１１３において制御レジスタ６２２が最後のステージに対応したものでない場合（ステップＳ１１３ Ｎｏ）、制御部６２１は、ステップＳ１４を繰り返す。

図９は、図８のバタフライによるバリア同期処理における各ステージ間での同期メッセージの流れを示す。

図９において、ノード＃０に着目すると、以下のように同期メッセージが流れる。例えば、ステージ＃１において、ノード＃０は、バリアポイントに到達した場合、バリア同期開始信号の入力により同期開始を指示される。これに応じて、ノード＃０は、ステージ＃１において、予め指示された宛先であるノード＃０及びノード＃１に、同期メッセージを送信する。ノード＃０はノード＃０にとって自ノード１であり、ノード＃１はノード＃０にとって他ノード１である。

ここで、ノード＃０のステージ＃１から、他ノード１、換言すれば、ノード＃１のステージ＃２に送信される同期メッセージは、ネットワーク２を介して、ノード＃２のステージ＃２に到達する。これに対して、ノード＃０のステージ＃１から、自ノード１、換言すれば、ノード＃１のステージ＃２に送信されるバリア同期メッセージは、遅延部６２４を介して、ノード＃１のバリア同期装置６の内部で送受信される。

また、ノード＃１のステージ＃１からノード＃１のステージ＃２に送信される同期メッセージ、ノード＃２のステージ＃１からノード＃２のステージ＃２に送信される同期メッセージ、ノード＃３のステージ＃１からノード＃３のステージ＃２に送信される同期メッセージも、各々の遅延部６２４を介して、自ノード１のバリア同期装置６の内部で送受信される。

ステージ＃２において、自己の同期信号を受信したノード＃０は、予め指示されたノード＃１からのバリア同期メッセージを待ち合わせる。ノード＃０のステージ＃２において待ち合わせられるバリア同期メッセージは、ノード＃１がバリアポイントに到達した後に、同様にして、ノード＃１からノード＃０に到達する。ノード＃１からのバリア同期メッセージが到達した場合、ノード＃０において、自己の同期信号と、ノード＃１からのバリア同期メッセージに含まれる同期信号との待ち合わせつまり２つの信号の同期が成立する。

この時、前述したように、自己の同期信号はネットワーク２と同等の遅延を生じる遅延部６２４を介して受信され、他ノード１からのバリア同期メッセージはネットワーク２を介して受信される。これにより、ノード＃０〜ノード＃３のステージ＃２の各々において、同時に同期が成立する。この結果、バリア同期において、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

ステージ＃２において同期が成立すると、ノード＃０は、予め指示された宛先であるノード＃０に同期信号を送信し、ノード＃２にバリア同期メッセージを送信する。

ここで、ノード＃０のステージ＃２から、ノード＃２のステージ＃３に送信されるバリア同期メッセージは、ネットワーク２を介して、ノード＃２のステージ＃３に到達する。これに対して、ノード＃０のステージ＃２から、ノード＃０のステージ＃３に送信される同期信号は、遅延部６２４を介して、ノード＃０のバリア同期装置６の内部で送受信される。ノード＃１のステージ＃２からノード＃１のステージ＃３に送信される同期信号、ノード＃２のステージ＃２からノード＃２のステージ＃３に送信される同期信号、ノード＃３のステージ＃２からノード＃３のステージ＃３に送信される同期信号も、各々の遅延部６２４を介して、自ノード１のバリア同期装置６の内部で送受信される。

ステージ＃３において、自己の同期信号を受信したノード＃０は、予め指示されたノード＃２からのバリア同期メッセージを待ち合わせる。ノード＃０のステージ＃３において待ち合わせられるバリア同期メッセージは、ノード＃２がバリアポイントに到達し、かつ、バリアポイントに到達したノード＃４からのバリア同期メッセージを受信した後に、同様にして、ノード＃２からノード＃０に到達する。ノード＃２からのバリア同期メッセージが到達した場合、ノード＃０において、自己の同期信号と、ノード＃２からのバリア同期メッセージとの同期が成立する。

この時、前述したように、自己の同期信号はネットワーク２と同等の遅延を生じる遅延部６２４を介して受信され、他ノード１からのバリア同期メッセージはネットワーク２を介して受信される。これにより、ノード＃０〜ノード＃３のステージ＃２の各々において、同時に同期が成立する。この結果、バリア同期において、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

ステージ＃３において同期が成立すると、ノード＃０は、バリア同期が成立したと判定して、バリア同期成立信号を出力する。

ノード＃１〜３においても、同様にして、ステージ＃３において、バリア同期が成立し、バリア同期成立信号が出力される。これにより、バタフライによるバリア同期が実行される。

次に、バタフライによりバリア同期を行いつつリダクション演算を行うリダクション演算装置を含む並列計算機について説明する。

図１０は、バタフライによりバリア同期を行いつつリダクション演算を行うリダクション演算装置を含むノードの構成の一例を示す。図１１は、図１０のリダクション演算装置の構成の一例を示す。

図１０のリダクション演算装置８は、図１に示す並列計算機システムを構成するノード１に設けられる。図１０の例において、ノード１は、図２に示すノード１のバリア同期装置６を、リダクション演算装置８で置き換えた構成を含む。即ち、図１０の例のノード１は、バリア同期装置６以外は、図２に示すノード１と同様の構成を含む。以下、図２〜図６にも示される要素については、図示又は説明を省略する場合がある。また、図１１において、リダクション演算装置８をバリア・リダクション演算装置８と表記している。

リダクション演算装置８は、バリア同期を取りつつリダクション演算を行う。リダクション演算装置８は、受信装置８１と、同期装置８２と、送信装置８３と、演算装置８４と、ループ経路８２３とを含む。同期装置８２は、制御部８２１と、制御レジスタ８２２とを含む。なお、以下の説明において、同期装置８２を「同期部８２」と言い、演算装置８４を「演算部８４」と言うこととする。また、制御部８２１は、図３の制御部６２１と同様の構成を有するが、図示を省略する。

リダクション演算装置８は、図１１に示すように、演算部８４と演算部８４の周辺回路である入力データレジスタ８４１及び出力データレジスタ８４２以外は、バリア同期装置６と同様の構成を含む。演算部８４を含むので、リダクション演算装置８は、バリア同期開始の信号に代えてリダクション演算開始の信号を入力され、また、バリア同期成立の信号に代えてリダクション演算完了の信号を出力する。

また、演算部８４を含むので、リダクション演算装置８は、ネットワーク２との間で、パケットの送受信に加えて、データの送受信も行い、また、ＣＰＵ３の設定処理部３１との間で、制御信号に加えて、データの送受信も行う。

また、演算部８４を含むので、リダクション演算装置８は、リダクション演算の対象データを外部から入力され、また、リダクション演算の結果を外部に出力する。具体的には、受信装置８１は、受信した２以上の同期装置からのデータから演算対象データを抽出し、演算部８４に入力する。演算部８４は、抽出された演算対象データに対して演算を行い、演算結果データを送信装置８３へ出力する。送信装置８３は、同期を行う２以上の同期装置へのデータに、演算結果データを含めてそれぞれ送信する。

リダクション演算の第１の対象データは、ＣＰＵ３の設定処理部３１から、ライトデータとして入力データレジスタ８４１に入力され、入力データレジスタ８４１から演算部８４に入力される。リダクション演算の第２の対象データは、ネットワーク２から受信装置８１を介してパケットとして入力され、パケットから取出されて、演算部８４に入力される。

一方、リダクション演算の結果は、演算部８４から、出力データレジスタ８４２に出力され、リードデータとして出力データレジスタ８４２からＣＰＵ３の設定処理部３１に出力される。また、リダクション演算の結果は、演算部８４から送信装置８３に出力され、送信装置８３からネットワーク２へパケットとして送信される。

入力データレジスタ８４１及び出力データレジスタ８４２は、複数設けられる。入力データレジスタ８４１は、各々、制御レジスタ８２２と対応する。出力データレジスタ８４２も同様である。

ライトデータを書き込むべき入力データレジスタ８４１は、設定処理部３１からライトアドレスにより指定される。リードデータを読み出すべき入力データレジスタ８４１は、制御部８２１からリードアドレスにより指定される。入力データレジスタ８４１のリードアドレスは、例えば受信装置８１が受信したパケットにおける宛先情報が指示する制御レジスタ８２２に対応し、指示された制御レジスタ８２２の設定情報に基づいて生成される。ライトデータを書き込むべき出力データレジスタ８４２は、制御部８２１からライトアドレスにより指定される。出力データレジスタ８４２のライトアドレスは、ライトデータのリダクション演算に用いられる制御レジスタ８２２に対応し、指示された制御レジスタ８２２の設定情報に基づいて生成される。リードデータを読み出すべき出力データレジスタ８４２は、設定処理部３１からリードアドレスにより指定される。

リダクション演算を実行するために、設定処理部３１は、ＩＯ装置１１から入力された設定条件に従って、リダクション演算装置８における第１のバリア同期メッセージの送信先及び第２のバリア同期メッセージの送信先を、リダクション演算装置８に設定する。

また、設定処理部３１は、システム制御部５を介して、リダクション演算の開始時にリダクション演算装置８に対して演算対象のデータを送信し、また、リダクション演算装置８からリダクション演算結果を受信する。リダクション演算装置８は、ネットワーク２を介して、他ノード１のリダクション演算装置との間で通信を行ない、当該通信に基づいて、リダクション演算を行なう。

更に、リダクション演算を実行するために、リダクション演算装置８が含む同期部８２は、同期成立の後に、第２のバリア同期メッセージの送信を送信装置８３に指示（図示「他ノード宛て同期メッセージ送信指示」）すると共に、予め定められたリダクション演算を演算部８４に指示する。また、送信装置８３は、第２のバリア同期メッセージ送信の指示を受信した場合、第２のバリア同期メッセージと共に、演算部８４におけるリダクション演算の結果をネットワーク２に送信する。

また、同期部８２の制御部８２１は、演算種類情報を保持する。演算種類情報は、演算部８４におけるリダクション演算の制御のために、演算の種類を示す情報である。演算種類情報は、ＣＰＵ３から入力データレジスタを介して制御部８２１に入力される。演算種類情報も、設定条件の一部として、ＩＯ装置１１から入力される。

図１０の例におけるリダクション演算は、以下のように行われる。

設定処理部３１は、バリア同期装置６と同様にして、同期部８２におけるリダクション演算の各組に対応する制御レジスタ８２２に、設定条件に基づいて、設定情報を設定する。この後、設定処理部３１は、入力データを入力データレジスタ８４１に入力して、リダクション同期開始信号を同期部８２に送信する。これにより、演算部８４によるリダクション演算が開始される。最後のステージに対応した制御レジスタ８２２において同期が成立した場合、リダクション演算装置８は、演算結果とリダクション演算完了の信号とを、設定処理部３１に送る。

受信装置８１はネットワーク２を介してパケットを受信し、受信したパケットに基づいて、同期信号及び宛先情報を同期部８２に送信し、パケットとして受信したデータを演算部８４に送信する。

演算部８４において、入力データレジスタ８４１は、ＣＰＵ３から送信されたリダクション演算の対象である入力データを一時格納し、制御部８２１からの指示に応じて、格納したデータを演算部８４に入力する。ＣＰＵ３からのデータは、前述したように、リダクション演算の開始時に入力される。

演算部８４は、同期が成立した場合、制御部８２１からの演算指示に従って、第１のデータと第２のデータとについて、所定のリダクション演算を行なう。第１のデータは、例えば、自ノード１のデータ、換言すれば、演算部８４が前ステージで行なった演算結果である。第２のデータは、例えば、他ノード１から受信したデータ、換言すれば、受信装置８１が受信したパケットからのデータである。演算の種類は、制御部８２１からの演算装置制御により指示される。

演算部８４は、制御部８２１からの制御に従って、演算結果を保持し、また、送信装置８３に入力する。具体的には、演算結果は、リダクション演算が完了する以前には、送信装置８３に出力するようにされ、これ以外の場合には、出力データレジスタ８４２に出力するようにされる。

出力データレジスタ８４２は、リダクション演算の結果を、ＣＰＵ３に出力する。出力データレジスタ８４２から出力されるリダクション演算結果は、リダクション演算完了時にＣＰＵ３に入力される。

送信装置８３は、演算部８４から演算結果を受信し、制御部８２１から送信指示を受信した場合、これらに基づいて、パケットを生成し、生成したパケットをネットワーク２へ送信する。

同期部８２は、バリア同期装置６の同期部６２と同様にして、ステージ毎に演算の中間結果の送信先を変更する処理を行う。同期部８２の制御部８２１は、同期信号及び設定情報を受信装置８１から受信した場合、受信した設定情報に対応する制御レジスタ８２２に同期信号を送る。

制御部８２１は、同期が成立した場合、送信装置８３へ同期信号、換言すれば、他ノード１宛てのバリア同期のメッセージの送信指示を出す。この時、制御部８２１は、自プロセス又は自ノード１の同期部８２内の指定された制御レジスタ８２２に同期信号を送信することに加えて、演算部８４を制御する。例えば、制御部８２１は、演算部８４に入力されたデータと、保持している前ステージにおける演算結果との間で、リダクション演算を行なわせる。一方、同期が成立していない場合、制御部８２１は、演算部８４にデータを保持させる。

自プロセス又は自ノード１の同期部８２の指定された制御レジスタ８２２に同期信号を送信した場合において、同期が成立した場合、制御部８２１は、更に、演算結果と演算部８４内の記憶部で待ち合わせているデータとの演算を繰り返すよう演算部８４を制御する。一方、同期が成立しない場合、制御部８２１は、演算結果を演算部８４内の記憶部に送信する。

制御部８２１は、設定処理部３１からリダクション演算開始の信号を受け取ると、指定された組つまり制御レジスタ８２２の送信先に、同期信号と設定処理部３１から入力されたデータとを送信する。この後、最後の組で同期が成立した場合、制御部８２１は、演算結果とリダクション演算完了の信号とを、設定処理部３１に送信する。

図１２及び図１３は、一体となって、図１０のリダクション演算装置８が実行する、バタフライによるバリア同期を行いつつリダクション演算を行う処理の処理フローを示す。

このリダクション演算はバリア同期を利用する。従って、図１３の処理フローは、リダクション演算対象のデータの送受信及びリダクション演算を含むこと以外は、図８の処理フローとほぼ同一である。

設定処理部３１は、リダクション演算を開始する前に、リダクション演算を行なうノード数から使用する制御レジスタ８２２の数を決定し、各制御レジスタ８２２の宛先レジスタ８２２２にバタフライでの次ステージに対応した宛先ノードアドレスと宛先ステージ番号とを設定し、また、各制御レジスタ８２２の所定のレジスタに演算種類を設定する（ステップＳ２１）。レジスタの設定は、バリア同期におけるレジスタの設定と同様に行われる。

設定処理部３１は、リダクション演算を開始するため、リダクション演算のタイプを入力データレジスタ８４１に設定し、演算データを入力データレジスタ８４１に設定する（ステップＳ２２）。

設定処理部３１は、プロセスがバリアポイントに到達した場合、バリア同期装置８の同期部８２に対しバリア同期及びリダクション演算開始の信号を送る（ステップＳ２３）。バリア同期及びリダクション演算開始信号は、入力レジスタ番号と、最初のステージに対応した宛先ステージ番号とを含む。

同期部８２の制御部８２１は、バリア同期及びリダクション演算開始の信号が送られると、リダクション演算信号で指定された制御レジスタ８２２の宛先レジスタ８２２２の値を読む（ステップＳ２４）。

更に、同期部８２の制御部８２１は、演算部８４にリダクション演算を指示する。これに応じて、演算部８４は、リダクション演算を実行し、演算結果を送信装置８３に出力する。また、制御部８２１は、宛先レジスタ８２２２の値の中の他ノード１の制御レジスタ８２２を指定する値に基づいて、送信装置８３に対しパケット送信指示の信号を出すと共に、宛先レジスタ８２２２の値の中の自ノード１の制御レジスタ８２２を指定する値に基づいて、遅延部８２４へ同期信号を送信する（ステップＳ２５）。パケット送信指示は、他ノード１を指示する宛先レジスタ８２２２の値を含む。

送信装置８３は、制御部８２１からのパケット送信指示で指定された宛先ノードアドレスおよび宛先ステージ番号に基づいて、パケットを生成し、パケットをネットワーク２へ送信する。このパケットは、他ノード１宛のバリア同期及びリダクション演算のメッセージ、換言すれば、同期信号を含むバリア同期メッセージである。このパケットの送信先は、指定された宛先ノードアドレスおよび宛先ステージ番号である。一方、制御部８２１が遅延部８２４へ送信する同期信号は、自ノード１宛のバリア同期及びリダクション演算のメッセージである。例えば、制御部８２１が遅延部８２４へ送信する同期信号は、図５のパケットから、ヘッダＣＲＣ、ルーティングヘッダ、パケットＣＲＣを除いたものである。

遅延部８２４は、制御部８２１から受信した遅延値に相当する時間だけ、制御部８２１から受信した同期信号の送信を保留し（ステップＳ２６）、遅延値に相当する時間、換言すれば、遅延時間が経過したか否かを判断する（ステップＳ２７）。遅延時間が経過しない場合（ステップＳ２７ Ｎｏ）、遅延部８２４は、ステップＳ２６を繰り返す。遅延時間が経過した場合（ステップＳ２７ Ｙｅｓ）、遅延部８２４は、保持している同期信号を、制御部８２１へ送信する（ステップＳ２８）。

制御部８２１が、宛先レジスタ８２２２の値の中の自ノードの制御レジスタ８２２を指定する値に基づいて、宛先レジスタ８２２２において指定された制御レジスタ８２２のシグナルレジスタ８２２１の値を読む（ステップＳ２９）。続いて、制御部８２１が、シグナルレジスタ８２２１に「１」が設定されているか否かを調べる（ステップＳ２１０）。シグナルレジスタ８２２１に「１」が設定されている場合（ステップＳ２１０ Ｙｅｓ）、同期成立となる。一方、シグナルレジスタ８２２１に「１」が設定されていない場合（ステップＳ２１０ Ｎｏ）、同期は成立していない。

同期が成立していない場合、制御部８２１は、シグナルレジスタ８２２１に「１」を設定し（ステップＳ２１１）、データを演算部８４の記憶装置において制御レジスタ８２２に対応するアドレスに格納する。データは、制御レジスタ８２２が最初のステージである場合には入力データレジスタの値であり、後続のステージである場合には前ステージの演算結果である。

この後、制御部８２１は、他のプロセスからのパケットの受信を待ち合わせ、受信装置８１は、他のプロセスからパケットを受信した場合、受信したパケットに基づいて、データ、同期信号、宛先となる宛先ステージ番号を取り出し、演算部８４、同期部８２へ対応する情報を送信する（ステップＳ２１２）。

同期部８２は、受信装置８１から同期信号、宛先ステージ番号を受信した場合、指定された制御レジスタ８２２のSignalの値を読取る（ステップＳ２１３）。この後、ステップＳ２１０を繰り返す。

一方、ステップＳ２１０において同期が成立している場合（ステップＳ２１０ Ｙｅｓ）、制御部８２１は、制御レジスタ８２２が最後のステージに対応したものか否かを調べる（ステップＳ２１４）。

最後のステージに対応する制御レジスタ８２２で同期が成立した場合（ステップＳ２１４ Ｙｅｓ）、制御部８２１は、演算結果を出力データレジスタ８４２に格納し、設定処理部３１にリダクション演算完了の信号を送信する（ステップＳ２１５）。設定処理部３１は、制御部８２１からのリダクション演算完了の信号を受け取り、出力データレジスタ８４２から演算結果を読み取る（ステップＳ２１６）。

ステップＳ２１４において制御レジスタ８２２が最後のステージに対応したものでない場合（ステップＳ２１４ Ｎｏ）、制御部８２１は、ステップＳ２５を繰り返す。

図１０のリダクション演算装置８は、前述したように、図２のバリア同期装置６と同様にしてバリア同期を実行しつつ、リダクション演算を実行する。従って、図１０のリダクション演算装置８によれば、図９のバタフライによるバリア同期処理における各ステージ間での同期メッセージの流れと同様にして、図１８に示す同期メッセージとリダクション演算の演算途中データとが送受信される。換言すれば、自ノード１における同期メッセージ及び演算途中データの送受信はネットワーク２と同等の遅延を生じる遅延部６２４を介して実行され、他ノード１との間の同期メッセージ及び演算途中データの送受信はネットワーク２を介して実行される。これにより、ノード＃０〜ノード＃３のステージ＃２の各々において、同時に同期が成立する。この結果、バリア同期において、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

図１４は、バリア同期装置を含むノードの構成の他の一例を示す図である。

図１４の例は、遅延計算回路６２１４が遅延値を算出する場合における基準となる値を制御レジスタ６２２に格納する例である。具体的には、図１４に示すように、複数の制御レジスタ６２２の各々において、シグナルレジスタ６２２１及び宛先レジスタ６２２２と共に、遅延時間レジスタ６２２３が設けられる。図１４において、遅延時間レジスタ６２２３は、符号Delay1 を付して表す。

遅延時間レジスタ６２２３は、遅延値の計算の基準となる値を格納する。遅延値の計算の基準となる値は、例えば、ネットワーク２上における通信遅延時間、又は、その補正係数である。例えば、論理ネットワークアドレスにおいてノード１間の距離が「１ホップ」であっても、実際の通信における通信遅延時間が大きく異なる場合がある。この場合、１ホップ当りの通信遅延時間Ｔｄを、遅延時間レジスタ６２２３に格納された基準値を適切な値に変更又は補正することができる。

これにより、各ノード１の間における通信時間がネットワーク２の状態に依存して大きく異なる場合において、複数のプロセスの各々について、プロセス毎に遅延値を補正してプロセス毎に適した遅延処理を実現することができる。この結果、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

図１５は、バリア同期装置を含むノードの構成の更に他の一例を示す図である。

図１５の例は、遅延計算回路６２１４を省略して、遅延値を制御レジスタ６２２に格納する例である。具体的には、図１５に示すように、複数の制御レジスタ６２２の各々において、シグナルレジスタ６２２１及び宛先レジスタ６２２２と共に、遅延値レジスタ６２２４が設けられる。図１５において、遅延値レジスタ６２２４は、符号Delay2 を付して表す。

遅延値レジスタ６２２４は、遅延値を格納する。例えば、ネットワーク２によっては、実際の通信における通信遅延時間を予め知ることができる場合がある。この場合、予め知った通信遅延時間Ｔｄを、遅延時間レジスタ６２２４に遅延値として格納することができる。

これにより、各ノード１の間における通信時間がネットワーク２に依存して予め知ることができる場合において、複数のプロセスの各々について、プロセス毎に遅延値を予め設定してプロセス毎に適した遅延処理を実現することができる。この結果、複数のノードの間における同期の成立のばらつきをほぼ無くすことができる。

以上に説明した並列計算機システムにおいては、バリア同期のアルゴリズムはバタフライ演算によるアルゴリズムによるが、並列計算機システムにおけるバリア同期は、バタフライによるバリア同期に限られない。

例えば、バリア同期のアルゴリズムは、ディスエミネーションであっても良い。これにより、プロセス数が２のべき乗でない場合であっても、並列計算機システムにおいて、ディスエミネーションによるバリア同期処理を実行することができ、また、ディスエミネーションによるバリア同期によるリダクション演算処理を実行することができる。

また、例えば、バリア同期のアルゴリズムは、ペアワイズエクスチェンジウィズリカーシブダブリング（Pairwise exchange with recursive doubling）であっても良い。これにより、プロセス数が２のべき乗でない場合であっても、並列計算機システムにおいて、ペアワイズエクスチェンジウィズリカーシブダブリングによるバリア同期処理を実行することができ、また、ペアワイズエクスチェンジウィズリカーシブダブリングによるバリア同期によるリダクション演算処理を実行することができる。

また、以上に説明した並列計算機システムにおいては、バリア同期装置は各々のノード、換言すれば、プロセッサに設けられるが、これに限られない。

例えば、マルチプロセッサ（マルチプロセッサコア）により構成される並列計算機システムにおいて、バリア同期装置は、各々のノード、換言すれば、プロセッサコアに設けられるのではなく、プロセッサコアとは独立に設けられるようにしても良い。換言すれば、１個のバリア同期装置が、複数のプロセッサコアに共通に設けられるようにしても良い。また、マルチプロセッサにより構成される並列計算機システムにおいて、リダクション演算装置は、各々のノード、換言すれば、プロセッサコアに設けられるのではなく、プロセッサコアとは独立に設けられるようにしても良い。換言すれば、１個のリダクション演算装置が、複数のプロセッサコアに共通に設けられるようにしても良い。

１ ノード
２ ネットワーク
３ ＣＰＵ
４ メモリ
５ システム制御部
６ バリア同期装置
７ ＩＯインタフェース部
８ リダクション演算装置
９ ネットワークインタフェース部
１１ ＩＯ装置
６１、８１ 受信装置
６２、８２ 同期装置（同期部）
６３、８３ 送信装置
６２１、８２１ 制御部
６２２、８２２ 制御レジスタ

Claims (12)

1. 受けるデータの待ち合わせを行ない、前記待ち合わせたデータが揃った場合にデータを送信することにより同期を行う同期装置をそれぞれ備えた複数のノードを有する並列計算機システムにおいて、
   前記複数の同期装置の各々は、
   前記複数の同期装置のうち、自ノードと同期を行う他ノードの同期装置からのデータを受信し、受信した前記他ノードの同期装置からのデータから同期情報を抽出する受信部と、
   前記複数の同期装置のうち、前記自ノードと同期を行う他ノードの同期装置へのデータを送信する送信部と、
   前記抽出した同期情報を保持する受信状態レジスタと、
   データを所定時間だけ遅延させる遅延部と、
   前記受信部が抽出した同期情報と自制御部からの同期情報を、前記受信状態レジスタに保持するとともに、前記受信状態レジスタに前記受信部が抽出した同期情報と自制御部からの同期情報が揃った場合に、前記他ノードへのデータを前記送信部に送信させ、前記自ノードへのデータを、前記遅延部を介して自制御部へ戻す制御部とを含む
   ことを特徴とする並列計算機システム。
2. 前記同期装置の各々は、更に、前記制御部から送信された前記自ノードへのデータを前記制御部へ戻すループ経路を含み、
   前記遅延部は、前記ループ経路に設けられ、
   前記同期装置の各々が有する制御部は、前記自ノードへのデータを送信する場合、前記ループ経路を介してデータを送信する
   ことを特徴とする請求項１に記載の並列計算機システム。
3. 前記所定時間は、前記他ノードへのデータの送信に要する時間と等しい
   ことを特徴とする請求項１又は２に記載の並列計算機システム。
4. 前記複数の同期装置の各々が有する受信部は、更に、受信した前記他ノードの同期装置からのデータから演算対象データを抽出し、
   前記複数の同期装置の各々は、更に、前記抽出した演算対象データを用いて演算を行い、演算結果データを出力するリダクション演算部を含み、
   前記複数の同期装置の各々が有する送信部は、更に、前記他ノードの同期装置へのデータに、前記演算結果データを含めて送信する
   ことを特徴とする請求項１〜３のいずれか１項に記載の並列計算機システム。
5. 前記同期装置の各々が有する制御部は、前記受信状態レジスタに、前記同期を行う全ての同期装置からの同期情報を全て保持した場合に、前記同期を行う２以上の同期装置へのデータを前記送信部にそれぞれ送信させる
   ことを特徴とする請求項１〜４のいずれか１項に記載の並列計算機システム。
6. 前記並列計算機システムは、前記複数の同期装置のうち同期を行う第１の複数の同期装置の組の各々に含まれる複数の同期装置の間で同期を行い、前記第１の複数の同期装置の組の各々に含まれる複数の同期装置の間で同期を完了した後、前記第１の複数の同期装置の組とは異なる第２の複数の同期装置の組の各々に含まれる複数の同期装置の間で同期を行う
   ことを特徴とする請求項１〜５のいずれか１項に記載の並列計算機システム。
7. 並列計算機システムが有するノードにそれぞれ含まれる、受けるデータの待ち合わせを行ない、前記待ち合わせたデータが揃った場合にデータを送信することにより同期を行う複数の同期装置の各々において、
   前記複数の同期装置のうち、自ノードと同期を行う他ノードの同期装置からのデータを受信し、受信した前記他ノードの同期装置からのデータから同期情報を抽出する受信部と、
   前記複数の同期装置のうち、前記自ノードと同期を行う他ノードの同期装置へのデータを送信する送信部と、
   前記抽出した同期情報を保持する受信状態レジスタと、
   データを所定時間だけ遅延させる遅延部と、
   前記受信部が抽出した同期情報と自制御部からの同期情報を、前記受信状態レジスタに保持するとともに、前記受信状態レジスタに前記受信部が抽出した同期情報と自制御部からの同期情報が揃った場合に、前記他ノードへのデータを前記送信部に送信させ、前記自ノードへのデータを、前記遅延部を介して自制御部へ戻す制御部とを有する
   ことを特徴とする同期装置。
8. 前記同期装置の各々は、更に、前記制御部から送信された前記自ノードへのデータを前記制御部へ戻すループ経路を含み、
   前記遅延部は、前記ループ経路に設けられ、
   前記同期装置の各々が有する制御部は、前記自ノードへのデータを送信する場合、前記ループ経路を介してデータを送信する
   ことを特徴とする請求項７に記載の同期装置。
9. 前記所定時間は、前記他ノードへのデータの送信に要する時間と等しい
   ことを特徴とする請求項７又は８に記載の同期装置。
10. 前記複数の同期装置の各々が有する受信部は、更に、受信した前記他ノードの同期装置からのデータから演算対象データを抽出し、
    前記複数の同期装置の各々は、更に、前記抽出した演算対象データを用いて演算を行い、演算結果データを出力するリダクション演算部を含み、
    前記複数の同期装置の各々が有する送信部は、更に、前記他ノードの同期装置へのデータに、前記演算結果データを含めて送信する
    ことを特徴とする請求項７〜９のいずれか１項に記載の同期装置。
11. 前記同期装置の各々が有する制御部は、前記受信状態レジスタに、前記同期を行う全ての同期装置からの同期情報を全て保持した場合に、前記同期を行う２以上の同期装置へのデータを前記送信部にそれぞれ送信させる
    ことを特徴とする請求項７〜１０のいずれか１項に記載の同期装置。
12. 受けるデータの待ち合わせを行ない、前記待ち合わせたデータが揃った場合にデータを送信することにより同期を行う同期装置をそれぞれ備えた複数のノードを有する並列計算機システムの制御方法において、
    前記複数の同期装置の各々が有する受信部が、前記複数の同期装置のうち、自ノードと同期を行う他ノードの同期装置からのデータを受信するステップと、
    前記受信部が、受信した前記他ノードの同期装置からのデータから同期情報を抽出するステップと、
    前記複数の同期装置の各々が有する制御部が、前記受信部が抽出した同期情報を、受信状態レジスタに保持するステップと、
    前記制御部が、前記受信状態レジスタに保持された同期情報に基づき、前記他ノードへのデータを、前記制御部が属する同期装置が有する送信部に送信させるステップと、
    前記制御部が、前記受信状態レジスタに前記受信部が抽出した同期情報と自制御部からの同期情報が揃った場合に、前記自ノードへのデータを、データを所定時間だけ遅延させる遅延部を介して自制御部へ戻すステップとを有する
    ことを特徴とする並列計算機システムの制御方法。

Images