JPH10198603A - 情報処理システム及びその制御方法、情報処理装置 - Google Patents

Abstract

(57)【要約】 【課題】 処理能力を向上させることができる情報処理
システム及びその制御方法、情報処理装置を提供する。 【解決手段】 クラスタ方式のようなメモリアクセス遅
延に大きな差異を生じるような複数のメモリをもつシス
テムにおいて、キャッシュ・ブロックの置換対象を決定
する際に、従来用いられているＬＲＵ法等の方法に加え
て、そのキャッシュ・ブロックを再びキャッシュ・メモ
リに読み込むために必要となるアクセス遅延の大小を考
慮して、アクセス遅延の大きな記憶装置に由来するデー
タブロックのキャッシュ・メモリ内部に引き続き存続す
る優先度を上昇させることによって、アクセス遅延の大
きなメモリに由来するキャッシュ・ブロックが置換対象
として選択されにくくする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はアクセス遅延の異な
る複数の記憶装置を有するシステムにおけるキャッシュ
・メモリのデータブロックの置換制御を実行する情報処
理システム及びその制御方法、情報処理装置に関するも
のである。

【０００２】

【従来の技術】近年の計算機システムにおいては、記憶
装置（以下メモリに代表させる）に対し発せられるプロ
セッサからのアクセス要求に高速に応答するため、各プ
ロセッサにはキャッシュ・メモリが付随されることが多
い。プロセッサから発行されるメモリへのアクセス要求
はキャッシュ・メモリを介して行われ、キャッシュ・メ
モリ中にはそれらメモリへのアクセス要求対象のデータ
ブロックのコピーが置かれることとなる。

【０００３】キャッシュ・メモリの構成法としてはダイ
レクトマップ方式、フルアソシアティブ方式、セット・
アソシアティブ方式等が代表的なものとして挙げられ
る。これらは、既に公知の構成法であり、例えば”Ｃｏ
ｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ ａ Ｑｕａ
ｎｔｉｔａｔｉｖｅ Ａｐｐｒｏａｃｈ” Ｓｅｃｏｎ
ｄ Ｅｄｉｔｉｏｎ（Ｄａｖｉｄ Ａ． Ｐａｔｔｅｒ
ｓｏｎ， Ｊｏｈｎ Ｌ．Ｈｅｎｎｅｓｓｙ 著、以
下、参考文献１と呼ぶ）の３７６、３７７ページにこれ
らに関する記載がある。

【０００４】キャッシュ・メモリにおいて、キャッシュ
・ミスした場合にはキャッシュ・ブロックを置き換える
必要が生じる。その場合、上記の３方式の中でも、比較
的今日良く用いられるセット・アソシアティブ方式で
は、置き換えの候補となるキャッシュ・ブロックが複数
あり、その中からどのキャッシュ・ブロックを置き換え
るかを選択しなければならない。選択方法としては、主
としてランダム法とＬＲＵ（Ｌｅａｓｔ‐Ｒｅｃｅｎｔ
ｌｙ Ｕｓｅｄ）法のうちのいずれか、もしくはそれに
似せた方法が取られていることが多い。尚、各手法に関
しては参考文献１の３７８ページ等に記載がある。

【０００５】一方、近年の計算機の処理能力の向上の要
求に応えて分散共有メモリ型のクラスタ型計算機及びそ
れらを複数構成した計算機システムが見られるようにな
ってきた。図１にその概略を示す。これは複数の単体の
計算機をノードとし、高速のネットワークで接続し、一
つの大きな計算機システムとして稼働させることによ
り、処理能力を向上させることをねらったものである。
これらのシステムの場合、あるノード１に存在するプロ
セッサ１０からは自ノード１内部のメモリ１２とノード
２上に存在するメモリ２２とにアクセスすることが可能
である。メモリ１２とメモリ２２とのプロセッサ１０か
ら見た差異は、メモリ２２の方がネットワークを介して
アクセスするためアクセス遅延が大きいことである。し
かし、キャッシュ・メモリ１１の存在により、一旦キャ
ッシュ・メモリ１１にデータブロックが格納されてしま
えば、それ以降のプロセッサ１０からのアクセスに関し
てはアクセス遅延は隠蔽され、処理能力の向上が期待で
きる。

【０００６】

【発明が解決しようとする課題】しかしながら、上記従
来のセットアソシアティブ方式をとったキャッシュ・メ
モリにおいて、一旦、キャッシュ・ミスが発生すると、
ＬＲＵ法等のメモリアクセス遅延を考慮しない方法でキ
ャッシュ・ブロックの置換対象の選択を行っていた。そ
のため、クラスタ方式のようなメモリアクセス遅延に大
きな差異を生じるようなシステムにおいては、そのキャ
ッシュ・ブロックがノード内、ノード外のいずれにある
かに関わらず置換対象として選択されてしまう。その結
果、特に、ノード外のアドレスに対応するデータのキャ
ッシュ・ブロックが置換対象として選択され、再び、そ
のノード外のメモリにアクセスした場合には、大きなメ
モリアクセス遅延が必要となり、システム全体の性能の
著しい低下を招く一因となっていた。

【０００７】本発明は上記の問題点を鑑みてなされたも
のであり、処理能力を向上させることができる情報処理
システム及びその制御方法、情報処理装置を提供するこ
とを目的とする。

【０００８】

【課題を解決するための手段】上記の目的を解決するた
めの本発明による情報処理装置は以下の構成を備える。
即ち、第１の記憶装置と、該第１の記憶装置よりもアク
セス遅延が大きい第２の記憶装置と、複数のキャッシュ
・ブロックを有するキャッシュ・メモリとを備える情報
処理システムであって、前記複数のキャッシュ・ブロッ
クのいずれかを置換する場合、該複数のキャッシュ・ブ
ロックそれぞれが前記第１の記憶装置及び前記第２の記
憶装置のどちらに属しているかを判定する判定手段と、
前記判定手段の判定結果に基づいて、前記複数のキャッ
シュ・ブロックのいずれかを置換する置換手段とを備え
る。

【０００９】また、好ましくは、前記置換手段による置
換対象としない優先度を前記複数のキャッシュ・ブロッ
ク毎に保持する保持手段を更に備え、前記判定手段の判
定結果及び前記保持手段が保持する優先度に基づいて、
前記置換手段は前記複数のキャッシュ・ブロックのいず
れかを置換する。また、好ましくは、前記置換手段によ
る置換されるキャッシュ・ブロックの優先度に基づい
て、該キャッシュ・ブロックを含む前記複数のキャッシ
ュ・ブロックの優先度を変更する変更手段を更に備え
る。

【００１０】また、好ましくは、前記変更手段は、前記
置換手段によって置換されるキャッシュ・ブロックの優
先度を最上位に変更し、該優先度と同じあるいはそれ以
下の優先度を持つキャッシュ・ブロックの優先度を上昇
させる。また、好ましくは、前記複数のキャッシュ・ブ
ロックそれぞれ保持するデータが有効であるか否かを示
す情報を管理する管理手段を更に備え、前記判定手段の
判定結果及び前記保持手段が保持する優先度及び前記管
理手段が管理する情報に基づいて、前記置換手段は前記
複数のキャッシュ・ブロックのいずれかを置換する。

【００１１】また、好ましくは、有効なデータを保持し
ていないキャッシュ・ブロックを示す情報を前記管理手
段が管理し、かつ前記複数のキャッシュ・ブロックのい
ずれかを置換する場合は、前記置換手段は該有効なデー
タを保持していないキャッシュ・ブロックを置換する。
また、好ましくは、前記判定手段は、前記第１の記憶装
置と前記第２の記憶装置それぞれに割り当てられたアド
レス空間に基づいて、前記複数のキャッシュ・ブロック
それぞれが前記第１の記憶装置及び前記第２の記憶装置
のどちらに属しているかを判定する。

