JPH04191946A - スヌープキャッシュメモリ制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、共有バス型マルチプロセッサ７ステムにおけ
るキャッシュメモリの制御方式に関するものであり、特
に、共有バスを介して共有メモリに接続された各キャッ
シュメモリ相互の記憶内容の一貫性（ｃｏｈｅｒｅｎｃ
ｅ　）を効果的に保証するスヌープキャッシュメモリ制
御方式に関する。

〔従来の技術〕

複数のプロセッサが共有バスを介して共有メモリに接続
された共有バス型マルチプロセッサシステムにおいては
、多くの場合、各要素プロセッサ毎にキャッシュメモリ
を有する。この場合、これらのキャッシュメモリ相互間
の記憶内容に対する更新の一貫性が問題となる。このた
め共有バス型マルチプロセッサシステムにおいては共有
バスのトランザクシロンを各キャッシュメモリが監視し
、各プロセッサシステム毎にローカルにキャッシュメモ
リ内の情報更新を管理して上記一貫性を保つようにして
いる。このような一貫性を保証するためのキャッシュメ
モリの制御方式をスヌーブキャソシュ制御方式と呼ぶ。

このスヌープキャ１．シュ制御方式にはキャッシュメモ
リの管理についていくつかの制御方法が提案され、評価
か試みられている（たとえば、　　Ｃａｃｈｅ　Ｃｏｈ
ｅｒｅｎｃｅ　Ｐｒｏｔｏｃｏｌｓ：Ｅｖａｌｕａｔｉ
ｏｎ　ｔｌｓｉｎｇ　ａ　Ｍｕｌｔｉｐｒｏｃｅｓｓｏ
ｒ　ＳｉｍｕｌａｔｉｏｎＭｏｄｅｌ″、　Ｊａｍｅｓ
　Ａｒｃｈｉｂａｌｄ、他＋　ａｃａ＋　Ｔｒｎａｓａ
ｃＬｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍ
ｓ、　１９８６．　Ｎｏｖｅｍｂｅｒ、　Ｖｏｌｕｍｅ
４．　Ｎｕｍｂｅｒ４．　ｐｐ、２７３−２９８）。

従来のスヌーブキャッシュメモリ制御方式（７）Ｌ）ず
れにおいても、キャッシュメモリ相互間で互いに共有し
ているブロック（これを共有ブロックと呼ぶ）の写しを
複数のキャッシュメモリで持つことは許している。一方
、共有ブロックの中のデータ（これを共有データと呼ぶ
）を書き換えた場合の扱い方として、他のキャッシュメ
モリの共有ブロックを無効にする無効化方式と、他のキ
ャッシュメモリの古いブロックを新たなブロックに更新
する更新方式との２つの方式が提案されている。

しかしながら、どちらの方式もすべての共有データの取
扱いに対しても有効というわけではなく、ブロモ、す間
で共有データの受は渡しが頻繁に起こる場合には更新方
式が有利であるが、データの受は渡しの頻度が少ない場
合は無効化方式が有利な場合がある。

従って、スヌープキャノシュの制御方式として無効化方
式か更新方式かのいずれかに固定した場合、ある種のデ
ータの受渡しには有効であるが他のデータについては効
率か悪くなることがある。

このため上記２方式を切り換えることが提案されている
。この切り換え方法としては、キャシュメモリ全体とし
てではなく、ページと呼ぶキャッシュメモリ内の一定の
記憶領域ごとに無効化方式か更新方式かのどちらの制御
方式をとるかの情報をソフトウェアで指定し、その指定
に従ってページ単位でどちらかの方式に切り換える方式
が提案されている（たとえば、［細粒度並列実行支援機
構」、松本、（社）情報処理学会「情報処理学会研究報
告Ｊ、８９−ＡＲＣ−７７，１９８９年７月１３日１４
日、第９１〜９８ページ）。

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

しかしながら、以上述べた切換方式では共有データの特
性によってデータの記憶領域を分けると共に、無効化方
式または更新方式のどちらを使用するかをユーザが指定
する必要があり、この指定が厄介である。

