JPH0352057A - 並列計算機構成方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　　　要〕 ハイパーキューブ型の結合をしている並列計算機におい
てホスト計算機とノード間の接続における構成方式に関
し、 ホスト計算機からのデータのロード，アンロードの実現
を共通バスを用いずノード間の通信に用いられるバイパ
ス回路の結合方式で、特に、ハイパーキエーブ型並列計
算機におけるバイパスの結合方式を提供することを目的
とし、 ハイバーキューブ型の結合をする並列計算機において、
並列計算機を構威する複数のノードの内の１つのノード
のバイパス回路の次元を１つだけ高くし、その余った端
子対にホスト計算機を結合することにより、全ノードへ
のデータのロードとアンロードをホスト計算機から直接
各ノードに行うように構成する。

〔産業上の利用分野〕

本発明は、並列計算機の構成方式に係り、さらに詳しく
は、ハイパーキューブ型の結合をしている並列計算機に
おいてホスト計算機とノード間の接続における並列計算
機構成方式に関する。

計算機技術の発展に伴い、逐次計算機を複数台結合する
ことにより処理能力を向上させるため並列計算方式の重
要性が高まってきた。並列計算方式ムこは、共通バスに
複数の計算機を結合するマルチシステム方式や複数の計
算機を隣接結合しデータを流しながらデータのそろった
所で演算を次々に処理するシストリックアレイ方式や他
のアレイ型方式がいろいろと考えられている。このよう
な並列計算機においては、どのような結合方式を採用す
るかということが問題であって、特に計算機の台数が増
えると共通バスを構成するためのハードウェア量が増大
し、また共通バスを共有するためのｆｌｉｌｌ御も複雑
になるという問題がある。

一般に並列計算機を構成する場合、ノードに計算機を配
置した場合のノ一ド間をどのように結合するかというネ
ットワークの構成が重要となる。

ハイパーキューブ型の並列計算機では各ノ一ドに割り振
られたアドレスの２値情報を符号に対応させたとき、そ
の符号間距離が通信の距離に対応するもので、任意のノ
ード間の通信が非常に小さいコストでできるという特徴
を有し、並列計算機を構成する結合方式として非常に注
目されている。

この上うなハイパーキューブ型の並列計算機において、
ホスト計算機と各ノードとの通信をどのように行うかと
いう技術は極めて重要となる。

［従来の技術〕 第７図は従来の並列計算機の構成図である。図中、４１
はホスト計算機、４２は処理プロセッサが置かれるノー
ド、４３は共通バスである。ノードは縦，横にアレイ状
に配直されホスト計算機と共通バスを介して結合される
。しかし一般に各ノ一ドがホスト計算機に直接接続する
と、通信のハードウエア量が増加しコストが向上する．
そのため一般には、図に示すような共通バスの接続を用
いて、ホスト計算機とノードが直接接続されるものと、
他のノードを介して間接的に接続される。

従って、ホスト計算機から各ノードヘデータをロード，
アンロードする時にはこの共通バスを用いて行うことに
なる。

［発明が解決しようとする課題］ 従来技術では共通バスを用いて多数の計算機を接続して
並列計算機を構成する場合、ホスト計算機と通信するノ
ード間にあるノードのバス制御が複雑になる。そのため
に、共通バスを制御するタイミング制御が非常に難しく
なり、共通バスを構成するためのハードウェア量も増大
し、従って、通信コストが高くなるという問題点が生じ
ていた．本発明は、ホスト計算機からのデータのロード
、アンロードの実現を共通バスを用いずノード間の通信
に用いられるバイパスの結合方式で、特に、ハイパーキ
ューブ型並列計算機におけるバイパスの結合方式を目的
とする。

〔課題を解決するための手段〕

第１図に本発明の原理図である。

本発明は、ハイバーキュープ型の結合を有する並列計算
機に関する。

