JPH0417046A - アドレス変換装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、電子計算機のアドレス変換装置に係わる。

〔従来の技術〕

仮想記憶機能を有する電子言］算機システムの利用者は
、システムに実装されている主メモリよりも多くのメモ
リが備わっているかのように計算機を扱うことができる
。このようなシステムでは、動作中に必要に応じてメモ
リの割当てが行われ、そのメモリには適切なアドレスが
割り振られる。

そのため、プログラム上のアドレス（これを論理アドレ
ス、または仮想アドレスという）を、実装されている・
メモリのアドレス（これを物理アドレス、または実アド
レスという）に変換する必要がある。アドレス変換装置
とは、このように論理アドレスを物理アドレスに変換す
る装置である。すなわち、アドレス変換装置の入力は論
理アドレスであり、出力は物理アドレスである。

アドレス変換装置は、マイクロプロセッサに内蔵される
場合も多い。この例として、日立製作所３２ピッ１−マ
イクロプロセッサｒＨ３２／’２００Ｊが挙げられる。

ｒＨ３２／２００オペレーションアーキテクチャマニュ
アル」の第４章「メモリ管理機構」には、アドレス変換
の仕様が記載゛されている。

このマニュアルによるとＨ３２／２００の論理アドレス
は３２ビツトである。そして、論理アドレスはアドレス
変換のため第２図に示すように、半空間指定子２０１．
セクションインデックス２０２、ページインデックス２
０３．オフセラ１〜２０４の４つのフィールドに分割さ
れる。半空間指定子２０１がアドレス変換に及ぼす作用
については本発明の本質と無関係であるので、ここでは
省略する。セクションインデックス２０２．ページイン
デックス２０３の各フィールドをインデックスとして主
メモリに記憶されているテーブルをアクセスすることに
よって、論理アドレスが物理アドレスに変換される。セ
クションインデックス２０２は９ビツト、ページインデ
ックス２０３は１０ビツト、オフセット２０４は１２ビ
ツトである。

アドレス変換の概念を第３図に示した。セクションテー
ブル３０２は、セクションテーブルベース３０１をベー
スとし、セクションインデックス２０２をインデックス
としてアクセスされるテーブルである。セクションテー
ブル３０２の各エントリには、ページテーブルベース３
０６、すなわちページテーブル３０３のベースアドレス
が記憶されている。ページテーブル３０３は、ページテ
ーブルベース３０６をベースとし、ページインデックス
２０３をインデックスとしてアクセスされるテーブルで
ある。ページテーブル３０３の各エントリには、ページ
フレーム番号３０８が記憶されている。物理メモリ３０
９は、ページと呼ばれるブロックに分割されており、ペ
ージの先頭の物理アドレスがページフレーム番号である
。また、最近のアドレス変換の入出力対、すなわち論理
アドレスと物理アドレスの対を記憶しているＴＬＢ（Ｔ
ｒａｎｓｌａｔｉｏｎ　Ｌｏｏｋａｓｉｄｅ　Ｂｕｆｆ
ｅｒ）　３１０がある。

入力された論理アドレスがＴＬＢ３１０に登録されてい
る場合は、主メモリ上のテーブルにアクセスせずに物理
アドレスが求められるので、アドレス変換を高速に行う
ことが可能である。

アドレス変換の手順は以下の通りである。

まず、入力された論理アドレスを基にＴＬＢ３１０を検
索する。ＴＬ’Ｂ５１０には、論理ページ番号３１１と
その論理ページ番号に対応するページフレーム番号３１
２との対が記憶されている（論理ページ番号は、論理ア
ドレスからオフセットを取り除いた部分である）。物理
アドレスは、ページフレーム番号３１２とオフセラ１−
２０４の和なので、入力された論理アドレスがＴ　Ｌ　
Ｂ’３１０に登録されていれば、直ちに対応する物理ア
ドレスを求めることができる。

入力された論理アドレスがＴＬＢ　３１０に登録されて
いない場合は、主メモリ上のテーブルをアクセスして物
理アドレスを求める必要がある。まず、セクションテー
ブルベース３０１をベースとし、セクションインデック
ス２０２をインデックスとしてセクションテーブル３０
２をアクセスすると、ページテーブルベース３０６が求
められる。

次に、このページテーブルベース３．０６をベースとし
、ページインデックス２０３をインデックスとしてペー
ジテーブル３０３をアクセスすると、ページフレーム番
号３０８が求められる。ページフレーム番号３０８は該
ページの先頭の物理アドレスなので、この値とオフセラ
Ｉ−２０４を加算して、目的の物理アドレスが求められ
る。以上でアドレス変換が終了する。また、後のアドレ
ス変換に備えるため、入力された論理ページ番号と求め
られたページフレーム番号との対がＴＬＢ３１０に登録
される。

