JPH02242364A

JPH02242364A - マルチプロセッサシステムにおいてシステム制御ユニットを用いて通信要求を仲裁するための方法及び手段

Info

Publication number: JPH02242364A
Application number: JP2024313A
Authority: JP
Inventors: Michael E Flynn; アイケル　イー　フリン; Tryggve Fossum; トリュグヴ　フォッサム
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1989-02-03
Filing date: 1990-02-02
Publication date: 1990-09-26
Also published as: US5155854A; EP0380857A2; DE68927375D1; ATE144631T1; EP0380857A3; DE68927375T2; EP0380857B1; AU628529B2; AU5394690A

Abstract

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

Description

【発明の詳細な説明】産業上の利用分野本発明は、これと同時に出願された次のような米国特許
出願に開示されているコンピュータシステムの幾つかの
特徴を有するものである。エバンス氏等の［デジタルコ
ンピュータのシステム制御ユニットとシステム処理ユニ
ットとの間のインターフェイス（ＡＮ　ＩＮＴＥＲＦＡ
ＣＥ　ＢＥＴＷＥＥＮ　Ａ　ＳＹＳＴＥＭＣＯＮＴＲＯ
Ｌ　ＵＮＩＴ　ＡＮＤ　Ａ　ＳＹＳＴＥＭ　ＰＲＯＣＥ
ＳＳＩＮＧ　ＵＮＩＴＯＦ　Ａ　ＣＩＧＩＴＡＬ、ＣＯ
ＭＰＵＴＥＲ）Ｊ　　；アーノルド氏等の「マイクロプ
ロセッサシステムのシステム制御ユニットと中央処理ユ
ニットとをインターフェイスする方法及び装置（ＭＥＴ
ＨＯＤ　ＡＮＤ　ＡＰＰＡＲＡＴＵＳ　ＦＯＲＩＮＴＥ
ＲＦＡＣｒＮＧ　Ａ　ＳＹＳＴＥＭ　Ｃ０ＮＴＲ０Ｌ　
ＵＮＩＴ　ＦＯＲＡＭＵＬＴＩＰＲＯＣＥＳＳＯＲＳＹ
ＳＴＥＭ　ＷＩＴ）（Ｔ）ＩＥ　ＣＥＮＴＲＡＬＰＲＯ
ＣＥＳＳＩＮＧ　ＵＮＩＴＳ）Ｊ　　；ガグリアード氏
等の［マルチプロセッサシステムのシステム制御ユニッ
トをシステムメインメモリとインターフェイスするため
の方法及び手段（ＭＥＴＨＯＤ　ＡＮＤ　ＭＥＡＮＳ　
ＦＯＲＩＮＴＥＲＦＡＣＩＮＧ　Ａ　ＳＹＳＴＥＭ　Ｃ
０ＮＴＲ０Ｌ　ＵＮＩＴ　ＦＯＲＡＭＵＬＴＩＰＲＯＣ
ＥＳＳＯＲＳＹＳＹＴＥＭ　　ＷＩＴ）ｌ　　ＴＨＥ　
　ＳＹＳＹＴＥＭ　　ＭＡＩＮＭＥＭＯＲＹ）Ｊ　　；
　Ｄ、フィツト氏等の「パイプライン式コンピュータシ
ステムにおいて考えられる種々の数のメモリアクセス競
合を分析する方法と装置（ＭＥＴＨＯＤ　ＡＮＤ　ＡＰ
ＰＡＲＡＴＵＳ　ＦＯＲＲＥＳＯＬＶＩＮＧ　ＡＶＡＲ
ＩＡＢＬＥ　ＮＵＭＢＥＲＯＦ　ＰＯＴＥＮＴＩＡＬ　
ＭＥＭＯＲＹ　ＡＣＣＥＳＳＣＯＮＦＬＩＣＴＳ　ＩＮ
　Ａ　ＰＩＰＥＬＩＮＥＤ　ＣＯＭＰＵＴＥＲＳＹＳＹ
ＴＥＭ）Ｊ　；Ｄ、フィツト氏等の「可変長さの命令ア
ーキテクチャにおいて多数の指定子をデコードする方法
（ＤＥＣＯＤＩＮＧ　ＭＵＬＴＩＰＬＥ　５ＰＥＣＩＦ
ＩＥＲＳ　ＴＮ　Ａ　ＶＡＲＩＡＢＬＥＬＥＮＧＴＨｒ
ＮｓＴＲＵｃＴＩＯＮ　ＡＲＣＩ（ｒＴＥｃＴＵＲＥ）
Ｊ　　；　Ｄ、　’７　イツト氏等の［仮想命令キャッ
シュリフィルアルゴリＸム（ＶＩＲＴＵＡＬ　ｌＮ５Ｔ
ＲＵＣＴＩＯＮ　ＣＡＣＨＥ　ＲＥＦＩＬＬＡＬＧＯＲ
ＩＴＩ−ＩＭ）Ｊ　　；パーマン氏等の「同じ命令内で
のレジスタ及びレジスタ変更指定子のパイプライン処１
１（ＰＩＰＥｌｊＮＥ　ＰＲＯＣＥＳＳＩＮＧ　ＯＦ　
ＲＥＧＩＳＴＥＲＡＮＤＲＥＧ［５ＴＥＲＭＯＤＩＦＹ
ＩＮＧＴ　５ＰＥＣＩＦＩＥＲ５ＷＩＴＨＩＮ　Ｔ）Ｉ
ＥＳＡＭＥ　ｌＮ５ＴＲＵＣＴＩＯＮ））　　：　Ｖ−
レイ氏等のデジタルコンピュータ用のデータ依存性分析
を行なう多命令予備処理システム（ＭＵＬＴＩＰＬＥ　
ｌＮ５ＴＲＵＣＴＩＯＮ　ＰＲＥ−ＰＲＯＣＥＳＳＩＮ
Ｇ　ＳＹＳＴＥＭ　ＷＩＴ）（ＤＡＴＡ　ＤＥＰＥＮＤ
ＥＮＣＹＲＥＳＯＬＵＴＩＯＮ　ＦＯＲＤＩＧＩＴＡＬ
　ＣＰＭＰＵＴＥＲ）Ｊ　　；　Ｄ、フィツト氏等の「
バイブラインプロセッサにおいて暗示された指定子を予
め処理する方法（ＰＲＥ−ＰＲＯＣＥＳＳＩＮＧ　ＩＭ
ＰＬＩＥＤ　５ＰＥＣＩＦＩＥＲ５ＩＮＡ　ＰＩＰＥＬ
ＩＮＥＤＰＲＯＣＥＳＳＥＲ）Ｊ　　；　Ｄ、フィツト
氏等の「ブランチ予想（ｓＲＡＮｃＨＰＲＥＤＩＣＴＩ
ＯＮ）Ｊ　　；フォラサム氏等の［デジタルコンピュー
タのバイブライン式フローティングポイント加算器（Ｐ
ＩＰＥＬＩＮＥＤ　ＦＬＯＡＴＩＮＧＰＯＩＮＴ　ＡＤ
ＤＥＲＦＯＲＤＩＧＩＴＡＬ　ＣＯＭＰＵＴＥＲ）Ｊ　
；グランドマン氏等の［自己計時式レジスタファイル（
ＳＡＬＦ　ＴＩＭＥＤ　ＲＥＧＩＳＴＥＲＦＩＬＥ）Ｊ
　　；ベベン氏等の「パイプライン式コンピュータシス
テムにおいてエラーを検出して修正する方法及び装置（
ＭＥＴＨＯＤＡＮＤ　　ＡＰＰＡＲＡＴＵＳ　　ＦＯＲ
ＤＥＴＥＣＴＩＮＧ　　ＡＮＤ　　ＣｏＲＲＥＣ丁ＩＮ
ＧＥＲＲＯＲＳ　ＩＮ　Ａ　ＰＩＰＥＬＩＮＥＤ　ＣＯ
ＭＰＵＴＥＲＳＹＳＴＥＭ）Ｊ　；フリン氏等の「マル
チプロセッサシステムにおいてシステム制御ユニットを
用いて通信要求を仲裁する方法及び装置（ＭＥＴ）ＩＯ
Ｄ　ＡＮＤ　ＭＥＡＮＳ　ＦＯＲＡＲＢＩＴＲＡ−ＴＩ
ＮＧ　ＣＯＭＭＵＮＩＣＡＴＩＯＮ　ＲＥＱＵＥＳＴＳ
　ＵＳＩＮＧ　Ａ　ＳＹＳＴＥＭＣＯＮＴＲＯＬ　ＵＮ
ＩＴ　ＩＮ　Ａ　ＭＵＬＴＩ−ＰＲＯＣＥＳＳＯＲＳＹ
ＳＴＥＭ）Ｊ　　。