また、事前によく検討してプログラムの実行開始前にペ
ージ単位で更新方式が無効化方式に固定的に指定したと
しても、プロセッサ間での共有データの受は渡しの頻度
（共有データの特性）が動的に変化する場合もありうる
ため、静的ないし固定的に指定した更新方式または無効
化方式では有効に働かない場合に遭遇するという問題が
ある。

したがって、本発明は、該当するブロックを更新するか
無効にするかの決定をハードウェアで行なわせることに
よって、共有データの特性変化に対しても、効率の良い
スヌープキャッシュメモリ制御方式を提供することを目
的とするものである。

〔課題を解決するための手段〕

上述した問題を解決するため、本発明は、それぞれがキ
ャシュメモリおよびプロセッサを有する複数の要素プロ
セッサの各キャ／ユメモリが共有バスを介して共有メモ
リに接続され、各キャシュメモリが共有バスのトランザ
クションを監視して当該キャシュメモリ内の情報を管理
するスヌーブキャッンユ制御方式において、あるキャッ
シュメモリ内の共有データが書き換えられる際に、同じ
共有データを含むブロックを有する他のキャッシュメモ
リが、前記ブロックを更新するか無効にするかの決定を
プロセッサによるブロックの使用状況により動的に判断
する手段を設けたものである。

〔作用〕

キャッシュメモリの情報管理、すなわち、更新方式によ
るか無効化方式によるかの切換判断をプロセッサがブロ
ックを使用する状況（頻度）に応じて動的に行う。

より具体的に述べると、更新型のスヌーブキャッシュに
おいて、−変地のキャッシュメモリが書き換えられたこ
とに伴なって更新されたブロックは、次に他のキャッシ
ュメモリによって同じブロツクが更新されるまでにプロ
セッサによって一度もアクセスされていなければ、その
後もプロセッサがそのブロックを使用する可能性は少な
いと考えられる。したがって、そのようなブロックは無
効化しても効率的にあまり問題とはならず、再び使用す
ることが必要になった時点で改めてキャッシュメモリに
登録したほうが全体としては効率がよくなる。

このように、本発明は更新型スヌーブキャッシニメモリ
制御方式で、キャッシュメモリ内のブロックをプロセッ
サが一度以上アクセスした場合にセ、ツトされるフラグ
（アクセスフラグ）をブロック単位に設け、他のキャッ
シュメモリで同じブロックが書き換えられた時点までに
自己のアクセスフラグがセットされていれば自己のブロ
ックを更新するが、アクセスフラグがセットされていな
ければ自己のブロックを無効化するとともに、ブロック
を更新したか無効化したのかいずれかの情報を更新要求
元のキャッシュメモリに知らせることによって一貫性を
保つように構成する。

すなわち、本発明は共有ブロックの不要な更新を極力低
減することにより、共有バスの使用効率を向上させると
いう構想に基づくものである。

〔実施例〕

第２図に示すように本発明の実施例としての共有バス型
キャッシュメモリ制御方式は、共有メモリ５０と、複数
の要素プロセッサ６ｏ〜７０を有しており、各プロセッ
サシステム、たとえば、要素プロセッサ６０はスヌーブ
キヤツシュメモリ６１とプロセッサ６２とを有している
。そして、各キャッシュメモリ６１〜７１が共有メモリ
５０と共有バス８０を介して接続されている。

共有バス８０は、共有メモリ、キャッシュメモリに共通
するアドレスを転送する共有アドレスバス線１、データ
をブロック単位で転送する共有データバス線２、読み込
み要求や書き込み要求を転諾する共有バス制御線３、お
よびキャッシュメモリ相互間の一貫性を保つためデータ
を共有していることを表すシェアード線４からなり、図
示の如く共有メモリ５ｏと各キャッシュメモリ６１〜７
１との間を接続している。

また、第３図に示すように、本発明の実施例のスヌー７
’−１−ヤ・ｙシュメモリ制御方式におけるアドレスは
、タグ部４１．インデックス部４２．オフセット４３か
ら構成されており、共有メモリ５゜中のブロック格納位
置はタグ部４１とインデックス部４２で特定され、ブロ
ック中のデータはオフセット４３によって特定される。

