JP2006099770A - シングルポートメモリを使用した命令キャッシュ - Google Patents

Abstract

【課題】マイクロプロセッサの性能を最適化するために、命令キャッシュが、命令フェッチユニットにおける処理と同じ高いスループットで、命令を配信できるようにする。
【解決手段】 本発明にかかる命令キャッシュは、シングルポートメモリ（２１０、２１５）と、前記命令キャッシュが受信する異なるタイプのキャッシュイベントを処理するように構成され、前記シングルポートメモリに対する前記キャッシュイベントの処理を調整するマルチステージパイプラインで構成されるキャッシュ制御ロジック（２０５）と、異なるステージが、前記キャッシュイベントの読み出しおよび書き込みまたはこれらのいずれかのステージとして事前に割り当てられ、前記キャッシュイベント間のアクセス衝突が最小にされる前記マルチステージパイプライン（２３０）とを備える。
【選択図】図２

Description

本発明は、シングルポートメモリを使用した命令キャッシュに関する。

プロセッサ速度がメモリ速度よりも速い割合で増加し続けるにつれて、メモリ速度はますます重要になってきた。
キャッシュは、メインメモリよりも小さく高速なタイプのバッファであり、通常、プロセッサとメインメモリとの間に配置される。
メモリ速度を改善するために、キャッシュは、プロセッサが次に必要とする可能性のある命令および／またはデータのコピーをメインメモリから記憶する。

キャッシュは、メインメモリからコピーされた命令をキャッシュラインに記憶することができる。
キャッシュラインは、１つまたは多数の連続した命令を記憶することができる。
各キャッシュラインは、コピーされた命令のメモリアドレスを特定するのに使用されるタグエントリを有することができる。
その最も単純な形式では、タグは、コピーされた命令を一意に特定するのに必要なアドレスの最小部分である。
タグの他の形式は、符号化されたアドレスを含むことができる。

要求された命令がキャッシュに存在する場合、キャッシュヒットが発生する。
要求された命令がキャッシュに記憶されていない場合、キャッシュミスが発生する。
通常、キャッシュミスが発生すると、プロセッサの実行ユニットは、プログラムの実行を続ける前に、要求された命令がメインメモリから取り出されるまで待機またはストールしなければならず、これによって、プロセッサの性能は劣化する。
キャッシュヒットおよびキャッシュミスの回数は、コンピュータシステムの性能の尺度として使用することができる。

マルチレベルキャッシュ構造は、Ｌ０キャッシュ（レベル０キャッシュ）やＬ１キャッシュ（レベル１キャッシュ）等の２つまたは３つ以上の独立したキャッシュメモリを有することができる。
これらのキャッシュメモリは、異なるサイズを有することができ、異なる速度またはメモリ待ち時間アクセス時間を有することができる。
通常、高レベルのキャッシュ（例えば、Ｌ１キャッシュ）は、低レベルのキャッシュ（例えば、Ｌ０キャッシュ）よりも多くの命令を記憶するが、アクセスは遅い。

マイクロプロセッサの性能を最適化するために、命令キャッシュは、可能な最低の待ち時間で、かつ、少なくとも、命令フェッチユニットが命令を処理できるのと同じ高いスループットで、命令を配信すべきである。
いくつかの従来のキャッシュ設計は、メモリへの複数の同時アクセスを可能にするマルチポートメモリを使用することによってこれらの目的を達成するように試みる。
例えば、これらの設計は、メモリアレイへの各ポートがそのメモリアレイのどのデータ部分にも独立してアクセスできる場合に、３ポートメモリアレイセルを使用してタグアレイを実施することができ、２ポートメモリアレイセルを使用してデータアレイを実施することができる。
このように、さまざまなタイプのアクセス、および、ヒット、フィル、スヌープ等のさまざまなタイプのキャッシュイベントを他のイベントを干渉することなく処理することができる。
しかしながら、この手法では、設計の複雑度が高くなり、チップ面積が大きくなり、かつ、電力消費が大きくなる。

明細書に組み込まれて明細書の一部を構成する添付図面は、本発明のさまざまな態様のさまざまなシステム例、方法例、および他の実施の形態例を示す。
図に示した要素の境界（例えば、ボックス、数群のボックス、または他の形状）は、境界の一例を表すことが理解されよう。

１つの要素を複数の要素として設計することもできるし、その複数の要素を１つの要素として設計することもできることが当業者には理解されよう。
別の要素の内部コンポーネントとして示された要素は、外部コンポーネントとして実施することもできるし、その逆も同様である。
さらに、要素は、一定の縮尺で描かれていないことがある。

本明細書のさまざまな例で説明するように、キャッシュアーキテクチャならびに他のシステムおよび方法には、キャッシュイベントを処理するオペレーションシーケンスを定義する機能的なマルチステージパイプラインが提供される。
このパイプラインを使用することによって、アクセス衝突を最小にすることができ、キャッシュのメモリアレイを単純にすることができる。
このキャッシュアーキテクチャ例によって、シングルポートタグ／データメモリを使用することが可能になる。
これらのシングルポートタグ／データメモリは、マルチポートメモリよりも単純であり、かつ、小さい。
また、キャッシュのシングルポートメモリは、フルスループット、および、マルチポート設計とほぼ同じ低さのアクセス待ち時間を提供することもできる。

アクセスがオペレーションによって要求されると、可能なキャッシュオペレーションは、本明細書で説明するキャッシュ構成例の１つまたは複数に基づいて、シングルポートタグ／データアレイ、および、キャッシュ内の他のアクセス制限された資源にアクセスすることができる。
アクセス制限された１つの資源には、要求アドレスキューが含まれる。
キャッシュオペレーションがマルチステージパイプラインに沿って開始されると、キャッシュオペレーションは、ストールも、遅延も、実行中の可能性のある他のオペレーションとの衝突もなく、一定のタイミングシーケンスで完了する。

以下は、本明細書で使用される選択された用語の定義を含む。
これらの定義は、用語の範囲内に入り、かつ、実施態様（インプリメンテーション）に使用できるコンポーネントのさまざまな例および／または形式を含む。
これらの例は、限定するためのものではない。
用語の単数形および複数形の双方が定義の範囲内に入ることができる。

「ロジック」には、本明細書で使用されるように、機能（複数可）または動作（複数可）を実行し、かつ／または、別のロジック、方法、および／もしくはシステムからの機能もしくは動作を引き起こすハードウェア、ファームウェア、ソフトウェア、および／またはそれぞれの組み合わせが含まれるが、これらに限定されるものではない。
例えば、所望の用途またはニーズに基づいて、ロジックには、ソフトウェア制御のマイクロプロセッサ、特定用途向け集積回路（ＡＳＩＣ）のようなディスクリートロジック、アナログ回路、デジタル回路、プログラミングされたロジックデバイス、命令を収容するメモリデバイス等が含まれ得る。
ロジックは、１つまたは複数のゲート、ゲートの組み合わせ、１つまたは複数のチップ、または他の回路コンポーネントを含むことができる。
また、ロジックは、全面的にソフトウェアとして実施することもできる。
複数の論理ロジックが説明される場合、それら複数の論理ロジックを１つの物理ロジックに組み込むことが可能な場合がある。
同様に、単一の論理ロジックが説明される場合、その単一の論理ロジックを複数の物理ロジック間に分散させることが可能な場合がある。

「動作可能接続（operable connection）」、すなわち、エンティティが「動作可能に接続」される接続は、信号、物理通信、および／または論理通信を送信および／または受信することができる接続である。
通常、動作可能接続には、物理インターフェース、電気インターフェース、および／またはデータインターフェースが含まれるが、動作可能接続には、これらの異なる組み合わせ、または、動作可能制御（operable control）を可能にするのに十分な他のタイプの接続も含まれ得ることに留意すべきである。
例えば、２つのエンティティは、相互に信号を直接通信可能にすることによって、または、１つまたは複数の中間エンティティを通じて通信可能にすることによって、動作可能に接続することができる。
この中間エンティティは、プロセッサ、オペレーティングシステム、ロジック、ソフトウェア、もしくは他のエンティティのようなものである。
動作可能接続を作成するのに、論理通信チャネルおよび／または物理通信チャネルを使用することができる。

「信号」には、本明細書で使用されるように、１つまたは複数の電気信号もしくは光信号、アナログ信号もしくはデジタル信号、データ、１つまたは複数のコンピュータ命令もしくはプロセッサ命令、メッセージ、ビットもしくはビットストリーム、または、受信、送信、および／もしくは検出が可能な他の手段が含まれるが、これらに限定されるものではない。

以下の詳細な説明のいくつかの部分は、データビットに対するオペレーションのアルゴリズム表現およびシンボル表現に関して提示される。
これらの説明および表現は、当業者が自身の作業の内容を他者に伝達するのに使用される手段である。
アルゴリズムは、本明細書では一般に、結果を生み出すオペレーションシーケンスであると考えられる。
オペレーションには、物理量の物理的な操作が含まれ得る。
必ずしもそうではないが、通例、物理量は、ロジック等における記憶、転送、結合、比較、およびそれ以外の操作が可能な電気信号または磁気信号の形を取る。

