JPH0628247A

JPH0628247A - 動的に再配置されるメモリバンク待ち行列

Info

Publication number: JPH0628247A
Application number: JP4017642A
Authority: JP
Inventors: Chitta L Rao; チッタ、ラクシミナライナ、ラオ; Steven W White; スティーブン、ウェイン、ホワイト
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-03-04
Filing date: 1992-02-03
Publication date: 1994-02-04
Anticipated expiration: 2011-02-07
Also published as: JPH0812635B2; US5276838A

Abstract

(57)【要約】【目的】個別のＦＩＦＯバンク待ち行列に機能上等価
でありながら、単一のＢＳＭバンク待ち行列方式よりも
ごくわずかに多くのハードウエアを要するにすぎないよ
うな待ち行列構造を提供する。【構成】本発明の待ち行列構造は、待ち行列位置と所
与のＢＳＭ内のバンクとの間に１対１対応が存在する、
（ＢＳＭ当たり１の）「自己前進」ＷＡＩＴＩＮＧ待ち
行列を使用する。しかし、位置／バンクの関係は、位置
がビジーバンクについてだけ存在するように動的に管理
され、それにより、ＢＳＭ当たり１の待ち行列を維持し
ながら、事実上、バンク当たりのＦＩＦＯ待ち行列を付
与する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データプロセッサメモ
リのアーキテクチャ、より詳しくは、単一の基本記憶モ
ジュール待ち行列と近似的なコストで個々のバンク待ち
行列の性能を付与する待ち行列構造に関する。

【０００２】

【従来の技術およびその課題】ほとんどの大型データ処
理システムでは、プロセッサの速度はメモリのサイクル
時間の数倍も高速である。メモリの平均待ち時間を低減
するために、メモリは通常、さらに多数のバンクに部分
分割される基本記憶モジュール（ＢＳＭ）に区分化され
ている。ＢＳＭの有効数が、プロセッササイクル当たり
の可能な記憶アクセス数を限定する。ＢＳＭ内のバンキ
ングの程度は、メモリ対プロセッサのサイクル時間の比
によって決定される。例えば、各個が１２８バンクを備
えた６４のＢＳＭが存在するかもしれない。

【０００３】大半の高性能設計では、アドレスビットは
以下のフィールドに分割されている。

【０００４】｜チップ選択・チップ内アドレス｜バンク
選択｜ＢＳＭ選択｜バイトインデックス｜上記の最初の３のフィールドはメモリワードを選択し、
最低位の数ビットはワード内のバイトを選択する。記憶
要求のＢＳＭユニット全体にわたる均一な分配を得よう
とする場合、ＢＳＭ選択フィールドは、通常、ワードを
選択する最低位数ビットである。バンク選択ビットは、
その次に高位のビット集合である。残りのビットは、チ
ップ内のロケーションおよびバンク内のチップを選択す
る。例示のために、４バイトワード、６４のＢＳＭおよ
び各ＢＳＭで１２８バンクを使用する基本メモリ設計を
前提とする。

【０００５】多数の別個のバンクが存在するので、所与
の要求はまず間違いなく「レディ」バンクに向けられ
る。待ち行列は、以前の要求によりまだビジー（アクテ
ィブ）であるバンクのメモリ要求をバッファするために
維持されている。ＩＢＭＳ／３７０のアーキテクチャ
要求条件は、記憶参照シーケンスに関して、各バンクの
前に個別の先入れ先出し方式（ＦＩＦＯ）待ち行列を置
くことによって満たすことができた。（６４のＢＳＭの
それぞれで１２８バンクといった）極めて多数のバンク
を備えたシステムでは、ハードウエアのコストのために
そうした個別のバンク待ち行列は非実際的なものとな
る。従って、通常は、ＢＳＭにつき単一のＦＩＦＯ待ち
行列が実施されており、それにより性能を犠牲にしてハ
ードウエアのコストを大幅に低減している。先頭エント
リがその要求バンクがアクティブであるために待たなけ
ればならない場合、その待ち行列にある以降の全部のメ
モリ要求も待たされることになる。ＢＳＭ当たり多数の
バンクを持っているシステムでは、待機している要求の
ほとんどはレディとなっているバンクに対するものであ
る。しかし、プロセッサのサイクルの点から、メモリア
クセス時間を高めるという傾向のために、待ち行列の先
頭にある単一のブロック化エントリは、多数のサイクル
の間、多数の要求を遅らせるかもしれない。

