JPH10283261A - キャッシュ・エントリの予約処理方法及び装置 - Google Patents
キャッシュ・エントリの予約処理方法及び装置Info
- Publication number
- JPH10283261A JPH10283261A JP10059385A JP5938598A JPH10283261A JP H10283261 A JPH10283261 A JP H10283261A JP 10059385 A JP10059385 A JP 10059385A JP 5938598 A JP5938598 A JP 5938598A JP H10283261 A JPH10283261 A JP H10283261A
- Authority
- JP
- Japan
- Prior art keywords
- block
- cache
- value
- reservation
- eviction
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/12—Replacement control
- G06F12/121—Replacement control using replacement algorithms
- G06F12/126—Replacement control using replacement algorithms with special data handling, e.g. priority of data or instructions, handling errors or pinning
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【課題】 マルチ・プロセッサ・コンピュータ・システ
ムのキャッシュ・エントリ予約を処理する改善された方
法の提供。 【解決手段】 処理装置のキャッシュに値を格納する方
法は、キャッシュの第１のブロックに第１の値をロード
する段階と、第１の値が予約されるものであることを表
示する段階と、キャッシュの別のブロックに他の値を少
なくとも一つロードする段階と、もし第１の値が予約さ
れていることがなおも表示されているとするならば、選
択されたブロックは第１のブロックとは別のブロックで
あるとするキャッシュの選択されたブロックを追い出す
段階と、追い出す段階の後に、選択されたブロックに新
しい値をロードする段階とを一般に有すること特徴とす
る。
ムのキャッシュ・エントリ予約を処理する改善された方
法の提供。 【解決手段】 処理装置のキャッシュに値を格納する方
法は、キャッシュの第１のブロックに第１の値をロード
する段階と、第１の値が予約されるものであることを表
示する段階と、キャッシュの別のブロックに他の値を少
なくとも一つロードする段階と、もし第１の値が予約さ
れていることがなおも表示されているとするならば、選
択されたブロックは第１のブロックとは別のブロックで
あるとするキャッシュの選択されたブロックを追い出す
段階と、追い出す段階の後に、選択されたブロックに新
しい値をロードする段階とを一般に有すること特徴とす
る。
Description
【０００１】
【発明の属する技術分野】本発明は、一般にコンピュー
タ・システム関するもので、特にコンピュータ・プロセ
ッサによって使用されたキャッシュからの追い出しを制
御する方法に関する。
タ・システム関するもので、特にコンピュータ・プロセ
ッサによって使用されたキャッシュからの追い出しを制
御する方法に関する。
【０００２】
【従来の技術】従来の多重プロセッサ・コンピュータ・
システム１０の基本構造を図１に示す。コンピュータ・
システム１０はいくつかの処理装置（そのうちの２つを
符号１２ａおよび１２ｂとして図示）を持ち、該処理装
置は入出力（Ｉ／Ｏ）装置（例えば、ディスプレイ・モ
ニタ、キーボード、および固定記憶装置）、プログラム
命令を実行するために処理装置によって使用されるメモ
リ素子１６（例えば、ランダム・アクセス・メモリまた
はＲＡＭ）、およびコンピュータの電源が最初にオンに
なるたびに周辺機器の１つ（通常は固定記憶装置）から
オペレーティング・システムをシークしてロードするこ
とを第１の目的とするファームウエア１８等の周辺機器
に接続されている。また、処理装置１２ａおよび１２ｂ
は、これらの周辺機器と種々の手段、例えば汎用インタ
フェースまたはバス２０によってデータのやりとりを行
う。コンピュータ・システム１０は、モデムまたはプリ
ンタへの接続のためのシリアルまたはパラレル・ポート
等、多くの追加のコンポーネントを持つものであっても
よい。 当業者は、図１のブロック図に示されたコンポ
ーネントとともに他のコンポーネント、例えばビデオ表
示用モニタを制御するために使用可能なディスプレイ・
アダプタやメモリ１６へのアクセスに使用するメモリ・
コントローラ等を用いることが可能であることをさらに
理解することができよう。また、コンピュータは２を上
回る数の処理装置を持つことができる。
システム１０の基本構造を図１に示す。コンピュータ・
システム１０はいくつかの処理装置（そのうちの２つを
符号１２ａおよび１２ｂとして図示）を持ち、該処理装
置は入出力（Ｉ／Ｏ）装置（例えば、ディスプレイ・モ
ニタ、キーボード、および固定記憶装置）、プログラム
命令を実行するために処理装置によって使用されるメモ
リ素子１６（例えば、ランダム・アクセス・メモリまた
はＲＡＭ）、およびコンピュータの電源が最初にオンに
なるたびに周辺機器の１つ（通常は固定記憶装置）から
オペレーティング・システムをシークしてロードするこ
とを第１の目的とするファームウエア１８等の周辺機器
に接続されている。また、処理装置１２ａおよび１２ｂ
は、これらの周辺機器と種々の手段、例えば汎用インタ
フェースまたはバス２０によってデータのやりとりを行
う。コンピュータ・システム１０は、モデムまたはプリ
ンタへの接続のためのシリアルまたはパラレル・ポート
等、多くの追加のコンポーネントを持つものであっても
よい。 当業者は、図１のブロック図に示されたコンポ
ーネントとともに他のコンポーネント、例えばビデオ表
示用モニタを制御するために使用可能なディスプレイ・
アダプタやメモリ１６へのアクセスに使用するメモリ・
コントローラ等を用いることが可能であることをさらに
理解することができよう。また、コンピュータは２を上
回る数の処理装置を持つことができる。
【０００３】対称型マルチ・プロセッサ（ＳＭＰ）コン
ピュータでは、処理装置のすべてが概略同一である。す
なわち、コンピュータを操作するために使用される命令
およびプロトコルのセットまたはサブセットが共通であ
り、一般に同一のアーキテクチャを持つ。典型的なアー
キテクチャが図１に示されている。処理装置は、コンピ
ュータを操作するためにプログラム命令を実行する複数
のレジスタおよび実行ユニットを持つプロセッサ・コア
２２を有する。処理装置の一例として、International
Business Machines Corporation（ＩＢＭ）が市場に出
したＰｏｗｅｒＰＣ（商標）−６０４シリーズのプロセ
ッサが挙げられる。また、処理装置は高速メモリ素子を
使用して実装された命令キャッシュ２４およびデータ・
キャッシュ２６等のキャッシュを１つ以上持つ。キャッ
シュは、プロセッサによって繰り返しアクセスされるか
もしれない値を一時的に格納し、メモリ１６から値をロ
ードするより長いステップを避けることで処理速度を上
げることに一般に使われる。これらのキャッシュは、単
一の集積回路素子２８上にプロセッサ・コアとともに集
積実装された場合に「オン・ボード」と呼ばれる。それ
ぞれのキャッシュは、プロセッサ・コアとキャッシュ・
メモリとの間のデータ転送を管理するキャッシュ・コン
トロール（不図示）に対応している。
ピュータでは、処理装置のすべてが概略同一である。す
なわち、コンピュータを操作するために使用される命令
およびプロトコルのセットまたはサブセットが共通であ
り、一般に同一のアーキテクチャを持つ。典型的なアー
キテクチャが図１に示されている。処理装置は、コンピ
ュータを操作するためにプログラム命令を実行する複数
のレジスタおよび実行ユニットを持つプロセッサ・コア
２２を有する。処理装置の一例として、International
Business Machines Corporation（ＩＢＭ）が市場に出
したＰｏｗｅｒＰＣ（商標）−６０４シリーズのプロセ
ッサが挙げられる。また、処理装置は高速メモリ素子を
使用して実装された命令キャッシュ２４およびデータ・
キャッシュ２６等のキャッシュを１つ以上持つ。キャッ
シュは、プロセッサによって繰り返しアクセスされるか
もしれない値を一時的に格納し、メモリ１６から値をロ
ードするより長いステップを避けることで処理速度を上
げることに一般に使われる。これらのキャッシュは、単
一の集積回路素子２８上にプロセッサ・コアとともに集
積実装された場合に「オン・ボード」と呼ばれる。それ
ぞれのキャッシュは、プロセッサ・コアとキャッシュ・
メモリとの間のデータ転送を管理するキャッシュ・コン
トロール（不図示）に対応している。
【０００４】キャッシュ、例えばキャッシュ３０を処理
装置１２ａに追加することができる。このキャッシュ３
０はオン・ボード・キャッシュである１次（Ｌ１）のキ
ャッシュ２４および２６をサポートすることから２次
（Ｌ２）のキャッシュと呼ばれる。別の言い方をする
と、キャッシュ３０はメモリ１６とオン・ボード・キャ
ッシュとの媒介として動作し、オン・ボード・キャッシ
ュよりもかなり多くの情報（命令およびデータ）を格納
することができるが、アクセス時間が長い。例えば、キ
ャッシュ３０を２５６または５１２キロバイトの記憶容
量を持つチップとし、一方プロセッサを全体の容量が６
４キロバイトのオン・ボード・キャッシュを持つＩＢＭ
のＰｏｗｅｒＰＣ（登録商標）−６０４とすることがで
きよう。キャッシュ３０はバス２０に接続し、メモリ１
６からプロセッサ・コア２２への情報の転送すべてがキ
ャッシュ３０を通らなければならない。図１に示したキ
ャッシュの階層は２レベルのみであるけれども、連続的
に接続された多くのレベルのキャッシュを有する多重レ
ベル・キャッシュ階層を提供することができる。
装置１２ａに追加することができる。このキャッシュ３
０はオン・ボード・キャッシュである１次（Ｌ１）のキ
ャッシュ２４および２６をサポートすることから２次
（Ｌ２）のキャッシュと呼ばれる。別の言い方をする
と、キャッシュ３０はメモリ１６とオン・ボード・キャ
ッシュとの媒介として動作し、オン・ボード・キャッシ
ュよりもかなり多くの情報（命令およびデータ）を格納
することができるが、アクセス時間が長い。例えば、キ
ャッシュ３０を２５６または５１２キロバイトの記憶容
量を持つチップとし、一方プロセッサを全体の容量が６
４キロバイトのオン・ボード・キャッシュを持つＩＢＭ
のＰｏｗｅｒＰＣ（登録商標）−６０４とすることがで
きよう。キャッシュ３０はバス２０に接続し、メモリ１
６からプロセッサ・コア２２への情報の転送すべてがキ
ャッシュ３０を通らなければならない。図１に示したキ
ャッシュの階層は２レベルのみであるけれども、連続的
に接続された多くのレベルのキャッシュを有する多重レ
ベル・キャッシュ階層を提供することができる。
【０００５】キャッシュは、種々の命令およびデータ値
を個別に格納する多くの「ブロック」を有する。どのよ
うなキャッシュのブロックでも「セット」と呼ばれるブ
ロック群にグループ分けされる。セットは、所定のメモ
リ・ブロックが常駐することができるブロックの集まり
である。所定のメモリ・ブロックのいずれについても、
プリセット・マッピング機能にもとづいてブロックがマ
ップされるキャッシュ内の単一のセットが存在する。一
セットに含まれるブロックの数は、キャッシュの連想性
と呼ばれる（例えば、任意のメモリ・ブロックに関し
て、２方向セット連想手段、メモリ・ブロックがマップ
されるキャッシュ内にブロックが２つある）。しかし、
メイン・メモリのいくつかの異なったブロックを任意の
セットにマップすることができる。
を個別に格納する多くの「ブロック」を有する。どのよ
うなキャッシュのブロックでも「セット」と呼ばれるブ
ロック群にグループ分けされる。セットは、所定のメモ
リ・ブロックが常駐することができるブロックの集まり
である。所定のメモリ・ブロックのいずれについても、
プリセット・マッピング機能にもとづいてブロックがマ
ップされるキャッシュ内の単一のセットが存在する。一
セットに含まれるブロックの数は、キャッシュの連想性
と呼ばれる（例えば、任意のメモリ・ブロックに関し
て、２方向セット連想手段、メモリ・ブロックがマップ
されるキャッシュ内にブロックが２つある）。しかし、
メイン・メモリのいくつかの異なったブロックを任意の
セットにマップすることができる。
【０００６】所定のキャッシュのためのセットにあるブ
ロックのすべてが満たされ、かつキャッシュが要求を受
け取る場合、完全なセットにマップされるメモリ・ロケ
ーションに対する「読出し」または「書込み」であろう
と、キャッシュはセットに現在あるブロックの一つを
「追い出し（ｅｖｉｃｔ）」しなければならない。キャ
ッシュは、当業者に知られている数多くの手段（最低使
用頻度（ＬＲＵ）、ランダム、疑似ＬＲＵ）の一つによ
って追い出されるブロックを選択する。もし選択された
ブロックが修飾されるならば、そのデータは別のキャッ
シュ（Ｌ１またはオン・ボード・キャッシュの場合）あ
るいはメイン・メモリ（図１の２レベル・アーキテクチ
ャに図示されたように、Ｌ２キャッシュの場合）であろ
うメモリ階層の次にもっとも低いレベルに書込みされ
る。しかし、もし選ばれたブロック内のデータが修飾さ
れなければ、ブロックはただ放棄され、階層の次の最も
低いレベルに書込みされない。ブロックを階層の１つの
レベルから取り除くこのプロセスは「追い出し」として
知られている。このプロセスの終わりにおいて、もはや
キャッシュは追い出されたブロックを持たない。
ロックのすべてが満たされ、かつキャッシュが要求を受
け取る場合、完全なセットにマップされるメモリ・ロケ
ーションに対する「読出し」または「書込み」であろう
と、キャッシュはセットに現在あるブロックの一つを
「追い出し（ｅｖｉｃｔ）」しなければならない。キャ
ッシュは、当業者に知られている数多くの手段（最低使
用頻度（ＬＲＵ）、ランダム、疑似ＬＲＵ）の一つによ
って追い出されるブロックを選択する。もし選択された
ブロックが修飾されるならば、そのデータは別のキャッ
シュ（Ｌ１またはオン・ボード・キャッシュの場合）あ
るいはメイン・メモリ（図１の２レベル・アーキテクチ
ャに図示されたように、Ｌ２キャッシュの場合）であろ
うメモリ階層の次にもっとも低いレベルに書込みされ
る。しかし、もし選ばれたブロック内のデータが修飾さ
れなければ、ブロックはただ放棄され、階層の次の最も
低いレベルに書込みされない。ブロックを階層の１つの
レベルから取り除くこのプロセスは「追い出し」として
知られている。このプロセスの終わりにおいて、もはや
キャッシュは追い出されたブロックを持たない。
【０００７】本発明に関連する対称型マルチ・プロセッ
サの別の態様は、一つのタスクに取り組んでいるプロセ
ッサ間の協同を可能とさせるためにシステム内の種々の
プロセッサの動作を同期させる手段が必要であることに
関係する。これを成し遂げるために、今日のプロセッサ
のほとんどは同期に対処する命令を明示する該プロセッ
サの命令セットを含む。特に、ＰｏｗｅｒＰＣ（登録商
標）命令セットは、"Ｌｗｒｘ"および"ｓｔｃｘ"と呼ば
れる２つの命令を提供する。これらの命令は２つの形式
になる。すなわち、３２ビットのインプリメンテーショ
ンのための"ｌｗａｒｘ命令"および"ｓｗｔｃｘ"と、６
４ビットのインプリメンテーションのための"ｌｄａｒ
ｘ"および"ｓｔｄｃｘ"とである。今後、用語"ｌｗａｒ
ｘ命令"および"ｓｔｗｃｘ命令"を用いてどちらか一方
のインプリメンテーション（ｌｄａｒｘおよびｓｔｄｃ
ｘ命令は本質的に同一のセマンティックスを持ち、例外
としてｌｄａｒｘおよびｓｔｄｃｘは８バイト量で動作
し、ｌｗａｒｘ命令およびｓｔｄｃｘは４バイト量で動
作する）のための命令を示すのに使われる。これらの命
令は、同期プリミティブを形成するのに役立つ。
サの別の態様は、一つのタスクに取り組んでいるプロセ
ッサ間の協同を可能とさせるためにシステム内の種々の
プロセッサの動作を同期させる手段が必要であることに
関係する。これを成し遂げるために、今日のプロセッサ
のほとんどは同期に対処する命令を明示する該プロセッ
サの命令セットを含む。特に、ＰｏｗｅｒＰＣ（登録商
標）命令セットは、"Ｌｗｒｘ"および"ｓｔｃｘ"と呼ば
れる２つの命令を提供する。これらの命令は２つの形式
になる。すなわち、３２ビットのインプリメンテーショ
ンのための"ｌｗａｒｘ命令"および"ｓｗｔｃｘ"と、６
４ビットのインプリメンテーションのための"ｌｄａｒ
ｘ"および"ｓｔｄｃｘ"とである。今後、用語"ｌｗａｒ
ｘ命令"および"ｓｔｗｃｘ命令"を用いてどちらか一方
のインプリメンテーション（ｌｄａｒｘおよびｓｔｄｃ
ｘ命令は本質的に同一のセマンティックスを持ち、例外
としてｌｄａｒｘおよびｓｔｄｃｘは８バイト量で動作
し、ｌｗａｒｘ命令およびｓｔｄｃｘは４バイト量で動
作する）のための命令を示すのに使われる。これらの命
令は、同期プリミティブを形成するのに役立つ。
【０００８】ｌｗａｒｘ命令は、メモリの一列に並べら
れた４バイト・ワードをプロセッサのレジスタにロード
する。さらに、ｌｗａｒｘ命令は、アクセスされたメモ
リのワードを含んでいるメモリのブロック上に「予約」
を入れる。予約には、ブロックのアドレスとフラグとが
含まれる。このフラグはアクティブにされ、ブロックの
アドアレスはｌｗａｒｘ命令が参照されたメモリのワー
ドを成功裏に読込む場合にロードされる。もし予約が有
効（フラグがアクティブ）ならば、プロセッサおよびメ
モリの階層は予約が存在するブロックに書込んでもよい
任意の操作のためにシステム全体を協同的にモニタする
ように義務づけられる。もし、そのような書込みが生じ
るならば、予約に含まれるフラグはリセットされる。予
約フラグはｓｔｗｃｘ命令の挙動を制御するために使用
される。
れた４バイト・ワードをプロセッサのレジスタにロード
する。さらに、ｌｗａｒｘ命令は、アクセスされたメモ
リのワードを含んでいるメモリのブロック上に「予約」
を入れる。予約には、ブロックのアドレスとフラグとが
含まれる。このフラグはアクティブにされ、ブロックの
アドアレスはｌｗａｒｘ命令が参照されたメモリのワー
ドを成功裏に読込む場合にロードされる。もし予約が有
効（フラグがアクティブ）ならば、プロセッサおよびメ
モリの階層は予約が存在するブロックに書込んでもよい
任意の操作のためにシステム全体を協同的にモニタする
ように義務づけられる。もし、そのような書込みが生じ
るならば、予約に含まれるフラグはリセットされる。予
約フラグはｓｔｗｃｘ命令の挙動を制御するために使用
される。
【０００９】ｓｔｗｃｘ命令はｌｗａｒｘ命令の対応物
である。ｓｔｗｃｘ命令は、最初に予約フラグが有効で
あるかどうかを決定する。もし有効であるならば、指定
されたメモリの４バイトのワードに対する格納を実行
し、該格納が成功したことを示すために条件コード・レ
ジスタをセットし、さらに予約フラグをリセットする。
一方、もし予約の予約フラグが有効でなければ、ｓｔｗ
ｃｘ命令はメモリへの格納を実施せず、格納失敗を示す
条件コード・レジスタをセットする。ｓｔｗｃｘ命令
は、格納が予約フラグの状態を条件としていることか
ら、しばしば「条件付格納」と呼ばれる。
である。ｓｔｗｃｘ命令は、最初に予約フラグが有効で
あるかどうかを決定する。もし有効であるならば、指定
されたメモリの４バイトのワードに対する格納を実行
し、該格納が成功したことを示すために条件コード・レ
ジスタをセットし、さらに予約フラグをリセットする。
一方、もし予約の予約フラグが有効でなければ、ｓｔｗ
ｃｘ命令はメモリへの格納を実施せず、格納失敗を示す
条件コード・レジスタをセットする。ｓｔｗｃｘ命令
は、格納が予約フラグの状態を条件としていることか
ら、しばしば「条件付格納」と呼ばれる。
【００１０】ｌｗａｒｘ／ｓｔｗｃｘ命令シーケンスの
根底にある普遍的概念は、プロセッサがメモリ・ロケー
ションを読出し、該ロケーションをある種の方法でもっ
て修飾し、さらにｓｔｗｃｘ命令 が完了するまでｌｗ
ａｒｘ命令が実行された時点から他のプロセッサがメモ
リ・ロケーションを変更しないことを確かめる一方でメ
モリに新しい値を格納する。そのようなシーケンスで
は、プロセッサはロケーションを読出し、それを修飾
し、さらに該ロケーションに対して書込みする他のプロ
セッサによる割込みなしで新しい値を書込むことが可能
であったことから、一般に「アトミック読出し修飾書込
み（atomic read−modify−write）」シーケンスと呼ば
れる。ｌｗａｒｘ／ｓｔｗｃｘシーケンスからなる動作
は、割込みの起こらないシーケンスとしては行われな
い。しかしどちらかと言うと、プロセッサがｌｗａｒｘ
命令を実行した後で成功裏にｓｔｗｃｘ命令を完了する
ことが可能であるという事実は、読出し／修飾／書込み
シーケンスが実際にあたかも極めて小さいかのように行
われることをプログラマに保証する。このｌｗａｒｘ／
ｓｔｗｃｘシーケンスのアトミック特性は、当業者によ
く知られたいくつかの同期プリミティブの実行に使用す
ることができる。
根底にある普遍的概念は、プロセッサがメモリ・ロケー
ションを読出し、該ロケーションをある種の方法でもっ
て修飾し、さらにｓｔｗｃｘ命令 が完了するまでｌｗ
ａｒｘ命令が実行された時点から他のプロセッサがメモ
リ・ロケーションを変更しないことを確かめる一方でメ
モリに新しい値を格納する。そのようなシーケンスで
は、プロセッサはロケーションを読出し、それを修飾
し、さらに該ロケーションに対して書込みする他のプロ
セッサによる割込みなしで新しい値を書込むことが可能
であったことから、一般に「アトミック読出し修飾書込
み（atomic read−modify−write）」シーケンスと呼ば
れる。ｌｗａｒｘ／ｓｔｗｃｘシーケンスからなる動作
は、割込みの起こらないシーケンスとしては行われな
い。しかしどちらかと言うと、プロセッサがｌｗａｒｘ
命令を実行した後で成功裏にｓｔｗｃｘ命令を完了する
ことが可能であるという事実は、読出し／修飾／書込み
シーケンスが実際にあたかも極めて小さいかのように行
われることをプログラマに保証する。このｌｗａｒｘ／
ｓｔｗｃｘシーケンスのアトミック特性は、当業者によ
く知られたいくつかの同期プリミティブの実行に使用す
ることができる。
【００１１】図１は、キャッシュ２６および３０にそれ
ぞれが関連した予約ユニット３２および３２を示す。こ
れらのユニットは、予約、アドレスおよびフラグの両方
を含むもので、予約グラニュール・アドレス内の任意の
書込み動作について各々のバス３６および３８をそれぞ
れが「スヌープ」（モニタ）し、そのような動作が検出
された場合に関連予約フラグを無効にする（もし予約を
無効にする動作が低位レベルのキャッシュによって検出
されるならば、それは高位レベルのキャッシュに上げら
れる）。そのようにして、バスがモニタされ、キャッシ
ュそれ自身に類似したやり方でバス・トランザクション
に応答する。予約ユニット・アドレスおよびフラグは２
通りある一般的方法のうちの一つで通常は設定される。
もしメモリ階層の任意のキャッシュにブロックが存在し
ないメモリ・ロケーションに対してプロセッサがｌｗａ
ｒｘ命令を送出しようと試みるならば、読出し動作が階
層の頂点にあるプロセッサから該階層内のキャッシュの
各々を通して伝播し、最終的にサービスが提供される汎
用の相互接続部２０上に出力される。これらの読出し動
作は、単一の標識でタグが付けられ、読出しがｌｗａｒ
ｘ命令のためにあり、かつ読出しユニットがアドレスお
よびフラグを設定しなければならないキャッシュ内に予
約ユニットを知らせる。あるいは、プロセッサは１次キ
ャッシュ２６内にすでに存在するブロックのメモリ・ロ
ケーションにｌｗａｒｘ命令を送出する。この状況は
「ｌｗａｒｘ命令ヒット」として知られている。この場
合、プロセッサの予約ユニット３２はその予約アドレス
およびフラグをセットし、１次キャッシュと２次キャッ
シュとの間の接続３６上にｌｗａｒｘ命令予約（以下、
予約とする）として知られる単一のバス動作を送出する
であろう。２次キャッシュは、予約のアドレスを含む予
約メッセージを受け取り、その予約ドレスおよびフラグ
を予約ユニット３４にセットするであろう。もし他のキ
ャッシュ・レベルが存在（図１では示さず）するなら
ば、２次キャッシュは予約メッセージを、メモリ階層内
の任意の低位レベルのキャッシュ上に転送するであろ
う。この低位レベルのキャッシュでは２次キャッシュに
よって取られた動作が繰り返され、すべての予約ユニッ
トが適正にセットされるであろう。すべてのキャッシュ
・レベルに予約メッセージを伝播するプロセスは、一般
にキャッシュ間の相互接続部（例えば、３６および３
８）の使用可能度や特定のインプリメンテーションの細
部に応じて任意の時間取ることがでる。
ぞれが関連した予約ユニット３２および３２を示す。こ
れらのユニットは、予約、アドレスおよびフラグの両方
を含むもので、予約グラニュール・アドレス内の任意の
書込み動作について各々のバス３６および３８をそれぞ
れが「スヌープ」（モニタ）し、そのような動作が検出
された場合に関連予約フラグを無効にする（もし予約を
無効にする動作が低位レベルのキャッシュによって検出
されるならば、それは高位レベルのキャッシュに上げら
れる）。そのようにして、バスがモニタされ、キャッシ
ュそれ自身に類似したやり方でバス・トランザクション
に応答する。予約ユニット・アドレスおよびフラグは２
通りある一般的方法のうちの一つで通常は設定される。
もしメモリ階層の任意のキャッシュにブロックが存在し
ないメモリ・ロケーションに対してプロセッサがｌｗａ
ｒｘ命令を送出しようと試みるならば、読出し動作が階
層の頂点にあるプロセッサから該階層内のキャッシュの
各々を通して伝播し、最終的にサービスが提供される汎
用の相互接続部２０上に出力される。これらの読出し動
作は、単一の標識でタグが付けられ、読出しがｌｗａｒ
ｘ命令のためにあり、かつ読出しユニットがアドレスお
よびフラグを設定しなければならないキャッシュ内に予
約ユニットを知らせる。あるいは、プロセッサは１次キ
ャッシュ２６内にすでに存在するブロックのメモリ・ロ
ケーションにｌｗａｒｘ命令を送出する。この状況は
「ｌｗａｒｘ命令ヒット」として知られている。この場
合、プロセッサの予約ユニット３２はその予約アドレス
およびフラグをセットし、１次キャッシュと２次キャッ
シュとの間の接続３６上にｌｗａｒｘ命令予約（以下、
予約とする）として知られる単一のバス動作を送出する
であろう。２次キャッシュは、予約のアドレスを含む予
約メッセージを受け取り、その予約ドレスおよびフラグ
を予約ユニット３４にセットするであろう。もし他のキ
ャッシュ・レベルが存在（図１では示さず）するなら
ば、２次キャッシュは予約メッセージを、メモリ階層内
の任意の低位レベルのキャッシュ上に転送するであろ
う。この低位レベルのキャッシュでは２次キャッシュに
よって取られた動作が繰り返され、すべての予約ユニッ
トが適正にセットされるであろう。すべてのキャッシュ
・レベルに予約メッセージを伝播するプロセスは、一般
にキャッシュ間の相互接続部（例えば、３６および３
８）の使用可能度や特定のインプリメンテーションの細
部に応じて任意の時間取ることがでる。
【００１２】予約ユニットをセットすることができる１
つの他の方法がある。この状況はブロックが部分的に、
しかも完全にではなくキャッシュ階層から追い出される
場合に起こる。例えば、１次キャッシュにはなく２次キ
ャッシュに存在するブロックにあるアドレスに対してプ
ロセッサ・コア２２がｌｗａｒｘ命令を実行すると想定
する。この場合、プロセッサ・コア２２は２次キャッシ
ュ用の読出しとしてマークされる読出しを送出するであ
ろう。２次キャッシュはブロックのコピーを有し、この
ブロックをプロセッサ・コアに直接返すことを決定する
であろう。一度ブロックがプロセッサ・コアに返される
と、プロセッサ・コアは予約ユニット３２の予約アドレ
スおよびフラグを更新する。２次キャッシュはその予約
もセットし、さらに該予約を伝えるために任意の低位レ
ベルのキャッシュへ予約バス動作を送る。このシナリオ
は、既に記述された２つのケースの組み合わせに過ぎな
い。一般に、ｌｗａｒｘ命令指示によるプロセッサ・コ
アからの読出しは階層に伝播し、該読出しを満足させる
ブロックのコピーを持つキャッシュ（潜在的に１次）に
遭遇するまで予約ユニットを設定する。そのキャッシュ
は階層の残りの部分に予約バス動作を伝播し、残りの予
約ユニットをセットする。このようにして、階層内のす
べての予約ユニットが適切な予約情報を持つｌｗａｒｘ
命令の結果としてロードされ、予約グラニュールに書込
みを行うトランザクションに対してスヌープを開始する
ことができる。このことによって、予約ユニットが予約
フラグをリセットし、該予約のためのメモリ・ロケーシ
ョンが潜在的に修飾されている場合にｓｔｗｃｘ命令が
完了するのを阻止することが可能となる。
つの他の方法がある。この状況はブロックが部分的に、
しかも完全にではなくキャッシュ階層から追い出される
場合に起こる。例えば、１次キャッシュにはなく２次キ
ャッシュに存在するブロックにあるアドレスに対してプ
ロセッサ・コア２２がｌｗａｒｘ命令を実行すると想定
する。この場合、プロセッサ・コア２２は２次キャッシ
ュ用の読出しとしてマークされる読出しを送出するであ
ろう。２次キャッシュはブロックのコピーを有し、この
ブロックをプロセッサ・コアに直接返すことを決定する
であろう。一度ブロックがプロセッサ・コアに返される
と、プロセッサ・コアは予約ユニット３２の予約アドレ
スおよびフラグを更新する。２次キャッシュはその予約
もセットし、さらに該予約を伝えるために任意の低位レ
ベルのキャッシュへ予約バス動作を送る。このシナリオ
は、既に記述された２つのケースの組み合わせに過ぎな
い。一般に、ｌｗａｒｘ命令指示によるプロセッサ・コ
アからの読出しは階層に伝播し、該読出しを満足させる
ブロックのコピーを持つキャッシュ（潜在的に１次）に
遭遇するまで予約ユニットを設定する。そのキャッシュ
は階層の残りの部分に予約バス動作を伝播し、残りの予
約ユニットをセットする。このようにして、階層内のす
べての予約ユニットが適切な予約情報を持つｌｗａｒｘ
命令の結果としてロードされ、予約グラニュールに書込
みを行うトランザクションに対してスヌープを開始する
ことができる。このことによって、予約ユニットが予約
フラグをリセットし、該予約のためのメモリ・ロケーシ
ョンが潜在的に修飾されている場合にｓｔｗｃｘ命令が
完了するのを阻止することが可能となる。
【００１３】従来のＳＭＰシステムにおける一つの問題
は、ｌｗａｒｘ命令予約の実体であるデータ値を持つブ
ロックの追い出しに関係する。ほとんどすべてのｌｗａ
ｒｘ命令がｓｔｗｃｘ命令によって最終的には追従され
る（条件付格納動作がアトミック読出し書込みシークエ
ンスのために後で使われるほかはメモリのブロック上に
予約を置く必要はない）。しかし、種々の理由から、ｌ
ｗａｒｘ命令の実行と関連するｓｔｗｃｘ命令の実行と
の間で比較的多くの時間を経過させることができる。そ
の間に、所定のキャッシュにロードされたメモリ・ブロ
ックはプロセッサによって実行された他の命令の結果と
して追い出されるであろう。この結果は望ましくない。
なぜなら、メモリ・ブロックは最終的にはｓｔｗｃｘ命
令を実行するために再びキャッシュにロードされる必要
性があるため不必要な遅れが生ずるからである。さら
に、予約ブロックはｓｔｗｃｘ命令の実行前に追い出さ
れ、再びロードされ、そして再び追い出される（数回に
わたって）ことが可能である。したがって、この非能率
は顕著な性能劣化を招き、そのためそれらの命令を処理
する速度が高められるようにｌｗａｒｘ／ｓｔｗｃｘセ
マンティクスを実現するより効率的な方法を発明するこ
とが求められている。もし、その方法が予約メモリ・ブ
ロックの不必要な追い出しを防ぐことができるならば特
に有利であろう。
は、ｌｗａｒｘ命令予約の実体であるデータ値を持つブ
ロックの追い出しに関係する。ほとんどすべてのｌｗａ
ｒｘ命令がｓｔｗｃｘ命令によって最終的には追従され
る（条件付格納動作がアトミック読出し書込みシークエ
ンスのために後で使われるほかはメモリのブロック上に
予約を置く必要はない）。しかし、種々の理由から、ｌ
ｗａｒｘ命令の実行と関連するｓｔｗｃｘ命令の実行と
の間で比較的多くの時間を経過させることができる。そ
の間に、所定のキャッシュにロードされたメモリ・ブロ
ックはプロセッサによって実行された他の命令の結果と
して追い出されるであろう。この結果は望ましくない。
なぜなら、メモリ・ブロックは最終的にはｓｔｗｃｘ命
令を実行するために再びキャッシュにロードされる必要
性があるため不必要な遅れが生ずるからである。さら
に、予約ブロックはｓｔｗｃｘ命令の実行前に追い出さ
れ、再びロードされ、そして再び追い出される（数回に
わたって）ことが可能である。したがって、この非能率
は顕著な性能劣化を招き、そのためそれらの命令を処理
する速度が高められるようにｌｗａｒｘ／ｓｔｗｃｘセ
マンティクスを実現するより効率的な方法を発明するこ
とが求められている。もし、その方法が予約メモリ・ブ
ロックの不必要な追い出しを防ぐことができるならば特
に有利であろう。
【００１４】
【発明が解決しようとする課題】したがって、本発明の
目的の一つは、マルチ・プロセッサ・コンピュータ・シ
ステムのキャッシュ・エントリ予約を処理する改善され
た方法を提供することである。本発明の別の目的は、ロ
ードおよび予約（ｌｗａｒｘ）命令と条件付格納（ｓｔ
ｗｃｘ）命令とを用いるアトミック読出し書込みシーケ
ンスの実行速度を高めるような方法を提供することであ
る。本発明のさらに別の目的は、予約メモリ・ブロック
の不必要な追い出しを防ぐような方法を提供することで
ある。
目的の一つは、マルチ・プロセッサ・コンピュータ・シ
ステムのキャッシュ・エントリ予約を処理する改善され
た方法を提供することである。本発明の別の目的は、ロ
ードおよび予約（ｌｗａｒｘ）命令と条件付格納（ｓｔ
ｗｃｘ）命令とを用いるアトミック読出し書込みシーケ
ンスの実行速度を高めるような方法を提供することであ
る。本発明のさらに別の目的は、予約メモリ・ブロック
の不必要な追い出しを防ぐような方法を提供することで
ある。
【００１５】上記目的は、処理装置のキャッシュに値を
格納する方法であって、キャッシュの第１のブロックに
第１の値をロードする段階と、第１の値が予約されるも
のであることを表示する段階と、キャッシュの別のブロ
ックに他の値を少なくとも一つロードする段階と、もし
第１の値が予約されていることがなおも表示されている
とするならば、選択されたブロックは第１のブロックと
は別のブロックであるとするキャッシュの選択されたブ
ロックを追い出す段階と、追い出す段階の後に、選択さ
れたブロックに新しい値をロードする段階とを一般に有
する方法によって達成される。第１の値は、該第１の値
に関連したメモリ・アドレスをキャッシュの予約ユニッ
トにロードする段階と、該予約ユニットの予約フラグを
アクティブにする段階とによって予約されているとして
表示することができる。２通りの選択可能なインプリメ
ンテーションでは、追い出す段階は、追い出しのために
仮のブロックを選択する段階と、仮のブロックが第１の
ブロックと同一であるかどうかを決定（もし同一である
ならば選択されたブロックとして異なるブロックを選
び、もし同一でなければ選択されたブロックとして仮の
ブロックを選択）する段階か、あるいは第１のブロック
が選択されたブロックとして選ばれることをプリエンプ
ティブに禁止する段階のいずれかである。本発明の方法
は異なるタイプのキャッシュ置換コントロール、例えば
ランダム機構または最低使用頻度機構によって実現され
る。
格納する方法であって、キャッシュの第１のブロックに
第１の値をロードする段階と、第１の値が予約されるも
のであることを表示する段階と、キャッシュの別のブロ
ックに他の値を少なくとも一つロードする段階と、もし
第１の値が予約されていることがなおも表示されている
とするならば、選択されたブロックは第１のブロックと
は別のブロックであるとするキャッシュの選択されたブ
ロックを追い出す段階と、追い出す段階の後に、選択さ
れたブロックに新しい値をロードする段階とを一般に有
する方法によって達成される。第１の値は、該第１の値
に関連したメモリ・アドレスをキャッシュの予約ユニッ
トにロードする段階と、該予約ユニットの予約フラグを
アクティブにする段階とによって予約されているとして
表示することができる。２通りの選択可能なインプリメ
ンテーションでは、追い出す段階は、追い出しのために
仮のブロックを選択する段階と、仮のブロックが第１の
ブロックと同一であるかどうかを決定（もし同一である
ならば選択されたブロックとして異なるブロックを選
び、もし同一でなければ選択されたブロックとして仮の
ブロックを選択）する段階か、あるいは第１のブロック
が選択されたブロックとして選ばれることをプリエンプ
ティブに禁止する段階のいずれかである。本発明の方法
は異なるタイプのキャッシュ置換コントロール、例えば
ランダム機構または最低使用頻度機構によって実現され
る。
【００１６】上記目的と同様に本発明のさらなる目的、
特徴、および利点は、以下の詳細な記述から明らかにな
ろう。
特徴、および利点は、以下の詳細な記述から明らかにな
ろう。
【００１７】
【発明の実施の形態】本発明は、マルチ・プロセッサ・
システム、例えば図１に示すシステムにおけるキャッシ
ュの予約および追い出しを処理する方法に関する。しか
し、本発明は必ずしも従来のコンピュータ・システムに
適用されるものではなく、図１には示されていないよう
な新規のハードウェア・コンポーネント、あるいは既存
のコンポーネント用の新規相互接続アーキテクチャを包
含することができよう。したがって、当業者は本発明が
図示の一般化されたシステムに限定されるものではない
ことを正当に評価することができよう。
システム、例えば図１に示すシステムにおけるキャッシ
ュの予約および追い出しを処理する方法に関する。しか
し、本発明は必ずしも従来のコンピュータ・システムに
適用されるものではなく、図１には示されていないよう
な新規のハードウェア・コンポーネント、あるいは既存
のコンポーネント用の新規相互接続アーキテクチャを包
含することができよう。したがって、当業者は本発明が
図示の一般化されたシステムに限定されるものではない
ことを正当に評価することができよう。
【００１８】図２は、本発明にもとづいて構成されるキ
ャッシュ・ユニット４０の一実施形態例を示す。キャッ
シュ４０は、キャッシュ・ディレクトリ４２、キャッシ
ュ・エントリ・アレイ４４、キャッシュ置換コントロー
ル・ユニット４６、および予約ユニットから概略構成さ
れる。キャッシュ・エントリ・アレイ４４はキャッシュ
４０に関連するコンピュータ・システムの所定のプロセ
ッサによって使用されるデータ値を保持し、キャッシュ
・ディレクトリ４３はキャッシュ・エントリ・アレイ４
４に格納されたデータ値に対応するメモリ・ブロックの
アドレスを保持する。キャッシュ４０のこれら２つのコ
ンポーネント（すなわち、キャッシュ・ディレクトリ４
２およびキャッシュ・エントリ・アレイ４４）は一般的
に従来のものであり、高位レベルのコンポーネント（例
えば、高位レベルのキャッシュまたはプロセッサ・コ
ア）と通信することを可能とさせる第１の相互接続バス
５０と接続し、さらに低位レベルのコンポーネント（例
えば低位レベルのキャッシュまたはシステム・バスを介
したシステム・メモリ（ＲＡＭ））と通信することを可
能とさせる第２の相互接続バス５２に接続している。
ャッシュ・ユニット４０の一実施形態例を示す。キャッ
シュ４０は、キャッシュ・ディレクトリ４２、キャッシ
ュ・エントリ・アレイ４４、キャッシュ置換コントロー
ル・ユニット４６、および予約ユニットから概略構成さ
れる。キャッシュ・エントリ・アレイ４４はキャッシュ
４０に関連するコンピュータ・システムの所定のプロセ
ッサによって使用されるデータ値を保持し、キャッシュ
・ディレクトリ４３はキャッシュ・エントリ・アレイ４
４に格納されたデータ値に対応するメモリ・ブロックの
アドレスを保持する。キャッシュ４０のこれら２つのコ
ンポーネント（すなわち、キャッシュ・ディレクトリ４
２およびキャッシュ・エントリ・アレイ４４）は一般的
に従来のものであり、高位レベルのコンポーネント（例
えば、高位レベルのキャッシュまたはプロセッサ・コ
ア）と通信することを可能とさせる第１の相互接続バス
５０と接続し、さらに低位レベルのコンポーネント（例
えば低位レベルのキャッシュまたはシステム・バスを介
したシステム・メモリ（ＲＡＭ））と通信することを可
能とさせる第２の相互接続バス５２に接続している。
【００１９】予約ユニット４８は、この実施形態例のキ
ャッシュ４０のものを除いて一般に従来のものであり、
後述する理由からキャッシュ置換コントロール・ユニッ
ト４６に接続している。従来技術で述べたように、ロー
ドおよび予約（ｌａｗｒｘ）命令のターゲットがキャッ
シュ４０内に見いだされた場合、ターゲット・メモリ・
ブロックのアドレスは予約（ｒｅｓｅｒｖａｔｉｏｎ）
ユニット４８に格納され、予約フラグがアクティブにな
る。その後、条件付格納（ｓｔｗｃｘ命令）命令が実行
された場合、予約フラグが有効かどうかを最初に決定す
る。もし有効であるならば、ｓｔｗｃｘ命令は指定され
たメモリのワードの格納を行い、条件コード・レジスタ
を設定して格納が成功したことを示し、さらに予約フラ
グをリセットする。一方、もし予約の予約フラグが有効
でなければ、ｓｔｗｃｘ命令は格納を行わず、格納が失
敗したことを示す条件コード・レジスタが設定される。
ｓｔｗｃｘ命令の条件付完了は１次（Ｌ１）キャッシュ
のレベルのみで行われる。
ャッシュ４０のものを除いて一般に従来のものであり、
後述する理由からキャッシュ置換コントロール・ユニッ
ト４６に接続している。従来技術で述べたように、ロー
ドおよび予約（ｌａｗｒｘ）命令のターゲットがキャッ
シュ４０内に見いだされた場合、ターゲット・メモリ・
ブロックのアドレスは予約（ｒｅｓｅｒｖａｔｉｏｎ）
ユニット４８に格納され、予約フラグがアクティブにな
る。その後、条件付格納（ｓｔｗｃｘ命令）命令が実行
された場合、予約フラグが有効かどうかを最初に決定す
る。もし有効であるならば、ｓｔｗｃｘ命令は指定され
たメモリのワードの格納を行い、条件コード・レジスタ
を設定して格納が成功したことを示し、さらに予約フラ
グをリセットする。一方、もし予約の予約フラグが有効
でなければ、ｓｔｗｃｘ命令は格納を行わず、格納が失
敗したことを示す条件コード・レジスタが設定される。
ｓｔｗｃｘ命令の条件付完了は１次（Ｌ１）キャッシュ
のレベルのみで行われる。
【００２０】キャッシュ・エントリ・アレイ３３は、従
来のキャッシュ・エントリ・アレイと同様にセットに分
けられた複数のブロックを有し、また任意のメモリ・ブ
ロックに対して該ブロックが現行（従来）のマッピング
機能にもとづいてマップされる単一のセットがキャッシ
ュ内にある。キャッシュ・エントリ・アレイ４４にある
すべてのブロックが満たされており、またキャッシュが
全セットにマップするメモリ・ロケーションに対する読
出しおよび書込み要求を受け取る場合、全セット内にあ
るブロックの一つは追い出されなければならない。キャ
ッシュ置換コントロール・ユニット４６は、予約アドレ
スを含むブロックは追い出されないことを除いて、いく
つかある従来の方法の一つによってブロックを選択す
る。キャッシュ置換コントロール・ユニット４６は、ブ
ロック上の予約に気づき、さもなければ予約ブロックを
追い出すであろう任意の動作を無効にする。このように
してキャッシュは、次のｓｔｗｃｘ命令に潜在的に要求
されることから、より効率的に予約メモリ・ブロックを
処理する。キャッシュ・エントリ・アレイ４４の一つの
セットにおけるブロックの数は、一セットあたりのブロ
ックの数が１よりも多いことを条件（すなわち、キャッ
シュは少なくとも２通りのセット・アソシエイティブで
なければならない）として変動することができる。さも
なければ、追い出すべき代りのブロックがセット内に存
在しないであろう。
来のキャッシュ・エントリ・アレイと同様にセットに分
けられた複数のブロックを有し、また任意のメモリ・ブ
ロックに対して該ブロックが現行（従来）のマッピング
機能にもとづいてマップされる単一のセットがキャッシ
ュ内にある。キャッシュ・エントリ・アレイ４４にある
すべてのブロックが満たされており、またキャッシュが
全セットにマップするメモリ・ロケーションに対する読
出しおよび書込み要求を受け取る場合、全セット内にあ
るブロックの一つは追い出されなければならない。キャ
ッシュ置換コントロール・ユニット４６は、予約アドレ
スを含むブロックは追い出されないことを除いて、いく
つかある従来の方法の一つによってブロックを選択す
る。キャッシュ置換コントロール・ユニット４６は、ブ
ロック上の予約に気づき、さもなければ予約ブロックを
追い出すであろう任意の動作を無効にする。このように
してキャッシュは、次のｓｔｗｃｘ命令に潜在的に要求
されることから、より効率的に予約メモリ・ブロックを
処理する。キャッシュ・エントリ・アレイ４４の一つの
セットにおけるブロックの数は、一セットあたりのブロ
ックの数が１よりも多いことを条件（すなわち、キャッ
シュは少なくとも２通りのセット・アソシエイティブで
なければならない）として変動することができる。さも
なければ、追い出すべき代りのブロックがセット内に存
在しないであろう。
【００２１】キャッシュ置換コントロール・ユニット４
６が予約ブロックの追い出しを無効にする方法は、使用
されている特定の置換機構による影響を受けるけれど
も、置換のアルゴリズムおよび無効にさせるアルゴリズ
ムは実際のところ無関係である。例えば、もし置換機構
がランダムであるならば、キャッシュ・コントロール・
ユニット４６はセット内のどのブロックが追い出される
かを最初にランダムに決定することができ、また予約ユ
ニット３８およびキャッシュ・ディレクトリ４２のアド
レスを検査することでそのブロックが予約を持つかどう
かを決定することができる。もしそうであるならば、い
くつかの方法のうちの一つによってセット内のブロック
が新たに選択される。例えば、追い出しのために予約さ
れていないブロックが選択されるまで別のランダム決定
を繰り返し行ってもよく、あるいは予約ブロック後にセ
ット内の次に続くブロックを選択するというような、よ
り簡単なアプローチを使用してもよい（一般に、実行時
間が長くなるので繰り返しによるアプローチはあまり望
ましいものとはいえない）。もし少なくとも最低使用頻
度（ＬＲＵ）機構が追い出しのためのブロックを選択す
る際に使用するならば、前述の方法と同様に、すなわち
ＬＲＵ方法を使用し、予約アドレスに対する選択ブロッ
クのいずれかをチェックすることによって実行してもよ
い。もし予約ブロックが仮に選択されたならば、次に続
くブロックが選択されてもよく、あるいは（ＬＲＵビッ
ト・パターンにもとづいて）最近使用されていない別の
ブロックを選択することができる。代わりとして、プリ
エンプティブ方法を用いてもよく、各時間ごとに所定の
セットに対して読出しおよび書込み動作が行われ、セッ
ト内の任意の予約ブロックのアドレスは、予約ブロック
がもっとも最近使用されたことを示すようにＬＲＵユニ
ット（すなわち、キャッシュ置換コントロール・ユニッ
ト４６）にリセットすることができる。このようにし
て、ＬＲＵ機構による予約ブロックの選択が禁止され
る。プリエンプティブ技法もまたランダム置換機構に適
用することができる。
６が予約ブロックの追い出しを無効にする方法は、使用
されている特定の置換機構による影響を受けるけれど
も、置換のアルゴリズムおよび無効にさせるアルゴリズ
ムは実際のところ無関係である。例えば、もし置換機構
がランダムであるならば、キャッシュ・コントロール・
ユニット４６はセット内のどのブロックが追い出される
かを最初にランダムに決定することができ、また予約ユ
ニット３８およびキャッシュ・ディレクトリ４２のアド
レスを検査することでそのブロックが予約を持つかどう
かを決定することができる。もしそうであるならば、い
くつかの方法のうちの一つによってセット内のブロック
が新たに選択される。例えば、追い出しのために予約さ
れていないブロックが選択されるまで別のランダム決定
を繰り返し行ってもよく、あるいは予約ブロック後にセ
ット内の次に続くブロックを選択するというような、よ
り簡単なアプローチを使用してもよい（一般に、実行時
間が長くなるので繰り返しによるアプローチはあまり望
ましいものとはいえない）。もし少なくとも最低使用頻
度（ＬＲＵ）機構が追い出しのためのブロックを選択す
る際に使用するならば、前述の方法と同様に、すなわち
ＬＲＵ方法を使用し、予約アドレスに対する選択ブロッ
クのいずれかをチェックすることによって実行してもよ
い。もし予約ブロックが仮に選択されたならば、次に続
くブロックが選択されてもよく、あるいは（ＬＲＵビッ
ト・パターンにもとづいて）最近使用されていない別の
ブロックを選択することができる。代わりとして、プリ
エンプティブ方法を用いてもよく、各時間ごとに所定の
セットに対して読出しおよび書込み動作が行われ、セッ
ト内の任意の予約ブロックのアドレスは、予約ブロック
がもっとも最近使用されたことを示すようにＬＲＵユニ
ット（すなわち、キャッシュ置換コントロール・ユニッ
ト４６）にリセットすることができる。このようにし
て、ＬＲＵ機構による予約ブロックの選択が禁止され
る。プリエンプティブ技法もまたランダム置換機構に適
用することができる。
【００２２】キャッシュ４０を、オン・ボード（Ｌ１）
キャッシュ、または低位レベルのキャッシュ（例えば、
Ｌ２）として使用してもよい。キャッシュ４０の構成
を、キャッシュ階層の一つあるいは限られた数のキャッ
シュ・レベルのためにのみ使用してもよく、性能を最大
限引きだすようにこの構成をすべてのキャッシュ・レベ
ルに対して使用することが好ましいことを当業者が正当
に評価することであろう。
キャッシュ、または低位レベルのキャッシュ（例えば、
Ｌ２）として使用してもよい。キャッシュ４０の構成
を、キャッシュ階層の一つあるいは限られた数のキャッ
シュ・レベルのためにのみ使用してもよく、性能を最大
限引きだすようにこの構成をすべてのキャッシュ・レベ
ルに対して使用することが好ましいことを当業者が正当
に評価することであろう。
【００２３】図３のフローチャートを参照しながら本発
明をさらに詳細に説明する。ロードおよび予約命令によ
って読出しされる値にプロセッサが最初にアクセスする
場合（６０）、その値は最も高いレベルのキャッシュ６
２に至るまですべてのキャッシュ・レベルにおかれる
（６２）。メモリ・ブロックのアドレスは、各キャッシ
ュの予約ユニットに置かれて、予約フラグがアクティブ
になる（６４）。次に、プロセッサはロードおよび予約
キャッシュ値に関連してもよく、あるいは関連しなくて
もよい他の命令を実行する（６６）。もし予約値を保持
している任意のキャッシュ・エントリ・アレイのセット
が満たされ、またプリセットされたマッピング機構によ
ってセットされるという点で新規の値を格納することが
必要とされるならば（６８）、キャッシュ置換コントロ
ール・ユニットは追い出しのためにブロックの一つを選
択する（７０）。プリエンプティブ機構が予約ブロック
の追い出しを無効にすることには使用されないこの実施
例では、追い出しのために仮に選択されたブロックのメ
モリ・アドレスが予約ブロックのアドレスと比較される
（７２）。また、もしそれらが同一であるならば（７
２）、異なるブロックが選択される（７４）。予約され
ていないブロックが一度選択されると、その値が追い出
され（もしデータが修復されるならばメモリ階層の次の
レベルに押し下げられ、あるいはもしデータが修復され
ていなければ放棄される）、さらに新しい値がロードさ
れる（７６）。このプロセスは、予約フラグが特定のキ
ャッシュに対してアクティブである限り繰り返される。
明をさらに詳細に説明する。ロードおよび予約命令によ
って読出しされる値にプロセッサが最初にアクセスする
場合（６０）、その値は最も高いレベルのキャッシュ６
２に至るまですべてのキャッシュ・レベルにおかれる
（６２）。メモリ・ブロックのアドレスは、各キャッシ
ュの予約ユニットに置かれて、予約フラグがアクティブ
になる（６４）。次に、プロセッサはロードおよび予約
キャッシュ値に関連してもよく、あるいは関連しなくて
もよい他の命令を実行する（６６）。もし予約値を保持
している任意のキャッシュ・エントリ・アレイのセット
が満たされ、またプリセットされたマッピング機構によ
ってセットされるという点で新規の値を格納することが
必要とされるならば（６８）、キャッシュ置換コントロ
ール・ユニットは追い出しのためにブロックの一つを選
択する（７０）。プリエンプティブ機構が予約ブロック
の追い出しを無効にすることには使用されないこの実施
例では、追い出しのために仮に選択されたブロックのメ
モリ・アドレスが予約ブロックのアドレスと比較される
（７２）。また、もしそれらが同一であるならば（７
２）、異なるブロックが選択される（７４）。予約され
ていないブロックが一度選択されると、その値が追い出
され（もしデータが修復されるならばメモリ階層の次の
レベルに押し下げられ、あるいはもしデータが修復され
ていなければ放棄される）、さらに新しい値がロードさ
れる（７６）。このプロセスは、予約フラグが特定のキ
ャッシュに対してアクティブである限り繰り返される。
【００２４】本発明は、ｌｗａｒｘ命令予約アドレスの
不必要な追い出しを避けることによってプロセッサの性
能を改善する。さもなければ、次に続くｓｔｗｃｘ命令
のために所定のプロセッサに関連したすべてのキャッシ
ュにｌｗａｒｘ命令予約アドレスを再ロードしなければ
ならないであろう。ｌｗａｒｘ／ｓｔｗｃｘ命令が頻繁
に実行されているＳＭＰシステムにおいて、本発明は全
体的なシステム性能の向上を可能にする。しかし、この
技術についてはある種の限界があろう。例えば、Ｐｏｗ
ｅｒＰＣ（登録商標）プロセッサもまた「フラッシュ」
命令を使用してシステムの全プロセッシング・ユニット
のキャッシュから所定のブロックを取り除く。この命令
が実行される場合、すべてのプロセッサは所定のブロッ
クのいかなるコピーも放棄しなくてはならない。この手
順は、たとえ予約がブロック上に保持されていようとも
実行されなければならない。この動作は追い出しとは異
なり、「スヌープ」動作として知られている。この場
合、本発明はキャッシュにブロックのコピーを保持させ
るようなことはできず、またそれはシステムのキャッシ
ュから取り除かれなくてはならない。この結果は、シス
テムの適正動作を妨げるものではなかろう。しかしどち
らかと言うと、もしブロックがさらなるｓｔｗｃｘ命令
のためにキャッシュに再ロードされなければならないと
するならば性能を犠牲にすることになろう。
不必要な追い出しを避けることによってプロセッサの性
能を改善する。さもなければ、次に続くｓｔｗｃｘ命令
のために所定のプロセッサに関連したすべてのキャッシ
ュにｌｗａｒｘ命令予約アドレスを再ロードしなければ
ならないであろう。ｌｗａｒｘ／ｓｔｗｃｘ命令が頻繁
に実行されているＳＭＰシステムにおいて、本発明は全
体的なシステム性能の向上を可能にする。しかし、この
技術についてはある種の限界があろう。例えば、Ｐｏｗ
ｅｒＰＣ（登録商標）プロセッサもまた「フラッシュ」
命令を使用してシステムの全プロセッシング・ユニット
のキャッシュから所定のブロックを取り除く。この命令
が実行される場合、すべてのプロセッサは所定のブロッ
クのいかなるコピーも放棄しなくてはならない。この手
順は、たとえ予約がブロック上に保持されていようとも
実行されなければならない。この動作は追い出しとは異
なり、「スヌープ」動作として知られている。この場
合、本発明はキャッシュにブロックのコピーを保持させ
るようなことはできず、またそれはシステムのキャッシ
ュから取り除かれなくてはならない。この結果は、シス
テムの適正動作を妨げるものではなかろう。しかしどち
らかと言うと、もしブロックがさらなるｓｔｗｃｘ命令
のためにキャッシュに再ロードされなければならないと
するならば性能を犠牲にすることになろう。
【００２５】以上、本発明を特定の実施形態例を参照し
ながら説明したけれども、この記述を限定の意味で解釈
すべきものではない。本発明の記述にもとづいて当業者
は本発明の別の実施形態例のみならず開示された実施形
態例の種々の変形例を理解することができよう。したが
って、そのような変形例は本発明の精神または範囲から
外れることなく実施されることが理解されよう。
ながら説明したけれども、この記述を限定の意味で解釈
すべきものではない。本発明の記述にもとづいて当業者
は本発明の別の実施形態例のみならず開示された実施形
態例の種々の変形例を理解することができよう。したが
って、そのような変形例は本発明の精神または範囲から
外れることなく実施されることが理解されよう。
【００２６】まとめとして、本発明の構成に関して以下
の事項を開示する。 （１）コンピュータ・システムの処理装置用で、かつ値
を受け取るための複数のブロックを有するキャッシュに
対して前記値を格納する方法であって、前記キャッシュ
の第１のブロックに第１の値をロードする段階と、前記
第１の値が予約されるものであることを表示する段階
と、前記キャッシュの別のブロックに他の値を少なくと
も一つロードする段階と、もし前記第１の値が予約され
ていることがなおも表示されているとするならば、前記
選択されたブロックは前記第１のブロックとは別のブロ
ックであるとする前記キャッシュの選択されたブロック
を追い出す段階と、前記追い出す段階の後に、前記選択
されたブロックに新しい値をロードする段階と、を有す
ることを特徴とするキャッシュへの値格納方法。 （２）前記第１の値は、前記第１の値に関連したメモリ
・アドレスを前記キャッシュの予約ユニットにロードす
る段階と、前記予約ユニットの予約フラグをアクティブ
にする段階と、によって予約されているとして表示され
ることを特徴とする上記（１）に記載のキャッシュへの
値格納方法。 （３）前記追い出す段階は、追い出しのために仮のブロ
ックを選択する段階と、前記仮のブロックが前記第１の
ブロックと同一であるかどうかを決定し、もし同一であ
るならば前記選択されたブロックとして異なるブロック
を選び、もし同一でなければ前記選択されたブロックと
して前記仮のブロックを選ぶ段階と、をさらに含むこと
を特徴とする上記（１）に記載のキャッシュへの値格納
方法。 （４）前記追い出す段階は、前記第１のブロックが前記
選択されたブロックとして選ばれることをプリエンプテ
ィブに禁止する段階をさらに含むことを特徴とする上記
（１）に記載のキャッシュへの値格納方法。 （５）前記キャッシュの前記ブロックはセットにグルー
プ分けされ、前記ロードする段階の各々は所定の値のメ
モリ・アドレスとプリセット・マッピング機能とにもと
づいて所定の値がロードされるであろうブロックを持つ
単一のセットを決定する段階を含むことを特徴とする上
記（１）に記載のキャッシュへの値格納方法。 （６）前記キャッシュは、ランダム機構にもとづいて前
記選択されたブロックを選ぶ置換ユニットをさらに含む
ことを特徴とする上記（１）に記載のキャッシュへの値
格納方法。 （７）前記キャッシュは、最低使用頻度機構にもとづい
て前記選択されたブロックを選ぶ置換ユニットをさらに
含むことを特徴とする上記（１）に記載のキャッシュへ
の値格納方法。 （８）前記予約フラグがなおも有効であるかどうかを決
定し、もし有効であるならば、前記第１のメモリ・ブロ
ックに新しい値を格納して前記予約フラグをリセットす
る段階を、さらに有することを特徴とする上記（２）に
記載のキャッシュへの値格納方法。 （９）前記キャッシュは、前記ブロックを含むキャッシ
ュ・エントリ・アレイと、前記ブロックにロードされた
値に関連したメモリ・アドレスを持つキャッシュ・ディ
レクトリとをさらに有し、また前記決定する段階は前記
キャッシュ・ディレクトリのアドレスに対して前記第１
の値に関連したメモリ・アドレスを比較する段階を含む
ことを特徴とする上記（３）に記載のキャッシュへの値
格納方法。 （１０）コンピュータ・システムの処理装置用で、かつ
値を受け取るためのセットにグループ分けされた複数の
ブロックを有するキャッシュに対して前記値を格納する
方法であって、前記キャッシュの第１のブロックに第１
の値をロードする段階と、前記キャッシュの予約ユニッ
トに前記第１の値に関連したメモリ・アドレスをロード
する段階と、前記予約ユニットの予約フラグをアクティ
ブにする段階と、前記キャッシュの別のブロックに他の
値を少なくとも一つロードする段階と、もし前記第１の
値が予約されていることがなおも表示されているとする
ならば、前記選択されたブロックは前記第１のブロック
とは別のブロックであるとする前記キャッシュの選択さ
れたブロックを追い出す段階と、前記追い出す段階の後
に、前記選択されたブロックに新しい値をロードする段
階とを有し、さらに、前記ロードする段階の各々は、所
定の値のメモリ・アドレスとプリセット・マッピング機
能とにもとづいて所定の値がロードされるであろうブロ
ックを持つ単一のセットを決定する段階を含むことを特
徴とするキャッシュへの値格納方法。 （１１）コンピュータ・システムであって、プログラム
命令を実行するためのプロセッサと、プログラム命令と
データ値を格納するためのメモリ素子と、前記プロセッ
サと前記メモリ素子とを相互接続するための手段と、前
記プロセッサに接続されたキャッシュとを備え、さら
に、前記キャッシュは前記プロセッサによって使用され
るデータ値を格納するための複数のブロックと、予約を
持つブロックの追い出しを禁止するための手段とを持つ
ことを特徴とするコンピュータ・システム。 （１２）前記キャッシュは、さらに、予約されるブロッ
クに関連したメモリ・アドレスを格納する予約ユニット
と、アクティブになることで前記予約を持つ前記ブロッ
クが予約されることを表示する予約フラグと、を有する
ことを特徴とする上記（１１）に記載のコンピュータ・
システム。 （１３）前記追い出し無効手段は、追い出しのための仮
のブロックを選択し、該仮のブロックが前記予約を持つ
前記ブロックと同一であるかを決定し、もし同一である
ならば、追い出しのために異なるブロックを選ぶことを
特徴とする上記（１１）に記載のコンピュータ・システ
ム。 （１４）前記追い出し無効手段は、前記予約を持つ前記
ブロックが追い出しのために選ばれることをプリエンプ
ティブに禁止することを特徴とする上記（１１）に記載
のコンピュータ・システム。 （１５）前記キャッシュの前記ブロックはセットにグル
ープ分けされ、さらに前記キャッシュは、所定の値のメ
モリ・アドレスとプリセット・マッピング機能とにもと
づいて単一のセットに前記所定の値をロードすることを
特徴とする上記（１１）に記載のコンピュータ・システ
ム。 （１６）前記キャッシュは、さらに、ランダム機構にも
とづいて前記仮のブロックを選ぶ置換ユニットを含むこ
とを特徴とする上記（１３）に記載のコンピュータ・シ
ステム。 （１７）前記キャッシュは、さらに、最低使用頻度機構
にもとづいて追い出しのためのブロックを選ぶ置換ユニ
ットを含むことを特徴とする上記（１）に記載のキャッ
シュへの値格納方法。 （１８）前記キャッシュは、前記ブロックを含むキャッ
シュ・エントリ・アレイと、前記ブロックにロードされ
た値に関連したメモリ・アドレスを持つキャッシュ・デ
ィレクトリとをさらに含み、また、前記仮のブロックが
前記予約を持つ前記ブロックと同一であるかの決定は、
前記キャッシュ・ディレクトリの前記アドレスに対して
前記予約を持つ前記ブロックに関連したメモリ・アドレ
スを比較することによって達成されることを特徴とする
上記（１６）に記載のコンピュータ・システム。 （１９）前記追い出し無効手段は、前記予約を持つ前記
ブロックが最も最近使用されたことを表示することによ
って前記予約を持つ前記ブロックが追い出しのために選
ばれることをプリエンティブに禁止することを特徴とす
る上記（１７）に記載のコンピュータ・システム。
の事項を開示する。 （１）コンピュータ・システムの処理装置用で、かつ値
を受け取るための複数のブロックを有するキャッシュに
対して前記値を格納する方法であって、前記キャッシュ
の第１のブロックに第１の値をロードする段階と、前記
第１の値が予約されるものであることを表示する段階
と、前記キャッシュの別のブロックに他の値を少なくと
も一つロードする段階と、もし前記第１の値が予約され
ていることがなおも表示されているとするならば、前記
選択されたブロックは前記第１のブロックとは別のブロ
ックであるとする前記キャッシュの選択されたブロック
を追い出す段階と、前記追い出す段階の後に、前記選択
されたブロックに新しい値をロードする段階と、を有す
ることを特徴とするキャッシュへの値格納方法。 （２）前記第１の値は、前記第１の値に関連したメモリ
・アドレスを前記キャッシュの予約ユニットにロードす
る段階と、前記予約ユニットの予約フラグをアクティブ
にする段階と、によって予約されているとして表示され
ることを特徴とする上記（１）に記載のキャッシュへの
値格納方法。 （３）前記追い出す段階は、追い出しのために仮のブロ
ックを選択する段階と、前記仮のブロックが前記第１の
ブロックと同一であるかどうかを決定し、もし同一であ
るならば前記選択されたブロックとして異なるブロック
を選び、もし同一でなければ前記選択されたブロックと
して前記仮のブロックを選ぶ段階と、をさらに含むこと
を特徴とする上記（１）に記載のキャッシュへの値格納
方法。 （４）前記追い出す段階は、前記第１のブロックが前記
選択されたブロックとして選ばれることをプリエンプテ
ィブに禁止する段階をさらに含むことを特徴とする上記
（１）に記載のキャッシュへの値格納方法。 （５）前記キャッシュの前記ブロックはセットにグルー
プ分けされ、前記ロードする段階の各々は所定の値のメ
モリ・アドレスとプリセット・マッピング機能とにもと
づいて所定の値がロードされるであろうブロックを持つ
単一のセットを決定する段階を含むことを特徴とする上
記（１）に記載のキャッシュへの値格納方法。 （６）前記キャッシュは、ランダム機構にもとづいて前
記選択されたブロックを選ぶ置換ユニットをさらに含む
ことを特徴とする上記（１）に記載のキャッシュへの値
格納方法。 （７）前記キャッシュは、最低使用頻度機構にもとづい
て前記選択されたブロックを選ぶ置換ユニットをさらに
含むことを特徴とする上記（１）に記載のキャッシュへ
の値格納方法。 （８）前記予約フラグがなおも有効であるかどうかを決
定し、もし有効であるならば、前記第１のメモリ・ブロ
ックに新しい値を格納して前記予約フラグをリセットす
る段階を、さらに有することを特徴とする上記（２）に
記載のキャッシュへの値格納方法。 （９）前記キャッシュは、前記ブロックを含むキャッシ
ュ・エントリ・アレイと、前記ブロックにロードされた
値に関連したメモリ・アドレスを持つキャッシュ・ディ
レクトリとをさらに有し、また前記決定する段階は前記
キャッシュ・ディレクトリのアドレスに対して前記第１
の値に関連したメモリ・アドレスを比較する段階を含む
ことを特徴とする上記（３）に記載のキャッシュへの値
格納方法。 （１０）コンピュータ・システムの処理装置用で、かつ
値を受け取るためのセットにグループ分けされた複数の
ブロックを有するキャッシュに対して前記値を格納する
方法であって、前記キャッシュの第１のブロックに第１
の値をロードする段階と、前記キャッシュの予約ユニッ
トに前記第１の値に関連したメモリ・アドレスをロード
する段階と、前記予約ユニットの予約フラグをアクティ
ブにする段階と、前記キャッシュの別のブロックに他の
値を少なくとも一つロードする段階と、もし前記第１の
値が予約されていることがなおも表示されているとする
ならば、前記選択されたブロックは前記第１のブロック
とは別のブロックであるとする前記キャッシュの選択さ
れたブロックを追い出す段階と、前記追い出す段階の後
に、前記選択されたブロックに新しい値をロードする段
階とを有し、さらに、前記ロードする段階の各々は、所
定の値のメモリ・アドレスとプリセット・マッピング機
能とにもとづいて所定の値がロードされるであろうブロ
ックを持つ単一のセットを決定する段階を含むことを特
徴とするキャッシュへの値格納方法。 （１１）コンピュータ・システムであって、プログラム
命令を実行するためのプロセッサと、プログラム命令と
データ値を格納するためのメモリ素子と、前記プロセッ
サと前記メモリ素子とを相互接続するための手段と、前
記プロセッサに接続されたキャッシュとを備え、さら
に、前記キャッシュは前記プロセッサによって使用され
るデータ値を格納するための複数のブロックと、予約を
持つブロックの追い出しを禁止するための手段とを持つ
ことを特徴とするコンピュータ・システム。 （１２）前記キャッシュは、さらに、予約されるブロッ
クに関連したメモリ・アドレスを格納する予約ユニット
と、アクティブになることで前記予約を持つ前記ブロッ
クが予約されることを表示する予約フラグと、を有する
ことを特徴とする上記（１１）に記載のコンピュータ・
システム。 （１３）前記追い出し無効手段は、追い出しのための仮
のブロックを選択し、該仮のブロックが前記予約を持つ
前記ブロックと同一であるかを決定し、もし同一である
ならば、追い出しのために異なるブロックを選ぶことを
特徴とする上記（１１）に記載のコンピュータ・システ
ム。 （１４）前記追い出し無効手段は、前記予約を持つ前記
ブロックが追い出しのために選ばれることをプリエンプ
ティブに禁止することを特徴とする上記（１１）に記載
のコンピュータ・システム。 （１５）前記キャッシュの前記ブロックはセットにグル
ープ分けされ、さらに前記キャッシュは、所定の値のメ
モリ・アドレスとプリセット・マッピング機能とにもと
づいて単一のセットに前記所定の値をロードすることを
特徴とする上記（１１）に記載のコンピュータ・システ
ム。 （１６）前記キャッシュは、さらに、ランダム機構にも
とづいて前記仮のブロックを選ぶ置換ユニットを含むこ
とを特徴とする上記（１３）に記載のコンピュータ・シ
ステム。 （１７）前記キャッシュは、さらに、最低使用頻度機構
にもとづいて追い出しのためのブロックを選ぶ置換ユニ
ットを含むことを特徴とする上記（１）に記載のキャッ
シュへの値格納方法。 （１８）前記キャッシュは、前記ブロックを含むキャッ
シュ・エントリ・アレイと、前記ブロックにロードされ
た値に関連したメモリ・アドレスを持つキャッシュ・デ
ィレクトリとをさらに含み、また、前記仮のブロックが
前記予約を持つ前記ブロックと同一であるかの決定は、
前記キャッシュ・ディレクトリの前記アドレスに対して
前記予約を持つ前記ブロックに関連したメモリ・アドレ
スを比較することによって達成されることを特徴とする
上記（１６）に記載のコンピュータ・システム。 （１９）前記追い出し無効手段は、前記予約を持つ前記
ブロックが最も最近使用されたことを表示することによ
って前記予約を持つ前記ブロックが追い出しのために選
ばれることをプリエンティブに禁止することを特徴とす
る上記（１７）に記載のコンピュータ・システム。
【図１】従来のマルチ・プロセッサ・コンピュータ・シ
ステムのブロック図である。
ステムのブロック図である。
【図２】本発明にもとづいて構成されたマルチ・プロセ
ッサ・コンピュータ・システムのキャッシュのブロック
図である。
ッサ・コンピュータ・システムのキャッシュのブロック
図である。
【図３】予約アドレスを含むと思われるキャッシュ・ブ
ロックの追い出しに関連した段階を説明するためのフロ
ーチャートである。
ロックの追い出しに関連した段階を説明するためのフロ
ーチャートである。
４０ キャッシュ・ユニット ４２ キャッシュ・ディレクトリ ４４ キャッシュ・エントリ・アレイ ４６ キャッシュ置換コントロール・ユニット ４８ 予約ユニット ５０ 第１の相互接続バス ５２ 第２の相互接続バス
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジョン・スティーブン・ドットソン アメリカ合衆国78660、 テキサス州フラ ッガーヴィル ベル・ロック・サークル 1205 (72)発明者 ジェリー・ドン・ルイス アメリカ合衆国78681、 テキサス州ラウ ンド・ロック アロウヘッド・サークル 3409 (72)発明者 デレック・エドワード・ウイリアムス アメリカ合衆国78728、 テキサス州オー スティン シングル・トレイス 14723
Claims (19)
- 【請求項１】コンピュータ・システムの処理装置用で、
かつ値を受け取るための複数のブロックを有するキャッ
シュに対して前記値を格納する方法であって、 前記キャッシュの第１のブロックに第１の値をロードす
る段階と、 前記第１の値が予約されるものであることを表示する段
階と、 前記キャッシュの別のブロックに他の値を少なくとも一
つロードする段階と、 もし前記第１の値が予約されていることがなおも表示さ
れているとするならば、前記選択されたブロックは前記
第１のブロックとは別のブロックであるとする前記キャ
ッシュの選択されたブロックを追い出す段階と、 前記追い出す段階の後に、前記選択されたブロックに新
しい値をロードする段階と、 を有することを特徴とするキャッシュへの値格納方法。 - 【請求項２】前記第１の値は、 前記第１の値に関連したメモリ・アドレスを前記キャッ
シュの予約ユニットにロードする段階と、 前記予約ユニットの予約フラグをアクティブにする段階
と、 によって予約されているとして表示されることを特徴と
する請求項１に記載のキャッシュへの値格納方法。 - 【請求項３】前記追い出す段階は、 追い出しのために仮のブロックを選択する段階と、 前記仮のブロックが前記第１のブロックと同一であるか
どうかを決定し、もし同一であるならば前記選択された
ブロックとして異なるブロックを選び、もし同一でなけ
れば前記選択されたブロックとして前記仮のブロックを
選ぶ段階と、 をさらに含むことを特徴とする請求項１に記載のキャッ
シュへの値格納方法。 - 【請求項４】前記追い出す段階は、 前記第１のブロックが前記選択されたブロックとして選
ばれることをプリエンプティブに禁止する段階をさらに
含むことを特徴とする請求項１に記載のキャッシュへの
値格納方法。 - 【請求項５】前記キャッシュの前記ブロックはセットに
グループ分けされ、前記ロードする段階の各々は所定の
値のメモリ・アドレスとプリセット・マッピング機能と
にもとづいて所定の値がロードされるであろうブロック
を持つ単一のセットを決定する段階を含むことを特徴と
する請求項１に記載のキャッシュへの値格納方法。 - 【請求項６】前記キャッシュは、 ランダム機構にもとづいて前記選択されたブロックを選
ぶ置換ユニットをさらに含むことを特徴とする請求項１
に記載のキャッシュへの値格納方法。 - 【請求項７】前記キャッシュは、 最低使用頻度機構にもとづいて前記選択されたブロック
を選ぶ置換ユニットをさらに含むことを特徴とする請求
項１に記載のキャッシュへの値格納方法。 - 【請求項８】前記予約フラグがなおも有効であるかどう
かを決定し、もし有効であるならば、前記第１のメモリ
・ブロックに新しい値を格納して前記予約フラグをリセ
ットする段階を、さらに有することを特徴とする請求項
２に記載のキャッシュへの値格納方法。 - 【請求項９】前記キャッシュは、前記ブロックを含むキ
ャッシュ・エントリ・アレイと、前記ブロックにロード
された値に関連したメモリ・アドレスを持つキャッシュ
・ディレクトリとをさらに有し、また前記決定する段階
は前記キャッシュ・ディレクトリのアドレスに対して前
記第１の値に関連したメモリ・アドレスを比較する段階
を含むことを特徴とする請求項３に記載のキャッシュへ
の値格納方法。 - 【請求項１０】コンピュータ・システムの処理装置用
で、かつ値を受け取るためのセットにグループ分けされ
た複数のブロックを有するキャッシュに対して前記値を
格納する方法であって、 前記キャッシュの第１のブロックに第１の値をロードす
る段階と、 前記キャッシュの予約ユニットに前記第１の値に関連し
たメモリ・アドレスをロードする段階と、 前記予約ユニットの予約フラグをアクティブにする段階
と、 前記キャッシュの別のブロックに他の値を少なくとも一
つロードする段階と、 もし前記第１の値が予約されていることがなおも表示さ
れているとするならば、前記選択されたブロックは前記
第１のブロックとは別のブロックであるとする前記キャ
ッシュの選択されたブロックを追い出す段階と、 前記追い出す段階の後に、前記選択されたブロックに新
しい値をロードする段階とを有し、さらに、 前記ロードする段階の各々は、所定の値のメモリ・アド
レスとプリセット・マッピング機能とにもとづいて所定
の値がロードされるであろうブロックを持つ単一のセッ
トを決定する段階を含むことを特徴とするキャッシュへ
の値格納方法。 - 【請求項１１】コンピュータ・システムであって、 プログラム命令を実行するためのプロセッサと、 プログラム命令とデータ値を格納するためのメモリ素子
と、 前記プロセッサと前記メモリ素子とを相互接続するため
の手段と、 前記プロセッサに接続されたキャッシュとを備え、さら
に、 前記キャッシュは前記プロセッサによって使用されるデ
ータ値を格納するための複数のブロックと、予約を持つ
ブロックの追い出しを禁止するための手段とを持つこと
を特徴とするコンピュータ・システム。 - 【請求項１２】前記キャッシュは、さらに、 予約されるブロックに関連したメモリ・アドレスを格納
する予約ユニットと、 アクティブになることで前記予約を持つ前記ブロックが
予約されることを表示する予約フラグと、 を有することを特徴とする請求項１１に記載のコンピュ
ータ・システム。 - 【請求項１３】前記追い出し無効手段は、追い出しのた
めの仮のブロックを選択し、該仮のブロックが前記予約
を持つ前記ブロックと同一であるかを決定し、もし同一
であるならば、追い出しのために異なるブロックを選ぶ
ことを特徴とする請求項１１に記載のコンピュータ・シ
ステム。 - 【請求項１４】前記追い出し無効手段は、前記予約を持
つ前記ブロックが追い出しのために選ばれることをプリ
エンプティブに禁止することを特徴とする請求項１１に
記載のコンピュータ・システム。 - 【請求項１５】前記キャッシュの前記ブロックはセット
にグループ分けされ、さらに前記キャッシュは、所定の
値のメモリ・アドレスとプリセット・マッピング機能と
にもとづいて単一のセットに前記所定の値をロードする
ことを特徴とする請求項１１に記載のコンピュータ・シ
ステム。 - 【請求項１６】前記キャッシュは、さらに、 ランダム機構にもとづいて前記仮のブロックを選ぶ置換
ユニットを含むことを特徴とする請求項１３に記載のコ
ンピュータ・システム。 - 【請求項１７】前記キャッシュは、さらに、 最低使用頻度機構にもとづいて追い出しのためのブロッ
クを選ぶ置換ユニットを含むことを特徴とする請求項１
に記載のキャッシュへの値格納方法。 - 【請求項１８】前記キャッシュは、 前記ブロックを含むキャッシュ・エントリ・アレイと、
前記ブロックにロードされた値に関連したメモリ・アド
レスを持つキャッシュ・ディレクトリとをさらに含み、
また、 前記仮のブロックが前記予約を持つ前記ブロックと同一
であるかの決定は、前記キャッシュ・ディレクトリの前
記アドレスに対して前記予約を持つ前記ブロックに関連
したメモリ・アドレスを比較することによって達成され
ることを特徴とする請求項１６に記載のコンピュータ・
システム。 - 【請求項１９】前記追い出し無効手段は、前記予約を持
つ前記ブロックが最も最近使用されたことを表示するこ
とによって前記予約を持つ前記ブロックが追い出しのた
めに選ばれることをプリエンティブに禁止することを特
徴とする請求項１７に記載のコンピュータ・システム。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/829,577 US6212605B1 (en) | 1997-03-31 | 1997-03-31 | Eviction override for larx-reserved addresses |
| US08/829577 | 1997-03-31 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10283261A true JPH10283261A (ja) | 1998-10-23 |
Family
ID=25254911
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10059385A Pending JPH10283261A (ja) | 1997-03-31 | 1998-03-11 | キャッシュ・エントリの予約処理方法及び装置 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6212605B1 (ja) |
| JP (1) | JPH10283261A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2009122694A1 (ja) * | 2008-03-31 | 2009-10-08 | パナソニック株式会社 | キャッシュメモリ装置、キャッシュメモリシステム、プロセッサシステム |
Families Citing this family (27)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6807620B1 (en) * | 2000-02-11 | 2004-10-19 | Sony Computer Entertainment Inc. | Game system with graphics processor |
| US6347360B1 (en) * | 2000-02-25 | 2002-02-12 | Sun Microsystems, Inc. | Apparatus and method for preventing cache data eviction during an atomic operation |
| US6766419B1 (en) * | 2000-03-31 | 2004-07-20 | Intel Corporation | Optimization of cache evictions through software hints |
| US6826662B2 (en) * | 2001-03-22 | 2004-11-30 | Sony Computer Entertainment Inc. | System and method for data synchronization for a computer architecture for broadband networks |
| US7516334B2 (en) | 2001-03-22 | 2009-04-07 | Sony Computer Entertainment Inc. | Power management for processing modules |
| US6526491B2 (en) | 2001-03-22 | 2003-02-25 | Sony Corporation Entertainment Inc. | Memory protection system and method for computer architecture for broadband networks |
| US7233998B2 (en) | 2001-03-22 | 2007-06-19 | Sony Computer Entertainment Inc. | Computer architecture and software cells for broadband networks |
| US7093104B2 (en) * | 2001-03-22 | 2006-08-15 | Sony Computer Entertainment Inc. | Processing modules for computer architecture for broadband networks |
| US7231500B2 (en) | 2001-03-22 | 2007-06-12 | Sony Computer Entertainment Inc. | External data interface in a computer architecture for broadband networks |
| US6809734B2 (en) | 2001-03-22 | 2004-10-26 | Sony Computer Entertainment Inc. | Resource dedication system and method for a computer architecture for broadband networks |
| US6747657B2 (en) * | 2001-12-31 | 2004-06-08 | Intel Corporation | Depth write disable for zone rendering |
| US7024519B2 (en) * | 2002-05-06 | 2006-04-04 | Sony Computer Entertainment Inc. | Methods and apparatus for controlling hierarchical cache memory |
| ATE534078T1 (de) * | 2002-07-23 | 2011-12-15 | Research In Motion Ltd | Datenspeicher-verwaltungs-system und- verfahren, für drahtlose vorrichtungen |
| US20050076179A1 (en) * | 2003-10-02 | 2005-04-07 | International Business Machines Corporation | Cache optimized logical partitioning a symmetric multi-processor data processing system |
| US8224639B2 (en) | 2004-03-29 | 2012-07-17 | Sony Computer Entertainment Inc. | Methods and apparatus for achieving thermal management using processing task scheduling |
| US20050289300A1 (en) * | 2004-06-24 | 2005-12-29 | International Business Machines Corporation | Disable write back on atomic reserved line in a small cache system |
| US7437541B2 (en) * | 2004-07-08 | 2008-10-14 | International Business Machiens Corporation | Atomically updating 64 bit fields in the 32 bit AIX kernel |
| US7197604B2 (en) * | 2004-10-14 | 2007-03-27 | International Business Machines Corporation | Processor, data processing system and method for synchronzing access to data in shared memory |
| US20080065865A1 (en) * | 2006-09-08 | 2008-03-13 | Ilhyun Kim | In-use bits for efficient instruction fetch operations |
| US9013498B1 (en) * | 2008-12-19 | 2015-04-21 | Nvidia Corporation | Determining a working set of texture maps |
| US8832415B2 (en) * | 2010-01-08 | 2014-09-09 | International Business Machines Corporation | Mapping virtual addresses to different physical addresses for value disambiguation for thread memory access requests |
| US8533399B2 (en) * | 2010-01-15 | 2013-09-10 | International Business Machines Corporation | Cache directory look-up re-use as conflict check mechanism for speculative memory requests |
| US9507647B2 (en) * | 2010-01-08 | 2016-11-29 | Globalfoundries Inc. | Cache as point of coherence in multiprocessor system |
| US9323467B2 (en) * | 2013-10-29 | 2016-04-26 | Western Digital Technologies, Inc. | Data storage device startup |
| US10261911B2 (en) * | 2016-09-08 | 2019-04-16 | The Johns Hopkins University | Apparatus and method for computational workflow management |
| US11436158B2 (en) | 2020-05-29 | 2022-09-06 | International Business Machines Corporation | Fine-grained forced cache eviction |
| US12596490B2 (en) * | 2024-03-13 | 2026-04-07 | Nvidia Corporation | Memory management using a register |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4910656A (en) * | 1987-09-21 | 1990-03-20 | Motorola, Inc. | Bus master having selective burst initiation |
| US5155824A (en) * | 1989-05-15 | 1992-10-13 | Motorola, Inc. | System for transferring selected data words between main memory and cache with multiple data words and multiple dirty bits for each address |
| US5454093A (en) * | 1991-02-25 | 1995-09-26 | International Business Machines Corporation | Buffer bypass for quick data access |
| GB2260628A (en) * | 1991-10-11 | 1993-04-21 | Intel Corp | Line buffer for cache memory |
| US5428761A (en) * | 1992-03-12 | 1995-06-27 | Digital Equipment Corporation | System for achieving atomic non-sequential multi-word operations in shared memory |
| GB9307359D0 (en) * | 1993-04-08 | 1993-06-02 | Int Computers Ltd | Cache replacement mechanism |
| US5623627A (en) * | 1993-12-09 | 1997-04-22 | Advanced Micro Devices, Inc. | Computer memory architecture including a replacement cache |
| US5526510A (en) * | 1994-02-28 | 1996-06-11 | Intel Corporation | Method and apparatus for implementing a single clock cycle line replacement in a data cache unit |
| US5594886A (en) * | 1994-10-23 | 1997-01-14 | Lsi Logic Corporation | Pseudo-LRU cache memory replacement method and apparatus utilizing nodes |
| US5778430A (en) * | 1996-04-19 | 1998-07-07 | Eccs, Inc. | Method and apparatus for computer disk cache management |
| US5781926A (en) * | 1996-05-20 | 1998-07-14 | Integrated Device Technology, Inc. | Method and apparatus for sub cache line access and storage allowing access to sub cache lines before completion of line fill |
-
1997
- 1997-03-31 US US08/829,577 patent/US6212605B1/en not_active Expired - Fee Related
-
1998
- 1998-03-11 JP JP10059385A patent/JPH10283261A/ja active Pending
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2009122694A1 (ja) * | 2008-03-31 | 2009-10-08 | パナソニック株式会社 | キャッシュメモリ装置、キャッシュメモリシステム、プロセッサシステム |
| JP4767361B2 (ja) * | 2008-03-31 | 2011-09-07 | パナソニック株式会社 | キャッシュメモリ装置、キャッシュメモリシステム、プロセッサシステム |
Also Published As
| Publication number | Publication date |
|---|---|
| US6212605B1 (en) | 2001-04-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH10283261A (ja) | キャッシュ・エントリの予約処理方法及び装置 | |
| US6085294A (en) | Distributed data dependency stall mechanism | |
| US6748501B2 (en) | Microprocessor reservation mechanism for a hashed address system | |
| JP3431824B2 (ja) | アクセス方法及び処理装置 | |
| US7827354B2 (en) | Victim cache using direct intervention | |
| US5706464A (en) | Method and system for achieving atomic memory references in a multilevel cache data processing system | |
| US7925839B1 (en) | System and method for performing memory operations in a computing system | |
| KR100204741B1 (ko) | 제1및 제2캐시 메모리 사용방법 | |
| US7765360B2 (en) | Performing useful computations while waiting for a line in a system with a software implemented cache | |
| CN106897230B (zh) | 用于处理原子更新操作的装置和方法 | |
| US20110167222A1 (en) | Unbounded transactional memory system and method | |
| CN111263934B (zh) | 至少具有三个缓存级别的缓存层级的混合低级缓存包含策略 | |
| US7305523B2 (en) | Cache memory direct intervention | |
| US5671231A (en) | Method and apparatus for performing cache snoop testing on a cache system | |
| CN101593161A (zh) | 确保微处理器的快取存储器层级数据一致性的装置与方法 | |
| US6105108A (en) | Method and apparatus for releasing victim data buffers of computer systems by comparing a probe counter with a service counter | |
| CN101446923A (zh) | 一种响应于指令而清洗高速缓冲存储器线的装置和方法 | |
| US20160314069A1 (en) | Non-Temporal Write Combining Using Cache Resources | |
| US6061765A (en) | Independent victim data buffer and probe buffer release control utilzing control flag | |
| US6202126B1 (en) | Victimization of clean data blocks | |
| US6434665B1 (en) | Cache memory store buffer | |
| CN1127693C (zh) | 保持指令、数据高速缓存之间相关性的方法和设备 | |
| US6182201B1 (en) | Demand-based issuance of cache operations to a system bus | |
| JP5482197B2 (ja) | 演算処理装置、情報処理装置及びキャッシュメモリ制御方法 | |
| US5920889A (en) | Apparatus and method for write miss processing in a copy-back data cache with an allocating load buffer and a non-allocating store buffer |