JPH06208510A - アドレス変換バッファ、および論理空間割当て方法 - Google Patents

Abstract

(57)【要約】 【目的】仮想記憶方式の計算機におけるアドレス変換バ
ッファに関し、アドレス変換の効率を落とさずにハード
ウェアの物量を減少させることを目的とする。 【構成】論理ページアドレスを４つの部分に分け、第１
の部分51でアドレスされ、第２の部分52と第３の部分53
と物理ページアドレス11とからなるアドレス変換対と、
下位有効フラグ13とをエントリとして記憶する下位ＴＬ
Ｂメモリ１と、第３の部分53でアドレスされ、第４の部
分54と上位有効フラグ130 とをエントリとして記憶する
上位ＴＬＢメモリ10と、第２の部分52と下位論理アドレ
ス部分12とを比較する下位アドレス比較回路22と、第４
の部分54と上位論理アドレス部分120 とを比較する上位
アドレス比較回路220 と、ＴＬＢメモリのエントリの入
替えを制御するＴＬＢ制御回路30とを備えるように構成
する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は仮想記憶方式の計算機に
おけるアドレス変換バッファに関する。計算機が扱う論
理アドレス空間の大きさは非常に巨大になり、それに伴
いアドレス変換バッファに使うメモリの容量も多く必要
になった。アドレス変換の効率を落とさずにハードウェ
アの物量を減少させることが要求されている。

【０００２】

【従来の技術】図５にＴＬＢをもつ仮想記憶方式の計算
機のシステム構成概念図を示す。命令処理部５が仮想ア
ドレスモードで主記憶６をアクセスすると、そのときの
アドレスは論理アドレスとして扱われる。論理アドレス
の上位部分（論理ページアドレス) が、公知のＤＡＴ
（Dynamic Address Translation)機構４によってセグメ
ントテーブル、ページテーブルを索引して物理ページア
ドレスに変換される。論理アドレスの下位部分であるペ
ージ内アドレスと合わせて主記憶６の物理アドレスとな
る。このようにして一度変換したページの論理アドレス
と物理アドレスとを対にして高速の変換用メモリに写し
として記憶しておく。命令処理部５が主記憶６を次にア
クセスしたとき、変換用メモリを索引してその中にアク
セスするページのアドレス変換対があれば、それから物
理ページアドレスが得られ、アドレス変換が高速にでき
る。この変換用メモリを中心とする機構がアドレス変換
バッファである。

【０００３】図６は従来技術のアドレス変換バッファ
（以下ＴＬＢ：Translation Look-aside Buffer と記
す）の構成図である。図において、１はＴＬＢメモリ、
２はアドレス比較回路、３はＴＬＢ制御回路である。Ｔ
ＬＢメモリのエントリにおいて11は論理アドレス上位部
ＬＡＨ、12は物理ページアドレスＰＡであり11と12でア
ドレス変換対を構成し、13はアドレス変換対の有効フラ
グである。

【０００４】命令処理部５から渡される論理アドレス
は、図６に示すようにページ内アドレス（Ｔ部）50と論
理ページアドレスよりなる。論理ページアドレスを２つ
に分け、その下位部分（Ｎ部）51によってＴＬＢメモリ
１のアドレスを指定し、論理ページアドレスの上位部分
（Ｓ部）52とＤＡＴ機構によって変換された物理ページ
アドレスとを対（アドレス変換対）にしてＴＬＢメモリ
１の内容として記憶する。アドレス変換対とその有効フ
ラグの記憶部分はヒット率を高めるために複数ある場合
もあるが、簡単にするため以下にアドレス変換対が１個
である場合を例に説明する。

【０００５】ＴＬＢ索引を行う場合、論理ページアドレ
スの下位部分（Ｎ部）51がＴＬＢメモリ１のアドレスと
して入力される。ＴＬＢメモリ１は、指定されたアドレ
スに対応したエントリのデータを出力する。ＴＬＢメモ
リ１から出力されるデータとしては、アドレス変換対と
して、物理ページアドレス12（以下、ＰＡと記す）と論
理ページアドレスの上位11（以下、ＬＡＨと記す）が出
力される。更に、制御フラグとして、アドレス変換対の
有効フラグ13（‘０’＝無効、‘１’＝有効、以下、Ｖ
と記す）が出力される。