【０００６】従って、本発明の目的は、個別のＦＩＦＯ
バンク待ち行列に機能上等価でありながら、単一ＢＳＭ
待ち行列方式よりもごくわずかに多くのハードウエアを
要するにすぎないような待ち行列構造を提供することで
ある。

【０００７】

【課題を解決するための手段及び作用】本発明に従え
ば、待ち行列位置と所与のＢＳＭ内のバンクとの間に１
対１対応が存在する、（ＢＳＭ当たり１の）「自己前
進」ＷＡＩＴＩＮＧ待ち行列を使用する待ち行列構造が
付与される。しかし、位置／バンクの関係は、（待ち行
列を必要とする唯一のバンクである）ビジーバンクにつ
いて（有効）位置だけが存在するように動的に管理さ
れ、それにより、ＢＳＭ当たり１の１６エレメント待ち
行列（例えば、１２８バンク）を維持しながら、事実
上、バンク当たりのＦＩＦＯ待ち行列を与えることにな
る。

【０００８】システム性能は、本発明の実施の原動力で
ある。スイッチ、メモリおよび関係する待ち行列の集約
的なコンピュータモデル化は、（ＢＳＭ入力での）提起
した待ち行列構造の使用がアプリケーションのクラスに
ついてメモリ平均待ち時間を著しく（約３０％）低減す
ることを示している。

【０００９】

【実施例】図面について説明する。図１は、各個が互い
に独立してかつ並列で動作する多数の中央処理装置（Ｃ
ＰＵ）１０を含む、高性能データ処理システムを示す。
ＣＰＵ１０の各個は、複数のメモリデバイス（すなわ
ちＢＳＭ）１２の１つに対するアクセスを時に応じて要
求する。各ＣＰＵ１０は経路１４を有しており、各メ
モリデバイス１２は経路１６を有する。メモリデバイス
１２にアクセスを要求するＣＰＵ１０は、自己の経路
１４を、交換網１８によって、要求されたメモリデバイ
ス１２の経路１６に接続させる。

【００１０】アドレスは、ＢＳＭ番号およびＢＳＭ内ア
ドレスに区分できる。このＢＳＭ番号は、正しい接続を
決定するために交換網１８によって使用される。「ＢＳ
Ｍ内アドレス」は、まったく修正されることなく交換網
１８を通じて渡される。現在のシステムでは、ＢＳＭ値
は単に１群のアドレスビットである。残りのビットが
「ＢＳＭ内アドレス」である。これは、大幅に修正され
たモジュロ２ｎ計算に等しい。

【００１１】図１に示すように、スイッチ１８からのＢ
ＳＭ内アドレスおよびデータは、選択されたＢＳＭ１
２内のＢＳＭ待ち行列論理２２に供給される。アドレス
は、Ｍのバンク２４のうちの１バンクを選択するアドレ
ス解読／バンク選択論理２２に渡され、ＢＳＭ待ち行列
論理からのデータは選択されたバンクに読み込まれる。
逆に、選択されたＢＳＭから読み出されるデータは、同
様にアドレス指定されるが、そのデータはスイッチ１８
に直接読み出され、要求側プロセッサ１０に供給され
る。