【００１２】上記の目的を達成するための本発明による
情報処理システムの制御方法は以下の構成を備える。即
ち、第１の記憶装置と、該第１の記憶装置よりもアクセ
ス遅延が大きい第２の記憶装置と、複数のキャッシュ・
ブロックを有するキャッシュ・メモリとを備える情報処
理システムの制御方法であって、前記複数のキャッシュ
・ブロックのいずれかを置換する場合、該複数のキャッ
シュ・ブロックそれぞれが前記第１の記憶装置及び前記
第２の記憶装置のどちらに属しているかを判定する判定
工程と、前記判定工程の判定結果に基づいて、前記複数
のキャッシュ・ブロックのいずれかを置換する置換工程
とを備える。

【００１３】上記の目的を達成するための本発明による
情報処理装置は以下の構成を備える。即ち、第１の記憶
装置と、該第１の記憶装置よりもアクセス遅延が大きい
第２の記憶装置と、複数のキャッシュ・ブロックを有す
るキャッシュ・メモリとを備える情報処理装置であっ
て、前記複数のキャッシュ・ブロックのいずれかを置換
する場合、該複数のキャッシュ・ブロックそれぞれが前
記第１の記憶装置及び前記第２の記憶装置のどちらに属
しているかを判定する判定手段と、前記判定手段の判定
結果に基づいて、前記複数のキャッシュ・ブロックのい
ずれかを置換する置換手段と、を備える。

【００１４】上記の目的を達成するための本発明による
コンピュータ可読メモリは以下の構成を備える。即ち、
第１の記憶装置と、該第１の記憶装置よりもアクセス遅
延が大きい第２の記憶装置と、複数のキャッシュ・ブロ
ックを有するキャッシュ・メモリとを備える情報処理シ
ステムの制御のプログラムコードが格納されたコンピュ
ータ可読メモリであって、前記複数のキャッシュ・ブロ
ックのいずれかを置換する場合、該複数のキャッシュ・
ブロックそれぞれが前記第１の記憶装置及び前記第２の
記憶装置のどちらに属しているかを判定する判定工程の
プログラムコードと、前記判定手段の判定結果に基づい
て、前記複数のキャッシュ・ブロックのいずれかを置換
する置換工程のプログラムコードとを備える。

【００１５】

【発明の実施の形態】以下、図面を参照して本発明の好
適な実施形態を詳細に説明する。 ＜実施形態１＞図１は本発明を実現する実施形態１の計
算機システムの構成を示すブロック図である。

【００１６】尚、図１では、単体で動作し得る計算機を
それぞれノード１、ノード２とし、２つのノードが外部
バス５によって相互に接続されることにより分散共有メ
モリ型のクラスタ型計算機システムを構成する。図１に
おいて、１０、２０は各ノード１、２のプロセッサであ
り、各プロセッサ１０、２０は、プロセッサバス１４、
２４を介してそれぞれキャッシュ・メモリ１１、２１に
接続される。プロセッサバス１４は、プロセッサアドレ
スバス１４１、プロセッサデータバス１４２、プロセッ
サコントロールバス１４３から構成されている。同様
に、プロセッサバス２４は、プロセッサアドレスバス２
４１、プロセッサデータバス２４２、プロセッサコント
ロールバス２４３から構成されている。

【００１７】また、各キャッシュ・メモリ１１、２１は
共有バス１５、２５を介してメモリ１２、２２、及びノ
ード間の接続を司る外部バスインタフェース１３、２３
と接続される。共有バス１５は、共有アドレスバス１５
１、共有データバス１５２、共有コントロールバス１５
３から構成されている。同様に、共有バス２５は、共有
アドレスバス２５１、共有データバス２５２、共有コン
トロールバス２５３から構成されている。

【００１８】１６、２６は各ノード１、２のバスアービ
タであり、それぞれノード１、２の内部におけるキャッ
シュ・メモリ１１、２１と外部バスインタフェース１
３、２３との間での共有バス１５、２５の利用権を調停
するためのものである。外部バスインタフェース（外部
バスＩ／Ｆ）１３、１４には、ノードＩＤレジスタ（Ｎ
ｏｄｅＩＤＲＥＧ．）１３１、２３１が存在する。実施
形態１では、ノードＩＤレジスタ１３１にはノード１を
示す”０”が、ノードＩＤレジスタ２３１にはノード２
を示す”１”がそれぞれ格納されている。

【００１９】次に実施形態１の図１のクラスタ型計算機
システム全体のアドレス空間の割り当てについて、図２
を用いて説明する。図２は実施形態１のクラスタ型計算
機システム全体のアドレス空間の割り当てを示す図であ
る。図２に示すように、ノード１にはアドレス空間とし
て”０ｘ００００００００”〜”０ｘ７ｆｆｆｆｆｆ
ｆ”（０ｘは１６進数を表わす）の領域が、ノード２に
はアドレス空間として”０ｘ８０００００００”〜”０
ｘｆｆｆｆｆｆｆｆ”の領域が割り当てられている。

【００２０】以上の構成において、図１に示すノード１
上のプロセッサ１０は、キャッシュ・メモリ１１及び外
部バス５等を介してノード２上のメモリ２２に対してア
クセスすることができる。また、このノード２上のメモ
リ２２に対するアクセスは、ノード１上のメモリ１２と
同様にアクセスすることができる。そして、ノード１の
プロセッサ１０がノード２上のメモリ２２に実際にアク
セスする場合には、図２に示されるノード２内のアドレ
ス空間を示すメモリアクセスを発行すればよい。しか
し、このキャッシュ・メモリ１１を介してプロセッサ１
０が行うノード２上のメモリ２２へのアクセスは、ノー
ド１、２間の通信等に要するオーバヘッドがかかるた
め、ノード１上のメモリ１２へのアクセスに比べてアク
セス遅延が大きいものとなる。

【００２１】次に実施形態１のキャッシュ・メモリ１
１、２１の詳細な構成について、図３を用いて説明す
る。図３は実施形態１のキャッシュ・メモリの詳細な構
成を示すブロック図である。尚、キャッシュ・メモリ１
１、２１の構成は同様のものであり、ここでは、キャッ
シュ・メモリ１１の詳細な構成として説明する。

【００２２】図３において、キャッシュ・メモリ１１の
本体は、キャッシュ・メモリ制御シーケンサ１１１、ア
ドレスタグ１１２、状態フラグ１１３、ＳＲＡＭ１１
４、比較器１１５、選択器１１６からなる。ここで、Ｓ
ＲＡＭ１１４は、データを保持するためのデータ・ブロ
ックを構成する。アドレスタグ１１２は、データ・ブロ
ックであるＳＲＡＭ１１４のアドレスを保持する。状態
フラグ１１３は、ＳＲＡＭ１１４上のデータの状態を保
持する役割りを果たす。比較器１１５は、アドレスタグ
１１２の内容とプロセッサバス１４、共有バス１５から
もたらされるアドレス及びノードＩＤとを比較する。選
択器１１６は、比較器１１５の比較結果からＳＲＡＭ１
１４内のデータを選択する。キャッシュ・メモリ制御シ
ーケンサ１１１は、これらキャッシュ・メモリ１１内の
各モジュールを制御する。

【００２３】尚、実施形態１のキャッシュ・メモリ１１
は、４ウェイ・セット・アソシアティブの構成をとる
が、これらのキャッシュ・メモリを有する計算機システ
ムの構成は本発明により制限されるものではない。キャ
ッシュ・メモリ１１内の各モジュールは、プロセッサバ
ス１４を介してプロセッサ１０と、プロセッサバスアド
レスインタフェース（プロセッサバスアドレスＩ／Ｆ）
１４４、プロセッサバスデータインタフェース（プロセ
ッサバスデータＩ／Ｆ）１４５、プロセッサバスコント
ロールインタフェース（プロセッサバスコントロールＩ
／Ｆ）アドレス１４６によって接続される。そして、プ
ロセッサ１０からもたらされるアクセス要求に従って、
データの供給等を実行する。

【００２４】また、キャッシュ・メモリ１１内の各モジ
ュールは、共有バス１５に、共有バスアドレスインタフ
ェース（共有バスアドレスＩ／Ｆ）１５４、共有バスデ
ータインタフェース（共有バスデータＩ／Ｆ）１５５、
共有バスコントロールインタフェース（共有バスコント
ロールＩ／Ｆ）１５６によって接続され、プロセッサか
らもたらされるアクセス要求に従ってデータの供給等を
実行する。例えば、キャッシュ・ミスした場合には、デ
ータをメインメモリ１２からキャッシュ・メモリ１１内
にロードしたり、キャッシュ・メモリ１１に蓄えられた
データをプロセッサ１０に供給したり、他のキャッシュ
・メモリからもたらされる情報をもとに、キャッシュ・
メモリ１１内部の状態フラグ１１３を変更したりする。

