JPH0325558A - マルチプロセッサシステムの主記憶アクセスリクエスト選択方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、複数のプロセッサを備えたマルチプロセッサ
システムにおいて、各々のプロセッサから出力された主
記憶アクセスリクエストを最適な方法で選択する主記憶
アクセスリクエスト選択方式に関するものである。

〔従来の技術〕

第４図は特開昭６３−８６０６２号に従来技術として示
されている従来の主記憶アクセスリクエスト選択装置の
構或例である。同図において、２ｂは優先順位制御回路
、３はリクエスト受信レジスタ、４は優先順位カウンタ
、５はロックレジスタ、６はパイプライン、７はバンク
ビジー表示回路、８は主記憶アクセス起動レジスタであ
る。

この構或において、各プロセッサからの主記憶アクセス
リクエストは各々のプロセッサに対応したリクエスト受
信レジスタ３にバッフ戸リングされる。図示の例では、
プロセッサ数が４台に仮定ざれているので、リクエスト
受信レジスタ３はＲＲＯ〜ＲＲ４の４個存在する。バッ
ファリングされた主記憶アクセスリクエストは優先順位
制御回路２ｂに送られる．優先順位制御回路２ｂは各リ
クエスト受信レシズタ３から送られてきている主記憶ア
クセスリクエストのうち唯一のリクエストを選択する。

パイプライン６は主記憶￥ｉＮＩｌを起動したアクセス
を各ステージ毎に保持するものである。優先順位カウン
タ４はｎビットのカウンタで、プロセッサ間の優先順位
を動的に決定するものであり、リクエストが選択される
毎に優先順位が変更される。プロセッサをＰＯ〜Ｐ３と
すると、優先順位制御回路２ｂは優先順位カウンタ４の
ｎビットをデコードすることにより、下記の優先順位を
指定する。

カウンタ４ ２ピット出力　　　　優先順位 ００　　　　：ＰＯ　　　ＰＩ　　　Ｐ２　　　Ｐ３“
０１　　　　：ＰＩ　　　Ｐ２　　　Ｐ３　　　Ｐ４１
０　　　　：Ｐ２　　　Ｐ３　　　ＰＯ　　　Ｐ１１１
　　　　：Ｐ３　　　ＰＯ　　　ＰＩ　　　Ｐ２パング
ビジー表示回路７は主記憶のバンク対応に各バンクのビ
ジー時間を保持するフラグを持ち、このフラグがオンで
あるバンクへのアクセスは、このフラグがオフになるま
での期間抑止される。

ロックレジスタ５はロックされたバンクのアドレスまた
はキャッシュブロック単位のアドレスが保持され、バン
ク単位またはブロック単位のロックが実現される。この
ロックレジスタ５の値が有効な間、同一バンクまたは同
一ブロックへのアクセスはロックを指令したプロセッサ
からのアクセス以外は抑止される。ロックレジスタ５は
、ロックを起動したブＯセッサからのロック解除リクエ
ストによって無効化される。

〔発明が解決しようとする課題〕

上述した従来のアクセスリクエスト選択方式では、プロ
セッサ間の優先順，位のみを動的に変化させていたため
、多数のプロセッサから＄１１！にリクエストが発生す
る場合、優先順位が低く割当てられているプロセッサは
自分の優先順位が高くなるまで待たされる可能性がある
。これは優先順位の低いプロセッサからのリクエストが
優先順位の高いプロセッサからのリクエストよりも時間
的に早く発行されても、優先順位の高いプロセッサから
のリクエス１・に追越されてしまう可能性があることを
意味する。仁のような状態が生じる例を第５図により説
明すると、ここでは時間ＴｏからＴ３まで、優先順位制
御回路２ｂで１回のリクエスト選択に要する時間単位で
区切られ、各々の時間に対して各プロセッサからリクエ
ストの状態が示されている。リクエスｉ・の状態は“ｄ
　Ｓ　ｎが優先順位制御回路２ｂでリクエスト選択処理
されている状態、′Ｗ”が優先順位制御回路２ｂの入口
で待たされている状態を示しており、この例ではプロセ
ッサＰ３のリクエストが長時間待たされている場合を示
している。このときの例の動作を時間毎に説明する。

