JPH0529945B2

JPH0529945B2 -

Info

Publication number: JPH0529945B2
Application number: JP2099156A
Authority: JP
Inventors: Deyukuso Rooran; Uare Fuiritsupu
Original assignee: Bull SAS
Current assignee: Bull SAS
Priority date: 1989-04-13
Filing date: 1990-04-13
Publication date: 1993-05-06
Also published as: EP0392932B1; US5218687A; EP0392932A1; JPH0362144A; DE69010739D1; ES2060090T3; DE69010739T2; FR2645986B1; FR2645986A1

Description

【発明の詳細な説明】産業上の利用分野本発明は、情報処理システムの分野に関するも
のであり、特に、これらのシステムの主記憶装置
中に記憶された情報へのアクセスの加速に関する
ものである。

情報処理システムの中央サブシステムは、通
常、３種の装置を備える。すなわち、プロセツ
サ、主記憶装置を形成するメモリモジユール及び
入力−出力コントローラである。従来、プロセツ
サは、バスを介して、メモリモジユールと接続す
る。このバスによつてプロセツサと主記憶装置間
のアドレツシングとデータ転送を行うことができ
る。プログラム命令を実施するためには、そのオ
ペランドを主記憶装置中に探索しなければならな
い。連続したプログラム命令を実行する場合も同
様である。多重プログラミングで作動するシステ
ムの場合、メモリはプログラム間での多重化を可
能にするように分割されなければならない。その
ためには、通常、ページング技術と組み合わせた
仮想アドレツシングを使用する。このページング
技術とは、アドレス可能な空間、すなわち、「仮
想空間」を「ページ」と呼ばれる一定のサイズの
区間に分割することからなる。このようなシステ
ムでは、実行中のプログラムは仮想空間をアドレ
スすることができる。主記憶装置の一部は、その
仮想空間に対応しなければならない。従つて、論
理または仮想アドレスは、物理アドレス、すなわ
ち、メモリのアドレツシングを可能にする実際の
アドレスに変換されなければならない。

アドレツシングを必要とする命令は、それを実
行するプロセツサが結果として仮想アドレスを有
するアドレスの発生を実施することができるよう
にする表示を含む。通常、この仮想アドレスはセ
グメント化されており、すなわち、セグメント番
号とページ番号とページ中のデイスプレイスメン
トによつて構成されている。セグメント番号は、
それ自体、セグメントのテーブル番号とこのテー
ブル内でのデイスプレイメントに更に分割され
る。

メモリ内で、このセグメント化されたアドレス
に組合わされた情報にアクセスするためには、複
数のメモリアクセスが必要である。まず、このテ
ーブル内で、その処理（実行中のプログラム）に
割り当てられた空間にアクセスし、セグメントの
テーブル番号を使用して、対応するセグメントテ
ーブルの実アドレスを得て、セグメントテーブル
内のデイスプレイスメントに応じて、ページテー
ブルの実アドレスを計算することのできるセグメ
ントの記述子にアクセスし、最後に、このページ
テーブル内のデイスプレイスメントを決定するペ
ージ番号に応じて、メモリにアドレツシングする
ことのできるページの実アドレスを得る。１ワー
ドまたは１バイトの実アドレスは、ページの実ア
ドレスと、仮想アドレスの最下位部分によつて規
定されたこのページ内でのデイスプレイスメント
とを結合することによつて得られる。

また、メモリアクセスの実行は、特に、プロセ
ツサやメモリモジユールと共通のバスを使用する
ため、かなりの時間がかかる。従つて、システム
の性能を改善するために、原則的に各々のアドレ
ツシングを必要とする連続したメモリアクセスを
可能な限り避けるようにする。さらに、大部分の
処理はロケーシヨン特性を示し、それに応じて、
その実行の所定のフエイズの間、処理によつて使
用されるページ数は、それに割り当てられたペー
ジの総数に対して極めて少ない。

この特性を利用して、仮想アドレスの実アドレ
スへの変換を速くすることができる。そのため
に、高速メモリもしくはレジスタ内に仮想アドレ
スと組み合わされた実アドレスの複数のセツトを
記憶する。このアドレスのセツトは、「エントリ
（対応表）」と呼ばれ、実行中のプログラムによつ
て使用される。次に、仮想アドレスを実アドレス
に変換するために、連想的にこの高速メモリにア
クセスし、変換すべき仮想アドレスが高速メモリ
中に存在するかどうかをさがす。存在する場合、
主記憶装置にアクセスしなくても、実アドレスが
直接得られる。

局在性は、また、最も最近に参照されたページ
を常に維持しているサイズの小さな複数の高速メ
モリによつて構成されているキヤツシユメモリ
（「キヤツシユ」と呼ばれることもある）の使用に
基づくことがある。新しい参照がすでにキヤツシ
ユメモリに存在する情報に関するものである見込
みが高い時、明らかに情報へのアクセス時間は減
少される。仮想アドレスの実アドレスへの変換と
同様に、キヤツシユメモリは、キヤツシユメモリ
中に存在するページの実アドレスを含むテーブル
を備える。デイレクトリと呼ばれるこのテーブル
を連想的に参照して、実アドレスデータに組み合
わされた情報がキヤツシユメモリに含まれている
かどうかを調べることができる。含まれている場
合、１ワードまたはバイトを得て、この１ワード
またはバイトの仮想アドレスの最下位部分を利用
して、キヤツシユメモリにアドレツシングする。

以下の説明では、キヤツシユメモリの問題にも
同様の考察を当てはめることができるので、アド
レス変換に関する問題についてのみ説明する。実
際、どちらの場合も、問題は、ページアドレスに
組み合わされた情報を迅速に得ることにある。ア
ドレス変換の場合、ページアドレスは仮想アドレ
スであり、組み合わされた情報は対応する実アド
レスであるが、キヤツシユメモリの場合、ページ
アドレスは実アドレスであり、組みあわされた情
報はページに含まれるデータの全体によつて構成
されている。