主として、共通に使用されるとの理由から、これらの信号をビット、値、要素、シンボル、文字、用語、数字等と呼ぶことが時に便利であることが分かっている。
しかしながら、これらの用語および類似の用語は、適切な物理量に関連付けられることになり、これらの量に適用された便利なラベルにすぎないことに留意すべきである。
特に別段の指定がない限り、この説明の全体を通じて、処理、計算、保守、算出、決定等のような用語は、物理（電子）量として表されたデータを操作および／または変換するコンピュータシステム、ロジック、プロセッサ、または同様の電子デバイスの動作およびプロセスを指すことが理解されよう。

システム例、方法例、および他の実施の形態例を、本明細書では、キャッシュメモリ、キャッシュメモリの制御、ならびに、キャッシュメモリを含むマイクロプロセッサおよび計算デバイスに関して説明する。
一例のシステムは、マルチステージパイプラインで構成できるキャッシュ制御ロジックを含む。
マルチステージパイプラインは、キャッシュイベント間のアクセス衝突を最小にするために、キャッシュイベントごとのオペレーションシーケンスを事前に定義する１組のステージを含むことができる。
キャッシュイベントには、例えば、検索要求、フィル要求、およびスヌープ（例えば、照会要求（inquiry request）および無効要求（invalidation request））が含まれ得る。
キャッシュ制御ロジックのシステム例および方法例では、マルチポートメモリよりも単純でかつ小さくすることができるシングルポートキャッシュメモリを実施することができる。

図１には、キャッシュ制御ロジック１０５、および、Ｌ１キャッシュ１１０のような命令キャッシュメモリを含むキャッシュシステム１００の一例が示されている。
キャッシュシステム１００は、Ｌ０キャッシュ１１５やＬ２キャッシュ１２０等の複数のキャッシュメモリおよびメモリ１２５も含むことができる。
これらの複数のキャッシュメモリおよびメモリ１２５は、マイクロプロセッサ１３０および命令フェッチユニット１３５に動作可能に接続される。
Ｌ０、Ｌ１、およびＬ２は、それぞれレベル０キャッシュメモリ、レベル１キャッシュメモリ、およびレベル２キャッシュメモリを表す。
キャッシュシステム１００が特定の個数のキャッシュメモリまたは階層に限定されないこと、および、キャッシュ制御ロジック１０５が他のキャッシュメモリと共に動作するように構成できることが理解されよう。
また、図１はコンポーネントの論理構成を示し、また、キャッシュメモリ１１０、１１５、および１２０の１つまたは複数は、所望の設計の検討に基づいてマイクロプロセッサ１３０と共にオンチップであってよいし、なくてもよいことも理解されよう。

一構成例では、Ｌ１キャッシュ１１０は、シングルポートメモリセルを使用して実施される命令キャッシュである。
このメモリセルは、命令を記憶するように構成されたデータアレイ、および、そのデータアレイに記憶された命令へのアドレスを記憶するように構成されたタグアレイに配列することができる。
データアレイは、タグアレイとは独立に動作するように構成することができる。
例えば、一方のアレイは読み出し中であると同時に、他方のアレイが書き込み中またはアイドルである場合がある。
キャッシュ制御ロジック１０５は、命令キャッシュ１１０が受信できる異なるタイプのアクセス要求（キャッシュイベントとも呼ばれる）を処理するように構成することができる。
キャッシュ制御ロジック１０５は、命令キャッシュ１１０のシングルポートメモリセルに対するアクセス要求の処理を調整するマルチステージパイプライン（図示せず）を含むことができる。

一例では、マルチステージパイプラインは、クロックに従って順次循環される複数のステージで定義することができる。
さまざまなタイプのアクセス要求について、メモリセルまたは他の資源の読み出しまたは書き込みを行う異なるステージを事前に割り当て、それによって、それらアクセス要求間の衝突を最小にすることができる。
以下の例でさらに詳細に説明するように、マルチステージパイプラインは、キャッシュイベントごとのオペレーションシーケンスを定義する１組のステージを含むことができる。
換言すると、キャッシュメモリ１１０内のシングルポートメモリセルまたは他の資源にアクセスしようとしているキャッシュイベント間のアクセス衝突を最小にするために、ステージは、異なるタイプのキャッシュイベントを異なるステージで処理するシーケンスを定義することができる。

例えば、Ｌ１キャッシュメモリ１１０が検索要求およびフィル要求を同時に受信すると仮定する。
各要求は、その要求を達成するために実行される特定のオペレーションシーケンスを有する。
双方の要求が同時にキャッシュメモリにアクセスしようとすると、衝突が発生する可能性がある。
パイプラインは、各タイプの要求のさまざまなオペレーションに割り当てられた、選択されたステージを有するように設計することができる。
ステージ割り当てによって、読み出しアクセスおよび／または書き込みアクセスが、異なるキャッシュイベントについて発生する可能性がある場合を調整することができ、異なるキャッシュイベントについて同じステージで発生した読み出し／書き込みアクセスが削減または回避される。

図１をさらに参照して、キャッシュシステム１００の一般的な説明を以下のように記載することができる。
キャッシュシステム例１００は、異なるサイズのキャッシュメモリを有するマルチレベルキャッシュ設計を含むことができる。
この設計は、小さい方のキャッシュをマイクロプロセッサ１３０にオンチップで配置すること、および、大きい方のキャッシュをオフチップで配置することを含むことができる。
データがマイクロプロセッサ１３０によって要求されると、第１レベルのキャッシュ（例えば、Ｌ０キャッシュ１１５）がマイクロプロセッサ１３０によって最初にアクセスされて、メモリアクセス要求について真のキャッシュヒットが得られるかどうかが判断される。
真のキャッシュヒットがＬ０キャッシュ１１５で得られていない場合には、第２レベルのキャッシュ（例えば、Ｌ１キャッシュ１１０）について判断が行われる。
メモリアクセス要求がキャッシュメモリの１つによって満たされるまで、同様のことが行われる。
要求されたアドレスがキャッシュレベルのいずれにも見つからない場合には、マイクロプロセッサ１３０は、メモリアクセス要求を満たそうとして、システムのメモリ１２５へ要求を送信することになる。
キャッシュ制御ロジック１０５は、示した例では、Ｌ１キャッシュ１１０が受信したアクセス要求を制御するように構成される。

図２には、キャッシュ制御ロジック２０５を含む命令キャッシュシステム２００の一構成例が示されている。
このキャッシュ制御ロジック２０５は、図１のＬ１キャッシュ１１０およびキャッシュ制御ロジック１０５の代わりに実施することができる。
命令キャッシュ２００は、タグアレイ２１０およびデータアレイ２１５を含むことができる。
タグアレイ２１０は、タグとしても知られている制御データを記憶するように構成される。
この制御データは、所望のアドレス（例えば、メモリアクセス要求に必要とされるアドレス）がキャッシュデータアレイ２１５内に含まれているかどうかを示す。
動作時に、メモリアクセス要求がキャッシュ２００によって受信されると、まず、その要求についてタグが取得される。
所望のアドレスがデータアレイ２１５内に含まれることをこのタグが示す場合には、データアレイ２１５がアクセスされて、メモリアクセス要求が満たされる。
マイクロプロセッサがキャッシュにアイテムを要求し、そのアイテムがキャッシュに実際に存在する場合に、真のキャッシュヒットが発生する。
アイテムがキャッシュに存在しない場合に、キャッシュミスが発生する。
メモリアクセス要求は、ＣＰＵ要求または検索要求とも呼ばれる。

キャッシュ２００は、シングルポートメモリを使用して実施され、これは、１つのアクセス要求のみが、所与のクロックサイクル内において、タグアレイ２１０および／またはデータアレイ２１５内で発生する可能性があることを意味する。
しかしながら、複数のアクセス要求がキャッシュ２００によって受信される可能性があり、同時に保留状態になり、かつ／または、パイプラインに存在する可能性がある。
アクセス要求例が参照符号２２０によって示される。
このアクセス要求例には、ＣＰＵ要求（検索要求）、フィル、およびスヌープが含まれ得る。
ＣＰＵ要求は、ＣＰＵ／マイクロプロセッサがデータを必要として、ＣＰＵがキャッシュ２００に要求を行った時に生成される。
このタイプの要求を処理するために、タグアレイ２１０がチェックされて、データがデータアレイ２１５に存在するかどうかが調べられる。
データが存在しない場合、フィル要求をキャッシュ構造の高いレベルへ送信して、欠けているデータを取り出し、取り出したデータをフィルラインを介してデータアレイ２１５へ書き込むことができる。

スヌープ要求は、キャッシュに記憶されたデータが古くなった時、および、キャッシュに記憶されたデータをキャッシュから除去する必要がある時のさまざまな時に実行することができる。
スヌープ要求は、照会オペレーションおよび無効オペレーションの２つの個別のオペレーションを含むことができる。
古い選択されたデータについて、スヌープ照会は、タグメモリアレイ２１０を読み出して、その古いデータが存在するかどうかを判断する。
これは、スヌープ照会がキャッシュによって受信された時、常に実行される。
古いデータが存在する場合、無効オペレーションがタグメモリアレイ２１０に書き込まれ、データが無効であることが示される。
スヌープ照会がキャッシュで「ヒット」する場合にのみ、無効オペレーションは実行される。