【００２５】次に実施形態１のアドレスタグ１１２、状
態フラグ１１３、ＳＲＡＭ１１４の詳細な構成につい
て、図４を用いて説明する。図４は実施形態１のアドレ
スタグ、状態フラグ、ＳＲＡＭの詳細な構成を示す図で
ある。図４において、上述したようにキャッシュ・メモ
リ１１は、４ウェイ・セット・アソシアティブの構成を
とっているため、同一のラインアドレス（アドレスーｍ
１７１）で指し示される領域が４つ存在する。そして、
１ラインあたりに含まれるＳＲＡＭ１１４上のデータ
（Ｄ０〜Ｄ３）は、４つの４バイトワード（３２ビッ
ト）となっている。

【００２６】状態フラグ１１３内の「Ｖ」で示される領
域は、それぞれそのアドレスに対応するキャッシングデ
ータが有効（”１”）であるか無効（”０”）であるか
を示している。また、「ＬＲＵ」で示される領域は、Ｌ
ＲＵ管理ビットである。これは、この同一のラインアド
レスに対応する４つのセットのうちで最も最近にアクセ
スされたセットはどれかを指し示すものである。

【００２７】アドレスタグ１１２には、アドレスの上位
２２ビット（ａｄｄｒーｈ’１７３）が格納される。こ
れらの値は、アクセスが発生する度にキャッシュ・メモ
リ制御シーケンサ１１１によって最新の状態を示すよう
に書き換えられる。以上説明した上記の図１〜図４で示
される実施形態１の計算機システムで用いるプロトコル
は、ライトスルー型キャッシュ・メモリの無効化型プロ
トコルを用いるとする。そして、その条件の下で、キャ
ッシュ・ミスが発生した場合のキャッシュ・ブロックの
置換対象の選択を、その原データが保存されるべき記憶
装置へのアクセス遅延の大小を考慮にいれて決定するこ
とができる実施形態１の具体例について説明する。

【００２８】この具体例の概要を説明すると、キャッシ
ュ・ミスが発生し且つキャッシュ・ブロックの置換が必
要となった場合に、その置換対象を決定する際、従来の
ＬＲＵ法の方法に加えて、そのキャッシュ・ブロックを
再びキャッシュ・メモリに読み込むために必要となるア
クセス遅延の大小を考慮して決定する。この決定の実現
は、アクセス遅延の大きな記憶装置に由来するデータブ
ロックのキャッシュ・メモリ内部に存続する優先度を上
昇させ、アクセス遅延の大きなメモリに由来するキャッ
シュ・ブロックが置換対象として選択されにくくするこ
とで実現する。以下、これを実現するキャッシュ・メモ
リを備える計算機システムの動作手順と詳細な構成につ
いて、図１〜図４及び図５〜図７のフローチャートを用
いて説明する。

【００２９】まず、メモリ１２からプロセッサ１０にデ
ータブロックを読み込むＬＯＡＤ命令を実行するの際の
実施形態１のキャッシュ・メモリ１１における制御手順
について、図５を用いて説明する。図５は実施形態１で
実行されるＬＯＡＤ命令が発行された際のキャッシュ・
メモリにおける制御手順を示すフローチャートである。
（以下、ＬＯＡＤ命令がプロセッサ１０から発行された
ものとして説明する。） 図５において、プロセッサ１０から発行されるＬＯＡＤ
命令に対して、プロセッサアドレスバス１４１に出力さ
れているアドレスと、アドレスタグ１１２に格納された
アドレスとを比較器１１５により比較する（ステップＳ
５０１）。そして、キャッシュ・リードヒットした場合
（ステップＳ５０１でＹＥＳ）、キャッシュ・メモリ１
１は、プロセッサ１０に対してＳＲＡＭ１１４よりデー
タを供給する（ステップＳ５０３）。次いで、状態フラ
グ１１３内部のＬＲＵ管理ビットを更新する（ステップ
Ｓ５０４）。

【００３０】一方、プロセッサ１０から発行されるＬＯ
ＡＤ命令に対して、キャッシュ・リードミスした場合
（ステップＳ５０１でＮＯ）、キャッシュ・メモリ１１
は、キャッシュ・ミス処理を行い、メモリ１２からデー
タを読み込む（ステップＳ５０２）。尚、キャッシュ・
ミス処理の詳細については、図６のフローチャートを用
いて説明する。そして、プロセッサ１０に対してＳＲＡ
Ｍ１１４よりデータを供給する（ステップＳ５０３）。
この場合、キャッシュ・リードミスしたデータがキャッ
シュ・メモリ１１に供給されるまで、キャッシュ・メモ
リ１１はプロセッサ１０に対して当該データの供給を行
わない。

【００３１】次に、実施形態１のキャッシュ・ミス処理
の制御手順について、図６を用いて説明する。図６は実
施形態１のキャッシュ・ミス処理の制御手順を示すフロ
ーチャートである。図６において、まず、キャッシュ・
ブロックの置換を行う必要があるか否かを判定する（ス
テップＳ６０１）。キャッシュ・ブロックの置換を行う
必要がある場合（ステップＳ６０１でＹＥＳ）、即ち、
選択されたラインに対応する全てのセットが使用中であ
る場合、使用中であるキャッシュ・ブロックの中の一つ
を選択し、新しく読み込んだデータを置換する対象とす
る（ステップＳ６０２）。尚、どのキャッシュ・ブロッ
クを選択するかの置換アルゴリズムの詳細に関しては後
述する。一方、キャッシュ・ブロックの置換を行う必要
がない場合（ステップＳ６０１でＮＯ）、ステップＳ６
０３に進む。

【００３２】続いて、その状態で、バスアービタ１６に
対して共有バス１５の利用許可要求を発行する（ステッ
プＳ６０３）。キャッシュ・メモリ１１は、共有バス１
５の利用許可を得るまで待機する（ステップＳ６０
４）。共有バス１５の利用許可を得られたら、共有アド
レスバス１５１に対して当該アドレスのアドレスを転送
する。そして、共有コントロールバス１５３に対してリ
ード要求を示す信号等をドライブし、共有データバス１
５２にデータが供給されるのを待つ（ステップＳ６０
５）。

【００３３】メモリ１２により、リード要求及び当該リ
ードアクセスのアドレスが受けつけられて、共有データ
バス１５２にデータが転送される（ステップＳ６０
６）。キャッシュ・メモリ１１は、共有データバス１５
２に転送されたデータをキャッシュ・メモリ１１内のＳ
ＲＡＭ１１４の置換対象として選択された当該データブ
ロックのエントリに登録する（ステップＳ６０７）。

【００３４】次にプロセッサ１０がデータをメモリ１２
上のアドレスで示される領域に書き込むＳＴＯＲＥ命令
を実行する際の実施形態１のキャッシュ・メモリ１１に
おける制御手順について、図７を用いて説明する。図７
は実施形態１で実行されるＳＴＯＲＥ命令が発行された
際のキャッシュ・メモリにおける制御手順を示すフロー
チャートである。（以下、ＳＴＯＲＥ命令がプロセッサ
１０から発行されたものとして説明する。） 尚、実施形態１においては、ＳＴＯＲＥ時のミスにおけ
る処理方式として、ノー・ライト・アロケート方式を採
用している場合を例に挙げて説明する。

【００３５】図７において、プロセッサ１０から発行さ
れるＳＴＯＲＥ命令に対して、プロセッサアドレスバス
１４１に出力されているアドレスとアドレスタグ１１２
に格納されたアドレスとを比較器１１５により比較し、
一致したアドレスがあるか、即ち、キャッシュライトヒ
ットしたか否かを調べる（ステップＳ７０１）。キャッ
シュ・ライトヒットした場合（ステップＳ７０１でＹＥ
Ｓ）、プロセッサ１０が供給するデータを、キャッシュ
・メモリ１１中のＳＲＡＭ１１４は対応するデータブロ
ックに登録する（ステップＳ７０２）。次いで、状態フ
ラグ１１３を所定の値に更新する（ステップＳ７０
３）。

