JPH02279046A - データ転送システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はデータ処理ユニット間で最適化された数の同時
的なデータパケットの転送を遂行するための交換システ
ムに関する。

Ｂ、従来の技術及びその課題 データ処理ユニット間におけるデータパケットの転送の
ための技術が幾つかある。たとえば、これらのユニット
が通常の時分割多重化バスに接続されるものがある。こ
の手法の欠点は所与の太きさの帯域幅が割振られている
ユニットの間でデータの転送がない場合でも２つのユニ
ットの接続の間はこの帯域幅を確保しておかなければな
らないことである。

データ処理ユニット間の同時的なデータ転送を可能にす
る別の手法が米国特許第４６２３９９６号に記載されて
いる。この特許に記載されたパケット交換ノードはＮ個
の入力ボート及びＭ個の出力ボートを有する。各入力ボ
ートには１つの待ち行列セットが関連し、各セットは１
つの待ち行列を含む。各人力ボートは待ち行列セレクタ
に接続される。このセレクタによって、受信されたパケ
ットは経路指定されるべき出力ボートに関連する待ち行
列に記憶される。各待ち行列セットの待ち行列は、同じ
出力ボートについて競合する各セットの待ち行列に記憶
されたデータパケットの間の調停を行う異なる出力調停
手段に接続される。この交換ノードは待ち行列をこれら
の出力調停手段に接続するＮ、Ｍ個のバスを有するので
、この手法は入力ボート及び出力ボートの数が大きい場
合には実用に適しないものとなる。

そこで、本発明はデータ処理ユニットの間で最適な数の
同時転送を遂行できるようなシステムを提供することを
目的としている。

本発明の他の目的は複数のデータ処理にユニット対して
均等なサービスの機会を与えるようなシステムを提供す
ることにある。

本発明の他の目的はデータ転送の性能を改善するシステ
ムを提供することにある。

Ｃ０課題を解決するための手段 この目的を達成するため、Ｎ個のデータ処理ユニット（
以下、単にユニットともいう）の中から選択された起点
ユニット及び宛先ユニットからなる複数のユニットのペ
アの間でのデータパケットの転送を行うため、各データ
処理ユニットはアウトバンド待ち行列のセットを有し該
アウトバウンド待ち行列はぞれぞれ当該データ処理ユニ
ットのデータパケットの送り先である１つのデータ処理
ユニットに関連しかつ該関連するデータ処理ユニットへ
送るべきデータパケットを記憶するような本発明のデー
タ転送システムは（ａｌ固定された期間であるバースト
時間Ｔｉを定めるためのタイミング信号を供給するクロ
ック手段と、（ｂ）　Ｎ個のデータ処理ユニットから受
け取られた転送要求に基づいて条件的にユニットの異な
る複数のペアを選択するため各バースト時間の間に活動
する中央選択手段と、（Ｃ）上記中央選択手段に設けら
れ、選択された各ペアの宛先ユニットのアドレスを該ペ
アの起点ユニットに送るための送信手段と、（ｄ）１つ
の受信データバス及び１つの送信データバスを介してＮ
個のデータ処理ユニットのそれぞれに接続され、選択さ
れた起点ユニットから受取られた選択された宛先ユニッ
トのアドレスに応答して、バースト時間Ｔｉの間に選択
された各ペアの宛先ユニットと起点ユニットとの間の接
続を次のバースト時間Ｔｉ　　　　（Ｋは１以上の整数
）のｒ＋に 間に行うデータ交換手段と、を有することにより、選択
された複数の起点ユニットから宛先ユニットへのデータ
パケットの転送を同時に行うようにしたことを特徴とし
ている。

本発明の実施例ではデータ転送システムにおいて、さら
に、バースト時間Ｔｉが少な（ともＮ個のサイクルを含
み、上記中央選択手段が１ないしＮの各サイクルで条件
的にユニットの１つのペアを選択するため各バースト時
間Ｔｉの最初のＮすイクルの間活動化され、（ａ）第１
に、Ｎ個のデータ処理ユニットから受取られた転送要求
に基づいて、所定のバースト時間の所与のサイクルで起
点ユニット及び宛先ユニットとして選択されたユニット
を、同じ所定のバースト時間の他のサイクルでは起点ユ
ニット及び宛先ユニットとしては選択しないで、Ｔｂ）
第２に、最初のサイクル（以下、サイクル（イ）という
）の間、前のバースト時間Ｔｉ−Ｎの最初のサイクル（
以下、サイクル（ロ）という）の間に選択されたユニッ
トのペアに基づいて、他のペアが選択できる場合はサイ
クル（ロ）で選択されたユニットのペアをサイクル　（
イ）では選択しないで、（ｃ）第３に、２番目ないしＮ
番目のサイクルの間、直前のバースト時間の３番ない間
野３番目ないしＮ番目及び最初のサイクルで選択された
ユニットの複数のペアに基づいて、それぞれ他のペアが
選択できる場合は直前のバースト時間の３番目ないしＮ
番目及び最初のサイクルの間に選択されたユニットのペ
アを現バースト時間Ｔｉの２番目ないしＮ番目のサイク
ルではそれぞれ選択しない、ことを特徴としている。

また、本発明の他の実施例ではデータ転送システムは、
さらに、上記中央選択手段が下記の（ａｔないし　ｌｄ
）の手段を有することを特徴としている。

（ａ）　　アウトバウンド待ち行列についての空又は空
でないという状況の変更を表わす情報の形式でＮ個のデ
ータ処理ユニットから転送要求を受取りかつＮ個の記憶
位置のＮ個のセット（行１ないし行Ｎ）を有する第１の
記憶手段（各記憶装置はそれぞれ１つのデータ処理ユニ
ットに割当てられ、Ｎ個のデータ処理ユニットにおける
所与の１つのデータ処理ユニットに関連するアウトバウ
ンド待ち行列についての空又は空でないという状況を表
わす情報は記憶位置の１つのセットに記憶される）。

