JPH0136139B2 - - Google Patents

Description

【発明の詳細な説明】 本発明は、データ転送装置に関し、特に規則的
に結合されたスイツチ・モジユールから負荷に応
じて転送先の演算処理装置を動的に選択できるパ
ケツト・データの転送装置に関するものである。

多数の演算処理装置が転送系を介して結合され
ている並列処理計算機システムでは、その転送系
の構成方法によつてデータの処理能率が異なつて
くる。

第１図ａ，ｂ，ｃは、従来の問題の構造および
並列処理計算機システムの転送系の構成図であ
る。

第１図ａは、問題のアルゴリズムを示す木構造
を示すもので、根、節、葉の各ノードで問題が発
生し、分岐することを表わしている。これらの問
題を、演算処理装置では、通常サブ・ルーチン・
プログラムを実行することにより処理し、その結
果をメイン・プログラムに戻して次の問題に移
る。

第１図ｂ，ｃは、それぞれ、第１図ａに示す木
構造の問題を処理する並列処理計算機システムの
構成を示すもので、いずれも各ノードに対応する
位置に演算処理装置１を２次元配列し、隣接する
演算処理装置１間を転送路を介して結合してい
る。

第１図ｂに示すシステムの配列構造は、多数の
演算処理装置１を縦横に配列し、隣接相互間を伝
送路を介して連続的に結合するものであり、第１
図ｃに示すシステム構造は、根、節、葉の各ノー
ドの位置にそれぞれ演算処理装置１を設置し、伝
送路を介して根より各節点に至るアクセス・パス
を一意的に指定するものであり、第１図ａの各ノ
ード番号に対応した演算処理装置１には同一番号
を付している。番号のない処理装置１は、タスク
が与えられていないことを示す。

このように、分割統治法をはじめとして、処理
形態が木構造を形成するアルゴリズムの並列実行
においては、通常、木の１つのノードの処理を１
つの演算処理装置に割り当て、親子の関係にある
ノードを隣接する演算処理装置に割り当てる。

しかし、第１図ｂに示す配列構造結合系では、
演算処理装置の間で割り当てノード数が不均一と
なり、負荷の不平衡が生じる欠点がある。また、
第１図ｃに示す対称型木構造結合系においては、
与えられた問題が一般には非対称木構造を形成し
ており、問題の構造と結合系の構造との間に不整
合が生じ、しかも１台の演算処理装置に対して複
数ノードを割り当てることが不可能であるため、
演算処理装置を十分に稼動させるとができない欠
点がある。

本発明の目的は、これらの従来の欠点を除去す
るため、演算処理装置間での負荷の不平衡をなく
し、種々の処理構造に適合できるような柔軟な構
造を有するデータ転送装置を提供することにあ
る。

本発明のデータ転送装置は、直接あるいは演算
処理装置を介して他に結合された複数のデータ入
力部とデータ出力部を備え、該データ出力部に接
続された演算処理装置の負荷状態を識別し、軽負
荷のものを選択して独立転送動作する複数個のス
イツチ・モジユールをアレイ状に配列し、タスク
を発生した演算処理装置と該タスクが割り付けら
れた演算処理装置との相対的位置関係を示すコー
ドを転送経路情報として、１個以上のスイツチ・
モジユールを経由し、パケツト・データを転送す
ることを特徴としている。

また、タスクが割り付けられた演算処理装置か
らタスクを発生した演算処理装置に返送データを
送出する場合、後者と前者の演算処理装置の相対
的位置関係を示すコードのビツト順を逆転したも
のを反送経路情報として、転送時の処理と同一の
処理によりパケツト・データを返送することを特
徴としている。

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

第２図は、本発明の実施例を示すデータ転送系
を備えた計算機システムの全体構成図である。

第２図において、データ転送系は、スイツチ・
モジユール２と一方向性の転送路４，５の集合体
から構成される。縦横に規則的に結合されたスイ
ツチ・モジユール２は、単純な制御方式により実
現でき、かつLSI化が可能であり、また転送路
４，５に接続された演算処理装置３のうちの軽負
荷のものを選択する機能を有する。これらのスイ
ツチ・モジユール２によつて、物理的には隣接結
合構造を形成しているが、論理的には木構造形態
を実現することができる。また、各スイツチ・モ
ジユール２は、軽負荷の演算処理装置３を選択す
るモード（サーチ・モード）と、指定された演算
処理装置３にデータを転送するモード（トランス
フア・モード）の２つのモードで動作し、各演算
処理装置３とともに独立して動作する。