また、キャッシュ中のブロックの格納位置はインデック
ス部４２によって特定される。

各キャッシュメモリは第１図に示す構成となっている。

第１図において、キャッシュメモリは、プロセッサから
の要求を処理するためのアドレスが格納されるアドレス
レジスタ１０．アドレスレジスタ１０の出力に接続され
たバッファ１７、共有バス８０からの要求を処理するた
めのアドレスが格納される共有アドレスレジスタ１４、
アドレスレジスタ１０または共有アドレスレジスタ１４
の値と後述するタグメモリｌｌａの値とを比較してキャ
ツシュヒツトを判定するヒツト判定部１１、後に詳述す
るステータスメモリ１２、キャッシュメモリ１３、共有
データバス線２上のデータ、キャソンユメモリ１３内の
データ及びデータレジスタ１５のデータを相互でやり取
りするための双方向バッファ１９、プロセッサに読み込
ませるデータおよびプロセッサからのデータを一時的に
格納するデータレジスタ１５、キャッシュを統括制御す
るキャッシュ制御部１６が、図示される如く接続されて
構成されている。

マタ、キャッンユ制御部１６には、アクセス要求線５、
共有バス制御線３゛およびシェアード線４が図示の如く
接続されている。また、共有データバス線２が双方向バ
ッファ１９を介してキャッシュメモリ１３およびデータ
レジスタ１５接続され、共有アドレスバス線１がアドレ
スレジスタ１０に接続されたバッファ１７に接続される
と共に、共有アドレスレジスタ１４およびヒツト判定部
１１に接続されている。

ヒツト判定部１１にはタグメモリｌｌａとキャッシュメ
モリのヒツト判定回路が含まれている。

タグメモリｌｌａにはキャツンユメモリ１３に格納され
ている各ブロックに対応するアドレスのタグ部４１（第
３図参照）が格納されている。

また、上記ステータスメモリ１２はプロセッサがそのブ
ロックを１度以上アクセスしたことを表すアクセスフラ
グ２０、他のキャッシュメモリがそのブロックを共有し
ていることを表すシエアードフラグ２１、キャッシュメ
モリ内の該ブロックが存効なものであることを表すバリ
ッドフラグ２２、プロセッサがそのブロックに書き込み
を行ったことを表すダーティフラグ２３、および、その
ブロックの所有者であることを表すオーナフラグ２４か
らなる。これらのフラグの判定及び値のセクトはキャッ
シュ制御部１６によって行われる。

ダーティフラグ２３はプロセッサからの書き込み要求が
あった時に「１」にセットされ、他のキャッシュからそ
のブロックの更新要求があった時およびキャッンユから
追い出される時「０」にセットされる。またオーナフラ
グ２４はプロセッサからの書き込み要求があった時およ
び共有メモリよりそのプロ、りを読み出した時「１」に
セットされ、他のキャッシュからそのブロックの更新要
求があった時およびキャッシュから追い出される時「０
」にセットされる。これらのフラグの管理は本発明に直
接関与しないため以下の説明では省略しである。

ブロモ、すからのデータの読み出し及び書き込み要求は
アクセス要求線５を通してキャッシュ制御部１６に知ら
される。また共有バス８０上の他のキャッシュメモリや
共有メモリとキャッシュ制御部１６とのデータの読み出
し及び書き込み要求は共有バス制御線３を通して相互に
行われる。

ヒツト判定部１１のタグメモリ１１ａ５ステータスメモ
リ１２及びキャッシュメモリ１３に対するデータの読み
出しおよび書き込み番地はアドレスレジスタ１０または
共有アドレスレジスタ１４のインデックス部４２（第３
図参照）で指定される。

