JPH07152646A

JPH07152646A - 記憶階層レベル間での交換のコヒーレンシー管理方法

Info

Publication number: JPH07152646A
Application number: JP6164406A
Authority: JP
Inventors: Sylvie Lesmanne; スイルビ・レスマンヌ; Alain Boudou; アラン・ブドウ; Kaszynski Anne; アンヌ・カズインスキ
Original assignee: Bull SAS
Current assignee: Bull SAS
Priority date: 1993-07-15
Filing date: 1994-07-15
Publication date: 1995-06-16
Also published as: EP0636988A1; DE69421340T2; DE69421340D1; EP0636988B1; FR2707774B1; FR2707774A1; US5568633A

Abstract

(57)【要約】【目的】記憶階層のレベル間で交換のコヒーレンシー
を管理するための最適な方法を提供する。【構成】階層の上位レベルと下位レベルとに接続され
た少なくとも１つの中間レベルを有する記憶階層のレベ
ル間での交換に適用される方法。階層の各レベルはメモ
リ（３、５、６）からなる。このメモリはアドレス（Ａ
ｄ）によって識別される情報（１１）を格納した複数の
ブロック（１０）からなり、上位レベルおよび中間レベ
ルにあるメモリのブロックは下位レベルの対応するアド
レスにあるブロック内の情報のコピーを格納している。
上位レベルにあるメモリのブロック（１０．３２）内の
情報を修正する際、上位レベルにある他のメモリの対応
するアドレスにある情報の少なくとも一部を無効にし、
更新の有用性に基づいて中間レベルおよび下位レベルの
対応するアドレスにある情報の更新あるいは無効化を管
理する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、少なくとも３つのレベ
ルを有する記憶階層のレベル間での交換のコヒーレント
な管理方法に関する。

【０００２】

【従来の技術】最高速の最も高価な技術によるメモリの
容量を減らした記憶階層の諸レベルを設け、この階層の
連続したレベルのどこに置くかに応じて技術的コストに
反比例してメモリのサイズを増やしていき、あるいは常
に階層の最高速部分のメモリサイクルにほぼ匹敵するア
クセス時間で最も有用な情報を得られるのにちょうど十
分な容量のメモリを階層の最上位のレベルに使用して、
階層の全容量を階層の最下位のレベルにあるメモリすな
わち一般に最も安価な技術による最も大容量のメモリの
レベルの容量に等しくすることにより、総費用が法外な
ものになるという問題を生じずに、可能な限り大きなメ
モリ空間を持てるようにするための記憶階層を備える情
報処理アセンブリが知られている。

【０００３】通常の用語について考えると、各レベルは
複数のメモリに分かれており、このメモリ自体もアドレ
スによって識別される情報を格納した複数のブロックに
分かれている。階層の最下位レベルにあるアドレスは情
報の所在地に対応している。一方、階層の他のレベルに
あるブロックに格納されたこの情報のコピーも同じアド
レスに関連しているが、当該メモリの管理処理装置によ
って決められた任意の場所に格納されている。

【０００４】

【発明が解決しようとする課題】このような記憶階層で
は、下位レベルにあるブロックの同一の初期情報のコピ
ーが複数存在し、これらのコピーが階層の上位レベルに
ある異なるブロックで修正された場合に、コピーのコヒ
ーレンシーの管理の問題が生じる。

【０００５】情報の管理のコヒーレンシーを保証するた
めに、上位レベルにあるブロックで情報を修正した場合
には、階層の上位レベルにある対応するブロックに格納
された情報を更新するかあるいは無効化するのが普通で
ある。更新には、情報の修正が行われなかったメモリに
格納されている情報に対する問合せ時に発生するミスヒ
ットを避けることができるという利点がある。しかしな
がら、この方法では修正を行う毎に情報を更新しなけれ
ばならず、メモリ間をつなぐ信号線上でのメッセージの
ビットレートが極めて大きくなるため、更新することで
情報処理装置の動作時間を犠牲にしなければならないと
いう欠点もある。一方、無効化は、情報を何回か修正す
る間に１回しか行わなくてよいので情報処理装置の動作
時間の点では有利であるが、情報が無効になったメモリ
での問合せの成功率は落ちる。

【０００６】実際の情報処理アセンブリでは、記憶階層
の汎用管理システムのレベルでの命令やアプリケーショ
ンプログラムの命令によって、更新または無効化の処理
プロトコルを予め定めてある。従って、必要に応じて記
憶階層のレベル間をつなぐ信号線上のメッセージのビッ
トレートを最適化するように処理プロトコルを適合させ
ることが好ましいことは明らかである。

【０００７】本発明の目的は、階層の上位レベルおよび
下位レベルに接続された少なくとも１つの中間レベルを
有する記憶階層のレベル間で交換のコヒーレンシーを管
理するための最適な方法を提供することにある。

【０００８】

【課題を解決するための手段】本発明によれば、階層の
上位レベルにあるメモリのブロックに格納された情報の
修正時に、階層の上位レベルにある他のメモリの対応す
るアドレスにある情報の少なくとも一部を無効化し、更
新の有用性に応じて階層の中間レベルおよび下位レベル
の対応するアドレスにある情報の更新や無効化を管理す
るコヒーレンシー管理方法が得られる。

