JPS631633B2 - - Google Patents

Description

【発明の詳細な説明】 本発明は多数のスイツチモジユールを構成要素
とし、該スイツチモジユールを介して接続される
任意のプロセツサから他の任意のプロセツサへデ
ータ転送するデータ転送装置において、該データ
転送装置がプロセツサ負荷を動的に均等化するこ
とを可能としたデータ転送方式に関するものであ
る。

多数のプロセツサを転送系を介して結合した並
列処理計算機では、プロセツサ間の負荷を均等化
することが処理の効率化の観点から重要である。
負荷の均等化は、転送系が動的に負荷の配分をす
ることにより容易に実現できる。しかし、従来の
転送系の動作は受動的であつた。すなわち、プロ
セツサは転送先プロセツサを明記した転送要求を
転送系に出し、転送系はこれを受けて指定された
プロセツサへの転送を行つていた。そのため、負
荷の配分はソフトウエア側にまかされていた。換
言すれば、プログラマはプロセツサの負荷のバラ
ンスが平衡するようにプログラムする必要があつ
た。これは負荷の不平衡を起こす最大の要因であ
る。

第１図は従来の並列処理計算機の概略構成図で
ある。いま、このような並列処理計算機上で、第
２図ａに示すような分割統治法に代表される処理
形態が木構造をなすアルゴリズムの並列実行を考
える。木の１つのノードの処理を１つのプロセツ
サに割付ける。そうすると、木の名ノードは、第
２図ｂのように各プロセツサに割付けられ、明ら
かにプロセツサ間で負荷の不平衡を生じる。

ところで、負荷の配分の問題は、ソフトウエア
の負担の増加、処理オーバヘツドの増加、割付の
誤りによる負荷の不平衡などの問題を引き起し、
これがプロセツサの稼動率の低下、システムスル
ープツトの低下をもたらすことになる。

本発明の目的は、動的な負荷分散を可能とする
データ転送方式を提供することにある。

しかして、本発明はデータ転送方式をパケツト
転送方式とすることにより、転送先プロセツサの
動的な決定手段を簡単化するものである。又、本
発明は、プロセツサの負荷情報を転送系に与える
ため、複数の転送モードを持つことを特徴とし、
更にはプロセツサの負荷情報を把握するため、ス
イツチモジユールを通過するパケツト数をカウン
トするカウンタを持つことを特徴にしている。

以下、図示の一実施例にもとづいて本発明のデ
ータ転送方式を詳述する。

第３図は本発明の一実施例で、第３図ａは多数
のスイツチモジユール１を２次元アレイ状に結合
したデータ転送装置を示す。各スイツチモジユー
ル１にはプロセツサ２が接続される。一方、第３
図ｂは多数のスイツチモジユール３を多段構成し
たデータ転送装置４であり、データ転送装置４の
入出力にはプロセツサ５，５′が接続される。

第３図ａのスイツチモジユール１の構成図を第
４図ａに示し、第３図ｂのスイツチモジユール３
の構成図を第４図ｂに示す。第４図ａとｂにおい
て、６，１０は入力回路、７，１１はスイツチ、
８，１２は出力回路、９，１３はカウンタであ
る。

第３図ａとｂのどちらのデータ転送装置も基本
的動作は同じであるので、以下では第３図ｂのデ
ータ転送装置４について説明する。

第５図は第３図ｂに示すデータ転送装置４の構
成要素であるスイツチモジユール３の入力回路１
０、スイツチ１１、出力回路１２の詳細図であ
る。１３はカウンタ、１４は入力キユー、１５は
入力制御回路、１６はモードキユー、１７は出力
選択情報キユー、１８はセレクタ、１９はセレク
タ制御回路、２０はアービタ、２１はセレクタ、
２２はオアゲート、２３はカウンタ制御回路、２
４は比較回路である。

第６図は転送パケツトの構成図である。パケツ
トはデータバス巾単位に直列転送される。第６図
において、２５はパケツト頭部、２６はパケツト
本体であり、パケツト頭部２５の先頭部分は出力
選択情報に用いる。