【００３６】同時に、キャッシュ・メモリ１１は、その
ままライトされるデータをメモリ１２に書き込むため、
共有バス１５の利用許可要求を発行する（ステップＳ７
０４）。そして、キャッシュ・メモリ１１は、利用許可
を得るまで待機する（ステップＳ７０５）。共有バス１
５の利用許可を得られたら、共有アドレスバス１５１に
対して当該アドレスのアドレスを転送する。そして、共
有コントロールバス１５３に対してライト要求を示す信
号等をドライブし、共有データバス１５２にデータが供
給されるのを待つ（ステップＳ７０６）。メモリ１２に
より、ライト要求及び当該ライトアクセスのアドレスが
受け付けられて、共有データバス１５２にデータが転送
される（ステップＳ７０７）。そして、メモリ１２は、
共有データバス１５２に転送されたデータを取り込む
（ステップＳ７０８）。

【００３７】一方、キャッシュライトミスした場合（ス
テップＳ７０１でＮＯ）、そのライトされるデータはメ
モリに書き込まれるだけで、メモリ１２の対応ラインが
それによってキャッシュ・メモリ１１にロードされるこ
とはない。その場合、ステップＳ７０４〜ステップＳ７
０８の動作のみが実施される。更に、この際、キャッシ
ュの一貫性保持動作が同時に行われる。

【００３８】即ち、ＳＴＯＲＥ命令が発行されると、キ
ャッシュ・メモリ１１以外のキャッシュ・メモリ、ここ
では、１つのクラスタ型計算機システムを共有メモリ型
システムとして構成しているノード２内部のキャッシュ
・メモリ２１が保持しているデータとの一貫性を取るた
めに、キャッシュ・メモリ２１側においてキャッシュ・
メモリの一貫性保持動作が行われる。

【００３９】この場合、ノード１内部の共有バス１５上
にＳＴＯＲＥ命令に伴うメモリ１２へのライト動作が行
われていることを、ノード１内部の外部バスインタフェ
ース１３が検出する。そして、アドレス情報等を含むそ
の検出に関する情報を外部バス５を通じて、ノード２の
外部バスインタフェース２３に通知する。ノード２の外
部バスインタフェース２３は、通知されたアドレス情報
を元にノード２内部の共有バス２５上にダミーのライト
要求を発行する。

【００４０】これにより、キャッシュ・メモリ２１は共
有バス２５上に行われているライト要求をスヌープする
（ステップＳ７１１）。そして、キャッシュ・メモリ２
１内のアドレスタグ（不図示）を検索する（ステップＳ
７１２）。検索の結果、一致するアドレスタグが存在す
るか否かを判定する。アドレスタグ上に一致するアドレ
スが発見され、それの状態フラグが有効（”１”）を示
していた場合（ステップＳ７１３でＹＥＳ）、その状態
フラグ無効化（”０”に）し、動作を終了する（ステッ
プＳ７１４）。一方、一致するアドレスタグがない場合
（ステップＳ７１３でＮＯ）、そのまま処理を終了す
る。

【００４１】以上の動作が、実施形態１におけるキャッ
シュ・メモリの一貫性保持動作である。次に実施形態１
の各メモリ１２、２２のメモリトランザクション実行時
の状態フラグの状態遷移について、図８を用いて説明す
る。図８は実施形態１の各メモリトランザクション実行
時の状態フラグの状態遷移を示す図である。（以下、キ
ャッシュ・メモリ１１の状態フラグ１１３の状態遷移と
して説明する。） 図８において、状態ＩＮＶＡＬＩＤは、当該状態フラグ
１１３が管理するデータエントリが無効（”０”）であ
ることを示す。状態ＶＡＬＩＤは、当該状態フラグ１１
３が管理するデータエントリが有効（”１”）であるこ
とを示す。

【００４２】ＩＮＶＡＬＩＤ状態のデータに対して、プ
ロセッサ１０からＬＯＡＤ命令が発行された場合、キャ
ッシュ・リード・ミス処理が行なわれ、状態フラグ１１
３はＶＡＬＩＤに遷移する。ＩＮＶＡＬＩＤ状態のデー
タに対して、プロセッサ１０からＳＴＯＲＥ命令が発行
された場合、実施形態１の計算機システムではノー・ラ
イト・アロケート方式を採用しているため、メモリ１２
の対応ラインのキャッシュ・メモリ１１へのロードは行
われず、状態フラグ１１３はＩＮＶＡＬＩＤのままであ
る。

【００４３】ＩＮＶＡＬＩＤ状態のデータに対して、外
部のバスマスタのライト処理に対応してスヌープミスし
た場合は、状態フラグ１１３はＩＮＶＡＬＩＤのままで
ある。ＶＡＬＩＤ状態のデータに対して、プロセッサ１
０からＬＯＡＤ命令が発行された場合及びＳＴＯＲＥ命
令が発行された場合は、キャッシュ・メモリ１１へのヒ
ット／ミスにかかわらず、状態フラグ１１３はＶＡＬＩ
Ｄのままとなる。

【００４４】ＶＡＬＩＤ状態のデータに対して、外部の
バスマスタのライト処理に対応してスヌープヒットした
場合は、一貫性保持動作が実行され、状態フラグ１１３
はＩＮＶＡＬＩＤに遷移する。ＶＡＬＩＤ状態のデータ
に対して、外部のバスマスタのライト処理に対応してス
ヌープミスした場合は、一貫性保持動作が実行されず、
状態フラグ１１３はＶＡＬＩＤのままである。

【００４５】次に、実施形態１の計算機システムの特長
であるキャッシュ・ミス時における置換対象ブロックを
選択する置換アルゴリズムについて、図９、図１０を用
いて詳細に説明する。ここで、状態フラグ１１３の中の
ＬＲＵビットは、図４で説明したように同一のラインア
ドレスに対応する４つのセットのうちで最も最近にアク
セスされたセットはどれかを指し示すためのものであ
る。そこで、アドレスタグ１１２とＬＲＵビットの値の
変化の様子について、図９を用いて説明する。尚、説明
の簡単化のため、ここで行われるアクセスは、全てプロ
セッサ１０のＬＯＡＤ命令発行に伴うリード動作である
ものとする。

【００４６】図９は実施形態１のアドレスタグとＬＲＵ
ビットの遷移の一例を示す部である。図９において、ま
ず、時刻０において、アドレス０ｘ００００００００へ
のアクセスがプロセッサ１０から発行され、その処理の
結果のキャッシュライン０における各セットのアドレス
タグ１１２及びＬＲＵビットの状態が１行目に示されて
いる。この場合は、セット０のアドレスタグ１１２には
アドレス０ｘ００００００００を指し示すための情報
が、セット１のアドレスタグ１１２にはアドレス０ｘ１
０００００００を指し示すための情報が、セット２のア
ドレスタグ１１２にはアドレス０ｘ２０００００００を
指し示すための情報が、セット３のアドレスタグ１１２
にはアドレス０ｘ３０００００００を指し示すための情
報が、それぞれ入っている。そして、過去のアクセスの
履歴により、そのＬＲＵビットは、それぞれセット０が
０、セット１が１、セット２が２、セット３が３を示し
ているものとする。なお、ここで、ＬＲＵビットは数が
小さい程、最近アクセスされていることを示しているも
のとする。この場合、セット３のＬＲＵビットが３であ
るので、ＬＲＵビットとしてはセット３が示されてい
る。

【００４７】尚、ここで、全てのラインは有効（ＶＡＬ
ＩＤ）状態にあるものとする。次に、時刻１において、
キャッシュライン０に関連するアドレス０ｘ３００００
０００へのアクセスが行われる。この場合、キャッシュ
・ヒットして各キャッシュタグは変更されず、ＬＲＵビ
ットがそれぞれ更新される。続いて、時刻２において、
キャッシュライン０に関連するアドレス０ｘ３００００
０００へのアクセスが行われる。この場合、キャッシュ
・ヒットして各キャッシュタグは変更されない。また、
ＬＲＵビットの値もＬＲＵ＝０を値として持つセットが
アクセスされたため、そのまま保たれる。