【０００９】従って、情報が有用であり得るブロックに
格納された情報を維持しながら、更新に必要なメッセー
ジの交換を最小限に抑えることができる。本発明による
方法は、階層の中間レベルが例えば５０ＭＨｚで１６オ
クテットの転送能力を持つバスなどの待ち時間の短い信
号線によって階層の上位レベルと接続され、例えば２ギ
ガビット／秒の２本の直列接続からなる信号線などの高
ビットレートの信号線によって階層の下位レベルと接続
されている場合に特に好都合である。特に、このような
場合、修正後の情報が必要になった場合に待ち時間の短
い信号線を利用してこの修正後の情報を高速にアクセス
し、この待ち時間の短い信号線のあまり良くないビット
レートによる影響をなくすと共に、直列信号線の高ビッ
トレートを利用してこれらの信号線での長い待ち時間に
よる影響を最小限に抑えた更新を行う。

【００１０】階層における異なるレベルにあるメモリを
ノードに応じて再グループ化した情報処理アセンブリに
関する本発明の有利な態様によれば、修正されたブロッ
クが属するノードの階層の上位レベルにあるメモリに対
応するアドレスにあるブロックを更新すると共に、他の
ノード内の階層の上位レベルにあるメモリに対応するア
ドレスにあるブロックを無効にする。

【００１１】従って、情報処理アセンブリの残りの信号
線上のメッセージの流れを最小限に抑えながら、階層の
上位レベルにあるメモリが簡単にアクセスできることを
利用してこれらのメモリに対応するブロックを更新する
ことができる。

【００１２】階層の中間レベルの対応するアドレスにあ
るブロックに格納された情報のコピーを更新モードでプ
ロトコルに従って通常通り処理する情報処理アセンブリ
において交換の管理をさらに洗練された形で最適化する
ことを目的とした本発明の他の態様によれば、該ブロッ
クに格納された情報の第１のコピーあるいは情報の更新
を行う際に第１の状態になると共に、該ブロックに格納
された情報を利用する時には第２の状態になる有用ビッ
トを階層の中間レベルにある各ブロックに関連させ、階
層の下位レベルのあるアドレスにある情報を修正する際
に、階層の中間レベルの対応するアドレスにあるブロッ
クの更新を行うと共に、このアドレスにある先の更新の
有用性に応じて処理プロトコルが更新モードに維持さ
れ、あるいは無効化モードになり、この先の更新の有用
性は、更新の直前の同一アドレスのブロックでの有用ビ
ットの状態に応じて決定される。

【００１３】従って、有用ビットの状態から更新済み情
報が利用されておらず先に行われた更新が無駄であった
ことが分かると、処理プロトコルが対応するアドレスか
ら無効化モードに移り、後の修正の際に更新を効率よく
行なうことができる。

【００１４】本発明の実施態様の第１の形態によれば、
下位レベルに更新閾値を記憶し、第２の状態にある有用
ビットの比率が少なくとも更新閾値に等しい場合にはプ
ロトコルを更新モードに維持し、第２の状態にある有用
ビットの比率が更新閾値よりも小さい場合には無効モー
ドにする。

【００１５】本発明の実施態様の第２の形態によれば、
階層の下位レベルに第１の閾値および第２の閾値を記憶
し、第１および第２の閾値と比較することにより第１お
よび第２の状態にある有用ビットの実際の数に応じて処
理プロトコルを更新モードに維持しあるいは無効化モー
ドにする。

【００１６】具体的には、第２の状態にある有用ビット
の数が第２の閾値よりも小さい場合に、プロトコルを無
効化モードにする。

【００１７】第１および第２の状態にある有用ビットの
数がそれぞれ第１および第２の閾値よりも大きい場合に
は、プロトコルを更新モードに維持したまま、階層の上
位レベルにあるブロックに格納された情報を単発的に無
効化することが好ましい。

【００１８】本発明のさらに他の態様によれば、階層の
中間レベルにあるブロックに格納された情報のコピーを
更新モードにあるプロトコルで処理する場合に更新の有
用性に応じて変化すると共に、階層の中間レベルにある
ブロックに格納された情報のコピーを無効化モードにあ
るプロトコルで処理する場合にはミスヒットの性質に応
じて変化するコードを階層の下位レベルの各アドレスに
関連させる。更新の有用性は有用ビットの状態に応じて
決定され、ミスヒットの性質は階層の中間レベルにある
メモリ内の情報およびアドレスの有無あるいは該メモリ
のブロック内の無効な情報によって決定され、階層の下
位レベルにある当該アドレスのコードに応じてプロトコ
ルのモードを変える。従って、実際の状況を極めて細か
く解析することができると共に、更新モードから無効化
モードに移るだけでなく、ミスヒットの性質から判断し
て明らかに有用なものであると分かった場合には更新モ
ードに戻ることもできる。

【００１９】もちろん、更新の有用性を判断する際には
以下の実施例において説明するモードを利用する。

【００２０】

