JPH01131950A - 相互結合ネツトワークおよびそのためのクロスバスイツチ - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は並列計算機の要素プロセッサの相互結合方式に
係り、特に高い結合能力が必要でありながらプロセッサ
台数が多くてフルクロスバスイッチでは全部を結合出来
ない場合に好適なスイッチ構成に関する。

〔従来の技術〕

従来の装置は、各要素プロセッサを一本または数本のバ
スに結合する一般的な方法の他、特開昭５８−１８１１
６８に記載のように、格子状に配列された要素プロセッ
サの隣合うもの同士を結合する方式、特開昭５９−１０
９９６６に記載のように、全要素プロセッサを（フル）
クロスバスイッチで結合する方式、特開昭６２−２３５
３に記載のように、全要素プロセッサを多段スイッチで
結合する方式、文献１に記載のように、超立方体結合を
取るもの等が代表的である。

文献１ニジ−・エル・サイン「ザ　コスミックキューブ
」、コミュニケーションズ　オブ　ザエーシーエム、２
８巻、１号、２２〜３３頁、１９８５年（Ｃ，Ｌ、５ａ
ｉｔｚ　”Ｔｈｅ　Ｃｏ５ｍ１ｃ　Ｃｕｂｅ”。

ｃｏｍ＋ｎｕｎｉｃａｔｉｏｎＮ　　ｏｆ　　ｔｈｅＡ
ＣＭ、ｖｏ１、　　２８．　ｎｏ、　　１、　ｐｐ、　
　２２−３３．１９８５）〔発明が解決しようとする問
題点〕 上記従来技術のうち、バス結合方式はハードウェアの量
が少ないという利点があるが、結合されている要素プロ
セッサ台数が多いと、バスの競合により性能が低下する
という問題点があり、十数台が限度とされている６ 格子状結合（メツシュ結合ともいう）は同じくハードウ
ェアの量が少なく、しがも多数の要素プロセッサを結合
できる反面、隣接プロセッサとしか交信出来ないためそ
の通信性能は扱う問題の性質に大きく依存する。近傍計
算に向く偏微分方程式の求解９画像処理等は良いが、有
限要素法や高速フーリエ変換（ＦＦＴ）、論理／回路シ
ミュレーション等では通信のオーバヘッドが著しくなる
。

フルクロスバスイッチ結合はマトリックススイッチによ
り全ての要素プロセッサを完全結合するものである。そ
のため、性能的にはあらゆる結合の中で最高であるが、
ハードウェア量が要素プロセッサ台数２乗に比例するた
め、一般には数十台程度が結合限度とされている。

多段スイッチはハードウェア量が要素プロセッサ台数を
ＬとするとＬ　ｌｏｇｚ　Ｌ程度に抑えられ、しかも完
全結合が可能であるため、多数の要素プロセッサを含む
超並列計算機向きの結合方式とされてきた。しかし、通
信路の長さ（中継段数）が約１ｏｇｚ　Ｌ程度となり転
送遅延が大きいこと、また多数の要素プロセッサが同じ
共有変換をアクセスしようとすると、複数のアクセスバ
スが途中の通信経路を奪いあいホットスポットコンテン
ションと呼ばれるネットワークの全面マヒ（マヒは全て
のアクセスに波及する）が生じること、ホットスポット
コンテンションに至らなくてもアクセス競合が大きく性
能が出ないこと１等の問題点が指摘されている。

超立方体結合（ハイパーキューブ）は、比較的効率の良
い通信が行える結合として知られているが、プログラム
上で通信相手を指定しなくてはならずプログラミングが
煩雑となる。これを避けるために、各要素プロセッサ対
応に自動中継機構を設けると、ハードウェア量が増大す
る。また、結線が交差するので実装が面倒であるという
問題がある。

大規模な数値計算の並列処理においては、しばしば特定
のプロセッサ間通信バタンか現れることが知られている
。代表的なものとしては、格子結合、リング結合、バタ
フライ結合が挙げられる。

従って、これら特定のパタンの通信が高速に処理できる
ならば、そのネットワークの有効性は大であるといえる
。上記の従来技術のうち、格子結合。

リング結合、バタフライ結合を自身の結合トポロジーと
して内包しており、中継動作を必要とせずにこれらのパ
タンで通信できるのは、フルクロスバスイッチと超立方
体結合だけである。バス結合。

格子結合、多段スイッチはいずれも、これら特定パタン
の通信全てを高速に処理することはできない、また、特
殊な例として、文献２には２台のプロセッサの結合を基
本とする２構成の超立方体結合を複数台のプロセッサの
結合を基本にした構成に拡張したＳｐａｎｎｉｎｇ　Ｂ
ｕｓ　）ｌｙｐｅｒｃｕｂａが紹介されているが、複数
台のプロセッサはバス結合されているため一時には２台
のプロセッサしか通信出来ず、上記結合トポロジーを内
包しているとはみなせない。

文献２：ダルマ・ピー・アグラワル他「エバリュエイテ
イング　ザ　パフォーマンス　オブ　マルチコンピュー
タ　コンフィギユレーション」。

アイ・イー・イー・イーコンピュータ、メイ。

１９８６．２８〜２９頁、１９８６年 （Ｄｈａｒｍａ　Ｐ、　Ａｇｒａｗａｌ　ｅ１、　ａ１
、’　Ｅｖａｌｕａｔｉｎｇ　ｔｈｅＰｅｒｆｏｒｍａ
ｎｃｅ　ｏｆ　Ｍｕｌｔｉｃｏｎ＋ｐｕｔｅｒ　Ｃｏｎ
ｆｉｇｕｒａｔｉｏｎＮ”。

Ｍａｙ　１９８６．ｐｐ、２８−２９，１９８６）以上
の譜問題のうち、バス結合における結合台数制約の問題
は、要素プロセッサ台数が多い場合には解決することが
出来ない。また、格子結合における扱う問題の性質によ
って性能が大幅に変わる点、多段スイッチのホットスポ
ットコンテンションの問題はいずれも基本的かつ本質的
な問題であり、現状では解決されていない。さらに。

Ｓｐａｎｎｉｎｇ　Ｂｕｓ　Ｈｙｐｅｒｃｕｂｅと共に
、これらの結合は格子結合、リング結合、バタフライ結
合の全てを内包していないことに起因する主要応用問題
における性能低下の問題がある。