スヌープ要求の実行中、照会オペレーションは、タグアレイ２１０においてスヌープのアドレスにより決定された「セット」内のタグエントリのすべてを読み出して、「ウェイ」がもしあれば、どの「ウェイ」が、現在、古い所与のアドレスのデータを含んでいるかを決定することができる。
次に、無効オペレーションは、その特定のキャッシュエントリのタグを変更して、そのエントリに「非有効」状態をマーキングすることができる。
キャッシュ状態例は、図８および図９を参照して説明する。
一般的なキャッシュ設計では、無効オペレーションはわずかな時間で実行される。
したがって、ほとんどのスヌープ要求は、タグメモリアレイ２１０への単一のアクセスのみを必要とする。
異なるタイプのキャッシュイベントのアクセス要件の知識は、パイプラインステージをキャッシュイベントへ割り当てる際に役立つ。
後述するように、ステージ割り当ては、処理の順序を制御することができ、キャッシュにアクセスしようとしているキャッシュイベント間のアクセス衝突の削減および／または回避に役立つ。

図２をさらに参照して、キャッシュ制御ロジック２０５は、キャッシュ２００のシングルポートメモリを通じて処理されるキャッシュイベント／アクセス要求２２０の処理を制御するように構成される。
キャッシュ制御ロジック２０５は、１つまたは複数のアクセス要求２２０を選択して処理することができるマルチプレクサ２２５のような選択ロジックを含むことができる。
パイプラインロジック２３０は、マルチステージパイプラインを実施して、アクセス要求２２０に関連したオペレーションシーケンス２３５を制御することができる。
キャッシュ制御ロジック２０５が、現在のステージに基づいて、どの動作を実行できるかを決定できるように、パイプラインロジック２３０は、各タイプのアクセス要求の処理順序を特定する１組のステージを定義することができる。
タグアレイ２１０および／またはデータアレイ２１５に対するアクセス要求がパイプラインの異なるステージで行われるように、オペレーションシーケンス２３５はステージに割り当てられる。

例えば、検索要求およびスヌープ照会は、共にタグアレイ２１０に対する読み出しアクセスを実行する。
検索要求用に定義されたオペレーションシーケンス２３５およびスヌープ照会用に定義されたオペレーションシーケンス２３５は、タグアレイ２１０に対する読み出しアクセスが２つのタイプのオペレーションについてパイプラインの異なるステージで行われるようにパイプラインに割り当てることができる。
したがって、検索要求およびスヌープ照会の双方をパイプラインステージに基づいて同時に処理する時、タグアレイに対するアクセス要求は、異なる時刻（例えば、異なるクロックサイクル）で行われ、それによって、アクセス衝突が回避される。
アクセス衝突を回避するか、または、最小にするために、ステージへの同様の割り当てを他のオペレーションおよび他のアクセス要求についても行うことができる。
マルチステージパイプラインおよび事前に割り当てられたオペレーションシーケンスのさらに詳細な例は、図３〜図７を参照して説明する。

別の例では、キャッシュ２００は、マルチプレクサ２２５に動作可能に接続されたバッファロジック（図示せず）を含むことができる。
マイクロプロセッサは、クロックサイクルごとにアクセス要求２２０を送信でき、ＣＰＵ要求ラインは複数のライン（例えば、複数のデータ要求用に８本のライン）を有することができるので、複数の要求が処理のためにマルチプレクサ２２５を通じて選択されるまで、バッファロジックは、それら複数の要求のキューを作るのに使用することができる。
上述した４サイクルパイプライン例に基づいて、新たなＣＰＵ要求を４サイクルごとに開始することができ、したがって、４クロックサイクルごとにバッファロジックからＣＰＵ要求を選択することが可能になる。

図２をさらに参照して、キャッシュ制御ロジック２０５で構成することができるパイプライン構造の一例が４ステージパイプラインである。
この例は、１つのステージが１クロックサイクルの間に実行されることに基づくことになる。
したがって、このパイプラインは、４サイクルパイプラインとも呼ばれる。
これよりも多くの量のステージまたは少ない量のステージでパイプラインを実施できることが理解されよう。

一構成例では、ステージの個数は、キャッシュのデータバスと全幅のキャッシュラインとのサイズ比に基づくことができる。
例えば、全幅のキャッシュラインが１，０２４ビットのデータである場合、さまざまなレベルのキャッシュメモリ間に全幅のデータバスを有することが望ましい場合がある。
１つのオプションは、データの伝送を小さなサイズに細分して、データバス２４０や２４５等の小さなバスを使用できるようにすることである。
マルチプレクサをデータバス２４０および２４５と共に使用して、データアレイ２１５に向かうデータバス幅およびデータアレイ２１５から出るデータバス幅を拡張することができる。
データバスは、全キャッシュラインの４分の１（１／４）となるように構成されると、２５６ビット幅となる。
これは、１つのキャッシュラインのデータ転送を実行するのに４クロックサイクルを要することを意味する。
データ転送を実行するのに４サイクルを要するので、このマルチステージパイプラインは、４サイクルに対応する４つのステージで構成することができる。
この例に基づいて、後の例で説明するようなデュアルマルチステージパイプラインを含む異なる個数のサイクルおよび異なる個数のステージを実施できることが理解されよう。

４ステージパイプライン構造例を使用すると、システム２００は、４クロックサイクルを有し、その４クロックサイクルにおいて、所与のアクセス要求に関連したさまざまなオペレーションを実行する。
前述したように、各アクセス要求またはキャッシュイベントは、その要求を完了するために実行されるオペレーションシーケンスを含む。
このオペレーションシーケンスは、（例えば、割り当てられた開始ステージに基づいて）パイプライン内の選択されたステージに割り当てることができる。
この選択されたステージは、キャッシュ制御ロジック２０５が、ＣＰＵ要求、フィル、およびスヌープ照会をすべて同時にパイプラインに有すること、および、異なる時刻にタグアレイ２１０および／またはデータアレイ２１５にアクセスする各アクセス要求をパイプライン内に有することを可能にするものである。
このように、アクセス要求間の衝突を回避できるか、または、少なくとも最小にすることができる。

図３〜図７を参照して、パイプラインタイミング図のさまざまな例が示されている。
これらの図では、パイプライン構造例がデュアル４ステージパイプラインを実施する。
このデュアル４ステージパイプラインは、４つのステージを有する１次パイプラインおよび４つのステージを有する２次パイプラインを含む。
前述したように、４ステージパイプラインは、データバスが全幅のキャッシュラインの１／４である設計に基づく。
これらのタイミング図は、キャッシュイベントの処理時に使用できる処理順序の例を表す。

パイプライン２３０のステージを制御するように状態マシン（図示せず）を構成することができる。
例えば、状態マシンは、任意の所与の時刻に１次パイプラインの１つのステージにのみ存在することができる。
また、状態マシンは、所与の時刻に２次パイプラインの１つのステージにのみ存在することもできる。
しかしながら、１次パイプラインおよび２次パイプラインの双方がアクティブである場合、それらパイプラインは、対応するステージに同時に存在する。
例えば、それらパイプラインが、共にそれらの第２のステージに存在することがあるが、一方のパイプラインがその第２のステージに存在すると同時に、他方のパイプラインがその第３のステージに存在することはできない。
したがって、新しいオペレーションが到着した時に、キャッシュ２００がキャッシュオペレーションを実行している場合、その新しいオペレーションは、現在のステージと適切に調整を行うために１つまたは複数のサイクルを待機し、そして１次パイプラインに入ることが必要な場合がある。
新しいオペレーションが到着した時に、キャッシュ２００がアイドルである場合、その新しいオペレーションは、直ちに開始して、１次パイプラインに入ることができる。

図３〜図７のそれぞれは、選択されたキャッシュイベントのオペレーションシーケンス例、および、パイプラインの選択されたステージへのそれらオペレーションの割り当て例を示している。
例えば、図３は、検索要求の結果が「ヒット」になるパイプラインタイミング図の例３００を示している。
図４は、検索要求の結果が「ミス」になるパイプラインタイミング図の例４００を示している。
図５は、スヌープ照会に関連付けることができるパイプラインタイミング図の例５００を示している。
図６は、スヌープ無効オペレーションに関連付けることができるパイプラインタイミング図の例６００を示している。
図７は、フィル要求に関連付けることができるパイプラインタイミング図の例７００を示している。
所望のキャッシュシステムの実施態様（インプリメンテーション）に応じて、選択されたキャッシュイベントに関連したオペレーションは、図示したオペレーション例と異なる場合があることが理解されよう。
このシステムは、図示したオペレーションにもステージの割り当てにも限定されるように意図されていない。

キャッシュおよびその制御ロジック用の回路機構または他のロジックを設計する際の考慮すべき事項の一例は以下のようになることがある。
フィル要求または検索要求の場合、キャッシュシステムは、４つのクロックサイクルを使用して、データアレイが一旦アクセスされる前または後にデータを組み立てる。
したがって、１次４サイクルパイプラインは、この考慮すべき事項から設計することができる。
例えば、図３の検索要求（ヒット）タイミング図を参照すると、タグは、１次パイプラインステージＰ１のブロック３１５で読み出され、データアレイは、１次パイプラインステージＰ２のブロック３３０で読み出され、次いで、要求側のデバイス（例えば、Ｌ０キャッシュ）へデータを送出するのに４クロックサイクル（ステージ）を要する。
データの送信に使用される４ステージは、２次パイプラインステージＳ０〜Ｓ３に示されている。
以下にさらに詳細に説明するように、異なるアクセス要求のオペレーションは、パイプラインのさまざまなステージに割り当てられ、その結果、タグアレイおよび／またはデータアレイへのアクセスが重ならないようにされ、したがって、互いに衝突しないようにされる。
あるいは、少なくとも、潜在的な衝突が存在する場合には、その衝突が頻繁に発生しないように設計することができる。