【実施例】図１を参照し、本発明による方法を共用メモ
リを使用する情報処理アセンブリに関して説明する。こ
の情報処理アセンブリでは、どの処理装置からもアクセ
ス可能なものでなければならない汎用メモリを、各処理
装置から直接あるいは間接的にアクセス可能なローカル
メモリに分散させている。以下に述べる実施例におい
て、処理装置およびメモリは、信号線を介して互いに接
続されたノードに従って再グループ化されている。

【００２１】図示の情報処理アセンブリは、一点鎖線の
矩形ブロックで示す３つのノードを含む。これらのノー
ドには参照符号１を付し、さらに各ノードを個々に区別
するために補助参照符号１、２、３を付す。よって、各
ノードはそれぞれ１．１、１．２、１．３となる。

【００２２】本発明を説明するためにここでは３つのノ
ードを示してあるが、本発明はこの数に限定されるもの
ではなく、後述する本発明による方法を使用すれば、多
数（その数は図示の例に限定されるものではない）の処
理装置を各々再グループ化して得られる極めて多数のノ
ードからなる群を実現することができる。本発明では処
理装置の総数に比例して性能が向上するが、従来の方法
を使用すると処理装置の数を増やしても、逆に性能はす
ぐに限界に達してしまう。

【００２３】図１を参照すると、各ノード１は参照符号
２を付した２つの命令処理装置を備えている。これらの
命令処理装置には２桁の補助参照符号を付し、各々どの
ノードに属するか（個々の補助参照符号の１０の位の数
字）を示す。また、各命令処理装置にはノードの内部で
順に番号（個々の補助参照符号の１の位の数字）を付し
てある。従って、ノード１．１に属する処理装置は参照
符号２．１１および２．１２、ノード１．２に属する処
理装置は参照符号２．２１および２．２２、ノード１．
３に属する処理装置は参照符号２．３１および２．３２
で示される。

【００２４】各処理装置は直接メモリに接続されてい
る。以下の説明では、このメモリを専用キャッシュまた
は階層の上位レベルにあるメモリと呼ぶ。「キャッシ
ュ」という用語は、情報処理アセンブリの汎用メモリの
あるアドレスに保持された情報のコピーを格納してお
き、命令処理装置が特定の情報を使用して命令を実行す
る際にこの命令の実行毎に汎用メモリから情報を機械的
に取り出してくる場合よりも高速に同じ情報を利用でき
るようにするためのブロックを有するメモリという意味
で用いられるのが普通である。本願明細書において使用
する「専用キャッシュ」あるいは「階層の上位レベルに
あるメモリ」という用語は、命令処理装置が直接接続さ
れているキャッシュを意味する。専用キャッシュには参
照符号３を付し、これらのキャッシュが接続された処理
装置の場合と同様に個々の専用キャッシュには以下のよ
うに参照符号を付す。すなわち、ノード１．１について
は３．１１および３．１２、ノード１．２については
３．２１および３．２２、ノード１．３については３．
３１および３．３２で専用キャッシュを示してある。

【００２５】専用キャッシュ３は各ノード内でパラレル
バスに接続されている。このパラレルバスには参照符号
４を付し、さらに個々のパラレルバスを区別するために
それぞれが属するノードに対応した補助参照符号を付
す。従って各パラレルバスを示す参照符号は４．１、
４．２、４．３となる。後述するノード内の全構成要素
についてこれと同じように参照符号を付す。このバス４
はノード内での単なる内部接続用であるので、以下の説
明ではこのバスをローカルバスと呼ぶ。ローカルバス４
は、例えば５０ＭＨｚで１６オクテットの転送能力を持
つバスなどの待ち時間の短いバスである。

【００２６】各ローカルバスはキャッシュ（以下、共用
キャッシュと呼ぶ）に接続されている。共用キャッシュ
は階層の中間レベルにあるメモリからなり、全体として
参照符号５で示され、その各々は参照符号５．１、５．
２、５．３で示されている。各ローカルバスは、また情
報処理アセンブリの汎用メモリの一部に接続されてい
る。汎用メモリの各部分がノード内にあることを示すた
めに、以下の説明ではこれらの部分をローカルメモリと
呼ぶ。ローカルメモリを参照符号６で示し、そのそれぞ
れを６．１、６．２、６．３とする。

【００２７】ここに図示する好ましい実施例において、
共用キャッシュ５およびローカルメモリ６は、７．１、
７．２、７．３で示されるパラレルバス７に接続されて
いる。以下の説明ではパラレルバス７をシステムバスと
呼ぶ。各システムバスは、８．１、８．２、８．３で示
される直列信号線制御装置８に接続されている。この直
列信号線制御装置は、ノード同士を接続するための直列
信号線９とシステムバスとの間のインタフェースをなし
ている。