【００１２】図２は、１２８バンク記憶装置の通常のＢ
ＳＭ待ち行列論理２０を例示する。この待ち行列論理
は、１６段から成るＦＩＦＯレジスタ２６および、待ち
行列に入れられた要求を１２８バンク記憶装置に供給す
るための制御論理を含む。レジスタ２６に図示した番号
は、現在その待ち行列にある要求に対するバンクの番号
を表している。待ち行列制御論理２８は、特定のバンク
への要求がその待ち行列に入れられた順序で（バンク２
４に対応する）記憶装置２９に要求を行う。これらの要
求は受け入れられるか拒絶されるかのいずれかであり、
要求の受入れまたは拒絶はＢＳＭ待ち行列に返信され
る。ＢＳＭ待ち行列の先頭エントリが受け入れられた場
合、その待ち行列の他の全エントリは１位置ずつ前進す
る。ＢＳＭ待ち行列の先頭エントリが拒絶された場合
（バンクビジー）、その次のサイクルで再試行される。

【００１３】図３は、本発明の好ましい実施例に従っ
た、ＢＳＭ待ち行列論理２０の代替となる待ち行列構造
を示す。現在アクティブであるバンクへのメモリ要求
は、「ＷＡＩＴＩＮＧ待ち行列」３０に経路指定され
る。「ＷＡＩＴＩＮＧ待ち行列」の位置の数は、メモリ
サイクルにおけるプロセッササイクル数と同じである。
以下の説明のために、メモリ／プロセッサのサイクルは
１６とする。この前提により、後述する図４の実施例に
おける要求順序を維持するために使用される各レジスタ
には、４ビットが必要であることが決まる。

【００１４】ＷＡＩＴＩＮＧ待ち行列３０内のメモリ要
求の位置は、要求されたバンクのビジーサイクルで残っ
ているサイクル数を指示する。各サイクルにおいて、Ｗ
ＡＩＴＩＮＧ待ち行列３０のエントリは、１サイクルず
つ右側に桁送りされ、１サイクルずつレディに近づくに
つれてそのエントリによって要求されたバンクをマーク
する。本発明の第１の実施例では、「ブックキーピン
グ」回路３３の４：１６デコーダ３２が、ホールド／ロ
ード回路３４に入力される１６の出力ＳＥＬＥＣＴ０〜
ＳＥＬＥＣＴ１５のいずれかを生成する。どの出力がア
クティブであるかに応じて、ＮＥＷ待ち行列３６の先頭
エントリの全ビットは、ホールド／ロード回路３４を介
してＷＡＩＴＩＮＧ待ち行列３０の対応する位置に読み
込まれる。デコーダ３２は、１２８の４ビットカウンタ
３８から、４カウンタビットおよび１有効ビットから成
る５ビットカウンタ出力をその入力として受信し、カウ
ンタ３８は逆にＮＥＷ待ち行列３６からの８カウンタ選
択ビットによって制御される。この８ビットは７ビット
のデータおよび１有効ビットから成る。

【００１５】上述のように、当該位置の要求の存在を指
示する「有効」ビットが各エントリと関係する。ＷＡＩ
ＴＩＮＧ待ち行列３０の有効エントリが右端の位置（ス
ロット０）まで進むと、そのバンクが要求に対しレディ
となっていることが保証され、その要求はそのメモリに
ディスパッチされる。右端のスロットまで進んだエント
リがＦＡＬＳＥ有効ビットを持っている場合、ＷＡＩＴ
ＩＮＧ待ち行列によって要求されたバンクのいずれもレ
ディとならない。従って、有効な「新しい」ビットが使
用可能であり、デコーダ３２からのＳＥＬＥＣＴ０によ
ってＴＲＵＥであると指示された場合、その新しい要求
はただちにサービスされることが可能となる。