Ｅ、フィツト氏等のｒマイクロコード化実行ユニットに
おいて並列動作で多機能ユニットを制御すル方法（ＣＯ
ＮＴＲＯＬＯＦ　ＭＵＬＴＩＰＬＥ　ＦＵＮＣＴＩＯＮ
　ＵＩＮＴＳＷＩＴＨＰＡＲＡＬＬＥＬ　０ＰＥＲＡＴ
ＩＯＮ　ＩＮ　Ａ　ＭＩＣＲＯＣＯＤＥＤＥＸＥＣＵＲ
ＩＯＮ　ＵＩＮＴ）Ｊ　　；ウェブ二世氏等の［仮想メ
モリシステムをベースとするデジタルコンピュータの命
令パイプライン内において予めフェッチした命令でメモ
リアクセス例外を処理する方法（ＰＲＯＣＥＳＳＩＮＧ
　ＯＦ　ＭＥＭＯＲＹ　ＡＣ：ＣＥＳＳ　ＥＸＣＥＰＴ
ＩＯＮＳ　ＷＩＴＨＰＲＥ−ＦＥＴＣＩ（ＥＤ　ｌＮ５
ＴＲＵＣＴＩＯＮＳ　ＷＩＴＩ（ＩＮ　ＴＨＥ　ｌＮ５
ＴＲＵ（ニーＴｌ０Ｎ　　ＰＩＰＥＬＩＮＥ　　ＯＦ　
　Ａ　　ＶＩＲＴＵＡＬＭＥＭＯＲＹ　　ＳＹＳＴＥＭ
−ＢＡＳＥＤ　ＤＩＧＩＴＡＬ　ＣＯＭＰＵＴＥＲ）Ｊ
　　；ヘザリントン氏等の「デジタルコンピュータシス
テムにおいて仮想−物理メモリアドレスの変換を制御す
る方法及び装置（ＭＥＴＨＯＤ　ＡＮＤ　ＡＰＰＡＲＡ
ＴＵＳ　ＦＯＲＣ０ＮＴＲ０ＬＬＩＮＧｎｌＥ　Ｃ０Ｎ
ＶＥＲ５ＩＯＮ　ＯＦ　ＶＩＲＴＵＡＬ　Ｔｏ　ＰＨＹ
ＳＩＣＡＬ　ＭＥＭＯＲＹＡＤＤＲＥＳＳＥＳ　ＩＮ　
Ａ　ＤＩＧＩＴＡＬ　Ｃ０ＮＰＵＴＥＲＳＹＳＹＴＥＭ
）Ｊ　　；ヘザリントン氏等の「エラー修正機能を有す
るライトハラ／７／＜）　７７（ｗＲＩＴＥＢＡＣＫ　
ＢＵＦＦＥＲＷｒＴＨＥＲＲＯＲＣ０ＲＲＥＣＴＩＮＧ
ＣＡＰＡＢＩＬＩＴＩＥＳ）Ｊ　　、チナスウエイ氏等
の［マルチプロセッサシステムにおいてシステムユニッ
ト間でデータトランザクションを行なうモジュール式ク
ロスバ−相互接続ネットワーク（ＭＯＤＵＬＡＲＣＲＯ
３ＳＢＡＲＩＮＴＥＲＣＯＮＮＥＣＴＩＯＮ　ＮＥＴＷ
ＯＲＫＦＯＲＤＡＴＡ　ＴＲＡＮＳＡＣＴＩＯＮＳ　Ｂ
ＥＴＷＥＥＮ　ＳＹＳＴＥＭ　ＵＮＩＴＳＩＮ　Ａ　Ｍ
ＵＬＴＩ−ＰＲＯＣＥＳＳＯＲＳＹＳＴＥＭ）Ｊ　　；
ポルジン氏等の「入力／出カニニットとマルチプロセッ
サシステムのシステム制置ユニットとをインターフェイ
スする方法及び装置（ＭＥＴＨＯＤ　ＡＮＤ　ＡＰＰＡ
ＲＡＴｔＪＳ　ＦＯＲＩＮＴＥＲＦＡＣＩＮＧ　Ａ　Ｓ
ＹＳＹＴＥＭ　Ｃ０ＮＴＲ０Ｌ　ＵＮＩＴ　ＦＯＲＡＭ
ＵＬＴＩ−ＰＲＯＣＥＳＳＯＲＳＹＳＹＴＥＭ　ＷＩＴ
ＨＩＮＰＵＴｌｏＵＴＰＵＴＵＮＩＴＳ）」；ガグリア
ード氏等の「マルチプロセッサシステムのシステム制御
ユニットとシステムメインメモリとをインターフェイス
する手段に用いるメモリ構成（ＭＥＭＯＲＹ　Ｃ０ＮＦ
ＩＧＵＲＡＴＩＯＮ　ＦＯＲＵＳＥＷＩＴＨＭＥＡＮＳ
　ＦＯＲＩＮＴＥＲＦＡＣＩＮＧ　Ａ　５ＹＳＴＥＮ　
Ｃ０ＮＴＲ０ＬＵＮＩＴ　ＦＯＲＡ　ＭＵＬＴＩ−ＰＲ
ＯＣＥＳＳＯＲＳＹＳＴＥＭ　ＷＩＴＨＴＨＥＳＹＳＴ
ＥＭ　ＭＡＩＮ　ＭＥＭＯＲＹ）Ｊ　　；そしてガグリ
アード氏等の「システムモジュール間のＤＲＡＭ制御信
号のエラーチエツクのための方法及び手段（ＭＥＴ）Ｉ
ＯＤＡＮＤ　ＭＥＡＮＳ　ＦＯＲＥＲＲＯＲＣＨＥＣＫ
ＩＮＧ　ＯＦ　ＤＲＡＭ−ＣＯＮＴＲＯＬＳＩＧＮＡＬ
Ｓ　ＢＥＴＷＥＥＮ　ＳＹＳＴＥＭ　ＭＯＤＵＬＥＳ）
Ｊ。

本発明は、一般に、複数の中央処理ユニット（ＣＰＵ）
及び他のシステムユニットを並列に動作させるためにシ
ステム制御ユニット（ＳＣＵ）が使用されたマルチプロ
セッサのコンピュータシステムに係る。より詳細には、
本発明は、マルチプロセッサシステムのＳＣＵが特にＣ
ＰＵと入力／出カニニットとシステムメモリとの間で種
々のシステムポートからの通信要求を効率的に仲裁でき
るようにする仲裁機構に係る。

従来の技術複数のプロセッサがある定められたタスクにおいて問題
分析を介して動作するようにされたマルチプロセッシン
グの技術や、コンピュータ命令が一連のより小さなそし
て複雑でないオペレーションに分割されそしてこれらの
オペレーションが特定の目的に適するようにされた専用
のファンクションユニットによってパイプライン形態で
次々に実行されるような並列処理が高性能コンピュータ
として通常知られている。このようなコンピュータシス
テムでは、複数のプロセッサユニットと、入力／出カニ
ニットとの間で大量記憶装置及び他の装置への並列経路
と共に設けられた多数の通信経路によって高い実行速度
とオペレーションの冗長度とが実現されている。

マルチプロセッサシステムにおいては、コンピュータシ
ステムのシステムメモリ、入力／出力装置及び他のユニ
ットに関連した複数のＣＰＵの並列動作が典型的にシス
テム制御ユニット（ＳＣＵ）によって調整され、該制御
ユニットは、これにポート接合された全てのシステムユ
ニットをリンクし、そしてデータ及び当該制御信号を効
率的に交換するためのユニット内通信を与える。ＳＣＵ
は、全てのシステム要素をアクティブな状態に保つ一方
、ユニット内競合を回避し、ＳＣＵの種々のポートを介
してリンクされたシステムユニットとシステムメモリと
の間の通信要求を処理するように本質的に機能する。次
々の通信要求がＳＣＵに到達するにつれて、並列動作を
容易にする方向にシステムリソースを最も効率的に使用
するだけでなく、適度な時間内にその要求を処理するこ
とにより各々の要求を発しているポートを公平に処理す
るように種々のポートからの要求を処理することが重要
である。これらの要求、即ちシステムの効率とユニット
の公平さが本来競合を生じることになり、これら２つの
間に最適な兼ね合いを得ることが、効率的な仲裁機構を
実施する上で大きな仕事となる。

従来の仲裁機構は、マルチプロセッサシステムに用いた
ときには、バックアップ通信要求によって制約が生じる
ために、適度な応答時間及びブレークダウンを与える上
で非効率的となる。例えば、全ての要求がＳＣＵに到達
する時間に基づいて処理されるような「ラウントロピン
」機構は、公平な仲裁を確保するが、このような機構は
、システムリソースの使用が非常に非効率的である。

というのは、仲裁待ち行列の最上部にある要求がその後
にある要求を効率的にシャットアウトし、これは、次の
保留中の要求により必要とされるリソースが実際に使用
できることに拘りなく、その前の要求により必要とされ
た全てのリソースが使用できるまで行なわれるからであ
る。

例えば、独自にサイクルを繰り返すことのできる複数の
メモリセグメントより成るメモリにアクセスする場合を
考える。「ラウントロピン」の解決策では、２つの要求
を発しているポートＡとＢ（そのうちの要求Ａは仲裁待
ち行列においてＢに先行する）がＳＣＵにおいて保留中
であり、そして要求Ａがそのときビジーであるメモリセ
グメントにアクセス要求を発し、一方要求Ｂがそのとき
使用できるメモリセグメントの使用を必要とする場合に
、要求Ａによって必要とされるメモリセグメントが自由
であって要求Ａを最初に処理できるときまで要求Ｂは不
必要にも処理されないようにシャットアウトされる。従
って、通信要求当たりの平均応答時間が不当に増加され
、この機構は並列動作を行なわない。

これとは別に、いわゆる［瞬時実行）仲裁機構を使用す
ることも考えられ、この場合は、ＳＣＵに到達する通信
要求が次々にポーリングされ、このポーリングの時点で
使用不能のリソースを必要としている要求が無視され、
一方リソースを使用できるその後に生じる要求が瞬時に
処理される。

このような解決策は所与の時間に使用できるシステムリ
ソースを効率的に使用するが、仲裁シーケンスの一部分
として要求がポーリングされるたびに要求によって必要
とされている全てのリソースが使用不能であると分かっ
た場合に要求を完全にシャットアウトできるという点で
実際的でない。

マルチプロセッサシステムの種々のシステムユニットか
らの通信要求が、使用可能なリソースを最適に使用する
ように仲裁されると同時に、このような全ての要求が適
度な時間内に処理されるよう確保する効率的な仲裁機構
は、入ってくる通信要求を仲裁時に満足するために必要
な全てのリソースを識別し、全ての必要なリソースを使
用できるところの要求を処理し、必要とされる使用不能
なリソースをリザーブした後に必要とされるリソースが
使用できないところの要求をバイバスし、その後の新た
な要求と、それに関連して要求がリザーブされた要求と
を交互にポーリングすることにより仲裁を行なうという
考え方に基づいている。

仲裁システムは、一対のリソースベクトルに関連して動
作する。即ちそれは、ｌ）仲裁時に未解決の要求を伴う
コマンドを実行する必要のある全てのリソースを表わす
リソース要求（ＲＲ）ベクトルと、２）ポーリング時に
使用可能な全てのリソースを表わすリソース使用可能（
ＲＡ）なベクトルとである。仲裁時に必要なリソースを
使用できるところの要求の識別は、２つのリソースベク
トルを比較することにより行なわれる。これらのベクト
ルが合致すると分かった場合、必要な全てのリソースが
使用できることを指示する。リソースベクトルが合致し
ない場合には、必要なリソースの少なくとも幾つかが使
用できず且つその要求がリザーブされないことを指示す
る。リザーブされた要求が仲裁されるときにも同様の合
致が行なわれるが、この場合は、ベクトルが合致しない
ときには、ＲＡベクトルを記憶してリソースが次の要求
に使用不能となるようにすることにより、全ての対応す
る必要なリソースがリザーブ状態に入れられる。

