JPH11203199A - キャッシュ・メモリ - Google Patents

キャッシュ・メモリ

Info

Publication number
JPH11203199A
JPH11203199A JP10300695A JP30069598A JPH11203199A JP H11203199 A JPH11203199 A JP H11203199A JP 10300695 A JP10300695 A JP 10300695A JP 30069598 A JP30069598 A JP 30069598A JP H11203199 A JPH11203199 A JP H11203199A
Authority
JP
Japan
Prior art keywords
tag
cache
virtual
physical
vector
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP10300695A
Other languages
English (en)
Inventor
Samuel D Naffziger
サミュエル・ディー・ナフジィガー
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
HP Inc
Original Assignee
Hewlett Packard Co
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Hewlett Packard Co filed Critical Hewlett Packard Co
Publication of JPH11203199A publication Critical patent/JPH11203199A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
    • G06F12/1045—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
    • G06F12/0864—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches using pseudo-associative means, e.g. set-associative or hashing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
    • G06F12/10—Address translation
    • G06F12/1027—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
    • G06F12/1045—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache
    • G06F12/1054—Address translation using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB] associated with a data cache the data cache being concurrently physically addressed
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/65—Details of virtual memory and virtual address translation
    • G06F2212/652—Page size control

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Abstract

(57)【要約】 【課題】キャッシュ・メモリにおけるアクセス時間を改
善するための方法および装置を提供する。 【解決手段】本発明の一実施例によれば、キャッシュへ
のアクセス時に変換索引バッファ（ＴＬＢ）から物理的
アドレス・タグを検索する必要のないキャッシュが提供
される。キャッシュは各新キャッシュ行に対しキャッシ
ュのタグ部に物理的ヒット・ベクトルを物理的タグの代
わりに記憶する。物理的ヒット・ベクトルは第１のＴＬ
Ｂ ＣＡＭ（内容アドレス・メモリ）によって発生され
る。各物理的ヒット・ベクトルはキャッシュ行の物理的
タグを有する第１のＴＬＢ ＣＡＭ内の全ての位置を示
す。キャッシュ・アクセスに対し、第２のＴＬＢ ＣＡ
Ｍが仮想タグを受信し仮想ヒット・ベクトルを発生す
る。仮想ヒット・ベクトルは対応する仮想タグの第２の
ＴＬＢ ＣＡＭ内の位置を示す。次に、キャッシュは仮
想ヒット・ベクトルと物理的ヒット・ベクトルのセット
とを比較する。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、一般に、コンピュータ
・メモリ・システムに関するものであり、とりわけ、キ
ャッシュ・メモリにおけるアクセス時間の改善に関する
ものである。
【０００２】
【従来の技術】大部分のコンピュータ・システムでは、
最高レベルの階層における比較的高速で、高価で、容量
の制限されたメモリから、最低レベルの階層における比
較的低速で、コストが低く、容量の大きいメモリに至
る、マルチレベル階層のメモリ・システムが用いられ
る。一般に、階層には、速度を速めるため、物理的にプ
ロセッサの集積回路内に組み込まれるか、あるいは、物
理的にプロセッサに近接して取付られる、キャッシュと
呼ばれる小形の高速メモリが組み込まれている。独立し
た命令キャッシュとデータ・キャッシュを設けることも
可能である。マルチレベルのキャッシュを設ける場合も
ある。
【０００３】プロセッサが、キャッシュからある項目を
要求し、その項目がキャッシュに納められている場合、
その事象はキャッシュ・ヒットと呼ばれる。プロセッサ
が、キャッシュからある項目を要求し、その項目がキャ
ッシュに納められていない場合、その事象はキャッシュ
・ミスと呼ばれる。キャッシュ・ミスの場合、要求され
た項目は、より低いレベルのメモリ階層から検索され
る。多くのプロセッサ設計では、キャッシュ・ヒットの
ための、項目にアクセスするのに必要な時間は、プロセ
ッサのクロック・レートに対する主要なリミッタの１つ
である。従って、キャッシュ・ヒットのためのアクセス
時間の最適化は、性能にとってクリティカルである。コ
ンピュータ・プロセッサにとって、キャッシュ・アクセ
ス時間の改善は継続して必要とされている。
【０００４】一般に、メモリは、ワードに編成される
（例えば、３２ビットまたは６４ビット／ワード）。一
般に、キャッシュと次に低レベルのメモリ階層との間に
おいて転送可能な最小量のメモリは、行と呼ばれるが、
ブロックと呼ばれる場合もある。１行は、一般に、複数
ワードである（例えば、１６ワード／行）。メモリは、
ページ（セグメントとも呼ばれる）に分割し、ページ毎
に多数行から成るようにすることも可能である。システ
ムによっては、ページ・サイズを可変にすることも可能
である。
【０００５】多くの最新コンピュータ・メモリ・アーキ
テクチャにおいて、ＣＰＵは、ハードウェア及びソフト
ウェアによって、物理的メイン・メモリにアクセスする
物理的アドレスに変換される、仮想アドレスを生成す
る。仮想アドレス・グループは、動的に各ページに割り
当てることが可能である。仮想メモリ（ページングまた
はセグメンテーション）は、仮想アドレスを物理的アド
レスに変換する、ページ・テーブルと呼ばれることもあ
る、データ構造を必要とする。アドレス変換時間を短縮
するため、コンピュータは、一般に変換索引バッファ
（ＴＬＢ）と呼ばれる、アドレス変換専用の特殊連想キ
ャッシュを用いるのが普通である。
【０００６】キャッシュが、データと共に全行アドレス
を記憶し、キャッシュ内の任意の位置に任意の行を配置
することが可能な場合、そのキャッシュは完全に連想型
であると表現される。しかし、任意の位置に任意の行を
配置することが可能な大型キャッシュの場合、エントリ
がキャッシュ内に（及びどこに）あるか否かを迅速に判
定する必要のあるハードウェアは、極めて大型で、高価
なものになる可能性がある。大型キャッシュの場合、よ
り高速で、スペースの節約になる代替案は、アドレスの
サブセット（索引と呼ばれる）を用いて、キャッシュ内
における行位置を指定し、さらに、データと共に、各物
理的アドレスの最上位ビットの残りのセット（タグと呼
ばれる）を記憶する。索引付けを施したキャッシュで
は、特定のアドレスを備えた項目は、索引によって指定
された行セット内にしか配置することができない。キャ
ッシュが、所定のアドレスの索引がサブセット内の１つ
の行に正確にマッピングされるように構成されている場
合、そのキャッシュは、直接マッピング式であると表現
される。索引が、サブセット内の２つ以上の行にマッピ
ングされる場合、そのキャッシュは、セット連想型であ
ると表現される。アドレス空間をセットに分割するセッ
ト索引が得られるようにするため、アドレスの全てまた
は一部にハッシングが施される。
【０００７】直接マッピングでは、ある行が要求される
場合、一致する索引ビットを備えているのは、キャッシ
ュ内の１つの行だけである。従って、システムが、アド
レスの残りが一致するか否かを判定する前に、データを
すぐに検索し、データ・バスに送り込むことが可能であ
る。データは、有効の場合も、あるいは、有効でない場
合もあるが、有効である通常の場合、システムが妥当性
を判定する前に、バスにおいてそのデータを入手するこ
とが可能である。セット連想キャッシュの場合、完全な
アドレスを比較するまで、どの行がアドレスに対応する
か分からない。すなわち、セット連想キャッシュの場
合、タグの比較結果を利用して、行セット内におけるど
の行のデータ・ビットをプロセッサに供給するかを選択
する。
【０００８】ＴＬＢを備えたキャッシュの場合、ヒット
のためのクリティカルなタイミング経路は、次のシーケ
ンスをなす４つの操作を必要とする：（１）仮想タグを
ＴＬＢの内容アドレス・メモリ（ＣＡＭ）に提示し、Ｔ
ＬＢのＲＡＭにおける対応する物理的タグの位置を求め
なければならない；（２）次に、ＴＬＢ ＲＡＭから物
理的タグを検索しなければならない；（３）次に、ＴＬ
Ｂ ＲＡＭからの物理的タグとキャッシュのタグ・セク
ションからアクセスした物理的タグの比較を行わなけれ
ばならない；（４）適合するデータ行を選択しなければ
ならない。この４つの操作からなるシーケンスは、クロ
ック・サイクルの単一位相で完了することが望ましく、
実際、その位相をどれほど短くできるかを制限する可能
性がある。４つの操作のそれぞれに、時間がかかり、専
ら、各操作をできる限り速くすることに、多大の設計努
力が傾注される。ＴＬＢを備えたキャッシュに対するア
クセスのためのクリティカルな時間経路に関して、総合
的な時間の改良が必要とされる。
【０００９】
【発明が解決しようとする課題】本発明は、キャッシュ
・メモリにおけるアクセス時間を改善するための方法お
よび装置を提供することを目的とする。
【００１０】
【課題を解決するための手段】ＴＬＢから物理的タグを
検索する必要のない、ＴＬＢを備えたキャッシュが開示
される。キャッシュには、物理的タグを記憶する代わり
に、物理的タグが記憶されているＴＬＢ内の位置を記憶
する。ＴＬＢには、２つのＣＡＭが含まれている。キャ
ッシュ・ヒットの場合、ＴＬＢのＣＡＭの１つが、物理
的アドレスが記憶されているＴＬＢ内の位置を指定する
ベクトルを発生する。このベクトルが、キャッシュに記
憶されている位置ベクトルと比較される。この位置ベク
トルの比較によって、実際に物理的アドレスを検索する
ことを必要とせずに、セット内の１つのデータ行の選択
を可能にするのに十分な情報が得られる。結果として、
かなりの時間を費やす操作（物理的アドレス検索）が、
キャッシュ・ヒットのクリティカルな時間経路から取り
除かれる。さらに、物理的タグではなく、位置ベクトル
の比較によって、従来用いられているデジタル比較器よ
り高速で単純な比較論理の利用が可能になる。
【００１１】システムが可変ページ・サイズを備えてい
る場合、追加構造が必要になる。実際上、追加構造は、
もう１つのＣＡＭである。追加構造には、ページ・オフ
セット・ビット（アドレスの一部）と、どのページ・オ
フセット・ビットが関連しているかを指定するページ・
マスク・ビット（オペレーティング・システムによって
与えられる）が納められている。仮想アドレスの索引ビ
ットが、追加構造のエントリを指定する。
【００１２】実施態様例には、４ウェイ・セット連想キ
ャッシュが用いられる。しかし、本発明は、ＴＬＢを備
えた任意のキャッシュに適用可能である。
【００１３】
【実施例】図１には、先行技術によるキャッシュの一例
が示されている。例示のため、４ウェイ・セット連想キ
ャッシュが用いられているが、本発明は、ＴＬＢを用い
る任意のキャッシュに適用可能である。仮想アドレス１
００は、下位索引ビット１０２と上位タグ・ビット１０
４から構成される。索引ビットは、一般に、仮想アドレ
ス及び物理的アドレスに関して同じである。索引ビット
は、キャッシュのデータ・セクション１０６における１
つのデータ行セットを選択するために用いられる。デー
タ・セクション１０６の出力は、４つのデータ行１０８
である。索引ビットは、キャッシュのタグ・セクション
１１０における１つの物理的タグ・セットを選択するた
めにも用いられる。タグ・セクション１１０の出力は、
それぞれ、１データ行１０８に対応する、４つの物理的
タグ１１２である。仮想タグ・ビット１０４は、ＴＬＢ
１１４内のＣＡＭ１１６における１つのエントリを選択
するために利用される。ＴＬＢ１１４は、仮想タグと物
理的タグの両方を記憶する。仮想タグ１０４が、ＣＡＭ
１１６に一致を見つけることができないと、その場合、
ＴＬＢミスが生じたことになるという点に留意された
い。また、複数の仮想タグが、１つの物理的タグに対し
てマッピングされることがある点にも留意されたい。Ｔ
ＬＢヒットが生じると、選択されたＣＡＭエントリは、
仮想タグ１０４に対応する物理的タグについての、ＴＬ
Ｂ ＲＡＭ１１８におけるアドレスを指定する。次に、
ＴＬＢ ＲＡＭ１１８から物理的タグが検索される。次
に、４つのデジタル比較器が、それぞれ、ＴＬＢ ＲＡ
Ｍ１１８からの物理的タグとタグ・セクション１１０か
らの物理的タグ１１２の比較を行う。１対の一致する物
理的タグは、論理回路１２２を介して、４つのデータ行
のうちのどの行がマルチプレクサ１２４によって選択さ
れるかを表示する。特定の索引ビットについて、１対の
一致する物理的タグが存在しない可能性もあり、この場
合、キャッシュ・ミスが生じたことになるという点に留
意されたい。
【００１４】図２には、本発明の実施態様の一例を示す
４ウェイ・セット連想キャッシュが示されている。図２
における索引ビット１０２、キャッシュのデータ・セク
ション１０６、及び、マルチプレクサ１２４は、図１と
同じである。図２のキャッシュの場合、セクション２０
４は、物理的に図１のキャッシュのセクション１１０に
対応するが、新たなデータ行が、図２のキャッシュ内に
納められる場合、物理的タグがセクション２０４に記憶
される代わりに、ベクトル２１２（物理的ヒット・ベク
トルと呼ばれ、さらに詳細に後述する）がセクション２
０４に記憶される。
【００１５】図２のキャッシュの場合、ＴＬＢ２１０
は、２つのＣＡＭ、すなわち、物理的タグを納めた物理
的ＣＡＭ２０６と、仮想タグを納めた仮想ＣＡＭ２０８
を備えている。仮想ＣＡＭ２０８に新たな仮想タグ２０
２が記憶される場合、オペレーティング・システムを介
して、対応する物理的タグ２０３も得られ、対応する物
理的タグ２０３は、物理的ＣＡＭ２０６に記憶される。
物理的ヒット・ベクトル２１２は、物理的タグ２０３を
有する物理的ＣＡＭ２０６内の各位置に対応する２進数
「１」を備えている。例えば、物理的ヒット・ベクトル 00000000000001000100000000000000 は、仮想タグ２０２に対応するこのキャッシュ行に関す
る物理的タグが、３２エントリの物理的ＣＡＭ２０６の
うち１４番目のエントリ及び１８番目のエントリ（任意
に、１番目を左から始めて数えた引例の場合）にあるこ
とを表している。例えば、新たな仮想タグ２０２及び対
応する物理的タグ２０３は、それぞれ、ＣＡＭ２０８及
び２０６の１８番目のエントリに配置することが可能で
あり、ＣＡＭ２０８及び２０６の１４番目のエントリに
は、それぞれ、異なる仮想タグ及び同じ対応する物理的
タグが既に納められている可能性がある。キャッシュに
新たな行を入力すると、新たな行の物理的タグ２０３の
物理的ＣＡＭ２０６における全てのインスタンスの位置
を示す２進数の物理的ヒット・ベクトル２１２が、物理
的ＣＡＭ２０６によって生成され、キャッシュ・セクシ
ョン２０４における索引ビットによって決まる行位置及
びセット配置アルゴリズムによって決まる列位置に記憶
される。
【００１６】図２のキャッシュに関するキャッシュ・ア
クセスの場合、仮想タグ２０２は、仮想ＣＡＭ２０８に
よって、仮想ヒット・ベクトルと呼ばれるベクトル２１
４を生成するために用いられる。ＴＬＢミスがあると、
仮想ヒット・ベクトル２１４は、全て「ゼロ」になる。
ＴＬＢヒットがあると、仮想ヒット・ベクトル２１４
は、仮想ＣＡＭ２０８における仮想タグ２０２の１つの
位置を示す単一２進数「１」を備える。（ＴＬＢにおけ
る各仮想タグは、ちょうど先行技術のＴＬＢにおけるよ
うに一意的でなければならない）。
【００１７】キャッシュ・アクセスに関して、索引ビッ
ト１０２によって、キャッシュ・セクション２０４にお
ける１つのセットをなす４つの物理的ヒット・ベクトル
が選択される。図１のキャッシュの場合、任意のセット
をなす索引ビット１０２に関して、セクション１１０に
おいて選択された４つの物理的タグは、ＴＬＢからの物
理的タグに一致する。同様に、図２のキャッシュの場合
も、固定ページ・サイズであれば（可変ページ・サイズ
の修正例については後述する）、任意のセットをなす索
引ビット１０２に関して、セクション２０４において選
択された４つの物理的ヒット・ベクトルのうちの１つだ
けが、仮想ヒット・ベクトル２１４における２進数
「１」（仮想ＣＡＭ２０８における仮想タグの１つの位
置）に対応する、２進数「１」（物理的ＣＡＭ２０６に
おける物理的タグの全ての位置）を備えることになる。
固定ページ・サイズの場合、次に、ヒット・ベクトルに
おける単一対をなす一致する「１」によって、マルチプ
レクサ１２４によってどのデータ行が選択されるかの判
定が行われる。所定のセットをなす索引ビット１０２に
関して、比較されたベクトル中に一致する「１」がない
可能性もあり、その場合、キャッシュ・ミスが生じたこ
とになるという点に留意されたい。
【００１８】仮想ヒット・ベクトル２１４は、ＴＬＢ
ＲＡＭから物理的タグを検索するために、一般に、ＴＬ
Ｂ ＣＡＭ（例えば、図１のＣＡＭ１１６）によって内
部で生成しなければならない情報を含んでいる。しか
し、図２のキャッシュの場合、この情報は、ＴＬＢ２１
０外部で用いられ、キャッシュ・アクセスのために、Ｔ
ＬＢ２１０からの物理的タグが検索されることはない。
ＴＬＢ２１０からの物理的タグの検索操作をなくすこと
によって、キャッシュのクリティカルな時間経路におい
てかなりの時間量を要する操作が排除されることにな
る。
【００１９】図１のデジタル比較器１２０には、大型フ
ァン・インＮＯＲゲート（または論理的同等物）が後続
する、各ビット位置毎の排他的ＯＲゲートが含まれてい
る。すなわち、２つの物理的タグを比較するため、各ビ
ット位置毎に、２つの一致する論理「１」と、２つの一
致する論理「０」のいずれであるかを調べなければなら
ない。対照的に、図２における物理的ヒット・ベクトル
の場合、一致を確認するのに、１対の一致する論理
「１」だけしか必要としない。従って、比較器２１６
は、大型ファン・インＮＯＲゲートが後続する単純なＡ
ＮＤゲートとすることが可能である。ＡＮＤゲートは、
排他的ＯＲゲートより高速かつ小型（単純）であり、Ｏ
Ｒゲートは、ＮＯＲゲートよりはるかに高速である。
【００２０】可能性のある複雑化の要因の１つは、プロ
セッサ・アーキテクチャによっては、アドレス・ビット
の一部が、可変とすることが可能なページ・サイズを示
す場合があり得るという点である。一般に、これは、コ
ンテキストまたはジョブによって決まる。例えば、ある
ページ・サイズをデータ・ベース・アプリケーションに
利用し、別のページ・サイズをグラフィックス集約的ア
プリケーションに利用することが可能である。上述のよ
うに、索引ビットは、一般に、仮想アドレスと物理的ア
ドレスにとって同じである。ページ・サイズが変化する
と、物理的索引のビット数が変化する。換言すれば、ア
ドレス中に、仮想の場合もあれば、物理的な場合もある
ビット・セットが存在する可能性がある。本特許文書に
おいて、これらのビット・ページをオフセット・ビット
と呼ぶことにする。各ページ・オフセット・ビット毎
に、オペレーティング・システムによって、対応するペ
ージ・オフセット・ビットが物理的か、あるいは、仮想
かを示すマスク・ビットが供給される。さらに、オフセ
ット・ビットは、ＴＬＢに送られる仮想タグと共に含め
られ、マスク・ビットは、各オフセット・ビット毎に、
そのオフセット・ビットが、ＴＬＢのＣＡＭによる比較
において排除すべきでかあるか否かを指示する。可変ペ
ージ・サイズの場合、物理的タグが物理的ＣＡＭ２０６
に記憶されると、記憶されたタグの長さは、実際上、マ
スキングの結果として、ページ・オフセット・ビットが
どれだけ含まれているかに応じて変動する。しかし、物
理的ヒット・ベクトル２１２は、物理的タグ２０３だけ
（ページ・オフセット・ビットを除いて）に対する比較
結果を表している。
【００２１】ページ・サイズが可変のシステムの場合、
図２におけるキャッシュには、独立したＣＡＭ構造２２
０が含まれている。構造２２０の各エントリは、ある行
のアドレスに関するページ・オフセット・ビットと、対
応するマスク・ビットから構成される。キャッシュ内の
ある行にアクセスする場合、仮想索引ビットによって、
ＣＡＭ構造２２０内のある行が選択される。ＣＡＭ構造
２２０は、記憶されたページ・オフセット・ビット（オ
フセット・ビット２２４からの）と受信したページ・オ
フセット・ビット２２２（仮想アドレス２００におけ
る）の比較を行う。ＣＡＭ構造２２０の場合、記憶され
ているマスク・ビットは、各オフセット・ビット位置毎
に、比較にオフセット・ビットを含めるべきか否かを指
示する。同様に、物理的ＣＡＭ２０６には、オフセット
・ビット及びマスク・ビットが、物理的タグと共に含ま
れており、ＴＬＢ２１０の場合、記憶されているマスク
・ビットは、各オフセット・ビット位置毎に、比較から
オフセット・ビットを除くべきか否かを指示する。各マ
スク・ビット毎に、対応するページ・オフセット・ビッ
トが、ＣＡＭ２２０の比較に含められ、ＣＡＭ２０６の
比較において排除される、あるいは、この逆になるとい
う点に留意されたい。物理的ヒット・ベクトル２１２
は、物理的タグ２０３だけ（ページ・オフセット・ビッ
トを除いて）に対する比較結果を表すので、ページ・サ
イズが可変の、大きいページ・サイズの場合、比較器２
１６によってうまくゆく突き合わせが複数生じる可能性
がある。ＣＡＭ２２０は、物理的ヒット・ベクトル２１
２の生成において無視されたオフセット・ビットを比較
する。ＣＡＭ２２０の出力は、有効（対応するマスク・
ビットの指示に従って含まれる）オフセット・ビットの
行セットである。次に、比較器２２６は、ＣＡＭ２２０
の出力とアドレス２００のページ・オフセット・ビット
２２２を比較する。次に、比較器２２６の出力を利用し
て、さらに比較器２１６の出力の認定が行われる。次
に、論理回路２１８は、セクション１０６からの４つの
データ行のうちのどの１つがマルチプレクサ１２４によ
って選択されるかを示す２つの出力を生じる。
【００２２】本発明の以上の説明は、例証及び解説を目
的として提示されたものである。余すところなく述べよ
うとか、あるいは、本発明を開示の形態そのままに制限
しようとするものではなく、上記教示に鑑みて、他の修
正及び変更を加えることも可能である。この実施態様
は、本発明の原理及びその実際の適用例を最も明確に説
明することによって、当該技術者が、企図される特定の
用途に適合するさまざまな実施態様及びさまざまな修正
において、本発明を最も有効に利用できるようにするた
めに、選択され、解説された。付属の請求項は、先行技
術による制限のある場合を除き、本発明の他の代替実施
態様を含むものと解釈されることを意図している。
【００２３】以上、本発明の実施例について詳述した
が、以下、本発明の各実施態様の例を示す。
【００２４】[実施態様１］キャッシュによって仮想ア
ドレス（２００）を受信するステップであって、該仮想
アドレスは仮想タグ（２０２）と仮想索引（１０２）と
を有し、該仮想タグは、前記仮想アドレスとは別の、対
応する物理的タグ（２０３）を備えている、ステップ
と、前記仮想タグに対する一致を含む変換索引バッファ
（２１０）内の位置を示す第１のベクトルを該変換索引
バッファによって発生するステップと、第１のメモリ構
造（２０４）によって、前記仮想索引によって決まる少
なくとも１つの位置から、前記変換索引バッファ内の少
なくとも１つの位置に前記物理的タグに一致するタグが
納められているか否かを示す少なくとも１つの第２のベ
クトルを検索するステップと、デジタル比較器（２１
６）によって、前記第１のベクトルと前記第２のベクト
ルとを比較するステップと、比較結果を利用して、第２
のメモリ構造（１０６）からデータを選択するステップ
と、を備えて成る、キャッシュ内のデータにアクセスす
る方法。
【００２５】［実施態様２]前記仮想アドレスには、さ
らに、ページ・オフセット・ビット（２２２）が含ま
れ、第３のメモリ構造（２２０）によって、前記仮想ア
ドレスのページ・オフセット・ビット（２２２）と、前
記第３のメモリ構造の、前記仮想索引によって決まる位
置に記憶されたページ・オフセット・ビット（２２４）
とを比較するステップと、前記第３のメモリ構造による
比較結果を利用して、前記デジタル比較器による比較結
果を検定するステップと、をさらに備えて成ることを特
徴とする、実施態様１に記載の方法。
【００２６】[実施態様３]索引ビット（１０２）とタグ
・ビット（２０２）とを有する仮想アドレス（２００）
を受信するキャッシュであって、前記タグ・ビットを受
信して、該タグ・ビットに対応する特定の仮想アドレス
・タグを納めた変換索引バッファ内の位置を示す第１の
ベクトル（２１４）を発生する、変換索引バッファ（２
１０）と、索引ビットを受信するメモリ構造（２０４）
であって、該メモリ構造は第２のベクトルを有し、該第
２のベクトルの各々は前記変換索引バッファ内における
物理的アドレス・タグの少なくとも１つの位置を示し、
少なくとも１つの第２のベクトルは、前記索引ビットに
よって指定される、メモリ構造と、前記メモリ構造から
の第２のベクトルと前記変換索引バッファからの第１の
ベクトルとを比較する少なくとも１つのベクトル比較器
（２１６）と、を備えて成るキャッシュ。
【００２７】[実施態様４]前記仮想アドレスが、さら
に、ページ・オフセット・ビット（２２２）を有し、記
憶ページ・オフセット・ビット（２２４）を納め、前記
索引ビットを受信する第２のメモリ構造（２２０）と、
前記索引ビットによって指定される、前記第２のメモリ
構造からの記憶ページ・オフセット・ビットを受信し、
前記仮想アドレスからページ・オフセット・ビット（２
２２）を受信する少なくとも１つのオフセット比較器
（２２６）と、前記オフセット比較器の出力と前記ベク
トル比較器の出力とを受信する少なくとも１つの論理ゲ
ートと、をさらに備えて成ることを特徴とする、実施態
様３に記載のキャッシュ。
【００２８】
【発明の効果】以上説明したように、本発明を用いるこ
とにより、キャッシュ・メモリにおけるアクセス時間を
改善することができる。
【図面の簡単な説明】
【図１】セット連想キャッシュの一例に関する略ブロッ
ク図である（先行技術）。
【図２】本発明によるセット連想キャッシュの一例に関
する略ブロック図である。
【符号の説明】
１０２：索引ビット １０６：データ・セクション １２４：マルチプレクサ ２０２：仮想タグ ２０３：物理的タグ ２０４：キャッシュ・セクション ２０６：物理的ＣＡＭ ２０８：仮想ＣＡＭ ２１０：ＴＬＢ ２１２：物理的ヒット・ベクトル ２１４：仮想ヒット・ベクトル ２１６：比較器 ２２０：ＣＡＭ構造 ２２２：ページ・オフセット・ビット