【００２８】管理処理装置は異なるレベルのメモリの各
々に接続されているが、ここでは図面が細かくなりすぎ
るのを避けるために図示していない。階層の上位レベ
ル、階層の中間レベル、階層の下位レベルという呼び方
は、記憶階層内での各レベルの幾何的位置を示すもので
はなく、命令処理装置に対する多少なりとも直接的な関
係の重要度を示す。具体的には、ローカルメモリ６は物
理的にはむしろ共用キャッシュ５に隣接するような形で
配置されている。このようにするため、ノード内ではロ
ーカルメモリ６は直接ローカルバス４に接続されている
が、本発明ではローカルメモリの方を下位レベルのメモ
リにしていることに注意されたい。同一ノード内で別の
情報を同時にアクセスするために、例えばローカルメモ
リ６．２など同じノードのローカルメモリに格納されて
いる情報を、この場合であれば共用キャッシュ５．２な
どのノードの共用キャッシュにコピーする。この時、ノ
ード１．２の処理装置はローカルメモリ内の情報を直接
アクセスすることができるが、共用キャッシュ５．２に
格納されたコピーは他のノードのローカルメモリ内の情
報のコピー同様に階層の中間レベルにあるメモリ中のコ
ピーとみなされることは理解できよう。

【００２９】一般に、階層の下位レベルにあるローカル
メモリ６は、低コストの技術で得られる大容量のメモリ
である。一方、階層の上位レベルにある専用キャッシュ
３は、高価な技術によるメモリである。この専用キャッ
シュはアクセス速度は速いが、製造費用が法外に高くな
らないようにその相対的サイズはメモリ６のサイズより
もずっと小さい。

【００３０】次に動作について説明する。例えばブロッ
ク１０に格納されている情報やアドレスＡｄに関連した
ビット列１１で示される情報など最初からメモリ６に格
納されている情報は、階層の上位レベルにある対応する
ブロック（それぞれ１０．１、１０．３；１０．１１、
１０．２２、１０．３１および１０．３２）内に格納さ
れた情報を順次コピーしたものであり、命令処理装置に
おいて即座に利用できるようにこの命令処理装置からの
要求に応じて同一のアドレスＡｄと関連させてある。従
って、図示の例では情報Ａは、階層の中間レベルにある
対応する共用キャッシュ５．１のブロック１０．１と共
用キャッシュ５．３のブロック１０．３とにコピーさ
れ、次に階層の上位レベルにある専用キャッシュ３．１
１、３．３１、３．３２のブロック１０．１１、１０．
３１、１０．３２にコピーされる。専用キャッシュ３．
２２のブロック１０．２２内のコピーについて考える
と、専用キャッシュ３．２２は同一ノード内にあるロー
カルメモリ６．２を直接アクセスできるため、このコピ
ーは直接実行される。従って、命令処理装置２．１１、
２．２２、２．３１および２．３２は同じ情報を独立し
て処理する。ある情報をＡからＢに修正する時に例えば
ブロック１０．３２など階層の上位レベルでこの情報を
修正した場合、下向きの太い矢印で示すように、階層の
下位レベルすなわちローカルメモリ６．２でもこの情報
が分かるようにしておく。他のメモリ３のブロック全て
についても同様に体系的な更新を行うことができる。し
かしながら、１つの命令処理装置２が情報を修正する毎
に階層の上位レベルにある他のメモリ全てにおいて更新
を行ってしまうと、信号線上の更新メッセージのビット
レートが極めて大きくなり、命令処理装置を待たせてし
まうというリスクを生じる。

【００３１】一方、全メモリ３において無効化を行う
と、命令処理装置２が後で問合せを行う時にミスヒット
が生じ、結局は同じように命令処理装置２の動作速度が
落ちてしまう。

【００３２】本発明によれば、階層の上位レベルにある
他のメモリの対応するアドレスにある情報の少なくとも
一部を無効にし、階層の中間レベルおよび下位レベルの
対応するアドレスにある情報の更新や無効化を更新の有
用性に基づいて管理する。

【００３３】特に、図１に示す好ましい実施例によれ
ば、修正されたブロックの属するノードの階層の上位レ
ベルにあるメモリ３の対応するアドレスにあるブロック
を更新する一方で、他のノードの階層の上位レベルにあ
るメモリの対応するアドレスにあるブロックを無効にす
る。図示の実施例において、修正は処理装置２．３２に
よって行われ、したがって最初に専用キャッシュ３．３
２内で実行されると仮定する。本発明によれば、専用キ
ャッシュ３．３１のブロック１０．３１内の情報を更新
すると共に、専用キャッシュ３．１１のブロック１０．
１１に格納された情報と、専用キャッシュ３．２２のブ
ロック１０．２２に格納された情報を無効にする。

【００３４】仮に処理装置２．１１によって利用される
ことを前提に情報Ａを予めコピーしておいたとしても、
この情報が処理装置によって利用されずに問合せの対象
ともならないのであれば、共用キャッシュ５．１のブロ
ック１０．１内の情報の更新は必ずしも有用という訳で
はないことに留意されたい。

【００３５】本発明の好ましい実施例によれば、更新の
有用性に基づいて処理モードを適合させる。このように
するため、本発明の第１の実施例では、メモリ５のブロ
ックに格納された情報のコピーを更新モードにあるプロ
トコルで通常通り処理し、階層の中間レベルにある各ブ
ロックに有用ビット１２を関連させる。すなわち、ブロ
ック１０．１にはビット１２．１、ブロック１０．３に
はビット１２．３を関連させる。有用ビットは、第１の
コピーあるいはこのアドレスに関連した情報の更新時に
は例えば図１において「０」で示すように第１の状態に
なり、このアドレスに関連した情報の問合せ時には例え
ば状態１などの第２の状態になる。実際には、階層の下
位レベルにあるメモリ６．２の管理処理装置によって更
新を行う場合には、更新が行われるブロックから肯定応
答信号が出力される。従って、更新の直前に有用ビット
の状態についての指示を簡単に肯定応答メッセージに含
めることができる。この有用ビットの状態は、このブロ
ックについての前の更新がどの程度有用であるかを示
す。具体的には、有用ビットの前の更新後にアドレスが
照会された場合にはそのブロックは「１」になり、アド
レスが全く照会されない場合にはそのブロックは「０」
のままである。