上記のように、アドレス変換高速メモリは、複
数のレジスタ、または、より一般的には、複数の
ロケーシヨンを備え、その各々に仮想アドレスと
それに組み合わされた実アドレスからなるエント
リを記憶するこのとのできる連想メモリである。
各エントリには、アクセス権フラツグや、書き込
みアクセスがこのエントリに組み合わされたペー
ジ中で実行されたことを示すフラツグ等の補足的
な情報が伴うことがある。また、各エントリは、
所定の論理値について、組み合わされたエントリ
が有効であることを示す存在フラツグに組み合わ
されている。これらの存在フラツグは、初期化の
際、すなわち、問題のプロセツサで処理が開始さ
れるたびに、例えば、０に設定される。次に、処
理が新しいページを使用するにつれて、組み合わ
されたエントリは連想メモリにロードされ、同時
に、存在フラツグは１に設定される。メモリアク
セスを実行しなければならない時、仮想アドレス
を連想メモリに含まれた各仮想アドレスと比較し
て、存在フラツグが１の時に探索中の仮想アドレ
スとメモリに含まれる仮想アドレスの１つとの間
に一致があると、対応する実アドレスは、実アド
レスレジスタの簡単な読出しによつて直接得られ
る。

この変換システムを実際に実現可能にするため
には、連想メモリのサイズが限定されなければな
らないことは明らかである。その結果、ある処理
のためには、このサイズはこの処理に使用される
全部のページのエントリを含むには不十分である
ことがある。従つて、連想メモリが一杯の場合、
存在するエントリの１つを排除して、その場所に
新規なエントリをロードすることを考えなければ
ならない。そのため、排除すべきエントリを選択
するための置換アルゴリズムを使用する。多数の
アルゴリズムが既に提案されており、例えば、以
下のものがある。

−FIFO（first in first out）；最も古いエントリ
が除去される。

−RAND（random choice）；エントリを偶然に
選択する。

−LFU（least frequently used）；使用頻度が最
も低いエントリを排除する。

−LRU（least recently used）；最も昔に使用さ
れたエントリを置換する。

LRUアルゴリズムは、論理的には良好な結果
を示すが、実際には、疑似LRUと呼ばれる、単
純化されたバージヨンを使用するのが好ましい。
実際、ｎ個のエントリを管理するためには、本当
のLRUはエントリごとにlog₂（ｎ）ビツトの存在
と管理を必要として、最近使用されたエントリの
順序を保つ。一方、疑似LRUは、エントリごと
に参照ビツトもしくは参照フラツグと呼ばれる１
個のビツトを使用するだけでよい。

疑似LRUアルゴリズムによると、参照ビツト
は、それに組み合わされた存在するエントリが使
用される時、最初の論理値（例えば、１）に設定
される。連想メモリが一杯なのに新しいエントリ
をロードしなければならない時、すなわち、存在
フラツグが全部１の時、除去すべきエントリは、
ロードの順番において時間的に最も古いものであ
り、その参照ビツトは０である。飽和に達した
時、すなわち、参照ビツトが１つを除いて全部１
になつた時、全ての参照ビツトを０に再設定し、
参照ビツトが０になつたエントリを新しいエント
リで置換する。この瞬間から、ページの使用の時
間的順序は失われる。

飽和による時間的順序の喪失によつて、アルゴ
リズムの有効性が低下する。また、新たにロード
されたエントリはそのロードの直後に再使用され
る可能性が高いことを考慮すると、最後のエント
リがロードされると飽和が生じることになる。

発明が解決しようとする課題この時間的順序の損失の結果を判定するため
に、システムによつて従来処理されている方法の
特有の処理の母集団に関するシミユレーシヨンを
実施することが有効である。例えば、ある処理の
母集団では、65％の場合、必要なエントリは32個
だけであることが確かめられる。このことは、処
理の65％は、置換アルゴリズムの使用を必要とし
ないことを意味する。反対に、35％の処理では、
少なくとも１回はアルゴリズムが必要とされる。
従つて、時間的順序の喪失は、35％の場合、少な
くとも１回は起こることになる。

また、シミユレーシヨンの際、所定の瞬間に、
90％の場合、プログラムは、最近呼び出された７
つのエントリの１つにアクセスすることが確かめ
られた。この結果として、前述の局所性の現象が
確かめられる。また、飽和後参照ビツトを０に再
設定した後、除去すべきエントリを選択する唯一
の参照は連想メモリ中のエントリの位置である。
しかし、エントリのロケーシヨンは、その最後の
使用の時についての情報を示すのではなく、最小
の使用の時についての除法を示している。さら
に、処理の始めに使用されたページは飽和の直前
に再度使用されることがある。従つて、この場
合、参照ビツトを０に再設定すると、これらのペ
ージは、迅速に再使用される機会があるにもかか
わらず、優先的に除去される。

従つて、この問題を解決するために、本発明に
よると、処理の実行の始めの間、及び、存在する
エントリ数が所定の閾値により小さい限り、ずつ
と参照フラツグをその初期値（例えば１）に保つ
ことを提案した。閾値に達すると、通常、参照フ
ラツグが明らかになる。従つて、連想メモリが一
杯になると、ロードの終わりに対応する実行フエ
イズの間使用されたエントリだけが使用を示す論
理値（例えば１）の参照フラツグを持つことがで
きる。そのため、平均して、かなり大きな数の処
理が飽和による時間的順序の喪失を逃れることが
できる。

課題を解決するための手段より詳細には、本発明は、情報がアドレスによ
つて参照され、情報と組み合わされたアドレスに
よつて形成される組が「エントリ」と呼ばれる情
報処理システムの主記憶装置に含まれる情報にア
クセスする方法であつて、このシステムは、各々
が１つのエントリを記憶することのできる複数の
ロケーシヨンによつて構成された高速メモリを備
え、上記エントリは各々所定の第１の論理値に初
期化された存在フラツグと参照フラツグとに組み
合わされており、上記存在フラツグは対応するエ
ントリが上記高速メモリ中に存在すると第２の論
理値を取り、該高速メモリ中に存在し、そのアド
レスが探索中の情報のアドレスと一致するエント
リを探索する連想読出しによつて情報へのアクセ
スを実施し、上記参照フラツグは組み合わされた
エントリの使用を示し、それによつて、サーチし
ているが、まだ、上記高速メモリ中に存在してい
ない新規なエントリのロードのアルゴリズムを実
施することができる方法において、上記参照フラ
ツグは、上記高速メモリ中に存在するエントリ数
が所定の閾値値より小さい限りその第１の論理値
に維持され、上記の存在するエントリ数が閾値以
上の時、上記の組み合わされたエントリが使用さ
れると、参照フラツグが第２の論理値になること
を特徴とする方法を提供することを目的とする。

