(57)【特許請求の範囲】
【請求項１】
プロセッサ毎に設けられ、相互に接続されるキャッシュ装置に於いて、
主記憶の一部のデータをキャッシュラインのブロック単位に保持すると共に前記キャッシュラインに保持したデータブロック状態を示す情報を保持するキャッシュメモリと、
前記データブロックの状態を、無効Ｉ（Ｉｎｖａｌｉｄ）、共有Ｓ（Ｓｈａｒｅｄ）、排他Ｅ（Ｅｘｃｌｕｓｉｖｅ）、変更Ｍ（Ｍｏｄｉｆｉｅｄ）、共有変更Ｏ（ＳｈａｒｅｄＭｏｄｉｆｉｅｄ）の他に、フェッチ要求があった場合に段階的に共有性を持たせるために書込可能Ｗ（Ｗｒｉｔａｂｌｅ  Ｍｏｄｉｆｉｅｄ）の６状態で表現して前記キャッシュメモリを制御するキャッシュコントローラと、
を備えたことを特徴とするキャッシュ装置。
【請求項２】
請求項１記載のキャッシュ装置に於いて、前記キャッシュコントローラは、
自系のプロセッサから無効Ｉの状態にあるデータブロックへのフェッチ要求に対し他系のキャッシュ装置から変更Ｍの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから書込可能Ｗに変更し、
変更Ｍの状態にあるデータブロックに対し他系のキャッシュ装置からフェッチ要求を受けた場合は、該データブロックの状態を変更Ｍから無効Ｉに切替えることを特徴とするキャッシュ装置。
【請求項３】
請求項２記載のキャッシュ装置に於いて、前記キャッシュコントローラは、自系のプロセッサから書込可能Ｗの状態にあるデータブロックへのストア要求に対し、該データブロックにデータをストアした後にデータブロックの状態を書込可能Ｗから変更Ｍに切替えることを特徴とするキャッシュ装置。
【請求項４】
請求項２記載のキャッシュ装置に於いて、前記キャッシュコントローラは、
データブロックが無効Ｉの状態にある他系のキャッシュ装置から書込可能Ｗの状態にあるデータブロックにフェッチ要求を受けた場合、該データブロックの状態を書込可能Ｗから共有変更Ｏに切替え、
自系のプロセッサからの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置から書込可能Ｗの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有Ｓに切替えることを特徴とするキャッシュ装置。
【請求項５】
請求項４記載のキャッシュ装置に於いて、前記キャッシュコントローラは、共有変更Ｏの状態にあるデータブロックに自系のプロセッサ又は他系のキャッシュ装置からフェッチ要求を受けた場合、共有変更Ｏの状態を維持することを特徴とするキャッシュ装置。
【請求項６】
請求項２記載のキャッシュ装置に於いて、前記キャッシュコントローラは、
データブロックが無効Ｉの状態にある他系のキャッシュ装置から書込可能Ｗのデータブロックにフェッチ要求を受けた場合、該データブロックの状態を書込可能Ｗから共有Ｓに切替え、
自系のプロセッサからの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置から書込可能Ｗの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有変更Ｏに切替えることを特徴とするキャッシュ装置。
【請求項７】
請求項６記載のキャッシュ装置に於いて、前記キャッシュコントローラは、
共有変更Ｏの状態にあるデータブロックに自系のプロセッサからフェッチ要求を受けた場合は、共有変更Ｏの状態を維持し、
共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置からフェッチ要求を受けた場合は、データブロックの状態を共有変更Ｏから共有Ｓに切替え、
自系のプロセッサからの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置から共有変更Ｏの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有変更Ｏに切替えることを特徴とするキャッシュ装置。
【請求項８】
請求項５又は７記載のキャッシュ装置に於いて、前記キャッシュコントローラは、
共有変更Ｏの状態にあるデータブロックに自系のプロセッサからストア要求を受けた場合は、データブロックの状態を共有変更Ｏから変更Ｍに切替え、
共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置からストア要求に基づく状態変更通知を受けた場合は、データブロックの状態を共有変更Ｏから無効Ｉに切替えることを特徴とするキャッシュ装置。
【請求項９】
プロセッサ毎に設けられ、相互にバス接続されるキャッシュ装置を制御するキャッシュ制御方法に於いて、キャッシュメモリに主記憶の一部のデータをキャッシュラインのブロック単位に保持すると共に前記キャッシュラインに保持したデータブロック状態を示す情報を保持し、
前記データブロックの状態を、無効Ｉ（Ｉｎｖａｌｉｄ）、共有Ｓ（Ｓｈａｒｅｄ）、排他Ｅ（Ｅｘｃｌｕｓｉｖｅ）、変更Ｍ（Ｍｏｄｉｆｉｅｄ）、共有変更Ｏ（Ｓｈａｒｅｄ  Ｍｏｄｉｆｉｅｄ）の他に、フェッチ要求があった場合に段階的に共有性を持たせるために書込可能Ｗ（Ｗｒｉｔａｂｌｅ  Ｍｏｄｉｆｉｅｄ）の６状態で表現して前記キャッシュメモリを制御することを特徴とするキャッシュ制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、マルチプロセッサシステムでキャッシュメモリを管理するキャッシュ装置及び制御方法に関し、特に、キャッシュデータの状態を細かく制御することによってアクセス性能を高めるようにしたキャッシュ装置及び制御方法に関する。
【０００２】
【従来の技術】
近年のコンピュータシステムの高速化の要求に伴い、マルチプロセッサシステムにおいては各ＣＰＵ（プロセッサ）にキャッシュ装置を設けている。ＣＰＵ毎に設けたキャッシュ上のデータは、キャッシュ間に亘ってそのデータの正しさ、即ちデータの共有と一貫性を保つため、キャッシュコヒーレンスプロトコルと呼ばれるキャシュ間のデータの整合性を保つ規則に従って、キャッシュメモリ上でブロック毎に管理されている。
【０００３】
従来の一般的なキャッシュプロトコルとしては、ＭＥＳＩの４状態を管理するＭＥＳＩキャッシュプロトコルが知られている。
【０００４】
図９は従来のＭＥＳＩキャッシュプロトコルの状態遷移図であり、図９（Ａ）がフェッチ要求（リード要求）の場合のフェッチプロトコルであり、図９（Ｂ）がストア要求（ライト要求）の場合のストアプロトコルである。この状態遷移の記号は次の内容を表わす。
【０００５】
Ｍ：変更（Modified) であり、複数のキャッシュの１つにのみ有効データが保持されており、かつ、データは変更されており、主記憶のそれと値が同じであることが保証されない。
【０００６】
Ｅ：排他(Exclusive) であり、複数のキャッシュの１つにのみ有効データが保持されている。
【０００７】
Ｓ：共有(Shared)であり、複数のキャッシュ上に同じデータが保持されている。
【０００８】
Ｉ：無効（Invalid)であり、キャッシュ上のデータは無効である。
【０００９】
このような従来のＭＥＳＩキャッシュプロトコルを用いたキュッシュ制御において、あるＣＰＵがキャッシュ装置にストアしたデータブロックに対して、他系のＣＰＵが参照するフェッチ要求を行った場合、主記憶ＭＳへのデータブロックの書込みを必要とし、その分、アクセスに時間がかかる。
【００１０】
図１０は、ＣＰＵ１００−１〜１００−３とキャッシュ装置１００−１〜１０２−３で構成されたマルチプロセッサシステムであり、ＣＰＵ１０２−２がフェッチ要求とストア要求を同じデータブロックに対し行った場合である。まず図１０（Ａ）（Ｂ）は、ＣＰＵ１００−２のフェッチ処理である。
【００１１】
まず図１０（Ａ）でＣＰＵ１００−２は自系のキャッシュ装置１０２−２にフェッチ要求を行うが、そのデータブロックの状態が無効Ｉなため、バスを介してデータブロックを変更Ｍの状態で保持しているキャッシュ装置１０２−１にフェッチ要求を行い、図１０（Ｂ）でデータブロックを取得してＣＰＵ１００−２に応答し、キャッシュ装置１０２−２のデータブロックの状態を無効Ｉから共有Ｓに変更する。
【００１２】
ここでデータ取得先のキャッシュ装置１０２−１のデータブロックの状態は、変更Ｍから共有Ｓに切替えられ、更に、フェッチ要求を受けたデータブロックの主記憶ＭＳライトが行われる。
【００１３】
図１０（Ｃ）−（Ｅ）は、次にＣＰＵ１００−２が同じデータブロックにストア要求を行った場合である。図１０（Ｃ）のように、ＣＰＵ１００−２が自系のキャッシュ装置１０２−２にストア要求を行うと、共有Ｓの状態で同じデータブロックを保持している他系のキャッシュ装置１０２−１にブロック変更要求を行い、図１０（Ｄ）のように、データブロックの状態を共有Ｓから無効Ｉに切替え、ＣＰＵ１００−２がキャッシュ装置のデータブロックに新たなデータをストアするストア処理を行う。
【００１４】
このストア処理が済むと、図１０（Ｅ）のように、キャッシュ装置１０２−２からストア完了がＣＰＵ１００−２に報告され、処理を終了する。
【００１５】
図１１は、ＣＰＵ１００−２とＣＰＵ１００−３が連続してフェッチ要求を同じデータブロックに対し行った場合である。まず図１１（Ａ）（Ｂ）のＣＰＵ１００−２のフェッチ処理は、図１０（Ａ）（Ｂ）と同じであり、キャッシュ装置１０２−１に対するフェッチ要求で主記憶ＭＳライトを必要とする。
【００１６】
図１１（Ｃ）（Ｄ）は、ＣＰＵ１００−３のフェッチ処理であり、他系のキャッシュ装置１０２−２へのフェッチ要求でデータブロックを取得し、ＣＰＵ１００−３に図１１（Ｄ）でフェッチ完了を通知する。
【００１７】
【発明が解決しようとする課題】
しかしながら、このような従来のＭＥＳＩキャッシュプロトコルでは、図１０（Ｂ）及び図１１（Ｂ）のように、他系のキャッシュ装置にフェッチ要求を行ってデータブロックを取得した際、他系のキャッシュ装置１０２−１で主記憶ＭＳライトが発生する。
【００１８】
また図１０（Ｃ）のように、自系と他系のキャッシュ装置１０２−１，１０２−２に共有Ｓの状態で保持されているデータブロックをＣＰＵ１００−２がストアする場合、他系のキャッシュ装置１００−１にブロック変更要求（状態変更要求）を行ってデータブロックの状態を共有Ｓから無効Ｉに切替える必要がある。
【００１９】
図１２（Ａ）は、従来のＭＥＳＩキャッシュプロトコルにおけるフェッチプロトコルの他の状態遷移図であり、この場合にも、変更Ｍの状態にあるデータブロックが他系からのフェッチ要求で無効Ｉに切替える際に、主記憶ＭＳライトが生ずる。
【００２０】
図１２（Ｂ）は、従来のＳＥＭＩキャッシュプロトコルにおけるフェッチプロトコルの他の状態遷移図である。この場合は、変更Ｍの状態にあるデータブロックが他系からのフェッチ要求で無効Ｉに切替えられると、その後にフェッチ要求があっても共有Ｓに切替えないようにし、これによって他系のフェッチ要求で変更Ｍから無効Ｉに切替えても主記憶ＭＳライトを不要にしている。
【００２１】
この図１０（Ａ）又は図１１（Ａ）のＭＥＳＩキャッシュプロトコルのフェッチ処理の際に発生する主記憶ＭＳライトを不要とするため、特開平６−１２４２４０（特願平４−２７５８２５）では、図１３のように、ＭＥＳＩキャッシュプロトコルに、共有変更Ｏ（Shared Modified ）を加えた５状態を示す構成とすることにより、フェッチ処理の際の主記憶ＭＳへの書き込みを不要にしている。尚、共有変更の符号Ｏは、Owner を表わす。
【００２２】
図１４は、ＣＰＵ１００−１〜１００−３とキャッシュ装置１０２−１〜１０２−３で構成されたマルチプロセッサシステムであり、ＣＰＵ１００がフェッチ要求とストア要求を同じデータブロックに対し行った場合である。まず図１４（Ａ）（Ｂ）は、ＣＰＵ１００−２のフェッチ処理である。
【００２３】
図１４（Ａ）でＣＰＵ１００−２は自系のキャッシュ装置０２−２にフェッチ要求を行うが、そのデータブロックが無効Ｉ状態なため、バスを介してデータブロックを変更Ｍの状態で保持しているキャッシュ装置１０２−１にフェッチ要求を行い、図１４（Ｂ）でデータブロックを取得してＣＰＵ１００−２に応答し、キャッシュ装置１０２−２のデータブロックの状態を無効Ｉから共有Ｓに変更する。
【００２４】
このときデータ取得先のキャッシュ装置１０２−１のデータブロックの状態は変更Ｍから共有変更Ｏに切替えられ、この場合、共有Ｓへの切替えとはならないため、フェッチ要求を受けたデータブロックの主記憶ＭＳライトは不要となる。
【００２５】
図１４（Ｃ）−（Ｆ）は、次にＣＰＵ１００−２が同じデータブロックにストア要求を行った場合である。図１４（Ｃ）のように、ＣＰＵ１００−２が自系のキャッシュ装置１０２−２にストア要求を行うと、共有変更Ｏの状態で同じデータブロックを保持している他系のキャッシュ装置１００−１にブロック変更要求（状態変更要求）を行う。
【００２６】
このため図１４（Ｄ）のように、データブロックの状態を共有変更Ｏから無効Ｉに切替え、ＣＰＵ１００−２がキャッシュ装置のデータブロックに新たなデータをストアするストア処理を行う。このストア処理が済むと図１４（Ｆ）のように、キャッシュ装置１０２−２からストア完了がＣＰＵ１００−２に報告され、処理を終了する。
【００２７】
図１５は、ＣＰＵ１００−２とＣＰＵ１００−３の順番に連続してフェッチ要求を同じデータブロックに対し行った場合である。まず図１５（Ａ）（Ｂ）のＣＰＵ１００−２のフェッチ処理は図１４（Ａ）（Ｂ）と同じであり、キャッシュ装置１０２−１に対するフェッチ要求で変更Ｍから共有変更Ｏに切替えるため、主記憶ＭＳライトは必要としない。
【００２８】
図１５（Ｃ）（Ｄ）は、続いて行われる他系のＣＰＵ１００−３のフェッチ処理であり、キャッシュ装置１０２−２へのフェッチ要求でデータブロックを取得し、ＣＰＵ１００−３に図１５（Ｄ）でフェッチ完了を通知する。
【００２９】
このように図１３の５状態をとるＳＥＭＩＯキャッシュプロトコルでは、新たに変更Ｍと共有Ｓの中間に位置する共有変更Ｏを設け、共有に段階性をもたせたことで、変更Ｍの状態にあるデータブロックに他系のフェッチ要求があっても、主記憶ＭＳライトは必要なくなる。
【００３０】
この５状態のキャッシュプロトコルで、主記憶ＭＳライトが必要になるのは、変更Ｍ又は共有変更Ｏの状態にあるデータブロックを、自系ＣＰＵのストア要求に伴ないリプレースする場合のみとなる。
【００３１】
しかしながら、この５状態をとるキャッシュプロトコルにあっても、図１４（Ｃ）のように、自系フェッチ処理に続いて他系ストア処理が行われた場合、共有変更Ｏの状態にある他系に対し無効Ｉに切替えるための状態変更要求が必要であり、この他系への状態変更要求を行っている分、ストア処理に時間がかかり、自系のフェッチ要求で取得したキャッシュ上のデータブロックに自系でストア処理を行う頻度は高いため、装置全体としてのアクセス性能に大きく影響する問題があった。
【００３２】
本発明は、キャッシュ上のデータブロックを管理する状態を細分化して他系への状態変更の要求を減してキャッシュへのアクセス性能を高めるようにしたキャッシュ装置及び制御方法を提供することを目的とする。
【００３３】
【課題を解決するための手段】
図１は本発明の原理説明図である。
【００３４】
本発明のキャッシュ装置は、キャッシュメモリとキャッシュコントローラで構成される。キャッシュメモリは、主記憶の一部のデータをキャッシュラインのブロック単位に保持すると共にキャッシュラインに保持したデータブロック状態を示す情報を保持する。
【００３５】
キャッシュコントローラは、データブロックの状態を、例えば図１（Ｂ）のフェッチプロコトルのように、
無効Ｉ（Ｉｎｖａｌｉｄ）；
共有Ｓ（Ｓｈａｒｅｄ）；
排他Ｅ（Ｅｘｃｌｕｓｉｖｅ）；
変更Ｍ（Ｍｏｄｉｆｉｅｄ）；
共有変更Ｏ（Ｓｈａｒｅｄ  Ｍｏｄｉｆｉｅｄ）；
書込可能Ｗ（Ｗｒｉｔａｂｌｅ  Ｍｏｄｉｆｉｅｄ）；
の６状態で表現してキャッシュメモリを制御する。本発明で付加した書込可能Ｗは、フェッチ要求があった場合に段階的に共有性を持たせるための状態である。
【００３６】
キャッシュ装置１４−２のキャッシュコントローラは、書込可能Ｗの状態を生成する自系フェッチ処理として、図１（Ａ）の▲１▼▲２▼のように、自系のＣＰＵ１２−２から無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、キャッシュ装置１４−２が他系のキャッシュ装置１４−１から変更Ｍの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから書込可能Ｗに変更し、同時にキャッシュ装置１４−１は、変更Ｍの状態にあるデータブロックに対し他系のキャッシュ装置１４−２からフェッチ要求を受けた場合、このデータブロックの状態を変更Ｍから無効Ｉに切替える。この条件によって本発明で追加した６番目の書込可能Ｗの状態が生成される。
【００３７】
またキャッシュ装置１４−２のキャッシュコントローラは、書込可能Ｗの状態を生成した後の自系ストア処理として、図１（Ａ）の▲３▼▲４▼のように、自系ＣＰＵ１２−２からの書込可能Ｗの状態にあるデータブロックへのストア要求に対し、このデータブロックにデータをストアした後に、他系への状態変更通知を一切必要とすることなく、データブロックの状態を書込可能Ｗから変更Ｍに切替える。
【００３８】
このような本発明のキャッシャ装置は、キャッシュ上で管理するデータブロックの状態を細分化し、これによって他系への状態変更要求を減らし、結果としてキャッシュ装置へのアクセスを速くすることを意図している。
【００３９】
ストアイン方式のキャッシュ装置を有するマルチプロセッサシステムにおいて、あるＣＰＵがストアを行ったデータブロックを他系のＣＰＵがフェッチする場合、他系のＣＰＵが同じデータブロックにストアを行う確率が高いことが知られている。また、他系のＣＰＵがそのデータブロックにストアを行わずにフェッチを行う場合、共有の状態が続くことも知られている。
【００４０】
このことは、複数のＣＰＵが同じデータブロックを参照する場合、そのブロックが単なる参照域であればストアは発生せず、ストアを行うような制御域であれば、他系のＣＰＵからもストアが行われる可能性があることからも推測可能である。
【００４１】
この性質を利用して本発明は、従来の５状態に更に書込可能Ｗという状態を設けた６状態構成とし、この書込可能Ｗのデータブロックは、他系と共有せずに単独でストアできるようにする。
【００４２】
このため、ＣＰＵがフェッチ要求に次いでストア要求する場合、５状態のキャッシュプロトコルでは、他系に状態変更要求を必要とするが、本発明の６状態のキャッシュプロトコルでは、他系への状態通知を必要とすることなくストア可能となる。
【００４３】
また６状態を表わすのに必要なビットは、５状態と同様３ビットで行うことができる。また、ストア要求が無く、他系からフェッチ要求があった場合も、要求回数を増やすことなく５状態のキャッシュプロトコルと同様に対応できる。
【００４４】
キャッシュ装置１４−２のキャッシュコントローラは、書込可能Ｗの状態を生成した後の自系フェッチ処理として、２つの異なった処理のいずれかを行う。
【００４５】
第１の自系フェッチ処理として、キャッシュ装置１４−２のキャッシュコントローラは、データブロックが無効Ｉの状態にある他系のキャッシュ装置１４−３から書込可能Ｗの状態にあるデータブロックにフェッチ要求を受けた場合、このデータブロックの状態を書込可能Ｗから共有変更Ｏに切替える（オーナの移動なし）。
【００４６】
またキャッシュ装置１４−３のキャッシュコントローラは、自系のＣＰＵ１２−３からの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置１４−２から書込可能Ｗの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有Ｓに切替える。
【００４７】
この場合、キャッシュ装置１４−２のキャッシュコントローラ１８は、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵ１２−２又は他系のキャッシュ装置１４−３からフェッチ要求を受けた場合は、共有変更Ｏの状態を維持し、オーナは移動しない。
【００４８】
また第２の自系フェッチ処理として、キャッシュ装置１４−２のキャッシュコントローラは、データブロックが無効Ｉの状態にある他系のキャッシュ装置１４−３から書込可能Ｗのデータブロックにフェッチ要求を受けた場合、このデータブロックの状態を書込可能Ｗから共有Ｓに切替える。
【００４９】
またキャッシュ装置１４−３のキャッシュコントローラは、自系のＣＰＵ１２−３からの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置１４−２から書込可能Ｗの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有変更Ｏに切替える（オーナの移動）。
【００５０】
この場合、キャッシュ装置１４−３のキャッシュコントローラ１８は、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵ１２−３からフェッチ要求を受けた場合は、共有変更Ｏの状態を維持し、共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置１４−２からフェッチ要求を受けた場合は、データブロックの状態を共有変更Ｏから共有Ｓに切替える（オーナの移動）。
【００５１】
更に、自系のプロセッサからの無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置から共有変更Ｏの状態にあるデータブロックを取得した場合、取得したデータブロックの状態を無効Ｉから共有変更Ｏに切替える。
【００５２】
この第１及び第２の自系フェッチ処理に対応した共有変更Ｏのストア処理として、キャッシュ装置１４−３又は１４−３のキャッシュコントローラ１８は、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵからストア要求を受けた場合は、このデータブロックにデータをストアした後に、データブロックの状態を共有変更Ｏから変更Ｍに切替える。また共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置からストア要求に基づく状態変更要求を受けた場合は、データブロックの状態を共有変更Ｏから無効Ｉに切替える。
【００５３】
本発明は、プロセッサ毎に設けられ、相互にバス接続されるキャッシュ装置を制御するキャッシュ制御方法を提供する。
【００５４】
この制御方法は、
キャッシュメモリに主記憶の一部のデータをキャッシュラインのブロック単位に保持すると共に前記キャッシュラインに保持したデータブロック状態を示す情報を保持し、
データブロックの状態を、無効Ｉ（Ｉｎｖａｌｉｄ）、共有Ｓ（Ｓｈａｒｅｄ）、排他Ｅ（Ｅｘｃｌｕｓｉｖｅ）、変更Ｍ（Ｍｏｄｉｆｉｅｄ）、共有変更Ｏ（Ｓｈａｒｅｄ    Ｍｏｄｉｆｉｅｄ）の他系に、フェッチ要求があった場合に段階的に共有性を持たせるために書込可能Ｗ（Ｗｒｉｔａｂｌｅ  Ｍｏｄｉｆｉｅｄ）の６状態で表現して前記キャッシュメモリを制御することを特徴とする。
【００５５】
また書込可能Ｗの状態の生成として、あるキャッシュ装置が自系のＣＰＵから無効Ｉの状態にあるデータブロックへのフェッチ要求に対し、他系のキャッシュ装置から変更Ｍの状態にあるデータブロックを取得した場合、要求元のキャッシュ装置は取得したデータブロックの状態を無効Ｉから書込可能Ｗに切替え、取得先の他系のキャッシュ装置はデータブロックの状態を変更Ｍから無効Ｉに切替える。
【００５６】
また書込可能Ｗの状態を生成した後のストア処理として、あるキャッシュ装置が自系のＣＰＵから書込可能Ｗの状態にあるデータブロックへのストア要求を受けた場合、このデータブロックにデータをストアした後にデータブロックの状態を書込可能Ｗから変更Ｍに切替える。
【００５７】
また書込可能Ｗの状態を生成した後の第１のフェッチ処理として、あるキャッシュ装置が書込可能Ｗの状態にあるデータブロックに、データブロックが無効Ｉの状態にある他系のキャッシュ装置からフェッチ要求を受けた場合、このデータブロックの状態を書込可能Ｗから共有変更Ｏに切替え、他系のキャッシュ装置は取得したデータブロックの状態を無効Ｉから共有Ｓに切替える。
【００５８】
ここで、第１のフェッチ処理で生成された共有変更Ｏの状態に対するフェッチ処理として、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵ又は他系のキャッシュ装置からフェッチ要求を受けた場合は、共有変更Ｏの状態を維持する。
【００５９】
また書込可能Ｗの状態を生成した後の第２のフェッチ処理として、あるキャッシュ装置が書込可能Ｗの状態にあるデータブロックに、データブロックが無効Ｉの状態にある他系のキャッシュ装置からフェッチ要求を受けた場合、このデータブロックの状態を書込可能Ｗから共有Ｓに切替え、他系のキャッシュ装置は取得したデータブロックの状態を無効Ｉから共有変更Ｏに切替える。
【００６０】
ここで第２のフェッチ処理で生成された共有変更Ｏの状態に対するフェッチ処理として、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵからフェッチ要求を受けた場合は、共有変更Ｏの状態を維持し、共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置からフェッチ要求を受けた場合は、データブロックの状態を共有変更Ｏから共有Ｓに切替える。
【００６１】
第１及び第２のフェッチ処理に対応したストア処理としては、共有変更Ｏの状態にあるデータブロックに自系のＣＰＵからストア要求を受けた場合は、データブロックにデータをストアした後に、データブロックの状態を共有変更Ｏから変更Ｍに切替える。また共有変更Ｏの状態にあるデータブロックに他系のキャッシュ装置からストア要求に基づく状態変更通知を受けた場合は、データブロックの状態を共有変更Ｏから無効Ｉに切替える。
【００６２】
【発明の実施の形態】
図２は、本発明のキャッシュ装置及び制御方法が適用されるマルチプロセッサシステムのブロック図である。
【００６３】
図２において、マルチプロセッサシステムは、複数のプロセッサモジュール１０−１，１０−２，・・・１０−ｎを持ち、プロセッサモジュール１０−１〜１０−ｎのそれぞれには、ＣＰＵ（プロセッサ）１２−１〜１２−ｎ及びキャッシュ装置１４−１〜１４−ｎが設けられている。キャッシュ装置１４−１〜１４−ｎはシステムバス１５により相互に接続され、更にシステムバス１５により主記憶１６と接続されている。
【００６４】
キャッシュ装置１４−１〜１４−ｎを接続するシステムバス１５としては、例えばスヌープバスを使用する。スヌープバスは、キャッシュ装置１４−１〜１４−ｎのいずれかでＣＰＵ１２−１〜１２−ｎからフェッチまたはストアの処理要求があった際に、この処理要求に該当するキャッシュラインに保持しているデータブロックの状態をスヌープ制御線の状態信号により直ちに取得できるバスである。
【００６５】
図３は本発明のキャッシュ装置１０の機能ブロック図である。キャッシュ装置１０は、キャッシュコントローラ１８とキャッシュメモリ２０で構成される。キャッシュメモリ２０は、複数のキャッシュライン２２単位にデータを保持しており、各キャッシュライン２２はタグ２４とデータブロック３０を含み、タグ２４は状態タグ２６とアドレスタグ２８を備える。
【００６６】
キャッシュメモリ２０の状態タグ２６につき、本発明にあっては、データブロックの状態を無効Ｉ、共有Ｓ、排他Ｅ、変更Ｍ及び共有変更Ｏの他に、自系のフェッチ要求があった場合に、段階的に共有性を持たせるための書込可能Ｗの６状態で表現してキャッシュメモリ２０を管理している。
【００６７】
キャッシュコントローラ１８にはキャッシュ制御管理部３２、状態管理部３４、プロセッサインタフェース３６、バスインタフェース３８が設けられる。また状態管理部３４にはフェッチプロトコル処理部４０とストアプロトコル処理部４２が設けられる。
【００６８】
キャッシュ制御管理部３２は、ＣＰＵ１２からフェッチ要求を受けると、キャッシュメモリ２０のタグ２４を参照し、要求アドレスとアドレス値の一致するアドレスタグ２８を持ったキャッシュライン２２を検索する。アドレスの一致するキャッシュラインが存在しない場合にはキャッシュミスとなり、主記憶１６もしくは他のキャッシュ装置からデータブロックを取得してＣＰＵ１２に提供する。
【００６９】
キャッシュ制御管理部３２は、要求アドレスに一致するアドレスのキャッシュラインが存在した場合には、そのキャッシュラインの状態タグ２６による無効Ｉ、共有Ｓ、排他Ｅ、変更Ｍ、共有変更Ｏまたは書込可能Ｗの状態に応じた処理を行う。
【００７０】
キャッシュ制御管理部３２は、ＣＰＵ１２からのストア要求に対し、キャッシュヒットであればキャッシュメモリ２０上の該当するキャッシュラインのデータブロックを更新するストア処理を行い、ミスヒットであればキャッシュメモリ２０上に新たなキャッシュラインを確保してデータを書き込むストア処理を行う。このとき他のキャッシュ装置に該当するデータブロックが存在する場合には、最新のデータブロックを他のキャッシュ装置から取得した後にデータを書き込むストア処理を行う。
【００７１】
このようなキャッシュ制御管理部３２によるＣＰＵ１２及びシステムバス１５を経由した他のキャッシュ装置からの処理要求に対し、状態管理部３４が処理要求を実行した後の該当するキャッシュライン上の状態タグ２６の状態遷移制御を行う。
【００７２】
状態管理部３４によるキャッシュコヒーレンスのための状態遷移制御として、本発明にあっては、図１３に示した従来のＭＥＳＩＯの５状態のキャッシュプロトコルに更に自系フェッチ要求があった場合に段階的に共有性を持たせるための書込可能Ｗを加えたＭＥＳＩＯＷの６状態のキャッシュプロトコルを適用している。
【００７３】
図４は、図３の状態管理部３４で使用されるＭＥＳＩＯＷの６状態キャッシュプロトコルの状態遷移の説明図である。即ち図４（Ａ）がフェッチプロトコル処理部４０で処理するフェッチ要求に対するＭＥＳＩＯＷフェッチプロトコルの状態遷移である。また図４（Ｂ）が図３のストアプロトコル処理部４２によるＭＥＳＩＯＷストアプロトコルの状態遷移である。
【００７４】
尚、図の実線の矢印は、その状態で自系ＣＰＵによるフェッチ要求又はストア要求があった場合の遷移であり、破線の矢印は、他系のキャッシュ装置でフェッチ要求又はストア要求が処理された場合の遷移である。
【００７５】
このよう図１４の本発明による６状態のキャッシュプロトコルの特徴は、図１３に示した５状態のキャッシュプロトコルに段階的に共有性を持たせるための書込可能Ｗの状態を付加している。
【００７６】
そこで図４（Ａ）の本発明による６状態のフェッチプロトコルと図１３（Ａ）の５状態のフェッチプロトコルを対比して見ると、新たに書込可能Ｗが加わっている。この書込可能Ｗの状態への遷移は、自系ＣＰＵからのフェッチ要求に対し自分のキャッシュメモリのデータブロックが無効Ｉで他のキャッシュ装置に該当するデータブロックが変更Ｍの状態で存在しているとき、他のキャッシュ装置から該当するデータブロックを取得して自系ＣＰＵに提供する。このような自系フェッチ処理が済んだ状態で
（１）取得先のキャッシュ装置のデータブロックの状態を変更Ｍから無効Ｉに切り替え、
（２）取得したデータブロックの状態を無効Ｉから本発明で新たに設けた書込可能Ｗに切り替える。
【００７７】
この書込可能Ｗを生成する遷移状態は、図４（Ａ）において無効Ｉから実線の矢印のように他系のデータブロックの状態が変更Ｍであることを条件に書込可能Ｗの状態に遷移している部分である。また他系キャッシュからフェッチ要求でデータを取得した後のデータブロックの状態については、他系キャッシュのデータブロックの状態がＭから破線のように無効Ｉに遷移している部分である。
【００７８】
ここで図４（Ａ）の６状態のフェッチプロトコルを図１３（Ａ）の５状態のフェッチプロトコルと対比して見ると、６状態のフェッチプロトコルにあっては新たに書込可能Ｗの状態が付加されたことで、共有変更Ｏへの遷移は、この追加した書込可能Ｗを経由して行われることになる。
【００７９】
図４（Ａ）のフェッチプロトコルに従ってキャッシュラインのデータブロックが書込可能Ｗとなった場合には、図４（Ｂ）のストアプロトコルに従った自系ＣＰＵからのストア要求に対し、他のキャッシュ装置に対する状態変更要求を必要とすることなく、書込可能Ｗ状態にあるキャッシュ装置のみでストア処理を完了することができる。
【００８０】
図４（Ｂ）のストアプロトコルにあっても、図１３（Ｂ）に示した５状態のストアプロトコルに新たに段階的に共有性を持たせるための書込可能Ｗが追加されている。このため図４（Ａ）の６状態のフェッチプロトコルに従ってキャッシュラインのデータブロックが書込可能Ｗとなった後は、自系ＣＰＵのストア要求が完了すると、そのキャッシュラインのデータブロックの状態は書込可能Ｗから変更Ｍに遷移する。
【００８１】
また書込可能Ｗとなっているデータブロックが他系のキャッシュ装置でのストア要求の対象となった場合には、破線のように書込可能Ｗから無効Ｉに遷移する。
【００８２】
更に無効Ｉの状態で他系のキャッシュ装置からストア対象とするデータブロックを取得する際に、他系のデータブロックの状態が書込可能Ｗまたは共有変更Ｏの状態の場合には、他系キャッシュからデータブロックを取得してストア処理を完了した状態で無効Ｉから変更Ｍに遷移させる。これ以外の点は図１３（Ｂ）の５状態のストアプロトコルの状態遷移と同じである。
【００８３】
図５は、図２に示したマルチプロセッサシステムの中の３つのプロセッサモジュールに設けているＣＰＵ１２−１，１２−２，１２−３及びそれぞれのキャッシュ装置１４−１，１４−２．１４−３の３台ずつを例にとって、本発明のＳＥＭＩＯＷの６状態キャッシュプロトコルについて、自系フェッチ要求によって書込可能Ｗへの状態遷移とその後の自系ストア処理による状態遷移を示した説明図である。
【００８４】
図５（Ａ）は、真ん中に位置するＣＰＵ１２−２がキャッシュ装置１４−２に対しフェッチ要求を行ったときの該当データブロックの状態であり、キャッシュ装置１４−１が変更Ｍ、キャッシュ装置１４−２，１４−３がそれぞれ無効Ｉとなっている。
【００８５】
以下のキャッシュ処理の説明にあっては、中央に位置するＣＰＵ１２−２に着目しており、ＣＰＵ１２−２からのフェッチ要求またはストア要求を自系フェッチ要求または自系ストア要求とし、ＣＰＵ１２−１またはＣＰＵ１２−３からのフェッチ要求またはストア要求は他系フェッチ要求または他系ストア要求と呼ぶ。
【００８６】
図５（Ａ）は、ＣＰＵ１２−２による自系ＣＰＵフェッチ要求であり、このフェッチ要求を受けたキャッシュ装置１４−２は該当するデータブロックの状態が無効Ｉであることから、該当するキャッシュラインを変更Ｍとして保持しているキャッシュ装置１４−１に対しフェッチ要求を行う。
【００８７】
続いて図５（Ｂ）のように、キャッシュ装置１４−２からフェッチ要求を受けたキャッシュ装置１４−１は、該当するデータブロックを要求元に転送し、これをＣＰＵ１２−２に応答することでフェッチが完了する。このフェッチ完了によって取得先のキャッシュ装置１４−１のデータブロックは変更Ｍから無効Ｉに切り替えられ、データブロックを取得したキャッシュ装置１４−２にあっては、無効Ｉから本発明で新たに追加した書込可能Ｗに切り替える。
【００８８】
ここで図９（Ａ）に示した従来の４状態のフェッチプロトコルでは、キャッシュ装置１４−１の状態Ｍから遷移する際に主記憶ＭＳの書込みを必要としているが、本発明の６状態キャッシュプロトコルにあっては、図１３の５状態キャッシュプロトコルと同様、変更Ｍからの遷移について主記憶書込み即ちＭＳライトを必要としない。
【００８９】
次に図５（Ｃ）のように、同じＣＰＵ１２−２がフェッチ要求に続いて同じデータブロックに対しストア要求を行ったとする。このときストア要求の対象となったデータブロックの状態は書込可能Ｗとなっており、他のキャッシュ装置１４−１，１４−３にあっては該当するデータブロックは共に無効Ｉとなっている。
【００９０】
このため、他のキャッシュ装置１４−１，１４−３に対する状態変更通知を必要とすることなく、キャッシュ装置１４−２に単独でＣＰＵ１２−２からのデータを書き込むストア処理を行い、図５（Ｄ）のストア処理の完了により、キャッシュ装置１４−２のストア済みのデータブロックは書込可能Ｗから変更Ｍに切り替えられる。
【００９１】
これに対し図１４（Ｃ）〜（Ｆ）に示した５状態のキャッシュプロトコルにおける自系フェッチ要求後の自系ストア要求にあっては、自系及び他系の該当するデータブロックの状態が共に共有Ｓとなっているために、ストア要求に対し他のキャッシュ装置に対し状態変更要求（ブロック変更要求）を行わなければならない。
【００９２】
この結果、本発明の６状態キャッシュプロトコルにあっては、自系フェッチに続く自系ストア処理につき、データブロックが書込可能Ｗとなっているために他のキャッシュ装置に対する状態変更通知を必要とせず、その分キャッシュのアクセスを高速にすることができる。
【００９３】
図６は、図５と同様、３つのＣＰＵ１２−１〜１２−３及びキャッシュ装置１４−１〜１４−３を例にとって、書込可能Ｗに切り替わる自系フェッチ要求に続き他系フェッチ要求が行われた場合のキャッシュ処理の説明図である。
【００９４】
図６（Ａ）（Ｂ）は、図５（Ａ）（Ｂ）と同じであり、ＣＰＵ１２−２のキャッシュ装置１４−２に対する自系のフェッチ要求に対し他のキャッシュ装置１４−１からデータブロックを取得して応答することで、取得先のキャッシュ装置１４−１のデータブロックは変更Ｍから無効Ｉに切り替わり、要求元のキャッシュ装置１４−２のデータブロックは無効Ｉから書込可能Ｗに切り替わっている。
【００９５】
次に図６（Ｃ）のように、他のＣＰＵ１２−３でキャッシュ装置１４−３にフェッチ要求が行われ、該当するデータブロックは無効Ｉであることから、書込可能Ｗの状態でデータブロックを保持しているキャッシュ装置１４−２に対しフェッチ要求が行われる。
【００９６】
このフェッチ要求に対し、図６（Ｄ）のようにキャッシュ装置１４−２から要求元のキャッシュ装置１４−３に該当するデータブロックが送られ、ＣＰＵ１２−３に提供されてフェッチを完了する。
【００９７】
このフェッチの完了で、データブロックの転送元のキャッシュ装置１４−２にあっては、書込可能Ｗから共有変更Ｏに切り替える。またデータブロックを取得した要求元のキャッシュ装置１４−３にあっては、無効Ｉから共有Ｓに遷移する。
【００９８】
この自系フェッチ後の他系フェッチによる処理は、図１５に示した従来の５状態のキャッシュプロトコルの場合と同じ手順であり、本発明で新たに書込可能Ｗを加えた６状態としても、自系フェッチに続く他系フェッチのキャッシュ処理の手順は増加せずに同じにできる。
【００９９】
図７は、図４（Ｂ）に示した本発明による６状態キャッシュプロトコルにおけるフェッチプロトコルの他の実施形態の状態遷移の説明図である。この６状態のフェッチプロトコルの状態遷移にあっては、自系フェッチに続いて他系フェッチが行われた場合の書込可能Ｗの状態にあるキャッシュデータの遷移を、図４（Ａ）のフェッチプロトコルでは図６（Ｄ）のように共有変更Ｏとしていたが、この実施形態にあっては共有Ｓとし、フェッチ要求元に転送したデータブロックについて共有変更Ｏとするようにしたことを特徴とする。
【０１００】
即ち図４（Ａ）のフェッチプロトコルにあっては、自系フェッチ要求、他系フェッチ要求と続いた場合、書込可能Ｗから共有変更Ｏに遷移させているが、図７のフェッチプロトコルにあっては書込可能Ｗから共有Ｓに遷移させ、逆に書込可能Ｗのキャッシュ装置からデータブロックを取得した要求元を無効Ｉから共有変更Ｏに遷移させている。
【０１０１】
図８は、図７のフェッチプロトコルに従った自系フェッチに続いて他系フェッチを処理した場合のキャッシュ処理の説明図である。図８（Ａ）（Ｂ）の自系フェッチ処理は図６（Ａ）（Ｂ）と同じであり、図８（Ｃ）（Ｄ）の他系フェッチ処理が図６（Ｃ）（Ｄ）と異なる。
【０１０２】
図６（Ｄ）では要求先のキャッシュ装置１４−２の状態を書込可能Ｗから共有変更Ｏとし、要求元のキャッシュ装置１４−３の状態を無効Ｉから共有Ｓとしていたものを、図８（Ｃ）（Ｄ）では、逆に要求元のキャッシュ装置１４−２の書込可能Ｗを共有Ｓとし、要求元のキャッシュ装置１４−３の無効Ｉを共有変更Ｏとしている。
【０１０３】
即ち図４（Ａ）のフェッチプロトコルにあっては、図６（Ｄ）のように他系フェッチ要求が続く限り、要求先となるキャッシュ装置１４−２は共有変更Ｏの状態を継続することとなり、他系フェッチが続いても共有変更Ｏとなっているキャッシュ装置は固定されるため、他系フェッチ要求に対し他のキャッシュ装置に対する状態変更要求が少なくできる。
【０１０４】
これに対し図７のフェッチプロトコルにあっては、図８（Ｄ）のように他系フェッチ要求が続く場合、要求元に次々と共有変更０が移動していくこととなり、共有変更の特定のキャッシュ装置に固定している場合に比べストア要求を受ける機会が少ないため、共有状態を長く続けたい場合に有効なプロトコルである。
【０１０５】
もちろん、図４（Ａ）のフェッチプロトコルとするか図７のフェッチプロトコルにするかは必要に応じて適宜に設定することができる。例えば図４（Ａ）のフェッチプロトコルと図７のフェッチプロトコルの両方を備え、運用テストやシミュレーション等によりアクセスの早い方のフェッチプロトコルを選択してダイナミックに使用することもできる。
【０１０６】
尚、本発明は、その目的と利点を損なわない適宜の変形を含む。また本発明は上記の実施形態に示した数値による限定は受けない。
【０１０７】
【発明の効果】
以上説明してきたように本発明によれば、データブロックの状態を無効、共有、排他、変更、共有変更に加えて、フェッチ要求があった場合に段階的に共有性を持たせるための書込可能を加えた６状態で表現してキャッシュ制御を行うようにしたため、自系フェッチ要求で他のキャッシュ装置の変更状態にあるデータブロックを取得して書込可能状態とした後に自系ストア要求を受けた場合、他のキャッシュ装置に対する状態変更要求を必要とすることなく、書込可能状態にあるキャッシュ装置単独でストア処理を完了することができ、これによってキャッシュアクセスを更に高速にすることができる。
【０１０８】
また、新たに書込可能を加えた６状態としていても、データブロックが書込可能に遷移する自系フェッチ要求に続いて他のＣＰＵからの他系フェッチ要求があった場合にも、この他系フェッチ要求に対する動作手順の回数を増やすことなく対応することができ、６状態としたことによるアクセス性能の低下は起きない。
【図面の簡単な説明】
【図１】本発明の原理説明図
【図２】本発明が適用されるマルチプロセッサシステムのブロック図
【図３】本発明のキャッシュ装置の機能構成のブロック図
【図４】本発明の６状態キャッシュプロトコルの状態遷移の説明図
【図５】自系フェッチによる書込可能Ｗの状態の生成に続いて自系ストアを行った場合の本発明のキャッシュ処理の説明図
【図６】自系フェッチによる書込可能Ｗの状態の生成に続いて他系フェッチを行った場合の本発明のキャッシュ処理の説明図
【図７】本発明の６状態キャッシュプロトコルのフェッチ要求に対する他の状態遷移の説明図
【図８】自系フェッチによる書込可能Ｗの状態の生成に続いて図７の状態遷移に従って自系ストアを行った場合の本発明のキャッシュ処理の説明図
【図９】従来の４状態キャッシュプロトコルの状態遷移の説明図
【図１０】従来の４状態キャッシュプロトコルで自系フェッチに続いて自系ストアを行った場合のキャッシュ処理の説明図
【図１１】従来の４状態キャッシュプロトコルで自系フェッチに続いて他系フェッチを行った場合のキャッシュ処理の説明図
【図１２】従来の４状態キャッシュプロトコルにおけるフェッチ要求に対する他の状態遷移の説明図
【図１３】従来の５状態キャッシュプロトコルの状態遷移の説明図
【図１４】従来の５状態キャッシュプロトコルで自系フェッチに続いて自系ストアを行った場合のキャッシュ処理の説明図
【図１５】従来の５状態キャッシュプロトコルで自系フェッチに続いて他系フェッチを行った場合のキャッシュ処理の説明図
【符号の説明】
１０，１０−１〜１０−ｎ：プロセッサモジュール
１２，１２−１〜１２−ｎ：ＣＰＵ（プロセッサ）
１４，１４−１〜１４−ｎ：キャッシュ装置
１５：システムバス
１６：主記憶装置（ＭＳ）
１８：キャッシュコントローラ
２０：キャッシュメモリ
２２：キャッシュライン
２４：タグ
２６：状態
２８：アドレス
３０：データブロック
３２：キャシュ制御管理部
３４：状態管理部
３６：プロセッサＩＦ
３８：バスＩＦ
４０：フェッチプロトコル処理部
４２：ストアプロトコル処理部
【図１】
0003897218.tif 000002
【図２】
0003897218.tif 000003
【図３】
0003897218.tif 000004
【図４】
0003897218.tif 000005
【図５】
0003897218.tif 000006
【図６】
0003897218.tif 000007
【図７】
0003897218.tif 000008
【図８】
0003897218.tif 000009
【図９】
0003897218.tif 000010
【図１０】
0003897218.tif 000011
【図１１】
0003897218.tif 000012
【図１２】
0003897218.tif 000013
【図１３】
0003897218.tif 000014
【図１４】
0003897218.tif 000015
【図１５】
0003897218.tif 000016