(57)【要約】装置及びシステムは、プロセッサに結合されたキャッシュ制御回路と、キャッシュ制御回路に結合された独立してアクセス可能な複数のメモリバンク（２２８）とより成る。一部のバンクは非均等な待ち時間を有し、２またはそれ以上の展開バンクセット（２４６）に編成されている。選択されたバンクが他のバンクよりもキャッシュ制御回路及び／またはプロセッサに近いところにあるが、この方法は、バンク内のデータにアクセスし、第１のデータ（４４５）が第２のデータよりより頻繁にアクセスされると判定されると第１のデータをさらに別のバンクから、近いバンクへ移行させるステップを含み、第２のデータはその別のバンク（４５１）へ移行される。
2005522773.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュ制御回路と、
展開バンクセットとして編成され、キャッシュ制御回路に結合された独立にアクセス可能な複数のメモリバンクとより成り、独立にアクセス可能な複数のメモリバンクのうちの少なくとも４つのバンクは非均等な待ち時間を有する装置。
【請求項２】
複数のキャッシュラインは、独立してアクセス可能な複数のメモリバンクのうちの少なくとも１つに静的マッピングされる請求項１の装置。
【請求項３】
独立してアクセス可能な複数のメモリバンクはそれぞれ専用チャンネルを用いてキャッシュ制御回路に結合される請求項１の装置。
【請求項４】
キャッシュ制御回路は、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクがキャッシュ制御回路からの第１のリクエストの処理を完了するまでは、独立してアクセス可能な複数のメモリバンクのうちの選択した１つのバンクに第２のリクエストを送ることができない請求項１の装置。
【請求項５】
独立してアクセス可能な複数のメモリバンクは側部を有するアレイとして形成され、キャッシュ制御回路はほぼその側部に位置する請求項１の装置。
【請求項６】
独立してアクセス可能な複数のメモリバンクのうちの選択したバンクはセットアソシアティブバンクである請求項１の装置。
【請求項７】
独立してアクセス可能な複数のメモリバンクはそれぞれ切換型ネットワークを用いてキャッシュ制御回路に結合される請求項１の装置。
【請求項８】
切換型ネットワークは切換型二次元メッシュネットワークである請求項７の装置。
【請求項９】
切換型ネットワークに含まれる複数のポイント間リンクのうちの選択されたリンクは双方向性ルーティング手段を用いて接続される請求項７の装置。
【請求項１０】
切換型ネットワークに含まれる複数のポイント間リンクのうちの選択されたリンクは単方向性ルーティング手段を用いて接続される請求項７の装置
【請求項１１】
切換型ネットワークは複数のルーターを含み、複数のルーターのうちの選択されたルーターは独立してアクセス可能な複数のメモリバンクの選択された交差点に位置する請求項１０の装置。
【請求項１２】
複数のルーターはアドレスのルーティングを行う請求項１５の装置。
【請求項１３】
複数のルーターは読出しデータのルーティングを行う請求項１０の装置。
【請求項１４】
複数のルーターは書込みデータのルーティングを行う請求項１５の装置。
【請求項１５】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクはタグアレイを含む請求項１０の装置。
【請求項１６】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクはリクエストバッファを含む請求項１０の装置。
【請求項１７】
キャッシュ制御回路に結合されたリクエストバッファをさらに備え、キャッシュ制御回路から独立してアクセス可能な複数のメモリバンクへのリクエストが競合すると、そのリクエストはリクエストバッファに保存される請求項１０の装置。
【請求項１８】
切換型ネットワークは非同期ネットワークである請求項１０の装置。
【請求項１９】
複数のキャッシュラインは、独立してアクセス可能なメモリバンクのうちの少なくとも２つに動的マッピングできる請求項１の装置。
【請求項２０】
キャッシュ制御回路に結合された分散タグ記憶装置をさらに備えた請求項１９の装置。
【請求項２１】
キャッシュ制御回路に結合された集中型パーシャルタグ記憶装置をさらに備えた請求項２０の装置。
【請求項２２】
タグを独立してアクセス可能な複数のメモリバンクにそれぞれ同報するためにキャッシュ制御回路に結合された同報モジュールをさらに備えた請求項２１の装置。
【請求項２３】
独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成される請求項１の装置。
【請求項２４】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは、キャッシュ制御回路に結合されたプロセッサに、独立してアクセス可能な複数のメモリバンクのうちの別の選択されたバンクより近い請求項２３の装置。
【請求項２５】
選択されたバンク及びそれ以外の選択されたバンクは共に少なくとも２つの展開バンクセットのうちの選択されたセットに位置する請求項２４の装置。
【請求項２６】
少なくとも２つの展開バンクセットのうちの１つの各バンクは、少なくとも２つの展開バンクセットのうちの１つの２以上のアソシアティブウェイを保持する請求項２３の装置。
【請求項２７】
少なくとも２つの展開バンクセットのうちの１つは少なくとも２つのメモリバンクを含み、少なくとも２つのメモリバンクの少なくとも１つのアソシアティブウェイは少なくとも２つのメモリバンクのうちの別の１つの別のアソシアティブウェイとは異なるアクセス待ち時間を有する請求項２６の装置。
【請求項２８】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのサブセットを少なくとも２つの展開バンクセットのうちのそれぞれにマッピングすることにより、少なくとも１つの展開バンクセットに編成される請求項２３の装置。
【請求項２９】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのうちの第１群のバンクを少なくとも２つの展開バンクセットのうちの１つにマッピングし、また、独立してアクセス可能な複数のメモリバンクのうちの第２群のバンクを少なくとも２つの展開バンクセットの別のセットにマッピングすることにより、少なくとも２つの展開バンクセットに編成される請求項２８の装置。
【請求項３０】
独立してアクセス可能な複数のメモリバンクのうちの第１群のバンクは第１のカラムを構成し、独立してアクセス可能な複数のメモリバンクのうちの第２群のバンクは第２のカラムを構成する請求項２９の装置。
【請求項３１】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクをフェアマッピングすることにより、少なくとも２つの展開バンクセットに編成される請求項２９の装置。
【請求項３２】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクを高速共有マッピングすることにより、少なくとも１つの展開バンクセットに編成される請求項２９の装置。
【請求項３３】
独立してアクセス可能な複数のメモリバンクは、ｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリに編成されており、各展開バンクセットは独立してアクセス可能な複数のメモリバンクから選択されたメモリバンクのサブセットを含み、少なくともｎウェイのうちの少なくとも２つのウェイは異なるアクセス待ち時間を有する請求項１の装置。
【請求項３４】
ｎウェイのうちの各ウェイは異なるアクセス時間を有する請求項３３の装置。
【請求項３５】
算術機能ユニットと、
算術論理ユニットに結合されたキャッシュ制御回路と、
キャッシュ制御に結合された、独立してアクセス可能な複数のメモリバンクとより成り、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つのバンクは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成されるプロセッサ。
【請求項３６】
キャッシュ制御回路と、キャッシュ制御回路に結合され独立してアクセス可能な複数のメモリバンクとを有するプロセッサより成り、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成され、プロセッサに作動的に結合されたバスと、バスに作動的に結合されたランダムアクセスメモリとをさらに含むシステム。
【請求項３７】
概説し図１Ａに示す装置。
【請求項３８】
概説し図２に示す装置。
【請求項３９】
概説し図３Ａ、３Ｂ及び３Ｃに示す装置。
【請求項４０】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１のデータ及び第２のデータにアクセスするステップを含み、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成されており、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクは独立してアクセス可能な複数のバンクのうちの他の選択されたバンクよりプロセッサに近く、
所定の基準が満足されたと判定されると、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクへ独立してアクセス可能な複数のメモリバンクのうちの他の選択されたバンクから第１のデータを移行させるステップをさらに含む方法。
【請求項４１】
所定の基準は、第１のデータが第２のデータより頻繁にアクセスされると判定されると満足される請求項４０の方法。
【請求項４２】
所定の基準が満足されたと判定されると、第２のデータを独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクから独立してアクセス可能な複数のメモリバンクのうちの他の選択されたバンクへ移行させるステップを含む請求項４１の方法。
【請求項４３】
独立してアクセス可能な複数のメモリバンクはｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリに編成されており、各展開バンクセットは独立してアクセス可能な複数のメモリバンクから選択された少なくとも２つのメモリバンクを含む請求項４０の方法。
【請求項４４】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１のデータ及び第２のデータにアクセスするステップを含み、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも複数の展開バンクセットに編成されており、独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは独立してアクセス可能な複数のバンクのうちの他の選択されたバンクよりプロセッサに近く、
第１のデータが第２のデータより頻繁にアクセスされると判定されると、独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップを含む方法。
【請求項４５】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
マルチキャストサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４６】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
限定マルチキャストサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４７】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
インクリメンタルサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４８】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、  
区分マルチキャスト方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４９】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
マルチキャスト方式、限定マルチキャスト、インクリメンタルサーチ方式及び区分マルチキャストサーチ方式を含む群から選択された方式を組み合わせてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項５０】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
ＬＲＵビット方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを追出すステップを含む請求項４４の方法。
【請求項５１】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
世代昇進方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを移動させるステップを含む請求項４４の方法。
【請求項５２】
世代昇進方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを移動させるステップは、
世代昇進方式の昇進距離を選択し、
世代昇進方式の昇進トリガを選択するステップを含む請求項５１の方法。
【請求項５３】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
第１のデータをより近いメモリバンクに位置する別のデータとスワッピングするステップを含む請求項４４の方法。
【請求項５４】
中央タグ記憶装置にアクセスすることによりビクティムバンクを選択するステップを含む請求項４４の方法。
【請求項５５】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
独立してアクセス可能な複数のメモリバンクに含まれる分散タグにアクセスするステップを含む請求項４４の方法。
【請求項５６】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
中央タグ記憶装置内のパーシャルタグにアクセスし、独立してアクセス可能な複数のメモリバンクに含まれる分散タグにアクセスするステップを含む請求項４４の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施例は、一般的に、コンピュータシステムにおいてキャッシュメモリを実現する装置、システム及び方法に係り、さらに詳細には、アクセス可能な複数のバンクを有するキャッシュメモリを用いる装置、システム及び方法に係る。
【背景技術】
【０００２】
コンピュータシステムの主記憶装置のアクセスに用いるキャッシュは個別階層レベルへの編成が可能である。通常、各レベルは包含関係に従い、その上方の小さなレベルの内容を複製して階層構造の低レベルのアクセス回数を減らそうとする。メモリアクセスのバンド幅需要が大きくなり、技術が可能にする回路素子のサイズがさらに減少するにつれて、オンチップ型キャッシュメモリのサイズが増加すると予想される。
【０００３】
単一レベルのキャッシュは伝統的に均等なアクセス時間を有する。この均等型キャッシュアーキテクチャ（ＵＣＡ）は、アクセス時間を減少するために多数のサブバンクに分割することができる。信号をサブバンクのローカルデコーダに送るために、中央プリレコーダを用いることが多い。データを各サブバンクでアクセスし、リクエストされたラインを集めてキャッシュコントローラへ駆動するマルチプレクサを通過させた後、出力ドライバに戻すことができる。キャッシュサイズを増加すると、キャッシュ全体のグローバルワイヤ遅延にもよるが、データアクセス時間が増加する。かかる遅延は、バンクへの、またバンクからのルーティングタイムによるデータアクセス時間をさらに大きくする。従って、たとえ最適なサブバンク構成を使用しても、相対的にワイヤ遅延が大きいプロセスでは最も遅いサブバンクからのラインの一部の受信が停止されるため、このタイプの大型キャッシュの性能には問題がある。
【０００４】
別の問題として、必要とされるバンクが異なるリクエストの処理に追われているためリクエストがストールすると生じるバンクの競合、及びバンクはフリーであるがそのルーティングパスが使用中の時に起こるチャンネルの競合を含む競合の問題がある。ＵＣＡキャッシュでは、ポートの競合による待ち時間は実質的なロスを生ぜしめるほど十分に大きい。マルチポートセルでは大型キャッシュのアクセスオーバーラップの問題をうまく解決できないが、その理由は面積の増加によりロードアクセス時間が有意に増加するためであろう。これが、場合によっては、デュアルポートキャッシュがシングルポート方式ほど性能がよくない理由である。
【０００５】
従って、独立してアクセス可能なキャッシュメモリバンクを高効率で利用する装置、システム、製品及び方法が求められている。また、キャッシュ環境における競合を減少させる装置、システム、製品及び方法が求められている。
【発明の概要】
【０００６】
本発明の装置またはシステムは、キャッシュ制御回路と、キャッシュ制御回路に結合された独立してアクセス可能な複数のメモリバンクとより成る。一部のバンクは非均等な待ち時間を有し、２またはそれ以上の展開バンクセットに編成される。本発明の方法は、選択されたバンクが他のバンクに比べてキャッシュコントローラ及び／またはプロセッサにより近いバンク内のデータにアクセスし、第１のデータが第２のデータに比べてより頻繁にアクセスされ、さらに別のバンクに移行される可能性があると判定されると、第１のデータをそのさらに別のバンクからより近いバンクへ移行させるステップを含む。
【実施例】
【０００７】
本発明の種々の実施例の以下の詳細な説明において、本願の一部である添付図面を参照する。これらの図面において、本発明の特定の実施例は限定のためでなく例示のために図示されている。図面において、同様な番号はいくつかの図を通して実質的に同じコンポーネントを指示するものであり。これらの実施例は、当業者が本発明を実施できるように十分に詳しく記載されており、他の実施例もそれらから想到可能であって、本発明の範囲から逸脱することなく、構造的及び論理的な変形又は設計変更を行うことができる。従って、以下の詳細な説明は限定的に捉えるべきではなく、本発明の範囲は頭書の請求項及びそれらが享受する均等物の全幅のみにより規定されるべきものである。
【０００８】
相対的にワイヤ遅延が大きいキャッシュでは最悪の均等アクセスにより性能が低下することがある。しかしながら、マルチバンク型構成は、アクセスすべきデータが特定の態様で配置されている場合、例えば、キャッシュコントローラ及び／またはプロセッサからの各バンクの距離に恐らく比例する非均等な（即ち、異なる）速度で種々のバンクがアクセスされる場合はその性能低下を緩和することができる。一部の実施例において、各バンクは独立してアドレス可能であり、局所的に最適な物理的サブバンクを構成するようにサイズそして／または区分を決められている。バンク及びサブバンクの数及び物理的構成は、設計空間を体系的に探索して全体性能を最大にするように選択することが可能である。データはバンクに静的にマッピングされ、アドレスビットのサブセットがバンクを決定するために使用される。例えば、アドレスの低次ビットをマッピングインデックスとして用いることができる。バンクはｎウェイのセットアソシアティブ、例えば４ウェイのセットアソシアティブであり、以下に説明するように全連想度はバンク間及びバンク内の連想度の積である。かかる静的非均等型キャッシュアーキテクチャには幾つかの利点がある。例えば、バンクがキャッシュコントローラ及び／またはプロセッサに近ければ近いほどアクセスは短い待ち時間で行える。近いバンクが頻繁にアクセスされる場合は、性能は劇的に増加することがある。
【０００９】
例えば、静的ＮＵＣＡ構成のアドレス可能な各バンクは、それぞれ方向が異なる、バンク当たり１２８ビットの２またはそれ以上の専用データ通信チャンネルを備えている。かかるバンクには専用チャンネルがあるため、各バンクをそれぞれ独立に高速でアクセスすることができる。バンクが小さいとコンカレンシが大きくなり、隣接するバンク間の待ち時間の差が小さくなるが、バンク当たりのチャンネル数が多いため面積、従って、時間及びペナルティが増加する。
【００１０】
ＮＵＣＡの平均性能は、キャッシュサイズの増加につれて、ある点まで増加する。サイズがさらに大きくなると、キャッシュが占有する面積が大きくなるためヒット待ち時間が増加し、ミスが減少する利点を圧倒することがある。
【００１１】
技術により可能な素子のサイズが減少するにつれて、個々のバンクのアクセス時間及びキャッシュコントローラから遠い所にあるバンクへのルーティング遅延が増加するが、これは微細素子形成技術にとって最適な構成が大型バンクを利用するからである。大型で速度の遅いバンクのオーバーヘッドは、数が多く小型のバンクに必要とされる余分なワイヤによる遅延に比べれば小さいかもしれない。微細素子形成技術の利用により遭遇するワイヤ遅延が大きくなればなるほど、遠く離れたバンクへのルーティング遅延は増加することになる。キャッシュの生のルーティング遅延はかなり大きくなる可能性があるが、競合は問題としては小さいものである。
【００１２】
バンク数が増加すると、バンク当たりのチャンネルの面積オーバーヘッドにより、各バンクはキャッシュサイズの増加につれてますます大型且つ低速になるため、最適の数に到達する。この基本的な静的ＮＵＣＡの制約により、小型で高速のバンクのアクセス時間を減少させる試みが妨げられる。
【００１３】
基本的なＮＵＣＡアーキテクチャによるバンク当たりのチャンネル面積の制約を軽減するために、別の構造を用いることが可能である。図１Ａ及び１Ｂは、本発明の種々の実施例による静的非均等型キャッシュアーキテクチャのブロック図である。
【００１４】
この場合、装置１００の構成はバンク当たりのチャンネルに起因する多数のワイヤの必要性をなくすものである。切換型ＮＵＣＡと呼ぶこの構成では、例えば軽量で虫食穴をルーティングさせる二次元メッシュのようなネットワーク１１０に、各バンク１２８の簡単なスイッチ１２２へのポイント間リンク１１６が埋め込まれている。各リンク１１６は、例えば、双方向ルーティング用の２つの別個の１２８ビットチャンネル１３４と、４ウェイセットアソシアティブバンク１２８とを有する。各スイッチ１２２は、例えば１６バイトのパケットをバッファするように構成することが可能であり、各バンク１２８は未決のリクエスト１４２全体をホールドするための大型バッファ１３８を含む。かくして、１つのリクエスト１４２は、別のリクエストがサービスを受けている間に特定のバンク１２８で待ち行列を作ることができる。第３のリクエストが到来するとネットワークライン１１６がブロックされ、新しく到着したリクエスト１４２がネットワークスイッチ１２２内にバッファされ、それらのスイッチ１２２を使用しなければならない他のリクエストを遅延させる。異なるネットワーク１１０のパスに沿う他のバンク１２８は、並行してアクセスすることができる。図１Ｂを参照すると、各バンク１２８は複数のサブバンク１４６、１またはそれ以上のタグアレイ１４８、プリデコーダ１５０、センス増幅器１５２、及びワードラインドライバ及びデコーダ１５３を含むことがわかる。バンクは、チャンネル１３４を介してキャッシュ制御回路１５４に結合されている。
【００１５】
各バンク１２８は、１つのバンク１２８に沿うルーティング遅延がちょうど１クロックサイクル以下になるようなサイズにすることができる。スイッチ１２２は、チャンネル当たり４ビットを含む任意数のビットのためのバッファ１３８のスロットを含むように構成することができる。実験によると、切換型ＮＵＣＡ構成の最小、平均及び最大バンク待ち時間は静的ＮＵＣＡ構成にとっては有意に小さいことがわかっている。切換型ＮＵＣＡネットワーク１１０は、専用パーバンクチャンネルよりも消費面積が小さく、アレイが小型になって全てのバンク１２８のアクセスが速くなるから、キャッシュアクセスをスピードアップすることができる。例えば、一部の実施例の基本的な静的ＮＵＣＡ構成では、ワイヤはバンク面積の２１％を占めるが、静的ＮＵＣＡ構成では、チャンネルオーバーヘッドはバンク１２８の全面積の６％未満に制限される。
【００１６】
かくして、実験によると、切換型ＮＵＣＡ構成は、特に技術により回路素子のサイズが減少するにつれて基本的な静的ＮＵＣＡ構成より有意に速いアクセスを可能にすることがわかっている。バンク当たりのワイヤオーバーヘッドの減少により得られるより別の利点として、チップ上により多くのバンク１２８を実現できることがある。
【００１７】
データのマッピング、サーチ及び移動に関して異なる方式を選択すると、性能をさらに向上させることが可能である。これらの方式については、キャッシュ内でのデータ管理につき３つの領域を考慮することができる。それらは、即ち、（１）如何にしてデータをバンクにマッピングするか、何れのバンクにデータを常駐させることができるかの論理から物理への「マッピング」、（２）如何にして可能性のある場所のセットを１つのラインに対してサーチするかの「サーチ」、及び（３）如何なる条件でデータを１つのバンクから別のバンクへ移送すべきかの「移動」である。例えば、頻繁にアクセスされるデータを高速バンク（例えば、キャッシュコントローラに近いバンク）に配置し、それほど重要でないが依然としてキャッシュされるデータを遅速バンク（例えば、キャッシュコントローラから離れたバンク）に配置することにより、非均等型アクセスを利用することができる。
【００１８】
バンクの数が多いと、キャッシュラインをバンクにマッピングするにつき実質的な柔軟性が得られる。一方の一番端にあるのは基本的な静的ＮＵＣＡ方式であるが、１つのラインのデータを静的に決定される単一バンクにマッピングすることができる。もう一方の端にあるのは、ラインを任意のキャッシュバンクにマッピングできる方式である。後者のアプローチは配置の柔軟性を増加させるが、集中型タグ記憶装置を介するか、またはタグを全バンクに同報することによるか何れかで各バンクをサーチする必要があるため、そのラインを見つけるオーバーヘッドが大きすぎる。展開バンクセットを用いて中間的な解決法を実現することができる。
【００１９】
この開示のために、キャッシュのＭ個のバンクのサーチをｋ個のステップで行い、Ｍ個のバンクの一部のサブセットは各ステップ（即ち、ｓ1、ｓ2、・・・、ｓk）でサーチされるため、サーチされるサブセットのバンクの和がＭに等しいことに注目して、以下の定義について述べる。
【００２０】
マッピング
展開バンクセット：展開バンクセットは、全てのセットアソシアティブウェイを単一バンクに配置する代わりに、各セットのウェイを多数の物理的バンク間に割り当てるか、または多数のバンクにわたって「展開」させるキャッシュメモリバンク構成である。
動的マッピング：動的マッピングは、Ｍ個のバンクのうち２またはそれ以上のバンクへのマッピングが可能であり、キャッシュにありながら可能なバンク間を移動できるキャッシュラインのことを言う。
フェアマッピング：フェアマッピングは、平均アクセス時間が実質的に等しくなるように各バンクセットからの選択されたウェイを異なるバンクへマッピングする方式である。
高速共有マッピング：高速共有マッピングは、プロセッサ／コントローラに最も近い選択されたバンク（例えば、高速バンク）が各々が多数のバンクセット間で共有され、その各セットは多数のバンクセット間で共有されない他のバンクを含む方式である。
【００２１】
コピー方式
ワンコピー方式：これはビクティムキャッシュラインをキャッシュ内のどこか他の場所（例えば、移動前に通常はビクティムキャッシュラインの元の場所よりキャッシュコントローラから遠いターゲットライン場所）へ移動した後、そのターゲットラインをキャッシュから追い出すことができるキャッシュ追出し方式である。
ｎコピー方式：これは第１のビクティムキャッシュラインを、キャッシュ内のどこか他の場所（例えば、第１のターゲットライン場所）へ移動させた後、第１のターゲットラインをキャッシュ内のどこか他の場所（例えば、第２のターゲット場所）へ移動させ、その後、第２のターゲットラインを、ｎ個のラインが移動されるまで、順次どこか他の場所へ移動させる、ワンコピー方式の変形方式である。
ゼロコピー方式：これは、ビクティムキャッシュラインを全く移動させずに、ただキャッシュから追い出すキャッシュ追出し方式である。
【００２２】
サーチ方式
インクリメンタルサーチ方式：この方式は、実質的に直列のような態様で連続してキャッシュの個々のバンクをサーチすることにより実現可能である（即ち、ｋ＝Ｍ、及び
2005522773.tif 000003
につきｓi＝１）。
限定マルチキャストサーチ方式：この方式は、キャッシュの一部の選択された数のバンクまたはバンクのサブセット内の所望のデータを実質的に同時にサーチすることにより実現可能である（例えば、サーチリクエストは選択されたサブセットのバンクへ実質的に同時に送られるか同報される）。サブセットのバンクは、コントローラ及び／またはプロセッサに最も近い多数のバンクを選択するか、またはパーシャルタグ記憶装置により特定されたバンクを用いることにより選択することができる。コントローラは、プロセッサを構成するかまたはプロセッサに結合される。
マルチキャストサーチ方式：この方式は、キャッシュの実質的に全てのバンクを実質的に同時にサーチすることにより実現可能である（例えば、サーチリクエストは実質的に全てのバンクへ実質的に同時に送られる、またはｋ＝１）。
区分マルチキャストサーチ方式：この方式は、キャッシュの一部の選択された数のバンクまたはバンクのサブセット内の所望のデータを実質的に同時にサーチすることにより実現可能である（例えば、サーチリクエストは、ｋ＝２及びｓｌ＝Ｍ／２、Ｓ２＝Ｍ／２、ｓ2＝Ｍ／２と設定するなどして選択されたバンクのサブセットへ実質的に同時に送られる）。バンクのサブセットは、キャッシュコントローラに最も近いある数のバンクを選択することにより選択可能である。そうすると、所望のデータが選択されたサブセットのバンク内にない場合には、キャッシュの残りのバンクをインクリメンタル方式でサーチすることができる。
【００２３】
図２は、本発明の種々の実施例による動的非均等型キャッシュアーキテクチャのブロック図である。展開バンクセットはマルチバンクキャッシュ２００をセットアソシアティブ構造として取り扱うが、各セット２４６は多数のバンク２２８にわたり展開され、各バンク２２８はそのセット２４６の１またはそれ以上のウェイを保持する。連想性に実現に用いるバンク２２８の集合体をバンクセット２４６と呼ぶことができるが、そのセットのバンク数はその連想度に対応する。アソシアティブウェイが異なるとアクセス待ち時間も異なる。
【００２４】
図３Ａ、３Ｂ及び３Ｃは、本発明の種々の実施例によるデータマッピング方式を示す流れ図である。キャッシュは多数のバンクセットより成る。例えば、図３Ａに示すように、３２個のバンクを有するキャッシュ３００は、８個のバンクセット３４６がそれぞれ４個のキャッシュバンク３２８を有する、４ウェイセットアソシアティブキャッシュとして編成されている。展開セットキャッシュ３００のヒットをチェックするために、バンクセットの４個のバンク３２８のそれぞれに固有のタグをチェックすることができる。
【００２５】
バンク３２８をバンクセット３４６及びウェイに割り当てるために、単純マッピング、フェアマッピング及び共有マッピングを含む任意の数の方法を用いることができる。図３Ａに示す単純マッピング方式の実施例では、キャッシュ３００のバンク３２８の各カラムがバンクセット３４６になるが、そのカラム内の全てのバンク３２８がセットアソシアティブウェイ３５０を構成する。従って、キャッシュ３００は、最初にバンクセットカラムを選択し、カラム内のウェイ３４６を選択し、最後にキャッシュのそのカラム内のバンク３２８上のタグをマッチさせることにより、１つのラインのサーチをすることができる。従って、１つのカラムは多数のバンクセットを表し、１つのカラム内の１つのバンクはそのカラムの各バンクセットについて１つのウェイ（または、バンク内連想性がある時はそれ以上）を保持することができる。列の数は各バンクセット３４６の所望のウェイ３５０の数に対応しないこともあり、全てのバンクセット３４６にアクセスするための待ち時間は同一でなく、従って、一部の列３５０が他の列よりもキャッシュコントローラ３５４に近いため、一部のバンクセット３４６は他のセットより速いことに注意されたい。
【００２６】
図３Ｂは、単純マッピング方式の下で生ずる問題に複雑さは増加するが対処しているフェアマッピング方式の実施例を示す。この場合、物理的バンク３２８へのセット３４６のマッピングを図の矢印３４６で示す。バンク３２８は、全てのバンクセット３４６にわたる平均アクセス時間が実質的に等しくなるように、バンクセット３４６に割り当てられる。フェアマッピング方式は、各バンクセット３４６につきほぼ等しい平均アクセス時間を与える。しかしながら、セット３４６のバンク３２８間より複雑なルーティングパスが必要であるため、ルーティング待ち時間が長くなり、ネットワーク３１０内の競合が増える。
【００２７】
図３Ｃは、高速共有マッピングを含む共有マッピング方式の実施例を示す。この方式は、多数のバンクセットの間でキャッシュコントローラに最も近いバンクを共有することにより全てのバンクセットに最速のバンクアクセスを提供しようとするものである。バンク内連想性はセット連想性を見る伝統的な方法である。バンク間連想性はここで述べるように展開バンクセットにより実現される。全連想度はバンク間連想度とバンク内連想度の積である。従って、展開バンクセットが単一バンクを共有する場合、キャッシュの全てのバンクはＮウェイセットアソシアティブである。あるいは、単独所有のバンクから共有のバンクへスワッピングを行うと、共有バンクは非共有バンクよりセットが少数であるから、単独所有のバンク内に配置できないラインが生まれる。一部の実施例において、最大２つのバンクセットに１つのバンクを共有させるのがベストである。従って、Ｎ／Ｍ（例えば、Ｍ＝２）の最も遠いバンクセットはそれぞれ最も近いＮ／Ｍのバンクセットのうちの１つの最も近いバンクの半分を共有する。この選択により他のセットよりバンク連想度がわずかに高いバンクセットが生まれるが（一部のバンクセットは非共有バンクが多い）、これによりそのバンクセットへのわずかに大きい平均アクセス待ち時間を相殺することができる。かかる方式を例えば図３Ｃに示す。この方式によると、カラム３の底のバンク３２８はカラム１及び３からのラインをキャッシュし、カラム４の底のバンク３２８はカラム２及び４からのラインをキャッシュし、以下続く。この例では、８個のバンクセット３４６の最も遠い４つのセット（カラム１、２、７及び８）は８個のバンクセット３４６の最も近い４つのセット（カラム３、４、５及び６）の最も近いバンク３２８を共有する。
【００２８】
種々の異なる方式によりバンクセットに含まれるラインをサーチしその場所を突き止めることができるが、ヒットまたはミスを確かめる時間が増加すると性能が低下する。１つの可能な方式は、バンクをキャッシュに最も近いバンクからスタートしてキャッシュコントローラから最も遠いバンクまで進む順序で、リクエストされたラインが見つかるかまたは最後のバンクでミスが生じるまでサーチするインクリメンタルサーチの方式である。
【００２９】
別の可能な方式は、リクエストされたアドレスがリクエストされたバンクセットの一部または全てのバンクへ実質的に同時に同報されるマルチキャストサーチ方式である。探索はほぼ並行して、しかしながら、ネットワークを介するルーティング遅延により実際は異なる時間で進行する。マルチキャストサーチ方式はエネルギー消費及びネットワーク競合の増加を犠牲にして優れた性能を提供するものであるが、その理由は、コントローラから遠いバンクへのヒットはインクリメンタルサーチ方式よりも速く処理されるからである。しかしながら、アドレスが各バンクへルーティングされる際に消費される余分のアドレスバンド幅により他のアクセスが遅くなる。
【００３０】
限定マルチキャスト方式のような中間のハイブリッド方式も可能であるが、その方式ではバンクセット内のバンクの第１の部分が並行してサーチされた後、残りの部分がインクリメンタル方式でサーチされる。従って、大部分のヒットは高速の探索により処理されるが、一度に全てのウェイにアクセスすることにより消費されるエネルギー及びネットワークバンド幅を回避することができる。別のハイブリッド方式として、バンクセットがバンクのサブセットに分解される区分マルチキャスト方式がある。各サブセットは反復してサーチされるが、各サブセットに含まれるメンバーバンクは並行してサーチされる。
【００３１】
タグがバングに分散される分散キャッシュアレイも、最新のサーチ技術の利点を享受することができる。第１に、キャッシュヒット上のラインを見つけるためには多数のバンクをサーチする必要がある。第２に、ラインがキャッシュ内にない場合、最遅のバンクによりリクエストがミスになったことを確かめるに必要な時間が決まる。即ち、ミス確認時間はバンクセット内のバンクの数が増加するにつれて大きくなる。インクリメンタルサーチ方式はバンク探索数を減少させることができるが、直列方式のタグ探索時間はヒット待ち時間及びミス確認時間の両方を増加させる。
【００３２】
パーシャルタグの比較を実行すると、バンク探索数及びミス確認時間の両方を減少することができる。この場合、パーシャルタグビットはキャッシュコントローラ内に位置するスマートサーチアレイに保存できる。例えば、パーシャルタグの比較に基づき２つの「スマートサーチ」方式を実現できる。第１の方式では、キャッシュアレイを前の方式と同様にサーチすることができる。しかしながら、保存されたパーシャルタグビットをリクエストされたタグの対応ビットと実質的に並行して比較して、マッチしなければ直ちにミスの処理を開始する。この方式では、スマートサーチアレイが誤ヒットの可能性を低くするに十分なライン当たりのタグビットを含むようにして、ミスが発生すると、リクエストされたタグに対するキャッシュされたタグの偶発的なパーシャルマッチが頻繁に起こらないようにする必要がある。一部の実施例では、実験によると、各タグからの約３個から約６個のビットを用いると、誤ビットの発生確率の減少とスマートサーチアレイへのアクセス待ち時間の増加との間でよいバランスをとれることがわかっている。
【００３３】
第２のスマートサーチ方式では、パーシャルタグの比較によりミス発生時にサーチされるバンクの数を減少することができる。スマートサーチアレイはアクセスするために多数のサイクル（例えば、４乃至６サイクル）を必要とするため、任意のキャッシュアクセス前にスマートサーチアレイのアクセスを直列化すると性能が有意に低下する。別法として、最も近いバンク（または１またはそれ以上の近いバンク）へのアクセスがスマートサーチアレイのアクセスと並行して進行できるようにしてもよい。キャッシュコントローラに最も近いバンクのヒットがこの最初のアクセス時に起こらない場合は、パーシャルタグの比較がうまくいった他の全てのバンクを並行してサーチする。
【００３４】
動的ＮＵＣＡ（Ｄ−ＮＵＣＡ）装置、システム及び方法は、キャッシュラインが割り当てられたバンクを変更できるようにして、キャッシュコントローラに最も近いバンクにおけるキャッシュヒットの数を増加するように作用する。ＬＲＵビットを用いてラインの場所を決定する。しかしながら、これによりバンク間のトラフィック及びデータの移動量が増加する。キャッシュラインを増分移動させ、そして／または実質的に同じ年齢のデータを実質的に同時に昇進させる世代昇進方式を用いることにより、バンクセットの物理的トポロジー上にマッピングされたＬＲＵリストを依然として近いが純粋なＬＲＵデータマッピング方式に必要とされるコピー量を減少することができる。かくして、キャッシュラインにヒットが生じると、このラインは、キャッシュコントローラに次に最も近いバンクのラインとスワップすることができる。頻繁に使用されるラインは、その後、高速のバンク（即ち、キャッシュコントローラに近い所にあるバンク）の方へ移行するが、それほど頻繁に使用されないラインは遅いバンク（即ち、キャッシュコントローラから離れた所にあるバンク）へ降格することができる。
【００３５】
Ｄ−ＮＵＣＡ装置システム及び方法はまた、キャッシュミスにより生じる入来データブロックの配置を決定するように作用する。例えば、置換データブロックがキャッシュコントローラに近いバンクにロードされる場合、その場所から重要なデータブロックを変位させることができる。しかしながら、その置換ブロック自体が頻繁に使用されるデータブロックであり、キャッシュコントローラから遠いバンクへロードされる場合、その置換ブロックは高速の近いバンクに最終的に移行する前に幾つかのアクセスを必要とする。昇進は、キャッシュバンクの数で測った昇進距離により説明することができる（例えば、３つのバンクに相当する昇進距離は、バンク５からバンク２へ、８個のバンクのラインに沿って最も遅く遠いバンクから最速の最も近いバンクへのキャッシュラインの昇進を意味する）。昇進はまた、データブロックの昇進実行前に生じる１つのバンクに対するヒットの数で測った昇進トリガーにより説明することができる。「末尾挿入」も実現可能である。例えば、ミスが発生すると、フェッチされたキャッシュラインはキャッシュコントローラから最も遠いバンクへ、または展開セットの末尾へ配置することができる。
【００３６】
実行しなければならない別の決定には、置換時にビクティムデータブロックに対して行うものが含まれる。多くのタイプの追出し方式があるが、それには、ビクティムがキャッシュから追出される方式（ゼロコピー方式）、及びビクティムが低い優先度のバンクへ移動されキャッシュコントローラから遠い重要度の低いラインに置換される方式（ワンコピー方式）が含まれる。かくして、入来データブロックを配置する場所を選択し、変位されたデータブロックをコピーするかまたはコピーしない。
【００３７】
ここまで説明した方式を組み合わせる方式が幾つか可能であり、それにより本発明に極めて多数の実施例が提供される。例えば、１つの実施例は、単純マッピング、マルチキャストサーチ、各ヒットに対する１つのバンクの昇進方式、及びミス発生時にビクティムとして最も遅いバンクのブロックを選択する置換方式を含むことができる。これらの技術は種々のキャッシュサイズで利用されるが、それにはバンクセットが任意数のアソシアティブウェイ（例えば、２ウェイ、４ウェイ、８ウェイ、１６ウェイなど）を有する多くのメガバイト（例えば、１ＭＢ、２ＭＢ、４ＭＢ、８ＭＢ、１６ＭＢなど）メモリを備えたＤ−ＮＵＣＡキャッシュが含まれる。かくして、例えば、別のＤ−ＮＵＣＡ実施例は、単純マッピング、マルチキャストサーチ、末尾挿入、及び各ヒットに対する１つのバンクの昇進方式を含む。
【００３８】
個々の方式を独立した形で調整することにより他の実施例を考案することが可能である。例えば、マッピング機能を単純マッピングからフェアマッピングへ変更することにより、たとえアンロード待ち時間が小さくても切換型ネットワークにおける競合により性能を低下させることがある。切換型ネットワークの代わりに他のタイプのネットワークを用いてもよいことに注意されたい。
【００３９】
別例として、マルチキャスト方式から純粋なインクリメンタルサーチ方式への変更によりバンクアクセス数を実質的に減少するものが含まれる。
【００４０】
多くのハイブリッドサーチ方式は、マルチキャスト方式とインクリメンタルサーチ方式の特徴を組み合わせることにより構成できる。例えば、１つのハイブリッド方式として、バンクセットの最初の２つのバンクにマルチキャスティングを行った後、残りのバンクのインクリメンタル方式でサーチするものがある。異なるハイブリッド方式として、最初の２つのバンクに対してマルチキャスティングを行い、データが発見できなければ、残りのバンクに対してもマルチキャスティングを行うものがある。ハイブリッド方式を入念に選択すると、性能を向上させ、ベースラインの非ハイブリッド方式により必要とされるバンクアクセスの数を減らすことができる。
【００４１】
データ昇進方式には、ブロックを多数のヒット発生後に限り昇進させるか、または単一のヒットが発生するとブロックを多数のバンクだけ昇進させるものがある。追出し方式は、追出しのためにリストの末尾のブロックを置換可能にするか、または追出しリストの最初のブロックを置き換え、それをランダムな優先度の低いバンクセットにコピーできるようにする。別の実施例は、スマートサーチ方式を共有マッピングと組み合わせたものである。
【００４２】
本発明の他の実施例の装置は、キャッシュ制御回路と、このキャッシュ制御回路に結合された独立してアクセス可能な複数のメモリバンクとを含むが、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有する。独立してアクセス可能な複数のメモリバンクはそれぞれ、切換型ネットワークを用いてキャッシュ制御回路に結合される。独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは、ワードラインドライバとデコーダとを含む。独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは、センス増幅器を含む。
【００４３】
かくして、図１−３を参照すると、種々の実施例について説明したことがわかる。例えば、１つの実施例の装置３００は、キャッシュ制御回路３５４と、このキャッシュ制御回路３５４に結合された独立してアクセス可能な複数のメモリバンク３２８とを含み、独立してアクセス可能な複数のメモリバンク３２８のうちの少なくとも２つのバンクは非均等な待ち時間を有する。複数のキャッシュラインは、独立してアクセス可能な複数のメモリバンク３２８のうちの少なくとも１つのバンクに静的マッピングすることができる。そして、所望であれば、独立してアクセス可能な複数のメモリバンク３２８をそれぞれ、１またはそれ以上の専用チャンネルを有するネットワーク３６０を用いてキャッシュ制御回路３５４に結合することができる。
【００４４】
上述したように、非均等な待ち時間は、データを独立してアクセス可能な複数のメモリバンク３２８にルーティングするワイヤ遅延により発生されるか、それを含むものである。非均等な待ち時間はまた、独立してアクセス可能な複数のメモリバンク３２８のバンクアクセス時間により発生されるか、それを含むものである。さらに、非均等な待ち時間は、ネットワーク３６０、または独立してアクセス可能な複数のメモリバンク３２８の所定のバンクに結合された専用チャンネルのアクセス時間により生じるか、それを含む。かくして、キャッシュ制御回路３５４は、選択されたバンクがキャッシュ制御回路３５４からの第１のリクエストの処理を完了するまで、第２のリクエストを独立してアクセス可能な複数のメモリバンクのうちの１つに送ることができない。
【００４５】
この装置３００は、バンク３２８が中間点３６８を含む側部３６４を有するアレイとして形成され、キャッシュ制御回路３５４が側部３６４のほぼ中間点３６８に位置するようにバンク３２８が編成されたものである。独立してアクセス可能な複数のメモリバンク３２８のうち選択されたバンクは、セットアソシアティブバンク（例えば、ｎウェイまたは４ウェイのセットアソシアティブバンク）であることが可能である。
【００４６】
一部の実施例において、独立してアクセス可能な複数のメモリバンク１２８はそれぞれ切換型ネットワーク１１０を用いてキャッシュ制御回路１５４に結合することができる。このネットワーク１１０は、切換型二次元メッシュネットワーク１１０でよく、複数のポイント間リンク１１６を含む。複数のポイント間リンク１１６のうちの選択されたリンクは、単方向または双方向ルーティングにより接続することができる。
【００４７】
切換型ネットワーク１１０は複数のルーター１２２を含む。複数のルーター１２２のうちの選択されたルーターは，独立してアクセス可能な複数のメモリバンク１２８の選択された交差点に配置することができる。ルーター１２２は、アドレス及び／または読出し及び書込みデータを含むデータのルーティングに使用できる。切換型ネットワーク１１０は同期ネットワークまたは非同期ネットワークでよい。
【００４８】
一部のバンク１２８は，リクエストバッファ１３８及び／またはタグアレイ１４８を含む。リクエストバッファ１３８はキャッシュ制御回路１５４に結合され、キャッシュ制御回路１５４から独立してアクセス可能な複数のバンク１２８のうちの１つのバンクへのリクエストが競合するため、そのリクエストはリクエストバッファ１３８に保存される。
【００４９】
複数のキャッシュラインは、独立してアクセス可能な複数のメモリバンク１２８のうちの少なくとも２つのバンクに動的マッピングできることがわかるであろう。タグ記憶装置１５６はキャッシュ制御回路１５４に結合される。
【００５０】
タグを保存する幾つかのアプローチが可能である。例えば、タグ記憶装置１５６は集中型でありキャッシュバンク１２８の外側に位置する。あるいは、タグを分散させて各バンク１２８に記憶させることができる。ハイブリッドアプローチとして、フルタグをバンク１２８へ分散させ、集中型タグ記憶装置１５６にパーシャルタグを記憶させるものがある。この場合、パーシャルタグを用いてフルタグのサーチを実行すべき大体の場所を指示することができる。さらに、同報モジュール１５８をキャッシュ制御回路１５４に結合して、タグを独立してアクセス可能な複数のメモリバンク１２８にそれぞれ同報することができる。
【００５１】
さらに、独立してアクセス可能な複数のメモリバンク３２８を少なくとも２つの展開セット３４６に編成することが可能である。独立してアクセス可能な複数のメモリバンク３２８のうちの選択されたバンク３２８は、独立してアクセス可能な複数のメモリバンク３２８のうちの別の選択されたバンク３２８に比べて、プロセッサ３７２及び／またはこのプロセッサ３７２が結合されたキャッシュ制御回路３５４に近い所に位置する。選択されたバンク３２８（即ち、近いバンク）と、別の選択されたバンク３２８（即ち、遠いバンク）とを、少なくとも２つの展開バンクセット３４８の選択された１つのセット（即ち、同じバンクセット）に位置させることができる（図２Ｂを参照）。少なくとも２つの展開バンクセットのうちの１つの各バンク３２８は、少なくとも２つの展開バンクセット３４６のうちの１つの少なくとも１つのアソシアティブウェイを保持する。さらに、少なくとも２つの展開バンクセット３４６の１つは少なくとも２つのメモリバンク３２８を含み、少なくとも２つのメモリバンク３２８のうちの１つの少なくとも１つのアソシアティブウェイは少なくとも２つのメモリバンク３２８のうちの別のバンクの別のアソシアティブウェイとは異なるアクセス待ち時間を有する。
【００５２】
独立してアクセス可能な複数のメモリバンク３２８は、独立してアクセス可能な複数のメモリバンク３２８のサブセットを少なくとも２つの展開バンクセット３４６にそれぞれマッピングすることにより、少なくとも２つの展開バンクセット３４６に編成することができる。独立してアクセス可能な複数のメモリバンク３２８は、独立してアクセス可能な複数のメモリバンク３２８の１つのカラムを少なくとも２つの展開バンクセット３４６にマッピングし、独立してアクセス可能な複数のメモリバンク３２８の別のカラムを少なくとも２つの展開バンクセット３４６の別のセットにマッピングすることにより、少なくとも２つの展開バンクセット３４６に編成することができる。
【００５３】
かくして、独立してアクセス可能な複数のメモリバンク３２８は、ほぼ等化された平均アクセス時間に従って独立してアクセス可能な複数のメモリバンク３２８のうちの選択されたバンクをフェアマッピングすることにより、少なくとも２つの展開バンクセット３４６に編成することができる。さらに、独立してアクセス可能な複数のメモリバンク３２８は、その独立してアクセス可能な複数のメモリバンクのそれぞれに関連するキャッシュ制御回路３５４からの距離に応じて独立してアクセス可能な複数のメモリバンク３２８のうちの選択されたバンクを高速共有マッピングすることにより、少なくとも２つの展開バンクセット３４６に編成することができる。独立してアクセス可能な複数のメモリバンク３２８はまた、ｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリ３００に編成することが可能であり、各展開バンクセット３４６は独立してアクセス可能な複数のメモリバンク３２８から選択されたメモリバンク３２８のサブセットを含み、ｎウェイ３５０のうちの少なくとも２つのウェイは異なるアクセス待ち時間を有する（例えば、ｎは４、ｍは８でよく、メモリバンクのサブセットは４つのメモリバンクを含む）。ｎウェイ３５０の各ウェイ３５０は異なるアクセス待ち時間を有する。
【００５４】
本発明の実施例はまた、１またはそれ以上の算術機能ユニット３７０（恐らく算術論理ユニットを含む）より成るプロセッサ３７２と、算術機能ユニット３７０に結合されたキャッシュ制御回路３５４と、キャッシュ制御回路３５４に結合された独立してアクセス可能な複数のメモリバンク３２８とを含む。上述したように、独立してアクセス可能な複数のメモリバンク３２８のうちの少なくとも２つのバンクは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンク３２８は少なくとも２つの展開バンクセット３４６に編成される。
【００５５】
本発明の他の実施例は、キャッシュ制御回路３５４を含むプロセッサ３７２と、キャッシュ制御回路３５４に結合された独立してアクセス可能な複数のメモリバンク３２８とより成るシステム３７１を含む。バス３７４はプロセッサ３７０に作動的に結合され、ランダムアクセスメモリ３７６はバス３７４に作動的に結合されている。上述したように、独立してアクセス可能な複数のメモリバンク３２８のうちの少なくとも２つのバンクは非均等な待ち時間を有し、１またはそれ以上の展開バンクセット３４６への編成を含む多くの異なる方法によりマッピングすることができる。
【００５６】
本発明の種々の実施例の装置、プロセッサ、メモリ、集積回路、キャッシュコントローラ、システム、製品、方法及び他の局面は、データ伝送以外の用途及びコンピュータを含むシステム以外の用途に用いるように構成されると予想され、かくして、本発明の実施例はそれらに限定すべきでない。装置１００、２００、３００及びシステム３７１を示す図は本発明の種々の実施例の構造の一般的な理解を目的としたものであり、その装置の全ての要素及び特徴並びにここに述べた構造を利用するシステムの完全な説明として役立つことを意図されていない。
【００５７】
本発明の種々の実施例の新規な装置及びシステムを含む用途は、高速コンピュータ、通信及び信号処理回路、データトランシーバ、モデム、プロセッサモジュール、埋め込み型プロセッサ及び多層多チップモジュールを含む特定用途モジュールに用いられる電子回路を含んでいる。かかる装置及びシステムはさらに、テレビジョン、セルラー電話、パソコン、ワークステーション、ラジオ、ビデオプレーヤ、車両などのような多種多様な電子システム内にサブコンポーネントとして含まれることがある。
【００５８】
本発明の実施例はまた多数の方法を包含する。図４は、本発明の種々の実施例に従ってデータにアクセスしデータを移動させる方法を示す流れ図である。例えば、方法４１１は、ブロック４２１において、プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータを含むデータへのアクセスでスタートする。独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つのバンクは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクのうちの任意数のバンクは１またはそれ以上の展開バンクセットに編成可能である。独立してアクセス可能な複数のメモリバンクのうちの１またはそれ以上のバンクは、プロセッサに結合されるかまたはプロセッサを構成するキャッシュコントローラに、選択された他のバンクよりも近いところに位置する。
【００５９】
この方法は、ブロック４２５においてデータへのアクセス頻度を求め、ブロック４３１において複数のバンクに含まれる選択されたバンクへ、選択された他のバンクからデータを移行させるステップを含む。選択されたバンクは、選択された他のバンクよりもキャッシュコントローラに近い所に位置する。
【００６０】
ブロック４２１における第１及び第２のデータのアクセスは、ブロック４３５におけるプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクのサーチを含む。サーチは、ブロック４４１においてマルチキャストサーチ方式により行うことができる。ブロック４２１における第１及び第２のデータのアクセスはまた、ブロック４４１における限定マルチキャストサーチ方式による独立してアクセス可能な複数のメモリバンクのサーチを含む。さらに、第１及び第２のデータのアクセスは、ブロック４４１におけるインクリメンタルサーチ方式による独立してアクセス可能な複数のメモリバンクのサーチを含む。さらに、第１及び第２のデータのアクセスは、ブロック４４１における区分マルチキャストサーチ方式による独立してアクセス可能な複数のメモリバンクのサーチを含む。さらに、第１及び第２のデータのアクセスは、マルチキャスト方式、限定マルチキャスト方式、インクリメンタルサーチ方式及び／または区分マルチキャストサーチ方式を含む群から選択された方式の組み合わせによる、ブロック４４１に示した独立してアクセス可能な複数のメモリバンクのサーチを含む。
【００６１】
この方法４１１は、選択された基準が満足されたと判定されると、独立してアクセス可能な複数のメモリバンクのうちの選択された他のバンクから独立してアクセス可能な複数のメモリバンクの選択されたバンクへ第１のデータを移行するステップを含む。
【００６２】
例えば、選択された基準は、ブロック４４５において第１のデータが第２のデータより頻繁にアクセスされると判定されると満足される。従って、独立してアクセス可能な複数のメモリバンクのうちの選択された他のバンクから独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクへの移行パス上において、第１のデータは、恐らくは第１のデータを近いメモリバンクにある別のデータとスワップして、ブロック４４５において第１のデータを独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクを通してキャッシュコントローラに徐々に近づくように移行させることにより第１のデータを移動することができる。
【００６３】
この方法４１１はまた、選択された基準が満足されたと判定されると、第２のデータを独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクから独立してアクセス可能な複数のメモリバンクのうちの選択された他のバンクへ移行させるステップを含む。例えば、第１のデータがブロック４５１において第２のデータより頻繁にアクセスされると判定されると起こる。再び、選択されたバンクは、バンクのうちの選択された他のバンクよりもキャッシュコントローラに近い所に位置する。独立してアクセス可能な複数のメモリバンクは、ｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリに編成することが可能である。各展開バンクセットは、独立してアクセス可能な複数のメモリバンクから選択された２またはそれ以上のメモリバンク（例えば、ｎは４、ｍは８である）を含む。
【００６４】
ブロック４４５における独立してアクセス可能な複数のメモリバンクの選択されたバンクを介してキャッシュコントローラへ徐々に近づける第１のデータの移行は、ブロック４５５においてＬＲＵビット方式に基づき複数の展開バンクセットのうちの選択されたセット内のビクティムバンクを選択するステップを含む。ビクティムバンクの選択はまた、上述したように、集中タグ、分散タグまたはハイブリッド方式の利用を含む。従って、ビクティムバンクの選択は、アクセスすべきバンクを決定するためのタグ記憶装置のアクセスを含む。ビクティムバンクの選択はまた分散タグのアクセスを含むが、これは何れのバンクをアクセスすべきかを決定するための個々のバンクのサーチを必要とする。最後に、ビクティムバンクの選択は、タグ記憶装置内のパーシャルタグのアクセスと、パーシャルタグにより指示される個々のバンク内の分散タグのその後のアクセスを含む。
【００６５】
ブロック４４５における独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクを介してキャッシュコントローラへ徐々に近づくようにする第１のデータの移行は、ブロック４６１における世代昇進方式に基づく複数の展開バンクセットのうちの選択されたセット内のキャッシュラインの移動を含む。この方法４１１は、ブロック４６５においてキャッシュラインの追出しを引き続き行う。
【００６６】
ブロック４６１における世代昇進方式に基づく複数の展開バンクセットの選択されたセット内のキャッシュラインの移動は、ブロック４７１における世代昇進方式の昇進距離の選択と、ブロック４７５における世代昇進方式の昇進トリガーの選択とを含む。この方法４１１は、ブロック４６５においてキャッシュラインの追出しを引き続き行う。
【００６７】
かくして、ブロック４４５における独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクを介してプロセッサ及びキャッシュコントローラに徐々に近づくようにする第１のデータの移行は、ブロック４６５における複数の展開バンクセットのうちの選択されたセット内のキャッシュラインの追出しを含むが、これはブロック４８１におけるゼロコピー方式またはｎコピー方式（例えば、ｎ＝ｌ，２，３など）に基づくものである。この方法はその後、ブロック４５１において第２のデータを引き続き移行させる。
【００６８】
特定の実施例を図示説明したが、同一目的を達成するように意図された構成を図示の実施例と置換できることを理解されたい。この開示は、本発明の種々の実施例の任意の、そして全ての変形例または設計変更を包含するものと意図されている。上記説明は例示の目的のためであって、限定の目的のためではないことを理解されたい。上記の実施例と特に図示説明されていない実施例との組み合わせは、この説明から当業者にとっては明らかになるであろう。
【００６９】
本発明の種々の実施例の範囲には、上記構造及び方法を使用する他の任意の用途が含まれる。従って、本発明の種々の実施例の範囲は、頭書の特許請求の範囲及びかかる請求の範囲が享受する均等物の全範囲に関連して決定する必要がある。
【００７０】
要約は３７ＣＦＲセクション１．７２（ｂ）に従うために提供されたものであり、読者が技術的開示の性質を迅速に確かめられるようにするために要約を必要とする。この要約は、特許請求の範囲または意味を解釈したり限定したりするために使用されないという了解の下に提出されたものである。実施例の説明では、種々の特徴部分の開示を単純化するために単一の実施例に集約したことがわかるであろう。この開示方法は、本発明の実施例が各請求項に明示的に記載されたものより多くの特徴部分を必要とするという意図を反映するものと解釈すべきでない。頭書の特許請求の範囲が反映するように、本発明は単一の実施例の全ての特徴部分より少ない所にあるものである。従って、頭書の特許請求の範囲は明細書に組み込まれており、各請求項は別個の好ましい実施例としてそれ自身の立場を有するものである。
【図面の簡単な説明】
【００７１】
【図１Ａ】本発明の種々の実施例による静的非均等キャッシュアーキテクチャのブロック図である。
【図１Ｂ】本発明の種々の実施例による静的非均等キャッシュアーキテクチャのブロック図である。
【図２】本発明の種々の実施例による動的非均等キャッシュアーキテクチャのブロック図である。
【図３Ａ】本発明の種々の実施例によるデータマッピング方式を示す流れ図である。
【図３Ｂ】本発明の種々の実施例によるデータマッピング方式を示す流れ図である。
【図３Ｃ】本発明の種々の実施例によるデータマッピング方式を示す流れ図である。
【図４】本発明の種々の実施例に従ってデータにアクセスしデータを移動させる方法を示すフローチャートである。
【図１Ａ】
2005522773.tif 000004
【図１Ｂ】
2005522773.tif 000005
【図２】
2005522773.tif 000006
【図３Ａ】
2005522773.tif 000007
【図３Ｂ】
2005522773.tif 000008
【図３Ｃ】
2005522773.tif 000009
【図４】
2005522773.tif 000010
【手続補正書】
【提出日】平成16年2月18日(2004.2.18)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
キャッシュ制御回路と、
展開バンクセットとして編成され、キャッシュ制御回路に結合された独立にアクセス可能な複数のメモリバンクとより成り、独立にアクセス可能な複数のメモリバンクのうちの少なくとも４つのバンクは非均等な待ち時間を有する装置。
【請求項２】
複数のキャッシュラインは、独立してアクセス可能な複数のメモリバンクのうちの少なくとも１つに静的マッピングされる請求項１の装置。
【請求項３】
独立してアクセス可能な複数のメモリバンクはそれぞれ専用チャンネルを用いてキャッシュ制御回路に結合される請求項１の装置。
【請求項４】
キャッシュ制御回路は、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクがキャッシュ制御回路からの第１のリクエストの処理を完了するまでは、独立してアクセス可能な複数のメモリバンクのうちの選択した１つのバンクに第２のリクエストを送ることができない請求項１の装置。
【請求項５】
独立してアクセス可能な複数のメモリバンクは側部を有するアレイとして形成され、キャッシュ制御回路はほぼその側部に位置する請求項１の装置。
【請求項６】
独立してアクセス可能な複数のメモリバンクのうちの選択したバンクはセットアソシアティブバンクである請求項１の装置。
【請求項７】
独立してアクセス可能な複数のメモリバンクはそれぞれ切換型ネットワークを用いてキャッシュ制御回路に結合される請求項１の装置。
【請求項８】
切換型ネットワークは切換型二次元メッシュネットワークである請求項７の装置。
【請求項９】
切換型ネットワークに含まれる複数のポイント間リンクのうちの選択されたリンクは双方向性ルーティング手段を用いて接続される請求項７の装置。
【請求項１０】
切換型ネットワークに含まれる複数のポイント間リンクのうちの選択されたリンクは単方向性ルーティング手段を用いて接続される請求項７の装置
【請求項１１】
切換型ネットワークは複数のルーターを含み、複数のルーターのうちの選択されたルーターは独立してアクセス可能な複数のメモリバンクの選択された交差点に位置する請求項１０の装置。
【請求項１２】
複数のルーターはアドレスのルーティングを行う請求項１５の装置。
【請求項１３】
複数のルーターは読出しデータのルーティングを行う請求項１０の装置。
【請求項１４】
複数のルーターは書込みデータのルーティングを行う請求項１５の装置。
【請求項１５】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクはタグアレイを含む請求項１０の装置。
【請求項１６】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクはリクエストバッファを含む請求項１０の装置。
【請求項１７】
キャッシュ制御回路に結合されたリクエストバッファをさらに備え、キャッシュ制御回路から独立してアクセス可能な複数のメモリバンクへのリクエストが競合すると、そのリクエストはリクエストバッファに保存される請求項１０の装置。
【請求項１８】
切換型ネットワークは非同期ネットワークである請求項１０の装置。
【請求項１９】
複数のキャッシュラインは、独立してアクセス可能なメモリバンクのうちの少なくとも２つに動的マッピングできる請求項１の装置。
【請求項２０】
キャッシュ制御回路に結合された分散タグ記憶装置をさらに備えた請求項１９の装置。
【請求項２１】
キャッシュ制御回路に結合された集中型パーシャルタグ記憶装置をさらに備えた請求項２０の装置。
【請求項２２】
タグを独立してアクセス可能な複数のメモリバンクにそれぞれ同報するためにキャッシュ制御回路に結合された同報モジュールをさらに備えた請求項１の装置。
【請求項２３】
独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成される請求項１の装置。
【請求項２４】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは、キャッシュ制御回路に結合されたプロセッサに、独立してアクセス可能な複数のメモリバンクのうちの別の選択されたバンクより近い請求項２３の装置。
【請求項２５】
選択されたバンク及びそれ以外の選択されたバンクは共に少なくとも２つの展開バンクセットのうちの選択されたセットに位置する請求項２４の装置。
【請求項２６】
少なくとも２つの展開バンクセットのうちの１つの各バンクは、少なくとも２つの展開バンクセットのうちの１つの２以上のアソシアティブウェイを保持する請求項２３の装置。
【請求項２７】
少なくとも２つの展開バンクセットのうちの１つは少なくとも２つのメモリバンクを含み、少なくとも２つのメモリバンクの少なくとも１つのアソシアティブウェイは少なくとも２つのメモリバンクのうちの別の１つの別のアソシアティブウェイとは異なるアクセス待ち時間を有する請求項２６の装置。
【請求項２８】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのサブセットを少なくとも２つの展開バンクセットのうちのそれぞれにマッピングすることにより、少なくとも１つの展開バンクセットに編成される請求項２３の装置。
【請求項２９】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのうちの第１群のバンクを少なくとも２つの展開バンクセットのうちの１つにマッピングし、また、独立してアクセス可能な複数のメモリバンクのうちの第２群のバンクを少なくとも２つの展開バンクセットの別のセットにマッピングすることにより、少なくとも２つの展開バンクセットに編成される請求項２８の装置。
【請求項３０】
独立してアクセス可能な複数のメモリバンクのうちの第１群のバンクは第１のカラムを構成し、独立してアクセス可能な複数のメモリバンクのうちの第２群のバンクは第２のカラムを構成する請求項２９の装置。
【請求項３１】
独立してアクセス可能な複数のメモリバンクは、独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクをフェアマッピングすることにより、少なくとも２つの展開バンクセットに編成される請求項２９の装置。
【請求項３２】
独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクを高速共有マッピングすることにより、少なくとも１つの展開バンクセットに編成される請求項２９の装置。
【請求項３３】
独立してアクセス可能な複数のメモリバンクは、ｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリに編成されており、各展開バンクセットは独立してアクセス可能な複数のメモリバンクから選択されたメモリバンクのサブセットを含み、少なくともｎウェイのうちの少なくとも２つのウェイは異なるアクセス待ち時間を有する請求項１の装置。
【請求項３４】
ｎウェイのうちの各ウェイは異なるアクセス時間を有する請求項３３の装置。
【請求項３５】
算術機能ユニットと、
算術論理ユニットに結合されたキャッシュ制御回路と、
キャッシュ制御に結合された、独立してアクセス可能な複数のメモリバンクとより成り、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つのバンクは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成されるプロセッサ。
【請求項３６】
キャッシュ制御回路と、キャッシュ制御回路に結合され独立してアクセス可能な複数のメモリバンクとを有するプロセッサより成り、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成され、プロセッサに作動的に結合されたバスと、バスに作動的に結合されたランダムアクセスメモリとをさらに含むシステム。
【請求項３７】
概説し図１Ａに示す装置。
【請求項３８】
概説し図２に示す装置。
【請求項３９】
概説し図３Ａ、３Ｂ及び３Ｃに示す装置。
【請求項４０】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１のデータ及び第２のデータにアクセスするステップを含み、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも２つの展開バンクセットに編成されており、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクは独立してアクセス可能な複数のバンクのうちの他の選択されたバンクよりプロセッサに近く、
所定の基準が満足されたと判定されると、独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクへ独立してアクセス可能な複数のメモリバンクのうちの他の選択されたバンクから第１のデータを移行させるステップをさらに含む方法。
【請求項４１】
所定の基準は、第１のデータが第２のデータより頻繁にアクセスされると判定されると満足される請求項４０の方法。
【請求項４２】
所定の基準が満足されたと判定されると、第２のデータを独立してアクセス可能な複数のメモリバンクのうちの選択された１つのバンクから独立してアクセス可能な複数のメモリバンクのうちの他の選択されたバンクへ移行させるステップを含む請求項４１の方法。
【請求項４３】
独立してアクセス可能な複数のメモリバンクはｍ個の展開バンクセットを含むｎウェイセットアソシアティブキャッシュメモリに編成されており、各展開バンクセットは独立してアクセス可能な複数のメモリバンクから選択された少なくとも２つのメモリバンクを含む請求項４０の方法。
【請求項４４】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１のデータ及び第２のデータにアクセスするステップを含み、独立してアクセス可能な複数のメモリバンクのうちの少なくとも２つは非均等な待ち時間を有し、独立してアクセス可能な複数のメモリバンクは少なくとも複数の展開バンクセットに編成されており、独立してアクセス可能な複数のメモリバンクのうちの選択されたバンクは独立してアクセス可能な複数のバンクのうちの他の選択されたバンクよりプロセッサに近く、
第１のデータが第２のデータより頻繁にアクセスされると判定されると、独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップを含む方法。
【請求項４５】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
マルチキャストサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４６】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
限定マルチキャストサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４７】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
インクリメンタルサーチ方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４８】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、  
区分マルチキャスト方式を用いてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項４９】
プロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンク内の第１及び第２のデータをアクセスするステップは、
マルチキャスト方式、限定マルチキャスト、インクリメンタルサーチ方式及び区分マルチキャストサーチ方式を含む群から選択された方式を組み合わせてプロセッサに作動的に結合された独立してアクセス可能な複数のメモリバンクをサーチするステップを含む請求項４４の方法。
【請求項５０】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
ＬＲＵビット方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを追出すステップを含む請求項４４の方法。
【請求項５１】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
世代昇進方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを移動させるステップを含む請求項４４の方法。
【請求項５２】
世代昇進方式に基づき複数の展開バンクセットのうちの選択されたセット内のキャッシュラインを移動させるステップは、
世代昇進方式の昇進距離を選択し、
世代昇進方式の昇進トリガを選択するステップを含む請求項５１の方法。
【請求項５３】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
第１のデータをより近いメモリバンクに位置する別のデータとスワッピングするステップを含む請求項４４の方法。
【請求項５４】
中央タグ記憶装置にアクセスすることによりビクティムバンクを選択するステップを含む請求項４４の方法。
【請求項５５】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
独立してアクセス可能な複数のメモリバンクに含まれる分散タグにアクセスするステップを含む請求項４４の方法。
【請求項５６】
独立してアクセス可能な複数のメモリバンクのうちの予め選択されたバンクを介して第１のデータをプロセッサに徐々に近くなるように移行させるステップは、
中央タグ記憶装置内のパーシャルタグにアクセスし、独立してアクセス可能な複数のメモリバンクに含まれる分散タグにアクセスするステップを含む請求項４４の方法。
【国際調査報告】
2005522773.tif 000011
2005522773.tif 000012