閾値の選択は、高速メモリのロケーシヨンの数
ｎを考慮し、閾値とこのｎの数との間の範囲に含
まれるエントリ数が考えられる利用法のための最
適の経時的な期間に対応するようにされることに
注目するとよい。

本発明の特徴によると、この方法は、さらに、
範囲は上記高速メモリの各ロケーシヨンに当ては
められるので、エントリは当初範囲が増大するロ
ケーシヨン内で時間的順序によつてロードされ、
上記範囲が上記閾値に等しい存在フラツグは上記
閾値に到達したという表示を提供することを特徴
とする。

本発明の別の特徴によると、この方法は、探索
中の情報が高速メモリに存在しないと、該情報は
主記憶装置中で探索され、対応するエントリは範
囲がロードのアルゴリズムによつて決定されたロ
ケーシヨンに配置され、上記の組み合わされた存
在フラツグは上記ロードと同期して第２の論理値
にされ、次に、探索中の情報の新規な連想的探索
が実施されることを特徴とする。

また別の特徴によると、この方法は、上記ロー
ドアルゴリズムは、増大する順序で上記存在フラ
ツグが上記の所定の第１の論理値である第１のエ
ントリ、または、そうでなければ、参照フラツグ
が上記の所定の第１の論理値である第１のエント
リの範囲を探索することを特徴とする。

本発明は、また、上記の方法を実施することの
できる情報処理システムであり、該システムの主
記憶装置へのアドレツシングによつてアクセスす
ることのできる処理手段を備え、該主記憶装置中
に含まれるアドレスとそれに組み合わされた情報
とによつて形成された組が「エントリ」と呼ば
れ、上記処理手段は複数のロケーシヨンによつて
構成された高速メモリを備え、このロケーシヨン
は各々上記エントリの１つの記憶することがで
き、各々、当初第１の論理値に設定された存在フ
リツプフロツプ及び参照フリツプフロツプに接続
され、エントリが上記の接続されたロケーシヨン
にロードされた時上記存在フリツプフロツプは第
２の論理値にされ、上記高速メモリは探索中の情
報のアドレスが上記ロケーシヨンに存在するエン
トリのアドレスに一致する第１の論理値を有する
一致信号を各ロケーシヨンに出力することのでき
る比較手段に接続されており、上記システムは、
上記高速メモリ中に存在するエントリ数が所定の
閾値以上であるかどうかをその論理値が示す閾値
信号を発生させる閾値検出手段を備え、各存在す
るエントリのため、上記の接続された参照フリツ
プフロツプの状態は、上記一致信号が一致を示
し、同時に、上記閾値信号が閾値に達したことを
示す時、該参照フリツプフロツプを第２の論理状
態にする管理回路によつて制御されていることを
特徴とするシステムを提供することを目的とす
る。

本発明のその他の特徴及び詳細な実施態様を添
付図面を参照して、以下に説明する。

実施例第１図は、本発明を実施することのできる情報
処理システムの装置の概略図である。この装置
は、高速メモリまたは連想メモリ１を備える。こ
のメモリは、そのコントローラ２とプロセツサの
他の回路３に接続されている。従来の方法では、
プロセツサは、回路３を介して主記憶装置（図示
せず）に接続されていた。回路３は、アドレス変
換に関するものを除いて、他の全部のプロセツサ
の処理手段を備える。特に、通常、マイクロプロ
グラミングされたアドレス生成ユニツトを備えて
おり、求められている情報の仮想アドレスAVを
命令から計算する。回路３のマイクロプログラム
により、テーブル内を探索して、仮想アドレスに
応じて実アドレスを得る。このアドレス変換は、
ｎ個の仮想アドレスレジスタRAVと同じ数の実
アドレスレジスタRARによつて構成されている
連想メモリ１によつて、加速される。メモリ１
は、また、ｎ個のフリツプフロツプBPRの装置
を備えており、このフリツプフロツプは各々仮想
アドレス及び実アドレスのレジスタに接続されて
いる。行ｉの仮想アドレスレジスタに含まれた仮
想アドレスAV_iと同じ行の実アドレスレジスタに
含まれた実アドレスAR_iは、エントリｉを構成す
る。このエントリｉは、存在フラツグPR_iに組み
合わされている。このフラツグの論理値は、対応
する存在フリツプフロツプの状態に対応する。コ
ンパレータ４は仮想アドレスレジスタRAVの出
力AV_iに接続されており、マイクロプログラム回
路から変換すべき仮想アドレスAVを受ける。比
較回路４は、存在フリツプフロツプBPRの出力
PR_iの信号によつて有効化される。回路４は、一
致信号HIT_iを出力する。この信号の論理値は、
求めていた論理アドレスとレジスタRAVに含ま
れた論理アドレスの１つが等しいことを示す。信
号HIT_iは、有効化回路８に入力される。この回
路は、アドレス変換が成功したかどうかを示すア
ドレス有効化信号AD VALをマイクロプログラ
ム回路に出力する。

失敗の場合、信号AD VALはテーブル内で探
索マイクロプログラムを始動させ、実アドレスを
得る。探索が実施されると、組み合わされた仮想
アドレスAV_eと実アドレスAR_eは、各々、仮想ア
ドレスレジスタと実アドレスレジスタの入力イン
ターフエース５及び６に入力され、各々、書き込
み制御信号WRV_i及びWRR_iの制御下でこれらの
レジスタの１つに書き込まれる。

交換が成功した場合、一致信号HIT_iはインタ
ーフエース７によつて、求めていた変換を含むア
ドレスレジスタの読出しを実施させる。