〔発明が解決しようとする課題〕

従来の技術をそのままアドレス幅が大きい場合に適用す
ると、変換テーブルが多段階となり変換速度が低下する
、という問題がある。以下、多段階にしない場合に生じ
る問題点について説明する。

分割された論理アドレスの各フィールドのうち、オフセ
ット２０４は物理アドレスを求める際にページフレーム
番号に加算される数値である。したがって、オフセット
２０４のフィールドの幅はぺ−ジの大きさを表している
（以下、オフセラ１〜のフィールドをオフセットフィー
ルドという）。それ以外の各フィールド２０２，２０３
は、主メモリ」二の各テーブルへのインデックスである
（以下、これらのフィールドをインデックスフィールド
という）。テーブルにアクセスする際のアドレスは、各
テーブルのベースアドレスにインデックスを加算して得
られるので、インデックスフィールドのビットのピッ１
〜幅は各テーブルの大きさを表している。

さて、アドレス幅が拡大した際にも段数を少なく抑える
ためには、オフセットフィールドか、あるいはインデッ
クスフィールドのどちらかの幅を拡大しなければならな
い。オフセラ１〜フイールドの幅を拡大すると、ページ
のサイズが拡大される。

ページはメモリの割当ての最小単位であり、大きすぎる
とメモリを有効に利用できない。また、インデックスフ
ィールドの幅を拡大すると、各テーブルの容量は巨大に
なってしまい、やはりメモリを有効に利用できなくなる
。したがって、アドレス幅が大きい場合は、テーブルは
多段階とする必要がある。

以上、アドレス幅が拡大された際には、テーブルを多段
階としなければな″らないことを示した。

さて、ここでテーブルを多段階にした場合の問題点を考
えてみる。

従来の技術では、入力された論理アドレスがＴＬＢに登
録されていれば、物理アドレスへの変換は高速に行うこ
とができる。一方、入力された論理アドレスがＴＬＢに
登録されていない場合は主メモリ上のテーブルをアクセ
スしなければならない。すでに示したように、アドレス
幅が大きい分テーブルは多段階となるので、主メモリの
アクセス回数が多くなり変換に要する時間は増大する。

第４図は、論理アドレスが６２ビツトの場合のアドレス
フィールドの分割例を示している。フィールドの数は、
オフセット４−０７を除くと、５っである。したがって
、入力された論理アドレスがＴ　Ｌ　Ｂに登録されてい
ない場合、物理アドレスを求めるためには主メモリ上の
テーブルを５回アクセスする必要があり、論理アドレス
幅が３２ビツトの場合と比較して変換速度は明らかに低
下する（なお、従来のアドレスフィールドの数は、半空
間指定子とオフセットを除けば２つであり、テーブルへ
のアクセスは２回であった）。

変換速度の低下の原因は、入力された論理アドレスがＴ
ＬＢに登録されていない場合（以下、このことをＴＬＢ
ミスヒツトという）に、主メモリ上のテーブルにアクセ
スする回数が大きいことにある。したがって、変換速度
の低下を抑えるためには、アドレス変換１回当りのテー
ブルへのアクセス回数の実効値を等しくしなければなら
ない。

〔アドレス変換１回あたりのテーブルへのアクセス回数
〕Ａは、［Ｔ　Ｌ　Ｂミスヒラｈの確率（以下、ＴＬＢ
ミスヒツト率という）〕をＰ、［ＴＬＢミスヒッＩ・の
際のテーブルアクセス回数〕をＮとすれば、次に示す式
で計算できる。

Ａ＝ＰＸＮ したがって、Ａを一定とすればＰとＮは反比例する。Ｔ
ＬＢミスヒツトの際のテーブルへのアクセス回数Ｎは、
論理アドレス幅が３２ビツトの場合２回、６２ビツトの
場合５回である。したがって、論理アドレス幅が６２ピ
ツ１への場合に、３２ビツトの場合と同じ速度でアドレ
ス変換を行うには、アドレス変換１回当りのテーブルへ
のアクセス回数Ａを等しくするために、ＴＬＢミスヒツ
ト率Ｐを、論理アドレスが３２ピッ１−の場合の５分の
２にしなければならない。

さて、ＴＬＢミスヒツト率Ｐを小さくするには、入力さ
れた論理アドレスがＴＬＢに！されている確率を上げる
必要がある。このためには、ＴＬＢのエントリ数を増加
させ、登録可能な論理アドレスと物理アドレスの対の数
を増加させなければならないが、価格対効果の点で不利
であり、現実的ではない。

