JPH0228738A - 多階層キャッシュメモリのブロック置換え方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、多階層キャッシュメモリで構成される情報処
理装置におけるキャッシュメモリのブロック置換え方法
に関する。

〔従来の技術〕

第４図に従来のブロック置換え方法を説明するための多
階層キャッシュメモリの構成例を示す。

これはプロセッサ１とメインメモリ４の間に、レベル０
（上位レベル）のキャッシュメモリ２とレベル１　（下
位レベル）のキャッシュメモリ３の二階層キャッシュメ
モリを配置した例である。第４図では、レベル１のキャ
ッシュメモリ３の容量はレベル０のキャッシュメモリ２
の容量の２倍、メモリ４の容量はレベル１のキャッシュ
メモリ３の容量の２倍であるとしている。５は一つのブ
ロックを示し、各メモリともに等しい大きさの容量であ
る。

レベルＯのキャッシュメモリ２、レベル１のキャッシュ
メモリ３およびメインメモリ４は複数の列（第４図では
４列）に分割されており、メインメモリ４の同一列に含
まれるブロック５は、レベルＯのキャッシュメモリ２お
よびレベル１のキャッシュメモリ３の同一列に格納され
る。また、レベル○のキャッシュメモリ２およびレベル
１のキャッシュメモリ３の各列において、各ブロックは
、過去にブロックの要求が行われた順序に格納される。

第４図において、これを新←旧で示している。

以下、第４図の構成例について、第５図および第６図を
参照して従来のブロック置換え処理を説明する。

いま、初期状態として、第４図に示すメインメモリ４の
ブロック群に対し、レベルＯのキャッシュメモリ２およ
びレベル１のキャッシュメモリ３に第６図（ａ）に示す
ようにブロックが格納されており、プロセッサ１はブロ
ック０１，０２，０１．０３，０４の順に各ブロック内
のデータを要求したとする。

まず、プロセッサ１からブロック０１内のデータが要求
された時、レベルＯのキャッシュメモリ２にブロック０
１が存在するので、レベルＯのキャッシュメモリ２はプ
ロセッサ１にブロック０１内のデータを転送すると＼も
に、第０列に格納されているブロックをプロセッサ１か
ら要求のあった順序に並べ換える（第５図のステップ５
０１゜５０２、　５］、２．　５１３）　　。

このプロセッサ１からブロック０１が要求された場合の
処理後、レベルＯのキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第６図（ｂ）のようにな
る。

次に、プロセッサ１からブロック０２内のデータが要求
された時、レベル０のキャッシュメモリ２は、内部にブ
ロック０２を格納していないので、レベル１のキャッシ
ュメモリ３にブロック０２を要求すると共に、第０列の
ブロック中でプロセッサ］からの要求が最も古く行われ
たブロックＯ０をブロック０２て置換えるべきブロック
として選択する（第５図のステップ５０１，５０２，５
０３．５０４．）。

レベル１のキャッシュメモリ３は、ブロック０２が存在
するので、レベル０のキャッシュメモリ２ヘブロツク０
２を転送（ブロック転送）すると。

＼もに、第０列中に格納されているブロックをレベルＯ
のキャッシュメモリ２から要求のあった順序に並べ変え
る（第５図のステップ５０５．５０９．５１０）。レベ
ル０のキャッシュメモリ２は、第０列中のブロックＯＯ
を、レベル１のキャッシュメモリ３から転送されたブロ
ック０２で置き換える（第５図のステップ５１１）。そ
の後、レベルＯのキャッシュメモリ２は、プロセッサ１
にブロック０２内のデータを転送すると＼もに、第０列
に格納されているブロックをプロセッサ１から要求のあ
った順序に並べ変える（第５図の５１２゜５１３）。

このプロセッサ１からブロック０２が要求された場合の
処理後、レベルＯのキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第６図（ｃ）のようにな
る。

次に、プロセッサ１から再びブロック０１内のデータが
要求された時、レベル０のキャッシュメモリ２にブロッ
ク０１が存在するので、レベル０のキャッシュメモリ２
はプロセッサ１にブロック０１内のデータを転送すると
２もに、第０列に格納されているブロックをプロセッサ
１がら要求のあった順序で並べ変える（第５図のステッ
プ５゜１、　５０２．　５１２．　５０３）　　。