【００３６】この指示の利用は、特に階層の下位レベル
にあるブロックの各々に接続された階層の中間レベルに
あるブロックの数や、異なる命令処理装置間での予測で
きる情報共用の程度などに応じて様々な方法で行うこと
ができる。プロトコルの機能モードを、ある１つのブロ
ックでの更新の有用性を考慮してというよりは、同一の
アドレスを有する中間レベルにあるブロックの群に応じ
た更新の有用性を考慮して修正されることが好ましい。

【００３７】特に、本発明のこの実施例の第１の形態に
よれば、例えば階層の下位レベルにあるメモリ６．２の
管理処理装置に関連したディレクトリ（図示せず）に更
新閾値を記憶しておき、更新を行う毎に第２の状態にあ
る有用ビットの比率を更新閾値と比較する。第２の状態
にある有用ビットの比率が更新閾値よりも小さい場合、
階層の中間レベルにある同一アドレスのブロック全てに
ついて処理プロトコルを無効化モードに維持する。ま
た、第２の状態にある有用ビットの比率が少なくとも更
新閾値と等しい場合には、階層の上位レベルの処理プロ
トコルを更新モードに維持する。

【００３８】図２の表に示した本実施例の第２の形態で
は、第２の状態にある有用ビットの比率は考慮せず、各
状態にあるビット数および２つの閾値を考慮に入れる。
第１の状態にある有用ビット数、すなわち前回の更新時
以来１度も照会されていないためその更新が無駄になる
ブロックに関連した有用ビットの数を第１の閾値Ｓ１と
比較する。第２の状態にある有用ビット数、すなわち同
一アドレスを有し、メモリの接続されている命令処理装
置によって照会され、前回の更新が有用になったブロッ
クに関連した有用ビットの数を、第１の閾値Ｓ１ではな
く第２の閾値Ｓ２と比較する。

【００３９】このように比較した結果に基づいてプロト
コルの処理モードは「更新」モードに維持されるかある
いは「無効化」モードにされる。図２に示す好ましい実
施例によれば、第２の状態にある有用ビットの数が第１
の状態にある有用ビットの数及び第２の閾値Ｓ２よりも
小さくなると、無効化モードに移る。第２の状態にある
有用ビットの数が第２の閾値Ｓ２よりも大きく、かつ第
１の状態にある有用ビットの数が第１の閾値Ｓ１よりも
小さいような状況では、プロトコルは更新モードにな
る。第２の状態にある有用ビット数が第２の閾値よりも
大きく、かつ第１の状態にある有用ビット数も第１の閾
値Ｓ１よりも大きい場合にも、プロトコルは更新モード
になるが、明らかに無駄なものであって次の更新前に命
令処理装置からの問合せがなければ、更新されることも
ない大量のコピーを格納しているメモリをクリアするた
めに単発的に無効化を実行する。この目的のため、更新
モードにあるプロトコルは、修正対象となる下位レベル
のブロックと同一アドレスを有する、階層の中間レベル
に存在するブロックに対するコピーの更新だけを行うこ
とに留意されたい。

【００４０】以下に述べる本発明の特定の実施例の２つ
の形態は、多数の処理装置が限られた回数だけしか情報
を利用しなかった場合に更新メッセージのビットレート
を効果的に減少させる一方で、限られた数の処理装置だ
けが情報を頻繁に利用し多数の処理装置はその情報をあ
まり利用しなかった場合に中間レベルにおける問い合わ
せのミスヒット率を増加させる統計的機能を有する。無
効化モードになった後は、更新が有用であるならば更新
モードに戻すことができると好ましい。

【００４１】これについて、本発明の実施例における第
２の形態によれば、プロトコルが更新モードである時に
は更新の有用性、プロトコルが無効化モードである時に
はミスヒットの性質に応じて後述するように変化するコ
ードを下位レベルの各アドレスに関連させる。

【００４２】本発明のこの実施例の第２の形態では、階
層の下位レベルにあるアドレスのコードに応じてプロト
コルのモードを変化させる。

【００４３】図１を参照すると、下位レベルにあるブロ
ック１０はそれぞれコードを形成する２ビットからなる
領域１３を有する。このコードの変化およびプロトコル
に対応する機能のモードの選択の例を図３に示す。図３
には、下位レベルのアドレスに関連した２ビットのコー
ドについて考えられる異なる値を示してある。これらの
値は点線で２つのグループに分けられている。点線の上
側にある値は無効化モードにあるプロトコルに対応し、
点線の下側にある値は更新モードにあるプロトコルに対
応している。

