JPS6029135B2 - バツフアメモリシステム - Google Patents

Description

【発明の詳細な説明】 本発明は計算機システムにおけるバッファメモリシステ
ムに関する。

計算機システムにおいては、中央処理装置の速度と主記
憶装置の速度との間には大きな隔たりがあり、これが計
算機システムの性能を制限する要因となっている。

これを緩和するために、中央処理装置側に比較的小容量
のバッファメモリを設け中央処理装置から主記憶にアク
セスを行う際に、アクセスすべき語を含む複数語からな
るブロックをバッファメモリに取込んでおき、次にアク
セスを行う際にはこのバッファメモ川こ対してアクセス
を行うことにより実効的に主記憶の高速化が達成できる
ことが知られており、セットアソシアティブ方式と呼ば
れるバッファメモリが一般に採用されている。この方式
においては、主記憶とバッファメモリは複数個のセット
に分割され、バッファメモリはある定められた数のブロ
ックをもつ。

以後、バッファメモリにおけるブロックをコンパーメン
トとよび、セットあたりのバッファメモリのブロック数
をコンパーメント数と呼ぶことにする。主記憶上のブロ
ックは同じセットに属するバッファメモリ上の前記複数
個のコンバートメントのうちのいずれかに格納し得るこ
とになる。この従来方式においては、主記憶上のブロッ
クが格納し得るバッファメモリ上の格納位置に制限があ
り、このため、特定のセットにおいてブロックの直換え
が頻発し、これがバッファメモリの効率を低下させる原
因となっている。

従って、本発明の目的は、必要な情報を高い確率で保持
しようとする効率のよいバッファメモリシステムを安価
に実現することにある。

本発明はある一定数のセットをもつバッファメモリ（以
下これを主バッファメモリと呼ぶ）と、第１のバッファ
メモリの複数セットを１つのセットとする第２のバッフ
ァメモリ（以下これを副バッファメモリと呼ぶ）を設け
、副バッファメモリのブロックを、主バッファメモ川こ
おいてブロックの層換えの頻発しているセットに対して
割当てることにより、主バッファメモリの特定のセット
におけるアクセスの集中を緩和しようとするものである
。

本発明によれば、副バッファメモリにおけるブロックを
対応する主バッファメモリの複数セットのいずれかに必
要に応じて優先的に割当てることにより小量の副バッフ
ァメモリで実効的に主バッファメモリのコンバートメン
ト数を増大させた場合と同様な効果をもたらすことがで
きる。

次に、本発明のバッファメモリシステムについて図面を
用いて説明する。

本発明の第１の実施例を説明する。

本実施例においては、主バッファメモリのセット数は２
５６ コンパーメント数は２、副バッファメモリのセッ
ト数は１２８ コンパーメント数は１に選ばれている。

従って、本実施例においては主バッファメモリの２個の
セットが、副バッファメモリの１個のセットに対応して
いる。即ち、副バッファメモリのあるセットにおけるコ
ンパーメントは、対応する主バッファメモリの２個のセ
ットのうちのいずれか一方に割当てられることになる。
これは、対応する２個のセットのうちのいずれか一方の
セットのコンパーメントの数が主バッフアの２つのコン
バートメントに副バツフアの１つを加えて３になること
を意味する。次に、第１図により本発明の第１の実施例
の構成を説明する。

また、本実施例においては説明の都合上主記憶（図示し
ていない）のりードアドレスは２０ビットからなり、ブ
ロックサイズは４ワードであるとする。従って主バッフ
ァメモリ（図示していない）に対しては、主記憶のワー
ドアドレスは上位から各々８ビットの第１のタグ部、８
ビットの第１のセットアドレス部、２ビットのワードア
ドレス部に分割される。同様に副バッファメモリ（図示
していない）に対しては９ビットの第２のタグ部、７ビ
ットの第２のセットアドレス部、２ビットのワードアド
レス部に分割される。本実施例においては以後第１のセ
ットアドレス部の最上位ビットで０および１をもつセッ
トを各々上位および下位のセットと呼ぶ。主および副バ
ッファメモリに現在格納されているブロックを管理する
ために主および副の監理テーブル４（以下単にテーブル
と呼ぶ）および２が用意される。

