JPH10275112A

JPH10275112A - キャッシュメモリシステム

Info

Publication number: JPH10275112A
Application number: JP9081144A
Authority: JP
Inventors: Hideo Mochizuki; 英生望月
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1997-03-31
Filing date: 1997-03-31
Publication date: 1998-10-13
Anticipated expiration: 2017-03-31
Also published as: JP3204295B2

Abstract

(57)【要約】【課題】キャッシュメモリから主記憶装置へのデータ
転送時間を書き戻す必要のあるデータの分布に応じて、
最適化できるキャッシュメモリシステムを提供するこ
と。【解決手段】夫々のキャッシュラインを複数のサブブ
ロックに分割すると共に、サブブロック毎にダーティビ
ットを設けたキャッシュメモリ２０と、主記憶装置５０
に対してキャッシュラインに格納されているデータを書
き戻すためのデータ書戻手段３０を備えたキャッシュメ
モリシステム１０において、データ書戻手段３０は、キ
ャッシュラインに格納されているデータを書き戻す際
に、書き戻すデータサイズと書き戻しに要する時間との
関係を表すテーブルを参照すると共に、ダーティビット
格納部に格納されているダーティビットの内、オンを示
すダーティビットを参照して、書き戻すべきサブブロッ
クの最適な組合わせを決定する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、キャッシュメモリ
に関し、特にライトバック方式を採用したキャッシュメ
モリに関する。

【０００２】

【従来の技術】一般に、この種のキャッシュメモリは、
情報処理システムにおいて、例えば、中央処理装置（以
下、ＣＰＵと呼ぶ。）と主記憶装置の間に設けられ、主
記憶装置からの読出しに伴うＣＰＵへのデータ転送、及
び、ＣＰＵから主記憶装置への書込み動作に伴うデータ
転送によるスループットの低下を補うために用いられて
いる。このようなキャッシュメモリは、情報処理システ
ムにおいて取り扱われる情報が、その性質上、時間的局
所性及び空間的局所性を有していることを利用したもの
である。このような情報処理システムでは、読出し及び
書込みの対象となるデータがキャッシュメモリ内に存在
する場合には、当該データの読出し及び書込みは、ＣＰ
Ｕとキャッシュメモリとの間で迅速に行われ、対象とな
るデータがキャッシュメモリ内に存在しない場合だけ、
ＣＰＵは主記憶装置に格納されているデータをアクセス
する。この構成では、主記憶装置に格納されているデー
タ対するＣＰＵからのアクセスを減少させることがで
き、これによって、情報処理システム全体のスループッ
トを向上させることができる。

【０００３】ここで、キャッシュメモリの対するＣＰＵ
からの書込み動作によって、キャッシュメモリ内のデー
タが書き換えられた場合、キャッシュメモリ内のデータ
と主記憶装置内の対応するデータとが一貫性をなくして
しまう。このようにデータに一貫性がないことは好まし
くないため、内容の書き換えられたキャッシュメモリ内
のデータは、主記憶装置に書き戻され、キャッシュメモ
リ内のデータと主記憶装置内のデータとの不一致が解消
するように、制御されている。一方、ＣＰＵからキャッ
シュメモリに対するリード要求やライト要求がなされた
際、対象となるデータがキャッシュメモリ内に存在しな
い場合、ＣＰＵは、主記憶装置から対象となるデータを
読み出すと共に、当該データをキャッシュメモリ内に転
送するように要求する。

【０００４】尚、キャッシュメモリは、アドレス変換を
高速に行い、対象となるデータのアドレスがキャッシュ
メモリ内に格納されているか否かを検出するＴＬＢ（Ｔ
ｒａｎｓｌａｔｉｏｎＬｏｏｋａｓｉｄｅＢｕｆｆ
ｅｒ）部分と、データを格納するデータキャッシュとを
備えており、ＴＬＢは、本発明とは直接、関係がないた
め、以下では、データキャッシュをキャッシュメモリと
呼ぶ。

【０００５】従来、この種のキャッシュメモリには、デ
ータ格納領域を複数のキャッシュラインと呼ばれる部分
領域に区分し、各キャッシュライン毎に、ダーティビッ
トと呼ばれるフラグを設け、主記憶装置に書き戻す必要
があるデータを格納しているキャッシュラインに対して
は、ダーティビットをオンにするように、構成されたも
のがある。このようなキャッシュメモリでは、ダーティ
ビットがオンであるキャッシュラインのデータを、当該
キャッシュラインのデータが置き換え対象になった際
に、主記憶装置に対して書き戻すことにより、キャッシ
ュメモリと主記憶装置との間のデータの不一致を防ぐこ
とができる。このように、キャッシュメモリに格納され
ているデータと主記憶装置に格納されているデータとの
一貫性を保持する方式をライトバック方式と呼ぶ。

【０００６】ところで、ＣＰＵにおける処理能力の増大
や、下位レベルとのデータ転送速度のギャップの増大と
共に、キャッシュメモリのメモリ容量も増加する傾向に
あり、各キャッシュラインに格納されるデータも、ミス
率を低下させるために、例えば、３２バイト或いは６４
バイトと増加している。しかし、このようにキャッシュ
ラインに格納されるデータのサイズを大きくすると、一
旦ミスが生じてしまった場合、例えば、単一のキャッシ
ュラインにおける１バイトのデータだけを書き戻すため
に、１キャッシュライン全体のデータを主記憶装置に書
き戻す時間は、１バイトのデータを書き戻す時間に比較
して長くなってしまう。即ち、キャッシュラインサイズ
を大きくすると、ミス率が低下する一方で、ミスした場
合におけるミスペナルティが増大することになる。

【０００７】従来、キャッシュメモリのデータ格納領域
をキャッシュラインに区分すると共に、各キャッシュラ
インを更にサブブロックに分けておき、各キャッシュラ
インの一部しか書き戻す必要がない場合には、書き戻す
べきサブブロックだけを書き戻し、残りのサブブロック
を書き戻さない形式のキャッシュメモリが提案されてい
る（特開平４−１９５５６３号公報（以下、従来例１と
呼ぶ）、及び、特開平５−２８２２０８号公報（以下、
従来例２と呼ぶ）参照）。更に言えば、上記した従来例
１及び従来例２には、いずれも、サブブロック毎にダー
ティビットを設けておき、キャッシュラインより小さい
サブブロックを単位として、或いは、対象となるサブブ
ロックを含むサブブロックグループ毎に、主記憶装置に
書き戻す形式のキャッシュメモリが開示されており、こ
れによって、無駄なデータ転送によるスループットの低
下を防止できることとしている。

【０００８】

【発明が解決しようとする課題】しかしながら、引用例
１及び２は、キャッシュメモリの有する各キャッシュラ
イン内において、複数のサブブロックに対応するダーテ
ィビットがオンである場合における問題点について、何
等、指摘していない。即ち、各キャッシュライン内に、
対応するダーティビットがオンであるサブブロックが分
散、或いは、点在している場合、ダーティビットがオン
である各サブブロック毎に、或いは、各サブブロックを
含むサブブロックグループ毎に、主記憶装置に対して書
き戻しを行うと、書き戻すサブブロックの数によって
は、キャッシュラインごと書き戻しを行った方が、デー
タ転送時間を短縮できることがある。このような場合に
ついて、従来例１及び従来例２は、何等、考慮していな
いため、書き戻すべき最適なデータに関して開示してい
るとは言えない。換言すれば、従来例１及び従来例２
は、書き戻すべきデータのサイズと、書き戻しに要する
所要時間との関係について、全く考慮していない。