１次パイプラインステージおよび２次パイプラインステージの用語法は、前述した４サイクル設計に基づく。
この設計では、システムは、４クロックサイクルごとにキャッシュに対して新しいアクセスを開始することができる。
したがって、パイプライン構造の１つの見方は、２つのグループが４サイクルの間持続する４ステージパイプラインとするものである。
換言すると、これは、システム（例えば、キャッシュ制御ロジック１０５、２０５）が、２次パイプラインと重なる新しい１次パイプラインを開始できることを意味する。
図３〜図７の例に示すように、各ステージＰ０〜Ｐ３およびＳ０〜Ｓ３は、各ステージが１クロックサイクルの間持続する異なるステージを表す。
１次ステージＰ０〜Ｐ３および２次ステージＳ０〜Ｓ３は、４クロックサイクルにわたって順に発生する連続したステージを表す。

図３〜図７のタイミング図を参照すると、各アクセス要求のオペレーションへのパイプラインステージ割り当て例が、アクセス衝突を回避し、かつ／または、最小にする各アクセス要求の処理順序を作成できることが分かる。
例えば、１つまたは複数のタイミング図を重ね合わせることによって、各要求の読み出しアクセスおよび書き込みアクセスが、異なるステージで行われ、したがって、互いに衝突することはない。
例えば、図３に示す検索要求「ヒット」図を、図５に示すスヌープ照会と比較し、かつ、双方の要求が同時に処理されていると仮定することによって、検索要求については、タグは、１次ステージＰ１（ブロック３１５）で読み出し中となり、スヌープ要求については、タグは、１次ステージＰ３（ブロック５０５）で読み出し中となる。
また、図７に示すフィル要求のタイミング図を重ね合わせ、かつ、２次パイプラインが１次パイプラインと重なることができることを思い出すことによって、フィル要求は、２次ステージＳ２（１次ステージＰ２と重なる）でタグ書き込みを実行し、検索「ヒット」図のタグ読み出しにも、フィル要求図のタグ読み出しにも衝突しない。

したがって、パイプラインステージへのオペレーションの割り当て例を使用すると、検索要求（ヒットまたはミスのいずれか）、フィル要求、およびスヌープ照会の可能な組み合わせは、異なるステージでタグにアクセスするので、それら組み合わせを同時に行うことを可能にする異なるステージサイクルでタグアレイの完全利用を達成することができる。
したがって、選択された事前に割り当てられるオペレーションシーケンスでは、４サイクルパイプラインによって、検索要求、フィル要求、およびスヌープ照会を同時に行うことが可能になり、パイプラインを使用することによって、各要求が、互いに衝突しない一意のサイクルの期間中に命令キャッシュのタグアレイおよび／またはデータアレイにアクセスすることが保証される。
もちろん、いくつかの割り当てパターンの結果、潜在的な衝突が生じる場合があることが理解されよう。

例えば、図３〜図７に示すステージ割り当て例に基づいて、図６に示すスヌープ無効図６００は、タグ読み出し（ブロック６０５）が１次ステージＰ１で行われるステージ割り当てを含む。
このタグ読み出しは、同じく１次ステージＰ１に割り当てられる図３に示す検索要求のタグ読み出し（ブロック３１５）と衝突する可能性がある。
これらの要求の双方が同時に受信された場合、それら双方の要求は、同じサイクル（例えば、ステージＰ１）で同じ資源（例えば、タグアレイ）を使用しようとするので、一方の要求の処理をブロックするか、または、遅延させる必要がある。
キャッシュ制御ロジックが、この状況で検索要求を遅延させるように構成されている場合、検索要求は、パイプラインがそのステージを循環するまでの４クロックサイクルの間だけ遅延されることになる。
この期間中、スヌープ無効が処理され、パイプラインはステージＰ０に戻る。
ステージＰ０は、検索要求の開始ステージである。
スヌープ無効オペレーションは稀なイベントであり、この衝突は稀にしか起こらないので、このタイプの衝突はいくつかの設計では許容可能とすることができる。
したがって、ステージ割り当ては、オペレーションの一般的な発生に基づいて、要求の処理を最適化するように行うことができる。
その結果、潜在的な衝突を最小にすることができる。

図３を再び参照して、以下は、キャッシュ「ヒット」になる検索要求について実行されるオペレーション例の説明である。
このステージ割り当て例では、検索要求は、ステージＰ０で処理を開始するように割り当てられる。
これは、パイプラインがステージＰ０にいる時にのみ保留中の検索要求が処理を開始することを意味する。
動作時に、現在のパイプラインステージがＰ２であり、検索要求が受信されるか、または、処理されるため保留中である場合、検索要求は、パイプラインステージが循環してステージＰ０に巡ってくるまで待機することになる。
キャッシュのこの処理制御は、前述したようなキャッシュ制御ロジック（例えば、キャッシュ制御ロジック１０５、２０５）に構成される。
この例におけるパイプラインは４ステージで構成されるので、検索要求は、多くとも３クロックサイクルの間、遅延されることがある。

検索要求がステージＰ０で開始されると、ステージＰ０で実行されるオペレーションは、「要求アドレス多重（request address mux）」３０５およびプリデコード３１０を含むことができる。
「要求アドレス多重」３０５は、アドレス要求が、命令キャッシュのタグアレイの前に配置されたマルチプレクサによって受信されることを指す。
マルチプレクサの例は、図２にＭＵＸ２２０として示されている。
プリデコードオペレーション３１０は、マルチビットアドレスの場合がある要求されたアドレスを取り込むこと、および、そのアドレスをタグアレイ内の可能なエントリに変換することを含む。
例えば、１０ビットのバイナリアドレスを使用して、タグアレイの１０２４セットの１つを選択することができる。
プリデコードオペレーションを物理的に実施する１つの方法は、各タグエントリについて個別のワードラインを有し、１０ビットアドレスを１０２４ワードラインに変換することである。
もちろん、異なるサイズのアドレスおよびタグアレイエントリを使用することもできる。

ステージＰ１では、タグ読み出しオペレーション３１５が実行される。
ここで、タグアレイに対するアクセスが行われる。
キャッシュはシングルポートメモリで構成されるので、１ステージにつき、タグアレイに対する１つのアクセスのみを行うことができる。
これを１つの条件として使用すると、他のキャッシュイベントのオペレーションシーケンスを、前述したようにアクセス衝突を最小にするようにステージに割り当てることができる。

キャッシュの構成に応じてタグアレイアクセスを処理している間、さまざまな動作を行うことができる。
例えば、ワードラインをデコードすることができる。
このデコードは、ステージＰ０からのプリデコードオペレーション３１０と共に実行することができる。
ワードラインがデコードされた後、１ワードラインが選択されてアクティブにされ、そのラインは、要求されたアドレスについて、タグアレイのどのエントリを読み出すのかを特定する。
タグアレイからデータを読み出すのに、１つまたは複数のセンス増幅器（図示せず）を使用することができる。
センス増幅器は、タグアレイの各メモリセルから駆動される小さな信号を増幅する物理回路であり、それら信号をより大きく、より使用可能な値に増幅する。
次に、タグエントリから読み出された情報を使用して、要求されたアドレスがキャッシュのデータアレイに実際に見つかったかどうかを判断することによって、照合オペレーションを実行することができる。

一構成例では、キャッシュは、関連した複数の「ウェイ」で構成することができ、例えば、８つのウェイで構成することができる。
これは、キャッシュに要求されているどの特定のデータ部分も、キャッシュの特定のセットを含む８つのロケーションのいずれかに配置できることを意味する。
タグメモリを読み出す時、１つの特定のセット内のロケーションのみにアクセスして、可能なアドレス照合があるかどうかをチェックする必要がある。
キャッシュが８１９２個のストレージロケーションで構成されるが、どの特定のアドレスも、８つのロケーションのうちの１つにしか配置できない場合、キャッシュのアドレス照合は簡単化される。
これは、ウェイ検出オペレーション３２０を用いて実行される。
データがデータアレイに存在する場合、そのデータアレイがアクセスされて（３３０）、データが読み出される。
センス増幅器３３５を再び使用して、データアレイから読み出された信号を増幅することができる。

この例では、データアレイから来る大量のデータが追加時間を必要とするので、１次パイプラインステージＰ１およびＰ２は、伝搬時間用に使用することができる。
次いで、２次パイプラインステージＳ０〜Ｓ３は、要求側のデバイス（例えば、マイクロプロセッサ）へデータを実際に配信するのに使用することができる。
前述したように、４ステージパイプラインは、フルキャッシュラインの１／４のサイズであるデータバスを有することに関連付けられる。
したがって、キャッシュへ転送されるデータまたはキャッシュから転送されるデータは、４つの等しいサイズのパケットまたはチャンクに分割され、１，０２４ビットのデータを４つの２５６ビットのデータチャンクに分解するには４クロックサイクルを要する。
チャンクＭＵＸ３４０は、データチャンクの処理の選択および制御を行うように構成されたマルチプレクサとすることができる。
センス増幅器３３５からの出力信号は、データアレイから読み出されたデータを表し、グローバルビットライン３４５に置かれる。
データがチャンクＭＵＸ３４０によって４つの部分に分割される前のクロックサイクルにおける延長時間の間、データを記憶するのに、ゼロキャッチャ（zero-catcher）を使用することができる。

