(57)【特許請求の範囲】
【請求項１】
ライトバック型キャッシュが実装された複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるキャッシュコヒーレンシ制御装置であって、
前記複数のプロセッサのうちのいずれかのプロセッサからメインメモリに対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスのデータに対して他のプロセッサによりリードが実行されていないことを条件に、該リードリクエストに要求されたリードを許可するリード管理部と、
前記複数のプロセッサのうちのいずれかのプロセッサによりメインメモリからデータのリードが実行されている際に、前記データが前記プロセッサに出力されるまで該データのキャッシュラインアドレスを保持して前記リード管理部に供するキャッシュラインアドレス情報保持部と、
前記キャッシュラインアドレス情報保持部に保持されたキャッシュラインアドレスのデータが当該プロセッサへ出力されることに同期して、データのリードに関連するリクエストの発行を一時停止させるペンディング指示を前記プロセッサ以外のプロセッサに行うペンディング指示部とを備えることを特徴とするキャッシュコヒーレンシ制御装置。
【請求項２】
データのリードに関連するリクエストは、メインメモリへのリードリクエストと他のプロセッサへのスヌープリクエストを含むことを特徴とする請求項１に記載のキャッシュコヒーレンシ制御装置。
【請求項３】
前記ペンディング指示部は、前記キャッシュラインアドレス情報保持部に保持されたキャッシュラインアドレスについてリードのリトライを行うプロセッサがあるときに前記ペンディング指示を行うことを特徴とする請求項１または２に記載のキャッシュコヒーレンシ制御装置。
【請求項４】
前記リトライを行うプロセッサの数をカウントするリトライ数カウンタをさらに備え、
前記ペンディング指示部は、前記リトライ数カウンタのカウント値が所定の閾値を超えたことを条件に前記ペンディング指示を行うことを特徴とする請求項３に記載のキャッシュコヒーレンシ制御装置。
【請求項５】
前記ペンディング指示部は、前記リトライを行うプロセッサに対して前記ペンディング指示を行うことを特徴とする請求項３または４に記載のキャッシュコヒーレンシ制御装置。
【請求項６】
前記キャッシュラインアドレス情報保持部が保持する前記キャッシュラインアドレスについてメインメモリに対するリードリクエストを受信したとき、リクエスト元のプロセッサに対して該リードのリトライを指示するリトライ指示部をさらに備えることを特徴とする請求項１から５のいずれか１項に記載のキャッシュコヒーレンシ制御装置。
【請求項７】
前記ペンディング指示部は、前記キャッシュラインアドレスが含まれるペンディング指示をし、該キャッシュラインアドレスのデータのリードに関連するリクエストの発行を一時停止させることを特徴とする請求項１から６のいずれか１項に記載のキャッシュコヒーレンシ制御装置。
【請求項８】
複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおける前記プロセッサであって、
ライトバック型キャッシュと、
キャッシュミスしたときに対象データのリードに関連するリクエストを発行するリクエスト発行部と、
リードに関連するリクエストの発行の一時停止を要求するペンディング指示を受信した際に、前記リクエスト発行部がリードに関連するリクエストの発行を所定期間停止するように制御を行うリクエスト制御部とを備えることを特徴とするプロセッサ。
【請求項９】
リードに関連するリクエストは、メインメモリへのリードリクエストと他のプロセッサへのスヌープリクエストを含むことを特徴とする請求項８に記載のプロセッサ。
【請求項１０】
前記リクエスト発行部は、前記メインメモリへのリードリクエストが拒否されたときに、該リードのリトライを行い、
前記リクエスト制御部は、前記リトライ中に前記ペンディング指示を受信した際に前記制御を行うことを特徴とする請求項８または９に記載のプロセッサ。
【請求項１１】
前記ペンディング指示は、リードに関連するリクエストの発行の一時停止が要求されるキャッシュラインアドレスが含まれており、
前記リクエスト制御部は、該キャッシュラインアドレスに対するリードに関連するリクエストの発行について前記制御を行うことを特徴とする請求項８から１０のいずれか１項に記載のプロセッサ。
【請求項１２】
ライトバック型キャッシュが実装された複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるキャッシュコヒーレンシ制御方法であって、
前記複数のプロセッサのうちのいずれかのプロセッサによりメインメモリからデータのリードが実行されている際に、前記データが前記プロセッサに出力されるまで該データのキャッシュラインアドレスを保持し、
前記複数のプロセッサのうちのいずれかのプロセッサからメインメモリに対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスが保持されていないことを条件に、該リードリクエストに要求されたリードを許可し、
保持されたキャッシュラインアドレスのデータが当該プロセッサへ出力されることに同期して、データのリードに関連するリクエストの発行を一時停止させるペンディング指示を前記プロセッサ以外のプロセッサに行うことを特徴とするキャッシュコヒーレンシ制御方法。
【請求項１３】
データのリードに関連するリクエストは、メインメモリへのリードリクエストと他のプロセッサへのスヌープリクエストを含むことを特徴とする請求項１２に記載のキャッシュコヒーレンシ制御方法。
【請求項１４】
保持中の前記キャッシュラインアドレスについてリードのリトライを行うプロセッサがあるときに前記ペンディング指示を行うことを特徴とする請求項１２または１３に記載のキャッシュコヒーレンシ制御方法。
【請求項１５】
前記リトライを行うプロセッサの数をリトライ数としてカウントし、
前記リトライ数が所定の閾値を超えたことを条件に前記ペンディング指示を行うことを特徴とする請求項１４に記載のキャッシュコヒーレンシ制御方法。
【請求項１６】
前記リトライを行うプロセッサに対して前記ペンディング指示を行うことを特徴とする請求項１４または１５に記載のキャッシュコヒーレンシ制御方法。
【請求項１７】
保持中の前記キャッシュラインアドレスについてメインメモリに対するリードリクエストを受信したとき、リクエスト元のプロセッサに対して該リードのリトライを指示するリトライ指示をさらに行うことを特徴とする請求項１２から１６のいずれか１項に記載のキャッシュコヒーレンシ制御方法。
【請求項１８】
前記キャッシュラインアドレスが含まれる前記ペンディング指示を行い、該キャッシュラインアドレスのデータのリードに関連するリクエストの発行を一時停止させることを特徴とする請求項１２から１７のいずれか１項に記載のキャッシュコヒーレンシ制御方法。
【請求項１９】
ライトバック型キャッシュが実装された複数のプロセッサと、
前記複数のプロセッサにより共有されるメインメモリと、
前記複数のプロセッサのキャッシュコヒーレンシを制御するキャッシュコヒーレンシ制御装置とを備え、
前記キャッシュコヒーレンシ制御装置は、
前記複数のプロセッサのうちのいずれかのプロセッサからメインメモリに対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスのデータに対して他のプロセッサによりリードが実行されていないことを条件に、該リードリクエストに要求されたリードを許可するリード管理部と、
前記複数のプロセッサのうちのいずれかのプロセッサによりメインメモリからデータのリードが実行されている際に、前記データが前記プロセッサに出力されるまで該データのキャッシュラインアドレスを保持して前記リード管理部に供するキャッシュラインアドレス情報保持部と、
前記キャッシュラインアドレス情報保持部に保持されたキャッシュラインアドレスのデータが当該プロセッサへ出力されることに同期して、データのリードに関連するリクエストの発行を一時停止させるペンディング指示を前記プロセッサ以外のプロセッサに行うペンディング指示部とを有し、
前記複数のプロセッサは、前記ペンディング指示を受信した際に、データのリードに関連するリクエストの発行を所定期間停止することを特徴とする情報処理装置。
【請求項２０】
データのリードに関連するリクエストは、メインメモリへのリードリクエストと他のプロセッサへのスヌープリクエストを含むことを特徴とする請求項１９に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるキャッシュコヒーレンシ制御技術に関する。
【背景技術】
【０００２】
複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおいて、キャッシュのコヒーレンシ（一貫性）を保証する手法として、スヌープ方式が知られている。スヌープ方式では、プロセッサのキャッシュ間でハンドシェイクを行うことで、各プロセッサのキャッシュは自身や他のプロセッサのキャッシュのライン更新状態を把握し、どのキャッシュに最新のデータが存在するかを知り、必要なときに最新のデータを取得できるようにラインのパージなどを行う。
【０００３】
通常のプロセッサでは、メインメモリへのアクセスとしてキャッシュ経由のアクセスとメインメモリへのダイレクトアクセスの両方がサポートされている。キャッシュ経由の場合は、プロセッサに実装されたキャッシュがライトスルー方式で動作するか、ライトバック方式で動作するかによって処理は異なる。
【０００４】
ライトスルー方式は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）がメモリ書込みを行ったら、更新データはキャッシュにストアされると同時にメインメモリに書き戻される方式である。
【０００５】
ライトバック方式は、ＣＰＵがメモリ書込を行っても、条件が整わない限り更新データはキャッシュに留まり、メインメモリへの書戻しがなされない方式である。書き戻す条件は、例えば対象エントリにウェイ数以上のフレームアドレスのリード／ライトが行われる、他のプロセッサが対象エントリに対してアクセス要求があったなどである。
【０００６】
ライトバック方式のキャッシュが実装されたプロセッサにより構成されたマルチプロセッサシステムにおいて、スヌープ方式では無効型プロトコルが用いられる。無効型プロトコルでは、複数のキャッシュから参照があるアドレスに対してあるキャッシュが更新を行う場合、そのアドレスがダーティであるとして参照中の全キャッシュの当該ラインを無効化する。これにより、更新されたラインがありながら他のキャッシュで古いデータをキャッシングしている状態が無くなり、キャッシュコヒーレンシが保たれる。無効型プロトコルには、ＭＥＳＩプロトコルや、ＭＯＳＩプロトコルなどがある。
【０００７】
例えばＭＥＳＩプロトコルの場合、各プロセッサ内は、キャッシュを下記４つの状態に定義して管理する。
【０００８】
状態１：対象データは無い状態。この状態は、以下Ｉ（Ｉｎｖａｌｉｄ）状態ともいう。
状態２：対象データはあり、メインメモリ内のデータと同一である。さらに、他のプロセッサのキャッシュにも登録されている。この状態は、以下Ｓ（Ｓｈａｒｅｄ−Ｕｎｍｏｄｉｆｉｅｄ）状態ともいう。
状態３：対象データは、自身のキャッシュにのみ登録されており、メインメモリ内のデータと同一である。この状態は、以下Ｅ（Ｅｘｃｌｕｓｉｖｅ−Ｍｏｄｉｆｉｅｄ）状態ともいう。
状態４：対象データは、自身のキャッシュにのみ登録されており、メインメモリ内のデータと異なる。この状態では、キャッシュに登録されたデータは、メインメモリにライトバックされていない最新データとなる。なお、この状態を、以下Ｍ（Ｅｘｃｌｕｓｉｖｅ−Ｍｏｄｉｆｉｅｄ）状態ともいう。
【０００９】
このようなマルチプロセッサシステムにおいて、同一のキャッシュラインアドレス（以下単にアドレスともいう）のデータに対して複数のプロセッサが近接したタイミングでリードする場合、キャッシュコヒーレンシに問題が生じる可能性がある。図９に示すマルチプロセッサシステム１を例に説明する。
【００１０】
図９に示すマルチプロセッサシステム１は、複数（図示の例では４つ）のＣＰＵ１０〜４０と、共有バス５０と、メインメモリ７０を備える。
【００１１】
ＣＰＵ１０〜４０は、共有バス５０に接続され、共有バス５０を介して互いに通信することや、メインメモリ７０へアクセスすることができる。また、ＣＰＵ１０〜４０には、キャッシュ１２、キャッシュ２２、キャッシュ３２、キャッシュ４２がそれぞれ実装されており、これらのキャッシュは、ライトバック方式のものである。
【００１２】
例えば、ＣＰＵ１０がメインメモリ７０のアドレス（アドレスＡとする）のデータをリードするときに、自身のキャッシュ１２にそのデータが無ければキャッシュミスとなる。この場合、ＣＰＵ１０は、メインメモリ７０にリードリクエストを出力すると共に、アドレスＡについてのスヌープリクエストを出力する。このスヌープリクエストは、共有バス５０に接続されたすべての他のＣＰＵに受信される。スヌープリクエストを受信したＣＰＵは、自身のキャッシュの状態を参照し、アドレスＡのデータが自身のキャッシュにありすなわちキャッシュヒットすれば、ＣＰＵ１０に当該データを転送する。なお、キャッシュヒットしたＣＰＵのキャッシュの状態が上記状態４（Ｍ状態）であれば、当該ＣＰＵは、このデータをメインメモリ７０へのライトバックも実施する。
【００１３】
上記状態３（Ｅ状態）とＭ状態のキャッシュがデータを他のＣＰＵに出力した、当該ＣＰＵのキャッシュは、上記状態１（Ｉ状態）と状態２（Ｓ状態）のいずれに遷移するかは、システムの設計によって異なる。
通常、ＣＰＵがデータをリードするのは、このデータを更新するためである。Ｅ状態とＭ状態のキャッシュがデータを他のプロセッサに出力した後にＳ状態に遷移するのでは、該データを受け取ったＣＰＵが更新を行ってキャッシュにストアするときに、他のＣＰＵの当該キャッシュラインを無効にするためのリクエストを出す必要がある。そのため、バス上のトラフィックが多く、システムの効率が低下する。したがって、通常のマルチプロセッサシステムにおいて、Ｅ状態およびＭ状態のキャッシュがデータを出力した後にＩ状態に遷移するようになっている。
【００１４】
また、ＣＰＵ１０は、キャッシュミスをし、当該アドレス（アドレスＢとする）のリードリクエストをメインメモリ７０に出力すると共に、スヌープリクエストを出力した際に、ＣＰＵ１０以外の各ＣＰＵもキャッシュミスした場合、ＣＰＵ１０は、メインメモリ７０から当該データを読み出す処理を実行する。この処理の実行中に、ＣＰＵ２０がアドレスＢのデータをリードしようとして、キャッシュミスした場合を考える。
【００１５】
この場合、ＣＰＵ２０は、メインメモリ７０にアドレスＢのリードリクエストを出力すると共に、スヌープリクエストを出力する。ＣＰＵ１０は、ＣＰＵ２０からのスヌープリクエストを受信すると、自身のキャッシュに当該データがまだ無いため、キャッシュミスし、その旨を示すメッセージをＣＰＵ２０に出力する。また、ＣＰＵ３０とＣＰＵ４０もキャッシュミスし、ＣＰＵ２０にその旨を通知したとする。
【００１６】
ＣＰＵ１０はリード動作を続き、メインメモリ７０からアドレスＢのデータを受信する。また、リード中に、ＣＰＵ２０、ＣＰＵ３０、ＣＰＵ４０が共にアドレスＢについてキャッシュミスしているので、ＣＰＵ１０は、アドレスＢのデータをＥ状態でキャッシュに登録する。
【００１７】
ところで、ＣＰＵ２０もリード動作を続き、メインメモリ７０からアドレスＢのデータを受信する。また、ＣＰＵ２０のスヌープリクエストについて、ＣＰＵ１０、ＣＰＵ３０、ＣＰＵ４０が共にキャッシュミスし、その旨を示すメッセージをＣＰＵ２０に出しているので、ＣＰＵ２０も、アドレスＢのデータをＥ状態で登録する。
【００１８】
その結果、マルチプロセッサシステム１において、２つのプロセッサのキャッシュが同一のアドレスＢについてデータをＥ状態で保持してしまう。これでは、アドレスＢについて、キャッシュコヒーレンシは破綻することになる。
【００１９】
これは、ＣＰＵ１０がメインメモリからデータを読み出している最中に他のＣＰＵからのスヌープリクエストに「キャッシュミス」の応答をすることに起因する。特許文献１には、この問題を解決するための手法が開示されている（特許文献１における「００６２」〜「００６６」）。
【００２０】
この手法では、各プロセッサを接続する相互結合網（特許文献１における相互結合網Ｂ）にキャッシュコヒーレンシの制御機能が設けられていると共に、各プロセッサは、あるアドレスのデータをメインメモリからリードしている最中に他のプロセッサから当該アドレスのデータのスヌープリクエストを受信した際に、リクエストの中止と再実行を要求する「ＲＴＹ」を相互結合網に出力するようになっている。そして、相互結合網が受信した「ＲＴＹ」をブロードキャストすることにより、リクエスト元のプロセッサは「ＲＴＹ」を受取り、リードリクエストおよびスヌープリクエストをリトライする。
【００２１】
こうすることにより、メインメモリからデータを読み出している最中のプロセッサが「キャッシュミス」の返答をすることを防ぐことができ、キャッシュコヒーレンシは保たれる。
【特許文献１】特開２００３−１５０５７３号公報
【発明の開示】
【発明が解決しようとする課題】
【００２２】
ここで、図９に示すマルチプロセッサシステム１に特許文献１の手法を適用した際に、同一のアドレスに複数のプロセッサが近接したタイミングでリードした場合の問題点について考える。
【００２３】
図１０は、この場合のタイミングチャートの例を示す。図１０において、ＳＲ、ＲＲ、ＲＤ、ＲＴＹは、それぞれ「スヌープリクエスト」、「リードリクエスト」、「リードデータ」、「リトライ要求」を示す。Ｔ１、Ｔ２、・・・は、タイミングを示す。なお、分かりやすいように、スヌープリクエストについて、ＣＰＵ１０と関係するもののみを示している。同様に、ＣＰＵ１０がメインメモリ７０からデータをリードいる最中に他のＣＰＵからスヌープリクエストを受信した際に、相互結合網に出力するＲＴＹも省略している。
【００２４】
図１０に示す例では、Ｔ０において、ＣＰＵ１０は、対象アドレス（アドレスＣとする）についてキャッシュミスしたため、メインメモリ７０にリードリクエストＲＲ１０を出力すると共に、スヌープリクエストを出力する（ＳＲ１０２、ＳＲ１０３、ＳＲ１０４）。ＣＰＵ２０〜４０も、キャッシュミスし、スヌープリクエストに返答しないとする。
【００２５】
Ｔ１において、ＣＰＵ１０からのリードリクエストＲＲ１０は、相互結合網によりメインメモリ７０に発行される。
【００２６】
Ｔ２において、ＣＰＵ２０も、アドレスＣについてキャッシュミスし、メインメモリ７０にリードリクエストＲＲ２０を出力すると共に、スヌープリクエストを出力する。これにより、Ｔ３において、ＣＰＵ１０は、スヌープリクエストＳＲ２０１を受信し、相互結合網は、リードリクエストＲＲ２０を受信する。
【００２７】
ＣＰＵ１０がアドレスＣのデータをメインメモリ７０からリードする処理中であるので、Ｔ４において、相互結合網は、ＣＰＵ２０に対してリトライ要求ＲＴＹ２０を出力する。
【００２８】
その後、アドレスＣについてキャッシュミスしたＣＰＵ３０とＣＰＵ４０も、相互結合網からリトライ要求ＲＴＹ３０（Ｔ８）とＲＴＹ４０（Ｔ１２）をそれぞれ出される。
【００２９】
Ｔ１４において、メインメモリ７０は、相互結合網を介してアドレスＣのデータ（リードデータＲＤ１０）をＣＰＵ１０に出力する。このデータは、相互結合網によりＴ１５においてＣＰＵ１０に発行される。
【００３０】
Ｔ１６において、ＣＰＵ１０は、リードデータＲＤ１０を受信し、それをキャッシュ１２に登録する。これにより、ＣＰＵ１０のキャッシュ１２は、状態Ｉから状態Ｅに遷移する。
【００３１】
ＣＰＵ２０は、Ｔ５で受信したリトライ要求ＲＴＹ２０に応じて、Ｔ１７で再度アドレスＣについてリードリクエストＲＲ２０とスヌープリクエストを発行する。このとき、ＣＰＵ１０は、キャッシュヒットするため、当該データ（ＲＤ１０）をリードデータＲＤ２０ＡとしてＣＰＵ２０に出力する（Ｔ１９）。このとき、ＣＰＵ１０のキャッシュ１２は、状態Ｅから状態Ｉに戻る。
【００３２】
Ｔ２０において、ＣＰＵ２０は、ＣＰＵ１０からのリードデータＲＤ２０Ａを受信すると、それをキャッシュ２２に登録する。
【００３３】
なお、Ｔ２１において、リードリクエストＲＲ２０に応じてメインメモリ７０からもリードデータＲＤ２０ＢがＣＰＵ２０に出力されるが、ＣＰＵ２０のキャッシュに既に最新のデータが登録されているため、ＣＰＵ２０は、リードデータ２０Ｂを破棄する。
【００３４】
図１０のタイミングチャートから分かるように、ＣＰＵ１０のキャッシュ１２には、リードデータＲＤ１０はＴ１６〜Ｔ１８の期間にのみ登録されている。
【００３５】
ところで、ＣＰＵ１０がデータをリードしたのも、通常、このデータを更新するためである。ＣＰＵ１０がリードしたデータを更新してキャッシュにストアする前に他のプロセッサに出力してしまったのでは、ストア時にキャッシュの状態がＩ状態に戻っているため、再びキャッシュミスが生じる。そのため、データの更新を完結させるためには、他のＣＰＵとのハンドシェイクが必要になり、レイテンシが長くなる。その結果、システムの処理効率が悪化する。
本発明は、上記事情に鑑みてなされたものであり、データのリード、更新、ストアの一連の処理をＣＰＵ内部において完結させ、システムの処理効率を向上させる技術を提案する。
【課題を解決するための手段】
【００３６】
本発明の１つの態様は、ライトバック型キャッシュが実装された複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるキャッシュコヒーレンシ制御装置である。このキャッシュコヒーレンシ制御装置は、リード管理部と、キャッシュラインアドレス情報保持部と、ペンディング指示部を備える。
【００３７】
リード管理部は、上記複数のプロセッサのうちのいずれかのプロセッサからメインメモリに対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスのデータが他のプロセッサによりリードが実行されていないことを条件に、該リードリクエストに要求されたリードを許可する。
【００３８】
キャッシュラインアドレス情報保持部は、上記複数のプロセッサのうちのいずれかのプロセッサによりメインメモリからデータのリードが実行されている際に、このデータが当該プロセッサに出力されるまで該データのキャッシュラインアドレスを保持してリード管理部に供する。
【００３９】
ペンディング指示部は、キャッシュラインアドレス情報保持部に保持されたキャッシュラインアドレスのデータが当該プロセッサへ出力されることに同期して、データのリードに関連するリクエストの発行を一時停止させるペンディング指示を該プロセッサ以外のプロセッサに行う。
【００４０】
本発明の別の態様は、複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるプロセッサである。このプロセッサは、ライトバック型キャッシュと、キャッシュミスしたときに対象データのリードに関連するリクエストを発行するリクエスト発行部と、リードに関連するリクエストの発行の一時停止を要求するペンディング指示を受信した際に、リクエスト発行部がリードに関連するリクエストの発行を所定期間停止するように制御を行うリクエスト制御部を備える。
【００４１】
本発明のさらなる別の態様は、ライトバック型キャッシュが実装された複数のプロセッサがメインメモリを共有するマルチプロセッサシステムにおけるキャッシュコヒーレンシ制御方法である。この方法は、上記複数のプロセッサのうちのいずれかのプロセッサによりメインメモリからデータのリードが実行されている際に、このデータが当該プロセッサに出力されるまでそのキャッシュラインアドレスを保持する工程と、上記複数のプロセッサのうちのいずれかのプロセッサからメインメモリに対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスのデータが保持されていないことを条件に、該リードリクエストに要求されたリードを許可する工程と、保持されたキャッシュラインアドレスのデータが当該プロセッサへ出力されることに同期して、データのリードに関連するリクエストの発行を一時停止させるペンディング指示を該プロセッサ以外のプロセッサに行う工程を有する。
【００４２】
本発明のさらなる別の態様は、情報処理装置である。この情報処理装置は、ライトバック型キャッシュが実装された複数のプロセッサと、該複数のプロセッサにより共有されるメインメモリと、該複数のプロセッサのキャッシュコヒーレンシを制御するキャッシュコヒーレンシ制御装置を備える。キャッシュコヒーレンシ制御装置は、上記態様のキャッシュコヒーレンシ制御装置が適用され、プロセッサは、上記態様のプロセッサが適用される。
【００４３】
なお、上記態様のキャッシュコヒーレンシ制御装置を回路や方法並びにプログラムに置き換えて表現したもの、上記態様のキャッシュコヒーレンシ制御方法を装置や回路並びにプログラムに置き換えて表現したもの、上記態様のプロセッサを装置や回路並びに方法に置き換えて表現したものも、上記各態様の構成要素の組合せも、本発明の態様として有効である。
【発明の効果】
【００４４】
本発明によれば、マルチプロセッサシステムにおいて、キャッシュコヒーレンシを保証すると共に、システムの処理効率の悪化を防ぐことができる。
【発明を実施するための最良の形態】
【００４５】
本発明の具体的な実施例を説明する前に、まず、本発明にかかるキャッシュコヒーレンシ制御技術の原理を説明する。
図１は、本発明にかかるキャッシュコヒーレンシ制御技術を適用したマルチプロセッサシステム８０を示す。マルチプロセッサシステム８０は、複数（図示の例では４つ）のプロセッサ（ＣＰＵ）８１〜８４と、共有バス８５と、キャッシュコヒーレンシ制御装置９０と、メインメモリ８６を備える。例として、マルチプロセッサシステム８０は、キャッシュコヒーレンシを保証する方式としてスヌープ方式が用いられ、具体的なプロトコルはＭＥＳＩである。なお、分かりやすいように、図１においてリードに関連する構成要素のみを示し、マルチプロセッサシステムに通常備えられる他の構成要素については、図示および説明を省略する。
【００４６】
ＣＰＵ８１〜８４は、共有バス８５に接続され、共有バス８５を介して互いに通信することや、メインメモリ８６へアクセスすることができる。ＣＰＵ８１には、ライトバック型のキャッシュ８１Ａと、リクエスト発行部８１Ｂと、リクエスト制御部８１Ｃを備える。ＣＰＵ８２〜８４にも、ＣＰＵ８１と同様の構成を有する。
【００４７】
各ＣＰＵに備えられる各々の構成要素の詳細について、ＣＰＵ８１を例にして説明する。
ＣＰＵ８１において、図示しないＣＰＵコアの要求などにより、メインメモリ７０中のデータに対してリードする必要が生じたときに、キャッシュ８１Ａは、当該データの最新データが自身に登録されているか否かを確認する。登録されているときには、キャッシュ８１Ａは、キャッシュヒットしたとして当該データをＣＰＵコアに供する。一方、登録されていないときには、キャッシュ８１Ａは、キャッシュミスしたとして、その旨をリクエスト発行部８１Ｂに通知する。
【００４８】
リクエスト発行部８１Ｂは、キャッシュミスの通知を受信すると、共有バス８５を介して、リードに関連するリクエスト（以下単にリクエストともいう）を出力する。具体的には、マルチプロセッサシステム８０に対してリードリクエストを出力し、スヌープ処理すなわちスヌープリクエストの出力をする。なお、リクエスト発行部８１Ｂは、リクエスト制御部８１Ｃにより、リードに関連するリクエストの発行が一時停止するように制御されている場合には、上記リクエストの発行を停止し、該所定期間後にリクエストを発行する。
【００４９】
リクエスト発行部８１Ｂが発行したスヌープリクエストについて、ＣＰＵ８２〜８４のうちのいずれかにおいてキャッシュヒットがすると、該ＣＰＵは当該データをＣＰＵ８１に転送する。ＣＰＵ８１は、受信したこのデータをキャッシュ８１Ａに登録する。この場合、キャッシュヒットしたＣＰＵ内の最新データがメインメモリ８６に書き戻されていないものであれば、当該ＣＰＵは、ライトバックを実行する。また、データを出力したＣＰＵのキャッシュは、Ｉ状態に遷移する。
【００５０】
リクエスト制御部８１Ｃは、キャッシュコヒーレンシ制御装置９０からペンディング指示を受信した際に、リクエスト発行部８１Ｂがリードに関連するリクエストの発行が一時停止するように制御する。
【００５１】
キャッシュコヒーレンシ制御装置９０は、リード管理部９２と、キャッシュラインアドレス情報保持部９４と、ペンディング指示部９６を備える。
【００５２】
リード管理部９２は、ＣＰＵ８１〜８４のうちのいずれかのＣＰＵからメインメモリ８６に対するリードリクエストを受信した際に、該リードリクエストにより要求されるキャッシュラインアドレスがキャッシュラインアドレス情報保持部９４に保持されていないことを条件にリードを許可する。リードの許可／拒否は、例えばリードリクエストをメインメモリ８６に転送する／しないことにより実行される。
【００５３】
メインメモリ８６は、共有バス８５を介して、リード管理部９２によりリードが許可されたデータをリクエスト元のＣＰＵに送信すると共に、その旨をキャッシュコヒーレンシ制御装置９０に通知する。通知に際しては、その旨を示す信号をキャッシュコヒーレンシ制御装置９０に出力するようにしてもよく、リクエスト元のＣＰＵに送信するデータをキャッシュコヒーレンシ制御装置９０にも送信するようにしてもよい。なお、図１において、メインメモリ８６は、直接共有バス８５にデータを出力しているが、キャッシュコヒーレンシ制御装置９０を介してデータを出力するようにしてもよい。
【００５４】
リクエスト元のＣＰＵは、メインメモリ８６からのデータを受信すると、当該データを自身のキャッシュに登録する。
【００５５】
キャッシュラインアドレス情報保持部９４は、いずれかのＣＰＵによりメインメモリ８６からデータのリードが実行されているときに、該データのキャッシュラインアドレスを、該データがリクエスト元のＣＰＵに出力されるまで保持する。リード管理部９２は、キャッシュラインアドレス情報保持部９４に保持されたキャッシュラインアドレス情報を参照して、他のＣＰＵからのリードリクエストに対する許可／拒否を決定する。
【００５６】
ペンディング指示部９６は、キャッシュラインアドレス情報保持部９４に保持されたキャッシュラインアドレスのデータがリクエスト元のＣＰＵに出力されることに同期して、データのリードに関連するリクエストの発行を一時停止するペンディング指示を、該リクエスト元のＣＰＵ以外の他の各ＣＰＵに出力する。
【００５７】
マルチプロセッサシステム８０によれば、キャッシュコヒーレンシ制御装置９０は、複数のＣＰＵが近接したタイミングで同一のキャッシュラインアドレスのリードに関連するリクエストをし、先にリードが実行されるＣＰＵによりメインメモリ８６からデータを読み出している最中に後続のＣＰＵからリードリクエストが到達した場合に、後続のリードリクエストを拒否する。こうすることにより、同一のキャッシュラインアドレスについて、複数のＣＰＵが近接したタイミングでリードリクエストをした場合にも、該キャッシュラインアドレスのデータが２つ以上のＣＰＵのキャッシュにＥ状態で登録されることを防ぐことができ、キャッシュコヒーレンシが保たれる。
【００５８】
また、キャッシュコヒーレンシ制御装置９０は、リードが実行されたＣＰＵ（例えばＣＰＵ８１）に対象データ（たとえばキャッシュラインアドレスＡのデータ）が出力されるときに、ＣＰＵ８１以外の各ＣＰＵにペンディング指示をし、データのリードに関連するリクエストの発行を一時停止させる。こうすることにより、ペンディング指示を受信したＣＰＵ８２〜８４は、リードリクエストおよびスヌープリクエストを一定期間停止するので、これらのＣＰＵからのスヌープリクエストによりＣＰＵ８１のキャッシュ８１Ａにデータが登録された直後に無効にされてしまうことを防ぐことができる。そのため、ＣＰＵ８１は、該一定期間において、キャッシュラインアドレスＡのデータを更新してストアするときにキャッシュヒットできる。したがって、データのリード、更新、ストアをＣＰＵ８１内部で完結させることができ、短レイテンシのアクセスを実現する。
【００５９】
マルチプロセッサシステム８０において、キャッシュラインアドレス情報保持部９４に保持されたキャッシュラインアドレスについてリードに関連するリクエストを発行したＣＰＵは、リードが拒否された後、リードのリトライを行う必要がある。リードが拒否されたＣＰＵ自身によりリードリクエストの履歴を記憶し、拒否される度にリトライをしてもよいし、メインメモリ８６からデータの読出しを実行しているＣＰＵが、当該データのキャッシュラインアドレスについて他のＣＰＵからスヌープリクエストを受信した際に、キャッシュミスを返答する代わりにリトライを指示するリトライ指示を返答することによりリトライを実行させるようにしてもよい。
【００６０】
これについて、本発明にかかるキャッシュコヒーレンシ制御技術では、図１に示すキャッシュコヒーレンシ制御装置９０にリトライ指示部を設け、該リトライ指示部により、リード管理部９２がリードを拒否したＣＰＵにリトライ指示をすることが好ましい。こうすることにより、各ＣＰＵの負担を減らすことができると共に、特許文献１（「００６０」〜「００６１」）に記載された沈込み（スターべーション）の問題も防ぐことができる。
【００６１】
また、例えば、リードが実行されたＣＰＵ８１にキャッシュラインアドレスＡのデータが出力され、該データがＣＰＵ８１のキャッシュ８１Ａに登録された直後は、必ずしも他のＣＰＵからキャッシュラインアドレスＡに対するスヌープリクエストがあるとは限らない。他のＣＰＵからキャッシュラインアドレスＡに対するスヌープリクエストが無い場合に、他のＣＰＵにペンディング指示をしてリクエストを一時停止させると、システムの処理効率が低下する恐れがある。一方、ＣＰＵ８１によりキャッシュラインアドレスＡのデータの読出し中に、他のＣＰＵはキャッシュラインアドレスＡに対するリードリクエストが拒否され、リトライを行っている場合には、該データがＣＰＵ８１のキャッシュ８１Ａに登録された直後は、他のＣＰＵからキャッシュラインアドレスＡに対するスヌープリクエストの発生可能性が大きい。そのため、キャッシュコヒーレンシ制御装置９０は、リードのリトライを行うＣＰＵがあるときにのみペンディング指示を行うことが好ましい。こうすることによって、システムの処理効率の最適化を図ることができる。
【００６２】
さらに、例えば、ＣＰＵ８１によりキャッシュラインアドレスＡのデータの読出し中にリトライを実行していないＣＰＵは、リトライを実行しているＣＰＵと比べ、キャッシュラインアドレスＡのデータがＣＰＵ８１のキャッシュ８１Ａに登録された直後に該キャッシュラインアドレスＡについてスヌープリクエストを出力する可能性が低い。そのため、キャッシュコヒーレンシ制御装置９０は、リトライを行うプロセッサに対してのみペンディング指示を行うことが好ましい。こうすることにより、システムの処理効率を一層向上させることが可能である。
【００６３】
また、例えば、ＣＰＵ８１によりキャッシュラインアドレスＡのデータの読出し中にリトライを実行するＣＰＵの数が多いほど、キャッシュラインアドレスＡのデータがＣＰＵ８１のキャッシュ８１Ａに登録された直後に該キャッシュラインアドレスＡについてスヌープリクエストが出力される可能性が高い。そのため、キャッシュコヒーレンシ制御装置９０に、リトライを行うＣＰＵの数をカウントするリトライ数カウンタを設け、該リトライ数カウンタのカウント値が所定の閾値を超えたことを条件にペンディング指示を行うことが好ましい。これも、システムの処理効率の向上に功を奏することができる。
【００６４】
また、ペンディング指示部９６は、ペンディング指示として、キャッシュラインアドレス情報保持部９４に保持されたキャッシュラインアドレスが含まれたものを出力することが好ましい。こうすることにより、当該キャッシュラインアドレスのデータをリードすることに関連するリクエストの発行のみを一時停止させることになるので、システムの処理効率をより向上させることが可能である。
【００６５】
上記に説明した本発明のキャッシュコヒーレンシ制御技術は、同一のプロセッサにより同一のキャッシュラインアドレスに連続してアクセスすることが頻発するマルチプロセッサシステムに特に有利である。ここで、このようなマルチプロセッサシステムの一例を説明する。
【００６６】
マルチプロセッサシステムにおいて、メインメモリにおける共有領域のデータの更新に関して、一般的に、プロセッサ間でロックシーケンスと呼ばれる同期処理が実行される。図２は、このロックシーケンスを示す。図示のように、プロセッサは、共有領域を更新する際に、まず、共有領域に対して設けられた、該共有領域がロックされているか否かを示すロック変数をリードする（Ｓ１０）。ロック変数が、共有領域がロックされていることを示す場合に、該プロセッサは共有領域のロックが解除されるまでリトライを試みるが（Ｓ１２：Ｎｏ、Ｓ１０〜）、共有領域がロックされていないことを示すときに、該プロセッサはロック変数を更新して共有領域をロックすると共に、そのデータの更新および更新後のストアをする（Ｓ１２：Ｙｅｓ、Ｓ１４）。その後、該プロセッサは、ロック変数を更新して共有領域のロックを解除する（Ｓ１６）。
【００６７】
この際、ロック変数と共有領域が図３に示すように同一のキャッシュラインアドレスである場合には、共有領域に対するアクセスはプロセッサに備えられたキャッシュ上で行うことができるため、短レイテンシでアクセスを実行できる。
【００６８】
図３に示すようにロック変数と共有領域が同一のキャッシュラインアドレスに設けられたマルチプロセッサシステムにおいて、プロセッサが共有領域の更新を行うために、まずロック変数をリードする。ロック変数をリードした後に必ずロック変数の更新を行う。さらに、ロック変数の更新後、共有領域を更新するために再度同じキャッシュラインアドレスをリードする。また、共有領域の更新後には更新されたデータをストアするためにも同じキャッシュラインアドレスにアクセスする。そのため、このようなマルチプロセッサシステムにおいては、プロセッサが共有領域の更新に際して、必ず同一のキャッシュラインアドレスに対して連続してアクセスする。さらに、無効型プロトコルに準じて、ロック変数の更新に同期して、他のプロセッサのキャッシュにおける、該ロック変数が含まれるキャッシュラインは無効にされる。
【００６９】
すなわち、あるプロセッサ（プロセッサＡとする）のキャッシュに登録された、ロック変数と共有領域が含まれる同一のキャッシュラインのデータが、他のプロセッサのスヌープリクエストに応じて転送された際に、プロセッサＡの当該キャッシュラインは無効にされる。従って、プロセッサＡのリードに続き、他のプロセッサが近接したタイミングで同一のキャッシュラインアドレスをリードしようとしてキャッシュミスした場合には、スヌープリクエストのタイミングが、プロセッサＡが更新したデータをストアする前になる可能性が大きい。これでは、プロセッサＡがストアする際に、キャッシュミスしてしまうため、システムの処理効率が低下する。
【００７０】
そこで、このようなマルチプロセッサシステムに、本発明にかかるキャッシュコヒーレンシ制御技術を適用すれば、複数のプロセッサが近接したタイミングで同一のキャッシュアドレスラインにリードリクエストをした場合にも、ロックシーケンスの処理効率低下を防ぐことができるため、ロック変数と共有領域を同一のキャッシュラインアドレスに設けることの利点を最大に生かすことができる。
【００７１】
例えば、キャッシュヒット時のレイテンシを１ｎｓ、キャッシュミス時のレイテンシをＴｎｓ、プロセッサの数をｎ個、一度のロックシーケンスにつき共有領域へのアクセス回数をＭ回とする。この場合、本発明にかかるキャッシュコヒーレンシ制御技術を適用しない場合には、ロックシーケンスの処理時間は、「Ｍ×Ｔ×（ｎ−１）」ｎｓである。一方、本発明の技術を適用すれば、ロックシーケンスの処理時間は、「Ｍ×１」ｎｓになり、大幅に減少される。また、ｎが大きいほどすなわちプロセッサが多いほど、本発明により処理時間の短縮効果が顕著である。近年、マルチプロセッサシステムについて、ＣＰＵの数は年々増加する傾向にある。本発明にかかるキャッシュコヒーレンシ制御技術は、ＣＰＵの数が増加する一方のマルチプロセッサシステムにとって処理効率を向上させるための有効な技術である。
【００７２】
以上の説明を踏まえて、本発明の原理を具現化した実施例を説明する。
図４は、本発明の実施例にかかるマルチプロセッサシステム１００を示す。マルチプロセッサシステム１００は、複数（図示の例では４つ）のＣＰＵ１１０〜１４０と、共有バス１５０と、キャッシュコヒーレンシ制御回路１６０と、メインメモリ７０を備える。
【００７３】
ＣＰＵ１１０〜１４０は、共有バス１５０に接続され、共有バス５０を介して互いに通信することや、メインメモリ１７０へアクセスすることができる。また、ＣＰＵ１１０〜１４０には、キャッシュ１１２、キャッシュ１２２、キャッシュ１３２、キャッシュ１４２がそれぞれ実装されており、これらのキャッシュは、ライトバック方式のものである。なお、各ＣＰＵの他の構成要素について、図１に示すＣＰＵ１０らのものと同一であるので、図示を省略する。
【００７４】
キャッシュコヒーレンシ制御回路１６０は、キャッシュコヒーレンシを制御するものであり、共有バス１５０とメインメモリ１７０間に接続される。なお、本実施例のマルチプロセッサシステム１００において、キャッシュコヒーレンシを保証するプロトコルとして、スヌープ方式のＭＥＳＩプロトコルが用いられている。
【００７５】
図５は、マルチプロセッサシステム１００におけるキャッシュコヒーレンシ制御回路１６０を示す。キャッシュコヒーレンシ制御回路１６０は、リクエスト受信回路１６１と、リクエスト送信回路１６２と、リトライ送信回路１６３と、ペンディング指示生成回路１６４と、リプライ受信回路１６５と、リプライ送信回路１６６と、排他制御管理テーブル２００を備える。
【００７６】
リクエスト受信回路１６１は、各ＣＰＵからメインメモリ１７０へのリードリクエストを受信し、受信したリードリクエストを排他制御管理テーブル２００とリクエスト送信回路１６２に転送する。また、リクエスト受信回路１６１は、複数のＣＰＵから同時にリードリクエストを受信した際に、ＣＰＵ間で調停を行うと共に、調停を獲得したＣＰＵのリードリクエストを排他制御管理テーブル２００とリクエスト送信回路１６２に転送する。
【００７７】
排他制御管理テーブル２００は、リクエスト受信回路１６１から受信したリードリクエストを登録し、当該リードリクエストに対応するデータ（リードデータ）がリプライ受信回路１６５によりメインメモリ１７０から受信されるまで、このリードリクエストを保持する。排他制御管理テーブル２００は、複数のＣＰＵから同一のキャッシュラインアドレスに対するメインメモリ１７０へのリードリクエストを受信した場合に、最新のデータがこれらの複数のＣＰＵにキャッシュに登録されることが無いように排他制御を行う機能を有する。排他制御管理テーブル２００の詳細については、後に詳細に説明する。
【００７８】
リクエスト送信回路１６２は、リクエスト受信回路１６１から受信したリードリクエストをメインメモリ１７０に転送する。但し、既に同一のキャッシュラインアドレスに対するリードリクエストが排他制御管理テーブル２００に登録されている場合、リクエスト送信回路１６２は、受信したリードリクエストを破棄する。
【００７９】
リトライ送信回路１６３は、リクエスト受信回路１６１が受信したリードリクエストが要求するキャッシュラインアドレスに対するリードリクエストが既に排他制御管理テーブル２００にある場合、リクエスト受信回路１６１が受信したリードリクエストの発行元ＣＰＵに対してリトライ要求を送信する。
【００８０】
なお、リクエスト受信回路１６１が受信したリードリクエストが要求するキャッシュラインアドレスに対するリードリクエストが既に排他制御管理テーブル２００にあるか否かについて、リクエスト送信回路１６２とリトライ送信回路１６３は、排他制御管理テーブル２００から通知される。
【００８１】
リプライ受信回路１６５は、メインメモリ１７０がリクエスト送信回路１６２からのリードリクエストに応じて発行したリードデータを受信して、排他制御管理テーブル２００とリプライ送信回路１６６に転送する。
【００８２】
リプライ送信回路１６６は、リプライ受信回路１６５から受信したリードデータを、リクエストの発行元のＣＰＵに送信する。
【００８３】
ペンディング指示生成回路１６４は、リクエストの発行元のＣＰＵに対するリードデータが送信されると同時に、該ＣＰＵ以外のＣＰＵに対して、リードに関するリクエスト（リードリクエストとスヌープリクエスト）の新規発行を抑制するペンディング指示を送信する機能を有し、これは、排他制御管理テーブル２００により制御される。
【００８４】
図６は、排他制御管理テーブル２００を示す。排他制御管理テーブル２００は、複数のエントリを有し、各エントリには、該エントリの有効／無効を判別する判別ビット２０１と、メインメモリ１７０へのデータリクエストが実行されているキャッシュラインアドレスを示すキャッシュラインアドレス情報２０２と、キャッシュラインアドレス情報２０２に記憶されたキャッシュラインアドレスと同一のキャッシュラインアドレスに対するリードリクエストを受信した際に、リクエスト元のＣＰＵにリトライ要求を送信したことを示すリトライ検出フラグ２１３が設けられている。
【００８５】
上記各構成要素以外に、排他制御管理テーブル２００は、さらに、アドレス比較回路２０３と、無効エントリ判断回路２０４と、一致エントリ判断回路２０５と、エントリ判断回路２１１と、リクエスト元ＣＰＵ判断回路２１２と、リトライ数カウンタ２１４を備える。
【００８６】
アドレス比較回路２０３は、リクエスト受信回路１６１がリードリクエストを受信すると、判別ビット２０１とキャッシュラインアドレス情報２０２を参照し、エントリの判別ビット２０１が有効を示す「１」にセットされているエントリのキャッシュラインアドレスと、受信したリードリクエストにより要求されるキャッシュラインアドレスと比較する。比較の結果は、無効エントリ判断回路２０４、一致エントリ判断回路２０５、リクエスト送信回路１６２、リトライ送信回路１６３に出力される。
【００８７】
アドレス比較回路２０３による比較の結果、受信したリードリクエストにより要求されるキャッシュラインアドレスに一致するものが無ければ、無効エントリ判断回路２０４は、有効ビットが設定されていない空きエントリの判別ビット２０１を「１」にセットすると共に、キャッシュラインアドレス情報２０２に該キャッシュラインアドレスを登録する。また、無効エントリ判断回路２０４は、該リードリクエストが登録されたエントリを示すエントリ情報をリクエスト送信回路１６２に出力する。
【００８８】
この場合、一致エントリ判断回路２０５とリトライ送信回路１６３は、何もしない。リクエスト送信回路１６２は、当該リードリクエストをエントリ情報と共にメインメモリ１７０に送信すると共に、そのエントリ情報を保持する。
【００８９】
一方、アドレス比較回路２０３による比較の結果、受信したリードリクエストにより要求されるキャッシュラインアドレスに一致するものがあれば、一致エントリ判断回路２０５は、一致したキャッシュラインアドレスのエントリ番号を取得して、該エントリのリトライ検出フラグ２１３をセットする。リトライ検出フラグ２１３は、マルチプロセッサシステム１００におけるＣＰＵ毎に、該ＣＰＵを識別する情報例えばＣＰＵ番号とフラグとが対応付けて設けられており、それぞれのＣＰＵに対してリトライ要求を送信したか否かを示すことができる。リクエスト元ＣＰＵ判断回路２１２は、一致エントリ判断回路２０５からの情報に基づいて、リクエスト発行元のＣＰＵを判断してリトライ検出フラグ２１３に供する。
【００９０】
この場合、無効エントリ判断回路２０４は何もしない。リクエスト送信回路１６２は、当該リードリクエストを破棄する。リトライ送信回路１６３は、リクエスト元ＣＰＵにリトライ要求を送信する。
【００９１】
メインメモリ１７０は、リクエスト送信回路１６２からのリードリクエストに要求されたデータをリプライ受信回路１６５に出力する。リプライ受信回路１６５は、そのデータをエントリ判断回路２１１に送信する。なお、このデータにはエントリ情報が付属されている。
【００９２】
エントリ判断回路２１１は、データに付属されたエントリ情報に基づいて、当該データのリクエストが登録されているエントリを判断する共に、このエントリの判別ビット２０１を、無効を示す「０」にリセットする。また、エントリ判断回路２１１は、リトライ検出フラグ２１３を索引し、フラグがセットされたＣＰＵの数すなわちリトライ要求が送信されたＣＰＵの数をリトライ数として取得する。このリトライ数は、リトライ数カウンタ２１４に出力される。リトライ数カウンタ２１４はそれをカウントし、ペンディング指示生成回路１６４に出力する。
【００９３】
リトライ数カウンタ２１４のカウント値が所定の閾値（たとえば２）を超えたときに、ペンディング指示生成回路１６４は、メインメモリ１７０へのリードに関する新規のリクエスト（リードリクエストとスヌープリクエスト）を一時停止させるペンディング指示を、リプライ受信回路１６５が受信したリードデータのリクエスト元ＣＰＵ以外のＣＰＵに送信する。
【００９４】
なお、キャッシュコヒーレンシ制御回路１６０において、判別ビット２０１とキャッシュラインアドレス情報２０２は、図１に示すマルチプロセッサシステム８０のキャッシュラインアドレス情報保持部９４に保持されたキャッシュラインアドレス情報に該当し、ペンディング指示生成回路１６４は、マルチプロセッサシステム８０のペンディング指示部９６として機能する。また、リクエスト送信回路１６２は、マルチプロセッサシステム８０のリード管理部９２の機能を備える。
【００９５】
図７は、マルチプロセッサシステム１００において、同一のキャッシュラインアドレスに対して、複数のプロセッサが近接したタイミングでリードした場合のタイミングチャートの例を示す。図７において、ＳＲ、ＲＲ、ＲＤ、ＲＴＹ、ＰＤは、それぞれ「スヌープリクエスト」、「リードリクエスト」、「リードデータ」、「リトライ要求」、「ペンディング指示」を示す。Ｔ１、Ｔ２、・・・は、タイミングを示す。なお、分かりやすいように、スヌープリクエストについて、ＣＰＵ１１０と関係するもののみを示している。
【００９６】
図７に示す例では、Ｔ０において、ＣＰＵ１１０は、対象アドレス（アドレスＣとする）についてキャッシュミスしたため、メインメモリ１７０にリードリクエストＲＲ１１０を出力すると共に、スヌープ処理をする（ＳＲ１１０２、ＳＲ１１０３、ＳＲ１１０４）。ＣＰＵ１２０〜１４０も、キャッシュミスし、スヌープリクエストに返答しないとする。
【００９７】
Ｔ１において、ＣＰＵ１１０からのリードリクエストＲＲ１１０は、キャッシュコヒーレンシ制御回路１６０によりメインメモリ１７０に発行される。
【００９８】
Ｔ２において、ＣＰＵ１２０も、アドレスＣについてキャッシュミスし、メインメモリ１７０にリードリクエストＲＲ１２０を出力すると共に、スヌープ処理をする。これにより、Ｔ３において、ＣＰＵ１１０は、スヌープリクエストＳＲ１２０１を受信し、キャッシュコヒーレンシ制御回路１６０は、リードリクエストＲＲ１２０を受信する。
【００９９】
ＣＰＵ１１０がアドレスＣのデータをメインメモリ１７０からリードする処理中であるので、Ｔ４において、キャッシュコヒーレンシ制御回路１６０は、ＣＰＵ１２０に対してリトライ要求ＲＴＹ１２０を出力する。
【０１００】
その後、アドレスＣについてキャッシュミスしたＣＰＵ１３０とＣＰＵ１４０も、キャッシュコヒーレンシ制御回路１６０からリトライ要求ＲＴＹ１３０（Ｔ８）とＲＴＹ１４０（Ｔ１２）をそれぞれ出される。
【０１０１】
Ｔ１４において、メインメモリ１７０は、キャッシュコヒーレンシ制御回路１６０を介してアドレスＣのデータ（リードデータＲＤ１１０）をＣＰＵ１１０に出力する。このデータは、キャッシュコヒーレンシ制御回路１６０によりＣＰＵ１１０に発行される（Ｔ１５）。
【０１０２】
Ｔ１７において、ＣＰＵ１１０は、リードデータＲＤ１１０を受信し、それをキャッシュ１１２に登録する。
【０１０３】
ここで、リトライを行うＣＰＵの数が３つであり、閾値の２を超えたとして、キャッシュコヒーレンシ制御回路１６０は、ＣＰＵ１２０、ＣＰＵ１３０、ＣＰＵ１４０に対して、ペンディング指示ＰＤ１２０、ペンディング指示ＰＤ１３０、ペンシング指示ＰＤ１４０をそれぞれ発行する（Ｔ１７）。
【０１０４】
これにより、ＣＰＵ１２０〜１４０は、Ｔ１７〜Ｔ１８間にリードに関連するリクエストの発行を一時停止する。そのため、ＣＰＵ１１０は、Ｔ１７〜Ｔ１９間に、再度アドレスＣについてリードを行うと、キャッシュヒットする。
【０１０５】
ＣＰＵ１２０は、Ｔ５で受信したリトライ要求ＲＴＹ１２０に応じて、Ｔ１８でリクエストを再開し、アドレスＣについてリードリクエストＲＲ１２０とスヌープリクエストを発行する。このとき、ＣＰＵ１１０は、キャッシュヒットするため、当該データ（ＲＤ１１０）をリードデータＲＤ１２０ＡとしてＣＰＵ１２０に出力する（Ｔ２０）。
【０１０６】
Ｔ２１において、ＣＰＵ１２０は、ＣＰＵ１１０からのリードデータＲＤ１２０Ａを受信すると、それをキャッシュ１２２に登録する。
【０１０７】
なお、Ｔ２２において、リードリクエストＲＲ１２０に応じてメインメモリ１７０からもリードデータＲＤ１２０ＢがＣＰＵ１２０に出力されるが、ＣＰＵ１２０のキャッシュに既に最新のデータが登録されているため、ＣＰＵ１２０は、リードデータ１２０Ｂを破棄する。
【０１０８】
図７のタイミングチャートから分かるように、ＣＰＵ１２０がＣＰＵ１１０から受信したＣＰＵ１２０Ａに対して更新をし、ＣＰＵ１１０内の当該キャッシュラインが無効になったとしても、ＣＰＵ１１０は、Ｔ１７においてアドレスＣのデータをキャッシュ１１２に登録した後、他のＣＰＵのリクエスト停止期間が終わるまで、アドレスＣへのアクセスは、キャッシュヒットすることができ、短レイテンシのアクセスを実現可能である。
【０１０９】
マルチプロセッサシステム１００は、マルチプロセッサシステム８０の具体例であり、マルチプロセッサシステム８０について説明した効果を得ることができる。
【０１１０】
以上、実施の形態をもとに本発明を説明した。実施の形態は例示であり、本発明の主旨から逸脱しない限り、さまざまな変更、増減を加えてもよい。これらの変更、増減が加えられた変形例も本発明の範囲にあることは当業者に理解されるところである。
【０１１１】
例えば、マルチプロセッサシステム８０およびマルチプロセッサシステム１００において、メインメモリは１つしかないが、本発明にかかるキャッシュコヒーレンシ制御技術は、複数のメインメモリを有するマルチプロセッサシステムに適用できる共に、適用によりシステムのキャッシュコヒーレンシを保証すると共に、処理効率を向上させることができる。
【０１１２】
また、上記説明において、各プロセッサおよびメインメモリが共有バスを介して接続されたマルチプロセッサシステムを例としているが、本発明にかかる技術は、複数のプロセッサがメインメモリを共有するいかなるマルチプロセッサシステムにも適用することができると共に、適用することによりその効果を発揮することができる。例えば、図８に示すように、複数のプロセッサとメインメモリがネットワークを介して接続されたマルチプロセッサシステムにも本発明の技術を適用することができる。
【図面の簡単な説明】
【０１１３】
【図１】本発明の技術の原理を説明するためのマルチプロセッサシステムの模式図である。
【図２】本発明の技術を適用するシステム例を説明するための図である（その１）。
【図３】本発明の技術を適用するシステム例を説明するための図である（その２）。
【図４】本発明の実施例にかかるマルチプロセッサシステムを示す図である。
【図５】図４に示すマルチプロセッサにおけるキャッシュコヒーレンシ制御回路を示す図である。
【図６】図６に示すキャッシュコヒーレンシ制御回路における排他制御管理テーブルを示す図である。
【図７】図４に示すマルチプロセッサシステムのタイミングチャートの例である。
【図８】本発明の技術を適用可能な他のマルチプロセッサシステムの例を示す図である。
【図９】通常のマルチプロセッサシステムの例を示す図である。
【図１０】図９に示すマルチプロセッサシステムに特許文献１の手法を適用した場合のタイミングチャートの例である。
【符号の説明】
【０１１４】
１  マルチプロセッサシステム  １０  ＣＰＵ
１２  キャッシュ  ２０  ＣＰＵ
２２  キャッシュ  ３０  ＣＰＵ
３２  キャッシュ  ４０  ＣＰＵ
４２  キャッシュ  ５０  共有バス
７０  メインメモリ  ８０  マルチプロセッサシステム
８１  ＣＰＵ  ８１Ａ  キャッシュ
８１Ｂ  リクエスト発行部  ８１Ｃ  リクエスト制御部
８２  ＣＰＵ  ８２Ａ  キャッシュ
８２Ｂ  リクエスト発行部  ８２Ｃ  リクエスト制御部
８３  ＣＰＵ  ８３Ａ  キャッシュ
８３Ｂ  リクエスト発行部  ８３Ｃ  リクエスト制御部
８４  ＣＰＵ  ８４Ａ  キャッシュ
８４Ｂ  リクエスト発行部  ８４Ｃ  リクエスト制御部
８５  共有バス  ８６  メインメモリ
９０  キャッシュコヒーレンシ制御装置  ９２  リード管理部
９４  キャッシュラインアドレス情報保持部  ９６  ペンディング指示部
１００  マルチプロセッサシステム  １１０  ＣＰＵ
１１２  キャッシュ  １２０  ＣＰＵ
１２２  キャッシュ  １３０  ＣＰＵ
１３２  キャッシュ  １４０  ＣＰＵ
１４２  キャッシュ  １５０  共有バス
１６０  キャッシュコヒーレンシ制御回路  １６１  リクエスト受信回路
１６２  リクエスト送信回路  １６３  リトライ送信回路
１６４  ペンディング指示生成回路  １６５  リプライ受信回路
１６６  リプライ送信回路  １７０  メインメモリ
２００  排他制御管理テーブル  ２０１  判別ビット
２０２  キャッシュラインアドレス情報  ２０３  アドレス比較回路
２０４  無効エントリ判断回路  ２０５  一致エントリ判断回路
２１１  エントリ判断回路  ２１２  リクエスト元ＣＰＵ判断回路
２１３  リトライ検出フラグ  ２１４  リトライ数カウンタ
【図１】
0004474570.tif 000002
【図２】
0004474570.tif 000003
【図３】
0004474570.tif 000004
【図４】
0004474570.tif 000005
【図５】
0004474570.tif 000006
【図６】
0004474570.tif 000007
【図７】
0004474570.tif 000008
【図８】
0004474570.tif 000009
【図９】
0004474570.tif 000010
【図１０】
0004474570.tif 000011