コントローラ２は、複数の参照フリツプフロツ
プBRFを備える。これらのフリツプフロツプは、
各々、メモリ１のロケーシヨンに組み合わされて
いる。フリツプフロツプBRFの状態RF_iは、制御
回路９によつて決定されている。この制御回路９
には一致信号HIT_iが入力され、また、この制御
回路は参照フリツプフロツプBRFの出力RF_iに接
続されている。存在フリツプフロツプBPRと参
照フリツプフロツプBRFの出力に接続された選
択回路１０は選択信号S_iを出力し、この信号は、
ロード制御回路１１に入力される。このロード制
御回路１１は、前記の信号WRV_iとWRR_iを出力
する。この選択信号S_iによつて、テーブルに存在
しない新しいエントリをロードすべきである仮想
アドレスレジスタと実アドレスレジスタを決定す
ることができる。書き込み制御WRV_iとWRR_iは、
選択信号S_iとマイクロプログラム回路によつて出
力される書き込み制御共通信号WRR，WRVに
に応じてロード制御回路１１によつて決定され
る。また、マイクロプログラム回路３は、存在フ
リツプフロツプ及び参照フリツプフロツプを０に
リセツトする信号RSを出力する。

第１図の装置は、以下の方法で動作する。仮想
アドレスAVを変換すべき時、マイクロプログラ
ム回路はコンパレータ４の入力にこのアドレスを
配置する。一致の場合、信号HIT_iは求めていた
変換を含む実アドレスレジスタを有効化し、回路
８は信号ADVALによつてこのアドレスを有効化
する。一致信号HIT_i、高速メモリに存在するエ
ントリ数及び参照フリツプフロツプの前段の状態
RF_iに応じて、制御回路９はこの参照フリツプフ
ロツプの状態を再活性化する。これらのフリツプ
フロツプの新規な状態RF_i及び存在フラツグPR_i
に応じて、選択回路１０は選択信号S_iを再活性化
し、ロードされるべき次のエントリが書き込まれ
る新規なレジスタを決定することができる。

失敗の場合、この状態は、テーブル内でリサー
チマイクロプログラムを再始動させる信号AD
VALによつて信号化される。リサーチを実施す
ると、対応するエントリAV_e，AR_eはインターフ
エース５及び６の入力に存在する。次に、このエ
ントリは、書き込み信号WRR，WRV及び選択
信号S_iに応じて回路１１の制御下でロードされ
る。この選択されたレジスタにエントリがロード
さると、マイクロプログラムは変換すべき仮想ア
ドレス変換の新規な試みを実施する。

この実施態様の特徴によると、制御回路９はメ
モリ中に存在するエントリ数を考慮する。この数
が所定の閾値ｔより小さい限り、参照フラツグ
RF_iは変わらず、従つて、例えば、デイスパツチ
ングに続いて、処理の実施の始めに信号RSによ
つて与えられた初期値（例えば、０）を維持す
る。存在するエントリ数がｔの値に達するかそれ
以上になると、フラツグRF_iは従来のアルゴリズ
ム疑似LRUによつて変更される。以下の説明で、
この閾値が実際にどのようにして検出されるかを
説明する。

閾値は、ｎ−ｔの最大値を求めることによつて
決定される。このｎ−ｔは、閾値に達した時と連
想メモリが一杯になつた時との間にロードされた
エントリ数を対応する。そのため、特に、２つの
デイスパツチングと再使用されたページの古さと
の間で、処理によつて使用されるエントリ数につ
いての統計データを使用することができる。もし
１つの解決法は、閾値を変化させながら、プログ
ラムの特性でシステムの機能シミユレーシヨンを
実施することである。

非限定的な実施例として、ｎ＝32のマイクロプ
ロセツサ型汎用コンピユータの場合、ｔ＝24を選
択する。

第２図は、エントリの１つに組み合わされたメ
モリ１の一部分を図示したものである。想定され
たエントリｉの仮想アドレス及び実アドレスは、
各々、仮想アドレスレジスタRAV_iと実アドレス
レジスタRAR_iに含まれている。仮想アドレス
RAV_iの並列出力AV_iはコンパレータ４の比較回
路１４の第１の入力に接続されており、その第２
の入力にはレジスタR_cによつて出力された変換
すべき仮想アドレスAVが入力される。存在フリ
ツプフロツプBPR_iの出力PR_iは、回路１４の有効
入力に接続されている。また、出力PR_iは、コン
トローラ２に接続されている。回路１４の出力
は、一方はコントローラ２に、他方は同期化ゲー
ト１７の入力に接続されている。ゲート１７は、
クロツク信号の第１の位相CK１によつて同期化
される。

実アドレスレジスタRAR_iの並列出力は、同期
化ゲート１７の出力信号RD_iによつて有効化され
る増幅器１８Ｂの入力に接続されている。信号
RD_iは、また、増幅器１８Ａを有効化し、増幅器
１８Ａは、論理値１に対応する電圧をその入力に
受ける。増幅器１８Ａ及び１８Ｂから出力された
信号ADVAL及びAR_iはマイクロプログラム回路
に送られる。

レジスタにロードされるべき仮想アドレス及び
実アドレスAV_e，AR_eは、当初、マイクロプログ
ラム回路の出力R_eのレジスタに配置される。レ
ジスタR_eの並列出力は、増幅器１５及び１６を
介してレジスタの並列入力RAV_i及びRAR_iに接
続されている。増幅器１５及び１６は、各々コン
トローラ２によつて出力された信号WRV_i及び
WRR_iによつて有効化される。

第２図の回路は、以下のように作動する。クロ
ツク（図示せず）は、２つの位相のクロツク信号
CK１及びCK２を出力する。位相CK２の間、マ
イクロプログラム回路はレジスタR_c内に変換す
べき仮想アドレスを配置する。次の位相CK１の
間、このアドレスを回路１４中でレジスタRAV_i
に含まれる仮想アドレスAV_iに比較する。これら
のアドレスAVとAV_iが異なる時、または、存在
フラツグPR_iが０の時、一致信号HIT_iは０の値を
とる。その結果、位相CK１の間、増幅器１８Ａ
及び１８Ｂは高インピーダンス状態に維持され
る。

