JPH0628257A - キャッシュメモリ内のデータ交換方法 - Google Patents

キャッシュメモリ内のデータ交換方法

Info

Publication number
JPH0628257A
JPH0628257A JP4045437A JP4543792A JPH0628257A JP H0628257 A JPH0628257 A JP H0628257A JP 4045437 A JP4045437 A JP 4045437A JP 4543792 A JP4543792 A JP 4543792A JP H0628257 A JPH0628257 A JP H0628257A
Authority
JP
Japan
Prior art keywords
data
prefetch
request
section
items
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.)
Granted
Application number
JP4045437A
Other languages
English (en)
Other versions
JP2558033B2 (ja
Inventor
Feng-Hsien W Shih
フェン‐フシエン、ワーレン、シー
Jr James F Macon
ジェームズ、フランクリン、メイコン、ジュニア
Shauchi Ong
シャウチ、オング
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.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
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 International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH0628257A publication Critical patent/JPH0628257A/ja
Application granted granted Critical
Publication of JP2558033B2 publication Critical patent/JP2558033B2/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/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/123—Replacement control using replacement algorithms with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
    • 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/0862—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches with prefetch
    • 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/0866—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches for peripheral storage systems, e.g. disk 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/12—Replacement control
    • G06F12/121—Replacement control using replacement algorithms
    • G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning

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

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、一般的には、要求デー
タ及び先取りデータの両方が格納できるキャッシュメモ
リの動作を管理するための改良された方法、より具体的
には、メモリ内のスペースを要求データと先取りデータ
との間で使用の頻度に基づいて割り当てるための改良さ
れた方法に関する。
【０００２】
【従来の技術】多くのデータ処理システムにおいては、
通常”キャッシュ”と呼ばれる高速メモリが中央処理ユ
ニットの作業メモリと主メモリとの間に提供される。こ
のキャッシュは前に主メモリからキャッシュに移された
データのサブセットへの比較的高速度のアクセスを可能
にし、こうして、データ処理システムの全体としての速
度を向上させる。通常、主メモリからキャッシュへのデ
ータの転送はデータのページあるいはブロックにて行な
われ、要求データページ及び先取りデータページの両方
を含む。要求データは中央処理ユニットからの特定の要
求の結果としてキャッシュに転送されたデータである。
要求データをキャッシュに転送するとき、追加のデータ
が直に要求される可能性がある場合、同時にこの追加の
要求されないデータ（つまり、先取りデータ）も転送す
ることが有利である。
【０００３】キャッシュが満たされている場合、新たな
データを書込む場合そのキャッシュからデータを除去す
ることが必要である。通常、データキャッシュ管理シス
テムは、キャッシュから除去されるべきデータを選択す
るための基準としてデータの使用頻度を使用する。最も
前に使用された（least recently used 、ＬＲＵ）と言
う考えは、これが簡単で効率的であるために交換のため
の通常の基準とされる。
【０００４】先行技術においては、キャッシュ内のデー
タの交換において、要求データ及び先取りデータは個々
のタイプの入りデータのサイズと無関係に等しく扱われ
る。このような条件下においては、（キャッシュ内の要
求データを発見すると言う視点から）総キャッシュメモ
リ容量の大き過ぎる部分が先取りデータを格納するため
に割り当てられることがあり、特に、個々の主メモリの
要求データへのアクセスとの関連で多量のデータが先取
りされる場合にはこれが顕著になる。
【０００５】『ディスクキャッシュ動作における先取り
データの量の自動的調節（Automatic Adjustment of th
e Quantity of Prefetch Data in a Disk Cache Operat
ion)』と言う名称の合衆国特許第４，４８９，３７８号
は、個々のディスクキャッシュ動作においる先取りデー
タブロックの数を決定するための動的機構について開示
する。『逐次的にアクセスされたブロックに対する第２
のディレクトリを持つキャッシュのための先取りシステ
ム（Prefetching System for a Cache Havinga Second
Directory for Sequentially Accessed Blocks ）』と
言う名称の合衆国特許第４，８０７，１１０号は２レベ
ルキャッシュディレクトリを使用して先取りのためのデ
ータブロックを選択するための方法について開示する。
これら特許の両方ともキャッシュ動作における先取りに
ついて考えるが、但し、交換のために従来の最も先に使
用された（ＬＲＵ）と言う原理に基づく案を使用する。
【０００６】
【発明が解決しようとする課題】本発明の一つの目的
は、要求データ及び先取りデータに対して割り当てられ
る記憶領域のサイズをこうして割り当てられた領域が動
作の際に領域‐性能（つまり、キャッシュヒット密度）
に基づいてバランスされるように自動的に調節するキャ
ッシュ管理データシステムを提供することにある。この
システムは、使用される先取りアルゴリズムとは無関係
に動作し、設計が単純で簡明である。
【０００７】要約すると、本発明は、データキャッシュ
メモリが論理的に要求及び先取りの二つの分離したセク
ションに論理的に分割される最も前に使用されたと言う
概念に基づくキャッシュ交換システムを考える。このキ
ャッシュを維持するためにキャッシュディレクトリテー
ブル及び最も前に使用されたページに対するテーブルが
使用される。新たな要求データページがキャッシュに加
えられると、最も最近使用された（most recently use
d、ＭＲＵ）ページに対するポインタが更新され、この
新たなページを指す。先取りページがキャッシュに加え
られると、要求セクションの最も前に使用されたページ
に対するポインタがこの新たなページを指す逆ポインタ
にて更新される。要求あるいは先取りセクション内のペ
ージに対するキャッシュヒットはそのページを最も前に
使用されたページのテーブルの先頭に移動させる。キャ
ッシュ内でフリーのページが必要となった場合、これは
メモリの要求あるいは先取りセクションから要求ヒット
密度と先取りヒット密度の比較に基づいてこれら二つの
ヒット密度のバランスが維持されるような方法にて選択
される。要求ヒット密度は最も前に使用されたページに
対するテーブルの要求セクション内の項目の数に対する
要求ヒット密度の比である。同様に、先取りヒット密度
は、最も前に使用されたページに対するテーブルの先取
りセクション内の項目の数に対する先取り確率の比であ
る。 本発明の前述の及びその他の目的、特徴並びに長
所は、本発明の一つの好ましい実施例の以下の詳細な説
明を図面を参照しながら読むことによって一層理解でき
るものである。
【０００８】
【実施例】図１において、キャッシュディレクトリテー
ブルは先行技術によるキャッシュ管理システム内のディ
レトクリテーブルに一般的な項目を含む。これは、ある
キャッシュ内のセルがフリーであるか使用されているか
を示す単一ビット項目１０、ホームインジケータ１２及
びファイルブロックアドレス１４を含む。順ポインタ１
６及び逆ポインタ１８は次のリスト項目に対するアドレ
スを提供する。キャッシュアドレス２０並びに２２の所
に示されるような他の情報も提供される。第一のフリー
ページポインタ２６は次にそれに書き込まれるべきキャ
ッシュ内のフリーのページあるいはセルのキャッシュア
ドレスを提供し、フリーページカウンタ２４はキャッシ
ュ内のフリーページのラニングトータルを保つ。
【０００９】図２は最も前に使用された（Least Recent
ly Used 、ＬＲＵ）ページに対するテーブルの編成を示
す。順ポインタ１６、逆ポインタ１８並びにディレクト
リテーブルポインタ２８はプッシュダウンスタック内に
保持され、これらは論理的に要求セクション３０と先取
りセクション３２に分離される。テーブル中、キャッシ
ュ内の最も最近使用されたページに対するこれらポイン
タ１６、１８及び２８はテーブルの最も上に入れられ、
最も最近使用されたページに対するポインタ３４によっ
て示される。主メモリから新たに移された要求ページに
対するこれらポインタは最も最近使用されたものとして
テーブルの最も上に入れられる。新しく先取りされたペ
ージに対するこれらポインタはテーブルの先取りセクシ
ョンの最も上に入れられる。最も前に使用されたページ
に対するポインタ３６はテーブルの要求セクション内の
最後の項目を指し、もう一つの最も前に使用されたペー
ジに対するポインタ３８はテーブルの先取りセクション
内の最後の項目を指す。本発明の教示に従えば、要求セ
クション３０のサイズ及び先取りセクション３２のサイ
ズは先取りセクションのヒット密度に対する要求セクシ
ョンのヒット密度の比に依存して変化することが理解で
きる。
【００１０】キャッシュの要求及び先取りセクションの
両方に対するヒット密度を計算するためには、キャッシ
ュヒストリウインドウが計算プロセスにおけるヒストリ
データのサイズを制限するために定義される。例えば、
これは３２個の入力／出力要求サイズに制限される。以
下のチャート１はここで使用されるキャッシュパラメー
タを定義し、チャート２はヒットヒストリ計算の項を定
義する。 チャート１：キャッシングパラメータの定義 ・キャッシュヒストリウインドウ、ＣＨＷ（ｉ） 全体としてのキャシングヒストリはＣＨＷに分割され、
個々のウインドウは同数（例えば、３２個）のファイル
Ｉ／Ｏ要求を持つ。 ・個々のＣＨＷ（ｉ）内において、 Ｎd ＝要求ページの総数 Ｎp （ｉ）＝先取りページの総数 Ｎdh（ｉ）＝要求ヒットの総数 Ｎph（ｉ）＝先取りヒットの総数 ・ヒストリワーキングセット キャッシングヒストリ計算のために選択されたウインド
ウの最も最近のセット（例えば、４あるいは５個） ・Ｎd ＝現ファイルＩ／Ｏ内の要求ページの数 ・Ｎp ＝現Ｉ／Ｏ内の先取りページの数 ・Ｌd ＝最も前に使用された（ＬＲＵ）ページに対する
テーブルの要求セクション内の項目の数 ・Ｌp ＝ＬＲＵテーブルの先取りセクション内の項目の
数 ・Ｎdt、Ｎpt、Ｎdht 、Ｎpht ＝累積パラメータカウン
ト ・ＣＷＣ＝完全なウインドのウカウント ・Ｉカウント＝現ウインドウ内のファイルＩ／Ｏカウン
ト チャート２：キャッシングヒストリ密度計算 ヒストリワーキングセット＝｛ＣＨＷ（ｉ）、ＣＨＷ
（ｉ＋１）、ＣＨＷ（ｉ＋２）、ＣＨＷ（ｉ＋３）、Ｃ
ＨＷ（ｉ＋４）｝について考えると、
【００１１】
【数１】
【００１２】
【数２】 ・要求ヒット密度（ＤＨＤ）＝要求ヒット確率／Ｌd ・先取りヒット密度（ＰＨＤ）＝先取りヒット確率／Ｌ
p 図３に示されるように、全体としてのキャッシュ管理動
作は、ブロック４０から開始されるが、ここでは、個々
の入力／出力要求がこれがキャッシュバイパス指令を持
つか否か調べられる。そのキャッシュがバイパスされな
いときは、判定ブロック４２において、キャッシュ要求
のタイプ、つまり、読出し要求であるか書込み要求であ
るかが決定される。ここで、全てのキャッシュへの書込
み要求は要求読出しリクエストであると扱われることに
注意する。キャッシュからＩ／Ｏ要求が読出された場
合、ブロック４４において、これが先取り読出しである
か否かの決定が行なわれる。そうでない場合、あるいは
このＩ／Ｏが書込みコマンド（ブロック４２）である場
合は、このＩ／Ｏファイル内の先取りページ（ＮP ）の
数はゼロ（０）であり、動作は、書込み要求であるとき
はキャッシュ管理ブロック４８に進み、要求の読出しの
場合は、先取り動作（ブロック５０）へと進む。先取り
の読出しの場合は、先取りアルゴリズムがブロック５２
において読出し要求内の先取りページの数を決定し、こ
れらページがブロック５０において先取りされる。残り
の動作は以下の通りである。つまり、図４及び５との関
連で後に説明されるキャッシュ管理ブロック４８、図６
との関連で後に説明されるヒット密度計算ブロック５
６、及び図７との関連で後に説明されるウインドウカウ
ント更新ブロック５８がある。
【００１３】図４に示されるように、キャッシュの管理
において、先取りされた個々のページに対して（図３、
ブロック５０）、キャッシュディレクトリテーブル内に
おいてそのページがキャッシュ内に存在するか否かを決
定するための探索が行なわれる（ブロック６０）。その
ページがキャッシュに存在しないときは、後に図５との
関連でより詳細に説明されるようにそのページが加えら
れる。その要求ページがキャッシュ内に存在するときは
（ブロック６２）、ブロック６４においてそれが要求さ
れたＩ／Ｏページであるか否かの決定が行なわれる。要
求されたページ以外のページが先取りされた場合は、こ
の図４に示される動作の残りのステップからの退出が起
こる。キャッシュのページが要求されたページであると
きは、ブロック６６において、要求されたページが要求
セクション３０内にあるか、あるいは先取りセクション
３２内にあるかの決定が行なわれる。ウインドウセット
（Ｎdhｉ）に対する要求ヒットの総数あるいはウインド
ウセット（Ｎphｉ）に対する先取りヒットの総数がこれ
に従って更新され（それぞれブロック６５及び６７）、
最も最近使用されたページに対するポインタがこの要求
されたページを指すように更新される（ブロック６
８）。
【００１４】図５に示されるように、キャッシュに新た
なページを加える場合、ブロック６９において、キャッ
シュ内に加えられるページを受け入れるためのフリーの
ページあるいはセルが存在するか否かを決定するための
初期チェックが行なわれる。使用できるフリーページが
存在するときは、ブロック７０において、加えられるべ
きページのタイプ、つまり、要求ページであるか先取り
ページであるかの決定が行なわれる。要求であるとき
は、ページがブロック７２においてキャッシュの要求セ
クションの最も上の所に挿入され、要求セクションの最
も最近使用されたページに対するポインタがこのページ
を指すように更新され、ブロック７４において要求セク
ションの項目カウントが更新される。同様に、先取りペ
ージが加えられる場合は、ブロック７６においてキャッ
シュの先取りセクションの最も上の所に置かれ、先取り
セクションの項目カウントが更新される。
【００１５】ブロック６９において、キャッシュ内にフ
リーの使用できるページが存在しないと決定された場合
は、一つのページが最初にキャッシュの要求あるいは先
取りセクションから削除される。ブロック７８におい
て、要求ヒット密度（demandhit density 、ＤＨＤ）が
先取りヒット密度（prefetch hit density、ＰＨＤ）以
上であるか否か（ＤＨＤ≧ＰＨＤであるか否か）の決定
が行なわれ、ＤＨＤがＰＨＤより小さい場合（ＤＨＤ＜
ＰＨＤの場合）、ＲＤに１に等しい値が割り当てられ
る。要求ヒット密度が先取りヒット密度以上である場合
は、キャッシュの先取りセクション内の最も前に使用さ
れたページがブロック８０において削除され、先取りセ
クションカウンタ内の項目の数が１だけ減分される。同
様に、要求ヒット密度が先取りヒット密度よりも小さい
ときは、キャッシュの要求セクション内の最も前に使用
されたページがブロック８２において削除され、要求セ
クションの項目カウンタ内の項目の数が１だけ減分され
る。
【００１６】図６に示されるように、要求及び先取りヒ
ット密度の計算において、この例は５つの最も最近のウ
インドウのワーキングヒストリセット、つまり、Ｎ
d （５）及びＮp （５）を想定する。動作はブロック８
１から開始されるが、ここで、ワーキングヒストリセッ
トに対する要求ページの総数Ｎd （５）及び先取りペー
ジの総数Ｎp （５）が現Ｉ／Ｏ要求のＮp のページの数
Ｎd にて更新される。要求セクションＬd 内のページの
数がゼロ（０）の場合は、ブロック８４においてＲＤが
ゼロにセットされる。同様に、先取りセクション内のペ
ージの数がゼロ（０）の場合は、ＲＤがブロック８６に
おいて１にセットされる。キャッシュ内に要求及び先取
りページが存在するときは、ブロック８６において、要
求ヒット率及び先取りヒット率が計算される。
【００１７】要求ヒット率（ＤＨＤ）は要求ヒット確率
のキャッシュの要求セクション内の項目の数に対する比
である。要求ヒット確率はワーキングセットヒストリに
対する要求ヒットの総数のこのヒストリに対する要求ペ
ージ要求の数に対する比である。つまり、 （ＤＨＤ）＝要求ヒット確率／Ｌd 先取りヒット密度（ＰＨＤ）は先取りヒット確率のキャ
ッシュの先取りセクション内の項目の数に対する比であ
る。先取りヒット確率はワーキングヒットヒストリに対
する先取りヒットの総数のこのヒストリに対する先取り
ページ要求の数に対する比である。つまり、 （ＰＤＨ）＝先取りヒット確率／Ｌp ブロック９０において、要求ヒット密度ＤＨＤと先取り
ヒット密度の比較が行なわれ；ＤＨＤがＰＨＤに等しい
かこれよりも大きなときは、ＲＤにゼロ（０）の値が割
り当てられる。ＤＨＤがＰＨＤよりも小さいときは、Ｒ
Ｄに１の値が割り当てられる。
【００１８】図７には、ウインドウ更新動作が示され
る。この例は、ウインドウ当り３２Ｉ／Ｏ要求、及びロ
ーリングヒストリセット当り５個のウインドを想定す
る。
【００１９】動作は、ブロック９２において入力要求”
Ｉ”に応答して個々の要求に応答して要求カウント”
Ｉ”を１だけ増分することから開始する。このカウント
がブロック９４においてウインドウ当りの要求数（例え
ば、この例では３２）に対してテストされる。３２のカ
ウントは一つの完全なウインドウを示し、このカウント
に達すると、ブロック９６において完結ウインドウカウ
ントが１だけ増分される。ブロック１００において、こ
の完結ウインドウカウントが割り当てられたワーキング
セットヒストリ数に対してテストされる。残りの論理
は、セットのウインドウから構成されるローリングヒス
トリに対してヒット密度データパラメータをこのセット
内の最も古い完結ウインドウに対するデータ（ここでは
５個）を削除し、一つのウインドウが完結する度に最後
のウインドウデータを加えることによって最新に保つ働
きをする。ブロック１０１において、要求ページのカウ
ント（Ｎd ）、先取りページのカウント（Ｎp ）、要求
ヒット（Ｎdh）及び先取りヒット（Ｎph）が個々のウイ
ンドウに対して決定される。一つのウインドウが完結す
ると（つまり、ブロック１００においてＣＷＣ＝５）、
このセット内の最も古いケースヒストリウインドウが、
結果として、ブロック１０６において、値ＫをＫ＋１に
増分することによって削除される。ブロック１０５によ
って完結ウインドウカウントが１だけ減分される。要求
及び先取りページ要求に対する累積パラメータカウント
並びに要求及び先取りヒットがブロック１０２において
このウインドウの更新されたセットに対して決定され
る。ブロック１０４において、完結ウインドウカウント
（ブロック１０１）のヒット密度データパラメータがゼ
ロにリセットされる。
【００２０】こうして、本発明の様々な目的が達成され
たことが分かる。本発明は、割り当てられたキャッシュ
の記憶領域のサイズを動作の際に面積性能（つまり、キ
ャッシュヒット密度）基づいて要求及び先取りデータに
対して自動的に調節するキャッシュ管理データシステム
を提供するが；このシステムは使用される先取りアルゴ
リズムとは独立して動作する。またこのシステムは設計
が単純で簡明である。
【００２１】本発明が一つの好ましい実施例との関連で
説明されたが、当業者においては、本発明が本発明の請
求項の精神及び範囲内で修正して実現できることも認識
できるものである。
【図面の簡単な説明】
【図１】本発明の教示に従うキャッシュ管理システムに
おける典型的な表項目の例を説明するキャッシュディレ
クトリ表を表わす図である。
【図２】本発明の教示に従うキャッシュ管理システムに
対する典型的な表編成を説明するリーストリセントリユ
ーズド（ＬＲＵ）表を示す図である。
【図３】ヒット密度に基づくキャッシュ交換動作の全体
としての設計のフローチャートである。
【図４】キャッシュ管理動作を示すフローチャートであ
る。
【図５】新たなページの追加動作を示すフローチャート
である。
【図６】ヒット密度計算のフローチャートである。
【図７】ウインドウ計算のフローチャートである。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジェームズ、フランクリン、メイコン、ジ ュニア アメリカ合衆国フロリダ州、ボイントン、 ビーチ、ドリット、アベニュ、3576 (72)発明者 シャウチ、オング アメリカ合衆国ニューヨーク州、プレザン トビル、ヘリテージ、ドライブ、23

