(57)【要約】本発明は、キャッシュ置換法に関するものである。第１の複数のレジスタは、特定のキャッシュ・ラインと関連して互いにデイジー・チェイン状に結合される。同様に、第２の複数のレジスタが特定のキャッシュ・ラインと関連して互いにデイジー・チェイン状に結合される。第１のデイジー・チェインは、キャッシュ・ラインのフィル命令（ｆｉｌｌ ｏｒｄｅｒ）を定義し、また第２のデイジー・チェインは、キャッシュ・ラインのロック命令（ｌｏｃｋ ｏｒｄｅｒ）を定義する。
2004538536.tif 000002
【特許請求の範囲】
【請求項１】
第１シフト・レジスタと共に結合された第１の複数のラッチであって、前記第１の複数のラッチの各々はキャッシュのラインと関連付けられ、前記レジスタは前記キャッシュのラインに対しフィル命令を定義する、第１の複数のラッチと、
第２シフト・レジスタと共に結合された第２の複数のラッチであって、前記第２の複数のラッチの各々はキャッシュ・ラインと関連付けられ、前記レジスタは前記キャッシュのラインに対しロック命令を定義する、第２の複数のラッチと、
から構成されることを特徴とする装置。
【請求項２】
前記第１の複数のラッチの第１開始レジスタの出力を増幅し、前記第１の複数のラッチにおける他の各レジスタに対する入力を駆動するバッファをさらに含むことを特徴とする請求項１記載の装置。
【請求項３】
前記第１の複数のラッチにおける他の各レジスタは前記複数のラッチにおけるその後続に対する入力を駆動することを特徴とする請求項２記載の装置。
【請求項４】
前記第１の複数のラッチおよび前記第２の複数のラッチは、数において異なっていることを特徴とする請求項１記載の装置。
【請求項５】
前記第１の複数のラッチの第１開始レジスタは、キャッシュ・ラインと関連付けられ、第２キャッシュ・ラインのアドレスと最大の差異を有するアドレスは前記第２の複数のラッチの第２開始レジスタと関連付けられることを特徴とする請求項１記載の装置。
【請求項６】
第２フィル・ラインが次のロック・ラインと同じ拡がりとなるように前記第１および第２の複数のラッチを結合する結合論理をさらに含むことを特徴とする請求項５記載の装置。
【請求項７】
前記第１の複数のラッチの１つのラッチのみが３より大きいファンアウトを有することを特徴とする請求項１記載の装置。
【請求項８】
前記キャッシュは、変換索引バッファ（ｔｒａｎｓｌａｔｉｏｎ ｌｏｏｋａｓｉｄｅ ｂｕｆｆｅｒ：ＴＬＢ）であることを特徴とする請求項１記載の装置。
【請求項９】
ロックされるべきラインは、先行するロック・レジスタ・ビットにおける論理１と現在ビットの論理０との一致によって決定されること特徴とする請求項１記載の装置。
【請求項１０】
前記第１シフト・レジスタは循環バッファとして構成されることを特徴とする請求項１記載の装置。
【請求項１１】
前記第１シフト・レジスタにおける循環シフトの長さは、前記第２シフト・レジスタ中のビットを設定することにより決定されることを特徴とする請求項１０記載の装置。
【請求項１２】
各ラッチは、マスター・スレイブ・フリップフロップを含むことを特徴とする請求項１記載の装置。
【請求項１３】
連想記憶装置のアレイ（ＣＡＭ）と、
前記ＣＡＭに結合されたランダム・アクセス・メモリ （ＲＡＭ）と、
前記ＣＡＭに結合され、前記ＲＡＭ中の非ロック・ラインに対するラウンド・ロビン置換法を実行している間、前記ＣＡＭに前記ＲＡＭの特定のラインをロックさせる制御論理と、
から構成されることを特徴とするシステム。
【請求項１４】
前記制御論理は、
デイジー・チェイン状に共に結合された第１の複数のラッチであって、前記複数のラッチの各々は前記ＲＡＭのラインと関連付けられ、前記デイジー・チェインは前記ＲＡＭのラインに対しフィル命令を定義する、第１の複数のラッチと、
デイジー・チェイン状に共に結合された第２の複数のラッチであって、前記第２の複数のラッチの各レジスタはキャッシュ・ラインと関連付けられ、前記デイジー・チェインは前記キャッシュ・ラインに対しロック命令を定義する、第２の複数のラッチと、
から構成されることを特徴とする請求項１３記載のシステム。
【請求項１５】
ロック開始ラインを定義する段階と、
フィル開始ラインおよび前記ロック開始ラインからの距離を定義する段階と、
ロックが転送される時間毎にフィル・ポインタを前記フィル開始ラインにリセットする段階と、
から構成される方法。
【請求項１６】
転送されるロック・ラインに応答して、ライン１を前記フィル開始ラインにより近くに表示するためにロック・インジケータを変更する段階をさらに含むことを特徴とする請求項１５記載の方法。
【請求項１７】
前記フィル開始ラインを第１フィルに満たす段階と、
前記ロック開始ラインに最も近い非ロック・ラインを第２フィルに満たす段階と、
から構成されることを特徴とする請求項１５記載の方法。
【請求項１８】
実行時に、デジタル処理システムを稼動させる実行可能なコンピュータ・プログラムの命令を収容するコンピュータの読み取り可能な格納媒体において、
ロック・データをキャッシュ・ラインへ転送するキャッシュ内のロック・モードを初期化する段階と、
前記キャッシュ・ラインをロックする段階と、
前記キャッシュをフィル・モードに戻す段階と、
から構成される方法。
【発明の詳細な説明】
【発明の属する技術分野】
本願発明は、キャッシュ置換法に関するものである。さらに詳しくは、本願発明は結合型ラウンド・ロビン・キャッシュ置換およびキャッシュ・ラインのロッキング法に関するものである。
【従来の技術】
新しいデータ・セットがキャッシュから転送される場合、どんなデータが置き換えられるかを定義する様々な方法が存在する。直接マップ法における１つの好ましい方法は、最低使用頻度（ｌｅａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ：ＬＲＵ）方式である。最低使用頻度方式では、その名前が暗示するように、最低の使用頻度であるデータのブロックがあらゆる入力データと置き換えられる。コンピュータ・ソフトウェアの実行およびデータの使用に共通した基準となる位置を占めるために、この方式はかなり効果的なキャッシュ置換法であるように思われた。しかしながら、セット・アソシエイティブ性（ｓｅｔ ａｓｓｏｃｉａｔｉｖｉｔｙ）が増大するにつれて、ＬＲＵ方式に対する複雑さおよびオーバヘッドが、ハードウェア条件への強化要求となり、このような方式に対する魅力を減退させている。
さらに、別々のデコーダを具備しない連想記憶装置（ｃｏｎｔｅｎｔ ａｄｄｒｅｓｓａｂｌｅ ｍｅｍｏｒｙ）（ＣＡＭ）ベースのキャッシュでは、高いセット・アソシエイティブ性が達成され、どこへフィル・データ（ｆｉｌｌ ｄａｔａ）を書き込むべきかを識別することは極めて問題となってくる。使用されている１つの可能な解決法は、ラウンド・ロビン・キャッシュ置換法（ｒｏｕｎｄ ｒｏｂｉｎ ｒｅｐｌａｃｅｍｅｎｔ ｓｃｅｈｍｅ）であるが、循環シフト・レジスタが転送されるべきラインを識別するループを形成する。これは、最も古いデータをキャッシュに退避させる効果をもつが、その置換は使用頻度とは全く独立している。このように、それは極めて大量のキャッシュ・スラッシング（ｃａｃｈｅ ｔｈｒａｓｈｉｎｇ）の原因となる。
データがキャッシュから早まって追い出されるのを防止するいくつかの方法は、経路をロックするのを許容することであった。これらのシステムは、多くの細分性（ｇｒａｎｕｌａｒｉｔｙ）を提供することができなかった。例えば、双方向キャッシュでは、たとえ保持されるべきデータのブロックが比較的小さくても、キャッシュの半分がロックされるであろう。これは、しばしば非効率なキャッシュの使用となる。
【発明の概要】
第１の複数のラッチが、レジスタを形成して互いにデイジー・チェイン（いもずる）状に結合され、各ラッチは特定のキャッシュ・ラインと結合される。同様に、第２の複数のラッチが、互いにデイジー・チェイン状に結合され、各ラッチはキャッシュ・ラインと結合される。第１レジスタはキャッシュ・ラインのフィル命令（ｆｉｌｌ ｏｒｄｅｒ）を定義し、また第２レジスタはキャッシュ・ラインのロック命令（ｌｏｃｋ ｏｒｄｅｒ）を定義する。
【好適な実施例の詳細な説明】
図１は、本願発明の一実施例のブロック図である。連想記憶装置のアレイ（ＣＡＭ）１０２は、ランダム・アクセス・メモリ装置（ＲＡＭ）１０４へアドレスを指定するために用いられる。ＣＡＭ１０２およびＲＡＭ１０４の結合によって、典型的には、例えばキャッシュとなり、ある実施例において特定すればレベル・ゼロ・キャッシュとなり、あるいは別の実施例で可能であるなら変換索引バッファ（ｔｒａｎｓｌａｔｉｏｎ ｌｏｏｋａｓｉｄｅ ｂｕｆｆｅｒ：ＴＬＢ）となる。いずれの場合でも、ＣＡＭ１０２は対応する入力に応じたアドレスを含み、これは前の例ではコードまたはデータのラインであり、後の例ではページ・テーブルの入力である。ＣＡＭ入力内に収容されたデータは、いずれの例においても、「タグ」入力と呼ばれる。ラウンド・ロビンおよびロック論理１００のような制御論理装置はＣＡＭ１０２に結合される。データがＣＡＭ１０２およびＲＡＭ１０４に書き込まれたとき、すなわち、ラインがキャッシュ・フィル動作に置き換えられたとき、制御論理装置は、ＣＡＭがアドレスしたキャッシュによって使用される置換法を制御する。ＣＡＭ１０２およびＲＡＭ１０４双方の回路は、当業者によく知られた手段によって形成され得る。ＣＡＭ１０２はＣＡＭ１０２の内容参照可能な特性を介してマッチング入力（もし１つあるならば）を決定するためにアドレス指定される。もしマッチが検出されると、データは、ＲＡＭ１０４に結合されたセンス増幅器１０６からの出力として、ＲＡＭ１０４から読み出され、あるいは前述のフィル動作中にＲＡＭ１０４へデータを書き込むために用いられたのと同じ回路によって、ＲＡＭ１０４への書き込み動作が実行されてもよい。一般的に、タグ・データを格納するためにＲＡＭセルを使用するより典型的な構造に比べて、この形式のキャッシュ回路構造はより好ましい低電力特性を提供する。
転送要求を受け取ることに加えて、ラウンド・ロビンおよびロック論理１００は、ロック・クロック，ロック選択，ロック・クリア，およびラウンド・ロビン・クリアを含む多くの制御信号を受け取る。ロック・クロックは、それが表明（ａｓｓｅｒｔ）されたとき、転送要求がロックであることを示す。ロック・クロックが表明されていないとき、その転送はフィル（ｆｉｌｌ）となる。ここに用いられるように、ロックは、次の転送によって上書きされないように、ロックされるべきラインへの転送である。フィルは、通常のキャッシュ置換法の一部として自由に上書きできる転送である。ロック・クリアは、ロック・レジスタ（以下さらに説明される）をクリアし、前に転送されたロックの次の上書きを許容する。ラウンド・ロビン・クリアは、ラウンド・ロビン・レジスタ（同様に、以下さらに説明される）を予め定める値へリセットする。ロック選択信号は一組のマルチプレクサに対するモード選択として用いられ、一組のマルチプレクサはラウンド・ロビン・レジスタおよびワード線を使用可能にするロック・レジスタからの信号を選択する。
図２は、本願発明の一実施例におけるラウンド・ロビン・ロック論理のブロック図である。複数のラウンド・ロビン・ラッチ２１２，２１４，２１６，２１０は、各々キャッシュ・ラインの１つに結合される。図示された実施例では、アレイ中に３２本あると仮定される。しかしながら、さらに多くのあるいはさらに少ないライン（従って、ラッチについても）が本願発明の範囲および目的の範囲内にある。従って、３２個のラウンド・ロビン・ラッチが提供され、ラウンド・ロビン・レジスタ２００を構成する。第２の複数のラッチ２３０，２３２，２３４は、ロック・レジスタ２０２を構成するが、１つのラッチは複数のキャッシュ・ラインの各々に結合される。図示された実施例において、３１個のロック・ラッチがあり、３２本のキャッシュ・ラインのうち３１本までをロックすることを許容する。１またはそれ以上のラインがロックされるのを防ぐことによって、システムは、新しいデータをキャッシュ中に転送することを必要とするが、しかし、全ラインがロックされ、そのような転送が阻止されるデッドロック状態を回避する。ロック・ラッチは、ラウンド・ロビン・ラッチと同じように、デイジー・チェイン状に結合される。このように、ロック・レジスタは、ロック・クロックに応答して、アレイ中の指令された一連のロックをトップからボトムまで強制する。ラウンド・ロビン・レジスタ２００は、循環フィルがアレイ中のボトム・ラインから始まって最も高位の非ロック・ラインまで生起し、そしてボトムへ下方移動し、その後循環する。結合論理２０４は、ロックされたラインに上書きしないことを確保する。ある実施例では、レジスタ２００および２０４は被パルス・ラッチであり、別の実施例では、それらはマスター・スレイブ・フリップフロップである。被パルス・ラッチは、領域的には能率的であるが、プロセス・スキュー（ｐｒｏｃｅｓｓ ｓｋｅｗ）にわたって不十分な保持時間としてこのような問題に対してより敏感となる。
ロック・レジスタは、動作中のアレイのワード・ライン３１に対応する開始ラッチ２３０を含み、正の電源供給に結合された入力を有する。このように、ロック・クロックが与えられると、レジスタ２３０の出力およびそれに対応して図示されるようなデイジー・チェイン状に結合されたレジスタ２３２の入力に、高値が現れる。マスター・スレイブ・フリップフロップではなく被パルス・ラッチを用いる実施例における１つの問題点は、十分な遅延が回路に確立され、ロック・クロックが表明された際にラッチ２３０およびラッチ２３２の両方（またはチェイン中のさらに多く）が設定されるのを避けなければならない。この問題を解決するために、本願発明のパルス・ラッチの実施例では、ロック・クロックは、ロック・レジスタ中の１つのラッチがその入力値を受け取るために十分な長さの時間を与えられた短パルスであるが、しかし、意図した目標ラッチの出力に結合されたラッチが同じデータを受け取らないようにするため十分に短くする。このように、ロック・クロックの次の表明では、高値がレジスタ２３０と同様に、レジスタ２３２の出力に現れる。この手法で、３１個のロック・クロックの表明の後に、高値がロック・ラッチ２３４に到達するまで、ロック・レジスタ中を循環する。この時点において、ロック・レジスタ２０２中の３１個の全てのラッチは、ラッチ中に論理１を格納する。
ラウンド・ロビン・レジスタ２００のラッチは、ラウンド・ロビン・リセット信号の表明の後に、ラッチ２１０を除く全てのラッチがクリアにされるように結合される。ラッチ２１０は、ラウンド・ロビン開始ビットであり、ラウンド・ロビン・クリア信号に応答して設定される。この信号は、またキャッシュを初期化するために全チップ・リセットに与えられる。ラッチ２１０が設定されると、フィルがワード・ライン・ゼロから開始することが必要である。スタートアップに加えて、ラウンド・ロビン・リセット信号は、ロックが発生するのに応答して、表明される。これは、ロック・ビットがラウンド・ロビン・ビットと同時に設定される論理的にイリーガルな状態、すなわちロックされたラインがライン・フィルのための次の目標となるために選択されることがないことを確保する。ロック動作が実行されるとき、置換のためにロックできない位置にボトムを設定するこの手法は、最小の論理を必要とする。キャッシュの効率性に関する本手法との関連性は、次に述べられる。
ワード・ライン・ゼロのフィルに続いて、結合論理２０４の助けを借りて、次のフィル・ラインはロックされていない最も高位のラインに認定される。このように、ワード・ライン３１がまだロックされていない場合、ラッチ２３０の出力はゼロとなり、それはインバータ３００によって反転されてＡＮＤゲート３１２を出力「１」に設定し、さらにそれはＡＮＤゲート３１４を出力「１」にして、ＯＲゲート３１６はその後レジスタ２１２の出力を高値に駆動し、それによりワード・ライン３１を選択する。マルチプレクサ２０８はロック選択信号を使用し、どのラウンド・ロビン・レジスタまたはロック・レジスタがワード・ラインを選択するかを決定する。このように、ロック動作において、ワード・ライン（ＷＬ）選択は、ゲート３１２の出力からマルチプレクサ２０８，２０９を介して選択される。表明されるべきＷＬは、ロックの状態でフィルされるべきラインを示し、前のロック・ラッチが論理１に設定され、かつ現在が論理０であることの一致に基づく。論理から推論されるように、各ロック動作であるＷＬ表明後に、ロック・クロックが表明される。（非ロック）ライン・フィルのために、マルチプレクサ２０８は対応するラウンド・ロビン・ラッチに収容された論理１をマルチプレクサ２０９を経由してＷＬ選択ノードへ送ることによりＷＬを表明する。高信号は、次のフィルが生じるラインを示し、ポインタとしてふるまって、ラウンド・ロビン・レジスタを通して伝播する。マルチプレクサ２０９は、マルチプレクサ２０８の出力とＣＡＭマッチ信号との間で選択し、アドレスを行うためにＣＡＭを使用するキャッシュ読み取りおよび書き込み動作の間に、ＣＡＭがＷＬ選択を表明するのを許容する。別の実施例では、マッチ信号に代わって、デコーダ出力が第２の入力をマルチプレクサ２０９に提供する。
明らかなように、開始レジスタ２１０は、唯一の高いファンアウトを具備するラウンド・ロビン・レジスタのレジスタである。ここで用いられるように、”高い”ファンアウトはデバイスの出力が３つ以上の入力を駆動するものである。バッファ２０６は信号を緩衝するために用いられ、レジスタ２１０が他のラウンド・ロビン・レジスタの各々に対する入力信号を駆動するためのファンアウトを提供する。逆に、他のラウンド・ロビン・レジスタは最も近接のものへの入力を駆動する。その結果、それらは非常に小さく維持することができる。キャッシュ中のラインには２つのラッチ（被パルス・ラッチの実施例において）、ＴＬＢでは典型的には３２個、が存在し、キャッシュの場合には何千にも分配するので、これは望ましい。この小サイズになる望ましさがマスター・スレイブ・フリップフロップよりむしろ被パルス・ラッチとしてラッチ格納エレメントを有する実施例を用いる主な理由である。ファンアウトを管理することで、デバイスのサイズおよび回路の対応する電力消費を削減できる。開始レジスタはボトムにあるので、ＣＡＭおよびＲＡＭ回路のセンスおよび書き込み回路領域に対応するアレイの周囲にその領域を設けて、バッファのレイアウトを単純化できる。
図３は、８周期の期間中における転送の実行過程を示す。サイクル１において、フィル１がワード・ライン０に転送され、そのフィル・ポインタはワード・ライン３１へ位置を示すために進行する。サイクル２において、フィル２がワード・ライン３１へ転送され、そのフィル・ポインタはワード・ライン３０へ位置を示すために進行する。サイクル３において、フィル３がワード・ライン３０へ転送される。その後、サイクル４において、ロック１がロック開始ライン（ワード・ライン３１）へ転送され、フィル２を押し出し、そのフィル・ポインタがワード・ライン０へ位置を示すためにリセットされる。サイクル５において、ロック２が次のロック・ライン（ワード・ライン３０）へ転送され、フィル３を押し出し、再びそのフィル・ポインタがワード・ライン０へ位置を示すためにリセットされる。サイクル６において、フィル４が転送され、フィル１を押し出し、そのフィル・ポインタは最も高位のライン、このケースではワード・ライン２９へ位置を示すために進む。サイクル７で、フィル５はワード・ライン２９を満たす。サイクル８で、ロック３はフィル５を押し出し、そのフィル・ポインタはワード・ライン０へ位置を示すためにリセットされる。これは、単にフィルおよびロック・パターンの一例である。代わって、もしロック１，２，３が最初の３つのサイクルで成されると共に、フィル１から５が次の５つのサイクルで成されるならば、データがキャッシュから押し出されることはないであろう。このように、ソフトウェアを適切に設計することによって、各ロック後のフィル部分を再スタートするという潜在的なあらゆる不利益を取り除くことができる。例えば、あらゆるキャッシュ・ラインを満たす（ｆｉｌｌ）前に、ソフトウェアは初期時にロックされる必要のある全てのコードまたはデータをロックしてもよい。ロックを最初にすることによって、既にキャッシュへ転送されたコードでラインをロックするという潜在的な負の影響が軽減される得る。ロックすることが望ましいコードの例は、非常に迅速に応答すべきであるルーチンまたは同様のコードを処理するクリティカル割込みである。しかしながら、上記記述は本願発明の一実施例の動作を図示的に説明するものである。
図４は、本願発明の一実施例における一組の信号に対するタイミング図を示す。パルス・クロック信号４１０は、上述したパルス・ラッチの実施例で用いられる。このパルスは、隣接するラッチからの信号が次のラッチに伝播する前に低に戻るために十分短くすべきであろう。このように、ラウンド・ロビン・ラッチ（図２の２１２）の出力は、信号４１２として示される。この出力は、パルス・クロック４１０に応答して高へ遷移する。信号４１４によって示されるＯＲゲート（図１の３３６）の出力がそのＯＲゲートへの信号４１２の印加に基づいて高へ遷移する前に、パルス・クロック４１０は低でなければならない。
ある実施例において、いくつかのＣＡＭが複数のバンクを有するより大きなキャッシュを形成するために用いられ、各ＣＡＭは関連するラウンド・ロビンおよびロック論理装置を具備する。各バンクはラウンド・ロビンおよびロック手法をそのバンク内で実行し、他の全てのバンクからは独立する。
上述した明細書において、本願発明は特定の実施例に関連して説明された。しかしながら、様々な修正および変更が、添付の請求項に示されたように、本願発明のより広い精神および範囲から逸脱しないで成される。従って、本願明細書および図面は、限定的な認識ではなくむしろ解説のために成されているものとみなされる。
【図面の簡単な説明】
【図１】
本願発明の一実施例のブロック図である。
【図２】
本願発明の一実施例におけるラウンド・ロビン・ロック論理のブロック図である。
【図３】
８周期の期間中における転送の実行過程を示す。
【図４】
本願発明の一実施例における一組の信号に対するタイミング図を示す。
【図１】
2004538536.tif 000003
【図２】
2004538536.tif 000004
【図３】
2004538536.tif 000005
【図４】
2004538536.tif 000006
【国際公開パンフレット】
2004538536.tif 000007
2004538536.tif 000008
2004538536.tif 000009
2004538536.tif 000010
2004538536.tif 000011
2004538536.tif 000012
2004538536.tif 000013
2004538536.tif 000014
2004538536.tif 000015
2004538536.tif 000016
2004538536.tif 000017
2004538536.tif 000018
2004538536.tif 000019
2004538536.tif 000020
2004538536.tif 000021
【国際公開パンフレット（コレクトバージョン）】
2004538536.tif 000022
【国際調査報告】
2004538536.tif 000023
2004538536.tif 000024