キヤ・７シユメモリにヒツトしたことの判定は、ヒツト
判定部１１においてアドレスレジスタ１０または共有ア
ドレスレジスタ１４のインデックス部で指定されたタグ
メモリｌｌａの値とアドレスレジスタ１０または共有ア
ドレスレジスタ１４のタグ部４１の値が一致したことを
示す信号３０と、アドレスレジスタ１０または共有アド
レスレジスタ１４のインデックス部で措定されたステー
タスメモリ１２のバリッドフラグ２２が「１」で有るこ
とを示す信号３１とをキャッシュ制御部１６で調べるこ
とにより行われる。以後、特に断らない限りプロセッサ
からの要求を処理する場合のアドレスは、アドレスレジ
スタ１０にセットされており、共有バス８０からの要求
を処理する場合のアドレスは共有アドレスレジスタ１４
にセットされているものとする。また処理に応じてどち
らかのレジスタ１０．１４が選択されキャッシュメモリ
１３゜ステータスメモリ１２．ヒツト判定部１１の各部
にアドレスを供給するものとする。

なお、上述したヒツト判定部１１．ステータスメモリ１
２．キャッシュ制御部１６等で、本発明の、該当するブ
ロックを更新するか無効にするかの決定をブロモ、すに
よるブロックの使用状況により動的に判断する手段が構
成される。

次にプロセッサまたは共有バスからの要求にしたがって
行われるキャッシュメモリ及びアクセスフラグの動作を
第４図を用いて説明する。

キャッシュ制御部１６は、まず、出力された要求がプロ
セッサからの要求であるのか、共有バスからの要求であ
るのかを判断する（ステップ４０１）。

プロセッサからの要求であれば、更にその要求内容が読
み出し要求であるのか、書き込み要求であるのかの判断
を行う（ステップ４０２）。読み出し要求であれば、そ
の読み出し要求の判断結果に応じて（１）プロセッサか
らの読み出し要求でキャツシュヒツトしたく要求された
データがキャッシュにある）場合、または（２）プロセ
ッサからの読み出し要求でキヤ・７シユミスした（要求
されたデータがキャッシュにない）場合へ分岐する（ス
テップ４０３）。

ステップ４０２で書き込み要求であると判断されれば、
その書き込み要求の結果に応じて（３）ブロモ、すから
の書き込み要求でキャツシュヒツトした場合、または（
４）プロセッサからの書き込み要求でキャッシュミスし
た場合へ分岐する（ステ丁ズ、ブ４０４）。

１１，１ ゴー’、：　１また、ステップ４０１で要求が共有バス
からの′要゛求であると判断されれば、更にその要求内
容が一更新要求であるのか、読み出し要求であるのかの
判断を行う（ステップ４０５）。更新要求であれば、そ
の更新要求でキャツシュヒツトした（要求されたブロッ
クがキャッシュにある）とき、（５）共有バスからの更
新登録要求でキャツシュヒツトした場合へ進む（ステッ
プ４０６）。読み出し要求であれば、その読み出し要求
でキャツシュヒツトした（要求されたブロックがキャッ
シュにある）とき、（６）共有バスからの読み出し要求
でキャツシュヒツトした場合へ進む（ステップ４０７）
。なお、ステップ４０６，４０７でキャッシュミスした
場合は何もしない。

このように主なものとして６通りの場合が考えられるが
、この内、特に（５）の場合がキャッンユ内の共有ブロ
ックを無効化するか更新するかの選択を行う本処理フロ
ーとなり、（５）を除＜（１）〜（６）の場合が、その
選択を可能にするための前処理的フローなる。以下、こ
れらの場合を個別的に説明する。

（１）プロセッサからの読み出し要求でキャツシュヒツ
トした場合 プロセッサによってアクセスされたので、アドレスレジ
スタ１０で指定されたステータスメモリ１２のアクセス
フラグ２０を「１」にセントするとともに、ヒツトした
データをキャッシュメモリ１３よりデータレジスタ１５
にセットする（ステップ４１１．４．１２）。

（２）プロセッサからの読み出し要求でキャッシュミス
した場合 説明順序が逆になるが、便宜上、途中のステ。