このような原理的困難が無い残る二つのネットワーク：
　（フル）クロスバスイッチ、超立方体結合の内、前者
はハードウェア量が多すぎて多数台の要素プロセッサを
結合出来ず、後者は多数台を結合できるが、プログラミ
ングと実装が大変であり、結合台数が増加すると性能も
低下する。また、超立方体結合では、直接結合していな
い２台の要素プロセッサ間で通信する場合には、別の要
素プロセッサに中継させる必要がある。このように情報
パケットを一旦ある要素プロセッサに取り込ませてから
別の要素プロセッサに転送していく通信の方法をストア
・アンド・フォワード方式というが、超立方体結合に限
らずストア・アンド・フォワード方式では、複数台の要
素プロセッサＰ１゜Ｐａ、　Ｐａ・・・がループ状に通
信経路を形成して、その上で中継動作を行なおうとする
と、ＰｌはＰ２が送信動作を終了して受信可能になるま
で送信動作を終了出来ず、Ｐ２はＰ３が送信動作を終了
して受信可能になるまで送信動作を終了出来ず、・・・
というようにお互いに噛み合って動けなくなるデッドロ
ック状態に陥ることがあるという問題がある。

性能は、−単位の送信情報が最終目的地に到達するまで
に通過する基本切替スイッチ（クロスポイント）の数で
、ハードウェア量は、ネットワークを構成するクロスポ
イントの総数で評価するが。

通常、ハードウェア量と性能はトレードオフ関係にあり
、クロスポイント総数を増せず一単位の送信情報の通過
するクロスポイント数は減少する。

本発明は、上記の意味での原理的困難のない相互結合ネ
ットワークであり、かつ、ハードウェア量の上限値（技
術的・経済的）と要素プロセッサ台数が任意に与えられ
たとき、これらのプロセッサをフルクロスバスイッチに
近い高い結合能力（少ない切替段数）で結合するととも
に、通信性能とハードウェア量に関して最適な結合を与
えるシステム構成を提供すること、特に最小もしくは最
適なスイッチ・ハードウェア量を持つネットワークを可
変的に構成する技術を提供することを目的としている６
すなわち、従来技術の範囲では、プロセッサ台数が少な
いうちはフルクロスバスイッチで、ある台数以上になる
と超立方体結合でネットワークを構成せざるを得なかっ
たが、本発明によればこれら再結合方式の中間の性能を
持ち、デッドロックの恐れのない自動中継機能付きの場
合にはさらにスイッチ・ハードウェア量も超立方体結合
より少ない結合ネットワークを幾種類も構成できる。ま
た実装は、単位となるスイッチをチップ内、モジュール
内、ボード内、匣体内、匡体間等にスイッチ毎にまとめ
て実装出来るので、性能バランス上、保守上好適である
。

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

上記目的は、基本的には、　Ｌ　＝　ｎ　Ｉ　Ｘ　ｎ２
Ｘ・・・×ｎＮと因数分解できるＬを要素プロセッサの
台数とする並列計算機において、これらの因数の各々を
一辺の格子点数とするＮ次元格子間空間上の超直方体の
内点の座’！！４　（ｉ１、ｉｚ＋・・・、ＩＮ）Ｔｏ
≦ｉ１≦ｎｚ１、Ｏ≦１２≦ｎｚ−１，−０≦ｉＮ　≦
ｎＮ−１を各要素プロセッサのプロセッサ番号として与
え、任意のｋに対し第に次元の座標のみが異なるプロセ
ッサ番号を持つ一群の要素プロセッサ、すなわち、プロ
セッサ番号 （１１＋１２ｙ・・・、ｏｒ・・・、１ｓ）（１１，１
２？・・・、１、・・・、ｉ＊）（１１１１２ｙ　”’
ＨｎＫ　　１　ｒ　”’ｔ　ｉＮ）を持つｎに個の要素
プロセッサ群を一つのｎＫ入力ｎＫ出力のクロスバスイ
ッチで相互に結合し、該結合を第に次元を除くＮ−１次
元部分空間の座標（Ｉｌｌ　　１２？　　”’ｒ　　ｎ
Ｋ−１ｒ　　ｎＫ＋１＋　　”’ｔ　　ＩＮ）の全て（
Ｌ／ｎｇ組）にわたって行ない、さらに全てのＫ（１≦
に≦Ｎ）に対して行なうことにより構成した、計ＬＸ　
（１／ｎｚ＋１／ｎｚ＋−＋１／ｎＮ）個のクロスバス
イッチにより要素プロセッサを結合し、さらにこの結合
において、送信側プロセッサに付随する中継手段が自プ
ロセッサ番号（ｉ工、ｉｚｔ・・・ｔｘｈ）と目的地プ
ロセッサ番号Ｆ１＋Ｊ２ｙ・・・、ｊＮ）とで不一致な
次元の一つに（ｉに≠ｊｘ）を選び、送信側プロセッサ
の中継手段に付随しているＮ個のクロスバスイッチ（こ
れを以下、座標変換クロスバスイッチと呼ぶ）のうち第
に次元の座標のみが異なるプロセッサ番号の要素プロセ
ッサ群を結合しているクロスバスイッチ（第に次元座標
変換クロスバスイッチ）を選択し、これに目的地プロセ
ッサ番号を送信データと組にして構成した通信用情報パ
ケットを入力し、各座標変換クロスバスイッチは目的地
プロセッサ番号の第に次元座標部分をデコードして第に
次元の座標が目的地プロセッサ番号の第に次元座標と等
しいプロセッサ番号を持つプロセッサ、すなわち、目的
地プロセッサそれ自身、または目的地プロセッサへ至る
経路上のプロセッサに送信して中継させ、後者の場合、
これを不一致座標が無くなるまで繰り返すことにより目
的地プロセッサに情報パケットを送信する方式を用いる
ことにより解決することが出来る。さらに、要素プロセ
ッサに付随する中継手段としてクロスバスイッチを用い
ることにより、中継時に他の中継パスと競合することが
無くなるためデッドロックの危険性を完全に排除するこ
とができる。

〔作用〕