【００４４】コードの値の変化と、コードの値が変化す
ることによるプロトコルのモードへの影響について説明
するために、下位レベルにあるメモリ６のブロック１０
に格納された情報はコピーされていないと仮定し、その
２ビットのコードはゼロであって中間レベルにあるメモ
リとの関係を示すプロトコルは無効化モードにあると仮
定する。

【００４５】このような状況から出発して、アドレス
（Ａｄ）における情報を必要としている例えば命令処理
装置２．１１などの命令処理装置は、専用キャッシュ
３．１１に対してその情報を要求する。専用キャッシュ
３．１１はその情報を格納していないため、共用キャッ
シュ５．１に対して同じように情報を要求する。（ここ
で、要求された情報はローカルメモリ６．１には格納さ
れておらず、例えば図示の例ではローカルメモリ６．２
など他のノードにあるローカルメモリに格納されている
と仮定する。）共用キャッシュ５．１はその情報を格納
していないので、メモリ５．１の管理処理装置は、シス
テムバス７．１、直列信号線制御装置８．１、この直列
信号線制御装置と直列信号線制御装置８．２とを結ぶ直
列信号線９、システムバス７．２を介してメモリ６．２
に対してその情報を要求しなければならない。この問合
せの間、共用キャッシュ５．１の管理処理装置は、共用
キャッシュ５．１にその情報はないだけでなくどのブロ
ックにもアドレス（Ａｄ）が含まれていないことを示す
信号をローカルメモリ６．２の管理処理装置に送る。以
下、このような状況を「重大なミスヒット」と呼び、図
３において矢印１４で示す。この矢印１４は、ブロック
１０の領域１３のコードの値が「００」のままであり、
アドレス（Ａｄ）に関するメモリ６．２とメモリ５との
関係を示すプロトコルが無効化モードのままである状態
に対応する。この情報が極めてまれにしか利用されない
のであれば、共用キャッシュ５．１の管理処理装置は後
にそのアドレスを消去する。処理装置２．１１によって
この情報に対して後述する新たな問合せがなされた場合
には状況は再び重大なミスヒット状態になる。新たな処
理装置が情報のコピーを問合せる毎に同じようなことが
起こる。

【００４６】ここで、情報は中間レベルの２つのブロッ
ク１０．１および１０．３に順次コピーされており、例
えば図１に示すような２．３２などの処理装置が情報を
ＡからＢに修正したと仮定する。下降関係のプロトコル
によれば、ブロック１０のベースアドレスの情報も同じ
ように修正されるが、ブロック１０のコードは「００」
のままである。メモリ６．２からメモリ５方向への上昇
関係のプロトコルは無効化モードのままであり、ブロッ
ク１０．１の情報は単に無効化され、一方アドレス（Ａ
ｄ）はブロック１０．１に維持される。

【００４７】この状況において、処理装置２．１１によ
って情報が要求されると、メモリ５．１の管理処理装置
はアドレスの存在を確認するが無効化されている関連の
情報を与えることはできない。従って、その情報を更新
するために再びメモリ６．２に問合せる必要がある。し
かしながら、この問合せはアドレス（Ａｄ）が常にブロ
ック１０．１にあることを明言することによって実行さ
れる。以下、このような状況を「些細なミスヒット」と
呼ぶ。この時、図３において矢印１５で示すようにコー
ドの値が「０１」になるように、コードの状態を示すビ
ットの１つを修正する。図３からも明らかなように、こ
のコードについてメモリ６．２からメモリ５方向へのア
ドレス（Ａｄ）についての関係のプロトコルは無効化モ
ードのままであり、その間にアドレス１０．１が削除さ
れていれば処理装置２．１１以外の処理装置による情報
の修正後のブロック１０．１に対する問合せは再び些細
なミスヒット状態になる。このような重大なミスヒット
に対応する状況を図３において矢印１６で示す。ここで
はブロック１０内のコードを値「００」に戻す。

【００４８】一方、些細なミスヒットを図３の矢印１７
で示す。コードの値が「０１」の時に些細なミスヒット
が生じるとこのコードの値は「１０」になり、アドレス
Ａｄに関連した上昇関係のプロトコルは変化して更新モ
ードになる。

【００４９】従って、いずれか１つの命令処理装置２に
よって後で情報が修正されると、階層の中間レベルにお
いて各メモリ５が更新され、各共用キャッシュ５に対す
る問合せは成功しミスヒットは生じない。この状況から
出発して、提起される質問は、更新を実行するのに役立
つものであるか否か知ることである。最初に情報を要求
している処理装置側で生じる可能性のあるミスヒットは
もはや考慮されない。この場合、本発明の第１の実施例
において説明したような更新の有用性についての基準、
すなわちメモリ５のブロックの各更新が適用され、肯定
応答信号によって有用ビット１２の状態を送信する。各
アドレスに対し、メモリ６の管理処理装置は、上述の実
施例の１つに基づいて有用ビット全体の状態を解析し、
それから更新の全体的有用性を導き出す。

【００５０】有用ビットの状態に対応する更新が有用で
ある場合には、コードの値は図３において矢印１８で示
すように「１０」に維持され、上昇関係のプロトコルも
当然変化しない。全体として更新が無用である場合に
は、図３において矢印１８で示すようにコードの値は
「１１」に修正される。

