JP2000067024A - 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ - Google Patents
分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリInfo
- Publication number
- JP2000067024A JP2000067024A JP11127277A JP12727799A JP2000067024A JP 2000067024 A JP2000067024 A JP 2000067024A JP 11127277 A JP11127277 A JP 11127277A JP 12727799 A JP12727799 A JP 12727799A JP 2000067024 A JP2000067024 A JP 2000067024A
- Authority
- JP
- Japan
- Prior art keywords
- directory
- cache
- data processing
- processing system
- memory
- 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; CALCULATING OR 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/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0815—Cache consistency protocols
- G06F12/0817—Cache consistency protocols using directory methods
- G06F12/082—Associative directories
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
- G06F15/163—Interprocessor communication
- G06F15/167—Interprocessor communication using a common memory, e.g. mailbox
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
- G06F15/177—Initialisation or configuration control
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【課題】 マルチプロセッサ・データ処理システムに関
し、特にキャッシュ中のラインの様々なコヒーレンス状
態の様々なディレクトリ要求を利用してメモリ・サブシ
ステムの性能を改善したディレクトリ・アーキテクチャ
を提供する。 【解決手段】 多数のノードを伴い、各ノードが複数の
プロセッサを含み、各プロセッサが関連キャッシュを有
する、分散共有メモリ・マルチプロセッサ・システムの
ための分割疎ディレクトリを提供する。分割疎ディレク
トリは、コヒーレンス制御装置、一時的状態バッファ及
び外部ディレクトリを含むメモリ・サブシステム内に存
在する。分割疎ディレクトリはノード中のキャッシュ・
ラインに関する情報を保存するが、その際一時的状態バ
ッファは遷移キャッシュ・ラインに関する情報を保持
し、外部ディレクトリは非遷移キャッシュ・ラインに関
する状態情報を保持する。
し、特にキャッシュ中のラインの様々なコヒーレンス状
態の様々なディレクトリ要求を利用してメモリ・サブシ
ステムの性能を改善したディレクトリ・アーキテクチャ
を提供する。 【解決手段】 多数のノードを伴い、各ノードが複数の
プロセッサを含み、各プロセッサが関連キャッシュを有
する、分散共有メモリ・マルチプロセッサ・システムの
ための分割疎ディレクトリを提供する。分割疎ディレク
トリは、コヒーレンス制御装置、一時的状態バッファ及
び外部ディレクトリを含むメモリ・サブシステム内に存
在する。分割疎ディレクトリはノード中のキャッシュ・
ラインに関する情報を保存するが、その際一時的状態バ
ッファは遷移キャッシュ・ラインに関する情報を保持
し、外部ディレクトリは非遷移キャッシュ・ラインに関
する状態情報を保持する。
Description
【０００１】
【発明の属する技術分野】本発明はマルチプロセッサ・
データ処理システムに関し、特にマルチバス共有メモリ
・システムを伴う複数のマルチプロセッサのキャッシュ
・コヒーレンスに関する。
データ処理システムに関し、特にマルチバス共有メモリ
・システムを伴う複数のマルチプロセッサのキャッシュ
・コヒーレンスに関する。
【０００２】コンピュータ・システムの中には、１つの
プログラムに対して並行して動作し、プログラムの実行
速度を上げることのできる多数のプロセッサによって構
築されているものがある。こうしたマルチプロセッサ・
システムのアーキテクチャは、多数のプロセッサ間の通
信に使用される機構によって分類される。共有メモリ・
アーキテクチャでは、すべてのプロセッサは１つの大き
なメモリにアクセスし、この共有メモリの読み出し及び
書き込みを行うことによって互いに通信する。
プログラムに対して並行して動作し、プログラムの実行
速度を上げることのできる多数のプロセッサによって構
築されているものがある。こうしたマルチプロセッサ・
システムのアーキテクチャは、多数のプロセッサ間の通
信に使用される機構によって分類される。共有メモリ・
アーキテクチャでは、すべてのプロセッサは１つの大き
なメモリにアクセスし、この共有メモリの読み出し及び
書き込みを行うことによって互いに通信する。
【０００３】なお、本出願は、１９９８年５月８日出願
の米国仮出願第６０／０８４，７９５号の利益を請求す
る。本出願は、１９９８年３月１２日出願の「パイプラ
イン化されたスヌーピープロトコルを有する相互接続用
マルチプロセッサノードのためのキャッシュコヒーレン
スユニット」と題された同時係属中の米国特許出願第０
９／０４１，５６８号、１９９８年１月７日出願の「統
合されたメッセージパッシングサポートを備える分散共
有メモリマルチプロセッサのためのメモリ保護メカニズ
ム」と題された同時係属中の米国特許出願第０９／００
３，７７１号及び、１９９８年１月７日出願の「分散共
有メモリマルチプロセッサシステムのための統合化され
たメッセージパッシングとメモリ保護を備えるキャッシ
ュコヒーレンスユニット」と題された同時係属中の米国
特許出願第０９／００３，７２１号に関連するが、これ
らは引用によって本出願の記載に援用する。
の米国仮出願第６０／０８４，７９５号の利益を請求す
る。本出願は、１９９８年３月１２日出願の「パイプラ
イン化されたスヌーピープロトコルを有する相互接続用
マルチプロセッサノードのためのキャッシュコヒーレン
スユニット」と題された同時係属中の米国特許出願第０
９／０４１，５６８号、１９９８年１月７日出願の「統
合されたメッセージパッシングサポートを備える分散共
有メモリマルチプロセッサのためのメモリ保護メカニズ
ム」と題された同時係属中の米国特許出願第０９／００
３，７７１号及び、１９９８年１月７日出願の「分散共
有メモリマルチプロセッサシステムのための統合化され
たメッセージパッシングとメモリ保護を備えるキャッシ
ュコヒーレンスユニット」と題された同時係属中の米国
特許出願第０９／００３，７２１号に関連するが、これ
らは引用によって本出願の記載に援用する。
【０００４】
【従来の技術】コンピュータ・システム・ノードは、プ
ロセッサ・サブシステムとメモリ・サブシステムに分割
される。メモリ・サブシステムには主ダイナミック・ラ
ンダムアクセス・メモリ（ＤＲＡＭ）が含まれ、いくつ
かの接続されたプロセッサからの要求に応答してメモリ
からデータを提供する。普通、メモリ・サブシステムで
データにアクセスするために費やされる時間の量はプロ
セッサの速度と比較してかなり長いので、プロセッサに
は動作を改善するためキャッシュを備えることが多い。
キャッシュはプロセッサと主メモリの間に接続された小
さなメモリで、主メモリのロケーションの最近使用され
たデータを保存する。転送によってキャッシュを出入り
できるデータの最小単位を「ライン」と呼ぶ。
ロセッサ・サブシステムとメモリ・サブシステムに分割
される。メモリ・サブシステムには主ダイナミック・ラ
ンダムアクセス・メモリ（ＤＲＡＭ）が含まれ、いくつ
かの接続されたプロセッサからの要求に応答してメモリ
からデータを提供する。普通、メモリ・サブシステムで
データにアクセスするために費やされる時間の量はプロ
セッサの速度と比較してかなり長いので、プロセッサに
は動作を改善するためキャッシュを備えることが多い。
キャッシュはプロセッサと主メモリの間に接続された小
さなメモリで、主メモリのロケーションの最近使用され
たデータを保存する。転送によってキャッシュを出入り
できるデータの最小単位を「ライン」と呼ぶ。
【０００５】プロセッサ・サブシステムにはプロセッサ
と１つかそれ以上のキャッシュが含まれる。キャッシュ
は主メモリ・サブシステムよりかなり速いアクセス時間
を有するが普通かなり小さい。小さなキャッシュは主メ
モリにあるすべてのデータを保持することができないの
で、現在保持しているデータのアドレス（タグと呼ばれ
る）と値の両方を保存しなければならない。特定のライ
ンを要求する場合、プロセッサはまずそのアドレスを現
在キャッシュにある各タグと突き合わせ、そのラインが
キャッシュにあるかを調べる。一致がない場合、メモリ
・サブシステムは要求を主メモリに伝える。
と１つかそれ以上のキャッシュが含まれる。キャッシュ
は主メモリ・サブシステムよりかなり速いアクセス時間
を有するが普通かなり小さい。小さなキャッシュは主メ
モリにあるすべてのデータを保持することができないの
で、現在保持しているデータのアドレス（タグと呼ばれ
る）と値の両方を保存しなければならない。特定のライ
ンを要求する場合、プロセッサはまずそのアドレスを現
在キャッシュにある各タグと突き合わせ、そのラインが
キャッシュにあるかを調べる。一致がない場合、メモリ
・サブシステムは要求を主メモリに伝える。
【０００６】すべてのキャッシュ・スキームは主メモリ
を物理的に連続したセグメントに分割する。キャッシュ
は普通、合計がセグメントと同じサイズになる一連のラ
インとして編成される。タグは、どのセグメントが現在
キャッシュを占めているかを識別するために使用され
る。要求されたアドレスを有するラインがキャッシュに
含まれている場合、そのラインのデータがプロセッサに
転送される。そのラインがキャッシュにない場合、その
ラインを含む主メモリのセグメントがキャッシュにフェ
ッチされ、そのラインがプロセッサに転送される。
を物理的に連続したセグメントに分割する。キャッシュ
は普通、合計がセグメントと同じサイズになる一連のラ
インとして編成される。タグは、どのセグメントが現在
キャッシュを占めているかを識別するために使用され
る。要求されたアドレスを有するラインがキャッシュに
含まれている場合、そのラインのデータがプロセッサに
転送される。そのラインがキャッシュにない場合、その
ラインを含む主メモリのセグメントがキャッシュにフェ
ッチされ、そのラインがプロセッサに転送される。
【０００７】直接マップ・キャッシュ・メモリでは、セ
グメントはキャッシュ・ラインという形を取り、そのラ
イン番号は主メモリ・アドレスから容易に計算できる。
連想キャッシュは、任意のセグメントのラインが任意の
キャッシュ・ラインにロードされる点で直接マップ・キ
ャッシュと異なっている。キャッシュ・ラインはデータ
自身とさらにセグメント番号を記憶する必要がある。キ
ャッシュの探索を可能にするため、連想キャッシュに
は、キャッシュのライン毎のセグメント番号に対するセ
グメント番号アドレスを同時に検査する回路が含まれて
いる。この追加回路のため、連想キャッシュはより高価
になる。
グメントはキャッシュ・ラインという形を取り、そのラ
イン番号は主メモリ・アドレスから容易に計算できる。
連想キャッシュは、任意のセグメントのラインが任意の
キャッシュ・ラインにロードされる点で直接マップ・キ
ャッシュと異なっている。キャッシュ・ラインはデータ
自身とさらにセグメント番号を記憶する必要がある。キ
ャッシュの探索を可能にするため、連想キャッシュに
は、キャッシュのライン毎のセグメント番号に対するセ
グメント番号アドレスを同時に検査する回路が含まれて
いる。この追加回路のため、連想キャッシュはより高価
になる。
【０００８】セット連想マッピングは、直接マッピング
と連想キャッシュ両方のアーキテクチャを結合する。セ
ット連想キャッシュは、各々が多数のラインを含む多数
のセットとして編成される。セット連想マッピングで
は、キャッシュ・セットはアドレス・セグメント番号に
よって決定されるが、セット内のラインはアドレス・セ
グメント番号によって決定されない。通常、セット連想
キャッシュは双方向であり、すなわちキャッシュに２つ
のセットが存在するので、要求されたメモリ・ラインを
提供する際直接マップ・キャッシュに対してキャッシュ
・ヒット率が大きく改善される。
と連想キャッシュ両方のアーキテクチャを結合する。セ
ット連想キャッシュは、各々が多数のラインを含む多数
のセットとして編成される。セット連想マッピングで
は、キャッシュ・セットはアドレス・セグメント番号に
よって決定されるが、セット内のラインはアドレス・セ
グメント番号によって決定されない。通常、セット連想
キャッシュは双方向であり、すなわちキャッシュに２つ
のセットが存在するので、要求されたメモリ・ラインを
提供する際直接マップ・キャッシュに対してキャッシュ
・ヒット率が大きく改善される。
【０００９】図１は、メモリ中のデータを新しく要求す
るステップ１０２で開始される、通常の先行技術キャッ
シュ・メモリ・アクセス・アルゴリズム１００のフロー
チャートを示す。ステップ１０４では、要求されたデー
タ・アドレスがキャッシュ・タグと比較される。ステッ
プ１０６は要求されたデータがキャッシュにあるか否か
を判定する。ステップ１０６で、データの有効なコピー
がキャッシュにない場合、ステップ１０８でメモリ・サ
ブシステムは要求されたデータを主メモリからキャッシ
ュ・メモリにフェッチする。要求されたデータがキャッ
シュにある場合、ステップ１１０でメモリ・サブシステ
ムは要求を出したプロセッサにデータを転送する。デー
タがプロセッサに転送された後、メモリ・アクセス・ア
ルゴリズムはステップ１０２に戻り、次のメモリ要求を
待つ。
るステップ１０２で開始される、通常の先行技術キャッ
シュ・メモリ・アクセス・アルゴリズム１００のフロー
チャートを示す。ステップ１０４では、要求されたデー
タ・アドレスがキャッシュ・タグと比較される。ステッ
プ１０６は要求されたデータがキャッシュにあるか否か
を判定する。ステップ１０６で、データの有効なコピー
がキャッシュにない場合、ステップ１０８でメモリ・サ
ブシステムは要求されたデータを主メモリからキャッシ
ュ・メモリにフェッチする。要求されたデータがキャッ
シュにある場合、ステップ１１０でメモリ・サブシステ
ムは要求を出したプロセッサにデータを転送する。デー
タがプロセッサに転送された後、メモリ・アクセス・ア
ルゴリズムはステップ１０２に戻り、次のメモリ要求を
待つ。
【００１０】共有メモリマルチプロセッサ・システムで
は、各プロセッサは通常固有のキャッシュを有するの
で、システムは多数のキャッシュを有することになる。
各キャッシュは所定のデータ項目のコピーを保持できる
ので、すべてのキャッシュの状態がプロセッサの１つに
よって書かれた最新のコピーと一貫性のある最新のもの
であるように維持することが重要である。キャッシュま
たは主メモリから、メモリ・サブシステムの動作を管理
する一組の規則であるプロセッサのメモリ・モデルの規
定通りに、正しい値を返すことはメモリ・サブシステム
の責任である。これはキャッシュ・コヒーレンス・プロ
トコルの使用を通じて達成される。
は、各プロセッサは通常固有のキャッシュを有するの
で、システムは多数のキャッシュを有することになる。
各キャッシュは所定のデータ項目のコピーを保持できる
ので、すべてのキャッシュの状態がプロセッサの１つに
よって書かれた最新のコピーと一貫性のある最新のもの
であるように維持することが重要である。キャッシュま
たは主メモリから、メモリ・サブシステムの動作を管理
する一組の規則であるプロセッサのメモリ・モデルの規
定通りに、正しい値を返すことはメモリ・サブシステム
の責任である。これはキャッシュ・コヒーレンス・プロ
トコルの使用を通じて達成される。
【００１１】従って、主メモリに加えて、メモリ・サブ
システムには、システムのキャッシュ・コヒーレンスを
維持するためにキャッシュ・コヒーレンス・プロトコル
が使用する制御情報を含むキャッシュ・コヒーレンス・
ディレクトリが含まれる。従来のディレクトリは、メモ
リ・ロケーション・データがシステムのどこかのキャッ
シュに存在するか否かを示す状態情報を伴う各メモリ・
ロケーションのエントリを有する。主メモリ・ラインが
存在するノードはそのラインのホーム・ノードと呼ばれ
る。ディレクトリが存在するノードはローカル・ノード
と呼ばれ、他のノードはリモート・ノードと呼ばれる。
コヒーレンス・プロトコルは各キャッシュ・ラインの状
態を把握し、データの最新のコピーがプロセッサに与え
られることを保証する。また、このプロトコルは、要求
に応答してなされるすべての遷移とトランザクションを
指定する。キャッシュ・ライン上で行われるすべての処
理はディレクトリに保存された状態に反映される。一般
的なスキームは３つの永続状態を使用してこれを達成す
る。「無効」状態は、ラインがどこにもキャッシュされ
ず主メモリが唯一のコピーである場合に存在する。「共
有」状態は、リモート・ノード（プロセッサのグルー
プ）がラインの有効なコピーを有する場合に存在する。
これは「グローバル共有状態」、すなわちローカル・ノ
ードの何れかのキャッシュまたは少なくとも１つのリモ
ート・キャッシュがラインの有効なコピーを有するグロ
ーバル・キャッシュ・コヒーレンス状態と混同してはな
らない。こうした有効なラインは読み取り専用であり、
主メモリのコピーと同一である。「ダーティ」状態は、
ラインがリモート・ノードの１つのキャッシュだけで有
効な場合に存在する。そのコピーがそのプロセッサによ
って修正され、主メモリが古いデータを含んでいること
がある。
システムには、システムのキャッシュ・コヒーレンスを
維持するためにキャッシュ・コヒーレンス・プロトコル
が使用する制御情報を含むキャッシュ・コヒーレンス・
ディレクトリが含まれる。従来のディレクトリは、メモ
リ・ロケーション・データがシステムのどこかのキャッ
シュに存在するか否かを示す状態情報を伴う各メモリ・
ロケーションのエントリを有する。主メモリ・ラインが
存在するノードはそのラインのホーム・ノードと呼ばれ
る。ディレクトリが存在するノードはローカル・ノード
と呼ばれ、他のノードはリモート・ノードと呼ばれる。
コヒーレンス・プロトコルは各キャッシュ・ラインの状
態を把握し、データの最新のコピーがプロセッサに与え
られることを保証する。また、このプロトコルは、要求
に応答してなされるすべての遷移とトランザクションを
指定する。キャッシュ・ライン上で行われるすべての処
理はディレクトリに保存された状態に反映される。一般
的なスキームは３つの永続状態を使用してこれを達成す
る。「無効」状態は、ラインがどこにもキャッシュされ
ず主メモリが唯一のコピーである場合に存在する。「共
有」状態は、リモート・ノード（プロセッサのグルー
プ）がラインの有効なコピーを有する場合に存在する。
これは「グローバル共有状態」、すなわちローカル・ノ
ードの何れかのキャッシュまたは少なくとも１つのリモ
ート・キャッシュがラインの有効なコピーを有するグロ
ーバル・キャッシュ・コヒーレンス状態と混同してはな
らない。こうした有効なラインは読み取り専用であり、
主メモリのコピーと同一である。「ダーティ」状態は、
ラインがリモート・ノードの１つのキャッシュだけで有
効な場合に存在する。そのコピーがそのプロセッサによ
って修正され、主メモリが古いデータを含んでいること
がある。
【００１２】図２は、キャッシュ・コヒーレンス・ディ
レクトリを使用するメモリ・アクセス・アルゴリズム２
００のフローチャートを示す。ステップ２０２で、メモ
リ中のデータの新しい要求によってアルゴリズムが開始
される。ステップ２０４では、アルゴリズムは要求され
たデータ・アドレスをキャッシュ・コヒーレンス・ディ
レクトリ中のディレクトリ・タグと比較する。
レクトリを使用するメモリ・アクセス・アルゴリズム２
００のフローチャートを示す。ステップ２０２で、メモ
リ中のデータの新しい要求によってアルゴリズムが開始
される。ステップ２０４では、アルゴリズムは要求され
たデータ・アドレスをキャッシュ・コヒーレンス・ディ
レクトリ中のディレクトリ・タグと比較する。
【００１３】ステップ２０６では、アルゴリズムはキャ
ッシュ・コヒーレンス・ディレクトリから要求されたデ
ータの状態を判定する。ステップ２０６で状態が「無
効」である（すなわち、キャッシュにデータの有効なコ
ピーがない）場合、ステップ２０８でアルゴリズムは要
求されたデータを主メモリまたはローカル・キャッシュ
からキャッシュ・メモリにフェッチする。ステップ２０
６で状態が「共有」である（すなわち、要求されたデー
タがリモート・ノードのキャッシュにある）場合、ステ
ップ２１２でアルゴリズムはデータをメモリからフェッ
チし、要求が「保存」である場合、キャッシュされたコ
ピーを無効にする。ステップ２０６で状態が「ダーテ
ィ」である（すなわち、データの最新バージョンが１つ
のキャッシュでだけ有効である）場合、ステップ２１０
でアルゴリズムは要求されたデータをキャッシュからフ
ェッチする。
ッシュ・コヒーレンス・ディレクトリから要求されたデ
ータの状態を判定する。ステップ２０６で状態が「無
効」である（すなわち、キャッシュにデータの有効なコ
ピーがない）場合、ステップ２０８でアルゴリズムは要
求されたデータを主メモリまたはローカル・キャッシュ
からキャッシュ・メモリにフェッチする。ステップ２０
６で状態が「共有」である（すなわち、要求されたデー
タがリモート・ノードのキャッシュにある）場合、ステ
ップ２１２でアルゴリズムはデータをメモリからフェッ
チし、要求が「保存」である場合、キャッシュされたコ
ピーを無効にする。ステップ２０６で状態が「ダーテ
ィ」である（すなわち、データの最新バージョンが１つ
のキャッシュでだけ有効である）場合、ステップ２１０
でアルゴリズムは要求されたデータをキャッシュからフ
ェッチする。
【００１４】データの有効なコピーがフェッチされる
と、ステップ２１４でアルゴリズムはデータを要求を出
したプロセッサに転送する。データがプロセッサに転送
された後、メモリ・アクセス・アルゴリズムはステップ
２０２に戻り、次のメモリ要求を待つ。
と、ステップ２１４でアルゴリズムはデータを要求を出
したプロセッサに転送する。データがプロセッサに転送
された後、メモリ・アクセス・アルゴリズムはステップ
２０２に戻り、次のメモリ要求を待つ。
【００１５】コヒーレンス・プロトコルは、ラインが遷
移中であることを示すため他の遷移状態を使用すること
がある。十分な時間を与えれば、こうした遷移状態は３
つの永続状態の１つに復帰する。
移中であることを示すため他の遷移状態を使用すること
がある。十分な時間を与えれば、こうした遷移状態は３
つの永続状態の１つに復帰する。
【００１６】キャッシュ・コヒーレンス・プロトコルは
通常有限状態マシンによって実現されるが、そこではデ
ータの最新の値がどこに存在するかを状態が決定する。
状態値はメモリ中のすべてのラインに明示的または暗示
的に関連しなければならない。通常、ある状態情報を各
キャッシュのキャッシュ・タグに追加することによって
明示的関連付けがなされる。キャッシュされていないラ
インについては、状態値がシステム中のどこにもタグの
一致がないということを暗示しており、最新の値は主メ
モリにあることが分かる。
通常有限状態マシンによって実現されるが、そこではデ
ータの最新の値がどこに存在するかを状態が決定する。
状態値はメモリ中のすべてのラインに明示的または暗示
的に関連しなければならない。通常、ある状態情報を各
キャッシュのキャッシュ・タグに追加することによって
明示的関連付けがなされる。キャッシュされていないラ
インについては、状態値がシステム中のどこにもタグの
一致がないということを暗示しており、最新の値は主メ
モリにあることが分かる。
【００１７】プロセッサの要求がある毎に、メモリ・サ
ブシステムはシステムのすべてのキャッシュのすべての
キャッシュ・タグを調べなければならない。これを行う
２つの方法が存在する。「スヌーピー・プロトコル」と
呼ばれることもある第１の方法では、各キャッシュはす
べての要求を「のぞき回り(snoop) 」、データの最新の
コピーを有している場合メモリ・サブシステムに信号を
送る。「ディレクトリ・ベース・キャッシュ・コヒーレ
ンス・プロトコル」と呼ばれることもある第２の方法で
は、メモリ・サブシステムは各キャッシュのタグのコピ
ーを保持し、最新のコピーのロケーションを発見するこ
とができる。
ブシステムはシステムのすべてのキャッシュのすべての
キャッシュ・タグを調べなければならない。これを行う
２つの方法が存在する。「スヌーピー・プロトコル」と
呼ばれることもある第１の方法では、各キャッシュはす
べての要求を「のぞき回り(snoop) 」、データの最新の
コピーを有している場合メモリ・サブシステムに信号を
送る。「ディレクトリ・ベース・キャッシュ・コヒーレ
ンス・プロトコル」と呼ばれることもある第２の方法で
は、メモリ・サブシステムは各キャッシュのタグのコピ
ーを保持し、最新のコピーのロケーションを発見するこ
とができる。
【００１８】キャッシュ・コヒーレンス不均一メモリ・
アーキテクチャ（ｃｃ−ＮＵＭＡ）マシンでは、いくつ
かのメモリ・サブシステムが互いにリンクされ、キャッ
シュ・コヒーレンス・プロトコルを使用してメモリ・サ
ブシステム間の正しいメモリ・モデルを強化し、単一共
有メモリ・システムを形成する。すなわち、マシンはメ
モリ・サブシステムの追加によって拡張され、メモリへ
の通信経路の帯域幅が拡大する。同様に、キャッシュ・
コヒーレンス・プロトコルもディレクトリ・ベースにす
ることでスケーラブルなものにすることができる。メモ
リ・サブシステムを追加すればするほど、ディレクトリ
の数も多くなる。ディレクトリはシステムのノード間で
分散される。各ディレクトリはすべてのキャッシュ・ラ
インの状態を追跡する。従って、ディレクトリ・サイズ
はキャッシュの合計サイズに比例し、ディレクトリはデ
ィレクトリ・エントリのセット連想キャッシュとして編
成される。
アーキテクチャ（ｃｃ−ＮＵＭＡ）マシンでは、いくつ
かのメモリ・サブシステムが互いにリンクされ、キャッ
シュ・コヒーレンス・プロトコルを使用してメモリ・サ
ブシステム間の正しいメモリ・モデルを強化し、単一共
有メモリ・システムを形成する。すなわち、マシンはメ
モリ・サブシステムの追加によって拡張され、メモリへ
の通信経路の帯域幅が拡大する。同様に、キャッシュ・
コヒーレンス・プロトコルもディレクトリ・ベースにす
ることでスケーラブルなものにすることができる。メモ
リ・サブシステムを追加すればするほど、ディレクトリ
の数も多くなる。ディレクトリはシステムのノード間で
分散される。各ディレクトリはすべてのキャッシュ・ラ
インの状態を追跡する。従って、ディレクトリ・サイズ
はキャッシュの合計サイズに比例し、ディレクトリはデ
ィレクトリ・エントリのセット連想キャッシュとして編
成される。
【００１９】直接マッピングは常にセグメントを同じ位
置に置くので、キャッシュが一杯の時どのラインを置換
するかという問題は回避される。しかし、完全連想及び
セット連想キャッシュ・マッピング・スキームは、キャ
ッシュのどのセグメントを新たに要求されたセグメント
で置換するかを決定する置換プロトコルが必要である。
最も一般的なプロトコルは「最低使用頻度」（ＬＲＵ）
プロトコルであるが、これは最も長い時間使用されなか
ったセグメントを置換する。
置に置くので、キャッシュが一杯の時どのラインを置換
するかという問題は回避される。しかし、完全連想及び
セット連想キャッシュ・マッピング・スキームは、キャ
ッシュのどのセグメントを新たに要求されたセグメント
で置換するかを決定する置換プロトコルが必要である。
最も一般的なプロトコルは「最低使用頻度」（ＬＲＵ）
プロトコルであるが、これは最も長い時間使用されなか
ったセグメントを置換する。
【００２０】
【発明が解決しようとする課題】図３は、バス３１８に
よって主ＤＲＡＭメモリ３２２のメモリ制御装置３２０
に接続されたそれぞれのローカル・キャッシュ３１０、
３１２、３１４及び３１６を有する多数のＣＰＵ３０
２、３０４、３０６及び３０８を含む従来技術システム
３００を示す。この例の疎でないディレクトリでは、主
メモリ３２２は、各メモリ・ラインのロケーションにつ
いて、ディレクトリ３２４のエントリのために確保され
た空間を有する。有効なディレクトリ・エントリの数を
決定するキャッシュされたラインの合計数は普通主メモ
リのラインの合計数よりかなり少ないため、これはメモ
リ空間の浪費である。ディレクトリ３２４がすべてのコ
ヒーレンス状態を保持するために同じメモリ３２２が使
用され、短期間の遷移状態にあるライン専用のディレク
トリが利用できるより高速で小さなメモリがないため、
これはメモリ帯域幅の浪費でもある。
よって主ＤＲＡＭメモリ３２２のメモリ制御装置３２０
に接続されたそれぞれのローカル・キャッシュ３１０、
３１２、３１４及び３１６を有する多数のＣＰＵ３０
２、３０４、３０６及び３０８を含む従来技術システム
３００を示す。この例の疎でないディレクトリでは、主
メモリ３２２は、各メモリ・ラインのロケーションにつ
いて、ディレクトリ３２４のエントリのために確保され
た空間を有する。有効なディレクトリ・エントリの数を
決定するキャッシュされたラインの合計数は普通主メモ
リのラインの合計数よりかなり少ないため、これはメモ
リ空間の浪費である。ディレクトリ３２４がすべてのコ
ヒーレンス状態を保持するために同じメモリ３２２が使
用され、短期間の遷移状態にあるライン専用のディレク
トリが利用できるより高速で小さなメモリがないため、
これはメモリ帯域幅の浪費でもある。
【００２１】従来技術のキャッシュ・コヒーレンス・プ
ロトコルは、ディレクトリ構造が遷移ライン状態と非遷
移ライン状態を区別しないという欠点がある。普通、遷
移状態と非遷移状態の間の遷移は１つだけだが、遷移状
態間に多数の遷移があり得る。すなわち、ラインが遷移
する時多数の状態変化が発生するため追加のディレクト
リ帯域幅が必要になる。
ロトコルは、ディレクトリ構造が遷移ライン状態と非遷
移ライン状態を区別しないという欠点がある。普通、遷
移状態と非遷移状態の間の遷移は１つだけだが、遷移状
態間に多数の遷移があり得る。すなわち、ラインが遷移
する時多数の状態変化が発生するため追加のディレクト
リ帯域幅が必要になる。
【００２２】従って、必要なものは、キャッシュ中のラ
インの様々なコヒーレンス状態の様々なディレクトリ要
求を利用してメモリ・サブシステムの性能を改善するこ
とのできる最適なディレクトリ・アーキテクチャを提供
するキャッシュ・コヒーレンス・プロトコルである。本
発明はそれを提供することを目的とする。
インの様々なコヒーレンス状態の様々なディレクトリ要
求を利用してメモリ・サブシステムの性能を改善するこ
とのできる最適なディレクトリ・アーキテクチャを提供
するキャッシュ・コヒーレンス・プロトコルである。本
発明はそれを提供することを目的とする。
【００２３】
【課題を解決するための手段】本発明には、多数のキャ
ッシュ・ライン・エントリを保存するキャッシュに接続
された少なくとも１つのプロセッサを各々有する多数の
マルチプロセッサ・ノード、コヒーレンス制御装置及
び、キャッシュ中のキャッシュ・ライン状態を把握する
ディレクトリが含まれる。このディレクトリには、キャ
ッシュのラインの第１サブセットに関する一時的状態情
報を保持する第１部分と、キャッシュのラインの第２サ
ブセットに関する非一時的状態情報を保持する第２部分
とが含まれる。
ッシュ・ライン・エントリを保存するキャッシュに接続
された少なくとも１つのプロセッサを各々有する多数の
マルチプロセッサ・ノード、コヒーレンス制御装置及
び、キャッシュ中のキャッシュ・ライン状態を把握する
ディレクトリが含まれる。このディレクトリには、キャ
ッシュのラインの第１サブセットに関する一時的状態情
報を保持する第１部分と、キャッシュのラインの第２サ
ブセットに関する非一時的状態情報を保持する第２部分
とが含まれる。
【００２４】本発明は、キャッシュ・コヒーレンス状態
を保持するために必要な外部記憶装置の量を減少させ
る。ラインが遷移状態にある時間の量は非常に短く、あ
る時間に遷移状態にあるラインはごく少数なので、本発
明は一時的状態バッファのサイズも減少させる。さら
に、本発明は、多数の遷移状態を通じて、遷移のための
外部ディレクトリへのアクセスを除去し、コヒーレンス
・プロトコルの総合的な処理能力を増大する。
を保持するために必要な外部記憶装置の量を減少させ
る。ラインが遷移状態にある時間の量は非常に短く、あ
る時間に遷移状態にあるラインはごく少数なので、本発
明は一時的状態バッファのサイズも減少させる。さら
に、本発明は、多数の遷移状態を通じて、遷移のための
外部ディレクトリへのアクセスを除去し、コヒーレンス
・プロトコルの総合的な処理能力を増大する。
【００２５】
【発明の実施の形態】本発明のこれらと他の利点は、当
業技術分野に熟練した者には以下の詳細な説明と添付の
図面から明らかになるだろう。本発明は、ディレクトリ
・ベース・キャッシュ・コヒーレンス・プロトコルにお
いてキャッシュ・コヒーレンス状態情報を使用する。す
なわち本発明には、永続状態を保持する外部ランダムア
クセス・メモリ（ＲＡＭ）と、遷移状態を保持する内部
バッファとが含まれる。従って、バッファが、キャッシ
ュ・コヒーレンス状態情報に加えて状態とデータ値の両
方を保存する従来技術のシステムに対して本発明は有利
である。このバッファは普通、遷移によってメモリを出
入りするラインのための内部完全連想キャッシュ拡張で
ある。 また本発明によって、多くの状態遷移が内部バ
ッファの中で完全になされるようになるため、外部ディ
レクトリの必要な帯域幅が減少し、総合的な処理能力が
増大する。従来技術の分割遷移システムは、何らかの状
態更新がある度に外部ディレクトリＲＡＭに対して読み
出しサイクルと書き込みサイクルを行わなければならな
い。
業技術分野に熟練した者には以下の詳細な説明と添付の
図面から明らかになるだろう。本発明は、ディレクトリ
・ベース・キャッシュ・コヒーレンス・プロトコルにお
いてキャッシュ・コヒーレンス状態情報を使用する。す
なわち本発明には、永続状態を保持する外部ランダムア
クセス・メモリ（ＲＡＭ）と、遷移状態を保持する内部
バッファとが含まれる。従って、バッファが、キャッシ
ュ・コヒーレンス状態情報に加えて状態とデータ値の両
方を保存する従来技術のシステムに対して本発明は有利
である。このバッファは普通、遷移によってメモリを出
入りするラインのための内部完全連想キャッシュ拡張で
ある。 また本発明によって、多くの状態遷移が内部バ
ッファの中で完全になされるようになるため、外部ディ
レクトリの必要な帯域幅が減少し、総合的な処理能力が
増大する。従来技術の分割遷移システムは、何らかの状
態更新がある度に外部ディレクトリＲＡＭに対して読み
出しサイクルと書き込みサイクルを行わなければならな
い。
【００２６】図４は、多数の接続されたノード４０
２、．．．、４０８及び４１０を備えるｃｃＮＵＭＡシ
ステム４００の概要を示す。各ノードには、ノード４１
０について図示するように、１つのメモリ・サブシステ
ム４４０に接続されたそれぞれのキャッシュ４２２、４
２４、．．．、及び４３０を有するいくつかの数のプロ
セッサ４１２、４１４、．．．、及び４２０が含まれ
る。メモリ・サブシステム４４０には、外部ディレクト
リ４６０、主メモリ４９０及び、コヒーレンス制御装置
４５０と一時的状態バッファ４７０を含むコヒーレンス
制御チップ４８０が含まれる。コヒーレンス制御装置４
５０は、外部ディレクトリ４６０と一時的状態バッファ
４７０に含まれる状態情報を読み出し及び書き込みを行
う。
２、．．．、４０８及び４１０を備えるｃｃＮＵＭＡシ
ステム４００の概要を示す。各ノードには、ノード４１
０について図示するように、１つのメモリ・サブシステ
ム４４０に接続されたそれぞれのキャッシュ４２２、４
２４、．．．、及び４３０を有するいくつかの数のプロ
セッサ４１２、４１４、．．．、及び４２０が含まれ
る。メモリ・サブシステム４４０には、外部ディレクト
リ４６０、主メモリ４９０及び、コヒーレンス制御装置
４５０と一時的状態バッファ４７０を含むコヒーレンス
制御チップ４８０が含まれる。コヒーレンス制御装置４
５０は、外部ディレクトリ４６０と一時的状態バッファ
４７０に含まれる状態情報を読み出し及び書き込みを行
う。
【００２７】外部ディレクトリ４６０は、普通既製のＲ
ＡＭを使用して実現される。一度に実行される「読み出
し」または「書き込み」は１つだけだが、読み出しと書
き込みをパイプラインすることができ、読み出しまたは
書き込みを完了するには普通多数のシステム・サイクル
を要する。これは普通セット連想または直接マップ・キ
ャッシュとして実現される。セット連想の場合、各セッ
トは、コヒーレンス制御装置４５０によって使用される
タグ、状態及び他の情報を各々含む多数のエントリを備
えている。通常、「最低使用頻度」（ＬＲＵ）フィール
ド等の、コヒーレンス制御装置４５０によるエントリの
割り当て及び割り当て解除を可能にする少量の他の情報
も存在する。コヒーレンス制御装置４５０は、ＲＡＭに
対する基本的な読み出し及び書き込み操作を行うことに
よって外部ディレクトリ４６０を管理する。これは既製
のＲＡＭであるので、その動作は周知でありここで詳細
には説明しない。
ＡＭを使用して実現される。一度に実行される「読み出
し」または「書き込み」は１つだけだが、読み出しと書
き込みをパイプラインすることができ、読み出しまたは
書き込みを完了するには普通多数のシステム・サイクル
を要する。これは普通セット連想または直接マップ・キ
ャッシュとして実現される。セット連想の場合、各セッ
トは、コヒーレンス制御装置４５０によって使用される
タグ、状態及び他の情報を各々含む多数のエントリを備
えている。通常、「最低使用頻度」（ＬＲＵ）フィール
ド等の、コヒーレンス制御装置４５０によるエントリの
割り当て及び割り当て解除を可能にする少量の他の情報
も存在する。コヒーレンス制御装置４５０は、ＲＡＭに
対する基本的な読み出し及び書き込み操作を行うことに
よって外部ディレクトリ４６０を管理する。これは既製
のＲＡＭであるので、その動作は周知でありここで詳細
には説明しない。
【００２８】一時的状態バッファ４７０は、コヒーレン
ス制御装置４５０によって使用されるタグ、状態及びそ
の他の情報を各々含む多数のエントリを含んでいる。一
時的状態バッファ４７０で行われる操作は、エントリの
割り当て、エントリの割り当て解除及びエントリの更新
である。さらに、一時的状態バッファ４７０は、すべて
のエントリが割り当てられたことをコヒーレンス制御装
置４５０に示す出力を有する。これらの操作も一時的状
態バッファ４７０で同時に行われる。
ス制御装置４５０によって使用されるタグ、状態及びそ
の他の情報を各々含む多数のエントリを含んでいる。一
時的状態バッファ４７０で行われる操作は、エントリの
割り当て、エントリの割り当て解除及びエントリの更新
である。さらに、一時的状態バッファ４７０は、すべて
のエントリが割り当てられたことをコヒーレンス制御装
置４５０に示す出力を有する。これらの操作も一時的状
態バッファ４７０で同時に行われる。
【００２９】割り当てには未使用エントリを発見するこ
とが含まれる。未使用エントリは、各エントリの明示的
ビットを有するか、またはエントリの状態を「無効」に
設定するかの何れかによって示される。未使用エントリ
は任意に選択されるが、１つの簡単な方法は優先順位デ
コーダ（図示せず）の使用によるものである。割り当て
は、状態を「有効」値として書き込み、エントリのすべ
てのフィールドを書き込むことによって行われる。その
後一時的状態バッファ４７０はコヒーレンス制御装置４
５０に割り当てされたエントリの数を戻す。
とが含まれる。未使用エントリは、各エントリの明示的
ビットを有するか、またはエントリの状態を「無効」に
設定するかの何れかによって示される。未使用エントリ
は任意に選択されるが、１つの簡単な方法は優先順位デ
コーダ（図示せず）の使用によるものである。割り当て
は、状態を「有効」値として書き込み、エントリのすべ
てのフィールドを書き込むことによって行われる。その
後一時的状態バッファ４７０はコヒーレンス制御装置４
５０に割り当てされたエントリの数を戻す。
【００３０】割り当て解除は、エントリか、または連想
ルックアップかの何れかによってなされる。エントリに
よってなされる場合、コヒーレンス制御装置４５０は割
り当て解除すべきエントリの数を提供する。連想ルック
アップによってなされる場合、一時的状態バッファ４７
０はアドレスを一時的状態バッファ４７０中のすべての
タグと比較し、どのエントリを割り当て解除すべきかを
決定する。割り当て解除は、明示的ビットを「無効」と
して設定するか、または状態を「無効」状態として設定
するかの何れかによってなされる。 コヒーレンス制御
装置４５０は、一時的状態バッファ４７０中の有効なエ
ントリを更新することができる。それはまず、明示的エ
ントリ番号を使用するか、または連想ルックアップを使
用するかの何れかによってどのエントリを更新すべきか
を決定する。次に一時的状態バッファ４７０は、コヒー
レンス制御装置４５０によって指定された、タグ・フィ
ールドでなく状態フィールドを含む、何らかのフィール
ドの書き込みを行う。
ルックアップかの何れかによってなされる。エントリに
よってなされる場合、コヒーレンス制御装置４５０は割
り当て解除すべきエントリの数を提供する。連想ルック
アップによってなされる場合、一時的状態バッファ４７
０はアドレスを一時的状態バッファ４７０中のすべての
タグと比較し、どのエントリを割り当て解除すべきかを
決定する。割り当て解除は、明示的ビットを「無効」と
して設定するか、または状態を「無効」状態として設定
するかの何れかによってなされる。 コヒーレンス制御
装置４５０は、一時的状態バッファ４７０中の有効なエ
ントリを更新することができる。それはまず、明示的エ
ントリ番号を使用するか、または連想ルックアップを使
用するかの何れかによってどのエントリを更新すべきか
を決定する。次に一時的状態バッファ４７０は、コヒー
レンス制御装置４５０によって指定された、タグ・フィ
ールドでなく状態フィールドを含む、何らかのフィール
ドの書き込みを行う。
【００３１】図５は、一時的状態バッファ４７０を使用
するローカル読み出し操作５００のフローチャートであ
る。このアルゴリズムは、ステップ５０２でプロセッサ
４１２が、ローカル・ノード４１０中のロケーションを
参照するアドレスによるロード命令を実行することで開
始される。ステップ５０４では、プロセッサ４１２がま
ずこの要求をキャッシュ４２２に伝え、ステップ５０６
で、ラインの有効なコピーを有するか否かが検査され
る。有効なコピーを有する場合、ステップ５０８でキャ
ッシュ４２２はラインを提供し、ロード命令を終了す
る。有効なコピーを有さない場合、ステップ５１０でキ
ャッシュ４２２は要求をメモリ・サブシステム４４０に
伝える。ステップ５１２では、メモリ・サブシステム４
４０のコヒーレンス制御装置４５０はまずアドレスを、
外部ディレクトリ４６０と一時的状態バッファ４７０の
両方のエントリと比較し、何らかの状態情報がこれらの
ディレクトリ中のアドレスと一致するかを調べる。一致
しない場合、データ・ラインの最新の値は主メモリにあ
るはずなので、ステップ５１４でメモリ・サブシステム
４４０はデータ・ラインを主メモリ４９０からフェッチ
し、ロード命令は終了する。ステップ５１２でアルゴリ
ズムが一致するアドレスが一時的状態バッファ４７０に
保存されていることを発見した場合、ステップ５１６で
コヒーレンス制御装置４５０はこのラインについて要求
がすでに出されていると判断する。これをどう処理する
かはコヒーレンス・プロトコルに依存するが、この状況
を処理する１つの方法がステップ５１８に示されてお
り、そこではアルゴリズムは単にプロセッサ４１２に要
求を再試行するよう命令する。
するローカル読み出し操作５００のフローチャートであ
る。このアルゴリズムは、ステップ５０２でプロセッサ
４１２が、ローカル・ノード４１０中のロケーションを
参照するアドレスによるロード命令を実行することで開
始される。ステップ５０４では、プロセッサ４１２がま
ずこの要求をキャッシュ４２２に伝え、ステップ５０６
で、ラインの有効なコピーを有するか否かが検査され
る。有効なコピーを有する場合、ステップ５０８でキャ
ッシュ４２２はラインを提供し、ロード命令を終了す
る。有効なコピーを有さない場合、ステップ５１０でキ
ャッシュ４２２は要求をメモリ・サブシステム４４０に
伝える。ステップ５１２では、メモリ・サブシステム４
４０のコヒーレンス制御装置４５０はまずアドレスを、
外部ディレクトリ４６０と一時的状態バッファ４７０の
両方のエントリと比較し、何らかの状態情報がこれらの
ディレクトリ中のアドレスと一致するかを調べる。一致
しない場合、データ・ラインの最新の値は主メモリにあ
るはずなので、ステップ５１４でメモリ・サブシステム
４４０はデータ・ラインを主メモリ４９０からフェッチ
し、ロード命令は終了する。ステップ５１２でアルゴリ
ズムが一致するアドレスが一時的状態バッファ４７０に
保存されていることを発見した場合、ステップ５１６で
コヒーレンス制御装置４５０はこのラインについて要求
がすでに出されていると判断する。これをどう処理する
かはコヒーレンス・プロトコルに依存するが、この状況
を処理する１つの方法がステップ５１８に示されてお
り、そこではアルゴリズムは単にプロセッサ４１２に要
求を再試行するよう命令する。
【００３２】ステップ５１２で一致するアドレスが外部
ディレクトリ４６０にあるとアルゴリズムが判断し、最
新の値がどこか他のノードに存在することを示す場合、
ステップ５２０でコヒーレンス制御装置４５０はメッセ
ージをそのノードに送信し、一時的状態バッファ４７０
中のこのラインのエントリを割り当て、バッファ４７０
中に以前存在したラインを遷移状態にする。ステップ５
２２で、コヒーレンス制御装置４５０は、コヒーレンス
制御装置４５０がデータを待っていることを要求を出し
たプロセッサ４１２に知らせることによって、現在のト
ランザクションを完了する。その後コヒーレンス制御装
置４５０は自由に新しい要求を処理することができる。
ディレクトリ４６０にあるとアルゴリズムが判断し、最
新の値がどこか他のノードに存在することを示す場合、
ステップ５２０でコヒーレンス制御装置４５０はメッセ
ージをそのノードに送信し、一時的状態バッファ４７０
中のこのラインのエントリを割り当て、バッファ４７０
中に以前存在したラインを遷移状態にする。ステップ５
２２で、コヒーレンス制御装置４５０は、コヒーレンス
制御装置４５０がデータを待っていることを要求を出し
たプロセッサ４１２に知らせることによって、現在のト
ランザクションを完了する。その後コヒーレンス制御装
置４５０は自由に新しい要求を処理することができる。
【００３３】後に、ステップ５２４で、要求されたデー
タがリモート・ノードから到着し、ステップ５２６でコ
ヒーレンス制御装置４５０は一時的状態バッファ４７０
のラインを参照し、遷移状態を検索する。この遷移状態
は、コヒーレンス制御装置４５０に、データをどこに転
送すべきか、また最終的な永続状態は何であるべきかを
告げる。ステップ５２８で、コヒーレンス制御装置４５
０は、新しいトランザクションを開始して、データを要
求を出したプロセッサ４１２に送信し、一時的状態バッ
ファ・エントリを割り当て解除し、外部ディレクトリ４
６０を最終永続状態に更新し、ロード命令を終了する。
タがリモート・ノードから到着し、ステップ５２６でコ
ヒーレンス制御装置４５０は一時的状態バッファ４７０
のラインを参照し、遷移状態を検索する。この遷移状態
は、コヒーレンス制御装置４５０に、データをどこに転
送すべきか、また最終的な永続状態は何であるべきかを
告げる。ステップ５２８で、コヒーレンス制御装置４５
０は、新しいトランザクションを開始して、データを要
求を出したプロセッサ４１２に送信し、一時的状態バッ
ファ・エントリを割り当て解除し、外部ディレクトリ４
６０を最終永続状態に更新し、ロード命令を終了する。
【００３４】
【発明の効果】以上述べたように、本発明によれば、キ
ャッシュ・コヒーレンス状態を保持するために必要な外
部記憶装置の量を減少させる。ラインが遷移状態にある
時間の量は非常に短く、ある時間に遷移状態にあるライ
ンはごく少数なので、本発明は一時的状態バッファのサ
イズも減少させる。さらに、本発明は、多数の遷移状態
を通じて、遷移のための外部ディレクトリへのアクセス
を除去し、コヒーレンス・プロトコルの総合的な処理能
力を増大する。
ャッシュ・コヒーレンス状態を保持するために必要な外
部記憶装置の量を減少させる。ラインが遷移状態にある
時間の量は非常に短く、ある時間に遷移状態にあるライ
ンはごく少数なので、本発明は一時的状態バッファのサ
イズも減少させる。さらに、本発明は、多数の遷移状態
を通じて、遷移のための外部ディレクトリへのアクセス
を除去し、コヒーレンス・プロトコルの総合的な処理能
力を増大する。
【００３５】ここで説明した実施形態の例は例示を目的
とし、制限することを企図するものではない。従って、
当業技術分野に熟練した者は、他の実施形態が請求項の
範囲と精神から離れることなく実行されることが認識さ
れるだろう。
とし、制限することを企図するものではない。従って、
当業技術分野に熟練した者は、他の実施形態が請求項の
範囲と精神から離れることなく実行されることが認識さ
れるだろう。
【図１】先行技術のキャッシュ・メモリ・アクセス・ア
ルゴリズムのフローチャートである。
ルゴリズムのフローチャートである。
【図２】キャッシュ・コヒーレンス・ディレクトリを使
用する従来技術のキャッシュ・メモリ・アクセス・アル
ゴリズムのフローチャートである。
用する従来技術のキャッシュ・メモリ・アクセス・アル
ゴリズムのフローチャートである。
【図３】バスによって主メモリに接続された固有のロー
カル・キャッシュを各々有する多数のＣＰＵを含む従来
技術のシステムの構成図である。
カル・キャッシュを各々有する多数のＣＰＵを含む従来
技術のシステムの構成図である。
【図４】各々多数のプロセッサとキャッシュを含む多数
の相互接続されたノード、コヒーレンス制御装置、外部
ディレクトリ及び一時的状態バッファを有するｃｃＮＵ
ＭＡシステムの構成図である。
の相互接続されたノード、コヒーレンス制御装置、外部
ディレクトリ及び一時的状態バッファを有するｃｃＮＵ
ＭＡシステムの構成図である。
【図５】図４のｃｃＮＵＭＡシステムの一時的状態バッ
ファを使用するローカル読み出し操作のフローチャート
である。
ファを使用するローカル読み出し操作のフローチャート
である。
３０２、３０４、３０６、３０８…ＣＰＵ ３１０、３１２、３１４、３１６…キャッシュ ３２０…メモリ制御装置 ３２２…メモリ ３２４…ディレクトリ ４０２、４０８、４１０…ノード ４１２、４１４、４２０…プロセッサ ４２２、４２４、４３０…キャッシュ ４４０…メモリ・サブシステム ４５０…コヒーレンス制御装置 ４６０…外部ディレクトリ ４７０…一時的状態バッファ ４８０…コヒーレンス制御チップ ４９０…主メモリ
Claims (20)
- 【請求項１】 データ処理システムであって、 各々複数のキャッシュ・ライン・エントリを保存する複
数のキャッシュと、 各々それぞれのキャッシュに接続された複数のプロセッ
サと、 コヒーレンス制御装置と、 前記複数のキャッシュ中のキャッシュ・ラインの状態を
把握するディレクトリであって、前記ディレクトリの第
１部分が前記複数のキャッシュのラインの第１サブセッ
トに関する一時的状態情報を保持し、前記ディレクトリ
の第２部分が前記複数のキャッシュのラインの第２サブ
セットに関する非一時的状態を保持するディレクトリと
を各々含む、 複数のマルチプロセッサ・ノードを備えるデータ処理シ
ステム。 - 【請求項２】 前記ディレクトリの前記第２部分が少な
くとも１つの外部ディレクトリを備える、請求項１に記
載のデータ処理システム。 - 【請求項３】 前記ディレクトリの前記第１及び第２部
分が物理的に独立している、請求項１に記載のデータ処
理システム。 - 【請求項４】 前記複数のマルチプロセッサ・ノードの
少なくとも１つの中のキャッシュ・コヒーレンス・プロ
トコルがスヌーピー・コヒーレンス・プロトコルを使用
し、前記複数のマルチプロセッサ・ノードの全体にわた
るキャッシュ・コヒーレンス・プロトコルがディレクト
リ・ベース・キャッシュ・コヒーレンス・プロトコルを
使用する、請求項１に記載のデータ処理システム。 - 【請求項５】 前記ディレクトリの前記第１部分が内部
オンチップ・ディレクトリであり、前記ディレクトリの
前記第２部分が外部オフチップ・ディレクトリである、
請求項３に記載のデータ処理システム。 - 【請求項６】 データ処理システムであって、 メモリ・バスに結合された複数のプロセッサを各々有す
る多数のノードであって、各プロセッサが複数のキャッ
シュ・ラインを保存する関連キャッシュを有する多数の
ノードと、 前記メモリ・バスに結合するバス・インタフェース素子
と、 前記キャッシュ中のキャッシュ・ラインの状態を把握す
るディレクトリと、 前記ディレクトリから状態情報を読み出し前記状態情報
を更新する、前記バス・インタフェース素子と前記ディ
レクトリに結合されたコヒーレンス制御装置とを備える
データ処理システム。 - 【請求項７】 前記ディレクトリの前記第２部分が少な
くとも１つの外部ディレクトリを備える、請求項６に記
載のデータ処理システム。 - 【請求項８】 前記ディレクトリの前記第１及び第２部
分が物理的に独立している、請求項６に記載のデータ処
理システム。 - 【請求項９】 前記多数のノードの少なくとも１つの中
のキャッシュ・コヒーレンス・プロトコルがスヌーピー
・コヒーレンス・プロトコルを使用し、前記多数のノー
ドの全体にわたるキャッシュ・コヒーレンス・プロトコ
ルがディレクトリ・ベース・キャッシュ・コヒーレンス
・プロトコルを使用する、請求項６に記載のデータ処理
システム。 - 【請求項１０】 前記ディレクトリの前記第１部分が内
部オンチップ・ディレクトリであり、前記ディレクトリ
の前記第２部分が外部オフチップ・ディレクトリであ
る、請求項８に記載のデータ処理システム。 - 【請求項１１】 メモリ・バスに結合された複数のプロ
セッサを各々有する多数のノードを含も、各プロセッサ
が関連キャッシュ・メモリを有する、データ処理システ
ムにおけるキャッシュ・コヒーレンスを維持する方法で
あって、 キャッシュされたメモリ・ロケーションに関する情報を
ディレクトリに保存するステップであって、前記ディレ
クトリの第１部分が第１の複数のキャッシュ・ラインに
関する遷移状態情報を保持し、前記ディレクトリの第２
部分が第２の複数のキャッシュ・ラインに関する非遷移
状態情報を保持するステップと、 キャッシュ・コヒーレンスを維持するために前記キャッ
シュ・メモリにコヒーレンス制御装置を結合するステッ
プとを含む方法。 - 【請求項１２】 前記結合ステップが、 前記ディレクトリから状態情報を読み出すステップと、 前記ディレクトリ中の前記状態情報を更新するステップ
とを含む、請求項１１に記載の方法。 - 【請求項１３】 さらに、 少なくとも１つの前記多数のノードの中でスヌーピー・
コヒーレンス・プロトコルを使用するステップと、 前記多数のノードの全体にわたってディレクトリ・ベー
ス・キャッシュ・コヒーレンス・プロトコルを使用する
ステップとを含む、請求項１１に記載の方法。 - 【請求項１４】 複数のノードと相互接続を含むデータ
処理システムにおけるキャッシュ・コヒーレンスを維持
する方法であって、各ノードが、 関連するキャッシュ及びメモリを伴う複数のマルチプロ
セッサと、 複数のキャッシュされたメモリ・ラインに関する状態情
報を保存するディレクトリであって、前記ディレクトリ
の第１部分が前記複数のキャッシュされたメモリ・ライ
ンに関する遷移状態情報を保持し、前記ディレクトリの
第２部分が前記複数のキャッシュされたメモリ・ライン
に関する非遷移状態情報を保持するディレクトリとを有
し、 メモリ・バスから前記キャッシュされたメモリ・ライン
の制御に関するバス要求を受信するステップと、 前記キャッシュされたメモリ・ラインの前記状態情報を
読み出すステップと、 前記キャッシュされたメモリ・ラインに関する前記状態
情報を更新するステップとを含む方法。 - 【請求項１５】 さらに、 前記複数のノードの少なくとも１つの中でスヌーピー・
コヒーレンス・プロトコルを使用するステップと、 前記複数のノードの全体にわたってディレクトリ・ベー
ス・キャッシュ・コヒーレンス・プロトコルを使用する
ステップとを含む、請求項１４に記載の方法。 - 【請求項１６】 複数のノードと相互接続を含むデータ
処理システムであって、各ノードが関連するキャッシュ
及びメモリを伴う複数のマルチプロセッサと、複数のキ
ャッシュされたメモリ・ラインに関する状態情報を保存
するディレクトリを有し、前記ディレクトリの１つの部
分が前記複数のキャッシュされたメモリ・ラインの第１
サブセットに関する遷移状態情報を保持し、前記ディレ
クトリの第２の部分が前記複数のキャッシュされたメモ
リ・ラインの第２サブセットに関する非遷移状態情報を
保持し、さらに前記データ処理システムは、 メモリ・バスに結合され、メモリ・バス要求を受信する
制御ユニットと、 前記キャッシュされたメモリ・ラインの前記状態情報を
読み出す手段と、 前記キャッシュされたメモリ・ラインに関する前記状態
情報を更新する手段とを備えるデータ処理システム。 - 【請求項１７】 前記ディレクトリの前記第２部分が少
なくとも１つの外部ディレクトリを備える、請求項１６
に記載のデータ処理システム。 - 【請求項１８】 前記ディレクトリの前記第１及び第２
部分が物理的に独立している、請求項１６に記載のデー
タ処理システム。 - 【請求項１９】 前記ディレクトリの前記第１部分が内
部オンチップ・ディレクトリであり、前記ディレクトリ
の前記第２部分が外部オフチップ・ディレクトリであ
る、請求項１６に記載のデータ処理システム。 - 【請求項２０】 前記複数のノードの少なくとも１つの
中のキャッシュ・コヒーレンス・プロトコルがスヌーピ
ー・コヒーレンス・プロトコルを使用し、前記複数のノ
ードの全体にわたるキャッシュ・コヒーレンス・プロト
コルがディレクトリ・ベース・キャッシュ・コヒーレン
ス・プロトコルを使用する、請求項１６に記載のデータ
処理システム。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US8479598P | 1998-05-08 | 1998-05-08 | |
| US09/281,714 US6560681B1 (en) | 1998-05-08 | 1999-03-30 | Split sparse directory for a distributed shared memory multiprocessor system |
| US09/281714 | 1999-03-30 | ||
| US60/084795 | 1999-03-30 |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006159012A Division JP4447580B2 (ja) | 1998-05-08 | 2006-06-07 | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2000067024A true JP2000067024A (ja) | 2000-03-03 |
Family
ID=26771438
Family Applications (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11127277A Pending JP2000067024A (ja) | 1998-05-08 | 1999-05-07 | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ |
| JP2006159012A Expired - Lifetime JP4447580B2 (ja) | 1998-05-08 | 2006-06-07 | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ |
Family Applications After (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006159012A Expired - Lifetime JP4447580B2 (ja) | 1998-05-08 | 2006-06-07 | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6560681B1 (ja) |
| JP (2) | JP2000067024A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2010052799A1 (ja) * | 2008-11-10 | 2010-05-14 | 富士通株式会社 | 情報処理装置及びメモリ制御装置 |
| US7904665B2 (en) | 2006-01-26 | 2011-03-08 | Nec Computer Techno, Ltd. | Multiprocessor system and its operational method |
| WO2012035605A1 (ja) * | 2010-09-13 | 2012-03-22 | 富士通株式会社 | 情報処理装置および情報処理装置の制御方法 |
| WO2012039008A1 (ja) * | 2010-09-23 | 2012-03-29 | 富士通株式会社 | 情報処理装置、メモリ制御方法及びメモリ制御装置 |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6725334B2 (en) * | 2000-06-09 | 2004-04-20 | Hewlett-Packard Development Company, L.P. | Method and system for exclusive two-level caching in a chip-multiprocessor |
| US6775742B2 (en) * | 2000-07-20 | 2004-08-10 | Silicon Graphics, Inc. | Memory device storing data and directory information thereon, and method for providing the directory information and the data in the memory device |
| FR2820850B1 (fr) * | 2001-02-15 | 2003-05-09 | Bull Sa | Controleur de coherence pour ensemble multiprocesseur, module et ensemble multiprocesseur a architecture multimodule integrant un tel controleur |
| US6832297B2 (en) * | 2001-08-09 | 2004-12-14 | International Business Machines Corporation | Method and apparatus for managing data in a distributed buffer system |
| US20030041215A1 (en) * | 2001-08-27 | 2003-02-27 | George Robert T. | Method and apparatus for the utilization of distributed caches |
| US7546422B2 (en) * | 2002-08-28 | 2009-06-09 | Intel Corporation | Method and apparatus for the synchronization of distributed caches |
| US6965972B2 (en) * | 2002-09-25 | 2005-11-15 | International Business Machines Corporation | Real time emulation of coherence directories using global sparse directories |
| US8185602B2 (en) | 2002-11-05 | 2012-05-22 | Newisys, Inc. | Transaction processing using multiple protocol engines in systems having multiple multi-processor clusters |
| US7337273B2 (en) * | 2004-03-31 | 2008-02-26 | Microsoft Corporation | Strategies for reading information from a mass storage medium using a cache memory |
| WO2006029508A1 (en) * | 2004-09-13 | 2006-03-23 | Solace Systems Inc. | Highly scalable subscription matching for a content routing network |
| US7475193B2 (en) * | 2006-01-18 | 2009-01-06 | International Business Machines Corporation | Separate data and coherency cache directories in a shared cache in a multiprocessor system |
| US20070168620A1 (en) * | 2006-01-19 | 2007-07-19 | Sicortex, Inc. | System and method of multi-core cache coherency |
| US8566533B1 (en) * | 2009-09-30 | 2013-10-22 | Netlogic Microsystems, Inc. | System, method, and computer program product for conditionally sending a request for data to a node based on a determination |
| US8856453B2 (en) | 2012-03-01 | 2014-10-07 | International Business Machines Corporation | Persistent prefetch data stream settings |
| US20140293393A1 (en) | 2013-03-28 | 2014-10-02 | Barthelemy Fondeur | Flat-top tunable filter |
| KR20180078253A (ko) | 2015-11-04 | 2018-07-09 | 삼성전자주식회사 | 다중 프로세서 시스템에서 코히어런트 메모리를 구현하기 위한 시스템 및 방법 |
| JP6578992B2 (ja) * | 2016-03-02 | 2019-09-25 | 富士通株式会社 | 制御回路、情報処理装置、および情報処理装置の制御方法 |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3872118B2 (ja) * | 1995-03-20 | 2007-01-24 | 富士通株式会社 | キャッシュコヒーレンス装置 |
| US5680576A (en) * | 1995-05-05 | 1997-10-21 | Silicon Graphics, Inc. | Directory-based coherence protocol allowing efficient dropping of clean-exclusive data |
| US5822763A (en) * | 1996-04-19 | 1998-10-13 | Ibm Corporation | Cache coherence protocol for reducing the effects of false sharing in non-bus-based shared-memory multiprocessors |
| US5749095A (en) * | 1996-07-01 | 1998-05-05 | Sun Microsystems, Inc. | Multiprocessing system configured to perform efficient write operations |
| US5875468A (en) * | 1996-09-04 | 1999-02-23 | Silicon Graphics, Inc. | Method to pipeline write misses in shared cache multiprocessor systems |
| US6253292B1 (en) * | 1997-08-22 | 2001-06-26 | Seong Tae Jhang | Distributed shared memory multiprocessor system based on a unidirectional ring bus using a snooping scheme |
| US6631448B2 (en) * | 1998-03-12 | 2003-10-07 | Fujitsu Limited | Cache coherence unit for interconnecting multiprocessor nodes having pipelined snoopy protocol |
-
1999
- 1999-03-30 US US09/281,714 patent/US6560681B1/en not_active Expired - Lifetime
- 1999-05-07 JP JP11127277A patent/JP2000067024A/ja active Pending
-
2006
- 2006-06-07 JP JP2006159012A patent/JP4447580B2/ja not_active Expired - Lifetime
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7904665B2 (en) | 2006-01-26 | 2011-03-08 | Nec Computer Techno, Ltd. | Multiprocessor system and its operational method |
| WO2010052799A1 (ja) * | 2008-11-10 | 2010-05-14 | 富士通株式会社 | 情報処理装置及びメモリ制御装置 |
| JP5136652B2 (ja) * | 2008-11-10 | 2013-02-06 | 富士通株式会社 | 情報処理装置及びメモリ制御装置 |
| US8725954B2 (en) | 2008-11-10 | 2014-05-13 | Fujitsu Limited | Information processing apparatus and memory control apparatus |
| WO2012035605A1 (ja) * | 2010-09-13 | 2012-03-22 | 富士通株式会社 | 情報処理装置および情報処理装置の制御方法 |
| WO2012039008A1 (ja) * | 2010-09-23 | 2012-03-29 | 富士通株式会社 | 情報処理装置、メモリ制御方法及びメモリ制御装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US6560681B1 (en) | 2003-05-06 |
| JP2006277762A (ja) | 2006-10-12 |
| JP4447580B2 (ja) | 2010-04-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4447580B2 (ja) | 分散共有メモリマルチプロセッサシステムのための分割疎ディレクトリ | |
| US6901495B2 (en) | Cache memory system allowing concurrent reads and writes to cache lines to increase snoop bandwith | |
| US7032074B2 (en) | Method and mechanism to use a cache to translate from a virtual bus to a physical bus | |
| JP5431525B2 (ja) | アクセラレータ用低コストのキャッシュ一貫性を維持するシステム | |
| US6647466B2 (en) | Method and apparatus for adaptively bypassing one or more levels of a cache hierarchy | |
| JP3924206B2 (ja) | 不均一メモリ・アクセス（ｎｕｍａ）データ処理システム | |
| US6826651B2 (en) | State-based allocation and replacement for improved hit ratio in directory caches | |
| US6272602B1 (en) | Multiprocessing system employing pending tags to maintain cache coherence | |
| US20030005237A1 (en) | Symmetric multiprocessor coherence mechanism | |
| US6405290B1 (en) | Multiprocessor system bus protocol for O state memory-consistent data | |
| JPH11506852A (ja) | 多数のバスマスタと共用レベル２キャッシュとを備える多レベルキャッシュシステムでのキャッシュスヌーピングオーバーヘッドの低減 | |
| JPH09185549A (ja) | キャッシュ記憶モードの間で選択するためのハイブリッドｎｕｍａ ｃｏｍａキャッシュ記憶のシステムおよび方法 | |
| US6345341B1 (en) | Method of cache management for dynamically disabling O state memory-consistent data | |
| US20060184743A1 (en) | Cache memory direct intervention | |
| JP2000010860A (ja) | キャッシュメモリ制御回路及びプロセッサ及びプロセッサシステム及び並列プロセッサシステム | |
| US7117312B1 (en) | Mechanism and method employing a plurality of hash functions for cache snoop filtering | |
| US7325102B1 (en) | Mechanism and method for cache snoop filtering | |
| US7024520B2 (en) | System and method enabling efficient cache line reuse in a computer system | |
| US20050080998A1 (en) | Method and apparatus for coherent memory structure of heterogeneous processor systems | |
| US6397303B1 (en) | Data processing system, cache, and method of cache management including an O state for memory-consistent cache lines | |
| US6356982B1 (en) | Dynamic mechanism to upgrade o state memory-consistent cache lines | |
| US20020002659A1 (en) | System and method for improving directory lookup speed | |
| US6349368B1 (en) | High performance mechanism to support O state horizontal cache-to-cache transfers | |
| US6826654B2 (en) | Cache invalidation bus for a highly scalable shared cache memory hierarchy | |
| US20040030950A1 (en) | Apparatus for imprecisely tracking cache line inclusivity of a higher level cache |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040324 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050818 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050906 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20051107 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20060404 |