簡単に述べると、本発明の仲裁機構によれば、ＳＣＵ　
（即ち、全てのＳＣＵポート）にポート結合された全て
のユニットが順次にポーリングされ、そしてＳＣＵに到
着する要求の優先順位を決める所定のハイアラーキ優先
順位決め機構に基づいて要求が最初に仲裁される。ポー
リングシーケンスの第１のバスにおいては、処理可能な
全ての要求がそのように行なわれる一方、使用不能なリ
ソースを必要とするリソースがリザーブされた状態に入
れられる。次のバスにおいて、手前のバスからの全ての
リザーブされた要求が再びポーリングされて、それに対
応するリザーブされたリソースがそのとき使用できるが
どうが判断される。必要なリソースがそれから使用可能
になったところのリザーブされた要求が処理される。必
要なリソースがまだ使用不能であるところのリザーブさ
れた要求はリザーブ状態に保持され、更に、それに対応
するリソースはリザーブされたリソースとして記憶され
、その後の要求に対して使用不能となるリザーブされた
リソースの要約を発生する。このバスの間に、手前のポ
ーリング時から保持されそして必要なリソースを保持で
きるところの新たな要求が処理される。然し乍ら、リソ
ースのリザーブは第３バスの部分として行なわれない。

「リザーブされた」要求と、「新たな」要求とのこの交
互の要求は、リザーブされた全ての要求が処理されるま
で、即ちシステムリソースがいずれもリザーブ状態でな
くなるまで、その後のバスにおいて続けられ、そのとき
にはリザーブされた要求の新たな要約が開始される。

以下に詳細に説明するように、上記仲裁機構はノン・ス
トップで動作する。というのは、到達する通信要求は、
特定の要求が不必要に次の要求の仲裁を妨げることなく
連続的に処理されるからである。仲裁バスの一部分とし
てリザーブされた全ての要求が処理された後に次の要求
に対するリソースのリザーブを開始するように確保する
ことにより、仲裁機構は、要求を発しているユニットが
ロックアウトされるのを阻止する。

本発明による好ましい実施例の仲裁機構においては、コ
マンド変換手段を用いて、システムで処理できる全ての
通信コマンドのディレクトリが記憶され、このディレク
トリの各入力は、特定のコマンドを実行するのに必要な
全てのリソースの対応するリストに対してインデックス
される。ＳＣＵにおける全ての入力要求は、優先順位決
め手段内に記憶され、この手段は、入ってくる要求を順
次に受け入れそして全ての記憶された要求の中で所定の
優先順位決め機構に基づいて最も高い優先順位が指定さ
れた単一の要求をその出力に得られるようにする。入っ
て（る通信要求に関連したコ又ンドは、コマンドバッフ
ァ手段に記憶される。

優先順位決め手段によって選択された要求によりインデ
ックスされた乗算器構成体を用いて、その選択された要
求に対応するコマンドがコマンド変換手段に送られ、該
手段は、それに応答して、コマンドの処理に必要な全て
のリソースを表わすリソースベクトルを発生する。

ＳＣＵには、使用可能なリソースのベクトルを発生する
ために仲裁時に使用できるリソースの更新された記録を
維持するための手段が設けられている。このベクトルは
、比較器構成体により、優先順位決め手段で決定された
現在未解決の要求に対応するリソースベクトルと比較さ
れ、仲裁されている要求に関連したコマンドを実行する
に必要な全てのリソースが使用可能であるかどうかを判
断する。２つのリソースベクトルが合致すると分かった
場合には、比較器の出力により選択された要求が処理さ
れる。然し乍ら、リソースベクトルが合致しない場合に
は、比較器構成体は、通信要求を開始した要求発生ユニ
ットに対応するＳＣＵポートがリザーブ状態にあるもの
としてフラグがたてられるようにする。リザーブされた
要求が仲裁されるときには、必要なリソースのベクトル
が使用可能なリソースの現、在ベクトルと再び比較され
る。ベクトルが依然として合致しない場合には、比較器
の出力により必要なリソースのベクトルがリソースリザ
ーブベクトルに記憶され、即ちベクトルが合致しない場
合には、リザーブされた要求が処理され、リザーブされ
た要求のリストから取り外される。この物理的構成の繰
返し動作は上記の仲裁機構に基づいており、以下で詳細
に説明する。

本発明の他の目的及び効果は、添付図面を参照した以下
の詳細な説明がら明らかとなろう。

実施例本発明は、種々の変更及び修正が考えられるが、−例と
して添付図面を参照してその特定の実施例について詳細
に説明する。然し乍ら、本発明は、ここに開示する特定
の形態に限定されるものではなく、特許請求の範囲で規
定した本発明の精神及び範囲内に入る全ての変更や修正
を網羅するものとする。

添付図面の特に第１図は、マルチプロセッサシステムＩ
Ｏの簡単なブロック図であり、該システムは、複数の中
央処理ユニット（ＣＰＵ）１．２を用いており、これら
のシステムＣＰＵがシステムに対して共通のメモリ１６
を共有できるようにすることによりこれらＣＰＵの同時
の即ち並列の動作を行なえるようになっている。メイン
メモリ１６自体は、典型的に、複数のメモリユニット１
６Ａ及び１６Ｂを備えている。システム制御ユニット（
ＳＣＵ）１４は、ＣＰＵ１２をメインメモリ１６にリン
クすると共に、入力／出力（Ｉ／Ｏ）制御器１８にリン
クする。このＩ１０制御器は、一般的にはプロセッサシ
ステムがそしてより詳細にはＣＰＵがシステムの適当な
Ｉ１０インターフェイス２０及び当該Ｉ１０ユニット２
０Ａを経て外界と通信できるようにする。又、５ＣＵ１
４は、種々のシステムモジュールをサービスプロセッサ
／コンソールユニット（ＳＰＵ）２２へリンクし、この
ユニットは、プロセッサシステムの全オペレーションに
ついての状態の決定及び制御を含む通常のコンソール機
能を調整する。第１図のマルチプロセッサシステムでは
、５ＣＵ１４を経てリンクされたシステムユニットとメ
インメモリ１６との間、より詳細には、各システムＣＰ
Ｕ１２と各メモリユニット１６Ａ、１６Ｂを構成する個
々にアドレス可能なセグメントとの間の効率的な通信が
専用のインターフェイス手段３０を経て処理される。メ
インメモリの特定の構成及びＳＣＵをメモリにインター
フェイスする特定の仕方は、本発明にとって重要ではな
く、従って、ここでは詳細に説明しない。好ましいイン
ターフェイス手段の詳細については、本発明の譲受人に
譲渡された参考としてここに取り上げる前記ガグリアド
氏等の１９８９年２月３日に出願された［マルチプロセ
ッサシステムのシステム制御ユニットをシステムメイン
メモリとインターフェイスする方法及び手段」と題する
米国特許出願第３０６，３２６号を参照されたい。本発
明の説明上、メインメモリ１６の各メモリユニット１６
Ａ、１６Ｂは、ＳＣＵの２つのメモリポート間に分割さ
れるのが好ましく、各ポートは２つの個々にアドレス可
能なセグメントにリンクされそして全てのセグメントは
ブロック境界においてインターリーブされることを述べ
れば充分であろう。これについては、前記特許出願に詳
細に開示されている。

ＣＰＵやＩ１０ユニットのような各システムユニットは
別々のポートを通して５ＣＵ１４に結合され、そしてメ
モリとの間の全ての通信要求、より詳細には、メモリと
システムユニットとの間のアクセス要求は、ＳＣＵの対
応するポートに保持される。５ＣＵ１４は、システムユ
ニットをアクティブに保持するように働く一方、システ
ムユニットとシステムメモリとの間でＳＣＵの種々のポ
ートに受け入れられる通信に対する要求を取り扱うこと
によりユニット内競合を回避するように働く。種々のＣ
ＰＵ及びＩ１０ユニットはマルチプロセッサシステム内
で並列に動作されるので、複数の通信要求がルーチン的
にＳＣＵに受け取られる。更に、多数のこのような要求
は、典型的に、同じシステムリソースへのアクセスを要
求し、それに関連したコマンドを実行することにより要
求を処理する。

従って、システムリソースを最も効率的に使用すると共
に、要求を適度な時間内に処理することにより各到達す
るシステム要求を公平に処理する形態でシステムユニッ
トからそのポートで受け取った要求を処理することがＳ
ＣＵの重要な機能である。より詳細には、ＳＣＵがその
ポートで未解決となっているシステムユニットからのど
の要求を仲裁してシステムの効率とユニットの公平さの
２つの要求を満たすかをベースとする技術は、プロセッ
サシステムの全作動効率に影響する重要なファクタの１
つである。上記したように、従来の仲裁機構は、例えば
、「ラウントロピン」解決策に基づいており、即ち「瞬
時実行」の解決策はマルチプロセッサシステムに用いる
には満足なものではない。というのは、それらは通信要
求の仲裁において適度な応答時間との組み合わせでシス
テムリソースの効率的な効率的な使用をもたらすからで
ある。

本発明によれば、第１図に関して上記した形式のマルチ
プロセッサシステムにおいてシステムユニットからの要
求を効率的に仲裁するようにＳＣＵにより使用すること
のできる新規な仲裁機構が提供される。この仲裁機構は
、関連コマンドの実行により入ってくる通信要求を処理
することが必要な全てのシステムリソースを識別し、仲
裁時に全ての必要なリソースを使用できるところの要求
を処理し、仲裁時に全ての必要なリソースを使用できな
いところの要求をリザーブされた状態に入れ、リザーブ
された要求を処理できないときに対応する必要な要求を
リザーブし、そしてリザーブされたリソースに関連した
既にリザーブされた要求と、その後に受け取った新たな
要求とを交互にポーリングして、その必要なリソースを
使用できるか又は使用できるようになった要求を処理す
ることにより仲裁を進めるという考え方に基づくもので
ある。入ってくる要求を処理する必要のある全てのリソ
ースを識別するために、本発明の仲裁システムは、シス
テムで発生された一対のリソースベクトルに関連して次
のものを使用する。

１）選択された要求を付随するコマンドを仲裁時に実行
する必要のある全てのシステムリソースを識別するリソ
ース要求（ＲＲ）ベクトル；及び２）仲裁時に実際に使
用可能な全てのシステムリソースを識別するリソース使
用可能（ＲＡ）ベクトル。