Ｔｂｌ　　バースト時間の各サイクルで選択されたユニ
ットのペアのアドレスを記゛臆するための第２の記憶手
段。

（ｃｌ　　バースト時間Ｔｉ　　のサイクルｌで選択さ
１　＋４ れたペアのアドレスと直前のバースト時間Ｔｉのサイク
ル３ないしＮ及びサイクル１で選択されたペアのアドレ
スとを取得するよう、上記クロック手段からのタイミン
グ信号に応答して、現バースト時間Ｔｉのうちの連続的
なサイクル■ないしＮの間に上記第１の記憶手段におけ
る記憶位置の１つのマットを連続的にアドレスし次に上
記第２の記憶手段をアドレスするためのアドレス指定手
段。

（ｄｌ　　上記アドレス指定手段によってアドレスされ
たときに上記第１及び第２の記憶手段から読取られた情
報に応答して、現バースト時間Ｔｉのうちの１ないしＮ
の各サーイクルの間に条件的に選択できるペアの起点ユ
ニット及び宛先ユニットのアドレスを判断し該アドレス
を上記送信手段に供給するための選択処理手段。

また、本発明の他の実施例ではデータ処理システムは、
さらに、上記第１の記憶手段がＮ個の記憶位置のＮ個の
セットで構成されるＮ個の行を有するＮ行Ｎ列のマトリ
クスを含むことによって、１ないしＮの各サイクルで該
マトリクスの１つの行が上記アドレス指定手段でアドレ
スさ°れかつ該アドレスされた行の内容が読取られて上
記選択処理手段に供給される（行のアドレスは上記選択
処理手段によって条件的に選択される起点ユニットとペ
アになる宛先ユニットを表わしている）ことを特徴とし
ている。

以下、本発明の作用を実施例とともに説明する。

Ｄ、実施例 第１図に示すように、本発明に基づくシステム主要部は
スケジューラ４及びデータ交換手段６を有する交換論理
回路２である。

交換論理回路２はＮ個のバス１０−１ないし１Ｏ−Ｎを
それぞれ介してＮ個のデータ処理ユニット８−１ないし
８−Ｎに接続される。

バス１０−１ないし１０−Ｎはそれぞれ直列制御信号を
伝達するのに用いられる３本の線、すなわち、制御入力
線１２−１ないし１２−Ｎ、制御出力綿１４−１ないし
１４−Ｎ及び交換制御綿１６−１ないし１６−Ｎを有す
る。バス１０−１ないし１０−Ｎのうち制御入力綿１２
−１ないし１２−Ｎ及び制御出力線１４−１ないし１４
−Ｎはスケジュ−ラ４に接続され、交換制御綿１６−１
ないし１６−Ｎはデータ交換手段６に接続される。

バスｔｏ−１ないし１０−Ｎは、さらに、データ送信綿
ＸＭＩＴ１８−１ないし１８−Ｎ及びデータ受信綿ＲＣ
Ｖ２０−１ないし２０−Ｎをそれぞれ有する。これらの
線はデータ処理ユニュト８−１ないし８−Ｎとデータ交
換手段６との間のデータバイトの並列的な伝達のために
それぞれ用いられるものである。その他、スケジューラ
４はデータ転送オペレーションの時間調整を行うため、
クロックバス１１を介してクロック信号をデータ処理ユ
ニット８及びデータ交換手段６に送り、データ処理ユニ
ット８からクロック信号を受け取る。

本発明に従って、データ処理ユニット間で転送すべき情
報ストリームは固定長のバーストに切り刻まれる。これ
らのバーストは１バ一スト時間で同期的に交換される。

すなわち、これらのバーストの場合、伝送は同じときに
開始され終了する。

バースト時間は１データバーストの転送に必要な時間に
等しい。

スケジューラ４はＮ個のデータ処理ユニット８−１ない
し８−Ｎの中から送信ユニット（起点ユニット）及び対
応する受信ユニット（宛先ユニット）を含むユニットの
複数のベアを選択する。その選択機構（後で説明する）
は各バースト時間の間にデータ処理ユニットの異なるペ
アの最大の数を選択することによって交換論理回路２の
全体的な交換能力を最適化する。この選択機構に従って
、これらのユニットは送信、受信又は送信及び受信の双
方について選択することができる。

要約するに、バースト時間Ｔｉの間に、前のバ−スト時
間Ｔｉ　　の間に選択されたペアのデー１−に 夕処理ユニットの間で同時的な転送が関連するデータ受
信線及びデータ送信線を介して遂行され、スケジューラ
４が次のバースト時間、　　の間に１＋１ データ転送の遂行のために選択されるデータ処理ユニッ
トの複数のベアを決定する。この選択は線１２−１ない
し１２−Ｎを介してデータ処理ユニットによって供給さ
れる制御入力信号の下で遂行される。さらに、本発明の
好適な実施例においては、この選択は前のバースト時間
の間に遂行される転送に基づいて行われる。これは、各
データ処理ユニットの選択の機会を均等にするためであ
る。

バースト時間Ｔｉ　　の間に線１４−１ないしｌ−に １４−Ｎを介して受け取られた制御出力信号に応答して
、データ処理ユニット８−１ないし８−Ｎは線１６−１
ないし１６−Ｎに交換制御信号を出す。これらの信号が
データ交換手段６に供給されることにより、次のバース
ト時間Ｔｉの間にデー！ 夕の転送を遂行すべ（、スケジューラ４で選択されたユ
ニットの複数のベアに従ってデータ送信線１８−１ない
し１８−Ｎ及びデータ受診線２０−１ないし２０−Ｎが
接続される。

そうして、任意のバースト時間の間、複数のデータバイ
トがデータ処理ユニットの選択された複数のペアの間で
転送される。

いずれのユニットも別のユニットからのデータバイトを
受け取ったり、別のユニットにデータを送ったり、又は
送信及び受診の双方を行うことができる。

