[go: up one dir, main page]

JPH07104816B2 - コンピュータシステムを動作する方法及びコンピュータシステムにおけるメモリ管理装置 - Google Patents

コンピュータシステムを動作する方法及びコンピュータシステムにおけるメモリ管理装置

Info

Publication number
JPH07104816B2
JPH07104816B2 JP5500873A JP50087392A JPH07104816B2 JP H07104816 B2 JPH07104816 B2 JP H07104816B2 JP 5500873 A JP5500873 A JP 5500873A JP 50087392 A JP50087392 A JP 50087392A JP H07104816 B2 JPH07104816 B2 JP H07104816B2
Authority
JP
Japan
Prior art keywords
cache
address
main memory
data
page
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.)
Expired - Lifetime
Application number
JP5500873A
Other languages
English (en)
Other versions
JPH05509189A (ja
Inventor
リチャード エル シテス
Original Assignee
ディジタル イクイプメント コーポレイション
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 ディジタル イクイプメント コーポレイション filed Critical ディジタル イクイプメント コーポレイション
Publication of JPH05509189A publication Critical patent/JPH05509189A/ja
Publication of JPH07104816B2 publication Critical patent/JPH07104816B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime 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/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/653—Page colouring

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)

Description

【発明の詳細な説明】 発明の分野 本発明は、コンピュータのオペレーションに係り、より
詳細には、仮想メモリを用いたコンピュータに直接マッ
プ式のキャッシュを使用してセット連想キャッシュの性
能を模擬する方法に係る。
先行技術 プロセッサの速度が高くなるにつれてコンピュータシス
テムに高速キャッシュメモリを使用することが益々重要
になってきた。例えば、カナダ公開公報第2,045.833−
０号に開示された形式の高速RISCプロセッサは、CPUの
サイクルタイムである５ナノ秒で動作し、各サイクル中
に命令を実行するように構成される（減少命令セットコ
ンピュータ（RISC）の概念を実施することによって）。
メインメモリのサイクルタイムが300ナノ秒の場合に、C
PUは、現在一般的となったキャッシュヒット（当たり）
率を用いてメモリを待機するのにその時間の95％を費や
すことが計算できる。メモリの性能をCPUにより近づけ
るために、キャッシュメモリは、第１、第２そしてある
場合には第３レベルのキャッシュを構成するようなハイ
アラーキ構成とされ、当然ながら、キャッシュメモリの
速度が高められると共に、経済性も増大される。しか
し、これらの高速CPUにとって受け入れられる性能を得
るためには、キャッシュのヒット率を高めなければなら
ない。
キャッシュメモリは、直接マップ式アーキテクチャか又
はＮウェイ連想式かのいずれかで構成される。直接マッ
プ式キャッシュは、投与のデータ項目がキャッシュ内の
１つの場所にしか記憶できず、ヒット率は低いが、回路
で簡単で高速であるという利点がある。Ｎウェイ連想キ
ャッシュは、投与のデータ項目をキャッシュ内のＮ個の
異なる場所のいずれにも記憶でき、同じサイズの直接マ
ップ式キャッシュよりも高いヒット率を生じさせる。Ｎ
ウェイ連想キャッシュの高いヒット率は、キャッシュ内
での情報配置の融通性が高いことによるものである。
直接マップ式キャッシュの速度と構造簡易性から高性能
コンピュータシステムにこの形式のキャッシュを使用
し、しかも、Ｎウェイ連想キャッシュに本来あるのと同
様の高いキャッシュヒット率を達成できることが望まれ
ている。
発明の要旨 本発明は、その広い観点において、 ａ）メインメモリ及び直接マップ式キャッシュをアクセ
スするCPUを備えていて、データが上記メインメモリに
ページで記憶され、 ｂ）更に、キャッシュミス（外れ）を生じるアクセスに
対し上記メインメモリのアドレスを検出する手段と、 ｃ）上記アドレスを含むページの上記メインメモリ内の
位置を上記メインメモリ内の別の位置に変更する手段と
を備えたコンピュータシステム及びその動作方法に関す
る。
本発明の一実施例によれば、直接マップ式キャッシュを
有するコンピュータシステムは、セット連想キャッシュ
の作用を模擬するように動作される。この方法は、デー
タがページで取り扱われそしてキャッシュが物理アドレ
スによってアクセスされるような仮想メモリ型オペレー
ティングシステムを実行するCPUにおいて有用である。
この方法は、キャッシュミスを検出し、その検出された
キャッシュミスのアドレスを含むメインメモリのページ
を再マッピングし、スラッシングを生じるメモリ参照が
キャッシュにも共存し得るようにすることを含む。異な
る物理ページフレーム内にあるがキャッシュ内の同じ位
置にマップされる２つのメモリアドレスは、直接マップ
式キャシュに同時に存在しないことがあり、CPUで実行
されるタスクによりこれら２つのアドレスを交互に参照
すると、スラッシングを招く。しかしながら、メインメ
モリ内のこれらアドレスの１つの位置が変更された場合
には、これらのアドレスを有するデータ項目がキャッシ
ュにも共存でき、スラッシングはもはや生じないので、
性能は著しく向上される。仮想メモリオペレーティング
システムを実行するCPUの場合は、データ又は命令のペ
ージを異なる物理ページフレームに移動できるが、同じ
仮想アドレスのままにすることができる。これは、単に
ページの新たな物理位置を反映するようにページマップ
テーブルを更新しそして古いページフレームから新たな
ページフレームへデータをコピーするだけで達成され
る。キャッシュミスアドレスをラッチし、そのラッチを
周期的にサンプリングし、そしてこのサンプリングの際
に見っかったアドレスを含むページを再マッピングする
ことにより、スラッシング状態が検出されて動的に修正
される。直接マップ式キャッシュは、２つ以上のページ
を保持する充分な大きさでなければならない。４ページ
よりも多くのページを実質的に保持するキャッシュの場
合には、本発明の模擬技術は、ハードウェアを組み込む
ための典型的な経済性よりも高い連想特性を生み出すこ
とができる。
添付図面を参照した好ましい実施例の以下の詳細な説明
より本発明を更に良く理解することができよう。
図面の簡単な説明 図１は、本発明の一実施例の特徴を使用することのでき
るコンピュータシステムの電気ブロック図である。
図２は、図１のシステムに使用することのできる仮想メ
モリ機構に対するメモリマッピングを示す図である。
図３は、図１のシステムに使用される本発明のキャッシ
ュメモリの電気回路図である。
図４は、本発明の一実施例によりページ番号スワッピン
グ動作を実行するときのメインメモリマップの一部分を
示す図である。
図5a又は5bは、本発明を用いた１つのシステムと本発明
を用いない別のシステムについて、キャッシュアドレス
対時間のグラフにキャッシュミスを示した図である。
好ましい実施例の詳細な説明 図１には、本発明のキャッシュ連想方法を使用すること
のできるコンピュータシステムが示されている。CPU10
は、キャッシュコントローラ12及びCPUバス13を経てシ
ステムバス11へ接続される。メインメモリ14はシステム
バス11に接続されてこれによりアクセスされ、キャッシ
ュメモリ15はキャッシュコントローラ12に接続されてCP
Uバス13により直接アクセスされるようになっている。C
PU10は、UNIX（登録商標）又はVAX/VSM（登録商標）オ
ペレーティングシステムによって与えられるような仮想
メモリマネージメントシステムを実施するものであり、
従って、メインメモリ14により与えられる物理的なメモ
リと、ディスク16の形態の二次記憶装置との間でデータ
のページがスワップされる。VAXアーキテクチャは、参
考としてここに取り上げるレビー氏及びエクハウス氏著
の「コンピュータプログラミング及びアーキテクチャ
ー：ザ・VAX（Computer Programming and Architectur
e:The VAX）」、第２版、デジタル・プレス、1989年に
掲載されている。CPU10は、レビー氏等の文献又は本発
明の譲受人であるデジタル・イクイップメント・コーポ
レーションに譲渡されサンダー、ウーラー及びブラウン
氏の米国特許第5,006,980号に開示されたVAX（登録商
標）形式のものであってもよいが、同じくデジタル・イ
クイップメント・コーポレーションに譲渡されたカナダ
公開公報第2,045.833−０号に開示された高度な64ビッ
トRISC形式のものであるのが好ましい。
CPU10は、先ず、図２に示す全アドレス範囲17内のアド
レスを表す仮想アドレスであってオペレーティングシス
テムによって許されるコンピュータ又はその一部分のア
ーキテクチャ仕様により定められた仮想アドレスを形成
し、次いで、その仮想アドレスを、メインメモリ14のサ
イズによって制限されたアドレスマップ18の物理アドレ
スに変換することにより、メモリレファレンスを発生す
る。上記の変換はページによって行われ、従って、仮想
メモリマップ17のページ19に対する仮想ページアドレス
が物理メモリマップ18のページに対する物理アドレス1
9′に変換される。仮想アドレスと物理アドレスとの間
の変換を行うためにメモリにはページテーブルが維持さ
れ、そして通常は図１に示す変換バッファ20がCPU10に
含まれていて最も最近使用された変換を保持し、これに
より、データレファレンスを行う前に変換を得るのにメ
モリ14内のテーブルを参照する必要がないようになって
いる。現在実行されているタスク（及びオペレーティン
グシステムそれ自体）によって使用されるページのみが
投与の時間に物理メモリ14内におそらく入れられ、即ち
アドレス19′への変換はページテーブル内において実際
に存在するページのみに対するものである。CPU10によ
って参照されるページが物理メモリ14に存在しないと分
かったときには、ページ欠陥が実行されてスワップ動作
を開始し、物理メモリ14からのページがディスクメモリ
16に維持された所望のページとスワップされ、このスワ
ップはオペレーティングシステムの制御のもとで行われ
る。
又、図１のCPU10は、前記カナダ公開公報に開示された
ように命令キャッシュ即ちＩキャッス21と、データキャ
ッシュ即ちＤキャッシュ22とを備えた内部キャッシュメ
モリも有しているが、これらは本発明のこの実施例によ
る直接マップ式キャッシュ15の動作には関係しない。従
って、図１のコンピュータシステムによって使用される
メモリは、最も高速のものが内部キャッシュ21、22で、
次に高速のものがキャッシュ15で、次いで、メインメモ
リ14で、最後にディスク16のスワップスペースであるよ
うなハイアラーキ構成のものである。最も高速のものと
低速のものとの間の速度の差は何桁もある。内部キャッ
シュとキャッシュ15は数CPUサイクル内にアクセスさ
れ、一方、メインメモリ14はおそらく10ないし100又は
それ以上のCPUサイクルでアクセスされそしてディスク1
6のページスワップは数百又は数千のCPUサイクルを必要
とする。従って、システムの性能は、現在使用されてい
る命令及びデータがキャッシュに維持されているかどう
かによって大きく左右される。物理メモリ14内のデータ
のサブレット（図２の18にマップされた）は、所与の時
間にキャッシュ15にあり、キャッシュ15内のデータのサ
ブレットは内部キャッシュ21及び22にある。
キャッシュメモリ15は直接マップ式のものであり、図３
に示すように構成される。データは、行24のアレイ23と
して示されたメモリチップのアレイに記憶され、各行は
多数のブロック25を有している。各ブロック25は、例え
ば、64バイト即ち８クオドワードのデータを含む。キャ
ッシュ15（又はメインメモリ14）をアクセスするのに使
用されるCPUバス13上の物理アドレス26は、ブロック25
内のバイト（又はワード）を選択する下位フィールド27
と、行24内のブロック25を選択するフィールド28と、行
を選択するフィールド29と、タグフィールド30とを含ん
でいる。フィールド28は、行内のブロックを選択するた
めにデコーダ31へ送られ、そしてフィールド29は行デコ
ーダ32へ送られて行が選択され、それがデコーダ31へ出
力される。フィールド27のアドレスの下位ビットはデコ
ーダ33へ送られてブロック内のバイト又はワードが選択
され、CPUバス13のデータバスに接続される。キャッシ
ュコントローラ12においては、タグ記憶部34がブロック
25の個数に対応する多数のタグを保持し、CPUバス13の
アドレスバスのアドレス26からのフィールド28及び29
は、行及び列デコーダ35によって使用されて、１つのタ
グが選択され、タグ比較回路36へ送られる。タグ比較回
路36の他方の入力はアドレス26からのタグフィールド30
である。デコーダ35によって選択された記憶されたタグ
とタグフィールド30とが合致した場合には、タグのヒッ
トが出力37によって信号され、データアレイ23からの出
力38のデータが使用されるが、さもなくば、ミスが信号
されてデータ出力が廃棄される。ミスが生じたときは、
メモリ14へのレファレンスを行わねばならず、従って、
アドレスはキャッシュコントローラ12を経てシステムバ
ス11へ通される。
図３のキャッシュ15は、フィールド28及び29に所与の値
のアドレスビットを有する第１のデータ項目を、キャッ
シュアレイ23の１つのそして１つだけの位置（ブロック
25）に記憶しなければならないという点で直接マップ式
である。フィールド28及び29に同じ値のアドレスビット
を有する第２のメモリ位置に対してメモリ参照がなされ
た場合には、これがその参照された第１データ項目と同
じ位置にマップされ、従って、第１のものは第のものに
よってオーバーライトされねばならない。例えば、CPU1
0で実行しているタスクがフィールド28及び29に同じア
ドレスビットを有する２つの異なるページに対して同じ
インデックスを参照する場合には、２つのページからの
このインデックスを含むブロックがキャッシュにおいて
繰り返しオーバーライトされ、スラッシング状態を招
く。これに対し、セット連想キャッシュでは、所与のア
ドレス値をキャッシュアレイ内の２つ以上の位置にマッ
プすることができ、従って、等しいビットの対応セット
を有する異なるページからの２つのアドレスがキャッシ
ュ内に同時に存在することができる。しかしながら、図
３に示す直接マップ式キャッシュを実施するハードウェ
アは、セット連想キャッシュに比して動作が迅速であ
る。というのは、比較回路36において１つのタグ比較動
作しか必要とされないからである。セット連想キャッシ
ュの場合には、タグアドレスを多数の考えられる合致に
ついて比較し、次いで、対応するデータも選択しなけれ
ばならない（タグ比較が完了した後に）。この付加的な
段階が当然ながら動作を低速なものにする。
例えば、図１のコンピュータシステムで実行される仮想
メモリシステムのページサイズが1Kバイトであり、10ビ
ットアドレス値の後に下位バイトアドレス（２進）が繰
り返されると仮定する。又、キャッシュ15の構成が2Kバ
イトであって、このキャッシュは図２の物理メモリマッ
プ18の部分を合計2Kバイトまでマップし、これらの部分
は所与の時間に異なるページ（但し、全部で２ページ）
からの多数のブロックで構成されると仮定する。２進ア
ドレスでビット＜10:0＞がゼロの境界において物理アド
レスが始まるデータ項目が常にキャッシュ15の第１ブロ
ックにマップされる。従って、物理アドレス0000、204
8、4096等はキャッシュ内の同じ場所にマップされ、即
ち、フィールド28及び29は、例えば、アドレス26のビッ
ト＜10:4＞が同じであるものを含む。それ故、物理位置
0000及び2048を交互にアクセスするタスクは、図３の直
接マップ式キャッシュ15において常にキャッシュミスを
生じることになる。これに対し、２ウェイ連想キャッシ
ュ（又はより高い連想特性のもの）においては、２つの
データ項目を同時にキャッシュ内に維持することがで
き、従ってこれらの２つの物理アドレスを交互に繰り返
しアクセスすることによりキャッシュヒットが得られ
る。繰り返しミスを生じそしてキャッシュから互いに変
位している２つ以上の位置を「スラッシング」と称す
る。
ここに開示するように、キャッシュ15が、CPU10で実行
している仮想メモリ管理環境においてＮページを保持す
る充分な大きさである場合には、Ｎウェイ連想特性の作
用を得るようにページが再マップされる。キャッシュ15
が２つの1Kバイトページを保持できるような図４の例で
は、オペレーティングシステムが仮想ページをメモリ14
（メモリマップ18）の物理ページに再マップして、２ウ
ェイ連想特性を模擬するという所望の作用を得ることが
できる。仮想アドレス0000及び2048は異なった仮想アド
レスページにあり、キャッシュ15内の同じ位置にマップ
される２つの物理ページ（ページフレーム番号301及び3
03のような）にマップすることができる。このようなマ
ッピングの場合に、直接マップ式キャッシュ15は、仮想
アドレス0000及び2048へ繰り返しアクセスがなされたと
きにスラッシングを生じる。異なる仮想−物理マッピン
グ（ページフレーム番号（PFN）301及び303ではなくて
ページフレーム番号301及び302を指定するような）で
は、2Kバイトキャッシュ15において両方のページが同時
に存在することができ、キャッシュは２ウェイ連想キャ
ッシュの作用を与える。ページフレーム番号PFN303にあ
った同じデータは物理メモリ14内のPFN302に再書き込み
され、従って、キャッシュ15内の同じ位置に既にマップ
されている一対のブロックが今度は異なるブロック位置
にマップされる。２つの項目に対する物理アドレス26の
アドレスビットのセットは今度はフィールド28及び29に
異なるビットをもつことになる。
オペレーティングシステムによりデータをコピーしそし
て仮想ページに指定されたページフレーム番号を再マッ
プするのは簡単なタスクである（この機能は、不良メモ
リブロック、即ちソフトのエラー等を示すブロックを再
マップするためのUNIX又はXAX/VMSに既に存在する）。
しかしながら、先ず、スラッシングを生じるようなデー
タ項目を検出しなければならない。これら項目の有無
は、もちろん、データに依存すると共にアプリケーショ
ンソフトウェアに存在するものであり、従って、実行時
間の前にいつその状態が生じるかを予想することは実質
上不可能であり、又、ソフトウェアが別に呼び出された
ときには、スラッシングの実例がおそらくプログラム内
の別の時間及び場所で生じるであろう。その当該ソフト
ウェアは、その状態が生じたかどうか分かる前であって
且つその状態の各実例の位置が分かる前に実行していな
ければならない。実行時間中にスラッシング状態を検出
する１つの方法は、キャッシュミスを生じるアドレスの
サブセット（例えば、６ビットのミスカウンタ40によっ
て制御される１オブ64のような）をラッチし（メモリ又
は図３のレジスタ39に）、そしてタイマー割り込みルー
チンによりこのラッチ39のアドレスを周期的に読み取る
ことである。このように実施される方法では、ミスアド
レスの流れのこのサンプルに基づいてページ番号を選択
的に再マッピングし（図４のように）、スラッシングを
減少させる。ミスアドレス流のサブセットをサンプリン
グする目的は、タイマー割り込みルーチンがミスアドレ
スラッチ39においてタイマー割り込みルーチンそれ自体
のアドレスを常時見い出すのを回避するためである。ミ
スラッチ39及びカウンタ40は、キャッシュコントローラ
12又はCPU10の一部分として構成することもできるし、
或いはCPUバス13に接続された個別のハードウェアであ
ってもよい。
使用することのできる１つの再マッピングアルゴリズム
は、ミスラッチ39から１秒当たり100ないし1000のサン
プルを取り出しそしてそのサンプリングされた各ページ
を図４に示すように異なる物理メモリ位置（異なるペー
ジフレーム）へと再マッピングすることである。新たな
PFNを選択するアルゴリズムは、単に既存のPFNを減少し
そして変位したPFNを増加するだけでよい。もう１つの
アルゴリズムは、オペレーティングシステムが追跡する
物理メモリ内の「非割り当てページ」の１つを使用し、
即ち、移動されるべきページフレームに未使用のページ
フレーム番号の１つを与え、これにより、切り換えねば
ならないような変位したページがないようにすることで
ある。このように、新たな番号が指定された後に、この
方法では、１ページ又は２ページを物理メモリ14内の新
たな位置に移動する必要がある。実際にスラッシングを
生じる位置は、高い確率で、サンプリングされ移動され
て終了となる。又、スラッシングページは、高い確率で
（少なくとも数回のこのような移動の後に）、ハードウ
ェアＮウェイ連想キャッシュ（Ｎは直接マップ式キャッ
シュ15が保持できるページ数である）に等価なキャッシ
ュ構成に到達し、スラッシングが減少される。
本発明の方法を使用する効果を実証するものとして、キ
ャッシュミスの記録を図5aに示した。これは本発明の改
良を使用しない場合である。このグラフの座標は、図に
おいて上から下へ延びる時間と、左から右へ延びるキャ
ッシュメモリアドレスであり、各マークがキャッシュミ
スで、マークの密度がスラッシングの程度を示してお
り、全くマークがないのが理想的な状態である。この例
では、キャッシュを約１ページのレベルまで満たし、次
いでゼロまで戻ると思われるパターンをたどりそして同
じ一般的なパターンを再びたどり始めるようなミスを示
すアプリケーションプログラムが実行される。キャッシ
ュの第２ページは、たとえ存在しても、このトレースに
は使用されないか又は少なくともほとんどミスが現れな
いと思われる。図5aには、時間に伴う性能の改善が見ら
れず、最初のパターンが不定に繰り返されると考えられ
る。これに対し、図5bでは、キャッシュのサイズは同じ
であるが、本発明の方法が使用されている。ここでは、
最初のパターンは、図の上部において図5aと同じであ
り、次いで、第２のパターンは、キャッシュの第２ペー
ジを満たし始めると思われ、そしてミスの回数（マーク
の密度）はプログラムの実行が続くにつれて徐々に減少
され、やがて、グラフの下部において、その密度が著し
く低下する。このグラフの全時間は、上から下まで約２
秒である。本発明を用いる特徴は、プログラムの実行が
時間と共に変化することであり、即ちアドレス動作のパ
ターンが上記の現象によりスラッシングを生じるような
ものである場合に性能が向上することである。しかしな
がら、あるプログラムでは、アドレス動作が著しくラン
ダムなものとなり、図5a及び5bに示すような効果が生じ
ない。全くランダムなアドレスを発生する実験では、本
発明の方法を用いても全く改善は与えられず、実際に
は、ランダムなスラッシングを検出した後にページを移
動する時間が必要なために僅かに性能上不利益があるこ
とが示される。しかしながら、ほとんど全てのプログラ
ムは、一般にはループであることが多いのでランダムな
アドレスパターンはほとんど示さず、従って、大部分の
プログラムは、本発明の方法を使用したときには時間に
伴う性能の改善をもたらす。
本発明の方法によってもたらされる改良された動作は、
高速で簡単な構造の直接マップ式キャッシュメモリデバ
イスを使用できるようにする一方、低速で複雑なＮウェ
イ連想キャッシュハードウェアにほぼ匹敵するキャッシ
ュヒット性能を達成できるようにする。速度の点からの
全性能は、セット連想キャッシュを使用した場合より優
れている。というのは、セット連想キャッシュに本来あ
るハードウェア遅延が存在しないからである。
特定の実施例について本発明を説明したが、本発明をこ
れに限定するものではない。当業者であれば、ここに開
示した実施例の種々の変更や別の実施例が明らかとなろ
う。それ故、本発明の範囲内に入るこれらの変更や別の
実施例は本発明の請求の範囲内に包含されるものとす
る。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 ＩＢＭ Ｔｅｃｈｎｉｃａｌ Ｄｉｓｃ ｌｏｓｕｒｅ Ｂｕｌｌｅｔｉｎ Ｖｏ ｌ．32，Ｎｏ．８Ａ，Ｊａｎｕａｒｙ 1990，Ｐ．334−337，ＸＰ82829“ＰＡＧ Ｅ ＡＬＬＯＣＡＴＩＯＮ ＣＯＮＴＲＯ Ｌ"