【００４８】時刻３において、キャッシュライン０に関
連するアドレス０ｘ１０００００００へのアクセスが行
われる。この場合、キャッシュ・ヒットして各キャッシ
ュタグは変更されず、ＬＲＵビットがそれぞれ更新され
る。但し、ＬＲＵ＝２を値として持つセットがアクセス
されたため、ＬＲＵの値が２以下のセットに関してのみ
ＬＲＵビットが更新される。

【００４９】時刻４において、キャッシュライン０に関
連するアドレス０ｘ２０００００００へのアクセスが行
われる。この場合、キャッシュ・ヒットして各キャッシ
ュタグは変更されず、ＬＲＵビットがそれぞれ更新され
る。時刻５において、キャッシュライン０に関連するア
ドレス０ｘ４０００００００へのアクセスが行われる。
この場合、キャッシュ・リードミスするため、キャッシ
ュ・ブロックの置換が実施される。ここでは、時刻４の
処理終了時点においてＬＲＵセットとして示されていた
セット０が置換対象となり、そこのキャッシュタグには
アドレス０ｘ４０００００００を示すための情報が格納
される。同時にＬＲＵビットがそれぞれ更新される。

【００５０】時刻６において、キャッシュライン０に関
連するアドレス０ｘ２０００００００へのアクセスが行
われる。この場合、キャッシュ・ヒットして各キャッシ
ュタグは変更されず、ＬＲＵビットがそれぞれ更新され
る。但し、ＬＲＵ＝１を値として持つセットがアクセス
されたため、ＬＲＵの値が１以下のセットに関しての
み、ＬＲＵビットが更新される。

【００５１】以上説明した図９に示した遷移例では、時
刻５において、キャッシュ・ブロックの置換が行われて
いる。そして、このキャッシュ・ブロックの置換対象を
決定するために実行される実施形態１の計算機システム
の置換アルゴリズムは、上述したＬＲＵ法に加えて、そ
のキャッシュ・ブロックを再びキャッシュ・メモリに読
み込むために必要となるアクセス遅延の大小を考慮する
ために、アクセス遅延の大きな記憶装置に由来するデー
タブロックのキャッシュ内部に存続する優先度を上昇さ
せることによって、アクセス遅延の大きなメモリに由来
するキャッシュ・ブロックが置換対象として選択されに
くくするものである。

【００５２】以下、実施形態１のキャッシュ・ブロック
の置換対象を決定する置換アルゴリズムの制御手順につ
いて、図１０を用いて説明する。図１０は実施形態１の
キャッシュ・ブロックの置換対象を決定する置換アルゴ
リズムの制御手順を示すフローチャートである。図１０
において、まず、キャッシュ・ブロックの置換対象とし
て、再優先されるのは無効フラグ（Ｖ＝”０”）の立っ
ているセットである。そこで、無効フラグ（Ｖ＝”
０”）が存在するか否かを判定する（ステップＳ１００
１）。複数のセットにおいて無効フラグがたっている場
合（ステップＳ１００１でＹＥＳ）、実施形態１では該
当セットの内、セットＮｏ．が最小のものを選択する
（ステップＳ１００２）。

【００５３】一方、無効フラグが立っているセットが存
在しない（全てのセットにおいてＶ＝”１”）場合（ス
テップＳ１００１でＮＯ）、現在有効にキャッシングさ
れているセットの内、どれか一つを置き換えなければな
らない。そこで、実施形態１では、その置き換えを実行
するための基準として２つの基準を用いている。その第
１の基準としてＬＲＵ（Ｌｅａｓｔ‐Ｒｅｃｅｎｔｌｙ
Ｕｓｅｄ）法を用いる。これは、すぐに必要となる情
報を捨ててしまわないように、各セットへのアクセスを
記録し最も長時間使用されなかったセットを置換対象と
して選択するものである。また、図９に示した遷移例の
ように、ＬＲＵビットをそのアクセスの度に更新するこ
とによって最も最近にアクセスされたものから順にＬＲ
Ｕビットを０、１、２、３とそのセットの状態フラグ１
１３に記録している。この場合、最も長時間使用されて
いないものはＬＲＵビット＝３、その次に長期間使用さ
れていないものはＬＲＵビット＝２となる。

【００５４】また、更に置換対象となるセットを選択す
る第２の基準として、その置換対象となったセットのア
ドレスタグ１１２に入っているアドレスがノード内アド
レスを指しているのか、ノード外アドレスを指している
のかを用いている。このノード内アドレスかどうかを判
断するための情報自体は、外部バスインタフェース１３
内のノードＩＤレジスタ１３１に示されている値（ノー
ドＩＤ：”０”又は”１”）を、共有コントロールバス
１５３及び共有バスコントロールインタフェース１５６
を通してＮｏｄｅＩＤ信号１８１として比較器１１５に
与えられる。

【００５５】ここでＮｏｄｅＩＤ信号１８１に示される
ノードＩＤは、図２に示されるアドレス空間の最上位ビ
ットと同一のものである。即ち、ノードＩＤ＝０はノー
ド１を、ノードＩＤ＝１はノード２をそれぞれ示してい
る。このＮｏｄｅＩＤ信号１８１を各アドレスタグ１１
２に入っているアドレスの最上位ビットと比較すること
によって、一致すればノード内部のアドレス、一致しな
ければノード外部のアドレスを示していることが判明す
る。

【００５６】この第１の基準と第２の基準とを組みあわ
せた置換対象のセットを選択する置換アルゴリズムは以
下の通りである。 １． ＬＲＵ＝３を示すセットに蓄えられているアドレ
スタグ１１２が示すアドレスがノード内アドレスである
か否かを検査する（ステップＳ１００３）。ノード内ア
ドレスである場合（ステップＳ１００３でＹＥＳ）、そ
のままＬＲＵ＝３のセットを置換対象として選択する
（ステップＳ１００４）。

【００５７】２． １においてＬＲＵ＝３のセットに蓄
えられているアドレスタグ１１２が示すアドレスがノー
ド外アドレスである場合（ステップＳ１００３でＮ
Ｏ）、第２の置換候補としてＬＲＵ＝２の示すセットの
アドレスタグ１１２が示すアドレスがノード内アドレス
であるか否かを検査する（ステップＳ１００５）。 ３． ＬＲＵ＝２のセットの持つアドレスがノード内ア
ドレスである場合（ステップＳ１００５でＹＥＳ）、そ
のＬＲＵ＝２のセットを置換対象として選択する（ステ
ップＳ１００６）。

【００５８】４． ＬＲＵ＝２のセットの持つアドレス
がノード外アドレスである場合（ステップＳ１００５で
ＮＯ）、第１の置換候補であったＬＲＵ＝３のセットを
置換対象として選択する（ステップＳ１００７）。この
ように、ノード外アドレスをキャッシングしていた場合
は、置換対象として選択されずにキャッシュ・メモリ１
２内部に残る可能性がＬＲＵ法のみを用いて判断してい
た時に比べて１レベル高くなる。

【００５９】以上のような置換アルゴリズムを実行する
ことによって、ノード外のメモリからデータを読み込む
ようなアクセス遅延の大きな記憶装置に由来するデータ
ブロックのキャッシュ・メモリ１１内部に存続する優先
度を上昇させることが可能になる。この結果、計算機シ
ステム全体としての動作速度を向上させ、システム性能
の向上を図ることができる。

【００６０】＜実施形態２＞実施形態２では、単体で動
作し得る計算機システムに拡張用インタフェースを介し
てアクセス遅延の大きい拡張メモリを増設した計算機シ
ステムに対し本発明を適用する。尚、以下に示す実施形
態２の計算機システムは、基本的に実施形態１と重複す
る部分が多いので、以下、図の説明等では実施形態２に
おいて特徴的なところを重点的に述べる。

【００６１】図１１は本発明を実現する実施形態２の計
算機システムの構成を示すブロック図である。図１１に
おいて、１０はプロセッサであり、プロセッサバス１４
を介してキャッシュ・メモリ１１に接続される。また、
キャッシュ・メモリ１１は共有バス１５を介してメモリ
１２及び拡張用インタフェース３３と接続される。拡張
用インタフェース３３の先には拡張バス３５が存在し、
拡張バス３５を介して拡張メモリ３２が配置されてい
る。