【０００９】本発明の目的は、データのサイズ、即ち、
サブブロックの数に応じて、適応的に最適なデータ転送
時間を得ることができるキャッシュメモリを提供するこ
とである。

【００１０】本発明の他の目的は、キャッシュメモリか
ら主記憶装置へのデータ転送時間をデータサイズに応じ
て、最適化できるキャッシュメモリシステムを提供する
ことである。

【００１１】本発明の更に他の目的は、書き戻すべきサ
ブブロックの分布、及びデータサイズと書戻所要時間と
の関係を利用して、キャッシュメモリから主記憶装置へ
最適なサイズを有するデータを求める方法を提供するこ
とである。

【００１２】

【課題を解決するための手段】本発明によれば、予め定
められた量のデータをそれぞれ格納する複数のキャッシ
ュライン、及び該複数のキャッシュラインのそれぞれに
対応した複数のダーティビット格納部を有するキャッシ
ュメモリと、当該キャッシュメモリからみて下位レベル
の記憶領域に対して前記キャッシュラインに格納されて
いるデータを書き戻すためのデータ書戻手段とを備えた
キャッシュメモリシステムにおいて、書き戻すデータサ
イズと書き戻しに要する時間との関係を表すテーブルを
更に備えており、前記キャッシュメモリは、前記複数の
キャッシュラインの夫々が所定数のサブブロックに分割
されていると共に、前記各ダーティビット格納部が、夫
々、対応するキャッシュラインにおけるサブブロックに
対応したダーティビットを格納するものであり、前記デ
ータ書戻手段は、特定の前記キャッシュラインに格納さ
れているデータを書き戻す際に、前記テーブルを参照す
ると共に、前記特定のキャッシュラインに対応する前記
ダーティビット格納部に格納されているダーティビット
の内、オンを示すダーティビットを参照して、書き戻す
べき前記サブブロックの最適な組合わせを決定し、当該
最適な組合わせを構成する前記サブブロックに格納され
ているデータを前記下位レベルの記憶領域に対して書き
戻すことを特徴とするキャッシュメモリシステムが得ら
れる。

【００１３】また、本発明によれば、前記キャッシュメ
モリシステムにおいて、前記キャッシュメモリは、前記
複数のキャッシュラインの夫々に対応するタグを格納す
るための複数のタグフィールドを備えていることを特徴
とするキャッシュメモリシステムが得られる。

【００１４】また、本発明によれば、前記キャッシュメ
モリシステムにおいて、前記データ書戻手段は、前記特
定のキャッシュラインに格納されているデータを、前記
下位レベルの記憶領域に書き戻す際に、前記テーブルを
参照すると共に、該特定のキャッシュラインに対応する
前記タグフィールドに格納されている前記タグである特
定のタグと、前記特定のキャッシュラインに対応する前
記ダーティビット格納部に格納されている前記ダーティ
ビットである特定のダーティビットとを参照して、前記
最適な組合わせを構成する前記サブブロックのデータに
関し、データサイズ及び前記特定のキャッシュラインに
おけるアドレスを生成するためのライトバックサイズ／
アドレス生成部と、前記特定のキャッシュラインに格納
されているデータを前記下位レベルの記憶領域に書き戻
す際に、前記テーブルを参照すると共に、前記特定のタ
グ及び前記特定のダーティビットを参照して、前記最適
な組合わせを構成する前記サブブロックのデータとして
のライトバックデータを生成するためのライトバックデ
ータ生成部と、前記ライトバックサイズ／アドレス生成
部の生成した前記データサイズ及び前記特定のキャッシ
ュラインにおけるアドレス、並びに前記ライトバックデ
ータ生成部の生成した前記ライトバックデータを一時的
に格納するためのライトバッファと、該ライトバッファ
の状態を監視すると共に、前記下位レベルの記憶領域に
対して、前記ライトバッファに一時的に格納される前記
データサイズ、前記アドレス及び前記ライトバックデー
タを書き戻す制御を行うためのライトバック制御部とを
備えていることを特徴とするキャッシュメモリシステム
が得られる。

【００１５】また、本発明によれば、前記キャッシュメ
モリシステムにおいて、前記キャッシュメモリの上位レ
ベルから前記キャッシュメモリに対する要求に含まれる
アドレスと同内容のアドレスを受けて、前記下位レベル
の記憶領域に対して前記要求に対応するデータ要求を行
うと共に、前記下位レベルの記憶領域から当該データ要
求に対応するデータを受けて、該データを前記キャッシ
ュメモリに対して送出するためのリード制御部を更に備
えていることを特徴とするキャッシュメモリシステムが
得られる。

【００１６】更に、本発明によれば、前記キャッシュメ
モリシステムにおいて、前記ライトバック制御部は、前
記ライトバックデータ、当該ライトバックデータのサイ
ズである前記データサイズ及び前記アドレスが前記ライ
トバッファに揃ったことを示すライトバッファ状態信号
を前記リード制御部に対して送出すると共に、前記リー
ド制御部からのデータ転送終了信号を受けて、前記ライ
トバッファに揃っている前記ライトバックデータ、前記
データサイズ及び前記アドレスを前記下位レベルの記憶
領域に対して書き戻すためのものであり、前記リード制
御部は、前記ライトバッファ状態信号を受けた後に、前
記下位レベルの記憶領域から受けた前記データ要求に対
応するデータを前記キャッシュメモリに対して転送する
と共に、当該転送が終了したことを示すデータ転送終了
信号を前記ライトバック制御部に対して送出するための
ものであることを特徴とするキャッシュメモリシステム
が得られる。

【００１７】また、本発明によれば、データ格納領域と
して複数のキャッシュラインを有するキャッシュメモリ
であって、キャッシュラインを複数のサブブロックに分
割し、前記各サブブロックに対応する複数のダーティビ
ットを備えることとしたキャッシュメモリにおいて、前
記キャッシュラインに格納されているデータを当該キャ
ッシュメモリから見て下位レベルの記憶領域に対して書
き戻す必要が生じた場合における最適な書戻データサイ
ズを求める方法であって、データサイズと書き戻しに要
する時間との関係に基づいて、オンを示す前記ダーティ
ビットに対応する前記サブブロックと、該サブブロック
に隣接するサブブロックとをまとめて前記下位レベルの
記憶領域に対して書き戻すべきかどうかを判断し、前記
複数のダーティビットの内、オンを示すダーティビット
の分布に従って、更に必要に応じて、書き戻すべきと判
断した複数の前記サブブロックからなる書戻データブロ
ックと、当該書戻データブロックと同じデータサイズの
データブロックであって、該書き戻しデータブロックに
隣接するデータブロックとをまとめて前記下位レベルの
記憶領域に対して書き戻すべきかどうかを判断すること
により、最適な書戻データサイズを求める方法が得られ
る。

【００１８】

【発明の実施の形態】以下に、本発明の実施の形態のキ
ャッシュメモリ及びキャッシュメモリシステムについて
図面を用いて説明する。

【００１９】本実施の形態のキャッシュメモリは、図１
に示されるように、データ格納部ＤＭとしての第１乃至
第ｎのキャッシュラインＣＬ１〜ＣＬ（ｎ）と、それに
対応した第１乃至第ｎのタグフィールドＴＦ１〜ＴＦ
（ｎ）及び第１乃至第ｎのダーティビット格納部ＤＢＭ
１〜ＤＢＭ（ｎ）とを備えている。