反対に、アドレスAVとAV_iが同じで、存在フ
ラツグPR_iが１の時、一致信号HIT_iは１の値をと
る。このように、位相CK１の間、レジスタ
RAR_iに含まれる実アドレスAR_iは、増幅器１８
Ｂを介してマイクロプログラムに転送される。同
時に、信号AD VALは１であり、このようにし
て変換の成功を表示する。メモリの他のエントリ
に組み合わされた増幅器１８ＡはワイヤードOR
機能を実施する。これは、好ましは、位相CK２
中にあらかじめ充電され、位相CK１中に信号
RD_iによつて選択的に放電された線を介して、実
施することができる。

高速メモリ内に新規なエントリをロードするに
は、まず、レジスタR_e内にエントリの仮想アド
レスAV_eを配置し、仮想アドレスの書き込み制
御信号WRVを活性化する。レジスタRAV_iが選
択された時、コントローラ２のロード回路１１は
信号WRV_iを出力して、増幅器１５を有効化させ
る。同様に、対応する実アドレスAR_eを出力レジ
スタR_eに配置して、信号WRR_iは増幅器１６を有
効化させる。

第３図は、参照フリツプフロツプBRFとその
制御回路９を詳細に図示したものである。制御回
路９は、１つの共通制御回路１９Ｂと複数のフリ
ツプフロツプBRFの管理回路１９Ａに分解され
る。連想メモリの配置（レジスタのセツト）は表
示１，２…，ｉ，…，ｎによつて参照されるの
で、それらに各々フリツプフロツプBRF₁，
BRF₂，…，BRF_i，…，BRF_oを組み合わせる。
各フリツプフロツプBRF_iは、組み合わされた管
理回路GRFによつて出力された信号WRF_iによつ
て制御される。出力RF₁，RF₂，…，RF_i，…
RF_oは、共通制御回路１９Ｂに接続されており、
各管理回路GRFに１へのセツト信号Ｖと０への
リセツト信号CL２とを出力する。回路１９Ｂは、
また、一致信号HIT₁，HIT₂，…，HIT_i，…
HIT_oを受ける。

各管理回路GRFは、組み合わされた一致信号
HIT_iのフリツプフロツプBHLによる位相CK１
でのラツチによつて得られた信号HL_iを受ける。

第３図は、第４図及び第５図によつて説明され
る。第４図及び第５図は、各々、共通制御回路１
９Ｂ及び管理回路GRFの実施態様を詳細に図示
したものである。以下の説明は、正の論理で行わ
れる。

第４図の共通制御回路１９Ｂは、判定回路１９
Ｃ、フリツプフロツプBCL及び同期化回路１９
Ｄとによつて構成されている。

判定回路１９Ｃは、判定線CLを備える。この
判定線の状態は、高速メモリが飽和状態に達して
いるかどうかを示す。判定回路１９Ｃは、
CMOS技術の複雑な論理ゲートによつて構成さ
れている。その線CLは、PMOSトランジスタＰ
１及びＰ２を使用して、位相CK２の間にあらか
じめロードされる。線CLは、信号HIT_i ^*及びRF_i
^＊に応じて決定される。これらの信号は、各々、
高速メモリ内に含まれたエントリに組み合わされ
た一致信号HIT_i及び参照信号RF_iの反転信号であ
る。線CLの状態は、位相CK１によつてフリツプ
フロツプBCL中にラツチされる。このフリツプ
フロツプは、ラツチされた判定信号CL１を出力
する。

線CLは、共通のNMOSトランジスタＮ３と、
各エントリごとに、２つのNMOSトランジスタ
Ｎ１及びＮ２で形成された直列回路を介してアー
スV_ssに接続されている。その２つのNMOSトラ
ンジスタＮ１及びＮ２のゲートには、各々、組み
合わされたエントリの信号RF_i ^*及びHIT_i ^*が入力
される。この構成によつて、論理関数を演算（位
相CK１の間に計算）することができる。

CL＝Σ^*（RF_i ^*・HIT_i ^*）（但し、上記式において、Σ^*は、論理積RF_i
^＊・HIT_i ^*の全体に当てはめられるNOR関数であ
る。）位相CK２の間ブロツクされたトランジスタＮ
３は、CL線のプリロードに役立つ。

従つて、全てのフラツグが０に初期化された連
想メモリの作動の最初から、飽和状態に達してお
らず、この状態が一致がある場合だけを除いて、
参照フラツグが全部１である場合に対応する限
り、CL線は各判定フエイズで放電する。一致が
ある場合、CL線は判定フエイズの間論理値１を
保持し、このようにして飽和状態に達したことを
信号化する。

同期化回路１９Ｄは、３つの入力を有する
ANDゲート２１を備える。第１の入力にはラツ
チされた判定信号CL１が入力され、第２の入力
には位相CK２が、第３の入力には作動許可信号
USEが入力される。USE信号は、マイクロプロ
グラム回路によつて出力される作動制御信号であ
る。

また、同期化回路１９Ｄは、３つの入力を有す
るNANDゲート２０を備える。この３つの入力
には、各々、クロツクの位相CK２，USE信号及
び高速メモリのロード限界に達した時１の値をと
る閾値信号PR_tが入力される。ゲート２０は、信
号V^*を出力する。この信号V^*は、１にあらかじ
め決定される信号Ｖの反転信号である。ロケーシ
ヨンが所定の順序でロードされているならば、閾
値信号は、フリツプフロツプBPR_tの読出しによ
つて容易に得られる。その範囲は、閾値に等し
く、あらかじめ選択されたものである。

第５図は、参照フリツプフロツプBRF_iと接続
された管理回路GRFを図示した者である。フリ
ツプフロツプBRF_iは、互い違いに接続されたイ
ンバータによつて簡単に構成されている。これら
のインバータは、参照フラツグRF_i及びその反転
信号RF_i ^*を出力する。

