JPH07114515A - 同期通信用ネットワークを有する分散メモリ計算機 - Google Patents
同期通信用ネットワークを有する分散メモリ計算機Info
- Publication number
- JPH07114515A JPH07114515A JP5260952A JP26095293A JPH07114515A JP H07114515 A JPH07114515 A JP H07114515A JP 5260952 A JP5260952 A JP 5260952A JP 26095293 A JP26095293 A JP 26095293A JP H07114515 A JPH07114515 A JP H07114515A
- Authority
- JP
- Japan
- Prior art keywords
- node
- communication
- data
- synchronous
- computer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 230000001360 synchronised effect Effects 0.000 title claims abstract description 43
- 230000015654 memory Effects 0.000 title claims abstract description 34
- 238000010586 diagram Methods 0.000 description 6
- 238000003491 array Methods 0.000 description 4
- 238000000034 method Methods 0.000 description 3
- 230000000694 effects Effects 0.000 description 1
Landscapes
- Multi Processors (AREA)
Abstract
(57)【要約】
【目的】通信効率に優れた同期通信用ネットワークを有
する分散メモリ計算機を提供すること。 【構成】プロセッサと通信手段及び通信のために用いる
局所メモリを有する複数のノード計算機と、これらを接
続し相互にデータを交換するためのノード接続ネットワ
ークを有し、かつ、全プロセッサ間で同期をとる必要の
ある変数用の同期メモリと、同期通信手段１１２とをそ
れぞれに有し、かつそれぞれの同期通信手段が前記ノー
ド接続ネットワークとは別のネットワークによって接続
されていること。
する分散メモリ計算機を提供すること。 【構成】プロセッサと通信手段及び通信のために用いる
局所メモリを有する複数のノード計算機と、これらを接
続し相互にデータを交換するためのノード接続ネットワ
ークを有し、かつ、全プロセッサ間で同期をとる必要の
ある変数用の同期メモリと、同期通信手段１１２とをそ
れぞれに有し、かつそれぞれの同期通信手段が前記ノー
ド接続ネットワークとは別のネットワークによって接続
されていること。
Description
【０００１】
【産業上の利用分野】本発明は、分散記憶メモリ並列計
算機に関する。
算機に関する。
【０００２】
【従来の技術】フォートラン等の言語で書かれた科学技
術計算のプログラムを実行するには、従来、スーパーコ
ンピュータ等のベクトル計算機が用いられてきたが、近
年では、並列計算機が用いられるようになってきた。
術計算のプログラムを実行するには、従来、スーパーコ
ンピュータ等のベクトル計算機が用いられてきたが、近
年では、並列計算機が用いられるようになってきた。
【０００３】この並列計算機には、プログラムの取り扱
うデータ量に応じてノード計算機の数を増かすることの
できる分散メモリ並列計算機があり、特に、科学技術計
算に適している。この分散メモリ並列計算機の構成は、
図２に示すように、プロセッサと通信手段及び通信のた
めに用いる局所メモリを有する複数のノード計算機と、
これらを接続し相互にデータを交換するためのノード接
続ネットワークを有するものである。このノード計算機
は、通信手段を除けば、普通の小型計算機とほぼ同じも
のである。また、ノード接続ネットワークは、数個〜数
千個のノード計算機を接続するためのネットワークであ
り、ハイパーキューブ、メッシュ、トーラス、トリー等
様々なトポロジィのネットワークが開発され、使用され
ている。
うデータ量に応じてノード計算機の数を増かすることの
できる分散メモリ並列計算機があり、特に、科学技術計
算に適している。この分散メモリ並列計算機の構成は、
図２に示すように、プロセッサと通信手段及び通信のた
めに用いる局所メモリを有する複数のノード計算機と、
これらを接続し相互にデータを交換するためのノード接
続ネットワークを有するものである。このノード計算機
は、通信手段を除けば、普通の小型計算機とほぼ同じも
のである。また、ノード接続ネットワークは、数個〜数
千個のノード計算機を接続するためのネットワークであ
り、ハイパーキューブ、メッシュ、トーラス、トリー等
様々なトポロジィのネットワークが開発され、使用され
ている。
【０００４】
【発明が解決しようとする課題】このようなノード接続
ネットワークを用いて、複数のノード計算機で、並列計
算する手法として、シングルプログラムマルチプルデー
タ（以下、ＳＰＭＤという。）法と呼ばれるものが知ら
れている。
ネットワークを用いて、複数のノード計算機で、並列計
算する手法として、シングルプログラムマルチプルデー
タ（以下、ＳＰＭＤという。）法と呼ばれるものが知ら
れている。
【０００５】例を挙げて説明すると、図３に示すよう
に、このプログラムでは、データとして、実数ｓ、２つ
の１０００個の要素を持った実数配列ａ（ｉ），ｂ
（ｉ）であり、Ｓ１のｄｏループではｂ（ｉ）を参照し
てａ（ｉ）を計算し、Ｓ２のｄｏループでは、Ｓ１のｄ
ｏループで計算した配列ａ（ｉ）の総和を求めるように
している。この計算を並列して高速に行うために、配列
ａ（ｉ）及びｂ（ｉ）を５００づつの配列に分け、ＳＰ
ＭＤ法によってノード計算機Ｎ１１とＮ１２に実行させ
るプログラム例を、（後に説明するように、細かい点で
完全ではないが、説明のために）模擬的に図４（ａ）及
び（ｂ）に示す。このようにプログラムを作成すると、
図３に示すプログラムでは、それぞれ１０００個あった
配列が、共に、各ノード計算機において半分づつにな
り、同時に計算を行えば、高速に実行できるであろうこ
とが期待できる。
に、このプログラムでは、データとして、実数ｓ、２つ
の１０００個の要素を持った実数配列ａ（ｉ），ｂ
（ｉ）であり、Ｓ１のｄｏループではｂ（ｉ）を参照し
てａ（ｉ）を計算し、Ｓ２のｄｏループでは、Ｓ１のｄ
ｏループで計算した配列ａ（ｉ）の総和を求めるように
している。この計算を並列して高速に行うために、配列
ａ（ｉ）及びｂ（ｉ）を５００づつの配列に分け、ＳＰ
ＭＤ法によってノード計算機Ｎ１１とＮ１２に実行させ
るプログラム例を、（後に説明するように、細かい点で
完全ではないが、説明のために）模擬的に図４（ａ）及
び（ｂ）に示す。このようにプログラムを作成すると、
図３に示すプログラムでは、それぞれ１０００個あった
配列が、共に、各ノード計算機において半分づつにな
り、同時に計算を行えば、高速に実行できるであろうこ
とが期待できる。
【０００６】ところで、ここに挙げた例に用いたａ
（ｉ），ｂ（ｉ）のように、複数のノード計算機に分散
して格納される変数は複値（ポリ）と呼ばれ、プログラ
ム中でこのような複値を参照する場合には、注意を要す
る。というのも、図４のそれぞれのプログラムを同時に
実行すると、ノード計算機Ｎ１１上にはノード計算機Ｎ
１２上におけるｂ（１）に相当するｂ（５０１）が存在
しないので、ｉ＝５００のときに期待した計算結果が得
られないかもしくはエラーとなってしまい、ノード計算
機Ｎ１２上にはノード計算機Ｎ１１上におけるａ（５０
０）に相当するａ（０）が存在せず、同様に期待した計
算結果が得られないかもしくはエラーとなってしまうは
ずである。したがって、ノード計算機Ｎ１１からノード
計算機Ｎ１２に、ノード計算機Ｎ１１上のａ（５００）
を送り、ノード計算機Ｎ１２からノード計算機Ｎ１１
に、ノード計算機Ｎ１２上のｂ（１）を送らなければな
らない。
（ｉ），ｂ（ｉ）のように、複数のノード計算機に分散
して格納される変数は複値（ポリ）と呼ばれ、プログラ
ム中でこのような複値を参照する場合には、注意を要す
る。というのも、図４のそれぞれのプログラムを同時に
実行すると、ノード計算機Ｎ１１上にはノード計算機Ｎ
１２上におけるｂ（１）に相当するｂ（５０１）が存在
しないので、ｉ＝５００のときに期待した計算結果が得
られないかもしくはエラーとなってしまい、ノード計算
機Ｎ１２上にはノード計算機Ｎ１１上におけるａ（５０
０）に相当するａ（０）が存在せず、同様に期待した計
算結果が得られないかもしくはエラーとなってしまうは
ずである。したがって、ノード計算機Ｎ１１からノード
計算機Ｎ１２に、ノード計算機Ｎ１１上のａ（５００）
を送り、ノード計算機Ｎ１２からノード計算機Ｎ１１
に、ノード計算機Ｎ１２上のｂ（１）を送らなければな
らない。
【０００７】このように複値を各ノード計算機上で参照
する場合は、配列を分けた境界等のデータを、隣接する
ノード計算機間で通信する必要がある。図４の例では、
１次元の配列を分けているので、ノード間で通信するデ
ータはそれぞれ１つで済むが、一般的に使用される科学
計算は、配列が２次元以上のことが多く、その場合に
は、複数のデータを通信して交換しなければならない。
する場合は、配列を分けた境界等のデータを、隣接する
ノード計算機間で通信する必要がある。図４の例では、
１次元の配列を分けているので、ノード間で通信するデ
ータはそれぞれ１つで済むが、一般的に使用される科学
計算は、配列が２次元以上のことが多く、その場合に
は、複数のデータを通信して交換しなければならない。
【０００８】この複値を参照するプログラムに起因する
データ通信Ａは、一般的に次のような特徴を有する。 Ａ１．配列要素等の複数のデータを含むブロックを通信
する。 Ａ２．基本的には、ノード間の１対１の通信であり、ノ
ード計算機群全体でみると、境界でのデータの通信であ
って、通信するノードは隣接している場合が多く、局所
的な通信である。
データ通信Ａは、一般的に次のような特徴を有する。 Ａ１．配列要素等の複数のデータを含むブロックを通信
する。 Ａ２．基本的には、ノード間の１対１の通信であり、ノ
ード計算機群全体でみると、境界でのデータの通信であ
って、通信するノードは隣接している場合が多く、局所
的な通信である。
【０００９】一方、図４（ａ）におけるプログラムのｄ
ｏループ文Ｓ１２や、図４（ｂ）におけるプログラムの
ｄｏループ文Ｓ２２は、ｓが単なる変数であり、計算を
行う毎に値を代入しているため、実行する毎に、通信す
る必要がある。このような変数は、単値（モノ）と呼ば
れ、ノード計算機上では、一般にコピーして使用されて
おり、単値のデータは、接続された全てのノード計算機
上に、そのコピーが存在している。したがって、単値を
参照して計算する場合は、そのコピーを参照すればよい
ので、通信する必要はないが、単値に新たな値を代入し
た場合には、全てのノード計算機にコピーしなければな
らない。
ｏループ文Ｓ１２や、図４（ｂ）におけるプログラムの
ｄｏループ文Ｓ２２は、ｓが単なる変数であり、計算を
行う毎に値を代入しているため、実行する毎に、通信す
る必要がある。このような変数は、単値（モノ）と呼ば
れ、ノード計算機上では、一般にコピーして使用されて
おり、単値のデータは、接続された全てのノード計算機
上に、そのコピーが存在している。したがって、単値を
参照して計算する場合は、そのコピーを参照すればよい
ので、通信する必要はないが、単値に新たな値を代入し
た場合には、全てのノード計算機にコピーしなければな
らない。
【００１０】この単値に新たに値を代入することに起因
するデータ通信Ｂは、一般的に次のような特徴を有す
る。 Ｂ１．通信するデータは、比較的少ない。 Ｂ２．接続されたノード計算機全てが、同期的に参加す
る、広域的な通信である。
するデータ通信Ｂは、一般的に次のような特徴を有す
る。 Ｂ１．通信するデータは、比較的少ない。 Ｂ２．接続されたノード計算機全てが、同期的に参加す
る、広域的な通信である。
【００１１】図４に示すような単純なプログラムであれ
ば、データ通信Ａとデータ通信Ｂは、複値参照のプログ
ラムであるｄｏループ文Ｓ１１及びＳ２１と、単値に新
たに代入されるプログラムであるｄｏループ文Ｓ１２及
びＳ２２とが、別のループとなっているので問題は発生
しないが、一般に行われるプログラムでは、このデータ
通信Ａとデータ通信Ｂが、同一のループ内に存在する
等、同時に発生する場合が多く、一つのノード接続ネッ
トワーク上に、全く性質の異なる通信が混在するため、
通信効率の低下をまねいていた。
ば、データ通信Ａとデータ通信Ｂは、複値参照のプログ
ラムであるｄｏループ文Ｓ１１及びＳ２１と、単値に新
たに代入されるプログラムであるｄｏループ文Ｓ１２及
びＳ２２とが、別のループとなっているので問題は発生
しないが、一般に行われるプログラムでは、このデータ
通信Ａとデータ通信Ｂが、同一のループ内に存在する
等、同時に発生する場合が多く、一つのノード接続ネッ
トワーク上に、全く性質の異なる通信が混在するため、
通信効率の低下をまねいていた。
【００１２】本発明は、通信効率に優れた同期通信用ネ
ットワークを有する分散メモリ計算機を提供することを
目的とするものである。
ットワークを有する分散メモリ計算機を提供することを
目的とするものである。
【００１３】
【課題を解決するための手段】本発明の同期通信用ネッ
トワークを有する分散メモリ計算機は、図１に示すよう
に、プロセッサと通信手段及び通信のために用いる局所
メモリを有する複数のノード計算機と、これらを接続し
相互にデータを交換するためのノード接続ネットワーク
を有する分散メモリ計算機において、全プロセッサ間で
同期をとる必要のある変数用の同期メモリと、同期通信
手段１１２とをそれぞれに有し、かつそれぞれの同期通
信手段が前記ノード接続ネットワークとは別のネットワ
ークによって接続されていることを特徴とする。
トワークを有する分散メモリ計算機は、図１に示すよう
に、プロセッサと通信手段及び通信のために用いる局所
メモリを有する複数のノード計算機と、これらを接続し
相互にデータを交換するためのノード接続ネットワーク
を有する分散メモリ計算機において、全プロセッサ間で
同期をとる必要のある変数用の同期メモリと、同期通信
手段１１２とをそれぞれに有し、かつそれぞれの同期通
信手段が前記ノード接続ネットワークとは別のネットワ
ークによって接続されていることを特徴とする。
【００１４】ノード接続ネットワークの接続トポロジィ
としては、前述のように、通信するデータは、比較的少
なく、接続されたノード計算機全てが、同期的に参加す
る、広域的な通信であるため、メッシュを用いることが
好ましい。
としては、前述のように、通信するデータは、比較的少
なく、接続されたノード計算機全てが、同期的に参加す
る、広域的な通信であるため、メッシュを用いることが
好ましい。
【００１５】同期通信ネットワークの接続トポロジィと
しては、前述のように、配列要素等の複数のデータを含
むブロックを通信するものであり、かつ基本的には、ノ
ード間の１対１の通信であり、局所的な通信であること
から、トリーを用いることが好ましい。
しては、前述のように、配列要素等の複数のデータを含
むブロックを通信するものであり、かつ基本的には、ノ
ード間の１対１の通信であり、局所的な通信であること
から、トリーを用いることが好ましい。
【００１６】本発明において、同期メモリは、データメ
モリと最終書換時刻を示すタイムスタンプメモリとを含
むことが好ましく、さらにはデータメモリとデータに対
する同期処理の内容を格納するメモリを含むことが好ま
しい。
モリと最終書換時刻を示すタイムスタンプメモリとを含
むことが好ましく、さらにはデータメモリとデータに対
する同期処理の内容を格納するメモリを含むことが好ま
しい。
【００１７】
【作用】本発明では、２つのネットワークを用いたの
で、性質の異なる局所的な通信と広域的な通信とを、同
時に行うことができる。
で、性質の異なる局所的な通信と広域的な通信とを、同
時に行うことができる。
【００１８】
《ノード接続ネットワーク》図６に、本発明の実施例に
使用したノード接続ネットワークを示す。このネットワ
ークは、ノード計算機Ｎ１，Ｎ２，Ｎ３，Ｎ４と、ノー
ド計算機と同数のノードＣ１，Ｃ２，Ｃ３，Ｃ４と、ノ
ード間の通信路Ｌ１，Ｌ２，Ｌ３，Ｌ４と、ノードと計
算機との通信路ＮＬ１，ＮＬ２，ＮＬ３，ＮＬ４から構
成され、メッシュ接続してある。この構成では、例えば
Ｃ１とＣ２、あるいはＣ１とＣ４のように、通信ノード
が直接接続されているノード計算機同志は、直接通信を
行い、例えばＣ１とＣ４、あるいはＣ２とＣ３のよう
に、通信ノードが直接接続されていないノード計算機同
志は、介在する通信ノードが別の通信ノードへデータを
渡すことによって、通信が行われる。このネットワーク
の特徴は、以下のとおりである。 隣接するノード計算機同志の通信が最も速く通信で
きる。 １辺がＮ個の正方メッシュにノード計算機が接続さ
れた場合、最長の通信距離（時間）は、２つのノード計
算機間の通信距離の約２（Ｎ−１）倍である。
使用したノード接続ネットワークを示す。このネットワ
ークは、ノード計算機Ｎ１，Ｎ２，Ｎ３，Ｎ４と、ノー
ド計算機と同数のノードＣ１，Ｃ２，Ｃ３，Ｃ４と、ノ
ード間の通信路Ｌ１，Ｌ２，Ｌ３，Ｌ４と、ノードと計
算機との通信路ＮＬ１，ＮＬ２，ＮＬ３，ＮＬ４から構
成され、メッシュ接続してある。この構成では、例えば
Ｃ１とＣ２、あるいはＣ１とＣ４のように、通信ノード
が直接接続されているノード計算機同志は、直接通信を
行い、例えばＣ１とＣ４、あるいはＣ２とＣ３のよう
に、通信ノードが直接接続されていないノード計算機同
志は、介在する通信ノードが別の通信ノードへデータを
渡すことによって、通信が行われる。このネットワーク
の特徴は、以下のとおりである。 隣接するノード計算機同志の通信が最も速く通信で
きる。 １辺がＮ個の正方メッシュにノード計算機が接続さ
れた場合、最長の通信距離（時間）は、２つのノード計
算機間の通信距離の約２（Ｎ−１）倍である。
【００１９】《同期通信ネットワーク》図７に、本発明
の実施例に用いた同期通信ネットワークを示す。このネ
ットワークは、ルート同志が接続された２つのトリーネ
ットワークから構成され、入力側のトリーは、同期通信
マージノードＭ１，Ｍ２，Ｍ３，Ｍ４から構成され、出
力側のトリーは、同期通信フォークノードＦ１，Ｆ２，
Ｆ３，Ｆ４から構成されている。４つのノード計算機
は、それぞれのマージノードと、入力用通信路Ｉ１，Ｉ
２，Ｉ３，Ｉ４、及び、それぞれのフォークノードと、
出力通信用路Ｏ１，Ｏ２，Ｏ３，Ｏ４で接続され、全ノ
ード計算機が参加する同期通信を行うものである。例え
ば、このネットワークによって構成された全ノード計算
機が、各ノード計算機の持つデータの加算を行うとき
は、 (1) 各ノード計算機は、それぞれ、同期メモリを介して
接続されたマージノードに加算したいデータを出力す
る。 (2) 同期通信ネットワーク内では、ノード計算機Ｎ１と
Ｎ２のデータの加算をマージノードＭ１で行い、同時
に、ノード計算機Ｎ３とＮ４のデータの加算を、マージ
ノードＭ２で行う。 (3) 次にマージノードＭ１とマージノードＭ２の結果
を、マージノードＭ３で加算する。 (4) 結果を、フォークノードＦ１にコピーする。 (5) フォークノードＦ１からフォークノードＦ２，Ｆ３
にデータを送る。 (6) フォークノードＦ２からノード計算機Ｎ１とＮ２に
データを送るり、フォークノードＦ３からノード計算機
Ｎ３，Ｎ４にデータを送る。 この結果、一定時間後に、それぞれのノード計算機は、
全ての加算結果を得ることができる。
の実施例に用いた同期通信ネットワークを示す。このネ
ットワークは、ルート同志が接続された２つのトリーネ
ットワークから構成され、入力側のトリーは、同期通信
マージノードＭ１，Ｍ２，Ｍ３，Ｍ４から構成され、出
力側のトリーは、同期通信フォークノードＦ１，Ｆ２，
Ｆ３，Ｆ４から構成されている。４つのノード計算機
は、それぞれのマージノードと、入力用通信路Ｉ１，Ｉ
２，Ｉ３，Ｉ４、及び、それぞれのフォークノードと、
出力通信用路Ｏ１，Ｏ２，Ｏ３，Ｏ４で接続され、全ノ
ード計算機が参加する同期通信を行うものである。例え
ば、このネットワークによって構成された全ノード計算
機が、各ノード計算機の持つデータの加算を行うとき
は、 (1) 各ノード計算機は、それぞれ、同期メモリを介して
接続されたマージノードに加算したいデータを出力す
る。 (2) 同期通信ネットワーク内では、ノード計算機Ｎ１と
Ｎ２のデータの加算をマージノードＭ１で行い、同時
に、ノード計算機Ｎ３とＮ４のデータの加算を、マージ
ノードＭ２で行う。 (3) 次にマージノードＭ１とマージノードＭ２の結果
を、マージノードＭ３で加算する。 (4) 結果を、フォークノードＦ１にコピーする。 (5) フォークノードＦ１からフォークノードＦ２，Ｆ３
にデータを送る。 (6) フォークノードＦ２からノード計算機Ｎ１とＮ２に
データを送るり、フォークノードＦ３からノード計算機
Ｎ３，Ｎ４にデータを送る。 この結果、一定時間後に、それぞれのノード計算機は、
全ての加算結果を得ることができる。
【００２０】（マージノード）図８に、本発明に用いた
マージノードの構成を示す。この同期マージノードは、
２つの入力ＭＩ１、ＭＩ２に接続されたキューＱ１、Ｑ
２と、データの種類を比較する比較機ＣＯＭＰと、デー
タの演算を行う演算器Ｐから構成され、演算結果はＭＯ
から出力される。本発明に用いた同期通信データは、そ
の構成を図９に示すように、データの書換時間を示すタ
イムスタンプＴＭと、全ノード計算機で行う処理の内容
である演算指示ＯＰと、それぞれのノード計算機の持つ
データＤＡＴＡとで構成している。ここで、本発明に使
用したマージノードの動作を以下に説明する。まず、各
ノード計算機から出力されたデータは、それぞれ、マー
ジノード内のキューＱ１またはＱ２に入力され、比較機
ＣＯＭＰでは、Ｑ１とＱ２のタイムスタンプＴＭと演算
指示ＯＰが一致するのを待ち、一致すれば、演算指示を
演算器Ｐに送り、演算器Ｐは、その指示にしたがって演
算を行い、その結果をＭＯから出力する。
マージノードの構成を示す。この同期マージノードは、
２つの入力ＭＩ１、ＭＩ２に接続されたキューＱ１、Ｑ
２と、データの種類を比較する比較機ＣＯＭＰと、デー
タの演算を行う演算器Ｐから構成され、演算結果はＭＯ
から出力される。本発明に用いた同期通信データは、そ
の構成を図９に示すように、データの書換時間を示すタ
イムスタンプＴＭと、全ノード計算機で行う処理の内容
である演算指示ＯＰと、それぞれのノード計算機の持つ
データＤＡＴＡとで構成している。ここで、本発明に使
用したマージノードの動作を以下に説明する。まず、各
ノード計算機から出力されたデータは、それぞれ、マー
ジノード内のキューＱ１またはＱ２に入力され、比較機
ＣＯＭＰでは、Ｑ１とＱ２のタイムスタンプＴＭと演算
指示ＯＰが一致するのを待ち、一致すれば、演算指示を
演算器Ｐに送り、演算器Ｐは、その指示にしたがって演
算を行い、その結果をＭＯから出力する。
【００２１】（フォークノード）図１０に、本発明に用
いたフォークノードの構成を示す。このフォークノード
は、ノード内のコピー器Ｄが、入力されたデータを複写
して、２つの出力ＦＯ１及びＦＯ２から出力する。
いたフォークノードの構成を示す。このフォークノード
は、ノード内のコピー器Ｄが、入力されたデータを複写
して、２つの出力ＦＯ１及びＦＯ２から出力する。
【００２２】（特徴）このようなトリー形の同期通信ネ
ットワークは、以下のような特徴を有する。 通信は同期しており、すべてのノード計算機が、通
信に同じ時間を要する。 １辺がＮ個の正方メッシュを有するノード計算機の
場合、この同期通信ネットワークの最長通信時間は、２
つのノード計算機間の通信の約 ２＊ＬＯＧ2Ｎ 倍である。
ットワークは、以下のような特徴を有する。 通信は同期しており、すべてのノード計算機が、通
信に同じ時間を要する。 １辺がＮ個の正方メッシュを有するノード計算機の
場合、この同期通信ネットワークの最長通信時間は、２
つのノード計算機間の通信の約 ２＊ＬＯＧ2Ｎ 倍である。
【００２３】
【発明の効果】以上に説明したように、本発明によっ
て、複値のデータの参照に対しては、 隣接するノード計算機同志の通信が最も速く通信で
きる。 １辺がＮ個の正方メッシュにノード計算機が接続さ
れた場合でも、最長の通信距離（時間）は、たかだか２
つのノード計算機間の通信距離の約２（Ｎ−１）倍であ
り、単値に新たに値を代入することに対しては、 通信は同期しており、すべてのノード計算機が、通
信に同じ時間を要する。 １辺がＮ個の正方メッシュを有するノード計算機の
場合、この同期通信ネットワークの最長通信時間は、２
つのノード計算機間の通信の約２＊ＬＯＧ2Ｎ倍である
ことを同時に満足することができ、このことから （１）配列要素等の複数のデータを、比較的大きなパケ
ットが必要なブロックデータ用に設計・最適化を行うこ
とができる。 （２）隣接するノード計算機間での通信が高速であり、
局所的な通信を効率的に行うことが可能である。 （３）接続されたノード計算機全てが、同期的に参加す
る、広域的な通信が可能であり、全体通信やレダクショ
ンを高速に実行できる。 （４）通信するデータが比較的少ない通信に適してお
り、通信パケットも小さいものに最適化できる。 という２つの効果を同時に有する同期通信用ネットワー
クを有する分散メモリ計算機を提供することができる。
て、複値のデータの参照に対しては、 隣接するノード計算機同志の通信が最も速く通信で
きる。 １辺がＮ個の正方メッシュにノード計算機が接続さ
れた場合でも、最長の通信距離（時間）は、たかだか２
つのノード計算機間の通信距離の約２（Ｎ−１）倍であ
り、単値に新たに値を代入することに対しては、 通信は同期しており、すべてのノード計算機が、通
信に同じ時間を要する。 １辺がＮ個の正方メッシュを有するノード計算機の
場合、この同期通信ネットワークの最長通信時間は、２
つのノード計算機間の通信の約２＊ＬＯＧ2Ｎ倍である
ことを同時に満足することができ、このことから （１）配列要素等の複数のデータを、比較的大きなパケ
ットが必要なブロックデータ用に設計・最適化を行うこ
とができる。 （２）隣接するノード計算機間での通信が高速であり、
局所的な通信を効率的に行うことが可能である。 （３）接続されたノード計算機全てが、同期的に参加す
る、広域的な通信が可能であり、全体通信やレダクショ
ンを高速に実行できる。 （４）通信するデータが比較的少ない通信に適してお
り、通信パケットも小さいものに最適化できる。 という２つの効果を同時に有する同期通信用ネットワー
クを有する分散メモリ計算機を提供することができる。
【図１】本発明の原理を説明するためのブロック図であ
る。
る。
【図２】従来例を説明するためのブロック図である。
【図３】本発明の課題を説明するためのプログラム例で
ある。
ある。
【図４】（ａ）及び（ｂ）は、それぞれ本発明の課題を
説明するためのプログラム例である。
説明するためのプログラム例である。
【図５】本発明の課題を説明するための表である。
【図６】本発明の一実施例の一部を示す構成概略図であ
る。
る。
【図７】本発明の一実施例を示す他の一部の構成概略図
である。
である。
【図８】図７の同期通信マージノードの構成を示すブロ
ック図である。
ック図である。
【図９】本発明の同期通信に用いたデータの構成を示す
表である。
表である。
【図１０】図７の同期通信フォークノードの構成を示す
ブロック図である。
ブロック図である。
Claims (5)
- 【請求項１】プロセッサと通信手段及び通信のために用
いる局所メモリを有する複数のノード計算機と、これら
を接続し相互にデータを交換するためのノード接続ネッ
トワークを有する分散メモリ計算機において、 全プロセッサ間で同期をとる必要のある変数用の同期メ
モリと、同期通信手段１１２とをそれぞれに有し、かつ
それぞれの同期通信手段が前記ノード接続ネットワーク
とは別のネットワークによって接続されていることを特
徴とする同期通信用ネットワークを有する分散メモリ計
算機。 - 【請求項２】ノード接続ネットワークの接続トポロジィ
として、メッシュを用いたことを特徴とする請求項１に
記載の同期通信用ネットワークを有する分散メモリ計算
機。 - 【請求項３】同期通信ネットワークの接続トポロジィと
して、トリーを用いたことを特徴とする請求項１または
２に記載の同期通信用ネットワークを有する分散メモリ
計算機。 - 【請求項４】同期メモリが、データメモリと最終書換時
刻を示すタイムスタンプメモリとを含むことを特徴とす
る請求項１〜３のうちいずれかに記載の同期通信用ネッ
トワークを有する分散メモリ計算機。 - 【請求項５】同期メモリが、データメモリとデータに対
する同期処理の内容を格納するメモリを含むことを特徴
とする請求項１〜４のうちいずれかに記載の同期通信用
ネットワークを有する分散メモリ計算機。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5260952A JPH07114515A (ja) | 1993-10-19 | 1993-10-19 | 同期通信用ネットワークを有する分散メモリ計算機 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5260952A JPH07114515A (ja) | 1993-10-19 | 1993-10-19 | 同期通信用ネットワークを有する分散メモリ計算機 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH07114515A true JPH07114515A (ja) | 1995-05-02 |
Family
ID=17355056
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5260952A Pending JPH07114515A (ja) | 1993-10-19 | 1993-10-19 | 同期通信用ネットワークを有する分散メモリ計算機 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07114515A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH10187534A (ja) * | 1996-09-27 | 1998-07-21 | Hewlett Packard Co <Hp> | コヒーレントメモリシステムにおいて強い順序づけを維持する方法およびシステム |
| JP2007509439A (ja) * | 2003-10-22 | 2007-04-12 | インテル コーポレイション | 相互接続ネットワークでの効率的な順序保存用の方法及び装置 |
| JP2012058958A (ja) * | 2010-09-08 | 2012-03-22 | Fujitsu Ltd | リダクション演算装置、処理装置及びコンピュータシステム |
| JP2013246584A (ja) * | 2012-05-24 | 2013-12-09 | Mitsubishi Electric Corp | 制御装置、データ出力制御ユニット、データ入力制御ユニット、および制御ユニット |
-
1993
- 1993-10-19 JP JP5260952A patent/JPH07114515A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH10187534A (ja) * | 1996-09-27 | 1998-07-21 | Hewlett Packard Co <Hp> | コヒーレントメモリシステムにおいて強い順序づけを維持する方法およびシステム |
| JP2007509439A (ja) * | 2003-10-22 | 2007-04-12 | インテル コーポレイション | 相互接続ネットワークでの効率的な順序保存用の方法及び装置 |
| JP2012058958A (ja) * | 2010-09-08 | 2012-03-22 | Fujitsu Ltd | リダクション演算装置、処理装置及びコンピュータシステム |
| JP2013246584A (ja) * | 2012-05-24 | 2013-12-09 | Mitsubishi Electric Corp | 制御装置、データ出力制御ユニット、データ入力制御ユニット、および制御ユニット |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Wang et al. | Blink: Fast and generic collectives for distributed ml | |
| US5170482A (en) | Improved hypercube topology for multiprocessor computer systems | |
| Hoefler et al. | Hammingmesh: A network topology for large-scale deep learning | |
| US7418470B2 (en) | Parallel processing systems and method | |
| US5944779A (en) | Cluster of workstations for solving compute-intensive applications by exchanging interim computation results using a two phase communication protocol | |
| JP2512661B2 (ja) | 非バイナリ・ハイパ―キュ―ブ形式のコンピュ―タ・システムおよびネットワ―クにおける複数ノ―ドの接続方法 | |
| Li et al. | Efficient collective communications in dual-cube | |
| US11531637B2 (en) | Embedding rings on a toroid computer network | |
| EP1502203A2 (en) | Parallel processing systems and method | |
| Zhao et al. | Efficient {Direct-Connect} Topologies for Collective Communications | |
| Kobus et al. | Gossip: Efficient communication primitives for multi-gpu systems | |
| Abali et al. | Routing algorithms for IBM SP1 | |
| Liszka et al. | Problems with comparing interconnection networks: Is an alligator better than an armadillo? | |
| JPH07114515A (ja) | 同期通信用ネットワークを有する分散メモリ計算機 | |
| KR102801506B1 (ko) | 토로이드 컴퓨터 네트워크 상의 내포된 링들 | |
| Yeh et al. | Routing and embeddings in cyclic Petersen networks: an efficient extension of the Petersen graph | |
| Pritchard et al. | Cube connected Mobius ladders: An inherently deadlock-free fixed degree network | |
| Kumar et al. | Hierarchical communication optimization for fft | |
| Romashikhin | Implementation of Regular Topologies for NoCs Based on schoolMIPS Soft-Processor Cores | |
| Schomberg | A transputer-based shuffle-shift machine for image processing and reconstruction | |
| Gomez-Lopez et al. | Implementation and Evaluation of a Hybrid Network Topology in an Infiniband-based HPC cluster | |
| WO1989001665A1 (en) | Hypercube topology for multiprocessor systems with added communication paths between nodes or substituted corner topologies | |
| Yang et al. | Adaptive wormhole routing in k-ary n-cubes | |
| Xu et al. | ComPaSS: a communication package for scalable software design | |
| Mišić | Unicast-based multicast algorithm in wormhole-routed star graph interconnection networks |