全ての必要なリソースが仲裁時に使用できるところの要
求を識別するために、２つのリソースベクトルＲＲ及び
ＲＡが比較される。これらのリソースベクトルが合致す
ると分かった場合には、全ての必要なリソースが使用可
能であるという明確な指示である。リソースベクトルが
合致しない場合には、対応するコマンドを実行するに必
要なリソースの少なくとも幾つかがそのとき使用できな
いことを指示し、従って、その要求はそのとき処理でき
ないことを指示する。そこで、入ってくる要求は、ベク
トルが合致したときに実行され、ベクトルが合致しない
ときにリザーブ状態に入れられる。リザーブされた要求
を実行するに必要なリソースが使用できないと分かった
場合、即ちリザーブされた要求に対するＲＲベクトルと
ＲＡベクトルとが合致しない場合には、それらがリザー
ブ状態にされ、これらのリソースはリソースを使用でき
るようになるや否やリザーブされた要求を処理するのに
適するようになる。ＲＡベクトルは、リザーブされたリ
ソースをその後の要求に対して使用不能にすることによ
りこれらリソースのリザーブされた状態を反映するよう
に同時に調整される。次の説明は、本発明の仲裁機構に
基づく順次の手順に集約される。仲裁は、対応するシス
テムユニットからの通信要求を保持するのに使用できる
全てのＳＣＵポートを順次にポーリングすることに基づ
いている。入ってくる要求は、ポーリングルーチンの間
に収集され、その後に仲裁するために記憶される。記憶
された要求からの仲裁要求の選択は、簡単なハイアラー
キ機構に直接基づくものであり、これは、好ましい実施
例によれば、ポートにおける要求の到達時間に関連した
「最初に入ってくるものが最初に仲裁される」というベ
ースで所与のポートにおいて多数の要求を優先順位決め
し、更に、所定の優先順位決めハイアラーキに基づいて
所与のポーリングルーチン中に収集された全ての要求を
極性状めする。

本発明の特徴によれば、仲裁シーケンスは３つの別々の
仲裁バスを使用し、各バスは、単一のポーリングルーチ
ン中に収集された全ての要求の選択及び仲裁より成る。

より詳細には、ポーリングシーケンスの第１バス（リザ
ーブバス）中に、関連コマンドに対応する全ての必要な
リソースが仲裁時に使用できるところの要求が処理され
る。

又、リザーブバス中に、必要なリソースの全部ではない
リソースが使用可能であるところの要求が更に仲裁のた
めにリザーブ状態に入れられる。

次の仲裁バス（リザーブバス）においては、手前のリザ
ーブバスにおいてリザーブされた要求のみが、それら要
求がリザーブ状態に入れられたときから対応するリザー
ブリソースを使用できるよう−になったところのリザー
ブされた要求を処理することにより、仲裁される。又、
リチェックバス中に、関連コマンドに対応する必要なリ
ソースが依然として使用できないところのリザーブされ
た要求はリザーブ状態に保持され、更に、対応するＲＲ
ベクトルにより表わされた対応する必要なリソースは、
リザーブされたリソースの要約としてリザーブ状態に入
れられる。

第３の仲裁バス（非リザーブバス）の間には、手前のポ
ーリングルーチン以来ＳＣＵに保持された新たな要求の
みが処理されるが、これは、全ての対応する必要なリソ
ースを使用することのできる要求を処理することによっ
て行なわれる。然し乍ら、リソースのリザーブは第３バ
スの一部分として行なわれない。「リザーブされた」要
求及び「新たな」要求のこの交互のポーリングは、最初
のリザーブバスから生じる全てのリザーブされた要求が
処理されるまで次々のバスにおいて続けられる。この点
において未解決のリザーブされた要求はなく、リザーブ
する必要のある非実行可能な要求の識別及びそれに関連
したリザーブされたリソースの要約の発生は、新たなリ
ザーブバスを実行した後に、再び仲裁の進行に続いてリ
チェックバス及び非リザーブバスを交互に実行すること
により新たに開始される。

本発明の仲裁機構により３つの仲裁バスを実行するのに
含まれる種々の手順ステップのより詳細な説明は、第２
Ａ図、第２Ｂ図及び第２Ｃ図を参照して行なう。特に、
第２Ａ図には、リザーブバスに対する流れ線図５０が示
されている。図示されたように、第１ステツプ５１にお
いて、ＳＣＵのポーリングされたポートからの要求が受
け取られ、それに関連するコマンドと共に記憶される。

説明上、ＳＣＵにポート結合されたユニットの数、ひい
ては、ＳＣＵポートの数がｒＰＪに等しく、全てのポー
トに単一の通信要求が保持されていると仮定すれば、単
一のポーリングルーチン中にＳＣＵによって仲裁するた
めに収集された要求及びコマンドの数も「Ｐ」に等しく
なる。ステップ５２において、記憶された要求は、例え
ば、最も上の優先順位ｒＮＪで始まる選択されたハイア
ラーキ優先順位決め機構に基づいて優先順位決めされる
。

次のステップ５３において、そのとき最も高い優先順位
をもつ要求ＲＥＱＮが次に仲裁されるように選択され、
そして対応する記憶されたコマンドＣＭＮＤが抽出され
る。ステップ５４において、選択されたコマンドに対応
する必要なリソースベクトルＲＲＮが発生される。その
次のステップ５５において、リソース使用可能ベクトル
ＲＡが発生され、その後、ステップ５６において、２つ
のリソースベクトルが比較されて、選択されたコマンド
により要求された全てのリソースがそのとき使用できる
かどうか判断される。ステップ５６の答えが否定である
場合には、その要求ＲＥＱＮがステップ５７においてリ
ザーブ状態に入れられる。

ステップ５６の答えが肯定である場合、即ち仲裁されて
いる要求によって必要とされた全てのリソースが実際に
使用できる場合には、ステップ５８がアクセスされ、仲
裁機構は要求の処理を開始する。ステップ５７及び５８
のいずれかの実行の後にステップ５９へと続き、Ｓ、Ｃ
Ｕポートから収集された全ての要求が仲裁されたかどう
かのチエツクがなされる。ステップ５９の答えが否定で
ある場合には、ステップ６０がアクセスされ、優先順位
決めパラメータＮが増加された後に、リザーブバスシー
ケンスのステップ５３に戻り、そのとき最も優先順位の
高い未解決の要求が仲裁のために選択される。上記した
流れシーケンスは、優先順位決めされた全ての要求が実
際に仲裁されてしまうまで繰り返され、その時点で、ス
テップ５９の答えが肯定となり、ステップ６１がアクセ
スされ、仲裁機構のりチエツクバスが開始される。

第２Ｂ図は、本発明による仲裁機構のりチエツクバスを
実行するのに含まれる手順シーケンスを表わす流れ線図
である。リチェックバス７０はステップ７１で開始され
、最初のリザーブバス中にリザーブされた状態のもとで
記憶された要求を順次に仲裁することを含む。ステップ
７２において、リザーブレジスタが空であるかどうか、
即ち最初のリザーブバスの一部分としてリザーブ状態に
入れられた全ての要求がその後に処理されて、未解決の
リザーブされた要求がそのとき存在しないかどうかを判
断するためのチエツクがなされる。

その答えが肯定であると分かった場合には、ステップ７
３がアクセスされ、リザーブバスへ復帰することによっ
て仲裁が進められる。さもなくば、ステップ７４がアク
セスされ、最も未解決のリザーブされた要求ＲＲＥＱＸ
に対応する必要なコマンドＣＭＤＸが仲裁のために選択
される。説明上、ｒＱＪのリザーブされた要求は仲裁の
必要があり。

サフィックスｒＸＪは、仲裁時に最も未解決なリザーブ
された要求を指す。ステップ７５において、それに対応
する必要なリソースベクトルＲＲＸが発生される。

その後、ステップ７６において、ベクトルＲＲＸがリソ
ース使用可能ベクトルＲＡと比較される。ステップ７７
において、選択された要求を処理するに必要な全てのリ
ソースがそのとき使用できるかどうかについての判断が
なされる。ステップ７７の答えが否定である場合には、
ベクトルＲＲＸに対して表わされる要求ＲＥＱＸに対応
する全ての必要なリソースがステップ７８においてリソ
ースリザーブレジスタに記憶される。その後、ステップ
７９がアクセスされ、ベクトルＲＲＮにより表わされた
リザーブされたリソースを次の要求に対して使用不能に
するようにリソース使用可能ベクトルＲＡが調整される
。

然し乍ら、ステップ７７の答えが肯定であることが分か
った場合には、ステップ８０がアクセスされ、選択され
た要求の処理が開始された後に、ステップ７９において
流れシーケンスに復帰し、リソース使用可能ベクトルＲ
Ａが対応的に調整される。次いで、ステップ８１がアク
セスされ、全ての未解決のリザーブされた要求が仲裁さ
れたかどうかを判断するテストが行なわれる。ステップ
８１のテストが否定の結果９を生じた場合には、リザー
ブ状態を指示するパラメータＸがステップ８２において
増加され、ステップ７２において流れシーケンスに再び
入り、そのとき最も未解決となっているリザーブされた
要求が次に仲裁のために選択される。一方、ステップ８
１のテストが肯定の結果をもたらす場合、即ち全ての未
解決のリザーブされた要求が実際に仲裁された場合には
、流れシーケンスがステップ８３において非リザーブバ
スへと進む。

第２Ｃ図には、本発明の仲裁機構による非リザーブバス
に含まれるシーケンスを定める流れ線図である。非リザ
ーブバス９０はステップ９１において開始され、手前の
リザーブバスに続いて要求発生システムユニットからＳ
ＣＵポートで受け取った全てのコマンド或いはリザーブ
バスで仲裁のために取り上げられたちの以外のポートに
おける未解決の要求が収集され、それに関連したコマン
ドと共に記憶される。解説上、非リザーブバスで仲裁す
る必要のある要求／コマンドの全数を［Ｋ」と仮定する
。次のステップ９２においては、リザーブバスの優先順
位決めステップ５２に用いられたものと同様に記憶され
た要求が優先順位決めされる（第２Ａ図）。