【００２０】第１乃至第ｎのキャッシュラインＣＬ１〜
ＣＬ（ｎ）の夫々は、所定量のデータを格納することが
できるものである。以下、このキャッシュラインの格納
することができるデータサイズをキャッシュラインサイ
ズという。また、本実施の形態において、第１乃至第ｎ
のキャッシュラインＣＬ１〜ＣＬ（ｎ）は、夫々、ｎ個
（図１においては４個の場合が示されている。）のサブ
ブロックの集まりとして認識される。例えば、図１にお
いては、第１のキャッシュラインは、第１乃至第４のサ
ブブロックＳＢ１〜ＳＢ４の集まりとして認識される。
また、夫々のサブブロックＳＢ１〜ＳＢ４は、第２の所
定量のデータを格納することができるものである。ここ
で、第２の所定量は、キャッシュラインサイズをサブブ
ロックの個数ｎで分割したものである。以下、この第２
の所定量、即ちサブブロックの格納することができるデ
ータサイズをサブブロックデータサイズという。例え
ば、キャッシュラインサイズを３２バイトとし、サブブ
ロックの個数ｎを３２個とすると、サブブロックデータ
サイズは、１バイト（８ビット）ということになる。
尚、キャッシュメモリの分野において、データ転送の最
小単位を意味するブロックという概念があるが、サブブ
ロックとは、このブロックに限られるものではなく、あ
くまでも上述した定義に従うものである。

【００２１】第１乃至第ｎのタグフィールドＴＦ１〜Ｔ
Ｆ（ｎ）は、タグを格納するためのものである。ここ
で、タグとは、夫々、第１乃至第ｎのキャッシュライン
ＣＬ１〜ＣＬ（ｎ）の内の対応するキャッシュライン内
に、求める語が格納されているか否かを判別するための
情報である。

【００２２】第１乃至第ｎのダーティビット格納部ＤＢ
Ｍ１〜ＤＢＭ（ｎ）は、夫々、ｎ個（図１においては一
例として４個の場合が示されている。）のダーティビッ
トを格納するためのものである。第１乃至第ｎのダーテ
ィビット格納部ＤＢＭ１〜ＤＢＭ（ｎ）におけるｎ個の
ダーティビットは、夫々、第１乃至第ｎのキャッシュラ
インＣＬ１〜ＣＬ（ｎ）におけるｎ個のサブブロックの
いずれかに対応する。例えば、図１において、第２のダ
ーティビット格納部ＤＢＭ２に格納される第１のダーテ
ィビットＤＢ１は、第２のキャッシュラインＣＬ２にお
ける第１のサブブロックＳＢ１に対応し、第ｎ−３のダ
ーティビット格納部ＤＢＭ（ｎ−３）に格納される第４
のダーティビットＤＢ４は、第ｎ−３のキャッシュライ
ンＣＬ（ｎ−３）における第４のサブブロックＳＢ４に
対応する。尚、ダーティビットとは、キャッシュライン
内に格納されているデータを他のデータに置き換える際
に、現在格納されているデータを下位レベルに書き戻す
か否かを判定するためのビットであり、例えば、ダーテ
ィビットがオンになっていれば、当該キャッシュライン
に格納されているデータをライトバックする。特に本実
施の形態においては、ダーティビットがサブブロックに
対応しているため、あるダーティビットがオンになって
いれば、対応するサブブロックとして格納されているデ
ータは、下位レベルの記憶領域に対してライトバックす
る必要があるものであると判定することができる。

【００２３】本実施の形態のキャッシュメモリシステム
１０は、図２に示されるように、上述したキャッシュメ
モリ２０と、以下に詳述するデータ書戻手段３０とを備
えている。尚、本実施の形態においては、ＣＰＵ４０と
主記憶装置５０との間に設けられるキャッシュメモリシ
ステム１０を例にとり説明する。しかしながら、情報処
理装置における記憶部は、速度及び容量の異なる複数レ
ベルのメモリを備えるのが一般的である。ここで、複数
レベルのメモリからなる記憶階層において、情報処理装
置の有するＣＰＵに近いレベルを上位レベルといい、Ｃ
ＰＵから遠いレベルを下位レベルというものと定義する
と、本発明のキャッシュメモリシステムは、少なくとも
下位レベルの記憶領域が存在するようなレベルに配置さ
れていれば良い。上述の定義に従えば、本実施の形態に
おいて、キャッシュメモリからみて下位レベルの記憶領
域は、主記憶装置５０に相当する。

【００２４】データ書戻手段３０は、キャッシュライン
に格納されているデータを主記憶装置５０対して書き戻
すためのものである。特に本実施の形態においては、デ
ータ書戻手段３０は、例えば、第３のキャッシュライン
ＣＬ３に格納されているデータを主記憶装置５０に対し
て書き戻す必要が生じた場合に、以下のようにして処理
を行うものである。即ち、図１を例にとると、第３のキ
ャッシュラインＣＬ３に対応する第３のダーティビット
格納部ＤＢＭ３に格納されている４個のダーティビット
を参照して、第３のキャッシュラインＣＬ３の備える第
１乃至第４のサブブロックＳＢ１〜ＳＢ４の内、書き戻
すべきサブブロックの最適な組合わせを決定し、その決
定に従って、最適な組合わせを構成するサブブロックに
格納されているデータを主記憶装置５０に対して書き戻
すためのものである。

【００２５】ここで、最適な組合わせを構成するサブブ
ロックの夫々は、後述するように、種々のデータサイズ
のデータを主記憶装置５０に書き戻す際に必要となる書
戻所要時間と当該データサイズとの関係に従って、最も
書戻所要時間が短くなるようにして決定されるため、ダ
ーティビットがオンになっているサブブロックのみに限
られる訳ではない。即ち、書き戻すべきサブブロックの
最適な組合わせは、ダーティビットがオンであるサブブ
ロックのみからなる場合もある一方で、ダーティビット
がオンであるサブブロックとダーティビットがオフであ
るサブブロックとの組合わせからなる場合もあり、この
点において、前述の従来例１と異なる。また、書き戻す
べきサブブロックの最適な組合わせは、連続した任意の
数のサブブロックの集まりと、それとはデータサイズの
異なる連続した任意の数のサブブロックの集まりとの組
合わせからなる場合もあり、この点において前述の従来
例２と異なる。尚、後の説明における用語として、「書
戻サブブロック」という語句を用いているため、これま
での説明における「書き戻すべきサブブロック」と「書
戻サブブロック」とについて、相互に混同しないように
注意を要する。

【００２６】本実施の形態におけるデータ書戻手段３０
は、図３に示されるように、ライトバックサイズ／アド
レス生成部３０１と、ライトバックデータ生成部３０２
と、ライトバッファ３０３と、ライトバック制御部３０
４と、リード制御部３０５とを備えている。

【００２７】ライトバックサイズ／アドレス生成部３０
１は、主記憶装置５０に対して書き戻すべきキャッシュ
ラインに関して、そのキャッシュラインに対応するタグ
フィールドＴＦに格納されているタグ及び対応するダー
ティビット格納部ＤＢＭに格納されている所定数個のダ
ーティビットＤＢを参照し、データサイズと書戻所要時
間との関係をあらわすテーブルに従って、書き戻すべき
サブブロックの最適な組合わせを判断し、当該最適な組
合わせに関するデータサイズ及びキャッシュラインにお
けるアドレス情報をライトバッファ３０３に対して送出
するためのものである。尚、データサイズと当該データ
サイズに係る書戻所要時間との関係を示すテーブルは、
ライトバックサイズ／アドレス生成部３０１が備えてい
ても良いし、キャッシュメモリ２０が備えているものと
しても良いし、更には、別個に設けられた記憶手段に記
憶しておくこととしても良い。但し、ライトバックサイ
ズ／アドレス生成部３０１が書き戻すべきサブブロック
の最適な組合わせを判断する際に、テーブルは、ライト
バックサイズ／アドレス生成部３０１が参照可能である
ことが必要とされる。