本発明の相互結合方式により任意の要素プロセッサ間で
通信が行えることを述べる。プロセッサ番号（ｉｘｇｘ
ｚ＋・・・ｔｘＮ）を持つ送信元プロセッサからプロセ
ッサ番号Ｆ　ｔｔ　ｘ　２．・・・、ｉＮ）を持つ目的
地プロセッサへ通信する場合を考える６送信元プロセッ
サの第一座標ｉｚと目的地プロセッサ第一座標ｊｚとが
等しくない場合、これ以外の座標が全て等しい要素プロ
セッサは一つのクロスバスイッチ（第１次座標変換クロ
スバスイッチ）に接続されているから、このクロスバス
イッチによりプロセッサ番号Ｆ１ｙ　ｉｇ、・・・ｔｘ
Ｎ）を持つ要素プロセッサ、または該要素プロセッサに
付随した中継クロスバスイッチに情報を送信できる。

次にいま情報を受は取った要素プロセッサ、または該要
素プロセッサに付随した中継クロスバスイッチは、第２
次座標以外の座標が全て等しい要素プロセッサと一つの
座標変換クロスバスイッチにより結合されているから、
１２≠ｊ２なら、このスイッチによりプロセッサ番号Ｃ
ｊｓｖ　ｊｚｔ　ｉａ、・・・ｉＮ）を持つ要素プロセ
ッサ、または該要素プロセッサに付随した中継クロスバ
スイッチに情報を送信できる。このような経路を選び次
々とクロスバスイッチにより対応する座標を置き換えた
要素プロセッサ、または該要素プロセッサに付随した中
継クロスバスイッチに送信していくことにより、最後に
はプロセッサ番号Ｆ１＋、］２．・・・Ｗ　ｊＳ）を持
つ要素プロセッサに情報を送信できる。

また、多くの場合、Ｌの因数分解を適当に行なうことに
より、各次元の結合要素プロセッサ台数をある範囲に制
限することが出来る。これにより、各次元の座標変換ク
ロスバスイッチを定められた実装単位内、例えば、チッ
プ内、モジュール内。

ボード内、置体内、匡体間等に収めることが可能となる
。この性質は、各因数がすべて同じ値をとるという条件
：Ｌ＝ｍＮの下では充分満たすことができず、本発明の
分解：Ｌ＝ｎＩＸｎ２Ｘ・・・ＸｎＮが必要条件となる
。

中継クロスバスイッチを用いない場合には、要素プロセ
ッサＰ１が要素プロセッサＰ２にパケットを中継しよう
とし、同時に要素プロセッサＰ２も要素プロセッサＰ１
にパケットを中継しようとするとデッドロックが生じる
。しかし、中継クロスバスイッチを用いると、Ｐｌから
Ｐｌへのパケットの流れと独立にＰｌからＰｌへのパケ
ットの流れを設定できるため、プツトロックは発生しな
い。

〔実施例〕

以下、本発明の実施例を図面により詳細に説明する。

第一実施例 （１）相互結合ネットワークの構成 第１図は本発明の第一実施例の結合方式の３次元を例と
した説明図であるが、Ｎ次元に拡張した場合も同様であ
る。第２図に示すように。

３次元格子空間上のＬＸＭＸＫの直方体の内点に対応す
る各格子点に論理的に配置された任意の（プロセッサ番
号（１＊、１＊ｋ）を持つ）要素プロセッサＰ（１ｔ　
ａ　ｓ　ｋ）は、第１図に示すように、３個のクロスバ
スイッチ９−１、９−２．９−３に接続される。ここに
クロスバスイッチ９−１は、プロセッサｐ　（ｉ、　Ｊ
、ｋ）と第１次元の座標のみが異なる要素プロセッサＰ
（Ｏｗ　ｊ＋　ｋ）＋　Ｐ（１＋　ｊ＋　ｋ）＋・・・
・・・、Ｐ（Ｌ−１，ｊｔｋ）を完全結合するものであ
り。

同様にクロスバスイッチ９−２は第２次元の座標のみが
異なる要素プロセッサＰ（ｉ、Ｏ，ｋ）。

Ｐ　（１＋　１＋　ｋ）＋・・・・・・、Ｐ　（ｉ、Ｍ
−１，ｋ）を、また、クロスバスイッチ９−３は第３次
元の座標のみが異なる要素プロセッサＰ（１＋ｊ＋０）
ｔ　Ｐ　（ｌｅ　ｊｖ　１）ｔ・・・・・・、Ｐ　（１
＋　、）＋に−１）を完全結合するものである。

各々のクロスバスイッチは、プロセッサ番号を構成する
３次元座標の一つの特定次元の座標値を他の座標値に置
き換えた番号を持つ要素プロセッサと通信する機能を持
つ。このため、このクロスバスイッチを以下では座標変
換クロスバスイッチと呼ぶ。そして、特定の次元にの座
標変換を行なうスイッチをに次元座標変換クロスバスイ
ッチと呼ぶ。後に示すように、３個の座標変換クロスバ
スイッチを中継することにより、いかなる番号の要素プ
ロセッサとも通信することができる。

（２）要素プロセッサの構造 第３図には、要素プロセッサの構造を示す。

要素プロセッサｐ　（ｉ、ｊ＋　ｋ）は中継装置１およ
びプログラムカウンタを持ち命令を逐次実行していく通
常の計算機である処理装置２とから構成されている。中
継装置１はマイクロプログラムを内蔵し、処理装置２ま
たは入力ポートレジスタ５から入力した通信用パケット
送信先プロセッサ番号を解読し、その結果に基づき特定
の座標変換クロスバスイッチ９−１〜９−３、または処
理装置２を選択してそこに通信用パケットを送る機能を
持つ通信制御装置３と、通信用パケットを一時的に格納
する入力ポートレジスタ５および出力ポートレジスタ６
と、３個の座標変換クロスバスイッチからの入力通信路
の一つを選択するセレクタ７と、出力ポート中の通信用
パケットの送出先としてＮ個の座標変換クロスバスイッ
チの一つを選択する分配器８とから構成されている。こ
こに通信用パケットは送信先プロセッサ番号と送信デー
タとから成っている。

（３）通信方法 次に第１図の３次元の例で、プロセッサＰ（ｉ、ｊ、ｋ
）−出発地プロセッサーからプロセッサＰ　（０，Ｏ，
Ｏ）−目的地プロセッサーへ送信する仕組みについて第
１、３．４図を用いて説明する。まず、出発地プロセッ
サＰ（ｉ。