さて、第３図ｂのデータ転送装置４では、タス
クをプロセツサ５，５′への割付単位とする。
こゝで、タスクとは第２図における木のノードの
ように、１つのまとまつた処理単位をいう。各プ
ロセツサはすべてのタスクの処理ができ、タスク
はその処理に必要なパラメータが揃つた時、起動
されるものとする。タスクが子タスクを生成した
場合（第２図の例では木の１つのノードが子のノ
ードに処理要求を出した場合）、プロセツサ負荷
を分散するため、子タスクは軽負荷プロセツサで
処理される。そのために、プロセツサは処理依頼
をデータ転送装置に発行する。データ転送装置は
軽負荷プロセツサを動的に探し、タスクを割付け
る。タスクの割付けられたプロセツサはその処理
を行い、結果を依頼元プロセツサに返す。当該シ
ステムでは、このようにタスク処理が進む。

上記プロセツサ負荷の動的な分散化を実現する
ために、本データ転送装置には３つの転送モード
があり、パケツトはいづれかの転送モードで転送
される。３つの転送モードは次の通りである。

(a) サーチモード（Ｓモード）； これは転負荷プロセツサを動的に探すための
転送モードである。このモードのパケツトは、
スイツチモジユール３において、それぞれの出
力回路１２に付随するカウンタ１３の値を比較
し、その小さい方の出力回路を選択する。そし
て、選択された側のカウンタの値をカウントア
ツプする。両カウンタの値が同じ場合は、いづ
れか一方の出力回路を選択する。

(b) トランスフアモード（Ｔモード）； これは転送先プロセツサが常に定まつている
場合の転送モードである。このモードのパケツ
トは、パケツト頭部の先頭に出力選択情報を持
つ。スイツチモジユール３では、この値に従つ
て出力回路１２が選択される。

(c) フイニツシユモード（Ｆモード）； これはタスク終了をデータ転送装置に知らせ
るための転送モードである。このモードのパケ
ツトは、パケツト頭部の先頭に出力選択情報を
持つ。スイツチモジユール３では、この値に従
つて出力回路１２が選択される。さらに、選択
された出力回路１２に付随するカウンタ１３の
値がカウントダウンされる。

これらの転送モードを用いると、プロセツサ負
荷の分散は次の手法により実現できる。

タスクが子タスクを生成すると、子タスク処理
に必要なデータをパケツトにして、データ転送装
置に処理要求をだす。このパケツトの転送モード
はＳモードである。データが複数個のパケツトに
なる場合は、そのうちの任意の一つをＳモードで
転送する。データ転送装置は子タスクの処理プロ
セツサが動的に決まると、処理先が決つた旨をパ
ケツトにして依頼元プロセツサに知らせる。この
転送モードはＴモードである。依頼元プロセツサ
は、このパケツトを受けとると、処理依頼が複数
個のパケツトで構成されている場合、残りのパケ
ツトをＴモードで転送する。処理先のプロセツサ
は、転送されたデータにより、子タスクの処理を
行い、結果を求め、それを１個ないし複数個のパ
ケツトにしてＴモードで依頼元プロセツサに返
す。依頼元プロセツサは、結果を受けとると、受
けとつた旨をパケツトにしてＦモードで転送す
る。子タスクの生成から消滅までの過程におい
て、このようなパケツトの転送が行われる。

各モードのパケツトに対し、スイツチモジユー
ル３の転送シーケンスは以下のようになる。

第５図において、入力キユー１４にはパケツト
が入つており、モードキユー１６には入力キユー
１４のパケツト対応にそのパケツトの転送モード
が入つており、出力選択情報キユー１７には、同
じく出力選択情報が入つているものとする。ただ
し、Ｓモードのパケツトに対する出力選択情報は
定義されないが、出力選択情報キユー１７にはダ
ミーデータを対応する出力選択情報として入れ、
各キユー１４，１６，１７のパケツトの順序関係
を保持するものとする。カウンタ１３は、出力回
路１２を通過したパケツトのうち、Ｓモードのパ
ケツトの個数とＦモードのパケツトの個数の差を
保持している。比較回路２４は２つの出力回路の
カウンタの値を比較し、大小関係を出力する。そ
れはセレクタ制御回路１９の入力となる。以下、
転送シーケンスを説明する。

(i) 入力制御回路１５は、モードキユー１６から
転送モード（mode）を出力し、自らは処理要
求信号（reg）を出す。転送モードはセレクタ
制御回路１９の制御信号となると同時に、セレ
クタ１８を径由して、次段スイツチモジユール
に送られる。

