JPH044617B2 - - Google Patents

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ 産業上の利用分野 Ｂ 開示の概要 Ｃ 従来の技術 Ｄ 発明が解決しようとする問題点 Ｅ 問題点を解決するための手段 Ｆ 作用 Ｇ 実施例 G1 一般的構成の説明（第１図、第２図） G2 メモリ・アドレス及びエントリの説明（第
３図〜第６図） G3 L2キヤツシユの詳細な説明（第７図） G4 WSHTの詳細な説明（第８図） G5 ライン有効ビツト更新論理及びライン使用
ビツト更新論理の説明（第９図、第１０図） Ｈ 発明の効果 Ａ 産業上の利用分野 本発明はデータ処理システムに係り、更に詳細
に説明すれば階層メモリを備えた高性能データ処
理システムのメモリ・アクセス時間及びメモリ・
アクセス・トラヒツクを改善することに係る。

Ｂ 開示の概要 本発明は、第１レベル（L1）のキヤツシユ、
第２レベル（L2）のキヤツシユ及び第３レベル
（L3）のメイン・メモリから成る階層メモリを備
えたデータ処理システムに関する。このような階
層メモリを備えたデータ処理システムでは、一般
に、メインメモリとL2キヤツシユの間の情報転
送単位は、L2キヤツシユとL1キヤツシユの間の
それよりも大きい。本願明細書では、前者の単位
で転送される情報の集りを情報セツトと呼び、後
者の単位で転送される情報の集りを情報サブセツ
トと呼ぶ。１つの情報セツトは、複数の情報サブ
セツトから構成される。以下の説明は、後述の
IBMテクニカル・デイスクロージヤー・ブレテ
ンで開示されたアーキテクチヤーの用語に即して
行うが、情報セツトに対応するものはブロツクで
あり、情報サブセツトに対応するものは、ライン
である。本発明は、L2キヤツシユに保持されて
いる各ブロツクのうち実際に使用されたラインを
識別するためのワーキング・セツト履歴テーブル
（WSHT）を設け、L2キヤツシユ中の所与のブロ
ツクがメイン・メモリへ戻され且つその後にこの
ブロツクが要求される場合、このブロツクが以前
にL2キヤツシユに保持されている間に使用され
たラインだけをL2キヤツシユへ転送することに
より、この種のデータ処理システムの性能を改善
するようにしたものである。

Ｃ 従来の技術 高性能の多重処理システムでは、複数のプロセ
ツサが１つの階層メモリを共有するか、又は各プ
ロセツサがそれ自身の階層メモリを備えている。
ここで、階層メモリとは、キヤツシユと呼ばれる
高速小容量のバツフアと、低速大容量のメイン・
メモリを含むものである。キヤツシユはプロセツ
サが最近に使用した一部のデータを保持するにす
ぎないが、そのヒツト率は非常に高く、これによ
りプロセツサの平均メモリ・アクセス時間が著し
く短縮されている。しかしながら、キヤツシユの
性能は、依然としてそのサイズによつて制約され
るのである。すなわち、メイン・メモリが比較的
遠い位置に設けられている場合は、所謂キヤツシ
ユ・ミスが極く僅かしか生じないとしても、プロ
セツサはその必要とするデータがメイン・メモリ
から取出されるまで長時間の間これを待機しなけ
ればならないからである。キヤツシユ・ミスを補
償するための１つの方法は、キヤツシユとメイ
ン・メモリの間に第２レベルのキヤツシユを設け
ることである。IBMテクニカル・デイスクロー
ジヤ・ブレテン（Technical Disclosure
Bulletin）、第21巻、第６号、1978年11月発行、
第2468頁−第2469頁には、第２レベルのキヤツシ
ユが記述されている。ここで、プロセツサに最も
近いキヤツシユは第１レベルのキヤツシユ（L1
キヤツシユ）と呼ばれ、L1キヤツシユとメイ
ン・メモリの間にあるキヤツシユは第２レベルの
キヤツシユ（L2キヤツシユ）と呼ばれる。

L2キヤツシユはL1キヤツシユよりも低速であ
るが、比較的大きな容量を有する。従つて、L1
キヤツシユ及びL2キヤツシユの記憶単位をそれ
ぞれライン及びブロツクと呼ぶことにすれば、１
ブロツクを１ラインよりも相当大きく取るのが有
利である。このようにすれば、L2キヤツシユの
デイレクトリ空間が節約できるだけでなく、プロ
セツサがメモリ位置を逐次にアクセスすることが
非常に多いという特性を有効に活用することがで
きるからである。フル・ブロツク型のL2キヤツ
シユでキヤツシユ・ミスが生ずる場合、すなわち
プロセツサによつて要求されたデータを含むブロ
ツクがL2キヤツシユに置かれていない場合、メ
イン・メモリからL2キヤツシユへブロツク転送
が行われなければならない。しかしながら、L2
キヤツシユにおける２つ以上のキヤツシユ・ミス
が連続的に生ずるような場合には、プロセツサは
長い遅延に遭遇することになる。この種の現象
は、L2キヤツシユのために選ばれた大きなブロ
ツク・サイズに起因するものである。