ステップ９３において、最も高い未解決の優先順位決め
レベル（ここでは説明上、ｒＬＪと称する）を有する要
求ＲＥＱＬ及びそれに対応するコマンドＣＭＤＬが仲裁
のために選択される。次のステップ９４において、選択
されたコマンドに対応する必要なリソースベクトルＲＲ
Ｌが発生され、そしてステップ９５において、リソース
使用可能ベクトルＲＡと比較される。ステップ９６にお
いて、選択されたコマンドを実行するに必要な全てのリ
ソースが使用できるがどうかについての判断が成される
。ステップ９６の答えが否定である場合には、ステップ
９７がアクセスされ、優先順位決めされた全ての要求が
仲裁されたがどうかについての判断がなされる。ステッ
プ９７の答えが否定である場合には、優先順位決めパラ
メータＬがステップ９８において増加され、ステップ９
３で流れシーケンスに再び入り、そのとき最も優先順位
の高い要求が仲裁のために次に選択される。

然し乍ら、ステップ９６において全ての必要なリーソー
スが実際に使用できることが分かった場合には、ステッ
プ９９に達し、選択された要求の処理が開始され、その
後ステップ９７において流れシーケンスに再び入り、優
先順位決めされた全ての要求が仲裁されるかどうかの判
断がなされる。

上記事象シーケンスは、ステップ９７において肯定の答
えが発生されて全ての優先順位決めされた要求が実際に
仲裁されることを指示するまで繰り返され、その後、シ
ーケンスはりチエツクバスに復帰し、これはステップ９
９Ａで開始される。

第３図は、第２図の仲裁機構を実施するための好ましい
構成であって第１図に示した形式のマルチプロセッサシ
ステムに用いる構成１００を示す簡単なブロック図であ
る。ＳＣＵポートに入ってくる要求１１２は優先順位決
め手段１１３内に記憶され、一方、その入ってくる要求
に関連した対応するコマンド１１４は受け入れられて最
初に個別のコマンドバッファ１１５に記憶される。記憶
されたコマンドは、その後、バッファ１１５がらマルチ
プレクサ１１７へ転送され、このマルチプレクサは、優
先順位決め手段１１３がら優先順位インデックス信号１
１６を受け入れ、そしてこれに応答して、それに対応す
る記憶されたコマンドを選択されたコマンド１１８とし
て出力する。

本発明の特徴によれば、優先順位決め手段ｌ１３は、多
数の要求が所与のポートに到達するときにＳＣＵポート
における到着時間に関して最も未解決な要求を選択する
ことと、全てのＳＣＵポートから収集されたこのような
未解決の要求から、予め定められたハイアラーキの要求
発生ソースをベースとする単一の要求を選択することと
に基づいてハイアラーキ選択機構に機能する。より詳細
には、優先順位を指定するためのハイアラーキは、通信
要求を発生する特定のシステムユニットにキー固定され
、このような機構においては、メモリから発せられる要
求に最も高い優先順位が与えられるのが好ましく、一方
、Ｉ１０ユニットからの要求には比較的低い優先順位が
与えられ、そして最後に、ＣＰＵから発せられる要求に
は最も低い優先順位が与えられる。

本発明の仲裁技術及びその実施は、ＳＣＵが４つのＣＰ
Ｕ、２つのメモリユニット及び２つのＩｌｏからの通信
要求を仲裁するようにされた本発明の好ましい実施例に
よるＳＣＵＣＰポートを考えることによって最も良く理
解されよう。従って、少なくとも８個のポートがそれに
対応するシステムユニットからの要求及び関連コマンド
を受け入れるためにＳＣＵに設けられる。更に、各ＳＣ
Ｕポートは、対応するシステムユニットからの複数の通
信要求を受け入れてそこに保持するように用いられる。

優先順位が許可された通信要求は、例えば、ＳＣＵを通
る送信路を指定の時間中リザーブさせ、これについては
、参考としてここに取り上げる１９８９年２月３日出願
の［マルチプロセッサシステム内のシステムユニット間
でデータ送信を行なうためのモジュール式クロスバ−相
互接続ネットワーク」と題するチナスウェイ氏等の米国
特許出願筒３０６，３３６号に開示されている。

好ましくは、ＳＯＵは、ＳＣＵ内の各々のＣＰＵポート
において未解決となっている３つまでの要求と、各Ｉ１
０ユニット及びＳＣＵ内の各メモリユニットポートに対
する２つまでの要求とをもつようにされ、これにより、
所与の時間に優先順位決め手段で処理するためにＳＣＵ
ポートに２Ｏまでの要求が未解決となることがある。同
様に、２０までの対応する入力コマンドを記憶する必要
があり、従って、コマンドバッファ１１５にはこれを達
成するための容量が設けられる。

第４図は、２０までの入ってくる要求（ＲＥＱＯ−ＲＥ
ＱＩ　９）をＳＣＵポートで受け入れて、１つの要求を
仲裁のために選択するのに適するようにそれらの優先順
位を決めるための優先順位決め手段１１３の好ましい構
成を示している。この構成体１６０は、８つのＳＣＵポ
ートからの入ってくる要求を受け入れるための一連のラ
ッチ１６１を備えており、これらのポートは、４つのｃ
ＰＵ　１−４　ニ対する４つ（７）Ｃ，ＰＵポート（Ｃ
ＰＵボーｈｏ％ＣＰＵボー）１．ＣＰＵポート２及びＣ
ＰＵポート３）と、２つのＩ１０ユニットに対する２つ
のＩ１０ポート（Ｉ１０ポート０及びＩ１０ポート１）
と、２つのメモリユニットに対する２つのメモリポート
（ＭＥＭポート０及びＭＥＭポートｌ）とを備えている
。より詳細には、各ＳＣＵポートごとに単一のラッチが
設けられていて、当該システムユニットへの及びユニッ
トからの通信要求を受け取れるようになっている。例え
ば、ラッチＯは、ＣＰＵポート０に対応し、これは、Ｃ
ＰＵＩからの及びこれへのＲＥＱＯｌＲＥＱＩ及びＲＥ
Ｑ２を受け入れる。

ＣＰＵポートに記憶することのできる入ってくる要求の
最大数（この場合は、３）は、ラッチＯに順次にラッチ
され、最初にポートに到着する要求は所与の時間に最も
未解決な要求を構成し、ＣＰＵポート０から収集された
特定の要求ＲＥＱ００としてラッチ出力される。この形
式の選択は、ＣＰＵ２．３及び４に各々対応するＳＣＵ
ＣＰポート２及び３に対応する残りの３つのラッチにお
いて続けられる。例えば、ラッチ３は、ＣＰＵポート３
に対応し、ＣＰＵポート３におそらく保持された３つの
要求、即ちＲＥＱ９、ＲＥＱＩＯ及びＲＥＱＩＩを受け
入れて、その受け入れられた要求の最も未解決なものを
更に仲裁のためにＲＥＱＯ３として選択するのに役立つ
。

同様に、ラッチ４．５は、各々、Ｉ１０二ニット０，１
に対しＳＣＵＣＰポート５に対応するように設けられる
。より詳細には、ラッチ４は、Ｉ１０ポート０がらＲＥ
Ｑ１２及びＲＥＱ１３の２つの要求を受け入れて、２つ
のうちの最も未解決なものをＲＥＱＯ４として選択する
。同様に、ラッチ５は、Ｉ１０ポート１がら２つの要求
ＲＥＱ１４及びＲＥＱ１５を受け入れ、２つの要求のう
ちの１つを未解決の要求ＲＥＱＯ５として選択する。

同様に、ラッチ６．７は、システムをサポートする２つ
のメモリユニット０．１に対するｓｃＵポートに対応す
るように各々設けられている。

特に、ラッチ６は、メモリポートｌがら２つの要求ＲＥ
Ｑ１６及びＲＥＱ１７を受け入れ、そこから最も未解決
なｌ要求をＲＥＱＯ６として選択する。ラッチ７はメモ
リポート０がら要求ＲＥＱＩ８及びＲＥＱ１９を受け入
れ、２つの要求のうちの最も未解決なものをＲＥＱＯ７
として選択する。

実際に、８つのＳＣＵポートに対応する８つのラッチ１
６１を用いた構成体は、各ｓｃＵポートにおける最も未
解決な要求を選択し、８つまでの要求を収集するように
働き、各ポートに対する単一の未解決の要求を収集する
ために８つのＳＣＵポートの各々をポーリングするこの
シーケンスは、単一のポーリングルーチンを構成する。

選択された要求ＲＥＱＯＯ−ＲＥＱＯ７は、優先順位選
択ネットワーク１６２へ送られ、このネットワークは、
優先順位レベルの所定のハイアラーキに基づいて特定の
要求をピックアップするための簡単な論理構成体を作る
。

上記したように、優先順位決めハイアラーキは、メモリ
ポートを通して保持された要求に最も高い優先順位を指
定し、Ｉ１０ポートから発せられる要求に比較的低い優
先順位を指定し、そしてＣＰＵポートから発せられる要
求に最も低い優先順位を指定することに基づくのが好ま
しい。より詳細には、２つのメモリポートのうちの１つ
、例えば、メモリポート０には最も高い優先順位が指定
され、ＲＥＱＯ７がアクティブであるときに、最も高い
優先順位が指定されて、それにより、仲裁に選択される
ようになっている。次の優先順位レベルは、メモリポー
トｌがらのＲＥＱＯ６に指定される。同様に、次々に低
い優先順位レベルが、Ｉ１０ポートｏがら（７）ＲＥＱ
Ｏ５、Ｉ１０ポートｌから（７）ＲＥＱＯ４、ＣＰＵポ
ート３がら（７）ＲＥＱＯ３、ＣＰＵポート２がら（７
）ＲＥＱＯ２、ｃｐＵポートｌから（７）ＲＥＱＯＩ及
びＣＰＵポート〇からのＲＥＱＯＯに各々指定される。

特定のアクティブな要求は、優先順位の高いレベルをも
つ全ての要求がインアクティブである場合だけ仲裁のた
めに選択される。例えば、Ｉ１０ポート１に対応するＲ
ＥＱｏ４は、ＲＥＱＯ５、ＲＥＱＯ６及びＲＥＱＯ７（
、：れらは、ＲＥＱＱ４よりも優先順位レベルが高い）
がインアクティブである場合にのみ仲裁のために選択さ
れる。特定の要求がその優先順位レベルに基づいて仲裁
のために選択されると、それに対応する優先順位インデ
ックスが、仲裁のために選択された入ってくる２０個の
要求の特定の１つを表わす信号として発生され、これに
より、選択された要求に関連した対応コメントを仲裁の
ために選択することができる。