Claims (1)

    【特許請求の範囲】
  1. 【請求項１】キャッシュによって仮想アドレスを受信す
    るステップであって、該仮想アドレスは仮想タグと仮想
    索引とを有し、該仮想タグは、前記仮想アドレスとは別
    の、対応する物理的タグを備えている、ステップと、 前記仮想タグに対する一致を含む変換索引バッファ内の
    位置を示す第１のベクトルを該変換索引バッファによっ
    て発生するステップと、 第１のメモリ構造によって、前記仮想索引によって決ま
    る少なくとも１つの位置から、前記変換索引バッファ内
    の少なくとも１つの位置に前記物理的タグに一致するタ
    グが納められているか否かを示す少なくとも１つの第２
    のベクトルを検索するステップと、 デジタル比較器によって、前記第１のベクトルと前記第
    ２のベクトルとを比較するステップと、比較結果を利用
    して、第２のメモリ構造からデータを選択するステップ
    と、を備えて成る、キャッシュ内のデータにアクセスす
    る方法。
JP10300695A 1997-10-22 1998-10-22 キャッシュ・メモリ Pending JPH11203199A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US955,821 1997-10-22
US08/955,821 US6014732A (en) 1997-10-22 1997-10-22 Cache memory with reduced access time

Publications (1)

