JPH10500235A - データ記憶装置 - Google Patents

Abstract

(57)【要約】 本メモリ装置は有用メモリの他に補助メモリを備える。両メモリは複数のメモリエントリを有する。補助メモリは、有用メモリをアドレスし得る複数のアドレスを含むアドレス空間領域をその中に記憶するためのものである。有用メモリエントリに関連した状態領域が限定状態を信号出力し、有用メモリエントリをアドレスするためのアドレスが、補助メモリに記憶されている少なくとも１つのアドレス空間領域内にある場合は、有用メモリエントリへの書き込み／読み出しアクセスは不可能となる。活性記憶のための効率良い領域選択的フラッシュはこの手順により可能である。

Description

【発明の詳細な説明】 データ記憶装置 本発明は、データ用メモリ装置に関する。特に本発明は、キャッシュ又は変換 索引バッファ（ＴＬＢ）に関し、その新式はフラッシュバッファ、特にＴＬＢ又 はキャッシュ全体をフラッシュすることなく拡大領域及び縮小領域をフラッシュ することが可能な平行動作するフラッシュバッファである。 近年のプロセッサにおいては仮想アドレスから物理アドレスへの変換を高速化 するためにＴＬＢを使用している。一般にＴＬＢ及びキャッシュはプロセッサチ ップ上に設けられている。物理索引キャッシュにおいてはこれらは直列に配置さ れており（図４）、仮想索引一物理タグキャッシュにおいては平行に配置されて いる（図５）。 ここでＴＬＢはアドレス変換のための特別なキャッシュである。しかしながら 概してフルアソシアティブＴＬＢも使用されており、ＴＬＢはｎウェイセットア ソシアティブである。図６はダイレクトマップＴＬＢを示しており、即ち１ウェ イセットアソシアティブＴＬＢである。仮想アドレスｖの上位部分ｖ’はＴＬＢ のライン（メモリエントリ）を索引付けするために使用されている。数ある中で １つでも有効なエントリがあるかを示す、図６に示されていない状態ビットと共 に、このエントリに関連した仮想ページアドレスｖ’_i及び物理ページアドレス ｒ'_iが配置されている。これが有効でありｖ'_iが現ページアドレスｖ’と一致し ている場合、ＴＬＢヒットとなり、仮想アドレスの下位部分ｖ”及びＴＬＢから 与えられた物理ページアドレスｒ'_iから物理アドレスが構成される。 ｎウェイセットアソシアティブＴＬＢはダイレクトマップＴＬＢとは異なり、 同時に索引付けされｖ’を平行してチェックされた複 数のエントリを１つのラインが保持する。これらのエントリの１つが正しい場合 がヒットであり、そのとき物理アドレスｒを形成しアクセスの有効性を確認する ためにｒ'_i及びその状態ビットが使用される。 ＴＬＢはアドレス変換プロセスを短縮する。限定しているアドレスマッピング プロセス、即ち１又は複数のページテーブルエントリが修正されると、整合のた めに、無効化(“フラッシング”)、又は修正によって影響されたＴＬＢエントリ の対応する変更が必要となる。 アドレスマップの修正が単一ページのみを参照する場合、ＴＬＢ内にある限り 、フラッシュする又は各エントリを変更することで十分である。これは多くとも １つのＴＬＢエントリに関するので、その動作はＴＬＢの通常の変換ステップと 比較され得る。即ちＴＬＢは仮想ページアドレスを使用してアドレスされ、ヒッ トである場合エントリは無効とされるか又は修正される。 大領域に関する修正に関しては、この方法はすぐに複雑になる。 ｍページ分の仮想領域に対してはｍ個のステップが必要である。フルアソシアテ ィブＴＬＢでは、その問題は、全てのＴＬＢエントリの平行に限定されたフラッ シングによって効率良く解決される。あいにく、これに要求されるハードウェア は一般的に過剰となる。 ｎウェイセットアソシアティブＴＬＢに関しては、ＴＬＢ全体を調べることは 測り知れないほど高価であり、例えばｋ個のエントリに対して１つのＴＬＢ当た りｋ／ｎ個のステップが必要である。従ってこのような場合、１つのステップで 行えるようにＴＬＢ全体をフラッシュしておく。ＴＬＢのサイズ拡大に関しては 、これにより索引付けされたＴＬＢミスのためにこれの重要性が減少する。 本発明の目的は、メモリ装置、特により大きいアドレス空間領域（仮想領域） のフラッシングを有効に行えるｎウェイセットアソシ アティブキャッシュ又はＴＬＢを提供することにある。 この目的を達成するために、本発明は、請求項１記載の特徴を有するメモリ装 置を提案する。本発明の実施例の特徴は各従属項に記載する。 本発明に係るメモリ装置は、アドレス手段によりアドレス可能な複数のメモリ エントリを有する有用メモリを備える。この有用メモリは、例えばアドレス変換 のための特定のキャッシュメモリとして見なされ得るキャッシュメモリ又は変換 索引緩衝器とすることができる。特に本発明に係る有用メモリは、有用メモリを アドレスするためにアドレス空間が有するアドレスよりも事実上少ないメモリエ ントリを有する。各メモリエントリには、１又は複数のデータワードが記憶され 得るデータ領域が設けられている。またこのデータ領域に加えて、各メモリエン トリが、データ領域への書き込み／読み出しアクセスを限定するための少なくと も１つの限定状態、又はデータ領域への書き込み／読み出しアクセスを限定しな い非限定状態に変換され得る状態領域を有する。さらに各メモリエントリは他の 領域、特にタグ領域及び有効／無効領域を有する。有用メモリをアドレスすると き、アドレス又はその一部が、有用メモリのアドレスされた全エントリのタグ領 域の内容と比較される。これがタグ領域と一致しており、一方で、有効／非有効 領域に有効とマークされ、状態領域が非限定状態にあるか又は状態領域が限定状 態にあるかのいずれかであり、有用メモリの索引付けに使用されたアドレスが、 補助メモリに記憶された少なくとも１つのアドレス空間領域の一部でない場合は 、そのデータ領域への書き込み／読み出しアクセスが実行されてもよい。 また本メモリ装置は、アドレス空間の領域を限定するデータが記憶されている １又は複数のメモリエントリを含む補助メモリを備え る。この補助メモリ（フラッシュルックアサイドバッファ、略してＦＬＢとも称 される）を使用して、有用メモリが、領域選択方法により、即ち単一の動作ステ ップで効率良くフラッシュされてもよい。 有用メモリを領域選択的にフラッシュするための方法は以下のように行う。即 ち、補助メモリにアドレス空間領域を記憶する際に、全ての有用メモリエントリ の状態領域が限定状態に変換される。有用メモリエントリを続いてアドレスする とき、補助メモリに記憶されている少なくとも１つのアドレス空間領域内にアド レスがあり、状態領域が限定状態にある場合は、この有用メモリエントリのデー タ領域への書き込み／読み出しアクセスは実行されない。これを決定するために 有用メモリエントリをアドレスするために使用されたアドレスが、補助メモリに 記憶された少なくとも１つのアドレス空間領域に含まれているかをチェックされ る。この結果、該当する場合は、補助メモリはこの状況を示す信号（以後Ｆｈｉ ｔとも称する）を出力する。即ち有用メモリのフラッシュの後も、補助メモリに 記憶された少なくとも１つのアドレス空間領域に含まれないアドレスを使用して アドレスすることが可能な全ての有用メモリエントリのデータ領域に対しアクセ スしてもよい。有用メモリをＴＬＢ又はキャッシュとして実行する場合、有用メ モリの横に備えられるべき全てのものが補助メモリであり、有用メモリにおける メモリエントリが状態領域に加えられるべきであるので、時間消費テーブルウォ ーク、又は選択的フラッシュに関連しない有用メモリエントリのための主メモリ アクセスが回避され、ハードウェア及びソフトウェアの負担が比較的軽くなる。 前記状態領域は、必要な場合、それらが中央コマンド上で同時に限定状態へ変換 され選択的に非限定状態へ変換されるようになしてある。 好適には、それが初期化された（一般にデータが有用メモリエン トリに書き込まれ、有効としてタグ付けされた）有用メモリエントリを記憶する 場合、有用メモリエントリをアドレスするためのアドレスが補助メモリに記憶さ れている少なくとも１つのアドレス空間領域の一部ではないときに、各有用メモ リエントリの状態領域は正確に限定状態に変換される。しかしながらアドレスが 補助メモリに記憶されている少なくとも１つのアドレス空間領域の一部である場 合、アドレスされた有用メモリエントリの状態領域は非限定状態へ変換される。 また代案として、アドレッシングのために使用されたアドレスが補助メモリに 記憶されている少なくとも１つのアドレス空間領域の一部であるか否かに関わら ず、記憶アクセス時に、アドレスされた有用メモリエントリの状態領域が常に非 限定状態へ変換されてもよい。アドレッシング（特に有用メモリの初期化時又は 各フラッシュの後である）に先立ってアドレスされた有用メモリエントリの状態 領域が限定状態にあり、且つアドレッシングのためのアドレスが補助メモリに記 憶されている少なくとも１つのアドレス空間領域の一部でない場合、状態領域は 、アドレスする際に非限定状態に変換されるので、この瞬間から状態領域が限定 状態へ変換されるまでは、補助メモリに関するチェックが、有用メモリエントリ をアドレスする際にはもはや不要となる。 好適には、アドレス空間領域を限定するデータを補助メモリエントリへ書き込 む際に、全ての有用メモリエントリの状態領域が限定状態に変換される。また補 助メモリは複数のメモリエントリを有することが望ましい。補助メモリがオーバ ーフローすると、全ての有用メモリエントリ及び全ての補助メモリエントリが無 効として都合良くタグ付けされる。技術回路の実現においては、各補助メモリエ ントリが、補助メモリエントリに記憶されているデータが有効か否 かを示す有効ビットを有することに注意する。その有効ビットは各有用メモリエ ントリ（先の有効／無効領域に相当する）にも設けられている。 有益には、補助メモリエントリのアドレス空間領域の各記憶に先立ち、記憶さ れるべきアドレス空間領域が、補助メモリに既に記憶されているアドレス空間領 域と重複するかをチェックされる。補助メモリに記憶されている全てのアドレス 空間領域と、記憶されるべき新たなアドレス空間領域との組み合わせの論理積が 後者に等しい場合、新たなアドレス空間領域は補助メモリに再度記憶される必要 はなく、むしろ全ての有用メモリエントリの状態領域を限定状態に切り換えるこ とで足りる。そのとき補助メモリは何の変更もなく使用され得る。一方、アドレ ス空間領域が補助メモリに記憶されている場合、例えば追加的に記憶されるべき アドレス空間領域内全体にある場合、そして後者が既に記憶されているアドレス 空間領域より大きいか、又は前者が記憶されるべきアドレス空間領域と重複又は これと隣接する（それらの間に距離があってもなくてもよい）場合、既に記憶さ れているアドレス空間領域を含む補助メモリエントリは、記憶されるべき新たな アドレス空間領域を特定するデータで上書きされるてもよい。有用メモリは、全 ての有用メモリエントリの状態領域を限定状態に変換することにより、通常の方 法で選択的に再度フラッシュされる。上記考察は、相応じて、記憶されるべき新 たなアドレス空間領域と、補助メモリに既に記憶されている全てのアドレス空間 領域の結合との比較に適応する。 上述した補助メモリにおける動作は、補助メモリが早期オーバーフローを抑制 するための、補助メモリの最適使用を想定している。即ち本発明のこの具体例で は、１又は複数の現行の補助メモリエントリ及び／又は新たな補助メモリエント リが、以前のデータ及び新 たなデータによって特定された全てのアドレス空間領域が、せめて補助メモリに 記憶されるように、常に更新されるか又は選択される。 好適には全ての有用メモリエントリの状態領域が、補助メモリにおける動作に 関係なく、また補助メモリの状態に関係なく、同時に限定状態に切り換えられ得 る。 状態領域の実行の最も簡単な形態では、これは１ビット領域で構成され、限定 状態又は非限定状態を特定するためにセット及びリセットされてもよい。 上述したものとは異なる状態領域の実施例では、複数のビットを含み“生成番 号”が状態領域に記憶される。この場合、本発明のメモリ装置は、アドレス空間 領域が補助メモリエントリに記憶される都度インクリメントされる生成番号カウ ンタを備える。各補助メモリエントリは１つの生成番号領域で構成されている。 アドレス空間領域が補助メモリエントリに記憶される場合、この補助メモリエン トリの生成番号領域は、インクリメントの前に保持されている生成番号カウンタ の値にセットされる。記憶アクセスの実行対象である有用メモリエントリの状態 領域は、生成番号カウンタの現行の値にセットされる。アドレスされた有用メモ リエントリの状態領域が限定状態にあるか非限定状態にあるかは、その状態領域 の値と、アドレス空間領域が記憶されており、有用メモリエントリをアドレスす るために使用されたアドレスを含む補助メモリエントリの生成番号領域の値とを 比較することにより、そのとき決定される。その非限定状態は、状態領域の値が 各補助メモリエントリの生成番号領域の値より大きい場合に正確に与えられる。 このように有用メモリエントリの状態領域値と生成番号領域エントリとが、常に ２つのエントリのうちいずれがより新しいか（補助メモリエントリ、又は補助メ モリエントリにより特定されたアドレス空間領域内にあるアドレス を有する有用メモリエントリ）を示す。その機能として、状態領域は非限定状態 又は限定状態にある。 本発明にあっては、有用メモリエントリをアドレスするためのアドレスが補助 メモリに記憶された複数のアドレス空間領域内に存在することは基本的に可能で ある。アドレスされた有用メモリエントリのアドレスが、複数の補助メモリエン トリのデータによって限定されたアドレス空間領域内にある場合、有用メモリ及 び補助メモリの生成番号を比較することにより、状態領域の非限定状態又は限定 状態を実現するとき、しかも状態領域の値が、有用メモリエントリをアドレスす るために使用されたアドレスを含むアドレス空間領域を記憶している補助メモリ エントリの生成番号領域に記憶された生成番号の最大値より大きい場合、アドレ スされた有用メモリエントリの状態領域は非限定状態にある。そうでない場合、 アドレスされた有用メモリエントリの状態領域は限定状態にある。 好適には、生成番号カウンタは、補助メモリエントリのアドレス空間領域が補 助メモリに既に記憶されている１又は複数のアドレス空間領域と重複する場合に 、補助メモリエントリのアドレス空間領域を記憶するときにのみインクリメント される。従って一致し得る総生成番号が減少し、対応する補助メモリの生成番号 領域と有用メモリの状態領域とが縮小されるという効果が得られる。 補助メモリがオーバーフローする、即ちアドレス空間領域が補助メモリにこれ 以上記憶されないような場合、全ての有用メモリ及び補助メモリエントリは無効 としてタグ付けされ、さらに世代番号カウンタはリセットされる。世代番号カウ ンタが所定の最大値を超過すると、世代番号カウンタがリセットされ、また全て の有用メモリ及び補助メモリエントリが無効としてタグ付けされる。 本発明の具体例を、図面を用いて以下に詳述する。各図は以下の 通りである。 図１は、所定のＴＬＢ／キャッシュシステムに追加される“フラッシュルック アサイドバッファ”の構成の模式図である。 図２は、感衝突ビットの形態における状態領域を備えたＴＬＢの構成を示す。 図３は、論理的に結合されたＦＬＢ及びＴＬＢのブロック図である。 図４は、限定状態及び非限定状態をマークするための世代番号を備えたＦＬＢ の構成の模式図である。 図５は、世代番号を備え有効ビット及びＦｈｉｔ信号を備えないＦＬＢの構成 を示す。 図６は、世代番号を備えたＴＬＢを示す。 図７は、世代番号を備え、その出力が論理的に結合されたＦＬＢ及びＴＬＢの ブロック図である。 図８は、有効ビット及びＴｈｉｔ信号を備えないＴＬＢの構成を示す。 図９は、有効ビット及びＴｈｉｔ信号を備えないＦＬＢ及びＴＬＢの構成を（ ブロック図として）示す。 図１０は、マスクＦＬＢを備えたＴＬＢを（ブロック図として）示す。 図１１は、アクティヴィティノートを備えた単純なＦＬＢの基本的な構成を示 す。 図１２は、シャドウＴＬＢの構成を示す。 図１３は、“書き込み保護”を備えたＴＬＢ及びＦＬＢを含むシステムのブロ ック図である。 図１４は、ＴＬＢ及びキャッシュを含む直列キャッシュメモリシステムの基本 構成を示す。 図１５は、ＴＬＢ及びキャッシュを含む平行キャッシュメモリシステムの構成 を示す。 図１６は、ダイレクトマップＴＬＢ（基本構成）を示す。 １．フラッシュルックアサイドバッファ １．１ 単純なＦＬＢ 図１〜３を参照して、ＴＬＢメモリシステムを用いた本発明に係るメモリ装置 の第１実施例について以下に詳述する。以下の（全ての実施例に対する）考察は 全て同様にキャッシュメモリシステムに転じることができる。ここでＴＬＢは物 理的にキャッシュメモリであることに注目する。 ＴＬＢシステムを備えた本発明を実行するために、小型でフルアソシアティブ フラッシュルックアサイドバッファ（以下ＦＬＢと称する）がＴＬＢシステムに 追加されている。ＦＬＢの各エントリは有効ビットを有し、領域ρ_jの特定に適 用することができる（図１）。 ここで領域は、例えば開始及び終了アドレス又は長さによって特定されてもよ く、アドレス、及びアドレスビットをヒットチェックのために使用すべきである か無視すべきであるかを示すマスクによって特定してもよい。 有効（ｖａｌｉｄ_j）であり、その仮想アドレスｖを含む領域ρ_jである少なく とも１つのエントリｊがある場合、ＦＬＢはヒットＦｈｉｔの信号を出力する。 ＴＬＢは、ＦＬＢヒットを伴う衝突を照合すべきか（ｃｓ）即ち限定状態であ るか、又はＦＬＢヒットを伴う衝突を無視すべきか ｃｓ_iを備える。ヒットである場合、ＴＬＢはＴｈｉｔを信号出力 し、物理アドレスｒ’及びそのヒットエントリからの感衝突ビットｃｓを与える 。 変換時に、ＴＬＢヒット及びＦＬＢヒットとなった（Ｔｈｉｔ∧Ｆｈｉｔ）場 合、これを衝突と称する。衝突はｃｓがセットされている場合に真であり、ｃｓ がセットされていない場合は偽である。真の衝突時にはシステム全体はＴＬＢヒ ットを無視する、即ち丁度ＦＬＢヒットが報告されたときにも感衝突ビットがセ ットされる。 即ち、 Ｈｉｔ＝Ｔｈｉｔ∧¬（Ｆｈｉｔ∧ｃｓ） このヒット状態の理解を深めるために図３を参照されたい。 新たなＴＬＢエントリが記憶される都度、対応する仮想アドレスがＦＬＢヒッ トをトリガしないときに、感衝突ビットｃｓ_iはセットされる。そうでない場合 、ｃｓ_iはこの工程においてリセットされる。通常、ＴＬＢミス（記憶アクセス ）のためにＴＬＢエントリが記憶され、この場合対応する仮想アドレスｖ’はＦ ＬＢによってＴＬＢステップと平行に処理されるので、新たなＴＬＢエントリの ておく。 真の衝突を伴うＴＬＢヒットでは、 １．対応するＴＬＢエントリはフラッシュされる（ｖａｌｉｄ_i：＝偽） ２．ＴＬＢミスが信号出力され、ＭＭＵテーブルウォークが実行される。 ３．ＦｈｉｔがＴＬＢミス時にセットされるので、使用エントリの感衝突ビット ｃｓ_iが新たな記憶動作時にリセットされる。 同じ仮想アドレスを再度アドレスすると偽衝突となる。 ヒット信号の相互作用を示す次の図式では、右側の動作のための前提条件を夫 々矢符→の左側に示す。いずれかを選択するために、ここで挙げた前提条件を全 て満足すべきである（ＡＮＤ動作）。コンマで分けた全ての動作は平行に実行さ れる。オーバーストライク ットを示し、“−！”は信号又はビットのリセットを示す。 ＦＬＢの方法は次のものを使用する。 ・領域ρがＦＬＢに既に記憶された領域ρ_jと重複せず、少なくとも１つの自由 なＦＬＢエントリが存在するとき、自由なエントリにρを記憶し、それを有効と して設定することによりフラッシュしてもよい。 ・ＦＬＢがオーバーフロー又は重複する場合、 (a)ＦＬＢ及びＴＬＢは、一般に全ての有効ビットを同時にリセットすることに より完全にフラッシュされる。 (b)又はＴＬＢは、全ての感衝突ビットｃｓ_iを同時にセットすることにより再度 感衝突状態とされるのみであり、又はＴＬＢはそのままにしておく。ＦＬＢは、 そのままにしておくか、又は変更の後に全ての有効ＦＬＢエントリの領域の結合 が変更前の対応する量を含むように変更してもよい。 １．２ 世代番号を備えたＦＬＢ 次に図１〜６を参照しながら本発明の第２実施例について述べる。ここではア ドレスされたＴＬＢメモリエントリのデータ領域にアクセスされたかを示す状態 情報又は状態領域の内容が、ＦＬＢに記憶されているアドレス空間領域の一部で あるアドレス手段によりアドレスされる。 簡単なＦＬＢではエントリ毎に１つの世代番号領域Ｇ_jを備える。ＦＬＢにお ける領域の重複が許可されない場合、Ｇにおける正確なエントリの世代番号Ｇ_j はＦＬＢヒット時に準備される。領域が重複すると、Ｇにおける全ての正確な（ ｖ’∈ρ_j）有効エントリの最大の世代番号Ｇ_jがＦＬＢヒット時に準備される。 図５に示す代案は有効ビット及びＦｈｉｔ信号がない場合である。ここで無効 は予備の最小世代番号−∞によって示されている。ＦＬＢエントリはＧ_j＝−∞ で無効とマークされる。さらにＦＬＢはヒットでない場合Ｇ＝−∞を与える。図 面及び説明の簡素化のために以下の記述は常にこの第２実施例に基づくものとす る。有効ビット及びＦｈｉｔ信号を使用し、回路の形態において簡素化及び高速 化が可能である実施例は、これらの記述から容易に導かれる。 感衝突ビットの代わりに、ＴＬＢはエントリ毎に１つの世代番号ｇ_iを備える （図６）。ＴＬＢヒットの場合、対応する世代番号がｇに与えられる。現行の各 世代を示すレジスタγが存在する。最初に又は各ＦＬＢフラッシュの後にそれは 例えば値１を保持する。ＦＬＢの内容が変更される度に世代は１ずつインクリメ ントされる。ＴＬＢエントリの各ローディングに際しその世代番号が現行の世代 ｇ_i：＝γにセットされる。 衝突はＴｈｉｔ∧Ｇ＞−∞として与えられる。Ｇ≧ｇであるときは図７に示す ように真である。γ及びＦＬＢ領域Ｇ_jを適当に使用する場合は、同じ仮想アド レスの他のアドレッシングが偽衝突へ導 かれるのみであり、以下のようになる。 −∞の代用として０が使用され、ＴＬＢにおける各世代番号領域ｇ_iのｋビッ トを０で代用すると、１〜２^k-1が有効世代値として使用されてもよい。 ＦＬＢ管理方法 具体的なフラッシュの語義は、ＦＬＢの管理で略定義される。２つの方法例に ついて概略を述べる。 (a)世代番号領域が十分に広い場合、Ｇ_jにおけるγの値は、新たな各ＦＬＢエン トリで引き継がれ、レジスタγは１ずつインクリメントされる。そのとき他のＦ ＬＢエントリとの重複はもはや重要ではない。ＦＬＢがオーバーフローした場合 、ＦＬＢ及びＴＬＢはフラッシュされてγがリセットされる。 (b)しかしながら多くの場合、１．１章で述べた方法を応用することにより、よ り狭幅の世代番号領域を使用することができる。ここで新たなＦＬＢエントリの Ｇ_jが常にγにセットされているが、その後、少なくとも１つの有効ρ_jと共に記 憶されるべき新たな領域ρが重複する場合、レジスタγが１ずつインクリメント されるのみである。そうでない場合γは変更されずにもとのままである。ＦＬＢ がオーバーフローするか又は現行の世代番号γが大きくなりすぎた場合、ＦＬＢ 及びＴＬＢはフラッシュされ、γがリセットされる。 ＴＬＢを完全にフラッシュする代わりに、方法(b)においては、全ての世代番 号ｇ_iを同時に例えば１にリセットすることにより、 ＴＬＢを感衝突性にすることが可能である。そのときＦＬＢはもとのままである か、又は変更後の全ての有効ＦＬＢエントリの総数が、変更前の対応する領域を 少なくとも有効に包含するように変更されてもよい。 有効ビット及びＴｈｉｔ信号を有さない場合 ヒットでないときに、予備の最小世代番号−∞を使用すると、無効ＴＬＢエン トリに対してｇ_i＝−∞をセットし、マルチウェイセットアフシアティブＴＬＢ に対しｇ_i＞−∞であるエントリについてのみ考慮し、常時ｇに−∞を与えるこ とにより、ＴＬＢにおいても有効ビット及びＴｈｉｔ信号を要求しない。このモ デルを図８，９に示す。 以下が適用される。 エントリ毎の１ビットがＴＬＢに保持されているこのモデルは特に重要である 。例えば２つのビットｃｓ_i，ｖａｌｉｄ_iが２ビット領域ｇ_iと入れ換えられ、 値０が−∞として使用されている場合、同じメモリ動作が既に３つの真の世代の ために許容されている。 しかしながら全ての有効な（ｇ_i＞０）世代番号をリセットすることにより、 感衝突性とすることは書き込みのためにはもはや実行されない。 １．３ 世代マスクを備えたＦＬＢ及びＴＬＢ 世代番号の代わりにビットマスクを使用してもよい。即ち数学的 な比較＜の代わりに“ビット式ＡＮＤ演算”が必要である。 １．４ マスクＦＬＢを備えたＴＬＢ 世代番号又はマスクが十分に広い場合、ＦＬＢにおける世代情報Ｇ_jが省略さ れ、ＦＬＢエントリのアドレスとしてｇ_iを理解する。図１０に示す如く、ＦＬ Ｂは各エントリｊに対して信号Ｆｈｉｔ_jを与える。これら全ての信号はｋ個の ＦＬＢエントリでＯＲ演算をマスクされる。 Xhit＝(Fhit₀∧m₀)∨(Fhit₁∧m₁)∨…∨(Fhit_k-1∧m_k-1) ここでマスク（ｍ₀，ｍ₁，…，ｍ_k-1）は、ＴＬＢエントリに直接記憶されｇ として与えられるか、与えられたｇから例えば−２^gとして生成される。¬Ｘｈ ｉｔ∧Ｔｈｉｔの場合がヒットであり、Ｘｈｉｔ∧Ｔｈｉｔの場合が真の衝突で ある。以下が適用される。 １．５ アクティヴィティノートを備えたＦＬＢ ＦＬＢに記憶されるべき新たな領域が既に記憶されている現行の領域と重複す る場合、幾つかのＦＬＢモードがＴＬＢをフラッシュするか、又は再度完全に感 衝突性にする。このような処理を減少させるためにＦＬＢの活性エントリと非活 性エントリとを差別化してもよい。即ち各エントリが最初に真の衝突が生じたと きのみ活性となる。そのとき非活性エントリは、拡張されるか、又は真のＦＬＢ 又はＴＬＢフラッシュを必要としない他のフラッシュのために使用される。 各ＦＬＢエントリは１つのアクティヴィティビットａｃｔｖ_jによって拡張さ れる。これは有効ビットを備え世代番号を備えない単純なＦＬＢとして図１１に 示される。他のタイプのＦＬＢはアクティヴィティビットを付加することにより 同様にして拡張される。新たにＦＬＢエントリをローディングする場合、アクテ ィヴィティノートは常にリセットされる。真の衝突が生じた場合にのみ、一致し ている（∀ｖ’∈ρ_j：ａｃｔｖ_j！）全てのＦＬＢエントリのアクティヴィティ ビットがセットされるが、このとき無効エントリは無視される。ＦＬＢにおいて 領域の重複が生じた場合、複数のアクティヴィティビットをセットするだけでよ いことを明記する。そうでない場合は真の衝突である１つの一致ＦＬＢエントリ が正確に存在する。 感衝突性及び有効ビットを備えた簡単なＦＬＢ及びＴＬＢのために以下が適用 される。 有効ビットと共に、世代番号Ｇ_jを備えたＦＬＢ及び世代番号ｇ_iを備えたＴＬ Ｂに対して以下が適用される。 世代番号Ｇ_jを備えたＦＬＢ及び世代番号ｇ_iを備え有効ビットを備えないＴＬ Ｂに対しては以下が適用される。 マスクＦＬＢを備えたＴＬＢに対しては以下が適用される。 領域ρがＦＬＢに既に記憶されている領域ρ_jと重複せず、活性であり（ａｃ ｔｖ_j）、少なくとも１つのＦＬＢエントリを自由にする場合、その領域は、自 由なエントリにρをローディングし、これを有効とセットすることによりフラッ シュされる。 また非活性（ａｃｔｖ_j）のＦＬＢエントリは修正されるか又はイネーブルと される。フラッシュ語義のための要求事項は、変更後の有効な全てのＦＬＢエン トリの総数が変更前の対応する有効な領域を少なくとも包含することのみである 。 ２．ＦＬＢのその他の形態 ２．１ 選択的ＴＬＢフラッシュ ＴＬＢは、全ての有効なＴＬＢエントリの領域ｖ'_iをＦＬＢに対して順番にテ ストすることにより選択的にフラッシュされてもよい。 ＦＬＢがｖ_iでヒットを報告した場合、このＴＬＢエントリは無効とされる。Ｔ ＬＢ全体がこのようにしてスキャンされているとき、スキャンの開始以来変更さ れていない全てのＦＬＢはイネーブルとされる。特にスキャン中にＦＬＢにおい て変更かない場合、ＦＬＢ全体がフラッシュされてもよい。 各ｎウェイセットアソシアティブＴＬＢエントリを平行にテストすることによ り、ｎ方向ＴＬＢの要素ｎにてＴＬＢスキャンは高速化されてもよい。ＦＬＢの 速度に依存してＴＬＢスキャンはその最後まで増加すべきである。 スキャンと平行にＴＬＢによる通常のアドレス変換を行うためにシステムは、 図１２に示す如く、“シャドウ”ＴＬＢにより拡張されてもよい。ＴＬＢと比較 した場合、シャドウＴＬＢは、アソシアティブではないが、ダイレクトアドレス メモリである。ＴＬＢの変更による更新時にＴＬＢアドレスは引き継がれる。シ ャドウＴＬＢは、各ＴＬＢエントリの仮想アドレスと有効性と衝突情報とを複写 する。感衝突ビットを備えたＴＬＢに対しては以下のようにシャドウＴＬＢのエ ントリに対して真である（図１２参照）、即ち ｗ_i＝ｖ_i，ｘ_i＝ｖａｌｉｄ_i∧ｃｓ_i， 世代番号及び有効ビットを備えたＴＬＢについては以下が適用され、 ｗ_i＝ｖ_i，ｘ_i＝（ｖａｌｉｄ_i，ｇ_i）， そして世代番号を備え有効ビットを備えないＴＬＢに対しては以下が真である。 ｗ_i＝ｖ_i，ｘ_i＝ｖａｌｉｄ_i＝ｇ_i 対応するＴＬＢ領域における変更は直ちにシャドウＴＬＢへ伝えられる。シャ ドウＴＬＢをスキャンすることにより選択的フラッシュが実行される。この工程 においてフラッシュされるべきエントリが見つかった場合、そのフラッシュ動作 はシャドウＴＬＢ及び実ＴＬＢに対して実行される。 ２．２ 仮のＴＬＢとしてのＦＬＢ ＦＬＢエントリは、ＴＬＢにおいてもラッチされている領域、例えばアクセス 属性によって拡張されてもよい。これらが領域のため に変更される（制限される）とき、Ｆｈｉｔに際しては、ＦＬＢからの対応する 情報を引き継ぐことで十分である。テーブルウォークは不要となる。 図１３は、例えばＦｗｐにおけるＦＬＢヒット時に与えられる、領域毎の書き 込み保護信号をも含むＦＬＢを示す。最後の書き込み保護信号ｗｐはＴｗｐｖ（ Ｆｈｉｔ∧Ｆｗｐ）として形成され、ここでＴｗｐはＴＬＢによって与えられた 書き込み保護信号である。このようにして領域は、追加ＴＬＢミス及びテーブル をウォークを必要とすることなく一時的に書き込み保護される。 この方法は、仮想別名及び呼出参照のために使用することも可能である。先の ２．１章で述べた方法は、可能であれば、ＴＬＢエントリがフラッシュされない ように展開されてもよいが、ＦＬＢからの情報に基づいて変更されてもよい。 ２．３ ＦＬＢにおける重複 より大きいＦＬＢにおいては、新たな領域ρ＝［ρ，ρ］が既に有効に記憶さ れた領域ρ_j＝［ρ_j，ρ_j］と重複するかを決定することが複雑になり得る。フ ルアソシアティブエレメントのように、ＦＬＢは、そのサイズに関係なく２つの ステップでこの決定を行うことができるが、ＦＬＢの複雑さとコストとはこれに より増大する。 各ＦＬＢエントリはビットｌｏｗ_jによって拡張される。重複チェックの初期 において全てのｌｏｗ_jビット及びＦｈｉｔ信号はリセットされる。ＦＬＢは新 領域の下限ρを受け、各素子は以下の規則に従うステップ１を実行する。 次にＦＬＢは上限ρを受け各素子は以下の規則に従うステップ２を実行する。 ステップ２の後、信号Ｆｈｉｔがセットされている場合は重複がある。 ２．４ キャッシュ 記載した全ての方法はＴＬＢに代わりにキャッシュを用いて実施してもよい。 そのときＴＬＢエントリの新たなローディングによるテーブルウォークは主メモ リアクセスと入れ換えられる。