【００１６】マルチプレクサ３５は、ＷＡＩＴＩＮＧ待
ち行列３０の先頭エントリからのその有効ビットを使用
して、そのエントリまたはＮＥＷ待ち行列３６からの先
頭エントリのいずれをメモリバンクに供給すべきかを選
択する。ホールド／ロード回路３４内で、ＳＥＬＥＣＴ
０は、ビジーバンクに指定された要求が処理されないよ
うにするために、ＮＥＷ待ち行列３６の先頭エントリの
有効ビットと論理積をとることができる（図示せず）。
しかし、ＷＡＩＴＩＮＧ待ち行列３０がレディである要
求を持っている場合、有効な「新しい」エントリが「ホ
ールド／ロード」回路３４からＨＯＬＤ信号を生成し、
これがＮＥＷ待ち行列３６に次のサイクルで再試行させ
るようにする。

【００１７】ＨＯＬＤ信号が生成される他の条件は、Ｎ
ＥＷエントリが待ち行列に入れられなければならず（す
なわち、そのバンクがアクティブである）、ＷＡＩＴＩ
ＮＧ待ち行列３０がそのＮＥＷエントリが置換されるは
ずの位置に有効エントリをすでに持っている場合であ
る。これは、第１の要求がメモリがアクティブである要
求であり、第２の要求がＷＡＩＴＩＮＧ待ち行列にあ
り、第３の要求がＨＯＬＤ条件を生じるといった、バン
クのビジー時間内において同一のバンクに対して３の要
求を必要とする場合なので、ほとんどない例である。

【００１８】この設計の鍵は、ＷＡＩＴＩＮＧ待ち行列
３０における要求の位置と要求されたバンクのビジーサ
イクルで残っているサイクル数との間の関係を維持でき
ることである。カウンタセル４０の集合を用いて必要な
ブックキーピング情報を維持する方法は、図４に示され
ており、そのカウンタの１つが４ビットカウンタ４２を
含むものとして詳細に図示されている。これらのカウン
タは、Ｓｉｇｎｅｔｉｃｓ７４Ｆ１９１またはＴｅｘ
ａｓＩｎｓｔｒｕｍｅｎｔｓＳＮ７４１９１と同様
の設計の通常の４ビット可逆バイナリカウンタとするこ
とができる。各サイクルで、非ゼロ値を持つカウンタは
すべて、ＡＮＤゲート４４を通じてプロセッサによって
減分される。ＡＮＤゲート４４は、カウンタ４２の非ゼ
ロ値を検出するＯＲゲート４６によってイネーブルにさ
れる。従って、カウンタの値がゼロである場合は、減分
は生じない。値１５（バンクが開始されたサイクル後に
残っているビジーサイクル数）は、ＬＯＡＤｉがＴＲＵ
Ｅである場合にカウンタに非同期でロードされる。ＬＯ
ＡＤｉはバンクｉの要求が記憶装置によって受け入れら
れた場合にデコーダ４８によって表明される。カウンタ
４２とバンクとの間には、不変の１対１対応がある。従
って、Ｎのバンクを持ったシステムの場合は、Ｎのカウ
ンタが必要になる。メモリ要求がレディバンクにディス
パッチされると、バンク選択ビットがカウンタに経路指
定される。このバンク番号は対応するカウンタを選択す
るために使用される。その値は、その関係するバンクが
１５の付加サイクルでアクティブになることを指示する
ために１５に設定される。メモリサイクルがＭプロセッ
ササイクルであれば、初期カウンタ値は、ゼロに達する
ためにＭ−１の減分が必要となるように設定される。い
ずれの時点でも、カウンタ４２は、対応するバンクのビ
ジーサイクルに残っているサイクル数を指示する。ゼロ
値は、その関係するバンクがアクティブではないという
特殊な意味を有する。カウンタセル４０のうちのいずれ
かの４ビット出力は、４ビット幅ｘ１２８マルチプレク
サ４９によって選択される。マルチプレクサ４９を制御
する８のバンク選択ビットは、ＮＥＷ待ち行列３６（図
３）から得られる。この８ビットは、７選択ビットと１
有効ビットに分けられる。有効ビットは、マルチプレク
サ４９をイネーブルにするために使用され、また、図３
のデコーダ３２に入力される５ビットカウンタ出力を供
給するためにマルチプレクサの４ビット出力と結合され
る。

