JPS6324337A - キャッシュ・メモリ管理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明は仮想アドレスを用いるコンピュータ・システム
釦おいて、キャッシュ−メモリへのアクセス時間を改良
するキャッシュ・メモリ管理方式〔従来技術およびその
問題点〕 たいていの現代のコンピュータ・システムは中央処理装
置（ＣＰＵ）と主メモリを含む。ＣＰＵが命令をデコー
ドし実行してデータを処理できるスピードは、このとこ
ろ長いこと、命令およびオペランドを主メモリからＣＰ
Ｕへ転送できるスピードを越えていた。この不一致によ
って生じる問題を解決させようとして、多くのコンピュ
ータはＣＰＵと主メモリの間にキャッシュ・メモリつま
りバッファを投げている。

キャッシュ・メモリは小型の高速バッファメモリで、Ｃ
ＰＵによって近い将来用いられると思われる、主メモリ
の内容の部分を一時的に保持することに用いるものであ
る。キャッシュ・メモリの主目的は、データや命令のフ
ェッチのためのメモリ・アクセスを実行するのに必要な
時間を短縮することである。キャッシュ・メモリに置か
れた情報は主メモリに置かれたものよりずっと少ない時
間でアクセスできる。したがって、キャッシュ・メモリ
をもったＣＰＵば、命令およびオペランドがフェッチさ
れたり、記憶されたりするのを待つのにかなり短かい時
間しか消費する必安がない。

たとえば、典型的な大規模なコンビエータでは、主メモ
リは３００〜６００ナノ秒でアクセスできるが、他方、
キャッシュ・メモリからは情報は５０〜１００ナノ秒で
得ることができる。このよっな機絨では、キャッシュ・
メモリは実行速度をかなり向上させる。

キャッシュ・メモリは１つまたはそれ以上のデータ語か
らなる多くのブロックから構成され、各ブロックにはそ
のブロックが主メモリのどのブロックのコピーであるか
を一義的に決定するアドレス・タグが関連付けられてい
る。プロセッサがメモリ参照をなす毎に、キャッシュ・
メモリは自分が要求されているデータのコピーを有する
かどうかを調べる。コピーが有る場合はキャッシュ・メ
モリがデータを供給し、有しない場合は主メモリからデ
ータを検索してキャッシュ・メモリ内に格納されたデー
タ・ブロックの１つを置換え、そのデータをプロセッサ
に供給する。

キャッシュ・メモリの性能を向上させることができるひ
とつのやυ方は、主メモリの更新や多キャ７シュ整合性
（ｍｕｌｔｉｃａｃｈｅ　ｃｏｎｓｉｓｔｅｎｃｙ　）
を維持するだめのオーバーヘッドを最小にすることであ
る。

情報は通常、キャッシュから検索して、キ≠≠＃“ヒツ
ト”かどうかを連想的に判別する。しかし、大容量の連
想メモリは非常に高価でかつやや低速である。初期のキ
ャッシュ・メモリでは、ＣＰｔＪからの要求がある毎に
全ての要素が連想的に探索された。ＣＰＵに遅れないで
ついていくために必要なアクセス時間を与えるために、
キャッシュ・メモリの大きさは限定され、これによって
ヒツト率もやや低かりた。

キャッシュ・メモリはまた、各々がセット・サイズと呼
ばれるある個数のロケーションを含むセットと呼ぶ小さ
な連想メモリの複数のグループに編成することかできる
。Ｌ個のセットに分割されたサイズｍのキャッシュ・メ
モリでは、各セットに、ｓ＝ｍ／Ｌ　　個のロケーショ
ンが存在する。主メモリ内のアドレスがキャックユ・メ
モＩＪ　内にマツプされると、そのアドレスばＬ（固の
セットのいずれにも現われることが可能である。所与の
サイズのキャッシュ・メモリに対して、各セットを並列
に探索するとＬ倍だけアクセス時間を向上させることが
できる。しかし、要求された連想サーチを完了させる時
間はそれでもなお好ましくない程長い。