(ii) セレクタ制御回路１９は転送モードに従つ
て、比較回路２４（Ｓモードのとき）、又は出
力選択情報キユー１７の出力値（Ｔ，Ｆモード
のとき）からセレクタ１８の出力を決定する。

(iii) reg信号および転送モードは、セレクタ１８、
アービタ２０を径由して次段スイツチモジユー
ルの入力制御回路１５、モードキユー１６へ到
達する。

(iv) （次段スイツチモジユールの）入力制御回路
１５は入力キユー１４が一杯でない限り、ack
信号を返す。と同時に、転送モードをモードキ
ユー１６にとりこむ。入力キユー１４が一杯の
ときは、キユーに空きが生じるまでack信号を
返さない。また、転送モードもとりこまない。

(v) ack信号は、カウンタ制御回路２３の入力と
なり、転送モードにより、所定の動作（Ｓモー
ドならカウントアツプ、Ｆモードならカウント
ダウン、Ｔモードなら何もしない）をする。ま
た、セレクタ２１、オアゲート２２を径由して
入力制御回路１５へ行く。セレクタ１２の出力
は、アービタ２０が選択した入力回路１０に対
応する側の出力が選択される。

(vi) 入力制御回路１５は、入力キユー１４の先頭
にあるパケツトをセレクタ１８、アービタ２０
を径由して次段スイツチモジユールの入力キユ
ー１４へ転送する。このとき、出力選択情報
は、入力制御回路１５の制御のもとに出力選択
情報キユー１７にも入れられる。

(vii) パケツト転送終了後、入力制御回路１５は
reg信号をおとし、転送シーケンスを終了する。

以上説明したように、本発明によれば、データ
転送装置はスイツチモジユールに用意したカウン
タにより動的にタスクの分散化制御を行い、プロ
セツサ負荷を均等化することができるから、プロ
グラムの処理のスループツトや、プロセツサの稼
動率が上昇し、また、ソフトウエア側で負荷分散
を意識する必要がなくなる。さらに、簡単な回路
構成のスイツチモジユールを多数用いるので、
LSI化に適する。

【図面の簡単な説明】

第１図は従来の並列処理計算機の構成図、第２
図は木構造のプログラムの模式図および木のノー
ドを第１図の並列処理計算機に割付けた図、第３
図ａ，ｂは本発明のデータ転送方式の一実施例の
構成図、第４図ａ，ｂは第３図ａ，ｂのスイツチ
モジユールの構成図、第５図は第４図ｂのスイツ
チモジユールの詳細構成図、第６図はパケツトの
構成図である。 １，３…スイツチモジユール、２，５，５′…
プロセツサ、４…データ転送装置、６，１０…入
力回路、７，１１…スイツチ、８，１２…出力回
路、９，１３…カウンタ、１４…入力キユー、１
５…入力制御回路、１６…モードキユー、１７…
出力選択情報キユー、１８，２１…セレクタ、１
９…セレクタ制御回路、２０…アービタ、２２…
オアゲート、２３…カウンタ制御回路、２４…比
較回路、２５…パケツト頭部、２６…パケツト本
体。

Claims (1)

【特許請求の範囲】
1. １ 複数の入力と複数の出力を持ち、任意の入力
   から任意の出力へスイツチできるスイツチモジユ
   ールを複数個結合して構成され、該スイツチモジ
   ユールを介して接続される任意のプロセツサから
   任意のプロセツサへデータ転送ができるデータ転
   送装置において、前記スイツチモジユールは出力
   対応に配下のプロセツサの負荷を表示するための
   カウンタを持ち、且つ、データ転送装置はパケツ
   トによりデータ転送を遂行し、その転送モードと
   して、軽負荷プロセツサを動的に探すためのモー
   ドと、プロセツサ負荷が軽減されたことを知らせ
   るためのモードと、指定したプロセツサへデータ
   を転送するモードとを有し、前記軽負荷プロセツ
   サを動的に探すための転送モードのパケツトは、
   スイツチモジユールにおいてカウンタ値の最も小
   さい出力を選択して該当カウンタをカウントアツ
   プし、また、前記プロセツサの負荷が軽減された
   ことを知らせるための転送モードのパケツトはカ
   ウンタをカウントダウンし、これらのカウンタ操
   作によりプロセツサ負荷情報をデータ転送装置に
   与え、該データ転送装置がプロセツサ負荷を動的
   に分散化することを特徴とするデータ転送方式。