ｋの値は本発明の実施の態様により異なる。好適な実施
例では、制御出力信号及び交換制御信号は、綿の数を減
らすため、直列的に伝送される。

この場合、ｋの値として２が選択される。

説明をわかり易（するため、本システムが４つのデータ
処理ユニット８−１ないし８−Ｍ　（Ａ。

Ｂ、Ｃ，Ｄと呼ぶ）を有するものとして本発明のシステ
ムを記載する。もちろん、本発明はこのようなユニット
の数に限定されるものでないことば当業者には理解され
るであろう。

第２図は本発明に基づくシステムを実現するためにデー
タ処理ユニットＡ、Ｂ、Ｃ及びＤに必要な手段を表わす
。

各ユニットはデータの送信及び受信を処理する通常のデ
ータ処理手段２２を有する。

送信すべきデータはバス２６を介して待ち行列マネジャ
２４に供給され、受信データはバス２８を介して待ち行
列マネジャ２４からデータ処理手段２２に供給される。

送信すべきデータ及び受信デー・夕はメモリ３０に記憶
される。各ユニットは自分自身又は他のユニットを自己
のデータを送信することのできる宛先とみなす。したが
って、メモリ３０は各ユニットへの待ち行列を収容する
。これらの待ち行列はアウトバウンド待ち行列と呼ばれ
る。

ところで、データ処理ユニットは４つ（Ａ、Ｂ、Ｃ，Ｄ
）存在すると仮定したので、４つのアウトバンド待ち行
列ＱＯ，ＱＯＱＯ及びａ　　　　ｂゝ　　Ｃ ＱＯｄが存在することとなる。たとえば、ユニツトＡの
場合、折返しテスト用にユニットＡに送信すべきデータ
をエンキューするためにアウトバンド待ち行列ＱＯがユ
ニットＡで使用され、アラトバウンド待ち行列ＱＯ５は
ユニットＢに送信すべきデータをエンキューするために
ユニットＡで使用され、アウトバウンド待ち行列ＱＯは
ユニットＣに送信すべきデータをエンキューするために
ユニットＡで使用され、アウトバンド待ち行列ＱＯｄは
ユニットＤに送信すべきデータをエンキュウするために
ユニットＡで使用される。

好適な実施例では、ユニットＡ、Ｂ、Ｃ及びＤにつきそ
れぞれインバウンド待ち行列ＱＩ　　、ＱＩ　　　ＱＩ
　　及びＱＩｄが存在する。これらはｂ″　　　　　Ｃ バス１０−１の線２０−１を介して待ち行列セレクタ３
２の制御の下でユニットＡ、Ｂ、Ｃ及びＤからの受信デ
ータをエンキューするために用いられるものである。こ
れらのインバウンド待ち行列から読み取られたデータは
待ち行列マネジャ２４の制御の下でデータ処理手段２２
に送られる。

アウトバウンド待ち行列に関する限り、待ち行列マネジ
ャ２４はそのデータがアドレス指定される宛先ユニット
に基づいて選択されるアウトバウンド待ち行列における
データの記憶オペレーションを制御する。宛先ユニット
のアドレスは従来と同様、データメツセージのヘッダ部
分に含まれる。待ち行列マネジャ２４はアウトバウンド
待ち行列の状況に関する標識を待ち行列状況変更エンコ
ーダ３４に供給する。この情報を使って線１２−１ない
し１２−４へ制御入力信号を出して、スケジューラ４の
要求マトリクス３６（後の第３図の説明参照）を更新す
る。

各アウトバウンド待ち行列では、制御入力信号は、アウ
トバウンド待ち行列が空か又は空でないかを示す状況ビ
ットと、対応する待ち行列の宛先とを含む待ち行列状況
情報を伝達する。これらの信号は１本の線だけで直列的
に送っても良い。要求マトリクスの更新は状況の変更の
検出後、すぐに行う必要はないからである。

待ち行列セレクタ３２は４９１４−１からの制御出力信
号を受取って、これらの信号によって伝達されたアウト
バウンド待ち行列の宛先に基づき、選択されたアウトバ
ウンド待ち行列の内容を線１８−１を介して交換制御信
号と共に送る。これについては、後で第３図を参照して
詳説する。

さらに、待ち行列セレクタ３２は制御入力信号によって
伝達されたインバウンド待ち行列の宛先に基づいて選択
されたインバウンド待ち行列に記憶すべきバス２０−１
からの受信データを経路指定する。

本発明の他の実施例によれば、他のユニットから受信し
た全てのデータバーストをエンキューするため単一のイ
ンバウンド待ち行列を用いることができる。この場合、
制御入力信号においてインバウンド待ち行列の宛先を送
る必要はない。

第３図は交換論理回路２を構成するスケジューラ４及び
データ交換手段６を示す図である。

スケジューラ４は各データ処理ユニットのアウトバウン
ド待ち行列の状況に関する標識を記憶するために用いら
れる要求マトリクス３６を有する。好適な実施例では、
このマトリクスは４行×４列で構成される。エレメント
Ｔ１．（行ｉ及び列Ｊ ｊ）はユニットｊにおけるユニットｉへのアウトバウン
ド待ち行列の状況を表す。たとえば、エレメント”２３
における“１゛°はユニットＣにおけるアウトバウンド
待ち行列Ｑｏｂが空でないことを示している。これは、
ユニットＣがユニットＢへの転送要求を有することを意
味する。

要求マトリクスはたとえば以下の第１表のような構成を
有する。

第　　　１　　　表 データ処理ユニット アウト バウンド 待ち行列 行１ 行２ 行３ 行４ 第１表の例では、ユニットＡがＣに送信すべきデータを
有し、ユニットＢがＡに送信すべきデータを有し、ユニ
ットＣがＢ及びＤに送信すべきデータを有し、ユニット
ＤがＡ及びＣに送信すべきデータを有することを意味す
る。