前記主および副テーブル４および２は主および副バッフ
ァメモリのセット数に対応して各々２５６ワード、１２
８ワードから構成される。主テーブル４の１ワードは、
主バッファメモリの２つのコンパーメントに対応して第
１および第２の夕グ部４１，４２をもち、各タグ部の値
は各々比較回路５１，５２の一方の入力に対応して印加
されている。前記２個の比較回路５１，５２の一方の入
力にはアドレスレジスターの８ビットのタグ部の値が印
加されている。前記８ビットのタグ部の値は書込みデー
タとして主テーブル４の第１および第２の夕グ部４１，
４２にも印加されている。副テーブル２は、アドレスレ
ジスタ１の７ビットのセットアドレス部でアドレスされ
るメモリで、現在副バッファメモリに格納されているブ
ロックを管理するための９ビットのタグ部２１および主
および副バッファメモリで必要なブロックが見出されな
い場合に必要なブロックを格納すべきバッファアドレス
の格納位置を管理するためのＩＪプレースメント管理部
として、６ビットのりプレースメントフラグ部２２をも
つ。リブレースメントフラグ部２２の第１ビットおよび
第２ビットつまり第１および第２のフラグは、副バッフ
ァメモリのコンバートメントと、主バッファメモリの対
応する２個のセットのうちの上位のセット、すなわち８
ビットの第１のセットビットの最上位ビットが０に対応
するセットの第１および第２のコンバートメントとのア
クセスの古さを示すためのビットである。即ち、第１あ
るいは第２のフラグが０であるということは、墓Ｕ／ゞ
ツフアメモリのコンバートメントが対応する主バッファ
メモリのコンバートメントよりも最近アクセスされた事
を意味する。同様に、第３および第４，第５および第６
のフラグは各々副バッファメモリのコンバートメントと
主バッファメモリの下位のセットの第１および第２のコ
ンバートメントとのアクセスの古さ、主バッファメモリ
の上位および下位のセットの第１コンパーメントと第２
のコンパーメントの古さの関係を示す。第１表に各フラ
グの意味を示す。

第１表 副テーブル２の９ビットのタグ部２１には、アドレスレ
ジスタ１の９ビットの第２のタグ部の値が印加これ副テ
ーブル２のタグ部２１からの議出しデータは比較回路３
に印加されている。

比較回路３の他の入力には、アドレスレジスタ１の第２
のタグ部の値が印加されている。また、副テーフル２の
フラグ部２２は、リプレース制御回路６に接続されてい
る。次に本実施例の動作を説明する。

バッファメモリに対してアクセス要求があると、アクセ
スすべき主記憶アドレスはアドレスレジスタ１に格納さ
れ、この第１および第２のセットアドレス部の値をアド
レスとして主および副テーブル４，２の内容が読出され
、各タグ部４１，４２および２１の値が比較回路５１，
５２，３によりアドレスレジス夕第１および第２のタグ
部の値と比較される。

比較回路５１，５２，３のいずれかで−致が検出された
場合、即ち、主バッファメモリおよび副バッファメモリ
のいずれかのコンバートメントに必要なブロックが取込
まれている場合、一致の検出された比較回路に対応する
バッファメモリのコンバートメントに対してアクセスを
行うとともにリプレース管理部としてのりプレースメン
トフラグ２２を更新する。

