JPS58200366A

JPS58200366A - デ−タ転送方式

Info

Publication number: JPS58200366A
Application number: JP57083632A
Authority: JP
Inventors: Tadashi Naruse; 正成瀬; Masato Amamiya; 雨宮　真人
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1982-05-18
Filing date: 1982-05-18
Publication date: 1983-11-21
Also published as: JPS631633B2

Abstract

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

Description

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

多数のプロセッサを転送系を介して結合した並列処理計
算機では、プロセッサ間の負荷を均等化することが処理
の効率化の観点から重要である。

負荷の均等化は、転送系が動的に負荷の配分をすること
により容易に実現できる。しかし：従来の転送系の動作
は受動的であった。すなわち、プロセッサは転送先プロ
セッサを明記した転送要求を転送系に出し、転送系はこ
れを受けて指定されたプロセッサへの転送を行っていた
。そのため、負荷の配分はソフトウェア側にまかされて
いた。換言すれば、プログラマはプロセッサの負荷のバ
ランスが平衡するようにプログラムする必要があった。

これは負荷の不平衡を起こす最大の要因である。

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

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

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

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

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

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

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

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

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

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

さて、第８図＜ｈ）のデータ転送装置４では、タスクを
プロセッサ５．５′への割付単位とする。こ＼で、タス
クとは第２図における木のノードのように、１つのまと
まった処理単位をいう。各プロセッサはすべてのタスク
の処理ができ、タスクはその処理に必要なパラメータが
揃った時、起動されるものとする。タスクが子タスクを
生成した場合（第２図の例では木の１っのノードが子の
ノードに処理要求を出した場合）、プロセッサ負荷を分
散するため、子タスクは軽負荷プロセッサで処理される
。そのために、プロセッサは処理依頼をデータ転送装置
に発行する。データ転送装置は軽負荷プロセッサを動的
に探し、タスクを割付ける。

タスクの割付られたプロセッサはその処理を行い、結果
を依頼元プロセッサに返す。当該システムでは、このよ
うにタスク処理が進む。

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

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

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

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

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

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

依頼元プロセッサは、結果を受けとると、受けとった旨
をパケットにしてＦモードで転送する。子タスクの生成
から消滅までの過程において、このようなパケットの転
送が行われる。

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

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

（１）入力制御回路１５は、モードキュー１６から転送
モード（ｍｏｄｅ）を出力し、自らは処理要求信号（ｒ
ｅｑ）を出す。転送モードはセレクタ制御回路１９の制
御信号となると同時に、セレクタ１８を径由して、次段
スイッチモジュールに送られる。

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

１ｉ）　　ｒｅｑ信号および転送モードは、セレクタ１
８、アーービタ２０を径由して次段スイッチモジュール
の入力制御回路１５、モードキュー１６へ到達する。

（ｉＶ）　　（次段スイッチモジュールの）入力制御回
路１５は入力キュー１４が一杯でない限り、αｃｋ信号
を返す。と同時に、転送モードをモードキュー１６にと
りこむ。入力キュー１４が一杯のときは、キューに空き
が生じるまでａｃｋ信号を　・返箸ない。また、転送モ
ードもとりこまない。

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

（ｖｌ）入力制御回路１５は、入力キュー１４の先頭に
あるパケットをセレクタ１８、アービタ２０を径由して
次段スイッチモジュールの入力キュー１４へ転送する。

このとき、出力選択情報は、入力制御回路１５の制御の
もとに出力選択情報キュー１７にも入れられる：、・。

（ｖｌｌ）パケット転送終了後、入力制御回路１５はｒ
ｅｑ信号をおとし、転送シーケンスを終了する。

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

【図面の簡単な説明】

第１図は従来の並列処理計算機の構成図、第２図は木構
造のプログラムの模式図および木のノードを第１図の並
列処理計算機に割付けた図、第８図（α）、（ｂ）は本
発明のデータ転送方式の一実施例の構成図、第４図（α
）、（ｂ）は第３図（ａ）、（ｈ）のスイッチモジュー
ルの構成図、第５図は第４図＜ｂ＞のスイッチモジュー
ルの詳細構成図、第６図はパケットの構成図である。　
。１．３・・・スイッチモジュール、２，５．５’・・・
プロセッサ、４・・・データ転送装置、６，１０・・・
入力回路、７．１１・・・スイッチ、８．１２・・・出
力回路、９．１３・・・カウンタ、■４・・・入力キュ
ー、１５・・・入力制御回路、１６・・・モードキュー
、１７・・・出力選択情報キュー、：ｔｓ、２１・・・
セレクタ、１９・・・セレクタ制御回路、ｚＯ・・・ア
ービタ、２ｚ・・・オアゲート、２３・・・カウンタ制
御回路、２４・・・比較回路、２５・・・パケット頭部
、２６・・・パケット本体。代理人　弁理士　　鈴　　木　　　　　誠（’：（Ｂ］
り１第３図（α）第４図Ｃ（１）（ｂ）

Claims

【特許請求の範囲】

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