複数のノード１，２，３．４によって並列計算機を構威
し、各ノードはそれぞれ対応するバイパス回路を有する
。各ノードは例えば２次元のときには３つの入出力端子
対を有する。複数のノードのうち１つのノード１のバイ
パス５の次元を１つ高くし、入出力端子対を１つだけ増
加し、その余った入出力端子対Ｄ−Ｄ　”にホスト計算
機６を結合する。そして、全ノード１，２，３．４への
データのロードとアンロードをホスト計算機６から各ノ
ードに入出力端子対Ｄ−Ｄ　’を介して行う。

〔作　　　用〕

本発明では、ハイパーキューブ型結合方式の並列計算機
において、ノード内の１つのノードのバイパスの次元を
１つだけ高くし、その余った次元にホスト計算機と結合
することにより、全ノードヘのデータのロードをホスト
計算機から直接各ノードに行うことをハイバーキューブ
型方式の通信で行うことができるようにしている．従っ
て、共通バスにおいて必要な複雑なタイミング制御の問
題を緩和できる。

〔実　　施　　例〕

次に本発明の実施例を図面を参照して説明する。

第２図はハイパーキューブ結合方式の概念図である。図
中、１１は処理プロセッサが配置されるノード、１２は
通信用バスである。この図では、結合が立方体をなしこ
れを３次元のハイパーキューブ結合と呼ぶ。各ノードに
は３ビットのアドレスが割り振られ、３ビットの各ビッ
トは次元に対応している。すなわち最下位ビットは１次
元に、２ビット目は２次元、最上位ビットは３次元を意
味する。図に示すように３次元をＸ方向，ｙ方向，２方
向に分けると、３点ＯＯＯのノードは最下位ビットを１
にした００１のノードとはＸ方向すなわち１次元の方向
に結合されている。また原点のノードＯＯＯは２ビット
目を１にした０１０のノードとは２次元すなわちｙ方向
に結合されている。

またこの原点にあるＯＯＯのノードは最上位ビットを１
にした１００のノードと２方向すなわち３次元方向に結
合されたものとなっている。０００のノードと１ビット
違いすなわちハミング距離が１のものとはこのように１
本の技で結合されている。これを今距Ｍ１の結合と呼ぶ
ことにする。するとＯＯ１のノードと０１１のノードは
距離１で結合され、これはＯＯＯから見ると距離２で結
合されている。この場合、００１の２ビット目を１にし
たものが０１１で２次元方向に結合されている。０１０
のノードの最下位ビットをｌにすると１次元方向すなわ
ちＸ方向の結合になり、これがノード０１１である。３
ビット目をＯから１に変えると２方向すなわち３次元方
向に結合されるノードが隣接した形で結合される。すな
わちＯＯＯはｉｏｏと結合され、００１！！１０１と結
合され、０１１は１１１と結合され、０１０は１１０と
結合されている。これら上位ビットが１であるノードは
同様にＸ方向．ｙ方向に対してはそれぞれ最下位ビット
及び２ビット目の違いによって結合されている。１００
のノードはＸ方向に１０１と結合され、ｙ方向に１１０
と結合されている．そして１０１はｙ方向に１１１と結
合され、１１０はＸ方向に１１１と結合されている．距
離とノ＼ミング距離とは対応する。ハミング距離が３で
あるならばその間のノード間の距離は３となる。例えば
ＯＯＯのノードと１１１のノードとの距離は３である。

従ってＯＯＯのノードから１１１に通信する場合は距離
３で通信可能となる，０００から００１、１０１、そし
て１１１へは距離３となる。

４次元以上のものも構成することが可能である。

例えば４次元である場合には立方体の中に立方体が含ま
れているもので、各ノードのアドレス情報は４ビットで
あってノード数は１６となる。この場合の最大ハ【ング
距離は４である．従ってどの任意のノード間も距Ｍ４以
内で通信可能となる。

このようなハイパーキエーブ方式の結合方式では、任意
のノード間の通信に係る時間は非常に小さいことが知ら
れている。さらに各ノードにおける通信のバイパス方式
は単純となる。例えば、３次元のハイパーキューブ結合
においては、第２図に示すように、例えばＯＯＯのノー
ドから０１１のノードに通信を行う場合にはＯＯＯと０
１１とのビットの違いを検出し、そのビットの違いに対
応する方向に通信を行えばよいので、０００からＯｌ１
は最下位ビットが異なるためまずＸ方向に進み、２ビッ
ト目も異なるので次にｙ方向に進めばよい。