【０００６】ＴＬＢ制御回路３は、ＴＬＢメモリ１から
出力されたＬＡＨと論理ページアドレスの上位部分（Ｓ
部）52との一致判定を行い、この結果が一致し、かつＶ
ビットが‘１’の時には、ＴＬＢヒットとする。この結
果が一致しないか、Ｖビットが‘０’の時にはＴＬＢフ
ォルトとする。

【０００７】ＴＬＢヒットのときＴＬＢ制御回路３は、
ＴＬＢメモリ１から出力された物理ページアドレス12
と、ページ内アドレス50とから物理アドレスを生成して
ＤＡＴ機構に渡す。これにより主記憶がアクセスされ
る。

【０００８】ＴＬＢフォルトとなった場合、ＤＡＴ機構
によってセグメントテーブル、ページテーブルを索引し
て物理ページアドレスが得られる。これによって得られ
た新たなアドレス変換対のデータをＴＬＢメモリに書き
込み、更新する。

【０００９】ところで、命令処理部５が出力する論理ア
ドレスのビット数が増加すると、ＴＬＢメモリ１が保持
しなくてはいけない論理ページアドレス上位のビット幅
もそのまま増加する。ヒット率を向上させるためＴＬＢ
メモリのアドレス（論理ページアドレス下位部分Ｎ部）
を増やしたり、アドレス変換対を複数にしたりすれば必
要なＴＬＢメモリの容量はさらに倍加して増加する。

【００１０】

【発明が解決しようとする課題】計算機システムにおい
て命令処理部５が扱う論理アドレス空間の大きさ、すな
わち論理アドレスのビット数は増大の一途であり、最近
では従来の３２ビットから６４ビットが主流となってお
り、将来はさらに増加するものと考えられる。また近年
処理速度の向上のために、スーパスケーラプロセッサに
代表されるような複数の命令列を同時に処理する方式の
計算機システムが研究され実用化されてきている。この
ようなプロセッサにおいて、性能の向上を図る有力な手
段として、演算回路を同時に実行される演算命令の数だ
け複数個用意するのと同様に、アドレス変換の機構も同
時に実行可能なメモリアクセス命令の個数だけ持たせる
というものがあるが、このような場合、ＴＬＢの実装コ
ストが高いことは非常に問題になる。

【００１１】本発明はＴＬＢメモリを２つに分割するこ
とにより、ヒット率を下げずにハードウェア量を少なく
することができるようにしたアドレス変換バッファを実
現することを目的としている。

【００１２】

【課題を解決するための手段】図１は本発明の原理ブロ
ック図である。また、図２（Ａ）に論理アドレスとＴＬ
Ｂのエントリとの対応関係を示す。

【００１３】図において、従来技術による構成と比較し
て、ＴＬＢメモリの論理ページアドレスを格納する部分
を上位ＴＬＢメモリ10と下位ＴＬＢメモリ１とに分けて
設けており、それぞれのＴＬＢメモリを論理ページアド
レスの異なった部分（上位側はＭ／下位側はＮ）を用い
てアドレッシングする。また下位ＴＬＢメモリ１に格納
されるのは、上位ＴＬＢメモリ10へアドレスとして供給
されるＭ部を含んだＭ＋Ｓとなっている。またそれぞれ
のＴＬＢメモリが、エントリが有効か無効かを示すビッ
ト130 、13をもつ。

【００１４】さらにアドレス比較回路も上位側用20と下
位側用２をそれぞれ設け、有効ビット130 、13の値と合
わせて、ＴＬＢヒット／フォルトを判定するＴＬＢ制御
回路３０に入力する。

【００１５】ＴＬＢ制御回路３０はこれらの入力に基づ
いてＴＬＢのヒット／フォルト、の判断、ＴＬＢエント
リの入れ替えを制御する。

【００１６】

【作用】命令処理部５からＴＬＢへ論理アドレスが供給
されると、アドレスの上位側と下位側でそれぞれ別々に
ＴＬＢメモリの検索／比較を行う。