Claims (9)

    【特許請求の範囲】
  1. 【請求項１】要求データ及び先取りデータが格納されて
    いるデータキャッシュメモリ内のデータを交換するため
    の方法において、この方法が：前記キャッシュメモリを
    先取りセクションと要求セクションに分割するステッ
    プ；前記要求セクション内に要求データを格納するステ
    ップ；前記先取りセクション内に先取りデータを格納す
    るステップ；前記先取りセクションに対する先取り確率
    を先取り要求の数に対する前記先取りセクション内のヒ
    ットの数の比に基づいて決定するステップ；前記要求セ
    クションに対する要求ヒット確率を要求リクエストの数
    に対する前記要求セクション内のヒットの数の比に基づ
    いて決定するステップ；前記先取りセクションに対する
    先取りヒット密度を前記先取りセクション内のデータ項
    目の数に対する先取りヒット確率の比に基づいて決定す
    るステップ；前記要求セクションに対する要求ヒット密
    度を前記要求セクション内のデータ項目の数に対する先
    取りヒット密度の比に基づいて決定するステップ；前記
    要求セクションに対する要求ヒット密度を前記要求セク
    ション内のデータ項目の数に対する要求ヒット密度の比
    に基づいて決定するステップ；及び前記要求セクション
    内の項目あるいは前記先取りセクション内の項目を先取
    りヒット密度と要求ヒット密度の比較に基づいて交換す
    るステップを含むことを特徴とする方法。
  2. 【請求項２】前記先取りヒット密度と前記要求ヒット密
    度が事前に決定された数の入力／出力要求に基づいて決
    定されることを特徴とする請求項１のデータキャッシュ
    メモリ内のデータを交換するための方法。
  3. 【請求項３】前記先取りセクションからの項目が前記要
    求ヒット密度が先取り密度よりも大きな場合に交換され
    ることを特徴とする請求項１のデータキャッシュメモリ
    ー内のデータを交換するための方法。
  4. 【請求項４】前記先取りセクションからの項目が前記要
    求ヒット密度が先取り密度に等しい場合に交換されるこ
    とを特徴とする請求項１のデータキャッシュメモリ内の
    データを交換するための方法。
  5. 【請求項５】前記先取りセクションからの項目が前記要
    求ヒット密度が先取り密度に等しい場合に交換されるこ
    とを特徴とする請求項１のデータキャッシュメモリ内の
    データを交換するための方法。
  6. 【請求項６】要求セクション内の最も前に使用されたデ
    ータを決定するステップ、先取りセクション内の最も前
    に使用されたデータを決定するステップ、及び前記要求
    セクションあるいは前記先取りセクション内の最も前に
    使用されたデータを交換するステップがさらに含まれる
    ことを特徴とする請求項１のデータキャッシュメモリ内
    のデータを交換するための方法。
  7. 【請求項７】要求データ及び先取りデータが格納される
    データキャッシュメモリ内のデータを交換するための方
    法において、この方法が組合わせにて；キャッシュメモ
    リを先取りセクション及び要求セクションに分割するス
    テップ；前記要求セクション内に要求データを格納する
    ステップ；前記先取りセクション内にデータを格納する
    ステップ；及び前記先取りデータセクションの項目の数
    に対する前記要求データセクションの項目の数を前記要
    求セクションあるいは前記先取りセクション内のデータ
    を前記要求セクション内のデータ要求ヒットの数、前記
    先取りセクション内のデータ要求ヒットの数及び前記先
    取りセクション内の項目の数の関数として交換すること
    によって調節するステップを含むことを特徴とする方
    法。
  8. 【請求項８】要求データ及び先取りデータが格納される
    データキャッシュメモリ内のデータを交換するための方
    法において、この方法が組合わせにて；前記キャッシュ
    メモリを先取りセクション及び要求セクションに分割す
    るステップ；前記要求セクション内に要求データを格納
    するステップ；前記先取りセクション内に先取りデータ
    を格納するステップ；及び前記先取りデータセクション
    の項目に対する前記要求データセクションの項目の数を
    前記要求セクションあるいは前記先取りセクション内の
    データを前記要求セクション内のデータ要求ヒットの数
    及び前記先取りセクション内のデータ要求ヒットの数の
    関数として交換することによって調節するステップを含
    むことを特徴とする方法。
  9. 【請求項９】前記要求セクション内の最も前に使用され
    たデータを決定するステップ、前記先取りセクション内
    の最も前に使用されたデータを決定するステップ、及び
    前記要求セクションあるいは前記先取りセクション内の
    最も前に使用されたデータを交換するステップがさらに
    含まれることを特徴とする請求項８のデータキャッシュ
    メモリ内のデータを交換するための方法。