デイレクトリ空間を増加することなくこの種の
現象に起因する遅延を最小にするための１つの方
法は、IBMシステム／360モデル85で使用され
た、セクタ型キヤツシユの概念を使用することで
ある。この概念によれば、L2キヤツシユにおけ
る記憶割振りは依然としてブロツク単位で行われ
るが、ブロツクの一部（通常はキヤツシユ・ミス
を生ぜしめたL1ライン）だけをメイン・メモリ
から取出して、これをL2キヤツシユへロードす
ればよい。L1キヤツシユに比べると、セクタ型
のL2キヤツシユはプロセツサで実行されている
プログラムの一層大きなワーキング・セツトを保
持しうることは明らかである。しかしながら、プ
ロセツサが新しいプログラム、従つて新しいワー
キング・セツトへ切換わる場合には、両キヤツシ
ユとも同数のキヤツシユ・ミスを生ぜしめること
になる。セクタ型のL2キヤツシユはキヤツシ
ユ・ミス発生時にL1キヤツシユと同じ量のデー
タを取出すから、もしL2キヤツシユが各キヤツ
シユ・ミスごとに１又は２ラインのみを常に取出
すように制限されていなければ、L2キヤツシユ
に新しいワーキング・セツトが先にロードされる
ことがありうる。

プロセツサとメイン・メモリの間に設けられた
通常のL1キヤツシユと比べると、L2キヤツシユ
の構成、動作様式及びメイン・メモリとの相互作
用には、実質的な違いはない。すなわち、L1キ
ヤツシユについて使用されるすべての概念は、
L2キヤツシユにも同様に適用することができる
のである。メイン・メモリからL1キヤツシユへ
データをロードする方法には、多くのものがあ
る。たとえば、米国特許第3588829号に記述され
た階層メモリでは、キヤツシユとメイン・メモリ
の間のバスをバツフアとして使用し且つインタリ
ーブ式メモリを使用することによつて、階層メモ
リに対する複数の取出又は書込動作を並列に行わ
せるようにしている。また米国特許第4317168号
に記述されたキヤツシユ・システムでは、メイ
ン・メモリからのライン取出とキヤツシユからの
変更ラインの置換を並列に行わせるようにしてい
る。これらの特許に記述されたものは、いずれも
階層メモリに対するアクセスの同時性に重きを置
いている。一方、これまでに提案されたすべての
ローデイング方式は、キヤツシユ・ミスが生じた
場合にだけキヤツシユへのロードを行うという意
味で、デマンド式のものであると云うことができ
る。たとえば、米国特許第3735360号及び第
3771137号に記述されたストア・イン型のキヤツ
シユでは、キヤツシユ・ミスの発生時に任意のラ
インをキヤツシユへロードするとともに、変更ラ
インをその置換が必要となるまでキヤツシユ中に
保持させるようにしている。

また米国特許第4442487号に記述された多重処
理システムにおける３レベルの階層メモリでは、
各プロセツサは、それ自身のL1キヤツシユ及び
L2キヤツシユに加えて、各レベルにおける共有
キヤツシユを備えている。ここで強調されている
のは、多重処理システムにおける複数のプロセツ
サによつてデータを有効に共有するということで
ある。

Ｄ 発明が解決しようとする問題点 前記特許のいずれにも、プロセツサがそのワー
キング・セツトを構築することを助けるように、
キヤツシユとメイン・メモリの間のトラヒツクを
考慮しつつ、複数のラインをキヤツシユへロード
することについては、全く示されていない。

従つて、本発明の目的は、３レベルの階層メモ
リを備えたデータ処理システムのメモリ・アクセ
ス時間を改善することにある。

本発明の他の目的は、３レベルの階層メモリを
備えたデータ処理システムにおいて、L2キヤツ
シユに保持されている各ブロツクのうち過去に使
用されたラインを識別するためのワーキング・セ
ツト履歴テーブルを設け、L2キヤツシユ中の所
与のブロツクがメイン・メモリへ戻され且つその
後にこのブロツクが要求される場合、このブロツ
クがL2キヤツシユに以前に保持されている間に
使用されたラインだけをL2キヤツシユへ転送す
ることにより、当該データ処理システムのメモ
リ・アクセス時間を改善することにある。