【００１９】前述のように、プロセッサにより生成され
たメモリ要求は、図１に示したスイッチ１８によって適
切なＢＳＭに経路指定される。正しいＢＳＭは、通常、
アドレスビットのうちの少数を調べることによって決定
される。アドレスビットの類似フィールドは、バンクを
選択するためにＢＳＭ内で使用される。スイッチ１８に
よってＢＳＭに経路指定された新しいメモリ要求は、初
めに、ＮＥＷ待ち行列３６に入れられる。要求は、待ち
行列が空であれば先頭エントリに置かれる。先頭エント
リについてＨＯＬＤ信号が生成されていない限り、ＮＥ
Ｗ待ち行列３６の各エントリは各サイクルごとに前進す
ることができる。先頭エントリのバンク選択ビットは、
関係するカウンタ値を選択するために使用される。カウ
ンタ値は、デコーダ３２により、１６の選択線の（多く
ても）いずれかに復号される。要求されたバンクがその
ビジーサイクルに２サイクルを残している場合、ＳＥＬ
ＥＣＴ２がＴＲＵＥになる。ＷＡＩＴＩＮＧ待ち行列の
右側エントリから３番目のエントリが空である場合、Ｎ
ＥＷ待ち行列からの先頭エントリがこのスロットにゲー
トされる。そのスロットが埋まっていれば、ＮＥＷ待ち
行列３６の先頭エントリは保留され、再試行される。Ｔ
ＲＵＥである特定のＳＥＬＥＣＴ線が、新しいエントリ
をＷＡＩＴＩＮＧ待ち行列３０のどの位置に置くかを決
定する。ＳＥＬＥＣＴ０は、その新しいエントリがレデ
ィバンクの対象となっている、特殊な例として扱われ
る。ＷＡＩＴＩＮＧ待ち行列３０が右端のスロットに有
効エントリを持っていない場合、新エントリはそのバン
クにディスパッチされる。そうでなければ、ＮＥＷ待ち
行列の先頭エントリは保留され、次のサイクルで再試行
される。

【００２０】ブックキーピング／ＳＥＬＥＣＴ線生成の
さらに効率的な実施が、図５の「タグ」シフトレジスタ
５０およびコンパレータの集合５２である。図３のホー
ルド／ロード回路３４、ＷＡＩＴＩＮＧ待ち行列３０お
よびマルチプレクサ３５が記憶装置に供給する要求を選
択すると、そのバンク番号（タグ）がシフトレジスタ５
０の左端位置に置かれる。シフトレジスタ５０は、メモ
リバンクのビジーサイクルのサイクル数と同じ段数を有
するように規定される。シフトレジスタは各サイクルご
とに１位置ずつ右側に桁送りさせる。しかし、ＷＡＩＴ
ＩＮＧ待ち行列３０と同様に、このＴＡＧシフトレジス
タ５０のタグ（すなわちバンク番号）の位置は、関係す
るメモリバンクのビジーサイクルで残っているサイクル
数を指示する。例えば、図示の例では値「６７」が第６
の位置にあるので、バンク番号「６７」はさらに６サイ
クルの間ビジーである。従って、選択線生成は単に、Ｎ
ＥＷ待ち行列３６の先頭エントリからのバンク選択ビッ
トとシフトレジスタ５０のタグの全部を比較するという
ことになる。位置Ｎのエントリとの一致があった場合、
その要求はさらにＮサイクルの間ビジーであるバンクに
指定される。従って、ＳＥＬＥＣＴＮはＴＲＵＥとして
表明されるはずである。ＮＥＷ待ち行列３６、ＨＯＬＤ
／ＬＯＡＤ回路３４、ＮＥＷ待ち行列３６およびその他
のハードウエアは、図４のカウンタ／デコーダ回路をＴ
ＡＧシフトレジスタ５０およびコンパレータ５２に代替
させることによって影響されない。ブックキーピングお
よびＳＥＬＥＣＴ線生成のこれらの２形式への入出力は
同一である。