JP4045437A 1991-04-19 1992-03-03 データキャッシュメモリ内のデータを置換する方法 Expired - Lifetime JP2558033B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US688732 1991-04-19
US07/688,732 US5293609A (en) 1991-04-19 1991-04-19 Hit-density-based replacement for data cache with prefetching

Publications (2)

Publication Number Publication Date
JPH0628257A true JPH0628257A (ja) 1994-02-04
JP2558033B2 JP2558033B2 (ja) 1996-11-27

Family

ID=24765540

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4045437A Expired - Lifetime JP2558033B2 (ja) 1991-04-19 1992-03-03 データキャッシュメモリ内のデータを置換する方法

Country Status (3)

Country Link
US (1) US5293609A (ja)
EP (1) EP0509231A1 (ja)
JP (1) JP2558033B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2019516188A (ja) * 2016-04-27 2019-06-13 アドバンスト・マイクロ・ディバイシズ・インコーポレイテッドＡｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓ Ｉｎｃｏｒｐｏｒａｔｅｄ キャッシュテスト領域に基づくプリフェッチのためのキャッシュエージングポリシーの選択

Families Citing this family (54)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH06180669A (ja) * 1992-12-14 1994-06-28 Nec Niigata Ltd キャッシュシステム
FR2699703B1 (fr) * 1992-12-22 1995-01-13 Bull Sa Procédé de gestion d'une mémoire tampon, support d'enregistrement et système informatique l'incorporant.
JP2784440B2 (ja) * 1993-04-14 1998-08-06 インターナショナル・ビジネス・マシーンズ・コーポレイション データ・ページの転送制御方法
GB2286267A (en) * 1994-02-03 1995-08-09 Ibm Energy-saving cache control system
JP3586887B2 (ja) * 1994-06-10 2004-11-10 松下電器産業株式会社 情報記録再生装置およびデータキャッシュ方法
US5604889A (en) * 1994-06-15 1997-02-18 Texas Instruments Incorporated Memory management system for checkpointed logic simulator with increased locality of data
GB2292822A (en) * 1994-08-31 1996-03-06 Hewlett Packard Co Partitioned cache memory
JPH08314794A (ja) * 1995-02-28 1996-11-29 Matsushita Electric Ind Co Ltd 安定記憶装置へのアクセス待ち時間を短縮するための方法およびシステム
US5701426A (en) * 1995-03-31 1997-12-23 Bull Information Systems Inc. Data processing system and method using cache miss address prediction and forced LRU status in a cache memory to improve cache hit ratio
US5696932A (en) * 1995-05-16 1997-12-09 International Business Machines Corporation Method and system for estimating minumun requirements on a cache in a computer based storage system
US5761464A (en) * 1995-05-22 1998-06-02 Emc Corporation Prefetching variable length data
US5787472A (en) * 1995-07-31 1998-07-28 Ibm Corporation Disk caching system for selectively providing interval caching or segment caching of vided data
US5680640A (en) * 1995-09-01 1997-10-21 Emc Corporation System for migrating data by selecting a first or second transfer means based on the status of a data element map initialized to a predetermined state
US5893920A (en) * 1996-09-30 1999-04-13 International Business Machines Corporation System and method for cache management in mobile user file systems
US6065100A (en) * 1996-11-12 2000-05-16 Micro-Design International Caching apparatus and method for enhancing retrieval of data from an optical storage device
US5781922A (en) * 1996-11-19 1998-07-14 International Business Machines Corporation Page boundary caches
DE69724099T2 (de) * 1997-05-22 2004-06-17 Bull S.A. Speicherstruktur nach Art eines Pufferspeichers
US6138213A (en) 1997-06-27 2000-10-24 Advanced Micro Devices, Inc. Cache including a prefetch way for storing prefetch cache lines and configured to move a prefetched cache line to a non-prefetch way upon access to the prefetched cache line
US6266742B1 (en) * 1997-10-27 2001-07-24 International Business Machines Corporation Algorithm for cache replacement
US6134643A (en) * 1997-11-26 2000-10-17 Intel Corporation Method and apparatus for cache line prediction and prefetching using a prefetch controller and buffer and access history
WO1999034356A2 (en) * 1997-12-30 1999-07-08 Genesis One Technologies, Inc. Disk cache enhancer with dynamically sized read request based upon current cache hit rate
US6542966B1 (en) * 1998-07-16 2003-04-01 Intel Corporation Method and apparatus for managing temporal and non-temporal data in a single cache structure
US6327644B1 (en) * 1998-08-18 2001-12-04 International Business Machines Corporation Method and system for managing data in cache
US6338115B1 (en) 1999-02-16 2002-01-08 International Business Machines Corporation Advanced read cache management
GB2348024B (en) * 1999-03-16 2003-06-25 Ibm Cache memory systems
US6314494B1 (en) * 1999-04-15 2001-11-06 Agilent Technologies, Inc. Dynamically size configurable data buffer for data cache and prefetch cache memory
US6260115B1 (en) * 1999-05-13 2001-07-10 Storage Technology Corporation Sequential detection and prestaging methods for a disk storage subsystem
US6754779B1 (en) * 1999-08-23 2004-06-22 Advanced Micro Devices SDRAM read prefetch from multiple master devices
US6341331B1 (en) * 1999-10-01 2002-01-22 International Business Machines Corporation Method and system for managing a raid storage system with cache
WO2001050275A1 (en) * 2000-01-05 2001-07-12 Sun Microsystems, Inc. A method for employing a page prefetch cache for database applications
US6848028B1 (en) * 2000-01-05 2005-01-25 Sun Microsystems, Inc. Microprocessor having a page prefetch cache for database applications
US6829680B1 (en) * 2000-01-05 2004-12-07 Sun Microsystems, Inc. Method for employing a page prefetch cache for database applications
US6671766B1 (en) 2000-01-07 2003-12-30 Storage Technology Corporation Method and system for implementing memory efficient track aging
US6574713B1 (en) * 2000-10-10 2003-06-03 Sun Microsystems, Inc. Heuristic for identifying loads guaranteed to hit in processor cache
US7039766B1 (en) * 2000-10-12 2006-05-02 International Business Machines Corporation Prescheduling sequential data prefetches in a preexisting LRU cache
US6721850B2 (en) 2001-02-27 2004-04-13 Lucent Technologies Inc. Method of cache replacement for streaming media
US6662272B2 (en) * 2001-09-29 2003-12-09 Hewlett-Packard Development Company, L.P. Dynamic cache partitioning
US6848026B2 (en) 2001-11-09 2005-01-25 International Business Machines Corporation Caching memory contents into cache partitions based on memory locations
US6829679B2 (en) * 2001-11-09 2004-12-07 International Business Machines Corporation Different caching treatment of memory contents based on memory region
US7359890B1 (en) * 2002-05-08 2008-04-15 Oracle International Corporation System load based adaptive prefetch
US7107400B2 (en) * 2003-03-31 2006-09-12 International Business Machines Corporation System, apparatus, and process for evaluating projected cache sizes
US7213107B2 (en) * 2003-12-31 2007-05-01 Intel Corporation Dedicated cache memory
US7529891B2 (en) * 2005-09-19 2009-05-05 Microsoft Corporation Balanced prefetching exploiting structured data
US8356151B2 (en) * 2008-02-01 2013-01-15 International Business Machines Corporation Reporting of partially performed memory move
US8327101B2 (en) * 2008-02-01 2012-12-04 International Business Machines Corporation Cache management during asynchronous memory move operations
US8275963B2 (en) * 2008-02-01 2012-09-25 International Business Machines Corporation Asynchronous memory move across physical nodes with dual-sided communication
US8245004B2 (en) * 2008-02-01 2012-08-14 International Business Machines Corporation Mechanisms for communicating with an asynchronous memory mover to perform AMM operations
JP5730126B2 (ja) * 2011-05-18 2015-06-03 キヤノン株式会社 データ供給装置、キャッシュ装置、データ供給方法、キャッシュ方法およびプログラム
US20130205089A1 (en) * 2012-02-08 2013-08-08 Mediatek Singapore Pte. Ltd. Cache Device and Methods Thereof
US9274955B2 (en) * 2012-08-17 2016-03-01 Futurewei Technologies, Inc. Reduced scalable cache directory
US9208094B2 (en) * 2013-08-06 2015-12-08 GlobalFoudries, Inc. Managing and sharing storage cache resources in a cluster environment
US9569364B1 (en) 2016-02-08 2017-02-14 International Business Machines Corporation Multiple history based micro partition prefetch optimization
CN107305531B (zh) * 2016-04-20 2020-10-16 阿里巴巴（中国）有限公司 缓存容量限值确定方法和装置以及计算设备
US9928176B2 (en) * 2016-07-20 2018-03-27 Advanced Micro Devices, Inc. Selecting cache transfer policy for prefetched data based on cache test regions

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4489378A (en) * 1981-06-05 1984-12-18 International Business Machines Corporation Automatic adjustment of the quantity of prefetch data in a disk cache operation
US4466059A (en) * 1981-10-15 1984-08-14 International Business Machines Corporation Method and apparatus for limiting data occupancy in a cache
US4807110A (en) * 1984-04-06 1989-02-21 International Business Machines Corporation Prefetching system for a cache having a second directory for sequentially accessed blocks
US4928239A (en) * 1986-06-27 1990-05-22 Hewlett-Packard Company Cache memory with variable fetch and replacement schemes
EP0391871A3 (en) * 1989-04-03 1992-05-27 International Business Machines Corporation Method for managing a prioritized cache
US5146578A (en) * 1989-05-01 1992-09-08 Zenith Data Systems Corporation Method of varying the amount of data prefetched to a cache memory in dependence on the history of data requests
US5150472A (en) * 1989-10-20 1992-09-22 International Business Machines Corp. Cache management method and apparatus for shared, sequentially-accessed, data

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2019516188A (ja) * 2016-04-27 2019-06-13 アドバンスト・マイクロ・ディバイシズ・インコーポレイテッドＡｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓ Ｉｎｃｏｒｐｏｒａｔｅｄ キャッシュテスト領域に基づくプリフェッチのためのキャッシュエージングポリシーの選択
US11321245B2 (en) 2016-04-27 2022-05-03 Advanced Micro Devices, Inc. Selecting cache aging policy for prefetches based on cache test regions