Ｅ 問題点を解決するための手段 本発明は、メイン・メモリからL2キヤツシユ
へデータを取出すための巧妙な方法を提供するも
のである。この概念は、各ブロツク中のどのライ
ンが過去に使用されたかを記録することに基いて
いる。云いかえれば、所与のブロツクをメイン・
メモリに戻した後に該当するブロツク・ミス（キ
ヤツシユ・ミス）が生ずる場合、このブロツクが
L2キヤツシユに保持されている間に使用された
ラインだけをL2キヤツシユへ転送するのである。
この概念を実現するため、セクタ型のL2キヤツ
シユに関連してワーキング・セツト履歴テーブル
（WSHT）が設けられる。L2キヤツシユの編成及
び動作は、WSHTとのインタフエースを除けば、
通常のセクタ型キヤツシユと同じである。
WSHTの構成は、L2キヤツシユのデイレクトリ
と同様であるが、それより大きいサイズを有す
る。WSHTはプロセツサによつて最近に使用さ
れたブロツクの識別子を保持し、また各ブロツク
中のラインごとに使用ビツトを保持する。
WSHTは有限のテーブルであるから、LRU
（Least Recently Used）アルゴリズムに従つた
置換を行うことが必要である。L2キヤツシユに
対するアクセス要求のアドレスは、アクセスされ
たブロツク中の使用ラインを更新するために、
WSHTにも並列に送られる。L2キヤツシユでブ
ロツク・ミスが生ずる場合、もしそのブロツク識
別子がWSHT中で検出されるならば、当該ブロ
ツクのうち使用ビツトがオンとなつている任意の
ラインがメイン・メモリからL2キヤツシユへロ
ードされる。

さもなければ、ブロツク識別子がWSHTに書
込まれ、そしてブロツク・ミスを生ぜしめたライ
ンだけがL2キヤツシユへロードされる。

Ｆ 作用 本発明はセクタ型のL2キヤツシユに基礎を置
いている。L2キヤツシユでブロツク・ミスが生
ずる場合、このブロツクがL2キヤツシユに保持
されている間の過去の使用状況に従つて、当該ブ
ロツク中のラインがメイン・メモリから取出され
る。プロセツサで実行中のプログラムはメモリ・
セグメントにおける１組の位置を反復的に使用す
る傾向があるから、本発明によれば、ブロツク・
ミスが生じた際にプロセツサが将来使用するであ
ろう当該ブロツク中のラインを正確に推定するこ
とができる。本発明に従つたL2キヤツシユは、
各ブロツクにおけるラインの使用状況を記録する
ワーキング・セツト履歴テーブル（WSHT）を
備えている。このため、ブロツク中のすべてのラ
インを取出すことが不要となるから、メモリ・ト
ラヒツクを著しく減少させることができる。一
方、所与のブロツクが再び有効になると、プロセ
ツサは直ちにそのワーキング・セツトを再構築す
ることができる。この結果、メモリ・アクセス時
間が著しく減少することになる。

Ｇ 実施例 G1 一般的構成の説明（第１図、第２図） 第２図のデータ処理システムは、プロセツサ１
００とその関連する３レベルの階層メモリ、すな
わち第１レベル（L1）のキヤツシユ２００及び
そのデイレクトリ２５０、第２レベル（L2）の
キヤツシユ３００及びそのデイレクトリ３５０、
並びにメイン・メモリ５００を含んでいる。これ
らのメモリはアクセス要求のアドレスを転送する
１つ以上のアドレス・バス１１０を介して接続さ
れ、また変更データ又は要求データを転送するデ
ータ・バス１２０を介して接続されている。一般
に、アクセス要求（書込み又は取出し）はアドレ
ス・バス１１０を介してまずL1キヤツシユ・デ
イレクトリ２５０へ送られ、次にL2キヤツシ
ユ・デイレクトリ３５０へ送られ、最後にメイ
ン・メモリ５００へ送られる。この階層メモリに
おける探索は、要求データが検出されたレベルで
終了する。