図４を参照して、検索要求が「ミス」になる場合の検索要求のパイプラインタイミング図の例４００が示されている。
この検索要求のオペレーション例は、図３の検索要求に示すような１次パイプラインステージＰ０〜Ｐ２については同じである。
一方、パイプラインステージＰ３では、「ミス」となったので、データアレイは読み出されない。
その代わり、プロセスは、タグアレイに再びアクセスするために、ステージＰ３の４０５で要求アドレスＭＵＸを再び通過する。
交換ウェイ選択４１０は、キャッシュメモリの第３のアレイに対して実行される動作を指す。

一般に、「交換ウェイ（replacement way）」は、キャッシュのロケーションの１つにデータチャンクを配置しようとする。
前述したように、キャッシュは、８つの「ウェイ」等の複数のロケーションで構成することができる。
キャッシュが、新しいデータ部分を取り入れる必要がある時、或るデータをキャッシュから除去する必要がある。
交換ウェイ４１０は、キャッシュから除去するコストが最小のデータ部分がどれであるかを決定しようと試みる。
考慮することができる１つの因子は、未使用期間が最長のデータを選択することである。
もちろん、他のタイプの因子を使用することもできる。
現時点では、新しいデータが受信された時に、その新しいデータ用のロケーションが予約される。
次に、新しいデータのアドレスが判明するとすぐに、そのアドレスをタグアレイに書き込むことができる。

全体的に見ると、図４のタイミング図のステージ割り当ては、タグアレイがステージＰ１および２次ステージＳ０でアクセスされることを示している。
前述したように、２次パイプラインは、１次パイプラインステージと重なるものとみなすことができ、したがって、２次ステージＳ０は１次ステージＰ０と等価である。
したがって、この検索要求の場合、２つのステージが、４ステージパイプラインから割り当てられている。

図５および図６を参照して、スヌープ照会５００およびスヌープ無効オペレーション６００のパイプラインステージ割り当ておよびタイミング図がそれぞれ示されている。
図５のスヌープ照会のオペレーション例は、或る状況で実行することができる。
この或る状況とは、キャッシュが特定のデータ部分を含む場合に、そのデータが古いかまたはそれ以外にもはや有効でないことから、キャッシュがそのデータ部分を除去すべきであることを、デバイスまたは他のソースがキャッシュシステムに示している状況である。
スヌープ照会オペレーションの間、このオペレーションは、選択されたデータ部分がキャッシュにあるかどうかを判断するように構成される。
キャッシュシステムがスヌープ要求を受信する時はいつでも、この照会オペレーションが実行される。
要求されたデータが実際にキャッシュに存在する場合にのみ、図６のスヌープ無効オペレーションは実行される。
前述したように、スヌープ無効オペレーションは、通常、スヌープ照会オペレーションに対して非常に小さな割合の時間でしか実行されない。

スヌープ照会では、タグ読み出しがブロック５０５で実行される。
このステージ割り当て例は、タグ読み出し５０５が１次パイプラインステージＰ３で行われることを示している。
検索要求およびスヌープ照会に関連したステージの割り当てを考慮すると、同時の検索要求およびスヌープ照会が、ステージＰ０、Ｐ１、およびＰ３でタグアレイにアクセスすることになる。
したがって、アクセス衝突は、これらのアクセス要求のオペレーション間には存在しない。

しかしながら、このステージ割り当て例では、１つの潜在的な衝突が存在する可能性がある。
スヌープ照会がヒットした場合、図６に示すスヌープ無効オペレーションが実行される。
スヌープ無効のタイミング図の例６００は、スヌープ無効が、ステージＰ０で処理を開始するように割り当てられていることを示している。
タグ読み出し６０５はステージＰ１で行われる。
ステージＰ１は、検索要求（図３および図４参照）についてタグ読み出しが行われるスヌープと同じステージである。
したがって、スヌープ無効および検索要求が同時に処理されている場合に衝突が起こり得る１つの状況が発生する可能性がある。
キャッシュ制御ロジックは、オペレーションの一方をブロックし、その開始ステージがパイプラインにおいて現在のステージとなる次の時までオペレーションの一方を遅延させるように構成される。
一構成では、検索要求を遅延させて、スヌープ無効を最初に処理することを可能にすることができる。
前述したように、スヌープ無効オペレーションは、非常に稀なイベントであり、したがって、図示したステージ割り当て例は、潜在的なアクセス衝突を最小にするために最適化される。
このタイプの衝突は、稀にしか発生することがないので、キャッシュシステムのスループットは、最低限しか影響を受けない。

図７には、フィルオペレーションに関連付けることができるパイプラインタイミング図の例７００が示されている。
これらの例のデータバスは、フルキャッシュラインの１／４である２５６ビットバスとなるように構成されることを思い出すと、キャッシュは、キャッシュライン全体が組み立てられるまで、４クロックサイクルを使用して、４つの２５６ビットのデータチャンクを組み立てる。
データは、一旦組み立てられると、その後、データアレイに書き込むことができる。
このデータ組み立てオペレーションは、フィルデータＭＵＸ（ブロック７０５）およびローカルアレイラッチ（ブロック７１０）によって表される。
これらフィルデータＭＵＸおよびローカルアレイラッチは、パイプラインステージＰ０〜Ｐ３にわたって４回繰り返される。
データのすべてが組み立てられると、次に、データは、データアレイに書き込まれる（ブロック７１５）。
これは、２次パイプラインステージＳ０で行われるように示されている。
２次ステージＳ２では、データのアドレスがタグアレイに書き込まれる（ブロック７２０）。
この場合もこのステージ割り当てを考慮すると、同時に起こる検索要求ミス、スヌープ照会、およびフィルは、何らのアクセス衝突なく、ステージ０、１、２、および３でタグアレイにアクセスする。

図３〜図７に示すオペレーション例のステージ割り当ては、マルチステージパイプラインを使用してキャッシュイベントを処理するのに使用できる一構成例にすぎないことが理解されよう。
本システムおよび方法は、説明したオペレーションまたはオペレーションシーケンスによって限定されるように意図されていない。
さらに、異なる方法でイベントおよびデータを処理するように異なるキャッシュシステム設計を構成できることも理解されよう。
この異なる方法とは、説明した例には示されていないオペレーションを含むことができ、かつ／または、これより少ない個数のオペレーションもしくはこれより多くの個数のオペレーションを含むことができるものである。

図８には、キャッシュの状態を制御するキャッシュシステムで実施することができる状態図の例８００が示されている。
各タグエントリは状態を有することができる。
一例では、このキャッシュシステムについて、「Ｉ」、「Ｓ」、「Ｋ」、および「Ｐ」を含む４つの可能なキャッシュ状態を実施することができる。
「Ｉ」は、ラインが無効である（invalid）ことを示す。
「Ｓ」は、データが共有される（shared）ことを示す。
「Ｋ」は、データがキルされる（killed）ことを示す。
「Ｐ」は、データが保留中である（pending）ことを示す。
この状態例は、ＭＥＳＩ状態と呼ばれる一般のキャッシュ状態とは異なる。
ＭＥＳＩ状態では、「Ｍ」は変更（modified）を表し、「Ｅ」は排他（exclusive）を表し、「Ｓ」は共有（shared）を表し、「Ｉ」は無効（invalid）を表す。

このキャッシュシステム例は命令キャッシュであるので、変更されたデータを記憶することはない。
命令キャッシュでは、そのデータを変更して、データがメモリに書き込まれることにつながるキャッシュイベントまたはオペレーションは存在しない。
この考慮すべき事項に基づいて、キャッシュシステムは、無効および共有の２つの状態で構成される。
これは、データがメインメモリのデータと一致していることを意味する。
他のオペレーションをサポートするために、状態を追加して使用することができる。
例えば、検索ミスをサポートするために、システムが、まだ受信されていないデータについてキャッシュに新しいエントリを割り当てている時は、保留状態「Ｐ」を使用することができる。

図８に示すキャッシュライン状態の一般的なフローは、キャッシュラインの無効状態「Ｉ」で開始することができる。
「検索ミス」が発生し、システムがデータの要求をＬ２キャッシュまたはメモリへ送出する場合、状態は保留状態「Ｐ」に進む。
無効状態または共有状態のいずれかのエントリのみを「交換」することができ、検索ミスによって保留状態に設定することができる。
そのエントリのデータが返され、キャッシュがフィルを受信すると、関連したキャッシュラインは、共有状態「Ｓ」へ遷移する。
そのラインを無効にするスヌープが受信された場合、そのラインは無効状態「Ｉ」に戻される。
キル状態「Ｋ」は、キャッシュラインが保留状態「Ｐ」にあり、フィル要求が受信される前にスヌープが受信された時に発生するように構成することができる。
換言すると、マイクロプロセッサはデータのラインを要求しており、キャッシュは次のレベルのメモリ（例えば、Ｌ２キャッシュ）へ要求を送出しているが、その後、キャッシュは、当該キャッシュにそのラインをキャンセルするように指示するスヌープを受信する。
したがって、そのラインはもはや有効ではない。
キル状態「Ｋ」は、キャッシュシステムがその状況を把握する方法である。
その後、キルされたキャッシュラインについて、フィルが受信されると、状態は共有状態「Ｓ」ではなく無効「Ｉ」に変更される。
これは、データがスヌープされた後に、そのデータのラインをキャッシュが使用しないことを保証する１つの方法である。