スイツチ・モジユール２と演算処理装置３間、
およびスイツチ・モジユール２相互間は、データ
転送線と制御線からなる転送路４，５を介して接
続される。第２図に示すように、スイツチ・モジ
ユール２と演算処理装置３間は、互いに隣接する
ものどうしで接続されるのに対して、スイツチ・
モジユール２相互間は、遠距離のものどうしで斜
方向に貫通して接続される。なお、演算処理装置
３を経由する転送路は、上下と左右方向のみであ
り、斜め方向の転送路（スイツチ・モジユール２
相互間を結合する）は演算処理装置３を経由しな
い。したがつて、第２図では、演算処理装置３を
経由しているように見える斜方向の転送路は、演
算処理装置３の裏を迂回している。

いま、スイツチ・モジユール２の総数をＮ（第
２図ではＮ＝16）とすると、Ｎを法として計算し
たスイツチ・モジユール２間の番号の差をｄとし
たとき、Ｎとｄが互いに素となるスイツチ・モジ
ユール２相互間を接続する。第２図では、ｄ＝７
としているので、(1)―(8)、(2)―(9)、(3)―(10)、(4)
―
(11)、……(9)―（16）の各番号のものがそれぞれ接
続される。

第３図は、第２図のデータ転送系で用いられる
転送単位のパケツトの構成図である。

本実施例におけるデータ転送系の転送形態は、
パケツト転送である。第３図に示すように、パケ
ツトは、パケツト・ヘツダ６とパケツト本体７か
ら構成されており、パケツト幅を転送路４，５の
データ転送幅に一致させて、これを語と呼ぶ。つ
まり、パケツトは語の集団を形成しており、パケ
ツト長がパケツトを構成する語数である。ここで
は、パケツト長は、固定長のものを扱うものとす
る。なお、パケツト・ヘツダ６の先頭の１語は、
転送経路情報のエリア８である。

本発明のデータ転送装置では、次の各機能をス
イツチ・モジユール２に備えることにより、演算
処理装置の負荷状態を常時観察して、スイツチ・
モジユール２間でパケツトの転送を行い、軽負荷
の演算処理装置３に処理依類パケツトを動的に導
くものである。すなわち、スイツチ・モジユール
２は、(1)タスクの依頼先となる軽負荷演算処理装
置３の動的な決定、(2)タスクを依頼する処理依頼
パケツトの転送、(3)処理依頼パケツトに対する依
頼側への返送パケツトの転送、の各機能を具備し
て、(1)サーチ・モードと(2)トランスフア・モード
の２つのモードにしたがつてパケツトを転送す
る。

サーチ・モードは、処理依頼先を動的に定める
ための転送モードであり、トランスフア・モード
は、転送先がすでに定まつている場合の転送モー
ドである。

第２図において、処理依頼パケツトの転送には
転送路４を使用し、返送パケツトの転送には転送
路５を使用する。

あるスイツチ・モジユール２からの処理依頼デ
ータが複数のパケツトになる場合、これらのパケ
ツトは、すべて同一の演算処理装置３に転送する
必要がある。その場合のスイツチ・モジユール２
の手順は、次のようになる。

(1)先ず、１番目の処理依頼パケツトをサーチ・
モードで転送し、転送先と転送経路を決定する。
(2)次に、この転送経路情報を返送パケツトに組み
立て、トランスフア・モードで依頼元方向に転送
する。(3)次に、パケツト・ヘツダの第１語にこの
転送経路情報を挿入した２番目以降の処理依頼パ
ケツトをトランスフア・モードで依頼先方向に転
送する。(4)依頼パケツトの処理が終了すると、処
理結果を依頼元に返送するが、そのときはトラン
スフア・モードで転送する（これも返送パケツト
である）。

第４図は、本発明の実施例を示すスイツチ・モ
ジユールの構成図である。