即ち、第１の比較回路５１で一致が検出された場合には
、主バッファの第１コンパーメントへのアクセスを意味
する。従ってこれが上位セットの場合には、第１表から
判るように第１フラグおよび第５フラグを各々１および
０にし、このコンバートメントの方が新しいアクセスで
あるように更新し、第１のバッファの第１のコンバート
メントに対してアクセスを行う。同様に、これが下位の
セットの場合には、第３および第６のフラグを各々１お
よび０にする。同機に、第２の比較回路５２で一致が検
出された場合には上位セットの場合には第２および第５
フラグをともに１、下位セットの場合には第４および第
６のフラグをともに１にするとともに第１のバッファの
第２のコンバートメントに対してアクセスを行う。第３
の比較回路３で一致が検出された場合には第１，第２，
第３，第４フラグを共に０にするとともに第２のバッフ
ァに対してアクセスを行う。比較回路３，５１，５２の
いずれにおいても一致が検出されない場合、即ち、バッ
ファメモリに必要な語を含むブロックが存在している場
合（以下これをミスヒットとよぶ）には、新たに必要な
ブロックを主あるいは富ルゞッフアメモリのいずれのコ
ンバートメントに取込むかを決定するためにリプレース
メント制御回路６は次の処理を行う。即ち、第１のセッ
トアドレス部の最上位ビットが１でアクセス要求が上位
セットに対するものである場合には、第１，第２，第５
のフラグが調べられ第１と第２のフラグが共に１の場合
には、主バッファのいずれのコンバートメントよりも副
バッファメモリの方が古いアクセスであることにより副
バッファメモリのコンバートメントがリプレースの対象
と決定される。第１および第２のフラグのいずれか一方
が０の場合には、第５のフラグが０および１の場合に、
各々、主バッファメモリの第２および第１のコンバート
メントがリプレースの対象とされるアクセス要求が下位
セットに対するものである場合にも同様に、第３，第４
，第６のフラグを調べることにより、リプレースすべき
ブロックが決定され、決定されたコンバートメントに対
して要求されるブロックが主記憶からとり込まれる。以
上、本発明の第１の実施例を説明したが、本実施例にお
いては、副バッファメモリのコンバートメントは、主バ
ッファメモリの上位および下位の２個のセットのいずれ
かのセットのブロックを保持でき、副バッファメモリの
コンバートメントと対応する主バッファメモリの上位お
よび下位のセットの各々２個のコンバートメントのアク
セスされた古さおよび主バッファメモリの上位および下
位の各々２個のコンバートメントの相互間の古さが６ビ
ットのりプレースメントフラグにより管理され、バッフ
ァメモリでのミスヒツトに際し、主バッファメモリの対
応する２個のコンバートメントおよび副バッファメモリ
のコンバートメントの古さを調べ、最も長い間アクセス
されなかったコンバートメントをリブレースの対象とし
て定めている。

以上の動作は、制御回路（図示せず）の制御により行わ
れる。

制御回路は、主記憶へのアクセス要求に際して、前述の
動作を行うための管理テーブルの論出し、書込み、リプ
レース制御回路への指令、第１および第２のバッファメ
モリへのアクセスの要求、主記憶へのアクセス要求等の
制御信号を発生する。次に第２図により本発明の第２の
実施例を説明する。

尚、第１図と同じ数字は同一機能を示すものである。

本実施例においては、主バッファメモリのセット数は２
５６で副バッファメモリのセット数１２８の２倍、主バ
ッファメモリのコンバートメント数は２で副バッファメ
モリのコンバートメント数は４であるとする。

また、本実施例においては、副バッファメモリの各セッ
ト毎に対応する主バッファメモリのセットにおけるミス
ヒツトの回数を管理することにより、ミスヒットの多数
回発生するセットに対しては副バッファメモリの多くの
コンバートメントを割当てようとするものである。

従ってこの場合には４個のコンバートメントを持つ副バ
ッファを付加することにより、主バッファメモリのコン
バートメント数が各セットでのミスヒットの発生頻度に
応じて副バッファの使用しうるコンバートメント数が０
から４にでき、その結果１つのセットについて２から６
までの値をとることになる。

本実施例においては、セット内のコンバートメントのリ
ブレースはＦＩＦ○（Ｆｉｒｓｔ一１ｎ−Ｆｉ俺ｔ−○
町ｔ）により行われるとする。