キャッシュ状態を実施する一システム例は、有効ビットおよび保留ビットの２ビットを使用することによるものとすることができる。
タグアレイの各タグエントリは、そのタグエントリの現在の状態を特定するための、当該タグエントリに関連した有効ビットおよび保留ビットを有する。
図９に示す表は、４つのキャッシュ状態のそれぞれに対する有効ビットおよび保留ビットのビットエンコーディング例９００を示している。
キャッシュ制御ロジックによって使用されるビットエンコーディング９００を実施することによって、タグアレイに対する或るアクセスを、一定の条件下で回避することができる。
例えば、スヌープ無効またはフィル要求の「タグ書き込み」を実行するために、キャッシュ制御ロジックは、タグアレイの内容をどのように変更するかを決定するためにタグアレイの内容を読み出す必要はない。

一例として、キャッシュ状態遷移８００を参照して、キャッシュがフィルを受信した時、キャッシュエントリは、保留状態から共有状態へ遷移することが必要な場合もあるし、キル状態から無効状態へ遷移することが必要な場合もある。
一般的な手法では、キャッシュ制御ロジックは、タグアレイから古いキャッシュライン状態を読み出し、その結果に基づいて新しい状態を決定し、その適切な新しい状態をキャッシュエントリに書き込むことができる。
しかしながら、ビットエンコーディング９００は、キャッシュ制御ロジックがタグアレイの読み出しを回避することを可能にすることができる。
その理由は、キャッシュラインがたとえキャッシュ状態のいずれであろうとも、そのキャッシュラインについてフィルが受信されると、キャッシュ制御ロジックは、そのキャッシュラインの保留ビットのクリアのみを行えばよいことが決定されるからである。
したがって、タグの潜在的な「読み出しアクセス」をなくすことができ、書き込みオペレーションのみを実行する必要がある。

スヌープ無効またはフィル要求についてのタグ読み出しをなくすことによって、キャッシュイベントのステージへの割り当てが簡単化され、この割り当ては、実行する必要のあるタグアクセスの回数を削減することにより潜在的なアクセス衝突を削減する。
一般に、キャッシュ状態８００およびビットエンコーディング９００は、各キャッシュラインがどの状態にあるかを機能的に特定するのに使用することができ、また、各キャッシュラインについてどのオペレーションを実行できるかを示すのに使用することができる。

図３〜図７に示すステージ割り当て例、ならびに、図８および図９の状態例を使用すると、キャッシュシステム２００のいくつかの設計検討例を以下のようなものにすることができる。
スヌープ照会は、検索イベントおよびフィルイベントと並列に、８クロックサイクルごとに１回実行することができる。
スヌープ無効が必要とされる場合、このスヌープ無効がパイプラインの検索要求に取って代わることになる。
図６は、タグメモリの第２の読み出しを実行するスヌープ無効を示している（そのオペレーションを検索要求と同様に見せる）が、この第２のタグ読み出しは、機能的には必要ではなく、アクセス衝突をさらにできる限り削減するためになくすことができる。

キャッシュシステム２００は、完全なタグエントリを書き込むように構成することができる。
また、キャッシュは、タグエントリの保留ビットのみ、または、有効ビットのみを個別に書き込むことを可能にすることもできる。
この特徴によって、通常ならば読み出し／変更／書き込みシーケンスの間に実行される２つのタグメモリアクセスではなく、タグに対して単一の書き込みオペレーションを実行することを「フィル」オペレーションおよび「スヌープ無効」の双方に可能にすることができる。

また、システムは、「ミス」が発生した場合に、新しいタグエントリの有効ビットおよび保留ビットの双方を設定するように構成することもできる。
「フィル」については、システムは、適切なタグエントリの保留ビットをクリアすることはできるが、そのタグエントリの有効ビットを変更することはできない。
「スヌープ無効」については、システムは、適切なタグエントリの保留ビットを変更せずに、そのエントリの有効ビットをクリアすることができる。
これによって、一方のオペレーションの更新が、他方のオペレーションの更新を確認せず、エントリを異常な状態にする可能性なしに、「フィル」および「スヌープ」が重なることが可能になる。

図１０には、マルチステージパイプラインを使用してキャッシュイベントの処理を円滑にすることができるキャッシュ制御ロジック１０００の構成例が示されている。
このキャッシュ制御ロジック１０００は、前述した他のキャッシュ制御ロジック例１０５および２０５を実施するのに使用することができる。
キャッシュ制御ロジック１０００は、ステージコントローラ９０５を含むことができる。
このステージコントローラ９０５は、パイプラインステージのカウントをいつ開始するかを示すロジックとして構成される。
例えば、保留状態の要求がキャッシュに存在しない場合（例えば、アイドル状態）、パイプラインステージは進行する必要はない。
要求が受信され、パイプラインがアイドル状態にある場合、ステージは、ステージＰ０で開始し、クロックサイクルに基づいて循環を始める。

パイプラインステージロジック１０１０は、パイプラインの現在のステージを特定するのに使用することできる。
一例では、パイプラインステージロジック１０１０は、カウントメカニズムで構成することができる。
このカウントメカニズムは、ステージを繰り返しカウントでき、ステージを順次循環することができるものである。
一構成は、パイプライン用に実施されたステージの個数に対応する複数のフリップフロップまたはレジスタを有するものとすることができる。
キャッシュ制御ロジック１０００が、上記例で説明したような１次パイプラインおよび２次パイプラインを含むデュアル４ステージパイプラインで構成される場合、ステージの総数は８になる。
したがって、フリップフロップのチェーンを通じてビットを伝搬するように８つのフリップフロップを構成することができる。
ビットの位置は、パイプラインの現在のステージを表す。

図１０をさらに参照して、決定ロジック１０１５は、各パイプラインステージにおいてどの動作および／もしくはオペレーションを取ることができるか、または、取る必要があるかを決定するように構成することができる。
この決定は、パイプラインステージロジック１０１０および資源割り当てマトリックス１０２０によって示されるようなパイプラインの現在のステージに基づくものとすることができる。
資源割り当てマトリックス１０２０は、各キャッシュイベントのオペレーションシーケンスおよび各オペレーションを実行できる対応するパイプラインステージを定義するロジックとして構成することができる。
一例では、資源割り当てマトリックス１０２０は、回路機構を使用して、さまざまなキャッシュイベントに関連した図３〜図７に示すパイプラインステージ割り当てを定義することができる。

以下の処理オペレーション例は、検索要求についての図３に示すステージ割り当てに基づいている。
検索要求が選択されて処理されている場合、決定ロジック１０１５は、パイプラインが１次ステージＰ１にいる場合に、タグアレイを読み出すべきであると決定することができる。
これは、タグ読み出しオペレーション３１５がステージＰ１に割り当てられる図３に見られる。
他のシナリオ例および決定例は、上記例に基づいて理解されよう。
キャッシュ制御ロジック１０００が行う処理決定に基づき、１つまたは複数の制御信号を生成して、キャッシュを制御することができる。
例えば、図２に示すキャッシュ構造を使用すると、キャッシュ制御ロジック２０５は、マルチプレクサ２２５、タグアレイ２１０、およびデータアレイ２１５へ制御信号を送信することができる。

方法の例は、フロー図を参照することによって、より良く理解することができる。
説明を簡単にするために、図示した方法論は、一連のブロックとして図示および説明されるが、いくつかのブロックは、図示および説明される順序とは異なる順序で、かつ／または、他のブロックと同時に行うことができるので、この方法論はブロックの順序によって限定されるものでないことが理解されるべきである。
その上、図示したすべてのブロックが例示の方法論を実施するのに必要とされるとは限らない場合がある。
ブロックは、組み合わせることもできるし、複数のコンポーネントに分割することもできる。
さらに、付加的な方法論および／または代替的な方法論は、図示しない付加的なブロックを使用することができる。
図は、連続して行われるさまざまな動作を示しているが、さまざまな動作は、同時に行うこともできるし、実質的に並列に行うこともできるし、かつ／または、実質的に異なる時点で行うこともできることが理解されるべきである。

図１１には、キャッシュシステムの設計、構成、および／または製造に関連付けることができる方法論の例１１００が示されている。
この方法論の例は、キャッシュメモリを有するマイクロプロセッサの構築を含むことができる。
図示した要素は、ロジックで実施することができる「処理ブロック」を示す。
一例では、処理ブロックは、応答、動作（複数可）の実行、状態の変更、および／または決定をコンピュータ、プロセッサ、および／またはロジックデバイスに行わせる実行可能命令を表すことができる。
したがって、説明する方法論は、コンピュータ可読媒体によって提供されるプロセッサ実行可能命令および／またはオペレーションとして実施することができる。
別の例では、処理ブロックは、アナログ回路、デジタル回路、特定用途向け集積回路（ＡＳＩＣ）、他のロジックデバイス等の機能的に等価な回路によって実行される機能および／または動作を表すことができる。
図１１の図およびそれ以外に示す図は、説明する例の実施態様（インプリメンテーション）を限定するためのものではない。
逆に、これらの図は、当業者が、回路の設計／製造もしくはソフトウェア／ファームウェアの生成に使用して、または、ロジックの組み合わせを使用して、図示した処理を実行できる機能的な情報を示すものである。

キャッシュ設計は、図示したブロックを、図示したシーケンスとは異なる他のシーケンスで実行でき、かつ／または、ブロックを組み合わせたり、複数のコンポーネントに分割したりすることができるような動的で柔軟なプロセスを含むことができることが理解されよう。
また、ブロックは、同時に実行することもできるし、実質的に並列に実行することもできるし、かつ／または、実質的に異なる時点で実行することもできる。
上記の内容は、本明細書で説明したすべての方法論に当てはまる。