このシステムの動作を説明する前に、本明細書
で使用する用語を説明しておく。メモリ中の一定
数のバイトを参照するアクセス要求のサイズは一
定であり、「アクセス単位」と呼ばれる。本発明
は特定のアクセス単位を必要としないが、説明の
便宜上、以下ではすべてのアクセス要求がダブル
ワード単位で行われると仮定する。L1キヤツシ
ユ２００の記憶単位は「ライン」と呼ばれ、これ
はメモリ中の連続データを保持することができ
る。L1キヤツシユ・デイレクトリ２５０は、L1
キヤツシユ２００に現に保持されている各ライン
ごとに１つのエントリを有する。またこのデイレ
クトリはL1キヤツシユ２００に保持されている
各ラインの置換順序も維持しているので、L1キ
ヤツシユ２００が充満状態にある間に所与のライ
ンをロードしようとする場合には、最も長い間使
用されなかつたラインを決定してこれを置換する
ことができる。L2キヤツシユ３００の記憶単位
は「ブロツク」と呼ばれ、これはL1キヤツシユ
２００中の１ラインよりも相当大きいものと仮定
する。現にアクセスを要求されているダブルワー
ドを含むライン及びブロツクは、それぞれ「アク
セス・ライン」及び「アクセス・ブロツク」と呼
ばれる。ブロツク・ミス発生時にブロツク全体を
出し入れするようなフル・ブロツク型L2キヤツ
シユの構成及び動作は、L1キヤツシユ２００の
それと同じである。しかしながら、セクタ型の
L2キヤツシユ３００はこれとは若干異なる。す
なわち、データの記憶割振り及び置換は依然とし
てブロツク単位で行われるが、データのロードは
ライン単位で行われるからである。もしアクセ
ス・ブロツクがL2キヤツシユ３００に現に保持
されていなければ、当該ブロツクのうち極く僅か
なラインだけがL2キヤツシユ３００へロードさ
れる。これは「ブロツク・ミス」と呼ばれる。ブ
ロツク・ミスが存在する場合か、或いはアクセ
ス・ブロツクがL2キヤツシユ３００で検出され
るとしても、要求されているダブルワードを含む
ラインがL2キヤツシユ３００に保持されていな
い場合には、現アクセス要求は「ライン・ミス」
を発生する。

当該技術分野では周知のように、キヤツシユと
その上位レベルのメモリに置かれたデータのコピ
ーを一致させるためには、２つの方法を使用する
ことができる。すなわち、ストア・イン型キヤツ
シユでは、キヤツシユからその上位レベルのメモ
リへの置換が必要となるまで、変更ラインの最新
コピーをキヤツシユにだけ保持させるようにして
いる。一方、ストア・スルー型キヤツシユでは、
プロセツサによつて変更されたすべてのデータの
最新コピーをキヤツシユ及びその上位レベルのメ
モリに同時に保持させるようにしている。後者の
方法はデータ書込みの際にキヤツシユ及びその上
位レベルのメモリを同時に更新することを必要と
するが、前者の方法ではキヤツシユ中にデータが
保持されている場合でもその上位レベルのメモリ
を更新する必要はない。説明の便宜上、以下では
ストア・スルー型のL1キヤツシユ２００とスト
ア・イン型のL2キヤツシユ３００が使用される
ものと仮定する。ストア・イン型キヤツシユ及び
その置換論理については、米国特許第3735360号
及び第3771137号に詳細に記述されている。スト
ア・スルー型キヤツシユの詳細は、シー・ジエ
ー・コンテイによる論文「バツフア記憶装置の概
念」、アイ・イー・イー・イー コンピユータ・
グループ・ニユース（C.J.Conti、“Concepts for
Buffer Storage”、IEEE Computer Group
News）、1969年３月発行、第９頁−第13頁に記
述されている。さらにセクタ型キヤツシユの構成
及び動作は、IBMシステムズ・ジヤーナル
（IBM Systems Journal）、第７巻、第１号、
1968年、第15頁−第21頁に記述されている。従つ
て、これらのキヤツシユの詳細については、本明
細書では省略する。

第１図は本発明に従つたワーキング・セツト履
歴テーブル（以下「WSHT」と略す。」４００の
実現模式を示す。WSHT４００は通常のデー
タ・メモリを備えていないが、最近に使用された
ブロツクのすべての識別子を保持するテーブルを
備えており、そこに以下で説明するラインの使用
ビツトを記憶している。WSHT４００は、L2キ
ヤツシユ・デイレクトリ３５０に対するインタフ
エース４５０を除けば、このデイレクトリと実質
的に同様のものである。L2キヤツシユ３００の
アクセスが行われるたびに、これと同じアドレス
がWSHT４００にも送られる。もしアクセス・
ブロツクの識別子がWSHT４００で検出される
ならば、当該ブロツクにおけるアクセス・ライン
の使用ビツトが更新される。さもなければ、最も
長い間使用されなかつたブロツクの識別子を現ア
クセス・ブロツクの識別子と置換し、そして当該
ブロツクにおけるアクセス・ラインの使用ビツト
をオンに転ずる。L2キヤツシユ・デイレクトリ
３５０がブロツク・ミスを検出する場合は、これ
はインタフエース４５０を介してWSHT４００
に信号を送ることにより、WSHT４００に当該
ブロツクの識別子が存在するか否かを調べさせ
る。もしこのブロツクの識別子がWSHT４００
で検出されるならば、使用ビツトがオンとなつて
いるすべてのラインがL2キヤツシユ３００へ取
出される。但し、このブロツク・ミスを生ぜしめ
たラインについては、L2キヤツシユの通常の動
作を通して既に取出要求が送出されているので、
これは新たな取出しの対象とならない。