第４図に示すように、スイツチ・モジユール２
は、入力回路９，１４、出力回路１０，１３、負
荷表示回路１５および内部転送路１１，１２から
構成される。

第２図より明らかなように、あるスイツチ・モ
ジユール２に注目すると、そのスイツチ・モジユ
ール２からの処理依頼パケツトが送られる演算処
理装置３は左方向と下方向の２個であり、またそ
のスイツチ・モジユール２に処理依頼パケツトを
送る演算処理装置３′は右方向と上方向の２個で
ある。また、そのスイツチ・モジユール２からの
処理依頼パケツトが送られる他のスイツチ・モジ
ユール２′は１つであり、そのスイツチ・モジユ
ール２に処理依頼パケツトを送るスイツチ・モジ
ユール２′は１つである。

第４図において、出力回路１３に接続される２
本の転送路４、入力回路１４に接続される２本の
転送路５、および負荷表示回路１５に接続される
２本の制御線は、このスイツチ・モジユール２か
らの処理依頼パケツトが到着する側の２つの演算
処理装置３に結合される。一方、入力回路９に接
続される２本の転送路４、出力回路１０に接続さ
れる２本の転送路５は、このスイツチ・モジユー
ル２に処理依頼パケツトを発送する側の２つの演
算処理装置３′に結合される。

入力回路９，１４、出力回路１０，１３は、
LSI化の際のリピータビリテイを考慮して、いず
れも同一構成とする。また、処理表示回路１５
は、２個の演算処理装置３の負荷状態を、装置ご
とにそれぞれ過負荷、軽負荷の２つの状態で表示
する。

入力回路９は、転送モードにより動作が異なる
が、入力回路１４は返送パケツトの転送に用いる
ため、常にトランスフア・モードにより動作す
る。したがつて、入力回路９がサーチ・モードで
動作するときには、処理表示回路１５からの信号
線１６を利用するが、入力回路１４がトランスフ
ア・モードで動作するときには、信号線１６を利
用しない。

第５図は、第３図におけるサーチ・モード時と
トランスフア・モード時の転送経路情報を示す
図、第６図は第４図における入力回路と出力回路
の位置関係を符号化した図、第７図は第２図にお
けるパケツトの転送過程を示す図である。

(1) 先ず、サーチ・モード時の動作を説明する。

前段のスイツチ・モジユール２から演算処理
装置３および転送路４を介してパケツト・デー
タの処理依頼が入力した場合、入力回路９は処
理表示回路１５の状態を参照して、いずれの演
算処理装置３も過負荷でなければ、それらのう
ちの任意の１個に対応する出力回路１３を選択
し、また、いずれか一方が過負荷でなければ、
それに対応する出力回路１３を選択し、またい
ずれも過負荷であれば、このスイツチ・モジユ
ール２に接続された演算処理装置３への処理依
頼は無理であると判断して、他の演算処理装置
３に処理依頼を行うために、他のスイツチ・モ
ジユール２′に対応する出力回路１３を選択す
る。ただし、後述するように、前段のスイツ
チ・モジユール２で、転送経路情報の追加によ
る転送経路情報エリア８のあふれが検出された
場合には、たとえ負荷表示回路１５が両演算処
理装置３ともに過負荷を表示していても、入力
回路９は、演算処理装置３に接続されているい
ずれか一方の出力回路１３を選択することにな
る。

第５図ａはサーチ・モードにおける転送経路
情報のビツト・パターンであり、第５図ｂはト
ランスフア・モードにおける処理依頼パケツト
と返送パケツトの転送経路情報のビツト・パタ
ーンであつて、転送時には矢印方向に進行す
る。

第５図ａにおいて、処理依頼パケツトが作成
された時点では、転送経路情報エリア８は全ビ
ツトが“０”の初期状態にある。

なお、スイツチ・モジユール２において、入
力回路_iと出力回路_jの位置関係を、第６図
に示すように対応づけて、それぞれ２ビツトで
符号化しておく。