ｊ、ｋ）の処理袋Ｗ２は、通信制御装置３に通信用パケ
ットを入力しその送信を指示する。通信用パケットの宛
先情報（プロセッサ番号）は３個の座標（０，Ｏ，Ｏ）
から構成され、その第一座標から順にその座標値を通信
制御装置３のマイクロプログラム中の自プロセッサ番号
を構成する３個の座標値（ｉ、ｊｔ　ｋ）と比較してい
き、最初に不一致となった第１座標ｉに関してこの座標
値をＯに置き換えた査を持つ要素プロセッサｐ　（０，
ｊ＋　ｋ）と通信するべく、対応する第１座標変換クロ
スバスイッチ９−１を選択する。通信用パケットは出力
ポートレジスタ６に置かれ、選択されたクロスバスイッ
チ９−１の番号“１″は信号線１２により分配器に入力
される。分配器８はこの番号１１１　ＩＦを用いてデー
タ線１３、制御信号線１２を第１座標変換クロスバスイ
ッチ９−１の一つの入力チャネル１０１，１０２に接続
する。通信制御装置３は制御信号線１２および１０１デ
ータ線１３および１０２を用いて出力ポートロ中の通信
用パケットを第１座標変換クロスバスイッチ９−１に送
出する。座標変換クロスバスイッチの構造と動作につい
ては後述する。

該クロスバスイッチ９−１を経由してこの通信用パケッ
トを送られた要素プロセッサＰ　（０゜ｊ、ｋ）は、そ
のセレクタ７−２が送信要求信号０ＲＥＱ　（後述）を
出力している複数のクロスバスイッチの中から該クロス
バスイッチ９−１を選択すると、（本発明では選択の論
理については主張しない）クロスバスイッチの出力チャ
ネル線１０３，１０４が制御信号線１０−２とデータ線
１１−２に接続され、入力ポートレジスタ５−２を経て
通信制御装置３−２に通信用パケットを取り込む。この
とき、セレクタ７−２はその選択論理が選択した受信ク
ロスバスイッチ９−１の番号１１１　＃ｌも制御信号線
１〇−２により伝える。要素プロセッサＰ　（０＊　ｊ
＋ｋ）の通信制御袋［３−２では該スイッチ番号Ｊｌ　
Ｉ　Ｉ＋から変換された座標−二の例では第１座標−を
知り、再びそれ（第１座標）以降の座標から順に目的地
プロセッサの座標値（傘、０゜０）−傘は変換済み座標
であることを示す−を自プロセッサの座標値（０，ｊ、
ｋ）と比較していき、最初に不一致となった第２次元座
標ｊに関してこの座標値を０に置き換えた座標を持つ要
素プロセッサＰ　（０，Ｏ，ｋ）に送信するべく第２次
元座標変換クロスバスイッチ９−４を選択して入力チャ
ネル線２０１，２０２に通信用パケットを送出する。出
力チャネル線２０３゜２０４からパケットを入力したプ
ロセッサＰ（０，Ｏ，ｋ）でも同様にして中継動作を行
ない、第３次元座標変換クロスバスイッチ９−５の入力
チャネル線３０１，３０２にパケットを送出し、目的地
プロセッサＰ　（０，Ｏ，Ｏ）へは出力チャネル線３０
３，３０４を経由して通信用パケットを届けることが出
来る。目的地プロセッサＰ　（０，Ｏ，Ｏ）では、セレ
クタ７−４を経由して入力ボート５−４に格納されたパ
ケットの宛先（プロセッサ番号）（０，Ｏ，Ｏ）を通信
制御装置３−４が解読し、マイクロプログラム中の自プ
ロセッサ番号（０，０，０）と一致するので、処理装置
２−４にパケットの到着を通知する。

一般のＮ次元の場合でも同様に、このようにして次々と
座標変換クロスバスイッチにより不一致座標を目的地プ
ロセッサの座標に置き換えた座標を持つ要素プロセッサ
に中継していくことにより、最後には目的地プロセッサ
に情報を送信できる。不一致座標の変換は高々Ｎ回で完
了するから、この結合方式の最大通信路長はＮである。

第１図の３次元の例では、最大通信路長は３である。し
かし、格子結合、リング結合。

バタフライ結合に関しては、中継動作無しで一回の送信
で目的地プロセッサに通信用パケットを転送できるので
、フルクロスバスイッチと同等の通信性能となる。第４
図には、以上に述べた通信制御装置３の中継動作論理を
示す。

（４）座標変換クロスバスイッチの構造と動作第５図に
は、一つのＬ入力り出力のクロスバスイッチ９の外部イ
ンタフェースを示す。−組の入力チャネルは２本の制御
信号線ＩＲＥＱとＩＡＣＫ、およびデータ線ＩＤＡＴＡ
とからなっている。ＩＲＥＱは通信用の要素プロセッサ
が出力ポートレジスタ６に送信したいデータを格納して
送信待ち状態にあることをクロスバスイッチに通知する
信号を載せるためのものであり、ＩＡＣＫはクロスバス
イッチが次の送信データを出力ポートレジスタ６に書き
込んでも良いことを要素プロセッサに通知する信号を載
せるためのものである。ＩＤＡＴＡには送信データを載
せる。同様に、−組の出力チャネルは２本の制御信号ｇ
ＯＲＥＱと０ＡｃＫ、オヨび出力データ線０ＤＡＴＡと
からなっている。０ＲＥＱはクロスバスイッチが受信側
要素プロセッサの入力ポートレジスタ５に送信データの
転送を要求する信号を載せるためのものであり、　ＯＡ
Ｃには受信側要素プロセッサがそれを完了した信号を載
せるためのものである。０ＤＡＴＡには送信データを載
せる。以上のインタフェースにおいて、制御信号線ＩＲ
ＥＱ、ＩＡＣＫは第３図に示すように分配器８を介して
要素プロセッサの通信制御装置３と、また、制御信号線
０ＲＥＱ。

０ＡＧＫはセレクタ７を介して要素プロセッサの通信制
御装置３と接続されている。また、データ線ＩＤＡＴＡ
は分配器８を介して要素プロセッサの出力ポートレジス
タ６と、データ線０ＤＡＴＡはセレクタ７を介して要素
プロセッサの入力ポートレジスタ５と接続されている。

