JPH02500552A - 少なくとも２つの装填サイズを有するキャッシュ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 少なくとも２つの装填サイズを有するキャッシュ五笠立互 本発明は、デジタルコンピュータ及びそれらのアーキテクチャに係る。より詳細 には、本発明は、このようなコンピュータに使用されるキャッシュメモリをいっ ばいにすることに関する。

五ｎ皿 近代的なコンピュータシステムは、種々様々な性能特性を有するメモリ装置を必 要とする。ある近代的な中央処理ユニット（ＣＰＵ）にそれらを動作するための 命令及びデータを供給するためには、非常に迅速な情報検索及び送信を行なうこ とのできるメモリユニットがしばしば必要とされる。このようなメモリは、通常 、ランダムアクセスメモリ（ＲＡＭ）の形態で入手することができ、一般に「キ ャッシュ」メモリと称される。

これらのキャッシュは、一般に、データを迅速に検索できるようにするために数 千バイト程度の小さなものである。このサイズのメモリに記憶できる完全なプロ グラム又はデータベースは数個であるから、コンピュータシステムは、アクセス 及び検索時間のかかる大容量のメモリも組み込むことになる。これらのメモリに は、検索速度の遅い大きなＲＡＭや、バブルメモリや、種々の形式のディスクメ モリや、その他のメモリが含まれる。

コンピュータの動作を最適にするために一般に用いられている方法は、キャッシ ュメモリをＣＰＵに直接接続しそして別の大型のメモリユニットをキャッシュメ モリ及びＣＰＵの両方に接続することである。このようにして、キャッシュは、 ＣＰＵの動作を妨げることのない速度で必要な命令及びデータを直ちにＣＰＵに 供給することができる。主メモリは、通常、再装填データをキャッシュに供給し 、キャッシュをいっばいに保つ。

ＣＰＵが必要とするときに命令又は必要なデータ片がキャッシュにない場合には 、これを主メモリから得ることができるが、これには相当の時間がかかる。

仮想メモリマツピングを用いるキャッシュに伴う問題は、キャッシュをクリア又 はフラッシュするときに生じる。

メモリは、少なくとも２つのやり方でマツピングすることができる。その第１は 物理的なマツピングであり、命令は必要なデータが記憶された実際のメモリアド レスを参照する。第２のやり方は仮想マツピングである。この場合は、命令が仮 想、アドレスを参照し、これはデータが記憶された物理アドレスを得るためにあ る形態で変換しなければならない。仮想マツピングは主メモリを良好に利用でき るようにし、ユーザ間で連続的に仕切ることなくメモリを割り当てることができ るので、マルチプログラム環境で特に有用である。物理的マツピング及び仮想マ ツピングの両方のキャッシュがコンピュータ設計に現在使用されている。

又、キャッシュメモリの物理的な位置は、コンピュータの動作を最適にする上で 重要な役割を果たす。ＣＰＵの動作は、仮想アドレスで実行される。コンピュー タシステムが仮想マツピングキャッシュを用いる場合には、キャッシュを直接ｃ ＰＵに接続することが効果的となる。行なわればならない仮想アドレスから物理 アドレスへの変換は、キャッシュから下流に行なうことができる。

新たなプログラムを走らせるといった多数の理由で、仮想マツプキャッシュの仮 想、−物理アドレス変換マツプが変化する。

これが生じたときには、キャッシュをフラッシュ（クリア）して新たなマツプと 交換しなければならない。

キャッシュは、フラッシュされた後に、新たなデータ及び命令が再装填される。

これまでは、キャッシュがフラッシュされた後に、所与のプログラムを長時間実 行したときにデータや命令がキャッシュに供給されたのと同じ率でキャッシュが 再装填される。キャッシュは完全にいっばいであるときに最も効率的にＬ作する 。というのは、キャッシュ内のデータ又は命令を見つけるよう試みたときに、主 メモリの探索を必要とするような外れ（ミス）の結果になることが少ないからで ある。従って、フラッシュの後に一定の率でキャッシュを再装填したのでは、主 メモリを参照してそこからの応答を必要とするような多数の「外れ」が生じ、キ ャッシュの利用が不充分なものとなる。一方、キャッシュが常時再装填されるか 又は非常に高い率でリフレッシュされる場合には、明１在存在していて有用であ るデータ又は命令の上に書き込んでしまうような他の問題が生じる。

