JP3550092B2 - キャッシュ装置及び制御方法 - Google Patents
キャッシュ装置及び制御方法 Download PDFInfo
- Publication number
- JP3550092B2 JP3550092B2 JP2000587273A JP2000587273A JP3550092B2 JP 3550092 B2 JP3550092 B2 JP 3550092B2 JP 2000587273 A JP2000587273 A JP 2000587273A JP 2000587273 A JP2000587273 A JP 2000587273A JP 3550092 B2 JP3550092 B2 JP 3550092B2
- Authority
- JP
- Japan
- Prior art keywords
- state
- cache
- data
- request
- processor
- 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 - Fee Related
Links
- 238000000034 method Methods 0.000 title claims description 69
- 230000007704 transition Effects 0.000 claims description 159
- 230000015654 memory Effects 0.000 claims description 98
- 230000008859 change Effects 0.000 claims description 79
- 238000012545 processing Methods 0.000 claims description 51
- 238000012790 confirmation Methods 0.000 claims description 36
- 230000008569 process Effects 0.000 claims description 24
- 238000001693 membrane extraction with a sorbent interface Methods 0.000 claims description 20
- 230000000717 retained effect Effects 0.000 claims description 7
- 239000000835 fiber Substances 0.000 claims description 2
- 238000012795 verification Methods 0.000 claims 1
- 230000003442 weekly effect Effects 0.000 claims 1
- 238000007726 management method Methods 0.000 description 36
- 238000010586 diagram Methods 0.000 description 19
- 230000004044 response Effects 0.000 description 13
- 238000012546 transfer Methods 0.000 description 5
- 230000006870 function Effects 0.000 description 3
- 238000004904 shortening Methods 0.000 description 3
- 101100206389 Caenorhabditis elegans tag-124 gene Proteins 0.000 description 2
- 230000008901 benefit Effects 0.000 description 2
- 238000006243 chemical reaction Methods 0.000 description 1
- 230000014759 maintenance of location Effects 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
- G06F9/3824—Operand accessing
- G06F9/3834—Maintaining memory consistency
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR 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/0831—Cache consistency protocols using a bus scheme, e.g. with bus monitoring or watching means
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
- G06F9/3824—Operand accessing
- G06F9/383—Operand prefetching
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
- G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
- G06F9/3842—Speculative instruction execution
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
- Multi Processors (AREA)
Description
【技術分野】
本発明は、マルチプロセッサシステムでキャッシュメモリを管理するキャッシュ装置及び制御方法に関し、特に、有効性のはっきりしないデータのキャッシュメモリでの保持を可能にしてプロセッサに投機的に処理させるキャッシュ装置及び制御方法に関する。
【背景技術】
一般的に、計算機システムの主記憶へのアクセス時間は、プロセッサの動作速度に比べ非常に遅い。そのため、主記憶へのアクセスが発生すると、プロセッサは主記憶から送られるデータを待つことになる。キャッシュ装置は、主記憶に比べて小容量だが高速に動作するメモリであり、プロセッサと主記憶の間に配置され、見かけ上の主記憶アクセス時間を短縮し、プロセッサのデータ待ち時間を短くする。
図１はキャッシュ装置に設けたキャッシュメモリのテーブル構造であり、記憶単位となるキャッシュライン１２２には、タグ１２４とデータ１３０で構成され、タグ１２４には状態タグ１２６とアドレスタグ１２８が付いている。
プロセッサから読出要求を受けると、キャッシュメモリは要求アドレスとアドレス値の一致するアドレスタグ１２８を持ったキャッシュラインを探す。アドレス値の一致するキャッシュラインが存在しない場合は、キャッシュミスとなる。アドレス値の一致するキャッシュラインが存在したとしても、そのキャッシュラインに保持されているデータの有効性が状態タグ１２６から無効であれば、キャッシュミスとなる。キャッシュミスの場合には、主記憶もしくは他キャッシュメモリへのアクセスが必要となる。
アドレスタグ１２８のアドレス値の一致するキャッシュラインが存在し、かつ、そのキャッシュラインに保持されているデータの有効性が状態タグ１２６から有効であれば、キャッシュヒットとなる。キャッシュヒットの場合には、主記憶もしくは他のキャッシュへのアクセスが不要なので、プロセッサのデータ待ち時間は短くて済む。
このように、キャッシュメモリ装置では、要求アドレスとアドレス値の一致するキャッシュラインが存在する場合には、そのキャッシュラインに保持されているデータの有効性が有効であるか無効であるかにより、主記憶もしくは他キャッシュメモリへのアクセスが必要かどうか、プロセッサのデータ待ち時間が短くて済むかどうか、が決まる。
一方、マルチプロセッサシステムでは、プロセッサ毎にキャッシュ装置を持っていることが多い。プロセッサ毎に設けたキャッシュメモリ上のデータは、キャッシュメモリ間に亘ってそのデータの正しさ、即ちデータの一貫性を保つ必要がある。データの一貫性を保つため、キャッシュコヒーレンスプロトコルと呼ばれるキャッシュメモリ間のデータの整合性を保つ規則に従って、キャッシュメモリは管理される。これによりキャッシュメモリ上のデータへのアクセスが可能となっている。
マルチプロセッサシステムにおいて、キャッシュメモリ間に亘ってデータの一貫性を保つ様子を、無効化型キャッシュコヒーレンスプロトコルとして知られたＭＥＳＩプロトコルを使用したキャッシュ装置を例に説明する。
図２（Ａ）は、ＭＥＳＩプロトコルのリード要求に対する状態遷移であり、図２（Ｂ）は、ＭＥＳＩプロトコルのライト要求に対する状態遷移である。この状態繊維の記号は次の内容を表わす。
Ｍ：変更（Modified) であり、複数のキャッシュの１つにのみ有効データが保持されており、かつ、データは変更されており、主記憶のそれと値が同じであることが保証されない。
Ｅ：排他(Exclusive) であり、複数のキャッシュの１つにのみ有効データが保持されている。
Ｓ：共有(Shared)であり、複数のキャッシュ上に同じデータが保持されている。
Ｉ：無効（Invalid)であり、キャッシュ上のデータは無効である。
self : 自己のプロセッサからの要求を処理した場合である。
other : 他のキャッシュ装置からの要求を処理した場合である。
self-if copy:
リード要求に対し無効状態にあり、他のキャッシュが、そのデータを保持している場合。
self-if no copy:
リード要求に対し無効状態にあり、どのキャッシュも、そのデータを保持していない場合。
ここで、キャッシュ上に、データが存在しないという状態は、キャッシュ上にデータが無効Ｉ状態で保持されていることと意味的に等価なので、便宜上、無効Ｉ状態とは、
▲１▼キャッシュ上にそのデータが無効Ｉ状態で保持されている場合と、
▲２▼キャッシュ上にそのデータが存在しない場合
の両方を指すものとする。
同様に、キャッシュ上にデータが存在しないという表現は、
▲１▼キャッシュ上に、本当に、そのデータが存在しない場合と、
▲２▼キャッシュ上に、そのデータが無効Ｉ状態で保持されている場合
の両方を指すものとする。
図３（Ａ）は、マルチプロセッサシステムのキャッシュ装置であり、プロセッサ１０２−１，１０２−２のそれぞれにキャッシュ装置１００−１，１００−２が設けられ、バス１０４により主記憶１０６と共に共通接続されている。
いま図３（Ａ）のように、キャッシュ装置１００−１，１００−２のキャッシュメモリ上に、あるキャッシュラインにデータが共有Ｓ（Shared）状態で保持されているとする。ここで、図３（Ｂ）のように、プロセッサ１０２−１からキャッシュ装置１００−１のデータへの書込要求が発生した場合、キャッシュ装置１００−１のデータを変更し、共有Ｓ状態を変更Ｍ状態とする。しかし、キャッシュ装置１００−１のデータを変更するだけでは、キャッシュ装置１００−１，１００−２間のデータの一貫性が保てない。そのため、キャッシュ装置１００−２の共有Ｓ状態を無効Ｉ状態に変更する無効化操作を行った後、キャッシュメモリ１００−１のデータを変更する操作が必要となる。
その後、図３（Ｃ）のように、プロセッサ１０２−２が変更したデータに対し読出要求を行うと、図３（Ｂ）のプロセッサ１０２−１の書込要求によりキャッシュ装置１００−２のデータは無効Ｉ状態に無効化されているので、その後に発生したプロセッサ１０２−２の読出要求はキャッシュミスとなる。
一般に、キャッシュラインのブロックサイズは、プロセッサの扱うデータサイズよりサイズが大きい。仮に、キャッシュブロックサイズを２ワード、プロセッサの扱うデータサイズを半分の１ワードとする。ここで図４（Ａ）のように、キャッシュ装置１００−１，１００−２が、キャッシュライン１２２−１，１２２−２にある同じデータ、例えば、先頭１ワード部分のデータが“１２”、後方１ワード部分のデータが“３４”である２ワード帳のデータを保持していたとする。。この状態で図４（Ｂ）のように、プロセッサ１０２−１の書込要求がキャッシュライン１２２−１の先頭１ワード部分のデータへの書込要求が発生し、値が“１２”から“５６”に書き替えられたとする。このときキャッシュ装置１００−１，１００−２のキャッシュメモリには、キャッシュライン１２２−１，１２２−２単位で状態が管理されるので、キャッシュ装置１００−２のキャッシュライン１２２−２のデータは、２ワード分の全てが無効Ｉへの状態遷移で無効化される。
次に図４（Ｃ）のように、プロセッサ１０２−１のキャッシュ装置１００−２におけるキャッシュライン１２２−２の読出要求が、後ろ１ワード部分のデータへの読出要求であったとする。この場合、キャッシュ装置１００−１，１００−２におけるキャッシュライン１２２−１，１２２−２の後ろ１ワード部分に保持されているデータの値は“３４”と同じであるにも関わらず、キャッシュライン１２２−２は状態は無効Ｉのためキャッシュミスとなり、主記憶もしくは他キャッシュへのアクセスが発生し、プロセッサ１０２−２はデータ待ちになる。いわゆるいわつりの共有（false sharing ）によるキャッシュミスである。このようなキャッシュミスを発生させてしまう無効化操作を「好ましくない無効化操作」と呼ぶことにする。
一方、図５（Ａ）のように、あるデータがプロセッサ１０２−１のキャッシュ装置１００−１に排他Ｅの状態で保持されており、プロセッサ１０２−２のキャッシュ装置１００−２には存在しないか又は無効Ｉの状態でデータが保持されていたとする。ここで、図５（Ｂ）のように、プロセッサ１０２−２からキャッシュ装置１００−２のデータへの読出要求が発生すると、キャッシュ装置１００−１に排他Ｅの状態で保持しているデータを、キャッシュ装置１００−２に転送してプロセッサ１０２−２に提供し、この結果、キャッシュ装置１００−１，１００−２で共有されることになる。従って、データをキャッシュ装置１００−１もしくは主記憶から１００−２へデータを転送する操作と、キャッシュ装置１００−１の排他Ｅの状態から共有Ｓの状態に変える操作が必要となる。
このようにプロセッサ１０２−２の読出要求で、キャッシュ装置１００−１の状態が排他Ｅの状態から共有Ｓの状態に変わった後に、図５（Ｃ）のように、プロセッサ１０２−１が書込要求を行うと、キャッシュ装置１００−２の状態を共有Ｓの状態から無効Ｉの状態に変える無効化操作が必要となり、無効化後にキャッシュ装置１００−１の状態を共有Ｓから変更Ｍに変える。
近年のプロセッサは、条件分岐を動的又は静的に予測し、投機的に命令を実行する機能を備えており、その結果、投機的な読出要求を出す。投機的な読出命令の実行は予測に基づく命令実行であるので、その予測が正しければ良いが、誤りであればその投機的な実行結果は破棄される。つまり、投機的に実行された読出要求により読み出されたデータは、利用されない可能性がある。
図５（Ｂ）のプロセッサ１０２−２の読出要求が、もし誤った予測に基づく読出要求であったとしても、プロセッサ１０２−２の読出要求によりキャッシュ装置１００−１の状態を排他Ｅから共有Ｓに変える操作が実行されてしまう。そのため、図５（Ｃ）のように、その後に発生するプロセッサ１０２−１の書込要求では、本質的には必要のない共有Ｓの状態にあるキャッシュ装置１００−２のデータの状態を無効Ｉに変える無効化操作が必要となる。この読出データが結果的に利用されない読出要求の実行でキャッシュメモリの状態を共有Ｓに変えしてまう操作を、「好ましくない読出操作」と呼ぶこととする。
【発明の開示】
本発明に従えば、「好ましくない無効化操作」により発生するキャッシュミスを減らし、プロセッサのデータ待ち時間を短くするキャッシュ装置及び制御方法が提供される。
また本発明に従えば、「好ましくない読出操作」により必要となる無効化操作を減らしてプロセッサのデータ待ち時間を短くするキャッシュ装置及び制御方法が提供される。
本発明は、複数のプロセッサ毎に設けられ、相互にバス接続されると共に主記憶とバス接続されたキャッシュ装置に於いて、主記憶の一部のデータをキャッシュライン単位に保持すると共にキャッシュラインに保持したデータの状態を
▲１▼有効
▲２▼無効
▲３▼不明
の３種類の状態で区別するキャッシュメモリと、自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効、無効、又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラとを備えたことを特徴とする。
このように本発明では、データの有効性が有効であるか無効であるか確かではないデータを、有効性の不明なデータとしてキャッシュラインに保持することを許す。そして、「好ましくない無効化操作」を「弱い無効化操作（ウィーク・インバリデイト weak -invalidate）」により処理し、また「好ましくない読出操作」を「弱いリード操作（ウィークリート；weak-read）」により処理することで問題を解決する。
「弱い無効化操作」は、キャッシュラインを無効化する代わりに、キャッシュライン上のデータを有効性の不明なデータとして保持し続けることを許す。例えばキャッシュコヒーレンスのためのＭＥＳＩプロトコルの「好ましくない無効化操作」では、共有Ｓの状態にある２つのキャッシュメモリデータの一方に書込要求が発生すると、他方のキャッシュメモリのデータは無効化されてしまうが、本発明の「弱い無効化操作」では、無効化されずに有効性の不明なデータとして保持され続ける。このため「好ましくない無効化操作」ではプロセッサの読出要求でキャッシュミスとなるが、本発明の「弱い無効化操作」ではキャッシュメモリは有効性の不明なデータを保持しているため、読出要求に対し投機データとしてプロセッサに供給できる。このような本発明の「弱い無効化操作」は、ＭＥＳＩプロトコルに不明Ｕの状態を加えたＭＥＳＩＵプロトコルということができる。
本発明の「弱い読出操作」は、本発明の「弱い無効化操作」を実現するＭＥＳＩＵプロトコルに従ったキャッシュ管理制御において、プロセッサがキャッシュメモリに保持された有効性が不明なデータを投機データとして提供を許可するウィークリード要求が生じた時に実行される。この場合、読出要求を受けたキャッシュ装置は、他のキャッシュ装置に保持している有効データを読出転送して要求元に応答して自分にコピーする。このとき本発明の「弱い読出操作」では、他のキャッシュメモリから転送したデータを、有効なデータとしてではなく、有効性の不明なデータとして扱う。
即ち、ＭＥＳＩプロトコルの「好ましくない読出操作」では、無効Ｉの状態にあるキャッシュメモリのデータは排他Ｅの状態にある他のキャッシュメモリから転送した場合、各々共有Ｓの状態に変更される。しかし、本発明の「弱い読出操作」で処理した場合は、他のキャッシュメモリのデータは排他Ｅの状態のまま変更されず、読出対象のキャッシュメモリに転送されたデータは有効性の不明なデータ、即ち不明Ｕの状態のデータとして保持される。従って、その後、に排他Ｅの状態にある他のキャッシュデータに書込要求があっても、同じデータを不明Ｕの状態で保持しているキャッシュメモリの無効化操作は必要なくなる。
本発明の弱い読出操作は、プロセッサがキャッシュメモリに保持された有効性が不明なデータを投機データとして提供を許可するウィークリード要求が生じた時とする以外に、キャッシュ装置の機能として固定設定してもよい。
本発明の別の形態にあっては、複数のプロセッサ毎に設けられ、相互にバス接続すると共に主記憶とバス接続されたキャッシュ装置に於いて、主記憶の一部のデータをキャッシュライン単位に保持すると共にキャッシュラインに保持したデータの状態を
▲１▼有効
▲２▼不明
の２種類の状態で区別するキャッシュメモリと、自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラとを備えたことを特徴とする。
この場合にも、データの有効性が有効であるかが確かではないデータを、有効性の不明なデータとしてキャッシュラインに保持することを許す。そして、同様にして「好ましくない無効化操作」を「弱い無効化操作（weak-invalidate）」により処理し、また「好ましくない読出操作」を「弱いリード操作（weak-read）」により処理することで問題を解決する。これは本発明のＭＥＳＩＵプロトコルから無効Ｉの状態を除いたＭＥＳＵプロトコルということができる。
キャッシュコントローラは、有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した際に、投機データの要求元への提供許可か提供禁止かを判定し、提供許可を判定した場合は、有効性の不明なデータを投機データとして要求元に提供し、提供禁止を判定した場合は、他のキャッシュ装置又は主記憶から有効データを入手して要求元に提供させる。
キャッシュコントローラは、投機データを要求元に提供した後、要求元から投機データの有効性確認要求が発生した際に、投機データの本当の有効性を確認して確認の結果を要求元に通知する。
またキャッシュコントローラは、投機データを要求元に提供すると同時に、投機データの本当の有効性を確認して確認の結果を記憶し、要求元から前記投機データの有効性の確認要求が発生した際に、記憶しておいた有効性の確認結果を要求元に通知するようにしてもよい。
更に、キャッシュコントローラは、投機データを要求元に提供すると同時に、投機データの本当の有効性を自分自身で確認し、確認結果を要求元に通知するようにしてもよい。
キャッシュコントローラは、確認結果から投機データが有効であった場合は、要求元のプロセッサに確認結果を通知して投機データに基づく命令の実行結果を承認させ、一方、確認結果から投機データが無効であった場合は、要求元のプロセッサに確認結果を通知して投機データに基づく命令の実行結果を破棄させる。このように有効性の不明なデータを保持することができる本発明のキャッシュ装置により、プロセッサに投機的にデータを供給することが可能となり、投機データの提供でキャッシュミスを低減し、プロセッサの待ち時間を短縮してキャッシュ性能を向上させる。
キャッシャコントローラは、主記憶の予め定めた特定アドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を禁止し、主記憶の特定アドレス以外のアドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を許可する。
またキャッシャコントローラは、プロセッサの投機データを禁止する命令の実行で生成した読出要求を有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を禁止し、プロセッサの投機データを許容する命令の実行、例えば分岐予測の結果、生成された読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を許可する。このように投機的な読出要求か否かを、主記憶のアドレスまたはプロセッサ実行命令から識別し、プロセッサの投機的な命令実行と投機的でない通常の命令実行を区別したキャッシュ管理制御を行う。
キャッシュコントローラは、キャッシュラインの保持データの状態を、有効を示す変更Ｍ、排他Ｅ及び共有Ｓと無効Ｉの４状態で区別するキャッシュコヒーレンスのＭＥＳＩプロトコルに、データの有効性が不明であることを示す状態Ｕを加えた５状態で区別するキャッシュコヒーレンスのＭＥＳＩＵプロトコルとする。このＭＥＳＩＵプロトコルが、前述したように本発明の「弱い無効化操作」を実現する。
キャッシュコントローラは、キャッシュラインの保持データに対するリード要求を処理した場合、ＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置で読出要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求により主記憶からデータをコピーした場合は排他Ｅに状態遷移し、他のキャッシュ装置からコピーした場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する。
また、キャッシュコトローラは、キャッシュラインの保持データに対するライト要求を処理した場合には、ＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
キャッシュコントローラは、不明Ｕの状態で保持したデータの提供を許すプロセッサからのウィークリード要求（弱い読出要求）を処理した場合、ウィークリードでのキャッシュコヒーレンスのためのＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの弱い読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの弱い読出要求であれば排他Ｅに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置からの弱い読出要求であれば同じ排他Ｅに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置からの弱い読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの弱い読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は不明Ｕに状態遷移し、更に他のキャッシュ装置の弱い読出要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置の弱い読出要求であれば同じ不明Ｕに状態遷移する。
このウィークリード要求を実現するＭＥＳＩＵプロトコルは、プロセッサからウィークリード要求を受けた際に実行せずに、キャッシュコントローラで固定設定してもよい。
キャッシュコントローラは、キャッシュラインの保持データの状態を、有効を示す変更、排他及び共有の３状態で区別するＭＥＳプロトコルに、データの有効性が不明であることを示す状態Ｕを加えた４状態で区別するＭＥＳＵプロトコルを備える。
キャッシュコントローラは、キャッシュラインの保持データに対するリード要求を処理した場合、このＭＥＳＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置からの読出要求であれば同じ不明Ｕに状態遷移する。
またキャッシュコントローラは、キャッシュラインの保持データに対するライト要求を処理した場合、ＭＥＳＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
▲４▼不明Ｕで、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
またキャッシュコントローラは、キャッシュラインに不明Ｕの状態で保持した投機データの提供を許可するプロセッサからのウィークリード要求（弱い読出要求）命令を処理した場合、ＭＥＳＵプロトコルに基づき次の処理を行う。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する。
このウィークリード要求を実現するＭＥＳＵプロトコルについても、プロセッサからウィークリード要求を受けた際に実行する以外に、キャッシュコントローラでＭＥＳＵプロトコルを固定設定してもよい。
一方、本発明は、複数のプロセッサ毎に設けたキャッシュ装置を相互にバス接続すると共に主記憶とバス接続したキャッシュ制御方法を提供する。
このキャッシュ制御方法は、
▲１▼主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効、無効、及び不明の３種類の状態で区別し、
▲２▼自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効、無効、又は不明の状態に応じて処理し（ＭＥＳＵＩプロトコル）、
▲３▼要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するために定めた所定の状態に遷移させることを特徴とする。
また本発明のキャッシュ制御方法の別の形態にあっては、
▲１▼主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効及び不明の２種類で区別し、
▲２▼自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理し（ＭＥＳＵプロトコル）、
▲３▼要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを維持するために定めた所定の状態に遷移させる。
この本発明によるキャッシュ制御方法の詳細は、装置構成の場合と基本的に同じになる。
【図面の簡単な説明】
図１はキャッシュメモリのテーブル構造の説明図
図２はＭＥＳＩプロトコルの状態遷移図
図３はＭＥＳＩプロトコルにおける好ましくない無効化操作を招くキャッシュ動作の説明図
図４は図３の好ましくない無効化操作におけるキャッシュラインの説明図
図５はＭＥＳＩプロトコルにおける好ましくない読出操作を招くキャッシュ動作の説明図
図６は本発明のキャッシュ装置が使用されるマルチプロセッサシステムのブロック図
図７は本発明のキャッシュ装置の機能ブロック図
図８はキャッシュ保持データを不明として扱う本発明の弱い無効化操作及び弱い読出操作を実現するＭＵＳＩＵプロトコルの状態遷移図
図９は図８のＭＵＳＩＵプロトコルの状態遷移表の説明図
図１０は図３の好ましくない無効化操作の問題を解消する本発明の弱い無効化操作の説明図
図１１は図５の好ましくない読出操作の問題を解消する本発明の弱い読出操作の説明図
図１２は本発明の弱い読出操作の他の動作形態の説明図
図１３は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第１実施形態のフローチャート
図１４は図１３で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図１５は図１４の投機データの有効性確認のフローチャート
図１６は図１４の投機データの他の有効性確認のフローチャート
図１７は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第２実施形態のフローチャート
図１８は図１７で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図１９は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第３実施形態のフローチャート
図２０はキャッシュ保持データを不明として扱う本発明の弱い無効化操作及び弱い読出操作を実現するＭＥＳＵプロトコルの状態遷移図
図２１は図２０のＭＥＳＵプロトコルの状態遷移表の説明図
図２２は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第４実施形態のフローチャート
図２３は図２２で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図２４は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第５実施形態のフローチャート
図２５は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第６実施形態のフローチャート
【発明を実施するための最良の形態】
（装置構成と機能）
図６は本発明のキャッシュ装置および制御方法が適用されたマルチプロセッサシステムのブロック図である。
図６において、本発明のキャッシュ装置１０−１，１０−２，・・・１０−ｎは、それぞれプロセッサ１２−１，１２−２，・・・１２−ｎに対応して設けられる。キャッシュ装置１０−１〜１０−ｎは、システムバス１４により相互に接続され、更にシステムバス１４により主記憶１６と接続されている。キャッシュ装置１０−１〜１０−ｎを接続するシステムバス１４としては、例えばスヌープバスを使用する。スヌープバスはキャッシュ装置１０−１〜１０−ｎのいずれかでプロセッサ１２−１〜１２−ｎから処理要求があった際に、処理要求に該当するキャッシュラインに保持しているデータの状態をスヌープ制御線の状態信号により直ちに取得できるバスである。
図７は、本発明のキャッシュ装置１０の機能ブロック図である。キャッシュ装置１０は、キャッシュコントローラ１８とキャッシュメモリ２０で構成される。キャッシュメモリ２０は、複数のキャッシュライン２２単位にデータを保持しており、各キャッシュライン２２はタグ２４とデータ３０を含み、タグ２４は状態タグ２６のアドレスタグ２８を備える。キャッシュメモリ２０の状態タグ２６につき本発明にあっては、保持データの状態として有効及び無効に加えて、有効性の不明なデータを保持することができる。
キャッシュコントローラ１８には、キャッシュ制御管理部３２、状態管理部３４、プロセッサインタフェース３６、バスインタフェース３８が設けられる。また状態管理部３４には、リードプロトコル処理部４０、ウィークリードプロトコル処理部４２、投機データ確認部４４及びライトプロトコル処理部４６が設けられる。
キャッシュ制御管理部３２は、プロセッサ１２から読出要求を受けると、キャッシュメモリ２０のタグ２４を参照し、要求アドレスとアドレス値の一致するアドレスタグ２８をもったキャッシュライン２２を検索する。アドレス値の一致するキャッシュラインが存在しない場合にはキャッシュミスとなり、主記憶１６もしくは他のキャッシュ装置から有効データを獲得してプロセッサ１２に提供する。
キャッシュ制御管理部３２は、要求アドレスに一致するアドレスのキャッシュラインが存在した場合には、そのキャッシュラインの状態タグ２６による有効、無効、不明の状態に応じた処理を行う。即ち状態が有効であれば、キャッシュメモリ１０上に保持されているデータをプロセッサ１２に提供する。無効であれば他のキャッシュ装置または主記憶から有効データを入手してプロセッサ１２に応答する。更に不明であれば、プロセッサ１２が投機データの提供を許可していることを条件に、キャッシュメモリ２０上に有効性が不明な状態で保持しているデータを、投機データとしてプロセッサ１２に提供する。
キャッシュ制御管理部３２は、プロセッサ１２からの書込要求に対しては、キャッシュヒットであればキャッシュメモリ２０上の該当するキャッシュラインのデータを更新し、ミスヒットであればキャッシュメモリ２０上に新たなキャッシュラインを確保してデータを書き込む。
このようなキャッシュ制御管理部３２によるプロセッサ１２及びシステムバス１４を経由した他のキャッシュ装置からの処理要求に対し、状態管理部３４が処理要求を実行した後の該当するキャッシュライン上の状態タグ２６の状態遷移制御を行う。状態管理部３４によるキャッシュコヒーレンスのための状態遷移制御として、本発明にあっては、図２のＭＥＳＩプロトコルに更に、有効性の不明なデータの保持を示す不明Ｕの状態を加えたＭＥＳＩＵプロトコルを適用している。
図８は、図７の状態管理部３４で使用されるＭＥＳＩＵプロトコルの状態遷移の説明図である。即ち図８（Ａ）が、リードプロトコル処理部４０で処理する読出要求に対するＭＥＳＩＵリードプロトコルの状態遷移である。また図８（Ｂ）が、図７のライトプロトコル処理部４６によるＭＥＳＩＵライトプロトコルの状態遷移である。この図８（Ａ）及び（Ｂ）のＭＥＳＩＵのリードプロトコル及びライトプロトコルは、図３のＭＥＳＩプロトコルにおける「好ましくない無効化操作」を解消するための本発明による「弱い無効化操作」のキャッシュ管理制御を実現する。
更に図８（Ｃ）は、図７のウィークリードプロトコル処理部４２で処理されるＭＥＳＩＵウィークリードプロトコルの状態遷移である。このＭＥＳＩＵウィークリードプロトコルは、図５に示したＭＥＳＩプロトコルにおける「好ましくない読出操作」の問題を解消するための本発明の「弱い読出操作」のキャッシュ管理制御を実現する。
ここで図８（Ａ）（Ｂ）（Ｃ）の各プロトコルにおいて、状態Ｍは変更（Modified）、状態Ｅは排他（Exclusive ）、状態Ｓは共有（Shared）、状態Ｉは無効（Invalid ）を表わし、更に本発明にあっては新たに、有効性の不明なデータ保持の状態として不明（Unknown ）を追加している。
また図８（Ａ）のリードで、状態Ｍ，Ｅ，Ｓにおける実線の遷移は、自己のプロセッサからリード要求を処理した場合であり、破線は他のキャッシュ装置でリード要求が処理された場合である。また無効Ｉにあっては他の装置での読出要求は破線のように状態変化を起こさないが、自己のプロセッサからの読出要求にあっては、他キャッシュ装置が該当ラインを保持していない(self-if no copy) の場合には排他Ｅに状態遷移し、他キャッシュ装置が該当ラインを保持している(self-if copy)の場合には共有Ｓに状態遷移する。
図８（Ｂ）のＭＥＳＩＵライトプロトコルの状態遷移にあっては、状態Ｍ，Ｅ，Ｓ，Ｉ，Ｕのそれぞれについて、自己のプロセッサからの書込要求を処理した場合ついては実線のように遷移し、他のキャッシュ装置で書込要求が処理された場合については破線のように遷移する。図８（Ｃ）のＭＥＳＩＵウィークリードプロトコルの破線及び実線の遷移は、図８（Ａ）のＭＥＳＩＵリードプロトコルと同じ意味をもつ。
図９は、図８のＭＥＳＩＵプロトコルの状態遷移表である。この状態遷移表は、縦方向に現在のキャッシュラインに保持したデータの状態を表わし、横方向に次の状態として自己のプロセッサからの要求を「ＳＥＬＦ」、他のキャッシュ装置での要求を「ＯＴＨＥＲ」として、図８（Ａ）（Ｂ）（Ｃ）のリード、ライト及びウィークリードに分けて状態遷移を表わしている。
このうち、次の状態が「Ｅ，Ｓ」及び「Ｅ，Ｕ」に付した（１）（２）は、図８（Ａ）のリードプロトコルにおける現在の状態Ｉからの実線の「ＳＥＬＦ−ＩＦ ＮＯ ＣＯＰＹ」と「ＳＥＬＦ−ＩＦ−ＣＯＰＹ」に対応している。例えば現在の状態Ｉで次の状態が自己プロセッサからのリード要求の結果遷移する状態「Ｅ，Ｓ」の（１）については、図８（Ａ）の状態Ｉのように、他のどのキャッシュ装置が該当するキャッシュラインを保持していない場合は排他Ｅに遷移し、それ以外の他のキャッシュ装置が該当ラインを保持している場合には共有Ｓに遷移する。また（２）で示す次の状態「Ｅ，Ｕ」については、図８（Ｃ）の現在の状態Ｉから次の状態ＥまたはＵへの遷移を表わす。更に図９の（３）で示す次の状態「Ｅ，Ｓ」への遷移は、図８（Ａ）のリードプロトコルにおける現在の状態Ｕにおいて自己のプロセッサからリード要求を受けた場合であり、この場合にも、どのキャッシュ装置にも該当するキャッシュラインを保持していないときは排他Ｅの状態に遷移し、それ以外の他のキャッシュ装置が該当ラインを保持している場合は共有Ｓに状態遷移する。
（弱い無効化操作と弱い読出操作）
図１０は、図８（Ａ）（Ｂ）のＭＥＳＩＵプロトコルにより処理で、図３のＭＥＳＩプロトコルで「好ましくない無効化操作」が生じたと同じプロセッサからの処理要求があったときの本発明による「弱い無効化操作」の動作説明である。
図１０（Ａ）は、２つのキャッシュ装置１０−１，１０−２のあるキャッシュラインについて、同じデータが共有Ｓの状態で保持されていたとする。この状態で、図１０（Ｂ）のように、プロセッサ１２−１から共有Ｓの状態で保持しているデータに対しライト要求を受けて処理したとすると、図８（Ｂ）のライトプロトコルの状態遷移に従い、キャッシュ装置１０−１の状態は共有Ｓから変更Ｍに遷移する。同時に、同じデータをキャッシュラインに保持しているキャッシュ装置１０−２にあっては、図８（Ｂ）のライトプロトコルの状態遷移に従い、他のキャッシュ装置１０−１で書込みがあったことから不明Ｕの状態に遷移する。この図１０（Ａ）の２つのキャッシュメモリ１０−１，１０−２の共有Ｓ状態が、図１０（Ｂ）のように一方のキャッシュ装置１０−１に対するプロトコル１２−１の書込要求で変更Ｍに遷移したとき、他のキャッシュ装置１０−２の共有Ｓの状態を図３（Ｂ）のように無効Ｉの状態とせずに不明Ｕの状態とするのが、本発明の「弱い無効化操作（ウィークインバリデイト）」である。
続いて図１０（Ｃ）のように、プロセッサ１２−２からのリード要求をキャッシュ装置１０−２で処理すると、このときのデータは不明Ｕの状態で保持しており、無効ではないことからキャッシュヒットとなって、不明Ｕの状態で保持したデータを要求元のプロセッサ１２−２に投機的データとして提供する。この場合には図８（Ａ）のリードプロトコルの状態遷移のように、リード要求のあったキャッシュ装置１０−２の不明Ｕの状態は共有Ｓの状態に遷移し、同時に他のキャッシュ装置１０−１の変更Ｍの状態も共有Ｓの状態に遷移する。
この図１０（Ａ）におけるキャッシュ装置１０−１，１０−２が共有Ｓの状態にあるときのいずれか一方、例えばプロセッサ１２−１からの書込要求に対し、他のキャッシュ装置１０−２のキャッシュラインを無効化せずに不明Ｕの状態とする弱い無効化操作（ウィークインバリディド）を行うことで、次の図１０（Ｃ）のようにプロセッサ１２−２がリード要求をキャッシュ装置１０−２に行ったとき、ミスヒットとならずにキャッシュヒットとして不明Ｕの状態にあるデータをプロセッサ１２−２に投機的データとして提供でき、無効Ｉの状態では必要だったプロセッサのデータ待ちの時間を短くすることができる。
図１１は、図８（Ｃ）のウィークリードプロトコルに従った本発明の「弱い読出操作」の動作説明図である。この「弱い読出操作」は、図５のＭＥＳＩプロトコルにおける「好ましくない読出操作」の問題を解消する。
図１１（Ａ）は、２つのキャッシュ装置１０−１，１０−２のあるキャッシュラインに同じデータが、一方は排他Ｅの状態で他方は無効Ｉの状態で保持されていたとする。次に図１１（Ｂ）のように、プロセッサ１２−２が無効Ｉの状態でキャッシュ装置１０−２のキャッシュラインに保持しているデータのリード要求を行うと、このリード要求はウィークリード要求として扱われることを許されている場合にはウィークリード要求としてキャッシュ装置１０−２で処理される。即ちキャッシュ装置１０−２は、プロセッサからの投機データの提供を許可するウィークリード要求を認識すると、図８（Ｃ）のウィークリードプロトコルの状態遷移に従ったウィークリード処理を実行する。ウィークリード処理は、、プロセッサ１２−２からのウィークリード要求に対しキャッシュ装置１０−２は該当するキャッシュラインのデータが無効Ｉの状態にあることから、排他Ｅの状態にあるキャッシュ装置１０−１にウィークリードを要求し、有効データの転送を受けてキャッシュラインにコピーし、且つ要求元のプロセッサ１２−２に提供する。このとき図５（Ｂ）のＭＥＳＩプロトコルにあってはキャッシュ装置１０−１，１０−２は共有Ｓの状態に遷移するが、図１１（Ｂ）のウィークリードにあっては、キャッシュ装置１０−１から転送した有効データをキャッシュ装置１０−２上では不明Ｕの状態で保持し、キャッシュ装置１０−１は同じ排他Ｅの状態を維持する。
このため、図１１（Ｃ）のように、次にプロセッサ１２−１からキャッシュ装置１０−１にライト要求があったとき、図５（Ｃ）のＭＥＳＩプロトコルでは他のキャッシュ装置１０−２の無効化を必要としたが、図１１（Ｃ）では、無効化は不要であり、他のキャッシュ装置１０−２のキャッシュラインのデータは同じ不明Ｕの状態が維持される。もちろん、ライト要求のあったキャッシュ装置１０−１は排他Ｅの状態から変更Ｍの状態に遷移する。
図１２は、図８（Ｃ）のウィークリードプロトコルの他のキャッシュ動作の例である。図１２（Ａ）にあっては、プロセッサ１０−１のキャッシュラインのデータは変更Ｍの状態で保持されており、キャッシュ装置１０−２のキャッシュラインの同じデータは無効Ｉの状態で保持されている。この図１２（Ａ）の状態で図１２（Ｂ）のようにプロセッサ１２−２が投機データの提供を許可するウィークリード要求を行うと、キャッシュ装置１０−１の有効データをウィークリード要求によりキャッシュ装置１０−２に転送してコピーし、且つ要求元のプロセッサ１０−２に提供する。そして、ウィークリード要求を受けたキャッシュ装置１０−２は無効Ｉの状態から不明Ｕの状態に遷移し、同時にデータ転送元であるキャッシュ装置１０−１は変更Ｍの状態から排他Ｅの状態に遷移する。これは図１１（Ｂ）と同じ状態への遷移となる。このため図１２（Ｃ）のように、次にプロセッサ１２−１からキャッシュ装置１０−１にライト要求があっても、同じデータをキャッシュラインに保持している他のキャッシュ装置１０−２の無効化は不要となる。
（ＭＥＳＩＵプロトコルのキャッシュ管理制御）
図１３は、図８のＭＥＳＩＵプロトコルに従った図７のキャッシュコントローラ１８によるキャッシュ管理制御の第１実施形態のフローチャートである。
図１３において、プロセッサ１２から読出要求があるとキャッシュ管理制御が開始され、まずステップＳ１で要求アドレスのアドレス値をもつ要求データがキャッシュメモリ２０のキャッシュラインに存在するか否かの要求データの所有をチェックする。要求データを所有していれば、ステップＳ２に進み、キャッシュラインの状態タグ２６からデータの有効性をチェックする。状態タグ２６に変更Ｍ、共有Ｓまたは排他Ｅのいずれかの状態が格納されていれば、有効データとしてステップＳ３に進み、キャッシュメモリ２０のキャッシュライン上に保持している有効データを読み出して要求元のプロセッサ１２に提供する。ステップＳ３で有効データを要求元に提供した後の状態制御は、図８（Ａ）のリードプロトコルにおける現在の状態を変更Ｍ、共有Ｓもしくは排他Ｅとして実線のように遷移することから、同じ状態Ｍ，Ｓ，Ｅが維持される。
一方、ステップＳ２でデータの有効性をチェックしたところ不明Ｕ状態であったとすると、ステップＳ４に進み、プロセッサの読出要求に対する提供データが投機データの許可する要求か否かチェックする。このプロセッサに対し投機データの提供を許可する読出要求か否かのチェックは
▲１▼主記憶１６上の投機データの要求元への提供を禁止している特定アドレスか否かを判断、
▲２▼プロセッサ１２が投機データを禁止する命令で生成した読出要求か投機データを許容する命令で生成した読出要求かを判断、
のいずれか又は両方とすれば良い。
ステップＳ４で投機データの提供を許可する読出要求であることが判断されると、ステップＳ５で、それまでの図８（Ａ）のリードプロトコルから図８（Ｃ）のウィークリードプロトコルに切り替え、キャッシュライン上に不明Ｕの状態で保持しているデータを投機データとして要求元のプロセッサ１２に供給する。この投機データの要求元への供給が済むと、キャッシュ装置は図８（Ｃ）のウィークリードの遷移状態のように、同じ不明Ｕの状態を維持する。
このようにステップＳ５で要求元のプロセッサ１２に投機データを供給した場合には、その後に要求元のプロセッサ１２から投機データの有効性の確認要求を受けた際に図１４のフローチャートの処理を行う。この投機データの有効性確認要求処理にあっては、ステップＳ１で主記憶や他のキャッシュへアクセスし、ステップＳ２で投機データの本当の有効性を確認する。ステップＳ３で本当の有効性から有効であることが判別されると、ステップＳ４で要求元のプロセッサに投機データが有効データであることを通知する。この投機データが有効であることの通知を受けたプロセッサは、投機データに基づく命令の実行結果を承認し、これに基づく処理を継続する。一方、ステップＳ３で本当の有効性から投機データが無効であった場合には、ステップＳ５で無効である旨の確認結果を要求元のプロセッサに通知する。投機データが無効であることの通知を受けた要求元のプロセッサは、投機データに基づく命令の実行結果を破棄する。
図１５は、図１４のステップＳ１，Ｓ２における投機データの有効性確認の具体的処理のフローチャートである。まずステップＳ１で主記憶もしくは他のキャッシュ装置をアクセスして有効データを確保する。続いてステップＳ２で投機データと獲得した有効データを比較し、一致すれば、ステップＳ３で要求元のプロセッサに投機データは有効であることを通知する。不一致であれば、ステップＳ４で投機データは無効であることを通知する。
図１６は、図１４のステップＳ１，Ｓ２の投機データの有効性確認の他の具体的処理のフローチャートである。この有効性確認処理にあっては、ステップＳ１で他のキャッシュの状態を調べる。このとき図１１（Ｃ）のように、他のキャッシュ装置１０−１に変更Ｍの状態で有効データが存在するか否かチェックする。もし他のキャッシュ装置上に変更Ｍの状態で有効データが存在すれば、ステップＳ４に進み、投機データは無効と判断して要求元のプロセッサに通知する。なぜなら、他のキャッシュ装置が該当ラインを変更Ｍの状態で保持しているということは、投機データの元となったデータが、既に変更されてしまったことを意味するからである。
一方、ステップＳ２で他のキャッシュ装置上に、変更Ｍの状態で有効データが存在しなければ、投機データは有効と判断して、要求元のプロセッサに通知する。なぜなら、他のキャッシュ装置が該当ラインを変更Ｍの状態で保持していないということは、投機データの元となったデータは変更されておらず、投機データと変わらないことを意味するからである。
再び図１３を参照するに、プロセッサ１２からの読出要求に対し、ステップＳ１で要求データを所有していない場合、ステップＳ２でキャッシュラインの保持データが無効Ｉの状態にある場合、又は、ステップＳ６でプロセッサに対する投機データの提供が禁止されていた場合、ステップＳ６に進み、主記憶１６または他のキャッシュ装置にアクセスして、ステップＳ７で有効データを入手し、ステップＳ８で有効データを要求元のプロセッサ１２に供給する。
ステップＳ６における他のキャッシュ装置へのアクセスは、他のキャッシュ装置の保持データの状態が変更Ｍ、排他Ｅもしくは共有Ｓのいずれかの場合であり、他のキャッシュ装置からもしくは主記憶から有効データの転送を受けてコピーした後に要求元のプロセッサに供給する。この場合のキャッシュ装置の状態遷移は、図８（Ａ）のリードプロトコルのように現在の無効Ｉの状態から共有Ｓの状態に遷移する。またデータ転送を行った他のキャッシュ装置にあっても、排他Ｍの状態であれば共有Ｓの状態に遷移し、排他Ｅの状態であれば同じく共有Ｓの状態に遷移し、共有Ｓの状態であれば同じ状態を維持する。
また他のキャッシュ装置が該当ラインを保持していない場合には、キャッシュ装置は図８（Ａ）のリードプロトコルにおける現在の無効Ｉの状態から排他Ｅ状態に遷移する。
図１７は、図８のＭＥＳＩＵプロトコルによるキャッシュ管理制御の第２実施形態のフローチャートである。この第２実施形態にあっては、投機データを要求元のプロセッサに供給した後、要求元のプロセッサからの確認要求を受けることなく、キャッシュ装置自身で投機データの本当の有効性を確認して記憶し、プロセッサから投機データの有効性の確認要求があったときには記憶結果を通知するようにしたことを特徴とする。
図１７において、プロセッサ１２から読出要求を受けたときのステップＳ１のキャッシュメモリ２０における要求データの所有の有無、ステップＳ２のデータの有効性によるステップＳ３の有効データの要求元への供給、またステップＳ２でキャッシュライン保持データの状態が無効Ｉ状態か、あるいはステップＳ４でプロセッサによる投機データを許可する読出要求でなかった場合のステップＳ９〜Ｓ１１の処理については、図１３のステップＳ１〜Ｓ３及びステップＳ６〜Ｓ８の処理と同じである。
これに対しステップＳ４でプロセッサからの読出要求が投機データを許可する読出要求であった場合には、図８（Ｃ）のウィークリードプロトコルに従って不明Ｕ状態にある保持データを投機データとして要求元のプロセッサに供給した後、ステップＳ６で主記憶や他のキャッシュ装置にアクセスし、ステップＳ７で投機データの本当の有効性を確認し、ステップＳ８で確認結果を記憶する。この場合の投機データの本当の有効性の確認処理も、具体的には図１５または図１６の投機データ有効性の確認処理フローチャートに従って行われる。
図１８は、図１７のステップＳ４〜Ｓ８で投機データを要求元に供給して投機データの本当の有効性の確認を行った後にプロセッサから投機データの有効性の確認要求を受けた場合のフローチャートである。この要求元のプロセッサからの投機データ有効性の確認要求を受けると、ステップＳ１でキャッシュ装置１０に既に記憶してある投機データの本当の有効性を示す確認結果を読み出し、ステップＳ２で本当の有効性が有効であれば、ステップＳ３で要求元に有効を通知し、投機データに基づく命令の実行結果を承認させる。また無効であれば、ステップＳ４で要求元のプロセッサ１２に投機データの無効を通知し、投機データに基づく命令の実行結果を破棄させる。
図１９は、図８のＭＥＳＩプロトコルによるキャッシュ管理制御の第３実施形態のフローチャートである。この第３実施形態にあっては、プロセッサの読出要求に対し、不明Ｕの状態にあるデータを投機データとして供給した場合には、プロセッサからの投機データの有効性確認要求を待つことなく、キャッシュ装置自身で投機データの本当の有効性を確認して、結果を要求元のプロセッサに通知するようにしたことを特徴とする。このためプロセッサからの投機データの有効性確認要求は不要となり、プロセッサの負担を軽減する。
図１９において、ステップＳ１〜Ｓ４、及びステップＳ１１〜Ｓ１３の処理は、図１７の第２実施形態のステップＳ１〜Ｓ４、及びステップＳ９〜Ｓ１１と同じである。またステップＳ４でプロセッサからの投機データの提供を許可する読出要求を判別した場合のステップＳ５〜Ｓ７の処理も図１７の第２実施形態と同じであり、キャッシュ装置自身で投機データを要求元のプロセッサに供給した後、主記憶や他のキャッシュにアクセスして投機データの本当の有効性を確認する。続いてステップＳ８で投機データの本当の有効性が有効であれば、ステップＳ９で要求元のプロセッサに有効を通知し、これにより要求元のプロセッサは投機データに基づく命令の実行結果を承認する。また投機データの本当の有効性が無効であれば、ステップＳ１０で同じく要求元のプロセッサに無効を通知し、投機データに基づく命令の実行結果を破棄させる。
（ＭＥＳＵプロトコルとキャッシュ管理制御）
図２０は、図７の本発明のキャッシュ装置１０で使用されるキャッシュメモリ上に有効性の不明なデータの保存を可能とするキャッシュ管理制御を実現するＭＥＳＵプロトコルの状態遷移図である。このＭＥＳＵプロトコルは、図８のＭＥＳＩＵプロトコルから無効Ｉの状態を取り除いている。
図２０（Ａ）は、ＭＥＳＵリードプロトコル、図２０（Ｂ）はＭＥＳＵライトプロトコルである。この図２０（Ａ）（Ｂ）のＭＥＳＵリードプロトコル及びライトプロトコルによって、図１０の本発明による「弱い無効化操作（ウィークインバリディド）」を同様に実現することができる。
図２０（Ｃ）は、ＭＥＳＵウィークリードプロトコルであり、このＭＥＳＵウィークリードプロトコルによって、図１１に示した本発明の弱い読出操作（ウィークリード操作）と同じキャッシュ管理制御ができる。但し、ＭＥＳＵウィークリードプロトコルの場合、図１１（Ａ）のキャッシュ装置１０−２の状態が無効Ｉではなく不明Ｕとなる点が相違する。この点は図１２のＭＥＳＩＵウィークリードプロトコルの他の処理動作についても同様である。
図２１は、図２０のＭＥＳＵプロトコルの状態遷移表である。この状態遷移表を図９のＭＥＳＩＵプロトコルの状態遷移表と対比して明らかなように、現在の状態が変更Ｍ，排他Ｅ及び共有Ｓについては同じであり、図９の無効Ｉの状態が除かれ、不明Ｕ状態については次の状態が「ＳＥＬＦ」で「weak read」のときの（２）の「Ｅ，Ｕ」への遷移が相違するだけである。
図２２は、図２０のＭＥＳＵプロトコルを使用した図７のキャッシュ装置１０によるキャッシュ管理制御のフローチャートであり、本発明の第４実施形態となる。このＭＥＳＵプロトコルに従ったキャッシュ管理制御にあっては、プロセッサ１２から読出要求があると、ステップＳ１でキャッシュメモリ２０上にデータが保持されているか否かの要求データの所有の有無をチェックし、要求データが所有されていれば、ステップＳ２でデータの有効性をチェックし、状態がＭ，Ｓ，Ｅのいずれかであれば有効として、ステップＳ３に進み、有効データを要求元のプロセッサ１２に供給する。
ステップＳ２でデータの有効性が不明Ｕの状態であった場合には、ステップＳ４に進み、プロセッサが投機データの提供を許可した読出要求か否かチェックする。投機データの許可の読出要求であれば、ステップＳ５で投機データを要求元のプロセッサに供給する。ステップＳ５で投機データを要求元のプロセッサに供給した後、プロセッサから投機データの有効性確認要求を受けると、図２３のフローチャートの処理を行う。この投機データ有効性確認要求の処理は、図１４の第１実施形態の場合と同じである。
再び図２２を参照するに、ステップＳ１でキャッシュメモリ４０上に要求データを所有しない場合、あるいはステップＳ４でプロセッサが投機データの提供を禁止する読出要求であった場合には、ステップＳ６に進み、主記憶１６や他のキャッシュ装置にアクセスし、ステップＳ７で有効データを入手し、ステップＳ８で有効データを要求元に供給する。この図２２のＭＥＳＵプロトコルの本発明の第４実施形態となるキャッシュ管理制御は、図１３のＭＥＳＩＵプロトコルのステップＳ２のデータの有効性の判断結果のうちの無効Ｉの条件分岐を除いた処理である。
図２４は、図２０のＭＥＳＵプロトコルを使用した本発明のキャッシュ管理制御の第５実施形態のフローチャートであり、投機データを要求元のプロセッサに供給した後に、キャッシュ装置１２自身で投機データの有効性を確認して結果を記憶し、その後の要求元のプロセッサからの投機データ有効性の確認要求に対し、キャッシュ装置に記憶している確認結果に基づいて投機データの本当の有効、無効を通知するようにしたことを特徴とする。この図２４の第５実施形態は、図１７のＭＥＳＩＵプロトコルのキャッシュ管理制御の第２実施形態のステップＳ２における無効Ｉの分岐処理を除いたと同じ処理であり、またステップＳ５〜Ｓ８で投機データを供給した後の投機データの本当の有効性の確認結果の記憶は、図１８と同様、要求元のプロセッサからの投機データ有効性の確認要求に対し、記憶した確認結果に基づいた有効または無効の通知を行う。
図２５は、図２０のＭＥＳＵプロトコルを使用した本発明のキャッシュ管理制御の第６実施形態のフローチャートであり、投機データを要求元のプロセッサに供給した後、投機データの本当の有効性の確認と確認結果の要求元への通知をキャッシュ装置自身で行うようにしたことを特徴とする。この図２５の処理は、図１９のＭＥＳＩＵプロトコルにおけるキャッシュ管理制御の第３実施形態のステップＳ２における無効Ｉの分岐処理を除いたと同じ処理になる。
尚、上記の実施形態における本発明の「弱い無効化操作（ウィークインバリディド）」及び「弱い読出操作（ウィークリード）」については、説明を簡単にするため２台のキャッシュ装置を例にとっているが、図６に示したように、システムバス１４で接続されたｎ台の任意の数のキャッシュ装置１０−１〜１０−ｎ間で全く同様に、図８のＭＥＳＩＵプロトコルあるいは図２０のＭＥＳＵプロトコルに従ったキャッシュ管理制御が行われる。
また上記の実施形態での「弱い読出操作（ウィークリード）」は、プロセッサから投機データの提供を許可するウィークリード要求が行われたときに図８（Ｃ）又は図２０（Ｃ）のウィークリードプロトコルに切替えて処理しているが、キャッシュコントローラの立ち上げ時に、図８（Ｃ）又は図２０（Ｃ）のウィークリードプロトコルを固定設定してもよい。この点は、「弱い無効化操作（ウィークインバリディド）」についても同じであり、キャッシュコントローラの立ち上げ時に、図８（Ａ）又は図２０（Ａ）のリードプロトコルを固定設定してもよい。餅録、いずれの場合もライトプロトコルは図８（Ｂ）又は図２０（Ｂ）である。
更に、本発明は上記の実施形態に限定されず、本発明の目的と利点を損なわない適宜の変形を含む。
【産業上の利用の可能性】
本発明のキャッシュ装置及びキャッシュ制御方法は、キャッシュ上に有効性の不明なデータを保持することができることにより、プロセッサに投機的にデータを供給することが可能となり、プロセッサが投機的に命令を実行する機会が増える。これにより、プロセッサからの読出要求でキャッシュミスとなり、主記憶もしくは他のキャッシュメモリからのデータを待つ必要のあったケースの一部で、キャッシュヒットにより投機的に命令実行を進行させることが可能となる。このため本発明は、読出要求を行ったプロセッサのデータ待ち時間を短くすることに貢献し、その結果としてマルチプロセッサシステムの性能を向上できる。
本発明は、マルチプロセッサシステムでキャッシュメモリを管理するキャッシュ装置及び制御方法に関し、特に、有効性のはっきりしないデータのキャッシュメモリでの保持を可能にしてプロセッサに投機的に処理させるキャッシュ装置及び制御方法に関する。
【背景技術】
一般的に、計算機システムの主記憶へのアクセス時間は、プロセッサの動作速度に比べ非常に遅い。そのため、主記憶へのアクセスが発生すると、プロセッサは主記憶から送られるデータを待つことになる。キャッシュ装置は、主記憶に比べて小容量だが高速に動作するメモリであり、プロセッサと主記憶の間に配置され、見かけ上の主記憶アクセス時間を短縮し、プロセッサのデータ待ち時間を短くする。
図１はキャッシュ装置に設けたキャッシュメモリのテーブル構造であり、記憶単位となるキャッシュライン１２２には、タグ１２４とデータ１３０で構成され、タグ１２４には状態タグ１２６とアドレスタグ１２８が付いている。
プロセッサから読出要求を受けると、キャッシュメモリは要求アドレスとアドレス値の一致するアドレスタグ１２８を持ったキャッシュラインを探す。アドレス値の一致するキャッシュラインが存在しない場合は、キャッシュミスとなる。アドレス値の一致するキャッシュラインが存在したとしても、そのキャッシュラインに保持されているデータの有効性が状態タグ１２６から無効であれば、キャッシュミスとなる。キャッシュミスの場合には、主記憶もしくは他キャッシュメモリへのアクセスが必要となる。
アドレスタグ１２８のアドレス値の一致するキャッシュラインが存在し、かつ、そのキャッシュラインに保持されているデータの有効性が状態タグ１２６から有効であれば、キャッシュヒットとなる。キャッシュヒットの場合には、主記憶もしくは他のキャッシュへのアクセスが不要なので、プロセッサのデータ待ち時間は短くて済む。
このように、キャッシュメモリ装置では、要求アドレスとアドレス値の一致するキャッシュラインが存在する場合には、そのキャッシュラインに保持されているデータの有効性が有効であるか無効であるかにより、主記憶もしくは他キャッシュメモリへのアクセスが必要かどうか、プロセッサのデータ待ち時間が短くて済むかどうか、が決まる。
一方、マルチプロセッサシステムでは、プロセッサ毎にキャッシュ装置を持っていることが多い。プロセッサ毎に設けたキャッシュメモリ上のデータは、キャッシュメモリ間に亘ってそのデータの正しさ、即ちデータの一貫性を保つ必要がある。データの一貫性を保つため、キャッシュコヒーレンスプロトコルと呼ばれるキャッシュメモリ間のデータの整合性を保つ規則に従って、キャッシュメモリは管理される。これによりキャッシュメモリ上のデータへのアクセスが可能となっている。
マルチプロセッサシステムにおいて、キャッシュメモリ間に亘ってデータの一貫性を保つ様子を、無効化型キャッシュコヒーレンスプロトコルとして知られたＭＥＳＩプロトコルを使用したキャッシュ装置を例に説明する。
図２（Ａ）は、ＭＥＳＩプロトコルのリード要求に対する状態遷移であり、図２（Ｂ）は、ＭＥＳＩプロトコルのライト要求に対する状態遷移である。この状態繊維の記号は次の内容を表わす。
Ｍ：変更（Modified) であり、複数のキャッシュの１つにのみ有効データが保持されており、かつ、データは変更されており、主記憶のそれと値が同じであることが保証されない。
Ｅ：排他(Exclusive) であり、複数のキャッシュの１つにのみ有効データが保持されている。
Ｓ：共有(Shared)であり、複数のキャッシュ上に同じデータが保持されている。
Ｉ：無効（Invalid)であり、キャッシュ上のデータは無効である。
self : 自己のプロセッサからの要求を処理した場合である。
other : 他のキャッシュ装置からの要求を処理した場合である。
self-if copy:
リード要求に対し無効状態にあり、他のキャッシュが、そのデータを保持している場合。
self-if no copy:
リード要求に対し無効状態にあり、どのキャッシュも、そのデータを保持していない場合。
ここで、キャッシュ上に、データが存在しないという状態は、キャッシュ上にデータが無効Ｉ状態で保持されていることと意味的に等価なので、便宜上、無効Ｉ状態とは、
▲１▼キャッシュ上にそのデータが無効Ｉ状態で保持されている場合と、
▲２▼キャッシュ上にそのデータが存在しない場合
の両方を指すものとする。
同様に、キャッシュ上にデータが存在しないという表現は、
▲１▼キャッシュ上に、本当に、そのデータが存在しない場合と、
▲２▼キャッシュ上に、そのデータが無効Ｉ状態で保持されている場合
の両方を指すものとする。
図３（Ａ）は、マルチプロセッサシステムのキャッシュ装置であり、プロセッサ１０２−１，１０２−２のそれぞれにキャッシュ装置１００−１，１００−２が設けられ、バス１０４により主記憶１０６と共に共通接続されている。
いま図３（Ａ）のように、キャッシュ装置１００−１，１００−２のキャッシュメモリ上に、あるキャッシュラインにデータが共有Ｓ（Shared）状態で保持されているとする。ここで、図３（Ｂ）のように、プロセッサ１０２−１からキャッシュ装置１００−１のデータへの書込要求が発生した場合、キャッシュ装置１００−１のデータを変更し、共有Ｓ状態を変更Ｍ状態とする。しかし、キャッシュ装置１００−１のデータを変更するだけでは、キャッシュ装置１００−１，１００−２間のデータの一貫性が保てない。そのため、キャッシュ装置１００−２の共有Ｓ状態を無効Ｉ状態に変更する無効化操作を行った後、キャッシュメモリ１００−１のデータを変更する操作が必要となる。
その後、図３（Ｃ）のように、プロセッサ１０２−２が変更したデータに対し読出要求を行うと、図３（Ｂ）のプロセッサ１０２−１の書込要求によりキャッシュ装置１００−２のデータは無効Ｉ状態に無効化されているので、その後に発生したプロセッサ１０２−２の読出要求はキャッシュミスとなる。
一般に、キャッシュラインのブロックサイズは、プロセッサの扱うデータサイズよりサイズが大きい。仮に、キャッシュブロックサイズを２ワード、プロセッサの扱うデータサイズを半分の１ワードとする。ここで図４（Ａ）のように、キャッシュ装置１００−１，１００−２が、キャッシュライン１２２−１，１２２−２にある同じデータ、例えば、先頭１ワード部分のデータが“１２”、後方１ワード部分のデータが“３４”である２ワード帳のデータを保持していたとする。。この状態で図４（Ｂ）のように、プロセッサ１０２−１の書込要求がキャッシュライン１２２−１の先頭１ワード部分のデータへの書込要求が発生し、値が“１２”から“５６”に書き替えられたとする。このときキャッシュ装置１００−１，１００−２のキャッシュメモリには、キャッシュライン１２２−１，１２２−２単位で状態が管理されるので、キャッシュ装置１００−２のキャッシュライン１２２−２のデータは、２ワード分の全てが無効Ｉへの状態遷移で無効化される。
次に図４（Ｃ）のように、プロセッサ１０２−１のキャッシュ装置１００−２におけるキャッシュライン１２２−２の読出要求が、後ろ１ワード部分のデータへの読出要求であったとする。この場合、キャッシュ装置１００−１，１００−２におけるキャッシュライン１２２−１，１２２−２の後ろ１ワード部分に保持されているデータの値は“３４”と同じであるにも関わらず、キャッシュライン１２２−２は状態は無効Ｉのためキャッシュミスとなり、主記憶もしくは他キャッシュへのアクセスが発生し、プロセッサ１０２−２はデータ待ちになる。いわゆるいわつりの共有（false sharing ）によるキャッシュミスである。このようなキャッシュミスを発生させてしまう無効化操作を「好ましくない無効化操作」と呼ぶことにする。
一方、図５（Ａ）のように、あるデータがプロセッサ１０２−１のキャッシュ装置１００−１に排他Ｅの状態で保持されており、プロセッサ１０２−２のキャッシュ装置１００−２には存在しないか又は無効Ｉの状態でデータが保持されていたとする。ここで、図５（Ｂ）のように、プロセッサ１０２−２からキャッシュ装置１００−２のデータへの読出要求が発生すると、キャッシュ装置１００−１に排他Ｅの状態で保持しているデータを、キャッシュ装置１００−２に転送してプロセッサ１０２−２に提供し、この結果、キャッシュ装置１００−１，１００−２で共有されることになる。従って、データをキャッシュ装置１００−１もしくは主記憶から１００−２へデータを転送する操作と、キャッシュ装置１００−１の排他Ｅの状態から共有Ｓの状態に変える操作が必要となる。
このようにプロセッサ１０２−２の読出要求で、キャッシュ装置１００−１の状態が排他Ｅの状態から共有Ｓの状態に変わった後に、図５（Ｃ）のように、プロセッサ１０２−１が書込要求を行うと、キャッシュ装置１００−２の状態を共有Ｓの状態から無効Ｉの状態に変える無効化操作が必要となり、無効化後にキャッシュ装置１００−１の状態を共有Ｓから変更Ｍに変える。
近年のプロセッサは、条件分岐を動的又は静的に予測し、投機的に命令を実行する機能を備えており、その結果、投機的な読出要求を出す。投機的な読出命令の実行は予測に基づく命令実行であるので、その予測が正しければ良いが、誤りであればその投機的な実行結果は破棄される。つまり、投機的に実行された読出要求により読み出されたデータは、利用されない可能性がある。
図５（Ｂ）のプロセッサ１０２−２の読出要求が、もし誤った予測に基づく読出要求であったとしても、プロセッサ１０２−２の読出要求によりキャッシュ装置１００−１の状態を排他Ｅから共有Ｓに変える操作が実行されてしまう。そのため、図５（Ｃ）のように、その後に発生するプロセッサ１０２−１の書込要求では、本質的には必要のない共有Ｓの状態にあるキャッシュ装置１００−２のデータの状態を無効Ｉに変える無効化操作が必要となる。この読出データが結果的に利用されない読出要求の実行でキャッシュメモリの状態を共有Ｓに変えしてまう操作を、「好ましくない読出操作」と呼ぶこととする。
【発明の開示】
本発明に従えば、「好ましくない無効化操作」により発生するキャッシュミスを減らし、プロセッサのデータ待ち時間を短くするキャッシュ装置及び制御方法が提供される。
また本発明に従えば、「好ましくない読出操作」により必要となる無効化操作を減らしてプロセッサのデータ待ち時間を短くするキャッシュ装置及び制御方法が提供される。
本発明は、複数のプロセッサ毎に設けられ、相互にバス接続されると共に主記憶とバス接続されたキャッシュ装置に於いて、主記憶の一部のデータをキャッシュライン単位に保持すると共にキャッシュラインに保持したデータの状態を
▲１▼有効
▲２▼無効
▲３▼不明
の３種類の状態で区別するキャッシュメモリと、自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効、無効、又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラとを備えたことを特徴とする。
このように本発明では、データの有効性が有効であるか無効であるか確かではないデータを、有効性の不明なデータとしてキャッシュラインに保持することを許す。そして、「好ましくない無効化操作」を「弱い無効化操作（ウィーク・インバリデイト weak -invalidate）」により処理し、また「好ましくない読出操作」を「弱いリード操作（ウィークリート；weak-read）」により処理することで問題を解決する。
「弱い無効化操作」は、キャッシュラインを無効化する代わりに、キャッシュライン上のデータを有効性の不明なデータとして保持し続けることを許す。例えばキャッシュコヒーレンスのためのＭＥＳＩプロトコルの「好ましくない無効化操作」では、共有Ｓの状態にある２つのキャッシュメモリデータの一方に書込要求が発生すると、他方のキャッシュメモリのデータは無効化されてしまうが、本発明の「弱い無効化操作」では、無効化されずに有効性の不明なデータとして保持され続ける。このため「好ましくない無効化操作」ではプロセッサの読出要求でキャッシュミスとなるが、本発明の「弱い無効化操作」ではキャッシュメモリは有効性の不明なデータを保持しているため、読出要求に対し投機データとしてプロセッサに供給できる。このような本発明の「弱い無効化操作」は、ＭＥＳＩプロトコルに不明Ｕの状態を加えたＭＥＳＩＵプロトコルということができる。
本発明の「弱い読出操作」は、本発明の「弱い無効化操作」を実現するＭＥＳＩＵプロトコルに従ったキャッシュ管理制御において、プロセッサがキャッシュメモリに保持された有効性が不明なデータを投機データとして提供を許可するウィークリード要求が生じた時に実行される。この場合、読出要求を受けたキャッシュ装置は、他のキャッシュ装置に保持している有効データを読出転送して要求元に応答して自分にコピーする。このとき本発明の「弱い読出操作」では、他のキャッシュメモリから転送したデータを、有効なデータとしてではなく、有効性の不明なデータとして扱う。
即ち、ＭＥＳＩプロトコルの「好ましくない読出操作」では、無効Ｉの状態にあるキャッシュメモリのデータは排他Ｅの状態にある他のキャッシュメモリから転送した場合、各々共有Ｓの状態に変更される。しかし、本発明の「弱い読出操作」で処理した場合は、他のキャッシュメモリのデータは排他Ｅの状態のまま変更されず、読出対象のキャッシュメモリに転送されたデータは有効性の不明なデータ、即ち不明Ｕの状態のデータとして保持される。従って、その後、に排他Ｅの状態にある他のキャッシュデータに書込要求があっても、同じデータを不明Ｕの状態で保持しているキャッシュメモリの無効化操作は必要なくなる。
本発明の弱い読出操作は、プロセッサがキャッシュメモリに保持された有効性が不明なデータを投機データとして提供を許可するウィークリード要求が生じた時とする以外に、キャッシュ装置の機能として固定設定してもよい。
本発明の別の形態にあっては、複数のプロセッサ毎に設けられ、相互にバス接続すると共に主記憶とバス接続されたキャッシュ装置に於いて、主記憶の一部のデータをキャッシュライン単位に保持すると共にキャッシュラインに保持したデータの状態を
▲１▼有効
▲２▼不明
の２種類の状態で区別するキャッシュメモリと、自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラとを備えたことを特徴とする。
この場合にも、データの有効性が有効であるかが確かではないデータを、有効性の不明なデータとしてキャッシュラインに保持することを許す。そして、同様にして「好ましくない無効化操作」を「弱い無効化操作（weak-invalidate）」により処理し、また「好ましくない読出操作」を「弱いリード操作（weak-read）」により処理することで問題を解決する。これは本発明のＭＥＳＩＵプロトコルから無効Ｉの状態を除いたＭＥＳＵプロトコルということができる。
キャッシュコントローラは、有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した際に、投機データの要求元への提供許可か提供禁止かを判定し、提供許可を判定した場合は、有効性の不明なデータを投機データとして要求元に提供し、提供禁止を判定した場合は、他のキャッシュ装置又は主記憶から有効データを入手して要求元に提供させる。
キャッシュコントローラは、投機データを要求元に提供した後、要求元から投機データの有効性確認要求が発生した際に、投機データの本当の有効性を確認して確認の結果を要求元に通知する。
またキャッシュコントローラは、投機データを要求元に提供すると同時に、投機データの本当の有効性を確認して確認の結果を記憶し、要求元から前記投機データの有効性の確認要求が発生した際に、記憶しておいた有効性の確認結果を要求元に通知するようにしてもよい。
更に、キャッシュコントローラは、投機データを要求元に提供すると同時に、投機データの本当の有効性を自分自身で確認し、確認結果を要求元に通知するようにしてもよい。
キャッシュコントローラは、確認結果から投機データが有効であった場合は、要求元のプロセッサに確認結果を通知して投機データに基づく命令の実行結果を承認させ、一方、確認結果から投機データが無効であった場合は、要求元のプロセッサに確認結果を通知して投機データに基づく命令の実行結果を破棄させる。このように有効性の不明なデータを保持することができる本発明のキャッシュ装置により、プロセッサに投機的にデータを供給することが可能となり、投機データの提供でキャッシュミスを低減し、プロセッサの待ち時間を短縮してキャッシュ性能を向上させる。
キャッシャコントローラは、主記憶の予め定めた特定アドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を禁止し、主記憶の特定アドレス以外のアドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を許可する。
またキャッシャコントローラは、プロセッサの投機データを禁止する命令の実行で生成した読出要求を有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を禁止し、プロセッサの投機データを許容する命令の実行、例えば分岐予測の結果、生成された読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を許可する。このように投機的な読出要求か否かを、主記憶のアドレスまたはプロセッサ実行命令から識別し、プロセッサの投機的な命令実行と投機的でない通常の命令実行を区別したキャッシュ管理制御を行う。
キャッシュコントローラは、キャッシュラインの保持データの状態を、有効を示す変更Ｍ、排他Ｅ及び共有Ｓと無効Ｉの４状態で区別するキャッシュコヒーレンスのＭＥＳＩプロトコルに、データの有効性が不明であることを示す状態Ｕを加えた５状態で区別するキャッシュコヒーレンスのＭＥＳＩＵプロトコルとする。このＭＥＳＩＵプロトコルが、前述したように本発明の「弱い無効化操作」を実現する。
キャッシュコントローラは、キャッシュラインの保持データに対するリード要求を処理した場合、ＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置で読出要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求により主記憶からデータをコピーした場合は排他Ｅに状態遷移し、他のキャッシュ装置からコピーした場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する。
また、キャッシュコトローラは、キャッシュラインの保持データに対するライト要求を処理した場合には、ＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
キャッシュコントローラは、不明Ｕの状態で保持したデータの提供を許すプロセッサからのウィークリード要求（弱い読出要求）を処理した場合、ウィークリードでのキャッシュコヒーレンスのためのＭＥＳＩＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの弱い読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの弱い読出要求であれば排他Ｅに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置からの弱い読出要求であれば同じ排他Ｅに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置からの弱い読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼無効Ｉの状態で、自己のプロセッサの弱い読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は不明Ｕに状態遷移し、更に他のキャッシュ装置の弱い読出要求であれば同じ無効Ｉに状態遷移する。
▲５▼不明Ｕの状態で、自己のプロセッサの弱い読出要求又は他のキャッシュ装置の弱い読出要求であれば同じ不明Ｕに状態遷移する。
このウィークリード要求を実現するＭＥＳＩＵプロトコルは、プロセッサからウィークリード要求を受けた際に実行せずに、キャッシュコントローラで固定設定してもよい。
キャッシュコントローラは、キャッシュラインの保持データの状態を、有効を示す変更、排他及び共有の３状態で区別するＭＥＳプロトコルに、データの有効性が不明であることを示す状態Ｕを加えた４状態で区別するＭＥＳＵプロトコルを備える。
キャッシュコントローラは、キャッシュラインの保持データに対するリード要求を処理した場合、このＭＥＳＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置からの読出要求であれば同じ不明Ｕに状態遷移する。
またキャッシュコントローラは、キャッシュラインの保持データに対するライト要求を処理した場合、ＭＥＳＵプロトコルに基づき次のように処理する。
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
▲４▼不明Ｕで、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する。
またキャッシュコントローラは、キャッシュラインに不明Ｕの状態で保持した投機データの提供を許可するプロセッサからのウィークリード要求（弱い読出要求）命令を処理した場合、ＭＥＳＵプロトコルに基づき次の処理を行う。
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移する。
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移する。
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移する。
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求で、他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が、該当ラインを保持している場合又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する。
このウィークリード要求を実現するＭＥＳＵプロトコルについても、プロセッサからウィークリード要求を受けた際に実行する以外に、キャッシュコントローラでＭＥＳＵプロトコルを固定設定してもよい。
一方、本発明は、複数のプロセッサ毎に設けたキャッシュ装置を相互にバス接続すると共に主記憶とバス接続したキャッシュ制御方法を提供する。
このキャッシュ制御方法は、
▲１▼主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効、無効、及び不明の３種類の状態で区別し、
▲２▼自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効、無効、又は不明の状態に応じて処理し（ＭＥＳＵＩプロトコル）、
▲３▼要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するために定めた所定の状態に遷移させることを特徴とする。
また本発明のキャッシュ制御方法の別の形態にあっては、
▲１▼主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効及び不明の２種類で区別し、
▲２▼自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理し（ＭＥＳＵプロトコル）、
▲３▼要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを維持するために定めた所定の状態に遷移させる。
この本発明によるキャッシュ制御方法の詳細は、装置構成の場合と基本的に同じになる。
【図面の簡単な説明】
図１はキャッシュメモリのテーブル構造の説明図
図２はＭＥＳＩプロトコルの状態遷移図
図３はＭＥＳＩプロトコルにおける好ましくない無効化操作を招くキャッシュ動作の説明図
図４は図３の好ましくない無効化操作におけるキャッシュラインの説明図
図５はＭＥＳＩプロトコルにおける好ましくない読出操作を招くキャッシュ動作の説明図
図６は本発明のキャッシュ装置が使用されるマルチプロセッサシステムのブロック図
図７は本発明のキャッシュ装置の機能ブロック図
図８はキャッシュ保持データを不明として扱う本発明の弱い無効化操作及び弱い読出操作を実現するＭＵＳＩＵプロトコルの状態遷移図
図９は図８のＭＵＳＩＵプロトコルの状態遷移表の説明図
図１０は図３の好ましくない無効化操作の問題を解消する本発明の弱い無効化操作の説明図
図１１は図５の好ましくない読出操作の問題を解消する本発明の弱い読出操作の説明図
図１２は本発明の弱い読出操作の他の動作形態の説明図
図１３は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第１実施形態のフローチャート
図１４は図１３で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図１５は図１４の投機データの有効性確認のフローチャート
図１６は図１４の投機データの他の有効性確認のフローチャート
図１７は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第２実施形態のフローチャート
図１８は図１７で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図１９は図７のキャッシュコントローラによる本発明のキャッシュ管理制御の第３実施形態のフローチャート
図２０はキャッシュ保持データを不明として扱う本発明の弱い無効化操作及び弱い読出操作を実現するＭＥＳＵプロトコルの状態遷移図
図２１は図２０のＭＥＳＵプロトコルの状態遷移表の説明図
図２２は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第４実施形態のフローチャート
図２３は図２２で投機データを要求元に提供した後に実行する確認要求処理のフローチャート
図２４は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第５実施形態のフローチャート
図２５は図２０のＭＥＳＵプロトコルを使用したキャッシュコントローラによる本発明のキャッシュ管理制御の第６実施形態のフローチャート
【発明を実施するための最良の形態】
（装置構成と機能）
図６は本発明のキャッシュ装置および制御方法が適用されたマルチプロセッサシステムのブロック図である。
図６において、本発明のキャッシュ装置１０−１，１０−２，・・・１０−ｎは、それぞれプロセッサ１２−１，１２−２，・・・１２−ｎに対応して設けられる。キャッシュ装置１０−１〜１０−ｎは、システムバス１４により相互に接続され、更にシステムバス１４により主記憶１６と接続されている。キャッシュ装置１０−１〜１０−ｎを接続するシステムバス１４としては、例えばスヌープバスを使用する。スヌープバスはキャッシュ装置１０−１〜１０−ｎのいずれかでプロセッサ１２−１〜１２−ｎから処理要求があった際に、処理要求に該当するキャッシュラインに保持しているデータの状態をスヌープ制御線の状態信号により直ちに取得できるバスである。
図７は、本発明のキャッシュ装置１０の機能ブロック図である。キャッシュ装置１０は、キャッシュコントローラ１８とキャッシュメモリ２０で構成される。キャッシュメモリ２０は、複数のキャッシュライン２２単位にデータを保持しており、各キャッシュライン２２はタグ２４とデータ３０を含み、タグ２４は状態タグ２６のアドレスタグ２８を備える。キャッシュメモリ２０の状態タグ２６につき本発明にあっては、保持データの状態として有効及び無効に加えて、有効性の不明なデータを保持することができる。
キャッシュコントローラ１８には、キャッシュ制御管理部３２、状態管理部３４、プロセッサインタフェース３６、バスインタフェース３８が設けられる。また状態管理部３４には、リードプロトコル処理部４０、ウィークリードプロトコル処理部４２、投機データ確認部４４及びライトプロトコル処理部４６が設けられる。
キャッシュ制御管理部３２は、プロセッサ１２から読出要求を受けると、キャッシュメモリ２０のタグ２４を参照し、要求アドレスとアドレス値の一致するアドレスタグ２８をもったキャッシュライン２２を検索する。アドレス値の一致するキャッシュラインが存在しない場合にはキャッシュミスとなり、主記憶１６もしくは他のキャッシュ装置から有効データを獲得してプロセッサ１２に提供する。
キャッシュ制御管理部３２は、要求アドレスに一致するアドレスのキャッシュラインが存在した場合には、そのキャッシュラインの状態タグ２６による有効、無効、不明の状態に応じた処理を行う。即ち状態が有効であれば、キャッシュメモリ１０上に保持されているデータをプロセッサ１２に提供する。無効であれば他のキャッシュ装置または主記憶から有効データを入手してプロセッサ１２に応答する。更に不明であれば、プロセッサ１２が投機データの提供を許可していることを条件に、キャッシュメモリ２０上に有効性が不明な状態で保持しているデータを、投機データとしてプロセッサ１２に提供する。
キャッシュ制御管理部３２は、プロセッサ１２からの書込要求に対しては、キャッシュヒットであればキャッシュメモリ２０上の該当するキャッシュラインのデータを更新し、ミスヒットであればキャッシュメモリ２０上に新たなキャッシュラインを確保してデータを書き込む。
このようなキャッシュ制御管理部３２によるプロセッサ１２及びシステムバス１４を経由した他のキャッシュ装置からの処理要求に対し、状態管理部３４が処理要求を実行した後の該当するキャッシュライン上の状態タグ２６の状態遷移制御を行う。状態管理部３４によるキャッシュコヒーレンスのための状態遷移制御として、本発明にあっては、図２のＭＥＳＩプロトコルに更に、有効性の不明なデータの保持を示す不明Ｕの状態を加えたＭＥＳＩＵプロトコルを適用している。
図８は、図７の状態管理部３４で使用されるＭＥＳＩＵプロトコルの状態遷移の説明図である。即ち図８（Ａ）が、リードプロトコル処理部４０で処理する読出要求に対するＭＥＳＩＵリードプロトコルの状態遷移である。また図８（Ｂ）が、図７のライトプロトコル処理部４６によるＭＥＳＩＵライトプロトコルの状態遷移である。この図８（Ａ）及び（Ｂ）のＭＥＳＩＵのリードプロトコル及びライトプロトコルは、図３のＭＥＳＩプロトコルにおける「好ましくない無効化操作」を解消するための本発明による「弱い無効化操作」のキャッシュ管理制御を実現する。
更に図８（Ｃ）は、図７のウィークリードプロトコル処理部４２で処理されるＭＥＳＩＵウィークリードプロトコルの状態遷移である。このＭＥＳＩＵウィークリードプロトコルは、図５に示したＭＥＳＩプロトコルにおける「好ましくない読出操作」の問題を解消するための本発明の「弱い読出操作」のキャッシュ管理制御を実現する。
ここで図８（Ａ）（Ｂ）（Ｃ）の各プロトコルにおいて、状態Ｍは変更（Modified）、状態Ｅは排他（Exclusive ）、状態Ｓは共有（Shared）、状態Ｉは無効（Invalid ）を表わし、更に本発明にあっては新たに、有効性の不明なデータ保持の状態として不明（Unknown ）を追加している。
また図８（Ａ）のリードで、状態Ｍ，Ｅ，Ｓにおける実線の遷移は、自己のプロセッサからリード要求を処理した場合であり、破線は他のキャッシュ装置でリード要求が処理された場合である。また無効Ｉにあっては他の装置での読出要求は破線のように状態変化を起こさないが、自己のプロセッサからの読出要求にあっては、他キャッシュ装置が該当ラインを保持していない(self-if no copy) の場合には排他Ｅに状態遷移し、他キャッシュ装置が該当ラインを保持している(self-if copy)の場合には共有Ｓに状態遷移する。
図８（Ｂ）のＭＥＳＩＵライトプロトコルの状態遷移にあっては、状態Ｍ，Ｅ，Ｓ，Ｉ，Ｕのそれぞれについて、自己のプロセッサからの書込要求を処理した場合ついては実線のように遷移し、他のキャッシュ装置で書込要求が処理された場合については破線のように遷移する。図８（Ｃ）のＭＥＳＩＵウィークリードプロトコルの破線及び実線の遷移は、図８（Ａ）のＭＥＳＩＵリードプロトコルと同じ意味をもつ。
図９は、図８のＭＥＳＩＵプロトコルの状態遷移表である。この状態遷移表は、縦方向に現在のキャッシュラインに保持したデータの状態を表わし、横方向に次の状態として自己のプロセッサからの要求を「ＳＥＬＦ」、他のキャッシュ装置での要求を「ＯＴＨＥＲ」として、図８（Ａ）（Ｂ）（Ｃ）のリード、ライト及びウィークリードに分けて状態遷移を表わしている。
このうち、次の状態が「Ｅ，Ｓ」及び「Ｅ，Ｕ」に付した（１）（２）は、図８（Ａ）のリードプロトコルにおける現在の状態Ｉからの実線の「ＳＥＬＦ−ＩＦ ＮＯ ＣＯＰＹ」と「ＳＥＬＦ−ＩＦ−ＣＯＰＹ」に対応している。例えば現在の状態Ｉで次の状態が自己プロセッサからのリード要求の結果遷移する状態「Ｅ，Ｓ」の（１）については、図８（Ａ）の状態Ｉのように、他のどのキャッシュ装置が該当するキャッシュラインを保持していない場合は排他Ｅに遷移し、それ以外の他のキャッシュ装置が該当ラインを保持している場合には共有Ｓに遷移する。また（２）で示す次の状態「Ｅ，Ｕ」については、図８（Ｃ）の現在の状態Ｉから次の状態ＥまたはＵへの遷移を表わす。更に図９の（３）で示す次の状態「Ｅ，Ｓ」への遷移は、図８（Ａ）のリードプロトコルにおける現在の状態Ｕにおいて自己のプロセッサからリード要求を受けた場合であり、この場合にも、どのキャッシュ装置にも該当するキャッシュラインを保持していないときは排他Ｅの状態に遷移し、それ以外の他のキャッシュ装置が該当ラインを保持している場合は共有Ｓに状態遷移する。
（弱い無効化操作と弱い読出操作）
図１０は、図８（Ａ）（Ｂ）のＭＥＳＩＵプロトコルにより処理で、図３のＭＥＳＩプロトコルで「好ましくない無効化操作」が生じたと同じプロセッサからの処理要求があったときの本発明による「弱い無効化操作」の動作説明である。
図１０（Ａ）は、２つのキャッシュ装置１０−１，１０−２のあるキャッシュラインについて、同じデータが共有Ｓの状態で保持されていたとする。この状態で、図１０（Ｂ）のように、プロセッサ１２−１から共有Ｓの状態で保持しているデータに対しライト要求を受けて処理したとすると、図８（Ｂ）のライトプロトコルの状態遷移に従い、キャッシュ装置１０−１の状態は共有Ｓから変更Ｍに遷移する。同時に、同じデータをキャッシュラインに保持しているキャッシュ装置１０−２にあっては、図８（Ｂ）のライトプロトコルの状態遷移に従い、他のキャッシュ装置１０−１で書込みがあったことから不明Ｕの状態に遷移する。この図１０（Ａ）の２つのキャッシュメモリ１０−１，１０−２の共有Ｓ状態が、図１０（Ｂ）のように一方のキャッシュ装置１０−１に対するプロトコル１２−１の書込要求で変更Ｍに遷移したとき、他のキャッシュ装置１０−２の共有Ｓの状態を図３（Ｂ）のように無効Ｉの状態とせずに不明Ｕの状態とするのが、本発明の「弱い無効化操作（ウィークインバリデイト）」である。
続いて図１０（Ｃ）のように、プロセッサ１２−２からのリード要求をキャッシュ装置１０−２で処理すると、このときのデータは不明Ｕの状態で保持しており、無効ではないことからキャッシュヒットとなって、不明Ｕの状態で保持したデータを要求元のプロセッサ１２−２に投機的データとして提供する。この場合には図８（Ａ）のリードプロトコルの状態遷移のように、リード要求のあったキャッシュ装置１０−２の不明Ｕの状態は共有Ｓの状態に遷移し、同時に他のキャッシュ装置１０−１の変更Ｍの状態も共有Ｓの状態に遷移する。
この図１０（Ａ）におけるキャッシュ装置１０−１，１０−２が共有Ｓの状態にあるときのいずれか一方、例えばプロセッサ１２−１からの書込要求に対し、他のキャッシュ装置１０−２のキャッシュラインを無効化せずに不明Ｕの状態とする弱い無効化操作（ウィークインバリディド）を行うことで、次の図１０（Ｃ）のようにプロセッサ１２−２がリード要求をキャッシュ装置１０−２に行ったとき、ミスヒットとならずにキャッシュヒットとして不明Ｕの状態にあるデータをプロセッサ１２−２に投機的データとして提供でき、無効Ｉの状態では必要だったプロセッサのデータ待ちの時間を短くすることができる。
図１１は、図８（Ｃ）のウィークリードプロトコルに従った本発明の「弱い読出操作」の動作説明図である。この「弱い読出操作」は、図５のＭＥＳＩプロトコルにおける「好ましくない読出操作」の問題を解消する。
図１１（Ａ）は、２つのキャッシュ装置１０−１，１０−２のあるキャッシュラインに同じデータが、一方は排他Ｅの状態で他方は無効Ｉの状態で保持されていたとする。次に図１１（Ｂ）のように、プロセッサ１２−２が無効Ｉの状態でキャッシュ装置１０−２のキャッシュラインに保持しているデータのリード要求を行うと、このリード要求はウィークリード要求として扱われることを許されている場合にはウィークリード要求としてキャッシュ装置１０−２で処理される。即ちキャッシュ装置１０−２は、プロセッサからの投機データの提供を許可するウィークリード要求を認識すると、図８（Ｃ）のウィークリードプロトコルの状態遷移に従ったウィークリード処理を実行する。ウィークリード処理は、、プロセッサ１２−２からのウィークリード要求に対しキャッシュ装置１０−２は該当するキャッシュラインのデータが無効Ｉの状態にあることから、排他Ｅの状態にあるキャッシュ装置１０−１にウィークリードを要求し、有効データの転送を受けてキャッシュラインにコピーし、且つ要求元のプロセッサ１２−２に提供する。このとき図５（Ｂ）のＭＥＳＩプロトコルにあってはキャッシュ装置１０−１，１０−２は共有Ｓの状態に遷移するが、図１１（Ｂ）のウィークリードにあっては、キャッシュ装置１０−１から転送した有効データをキャッシュ装置１０−２上では不明Ｕの状態で保持し、キャッシュ装置１０−１は同じ排他Ｅの状態を維持する。
このため、図１１（Ｃ）のように、次にプロセッサ１２−１からキャッシュ装置１０−１にライト要求があったとき、図５（Ｃ）のＭＥＳＩプロトコルでは他のキャッシュ装置１０−２の無効化を必要としたが、図１１（Ｃ）では、無効化は不要であり、他のキャッシュ装置１０−２のキャッシュラインのデータは同じ不明Ｕの状態が維持される。もちろん、ライト要求のあったキャッシュ装置１０−１は排他Ｅの状態から変更Ｍの状態に遷移する。
図１２は、図８（Ｃ）のウィークリードプロトコルの他のキャッシュ動作の例である。図１２（Ａ）にあっては、プロセッサ１０−１のキャッシュラインのデータは変更Ｍの状態で保持されており、キャッシュ装置１０−２のキャッシュラインの同じデータは無効Ｉの状態で保持されている。この図１２（Ａ）の状態で図１２（Ｂ）のようにプロセッサ１２−２が投機データの提供を許可するウィークリード要求を行うと、キャッシュ装置１０−１の有効データをウィークリード要求によりキャッシュ装置１０−２に転送してコピーし、且つ要求元のプロセッサ１０−２に提供する。そして、ウィークリード要求を受けたキャッシュ装置１０−２は無効Ｉの状態から不明Ｕの状態に遷移し、同時にデータ転送元であるキャッシュ装置１０−１は変更Ｍの状態から排他Ｅの状態に遷移する。これは図１１（Ｂ）と同じ状態への遷移となる。このため図１２（Ｃ）のように、次にプロセッサ１２−１からキャッシュ装置１０−１にライト要求があっても、同じデータをキャッシュラインに保持している他のキャッシュ装置１０−２の無効化は不要となる。
（ＭＥＳＩＵプロトコルのキャッシュ管理制御）
図１３は、図８のＭＥＳＩＵプロトコルに従った図７のキャッシュコントローラ１８によるキャッシュ管理制御の第１実施形態のフローチャートである。
図１３において、プロセッサ１２から読出要求があるとキャッシュ管理制御が開始され、まずステップＳ１で要求アドレスのアドレス値をもつ要求データがキャッシュメモリ２０のキャッシュラインに存在するか否かの要求データの所有をチェックする。要求データを所有していれば、ステップＳ２に進み、キャッシュラインの状態タグ２６からデータの有効性をチェックする。状態タグ２６に変更Ｍ、共有Ｓまたは排他Ｅのいずれかの状態が格納されていれば、有効データとしてステップＳ３に進み、キャッシュメモリ２０のキャッシュライン上に保持している有効データを読み出して要求元のプロセッサ１２に提供する。ステップＳ３で有効データを要求元に提供した後の状態制御は、図８（Ａ）のリードプロトコルにおける現在の状態を変更Ｍ、共有Ｓもしくは排他Ｅとして実線のように遷移することから、同じ状態Ｍ，Ｓ，Ｅが維持される。
一方、ステップＳ２でデータの有効性をチェックしたところ不明Ｕ状態であったとすると、ステップＳ４に進み、プロセッサの読出要求に対する提供データが投機データの許可する要求か否かチェックする。このプロセッサに対し投機データの提供を許可する読出要求か否かのチェックは
▲１▼主記憶１６上の投機データの要求元への提供を禁止している特定アドレスか否かを判断、
▲２▼プロセッサ１２が投機データを禁止する命令で生成した読出要求か投機データを許容する命令で生成した読出要求かを判断、
のいずれか又は両方とすれば良い。
ステップＳ４で投機データの提供を許可する読出要求であることが判断されると、ステップＳ５で、それまでの図８（Ａ）のリードプロトコルから図８（Ｃ）のウィークリードプロトコルに切り替え、キャッシュライン上に不明Ｕの状態で保持しているデータを投機データとして要求元のプロセッサ１２に供給する。この投機データの要求元への供給が済むと、キャッシュ装置は図８（Ｃ）のウィークリードの遷移状態のように、同じ不明Ｕの状態を維持する。
このようにステップＳ５で要求元のプロセッサ１２に投機データを供給した場合には、その後に要求元のプロセッサ１２から投機データの有効性の確認要求を受けた際に図１４のフローチャートの処理を行う。この投機データの有効性確認要求処理にあっては、ステップＳ１で主記憶や他のキャッシュへアクセスし、ステップＳ２で投機データの本当の有効性を確認する。ステップＳ３で本当の有効性から有効であることが判別されると、ステップＳ４で要求元のプロセッサに投機データが有効データであることを通知する。この投機データが有効であることの通知を受けたプロセッサは、投機データに基づく命令の実行結果を承認し、これに基づく処理を継続する。一方、ステップＳ３で本当の有効性から投機データが無効であった場合には、ステップＳ５で無効である旨の確認結果を要求元のプロセッサに通知する。投機データが無効であることの通知を受けた要求元のプロセッサは、投機データに基づく命令の実行結果を破棄する。
図１５は、図１４のステップＳ１，Ｓ２における投機データの有効性確認の具体的処理のフローチャートである。まずステップＳ１で主記憶もしくは他のキャッシュ装置をアクセスして有効データを確保する。続いてステップＳ２で投機データと獲得した有効データを比較し、一致すれば、ステップＳ３で要求元のプロセッサに投機データは有効であることを通知する。不一致であれば、ステップＳ４で投機データは無効であることを通知する。
図１６は、図１４のステップＳ１，Ｓ２の投機データの有効性確認の他の具体的処理のフローチャートである。この有効性確認処理にあっては、ステップＳ１で他のキャッシュの状態を調べる。このとき図１１（Ｃ）のように、他のキャッシュ装置１０−１に変更Ｍの状態で有効データが存在するか否かチェックする。もし他のキャッシュ装置上に変更Ｍの状態で有効データが存在すれば、ステップＳ４に進み、投機データは無効と判断して要求元のプロセッサに通知する。なぜなら、他のキャッシュ装置が該当ラインを変更Ｍの状態で保持しているということは、投機データの元となったデータが、既に変更されてしまったことを意味するからである。
一方、ステップＳ２で他のキャッシュ装置上に、変更Ｍの状態で有効データが存在しなければ、投機データは有効と判断して、要求元のプロセッサに通知する。なぜなら、他のキャッシュ装置が該当ラインを変更Ｍの状態で保持していないということは、投機データの元となったデータは変更されておらず、投機データと変わらないことを意味するからである。
再び図１３を参照するに、プロセッサ１２からの読出要求に対し、ステップＳ１で要求データを所有していない場合、ステップＳ２でキャッシュラインの保持データが無効Ｉの状態にある場合、又は、ステップＳ６でプロセッサに対する投機データの提供が禁止されていた場合、ステップＳ６に進み、主記憶１６または他のキャッシュ装置にアクセスして、ステップＳ７で有効データを入手し、ステップＳ８で有効データを要求元のプロセッサ１２に供給する。
ステップＳ６における他のキャッシュ装置へのアクセスは、他のキャッシュ装置の保持データの状態が変更Ｍ、排他Ｅもしくは共有Ｓのいずれかの場合であり、他のキャッシュ装置からもしくは主記憶から有効データの転送を受けてコピーした後に要求元のプロセッサに供給する。この場合のキャッシュ装置の状態遷移は、図８（Ａ）のリードプロトコルのように現在の無効Ｉの状態から共有Ｓの状態に遷移する。またデータ転送を行った他のキャッシュ装置にあっても、排他Ｍの状態であれば共有Ｓの状態に遷移し、排他Ｅの状態であれば同じく共有Ｓの状態に遷移し、共有Ｓの状態であれば同じ状態を維持する。
また他のキャッシュ装置が該当ラインを保持していない場合には、キャッシュ装置は図８（Ａ）のリードプロトコルにおける現在の無効Ｉの状態から排他Ｅ状態に遷移する。
図１７は、図８のＭＥＳＩＵプロトコルによるキャッシュ管理制御の第２実施形態のフローチャートである。この第２実施形態にあっては、投機データを要求元のプロセッサに供給した後、要求元のプロセッサからの確認要求を受けることなく、キャッシュ装置自身で投機データの本当の有効性を確認して記憶し、プロセッサから投機データの有効性の確認要求があったときには記憶結果を通知するようにしたことを特徴とする。
図１７において、プロセッサ１２から読出要求を受けたときのステップＳ１のキャッシュメモリ２０における要求データの所有の有無、ステップＳ２のデータの有効性によるステップＳ３の有効データの要求元への供給、またステップＳ２でキャッシュライン保持データの状態が無効Ｉ状態か、あるいはステップＳ４でプロセッサによる投機データを許可する読出要求でなかった場合のステップＳ９〜Ｓ１１の処理については、図１３のステップＳ１〜Ｓ３及びステップＳ６〜Ｓ８の処理と同じである。
これに対しステップＳ４でプロセッサからの読出要求が投機データを許可する読出要求であった場合には、図８（Ｃ）のウィークリードプロトコルに従って不明Ｕ状態にある保持データを投機データとして要求元のプロセッサに供給した後、ステップＳ６で主記憶や他のキャッシュ装置にアクセスし、ステップＳ７で投機データの本当の有効性を確認し、ステップＳ８で確認結果を記憶する。この場合の投機データの本当の有効性の確認処理も、具体的には図１５または図１６の投機データ有効性の確認処理フローチャートに従って行われる。
図１８は、図１７のステップＳ４〜Ｓ８で投機データを要求元に供給して投機データの本当の有効性の確認を行った後にプロセッサから投機データの有効性の確認要求を受けた場合のフローチャートである。この要求元のプロセッサからの投機データ有効性の確認要求を受けると、ステップＳ１でキャッシュ装置１０に既に記憶してある投機データの本当の有効性を示す確認結果を読み出し、ステップＳ２で本当の有効性が有効であれば、ステップＳ３で要求元に有効を通知し、投機データに基づく命令の実行結果を承認させる。また無効であれば、ステップＳ４で要求元のプロセッサ１２に投機データの無効を通知し、投機データに基づく命令の実行結果を破棄させる。
図１９は、図８のＭＥＳＩプロトコルによるキャッシュ管理制御の第３実施形態のフローチャートである。この第３実施形態にあっては、プロセッサの読出要求に対し、不明Ｕの状態にあるデータを投機データとして供給した場合には、プロセッサからの投機データの有効性確認要求を待つことなく、キャッシュ装置自身で投機データの本当の有効性を確認して、結果を要求元のプロセッサに通知するようにしたことを特徴とする。このためプロセッサからの投機データの有効性確認要求は不要となり、プロセッサの負担を軽減する。
図１９において、ステップＳ１〜Ｓ４、及びステップＳ１１〜Ｓ１３の処理は、図１７の第２実施形態のステップＳ１〜Ｓ４、及びステップＳ９〜Ｓ１１と同じである。またステップＳ４でプロセッサからの投機データの提供を許可する読出要求を判別した場合のステップＳ５〜Ｓ７の処理も図１７の第２実施形態と同じであり、キャッシュ装置自身で投機データを要求元のプロセッサに供給した後、主記憶や他のキャッシュにアクセスして投機データの本当の有効性を確認する。続いてステップＳ８で投機データの本当の有効性が有効であれば、ステップＳ９で要求元のプロセッサに有効を通知し、これにより要求元のプロセッサは投機データに基づく命令の実行結果を承認する。また投機データの本当の有効性が無効であれば、ステップＳ１０で同じく要求元のプロセッサに無効を通知し、投機データに基づく命令の実行結果を破棄させる。
（ＭＥＳＵプロトコルとキャッシュ管理制御）
図２０は、図７の本発明のキャッシュ装置１０で使用されるキャッシュメモリ上に有効性の不明なデータの保存を可能とするキャッシュ管理制御を実現するＭＥＳＵプロトコルの状態遷移図である。このＭＥＳＵプロトコルは、図８のＭＥＳＩＵプロトコルから無効Ｉの状態を取り除いている。
図２０（Ａ）は、ＭＥＳＵリードプロトコル、図２０（Ｂ）はＭＥＳＵライトプロトコルである。この図２０（Ａ）（Ｂ）のＭＥＳＵリードプロトコル及びライトプロトコルによって、図１０の本発明による「弱い無効化操作（ウィークインバリディド）」を同様に実現することができる。
図２０（Ｃ）は、ＭＥＳＵウィークリードプロトコルであり、このＭＥＳＵウィークリードプロトコルによって、図１１に示した本発明の弱い読出操作（ウィークリード操作）と同じキャッシュ管理制御ができる。但し、ＭＥＳＵウィークリードプロトコルの場合、図１１（Ａ）のキャッシュ装置１０−２の状態が無効Ｉではなく不明Ｕとなる点が相違する。この点は図１２のＭＥＳＩＵウィークリードプロトコルの他の処理動作についても同様である。
図２１は、図２０のＭＥＳＵプロトコルの状態遷移表である。この状態遷移表を図９のＭＥＳＩＵプロトコルの状態遷移表と対比して明らかなように、現在の状態が変更Ｍ，排他Ｅ及び共有Ｓについては同じであり、図９の無効Ｉの状態が除かれ、不明Ｕ状態については次の状態が「ＳＥＬＦ」で「weak read」のときの（２）の「Ｅ，Ｕ」への遷移が相違するだけである。
図２２は、図２０のＭＥＳＵプロトコルを使用した図７のキャッシュ装置１０によるキャッシュ管理制御のフローチャートであり、本発明の第４実施形態となる。このＭＥＳＵプロトコルに従ったキャッシュ管理制御にあっては、プロセッサ１２から読出要求があると、ステップＳ１でキャッシュメモリ２０上にデータが保持されているか否かの要求データの所有の有無をチェックし、要求データが所有されていれば、ステップＳ２でデータの有効性をチェックし、状態がＭ，Ｓ，Ｅのいずれかであれば有効として、ステップＳ３に進み、有効データを要求元のプロセッサ１２に供給する。
ステップＳ２でデータの有効性が不明Ｕの状態であった場合には、ステップＳ４に進み、プロセッサが投機データの提供を許可した読出要求か否かチェックする。投機データの許可の読出要求であれば、ステップＳ５で投機データを要求元のプロセッサに供給する。ステップＳ５で投機データを要求元のプロセッサに供給した後、プロセッサから投機データの有効性確認要求を受けると、図２３のフローチャートの処理を行う。この投機データ有効性確認要求の処理は、図１４の第１実施形態の場合と同じである。
再び図２２を参照するに、ステップＳ１でキャッシュメモリ４０上に要求データを所有しない場合、あるいはステップＳ４でプロセッサが投機データの提供を禁止する読出要求であった場合には、ステップＳ６に進み、主記憶１６や他のキャッシュ装置にアクセスし、ステップＳ７で有効データを入手し、ステップＳ８で有効データを要求元に供給する。この図２２のＭＥＳＵプロトコルの本発明の第４実施形態となるキャッシュ管理制御は、図１３のＭＥＳＩＵプロトコルのステップＳ２のデータの有効性の判断結果のうちの無効Ｉの条件分岐を除いた処理である。
図２４は、図２０のＭＥＳＵプロトコルを使用した本発明のキャッシュ管理制御の第５実施形態のフローチャートであり、投機データを要求元のプロセッサに供給した後に、キャッシュ装置１２自身で投機データの有効性を確認して結果を記憶し、その後の要求元のプロセッサからの投機データ有効性の確認要求に対し、キャッシュ装置に記憶している確認結果に基づいて投機データの本当の有効、無効を通知するようにしたことを特徴とする。この図２４の第５実施形態は、図１７のＭＥＳＩＵプロトコルのキャッシュ管理制御の第２実施形態のステップＳ２における無効Ｉの分岐処理を除いたと同じ処理であり、またステップＳ５〜Ｓ８で投機データを供給した後の投機データの本当の有効性の確認結果の記憶は、図１８と同様、要求元のプロセッサからの投機データ有効性の確認要求に対し、記憶した確認結果に基づいた有効または無効の通知を行う。
図２５は、図２０のＭＥＳＵプロトコルを使用した本発明のキャッシュ管理制御の第６実施形態のフローチャートであり、投機データを要求元のプロセッサに供給した後、投機データの本当の有効性の確認と確認結果の要求元への通知をキャッシュ装置自身で行うようにしたことを特徴とする。この図２５の処理は、図１９のＭＥＳＩＵプロトコルにおけるキャッシュ管理制御の第３実施形態のステップＳ２における無効Ｉの分岐処理を除いたと同じ処理になる。
尚、上記の実施形態における本発明の「弱い無効化操作（ウィークインバリディド）」及び「弱い読出操作（ウィークリード）」については、説明を簡単にするため２台のキャッシュ装置を例にとっているが、図６に示したように、システムバス１４で接続されたｎ台の任意の数のキャッシュ装置１０−１〜１０−ｎ間で全く同様に、図８のＭＥＳＩＵプロトコルあるいは図２０のＭＥＳＵプロトコルに従ったキャッシュ管理制御が行われる。
また上記の実施形態での「弱い読出操作（ウィークリード）」は、プロセッサから投機データの提供を許可するウィークリード要求が行われたときに図８（Ｃ）又は図２０（Ｃ）のウィークリードプロトコルに切替えて処理しているが、キャッシュコントローラの立ち上げ時に、図８（Ｃ）又は図２０（Ｃ）のウィークリードプロトコルを固定設定してもよい。この点は、「弱い無効化操作（ウィークインバリディド）」についても同じであり、キャッシュコントローラの立ち上げ時に、図８（Ａ）又は図２０（Ａ）のリードプロトコルを固定設定してもよい。餅録、いずれの場合もライトプロトコルは図８（Ｂ）又は図２０（Ｂ）である。
更に、本発明は上記の実施形態に限定されず、本発明の目的と利点を損なわない適宜の変形を含む。
【産業上の利用の可能性】
本発明のキャッシュ装置及びキャッシュ制御方法は、キャッシュ上に有効性の不明なデータを保持することができることにより、プロセッサに投機的にデータを供給することが可能となり、プロセッサが投機的に命令を実行する機会が増える。これにより、プロセッサからの読出要求でキャッシュミスとなり、主記憶もしくは他のキャッシュメモリからのデータを待つ必要のあったケースの一部で、キャッシュヒットにより投機的に命令実行を進行させることが可能となる。このため本発明は、読出要求を行ったプロセッサのデータ待ち時間を短くすることに貢献し、その結果としてマルチプロセッサシステムの性能を向上できる。
Claims (34)
- 複数のプロセッサ毎に設けられ、相互にバス接続されると共に主記憶とバス接続されたキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効、無効、及び不明の３種類の状態で区別するキャッシュメモリと、
自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを、有効、無効、又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラと、
を備えたことを特徴とするキャッシュ装置。 - 複数のプロセッサ毎に設けられ、相互にバス接続されると共に主記憶とバス接続されたキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効及び不明の２種類の状態で区別するキャッシュメモリと、
自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理すると共に、処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させるキャッシュコントローラと、
を備えたことを特徴とするキャッシュ装置。 - 請求の範囲１又は２のキャッシュ装置に於いて、前記キャッシュコントローラは、有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した際に、投機データの要求元への提供許可か提供禁止かを判定し、提供許可を判定した場合は、前記有効性の不明なデータを投機データとして要求元に提供し、提供禁止を判定した場合は、他のキャッシュ装置又は主記憶から有効データを入手して要求元に提供することを特徴とするキャッシュ装置。
- 請求の範囲３のキャッシュ装置に於いて、前記キャッシュコントローラは、前記投機データを要求元に提供した後、前記要求元から前記投機データの有効性確認要求が発生した際に、前記投機データの本当の有効性を確認して確認の結果を要求元に通知するキャッシュ装置。
- 請求の範囲３のキャッシュ装置で、前記キャッシュコントローラは、前記投機データを要求元に提供すると同時に、前記投機データの本当の有効性を確認して確認の結果を記憶し、前記要求元から前記投機データの有効性確認要求が発生した際に、記憶しておいた有効性の確認結果を要求元に通知することを特徴とするキャッシュ装置。
- 請求の範囲３のキャッシュ装置に於いて、前記キャッシュコントローラは、前記投機データを要求元に提供すると同時に、前記投機データの本当の有効性を確認し、確認結果を要求元に通知することを特徴とするキャッシュ装置。
- 請求の範囲３のキャッシュ装置に於いて、前記キャッシュコントローラは、前記確認結果から前記投機データが有効であった場合、前記要求元に確認結果を通知して前記投機データに基づく命令の実行結果を承認させ、前記投機データが無効であった場合、前記要求元に確認結果を通知して前記投機データに基づく命令の実行結果を破棄させることを特徴とするキャッシュ装置。
- 請求の範囲３のキャッシュ装置に於いて、前記キャッシュコントローラは、前記主記憶の予め定めた特定アドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を禁止し、前記主記憶の特定アドレス以外のアドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を許可することを特徴とするキャッシュ装置。
- 請求の範囲３のキャッシュ装置に於いて、前記キャッシャコントローラは、前記プロセッサの投機データを禁止する命令の実行で生成した読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を禁止し、前記プロセッサの投機データを許容する命令の実行で生成した読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を許可することを特徴とするキャッシュ装置。
- 請求の範囲１のキャッシュ装置に於いて、前記キュッシュコントローラは、前記キャッシュラインの保持データの状態を、有効を表す変更、排他及び共有と無効の４状態で区別するキャッシュコヒーレンスのためのＭＥＳＩプロトコルに、データの有効性が不明であることを示す状態を加えた５状態で区別するＭＥＳＩＵプロトコルを備えたことを特徴とするキャッシュ装置。
- 請求の範囲１０のキャッシュ装置に於いて、前記キャッシュコントローラは、前記ＭＥＳＩＵプロトコルに基づき、
（Ａ）キャッシュラインの保持データに対するリード要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他キャッシュ装置が該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置で読出要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに遷移し、他のキャッシュ装置が該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移し、
（Ｂ）キャッシュラインの保持データに対するライト要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの書込要であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する、
状態制御を行うことを特徴とするキャッシュ装置。 - 請求の範囲１１のキャッシュ装置に於いて、前記キャッシュコントローラは、前記プロセッサから不明の状態で保持した投機データの提供を許可するウィークリード要求を処理した場合、ウィークリードのＭＥＳＩＵプロトコルに基づき、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当ラインを保持している場合は不明Ｕに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する、
状態制御を行うことを特徴とするキャッシュ装置。 - 請求の範囲１２のキャッシュ装置に於いて、前記キャッシュコントローラは、前記ウィークリードＭＥＳＩＵプロトコルのキャッシュ管理制御を固定設定したことを特徴とするキャッシュ装置。
- 請求の範囲２のキャッシュ装置に於いて、前記キュッシュコントローラは、前記キャッシュラインの保持データの状態を、有効を示す変更、排他及び共有の３状態で区別するキャッシュコヒーレンスのためのＭＥＳプロトコルに、データの有効性が不明であることを示す状態を加えた４状態で区別するＭＥＳＵプロトコルを備えたことを特徴とするキャッシュ装置。
- 請求の範囲１４のキャッシュ装置に於いて、前記キャッシュコントローラは、前記ＭＥＳＵプロトコルに基づき、
（Ａ）キャッシュラインの保持データに対するリード要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼不明Ｕの状態で、自己のプロセッサの読出要より他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当ラインを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移し、
（Ｂ）キャッシュラインの保持データに対するライト要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移し、
▲４▼不明Ｕで、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する、
繊維制御を行うことを特徴とするキャッシュ装置。 - 請求の範囲１５のキャッシュ装置に於いて、前記キャッシュコントローラは、前記プロセッサから不明Ｕ状態で保持した投機データの提供を許可するウィークリード要求を処理した場合は、ウィークリードのＭＥＳＵプロトコルに基づき、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当ラインを保持している場合又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する、
状態制御を行うことを特徴とするキャッシュ制御装置。 - 請求の範囲１６のキャッシュ装置に於いて、前記キャッシュコントローラは、前記ウィークリードＭＥＳＵプロトコルのキャッシュ管理制御を固定設定したことを特徴とするキャッシュ装置。
- 複数のプロセッサ毎に設けたキャッシュ装置を相互にバス接続すると共に主記憶とバス接続したキャッシュ制御方法に於いて、
主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効、無効、及び不明の３種類の状態で区別し、
自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効、無効、又は不明の状態に応じて処理し、
前記要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するめに定めた所定の状態に遷移させる、
を特徴とするキャッシュ制御方法。 - 複数のプロセッサ毎に設けたキャッシュ装置を相互にバス接続すると共に主記憶とバス接続したキャッシュ制御方法に於いて、
主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保持すると共に前記キャッシュラインに保持したデータの状態を有効及び不明の２種類の状態で区別し、
自己のプロセッサ又は他のキャッシュ装置から処理要求を受けた際に、該当するキャッシュラインに保持しているデータを有効又は不明の状態に応じて処理し、
前記要求の処理後に該当するキャッシュラインの保持データの状態をキャッシュコヒーレンスを確保するために定めた所定の状態に遷移させる、
を特徴とするキャッシュ制御方法。 - 請求の範囲１８又は１９のキャッシュ制御方法に於いて、有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した際に、投機データの要求元への提供許可か提供禁止かを判定し、提供許可を判定した場合は、前記有効性の不明なデータを投機データとして要求元に提供し、提供禁止を判定した場合は、他のキャッシュ装置又は主記憶から有効データを入手して要求元に提供することを特徴とするキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法に於いて、前記投機データを要求元に提供した後、前記要求元から前記投機データの有効性の確認要求が発生した際に、前記投機データの本当の有効性を確認して確認の結果を要求元に通知するキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法で、前記投機データを要求元に提供すると同時に、前記投機データの本当の有効性を確認して確認の結果を記憶し、前記要求元から前記投機データの有効性確認要求が発生した際に、記憶しておいた有効性の確認結果を要求元に通知することを特徴とするキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法に於いて、前記投機データを要求元に提供すると同時に、前記投機データの本当の有効性を確認し、確認結果を要求元に通知することを特徴とするキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法に於いて、前記確認結果から前記投機データが有効であった場合、前記要求元に確認結果を通知して前記投機データに基づく命令の実行結果を承認させ、前記投機データが無効であった場合、前記要求元に確認結果を通知して前記投機データに基づく命令の実行結果を破棄させることを特徴とするキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法に於いて、前記主記憶の予め定めた特定アドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を禁止し、前記主記憶の特定アドレス意外のアドレスをもつ有効性の不明なデータを保持しているキャッシュラインへの読出要求が発生した時は、投機データとしての要求元への提供を許可することを特徴とするキャッシュ制御方法。
- 請求の範囲２０のキャッシュ制御方法に於いて、前記プロセッサの投機データを禁止する命令の実行で生成した読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を禁止し、前記プロセッサの投機データを許容する命令の実行で生成した読出要求を、有効性の不明なデータの保持しているキャッシュラインに受けた時は、投機データとしての要求元への提供を許可することを特徴とするキャッシュ制御方法。
- 請求の範囲１８のキャッシュ制御方法に於いて、前記キャッシュラインの保持データの状態を、友好を示す変更、排他及び共有と無効の４状態で区別するキャッシュコヒーレンスのためのＭＥＳＩプロトコルに、データの有効性が不明であることを示す状態を加えた５状態で区別するＭＥＳＩＵプロトコルに基づき制御することを特徴とするキャッシュ制御方法。
- 請求の範囲２７のキャッシュ制御方法に於いて、前記ＭＥＳＩＵプロトコルに基づく制御は、
（Ａ）キャッシュラインの保持データに対するリード要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当データを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当データを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置で読出要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求により主記憶からデータをコピーした場合は排他Ｅに状態遷移し、他のキャッシュ装置からコピーした場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移し、
（Ｂ）キャッシュラインの保持データに対するライト要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する、
ことを特徴とするキャッシュ制御方法。 - 請求の範囲２８のキャッシュ制御方法に於いて、キャッシュラインに不明状態で保持した投機データの提供を許可する前記プロセッサからのウィークリード要求を処理した場合、ウィークリードＭＥＳＩＵプロトコルに基づく制御として、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼無効Ｉの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当データを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当データを保持している場合は不明Ｕに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ無効Ｉに状態遷移し、
▲５▼不明Ｕの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する、
ことを特徴とするキャッシュ制御方法。 - 請求の範囲２９のキャッシュ制御方法に於いて、前記ウィークリードＭＥＳＩＵプロトコルのキャッシュ管理制御を固定設定したことを特徴とするキャッシュ制御方法。
- 請求の範囲１９のキャッシュ制御方法に於いて、前記キャッシュラインの保持データの状態を友好を示す変更、排他及び共有の３状態で区別するキャッシュコヒーレンスのためのＭＥＳプロトコルに、データの有効性が不明であることを示す状態を加えた４状態で区別するＭＥＳＵプロトコルに基づいて制御することを特徴とするキャッシュ制御方法。
- 請求の範囲３１のキャッシュ制御方法に於いて、前記ＭＥＳＵプロトコルに基づく制御として、
（Ａ）キャッシュラインの保持データに対するリード要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求であれば同じ排他Ｅに状態遷移し、他のキャッシュ装置からの読出要求であれば共有Ｓに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当データを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当データを保持している場合は共有Ｓに状態遷移し、更に他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移し、
（Ｂ）キャッシュラインの保持データに対するライト要求を処理した場合、
▲１▼変更Ｍの状態で、自己のプロセッサの書込要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば不明Ｕに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移し、
▲４▼不明Ｕで、自己のプロセッサの書込要求であれば変更Ｍに状態遷移し、他のキャッシュ装置での書込要求であれば同じ不明Ｕに状態遷移する、
ことを特徴とするキャッシュ制御方法。 - 請求の範囲３１のキャッシュ制御方法に於いて、キャッシュラインに不明状態で保持した投機データの提供を許可する前記プロセッサからのウィークリード要求を処理した場合、ウィークリードＭＥＳＵプロトコルに基づく制御として、▲１▼変更Ｍの状態で、自己のプロセッサの読出要求であれば同じ変更Ｍに状態遷移し、他のキャッシュ装置からの読出要求であれば排他Ｅに状態遷移し、
▲２▼排他Ｅの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ排他Ｅに状態遷移し、
▲３▼共有Ｓの状態で、自己のプロセッサの読出要求又は他のキャッシュ装置からの読出要求であれば同じ共有Ｓに状態遷移し、
▲４▼不明Ｕの状態で、自己のプロセッサの読出要求により他キャッシュ装置が該当ラインを保持していない場合は排他Ｅに状態遷移し、他のキャッシュ装置が該当ラインを保持している場合又は他のキャッシュ装置の読出要求であれば同じ不明Ｕに状態遷移する、
ことを特徴とするキャッシュ制御方法。 - 請求の範囲３３のキャッシュ制御方法に於いて、前記ウィークリードＭＥＳＵプロトコルのキャッシュ管理制御を固定設定したことを特徴とするキャッシュ制御方法。
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| PCT/JP1998/005588 WO2000034882A1 (fr) | 1998-12-10 | 1998-12-10 | Antememoire et procede de commande |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP3550092B2 true JP3550092B2 (ja) | 2004-08-04 |
Family
ID=14209582
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000587273A Expired - Fee Related JP3550092B2 (ja) | 1998-12-10 | 1998-12-10 | キャッシュ装置及び制御方法 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US6526480B1 (ja) |
| JP (1) | JP3550092B2 (ja) |
| WO (1) | WO2000034882A1 (ja) |
Families Citing this family (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2000038077A1 (fr) * | 1998-12-18 | 2000-06-29 | Fujitsu Limited | Antememoire et procede de commande |
| US6742086B1 (en) * | 2000-08-11 | 2004-05-25 | Unisys Corporation | Affinity checking process for multiple processor, multiple bus optimization of throughput |
| SE0102564D0 (sv) | 2001-07-19 | 2001-07-19 | Ericsson Telefon Ab L M | Arrangement and method in computor system |
| WO2003107176A2 (en) * | 2002-06-13 | 2003-12-24 | Koninklijke Philips Electronics N.V. | Load speculation method |
| 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 |
| JP4673585B2 (ja) | 2004-08-05 | 2011-04-20 | 富士通株式会社 | メモリシステム制御装置およびメモリシステム制御方法 |
| CN106293637B (zh) * | 2015-05-28 | 2018-10-30 | 华为技术有限公司 | 数据移动、将数据设置为无效的方法、处理器及系统 |
| CN107506329B (zh) * | 2017-08-18 | 2018-06-19 | 浙江大学 | 一种自动支持循环迭代流水线的粗粒度可重构阵列及其配置方法 |
| US10866893B2 (en) * | 2018-01-23 | 2020-12-15 | Home Depot Product Authority, Llc | Cache coherency engine |
| US20220113901A1 (en) * | 2020-10-12 | 2022-04-14 | Qualcomm Incorporated | Read optional and write optional commands |
| US11947456B2 (en) | 2021-09-30 | 2024-04-02 | Advanced Micro Devices, Inc. | Weak cache line invalidation requests for speculatively executing instructions |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5025365A (en) * | 1988-11-14 | 1991-06-18 | Unisys Corporation | Hardware implemented cache coherency protocol with duplicated distributed directories for high-performance multiprocessors |
| US5623632A (en) * | 1995-05-17 | 1997-04-22 | International Business Machines Corporation | System and method for improving multilevel cache performance in a multiprocessing system |
| JPH0950400A (ja) * | 1995-08-10 | 1997-02-18 | Nec Corp | マルチプロセッサシステム |
| US6374330B1 (en) * | 1997-04-14 | 2002-04-16 | International Business Machines Corporation | Cache-coherency protocol with upstream undefined state |
-
1998
- 1998-12-10 JP JP2000587273A patent/JP3550092B2/ja not_active Expired - Fee Related
- 1998-12-10 US US09/646,704 patent/US6526480B1/en not_active Expired - Fee Related
- 1998-12-10 WO PCT/JP1998/005588 patent/WO2000034882A1/ja active Application Filing
Also Published As
| Publication number | Publication date |
|---|---|
| WO2000034882A1 (fr) | 2000-06-15 |
| US6526480B1 (en) | 2003-02-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108885583B (zh) | 高速缓存存储器访问 | |
| KR101639672B1 (ko) | 무한 트랜잭션 메모리 시스템 및 그 동작 방법 | |
| KR100194253B1 (ko) | 메시 데이터 코히어런시 프로토콜 이용 방법 및 멀티프로세서 시스템 | |
| US6636949B2 (en) | System for handling coherence protocol races in a scalable shared memory system based on chip multiprocessing | |
| US7549025B2 (en) | Efficient marking of shared cache lines | |
| TWI432963B (zh) | 加速器之低成本快取一致 | |
| TW591384B (en) | Method and system for speculatively invalidating lines in a cache | |
| US7657710B2 (en) | Cache coherence protocol with write-only permission | |
| JP4474570B2 (ja) | キャッシュコヒーレンシ制御方法 | |
| US8799589B2 (en) | Forward progress mechanism for stores in the presence of load contention in a system favoring loads | |
| JP4119380B2 (ja) | マルチプロセッサシステム | |
| US20080046651A1 (en) | Victim Cache Using Direct Intervention | |
| US20020083274A1 (en) | Scalable multiprocessor system and cache coherence method incorporating invalid-to-dirty requests | |
| JP2004348734A (ja) | 非対称型異種マルチプロセッサ環境でアトミック更新プリミティブを提供するための方法 | |
| JP2007199999A (ja) | マルチプロセッサシステム及びその動作方法 | |
| US20060184743A1 (en) | Cache memory direct intervention | |
| US5263144A (en) | Method and apparatus for sharing data between processors in a computer system | |
| JP3550092B2 (ja) | キャッシュ装置及び制御方法 | |
| WO1999035578A1 (en) | Method for increasing efficiency in a multi-processor system and multi-processor system with increased efficiency | |
| US8296520B2 (en) | System and method for optimizing neighboring cache usage in a multiprocessor environment | |
| US10949292B1 (en) | Memory interface having data signal path and tag signal path | |
| US7912998B2 (en) | DMA access systems and methods | |
| JP3757117B2 (ja) | キャッシュ装置及び制御方法 | |
| US8397029B2 (en) | System and method for cache coherency in a multiprocessor system | |
| JP4577729B2 (ja) | ライトバックキャッシュにおいてスヌーププッシュ処理やスヌープキル処理が同時発生しているときのライトバック処理をキャンセルするためのシステムおよび方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20040330 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20040422 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080430 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090430 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090430 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100430 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110430 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110430 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120430 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130430 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140430 Year of fee payment: 10 |
|
| LAPS | Cancellation because of no payment of annual fees |