JPH02226343A - 計算機装置および優先順位決定方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はコンピュータ・システムにおける優先順位の決
定に関し、ざらに詳しくは、共通資源の使用を必要とす
る命令やコマンドの選択を行うためのプログラム可能な
優先順位ならびに選択的ブロッキング方式を提供するも
のである。

Ｂ、従来技術及びその課題 ］ンピュータ・システム、特に多重プロセッサを有する
システムにおいては同時実行不可能なコマンド及び命令
の優先順位を決定するシステムが不可欠である。はとん
どの従来の優先システムでは、すべて、あるいは一部が
固定されており、そのフレキシビリティは期待できなか
った。

１つ以上のリクエストが処理システム中の直列経路に出
きれたときに使用される優先システムは必要不可欠であ
る。すべての実際の目的において、優先システムはその
システムに望ましい既知の順位に従ってリクエストを選
択すべきである。マシン構築時に理想的な優先順位が未
知であったり、優先順位が処理ごとに変わるものである
ときは、プログラム可能な優先順位が有効なものとなる
。

Ｃ１発明の概要及び解決課題 本発明の目的は低コストで実現可能なプログラマブル優
先体系を提供することである。

ざらに、あるタイプのコマンドや命令の迅速な実行の要
求を考慮しないラウンド・ロビン型の優先体系を避ける
ことも本発明の目的である。

また、ソース・ＩＤを指示し、その後これらのＩＤが選
択される順序を決定するプログラマブル優先コードを提
供することも本発明の目的である。

もう１つの重要な目的は、異なるプログラマブル優先コ
ードの各々ごとにすべてのソースを完全に再順序づける
とともに、実際のオペレーションの間には固定されてい
るように見える機能を提供することである。

さらに、いかなるソースもコマンドを伴うことができ、
特定のソース（例えばプロセッサ）がリセットするまで
他のソースが優先回路に侵入するのを排除するように、
ソースの選択的ブロッキングを提供することも本発明の
目的である。

また、優先順位により選択された後のコマンドを監視す
るモニタ・レジスタを設け、当該コマンドのスタートを
やり直しきせるような競合が生じたときに、モニタ・レ
ジスタでこれを検知して、この競合が解除されるまで当
該コマンドが優先サイクルをとらないことも、本発明の
目的である。

この競合が解除きれたときは、モニタ・レジスタはリセ
ットきれ、当該コマンドは優先サイクルに再び入ること
が許される。

以上のごとく、本発明は優先順位を完全に変えることが
できるプログラマブル優先コードを提供するものであり
、さらに競合、エラーまたは他の事象が当該優先順位を
無視する必要性を引き起こすような場合に、すでにクリ
アされた要求を選択的に排除する方法を提供する。

Ｃ９実施例 ここで示した実施例はこの複雑な問題を解決するための
手段としてユニークな技術を開示する。

これは２から４のソースを選択可能なボッドから構成き
れるツリー構造優先体系を使用することである。各ボッ
ドは２ないし５ピツトのデータで制御される。２ビツト
は２ソースのボッドを制御するために使用され、３ビツ
トは３ソースのボッドを、５ビツトは５ソースのボッド
を制御するために使用される。各ソースは、例えばソー
ス１がＯＯのようなコードを与えられている。最も理解
しやすい形としてボッドにおけるソースは例えば、第１
図のようなサークル状に表現される。ここから、どのよ
うにして指定ソース・コードが与えられるかが理解され
よう。これらのコードの１つはボッドの優先順位を制御
するデータの最初の２ビツトとして置かれる。そのコー
ドが置かれたソースは最高の優先順位を有する。このソ
ースがリクエストを有する場合には、他のソースがリク
エストを有しているか否かにかかわらず、これが実行さ
れる。第１図に示すようにＨＰは最優先ソース・コード
を示す。このソースからのリクエストが最初に処理され
る。これが存在しなければ、次の優先レベルのものが処
理きれる。

２ソースのボッドにおいてこれら２つのビットはすべて
必要なものとなる。たとえ、ツリー構造の他の構成を破
壊しないように１ビツトを使用可能としてもである。と
いうのは、使用されたビット中のソース・コードが最高
の優先順位を有するソースを指定するものであると、指
定されないソースが優先順位において２番目となるから
である。