【００６２】次に実施形態２の図１１の計算機システム
全体のアドレス空間の割り当てについて、図１２を用い
て説明する。図１２は実施形態２の計算機システム全体
のアドレス空間の割り当てを示す図である。図１２に示
すように、もともとのシステム領域（拡張用ではない領
域）にはアドレス空間として”０ｘ００００００００”
〜”０ｘ７ｆｆｆｆｆｆｆ”（０ｘは１６進数を表わ
す）の領域が、拡張用の領域にはアドレス空間として”
０ｘ８０００００００”〜”０ｘｆｆｆｆｆｆｆｆ”の
領域が割り当てられている。

【００６３】以上の構成において、図１１に示すプロセ
ッサ１０は、キャッシュ・メモリ１１を介してメモリ１
２及び拡張メモリ３２にアクセスすることができる。こ
の際、拡張メモリ３２は拡張用インタフェース３３等を
介してアクセスするため、メモリ１２に比べてアクセス
遅延が大きいものとなる。次に実施形態２のキャッシュ
・メモリ１１の詳細な構成について、図１３を用いて説
明する。

【００６４】図１３は実施形態２のキャッシュ・メモリ
の詳細な構成を示すブロック図である。図１３におい
て、キャッシュ・メモリ１１の本体は、キャッシュ・メ
モリ制御シーケンサ１１１、アドレスタグ１１２、状態
フラグ１１３、ＳＲＡＭ１１４、比較器１１５、選択器
１１６からなる。ここで、構成自体は実施形態１とほと
んど同一であるので詳細な説明は省略する。実施形態２
と実施形態１との主な違いは、キャッシュ・メモリ制御
シーケンサ１１１の内部にキャッシュ・メモリ１１にア
クセスが発生する度にインクリメントを繰り返す２ビッ
トのカウンタが存在していることである。

【００６５】次に実施形態２のアドレスタグ１１２、状
態フラグ１１３、ＳＲＡＭ１１４の詳細な構成につい
て、図１４を用いて説明する。図１４は実施形態２のア
ドレスタグ、状態フラグ、ＳＲＡＭの詳細な構成を示す
図である。図１４において、実施形態２のキャッシュ・
メモリ１１も実施形態と同様、４ウェイ・セット・アソ
シアティブの構成をとっているため、同一のラインアド
レス（アドレス‐ｍ１７１）で指し示される領域が４つ
存在する。そして、１ラインあたりに含まれるＳＲＡＭ
１１４上のデータ（Ｄ０〜Ｄ３）は、４つの４バイトワ
ード（３２ビット）となっている。

【００６６】状態フラグ１１３内のＶで示される領域
は、それぞれそのアドレスに対応するキヤッシングデー
タが有効（”１”）であるか無効（”０”）であるかを
示している。アドレスタグ１１２には、アドレスの上位
２２ビット（ａｄｄｒーｈ’１７３）が格納される。こ
れらの値は、アクセスが発生する度にキャッシュ・メモ
リ制御シーケンサ１１１によって最新の状態を示すよう
に書き換えられる。

【００６７】以上説明した上記の図１１〜図１４で示さ
れる実施形態２の計算機システム用いるプロトコルは、
ライトスルー型キャッシュ・メモリの無効化型プロトコ
ルを用いるとする。そして、その条件の下で、キャッシ
ュ・ミスが発生した場合のキャッシュ・ブロックの置換
対象の選択を、その原データが保存されるべき記憶装置
へのアクセス遅延の大小を考慮にいれて決定することが
できる実施形態２の具体例について説明する。

【００６８】この具体例の概要を説明すると、キャッシ
ュ・ミスが発生し且つキャッシュ・ブロックの置換が必
要となった場合に、その置換対象を決定する際、従来の
ランダム法の方法に加えて、そのキャッシュ・ブロック
を再びキャッシュ・メモリに読み込むために必要となる
アクセス遅延の大小を考慮して決定する。この決定の実
現は、アクセス遅延の大きな記憶装置に由来するデータ
ブロックのキャッシュ・メモリ内部に存続する優先度を
上昇させ、アクセス遅延の大きなメモリに由来するキャ
ッシュ・ブロックが置換対象として選択されにくくする
ことで実現する。以下、これを実現するキャッシュ・メ
モリを備える計算機システムの動作手順と詳細な構成に
ついて、図１１〜図１４及び図１５のフローチャートを
用いて説明する。

【００６９】尚、実施形態２におけるキャッシュ・メモ
リ１１の基本動作及び状態遷移は、実施形態１の図５〜
図８で説明したものと同一であるので割愛する。但し、
実施形態２の計算機システムは実施形態１のような複数
のプロセッサを有するマルチプロセッサの構成をとって
いないので、実施形態１の図７及び図８におけるバスス
ヌープ側の動作は、ここでは発生しない。

【００７０】次に、実施形態２のシステムのキャッシュ
・ブロックの置換対象を決定する置換アルゴリズムの制
御手順について、図１５を用いて説明する。図１５は実
施形態２のキャッシュ・ブロックの置換対象を決定する
置換アルゴリズムの制御手順を示すフローチャートであ
る。図１５において、まず、キャッシュ・ブロックの置
換対象として、再優先されるのは、無効フラグ（Ｖ＝”
０”）の立っているセットである。そこで、無効フラグ
（Ｖ＝”０”）が存在するか否かを判定する（ステップ
Ｓ１５０１）。複数のセットにおいて無効フラグがたっ
ている場合（ステップＳ１５０１でＹＥＳ）、実施形態
２では該当セットの内、セットＮｏ．が最小のものを選
択する（ステップＳ１５０２）。

【００７１】一方、無効フラグが立っているセットが存
在しない（全てのセットにおいてＶ＝”１”）場合（ス
テップＳ１５０１でＮＯ）、現在有効にキャッシングさ
れているセットの内、どれか一つを置き換えなければな
らない。そこで、実施形態２では、その置き換えを実行
するための基準として２つの基準を用いている。その第
１の基準としてランダム法を用いる。これは、置換対象
にどのセットを選ぶかをランダムに選択するものであ
る。それを実現するために、キャッシュ・メモリ制御シ
ーケンサ１１１の中に２ビットのカウンタ１８２を設け
ている。カウンタ１８２は、上述したように、キャッシ
ュ・メモリ１１がアクセスされる度にインクリメントさ
れるようになっている。そして、キャッシュ・ミスが発
生し、選択されたラインに対応する４セット全てが有効
である場合、このカウンタの示す番号のセットが置換の
第１候補として選択される。

【００７２】また、更に置換対象となるセットを選択す
る第２の基準として、その置換対象となったセットのア
ドレスタグ１１２に入っているアドレスがシステム内ア
ドレスを指しているのか、拡張用領域アドレスを指して
いるのかを用いている。この拡張用領域アドレスかどう
かを判断するための情報自体は、比較器１１５内部に保
持されている。即ち、図１２に示されるアドレス空間の
最上位ビットを判断に用いている。つまり、各アドレス
タグ１１２に入っているアドレスの最上位ビットが０で
あればシステム領域、１であれば拡張用領域のアドレス
を示していることが判明する。

【００７３】この第１の基準と第２の基準とを組みあわ
せた置換対象のセットを選択する置換アルゴリズムは以
下の通りである。尚、参考までにカウンタの指し示す番
号として２が与えられている場合にどのセットが選択さ
れるのかを例示する。 １． カウンタ１８２の指し示す番号のセット（ここで
はセット２）に蓄えられているアドレスタグ１１２が示
すアドレスがシステム領域アドレスであるか否かを検査
する（ステップＳ１５０３）。システム領域アドレスで
ある場合（ステップＳ１５０３でＹＥＳ）、そのままカ
ウンタの番号の指し示すセット（ここではセット２）を
置換対象に選択する（ステップＳ１５０４）。