【００１７】まず上位側は、上位ＴＬＢメモリ10を論理
ページアドレスの第３の部分（Ｍ部）53でアドレスし、
格納されているデータと論理ページアドレスの第４の部
分（Ｒ部）54を比較回路20で比較する。一方下位側は、
下位ＴＬＢメモリ１を論理アドレスの第１の部分（Ｎ
部）51でアドレッシングし、読み出したデータと論理ア
ドレスの第２と第３の部分との連結（Ｓ＋Ｍ部）52，53
を比較回路２で比較する。

【００１８】図２（Ｂ）に状態一覧を示す。この図に示
すように４つの場合があり、その場合毎に、以下の処理
を行なう。 上位側が無効なエントリの場合（上位有効フラグ
‘０’）。

【００１９】ＴＬＢフォルトと判定し、ＤＡＴ機構によ
るページテーブル索引により物理ページアドレスを得
て、上位および下位のＴＬＢメモリの読出時にアドレス
したエントリの更新を行なう。

【００２０】論理ページアドレスのＭ部で上位ＴＬＢメ
モリ10をアドレスし、Ｒ部を書き込み、Ｎ部で下位ＴＬ
Ｂメモリ１をアドレスし、Ｍ部とＳ部と物理ページアド
レス（変換対）とを書き込む。

【００２１】上位側が有効なエントリ（上位有効フラ
グ‘１’）であるがアドレスは一致していない場合。 下位ＴＬＢメモリ１のすべてのエントリを無効化（パー
ジ）した後、ＴＬＢフォルトとして、と同じ処理を行
なう。

【００２２】この場合、上位ＴＬＢメモリ10にすでに存
在する有効なエントリを新しいエントリに置き換える
が、下位ＴＬＢメモリ１にはこの置き換えられて上書き
されてしまう上位エントリと組である下位エントリが残
っている。従って単に対応するエントリだけを更新して
しまうと、引き続くメモリアクセスの処理の際、上位Ｔ
ＬＢメモリの新しいエントリと、上書きされてしまった
古い上位エントリに対応していた下位ＴＬＢメモリの下
位エントリとが読みだされ、本当は正しい論理ページア
ドレスではないのに間違ってヒットと判定されてしまう
可能性がある。これを防ぐため、更新の前に下位ＴＬＢ
メモリ１のすべてのエントリを無効化する（すべてのＶ
を‘０’にする）必要があるのである。

【００２３】上位側は一致しているが、下位側は一致
していない、または無効なエントリである場合。 ＴＬＢフォルトと判定し、下位ＴＬＢメモリ１のエント
リの更新だけを行なう。

【００２４】ＴＬＢ制御回路30はＤＡＴ機構によるペー
ジテーブル索引により物理ページアドレスを得て、下位
ＴＬＢメモリ１の読出時にアドレスしたエントリの更新
を行なう。論理ページアドレスのＮ部分で下位ＴＬＢメ
モリ１をアドレスし、Ｍ部分とＳ部分と物理ページアド
レスとを書き込む。上位ＴＬＢメモリ10は更新しない。

【００２５】上位側／下位側とも有効なエントリでア
ドレスが一致している場合。 ＴＬＢがヒットしたと判定し処理を行なう。すでに述べ
たとおり、下位ＴＬＢメモリ１のエントリの一部には、
論理ページアドレスの内の上位ＴＬＢメモリ10をアドレ
スしているビット部分（Ｍ部）が含まれている。下位側
の比較回路22ではこの部分も含めて比較している。これ
によって上位側／下位側ともに有効でアドレスが一致し
ていれば、別々に選択されたＴＬＢメモリ10，１に格納
されているエントリが連続した１つの正しい論理ページ
アドレスであることが保証される。この場合、下位ＴＬ
Ｂメモリ１の物理ページアドレス部分11から読み出され
たデータを、物理ページアドレスとして主記憶へ渡す。
このようにして、ＴＬＢを矛盾なく動作させることが出
来る。