入力回路９は、サーチ・モード時の転送を行
う際に、パケツト・ヘツダの転送経路情報に追
加を行う。前段からのパケツト・データが入力
回路９に入力したときには、第５図ａ上段に示
すように、エリア８の左端から順に旧転送経路
情報T₀（a_k……a₂，a₁）が挿入され、残りのビ
ツト位置には“０”が詰められている。入力回
路９による追加の操作は、第５図ａ下段に示す
ように、旧転送経路情報T₀を２ビツトだけ右
にシフトし、第６図の位置関係に対応する２ビ
ツトの追加情報a_k+2、a_k+1を左端に詰めること
によつて行われる（新転送経路情報はT₁）。

転送経路情報エリア８のあふれは、シフト後
の空きビツト、つまり“０”が詰められている
ビツトが残り２ビツトになつたときに検出され
る。すなわち、パケツトが１個のスイツチ・モ
ジユール２を経由するごとに、エリア８の左端
に２ビツトずつ追加され、全体の情報が右にシ
フトされていくため、複数個のスイツチ・モジ
ユール２を経由するうちに、エリア８のあふれ
が検出することになる。入力回路９は、前段の
スイツチ・モジユール２があふれを検出した場
合でも、残り２ビツトの“０”を使つて転送経
路情報の追加を上述のように行う。

(2) 次に、トランスフア・モード時の動作につい
て説明する。

サーチ・モード時に決定された転送経路情報
から一意的に出力回路１３，１０が選択できる
ように、入力回路９，１４はいずれも第６図に
示す符号表を具備している。第６図から明らか
なように、入力回路_iに対する出力回路_jの
符号と、入力回路′_jに対する出力回路′_iの
符号の関係は、ビツト順序を逆転した関係にあ
り、ある処理依頼パケツトを転送すると、それ
に対する返送パケツトは同一経路で逆方向に転
送されることになる。したがつて、トランスフ
ア・モード時の転送経路情報のうち処理依頼パ
ケツトの場合には、第５図ｂ上段に示すよう
に、サーチ・モード時に決定された転送経路情
報Ｔをそのビツト順序のまま右詰めして送出す
る。また、返送パケツトの場合には、第５図ｂ
下段に示すように、処理依頼パケツト転送のと
きのビツト順序を逆転した転送経路情報T′を
作り、これをエリア８に右詰めして送出する。
なお、エリア８の左側の余つたビツト位置に
は、“０”が詰め込まれる。

第７図では、タスクを発生した演算処理装置
３―１から３個のスイツチ・モジユール２―
１，２―２，２―３を経由してタスクを割り付
けられた演算処理装置３―２に処理転送パケツ
トを転送する場合、および返送パケツトを転送
する場合を示している。

実線矢印の経路で、処理依頼パケツトが転送
され、鎖線矢印の経路で、返送パケツトが転送
されるが、各スイツチ・モジユール２―１，２
―２，２―３の入力回路９は、右から順に２ビ
ツトごとの符号を見るだけで、一意的に出力回
路１３を選択することができる。そして、スイ
ツチ・モジユール相互間の転送においては、パ
ケツトを受け取るごとに転送経路情報を２ビツ
ト右にシフトすることにより、入力回路９は転
送経路情報の右端２ビツトを見るだけで出力回
路１３の選択が可能である。すなわち、各スイ
ツチ・モジユール２―１，２―２，２―３の順
序でサーチ・モード時に定められた符号が右端
よりa₁a₂，a₃a₄，a₅a₆と２ビツトごとに挿入さ
れているので、各スイツチ・モジユールは、前
のスイツチ・モジユールに対応する２ビツトを
シフトすることにより、自分の符号が右端に表
われる。返送パケツトの場合には、転送経路情
報が逆転して、スイツチ・モジユール２―３，
２―２，２―１の順序で右端よりa₆，a₅，a₄，
a₃，a₂，１と２ビツトごとに配列されており、
かつ前述のように符号関係を逆転した関係にあ
るため、各スイツチ・モジユールは、前のスイ
ツチ・モジユールに対応する２ビツトをシフト
することにより、自分の符号が右端に表われ
る。

なお、第４図の出力回路１０，１３は、転送
モードに関係なく、３つの入力回路９，１４か
らの転送要求を調整して、演算処理装置３また
はスイツチ・モジユール２にパケツトを送出す
る。

第８図は、本発明の実施例を示す入力回路と
出力回路の詳細ブロツク図である。