メモリで実現しうる要求マトリクス３６における情報は
線１２−１ないし１２−４から受取られた制御入力信号
から生成されて、要求宛先ユニットアドレスレジスタＲ
ＵＴＡ３８に記憶される。このレジスタは４つの記憶位
置を有しく１つの位置が１つのユニットに対応する）、
対応するユニットにおけるアウトバウンド待ち行列に関
する状況の変更を記憶する。

この情報はクロック４４に出力線４４で供給されるクロ
ックタイミング信号の制御の下で動作する制御回路４０
に与えられる。これは、スケジューラ４で使用されたい
場合に要求マトリクスの行の内容を更新するようにする
ためである。

クロック４４は各バースト時間Ｔの間にスケジューラ４
によって遂行されるオペレーションの逐次処理を制御す
る。好適な実施例では、バースト時間Ｔｉは少なくとも
Ｎ＋１サイクルに分けられす る。選択アルゴリズムプロセッサ４６は各バースト時間
の最初のＮ個のサイクルの時（すなわち、サイクル−な
いし４）に動作して、データバーストの転送のために次
のバーストＴｉの間に選択さ！ れるユニットのペアを決定する。サイクル−ないし４の
期間を決めるタイミング信号はバス４８を介して選択ア
ルゴリズムプロセッサ４６及び制御回路４０に供給され
る。サイクル５の期間を決めるタイミング信号は線４２
で供給される。選択されたユニットのアドレスは時間Ｔ
ｉ　　の間の転１＋２ 送を制御するため時間Ｔｉ　　の間に送られる。

１＋１ １バ一スト時間の１ないし４の各サイクルで、要求マト
リクスの１行が読取られて選択アルゴリズムプロセッサ
４６に供給され、転送要求がその行のパターン及び選択
記録パターン（選択記録マトリクス５０に記録されてい
るものであり、これについては後で説明する）に基づい
て選択される。各サイクルで、一対の選択されたユニッ
トについてのアドレスが次宛先ユニットアドレスレジス
タＮＴＵＡ５２及び決起点ユニットアドレスレジスタＮ
０ＵＡ５４に記憶される。これらのレジスタ５２及び５
４はそれぞれ４つの位置（５２−１ないし５２−４及び
５４−１ないし５４−４）を有する。１つの位置は１つ
のユニットに割り当てられている。

たとえば、レジスタ５２及び５４の位置１ないし４はユ
ニットＡないしＤにそれぞれ割当てられる。各サイクル
で、１つの起点ユニットと１つの宛先ユニットとか成る
一対のユニットを選択することができる。選択された起
点ユニット及び宛先ユニットがそれぞれユニットＡ及び
Ｂと仮定すると、ユニットＢのアドレスはレジスタ５２
においてユニットＡに割当てられた位置１に記憶され、
ユニットＡのアドレスはレジスタ５４においてユニット
Ｂに割当てられた位置２に記憶される。

バースト時間の最後のサイクル（サイクル５）の間に、
レジスタ５２及び５４の内容は直列化器５６に供給され
る。

レジスタ５２及び５４の位置ｌに含まれる宛先ユニット
及び起点ユニットのアドレスはバス１１の１本の綿を介
するビットクロック信号の制御の下で直列化され、）Ｊ
ｉ　１４−１を介してユニットＡに送られる。レジスタ
５２及び５４の位置２に含まれる宛先ユニット及び起点
ユニットのアドレスは直列化されて線１４−２を介して
Ｂに送られる。レジスタ５２及び５４の位置３に含まれ
る宛先ユニット及び起点ユニットのアドレスは直列化さ
れて）Ｉ　１４−３を介してユニットＣに送られる。レ
ジスタ５２及び５４の位置４に含まれる宛先ユニット及
び起点ユニットのアドレスは直列化されて線１４−４を
介してユニットＤに送られる。

こうして各ユニットはデータの送り先であるユニットの
宛先アドレスと、自分の受信するデータを発したユニッ
トの起点ユニットとを受取る。

次のバースト時間の間、これらのユニットは線１４−１
ないし１４−Ｎを介する制御出力信号に含まれている宛
先アドレス情報及び線４２を介するサイクル５のタイミ
ング信号に応答して、線１６−１ないし１６−４を介し
て適切な交換制御信号をゲート論理６０は供給するゲー
ト論理６０は交換制御信号に応答してバス６２に適切な
ゲート信号を生成し、時間Ｔｉ　　の間に選択された転
１＋２ 送を遂行できるように交換部６４における適切な論理ス
イッチを閉じる。交換部６４は論理ＡＮＤ１０Ｒ回路構
成を含んでいてもよい。待ち行列セレクタ３２は制御出
力信号に含まれる起点アドレスに応答して受信データを
その起点ユニットに対応するインバウンド待ち行列にゲ
ートする。

次に、選択アルゴリズムプロセッサ４６によって実行さ
れる選択方法について説明する。第４図は選択アルゴリ
ズムプロセッサ４６の詳細を示す図である。

この選択は選択アルゴリズムプロセッサ４６によって行
われる。プロセッサ４６は要求マトリクスの１つの行に
記憶されたビットパターンから導出される１つのビット
パターンを処理する。上記ビットパターンはデータ処理
ユニットの数と同じだけのビットを有しており（この場
合、４つ）れる別の４ビツトのパターンで与えられる位
置の後にはじめてあられれる°゛ｌ”を選択するように
して行われる。この選択された°゛ｌ°゛はその行が処
理されたときに選択されたペアの起点ユニット及び宛先
ユニットの標識を与えるものである。

選択記録マトリクス５０は２つのマトリクスを含む。１
つは基本マトリクス（７０）と呼ばれ、もう１つは相補
マトリクス（７２）と呼ばれる。

これらのマトリクスは４つの行を有する。すなわち、要
求マトリクス３６の行１ないし４に対応する行ｌないし
４である。