クロスバスイッチは、他に、後述するプロセッサ番号を
マスクするためのマスクレジスタの内容（マスクバタン
）を設定するためのマスクレジスタ書き込み制御信号線
Ｗとマスクバタン信号線ＭＡＳＫを備えている。

クロスバスイッチの構造の一例を第６図に示す。この例
では、３入力６出力のクロスバスイッチをとりあげてい
るが、一般のＬ入力Ｌ出力の場合でも全く同様である。

送信を行なおうとする要素プロセッサ、例えば第３図で
ｉ＝２とした場合プロセッサｐ　（２１ｊｔ　ｋ）の通
信制御装置３は出力ポートレジスタ６に送信データを格
納した後、分配器８にクロスバスイッチの番号“１”を
送って特定のクロスバスイッチ９−１を選択・接続し、
信号線１２を経由して入力チャネル２の制御信号、［１
０１すなわちＩＲＥＱ２に送信要求信号を出力する。当
該クロスバスイッチはプロセッサＰ　（０１ｊ、ｋ）、
Ｐ　（１゜ｊ、ｋ）ｒ　Ｐ　（２ｗ　ｊ−ｋ）をそれぞ
れ人出カチャネル０，１、２により接続している。線Ｉ
ＲＥＱＺ上の要求信号が当該クロスバスイッチのデコー
ダ２０−３に入力されると、送信先を求めるために出力
ポートロ上にある送信情報パケット中の送信先プロセッ
サ番号の第１次元座標相当部分がデコードされ、送信先
チャネル、例えば目的地プロセッサＰ　（０，Ｏ，Ｏ）
に対応するチャネル（出力チャネルＯ）に対しては１が
、それ以外に対してはＯが信号線２６−３に出力されて
全ての優先順位制御回路２１−１〜２１−３に伝えられ
る。デコードされるプロセッサ番号のビット列はその一
部だけがデコーダ２０−３に入力されれば良い。従って
、プロセッサ番号は、３次元格子空間の座標を表す３個
のフィールドよりなり、各次元の座標変換クロスバスイ
ッチではこれらのフィールドの当該次元に対応する一つ
のフィールドを取り出す機構が必要である。各次元の座
標値の範囲は一般には等しくなく、これに伴い各次元の
座標フィールドの位置や長さはまちまちである。本実施
例では、このフィールドを可変的に選択できるよう、各
デコーダにはマスクレジスタ２４−１〜２４−３を用意
し、プロセッサ番号の一部マスクして残りのビット列だ
けをデコードする仕組にしている。

第１１図にマスクレジスタの機能と端成を述べる。図で
は１６Ｘ１６のクロスバスイッチを想定しているが、他
の規模のクロスバスイッチでも同様である。マスクレジ
スタ２４は一種のマトリクススイッチとして働き、ＩＤ
ＡＴＡ中の送信先プロセッサ番号を示すビット列ｄｏ。

ｄｚ、・・・ｄ２１１のうち特定次元の座標を示す部分
ビット列ｄｉｄＪｄｈｄ露を選択してデコーダ（ＲＯＭ
）２ｏへの入力（アドレス）ＡｔＡｚＡａＡ４として出
力する。そのためには、図に示すようにデータ線ｄｓｄ
ａｄｈｄｍと出力線Ａ　ＩＡ　ｘ　Ａ　ｓ　Ａ　＆の交
点に対応するフィールドにＯを、他のフィールドに１を
書き込めば良い、出力線Ａ　Ｉ　Ａ　ｚＡ　ｓ　Ａ　！
上の信号はデコーダ２０により優先順位制御回路番号を
表す４ビツトの２進数としてデコードされ、優先順位制
御回路０〜１５への送信要求信号ｒｏ”ｒｔｓに変換さ
れる０例えば。

ｄ＋ｄＪｄｋｄｔの内容が’ｏ　ｏ　ｏ　ｏ’であれば
、優先順位制御回路Ｏを選択するべ（’１０００・・・
０′なる信号にデコードされる。このスイッチを１６Ｘ
１６より小模式のクロスバスイッチ、例えば４Ｘ４のク
ロスバスイッチとして用いる場合は、マスクレジスタ２
４は２ビツトだけを選択し、デコーダＲＯＭ２０への入
力アドレスＡ　ｓ　Ａ　２として用いる。Ａ　ａ　Ａ　
４は０となる。従って、この場合にはデコーダＲＯＭは
その一部だけが使用される。マスクレジスタ２４−１〜
２４−３の内容は外部（要素プロセッサまたはホスト計
算機等）からマスクレジスタ書き込み制御回路２５に指
示して設定可能である（ＷおよびＭＡＳＫ信号線を用い
る）。

優先順位制御回路２１−１には各入力チャネルから送信
要求が伝えられ、後述するように、予め定められた論理
に従ってそのうちの一つが選択される。その後、優先順
位制御回路２１−１は選択転送制御回路２２−１中のバ
ッファ２３−１が空きであることを確認し、信号線２７
−１により選択転送制御回路２２−１に選択された入力
チャネル番号（チャネル２）を伝える。その結果、プロ
セッサＰ　（２，ｊｔ　ｋ）の出力ポートロ上にある送
信情報パケットが（分配器８および入力チャネル２のデ
ータ線１０２（すなわちＩＤＡＴＡｚ）を経由して）選
択転送制御回路２２−１中のバッファ２３−１に転送さ
れる。この間優先順位制御回路２１−１はビジー状態に
あり、転送が完了すると次の選択動作に入る。

選択転送制御回路２２−１は、バッファ２３−１にデー
タが転送されると、出力光プロセッサ（プロセッサＰ　
（０，ｊ、ｋ））に対して送信を要求する信号線○ＲＥ
Ｑｏ、すなわち制御信号線１０３上に出力する。プロセ
ッサｐ（ｏ。

ｊ＋ｋ）のセレクタ７−２には複数個の座標変換クロス
バスイッチからの送信要求信号が入力され、予め定めら
れた論理に従ってそのうちの一つが選択され通信制御装
置３−２に伝えられる０通信制御装置３−２は、入力ポ
ートレジスタ５−２が空であるばあい、データ線０ＤＡ
ＴＡｏ。