このプロセッサ１から再びブロック０１が要求された場
合の処理後、レベル０のキャッシュメモリ２およびレベ
ル１のキャッシュメモリ３の状態は第６図（ｄ）のよう
になる。

次に、プロセッサ１からブロック０３内のデータが要求
された時、レベル０のキャッシュメモリ２はブロック０
３を内部に格納しておらず、レベル１のキャッシュメモ
リ３はブロック０３を格納している。この時の処理は、
先のブロック０２内のデータが要求された場合と同様で
ある。即ち、レベル１のキャッシュメモリ３からレベル
Ｏのキャッシュメモリ２にブロック０３が転送され、レ
ベル０のキャッシュメモリ２は、第０列のブロックでプ
ロセッサ１からの要求が最も以前に行われたブロック０
２をブロック０３で置き換え、プロセッサ１にブロック
０３内のデータを転送すると＼もに、第０列に格納され
ているブロックをプロセッサ１から要求のあった順序に
並べ変える。

方、レベル１のキャッシュメモリ３は、第０列に格納さ
れているブロックをレベル０のキャッシュメモリ２から
要求のあった順序に並べ変える。

このプロセッサ１からブロック０３が要求された場合の
処理後、レベルＯのキャッシュメモリ２およびレベル１
のキャッシュメモリの状態は第６図（ｅ）のようになる
。

次に、プロセッサ１からブロック０４内のデータが要求
された時、レベル０のキャッシュメモリ２は、内部にブ
ロック４を格納していないので、レベル１のキャッシュ
メモリ３にブロックｏ４を要求すると２もに、第０列の
ブロック中でプロセッサ１からの要求が最も古くに行わ
れたブロック０１を置き換えブロックとして選択する（
第５図のステップ５０１，５０２，５０３，５０４）。

一方、レベル１のキャッシュメモリ３にもブロック０４
が存在しないので、レベル１のキャッシュメモリ３は、
メインメモリ４に対してブロック０４を要求すると＼も
に、第０列のブロック中でレベルＯのキャッシュメモリ
２からの要求が最も古くに行われたブロック０１をブロ
ック０４で置き換えるべきブロックとして選択する（第
５図のステップ５０５，５０６，５０７）。メインメモ
リ４からブロック０４の転送（ブロック転送）が行われ
ると、レベル１のキャッシュメモリ３は、第０列中のブ
ロック０１を、メインメモリ４から転送されたブロック
０４で置き換える（第５図のステップ５０８）。その後
、レベル１のキャッシュメモリ３は、レベル０のキャッ
シュメモリ２にブロック０４を転送すると＼もに、第０
列に格納されているブロックをレベルＯのキャッシュメ
モリ２から要求のあった順序に並べ変える（第５図のス
テップ５０９，５１０）。

レベルＯのキャッシュメモリ２は、第０列中のブロック
０１を、レベル１のキャッシュメモリ３から転送された
ブロック４で置き換える（第５図のステップ５１１）。

その後、レベル０のキャッシュメモリ２は、プロセッサ
１にブロック０４内のデータを転送すると＼もに、第０
列に格納されているブロックをプロセッサ１からの要求
のあった順序に並べ換える（第５図のステップ５１２゜
５１３）。

このプロセッサ１からブロック０４が要求された場合の
処理後、レベルＯのキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第６図（ｆ）のようにな
る。

〔発明が解決しようとする課題〕

一般に、プロセッサから要求された順序が新しいブロッ
ク程、再びプロセッサから要求される確率が高いので、
キャッシュメモリに格納しておく必要がある。しかし、
従来のブロック置換え方法では、上記のように、下位の
レベルのキャッシュメモリは、上位レベルのキャッシュ
メモリから要求されたブロックの情報のみを用い、プロ
セッサから上位レベルのキャッシュメモリに対して行わ
れたアクセスと独立にブロックの置き換えを行っていた
ので、下位レベルのキャッシュメモリには、プロセッサ
から要求された順序の新しいブロックが、必ずしも格納
されるようになっていない欠点があった。第６図の例で
は、プロセッサ１からブロック内のデータの要求がブロ
ック０１，０２゜０１．０３，０４の順に行われたにも
か＼わらず、プロセッサ５から要求された順序が３番目
に新しいブロック０１がレベル１のキャッシュメモリ３
に格納されていない。