G2 メモリ・アドレス及びエントリの説明（第
３図〜第６図） 第３図は、L2キヤツシユ３００及びそのデイ
レクトリ３５０をアドレスするために使用され
る、アクセス要求の24ビツト・アドレスを示す。
説明の便宜上、ここではL1キヤツシユ２００及
びL2キヤツシユ３００の構成について下記の事
項を仮定している。

●24ビツト・アドレツシング（ビツト０−23） ●アクセス単位＝８バイト（１ダブルワード） ●L1キヤツシユ ストア・スルー型 １ライン＝128バイト ●L2キヤツシユ １ブロツク＝512バイト（４ラ
イン） ４ウエイのセツト・アソシアテイブ 512コラム セクタ型 容量＝1024ブロツク（1Mバイト） 第３図を再び参照するに、フイールドＡ（ビツ
ト０−５）は、現アクセス・ブロツクの識別子
（ID）である。これはL2キヤツシユ・デイレクト
リ３５０中のブロツク識別子と比較され、当該ブ
ロツクがL2キヤツシユ３００に保持されていな
い場合には、L2キヤツシユ・デイレクトリ３５
０へ書込まれる。フイールドＢ（ビツト６−14）
は、L2キヤツシユ３００のコラム・アドレスで
ある。フイールドＣ（ビツト15−16）は、当該ブ
ロツクにおけるアクセス・ラインのライン識別子
である。フイールドＤ（ビツト17−20）は、この
ラインにおける要求中ダブルワードの識別子であ
る。

第４図は、WSHT４００をアドレスするため
に使用される、24ビツト・アドレスを示す。但
し、WSHT４００のサイズはL2キヤツシユ３０
０と異なるから、第４図のアドレスは第３図とは
異なるフイールドへ分割されている。WSHT４
００については、下記の事項を除き、L2キヤツ
シユ３００と同じ事項が仮定されている。

●2048コラム ●容量＝8192ブロツク（すなわち、8192ブロツク
の履歴を保持） 第４図を参照するに、フイールドA′（ビツト０
−３）はブロツク識別子であり、フイールト
B′（ビツト４−14）はWSHT４００におけるコラ
ム・アドレスである。フイールドA′及びB′は、
L2キヤツシユ３００中の現アクセス・ブロツク
を参照する。フイールドＣ（ビツト15−16）は、
第３図と同じライン識別子である。

第５図は、L2キヤツシユ・デイレクトリ３５
０の１エントリを表わす。これは第３図のフイー
ルドＡに対応するブロツク識別子（フイールド
Ａ）を保持し、また当該ブロツク中の各ラインご
とに１つの有効ビツトを保持する。各有効ビツト
は、これに対応するラインがL2キヤツシユ３０
０に現にロードされているか否かを指示するため
のものである。第６図は、WSHF４００の１エ
ントリを表わす。これは第４図のフイールド
A′に対応するブロツク識別子（フイールドA′）
を保持し、また当該ブロツク中の各ラインごとに
１つの使用ビツトを保持する。各使用ビツトは、
これに対応するラインがL2キヤツシユ３００に
置かれている間にプロセツサ１００によつて使用
されたことがあるか否かを指示するためのもので
ある。

G3 L2キヤツシユの詳細な説明（第７図） 次に、L2キヤツシユ３００及びL2キヤツシ
ユ・デイレクトリ３５０の詳細な動作を説明す
る。第７図には、L2キヤツシユ３００、L2キヤ
ツシユ・デイレクトリ３５０及びWSHT４００
とのインタフエース４５０が詳細ブロツク図の形
式で示されている。図示されたシステムは４ウエ
イのセツト・アソシアテイブ式キヤツシユであつ
て、デイレクトリ、更新／置換アレイ及び制御論
理を含む。L2キヤツシユ３００は、入力ゲート
回路３０１、出力ゲート回路３０２、ORゲート
３０３及びデータ入力バス３０５を含む。キヤツ
シユ・デイレクトリ３５０は、アドレス入力ゲー
ト回路３５１、アドレス比較論理３５２及びライ
ン・インジケータ３５３を含む。更新／置換アレ
イは、置換アレイ３５５、更新／置換論理３５
６、アドレス・ゲート回路３５７及び３５８、並
びにライン有効ビツト更新論理（LVUL）３７０
から成る。

