JPH02297645A - データ処理装置およびその高速待ち行列機構 - Google Patents

データ処理装置およびその高速待ち行列機構

Info

Publication number
JPH02297645A
JPH02297645A JP2105473A JP10547390A JPH02297645A JP H02297645 A JPH02297645 A JP H02297645A JP 2105473 A JP2105473 A JP 2105473A JP 10547390 A JP10547390 A JP 10547390A JP H02297645 A JPH02297645 A JP H02297645A
Authority
JP
Japan
Prior art keywords
line
memory
data
address
main memory
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.)
Pending
Application number
JP2105473A
Other languages
English (en)
Inventor
Philip G Emma
フリップ・ジョージ・エマ
Joshua W Knight
ジョシュア・ウィルソン・ナイト
James H Pomerene
ジェームス・ハーバート・ポメレン
Rudolph N Rechtschaffen
ルドルフ・ノーザン・リチェスチャフェン
Frank J Sparacio
フランク・ジョン・スパッシオ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH02297645A publication Critical patent/JPH02297645A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/76—Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
    • G06F7/78—Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor
    • G06F7/785—Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0804—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with main memory updating
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
    • G06F12/0815—Cache consistency protocols
    • G06F12/0817—Cache consistency protocols using directory methods
    • G06F12/0828—Cache consistency protocols using directory methods with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)
  • Multi Processors (AREA)

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、キャッシュ・メモリを備えたデータ処理シス
テムに関し、より具体的にはこうしたデータ処理システ
ムがより高速でかつより効率的に動作するための待ち行
列バッファ機構に関する。
Ｂ、従来の技術 複数のプロセッサが１つの主記憶装置を共用するデータ
処理システムでは、各プロセッサにそれぞれキャッシュ
・メモリを設けることがしばしば行なわれる。こうした
キャッシュ・メモリは、プロセッサの速度を向上させ、
また主記憶装置上のトラフィック負荷を軽減させる。プ
ロセッサによって生成される取出しトラフィックは、主
としてそれぞれのキャッシュで扱われる。記憶トラフィ
ックは、一般に次の方法のどちらかで扱われる。その１
つは、すべての記憶を多少とも直接的に主記憶装置に送
って、主記憶装置があらゆる変更に対して常に最新状態
となるようにするものである。
これが、「ストア・スルー」型キャッシュである。
もう１つの方法は、記憶をキャッシュに送り、主記憶装
置を直ちに更新はしないものである。更新は、変更され
たキャッシュ・ラインが置換される時にだけ行なわれる
。この皿のキャッシュ動作は、「ストア・イン」型キャ
ッシュと呼ばれる。
ストア・スルー型キャッシュでは、プロセッサが記憶動
作に出会った時、記憶すべきデータが主記憶装置に直接
送られ、またプロセッサのキャッシュにも送られる。そ
のデータが記憶されるキャッシュのアドレス・ラインが
既にキャッシュ内にある場合は、そのラインが新しいデ
ータで更新される。そのラインがキャッシュ内にない場
合は、キャッシュ活動は起こらない。キャッシュの整合
性を維持するため、他のすべてのキャッシュを無効にし
なければならず、記憶プロセッサは、この無効化動作が
完了するまで、そのラインの修正された部分からの取出
しを行なえない。このようにして、主記憶装置は常に更
新されており、どのキャッシュも未更新のデータ・ライ
ンを含まない。
ストア・スルー型キャッシュの使用に伴う主な不利益は
、主記憶装置で扱わなければならない記憶トラフィック
の量が多くなることである。主記憶装置へのアクセスを
試みるプロセッサがいくつもある時は、これが重大なト
ラフィックのネックになりかねない。
ストア・イン型キャッシュは、主記憶装置への記憶トラ
フィックが限られるという利点がある。
しかし、こうしたキャッシュ構成では、所与のキャッシ
ュ・ラインが一時に１つのプロセッサによってしか変更
されないようにする必要がある。
これは、ラインがそれを変更しようとするプロセッサに
よって独占的に保持されるようにすることによって実施
される。ラインが他のキャッシュにある場合は、無効に
される。次に、別のプロセッサが自分のキャッシュの同
じライン・アドレスにデータを記憶しようとする場合、
そのプロセッサは第１のプロセッサから変更されたライ
ンを獲得し、それを独占的に保持し、他のすべてのキャ
ッシュ内のそのライン・アドレスを無効にしなければな
らない。この独占状況のラインをあるプロセッサから別
のプロセッサに転送すると、そのラインが複数のプロセ
ッサによって頻繁に変更される場合、性能が影響を受け
ることがある。というのは、ラインを前後に移動するの
は、かなり時間がかかるからである。現在取り出されて
いるラインはそのキャッシュ内に留まる傾向があり、独
占状況をいつまでも保持するので、この動作状況は長側
（可能性がある。ストア・イン型及びストア・スルー型
キャッシュ・メモリのさらに詳しい説明は、Ａ。
Ｊ　、　Ｘ　ミＸ　（Ｓｍｉｔｈ）の学習用論文「キャ
ッシュ・メモリ（Ｃａｃｈｅ　Ｍｅ＋＋＋ｏｒｆｅｓ）
　Ｊ　ｓ　ＣｏｍｐｕｔｉｎｇＳｕｒｖｅｙｓｖ　Ｖ　
ｏ　ｌ　、　１４、Ｎｏ、３　（１９８２年９月）、１
）ｐ、４７３−５３０に出ている。
現在の高性能マルチプロセッサ（最高８台のプロセッサ
）は、その欠点にかかわらずストア・イン型キャッジ゛
ユを使用している。それは、ストア・スルー型キャッシ
ュの記憶トラフィックが、主記憶装置のアクセス能力に
とって過電負担になるからである。
一部のプロセッサ設計では、記憶データがキャッシュに
送られてからではなく、スタックに入れられた時に、記
憶命令を完了したと指示できる「記憶スタック」を設け
ている。このスタックは、１項目当りただ１つの記憶命
令の結果を保持し、スタックからの項目は、それ以上修
正または処理されずに、キャッシュに記憶される。スタ
ック内のデータは、キャッシュに記憶されてからしかア
クセスできないので、どのプロセッサもスタック内のデ
ータにアクセスできない。スタック内で未処理の記憶を
監視して、後続のデータ取出しまたは命令取出しが未処
理の記憶の影響を受けていないことを確かめなければな
らない。記憶スタックは、パイプラインとキャッシュの
間のタイミングの考慮を容易にするためのバッファにす
ぎない。
従来技術では、キャッシュ・メモリに関する参照文献が
多数あるが、下記のものが代表的である。
米国特許第４１８７７８２号明細書には、すべてが共通
してシステム・バスに接続された（主記憶装置と高速バ
ッファまたはキャッシュ・メモリを含む）複数のシステ
ムを含むデータ処理システムが開示されている。キャッ
シュ・メモリは、システム・ユニット間の各通信を監視
して、それが、主記憶装置のあるワード位置を更新させ
る、システム・ユニットから主記憶装置への通信である
かどうか決定する。そのワード位置がキャッシュにも記
憶されている場合は、主記憶装置内のそのワード位置だ
けでなく、キャッシュ内のそのワード位置も更新される
。
米国特許第４１９５３４０号明細書には、キャッシュ記
憶用の先入れ先出し活動待ち行列が記載されている。こ
の待ち行列は、バッファ・メモリから構成され、それが
システム・バスを介して転送されるすべての情報を受け
取る。システム・バスが、主記憶装置をプロセッサ、そ
のキャッシュ、及び入出力マルチプレクサに接続する。
バッファ・メモリは、２つの相関連する用途を有する。
第１の用途は、キャッシュを主記憶装置と同じ最新状態
に保つことである。この用途では、主記憶装置の更新中
、すなわちプロセッサが主記憶装置に記憶している時、
バッファが受け取る更新済み情報を使って、キャッシュ
を更新する。これは、キャッシュが、主記憶装置中の現
在更新されている項目を含む場合にだけ行なわれる。そ
うでなく、その項目はキャッシュ内にない場合は、キャ
ッシュを更新する必要はなく、バッファ内の情報は廃棄
される。
もう１つの用途は、ミスとなった情報を主記憶装置から
獲得して、それをキャッシュに入れる必要がある、キャ
ッシュ・ミスの取扱いを支援することである。主記憶装
置からの情報がバッファに書き込まれ、次いでキャッシ
ュに書き込まれる。
主記憶装置の構成方式にも依存して、アクセスされてい
るデータに隣接する追加情報が、後で必要になるかもし
れないと予想して、キャッシュに入れられる。
米国特許第４４１５９７０号明細書は、１台ではなく複
数のプロセッサまたは記憶制御装置によって制御できる
メモリを記載している。そのすべてが複数の記憶制御装
置にアクセス可能な、コマンド待ち行列を記憶するキャ
ッシュ・メモリが提供される。空の記憶制御装置は、そ
の後その待ち行列にアクセスして、コマンドを入出力装
置に供給することができる。
本発明者等の知るどの従来技術も、マルチプロセッサ・
システムでストアｅスルー型キャッシュを使用し、同時
に主記憶装置内の記憶トラフィックを、通常はストア・
イン型キャッシュで見られるより低いレベルに保つこと
はできない。
Ｃ０発明が解決しようとする課題 本発明の目的は、マルチプロセッサ・システムでストア
・スルー型キャッシュが使用できるようにする待ち行列
機構を提供することにある。
本発明の他の目的は、マルチプロセッサ・システムでス
トア・イン型キャッシュを使用する場合に、主記憶装置
へのトラフィックを減少させることのできる待ち行列機
構を提供することにある。
００課題を解決するための手段 本発明によれば、各プロセッサによって発行される変更
（すなわち、記憶活動）の、すべてのプロセッサがアク
セスできる待ち行列を保持する、高速待ち行列機構が提
供される。いずれかのプロセッサが、待ち行列中のメモ
リ・ラインに対する記憶活動を発行する時、旧データは
新データで重ね書きされる。その待ち行列に現在対応す
る項目がない場合は、新しい項目が活動化される。新し
い項目用の空間は、既存の何らかの項目、最も古い項目
または先に使われてから最も長時間経った項目を選択し
て除去することによって行なわれる。
まず除去される項目を使って、主記憶装置内のそれに対
応するラインを更新する。除去される項目に保持されて
いる変更を（主記憶装置からの）そのラインの旧値に加
え、更新済みの値を主記憶装置に戻した後、待ち行列中
の項目を「空」とマークして除去する。
プロセッサがそのキャッシュ内にないデータ・ラインに
アクセスする時はキャッシュ・ミスが起こり、そのライ
ンを主記憶装置から取り出すことが必要になる。こうし
た取出しを待ち行列機構で監視して、それが取り出され
ているラインに対する変更を保持しているかどうか調べ
る。保持している場合は、その変更を主記憶装置からの
ラインに加えてから、そのラインを要求側プロセッサに
送る。待ち行列機構内に新しい項目を作成した後、任意
のプロセッサによる同じ項目への他の記憶活動が可能と
なり、通常はその項目を除去して別の項目用の場所をあ
ける前に、その項目に対していくつかの記憶活動が起こ
る。これらの記憶活動は、その項目が最終的に待ち行列
機構から除去される時以外は、主記憶装置に関係しない
ので、この待ち行列は、ストア・イン型キャッシュと同
様にかつ同程度に、主記憶装置への記憶トラフィックを
減少させる。
Ｅ、実施例 第１図には、複数のプロセッサＰ１〜Ｐｎを含むデータ
処理システムが示しである。各プロセッサは、関連する
キャッシュ・メモリ０１〜Ｃｎを備えている。すべての
プロセッサは、優先順位選択インタフェース１２及び高
速待ち行列機構１４を介して主記憶装置１０と通信する
。
優先順位選択インタフェース１２は、既知の方式で、プ
ロセッサＰ１〜Ｐｎのそれぞれと主記憶装置１０の間の
通信の優先順位を確立する。たとえば、次のような優先
順位決定規則が使用できる。
取出し活動に第１の優先順位を与え、ラウンド・ロビン
方式で、すなわちＰｌから順にＰｎへと進み、そこから
次にＰｌに戻る順序でプロセッサＰ１〜Ｐｎにサービス
する。記憶活動にやはりラウンド・ロビン方式で、第２
の優先順位を与える。
メモリ更新活動には最低の優先順位を割り振る。
各プロセッサは、アドレス経路１０２、取出し経路１０
４、記憶経路１０６、制御経路１０８の４つの経路を通
って優先順位選択インタフェース１２と通信する。優先
順位選択インタフェース１２と高速待ち行列機構１４の
間にも同じ経路が存在するが、選択された優先順位に従
って１つのプロセッサだけにサービスする。高速待ち行
列機構１４と主記憶装置１０の間には、アドレス経路１
０２、取出し経路２００、記憶経路２０２の３つの主信
号経路が存在する。これらの各経路の機能については後
で説明する。
各キャッシュ・メモリ０１〜Ｃｎは、ストア・スルー型
のものである。したがって、あるプロセッサがデータを
記憶しようとする時、データは主記憶装置１０に直接送
られ、またそのプロセッサに関連するキャッシュにも送
られる。第２図には、プロセッサと高速待ち行列機構１
４と主記憶装置１０の間の相互接続が、間に介在する優
先順位選択インタフェース１２なしで示しである。プロ
セッサＰ１による記憶活動は、記憶経路１０６を介して
高速待ち行列機構（ＦＱＭ）１４に運ばれ、同時に制御
経路１０８を介して関連する制御信号が運ばれる。その
記憶活動（及び他の活動）に関連するアドレスが、経路
１０２を介してＦＱＭ１４に運ばれる。ＦＱＭ１４で記
憶活動が完了すると、経路１１０を介してプロセッサＰ
１に完了信号が送られる。同時に、ＦＱＭ１４から経路
１１２を介してその信号が送られて、同じアドレスをも
つ他の（Ｃ１以外の）キャッシュ内のラインを無効にす
る。
ＦＱＭ１４はまた、主記憶装置１０からキャッシュへの
取出しを処理する。これらの取出しが起こるのは、プロ
セッサが、その関連するキヤ、ンシュ・メモリ内に存在
しないことがわかった（「キャッシュ・ミス」）特定の
データ・ラインに対する取出しを発行したためである。
取り出すべきデータ・ラインが経路１０２を介してアド
レスされ、主記憶装置１０から取り出されたデータが、
経路２００を介してＦＱＭ１４に戻される。
ＦＱＭ１４に保持されているデータ・ラインに変更があ
る場合は、その変更がそのデータ・ラインに加えられて
から、取出し経路１０４を介して要求側プロセッサに送
られる。
ＦＱＭ１４は小型の高速待ち行列メモリで、データ・ラ
インのリストをキャッシュ・ライン別に維持する。いつ
でも、変更されているキャッシュ・ラインは比較的少な
り、シたがってこのキャッシュ・ラインのリストは、た
とえば項目が８〜１６ライン分と通常は小さい。ＦＱＭ
は、キャッシュ・ライン別に編成され、キャッシュ・ラ
インはバイトのパケットで通常長さ６４バイトまたは１
２８バイトである。この説明では、ＦＱＭ１４はＮ個の
項目を有し、各項目が特定のキャッシュ・データ・ライ
ンに対する変更を保持するものと仮定する。Ｎ個の項目
がすべて「活動状態」、すなわち変更を保持しており、
かつ新しいデータ・ラインを変更しようとする時は、Ｆ
ＱＭ１４から１つの項目を外に出して、新しい項目用の
場所をあける必要がある。最も古い項目をＦＱＭ１４か
ら出すことが好ましいが、別法として最も使用されてい
ない項目を除去してもよい。除去された項目に記憶され
ている変更を使って、主記憶装置１０内の対応するデー
タ・ラインを更新する。これは、経路２０２を介して行
なわれ、更新すべきラインのアドレスがプロセッサから
線１０２を介して直接供給される。
ＦＱＭ１４の詳細な実施例を、第３図、第４図、及び第
５図に示す。まず第３図で、前述の主要相互接続経路が
図の左側に示しである。記憶データは記憶経路１０６上
に現れ、制御信号は制御経路１０８上に、アドレス信号
は経路１０２上に、記憶完了信号は経路１１０上に、取
り出されているデータは取出し経路１０４上に現れる。
−例として記憶活動を取り上げて、ＦＱＭ１４の動作の
説明を始める。命令の種類に応じて、記憶活動は、１バ
イトないし複数バイト（たとえば、１バイト、２バイト
、４バイトまたは８バイト）を記憶することがあり、し
たがってこの情報を、主記憶装置１０内のその記憶が行
なわれる場所のアドレスと共に供給しなければならない
。
記憶すべきバイト数に関する情報は、制御回路１０８を
介して受け取られ、経路１１４を介してバイト選択ゲー
ト１２０に運ばれる。主記憶装置内のその記憶が行なわ
れる場所のアドレスは、経路１０２上に現れる。アドレ
スは、ライン・アドレスとバイト・アドレスに分かれ、
ライン・アドレスは経路１１５上に置かれる。ライン内
のバイト・アドレスは経路１１７上に置かれ、そこから
位置合せスイッチ１２２に供給される。経路１１５上に
現れたライン・アドレスは、ドライバ・ブロック１３６
に供給され、そこから並列にＮ重比較ブロック１３４に
送られる。
高速待ち行列機構１４は、さらにライン変更待ち行列１
２６を含んでいる。この待ち行列１２６は複数ライン・
メモリであり、記憶された各キャッシュ・ラインに対す
る実際の変更データを記憶する。ライン・アドレス・レ
ジスタ１３２が、ライン変更待ち行列１２６内に含まれ
るアドレスのリストを維持する。ライン・アドレス・レ
ジスタ１３２中の活動項目が比較ブロック１３４に供給
される。比較ブロック１３４は、その記憶活動のアドレ
スがライン・アドレス・レジスタ１３２中の活動アドレ
スの１つと一致するか否かを示す信号を線１３５を介し
て送る。一致する場合、線１３５はゲート１４０を使用
可能にする。同様に、一致が発生した時、ライン変更待
ち行列１２θ内の一致したラインの項目番号（１〜Ｎの
数字）が線１４１を介してゲー）１４０に供給される。
ゲート１４０は使用可能になっているので、その項目番
号をＯＲ回路１４４に転送し、次いで経路１５４上に送
って、ライン変更待ち行列１２６中の一致するラインの
項目を選択させる。すなわち、一致が見つかった場合、
経路１５４に現れるデータが、ライン変更待ち行列１２
６中の、記憶が行なわれる先の特定のラインを選択する
。
一致がなく、ライン変更待ち行列１２６が、データを記
憶する先の特定のアドレスを含まないことを示す場合は
、不一致線１７６が励起されてゲート１４２を使用可能
にする。記憶すべきデータを収容するために、ライン変
更待ち行列１２６中に新しい項目を作成しなければなら
ない。この項目の項目番号は、レジスタ１４６中の次の
空項目ポインタで与えられる。レジスタ１４６の動作に
ついては後で説明する。
このポインタは、不一致信号１７６によって使用可能に
されたゲート１４２に供給され、（制御経路１０８から
導き出された）記憶信号１１６が、このポインタ・デー
タをＯＲ回路１４４に渡す。
したがって、次の空項目番号が経路１５４上に置かれて
、ライン変更待ち行列１２６中の次の空項目を選択させ
る。次の空項目ポインタ・レジスタが１だけ増分されて
、次の新しい空項目を指し、同時にそのポインタ値に値
ｋが加えられて、合計モジューロＮが得られる。この合
計値は、その項目が変更されたデータを含む場合に、主
記憶装置内の対応するラインを更新するのに使用される
、ライン変更待ち行列１２６中の別の項目を識別する。
主記憶装置１０内のデータ・ラインが更新されると、ラ
イン変更待ち行列１２６中のその項目が空とマークされ
る。識別された項目が変更されたデータを含んでいなか
った場合は、それは既に空になっており、主記憶装置の
ラインの更新は不要である。数字ｋには、たとえばＮ−
３の値を与えることができる。その場合、ライン変更待
ち行列１２６中に３つの空項目が保持される。
次に第４図で、経路１５４上の選択項目番号が、ライン
変更待ち行列１２６に供給される。選択項目がライン項
目１６０を示すと仮定した場合、それに入るゲート回路
（図示せず）は、入りデータを受け取るように条件付け
られる。経路１０４上に現れる、どのバイトを記憶する
かを指示する制御情報が、工ないし８バイト経路１６３
を、位置合せスイッチ１２２に対して開くように条件付
ける。バイト選択論理回路１２０中の各ゲート回路１６
５内で、バイト・データがそこを通過した時、有効ビッ
トが自動的に挿入される。このことは、第４図の右側の
詳細挿入図に示しである。
経路１０２上の、データ・ライン中のバイトのアドレス
は、位置合せスイッチ１２２に、経路１０６から受け取
ったデータの開始バイトをデータ・ライン項目１６０内
の適切なバイト・アドレス１６２に位置決めさせる。選
択され位置合せされたバイトのデータ・ライン項目１６
０への転送は、経路１１θ上の記憶信号によって使用可
能にされたゲート回路１２４によって制御される。記憶
される先のデータ・ライン項目中のバイトは、以前に有
効になっていても無効になっていてもよい。
有効な時は、そのバイトの新しい値が古い値に置き換わ
る。
第３図で、記憶される先のライン変更待ち行列１２６中
の項目が新しい項目である場合、状況レジスタ１３０中
に現れる対応するＡｃｔ　ｉｖｅ／Ｅｍｐｔｙビットは
、Ｅｍｐｔｙ状態になっているはずである。
そのラインが記憶される時、レジスタ１３０中の対応す
るピットが、ゲート１２８によってＡｃｔ　ｉｖｅ状態
にセットされる。ゲート１２８は、制御線１２９、記憶
線１１６、及び不一致線１７６上に現れる信号によって
使用可能にされる。
ライン変更待ち行列１２６への記憶活動の完了は、記憶
完了信号によって経路１１０を介して通知される。この
信号は記憶側プロセッサに送り返され、またゲート１７
４を使用可能にするのにも使用される。ゲート１７４は
、ライン・アドレスと記憶側プロセッサの識別とをキャ
ッシュ０１〜Ｃｎのすべてに送る。データ・ラインが存
在する場合、記憶側プロセッサのキャッシュ以外のすべ
てのキャッシュ内でそれが無効にされる。
取出し活動が行なわれるのは、プロセッサがキャッシユ
・ミスを起こし、したがってミスとなったデータ・ライ
ンを主記憶袋ｆｔ１ｏから取り出さなければならない時
である。そのデータ・ラインは、ライン変更待ち行列１
２６中に存在する（その中の項目である）こともしない
こともある。項目がない場合、主記憶装置１０内のその
ラインは最新状態であり、その取出しは後述のように通
常の方式で進むことができる。ライン変更待ち行列１２
６中に項目がある場合は、主記憶装置１０内のラインは
最新状態ではなく、そのラインを要求側プロセッサに送
る前に、ライン変更待ち行列１２８中に保持された変更
をそのデータ・ラインに加えなければならない。
あるデータ・ラインがライン変更待ち行列１２６中に項
目を有するかどうかの決定は、記憶活動の場合と同様に
行なわれる。経路１０２上のアドレスがドライバ・ブロ
ック１３６に供給され、ライン・レジスタ１３２中のラ
イン・アドレスと並列に比較される。一致した場合は、
一致したラインの項目番号が、ゲー）１４０または回路
１４４及び経路１５４を介してライン変更待ち行列に供
給される。一致しなかった場合は、どの項目も選択され
ない。同様に、これは記憶動作ではないので、記憶線１
１８がゲート１４２を条件付けるようにセットされてい
ないため、不一致線１７６上の信号はゲート１４２を通
過しない。
第５図には、取り出されるデータが最も最近に更新され
た情報を含むことを保証するために使用されるシステム
の諸要素の構成図を示す。上記のよう１こ、ライン・ア
ドレス拳レジスタ１３２中のアドレスと取り出されるデ
ータのライン・アドレスが一致した場合、ライン変更待
ち行列１２８中の選択された項目が、ゲート１７１を介
して経路１７２上に読み出される。ゲート１７１に対す
る読出し項目使用可能入力は、選択項目経路１５４から
導かれる。
ゲート１７１を介する項目読出しの前に、経路１５４上
の選択項目は、ライン・アドレス・レジスタ１３２から
経路１６４を介して主記憶装置１０にライン・アドレス
を読み出させていた。それに応答して、古い値が主記憶
装置１０から経路２００を介して読み出され、データ・
ライン・バッファ１６６に入れられる。次いで、経路１
７２上に現れる変更済みバイトが旧バイト値を重ね書き
し、更新された値が、ゲート１７０を介して経路１０４
に、次いで取出し側プロセッサに送られる。
一致しなかった場合、主記憶装置１０は依然としてアク
セスされるが、データ・ラインの古い（かつ正しい）値
がライン・バッファ１６６内に取り出される。変更がな
いので、経路１７２から何も重ね書きされず、無修正の
ラインがゲート１７０及び経路１０４を介して取出し側
プロセッサに送られる。
上記に簡略に述べた、主記憶装置１０の更新は、取出し
と同様にして行なわれる。ライン変更待ち行列１２６中
の選択された項目データ・ラインの変更を用いて、ライ
ン・バッファ１８６内のｆ−タ・ラインの古い値の変更
済みバイトを重ね書きする。次に、更新済みのラインを
要求側プロセッサに送る代わりに、更新済みの値をゲー
ト１６８及び経路２０２を介して主記憶装置１０に送り
返して、データ・ラインの古い値を置き換える。ライン
変更待ち行列１２８中の項目はもはや不要であり、Ａｃ
ｔｉｖｅ／Ｅｍｐｔｙレジスタ１３０中の項目をＡｃｔ
ｉｖｅ状態からＥｍｐｔｙ状態にセットして、新しい項
目のためにライン変更待ち行列１２６中の場所をあける
ことができる。
Ｆ０発明の効果 以上から明らかなように、本発明の高速待ち行列機構は
、極めて高速かつ効率的にメモリの変更を更新するのに
適合している。ＦＱＭは、一般に数マシン・サイクル以
内に更新済みレコードを作成することができる。一方、
主記憶装置は非常に遅く、単一の変更を記憶するのに１
０ないし２０サイクルかかることもある。したがって、
この高速待ち行列機構は、ライン・データの変更を高速
かつ効率的に扱うための、主記憶装置の代用物と見なす
ことができる。
【図面の簡単な説明】
第１図は、本発明の全体的構成図である。 第２図は、「高速待ち行列機構」が間に介在するプロセ
ッサと主記憶装置の主要相互接続の構成図である。 第４図は、記憶すべきバイトを選択する回路と、高速待
ち行列機構内でのそれらのバイトの位置合せとの構成図
である。 第５図は、主記憶装置の更新及び取出し更新を示す構成
図である。 １０・・・・主記憶装置、１２・・・・優先順位選択イ
ンタフェース、１４・・・・高速待ち行列機構（ＦＱＭ
）、１０２・・・・アドレス経路、１０４・・・・取出
し経路、１０８・・・・記憶経路、１０８・・・・制御
経路、１２０・・・・バイト選択ゲー）、１２２・・・
・位置合せスイッチ、１２ｅ・・・・ライン変更待ち行
列、１２８．１４０．１４２．１７Ｌ　１７４・・・・
ゲート、１３０・・・・状況レジスタ、１３２・・・・
ライン・アドレス・レジスタ、１３４・・・・Ｎ重比較
ブロック、１３６・・・・ドライバ・ブロック、１４４
・・・・ＯＲ回路、１４６・・・・次の新項目ポインタ
・レジスタ、１６３・・・・１ないし８バイト経路、１
６５・・・・ゲート回路、１６６・・・・データ・ライ
ン・バッファ。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション

Claims (2)

    【特許請求の範囲】
  1. （１）主記憶装置と、キャッシュ・メモリ手段を備えた
    少なくとも１台のプロセッサ・ユニットとを含むデータ
    処理装置において、 限られた数のデータ単位を記憶するための記憶位置を有
    する、上記の主記憶装置とプロセッサ・ユニットの間に
    介在する待ち行列メモリ手段と、主記憶装置のあるアド
    レスに記憶すべき新しく受け取ったデータ単位に応答し
    て、上記の待ち行列メモリ手段に記憶された、一致する
    アドレスをもつデータ単位の存在を示すための比較手段
    と、上記の待ち行列メモリ手段中の上記の記憶されたデ
    ータ単位を、上記の新しく受け取ったデータ単位と一致
    するように修正するための手段とを含むデータ処理装置
    。
  2. （２）主記憶装置と、関連するストア・スルー型キャッ
    シュ・メモリを備えた複数の中央演算処理装置とを含む
    データ処理装置において、 各ラインが複数のバイト項目を記憶する能力を有し、各
    バイト項目が特定のアドレスをもつ、複数のデータ記憶
    ラインを有する待ち行列メモリと、上記待ち行列メモリ
    に項目のアドレスを記憶するためのライン・アドレス・
    メモリと、 新しいバイト項目と上記主記憶装置に記憶すべきそれに
    関連するアドレスとを上記中央演算処理装置の１つから
    受け取るための手段と、 上記ライン・アドレス・メモリに接続された、上記の新
    バイト項目が上記ライン・アドレス・メモリに記憶され
    ているアドレスと一致するかどうか決定し、一致が見つ
    かった場合は一致信号を、また一致が見つからなかった
    場合は不一致信号を生成するための手段と、 不一致信号に応答して、上記新バイト項目を上記待ち行
    列メモリに記憶し、上記ライン・アドレス・メモリをそ
    れに応じて更新し、さらに一致信号に応答して、上記の
    記憶されたアドレスに対応するバイト項目を、上記新バ
    イト項目と合致するように変更するための回路手段と を含む、上記中央演算処理装置と上記主記憶装置の間に
    介在する高速待ち行列機構。
