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

Description

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

バス10−１ないし10−Ｎは、さらに、データ送信線XMIT
18−１ないし18−Ｎ及びデータ受信線RCV20−１ないし2
0−Ｎをそれぞれ有する。これらの線はデータ処理ユニ
ツト８−１ないし８−Ｎとデータ交換手段６との間のデ
ータバイトの並列的な伝達のためにそれぞれ用いられる
ものである。その他、スケジユーラ４はデータ転送オペ
レーシヨンの時間調整を行うため、クロツクバス11を介
してクロツク信号をデータ処理ユニツト８及びデータ交
換手段６に送り、データ処理ユニツト８からクロツク信
号を受け取る。

本発明に従つて、データ処理ユニツト間で転送すべき情
報ストリームは固定長のバーストに切り刻まれる。これ
らのバーストは１バースト時間で同期的に交換される。
すなわち、これらのバーストの場合、伝送は同じときに
開始され終了する。

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

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

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

バースト時間Ti_-kの間に線14−１ないし14−Ｎを介して
受け取られた制御出力信号に応答して、データ処理ユニ
ツト８−１ないし８−Ｎは線16−１ないし16−Ｎに交換
制御信号を出力する。これらの信号がデータ交換手段６
に供給されることにより、次のバースト時間Tiの間にデ
ータの転送を遂行すべく、スケジユーラ４で選択された
ユニツトの複数のペアに従ってデータ送信線18−１ない
し18−Ｎ及びデータ受信線20−１ないし20−Ｎが接続さ
れる。

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

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

ｋの値は本発明の実施の態様により異なる。好適な実施
例では、制御出力信号及び交換制御信号は、線の数を減
らすため、直列的に送信される。この場合、ｋの値とし
て２が選択される。

説明をわかり易くするため、本システムが４つのデータ
処理ユニツト８−１ないし８−Ｍ（Ａ、Ｂ、Ｃ、Ｄと呼
ぶ）を有するものとして本発明のシステムを記載する。
もちろん、本発明はこのようなユニツトの数に限定され
るものでないことは当業者には理解されるであろう。

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

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

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

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

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

好適な実施例では、ユニツトＡ、Ｂ、Ｃ及びＤにつきそ
れぞれインバウンド待ち行列QIa、QIb、QIc及びQIdが存
在する。これらはバス10−１の線20−１を介して待ち行
列セレクタ32の制御の下でユニツトＡ、Ｂ、Ｃ及びＤか
らの受信データをエンキユーするために用いられるもの
である。これらのインバウンド待ち行列から読み取られ
たデータは待ち行列マネジヤ24の制御の下でデータ処理
手段22に送られる。

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

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

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

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

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

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

スケジユーラ４は各データ処理ユニツトのアウトバウン
ド待ち行列の状況に関する標識を記憶するために用いら
れる要求マトリクス36を有する。好適な実施例では、こ
のマトリクスは４行×４列で構成される。エレメントTi
j（行ｉ及び列ｊ）はユニツトｊにおけるユニツトｉへ
のアウトバウント待ち行列の状況を表す。たとえば、エ
レメントT₂₃における“1"はユニツトＣにおけるアウト
バウンド待ち行列QObが空でないことを示している。こ
れは、ユニツトＣがユニツトＢへの転送要求を有するこ
とを意味する。

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

第１表の例では、ユニットＡがＣに送信すべきデータを
有し、ユニットＢがＡに送信すべきデータを有し、ユニ
ットＣがＢ及びＤに送信すべきデータを有し、ユニット
ＤがＡ及びＣに送信すべきデータを有することを意味す
る。

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

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

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

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

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

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

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

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

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

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

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

選択記録マトリクス50は２つのマトリクスを含む。１つ
は基本マトリクス（70）と呼ばれ、もう１つは相補マト
リクス（72）と呼ばれる。これらのマトリクスは４つの
行を有する。すなわち、要求マトリクス36の行１ないし
４に対応する行１ないし４である。

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

要求マトリクス36から読取られたビツトパターンは行読
取りレジスタ76に記憶される。サイクル１で、基本マト
リクス70から読取られた情報が基本レジスタ78に記憶さ
れ、サイクル２ないし４で、相補マトリクス72から読取
られた情報が相補レジスタ80に記憶される。