【００２８】ライトバックデータ生成部３０２は、ライ
トバックサイズ／アドレス生成部３０１と同様にして、
データサイズと書戻所要時間との関係をあらわすテーブ
ルに従い、書き戻すべきサブブロックの最適な組合わせ
を判断し、当該最適な組合わせに係るデータであるライ
トバックデータをライトバッファ３０３に対して送出す
るためのものである。尚、ライトバックデータ生成部３
０２においてもライトバックサイズ／アドレス生成部３
０１と同様に、ライトバックデータ生成部３０２が書き
戻すべきサブブロックの最適な組合わせを判断する際
に、テーブルは、ライトバックデータ生成部３０２が参
照可能であることが必要とされる。

【００２９】ライトバッファ３０３は、ライトバックサ
イズ／アドレス生成部３０１の生成した書き戻すデータ
サイズ及びアドレス情報と、ライトバックデータ生成部
３０２の生成したライトバックデータとを受けて、それ
らを一時的に格納するためのものである。

【００３０】ライトバック制御部３０４は、ライトバッ
ファ３０３の状態を監視すると共に、書き戻すデータサ
イズ及びアドレス、並びにライトバックデータがライト
バッファ３０３に揃ったことを示すライトバッファ状態
信号をリード制御部３０５に対して送出するためのもの
である。また、ライトバック制御部３０４は、リード制
御部３０５からのデータ転送終了信号を受けて、ライト
バッファ３０３に揃っている書き戻すデータサイズ及び
アドレス、並びにライトバックデータを主記憶装置５０
に対して書き戻す制御を行うためのものである。

【００３１】リード制御部３０５は、ＣＰＵ４０からキ
ャッシュメモリ２０に対して送出されたアドレスと同内
容のアドレスを受けて、主記憶装置５０に対してアドレ
ス及び必要とするデータサイズとを送出すると共に、そ
のアドレス及びデータサイズに対応するデータを主記憶
装置５０から受けて、更にライトバック制御部３０４か
らのライトバッファ状態信号を受けるのを待って、主記
憶装置５０から受けたデータをキャッシュメモリ２０に
おける該当するキャッシュラインに対して書き込むため
のものである。また、リード制御部３０５は、主記憶装
置５０から受けたデータのキャッシュメモリ２０に対す
る書き込みを終了すると、そのデータ転送が終了したこ
とを示すデータ転送終了信号をライトバック制御部３０
４に対して送出するためのものである。

【００３２】このような構成を備えたキャッシュメモリ
システム１０の動作について、ＣＰＵ４０及び主記憶装
置５０の動作と共に以下に説明する。尚、以下において
は、ＣＰＵ４０からキャッシュメモリ２０に対しリード
要求がなされた場合と、ライト要求がなされた場合とに
別けて説明することとする。

【００３３】まず、リード要求がなされた場合について
説明する。

【００３４】ＣＰＵ４０は、リード要求をする場合、キ
ャッシュメモリ２０に対してアドレスを送出してデータ
を要求する。

【００３５】キャッシュメモリ２０は、ＣＰＵ４０から
の要求がミスかヒットかを判定して、その判定の結果を
ＣＰＵに対して返す。キャッシュメモリ２０は、要求が
ヒットした場合、要求されたデータをＣＰＵ４０に対し
て送出する。一方、要求がミスした場合、いずれかのキ
ャッシュラインに格納されているデータを置き換えなけ
ればならない。ここで、ダイレクトマップ方式において
は、ＣＰＵ４０から受けたアドレスとキャッシュメモリ
２０におけるキャッシュラインとが一意に対応している
ため、データを置き換えなければならないキャッシュラ
イン、即ち更新すべきキャッシュラインも一意に決まる
ことになる。しかしながら、セット・アソシアティブ方
式やフル・アソシアティブ方式においては、置き換え対
象となるキャッシュラインをアドレスから一意に決定す
ることができない。従って、セット・アソシアティブ方
式やフル・アソシアティブ方式のキャッシュメモリ２０
においては、要求がミスした場合、更新すべきキャッシ
ュラインを求めることが必要となる。

【００３６】更に、キャッシュメモリ２０は、更新すべ
きキャッシュラインに対応するダーティビット格納部Ｄ
ＢＭに格納されている所定数個のダーティビットＤＢ
を、ライトバック制御部３０４、ライトバックサイズ／
アドレス生成部３０１及びライトバックデータ生成部３
０２に対して送出する。

【００３７】ＣＰＵ４０は、キャッシュメモリ２０から
の判定結果を受けて、判定結果がヒットを示している場
合、更に要求したデータを受けることになる。一方、判
定結果がミスを示している場合、リード制御部３０５に
対して必要なデータに係るアドレスを送出することによ
り、主記憶装置５０に対する当該必要なデータの要求を
行う。また、主記憶装置５０は、要求されたデータをリ
ード制御部３０５に対して送出する。

【００３８】ライトバックアドレス／サイズ生成部３０
１は、キャッシュメモリ２０から受けた更新すべきキャ
ッシュラインに対応する所定数個のダーティビットに従
い、当該キャッシュラインに格納されているデータを書
き戻す必要がある場合に、データサイズと書戻所要時間
との関係に基づいて、どのように書き戻すのが最適であ
るかを判断し、ライトバッファ３０３に対して当該判断
に基づいたデータサイズ及びアドレス情報を送出する。

【００３９】一方、ライトバックデータ生成部３０２
は、ライトバックアドレス／サイズ生成部３０１と同様
にして、キャッシュメモリ２０からのダーティビットに
従ってどのように書き戻すのが最適であるかを判断し、
ライトバッファ３０３に対して当該判断に基づいたライ
トバックデータを送出する。

【００４０】ライトバック制御部３０４は、ライトバッ
ファ３０３の状態を監視して、ライトバックデータ、ラ
イトバックデータに関するデータサイズ及びアドレス情
報がライトバッファ３０３に揃うと、リード制御部３０
５に対し、ライトバッファ状態信号を送出する。

【００４１】リード制御部３０５は、ライトバッファ状
態信号を受けて、その後に、主記憶装置５０から受けた
データをキャッシュメモリ２０を介してＣＰＵ４０に対
して転送する。更に、リード制御部３０５は、当該転送
が終了した後、ライトバック制御部３０４に対してデー
タ転送終了信号を送出する。

【００４２】ライトバック制御部３０４は、リード制御
部３０５からのデータ転送終了信号を受けて、ライトバ
ッファ３０３に一時的に格納されているライトバックデ
ータと、ライトバックデータに関するデータサイズ及び
アドレス情報とを主記憶装置５０に対し、順番に送出す
ることにより、ライトバックデータの書き戻しを行う。

【００４３】次に、ライト要求がなされた場合について
説明する。

【００４４】ＣＰＵ４０は、ライト要求をする場合、キ
ャッシュメモリ２０に対してアドレス及びデータを送出
する。