図１１を参照して、方法論の例１１００は、キャッシュにアドレスおよび命令を記憶するようにシングルポートメモリ構造を構成する（ブロック１１０５）ことを含む。
ロジックは、マルチステージパイプラインであって、当該マルチステージパイプラインのステージには、シングルポートメモリに対するアクセス衝突を最小にするように１組のキャッシュイベントを実行するオペレーションが関連付けられる、マルチステージパイプライン、を実施するように構成することができる（ブロック１１１０）。
キャッシュ制御ロジックは、シングルポートメモリに動作可能に接続することができる（ブロック１１１５）。
キャッシュ制御ロジックは、１組のキャッシュイベントを処理するシーケンスを調整するマルチステージパイプラインを少なくとも使用して、当該１組のキャッシュイベントの処理を制御するように構成することができる。
キャッシュイベントの例には、前述したような検索要求、フィル要求、およびスヌープが含まれる。
しかしながら、異なるキャッシュ設計に基づいて、他のタイプのオペレーションおよびキャッシュイベントも実施できることが理解されよう。

ブロックを構成する（１１１０）ことは、マルチステージパイプラインを構成する複数のステージを選択することを含むことができる。
キャッシュと共に機能することができる１組のキャッシュイベントが与えられると、各キャッシュイベントは、そのキャッシュイベントが処理される時に実行される１組のオペレーションを含む。
各キャッシュイベントのオペレーションは、マルチステージパイプラインのステージに関連付けられるか、または、そうでない場合に当該ステージに割り当てられる。
このマルチステージパイプラインは、各キャッシュイベントの開始ステージおよび処理順序を定義する。
このように、キャッシュのメモリアレイに対するアクセスは、既知のステージの期間中に行われるように設計される。
したがって、方法論１１００は、割り当てられたステージに基づいてシングルポートメモリに対するアクセスを静的に割り当てるようにキャッシュ制御ロジックを構成することを含むことができる。
キャッシュの資源を静的に割り当てることによって、キャッシュ制御ロジックが簡単化され、確認する必要のあるキャッシュイベントタイミングの組み合わせの個数が削減される。

図１２には、シングルポートキャッシュメモリのキャッシュイベントを処理することに関連付けることができる方法論の例１２００が示されている。
この方法論は、複数のステージを順次循環するパイプラインを保持する（ブロック１２０５）ことを含むことができる。
これら複数のステージは、キャッシュイベントのそれぞれを実行するシーケンスであって、当該シーケンスがキャッシュイベント間のアクセス衝突を最小にする、シーケンス、を定義するように構成される。
キャッシュイベントの受信に応答して、この方法は、パイプラインによって定義されたシーケンスに基づいて、そのキャッシュイベントをいつ処理するかを決定することができる（ブロック１２１０）。
次に、受信したキャッシュイベントは、少なくともパイプラインの現在のステージおよび受信したキャッシュイベントを実行するための定義されたシーケンスに基づいて処理される（ブロック１２１５）。

パイプラインは、一定の個数のステージを含むことができ、現在のステージは、クロックサイクルに基づいて、パイプラインを順次循環される。
サイクルがパイプラインの終了ステージに達すると、ステージが繰り返される。
上記例で説明したように、各キャッシュイベントには、パイプラインの開始ステージが割り当てられる。
この開始ステージは、特定のキャッシュイベントが処理を開始できる時を特定する。
キャッシュイベントが受信され、現在のステージが、この受信したキャッシュイベントに割り当てられた開始ステージでない場合、この受信したキャッシュイベントの処理は、パイプラインがそのイベントの開始ステージに戻るまで遅延される。
このように、ステージ割り当てに基づいて、キャッシュの資源を静的に割り当てることができ、アクセス衝突を最小にできるか、または、回避することができる。

図１３は、本明細書で説明したシステム例および方法例、ならびに、その均等物が動作できる計算デバイス例を示している。
この計算デバイス例はコンピュータ１３００とすることができる。
このコンピュータ１３００は、プロセッサ１３０２、メモリ１３０４、および入出力ポート１３１０を含む。
これらのプロセッサ１３０２、メモリ１３０４、および入出力ポート１３１０は、バス１３０８によって動作可能に接続される。
一例では、コンピュータ１３００は、マルチステージパイプラインを使用してキャッシュイベントの処理を円滑にするように構成されたキャッシュ制御ロジック１３３０を含むことができる。
キャッシュ制御ロジック１３３０は、図１、図２、および図１０で説明したキャッシュ制御ロジック１０５、２０５、および１０００と同様に実施することができ、これに加えて、本明細書で説明した他のシステムおよび方法と同様に実施することもできる。

コンピュータ１３００の構成例を一般的に説明すると、プロセッサ１３０２は、デュアルマイクロプロセッサおよび他のマルチプロセッサアーキテクチャを含む多種多様なさまざまなプロセッサとすることができる。
メモリ１３０４は、揮発性メモリおよび／または不揮発性メモリを含むことができる。
不揮発性メモリには、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等が含まれ得るが、これらに限定されるものではない。
揮発性メモリには、例えば、ＲＡＭ、同期ＲＡＭ（ＳＲＡＭ）、ダイナミックＲＡＭ（ＤＲＡＭ）、同期ＤＲＡＭ（ＳＤＲＡＭ）、ダブルデータレートＳＤＲＡＭ（ＤＤＲ ＳＤＲＡＭ）、およびダイレクトＲＡＭバスＲＡＭ（ＤＲＲＡＭ）が含まれ得る。

ディスク１３０６は、例えば、入出力インターフェース（例えば、カード、デバイス）１３１８および入出力ポート１３１０を介してコンピュータ１３００に動作可能に接続することができる。
ディスク１３０６には、磁気ディスクドライブ、ソリッドステートディスクドライブ、フロッピィディスクドライブ、テープドライブ、Ｚｉｐドライブ、フラッシュメモリカード、および／またはメモリスティックのようなデバイスが含まれ得るが、これらに限定されるものではない。
さらに、ディスク１３０６には、ＣＤ−ＲＯＭ、ＣＤ記録可能ドライブ（ＣＤ−Ｒドライブ）、ＣＤ再書き込み可能ドライブ（ＣＤ−ＲＷドライブ）、および／またはデジタルビデオＲＯＭドライブ（ＤＶＤ ＲＯＭ）のような光ドライブも含まれ得る。
メモリ１３０４は、例えば、プロセス１３１４および／またはデータ１３１６を記憶することができる。
ディスク１３０６および／またはメモリ１３０４は、コンピュータ１３００の資源の制御および割り当てを行うオペレーティングシステムを記憶することができる。

バス１３０８は、単一の内部バス相互接続アーキテクチャ、および／または、他のバスアーキテクチャもしくはメッシュアーキテクチャとすることができる。
単一のバスが示されているが、コンピュータ１３００は、図示しない他のバス（例えば、ＰＣＩＥ、ＳＡＴＡ、インフィニバンド、１３９４、ＵＳＢ、イーサネット（登録商標））を使用してさまざまなデバイス、ロジック、および周辺機器と通信できることが理解されるべきである。
バス１３０８は、さまざまなタイプのものとすることができ、このさまざまなタイプには、メモリバスもしくはメモリコントローラ、周辺バスもしくは外部バス、クロスバースイッチ、および／またはローカルバスが含まれるが、これらに限定されるものではない。
ローカルバスはさまざまなものとすることができ、このさまざまなものには、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＳＡ）バス、拡張ＩＳＡ（ＥＩＳＡ）バス、周辺機器相互接続（ＰＣＩ）バス、ユニバーサルシリアルバス（ＵＳＢ）、および小型コンピュータ用周辺機器インターフェース（ＳＣＳＩ）バスが含まれるが、これらに限定されるものではない。

コンピュータ１３００は、Ｉ／Ｏインターフェース１３１８および入出力ポート１３１０を介して入出力デバイスと対話することができる。
入出力デバイスには、キーボード、マイク、ポインティング／選択デバイス、カメラ、ビデオカード、ディスプレイ、ディスク１３０６、ネットワークデバイス１３２０等が含まれ得るが、これらに限定されるものではない。
入出力ポート１３１０には、シリアルポート、パラレルポート、およびＵＳＢポートが含まれ得るが、これらに限定されるものではない。

コンピュータ１３００は、ネットワーク環境で動作することができ、したがって、Ｉ／Ｏデバイス１３１８および／またはＩ／Ｏポート１３１０を介してネットワークデバイス１３２０に接続することができる。
ネットワークデバイス１３２０を通じて、コンピュータ１３００は、ネットワークと対話することができる。
このネットワークを通じて、コンピュータ１３００は、リモートコンピュータに論理的に接続することができる。
コンピュータ１３００が対話することができるネットワークには、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、および他のネットワークが含まれ得るが、これらに限定されるものではない。
ネットワークデバイス１３２０はＬＡＮ技術に接続することができる。
ＬＡＮ技術には、ファイバ分散データインターフェース（ＦＤＤＩ）、銅分散データインターフェース（ＣＤＤＩ）、イーサネット（ＩＥＥＥ８０２．３）、トークンリング（ＩＥＥＥ８０２．５）、無線コンピュータ通信（ＩＥＥＥ８０２．１１）、ブルートゥース（ＩＥＥＥ８０２．１５．１）等が含まれるが、これらに限定されるものではない。
同様に、ネットワークデバイス１３２０はＷＡＮ技術に接続することができる。
ＷＡＮ技術には、ポイントツーポイントリンク、サービス統合デジタル網（ＩＳＤＮ）のような回線交換ネットワーク、パケット交換ネットワーク、およびデジタル加入者線（ＤＳＬ）が含まれるが、これらに限定されるものではない。

