(57)【要約】  キャッシュのパーティションを管理する方法は、優先順位の高い書き込みのための第１のポインタと、優先順位の低い書き込みのための第２のポインタとを与え、第１のポインタを使用して、優先順位の低い書き込みを区切る（delimit）。例えば、ロックされた書き込みは、アンロックされた書き込みよりも高い優先順位をもち、第１のポインタは、ロックされた書き込みに使用され、第２のポインタは、アンロックされた書き込みに使用され得る。第１のポインタは、ロックされた書き込みを行うことに応答して進まされ、したがって、この前進は、ロックされた領域と、アンロックされた領域とを定義する。第２のポインタは、アンロックされた書き込みを行うことに応答して進まされる。さらに、第２のポインタは、必要に応じて進まされ（または、後退させられ）、第２のポインタが、第１のポインタによって既にトラバースされた位置を指すのを防ぐ。したがって、第１のポインタは、アンロックされた領域を区切り、アンロックされた領域を犠牲にして、ロックされた領域が大きくなることを可能にする。【選択図】      図２
2009509274.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュメモリのパーティショニングを管理する方法であって、
キャッシュメモリへの優先順位の高い書き込みのための第１の書き込みポインタと、キャッシュメモリへの優先順位の低い書き込みのための第２の書き込みポインタとを与えることと、
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することとを含む方法。
【請求項２】
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、通常、第２の書き込みポインタが、優先順位の高い書き込みが行われたキャッシュメモリ位置を指さないようにすることを含む請求項１記載の方法。
【請求項３】
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、第１および第２の書き込みポインタが等しくなるように初期設定することと、それぞれ優先順位の高い書き込みおよび低い書き込みを行うことに応答して、第１および第２の書き込みポインタを進ませることと、必要に応じて第２の書き込みポインタをさらに進ませて、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐこととを含む請求項１記載の方法。
【請求項４】
第２の書き込みポインタが、最大ポインタ値から、第１の書き込みポインタの現在の値か、または第１の書き込みポインタの現在の値からの定義されたオフセットに対応する値にラップバックすることを可能にすることをさらに含む請求項３記載の方法。
【請求項５】
第１の書き込みポインタを、最大ポインタ値か、または最大ポインタ値からの定義されたオフセットにおいて飽和させることをさらに含む請求項３記載の方法。
【請求項６】
優先順位の高い書き込みを行うことに応答して、第１の書き込みポインタを進ませることは、第１の書き込みポインタによってトラバースされたキャッシュメモリの部分に対応するキャッシュメモリの優先順位の高い領域を定義し、第１の書き込みポインタによってトラバースされていないキャッシュメモリの部分に対応するキャッシュメモリの優先順位の低い領域を定義する請求項３記載の方法。
【請求項７】
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、第１の値に第１の書き込みポインタを初期設定することと、第１の値からオフセットした第２の値に第２の書き込みポインタを初期設定することと、キャッシュメモリへ優先順位の高い書き込みを行うことに応答して、第１の書き込みポインタを第２の書き込みポインタに向かって進ませることと、キャッシュメモリへ優先順位の低い書き込みを行うことに応答して、第２の書き込みポインタを第２の書き込みポインタに向かって進ませることと、必要に応じて第２の書き込みポインタを後退させて、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐこととを含む請求項１記載の方法。
【請求項８】
優先順位の高い書き込みを行うことに応答して、第１の書き込みポインタを進ませることは、第１のポインタによってトラバースされたキャッシュメモリの部分に対応するキャッシュメモリの優先順位の高い領域を定義し、第１のポインタによってトラバースされていないキャッシュメモリの部分に対応するキャッシュメモリの優先順位の低い領域を定義する請求項７記載の方法。
【請求項９】
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、キャッシュメモリに関して同じ方向に移動するように第１および第２の書き込みポインタを構成することと、必要に応じて第２の書き込みポインタを移動させて、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐこととを含む請求項１記載の方法。
【請求項１０】
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、キャッシュメモリに関して互いに向かって移動するように第１および第２の書き込みポインタを構成することと、必要に応じて第２の書き込みポインタを移動させて、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐこととを含む請求項１記載の方法。
【請求項１１】
第１の書き込みポインタは、ロックされた書き込みポインタを含み、第２の書き込みポインタは、アンロックされた書き込みポインタを含む請求項１記載の方法。
【請求項１２】
キャッシュメモリのパーティショニングを管理する方法であって、
第１の書き込みポインタによってアドレス指定される優先順位の高い領域と、第２の書き込みポインタによってアドレス指定される優先順位の低い領域とを含む隣接する領域に、キャッシュメモリをパーティショニングすることと、
第１の書き込みポインタを使用して、優先順位の高い領域に対して優先順位の低い領域を区切ることとを含む方法。
【請求項１３】
キャッシュメモリにおけるパーティションを管理するパーティション制御回路であって、
キャッシュメモリへ優先順位の高い書き込みを行うための第１の書き込みポインタと、キャッシュメモリへ優先順位の低い書き込みを行うための第２の書き込みポインタと、
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用するように構成されているポインタ制御装置とを含むパーティション制御回路。
【請求項１４】
パーティション制御回路は、マイクロプロセッサに関連付けられたレベル１（Level 1, L1）またはレベル２（Level 2, L2）のキャッシュメモリの少なくとも一部分を管理するためにマイクロプロセッサに含まれた統合されたパーティション制御回路を含む請求項１３記載のパーティション制御回路。
【請求項１５】
ポインタ制御装置は、通常、第２の書き込みポインタが、優先順位の高い書き込みが行われたキャッシュメモリ位置を指さないようにするように構成されている請求項１記載のパーティション制御回路。
【請求項１６】
ポインタ制御装置は、第１および第２の書き込みポインタが等しくなるように初期設定し、それぞれ優先順位の高い書き込みおよび低い書き込みを行うことに応答して、第１および第２の書き込みポインタを進ませ、必要に応じて第２の書き込みポインタをさらに進ませて、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐように構成されている請求項１３記載のパーティション制御回路。
【請求項１７】
ポインタ制御装置は、最大ポインタ値から、第１の書き込みポインタの現在の値か、または第１の書き込みポインタの現在の値からの定義されたオフセットに対応する値に、第２の書き込みポインタをラップバックするように構成されている請求項１６記載のパーティション制御回路。
【請求項１８】
ポインタ制御装置は、第１の書き込みポインタを、最大ポインタ値か、または最大ポインタ値からの定義されたオフセットにおいて飽和させるように構成されている請求項１６記載のパーティション制御回路。
【請求項１９】
ポインタ制御装置は、第１の値に第１の書き込みポインタを初期設定し、第１の値からオフセットした第２の値に第２の書き込みポインタを初期設定し、キャッシュメモリへの優先順位の高い書き込みを行うことに応答して、第１の書き込みポインタを第２の書き込みポインタに向かって進ませ、キャッシュメモリへの優先順位の低い書き込みを行うことに応答して、第２の書き込みポインタを第１の書き込みポインタへ進ませ、必要に応じて第２の書き込みポインタを後退させ、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐように構成されている請求項１３記載のパーティション制御回路。
【請求項２０】
第１および第２のポインタは、通常、キャッシュメモリに関して同じ方向に移動するように構成され、ポインタ制御装置は、必要に応じて第２の書き込みポインタを移動させ、
第１のポインタが第２の書き込みポインタを追い越すのを防ぐように構成されている請求項１３記載のパーティション制御回路。
【請求項２１】
第１および第２の書き込みポインタは、通常は、互いに向かって移動するように構成され、ポインタ制御装置は、必要に応じて書き込みポインタを移動させ、第１の書き込みポインタが第２の書き込みポインタを追い越すのを防ぐように構成されている請求項１３記載のパーティション制御回路。
【請求項２２】
第１の書き込みポインタは、ロックされた書き込みポインタを含み、第２の書き込みポインタは、アンロックされた書き込みポインタを含む請求項１３記載のパーティション制御回路。
【請求項２３】
キャッシュメモリのパーティショニングを管理するように構成されたパーティション制御回路を含むマイクロプロセッサであって、
キャッシュメモリへ優先順位の高い書き込みを行うための第１の書き込みポインタと、キャッシュメモリへ優先順位の低い書き込みを行うための第２の書き込みポインタと、
優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用するように構成されているポインタ制御装置とを含むマイクロプロセッサ。
【請求項２４】
キャッシュメモリは、セットアソシエイティブ キャッシュメモリを含み、パーティション制御回路は、セットアソシエイティブ キャッシュメモリの各セットに対する第１および第２の書き込みポインタの対を含み、パーティション制御回路が各セットにおける優先順位の高いパーティションおよび低いパーティションを管理することを可能にする請求項２３記載のマイクロプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概ね、キャッシュメモリ、とくに、優先順位の高いエントリと優先順位の低いエントリとの間におけるような、このようなメモリのパーティショニング（partitioning）を管理することに関する。
【背景技術】
【０００２】
キャッシュメモリをロックされた領域（locked region）とアンロックされた領域(unlocked region)とにパーティショニングすることは、一般的に行われていることを代表する。より具体的には、ロックされたエントリとアンロックされたエントリとの間でキャッシュセットのウェイ（way）を割り当てることが知られているが、ロックされた／アンロックされたパーティションの管理に対する従来のアプローチは、ある特定の欠点を有する。
【０００３】
例えば、キャッシュウェイをロックされた部分とアンロックされた部分とに分ける１つの方法は、キャッシュセットごとに合計で３つのポインタを使用する。３つのポインタは、キャッシュセット内の次のロックされたエントリを示すロックポインタ（locked pointer）と、キャッシュセット内の次のアンロックされたエントリを示すのに使用されるアンロックポインタ(unlocked pointer)とを含む。第３のポインタは、ロックされたエントリのパーティションの上方限度(upper limit)または上限（ceiling）を定義し、したがって、アンロックされたパーティションに対する固定された下限（floor）を設定する。すなわち、３つのポインタのアプローチでは、２つのポインタは、キャッシュセットのロックされた部分とアンロックされた部分とに対する連続的な書き込みを管理するのに使用され、第３のポインタは、キャッシュセットのロックされた部分とアンロックされた部分との間における固定された境界を示すのに使用される。
【０００４】
所与のキャッシュセットのロックされた部分とアンロックされた部分とを管理する別のアプローチは、セットの中の各キャッシュウェイにおけるキャッシュラインごとに、ロックされた／アンロックされたビットを使用することに依存する。このアプローチでは、追加のレジスタビットは、個々のキャッシュラインを、ロックされた（locked）またはアンロックされた(unlocked)としてマークを付す。
【０００５】
上述の方法は、キャッシュセットのロックされた部分およびアンロックされた部分の少なくとも限られた管理を可能にするが、これらは、レジスタをさらに使用し、ソフトウェアのオーバーヘッドを増加し、かつキャッシュの使用効率を下げるという犠牲を払って、これを行う。相当なレジスタ資源がキャッシュメモリのパーティションの管理に与えられるとき、これらの欠点は、大きいキャッシュの場合にとくに問題になる。
【発明の開示】
【発明の概要】
【０００６】
本明細書に教示されているようにキャッシュメモリのパーティショニングを管理する方法の１つの実施形態は、キャッシュメモリへの優先順位の高い書き込みのための第１の書き込みポインタと、キャッシュメモリへの優先順位の低い書き込みのための第２の書き込みポインタとを与えることと、優先順位の低い書き込みに対する区切り（delimiter）として第１の書き込みポインタを使用することとを含む。優先順位の低い書き込みに対する区切りとして第１の書き込みポインタを使用することは、通常、第２のポインタが、優先順位の高い書き込みが行われたキャッシュメモリ位置を指さないようにすることを含む。
【０００７】
第１のポインタを優先順位の高い書き込みと関連付けて、それに応じて第２のポインタの位置を制約することは、キャッシュメモリの中の隣り合う優先順位の高い領域と優先順位の低い領域との間に動的な境界線を設定する。言い換えると、継続的な優先順位の低い書き込みは、必要に応じて行われ得るが、これらの優先順位の低い書き込みによって消費されたキャッシュメモリ位置は、第１および第２のポインタを操作することによって、優先順位の高い書き込みのために再利用され得る。このように、本明細書に教示されているようなキャッシュのパーティショニングを取り入れたマイクロプロセッサにおけるソフトウェアの実行では、パーティションの境界を明確に設定および管理する必要がない。
【０００８】
例えば、マイクロプロセッサは、キャッシュセットごとに２つのポインタを与えるように構成することができ、これらのポインタの第１のものは、（優先順位の高い）ロックポインタとして示され、これらのポインタの第２のものは（優先順位の低い）アンロックポインタとして示される。マイクロプロセッサに含まれているキャッシュパーティション制御回路は、例えば、ロックポインタがキャッシュセット内の第１のアンロックされたエントリを指すように構成され、したがって、このポインタよりも下の全エントリはロックされる。さらに、次のキャッシュの書き込みがロックされた書き込みであるか、またはアンロックされた書き込みであるかに応じて、ロックポインタおよびアンロックポインタの両者は、キャッシュセット内の次の犠牲（victim）を指す。この構成では、ロックポインタは、アンロックされた領域の下限として働き、連続的なアンロックされた書き込みにより、アンロックポインタが、キャッシュセット内の最大位置に移動し、ロックポインタにラップバックする（wrap back）ように、アンロックポインタは操作され得る。
【詳細な説明】
【０００９】
図１は、本明細書に教示されているキャッシュメモリのパーティショニングを管理する方法を概括的に説明する論理的なフローチャートである。この方法は、キャッシュメモリへの優先順位の高い書き込みのための第１の書き込みポインタと、キャッシュメモリへの優先順位の低い書き込みのための第２の書き込みポインタとを与えることに基づく（ステップ100）。
【００１０】
このように定義されたポインタの対を用いて、この方法は、優先順位の低い書き込みに対する区切り（delimiter）として第１の書き込みポインタを使用する（ステップ102）。効果的に、この方法は、キャッシュメモリ内に優先順位の高い領域および優先順位の低い領域を生成し、優先順位の高いポインタは、２つの領域間の動的な境界として働く。
【００１１】
この構成は図２に示されており、キャッシュメモリ10（または、キャッシュメモリの少なくとも選択された部分)は、第１のポインタ(first pointer, PTR1）によってアドレス指定される優先順位の高い領域12と、第２のポインタ（second pointer, PTR2）によってアドレス指定される優先順位の低い領域14とを含む。ＰＴＲ１は、領域12と14との間の境界16を定義する。ＰＴＲ１を使用して、領域間の境界にマークを付すことは、優先順位の低い領域14を犠牲にして、優先順位の高い領域12が大きくなることを可能にする。したがって、図示されているメモリのレイアウトにおいて、ＰＴＲ１は、キャッシュメモリ10の下方限界（lower bound）に関連する所与の開始（最小）値から、キャッシュメモリ10の上方限界（upper bound）に関連する最終（最大）値までの値をとることができる。対照的に、ＰＴＲ２は、ＰＴＲ１の現在の値から、キャッシュメモリ10の上方限界までにわたる値をとることができる。したがって、ＰＴＲ２は、通常、優先順位の高い書き込みが行われたキャッシュメモリ位置を指さない。
【００１２】
この構成を用いて、ＰＴＲ１は、キャッシュセットを最大ポインタ値、または最大ポインタ値からの定義されたオフセット（defined offset）まで進むように構成され得る。さらに、ＰＴＲ２は、キャッシュメモリを最大ポインタ値まで進み、次に、第１のポインタの現在の値にラップバックする（wrap back）か、または第１の書き込みポインタの現在の値からの定義されたオフセットに対応する値にラップバックするように構成され得る。図２は、優先順位の低い領域14が、有効エントリと無効(初期設定されていない)エントリとを含み得ることをとくに示している。このような状況は、例えば、キャッシュ使用の最初に存在し得る。次に、図３は、繰り返される優先順位の低い書き込みにより、ＰＴＲ２が優先順位の低い領域14の各使用可能な位置を埋め、次に、ＰＴＲ１によって定義された境界16までラップバックして下り、ＰＴＲ２がキャッシュメモリの上方限度に向かって再び進むときに、以前に書き込まれた優先順位の低いエントリに上書きし始めることを示している。
【００１３】
もちろん、優先順位の低い領域14におけるこのラップアラウンド（wrap-around）の書き込みは、優先順位の高い書き込みが、優先順位の高い領域12をその上方限度まで進めていないと仮定している。より具体的には、ＰＴＲ１は、最大値(または、最大値よりも小さい値)まで進み、次に、その値で“飽和する”か、またはそうでなければ、定着する（stick）ことを可能にされ得る。ＰＴＲ１がメモリ範囲の最上位で定着すると、それより下の全ての位置はＰＴＲ２に使用不可能になり、したがって、ＰＴＲ２は、事実上、ＰＴＲ１と共にメモリ範囲の最上位に“定着”させられる。このような場合に、ポインタ管理論理は、ＰＴＲ１およびＰＴＲ２を一番上のメモリ位置のままにしておき、その一番上の位置において、追加の優先順位の高いものおよび低いものの権利を許し得る。これは、事実上、その一番上の位置に対して書き込みの優先順位が付けられておらず、単に、次の優先順位の高い書き込みおよび低い書き込みが、その一番上の位置に、続いて上書きすることを意味する。
【００１４】
上述のポインタの対の構成を用いて、マイクロプロセッサは、ロックされたエントリとアンロックされたエントリとの間でキャッシュセットのウェイを適宜に割り当てて、例えば、ハードウェアを低減し、コード効率を高め得る。(“ロックされた”書き込みは、“アンロックされた”書き込みよりも高い優先順位をもつキャッシュ書き込みのタイプとして考えられ得る。）
より具体的には、ＰＴＲ１は、ロックポインタとして働き、ＰＴＲ２は、アンロックポインタとして働き得る。ＰＴＲ２は、アンロックされた書き込みを行うことに応答して進まされ、例えば、インクリメントされ、ＰＴＲ１は、ロックされた書き込みを行うことに応答して進まされる。したがって、ＰＴＲ１は、キャッシュセット内の第１のアンロックされたエントリを指し、それより下の全エントリはロックされる。したがって、ロックされた書き込みは、ＰＴＲ１によって現在指示されているアンロックされた(または、空の)エントリに上書きし、次に、ＰＴＲ１は、次のアンロックされた位置に進む。ＰＴＲ２は、ＰＴＲ１の位置またはそれよりも上に留まるように、必要であれば、調整される。さらに、ＰＴＲ２は、最大ポインタ値まで進んだ後に、ＰＴＲ１までラップバックするようにされることができ、したがって、ＰＴＲ１の現在の位置は、アンロックされた書き込みに対する下限を設定する。
【００１５】
この方法は、キャッシュセットごとの固有の下限／上限のレジスタの必要を無くし、キャッシュラインごとのロックされたビットおよびアンロックされたビットを不要にする。さらに、この方法は、ロックされたエントリとアンロックされたエントリと間にプログラマが管理する境界をもつ必要を無くす。最後に、ロックされたウェイとアンロックされたウェイとをこのようにグループ化することは、キャッシュ内でインターリーブされたロックされたエントリとアンロックされたエントリとを管理する必要を無くす。すなわち、ソフトウェアは、キャッシュエントリごとにロックされた／アンロックされた状態のビットを管理する義務を負わされない。
【００１６】
上述のロックされた／ロックされていない書き込みを、優先順位の高いキャッシュの書き込みおよび優先順位の低いキャッシュの書き込みの一例として用いて、図４ないし７は、ポインタの対を使用して、優先順位の高い領域および優先順位の低い領域へのキャッシュセット20の動的なパーティショニングを管理する１つの実施形態を示す。
【００１７】
図４ないし７に示されているキャッシュセット20は、１６ウェイ（０ないし１５）を含み、これらは、本明細書に教示されている方法にしたがって、優先順位の高い領域と優先順位の低い領域とに動的にパーティションされ得る。より具体的には、図４ないし７は、キャッシュセット20への優先順位の高い書き込みに対してポインタ(ＰＴＲ１)を与えることと、キャッシュセット20への優先順位の低い書き込みに対してポインタ(ＰＴＲ２)を与えることと、優先順位の低い書き込みに対する区切りとしてＰＴＲ１を使用することとを示している。
【００１８】
示されている実施形態において、優先順位の低い書き込みに対する区切りとしてＰＴＲ１を使用することは、ＰＴＲ１およびＰＴＲ２が等しくなるように初期設定することと、それぞれ優先順位の高い書き込みおよび低い書き込みを行うことに応答してＰＴＲ１およびＰＴＲ２を進ませることと、必要に応じてＰＴＲ２をさらに進ませて、ＰＴＲ１がＰＴＲ２を追い越す（passing）のを防ぐこととを含む。（“追い越す（passing）”という用語は、この意味で使用されるとき、関係を示す用語（relative term）であり、ＰＴＲ２が、ＰＴＲ１によってトラバースされたポインタ値をとる（assume）または留まる（remain）ことを許されないことを単に意味することに注意すべきである。）例えば、ＰＴＲ１が、次のロックされた書き込みの犠牲として、現在、１６ウェイのキャッシュセット20の中のウェイ５を指しているとき、ＰＴＲ１は、通常、キャッシュセットのウェイ０ないし４をトラバースしており、通常、ＰＴＲ２がウェイ０ないし４を指すのを妨げられ、これらの位置のロックされたエントリに上書きするのを避けることを意味する。
【００１９】
この通常のポインタ管理方法を認識した上で、図４は、キャッシュセット20の初期状態を示しており、ＰＴＲ１およびＰＴＲ２は、キャッシュセット20のウェイ０を指すように初期設定されている。したがって、動作は、ウェイ０が高い優先順位または低い優先順位の何れかに対する次の犠牲であることから始まる。優先順位の高い書き込みを行うことなく、３つの優先順位の低い書き込みが行われると仮定して、図５は、ＰＴＲ２がウェイ３に進んだことを示しており、キャッシュセット20のウェイ０ないし１５は、キャッシュセット20の優先順位の低い領域22を事実上定義している（ウェイ０ないし２は、書き込まれたばかりのエントリを含んでいる）。ＰＴＲ１は、ウェイ０を指したままであり、これは、ロックされた書き込みに対する次の犠牲がウェイ０であり、したがって、ウェイ０に以前に書き込まれたアンロックされたエントリが上書きされることを意味していることに注意すべきである。
【００２０】
ここで、追加の優先順位の低い書き込みを行うことなく、優先順位の高い書き込みがキャッシュセット20に対して行われると仮定して、図６は、ＰＴＲ１がキャッシュセット20のウェイ１に進み、したがって、キャッシュセット20のウェイ０がキャッシュセット20の優先順位の高い領域24を事実上表わしていることを示している。この例から、読者（reader）には、優先順位の低い領域22と優先順位の高い領域24との間の境界が、ＰＴＲ１の現在の位置によって定義されることが分かるであろう。
【００２１】
ここで、さらに優先順位の低い書き込みを行うことなく、３つの追加の優先順位の高い書き込みが行われると仮定して、図７は、ＰＴＲ１がウェイ１からウェイ４へ進み、今は、優先順位の高い領域24がウェイ０からウェイ３にわたっていることを示している。ＰＴＲ１のこの前進により、より優先順位の低い領域22は、優先順位の高い書き込みによって部分的に上書きされ、ＰＴＲ２は、ＰＴＲ１と共に進まされ、ＰＴＲ１がＰＴＲ２を追い越すのを防いでいる。
【００２２】
したがって、ＰＴＲ１およびＰＴＲ２の両者は、今は、キャッシュセット20のウェイ４を指している。ＰＴＲ１およびＰＴＲ２の現在の位置は、ウェイ４が優先順位の高い書き込み(ＰＴＲ１)または優先順位の低い書き込み(ＰＴＲ２)の何れにかに対する次の犠牲であり、ウェイ０ないし３がロックされていることを意味している。したがって、この瞬間において、優先順位の高い領域12はウェイ０ないし３にわたり、優先順位の低い領域はウェイ４ないしウェイ１５にわたる。
【００２３】
この点に関して、ＰＴＲ１は、通常、自分に割り当てられたキャッシュメモリの領域を直線的に進まされ、その領域の最上位に定着するか、またはそうでなければ飽和することを許され、すなわち、ＰＴＲ１はラップアラウンドするのを妨げられ、したがって、ＰＴＲ１より下のロックされたエントリは上書きされることから保護されることに注意すべきである。もちろん、ＰＴＲ２が、ＰＴＲ１の現在の位置またはそれよりも上に留まる限り、ＰＴＲ２は、キャッシュメモリの同じ領域を進むことを許され、さらに、領域の最上位からＰＴＲ１の現在の位置へラップバックするのを許され得る。こうすることは、“ラウンドロビン”置換方式を可能にし、キャッシュメモリ領域のどの部分がＰＴＲ１の現在の位置またはそれよりも上においてＰＴＲ２のままにされても、ＰＴＲ２が繰り返し循環することに基づいて、より新しい優先順位の低い書き込みが、必要に応じてより古い優先順位の低い書き込みと置き代わる。
【００２４】
何れの場合でも、優先順位の高い書き込みを行うことに応答してＰＴＲ１を進ませることは、ＰＴＲ１によってトラバースされたキャッシュメモリセット20の部分に対応するキャッシュメモリセット20の優先順位の高い領域を定義することであることが分かる。優先順位の低い書き込みを行うことに応答して、およびＰＴＲ１を進ませることに応答して必要に応じて、ＰＴＲ２を進ませることによって、動的な境界のために、優先順位の低い領域は、優先順位の高い領域よりも上に存在することが分かる。さらに、ＰＴＲ２のラップアラウンドによる上書きは、優先順位の低い領域に対して許され、ＰＴＲ１の位置は、ＰＴＲ２に対するラップアラウンドの下限として働き、それによって、優先順位の低い書き込みが、優先順位の高いエントリに上書きするのを防ぐのが分かる。より簡潔には、ＰＴＲ２が、ＰＴＲ１によってトラバースされたメモリ位置をトラバースしないように、ＰＴＲ２の値は制御される。
【００２５】
したがって、優先順位の低い領域の上限は、キャッシュメモリセット20内で上方へ移動することができるが、ＰＴＲ１の位置によって定義されている優先順位の低い領域の下限も、上方へ移動することができる。これは、より優先順位の低い領域を犠牲にして、優先順位の高い領域が大きくなることを可能にし、優先順位の低い書き込みが、前の優先順位の高い書き込みに上書きしないことを保証する。
【００２６】
図８および９は別の実施形態を示しており、ＰＴＲ１およびＰＴＲ２は、キャッシュセット20の反対側の第１および第２の端部に初期設定され、優先順位の高い書き込みおよび低い書き込みがキャッシュセット20に対して行われると、互いに向かって移動する。より具体的には、図８に示されているように、ＰＴＲ１は、第１の値（キャッシュセット20の最下位であり得る）に初期設定され、ＰＴＲ２は、第１の値からオフセットした第２の値（キャッシュセット20の最上位であり得る）に初期設定される。次に、キャッシュセット20に優先順位の高い書き込みを行うことに応答して、ＰＴＲ１はＰＴＲ２に向かって進み、キャッシュセット20に優先順位の低い書き込みを行うことに応答して、ＰＴＲ２はＰＴＲ１に向かって進む。この構成を用いて、この方法は、必要に応じて、ＰＴＲ２を後退させ、例えば、ＰＴＲ２を“後方”へ移動させ、ＰＴＲ１がそれを追い越すのを防ぐことをさらに含む。
【００２７】
図９は、図８に関連して、３つの優先順位の高い書き込みと２つの優先順位の低い書き込みとが、キャッシュセット20に対して行われたと仮定して、ＰＴＲ１およびＰＴＲ２に対するその後の位置を示している。理解され得るように、ウェイ１５ないし１４は、今は、キャッシュセット20の優先順位の低い領域22を構成し（ウェイ１５および１４は、書き込まれたばかりの優先順位の低い値を含んでいる）、ＰＴＲ２は、優先順位の低い書き込みに対する次の犠牲として、ウェイ１３を指している。同様に、ウェイ０ないし２は、今は、キャッシュセット20の優先順位の高い領域24を構成し、ＰＴＲ１は、優先順位の高い書き込みに対する次の犠牲として、ウェイ３を指している。
【００２８】
さらに、ＰＴＲ２が、ＰＴＲ１を越えずに、ＰＴＲ１の現在の位置に向かって進むことを許され、優先順位の低いキャッシュエントリのラウンドロビン置換において、ＰＴＲ１からＰＴＲ２の開始位置へラップバックすることを許されることができることに注意すべきである。すなわち、ＰＴＲ２は、それがＰＴＲ１に出会うポイントに向かって下方に進み、次に、その値がリセットされるか、またはキャッシュセット20の最上位へラップバックされ、その結果、ＰＴＲ２が少なくともＰＴＲ１の現在の位置に向かって再び下方へ進むことを可能にされる。
【００２９】
次に、全体的に、図８および９は、所与のキャッシュセット(または、キャッシュメモリの所与の領域)に対するキャッシュポインタの対を管理する別のアプローチを示し、その対の各ポインタは、対象のキャッシュ領域の反対側の端部で初期設定され、互いに中心に向かって移動することを許されている。より具体的には、優先順位の高い書き込みを行うことに応答して、ＰＴＲ１を進ませることは、ＰＴＲ１によってトラバースされたキャッシュセット20の部分に対応するキャッシュセット20の優先順位の高い領域を定義することであることが分かる。ＰＴＲ１によってトラバースされていないキャッシュセット20の領域は、一方の端部においてＰＴＲ２の最小(または、開始)位置によって、および他方の端部においてＰＴＲ１の動的に変化する位置によって境界を付けられた優先順位の低い領域として定義される。したがって、ＰＴＲ２は、優先順位の低い書き込みに応答して必要に応じて優先順位の低い領域の中を進み、必要に応じて後退し、ＰＴＲ１がＰＴＲ２を追い越すのを防ぐ。
【００３０】
図１０は、本明細書に教示されている動的にパーティショニングする方法のさらなる拡張を示しており、キャッシュメモリ10は、優先順位の高い領域12、次に優先順位の高い領域14、および次に優先順位の高い領域30に分けられている。(言い換えると、優先順位の階層は、領域12、領域14、次に領域30である。)
ＰＴＲ１は、領域14に対する下限の役割を果たし、ＰＴＲ２は、領域30に対する下限の役割を果たしている。ＰＴＲ１は上方へ進み、したがって、領域14および30を犠牲にして、領域12を大きくし、ＰＴＲ２は上方へ進み、したがって、領域30を犠牲にして、領域14を大きくする。ＰＴＲ１およびＰＴＲ２の両者は、キャッシュメモリ10の最大または最終位置まで、あるいはその最大位置よりも低い定義されたオフセットまで進むことを可能にされ得る。対照的に、ＰＴＲ３は、最大位置に向かって上方に行き、次に、領域30に対する下限(区切り)の役割を果たすＰＴＲ２に向かって下方へラップバックすることを可能にされ得る。したがって、領域30の全てまたは一部は、領域14および／または領域12に対するエントリによる上書きを受け、領域14の全てまたは一部は、領域12に対するエントリによる上書きを受ける。
【００３１】
大まかに理解されるように、上述の方法は、キャッシュメモリの優先順位の高い領域と優先順位の低い領域との間で動的にパーティショニングすることを教示しており、２つの領域の例において、優先順位の高い書き込みを行うことに応答して第１の書き込みポインタを進ませることは、第１の書き込みポインタによってトラバースされたキャッシュメモリの部分に対応するキャッシュメモリの優先順位の高い領域を定義し、第１の書き込みポインタによってトラバースされていないキャッシュメモリの部分に対応するキャッシュメモリの優先順位の低い領域を定義する。より具体的には、第１のポインタは、優先順位の高い書き込みを追跡し（track）、ラップする（wrap）ことを許されない。したがって、優先順位の高いポインタによってトラバースされていないキャッシュメモリの領域は、優先順位の高い書き込みが行われなかったメモリ位置を表わし、したがって、優先順位の低い書き込みを行うことができる位置である。優先順位の低いポインタは、必要に応じて優先順位の低い領域の中のラップアラウンドすることができ、優先順位の高い領域が大きくなるのにしたがって、優先順位の低い領域は小さくなる。
【００３２】
図１１は、本明細書に教示されている動的なキャッシュのパーティショニングを管理する１つ以上の方法を含むように構成され得るマイクロプロセッサ40を示している。当業者は、マイクロプロセッサのアーキテクチャが多様であり、多数の回路構成が、本明細書に教示されている種々の方法を具体化するのに使用され得ることが分かるであろう。図１１のマイクロプロセッサ40は、動的なキャッシュのパーティショニングをマイクロプロセッサに取り入れる非制限的な例として存在していることが理解されるはずである。
【００３３】
示されているマイクロプロセッサ40は、命令パイプライン42を含み、命令パイプライン42は、フロントエンド ユニット44、実行ユニット46、および完成ユニット48を含んでいる。命令パイプライン42は、分岐制御回路50およびキャッシュ制御装置52に関連付けられ、キャッシュ制御装置52は、キャッシュされた命令をレベル１（Level 1, L1）の命令キャッシュ54からフロントエンド ユニット44に与え、キャッシュされたデータをデータキャッシュ56から実行ユニット46に与える。本明細書において教示されている方法に関してとくに興味のあることに、キャッシュ制御装置52は、命令キャッシュ54および／またはデータキャッシュ56におけるパーティションを管理するパーティション制御回路を含むように構成され得る。命令キャッシュ54(または、データキャッシュ56)は、セットアソシエイティブ（set associative）であっても、またはフルアソシエイティブ（fully associative）であってもよく、本明細書において教示されている方法は、何れかの構成に等しく適用され得る。
【００３４】
図１２は、レジスタ62および64の対を含む、またはこれに関連付けられたパーティション制御回路60の１つの実施形態を示している。レジスタ62および64は、ポインタ値の対(すなわち、ＰＴＲ１に対する値およびＰＴＲ２に対する値)を保持するのに使用され得る。例えば、命令キャッシュ54が１６ウェイのセットアソシエイティブ キャッシュであると仮定すると、パーティション制御回路60は、命令キャッシュ54の各セットに対してレジスタの対62および64を維持し得る。非制限的な例によって、命令キャッシュ54が６４セットを含むと仮定すると、パーティション制御回路60は、１２８ポインタ(セットごとに２ポインタ)を維持し得る。セットごとに１６ウェイの場合、各ポインタは４ビットの値を含み、それが、対応するキャッシュセット内のウェイ０ないしウェイ１５を動くことを可能にし得る。キャッシュセットごとに３つ以上の優先順位が管理されているとき、パーティション制御回路60は、各キャッシュセットに存在する優先順位と同数のポインタ、例えば、３つの優先順位＝３つのポインタ、等を維持する。
【００３５】
少なくとも１つの実施形態において、パーティション制御回路60は、キャッシュ書き込みのタイプ(例えば、高い／低い優先順位、ロックされた／アンロックされた)の機能としてＰＴＲ１またはＰＴＲ２を選択するポインタ選択器を含む。すなわち、ポインタ選択器は、書き込みのタイプを識別し、したがって、ターゲットにされたキャッシュセットに対する２つのポインタの中の正しいポインタは、書き込みを行うことに応答して進まされ得る。パーティション制御回路は、１つ以上のインクリメンタ（incrementer）をさらに含み、キャッシュセットに対して連続的な書き込みが行われたときに、新しいポインタ値を計算し、１つ以上の比較器回路をさらに含み、第１のポインタ値と第２のポインタ値とを比較し、優先順位の低いポインタが、優先順位の高い書き込みが優先順位の低い書き込みによって上書きされることになる値をとらないようにすることを保証し得る。
【００３６】
マイクロプロセッサ40のキャッシュ制御装置52内にパーティション制御回路60を統合することに加えて、当業者は、パーティション制御回路60が別の場所で物理的または機能的に実施され得ることが分かるであろう。例えば、レベル２(Level 2, L2)キャッシュは、マイクロプロセッサ40の内部にあっても、または外部にあってもよく、より多くの量のキャッシュされた命令および／またはデータを保持する二次キャッシュを与えるように構成されることができる。これに関連して、本明細書に教示されている動的なパーティション制御方法は、Ｌ２キャッシュ制御装置において実施されることができ、Ｌ２キャッシュ制御装置は、一般に、Ｌ２キャッシュメモリ配列が存在するところであればどこでも存在する。
【００３７】
もちろん、当業者は、本発明が、種々の例示的な実施形態に関連した本明細書の説明によって制限されないことも、添付の図面によって制限されないことも分かるであろう。むしろ、本発明は、請求項およびそれらと法的に同等のもの（legal equivalent）のみによって制限される。
【図面の簡単な説明】
【００３８】
【図１】本明細書に教示されているポインタの管理および結果として得られる動的なキャッシュのパーティショニングの１つの実施形態を示す論理的なフローチャート。
【図２】第１のポインタと第２のポインタとを使用して、キャッシュメモリの優先順位の高い領域と優先順位の低い領域とを、それらの間の動的な境界を用いて生成する、キャッシュメモリのブロック図。
【図３】第１のポインタと第２のポインタとを使用して、キャッシュメモリの優先順位の高い領域と優先順位の低い領域とを、それらの間の動的な境界を用いて生成する、キャッシュメモリのブロック図。
【図４】ポインタの対を使用して、キャッシュセット内の動的にパーティションされるウェイを管理することを示す、キャッシュセットのブロック図。
【図５】ポインタの対を使用して、キャッシュセット内の動的にパーティションされるウェイを管理することを示す、キャッシュセットのブロック図。
【図６】ポインタの対を使用して、キャッシュセット内の動的にパーティションされるウェイを管理することを示す、キャッシュセットのブロック図。
【図７】ポインタの対を使用して、キャッシュセット内の動的にパーティションされるウェイを管理することを示す、キャッシュセットのブロック図。
【図８】第１のポインタと第２のポインタとを使用することによって、キャッシュセットを動的にパーティショニングする別の実施形態を示すブロック図。
【図９】第１のポインタと第２のポインタとを使用することによって、キャッシュセットを動的にパーティショニングする別の実施形態を示すブロック図。
【図１０】複数のポインタを使用して、キャッシュメモリ内の異なる優先順位をもつ複数の動的に境界を付けられた領域を生成することを示すブロック図。
【図１１】本明細書に教示されている方法の１つ以上にしたがって、ポインタの対を使用することによってキャッシュメモリのパーティショニングの管理を行うように構成されたキャッシュ制御回路を組み込んだマイクロプロセッサのブロック図。
【図１２】例えば、図１１のマイクロプロセッサ内のキャッシュメモリ制御回路に含まれ得るパーティション制御回路のブロック図。
【符号の説明】
【００３９】
10・・・キャッシュメモリ、20・・・キャッシュセット、22・・・優先順位の低い領域、24・・・優先順位の高い領域、40・・・マイクロプロセッサ、42・・・命令パイプライン、44・・・フロントエンド ユニット、46・・・行ユニット、48・・・完成ユニット、50・・・分岐制御回路、52・・・キャッシュ制御装置、54・・・命令キャッシュ、56・・・データキャッシュ、60・・・パーティション制御回路、62,64・・・レジスタ。
【図１】
2009509274.tif 000003
【図２】
2009509274.tif 000004
【図３】
2009509274.tif 000005
【図４】
2009509274.tif 000006
【図５】
2009509274.tif 000007
【図６】
2009509274.tif 000008
【図７】
2009509274.tif 000009
【図８】
2009509274.tif 000010
【図９】
2009509274.tif 000011
【図１０】
2009509274.tif 000012
【図１１】
2009509274.tif 000013
【図１２】
2009509274.tif 000014
【国際調査報告】
2009509274.tif 000015
2009509274.tif 000016