【００４５】キャッシュメモリ２０は、ＣＰＵ４０から
の要求がミスかヒットかを判定して、その判定の結果を
ＣＰＵに対して返す。ここで、要求がヒットすると、Ｃ
ＰＵ４０からのデータが、キャッシュメモリ２０におい
て要求に対応するキャッシュラインに対して書き込まれ
ることになる。キャッシュメモリ２０は、要求がヒット
した場合、データを書き込んだキャッシュラインに対応
するダーティビット格納部に対してダーティビットをセ
ットする。特に、本実施の形態においては、サブブロッ
クごとに対応するダーティビットを備えているため、デ
ータ変更のあったサブブロック毎に夫々ダーティビット
をセットする。一方、要求がミスした場合、いずれかの
キャッシュラインに格納されているデータを置き換えな
ければならない。その場合、キャッシュメモリ２０は、
上述したリード要求の場合と同様に、必要があれば、更
新すべきキャッシュラインを求める。更に、キャッシュ
メモリ２０は、更新すべきキャッシュラインに対応する
ダーティビット格納部ＤＢＭに格納されている所定数個
のダーティビットＤＢを、ライトバック制御部３０４、
ライトバックサイズ／アドレス生成部３０１及びライト
バックデータ生成部３０２に対して送出する。

【００４６】ＣＰＵ４０は、キャッシュメモリ２０から
の判定結果を受けて、判定結果がミスを示している場
合、リード制御部３０５に対して書き込み対象となるデ
ータに係るアドレスを送出することにより、主記憶装置
５０に対する当該データの要求を行う。また、主記憶装
置５０は、要求されたデータをリード制御部３０５に対
して送出する。

【００４７】ライトバックアドレス／サイズ生成部３０
１は、キャッシュメモリ２０から受けた更新すべきキャ
ッシュラインに対応する所定数個のダーティビットに従
い、当該キャッシュラインに格納されているデータを書
き戻す必要がある場合に、データサイズと書戻所要時間
との関係に基づいて、どのように書き戻すのが最適であ
るかを判断し、ライトバッファ３０３に対して当該判断
に基づいたデータサイズ及びアドレス情報を送出する。

【００４８】一方、ライトバックデータ生成部３０２
は、ライトバックアドレス／サイズ生成部３０１と同様
にして、キャッシュメモリ２０からのダーティビットに
従ってどのように書き戻すのが最適であるかを判断し、
ライトバッファ３０３に対して当該判断に基づいたライ
トバックデータを送出する。

【００４９】ライトバック制御部３０４は、ライトバッ
ファ３０３の状態を監視して、ライトバックデータ、ラ
イトバックデータに関するデータサイズ及びアドレス情
報がライトバッファ３０３に揃うと、リード制御部３０
５に対し、ライトバッファ状態信号を送出する。

【００５０】リード制御部３０５は、ライトバッファ状
態信号を受けて、その後に、主記憶装置５０から受けた
データを、キャッシュメモリ２０における更新するべき
キャッシュラインに対して転送し、次いで、当該キャッ
シュラインに対するＣＰＵ４０からのデータ書き込みが
行われる。更に、リード制御部３０５は、当該データ転
送等が終了した後、ライトバック制御部３０４に対して
データ転送終了信号を送出する。

【００５１】ライトバック制御部３０４は、リード制御
部３０５からのデータ転送終了信号を受けて、ライトバ
ッファ３０３に一時的に格納されているライトバックデ
ータと、ライトバックデータに関するデータサイズ及び
アドレス情報とを主記憶装置５０に対し、順番に送出す
ることにより、ライトバックデータの書き戻しを行う。

【００５２】以上が、本実施の形態において、ＣＰＵ４
０からリード要求及びライト要求がなされた場合の一連
の処理動作である。

【００５３】次に、ライトバックサイズ／アドレス生成
部３０１及びライトバックデータ生成部３０２におい
て、書き戻すべきサブブロックの最適な組合わせを判断
する際の処理等について、図４乃至図９を用い具体的な
例を挙げて説明する。尚、以下の処理動作例において、
キャッシュラインサイズは、３２バイトとし、初期のサ
ブブロックのサブブロックサイズは、１バイトとする。
従って、初期においてサブブロックの個数は、３２個と
なる。ここで、処理動作中においてサブブロックのサイ
ズは、後述するように変化する。従って、初期のサブブ
ロックについて、以降の処理におけるサブブロックと区
別する必要がある場合、当該初期のサブブロックを初期
サブブロックと呼ぶ。また、これに併せて、初期サブブ
ロックのデータサイズを初期サブブロックデータサイズ
と呼び、初期サブブロックの個数を初期サブブロック数
と呼ぶ。

【００５４】また、前述の通り、本実施の形態において
書き戻すべきサブブロックの最適な組合わせを判断する
にあたっては、データサイズとそのサイズのデータを書
き戻すために必要とする書戻所要時間との関係を示すテ
ーブルが必要となる。以下の処理においては、そのテー
ブルの具体例として、図４に示されるものを用いて説明
することとする。尚、図４における左欄は、各データサ
イズを示すものであり、単位はバイトである。また、図
４における右欄は、左欄に示される各データサイズに対
応する各書戻所要時間であり、ｔは、３０ｎｓである。
このテーブルにおける右欄は、クロック数等であっても
良く、例えば、図４において１クロックが３０ｎｓであ
るならば、右欄における夫々の値は、上から順に４、
４、５、７、１１、２２となる。

【００５５】尚、図５及び図９は、夫々の具体例におい
て、書き戻すべきサブブロックの最適な組合わせを求め
る過程を示す図である。また、図６乃至図８は、最適な
組合わせを求める処理動作を示すフローチャートであ
る。

【００５６】まず、図６に示されるように、サブブロッ
クデータサイズ、サブブロック数、キャッシュラインサ
イズの各初期値を設定すると共に、現在データサイズと
して、サブブロックデータサイズを設定する（ステップ
Ｓ１０１）。ここで、サブブロックデータサイズ、サブ
ブロック数は、前述の定義に従えば、初期サブブロック
データサイズ、初期サブブロック数であり、夫々、本処
理例においては、１バイト、３２個である。また、キャ
ッシュラインサイズは、３２バイトである。更に、現在
データサイズは、初期サブブロックデータサイズと同じ
であるので、１バイトである。

【００５７】次に、キャッシュメモリ２０から送出され
てきたダーティビットＤＢに従って、書戻サブブロック
を決定する（ステップＳ１０２）。詳しくは、対応する
ダーティビットがオンであるサブブロックを書戻サブブ
ロックとする。尚、図５（ａ）において、書戻サブブロ
ックは、黒く塗りつぶされて示されている。

【００５８】次に、書戻データブロックとして書戻サブ
ブロックに格納されているデータを記憶する（ステップ
Ｓ１０３）。書戻データブロックとは、判断過程におい
て実際に書き戻すべきと判断したデータサイズを有する
データブロックであり、処理過程においてそのデータサ
イズが変化することがあるものである。また、書戻サブ
ブロックとは、夫々の判断過程におけるサブブロックの
内、書戻データブロックを含むサブブロックをいう。従
って、図５（ａ）に示される初期の段階においては、書
戻サブブロックと書戻データブロックとは、一致してい
る。

【００５９】次に、隣り合うサブブロックをサブブロッ
クペアとして、サブブロック数の半分の個数のサブブロ
ックペアを決定する（ステップＳ１０４）。例えば、図
５（ａ）においては、最下位に位置するサブブロックＳ
Ｂ１と、その上位（隣）に位置するサブブロックＳＢ２
とのペアをサブブロックペアＳＢＰ１とし、サブブロッ
クＳＢ３と、その上位（隣）に位置するサブブロックＳ
Ｂ４とペアをサブブロックペアＳＢＰ２とする。残りの
サブブロックに関しても同様にしてサブブロックペアを
決定し、合計１６個のサブブロックペアを決定する。