各ノードには通信のバイパス回路が存在する。

第３図は本発明に利用されるハイバーキューブ用のノー
ドの構成図である。図中、２ｌは処理部であり内部に演
算部とメモリから構威される逐次型計算機である。２２
はバイパスである。バイパスの入力端子及び出力端子は
それぞれ次元よりも１つ多く例えば２次元の場合はＡ，
Ｂ，Ｃの３端子になっている。右側もＡ”，Ｂ”，Ｃ’
の３個ある。第３図では、２次元構造であるので、ノー
ド数は４つであり、００と０１．１０．１１の４つのノ
ードである。例えば００のノードであるならば１次元方
向すなわちＸ方向に対してはＢから入力され、１０の２
次元方向のノードからは端子Ａから入力される．また出
力に対してはノード０１の１次元方向へのノードに対し
てはＡ′の端子から出力され、２次元方向の１０に対し
ては端子Ｂ′から出力される。端子ＣとＣ′はこのノー
ドにある処理部との結合のためであり、演算部とメモリ
から構威される処理部の出力は端子Ｃに結合され、他の
ノードから入ってきた情報をこの処理部に伝達するため
の端子がＣ′である。バイパス回路では交換処理を行う
ことができ、入力のＡ，Ｂ，Ｃの端子と出力のＡ′，Ｂ
’，Ｃ”の結合を任意に変えることができる。例えばＡ
とＣ”，　　ＢとＢ′，ＣとＡ′が結合されれば次元２
からのデータは端子Ａ，Ｃ’を介して自分自身の処理部
に入力され、次元１からの情報はＢ，Ｂ”を介して次元
２の方向にバイパスされ、この処理部からの出力はＣか
らＡ′を介して次元１の方向に出力される。このような
バイパスの交換に対する制御は自分自身の処理部２１が
制御線２３を介して行う。

このバイパス回路はこのようにハイパーキューブの次元
に対応するもので、２次元であれば入出力端子の数はそ
れぞれが３であり、３次元であれば４となる。従来のバ
イパス回路の構成は各ノードとも同じ数の端子数のもの
を用いていたが、本発明では並列計算機を構成するノー
ドのうち１つのノードのバイパスの次元を１つだけ高く
しその余った次元にホスト計算機と結合する。このこと
により、全ノードへのデータのロードをホスト計算機か
ら直接各ノードに行うことにより、ホスト計算機と各ノ
ードを結ぶためのバスのハードウェアが不要となり、並
列計算機の構成をシンプルにするものである。このこと
を次に説明する．第４図はバイパス回路の次元がすべて
同じ場合の２次元構造のハイパーキューブ型並列計算機
の構成図である。図中、００，Ｏｆ．１０．１１はノー
ドである。３０〜３３はバイパス回路である。

各バイパス回路の○印は第３図に示した入出力用の端子
であり、この端子対数は３となる．ノード１のアドレス
は００，ノード２のアドレスは０１，ノード３のアドレ
スは１０，ノード４のアドレスは１１とする。各ノード
の中には処理部があり、その処理結果はＣ端子に入りＣ
′から情報を受ける。２次元構造のハイパーキューブで
あるからノード００と０−１はＸ方向に接続され、ノー
ド３からノード４もＸ方向に結合されている。これらの
結合はＡ及びＡ′とを図のように結合することにより可
能である。また２次元方向に対しても同様であり、ノー
ド１からノード３は端子Ｂ及びＢ′を図のように結合す
ることにより結合され、０１と１１に対しても同様であ
る。本発明はこのようなハイバーキュープ型並列計算機
の構成において、さらに１つのノード例えばノード１の
バイパス回路の次元を１つ増やし、その増やされた端子
にホスト計算機を結合する構成になっている。