【００２６】また一般に、マルチプロセスを実行するオ
ペレーティングシステムの元では、あるプロセスの実行
が開始され、コンテクストスイッチによって実行が中断
されるまでの間に命令処理部から実行されるメモリアク
セスは、そのプロセス（ユーザプロセス）の論理空間に
対するものとシステムの論理空間に対するものの、高々
２つ程度である。すなわちある時間内では、ユーザプロ
セスの論理空間およびシステムの論理空間に対するメモ
リアクセスが集中して行なわれ、それ以外の論理空間へ
のアクセスは、あまり行なわれないという性質がある。

【００２７】従って、下位ＴＬＢメモリ１で扱う論理ア
ドレス部分に、ある程度のビット数を割り当てれば、大
部分のプロセスについて、そのプロセスの論理アドレス
について上位ＴＬＢメモリ10は一定時間内フォルトにな
らない構成となる。上位ＴＬＢメモリ10は、ユーザプロ
セスの論理空間用とシステムの論理空間用の２個程度の
エントリ、余裕を持たせても高々４個程度（これは３回
程度のコンテクストスイッチの時間、あるいは大部分の
プロセスのアクセスする論理空間の範囲の３倍程度まで
の広さの論理空間へアクセスするプロセスを考えた場合
である）のエントリがあれば、下位ＴＬＢメモリのエン
トリ数が同程度なら、ＴＬＢのヒット率は同程度であ
る。

【００２８】各プロセスに対して上位ＴＬＢメモリのエ
ントリが区別できる論理空間の領域を割り当てることに
より、上記のように上位ＴＬＢメモリのエントリの入替
えはほとんど発生しないのでＴＬＢのヒット率は同程度
に維持できる。

【００２９】

【実施例】以下、図面を参照して本発明の実施例を説明
する。図３は本発明の一実施例のブロック図である。図
１と同一のものは、同一の符号を付して示す。図におい
て、下位ＴＬＢメモリはアドレス変換対を２つもってお
り、アドレス比較回路も２つ存在する。11a,12a,13a,2a
と11b,12b,13b,2bがそれぞれ物理ページアドレス、下位
論理ページアドレス、有効フラグ、アドレス比較回路の
組をなす。その他の構成は、課題を解決するための手段
で述べたものと基本的に同じである。２つのアドレス変
換対のどちらかがヒットすればＴＬＢヒットであり、ど
ちらもヒットしなければＴＬＢフォルトである。ＴＬＢ
ヒットの場合はヒットした方の物理ページアドレス（12
a 12b のいずれか）がメモリへのアドレスとして使われ
る。

【００３０】また、ＴＬＢフォルトの場合にエントリの
入替えを行なうとき、どちらのアドレス変換対を入れ替
えるべきかを制御するためのリプレースフラグを設ける
が、公知の技術であり本発明の主旨と直接関係ないので
省略する。

【００３１】命令処理部が扱う論理アドレスは６４ビッ
トであり、その内の下位３２ビットを下位ＴＬＢメモリ
１で扱い、上位の３２ビットを上位ＴＬＢメモリ10で扱
う。すなわち、論理アドレスの下位ビットから、０〜11
をＴ部、12〜18をＮ部、19〜31をＳ部、32，33をＭ部、
36〜63をＲ部とする。

【００３２】下位ＴＬＢメモリ１のエントリには２個の
アドレス変換対を記憶することができるためＴＬＢのヒ
ット率が向上する。下位ＴＬＢメモリ１は、論理アドレ
スの下位３２ビットを扱うので論理空間にして４ギガバ
イトを扱うことになる。これだけのアドレス空間があれ
ば、大抵のプロセスは充分収容できる。従って、一度そ
のプロセスの論理空間内へのアクセスを行なった後はプ
ロセスの切替えが行なわれない限り上位ＴＬＢメモリ10
のエントリを入れ替えずにすむ。

【００３３】上位ＴＬＢメモリ10は、２ビットでアドレ
スされ、４つのエントリをもつ。従って、同時に動作す
るプロセスは、ユーザプロセスとシステム（ＯＳ）の２
つであることがほとんどであり、２つのエントリが使わ
れるだけの場合が多いはずであるが、余裕を持たせて４
個（これは３回程度のコンテクストスイッチの時間、あ
るいは大部分のプロセスがアクセスする論理空間の範囲
の３倍程度までの広さの論理空間へアクセスするプロセ
スを考えた場合である）のエントリがあれば、下位ＴＬ
Ｂメモリ１のエントリ数が同程度なら、ＴＬＢのヒット
率はほとんど同じと考えられる。