【００６０】次に、書戻サブブロックの属するサブブロ
ックペアを書戻サブブロックペアとし、夫々の書戻サブ
ブロックペアに対してサブブロックナンバーを付す（ス
テップＳ１０５）。例えば、図５（ａ）においては、書
戻サブブロックが４個あり、それぞれが書戻サブブロッ
クではないサブブロックとサブブロックペアを構成する
こととなるため、書戻サブブロックペアも４個となる。
この４個の書戻サブブロックペアＳＢＰ１、ＳＢＰ２、
ＳＢＰ３、ＳＢＰ４に対して、サブブロックナンバーと
して、下位から順番に夫々、１、２、３、４を付す。

【００６１】次に、現在サブブロックナンバーとして、
１を設定すると共に、サブブロックペア数として書戻サ
ブブロックペアの個数を設定する（ステップＳ１０
６）。図５（ａ）の状態においては、書戻サブブロック
ペアが４個あるので、サブブロックペア数は４となる。

【００６２】次に、現在サブブロックナンバーの付され
ているサブブロックペアについて、書戻所要時間とデー
タサイズとの関係を示すテーブルに従って、サブブロッ
クペアとしてまとめて書き戻した方が良いかどうかにつ
いて判断し（ステップＳ１０７）、まとめて書き戻した
方が良いと判断した場合、ステップＳ１０８へ進み、ま
とめて書き戻さない方が良いと判断した場合、ステップ
Ｓ１０９へ進む。

【００６３】ここで、ステップＳ１０７における判断に
ついて、図８を用いて更に詳細に説明する。まず、現在
サブブロックナンバーの付されているサブブロックペア
について、当該サブブロックペアを構成するサブブロッ
クが、双方とも書戻サブブロックであるかどうかについ
て判定する（ステップＳ１０７１）。ステップＳ１０７
１において双方とも書戻サブブロックであると判定した
場合、次に、当該サブブロックペアに含まれている書戻
データブロックに関し、夫々の書戻データブロック毎に
書き戻した方が書戻所要時間が短いかどうかについて、
データサイズと書戻所要時間との関係を示すテーブルに
従って判定する（ステップＳ１０７２）。また、ステッ
プＳ１０７２において、書戻所要時間が短いと判定した
場合、ステップＳ１０９へ進み、短くないと判定した場
合、ステップＳ１０８へ進み、夫々、以降の処理を実行
する。一方、ステップＳ１０７１において、片方のみが
書戻サブブロックであると判定した場合、書戻所要時間
とデータサイズとの関係を示すテーブルに基づいて、当
該サブブロックペアとしてまとめて書き戻しても、書戻
サブブロックに含まれている書戻データブロックのみを
書き戻した場合と比較して、書戻所要時間が変わらない
かどうかについて判定する（ステップＳ１０７３）。ス
テップＳ１０７３において、書戻所要時間が変わらない
と判定した場合、ステップＳ１０８へ進み、サブブロッ
クペアとしてまとめて書き戻すと書戻所要時間が長くな
ると判定した場合、ステップＳ１０９へ進み、夫々、以
降の処理を実行する。現時点では、現在サブブロックナ
ンバーが１であるので、サブブロックペアＳＢＰ１を構
成するサブブロックは、一方のみが書戻サブブロックで
ある。従って、ステップＳ１０７１における判定によ
り、ステップＳ１０７３に進み、サブブロックペアＳＢ
Ｐ１について図４に示されるテーブルに基づいて判断す
る。図４に示されるテーブルによれば、データサイズが
１バイトであっても２バイトであっても書戻所要時間は
変わらないため、より大きなデータサイズとしてサブブ
ロックペアをまとめて書き戻した方が良いと判断し（ス
テップＳ１０７３）、ステップＳ１０８へ進む。

【００６４】次に、ステップＳ１０７において、まとめ
て書き戻した方が良いと判断した場合、新たな書戻デー
タブロックとしてサブブロックペアを構成する初期サブ
ブロックを記憶する（ステップＳ１０８）。現時点で
は、書戻データブロックとして記憶されているサブブロ
ックＳＢ１に代えて、サブブロックペアＳＢＰ１を構成
する２つの初期サブブロックＳＢ１及びＳＢ２を新たな
書戻データブロックとして記憶する。

【００６５】次に、現在サブブロックナンバーがサブブ
ロックペア数と同値かどうかについて判定し（ステップ
Ｓ１０９）、同値であれば、ステップＳ１１０へ進み、
以降の処理を実行する。一方、ステップＳ１０９におい
て判定した結果、同値でなければ、現在サブブロックナ
ンバーに１を加算して、加算結果を新たな現在サブブロ
ックナンバーとして再設定し（ステップＳ１１１）、ス
テップＳ１０７へ進み処理を続行する。現時点では、現
在サブブロックナンバーが１であり、サブブロックペア
数が４であるので、ステップＳ１１１に進み現在サブブ
ロックナンバーを２に再設定して、サブブロックナンバ
ーが２のサブブロックペアＳＢＰ２についてステップＳ
１０７における判断を行う。同様にして、サブブロック
ペアＳＢＰ４まで判断が終了すると、書戻データブロッ
クとして、図５（ｂ）に黒塗りで示されるような初期サ
ブブロックが記憶されることになる。また、サブブロッ
クペアＳＢＰ４まで、判断が終わった時点では、サブブ
ロックナンバーが４であり、サブブロックペア数と一致
するため、ステップＳ１１０へ進む。

【００６６】ステップＳ１０９において、現在サブブロ
ックナンバーとサブブロックペア数とが一致したら、次
に、現在データサイズとキャッシュラインサイズの半分
のデータサイズとが一致するかどうかについて判定し
（ステップＳ１１０）、一致した場合は、ステップＳ１
１３へ進み、以降の処理を実行する。一方ステップＳ１
１０において一致しないと判定した場合、現在データサ
イズを２倍したものを新たな現在データサイズとして再
設定し、また、サブブロックペアを新たなサブブロック
とすると共に、新たなサブブロックの内、書戻データブ
ロックを含むサブブロックを新たな書戻サブブロックと
して再設定し（ステップＳ１１２）、ステップＳ１０４
へ戻り、処理を続行する。現時点では、図５（ａ）に示
されるように、現在サブブロックサイズは、１バイトで
あり、一方、キャッシュラインサイズの半分のデータサ
イズは、３２／２で１６バイトであるため、ステップＳ
１１０における判定では一致しない。従って、ステップ
Ｓ１１２に進み、値を再設定する。即ち、これまでの現
在データサイズ（１バイト）を２倍し、新たな現在デー
タサイズとして２バイトを設定する。また、例えば、サ
ブブロックペアＳＢＰ１を新たなサブブロックＳＢ１′
として設定し、同様に、サブブロックペアＳＢＰ２を新
たなサブブロックＳＢ２′として設定する。全てのサブ
ブロックペアを新たなサブブロックとして設定すると、
新たなサブブロックの個数は、１６個となる。この１６
個のサブブロックの内、書戻データブロックを含むサブ
ブロックは、図５（ｂ）において黒塗りされている４つ
であり、それらを新たな書戻サブブロックとして設定す
る。