Also Published As

Publication number Publication date
JP2558033B2 (ja) 1996-11-27
US5293609A (en) 1994-03-08
EP0509231A1 (en) 1992-10-21

Similar Documents

Publication Publication Date Title
JP2558033B2 (ja) データキャッシュメモリ内のデータを置換する方法
US9710397B2 (en) Data migration for composite non-volatile storage device
US5577224A (en) Method and system for caching data
US5606688A (en) Method and apparatus for dynamic cache memory allocation via single-reference residency times
US6598125B2 (en) Method for caching information between work sessions
US5778430A (en) Method and apparatus for computer disk cache management
US5390315A (en) Allocation of uniform contiguous blocks of DASD storage by maintaining both a bit and a bit map record of available storage
EP1199638A2 (en) System and Method for dynamically controlling cache management
US20130173853A1 (en) Memory-efficient caching methods and systems
JPH0571976B2 (ja)
JPH0877073A (ja) 集合光ディスク装置
US6098153A (en) Method and a system for determining an appropriate amount of data to cache
US6842826B1 (en) Method and apparatus for providing efficient management of least recently used (LRU) algorithm insertion points corresponding to defined times-in-cache
JP2003330792A (ja) ディスクシステムとそのキャッシュ制御方法
KR20180135390A (ko) 대용량 ssd 장치를 위한 데이터 저널링 방법
JP4317531B2 (ja) 複数のメモリ・バッファ・サイズを均衡させるためのシステムおよび方法
US7769953B2 (en) Variable cache data retention system
JPH05233450A (ja) キャッシュモード選択方法
US5584015A (en) Buffer memory management method, recording medium, and computer system incorporating same
JPH08137754A (ja) ディスクキャッシュ装置
CN113296686B (zh) 数据处理方法、装置、设备及存储介质
JPH08263380A (ja) ディスクキャッシュ制御方式
CN111859038A (zh) 一种分布式存储系统数据热度统计方法、装置
JPS60214060A (ja) 外部記憶キヤツシユ制御方式
JP3020512B2 (ja) フアイルデータ管理方法