優先順位ハイアラーキを定める際には、メモリからのデ
ータが使用できるようになったことが関連メモリコマン
ドによって指示されるや否や、要求されたメモリデータ
をその要求を発しているＣＰＵに転送して戻す構成がな
されていない限り、ＣＰＵのようなシステムユニットか
らの要求に準じるようにメモリにアクセスするだけでは
何の役にも立たないようにすることを確認しなければな
らない。従って、メモリに向けられるその後のＣＰＵ要
求は、要求を発しているシステムユニットへのデータの
転送を必要とするメモリコマンドによって取って代わる
ことが重要である。これは、このメモリコマンドに最も
高い優先順位を指定することによって行なわれる。複数
のメモリユニ・ソトが存在するときには、各ユニットに
種々の優先順位レベルの１つが指定され、その各々は残
りのシステムユニットに指定されるものよりも高くされ
る。例えば、２つの独立してアクセスできるメモリユニ
ットを有する好ましい実施例では、メモリユニット「０
」に最も高い優先順位（即ちｌ）が指定され、一方メモ
リユニットｌには次に高い優先順位（即ち２）が指定さ
れる。

メモリユニットに対する優先順位レベルを越えると、次
に高いレベルがＩ１０ユニットに与えられる。これは、
Ｉ１０ユニットの動作を既に要求していてそのユニット
を動作の実行に加えさせたＣＰＵがその後に同じユニッ
トにより実行されるべき別の動作を要求し、それにより
Ｉ１０ユニットの負担を増して効率的なＩ１０応答を妨
げるときに生じる競合を回避するためである。従って、
Ｉ１０ユニットにより発せられたコマンドは、システム
ＣＰＵから送られるものよりも高い優先順位レベルをも
つものとして指示されることが重要である。好ましい実
施例では、例えば、システムＩ１０ユニットＯ，ｌに各
々レベル３．４の優先順位が指定され、これらは２つの
メモリユニットに対する優先順位レベルのすぐ下に入る
ものである。最後に、システムＣＰＵは最も低いレベル
の優先順位が与えられ、例えば、好ましい実施例では、
４つのＣＰＵｌ−４に各々優先順レベル４０７が与えら
れる。

第３図を参照すれば、優先順位決め手段１１３により発
生された優先順位インデックス１１６はマルチプレクサ
１１７へ送られ、このマルチプレクサに送られた受け取
ったコマンドのうちの特定の１つで、最も高い優先順位
を有する入ってくる要求１１２に対応する１つを選択す
るための選択信号として働く。

選択されたコマンド１１８は、これを実行するに必要な
全てのリソースを表わす必要なリソースベクトル１２０
を発生するためにコマンド変換手段１１９へ送られる。

よ、り詳細には、コマンド変換手段１１９は、一般に全
ての考えられる通信コマンドにそして特にプロセッサシ
ステムにより実行可能であると定められたメモリコマン
ドに相関した所定リストのテーブルを含んでいる。これ
を達成するために、ＳＣＵにより最も一般的に仲裁され
る通信コマンドは、所要リソースの同様の組を実行のた
めに必要とするコマンドのカテゴリに分割されるのが好
ましい。典型的なカテゴリは、メモリ読み取り、メモリ
書き込み、Ｉ１０読み取り及びＩ１０書き込みを含むが
、あまり一般的でないコマンド、例えば、メモリ及び■
／○ユニットへのアクセスを必要としないがシステムマ
イクロコード待ち行列へのアクセスを必要とするような
コマンド、及びメモリやＩ１０ユニットやシステムのマ
イクロコード待ち行列へのアクセスを必要としないコマ
ンドもカテゴリに分けられる。これらのコマンドカテゴ
リのいずれかに入る各コマンドについては、コマンドの
実゛行に重要な特定の組のシステムリソースが識別され
、指定されたコマンドをそれに対応する必要なリソース
に相関するテーブルが発生される。

仲裁機構は、システムリソースの特定の形式又はカテゴ
リに制約されないことが当業者に理解されよう。共通の
コマンドを実行するための典型的なリソースは、システ
ムＣＰＵ及びメモリユニットに対するコマンドバッファ
と、Ｉ１０装置のためのバッファと、ＣＰＵ、メモリ及
びＩ１０ユニットのためのデータ路ソースと、ＣＰＵ、
メモリユニット及びＩ１０ユニットに対するデータ路行
き先とを含む。更に、直接リンクされたクロスバ−モジ
ュールがシステムユニットとメモリセグメントとの間の
データ転送に使用されるときに、マイクロコード待ち行
列へのアクセス性やデータ路交差点といったリソースを
識別することもできる。

３２ビツトベクトルの形態で通常表わすことのできる選
択されたコマンドを実行するのに必要なシステムリソー
スを予め定める好ましい構成が第５図に示されている。

３２ビツトの各々は、これがアサートされたときに、特
定のシステムコマンドを実行するのに必要な特定のシス
テムリソースを表わす。第５図において、例えば、ビッ
ト０．１．２及び３は、ＣＰＵＩ、ＣＰＵ２、ＣＰＵ３
及びＣＰＵ４に対するＣＰＵコマンドバッファを各々表
わし、一方、ビット４．５及び６，７は、２つの別々の
独立してアクセスできる二重セグメントメモリユニット
より成るシステムメモリのメモリユニットの各セグメン
トに対する２つのコマンドバッファを各々表わし、そし
てビット８．９は、入力／出カニニットｌ、２に対する
バッファを各々表わし、等々となる。

仲裁機構が作用するものとして予め選択された各コマン
ドについては、対応するＲＲベクトルが定められ、コマ
ンドを実行するに必要な全てのシステムリソースを３２
ビツトワードの形態で識別する。従って、コマンド変換
器は、本質的に、仲裁コマンドのディレクトリをそれに
対応する３２ビツトＲＲベクトルと共に記憶するための
手段となる。各たびに、要求が仲裁のために選択される
。優先順位インデックス１１６は、対応するコマンドを
ＭＵＸ　１１７から抽出させてコマンド変換器１１９へ
供給し、そしてそれに応答して、それに対応する記憶さ
れたＲＲベクトルがその後にＲＡベクトルとの比較のた
めに抽出される。

又、第３図の仲裁システムは、使用可能なリソースモニ
タ１２１も備えており、このモニタは、使用することの
できる全てのシステムリソースの瞬時記録を与えると共
に、リソース使用可能（ＲＡ）１２２のベクトルを発生
し、これは、コマンド変換手段１１９によってリソース
比較手段１２３へ発生されたＲＲベクトル１２０と組み
合わせて送られる。

本質的に、リソースモニタ１２１は、各リソースの使用
性を確認しそしてそれに応答して、使用可能なリソース
ベクトルを記憶するレジスタ内の対応するビットをセッ
ト又はクリアするために各々のシステムリソース（第５
図のリソーステーブルで識別された）に直接リンクされ
たモジュールである。これに含まれる実際の物理的な構
成は重要なものではなく、リソースモニタ１２１が予め
指定されたシステムリソースの各々にリンクされて、所
与の時間に使用できるシステムリソースの指示（リソー
ス要求ベクトル（ＲＲ）に対応するフォーマットの）を
与えられることが必要とされるだけである。好ましくは
、リソースモニタは、各々の指定されたシステムリソー
スから、各システムリソースに対応する少なくとも１つ
のビットを有するリソース使用可能レジスタまでハード
ワイヤリンクの形態で実施され、即ち特定のシステムリ
ソースが使用中であるときには、リソース使用可能なレ
ジスタの対応するビットがセットされ、従って、レジス
タの出力は、システムリソースの使用性を指示し、リソ
ース使用可能ベクトルＲＡを表わす。第２３図の比較器
１２３は、これに送られる２つのリソースベクトルを比
較するように働き、２つのベクトルＲＲ及びＲＡが合致
すると分かった場合、即ち選択されたコマンド１１８に
より必要とされた全てのリソースがそのとき使用できる
場合には、「プロセス要求Ｊ信号１２４を発生し、即ち
この「プロセス要求」信号１２４は、選択されたコマン
ドを通常のやり方で実行する際にＳＣＵにより使用する
ことができる。

又、比較器１２３は、リザーブ信号１２０を発生するよ
うにされ、この信号はＲＲベクトルをリソースリザーブ
レジスタ（ＲＲＶ）１２５に供給させ、比較されるリソ
ースベクトルが合致しないと分かった場合に、ＲＲベク
トルで指定された必要なリソースをそこに記憶できるよ
うになっている。又、ＲＲＶ　ｌ　２５は、使用可能な
リソースモニタ１２１にもリンクされており、更新され
た使用可能なリソースベクトルＲＡ１１２をそこから発
生することができる。これは、レジスタ１２５に記憶さ
れた必要なリソースベクトル１２０により指定されたリ
ザーブされたリソースの使用不能性を表わす、又、リザ
ーブ信号１２０は、その要求をリザーブ状態であるとし
て指定させると共に要求リザーブレジスタ１２６内に記
憶させるのに使用できる。これは、優先順位決め手段１
１３及び第３図の仲裁システムの残り部分により処理さ
れた後に後で仲裁するためである。

或いは又、リソースリザーブレジスタ１２５自体は、リ
ソース比較手段１２３にリンクされていて、比較器に入
ってくるＲＲベクトルがリザーブされたリソースと比較
されて、使用可能なリソースがＲＲＶ１２５内に予めリ
ザーブされていない場合だけ選択されたコマンドを実行
するためにそれらのリソースが実際に使用可能となるよ
う確保される。

本質的に、本発明の仲裁機構は、選択されたコマンドを
実行するのに必要なリソースを決定し、どの使用可能な
リソースにも既に仲裁された要求がリザーブされていな
いことを最初に確保した後に全ての必要なリソースが使
用可能であるかどうかを判断し、特定のコマンドに必要
なリソースのいずれもが使用できないか或いは手前の要
求によってリザーブされているかを判断したときに全て
の必要なリソースをリザーブし、そして最後に、全ての
必要なリソースが使用でき且つその前に実行された要求
に対してリザーブされていないところの要求を処理可能
なものとして指示することに基づく。

