JPH0320847A - キャッシュメモリ制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔目　次〕 ４既要 産業上の利用分野 従来の技術と発明が解決しようとする課題課題を解決す
るための手段 作用 実施例 発明の効果 〔概要〕 論理アドレスから実アドレスへの変換をページ単位で行
っている計算機システムであって、セットアソシアティ
ブ方式のキャッシュメモリを有し、該キャッシュメモリ
をアクセスする為のラインアドレスに上記ページ内アド
レスを使用する中央処理装置（ＣＰＵ）におけるキャッ
シュメモリ制御方式に関し、 キャッシュメモリの各ラインの使用効率を一様にして、
該キャッシュメモリに対するヒット率を向上させること
を目的とし、 該ページ内のラインアドレスが、上記キャッシュメモリ
のラインアドレスに、ランダムに写像するハッシュ関数
を使用して、該キャッシュメモリをアクセスするように
構威する。

〔産業上の利用分野〕

本発明は、論理アドレスから実アドレスへの変換をペー
ジ単位で行っている計算機システムであって、アドレス
変換バッファ（ＴＩ；Ｂ）　と，セットアソシアティブ
方弐のキャッシュメモリを有し、例えば、該アドレス変
換バッファ（ＴＬＢ）をアクセスする動作と、該キャッ
シュメモリのディレクトリ部をアクセスする動作とを並
列に行い、該キャッシュメモリのディレクトリ部をアク
セスする為のラインアドレスがページ内アドレスを使用
する中央処理装置（ＣＰＵ）におけるキャッシュメモリ
制御方式に関する． 従来から、ソフトウエアの作戒を容易にする為に、例え
ば、各ジョブ単位に大きな論理アドレス空間を与えてプ
ログラムを作威し、それぞれのプログラムで使用してい
る論理アドレス空間を実記憶空間に、ページ単位に写像
して、複数個のジョブを１つの実計Ｘａシステムで時分
割的に実行させる多重仮想アドレス方式の計算機システ
ムが知られている。

このような計算機システムにおいてはミジョブ毎に使用
するページ数が異なる為、ページ単位の動的アドレス変
換機構（ＤＡＴ）によって、論理アドレスが実記憶装置
の実アドレスに写像される場合、該実記憶装置に写像さ
れているページが、各仮想記憶空間の最終ページである
ことが多くなり、結果として、該実記憶装置のページ内
のデータは、その先頭が使用されて、終わりの方が空き
になっていることが多くなる動向にある。

従って、該実記憶装置のコピーを記憶しているキャッシ
ュメモリに対しては、ラインを単位とするアクセス頻度
が一様でなくなり、ページ内の先頭の方のラインデータ
は、該キャッシュメモリから追い出される頻度が、該ペ
ージ内の終わりの方に比べると高くなり、該キャッシュ
メモリのヒット率が低下する動向になる。

このような事情から、動的アドレス変換機構（ＤＡＴ）
によりページ単位にメモリが管理されていて、キャッシ
ュメモリを備えている中央処理装！　（ＣＰＵ）におい
て、該キャッシュメモリに対するアクセス環境の如何に
関わらず、ラインアドレスによってヒット率の低下が起
こることが少ないキャッシュメモリ制御方式が必要とさ
れる。

〔従来の技術と発明が解決しようとする課題〕第２図は
セットアソシアティブ方式のキャッシュメモリ制御方式
を説明する図であり、（ａ）は記憶装置の階層構造の例
を示し、（ｂ）は動的アドレス変Ｉ！！！Ｉ機構（ＤＡ
Ｔ）の例を示し、（ｃ）はセソトアソシアティブ方式の
キャッシュメモリに対する写像方式を示し、第３図は従
来のキャッシュメモリ制御方式を説明する図であって、
（ａ）はキャソシュディレクトリ部に対するアクセス方
式を示し、（ｂ）はキャッシュデータ部に対するアクセ
ス方式を示している。

先ず、前述のように、例えば、多重仮想アドレス方式を
とる計算機システムにおいては、記憶装置は第２図（ａ
）に示した階層構造をとる。

