JPH0766363B2 - 調停システム - Google Patents
調停システムInfo
- Publication number
- JPH0766363B2 JPH0766363B2 JP63289036A JP28903688A JPH0766363B2 JP H0766363 B2 JPH0766363 B2 JP H0766363B2 JP 63289036 A JP63289036 A JP 63289036A JP 28903688 A JP28903688 A JP 28903688A JP H0766363 B2 JPH0766363 B2 JP H0766363B2
- Authority
- JP
- Japan
- Prior art keywords
- output
- input
- voltage level
- register
- gate
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
- G06F13/14—Handling requests for interconnection or transfer
- G06F13/16—Handling requests for interconnection or transfer for access to memory bus
- G06F13/1605—Handling requests for interconnection or transfer for access to memory bus based on arbitration
- G06F13/1652—Handling requests for interconnection or transfer for access to memory bus based on arbitration in a multiprocessor architecture
- G06F13/1657—Access to multiple memories
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
- G06F13/14—Handling requests for interconnection or transfer
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Multi Processors (AREA)
Description
【発明の詳細な説明】 A.産業上の利用分野 本発明は多重データ処理システム、より具体的に言え
ば、複数の入力装置から複数の出力装置へなされたアク
セス要求を処理する際に、それらの要求の処理を調停す
るための調停システムに関する。
ば、複数の入力装置から複数の出力装置へなされたアク
セス要求を処理する際に、それらの要求の処理を調停す
るための調停システムに関する。
B.従来の技術 大規模な複合コンピユータシステムにおいて、複数個の
基本メモリ、即ち基本ストレージ・モジユール（basic
storage module−BSM）を持たせて、バツフア機能によ
つて、複数個のプロセツサを複数個の基本メモリと通信
させることの出来る多重プロセツサ・システムを構成す
ることが望まれている。
基本メモリ、即ち基本ストレージ・モジユール（basic
storage module−BSM）を持たせて、バツフア機能によ
つて、複数個のプロセツサを複数個の基本メモリと通信
させることの出来る多重プロセツサ・システムを構成す
ることが望まれている。
米国特許第4473880号、または同第4499538号は共通バス
を持つ幾つかのプロセツサ、または幾つかのマイクロプ
ロセツサに対してある種の調停システムを与えることを
開示している。与えられた時間サイクル内でのバスを介
するデータ転送において、１つのユニットからのバスに
入力された情報だけが、そのバスを介して１つの出力ユ
ニツトにしか供給することが出来ないという意味からい
つて、共通バスを有するこれらの調停システムは、相対
的に低速度のシステムである。米国特許第4417245号に
開示されたスイツチング・マトリツクスのようなクロス
・ポイント・スイツチは、複数の入力を複数の出力に接
続する動作を行うけれども、与えられた入力が、同じ出
力において他の与えられた入力と混同を生じないよう
に、ある種の別個の制御装置が与えられている。しか
し、これには、調停システムは含まれていない。
を持つ幾つかのプロセツサ、または幾つかのマイクロプ
ロセツサに対してある種の調停システムを与えることを
開示している。与えられた時間サイクル内でのバスを介
するデータ転送において、１つのユニットからのバスに
入力された情報だけが、そのバスを介して１つの出力ユ
ニツトにしか供給することが出来ないという意味からい
つて、共通バスを有するこれらの調停システムは、相対
的に低速度のシステムである。米国特許第4417245号に
開示されたスイツチング・マトリツクスのようなクロス
・ポイント・スイツチは、複数の入力を複数の出力に接
続する動作を行うけれども、与えられた入力が、同じ出
力において他の与えられた入力と混同を生じないよう
に、ある種の別個の制御装置が与えられている。しか
し、これには、調停システムは含まれていない。
C.発明が解決しようとする問題点 本発明の目的は、複数の入力装置から複数の出力装置へ
なされたアクセス要求を処理する際に、それらの要求の
処理を調停するための調停システムを提供することにあ
る。
なされたアクセス要求を処理する際に、それらの要求の
処理を調停するための調停システムを提供することにあ
る。
D.問題点を解決するための手段 本発明に従つた調停装置と、出力を制御するゲート手段
とによつて、データ信号と、関連する出力要求コード信
号とを含む複数個の入力信号が、複数個の出力装置の１
つに選択的に与えられる。それらの調停装置及びゲート
手段は、競合（contention）が生じない時は、入力信号
を所定の出力装置に同時に接続し、競合が生じた時は、
関連する出力装置に対して競合するすべての競合信号を
順序付ける機能を含んでいる。
とによつて、データ信号と、関連する出力要求コード信
号とを含む複数個の入力信号が、複数個の出力装置の１
つに選択的に与えられる。それらの調停装置及びゲート
手段は、競合（contention）が生じない時は、入力信号
を所定の出力装置に同時に接続し、競合が生じた時は、
関連する出力装置に対して競合するすべての競合信号を
順序付ける機能を含んでいる。
E.実施例 第１図のシステム・ブロツク図を参照すると、本発明に
従つて、Ｎ個の入力ユニツト×Ｍ個の出力ユニツトの間
の通信アクセス要求を調停するための非ブロツキング方
式の高帯域幅スイツチ（non−blocking high bandwidth
switch）を含む調停システムの実施例が示されてい
る。第１図に示した調停システムは、４つの基本ストレ
ージ・モジユール（BSM）21乃至24のうちの１つに選択
的に接続されるプロセツサ11乃至14を含んでいる。実際
のシステムにおいては、BSMに接続されるプロセツサの
数は32台またはそれ以上の数である。プロセツサ11乃至
14からの出力信号が、夫々のバツフア31乃至34の入力信
号として与えられる。これらのバツフア31乃至34はFIFO
（First In First Out）バツフアであることが望まし
い。各プロセツサ11乃至14からのバスへの入力信号は、
接続（通信）要求コード及び関連データ信号、即ちデー
タ・パケツトを含んでいる。接続要求コード信号は、単
に、４本の接続線のうちの１本だけが論理値１の電圧レ
ベルにすることで表わされる。各バツフア31乃至34から
の出力要求コード信号は、夫々４つの調停装置41乃至44
に与えられる。要求コード信号及び関連したデータ信
号、即ちデータ・パケツトは、共に、バツフア31乃至34
を通つて、順序付けられる。接続（通信）要求コード信
号は、４本の接続線の内の１本だけが論理値１の電圧レ
ベルであり、他の３本が論理値０の電圧レベルであるよ
うな、４本の接続線の組合せで与えられ、論理値１の電
圧レベルは５ボルトであり、論理値０の電圧レベルは接
地電位であつてよい。若し、例えば、プロセツサ11がBS
M21との接続を望んだとすれば、プロセツサ11は、バツ
フア31から調停装置41の第１の要求入力ポートに接続さ
れている接続線101上に論理値１の電圧レベルの信号を
与え、同時にバツフア31から調停装置42乃至44の第１の
要求ポートに接続されている接続線102乃至104上に論理
値０の電圧レベルを与える。同様に、若し、プロセツサ
11がBSM22か、BSM23か、あるいはBSM24の何れかに接続
されることを望んだとすれば、論理値１の電圧レベル
が、調停装置の入力ポートへの接続線102か、103かある
いは104の何れかに与えられる。同様に、若しプロセツ
サ14がBSM21か、BSM22か、BSM23か、あるいはBSM24の何
れか１つと接続されることを要求したとすれば、論理値
１の電圧レベルが、接続線141か、142か、143か、ある
いは144のうちの何れか１つに与えられる。同様に、プ
ロテツサ12及び13等は、夫々調停装置41乃至44へ、要求
を入力する調停装置の入力ポートに対して、相当する論
理値１の電圧レベルを与えることによつて、BSM21乃至2
4のうちの１つに接続することが出来る。
従つて、Ｎ個の入力ユニツト×Ｍ個の出力ユニツトの間
の通信アクセス要求を調停するための非ブロツキング方
式の高帯域幅スイツチ（non−blocking high bandwidth
switch）を含む調停システムの実施例が示されてい
る。第１図に示した調停システムは、４つの基本ストレ
ージ・モジユール（BSM）21乃至24のうちの１つに選択
的に接続されるプロセツサ11乃至14を含んでいる。実際
のシステムにおいては、BSMに接続されるプロセツサの
数は32台またはそれ以上の数である。プロセツサ11乃至
14からの出力信号が、夫々のバツフア31乃至34の入力信
号として与えられる。これらのバツフア31乃至34はFIFO
（First In First Out）バツフアであることが望まし
い。各プロセツサ11乃至14からのバスへの入力信号は、
接続（通信）要求コード及び関連データ信号、即ちデー
タ・パケツトを含んでいる。接続要求コード信号は、単
に、４本の接続線のうちの１本だけが論理値１の電圧レ
ベルにすることで表わされる。各バツフア31乃至34から
の出力要求コード信号は、夫々４つの調停装置41乃至44
に与えられる。要求コード信号及び関連したデータ信
号、即ちデータ・パケツトは、共に、バツフア31乃至34
を通つて、順序付けられる。接続（通信）要求コード信
号は、４本の接続線の内の１本だけが論理値１の電圧レ
ベルであり、他の３本が論理値０の電圧レベルであるよ
うな、４本の接続線の組合せで与えられ、論理値１の電
圧レベルは５ボルトであり、論理値０の電圧レベルは接
地電位であつてよい。若し、例えば、プロセツサ11がBS
M21との接続を望んだとすれば、プロセツサ11は、バツ
フア31から調停装置41の第１の要求入力ポートに接続さ
れている接続線101上に論理値１の電圧レベルの信号を
与え、同時にバツフア31から調停装置42乃至44の第１の
要求ポートに接続されている接続線102乃至104上に論理
値０の電圧レベルを与える。同様に、若し、プロセツサ
11がBSM22か、BSM23か、あるいはBSM24の何れかに接続
されることを望んだとすれば、論理値１の電圧レベル
が、調停装置の入力ポートへの接続線102か、103かある
いは104の何れかに与えられる。同様に、若しプロセツ
サ14がBSM21か、BSM22か、BSM23か、あるいはBSM24の何
れか１つと接続されることを要求したとすれば、論理値
１の電圧レベルが、接続線141か、142か、143か、ある
いは144のうちの何れか１つに与えられる。同様に、プ
ロテツサ12及び13等は、夫々調停装置41乃至44へ、要求
を入力する調停装置の入力ポートに対して、相当する論
理値１の電圧レベルを与えることによつて、BSM21乃至2
4のうちの１つに接続することが出来る。
各調停装置は、先ず、４つのFIFOバツフア31乃至34の何
れかに入力があるか否かを決定する。苦し、その調停装
置に対して１つ以上の入力信号があれば、各クロツク・
サイクルごとに、関連するセレクタ51乃至54を通して、
データ入力を順序付ける。データは４つのセレクタ51乃
至54のすべてに送られる。若し、２以上のプロセツサに
よる競合（contention）がなければ、換言すれば、２以
上のプロセツサが、調停装置に関連した１つのBSMを使
用しようとしているのでなければ、各バツフア31乃至34
から送られた各セレクタ51乃至54への入力は、関連する
バツフア61乃至64を介して、関連するBSM21乃至24に同
時に接続される。セレクタ51乃至54は各BSM21乃至24に
関連付けられている。調停装置41乃至44は、与えられた
プロセツサからの入力データを、どのBSM21乃至24へ出
力するかを識別し、そして、バツフア31乃至34からのデ
ータをバツフア61乃至64のうちの所定の１つのバツフア
ゲートするための選択コードを、セレクタ51乃至54に与
える。
れかに入力があるか否かを決定する。苦し、その調停装
置に対して１つ以上の入力信号があれば、各クロツク・
サイクルごとに、関連するセレクタ51乃至54を通して、
データ入力を順序付ける。データは４つのセレクタ51乃
至54のすべてに送られる。若し、２以上のプロセツサに
よる競合（contention）がなければ、換言すれば、２以
上のプロセツサが、調停装置に関連した１つのBSMを使
用しようとしているのでなければ、各バツフア31乃至34
から送られた各セレクタ51乃至54への入力は、関連する
バツフア61乃至64を介して、関連するBSM21乃至24に同
時に接続される。セレクタ51乃至54は各BSM21乃至24に
関連付けられている。調停装置41乃至44は、与えられた
プロセツサからの入力データを、どのBSM21乃至24へ出
力するかを識別し、そして、バツフア31乃至34からのデ
ータをバツフア61乃至64のうちの所定の１つのバツフア
ゲートするための選択コードを、セレクタ51乃至54に与
える。
若し、所定のBSMに対して、２以上のプロセツサによる
競合が発生していれば、所定のBSMに関連した調停装置4
1乃至44の１つが、関連するセレクタ51乃至54の１つに
おける選択順序を決定する。若し、プロセツサ11がバツ
フア31を介してSM21に対して接続を要求する接続要求コ
ード信号と、プロセツサ12がバツフア32を介してBSM21
に対して接続を要求する接続要求コード信号とが同時に
生じたとすれば、それらの要求コード信号は両方とも調
停装置41に与えられる。然しながら、調停装置41は、例
えばFIFOバツフア31からの出力を、セレクタ51を介して
バツフア61にゲートし、更にBSM21へゲートするため
に、第１のクロツク・パルスの期間中に、第１の選択コ
ードをセレクタ51に与え、これにより、プロセツサ11の
データをBSM21に接続する。それから、次のクロツク・
サイクルの期間において、調停装置41は、第２の選択コ
ード信号をセレクタ51に与え、これにより、FIFOバツフ
ア32に記憶されているプロセツサ12のデータを、セレク
タ51を介してBSM21に接続する。
競合が発生していれば、所定のBSMに関連した調停装置4
1乃至44の１つが、関連するセレクタ51乃至54の１つに
おける選択順序を決定する。若し、プロセツサ11がバツ
フア31を介してSM21に対して接続を要求する接続要求コ
ード信号と、プロセツサ12がバツフア32を介してBSM21
に対して接続を要求する接続要求コード信号とが同時に
生じたとすれば、それらの要求コード信号は両方とも調
停装置41に与えられる。然しながら、調停装置41は、例
えばFIFOバツフア31からの出力を、セレクタ51を介して
バツフア61にゲートし、更にBSM21へゲートするため
に、第１のクロツク・パルスの期間中に、第１の選択コ
ードをセレクタ51に与え、これにより、プロセツサ11の
データをBSM21に接続する。それから、次のクロツク・
サイクルの期間において、調停装置41は、第２の選択コ
ード信号をセレクタ51に与え、これにより、FIFOバツフ
ア32に記憶されているプロセツサ12のデータを、セレク
タ51を介してBSM21に接続する。
第２図において、第１図の各調停装置の論理的ブロツク
図が示されている。第２図のブロツク図には、各調停装
置41乃至44に対する４個の要求入力ポート201乃至204が
示されている。第１の入力ポート201はバツフア31を通
つてプロセツサ11に接続されている。第２の入力ポート
202はバツフア32を通つてプロセツサ12に接続され、第
３の入力ポート203はバツフア33を通つてプロセツサ13
に接続され、そして第４の入力ポート204はバツフア34
を通つてプロセツサ14に接続されている。入力ポート20
1乃至204に入力される接続要求信号は夫々のアンド・ゲ
ートA1乃至A4に与えられる。アンド・ゲートA1乃至A4か
らの出力は、フリツプ・フロツプ・レジスタS1乃至S4の
夫々の入力に与えられる。レジスタS1からのＱ出力は出
力線205と、ノア（否定和）ゲート100とに与えられる。
また、レジスタS2乃至S4からのＱ出力は、ノア・ゲート
100に印加される。スイツチング・レジスタS1の出力
はアンド・ゲートA5に印加される。また、レジスタS2か
らのＱ出力はアンド・ゲートA5に印加される。レジスタ
S3及びS4のＱ出力は夫々のアンド・ゲートA6及びA7の入
力に接続される。また、アンド・ゲートA6はレジスタS1
及びS2からの出力を受け取る。アンド・ゲートA7はレ
ジスタS1、S2及びS3からの出力と、レジスタS4からＱ
出力とを受取る。レジスタS1からのＱ出力はレジスタS1
の他方の入力に印加される。アンド・ゲートA5の出力は
レジスタS2の他方の入力に印加される。アンド・ゲート
A6の出力はレジスタS3の他方の入力に接続され、そして
アンド・ゲートA7の出力はレジスタS4の他方の入力に接
続されている。接続線206乃至208上のアンド・ゲートA5
乃至A7の出力と、接続線205上のレジスタS1のＱ出力と
は、出力を選択するために、対応するセレクタ51乃至54
に印加される４ビツト・アドレス・コードを与える。こ
のようにして、４つのプロセツサと４つのBSMを有する
第１図の簡単な多重プロセツサ・システムの実施例にお
いて、論理値１の電圧レベルを有する調停装置の出力線
205乃至208の１つが、所定のプロセツサのデータを所望
のBSMと接続するのを可能とする。例えば、若し、レジ
スタS1からの出力が論理値１の電圧レベルにあるとすれ
ば、プロセツサ11の出力は、その調停装置に関連したBS
Mに接続される。若し、調停装置41のレジスタS1からの
出力が論理値１のレベルにあれば、プロセツサ11のデー
タはBSM21に接続される。若し、調停装置42のレジスタS
1からの出力が論理値１にあれば、プロセツサ11のデー
タはBSM22に接続され、若し、調停装置43のレジスタS1
が論理値１の電圧レベルにあれば、プロセツサ11のデー
タはBSM23に接続され、若し、調停装置44のレジスタS1
が論理値１の電圧レベルにあれば、プロセツサ11のデー
タはBSM24に接続される。若し、調停装置41において、
調停装置41の出力208が論理値１の電圧レベルにあれ
ば、プロセツサ14からのデータはBSM21に接続される。
若し、調停装置42の出力線208が論理値１の電圧レベル
にあれば、プロセツサ14からのデータがBSM22に接続さ
れる。若し、調停装置43の出力線208が論理値１の電圧
レベルにあれば、プロセツサ14からのデータがBSM23に
接続される等々になり、以下同様である。
図が示されている。第２図のブロツク図には、各調停装
置41乃至44に対する４個の要求入力ポート201乃至204が
示されている。第１の入力ポート201はバツフア31を通
つてプロセツサ11に接続されている。第２の入力ポート
202はバツフア32を通つてプロセツサ12に接続され、第
３の入力ポート203はバツフア33を通つてプロセツサ13
に接続され、そして第４の入力ポート204はバツフア34
を通つてプロセツサ14に接続されている。入力ポート20
1乃至204に入力される接続要求信号は夫々のアンド・ゲ
ートA1乃至A4に与えられる。アンド・ゲートA1乃至A4か
らの出力は、フリツプ・フロツプ・レジスタS1乃至S4の
夫々の入力に与えられる。レジスタS1からのＱ出力は出
力線205と、ノア（否定和）ゲート100とに与えられる。
また、レジスタS2乃至S4からのＱ出力は、ノア・ゲート
100に印加される。スイツチング・レジスタS1の出力
はアンド・ゲートA5に印加される。また、レジスタS2か
らのＱ出力はアンド・ゲートA5に印加される。レジスタ
S3及びS4のＱ出力は夫々のアンド・ゲートA6及びA7の入
力に接続される。また、アンド・ゲートA6はレジスタS1
及びS2からの出力を受け取る。アンド・ゲートA7はレ
ジスタS1、S2及びS3からの出力と、レジスタS4からＱ
出力とを受取る。レジスタS1からのＱ出力はレジスタS1
の他方の入力に印加される。アンド・ゲートA5の出力は
レジスタS2の他方の入力に印加される。アンド・ゲート
A6の出力はレジスタS3の他方の入力に接続され、そして
アンド・ゲートA7の出力はレジスタS4の他方の入力に接
続されている。接続線206乃至208上のアンド・ゲートA5
乃至A7の出力と、接続線205上のレジスタS1のＱ出力と
は、出力を選択するために、対応するセレクタ51乃至54
に印加される４ビツト・アドレス・コードを与える。こ
のようにして、４つのプロセツサと４つのBSMを有する
第１図の簡単な多重プロセツサ・システムの実施例にお
いて、論理値１の電圧レベルを有する調停装置の出力線
205乃至208の１つが、所定のプロセツサのデータを所望
のBSMと接続するのを可能とする。例えば、若し、レジ
スタS1からの出力が論理値１の電圧レベルにあるとすれ
ば、プロセツサ11の出力は、その調停装置に関連したBS
Mに接続される。若し、調停装置41のレジスタS1からの
出力が論理値１のレベルにあれば、プロセツサ11のデー
タはBSM21に接続される。若し、調停装置42のレジスタS
1からの出力が論理値１にあれば、プロセツサ11のデー
タはBSM22に接続され、若し、調停装置43のレジスタS1
が論理値１の電圧レベルにあれば、プロセツサ11のデー
タはBSM23に接続され、若し、調停装置44のレジスタS1
が論理値１の電圧レベルにあれば、プロセツサ11のデー
タはBSM24に接続される。若し、調停装置41において、
調停装置41の出力208が論理値１の電圧レベルにあれ
ば、プロセツサ14からのデータはBSM21に接続される。
若し、調停装置42の出力線208が論理値１の電圧レベル
にあれば、プロセツサ14からのデータがBSM22に接続さ
れる。若し、調停装置43の出力線208が論理値１の電圧
レベルにあれば、プロセツサ14からのデータがBSM23に
接続される等々になり、以下同様である。
調停装置の始動状態において、レジスタS1乃至S4のＱ出
力はすべて論理値０の電圧レベルにあり、かつ出力は
すべて論理値１の電圧レベルにある。ノア・ゲート100
は、すべての入力が０であるので、アンド・ゲートA1乃
至A4に論理値１の電圧レベルを与える。若し、例えば、
入力ポート202にのみ要求信号がある、即ち入力ポート2
02だけが論理値１の電圧レベルにあるとすると、これ
は、アンド・ゲートA2を付勢して、スイツチ・レジスタ
S2のセツト入力端子に論理値１の電圧レベルを与え、こ
れにより、レジスタS2のＱ出力に論理値１の電圧レベル
を与える。レジスタS2からの論理値１の電圧レベルはノ
ア・ゲート100に入力され、この論理値１の電圧レベル
に応答して、ノア・ゲート100からの論理値「低」の電
圧レベル、即ち論理値０の電圧レベルがアンド・ゲート
A1乃至A4に与えられて、これは、その後のすべての要求
を停止する。レジスタS2の出力の論理値１の電圧レベル
を入力として受けたアンド・ゲートA5は、レジスタS1の
出力からの論理値１の電圧レベルを受け取つて、その
出力線、即ち接続線206に論理値１の電圧レベルを与え
る。接続線206だけに論理値１の電圧レベルを持つこの
接続要求コードは、その調停装置に関連したセレクタ51
乃至54に対して、第２のプロセツサ12からのデータを、
そのセレクタに関連したBSMに接続することを要求す
る。例えば調停装置41の場合、プロセツサ12からのデー
タがBSM21に接続される。
力はすべて論理値０の電圧レベルにあり、かつ出力は
すべて論理値１の電圧レベルにある。ノア・ゲート100
は、すべての入力が０であるので、アンド・ゲートA1乃
至A4に論理値１の電圧レベルを与える。若し、例えば、
入力ポート202にのみ要求信号がある、即ち入力ポート2
02だけが論理値１の電圧レベルにあるとすると、これ
は、アンド・ゲートA2を付勢して、スイツチ・レジスタ
S2のセツト入力端子に論理値１の電圧レベルを与え、こ
れにより、レジスタS2のＱ出力に論理値１の電圧レベル
を与える。レジスタS2からの論理値１の電圧レベルはノ
ア・ゲート100に入力され、この論理値１の電圧レベル
に応答して、ノア・ゲート100からの論理値「低」の電
圧レベル、即ち論理値０の電圧レベルがアンド・ゲート
A1乃至A4に与えられて、これは、その後のすべての要求
を停止する。レジスタS2の出力の論理値１の電圧レベル
を入力として受けたアンド・ゲートA5は、レジスタS1の
出力からの論理値１の電圧レベルを受け取つて、その
出力線、即ち接続線206に論理値１の電圧レベルを与え
る。接続線206だけに論理値１の電圧レベルを持つこの
接続要求コードは、その調停装置に関連したセレクタ51
乃至54に対して、第２のプロセツサ12からのデータを、
そのセレクタに関連したBSMに接続することを要求す
る。例えば調停装置41の場合、プロセツサ12からのデー
タがBSM21に接続される。
与えられた１つのBSMに対して２以上の接続要求がある
時、競合が生じる。例えば、BSM21に対して、プロセツ
サ11及び13から入力接続線201及び203を介して接続要求
があつたものと仮定する。アンド・ゲートA1及びA3の入
力端子に論理値１の電圧レベルが入力すると、ノア・ゲ
ート100から論理値１が発生され、そしてレジスタS1及
びS3のセツト入力に論理値１の電圧レベルが設定される
のを、調停装置41が検出する。この状態は、レジスタS1
及びS3のＱ出力に論理値１の電圧レベルを発生する。ノ
ア・ゲート100の何れかの「Ｑ」出力端子に論理値１の
電圧レベルが出力されると、アンド・ゲートA1乃至A4
に、論理値「０」を発生させ、それ以上の要求を停止す
る。論理値０、即ち論理値「低」の電圧レベルがレジス
タS1及びS3のからアンド・ゲートA5乃至A7に与えられ
る。レジスタS1からの出力が論理値「低」のレベルに
あるので、アンド・ゲートA6の出力は論理値０の電圧レ
ベルにとどまる。その結果、BSM21に対する入力ポート2
01の接続要求だけが第１のクロツク・サイクルで認知さ
れる。プロセツサ11からのデータの接続が選択されるや
否や、レジスタS1は接続線209上の信号によつてリセツ
トされ、これによつてレジスタS1の出力に論理値１の
電圧レベルを与え、入力ポート203の接続要求信号をゲ
ートさせて、アンド・ゲートA6から論理値１の電圧レベ
ルを与える。アンド・ゲートA6の出力線207のこの論理
値１の電圧レベルは、次のサイクルにおいて、プロセツ
サ13からのデータを、関連するBSMに選択する。入力ポ
ート203の要求信号がデータを選択した後、レジスタS3
はアンド・ゲートA6からのフイードバツク路210の信号
によつてリセツトされ、そしてノア・ゲート100からの
ノア出力は論理値「高」のレベルになる。ノア出力が論
理値「高」のレベルになつた時、レジスタS1乃至S4のす
べてはオフになり、そして、入力する要求のあらゆる組
合せは、次のサイクルで認知することが出来る。
時、競合が生じる。例えば、BSM21に対して、プロセツ
サ11及び13から入力接続線201及び203を介して接続要求
があつたものと仮定する。アンド・ゲートA1及びA3の入
力端子に論理値１の電圧レベルが入力すると、ノア・ゲ
ート100から論理値１が発生され、そしてレジスタS1及
びS3のセツト入力に論理値１の電圧レベルが設定される
のを、調停装置41が検出する。この状態は、レジスタS1
及びS3のＱ出力に論理値１の電圧レベルを発生する。ノ
ア・ゲート100の何れかの「Ｑ」出力端子に論理値１の
電圧レベルが出力されると、アンド・ゲートA1乃至A4
に、論理値「０」を発生させ、それ以上の要求を停止す
る。論理値０、即ち論理値「低」の電圧レベルがレジス
タS1及びS3のからアンド・ゲートA5乃至A7に与えられ
る。レジスタS1からの出力が論理値「低」のレベルに
あるので、アンド・ゲートA6の出力は論理値０の電圧レ
ベルにとどまる。その結果、BSM21に対する入力ポート2
01の接続要求だけが第１のクロツク・サイクルで認知さ
れる。プロセツサ11からのデータの接続が選択されるや
否や、レジスタS1は接続線209上の信号によつてリセツ
トされ、これによつてレジスタS1の出力に論理値１の
電圧レベルを与え、入力ポート203の接続要求信号をゲ
ートさせて、アンド・ゲートA6から論理値１の電圧レベ
ルを与える。アンド・ゲートA6の出力線207のこの論理
値１の電圧レベルは、次のサイクルにおいて、プロセツ
サ13からのデータを、関連するBSMに選択する。入力ポ
ート203の要求信号がデータを選択した後、レジスタS3
はアンド・ゲートA6からのフイードバツク路210の信号
によつてリセツトされ、そしてノア・ゲート100からの
ノア出力は論理値「高」のレベルになる。ノア出力が論
理値「高」のレベルになつた時、レジスタS1乃至S4のす
べてはオフになり、そして、入力する要求のあらゆる組
合せは、次のサイクルで認知することが出来る。
上述のように、入力ポート201乃至204からの接続要求で
レジスタS1乃至S4が１つでもセットされると、ノア・ゲ
ート100の出力が「低」レベルになり、アンド・ゲートA
1乃至A4をすべて禁止状態にする。アンド・ゲートA1乃
至A4が再び要求を受け付けるようになるのは、レジスタ
S1乃至S4がすべてリセットされてから、すなわち前に出
された要求がすべて許可されてからである。それまで
は、たとえ優先順位の高い要求が後から出されても、ア
ンド・ゲートA1乃至A4のところでブロックされる。これ
により、優先順位の高い要求が連続的に許可されるとい
う事態を避けることができる。
レジスタS1乃至S4が１つでもセットされると、ノア・ゲ
ート100の出力が「低」レベルになり、アンド・ゲートA
1乃至A4をすべて禁止状態にする。アンド・ゲートA1乃
至A4が再び要求を受け付けるようになるのは、レジスタ
S1乃至S4がすべてリセットされてから、すなわち前に出
された要求がすべて許可されてからである。それまで
は、たとえ優先順位の高い要求が後から出されても、ア
ンド・ゲートA1乃至A4のところでブロックされる。これ
により、優先順位の高い要求が連続的に許可されるとい
う事態を避けることができる。
第１図及び第２図に示した実施例においては、所定のBS
Mに対して同時に生じた２つの接続要求を処理するのに
２つのサイクルが必要であつた。ポートの要求は毎サイ
クルごとに発生されるので、入力バツフアのストレージ
の数は、プロセツサの数と同じにすべきである。第１図
において、４つのすべてのプロセツサが、与えられたBS
Mに対して通信（接続）を要求した場合をカバーするた
めに、第１図のシステムは４つのバツフア・ストレージ
を必要とする。それらのバツフア・ストレージは４つの
サイクルにわたつて、記憶され、順序付けられる。図示
された実施例の場合、４個のBSMに接続されるプロセツ
サはたつた４台だけであるけれども、実用上のシステム
においては、例えば32台のプロセツサが32個、またはそ
れ以上のBSMに対して通信を行うことになる。
Mに対して同時に生じた２つの接続要求を処理するのに
２つのサイクルが必要であつた。ポートの要求は毎サイ
クルごとに発生されるので、入力バツフアのストレージ
の数は、プロセツサの数と同じにすべきである。第１図
において、４つのすべてのプロセツサが、与えられたBS
Mに対して通信（接続）を要求した場合をカバーするた
めに、第１図のシステムは４つのバツフア・ストレージ
を必要とする。それらのバツフア・ストレージは４つの
サイクルにわたつて、記憶され、順序付けられる。図示
された実施例の場合、４個のBSMに接続されるプロセツ
サはたつた４台だけであるけれども、実用上のシステム
においては、例えば32台のプロセツサが32個、またはそ
れ以上のBSMに対して通信を行うことになる。
第２図に示した調停装置は、複数の要求のすべての要求
が満足されるまで、常に、S1乃至S4の要求を優先順位に
基づく順序（round robin order）で複数の要求を認識
する。これを言い換えれば、図示の実施例の場合、その
特定の調停サイクル内において、入力ポート201の接続
要求が最も高い優先度に持ち、入力ポート202は次の優
先度を持ち、入力ポート203は第３の優先度を持ち、入
力ポート204は最も低い優先度を持つていることを意味
する。
が満足されるまで、常に、S1乃至S4の要求を優先順位に
基づく順序（round robin order）で複数の要求を認識
する。これを言い換えれば、図示の実施例の場合、その
特定の調停サイクル内において、入力ポート201の接続
要求が最も高い優先度に持ち、入力ポート202は次の優
先度を持ち、入力ポート203は第３の優先度を持ち、入
力ポート204は最も低い優先度を持つていることを意味
する。
１クロツク・サイクルの期間中において、４つの入力ポ
ートへの要求を４つのBSMにわたつて配分することが出
来ること、最大４つのBSMが１サイクル毎にサービスさ
れることが理解された。入力ポートの要求のすべてが同
じBSMに対してなされた場合、最少限、１つのBSMが１サ
イクル毎にサービスされる。例えば32台のプロセツサが
32台のBSMに接続されるような、多くのプロセツサが多
くのBSMを処理する本発明の他の実施例が第３図に示さ
れている。この実施例において、各プロセツサ301乃至3
32は転送されるべき各データ・ブロツク、即ちデータ・
パケツトに対して、５ビツトの符号化された接続要求信
号を与える。その関連されたデータ・パケツトの接続要
求コード信号は、それに関連するバツフアを通して順番
付けされる。デコーダ301a乃至332aは、各入力バツフア
301b乃至332bの出力端子の出力である各５ビツトのプロ
セツサ符号化接続要求信号をデコードし、そして所定の
調停装置へ、32本の出力線のうちの１本を介して論理値
１のレベルを与える。例えばデコーダ301aは、バツフア
301bからの符号化された出力信号をデコードして、BSM3
02fと通信されるべきバツフア301bのデータを表示し、
そして調停装置302cへ接続要求信号、即ち接続線400上
の論理値１の電圧レベルを与える。次に、バツフア301b
のデータは、セレクタ302dを通り、バツフア302eを経て
BSM302fに転送される。調停装置301c乃至332cは第１図
の４つの入力と４つの出力との代りに、32個の入力と32
個の出力を第２図と同じ態様で処理する。
ートへの要求を４つのBSMにわたつて配分することが出
来ること、最大４つのBSMが１サイクル毎にサービスさ
れることが理解された。入力ポートの要求のすべてが同
じBSMに対してなされた場合、最少限、１つのBSMが１サ
イクル毎にサービスされる。例えば32台のプロセツサが
32台のBSMに接続されるような、多くのプロセツサが多
くのBSMを処理する本発明の他の実施例が第３図に示さ
れている。この実施例において、各プロセツサ301乃至3
32は転送されるべき各データ・ブロツク、即ちデータ・
パケツトに対して、５ビツトの符号化された接続要求信
号を与える。その関連されたデータ・パケツトの接続要
求コード信号は、それに関連するバツフアを通して順番
付けされる。デコーダ301a乃至332aは、各入力バツフア
301b乃至332bの出力端子の出力である各５ビツトのプロ
セツサ符号化接続要求信号をデコードし、そして所定の
調停装置へ、32本の出力線のうちの１本を介して論理値
１のレベルを与える。例えばデコーダ301aは、バツフア
301bからの符号化された出力信号をデコードして、BSM3
02fと通信されるべきバツフア301bのデータを表示し、
そして調停装置302cへ接続要求信号、即ち接続線400上
の論理値１の電圧レベルを与える。次に、バツフア301b
のデータは、セレクタ302dを通り、バツフア302eを経て
BSM302fに転送される。調停装置301c乃至332cは第１図
の４つの入力と４つの出力との代りに、32個の入力と32
個の出力を第２図と同じ態様で処理する。
F.発明の効果 上述したように、本発明は複数の入力装置から複数の出
力装置へなされたアクセス要求を処理する際に、それら
の要求の処理を調停するための調停システムを与える。
力装置へなされたアクセス要求を処理する際に、それら
の要求の処理を調停するための調停システムを与える。
第１図は多重データ処理システムにおいて、本発明に従
つた調停システムの実施例を示す図、第２図は本発明の
調停装置の実施例を示す図、第３図は多数のプロセツサ
及び多数の基本メモリを備えた第１図のシステムを拡張
した多重データ処理システムにおいて、本発明に従つた
調停システムの実施例を示す図である。 11乃至14……プロセツサ、21乃至24……基本ストレージ
・モジユール（BSM）、31乃至34及び61乃至64……FIFO
バツフア、41乃至44……調停装置、51乃至54……セレク
タ。
つた調停システムの実施例を示す図、第２図は本発明の
調停装置の実施例を示す図、第３図は多数のプロセツサ
及び多数の基本メモリを備えた第１図のシステムを拡張
した多重データ処理システムにおいて、本発明に従つた
調停システムの実施例を示す図である。 11乃至14……プロセツサ、21乃至24……基本ストレージ
・モジユール（BSM）、31乃至34及び61乃至64……FIFO
バツフア、41乃至44……調停装置、51乃至54……セレク
タ。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジヨン・エドウイン・トーソン アメリカ合衆国ニユーヨーク州ポキプシ イ、ケリイ・サークル（番地なし) (72)発明者 イー‐ミング・テイング アメリカ合衆国ニユーヨーク州ポート・エ ウエン、ロンダート・ハーバー31番地 (56)参考文献 特開 昭58−129563（ＪＰ，Ａ) 特開 昭62−251956（ＪＰ，Ａ)
Claims (1)
- 【請求項１】入力ポートから出力ポートへの要求を調停
するための調停システムであって、 Ｎ個の入力ポートと、 Ｍ個の出力ポートと、 前記出力ポートにそれぞれ対応して設けられたＭ個の調
停装置とを具備し、 前記調停装置のそれぞれは、 前記入力ポートから要求を受け取るゲート手段と、 前記ゲート手段を介して受け取った要求をセットするレ
ジスタ手段と、 前記レジスタ手段にセットされた要求が１つの場合は該
要求を許可し、複数の要求がセットされた場合は所定の
優先順位に従ってそれらの要求を許可する手段と、 前記レジスタ手段に要求が１つでもセットされると前記
ゲート手段への入力を禁止し、前記レジスタ手段にセッ
トされたすべての要求が許可されると前記ゲート手段を
介する要求の受け取りを再び可能にする手段とを含む、 調停システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/152,779 US4991084A (en) | 1988-02-05 | 1988-02-05 | N×M round robin order arbitrating switching matrix system |
| US152779 | 1988-02-05 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01206450A JPH01206450A (ja) | 1989-08-18 |
| JPH0766363B2 true JPH0766363B2 (ja) | 1995-07-19 |
Family
ID=22544410
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63289036A Expired - Lifetime JPH0766363B2 (ja) | 1988-02-05 | 1988-11-17 | 調停システム |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4991084A (ja) |
| EP (1) | EP0327203B1 (ja) |
| JP (1) | JPH0766363B2 (ja) |
| DE (1) | DE68924435T2 (ja) |
Families Citing this family (21)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE68929288T2 (de) * | 1988-12-19 | 2001-11-15 | Nec Corp., Tokio/Tokyo | Datenübertragungsvorrichtung |
| EP0429733B1 (en) * | 1989-11-17 | 1999-04-28 | Texas Instruments Incorporated | Multiprocessor with crossbar between processors and memories |
| KR940001878B1 (ko) * | 1990-03-08 | 1994-03-10 | 가부시끼가이샤 히다찌세이사꾸쇼 | 멀티 프로세서시스템 및 인터럽션 제어장치 |
| US6928500B1 (en) * | 1990-06-29 | 2005-08-09 | Hewlett-Packard Development Company, L.P. | High speed bus system that incorporates uni-directional point-to-point buses |
| US5276808A (en) * | 1991-02-04 | 1994-01-04 | International Business Machines Corporation | Data storage buffer system and method |
| DE69227996T2 (de) * | 1991-07-26 | 1999-08-26 | Tandem Computers Inc. | Vorrichtung und verfahren zur vermittlung von datenblöcken |
| US5371893A (en) * | 1991-12-27 | 1994-12-06 | International Business Machines Corporation | Look-ahead priority arbitration system and method |
| US5274785A (en) * | 1992-01-15 | 1993-12-28 | Alcatel Network Systems, Inc. | Round robin arbiter circuit apparatus |
| US5301332A (en) * | 1992-12-23 | 1994-04-05 | Ncr Corporation | Method and apparatus for a dynamic, timed-loop arbitration |
| US5506968A (en) * | 1992-12-28 | 1996-04-09 | At&T Global Information Solutions Company | Terminating access of an agent to a shared resource when a timer, started after a low latency agent requests access, reaches a predetermined value |
| JPH07105175A (ja) * | 1993-10-08 | 1995-04-21 | Nec Corp | マイクロコンピュータ |
| CA2145553C (en) * | 1994-03-30 | 1999-12-21 | Yuuki Date | Multi-processor system including priority arbitrator for arbitrating request issued from processors |
| JPH0981508A (ja) * | 1995-08-31 | 1997-03-28 | Internatl Business Mach Corp <Ibm> | 通信方法及び装置 |
| US6006296A (en) * | 1997-05-16 | 1999-12-21 | Unisys Corporation | Scalable memory controller |
| US6026459A (en) * | 1998-02-03 | 2000-02-15 | Src Computers, Inc. | System and method for dynamic priority conflict resolution in a multi-processor computer system having shared memory resources |
| US6272580B1 (en) | 1999-03-16 | 2001-08-07 | Compaq Computer Corp. | Apparatus and method for dynamically elevating a lower level bus master to an upper level bus master within a multi-level arbitration system |
| US20030031197A1 (en) * | 2001-08-13 | 2003-02-13 | Schmidt Steven G. | Multiple arbitration circuit |
| US7284082B2 (en) * | 2004-08-19 | 2007-10-16 | Lsi Corporation | Controller apparatus and method for improved data transfer |
| US7353317B2 (en) * | 2004-12-28 | 2008-04-01 | Intel Corporation | Method and apparatus for implementing heterogeneous interconnects |
| US20070124554A1 (en) * | 2005-10-28 | 2007-05-31 | Honeywell International Inc. | Global memory for a rapidio network |
| US11520713B2 (en) * | 2018-08-03 | 2022-12-06 | International Business Machines Corporation | Distributed bus arbiter for one-cycle channel selection using inter-channel ordering constraints in a disaggregated memory system |
Family Cites Families (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3096447A (en) * | 1961-03-21 | 1963-07-02 | Gen Precision Inc | Transistor gate biased by signal being gated |
| US3487373A (en) * | 1965-11-16 | 1969-12-30 | Gen Electric | Apparatus providing symbolic memory addressing in a multicomputer system |
| JPS5917595B2 (ja) * | 1979-11-29 | 1984-04-21 | 岩崎通信機株式会社 | 通話路スイツチ回路網 |
| NL8000529A (nl) * | 1980-01-29 | 1981-08-17 | Philips Nv | Schakelmatrix. |
| US4314335A (en) * | 1980-02-06 | 1982-02-02 | The Perkin-Elmer Corporation | Multilevel priority arbiter |
| US4417245A (en) * | 1981-09-02 | 1983-11-22 | International Business Machines Corp. | Digital space division exchange |
| FR2513407B1 (fr) * | 1981-09-24 | 1987-01-16 | Finger Ulrich | Systeme d'arbitrage des demandes d'acces de plusieurs processeurs a des ressources communes, par l'intermediaire d'un bus commun |
| US4488218A (en) * | 1982-01-07 | 1984-12-11 | At&T Bell Laboratories | Dynamic priority queue occupancy scheme for access to a demand-shared bus |
| US4473880A (en) * | 1982-01-26 | 1984-09-25 | Intel Corporation | Arbitration means for controlling access to a bus shared by a number of modules |
| JPS6054694B2 (ja) * | 1982-01-27 | 1985-12-02 | 株式会社日立製作所 | 記憶制御装置 |
| EP0097351A3 (en) * | 1982-06-21 | 1986-02-26 | Nec Corporation | Router unit and routing network for determining an output port by detecting a part of an input packet |
| JPS59111891A (ja) * | 1982-12-16 | 1984-06-28 | Ricoh Co Ltd | 感熱転写媒体 |
| JPS59161755A (ja) * | 1983-03-07 | 1984-09-12 | Hitachi Ltd | 記憶制御方式 |
| US4706150A (en) * | 1984-06-29 | 1987-11-10 | International Business Machines Corporation | Switching protocal for multiple autonomous switching planes |
| JPH0628051B2 (ja) * | 1986-04-25 | 1994-04-13 | 株式会社日立製作所 | 記憶制御方式 |
| US4807184A (en) * | 1986-08-11 | 1989-02-21 | Ltv Aerospace | Modular multiple processor architecture using distributed cross-point switch |
-
1988
- 1988-02-05 US US07/152,779 patent/US4991084A/en not_active Expired - Fee Related
- 1988-11-17 JP JP63289036A patent/JPH0766363B2/ja not_active Expired - Lifetime
-
1989
- 1989-01-09 DE DE68924435T patent/DE68924435T2/de not_active Expired - Fee Related
- 1989-01-09 EP EP89300139A patent/EP0327203B1/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0327203B1 (en) | 1995-10-04 |
| EP0327203A3 (en) | 1991-05-02 |
| DE68924435T2 (de) | 1996-05-30 |
| DE68924435D1 (de) | 1995-11-09 |
| EP0327203A2 (en) | 1989-08-09 |
| JPH01206450A (ja) | 1989-08-18 |
| US4991084A (en) | 1991-02-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0766363B2 (ja) | 調停システム | |
| US4985830A (en) | Interprocessor bus switching system for simultaneous communication in plural bus parallel processing system | |
| KR900006793B1 (ko) | 패킷 스위치 다중 대기행렬 NxM 스위치 노오드 및 처리 방법 | |
| KR900006791B1 (ko) | 패킷 스위치식 다중포트 메모리 n×m 스위치 노드 및 처리 방법 | |
| US4152764A (en) | Floating-priority storage control for processors in a multi-processor system | |
| US6647449B1 (en) | System, method and circuit for performing round robin arbitration | |
| US5371893A (en) | Look-ahead priority arbitration system and method | |
| US5265223A (en) | Preservation of priority in computer bus arbitration | |
| JP4024875B2 (ja) | 異なるデータ・レートで動作するネットワーク・ポートに関して、共用メモリへのアクセスを調停する方法および装置 | |
| US6070205A (en) | High-speed processor system having bus arbitration mechanism | |
| US6052738A (en) | Method and apparatus in a packet routing switch for controlling access at different data rates to a shared memory | |
| US5729702A (en) | Multi-level round robin arbitration system | |
| US4554628A (en) | System in which multiple devices have a circuit that bids with a fixed priority, stores all losing bids if its bid wins, and doesn't bid again until all stored bids win | |
| US5111424A (en) | Lookahead bus arbitration system with override of conditional access grants by bus cycle extensions for multicycle data transfer | |
| JPH05508497A (ja) | 非順次源アクセスのための方法およびその装置 | |
| JPH05507805A (ja) | 複数の要求のトグリング優先順位を調停するシステム | |
| US4947368A (en) | Lookahead bus arbitration system with override of conditional access grants by bus cycle extensions for multicycle data transfers | |
| US5410300A (en) | Distributed crossbar switch architecture | |
| JPS6360579B2 (ja) | ||
| JPH0359634B2 (ja) | ||
| US5264842A (en) | Generalized usage of switch connections with wait chain | |
| Chi et al. | Decomposed arbiters for large crossbars with multi-queue input buffers | |
| JP3481445B2 (ja) | 競合調停方法 | |
| US5301330A (en) | Contention handling apparatus for generating user busy signal by logically summing wait output of next higher priority user and access requests of higher priority users | |
| JP3323142B2 (ja) | クロスバ装置、多段クロスバ装置及び情報処理装置 |