このため本実施例においては、副バッファメモリの管理
テーブル貝０ち、副テーブルとして、副バッファメモリ
４個のコンバートメントに対応した第１から第４の各々
９ビットの夕グ部２０１〜２０４、およびリプレースメ
ント管理部として、第１および第２の各々３ビットのポ
ィン夕部２０５，２０６、第１および第２の各々３ビッ
トの割当て数カウント部２０７，２０８第１および第２
の各々４ビットのミスヒットカウント部２０９，２１０
をもつ。第１および第２のポイント部２０５，２０６は
、各々上位セットおよび下位セットにおいて次にミスヒ
ットが発生したときに新しいブロックを割当てる即ち、
リプレースを行うべきコンバートメントを指定するため
のポインタで、値０および値１は各々主バッファメモリ
の第１および第２コンバートメントを指定し、値２から
５は、上位セットの場合には、副バッファメモリの第１
から第４のコンバートメントを下位セットの場合には、
第４から第１のコンバートメソトを各々指定するものと
する。

第１および第２の割当て数カウント部２０７，２０８は
各々主バッファメモリの上位および下位のセットに現在
割当てられているコンバートメント数を保持するための
もので、値１から値５までをとり副バッファメモリのコ
ンバートメントが０から４個、対応する上位または下位
のセットに割当てられていることを示す。

初期状態としては、上位および下位のセットに副バッフ
ァの４個のコンバートメントのうち、各々２個が割当て
られ、従って第１および第２の割当てカウント部２０７
，２０８は初期値としてともに値３をもつことになる。
第１および第２のミスヒツトカウント部２０９２１川ま
、各々上位セットにおけるミスヒットの回数および上位
、下位セットにおける合計のミスヒツトの回数を保持す
るもので、第２のカウンタがオーバフローした時点、す
なわち、上位および下位における合計のミスヒット回数
が１６回になった時点で上位セットにおけるミスヒツト
の回数を第２のミスヒットカウンタ２川こより調べるこ
とにより、次に上位および下位のセットに割当てるべき
副バッファメモリのコンバートメント数を修正するため
のものである。次に本実施例の動作を説明する。

本実施例においても、第１の実施例と同様に、主記憶へ
のアクセス要求があると、主および副のテーブル４，２
が読出され、必要なワードを含む語が主および副バッフ
ァメモリ上にあるかどうかが検索され、存在する場合、
すなわち、比較回路３０１〜３０４，５１，５２のいず
れかで−致が検出された場合に対応するバッファメモリ
の対応するコンバートメントに対してアクセスが行われ
る。

本実施例ではＦＩＦＯのリプレースメント方式を採用し
ているので、このとき副テーブル２のリプレースメント
管理部２０５〜２１０のいずれも更新されない。必要な
ブロックがバッファメモリ上に存在しないとき、即ち、
比較回路３０１〜３０４，５１，５２のいずれにおいて
も一致が検出されない場合には次の処理が行われる。即
ち、まずアクセスの要求された上位あるいは下位のセッ
トに対応するポィンタ部２０５または２０６が調べられ
、これで指定されるコンバートメントに対してリプレー
スの処理が起動される。即ち、ポィン夕部２０５または
２０６の値が０または１であれば最も早く割当てられた
コンバートメントが主バッファのコンバートメントであ
ることを示し、主バッファメモリの第１または第２のコ
ンバートメントがリプレースの対象となり、２から５の
値をもつ場合は、副バッファがリプレースの対象である
ことを示す。このとき上位のセットの場合には２〜５の
値にそれぞれ対応して副バッファメモリの第１から第４
までの対応するコンバートメントが下位セットの場合に
は、第４から第１までの対応するコンバートメントがリ
プレースの対象となる。これとともに、上位あるいは下
位セットに対応する第１あるいは第２のポィンタ部２０
５あるいは２０６の値がカウントアップされ、対応する
割当て数カウント部２０７あるいは２０８の値と比較さ
れる。これとともに、ミスヒットを起したのが上位セッ
トである場合には、第１および第２のミスヒツトカウン
ト部２０９，２１０の値が下位セットである場合には、
第２のミスヒットカウント部２１０の値のみがカウント
アップされる。第２のカウント部でオーバフローが発生
した場合には、副バッファメモリのコンバートメントの
主バッファメモリ上位および下位のセットへの割当て数
を修正するための後記１）の処理を行う。オーバフロウ
が発生しなかった場合には、ａ）アクセスが要求され上
位あるいは下位のセットに対応するポィンタ部２０５あ
るいは２０６の値がカウントアップされ、対応する割当
て数カウント部２０７あるいは２０８の値を比較され、
前者が後者よりも小さいか、あるいは等しい値をもつ場
合には、カウントアップされた値を、前者が後者よりも
大きい場合には値０をポィンタ部２０５あるいは２０６
にセットする。１ 第２のミスヒットカウント部でオー
バフロウが発生した場合には、第１のミスヒットカゥン
ト部の値が調べられる。