Claims (6)

    【特許請求の範囲】
  1. 【請求項１】プロセッサ、データを記憶するメインメモ
    リ及び選択されたメインメモリアドレスに記憶された上
    記データに対応するデータを記憶するキャッシュを有す
    るコンピュータシステムを動作する方法において、 ａ）データの複数のページが記憶されている複数のキャ
    ッシュ位置を識別する上記メインメモリアドレスを使用
    して上記キャッシュにアクセスしてデータの複数のペー
    ジを獲得し、 ｂ）上記ページが上記識別された位置に見当たらないキ
    ャッシュアクセスから成る複数のキャッシュミスをそれ
    ぞれ検出し、 ｃ）上記キャッシュミスに使用される上記メインメモリ
    アドレスの予め選択されたサブセット（ここで、サブセ
    ットは１よりも大きく上記キャッシュミスの総数よりも
    小さい）を記憶し、 ｄ）上記記憶されたメインメモリアドレスを選択された
    時間でサンプリングし、 ｅ）上記サンプリングされたメインメモリアドレスの各
    々におけるデータを上記メインメモリアドレスの別のア
    ドレスに移動する、 段階から成ることを特徴とする方法。
  2. 【請求項２】上記記憶段階は、上記キャッシュミスをカ
    ウントしてキャッシュミスＮ個（ここで、Ｎは１よりも
    大きく上記キャッシュミスの総数よりも小さい整数であ
    る）につき１個を記憶する段階から成ることを特徴とす
    る請求項１に記載の方法。
  3. 【請求項３】プロセッサ、データを記憶するメインメモ
    リ及び選択されたメインメモリアドレスに記憶された上
    記データに対応するデータを記憶するキャッシュを有す
    るコンピュータシステムにおけるメモリ管理装置におい
    て、 ａ）上記キャッシュに接続され、データの複数のページ
    が記憶されている複数のキャッシュ位置を識別する上記
    メインメモリアドレスを使用して上記キャッシュをアク
    セスしてデータの複数のページを獲得するアクセス手段
    と、 ｂ）上記アクセス手段に接続され、上記ページが上記識
    別された位置に見当たらないキャッシュアクセスから成
    る複数のキャッシュミスをそれぞれ検出する検出手段
    と、 ｃ）上記検出手段に接続され、上記キャッシュミスに使
    用される上記メインメモリアドレスの予め選択されたサ
    ブレット（ここで、サブレットは１よりも大きく上記キ
    ャッシュミスの総数よりも小さい）を記憶する記憶手段
    と、 ｄ）上記記憶手段に接続され、上記記憶されたメインメ
    モリアドレスを選択された時間においてサンプリングす
    るサンプリング手段と、 ｅ）上記サンプリング手段に接続され、上記サンプリン
    グされたメインメモリアドレスの各々におけるデータを
    上記メインメモリアドレスの別のアドレスに移動する手
    段と、 から成ることを特徴とする装置。
  4. 【請求項４】上記記憶手段は、上記キャッシュミスに使
    用される上記メインメモリアドレスの各々を順次記憶す
    るミスラッチから成ることを特徴とする請求項３に記載
    の装置。
  5. 【請求項５】上記記憶手段は、上記キャッシュミスをカ
    ウントするカウンタと、キャッシュミスＮ個（ここで、
    Ｎは１よりも大きく上記キャッシュミスの総数よりも小
    さい整数である）につき１個を記憶する手段とから成る
    ことを特徴とする請求項３又は４に記載の装置。
  6. 【請求項６】コンピュータシステムを動作する方法にお
    いて、 ａ）複数の物理アドレスにより識別されるメインメモリ
    （ここで、メインメモリは上記プロセッサによりアクセ
    ス可能である）の複数の位置にデータを記憶し、 ｂ）複数の仮想アドレス（ここで、仮想アドレスの各々
    は上記メインメモリに記憶されたデータの複数のページ
    の１つに対応する）を上記物理アドレスに対応するアド
    レスに変換する変換テーブルを維持し、 ｃ）キャッシュ（ここで、キャッシュはキャッシュ位置
    に記憶されるデータを識別する複数のキャッシュタグを
    含むキャッシュ情報を記憶する）の、上記物理アドレス
    によりアクセス可能な複数のキャッシュ位置に上記デー
    タのページのサブセットを記憶し、 ｄ）上記キャッシュから上記データのページの中の選択
    されたページをフェッチするために、上記プロセッサ
    が、上記選択されたページの仮想アドレスを物理アドレ
    スに変換し、上記選択されたページの物理アドレスが上
    記キャッシュ情報に対応するかどうかを判定することに
    より上記物理アドレスを使用して上記キャッシュをアク
    セスし、 ｅ）上記選択されたページの上記物理アドレスが上記キ
    ャッシュ情報に対応しない事態（ここで、上記事態はそ
    れぞれキャッシュミスとして識別される）をそれぞれト
    ラッキングし、 ｆ）上記キャッシュミスの上記物理アドレスの予め選択
    されたサブセットを記憶し、 ｇ）上記記憶されたキャッシュミスの物理アドレスを周
    期的にサンプリングし、 ｈ）上記サンプリングされた物理アドレスが上記仮想ア
    ドレスの別のアドレスに対応するように上記変換テーブ
    ルを変更し、 ｉ）上記サンプリングされた物理アドレスに対応する上
    記ページを上記メインメモリの別の位置に移動する、 段階から成る方法。