上述のように、キャッシュ・メモリが複数のセットを有
する場合、キャッシュ・ミスが起ったとキハ、キャッシ
ュ・メモリは、情報ブロックのうちのどれをスワップ・
アウトして主メモリから検索されている新ブロックのだ
めの領域を空けるべきかを決定しなげればならない。ど
のブロックがみ 丈ワップ・アウトされるのかを決定するために、それぞ
れのキャッシュ・メモリは各種の方式を用Ｒｅｃｅｎｔ
ｌｙ　Ｕｓｅｄ）法である。ＬＲＵ置換方式によれば、
ある特定のインデックスにある各ブロック・グループに
対して、キャッシュは、これらのブロックが最後にアク
セスされた順序をたどるいくつかのビットの状態を維持
する。ブロックの１つがアクセスされる毎に、それは最
も最近に用いられたとマークされ、それに応じて他のブ
ロックが調整される。キャッシュ・ミスが起った場合は
、主メモリから検索されているブロックのための領域を
つくるためにスワップ・アウトされるブロックは最後に
用いられた時点が最も以前であるブロックである。

利用される他の置換法は先入れ先出しくＦＩＦＯ）方式
およびランダム置換方式等である。

キャッジ−争メモリ・アーキテクチャは、仮想アドレス
を用いるシステム用のキャッシュ聯メモリをアクセスす
る際に複雑化するが、しかしその際キャッシュ−アクセ
スは２段階プロセスとなる。

すなわち、まず要求された仮想アドレスは物理アドレス
に変換され、キャッシュ・メモリがその物理アドレスに
対してサーチなされなければならない。この変換ステッ
プは通常、変換索引バッファ（ＴＬＩ：！　）によって
なされる。ＴＬＢはそれ自身、最近用いられた仮想アド
レス／物理アドレス変換を記憶する特別の型式のキャノ
ン−である。このキャッシュ・メモリ・アクセス参プロ
セスは２つの直列なステップを含む。その結果、キャッ
シュ・メモリ・アクセス時間がＴＬＢのアクセス時間だ
け長くなってしまう（もっともやり方によってはアクセ
スの多くを並列に行なうことができるのではあるが）。

この問題を解決する１つの方法は、ＣＰＵによって与え
られた仮想アドレスの物理オフセット部だけを用いてキ
ャッシュ・メモリをアクセスすることである。物理オフ
セットは仮想メモリ変換によっては変化しないから、変
換遅延が除去されることになる。しかし、このやり方に
は、キャッシュ・メモリのサイズを物理ページのナイズ
×キャッシュ・メモリのセット数に限定する欠点を有し
ている。

別の方法は仮想アドレスでアドレシングされたキャッシ
ュ・メモリを用いることである。直接仮想アドレス拳キ
ヤノンュｅメモリ・アクセスは、変換が必要ないから高
速ではあるが、いくつかの問題が生じる。すなわち、キ
ャッシュ・ミスが起った場合に主メモリへのアクセスを
行なうために、物理アドレスへの変換を扱うのにＴＬＢ
がなお必要である。また、キャッシュ・メモリ内に記憶
されたデータに関連付けられたタグとして、物理タグに
加えて仮想タグも必要となるが故に長くなる。

したがって、より多くのメモリ−ハードウェアが必要と
なシ、キャッシュ・メモリはより高価になる。

仮に、物理タグが仮想アドレスでアクセスされるキャッ
シュ・メモリ内に記憶されていないとすれば、たとえば
、２つまたはそれ以上の仮想アドレスが同じ物理アドレ
スにマクピングされ、そのためコードまたはデータを共
有するとき、しばしば反転マツピング（つまり物理アド
レスから仮想アドレスへの変換）が必要になる。もしあ
る仮想アドレスでキャッシュ・ミスが起った場合は、そ
のアドレスを物理アドレスに変換して主メモリをアクセ
スしなければならない。その際、この物理アドレスは反
転マツピングされ、キャッシュ・メモリ内にこの物理ア
ドレスに関連した他の仮想アドレスがあるか指摘するの
に用いられる。このようなアドレスがキャッシュ・メモ
リ内に存在する場合は、その名前を変更して、新しい仮
想アドレス・ロケーションに移動しなければならない。