【００２１】「ホールド／ロード」回路３４は、図６に
例示するが、ＮＥＷ待ち行列３６（図３）の先頭エント
リのＨＯＬＤ信号を生成し、ＮＥＷエントリがＷＡＩＴ
ＩＮＧ待ち行列３０の有効エントリの上位にロードされ
ないようにする。通常、ＳＥＬＥＣＴ線は新エントリを
ＷＡＩＴＩＮＧ待ち行列３０にロードするために使用さ
れるが、１のＴＲＵＥ値ＳＥＬＥＣＴ線が、すでに有効
エントリを持っているＷＡＩＴＩＮＧ待ち行列の位置に
対応する場合には、そのＳＥＬＥＣＴ線はＮＥＷ待ち行
列エントリをＷＡＩＴＩＮＧ待ち行列にロードすること
を禁止される。この場合、ＴＲＵＥ値はＨＯＬＤ線に置
かれる。

【００２２】図６について説明すれば、「ホールド／ロ
ード」回路３４は、デコーダ３２からの１６の復号ＳＥ
ＬＥＣＴ信号を受け入れ、ＳＥＬＥＣＴ１〜ＳＥＬＥＣ
Ｔ１５を使用してＮＥＷ待ち行列３６のエントリをＷＡ
ＩＴＩＮＧ待ち行列３０にロードする。これはＡＮＤゲ
ート６２１〜６２１５によって行われるが、これらのう
ちの１だけがＳＥＬＥＣＴ線によってイネーブルにされ
る。ＡＮＤゲート６２１〜６２１５はまた、各自のイン
バータ６３１〜６３１５を介して対応するＷＡＩＴＩＮ
Ｇ待ち行列位置への有効ビットを入力として受信するこ
とにも留意されたい。従って、特定のＷＡＩＴＩＮＧ待
ち行列位置ｉの有効ビットがＴＲＵＥである場合、対応
するＡＮＤゲート６２ｉは抑止され、ＮＥＷ待ち行列エ
ントリのＷＡＩＴＩＮＧ待ち行列へのロードを防止す
る。

【００２３】ＳＥＬＥＣＴ線および有効ビットはまた、
ＡＮＤゲート６４１〜６４１５を通じても供給され、そ
の出力は、ＷＡＩＴＩＮＧ待ち行列位置の矛盾を指示す
るＨＯＬＤ信号を生成するためにＯＲゲート６５によっ
て結合される。別のＡＮＤゲート６６は、ＳＥＬＥＣＴ
０信号およびＷＡＩＴＩＮＧ待ち行列の先頭エントリか
らの有効ビットを入力として受信し、上述と同様、２の
レディ要求間の矛盾を指示するＨＯＬＤ信号を生成す
る。２のＨＯＬＤ信号は、ＮＥＷ待ち行列への単一のＨ
ＯＬＤ信号出力を供給するために第２のＯＲゲート６７
で結合される。

