JPS6135584B2 - - Google Patents

Info

Publication number
JPS6135584B2
JPS6135584B2 JP57214788A JP21478882A JPS6135584B2 JP S6135584 B2 JPS6135584 B2 JP S6135584B2 JP 57214788 A JP57214788 A JP 57214788A JP 21478882 A JP21478882 A JP 21478882A JP S6135584 B2 JPS6135584 B2 JP S6135584B2
Authority
JP
Japan
Prior art keywords
tid
cache
line
candidate
remote
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.)
Expired
Application number
JP57214788A
Other languages
English (en)
Other versions
JPS58154062A (ja
Inventor
Paashii Furetsuchaa Robaato
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 JPS58154062A publication Critical patent/JPS58154062A/ja
Publication of JPS6135584B2 publication Critical patent/JPS6135584B2/ja
Granted legal-status Critical Current

Links

Classifications

    • 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
    • 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/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning
    • G06F12/127—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning using additional replacement algorithms

Landscapes

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

Description

【発明の詳細な説明】 〔技術分野〕 本発明は、専用のキヤツシユを各々有する複数
の中央プロセツサと、これらの中央プロセツサに
よつて共有される主記憶装置とを具備する多重プ
ロセツサ・システムに係り、特に該システムにお
けるキヤツシユ・デイレクトリのエントリ置換に
係る。
〔背景技術〕
現在使用されている中央プロセツサの大部分
は、主記憶装置のアクセス時間を短縮するために
専用の高速バツフア・メモリ即ちキヤツシユを備
えている。キヤツシユは中央プロセツサで実行さ
れているプログラムにとつてはトランスペアレン
トであり、プログラムがキヤツシユを直接アクセ
スできないようになつているのが普通である。キ
ヤツシユの種類としては、ストア・イン式のキヤ
ツシユ（以下、SIキヤツシユと略称）及びスト
ア・スルー式のキヤツシユ（以下、STキヤツシ
ユと略称）が知られている。
各中央プロセツサが専用のSIキヤツシユを持つ
ている多重プロセツサ・システム（以下、MPシ
ステムを略称）では、各中央プロセツサは、希望
するライン（ブロツクとも云う）が自身のSIキヤ
ツシユにあれば、主記憶装置をアクセスすること
なくそのラインを変更できるので、主記憶装置に
ある対応するラインが最新のものではなくなり、
従つて他の中央プロセツサが最新のものではない
ラインをアクセスするという問題がある。キヤツ
シユがSTキヤツシユであれば、STキヤツシユ及
び主記憶装置の両方でラインの変更或いは更新が
行なわれるから、このような問題は生じない。し
かしながら、STキヤツシユを用いた場合には、
すべての書込み要求（普通、中央プロセツサから
出される全要求の10〜20％を占める）を主記憶装
置に送る必要があり、それによる性能低下を避け
るためには、主記憶装置の帯域幅をかなり大きく
しなければならない。それができなければ、主記
憶装置を共有できる中央プロセツサの数（MPレ
ベルと呼ばれる）が著しく制限される。従つて、
〓〓〓〓〓
主記憶装置の帯域幅がそれ程大きくないMPシス
テムにはSIキヤツシユの方が適していると云え
る。米国特許第3735360号及び同第3771137号はSI
キヤツシユの代表的な構成を開示している。
書込み及び読出しの面からみれば、まずSTキ
ヤツシユはこれらを異なつた態様で処理する。即
ち、STキヤツシユを用いた場合、書込み要求は
すべて主記憶装置にも送られるので、たとえアド
レス指定されたライン（目的ラインと云う）が
STキヤツシユになくても書込みミスは生じな
い。これに対して、SIキヤツシユの場合は、書込
み及び読出しは同じように扱われる。即ち、書込
み又は読出しが行なわれるべき目的ラインは必ら
ずSIキヤツシユになければならない。もし目的ラ
インがSIキヤツシユになくて、キヤツシユ・ミス
が生じると、書込み又は読出しを行なう前に、主
記憶装置から対応するラインがSIキヤツシユへ転
送される。このラインに対する以後の書込みはす
べてSIキヤツシユでのみ行なわれるから、STキ
ヤツシユを用いた場合に比べて、主記憶装置の必
要な帯域幅をかなり小さくすることができる。
しかし、MPシステムにSIキヤツシユを用いた
場合、最新のデータが主記憶装置ではなくてキヤ
ツシユにあることが多いという問題がある。従つ
て、各中央プロセツサが自身のキヤツシユに対す
る読出し要求又は書込み要求を出したときに目的
ラインがキヤツシユになければ（キヤツシユ・ミ
ス）、当該中央プロセツサが最新のデータをアク
セスできるようにするため、MPシステム内のす
べてのキヤツシユ・デイレクトリで相互照会を行
なつて、目的ラインが他の中央プロセツサのキヤ
ツシユにあるか否か、及びもしあればそのライン
のコピーが当該キヤツシユで変更されているか否
かを調べなければならない。目的ラインがどの中
央プロセツサのキヤツシユにもなければ、目的ラ
インを主記憶装置から、要求を出した中央プロセ
ツサのキヤツシユへ読出すことができる。目出ラ
インが他の中央プロセツサのキヤツシユにあつて
も、それが変更されていなければ、同様な読出し
が行なわれる。その場合、他の中央プロセツサの
キヤツシユにおいて目的ラインが無効化されるこ
とがある。目的ラインが他の中央プロセツサのキ
ヤツシユにあつて変更されていると、目的ライン
をそのキヤツシユから主記憶装置に書戻す必要が
ある。このような書戻しは「吐出し」と呼ばれ
る。然る後、要求を出した中央プロセツサは目的
ラインを自身のキヤツシユへ読出し、次いでそれ
に対して読出し又は書込みを行なう。
同じラインのコピーが複数のキヤツシユにあつ
た場合、その何れもが変更されていなければ、キ
ヤツシユ（１以上でもよい）からの読出しは可能
である。
上述のように、目的ラインが他の中央プロセツ
サのキヤツシユで変更されていると、主記憶装置
への吐出し又は要求を出した中央プロセツサのキ
ヤツシユへの直接転送が必要なため、かなりのオ
ーバーヘツドが生じる。また、２台のプロセツサ
が同じラインを数多くアクセスした場合には、そ
の度に相互照会及びライン転送を行なわねばなら
ず、従つてシステム全体の処理能力が落ちる。
〔本発明の目的〕
本発明の目的は、上述の如きオーバーヘツドが
軽減されたMPシステムを提供することにある。
〔本発明の概要〕
まず本項及び次の「実施例の説明」の項で使用
される主な略語の意味を明らかにしておく。
CP＝中央プロセツサ LRU＝最も長い間使用されていないエントリを
置換えるアルゴリズム MP＝多重プロセツサ PSW＝プログラム状況ワード SI＝ストア・イン ST＝スイア・スルー STO＝セグメント・テーブル起点 TID＝タスク識別子 TLB＝変換索引緩衝機構（DLATとも呼ばれる） XI＝相互照会 複数のCPのうち、目的ラインが自身のキヤツ
シユになくて、他のCPにXI信号を送つたCPを
「リモートCP」と呼び、相互照会の結果、自身の
キヤツシユにリモートCPの目的ラインがあるこ
とがわかつた、即ちXIヒツトが生じたCPを「ロ
ーカルCP」と呼ぶことにする。ローカルCPは目
的ラインのコピーを無効化すると共に、もしそれ
が変更されていれば主記憶装置への吐出しを行な
わねばならない。
本発明はSIキヤツシユ及びSTキヤツシユの両
方に適用できるが、相互照会によるオーバーヘツ
〓〓〓〓〓
ドをかなり軽減するという点で、SIキヤツシユへ
の適用の方が効果がある。従つて、以下ではSIキ
ヤツシユに適用した場合について説明することに
する。
本発明は、プログラム・ジヨブの指名単位或い
は実行単位を表わすプログラム・タスク識別子
TIDを使用する。これは、本発明の実施にあたつ
て、プログラムがアクセスできるTIDを使用しな
ければならない、ということではない。市販の大
型CPにおいては、TIDを表わすためにハードウ
エアによつてSTOが割当てられるのが普通であ
り、またTIDには、記憶保護キーや、アーキテク
チヤ及びインプリメンテーシヨンに応じた他の属
性が含まれることもある。例えば、IBM社の大型
CPにおいては、ハードウエアによつて表わされ
たSTOが各ページ・フレーム・アドレスに割当
てられ、それがTLB内の変換されたアドレスを
用いて各キヤツシユ・エントリに関連付けられ
る。
本発明は次のような認識に基いている。即ち、
リモートCPで実行中のタスクが要求しているラ
インがローカルCPのキヤツシユにあつた場合、
ローカル・キヤツシユ中の同じタクスに関連する
他のラインが、最後のXIヒツトを生ぜしめたリ
モートCPによつて近い将来に要求される可能性
が高い。またローカルCPで実行中のタクスがそ
れと異なつていれば、ローカルCPがそのような
他のラインを近い将来に要求する可能性は低い。
従つて、本発明においては、XIヒツナの生じた
ラインと同じタスクで且つローカルCPで実行中
でないタスクに関連する他のラインが早期にロー
カル・キヤツシユから主記憶装置へ吐出される。
その結果XIヒツトが生じにくくなり、それに伴
なうオーバーヘツドが軽減される。ローカルCP
で実行中のタスクに関連するラインは近い将来に
ローカルCPによつて要求される可能性が高いの
で、そのようなラインについては早期吐出し（置
換）は禁止される。
LRUの如き通常の置換アルゴリズムによつて
選択されたエントリの代りに、ローカルCPで実
行中のタクスとは異なるタスクに関連するエント
リを置換えるようにすれば、前者のタスクで使用
されるラインをより多くキヤツシユにもつてくる
ことができるから、ローカルCPの性能が向上す
る。
キヤツシユ・デイレクトリのエントリ置換（キ
ヤツシユのライン置換も同義）をタクスに基いて
制御するため、本発明においては、キヤツシユ・
デイレクトリの各エントリは、対応するラインを
要求したタスクを識別するTIDを含んでいる。
TIDは例えばSTO及び当該タスクのための記憶保
護キーから作成される。XIヒツトが生じると、
そのときリモートCPで実行されていたタスクの
TIDがリモートTIDレジスタに保持される。のち
ほどローカルCPのキヤツシユにおいてライン置
換が必要になつたとき、即ちキヤツシユ・ミスが
生じたときに、リモートTIDレジスタに保持され
ているTIDと同じTIDを含むキヤツシユ・デイレ
クトリ・エントリが置換候補として選択される。
ただし、このTIDはローカルCPで現在実行中の
タスクのTIDとは異なつている、という条件があ
る。このような置換候補の選択は、当該TIDによ
つて識別されるタスクが現在別のCPで実行され
ており、従つてこのタクスがまもなく置換候補の
アクセスを要求するであろうという仮定に基いて
いる。
TIDの形式は、本発明を実施するCPのシステ
ム・アーキテクチヤに応じたものでよい。例えば
IBMシステム３８は、ハードウエアがアクセスし
得る２バイトの「プロセスID」によつて各タス
ク（プロセス）を一意的に識別しているが、この
プロセスIDを本発明におけるTIDとして用いるこ
とができる。IBMシステム／370アーキテクチヤ
に従うCPでは、STO及び現PSWの記憶保護キー
からタスクIDが作成される。システム／370のCP
は同じSTO及び記憶保護キーを持つた複数のタ
スクを実行し得るので、このタスクIDは必らず
しも一意的なものではないが、本発明での使用に
は支障はない。ただ、リモートCP及びローカル
CPにおいて同じTIDが作成される可能性が高く
なるだけである。
本発明に従えば、MPシステムにおける相互照
会によるオーバーヘツドが軽減され、それと同時
にキヤツシユのヒツト率が改善される。本発明
は、異なつたタスクが複数のCPで実行され得る
MPシステムでの実施に適しており、特に各CPが
SIキヤツシユを備えている場合に著しい効果を発
揮する。リモードCPによつて要求される可能性
〓〓〓〓〓
の高いラインが早期に主記憶装置へ吐出されるか
らである。
〔実施例の説明〕
本発明は、例えば第１１図に示したようなMP
システムで実施できる。図示のMPシステムは、
主記憶装置MSを共有している４台のCP（CP０
〜CP３）を含む。各CPは命令実行装置IE及びバ
ツフア制御装置BCEを具備し、システム・コン
トローラSC０又はSC１を介して主記憶装置MS
に接続される。主記憶装置MSは複数の基本記憶
モジユール・コントローラBSCと、各BSCに２台
ずつ接続されている複数の基本記憶モジユール
BSMとで構成される。入出力装置（図示せず）
もチヤンネルCHANを介して主記憶装置MSに接
続される。システム全体の監視はサービス・プロ
セツサSVPが受け持つ。何れかのCPでキヤツシ
ユ・ミスが生じると、例えば特願昭56−139873号
の明細書及び図面に記載されているようにして、
XI母線９を用いた相互照会が行なわれる。相互
照会自体は本発明とは無関係であるから、詳細に
ついては省略する。
第１図は、各CPで使用される本発明の実施例
の概要を示し、第２図は、４ウエイのセツト・ア
ソシアテイブ式キヤツシユ・デイレクトリ１２、
キヤツシユ１３、及びLRU回路１４を含む関連
制御回路を示している。LRU回路１４は通常の
LRUアルゴリズムに従つて置換候補（エント
リ）を選択するもので、母線２８を構成している
４本のLRU置換候補線Ａ，Ｂ，Ｃ，Ｄのうちの
１本に出力信号を発生し、第１図の置換選択回路
５１へ供給する。キヤツシユ・デイレクトリ１２
の各エントリ（第４図参照）は、アドレスや有効
ビツトなどの通常のフイールドの他に、有効エン
トリによつて表わされるラインを要求したタスク
を識別するための一意的なTIDフイールドを含ん
でいる。なお、実施例の動作の流れが第１０図に
示されているので、以下の説明では第１０図をも
併わせて参照されたい。
各CPは仮想アドレスを用いて読出し要求又は
書込み要求を出す。キヤツシユ・デイレクトリ１
２は、仮想アドレスによつてアドレス指定され、
４つのエントリＡ，Ｂ，Ｃ，Ｄを含む特定のコン
グルエンス・クラスがデイレクトリ出力レジスタ
２２（第４図）へ読出される。仮想アドレスは、
例えば米国特許第4136385号に記載の如きTLB
（図示せず）にも供給され、絶対アドレスに変換
される。キヤツシユ・デイレクトリ１２の出力側
に設けられている比較回路１６は、この変換され
た絶対アドレスと、デイレクトリ出力レジスタ２
２に読出された各エントリ中の絶対アドレスとを
比較し、一致すれば対応するビツト信号を発生す
る。
デイレクトリ出力レジスタ２２中の４つのエン
トリＡ，Ｂ，Ｃ，Ｄに含まれる各TIDはTID出力
母線２７を介して第１図のTID比較回路１８（詳
細は第５図）へ供給される。TID比較回路１８
は、TID出力母線２７から受取つた４つのTID即
ちTID−Ａ，TID−Ｂ，TID−Ｃ及びTID−Ｄ
と、リモートTIDレジスタ１１にあるリモート
CPからのTIDとを比較する。リモートTIDレジ
スタ１１は、ローカルCPが接続されているシス
テム・コントローラSCでXIヒツトが生じたとき
にセツトされる。TID比較回路１８での比較は、
ローカルCPでキヤツシユ・ミスが生じ（線２
６）、それによりアンド・ゲート２４が条件付け
られて、リモートTIDレジスタ１１の内容がTID
比較回路１８へ供給されたときに行なわれる。
TID出力母線２７からの４つのローカルTIDの何
れかがリモートTIDレジスタ１１からのリモート
TIDと一致すれば、候補選択回路５２及び５３が
付勢され、TID候補として最終的に選択されるの
はどのエントリかを決定する。
デイレクトリ出力レジスタ２２に読出されたコ
ングルエンス・クラスに含まれる４つの有効ビツ
トＶ−Ａ，Ｖ−Ｂ，Ｖ−Ｃ及びＶ−Ｄは、有効ビ
ツト母線３０を介して第１図の無効エントリ候補
選択回路５４へ供給される。この選択回路５４
は、有効ビツトＶが０である無効エントリを置換
候補として置換選択回路５１に知らせる。このよ
うな無効エントリは回路５１において最優先で選
択される。デイレクトリ出力レジスタ２２に読出
された４つのエントリがすべて有効であれば（Ｖ
＝１）、無効エントリ候補選択回路５４は線９７
へ全エントリ有効信号を発生する。置換選択回路
５１は、全エントリ有効信号が発生されると、
TID候補選択回路５３からのTID候補（もしあれ
ば）に対応するエントリを選択することができ
る。
〓〓〓〓〓
次に第３図を参照しながら、TIDの作成につい
て説明する。第３図はIBMシステム／370の大型
プロセツサ３０３３，３０８１などで使用されて
いるPSWの一部と制御レジスタCR１とを示した
ものである。PSWは記憶保護キー（SPキー）を
含み、制御レジスタCR１はセグメント・テーブ
ル長STL及びセグメント・テーブル起点STOを
含む。SPキーはPSWに含まれている場合、特に
PSWキーとも呼ばれる。PSWキーは各CPで現在
実行中のプログラムに割当てられる。STOは現
プログラムのセグメント・テーブル（主記憶装置
にある）を指定し、従つて現プログラムのための
仮想アドレス空間を識別する。各CPで現在実行
中のプログラムのためのTIDは、参照番号２１の
ところに示したように、STO及びPSWキーを連
結することによつて作成される。各CPで作成さ
れたTID即ちローカルTIDは自身のキヤツシユを
アクセスするのに用いられ、またキヤツシユ・ミ
スが生じた場合には、リモートTIDとしてXI母線
９（第１１図）を介して他のCPへ送られる。多
重仮想記憶（MVS）と呼ばれるシステム制御プ
ログラムにおいては、一般に、STO及びキーを
連結することによつて実行中のタスクを識別して
いる。
米国特許第4136385号に記載されているよう
に、STOそのものを使用する代りにSTOの識別
子を使用すれば、TIDのビツト数を減らすことが
できる。
第１図に戻つて、リモートTIDレジスタ１１
は、システム・コントローラSCに接続された線
３３上のXIヒツト信号によつてアンド・ゲート
３１が条件付けられたときに、リモートCPから
線３２を介して送られてきたリモートTIDを受取
る。XIヒツト信号は、リモートCPでキヤツシ
ユ・ミスが生じた場合に、システム・コントロー
ラSCでの相互照会の結果、目的ラインがローカ
ルCPのキヤツシユにあることがわかつたときに
発生される。リモートTIDレジスタ１１の内容即
ちリモートTIDは比較器３９にも供給される。比
較器３９はこのリモートTIDと線２３上のローカ
ルTIDとを比較し、一致していれば線４１に一致
信号を発生して、アンド・ゲート３７を部分的に
条件付ける。リモートTID及びローカルTIDが一
致するということは、リモートCP及びローカル
CPで同じタスクが並行して実行されていること
を意味する。アンド・ゲート３７は、オア・ゲー
ト３４を介して線３３上のXIヒツト信号又は線
３６上のキヤツシユ・ヒツト信号を受取つたとき
に完全に条件付けられ、リモートTIDレジスタ１
１をリセツトする。リモートTIDレジスタ１１が
リセツトされていまうと、TID比較回路１８は出
力を発生せず、従つてデイレクトリ出力レジスタ
２２に読出されていた４つのエントリ中のTID
は、キヤツシユ・デイレクトリ１２のための置換
候補選択に関与しなくなる。
しかしながら、リモートTIDがリモートTIDレ
ジスタ１１に存在している間は、キヤツシユ・デ
イレクトリ１２から選択されたコングルエンス・
クラスに含まれる４つのエントリ中のTIDは、置
換のためのTID候補の有無について検査される。
前述のように、無効ラインを表わすエントリは常
に最優先で選択される。４つのTIDは、ローカル
CPでキヤツシユ・ミスが生じる度に、TID比較
回路１８においてリモートTIDレジスタ１１にあ
るリモートTIDと比較される。TID比較回路１８
はTID−Ａ〜TID−Ｄの何れもがリモートTIDと
一致しなければ、線４８にLRU有効化信号を発
生し、TID候補がないことを置換選択回路５１に
知らせる。置換選択回路５１は、無効エントリ候
補及びTID候補の何れもが存在していなければ、
通常のLRU回路１４によつて決定されたLRU候
補をエントリ置換のために選択する。LRU回路
１４は周知であるから、詳細については省略す
る。
第５図はTID比較回路１８の詳細を示したもの
で、４つの比較器（排他的オア回路）を含んでい
る。これらの比較器はデイレクトリ出力レジスタ
２２からTID出力母線２７を介して送られてきた
４つのTID（TID−Ａ〜TID−Ｄ）とリモート
TIDレジスタ１１から送られてきたリモートTID
とを比較し、それらが一致すれば、各々の出力線
４１〜４４に対応する一致信号を発生する。出力
線４１〜４４はオア回路４６にも接続されてお
り、従つて何れの一致信号も発生されなければ、
オア回路４６のゼロ出力が反転器４７で反転され
て、線４８にLRU有効化信号が発生される。線
４１〜４４は候補選択回路５２及び５３に接続さ
れ、線４８は置換選択回路５１に接続される。
〓〓〓〓〓
候補選択回路５２及び５３は、TID比較回路１
８が１以上の一致信号を発生したときに、それに
応答して１つのTID候補を選択する。TID候補に
対応するエントリには、キヤツシユ中で変更され
たラインを表わすものと、変更されていないライ
ンを表わすものとがある。XIヒツトが生じる
と、変更されたラインは無効化の前にまず主記憶
装置へ吐出されねばならないが、変更されていな
いラインは無効化だけでよいから、TID候補とし
ては変更されたラインの方が優先される。変更さ
れたラインは変更候補選択回路５２で選択され
る。変更候補選択回路５２の詳細は第６図に示さ
れている。第６図の回路は、TID比較回路１８か
らの一致信号の他に、選択されたコングルエン
ス・クラスの各エントリに含まれている変更ビツ
トCH（第４図参照）を変更ビツト母線２９から
受取る。変更ビツトCH（CH−Ａ〜CA−Ｄ）が
１で且つ一致信号（TID−Ａ一致〜TID−Ｄ一
致）が発生されていた場合の選択の優先順位は
Ａ，Ｂ，Ｃ，Ｄの順である。これは、アンド・ゲ
ート６１〜６４及び反転器６６〜６８の接続から
明らかであろう。
アンド・ゲート６１〜６４の何れもが条件付け
られず、従つて線７１〜７４上に対応する変更候
補信号が発生されなかつた場合には、オア回路７
６及び反転器７７の働きによつて、変更候補がな
いことを示す無変更信号が線７８上に発生され、
TID候補選択回路５３（詳細は第７図）へ供給さ
れる。
第７図の回路は基本的には第６図の回路と同じ
であつて、アンド・ゲート及び反転器の組合せを
利用しており、変更ビツトCHが０のエントリに
対応するTID一致信号又は変更ビツトCHが１の
エントリに対応する変更候補信号をTID候補信号
として線８１〜８４へ出力する。ただし、前者の
TID一致信号が出力されるのは、線７８に無変更
信号が発生されている場合だけである。優先順位
は第６図の回路と同じくＡ，Ｂ，Ｃ，Ｄの順であ
る。TID候補信号は置換選択回路５１（詳細は第
８図）へ供給される。
第８図の回路は無効エントリ候補、TID候補及
びLRU候補の中から、キヤツシユ・デイレクト
リ１２で置換えられるべき候補（エントリ）を最
終的に選択する。TID候補は線９７上に全エント
リ有効信号が発生された場合にのみ選択され、
LRU候補は線９７上に全エントリ有効信号が発
生され且つ線４８上にLRU有効化信号が発生さ
れた場合にのみ選択される。第８図の回路は、選
択した置換エントリ信号を線２６上のキヤツシ
ユ・ミス信号に応答してキヤツシユ・デイレクト
リ１２へ供給する。
無効エントリ候補は第９図に詳細が示されてい
る無効エントリ候補選択回路５４で選択され、置
換選択回路５１へ供給される。第９図の回路は有
効ビツト母線３０上の４つの有効ビツトＶ−Ａ〜
Ｖ−Ｄの値に応じて無効エントリ候補を１つ選択
する。その場合の優先順位はＡ，Ｂ，Ｃ，Ｄの順
である。４つの有効ビツトがすべて１であれば、
オア回路９５及び反転器９６の働きによつて線９
７上に全エントリ有効信号が発生される。勿論そ
のときは、無効エントリ候補信号は線９１〜９４
の何れにも発生されない。
線９７上の全エントリ有効信号は、第８図の置
換選択回路５１においてTID候補の選択を可能に
する。そのときTID候補が存在していなければ、
線４８上のLRU有効化信号によつてLRU候補の
選択が可能になる。
以上のように、回路１４，１８，５１，５２，
５３及び５４は、選択されたコングルエンス・ク
ラスに含まれる特定のエントリを置換えるための
優先順位機構を構成しており、無効エントリ候
補、TID候補及びLRU候補の順に選択する。即
ち、優先順位としては無効エントリ候補が最高で
あり、TID候補が中間でありLRU候補が最低であ
る。エントリを置換える場合、LRU候補は常に
存在しているが、無効エントリ候補及びTID候補
はそうとは限らない。キヤツシユ・デイレクトリ
１２のエントリが置換えられると、当然のことと
してキヤツシユ１３中の対応するエントリ（ライ
ン）も置換えられる。
第１０図はこれまで説明してきた動作の流れを
示したもので、図中「CC」は選択されたコング
ルエンス・クラスを表わし、「Ｙ」は肯定（イエ
ス）を表わし、「Ｎ」は否定（ノー）を表わして
いる。第１０図の意味するところはこれまでの説
明から明らかであろう。
【図面の簡単な説明】
第１図及び第２図は本発明の実施例を示すブロ
〓〓〓〓〓
ツク図、第３図はTIDの作成方法を示すブロツク
図、第４図はキヤツシユ・デイレクトリ１２から
選択されたコングルエンス・クラスの内容を示す
ブロツク図、第５図はTID比較回路１８の詳細を
示す回路図、第６図は変更候補選択回路５２の詳
細を示す回路図、第７図はTID候補選択回路５３
の詳細を示す回路図、第８図は置換選択回路５１
の詳細を示す回路図、第９図は無効エントリ候補
選択回路５４の詳細を示す回路図、第１０図は実
施例の動作の流れを示す流れ図、第１１図は本発
明を適用し得るMPシステムの一例を示すブロツ
ク図である。 〓〓〓〓〓

Claims (1)

    【特許請求の範囲】
  1. １ 専用のキヤツシユ、該キヤツミユをアクセス
    するためのキヤツシユ・デイレクトリ、及び実行
    中のタクスを表わすタスク識別子を発生する手段
    を各々有する複数の中央プロセツサを具備し、各
    中央プロセツサで前記キヤツシユ及び前記キヤツ
    シユ・デイレクトリのエントリを置換える際に他
    の中央プロセツサのタスク識別子に関連するエン
    トリを選択する手段を各中央プロセツサに設けた
    ことを特徴とする多重プロセツサ・システム。
JP57214788A 1982-02-23 1982-12-09 多重プロセツサ・システム Granted JPS58154062A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US06/351,396 US4463420A (en) 1982-02-23 1982-02-23 Multiprocessor cache replacement under task control
US351396 1982-02-23

Publications (2)

Publication Number Publication Date
JPS58154062A JPS58154062A (ja) 1983-09-13
JPS6135584B2 true JPS6135584B2 (ja) 1986-08-13

Family

ID=23380742

Family Applications (1)

Application Number Title Priority Date Filing Date
JP57214788A Granted JPS58154062A (ja) 1982-02-23 1982-12-09 多重プロセツサ・システム

Country Status (4)

Country Link
US (1) US4463420A (ja)
EP (1) EP0088239B1 (ja)
JP (1) JPS58154062A (ja)
DE (1) DE3373569D1 (ja)

Families Citing this family (45)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4523275A (en) * 1980-11-14 1985-06-11 Sperry Corporation Cache/disk subsystem with floating entry
JPS5856277A (ja) * 1981-09-29 1983-04-02 Toshiba Corp 情報処理装置ならびに方法
USRE37305E1 (en) 1982-12-30 2001-07-31 International Business Machines Corporation Virtual memory address translation mechanism with controlled data persistence
JPS6079446A (ja) * 1983-10-06 1985-05-07 Hitachi Ltd 多重仮想記憶デ−タ処理装置
US4747043A (en) * 1984-02-10 1988-05-24 Prime Computer, Inc. Multiprocessor cache coherence system
US4821171A (en) * 1985-05-07 1989-04-11 Prime Computer, Inc. System of selective purging of address translation in computer memories
DE3650021T2 (de) * 1985-10-30 1995-03-09 Ibm Cache-Speicherübereinstimmungsvorrichtung mit Verriegelung.
US4829425A (en) * 1986-10-21 1989-05-09 Intel Corporation Memory-based interagent communication mechanism
US5553262B1 (en) * 1988-01-21 1999-07-06 Mitsubishi Electric Corp Memory apparatus and method capable of setting attribute of information to be cached
GB8814077D0 (en) * 1988-06-14 1988-07-20 Int Computers Ltd Data memory system
US5317716A (en) * 1988-08-16 1994-05-31 International Business Machines Corporation Multiple caches using state information indicating if cache line was previously modified and type of access rights granted to assign access rights to cache line
US5043885A (en) * 1989-08-08 1991-08-27 International Business Machines Corporation Data cache using dynamic frequency based replacement and boundary criteria
US5125085A (en) * 1989-09-01 1992-06-23 Bull Hn Information Systems Inc. Least recently used replacement level generating apparatus and method
US5109496A (en) * 1989-09-27 1992-04-28 International Business Machines Corporation Most recently used address translation system with least recently used (LRU) replacement
US7610452B1 (en) * 1989-10-31 2009-10-27 Canon Kabushiki Kaisha Data processing system wherein data is stored in a memory and an external storage in parallel
JPH0786848B2 (ja) * 1989-11-01 1995-09-20 三菱電機株式会社 キャッシュメモリ
US5197139A (en) * 1990-04-05 1993-03-23 International Business Machines Corporation Cache management for multi-processor systems utilizing bulk cross-invalidate
JPH05108484A (ja) * 1990-06-07 1993-04-30 Intel Corp キヤツシユメモリ
JP3009430B2 (ja) * 1990-07-09 2000-02-14 キヤノン株式会社 プロセッサおよびそのキャッシュメモリ制御方法
JP3236287B2 (ja) * 1990-11-29 2001-12-10 キヤノン株式会社 マルチプロセッサシステム
JPH07104791B2 (ja) * 1991-12-18 1995-11-13 インターナショナル・ビジネス・マシーンズ・コーポレイション タスク状態構築方法
US5530823A (en) * 1992-05-12 1996-06-25 Unisys Corporation Hit enhancement circuit for page-table-look-aside-buffer
US5455922A (en) * 1992-07-28 1995-10-03 International Business Machines Corporation Dynamic validity facility for fast purging of translation bypass buffers
FR2699304B1 (fr) * 1992-12-10 1996-03-15 Nec Corp Procede de repartition de processus.
CA2107056C (en) * 1993-01-08 1998-06-23 James Allan Kahle Method and system for increased system memory concurrency in a multiprocessor computer system
JPH06282488A (ja) * 1993-03-25 1994-10-07 Mitsubishi Electric Corp キャッシュ記憶装置
GB9307359D0 (en) * 1993-04-08 1993-06-02 Int Computers Ltd Cache replacement mechanism
US5539893A (en) * 1993-11-16 1996-07-23 Unisys Corporation Multi-level memory and methods for allocating data most likely to be used to the fastest memory level
US5555379A (en) * 1994-07-06 1996-09-10 Advanced Micro Devices, Inc. Cache controller index address generator
US5577227A (en) * 1994-08-04 1996-11-19 Finnell; James S. Method for decreasing penalty resulting from a cache miss in multi-level cache system
US5606688A (en) * 1994-08-31 1997-02-25 International Business Machines Corporation Method and apparatus for dynamic cache memory allocation via single-reference residency times
US6145057A (en) * 1997-04-14 2000-11-07 International Business Machines Corporation Precise method and system for selecting an alternative cache entry for replacement in response to a conflict between cache operation requests
US6049849A (en) * 1997-04-14 2000-04-11 International Business Machines Corporation Imprecise method and system for selecting an alternative cache entry for replacement in response to a conflict between cache operation requests
US6370585B1 (en) * 1997-09-05 2002-04-09 Sun Microsystems, Inc. Multiprocessing computer system employing a cluster communication launching and addressing mechanism
US6044430A (en) 1997-12-17 2000-03-28 Advanced Micro Devices Inc. Real time interrupt handling for superscalar processors
US6185658B1 (en) * 1997-12-17 2001-02-06 International Business Machines Corporation Cache with enhanced victim selection using the coherency states of cache lines
US6269425B1 (en) * 1998-08-20 2001-07-31 International Business Machines Corporation Accessing data from a multiple entry fully associative cache buffer in a multithread data processing system
US6643741B1 (en) * 2000-04-19 2003-11-04 International Business Machines Corporation Method and apparatus for efficient cache management and avoiding unnecessary cache traffic
US6738864B2 (en) * 2000-08-21 2004-05-18 Texas Instruments Incorporated Level 2 cache architecture for multiprocessor with task—ID and resource—ID
JP4226816B2 (ja) * 2001-09-28 2009-02-18 株式会社東芝 マイクロプロセッサ
JP3936672B2 (ja) * 2003-04-30 2007-06-27 富士通株式会社 マイクロプロセッサ
US20060138830A1 (en) * 2004-12-23 2006-06-29 Cho-Hsin Liu Barrel shaped chair of a racing car
US7366847B2 (en) * 2006-02-06 2008-04-29 Azul Systems, Inc. Distributed cache coherence at scalable requestor filter pipes that accumulate invalidation acknowledgements from other requestor filter pipes using ordering messages from central snoop tag
US7941610B2 (en) 2006-04-27 2011-05-10 Hewlett-Packard Development Company, L.P. Coherency directory updating in a multiprocessor computing system
US11907138B2 (en) 2021-12-31 2024-02-20 Qualcomm Incorporated Multimedia compressed frame aware cache replacement policy

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3735360A (en) * 1971-08-25 1973-05-22 Ibm High speed buffer operation in a multi-processing system
US3771137A (en) * 1971-09-10 1973-11-06 Ibm Memory control in a multipurpose system utilizing a broadcast
US3848234A (en) * 1973-04-04 1974-11-12 Sperry Rand Corp Multi-processor system with multiple cache memories
US3898624A (en) * 1973-06-14 1975-08-05 Amdahl Corp Data processing system with variable prefetch and replacement algorithms
US3845474A (en) * 1973-11-05 1974-10-29 Honeywell Inf Systems Cache store clearing operation for multiprocessor mode
JPS5373927A (en) * 1976-11-10 1978-06-30 Fujitsu Ltd Replacing system of intermediate buffer memory
US4228503A (en) * 1978-10-02 1980-10-14 Sperry Corporation Multiplexed directory for dedicated cache memory system
US4317168A (en) * 1979-11-23 1982-02-23 International Business Machines Corporation Cache organization enabling concurrent line castout and line fetch transfers with main storage
US4322795A (en) * 1980-01-24 1982-03-30 Honeywell Information Systems Inc. Cache memory utilizing selective clearing and least recently used updating
US4399506A (en) * 1980-10-06 1983-08-16 International Business Machines Corporation Store-in-cache processor means for clearing main storage
US4394731A (en) * 1980-11-10 1983-07-19 International Business Machines Corporation Cache storage line shareability control for a multiprocessor system
DE3177181D1 (de) * 1980-11-10 1990-06-21 Ibm Anordnung zur erkennung und verarbeitung von synonymen in cache-speichern.

Also Published As

Publication number Publication date
EP0088239B1 (en) 1987-09-09
EP0088239A3 (en) 1985-09-18
DE3373569D1 (en) 1987-10-15
JPS58154062A (ja) 1983-09-13
EP0088239A2 (en) 1983-09-14
US4463420A (en) 1984-07-31

Similar Documents

Publication Publication Date Title
JPS6135584B2 (ja)
US4484267A (en) Cache sharing control in a multiprocessor
US5490261A (en) Interlock for controlling processor ownership of pipelined data for a store in cache
US5761734A (en) Token-based serialisation of instructions in a multiprocessor system
US6772316B2 (en) Method and apparatus for updating and invalidating store data
US5584013A (en) Hierarchical cache arrangement wherein the replacement of an LRU entry in a second level cache is prevented when the cache entry is the only inclusive entry in the first level cache
EP0349122B1 (en) Method and apparatus for filtering invalidate requests
US4445174A (en) Multiprocessing system including a shared cache
US6457101B1 (en) System and method for providing the speculative return of cached data within a hierarchical memory system
US7266647B2 (en) List based method and apparatus for selective and rapid cache flushes
US7613884B2 (en) Multiprocessor system and method ensuring coherency between a main memory and a cache memory
JPH0743670B2 (ja) ストアスルーキャッシュ管理システム
EP0347040A1 (en) Data memory system
US5850534A (en) Method and apparatus for reducing cache snooping overhead in a multilevel cache system
US6044447A (en) Method and apparatus for communicating translation command information in a multithreaded environment
US5361342A (en) Tag control system in a hierarchical memory control system
US6973541B1 (en) System and method for initializing memory within a data processing system
US5479629A (en) Method and apparatus for translation request buffer and requestor table for minimizing the number of accesses to the same address
US6810473B2 (en) Replacement algorithm for a replicated fully associative translation look-aside buffer
EP0173909B1 (en) Look-aside buffer least recently used marker controller
US5619673A (en) Virtual access cache protection bits handling method and apparatus
KR100380674B1 (ko) 멀티프로세서 시스템에서의 기록-통과 기억 동작동안 캐시코히어런스를 유지하는 방법 및 시스템
GB2307319A (en) Dual-directory virtual cache
US6480940B1 (en) Method of controlling cache memory in multiprocessor system and the multiprocessor system based on detection of predetermined software module
US6934810B1 (en) Delayed leaky write system and method for a cache memory