(57)【要約】【課題】並列処理の実行時間を短縮することができるノード間接続装置を提供すること。【解決手段】本発明によれば、複数のノード間において複数の通信ステップで実現される集団通信が可能なノード間接続装置１０が提供される。このノード間接続装置１０は、複数のノードと通信可能に接続された制御送受信部２０と、その制御送受信部２０と接続されたロック制御部３０とを備える。ロック制御部３０は、複数のノードのうち集団通信に参加する参加ノード群のそれぞれに関して通信路のロックを行い、複数の通信ステップにわたって、その通信路のロックを維持する。【選択図】      図４
2006279390.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード間において複数の通信ステップで実現される集団通信を行うノード間接続装置であって、
前記複数のノードと通信可能に接続された制御送受信部と、
前記制御送受信部と接続されたロック制御部と
を具備し、
前記ロック制御部は、前記複数のノードのうち前記集団通信に参加する参加ノード群のそれぞれに関して通信路のロックを行い、前記複数の通信ステップにわたって前記通信路のロックを維持する
ノード間接続装置。
【請求項２】
請求項１に記載のノード間接続装置であって、
前記ロック制御部は、
前記複数のノードのそれぞれに対応して設けられた複数のロック更新判定部と、
前記複数のノードのそれぞれに関して前記ロックの状態を示す集団通信ロックフラグと
を備え、
前記複数のロック更新判定部の各々は、前記参加ノード群中の対応するノードが前記集団通信に参加する残りステップ数を記憶し、
前記集団通信ロックフラグは、前記残りステップ数に基づいて更新される
ノード間接続装置。
【請求項３】
請求項２に記載のノード間接続装置であって、
前記参加ノード群のうち第１ノードは、前記複数の通信ステップの最初のステップにおいて、通信路確保の要求であるロック要求を前記制御送受信部に送信し、
前記制御送受信部は、前記複数のロック更新判定部のうち前記第１ノードに対応する第１ロック更新判定部に格納される前記残りステップ数を、前記ロック要求に示される初期値に設定する
ノード間接続装置。
【請求項４】
請求項３に記載のノード間接続装置であって、
前記残りステップ数は、前記複数の通信ステップが進む毎に更新される
ノード間接続装置。
【請求項５】
請求項３又は４に記載のノード間接続装置であって、
前記第１ノードは、前記複数の通信ステップのうち前記最初のステップより後のステップにおいて、同期要求を前記制御送受信部に送信し、
前記制御送受信部は、前記同期要求に応答して、前記第１ロック更新判定部に格納された前記残りステップ数をデクリメントする
ノード間接続装置。
【請求項６】
請求項５に記載のノード間接続装置であって、
前記ロック制御部は、更に、前記複数のノードのそれぞれに関する前記集団通信への参加状態を示す集団通信参加フラグを備え、
前記第１ロック更新判定部は、前記残りステップ数が１以上の場合、前記集団通信参加フラグのうち前記第１ノードに対応する第１参加ビットを、第１の値に設定し、前記残りステップ数が０未満の場合、前記第１参加ビットを、前記第１の値の反転値である第２の値に設定する
ノード間接続装置。
【請求項７】
請求項６に記載のノード間接続装置であって、
前記集団通信ロックフラグのビット値は、前記集団通信参加フラグのビット値で更新される
ノード間接続装置。
【請求項８】
請求項７に記載のノード間接続装置であって、
前記制御送受信部及び前記ロック制御部に接続されたノード間同期部を更に具備し、
前記ノード間同期部は、
前記複数のノードのそれぞれに対して設けられた同期フラグと、
前記同期フラグをリセットするリセット論理と
を備え、
前記制御送受信部は、前記同期要求に応答して、前記同期フラグのうち前記第１ノードに対応する第１同期ビットを、前記第１の値に設定する
ノード間接続装置。
【請求項９】
請求項８に記載のノード間接続装置であって、
前記制御送受信部は、前記集団通信ロックフラグを参照し、前記参加ノード群の全てに対して前記通信路のロックが行われた場合、ロック要求リプライを前記リセット論理に出力する
ノード間接続装置。
【請求項１０】
請求項９に記載のノード間接続装置であって、
前記制御送受信部は、前記ロック要求リプライを更に前記第１ノードに送信し、
前記第１ノードは、前記ロック要求リプライに応答して、前記ロックされた通信路を用いてデータの送受信を行う
ノード間接続装置。
【請求項１１】
請求項９又は１０に記載のノード間接続装置であって、
前記リセット論理は、前記ロック要求リプライに応答して、前記集団通信ロックフラグのビット値の反転値で前記同期フラグのビット値をリセットする
ノード間接続装置。
【請求項１２】
請求項８乃至１１のいずれかに記載のノード間接続装置であって、
前記制御送受信部は、前記同期フラグの全てのビットが前記第１の値になった場合、同期要求リプライを発行する
ノード間接続装置。
【請求項１３】
請求項１２に記載のノード間接続装置であって、
前記リセット論理は、前記同期要求リプライに応答して、前記集団通信参加フラグのビット値の反転値で前記同期フラグのビット値をリセットする
ノード間接続装置。
【請求項１４】
請求項１２又は１３に記載のノード間接続装置であって、
前記制御送受信部は、前記同期要求リプライを前記ロック制御部に送信し、
前記集団通信ロックフラグのビット値は、前記同期要求リプライに応答して、前記集団通信参加フラグのビット値で更新される
ノード間接続装置。
【請求項１５】
請求項１２乃至１４のいずれかに記載のノード間接続装置であって、
前記制御送受信部は、前記同期要求リプライを更に前記第１ノードに送信し、
前記第１ノードは、前記同期要求リプライに応答して、前記ロックされた通信路を用いてデータの送受信を行う
ノード間接続装置。
【請求項１６】
請求項１乃至１５のいずれかに記載のノード間接続装置であって、
前記集団通信は、ギャザー、全ノードへのギャザー、リダクション、全ノードへのリダクションのいずれかを実行する
ノード間接続装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集団通信が可能な回線交換方式のノード間接続装置に関する。
【背景技術】
【０００２】
コンピュータを用いた処理手法として、「並列処理（Parallel Processing）」が知られている。並列処理によれば、複数の計算ノード（以下、「ノード」と参照される）間で処理の同期、分割、スケジューリングが行われ、複数ノードが協調して処理を行う。また、ノード間の通信として、「集団通信（Collective Communication）」が知られている。集団通信は、複数のプロセスから成るグループに関連した通信として定義されており、集団通信においては、複数のプロセス（ＣＰＵ）が同時に通信を行う。ノード数が多い場合、各ノード間で負荷をバランスさせるために、並列処理の集団通信は、複数の通信ステップで実現されることが一般に知られている。
【０００３】
図１は、集団通信の例を示す概念図である。図１に示される例においては、４つのノードＮ０〜Ｎ３が用いられる。これらノードのうち、データを送信するノードは、「ソースノード（SN; Source Node）」と呼ばれ、一方、データを受信するノードは、「デスティネーションノード（DN; Destination Node）」と呼ばれる。最初の通信ステップにおいて、ノードＮ０（ＳＮ）はノードＮ１（ＤＮ）にデータを送信し、ノードＮ１（ＳＮ）はノードＮ０（ＤＮ）にデータを送信する。また、ノードＮ２（ＳＮ）はノードＮ３（ＤＮ）にデータを送信し、ノードＮ３（ＳＮ）はノードＮ２（ＤＮ）にデータを送信する。その後、各ノードにおいて演算が行われる。次の通信ステップにおいて、ノードＮ０（ＳＮ）はノードＮ２（ＤＮ）にデータを送信し、ノードＮ１（ＳＮ）はノードＮ３（ＤＮ）にデータを送信する。また、ノードＮ２（ＳＮ）はノードＮ０（ＤＮ）にデータを送信し、ノードＮ３（ＳＮ）はノードＮ１（ＤＮ）にデータを送信する。その後、各ノードにおいて演算が行われる。
【０００４】
このような複数のステップからなる集団通信により、ギャザー、全ノードへのギャザー、リダクション、全ノードへのリダクション等の処理が実行される。例えば、ノードＮ０〜Ｎ３のそれぞれがデータＡ〜データＤを有しているとする。この場合、例えばノードＮ０に対する加算によるリダクション処理が実行されると、複数のステップ後に、ノードＮ０にそれらデータの総和Ａ＋Ｂ＋Ｃ＋Ｄが現れる。このような集団通信においては、通信ステップの進行に伴って、ＳＮとＤＮの関係が一定のルール（規則）に従って遷移する。
【０００５】
また、データ通信方式として、回線交換方式とパケット交換方式が知られている。回線交換方式のノード間接続装置は、データを送信するノードであるＳＮからデータを受信するノードであるＤＮへの通信路を確保する必要がある。また、図１に示されたように、回線交換方式のノード間接続装置は、各通信ステップにおいて各ノードが送信先として要求するＤＮが競合しないように制御を行う。
【０００６】
図２は、従来の回線交換方式のノード間接続装置による、複数のステップの通信からなる集団通信の制御例を示す概念図である。この例においては、４つのノードＮ０〜Ｎ３とノード間接続装置が用いられ、全ノードへのリダクション処理が行われるとする。複数の通信ステップで実現される集団通信において、ノード間接続装置は、通信ステップごとに通信路を確保する処理を行う。
【０００７】
図２に示されるように、集団通信の第１ステップにおいて、まず、通信路を確保する処理が行われる。通信路を確保する処理において、各ＳＮは、通信路確保の要求である「ロック要求」をノード間接続装置に送信する。ノード間接続装置は、ＳＮからロック要求を受信した後、そのロック要求に従って通信路（ＤＮ）をロックする処理を行う。通信路のロックに成功した後、ノード間接続装置は、ＳＮに対して通信路確保成功の通知である「ロック要求リプライ」を送信する。各ＳＮは、ロック要求リプライを受信すると、ロックされたＤＮにデータを送信する。その後、各ノードにおいて演算が行われる。
【０００８】
集団通信の第２ステップ以降において、まず、ノード間の同期をとる処理が行われる。同期をとる処理において、ＳＮは、同期確保の要求である「同期要求」をノード間接続装置に送信する。ノード間接続装置は、全ＳＮから同期要求を受信した後、その同期要求に従ってノード間の同期をとる処理を行う。ノード間の同期に成功した後、ノード間接続装置は、ＳＮに対して同期確保成功の通知である「同期要求リプライ」を送信する。次に、各ＳＮは、第１ステップと同様に、ロック要求をノード間接続装置に送信する。ノード間接続装置は、ロック処理を行い、ロック要求リプライをＳＮに送信する。各ＳＮは、ロック要求リプライを受信すると、ロックされたＤＮにデータを送信する。その後、各ノードにおいて演算が行われる。
【０００９】
並列処理やリダクション処理に関連する一般的な技術として、以下のものが知られている。
【００１０】
特許文献１は、並列計算機におけるリダクション処理方法を開示している。並列計算機上でリダクション処理を行う際に、計算機個数が２のべき乗でない場合、端数計算機によって従来行われていた処理が、演算部及び収集部に組み込まれる。これにより、端数計算機が２のべき乗個の計算機に転送するデータ量が削減される。そして、端数計算機の処理にかかる時間が短縮される。
【００１１】
特許文献２は、並列計算機のリダクション処理装置を開示している。このリダクション処理装置は、保持する演算済みの全データを相互に転送する全データ転送手段と、保持する全データを分割し、分割した各部分データをそれぞれ相互に転送する部分データ転送手段と、全データ転送手段による転送と部分データ転送手段による転送とを切り換える切り換え手段とを備える。切り換え手段は、保持する全データを相互に転送する全データ通信法による全体処理時間を演算する。また、切り換え手段は、保持する全データを分割し、分割した各部分データをそれぞれ相互に転送する部分データ通信法による全体処理時間を演算する。そして、切り換え手段は、全体処理時間の短い通信法を選択する。
【００１２】
特許文献３は、複数の処理手段の間で相互に情報を転送することにより各々の処理手段が同期をとって処理を実行する同期処理方法を開示している。この同期処理方法は、（ａ）複数の処理手段でいくつかのプログラムを処理するためにプログラム毎に同期をとるべき処理手段の組み合わせを示す同期組情報を記憶するステップと、（ｂ）自己の処理手段が処理を終了したときに同期待ち状態に至ったことを示す同期状態情報を記憶するステップと、（ｃ）同期状態情報を他の全ての処理手段に送出するステップと、（ｄ）同期組情報に基づき同期組情報により示される全ての処理手段から同期状態情報を受信したか否かを判定するステップと、（ｅ）同期組情報により示される全ての処理手段から同期状態情報が受信された場合、その同期組情報により示される全ての処理手段に対してその同期組情報に対応するプログラムの次の処理に移行させるステップとからなる。
【００１３】
特許文献４は、並列計算機のリダクション処理方法を開示している。この方法は、通信ネットワーク接続された並列計算機により、各々が複数の入力データに依存する複数の出力データを生成する計算を処理するための方法である。そのリダクション処理方法は、ブロードキャスト処理の実行により中間結果を得るステップと、その中間結果に基づいてコンビネーション処理を実行するステップとを含む。
【００１４】
特許文献５は、交換機を開示している。この交換機は、クロスコネクト・スイッチング手段と接続手段とを備えている。クロスコネクト・スイッチング手段は、複数のデータ・ユニットと、入力ポートと、出力ポートとを有している。クロスコネクト・スイッチング手段は、入力ポートにおいて受信したデータを出力ポートに転送するために供されるデータ転送パスを提供する。接続手段は、上記入力ポートに接続され、複数のデータ・ユニットのうちの少なくとも２つに接続される。複数のデータ・ユニットは、入力ポートに関係付けられたデータ・デリバリー・グループを構成する。接続手段は、そのデータ・デリバリー・グループの異なるデータ・ユニットから、それぞれ異なる時間に、上記関係付けられた入力ポートにデータを転送するように動作可能である。
【００１５】
特許文献６は、マルチプロセッサシステムにおける集団通信装置を開示している。この集団通信装置は、プロセッサグループ定義部と、マスタプロセッサ登録更新部と、集団通信実行制御部と、リスト参照集団通信実行部とを備える。プロセッサグループ定義部は、様々な性能レベルの通信経路で繋がった複数のプロセッサについて、均一な性能レベルの通信経路でデータ転送を実現できるプロセッサの集合を定義し、リストを作成する。マスタプロセッサ登録更新部は、通信要求で指定されたｒｏｏｔプロセッサ指示によってリストを更新する。集団通信実行制御部は、集団通信の種類によってリストの実行順序を制御する。リスト参照集団通信実行部は、リストを使って特定なプロセッサの間で集団通信を行う。
【００１６】
【特許文献１】特開２０００−３３９２７８号公報
【特許文献２】特開２００１−３２５２３９号公報
【特許文献３】特開平０６−１８７３０３号公報
【特許文献４】特開平０９−８１５３０号公報
【特許文献５】特開平１０−１１７２００号公報
【特許文献６】特開平１１−１３４３１１号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
一般に、ノード内のＣＰＵの動作速度と比較して、ノード間通信の伝送時間は非常に大きい。また、ノード数の増加とともに集団通信の通信ステップ数は増加する。従って、ノード数が多いほど、並列処理の時間の総和における通信路確保の処理の時間が占める割合は大きくなる。つまり、集団通信における通信路確保処理は、並列処理効率向上を妨げる一因といえる。
【００１８】
本発明の目的は、複数のステップからなる集団通信において、ノード間の通信路を確保するための処理数を削減することができる回線交換方式のノード間接続装置を提供することにある。
【００１９】
本発明の他の目的は、並列処理の実行時間を短縮することができる回線交換方式のノード間接続装置を提供することにある。
【課題を解決するための手段】
【００２０】
以下に、［発明を実施するための最良の形態］で使用される番号・符号を用いて、［課題を解決するための手段］を説明する。これらの番号・符号は、［特許請求の範囲］の記載と［発明を実施するための最良の形態］との対応関係を明らかにするために括弧付きで付加されたものである。ただし、それらの番号・符号を、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。
【００２１】
本発明によれば、複数のノード（Ｎ０〜Ｎ（Ｍ−１））間において複数の通信ステップで実現される集団通信が可能なノード間接続装置（１０）が提供される。このノード間接続装置（１０）は、複数のノードと通信可能に接続された制御送受信部（２０）と、その制御送受信部（２０）と接続されたロック制御部（３０）とを備える。ロック制御部（３０）は、複数のノードのうち集団通信に参加する参加ノード群のそれぞれに関して通信路のロックを行い、複数の通信ステップにわたって、その通信路のロックを維持する。
【００２２】
ロック制御部（３０）は、複数のノードのそれぞれに対応して設けられた複数のロック更新判定部（３１）と、複数のノードのそれぞれに関してロックの状態を示す集団通信ロックフラグ（３３）とを備える。複数のロック更新判定部（３１）の各々は、参加ノード群中の対応するノードが集団通信に参加する「残りステップ数」を記憶する。集団通信ロックフラグ（３３）は、この残りステップ数に基づいて更新される。
【００２３】
参加ノード群のうち第１ノード（Ｎｍ）は、複数の通信ステップの最初のステップにおいて、通信路確保の要求であるロック要求（１０１）を制御送受信部（２０）に送信する。制御送受信部（２０）は、複数のロック更新判定部（３１）のうち上記第１ノード（Ｎｍ）に対応する第１ロック更新判定部（３１−ｍ）に格納される残りステップ数を、ロック要求（１０１）に示される初期値に設定する。この残りステップ数は、複数の通信ステップが進む毎に更新される。
【００２４】
また、第１ノード（Ｎｍ）は、複数の通信ステップのうち最初のステップより後のステップにおいて、同期要求（１０３）を制御送受信部（２０）に送信する。制御送受信部（２０）は、この同期要求（１０３）に応答して、第１ロック更新判定部（３１−ｍ）に格納された残りステップ数をデクリメントする。
【００２５】
ロック制御部（３０）は、更に、複数のノードのそれぞれに関する集団通信への参加状態を示す集団通信参加フラグ（３４）を備える。第１ロック更新判定部（３１−ｍ）は、残りステップ数が１以上の場合、集団通信参加フラグ（３４）のうち第１ノード（Ｎｍ）に対応する第１参加ビットを、第１の値（“１”）に設定する。一方、残りステップ数が０未満の場合、第１ロック更新判定部（３１−ｍ）は、上記第１参加ビットを、第１の値（“１”）の反転値である第２の値（“０”）に設定する。
【００２６】
集団通信ロックフラグ（３３）のビット値は、集団通信参加フラグ（３４）のビット値で更新される。
【００２７】
本発明に係るノード間接続装置（１０）は、更に、制御送受信部（２０）及びロック制御部（３０）に接続されたノード間同期部（４０）を備える。ノード間同期部（４０）は、複数のノードのそれぞれに対して設けられた同期フラグ（４１）と、その同期フラグ（４１）をリセットするリセット論理（４２）とを備える。制御送受信部（２０）は、同期要求（１０３）に応答して、同期フラグ（４１）のうち第１ノード（Ｎｍ）に対応する第１同期ビットを、第１の値（“１”）に設定する。
【００２８】
制御送受信部（２０）は、上述の集団通信ロックフラグ（３３）を参照し、参加ノード群の全てに対して通信路のロックが行われた場合、ロック要求リプライ（２０１）をリセット論理（４２）及び第１ノード（Ｎｍ）に送信する。第１ノード（Ｎｍ）は、このロック要求リプライ（２０１）に応答して、ロックされた通信路を用いてデータ（１０２、１０３）の送受信を行う。
【００２９】
また、制御送受信部（２０）は、上述の同期フラグ（４１）の全てのビットが第１の値（“１”）になった場合、同期要求リプライ（２０３）を発行する。制御送受信部（２０）は、同期要求リプライ（２０３）を、第１ノード（Ｎｍ）及びロック制御部（３０）に送信する。第１ノード（Ｎｍ）は、同期要求リプライ（２０３）に応答して、ロックされた通信路を用いてデータの送受信を行う。
【００３０】
リセット論理（４２）は、ロック要求リプライ（２０１）に応答して、集団通信ロックフラグ（３３）のビット値の反転値で同期フラグ（４１）のビット値をリセットする。また、リセット論理（４２）は、同期要求リプライ（２０３）に応答して、集団通信参加フラグ（３４）のビット値の反転値で同期フラグ（４１）のビット値をリセットする。
【００３１】
集団通信ロックフラグ（３３）のビット値は、同期要求リプライ（２０３）に応答して、集団通信参加フラグ（３４）のビット値で更新される。
【００３２】
上記集団通信として、ギャザー、全ノードへのギャザー、リダクション、全ノードへのリダクションのいずれかが例示される。
【発明の効果】
【００３３】
本発明に係る回線交換方式のノード間接続装置によれば、複数のステップからなる集団通信において、ノード間の通信路を確保するための処理数が削減される。
【００３４】
本発明に係る回線交換方式のノード間接続装置によれば、並列処理の実行時間が短縮される。
【発明を実施するための最良の形態】
【００３５】
添付図面を参照して、本発明によるノード間接続装置を説明する。本発明に係るノード間接続装置は、回線交換方式のノード間接続装置である。また、本発明に係るノード間接続装置は、集団通信を行うことが可能である。集団通信は、複数の通信ステップからなり、通信ステップの進行とともに、ＳＮとＤＮの関係が一定の規則に従って遷移する。そのような集団通信として、ギャザー、全ノードへのギャザー、リダクション、全ノードへのリダクションが例示される。
【００３６】
図３は、本発明のノード間接続装置による、複数のステップの通信からなる集団通信の制御を示す概念図である。この図３に示される例を用いて、本発明の概要を説明する。この例においては、４つのノードＮ０〜Ｎ３とノード間接続装置が用いられ、全ノードへの「リダクション処理」が行われるとする。本発明に係るノード間接続装置は、複数の通信ステップにわたってＤＮ（通信路）のロックを維持する。つまり、本発明によれば、複数の通信ステップで実現される集団通信において、ＤＮのロックが維持されたまま通信ステップが進む。
【００３７】
図３に示されるように、集団通信の第１ステップにおいて、まず、通信路を確保する処理が行われる。通信路を確保する処理において、各ＳＮは、通信路確保の要求である「集団通信ロック要求」をノード間接続装置に送信する。ノード間接続装置は、各ＳＮから集団通信ロック要求を受信した後、その集団通信ロック要求に従って通信路（ＤＮ）をロックする処理を行う。通信路のロックに成功した後、ノード間接続装置は、ＳＮに対して通信路確保成功の通知である「集団通信ロック要求リプライ」を送信する。各ＳＮは、集団通信ロック要求リプライを受信すると、ロックされたＤＮにデータを送信する。その後、各ノードにおいて演算が行われる。
【００３８】
集団通信の第２ステップ以降において、まず、ノード間の同期をとる処理が行われる。同期をとる処理において、ＳＮは、同期確保の要求である「同期要求」をノード間接続装置に送信する。ノード間接続装置は、全ＳＮから同期要求を受信した後、その同期要求に従ってノード間の同期をとる処理を行う。ノード間の同期に成功した後、ノード間接続装置は、ＳＮに対して同期確保成功の通知である「同期要求リプライ」を送信する。各ＳＮは、ロック要求リプライを受信すると、ロックされたＤＮにデータを送信する。その後、各ノードにおいて演算が行われる。この第２ステップにおいて、通信路を確保する処理は行われない。従って、従来技術と比較して、並列処理の実行時間が短縮される。
【００３９】
以下、図３に示された集団通信を伴う並列処理を実現するための構成及び動作が詳しく説明される。
【００４０】
（構成）
図４は、本発明に係る並列処理システム及びノード間接続装置の構成を示すブロック図である。並列処理システム１は、Ｍ台のノードＮ０〜Ｎ（Ｍ−１）からなるノード群と、ノード間接続装置１０を備えている。ノード間接続装置１０は、ノード群のそれぞれと通信可能に接続されている。ノード間接続装置１０は、制御送受信部２０、ロック制御部３０、ノード間同期部４０、及びデータ転送パス５０を備えている。後に示されるように、制御送受信部２０は、Ｍ台のノードＮ０〜Ｎ（Ｍ−１）のそれぞれに接続されたＭ個の制御受信部２１とＭ個の制御送信部２２を有している。ロック制御部３０は、ロック処理の制御と、ロックされるＤＮ（通信路）の維持と更新を行う。ノード間同期部４０は、ノード間の同期の制御を行う。データ転送パス５０は、送信データ及び受信データの転送に用いられる。
【００４１】
各ノードは、集団通信ロック要求１０１をノード間接続装置１０に送信する。その集団通信ロック要求１０１は、制御送受信部２０を通してロック制御部３０に転送される。集団通信ロック要求１０１に応答して、ロック制御部３０は、ロック処理を行い、集団通信ロック要求リプライ２０１を生成する。その集団通信ロック要求リプライ２０１は、制御送受信部２０を通して各ノードに送信される。また、ＳＮは、送信データ１０２を、データ転送パス５０を介してＤＮに送信する。ＤＮは、受信データ２０２を、データ転送パス５０を介してＳＮから受信する。また、各ノードは、同期要求１０３をノード間接続装置１０に送信する。その同期要求１０３は、制御送受信部２０を通して、ロック制御部３０及びノード間同期部４０に転送される。ロック制御部３０は、同期要求１０３に応答して、ロックされるＤＮの維持と更新を行う。ノード間同期部４０は、同期要求１０３に応答して、ノード間の同期処理を行い、同期要求リプライ２０３を生成する。その同期要求リプライ２０３は、制御送受信部２０を通して各ノードに送信される。
【００４２】
図５は、本発明に係るノード間接続装置１０のロック制御部３０の構成を示すブロック図である。ロック制御部３０は、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれと通信可能に接続された制御受信部２１−０〜２１−（Ｍ−１）と接続されている。また、ロック制御部３０は、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれと通信可能に接続された制御送信部２２−０〜２２−（Ｍ−１）と接続されている。ロック制御部３０は、ロック更新判定部３１−０〜３１−（Ｍ−１）、ロック競合調停部３２、集団通信ロックフラグ３３、集団通信参加フラグ３４を備えている。
【００４３】
ロック更新判定部３１−０〜３１−（Ｍ−１）は、それぞれ制御受信部２１−０〜２１−（Ｍ−１）に接続されている。ロック更新判定部３１の各々は、ロックされるＤＮの維持と更新を行う。そのため、ロック更新判定部３１−ｍ（ｍは０以上Ｍ−１以下の整数）は、ノードＮｍがＤＮとして集団通信に参加する残ステップ数を保持するカウンタを備える。ロック競合調停部３２は、制御受信部２１−０〜２１−（Ｍ−１）に接続されている。ロック競合調停部３２は、通信路確保処理の際、通常の競合調停に従い、ロックの取得を行う。
【００４４】
集団通信ロックフラグ３３は、ロック競合調停部３２及び制御送信部２２−０〜２２−（Ｍ−１）に接続されている。集団通信ロックフラグ３３は、ロックを取得したノードを示すためのものであり、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれに対応したＭ個のｂｉｔを持つ。言い換えれば、集団通信ロックフラグ３３は、複数のノードＮ０〜Ｎ（Ｍ−１）のそれぞれに関してロックの状態を示す。集団通信参加フラグ３４は、ロック更新判定部３１と集団通信ロックフラグ３３に接続されている。集団通信参加フラグ３４は、集団通信に参加するノード（参加ノード群）を示すためのものであり、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれに対応したＭ個のｂｉｔを持つ。言い換えれば、集団通信参加フラグ３４は、複数のノードＮ０〜Ｎ（Ｍ−１）のそれぞれに関する集団通信への参加状態を示す。
【００４５】
図６は、本発明に係るノード間接続装置１０のノード間同期部４０の構成を示すブロック図である。ノード間同期部４０は、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれと通信可能に接続された制御受信部２１−０〜２１−（Ｍ−１）と接続されている。また、ノード間同期部４０は、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれと通信可能に接続された制御送信部２２−０〜２２−（Ｍ−１）と接続されている。ノード間同期部４０は、集団通信参加ノード間同期フラグ４１と、リセット論理４２を備えている。
【００４６】
集団通信参加ノード間同期フラグ４１は、制御受信部２１−０〜２１−（Ｍ−１）及び制御送信部２２−０〜２２−（Ｍ−１）に接続されている。集団通信参加ノード間同期フラグ４１は、集団通信に参加するノード（参加ノード群）を示すためのものであり、ノードＮ０〜Ｎ（Ｍ−１）のそれぞれに対応したＭ個のｂｉｔを持つ。リセット論理４２は、集団通信参加ノード間同期フラグ４１に接続されている。リセット論理４２は、ロック制御部３０からの信号に応答して、集団通信参加ノード間同期フラグ４１をリセットする。
【００４７】
（動作）
１．ロック動作
集団通信の複数のステップのうちの第１のステップ（最初のステップ）として、「ロック動作」が行われる。このロック動作は、ノード間接続装置１０が集団通信ロック要求１０１を受信してから、集団通信ロック要求リプライ２０１を送信するまでの動作であり、ロック制御部３０によって行われる。
【００４８】
図７は、本発明に係るロック制御部３０によるロック動作（第１の動作）を示すブロック図である。ノードＮｍから送信された集団通信ロック要求１０１は、制御受信部２１−ｍに入力される。制御受信部２１−ｍは、その集団通信ロック要求１０１に応答して、以下に示される３種類の信号を送出する。
【００４９】
第１として、制御受信部２１−ｍは、ノードＮｍに対応するロック更新判定部３１−ｍに初期設定信号Ｓ１を送出する。この初期設定信号Ｓ１は、ロック更新判定部３１−ｍを初期設定するための信号であり、ロック更新判定部３１−ｍに集団通信のための初期値を設定するための信号である。初期値は集団通信ロック要求１０１に示されている。より具体的には、ロック更新判定部３１−ｍは、ノードＮｍがＤＮとして集団通信に参加する残ステップ数を保持するカウンタを備えている。上述の初期設定信号Ｓ１によって、ノードＮｍが集団通信にＤＮとして参加するステップ数が、そのカウンタの初期値として設定される。このカウンタによって、ノードＮｍを何ステップの間ロックするべきかを把握することができるので、ロックを維持したまま通信ステップを進めることが可能となる。このように、本発明に係るロック制御部３０は、ロックするＤＮ（通信路）を維持・更新するための情報を保持する。
【００５０】
第２として、制御受信部２１−ｍは、ロック競合調停部３２にロック要求信号Ｓ２を送出する。このロック要求信号Ｓ２は、集団通信の第１ステップにおけるデータ送受信のためのロック取得を要求する信号である。このロック要求信号Ｓ２は、ノードＮｍの送信先であるＤＮに関する情報を含む。
【００５１】
ロック競合調停部３２は、ロック要求信号Ｓ２によって要求されたノードのロック取得を行う。つまり、ロック競合調停部３２は、制御受信部２１−ｍからロック要求信号Ｓ２を受けることにより、ノードＮｍが要求するＤＮ（通信路）のロックを取得する。そのロック取得において、ロック競合調停部３２は、周知の競合調停に従う。ロックを取得した後、ロック競合調停部３２は、ロック信号Ｓ３を、ノードＮｍに対応する集団通信ロックフラグ３３のビットｍに送出する。このロック信号Ｓ３により、集団通信ロックフラグ３３のビットｍに“１”が格納される。尚、この集団通信ロックフラグ３３の値は、ロック競合調停の結果に対して優先される。すなわち、集団通信ロックフラグ３３のビットｍが１の間は、ロック競合調停部３２は、ノードＮｍのロックを取得しない。
【００５２】
第３として、制御受信部２１−ｍは、全ての制御送信部２２−０〜２２−（Ｍ−１）に、通知信号Ｓ４を送出する。この通知信号Ｓ４は、ノードＮｍから集団通信ロック要求１０１を受信したことを、全ての制御送信部２２−０〜２２−（Ｍ−１）に通知するための信号である。この通知信号Ｓ４は、ノードＮｍが集団通信に参加するか否かの情報と、ノードＮｍの送信先であるＤＮに関する情報を含む。この通知信号Ｓ４によって、各制御送信部２２は、集団通信にＤＮとして参加するノードを識別する。
【００５３】
制御送信部２２−ｍは、全ての制御受信部２１から通知信号Ｓ４を受信する。また、制御送信部２２−ｍは、集団通信ロックフラグ３３から、ロック取得信号Ｓ５を受信する。このロック取得信号Ｓ５は、Ｍ個のノードＮ０〜Ｎ（Ｍ−１）に関するロック取得状態を示す信号である。尚、このロック取得信号Ｓ５は、制御送信部２２だけでなくノード間同期部４０にも送出される。制御送信部２２−ｍは、ロック取得信号Ｓ５と全ての制御受信部２１からの通知信号Ｓ４に基づいて、集団通信にＤＮとして参加する全てのノード（参加ノード群）がロックを取得しているかどうか判定する。集団通信に参加する全てのノード（参加ノード群）に対する集団通信ロックフラグ３３が“１”となった場合、制御送信部２２−ｍは、ノードＮｍに集団通信ロック要求リプライ２０１を送信する。つまり、制御送信部２２−ｍは、集団通信ロックフラグ３３を参照し、参加ノード群の全てに対してロックが行われた時、集団通信ロック要求リプライ２０１を出力する。尚、集団通信ロック要求リプライ２０１は、ノード間同期部４０にも転送される。
【００５４】
ノードＮｍは、制御送信部２２−ｍから集団通信ロック要求リプライ２０１を受信する。そのノードＮｍは、ノード間接続装置１０のデータ転送パス５０を介して、送信データ１０２をＤＮに送信し、受信データ２０２をＳＮから受信する。このように、集団通信に参加する各ノードは、集団通信ロック要求リプライ２０１を受信した後、送信データ１０２及び受信データ２０２を送受信する。データの送受信をしたノードＮｍは、ノード内で演算を行い、ノード間接続装置１０に対して同期要求１０３を送信する。
【００５５】
以上に示されたように、ロック制御部３０は、複数のノードＮ０〜Ｎｍのうち集団通信に参加する参加ノード群のそれぞれに関して通信路のロックを行う。そして、ロック制御部３０は、後に示されるように、集団通信の複数のステップにわたって、その通信路のロックを維持する。
【００５６】
２．同期動作
集団通信の複数のステップのうちの第２のステップにおいて、「同期動作」が行われる。この同期動作は、ノード間接続装置１０が同期要求１０３を受信してから、同期要求リプライ２０３を送信するまでの動作であり、ノード間同期部４０及びロック制御部３０によって行われる。
【００５７】
図８は、本発明に係るノード間同期部４０による同期動作を示すブロック図である。ノードＮｍから送信された同期要求１０３は、制御受信部２１−ｍに入力される。制御受信部２１−ｍは、その同期要求１０３に応答して、同期要求信号Ｓ６を、ノードＮｍに対応する集団通信参加ノード間同期フラグ４１のビットｍに送出する。この同期要求信号Ｓ６により、集団通信参加ノード間同期フラグ４１のビットｍに“１”が格納される。つまり、制御受信部２１−ｍは、同期要求１０３に応答して、集団通信参加ノード間同期フラグ４１のビットｍを“１”に設定する。
【００５８】
制御送信部２２−ｍは、集団通信参加ノード間同期フラグ４１から、同期信号Ｓ７を受信する。この同期信号Ｓ７は、Ｍ個のノードＮ０〜Ｎ（Ｍ−１）に関する同期状態を示す信号である。制御送信部２２−ｍは、同期信号Ｓ７に基づいて、集団通信参加ノード間同期フラグ４１の全ビットが“１”になっているかどうか判定する。集団通信参加ノード間同期フラグ４１の全てのｂｉｔが“１”になると、制御送信部２２−ｍは、ノードＮｍに同期要求リプライ２０３を発行する。尚、この同期要求リプライ２０３は、ロック制御部３０にも転送される。
【００５９】
一方、ロック制御部３０は、同期要求１０３に応答して、ロック更新判定部３１のカウンタ値を変更して、集団通信ロックフラグ３３を更新する。図９は、本発明に係るロック制御部３０による更新動作（第２の動作）を示すブロック図である。ノードＮｍから送信された同期要求１０３は、制御受信部２１−ｍに入力される。制御受信部２１−ｍは、その同期要求１０３に応答して、ノードＮｍに対応するロック更新判定部３１−ｍに設定変更信号Ｓ８を送出する。この設定変更信号Ｓ８は、ロック更新判定部３１−ｍのカウンタ値（残ステップ数）を変更するための信号である。
【００６０】
上述の通り、ロック更新判定部３１−ｍは、ノードＮｍがＤＮとして集団通信に参加する残ステップ数を保持するカウンタを有している。そして、このカウンタの値は、上記設定変更信号Ｓ８によってデクリメントされる。つまり、制御受信部２１−ｍ（あるいはロック更新判定部３１−ｍ）は、設定変更信号Ｓ８に応答して、ノードＮｍが集団通信にＤＮとして参加する残ステップ数をデクリメントする。
【００６１】
次に、ロック更新判定部３１−ｍは、ノードＮｍにおける集団通信の全通信ステップが終了しているかどうか判定する。その判定の結果、ロック更新判定部３１−ｍは、ノードＮｍに対応する集団通信参加フラグ３４のビットｍに対して、ビット信号Ｓ９を送出する。残ステップ数が１以上の場合、ロック更新判定部３１−ｍは、ビット信号Ｓ９として“１”を送出する。残ステップ数が１未満の場合、ロック更新判定部３１−ｍは、ビット信号Ｓ９として“０”を送出する。つまり、ロック更新判定部３１−ｍは、全通信ステップが終了している場合は、集団通信参加フラグ３４のビットｍを“０”に設定し、終了していない場合は、集団通信参加フラグ３４のビットｍを“１”に設定する。ビット値“０”は、集団通信への不参加を示し、ビット値“１”は、集団通信への参加を示している。
【００６２】
集団通信参加フラグ３４の内容は、更新信号Ｓ１０として集団通信ロックフラグ３３に転送される。ここで、その転送は、ノード間同期部４０から発行される同期要求リプライ２０３を契機に行われる。つまり、集団通信ロックフラグ３３のビットｍは、同期要求リプライ２０３に応答して、集団通信参加フラグ３４のビットｍの値で更新される。言い換えれば、集団通信ロックフラグ３３のビットｍは、ロック更新判定部３１−ｍが有するカウンタ値に基づいて更新される。尚、更新信号Ｓ１０は、ノード間同期部４０にも送信される。
【００６３】
既出の図８に示されるように、ロック制御部３０からのロック取得信号Ｓ５及び更新信号Ｓ１０は、ノード間同期部４０のリセット論理４２に入力される。上述の通り、ロック取得信号Ｓ５及び更新信号Ｓ１０は、集団通信ロックフラグ３３のＭビットの内容を示している。すなわち、ロック取得信号Ｓ５及び更新信号Ｓ１０は、ノードＮ０〜Ｎ（Ｍ−１）の集団通信への参加状態を示している。
【００６４】
リセット論理４２は、ロック制御部３０から集団通信ロック要求リプライ２０１を受け取った時、ロック取得信号Ｓ５を反転させた信号であるｒｅｓｅｔ信号を、集団通信参加ノード同期フラグ４１に出力する。つまり、集団通信ロック要求リプライ２０１の発行を契機として、集団通信ロックフラグ３３のビットｍの反転値が、集団通信参加ノード間同期フラグ４１のビットｍに格納される。また、リセット論理４２は、同期要求リプライ２０３が発行された時、更新信号Ｓ１０を反転させた信号であるｒｅｓｅｔ信号を、集団通信参加ノード同期フラグ４１に出力する。つまり、同期要求リプライ２０３の発行を契機として、集団通信ロックフラグ３３（集団通信参加フラグ３４）のビットｍの反転値が、集団通信参加ノード間同期フラグ４１のビットｍに格納される。リセット論理４２は、例えば、ＮＯＴ（インバータ）により実現される。
【００６５】
このように、リセット論理４２は、集団通信ロック要求リプライ２０１あるいは同期要求リプライ２０３が発行された時に、集団通信ロックフラグ３３の反転値を用いて集団通信参加ノード間同期フラグ４１をリセットする。この動作により、集団通信に参加していないノードに対応する集団通信ノード間同期フラグ４１に“１”が格納される。つまり、不参加ノードに対応するビット値は“１”に固定される。
【００６６】
上述の通り、あるステップ（第ｎステップ）において、集団通信に参加するノードＮｍに対応する制御受信部２１−ｍは、同期要求１０３に応答して、集団通信参加ノード間同期フラグ４１のビットｍを“１”に設定する。集団通信に参加しないノードに対応する集団通信参加ノード間同期フラグ４１のビットは、上記リセット論理４２により“１”に設定されている。これにより、集団通信参加ノード間同期フラグ４１の全てのｂｉｔが“１”となるので、制御送信部２２−ｍは、同期要求リプライ２０３を発行することができる。
【００６７】
また、上述の通り、同じステップ（第ｎステップ）の間に、ロック制御部３０のロック更新判定部３１は、同期要求１０３に応答して、集団通信参加フラグ３４の内容を更新する。具体的には、ロック更新判定部３１−ｍは、ノードＮｍが集団通信にＤＮとして参加する残ステップ数をデクリメントする。残ステップ数が０になった場合、ロック更新判定部３１−ｍは、集団通信参加フラグ３４のビットｍに“０”を格納する。残ステップ数が１以上の場合、ロック更新判定部３１−ｍは、集団通信参加フラグ３４のビットｍに“１”を格納する。この時の集団通信参加フラグ３４の内容は、次のステップ（第ｎ＋１ステップ）におけるノードＮ０〜Ｎ（Ｍ−１）の集団通信への参加状態を示している。つまり、第ｎステップの間に、集団通信参加フラグ３４には、次の第（ｎ＋１）ステップにおける参加状態が予め用意される。そして、第ｎステップの同期要求リプライ２０３に応答して、この集団通信参加フラグ３４の反転値により、集団通信参加ノード間同期フラグ４１が更新される。すなわち、第ｎステップの同期要求リプライ２０３が発行された時、第（ｎ＋１）ステップでの参加・不参加を示す情報が、即座に集団通信参加ノード間同期フラグ４１に格納される。従って、実行時間が削減される。また、ジョブＩＤや、集団通信の管理を行うマスターノードを用いることなく、通信ステップごとの同期を行うことが可能となる。
【００６８】
以上に示されたように、ノード間接続装置１０は、集団通信に参加している複数のノードから同期要求１０３を受信した後に、ロックの状態の更新を行い、また、各ノードに対して同期要求リプライ２０３を送信する。同期要求リプライ２０３を受信したノードは、ノード間接続装置１０のデータ転送パス５０を介して、送信データ１０２をＤＮに送信し、受信データ２０２をＳＮから受信する。このように、集団通信に参加する各ノードは、同期要求リプライ２０３を受信した後、送信データ１０２及び受信データ２０２を送受信する。データの送受信をしたノードＮｍは、ノード内で演算を行い、ノード間接続装置１０に対して同期要求１０３を送信する。以降、ノードＮｍとノード間接続装置１０の間で、同期要求１０３と同期要求リプライ２０３の送受信が繰り返される。これにより、複数の通信ステップにおける送信データ１０２及び受信データ２０２の送受信が実現される。
【００６９】
以上に説明されたように、本発明に係るノード間接続装置１０は、並列処理の集団通信を処理する場合において、ＤＮのロックを維持した状態で通信ステップを進めるように構成されている。これにより、従来集団通信の第２ステップ以降に必要であった、ノード間の通信路を確保するための処理（通信路確保処理）を削減することが可能となる。従って、並列処理の実行時間が短縮される。尚、複数の通信ステップにわたってＤＮのロックを維持するには、次の３つの条件が必要である。第１の条件は、集団通信の各ステップにおいて、ＳＮが要求するＤＮが競合しないことである。第２の条件は、通信ステップの進行とともに、ＳＮとＤＮの関係が一定の規則に従って遷移することである。第３の条件は、通信の第（ｎ＋１）ステップのＤＮが第ｎステップのＤＮに包含されることである。これら３つの条件を満たす集団通信として、ギャザー、全ノードへのギャザー、リダクション、全ノードへのリダクションがある。
【００７０】
本発明によれば、以下に記載される効果が得られる。
【００７１】
第１の効果は、複数の通信ステップで実現される集団通信を用いる並列処理の実行時間を削減できるということである。その理由は、複数の通信ステップで実現される集団通信が行われる際に、その複数の通信ステップにわたってＤＮのロックが維持され、通信の第２ステップ以降の通信路確保処理が削減されるからである。一般に、ノード内のＣＰＵの動作時間に比べて、ノードとノード間接続装置１０の間の信号の伝送時間は非常に長い。よって、通信路確保の処理に伴うロック要求やロック要求リプライの削減は、並列処理の実行時間の短縮に大きく寄与する。
【００７２】
第２の効果は、ジョブＩＤや、集団通信の管理を行うマスターノードを用いることなく、集団通信を行っているノード間のみで、通信ステップごとの同期処理が実行されることである。ノード、もしくはノードで動作するプログラムが、同期をとるべきノードを管理することなく、通信ステップごとの同期処理が実行される。その理由は、第ｎステップの通信において集団通信のロックがされているノード間で、第（ｎ＋１）ステップの同期が行われるからである（第３の条件）。また、第１ステップの通信において、ロックが保持されるべき通信ステップ数が、ノード間接続装置１０に予め設定されるからである。
【００７３】
尚、各ノードが通信ステップ数をカウントし、ロック維持の判定を行ってもよい。この場合、本発明に係るロック更新判定部３１−ｍが、ノードＮｍ内に設けられる。また、同期要求１０３に、ノード間接続装置１０がノードＮｍのロックを維持するかどうかを判定するために用いる情報、もしくは通信ステップ数が付加される。制御受信部２１−ｍは、同期要求１０３を受信すると、集団通信参加フラグ３４のビットｍを更新する。これにより、上述の動作と同様の動作が実現される。
【図面の簡単な説明】
【００７４】
【図１】図１は、集団通信の例を示す概念図である。
【図２】図２は、従来技術に係るノード間接続装置による集団通信制御を示す概念図である。
【図３】図３は、本発明に係るノード間接続装置による集団通信制御を示す概念図である。
【図４】図４は、本発明に係る並列処理システム及びノード間接続装置の構成を示すブロック図である。
【図５】図５は、本発明に係るノード間接続装置のロック制御部の構成を示すブロック図である。
【図６】図６は、本発明に係るノード間接続装置のノード間同期部の構成を示すブロック図である。
【図７】図７は、本発明に係るロック制御部の第１の動作を示すブロック図である。
【図８】図８は、本発明に係るノード間同期部の動作を示すブロック図である。
【図９】図９は、本発明に係るロック制御部の第２の動作を示すブロック図である。
【符号の説明】
【００７５】
１    並列処理システム
１０    ノード間接続装置
２０    制御送受信部
２１    制御受信部
２２    制御送信部
３０    ロック制御部
３１    ロック更新判定部
３２    ロック競合調停部
３３    集団通信ロックフラグ
３４    集団通信参加フラグ
４０    ノード間同期部
４１    集団通信参加ノード間同期フラグ
４２    リセット論理
５０    データ転送パス
１０１    集団通信ロック要求
２０１    集団通信ロック要求リプライ
１０２    送信データ
２０２    受信データ
１０３    同期要求
２０３    同期要求リプライ
【図１】
2006279390.tif 000003
【図２】
2006279390.tif 000004
【図３】
2006279390.tif 000005
【図４】
2006279390.tif 000006
【図５】
2006279390.tif 000007
【図６】
2006279390.tif 000008
【図７】
2006279390.tif 000009
【図８】
2006279390.tif 000010
【図９】
2006279390.tif 000011