すなわちデータ、１１！１０４上のデータをセレクタ７
−２を経由して入力ポートレジスタ５−２に書き込み、
書き込みが終了すると、書き込み完了信号を制御信号線
０ＡＣＫｏ上に出力する。

選択転送制御回路２２−１は線ＯＡ　ＣＫ　ｏから書き
込み完了信号を入力すると線ＯＲＥ　Ｑｏ上の送信要求
信号をネゲートし、プロセッサＰ（Ｏｔ　ｊｔ　ｋ）の
通信制御装置３−２はこれを検知して線ＯＡ　ＣＫ　ｏ
上の受信完了信号をネゲートする。選択転送制御回路２
２−１のバッファ２３−１は再び転送可能状態になり、
プロセッサＰ　（０＝　ｊｔ　ｋ）のセレクタ７−２も
他のクロスバスイッチを選択可能になる。

一方、優先順位制御回路２１−１がビジー状態から抜は
出ると、信号線２６−３によりこれを検知したデコーダ
２０−３は、プロセッサＰ（２１、Ｌ　ｋ）に対しＩＡ
ＣＫｚ上に転送完了信号を送る。ＩＡＣＫｚ上の転送完
了信号を受信したプロセッサｐ　（２１、Ｌ　ｋ）の通
信制御装置３はＩＲＥＱｚ上の転送要求信号をネゲート
し１次の送信データを出力ポートロ上に載せることが可
能となる。

優先順位制御回路２１−１〜２１−３の論理の一例を第
７図に示す。この例では、３つのデコーダからの入力が
３ビツトの情報、すなわちＯ〜７となることに着目し、
８エントリのメモリ（ＲＡＭ）１５に各入力に対応した
許可信号のパタンを記憶させておく方式をとる。しかし
、優先順位制御回路の論理はこれにとどまるものではな
い。

第二実施例 第８，９図には第二実施例の結合方式の説明図を示す。

第一実施例と異なるのは、要素プロセッサ内の通信制御
装置３で中継動作を行う代わりに、各要素プロセッサ毎
に設置された中継クロスバスイッチ１４がこれを行う点
にある。

（１）中継クロスバスイッチの構造と動作中継クロスバ
スイッチの構造は基本的には座標変換クロスバスイッチ
の構造と同じであるが、デコーダに入力される宛先プロ
セッサ番号は一つの座標フィールドでなく、３個の座標
フィー゛ルド全でである。中継クロスバスイッチの宛先
デコード部の詳細説明図を第１２図を用いて行なう。デ
ータ線ＩＤＡＴＡより入力された送信先プロセッサ番号
と、中継クロスバスイッチ内に用意された自プロセッサ
番号を格納した自プロセッサ番号レジスタ５０の内容は
比較器５１に入力され、ビットワイズにＥＸＯＲがとら
れて一致すれば１が、不一致であれば０が信号線５２−
１〜５２−３２上に出力される。この出力はマスクレジ
スタ２４に入力され、マスクレジスタ２４の交点フィー
ルドにＯが書かれている場合、すなわちマスクされてい
ない場合は、この入力は出力線Ａ　Ｉ　Ａ　Ｚ　Ａ　ａ
上にそのまま出力され、ここでワイアラドＡＮＤがとら
れる。その結果、マスクされずに出力線につながれた比
較器出力が全て１の場合にのみ、出力線には１が出力さ
れる。各出力線Ａ　Ｉ　Ａ　！　Ａ　ｓに対しプロセッ
サ番号の第１〜第３各座標を割り付ければ。

ある座標フィールドが全て自プロセッサ番号の対応する
フィールドと等しければ出力線には１が、そうでなけれ
ば（不一致座標の場合には）Ｏが出力されることになる
６出力線上の信号は反転されてデコーダ２０に入力され
る。

例えば１図で第１座標がデータ線ＩＤＡＴＡより入力さ
れた送信先プロセッサ番号のビット０゜１、２で表され
るとする。対応する自プロセッサ番号レジスタ５０のビ
ット０，１，２とともに比較器５１に入力され、全ての
ビットが一致すれば信号線５２−１、５２−２．５２−
３には１が出力される。第１座標フイールートとマスク
レジスタの第１出力線Ａｒの交点フィールド５３−１、
５３−２．５３−３にはＯが、他の出力線Ａ　ｚ　Ａ　
ｓとの交点フィールドには１が書き込まれているから、
第１出力１ｉＡ　Ａ　１に対してのみ比較結果が送られ
る。従って、信号線５２−１、５２−２．５２−３に全
て１が出力された場合にのみ、マスクレジスタの第１出
力線Ａ１に１が出力される。

デコーダは出力線Ａ　ｓ　Ａ　ｚ　Ａ　ｓ上の信号を２
進アドレスとしてチャネル番号に変換し、該チャネルの
優先順位制御回路に１を、他には０を送る。例えば、出
力線Ａ　Ｉ　Ａ　ｘ　Ａ　ｓ上の信号が全て１であった
場合、すなわち反転されたデコーダ入力アドレス’ｏ　
ｏ　ｏ’に対してはチャネルＯ１すなわち、自プロセッ
サへのチャネルを選択する。

（２）通信方法 第８図において、一つの座標変換クロスバスイッチ９か
ら中継クロスバスイッチ１４に通信用パケットが入力さ
れるとその宛先がデコードされ、もし、このプロセッサ
宛であればスイッチを要素プロセッサの入力ポート５へ
接続しパケットを入力する。もし、その以外の宛先であ
れば、不一致座標を変換する座標変換クロスバスイッチ
９を選択してそれに接続する。中継クロスバスイッチ１
４の外部インタフェースは座標変換クロスバスイッチ９
と同じである。

第９図には要素プロセッサＰ　（ｉ、ｊ、ｋ）から要素
プロセッサＰ　（０１ｊｔ　ｋ）　、　Ｐ　（０゜０、
ｋ）の中継クロスバスイッチを経由して要素プロセッサ
Ｐ　（０，Ｏ，Ｏ）にパケットを転送する例を破線で示
しである。

第二実施例においては、通信制御装置３は第一実施例に
て述べたような通信用パケットの宛先情報（通信先プロ
セッサ番号）の解読、その結果に基づく特定の座標変換
クロスバスイッチ。

