JPS593773A - バツフア記憶装置のｌｒｕ制御方式 - Google Patents
バツフア記憶装置のｌｒｕ制御方式Info
- Publication number
- JPS593773A JPS593773A JP57111919A JP11191982A JPS593773A JP S593773 A JPS593773 A JP S593773A JP 57111919 A JP57111919 A JP 57111919A JP 11191982 A JP11191982 A JP 11191982A JP S593773 A JPS593773 A JP S593773A
- Authority
- JP
- Japan
- Prior art keywords
- lru
- group
- levels
- bits
- storage device
- 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
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
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
【発明の詳細な説明】
〔発明の技術分野〕
本発明は主記憶装置のデータの一部をブロック単位でコ
ピーして格納するバッファ記憶装置におけるリプレース
ブロックの決定方式に関する。
ピーして格納するバッファ記憶装置におけるリプレース
ブロックの決定方式に関する。
一般にリプレース・ブロックの決定には１・ＲＵ（Ｌｅ
ａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ ）論理方式を用
いているが、ＬＲＵの対象ブロック数が増えるとＬＲＵ
メモリビットの容量が指数的に増加する。
ａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ ）論理方式を用
いているが、ＬＲＵの対象ブロック数が増えるとＬＲＵ
メモリビットの容量が指数的に増加する。
第１図は一般的セットアソシアティブ方式のバッファ記
憶装置の一実施例のブロック図１第２図はセット・アソ
シアティブ方式のバッファ記憶装置を説明する図である
。
憶装置の一実施例のブロック図１第２図はセット・アソ
シアティブ方式のバッファ記憶装置を説明する図である
。
第１図において１１は要求アドレス・レジスタ２−０な
いし２−ｍ７１はタグ部５３−０ないし３−「１は一致
回路、４はアップディト０ロジれぞれ示している。
いし２−ｍ７１はタグ部５３−０ないし３−「１は一致
回路、４はアップディト０ロジれぞれ示している。
尚第１図ではバッファ記憶装置のデータ記憶部は省略し
である。
である。
要求アドレス・レジスタ１には１要求アドレス而：］の
それぞれはバッフ１記憶装置のｔソシアティグ・レベル
０，１．・・・ｍ−１のそれぞれに対応している。第２
図に示すように、バッフ１記へ装置ＢＳはアソシアティ
ブ・レベルｏｌいしｍ−１を有しており、各アソシアテ
ィブ・メモリ単位は１個のセットに分割されている。１
個の分割単位を本明細書ではブロックという。主記憶装
ＷＮＩＳにおいてもに個のフ゛ロックＢごとに１１固の
メモリ単位を構成している。プログラムｙ＜行時には、
必要な主記憶ＭＳのブロックＢのデータは同一のセット
に属するｍ個のブロックＢのうちのどれかに移される。
それぞれはバッフ１記憶装置のｔソシアティグ・レベル
０，１．・・・ｍ−１のそれぞれに対応している。第２
図に示すように、バッフ１記へ装置ＢＳはアソシアティ
ブ・レベルｏｌいしｍ−１を有しており、各アソシアテ
ィブ・メモリ単位は１個のセットに分割されている。１
個の分割単位を本明細書ではブロックという。主記憶装
ＷＮＩＳにおいてもに個のフ゛ロックＢごとに１１固の
メモリ単位を構成している。プログラムｙ＜行時には、
必要な主記憶ＭＳのブロックＢのデータは同一のセット
に属するｍ個のブロックＢのうちのどれかに移される。
バッファ記憶をアクセスするとき、タグ部２−０．２−
１．・・・２−ｍ−１のそれぞれは、セット・アドレス
によって検索され、上位アドレスが読出される。各タグ
部２−０．２−１．・・・２−韮：ゴから読出された上
位アドレスは、一致回路３−０．３−１．・・・３−１
によって要求アドレス・レジスタ１の上位アドレスと比
較される。
１．・・・２−ｍ−１のそれぞれは、セット・アドレス
によって検索され、上位アドレスが読出される。各タグ
部２−０．２−１．・・・２−韮：ゴから読出された上
位アドレスは、一致回路３−０．３−１．・・・３−１
によって要求アドレス・レジスタ１の上位アドレスと比
較される。
バッファ記憶装［ＢＳは〜アソシアティブ・レベル毎に
デリートすることが出来る。何れのアソシアティブ・レ
ベルがデリートされているかは、オって指示される。一
致回路３−０ないし３−ｍ−１のうちの何れかがタグ一
致信号を出力する場合には）アップディトロジック回路
４は１古さ順序を示すＬＲＵパターンを新たに生成する
。アップディト・ロジック回路４で作成されたＬＲＵパ
ターンはＬＲＵメモリ６に１込まれる。ＬＲＵメモリ６
は１セツト毎にそのセットに属するブロックのデータの
古さ順序を示す情報を記憶している。
デリートすることが出来る。何れのアソシアティブ・レ
ベルがデリートされているかは、オって指示される。一
致回路３−０ないし３−ｍ−１のうちの何れかがタグ一
致信号を出力する場合には）アップディトロジック回路
４は１古さ順序を示すＬＲＵパターンを新たに生成する
。アップディト・ロジック回路４で作成されたＬＲＵパ
ターンはＬＲＵメモリ６に１込まれる。ＬＲＵメモリ６
は１セツト毎にそのセットに属するブロックのデータの
古さ順序を示す情報を記憶している。
タグ部２−０ないし２−ｍ−１に該当するアドレスが存
在しなかった場合には１該当ブロツクを主記憶装置ＭＳ
から新九にロードする必要があるが、そのロード先をど
のアソシアティブ−レベルとするかを決定するのがリプ
レース・ロジック回路７である。この場合要求アドレス
□レジスタ１の内のセット・アドレスがＬＲＵアドレス
・レジスタ５にセットされ、ＬＲＵメモリ６の読出しが
行われる。Ｌ ＲＵメモリ６から読出されたＬＲＵ情報
は１リプレース・ロジック回路７に入力され、リプレー
ス・ロジック回路７は、このＬＲＵ情報とデ゛リート・
アソシアティブΦレベル情報とに基づいてｆ” ’）
−トされていないブロックの中から１個のリプレースす
べきブロックを決定する。
在しなかった場合には１該当ブロツクを主記憶装置ＭＳ
から新九にロードする必要があるが、そのロード先をど
のアソシアティブ−レベルとするかを決定するのがリプ
レース・ロジック回路７である。この場合要求アドレス
□レジスタ１の内のセット・アドレスがＬＲＵアドレス
・レジスタ５にセットされ、ＬＲＵメモリ６の読出しが
行われる。Ｌ ＲＵメモリ６から読出されたＬＲＵ情報
は１リプレース・ロジック回路７に入力され、リプレー
ス・ロジック回路７は、このＬＲＵ情報とデ゛リート・
アソシアティブΦレベル情報とに基づいてｆ” ’）
−トされていないブロックの中から１個のリプレースす
べきブロックを決定する。
このようなバッフ１記憶装置ＢＳにおいて、アソシアテ
ィブ−レベルの数がｍの場合１ＬＲＵメモリ６の１セツ
トに関するＬＲＵビットはｍ（ｍ−１）／２ビット必要
となる。例えば４レベルであれば６ビツトで済むものが
、８Ｖべ養では２８ビツトも必要になｆｉ、ＬＲＵメモ
リ６の容量が増すばかシではなく、リプレースロジック
回路７及びアップディトロジック回路４も非常に複雑と
なり、さらには動作速度にも影響を及はす。一方で、バ
ッフ１記憶装置のヒツト率を高めるために、レベル数を
増す要求が高まっている。
ィブ−レベルの数がｍの場合１ＬＲＵメモリ６の１セツ
トに関するＬＲＵビットはｍ（ｍ−１）／２ビット必要
となる。例えば４レベルであれば６ビツトで済むものが
、８Ｖべ養では２８ビツトも必要になｆｉ、ＬＲＵメモ
リ６の容量が増すばかシではなく、リプレースロジック
回路７及びアップディトロジック回路４も非常に複雑と
なり、さらには動作速度にも影響を及はす。一方で、バ
ッフ１記憶装置のヒツト率を高めるために、レベル数を
増す要求が高まっている。
本発明は、アソシアティブ・レベル数を増加し１かつＬ
ＲＵビット数の増加を最小にとどめ１さらにはエラーを
生じてもバッフ１能力を低下させることなく処理を続行
できるようにすることを目的とする。
ＲＵビット数の増加を最小にとどめ１さらにはエラーを
生じてもバッフ１能力を低下させることなく処理を続行
できるようにすることを目的とする。
本発明は１アンシアテイプ・レベル数を増加し、かつＬ
ＲＵビット数の増加を最小にとどめ、さらにはエラーを
生じてもバッファ能力を低下させることなく処理を続行
できるようにすることを目的とする。
ＲＵビット数の増加を最小にとどめ、さらにはエラーを
生じてもバッファ能力を低下させることなく処理を続行
できるようにすることを目的とする。
本発明は１アソシアテイブ・レベルを複数のグループに
分け、各グループ内でＬＲＵ論理をとることによってＬ
ＲＵビット数を削減し、その代りにどのグループをリプ
レース対象とするかを指示するフラグ・ビットを別途設
ける。さらにこのフラグビットのエラ一時にはバッファ
能力が落ちるため、フラグビットを三重化し、多数決を
とって決定するようにして性能低下を防止する。
分け、各グループ内でＬＲＵ論理をとることによってＬ
ＲＵビット数を削減し、その代りにどのグループをリプ
レース対象とするかを指示するフラグ・ビットを別途設
ける。さらにこのフラグビットのエラ一時にはバッファ
能力が落ちるため、フラグビットを三重化し、多数決を
とって決定するようにして性能低下を防止する。
第３図は本発明の一実施例要部ブロック図であシ、８ア
ソシアテイブ・レベルを２つのグループに分は九例を示
す。６−１．６−２はＬＲＵメモリ６の・１セツト分の
ＬＲＵビットを示し、レベル７ ０〜３のグループ６−１とレベル４〜＄のり゛゛ループ
６−２分かれている。７−１．７−２はリプレース・ロ
ジック回路７のレベル０〜３に関する回路とレベル４〜
７に関する回路である。
ソシアテイブ・レベルを２つのグループに分は九例を示
す。６−１．６−２はＬＲＵメモリ６の・１セツト分の
ＬＲＵビットを示し、レベル７ ０〜３のグループ６−１とレベル４〜＄のり゛゛ループ
６−２分かれている。７−１．７−２はリプレース・ロ
ジック回路７のレベル０〜３に関する回路とレベル４〜
７に関する回路である。
ＬＲＵメモリ６−１．６−２において、（０１）〜（６
７）は夫々１ビツトの情報で、例えばピッ）（ｉ、ｊ）
はレベル五とレベルｊとのどちラカ新しく使用されるか
を示すものである。
７）は夫々１ビツトの情報で、例えばピッ）（ｉ、ｊ）
はレベル五とレベルｊとのどちラカ新しく使用されるか
を示すものである。
また８はＨ／ｅ （ホット会アンド・コールド）と呼ぶ
フラグビットであり、２つのグループのうちどちらかの
グループをリプレース対象とするかを指示するものであ
る。このＨ／Ｃビットはいずれかのグループのアソシア
ティブ・レベルにブロック・ロードがあったとき、他方
のグループをリプレース対象とするようにその値を更新
するように制御される。尚、グループ数が３以上のとき
は循環的にリプレース対象グループを指示するようにす
ればよい。
フラグビットであり、２つのグループのうちどちらかの
グループをリプレース対象とするかを指示するものであ
る。このＨ／Ｃビットはいずれかのグループのアソシア
ティブ・レベルにブロック・ロードがあったとき、他方
のグループをリプレース対象とするようにその値を更新
するように制御される。尚、グループ数が３以上のとき
は循環的にリプレース対象グループを指示するようにす
ればよい。
リプレース決定手段を構成することができる。
ここでＨ／Ｃビット８にエラーを生じて固定値に縮退し
まったとすると、常に特定のグループでしかリプレース
が行なわれず、結果的にはアソシアティブ・レベル数が
４レベルしかない場合と同等の性能しか得られないこと
になる。従って本発明ではＨ／Ｃビットを三重化してＨ
ＣＯ〜ＨＣ２の３ビツトを設ける。読出し時にはそれら
３ピツトの大 多数決を各零回路９にてとって）各リプレーＵロジック
回路７−１．７−２に与える。またリプレース・ロジッ
ク回路７−１には０Ｐ８Ｒからのデリート信号０〜３が
１同じく７−２はデリート信号４〜７が与えられ、Ｈ／
Ｃビットで指定された方のグループでデリートされてい
ないアソシアティブの中から最も古いレベルを決定して
リプレース・アソシアティブ−レベルとして出力する。
まったとすると、常に特定のグループでしかリプレース
が行なわれず、結果的にはアソシアティブ・レベル数が
４レベルしかない場合と同等の性能しか得られないこと
になる。従って本発明ではＨ／Ｃビットを三重化してＨ
ＣＯ〜ＨＣ２の３ビツトを設ける。読出し時にはそれら
３ピツトの大 多数決を各零回路９にてとって）各リプレーＵロジック
回路７−１．７−２に与える。またリプレース・ロジッ
ク回路７−１には０Ｐ８Ｒからのデリート信号０〜３が
１同じく７−２はデリート信号４〜７が与えられ、Ｈ／
Ｃビットで指定された方のグループでデリートされてい
ないアソシアティブの中から最も古いレベルを決定して
リプレース・アソシアティブ−レベルとして出力する。
尚、ＬＲＵビット６−１．６−２及びＨ／Ｃビット８は
全セットの夫々について存在することは勿論である。ま
たこれらはセットアドレスでアクセスされるＬＲＵメモ
リ６の１語を１５ピツトとすることによシ構成し得るこ
ともいうまでもない〔発明の効果〕 以上の如く１７ンシアテイブ・レベルを例えばうところ
を、本発明によれば６＋６＋３＝１５ビツトで爽現でき
、ＬＲＵメモリ６０節減になるばかりでなく、リプレー
ネロジック回路７−１．７−２も同一構成の回路を複数
使用できるので、回路のりビータビリティ向上し１コス
トダウンにもなる。
全セットの夫々について存在することは勿論である。ま
たこれらはセットアドレスでアクセスされるＬＲＵメモ
リ６の１語を１５ピツトとすることによシ構成し得るこ
ともいうまでもない〔発明の効果〕 以上の如く１７ンシアテイブ・レベルを例えばうところ
を、本発明によれば６＋６＋３＝１５ビツトで爽現でき
、ＬＲＵメモリ６０節減になるばかりでなく、リプレー
ネロジック回路７−１．７−２も同一構成の回路を複数
使用できるので、回路のりビータビリティ向上し１コス
トダウンにもなる。
第１図は〒般的なセット・アソシアティブ方式のバッフ
１記憶装置の制御部ブロック図１第２図はセラ）−テソ
シーアテイプの説明図、第３図は本発明の一実施例要部
ブロック図であり、６−１゜６−２は各グループのり、
ＲＵビットＳ８はＨ／Ｃ（ホット・アンド・コールド）
フラグピット）７−１．７−２は各グループのリプレー
ス・ロジック回路Ｓ９は多数決回路である。 ５０７
１記憶装置の制御部ブロック図１第２図はセラ）−テソ
シーアテイプの説明図、第３図は本発明の一実施例要部
ブロック図であり、６−１゜６−２は各グループのり、
ＲＵビットＳ８はＨ／Ｃ（ホット・アンド・コールド）
フラグピット）７−１．７−２は各グループのリプレー
ス・ロジック回路Ｓ９は多数決回路である。 ５０７
Claims (1)
- 【特許請求の範囲】 主記憶装置のデータの一部をブロック単位でコピーして
格納し・新たなブロックの格納に際してリプレースすべ
きブロックをＬＲＵ方式で決定するバッフ１記憶装置に
おいて１バツフア記憶装置のブロックを複数のグループ
に分け、各グループ毎にＬＲＵ方式でリプレースブロッ
クを決定する手段を設けるとともに１どのグループをリ
プレース対象とするかを指示するフラグビットを設け、
こ かつ左のフラグビットを三重化して設けて１読出し時に
は多数決をとるようにしたことを特徴とするバッファ記
憶装置のＬＲＵ制御方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57111919A JPS593773A (ja) | 1982-06-29 | 1982-06-29 | バツフア記憶装置のｌｒｕ制御方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57111919A JPS593773A (ja) | 1982-06-29 | 1982-06-29 | バツフア記憶装置のｌｒｕ制御方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS593773A true JPS593773A (ja) | 1984-01-10 |
Family
ID=14573398
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57111919A Pending JPS593773A (ja) | 1982-06-29 | 1982-06-29 | バツフア記憶装置のｌｒｕ制御方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS593773A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60163147A (ja) * | 1984-02-02 | 1985-08-26 | Nec Corp | リプレ−スメント方式 |
| JPS623360A (ja) * | 1985-06-28 | 1987-01-09 | Nec Corp | 情報処理装置 |
| JPS63163941A (ja) * | 1986-12-26 | 1988-07-07 | Hitachi Ltd | バツフアメモリ装置 |
| US8392660B2 (en) | 2006-11-30 | 2013-03-05 | Fujitsu Limited | Cache system including a plurality of processing units |
-
1982
- 1982-06-29 JP JP57111919A patent/JPS593773A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60163147A (ja) * | 1984-02-02 | 1985-08-26 | Nec Corp | リプレ−スメント方式 |
| JPS623360A (ja) * | 1985-06-28 | 1987-01-09 | Nec Corp | 情報処理装置 |
| JPS63163941A (ja) * | 1986-12-26 | 1988-07-07 | Hitachi Ltd | バツフアメモリ装置 |
| US8392660B2 (en) | 2006-11-30 | 2013-03-05 | Fujitsu Limited | Cache system including a plurality of processing units |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5530829A (en) | Track and record mode caching scheme for a storage system employing a scatter index table with pointer and a track directory | |
| US5640534A (en) | Method and system for concurrent access in a data cache array utilizing multiple match line selection paths | |
| US4580240A (en) | Memory arrangement operable as a cache and a local memory | |
| US4064489A (en) | Apparatus for searching compressed data file | |
| US5668972A (en) | Method and system for efficient miss sequence cache line allocation utilizing an allocation control cell state to enable a selected match line | |
| JPS624745B2 (ja) | ||
| US5805855A (en) | Data cache array having multiple content addressable fields per cache line | |
| EP0533427B1 (en) | Computer memory control system | |
| US5890221A (en) | Method and system for offset miss sequence handling in a data cache array having multiple content addressable field per cache line utilizing an MRU bit | |
| US5276829A (en) | Data processing system including cache memory for rapidly converting a logical address into a physical address using shared memory flag | |
| US4608671A (en) | Buffer storage including a swapping circuit | |
| US4044336A (en) | File searching system with variable record boundaries | |
| JPS593773A (ja) | バツフア記憶装置のｌｒｕ制御方式 | |
| US4733367A (en) | Swap control apparatus for hierarchical memory system | |
| JPH0614325B2 (ja) | リプレ−スメント方式 | |
| JPH05158795A (ja) | キャッシュメモリシステム | |
| JPH08328960A (ja) | キャッシュメモリ装置 | |
| JP2636485B2 (ja) | キャッシュ記憶装置 | |
| JPH0512119A (ja) | キヤツシユメモリ回路 | |
| JPH0689228A (ja) | キャッシュメモリ制御装置 | |
| EP0502206A1 (en) | System equipped with processor and cache memory, and method of controlling said cache memory | |
| JPS6331809B2 (ja) | ||
| JPH04145552A (ja) | キャッシュ記憶装置 | |
| JPH01173144A (ja) | 情報処理装置 | |
| JPH02156352A (ja) | キャッシュメモリ |