フリツプフロツプBRF_iの状態RF_iは、線WRF_i
によつて制御される。線WRF_iは、２つのNMOS
トランジスタＮ４，Ｎ５によつて構成された直列
回路を介してまたはNMOSトランジスタＮ６を
介して放電される。トランジスタＮ４，Ｎ５及び
Ｎ６のゲードには、各々、信号HL_iの反転信号で
あるHL_i ^*，CL２信号及びRS信号が入力される。
その結果、HL_i信号が０で、RS信号が１の時ま
たはCL２信号が１の時、WRF_i線は放電される。
このように、接続されたレジスタに含まれた仮想
アドレスが変換すべき仮想アドレスと一致しない
時、飽和状態が検出されると、フリツプフロツプ
BRF_iは０にされる。

WRF_i線は、２つのPMOSトランジスタＰ３，
Ｐ４によつて形成された直列回路を介して、論理
値１にされる。このPMOSトランジスタＰ３及
びＰ４のゲートには、HL_i ^*及びV^*信号が入力さ
れる。この構成によつて、Ｖ及びHL_i信号が１の
時、すなわち、閾値に達せずに、求めている仮想
アドレスがレジスタ内に含まれている仮想アドレ
スと一致する時、フリツプフロツプBRF_iは１に
される。

第６図のタイミングチヤートを参照して、第３
図、第４図及び第５図の回路の完全な機能を以下
に説明する。

第６図のタイミングチヤートは、共通制御回路
１９Ｂによつて生成した信号CL，CL１，CL２
及び連想メモリのエントリｉに組み合わされた信
号HIT_i，HL_i及びRF_iの時間を関数とした変動を
図示したものである。使用されているエントリｉ
は存在しており、すなわち、フラツグPR_iは１で
あるが分かる。また、既に閾値に達しており、位
相CK２の間、従つて、この位相の間信号V^*がこ
の０の時、すでに閾値に達している、すなわち、
信号Ｖが１であると考えられる。さらに、最初の
時t₀時、参照フラツグRF_i及びラツチされた判定
信号CL１はどちらも０であると考える。

t₀の時から、位相CK２の間は、回路１９Ｃの
CL線のプリロードが実施される。t₁の時から、
次の位相CK１の間、１をとると仮定された一致
信号HIT_iの判定が実施される。この位相の間、
信号HIT_iはフリツプフロツプBHLによつてラツ
チされる。このフリツプフロツプの状態HL_iは、
１になる。同時に、CL線を判定する。飽和に達
しないと仮定すると、CL線は０になり、信号CL
１及びCL２もまた０である。t₂時から次の位相
CK２の間、CL線は再度ロードされる。また、一
致信号HL_iと有効化信号が１の時、管理回路GRF
のトランジスタＰ３及びＰ４はオン状態であり、
WRF_i線はこのようにフラツグRF_iを１にする正
の電圧にロードされる。

t₃時から次の位相CK１の間、一致がないとす
ると、一致信号HIT_iは０になり、従つて、信号
HL_iを０にする。常に、飽和状態に達していない
と仮定すると、CL線はこの位相の間放電され、
信号CL１及びCL２は０のままである。その結
果、t₄から次の位相CK２の間、０の信号CL２は
トランジスタＮ５をオフ状態に保ち、このように
して、フリツプフロツプBRF_iが０にリセツトさ
れるのを防ぐ。

t₅時から以下の位相CK１の間、閾値状態に達
して、信号HIT_iは０であると仮定した。その結
果、CL線はロードされ、このようにしてフリツ
プフロツプを１にセツトし、その状態を１にす
る。次に、t₆時から以下の位相CK２の間、０に
リセツトする位置決定信号CL２は１になり、ト
ランジスタＮ５をオンにする。信号HL_iは０なの
で、トランジスタＮ４もオンになり、WRF_iは放
電され、フラツグRF_iを０にリセツトする。

上記の説明によつて、参照フラツグが０にリセ
ツトされなければならない時でさえ連想メモリは
常に２つの位相のクロツクで作動することが示さ
れている。

第７図は、第１図を参照して説明した選択回路
１０を図示したものである。この図には、存在フ
リツプフロツプBPR１，BPR２，…，BPR_i，…
BPR_o及び連想メモリの行１，２，…，ｉ，…ｎ
のエントリに各々接続された参照フリツプフロツ
プBRF１，BRF２，…，BRF_i，…，BRF_oが示
されている。

各エントリｉには、選択セルCS及び各々、エ
ントリの存在フリツプフロツプと参照フリツプフ
ロツプに接続された要求信号の２つの伝播回路
CPが接続されている。

伝播回路CPは、各々、要求信号VP_i及びRP_iを
出力し、接続されたフリツプフロツプのフラツグ
PR_i及びRF_i、同様に、上流の伝播回路から出力
された要求信号VP_i-1及びRP_i-1が入力される。

ｎ列の最後のエントリの存在フリツプフロツプ
BPR_oに接続された伝播回路CPの出力VP_oは、第
１のエントリの参照フリツプフロツプBRF₁に接
続された伝播回路の要求入力に入力される。ま
た、第１のエントリの参照フリツプフロツプ
BPF₁に接続された伝播回路CPの要求入力には、
常に、要求の存在について示す信号が入力され
る。図示した実施例ては、要求信号が１である時
要求が存在すると考えられる。もちろん、この取
り決めを逆に選択しても、本発明の範囲を越える
ことはない。

伝播回路は、各々、要求信号VP_i及びRP_iを発
生させるように設計されている。この要求信号
は、各々、上流の要求信号VP_i-1及びRP_i-1が要
求の存在を示し、フラツグPR_i及びRF_iが１であ
る時、要求の存在を示す。また、上流の要求信号
VP_i-1またはRP_i-1が要求の存在を示し、接続さ
れたフリツプフロツプBPR_iまたはBRF_iが０の
時、エントリｉの選択を示す選択信号S_iを出力す
る。

第７図の回路は、以下のように動作する。存在
フリツプフロツプ及び参照フリツプフロツプの状
態に応じて、第１の存在フリツプフロツプBPR₁
に接続された伝播回路の入力に常に入力されてい
る要求信号は、まず、存在フリツプフロツプに接
続された伝播回路を介して、次に、参照フリツプ
フロツプに接続された伝播回路を介してエントリ
の増加順序で少しずつ伝播する。要求信号の伝播
は、０である存在フリツプフロツプまたは参照フ
リツプフロツプに接続された伝播回路の位置で停
止する。このエントリに接続された選択セルは、
この時、選択信号S_iを、接続されたレジスタ中に
新規なエントリの書き込みが実行されなければな
らないことを示す所定の論理値にする。