JP5500873A 1991-06-17 1992-05-21 コンピュータシステムを動作する方法及びコンピュータシステムにおけるメモリ管理装置 Expired - Lifetime JPH07104816B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US71639791A 1991-06-17 1991-06-17
US716,397 1991-06-17
PCT/US1992/004281 WO1992022867A1 (en) 1991-06-17 1992-05-21 Improving computer performance by simulated cache associativity

Publications (2)

Publication Number Publication Date
JPH05509189A JPH05509189A (ja) 1993-12-16
JPH07104816B2 true JPH07104816B2 (ja) 1995-11-13

Family

ID=24877837

Family Applications (1)

Application Number Title Priority Date Filing Date
JP5500873A Expired - Lifetime JPH07104816B2 (ja) 1991-06-17 1992-05-21 コンピュータシステムを動作する方法及びコンピュータシステムにおけるメモリ管理装置

Country Status (12)

Country Link
US (1) US5442571A (ja)
EP (1) EP0543991B1 (ja)
JP (1) JPH07104816B2 (ja)
KR (1) KR960005443B1 (ja)
AU (1) AU658914B2 (ja)
CA (1) CA2088779C (ja)
DE (1) DE69229667T2 (ja)
IE (1) IE921691A1 (ja)
IL (1) IL102001A (ja)
MX (1) MX9202907A (ja)
TW (1) TW219986B (ja)
WO (1) WO1992022867A1 (ja)