Publication Number Publication Date
JPH11203199A true JPH11203199A (ja) 1999-07-30

Family

ID=25497399

Family Applications (1)

Application Number Title Priority Date Filing Date
JP10300695A Pending JPH11203199A (ja) 1997-10-22 1998-10-22 キャッシュ・メモリ

Country Status (3)

Country Link
US (1) US6014732A (ja)
EP (1) EP0911737A1 (ja)
JP (1) JPH11203199A (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013004101A (ja) * 2011-06-17 2013-01-07 Freescale Semiconductor Inc データプロセッサ内での分岐先バッファのアドレス指定

Families Citing this family (37)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6199140B1 (en) * 1997-10-30 2001-03-06 Netlogic Microsystems, Inc. Multiport content addressable memory device and timing signals
US6425065B2 (en) * 1997-12-31 2002-07-23 Intel Corporation Tag RAM with selection module for a variable width address field
US6192459B1 (en) * 1998-03-23 2001-02-20 Intel Corporation Method and apparatus for retrieving data from a data storage device
TW371756B (en) * 1998-05-04 1999-10-11 United Microelectronis Corp Projection memory of selective updating
KR100277902B1 (ko) * 1998-08-18 2001-01-15 김영환 마이크로 프로세서
US6138188A (en) * 1998-09-28 2000-10-24 Mentor Arc Inc. Buffer management device and method for improving buffer usage and access performance in data processing system
KR100280518B1 (ko) * 1998-11-10 2001-03-02 김영환 동기 에스램 회로
US6539455B1 (en) 1999-02-23 2003-03-25 Netlogic Microsystems, Inc. Method and apparatus for determining an exact match in a ternary content addressable memory device
US6460112B1 (en) * 1999-02-23 2002-10-01 Netlogic Microsystems, Llc Method and apparatus for determining a longest prefix match in a content addressable memory device
US6892272B1 (en) 1999-02-23 2005-05-10 Netlogic Microsystems, Inc. Method and apparatus for determining a longest prefix match in a content addressable memory device
US6574702B2 (en) 1999-02-23 2003-06-03 Netlogic Microsystems, Inc. Method and apparatus for determining an exact match in a content addressable memory device
US7272027B2 (en) * 1999-09-23 2007-09-18 Netlogic Microsystems, Inc. Priority circuit for content addressable memory
US6934795B2 (en) * 1999-09-23 2005-08-23 Netlogic Microsystems, Inc. Content addressable memory with programmable word width and programmable priority
US6944709B2 (en) * 1999-09-23 2005-09-13 Netlogic Microsystems, Inc. Content addressable memory with block-programmable mask write mode, word width and priority
US7143231B1 (en) 1999-09-23 2006-11-28 Netlogic Microsystems, Inc. Method and apparatus for performing packet classification for policy-based packet routing
US6625714B1 (en) * 1999-12-17 2003-09-23 Hewlett-Packard Development Company, L.P. Parallel distributed function translation lookaside buffer
US6470437B1 (en) * 1999-12-17 2002-10-22 Hewlett-Packard Company Updating and invalidating store data and removing stale cache lines in a prevalidated tag cache design
US6493812B1 (en) * 1999-12-17 2002-12-10 Hewlett-Packard Company Apparatus and method for virtual address aliasing and multiple page size support in a computer system having a prevalidated cache
US6574711B2 (en) * 1999-12-27 2003-06-03 Matsushita Electric Industrial Co., Ltd. Semiconductor integrated circuit
JP2001184870A (ja) * 1999-12-27 2001-07-06 Mitsubishi Electric Corp 連想メモリ装置およびそれを用いた可変長符号復号装置
US6446187B1 (en) * 2000-02-19 2002-09-03 Hewlett-Packard Company Virtual address bypassing using local page mask
US6643742B1 (en) * 2000-03-20 2003-11-04 Intel Corporation Method and system for efficient cache memory updating with a least recently used (LRU) protocol
US6622204B1 (en) * 2000-09-14 2003-09-16 Cypress Semiconductor Corp. Content-addressable memory with cascaded match, read and write logic in a programmable logic device
US6622208B2 (en) * 2001-03-30 2003-09-16 Cirrus Logic, Inc. System and methods using a system-on-a-chip with soft cache
US6301186B1 (en) * 2001-04-30 2001-10-09 Hewlett-Packard Company RAM cell with column clear
US6772277B2 (en) * 2001-04-30 2004-08-03 Hewlett-Packard Development Company, L.P. Method of writing to a memory array using clear enable and column clear signals
US6918021B2 (en) 2001-05-10 2005-07-12 Hewlett-Packard Development Company, L.P. System of and method for flow control within a tag pipeline
US6622211B2 (en) * 2001-08-15 2003-09-16 Ip-First, L.L.C. Virtual set cache that redirects store data to correct virtual set to avoid virtual set store miss penalty
US6820170B1 (en) * 2002-06-24 2004-11-16 Applied Micro Circuits Corporation Context based cache indexing
US20040054867A1 (en) * 2002-09-13 2004-03-18 Paulus Stravers Translation lookaside buffer
US7146457B2 (en) * 2003-09-24 2006-12-05 Hewlett-Packard Development Company, L.P. Content addressable memory selectively addressable in a physical address mode and a virtual address mode
GB2433613B (en) * 2005-12-22 2010-10-20 Advanced Risc Mach Ltd Variable size cache memory support within an integrated circuit
US8631206B1 (en) * 2007-09-21 2014-01-14 Marvell International Ltd. Way-selecting translation lookaside buffer
US8099580B2 (en) * 2009-06-09 2012-01-17 Freescale Semiconductor, Inc Translation look-aside buffer with a tag memory and method therefor
US8359456B2 (en) * 2010-02-22 2013-01-22 International Business Machines Corporation Generating random addresses for verification of distributed computerized devices
US9836513B2 (en) * 2012-03-12 2017-12-05 Entit Software Llc Page feed for efficient dataflow between distributed query engines
CN107844359A (zh) * 2016-09-20 2018-03-27 杭州华为数字技术有限公司 一种仿真方法及装置

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4969122A (en) * 1989-08-21 1990-11-06 Sun Microsystems, Inc. Apparatus for page tagging in a computer system
US5133058A (en) * 1989-09-18 1992-07-21 Sun Microsystems, Inc. Page-tagging translation look-aside buffer for a computer memory system

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013004101A (ja) * 2011-06-17 2013-01-07 Freescale Semiconductor Inc データプロセッサ内での分岐先バッファのアドレス指定

Also Published As

Publication number Publication date
US6014732A (en) 2000-01-11
EP0911737A1 (en) 1999-04-28

Similar Documents

Publication Publication Date Title
US6014732A (en) Cache memory with reduced access time
US6772316B2 (en) Method and apparatus for updating and invalidating store data
JP3278748B2 (ja) メモリ空間を節約する方法および装置
KR100297454B1 (ko) 컴퓨터장치
US6493812B1 (en) Apparatus and method for virtual address aliasing and multiple page size support in a computer system having a prevalidated cache
US6874077B2 (en) Parallel distributed function translation lookaside buffer
US5493660A (en) Software assisted hardware TLB miss handler
US6138225A (en) Address translation system having first and second translation look aside buffers
US4587610A (en) Address translation systems for high speed computer memories
KR100843536B1 (ko) 컴퓨터 시스템 내의 메모리 관리 향상 방법, 메모리 관리 메커니즘 및 컴퓨터 판독 가능한 기록 매체
US8082416B2 (en) Systems and methods for utilizing an extended translation look-aside buffer having a hybrid memory structure
US5058003A (en) Virtual storage dynamic address translation mechanism for multiple-sized pages
US6145064A (en) Method of efficiently updating hashed page tables
US11409663B2 (en) Methods and systems for optimized translation of a virtual address having multiple virtual address portions using multiple translation lookaside buffer (TLB) arrays for variable page sizes
JPH0619793A (ja) キャッシュ・アクセスのための仮想アドレス変換予測の履歴テーブル
US4914582A (en) Cache tag lookaside
US5778427A (en) Method and apparatus for selecting a way of a multi-way associative cache by storing waylets in a translation structure
US5897651A (en) Information handling system including a direct access set associative cache and method for accessing same
US6990551B2 (en) System and method for employing a process identifier to minimize aliasing in a linear-addressed cache
EP0206050A2 (en) Virtually addressed cache memory with physical tags
US20140006747A1 (en) Systems and methods for processing instructions when utilizing an extended translation look-aside buffer having a hybrid memory structure
US6226731B1 (en) Method and system for accessing a cache memory within a data-processing system utilizing a pre-calculated comparison array
US6581139B1 (en) Set-associative cache memory having asymmetric latency among sets
GB2395588A (en) Apparatus supporting multiple page sizes with address aliasing

Legal Events

Date Code Title Description
A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20031127

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20031202

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20040302

A02 Decision of refusal

Free format text: JAPANESE INTERMEDIATE CODE: A02

Effective date: 20040518

A521 Written amendment

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20040813

A911 Transfer of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A911

Effective date: 20041008

A912 Removal of reconsideration by examiner before appeal (zenchi)

Free format text: JAPANESE INTERMEDIATE CODE: A912

Effective date: 20050506