または処理装置２の選択と通信用パケットの送出機能は
持たず、単に中継クロスバスイッチ１４とのインタフェ
ースをとる機能だけを持つ。

評価 第９図の例では座標変換クロスバスイッチを三つ（９−
１，９，−４，９−５）と、中継クロスバスイッチを四
つ（１４−１，１４−２，１４−３゜１４−４）経由し
ているので計７回スイッチング、動作が必要である。第
一実施例ではクロスポイントの通過数、すなわち通信用
パケットを一つの入出力ボート／バッファから次のバッ
ファ／入出力ポートへ転送する単位スイッチング動作を
３回と数えているが、要素プロセッサの制御装置３での
判定・選択処理を考慮すれば、転送に要する時間は結局
同じことになる。第一実施例（プロセッサ自身が中継す
る方式）では最大Ｎ回の送信動作が必要であることから
、このスイッチの最大通信路長はＮであり、ハードウェ
アとしてはクロスポイントの数でみるとｎｔＸｎｚＸ・
・・ＸｎＮＸ（ｎｔ＋ｎｚ＋　−＋　ｎ　Ｎ）となる。

また、ｎＫ”：　ｋ＝１、−Ｎの最大値がクロスバスイ
ッチの最大結合能力である。

また、第二実施例（プロセッサ対応に中継クロスバスイ
ッチを持つ方式）では、中継クロスバスイッチ１４で中
継動作を行うこと自体を一回の送信動作とみなすと最大
２Ｎ＋１回の送信動作が必要となる。すなわちこのスイ
ッチの最大通信路長は２Ｎ＋１である。また、ハードウ
ェア量はｎ１×ｎ２×−ＸｎＮ×｛（Ｎ＋１）”＋ｎｌ
＋ｎｚ＋−＋ｎＮ）で表される。

次に、本発明の相互結合方式により、一つのクロスバス
イッチの最大結合能力が与えられたときに、最高の性能
が出せる構成と最小のハードウェア量で済む構成を容易
に求めることが出来ることを示す。

性能は、クロスバスイッチの各プロセッサ間結合用信号
線の本数を一定とすると、通信路長Ｎまたは２Ｎ＋１で
決まる。すなわち、プロセッサを論理的に配置する空間
の次元を出来るだけ小さくする方が高い性能が得られる
。例えば第一実施例に示すプロセッサが中継する方式の
場合、プロセッサ台数をり、一つのクロスバスイッチの
最大結合可能プロセッサ台数をｎとするとき、ｑ＝　［
ｌｏｇＬ／ｌｏｇｎ］　＋　１が該クロスバスイッチを
用いたときの最小通信路長である。ここに［］は商の整
数部分をとる記号である。このときの構成は、要素プロ
セッサをｑまたはｑ＋１次元の格子空間の超立方体状領
域に配置し、その中の一次元部分領域を構成する全ての
要素プロセッサを結合可能プロセッサ台数が上記最大値
ｎであるクロスバスイッチを用いて結合したものである
。

一方、ハードウェア量はｎｌＸｎ２Ｘ・・・Ｘ−ｎＮＸ
（ｎ工＋ｎ２＋・・・＋ｎＮ）となるから、明らかにｎ
１＝２の場合が最小ハードウェア量となる。しかし、第
二実施例に示す中継クロスバスイッチを用いろ方式では
、第１０図に示すように、別の構成を取るときにハード
量が最小と成る。例えば２５６台構成では８Ｘ８Ｘ４台
の３次元に、４０９６台構成では８Ｘ８Ｘ８Ｘ８台の４
次元に配置する場合がハード量が最小となる。また、あ
る程度ハード量が多くても性能が出た方が良いとする立
場に立てば、要素プロセッサ６４台〜１０２４台構成で
は８×８〜３２ｘ３２の２次元構成が、２０４８〜３２
７６８台構成では４Ｘ８Ｘ８〜３２Ｘ３２×３２の３次
元構成が適当であろう。

〔発明の効果〕 本発明により、一つのクロスバスイッチ（フルクロスバ
スイッチ）では接続出来ないような多数の要素プロセッ
サを、プロセッサ台数の如何にかかわらずフルクロスバ
スイッチに近い結合能力で接続するスイッチを構成する
ことができる。二二にフルクロスバスイッチに近い結合
能力とは、通信性能が高い（クロスポイント通過数が少
ない）こと、応用上重要なプロセッサ間結合トポロジー
（格子、リング、バタフライ）を内包していて、このよ
うなプロセッサ間通信パタンに対しては最小のクロスポ
イント通過数で通信できること、を意味する。従来技術
の範囲では、上記結合トポロジーを内包し、かつ、多数
台のプロセッサを結合できるネットワークとしてはハイ
パーキューブが公知であるが、本発明の結合方式は上記
特定の結合トポロジー以外の通信パタンにおける通信性
能が、ハイパーキューブよりはるかに優れている。

とくに中継クロスパイスイッチを用いることにより、デ
ッドロックを完全に防止することができる。

また、本発明により、座標変換用クロスバスイッチ規模
（クロスバスイッチの入出力チャネル数）の（技術的・
経済的な）上限値と要素プロセッサ台数が任意に与えら
れたとき、最適（通信性能最大、ハードウェア量最小、
または両者の中間）な結合方式を構成する方法が与えら
れ、フルクロスバスイッチとハイパーキューブの間隙を
埋めることが可能となる。

さらに、チップ、モジュール、ボード、筐体等の実装単
位ごとに各次元の座標変換スイッチを収納できるよう、
要素プロセッサの結合関係を定めることが可能である。

【図面の簡単な説明】

