(57)【要約】ＲＡＭと合成可能論理回路とを使用して形成される変換索引バッファ（ＴＬＢ）が開示される。ＴＬＢは、受信仮想アドレスから物理アドレスへの変換を見つけるために検索しなければならないメモリ・ロケーションの数を減らすため、合成可能論理回路内に論理回路を提供する。この論理回路は、受信仮想アドレスをハッシュするためのハッシュ回路を提供し、ＲＡＭを索引づけるハッシュされた仮想アドレスを使用して、変換を提供するＲＡＭ内のラインを見つける。
2005538465.tif 000002
【特許請求の範囲】
【請求項１】
仮想アドレスの部分を受信する少なくとも１つの入力ポートと、
ランダム・アクセス・メモリと、
１組のレジスタと、
前記仮想アドレスの受信部分からハッシュ値を決定し、前記ハッシュ値を前記１組のレジスタ内に格納されているハッシュ値と比較して、前記仮想アドレスに関係づけられた物理アドレスが、前記ランダム・アクセス・メモリ内のラインに格納されておりかつ１組のレジスタのうちハッシュ値が格納されているレジスタに関連づけられている可能性を判定する合成可能論理回路とを含む変換索引バッファ。
【請求項２】
前記合成可能論理回路は、ページ・サイズを表す少なくとも１つのページ・サイズ信号を受信し、前記少なくとも１つのページ・サイズ信号から、前記ハッシュ値を決定する際に使用する少なくとも１つのマスク・ビットを決定する符号器回路を含むことを特徴とする請求項１に記載の変換索引バッファ。
【請求項３】
前記合成可能論理回路は、出力ポートを含み、前記仮想アドレスの受信部分と前記少なくとも１つのマスク・ビットとを受信する第１のハッシュ回路を含み、
前記第１のハッシュ回路は、前記仮想アドレスの受信部分と前記少なくとも１つのマスク・ビットから第１のハッシュ値を確定的に発生させ、前記第１のハッシュ値を該第１のハッシュ回路の前記出力ポートに提供することを特徴とする請求項２に記載の変換索引バッファ。
【請求項４】
前記合成可能論理回路は、前記少なくとも１つのマスク・ビットを格納する少なくとも１つのレジスタを含むことを特徴とする請求項３に記載の変換索引バッファ。
【請求項５】
前記合成可能論理回路は、前記仮想アドレスの部分と前記少なくとも１つのレジスタからの少なくとも１つの格納マスク・ビットとを受信する第２のハッシュ回路を含み、
前記第２のハッシュ回路は、ハッシュ値を決定することを特徴とする請求項４に記載の変換索引バッファ。
【請求項６】
比較器を含み、
前記ランダム・アクセス・メモリは、該ランダム・アクセス・メモリに格納された変換表を含み、
前記ラインは、前記変換表内に格納され、
前記ハッシュ値は、前記仮想アドレスが前記変換表内の関連づけられたラインに存在するかどうかを決定するために前記比較器内で比較され、前記関連づけられたライン内の仮想アドレスについて、肯定表示は適合の可能性ありを表し、否定表示は適合の可能性なしを表すことを特徴とする請求項５に記載の変換索引バッファ。
【請求項７】
第３のハッシュ回路を含み、
前記第３のハッシュ回路は、前記仮想アドレスの部分と前記少なくとも１つのレジスタからの少なくとも１つの格納マスク・ビットとを受信し、前記第２のハッシュ回路と並列動作してハッシュ・ベクトルを決定し、
前記ハッシュ・ベクトルは、前記ランダム・アクセス・メモリ内の少なくとも２つのライン用に確定的に発生させられたハッシュ値を格納することを特徴とする請求項５に記載の変換索引バッファ。
【請求項８】
前記第１のハッシュ回路は、前記仮想アドレスと少なくとも１つの取得マスク・ビットを事前にハッシュして、事前ハッシュ値を前記第２および第３のハッシュ回路に提供することを特徴とする請求項７に記載の変換索引バッファ。
【請求項９】
少なくとも１つの第２のレジスタを含み、
前記少なくとも１つの第２のレジスタは、前記ハッシュ値と前記メモリ内の関連づけられたラインとの比較結果を格納し、
前記比較結果は、前記関連づけられたライン内の仮想アドレスについて、適合の可能性ありを表す肯定表示、適合の可能性なしを表す否定表示を提供することを特徴とする請求項８に記載の変換索引バッファ。
【請求項１０】
複数の前記少なくとも１つの第２のレジスタが、前記変換索引バッファのメモリのライン数以上の数のレジスタを含むことを特徴とする請求項９に記載の変換索引バッファ。
【請求項１１】
前記合成可能論理回路は、複数のハッシュ値と各々がメモリ内のラインに関連づけられた複数の期待ハッシュ値とを比較して、前記仮想アドレスの変換がメモリ内の関連づけられた各ライン内に格納されている可能性を決定する複数の比較器を含み、
前記比較器は、共同して、メモリ内の各ラインに関連づけられた値を含むベクトルを提供することを特徴とする請求項１に記載の変換索引バッファ。
【請求項１２】
前記合成可能論理回路は、前記変換を含むメモリ内のラインの可能性変換を表す複数の値間で解決を図るための解決回路を含むことを特徴とする請求項１１に記載の変換索引バッファ。
【請求項１３】
変換が現在格納されている仮想アドレス以外の仮想アドレスをハッシュしてハッシュ値を決定し、前記ハッシュ値をメモリ内の利用可能ラインに関連づけられたレジスタに格納するハッシュ回路を含み、
前記ハッシュ回路は、前記仮想アドレスおよびその変換をメモリ内の前記利用可能ラインに格納することを特徴とする請求項１に記載の変換索引バッファ。
【請求項１４】
ランダム・アクセス・メモリと、
前記ランダム・アクセス・メモリ内のラインに関連づけられた第１のレジスタと、
変換が前記ランダム・アクセス・メモリに現在格納されている仮想アドレス以外の仮想アドレスを受信し、ハッシュ値を決定し、前記ハッシュ値を前記第１のレジスタに格納するハッシュ回路とを含み、
前記ハッシュ回路は、前記仮想アドレスとその変換をメモリ内の前記ラインに格納することを特徴とする変換索引バッファ。
【請求項１５】
ＲＡＭと、
仮想アドレスに関連づけられた物理アドレスを検索するために、前記仮想アドレスからそれに固定的に関連づけられた前記ＲＡＭ内の少なくとも１つの可能性アドレスを決定する合成可能論理回路とを含み、
前記少なくとも１つの可能性アドレスは、前記仮想アドレスに関連づけられた前記物理アドレスが固定的に関連づけられて格納される前記ＲＡＭ内の或るまたは唯一既知のアドレスとは異なるアドレスであることを特徴とする変換索引バッファ。
【請求項１６】
前記合成可能論理回路は、前記仮想アドレスをハッシュして、前記仮想アドレスの変換を検索し始める前記ＲＡＭ内のラインを表す値を決定するハッシュ回路を含むことを特徴とする請求項１５に記載の変換索引バッファ。
【請求項１７】
前記合成可能論理回路は、前記ＲＡＭ内の複数のライン内に格納された仮想アドレス・データを前記仮想アドレスと繰り返し比較し、前記仮想アドレスの変換の存在を判定する探索解決回路を含み、
前記探索解決回路は、その出力ポートに解決された変換を提供することを特徴とする請求項１６に記載の変換索引バッファ。
【請求項１８】
前記探索解決回路は、連続する比較動作間に１ラインずつ前記メモリ内のライン・アドレスをインクリメントする増加回路を含むことを特徴とする請求項１７に記載の変換索引バッファ。
【請求項１９】
前記探索解決回路は、連続する比較動作間に１ラインずつ前記メモリ内のライン・アドレスを変更するハッシュ回路を含むことを特徴とする請求項１７に記載の変換索引バッファ。
【請求項２０】
ＲＡＭと合成可能論理回路とを含む変換索引バッファに関する仮想アドレス検索機能を実行する方法であって、
仮想アドレスを前記合成可能論理回路に提供するステップと、
前記提供された仮想アドレスをハッシュしてハッシュ結果を取得するステップと、
前記ハッシュ結果に基づいて、仮想アドレス識別子とそれに関連する物理アドレスが格納されている前記ＲＡＭ内のメモリ・ロケーションを決定するステップと、
前記仮想アドレスを前記仮想アドレス識別子と比較して、前記物理アドレスが前記提供された仮想アドレスに対応しているかどうかを決定するステップと、
前記物理アドレスが前記提供された仮想アドレスに対応している場合、前記物理アドレスを出力値として提供するステップとを含む方法。
【請求項２１】
メモリ・ロケーションを決定する前記ステップは、
前記ハッシュ結果をＲＡＭ内のラインに関連づけられた既知のハッシュ結果と比較して、比較結果を決定するステップと、
複数の値を含むヒット・ベクトルを形成するステップであって、各々の値は、前記既知のハッシュ結果に関連づけられたＲＡＭ内の前記ラインに関連づけられ、各々の値は、前記値が関連づけられたＲＡＭ内の前記ラインが前記仮想アドレスの変換を含むことの尤度に関連するステップとを含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
前記決定ステップは、前記ＲＡＭ内の各ライン毎に実行されることを特徴とする請求項２１に記載の方法。
【請求項２３】
前記比較ステップは、前記変換を含むラインが見つかるまで、前記仮想アドレスの可能性変換を表す値に関連づけられたＲＡＭ内の異なるライン毎に連続的に実行されることを特徴とする請求項２２に記載の方法。
【請求項２４】
前記判定ステップは、前記ＲＡＭ内の各ライン毎に実行されることを特徴とする請求項２０に記載の方法。
【請求項２５】
メモリ内のラインは、単一の仮想アドレスから単一の対応する物理アドレスへの単一アドレス変換を含むことを特徴とする請求項２４に記載の方法。
【請求項２６】
前記ハッシュ・ステップは、前記仮想アドレスとメモリ内の各ラインに関連づけられた格納値とをハッシュして、メモリ内の各ラインに関連づけられたハッシュ値を独立に決定するステップを含むことを特徴とする請求項２０に記載の方法。
【請求項２７】
メモリ内のラインは、単一の仮想アドレスから単一の対応する物理アドレスへの単一アドレス変換を含むことを特徴とする請求項２６に記載の方法。
【請求項２８】
前記ハッシュ・ステップは、前記仮想アドレスを事前ハッシュするステップと、前記事前ハッシュされた仮想アドレスをメモリ内のラインに関連づけられた複数の格納値の各々と独立に結合して、ＲＡＭ内の各ラインに関連づけられたハッシュ値を独立に決定するステップとを含むことを特徴とする請求項２０に記載の方法。
【請求項２９】
前記比較ステップは、前記変換を含むラインが見つかるまで、前記仮想アドレスの可能性変換を表す値に関連づけられたＲＡＭ内の異なるライン毎に連続的に実行されることを特徴とする請求項２８に記載の方法。
【請求項３０】
メモリ内のラインは、単一の仮想アドレスから単一の対応する物理アドレスへの単一アドレス変換を含むことを特徴とする請求項２８に記載の方法。
【請求項３１】
前記ハッシュ・ステップは、前記仮想アドレスをハッシュして、前記仮想アドレスの変換を格納している可能性のあるＲＡＭ内のラインを表す値を決定するステップを含むことを特徴とする請求項２０に記載の方法。
【請求項３２】
前記比較ステップは、前記仮想アドレスの変換が見つかるまで、前記決定された値に関連するＲＡＭ内のラインから始まる既知の順番で、ＲＡＭ内の複数のラインを繰り返し比較するステップを含むことを特徴とする請求項３１に記載の方法。
【請求項３３】
前記既知の順番は、連続する比較の間に１ラインずつインクリメントすることを特徴とする請求項３２に記載の方法。
【請求項３４】
前記既知の順番は、前記決定された値に基づく関数を計算することにより決定されることを特徴とする請求項３２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変換索引バッファの分野に関し、より詳細には、設計サイクルを迅速化するための変換索引バッファ構成に関する。
【背景技術】
【０００２】
現在のマイクロプロセッサ・システムは一般に、仮想アドレス指定を利用する。仮想アドレス指定を利用することで、システムは、実物理メモリ空間よりも広い仮想メモリ空間を効果的に生成することができる。実物理メモリ空間を仮想メモリ空間に分割するプロセスは、ページングと称される。ページングは、物理メモリ空間の線形アドレス空間を、ページと呼ばれる固定ブロックに分割する。ページは、広大な線形アドレス空間を、より狭い物理メイン・メモリと安価なバックグラウンド・メモリとを用いて実現することを可能にする。この構成は、「仮想メモリ」と呼ばれる。ページングは、バックグラウンド・メモリとの間でスワップ・アウトおよびスワップ・インされるページ内のメモリを管理することによって、仮想メモリを実施できるようにする。ページングには、メイン・メモリのフラグメンテーションが減少する、ページ毎にメモリ書き込み方針を選択できる、ページ毎にメモリ保護方式を変更できるといった、さらなる利点もある。ページング機構の存在は典型的に、アプリケーション・プログラムからは透過的である。
【０００３】
ページ・サイズは、柔軟性および性能とトレードオフの関係にある。ページ・サイズが小さければ、仮想メモリ・システムをよりきめ細かく制御できるが、ページング動作時のオーバヘッドは増大する。したがって、多くのＣＰＵは、ページ・サイズの混在をサポートする。例えば、特定のＭＩＰＳ実装は、４ｋＢ、１６ｋＢ、６４ｋＢ、２５６ｋＢ、１ＭＢ、４ＭＢ、１６ＭＢのページのうちの任意の混在をサポートする。
【０００４】
プロセッサは有利には、仮想アドレスを使用して仮想アドレス空間内で動作することができる。しかし、これらの仮想アドレスは頻繁に、物理アドレス、すなわち実メモリ・ロケーションに変換しなければならない。仮想アドレスから物理アドレスへのこの変換を実現する１つの方法は、変換表を使用するものであり、変換表は、定期的にアクセスされ、メイン・メモリに格納される。変換表は、一般にサイズが大きいので、メイン・メモリに格納される。残念ながら、メイン・メモリに格納された変換表に定期的にアクセスすると、システムの全体的な性能が低下しがちになる。
【０００５】
現在のマイクロプロセッサ・システムは、アドレス変換を行うためにメイン・メモリ内の変換表を定期的にアクセスしなくてもすむように、最近生成された仮想アドレスから物理アドレスへの変換を格納またはキャッシュする変換索引バッファ（ＴＬＢ）を頻繁に利用する。ＴＬＢは、特殊なタイプのキャッシュ・メモリである。その他のタイプのキャッシュ・メモリと同様に、ＴＬＢは一般に、高速アクセスが可能なように特別に設計された、比較的小容量のメモリ記憶部から構成される。ＴＬＢは典型的に、キャッシュ・メモリ内に備えられた、タグ・アレイおよびデータ・アレイの両方を内蔵している。タグ・アレイ内では、各タグ・ラインが仮想アドレスを格納する。次に、このタグ・ラインは、データ・アレイ内の対応するデータ・ラインに関連づけられ、データ・アレイには、仮想アドレスを変換した物理アドレスが格納される。したがって、メイン・メモリ内の変換表から仮想アドレスの変換アドレスを探し出す前に、プロセッサは、まず、ＴＬＢを参照して、当該仮想アドレスを変換した物理アドレスが現在ＴＬＢに格納されているかどうかを決定する。当該仮想アドレスおよびそれに対応する物理アドレスがＴＬＢに格納されている場合、ＴＬＢが対応する物理アドレスをＴＬＢの出力ポートに出力するので、時間およびリソースを消費するメイン・メモリのアクセスを行わずにすむ。ＴＬＢの動作を円滑化し、ＴＬＢの索引づけの必要性を減らすために、典型的に連想記憶メモリ（ＣＡＭ）がＴＬＢ内に備えられる。ＣＡＭは並列パターン・マッチング回路である。マッチング・モードで動作中、ＣＡＭは、そのすべてのデータを並列にサーチして、適合データ（match）を見つけることができる。
【０００６】
残念ながら、従来のＴＬＢでは、ＣＡＭを実装するために、カスタム回路設計技法を必要とする。カスタム回路設計を用いた場合、プロセッサ・システム設計において同じものを実現するのに、ＴＬＢおよび関連ＣＡＭ毎に多大な設計努力を必要とするので、これは有利とは言い難い。もちろん、プロセッサにＣＡＭ回路が無いと、プロセッサからの信号はチップからＣＡＭに伝播することになるので、遅延が生じることになる。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
したがって、本発明の目的は、従来の合成可能回路ブロックから形成されるＣＡＭ構成を提供することである。
【課題を解決するための手段】
【０００８】
本発明によれば、仮想アドレスの部分を受信する少なくとも１つの入力ポートと、
ランダム・アクセス・メモリと、１組のレジスタと、合成可能論理回路とを含む変換索引バッファ（ＴＬＢ）が提供され、合成可能論理回路は、仮想アドレスの受信部分からハッシュ値を決定し、そのハッシュ値を１組のレジスタ内に格納されているハッシュ値と比較して、仮想アドレスに関係づけられた物理アドレスが、ランダム・アクセス・メモリ内のラインに格納されておりかつ１組のレジスタのうちハッシュ値が格納されているレジスタに関連づけられている可能性を判定する。
【０００９】
本発明の一態様によれば、ランダム・アクセス・メモリと、前記メモリ内のラインに関連づけられた第１のレジスタと、ハッシュ回路とを含む変換索引バッファが提供され、ハッシュ回路は、変換アドレスがメモリに現在格納されている仮想アドレス以外の仮想アドレスを受信し、ハッシュ値を決定し、そのハッシュ値を第１のレジスタに格納し、さらに、ハッシュ回路は、仮想アドレスおよびその変換をメモリ内のラインに格納する。
【００１０】
本発明のさらに別の態様によれば、ＲＡＭと、合成可能論理回路とを含む変換索引バッファが提供され、合成可能論理回路は、仮想アドレスに関連づけられた物理アドレスを検索するために、仮想アドレスからそれに固定的に関連づけられたＲＡＭ内の少なくとも１つの可能性アドレスを決定し、少なくとも１つの可能性アドレスは、仮想アドレスに関連づけられた物理アドレスが固定的に関連づけられて格納されるＲＡＭ内の或るまたは唯一既知のアドレスとは異なるアドレスである。
【００１１】
本発明のさらに別の態様によれば、ＲＡＭと合成可能論理回路とを含む変換索引バッファ用の仮想アドレス検索機能を実行する方法が提供され、この方法は、仮想アドレスを合成可能論理回路に供給するステップと、供給された仮想アドレスをハッシュして、ハッシュ結果を取得するステップと、
ハッシュ結果に基づいて、仮想アドレス識別子とそれに関連する物理アドレスが格納されているＲＡＭ内のメモリ・ロケーションを決定するステップと、
仮想アドレスと仮想アドレス識別子とを比較して、物理アドレスが供給された仮想アドレスに対応しているかどうかを決定し、物理アドレスが供給された仮想アドレスに対応している場合、その物理アドレスを出力値として提供するステップとを含む。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照しながら本発明を説明する。
【００１３】
ＣＡＭ回路は、ＳＲＡＭ回路と構造的に類似した記憶回路を含む。しかし、ＣＡＭ回路は、追加の利点である並列検索モードでの動作を提供する検索回路をも含み、そのため、ハードウェアを使用して並列にＣＡＭの内容を検索することができる。特定のデータ値を求めてＣＡＭを検索する場合、ＣＡＭは、そのデータ値と適合する値をＣＡＭ内に見つけると、適合データを提供する。ＣＡＭとＳＲＡＭの主たる相違は、ＣＡＭでは、仮想アドレスを表すデータがＣＡＭに提示され、そのデータに関連するアドレスが返されるのに対し、ＳＲＡＭでは、アドレスがＳＲＡＭに提供され、そのアドレスに格納されているデータが返される。
【００１４】
ＣＡＭのセルは、セルからなる各行がメモリ・アドレスを保持し、セルからなるその行がマッチ・ラインによってデータ・アレイのうち対応するワード・ラインに接続されて、適合データ（match）が前記マッチ・ライン上で発生したときに、データ・アレイの前記ワード・ラインにアクセスできるように配列される。フル・アソシアティブ・キャッシュの場合、ＣＡＭの各行は、対応するメイン・メモリ・ロケーションの完全アドレスを保持し、ＣＡＭに入力するには、完全アドレスを入力する必要がある。
【００１５】
Ｓｔｅｖｅｎ  Ａ  Ｇｕｃｃｉｏｎｅ等による、「Ａ  Ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ」と題する従来技術に関する文献に、ＦＰＧＡ内でのＣＡＭの実施例が検討されている。従来技術を示す図１から分かるように、トランジスタ・レベルで、ＣＡＭ回路１０１の実施例は、標準的なＳＲＡＭ１００と非常に類似している。ＣＡＭ回路とＳＲＡＭ回路の両者はほとんど同じであり、各々６個のトランジスタ１０２を有するが、ＣＡＭ１０１がさらに、並列検索機能を提供する３個のマッチング用トランジスタ１０３を有する点で異なる。残念ながら、標準的なプログラム可能論理回路を使用したのでは、このようなトランジスタ・レベルの回路を容易に実施することはできない。
【００１６】
上記従来技術の文献において、ＦＰＧＡ内でのＣＡＭの実施例が検討されている。ゲート・レベルの論理回路を使用してＣＡＭを実施すると、ＣＡＭを所望のサイズにすることができないことが多い。ＣＡＭ内ではデータ記憶素子としてフリップ・フロップが使用されるが、その結果、ＦＰＧＡを使用して達成可能なＣＡＭ回路のサイズは、ＦＰＧＡ内で利用可能なフリップ・フロップの数に依存する。ＦＰＧＡ内でのＣＡＭの実施は、ＦＰＧＡのリソースの多くをすぐに使い果たしてしまうため、実現可能な解決策とはならない。残念ながら、このことが影響して、これまで設計者たちは、ＣＡＭはトランジスタ・レベルでのみ効率的に実施できると結論づけてきた。
【００１７】
上記の従来技術に関する文献では、ＦＰＧＡ内で参照表（ルックアップテーブル（ＬＵＴ））を使用したＣＡＭの実装についても説明されている。適合対象のデータを格納するのにＦＰＧＡ内でフリップ・フロップを使用する代わりに、この実装では、適合対象のデータを格納するのにＬＵＴを使用することで対処している。フリップ・フロップの代わりにＬＵＴを使用することによって、ＣＡＭ構成をより小さくすることができる。
【００１８】
残念ながら、合成可能素子からＣＡＭを形成することは簡単には成し得ないため、ＣＡＭを提供する従来技術のプロセッサは、その内部にＣＡＭコアを備えている。プロセッサ内部にＣＡＭコアを設けると、設計の複雑さが増すため、出来上がった回路は高価になる。設計の複雑さが増すことは、少量生産されるカスタム設計のプロセッサには不適当である。
【００１９】
図２に、仮想アドレス（ＶＡ）２０１から物理アドレス（ＰＡ）２０２への変換プロセスを示す。ＶＡ２０１は、３２ビット・アドレス、ＶＡ［３１：０］であり、ＰＡ２０２も、３２ビット・アドレス、ＰＡ［３１：０］である。ＶＡは、仮想ページ番号（ＶＰＮ）２０３とページ・オフセット（ＰＯ）２０４の２つの部分を有する。ＶＰＮ２０３は、代表的には、ＶＡ２０１の上位部分に配置され、ＰＡ２０２は、代表的には、ＶＡ２０１の下位部分に配置されるが、こうする必然性があるわけではない。一般に、３２ビット・アドレス指定方式の場合、ＶＰＮは２０ビットであり、ＰＡは１２ビットである。ＰＡ、すなわち下位１２ビットは、直接的にＰＡに変換される。ＶＰＮ２０３は、ＴＬＢ２０５を索引づけて、ＴＬＢ２０５から物理ページ番号（ＰＰＮ）２０６を取り出すために使用される。言い換えると、ＶＰＮ２０３は、ＰＰＮ２０６へ変換される。ＰＡ２０２の上位部分のＰＰＮ２０６とＰＡ２０２の下位部分に移されたＰＯを合成することによって、ＶＡからＰＡへの変換が行われる。
【００２０】
図３に、直接対応キャッシュ・メモリ（direct mapped cache memory）３０１とともに実行されるときのＶＡ２０１からＰＡ２０２への変換を図示する。変換サイクルの始めに、ＶＡを使用して、キャッシュ・メモリ３０１およびＴＬＢ２０５が共にアクセスされる。ＶＡのページ・オフセット部分を使用して、キャッシュ・メモリ３０１がアクセスされる。このときページ・オフセットは、変換プロセスによって変更されない残りのアドレス部分である。ページ・オフセットは、キャッシュ・メモリ３０１内のタグ・アレイ３０２およびデータ・アレイ３０３を索引づけるために使用され、また、キャッシュ・メモリ３０１内のキャッシュ・ライン３０２ａを索引づけるために使用される。ＴＬＢ２０５へのアクセスは、ＶＡ２０１のＶＰＮ２０３部分を使用して実行される。ＴＬＢ２０５は、代表的に、ＴＬＢタグ・アレイ３０４とＴＬＢデータ・アレイ３０５とを含む。ＴＬＢタグ・アレイ３０４およびＴＬＢデータ・アレイ３０５は共に、ＶＰＮ２０３からのビットを含んでおり、両アレイにＶＰＮが提供されたとき、ＶＰＮからなるビットをアレイ３０４、３０５に格納されているビットと比較して、ＴＬＢ２０５内にエントリを発見するようになっている。
【００２１】
ＴＬＢデータ・アレイ３０５がアクセスされ、ＶＰＮとＴＬＢデータ・アレイ内のエントリ３０５ａとの間で適合データが見つかると、ＰＰＮ２０６が取り出されて、キャッシュ・メモリ３０１に供給され、タグ・アレイ３０２から取り出されたタグ３０２ａとの比較のために使用される。適合データは、キャッシュ「ヒット（hit）」３０６を表す。ＶＰＮ２０３とＴＬＢタグ・アレイ内のエントリ３０４ａとの間で適合データが見つかった場合、ＴＬＢヒット信号３０７が発生する。このようにして、キャッシュは、ＰＰＮ２０６のビットだけを使用してアクセスされる。上記の例では、直接対応キャッシュ・メモリを使用する場合を説明したが、ＶＡからＰＡへの同一変換は、セット・アソシアティブ・キャッシュを使用しても同様に行うことができる。セット・アソシアティブ・キャッシュを使用する場合、キャッシュ・ウェイのサイズが仮想ページのサイズ以下となることは、当業者であれば理解されよう。
【００２２】
残念ながら、ＴＬＢをＳＲＡＭに実装すると、ＣＡＭ機能をサポートするのに、網羅的なメモリ・サーチが必要となる。したがって、ＴＬＢが１０２４個の仮想アドレスおよびそれらに対応する物理アドレスを格納する場合、アドレス変換を行う毎に、最大１０２４回のメモリ・アクセスおよび比較動作が必要になる。そのようなＣＡＭ実装は、ＣＡＭサイズに伴い性能が線形的に低下するので、実用に耐えない。
【００２３】
図４ａに、合成可能論理コンポーネント４９９とランダム・アクセス・メモリ（ＲＡＭ）４１０とを使用して形成されたＴＬＢ４００を概略的に示す。変換を要するＶＰＮが、ＶＰＮ＿ＩＮ入力ポート４５０を介して供給されるが、ビットＶＰＮ＿ＩＮ［３１：１２］は、ＶＡ［３１：０］からこの入力ポート４５０に供給される。ページ・マスク信号が、ＣＰ０＿ＰＡＧＥ＿ＭＡＳＫ入力ポート４５１を介して供給される。ＣＰ０＿ＴＲＡＮＳＬＡＴＩＯＮ入力信号が、ＣＰ０＿ＴＲＡＮＳＬＡＴＩＯＮ入力ポート４５２を介して供給される。ＴＬＢ＿ＴＲＡＮＳＬＡＴＩＯＮ出力信号は、ＴＬＢ４００を使用するＶＡからＰＡへの変換に基づいて、ＴＬＢ＿ＴＲＡＮＳＬＡＴＩＯＮ出力ポート４５３を介して出力される。
【００２４】
図４ｂに、合成可能論理コンポーネントから形成されるＴＬＢ４００をより詳しく示し、図４ｃに、ＴＬＢ４００の動作ステップを要約して示す。ＴＬＢの動作をより詳しく説明すると、４８０において、変換を要するＶＰＮが、ＶＰＮ＿ＩＮ入力ポート４５０を介して供給され、ビットＶＰＮ＿ＩＮ［３１：１２］は、ＶＡ［３１：０］からこの入力ポート４５０にＶＰＮとして供給される。ページ・マスクが、ＣＰ０＿ＰＡＧＥ＿ＭＡＳＫ入力ポート４５１を介して供給される。このページ・マスクは、ページ・マスク符号器４０８に供給され、表１に従って符号化される。
【表１】
2005538465.tif 000003
表１．ページ・マスク符号化
【００２５】
ページ・マスク符号器４０８は、符号器の入力でＣＰ０＿ＰＡＧＥ＿ＭＡＳＫ入力信号を受信し、この入力信号を３ビット・ベクトルＭＡＳＫ［２：０］と相関させるために使用される。３ビット・ベクトルＭＡＳＫ［２：０］はさらに、ハッシュ回路４０６にも供給される。ハッシュ回路４０６は、第１の入力ポート４０６ａを介してＶＰＮ＿ＩＮ［３１：１２］を、第２の入力ポート４０６ｂを介してＭＡＳＫ［２：０］を受信する。ハッシュ回路４０６のハッシュ動作４８１によって、ハッシュ回路の出力ポート４０６ｃから、ハッシュ・ベクトルＨ＿ＶＰＮ［５：０］が出力される。ハッシュ・ベクトルＨ＿ＶＰＮ［５：０］およびＭＡＳＫ［２：０］はさらに、４８個のレジスタ４０９の各々に供給される。各レジスタは、まとめて４９１として参照される複数のフリップ・フロップから構成されている。各レジスタ４０９は、出力ポートを２つもっている。レジスタの第１の出力ポートからの第１の出力信号は、比較器回路４０３に供給される。第２の出力ポートからの第２の出力信号は、４８個のハッシュ回路４０６のうちの１つの第２の入力ポート４０６ｂに供給される。このハッシュ回路の第１の入力ポートは、ＶＰＮ＿ＩＮ［３１：１２］を受信する。ハッシュ回路４０６の出力ポートは、４８個の比較器回路４０３のうちの１つに結合され、レジスタ出力信号とハッシュ回路出力信号との比較が実行される。各比較器は、２つの入力信号の比較に基づいて、信号が同じであれば「１」を、異なっていれば「０」を出力する。４８個の比較器の各々からの出力信号ｈｉｔｉは、４８個の１ビット２入力マルチプレクサ４１１のうちの１つに供給される。各マルチプレクサの出力ポートは、フリップ・フロップ４０４に結合されている。各フリップ・フロップ４０４は、ｔｒｙｉ（０≦ｉ≦４７）と記された出力ポートで供給される出力信号を発生し、まとめてこれらの出力信号ｔｒｙ［０．．４７］は、優先符号器回路４０１に供給される。優先符号器回路はさらに、バイナリ復号器回路４０２に結合され、優先符号器回路は、バイナリ復号器回路４０２およびＲＡＭ４１０に送られるＴＬＢ＿ＥＮＴＲＹ［５：０］信号をアサートする。ＴＬＢ４００には、ＥＮＴＲＹ＿ＦＯＵＮＤ出力ポート４５４、ＥＮＴＲＹ＿ＮＯＴ＿ＦＯＵＮＤ出力ポート４５５、およびＴＢＬ＿ＴＲＡＮＳＬＡＴＩＯＮ出力ポート４５３の３つの出力ポートが設けられ、それぞれＥＮＴＲＹ＿ＦＯＵＮＤ出力信号、ＥＮＴＲＹ＿ＮＯＴ＿ＦＯＵＮＤ出力信号、およびＴＢＬ＿ＴＲＡＮＳＬＡＴＩＯＮ出力信号を出力する。
【００２６】
ＶＡからＰＡへの変換を要するアドレスは、ランダム・アクセス・メモリ（ＲＡＭ）４１０に格納され、ＲＡＭ４１０は好ましくは、ラインの形をとる４８個のエントリを有する。使用中、新たに変換を実行すべき場合はいつでも、入力信号ＶＰＮ＿ＩＮ、ＣＰ０＿ＰＡＧＥ＿ＭＡＳＫおよびＣＰ０＿ＴＲＡＮＳＬＡＴＩＯＮが、それぞれ入力ポート４５０、４５１、４５２を介して、ＴＬＢ回路４００に供給される。ＴＬＢが実行した変換は、与えられたインデックスｉを割り当てられてＲＡＭ４１０に格納される。与えられたインデックスは、ＰＰＮへの変換を保持するＲＡＭ４１０内のライン４１０ａの１つを索引づけする。ハッシュ回路４０６は、ハッシュ関数Ｈ（ＶＰＮ＿ＩＮ，ＭＡＳＫ）を計算し、その結果を対応する６ビット・レジスタｈｉ４９０に格納する。ページ・マスクは、３ビット・レジスタｍｉ４９１に格納される。
【００２７】
ＴＬＢを使用する変換が要求された場合、ＶＰＮが入力ポート４５０を介して供給され、ハッシュ関数Ｈ（ＶＰＮ＿ＩＮ，ｍｉ）がすべてのｉについて計算され、ｈｉと比較される。これによって、４８ビットのベクトル４９２  ｈｉｔ０．．ｈｉｔ４７が生成され、続いて、このベクトルは４８ビットのレジスタ４９３  ｔｒｙ０．．ｔｒｙ４７にロードされる。要求されたＶＰＮ＿ＩＮがＲＡＭ４８２に格納されている変換表に存在するかどうかを決定するために、ｔｒｙｉがアサートされたＲＡＭのエントリまたはラインだけがチェックされる。４８ビットのｔｒｙｉベクトルのエントリは、「１」の場合に４８３でアサートされる。もちろん、ｔｒｙｉベクトルに２以上のアサートされたビットがあってもよいが、優先符号器４０１が、最も小さいインデックスを有するエントリを選択して、ＲＡＭ内のエントリをアドレス指定する。復号器４０２は、このインデックスを４８ビットのワン・ホット（ｏｎｅ−ｈｏｔ）ベクトル４９４  ｃｌｒ０．．ｃｌｒ４７に変換する。クロック・パルスがクロック回路（図示せず）から到着したとき、ｔｒｙｉベクトルは、ＲＡＭをアドレス指定するのに使ったばかりのインデックスに対応する１ビットを除いて再ロードされ、その１ビットはクリアされる。このプロセスは、時点４８３ごとに１エントリずつ繰り返される。このプロセスは、４８４に示すように、要求されたエントリが見つかってすぐに停止するか、またはｔｒｙｉのすべてのビットが０になった場合に停止する。見つかった場合、ＥＮＴＲＹ＿ＦＯＵＮＤ出力ポート４５４上のＥＮＴＲＹ＿ＦＯＵＮＤ信号によってそのことが示される。ｔｒｙｉのすべてのビットが０になった場合、ＥＮＴＲＹ＿ＮＯＴ＿ＦＯＵＮＤ信号がＥＮＴＲＹ＿ＮＯＴ＿ＦＯＵＮＤ出力ポート４５５を介して出力される。最初のケースでは、変換は成功であり、４８５において、変換情報が、ＴＬＢ＿ＴＲＡＮＳＬＡＴＩＯＮ出力ポート４５３上のＴＬＢ＿ＴＲＡＮＳＬＡＴＩＯＮ信号を使用してＲＡＭ４１０から提供される。第２のケースでは、変換は不成功であり、ＴＬＢはＴＬＢ入れ替えの例外を報告する。
【００２８】
図５に、ハッシュ回路５０６をより詳しく示す。ハッシュ回路５０６に供給されるＭＡＳＫ［２：０］およびＶＰＮ［３１：１２］入力信号を使用して、７対１マルチプレクサ５０１は、第２の出力ポート５０６ｂに供給されるＭＡＳＫ［２：０］に応じて、Ｈ＿ＶＰＮ［５：０］出力信号をハッシュ回路５０６から出力する。このハッシュ回路は、ＶＰＮから６個の最下位ビットを選択する。「最下位」の定義はページ・サイズによって変化するので、選択はページ・マスクによって制御される。例えば、ページ・サイズが４ｋＢの場合、ＶＰＮの６個の最下位ビット（ＬＳＢ）は、ビット２２：１７であるが、ページ・サイズが１６ｋＢの場合、６個のＬＳＢは、ビット１９：１４である。ＴＬＢ４００は、ＴＬＢエントリ毎に奇数／偶数ペアと呼ばれる２つの隣り合う仮想ページを格納するので、４ｋＢページの奇数／偶数ペアの場合の６個のＬＳＢは、ビット１８：１３となる。したがって、ビット１２は、偶数（０）変換を返すか、または奇数（１）変換を返すかを決定する。１６ｋＢページの奇数／偶数ペアの場合、ビットは２０：１５となる。しかし、ビットＨ＿ＶＰＮ［５：０］の順序づけは問題とされないので、このハッシュ関数は冗長である。図６は、ビットの順序づけが問題とされない事実を利用している。
【００２９】
図６に、図５に示したハッシュ回路の変形例を示す。ＶＰＮ［３２：１２］信号は、第１の入力ポート６０６ａに供給され、ＭＡＳＫ［２：０］信号は、第２の入力ポート６０６ｂに供給される。マスク信号ＭＡＳＫ［２：０］は、ビットｍ０、ｍ１、ｍ２から構成される。このハッシュ回路６０６内には、３つの３対１マルチプレクサ６０１〜６０３が存在する。第１のマルチプレクサ６０１は、選択入力ポート上で以下のビット
【数１】
2005538465.tif 000004
を受信し、ＶＰＮ中のビットであるＶＰＮ［１３：１４］、ＶＰＮ［１９：２０］、ＶＰＮ［２５：２６］が、それぞれマルチプレクサのデータ入力ポート０から２に供給される。その結果、マルチプレクサ６０１は、Ｈ＿ＶＰＮ［５：０］出力信号にビット５および４を供給する。第２のマルチプレクサ６０２は、選択入力ポート上で以下のビット
【数２】
2005538465.tif 000005
を受信し、ＶＰＮ中のビットであるＶＰＮ［１５：１６］、ＶＰＮ［２１：２２］、ＶＰＮ［２７：２８］が、それぞれマルチプレクサの０から２と表示したデータ入力ポートに供給される。その結果、マルチプレクサ６０２は、Ｈ＿ＶＰＮ［５：０］出力信号にビット３および２を供給する。第３のマルチプレクサ６０３は、選択入力ポート上で以下のビット
【数３】
2005538465.tif 000006
を受信し、ＶＰＮ中のビットであるＶＰＮ［１７：１８］、ＶＰＮ［２３：２４］、ＶＰＮ［２９：３０］が、それぞれマルチプレクサの０から２と表示したデータ入力ポートに供給される。その結果、マルチプレクサ６０３は、Ｈ＿ＶＰＮ［５：０］出力信号にビット１および０を供給する。
【００３０】
好ましくは、ハッシュ関数Ｈ＿ＶＰＮ［５：０］は、ＭＡＳＫ［２：０］およびＶＰＮ＿ＩＮ［３１：１２］入力信号に関して一様に分布する。ＴＬＢミスの場合、どのｔｒｙｉを最初にアサートするか決めるため、ＲＡＭ内のすべてのエントリが検索される。サイクル数Ｎｍｉｓｓは、以下の式で与えられる。
【数４】
2005538465.tif 000007
ただし、ｐは比較器の出力信号ｈｉｔｉがアサートされる確率である。項
【数５】
2005538465.tif 000008
は、トライ・ベクトルｔｒｙｉの中のちょうどｊ個のビットが最初にアサートされる確率を与える。ハッシュ関数の出力信号がｎビットである一様なハッシュ関数Ｈの場合、ｐ＝２−ｎであり、図４ｂの場合、ｎ＝６である。
【００３１】
ＴＬＢヒットの場合、トライ・ベクトルｔｒｙｉが０だけしか含まないためにＲＡＭにアクセスすることなく検出されるＴＬＢミス条件の場合とは反対に、ＲＡＭ４１０へのアクセスが少なくとも１回は必要とされる。
【００３２】
ＴＬＢ内でヒットが生じる変換を実行する平均サイクル数は、以下の式で与えられる。
【数６】
2005538465.tif 000009
【００３３】
ＴＬＢヒットの場合、トライ・ベクトルｔｒｙｉの中に少なくとも１つ「１」が存在しなければならない。唯一の不確定は、ベクトル内の残りの要素についてである。０．．．４７の範囲にある変数ｋは、トライ・ベクトルｔｒｙｉの中で「１」に設定された残りのエントリの数を表すのに使用される。ｋ＝０の場合、ＲＡＭ内の１つのエントリだけが調べられる。したがって、１クロック・サイクルはｉ＝０の第１のロケーションで変換を見つけるのに使用されるので、全部で２クロック・サイクルが変換を実行するのに使用される。ＲＡＭ４１０から要求された変換を返すのに、平均で２＋ｋ／２サイクルかかる。
【００３４】
変換の実行および割り込み応答時間に関して、必要とされるクロック・サイクル数は、例えば、ｋを２５以上とする長い探索シーケンスにわたって調べられる。以下の関係式
【数７】
2005538465.tif 000010
は、ＴＬＢが変換を完了するのに２５サイクル以上を費やす確率を与える。表２に、いくつかのハッシュ関数幅（ｎ）について、変換を見つけるのに要する平均サイクル数Ｎｈｉｔ、ミスを検出するための平均サイクル数Ｎｍｉｓｓ、およびＴＬＢ動作が２５サイクル以上を費やす確率を示す。
【表２】
2005538465.tif 000011
表２．ハッシュ・ビット数「ｎ」の関数としてのＴＬＢ応答時間
【００３５】
表２から、Ｐ｛Ｎ２５｝はきわめて小さく、４ビット・ハッシュ関数の場合であっても、ＴＬＢ変換が２５から４８クロック・サイクルを必要とするような場合に遭遇するには、連続的に動作して６０００年より長くかかることが分かる。
【００３６】
欄Ｎｈｉｔｑ（「ヒット・クイック」）は、ＶＰＮ＿ＩＮがＴＬＢ回路４００に継続して与えられる場合に適用される。この表から、最も重要な数であるＮｈｉｔに注目するならば、ｎ＝５またはｎ＝６であれば十分であることが分かる。ｎ≧２０のとき、Ｎｈｉｔは２．０に接近するので、６ビットよりビット数を増やしても、あまり得るところはない。ハッシュ関数があまり一様でないこともあるので、ＴＬＢ回路４００では、値ｎ＝６が使用される。したがって、ＴＬＢ内で使用される６ビットのハッシュ関数は、真に一様な５ビットのハッシュ関数の性能に近い。
【００３７】
有利には、ＶＡは、ＴＬＢに供給されたとき、各ライン毎に合成論理回路に伝えられ、結果として、ビットからなるｔｒｙｉベクトル内の少なくとも１つのアサート・ビットによって表される。適合データを表す結果が生じたラインだけが、ＰＰＮを提供するために物理的にアクセスされる。このようにすると、ＴＬＢラインのわずかな部分だけしか、変換プロセスのためにアクセスされず、その結果、著しい性能の向上が実現される。
【００３８】
数々のその他の実施形態も、本発明の主旨および範囲から逸脱しないものと見なすことができる。
【図面の簡単な説明】
【００３９】
【図１ａ】従来技術によるＳＲＡＭ回路のトランジスタの実施例を示した図である。
【図１ｂ】従来技術によるＣＡＭ回路のトランジスタの実施例を示した図である。
【図２】従来技術による仮想アドレス（ＶＡ）から物理アドレス（ＰＡ）への変換プロセスを示した図である。
【図３】直接対応キャッシュ・メモリを併用して実行される、従来技術によるＶＡからＰＡへの変換を示した図である。
【図４ａ】合成可能論理コンポーネントとランダム・アクセス・メモリを使用して形成される変換索引バッファを概略的に示した図である。
【図４ｂ】合成可能論理コンポーネントから形成される変換索引バッファをより詳しく示した図である。
【図４ｃ】ＴＬＢの動作で採用されるステップの概要を示した図である。
【図５】ハッシュ回路をより詳しく示した図である。
【図６】図５に示すハッシュ回路の変形例の回路図である。
【図１ａ】
2005538465.tif 000012
【図１ｂ】
2005538465.tif 000013
【図２】
2005538465.tif 000014
【図３】
2005538465.tif 000015
2005538465.tif 000016
2005538465.tif 000017
【図４ｃ】
2005538465.tif 000018
【図５】
2005538465.tif 000019
【図６】
2005538465.tif 000020
【国際調査報告】
2005538465.tif 000021
2005538465.tif 000022
2005538465.tif 000023