【００５１】次の更新時に有用ビットが変化し、有用な
更新を示している場合には、このコードは図３において
矢印２０で示すように値「１０」に戻る。一方、コード
の値が「１１」である時に、次の更新の間に有用ビット
が好ましい形に変更されないことが確認されると、直前
になされた更新は無駄になり、コードは図３において矢
印２１で示すように「００」の値をとり、上昇関係のプ
ロトコルは無効化モードに戻る。次に再び上述したよう
な状況になる。

【００５２】本発明による実施例の第２の形態では、モ
ードの上昇関係のプロトコルを他のプロトコルにするこ
とができる。ただし、このようにしてもモードの変更は
頻繁になりすぎることはないので、メモリ間の信号線上
でメッセージの流れを最適化することができる。

【００５３】初期化は必ずしもコード「００」を使用し
て行わなくてもよいことに留意されたい。他のコードを
使用し、上述したような機構に基づいてそのコードから
変更を実行することもできる。

【００５４】また、当該のアドレスに関連した情報につ
いてのコピーの状況に応じて異なるアドレスを異なるモ
ードにおくこともできることに留意されたい。

【００５５】もちろん、本発明は上述した実施例に限定
されるものではなく、特許請求の範囲に規定されている
ような本発明の趣旨を逸脱することなく様々な変更を加
えることが可能である。

【００５６】具体的には、１つのノードの中で共用キャ
ッシュを同一ノードのローカルメモリに対して中間レベ
ルのメモリとして機能させることができる。また、専用
キャッシュを階層の中間レベルに相当するものとするこ
ともできる。この場合、ノードのローカルメモリのアド
レスについて、そのノードの専用キャッシュに対応する
ブロックと有用ビットとを関連させ、有用ビットの状態
に応じてそのノードの専用キャッシュにおいて更新や無
効化を実行させることができる。

【００５７】一方、ローカルメモリのうちの１つに最初
から格納されていた情報を利用して処理装置のみによっ
て修正する場合には、ローカルメモリの管理処理装置
は、処理装置に対応する専用キャッシュに対してその情
報を格納できるのはそのキャッシュだけであり、他の処
理装置によって再要求されるまで情報を無効にするだけ
でローカルメモリまで修正を再び順次下げる必要はない
ことを通知することができる。

【００５８】以上、各ノード内でローカルメモリが直接
ローカルバスに接続されている情報処理アセンブリに本
発明を適用した場合について説明したが、本発明は階層
の下位レベルにあるメモリを排他的に階層の中間レベル
にあるメモリに接続した場合にも同じように適用可能で
ある。

【００５９】また、更新モードと無効化モードの切り換
えは、例えばメモリ６の各アドレスに関連したコードに
ついて考えられる値の数を増やすなどの他の方法で行う
こともできる。ただし、その方法が複雑になりすぎず、
もはや要求を満足せず順番を待たせることのないように
メモリの管理処理装置の機能を複雑にしないように注意
する必要がある。

【００６０】

【発明の効果】以上説明したように、本発明は、少なく
とも階層の上位レベルおよび下位レベルのメモリに接続
された中間レベルのメモリを有する記憶階層のレベル間
で交換のコヒーレンシーを管理するための最適な方法が
得られるという効果を奏する。

【図面の簡単な説明】

【図１】本発明による方法を３つのレベルを有する記憶
階層について示す概略図である。

【図２】本発明の第１の実施例における第２の形態を説
明するための表である。

【図３】状況を細かく分析する場合の更新および無効化
の方法を示す概略図である。

【符号の説明】

１ノード２命令処理装置３専用キャッシュ４ローカルバス５共用キャッシュ６ローカルメモリ７システムバス８直列信号線制御装置

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成６年１１月１６日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】図２

【補正方法】変更

【補正内容】

【図２】本発明の第１の実施例における第２の形態を説
明するための図表である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者アンヌ・カズインスキフランス国、マンゲラン・78660・アブリ、シユマン・デ・シヤルボニエ、13

Claims

【特許請求の範囲】