選択プロセスは各バースト時間のサイクルｌないし４の
間に行われる。各サイクルで、アドレスカウンタ７４は
要求マトリクス３６及び相補マトリクス７２をアドレス
する。基本マトリクス７０はサイクルｌだけでアドレス
される。

要求マトリクス３６から読取られたビットパターンは行
読取りレジスタ７６に記憶される。サイクルｌで、基本
マトリクス７０から読取られた情報が基本レジスタ７８
に記憶され、サイクル２ないし４で、相補マトリクス７
２から読取られた情報が相補レジスタ８０に記憶される
。

マスクレジスタ８２は４ビツトを有するマスクパターン
Ｐｍを記憶する（データ処理ユニットの数を４つと仮定
した）。マスクパターンＰｍはインバータ８３を介して
２４個のＡＮＤゲートで構成されるブロック８４に供給
される。レジスタ７６の内容はバス８６を介してブロッ
ク８４に供給され、こう、してブロック８４はレジスタ
７６に記憶されたビットパターンをマスクレジスタ７８
の内容によって修正したバス８８に出力する。

選択アルゴリズムプロセッサ４６はセレクタ９０を含む
。セレクタ９０はブロック８４の出力バス８８と、基本
レジスタ７８の出力バス９２と、相補レジスタ８０の出
力バス９４とに接続される。選択アルゴリズムプロセッ
サ４６は、さらに制御情報すなわちサイクルｌないし４
を設定するバス４８からのクロック信号と、アドレスカ
ウンタ７４によってバス７５を介して供給される行アド
レス情報とを受取る。

各サイクル１ないし４の終りで、相補マトリクス７２の
内容及びマスクレジスタ８２の内容が更新される。これ
について後で説明する。基本マトリクスの内容はサイク
ルｌの終りだけで更新される。

セレクタ９０はレジスタ５２及び５４の４つの位置に書
込むべきＮＴＵＡ及びＮ０ＵＡの情報を出力バス９６及
び９８を介してそれぞれ供給する。

セレクタ９０はさらにマスクレジスタ８２及びマトリク
ス７０．７２の内容を更新するために使用すべき更新情
報をバス９９を介して供給する。

次に、選択アルゴルズムプロセッサ４６のオペレーショ
ンを下記の第２表及び第３表を参照しながら説明する。

これらの表は、３つのバースト時間の間に走行する選択
プロセスによって選択された、起点ユニット及び宛先ユ
ニットを含むユニットのペアを表わしている。第２表は
第３表に示される要求マトリクスの１つの行を処理する
ための、各サイクルで処理される情報を表わす。第３表
は各サイクルの終りで更新されたときの基本マトリクス
及び相補マトリクスの内容を表わす。説明の簡単のため
、これらは要求マトリクスについて起こりつる更新は考
慮していない。これが生じれば、新しい要求マトリクス
は初期のマトリクスと同様にして処理されることになる
。

第２表においては、マスクレジスタ８２のマスクパター
ンＰｍについての２つの値と、基本レジスタ７８及び相
補レジスタ８ｏに記憶されたパターン存在する。上方の
値は選択を遂行するために用いられる値を表わし、下方
の値はそのサイクルの終りで更新された値を示す。

マスクパターンＰｍはアルゴリズムの走行につれて構成
される。マスクパターンは各バースト時間の始まりでは
ブランクであり、行が処理されるたびに変更される。マ
スクパターンはそのバースト時間の終りでゼロにリセッ
トされる。

マスキングのルールは次の通りである。行がＩ処理され
２ＪからＩへの要求が選択されたときは（ここで、■及
びＪはＡ、Ｂ％Ｃ又はＤである）、起点Ｊは再び選択さ
れるということのないよう、次の行の処理の間はマスク
する必要がある。したがって、選択された起点ユニット
に対応する。マスクレジスタ８２の位置に“１°°が書
込まれる。なお、第１表の例では、レジスタ８２の最左
端の位置がユニットＡ、Ｊｌ右端の位置がユニットＤに
対応するものと仮定した。

一対のユニットの選択は各行ごとに遂行されている。こ
れは、所定のバースト時間のうちの連続的なサイクル１
ないし４の間に同じユニットを宛先ユニットとして選択
す、ることができないようにするためである。この選択
は、サイクルｌのはじまりにおける基本マトリクス７０
の対応する行の内容及びサイクル２ないし４のはじまり
における相補マトリクス７２の対応する行の内容によっ
て決まる位置からマスクされた行における最初の°１”
を検出することによって遂行される。ｌが選択された場
合は、そのマスクパターンだけでなく、相補マトリクス
及び基本マトリクスの内容も更新される（第２表及び第
３表参照）。

ｏ　Ｏｏ　０ −ｔｏｏ。

く−ベム 基本マトリクス７０は１つのバーストのサイクル１だけ
で使用され、最初の行ｉが処理されたときに一対のユニ
ットの選択を遂行するために用いられる選択パターンを
選択アルゴリズムプロセッサ４６に供給する。基本マト
リクス７０の各行ｉは１行ｉが最初の行として処理され
た最後のと、き、すな゛わち、４バ一スト時間前に選択
された起点ユニットの標識を含む。

説明の簡単のため、第２表及び第３表においては、基本
マトリクス及び相補マトリクスの行は４つのエレメント
を有し、各エレメントは１つのユニットに対応し、最左
端のエレメント及び最右端のエレメントはそれぞれユニ
ットＡ及びユニットＤに対応している。しかしながら、
レジスタ７８及び８０に記憶されるたった１つの１しか
含まないＮビットのパターンで（Ｎはユニットの数）基
本マトリクス及び相補マトリクスの内容をエンコード及
びデコードしてもよい。

現アルゴリズム・の走行の結果として選択された新しい
起点ユニットは第２表及び第３表に示すように基本マト
リクス７０及び相補マトリクス７２の双方に保管される
。起点ユニットが選択されていない場合は、行ｉの内容
は双方のマトリクスにおいて変更されずそのままである
。