ＴＯ：プロセッサＰ２とプロセッサＰ３が同時にリクエ
ストを発行する。このとき、プロセッサＰ２の方が優先
順位が高いので、プロセッサＰ２のリクエストが選択さ
れる。

Ｔ１：継続的にプロセッサＰ３からのリクエストは発行
され続けている．さらにこの時点でプロセッサＰ１から
リクエストが発行される。このとき、プロセッサＰ１の
方が優先順位が高いため、プロセッサＰ１のリクエスト
が選択され、この時点でリクウエストの追い越しが生じ
る。

Ｔ２：継続的にプロセッサＰ３からのリクエストは発行
され続けている。さらにこの時点で、プロセッサＰＯか
らのリクエストが発行される。このとき、プロセッサＰ
Ｏの方が優先順位が高いので、プロセッサＰＯのリクエ
ストが選択され、この時点で再びリクエストの追い越し
が生じる。

Ｔ３：継続的にプロセッサＰ３からのリクエストは発行
され続けている。この時点でプロセッサＰ３の優先順位
が最高になるので、プロセッサＰ３からのリクエストは
この時点で初めて選択される． このようにして１つのプロセッサからのリクエストが長
時間待たされることは、優先順位の高いプロセッサがロ
ック領域を指定した場合にシステム性能の低下を招くと
いう問題点がある。具体的には以下に示すようなことが
生じる。

（１）プロセッサＰｉがロックをかけた主記憶領域に、
プロセッサＰｊがその領域をアクセスしようとするが、
ロックがかけられているためにキャンセルされる。

（２）プロセッサＰｊは再び同じところをアクセスしよ
うとする． （３）プロセッサＰｉはロック解除のリクエストを発行
する。

（４）プロセッサＰｊの優先順位の方がプロセッサｉの
優先順位よりも高いので、プロセッサＰｊからのリクエ
ストの方が優先され、再びロックをかけられた領域に対
してアクセスしてキャンセルされる。

このようにロック解除のリクエストを出しているプロセ
ッサがその優先順位が上がるまで艮時間持たされること
によって、上記（４）のような無駄なリクエストが何回
も受付けられてしまい、システム全体の性能の低下を招
いてしまうという問題点がある。

また、上記例ではプロセッサの数が多くなるほど優先順
位が上がるまでの時間が多くなるため、プロセッサの数
が多くなっても待ち時間が増加しないようなリクエスト
選択方式が要望されている．本発明は上記のような問題
を解決するためになされたもので、リクエストの追い越
しを回避し、システムの性能の低下と待ち時間の増加を
防止できるマルチプロセッサシステムの主記憶アクセス
リクエスト選択方式を提供することを目的としている。

［課題を解決するための手段〕 本発明は、優先順位に従って主記憶＠置へのアクセスリ
クエストを選択する手段の他に、時間的に先に発行され
たアクセスリエストを選択する手段を設けたものである
．すなわち、各プロセッサから発生される主記憶アクセ
スリクエストの優先順位を一定時間毎に動的に変化させ
、その優先順位に従って複数のプロセッサから同時に発
行されているリクエストのうち、唯一のリクエストを選
択すると共に、選択されたリクエストを表わす通知信号
を出力するリクエスト選択手段（４ｌ！先順位制御回路
２ａ）と、各プロセッサから任意の時刻に発行されるリ
クエストを一時的に保持しておく第１リクエスト保持手
段（リクエスト保持レジスタＡ１２）と、この第１リク
エスト保持手段に保持されていたリクエストを受取って
保持すると共に、保持しているリクエストを前記リクエ
スト選択手段に送り、さらに保持していたリクエストの
中で前記通知信号で示されるリクエストを消去し、さら
に保持されていたリクエストがなくなった時に再び前記
第１リクエスト保持手段に保持されていたリクエストを
受取る第２リクエスト保持手段〈リクエスト保持レジス
タラッチＢ１３）と、前記第１．第２リクエスト保持手
段の両方にリクエストが保持されていない時に各プロセ
ッサからのリクエストを直接に前記リクエスト選択手段
に転送するリクエスト切換手段《リクエストセレクタ１
１〉とを設けたものである。