マスクレジスタ82は４ビツトを有すマスクパターンPmを
記憶する（データ処理ユニツトの数を４つと仮定し
た）。マスクパターンPmはインバータ83を介して24個の
ANDゲートで構成されるブロツク84に供給される。レジ
スタ76の内容はバス86を介してブロツク84に供給され、
こうしてブロツク84はレジスタ76に記憶されたビツトパ
ターンをマスクレジスタ82の内容によつて修正したバス
88に出力する。

選択アルゴリズムプロセツサ46はセレクタ90を含む。セ
レクタ90はブロツク84の出力バス88と、基本レジスタ78
の出力バス92と、相補レジスタ80の出力バス94とに接続
される。選択アルゴリズムプセツサ46は、さらに制御情
報すなわちサイクル１ないし４を設定するバス48からの
クロツク信号と、アドレスカウンタ74によつてバス75を
介して供給される行アドレス情報とを受取る。

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

セレクタ90はレジスタ52及び54の４つの位置に書込むべ
きNTUA及びNOUAの情報を出力バス96及び98を介してそれ
ぞれ供給する。

セレクタ90はさらにマスクレジスタ82及びマトリクス7
0、72の内容を更新するために使用すべき更新情報をバ
ス99を介して供給する。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相補マトリクス72は要求マトリクス36と同期してシフト
され、基本マトリクスはサイクル１で１バースト時間に
つき１つしかシフトされない。

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

選択論理回路100はブロツク84のANDゲート84−１ないし
84−４で生成されたマスクされた行ビツトパターンAM、
BM、CM、及びDMを出力線88−１ないし88−４を介して受
取る。

ANDゲート84−１ないし84−４は行レジスタ76の４つの
ステージ76−１ないし76−４に記憶されたビツトパター
ンと、マスクレジスタ82の４つのステージ82−１ないし
82−４に記憶されたインバータ83−１ないし83−４で反
転されたマスクパターンとを受取る。

したがつてビツトパターンAM、BM、CM及びDMはマスクさ
れた行パターンである。

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

ゲート104はサイクル１の間に基本レジスタ78の内容を
自己の出力線104−１ないし104−４に出して、サイクル
２ないし４の間に相補レジスタ80の内容を自己の出力線
104−１ないし104−４に出す。

線104−１ないし104−４上のビツトパターンはFA、FB、
FC及びFDを記す。

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

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

線106−１の起点Ａ選択信号、線106−２の起点Ｂ選択信
号、線106−３の起点Ｃ選択信号又は線106−４の起点Ｄ
選択信号は以下の各論理関数がそれぞれ１に等しい場合
に、供給され 起点Ａ選択信号が出力される場合 AM.（▲▼．▲▼．▲▼．▲▼＋FB.▲
▼．▲▼＋FC.▲▼＋FD＋▲▼．▲
▼．▲▼．▲▼） 起点Ｂ選択信号が出力される場合 BM.（FA＋FB.▲▼．▲▼．▲▼＋FC.▲
▼．▲▼＋▲▼（FD＋▲▼．▲▼．
▲▼．▲▼）） 起点Ｃ選択信号が出力される場合 CM.（FA.▲▼．▲▼＋FB＋FC.▲▼．▲
▼．▲▼＋▲▼．▲▼．（FD＋▲
▼．▲▼．▲▼．▲▼）） 起点Ｄ選択信号が出力される場合 DM.（FA.▲▼．▲▼．▲▼＋FB.▲▼
＋FC＋▲▼．▲▼．▲▼．（FD＋▲
▼．▲▼．▲▼．▲▼）） る。

ここで、記号 はそれぞれAND演算子、OR演算子及び反転演算子を表
す。

各サイクル（１ないし４）の終りで、線106−１ないし1
06−４の信号はバス99を介してマスクレジスタ82のステ
ージ82−１ないし82−４に供給される。マスクレジスタ
82の内容はサイクル５でリセツトされる。

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

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

論理回路102によつて選択されたユニツトのアドレスが
バス96及び98を介して次宛先ユニツトアドレスレジスタ
NTUA52及び次起点ユニツトアドレスレジスタNOUA54に書
込まれる。

第６図はデコーデイング論理回路110、第７図はゲーテ
イング論理回路112を表す。

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