プ４２６から説明する。オフセットを除くアドレスレジ
スタ１０の値を共有アドレスバス線１に出力し、かつ共
有バス制御線３にキャッシュメモリ又は共有メモリへの
読み出し要求を出すことにより、対応するブロックを共
有データバス線２より読み込んでキャッシュメモリ１３
に書き込む（ステップ４２６，４２７，４２８）。また
ヒツト判定部１１のタグメモリｌｌａにアドレスレジス
タ１０のタグ部４１をセットするとともに、バリッドフ
ラグ２２に「１」をセットするが、シェアードフラグ２
１は共有バス８０からブロックを読み込む際、シェアー
ド線４が１になっていれば「１」を、そうでない場合は
「０」をセットする（ステップ４３０，４３１，４３２
，４３３，４３４）。

ここで、プロセッサによるアクセス要求に対する処理が
行われ、上記で書き込まれたブロックにプロセッサから
要求されたデータがあるためキャツシュヒツトと同様に
、アドレスレジスタ１０で指定されたステータスメモリ
１２のアクセスフラグ２０を「１」にセットすると共に
、上記データをキャッシュメモリ１３よりデータレジス
タ１５にセットする（ステップ４３５，４３６）。

なお、キャッシュミスしたデータをキャッシュメモリに
登録するにあたって、現在あるキャッシュメモリ内のブ
ロックを追い出す必要がある場合、上記処理（ステップ
４２６）の前に以下の処理を行う。なお、追い出すか上
書きするかは、キャッシュメモリ内の該ブロックに対す
るダーティフラグ２３によって判断し、ダーティフラグ
２３が「１」の場合に追い出す。

ブロックの追い出しか、上書きかを判断して、追い出し
であれば、追い出すブロックのアドレスのタグ部４１を
ヒツト判定部１１のタグメモリ１１ａより読み出し、そ
の値とアドレスレジスタ１０のインデックス部４２の値
とを共有アドレスバス線１に出力する（ステップ４２１
，４２２，４２３）。そして、キャッシュメモリ１３の
ブロックを共有データバス線２に出力し、共有バス制御
信号線３により書き込み要求を共有メモリに送出する（
ステップ４２４，４２５）。

（３）プロセッサからの書き込み要求でキャツシュヒツ
トした場合 キャッシュメモリ１３にデータレジスタ１５よリデータ
を書き込む（ステップ４４１）。またアドレスレジスタ
ｌＯで指定されたステータスメモリ１２のンエアードフ
ラグが「１」か否かを判断する（ステップ４４２）。シ
エアードフラグが「１」ならばオフセットを除いたアド
レスレジスタ１０のＭ　ヲ共有アドレスバス線１に、ア
ドレスレジスタ１０で指定されたキャッシュメモリ１３
のブロックを共有データバス線２に出力すると共に、共
有バス制御線３を通して他のキャッシュメモリに共有ブ
ロックの更新要求を送出する（ステップ４４３．４４４
）。さらにシェアード線４を監視し、シェアード線４が
「１」になればステータスメモリ１２のンエアードフラ
グ２１を「１」に、そうでない場合はｒＯＪにセットす
る（ステップ４４５．４４６，４４７）。また、ブロモ
・ツサからアクセスされたので、アクセスフラグ２０を
「１」にセットする（ステｙ　７’　４４　ａ　）。

（４）プロセッサからの書き込み要求でキャッシュミス
した場合 データレジスタ１５へのデータのセットおよびアクセス
フラグのセット（ステップ４３５□　４３６）を除いて
、読み込み要求でキャッシュミスした場合の（２）と同
じ処理を行った後、書き込み要求でキャツシュヒツトし
た場合の（３）と同じ処理を行う。

（５）共有バスからの更新要求でキャ／シュヒ。