（作用） ２台以上のプロセッサから同時にリクエストが発生され
た場合、各プロセッサからのリクエストは第１リクエス
ト保持手段に送られる。この時、第２リクエスト保持手
段に保留されているリクエストが存在しなければ、各プ
ロセッサからのリクエストは同時にリクエスト選択手段
に送られる。

リクエスト選択手段ではカウンタで定められた優先順位
に従って複数のリクエストのうち最も優先度の高い唯一
のリクエストを選択する。選択されたリクエストはパイ
プライン（６）などの各構成要素に送られると同時に、
どのプロセッサからのリクエストが選択されたかが第２
リクエスト保持手段に知らされる。そこで、第２リクエ
スト保持手段では保持しているリクエストのうち選択さ
れたブＯセッサに対応するリクエストを消去する．次の
リクエスト選択のとき、第２リクエスト保持手段内のリ
クエストが全て消去されていなければ、再度第２リクエ
スト保持手段内に保持されているリクエストがリクエス
ト選択手段に送られる。

リクエスト選択は第２リクエスト保持手段内に保持され
ているリクエストが全て消去されるまで続けられる。

一方、第２リクエスト保持手段に保持されているリクエ
ストがリクエスト選択手段に送られる間、各ブ０セッサ
から出されているリクエストは第１リクエスト保持手段
にセットされる。リクエスト選択の時、第２リクエスト
保持手段内のリクエストが全て消去されている場合、第
１リクエスト保持手段の内容が第２リクエス１・保持手
段にコピーされ、第１リクエスト保持手段の内容は消去
ざれる。以降のリクエスト道択には上記の動作が繰返さ
れる。

このように４１１威したことにより、時間的に先に発行
されたリクエストを優先して処理することが可能となり
、リクエストの追い越しを防止し、１つのプロセッサが
長時間待たされることを回避することができる。

（実施例） 第１図は、本発明の基本的な構戒の一実浦例を示したブ
ロック図である。図示の構成は、第４図に示されている
従来の主記憶アクセスリクエスト選択＠置の構成例を改
良したものとして示している。従って、参照番号２から
８で示されている構成要素は、両図において共通に用い
ている。しかし、第１図における優先順位回路２ａでは
バンクピジーまたはロック検出によるリクエスト抑止手
段が除去され、リクエスト抑止手段はリクエスト順序制
御回路１に移されている。

また、第１図において、新たに付加された回路がリクエ
スト順序１１１ＪＩ！１回路１である。リクエスト順序
制御回路１は、時間的に先に発行されたリクエストを優
先的に優先順位制御回路１に送る機構である。リクエス
ト順序制御回路１内にはリクエスト保持レジスタＡ１２
とリクエスト保持レジスタ８１３の２つの保持レジスタ
があり、各々のリクエスト保持レジスタは各プロセッサ
毎に対応した数のフリップ７ロップで構戒されている。

これらのリクエスト保持レジスタＡ１２．８１３によっ
てリクエストを保持し、リクエストの順序を保証する。

また、リクエスト順序制御回路１には、リクエスト停止
＠路１０とリクエストセレクタ１１が設けられている。