即ち、複数個の仮想アドレス空間１の各ページｌ１は、
（ｂ）図に示した動的アドレス変換機構（ＤＡＴ）によ
って、図示されている如く、主記憶装置（ＭＳ）　２の
実アドレス空間の任意のページアドレス空間に写像（こ
の写像を、フルアソシアティブという）される。

キャッシュメモリ３を備えた中央処理装置（ＣＰＵ）に
おいては、咳主記憶装置（ＭＳ）　２上の各ペジ内のデ
ータがライン単位にキャッシュメモリに写像される。

上記の動的アドレス変換機構（ＤＡＴ）は、通常、（ｂ
）図に示すように、セグメントテーブル，ベジテーブル
．主記憶ページテーブルからなっていて、中央処理装置
（ＣＰＬＩ）からのメモリアクセスで、該当ページの実
アドレスがアドレス変換パンファ（ＴＬＢ）から検索で
きないとき、当該動的アドレス変換機構（ＤＡＴ）が起
動され、論理アドレスである仮想アドレスにより、各テ
ーブルを順に検索して、現在、主記憶装置（ＭＳ）　２
に写像されている実アドレスを検索し、上記アドレス変
換バッファ（ＴＬＢ）に登録することで、以降は、該ア
ドレス変換バツファ（ＴＬＢ）をアクセスするだけで、
仮想アドレスから実アドレスを検索することができるよ
うになる。

セットアソシアティブ方式のキャッシュメモリにおいて
は、主記憶装置（ＭＳ）　２の各ページを構成している
ラインと、キャッシュメモリ３のラインとは、（ｃ）図
に示した関係にある。

即ら、主記憶装置（ＭＳ）　２のアドレス空間が複数個
のページに分割され、各ページが複数個の、例えば、ラ
インを単位とするセットに分割されている時、そのセッ
ト単位に、キャッシュメモリ３上の写像位置が決まって
いる場合を、セットアソシアティブ方式といい、前述の
動的アドレス変換機構（ＤＡＴ）のように、任意の位置
に写像される場合をフルアソシアティブ方式という。

そして、該セットアソシアテイブ方式のキャッシュメモ
リ３においては、主記憶装置（ＭＳ）　２のアドレス空
間のページ数より少ない複数個の割り当て空間（これを
、ウエイという）を設けている。

（ｃ）図の例では、主記憶装置（ＭＳ）　２の各ページ
のライン（ＡＯ，ＢＯ，〜，＾１，Ｂｌ，〜．・・・〉
が、キャッシュメモリ３上の図示されている位置に、固
定的に写像される。

このようなセットアソシアティブ方式のキャッシュメモ
リ３を有する中央処理装置（ＣＰＵ）において、該キャ
ッシュメモリ３に対するアクセス動作を第３図によって
説明する． 通常、キャッシュメモリ３のディレクトリ部関連は、（
ａ）図に示したように、該キャッシュメモリ３に対する
アクセスを高速に行う為、アドレス変換バッファ（ＴＬ
Ｂ）　３１を検索する動作と、キャッシュメモリ　３の
ディレクトリ部（タグ部ともいう）３２を検索する動作
とを同時に行うように構威されている． 従って、該キャッシュメモリ３をアクセスする為のライ
ンアドレスは、上記動的アドレス変換機構（以下、ＤＡ
Ｔという）によってもアドレスが変わらない部分である
ページ内アドレスを使用している。

先ず、図示されていないパイプラインのＴサイクルにお
いて、Ｔサイクル論理アドレスレジスタ（ＴＬＡＩＩ）
　３０にセットされた論理アドレスの内、セグメントア
ドレスとページアドレスにより、前述のアドレス変換バ
ッファ　（以下、ＴＬＢという）３１が検索され、比較
器（Ｙ）　３１０で一致が得られると論理積回路３５を
付勢する。

上記ＴＬ［ｌアクセス動作と同時に、該論理アドレスの
ページ内アドレスの一部を構威しているラインアドレス
によって、キャッシュデイレク１・９部３２が検索され
、その実アドレスと，上記ＴＬＢ　３１の検索で読み出
された実アドレスとが比較器（Ｖ）　３２０で比較され
、一致が得られると、該一致の得られたウエイを指示す
る信号■が上記論理積同路３５に送出され、Ｂサイクル
ディレク１・リマノチレジスク（ＲＤＭＲ）　３６にセ
ットされる。