マトリクス114の最初の行におけるANDゲート114−11な
いし114−14は線118−１上の活動信号によつて制御さ
れ、マトリクス114の第２行におけるANDゲート114−21
ないし114−24は線18−２上の活動信号によつて制御さ
れ、マトリクス114の第３行におけるANDゲート114−31
ないし114−34は線18−３上の活動信号によつて制御さ
れ、マトリクス114の第４行におけるANDゲート114−41
ないし114−44は線18−４上の活動信号によつて制御さ
れる。

線106−１の起点Ａ選択信号はANDゲートマトリクスの第
１列における４つのANDゲート114−11、114−21、114−
31及び114−41に供給され、線106−２の起点Ｂ選択信号
はANDゲートマトリクスの第２列における４つのANDゲー
ト114−12、114−32、及び114−42に供給され、線106−
３の起点Ｃ選択信号はANDゲートマトリクスの第３列に
おける４つのANDゲート114−13、114−23、114−33及び
114−43に供給され、線106−４の起点Ｄ選択信号はAND
ゲートマトリクスの第４列における４つのANDゲート114
−14、114−24、114−34及び114−44に供給される。

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

たとえば、ANDゲート114−23の出力に供給された活動信
号は選択された起点ユニツト及び宛先ユニツトがそれぞ
れユニツトＣ及びユニツトＢであることを示す。

第１行におけるANDゲート114−11ないし114−14の出力
はORゲート126に接続され、第２行におけるANDゲート11
4−21ないし114−24の出力はORゲート127に接続され、
第３行におけるANDゲート114−31ないし114−34の出力
はORゲート128に接続され、ANDゲート114−41ないし114
−44の出力はORゲート129に接続される。

こうして、ゲーテイング信号SIないしS4が線121ないし1
24に出され、ゲーテイング信号G1ないしG4がORゲート12
6ないし129の出力線131ないし134に出される。これらの
信号は第７図に示すゲーテイング論理回路112に供給さ
れる。

ゲーテイング論理回路112は選択されたユニツトのアド
レスをNTUA52及びNOUA54にゲートする。

ユニツトＡ、Ｂ、Ｃ及びＤのアドレスはレジスタ140、1
41、142及び143にそれぞれ記憶される。これらは以下の
第４表に示すようなユニツトの選択されたペアに基づい
てレジスタ52及び54の適切な位置ゲートされる。

レジスタ140ないし143に記憶されたユニツトアドレスの
１つがANDゲート148、150、152及び154ならびにORゲー
ト156を介して線131、132、133又は134の活動信号G1、G
2、G3又はG4の制御の下でバス146にゲートされる。バス
146はANDゲート158、160、162及び164の入力に接続さ
れ、したがつて、ユニツトＡ、Ｂ、Ｃ又はＤのアドレス
が線121、122、123又は124の活動信号の制御の下でレジ
スタ52の選択された１つの位置52−１ないし52−４にゲ
ートされる。

レジスタ140ないし144に記憶されたユニツトアドレスの
１つがANDゲート172、174、176及び178ならびにORゲー
ト180を介して線121、122、123又は124の活動信号S1、S
2、S3又はS4の制御の下でバス170にゲートされる。

バス170はANDゲート182、184、186及び188の入力に接続
されるので、ユニツトＡ、Ｂ、Ｃ又はＤのアドレスは線
131、132、133又は134の活動信号G1、G2、G3又はG4の制
御の下でレジスタ54の選択された１つの位置54−１ない
し54−４にゲートされる。

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

E.発明の効果 以上説明したように本発明によれば、複数のデータ処理
ユニツトの間で最適な数の同時的なデータ転送が可能と
なる。

【図面の簡単な説明】

第１図は本発明に基づくシステムの実施例を示す図、第
２図はデータ処理ユニツトを示す図、第３図は第１図に
おける交換論理回路を示す図、第４図は交換論理回路の
スケジユーラにおける選択アルゴリズムプロセツサを示
す図、第５図は選択アルゴリズムプロセツサにおけるセ
レクタ90を示す図、第６図は第５図におけるデコーデイ
ング及びゲーテイング論理のデコーデイング論理回路を
示す図、第７図は第５図におけるデコーデイング及びゲ
ーテイング論理のゲーテイング論理回路を示す図であ
る。

フロントページの続き (72)発明者 アンドレ・トラコル フランス国06270ヴアルヌーヴ・ルベ、ア ヴエニユ・デ・リヴ・ドウール ル・ソレ イユ・ルヴアン（番地なし)

Claims (4)

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