こうして、仮想アドレスでアドレシングされるキャッシ
ュ・メモリは通常、付加的なハードウェアと費用が必要
となる。

同様の問題は、プロセスが終了したとき、そのプロセス
に関連していた物理アドレスを再使用する必要から生じ
る。仮想アドレスから物理アドレスへのマツピングが変
更される毎に、従来技術によれば、旧マツピングに対応
した全てのキャッシュ・セットからいらなくなったデー
タをパージするためのステップがとられる。

〔発明の目的〕

本発明は、ＴＬＢにおける物理アドレス−仮想アドレス
・マツピングの変化に際して、キャッシュ・アクセス時
間の増加を伴なうことになる、キャッシュ・メモリから
の失効データのパージ動作を避けることができるキャッ
シュ・メモリ管理方式を提供することを目的とする。

〔発明の概要〕

本発明の一実施例によれば、仮想／物理アドレス・マツ
ピング情報の一部として、ページ世代番号が与えられる
。命令あるいけデータのいずれに関しても、キャッシュ
・ラインがキャッシュ・メモリにロードされる毎に、イ
ンクリメントされたページ世代番号がそのキャッシュ・
ラインに対するタグ内に入れられる。キャッシュ・メモ
リ内のデータに対する全てのアクセスに対して、ＴＬＢ
内のページ世代番号が選択されたキャッシュ・ラインに
対応したページ世代番号と一致するか否か確認される。

両者が一致しない場合は、失効データを含むキャッシュ
−ラインはキャッシュ−メモリからパージされ、正しい
データブロフク（これはインクリメントされたページ世
代番号を含む）が主メモリから取出され、キャッシュ・
メモリ内に置かれる。

〔実施例の説明〕

第１図に見られるように、コンピュータ・システムは、
バス１７を介して主メモリ１３および入力／出力チャン
ネル（Ｉｌｏ）１５と連絡するＣＰＵＩＩを含む。ＣＰ
ＵＩＩは命令をフェッチし、デコードし、実行してデー
タを処理するプロセッサ１９を含む。コンピュータ・シ
ステムによって用いられる命令およびデータを全てＣＰ
ＵＩＩ内に記憶することは実際的でないから、それらの
データ、および命令は主メモリ１３に記憶し、それらが
プログラムまたはルーチンの実行中に要求されるときプ
ロセッサ１９に転送し、そのプログラムまたはルーチン
が完了した後に、主メモリ１３に戻される。

主メモリ１３へのアクセスはプロセッサ１９の動作に比
べると比較的低速である。命令またはデータが必要とさ
れた毎にプロセｙ”ｊ　１９が主メモリ・アクセスの完
了を待たなければならないとすれば、その実行速度は大
きく減少してしまうことになるだろう。プロセッサ１９
の必要とするものに、より密接に適合するアクセス時間
を得るために、バッファ・メモリつまりキャッンユ・メ
モリ２１は限定された数の命令およびデー〉を記憶する
。

キ’ｒノシュ・メモリ２１は主メモリ１３よりずっと小
さいから、より速いアクセス速度をもつように、経済的
に作り上げることができる。それにもかかわらず、キャ
ッシュ・メモリに対するアクセス時間とキャッシュ・メ
モリのサイズの間にはなおトレードオフが存在する。上
述したように、キャッシュ・メモリが大きくなれにつれ
て、キャッシュ・メモリはより高価になシまたこれへの
アクセス時間は増大する。したがって、キャッシュ・メ
モリ２１がヒツト率を上げるために非常に大きくされた
場合、主メモリ１３への参照が非常に少なくなるのだけ
れども、プロセッサのスピードは、キャッシュ・メモリ
によくヒツトするようになってもメモリ・アクセス時間
が増加することにより低下することがある。したがって
、キャッシュ・メモリへのアクセス時間をできるだけ減
少させるのが望ましい。