【００７４】２． １においてカウンタ１８２の指し示
す番号のセット（ここではセット２）に蓄えられている
アドレスタグ１１２が示すアドレスが拡張用領域アドレ
スである場合（ステップＳ１５０３でＮＯ）、第２の置
換候補として”カウンタ−１”の指し示すセット（ここ
ではセット１）のアドレスタグ１１２がシステム領域ア
ドレスである否かを検査する（ステップＳ１５０５）。
尚、カウンタ値が０であった場合にはセット３のアドレ
スタグ１１２が検査の対象となる。

【００７５】３． ”カウンタ値−１”の指し示すセッ
ト（ここではセット１）の持つアドレスがシステム領域
アドレスである場合（ステップＳ１５０５でＹＥＳ）、
そのセット（ここではセット１）を置換対象として選択
する（ステップＳ１５０６）。 ４． ”カウンタ値−１”の指し示すセット（ここでは
セット１）の持つアドレスが拡張用領域アドレスである
場合（ステップＳ１５０５でＮＯ）、第１の置換候補で
あったカウンタの指し示す番号のセット（ここではセッ
ト２）を置換対象として選択する（ステップＳ１５０
７）。このように、拡張用領域アドレスをキャッシング
していた場合、置換対象として選ばれずにキャッシュ内
部に残る可能性がランダム法のみを用いて判断していた
時に比べて１レベル高くなることになる。

【００７６】以上のような置換アルゴリズムを実行する
ことによって、システム領域外のメモリからデータを読
み込むようなアクセス遅延の大きな記憶装置に由来する
データブロックのキャッシュ・メモリ１１内部に存続す
る優先度を上昇させることが可能になる。この結果、計
算機システム全体としての動作速度を向上させ、システ
ム性能の向上を図ることができる。

【００７７】以上説明したように、実施形態１、２によ
れば、アクセス遅延の異なる複数の記憶装置を有する計
算機システムにおいて、キャッシュ・メモリのデータブ
ロックの置換を行う際に、よりキャッシング効果が得ら
れるような置換対象となるデータブロックの決定方法を
提供でき、計算機システム全体の処理能力を向上させる
ことができる効果がある。

【００７８】尚、本発明は、複数の機器（例えば、ホス
トコンピュータ、インタフェース機器、リーダ、プリン
タ等）から構成されるシステムに適用しても、一つの機
器からなる装置（例えば、複写機、ファクシミリ装置
等）に適用してもよい。また、本発明の目的は、前述し
た実施形態の機能を実現するソフトウェアのプログラム
コードを記録した記憶媒体を、システムあるいは装置に
供給し、そのシステムあるいは装置のコンピュータ（ま
たはＣＰＵやＭＰＵ）が記憶媒体に格納されたプログラ
ムコードを読出し実行することによっても、達成される
ことは言うまでもない。

【００７９】この場合、記憶媒体から読出されたプログ
ラムコード自体が上述した実施の形態の機能を実現する
ことになり、そのプログラムコードを記憶した記憶媒体
は本発明を構成することになる。プログラムコードを供
給するための記憶媒体としては、例えば、フロッピディ
スク、ハードディスク、光ディスク、光磁気ディスク、
ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモ
リカード、ＲＯＭなどを用いることができる。

【００８０】また、コンピュータが読出したプログラム
コードを実行することにより、前述した実施形態の機能
が実現されるだけでなく、そのプログラムコードの指示
に基づき、コンピュータ上で稼働しているＯＳ（オペレ
ーティングシステム）などが実際の処理の一部または全
部を行い、その処理によって前述した実施の形態の機能
が実現される場合も含まれることは言うまでもない。

【００８１】更に、記憶媒体から読出されたプログラム
コードが、コンピュータに挿入された機能拡張ボードや
コンピュータに接続された機能拡張ユニットに備わるメ
モリに書き込まれた後、そのプログラムコードの指示に
基づき、その機能拡張ボードや機能拡張ユニットに備わ
るＣＰＵなどが実際の処理の一部または全部を行い、そ
の処理によって前述した実施形態の機能が実現される場
合も含まれることは言うまでもない。

【００８２】本発明を上記記憶媒体に適用する場合、そ
の記憶媒体には、先に説明したフローチャートに対応す
るプログラムコードを格納することになるが、簡単に説
明すると、図１６のメモリマップ例に示す各モジュール
を記憶媒体に格納することになる。すなわち、少なくと
も「判定モジュール」および「置換モジュール」の各モ
ジュールのプログラムコードを記憶媒体に格納すればよ
い。

【００８３】尚、「判定モジュール」は、複数のキャッ
シュ・ブロックのいずれかを置換する場合、該複数のキ
ャッシュ・ブロックそれぞれが第１の記憶装置及び第２
の記憶装置のどちらに属しているかを判定する。「置換
モジュール」は、判定結果に基づいて、複数のキャッシ
ュ・ブロックのいずれかを置換する。

【００８４】

【発明の効果】以上説明したように、本発明によれば、
処理能力を向上させることができる情報処理システム及
びその制御方法、情報処理装置を提供できる。

【図面の簡単な説明】

【図１】本発明を実現する実施形態１の計算機システム
の構成を示すブロック図である。

【図２】実施形態１のクラスタ型計算機システム全体の
アドレス空間の割り当てを示す図である。

【図３】実施形態１のキャッシュ・メモリの詳細な構成
を示すブロック図である。

【図４】実施形態１のアドレスタグ、状態フラグ、ＳＲ
ＡＭの詳細な構成を示す図である。

【図５】実施形態１で実行されるＬＯＡＤ命令が発行さ
れた際のキャッシュ・メモリにおける制御手順を示すフ
ローチャートである。

【図６】実施形態１のキャッシュ・ミス処理の制御手順
を示すフローチャートである。

【図７】実施形態１で実行されるＳＴＯＲＥ命令が発行
された際のキャッシュ・メモリにおける制御手順を示す
フローチャートである。

【図８】実施形態１の各メモリトランザクション実行時
の状態フラグの状態遷移を示す図である。

【図９】実施形態１のアドレスタグとＬＲＵビットの遷
移の一例を示す部である。

【図１０】実施形態１のキャッシュ・ブロックの置換対
象を決定する置換アルゴリズムの制御手順を示すフロー
チャートである。

【図１１】本発明を実現する実施形態２の計算機システ
ムの構成を示すブロック図である。

【図１２】実施形態２の計算機システム全体のアドレス
空間の割り当てを示す図である。

【図１３】実施形態２のキャッシュ・メモリの詳細な構
成を示すブロック図である。

【図１４】実施形態２のアドレスタグ、状態フラグ、Ｓ
ＲＡＭの詳細な構成を示す図である。

【図１５】実施形態２のキャッシュ・ブロックの置換対
象を決定する置換アルゴリズムの制御手順を示すフロー
チャートである。

【図１６】本発明の実施形態を実現するプログラムコー
ドを格納した記憶媒体のメモリマップの構造を示す図で
ある。

【符号の説明】

１、２ ノード ５ 外部バス １０、２０ プロセッサ １１、２１ キャッシュ・メモリ １２、２２ メモリ １３、２３ 外部バスインタフェース １４、２４ プロセッサバス １５、２５ 共有バス １６、２６ バスアービタ ３２ 拡張メモリ ３３ 拡張用インタフェース ３５：拡張バス １１１ キャシュ・メモリ制御シーケンサ １１２ アドレスタグ １１３ 状態フラグ １１４ ＳＲＡＭ １１５ 比較器 １１６ 選択器 １１７ キャッシュ・ブロックコントロール １１８ 比較器コントロール信号 １１９ Ｓｅｌｅｃｔ信号 １３１、２３１ ＮｏｄｅＩＤレジスタ １４１ プロセッサアドレスバス １４２ プロセッサデータバス １４３ プロセッサコントロールバス １４４ プロセッサバスアドレスインタフェース １４５ プロセッサバスデータインタフェース １４６ プロセッサバスコントロールインタフェース １５１ 共有アドレスバス １５２ 共有データバス １５３ 共有コントロールバス １５４ 共有バスアドレスインタフェース １５５ 共有バスデータインタフェース １５６ 共有バスコントロールインタフェース １７０ アドレスーｈ １７１ アドレスーｍ １７２ アドレスーｌ １７３ アドレスーｈ’ １７４ データ １７５ データ’ １７６ ステータス信号 １７７ 共有バスインタフェースコントロール信号 １７８ プロセッサバスインタフェースコントロール信
号 １７９ Ｌ‐Ｃｏｎｔ信号 １８０ Ｓ‐Ｃｏｎｔ信号 １８１ ＮｏｄｅＩＤ信号 １８２ カウンタ ３５１ 拡張アドレスバス ３５２ 拡張データバス ３５３ 拡張コントロールバス