本発明の目的は、キャッシュを少なくとも２つの異なった率で装填することがで きる機構で、第１の率がキャッシュのクリア直後に使用されそしてキャッシュが ほとんど完全に装填されたときに低い率が使用されるような機構を提供すること であｍΣ１里 この目的及び他の目的は、コンピュータのキャッシュに情報を装填する本発明の 方法によって達成される。この方法は、必要な情報に対してキャッシュを探索し 、必要な情報がキャッシュに見当らないときに外れ信号を発生し、そして外れ信 号が発生されたときに必要な情報が位置されているべきキャッシュ内のデータブ ロックの有効ビットを検査するという段階を具備する。有効ビットがオンでなく 、そのブロックのデータが既に使用されたが現在はもはやないことを示す場合に は、キャッシュにＮ個のデータブロックが書き込まれる。これらのＮ個のデータ ブロックは、必要な情報を含むデータブロックを備えている。有効ビットがオン である場合には、一度にＰ個のデータブロックがキャッシュに書き込まれる。Ｐ はＮよりも小さい。これらＰ個のデータブロックは、必要な情報を含むデータブ ロックを備えている。

本発明による他の実施例は、一度にキャッシュを装填するデータブロック数を決 定するのに他の基準を用いている。

図面の簡単な説明 第１図は、キャッシュに記憶されるデータブロックの構造を示し、そして 第２図は、仮想マツプキャッシュを用いたコンピュータシステムのブロック図で ある。

１五五二五里 第１図を参照すれば、キャッシュは、一般に、データのブロックとして情報を記 憶する。ここで各々１ｏ、２０．３０．４０及び５０と番号付けされている各ブ ロックは、有効ビット、タグフィールド、プロセス識別（Ｐ　Ｉ　Ｄ）フィール ド及びデータフィールドを含む。

有効ビットは、ブロックに含まれた情報が有効であるがどうかを決定するのに用 いられる。キャッシュがフラッシュされたときには、各データブロックの全ての 有効ビットが０にセットされ、これは無効データを指示すると共に、そのブロッ クの現在の内容を上に書き込めるようにする。新たな有効データが各ブロックに 供給されるときには、有効ビットがオンにされ、そこに含まれたデータが有効で あって且つ使用可能であることを指示する。

マルチユーザのコンピュータ環境においては、各ユーザのプログラムをある時間 中走らせることができ、その後に、別のプログラムが走らされる９以下で述べる 理由で、各プログラムを独特のＰＩＤ番号で走らせることが有用である１本発明 においては、ＰＩＤ番号として６ビツトのフィールドが使用され、少なくとも６ ３の別々のプロセスを追跡することができる。

データフィールドとは、各ブロックに記憶されたデータが実際に配置されるとこ ろである。

第２図を参照すれば、キャッシュ１００は仮想マツピングされて、ＣＰＵ１２０ に接続されている。キャッシュ１００は、例えば、仮想／物理変換をキャッシュ する変換バッファである。

主メモリ１６０は、キャッシュ１００及びＣＰＵ１２０と、複数の入力／出力装 置（図示せず）とに接続される。前記したように、仮想、マツピングキャッジ、 ユは、仮想／物理のマッピングを変更するたびにフラッシュしなければならない 。これが生じるときの一例として、あるラン中のプログラムがＣＰｔ、ｌにおい て別のものに変更されるときがそうである。

本発明は、次に述べるようにハードウェアを介して仮想キャッシュの再装填を最 適に行な・う６次に述べるように、キャッシュに外れがあり、即ちキャッシュ内 の所望のデータ又は命令が見つからなかったと仮定する。一般に、これが生じる のは、探索に使用されるアドレスタグが特定のブロックを参照するが、そのブロ ックが異なったデータ又は無効データを含んでいるときである。

外れが生じたときには、本発明の第１実施例では、有効ビットがオフであるかオ ンであるかがチェックされる。これがオフである場合には、最後のフラッシュ以 来このブロックにデータが書き込まれておらず、従って、一度にＮ個のブロック に等しい高い速度でキャッシュを再装填しなければならないことを意味する。有 効ビットがオンである場合は、有用なデータが既に存在しそして有用なデータの 上に書き込みするのが時間浪費であるという仮定に基づいてキャッシュに１ブロ ツクが再装填される。

コンピュータ環境で動作するために既に分かっている空間的な位置決めの原理に よれば、データ又は命令のある所与のブロックが必要とされるときには、それに 隣接するデータ又は命令のブロックも必要とされることが多々あることが述べら れている。ここに述べる全ての実施例では、ブロックＮの数が４に等しい。それ 故、本来互いに整列される４つのブロックを用いてキャッシュが再装填される。

これらの実施例では、ブロックが４つのブロックの木来均−に整列されたグルー プとして選択され、より詳細には、「外れ」ブロックが当該グループに入る場合 には、ブロック番号○ないし３．４ないし７、等々が１つのグループとしてフェ ッチされる。例えば、ブロック２が無効であると分かった場合には、ブロックＯ ないし３がフェッチされる。