JP2105473A 1989-04-24 1990-04-23 データ処理装置およびその高速待ち行列機構 Pending JPH02297645A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/342,493 US5155831A (en) 1989-04-24 1989-04-24 Data processing system with fast queue store interposed between store-through caches and a main memory
US342493 2003-01-15

Publications (1)

Publication Number Publication Date
JPH02297645A true JPH02297645A (ja) 1990-12-10

Family

ID=23342066

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2105473A Pending JPH02297645A (ja) 1989-04-24 1990-04-23 データ処理装置およびその高速待ち行列機構

Country Status (3)

Country Link
US (1) US5155831A (ja)
EP (1) EP0394620A3 (ja)
JP (1) JPH02297645A (ja)

Families Citing this family (67)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5317738A (en) * 1992-02-18 1994-05-31 Ncr Corporation Process affinity scheduling method and apparatus
US5502833A (en) * 1994-03-30 1996-03-26 International Business Machines Corporation System and method for management of a predictive split cache for supporting FIFO queues
US5692152A (en) * 1994-06-29 1997-11-25 Exponential Technology, Inc. Master-slave cache system with de-coupled data and tag pipelines and loop-back
US5551001A (en) * 1994-06-29 1996-08-27 Exponential Technology, Inc. Master-slave cache system for instruction and data cache memories
US5809550A (en) * 1994-09-30 1998-09-15 Intel Corporation Method and apparatus for pushing a cacheable memory access operation onto a bus controller queue while determining if the cacheable memory access operation hits a cache
US5802340A (en) * 1995-08-22 1998-09-01 International Business Machines Corporation Method and system of executing speculative store instructions in a parallel processing computer system
US5809530A (en) * 1995-11-13 1998-09-15 Motorola, Inc. Method and apparatus for processing multiple cache misses using reload folding and store merging
US6128711A (en) * 1996-11-12 2000-10-03 Compaq Computer Corporation Performance optimization and system bus duty cycle reduction by I/O bridge partial cache line writes
US6175902B1 (en) * 1997-12-18 2001-01-16 Advanced Micro Devices, Inc. Method and apparatus for maintaining a time order by physical ordering in a memory
US5926645A (en) * 1997-07-22 1999-07-20 International Business Machines Corporation Method and system for enabling multiple store instruction completions in a processing system
US6079002A (en) * 1997-09-23 2000-06-20 International Business Machines Corporation Dynamic expansion of execution pipeline stages
US6668317B1 (en) 1999-08-31 2003-12-23 Intel Corporation Microengine for parallel processor architecture
US6427196B1 (en) 1999-08-31 2002-07-30 Intel Corporation SRAM controller for parallel processor architecture including address and command queue and arbiter
US6983350B1 (en) 1999-08-31 2006-01-03 Intel Corporation SDRAM controller for parallel processor architecture
US7191309B1 (en) 1999-09-01 2007-03-13 Intel Corporation Double shift instruction for micro engine used in multithreaded parallel processor architecture
AU7340400A (en) 1999-09-01 2001-03-26 Intel Corporation Double shift instruction for micro engine used in multithreaded parallel processor architecture
US7546444B1 (en) 1999-09-01 2009-06-09 Intel Corporation Register set used in multithreaded parallel processor architecture
JP2001084707A (ja) * 1999-09-10 2001-03-30 Toshiba Corp 可変長符号の復号方法、復号装置及び可変長符号の復号プログラムを記録したコンピュータ読み取り可能な記録媒体
US6401175B1 (en) 1999-10-01 2002-06-04 Sun Microsystems, Inc. Shared write buffer for use by multiple processor units
US6532509B1 (en) 1999-12-22 2003-03-11 Intel Corporation Arbitrating command requests in a parallel multi-threaded processing system
US6694380B1 (en) 1999-12-27 2004-02-17 Intel Corporation Mapping requests from a processing unit that uses memory-mapped input-output space
US6307789B1 (en) 1999-12-28 2001-10-23 Intel Corporation Scratchpad memory
US6631430B1 (en) 1999-12-28 2003-10-07 Intel Corporation Optimizations to receive packet status from fifo bus
US6625654B1 (en) 1999-12-28 2003-09-23 Intel Corporation Thread signaling in multi-threaded network processor
US7620702B1 (en) 1999-12-28 2009-11-17 Intel Corporation Providing real-time control data for a network processor
US6324624B1 (en) 1999-12-28 2001-11-27 Intel Corporation Read lock miss control and queue management
US6661794B1 (en) 1999-12-29 2003-12-09 Intel Corporation Method and apparatus for gigabit packet assignment for multithreaded packet processing
US6976095B1 (en) 1999-12-30 2005-12-13 Intel Corporation Port blocking technique for maintaining receive packet ordering for a multiple ethernet port switch
US6952824B1 (en) 1999-12-30 2005-10-04 Intel Corporation Multi-threaded sequenced receive for fast network port stream of packets
US7480706B1 (en) 1999-12-30 2009-01-20 Intel Corporation Multi-threaded round-robin receive for fast network port
US6584522B1 (en) 1999-12-30 2003-06-24 Intel Corporation Communication between processors
US7681018B2 (en) * 2000-08-31 2010-03-16 Intel Corporation Method and apparatus for providing large register address space while maximizing cycletime performance for a multi-threaded register file set
US20020053017A1 (en) * 2000-09-01 2002-05-02 Adiletta Matthew J. Register instructions for a multithreaded processor
US7020871B2 (en) * 2000-12-21 2006-03-28 Intel Corporation Breakpoint method for parallel hardware threads in multithreaded processor
US20020129370A1 (en) * 2001-02-09 2002-09-12 Dan Kikinis Method and system for implementing an electronic program guide
US7487505B2 (en) 2001-08-27 2009-02-03 Intel Corporation Multithreaded microprocessor with register allocation based on number of active threads
US7225281B2 (en) 2001-08-27 2007-05-29 Intel Corporation Multiprocessor infrastructure for providing flexible bandwidth allocation via multiple instantiations of separate data buses, control buses and support mechanisms
US6868476B2 (en) 2001-08-27 2005-03-15 Intel Corporation Software controlled content addressable memory in a general purpose execution datapath
US7216204B2 (en) * 2001-08-27 2007-05-08 Intel Corporation Mechanism for providing early coherency detection to enable high performance memory updates in a latency sensitive multithreaded environment
US7126952B2 (en) 2001-09-28 2006-10-24 Intel Corporation Multiprotocol decapsulation/encapsulation control structure and packet protocol conversion method
US7158964B2 (en) * 2001-12-12 2007-01-02 Intel Corporation Queue management
US7107413B2 (en) * 2001-12-17 2006-09-12 Intel Corporation Write queue descriptor count instruction for high speed queuing
US7269179B2 (en) * 2001-12-18 2007-09-11 Intel Corporation Control mechanisms for enqueue and dequeue operations in a pipelined network processor
US7895239B2 (en) * 2002-01-04 2011-02-22 Intel Corporation Queue arrays in network devices
US7181573B2 (en) * 2002-01-07 2007-02-20 Intel Corporation Queue array caching in network devices
US6934951B2 (en) 2002-01-17 2005-08-23 Intel Corporation Parallel processor with functional pipeline providing programming engines by supporting multiple contexts and critical section
US7181594B2 (en) * 2002-01-25 2007-02-20 Intel Corporation Context pipelines
US7610451B2 (en) 2002-01-25 2009-10-27 Intel Corporation Data transfer mechanism using unidirectional pull bus and push bus
US6826656B2 (en) * 2002-01-28 2004-11-30 International Business Machines Corporation Reducing power in a snooping cache based multiprocessor environment
US7149226B2 (en) * 2002-02-01 2006-12-12 Intel Corporation Processing data packets
US7437724B2 (en) * 2002-04-03 2008-10-14 Intel Corporation Registers for data transfers
US7471688B2 (en) 2002-06-18 2008-12-30 Intel Corporation Scheduling system for transmission of cells to ATM virtual circuits and DSL ports
US7337275B2 (en) 2002-08-13 2008-02-26 Intel Corporation Free list and ring data structure management
US7352769B2 (en) 2002-09-12 2008-04-01 Intel Corporation Multiple calendar schedule reservation structure and method
US7433307B2 (en) 2002-11-05 2008-10-07 Intel Corporation Flow control in a network environment
US6941438B2 (en) 2003-01-10 2005-09-06 Intel Corporation Memory interleaving
US7443836B2 (en) 2003-06-16 2008-10-28 Intel Corporation Processing a data packet
US7225299B1 (en) 2003-07-16 2007-05-29 Transmeta Corporation Supporting speculative modification in a data cache
US7149851B1 (en) * 2003-08-21 2006-12-12 Transmeta Corporation Method and system for conservatively managing store capacity available to a processor issuing stores
US7213099B2 (en) 2003-12-30 2007-05-01 Intel Corporation Method and apparatus utilizing non-uniformly distributed DRAM configurations and to detect in-range memory address matches
US7941585B2 (en) * 2004-09-10 2011-05-10 Cavium Networks, Inc. Local scratchpad and data caching system
WO2006031551A2 (en) 2004-09-10 2006-03-23 Cavium Networks Selective replication of data structure
US7594081B2 (en) 2004-09-10 2009-09-22 Cavium Networks, Inc. Direct access to low-latency memory
US20070288694A1 (en) * 2006-06-13 2007-12-13 Sanjeev Ghai Data processing system, processor and method of data processing having controllable store gather windows
US20080089735A1 (en) * 2006-10-17 2008-04-17 Super Wash, Inc. Cover for the head of a foaming brush
CN102541746B (zh) * 2010-12-07 2014-11-26 深圳市金蝶中间件有限公司 一种队列的数据处理方法和系统
JP2016531370A (ja) * 2013-09-09 2016-10-06 シーゲイト テクノロジー エルエルシーＳｅａｇａｔｅ Ｔｅｃｈｎｏｌｏｇｙ ＬＬＣ 温度管理を有するモバイルデータ記憶デバイス

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4195340A (en) * 1977-12-22 1980-03-25 Honeywell Information Systems Inc. First in first out activity queue for a cache store
US4167782A (en) * 1977-12-22 1979-09-11 Honeywell Information Systems Inc. Continuous updating of cache store
US4394731A (en) * 1980-11-10 1983-07-19 International Business Machines Corporation Cache storage line shareability control for a multiprocessor system
US4415970A (en) * 1980-11-14 1983-11-15 Sperry Corporation Cache/disk subsystem with load equalization
US4533995A (en) * 1981-08-03 1985-08-06 International Business Machines Corporation Method and system for handling sequential data in a hierarchical store
US4521851A (en) * 1982-10-13 1985-06-04 Honeywell Information Systems Inc. Central processor
US4597044A (en) * 1982-10-14 1986-06-24 Honeywell Information Systems, Inc. Apparatus and method for providing a composite descriptor in a data processing system
US4530052A (en) * 1982-10-14 1985-07-16 Honeywell Information Systems Inc. Apparatus and method for a data processing unit sharing a plurality of operating systems
US4633387A (en) * 1983-02-25 1986-12-30 International Business Machines Corporation Load balancing in a multiunit system
US4775955A (en) * 1985-10-30 1988-10-04 International Business Machines Corporation Cache coherence mechanism based on locking
US4881163A (en) * 1986-09-19 1989-11-14 Amdahl Corporation Computer system architecture employing cache data line move-out queue buffer