ボッドの優先順位を制御する第３のビットは第１図に示
きれたサークルに沿った回転を示すものとして使用され
る。Ｒと記きれたこのローテーション・ビットはソース
のボッド・サークルに沿った回転方向を変えるのに使用
きれる。このローテーション・ビットは最高の優先順位
を持つソースの一 後にどのソースが続くかを示す。ローテーション・ビッ
トがＯのときは、す・−クルを時計回りに経路を取る。

ビットが１のときは経路はこの逆回りとなる。このビッ
トは３または４ソースのボッドについてのみ必要となる
。３ソース・ボッドの場合、最優先コードが００で、ロ
ーテーション・ビットがＯであると、優先順位は０Ｏ１
０１，１０の順となる。ローテーション・ビットが（１
）のときには優先順位は０Ｏ１１０，０１の順となる。

先の例において、最高の優先順位をもつソースがＯＯか
ら１０あるいは０１に変化すると、ローテーション・ビ
ットはソースの６つの可能な組合せを達成するように優
先ソース類を変更する（第１図参照）。

第４及び第５ビツトは４ソース・ボッドの場合のみに必
要となる。第４ビツトは、最優先コード及びローテーシ
ョン・ビットによって通常は第２番目であると示される
ソースが、今回は最後であることを示す。例えば、４ソ
ース・ボッドにおいて最初の３つの制御ビットが優先ソ
ース類００．０１．１０．１１を設定する。第４ビツト
が１にセットされていると、最後の３つのソースを１位
置ずつ回転させて００，１０．１１．０１の順に変える
。

第５ビツトが１にセットされていると、上述と同様の動
作をするが、この場合は最後の３つが２位置ずつ回転す
る。前述の例では、優先ソース類００．０１．１０．１
１が００，１１．０１．１０に変わる。この第５ビツト
は第４ビツトにかかわらず、最後の３ソースの順を２位
置ずつ回転させる。第５ビツトは１にセットきれている
ときは第４ビツトに優先する。

これらの最後の２ビツトはスキップ・ビットと呼ばれる
。というのは、ローテーション・ビットが示す方向に最
優先ソースに続く２つまたは３つのソースをスキップさ
せるからである。ここでは４ソース・ボッドのサークル
を考える。最高の優先順位を持つソースからローテーシ
ョン・ビットの示す方向に移動する場合を考えるにあた
り、最高の優先順位がＯＯで、ローテーション・ビット
がＯであると仮定する。ここで第１スキツプ・ビットが
ハイで、第２スキツプ・ビットがローであると、これは
先の例のごとく優先順位は０Ｏ１１０，１１，０１とな
ることを示す。このソース類はＯＯからスタートして、
次のソース０１をスキップして１０に飛び、それからす
べてのソースが選択されるまでサークルに沿った選択プ
ロセスを継続することによって達成される。ＯＯは最初
のラウンドで選択されているので第２ラウンドでは選択
されない。第２スキツプ・ビットは、２つのソースが０
０の後にスキップされることを除けば、同様に作用する
。ソースの選択はすべてのソースが選択されるまで実行
きれる。このように、スキップ・ビットは２ビツトであ
って、優先サークルの最初の回転の際に、次の１つある
いは２つのソースをバイパスすることを示す。

本発明のプログラマブル優先順位はコンピュータ・シス
テムの導入時の優先順位のセット、さらにコンピュータ
・システムが動作中の任意の時点で優先順位を動的に変
更する際に有用である。

この優先システムは第３図に示すようにいわゆる優先心
臓部において実現される。これは回転方向、スキップお
よびソースＩＤビットを持つプログラマブル・セット１
９によって制御ＩＩされる。第３図の実施例では、共通
資源に対して４つのリクエスト１２．１３．１４．１５
まで扱える。第４図の実施例は３つのリクエストの場合
の優先制御回路の例を示したものである。数字１．２及
び３は第３図の最初の３つの優先レベルを示し、第４図
の番号を付されたゲートに対応する。経路１６．１７の
２つのＩＤビット及び経路１８のローテーション・ビッ
トを変えることによって、同時に受取られた競合リクエ
ストを処理するための優先順位をゲーティングが自動的
に変える。競合リクエストには、例えば、０１コードの
ストア行列リクエスト２１．１０コードのコマンド・バ
ッファ・リクエスト２３．１１コードのチャネル＆低メ
モリ・リクエスト２５等の競合である。この例ではコー
ドｏＯは無効エントリである。第２図のブロッキング回
路２７からのブロッキングが発生した場合には、特定ソ
ースはブロッキングが終結するまで選択されることはな
い。

