(57)【特許請求の範囲】
【請求項１】
複数のプロセッサ毎に設けられ、相互に共通結合網で結合されると共に主記憶と結合されたキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定したキャッシュメモリと、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合は、前記プリフェッチ要求を失敗させる弱い読出操作をフェッチプロトコルとして実行するキャッシュコントローラと、
を備えたことを特徴とするキャッシュ装置。
【請求項２】
請求の範囲１のキャッシュ装置に於いて、
前記キャッシュメモリは、保存データの状態タグとして有効を示す変更状態Ｍ、排他状態Ｅ及び共有状態Ｓと無効状態Ｉの４状態で区別し、
前記キャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが変更状態Ｍ又は排他状態Ｅのとき、前記プリフェッチ要求を失敗させることを特徴とするキャッシュ装置。
【請求項３】
請求の範囲１のキャッシュ装置に於いて、前記キャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが、無効状態Ｉのときは、前記主記憶から読み出して排他状態Ｅでキャッシュメモリに保存し、共有状態Ｓのときは、他のキャッシュ装置から読み出して共有状態Ｓでキャッシュメモリに保存することを特徴とするキャッシュ装置。
【請求項４】
複数のプロセッサ毎に設けられ、相互に共通結合網で結合されると共に主記憶と結合されたキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定したキャッシュメモリと、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合、状態タグを変更することなくデータを読み出して弱い状態Ｗを設定してキャッシュメモリに保存し、ソフトウェアによりデータの一貫性をとるメモリコンシステンシの同期操作時に、前記弱い読出状態Ｗにあるキャッシュメモリのデータを全て無効化するプリフェッチプロトコルを実行するキャッシュコントローラと、
を備えたことを特徴とするキャッシュ装置。
【請求項５】
請求の範囲４のキャッシュ装置に於いて、
前記キャッシュメモリは、保存データの状態タグとして有効を示す変更状態Ｍ、排他状態Ｅ及び共有状態Ｓと無効状態Ｉの４状態で区別し、
前記キャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが変更状態Ｍ又は排他状態Ｅのとき、状態タグを変更することなくデータを読み出して弱い読出状態Ｗを設定してキャッシャメモリに保存し、メモリコンシステンシの同期操作時に、弱い読出状態Ｗを全て無効状態Ｉに変更することを特徴とするキャッシュ装置。
【請求項６】
請求の範囲５のキャッシュ装置に於いて、前記キャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが、無効状態Ｉのときは、前記主記憶から読み出して排他状態Ｅでキャッシュメモリに保存し、共有状態Ｓのときは、他のキャッシュ装置から読み出して共有状態Ｓでキャッシュメモリに保存することを特徴とするキャッシュ装置。
【請求項７】
複数のプロセッサ毎に設けられ、相互に共通結合網で結合されると共に主記憶と結合されたキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定したキャッシュメモリと、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置又は主記憶からプリフェッチしたデータに消極的保存モードＰを設定して前記キャッシュメモリに保存し、他のキャッシュ装置からの読出要求に該当するデータが前記消極的保存モードＰを設定したプリフェッチデータの場合、該当データの保存を他のキャッシュ装置に通知せず、他の全てのキャッシュ装置が該当データを保存していない場合は前記プリフェッチデータを無効化し、他のキャッシュ装置に該当データが共有されている場合は、前記プリフェッチデータをそのまま保存するプリフェッチプロトコルを実行するキャッシュコントローラと、を備えたことを特徴とするキャッシュ装置。
【請求項８】
請求の範囲７のキャッシュ装置に於いて、
前記キャッシュメモリは、キャッシュラインの状態タグとして、有効を示す変更状態Ｍ、排他状態Ｅ及び共有状態Ｓと無効状態Ｉの４状態で区別し、 前記キャッシュコントローラは、他のキャッシュ装置からの読出要求に該当するデータが前記消極的保存モードＰを設定したプリフェッチデータの場合、他のキャッシュ装置の全てが無効状態Ｉか、いずれかが変更状態Ｍ又は排他状態Ｅのとき、消極保存Ｐモードで保存しているプリフェッチデータを無効状態Ｉに変更し、他のキャッシュ装置が共有状態Ｓのとき消極的保存Ｐモードで保存しているプリフェッチデータを状態をそのまま維持することを特徴とするキャッシュ装置。
【請求項９】
請求の範囲７のキャッシュ装置に於いて、前記キャッシャメモリに保存した消極的保存モードＰのプリフェッチデータ以外のデータについてはノーマル保存モードＮを設定し、消極的保存モードＰとノーマル保存モードＮのデータ保存をキャッシュライン毎に使い分けて共存させることを特徴とするキャッシュ装置。
【請求項１０】
請求の範囲１乃至９のキャッシュ装置に於いて、前記キャッシュコントローラは、前記プロセッサの読出要求を受けた際に、前記読出要求に続いて読出要求アドレスに隣接する１又は複数アドレスのプリフェッチ要求を実行することを特徴とするキャッシュ装置。
【請求項１１】
請求の範囲１乃至９のキャッシュ装置に於いて、前記キャッシュコントローラは、前記プロセッサの読出要求を受けた際に、前記読出要求に続いて読出要求アドレスに隣接する１又は複数アドレスのプリフェッチ要求を同時実行することを特徴とするキャッシュ装置。
【請求項１２】
請求の範囲１１のキャッシュ装置に於いて、前記共通結合網は、前記キャッシュコントローラが自己のプロセッサ又は他のキャッシュ装置から読出要求を受けた際に、該当するデータの保存状態を状態信号線に出力するスヌープバスであり、前記キャッシュコントローラで同時に実行される読出要求とプリフェッチ要求の各々に対応して読出要求専用の状態信号線と、プリフェッチ要求専用の状態信号線を設け、要求データのアドレスとプリフェッチ要求のアドレスに対する各キャッシュ装置の状態を同時に通知することを特徴とするキャッシュ装置。
【請求項１３】
請求の範囲１１のキャッシュ装置に於いて、前記読出要求とプリフェッチ要求の同時要求に対する応答として、応答ヘッダに前記読出要求の応答データとプリフェッチ要求の応答データを識別する識別ビットを設け、識別ビットを有効とするデータをまとめて転送することを特徴とするキャッシュ装置。
【請求項１４】
複数のプロセッサ毎に設けられたキャッシュ装置を相互に共通結合網で結合されると共に主記憶と結合したキャッシュシステムの制御方法に於いて、
主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共に、データの一貫性管理に使用する状態タグをキャッシャライン毎に設定し、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合は、前記プリフェッチ要求を失敗させる弱い読出操作をフェッチプロトコルとして実行することを特徴とするキャッシュシステムの制御方法。
【請求項１５】
複数のプロセッサ毎に設けられたキャッシュ装置を相互に共通結合網で結合されると共に主記憶と結合されたキャッシュシステムの制御方法に於いて、
主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共に、データの一貫性管理に使用する状態タグをキャッシャライン毎に設定し、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合、状態タグを変更することなくデータを読み出して前記プロセッサに応答した後に弱い読出状態Ｗを設定してキャッシュメモリに保存し、
ソフトウェアによりデータの一貫性をとるメモリコンシステンシの同期操作時に、前記弱い読出状態Ｗにあるキャッシュメモリのデータを全て無効化することを特徴とするキャッシュシステムの制御方法。
【請求項１６】
複数のプロセッサ毎に設けられたキャッシュ装置を相互に共通結合網で結合されると共に主記憶と結合されたキャッシュシステムの制御方法に於いて、
主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定したキャッシュメモリと、
プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置又は主記憶からプリフェッチしたデータに消極的保存モードＰを設定して前記キャッシュメモリに保存し、
他のキャッシュ装置からの読出要求に該当するデータが前記消極的保存モードＰを設定したプリフェッチデータの場合、該当データの保存を他のキャッシュ装置に通知せず、
他の全てのキャッシュ装置が該当データを保存していない場合は前記プリフェッチデータを無効化し、他のキャッシュ装置に該当データが共有されている場合は前記プリフェッチデータをそのまま保存することを特徴とするキャッシュシステムの制御方法。
【発明の詳細な説明】
【発明の属する技術分野】
【０００１】
本発明は、マルチプロセッサシステムでキャッシュメモリを管理するキャッシュ装置及び制御方法に関し、特に、キャッシュメモリにプリフェッチされたデータを適切に管理するキャッシュ装置及び制御方法に関する。
【従来の技術】
【０００２】
キャッシュ装置は、計算機のメモリアクセス時間を短縮するための有効な手段の一つである。プロセッサにキャッシュメモリと呼ばれる小容量で高速なメモリを付加し、一度アクセスしたデータを保存することによって次にアクセスした場合には高速にデータを返すことができる。
【０００３】
図１はマルチプロセッサシステムのキャッシュ機構であり、プロセッサ１０２−１，１０２−２，・・・１０２−ｎのそれぞれにキャッシュ装置１００−１，１００−２，・・・１００−ｎを設け、相互結合網１０６により主メモリ１０８と共に共通接続されている。
【０００４】
このキャッシュ装置が有効に働くためには、プロセッサが要求するデータがなるべくキャッシュの中に保存されている状態を保つことが望ましい。即ち、プロセッサが要求するデータがキャッシュの中にない場合が多ければ、それだけ多くの回数、低速なメインメモリをアクセスしなければならず、平均のメモリアクセス時間が低下する。特に、マルチプロセッサシステムでは、複数のプロセッサが同じメモリをアクセスするため、アクセスの競合が起こり、メインメモリのアクセス速度の平均はさらに低下する傾向をとる。そのため、プロセッサが要求するデータをキャッシュ装置に保持しておくことは、キャッシュ装置を用いた計算機システムにとって重要な課題である。
【０００５】
現在のキャッシュ装置は、メモリアクセスの時間的局所性と空間的局所性という性質を用いて、キャッシュ装置のヒット率を向上させている。時間的局所性とは、一度アクセスしたデータはまたすぐにアクセスされやすいというものであり、キャッシュ装置の中では一度アクセスされるとそのデータは追い出されにくくするＬＲＵなどの手法によって利用されている。
【０００６】
また空間的局所性は、一度アクセスされたデータの近傍データはアクセスされやすいというものである。このためキャッシュ装置は図２のキャッシュメモリ１１０のキャッシュライン１１１に示すように、アドレス１１２に続くキャッシュアレイ１１４に、アクセスしたブロックデータ１１６−１に続く３ブロック分、のブロックデータ１１６〜２〜１１６−４を含む４ブロック分のデータを格納し、キャッシュブロック単位で管理するなどの手法によって利用されている。
【０００７】
空間的局所性は、時間的局所性と異なり、プロセッサから実際には要求が出ていないデータでもキャッシュ装置の中に予め取り込むという方法を用いる。これをさらに進めると、近いうちにプロセッサが要求するであろうブロックを予めキャッシュに格納しておくという方法も可能になる。これがプリフェッチである。プリフェッチを利用することによって、さらにキャッシュ装置のヒット率が上がり、メモリのアクセス時間を短縮することが可能になる。
【０００８】
このプリフェッチは、単一のプロセッサシステムだけでなく、マルチプロセッサシステムにおいても有効な手法である。しかし、マルチプロセッサシステムでは、新たに無駄な共有という問題が生じる。
【０００９】
マルチプロセッサシステムにおけるキャッシュシステムでは、ひとつのプロセッサのキャッシュ装置と他のプロセッサとのキャッシュ装置との間で矛盾が生じないように、キャッシュ装置の一貫性（キャッシュコヒーレンス）の管理を行う。例えば、図３（Ａ）のように複数のキャッシュ装置１００−１〜１００−ｎが保持しているデータは共有状態  （Ｓｈａｒｅｄ）になっており、プロセッサ１００−ｎが共有状態のデータに対し書込みを行う場合は、図３（Ｂ）のように、他の同じデータを持っているキャッシュ装置１００−１，１００−２に通知して必ず無効状態（Ｉｎｖａｌｉｄ）にした後に行う。この無効化によって他のキャッシュ装置１００−１，１００−２は、自己のデータが最新の状態ではないことを知ることができる。このようにして、どのプロセッサでデータを読み出しても、その時点で最新のデータを読み出せるようにするのが一貫性管理である。
【００１０】
プリフェッチは、ひとつのキャッシュ装置が、プロセッサによって要求されたデータに加えて、近い将来要求されるであろうデータを予測して読み出す。しかし、この予測は必ずしも当るわけではないので、無駄にデータを読み出してしまう可能性がある。単一のプロセッサシステムの場合でも、プリフェッチによる無駄な読出しはメインメモリとキャッシュの間の無駄なトラフィックとして問題になるが、マルチプロセッサシステムシステムでは、それに加えて、無駄な共有状態が発生する。即ち、要求されたデータのみを読み出す方式では共有しなかったデータも、プリフェッチを用いた方式では複数のキャッシュ間で共有にされてしまうことがある。
【発明が解決しようとする課題】
【００１１】
共有状態になったデータに対しては、書込み時に他のキャッシュ装置に通知するという処理が必要になる。この他のキャッシュ装置に通知する処理を終了しない限りデータを更新することができないため、共有されたデータに対する書込みは、キャッシュ装置にとって処理に時間のかかる重い処理になる。そのため、マルチプロセッサシステムのプリフェッチは、プリフェッチによる利点と無駄なトラフィック及び無駄な共有による欠点とが相殺し合い、性能的に優れたものとはなりにくかった。
【００１２】
このように従来のキャッシュ装置では、キャッシュのヒット率を向上させるプリフェッチは、同時に、無駄な共有による書込み時のオーバーヘッドの増加やプリフェッチによるデータ転送の増加を招き、マルチプロセッサシステムには応用しにくいという問題がある。
【００１３】
本発明に従えば、マルチプロセッサシステムのキャッシュ装置でのプリフェッチを有効に利用し、オーバーヘッドやデータ転送の増加を招くことなくキャッシュヒット率を向上させるキャッシュメモリ装置及び制御方法が提供される。
【課題を解決するための手段】
【００１４】
（第１ウィークリード）
本発明は、プロセッサ毎に設けられ、相互に共通結合網で結合されると共に主記憶と結合されたキャッシュ装置であり、キャッシュメモリとキャッシュコントローラを備える。キャッシュメモリは、主記憶の一部のデータをキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定する。キャッシュコントローラは、プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合は、プリフェッチ要求を失敗させる弱い読出操作（第１ウィークリード操作）をフェッチプロトコルとして実行する。
【００１５】
通常のキャッシュ装置では、読出要求が発生するとデータを必ず読み出されなければならず、そのため、他のキャッシュの状態を変化させた後に読み出すという一貫性管理のための重い処理を必要とする。しかし、本発明のキャッシュ装置はプリフェッチプロトコルを備えることで、プリフェッチは、後に使われない可能性もある一種の投機的なメモリアクセスであるので、読出しを必ず成功させる必要がなく、そのため、他のキャッシュの状態を変更するような場合には読出失敗とするプロトコルとし、失敗する可能性がある弱い読出操作を実現する。このプリフェッチプロトコルによって、他のキャッシュ装置の状態変更を起こすプリフェッチを排除し、プリフェッチの読出要求および当該データに対する書込み処理に伴うオーバーヘッドを減らす。
【００１６】
ここでキャッシュメモリは、保存データの状態タグとして有効を示す変更状態Ｍ、排他状態Ｅ及び共有状態Ｓと、無効状態Ｉの４状態（ＭＥＳＩプロコトル）で区別する。キャッシュコントローラは、プロセッサの読出要求に伴って発生した他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが変更状態Ｍ又は排他状態Ｅのとき、このプリフェッチ要求をプリフェッチプロトコルに基づき失敗させる。このようなプリフェッチプロトコルを用いることによって、排他状態Ｅまたは変更状態Ｍにあるキャッシュ装置の状態変更を起こすことを防ぐことができ、排他状態Ｅまたは変更状態Ｍでデータを保持しているキャッシュ装置からプリフェッチに伴うオーバーヘッドを削減することができる。
【００１７】
またキャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが、無効状態Ｉのときは主記憶から読み出して排他状態Ｅでキャッシュメモリに保存し、共有状態Ｓのときは他のキャッシュ装置から読み出して共有状態Ｓでキャッシュメモリに保存する。この場合は、通常のＭＥＳＩプロトコルによる処理である。
【００１８】
（第２ウィークリード）
本発明の別の形態のキャッシュ装置において、キャッシュコントローラは、プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合、状態タグを変更することなくデータを読み出してプロセッサに応答した後に、弱い状態（ウィーク状態）Ｗを設定してキャッシュメモリに保存する。その後、ソフトウェアによりデータの一貫性をとるメモリコンシステンシの同期操作時に、弱い状態Ｗにあるキャッシュメモリのデータを全て無効化するプリフェッチプロトコルを実行する。この弱い状態でプリフェッチデータを保存する読出操作を第２ウィークリードという。
【００１９】
この第２ウィークリードは、ソフトウェアによって弱い一貫性を保つ同期操作を伴うメモリコンシステンシモデルのもつ同期と同期の間のメモリ操作の順序は任意であるという性質を利用したものである。このメモリコンシステンシモデルを利用して他のキャッシュ装置の状態変更を必要とするプリフェッチデータの読出しを行う場合、第１ウィークリードでは失敗としていたものを、第２ウィークリードではテータを読み出してプリフェッチを正常終了させる。後に、同期ポイントに達し、同期メッセージが各キャッシュ装置に配られると、各キャッシュ装置は弱い状態Ｗのデータを検索し、全てを無効化する。これによって、同期点を越えた順序の入れ替えを防ぎ、メモリコンシステンシモデルの要請を満たす。
【００２０】
ここでＭＥＳＩプロトコルを例にとると、キャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが変更状態Ｍ又は排他状態Ｅのとき、状態タグを変更することなくデータを読み出して弱い状態Ｗを設定してキャッシャメモリに保存し、メモリコンシステンシの同期操作時に、弱い状態Ｗを全て無効状態Ｉに変更する。
【００２１】
このため弱い状態Ｗでプリフェッチした後に、他のキャッシュ装置が排他状態Ｅまたは変更状態Ｍでもっているデータをプロセッサが更新しても、その更新は弱い状態Ｗのキャシュ装置には通知されない。しかし、これは弱い状態Ｗでデータを保存しているキャッシュ装置と、排他状態Ｅ又は変更状態Ｍでデータを保存しているキャッシュ装置において、データの更新順序が入れ替わったと認識することができ、メモリコンシステンシモデルを満たしている。そして、後に、同期ポイントに達し、同期メッセージが各キャッシュ装置に配られると、各キャッシュ装置は弱い状態Ｗのデータを検索して全て無効化する。これによって、同期点を越えたデータ更新の順序の入れ替えを防ぎ、メモリコンシステンシモデルの要請を満たすようにしている。
【００２２】
またキャッシュコントローラは、他のキャッシュ装置に保存しているプリフェッチ要求に該当するデータが、無効状態Ｉのときは主記憶から読み出して排他状態Ｅでキャッシュメモリに保存し、共有状態Ｓのときは他のキャッシュ装置から読み出して共有状態Ｓでキャッシュメモリに保存する。この場合、ＭＥＳＩプロトコルに従う。
【００２３】
（消極的保存モード）
本発明の別の形態のキャッシュ装置において、キャッシュコントローラは、プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置又は主記憶からプリフェッチしたデータに消極的保存モードＰを設定してキャッシュメモリに保存し、 １．他のキャッシュ装置からの読出要求に該当するデータが消極的保存モードＰを設定したプリフェッチデータの場合は、該当データの保存を他のキャッシュ装置に通知せず、
２．他の全てのキャッシュ装置が該当データを保存していない場合は、プリフェッチデータを無効化し、更に、
３．他のキャッシュ装置に該当データが共有されている場合は、プリフェッチデータをそのまま保存する。
【００２４】
第１及び第２ウィークリードは、プリフェッチ要求の際に他のキャッシュ装置に対し読出要求を行った場合の操作であるが、マルチプロセッサシステムのキャッシュ装置では、逆に、キャッシュメモリに保存しているプリフェッチデータに対し、他のキャッシュ装置からの読出しによる状態変更が起こり得る。そこで、主記憶又は他のキャッシュ装置から読み出してきたプリフェッチデータについては、他のキャッシュ装置に優先度を持たせる消極的な保存であることを示す印として消極的保存モードＰを設定し、他のキャッシュ装置の読出要求を認識しても、データはもっていないことにし、プリフェッチデータの他のキャッシュ装置によるアクセスを禁止する。このため、実際に使われる可能性が低いが念のために保存しているプリフェッチデータについて、状態変更による無駄な共有状態への遷移を削減し、キャッシュ装置に読み出したデータ書込みの際のオーバーヘッドを低減する。
【００２５】
この消極的な保存方法と弱い読出しとが重なった場合には、消極的な保存方法で保存されたデータを排他的Ｅであると見なさないことによって共存することが可能である。消極的な保存方法でデータを保存しているキャッシュ装置は、自分が排他状態Ｅであろうとそうでなかろうと、データを持っていないことにして他のキャッシュ装置の状態通知を待つので、無駄な共有状態への遷移を回避できる。
【００２６】
キャッシュ装置が例えばＭＥＳＩプロトコルを備えた場合、キャッシュコントローラは、他のキャッシュ装置からの読出要求に該当するデータが消極的保存モードＰを設定したプリフェッチデータの場合、他のキャッシュ装置の全てが無効状態Ｉか、いずれかが変更状態Ｍ又は排他状態Ｅのとき、消極保存モードＰで保存しているプリフェッチデータを無効状態Ｉに変更してデータを持っていないことにし、他のキャッシュ装置が共有状態Ｓのときは消極的保存モードＰで保存しているプリフェッチデータを状態をそのまま維持する。
【００２７】
キャッシャメモリに保存した消極的保存モードＰのプリフェッチデータ以外のデータについてはノーマル保存モードＮを設定し、消極的保存モードＰとノーマル保存モードＮのデータ保存をキャッシュライン毎に使い分けて共存させる。
【００２８】
本発明のプリフェッチプロトコルは、通常のデータに対しては適用しにくい。即ち、通常のデータ読出要求は、実際にプロセッサがデータが必要になったために生じるものであり、データ読出しに失敗してデータが取得できないことは、そのままプロセッサの演算性能の低下につながるからである。したがって、本発明の第１ウィークリード、第２ウィークリード及び消極的保存モードＰはプリフェッチなどの一種の投機的データ読出しに対してのみ適用する。即ち、通常の保存データはノーマル保存モードＮの設定でキャッシュ装置に保存し、消極的な保存データであるプリフェッチデータは、消極的保存モードＰの設定で保存し、キャッシュメモリ上で区別する。これによってキャッシュライン毎に保存方法を使い分けたキャッシュ装置を構成できる。
【００２９】
キャッシュコントローラは、プロセッサの読出要求を受けた際に、読出要求に続いて読出要求アドレスＡＤＲに隣接する１又は複数アドレスＡＤ＋ｎ又はＡＤ＋ｎのプリフェッチ要求を実行する。プロセッサから読出要求に付随するプリフェッチ要求は、通常は、別々の命令サイクルで各キャッシュ装置に出される。しかし、本発明においては、通常の読出要求の中にプリフェッチ要求を埋め込む。例えば、隣接ブロックのプリフェッチを採用している場合、アドレスＡＤＲに対する読出要求がキャッシュ装置に出されると、その要求はそのまま隣接ブロックＡＤＲ＋１の読出要求としても扱われる。このため、プロセッサは、プリフェッチのために別途のアドレスＡＤＲ＋ｎの読出し要求を発生する必要なくプリフェッチデータを取得できる。
【００３０】
勿論、この時のプリフェッチの要求は第１ウィークリード、第２ウィークリード、消極的保存モードのいずれか又はその組合せを用いて行われる。即ち、異なるアドレスに対する異なるプロトコルの要求を、１つのリクエストにまとめてしまうのである。このようにキャッシュ装置に対するリクエストをまとめてしまうことによって、余分なリクエストによるオーバーヘッドを削減する。
【００３１】
キャッシュ装置のキャッシュコントローラは、プロセッサの読出要求を受けた際に、読出要求に続いて読出要求アドレスに隣接する１又は複数アドレスのプリフェッチ要求を同時実行する。具体的には、キャッシュ装置及び主記憶を結合する共通結合網として、キャッシュコントローラが自己のプロセッサ又は他のキャッシュ装置から読出要求を受けた際に、該当するデータの保存状態を状態信号線に出力するスヌープバスを使用し、キャッシュコントローラで同時に実行される読出要求とプリフェッチ要求の各々に対応して読出要求専用の状態信号線と、プリフェッチ要求専用の状態信号線を設け、要求データのアドレスとプリフェッチ要求のアドレスに対する各キャッシュ装置の状態を同時に通知する。
【００３２】
マルチプロセッサシステムのキャッシュ装置でプリフェッチを行う際に問題となる事柄のひとつとして、他のキャッシュ装置の状態検出がある。通常の読出要求では、要求アドレスに対してのみキャッシュ装置の状態検出を行えば良い。しかし、プリフェッチを導入すると、要求アドレスだけでなく、プリフェッチ要求アドレスについてもキャッシュ装置の状態検出が必要となる。そこで、共有バス上に、読出要求に対応した状態信号線と、プリフェッチ要求に対応した状態信号線を設け、状態検出結果を同時に通知し、リクエスト時のオーバーヘッドを削減する。
【００３３】
キャッシュ装置のキャッシュコントローラは、専用の状態信号線を用いた続出要求とプリフェッチ読出要求の同時要求に対する応答（リプライ）として、応答メッセージのヘッダに読出要求の応答データとプリフェッチ要求の応答データを識別する識別ビットを設け、識別ビットを有効とするデータをまとめて転送する。これによって、リプライ時のオーバーヘッドを削減する。
【００３４】
このように読出要求とプリフェッチ読出要求が同時に出ていることを利用して、両者にリプライをまとめる。この時、プリフェッチ読出要求には、弱いプリフェッチプロトコルを用いているため、読出しに失敗する可能性がある。プリフェッチに失敗した場合は、リプライのデータ部を切り詰めて要求元に送る。この時、識別ビットの有効状態をみることで、読出要求に対応したリプライか、プリフェッチ要求に対応したリプライか、両方に対応したリプライがが分かる。このように複数の要求に対するリプライをひとつにまとめると同時に、データの存在しない部分を切り詰めることによって、効率的なデータ転送を実現することができる。
【００３５】
また本発明は、複数のプロセッサ毎に設けられたキャッシュ装置を相互に共通結合網で結合されると共に主記憶と結合したキャッシュシステムの制御方法を提供する。
【００３６】
第１ウィークリードを行うキャッシュシステムの制御方法は、
１．主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共に、データの一貫性管理に使用する状態タグをキャッシャライン毎に設定し、
２．プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合は、プリフェッチ要求を失敗させる弱い読出操作をフェッチプロトコルとして実行する。
【００３７】
また第２ウィークリードを行うキャッシュシステムの制御方法は、
１．主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共に、データの一貫性管理に使用する状態タグをキャッシャライン毎に設定し、
２．プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態タグを変更しなければ読み出せない場合、状態タグを変更することなくデータを読み出して前記プロセッサに応答した後に弱い読出状態Ｗを設定してキャッシュメモリに保存し、
３．ソフトウェアによりデータの一貫性をとるメモリコンシステンシの同期操作時に、前記弱い読出状態Ｗにあるキャッシュメモリのデータを全て無効化する。
【００３８】
更に、消極的保存モードＰを採用したキャッシュシステムの制御方法は、
１．主記憶の一部のデータをキャッシュメモリ上でキャッシュライン単位に保存すると共にデータの一貫性管理に使用する状態タグをキャッシャライン毎に設定したキャッシュメモリと、
２．プロセッサの読出要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置又は主記憶からプリフェッチしたデータに消極的保存モードＰを設定してキャッシュメモリに保存し、
３．他のキャッシュ装置からの読出要求に該当するデータが消極的保存モードＰを設定したプリフェッチデータの場合、該当データの保存を他のキャッシュ装置に通知せず、
４．他の全てのキャッシュ装置が該当データを保存していない場合はプリフェッチデータを無効化し、他のキャッシュ装置に該当データが共有されている場合は、前記プリフェッチデータをそのまま保存する。
【発明の実施の形態】
【００３９】
（システム構成）
図４は、本発明のキャッシュ装置が適用されるマルチプロセッサシステムのブロック図である。マルチプロセッサシステムは、複数のプロセッサ１２−１，１２−２，・・・１２−ｎを有し、プロセッサ１２−１〜１２−ｎごとに本発明のキャッシュ装置１０−１，１０−２，・・・１０−ｎを設け、キャッシュ装置１０−１〜１０−ｎを通じて共通結合網としての共有バス１４で接続されている。共有バス１４に対してはメインメモリ１８がメモリコントローラ１６を介して接続されており、メインメモリ１８はシステム上に１つしか存在しない。
【００４０】
図５は、図４のマルチプロセッサシステムに設けたキャッシュ装置に対する共有バス１４の詳細である。共有バス１４にはキャッシュ装置１０の状態を検査した結果を流すＥＸ線２０、ＨＩＴ線２２、ＨＩＴＭ線２４が状態信号線として設けられる。またアドレスバス２６、データバス２８、コマンドバス３０が設けられる。このような共有バス１４としてはスヌープバスを用いる。
【００４１】
キャッシュ装置１０には、キャッシュコントローラ３０とキャッシュメモリ３２が設けられている。共有バス１４のＥＸ線２０、ＨＩＴ線２２、ＨＩＴＭ線２４は、各キャッシュ装置のキャッシュコントローラ３０で共有されており、メモリトランザクションからの特定のタイミングでアサートされるように規定されている。即ち、キャッシュコントローラ３０から何らかのメモリトランザクションが発生すると共有バスにリクエストメッセージが送出され、外部のキャッシュ装置のキャッシュコントローラは、トランザクションの要求アドレスに対応するデータが自分のキャッシュメモリ３２に存在するか否か、存在すればどうゆう状態かを調べ、調べた状態に応じてＥＸ線２０、ＨＩＴ線２２、ＨＩＴＭ線２４に乗せて通知する。ここで、本発明のキャッシュ装置のデータの一貫性を保持するためのプロトコルとしてはＭＥＳＩプロトコルを採用している。
【００４２】
図６（Ａ）は、本発明のキャッシュ装置に適用されるＭＥＳＩプロトコルのリード要求に対する状態遷移であり、図６（Ｂ）は同じくＭＥＳＩプロトコルのライト要求に対する状態遷移である。この状態遷移の記号は次の内容を表わす。
【００４３】
Ｍ：変更（Ｍｏｄｉｆｉｅｄ）であり、複数のキャッシュのうちの１つにのみ 書き替えられたデータが保存されている。
【００４４】
Ｅ：排他（Ｅｘｃｌｕｓｉｖｅ）であり、複数のキャッシュの１つにのみ書き 替えられていない有効データが保存されている。
【００４５】
Ｓ：共有（Ｓｈａｒｅｄ）であり、複数のキャッシュ上に同じデータが保存さ れている。
【００４６】
Ｉ：無効（Ｉｎｖａｌｉｄ）であり、キャッシュ上のデータは無効である。
ｓｅｌｆ：自己のプロセッサからの要求を処理した場合である。
ｏｔｈｅｒ：他のキャッシュ装置からの要求を処理した場合である。
ｓｅｌｆ−ｉｆ−ｃｏｐｙ：リード要求に対し無効状態にあり、他のキャッシ ュから有効データをコピーする。
ｓｅｌｆ−ｉｆ ｎｏ ｃｏｐｙ：リード要求に対し無効状態にあり、メイン メモリから有効データをコピーする。
【００４７】
このようなＭＥＳＩプロトコルに基づき、図５の共有バス１４にあっては、キャッシュコントローラ３０がメモリトランザクションの要求アドレスに対応するデータがキャッシュ上に存在して、その状態を調べたときに、無効状態ＥであればＥＸ線２０をアサートし、共有状態ＳであればＨＩＴ線２２をアサートし、また変更状態ＭであればＨＩＴＭ線２４をアサートする。これによって、各キャッシュ装置のキャッシュコントローラ３０は、現時点で共有バス１４に流れたメモリトランザクションに基づくリクエストメッセージに対応するデータが
１．いずれかのキャッシュに排他状態Ｅで保存されているか
２．複数のキャッシュ装置上に共有状態Ｓで保存されているか
３．いずれかのキャッシュに変更状態Ｍで保存されているか
４．キャッシュ上にデータが存在しない無効状態Ｉであるか
を判断することができる。
【００４８】
図７は、図５のキャッシュ装置におけるキャッシュコントローラ３０及びキャッシュメモリ３２の機能を詳細に示したブロック図である。キャッシュ装置１０は大きく分けてキャッシュコントローラ３０とキャッシュメモリ３２で構成される。キャッシュコントローラ３０はキャッシュメモリ３２の動作を司るもので、プロセッサ１２からデータ要求を受け取ったり、共有バス１４にリクエストメッセージを発行する。また常に共有バス１４上のトラフィックを監視しており、他のキャッシュ装置からのリクエストメッセージがバス上に流れると、このリクエストメッセージに応じたキャッシュ動作を行う。
【００４９】
キャッシュコントローラ３２は、キャッシュ制御管理部３４、プロセッサインタフェース３６、バスインタフェース３８、リードプロトコル処理部４０、プリフェッチプロトコル処理部４２及びライトプロトコル処理部４４が設けられる。リードプロトコル処理部４０は、図６（Ａ）のＭＥＳＩリードプロトコルに従って、通常のリード動作に伴う一貫性管理のための処理を実行する。またライトプロトコル処理部４４は図６（Ｂ）のＭＥＳＩライトプロトコルに基づき、データ一貫性を保持するための処理を行う。
【００５０】
本発明で新たに設けたプリフェッチプロトコル処理部４２は、第１ウィークプロトコルリード処理部４５、第２ウィークプロトコルリード処理部４６及び消極的読出モード処理部４８で構成される。第１ウィークプロトコルリード処理部４５は、プロセッサ１２のメモリアクセス要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置に保存しているデータを、その状態を変更しなければ読み出せない場合は、プリフェッチ要求を失敗させる弱い読出動作を行う。
【００５１】
第２ウィークプロトコルリード処理部４６は、プロセッサ１２のメモリアクセス要求に伴ってプリフェッチ要求が発生した際に、他のキャッシュ装置が保存しているデータを、その状態を変更しなければ読み出せない場合、状態を変更することなく強制的に読み出して、ウィークプロトコルリードを示す弱い状態Ｗを設定してキャッシュメモリに保存する。この第２ウィークプロトコルリード処理部４６は、プロセッサ１２側のソフトウエアによるデータの一貫性をとるメモリコンシステンシモデルと組み合わされており、データの一貫性をとるために流す同期メッセージを受けた際に、弱い状態Ｗにあるキャッシュメモリ３２のデータを全て無効化する。
【００５２】
消極的読出モード処理部４８は、第１ウィークプロトコルリード処理部及び第２ウィークプロトコルリード処理部４５，４６が他のキャッシュ装置からデータをプリフェッチする際の弱い読出操作を実行するに対し、他のキャッシュ装置におけるメモリアクセス要求の該当アドレスにプリフェッチデータを保持していた場合の処理である。即ち、消極的読出モード処理部４８は、キャッシュメモリ３２にプリフェッチデータを格納する際に消極的保存モードを示すモードＰを設定して保存しており、他のキャッシュ装置からの読出要求に該当するデータが消極的保存モードを設定したプリフェッチデータであった場合、このプリフェッチデータの保存を他のキャッシュ装置に通知せず、他のキャッシュ装置によるプリフェッチデータの利用を排除している。また消極的保存モードＰで格納されたプリフェッチデータは、他のキャッシュ装置が全て無効状態Ｉか、データが排他状態Ｅ又は変更状態Ｍで保存された場合には、消極的保存モードＰを設定したプリフェッチデータの状態は無効状態Ｉとする。また、他のキャッシュ装置で該当するデータが共有状態Ｓになっている場合には、プリフェッチデータの状態は変更せずにそのまま保存する。
【００５３】
このようなキャッシュコントローラ３０のプリフェッチプロトコル処理部４２に設けられた第１ウィークプロトコルリード処理部４５、第２ウィークプロトコルリード処理部４６及び消極的読出モード処理部４８は、装置立ち上げ時のセットアップ処理等により
１．第１ウィークプロトコルリード処理部４５と消極的読出モード処理部４８
２．第２ウィークプロトコルリード処理部４６と消極的読出モード処理部４８
のいずれかの組合せが選択的に設定される。もちろん、キャッシュコントローラ３０の機能として第１，第２ウィークプロトコルリード処理部４５，４６のいずれか一方の機能と消極的読出モード処理部４８の機能を固定的に設けるようにしてもよい。
【００５４】
キャッシュメモリ３２は、メインメモリ１８の一部のコピーを保存しておくための場所であり、キャッシュライン５０はタグ５２、キー５４、キャッシュアレイ５６で構成される。キャッシュアレイ５６はデータを保存するための場所であり、メインメモリ１８のコピーやプロセッサ１２によって更新されたデータが保存されている。キャッシュアレイ５６はブロック単位に管理されており、１ブロックはプロセッサ１２が処理するデータ単位の複数データから構成されている。タグ５２及びキー５４はキャッシュアレイ５６の各ブロックの状態を表わし、１つ１つのキャッシュアレイ５６に対応している。キャッシュメモリ３２としては一般に、あるインデックス（何番目のエントリか）に対応するデータを複数持たせるセット・アソシエイティブ・キャッシュ（連想キャッシュ）が用いられるが、この実施例では説明を簡単にするため、１つのインデックスに１つのアドレスが対応するダイレクト・マップ・キャッシュを用いる。
【００５５】
キー５４はキャッシュアレイ５６のデータがどのアドレスのメモリのコピーかを表わしており、インデックスと合わせるとアドレスが一義的に定まるようになっている。ダイレクトマップキャッシュの場合にはインデックスとアドレスが１対１に対応していることから、キーは直接アドレスを表わすことになる。タグ５２はキャッシュアレイ５６に格納したデータブロックの状態を表わし、図８に取り出して示すように、２ビットｂ１，ｂ２で構成される。このタグ５２の２ビットデータｂ１，ｂ２により、図６（Ａ）（Ｂ）のＭＥＳＩプロトコルによる保存データの状態は図９のように表現される。
【００５６】
（第１ウィークプロトコルリード）
本発明のキャッシュ装置１０におけるプリフェッチプロトコル処理の第１実施例として、図７のキャッシュコントローラ３０に設けている第１ウィークプロトコルリード処理部４５によるプリフェッチ処理を説明する。
【００５７】
図４のマルチプロセッサシステムにおいて、いま、プロセッサ１２−１からメモリアクセスの要求が出た場合を考える。プロセッサ１２−１からのメモリアクセスに伴うデータ要求は、キャッシュ装置１０−１より共有バス１４にリクエストメッセージとして流される。これに加えて本発明にあっては、キャッシュ装置１０−１においてハードウェアによるプリフェッチを行っている。この実施例では説明を簡単にするため、プロセッサ１２−１からのデータ要求アドレスＡＤＲに対し、アドレス（ＡＤＲ＋ｎ）のデータをプリフェッチする。ここでｎは任意のブロックサイズであり、隣接１または複数のブロックのプリフェッチを行うことになる。プロセッサ１２−１からのデータ要求に付随してハードウェアにより発生したプリフェッチは、図６の第１ウィークプロトコルリード処理部４５の処理により弱いリードプロトコルのリクエストメッセージとして共有バス１４に送出される。即ちキャッシュコントローラ３０は、プロセッサ１２からのデータ要求アドレスＡＤＲによる通常リードについては、通常リードのリクエストメッセージを共有バス１４に送出し、この通常リードのリクエストメッセージに対するリプライメッセージが終了した後に、要求アドレスＡＤＲ＋ｎをプリフェッチするための弱いプロトコルによるリードのためのリクエストメッセージが第１ウィークプロトコルリード処理部４５により共有バス１４に送出し、通常リードと弱いプロトコルリードのリクエストメッセージが区別して設けられている。
【００５８】
キャッシュコントローラ３０から弱いプロトコルによるリードのためのリクエストメッセージが発行されると、通常のリードと同様に、他のキャッシュ装置がスヌープ動作を開始する。即ち、他のキャッシュ装置は弱いプロトコルによるリードのリクエストメッセージで得られた要求アドレスＡＤＲ＋ｎを調べ、この要求アドレスＡＤＲ＋ｎに対応するデータが自分のキャッシュメモリの中に存在するか、また存在した場合にはその状態は何かを調べる。キャッシュメモリの中に該当するデータが存在し、排他状態Ｅの場合にはそのキャッシュコントローラはＥＸ線２０をアサートし、共有状態Ｓの場合にはＨＩＴ線２２をアサートし、また変更状態ＭであればＨＩＴＭ線２４をアサートし、無効状態Ｉであればいずれの状態制御線もアサートしない。
【００５９】
プリフェッチの要求元のキャッシュコントローラ３０及びメインメモリ１８のメモリコントローラ１６は、共有バス（スヌープバス）１４を監視し、他のキャッシュ装置の状態により次のように処理する。
【００６０】
１．ＥＸ線、ＨＩＴ線及びＨＩＴＭ線のいずれもアサートされずに無効状態Ｉの場合は、プリフェッチ要求は成功したものとして、メインメモリ１８から要求元キャッシュ装置に要求アドレスＡＤＲ＋ｎから読み出したデータを転送する。要求元のキャッシュコントローラ３０は、メインメモリ１８から転送されたデータをキャッシュアレイに排他状態Ｅとして保存する。
【００６１】
２．要求元のキャッシュコントローラ３０及びメインメモリ１８のメモリコントローラ１６は、ＨＩＴ線のみがアサートされた共有状態Ｓの場合はプリフェッチ要求は成功したと見做し、他のキャッシュメモリから要求アドレスＡＤＲ＋ｎのデータを読み出して転送し、要求元のキャッシュコントローラ３０は転送データを共有状態Ｓとしてキャッシュアレイに保存する。
【００６２】
３．要求元のキャッシュコントローラ３０及びメインメモリ１８のメモリコントローラ１６は、ＥＸ線がアサートされた排他状態ＥまたはＨＩＴＭ線がアサートされた変更状態Ｍの場合、即ち通常のリードプロトコルでは要求元のキャッシュ装置の状態を変更しなければならない場合については、プリフェッチ要求は失敗したものと見做し、処理を中断する。
【００６３】
図１０は、図７の第１ウィークプロトコルリード処理部によるプリフェッチ処理のフローチャートである。プロセッサ１８からのメモリ要求に付随してハードウェアによって要求アドレスＡＤＲ＋ｎのプリフェッチ要求が行われると、まずステップＳ１で自己のキャッシュメモリ３２を検索し、ステップＳ２でキャッシュ上に該当するデータが存在してヒットしたか否か判定する。ヒットすれば、ステップＳ９でプロセッサに読み出したデータを返し、一連の処理を終了する。ステップＳ２でキャッシュ上に該当するデータが存在せずにヒットしなかった場合には、ステップＳ３で共有バス１４に弱いプロトコルによるリードのためのリクエストメッセージを流す。この弱いプロトコルによるリードのためのリクエストメッセージに対し、他のキャッシュ装置で要求アドレスＡＤＲ＋ｎのデータが保存されているかどうか、保存されていた場合にはその状態が調べられ、対応する状態制御線がアサートされる。
【００６４】
まずステップＳ４で、ＥＸ線のアサートによる排他状態ＥまたはＨＩＴＭ線のアサートによる変更状態Ｍか否かチェックする。排他状態Ｅまたは変更状態Ｍに対応した状態制御線のアサートであれば、ステップＳ５に進み、プリフェッチ要求のデータ読出しは失敗したものとして処理を終了する。ステップＳ４でＥＸ線またはＨＩＴＭ線のアサートでなければ、ステップＳ６に進み、ＨＩＴＭ線のアサートによる共有状態Ｓか否かチェックする。ＨＩＴＭ線がアサートされていれば共有状態Ｓにあることから、ステップＳ７に進み、他のキャッシュメモリから要求アドレスＡＤＲ＋ｎのデータを読出転送し、状態を共有状態Ｓにしてキャッシュアレイに保存する。またステップＳ６でＨＩＴＭ線がアサートされなければ無効状態Ｉであることから、ステップＳ８に進み、メインメモリ１８から要求アドレスＡＤＲ＋ｎのデータを読出転送し、キャッシュアレイに排他状態Ｅとして保存する。
【００６５】
このようにプリフェッチによって他のキャッシュ装置の状態を変更する必要がある場合、即ちプリフェッチ要求の該当データが他のキャッシュ装置に排他状態Ｅまたは変更状態Ｍで保存されている場合については、プリフェッチ要求を弱いプロトコルによるリード操作とすることで、プリフェッチ要求に対するデータ読出しを失敗したものと見做して処理を中断させることで、排他状態Ｅまたは変更状態Ｍにある他のキャッシュ装置のデータをプロセッサがアクセスした際に、同じデータをプリフェッチデータとして保存しているキャッシュ装置の状態を共有状態Ｓとする操作を不要とし、排他状態Ｅまたは変更状態Ｍでデータを保持しているキャッシュ装置におけるプロセッサ書込時のオーバーヘッドを削減することができる。
【００６６】
（第２ウィークプロトコルリード）
次に図７のキャッシュコントローラ３０に設けた第２ウィークプロトコルリード処理部４６によるプリフェッチ処理を説明する。この第２ウィークプロトコルリードと既に説明した第１ウィークプロトコルリードの相違は、図１１に取り出して示すキャッシュライン５０におけるタグ５４の構造であり、キャッシュアレイ５８のデータの状態を示す２ビットデータｂ１，ｂ２に加え、第２ウィークプロトコルリードによってプリフェッチしたデータであることを示すウィーク状態Ｗを示すタグが付加されている。このため第２ウィークプロトコルリードにあっては、図６（Ａ）のＭＥＳＩプロトコルにウィーク状態Ｗを加えたＭＥＳＩＷプロトコルということができる。このウィーク状態Ｗはメモリトランザクションの順番を入れ替え、書込みの結果が反映されない状態のままでいるプリフェッチデータを表わす。
【００６７】
この第２ウィークプロトコルリードの処理にあっては、ソフトウェアによってメモリ間のデータの一貫性を保持するためのメモリコンシステンシモデルとしてウィークコンシステンシを採用する。ウィークコンシステンシとは、同期操作のためのｓｙｎｃメッセージとｓｙｎｃメッセージの間のメモリトランザクションの順序は任意であるというもので、プロセッサ間等での同期が必要な場合には必ずｓｙｎｃメッセージを流さなくてはならないというコンシステンシモデルである。このようなウィークコンシステンシモデルとしては、例えば、平成９年５月「並列処理シンポジウムＪＳＰＰ，９７」の城 和貴著「メモリコンシステンシモデルの諸定義と解説例」第１５７〜１５８頁がある。
【００６８】
このウィークコンシステンシモデルを採用すると、プリフェッチによってキャッシュに書き込まれた結果が反映されないデータが他のキャッシュ装置に存在しても構わない。しかしながら、ｓｙｎｃメッセージが来たときには、あるキャッシュ装置に書き込まれた結果が他のキャッシュ装置に反映されない限り同期操作は終了しない。このようなウィークコンシステンシモデルを利用し、第２ウィークプロトコルリードにあっては、既に説明した第１ウィークプロトコルリードでは失敗となっていたプリフェッチ要求を読出成功により正常終了させる手法を採用する。
【００６９】
まず図４のマルチプロセッサシステムにおいて、例えばプロセッサ１２−１からキャッシュ装置１０−１に対しメモリアクセスの要求が出たとする。プロセッサ１２−１からのデータ要求は、図７のキャッシュコントローラ３０に設けたリードプロトコル処理部４０による通常のリードとしてデータ要求アドレスＡＤＲに対応したリクエストメッセージを共有バス１４に流す。本発明のキャッシュ装置にあっては、ハードウェアによるプリフェッチを行うことから、データ要求アドレスＡＤＲに対し要求アドレスＡＤＲ＋ｎのデータをプリフェッチ要求として出す。このプリフェッチ要求は、図７のキャッシュコントローラ３０に設けた第２ウィークプロトコルリード処理部による弱いプロトコルによるリードのリクエストメッセージとして共有バス１４に流される。
【００７０】
キャッシュコントローラ３０から第２ウィークプロトコルリードに従ったリクエストメッセージが発行されると、通常のリードと同様、他のキャッシュ装置がスヌープ動作を開始する。即ち、他のキャッシュ装置はプリフェッチ要求のアドレスＡＤＲ＋ｎを調べ、要求アドレスに対応するデータが自分のキャッシュアレイの中に存在するか否か選び、存在した場合には状態が何かを調べる。キャッシュアレイの中に存在し且つ排他状態Ｅの場合には、キャッシュコントローラはＥＸ線をアサートし、共有状態Ｓの場合にはＨＩＴ線をアサートし、変更状態ＭであればＨＩＴＭ線をアサートし、更に無効状態Ｉであればいずれの状態信号線もアサートしない。これによってプリフェッチの要求アドレスＡＤＲ＋ｎのデータに関するデータの保存状態を他の全てのキャッシュ装置及びメモリコントローラ１６に通知する。
【００７１】
要求元のキャッシュコントローラ３０及びメインメモリ１８のメモリコントローラ１６は、共有バス（スヌープバス）１４を監視し、ＥＸ線，ＨＩＴ線及びＨＩＴＭ線のいずれもアサートされていない無効状態Ｉであれば、プリフェッチ要求は成功したものとしてメインメモリ１８からデータを転送し、要求元のキャッシュコントローラ３０は転送データをキャッシュアレイに排他状態Ｅとして保存する。またＨＩＴ線のみがアサートされた共有状態Ｓであれば、これもプリフェッチ要求は成功したと見做し、他のキャッシュメモリから要求アドレスのデータを転送し、要求元のキャッシュコントローラ３０は転送データを共有状態Ｓとしてキャッシュアレイに保存する。更に通常のリードでは、データ変更を必要とするＥＸ線がアサートされている排他状態Ｅの場合にも、第２ウィークプロトコルリードではプリフェッチ要求は成功したものとしてメインメモリ１８から要求アドレスのデータを転送し、この場合、要求元のキャッシュコントローラ３０は転送データをウィーク状態Ｗとしてキャッシュアレイに保存する。更に要求元のキャッシュコントローラ３０及びメインメモリ１８のメモリコントローラ１６は、ＨＩＴＭ線がアサートされている変更状態Ｍの場合については、
１．第２ウィークプロトコルリードに従って、プリフェッチ要求は成功したものとしてメインメモリ１８からデータを転送し、ウィーク状態Ｗで保存する方法、
２．通常のメモリトランザクションと同様、ライトバックによって読出しを成功させる方法、
３．第１ウィークプロトコルリードと同様、プリフェッチ要求は失敗したものとみなして処理を中断する方法、
のいずれかがある。
【００７２】
図１２は、第２ウィークプロトコルリードによるプリフェッチ処理のフローチャートである。まずステップＳ１で、プロセッサ１２からのメモリアクセスの要求に伴い要求アドレスＡＤＲからハードウェアでプリフェッチの要求アドレスＡＤＲ＋ｎによるプリフェッチ要求が行われると自己のキャッシュメモリ３２を検索し、要求アドレスＡＤＲ＋ｎのデータがキャッシュアレイに存在するか否か検索する。ステップＳ２でキャッシュアレイに存在してヒットとなれば、ステップＳ９でプロセッサ１２に読み出したデータを返し、処理を終了する。キャッシュアレイに要求アドレスのデータが存在しない場合には、ステップＳ３で第２ウィークプロトコルリードによるリクエストメッセージを共有バス１４に流す。このリクエストメッセージに対し、他のキャッシュ装置で要求アドレスＡＤＲ＋ｎのデータの存在の有無及び存在した場合の状態が検査され、そのプラスの状態制御線がアサートされる。ステップＳ４でＥＸ線がアサートされる排他状態ＥまたはＨＩＴＭ線がアサートされる変更状態Ｍの場合には、ステップＳ５に進み、メインメモリ１８から要求アドレスＡＤＲ＋ｎのデータを読出転送し、キャッシュアレイにウィーク状態Ｗのビットを立ててキャッシュアレイに保存する。ステップＳ４でＥＸ線またはＨＩＴＭ線のいずれもアサートされていない場合には、ステップＳ６に進み、ＨＩＴ線がアサートされているか否かチェックする。ＨＩＴ線がアサートされて共有状態Ｓの場合には、ステップＳ７に進み、他のキャッシュメモリ１８からの要求アドレスＡＤＲ＋ｎの転送データをキャッシュアレイに共有状態Ｓとして保存する。またステップＳ６でＨＩＴ線がアサートされていない無効状態Ｉの場合には、ステップＳ８に進み、メインメモリ１８から要求アドレスＡＤＲ＋ｎのデータを転送して排他状態Ｅでキャッシュアレイに保存する。
【００７３】
このような第２ウィークプロトコルリードに従ったプリフェッチ処理を行っている段階で同期メッセージがいずれかのプロセッサから発行されると、各キャッシュ装置のキャッシュコントローラは処理中の全てのトランザクションが終了するまでプロセッサからの新たなトランザクションの受付を抑止し、同時に共有バス１４にｓｙｎｃメッセージを流し、全てのキャッシュ装置のキャッシュコントローラに同期処理を通知する。ｓｙｎｃメッセージを受け取ったキャッシュコントローラ３０は、自分のキャッシュメモリ３２におけるキャッシュアレイ５６のタグ５２を検査し、ウィーク状態Ｗのデータを検索する。この検索により見つかったウィーク状態Ｗのデータについて、全て無効状態Ｉに変更することで無効化する。プロセッサからの同期メッセージに基づく同期処理は、全てのキャッシュ装置におけるウィーク状態にあるデータの無効化終了で完了する。
【００７４】
この第２ウィークプロトコルリードによるプリフェッチ処理にあっても、プリフェッチ要求に伴って他のキャッシュ装置に排他状態Ｅまたは変更状態Ｍにあるデータをメインメモリからプリフェッチする際に、他のキャッシュ装置の状態変更を起こすことを防止でき、またメモリコンシステンシモデルによる同期操作で他のキャッシュ装置の状態変更を無視して強制的にプリフェッチしたデータを無効化することで、排他状態Ｅまたは変更状態Ｍのデータを保存しているキャッシュ装置でプロセッサの書き込みが生じたときのオーバーヘッドを、メモリコンシステンシモデルの同期操作を以てウィーク状態Ｗのプリフェッチデータの保存を無効化することで、改めて無効化する必要なく書込時のオーバーヘッドを削減することができる。
【００７５】
（消極的保存モード）
次に図７のキャッシュコントローラ３０に設けている消極的読出モード処理部４８によるプリフェッチデータのキャッシュ上における消極保存モードを説明する。この消極的保存モードは、キャッシュ上に保存されているプリフェッチデータと同じアドレスのデータについて、他のキャッシュ装置でデータ要求が行われた際にプリフェッチデータを無効化するプロトコルである。
【００７６】
図１３は、消極的保存モードを適用するためのキャッシュライン５０を取り出しており、新たに保存モード識別タグ６０を設けている。この保存モード識別タグ６０には、通常保存方法を示すＮモード（Ｎｏｍａｌ Ｍｏｄｅ）か本発明の消極的な保存方法を示すＰモード（Ｐａｓｓｉｖｅ Ｍｏｄｅ）を示す符号が配置される。タグ５４の２ビットデータｂ１，ｂ２によるデータの状態は、図９のＭＥＳＩのいずれかである。この場合、消極的な保存方法であるＰモードで保存されている時には、変更状態Ｍとなることはない。即ち、図６（Ｂ）のＭＥＳＩライトプロトコルの遷移状態のように、変更状態Ｍに遷移するのはＰモードにおける排他状態Ｅまたは共有状態Ｓでプロセッサ１２がデータ書込みによる更新を行った場合であり、この場合には共有バスに無効化メッセージを流して他のキャッシュ装置に保存されているデータを無効化してから変更状態Ｍに遷移するため、その時点でプリフェッチデータでなくなり、ＰモードからＮモードとなる。したがって、Ｐモードのデータには変更状態Ｍはない。
【００７７】
一方、キャッシュアレイから読み出す際にＰモードであったときのモード制御については、
１．通常のリードを出してＰモードのデータをＮモードに変更して読み出す方法、
２．Ｐモードのままプロセッサの読出要求を終了させる方法、
３．Ｐモードのままプロセッサの読出要求を終了させた後に通常のリードを出してＰ
モードのデータをＮモードにする方法、
が考えられる。この実施例では、最も簡単な２．のＰモードのままプロセッサの続出要求を終了させる方法を採用する。
【００７８】
更にＰモードで保存されているデータに対しては、共有バス上に他のキャッシュ装置から流されたリクエストメッセージに対しキャッシュの状態検査の結果を出力せず、Ｐモードの保存データが排他状態Ｅでも共有状態Ｓでも変わることはない。したがって、Ｐモードで保存されているデータの状態は無効状態Ｉか排他状態Ｅまたは共有状態Ｓのいずれかである。
【００７９】
このようにキャッシュメモリ３２の各キャッシュラインごとに、通常のデータ読出しによるデータはＮモードで保存し、プリフェッチによる読出データは消極的な保存方法であるＰモードで保存することを、１つのキャッシュメモリ３２上で行うことができる。
【００８０】
消極的な保存方法であるＰモードでキャッシュメモリ上にデータが保存されている場合、他のキャッシュ装置におけるメモリアクセスの要求で共有バス上に通常のリードもしくは弱いプロトコルのリードによるリクエストメッセージが流れた場合、Ｐモードでデータを保存しているキャッシュコントローラ３０は、図７の消極的読出モード処理部４８の機能により次のような動作を行う。
【００８１】
まず共有バス１４に流れたリクエストメッセージに基づく状態検査の結果を待つ。この場合、Ｐモードのデータを保持しているキャッシュコントローラ３０は、キャッシュの状態に関わらずＥＸ線，ＨＩＴ線，ＨＩＴＭ線のいずれもアサートせず、外部からは無効状態Ｉと見えるようにする。他のキャッシュ装置における状態検査の結果によりＥＸ線，ＨＩＴ線，ＨＩＴＭ線のいずれもアサートされなかった場合、即ちＰモードのデータを保存しているキャッシュコントローラ以外のキャッシュコントローラが無効状態Ｉの場合、Ｐモードでデータを保存しているキャッシュコントローラ３０は自らのデータを無効化するため、Ｐモードのデータの状態を無効状態Ｉに変化させる。これによって、リード要求を発行した他のキャッシュコントローラは、排他状態Ｅでメインメモリ１８から要求アドレスのデータを読み出して保存することができる。
【００８２】
またＥＸ線またはＨＩＴＭ線がアサートさせ、他のキュッシュ装置のいずれかにデータが排他状態Ｅ又は変更状態Ｍで保存されている場合にも、Ｐモードでデータを保存しているキャッシュコントローラ３０は、Ｐモードのデータの状態を無効状態Ｉに変化させる。一方、他のキャッシュコントローラの状態検査の結果、ＨＩＴ線がアサートされた共有状態Ｓの場合には、Ｐモードでデータを保存しているキャッシュコントローラ３０は自らのデータの状態は変更させる必要はない。
【００８３】
図１４は他のキャッシュ装置からのリードによるリクエストメッセージが共有バスに流れたときのＰモードで要求アドレスのデータを保存しているキャッシュ装置の動作のフローチャートである。ステップＳ１で共有バス１４に他のキャッシュ装置のリードによるリクエストメッセージが流れると、リクエストメッセージの要求アドレスのデータを自分が消極的保存であるＰモードのコピーとして保持するか否かステップＳ２でチェックしている。Ｐモードで要求アドレスのデータを保持していれば、ステップＳ３でＨＩＴ線がアサートされているか否かチェックし、アサートされていなければ、即ち他のキャッシュ装置の全てが無効状態Ｉ、いずれかが排他状態Ｅか変更状態Ｍの場合は、ステップＳ４でＰモードデータの状態を無効状態Ｉに無効化する。ステップＳ３でＨＩＴ線がアサートされた共有状態Ｓの場合にはＰモードの保存データの状態を変更する必要がないことから、ステップＳ４の無効化をスキップして処理を終了する。
【００８４】
このようにキャッシュ上にプリフェッチされたデータについては、消極的保存モードであるＰモードとすることで、他のキャッシュ装置からの読出しによるプリフェッチによるデータの無駄な共有を極力回避し、共有状態にある特定データの書込時におけるオーバーヘッドを削減することができる。
【００８５】
（リクエスト及びリプライの統合）
図１５は、通常のメモリ要求とプリフェッチ要求が重複した際に両者のリクエストとリプライをまとめて転送するためのキャッシュ装置及び共有バスの実施例である。図１５の実施例の共有バス１４にあっては、キャッシュ装置の状態を検査した結果を流す状態制御線がノーマル制御系６２とプリフェッチ制御系６４の２系統に分けて２本ずつ設けられている。即ち、ノーマル制御系６２には図５の実施例と同様、ＥＸ線２０，ＨＩＴ線２２及びＨＩＴＭ線２４が設けられている。これに加え新たにプリフェッチ制御系６４として、ＥＸ線６６，ＨＩＴ線６８及びＨＩＴＭ線７０を設けている。もちろん、これらノーマル制御系６２及びプリフェッチ制御系６４の状態制御線に加え、アドレスバス２６、データバス２８及びコマンドバス３０が設けられる。
【００８６】
キャッシュ装置１０のキャッシュコントローラは、通常読出しによるリプライメッセージを共有バス１４から受けると、ノーマル制御系６２の状態制御線に対し要求アドレスのデータの状態の検査結果を送出する。またプリフェッチ要求に対するリプライメッセージを受けると、要求アドレスのデータの状態をプリフェッチ制御系６４の状態制御線に出力する。キャッシュ装置１０におけるプリフェッチデータの保存は、図１３のキャッシュラインに示したように、保存モード識別タグ６０に消極的保存法を示すＰモードをセットしたデータ保存を行う。
【００８７】
このようなノーマル制御系６２とプリフェッチ制御系６４の２系統の状態制御線を使用したキャッシュ装置１０のキャッシュコントローラは、プロセッサからのデータ読出要求に対し通常の読出要求とプリフェッチ要求を１つのリクエストメッセージにまとめる手法をとる。図５に示したキャッシュ装置１０にあっては、プロセッサ１２からデータ要求が出されたときに、通常のデータ要求に従ったリクエストメッセージと弱いプロトコルリードを用いたプリフェッチ用のデータ要求のためのリクエストメッセージを順次別々に共有バス１４に送出していたが、図１５の実施例では、プロセッサから通常のデータ要求を受けて共有バス１４にデータ要求のリクエストメッセージを流した際に、メインメモリ１８のメモリコントローラ１６及び他のキャッシュ装置において通常のデータ要求に加えプリフェッチのための弱いプロトコルによるデータ要求も含まれると解釈する機能を備える。即ち、要求元のキャッシュ装置から共有バス１４に流されたリクエストメッセージの要求アドレスＡＤＲについて、他のキャッシュ装置及びメインメモリのメモリコントローラ１６は弱いプロトコルによる要求アドレスＡＤＲ＋ｎのプリフェッチ要求を兼ねていると解釈する。これによって、要求元のキャッシュ装置から通常のリード要求のリクエストメッセージと付随するプリフェッチのための弱いプロトコルリードによるリクエストメッセージを個別に共有バス１４に出す必要がなく、余分なリクエストのオーバーヘッドを削減することができる。
【００８８】
ここで、通常のデータ要求に伴うプリフェッチすべきデータが自分のキャッシュメモリにある場合には、弱いプロトコルによるプリフェッチのためのデータ要求を共有バスに出す必要がない。そこで、図１６のリクエストフォーマット７２をもつリクエストメッセージを送出する。
【００８９】
図１６のリクエストフォーマット７２は、要求元ＩＤ７４，コマンド７６に続き、通常データ有効ビット７８とプリフェッチデータ有効ビット８０を設け、その後にアドレス８２を配置している。このため、通常データ有効ビット７８のビットＤまたはプリフェッチデータ有効ビットのビットＢを制御することで、図１８のリクエスト側に示すように、通常＋プリフェッチのデータ要求を行うリクエストメッセージ、通常データだけを要求するためのリクエストメッセージ、更にはプリフェッチデータのみを要求するためのリクエストメッセージのいずれかを選択的に発行することができる。
【００９０】
このような通常データ及びまたはプリフェッチデータの要求がまとめてできるリクエストメッセージに伴い、図１５の共有バス１４に設けたノーマル制御系６２とプリフェッチ制御系６４の状態信号線が設けられることで、１つのリクエストメッセージで行われた通常データの要求とプリフェッチデータの要求に対し、キャッシュ装置は通常データに対する状態検査の結果とプリフェッチデータに対する状態検査の結果を同時に他のキャッシュ装置に通知することができる。
【００９１】
更に、この実施例では、通常データとプリフェッチデータの同時要求のリクエストメッセージに対しては、図１７に示すように両方同時にデータを返すリプライフォーマット８４を採用している。リプライフォーマット８４は、ヘッダ部８６とデータ部８８で構成される。ヘッダ部８６には要求元ＩＤ９０、コマンド９２、通常データ有効ビット９５、プリフェッチデータ有効ビット９６及びアドレス９８が設けられる。このヘッダ部８６の後ろには、通常データ有効ビット９５のＤビットが有効であれば通常データの要求に応じて読み出されたデータＤａｔａが付加される。このデータＤａｔａ０の後ろには、プリフェッチデータ有効ビット９６のビットＢが有効であれば予め定めたｎブロック分のプリフェッチ用のデータＤａｔａ１〜ｎが並べられる。このリプライフォーマット８４のリクエストフォーマット７２との関係は、図１８に示すように、リクエストメッセージが「通常＋プリフェッチ」の場合にはリプライメッセージは「通常＋プリフェッチ」か「通常」のみとなり、リクエストメッセージが「通常」のみであればリプライメッセージも「通常」のみとなり、更にリクエストメッセージが「プリフェッチ」のみであればリプライメッセージも「プリフェッチ」のみとなる。
【００９２】
このように、通常データとプリフェッチデータのリクエスト及びリプライについて１つにまとめ、且つキャッシュ装置における通常データとプリフェッチデータの状態検査結果を知らせるスヌープバスの状態信号線を２系統設けたことで、通常のメモリ要求とプリフェッチ要求が重なっても両者をまとめて転送することができ、データ転送の増加によるオーバーヘッドを可能な限り小さくすることができる。
【００９３】
尚、上記の実施形態は、マルチプロセッサのキャッシュ装置を結合する共有バスとしてスヌープバスを例にとるものであったが、同等の機能を有する総合結合網としての適宜の共有バスが適用できる。また上記の実施形態は、ＭＥＳＩプロトコルによるデータの一貫性管理を例にとるものであったが、これ以外のキャッシュコヒーレンスプロトコルであってもよいことはもちろんである。更にまた本発明は、その目的と利点を損なわない範囲の適宜の変形を含み、加えて実施例に示した数値による限定は受けない。
【発明の効果】
【００９４】
以上説明したにように、本発明のキャッシュ装置によれば、弱い読出操作をマルチプロセッサシステムのプリフェッチに利用することで、通常のデータとの無駄な共有をなるべく避け、キャッシュ装置に対する書込みのオーバーヘッドを小さくすることができる。
【００９５】
また通常の読出要求のリクエストに付随するプリフェッチ要求を埋め込み、まつリ通常読出とプリフェッチのリプライを一体化することで、プリフェッチが増加することによるデータ転送のオーバーヘッドを最小限に抑えることができる。
【図面の簡単な説明】
【００９６】
図１  マルチプロセッサシステムを対象とした従来のキャッシュシステムのブロック図；
図２  キャッシュメモリの説明図；
図３  一貫性を保つために他のキャッシュ装置の状態変更を伴う読出要求の説明図；
図４  本発明のキャッシュ装置を用いたマルチプロセッサシステムのブロック図；
図５  図４のキャッシュ装置を結合する共有バスをスヌープバスとした回路ブロック図；
図６  ＭＥＳＩプロトコルの状態遷移図；
図７  本発明のキャッシュ装置の機能ブロック図；
図８  図７のキャッシュメモリにおけるキャッシュラインの説明図；
図９  図７のタグビットと保存データの状態の対応説明図；
図１０  第１ウィークリードによるプリフェッチ処理のフローチャート；
図１１  第２ウィークリードで使用する弱い状態Ｗをもつタグビットの説明図；
図１２  第２ウィークリードによるプリフェッチ処理のフローチャート；
図１３  消極的保存モードＰを設定するキャッシュラインの説明図；
図１４  消極的保存モードで保存しているデータに対するプリフェッチ処理のフローチャート；
図１５  読出要求とプリフェッチ要求による状態検出が同時にできるスヌープバスの回路ブロック図；
図１６  読出要求にプリフェッチ要求を埋め込んだリクエストフォーマットの説明図；
図１７  図１６のリクエストフォーマットに対するリプライフォーマットの説明図；
図１８  図１６のリクエストに対する図１７のリプライの対応関係の説明図
【符号の説明】
【００９７】
１０−１，１０−２，・・・１０−ｎ：キャッシュ装置
１２−１，１２−２，・・・１２−ｎ：プロセッサ
１４：共有バス
１６：メモリコントローラ
１８：メインメモリ
２６：アドレスバス
２８：データバス
３０：キャッシュコントローラ
３２：キャッシュメモリ
３４：キャッシュ制御管理部
３６：プロセッサインタフェース
３８：バスインタフェース
４０：リードプロトコル処理部
４２：プリフェッチプロトコル処理部
４４：ライトプロトコル処理部
４５：第１ウィークプロトコルリード処理部
４６：第２ウィークプロトコルリード処理部
４８：消極的読出モード処理部
５６：キャッシュアレイ
６２：ノーマル制御系
６４：プリフェッチ制御系
【図１】
0003757117.tif 000002
【図２】
0003757117.tif 000003
【図３】
0003757117.tif 000004
【図４】
0003757117.tif 000005
【図５】
0003757117.tif 000006
【図６】
0003757117.tif 000007
【図７】
0003757117.tif 000008
【図８】
0003757117.tif 000009
【図９】
0003757117.tif 000010
【図１０】
0003757117.tif 000011
【図１１】
0003757117.tif 000012
【図１２】
0003757117.tif 000013
【図１３】
0003757117.tif 000014
【図１４】
0003757117.tif 000015
【図１５】
0003757117.tif 000016
【図１６】
0003757117.tif 000017
【図１７】
0003757117.tif 000018
【図１８】
0003757117.tif 000019