Claims (17)

【特許請求の範囲】
1. 【請求項１】 第１の記憶装置と、該第１の記憶装置よ
   りもアクセス遅延が大きい第２の記憶装置と、複数のキ
   ャッシュ・ブロックを有するキャッシュ・メモリとを備
   える情報処理システムであって、 前記複数のキャッシュ・ブロックのいずれかを置換する
   場合、該複数のキャッシュ・ブロックそれぞれが前記第
   １の記憶装置及び前記第２の記憶装置のどちらに属して
   いるかを判定する判定手段と、 前記判定手段の判定結果に基づいて、前記複数のキャッ
   シュ・ブロックのいずれかを置換する置換手段とを備え
   ることを特徴とする情報処理システム。
2. 【請求項２】 前記置換手段による置換対象としない優
   先度を前記複数のキャッシュ・ブロック毎に保持する保
   持手段を更に備え、 前記判定手段の判定結果及び前記保持手段が保持する優
   先度に基づいて、前記置換手段は前記複数のキャッシュ
   ・ブロックのいずれかを置換することを特徴とする請求
   項１に記載の情報処理システム。
3. 【請求項３】 前記置換手段による置換されるキャッシ
   ュ・ブロックの優先度に基づいて、該キャッシュ・ブロ
   ックを含む前記複数のキャッシュ・ブロックの優先度を
   変更する変更手段を更に備えることを特徴とする請求項
   ２に記載の情報処理システム。
4. 【請求項４】 前記変更手段は、前記置換手段によって
   置換されるキャッシュ・ブロックの優先度を最上位に変
   更し、該優先度と同じあるいはそれ以下の優先度を持つ
   キャッシュ・ブロックの優先度を上昇させることを特徴
   する請求項３に記載の情報処理システム。
5. 【請求項５】 前記複数のキャッシュ・ブロックそれぞ
   れ保持するデータが有効であるか否かを示す情報を管理
   する管理手段を更に備え、 前記判定手段の判定結果及び前記保持手段が保持する優
   先度及び前記管理手段が管理する情報に基づいて、前記
   置換手段は前記複数のキャッシュ・ブロックのいずれか
   を置換することを特徴とする請求項２に記載の情報処理
   システム。
6. 【請求項６】 有効なデータを保持していないキャッシ
   ュ・ブロックを示す情報を前記管理手段が管理し、かつ
   前記複数のキャッシュ・ブロックのいずれかを置換する
   場合は、前記置換手段は該有効なデータを保持していな
   いキャッシュ・ブロックを置換することを特徴とする請
   求項５に記載の情報処理システム。
7. 【請求項７】 前記判定手段は、前記第１の記憶装置と
   前記第２の記憶装置それぞれに割り当てられたアドレス
   空間に基づいて、前記複数のキャッシュ・ブロックそれ
   ぞれが前記第１の記憶装置及び前記第２の記憶装置のど
   ちらに属しているかを判定することを特徴とする請求項
   １に記載の情報処理システム。
8. 【請求項８】 第１の記憶装置と、該第１の記憶装置よ
   りもアクセス遅延が大きい第２の記憶装置と、複数のキ
   ャッシュ・ブロックを有するキャッシュ・メモリとを備
   える情報処理システムの制御方法であって、 前記複数のキャッシュ・ブロックのいずれかを置換する
   場合、該複数のキャッシュ・ブロックそれぞれが前記第
   １の記憶装置及び前記第２の記憶装置のどちらに属して
   いるかを判定する判定工程と、 前記判定工程の判定結果に基づいて、前記複数のキャッ
   シュ・ブロックのいずれかを置換する置換工程とを備え
   ることを特徴とする情報処理システムの制御方法。
9. 【請求項９】 前記置換工程による置換対象としない優
   先度を前記複数のキャッシュ・ブロック毎に保持する保
   持工程を更に備え、 前記判定工程の判定結果及び前記保持工程で保持される
   優先度に基づいて、前記置換工程は前記複数のキャッシ
   ュ・ブロックのいずれかを置換することを特徴とする請
   求項８に記載の情報処理システムの制御方法。
10. 【請求項１０】 前記置換工程による置換されるキャッ
    シュ・ブロックの優先度に基づいて、該キャッシュ・ブ
    ロックを含む前記複数のキャッシュ・ブロックの優先度
    を変更する変更工程を更に備えることを特徴とする請求
    項９に記載の情報処理システムの制御方法。
11. 【請求項１１】 前記変更工程は、前記置換工程によっ
    て置換されるキャッシュ・ブロックの優先度を最上位に
    変更し、該優先度と同じあるいはそれ以下の優先度を持
    つキャッシュ・ブロックの優先度を上昇させることを特
    徴する請求項１０に記載の情報処理システムの制御方
    法。
12. 【請求項１２】 前記複数のキャッシュ・ブロックそれ
    ぞれ保持するデータが有効であるか否かを示す情報を管
    理する管理工程を更に備え、 前記判定工程の判定結果及び前記保持工程で保持される
    優先度及び前記管理工程で管理される情報に基づいて、
    前記置換工程は前記複数のキャッシュ・ブロックのいず
    れかを置換することを特徴とする請求項９に記載の情報
    処理システムの制御方法。
13. 【請求項１３】 有効なデータを保持していないキャッ
    シュ・ブロックを示す情報が前記管理工程で管理され、
    かつ前記複数のキャッシュ・ブロックのいずれかを置換
    する場合は、前記置換工程は該有効なデータを保持して
    いないキャッシュ・ブロックを置換することを特徴とす
    る請求項１２に記載の情報処理システムの制御方法。
14. 【請求項１４】 前記判定工程は、前記第１の記憶装置
    と前記第２の記憶装置それぞれに割り当てられたアドレ
    ス空間に基づいて、前記複数のキャッシュ・ブロックそ
    れぞれが前記第１の記憶装置及び前記第２の記憶装置の
    どちらに属しているかを判定することを特徴とする請求
    項８に記載の情報処理システムの制御方法。
15. 【請求項１５】 第１の記憶装置と、該第１の記憶装置
    よりもアクセス遅延が大きい第２の記憶装置と、複数の
    キャッシュ・ブロックを有するキャッシュ・メモリとを
    備える情報処理装置であって、 前記複数のキャッシュ・ブロックのいずれかを置換する
    場合、該複数のキャッシュ・ブロックそれぞれが前記第
    １の記憶装置及び前記第２の記憶装置のどちらに属して
    いるかを判定する判定手段と、 前記判定手段の判定結果に基づいて、前記複数のキャッ
    シュ・ブロックのいずれかを置換する置換手段と、 を備えることを特徴とする情報処理装置。
16. 【請求項１６】 前記置換手段による置換対象としない
    優先度を前記複数のキャッシュ・ブロック毎に保持する
    保持手段を更に備え、 前記判定手段の判定結果及び前記保持手段が保持する優
    先度に基づいて、前記置換手段は前記複数のキャッシュ
    ・ブロックのいずれかを置換することを特徴とする請求
    項１５に記載の情報処理装置。
17. 【請求項１７】 第１の記憶装置と、該第１の記憶装置
    よりもアクセス遅延が大きい第２の記憶装置と、複数の
    キャッシュ・ブロックを有するキャッシュ・メモリとを
    備える情報処理システムの制御のプログラムコードが格
    納されたコンピュータ可読メモリであって、 前記複数のキャッシュ・ブロックのいずれかを置換する
    場合、該複数のキャッシュ・ブロックそれぞれが前記第
    １の記憶装置及び前記第２の記憶装置のどちらに属して
    いるかを判定する判定工程のプログラムコードと、 前記判定手段の判定結果に基づいて、前記複数のキャッ
    シュ・ブロックのいずれかを置換する置換工程のプログ
    ラムコードとを備えることを特徴とするコンピュータ可
    読メモリ。