プロセツサ１００からバス１１０に与えられる
アクセス要求のアドレスは、第３図に関連して既
に説明したフイールドＡ及びＢに従つて、デイレ
クトリ３５０及び置換アレイ３５５をアドレスす
るために使用される。ブロツク識別子Ａはアドレ
ス入力ゲート路３５１へ供給され、またアドレス
比較論理３５２にも供給される。コラム・アドレ
スＢは、比較すべきブロツク識別子の特定のコラ
ムを選択するために、図示のようにデイレクトリ
３５０へ供給される。ライン・インジケータ３５
３は、２のべき乗演算を遂行することにより、ラ
イン識別子Ｃを所与のブロツク中のライン位置
C′へ変換する。すなわち、C′＝2^Cである。前述の
内容から明らかなように、１ブロツクを構成する
４ラインのライン識別子は、Ｃ＝‘00'、‘01'、
‘10'及び‘11'にそれぞれ等しい。これらのライ
ン識別子は、当該ブロツクにおける各ラインの位
置をそれぞれ表わすために、C′＝‘0001'、‘
0010'、‘0100'及び‘1000'となるようにそれぞれ
変換される。このC′を当該ブロツクの有効ビツト
（第５図参照）と比較して両者が一致すれば、ラ
インＣは現に当該ブロツク中に存在することがわ
かる。まず、コラム・アドレスＢによつて指定さ
れたエントリＥないしＨをアドレス比較論理３５
２へ同時に読出して、これをブロツク識別子Ａと
比較する。もし１つのエントリが一致すれば、ア
ドレス比較論理３５２はブロツク・ヒツトを発生
する。また有効ビツトとC′の論理演算結果が非ゼ
ロであれば、アドレス比較論理３５２はライン・
ビツトを発生する。これと同時に、ブロツクＥな
いしＨに対応するデータが出力ゲート回路３０２
へ読出される。アドレス比較論理３５２の比較結
果はバス３６１を介してL2キヤツシユ３００の
出力ゲート回路３０２へ送られ、そしてこれが取
出しアクセスに対するライン・ヒツトであれば、
ブロツクＡのラインＣにおけるダブルワードが選
択され、かくてORゲート３０３、データ出力バ
ス３０６及びデータ・バス１２０（第１図）を介
してL1キヤツシユ２００又はプロセツサ１００
へ送られる。一方、データ書込みの場合は、書込
むべきダブルワードはバス１２０及びデータ入力
バス３０５を介して入力ゲート回路３０１に供給
され、最終的にL2キヤツシユ３００へ書込まれ
る。変更ブロツクはL2キヤツシユ３００へ戻さ
れる。もしブロツクＡがL2キヤツシユ３００に
置かれているが、アクセス・ラインＣがL2キヤ
ツシユ３００に置かれていなければ、すなわちラ
インＣの有効ビツトがキヤツシユ・デイレクトリ
３５０中でオフとなつているならば、ライン・ミ
スが発生され、そして当該要求はメイン・メモリ
５００（第１図）へ送られる。この場合、当該ラ
イン・ミスを生ぜしめたラインは、入力ゲート回
路３０１を介してL2キヤツシユ３００へロード
される。もしいずれのブロツクについてもアドレ
ス一致が検出されなければ、ブロツク・ミスが発
生され、そしてアクセス・ラインのロード要求が
メイン・メモリへ送られる。これと同時に、イン
タフエース４５０を介してWSHT４００へブロ
ツク・ミス信号が送られ、これに応じて当該ブロ
ツク中の他のラインをL2キヤツシユ３００へロ
ードすべきか否かが検査される。

LRU置換論理の詳細は米国特許第4008460号に
記述されているから、ここではその詳細な説明を
省略する。更新／置換論理３５６は、フイールド
Ｂによつて指定されたコラムにおいて、各ブロツ
クの現置換ステータス３５５を読出す。もしブロ
ツクＡがL2キヤツシユ３００に置かれていなけ
れば（ブロツク・ミス）、このステータスはブロ
ツクＡの空間を作るために置換すべき特定のブロ
ツクを指示する。このコラムにおける更新済みの
ブロツク識別子は、WSHT４００からの使用ビ
ツトがバス４５１を通してライン有効ビツト更新
論理（LVUL）３７０で受取られるまで、アドレ
ス・ゲート回路３５７に記憶される。このように
して有効ビツトを作成されたブロツクＡの新しい
エントリはアドレス・ゲート回路３５８に記憶さ
れ、そこからアドレス入力ゲート回路３５１を経
由してキヤツシユ・デイレクトリ３５０へ送られ
てその内容を更新するのである。従つて、ブロツ
クＡがミスしているか否かに拘わらず、ブロツク
Ａが当該コラムにおける一番最近に使用されたブ
ロツクとなるように、置換アレイが更新されるこ
とになる。