（ｂ）図に示したキャッシュｙ一夕部３３は、図示して
いないパイプラインのｊｊｉ７　述の］゛サイクル〆゛
）次のＢザイクノレにおい゛（．１３サイクノレ論Ｉ里
アドレスレジスタ（ＢＬＡＲ）　３４に設定されている
論理アドレスのページ内アドレス中の上記ラインアドレ
スでアクセスされ、上記Ｂサイクルディレクトリマッチ
レジスタ（ＢＤＭＲ）　３６が指示するウエイのデータ
をキャッシュデータとして出力する．この方式では、ペ
ージ内アドレスが同じである、別ページのデータは、セ
ットに空きがある場合には、該空きのウエイに登録され
ることになり、該セットに空きがない場合には、該セッ
トに登録されているデータの中で、一番古いウエイのデ
ータが追い出されて、そこに登録されるように動作する
。

前述のように、ＤＡＴによりページ単位にメモリが管理
されている場合、該ページ内のデータ、ページの先頭か
ら使用されていく為に、該ページ内の先頭は必ず使用さ
れるが、該ページの終わりの方は空きになることが多い
ので、セットアソシア｝゛イブ方代のキャッシュメモリ
のように、セント′コ噴位゛、キ、ノシュ，メモリ上の
割当位置が決まってい、コ；場合に二、＝、キャッシュ
メモｌ１のラインによってアクセス頻度が一様でなるな
ることになる。

この為、ページ内の先頭の方のデータは、キャッシュメ
モリから追い出される頻度が、該ページ内の終わりの方
に比べて高くなり、ヒッ１・率が低くなる問題がある。

特に、前述のように、多重仮想アドレス方式をとる計算
機システムにおいては、この度合いが大きくなる為、先
頭ラインでのヒット率の低下は、該計算機システムの処
理能力を低下させる要因にもなるという問題があった。

上記の例は、アドレス変換バッファ（ＴＬＢ）　ヲアク
セスする動作と、キャッシュメモリのディレクトリ部を
アクセスする動作とを並列に行う場合について説明した
が、上記の問題点は、このケースに限定されるものでは
なく、論理アドレス呻実アドレス変換をページ単位に行
っている計算機システムに共通するものである． 本発明は上記従来の欠点に鑑み、論理アドレスから実ア
ドレスへの変換をページ単位で行っている計算機システ
ムであって、アドレス変換バッツァ（ＴＬＢ）と，セッ
トアソシアティブ方式のキャッシュメモリを有し、例え
ば、該アドレス変換バッファ（ＴＬＩＩ）をアクセスす
る動作と、該キャッシュメモリのディレクトリ部をアク
セスする動作とを並列に行い、該キャッシュメモリのデ
ィレクトリ部をアクセスする為のラインアドレスにペー
ジ内アドレスを使用する中央処理装置（ＣＰＵ）におい
て、ラインの位置によってヒット率が変わることが少く
ないキャッシュメモリ制御方式を提供することを目的と
するものである。

〔課題を解決するための手段〕

上記の問題点は下記の如くに構成されたキャッシュメモ
リ制御方式によって解決される。

論理アドレスから実アドレスの変換をページ単位で行う
計算機システムであって、アドレス変換バッファ（ＴＬ
Ｂ）　と，セットアソシアティブ方式のキャッシュメモ
リを有し、例えば、該アドレス変換バッファ（ＴＬＢ）
をアクセスする動作と、該キャッシュメモリのディレク
トリ部をアクセスする動作とを並列に行い、該キャッシ
ュメモリのディレクトリ部をアクセスする為のラインア
ドレスにページ内アドレスを使用する中央処理装置（Ｃ
Ｐυ）において、 該ページ内のラインアドレスが、上記キャッシュメモリ
のラインアドレスに、ランダムに写像するハンシュ関数
を使用して、該キャッシュメモリをアクセスするように
構戊する。

〔作用〕