【００２４】本発明に従ったこの待ち行列構造は、個別
のＦＩＦＯバンク待ち行列と機能的に等価である。所与
のバンクに対する全要求のＦＩＦＯ方式の取扱いは、要
求が他の要求を「渡す」ことができる唯一の方法がＷＡ
ＩＴＩＮＧ待ち行列に入れられた要求を妨げることによ
ることであるという点を認めることによって認識でき
る。ＷＡＩＴＩＮＧ待ち行列の（迂回されるかもしれな
い）いずれのエントリの場合も、関係するバンクカウン
タ（またはタグシフトレジスタの位置）は非ゼロであ
る。従って、（ＷＡＩＴＩＮＧ待ち行列にある要求と同
一のバンクに対する）新しい要求がＷＡＩＴＩＮＧ待ち
行列エントリを迂回しようとした場合、非ゼロのカウン
タ／タグ値が認められ、その非ゼロ値は、そのカウンタ
に関係するバンクについて待機している要求のＷＡＩＴ
ＩＮＧ待ち行列の位置を指示する。新エントリは、同一
バンクに向かうエントリをすでに有するＷＡＩＴＩＮＧ
待ち行列の位置に送られるので、ホールド／ロード回路
は新エントリのロードを防止し、ＨＯＬＤ信号を生成す
る。この例外は、新エントリがＷＡＩＴＩＮＧ待ち行列
３０の先頭エントリと同一のバンクに向かう場合であ
る。ゼロのカウンタ値が存在するが、ＷＡＩＴＩＮＧ待
ち行列の先頭エントリは（マルチプレクサ３５によっ
て）優先権を与えられており、新エントリは保留され、
それによりＷＡＩＴＩＮＧ待ち行列エントリを迂回する
ことを妨げられる。従って、提起した待ち行列機構は、
非ビジーバンクでの待ち行列のログ（上述の例では所与
の時間に１２８バンクのうち多くて１６がビジーとなり
得る）または関係する多重化／経路指定回路の全部を必
要とせずに、各バンクの個別のＦＩＦＯ待ち行列と同じ
機能を付与する。

【００２５】上述の実施例は、各ＢＳＭに対して１サイ
クル当たり１要求だけが行われることを前提としてい
る。１サイクル当たり２の要求が可能な場合、図示した
ハードウエアの全部（４ビットカウンタを除く）が単に
複製されるだけである。ＢＳＭ待ち行列領域との間の
（１サイクル当たり）２の要求の入出力は、各個が各自
のＷＡＩＴＩＮＧ待ち行列を備えたストリームとしてみ
なすことができる。ＮＥＷ待ち行列３６の先頭エントリ
間の７ビット比較は、ＮＥＷ待ち行列が同一バンクに向
けられた２の要求を同時に供給しないようにするために
行わなければならない。また、ＷＡＩＴＩＮＧ待ち行列
に向かうＮＥＷエントリと他のＷＡＩＴＩＮＧ待ち行列
の対応するエントリとの間の７ビット比較も、その２の
ＷＡＩＴＩＮＧ待ち行列が共に所与のバンクが「予約さ
れている」と「考える」要求を持たないようにするため
に行わなければならない。これは、そうした矛盾が生じ
た場合、他方の現在エントリの位置が必ずアクティブの
ＳＥＬＥＣＴ線によって指示されていることがわかるの
で、容易に行える検査である。

【００２６】本発明は、各バンクの前にＦＩＦＯ待ち行
列を機能的に置くことにより所与のワードに対する要求
順序を維持しながらも、ＢＳＭ当たり単一待ち行列方式
に比べて最低限のハードウエアの増量のみを必要とする
メモリアーキテクチャを提供する。ＷＡＩＴＩＮＧ待ち
行列のエントリ位置と、関係するバンクが使用可能とな
るまでの残りのサイクル数との間の１対１対応によっ
て、ＦＩＦＯ順序は所与のバンクについての全要求内で
維持できる。しかし、待ち行列エントリ位置と実際のバ
ンク番号との間の関係の一定の変化によって、ＷＡＩＴ
ＩＮＧ待ち行列エントリは、事実上、ビジーであるバン
クだけの前に置かれるＦＩＦＯ待ち行列として動作する
ように動的に再配置される。

【図面の簡単な説明】

【図１】各ＢＳＭがＭバンクを備えたＮのＢＳＭを含む
メモリサブシステムのブロック図。

【図２】通常のＢＳＭ待ち行列を例示するブロック図。

【図３】本発明の好ましい実施例に従ったメモリ待ち行
列のブロック図。