【請求項１】上位レベルと、上位レベルおよび下位レ
ベルに接続された少なくとも１つの中間レベルと、下位
レベルとを含む記憶階層のレベル間での交換のコヒーレ
ンシー管理方法であって、前記階層の各レベルが複数の
メモリ（３、５、６）からなり、該メモリはアドレス
（Ａｄ）によって識別される情報（１１）を格納した複
数のブロック（１０）からなり、前記階層の上位レベル
および中間レベルにあるメモリのブロックが、前記階層
の下位レベルの対応するアドレスにあるブロックに格納
された情報のコピーを格納し、階層の上位レベルにある
メモリのブロック（１０．３２）に格納された情報を修
正する際、前記階層の上位レベルにある他のメモリの対
応するアドレスにある情報の少なくとも一部を無効に
し、更新の有用性に基づいて前記階層の中間レベルおよ
び下位レベルの対応するアドレスにある情報の更新ある
いは無効化を管理することを特徴とする、記憶階層レベ
ル間での交換のコヒーレンシー管理方法。
【請求項２】信号線によって前記階層の異なるレベル
にあるメモリを複数のノードに再グループ化して情報処
理アセンブリとする記憶階層レベル間での交換のコヒー
レンシー管理方法において、前記階層の上位レベルにあ
るメモリのブロック（１０．３２）に格納された情報を
修正する際、修正されるブロックが属するノード（１．
３）の前記階層の上位レベルにあるメモリの対応するア
ドレスにあるブロック（１０．３１）を更新すると共
に、他のノード（１．１、１．２）内の前記階層の上位
レベルにあるメモリの対応するアドレスにあるブロック
（１０．１１、１０．２２）を無効にすることを特徴と
する、請求項１に記載の記憶階層レベル間での交換のコ
ヒーレンシー管理方法。
【請求項３】更新モードの間はプロトコルに基づいて
前記階層の中間レベルの対応するアドレスにあるブロッ
クに格納された情報のコピーを通常通り処理する記憶階
層レベル間での交換コヒーレンシー管理方法において、
該ブロックに格納された情報の第１のコピーあるいは情
報の更新を行う際に第１の状態になると共に、該ブロッ
クに格納された情報を利用する時には第２の状態になる
有用ビット（１２）を前記階層の中間レベルにある各ブ
ロックに関連させ、前記階層の下位レベルのあるアドレ
スにある情報を修正する際に、前記階層の中間レベルの
対応するアドレスにあるブロックの更新を行うと共に、
該アドレスにおける前回の更新の有用性に応じて処理プ
ロトコルを更新モードに維持するかまたは無効化モード
にし、該前回の更新の有用性が、該更新の直前に同一ア
ドレスのブロックでの有用ビットの状態に応じて決定さ
れることを特徴とする、請求項１または２に記載の記憶
階層レベル間での交換のコヒーレンシー管理方法。
【請求項４】下位レベルに更新閾値を記憶し、第２の
状態にある有用ビットの比率が少なくとも更新閾値と等
しい場合にはプロトコルを更新モードに維持し、第２の
状態にある有用ビットの比率が更新閾値よりも小さい場
合には無効化モードにすることを特徴とする、請求項３
に記載の記憶階層レベル間での交換のコヒーレンシー管
理方法。
【請求項５】前記階層の下位レベルに第１の閾値およ
び第２の閾値を記憶し、第１および第２の閾値と比較す
ることにより第１および第２の状態にある有用ビットの
実際の数に応じて処理プロトコルを更新モードに維持す
るかあるいは無効化モードにすることを特徴とする、請
求項３に記載の記憶階層レベル間での交換のコヒーレン
シー管理方法。
【請求項６】第２の状態にある有用ビットの数が第２
の閾値よりも小さい場合にプロトコルを無効化モードに
することを特徴とする、請求項５に記載の記憶階層レベ
ル間での交換のコヒーレンシー管理方法。
【請求項７】第１の状態および第２の状態にある有用
ビットの数がそれぞれ第１および第２の閾値よりも大き
い場合に、プロトコルを更新モードに維持したまま、前
記階層の上位レベルにあるブロックに格納された情報を
単発的に無効化することを特徴とする、請求項６に記載
の記憶階層レベル間での交換のコヒーレンシー管理方
法。
【請求項８】更新モードの間はプロトコルに基づいて
前記階層の中間レベルの対応するアドレスにあるブロッ
クに格納された情報のコピーを通常通り処理し、該ブロ
ックに格納された情報の第１のコピーあるいは情報の更
新を行う際に第１の状態になると共に、該ブロックに格
納された情報を利用する時には第２の状態になる有用ビ
ット（１２）を前記階層の中間レベルにある各ブロック
に関連させる記憶階層レベル間での交換のコヒーレンシ
ー管理方法において、前記階層の中間レベルにあるブロ
ックに格納された情報のコピーを更新モードにあるプロ
トコルで処理する場合に更新の有用性に応じて変化する
と共に、前記階層の中間レベルにあるブロックに格納さ
れた情報のコピーを無効化モードにあるプロトコルで処
理する場合にはミスヒットの性質に応じて変化するコー
ド（１３）を前記階層の下位レベルにある各アドレスに
関連させ、更新の有用性が有用ビットの状態に応じて決
定され、ミスヒットの性質が前記階層の中間レベルにあ
るメモリ内の情報およびアドレスの有無あるいは該メモ
リのブロック内の無効な情報によって決定され、前記階
層の下位レベルにある該アドレスのコードに応じてプロ
トコルのモードを変えることを特徴とする、請求項１ま
たは２に記載の記憶階層レベル間での交換のコヒーレン
シー管理方法。
【請求項９】前記階層の下位レベルに更新閾値を記憶
し、第２の状態にある有用ビットの比率と閾値を比較す
ることによって更新の有用性を判断することを特徴とす
る、請求項８に記載の記憶階層レベル間での交換のコヒ
ーレンシー管理方法。
【請求項１０】前記階層の下位レベルに第１の閾値お
よび第２の閾値を記憶し、該第１および第２の閾値と比
較することにより第１および第２の状態にある有用ビッ
トの実際の数に応じてコードを変化させることを特徴と
する、請求項８に記載の記憶階層レベル間での交換のコ
ヒーレンシー管理方法。