第１図に示されたコンピュータ・システムは仮想アドレ
スを用いて主メモリ１３にアクセスする変換器（図示せ
ず）はその仮想アドレスを、要求された命令またはデー
タを検索するに必要な物理アドレスに変換する。変換を
実現するために変換器に必要な情報は、主メモリ１３に
配置されたページ・ディレクトリＰＤＩＲに記憶される
。高速小型メモリであるＴＬＢ２３は、ＰＤＩＲによっ
て与えられた、限定された数の最近用いられた仮想アド
レス、／物理アドレス変換情報を記憶する。

ＴＬＢ２３は、それが記憶しているアドレス・マツピン
グに対応する変換ステップについてはメモリ・アクセス
の都度−々実行する必要をなくすことによって、主メモ
リ１３に対するアクセス時間を減少できる。ＴＬＢ２３
には要求された仮想アドレスが含まれていない場合、変
換器が呼出さベアドレス対をＴＬＢに戻す。ＴＬＢは将
来の使用のため現存するあるＴＬＢエントリをこれに置
換する。

本発明の方式をよシ完全に理解するためには、キャッシ
ュ・メモリ２１およびＴＬＢ２３の構造および編成の理
解が必要である。ＴＬＢ２３の構造は第２図に示される
。キャッシュ・メモリ２１の構造は第３図に示される。

第２図にみられるように、ＴＬＢ２３は仮想アドレス／
物理アドレス対を保持するロケーションのアレイを含む
。各ロケーションはインデクス３０でラベル付けされて
いる。このインデクス３ｏは仮想アドレスから導き出す
ことができる。仮想アドレス・エントリ３２は、プロセ
ラ＋ｊ１９によって用いられる仮想アドレスの仮想ペー
ジ番号である。物理アドレス・エントリ３４は、主メモ
リ（３内のアドレスの物理ページ・ロケーションすなわ
ち、仮想ページ番号を変換したものを表わす。完全な物
理アドレスは、物理ページ番号および物理オフセントか
ら成る。物理オフセントは仮想アドレスの下位部分から
直接数られる。

第３図に示されるように、キャッシュ・メモリ２１は主
メモリ１３からのデータを保持できるロケーションのア
レイを含む。各ロケーションは、ＴＬＢ２３のインデク
ス３０と同様のインデクス３１でラベル付けされ、物理
アドレス３３およびデータ３５を含む。物理アドレス３
３は、データ３５が主メモリ１３に記憶されている物理
ページ番号に対応する。

本発明によれば、変換器によって発生され、ＴＬＢ２３
に与えられた各仮想アドレス／物理アドレス・マツピン
グ情報は更にＴＬＢページ世代番号（Ｐａｇｅ　ｇｅｎ
ｅｒａｔｉｏｎ　　ｎｕｍｂｅｒ、　ＰＧＮ）を入れる
フィールド３６を含む。各キャッジ！’エントリもＴＬ
Ｂ　　ＰＧＮフィールド３６を含む。各キャッシュ・エ
ントリはキャッシュＰＧＮフィールド３７を含む。仮想
アドレス／物理アドレス・マツピングを変更する、すな
わち、現存する仮想アドレス、／物理アドレス変換対の
仮想アドレスを変更する必要がある毎に、そのマツピン
グはＰＩＯＲ内で変更され、新しい変換対のＰＧＮはＰ
ＤＩＲ内で増加され、ＴＬＢから旧変換がパージされる
。