本明細書で説明したキャッシュシステム例は、メモリアドレスに関して、直接マッピング方式のキャッシュライン、完全連想方式のキャッシュライン、または群連想方式のキャッシュラインで構成できることが理解されよう。
直接マッピング方式のキャッシュは、特定のキャッシュラインを各メモリアドレスに関連付け、特定のアドレスに記憶された命令またはデータをその特定のキャッシュラインにのみ配置するものである。
完全連想方式のキャッシュは、メモリアドレスをどの特定のキャッシュラインにも関連付けない。
命令およびデータは、任意のキャッシュラインに配置することができる。
群連想方式のキャッシュは、数組または数群の連続したキャッシュラインを特定のメモリロケーションに直接マッピングするものである。
一方、１組のキャッシュライン内では、キャッシュは完全連想方式とすることができる。

システム例、方法例等を、例を説明することによって示し、また、これらの例をかなり詳細に説明してきたが、添付の特許請求の範囲をこのような詳細なものに制限したり、多少なりとも限定したりすることは出願人の意図するところではない。
もちろん、本明細書で説明したシステム、方法等を説明するために、コンポーネントまたは方法論の考えられるあらゆる組み合わせを説明することはできない。
別の利点および変更は、当業者には容易に明らかであろう。
したがって、本発明は、図示および説明した具体的な記述、代表的な装置、および説明的な例に限定されるものではない。
したがって、この出願は、添付の特許請求の範囲の範囲内に入る改変、変更、および変形を包含するように意図されている。
さらに、上記説明は、本発明の範囲を限定するように意図されていない。
逆に、本発明の範囲は、添付の特許請求の範囲およびその均等物によって特定されることになる。

用語「含む」は、発明を実施するための最良の形態または特許請求の範囲で使用される限りにおいて、用語「備える」が特許請求の範囲で変わり目の用語として使用された場合にその用語が解釈されるのと同様に、包含的であるように意図されている。
さらに、用語「または（もしくは）」は、発明を実施するための最良の形態または特許請求の範囲で使用される限りにおいて（例えば、ＡまたはＢ）、「ＡもしくはＢまたはそれら双方」を意味するように意図されている。
出願人が、「ＡまたはＢのみであって、双方ではない」ことを示すように意図している場合、用語「ＡまたはＢのみであって、双方ではない」が使用されることになる。
したがって、本明細書における用語「または（もしくは）」の使用は、包含的な使用であって、排他的な使用ではない。
これについては、Bryan A. Garner著「A Dictionary of Modern Legal Usage 624 (2d. Ed. 1995)」を参照されたい。

マイクロプロセッサキャッシュシステムの構成例を示す図である。 キャッシュおよびキャッシュ制御ロジックの構成例を示す図である。 ヒットになる検索要求のタイミング図の例である。 ミスになる検索要求のタイミング図の例である。 スヌープ照会のタイミング図の例である。 スヌープ無効オペレーションのタイミング図の例である。 フィル要求のタイミング図の例である。 キャッシュ状態遷移図の例である。 キャッシュ状態を表すビットエンコーディング例を示す図である。 別のキャッシュ制御ロジック例を示す図である。 キャッシュシステムの設計、構成、および／または製造に関連付けることができる方法論の例を示す図である。 マルチステージパイプラインを使用してキャッシュイベントを処理することに関連付けることができる方法論の例を示す図である。 本明細書で図示したシステム例および方法例を実施でき、かつ、動作させることができる計算環境の例を示す図である。

符号の説明

１０５・・・キャッシュ制御ロジック，
１１０・・・Ｌ１キャッシュ，
１１５・・・Ｌ０キャッシュ，
１２０・・・Ｌ２キャッシュ，
１２５・・・メモリ，
１３０・・・マイクロプロセッサ，
１３５・・・命令フェッチユニット，
２０５・・・キャッシュ制御ロジック，
２１０・・・タグアレイ，
２１５・・・データアレイ，
２２０・・・ＣＰＵ要求，
２２５・・・マルチプレクサ，
２３５・・・オペレーションシーケンス，
１０００・・・キャッシュ制御ロジック，
１００５・・・ステージコントローラ，
１０１０・・・パイプラインステージロジック，
１０１５・・・決定ロジック，
１０２０・・・資源割り当てマトリックス，
１３００・・・コンピュータ，
１３０２・・・プロセッサ，
１３０４・・・メモリ，
１３０６・・・ディスク，
１３０８・・・バス，
１３１０・・・Ｉ／Ｏポート，
１３１４・・・プロセス，
１３１６・・・データ，
１３１８・・・Ｉ／Ｏインターフェース，
１３２０・・・ネットワークデバイス、
１３３０・・・キャッシュ制御ロジック，
１３４０・・・Ｉ／Ｏコントローラ，

Claims (11)

1. 命令キャッシュであって、
   シングルポートメモリ（２１０、２１５）と、
   前記命令キャッシュが受信する異なるタイプのキャッシュイベントを処理するように構成され、前記シングルポートメモリに対する前記キャッシュイベントの処理を調整するマルチステージパイプラインで構成されるキャッシュ制御ロジック（２０５）と、
   異なるステージが、前記キャッシュイベントの読み出しおよび書き込みまたはこれらのいずれかのステージとして事前に割り当てられ、前記キャッシュイベント間のアクセス衝突が最小にされる前記マルチステージパイプライン（２３０）と
   を備える命令キャッシュ。
2. 前記マルチステージパイプライン（２３０）は、各ステージが１つのクロックサイクルに関連付けられるデュアル４ステージ構造として構成される
   請求項１に記載の命令キャッシュ。
3. 前記キャッシュ制御ロジックは、前記異なるタイプのキャッシュイベントを入力として受信するように構成され、
   前記入力のいずれが処理されるかを前記マルチステージパイプラインの現在のステージに基づいて選択するように構成されるマルチプレクサ（２２５）
   を含む請求項１に記載の命令キャッシュ。
4. 前記異なるタイプのキャッシュイベントは、フィル要求、ＣＰＵデータ要求、およびスヌープを含み、
   前記キャッシュ制御ロジック（２０５）は、前記異なるタイプのキャッシュイベントが、前記マルチステージパイプラインに同時に存在することを可能にするように構成され、
   前記命令キャッシュのタグアレイに対するアクセスは、前記キャッシュイベントのそれぞれについての前記マルチステージパイプラインの異なるステージで行われるように割り当てられる、
   請求項１に記載の命令キャッシュ。
5. 前記命令キャッシュにおいて、前記マルチステージパイプラインの選択されたステージでどのタイプのキャッシュイベントを処理できるかを定義してアクセス衝突を回避するように構成される資源割り当てマトリックス（１０２０）
   をさらに含み、
   前記キャッシュ制御ロジック（２０５）は、
   前記資源割り当てマトリックスと、前記マルチステージパイプラインの現在のステージおよび処理されるアクセスタイプを含む状況とに基づき、どのキャッシュイベントを処理するかを決定するように構成される決定ロジック（１０１５）
   を含む
   請求項１に記載の命令キャッシュ。
6. シングルポートキャッシュのキャッシュイベントを処理する方法であって、
   複数のステージを順次循環するパイプラインを保持する（１２０５）ことであって、前記複数のステージが、前記キャッシュイベントのそれぞれを実行するシーケンスを定義するように構成され、前記シーケンスが前記キャッシュイベント間のアクセス衝突を最小にすることと、
   キャッシュイベントの受信に応答して、前記パイプラインにより定義された前記シーケンスに基づいて前記キャッシュイベントを処理する時を決定する（１２１０）ことと、
   少なくとも前記パイプラインの現在のステージと、前記受信したキャッシュイベントを実行するための前記定義されたシーケンスとに基づいて、前記受信したキャッシュイベントを処理する（１２１５）ことと
   を含む方法。
7. 前記受信したキャッシュイベントを処理することは、前記パイプラインが、前記受信したキャッシュイベントの開始ステージとして定義されたステージになるまで遅延される
   請求項６に記載の方法。
8. 前記パイプラインは、
   複数のステージ
   を含み、
   前記方法は、
   クロックサイクルに基づいて、前記ステージを順次循環すること
   を含む
   請求項６に記載の方法。
9. 命令キャッシュ内にコンテンツを記憶し、前記コンテンツにアクセスするシングルポートを有する手段（１１０）と、
   １組のキャッシュイベントを実行するオペレーションが、前記メモリ手段に対するアクセス衝突を最小にするようにマルチステージパイプラインのステージに関連付けられる、前記マルチステージパイプラインを提供する手段（２３０）と、
   前記命令キャッシュが受信できる前記１組のキャッシュイベントを、前記キャッシュイベントの処理順序を調整する前記パイプライン手段を少なくとも使用して処理する手段（１０５）と
   を備えるシステム。
10. 前記手段（１１０）は、
    少なくともタグアレイおよびデータアレイ
    を含む
    請求項９に記載のシステム。
11. マルチステージパイプラインを提供する前記手段（２３０）は、
    前記マルチステージパイプラインの前記ステージを、順次循環する手段
    を含む
    請求項９に記載のシステム。

Images