(57)【要約】【課題】確定的なウェイ-識別を可能にする方法とシステムと、ウェイの誤予測の処理を不要にする方法とシステムと、誤予測の無効化処理を必要とする従来のウェイ予測方式よりも複雑でないウェイ-決定方式と、アドレス指定されているデータ項目が、キャッシュのウェイ内にあることが既知か否かを直ちに決定するウェイ-識別方式と、を提供すること。【解決手段】要求されたデータ項目のラインアドレス全体に基づいていることにより、要求されたデータ項目を含むウェイを誤識別してしまう可能性がない、n-ウェイ・連想キャッシュのためのウェイ決定方式が提供される。限られた数のラインアドレスと、これらの割り当てられたウェイが、ウェイ決定テーブル内に格納される。要求されたデータアドレスが、これらのラインアドレスの1つに対応している場合、割り当てられたウェイが供給される。対応していない場合、「空白」応答が提供され、ウェイがこのデータアドレスに既知ではないことが示される。割り当てられたウェイが供給されると、この割り当てられたウェイに対応するウェイがアクセスされ、このアクセスされたウェイに、要求されたデータ項目が含まれていることが確実となる。「空白」応答が提供されると、従来のn-ウェイ・連想キャッシュの場合と同様に、要求されたデータラインがキャッシュ内にあるか否かを決定するために、n-ウェイがアクセスされる。「予測された」ウェイは供給されないので、予測または推測を誤ってしまう可能性に配慮する必要がなくなる。コンテンツに基づいたアクセスを用いることにより、要求されたデータアドレスが、割り当てられたウェイを有しているか否かが決定されるため、選択的なウェイアクセスを用いることが出来るか否か、またはn-ウェイアクセスが必要か否かを、迅速に決定することが可能となる。【選択図】図２
2004530995.tif 000002
【特許請求の範囲】
【請求項１】
- 複数の格納されたデータラインをその各々が有する複数のセクションを有するキャッシュメモリと、
- 前記格納されたデータラインのアドレスに対応する限られた数のアドレスエントリと、前記格納されたデータラインの前記アドレスの各々に割り当てられたセクションと、を含めるように構成されているウェイ決定テーブルと、
を有するキャッシュシステムであって、
- 前記格納されたデータラインの各前記アドレスの前記割り当てられたセクションが、前記格納されたデータラインを含む前記キャッシュメモリの前記セクションを一意かつ明確に識別し、かつ、
- 前記キャッシュシステムが、
- アドレス指定されたデータ項目が、前記複数のセクションの選択されたセクションの対応するデータライン内に配置されているか否かを、前記アドレス指定されたデータ項目のラインアドレスと、前記格納されたデータラインの前記アドレスの対応する一つとの間の対応に基づいて、決定するように構成されており、
- 前記選択されたセクションが、前記格納されたデータラインの前記アドレスの前記対応する一つの割り当てられたセクションである、
キャッシュシステム。
【請求項２】
- 前記キャッシュシステムが、更に、
- 前記アドレス指定されたデータ項目の前記ラインアドレスに対応する現在のデータラインを、メモリから、前記複数のセクションの特定のセクションに格納し、かつ、
- 前記ラインアドレスに対応するアドレスと、前記特定のセクションの識別表示とを、前記アドレスエントリの1つと、割り当てられたセクションとして各々格納するように構成されている、
請求項１に記載のキャッシュシステム。
【請求項３】
- 前記アドレスエントリの前記1つが、最も長い間使用されていないアドレスエントリに対応する、請求項2に記載のキャッシュシステム。
【請求項４】
前記ウェイ決定テーブルが、
前記割り当てられたセクションが前記格納されたデータラインの前記アドレスに対応する前記現在のデータラインを含み続けているか否かに基づいて、その状態が決定される有効フィールドをも含む、請求項2に記載のキャッシュシステム。
【請求項５】
- 前記限られた数のアドレスエントリが、最も最近にアクセスされたラインアドレスに対応する、請求項1に記載のキャッシュシステム。
【請求項６】
前記ウェイ決定テーブルが、コンテンツ・アドレス指定可能メモリとして実施される、請求項１に記載のキャッシュシステム。
【請求項７】
- 前記キャッシュメモリが、前記複数のセクションを形成する複数のウェイを有するn-ウェイ・連想キャッシュに対応し、
- 各ウェイが更に、
- 前記複数の格納されたデータラインに対応する複数の格納されたタグを有し、
- 前記複数の格納されたデータラインと、前記複数の格納されたタグとの各々が、前記アドレス指定されたデータ項目の前記ラインアドレスの索引フィールドを介して一意にアドレス指定可能であり、
- 前記アドレス指定されたデータ項目の前記ラインアドレスが、前記格納されたデータラインの前記アドレスの何れにも対応していない場合、前記ラインアドレスのタグフィールドを、前記ウェイ内の前記ラインアドレスの前記索引フィールドに対応する、前記複数の格納されたタグの格納されたタグの1つと比較することにより、前記アドレス指定されたデータ項目が、前記複数のウェイの各ウェイ内に配置されているか否かを決定するように、前記n-ウェイ・連想キャッシュが構成されている、
請求項１に記載のキャッシュシステム。
【請求項８】
- 前記n-ウェイ・連想キャッシュが、更に、
- 前記アドレス指定されたデータ項目が、前記複数のウェイ内の前記対応するデータライン内に配置されていない場合、前記アドレス指定されたデータ項目を、メモリから、かつ前記複数のウェイの特定のウェイにロードし、かつ、
- 前記アドレス指定されたデータ項目の前記ラインアドレスに対応するアドレスと、前記特定のセクションの識別表示とを、前記アドレスエントリの1つと、割り当てられたセクションとして各々格納するように構成されている、
請求項7に記載のキャッシュシステム。
【請求項９】
- 前記アドレス指定されたデータ項目に対応する予測ウェイを設けるように構成されているウェイ予測テーブルを更に有し、かつ、
- 前記n-ウェイ・連想キャッシュが、更に、
- 前記アドレス指定されたデータ項目の前記ラインアドレスが、前記格納されたデータラインの前記アドレスの何れにも対応していない場合、
前記ラインアドレスの前記タグフィールドを、前記ウェイ内の前記ラインアドレスの前記索引フィールドに対応する、前記複数の格納されたタグの前記格納されたタグと比較することにより、
前記アドレス指定されたデータ項目が、前記複数のウェイの前記予測ウェイ内に配置されているか否かを決定するように構成されている、
請求項7に記載のキャッシュシステム。
【請求項１０】
- 前記アドレスエントリが、複数の前記格納されたデータラインのアドレスに対応するグループアドレスを有する、請求項１に記載のキャッシュシステム。
【請求項１１】
参照されたデータ項目を含む、複数のセクションを含むキャッシュのセクションを決定する方法であって、
- 前記参照されたデータ項目に対応するラインアドレスを決定し、
- 前記ラインアドレスが、格納されたデータラインの複数のアドレスの格納されたデータラインのアドレスに対応しているか否かを決定し、かつ、
- 前記ラインアドレスが、前記格納されたデータラインの前記アドレスに対応している場合、
- 前記格納されたデータラインの前記アドレスに対応する、前記キャッシュの前記セクションの識別子を提供する、
方法。
【請求項１２】
- 前記キャッシュの前記セクションの前記識別子を提供することが、
- 前記識別子の現在の有効性を決定し、かつ、
- 前記識別子が現在有効な場合のみ、前記識別子を提供すること、
を含む、請求項11に記載の方法。
【請求項１３】
- 前記ラインアドレスが、前記格納されたデータラインの前記複数のアドレスの何れにも対応していない場合、
- 前記参照されたデータ項目に対応するタグアドレスを決定し、
- 前記参照されたデータ項目に対応する索引アドレスを決定し、
- 前記参照されたデータ項目が、前記キャッシュの何れかのセクション内に含まれているか否かを決定するために、前記タグアドレスを、前記複数のセクションの各々の中の前記索引アドレスに関連付けられているタグフィールドと比較する、
請求項11に記載の方法。
【請求項１４】
- メモリ内のデータ項目にアクセスするように構成されているプロセッサと、
- 前記メモリ内の前記データ項目のサブセットを含めるように構成されている、前記プロセッサと前記メモリとに動作可能に結合されているキャッシュシステムと、
を有する処理システムであって、
- 前記キャッシュシステムが、
- 前記データ項目の前記サブセットに対応する複数の格納されたデータラインにその各セクションが対応する複数のセクションを有するキャッシュメモリと、
- 前記格納されたデータラインのアドレスに対応する限られた数のアドレスエントリと、前記格納されたデータラインの前記アドレスの各々に割り当てられたセクションとを含めるように構成されているウェイ決定テーブルと、
を有し、
-前記格納されたデータラインの前記アドレスの各々の前記割り当てられたセクションが、前記格納されたデータラインを含む前記キャッシュメモリの前記セクションを一意かつ明確に識別し、かつ、
- 前記キャッシュシステムが、
- 前記アドレス指定されたデータ項目のラインアドレスと、前記格納されたデータラインの前記アドレスの対応する1つとの間の対応に基づいて、アドレス指定されたデータ項目が、前記複数のセクションの1つの選択セクションの対応するデータのライン内に配置されているか否かを決定するように構成されており、
- 前記選択されたセクションが、前記格納されたデータラインの前記アドレスの前記対応する1つの割り当てられたセクションである、
処理システム。
【請求項１５】
- 前記キャッシュシステムが、更に、
- 前記アドレス指定されたデータ項目の前記ラインアドレスに対応する現在のデータラインを、前記メモリから、前記複数のセクションの特定のセクションに格納し、かつ、
- 前記ラインアドレスに対応するアドレスと、前記特定のセクションの識別表示とを、各々、前記アドレスエントリの1つと、割り当てられたセクションとして格納するように構成されている、
請求項14に記載の処理システム。
【請求項１６】
- 前記アドレスエントリの前記1つが、最も長い間使用されていないアドレスエントリに対応する、請求項15に記載の処理システム。
【請求項１７】
- 前記割り当てられたセクションが、前記格納されたデータラインの前記アドレスに対応する前記現在のデータラインを含み続けているか否かに基づいて、その状態が決定される有効フィールドをも、前記ウェイ決定テーブルが含んでいる、請求項14に記載の処理システム。
【請求項１８】
- 前記格納されたデータラインの前記限られた数のアドレスが、最も最近にアクセスされたラインアドレスに対応する、請求項14に記載の処理システム。
【請求項１９】
- 前記ウェイ決定テーブルが、コンテンツ・アドレス指定可能メモリとして実施される、請求項14に記載の処理システム。
【請求項２０】
- 前記アドレスエントリが、複数の前記格納されたデータラインのアドレスに対応するグループアドレスを有する、請求項14に記載の処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・システムの分野、特に、確定的なウェイ選択を用いるn-ウェイ・連想キャッシュに関する。
【背景技術】
【０００２】
キャッシュシステムは、一般的に、相対的に低速メモリ装置へのアクセスに付随する実効遅延を低減させるために用いられる。プロセッサが、低速メモリ内の特定のデータ項目へのアクセスを要求すると、キャッシュシステムは、この要求されたデータ項目をより高速のメモリにロードする。その後、この同じデータ項目へのアクセスは、この高速メモリを介して行われ、これにより、低速メモリに付随する遅延がなくなる。一般的に、データ項目が要求されると、この要求されたデータ項目を含むデータ項目の「ライン」が、低速メモリから高速メモリにロードされ、この結果、このロードされたライン内のいかなるデータ項目も、その後、高速メモリによって提供することが可能となる。
【０００３】
キャッシュメモリ・アクセス・システムの効果は、将来のデータアクセスが従来のデータアクセスに関連して行われる可能性が高いと言う状況のもとに考慮される。一般的に、要求されたデータ項目が、従来に要求されたデータ項目が含まれているのと同じキャッシュのラインに含まれている可能性は、実質的にゼロより高いため、これに応じて、高速のキャッシュメモリによりこの要求を満たす可能性は、実質的にゼロより高くなる。
【０００４】
高速メモリは低速メモリよりも高価なので、利用可能なキャッシュメモリの量は、通常限られてしまう。新しいデータのラインを高速メモリにロードする必要がある場合、どのデータ項目を高速メモリから除去すべきかを決定するために、キャッシュ管理方式が用いられる。データ項目を高速メモリ内に保持するために一般的に用いられる優先順位方式は、「最も長い間使用されていない (least recently used)」（LRU）という基準である。この場合、メモリアクセスの最も長い間使用されていない（すなわち、「より古い」）ラインは、新しいラインにより置換され、これによって、最近使用／アクセスされたデータ項目が保持される。他の「使用頻度が最多」のような基準も、通常、LRU優先順位方式と共に用いることが出来る。
【０００５】
要求された項目のアドレスのサブセットに基づいてデータ項目のラインを格納するには、通常、連想キャッシュが用いられる。図1は、連想キャッシュシステム100のための従来のアドレス指定方式を示す。通常、プロセッサ180からの以下に詳細に説明するアドレス110は、論理的に、タグフィールド111と、索引フィールド112と、ワードフィールド113とに分割される。索引フィールド112は、キャッシュメモリ120内の関連付けられているキャッシュラインの組への索引を提供する。この組の各キャッシュラインは、「ウェイ」、つまりメモリ120の「セクション」に対応しており、かつ、キャッシュメモリ120は、「n-ウェイ・連想キャッシュ」と呼ばれる。ワードフィールド113の大きさjは、データラインのサイズ2jに対応する。すなわち、データライン毎に16ワードある場合、ワードフィールド113の大きさは4ビットとなり、データライン毎に64ワードある場合、ワードフィールド113は6ビットの広さになるであろう。タグフィールドと索引フィールドは、ワードフィールド113とデータラインの大きさとの間のこの2乗関係を利用して、メモリ内の各データラインを一意に識別する。
【０００６】
アドレス指定されているデータ項目が、低速メモリ（図示せず）からキャッシュメモリ120内にロードされると、このデータ項目を含むデータのラインは、選択されたウェイに配置される。これは、索引フィールドが、このデータラインを配置するための、この選択されたウェイ内の場所を定義しているからである。ウェイの選択は、前述したLRU優先順位方式のような、一般的に利用可能な様々なアルゴリズムの1つを用いることにより達成される。アドレス指定されているデータ項目が、キャッシュ120内の特定のライン領域DLine-a、DLine-bなどに格納されると、図1のタグ-a 121a、タグ-b 121bなどのフィールドが示すように、タグフィールド111も格納される。データラインの索引フィールド112に対応する、ウェイ内のデータラインの場所と組み合わされた格納されたタグフィールド121は、キャッシュ120内に格納されているデータラインを一意に識別する。
【０００７】
アドレス指定されているデータ項目がキャッシュ120にロードされる前に、データ項目が既にキャッシュ120に配置されているか否かを決定するためにキャッシュ120が検査されるので、低速メモリからデータ項目をロードすることは潜在的に不必要となる。アドレス指定されているデータ項目は、このデータ項目への以前のアクセス、または、現在アドレス指定されているデータ項目と同じデータのラインDLine-a、DLine-bなどの中のデータ項目への以前のアクセスにより、キャッシュ内に配置することが出来る。索引フィールド112は、このアドレスに関連付けられているキャッシュ120内のnラインの組を定義する。この関連付けられた組の中に格納されたライン125a、125bの各々に対応する格納されたタグ121a、121bなどの各々は、コンパレータ130a、130bなどを介して、アドレス指定されたデータ項目のタグフィールド111と比較される。この比較が行われている間、索引フィールド113に対応する格納されたデータライン125a、125bなどの各々は、高速のバッファ140にロードされ、この結果、このデータ項目がキャッシュ120に現在ロードされている場合、使用可能となる。
【０００８】
アドレス指定されたデータ項目が、キャッシュ120のウェイ120a、120bなどの1つに現在ロードされている場合、対応するコンパレータ130a、130bなどが、キャッシュ・ヒット信号をアサートし、これにより、このデータラインを含むHit-a, Hit-bなどの特定のウェイが識別される。ヒットがアサートされると、バッファ140に含まれているデータラインから適切なワード141a、141bなどを選択するためのワードフィールド113を用いることにより、適切なワードが、対応するバッファ140から検索される。検索されたワードは、アドレス110を供給するプロセッサ180に転送される。キャッシュシステム100の従来の実施例では、キャッシュ・ヒットが起こった場合に、タグフィールド111を格納されているタグフィールド121a、121bなどと比較し、かつその後141a、141bなどの適当なワードを選択するために要する時間は、実質的に、低速メモリに対応する遅延時間よりも短い。このように、データ項目がキャッシュ120内に配置されていると、データ項目への実際のアクセス時間が、著しく短縮される。
【０００９】
キャッシュ・ヒットが起こらない場合、一般的に、上述した、最も長い間使用されていない（LRU）ウェイにデータラインをロードすること、または他の優先順位方式により、アドレス指定されたデータラインのメモリからキャッシュ120の選択されたウェイ（ウェイ-a 120a、ウェイ-b 120bなど）への上述したロードが、実行される。
【００１０】
プロセッサ180からメモリにワードを効果的に格納するために要する時間は、キャッシュシステム100を用いることにより、同様に短縮される。アドレス指定されたデータ項目がキャッシュ120内に存在することは、上述した比較処理を用いることにより決定される。データ項目が、現在、キャッシュ120内に配置されている場合、バッファ140の選択されたワードは、プロセッサ180からのデータ項目の新たな値により置換され、かつ、バッファ140が、アドレス指定されたデータ項目を含むデータライン125a、125bなどにロードされる。「変更された」フィールド129は、キャッシュされたラインのコンテンツが変更されたことを示すために用いられる。データラインが新たなデータラインにより上書きされる前に、変更されたフィールド129が検査され、かつ、データラインが変更されている場合、このラインを格納するためのメモリ内の場所を識別するために、変更されたデータラインが、格納されたタグフィールド121a、121bなどを用いてメモリ内に戻されて格納される。
【００１１】
n-ウェイ・連想キャッシュは、実際のメモリアクセスの速さを増加させるための有効な手段となるが、アドレス指定されているデータ項目のタグが、格納されているタグの全てと比較されるこの同時ウェイ-比較方式は、一方向の連想キャッシュよりもn倍高い率でエネルギーを消費する。n-ウェイ・連想キャッシュが、集積回路の他の領域、つまり、プリント回路板よりも実質的に高温になることは、珍しいことではない。
【００１２】
従来のn-ウェイ・連想キャッシュの電力消費を低減させるために、予測技術を適用して、所定のアドレスに対応している可能性のあるウェイを選択する。ウェイ予測方式の従来の実施例の場合、可能性のあるウェイは、最初に、アドレス指定されたデータ項目に対して検査され、かつ、このウェイがアドレス指定されたデータ項目を含んでいない場合のみ、残りのウェイが検査される。本願明細書において引用されている、Koji Inoueらによる「推論的なウェイ選択による高性能かつ低電力なキャッシュ構造 (HIGH-PERFORMANCE AND LOW-POWER CACHE ARCHITECTURE WITH SPECULATIVE WAY-SELECTION)」（IEICE Trans. Electron., Vol. E83-C, No.2、pp.186〜194、2000年2月）は、ウェイ予測方式と、ウェイ予測方式と非予測的な方式とによるエネルギー消費の比較を紹介している。予測成功率が高い場合、ウェイ予測が正確である毎にエネルギーがn倍低減されるため、エネルギーをかなり大きく節減させることが出来る。
【００１３】
図1には、アドレス指定されたデータ項目に関連付けられた特定のウェイ120a、120bなどを予測するために用いられる、例示的なウェイ予測テーブル150が示されている。図1の点線が示すように、データアドレス110のサブセット115は、ウェイ予測テーブル150に索引を付けるために用いられる。アドレス110のこのサブセット115を定義し、かつ、ウェイ予測テーブル150のコンテンツを供給するために用いるアルゴリズムを定義するために、様々な方式を用いることが出来る。直接的な実施例の場合、索引フィールド113は、テーブル150に索引を付けるために用いるサブセット115として用いられ、かつ、テーブル150のコンテンツは、各索引113に対して、最も長い間使用されていない（LRU）ウェイ（ウェイ-a 120a、ウェイ-b 120bなど）に対応する。これに代えて、ウェイ予測テーブル150に索引を提供するために、索引フィールド112のサブセット115、またはタグフィールド111と索引フィールド112の両方から取り出されたサブセット115を用いることも出来る。ウェイ予測テーブルに索引を付けるために用いられる、アドレス110のサブセット115を選択することと、ウェイの数nとにより、必要なウェイ予測テーブルの大きさが決定する。8-ウェイ・連想キャッシュの場合、ウェイ予測テーブル内の各ウェイを一意に識別するためには3つのビットが必要となり、かつ、テーブル150内の3ビットのエントリの数は、テーブル150に索引を付けるために用いられるアドレスのサブセット115の固有の組合せの数により決定する。例えば、テーブル150に索引を付けるために、10ビット（i=10）をサブセット115として用いた場合、1024（2i）個の3ビットのエントリが、テーブル150内でサポートされなければならない。テーブル150の長さ（2i）は、アドレス指定可能なラインの数（2M-w（Mはアドレス内のビット数で通常は16、32または64であり、かつwは、ライン毎のワード数（通常は4、8、16または32）に対応するビット数（通常は2〜5）である））よりも実質的に短いことに留意されたい。すなわち、テーブル150への索引は、タグフィールド111と索引フィールド112の適切なサブセット115である。
【００１４】
アドレス110が要求されると、ウェイ予測テーブル150からの予測ウェイを用いることにより、予測ウェイのみに選択的にアクセスする。全てのアドレスは、対応する予測ウェイを有するが、テーブル150への索引は、アドレス指定可能なラインの数のサブセットであるため、異なるアドレス110は、各々、テーブル150内の同じエントリを指し示すことが出来る。実際には、これらの異なるアドレスの1つしか、任意の所定の時間にテーブル150のコンテンツが示すウェイ内に格納されるデータに対応することが出来ない。「予測された」という用語が用いられるのは、このためである。
【００１５】
以下、便宜のため、予測ウェイを示すために添字pを用いる。選択されたウェイ120p内の索引フィールド112に対応する格納されたタグ121pは、選択されたウェイ120pのコンパレータ130pに供給され、かつ対応するデータライン125pは、選択されたウェイ120pのバッファ140pに提供される。予測ウェイ120pがデータラインを含み、かつ、アドレス指定されたワードが、バッファ140pから、要求を行うプロセッサ180に供給されると、Hit-p信号がアサートされる。予測ウェイ120pが、アドレス指定されたデータ項目を含んでいない場合、上述したアドレス指定されたデータ項目に対するn-ウェイ・連想キャッシュを検査するための技術を用いることにより、アドレス指定されたデータ項目が存在するか否かの検査が、他の予測されていないウェイの各々に対して行われる。
【００１６】
アドレス指定されたデータ項目が、どのウェイにも含まれていない場合、アドレス指定されたデータ項目を含むデータラインは、メモリからキャッシュ120（通常は、索引位置における最も長い間使用されていないウェイ）にロードされる。ウェイ予測テーブル150が、最近の使用頻度が最大のウェイを格納するように構成されていることを想定すると、データラインを格納するために用いられたウェイの識別表示が、ウェイ予測テーブル150に格納される。このように、現在アドレス指定されているデータ項目と同じデータライン内のデータ項目に対する次の要求は、正確な予測ウェイを生じ、かつこれにより電力消費を節約するであろう。
【００１７】
この電力節約方式の変種を用いることも出来る。例えば、タグ121a、121bなどの全ては、対応するコンパレータ130a、130bなどにロード可能であるが、バッファ140pには、予測ウェイ120pのデータライン125pしかロードすることが出来ない。このように、予測ウェイにアドレス指定されたデータ項目が含まれていない場合、予測されなかったウェイのデータライン125a、125bなどの全てをバッファ140a、140bなどにロードすることはせず、同時に、タグフィールド121a、121bなどを全て再確認するために要する時間もなくすことにより、ある程度の電力節約が達成される。他のタグコンパレータ130の1つがヒット信号をアサートした場合、対応するウェイのデータライン125が、対応するバッファ140にロードされ、かつ適切なワードが、プロセッサ180に供給される。他のどのタグコンパレータ130もヒット信号をアサートしない場合、アドレス指定されたデータラインが、上述したように、メモリからキャッシュ120にロードされる。
【００１８】
図1に示す従来のウェイ予測方式の場合、ウェイ予測が不正確な際に、この誤予測されたウェイ内のデータラインへのアクセスと、この誤予測の他の影響とを「無効にする」有効な手段が必要となることに留意されたい。ウェイ予測方式は、通常、メモリからの値を必要とする時間になる前にメモリアクセスが開始する、パイプライン構成で用いられる。予測ウェイが、アドレス指定されたデータ項目を含んでいるか否かを決定し、かつその後、アドレス指定されているデータ項目がこれらのウェイの何れかに含まれているか否かを決定するためには時間がかかるため、キャッシュ・ミスを直ちに決定することは出来ない。キャッシュ・ヒットまたはキャッシュ・ミスが決定されている時間の間、キャッシュ・ヒットにより得られる速さの増加を利用するために、パイプライン処理は、通常、キャッシュ・ヒットを期待しながら処置を実施する。キャッシュ・ミスが発生した場合、キャッシュ・ヒットを期待した処置の効果の一部または全てを、無効にしなければならない。誤予測の無効化を確実に達成するために必要な回路とタイミングとの制約条件は、かなり複雑なものとなり得る。しかしながら、ウェイ予測方式により達成可能な電力節約と、キャッシュ・ヒットが頻繁に生じることにより達成可能な速さの増加とにより、この複雑な回路が加わることに付随する付加的な設計と生産コストは、通常相殺される。
【非特許文献１】
Koji Inoueら著「推論的なウェイ選択による高性能かつ低電力なキャッシュ構成 (HIGH-PERFORMANCE AND LOW-POWER CACHE ARCHITECTURE WITH SPECULATIVE WAY-SELECTION)」IEICE Trans. Electron., Vol. E83-C, No.2、pp.186〜194、2000年2月
【発明の開示】
【課題を解決するための手段】
【００１９】
この発明の目的は、確定的なウェイ-識別を可能にする方法とシステムとを提供することである。この発明の更なる目的は、ウェイの誤予測の処理を不要にする方法とシステムとを提供することである。この発明の更なる目的は、誤予測の無効化処理を必要とする従来のウェイ予測方式よりも複雑でないウェイ-決定方式を提供することである。この発明の更なる目的は、アドレス指定されているデータ項目が、キャッシュのウェイ内にあることが既知か否かを直ちに決定するウェイ-識別方式を提供することである。
【００２０】
これらの目的と他の目的は、要求されたデータ項目のラインアドレス全体に基づいたn-ウェイ・連想キャッシュのためのウェイ-決定方式を提供し、これによって、要求されたデータ項目を含むウェイを誤識別してしまう可能性をなくすことにより、達成される。限られた数のラインアドレスと、これらの割り当てられたウェイとが、ウェイ決定テーブル (Way Determination Table) 内に格納される。要求されたデータアドレスが、これらのラインアドレスの1つに対応している場合、割り当てられたウェイが供給され、対応していない場合、「空白」応答が提供され、ウェイがこのデータアドレスに対して既知ではないことが示される。割り当てられたウェイが供給されると、この割り当てられたウェイに対応するウェイがアクセスされ、要求されたデータ項目がこのアクセスされたウェイに含まれていることが確実となる。「空白」応答が提供された場合、従来のn-ウェイ・連想キャッシュの場合と同様に、要求されたデータラインがキャッシュ内にあるか否かを決定するために、n-ウェイがアクセスされる。「予測された」ウェイは供給されないので、予測または推測を誤ってしまう可能性に配慮する必要がなくなる。コンテンツに基づいたアクセスを用いて、要求されたデータアドレスが、割り当てられたウェイを有するか否かを決定することにより、選択的なウェイアクセスが利用可能か否か、またはn-ウェイアクセスが必要か否かを、迅速に決定することが出来る。
【発明を実施するための最良の形態】
【００２１】
本発明を、添付の図面を参照しながら更に詳細に、かつ具体例により説明する。
【００２２】
同じ参照番号は、全ての図面を通じて、類似または対応する特徴または機能を示す。後付き記号文字を有する項目は、共通する特徴または関数の特定の例を示す。本願明細書内において特定の後付き記号文字がない項目を参照している箇所は、同じ数字による参照符を有する図示された項目の何れかまたは全てを示す。
【００２３】
図2は、この発明によるウェイ-決定を用いたn-ウェイ・連想キャッシュシステム200の例示的なブロック図を示す。限られた数のラインアドレス251を、割り当てられたウェイ252にマッピングする、ウェイ-決定テーブル250が設けられている。各ラインアドレス251は、一意かつ明確にデータのラインDLine 125を識別し、かつ、割り当てられたウェイ252は、データのライン125を含むウェイ（ウェイ-a 120a、ウェイ-b 120bなど）を一意かつ明確に識別する。すなわち、低速メモリ内のアドレス指定可能なワードのアドレス空間が2Mであり、かつ、ライン毎のワード数が2wである場合、2M/2w（2M-w）本の一意にアドレス指定可能なラインが存在するであろう。このように、この例の場合、ラインアドレス251は、M-wビットの広さで、かつ、データアドレス110のタグフィールド111と索引フィールド112とに対応する。
【００２４】
この発明によると、各ラインアドレス251が、データのラインを一意に識別し、かつ、各割り当てられたウェイ252が、各ウェイを一意に識別するので、割り当てられたウェイ252に対応するウェイ120a、120bなどが、アドレス指定されたラインを含んでいるか否かという点に関する曖昧さがない。一方、図1の従来のウェイ予測方式の場合、複数のラインアドレス（タグ111と索引112との組合せ）が、同じ索引を予測的なウェイテーブル150に提供するため、予測ウェイ120pが、現在アドレス指定されているラインを実際に含んでいるか否かという点が、常に不明確である。
【００２５】
データアドレス110が受信されると、データアドレス110に対応するデータラインが、割り当てられたウェイ252内に格納されていることが既知であるか否かを決定するために、ウェイ-決定テーブル250が検査される。データアドレス110のタグフィールド111と索引フィールド112とに対応するアドレス指定されたデータライン215が、ウェイ-決定テーブル250内に含まれている場合、このアドレス指定されたデータライン215に対応する割り当てられたウェイ252が、このデータライン215を含む既知のウェイとして供給される。便宜上、ウェイ-決定テーブル250から供給された既知のウェイを示すために、kという文字を用いる。アドレス指定されたデータライン215が、ウェイ-決定テーブル250内に含まれていない場合、「空白」応答、つまり「失敗」応答が提供される。
【００２６】
好ましい実施例の場合、ウェイ-決定テーブル250が、本技術分野では一般的なコンテンツ・アドレス指定可能メモリ（CAM）構造を有することにより、アドレス指定されたデータライン215が、テーブル250内に含まれているラインアドレス251の1つであるか否かが直ちに示される。
【００２７】
既知のウェイ（k）が供給された場合、ウェイ120kからのデータライン125kがアクセスされ、かつHit-k信号がアサートされる。「空白」応答が提供された場合、従来のn-ウェイ・連想キャッシュの場合のように、複数のウェイ120a、120bなどがアクセスされ、データラインがキャッシュ120内のウェイの何れかの中に配置されているか否かが決定される。
【００２８】
図1の従来の予測的なキャッシュシステムと比べると、割り当てられたウェイ252は、各ラインアドレス251に一意に割り当てられるため、ウェイ-決定テーブル250からの既知のウェイを誤決定（誤予測）してしまう可能性に配慮した機能を設ける必要がない。しかしながら、図1の従来の予測的なキャッシュシステムと比較すべき更なる点は、限られた数のデータアドレスしか、ウェイ-決定テーブル250内に対応するエントリ251があるラインアドレス215を有さないであろう、ということである。従来の予測的なキャッシュシステムの場合、全てのデータアドレスが、ウェイ予測テーブル150内に索引115を提供するであろう。すなわち、この発明のウェイ-決定システム200は、限られた数のデータアドレスに対して正確なウェイ-決定を行うが、従来のウェイ予測システム100は、いかなるかつ全てのデータアドレスに対して潜在的に不正確なウェイ予測を行う。
【００２９】
どのラインアドレス251が、ウェイ-決定テーブル250に含まれているのかを決定するために、様々な技術を用いることが出来る。例えば、特定のデータ項目またはデータタイプに対応するラインアドレスは、テーブル250に格納可能である。本発明の好ましい実施例の場合、設計の複雑さを最小化するために、MRU（最も最近に使用された）アルゴリズムを用いて、最も最近にアクセスされたN個のラインアドレス215をテーブル250にロードする（Nは、テーブル250の長さである）。アドレス指定されたデータライン215が、ウェイ-決定テーブル250内に配置されていないことが判明した場合、キャッシュシステム200は、従来のn-ウェイキャッシュの場合のように、キャッシュ120のウェイの1つの中にデータラインを見つけること、または、低速メモリからのデータラインを、キャッシュ120のウェイの1つにロードすることの何れかを行うであろう。データラインのアドレス215と、今ではデータラインを含む、見つかったウェイまたはロードされたウェイの識別表示とは、各々テーブル250内で、ラインアドレス251と割り当てられたウェイ252として格納される。その後、このデータラインに次にアクセスする際、テーブル250内のこのエントリが、より最近に使用されたデータラインのラインアドレスとウェイとにより置換されるまで、既知のウェイkが設けられる。テーブル250内の最も長い間使用されていないエントリは、MRUアルゴリズムに呼応して、テーブル250内の各新しいエントリにより置換される。
【００３０】
エントリを「無効化」するために、「有効な」フィールド253も、キャッシュテーブル250内に含まれている。キャッシュシステムがデータラインをキャッシュに加えると、以前に格納されたデータラインは、このデータラインにより置換される。この以前に格納されたデータラインがテーブル250内のエントリに対応している場合、このエントリは、有効フィールド253の適切なマーキングにより無効化される。テーブル250内のエントリの無効化は、稀にしか発生しないと予想することが出来る。なぜならば、キャッシュ120内のデータラインの数は、一般的にテーブル250内のエントリの数よりも多く、かつ、キャッシュシステム200の一般的な置換方法は、最も長い間使用されていないデータラインを置換することであるのに、テーブル250は、最も最近に使用されたデータラインのラインアドレスを格納するように構成されているためである。本発明の好ましい実施例の場合、前述したMRUアルゴリズムは、無効化されたどのエントリでも、新しいエントリを追加するための好ましい場所として使用することにより、テーブル250内の無効化されるエントリの数を最小化するように、変更されている。
【００３１】
テーブル250内に含まれているラインアドレスの数Nにより、データアクセスのための既知のウェイが供給される可能性が決定される。隣接したデータ項目は、共通の時間範囲内にアクセスされ易いため、データライン毎のデータ項目数nも、既知のウェイが供給される可能性に影響を与える。データライン毎のデータ項目の数nは、通常、全体的なキャッシュ設計パラメータに基づいて決定され、かつ通常、データライン毎に8、16、または32ワードに対応している。テーブル250内の各エントリは、ラインアドレス251を含めるためのM-wビットと、割り当てられたウェイ252と有効フィールド253とを含めるための4〜6ビットを必要とするため、好ましいコンテンツ・アドレス指定可能なテーブル250内の各エントリの相対的なコストは、かなり大きくなる。好ましい実施例では、従来のベンチマーク試験を用いた場合、テーブル250内の僅か4つのエントリしか、平均ヒット率が50%を超さないことが判明している。すなわち、データライン毎に僅か8ワードしかない場合、最も最近にアクセスされた4本のデータラインを格納するように構成されているテーブル250を用いることにより、既知のウェイが、データアクセスの少なくとも半分に対して供給された。データライン毎に32ワードある場合、テーブル250内の4つのエントリの平均ヒット率は、70%を上回り、かつ8つのエントリの場合、80%を上回った。
【００３２】
図2の例示的な実施例の代替手段は、この開示内容を考慮することにより、当業者に明らかとなるであろう。例えば、空間的に関連付けられているキャッシュラインのグループ識別によりアクセス可能なウェイ-決定テーブルを設けることにより、キャッシュアクセスの空間的な局所性を活用することが出来る。例示的なグループが4つのラインを有する以下のテーブルは、この考え方を示している。各グループアドレスのエントリの後には、一組のウェイ-有効の対が続いている。このウェイのエントリは、このグループ内の対応するラインを含んでいる特定のウェイと、このウェイのエントリが現在有効であるか否かとを識別する。この例示的なテーブルの場合、第一グループアドレスの第一ライン（Line00）は、ウェイA内に配置されており、かつ現在有効であるのに対して、第一グループのアドレスの第二ラインは、ウェイC内に配置されていると示されているが、このエントリは無効であるとマーキングされている。本発明によると、第一グループの第一ライン内のデータ項目を参照すると、「既知のウェイ(known way)」というAの値が返され、かつ、第一グループの第二ライン内のデータ項目を参照すると、「失敗(failed)」という値が返されるであろう。好ましい実施例の場合、グループアドレスは、このグループに共通なラインアドレスの最も重要なビットである。すなわち、ラインアドレスの広さがNビットで、かつ、このグループに4つのラインが含まれている場合、グループアドレスは、このアドレスの最も重要なN-2ビットとなる。データ項目がアドレス指定されている場合、データ項目の最も重要なN-2ビットは、グループアドレスとなり、かつ次の2つのビットは、テーブル内のどの「ウェイ-値」エントリの対がアドレス指定されたラインに対応しているのかを決定する。同様に、8本のラインをグループ化することは、最も重要なN-3ビットのグループアドレスに対応することになり、かつ次の3つのビットは、どの「ウェイ-有効」の対が特定のアドレス指定されたウェイに対応しているかを決定するであろう。
【表１】
2004530995.tif 000003
【００３３】
上記は、本発明の原理を単に例示したものである。したがって、本願明細書には明確に記述または図示されていないが、本発明の原理を実施し、かつしたがって、その趣旨と目的の範囲内にある様々な構成が、当業者には考案可能となることが認識されよう。例えば、設計の複雑さが懸念事項でない場合、従来のウェイ予測方式を置換ではなく強化するために、この発明を用いることが出来る。このような実施例の場合、例えば、既知のウェイが見つからない場合、キャッシュ内のウェイの全体を評価する前に、予測ウェイを評価することが出来る。また、図中における機能の特定の分割化も、説明の便宜上のものである。例えば、キャッシュシステムの全てまたは一部を、プロセッサ内、または低速メモリを含むメモリ管理システム内などに含めることが出来る。さらに、図示した機能の幾つかまたは全てを、ハードウエア、ソフトウエア、またはファームウェア・ブロックとして実施することが出来る。これらと他のシステム構成と最適化機能は、この開示内容を考慮することにより当業者に明らかとなるであろうし、かつ、請求の範囲内に含まれている。
【図面の簡単な説明】
【００３４】
【図１】ウェイ予測を用いた従来技術のn-ウェイ・連想キャッシュの例示的なブロック図を示す。
【図２】この発明によるウェイ-決定を用いたn-ウェイ・連想キャッシュの例示的なブロック図を示す。
【符号の説明】
【００３５】
100…連想キャッシュシステム
110…アドレス
111…タグフィールド
112…索引フィールド
113…ワードフィールド
115…サブセット
120…ウェイ
121…タグ
125…データライン
129…変更されたフィールド
130…コンパレータ
140…バッファ
141…ワード
150…ウェイ予測テーブル
180…プロセッサ
215…データライン
250…ウェイ-決定テーブル
251…ラインアドレス
252…割り当てられたウェイ
253…有効なフィールド
【図１】
2004530995.tif 000004
【図２】
2004530995.tif 000005
【国際公開パンフレット】
2004530995.tif 000006
2004530995.tif 000007
2004530995.tif 000008
2004530995.tif 000009
2004530995.tif 000010
2004530995.tif 000011
2004530995.tif 000012
2004530995.tif 000013
2004530995.tif 000014
2004530995.tif 000015
2004530995.tif 000016
2004530995.tif 000017
2004530995.tif 000018
2004530995.tif 000019
2004530995.tif 000020
2004530995.tif 000021
2004530995.tif 000022
2004530995.tif 000023
2004530995.tif 000024
2004530995.tif 000025
【国際公開パンフレット（コレクトバージョン）】
2004530995.tif 000026
【国際調査報告】
2004530995.tif 000027
2004530995.tif 000028