本発明の第２の実施例は、ＰＩＤ番号及び有効ビットの両方に基づくもので、多 数の異なったプログラム又はプロセスをはゾ同じ速度で走らせるようなマルチユ ーザコンピュータシステムに特に有用である。各ＰＩＤは、単一のＣＰＵにおい てはＳ゛同じ時間でランする少なくとも３２のプロセス又はプログラムの１つを 参照する独特の番号を表わしている。この実施例では、各外れの後に有効ビット がチェックされる。有効ビットがオフである場合には、第１の実施例で述べたも のと同じ状態が考えられ、即ち、キャッシュの領域が空であり、Ｎブロックの再 装填が往じる。有効ビットがオンである場合には、第２の比較が、このときには 、実行されているプロセスのＰＩＤと、読み取られている特定ブロックのＰＩＤ との間で行なわれる。２つの番号が一致しない場合には、実行しているプログラ ムがＣＰＵを最も最近制御したプログラムと異なり、そのブロックに含まれたデ ータ又は命令が有用なものではない。従って、この場合も、外れ部にＮ個のブロ ックが再装填される。有効ビットがオンでありモしてＰＩＤ番号が一致する場合 のみ、外れ部に１つのブロックが再装填される。これは、実行されているプロセ スにとってまだ有用であるデータの上に書き込むのを防止する。

更に別の実施例では、最後の外れ部のアドレスが記憶される。第２の外れが生じ たときには、２つの外れ部の位置が比較される。これらが同一の整列したブロッ クグループ、例えば、ブロック２及び３において生じた場合には、実行されてい るプログラムが新たなデータ及び命令を必要とする新たな領域へ移動したものと みなされ、外れ部にＮ個のブロックが再装填される。この状態は、前記実施例で 述べたものに加えられるものである。

更に別の実施例では、外れカウンタが設けられる。この場合も、有効ビットがオ フであり及び／又はＰＩＤ番号が一致しない場合には、外れ部にＮ個のブロック が装填される。更に、外れカウンタは、有効ビットがオンであり且つＰＩＤ番号 が一致するときに生じる全ての読み取り外れも追跡する。このカウントが予め決 定されたスレッシュホールドを越える場合には、各外れ部にＮ個のブロックが再 装填される。この場合、実行されているプログラムは、ある遷移に達して、新た な領域にジャンプし、データ及び命令の変更を必要とすると仮定する。当たり（ ヒツト）が生じると、カウンタがゼロにセットされる。この実施例では、当たり が生じるたびにカウンタを減少するようにすることもできる。この場合は、カウ ンタが第２の予め決定されたスレッシュホールドより下がったときにのみ、外れ 部に１つのブロックが装填される。

更に別の実施例では、整列されたブロックグループのどのブロックが読み取られ るかを検査する。最後の２つの実施例の場合と同様に、有効ビットがオフであり 及び／又はＰＩＤ番号が一致しない場合には、外れ部にＮ個のブロックが再装填 される。有効ビットがオンであり且つＰＩＤ番号が一致する場合でも、検査され ているブロックがその整列ブロックグループの最初のブロックである場合には、 外れ部にＮ個のブロックが再装填される。この判断は、あるプログラム及びデー タセットのトラフィックパターンに基づいて決定される。

以上、特定の実施例を参照して本発明を説明した。然し乍ら、請求の範囲に規定 した本発明の精神及び範囲から逸脱することなく、種々の変更や修正がなされ得 ることが容易に明らかであろう、又、上記説明は、解説に過ぎず、本発明をこれ に限定するものではない。

ＦＩＧ、　１ 国際調査報告

Claims (12)