Families Citing this family (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2688612A1 (fr) * 1992-03-13 1993-09-17 Inst Nat Rech Inf Automat Dispositif d'antememoire.
US5732409A (en) * 1994-03-21 1998-03-24 Legend Research Limited Caching disk controller implemented by hardwired logic
US6129458A (en) * 1994-03-23 2000-10-10 At&T Global Information Solutions Company Cache optimization method
US6223255B1 (en) 1995-02-03 2001-04-24 Lucent Technologies Microprocessor with an instruction level reconfigurable n-way cache
US5845106A (en) * 1996-01-26 1998-12-01 Advanced Micro Devices, Inc. Method for simulating cache operation
US5752261A (en) * 1996-11-07 1998-05-12 Ncr Corporation Method and apparatus for detecting thrashing in a cache memory
US6301641B1 (en) * 1997-02-27 2001-10-09 U.S. Philips Corporation Method for reducing the frequency of cache misses in a computer
KR100231707B1 (ko) * 1997-08-04 2000-01-15 정선종 통신 장비의 디엠에이 처리 방법 및 그 장치
US6209062B1 (en) * 1997-11-24 2001-03-27 Intel Corporation Method for holding cache pages that are not invalidated within normal time duration for a second access or that are likely to be accessed again soon
US6446170B1 (en) * 1999-01-19 2002-09-03 International Business Machines Corporation Efficient store machine in cache based microprocessor
US6408368B1 (en) 1999-06-15 2002-06-18 Sun Microsystems, Inc. Operating system page placement to maximize cache data reuse
US6366994B1 (en) * 1999-06-22 2002-04-02 Sun Microsystems, Inc. Cache aware memory allocation
JP2001109661A (ja) 1999-10-14 2001-04-20 Hitachi Ltd キャッシュメモリの割当方法及びオペレーティングシステム及びそのオペレーティングシステムを有するコンピュータシステム
US6523092B1 (en) * 2000-09-29 2003-02-18 Intel Corporation Cache line replacement policy enhancement to avoid memory page thrashing
US6947052B2 (en) * 2001-07-13 2005-09-20 Texas Instruments Incorporated Visual program memory hierarchy optimization
GB2381886B (en) * 2001-11-07 2004-06-23 Sun Microsystems Inc Computer system with virtual memory and paging mechanism
US7366871B2 (en) 2004-11-18 2008-04-29 Sun Microsystems, Inc. Apparatus and method for determining stack distance including spatial locality of running software for estimating cache miss rates based upon contents of a hash table
US7373480B2 (en) * 2004-11-18 2008-05-13 Sun Microsystems, Inc. Apparatus and method for determining stack distance of running software for estimating cache miss rates based upon contents of a hash table
JP2007272691A (ja) * 2006-03-31 2007-10-18 Fujitsu Ltd プロセッサ装置およびスラッシング回避方法
US8806461B2 (en) * 2007-06-21 2014-08-12 Microsoft Corporation Using memory usage to pinpoint sub-optimal code for gaming systems
US9619396B2 (en) * 2015-03-27 2017-04-11 Intel Corporation Two level memory full line writes
US10310811B2 (en) 2017-03-31 2019-06-04 Hewlett Packard Enterprise Development Lp Transitioning a buffer to be accessed exclusively by a driver layer for writing immediate data stream
CN111666230B (zh) * 2020-05-27 2023-08-01 江苏华创微系统有限公司 在组相联tlb中支持巨页的方法
US12271318B2 (en) * 2020-12-28 2025-04-08 Advanced Micro Devices, Inc. Method and apparatus for managing a cache directory

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5119290A (en) * 1987-10-02 1992-06-02 Sun Microsystems, Inc. Alias address support
US5210843A (en) * 1988-03-25 1993-05-11 Northern Telecom Limited Pseudo set-associative memory caching arrangement
JPH02273843A (ja) * 1989-04-14 1990-11-08 Nec Corp スワッピング装置
US5101485B1 (en) * 1989-06-29 1996-12-10 Frank L Perazzoli Jr Virtual memory page table paging apparatus and method

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
ＩＢＭＴｅｃｈｎｉｃａｌＤｉｓｃｌｏｓｕｒｅＢｕｌｌｅｔｉｎＶｏｌ．３２，Ｎｏ．８Ａ，Ｊａｎｕａｒｙ１９９０，Ｐ．３３４−３３７，ＸＰ８２８２９"ＰＡＧＥＡＬＬＯＣＡＴＩＯＮＣＯＮＴＲＯＬ"

Also Published As

Publication number Publication date
DE69229667D1 (de) 1999-09-02
EP0543991A1 (en) 1993-06-02
WO1992022867A1 (en) 1992-12-23
KR960005443B1 (ko) 1996-04-25
AU658914B2 (en) 1995-05-04
JPH05509189A (ja) 1993-12-16
IE921691A1 (en) 1992-12-30
US5442571A (en) 1995-08-15
EP0543991B1 (en) 1999-07-28
DE69229667T2 (de) 2000-02-10
CA2088779A1 (en) 1992-12-18
TW219986B (ja) 1994-02-01
IL102001A (en) 1996-01-31
AU2247492A (en) 1993-01-12
IL102001A0 (en) 1992-12-30
MX9202907A (es) 1993-03-01
CA2088779C (en) 1998-09-01

Similar Documents

Publication Publication Date Title
JPH07104816B2 (ja) コンピュータシステムを動作する方法及びコンピュータシステムにおけるメモリ管理装置
US5694568A (en) Prefetch system applicable to complex memory access schemes
JP3618385B2 (ja) データをバッファリングする方法およびそのシステム
US5895501A (en) Virtual memory system for vector based computer systems
US5751994A (en) System and method for enhancing computer operation by prefetching data elements on a common bus without delaying bus access by multiple bus masters
US6161166A (en) Instruction cache for multithreaded processor
US6247107B1 (en) Chipset configured to perform data-directed prefetching
US5594886A (en) Pseudo-LRU cache memory replacement method and apparatus utilizing nodes
US7089370B2 (en) Apparatus and method for pre-fetching page data using segment table data
US5282274A (en) Translation of multiple virtual pages upon a TLB miss
JP2618175B2 (ja) キャッシュ・アクセスのための仮想アドレス変換予測の履歴テーブル
EP0215544B1 (en) Virtual memory address fetching
US5555395A (en) System for memory table cache reloads in a reduced number of cycles using a memory controller to set status bits in the main memory table
JPH05210585A (ja) キャッシュ管理システム
KR20010101694A (ko) 가상 메모리 시스템에서의 메모리 접근 개선 기술
JP3449487B2 (ja) 変換索引緩衝機構
JP2001184263A (ja) 旧キャッシュラインを無効化および除去する装置
US8621152B1 (en) Transparent level 2 cache that uses independent tag and valid random access memory arrays for cache access
US6571316B1 (en) Cache memory array for multiple address spaces
JP2001195303A (ja) 機能が並列に分散された変換索引バッファ
US5333291A (en) Stride enhancer for high speed memory accesses with line fetching mode and normal mode employing boundary crossing determination
US5452418A (en) Method of using stream buffer to perform operation under normal operation mode and selectively switching to test mode to check data integrity during system operation
US20070266199A1 (en) Virtual Address Cache and Method for Sharing Data Stored in a Virtual Address Cache
US7949833B1 (en) Transparent level 2 cache controller
US5835945A (en) Memory system with write buffer, prefetch and internal caches