以上の構成において、２台以上のプロセッサから同時に
リクエストが発行された場合、各プＯセッサからのリク
エストは各々のプロセッサに対応するリクエスト受信レ
ジスタ３を経由してリクエス１・順序制御回路１に送ら
れる。リクエスト順序制御回路１において、この時点で
保留されているリクエストが存在しなければ、各ブＯセ
ッサからのリクエストは同時に優先順位制御回路２ａに
送られる。同時に、リクエスト順序ｌＩｊｌＪＩＤ回路
１内では、リクエスト保持レジスタＢ１３内のリクエス
トを出したプロセッサに対応するフリップフロツブがセ
ットされる。

優先順位制御回路２ａでは、優先順位カウンタ４で定め
られた優先順位に従って複数のリクエストから唯一のリ
クエストを選択する。選択されたリクエストはパイプラ
イン６などの各構成要素に送られると同時に、信号Ｉｍ
９を経由してどのプロセッサからのリクエストが選択さ
れたかがリクエスト順序制御回路１に通知される。通知
されたリクエストに対応するフリップ７ロップはリセッ
トされる。

次のリクエスト選択のとき、リクエスト保持レジスタ８
１３のフリップフロップが全てリセットされていなけれ
ば、リクエスト保持レジスタＢ１３に残っているリクエ
ストが優先順位制御回路２ａに送られる。そして、再び
同様のリクエスト選択がリクエスト保持レジスタ８１３
のフリップフロップが全てリセットされるまで続けられ
、この間はリクエスト保持レジスタＢ１３でセットされ
ているリクエス１・が侵先順位制御回路２ａに送られる
。

一方、リクエスト保持レジスタ８１３からのリクエスト
が優先順位制御回路２ａに送られる間、各プロセッサか
ら出されているリクエストはリクエスト保持レジスタＡ
１２にセットされる。リクエスト選択の時、リクエスト
保持レジスタＢ１３の７リップフロップが全てリセット
されている場合、リクエスト保持レジスタＡＩ２の内容
がリクエスト保持レジスタ８１３にコピーされ、リクエ
スト保持レジスタＡＩ２の全てフリツプ７ロツブはリセ
ットされる。以降のリクエスト選択には上記の動作が繰
返される。

このように、リクエス｛・保持レジスタＡ１２，８１３
を含むリクエスト順序１１１Ｊｌ１］回路１を新たに設
けることにより、時間的に先に発行されたリクエストを
優先して処理することができる。

第２図は、第１図に示される本発明の構或例において各
プロセッサからのリクエストの発行、処理状態をＷ藺順
に示した図である。なお、第２図で使われている記弓は
第５図で示されている記号と全く同じ意味である。以下
に本発明の構成例における動作を時間毎に説明する。

ＴＯ＝プロセッサＰ２とプロセッサＰ３が同時にリクエ
ストを発行する。このとき、プロセッサＰ２の方が優先
順位が高いので、プロセッサＰ２　　　　のリクエスｌ
・が選択される。

丁１：継続的にプロセッサＰ３からのリクエストは発行
され続けている。さらにこの時点で、プロセッサＰ１か
らリクエストが発行される。このとき、プロセッサＰ１
の方が優先順位は高いが、プロセッサＰ３のリクエスト
の方が先に発行されているので、プロセッサＰ３のリク
エスＩ・が選択され、ブ０セッサＰ１のリクエストき待
たされる。従って、第５図の従来例のようなリクエスト
の追い越しはこの時点で生じない。

Ｔ２　：ＩＫ１続的にプロセッサＰ１からのリクエス１
・は発行され続けている。さらにこの時点で、プロセッ
サＰＯからリクエストが発行される．このとき、プロセ
ッサＰＯの方が優先順位は高いが、プロセッサＰ１のリ
クエストの方が先に発行されているのでプロセッサＰ１
のリクエストが選択され、プロセッサＰＯのリクエス１
・は待たされる． Ｔ３：継続的にブＯセッサＰＯからのリクエス１・は発
行され続けている。この時点でブＯセッサＰＯのリクエ
スト以外に待たされているリクエストは存在しないので
、ブＯセッサＰＯのリクエストが選択される。