G4 WSHTの詳細な説明（第８図） 第８図には、本発明に従つたWSHT４００が
示されている。その主たる構成要素は、L2キヤ
ツシユ・デイレクトリ３５０に対するインタフエ
ース論理を除けば、第７図に示した該デイレクト
リのそれと実質的に同じである。図示のように、
最近に使用されたブロツクのすべての識別子を保
持するWSHT４００が設けられている。第６図
に示すように、WSHT４００の各エントリは１
つのブロツク識別子を保持し、また当該ブロツク
中の各ラインごとに１つの使用ビツトを保持して
いる。L2キヤツシユ３００のアクセスを行なう
場合、そのアドレスはバス１１０を介して
WSHT４００にも送られる。フイールドB′によ
つて指定されたコラム中のすべてのブロツク識別
子はアドレス比較論理４０５へ同時に読出され、
そこでフイールドA′と比較される。第８図に示
したフイールドＣ、ライン・インジケータ４０３
及びライン位置C′は、第７図に示したものと同じ
である。もし当該コラムにブロツク識別子A′が
置かれており、しかもラインＣの使用ビツトがオ
ンであれば、当該エントリは不変のままに留ま
る。もし当該コラムにブロツク識別子A′が置か
れているが、ラインＣの使用ビツトがオフであれ
ば、ライン・ミスが発生される。もし当該コラム
におけるいずれのブロツク識別子も一致しなけれ
ば、ブロツク・ミスが発生され、そしてその結果
がバス４０７を介して更新／置換論理４２０へ送
られる。この場合、更新／置換論理４２０は、フ
イールドB′によつて指定されたコラムの現置換
ステータスを置換アレイ４１０に読取る。もしブ
ロツクA′のエントリがWSHT４００に置かれて
いなければ（ブロツク・ミス）、更新／置換論理
４２０は置換アレイ４１０の内容に従つて最も長
い間使用されなかつたブロツクのエントリをブロ
ツクA′のエントリと置換し、ブロツクA′のエン
トリにおけるラインＣの有効ビツトをオンに転ず
るとともに、新しく使用されたブロツクA′のエ
ントリをアドレス・ゲート回路４２１へ書込む。
もし当該アクセスがライン・ミスだけを生ぜしめ
るのであれば、更新／置換論理４２０はブロツク
A′のエントリにおけるラインＣの使用ビツトを
オンに転ずるにすぎない。もし同時的なL2キヤ
ツシユ３００のアクセスが該キヤツシユのブロツ
ク・ミスを生ぜしめるならば、L2キヤツシユ・
デイレクトリ３５０中のインタフエース４５０は
このブロツク・ミスをWSHTに通知して、当該
ブロツクの使用ビツトをバス４５１を介してL2
キヤツシユ・デイレクトリ３５０へ送るように指
示する。ライン使用ビツト更新論理（LUUL）４
３０の詳細は以下で説明する。ブロツクA′のエ
ントリ、すなわちブロツク識別子A′及びそのラ
イン・使用ビツトはアドレス・ゲート回路４２２
に記憶され、次いでWSHT４００を更新するた
めにアドレス入力ゲート回路４００へ送られる。
かくて、WSHT４００のブロツク・ミスが存在
するか否かに拘わらず、置換アレイ４１０におけ
るコラムのうちでブロツクA′が一番最近に使用
されたブロツクとなるように、更新動作が行われ
るのである。

G5 ライン有効ビツト更新論理及びライン使用
ビツト更新論理の説明（第９図、第１０図） 第９図は、第７図に概略的に示したライン有効
ビツト更新論理（LVUL）３７０を一層詳細に示
しており、特にライン又はブロツク・ミス発生時
に各ブロツクの有効ビツトがどのようにして更新
されるかを示している。すべてのアドレスは、第
７図のアドレス・ゲート回路３５７から与えられ
る。ライン・ミスが発生する場合、ブロツクＡの
１組の有効ビツトＶはORゲート３７２によつて
ミスしたラインのＣのC′と併合され、その結果が
有効ビツト（V′）バツフア３７３に書込まれる。
L2キヤツシユ３００のブロツク・ミスが生ずる
場合、有効ビツト・バツフア３７３の内容はバス
４５１を介して与えられる使用ビツトＵによつて
重ね書きされる。いずれの場合にも、有効ビツ
ト・バツフア３７３の内容はL2キヤツシユ・デ
イレクトリ３５０のエントリ３７４を形成するた
めにブロツク識別子Ａと併合され、その結果が第
７図のアドレス・ゲート回路３５８へ送られる。