本発明の目的は、多階層キャッシュメモリにおいて、下
位レベルのキャッシュメモリに、プロセッサから要求さ
れた順序の新しいブロックを格納することを可能とする
ブロック置換え方法を提供することにある。

〔課題を解決するための手段〕

上記目的を達成するため、本発明の多階層キャッシュメ
モリのブロック置換え方法においては、下位レベルのキ
ャッシュメモリのブロックを、上位レベルのキャッシュ
メモリに格納されているブロックと格納されていないブ
ロックに区分し、下位レベルのキャッシュメモリでのブ
ロック置き換え時、上位レベルのキャッシュメモリに格
納されていないブロックを置き換えの対象とすることを
特徴とするものである。

〔作　用〕

上位レベルのキャッシュメモリは、下位レベルのキャッ
シュメモリにブロック要求を出す時、該ブロックで置き
換えられるブロックも同時にを通知する。これにより、
下位レベルのキャッシュメモリでは、ブロックを上位レ
ベルのキャッシュメモリに格納されているブロックと格
納されていないブロックに区分することができる。

下位レベルのキャッシュメモリは、ブロック置き換え時
、上位レベルのキャッシュメモリに含まれていないブロ
ックのみを置き換えの対象とし、プロセッサから要求さ
れた順序に新しいブロックを格納する。これにより、下
位レベルのキャッシュメモリにおけるブロックの置き換
えが、上位レベルのキャッシュメモリが無い場合と同様
に行われ、プロセッサから要求された新しいブロックを
優先して内部に格納しておくことが可能となる。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明のブロック置換え方法の一実施例を説明
するための構成図で、１はプロセッサ、２はレベル０の
キャッシュメモリ、３はレベル１のキャッシュメモリ、
４はメインメモリである。

第１図の構成は、基本的に第４図の構成と同様であり、
レベルＯのキャッシュメモリ２、レベル１のキャッシュ
メモリ３およびメインメモリ４は４列に分かれ、レベル
］のキャッシュメモリ３の容量はレベルＯのキャッシュ
メモリ２の容量の２倍、メインメモリ４の容量はレベル
１のキャッシュメモリ３の容量の２倍であるとしている
。５は一つのブロックを示し、各メモリともに等しい大
きさの容量である。

メインメモリ４の同一列に含まれるブロックは、レベル
０のキャッシュメモリ２およびレベル１のキャッシュメ
モリ３の同一列に格納される。この場合、レベルＯのキ
ャッシュメモリ２の各列については、従来と同様にプロ
セッサ１から要求が行われた順序にブロックが格納され
るが、レベル１のキャッシュメモリ３の各列については
、レベルＯのキャッシュメモリ２に格納されているプロ
ン］１ りａ、レベルＯのキャッシュメモリ２に格納されていな
いブロックｂに分けて格納し、レベルＯのキャッシュメ
モリ２に格納されていないブロックｂは、過去にレベル
Ｏのキャッシュメモリ２に格納されていた順序に格納す
る。第１図において、置換えられた順序を新←旧で示す
。

以下、第１図の構成例について、第２図および第３図を
参照して本発明によるブロック置換え処理の一例を説明
する。

いま、初期状態として、第１図に示すメインメモリ４の
ブロック群に対し、レベルＯのキャッシュメモリ２およ
びレベル１のキャッシュメモリ３に第３図（ａ）に示す
ようにブロックが格納されているとする。この状態にお
いて、プロセッサ１がブロック０１，０２，０１，０３
，０４の順にデータを要求した場合について以下に説明
する。

まず、プロセッサｌからブロック０１内のデータが要求
された時、レベルＯのキャッシュメモリ２にブロック０
１が存在するので、レベルＯのキャッシュメモリ２はプ
ロセッサ１にブロック０１内のデータを転送すると＼も
に、第０列に格納されているブロックをプロセッサ１か
ら要求のあった順序に並べ換える（第２図のステップ２
０１゜２０２．２１２，２１３）。

