(57)【特許請求の範囲】
【請求項１】
データ・アドレスを使用したセット連想メモリのアクセスを高速にする方法であって、該アドレスはそれぞれオフセット部、コングルエンス・クラス・インデックス、タグ部を含み、該セット連想メモリはアレイとディレクトリを含み、該アレイはデータを格納し、複数のアレイ・コングルエンス・クラスに分けられ、該アレイ・コングルエンス・クラスはアレイ・セットに分けられ、該アレイ・セットはデータを持つキャッシュ・ラインを含み、該ディレクトリは複数のディレクトリ・コングルエンス・クラスに分けられ、該ディレクトリ・コングルエンス・クラスはディレクトリ・セットに分けられ、該ディレクトリ・セットはディレクトリ・エントリを含み、該ディレクトリ・エントリはアドレス・タグを含み、該ディレクトリは、該アドレス・タグが該キャッシュ・ラインのうち少なくとも１つと関連付けられるよう、該ディレクトリ・エントリと該キャッシュ・ラインが１：１で対応するように分けられ、且つ、
前記コングルエンス・クラス・インデックスを使用して、前記コングルエンス・クラス・インデックスにより指定されるシングル・アレイ・コングルエンス・クラスのセットの内容をアクセスするステップと、
前記コングルエンス・クラス・インデックスを使用して、前記コングルエンス・クラス・インデックスにより指定されるシングル・ディレクトリ・コングルエンス・クラスのセットの内容をアクセスするステップと、  セット選択情報を生成するステップと、
前記セット選択情報を利用して、前記アレイ・コングルエンス・クラスの前記セットを、前記ディレクトリにより指定される前記シングル・コングルエンス・クラスの出力よりも前に選択するステップと、
前記セット選択情報をもとに前記選択済みセットの前記キャッシュ・ラインから前記データを出力するステップと、
を含む、方法。
【請求項２】
前記タグ部を前記ディレクトリ・コングルエンス・クラスの前記選択済みセットの前記アドレス・タグと比較するステップと、
前記選択済みコングルエンス・クラスの前記アドレス・タグの１つが前記アドレスの前記タグ部に等しい場合は、前記選択済みセットを前記セット選択情報と比較するステップと、
前記選択済みコングルエンス・クラスの前記アドレス・タグがどれも前記アドレスの前記タグ部に等しくない場合は、第１制御信号を出力して、前記アクセスが不成功だったことと、前記キャッシュ・ラインから出力された前記データが無効なことを示し、前記選択済みセットが前記セット選択情報に等しくない場合は、第２制御信号を出力して、前記キャッシュ・ラインからの前記データが無効なことを示すステップと、
を含む、請求項１記載の方法。
【請求項３】
前記アドレスは第１パーティションと第２パーティションを含み、該第１パーティションはアレイ・オフセット部、アレイ・コングルエンス・クラス・インデックス、アレイ・タグ部を含み、該第２パーティションはディレクトリ部、ディレクトリ・コングルエンス・クラス・インデックス、ディレクトリ・タグ部を含み、該アレイ・コングルエンス・クラス・インデックスと該ディレクトリ・コングルエンス・クラス・インデックスは長さが可変であり、前記アレイと前記ディレクトリは異なるセット連想性を含む、請求項１記載の方法。
【請求項４】
前記オフセット部を利用して、前記キャッシュ・ラインから出力するデータを選択するステップを含む、請求項３記載の方法。
【請求項５】
予測されたセット以外のセットに、前記アレイ・タグ部に一致するアドレス・タグがある場合は、前記選択済みセットの前記キャッシュ・ラインからデータを出力するステップを含む、請求項１記載の方法。
【請求項６】
予測されたセット以外のセットに、前記ディレクトリ・タグ部に一致する前記アドレス・タグがある場合は、前記選択済みセットの前記キャッシュ・ラインからデータを出力するステップを含む、請求項３記載の方法。
【請求項７】
前記セット選択情報はブランチ・ターゲット・バッファにより提供される、請求項１記載の方法。
【請求項８】
命令アクセス用の前記セット選択情報はブランチ・ターゲット・バッファにより提供される、請求項３記載の方法。
【請求項９】
オペランド・アクセス用の前記セット選択情報は従来の命令アクセスにより提供される、請求項１記載の方法。
【請求項１０】
オペランド・アクセス用の前記セット選択情報は従来の命令アクセスにより提供される、請求項３記載の方法。
【請求項１１】
オペランド・アクセス用の前記セット選択情報はオペランド履歴テーブルにより提供される、請求項１記載の方法。
【請求項１２】
オペランド・アクセス用の前記セット選択情報はオペランド履歴テーブルにより提供される、請求項３記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ・メモリ・システムに関して、特にセット連想キャッシュのアクセス遅延を少なくする方法及び装置に関する。
【０００２】
【従来の技術】
キャッシュ・メモリは、通常はＣＰＵ（中央処理装置）とメイン・メモリの間に位置する小型で高速なバッファである。キャッシュは、現在使用中とみなされるメイン・メモリの内容を一時的に格納するために使用される。キャッシュの内容をいつ入れ替えるかに関する決定は、通常はＬＲＵ（least recently used、最長時間未使用）アルゴリズムがもとになる。ＬＲＵアルゴリズムでは、キャッシュ・メモリ位置は、未使用時間が最短のメイン・メモリの内容と入れ替えられる。キャッシュ・メモリの情報は、メイン・メモリの情報よりかなり短い時間でアクセスできる。従って、命令やオペランドがキャッシュにフェッチまたは格納されるときのＣＰＵの待ち時間は少なくなる。
【０００３】
直接マップ・キャッシュでは、メイン・メモリの位置の内容の記憶域はキャッシュの特定の位置に限定される。逆に、Ｍウェイ・セット連想キャッシュは、各メイン・メモリ位置の内容をキャッシュのＭ個の位置にマップする。Ｍウェイ・セット連想キャッシュは、基本的にはＭ個の同一の直接マップ（direct-mapped）・キャッシュを組み合わせたものである。しかし、Ｍウェイ・セット連想（set-associative）キャッシュからのアクセスと検索はより複雑である。Ｍウェイ・セット連想キャッシュへのメモリ・アクセスでは常に、Ｍ個の同じ直接マップ・キャッシュの組み合わせのそれぞれを検索し、対応するデータを選択して、一致があれば出力に多重化しなければならない。ミスが起こると、どのキャッシュ・ラインを削除し、比較的最近用いられたメイン・メモリの内容で書換えなければならないかに関して、Ｍ個の可能なキャッシュ・ライン間で選択を行う必要がある。
【０００４】
図１に、キャッシュ・ディレクトリ１０、キャッシュ・アレイ１２、ディレクトリ・マルチプレクサ１４、アレイ・マルチプレクサ１６で構成される従来技術による仮想タグ付き４ウェイ・セット連想キャッシュ・メモリを示す。キャッシュ・ディレクトリ１０は、キャッシュ・アレイ１２の対応する各位置の仮想アドレスを含む。キャッシュ・アレイ１２は、キャッシュ・ディレクトリ１０の対応する位置またはブロックによって示されるメイン・メモリ位置の内容を格納する。セットは、キャッシュ・アレイ１２の列とキャッシュ・ディレクトリ１０内の対応する列として定義される。キャッシュ・アレイ１２の行、及びキャッシュ・ディレクトリ１０の対応する行としてコングルエンス・クラスが定義される。特定のセット（列）と特定のコングルエンス・クラス（行）の交差部としてブロックまたは位置が定義される。位置やブロックはデータのバイトを含む。
【０００５】
キャッシュ・メモリに送られるアドレス１８は、ディレクトリ・タグ２０、コングルエンス・クラス２２、及びブロック・オフセット２４を含む。ディレクトリ・タグ２０は、ディレクトリ・マルチプレクサ１４を経てキャッシュ・ディレクトリ１０の所望のセット（列）を選択するために使用される。コングルエンス・クラス・タグ２２は、キャッシュ・ディレクトリ１０とキャッシュ・アレイ１２の両方の所望のコングルエンス・クラス（行）を選択するために使用される。ブロック・オフセット２４は、所望のブロックまたは位置内の所望のバイトを選択するために使用される。ディレクトリ・マルチプレクサ１４の出力は、アレイ・マルチプレクサ１６を介してキャッシュ・アレイ１２の所望のセット（列）を選択するために使用される。
【０００６】
連想キャッシュのアクセス遅延は、直接マップ・キャッシュのアクセス遅延よりも大きいが、これは、キャッシュ・ディレクトリ１０の複数のセットにまたがって格納されたタグに対してアドレスを比較する必要があるためである。一致があると、一致するタグに関連付けられたセットが、キャッシュ・アレイ１２の対応するセットから出力を選択するために使用される。キャッシュ・アレイ１２の出力は、最終的にレジスタと機能ユニットにルーティングされる。いわゆる"遅延選択問題"は、キャッシュ・アレイ１２の対応するセットを選択する前に、アドレスをキャッシュ・ディレクトリ１０で検索する必要があること、また、アドレス変換（物理タグ付けキャッシュが使用される場合）の可能性もあることをいう。従って、遅延選択問題は、セット連想キャッシュの遅延に悪影響を与える。
【０００７】
従って、キャッシュ・ディレクトリを検索してアドレスを変換する前に、セット選択情報を利用できれば好都合である。
【０００８】
キャッシュに関して詳しくは、以下の文献を参照されたい。
１．Emmaらによる米国特許第５６３４１１９号
２．Chang、Sheldon S. L. によるElectrical and Computer Engineering III（1983）
３．Smith、Allan J. によるCache Memories - ACM Computing Surveys Vol. 14（1982）
４．Cekleov M. 、Dubois M. によるVirtual-Address Caches - IEEE Micro（1997）
【０００９】
【課題を解決するための手段】
本発明の実施例に従って、セット連想キャッシュのアクセス遅延を少なくする方法が提供される。少なくとも１つの選択側のキャッシュにより選択可能なメモリの位置からデータが読出される。この方法は、セット選択情報を生成するステップと、セット選択情報を、選択側のキャッシュからメモリ選択情報が届く前にメモリからデータを検索するためにセット選択情報を使用できるようにする位置に格納するステップを含む。
【００１０】
セット連想キャッシュのアクセス遅延を少なくする装置は、セット選択情報を格納する記憶装置、アドレスを受け取り、アドレスによって決定されるＭセットのデータを出力するＭウェイ・セット連想キャッシュ、及びセット選択情報とセット連想アドレスの１つを多重化するマルチプレクサを含み、該セット選択情報は、該セット連想アドレスよりも前に該データのアクセスに使用できる。
【００１１】
セット連想キャッシュの消費電力を少なくする装置は、セット選択情報を格納するセット選択記憶装置、アレイと、アレイにアドレスのセット連想タグ部を出力するディレクトリを含むＭウェイ・セット連想キャッシュ、及び該Ｍセットのデータの１セットを出力するために該ディレクトリからのアドレスの該タグ部と該セット選択情報の１つを多重化するマルチプレクサを含む。
【００１２】
本発明に従って、データ・アドレスを使用してセット連想メモリのアクセスを高速にする方法が提供される。アドレスは、オフセット部、コングルエンス（congruence）・クラス・インデックス、及びタグ部を含む。セット連想メモリはアレイとディレクトリを含む。アレイは、データを格納し、複数のアレイ・コングルエンス・クラスに分けられる。アレイ・コングルエンス・クラスはアレイ・セットに分けられる。アレイ・セットはキャッシュ・ラインを含む。キャッシュ・ラインは複数のデータを含む。ディレクトリは複数のディレクトリ・コングルエンス・クラスに分けられる。ディレクトリ・コングルエンス・クラスは、それぞれディレクトリ・エントリを含むディレクトリ・セットに分けられる。ディレクトリ・エントリは、アドレス・タグと、有効なビット、パリティ等、その他のステータス情報を含む。ディレクトリは、キャッシュ・ラインのそれぞれにアドレス・タグが関連付けられるよう、ディレクトリ・エントリとキャッシュ・ラインに１：１に対応するように分けられる。
【００１３】
この方法は、好適には、コングルエンス・クラス・インデックスを使って、コングルエンス・クラス・インデックスにより指定されるシングル・アレイ・コングルエンス・クラスのセットの内容をアクセスするステップ、コングルエンス・クラス・インデックスを使って、コングルエンス・クラス・インデックスにより指定されるシングル・ディレクトリ・コングルエンス・クラスのセットの内容をアクセスするステップ、セット選択情報を生成するステップ、セット選択情報を利用してアレイ・コングルエンス・クラスのセットを選択するステップ、選択されたセットのキャッシュ・ラインからデータを出力するステップ、タグ部をディレクトリ・コングルエンス・クラスの選択済みセットのアドレス・タグと比較するステップ、選択済みコングルエンス・クラスのアドレス・タグの１つがアドレスのタグ部に等しい場合は選択済みセットをセット選択情報と比較するステップ、アクセスが成功しなかったことと、選択済みコングルエンス・クラスのアドレス・タグがどれもアドレスのタグ部に等しくない場合はキャッシュ・ラインから出力されるデータが無効なことを示す第１制御信号を出力するステップ、及び選択済みセットがセット選択情報に等しくない場合はキャッシュ・ラインからのデータが無効なことを示す第２制御信号を出力するステップを含む。
【００１４】
本発明に従って、データ・アドレスを使用してセット連想メモリのアクセス時間を少なくする装置が提供される。アドレスは、オフセット部、コングルエンス・クラス・インデックス、及びタグ部を含む。セット連想メモリは、アレイとディレクトリを含み、アレイはデータを含む。アレイは、複数のアレイ・コングルエンス・クラスに分けられる。アレイ・コングルエンス・クラスはアレイ・セットに分けられ、アレイ・セットはセット連想メモリのセット連想性を決定する。アレイ・セットはキャッシュ・ラインを含み、キャッシュ・ラインは複数のデータを含む。ディレクトリは複数のディレクトリ・コングルエンス・クラスに分けられる。ディレクトリ・コングルエンス・クラスはディレクトリ・セットに分けられる。ディレクトリ・セットはディレクトリ・エントリを含み、ディレクトリ・エントリはアドレス・タグを含む。ディレクトリは、ディレクトリのアドレス・タグが少なくとも１つのキャッシュ・ラインに関連付けられるよう、ディレクトリ・エントリとキャッシュ・ラインに１：１の対応があるように分けられる。セット連想メモリのアクセス時間を少なくする装置は、コングルエンス・クラス・インデックスにより指定されるコングルエンス・クラスであるシングル・アレイ・コングルエンス・クラスのセットの内容をアクセスする手段、コングルエンス・クラス・インデックスにより指定されるコングルエンス・クラスであるシングル・ディレクトリ・コングルエンス・クラスのセットの内容をアクセスする手段、セット選択情報を生成する手段、セット選択情報を使ってシングル・アレイ・コングルエンス・クラスのセットの１つを選択する手段、選択済みセットのキャッシュ・ラインからデータを出力する手段、アドレスのタグ部を選択済みシングル・ディレクトリ・コングルエンス・クラスのセットのアドレス・タグと比較する手段、アドレス・タグを含むセットをセット選択情報と等しいかどうか比較する手段、及びデータ・アクセスの成功と、キャッシュ・ラインから出力されるデータの有効性を示す制御信号を出力する手段を含む。
【００１５】
【発明の実施の形態】
セット予測により、セット連想キャッシュ・アクセスの遅延選択ステージを待機する必要がなくなる。本発明は、命令キャッシュとデータ・キャッシュのパフォーマンスを上げるために、セット予測のためのセット選択情報を用いる実施例を開示する。
【００１６】
図２は、本発明の実施例のブロック図を示す。セット選択情報２８は、物理タグ付きセット連想キャッシュのディレクトリ・マルチプレクサ１４とアレイ・マルチプレクサ１６に直接送られる。図２の物理アドレス・キャッシュは、図１の仮想アドレス・キャッシュとは対照的に、仮想アドレス１８をキャッシュ・ディレクトリ１０により用いられる物理アドレスに変換する変換索引バッファ（ＴＬＢ）２６を含む。セット選択情報２８をアレイ・マルチプレクサ１６に直接送ると、ディレクトリ・マルチプレクサ１４からアレイ・マルチプレクサ１６にマルチプレクサ選択データを使用できるようになる前にキャッシュ・アレイ１２からデータを検索できる。
【００１７】
本発明の実施例に従って、セット選択情報２８のデータは、ブランチ・ターゲット・バッファＢＴＢ（ブランチ履歴テーブルＢＨＴともいう）、オペランド履歴テーブル、命令キャッシュ等の複数のソースに格納でき、またそれら複数のソースから取り出すことができる。
【００１８】
ＢＴＢは、ブランチ命令のターゲット・アドレスを予測するのに用いられるバッファである。ＢＴＢの理論は、ほとんどのブランチは選択されるかされないかのどちらかであり、選択される場合はターゲット・アドレスが同じになるというものである。従って、選択されるブランチのテーブルが確立され、テーブルの各エントリは、選択されるブランチのアドレスと、これに続くブランチのターゲット・アドレスを含む。テーブルが一杯になると、新しいエントリを追加した場合は、通常はＬＲＵアルゴリズムにより古いエントリが置き換えられる。
【００１９】
図６を参照する。セット選択情報を格納する場所としてのＢＨＴ３０が示してある。命令の実行時、ＢＨＴ３０で、ブランチ・アドレスを使って各ブランチが参照される。ブランチが見つかると、そのターゲット・アドレスがフェッチされ（Ｉフェッチ）、実行ストリームの次の命令になる。ブランチ・アドレスがＢＨＴで見つからないと、それは選択されないとみなされる（ＮＴ）。ブランチ命令の実行が続いてテーブルが更新される。選択が予測されたブランチが選択されない場合、対応するＢＴＢエントリが削除される。選択されないと予測されたブランチが選択される場合は、新しいエントリが確立される。予測されたターゲット・アドレスが不当な場合、訂正されたアドレスが入力される。
ＢＨＴ３０の各エントリは、ブランチのアドレス、対応するブランチ・ターゲット・アドレス、及びセット選択情報を保持する。各ブランチは、プログラム・カウンタにより取り出される命令アドレスでアクセスされる。セット選択情報は、特定のＢＨＴエントリにより示される命令を最後に含んでいたセットを示し、そのＢＨＴエントリに対応するブランチが検出されたときに命令キャッシュからフェッチするセットを予測するために用いられる。フェッチするブランチ・アドレスは、プログラム・カウンタから取り出され、ＢＨＴ３０のブランチ・アドレスと比較される。一致があると、対応するブランチ・ターゲット・アドレスとセット選択情報が命令キャッシュに送られる。従って、ＢＨＴに格納されたセット選択情報から予測されたセットを使用すると、ＴＬＢとキャッシュ・ディレクトリの出力に依存して対応するセットが選択される場合よりも早く、命令キャッシュから対応する命令がフェッチされる。
【００２０】
ＢＨＴからのセット選択情報を適用した本発明の実施例について、図２のブロック図と図３のフロー図を参照して説明する。
プログラム・カウンタから命令フェッチ・アドレス（通常はブランチ命令またはブランチ命令を含むと予測される命令フェッチ・グループに対応するプログラム位置）がブランチ履歴テーブル（ＢＨＴ）にフェッチされる。ＢＨＴはブランチ・ターゲット・アドレスと、命令キャッシュの予測されたブランチ・ターゲットのセットを識別する予測セット・インデックスを送る（ステップ２００）。予測セット・インデックスは図２のセット選択情報２８になる。
ブランチ・ターゲット・アドレスが命令キャッシュにアドレス８で送られる。ターゲット・アドレスは３つの部分に分けることができる。ディレクトリ・タグ、コングルエンス・クラス・インデックス、命令のオフセットである（ステップ２０５）。
並行して、コングルエンス・クラス・インデックスがキャッシュ・ディレクトリ１０とキャッシュ・アレイ１２に送られる。コングルエンス・クラスのディレクトリとアレイのエントリが読出される。ＴＬＢ２６を介してディレクトリ・タグがディレクトリ・マルチプレクサ１４に送られ、セット選択情報２８がディレクトリ・マルチプレクサ１４とアレイ・マルチプレクサ１６に送られる。セット選択情報により、アレイ・マルチプレクサ１６が選択され、対応するアレイ・エントリが出力される（読出されたコングルエンス・クラスのアレイ・エントリのセットから）（ステップ２１０）。
オフセットを利用して、キャッシュ・アレイ１２から出力されるワードを識別し、ワードを命令キュー（またはバッファ）に追加して処理する（ステップ２２０）。
ディレクトリ・マルチプレクサ１４により、セット選択情報２８からのディレクトリ・タグが、ステップ２１０でキャッシュ・ディレクトリ１０から読出されたコングルエンス・クラスのタグ・エントリの１つに一致するかどうかが判定される（ステップ２２５）。
不一致（キャッシュ・ミス）がある場合、ステップ２２０で命令キューに追加されたデータが無効にされる（ステップ２４５）。次のレベルのメモリ階層から命令／データをフェッチする等、ミスが従来どおりに処理される（ステップ２５０）。命令キャッシュ・ラインがキャッシュに設定される（ステップ２５５）。
ＢＨＴが新しい命令キャッシュ・ラインのセットで更新される。予測のソースを更新する手法は、当業者には知られている。好適には、このような更新をこの例で行う場合、予測に使用されたオリジナルのＢＨＴのエントリの座標を記録する（ステップ２６０）。
ステップ２２５でセット選択情報２８からのディレクトリ・タグが、ＴＬＢ２６から送られたタグに一致する場合（キャッシュ・ヒット）でも、以下のような、予測が正しいかどうかの確認が必要である。
変換されたセット・インデックスが生成される。これは、一致するディレクトリ・タグのセットにより識別されるキャッシュ・アレイ１２の命令の変換されたセットを識別する（ステップ２３０）。並行して、変換済みセット・インデックスがアレイ・マルチプレクサ１６とセット予測変換ロジック（図示なし）に送られ、変換済みセット・インデックスを使ってアレイ・マルチプレクサ１６が制御され、対応するアレイ・エントリが選択される（ステップ２１０で読出されたコングルエンス・クラスのアレイ・エントリのセットから）（ステップ２３５）。
予測変換ロジックは、変換済みセット・インデックスがセット選択情報２８からの予測済みセット・インデックスに一致するかどうかを判定する。
一致がある（予測が正しい）場合、変換済みセット・インデックスに対応するエントリが選択されてアレイ・マルチプレクサ１６の動作が無効にされ、ステップ２２０で命令キューに追加されたワードが有効になる（ステップ２４０）。
不一致がある（予測が不当）場合、命令キューに追加されたワードが無効にされる（ステップ２７０）。オフセットを使って、ステップ２４０で識別されたキャッシュ・アレイ１２のワードが識別され、ワードが命令キューに追加され（ステップ２７５）、セット選択情報２８のエントリが更新されて、新しい予測セットが変換済み予測セットに等しいことが示される（ステップ２８０）。
【００２１】
前記の本発明の実施例では、ＢＨＴに、ＢＨＴの全てのバッファまたは位置に接続されたセット予測フィールドが含まれることは、当業者には明らかである。ブランチ・ターゲット（アドレス）にセット選択情報または予測セットを結び付けることで、ＴＬＢ２６、キャッシュ・ディレクトリ１０、ディレクトリ・マルチプレクサ１４による、遅延選択信号の変換またはディレクトリ検索生成を待たずに命令キャッシュからデータを検索できる。
【００２２】
オプションとして、セット選択情報を追加して各ＢＨＴエントリに割当てることができる。追加するセット選択情報により、通過パスつまり選択されないパスに適したセットを指定できる。このような情報は、予測が不当なブランチから復帰するときや、ブランチ命令がキャッシュ・ブロックの最後の位置を占め、通過パスが別のキャッシュ・ブロックに格納されるときに便利である。ターゲット・パスと通過パスが別のキャッシュ・セットにあることが検出されると、両方のセットを命令キャッシュから同時にフェッチできる。また、１つの命令キャッシュ・ライン内に複数のブランチが発生し得るので、ＢＴＢに追加するセット選択情報は、各ブランチ用のフィールドにもなる。
【００２３】
或いは、セット選択情報は、データ・キャッシュのパフォーマンスを上げるために命令キャッシュに格納できる。図７を参照する。データ・キャッシュ・セット選択情報１００を命令キャッシュ・ライン１２０に付加して、命令に必要なオペランドの予測セットを示すことができる。図７に示す通り、Ｄキャッシュ・セット選択情報が、Ｉキャッシュ・ライン１２０の対応する固定部（０乃至８）に関連付けられる。ロード命令かストア命令である命令は、データ・キャッシュ・セット選択情報を使って、ロードまたは格納されるオペランドを含むセットにアクセスする。データ・キャッシュ・セット選択情報は、命令キャッシュのアクセス時、つまりオペランド・アドレスの生成前に使用できるので、この方法によりデータ・キャッシュのパフォーマンスが大幅に向上する。
【００２４】
図９は、従来技術のオペランド履歴テーブル（ＯＨＴ）の動作を示す。プログラム・カウンタ３２によりフェッチされる各命令アドレスは、ＯＨＴ３６の命令アドレスと比較される。一致があると、対応するオペランド・アドレスがフェッチされる。オペランドは次に、プリデコード・オペランド・バッファの命令と比較される。命令がデコードされると、この命令に関連付けられたオペランドが使用でき、すぐに実行を開始できる。
【００２５】
セット選択情報は、本発明の他の実施例に従って、データ・キャッシュのパフォーマンスを上げるためにＯＨＴに格納することもできる。ＯＨＴにより、命令に関連付けられたオペランドをフェッチする時間が短縮される。ＯＨＴは、オペランドを必要とする命令の多くは、命令が実行されるごとに同じオペランド・アドレスを計算するという理論にもとづいている。例えば、ベース・レジスタ、インデックス・レジスタ、及び命令により与えられるディスプレースメント・フィールドを追加することで、オペランド・アドレスを計算できる。各エントリが命令アドレスと、その命令のオペランドのアドレスを含むテーブルを使用すると、命令がデコードされる前でもオペランドをフェッチできる。
【００２６】
図８を参照する。データ・キャッシュ・セット選択情報１４０がＯＨＴ３６の各エントリに付加され、命令がデコードされる前に対応するオペランドのアドレスが使用でき、データ・キャッシュからオペランドをフェッチできるので、データ・キャッシュのアクセス遅延が大幅に短縮される。ＯＨＴへのアクセスに必要なのはプログラム・カウンタだけなので、オペランドのアクセス時間が長くなる等のために必要な場合に、命令をフェッチする前にもオペランドをフェッチできる。
【００２７】
図４は、消費電力を下げるために変更された従来のキャッシュ・ディレクトリ１０とキャッシュ・アレイ１２を含む本発明の実施例を示す。第１と第２の実施例の違いは、アレイ・マルチプレクサ１６がキャッシュ・アレイ１２の前に移動しているため、セット選択情報２８は、キャッシュ・アレイ１２のアクセスに続いて出力されるセットを決定するために使用されるのではなく、キャッシュ・アレイ１２にアクセスする前に使用される。キャッシュ・アレイ１２がセット連想型であることは変わらないが、あるサイクルでキャッシュ・アレイ１２から検索されるセットは１つだけである。従って、アクセスするセット数を少なくすることで消費電力も少なくなる。セット選択情報２８が不当な場合は、ＴＬＢ２６とキャッシュ・ディレクトリ１０からの最後のセット選択情報を使って正しいアレイ情報を選択しアクセスすることができる。
【００２８】
図５は、キャッシュ・アレイ１２とキャッシュ・ディレクトリ１０を含む本発明の実施例を示す。いずれも、消費電力を下げるために変更されている。第２と第３の実施例の違いは、セット選択情報２８は、キャッシュ・ディレクトリ１０のアクセスに続いて出力されるセットを決定するために使用されるのではなく、キャッシュ・ディレクトリ１０にアクセスする前にアクセスするタグのセットを決定するために使用されることである。セット選択情報２８は、キャッシュ・ディレクトリ１０とキャッシュ・アレイ１２の両方から出力されるセットが１つだけになるよう、キャッシュ・ディレクトリ１０のセットとキャッシュ・アレイ１２のセットの両方を選択するために使用される。キャッシュのアクセス時にアクセスする必要のあるキャッシュ・ディレクトリ１０とキャッシュ・アレイ１２のセット数を減らすことで、消費電力が少なくなる。セット選択情報２８が不当な場合、ＴＬＢ２６とキャッシュ・ディレクトリ１０からの遅延選択情報を、正しいアレイ情報を選択し読出すために使用できる。
【００２９】
図１０は、ＣＰＵ４０への本発明の応用を示す。メモリ・システム４２は、ＣＰＵ４０により操作される命令やプログラム・データを含む。メモリ・システム４２は、通常は階層構造であり、メイン・メモリ（ダイナミック・ランダム・アクセス・メモリ）と２次記憶装置（磁気／光ディスク・ドライブ、電気的に消去／プログラム可能な読出し専用メモリ）を含む。
【００３０】
メモリ・システム４２は、頻繁に使用される命令やデータがそれぞれ命令キャッシュ４４やデータ・キャッシュ４６に保持されるように、命令キャッシュ４４、データ・キャッシュ４６とのインタフェースをとる。通常、キャッシュに格納される命令やデータはキャッシュ・ラインつまりブロックに分けられる。命令フェッチ・ユニット４８は、命令キャッシュ４４に格納された命令のブロックをフェッチして命令キュー５０に送る。デコードとディスパッチのユニット５２は、命令キュー５０から命令を読出し、命令をデコードして命令の実行をスケジュールする。スケジューリング方法の詳細については、Hennessy and Patterson Computer Architecture：A Quantitative Approach pp. 2220-362（1990）を参照されたい。条件ブランチ命令は、ブランチ・ユニット５４で実行されるようにスケジュールされ、逐次命令つまり非ブランチ命令は機能ユニット（ＦＵ）５６で実行されるようにスケジュールされる。
【００３１】
ロード／ストア・ユニット５８は、必要に応じてデータ・キャッシュ５６からデータのブロックをフェッチして機能ユニット５６に送る。ロード／ストア・ユニット５８はまた、データ・キャッシュ５６とメモリ・システム４２に格納されたデータのブロックを、機能ユニット５６の命令の実行により生成されるデータ値をもとに更新する。ＣＰＵは、命令を実行するために機能ユニット５６にオペランドを送り、実行結果を受け取るレジスタ・ファイル６０を含む。完了ユニット６２は、ＣＰＵ４０のアーキテクチャにより妥当とみなされる順序で命令の実行を完了する。機能ユニット５６は命令を順不同で実行できるが、ＣＰＵ４０は、アーキテクチャの制約により、命令を同じ順序で完了できる場合とできない場合がある。
【００３２】
ブランチ・ユニット５４は、条件ブランチの結果を評価するための条件レジスタと、機能ユニット５６により実行される操作の結果に応じて条件レジスタを更新するロジックを含む。メモリ・システム４２から命令キュー５０にフェッチされる命令のブロックを識別するアドレスは、命令フェッチ・レジスタ６４に格納される。命令フェッチ・レジスタ６４に格納されるブロック・アドレスはブランチ・ユニット５４に送られる。
【００３３】
各機能ユニット５６は、デコードとディスパッチのユニット５２を経て送られる一部か全てのタイプの命令を実行することができる。機能ユニット５６は、レジスタ・ファイル６０やデータ・キャッシュ・ユニット４６から入力ソース・オペランドを受け取り、出力結果をそれらに書込む。機能ユニット５６は非対称型でもよく、その場合、特定のユニットが命令の一部のみを実行できる。そのとき、レジスタ・ファイル６０は、通常は機能ユニット５６の機能に応じたサブセットに論理的に分けられる。レジスタ・ファイル６０の論理的分割は、アーキテクチャ上見える場合と見えない場合がある。更に、レジスタ・ファイル６０は、論理的に分割されていても、物理的には共通の回路を共有できる。また、デコード／ディスパッチ・ユニット５２は、この非対称性を認識し、命令を適宜スケジュールできなければならない。例えば、機能ユニット５６は、固定小数点演算を行う固定小数点ユニット、浮動小数点演算を行う浮動小数点ユニット、及びソース・ベクトルに対してベクトル演算を行うベクトル・ユニットを追加できる。固定小数点ユニットにより実行される固定小数点演算には、固定小数点加算、固定小数点減算、固定小数点乗算、固定小数点除算、ＡＮＤ、ＯＲ、ＸＯＲ、固定小数点比較、固定小数点回転、固定小数点シフト等がある。浮動小数点ユニットにより実行される浮動小数点演算には、浮動小数点加算、浮動小数点減算、浮動小数点乗算、浮動小数点除算、浮動小数点比較等がある。ベクトル・ユニットにより実行されるベクトル演算の特徴は、固有の高度な並列性にある。通常、このようなベクトル演算は、ＳＩＭＤスタイルの演算であり、命令は、ソース・ベクトル内の複数のデータ要素に対して同じ演算を行う。
【００３４】
ブランチ・ユニット５４は、セット選択情報を含むブランチ予測メカニズムを含む。ブランチ予測メカニズムは、命令のブロックに条件ブランチ命令が含まれないこと、または、選択されないと予測される条件ブランチ命令を含むことを確認してから、マルチプレクサ６６を制御して、次の逐次ブロック・アドレス（次の逐次ブロック・アドレス・ジェネレータ６８により生成される）のセットとブロック・アドレスを命令フェッチ・レジスタ６４にロードする。その場合、次の逐次ブロックはメモリ・システム４２から命令キュー５０にフェッチされる。ブランチ予測メカニズムにより、命令が、選択が予測されるブランチ命令であると判定された場合、マルチプレクサ６６の制御により、ターゲット・アドレスのセットとブロック・アドレスが命令フェッチ・レジスタ６４にロードされる。その場合、最初に予測され選択されるブランチ命令のターゲット命令を含むセットとブロックが、メモリ・システム４２から命令キュー５０にフェッチされる。このプロセスにより、命令キャッシュのアクセス遅延がかなり少なくなり、このプロセスを無制限に継続して、ＣＰＵ４０が現在実行しているブロックよりも更に先にすることができる。ただし、命令バッファのサイズと、ブランチ予測メカニズムによりブランチが不当に予測される可能性が大きくなることから、条件によっては、ブロックのプリフェッチを更に継続しても無益であり、このプロセスが制限されることになる。
【００３５】
ブロック内で選択が予測される条件ブランチ命令を２つ以上にできることは明らかである。最初に予測され選択される条件ブランチ命令をブランチ予測メカニズムで識別する場合、ターゲット命令のバイト・アドレスを、命令フェッチ・レジスタ６４に格納できるが、それでも、命令のブロックをフェッチする際にメモリ・システム４２により使用されることはない。その場合、バイト・アドレスはブランチ予測メカニズムに送られ、ブロックのターゲット命令のエントリ・ポイントが示される。ブランチ予測メカニズムは、ターゲットのバイト・アドレスを利用して、送られたエントリ・ポイントの後のシーケンスで発生する、最初に選択が予測された条件ブランチ命令が識別される。
【００３６】
ブランチ予測メカニズムは、ＢＴＢ、ＯＨＴ、命令キャッシュ、デコード履歴テーブル等に格納されるデータからセット選択情報を引き出すことができる。ブランチ予測方法の詳細については、以下に示す文献等を参照されたい。
１．Sussenguthによる米国特許第３５５９１８３号
２．Losqらによる米国特許第４４７７８７２号
３．J. SmithによるA Study of Branch Prediction Strategies 24th Annual Symposium on Computer Architecture pp. 135-148（May 1998）
４．Yeh、PattによるA Comparison of Dynamic Branch Predictors that Two Levels of Branchi History Conference Proceedings-Annual Symposium on Computer Architecture pp. 257-266（1993）
５．P. Emma、J. Pomerene、T. Puzak、R. Rechtschaffen、F. SparacioによるOperand History Table 、IBM Technical Disclosure Bulletin 12-84、p. 3815-3816
６．Emma、J. Knight、J. Pomerene、T. Puzak、R. RechtschaffenによるHedge Fetch History Table、IBM Technical Disclosure Bulletin 02-89、p. 101-102７．Simon Stely Jr. らによる米国特許第５２３５６９７号
８．L. Liuによる米国特許第５４１８９２２号
９．L. LiuによるPartial address directory for cache access、IEEE Transactions on Very Large Scale Integration （VLSI）Systems、2（2）、June 1994、pp. 226-240
（Liuは、ＳＥＴＬＡＴという固定テーブルを用いる。ＳＥＴＬＡＴは、ロード・アドレスの一部を使ってインデックスが付けられ、連想キャッシュからのデータ検索が高速化される。ＳＥＴＬＡＴは変換を必要とせず、従来のディレクトリよりも狭いので、コングルエンス・クラスからのセットの選択を高速にすることができる。Liuの発明は、仮想アドレス変換結果をキャッシュするためにも使用でき、サイクル当たり複数のキャッシュ・アクセスを可能にしている。）
１０．A. Agarwal、S. PudarによるColumn-Associative Caches：A Technique for Reducing the Miss Rate of Direct-Mapped Caches、The 20th Annual International Symposium on Computer Architecture（1993）pp. 179-190（AgarwalとPudarは、直接マップ・キャッシュを、第２ハッシングを使って２ウェイ・セット連想キャッシュのように実行する方法を開示している。この方法により、セットの最短時間未使用（ＭＲＵ）要素へのアクセスを高速にしている。）
１１．B. Calder、D. Grunwald、J. Emerによる"Predictive sequential associative cache"、IEEE High-Performance Computer Architecture Symposium Proceedings 1996、pp. 244-253
（Calderらは、AgarwalとPudarによる文献をもとに、毎回異なるハッシュ・プローブで直接マップ・キャッシュを複数回アクセスするのに適したキャッシュ・ハッシュ・プローブを選択するための、予測方法の使用方法について述べている。）
【００３７】
再び図１０を参照する。プロセッサ・ユニット４０には、命令やデータを、プロセッサ・ユニット４０から要求される前にキャッシュ・メモリ４４、４６にプリフェッチするハードウェア・メカニズムを追加できる。例えば、プロセッサ・ユニット４０には、Jouppiによる"Improving Direct-mapped Cache Performanceby the Addition of a Small Fuly-Associative Cache and Pre-fetch buffers- Proc. Of 17th annual Int"l Symposium on Computer Architecture"、 Seattle、 May、 1990、 IEEE Computer Society Press、 pp. 364-374、及びPalacharlaらによる"Evaluating Streaming Buffers as a Secondary Cache Replacement - Proc. of 21st Annual Int"l Symposium on Computer Architecture"、 Chicago、 April、 1994、 IEEE Computer Society Press、 pp. 24-33に述べられているプリフェッチ・ストリーム・バッファを追加できる。
【００３８】
また、プリフェッチ命令（つまり、命令やデータをキャッシュ・メモリ４４、４６に、プロセッサ・ユニット４０により要求される前にフェッチする命令）は、メモリ・システム４２に格納された命令のシーケンスに挿入できる。Callahanらによる"Software Prefetch Proceedings of the Fourth International Conference on Architectural Support For Programming Languages and Operating Systems"、 April 1991は、命令セットのプリフェッチを行う新しい命令の追加を開示している。IBM、Motorola、Appleが共同開発したPowerPCプロセッサでは、一般にはタッチ命令と呼ばれるデータ・キャッシュ・ブロック・タッチ（ｄｃｂｔ）命令により、メモリのブロックがキャッシュにフェッチされる。また、P. Dubeyによる米国特許第５７７４６８５号（米国特許出願第０８／４２６５０２号）は、投機的タッチ命令について説明している。
【００３９】
これらのプリフェッチ命令は、命令とデータ（オペランド）の両方をキャッシュ・メモリ４４、４６にプリフェッチするのに使用できる。一般に、これらのプリフェッチ命令は、データをプロセッサ・ユニット４０に転送されないことを除いて、ロード命令と同じように動作する。具体的には、プロセッサ・ユニット４０は、プリフェッチ・アドレスでキャッシュ・ディレクトリを検索し、ミスがあった場合はメモリ・システム４２からキャッシュ・メモリ４４、４６に情報を転送するメカニズムを含む。このようなプリフェッチ命令は、コンパイラにより、情報が必要なときにキャッシュで使用できるようにするときに、情報を実際に使用する前に、命令のシーケンスに挿入できる。しかし、コンパイラは、どのような場合でもキャッシュ・ミスを避けるために、プリフェッチ命令を挿入できない場合がある。例えば、プリフェッチ・アドレスは、そのデータを使用する命令が実行されるまで不明なままかもしれない。オペランドを直接参照するロード命令を考えてみる。つまり、レジスタがメモリに格納されたポインタをロードする。その場合、プリフェッチ・アドレスは、データを識別するポインタがロードされるまでは不明なままである。
【００４０】
ほかの場合、プリフェッチ命令により、プリフェッチ命令がデータの実際の使用箇所に近すぎる場合は、パフォーマンスが上がる可能性はほとんどない。例えば、プリフェッチ命令を、それがフェッチする情報が実際に使用されるところよりも１命令分だけ前に設定すれば、プリフェッチ命令を全く挿入しない場合に比べてパフォーマンスが上がることはほとんどない。従って、場合によっては無用なプリフェッチ命令は、無視する方が有益なケースがある。プリフェッチ命令を選択的に実行するメカニズムの例については、T. Puzakによる米国特許出願第０８／５９９８３３号を参照されたい。
【００４１】
プロセッサ・ユニット４０は、命令やデータをプリフェッチするほか、プリフェッチ命令を投機的に実行することもできる。このような命令が"投機的命令"と呼ばれるのは、推測が間違っている場合には、命令の実行結果が有用ではない可能性があるからである。プロセッサ・ユニット４０は、好適には、ブランチ予測により、命令を投機的に実行するパスを識別する。この点、ブランチ・ユニット５４は、予測の妥当性を、条件ブランチ命令の変換をもとに評価する。ある予測が妥当（つまり投機が妥当）と判断された場合、妥当な予測に左右される投機的命令の実行結果は永続的にされる。ただし、ある予測が無効（つまり投機が無効）と判断された場合は、無効な予測に左右される投機的命令は棄却され、プロセッサ・ユニット４０のステージによるその投機的命令の処理を終了することができる。投機的命令は、好適には、命令キュー５０でそのようにマークされる。
【００４２】
また、プロセッサ・ユニット４０の様々なステージ（ブランチ・ユニット５４、デコード／ディスパッチ・ユニット５２、ロード／ストア・ユニット５８、機能ユニット５６）は、好適には、そのステージにより実行されている投機的命令を識別する情報を格納する。また、完了ユニット６２は、好適には、そのような投機的命令の実行結果を投機的とマークする。ある投機が妥当と判断されると、ブランチ・ユニット５４は、完了ユニット６２と協力して、妥当な予測に依存する投機的命令の実行結果を永続的とマークし、これにより完了ユニット６２はその命令の実行を完了することができる（つまり、実行結果をレジスタ・ファイル６０やメモリ・システム４２に書込む）。一方、ある予測が無効と判断された場合、ブランチ・ユニット５４は、好適には次のように動作する。ブランチ・ユニット５４は、命令フェッチ・ユニット４８と協力して、無効な予測に依存し、命令キュー５０に残る投機的命令を棄却する。ブランチ・ユニット５４は、完了ユニット６２と協力して、無効な予測に依存する投機的命令の実行結果を棄却し、よって完了ユニット６２はその命令を完了できない。ブランチ・ユニット５４は、プロセッサ・ユニット４０の様々なステージと協力して、無効な予測に依存する投機的命令の処理を終了する。
【００４３】
セット予測情報の使用例を図１１及び図１２に示す。図１１及び図１２は、パイプライン処理の多いキャッシュのタイミング図である。図１１は、セット予測を行わずにパイプライン処理を行う従来の方法、図１２は、本発明に従ってセット予測を行う方法を示す。図１１の従来の方法では、キャッシュ・アクセスとアレイの読出しが、時間期間０と１の間に起こることがわかる。ほぼ同じ時間に、仮想アドレス変換（Ｖ→Ｒ）、ディレクトリの読出し、及びタグ・チェックがデータＡに対して実行される。遅延選択（セットにインデックスが付けられ変換される）の後、時間期間２でデータＡが使用できる。本発明の方法によると（図１２）、データＡは、時間期間"１"でアレイ読出しの後、期間"２"で遅延選択が実行される前に使用できる。データ"Ａ"は次に、時間期間"２"で有効なデータであることが確認される。
【００４４】
セット予測が不当な場合、キャッシュ・アクセス、アレイ読出し、及びデータが使用できる各ステップを２回目に（期間"３"で）実行する必要がある。データＡは時間４まで使用できない。データ"Ｂ"、"Ｃ"は有効なデータであり得る。それらが使用できるのは、データ"Ａ"が再び有効になる前である。
【００４５】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４６】
（１）少なくとも１つの選択キャッシュにより選択できるデータ選択情報をもとに、メモリの位置からデータを読出すことができるセット連想キャッシュを持つメモリの、アクセス遅延を少なくする方法であって、
セット選択情報を生成するステップと、
複数の位置のうち少なくとも１つに前記セット選択情報を格納するステップと、
前記セット選択情報を送信、使用して、前記少なくとも１つの選択キャッシュにより前記データ選択情報が届いたことを確認する前に前記メモリから前記データを検索するステップと、
を含む、方法。
（２）複数の位置のうち前記１つはブランチ・ターゲット・バッファであり、アクセスされるメモリは命令キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（１）記載の方法。
（３）ブランチ・ターゲット・バッファにセット選択情報を格納する前記ステップは、通過するパスのセットを予測する２次セット選択情報を前記ブランチ・ターゲット・バッファに格納するステップを含む、セット連想キャッシュのアクセス遅延を少なくする、前記（２）記載の方法。
（４）ブランチ・ターゲット・バッファにセット選択情報を格納する前記ステップは、選択されないパスのセットを予測する２次セット選択情報を前記ブランチ・ターゲット・バッファに格納するステップを含む、セット連想キャッシュのアクセス遅延を少なくする、前記（２）記載の方法。
（５）複数の位置のうち前記１つは命令キャッシュにあり、アクセスされるメモリはデータ・キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（１）記載の方法。
（６）複数の位置のうち前記１つはオペランド履歴テーブルであり、アクセスされるメモリ・キャッシュはデータ・キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（１）記載の方法。
（７）前記セット選択情報を前記データ選択情報と比較するステップと、
前記比較により不一致を確認した場合に前記セット選択情報を更新して無効なデータを示すステップと、
次のレベルのメモリ階層から命令またはデータをフェッチするステップと、
を含む、前記（１）記載の方法。
（８）セット連想キャッシュのアクセス遅延を少なくする装置であって、
ａ）セット選択情報を格納する記憶装置と、
ｂ）アドレスを受け取り、該アドレスにより決定されるＭセットのデータを出力するＭウェイ・セット連想キャッシュと、
ｃ）セット選択情報と、該セット選択情報よりも先に前記データのアクセスに使用できないセット連想アドレスの１つを多重化するマルチプレクサと、
を含む、装置。
（９）前記セット選択情報はブランチ・ターゲット・バッファに格納されるかそこから検索され、前記Ｍウェイ・セット連想キャッシュは命令キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（８）記載の装置。
（１０）前記セット選択情報は命令キャッシュに格納されるかそこから検索され、前記Ｍウェイ・セット連想キャッシュはデータ・キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（８）記載の装置。
（１１）前記セット選択情報はオペランド履歴テーブルに格納されるかそこから検索され、前記Ｍウェイ・セット連想キャッシュはデータ・キャッシュである、セット連想キャッシュのアクセス遅延を少なくする、前記（８）記載の装置。
（１２）セット連想キャッシュの消費電力を少なくする装置であって、
ａ）セット選択情報を格納するセット選択記憶装置と、
ｂ）アレイと、該アレイにアドレスのセット連想タグ部を出力するディレクトリを含むＭウェイ・セット連想キャッシュと、
ｃ）前記ディレクトリと前記セット選択情報からのアドレスの前記タグ部の１つを多重化して前記Ｍセットのデータのうち１セットを出力するマルチプレクサと、
を含む、装置。
（１３）前記Ｍウェイ・セット連想キャッシュは命令キャッシュである、セット連想キャッシュの消費電力を少なくする、前記（１２）記載の装置。
（１４）前記セット選択情報はブランチ・ターゲット・バッファに格納されるかそこからフェッチされる、セット連想キャッシュの消費電力を少なくする、前記（１３）記載の装置。
（１５）前記Ｍウェイ・セット連想キャッシュはデータ・キャッシュである、セット連想キャッシュの消費電力を少なくする、前記（１２）記載の装置。
（１６）前記セット選択情報はオペランド履歴テーブルに格納されるかそこからフェッチされる、セット連想キャッシュの消費電力を少なくする、前記（１２）記載の装置。
（１７）前記セット選択情報は命令キャッシュに格納されるかそこからフェッチされる、セット連想キャッシュの消費電力を少なくする、前記（１２）記載の装置。
（１８）データ・アドレスを使用したセット連想メモリのアクセスを高速にする方法であって、該アドレスはそれぞれオフセット部、コングルエンス・クラス・インデックス、タグ部を含み、該セット連想メモリはアレイとディレクトリを含み、該アレイはデータを格納し、複数のアレイ・コングルエンス・クラスに分けられ、該アレイ・コングルエンス・クラスはアレイ・セットに分けられ、該アレイ・セットはデータを持つキャッシュ・ラインを含み、該ディレクトリは複数のディレクトリ・コングルエンス・クラスに分けられ、該ディレクトリ・コングルエンス・クラスはディレクトリ・セットに分けられ、該ディレクトリ・セットはディレクトリ・エントリを含み、該ディレクトリ・エントリはアドレス・タグを含み、該ディレクトリは、該アドレス・タグが該キャッシュ・ラインのうち少なくとも１つと関連付けられるよう、該ディレクトリ・エントリと該キャッシュ・ラインが１：１で対応するように分けられ、且つ、
前記コングルエンス・クラス・インデックスを使用して、前記コングルエンス・クラス・インデックスにより指定されるシングル・アレイ・コングルエンス・クラスのセットの内容をアクセスするステップと、
前記コングルエンス・クラス・インデックスを使用して、前記コングルエンス・クラス・インデックスにより指定されるシングル・ディレクトリ・コングルエンス・クラスのセットの内容をアクセスするステップと、
セット選択情報を生成するステップと、
前記セット選択情報を利用して、前記アレイ・コングルエンス・クラスの前記セットを、前記ディレクトリにより指定される前記シングル・コングルエンス・クラスの出力よりも前に選択するステップと、
前記セット選択情報をもとに前記選択済みセットの前記キャッシュ・ラインから前記データを出力するステップと、
を含む、方法。
（１９）前記タグ部を前記ディレクトリ・コングルエンス・クラスの前記選択済みセットの前記アドレス・タグと比較するステップと、
前記選択済みコングルエンス・クラスの前記アドレス・タグの１つが前記アドレスの前記タグ部に等しい場合は、前記選択済みセットを前記セット選択情報と比較するステップと、
前記選択済みコングルエンス・クラスの前記アドレス・タグがどれも前記アドレスの前記タグ部に等しくない場合は、第１制御信号を出力して、前記アクセスが不成功だったことと、前記キャッシュ・ラインから出力された前記データが無効なことを示し、前記選択済みセットが前記セット選択情報に等しくない場合は、第２制御信号を出力して、前記キャッシュ・ラインからの前記データが無効なことを示すステップと、
を含む、前記（１８）記載の方法。
（２０）前記アドレスは第１パーティションと第２パーティションを含み、該第１パーティションはアレイ・オフセット部、アレイ・コングルエンス・クラス・インデックス、アレイ・タグ部を含み、該第２パーティションはディレクトリ部、ディレクトリ・コングルエンス・クラス・インデックス、ディレクトリ・タグ部を含み、該アレイ・コングルエンス・クラス・インデックスと該ディレクトリ・コングルエンス・クラス・インデックスは長さが可変であり、前記アレイと前記ディレクトリは異なるセット連想性を含む、前記（１８）記載の方法。
（２１）前記オフセット部を利用して、前記キャッシュ・ラインから出力するデータを選択するステップを含む、前記（２０）記載の方法。
（２２）予測されたセット以外のセットに、前記アレイ・タグ部に一致するアドレス・タグがある場合は、前記選択済みセットの前記キャッシュ・ラインからデータを出力するステップを含む、前記（１８）記載の方法。
（２３）予測されたセット以外のセットに、前記ディレクトリ・タグ部に一致する前記アドレス・タグがある場合は、前記選択済みセットの前記キャッシュ・ラインからデータを出力するステップを含む、前記（２０）記載の方法。
（２４）前記セット選択情報はブランチ・ターゲット・バッファにより提供される、前記（１８）記載の方法。
（２５）命令アクセス用の前記セット選択情報はブランチ・ターゲット・バッファにより提供される、前記（２０）記載の方法。
（２６）オペランド・アクセス用の前記セット選択情報は従来の命令アクセスにより提供される、前記（１８）記載の方法。
（２７）オペランド・アクセス用の前記セット選択情報は従来の命令アクセスにより提供される、前記（２０）記載の方法。
（２８）オペランド・アクセス用の前記セット選択情報はオペランド履歴テーブルにより提供される、前記（１８）記載の方法。
（２９）オペランド・アクセス用の前記セット選択情報はオペランド履歴テーブルにより提供される、前記（２０）記載の方法。
【図面の簡単な説明】
【図１】従来技術の仮想タグ付きキャッシュを示す図である。
【図２】物理タグ付きセット連想キャッシュに本発明を応用した図である。
【図３】本発明に従った方法の用途を示す代表的なフロー図である。
【図４】本発明の第２実施例の図である。
【図５】本発明の第３実施例の図である。
【図６】本発明のセット選択情報の記憶域としてのブランチ履歴テーブルを示す図である。
【図７】本発明のセット選択情報の記憶域としての命令キャッシュを示す図である。
【図８】本発明のセット選択情報の記憶域としてのオペランド履歴テーブルを示す図である。
【図９】従来技術のオペランド履歴テーブルの動作を示す図である。
【図１０】本発明を中央処理装置に応用した図である。
【図１１】従来技術の方法を使用したキャッシュ・アクセスのタイミング図である。
【図１２】本発明の方法を使用したキャッシュ・アクセスのタイミング図である。
【符号の説明】
１０  キャッシュ・ディレクトリ
１２  キャッシュ・アレイ
１４  ディレクトリ・マルチプレクサ
１６  アレイ・マルチプレクサ
１８  アドレス
２６  変換索引バッファ（ＴＬＢ）
２８  セット選択情報
３０  ＢＨＴ
３２  プログラム・カウンタ
３６  ＯＨＴ
４０  プロセッサ・ユニット
４２  メモリ・システム
４４、４６  キャッシュ・メモリ
５０  命令キュー
５２  デコード／ディスパッチ・ユニット
５４  ブランチ・ユニット
５６  機能ユニット（ＦＵ）
５８  ロード／ストア・ユニット
６０  レジスタ・ファイル
６２  完了ユニット
６４  命令フェッチ・レジスタ
６６  マルチプレクサ
【図１】
0003542021.tif 000002
【図２】
0003542021.tif 000003
【図３】
0003542021.tif 000004
【図４】
0003542021.tif 000005
【図５】
0003542021.tif 000006
【図６】
0003542021.tif 000007
【図７】
0003542021.tif 000008
【図８】
0003542021.tif 000009
【図９】
0003542021.tif 000010
【図１０】
0003542021.tif 000011
【図１１】
0003542021.tif 000012
【図１２】
0003542021.tif 000013