第１０図は、第６図に概略的に示したライン使
用ビツト更新論理（LUUL）４３０を一層詳細に
示しており、特にWSHT４００のライン又はブ
ロツク・ミス発生時に各ブロツクの使用ビツトが
どのように更新されるかを示している。すべての
アドレスは、第８図のアドレス・ゲート回路４２
１から与えられる。まず、ブロツク識別子A′が
WSHT４００に置かれていなければ、その１組
の使用ビツトＵはANDゲート４３２によつてゼ
ロに設定され、その結果が使用ビツト（U′）バ
ツフア４３３に書込まれる。さもなければ、これ
らの使用ビツトＵは直接的に使用ビツト・バツフ
ア４３３へ送られる。次いで、このバツフア４３
３の内容はORゲート４３４によつてアクセス・
ラインのＣのC′と併合され、その結果が他の使用
ビツト（U′）バツフア４３５に書込まれる。も
しブロツクＡがミスしていることを指示する信号
がL2キヤツシユから受取られなければ、使用ビ
ツト・バツフア４３５の内容はブロツク識別子
A′と併合され、その結果が第８図のアドレス・
ゲート回路４２２へ送られる。もしブロツクＡが
L2キヤツシユでミスしているならば、使用ビツ
ト・バツフア４３５中の１組の使用ビツトはバス
４５１を介してL2キヤツシユ・デイレクトリ３
５０中のライン有効ビツト更新論理（LVUL）３
７０へ送られる。ブロツク識別子A′及びC′を併
合することによつてWSHT４００のエントリが
形成され、第８図のアドレス・ゲート回路４２２
へ送られる。

Ｈ 発明の効果 以上詳述したように、本発明によれば、L2キ
ヤツシユ中のブロツクのうち以前に使用されたラ
インの識別子をワーキング・セツト履歴テーブル
に記録するようにしているので、キヤツシユのヒ
ツト率を実質的に改善することができ、ひいては
メイン・メモリとL2キヤツシユの間のトラヒツ
クを実質的に減少させることができる。

【図面の簡単な説明】

第１図は３レベルの階層メモリを備え、第２レ
ベル（L2）のキヤツシユに関連するワーキン
グ・セツト履歴テーブル（WSHT）を有する、
本発明に従つたデータ処理システムを示すブロツ
ク図、第２図は３レベルの階層メモリを備えたデ
ータ処理システムを示すブロツク図、第３図は
L2キヤツシユをアクセスするために使用される
24ビツト・アドレスの様式を示す図、第４図は
WSHTをアクセスするために使用される24ビツ
ト・アドレスの様式を示す図、第５図はL2キヤ
ツシユ・デイレクトリにおけるエントリの様式を
示す図、第６図はWSHTデイレクトリにおける
エントリの様式を示す図、第７図はWSHTとの
インタフエースを備えたL2キヤツシユを示すブ
ロツク図、第８図はWSHT及びL2キヤツシユ・
デイレクトリとのインタフエースを示すブロツク
図、第９図はL2キヤツシユにおけるライン有効
ビツト更新論理を示す図、第１０図はWSHTに
おけるライン使用ビツト更新論理を示す図であ
る。 １００……プロセツサ、２００……第１レベル
（L1）キヤツシユ、２５０……L1キヤツシユ・デ
イレクトリ、３００……第２レベル（L2）キヤ
ツシユ、３５０……L2キヤツシユ・デイレクト
リ、４００……ワーキング・セツト履歴テーブル
（WSHT）、４５０……インタフエース、５００
……メイン・メモリ。

Claims (1)

1. 【特許請求の範囲】 １ プロセツサと３レベルの階層メモリとを備
   え、該階層メモリは第１レベルのキヤツシユ、第
   ２レベルのキヤシユ及び第３レベルのメイン・メ
   モリから成り、該メイン・メモリは複数の情報セ
   ツトを記憶し、前記第２レベルのキヤツシユは各
   情報セツトを構成する複数の情報サブセツトを記
   憶するように編成されているデータ処理システム
   において、 各情報セツトの情報サブセツトが前記第２レベ
   ルのキヤツシユに置かれている間に実際に使用さ
   れたか否かを指示する使用情報を各情報サブセツ
   トごとに記憶するための履歴テーブルを前記メイ
   ン・メモリ及び前記第２レベルのキヤツシユに関
   連して設け、 所与の情報セツトが前記第２レベルのキヤツシ
   ユから前記メイン・メモリへ戻された後に該情報
   セツトを前記第２レベルのキヤツシユへ転送する
   ように要求される場合、該情報セツトが前記第２
   レベルのキヤツシユに置かれている間に使用され
   た特定の情報サブセツトだけを前記メイン・メモ
   リから前記第２レベルのキヤツシユへ転送するよ
   うにしたことを特徴とする、３レベルの階層メモ
   リを備えたデータ処理システム。