従つて、第７図の回路は、常に、ロードすべき
新規なエントリを入力するための連想メモリの位
置を示すことができる。この回路によつて実行さ
れるロードのアルゴリズムは、従つて、位置に影
響する行の増加する順序によつて、エントリを全
く含まない（その最初の存在フラツグPR_iは０で
ある）第１の位置、次に、最近使用されなくなつ
た第１のエントリ（その最初の存在フラツグRF_i
は０である）を求めることからなる。この実施態
様では、選択信号S_iの発見は、存在フリツプフロ
ツプ及び参照フリツプフロツプの状態の変化に自
動的に従う。

伝播回路の縦続接続を考慮すると、この反応時
間はかなり長い。しかし、選択信号は、ロードす
べき新規なエントリをテーブル内で探索した後し
か使用されず、この探索はかなり時間のかかる操
作なので、この欠点は決定的ではない。しかし、
連想メモリが多数のエントリを有する時、選択回
路の遅さは大きな欠点となることもなる。従つ
て、この欠点を解消するために、好ましい別の実
施態様によつて、これらの回路の層の数を減少さ
せて、従つて、動作の速度を大きくして、選択セ
ルと伝播回路の最適化を提案した。

この目的では、偶数の行か奇数の行の位置に接
続するかによつて２つの異なる型のセルを使用し
た。

第８図は、選択セルCSI及び奇数の行の位置に
接続された伝播回路を図示したものである。伝播
回路CPIは、NANDゲートによつて構成されて
おり、その第１の入力には接続されたフラツグ
RF_i，PR_iが、その第２の入力には上流の要求信
号RP_i-1，VP_i-1が入力される。CPIのゲートは、
反転した要求信号RP_i ^*，VP_i ^*を出力する。CSIセ
ルは、複合論理ゲートであり、その入力に上流の
要求信号RP_i-1，VP_i-1とフラツグRF_i，PR_iの反
転したRF_i ^*，PR_i ^*が入力される。CSIゲートは、
信号S_i ^*、この選択信号S_iの反転信号を出力する。
これは、以下の式によつて確かめられる。

S_i＝RF_i ^*・RP_i-1＋PR_i ^*VP_i-1 信号S_iを得るために、CSIゲートの出力は、イ
ンバータに接続される。

第９図は、選択セルCSP及び偶数行の位置に接
続された伝播回路CPPを図示したものである。
伝播セルCPPは、NORゲートを使用して実施さ
れる。その第１の入力には、接続されたフラツグ
RF_i，PR_iの反転信号が、第２の入力には前段の
奇数の段から出力された要求信号RP_i-1，VP_i-1
の反転したRP_i-1 ^*，VP_i-1 ^*が入力される。選択
セルCSPは、複合ゲートであり、その入力にはフ
ラツグRF_i，PR_i及び関連する要求信号RP_i-1，
VP_i-1の反転信号が入力される。CSPゲートは、
上記の論理式で確かめられる選択信号S_iを出力す
る。

CSI，CSPセル及びCSI，CPPゲートは、
CMOS技術で容易に実施することかできる。

第１０図は、制御信号WRV，WRR及び選択
信号S_iに応じて各々レジスタRAV_i及びRAR_iに接
続された書き込み制御信号WRV_i及びWRR_iを生
成することできる回路を図示したものである。第
１０図の回路は、各々、選択信号S_iによつて有効
化され、クロツク位相CK２によつて同期化され
る仮想アドレスWRV及び実アドレスWRRの書
き込み制御共通信号を転送することのできる
ANDゲートを使用して簡単に実現される。

【図面の簡単な説明】

第１図は、本発明を実施するための情報処理シ
ステムの概略図であり、第２図は、高速メモリの
１実施態様を図示したものであり、第３図は、参
照フラツグの制御回路を図示したものであり、第
４図は、第３図の制御回路の実施態様を詳細に図
示したものであり、第５図は、参照フリツプフロ
ツプの１つの管理回路を図示したものであり、第
６図は、第３図から第５図に図示した回路の動作
を説明するためのタイミングチヤートであり、第
７図は、新規なエントリをロードしなければなら
ない高速メモリの位置を決定することのできる選
択回路を図示したものであり、第８図及び第９図
は、第７図の回路の実施態様を詳細に図示したも
のであり、第１０図は、高速メモリの位置の１つ
のロード制御回路を図示したものである。主な参照番号、１……高速メモリ、２……コン
トローラ、３……マイクロプログラム回路、４…
…比較回路、５，６，７……インターフエース、
９……制御回路、１０……選択回路、１１……ロ
ード制御回路、１４……比較回路、１５，１６，
１８……増幅器、１９……管理回路、２０……
NANDゲート、２１……ANDゲート、AV……
仮想アドレス、RAV，RAR……高速メモリ、
PR_i……存在フラツグ、RF_i……参照フラツグ、
BPR_i……存在フリツプフロツプ、BRF_i……参照
フリツプフロツプ、HIT_i……一致信号。

Claims