一第６図には、仲裁されている特定のプロセスが処理で
きるときを識別するための上記機構を実施する好ましい
論理構成が示されている。この構成体１７０は、複数の
アンドゲート１７２を含み、その各々は、特定のリソー
スの使用性及び非リザーブ状態を各々表わす信号を２つ
の入力に受け入れる。通信要求を処理するのに使用でき
る個別のシステムリソースの数と同数のアンドゲート１
７２が設けられる。好ましい実施例によれば、３２個の
指定されたシステムリソースに関連した状態信号を受け
入れるために３２個のこのようなアンドゲート１７２が
設けられている。各アンドゲート１７２の出力は、対応
するリソースの実際の使用性を指示する。より詳細には
、出力は、ゲートへの両方の入力が高レベルであるとき
にのみ、即ち対応するリソースがシステムによって使用
できると同時に手前の要求によってリザーブされないと
きにのみ、高レベルとなり、ひいては、アサート状態と
なる。

各アンドゲート１７２から、リソースの使用性を表わす
信号が第２のアンドゲート１７４への入力の１つとして
供給され、この第２のアンドゲートは、選択されたコマ
ンドを実行するための要求が必要とされることを指示す
る信号を入力に受け入れる。リソースの必要な状態を指
示する信号は、必要なリソースベクトルＲＲから導出さ
れ、比較されている特定のリソースに対応するＲＲベク
トルからのビットの状態を表わす。従って、アンドゲー
ト１７４の出力は、入力における両方の信号が高レベル
である場合にのみ、即ち特定のリソースが使用でき且つ
必要とされた場合にのみアサートされる。

アンドゲート１７４の出力は、排他的オアゲート１７６
の２つの入力の１つとして供給され、又、このゲートに
は、ゲート１７４へ第２人力として供給される必要なリ
ソース信号も与えられる。

ゲート１７６により行なわれる排他的オア演算は、これ
に送られた２つの入力信号が異なる場合にのみ高レベル
となる出力を発生する。従って、ゲート１７６の出力は
、リソース使用可能信号が低レベルであり且つリソース
要求信号が高レベルであるときだけ、即ちそのリソース
が必要とされるが現在使用できないときだけ高レベルと
なる。全てのシステムリソースに対応する全ての排他的
オアゲート１７６の出力は、オアゲート１７８へ入力と
して送られる。従って、ゲート１７８の出力は、１つ以
上の入力が高レベルとなるたびに、即ち処理されている
要求に対応する必要なシステムリソースのいずれかが使
用できないときに、高レベルとなる。この信号は、特定
の要求に対して必要とされる全てのリソースがリザーブ
されなくてよいことを指示するものとして働き、これを
用いて、コマンド変換手段により発生されたリソース要
求ベクトルをリザーブリソースレジスタＲＲＶに転送す
る。

各々の排他的なオアゲート１７６の出力は、その入力の
２つの信号が等しいときに低レベルとなり、従って、そ
のリソースが実際にシステムに使用できることがアンド
ゲート１７４における高レベル出力の存在によって指示
された場合、及びコマンドを実行するためにリソースが
必要とされることがリソース要求信号の高レベル状態に
よって指示された場合には、それによりゲート１７６の
出力も高レベルとなる。従って、ゲート１７６における
高レベル出力は、その要求が必要とされると共に処理に
使用できることを指示する。このような状態を評価する
ために、全ての排他的オアゲート１７６の出力はノアゲ
ート１８０への入力としても送られ、これは、全ての入
力信号が高レベルである場合に高レベル出力を発生する
。従って、比較構成体の全ての排他的オアゲート１７６
の出力における信号が高レベルである場合、即ち全ての
必要なリソースが使用でき且つリザーブされていない場
合には、ノアゲート１７８の出力が対応的に高レベルと
なり、その要求の処理を開始するための信号として働く
。

ゲート１７８及び１８０の出力信号を用いて全ての必要
なリソースのリザーブを行なう特定の仕方と、仲裁要求
の処理とは、本仲裁機構の実施にとって重要ではなく、
これを行なう多数の通常の方法は当業者に明らかであり
、従って、このような詳細はここには述べない。重要な
ことは、特定のコマンドを実行するに必要な１つ以上の
リソースがシステムに使用できないか又はリザーブされ
た状態に入れられるたびにリザーブ信号が発生されると
共に、全ての必要なリソースがコマンドの実行に現在使
用されるときだけプロセス要求信号が発生されることで
ある。次の説明は、選択されたコマンドに対する必要な
リソースがコマンド変換手段（第３図の１１９）内に指
定されてそれに対応するＲＲベクトルを発生する好まし
い仕方を明らかにする。仲裁のために指定された１組の
コマンドの選択は、システムが実行可能なコマンドの全
セットから、高速の実行時間が重要となる限定された数
のコマンドを表わすサブセットを識別することに基づい
ており、残りのシステムコマンドは、システムマイクロ
コードによるか、又は他の通常の手段に基づいて処理さ
れる。次いで、選択されたサブセットが多数の広範なコ
マンドカテゴリに分割され、その各々に対して必要なメ
モリリソースの共通のグループが容易に識別される。

仲裁されているコマンドは、最初に、通常の技術に基づ
いてデコードされ、メモリコマンドであることが分かっ
た場合には、その後に、所定のコマンドカテゴリの１つ
に属すると識別される。好ましくは、コマンドサブセッ
トは、次の４つのメモリコマンドカテゴリを包囲するも
のとして指定される。

メモリ読み取り；メモリ書き込み：入力／出力読み取り；及び入力／出力書き込み。

これらカテゴリの各々に対し、そこに指定することので
きる全てのコマンドの完全なリストが作成される。又、
４つの形式のコマンドの各々を実行するのに必要な全て
のシステムリソースが指定される。従って、デコードさ
れたコマンドがメモリコマンドカテゴリの１．つに属す
るものとして識別されたときには、それに対応する組の
必要なリソースが直ちに分かる。このように、メモリコ
マンドの仲裁が著しく促進され、システムユニットから
のメモリコマンドを迅速に処理することが極めて重要で
あるために特に効果的である。

典型的な例として、メモリ書き込みオペレーションは、
実行すべき順序で次のリソースを使用しなければならな
い。即ち、アクセスする必要のある特定のメモリユニッ
トに対応するメモリコマンドバッファ：特定のメモリユ
ニット及びそのメモリセグメントに対する行き光経路；
要求を発しているユニットが所望のデータ路及び行き先
から取りだされたモジュールレベルである場合にはデー
タ路交差点、及びコマンドを発しているシステムユニッ
トに対するデータソース路。従って、デコードされたコ
マンドがメモリ書き込みカテゴリのちとに入ることが分
かったときに、上記したリソースが必要なリソースとし
て指定され、より詳細には、メモリ書き込みコマンドに
対応するリソーステーブル入力（第５図参照）がこれら
リソースに対応するビットをアサートすることにより表
わされる。例えば、コマンドがメモリユニットｌのセグ
メントｌをアドレスし、このコマンドがメモリユニット
ｌをアクセスするためにデータ路交差点を必要とするも
のとして定められたＣＰＵ４によって発せられる場合に
は、それに対応する３２ビツトＲＲベクトルがビット隘
７．２４．１３及び２９をアサートさせる。メモリ読み
取りカテゴリのもとに入る典型的なコマンドは、読み取
りリフィル、書き込みリフィル、書き込みリフィルリン
ク、書き込みリフィルロック、書き込みリフィルアンロ
ツタ、ＤＭＡ読み取り及びＤＭＡ読み取りロックを含む
。このカテゴリにおけるこれらコマンドの１つが仲裁さ
れるときには、それに対応するＲＲベクトルがそのカテ
ゴリに対して一般的に指定されたリソースを含む。

同様に、他のカテゴリは、所定の１組の共通のリソース
を含むように定められる。例えば、メモリ書き込みカテ
ゴリは、書き込みバック、ＤＭＡ書き込み及びＤＭＡ書
き込みアンロックコマンドを含む。Ｉ１０読み取りカテ
ゴリは、読み取りＩ１０レジスタコマンド及びサービス
プロセッサ読み取りコマンドを含み、一方Ｉ１０書き込
みカテゴリは、書き込みＩ１０レジスタコマンド及びサ
ービスプロセッサ書き込みコマンドを含む。いずれかの
メモリコマンドカテゴリに入らないコマンド又は更に別
のリソースを要求しているコマンドは、対応するＲＲベ
クトルを発生するために必要なリソースのグループを個
々に定めることができる。

もちろん、本発明の仲裁機構のもとてオペレーションす
るように選択された全てのシステムコマンド（全てのメ
モリコマンドを含む）は、「共通カテゴリ」のやり方を
用いるのではなく、必要なリソースのグループを個々に
定められることが理解されよう。或いは又、システムリ
ソースを表わす各ビットには、そのビットをアサートす
ることのできる対応する１組のシステムコマンドが指定
され、対応するＲＲベクトルは、コマンドをデコードし
、それを各々のリソースビットと比較し、そしてそのビ
ットに関連したコマンドセット内にコマンドが入るかど
うかに基づいてビットをアサートもしくはネゲートする
ことにより発生することができる。従って、本発明の仲
裁機構は、ＲＲベクトルを発生する特定の方法に限定さ
れないことが明らかであり、システムは、仲裁のために
選択された要求に関連したコマンドを実行するに必要な
全てのシステムリソースのリストを発生できるだけでよ
い。

上記説明から明らかなように、本発明の仲裁機構は、本
質的に、リザーブバスによって仲裁を開始し、その後、
必要に応じて多数の別々のりチエツクバス及び非リザー
ブバスを行なって、全ての未解決のリザーブされた要求
を仲裁及び処理することを含む。それ以上のリザーブさ
れた要求が保留中でないと分かった場合には、新たなリ
ザーブバスが開始され、それに続いて、非リザーブバス
及びリチェックバスが交互に行なわれる。従って、仲裁
シーケンスは、ノン・ストップであり、これは、システ
ムリソースが効率的に使用されないために典型的にシス
テム性能の低下を招く要求事項の突発的なポーリングを
伴う従来の仲裁機構に勝る顕著な改良である。

本発明の機構は、選択された要求が仲裁されるときに使
用できる全てのシステムリソースを効率的に使用する。

更に、本発明の機構による仲裁は、非ロツクアウト特性
のものであり、これは、必要なリソースのリザーブが最
初のバス中にしか許されず、その後のりチエツク及び非
リザーブバスは、必要なリソースが実際に使用できると
ころの未解決のリザーブされた要求及びその後に受け取
られる要求の各々仲裁及び実行に専用なものにされる。