【特許請求の範囲】
1. １．コンピュータのキャッシュに情報を送る方法において、必要な情報に対して キャッシュを探索し、必要な情報が見つからないときに外れ信号を発生し、上記 外れ信号が発生されるときに必要な情報が位置されているべき上記キャッシュ内 のデータブロックの有効ビットを検査し、 上記有効ビットがオンでない場合には特定の時間インターバル中に上記キャッシ ュにＮ個のデータブロックを装填し、該Ｎ個のデータブロックは、上記必要な情 報を含むデータブロックを備え、そして 上記有効ピットがオンである場合にはＰ個のデータブロックを上記キャッシュに 一度に装填し、但し、ＰはＮよりも小さく、そして上記Ｐ個のブロックは、上記 必要な情報を含むデータブロックを備えたものであることを特徴とする方法。
2. ２．コンピュータのキャッシュに情報を装填する方法において、 必要な情報に対してキャッシュを探索し、必要な情報が見つからないときに外れ 信号を発生し、上記必要な情報が上記キャッシュ内にないときにこの必要な情報 が位置されているべき上記キャッシュ内のデータブロックの有効ビットを評価し 、 上記有効ピットがオフである場合には特定の時間インターバル中に上記キャッシ ュにＮ個のデータブロックを装填し、該Ｎ個のデータブロックは、上記必要な情 報を含むデータブロックを備え、 上記必要な情報が位置されているべき上記データブロックのプロセス識別番号を 、上記コンピュータによって実行されているプロセスのプロセス識別番号と比較 し、上記プロセス識別番号が一致しない場合に指定の時間インターバル中に上記 キャッシュに上記Ｎ個のデータブロックを装填し、そして 上記プロセス識別番号が一致する場合に指定の時間インターバル中に上記キャッ シュに上記Ｐ個のデータブロックを装填し、ＰはＮよりも小さく、そしてＰは上 記必要な情報を含むデータブロックを備えていることを特徴とする方法。
3. ３．コンピュータの情報を有するキャッシュに情報を装填する方法において、 必要な情報に対してキャッシュのデータブロックを探索し、必要な情報が見つか らないときに外れ信号を発生し、発生された外れ信号のカウントを記憶し、探索 された上記データブロックの有効ピットを評価し、上記有効ピットがオフである 場合には特定の時間インターバル中に上記キャッシュにＮ個のデータブロックを 装填し、該Ｎ佃のデータブロックは、上記必要な情報を含むデータブロックを備 え、 プロセス識別番号が一致しない場合に指定の時間インターバル中に上記キャッシ ュに上記Ｎ個のデータブロックを装填し、上記カウントを第１の外れスレッシュ ホールド数と比較し、上記カウントが上記第１スレッシュホールドを越えた場合 に指定の時間インターバル中に上記キャッシュに上記Ｎ個のデータブロックを装 填し、 上記カウントが上記第１スレッシュホールドを越えないとき、及び上記有効ピッ トがオンであるときに、指定の時間インターバル中に上記キャッシュにＰ個のデ ータブロックを書き込み、ＰはＮよりも小さく、上記Ｐ個のブロックは、上記必 要な情報を含むデータブロックを備えており、そして上記データブロックの探索 により外れ信号が発生されないたびに上記カウントを減少し、そして上記カウン トが第２スレッシュホールドより低くなるまで指定の時間中に上記キャッシュに 上記Ｎ個のデータブロックを装填し続けることを特徴とする方法。
4. ４．上記の減少段階は、上記データブロックの探索により外れ信号が生じないた びに上記カウントをゼロに減少することを含む請求項３に記載の方法。
5. ５．上記キャッシュの探索により上記外れ信号が発生したときに外れの位置を記 憶し、 上記記憶された外れの位置を次に生じる外れの位置と比較し、そして 上記記憶された外れの位置及び上記次に生じる外れの位置が互いに予め設定され た距離内にある場合に指定の時間インターバル中上記キャッシュに上記Ｎ個のデ ータブロックを装填することを更に含む請求項１、２又は３に記載の方法。
6. ６．上記予め設定された距離は、同じ整列されたブロックグループである請求項 ５に記載の方法。
7. ７．コンピュータのキャッシュに情報を装填する装置において、 上記キャッシュのデータブロックの有効ビットを評価する手段と、 上記評価手段による上記有効ビットの評価に応答して指定の時間インターバル中 に異なったサイズのデータブロックを上記キャッシュに装填する手段とを備えた ことを特徴とする装置。
8. ８．上記データブロックのプロセス識別番号と、上記コンピュータによって実行 されているプロセスのプロセス識別番号とを比較する手段とを更に具備し、上記 装填手段は、上記比較手段による上記プロセス識別番号の比較に応答して上記キ ャッシュに異なったサイズのブロックを装填する請求項６に記載の装置。
9. ９．上記キャッシュは変換バッファである請求項６に記載の装置。
10. １０．Ｎが４であり、ＰがＩである請求項１、２又は３に記載の方法。
11. １１．探索された上記データブロックのプロセス識別番号と、上記コンピュータ によって実行されているプロセスのプロセス識別番号とを比較する段階を更に備 え、上記プロセス識別番号は、Ｐ個のデータブロックの性能に対する条件として 一致しなければならない請求項３に記載の方法。
12. １２．上記キャッシュの探索により上記外れ信号が発生されたときに外れの位置 を記憶し、 上記記憶された外れの位置と、次に生じる外れの位置とを比較し、そして 上記記憶された外れの位置がブロックの整列されたグループにおける第１ブロッ クである場合に指定に時間インターバル中上記キャッシュに上記Ｎ個のデータブ ロックを装填するという段階を更に備えた請求項１、２又は３に記載の方法。