トした場合 共有アドレスレジスタ１４で指定されたステータスメモ
リ１２のアクセスフラグ２０が「１」か否かを判定する
（ステップ４５１）。アクセスフラグ２０が「１」なら
ば、他のキャッシュにより更新されたブロックをプロセ
ッサが一度以上アクセスしたと判断して、プロ、りを更
新する。すなわち共有データバス線２上のブロックをキ
ャッシュメモリ１３に取り込むと共に、シェアード線４
を「１」にし、また、更新されたことに伴い、アクセス
フラグ２０を「０」にセットする（ステップ４５２．４
５３）。またアクセスフラグ２０が「○Ｊの場合、−変
地のキャッシュが書き換えられたことに伴い更新された
ブロックが、次に他のキャッシュにより同じブロックが
更新されるまでにプロセッサによって一度もアクセスさ
れていないと判断して、ブロックを無効化する。すなわ
ち、データは取り込まずシェアード線４をｒＯＪにする
と共に、バリッドフラグ２２をｒＯＪにする。

（６）共有バスからの読み出し要求でキヤノンユヒ、ト
した場合 要求されたブロックを共有バスに供給する必要がある場
合、すなわち、複数のキャッシュにヒツトシタ場合、フ
ロックを供給するキャッシュを特定する必要が有る。こ
の特定をするため、オーナフラグ２４が「ｌＪか否かの
判別を行う（ステップ４６１）。オーナフラグ２４が「
１」ならばブロックの供給を行う。

オーナフラグ２４がｒｌＪの場合、キャッシュメモリ１
３よりブロックを共有データバス線２上に出力する（ス
テップ４６２）。また、オーナフラグ２４にかかわらず
シェアード線４を「１」にする（ステップ４６３）。ス
テータスメモリ１２のバリ１ドフラグ２２、シェアード
フラグ２１及びアクセスフラグ２０はその時の状態を保
持する（ステップ４６４）。

（７）共有バスからの更新要求にたいしてキャッ／ユが
ヒ、トシない場合、何もしない。

〔発明の効果〕

以上述べたように、本発明によれば他のキャッシュメモ
リにある共有データが書き換えられた際、同じブロック
を持つキャッシュメモリをｌＦするか無効化するかをプ
ロセッサによるブロックの使用状況をもとに動的に判断
して、この判断に基づいてキャッシュメモリを管理して
いるため、データの特性変化による依存性が低下し、共
有バスの使用効率を向上できる。

【図面の簡単な説明】

第１図は第２図におけるキャッシュメモリの構成の実施
例を示すプロ・Ｉり図、第２図は本発明の実施例のスヌ
ーブキヤツシュメモリ制御方式が適用サレる共有バス型
マルチプロセッサシステムの構成図、第３図は第２図に
おけるアドレスの構成例を示す図、第４図は本実施例の
システム動作を示すフローチャートである。 １は共有アドレスバス線、２は共有データバス線、３は
共有バス制御線、４はシェアード線、１０はアドレスレ
ジスタ、１１はヒツト判定部、１２はステータスメモリ
、１３はキャッシュメモリ、１５はデータレジスタ、１
６はキャッシュ制御部、２ｏはアクセスフラグ、２１は
シエアードフラグ、２２はバリッドフラグ、２３はダー
ティフラグ、２４はオーナフラグである。 特許出願人　工業技術院長　杉油　　賢（１）７°叶１
号からの　　　　　　（２）７°０セ１４からの本実施
例の動作７０− 第４図（その２） （５）共有へ゛スからの 本実施例の動作７１ 第４図（その４ （６）共有ハ゛スからの 読み出し要求で Ａ！７ノスヒツトした

Claims (1)

1. 【特許請求の範囲】 それぞれがキャシュメモリおよびプロセッサを有する複
   数の要素プロセッサからなるシステムの各キャシュメモ
   リが共有バスを介して共有メモリに接続され、各キャシ
   ュメモリが共有バスのトランザクションを監視して当該
   キャシュメモリ内の情報を管理するスヌープキャッシュ
   制御方式において、 あるキャッシュメモリ内の共有データが書き換えられる
   際に、同じ共有データを含むブロックを有する他のキャ
   ッシュメモリが、該当するブロックを更新するか無効に
   するかの決定をプロセッサによるブロックの使用状況に
   より動的に判断する手段を設けて、 ブロックを動的に更新または無効化するように構成した
   ことを特徴とするスヌープキャッシュメモリ制御方式。