基本マトリクスは、少なくとも４Ｒバーストごとにマト
リクス３６の１つの行における１つの要求が出力される
ことを保証する（ここで、Ｒは当該行における要求セッ
トの数である）。最悪のケースでは、Ｒは４に等しい。

次にサイクル２ないし４で、相補マトリクス７２の内容
を用いて選択プロセスが遂行される。

相補マトリクス７２は要求マトリクス最初の行以外の全
ての行の処理のために使用される。それは選択アルゴリ
ズムプロセッサ４６に相補マトリクスの行から読取られ
た選択パターンを供給する。

行ｋが処理されるとき、相補マトリクス７２の行ｋがプ
ロセッサ４６に供給される。その内容は当該行の処理の
間すなわち直前のバースト時間で選択された起点ユニッ
トの記録である。

要求を１つも選択できないときは、相補マトリクス７２
の内容は変更されずそのままである。基本マトリクスは
相補マトリクスが使用される場合は更新されたい。相補
マトリクスの目的は新しい起点ユニットの選択が直前に
選択された起点ユニットに続く位置から始まるときに所
与の宛先ユニットへのトラヒックを共有することである
。

好適な実施例では、これらの３つのマトリクスはシフト
レジスタとして実現される。要求マトリクス３６は各バ
ースト時間に間に５回移動する。サイクル１ないし４の
間は４つの行を処理するためであり、サイクル５０間は
行番号を１つだけ増分するためである。第２表に示すよ
うに、行２はバースト時間１のサイクルｌで処理される
最初の行であり、行４はバースト時間３のサイクル１で
処理される最初の行である。

相補マトリクス７２は要求マトリクス３６と同期してシ
フトされ、基本マトリクスはサイクル１で１バ一スト時
間につき１つしかシフトされたい。

第５図に示すように、セレクタ９０は２つの論理回路を
有する。すなわち、選択論理回路１００と、デコーディ
ング及びゲーティング論理回路１０２である。

選択論理回路１００はブロック８４のＡＮＤゲート８４
−１ないし８４−４で生成されたマスクされた行ビット
パターンＡＭ、ＢＭ％ＣＭ、及びＤＭを出力ｗＡ８８−
１ないし８８−４を介して受取る。

ＡＮＤゲート８４−１ないし８４−４は行レジスタ７６
の４つのステージ７６−１ないし７６−４に記憶された
ビットパターンと、マスクレジスタ８２の４つのステー
ジ８２−１ないし８２−４に記憶されたインバータ８３
−１ないし８３−４で反転されたマスクパターンとを受
取る。

したがってビットパターンＡＭ、ＢＭ％ＣＭ及びＤＭは
マスクされた行パターンである。

基本レジスタ７８及び相補レジスタ８０は４つのステー
ジ７８−１ないし７８−４及び８０−１ないし８０−４
を有する。

ゲートｌＯ４はサイクル１の間に基本レジスタ７８の内
容を自己の出力線１０４−１ないし１０４−４に出して
、サイクル２ないし４の間に相補レジスタ８０の内容を
自己の出力９３１０４−１ないしｌ　０４−４に出す。

線１０４−１ないし１０４−４上のビットパターンはＦ
Ａ％ＦＢ、ＦＣ及びＦＤを記す。

選択論理１００は、１つの行が処理されたときにどのユ
ニット（Ａ、Ｂ、ＣまたはＤ）が起点ユニットとして選
択されたかを示す活動信号を出力線１０６−１ないし１
０６−４のうち１つに出す。

この機能を遂行するため、選択論理１００は１０６−１
ないし１０６−４のうちの適切な線を活動化するＡＮＤ
回路、ＯＲ回路及びインバータ回路で構成される。

線１０６−１の起点Ａ選択信号、線１０６−２の起点Ｂ
選択信号、線１０６−３の起点Ｃ選択信号又は線１０６
−４の起点り選択信号は以下の各論理機能がそれぞれ１
に等しい場合に、供給される。

ここで、記号°゛、、　　　“＋”及び−”はそれぞれ
ＡＮＤ演算子、ＯＲ演算子及び反転演算子を表す。

各サイクル（ｌないし４）の終りで、線１０６−１ない
し１０６−４の信号はバス９９を介してマスクレジスタ
８２のステージ８２−１ないし８２−４に供給される。

マスクレジスタ８２の内容はサイクル５でリセットされ
る。

さらに、線１０６−１ないし１０６−４の信号はサイク
ルｌで基本マトリクス及び相補マトリクスを、サイクル
２ないし４で相補マトリクスを更新するのに使用される
。この機能を遂行するため、線１０６−１ないし１０６
−４の信号は場合に応じて基本マトリクス又は相補マト
リクスに供給すべき適切な時間にゲート１０８によって
ゲートされ、る。

線１０６−１ないし１０６−４の信号はデコーディング
及びゲーティング回路１０２に供給される。この回路１
０２は、さらに、要求マトリクス３６の現に処理されて
いる行のアドレスをアドレスバス７５から受取る。

論理回路１０２によって選択されたユニットのアドレス
がバス９６及び９８を介して次宛先ユニットアドレスレ
ジスタＮＴｔＪＡ５２及び次起点ユニットアドレスレジ
スタＮ０ＵＡ５４に、書込まれる。

第６図はデコーディング論理回路１１０、第７図はゲー
ティング論理回路１１２を表す。

現に処理されている行のアドレスはバス７５からデコー
ダ１１６に供給され、デコーダ１１６はどの行アドレス
がデコードされているかに応じて自己の出力綿１１８−
１ないし１１８−４のうちの１つを活動化する。線１１
８−１は行１のアドレスがデコードされた場合に活動化
される（以下、同様）。