このプロセッサ１からブロック０１が要求された場合の
処理後、レベル０のキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第２図（ｂ）のようにな
る。これは第６図（ｂ）と同じである。

次に、プロセッサ１からブロック０２内のデータが要求
された時、レベルＯのキャッシュメモリ２は、内部にブ
ロックｏ２を格納していないので、第０列のブロック中
でプロセッサ１からの要求が最も古く行われたブロック
ＯＯをブロック０２で置換えるべきブロックとして選択
し、レベル１のキャッシュメモリ３に対し、ブロック０
２のブロック転送を要求すると＼もに、ブロックＯＯを
ブロック０２で置き換えることを通知する（第２図のス
テップ２０１，２０２，２０３，２０４）。

レベル１のキャッシュメモリ３は、ブロックＯ２が存在
するので、レベルＯのキャッシュメモリ２ヘブロツク０
２を転送する（第２図のステップ２０５．２０９）。そ
の後、レベル１のキャッシュメモリ３は、ブロック００
とブロック０２の格納位置を入れ換えると＼もに、レベ
ル０のキャッシュメモリ２の第０列に格納されていない
ブロックｂをレベルＯのキャッシュメモリ２に格納され
ていた順序に並べ変える（第２図のステップ２１０）。

レベルＯのキャッシュメモリ２は、第０列中のブロック
ＯＯを、レベル１のキャッシュメモリ３から転送された
ブロック０２で置き換える（第２図のステップ２１１）
。その後、レベルＯのキャッシュメモリ２は、プロセッ
サ１にブロック０２内のデータを転送すると＼もに、第
０列に格納されているブロックをプロセッサ１から要求
のあった順序に並べ変える（第２図の２１２，２１３）
。

このプロセッサ１からブロック０２が要求された場合の
処理後、レベル０のキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第２図（ｃ）のようにな
る。第６図（ｃ）に対し、第２図（Ｃ）では、レベル１
のキャッシュメモリ３において、ブロックＯＯとブロッ
ク０１の配置が入れ換わっている。

次に、プロセッサ１から再びブロック０１内のデータが
要求された時、レベル０のキャッシュメモリ２にブロッ
ク０１が存在するので、レベルＯのキャッシュメモリ２
はプロセッサ１にブロック０１内のデータを転送すると
＼もに、第０列に格納されているブロックをプロセッサ
１から要求のあった順序で並べ変える（第２図のステッ
プ２０．２０２，２１２，２１３）。

このプロセッサ１から再びブロック０１が要求された場
合の処理後、レベル０のキャッシュメモリ２およびレベ
ル１のキャッシュメモリ３の状態は第２図（ｄ）のよう
になる。

次に、プロセッサ１からブロック０３内のデータが要求
された時、レベルＯのキャッシュメモリ２はブロック０
３を内部に格納しておらず、レベル１のキャッシュメモ
リ３はブロック０３を格納している。この時の処理は、
先のブロック０２内のデータが要求された場合と同様で
ある。即ち、レベルＯのキャッシュメモリ２は、内部に
ブロック０３を格納していないので、レベル１のキャッ
シュメモリ３にブロック０３を要求するが、同時に第０
列のブロックでプロセッサ１からの要求が最も古くに行
われたブロック０２をブロック０３で置き換えることを
通知する。レベル１のキャッシュメモリ３は、レベルＯ
のキャッシュメモリ２にブロック０３を転送し、レベル
Ｏのキャッシュメモリ２は、ブロック０２をブロック０
３で置き換え、プロセッサ１にブロック０３内のデータ
を転送すると＼もに、第０列に格納されているブロック
をプロセッサ１から要求のあった順序に並べ換える。一
方、レベル１のキャッシュメモリ３は、ブロック０２と
ブロック０３の格納位置を入れ換えると＼もに、レベル
Ｏのキャッシュメモリ２の第０列に格納されていないブ
ロックｂをレベルＯのキャッシュメモリ２に格納されて
いた順序に並べ変える。