Also Published As

Publication number Publication date
EP0394620A3 (en) 1992-07-08
US5155831A (en) 1992-10-13
EP0394620A2 (en) 1990-10-31

Similar Documents

Publication Publication Date Title
US5155831A (en) Data processing system with fast queue store interposed between store-through caches and a main memory
US20230004500A1 (en) Aggressive write flush scheme for a victim cache
US4445174A (en) Multiprocessing system including a shared cache
US5091851A (en) Fast multiple-word accesses from a multi-way set-associative cache memory
EP0349122B1 (en) Method and apparatus for filtering invalidate requests
US6496902B1 (en) Vector and scalar data cache for a vector multiprocessor
US5410669A (en) Data processor having a cache memory capable of being used as a linear ram bank
US7120755B2 (en) Transfer of cache lines on-chip between processing cores in a multi-core system
US7017011B2 (en) Coherence controller for a multiprocessor system, module, and multiprocessor system with a multimodule architecture incorporating such a controller
TW573252B (en) Shared cache structure for temporal and non-temporal instructions
US5696937A (en) Cache controller utilizing a state machine for controlling invalidations in a network with dual system busses
US6249846B1 (en) Distributed data dependency stall mechanism
EP1399823B1 (en) Using an l2 directory to facilitate speculative loads in a multiprocessor system
EP0598535A1 (en) Pending write-back controller for a cache controller coupled to a packet switched memory bus
US4989140A (en) Single chip pipeline data processor using instruction and operand cache memories for parallel operation of instruction control and executions unit
US6260117B1 (en) Method for increasing efficiency in a multi-processor system and multi-processor system with increased efficiency
US20130205087A1 (en) Forward progress mechanism for stores in the presence of load contention in a system favoring loads
KR20040012812A (ko) Ｌ2 디렉토리를 이용한 멀티프로세서 시스템의 가-저장촉진 방법 및 장치
KR20030024895A (ko) 캐시 코히어런트 멀티-프로세서 시스템에서 순서화된입출력 트랜잭션을 파이프라이닝하기 위한 방법 및 장치
KR100851738B1 (ko) 로우-레벨 캐시를 포함한 액세스 촉진용 리버스 디렉토리
US6751700B2 (en) Date processor and storage system including a set associative cache with memory aliasing
JPH03225542A (ja) データ記憶方法及びビットエンコードデータの処理回路
US20060179185A1 (en) Method to preserve ordering of read and write operations in a DMA system by delaying read access
US5206945A (en) Single-chip pipeline processor for fetching/flushing instruction/data caches in response to first/second hit/mishit signal respectively detected in corresponding to their logical addresses
EP0741356A1 (en) Cache architecture and method of operation