入力回路９，１４の制御回路１８は、前段か
ら到達したパケツトの転送モードをパケツトご
とに保持し、パケツトの転送モードに応じて制
御を行う。

先ず、サーチ・モード時には、転送経路決定
回路１９が、負荷表示回路１５の状態と、前段
スイツチ・モジユール２′からの転送経路情報
エリアのあふれを示す信号（OVF）によつて、
分配回路２０の出力線を決定する。また、転送
経路付加回路シフタ２１は、転送経路付加回路
として動作する。制御回路１８は、到達したパ
ケツトのあふれ信号（OVF）をパケツトごと
に保持する。あふれ信号（OVF）の有無は、
パケツトの第１語（転送経路情報）がバツフア
２２に入力すると同時に識別できるため、有の
場合には転送経路決定回路１９からの信号を待
たずに、その時点で分配回路２０の出力線が決
定される。制御回路１８は、パケツトの第１語
が到達後に次段のスイツチ・モジユール２′ま
たは演算処理装置３に付して、このパケツトの
転送要求信号（req）と転送モード信号
（mode）を同時に送出する。これらの信号
（req）（mode）は、分配回路２０、内部転送路
１１、出力回路１３のアービタ２３を経由し
て、次段に伝搬される。この転送要求信号
（req）に対する応答信号（ack）が戻つてくる
と、出力回路１３の分配回路２４、内部転送路
１１、選択回路２５を経由して制御回路１８に
転送されるので、制御回路１８はパケツトの転
送を開始する。なお、分配回路２４の出力線と
選択回路２５の入力線は、それぞれアービタ２
３の入力線と、分配回路２０の出力線に対応し
て決定される。

制御回路１８は、パケツト転送に際して、そ
の第１語（転送経路情報）がバツフア２２から
転送経路付加回路シフタ２１およびあふれ検出
回路２６を経由するように、また、第２語以降
がバツフア２２からバス・ドライバ２７を経由
するように、インバータを介して切り換えるこ
とにより制御する。このとき、転送経路付加回
路シフタ２１は、第５図ａに示すような転送経
路情報の追加を行う。追加情報（a_k+1、a_k+2）
は、第８図に示す転送経路決定回路１９内で第
６図の符号関係を記憶するメモリを参照し、転
送経路付加回路シフタ２１に送出することによ
つて得られる。また、あふれ検出回路２６は、
転送経路情報のエリアの右端４ビツトを調べ、
１個でも“０”以外のビツトがあるときはあふ
れ信号（OVF）を出力する。これによつて、
次段のスイツチ・モジユール２′では、パケツ
トの第１語が到達すると同時に、あふれ信号
（OVF）が検出される。

このパケツトの転送終了後、制御回路１８
は、転送要求信号（req）の送出を止めて、転
送シシーケンスを終了する。

また、転送要求信号（req）に漸する応答信
号（ack）は、バツフア２２が一杯になつてい
ない限り要求信号（req）の入力直後に制御回
路１８から送出する。バツフア２２が一杯にな
つているときは、バツフア２２に空きが生じ次
第送出する。

次に、トランスフア・モード時には、転送経
路選択回路２８内に、到達したトランスフア・
モードのパケツトの第１語の右端２ビツトがパ
ケツトごとに保持されるので、分配回路２０の
出力線は、転送経路選択回路２８によつて決定
される。また、転送経路付加回路シフタ２１は
シフタとして動作し、あふれ検出回路２６は動
作しない。すなわち、バツフア２２からのパケ
ツトの第１語だけ転送経路付加回路シフタ２１
を経由し、第２語以降はバス・ドライバ２７を
経由して分配回路２０より出力される。転送経
路付加回路シフタ２１では、転送経路情報の２
ビツトが右シフトされる。

トランスフア・モード時のその他の転送シー
ケンスは、サーチ・モード時と同一である。

いずれの転送モードの場合でも、パケツトの
第１語がバツフア２２に到達していれば、分配
回路２０の出力線が決定できるので、バツフア
２２に複数個のパケツトがある場合、制御回路
１８は先頭のパケツトの転送シーケンス終了直
後に、次のパケツトの転送シーケンスに移る。
返送パケツトの送出の場合も全く同一の処理が
行われる。