第１図は本発明の第１実施例の構成図、第２図はプロセ
ッサの超直方体状配置図、第３図は要素プロセッサの摺
成図、第４図は通信制御装置３の中継動作を示す説明図
、第５図はクロスバスイッチのインタフェース説明図、
第６図はクロスバスイッチの構成図、第７図は優先順位
制御回路の一例を示す説明図、第８図は第二実施例の構
成図、第９図は第二実施例の動作説明図、第１０図は中
継クロスバスイッチを含む場合のハードウェア量を示す
説明図、第１１図はマクスレジスタの説明図、第１２図
は中継用クロスバスイッチのデコード部説明図である。 １・・・中継装置、２〜２−４・・・処理装置、３〜３
−４・・・通信制御装置、５〜５−４・・・入力ポート
レジスタ、６〜６−４・・・出力ポートレジスタ、７〜
７−４・・・セレクタ、８〜８−４・・・分配器、９−
１〜９−５・・・座標変換クロスバスイッチ、２０．２
０−１〜２０−３・・・プロセッサ番号デコーダ、２１
−１〜２１−３・・・優先順位制御回路、２２−１〜２
２−３・・・選択転送制御回路、２４．２４−４〜２４
−３・・・マスクレジスタ、１４−１〜１４−４・・・
中継クロスバスイッチ、１５・・・メモリ（ＲＡＭ）５
０・・・自プロセッサ番号レジスタ、５１・・・比較器
−ン 顎　１　　図 ｒ（ｖ忍θ） Ｋｚ　　図 第　５　図 （ｊＩＶ川旦用Ｊａ化２ 哲迭ぺｊ１門５　児７Ｋ　’　ｆｌβ 入力チャネルネル前 不　９　　凪 Ｐ（θ、θ、ρ） ■　／θ　困 不　１１　　図 Ｚ４　マス７Ｌノス７

Claims (1)

1. 【特許請求の範囲】 １、Ｌ＝ｎ＿１×ｎ＿２×・・・×ｎ＿Ｎ台の要素プロ
   セッサまたは外部デバイス（以下、要素プロセッサで代
   表）から構成される並列計算機において、Ｎ次元格子座
   標（ｉ＿１、ｉ＿２、・・・、ｉ＿Ｎ）、０≦ｉ＿１≦
   ｎ＿１−１、０≦ｉ＿２≦ｎ＿２−１、・・・、０≦ｉ
   ＿Ｎ≦ｎ＿Ｎ−１を各要素プロセッサのプロセッサ番号
   として与え、特定次元の格子点数に対応して定まる固有
   の位置および長さを持つたプロセッサ番号中の該次元フ
   ィールドをデコードして、当該次元に関するスイッチン
   グ動作を行なうクロスバスイッチを用意し、任意のｋに
   対し、第ｋ次元の座標のみが異なるプロセッサ番号を持
   つ一群の要素プロセッサ、すなわちプロセッサ番号 （ｉ＿１、ｉ＿２、・・・、■、・・・、ｉ＿Ｎ）（ｉ
   ＿１、ｉ＿２、・・・、１、・・・、ｉ＿Ｎ）・・・・
   ・・ （ｉ＿１、ｉ＿２、・・・、ｎ＿Ｋ−１、・・・、ｉ＿
   Ｎ）を持つｎ＿Ｋ個の要素プロセッサ群を一つのｎ＿Ｋ
   入力ｎ＿Ｋ出力の上記クロスバスイッチで相互に結合し
   、該結合を第ｋ次元を除くＮ−１次元部分空間の座標 （ｉ＿１、ｉ＿２、・・・、ｎ＿Ｋ＿−１、ｎ＿Ｋ＋１
   、・・・、ｉ＿Ｎ）の全て（Ｌ／ｎ＿Ｋ組）にわたつて
   行ない、さらに全てのＫ（１≦ｋ≦Ｎ）に対して行なう
   ことにより構成した、計Ｌ×（１／ｎ＿１＋１／ｎ＿２
   ＋・・・＋１／ｎ＿Ｎ）個のクロスバスイッチによる要
   素プロセッサの相互結合ネットワーク ２、特許請求の範囲第１項の相互結合ネットワークにお
   いて、最終目的地の送信先プロセッサ番号をアドレスと
   して送信データに付して与えた情報パケットを順次取り
   込み、自要素プロセッサ番号（ｉ＿１、ｉ＿２、・・・
   、ｎ＿Ｎ）と目的地要素プロセッサの番号（ｊ＿１、ｊ
   ＿２、・・・、ｊ＿Ｎ）とで不一致な次元の一つに（ｉ
   ＿Ｋ≠ｊ＿Ｋ）を選び、該要素プロセッサに結合してい
   るＮ個のクロスバスイッチのうち、該要素プロセッサの
   プロセッサ番号と第ｋ次元の座標のみが異なるプロセッ
   サ番号を持つ要素プロセッサ群を結合し、第ｋ次元の座
   標が目的地プロセッサ番号の第ｋ次元座標と等しいプロ
   セッサ番号を持つプロセッサ、すなわち、目的地プロセ
   ッサそれ自身、または目的地プロセッサへ至る経路上の
   プロセッサに送信することの出来るクロスバスイッチを
   選択して、該情報パケットを該クロスバスイッチに入力
   し、不一致座標が無い場合は自プロセッサの処理装置に
   該情報パケットを入力する各要素プロセッサ毎に設けた
   情報パケット中継手段を有することを特徴とする相互結
   合ネットワーク。 ３、特許請求の範囲第１項の相互結合ネットワークにお
   いて、該プロセッサの入出力ポートレジスタおよび該プ
   ロセッサに接続するＮ個のクロスバスイッチをこれに接
   続することにより、目的地へ情報パケットを中継する、
   各要素プロセッサ毎に設けたＮ＋１入力Ｎ＋１出力の中
   継用クロスバスイッチを有することを特徴とする相互結
   合ネットワーク。 ４、特許請求の範囲第３項において、ハードウェアの量
   を情報パケットが通過する、基本切替スイッチ（クロス
   ポイント）の数で評価するとき、与えられたプロセッサ
   台数Ｌに対して最小のハードウェア量を取る、すなわち
   、Ｌ×｛（Ｎ＋１）＾２＋ｎ＿１＋ｎ＿２＋・・・＋ｎ
   ＿Ｎ｝が最小となるように次元Ｎと、各次元の因数ｎ＿
   １、ｎ＿２、・・・ｎ＿Ｎが定められている相互結合ネ
   ットワーク。 ５、多次元座標で表される送信先アドレスを持つ情報パ
   ケツトを入力し、送信先アドレスの特定次元に関するス
   イッチングを行ない転送する機能を持つクロスバスイッ
   チにおいて、該次元に対応して定まる固有の位置および
   長さを持つたプロセッサ番号中のフィールドを、外部か
   らの指示により可変的に選択しデコードする手段を持つ
   ことを特徴とするクロスバイスイッチ。