本発明の重要な特徴を構成するブロッキングの１つのソ
ースは競合を監視する多数のレジスタである。これらの
レジスタはモニタ・レジスタ３１と呼ばれ、第２図のＦ
ｌからＦ６によって表される。選択された各リクエスト
は競合の存在が確認されるまで、その実行を遅らせるた
めに３３に入力される（第５図参照）。競合が存在する
場合は、競合が解除されるまでリクエストは保留され、
解除のときは優先回路に再入する。

本発明の実現形態は多重プロセッサを含むソースを有す
る。この実現形態でモニタされる競合はロック、ライン
・ホールド、および凍結レジスタ（図示せず）によるも
のである。ロックは、他のプロセッサかデータの８バイ
ト　セグメントの状態を変えるのを妨げるレジスタであ
る。ライン・ホールドは、プロセッサごとに設けられる
３つのレジスタであり、ラインがキャッシュ・レベルで
無効化されるのを防止する。凍結レジスタは、キャッシ
ュ・レベルにおいて同じデータの重複したインページ・
リクエストの発生を防止する。

モニタ・レジスタは、ロック、ライン・ホールド、凍結
レジスタ（図示せず）に関連する一連のレジスタである
。実施例では６つのプロセッサがあるので６個の凍結レ
ジスタがあり、これらの凍結レジスタに対して６個のモ
ニタ・レジスタがある。ラインメホールドあるいはロッ
ク・レジスタに関しては、１８個のライン・ホールド各
々に対して、また６個のロック・レジスタ各々に対して
個々のモニタ・レジスタは必要でない。まず、ライン・
ホールドおよびロックは相互に排他的な関係であり、同
じ物理的レジスタを共用するから、いずれにしてもモニ
タ・レジスタを別々に持つ必要がない。また、各プロセ
ッサに対する３つのライン・ホールドは同時にリセット
され、従って、これらは１つのモニタ・レジスタにグル
ープ化できる。この結果、総数で１２個のモニタ・レジ
スタが必要となるにすぎず、そのうち６個が凍結レジス
タに関する競合をカバーし、６個がロック、およびライ
ン・ホールドに関する競合をカバーする。

モニタ・レジスタ中には、適切なレベルでの優先順位に
対して補助を行うために必要なコマンドの各ソースに対
応するビットがある。必要なのはプロセッサ１個に対し
て２つのコマンドのソースである。これらはコマンド・
バッファおよびストア待行列である。この実現形態にお
けるコマンドの他のソースはＢＳＣ（バス・スイッチン
グ・コントロール）インタフェースであり、これはＢＳ
Ｃ優先順位によって制御されるので、モニタ・レジスタ
では必要ない。第２図の４ビツト・レジスタの代わりに
、モニタ・レジスタは１２ビツトを持ち、各プロセッサ
に対して各々２ビツト、各コマンド・バッファ（ＣＢｘ
）に１ビツト、各ストア待行列（ＳＱｘ）に１ビツトず
つで割当てられる。これを第６図に示す。

上記の状態の１つによって何かが妨げられると、何らか
の競合が発生する。もし、成るラインがライン・ホール
ドの１つによって無効化を妨げられ、ソースがその無効
化を行おうとすると、競合が発生する。この場合には無
効化を行おうとしているソースはライン・ホールドのア
ドレス・マツチの結果としてその無効化を妨げられ、ラ
イン・ホールドがクリアされるまでブロッキングによっ
て優先順位が排除（ｈｏｌｄ　ｏｕｔ）される。ライン
・ホールドはキャッシュ（図示せず）に対するシーケン
シャル・ストア・バッファのデータ・ストアによってク
リアきれる。この時、データのアドレスを保持している
すべてのライン・ホールドはリセットされ、かくてこれ
らのライン・ホールドに関連するモニタ・レジスタもリ
セットされ、これによってブロッキングは終結する。