１に のプロセッサ１からブロック０３が要求された場合の処
理後、レベルＯのキャッシュメモリ２およびレベル１の
キャッシュメモリの状態は第３図（ｅ）のようになる。

次に、プロセッサ１からブロック０４内のデータが要求
された時、レベル０のキャッシュメモリ２は、内部にブ
ロック０４を格納していないので、第０列のブロック中
でプロセッサ１からの要求が最も古くに行われたブロッ
ク０１を置き換えブロックとして選択し、レベル１のキ
ャッシュメモリ３に対し、ブロック０４を要求すると＼
もに、ブロック０１をブロック０４で置き換えることを
通知する（第２図のステップ２０１，２０２，２０３．
２０４）。

一方、レベル１のキャッシュメモリ３にもブロック０４
が存在しないので、レベル１のキャッシュメモリ３は、
メインメモリ４に対してブロック０４を要求すると＼も
に、第０列のブロック中でレベル０のキャッシュメモリ
２に最も古くに格納されなくなったブロック００をブロ
ック０４で置き換えるべきブロックとして選択する（第
２図のステップ２０５，２０６，２０７）。メインメモ
Ｉ７４からブロック０４の転送（ブロック転送）が行わ
れると、レベル１のキャッシュメモリ３は、第０列中の
ブロックＯＯを、メインメモリ４から転送されたブロッ
ク０４で置き換え、レベルＯのキャッシュメモリ２にブ
ロック０４を転送する（第２図のステップ２０８，２０
９）。その後、レベル１のキャッシュメモリ３は、第０
列中のブロック０１とブロック０４の格納位置を入れ換
えると＼もに、レベルＯのキャッシュメモリ２に格納さ
れていない第０列中のブロックｂをレベル０のキャッシ
ュメモリ２に格納されていた順序に並べ換える（第２図
のステップ２１０）。

レベルＯのキャッシュメモリ２は、第０列中のブロック
０１を、レベル１のキャッシュメモリ３から転送された
ブロック４で置き換える（第２図のステップ２１１）。

その後、レベルＯのキャッシュメモリ２は、プロセッサ
１にブロックｏ４内のデータを転送すると＼もに、第０
列に格納されているブロックをプロセッサ１からの要求
のあった順序に並べ換える（第２図のステップ２１２゜
２１３）。

このプロセッサ１からブロック０４が要求された場合の
処理後、レベル○のキャッシュメモリ２およびレベル１
のキャッシュメモリ３の状態は第３図（ｆ）のようにな
る。

第３図の例では、プロセッサ１からブロック内のデータ
の要求が、ブロック０１，０２，０１゜０３．０４の順
に行われ後、このプロセッサ１から要求された順序の新
しいブロック０１，０２゜０３．０４がレベル１のキャ
ッシュメモリ３に格納される。これにより、下位レベル
のキャッシュメモリ３におけるブロックの置き換えが、
上位レベルのキャッシュメモリ２が無い場合と同様に行
われ、プロセッサ１から要求された新しいブロックを優
先して内部に格納しておくことが可能となる。

〔発明の効果〕

以上説明したように、本発明によれば、多階層キャッシ
ュメモリにおいて、下位レベルのキャッシュメモリに上
位レベルのキャッシュメモリに格納されるブロックの情
報を伝え、上位レベルのキャッシュメモリでのブロック
の置き換え時、上位レベルのキャッシュメモリに含まれ
てないブロックを置き換えることにより、プロセッサか
ら要求された順序の新しいブロックを優先して内部に格
納しておくことが可能となる。一般に、上位レベルのキ
ャッシュメモリ程、プロセッサからのアクセス時間が短
かく、プロセッサから要求された順序が新しいブロック
程、再びプロセッサから要求される確率が高いので、プ
ロセッサから要求された順序に新しいブロックを正しく
キャッシュメモリに格納することにより、プロセッサか
らメモリへのアクセス時間を短縮することが可能となる
。

また、マルチプロセッサシステムのキャッシュメモリに
おいては、他のプロセッサにより書き変えられたメイン
メモリのデータをキャッシュメモリ内に持つことにより
、プロセッサが誤った処理を実行しないように、キャッ
シュメモリとメインメモリとのデータの一致制御を行う
必要がある。