即ち、本発明によれば、論理アドレスから実アドレスの
変換をページ単位で行う計算機システムであって、アド
レス変換バッファ（ＴＬｌ３）と，セットアソシアティ
ブ方式のキャッシュメモリを有し、例えば、該アドレス
変換バッファ（ＴＬｔｌ）をアクセスする動作と、該キ
ャッシュメモリのディレクトリをアクセスする動作とを
並列に行い、該キャッシュメモリのディレクトリをアク
セスする為のラインアドレスにページ内アドレスを使用
する中央処理装置（ＣＰｔｌ）において、キャッシュメ
モリに対するラインアドレスとして、例えば、ページア
ドレス，或いは、セグメントアドレスの一部で、ページ
内アドレスにハッシュ関数による変換を行ったものを、
キャッシュディレクトリ部．データ部に対するアドレス
とする。

このハッシュ関数として、該ページ内アドレスが、キャ
ッシュディレクトリ部，データ部内に、ランダムに写像
できるものであれば、特に、上記のように、ページアド
レス，或いは、セグメントアドレスに限定する必要はな
いが、該ランダム性を効果的に得ることを考えた場合、
メモリアクセス毎に、ランダムデータを発生する装置か
らのデータを使用してもよい。この場合には、余計なハ
ドウエアを必要とすることになるので、例えば、アクセ
ス毎によく変化する該ページ内アドレスに続くページア
ドレスの一部をハッシュ値として使用するのが最も効果
的である。

この結果、実際に使用されるページ内アドレスのライン
アドレスは、ディレクトリ部，データ部内のラインアド
レスにランダムに写像されることになり、ラインの使用
効率をランダム、即ら、一様にし、キャッシュメモリに
対するヒット率を向上させ、中央処理装置（ＣＰＵ）の
処理能力を向上させる効果がある。

〔実施例〕

以下本発明の実施例を図面によって詳述する。

第１図は本発明の一実施例を示した図であって、（ａｌ
）　，　（ａ２）　）は構成例を示し、（ｂ）はハッシ
ュ回路の構戒例であり、キャッシュディレクトリ部３２
，キャッシュデータ部３３に対するラインアドレスとし
て、ページ内アドレスにハッシュ値を掛けたものを使用
する手段（ハッシュ回路３８）が本発明を実施するのに
必要な手段である。尚、全図を通して同じ符号は同じ対
象物を示している。

以下、第１図によって、本発明のキャッシュメモリ制御
方式を説明する。

本発明を実施しても、キャッシュメモリの構或とか、該
キャッシュメモリに対するアクセス動作の基本的な動作
は、特に、変わることはないので省略し、ここでは、キ
ャッシュディレクトリ部３２に対するアドレスの生戒方
式を中心にして、本発明のキャッシュメモリ制御方式を
説明する。

本実施例においては、（ｂ）図に示したように、Ｔサイ
クル論理アドレスレベル（ＴＬＡＲ）　３０の４ｋバイ
トを１ページとするページ内アドレス（ビット２０〜３
１）の内の１ライン（６４バイト）を指示するアドレス
（ビット２０〜２５）に対して、該ページ内アドレスに
連続しているページアドレス（ビット１９〜１４）をハ
ッシュ値として、排他的論理和をとったアドレスを、該
キャッシュディレクトリ部３２をアクセスする為のアド
レスとするハッシュ回路３８を設け、（ａ１）図に示し
た如く、該ハッシュ回路３８の出力でキャッシュディレ
クトリ部３２をアクセスするようにする。

実際には、どのようなハッシュ値を使用してもよいが、
任意のページ内アドレスを、キャッシュディレクトリ部
３２の任意の位置に写像させようとした場合、セグメン
トアドレスのように、通常のプログラムの実行段階では
、殆ど変わらないアドレスを使用したのでは、そのラン
ダム性が得られないし、前述のように、特定のランダム
データを発生する回路を設けて、その出力データをハッ
シュ値とするようにしてもよいが、特別なランダム発生
装置を必要とすることから、経済的に、ランダムな写像
特性を得ようとすれば、該ページ内アドレスに続くペー
ジアドレスを使用するのが、最も効果的である。

このように構成することで、従来（第２図参照）、ペー
ジ内の各ラインが、例えば、上から固定的に、キャッシ
ュメモリのラインに写像されていたものが、本発明の場
合には、各ページ内の各ラインが、キャソシュメモリ上
の任意の位置に、即ち、ランダムに写像されるようにな
り、該キャノシュメモリに対するヒント率の片寄りをな
くし、平均的なヒット率の向上に寄与することができる
。