もう１つの例は８バイト・データのロックの場合である
。プロセッサＢが当該データに対するストアを実行しよ
うとするときにプロセッサＡによるロックが発生し得る
。この場合に競合が発生する。このロックに関連するモ
ニタ・レジスタはマツチ・アドレスを検出し、ストアに
対するリクエストを行っているソースのビット位置をハ
イにセツトする。この場合、ストア待ち行列ビットはプ
ロセッサＡのロック　モニタ・レジスタにおいてプロセ
ッサＢのためにセットされる。セットきれたストア待ち
行列ビットはロックきれたデータが解放されるまでプロ
セッサＢがストア・コマンドを再開しようとするのを妨
げる。これは優先サイクルが実行可能な他のソースによ
って使用され得る場合にこれらのサイクルがこのコマン
ドによってむだに使用されるのを防ぐものである（第５
図参照）。プロセッサＢのストア待ち行列の優先度をブ
ロックするのはこのビットのみではなく、１２個のモニ
タ・レジスタの各々におけるプロセッサＢのストア待ち
行列を表す各ビットも同じである。優先順位に従ってリ
クエストが実行されるためには、これらがすべてＯでな
ければならず、ざもなければそれらがすべてＯになるま
でリクエストは実行されない。この例において、ロック
はプロセッサＢのストア待ち行列の唯一の競合であり、
プロセッサＡがデータをロックから解放したときはモニ
タもリセットされる。競合が解除されると、プロセッサ
Ｂと同様、プロセッサＡのロックに関連するモニタ・レ
ジスタによって優先順位から排除されたすべてのソース
は、優先回路に復帰できることとなる。

通常の優先順位の選択を変更するブロッキングの例を第
２図に示す。これはシステム・ブロック３５を介してエ
ラー・セット３７および／または選択ソース・セット３
９によって開始きれるブロッキングを含む。ざらに、す
べてのソースをブロックするビット４９と個別のソース
をブロックするビット４５．４６．４７および４８を持
つプログラマブル・セット４３により、プログラマブル
・ブロック４１を介して開始されるブロッキングをも含
む。第２図に示すようにブロッキングは状況に応じて個
々のソースあるいはすべてのソースに作用する。いかな
るブロッキングにおいても、ブロックきれているリクエ
ストは優先心臓部に入り続けることはできず、競合また
はブロッキングを生ぜしめた他の事象が解除されるまで
待機し、その後優先心臓部に再び入ることとなる。

Ｄ０発明の効果 上述のごとく本発明によればプログラムによって変更可
能な優先順位の決定システムが達成される。

【図面の簡単な説明】

第１図は本発明の実施例における優先制御ビットの構造
を示す図、第２図は第２Ａ図、第２Ｂ図の結合様式を示
す図、第２Ａ図および第２Ｂ図はそれぞれ複数のブロッ
キング信号および優先回路の相互作用を示すブロック図
、第３図は４ソースの場合の優先回路の動作を示すブロ
ック図、第４図は３ソースの場合の優先コードの実現に
使用されるゲーティングを示す回路図、第５図は本発明
の実行の際のタイミング図、第６図はモニタ・レジスタ
の構成を示す構成図である。 ３１・・・・モニタ・レジスタ、４１・・・・フログラ
マプル・ブロック。 第 ・シーケンス ５図

Claims (2)

【特許請求の範囲】
1. （１）共通資源に向けられる複数の要求間の優先順位を
   決定する方法であつて、 前記要求を行つている各ソースに符号化された識別記号
   を付与するステップと、 前記識別記号をそれらの相対的優先順位を確立する２進
   ワードにプログラムするステップと、前記プログラムさ
   れた２進ワードを優先回路を通じて転送することにより
   、該回路を前記相対的優先順位に従つてプリセットする
   ステップと、所与の時点で１つの要求を選択するように
   前記優先回路に前記すべての要求を入力するステップと
   からなることを特徴とする優先順位決定方法。
2. （２）共通資源に対する複数の要求を持つ計算機装置に
   おいて、 前記複数の要求間のすべての優先順位を与えるようにプ
   ログラム可能な優先回路手段と、 前記優先回路手段の動作を変更させるように動作するブ
   ロッキング回路と、 前記優先回路手段および前記ブロッキング回路に接続さ
   れ、前記優先回路手段より選択されるべき要求をブロッ
   クする時機を決定するための調整回路手段とを有するこ
   とを特徴とする計算機装置。