本発明を用いることにより、任意のブロック（他のプロ
セッサにより書き変えられたデータを含むブロック）が
上位レベルのキャッシュメモリに格納されているか否か
を下位レベルのキャッシュメモリ内の情報から判定でき
るので、下位レベルから順しこ一致制御を行い、上位レ
ベルに他のプロセッサにより書き換えられたデータを含
むブロックが格納されていないと判定され＼ば、上位レ
ベルのキャッシュメモリに対する一致制御が不要となり
、キャッシュメモリにおけるプロセッサと一致制御のア
クセス競合を減少させることが可能となる利点がある。

【図面の簡単な説明】

第１図は本発明のブロック置換え方法の一実施例を説明
するための構成図、第２図は本発明によるブロック置換
え処理の一例のフローチャート、第３図は第１図の構成
の具体的処理例を示す図、第４図は従来のブロック置換
え方法を説明するための構成図、第５図は従来のブロッ
ク置換え処理のフローチャート、第６図は第４図の構成
の具体的処理例を示す図である。 １・・・プロセッサ、　２・・・レベルＯのキャッシュ
メモリ、　　３・・レベル１のキャッシュメモリ、４・
・メインメモリ、　　５・・・ブロック、ａ・・・レベ
ルＯのキャッシュメモリに格納されているブロック、　
ｂ・・レベルＯのキャッシュメモリに格納されていない
ブロック。 第３ 畝）ネｐヤ我態、 （ト）７′ロ゛ンフ０１會是七す”Ｌ　（！ＬＬＩ４１
ン（（、（す７°”ロツ７０２澱♂２゛（線１法君、（
ｄ）７’ｏ７７０１ｔノ’ｅ、；ｏｋ’Ｒ＊ｏｒ４に’
ｌｊ−しへ”ル０Ｉ７１ 七−一、二＋１％７キ１１ しへ゛ル１ク シｗ、、、＝　−−／Ｆ　ＩＩ （ｅ）７”Ｃ１ｙ７０３％’ｉ＃ｋ、−ｔｔａｅ４：’
Ｋｌ、ζ子）７・口、り。４饅Ｈ灯ｆ１１仄悠、六ヤン
鋺クーｙｔ７ へｆ７シＬＸ′ｔン 図 （α坊？ｌ勘状鉢 （ト２７パ０７〕Ｏ 減好１゛（代１＋ｊｌｒ’ｆｉ− （ｃ、＋〕゛’［７７７’２　ｊ北が”’ｆ９ｑ”ｌｊ
”’Ｂ（ｄ）フ゛０７７　Ｑ −＃茫子に’ｔフ夫ｌＩユ仄’Ｊ３− ＭＶ７シ１メセク へ？１シ２ヲ ムΔ゛ルＯラ ヘヤツ婢す ｌＡ−ル１の へヤシ〉メリ Ｃｅ）７”Ｏツｙｏ３ｊ：ｅＨｋ−Ｌｆ’ｉ、、＊”ｌ
Ｋ’ｇ（す）７°’Ｄソ）ｏ４　ｔＱａｆＦ−−Ｌｆ’
１ｑＬＦ’ｊ３、仁へＩＬＯＱ へヤソシニに×七υ Ｌへ゛ル１９ ＡヤＶ＝−ユ〆９ ムヘ゛ル０つ 六でフジメリ Ｌへ“ルック Ａヤフシエ〆−Ｊ

Claims (1)

【特許請求の範囲】
1. （１）プロセッサとメインメモリの間に、下位レベルほ
   ど容量の大きい複数のキャッシュメモリを配置してなる
   情報処理装置において、 下位レベルのキャッシュメモリのブロックを、上位レベ
   ルのキャッシュメモリに格納されているブロックと格納
   されていないブロックに区分し、下位レベルのキャッシ
   ュメモリでのブロック置き換え時、上位レベルのキャッ
   シュメモリに格納されていないブロックを置き換えの対
   象とすることを特徴とする多階層キャッシュメモリのブ
   ロック置換え方法。