(57)【要約】      （修正有）【課題】キャッシュメモリにおけるアクセス保留を簡易な構成により実現する。【解決手段】タグ記憶部２２０は、複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引される。タグ制御部２３０は、索引されたインデックスに含まれる保留中表示部が保留中である旨を表示している場合にはアクセスアドレスに係るアクセスを待機させる。一方、索引されたインデックスに含まれる保留中表示部が保留中でない旨を表示している場合には、第１のアドレス部分とは異なるアクセスアドレスの第２のアドレス部分と索引されたインデックスに含まれる複数のタグアドレスのそれぞれとを比較して一致するものを検出する。【選択図】図２
2014186579.tif 000002
【特許請求の範囲】
【請求項１】
複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、
前記複数のインデックス毎に前記複数のタグアドレスに対応するデータをそれぞれ記憶するデータ記憶部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させ、前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記索引されたインデックスに含まれる前記複数のタグアドレスのうち前記第２のアドレス部分と一致したタグアドレスに対応するデータを前記データ記憶部から選択するデータ制御部と
を具備するキャッシュメモリ。
【請求項２】
前記保留中表示部は、リード処理に起因する保留中を示すリード起因保留中表示部と、ライト処理に起因する保留中を示すライト起因保留中表示部とを含み、
前記タグ制御部は、前記索引されたインデックスにおいて前記リード起因保留中表示部および前記ライト起因保留中表示部の少なくとも何れか一方が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させる
請求項１記載のキャッシュメモリ。
【請求項３】
複数マスタから共有される共有キャッシュメモリである請求項１記載のキャッシュメモリ。
【請求項４】
複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させ、前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部と
を具備するキャッシュメモリ制御装置。
【請求項５】
複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部を備えるキャッシュメモリにおいて、前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させる手順と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出する手順と
を具備するキャッシュメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、キャッシュメモリに関する。詳しくは、先行するメモリへのアクセスの応答を待たずに後続のアクセスを発行可能なセットアソシアティブ方式のキャッシュメモリ、キャッシュメモリ制御装置、および、そのキャッシュメモリ制御方法に関する。
【背景技術】
【０００２】
これまで、プロセッサからメインメモリへのアクセス頻度をいかに減らすかという方策の一つとして、キャッシュメモリが用いられてきた。これは、プロセッサ処理速度の向上度合いに比べて、対メインメモリアクセス完了時間短縮化の向上度合いが小さいため、検討されてきたものである。メインメモリは、容量当たりのコストが比較的安価ではあるが、アクセス完了時間が比較的長い。これに対し、キャッシュメモリは、容量当たりのコストが比較的高価ではあるが、アクセス完了時間が比較的短い。プロセッサとメインメモリの間にキャッシュメモリを介する階層化された記憶機構を設けることにより、コストの低下とアクセス完了時間の短縮化を両立させている。
【０００３】
また、昨今のプロセッサを含むシステムにおいては、複数のプロセッサを備えたものが主流となりつつある。上述の記憶機構の階層化が進み、二次キャッシュや三次キャッシュが用いられ、さらにその二次あるいは三次キャッシュは、複数のプロセッサが共有する記憶装置となる場合がある。
【０００４】
プロセッサがキャッシュメモリへアクセスする際、所望のデータがキャッシュメモリ上にあることが望ましいが、実際にはキャッシュメモリ上に所望のデータが存在せずに、キャッシュミスとなることがある。その際、そのキャッシュメモリがメインメモリよりも一段のみプロセッサ寄りであった場合、キャッシュメモリからメインメモリへのアクセスが発生する。
【０００５】
このキャッシュメモリが複数のプロセッサにより共有されていた場合、メインメモリへのアクセス中に、その完了までいかにシステム全体として動作を中断させずに効率良く処理を実行できるかが問題となる。その対策として、以下のような手法が採られる可能性がある。
（１）そのキャッシュメモリへの後続アクセスがキャッシュヒットであった場合は処理を続行する（ヒット・アンダー・ミス）。
（２）上述の（１）に加えて、そのキャッシュメモリへの後続アクセスがキャッシュミスであった場合も処理を続行する（ミス・アンダー・ミス）。
【０００６】
これらヒット・アンダー・ミスや、ミス・アンダー・ミスを実現しようとする場合、キャッシュミスに起因するフィル処理やライトバック処理が完了するまでは、そのキャッシュラインへのアクセスを保留する必要がある。そのため、例えば、キャッシュライン毎に保留中か否かの状態を示すフラグを設けて、フィル処理完了までそのキャッシュラインへのアクセスを保留するキャッシュメモリが提案されている（例えば、特許文献１および２参照。）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平６−１４９６７３号公報
【特許文献２】特開２０１０−０３３４８０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の従来技術では、キャッシュライン毎にフラグを設けることにより、そのキャッシュラインへのアクセスを保留していた。しかしながら、そのようなフラグに加えて、バリッドやダーティの管理、さらにキャッシュライン選択制御を組み合わせると、回路規模が増大し、それらの検証が複雑になるという問題があった。
【０００９】
本技術はこのような状況に鑑みて生み出されたものであり、キャッシュメモリにおけるアクセス保留を簡易な構成により実現することを目的とする。
【課題を解決するための手段】
【００１０】
本技術は、上述の問題点を解消するためになされたものであり、その第１の側面は、複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、上記複数のインデックス毎に上記複数のタグアドレスに対応するデータをそれぞれ記憶するデータ記憶部と、上記索引されたインデックスに含まれる上記保留中表示部が保留中である旨を表示している場合には上記アクセスアドレスに係るアクセスを待機させ、上記索引されたインデックスに含まれる上記保留中表示部が保留中でない旨を表示している場合には上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたインデックスに含まれる上記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部と、上記索引されたインデックスに含まれる上記保留中表示部が保留中でない旨を表示している場合には上記索引されたインデックスに含まれる上記複数のタグアドレスのうち上記第２のアドレス部分と一致したタグアドレスに対応するデータを上記データ記憶部から選択するデータ制御部とを具備するキャッシュメモリおよびその処理方法である。これにより、索引されたインデックスに含まれる保留中表示部を参照することによって、キャッシュメモリにおける処理を待機させるか否かを判断するという作用をもたらす。
【００１１】
また、この第１の側面において、上記保留中表示部は、リード処理に起因する保留中を示すリード起因保留中表示部と、ライト処理に起因する保留中を示すライト起因保留中表示部とを含み、上記タグ制御部は、上記索引されたインデックスにおいて上記リード起因保留中表示部および上記ライト起因保留中表示部の少なくとも何れか一方が保留中である旨を表示している場合には上記アクセスアドレスに係るアクセスを待機させてもよい。これにより、保留中の要因となる処理を切り分けるという作用をもたらす。
【００１２】
また、この第１の側面において、複数マスタから共有される共有キャッシュメモリであってもよい。
【００１３】
また、本技術の第２の側面は、複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、上記索引されたインデックスに含まれる上記保留中表示部が保留中である旨を表示している場合には上記アクセスアドレスに係るアクセスを待機させ、上記索引されたインデックスに含まれる上記保留中表示部が保留中でない旨を表示している場合には上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたインデックスに含まれる上記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部とを具備するキャッシュメモリ制御装置およびその制御方法である。これにより、索引されたインデックスに含まれる保留中表示部を参照することによってアクセスを待機させるか否かを判断するという作用をもたらす。
【発明の効果】
【００１４】
本技術によれば、キャッシュメモリにおけるアクセス保留を簡易な構成により実現することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態における情報処理システムの一構成例を示す図である。
【図２】本発明の実施の形態における二次キャッシュ２００の機能構成例を示す図である。
【図３】本発明の実施の形態における二次キャッシュ２００の回路構成例を示す図である。
【図４】本発明の実施の形態におけるタグ記憶部２２０の構成例を示す図である。
【図５】本発明の実施の形態における二次キャッシュ２００の処理手順例を示す流れ図である。
【図６】本発明の実施の形態における二次キャッシュ２００のリード命令に対する状態遷移例を示す図である。
【図７】本発明の実施の形態における二次キャッシュ２００のライト命令に対する状態遷移例を示す図である。
【図８】本発明の実施の形態における二次キャッシュ２００のフィル命令に対する状態遷移例を示す図である。
【図９】本発明の実施の形態における二次キャッシュ２００のフラッシュ命令アドレス型に対する状態遷移例を示す図である。
【図１０】本発明の実施の形態における二次キャッシュ２００のフラッシュ命令インデックス型に対する状態遷移例を示す図である。
【図１１】本発明の実施の形態における二次キャッシュ２００のインバリデート命令アドレス型に対する状態遷移例を示す図である。
【図１２】本発明の実施の形態における二次キャッシュ２００のインバリデート命令インデックス型に対する状態遷移例を示す図である。
【図１３】本発明の実施の形態における二次キャッシュ２００のフラッシュアンドインバリデート命令アドレス型に対する状態遷移例を示す図である。
【図１４】本発明の実施の形態における二次キャッシュ２００のフラッシュアンドインバリデート命令インデックス型に対する状態遷移例を示す図である。
【図１５】本発明の実施の形態における二次キャッシュ２００のアロケート命令に対する状態遷移例を示す図である。
【図１６】本発明の実施の形態におけるリード命令の動作の第１の例を示すタイミング図である。
【図１７】本発明の実施の形態におけるリード命令の動作の第２の例を示すタイミング図である。
【図１８】本発明の実施の形態におけるリード命令の動作の第３の例を示すタイミング図である。
【図１９】本発明の実施の形態におけるリード命令の動作の第４の例を示すタイミング図である。
【図２０】本発明の実施の形態におけるリード命令の動作の第５の例を示すタイミング図である。
【図２１】本発明の実施の形態の変形例におけるタグ記憶部２２０の構成例を示す図である。
【図２２】本発明の実施の形態の変形例における二次キャッシュ２００の処理手順例を示す流れ図である。
【発明を実施するための形態】
【００１６】
以下、本技術を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．実施の形態（リードおよびライトを区別したアウトスタンディング管理の例）
２．変形例（リードおよびライトを区別しないアウトスタンディング管理の例）
【００１７】
＜１．実施の形態＞
［情報処理システムの構成］
図１は、本発明の実施の形態における情報処理システムの一構成例を示す図である。この情報処理システムは、ｐ個（ｐは１以上の整数）のプロセッサ１００−１乃至１００−ｐ（以下、これらをまとめてプロセッサ１００と呼称する場合がある。）と、二次キャッシュ２００と、メインメモリ３００とを備える。
【００１８】
プロセッサ１００は、それぞれ内部に一次キャッシュ１１０−１乃至１１０−ｐ（以下、これらをまとめて一次キャッシュ１１０と呼称する場合がある。）を備える。これにより、プロセッサ１００は、一次キャッシュ１１０にヒットしている限りにおいては一次キャッシュ１１０を用いてデータアクセスを行うが、一次キャッシュ１１０においてミスヒットとなった場合には二次キャッシュ２００にアクセスを行う。また、プロセッサ１００は、一次キャッシュ１１０でミスヒットとなった際、二次キャッシュ２００にヒットしている限りにおいては二次キャッシュ２００を用いてデータアクセスを行う。一方、二次キャッシュ２００においてミスヒットとなった場合にはメインメモリ３００にアクセスを行う。
【００１９】
このように、本発明の実施の形態においては、プロセッサ１００のそれぞれにおける一次キャッシュ１１０、プロセッサ１００のそれぞれに共有される二次キャッシュ２００、メインメモリ３００という３階層の記憶構造となっている。ここで、プロセッサ１００をマスタと考えると、この二次キャッシュ２００は複数マスタから共有される共有キャッシュメモリになる。
【００２０】
［二次キャッシュの構成］
図２は、本発明の実施の形態における二次キャッシュ２００の機能構成例を示す図である。この二次キャッシュ２００は、調停部２１０と、タグ記憶部２２０と、タグ制御部２３０と、データ記憶部２４０と、データ制御部２５０と、応答部２６０とを備えている。
【００２１】
調停部２１０は、プロセッサ１００−１乃至１００−ｐおよびメインメモリ３００からのアクセスを調停して、何れかにアクセス許可を付与するものである。この調停部２１０における調停としては、例えば、ラウンドロビン方式によりプロセッサ１００−１乃至１００−ｐおよびメインメモリ３００に順次割り当てていくことが考えられる。許可されたアクセスは、タグ制御部２３０に供給される。
【００２２】
タグ記憶部２２０は、複数のエントリからなるメモリであり、各エントリにタグアドレス等を保持するものである。タグアドレスは、後述するように、アクセスされたアドレスの一部を示すものである。タグ記憶部２２０の各エントリは、アクセスされたアドレスの他の一部により索引される。
【００２３】
タグ制御部２３０は、アクセスされたアドレスに基づいて、タグ記憶部２２０においてアクセスすべきエントリを選択して制御するものである。このタグ制御部２３０により選択されたエントリは、データ制御部２５０に通知される。
【００２４】
データ記憶部２４０は、タグ記憶部２２０の各エントリに対応するデータを記憶するものである。このデータ記憶部２４０に記憶されるデータはキャッシュライン毎に管理され、メインメモリ３００やプロセッサ１００との間の転送もキャッシュライン毎に行われる。
【００２５】
データ制御部２５０は、タグ制御部２３０において選択されたエントリに応じて、データ記憶部２４０に記憶されたデータ（キャッシュライン）にアクセスするものである。リードアクセスやライトバック動作の場合には、データ記憶部２４０から読み出されたデータは応答部２６０に供給される。ライトアクセスの場合には、データ記憶部２４０から読み出されたデータの中の対応する位置にライトデータが埋め込まれて、再びデータ記憶部２４０に記憶される。
【００２６】
応答部２６０は、データ制御部２５０から供給されたデータをプロセッサ１００−１乃至１００−ｐまたはメインメモリ３００に出力するものである。プロセッサ１００からのリードアクセスに対する応答であれば、データはアクセスしたプロセッサ１００に出力される。メインメモリ３００へのライトバック動作であれば、データはメインメモリ３００に出力される。
【００２７】
図３は、本発明の実施の形態における二次キャッシュ２００の回路構成例を示す図である。ここでは、二次キャッシュ２００として、ライン数１２８、ラインサイズ６４Ｂ（バイト）の４ウェイ・セット・アソシアティブ・キャッシュを想定する。すなわち、同一インデックスアドレスに対して最大４つのキャッシュラインを記憶可能であり、各キャッシュラインに対応するデータのサイズは６４Ｂとなる。
【００２８】
メインメモリ３００の領域を２５６ＭＢとすると、必要なアドレスは２８ビットとなる。ブロックサイズが６４Ｂであるため、アクセスアドレスの第０乃至５ビットの計６ビットがライン内アドレスに割り当てられる。また、ライン数が１２８であることから、タグ記憶部２２０のエントリを索引するためのインデックスアドレスは、アクセスアドレスの第６乃至１２ビットの計７ビットに割り当てられる。したがって、タグアドレスは、アクセスアドレスの第１３乃至２７ビットの計１５ビットに割り当てられる。アクセスアドレスのうちタグアドレスは信号線２０１を介して、インデックスアドレスは信号線２０２を介して、ライン内アドレスは信号線２０３を介して、それぞれ二次キャッシュ２００に供給される。
【００２９】
タグ記憶部２２０は、それぞれ１２８個のエントリから成る４つのウェイ（ｗａｙ）＃０乃至＃３を備える。タグ記憶部２２０の各ウェイは、信号線２０２を介して供給されるインデックスアドレスによって索引される。したがって、この例では、４つのエントリが索引されることになる。
【００３０】
タグ制御部２３０は、比較器２３１乃至２３４と、論理和演算器２３５とを備え、タグ記憶部２２０において索引されたエントリのうちタグアドレスが一致するものを検出する。比較器２３１は、タグ記憶部２２０のウェイ＃０において索引されたエントリに含まれるタグアドレスと、信号線２０１を介して供給されたタグアドレスとを比較して一致を検出するものである。比較器２３２は、タグ記憶部２２０のウェイ＃１において索引されたエントリに含まれるタグアドレスと、信号線２０１を介して供給されたタグアドレスとを比較して一致を検出するものである。同様に、比較器２３３はタグ記憶部２２０のウェイ＃２に対応し、比較器２３４はタグ記憶部２２０のウェイ＃３に対応する。これら比較器２３１乃至２３４における比較結果は、論理和演算器２３５およびデータ制御部２５０に供給される。論理和演算器２３５は、比較器２３１乃至２３４の何れかで一致が検出された場合に、ヒットした旨を、信号線２９８を介して出力するものである。ただし、後述するように、対応するエントリのバリッドビットが無効である旨を示している場合には、ミスヒットとして判定される。
【００３１】
データ記憶部２４０は、それぞれ１２８個のキャッシュラインから成る４つのウェイ＃０乃至＃３を備え、タグ記憶部２２０の各エントリに対応するデータを記憶する。このデータ記憶部２４０もタグ記憶部２２０と同様に信号線２０２を介して供給されるインデックスアドレスによって索引される。これにより、４つの６４Ｂのラインデータがデータ制御部２５０に供給される。
【００３２】
データ制御部２５０は、選択器２５１および２５２を備える。選択器２５１は、データ記憶部２４０から供給された４つの６４Ｂデータの何れか一方を選択するものである。すなわち、比較器２３１において一致が検出された場合にはデータ記憶部２４０のウェイ＃０のラインデータが選択され、比較器２３２において一致が検出された場合にはデータ記憶部２４０のウェイ＃１のラインデータが選択される。また、比較器２３３において一致が検出された場合にはデータ記憶部２４０のウェイ＃２のラインデータが選択され、比較器２３４において一致が検出された場合にはデータ記憶部２４０のウェイ＃３のラインデータが選択される。ただし、後述するように、一致が検出されたエントリのバリッドビットが無効である旨を示している場合にはそのキャッシュラインのデータは選択されない。比較器２３１および２３２の何れにおいても一致が検出されない場合には、何れのキャッシュラインのデータも選択されない。
【００３３】
選択器２５２は、選択されたラインデータのうちライン内アドレスとして指定された位置のデータを選択するものである。ライン内アドレスは、信号線２０３を介して供給される。ただし、この選択器２５２の機能はプロセッサ１００側に備えるようにしてもよい。何れの場合も、ラインデータ全体またはその一部は信号線２９９を介して応答部２６０に出力される。
【００３４】
図４は、本発明の実施の形態におけるタグ記憶部２２０の構成例を示す図である。タグ記憶部２２０は、４ウェイに分かれた各キャッシュラインに、タグアドレス２２１、バリッド２２２、および、ダーティ２２３の各フィールドを備える。また、インデックス毎にリードアウトスタンディング２２５、ライトアウトスタンディング２２６、置換アルゴリズム２２７の各フィールドを備える。
【００３５】
タグアドレス２２１は、そのエントリに対応するキャッシュラインのタグアドレス（アドレスの上位１５ビット）を記憶するものである。図中では、このタグアドレス２２１を「ＴＡＧ」と略している。
【００３６】
バリッド２２２は、そのエントリの有効性を示すバリッドビット（Ｖａｌｉｄ）を記憶するものである。このバリッド２２２が「１」を示していればそのエントリに対応するキャッシュラインのデータは有効であり、「０」を示していれば比較器２３１乃至２３４において一致が検出されたとしてもヒットとは判定されない。図中では、このバリッド２２２を「Ｖ」と略している。
【００３７】
ダーティ２２３は、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータとが一致していないことを示すダーティービット（Ｄｉｒｔｙ）を記憶するものである。このダーティ２２３が「１」を示している場合には、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータは一致しておらず、二次キャッシュ２００のデータが最新のデータであることを意味する。一方、ダーティ２２３が「０」を示している場合には、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータは一致していることを意味する。図中では、このダーティ２２３を「Ｄ」と略している。
【００３８】
リードアウトスタンディング２２５は、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００からのリード待ち状態である旨を示すリードアウトスタンディングビット（Ｒｅａｄ＿Ｏｕｔｓｔａｎｄｉｎｇ）を記憶するものである。このリードアウトスタンディング２２５が「１」を示している場合には、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００からのリード待ち状態が発生していることを意味する。一方、このリードアウトスタンディング２２５が「０」を示している場合には、そのインデックスに対応するキャッシュラインの何れにおいても、メインメモリ３００からのリード待ち状態が発生していないことを意味する。このようなリード待ち状態は、キャッシュラインのフィル処理の際に生じる。メインメモリ３００から該当するデータが読み出されて、キャッシュラインに書き込まれるとフィル処理は完了し、ＲＯＳがクリアされる。図中では、このリードアウトスタンディング２２５を「ＲＯＳ」と表記している。なお、リードアウトスタンディング２２５は、特許請求の範囲に記載の保留中表示部の一例である。
【００３９】
ライトアウトスタンディング２２６は、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００へのライト待ち状態である旨を示すライトアウトスタンディングビット（Ｗｒｉｔｅ＿Ｏｕｔｓｔａｎｄｉｎｇ）を記憶するものである。このライトアウトスタンディング２２６が「１」を示している場合には、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００へのライト待ち状態が発生していることを意味する。一方、このライトアウトスタンディング２２６が「０」を示している場合には、そのインデックスに対応するキャッシュラインの何れにおいても、メインメモリ３００へのライト待ち状態が発生していないことを意味する。このようなライト待ち状態は、キャッシュラインのライトバック処理の際に生じる。メインメモリ３００に対するライト指示に対して書込みが完了した旨の通知を受けることによりライトバック処理は完了し、ＷＯＳがクリアされる。図中では、このライトアウトスタンディング２２６を「ＷＯＳ」と表記している。なお、ライトアウトスタンディング２２６は、特許請求の範囲に記載の保留中表示部の一例である。
【００４０】
置換アルゴリズム２２７は、各インデックスにおいて新たなキャッシュラインを記憶する際に、何れのウェイを置換するかを判定するための情報を記憶するものである。この実施の形態では置換アルゴリズムとして何れの方式のものでも適用可能であるが、ここでは、最も近い時期に使用されていないキャッシュラインを追い出す手法（ＬＲＵ：Least Recently Used）を採用することを想定する。図中では、置換アルゴリズム２２７を「ＬＲＵ」と表記している。
【００４１】
このように、リードアウトスタンディング２２５とライトアウトスタンディング２２６を分けて管理することにより、確実にライト動作が完了してから次のフィル動作を行うことが可能となる。そのため、あるライトバック動作と、後続かつ同じアドレスのフィル動作との順序を保つことが可能となる。ここで前提とするような、ライト動作が完了した旨を示す応答を備えるプロトコルとして、例えばＡＸＩバスが挙げられる。
【００４２】
［二次キャッシュの動作］
図５は、本発明の実施の形態における二次キャッシュ２００の処理手順例を示す流れ図である。
【００４３】
まず、プロセッサ１００から二次キャッシュ２００へのアクセスがあると（ステップＳ９１１：Ｙｅｓ）、調停部２１０は、複数のプロセッサ１００−１乃至ｐのうちの何れのプロセッサ１００からのアクセスを許可するかを決定する（ステップＳ９１２）。そして、許可されたプロセッサ１００からのアクセスのアドレスに従ってタグ記憶部２２０が索引され、タグおよびその他の情報が読み出される（ステップＳ９１３）。
【００４４】
そのとき、読み出されたインデックスのリードアウトスタンディングビットまたはライトアウトスタンディングビットの何れかが「１」を示している場合には（ステップＳ９１４：Ｙｅｓ）、そのアクセスは保留され、調停処理（ステップＳ９１２）に戻る。一方、リードアウトスタンディングビットおよびライトアウトスタンディングビットの両者が「０」を示している場合には（ステップＳ９１４：Ｎｏ）、そのアクセスは許可され、タグの比較が行われるとともに、バリッドビット等が参照される（ステップＳ９１５）。これにより、キャッシュ動作が決定される（ステップＳ９１６）。その後、タグアドレス２２１、バリッド２２２、および、ダーティ２２３の各フィールドが更新される。
【００４５】
この流れ図から分かるように、この実施の形態では、タグ比較などの前の段階でリードアウトスタンディングビットおよびライトアウトスタンディングビットがチェックされるため、処理を大きく２段階に分けることができ、制御を簡略化することができる。
【００４６】
また、この一連の流れ図とは独立して、メインメモリ３００からの応答があると、対象のキャッシュラインのリードアウトスタンディングビットまたはライトアウトスタンディングビットがクリアされる。フィル処理の場合は二次キャッシュ２００内に、メインメモリ３００からのデータが格納される。
【００４７】
［二次キャッシュの状態遷移］
以下では、二次キャッシュ２００の状態遷移について各処理に分けて説明する。なお、本発明の実施の形態においては、Ｖを「０」にする際には必ずＤも「０」にするため、Ｖ＝０かつＤ＝１となる場合は発生し得ない。また、ＲＯＳ／ＷＯＳ＝０とは、リードアウトスタンディングビットおよびライトアウトスタンディングビットの両者が「０」であることを意味する。一方、ＲＯＳ／ＷＯＳ＝１とは、リードアウトスタンディングビットまたはライトアウトスタンディングビットの少なくとも何れか一方が「１」であることを意味する。また、各項目における「＊」は、その値や状態を問わないことを意味する。
【００４８】
図６は、本発明の実施の形態における二次キャッシュ２００のリード命令に対する状態遷移例を示す図である。このリード命令は、メインメモリ３００からデータの読出しを行うために、プロセッサ１００から発行される命令である。プロセッサ１００とメインメモリ３００との間には二次キャッシュ２００が接続されており、二次キャッシュ２００はプロセッサ１００から発行されたリード命令を受け取ると、以下の動作を行う。
【００４９】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、リード処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００５０】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、対応するキャッシュラインからリードが行われる。このとき、Ｄ＝１であったとしてもメインメモリ３００へのライトバックは行われない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００５１】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となる。したがって、タグアドレスの一致が検出されない場合には、ＬＲＵ法などによりリプレースすべきウェイが決定され、メインメモリ３００から該当するキャッシュラインのフィル動作が行われる。このとき、Ｄ＝１であれば、リプレース前にメインメモリ３００へのライトバックも行われる。なお、一致が検出されてもＶ＝０の場合には、新たにウェイを決定する必要はないため、そのキャッシュラインにおいてメインメモリ３００からフィル動作が行われるようにしてもよい。これらの場合において、メインメモリ３００に対してフィル動作が発行された際に、ＲＯＳ＝１に遷移する。また、ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００５２】
図７は、本発明の実施の形態における二次キャッシュ２００のライト命令に対する状態遷移例を示す図である。このライト命令は、メインメモリ３００に対してデータの書込みを行うために、プロセッサ１００から発行される命令である。プロセッサ１００とメインメモリ３００との間には二次キャッシュ２００が接続されており、二次キャッシュ２００はプロセッサ１００から発行されたライト命令を受け取ると、以下の動作を行う。
【００５３】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、ライト処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００５４】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、対応するキャッシュラインにライトが行われる。このとき、Ｄ＝１であったとしてもメインメモリ３００へのライトバックは行われない。ライトが行われた後にはＤ＝１の状態になる。
【００５５】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となる。したがって、タグアドレスの一致が検出されない場合には、ＬＲＵ法などによりリプレースすべきウェイが決定され、メインメモリ３００から該当するキャッシュラインのフィル動作が行われた後にライトが行われる。このとき、Ｄ＝１であれば、リプレース前にメインメモリ３００へのライトバックも行われる。なお、一致が検出されてもＶ＝０の場合には、新たにウェイを決定する必要はないため、そのキャッシュラインにおいてメインメモリ３００からフィル動作が行われるようにしてもよい。これらの場合において、メインメモリ３００に対してフィル動作が発行された際に、ＲＯＳ＝１に遷移する。また、ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００５６】
図８は、本発明の実施の形態における二次キャッシュ２００のフィル命令に対する状態遷移例を示す図である。このフィル命令は、メインメモリ３００から二次キャッシュ２００にキャッシュラインを読み出すための命令である。ただし、二次キャッシュ２００にヒットしている場合には、そのキャッシュラインをそのまま使用すればよいため、何も動作を行わない。
【００５７】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フィル処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００５８】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００５９】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となる。したがって、タグアドレスの一致が検出されない場合には、ＬＲＵ法などによりリプレースすべきウェイが決定され、メインメモリ３００から該当するキャッシュラインのフィル動作が行われる。このとき、Ｄ＝１であれば、リプレース前にメインメモリ３００へのライトバックも行われる。これらの場合において、メインメモリ３００に対してフィル動作が発行された際に、ＲＯＳ＝１に遷移する。また、ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００６０】
図９は、本発明の実施の形態における二次キャッシュ２００のフラッシュ命令アドレス型に対する状態遷移例を示す図である。フラッシュ命令は、キャッシュラインをメインメモリ３００に書き戻すための命令である。このフラッシュ命令アドレス型では、対象となるキャッシュラインはアドレスによって指定される。
【００６１】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フラッシュ処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００６２】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となる。このとき、Ｄ＝１であればライトバックが行われる。ライトバック動作が発行された際に、ＷＯＳ＝１に遷移する。
【００６３】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となり、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００６４】
図１０は、本発明の実施の形態における二次キャッシュ２００のフラッシュ命令インデックス型に対する状態遷移例を示す図である。このフラッシュ命令インデックス型では、対象となるキャッシュラインはインデックス値およびウェイ値によって指定される。したがって、比較器２３１乃至２３４による比較結果には依存せずに処理が行われる。
【００６５】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フラッシュ処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００６６】
指定されたインデックス値およびウェイ値に対応するエントリが、Ｖ＝１かつＤ＝１であればライトバックが行われる。ライトバック動作が発行された際に、ＷＯＳ＝１に遷移する。
【００６７】
また、指定されたインデックス値およびウェイ値に対応するエントリが、Ｄ＝０であればフラッシュする必要がないため、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００６８】
図１１は、本発明の実施の形態における二次キャッシュ２００のインバリデート命令アドレス型に対する状態遷移例を示す図である。インバリデート命令は、キャッシュラインを無効化するための命令である。このインバリデート命令アドレス型では、対象となるキャッシュラインはアドレスによって指定される。
【００６９】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フラッシュ処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００７０】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、無効化が行われる。これにより、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態はクリアされる。なお、この場合、Ｄ＝１であってもライトバックは行われない。
【００７１】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となり、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００７２】
図１２は、本発明の実施の形態における二次キャッシュ２００のインバリデート命令インデックス型に対する状態遷移例を示す図である。このインバリデート命令インデックス型では、対象となるキャッシュラインはインデックス値およびウェイ値によって指定される。したがって、比較器２３１乃至２３４による比較結果には依存せずに処理が行われる。
【００７３】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、インバリデート処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００７４】
指定されたインデックス値およびウェイ値に対応するエントリが、Ｖ＝１であれば無効化が行われる。これにより、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態はクリアされる。なお、この場合、Ｄ＝１であってもライトバックは行われない。
【００７５】
また、指定されたインデックス値およびウェイ値に対応するエントリが、Ｖ＝０であれば無効化する必要がないため、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００７６】
図１３は、本発明の実施の形態における二次キャッシュ２００のフラッシュアンドインバリデート命令アドレス型に対する状態遷移例を示す図である。フラッシュアンドインバリデート命令は、キャッシュラインをメインメモリ３００に書き戻した後に無効化するための命令である。このフラッシュアンドインバリデート命令アドレス型では、対象となるキャッシュラインはアドレスによって指定される。
【００７７】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フラッシュアンドインバリデート処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００７８】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、無効化が行われる。このとき、Ｄ＝１であれば無効化に先立ってライトバックが行われる。ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００７９】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となり、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００８０】
図１４は、本発明の実施の形態における二次キャッシュ２００のフラッシュアンドインバリデート命令インデックス型に対する状態遷移例を示す図である。このフラッシュアンドインバリデート命令インデックス型では、対象となるキャッシュラインはインデックス値およびウェイ値によって指定される。したがって、比較器２３１乃至２３４による比較結果には依存せずに処理が行われる。
【００８１】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、フラッシュアンドインバリデート処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００８２】
指定されたインデックス値およびウェイ値に対応するエントリが、Ｖ＝１であれば無効化が行われる。このとき、Ｄ＝１であれば無効化に先立ってライトバックが行われる。ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００８３】
また、指定されたインデックス値およびウェイ値に対応するエントリが、Ｖ＝０であれば無効化する必要がないため、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００８４】
図１５は、本発明の実施の形態における二次キャッシュ２００のアロケート命令に対する状態遷移例を示す図である。このアロケート命令は、指定されたアドレスに対応するキャッシュラインを二次キャッシュ２００に確保するための命令である。ただし、二次キャッシュ２００にヒットしている場合には、そのキャッシュラインをそのまま使用すればよいため、何も動作を行わない。なお、フィル命令と異なり、メインメモリ３００からのデータ読出しは行われない。
【００８５】
ＲＯＳまたはＷＯＳの少なくとも何れか一方が「１」である場合、アロケート処理は保留され、両者が「０」になるまで待機することになる。その間、他の命令による二次キャッシュ２００へのアクセスは受け付けられる。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００８６】
比較器２３１乃至２３４によって何れかのエントリにおいてタグアドレスの一致が検出された場合、Ｖ＝１であれば基本的にはヒット判定となり、何も動作を行わない。また、この場合、Ｖ、Ｄ、ＲＯＳ、ＷＯＳの状態に変更はない。
【００８７】
比較器２３１乃至２３４の何れにおいてもタグアドレスの一致が検出されない場合、または、一致が検出されてもＶ＝０の場合には、基本的にはミスヒット判定となる。したがって、タグアドレスの一致が検出されない場合には、ＬＲＵ法などによりリプレースすべきウェイが決定される。このとき、Ｄ＝１であれば、ウェイが確保される前にメインメモリ３００へのライトバックも行われる。ライトバック動作が発行された際には、ＷＯＳ＝１に遷移する。
【００８８】
［二次キャッシュの動作タイミング］
以下では、二次キャッシュ２００の動作タイミング例についてケース毎に分けて説明する。
【００８９】
図１６は、本発明の実施の形態におけるリード命令の動作の第１の例を示すタイミング図である。この例は、先行アクセスにおいてフィル処理が生じ、後続アクセスが保留状態となる場合を想定している。
【００９０】
プロセッサ＃１（１００−１）からリード命令が発行され（７１１）、二次キャッシュ２００のタグ制御部２３０においてミスヒットの判定がされたものと想定する（７１２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルの指示が発行される（７１３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１となる。
【００９１】
その後、プロセッサ＃２（１００−２）から同一キャッシュインデックスに対してリード命令が発行され（７１４）、二次キャッシュ２００のタグ制御部２３０においてＲＯＳ＝１であることが検出されたものとする。これにより、プロセッサ＃２からのリード命令に基づくリード処理は保留される（７１５）。
【００９２】
プロセッサ＃１からのリード命令に基づくフィル処理が完了すると（７１７）、対応するキャッシュインデックスにおいて、ＲＯＳ＝０となり、プロセッサ＃１からのリード命令について二次キャッシュ２００からリード動作が行われる（７１８）。また、プロセッサ＃２からのリード命令についても、二次キャッシュ２００からリード動作が行われる（７１９）。
【００９３】
図１７は、本発明の実施の形態におけるリード命令の動作の第２の例を示すタイミング図である。この例は、先行アクセスにおいてフィル処理およびライトバック処理が生じ、後続アクセスが保留状態となる場合を想定している。
【００９４】
プロセッサ＃１からリード命令が発行され（７２１）、二次キャッシュ２００のタグ制御部２３０においてミスヒットかつダーティである旨の判定がされたものと想定する（７２２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルおよびライトバックの指示が発行される（７２３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１およびＷＯＳ＝１となる。
【００９５】
プロセッサ＃２から同一キャッシュインデックスに対してリード命令が発行され（７２４）、二次キャッシュ２００のタグ制御部２３０においてＲＯＳ＝１およびＷＯＳ＝１であることが検出されたものとする。これにより、プロセッサ＃２からのリード命令に基づくリード処理は保留される（７２５）。
【００９６】
フィルおよびライトバックは同時に発行されるが、何れが先に完了するかは二次キャッシュ２００の外部の状態次第である。ここでは、フィルが先に完了するものと想定する（７２６、７２７）。フィルおよびライトバックの両者が完了すると、対応するキャッシュインデックスにおいて、ＲＯＳ＝０およびＷＯＳ＝０となり、プロセッサ＃１からのリード命令について二次キャッシュ２００からリード動作が行われる（７２８）。また、プロセッサ＃２からのリード命令についても、二次キャッシュ２００からリード動作が行われる（７２９）。
【００９７】
図１８は、本発明の実施の形態におけるリード命令の動作の第３の例を示すタイミング図である。この例は、先行アクセスにおいてフィル処理およびライトバック処理が生じ、フィル完了後の後続アクセスが保留状態となる場合を想定している。
【００９８】
プロセッサ＃１からリード命令が発行され（７３１）、二次キャッシュ２００のタグ制御部２３０においてミスヒットかつダーティである旨の判定がされたものと想定する（７３２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルおよびライトバックの指示が発行される（７３３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１およびＷＯＳ＝１となる。フィルおよびライトバックは同時に発行されるが、何れが先に完了するかは二次キャッシュ２００の外部の状態次第である。ここでは、フィルが先に完了するものと想定する（７３６）。フィル完了により、ＲＯＳ＝０となるが、ＷＯＳは「１」のままである。
【００９９】
フィル完了後に、プロセッサ＃２から同一キャッシュインデックスに対してリード命令が発行され（７３４）、二次キャッシュ２００のタグ制御部２３０においてＲＯＳ＝０およびＷＯＳ＝１であることが検出されたものとする。これにより、プロセッサ＃２からのリード命令に基づくリード処理は保留される（７３５）。
【０１００】
その後、ライトバックの両者が完了すると（７３７）、対応するキャッシュインデックスにおいて、ＲＯＳ＝０およびＷＯＳ＝０となり、プロセッサ＃１からのリード命令について二次キャッシュ２００からリード動作が行われる（７３８）。また、プロセッサ＃２からのリード命令についても、二次キャッシュ２００からリード動作が行われる（７３９）。
【０１０１】
図１９は、本発明の実施の形態におけるリード命令の動作の第４の例を示すタイミング図である。この例は、先行アクセスと後続アクセスとではインデックスアドレスが異なる場合を想定している。
【０１０２】
プロセッサ＃１からリード命令が発行され（７４１）、二次キャッシュ２００のタグ制御部２３０においてミスヒットかつダーティである旨の判定がされたものと想定する（７４２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルおよびライトバックの指示が発行される（７４３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１およびＷＯＳ＝１となる。
【０１０３】
一方、プロセッサ＃２からリード命令が発行されるが（７４４）、アクセス対象となるキャッシュインデックスが異なるものと想定する。この場合、二次キャッシュ２００のタグ制御部２３０においてそのキャッシュインデックスについてＲＯＳ＝０およびＷＯＳ＝０であることが検出されたものとする。そして、タグ制御部２３０においてキャッシュヒットが検出された場合（７４５）、プロセッサ＃２からのリード命令について二次キャッシュ２００からリード動作が行われる（７４９）。
【０１０４】
なお、プロセッサ＃１からリード命令に基づくフィルおよびライトバックの両者が完了すると（７４６、７４７）、それに対応するキャッシュインデックスにおいてもＲＯＳ＝０およびＷＯＳ＝０となる。これにより、プロセッサ＃１からのリード命令について二次キャッシュ２００からリード動作が行われる（７４８）。
【０１０５】
図２０は、本発明の実施の形態におけるリード命令の動作の第５の例を示すタイミング図である。この例は、先行アクセスと後続アクセスとではインデックスアドレスが異なり、両アクセスにおいてフィル処理およびライトバック処理が生じる場合を想定している。
【０１０６】
プロセッサ＃１からリード命令が発行され（７５１）、二次キャッシュ２００のタグ制御部２３０においてミスヒットかつダーティである旨の判定がされたものと想定する（７５２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルおよびライトバックの指示が発行される（７５３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１およびＷＯＳ＝１となる。
【０１０７】
一方、プロセッサ＃２からリード命令が発行されるが（７６１）、アクセス対象となるキャッシュインデックスが異なるものと想定する。この場合、二次キャッシュ２００のタグ制御部２３０においてそのキャッシュインデックスについてＲＯＳ＝０およびＷＯＳ＝０であることが検出されたものとする。そして、タグ制御部２３０においてミスヒットかつダーティである旨の判定がされたものと想定する（７６２）。このとき、二次キャッシュ２００の応答部２６０からメインメモリ３００に対してキャッシュラインのフィルおよびライトバックの指示が発行される（７６３）。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝１およびＷＯＳ＝１となる。
【０１０８】
このように、先行アクセスと後続アクセスとではインデックスアドレスが異なる場合、両アクセスについてフィルおよびライトバックの指示が発行される場合がある。この場合においても、フィルおよびライトバックの何れが先に完了するかは二次キャッシュ２００の外部の状態次第である。この例ではプロセッサ＃１からのリード命令についてはフィルが先に完了し（７５４）、その後でライトバックが完了した（７５５）ものとしている。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝０およびＷＯＳ＝０となり、プロセッサ＃１からのリード命令について二次キャッシュ２００からリード動作が行われる（７５６）。一方、この例ではプロセッサ＃２からのリード命令についてはライトバックが先に完了し（７６５）、その後でフィルが完了した（７６４）ものとしている。これにより、対応するキャッシュインデックスにおいて、ＲＯＳ＝０およびＷＯＳ＝０となり、プロセッサ＃２からのリード命令について二次キャッシュ２００からリード動作が行われる（７６６）。
【０１０９】
このように、本技術の実施の形態によれば、キャッシュインデックス毎にリードアウトスタンディング２２５およびライトアウトスタンディング２２６を設けることにより、二次キャッシュ２００におけるアクセス保留を簡易な構成により実現することができる。すなわち、タグ比較やバリッドやダーティの状態について処理を行う前段階においてアクセス保留するか否かを判断することができ、処理の複雑化を回避することができる。通常、キャッシュメモリの回路では、タグ記憶部からの読出し情報に基づいて動作を判定する箇所が、動作タイミングを保障する上で最も困難な部分である。本技術の実施の形態では、回路が単純化されているため、ミス・アンダー・ミスなどの複雑な動作を扱う場合においても、回路合成時のタイミング合致が容易となる。
【０１１０】
＜２．変形例＞
上述の実施の形態では、キャッシュインデックス毎にリードアウトスタンディング２２５およびライトアウトスタンディング２２６をそれぞれ設けていたが、両者をまとめて取り扱うことも可能である。これにより、リード処理に起因する保留とライト処理に起因する保留とを区別できなくなるが、ハードウェア構成およびその制御がより簡易なものとなる。なお、基本的な構成は上述の実施の形態と同様であるため、それらに関する詳細な説明は省略する。
【０１１１】
［タグ記憶部の構成］
図２１は、本発明の実施の形態の変形例におけるタグ記憶部２２０の構成例を示す図である。４ウェイに分かれた各キャッシュラインに、タグアドレス２２１、バリッド２２２、および、ダーティ２２３の各フィールドを備える点は、上述の実施の形態と同様である。そして、この変形例では、インデックス毎にアウトスタンディング２２４、置換アルゴリズム２２７の各フィールドを備える。置換アルゴリズム２２７は、上述の実施の形態と同様のものである。
【０１１２】
アウトスタンディング２２４は、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００からのリードまたはライト待ち状態である旨を示すアウトスタンディングビット（Ｏｕｔｓｔａｎｄｉｎｇ）を記憶するものである。このアウトスタンディング２２４が「１」を示している場合には、そのインデックスに対応するキャッシュラインの何れかにおいて、メインメモリ３００からのリードまたはライト待ち状態が発生していることを意味する。一方、このアウトスタンディング２２４が「０」を示している場合には、そのインデックスに対応するキャッシュラインの何れにおいても、メインメモリ３００からのリードまたはライト待ち状態が発生していないことを意味する。図中では、このアウトスタンディング２２４を「ＯＳ」と表記している。なお、アウトスタンディング２２４は、特許請求の範囲に記載の保留中表示部の一例である。
【０１１３】
この変形例におけるアウトスタンディング２２４は、上述の実施の形態におけるリードアウトスタンディング２２５とライトアウトスタンディング２２６とを論理和（ＯＲ）演算したものと考えることができる。したがって、キャッシュラインのフィル処理またはライトバック処理が発行された際にＯＳ＝１にセットされる。その後、フィル処理およびライトバック処理が完了し、そのキャッシュラインについて全てのリードまたはライト待ち状態が解消した際にＯＳ＝０にクリアされる。
【０１１４】
［二次キャッシュの動作］
図２２は、本発明の実施の形態の変形例における二次キャッシュ２００の処理手順例を示す流れ図である。上述の実施の形態では、ステップＳ９１４においてリードアウトスタンディング２２５とライトアウトスタンディング２２６の両者が「０」になっていることを条件として次の処理に進んでいたが、この変形例ではアウトスタンディング２２４のみが参照される。すなわち、アウトスタンディング２２４が「１」であればアクセスは保留され（ステップＳ９２４：Ｙｅｓ）、「０」であればタグ比較などが行われる（ステップＳ９２４：Ｎｏ）。
【０１１５】
このように、本発明の実施の形態の変形例によれば、ハードウェア構成およびその制御をより簡易なものとすることができる。
【０１１６】
なお、上述の実施の形態は本技術を具現化するための一例を示したものであり、実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本技術の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本技術は実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１１７】
なお、本技術は以下のような構成もとることができる。
（１）複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、
前記複数のインデックス毎に前記複数のタグアドレスに対応するデータをそれぞれ記憶するデータ記憶部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させ、前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記索引されたインデックスに含まれる前記複数のタグアドレスのうち前記第２のアドレス部分と一致したタグアドレスに対応するデータを前記データ記憶部から選択するデータ制御部と
を具備するキャッシュメモリ。
（２）前記保留中表示部は、リード処理に起因する保留中を示すリード起因保留中表示部と、ライト処理に起因する保留中を示すライト起因保留中表示部とを含み、
前記タグ制御部は、前記索引されたインデックスにおいて前記リード起因保留中表示部および前記ライト起因保留中表示部の少なくとも何れか一方が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させる
前記（１）に記載のキャッシュメモリ。
（３）複数マスタから共有される共有キャッシュメモリである前記（１）または（２）に記載のキャッシュメモリ。
（４）複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させ、前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出するタグ制御部と
を具備するキャッシュメモリ制御装置。
（５）複数のタグアドレスと１つの保留中表示部を含む複数のインデックスのうちの１つがアクセスアドレスの第１のアドレス部分によって索引されるタグ記憶部を備えるキャッシュメモリにおいて、前記索引されたインデックスに含まれる前記保留中表示部が保留中である旨を表示している場合には前記アクセスアドレスに係るアクセスを待機させる手順と、
前記索引されたインデックスに含まれる前記保留中表示部が保留中でない旨を表示している場合には前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたインデックスに含まれる前記複数のタグアドレスのそれぞれとを比較して一致するものを検出する手順と
を具備するキャッシュメモリ制御方法。
【符号の説明】
【０１１８】
１００  プロセッサ
１１０  一次キャッシュ
２００  二次キャッシュ
２１０  調停部
２２０  タグ記憶部
２２１  タグアドレス（ＴＡＧ）
２２２  バリッド（Ｖ）
２２３  ダーティ（Ｄ）
２２４  アウトスタンディング（ＯＳ）
２２５  リードアウトスタンディング（ＲＯＳ）
２２６  ライトアウトスタンディング（ＷＯＳ）
２２７  置換アルゴリズム（ＬＲＵ）
２３０  タグ制御部
２３１〜２３４  比較器
２３５  論理和演算器
２４０  データ記憶部
２５０  データ制御部
２５１、２５２  選択器
２６０  応答部
３００  メインメモリ
【図１】
2014186579.tif 000003
【図２】
2014186579.tif 000004
【図３】
2014186579.tif 000005
【図４】
2014186579.tif 000006
【図５】
2014186579.tif 000007
【図６】
2014186579.tif 000008
【図７】
2014186579.tif 000009
【図８】
2014186579.tif 000010
【図９】
2014186579.tif 000011
【図１０】
2014186579.tif 000012
【図１１】
2014186579.tif 000013
【図１２】
2014186579.tif 000014
【図１３】
2014186579.tif 000015
【図１４】
2014186579.tif 000016
【図１５】
2014186579.tif 000017
【図１６】
2014186579.tif 000018
【図１７】
2014186579.tif 000019
【図１８】
2014186579.tif 000020
【図１９】
2014186579.tif 000021
【図２０】
2014186579.tif 000022
【図２１】
2014186579.tif 000023
【図２２】
2014186579.tif 000024