本発明では、アドレス幅が増加しても、少量のハードウ
ェアの追加によって変換速度の低下を抑えられるアドレ
ス変換装置を提供することを目的とする。

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

上記の課題を解決するため、バッファメモリを備え、入
力された論理アドレスと変換テーブルの途中段のベース
アドレスとの対応を記憶することとした。このバッファ
メモリに対する登録の方法はＴＬＢに準じる。すなわち
、論理アドレスから物理アドレスを求める段階で得られ
る、途中段のテーブルベースがバッファメモリに記憶さ
れる。

〔作用〕

入力された論理アドレスがＴＬＢに登録されていなくて
もバッファメモリに登録されていれば、変換テーブルの
途中段のベースアドレスが直ちに求められるので、初段
から途中段までのテーブルへのアクセスは省略できる。

したがって、アクセスを省略した分だけ、アドレス変換
に要する時間は短縮でき、変換速度は上昇する。

また、このバッファメモリはＴＬＢと比較して、１エン
トリ当りカバーするアドレス範囲が広大である。１エン
トリのＴＬＢは４０９６　（＝２”）バイトのアドレス
範囲をカバーするのに対し、バッファメモリは約４２億
（＝２”）バイトのアトレス範囲をカバーし、ＴＬＢの
１００万倍強である。したがって、ＴＬＢよりも少ない
エントリ数でアドレス変換速度の向上が図れる。

たとえば、アクセスする範囲が論理アドレスの０番地か
ら４０億番地までの４０億バイトに限定されている場合
を考える。この場合、バッファメモリを検索するキーと
なる論理アドレス中のフィールドは常にＯとなるので、
バッファメモリが１エントリだけあれば、入力される論
理アドレスはいつもバッファメモリに登録されているこ
とになる。したがって１、ＴＬＢにミスヒツトしても、
アドレス変換に伴う主メモリ上のテーブルのアクセスは
２回で済む。つまり、アドレス幅が増大したにもかかわ
らず、バッファメモリを１エントリ設けるだけで論理ア
ドレスが３２ビツトの場合と同じ変換速度を得ることが
できる。

このことを、バッファメモリを使用しない場合と比較し
てみる。バッファメモリを使用しない場合は、前述した
とおりＴＬＢミスヒツト時のテーブルアクセス回数は、
アドレス幅３２ビツトの場合と比較して２．５倍である
。ＴＬＢを１エントリ増やしても、ＴＬＢがカバーする
アドレス範囲は４０９６バイト増加するだけであり、２
．５倍の差を縮めることは到底できない。アドレス幅３
２ピッｌ−の場合と同じ変換速度を得るためにはＴＬＢ
のエントリ数の大幅な増加が必要である。

つまり、バッファメモリを用いれば、アドレスが増加し
ても少量のハードウェアの追加で変換速度の低下を抑え
ることができる。

〔実施例〕

以下、本発明の実施例を第１図を基に説明する。

この実施例では、論理アドレスとセクションテーブルベ
ースとの対応がバッファメモリ１０９に記憶されている
。セクションテーブル１０５．ページテーブル１０７の
機能は従来と同様である。

すなわち、セクションテーブルの各エントリには、ペー
ジテーブルベース１０６が記憶され、ページテーブルの
各エントリには、ページフレーム番号１０８が記憶され
ている。

アドレスフィールドの区切りは、第４図のとおりである
。入力された論理アドレスを物理アドレスに変換するス
テップを第５図に示す。

ステップ５０１で、論理アドレスがＴ　Ｌ　Ｂ　１１３
に登録さ□れているかどうか検索する。登録されていれ
ば、ＴＬＢ　１１３からページフレーム番号１１８が得
られる（ステップ５０２）。これにオフセットを加算（
ステップ５０７）Ｌ、アドレス変換は終了する。

入力された論理アドレスが、ＴＬＢ１１３に登録されて
いない場合は、ステップ５０３でバッファメモリ１０９
に登録されているかどうか検索する。すなわち、バッフ
ァメモリインデックス１１０をキーとして、バッファメ
モリ１０９のエントリにこれと一致するインデックスフ
ィールド１１１を持つものがあるかどうかを検索する。

登録されている場合はステップ５０４へ進み、バッファ
メモリ１０９に登録されているセクションテーブルベー
ス１１２を得る。

なお、バッファメモリは１エントリ嶺り４Ｇ（＝２１０
＋１１′＋１２）バイトのアドレス変換に関する情報を
保持している。たとえば、バッファメモリが１６エン１
〜りであるとすると、１６Ｘ４Ｇバイ１−１すなわち６
４Ｇバイト分の情報を保持できるので、はぼ確実に変換
テーブルの３段分メモリアクセスは省略できる。