【００６７】これらの設定が終了した後、ステップＳ１
０４に進み、隣り合う新たなサブブロックを新たなサブ
ブロックペアとして８個のサブブロックペアを決定す
る。例えば、図５（ｂ）において、新たなサブブロック
ＳＢ１′とサブブロックＳＢ２′とを新たなサブブロッ
クペアＳＢＰ１′とし、同様にして８個のサブブロック
（ＳＢＰ２′他）を決定する（ステップＳ１０４参
照）。図５（ｂ）においては、４つの書戻サブブロック
があるが、その内の１組の書戻サブブロックが１つのサ
ブブロックペアを構成しているため、書戻サブブロック
ペアは３つとなる。従って、それら３つのサブブロック
ペアＳＢＰ１′、ＳＢＰ２′及びＳＢＰ３′に対して下
位から順番に１、２、３のサブブロックナンバーを付す
（ステップＳ１０５参照）。更に、それら全てに対して
サブブロックペアとしてまとめて書き戻した方が良いか
どうかを判定し（ステップＳ１０７及びステップＳ１０
９参照）、まとめて書き戻した方が良い場合には、当該
サブブロックペアを構成する初期サブブロックを新たな
書戻データブロックとして記憶する。サブブロックペア
ＳＢＰ１′については、書戻データブロック毎に書き戻
すよりも、まとめて書き戻した方が書戻所要時間を３ｔ
短縮できるため（図４及びステップＳ１０７２参照）、
新たな書き戻しデータブロックとして、サブブロックペ
アＳＢＰ１′を構成している４つの初期サブブロックＳ
Ｂ１〜ＳＢ４を記憶する（ステップＳ１０８参照）。一
方、サブブロックペアＳＢＰ２′及びサブブロックペア
ＳＢＰ３′については、夫々、まとめて書き戻すと書き
戻し所要時間が１ｔ長くかかることになるため（図４及
びステップＳ１０７３参照）、書戻データブロックは、
現時点でのサブブロックＳＢ３′及びサブブロックＳＢ
４′を夫々構成している初期サブブロックのままであ
る。このようにして、図５（ｂ）における全ての書戻サ
ブブロックペアについて判定が終了しても、現在データ
サイズは、２バイトであり、キャッシュラインサイズ
（３２バイト）の半分のデータサイズ（１６バイト）と
一致しないため（ステップＳ１１０参照）、ステップＳ
１１２に進む。ステップＳ１１２において新たな現在デ
ータサイズを４バイトと設定し、サブブロックペアＳＢ
Ｐ１′及びサブブロックペアＳＢＰ２′を、夫々、新た
なサブブロックＳＢ１″及びサブブロックＳＢ２″とす
る。同様にして、図５（ｂ）におけるサブブロックペア
を新たなサブブロックとすると、８個の新たなサブブロ
ックができる。その８個のサブブロックの内、書戻デー
タブロックを含むサブブロックは、図５（ｃ）に示され
るように３つである（サブブロックＳＢ１″、ＳＢ
２″、ＳＢ３″）。これらを設定した後、再度ステップ
Ｓ１０４へ戻り、新たなサブブロックペアを４つ決定
し、更に、ステップＳ１０５以降の処理を実行する。こ
のようにして図５（ｃ）〜図５（ｅ）に示されるよう
に、徐々に現在データサイズを大きくしながら、書戻デ
ータブロックについての判断を行う。図５（ｅ）に示さ
れる状態では、現在データサイズが１６バイトであり、
キャッシュラインサイズ（３２バイト）の半分となるた
め、ステップＳ１１０における判定の結果、ステップＳ
１１３へ進むことができる。

【００６８】この段階において、記憶されている書戻デ
ータブロックを書き戻すべき最適な初期サブブロックの
組合わせとして決定する（ステップＳ１１３）。例え
ば、図５（ｆ）を参照すると、図５（ｅ）までの処理よ
り、２つの書戻データブロックＷＢＤ１及びＷＢＤ２が
求められている。即ち、書き戻すべき最適な組合わせを
構成する初期サブブロックは、最下位のサブブロック＃
０からサブブロック＃７までの８つのサブブロックと、
最上位のサブブロック＃３１とその下位に位置するサブ
ブロック＃３０との２つのサブブロックとの合計１０個
のサブブロックであり、それらの書戻所要時間は、７ｔ
＋４ｔ＝１１ｔである。従来例１のように、ダーティビ
ットがオンであるサブブロック毎に書き戻しをしていれ
ば、書戻所要時間は、４ｔ×４＝１６ｔ必要である。ま
た、従来例２のように書戻サブブロックを含むサブブロ
ックグループ毎に書き戻す場合、サブブロックグループ
のサイズを２バイト、４バイト、８バイト、１６バイト
のいずれのサイズにプログラム設定したとしても、書戻
所要時間は、本具体例の１１ｔより長くなることにな
る。即ち、従来例１及び従来例２のいずれの場合も、書
き戻すべき最適なサブブロックの組合わせを適応的に決
定する本実施の形態と比較して、長い書戻所要時間を要
することとなる。

【００６９】最適な組合わせを構成するサブブロックを
判断する過程を示す他の例として図９を示す。図９は、
４つの初期サブブロック＃０、＃６、＃１６、及び＃３
１に対応するダーティビットがオンになっている場合で
ある。図９（ａ）においても上述の図５（ａ）における
判断と同様にして処理を行い、図９（ｂ）、図９
（ｃ）、図９（ｄ）、及び図９（ｅ）と順番に書戻デー
タブロックを決定していく。結果として、図９（ｆ）に
示されるように、書き戻すべき最適な組合わせを構成す
るサブブロックとして、８つの初期サブブロック＃０〜
＃７と、２つの初期サブブロック＃１６及び＃１７と、
２つの初期サブブロック＃３０及び＃３１との合計１６
個のサブブロックを決定する。これら１６個のサブブロ
ックを主記憶装置に書き戻すために要する時間は、１５
ｔである。この場合においても、従来例１のようにダー
ティビットがオンであるサブブロック毎に書き戻してい
れば、書戻所要時間は、４ｔ×４＝１６ｔ必要である。
また、従来例２のように書戻サブブロックを含むサブブ
ロックグループ毎に書き戻すとしても、書戻所要時間
は、１５ｔより長くなることになる。

【００７０】また、本実施の形態において示した手法に
よれば、更新すべきキャッシュラインに関して、全ての
サブブロックに対応するダーティビットがオンであった
場合、書戻所要時間は、キャッシュライン単位で書き戻
した場合と同じ時間となり、従来例１及び従来例２にお
けるような不具合は生じない。

【００７１】これらのことから理解されるように、本実
施の形態においては、従来例１及び従来例２と比較して
も、書き戻しに要する時間を短縮することができる。

【００７２】また、書き戻しに要する時間を短縮するこ
とができるということは、キャッシュラインサイズをよ
り大きなものとすることができることを意味する。更
に、キャッシュラインサイズをより大きいサイズとする
と、キャッシュメモリにおけるミス率が軽減されること
になり、キャッシュメモリの性能向上を図ることができ
る。即ち、本実施の形態に示される手法を適用すること
により、性能向上の図られたキャッシュメモリを実現す
ることが可能となる。

【００７３】尚、本実施の形態においては、ＣＰＵと主
記憶装置との間に設けられるキャッシュメモリ及びキャ
ッシュメモリシステムを例にとり説明してきたが、本発
明の概念は、本実施の形態に制限されるものではない。

【００７４】

【発明の効果】以上説明してきたように、本発明によれ
ば、データサイズと書戻所要時間との関係を示すテーブ
ルに基づいて、書き戻すべきサブブロックの最適な組合
わせを決定することができるため、書き戻しに要する時
間を短縮することができるキャッシュメモリシステムが
得られる。

【００７５】また、本発明によれば、より大きなキャッ
シュラインサイズを有することにより、性能向上の図ら
れたキャッシュメモリを実現することができる。