このように、時間的に先に発行されたリクエストが優先
されることにより、リクエストの追い越しを防止し、１
つのプロセッサが長時間待たされることを回避すること
ができる。

第３図はＷＪ１図の４Ｍ戊の詳細を具体的に示した回路
図である。第３図において、１はリクエスト順序制御回
路、２ａは優先順位制御回路である。

リクエスト順序制御回路１は各プロセッサからの主記憶
アクセクリクエストを受取り、決められた順番に従って
そのリクエストを優先順位ｌｖＩｔｌ１回路２ａに送る
。優先順位制御回２８２ａでは唯一のリクエストが選択
され、選択結果は次の構成要素に送られると共に、リク
エスト順序制御回路１にも信号！ｉ１９を経由してフィ
ードバックされる。以下に、リクエスト順序制御回路１
の内部構或について説明する。

各プロセッサから送られてくるリクエスト低目はまずＡ
ＮＤ回路１６に入力される。ＡＮＤ回路１６のもう一方
の入力はリクエスト停止回路１０からの信号線であり、
リクエスト停止回路１０でリクエストの停止が決定され
た場合、ＡＮＤ回路１６でリクエストは止められる。リ
クエスト停止の条件としては次の条件が挙げられる。

（１）バンクビジー状態であるバンクをアクセスしよう
とした時。

｛２｝ロックをかけたプロセッサ以外のプロセッサがそ
のロックされた主記憶領域をアクセスしようとした時。

従って、リクエスト停止回路１０には、バンクアドレス
、ロックアドレス、ビジーパンクアドレスの各信号が入
力されている． ＡＮＤ回路１６を通過したリクエストはリクエストセレ
クタ１１にも送られる。リクエストセレクタ１１はリク
エスト保持レジスタＢ１３にリクエストが残されていな
い場合、ＡＮＤ回ｉ１１６を通過したリクエストを直ち
に優先順位制御回路２ａに送るためのセレクタである。

リクエストセレクタ１１の切換はＮＯＲ回路１８の出力
によって決定される。ＮＯＲ回路１８はリクエスト保持
レジスタＢ１３にリクエス１・が残されていない場合、
つまり、リクエスト保持レジスタ８１３内のすべてのフ
リップフロツプ１５がリセットされている場合に信号を
出し、リクエストセレクタ１１を切換えてＡＮＤ回路１
６を通過したリクエストを直ちに優先順位＄８１１回路
２ａに送る。

リクエスト保持レジスタＡＩ２に保持されているリクエ
ストは、次のリクエス１・選択が起動される時にリクエ
スト保持レジスタＢ１３にリクエストが残されていなけ
れば、リクエストレジスタＢ１３にコピーされる。コピ
ー終了後、リクエスト保持レジスタＡ１２内の全てのフ
リップフロツプ１４はリセットされる．リクエス１・保
持レジスタＡ１２に保持ざれているリクエストはＡＮＤ
回路１７を経由してリクエスト保持レジスタＢ１３に送
られる。ＡＮＤ回路１７はリクエスト選択起動信号を受
取り、かつリクエスト保持レジスタＢ１３にリクエスト
が残されていないことを示すＮｏＲ回路１８からの信号
を受取った場合のみ、リクエストを通す。ＡＮＤ回路１
７に対する条件はＡＮＯ回路１９で生或される。

リクエスト保持レジスタＢ１３にリクエストが残ってい
る場合、リクエストセレクタ１１はリクエスト保持レジ
スタＢ１３からのリクエストを優先順位制御回路２ａに
送る。優先順位ｌｌｌｌＪ１ｍ！１回路２ａは優先順位
カウンタ４で指定される優先順位に従ってリクエストを
唯一つだけ選択する。

唯一つだけ選択されたリクエストは信号線９を経由して
リクエスト保持レジスタＢ１３に通知される。リクエス
ト保持レジスタ８１３では、優先順位制御回路２ａ出選
択されたリクエストの発行元であるプロセッサに対応す
るフリップフロップ１５がリセットされる。