「パージ」という用語は、主メモリの更新なしにこの時
点で、旧い変換時に対応している失効（ｓｔａｌｅ）デ
ータはなおキャッシュ・メモリ内に存在していいかもし
れない。しかし、従来行なわれていたように（これはオ
ーバヘッド時間を必要とする）キャッシュ・メモリをパ
ージするのではなく、失効データがキャッシュ・メモリ
内に留まることを許しておく。

プロセッサが次に新しい仮想アドレス／物理アドレス・
マツピングに対して仮想アドレスを与えたとき、ＴＬＢ
２３、キャッシュ２１０両者はこの仮想アドレスとそれ
ぞれ対応付けられたＴＬＢおよびキャッシュ・メモリ・
データ・ブロック内の仮想アドレス／物理アドレス・マ
ツピングを識別するためにアクセスされる。しかし、旧
変換対ＶｉＴＬＢ２３からパージされているから、ＴＬ
Ｂミスが起る。そこで新変換対が、そのインクリメント
されたＰＧＮとともに、変換器によってＰＤＩＲから検
索され、４ＬＬＢ２３に与えられる。

第４図に示すように、本発明によれば、キャッジ−・ヒ
ツトかどうか調べるため、通常の物理アドレス比較に加
えて、新たに検索されたＴＬＢエントリとキャッジ−・
ライン中のＰＧＮも比較される。この仮想アドレスに関
連したキャッシュ・ラインはインクリメントされていた
いＰＧＮを含むから、キャッシュ・ミスが生じる。これ
によって、失効キャッジ−・ラインのパージおよび主メ
モリからの新データ・ブロックの検索が生じる。

インクリメントされたＰＧＮおよび新キャッシュ・ブロ
ックに対する物理アドレス・フィールドがＴＬＢによっ
てキャッシュ・メモリに与えられ、この仮想アドレスに
関連したＴＬＢエントリおよびキャンシー・ラインの両
者を対応させる。

ページ世代番号の一義性を維持するために、仮想アドレ
スと関連したキャッシュおよびＴＬＢエントリは、１つ
のエントリに対するページ世代番号の値がラップした（
循環する）ときはいつでもフラッジ−させなければなら
ない。「フラッジ−」という用語はキャッシュ・メモリ
内のエントリの無効化を意味する。エン）　ＩＪが汚れ
て℃・れば（つまり書込みが行なわれていれば）、それ
は主メモリに書き戻される。これが起るのはマツピング
の変化よりずっと少なく、システム・オーバヘッドが低
くなる。

〔発明の効果〕

以上説明したように、本発明によればページ世代番号を
導入することにより、キャッシュ・メモリ管理上のオー
バーヘッドを低減することができる。

【図面の簡単な説明】

第１図は本発明が適用されるコンピュータ・システムの
ブロック図、第２図は本発明の一実施例で用いられるキ
ャッシュ・メモリの構成を説明する図、第３図は本発明
の一実施例で用いられるＴＬＢの構成を説明する図、第
４図は本発明の一実施例におけるページ世代番号のチェ
ククを説明する図である。 エエ：ＣＰＵ。 １３：主メモリ、 １９：プロセンサ、 ２１：キャソシュ拳メモリ ２３：ＴＬＢ ３０．３１：インデクス、 ３２：仮想アドレス・エントリ、 ３３：物理アドレス、 ３４：物理アドレス・エントリ、 ３５：データ、 ３６　：　ＴＬＢ　　ＰＧＮフィールド、３７：キヤツ
シユＰＧＮフィールド。

Claims (1)

1. 【特許請求の範囲】 仮想アドレス方式を用いたシステムのキャッシュ・メモ
   リ管理方式において、 仮想アドレス／物理アドレス変換対情報に当該変換対情
   報の更新に応答して更新される世代番号を付加し、 前記世代番号はＴＬＢおよびキャッシュ・メモリに与え
   られ、 前記キャッシュ・メモリへのアクセス時にはキャッシュ
   ・メモリから読出された世代番号と前記ＴＬＢから読出
   された世代番号の一致を確認することを特徴とするキャ
   ッシュ・メモリ管理方式。