【図面の簡単な説明】

【図１】本発明の実施の形態のキャッシュメモリの構成
を示す図である。

【図２】本発明の実施の形態のキャッシュメモリシステ
ムとＣＰＵ及び主記憶装置と関係を示すブロック図であ
る。

【図３】本発明の実施の形態におけるデータ書戻手段の
構成を示すブロック図である。

【図４】本発明の実施の形態におけるデータサイズと書
戻所要時間との関係を示すテーブルとしての一例であ
る。

【図５】本発明の実施の形態において書き戻すべきサブ
ブロックの最適な組合わせを判断する過程の一例を示す
図である。

【図６】本発明の実施の形態においてサブブロックの最
適な組合わせを判断するためのフローチャートの一部を
示す図である。

【図７】本発明の実施の形態においてサブブロックの最
適な組合わせを判断するためのフローチャートの内、図
６に示された残りを示す図である。

【図８】図６に示されるステップＳ１０７を更に詳細に
示す図である。

【図９】本発明の実施の形態において書き戻すべきサブ
ブロックの最適な組合わせを判断する過程の他の例を示
す図である。

【符号の説明】１０キャッシュメモリシステム２０キャッシュメモリ３０データ書戻手段４０ＣＰＵ５０主記憶装置３０１ライトバックサイズ／アドレス生成部３０２ライトバックデータ生成部３０３ライトバッファ３０４ライトバック制御部３０５リード制御部ＴＦタグフィールドＤＢＭダーティビット格納部ＤＭデータ格納部

Claims

【特許請求の範囲】

【請求項１】予め定められた量のデータをそれぞれ格
納する複数のキャッシュライン、及び該複数のキャッシ
ュラインのそれぞれに対応した複数のダーティビット格
納部を有するキャッシュメモリと、当該キャッシュメモ
リからみて下位レベルの記憶領域に対して前記キャッシ
ュラインに格納されているデータを書き戻すためのデー
タ書戻手段とを備えたキャッシュメモリシステムにおい
て、書き戻すデータサイズと書き戻しに要する時間との関係
を表すテーブルを更に備えており、前記キャッシュメモリは、前記複数のキャッシュライン
の夫々が所定数のサブブロックに分割されていると共
に、前記各ダーティビット格納部が、夫々、対応するキ
ャッシュラインにおけるサブブロックに対応したダーテ
ィビットを格納するものであり、前記データ書戻手段は、特定の前記キャッシュラインに
格納されているデータを書き戻す際に、前記テーブルを
参照すると共に、前記特定のキャッシュラインに対応す
る前記ダーティビット格納部に格納されているダーティ
ビットの内、オンを示すダーティビットを参照して、書
き戻すべき前記サブブロックの最適な組合わせを決定
し、当該最適な組合わせを構成する前記サブブロックに
格納されているデータを前記下位レベルの記憶領域に対
して書き戻すことを特徴とするキャッシュメモリシステ
ム。
【請求項２】請求項１に記載のキャッシュメモリシス
テムにおいて、前記キャッシュメモリは、前記複数のキャッシュライン
の夫々に対応するタグを格納するための複数のタグフィ
ールドを備えていることを特徴とするキャッシュメモリ
システム。
【請求項３】請求項２に記載のキャッシュメモリシス
テムにおいて、前記データ書戻手段は、前記特定のキャッシュラインに格納されているデータ
を、前記下位レベルの記憶領域に書き戻す際に、前記テ
ーブルを参照すると共に、該特定のキャッシュラインに
対応する前記タグフィールドに格納されている前記タグ
である特定のタグと、前記特定のキャッシュラインに対
応する前記ダーティビット格納部に格納されている前記
ダーティビットである特定のダーティビットとを参照し
て、前記最適な組合わせを構成する前記サブブロックの
データに関し、データサイズ及び前記特定のキャッシュ
ラインにおけるアドレスを生成するためのライトバック
サイズ／アドレス生成部と、前記特定のキャッシュラインに格納されているデータを
前記下位レベルの記憶領域に書き戻す際に、前記テーブ
ルを参照すると共に、前記特定のタグ及び前記特定のダ
ーティビットを参照して、前記最適な組合わせを構成す
る前記サブブロックのデータとしてのライトバックデー
タを生成するためのライトバックデータ生成部と、前記ライトバックサイズ／アドレス生成部の生成した前
記データサイズ及び前記特定のキャッシュラインにおけ
るアドレス、並びに前記ライトバックデータ生成部の生
成した前記ライトバックデータを一時的に格納するため
のライトバッファと、該ライトバッファの状態を監視すると共に、前記下位レ
ベルの記憶領域に対して、前記ライトバッファに一時的
に格納される前記データサイズ、前記アドレス及び前記
ライトバックデータを書き戻す制御を行うためのライト
バック制御部とを備えていることを特徴とするキャッシ
ュメモリシステム。
【請求項４】請求項３に記載のキャッシュメモリシス
テムにおいて、前記キャッシュメモリの上位レベルから前記キャッシュ
メモリに対する要求に含まれるアドレスと同内容のアド
レスを受けて、前記下位レベルの記憶領域に対して前記
要求に対応するデータ要求を行うと共に、前記下位レベ
ルの記憶領域から当該データ要求に対応するデータを受
けて、該データを前記キャッシュメモリに対して送出す
るためのリード制御部を更に備えていることを特徴とす
るキャッシュメモリシステム。
【請求項５】請求項４に記載のキャッシュメモリシス
テムにおいて、前記ライトバック制御部は、前記ライトバックデータ、
当該ライトバックデータのサイズである前記データサイ
ズ及び前記アドレスが前記ライトバッファに揃ったこと
を示すライトバッファ状態信号を前記リード制御部に対
して送出すると共に、前記リード制御部からのデータ転
送終了信号を受けて、前記ライトバッファに揃っている
前記ライトバックデータ、前記データサイズ及び前記ア
ドレスを前記下位レベルの記憶領域に対して書き戻すた
めのものであり、前記リード制御部は、前記ライトバッファ状態信号を受
けた後に、前記下位レベルの記憶領域から受けた前記デ
ータ要求に対応するデータを前記キャッシュメモリに対
して転送すると共に、当該転送が終了したことを示すデ
ータ転送終了信号を前記ライトバック制御部に対して送
出するためのものであることを特徴とするキャッシュメ
モリシステム。
【請求項６】データ格納領域として複数のキャッシュ
ラインを有するキャッシュメモリであって、キャッシュ
ラインを複数のサブブロックに分割し、前記各サブブロ
ックに対応する複数のダーティビットを備えることとし
たキャッシュメモリにおいて、前記キャッシュラインに
格納されているデータを当該キャッシュメモリから見て
下位レベルの記憶領域に対して書き戻す必要が生じた場
合における最適な書戻データサイズを求める方法であっ
て、データサイズと書き戻しに要する時間との関係に基づい
て、オンを示す前記ダーティビットに対応する前記サブ
ブロックと、該サブブロックに隣接するサブブロックと
をまとめて前記下位レベルの記憶領域に対して書き戻す
べきかどうかを判断し、前記複数のダーティビットの
内、オンを示すダーティビットの分布に従って、更に必
要に応じて、書き戻すべきと判断した複数の前記サブブ
ロックからなる書戻データブロックと、当該書戻データ
ブロックと同じデータサイズのデータブロックであっ
て、該書き戻しデータブロックに隣接するデータブロッ
クとをまとめて前記下位レベルの記憶領域に対して書き
戻すべきかどうかを判断することにより、最適な書戻デ
ータサイズを求める方法。