このようにして、リクエスト保持レジスタＢ１３内に保
持されているリクエストはリクエストが選択される毎に
リセットされ、ついにリクエスト保持レジスタＢ１３内
のリクエストが空きになると、リクエスト保持レジスタ
ＡＩ２内のリクエストが再びリクエスト保持レジスタＢ
１３にコピーされる。さらに、コピーされたリクエスト
保持レジスタＡ１２のリクエストが空きであれば、リク
エストセレクタ１１はＡＮＤ回路１６からのリクエスト
を直接に優先順位制御回路２ａに送る。

（発明の効果） 以上の説明から明らかなように、本発明によれば、多数
のプロセッサから発行される主記憶アクセスリクエスト
を選択する場合ににおいて、時間的に先に発行されたリ
クエストを優先する手段を設けたため、リクエストの追
い越しを防止し、１つのプロセッサが長時＠待たされる
ことを回避することができる。

従って、ロック解除のリクエストを出しているプロセッ
サが優先順位が上がるまで長時間待たされることによっ
て発生する無駄なリクエストが何回も行なわれることは
なくなり、システム全体の性能低下を未然に防止するこ
とが可能になる。

【図面の簡単な説明】

第１図は本発明の基本的な構或の一実施例を示すブロッ
ク図、第２図は第１図の構成例における各プロセッサか
らのリクエストの発行、処理タイミングを示す説明図、
第３図は第１図の実施例の詳細な構成の一例を示す回路
図、第４図は従来の主記憶アクセスリクエス１・選択装
置の構成を示すブロック図、第５図は第４図に示される
従来構成における各プロセッサからのリクエストの発行
、処理タイミングを示す説明図である． １・・・リクエスト順序制御回路、２ａ・・・優先順位
！ＩＪａ１１回路、３・・・リクエスト受信レジスタ、
４・・・優先順位カウンタ、５・・・ロックレジスタ、
６・・・パイプライン、７・・・バンクビジー表示回路
、８・・・主記憶アクセス起動レジスタ、１１・・・リ
クエストセレクタ、１２・・・リクエスト保持レジスタ
Ａ１１３・・・リクエス１・保持レジスタＢ． なお、図中、同一または相当部分は同一記号で示す。

Claims (1)

1. 【特許請求の範囲】 複数のプロセッサと、各プロセッサから共通にアクセス
   可能な主記憶装置とを備え、各プロセッサから任意の時
   刻で発生される主記憶アクセスリクエストに対する競合
   を制御するマルチプロセッサシステムのアクセスリクエ
   スト選択方式において、 各プロセッサから発生される主記憶アクセスリクエスト
   の優先順位を一定時間毎に動的に変化させ、その優先順
   位に従って複数のプロセッサから同時に発行されている
   リクエストのうち、唯一のリクエストを選択すると共に
   、選択されたリクエストを表わす通知信号を出力するリ
   クエスト選択手段と、各プロセッサから任意の時刻に発
   行されるリクエストを一時的に保持しておく第１リクエ
   スト保持手段と、この第１リクエスト保持手段に保持さ
   れていたリクエストを受取って保持すると共に、保持し
   ているリクエストを前記リクエスト選択手段に送り、さ
   らに保持していたリクエストの中で前記通知信号で示さ
   れるリクエストを消去し、さらに保持されていたリクエ
   ストがなくなった時に再び前記第１リクエスト保持手段
   に保持されていたリクエストを受取る第２リクエスト保
   持手段と、前記第１、第２リクエスト保持手段の両方に
   リクエストが保持されていない時に各プロセッサからの
   リクエストを直接に前記リクエスト選択手段に転送する
   リクエスト切換手段とを具備することを特徴とするマル
   チプロセッサシステムの主記憶アクセスリクエスト選択
   方式。