このように、各スイツチ・モジユールは、バ
ツフア２２を具備して独立動作し、パケツト単
位でデータ転送を行うため、並列計算機システ
ムでは高度なパイプライン処理が可能となり、
これにより高いスループツトが得られる。ま
た、パケツト転送先指定コードは、往路と復路
とでビツト順を逆転するので、送り元あるいは
送り先を一意的に定めることができ、スイツ
チ・モジユールでの転送制御を単純化すること
ができる。

さらに、軽負荷の演算処理装置３をサーチす
る場合、軽送経路情報エリアにあふれが生じた
ときには、あふれを検出したスイツチ・モジユ
ールの次段のスイツチ・モジユールにおいて、
強制的に演算処理装置３を選択するので、回路
構成が単純となり、LSI化が容易となる。

以上説明したように、本発明によれば、処理依
頼パケツトの転送先を演算処理装置の負荷に応じ
て動的に選択できるので、演算処理装置相互間で
の負荷の平衡化を図ることが可能である。特に、
実行形態が木構造を有するプログラムに対して、
従来の結合系では負荷の不平衡が生じているが、
本発明ではこれを簡単な方法で解決し、かつ軽負
荷の演算処理装置の選択に際して、全演算処理装
置にわたつてサーチできる結線構造を用いるの
で、負荷の局在化を防止でき、種々の処理構造に
適合させることができる。

【図面の簡単な説明】

第１図は従来の問題アルゴリズムの木構造およ
び並列処理計算機システムの転送系の構成図、第
２図は本発明の実施例を示すデータ転送系を備え
た計算機システムの全体構成図、第３図は第２図
のデータ転送系で用いる転送単位のパケツトの構
成図、第４図は本発明の実施例を示すスイツチ・
モジユールの構成図、第５図は第３図における転
送経路情報を示す図、第６図は第４図における入
力回路と出力回路の位置関係を符号化した図、第
７図は第２図におけるパケツトの転送過程を示す
図、第８図は本発明の実施例を示す入力回路と出
力回路の詳細ブロツク図である。 １，３，３′：演算処理装置、２，２′：スイツ
チ・モジユール、４，５：転送路、６：パケツ
ト・ヘツダ、７：パケツト本体、８：転送経路情
報のエリア、９，１４：入力回路、１０，１３：
出力回路、１１，１２：内部転送路、１５：負荷
表示回路、１６：負荷表示回路からの信号線、１
８：制御回路、１９：転送経路決定回路、２０，
２４：分配回路、２１：転送経路付加回路シフ
タ、２２：バツフア、２３：アービタ、２５：選
択回路、２６：あふれ検出回路、２７：バス・ド
ライバ、２６：転送経路選択回路。

Claims (1)

1. 【特許請求の範囲】 １ 演算処理装置あるいは他のスイツチ・モジユ
   ールに接続された複数のデータ入力部とデータ出
   力部、および該データ出力部に接続された演算処
   理装置の負荷状態を識別して、軽負荷のものを選
   択し、上記データ入力部、出力部相互間を独立し
   て接続する手段を備えた複数個のスイツチ・モジ
   ユールをアレイ状に配列し、該スイツチ・モジユ
   ールを少なくとも１個経由して、タスクを発生し
   た演算処理装置と該タスクが割り付けられた他の
   演算処理装置との相対的位置関係を示すコードを
   転送経路情報としてパケツト・データを転送する
   ことを特徴とするデータ転送装置。 ２ 演算処理装置あるいは他のスイツチ・モジユ
   ールに接続された複数のデータ入力部とデータ出
   力部、および該データ出力部に接続された演算処
   理装置の負荷状態を識別して、軽負荷のものを選
   択し、上記データ入力部、出力部相互間を独立し
   て接続する手段を備えた複数個のスイツチ・モジ
   ユールをアレイ状に配列し、タスクが割り付けら
   れた演算処理装置からタスクを発生した演算処理
   装置に返送データを送出する際には、後者と前者
   の演算処理装置の相対的位置関係を示すコードの
   ビツト順を逆転したものを返送経路情報として、
   転送時の処理と同一の処理によりパケツト・デー
   タを返送することを特徴とするデータ転送装置。