このように、本発明は、アドレス変換バッファ（ＴＬＩ
１）　と，セットアソシアティブ方式のキャッシュメモ
リを有し、例えば、該アドレス変換バッファ（ＴＬＢ）
をアクセスする動作と、該キャッシュメモリのディレク
トリをアクセスする動作とを並列に行い、該キャッシュ
メモリのディレクトリをアクセスする為のラインアドレ
スにページ内アドレスを使用する中央処理装置（ＣＰ（
１）においで、キャッシュディレクトリ部，データ部を
アクセスする為のアドレスと午で、ページ内アドレスに
、特定のハッシュ値をかけたものを使用して、該ページ
内アドレスが指示するラインアドレスがキャッシュディ
レクトリ部の任意のラインに、ランダムに写像するよう
にした所に特徴がある。

〔発明の効果〕

以上、詳細に説明したように、本発明のキャッシュメモ
リ制御方式は、論理アドレスから実アドレスへの変換を
ページ単位に行っている計′ｎａシステムであって、ア
ドレス変換バッファ（ＴＬＩＩ）と，セットアソシアテ
ィブ方式のキャッシュメモリを有し、例えば、該アドレ
ス変換バッファ（ＴＬＢ）をアクセスする動作と、該キ
ャッシュメモリのディレクトリ部をアクセスする動作と
を並列に行い、該キャッシュメモリのディレクトリ部を
アクセスする為のラインアドレスにページ内アドレスを
使用する中央処理装置（Ｃｌ）Ｕ）において、該ページ
内のラインアドレスが、上記キャッシュメモリのライン
アドレスに、ランダムに写像するハッシュ関数を使用し
て、該キャッシュメモリのディレクトリ部．データ部を
アクセスするようにしたものであるので、実際に使用さ
れるページ内アドレスのラインアドレスは、ディレクト
リ部，データ部内のラインアドレスにランダムに写像さ
れることになり、ラインの使用効率をランダム、即ち、
一様にし、キャッシュメモリに対するヒット率を向上さ
せ、中央処理装置（ＣＰＵ）の処理能力を向上させる効
果がある。

【図面の簡単な説明】

第ｌ図は本発明の一実施例を示した図，第２図はセット
アソシアティブ方式のキャッシュメモリ制御方式を説明
する図， 第３図は従来のキャッシュメモリ制御方式を説明する図
， である。 図面において、 １は仮想アドレス空間， ２は主記憶装置（ＭＳ），又は、実アドレス空間，３は
キャッシュメモリ． ３０はＴサイクル論理アドレスレジスタ（ＴＬＡＩ？）
，３１はアドレス変換バッファ（ＴＬＢ）　．３１０．
３２０は比較器（■）， ３２はキャッシュディレクトリ部，又は、ディレクトリ
部， ３３はキャッシュデータ部，又は、データ部．３４はＢ
サイクル論理アドレスレジスタ（ＢＬＡＲ）　，３５は
論理積回路， ３６はＢサイクルディレクトリマッチレジスタ（ＢＤＭ
Ｒ）， ３８はハッシュ回路， ■はウエイ指示信号， （α２） −ｊ発明の一実ウ管ダリと禾した図 第１図（での２） （ｂ） 本宅明の一突翅伊ｊＥ示した図 第１間（２の３） （Ｃ） 第２［！ｌ（イの２） （ｂ） 従釆の千ヤッシらメそり角１ｊ岬ろ式′と吉愛明す５図
第３図（１２の２）

Claims (1)

【特許請求の範囲】
1. 論理アドレスから実アドレスへの変換をページ単位で行
   っている計算機システムであって、セットアソシアティ
   ブ方式のキャッシュメモリ（３２、３３）を有し、該キ
   ャッシュメモリ（３２、３３）をアクセスする為のライ
   ンアドレスに上記ページ内アドレスを使用する中央処理
   装置（ＣＰＵ）において、該ページ内のラインアドレス
   が、上記キャッシュメモリ（３２、３３）のラインアド
   レスに、ランダムに写像するハッシュ関数を使用して、
   該キャッシュメモリをアクセスすることを特徴とするキ
   ャッシュメモリ制御方式。