【図４】図３に示すカウンタのブロック図。

【図５】ブックキーピングおよびＳＥＬＥＣＴ線生成機
能の効率的な実施の論理図。

【図６】図３に示すメモリ待ち行列で使用される「ホー
ルド／ロード」回路の論理図。

【符号の説明】

３０ＷＡＩＴＩＮＧ待ち行列３４ＨＯＬＤ／ＬＯＡＤ回路３３「ブックキーピング」回路３２３：１６デコーダ３８１２８の４ビットカウンタ３６ＮＥＷ待ち行列３５マルチプレクサ

───────────────────────────────────────────────────── フロントページの続き (72)発明者スティーブン、ウェイン、ホワイトアメリカ合衆国テキサス州、オースチン、ウェストカーク、ドライブ、9104

Claims

【特許請求の範囲】

【請求項１】基本記憶モジュールの各個がさらにメモリ
バンクに分割されている多数の基本記憶モジュールを有
するデータ処理メモリシステムにおいて、単一の基本記
憶モジュール待ち行列とほぼ同じコストで個別バンク待
ち行列の性能を付与する改良された待ち行列構造であっ
て、対応する記憶モジュールの現在アクティブなメモリバン
クのメモリ要求を格納するための前記基本記憶モジュー
ルの数と等しい数の多数のＷＡＩＴＩＮＧ待ち行列手段
であり、前記メモリ要求は各プロセッササイクルごとに
前記ＷＡＩＴＩＮＧ待ち行列手段内を進められるもので
ある前記ＷＡＩＴＩＮＧ待ち行列手段と、メモリバンクに供給されるかまたは前記ＷＡＩＴＩＮＧ
待ち行列手段に入れられるメモリ要求を受信するための
ＮＥＷ待ち行列手段であり、前記メモリ要求はバンク選
択ビットを含むものである前記ＮＥＷ待ち行列手段と、選択されたバンクに対応するＳＥＬＥＣＴ出力を生成す
るための前記ＮＥＷ待ち行列手段の先頭エントリから前
記バンク選択ビットを受け取るブックキーピング手段
と、選択された位置がすでに占有されている場合は前記ＷＡ
ＩＴＩＮＧ待ち行列手段の選択位置にメモリ要求をロー
ドするか、または、メモリバンクに要求を供給するか、
または、前記選択位置で矛盾が検出された場合は前記Ｎ
ＥＷ待ち行列手段へのＨＯＬＤ信号を生成するための前
記ＳＥＬＥＣＴ出力に応答するホールド／ロード回路で
あり、前記ＮＥＷ待ち行列手段は次のプロセッササイク
ルで再試行するために前記ＨＯＬＤ信号に応答するもの
である前記ホールド／ロード回路とを含むことを特徴と
する待ち行列構造。
【請求項２】請求項１記載の待ち行列構造であって、前
記ブックキーピング手段が、前記ＷＡＩＴＩＮＧ待ち行列の各個のための基本記憶モ
ジュール内の前記メモリバンクの数と等しい数の多数の
カウンタであり、前記カウンタのいずれかがカウント出
力を供給するために前記バンク選択ビットによって選択
されるものである前記多数のカウンタと、前記ＳＥＬＥＣＴ出力を生成するために前記カウント出
力に応答するデコーダ手段とを含むことを特徴とする待
ち行列構造。
【請求項３】請求項１記載の待ち行列構造であって、前
記ブックキーピング手段が、要求がメモリバンクに供給されるために選択された時に
バンク番号を受信するためのＴＡＧシフトレジスタ手段
と、前記ＳＥＬＥＣＴ出力を生成するために前記ＮＥＷ待ち
行列手段からの前記バンク選択ビットと前記段の内容と
を比較するための前記ＴＡＧシフトレジスタの段と等し
い数の多数のコンパレータ手段とを含むことを特徴とす
る待ち行列構造。