【００３４】図４に請求項３による各プロセスへの論理
アドレス空間の割当方法を示す。上記の考察に基づき、
本発明の方法では、複数のプロセスに対して上位ＴＬＢ
メモリで区別できる領域に論理空間を割り当てる。図の
Ａ，Ｂ，Ｄ，Ｚで示すように、大部分のプロセスは上位
ＴＬＢメモリで区別できる大きさの空間におさまる。Ｃ
で示したプロセスは２つ分の領域をとるが、エントリを
２つとることで対応できる。

【００３５】

【発明の効果】ページサイズを４Ｋバイトとすると、論
理アドレス中のページ内アドレスのためのビット数（図
１〜のＴ部分）は１２ビットである。ＴＬＢメモリのエ
ントリ数を１２８としたとき、アドレスビット（Ｎ部
分）は７ビットとなる。これらのことから、３２ビット
論理アドレスを採用するシステムでは、ＴＬＢメモリ１
の論理アドレスを格納するビット幅は１３ビット( ＝３
２−１２−７) で間に合うが、６４ビット論理アドレス
のシステムでは、４５ビット( ＝６４−１２−７)必要
であることがわかる。

【００３６】従来技術の構成では、４５ビット×１２８
エントリで５７６０ビットスクエア必要である。これに
対して本発明の構成では、上位側はエントリを４として
３０×４＝１２０、下位側（１３＋２）×１２８＝１９
２０の合計２０４０ビットスクエアで済むので、必要な
物量は約１／３となる。

【００３７】なお、論理アドレスが３２ビットで同一条
件の従来技術の構成（１３×１２８＝１６６４）と比較
しても、約２３％増加しているだけである。（従来方式
では約３．５倍に増加） 物理アドレス空間の大きさを６４Ｍバイトとすると、物
理ページアドレスとして２６−１２＝１４ビット、有効
ビット１ビットが必要で或ることを考慮すると、従来技
術の構成では、（４５＋１４＋１）×１２８＝７６８０
に対し、本発明の構成では、（１３＋２＋１４＋１）×
１２８＋（３０＋１）×４＝３９６４であり、約半分で
ある。アドレス変換対が複数ある場合でもこの比率はほ
ぼ同じである。

【００３８】以上説明したように、本発明によれば、ヒ
ット率を下げずにＴＬＢメモリの必要ビット数を大幅に
削減することができる。なお比較回路20，2 や判定回路
30等のため幾らか増加するが無視できる量である。

【図面の簡単な説明】

【図１】本発明の原理ブロック図である。

【図２】本発明の説明図である。

【図３】本発明の実施例のブロック図である。

【図４】論理アドレス空間の割当てを説明する図であ
る。

【図５】システム構成概念図である。

【図６】従来技術のアドレス変換バッファの構成図であ
る。

【符号の説明】

１ ＴＬＢメモリ（下位ＴＬＢメモリ） 10 上位ＴＬＢメモリ 11 物理ページアドレス 12 論理ページアドレス（下位論理ページアドレス） 13 下位有効フラグ 120 上位論理ページアドレス 130 上位有効フラグ ２ アドレス比較回路（下位アドレス比較回路） 20 上位アドレス比較回路 ３ ＴＬＢ制御回路 30 ＴＬＢ制御回路 ４ ＤＡＴ機構部 ５ 命令処理部 50 ページ内アドレス 51 論理ページアドレスの第１の部分 52 論理ページアドレスの第２の部分 53 論理ページアドレスの第３の部分 54 論理ページアドレスの第４の部分 ６ 主記憶部

Claims (3)