従って、リザーブされた状態に入れられる各要求は、適
度な時間内に処理することが保証され、要求を発しって
いるユニットがロックアウトされることは決してない。

【図面の簡単な説明】

第１図は、複数のプロセッサ及び入力／出カニニットを
動作するためのシステム制御ユニット（ＳＣＵ）であっ
て本発明の仲裁機構を効率的に使用することのできるユ
ニットを用いたマルチプロセッサシステムのブロック図
、第２Ａ図、第２Ｂ図及び第２Ｃ図は、本発明の仲裁機構
のベースとなるシーケンス手順を示すフローチャート、第３図は、第１図に示した形式のマルチプロセッサシス
テムにおいて第２図の仲裁機構を実施するための好まし
い手段を示すブロック図、第４図は、仲裁要求を選択す
るための好ましいハイアラーキ優先順位決め機構を実施
する構成を示した回路図、第５図は、必要なリソースベクトルを発生するコマンド
変換手段内に使用されてリソースベクトルによって識別
される種々のシステムリソースの好ましい表示をリスト
したテーブル、そして第６図は、第３図のリソース比較
器を実施するための好ましい論理構成を示す回路図であ
る。１０・・・マルチプロセッサシステム１２・・・中央処理ユニット（ｃ’、ｐｕ）１４・・・
システム制御ユニット（ＳＣＵ）Ｉ６・・・メインメモ
リ１８・・・入力／出力（Ｉ／Ｏ）制御器２ｏ・・・Ｉ１
０インターフェイス２２・・・サービスプロセッサ／コンソールユニット（
ＳＰＵ）

Claims

【特許請求の範囲】

（１）スカースのシステムリソースを割り当てるための
要求を仲裁する方法において、上記要求は、上記スカー
スのシステムリソースを割り当てるために実行されるべ
き対応するコマンドによって指定されるものであり、上
記方法は、仲裁されるべきコマンドを受け入れ、上記受け入れられたコマンドを実行するのに必要な全て
のスカースのシステムリソースを定める第１ベクトルを
発生し、現在使用できる全てのスカースのシステムリソースを表
わす第２ベクトルを発生し、上記第１ベクトルと第２ベクトルとを比較し、上記コマ
ンドを実行するのに必要な全てのスカースのシステムリ
ソースが現在使用できることが上記比較によって指示さ
れる場合に上記受け取ったコマンドを実行し、さもなく
ば、（ｉ）コマンドを「リザーブ」された状態に入れ、
（ｉｉ）上記受け取ったコマンドを実行するように上記
要求された全てのスカースシステムリソースをリザーブ
し、そして（ｉｉｉ）上記受け取ったコマンドを実行す
るために要求された全てのスカースシステムリソースが
使用できるときに上記受け取ったコマンドを実行すると
いう段階を具備することを特徴とする仲裁方法。
（２）上記受け取ったコマンドは、一連のコマンドを記
憶しそして上記受け取ったコマンドを予め定められた優
先順位機構に基づいて選択することにより受け取られる
請求項１に記載の仲裁方法。
（３）上記予め定められた優先順位機構は、記憶された
コマンドに対し、第１の仲裁バス（リザーブバス）を含み、この間には、
上記一連のコマンドを記憶するための記憶位置がポーリ
ングされると共に、対応するリザーブされたリソースを
使用できるところのコマンドを実行しそして全ての要求
されたスカースシステムリソースを使用できないところ
の全てのコマンドをリザーブされた状態に入れることに
よりそのときの上記記憶位置に記憶されているコマンド
が実行され、更に、第２の仲裁バス（リチェックバス）を含み、この
間には、全ての要求されたスカースシステムリソースが
そのとき使用できるようになったリザーブされた要求を
実行しそしてこの要求されたスカースシステムリソース
がそのとき使用できないリザーブされたコマンドに対し
て全ての要求されたスカースシステムリソースをリザー
ブすることにより、受け取ったコマンドのみが実行され
、更に、第３の仲裁バス（非リザーブバス）を含み、この
間には、手前の「リザーブ」バス（「新たな」要求）に
続く上記記憶位置に記憶されたコマンドのみが、全ての
要求されたスカースシステムリソースを使用できるとこ
ろの新たなコマンドを実行することにより仲裁される請
求項２に記載の仲裁方法。
（４）「リザーブ」バスの実行後に、次々の「リチェッ
ク」及び「非リザーブ」バスが交互に実行され、これは
最初の「リザーブ」バスの間にリザーブされた全てのコ
マンドが実行されるまで行なう請求項３に記載の仲裁方
法。
（５）少なくとも１つの入力／出力（Ｉ／Ｏ）ユニット
との組み合わせで複数のプロセッサを並列に動作させる
ためのシステム制御ユニット（ＳＣＵ）を有する形式の
マルチプロセッサシステムにおいて、上記ＣＰＵ及びＩ
／Ｏユニットの各々はＳＣＵにポート結合されており、
ＳＣＵは、上記ＣＰＵ及び上記Ｉ／Ｏユニットがシステ
ムメモリのアドレスされたセグメントを制御か能にアク
セスできるようにし、上記ＣＰＵ及びＩ／Ｏユニットか
らＳＣＵのポートで受け取った通信要求を効率的に且つ
公平に仲裁する方法であって、この要求にはこれを処理
するために実行されねばならないコマンドが組み合わさ
れているような方法が、入ってくる要求を記憶し、そこ
から、予め定められた優先順位決め機構に基づいて、仲
裁されるべき要求を選択し、選択された各要求に対応するコマンドを仲裁のために抽
出し、上記抽出されたコマンドを実行するに必要な全てのシス
テムリソースを定める第１ベクトルを発生し、上記選択された要求が仲裁されるときに使用できる全て
のシステムリソースを表わす第２ベクトルを発生し、上記第１ベクトルと第２ベクトルを比較し、全ての対応
する要求されたリソースが使用できる場合にコマンドを
処理し、さもなくば、上記コマンドに対応する要求を「リザーブ
」状態に入れ、リザーブされた要求に対応する全ての要求されたリソー
スが、上記リザーブされた要求の仲裁時に使用できない
場合にはこれらのリソースをリザーブし、そしてその後、対応するリザーブされたリソースが使用できる
ときにその関連コマンドを実行することにより上記リザ
ーブされた要求を処理することを特徴とする仲裁方法。
（６）上記仲裁シーケンスは、第１の仲裁バス（リザーブバス）を含み、この間には、
全てのＳＣＵポートがポーリングされると共に、対応す
るリザーブされたリソースを使用できるところの要求を
処理しそして全ての要求されたリソースを使用できない
ところの全ての要求をリザーブされた状態に入れること
によりそのとき未解決となっている要求が仲裁され、更に、第２の仲裁バス（リチェックバス）を含み、この
間には、全ての要求されたリソースがそのとき使用でき
るようになったリザーブされた要求を処理しそしてその
リソースがそのとき使用できないリザーブされた要求に
対して全ての要求されたリソースをリザーブすることに
より、受け取った要求のみが仲裁され、更に、第３の仲裁バス（非リザーブバス）を含み、この
間には、手前の「リザーブ」バス（「新たな」要求）に
続いてＳＣＵで受け取った要求のみが、全ての要求され
たリソースを使用できるところの新たな要求を処理する
ことにより仲裁される請求項５に記載の仲裁方法。
（７）「リザーブ」バスの実行後に、次々の「リチェッ
ク」及び「非リザーブ」バスが交互に実行され、これは
最初の「リザーブ」バスの間にリザーブされた全ての要
求が処理されるまで行なう請求項６に記載の仲裁機構。
（８）複数の中央処理ユニット（ＣＰＵ）及び少なくと
も１つの入力／出力（Ｉ／Ｏ）ユニットを含む複数のシ
ステムユニットを並列に動作させるためのシステム制御
ユニット（ＳＣＵ）を有する形式のマルチプロセッサシ
ステムにおいて、上記ＳＣＵは、上記ＣＰＵ及び上記Ｉ
／Ｏユニットが上記システムユニットからの通信要求を
仲裁することによりアクセスされたメモリセグメントを
制御可能にアクセスできるようにし、各要求は、対応す
る１組の予め定められたシステムリソースを使用できる
ときに当該コマンドを実行することにより処理すること
ができ、上記システムは、システムユニットからの入っ
てくる要求及びそれに関連したコマンドを記憶するため
の手段と、上記記憶された要求の選択された１つに組み
合わされたコマンドを仲裁のために選択する手段と、そ
の選択されたコマンドを実行するのに必要な全てのシス
テムリソースが仲裁時に使用できるかどうかを判断する
手段と、全ての要求されたリソースを使用できる場合に
要求の処理を開始する手段と、全てのこのようなリソー
スが使用できない場合に、このようなリザーブされたリ
ソースが次の要求に対して使用不能となるように、仲裁
されている上記要求に対応する要求されたリソースをリ
ザーブする手段と、対応するリザーブされたリソースが
使用可能となったときにリザーブされた要求の処理を開
始する手段とを備えたことを特徴とするマルチプロセッ
サシステム。
（９）選択されたコマンドによって要求されたリソース
が使用可能かどうかを判断する上記手段は、選択された
コマンドを実行するに必要な全てのリソースを識別する
第１リソースベクトルを発生する手段と、仲裁時に使用
できる全てのシステムリソースを表わす第２のリソース
ベクトルを発生する手段と、上記第１及び第２のリソー
スベクトルを比較する手段とを備えている請求項８に記
載のマルチプロセッサシステム。
（１０）入ってくる要求及びそれに関連したコマンドを
記憶する上記手段は、入ってくるコマンドを受け取って
記憶する手段と、入ってくる要求を受け入れて、所定の
優先順決め機構に基づいて、仲裁しなければならない選
択された要求に対応する上記記憶されたコマンドの選択
された１つを表わすコマンド信号を発生するための優先
順位決め手段と、上記制御信号に基づいて選択された記
憶されたコマンドを抽出しそしてこの抽出されたコマン
ドを上記第１リソースベクトルを発生する上記手段に中
継する手段とを備えている請求項９に記載のマルチプロ
セッサシステム。
（１１）上記リザーブされたリソースに基づいて第２の
リソースベクトルを調整することにより上記リザーブさ
れたリソースを次の要求に対して使用不能にする手段を
更に備え、要求の処理を開始する上記手段は、調整され
た第２のリソースベクトルに応答する請求項１０に記載
のマルチプロセッサシステム。