Claims (1)

1. 【特許請求の範囲】 １．アドレス空間領域のアドレス手段によりアドレスすることが可能な複数のメ モリエントリを有する有用メモリと、 −ここで各エントリは、有効又は無効とマークされたデータ領域、及び有効 なデータ領域への書き込み／読み出しアクセスを限定する少なくとも１つの限定 状態と、有効なデータ領域への書き込み／読み出しアクセスを限定しない少なく とも１つの非限定状態とへ変換することが可能な可変状態領域を含む、 アドレス空間領域を特定するデータを記憶する少なくとも１つのメモリエント リを備えた補助メモリと を備え、 補助メモリに記憶された少なくとも１つのアドレス空間領域及び有用メモリエ ントリの状態領域内にアドレスがある場合は、アドレスされた有用メモリエント リのデータ領域への書き込み／読み出しアクセスが許可されないようになしてあ る 特にキャッシュメモリ装置又は変換索引バッファにおけるデータ記憶用メモリ装 置。 ２．有用メモリエントリを初期化するロードアクセス時に、アドレスされた有用 メモリエントリの状態領域は、 アドレスが、補助メモリに記憶された少なくとも１つのアドレス空間領域でな いときには限定状態へ変換され、 また、アドレスが、補助メモリに記憶された少なくとも１つのアドレス空間領 域であるときには非限定状態へ変換されることを特徴とする請求項１記載のメモ リ装置。 ３．有用メモリエントリを初期化するためのロードアクセス時に、アドレスされ た有用メモリエントリの状態領域が非限定状態へ変換されることを特徴とする請 求項１記載のメモリ装置。 ４．限定状態となっており、アドレッシングのために使用されたアドレスが補助 メモリに記憶された少なくとも１つのアドレス空間領域の一部でない場合は、ア ドレス時に、アドレスされた有用メモリエントリの状態領域が非限定状態へ変換 されることを特徴とする請求項３記載のメモリ装置。 ５．アドレス空間領域を特定するためのデータを補助メモリエントリへ書き込む ときには、全ての有用メモリエントリの状態領域が非限定状態へ変換されること を特徴とする請求項２〜４のうちのいずれかに記載のメモリ装置。 ６．補助メモリは複数のメモリエントリを有することを特徴とする請求項１〜５ のうちのいずれかに記載のメモリ装置。 ７．全ての補助メモリエントリが各アドレス空間領域を特定するデータと、補助 メモリに記憶されるべきアドレス空間領域を特定するデータとを保持する場合は 、全ての有用メモリエントリ及び補助メモリエントリは無効とマークされること を特徴とする請求項１〜６のうちのいずれかに記載のメモリ装置。 ８．アドレス空間領域を特定するデータを補助メモリエントリへ記憶することに 先立ち、このアドレス空間領域が、補助メモリに既に記憶されているアドレス空 間領域と重複するか、そして存在してい る補助メモリエントリ及び／又は新たな補助メモリが、先に特定された全てのア ドレス空間領域と新たなデータとが補助メモリに記憶され、全ての有用メモリエ ントリの状態領域が限定状態へ変換されるように更新又は選択され得るかをチェ ックすることを特徴とする請求項１〜７のうちのいずれかに記載のメモリ装置。 ９．全ての有用メモリエントリの状態領域が、補助メモリの動作又はその状態に 関係なく、同時に限定状態へ変換されることを特徴とする請求項１〜８のうちの いずれかに記載のメモリ装置。 １０．有用メモリエントリの状態領域は、限定状態及び非限定状態を特定するた めにセット及びリセットされる単一ビットを含むことを特徴とする請求項１〜９ のうちのいずれかに記載のメモリ装置。 １１．各補助メモリエントリは世代番号領域を有しており、 アドレス空間領域を特定するデータを補助メモリエントリに記憶する各動作時 に、インクリメントされる世代番号カウンタが設けられており、 −補助メモリエントリの世代番号領域は、この補助メモリエントリがアドレ ス空間領域を特定するデータを記憶している場合に、インクリメント前に世代番 号カウンタが保持していた値にセットすることが可能であり、またここでは、こ れを初期化する有用メモリエントリに対してロードアクセスされる場合に、有用 メモリエントリの状態領域が世代番号カウンタの現行の値にセット可能であり、 アドレスされた有用メモリエントリの状態領域は、 −状態領域の値が、アドレスされた有用メモリエントリのアド レスを含む補助メモリエントリの世代番号領域の値より大きいとき非限定状態と なり、 −そうでないときには限定状態となる ことを特徴とする請求項１〜９のうちのいずれかに記載のメモリ装置。 １２．アドレスされた有用メモリエントリのアドレスが複数の補助メモリエント リのデータによって特定されたアドレス空間領域内にあるとき、アドレスされた 有用メモリエントリの状態領域は、 −状態領域の値が、対応する補助メモリエントリの世代番号領域に記憶され た世代番号の最大値より大きいときに非限定状態となり、 −そうでないときには限定状態となる ことを特徴とする請求項１１記載のメモリ装置。 １３．アドレス空間領域を特定するデータを補助メモリエントリに記憶するとき 、これらのデータによって特定されたアドレス空間領域が、補助メモリに既に記 憶された１又は複数のアドレス空間領域と重複する場合にのみ、世代番号カウン タがインクリメントされることを特徴とする請求項１１又は１２に記載のメモリ 装置。 １４．アドレス空間領域を特定するデータが補助メモリにこれ以上記憶され得な い場合は、有用メモリエントリ及び補助メモリエントリの全てが無効とマークさ れ、世代番号カウンタがリセットされることを特徴とする請求項１１〜１３のう ちのいずれかに記載のメモリ装置。 １５．世代番号カウンタが所定の最大値を超過した場合は、有用メモリエントリ 及び補助メモリエントリの全てが無効とマークされ、世代番号カウンタがリセッ トされることを特徴とする請求項１１〜１４のうちのいずれかに記載のメモリ装 置。