【特許請求の範囲】１情報がアドレスによつて参照され、情報と組
み合わされたアドレスによつて形成される組が
「エントリ」と呼ばれる情報処理システムの主記
憶装置に含まれる情報にアクセスする方法であつ
て、このシステムは、各々が１つのエントリを記
憶することのできる複数のロケーシヨンRAR_i，
RAV_iによつて構成された高速メモリ１，RAR，
RAVを備え、上記エントリは各々所定の第１の
論理値に初期化された存在フラツグPR_iと参照フ
ラツグRF_iとに組み合わされており、上記存在フ
ラツグPR_iは対応するエントリが上記高速メモリ
中に存在すると第２の論理値を取り、該高速メモ
リ中に存在し、そのアドレスが探索中の情報のア
ドレスと一致するエントリを探索する連想読出し
によつて情報へのアクセスを実施し、上記参照フ
ラツグRF_iは組み合わされたエントリの使用を示
し、それによつて、探索しているが、まだ、上記
高速メモリ１，RAR，RAV中に存在していない
新規なエントリのロードのアルゴリズムを実施す
ることができる方法において、上記参照フラツグ
RF_iは、上記高速メモリ中に存在するエントリ数
が所定の閾値ｔより小さい限りその第１の論理値
に維持され、上記の存在するエントリ数が閾値ｔ
以上の時、上記の組み合わされたエントリが使用
されると、参照フラツグRF_iが第２の論理値にな
ることを特徴とする方法。２範囲を上記高速メモリの各ロケーシヨンに対
応させ、上記エントリは当初範囲が増大するロケ
ーシヨン内で時間的順序によつてロードされ、上
記範囲ｉが上記閾値ｔに等しいとき存在するフラ
ツグPR_iは上記閾値ｔに到達した表示をすること
を特徴とする請求項１に記載の方法。３探索中の情報が上記高速メモリに存在しない
と、該情報は上記主記憶装置中で探索され、上記
の対応するエントリは上記範囲がそのロードのア
ルゴリズムによつて決定されたロケーシヨンに配
置され、上記の組み合わされた存在フラツグPR_i
は上記ロードと同期化して第２の論理値にされ、
次に、探索中の情報の新規な連想的探索が実施さ
れることを特徴とする請求項１もしくは２に記載
の方法。４上記ロードアルゴリズムは、増大する順序で
上記存在フラツグPR_iが上記の所定の第１の論理
値である第１のエントリ、または、そうでなけれ
ば、上記参照フラツグRF_iが上記の所定の第１の
論理値である第１のエントリの範囲を探索するこ
とを特徴とする請求項３に記載の方法。５上記システムはページ化された仮想アドレス
機構を備え、上記エントリの各々のアドレスはペ
ージの仮想アドレスであり、上記の組み合わされ
た情報は該ページの実アドレスであることを特徴
とする請求項１〜４のいずれか１項に記載の方
法。６上記主記憶装置はページで管理され、上記の
各エントリのアドレスはページの実アドレスであ
り、上記の組み合わされた情報は該ページに含ま
れるデータによつて構成されていることを特徴と
する請求項１〜４のいずれか１項に記載の方法。７主記憶装置へのアドレツシングによつてアク
セスすることのできる処理手段１，２，３を備え
る情報処理システムであつて、該主記憶装置中に
含まれるアドレスとそれに組み合わされた情報と
によつて形成された組が「エントリ」と呼ばれ、
上記処理手段１，２，３は複数のロケーシヨン
RAR_i，RAV_iによつて構成された高速メモリ１，
RAR，RAVを備え、このロケーシヨンは各々上
記エントリの１つに記憶することができ、各々、
当初第１の論理値に設定された存在フリツプフロ
ツプBPR_i及び参照フリツプフロツプBRF_iに接続
され、エントリが上記の接続されたロケーシヨン
にロードされた時上記存在フリツプフロツプ
BPR_iは第２の論理値にされ、上記高速メモリ１，
RAR，RAVは探索中の情報のアドレスが上記ロ
ケーシヨンに存在するエントリのアドレスに一致
する第１の論理値を有する一致信号HIT_iを各ロ
ケーシヨンに出力することのできる比較手段４，
１４に接続されており、上記システムは、上記高
速メモリ中に存在するエントリ数が所定の閾値以
上であるかどうかをその論理値が示す閾値信号Ｖ
を発生させる閾値検出手段２０を備え、各存在す
るエントリごとに、上記の接続された参照フリツ
プフロツプBRF_iの状態は、上記一致信号HIT_iが
一致を示し、同時に、上記閾値信号Ｖが閾値ｔに
達したことを示す時、該参照フリツプフロツプ
BRF_iを第２の論理状態にする管理回路１９，１
９Ａ，GRFによつて制御されていることを特徴
とするシステム。８上記高速メモリ中にまだ存在しないエントリ
をロードするためのロケーシヨンを選択するため
に、各存在フリツプフロツプBPR_iまたは参照フ
リツプフロツプBRF_iは要求信号VP_i，RP_iの伝播
回路CPに接続されており、範囲ｉが各ロケーシ
ヨンRAR_i，RAV_iに割り当てられており、上記
存在フリツプフロツプBPR_iまたは参照フリツプ
フロツプBRF_iに接続された伝播回路CPは各々縦
続接続されており、上記の最後の存在フリツプフ
ロツプBPR_oに接続された伝播回路CPの出力は上
記の最小の参照フリツプフロツプBRF_iに接続さ
れた伝播回路の入力BCPに接続されており、各
伝播回路CPは上流の要求信号VP_i-1，RP_i-1が要
求の存在を示し、上記の接続されたフリツプフロ
ツプBPR_i，BRF_iが所定の第２の論理状態にある
時、要求の存在を示す信号VP_i，RP_iを発生させ、
上記第１の存在フリツプフロツプBPR₁に接続さ
れた伝播回路CPには常に要求の存在を示す信号
が入力され、上記ロケーシヨンのフリツプフロツ
プBPR_i，BRF_iの１つに接続された上流の要求信
号VP_i-1，RP_i-1が要求の存在を示し、該フリツ
プフロツプBPR_i，BRF_iが上記の所定の第１の状
態にある時、上記ロケーシヨンは各々該ロケーシ
ヨンの選択を示す信号S_iを発生させる選択回路
CSに接続されていることを特徴とする請求項７
に記載のシステム。９上記閾値検出手段２０は、範囲が上記の予め
決定された閾値ｔに等しいロケーシヨンに接続さ
れた上記存在フリツプフロツプBPR_tの状態信号
を使用することを特徴とする請求項８に記載のシ
ステム。１０ページ化された仮想メモリ機構を備え、上
記の各エントリのアドレスは仮想アドレスであ
り、上記の組み合わされた情報は実アドレスであ
り、該メモリ１，RAV，RARは仮想アドレスレ
ジスタRAV_iと実アドレスレジスタRAR_iとによ
つて構成されていることを特徴とする請求項７〜
９のいずれか１項に記載のシステム。