マトリクス１１４の最初の行におけるＡＮＤゲート１１
４−１１ないし１１４−１４は線１１８−１上の活動信
号によって制御され、マトリクス１１４の第２行におけ
るＡＮＤゲート１１４−２１ないり、１１４−２４は＃
、１１８−２上の活動信号によって制御され、マトリク
ス１１４の第３行におけるＡＮＤゲート１１４−３１な
いし１１４−３４は線１８−３上の活動信号によって制
御され、マトリクス１１４の第４行におけるＡＮＤゲー
ト１１４−４１ないし１１４−４４は線１８−４上の活
゛動信号によって制御される。

線１０６−１の起点Ｃ選択信号はＡＮＤゲートマトリク
スの第１列における４つのＡＮＤゲート１１４−１１．
１１・４−２１．１１４−３１及び１１４−４１に供給
され、線１０６−２の起点Ｂ選択信号はＡＮＤゲートマ
トリクスの第２列における４つのＡＮＤゲート１１４−
１２，１１４−３２、及び１１４−４２に供給サレ、）
Ｊｉ　ｌ　Ｏ６−３の起点Ｃ選択信号はＡＮＤゲートマ
トリクスの第３列における４つのＡＮＤゲート１１４−
１３．１１４−２３．１１４−３３及び１１４−４３に
供給され、線１０６−４の起点り選択信号はＡＮＤゲー
トマトリクスの第４列における４つのＡＮＤゲート１１
４−１４．１１４−２４．１１４−３４及び１１４−４
４に供給される。

こうして、各サイクルで、活動信号が選択に可能性がな
い場合を除き、ＡＮＤゲート１１４−ｉｊの出力に供給
される。この活動信号はユニットのどのペアを選択すべ
きかを示す。

たとえば、ＡＮＤゲー）１１４−２３の出力に供給され
た活動信号は選択された起点ユニット及び宛先ユニット
がそれぞれユニットＣ及びユニットＢであることを示す
。

第１行におけるＡＮＤゲート１１４−１１ないし１１４
−１４の出力はＯＲゲート１２６に接続され、第２行に
おけるＡＮＤゲート１１４−２１ないし１１４−２４の
出力はＯＲゲート１２７に接続され、第３行におけるＡ
ＮＤゲート１１４−３１ないし１１４−３４の出力はＯ
Ｒゲート１２８に接続され、ＡＮＤゲート１１４−４１
ないし１１４−４４の出力はＯＲゲート１２９に接続さ
れる。

こうして、ゲーティング信号ＳＩないしＳ４が線１２１
ないし１２４に出され、ゲーティング信号ＧｌないしＧ
４がＯＲゲート１２６ないし１２９の出力線１３１ない
し１３４に出される。これらの信号は第７図に示すゲー
ティング論理回路１１２に供給される。

ゲーティング論理回路１１２は選択されたユニットのア
ドレスをＮ０ＵＡ５４及びＮ０ＵＡ５４にゲートする。

ユニットＡ、Ｂ、Ｃ及びＤのアドレスはレジスタ１４０
，１４１，１４２及び１４３にそれぞれ記憶される。こ
れらは以下の第４表に示すようなユニットの選択された
ペアに基づいてレジスタ５２及び５４の適切な位置にゲ
ートされる。

レジスタ１４０ないし１４３に記憶されたユニットアド
レスの１つがＡＮＤゲート１４８．１５０．１５２及び
１５４ならびにＯＲゲート１５６を介して線１３１．１
３２．１３３又は１３４の活動信号Ｇ１、Ｇ２、Ｇ３又
はＧ４の制御の下でバス１４６にゲートされる。バス１
４６はＡＮＤゲート１５８．１６０．１６２及び１６４
の入力に接続され、したがって、ユニットＡ、Ｂ％Ｃ又
はＤのアドレスが線１２１．１２２．１２３又は１２４
の活動信号の制御の下でレジスタ５２の選択された１つ
の位置５２−１ないし５２−４にゲートされる。

レジスタ１４０ないし１４４に記憶されたユニットアド
レスの１つがＡＮＤゲート１７２．１７４．１７６及び
１７８ならびにＯＲゲート１８０を介して線１２１．１
２２．１２３又は１２４の活動信号Ｓ１、Ｓ２、Ｓ３又
はＳ４の制御の下でバス１７０にゲートされる。

バス１７０はＡＮＤゲート１８２．１８４．１８６及び
１８８の人力に接続されるので、ユニットＡ、Ｂ、Ｃ又
はＤのアドレスは線１３１．１３２．１３３又は１３４
の活動信号Ｇ１、Ｇ２、Ｇ３又はＧ４の制御の下でレジ
スタ５４の選択された１つの位置５４−１ないし５４−
４にゲートされる。

前述の如く、本発明の好適な実施例では、要求マトリク
ス４６、マスクレジスタ８２及び記録マトリクス７０．
７２によって所与の時間内に各ユニットに対して均等な
選択の機会を与える選択アルゴリズムを走行させるプロ
セッサが使用されている。しかしながら、当業者には容
易に理解されるように、このプロセッサは、各バースト
時間の間にユニットの最大数の異なるペアが決定される
ことを保証するだけの簡単なアルゴリズムを走行させる
ようなものに変更することもできる。この場合、記録マ
トリクスは不要である。

Ｅ６発明の詳細 な説明したように本発明によれば、複数のデータ処理ユ
ニットの間で最適な数の同時的なデータ転送が可能とな
る。

【図面の簡単な説明】

第１図は本発明に基づくシステムの実施例を示す図、第
２図はデータ処理ユニットを示す図、第３図は第１図に
おける交換論理回路を示す図、第４図は交換論理回路の
スケジューラにおける選択アルゴリズムプロセッサを示
す図、第５図は選択アルゴリズムプロセッサにおけるセ
レクタ９０を示す図、第６図は第５図におけるデコーデ
ィング及びゲーテインク論理のデコーディング論理回路
を示す図、第７図は第５図におけるデコーディング及び
ゲーティング論理のゲーティング論理回路を示す図であ
る。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　頓　　宮　　孝　　−ＩｂＬ　１
　々Ａ １１１２図 −Ｎ 第４ｇ