第１のカウンタの上位２ビットがともに０のときには、
即ち、値３以下の値をもつ場合には、上位セットにおけ
るミスヒットが下位におけるミスヒットよりも発生する
頻度がかなり小さいと判断し、これまで上位セットに割
当てられていた副バッファメモリのコンバートメントの
数を少くするために、第１の割当て数のカウントダウン
し、第２の割当て数をカウントアップしテーブルに戻す
。

第１の割当て数がすでに値１をもつ場合にはこのカウン
トアップ、カウントダウンの処理は行わない。

同様に第１のカウンタの上位２ビットがともに１のとき
には、即ち、値１雄〆上をもつ場合には第１の割当て数
をカウントアップし、第２の割当て数をカウントダウン
し、テーブルに戻すことにより、上位セットに対する割
当て数を減少させる。第１の割当て数がすでに値５をも
つ場合にはこれらの動作は行わない。以上１以下の処理
を行った後、第１および第２のミスヒットカウン夕部に
はともに値０が戻される。以上、本発明の第１および第
２の実施例を説明したが、これらの実施例の説明におい
てはリプレースメント制御回路６の具体的構成について
は本発明の直接の主旨ではないので省略してあるが、通
常の論理回路を用いて容易に実現できることは明白であ
ろう。

また本発明主旨に反しない限り、いくつかの変形を行う
ことも可能で、主バッファメモリおよび副バッファメモ
リにおけるセット数、コンバートメント数、副バッファ
メモリの１セットに対応する主バッファメモリのセット
数、あるいは、コンバートメントのリプレースメント方
式、副ブロックメモリの主ブロックへの割当ての方式等
、さまざまな方式が選択できる。

また、本実施例においては、本実施例における動作を実
現するための制御回路（図示せず）についても、これは
従来知られている方法により実現可能であり、この具体
的構成自体は本発明の主旨とは直接関係ないので省略し
てある。

【図面の簡単な説明】

第１図は本発明のバッファメモリシステムの第１の実施
例を示すブロック図、第２図は本発明の第２の実施例を
示すブロック図である。 図において、１はアドレスレジスタ、２は副管理テーフ
ル、３は比較回路、４は主管理テーフル、６はリプレー
スメント制御回路、５１，５２，３０１〜３０４は比較
回路を示す。 オｌ図 オ２図

Claims (1)

【特許請求の範囲】
1. １ 主記憶上のブロツクの一部を保持するセツトアソシ
   アテイブ方式の第１のバツフアメモリと、前記第１のバ
   ツフアメモリの複数セツトを１つのセツトとするセツト
   アソシアテイブ方式の第２のバツフアメモリと、前記第
   １のバツフアメモリに現在格納されているブロツクのア
   ドレスを管理するための第１の管理テーブルと、前記第
   ２のバツフアメモリに現在格納されているブロツクのア
   ドレスを保持するアドレス部および前記第２のバツフア
   メモリおよび前記第１のバツフアメモリの対応する複数
   のセツトに属する各ブロツクのアクセスのされかたに関
   する情報を保持するリプレース情報部をもつ第２の管理
   テーブルと、前記第２の管理テーブルのリプレース情報
   部に接続され、この情報に従い主記憶上のブロツクを第
   １のバツフアメモリあるいは第２のバツフアメモリのい
   ずれのブロツクに割り当てるかを決定するためのリプレ
   ースメント制御回路をもつことを特徴とするバツフアメ
   モリシステム。