第５図は本発明に基づいたハイパーキューブ型並列計算
機の構成の実施例図である． 図中、００，０１，１０．１１はノードである。

３４，３１，３２．３３はバイパス回路である。

各バイパス回路のＯ印は第３図に示した入出力用の端子
であり、この端子対数は３の場合であるが、ノード１の
バイパス回路のみ端子対数が４となっている．ノード１
のアドレスはＯＯ，ノード２のアドレスは０１，ノード
３のアドレスは１０，ノード４のアドレスは１１とする
．各ノードの中には処理部があり、その処理結果はＣ端
子に入りＣ′から情報を受ける。２次元構造のハイパー
キューブであるからノードＯＯと０１はＸ方向に接続さ
れ、ノード３からノード４もＸ方向に結合されている。

これらの結合はＡ及びＡ′とを図のように結合すること
により可能である。また２次元方向に対しても同様であ
り、ノードｌからノード３は端子Ｂ及びＢ′を図のよう
に結合することにより結合され、０１と１１に対しても
同様である．本発明はこのようなハイバーキュープ型並
列計算機の構成において、さらに１つのノード例えばノ
ード１のバイパス回路の次元を１つ増やし、その増やさ
れた端子にホスト計算機を結合する構成になっている． 本発明ではノード１のバイパス回路では端子がＡ，Ｂ，
Ｃ及びＡ’，Ｂ’，Ｃ’ばかりでなくＤとＤ′が存在し
、ちょうどこれは３次元のバイパ・ス回路となっている
．しかしノード２，ノード３，ノード４のバイパス回路
は２次元のままである．ノードエのバーイパス回路のＤ
端子にホスト計算機からの出力を結合し、ホスト計算機
への入力にはＤ′端子を結合する。このバイパス回路す
なわち３次元のバイパス回路の交換動作では入力側端子
Ａ，Ｂ，Ｃ，Ｄと出力側端子Ａ’，Ｂ’，．Ｃ’，Ｄ′
が任意のものが結合可能であるとする。すなわちＡはＡ
”，Ｂ’，Ｃ′，Ｄ’に結合が可能であり、ＢもＡ’，
Ｂ”，Ｃ”，Ｄ”に結合可能であり、ＣやＤもＡ’，Ｂ
”，Ｃ”，Ｄ’のどの端子にも結合可能である。どれら
の結合の制御はノード１で制御するものとする。

第６図は第５図の本発明のハイパーキューブ型並列計算
機の構成においてホスト計算機から各ノードにデータを
転送する場合のロードの実施例図である。第６図（ａ）
はノード１へのデータのロード，第６図（ハ）はノード
２へのデータのロード．第６図（Ｃ）はノード３へのデ
ータのロード，第６図（ｄ）はノード４へのデータのロ
ードの実施例図である。

第６図（ａ）に示すように、ノードＡにホスト計算機か
らデータをロードする場合には、ホスト計算機からのデ
ータはＤ端子に入ってＣ′に抜けそこからノード１に伝
達される。

第６図（ｂ）に示すように、ホスト計算機からノード２
に転送する場合にはホスト計算機からのデータはノード
１のバイパス回路のＤ端子に入ってＡ′に抜け、ノード
２はノード１に対して１次元の方向であるからＡ′から
Ａに転送することが可能であり、ノード２においてＡか
らＣ′にスイッチ交換により転送され、Ｃ′からノード
２の最後に転送される。

第６図（Ｃ）に示すように、ホスト計算機からノード３
へのデータのロードに対してはホスト計算機からのデー
タはノードｌのバイパス端子Ｄに入力され、そこからＢ
′に抜けＢ′からノードエとノード３は２ビット目が違
うアドレスを有するので、２次元方向すなわちｙ方向に
進むことが可能でありそれはＢ′からノード３のＢ端子
への転送となる．そしてノード３のバイパス回路内でＢ
からＣ′に転送されたデータはＣ′からノード３の内部
に転送される。