【特許請求の範囲】
1. 【請求項１】 命令処理部から渡される論理ページアド
   レスを４つの部分に分け、第１の部分（51）でアドレス
   され、第２の部分（52）と第３の部分（53）とを連結し
   た下位論理アドレス部分（12）とアドレス変換によって
   得られた物理ページアドレスＰＡ（11）とからなるアド
   レス変換対と、アドレス変換対が有効か無効かを示す下
   位有効フラグ（13）とをエントリとして記憶する下位Ｔ
   ＬＢメモリ（１）と、 論理ページアドレスの第３の部分（53）でアドレスさ
   れ、第４の部分（54）からなる上位論理アドレス部分
   （120)と、それが有効か無効かを示す上位有効フラグ
   （130)とをエントリとして記憶する上位ＴＬＢメモリ
   （10）と、 論理ページアドレスの第２の部分（52）と下位ＴＬＢメ
   モリ（１）から読み出されたエントリの下位論理アドレ
   ス部分（12）とを比較する下位アドレス比較回路（22）
   と、 論理ページアドレスの第４の部分（54）と上位ＴＬＢメ
   モリ（10）から読み出されたエントリの上位論理アドレ
   ス部分（120)とを比較する上位アドレス比較回路（220)
   と、 下位アドレス比較回路（22）の出力と、下位ＴＬＢメモ
   リ（１）から読み出されたエントリの下位有効フラグ
   （13）と、上位アドレス比較回路（220)の出力と、上位
   ＴＬＢメモリ（10）から読み出されたエントリの上位有
   効フラグ（130)とを入力とし、ＴＬＢヒットと判定し
   て、下位ＴＬＢメモリ（１）から読み出されたエントリ
   の物理ページアドレスを出力させ、ＴＬＢフォルトと判
   定して、ＤＡＴ機構を働かせてページテーブル検索によ
   って得た物理ページアドレスをもって、ＴＬＢメモリの
   エントリの入替えを制御するＴＬＢ制御回路（30）とを
   備えるアドレス変換バッファ。
2. 【請求項２】 ＴＬＢエントリ入替え制御回路（30）
   は、 上位ＴＬＢメモリ（10）から読み出したエントリの上位
   有効フラグ（130)が‘０’すなわち無効を示すとき、上
   位ＴＬＢメモリ（10）と下位ＴＬＢメモリ（１）のエン
   トリの更新を行い、 上位ＴＬＢメモリ（10）から読み出したエントリの上位
   有効フラグ（130)が‘１’すなわち有効を示すが、エン
   トリの上位論理アドレス部分（120)は論理ページアドレ
   スの第４の部分とは一致しないとき、下位ＴＬＢメモリ
   （１）の全てのエントリを無効にしてから上位ＴＬＢメ
   モリ（10）と下位ＴＬＢメモリ（１）のエントリの更新
   を行い、 上位ＴＬＢメモリ（10）から読み出したエントリの有効
   フラグ（130)が‘１’を示し、上位論理アドレス部分
   （120)は論理ページアドレスの第４の部分（54）と一致
   するが、下位ＴＬＢメモリ（１）から読み出したエント
   リの有効フラグ（13）が‘０’を示すかエントリの下位
   論理アドレス部分（12) は論理ページアドレスの第２の
   部分（52）と第３の部分（53）との連結とは一致しない
   とき、下位ＴＬＢメモリ（１）のエントリの更新を行
   い、 上位ＴＬＢメモリ（10）から読み出したエントリの有効
   フラグ（130)が‘１’を示し上位論理アドレス部分（13
   0)は論理ページアドレスの第１の部分と一致し、下位Ｔ
   ＬＢメモリ（１）から読み出したエントリの有効フラグ
   （13) が‘１’を示し、エントリの下位論理アドレス部
   分（12) は論理ページアドレスの第２の部分（52）と第
   ３の部分（53）との連結と一致するとき、下位ＴＬＢメ
   モリ（１）から読み出したエントリの物理ページアドレ
   ス（11）を、論理アドレスのページ内アドレス（50）と
   合わせて主記憶へアクセスするためのアドレスとして出
   力するように構成したことを特徴とする請求項１に記載
   のアドレス変換バッファ。
3. 【請求項３】 請求項１または請求項２に記載のアドレ
   ス変換バッファを備えるマルチプロセシングシステムに
   おいて、 各プロセスに上位ＴＬＢメモリで区別できる論理空間領
   域を割り当てることを特徴とする論理空間割当て方法。