Claims (4)

【特許請求の範囲】
1. （１）Ｎ個のデータ処理ユニット（以下、単にユニット
   ともいう）の中から選択された起点ユニット及び宛先ユ
   ニットから成る複数のユニットのペアの間でのデータパ
   ケットの転送を行うため、各データ処理ユニットはアウ
   トバンド待ち行列のセットを有し該アウトバウンド待ち
   行列はそれぞれ当該データ処理ユニットのデータパケッ
   トの送り先である１つのデータ処理ユニットに関連しか
   つ該関連するデータ処理ユニツトへ送るべきデータパケ
   ットを記憶するようなデータ転送システムであつて、 （ａ）固定された期間であるバースト時間Ｔ＿ｉを定め
   るためのタイミング信号を供給するクロック手段と、 （ｂ）Ｎ個のデータ処理ユニットから受け取られ転送要
   求に基づいて条件的にユニットの異なる複数のペアを選
   択するため各バースト時間の間に活動する中央選択手段
   と、 （ｃ）上記中央選択手段に設けられ、選択された各ペア
   の宛先ユニットのアドレスを該ペアの起点ユニットに送
   るための送信手段と、 （ｄ）１つの受信データバス及び１つの送信データバス
   を介してＮ個のデータ処理ユニットのそれぞれに接続さ
   れ、選択された起点ユニットから受取られた選択された
   宛先ユニットのアドレスに応答して、バースト時間Ｔ＿
   ｉの間に選択された各ペアの宛先ユニットと起点ユニツ
   トとの間の接続を次のバースト時間Ｔ＿ｉ＿＋＿ｋ（Ｋ
   は１以上の整数）の間に行う、データ交換手段と、を有
   することにより、選択された複数の起点ユニットから宛
   先ユニツトへのデータパケットの転送を同時に行うよう
   にしたことを特徴とするデータ転送システム。
2. （２）バースト時間Ｔ＿ｉが少なくともＮ個のサイクル
   を含み、上記中央選択手段が１ないしＮの各サイクルで
   条件的にユニットの１つのペアを選択するため各バース
   ト時間Ｔ＿ｉの最初のＮサイクルの間活動化され、 （ａ）第１に、Ｎ個のデータ処理ユニットから受取られ
   た転送要求に基づいて、所定のバースト時間の所与サイ
   クルで起点ユニット及び宛先ユニットとして選択された
   ユニットを、同じ所定のバースト時間の他のサイクルで
   は起点ユニット及び宛先ユニットとしては選択しないで
   、 （ｂ）第２に、最初のサイクル（以下、サイクル（イ）
   という）の間、前のバースト時間Ｔ＿ｉ＿−＿Ｎの最初
   のサイクル（以下、サイクル（ロ）という）の間に選択
   されたユニットのペアに基づいて、他のペアが選択でき
   る場合はサイクル（ロ）で選択されたユニットのペアを
   サイクル（イ）では選択しないで、 （ｃ）第３に、２番目ないしＮ番目サイクルの間、直前
   のバースト時間の３番目ないしＮ番目及び最初のサイク
   ルで選択されたユニットの複数のペアに基づいて、それ
   ぞれ他のペアが選択できる場合は直前のバースト時間の
   ３番目ないしＮ番目及び最初のサイクルの間に選択され
   たユニツニトのペアを現バースト時間Ｔ＿ｉの２番目な
   いしＮ番目のサイクルではそれぞれ選択しない、 ことを特徴とする請求項１記載のデータ転送システム。
3. （３）上記中央選択手段が下記の（ａ）ないし（ｄ）の
   手段を有することを特徴とする請求項２記載のデータ処
   理システム。 （ａ）アウトバウンド待ち行列についての空又は空でな
   いという状況の変更を表わす情報の形式でＮ個のデータ
   処理ユニットから転送要求を受取りかつＮ個の記憶位置
   のＮ個のセット（行１ないし行Ｎ）を有する第１の記憶
   手段（各記憶位置はそれぞれ１つのデータ処理ユニット
   に割当てられ、Ｎ個のデータ処理ユニットにおける所与
   の１つのデータ処理ユニットに関連するアウトバンド待
   ち行列についての空または空でないという状況を表わす
   情報は記憶位置の１つのセットに記憶される）。 （ｂ）バースト時間の各サイルで選択されたユニットの
   ペアのアドレスを記憶するための第２の記憶手段。 （ｃ）バースト時間Ｔ＿ｉ＿−＿４のサイクル１で選択
   されたペアのアドレスと直前のバースト時間Ｔ＿ｉのサ
   イクル３ないしＮ及びサイクル１で選択されたペアのア
   ドレスとを取得するよう、上記クロック手段からのタイ
   ミング信号に応答して、現バースト時間Ｔ＿ｉのうちの
   連続的なサイクル記憶位置の１つのセットを連続的にア
   ドレスし次に上記第２の記憶手段をアドレスするための
   アドレス指定手段。 （ｄ）上記アドレス指定手段によつてアドレスされたと
   きに上記第１及び第２の記憶手段から読み取られた情報
   に応答して、現バースト時間Ｔ＿ｉのうちの１ないしＮ
   の各サイクルの間に条件的に選択できるペアの起点ユニ
   ット及び宛先ユニットのアドレスを判断し該アドレスを
   上記送信手段に供給するための選択処理手段。
4. （４）上記第１の記憶手段がＮ個の記憶位置のＮ個のセ
   ットで構成されるＮ個の行を有するＮ行Ｎ列のマトリク
   スを含むことによつて、１ないしＮの各サイクルで該マ
   トリクスの１つの行が上記アドレス指定手段でアドレス
   されかつ該アドレスされた行の内容が読取られて上記選
   択処理手段に供給される（行のアドレスは上記選択処理
   手段によつて条件的に選択される起点ユニットとペアに
   なる宛先ユニットを表わしている）ことを特徴とする請
   求項３記載のダータ転送システム。