第６図（イ）はノード４へのデータのロードである．ノ
ードｌからノード４に転送する場合には、アドレスがＯ
Ｏから１１に変わるため、２ビット違いであるから通信
距離は２となる。従って、ノードｌからノード２を介し
てノード４へ通信可能であるが、ここではノードｌから
ノード３そしてノード４へ行くルートで示されている．
すなわちホスト計算機から出力されたデータはノード１
のバイパスのＤ端子に入ってそこでＢ′に抜ける．そし
てｙ方向に進んでノード３のバイパス回路のＢ端子に入
力されＡ′に抜けてＸ方向に転送されそのバイパス回路
でＡからＣ′へ抜けてＣ′からノード４に入力される． このように本発明のハイパーキューブ型並列計算機を用
いてホスト計算機から各ノードへのデータロードに対す
る処理は次のように行われる。

ＳＴＥＰ　　１ ホスト計算機側で、４つのノードのそれぞれにロードす
べきデータを用意する。

ＳＴＥＰ　　２ 各ノードのバイパスの構成を第６図（ａ）のようにして
ホスト計算機からノード１ヘロードすべきデータを送る
。

ＳＴＥＰ　　３ 各ノードのバイパスの構威を第６図（ロ）のようにして
ホスト計算機からノード２ヘロードすべきデータを送る
． ＳＴＥＰ　　４ 各ノードのバイパスの構威を第６図（Ｃ）のようにして
ホスト計算機からノード３ヘロードすべてデータを送る
． ＳＴＥＰ　　　５ 各ノードのバイパスの構成を第６図（２）のようにして
ホスト計算機からノード４ヘロードすべきデータを送る
。

従って、本発明ではこのような処理を行うことによりホ
スト計算機から各ノードへのデータのロードがハイバー
キュープの通信コストで行うことが可能である。

以上はデータのロードに関して説明したが、データのア
ンロードに関しても同様な構成により実現できる。

〔発明の効果〕

本発明によれば、並列計算機を構成するノードのバイパ
ス回路の次元を１つだけ高くし、その余った次元にホス
ト計算機と結合することにより、全ノードへのデータの
ロードをホスト計算機から直接各ノードに行うことによ
り、ホスト計算機と各ノードを結ぶためのバスのハード
ウェアが不要となり、並列計算機の構成をシンプルにし
た．

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図はハイバーキューブ結合方式の概念図、第３図は
本発明に利用されるハイパーキューブ用のノードの構成
図、 第４図はハイパーキューブ型並列計算機のブロック図、 第５図は本発明に基づいたハイパーキューブ型並列計算
機の一実施例のブロック図、 第６図（ａ）〜（ｄ）は第５図においてホスト計算機か
ら各ノードにデータを転送する場合のロードの実施例図
、 第７図は従来の共通バスを持つ並列計算機の構成図であ
る。 １，２，３．４　・　・　・ノード、 ５・・・バイパス回路、 ６・・・ホスト計算機．

Claims (1)

1. 【特許請求の範囲】 １）ハイパーキューブ型の結合をする並列計算機におい
   て、並列計算機を構成する複数のノード（１、２、３、
   ４）の内の１つのノード（１）のバイパス回路（５）の
   次元を１つだけ高くし、その余った端子対（Ｄ−Ｄ′）
   にホスト計算機（６）を結合することにより、全ノード
   へのデータのロードとアンロードをホスト計算機から直
   接各ノードに行う並列計算機構成方式。 ２）各ノード（２、３、４）は、データに対する演算部
   とデータを格納するメモリと、当該ノードと隣接するノ
   ードへそれぞれ結合可能な入力端子及び出力端子とを有
   し、しかもハイパーキューブの次元に対してその次元数
   に等しい入出力端子対数と前記自分自身のノードに接続
   する入出力端子数を加えた数の端子対を入出力にそれぞ
   れ有するバイパス回路を有し、他のノード（１）では、
   そのバイパス回路（５）は入出力端子対を１つだけ多く
   してハイパーキューブの次元よりも１つ多い次元用のバ
   イパス回路と同じ構成にし、その付加された入力端子及
   び出力端子にホスト計算機（６）を結合することを特徴
   とする並列計算機構成方式。