以降はステップ５０５に進み、従来の技術の項で説明し
た３２ビツトの論理アドレスを変換する方法とほぼ同様
である。バッファメモリに登録されているセクションテ
ーブルベース１１２をベースとし、セクションインデッ
クス４０５をインデックスとして、セクションテーブル
１０５がアクセスされ、ページテーブルベース１０６を
得る。

次にステップ５０６に進み、このページテーブルベース
をベースとし、ページインデックス４０６をインデック
スとしてページテーブル１０７をアクセスし、ページフ
レーム番号１０８を得る。

（後のアドレス変換に備えるため、入力された論理アド
レスと求められたページフレーム番号との対がＴＬＢｂ
こ登録される）ページフレーム番号は該ページの先頭の
物理アドレスなので、この値とオフセット４０７を加算
して、目的の物理アドレスを求める。以上でアドレス変
換が終了する。

入力された論理アドレスが、Ｔ　Ｌ　Ｂにもバッファメ
モリ１０９にも登録されていない場合は、論理アドレス
を分割した各フィールド（第４図の４０２〜４０４）を
インデックスとしてテーブルをアクセスし、セクション
テーブルベースを求める必要がある（ステップ５０８〜
５１０）。これは、〔従来の技術〕の項で説明したとお
りであるが、ここでより詳細に説明する。

ステップ５０８では、変換チーフルベース１１４をベー
スとし、論理アドレスの第１フイールド４０２をインデ
ックスとして、第１テーブルをアクセスすることによっ
て、第２テーブルのベースを得る。ステップ５０９ては
、ステップ５０８で得た第２テーブルのベースを利用し
、論理アドレスの第２フイールド４０３のインデックス
として、第２テーブルをアクセスすることによって、第
３テーブルのベースを得る。ステップ５１０では、ステ
ップ５０９で得た第３テーブルのベースを利用し、論理
アドレスの第３フイールド４０４をインデックスとして
、第３テーブルをアクセスすることによって、セクショ
ンテーブルベースを得る（この際得られたセクションテ
ーブルベースは、バッファメモリに登録され、次回のア
ドレス変換に備える）。

以降はステップ５０５に進むので、入力された論理アド
レスがバッファメモリに登録されていた場合と同様であ
る。

以下、この実施例の一部を変更したものについて説明す
る。これは、以上の説明で用いられたバッファメモリの
代わりにレジスタを用いるものである。このレジスタは
、バッファメモリと同様、論理アドレスを記憶する部分
と、テーブルのベースアドレスを記憶する部分を備えて
いる。したがって、アドレス変換の手順は前の説明とほ
ぼ同様であるので省略する。ただし、登録を明示的に行
う必要がある点がバッファメモリと異なっている。

〔発明の効果〕

以上のように本発明によると、変換テーブルが多段階に
なった場合にもＴＬＢミスヒツト時のメモリアクセスの
回数を減少させることができる。

すなわち、アドレス幅の増大に伴うアドレス変換の速度
低下を抑えることが可能である。したがって、アドレス
幅増大の要求に柔軟に対応することができる。

【図面の簡単な説明】

第１図は本発明の実施例による７１〜レス変換を示した
説明図、第２図は従来の技術による論理アドレスの分割
を示した図、第３図は従来の技術によるアドレス変換を
示した説明図、第４図は本発明の実施例における論理ア
ドレスの分割例を示した図、第５図は本発明の実施例に
よるアドレス変換の処理手順図である。 １０９・・・バッファメモリ、１１３，３１０・・・Ｔ
ＬＢ、１１５．３０９・・・物理メモリ、１０６，３０
２・セクションテーブル、ｌ’０７，３０３・・ページ
テーブル、１１４・・・変換テーブルベース、２０２゜
４０５・・・セクションインデックス、２０３，４０６
・・ページインデックス、２０４，４０７・・オフセ、
リ　ｋ Ｏ・・・バ・・ノフマメ千 １インデ・ソクス７

Claims (1)

1. 【特許請求の範囲】 １、多段階のテーブル検索で、入力された論理アドレス
   から物理アドレスを求めるアドレス変換装置において、
   入力された論理アドレスの上位部と途中段テーブルのベ
   ースアドレスとの対応を記憶するバッファメモリを備え
   たことを特徴とするアドレス変換装置。 ２、入力された論理アドレスと出力される物理アドレス
   との対応を記憶するバッファメモリ （ＴＬＢ）を備えた、請求項１記載のアドレス変換装置
   。 ３、請求項１または２記載のアドレス変換装置であって
   、バッファメモリに代えて直接書き換え可能なレジスタ
   を用いることを特徴とするアドレス変換装置。