JP3399501B2 - 分割フェーズ制御を用いる明示的コヒーレンス - Google Patents
分割フェーズ制御を用いる明示的コヒーレンスInfo
- Publication number
- JP3399501B2 JP3399501B2 JP24365297A JP24365297A JP3399501B2 JP 3399501 B2 JP3399501 B2 JP 3399501B2 JP 24365297 A JP24365297 A JP 24365297A JP 24365297 A JP24365297 A JP 24365297A JP 3399501 B2 JP3399501 B2 JP 3399501B2
- Authority
- JP
- Japan
- Prior art keywords
- command
- coherence
- range
- completion
- lock
- 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.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
-
- 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/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
-
- 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/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/0837—Cache consistency protocols with software control, e.g. non-cacheable data
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/10—Providing a specific technical effect
- G06F2212/1016—Performance improvement
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/10—Providing a specific technical effect
- G06F2212/1041—Resource optimization
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/10—Providing a specific technical effect
- G06F2212/1056—Simplification
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
- Multi Processors (AREA)
Description
【０００１】
【発明の属する技術分野】本発明は、共用記憶多重プロ
セッサ・システムにおけるキャッシュ・コヒーレンスの
改善に関するものである。特に、本発明によれば、コヒ
ーレンスは、ロック獲得とロック解放との間のみで保た
れる。
セッサ・システムにおけるキャッシュ・コヒーレンスの
改善に関するものである。特に、本発明によれば、コヒ
ーレンスは、ロック獲得とロック解放との間のみで保た
れる。
【０００２】
【従来の技術】専用データ・キャッシュを持つ複数の処
理ノードから構成される多重処理システムはキャッシュ
内にあるデータの専用コピーが古くなるという、キャッ
シュ・コヒーレンスの問題がある。それに対する従来の
解決策では、ハードウエア・サポートがデータ書込みの
ときには常に自動的にすべてのキャッシュを無効化また
は更新することによって、またデータ読出しのときは常
に、データの最新のコピーを検索することによって、キ
ャッシュのコヒーレンスを保つ。
理ノードから構成される多重処理システムはキャッシュ
内にあるデータの専用コピーが古くなるという、キャッ
シュ・コヒーレンスの問題がある。それに対する従来の
解決策では、ハードウエア・サポートがデータ書込みの
ときには常に自動的にすべてのキャッシュを無効化また
は更新することによって、またデータ読出しのときは常
に、データの最新のコピーを検索することによって、キ
ャッシュのコヒーレンスを保つ。
【０００３】
【発明が解決しようとする課題】そのような従来の解決
策が抱える主な問題点は、各データの読出しまたは書込
みの際に自動的にキャッシュ・コヒーレンスを維持する
のに必要なハードウエアの複雑性である。従来の解決策
では、すべてのキャッシュに対して読出しおよび書込み
を同報通信するか、あるいはデータのコピーを持つすべ
てのキャッシュのディレクトリを維持している。読出し
および書込みを同報通信することは、高速メモリ・バス
を必要とするとともに、多重処理システムの大きさを限
定する。ディレクトリを維持しようとするとハードウエ
アが過剰となり、さらにシステムの大きさが増大すると
システムの経費に占めるディレクトリに必要なメモリの
割合が急激に増大してかなりの部分になる。従来の解決
策のすべてにおいて、キャッシュおよびメモリからなる
サブシステムを実質的に改良する必要があり、既製の部
品に頼ることはできない。
策が抱える主な問題点は、各データの読出しまたは書込
みの際に自動的にキャッシュ・コヒーレンスを維持する
のに必要なハードウエアの複雑性である。従来の解決策
では、すべてのキャッシュに対して読出しおよび書込み
を同報通信するか、あるいはデータのコピーを持つすべ
てのキャッシュのディレクトリを維持している。読出し
および書込みを同報通信することは、高速メモリ・バス
を必要とするとともに、多重処理システムの大きさを限
定する。ディレクトリを維持しようとするとハードウエ
アが過剰となり、さらにシステムの大きさが増大すると
システムの経費に占めるディレクトリに必要なメモリの
割合が急激に増大してかなりの部分になる。従来の解決
策のすべてにおいて、キャッシュおよびメモリからなる
サブシステムを実質的に改良する必要があり、既製の部
品に頼ることはできない。
【０００４】したがって、本発明の目的は、パフォーマ
ンスおよびハードウェアの複雑性という両方の点で単純
ではあるがキャッシュ・コヒーレンスの問題に対して有
効な解決策を提供することにある。
ンスおよびハードウェアの複雑性という両方の点で単純
ではあるがキャッシュ・コヒーレンスの問題に対して有
効な解決策を提供することにある。
【０００５】
【課題を解決するための手段】本発明は、キャッシュ・
コヒーレンスに対する新たな問題の取り組み方法を採用
するもので、従来の取り組み方と比較して、必要とされ
るハードウエア・サポートは最小限度のものである。ま
た、本発明は同報通信またはディレクトリに頼るもので
はない。キャッシュおよびメモリ・サブシステムを既製
部品から構築することができ、コヒーレンスを維持する
作業に積極的に関与する必要はない。本発明は、従来の
解決策に見られた複雑性の大部分を回避し、キャッシュ
・コヒーレンスを単純、かつ効率的に実現するものであ
る。すなわち、キャッシュおよびメモリ・システムが読
出しおよび書込みを同報通信したり、キャッシュの状況
を示すディクレクトリを維持したりする必要はない。ま
た、それは高度にパラレルであり、スケーラブルであ
る。
コヒーレンスに対する新たな問題の取り組み方法を採用
するもので、従来の取り組み方と比較して、必要とされ
るハードウエア・サポートは最小限度のものである。ま
た、本発明は同報通信またはディレクトリに頼るもので
はない。キャッシュおよびメモリ・サブシステムを既製
部品から構築することができ、コヒーレンスを維持する
作業に積極的に関与する必要はない。本発明は、従来の
解決策に見られた複雑性の大部分を回避し、キャッシュ
・コヒーレンスを単純、かつ効率的に実現するものであ
る。すなわち、キャッシュおよびメモリ・システムが読
出しおよび書込みを同報通信したり、キャッシュの状況
を示すディクレクトリを維持したりする必要はない。ま
た、それは高度にパラレルであり、スケーラブルであ
る。
【０００６】メモリの読出しまたは書込みの度にメモリ
全体のキャッシュ・コヒーレンスを自動的に保持する代
わりに、本発明ではメモリ・アドレスの所定の範囲のみ
に対応したキャッシュ・コヒーレンスを、その範囲に関
連したロックの獲得と解放との間の期間内のみで保持す
る。これは並列プログラムがロックを用いて共有データ
へのアクセスを同期させる性質に頼るものである。プロ
グラムが共有データの読出しを行う場合、最初に読出し
モードのロックを獲得する。プログラムが共有データの
読出しを終えると、読出しモードのロックを解放する。
プログラムが共有データの書込みを行う場合、最初に書
込みモードのロックを獲得する。プログラムが共有デー
タの書込みを終えると、書込みモードのロックを解放す
る。この並列プログラムの特性によって、本発明は書込
みおよび読出しがなされる共有データが常にコヒーレン
トであることを保証する。
全体のキャッシュ・コヒーレンスを自動的に保持する代
わりに、本発明ではメモリ・アドレスの所定の範囲のみ
に対応したキャッシュ・コヒーレンスを、その範囲に関
連したロックの獲得と解放との間の期間内のみで保持す
る。これは並列プログラムがロックを用いて共有データ
へのアクセスを同期させる性質に頼るものである。プロ
グラムが共有データの読出しを行う場合、最初に読出し
モードのロックを獲得する。プログラムが共有データの
読出しを終えると、読出しモードのロックを解放する。
プログラムが共有データの書込みを行う場合、最初に書
込みモードのロックを獲得する。プログラムが共有デー
タの書込みを終えると、書込みモードのロックを解放す
る。この並列プログラムの特性によって、本発明は書込
みおよび読出しがなされる共有データが常にコヒーレン
トであることを保証する。
【０００７】したがって、本発明はロックの獲得および
解放におけるアドレス範囲のコヒーレンスを維持するコ
ヒーレンス・オブジェクト・コントローラ（ＣＯＣ）を
有する。アドレスの範囲は、プロセス仮想アドレス空間
のなかの任意の連続したメモリ・ロケーションである。
このＣＯＣは、グローバル・ロック・マネージャ（ＧＬ
Ｍ）、最近獲得ロック・マネージャ（ＲＡＬＭ）、およ
び完了ビット・ベクトル（ＣＢＶ）から構成される。
解放におけるアドレス範囲のコヒーレンスを維持するコ
ヒーレンス・オブジェクト・コントローラ（ＣＯＣ）を
有する。アドレスの範囲は、プロセス仮想アドレス空間
のなかの任意の連続したメモリ・ロケーションである。
このＣＯＣは、グローバル・ロック・マネージャ（ＧＬ
Ｍ）、最近獲得ロック・マネージャ（ＲＡＬＭ）、およ
び完了ビット・ベクトル（ＣＢＶ）から構成される。
【０００８】ＧＬＭは、全プロセッサに対して現在有効
である全てのロックを追跡するグローバル・ロック・テ
ーブル（ＧＬＴ）を含む。ロック／アンロック動作に対
する要求はＧＬＭに向けられる。ディレクトリを必要と
する従来の解決策とは異なり、ＧＬＴのエントリにはロ
ックを保持するプロセッサのディレクトリは含まれな
い。その代わり、出されたロックの数を示す単純な参照
回数を含む。
である全てのロックを追跡するグローバル・ロック・テ
ーブル（ＧＬＴ）を含む。ロック／アンロック動作に対
する要求はＧＬＭに向けられる。ディレクトリを必要と
する従来の解決策とは異なり、ＧＬＴのエントリにはロ
ックを保持するプロセッサのディレクトリは含まれな
い。その代わり、出されたロックの数を示す単純な参照
回数を含む。
【０００９】ＧＭＬとの通信の必要性を最小限にするた
めに、各処理ノードのＣＯＣはＲＡＬＭを含む。また、
このＲＡＬＭは同一処理ノード内でプロセッサによって
獲得されたロックを追跡する最近獲得ロック・テーブル
（ＲＡＬＴ）が含まれる。
めに、各処理ノードのＣＯＣはＲＡＬＭを含む。また、
このＲＡＬＭは同一処理ノード内でプロセッサによって
獲得されたロックを追跡する最近獲得ロック・テーブル
（ＲＡＬＴ）が含まれる。
【００１０】通信同期待ち時間の影響を最小限にするた
めに、ロック獲得および解放動作は分割フェーズからな
る。すなわち、ロック動作の実行要求およびそれに続く
完了は２つの異なる動作に分割される。プロセッサはロ
ック動作の実行を要求し、その後完了ビット・ベクトル
を調べることによって、ロック動作の完了を検知するこ
とができる。
めに、ロック獲得および解放動作は分割フェーズからな
る。すなわち、ロック動作の実行要求およびそれに続く
完了は２つの異なる動作に分割される。プロセッサはロ
ック動作の実行を要求し、その後完了ビット・ベクトル
を調べることによって、ロック動作の完了を検知するこ
とができる。
【００１１】キャッシュ・コヒーレンスを維持するこの
方法は、"明示的コヒーレンス"と呼ばれる。なぜなら、
プログラムは読出しまたは書込みがなされるメモリ・ア
ドレス範囲を明示的にロックおよびアンロックするから
である。。共有データが書込まれるときは常にキャッシ
ュが他のキャッシュを強制的に無効にしたり、あるいは
更新する従来のキャッシュ・システムにあるような自動
的コヒーレンスは存在しない。明示的コヒーレンスで
は、プロセッサは、書込みを行う前に、他の全てのプロ
セッサが明示的解放コマンドを出すことによって共有デ
ータ上のロックを自発的に解放するまで待機する。この
ことによって導き出される最も重要な結果は、強制的な
無効化の必要がないことであり、また強制的無効化また
は更新をキャッシュに通知するための同報通信やディレ
クトリの維持も不要ということである。
方法は、"明示的コヒーレンス"と呼ばれる。なぜなら、
プログラムは読出しまたは書込みがなされるメモリ・ア
ドレス範囲を明示的にロックおよびアンロックするから
である。。共有データが書込まれるときは常にキャッシ
ュが他のキャッシュを強制的に無効にしたり、あるいは
更新する従来のキャッシュ・システムにあるような自動
的コヒーレンスは存在しない。明示的コヒーレンスで
は、プロセッサは、書込みを行う前に、他の全てのプロ
セッサが明示的解放コマンドを出すことによって共有デ
ータ上のロックを自発的に解放するまで待機する。この
ことによって導き出される最も重要な結果は、強制的な
無効化の必要がないことであり、また強制的無効化また
は更新をキャッシュに通知するための同報通信やディレ
クトリの維持も不要ということである。
【００１２】従来のアプローチに比べて、必要なハード
ウェア・サポートは最小限である。ハードウェアはメモ
リ範囲をロックし、一方でソフトウエアは共有オブジェ
クトをロックする。ハードウェア内のメモリ範囲に共有
オブジェクトをマッピングすることによって、ハードウ
ェアはプログラミング・モデルに対してよりいっそう大
きなサポートを提供する。プログラミング・モデルにハ
ードウェアを、接続することによって、本発明は現用メ
モリ・サブシステムの複雑性のほとんどが回避されるキ
ャッシュ・コヒーレンスを単純で、かつ有効に実現す
る。すなわち、本発明によれば、コヒーレンスはライン
・ベースよりはむしろ領域ベースで維持されることか
ら、ハードウェアの複雑性が減少する。この後者の特徴
は、キャッシュ内の個々のメモリ・ラインの状況を維持
する必要性を除去する。また、この後者の特徴はコヒー
レンス活動の頻度が減少するため、ハードウェアによる
実施にそれほど拘らなくてもよい。
ウェア・サポートは最小限である。ハードウェアはメモ
リ範囲をロックし、一方でソフトウエアは共有オブジェ
クトをロックする。ハードウェア内のメモリ範囲に共有
オブジェクトをマッピングすることによって、ハードウ
ェアはプログラミング・モデルに対してよりいっそう大
きなサポートを提供する。プログラミング・モデルにハ
ードウェアを、接続することによって、本発明は現用メ
モリ・サブシステムの複雑性のほとんどが回避されるキ
ャッシュ・コヒーレンスを単純で、かつ有効に実現す
る。すなわち、本発明によれば、コヒーレンスはライン
・ベースよりはむしろ領域ベースで維持されることか
ら、ハードウェアの複雑性が減少する。この後者の特徴
は、キャッシュ内の個々のメモリ・ラインの状況を維持
する必要性を除去する。また、この後者の特徴はコヒー
レンス活動の頻度が減少するため、ハードウェアによる
実施にそれほど拘らなくてもよい。
【００１３】したがって、本発明は、多重プロセッサ・
システム内で動作を行うためのコヒーレンス・オブジェ
クト・コントローラに関する。このコントローラは、複
数のプロセッサによるオブジェクトへの同時アクセスに
よって引き起こされるオブジェクトの破壊を防止するよ
うに設計されている。本発明によれば、プロセッサの各
々は、コヒーレンス・オブジェクト・コントローラに対
して明示的コヒーレンス・コマンドの実行を要求するこ
とが可能である。プロセッサからの明示的コヒーレンス
・コマンドをコヒーレンス・オブジェクト・コントロー
ラが受信すると、コヒーレンス・オブジェクト・コント
ローラはそのプロセッサに対して明示的コヒーレンス獲
得コマンドの完了時にアドレスの一範囲を保持させる。
すなわち、ＧＬＭが許可の応答をしたときにコヒーレン
ス・コマンドは完了する。この点については後述する。
もし明示的コヒーレンス獲得コマンドが書込み獲得コマ
ンドであるならば、アドレス範囲は書込みモードで保持
される。もし明示的コヒーレンス獲得コマンドが読出し
専用獲得コマンドであるならば、アドレス範囲は読出し
専用モードで保持される。コヒーレンス・オブジェクト
・コントローラはプロセッサから明示的コヒーレンス解
放コマンドを受け取ると、そのプロセッサに対して明示
的コヒーレンス解放コマンドの完了時にアドレスの一範
囲を放棄させる。
システム内で動作を行うためのコヒーレンス・オブジェ
クト・コントローラに関する。このコントローラは、複
数のプロセッサによるオブジェクトへの同時アクセスに
よって引き起こされるオブジェクトの破壊を防止するよ
うに設計されている。本発明によれば、プロセッサの各
々は、コヒーレンス・オブジェクト・コントローラに対
して明示的コヒーレンス・コマンドの実行を要求するこ
とが可能である。プロセッサからの明示的コヒーレンス
・コマンドをコヒーレンス・オブジェクト・コントロー
ラが受信すると、コヒーレンス・オブジェクト・コント
ローラはそのプロセッサに対して明示的コヒーレンス獲
得コマンドの完了時にアドレスの一範囲を保持させる。
すなわち、ＧＬＭが許可の応答をしたときにコヒーレン
ス・コマンドは完了する。この点については後述する。
もし明示的コヒーレンス獲得コマンドが書込み獲得コマ
ンドであるならば、アドレス範囲は書込みモードで保持
される。もし明示的コヒーレンス獲得コマンドが読出し
専用獲得コマンドであるならば、アドレス範囲は読出し
専用モードで保持される。コヒーレンス・オブジェクト
・コントローラはプロセッサから明示的コヒーレンス解
放コマンドを受け取ると、そのプロセッサに対して明示
的コヒーレンス解放コマンドの完了時にアドレスの一範
囲を放棄させる。
【００１４】
【発明の実施の形態】図１は、本発明を具現化する環境
の構成を説明するためのブロック図である。この環境
は、汎用通信ネットワーク・インタフェース３および通
信ネットワーク７を介して連結された複数のデジタル・
データ処理ノード（ＰＮ）１を備える。以下の記載のな
かで、"ローカル"と呼ばれるものは同じ処理ノード内の
構成要素であり、また"リモート"と呼ばれるものは異な
る処理ノード内の構成要素を意味する。
の構成を説明するためのブロック図である。この環境
は、汎用通信ネットワーク・インタフェース３および通
信ネットワーク７を介して連結された複数のデジタル・
データ処理ノード（ＰＮ）１を備える。以下の記載のな
かで、"ローカル"と呼ばれるものは同じ処理ノード内の
構成要素であり、また"リモート"と呼ばれるものは異な
る処理ノード内の構成要素を意味する。
【００１５】図２は、各処理ノードをさらに詳しく説明
するためのブロック図である。各処理ノード１は、プロ
セッサ２、キャッシュ５およびメモリ６を備える。ま
た、各処理ノード１内にグローバル・ロック・マネージ
ャ（ＧＭＬ）１５、最近獲得ロック・マネージャ（ＲＡ
ＬＭ）２０、および完了ビット・ベクトル（ＣＢＶ）２
５が設けられている。ＲＡＬＭ２０は、プロセッサから
ロック獲得および解放コマンドを受信し、該コマンドを
満足させるためにＧＬＭ（場合によってはリモートのＧ
ＬＭ）１５と通信する。また、ＲＡＬＭ２０はキャッシ
ュ５に対してキャッシュ無効化コマンドを送出する。
するためのブロック図である。各処理ノード１は、プロ
セッサ２、キャッシュ５およびメモリ６を備える。ま
た、各処理ノード１内にグローバル・ロック・マネージ
ャ（ＧＭＬ）１５、最近獲得ロック・マネージャ（ＲＡ
ＬＭ）２０、および完了ビット・ベクトル（ＣＢＶ）２
５が設けられている。ＲＡＬＭ２０は、プロセッサから
ロック獲得および解放コマンドを受信し、該コマンドを
満足させるためにＧＬＭ（場合によってはリモートのＧ
ＬＭ）１５と通信する。また、ＲＡＬＭ２０はキャッシ
ュ５に対してキャッシュ無効化コマンドを送出する。
【００１６】＜プロセッサ・インタフェース＞ここで、
プロセッサが記憶領域のロックを獲得または解放するた
めのプリミイティブとしての役割を果たす上記コマンド
を定義する。
プロセッサが記憶領域のロックを獲得または解放するた
めのプリミイティブとしての役割を果たす上記コマンド
を定義する。
【００１７】（１）獲得（範囲、モード、完了ビット）
範囲は上記したように仮想アドレス範囲である。モード
は、範囲が読出し専用モードまたは書込みモードで獲得
されているかどうかを示すビットである。完了ビット
は、最初は０に設定され、首尾良く獲得が完了すると続
いて１に設定される。この点で、完了ビットが１に設定
された場合、もし獲得コマンドのモードが書込みであれ
ば、プロセッサは書込みモードで対応範囲を保持する。
しかし、もし獲得コマンドのモードが読出し専用モード
ならば、プロセッサは読出し専用モードで対応範囲を保
持する。獲得コマンドは分割フェーズである。プロセッ
サはＣＯＣ（図１中、符号１０）に要求を出し、獲得処
理の進行中、自身のプログラムを実行し続ける。指定さ
れた完了ビットが１に設定された後、プロセッサは安全
に範囲内のメモリー・ロケーションにアクセスしてキャ
ッシュすることができ、ＣＯＣはメモリ範囲の局所的に
キャッシュされたコピーに対するコヒーレンスを維持す
る。
は、範囲が読出し専用モードまたは書込みモードで獲得
されているかどうかを示すビットである。完了ビット
は、最初は０に設定され、首尾良く獲得が完了すると続
いて１に設定される。この点で、完了ビットが１に設定
された場合、もし獲得コマンドのモードが書込みであれ
ば、プロセッサは書込みモードで対応範囲を保持する。
しかし、もし獲得コマンドのモードが読出し専用モード
ならば、プロセッサは読出し専用モードで対応範囲を保
持する。獲得コマンドは分割フェーズである。プロセッ
サはＣＯＣ（図１中、符号１０）に要求を出し、獲得処
理の進行中、自身のプログラムを実行し続ける。指定さ
れた完了ビットが１に設定された後、プロセッサは安全
に範囲内のメモリー・ロケーションにアクセスしてキャ
ッシュすることができ、ＣＯＣはメモリ範囲の局所的に
キャッシュされたコピーに対するコヒーレンスを維持す
る。
【００１８】（２）解放（範囲）
範囲は上記獲得コマンドを用いて早期に獲得していなけ
ればならない。プロセッサはＣＯＣに要求を出し、プロ
グラムを実行し続ける。要求の提出後ただちに、プロセ
ッサは範囲を放棄する。範囲が放棄されると、該範囲に
対するその後のアクセスはもはやコヒーレントではなく
なる。ＣＯＣはその範囲を解放し、範囲に対するその後
の獲得コマンドが出されるまで、メモリ範囲の局所的に
キャッシュされたコピーのコヒーレンスを維持する責任
はもはやなくなる。
ればならない。プロセッサはＣＯＣに要求を出し、プロ
グラムを実行し続ける。要求の提出後ただちに、プロセ
ッサは範囲を放棄する。範囲が放棄されると、該範囲に
対するその後のアクセスはもはやコヒーレントではなく
なる。ＣＯＣはその範囲を解放し、範囲に対するその後
の獲得コマンドが出されるまで、メモリ範囲の局所的に
キャッシュされたコピーのコヒーレンスを維持する責任
はもはやなくなる。
【００１９】＜グローバル・ロック・マネージャ（ＧＬ
Ｍ）＞グローバル・ロック・マネージャ（ＧＬＭ）は有
限状態マシン（ＦＳＭ）とグローバル・ロック・テーブ
ル（ＧＬＴ）とを有する。ＦＳＭの動作の流れは図８お
よび図９に図示されている。ＦＳＭを実現する一つの方
法として既知のプログラマブル論理アレイ（ＰＬＡ）を
用いることが挙げられる。
Ｍ）＞グローバル・ロック・マネージャ（ＧＬＭ）は有
限状態マシン（ＦＳＭ）とグローバル・ロック・テーブ
ル（ＧＬＴ）とを有する。ＦＳＭの動作の流れは図８お
よび図９に図示されている。ＦＳＭを実現する一つの方
法として既知のプログラマブル論理アレイ（ＰＬＡ）を
用いることが挙げられる。
【００２０】図３に示すように、ＧＬＭ１５は多重処理
システムのプロセッサによって現在獲得されている範囲
を追跡するテーブル（ＧＬＴ）を含む。仮想メモリ・ア
ドレス空間全体が処理ノードの間で区分化され、特定の
アドレス範囲は常に特定のノード上の同じＧＬＭによっ
て処理される。図３は、ＧＬＴのデータ構造を例示して
いる。ＧＬＴの各エントリは、タプルＴ１＝（範囲、モ
ード、バージョンｎ、参照回数ｋ、およびオーナＰ）に
より構成されている。ＸからＹまでの"範囲"は、ロック
獲得または解放コマンドに関連したメモリ・アドレス範
囲を示す。"モード"は、前記範囲が読出し専用（ＲＯ）
モードまたは書込み（Ｗ）モードでロックされているか
どうかを示す。"バージョン"は、前記範囲に対するロッ
クが書込みモードで何回獲得されたかを示す。"参照回
数"は、現在保持しているプロセッサの数を示す。"オー
ナ"は、そのような範囲が書込みモードで保持されてい
る場合に、その範囲を現在書込みモードで保持している
単一のプロセッサを示す。
システムのプロセッサによって現在獲得されている範囲
を追跡するテーブル（ＧＬＴ）を含む。仮想メモリ・ア
ドレス空間全体が処理ノードの間で区分化され、特定の
アドレス範囲は常に特定のノード上の同じＧＬＭによっ
て処理される。図３は、ＧＬＴのデータ構造を例示して
いる。ＧＬＴの各エントリは、タプルＴ１＝（範囲、モ
ード、バージョンｎ、参照回数ｋ、およびオーナＰ）に
より構成されている。ＸからＹまでの"範囲"は、ロック
獲得または解放コマンドに関連したメモリ・アドレス範
囲を示す。"モード"は、前記範囲が読出し専用（ＲＯ）
モードまたは書込み（Ｗ）モードでロックされているか
どうかを示す。"バージョン"は、前記範囲に対するロッ
クが書込みモードで何回獲得されたかを示す。"参照回
数"は、現在保持しているプロセッサの数を示す。"オー
ナ"は、そのような範囲が書込みモードで保持されてい
る場合に、その範囲を現在書込みモードで保持している
単一のプロセッサを示す。
【００２１】ＧＬＭは２つの動作の支援する。すなわ
ち、第１にロック（範囲、モード、完了ビット、ｎ）動
作である。 この動作は処理ノードのために、指定され
た範囲を指定されたモードで獲得する。もし獲得するこ
とができたならば、ＧＬＭは許可（範囲、モード、完了
ビット、バージョン）でノードｎに応答する。さもなけ
れば、拒否（範囲、モード、完了ビット）で応答する。
ち、第１にロック（範囲、モード、完了ビット、ｎ）動
作である。 この動作は処理ノードのために、指定され
た範囲を指定されたモードで獲得する。もし獲得するこ
とができたならば、ＧＬＭは許可（範囲、モード、完了
ビット、バージョン）でノードｎに応答する。さもなけ
れば、拒否（範囲、モード、完了ビット）で応答する。
【００２２】第２にアンロック（範囲）動作である。こ
の動作は指定された範囲をアンロックし、その範囲がそ
の後ロックされることを可能とする。
の動作は指定された範囲をアンロックし、その範囲がそ
の後ロックされることを可能とする。
【００２３】＜最近獲得ロック・マネージャ（ＲＡＬ
Ｍ）＞最近獲得ロック・マネージャ（ＲＡＬＭ）は、Ｒ
ＡＬＴおよびＦＳＭを有する。また、その動作を図４な
いし図７に示すとともに以下に説明する。ＧＬＭのＦＳ
Ｍと同じく、ＲＡＬＭのＦＳＭもＰＬＡを用いて実現す
ることができる。
Ｍ）＞最近獲得ロック・マネージャ（ＲＡＬＭ）は、Ｒ
ＡＬＴおよびＦＳＭを有する。また、その動作を図４な
いし図７に示すとともに以下に説明する。ＧＬＭのＦＳ
Ｍと同じく、ＲＡＬＭのＦＳＭもＰＬＡを用いて実現す
ることができる。
【００２４】図３に示すように、ＲＡＬＭ２０のＲＡＬ
Ｔはローカル・プロセッサによって現在獲得されている
範囲を追跡するテーブルから構成される。その目的は不
必要なキャッシュ・フラッシュを回避することであり、
またリモートＧＬＭとの通信を最小限にすることであ
る。ＲＡＬＴの各エントリはタプルＴ２（ＸからＹまで
の範囲、モード、バージョンｎ'、参照回数ｋ'、使用
中、放棄）から構成される。"範囲"は、ロック獲得また
は解放コマンドに関連したメモリ・アドレス範囲を示
す。"モード"は、前記範囲が読出し専用（ＲＯ）モード
または書込み（Ｗ）モードでロックされているかどうか
を示す。"バージョン"はローカル・キャッシュにコピー
されたメモリ・アドレス範囲にあるデータのバージョン
数を示す。"参照回数"は、ローカル・キャッシュにコピ
ーされた前記範囲の中のキャッシュ・ラインの数を示
す。"放棄"はロック解放時に範囲の所有権をＲＡＬＭが
放棄しなければならないことを示す。"使用中"はエント
リが現在使用中であるかどうかを示し、もはや必要では
ないＲＡＬＴのエントリを再利用するために使用され
る。エントリが現在使用中ということは、対応するエン
トリにある情報をＲＡＬＭが依然として使用できること
を意味する。よって、ＲＡＬＴの使用中でなくなったエ
ントリエントリは異なる範囲のために使用することが可
能である。
Ｔはローカル・プロセッサによって現在獲得されている
範囲を追跡するテーブルから構成される。その目的は不
必要なキャッシュ・フラッシュを回避することであり、
またリモートＧＬＭとの通信を最小限にすることであ
る。ＲＡＬＴの各エントリはタプルＴ２（ＸからＹまで
の範囲、モード、バージョンｎ'、参照回数ｋ'、使用
中、放棄）から構成される。"範囲"は、ロック獲得また
は解放コマンドに関連したメモリ・アドレス範囲を示
す。"モード"は、前記範囲が読出し専用（ＲＯ）モード
または書込み（Ｗ）モードでロックされているかどうか
を示す。"バージョン"はローカル・キャッシュにコピー
されたメモリ・アドレス範囲にあるデータのバージョン
数を示す。"参照回数"は、ローカル・キャッシュにコピ
ーされた前記範囲の中のキャッシュ・ラインの数を示
す。"放棄"はロック解放時に範囲の所有権をＲＡＬＭが
放棄しなければならないことを示す。"使用中"はエント
リが現在使用中であるかどうかを示し、もはや必要では
ないＲＡＬＴのエントリを再利用するために使用され
る。エントリが現在使用中ということは、対応するエン
トリにある情報をＲＡＬＭが依然として使用できること
を意味する。よって、ＲＡＬＴの使用中でなくなったエ
ントリエントリは異なる範囲のために使用することが可
能である。
【００２５】ＲＡＬＭは、メモリ範囲を獲得および解放
するローカル・プロセッサのコマンドのためにロックお
よびアンロック動作を適切なＧＬＭへ送り、以下の応答
を受信する。
するローカル・プロセッサのコマンドのためにロックお
よびアンロック動作を適切なＧＬＭへ送り、以下の応答
を受信する。
【００２６】（１）許可（範囲、モード、完了ビット、
バージョン） この動作はロックが獲得されること示す。これによって
ＲＡＬＴが更新され、対応する完了ビットを設定する。
バージョン） この動作はロックが獲得されること示す。これによって
ＲＡＬＴが更新され、対応する完了ビットを設定する。
【００２７】（２）拒否（範囲、モード、完了ビット）
この動作は指定された範囲に対するロックを再試行す
る。
る。
【００２８】ＲＡＬＭはまたローカル・キャッシュに対
するストア・スルー動作および無効化動作を生成する。
するストア・スルー動作および無効化動作を生成する。
【００２９】＜ＧＬＭおよびＲＡＬＭアルゴリズム＞図
４ないし図９は上記したコマンドに応答してＧＬＭおよ
びＲＡＬＭの有限状態マシンによって実行されるアルゴ
リズムを説明するためのフローチャートである。このア
ルゴリズムでは、もし２つの範囲が任意の共通メモリ・
アドレスを共有するならばこれらの範囲は一致する。な
お、システムの構成要素間でのコマンドの流れは、図２
を参照されたい。
４ないし図９は上記したコマンドに応答してＧＬＭおよ
びＲＡＬＭの有限状態マシンによって実行されるアルゴ
リズムを説明するためのフローチャートである。このア
ルゴリズムでは、もし２つの範囲が任意の共通メモリ・
アドレスを共有するならばこれらの範囲は一致する。な
お、システムの構成要素間でのコマンドの流れは、図２
を参照されたい。
【００３０】獲得（範囲、モード、完了ビット） 図４
参照。 １． ＣＢＶの指定された完了ビットをリセット（４
０）。 ２． 範囲を取り扱う処理ノードＰを計算（４１）。 ３． ロック（範囲、モード、完了ビット、Ｑ）を処理
ノードＰに送出（４２）。ここで、Ｑはロック要求を送
出するローカル処理ノードである。
参照。 １． ＣＢＶの指定された完了ビットをリセット（４
０）。 ２． 範囲を取り扱う処理ノードＰを計算（４１）。 ３． ロック（範囲、モード、完了ビット、Ｑ）を処理
ノードＰに送出（４２）。ここで、Ｑはロック要求を送
出するローカル処理ノードである。
【００３１】解放（範囲） 図５参照
１． 範囲が一致するＲＡＬＴ中のエントリＥを探索
（５０） ２． もしＥのモードが書込みであるならば（５１）、
キャッシュで変更されたこの範囲からのすべてのライン
についてストア・スルー・コマンドを出し（５４）、キ
ャッシュからのストア確認を待つ。 ３． 範囲を取り扱う処理ノードＰを計算（５２）。 ４． 範囲を取り扱う処理ノードＰにアンロック（範
囲）を送出（５３）。
（５０） ２． もしＥのモードが書込みであるならば（５１）、
キャッシュで変更されたこの範囲からのすべてのライン
についてストア・スルー・コマンドを出し（５４）、キ
ャッシュからのストア確認を待つ。 ３． 範囲を取り扱う処理ノードＰを計算（５２）。 ４． 範囲を取り扱う処理ノードＰにアンロック（範
囲）を送出（５３）。
【００３２】ロック（範囲、モード、完了ビット、Ｑ）
図８参照。 １．範囲が一致するＧＬＴ中のエントリＥを探索（８
１）。 ２．もし一致しなければ（８２）、 （ａ）ＧＬＴに新規エントリ［範囲、モード、１、０、
Ｑ］を入力。エントリ・フォーマットについて図３参
照。 （ｂ）許可（範囲、モード、完了ビット、０）を処理ノ
ードＱに送出（８４）。 ３．一致するエントリＥがあった場合、もしＥの参照回
数＝０ならば（８５）、 （ａ）Ｅの参照回数を１に設定（８６）。 （ｂ）Ｅのモードをロックのモードに設定（８６）。 （ｃ）もしモードが書込みならば、Ｅのバージョンを＋
１する（８８）。 （ｄ）許可（範囲、モード、完了ビット、Ｅのバージョ
ン）を処理ノードＱに送出（８９）。 ４．Ｅの参照回数が０でない場合、もしモードがＥのモ
ードに等しく、かつ読出し専用であるならば（９０）、 （ａ）Ｅの参照回数を＋１する（９１）。 （ｂ）許可（範囲、モード、完了ビット、Ｅのバージョ
ン）を処理ノードＱに送出（９２）。 ５．モードが同じでないか、読み出し専用でなければ、
拒否（範囲、モード、完了ビット）を処理ノードＱに送
出（９３）。
図８参照。 １．範囲が一致するＧＬＴ中のエントリＥを探索（８
１）。 ２．もし一致しなければ（８２）、 （ａ）ＧＬＴに新規エントリ［範囲、モード、１、０、
Ｑ］を入力。エントリ・フォーマットについて図３参
照。 （ｂ）許可（範囲、モード、完了ビット、０）を処理ノ
ードＱに送出（８４）。 ３．一致するエントリＥがあった場合、もしＥの参照回
数＝０ならば（８５）、 （ａ）Ｅの参照回数を１に設定（８６）。 （ｂ）Ｅのモードをロックのモードに設定（８６）。 （ｃ）もしモードが書込みならば、Ｅのバージョンを＋
１する（８８）。 （ｄ）許可（範囲、モード、完了ビット、Ｅのバージョ
ン）を処理ノードＱに送出（８９）。 ４．Ｅの参照回数が０でない場合、もしモードがＥのモ
ードに等しく、かつ読出し専用であるならば（９０）、 （ａ）Ｅの参照回数を＋１する（９１）。 （ｂ）許可（範囲、モード、完了ビット、Ｅのバージョ
ン）を処理ノードＱに送出（９２）。 ５．モードが同じでないか、読み出し専用でなければ、
拒否（範囲、モード、完了ビット）を処理ノードＱに送
出（９３）。
【００３３】アンロック（範囲） 図９参照。
１．指定された範囲に一致するエントリＥについてＧＬ
Ｔを探索（９５）。 ２．Ｅの参照回数を−１にする（９７）。
Ｔを探索（９５）。 ２．Ｅの参照回数を−１にする（９７）。
【００３４】許可（範囲、モード、完了ビット、バージ
ョン） 図６参照。 １．指定された範囲に一致するエントリＥについてＲＡ
ＬＴを探索（６０）。 ２．もし一致しなければ（６１）、 （ａ）新規エントリＥ＝［範囲、モード、０、０、Ｙ、
Ｎ］をＲＡＬＴに入力（６２）。 （ｂ）このエントリＥを以下のステップで使用する。 ３．もし当該許可のバージョンもしくはＥのバージョン
が０であるか、またはそれらが等しくなければ（６
３）、 （ａ）キャッシュに対して無効化コマンドを出すことに
よってこの範囲に属する全てのキャッシュ・ラインを無
効にする（６４）。 （ｂ）Ｅの参照回数を０に設定（６５）。 ４． Ｅのモードを許可のモードに設定（６６）。 ５． Ｅのバージョンを許可のバージョンに設定（６
６）。 ６． 指定された完了ビットを１に設定（６７）。
ョン） 図６参照。 １．指定された範囲に一致するエントリＥについてＲＡ
ＬＴを探索（６０）。 ２．もし一致しなければ（６１）、 （ａ）新規エントリＥ＝［範囲、モード、０、０、Ｙ、
Ｎ］をＲＡＬＴに入力（６２）。 （ｂ）このエントリＥを以下のステップで使用する。 ３．もし当該許可のバージョンもしくはＥのバージョン
が０であるか、またはそれらが等しくなければ（６
３）、 （ａ）キャッシュに対して無効化コマンドを出すことに
よってこの範囲に属する全てのキャッシュ・ラインを無
効にする（６４）。 （ｂ）Ｅの参照回数を０に設定（６５）。 ４． Ｅのモードを許可のモードに設定（６６）。 ５． Ｅのバージョンを許可のバージョンに設定（６
６）。 ６． 指定された完了ビットを１に設定（６７）。
【００３５】拒否（範囲、モード、完了ビット） 図７
参照。 １． ある期間にわたって遅延（７０）。 ２． 範囲を取り扱う処理ノードＰを計算（７１）。 ３． ロック（範囲、モード、完了ビット）を処理ノー
ドＰに送出（７２）。
参照。 １． ある期間にわたって遅延（７０）。 ２． 範囲を取り扱う処理ノードＰを計算（７１）。 ３． ロック（範囲、モード、完了ビット）を処理ノー
ドＰに送出（７２）。
【００３６】＜キャッシュ動作＞（図２参照）
キャッシュ５は、標準動作を実行する。一つのラインが
キャッシュに存在する場合、キャッシュはロード／スト
ア（読出し／書込み）コマンドに応答してラインを戻
す。さもなければ、メモリ６に対して要求がなされ、キ
ャッシュ内の新規ラインにメモリ６の内容がロードされ
る。ラインは変更された場合にダーティ・ラインとして
マークされる。ラインは、ＬＲＵアルゴリズムに従って
除去（パージ）される。ダーティ・ラインが除去される
場合、メモリ６に書き込まれる。ストア・スルー要求を
ＲＡＬＭ２０から受信すると、ラインはメモリに書込ま
れ、ダーティ・ビットがリセットされるが、該ラインは
排他的モードでキャッシュに保持される。無効化要求が
ＲＡＬＭ２０から受信されると、ラインは無効であると
マークされる。
キャッシュに存在する場合、キャッシュはロード／スト
ア（読出し／書込み）コマンドに応答してラインを戻
す。さもなければ、メモリ６に対して要求がなされ、キ
ャッシュ内の新規ラインにメモリ６の内容がロードされ
る。ラインは変更された場合にダーティ・ラインとして
マークされる。ラインは、ＬＲＵアルゴリズムに従って
除去（パージ）される。ダーティ・ラインが除去される
場合、メモリ６に書き込まれる。ストア・スルー要求を
ＲＡＬＭ２０から受信すると、ラインはメモリに書込ま
れ、ダーティ・ビットがリセットされるが、該ラインは
排他的モードでキャッシュに保持される。無効化要求が
ＲＡＬＭ２０から受信されると、ラインは無効であると
マークされる。
【００３７】＜性能を最適化するための拡張＞
【００３８】１． 完了ビット・ベクトルの仮想化
上記の設計では、任意のユーザ・プロセスによって完了
ビット・ベクトルにアクセスすることができる。多重プ
ログラミングを可能にするためには、何らかの保護機構
を設ける必要がある。完了ビット・ベクトルに対する保
護されたユーザ・レベルのアクセスを可能とする３通り
の実行可能な設計の概要を以下に説明する。
ビット・ベクトルにアクセスすることができる。多重プ
ログラミングを可能にするためには、何らかの保護機構
を設ける必要がある。完了ビット・ベクトルに対する保
護されたユーザ・レベルのアクセスを可能とする３通り
の実行可能な設計の概要を以下に説明する。
【００３９】ベース／境界チェック
この方式では、オペレーティング・システムは、例えば
初期設定時に完了ビット・ベクトルの連続した範囲をユ
ーザ・プロセスに割り当て、さらにベース／境界レジス
タを用いることによって、ハードウェアはその範囲から
外れた任意の完了ビットにユーザ・プロセスがアドレス
するのを防ぐ。ベース／境界レジスタはプロセス状態の
一部であり、プロセスが切り替わる際に、保管され、復
元される必要がある。
初期設定時に完了ビット・ベクトルの連続した範囲をユ
ーザ・プロセスに割り当て、さらにベース／境界レジス
タを用いることによって、ハードウェアはその範囲から
外れた任意の完了ビットにユーザ・プロセスがアドレス
するのを防ぐ。ベース／境界レジスタはプロセス状態の
一部であり、プロセスが切り替わる際に、保管され、復
元される必要がある。
【００４０】ユーザ・プロセスは、指標を用いて完了ビ
ットを指定し、さらにハードウエアはベースを指標に加
算し、もし得られた完了ビットが可能な範囲内ではない
とすると誤りとする。ノード間のすべての通信は完了ビ
ットの絶対指標を用いる。したがって、この方式では開
始元プロセスのスケジュールが解除されていても、獲得
動作に対する応答で完了ビットを設定することができ
る。
ットを指定し、さらにハードウエアはベースを指標に加
算し、もし得られた完了ビットが可能な範囲内ではない
とすると誤りとする。ノード間のすべての通信は完了ビ
ットの絶対指標を用いる。したがって、この方式では開
始元プロセスのスケジュールが解除されていても、獲得
動作に対する応答で完了ビットを設定することができ
る。
【００４１】保留応答カウンタ
この方式では、オペレーティング・システムはすべての
保留応答が復帰するまでプロセスの切り替えを遅らせ
る。ＲＡＬＭは保留応答の数を記録するカウンタを含
み、オペレーティング・システムはこのカウンタがゼロ
になるのを待って新しいプロセスに切り替える。この方
式が可能なのは、獲得動作に対する応答に無制限の遅延
がないからである。ＧＬＭは有限の期間内で成功または
失敗を戻す。したがって、オペレーティング・システム
はプロセスの切り替えが完了するまでの極めて長い間に
わって待つ必要はないであろう。
保留応答が復帰するまでプロセスの切り替えを遅らせ
る。ＲＡＬＭは保留応答の数を記録するカウンタを含
み、オペレーティング・システムはこのカウンタがゼロ
になるのを待って新しいプロセスに切り替える。この方
式が可能なのは、獲得動作に対する応答に無制限の遅延
がないからである。ＧＬＭは有限の期間内で成功または
失敗を戻す。したがって、オペレーティング・システム
はプロセスの切り替えが完了するまでの極めて長い間に
わって待つ必要はないであろう。
【００４２】プロセスの切り替え中、オペレーティング
・システムは完了ビット・ベクトルの現在の内容をプロ
セス保管領域に保管し、新たにスケジュールされたプロ
セスの完了ビット・ベクトルを復元する。
・システムは完了ビット・ベクトルの現在の内容をプロ
セス保管領域に保管し、新たにスケジュールされたプロ
セスの完了ビット・ベクトルを復元する。
【００４３】ピン・メモリ
この方式では、完了ビット・ベクトルはユーザのアドレ
ス空間にマップされ、効果的にビット・ベクトルがシス
テム・メモリ６に実装される。したがって、プロセスは
仮想メモリ・ハードウェアにより、それ自身の完了ビッ
トのみにアクセスするという制約を受ける。また、この
方式では、上記した保留応答カウンタ方式の場合と同様
に、プロセスの切り替え中に保留獲得動作を処理するた
めに、何らかのオペレーティング・システム・サポート
を必要とする。
ス空間にマップされ、効果的にビット・ベクトルがシス
テム・メモリ６に実装される。したがって、プロセスは
仮想メモリ・ハードウェアにより、それ自身の完了ビッ
トのみにアクセスするという制約を受ける。また、この
方式では、上記した保留応答カウンタ方式の場合と同様
に、プロセスの切り替え中に保留獲得動作を処理するた
めに、何らかのオペレーティング・システム・サポート
を必要とする。
【００４４】完了ビットは、オペレーティング・システ
ムが各プロセスに割り当てているピン・メモリ領域にマ
ップされる。例えば、ＡＩＸでは、プロセスのｕ−ブロ
ック領域に対してメモリのピン・ページが存在する。ノ
ード間の全ての通信は完了ビットを指定するために物理
アドレスを使用し、ＲＡＬＭは完了ビットを直接ＤＲＡ
Ｍに書込むことができる。
ムが各プロセスに割り当てているピン・メモリ領域にマ
ップされる。例えば、ＡＩＸでは、プロセスのｕ−ブロ
ック領域に対してメモリのピン・ページが存在する。ノ
ード間の全ての通信は完了ビットを指定するために物理
アドレスを使用し、ＲＡＬＭは完了ビットを直接ＤＲＡ
Ｍに書込むことができる。
【００４５】完了ビット・ベクトルへのアクセスを加速
するために、高速オンチップ・レジスタに完了ビット・
ベクトルをミラーリングすることも可能である。完了ビ
ット・ベクトル中のビットを設定する応答が届いた場
合、ＲＡＬＭは通常それをＤＲＡＭに設定する。さら
に、もしそのビットが現在実行されているプロセスに属
するならば、オンチップ・レジスタもまた設定される。
プロセスの切り替え中、オンチップ・レジスタはＤＲＡ
Ｍのコピーからロードされる。
するために、高速オンチップ・レジスタに完了ビット・
ベクトルをミラーリングすることも可能である。完了ビ
ット・ベクトル中のビットを設定する応答が届いた場
合、ＲＡＬＭは通常それをＤＲＡＭに設定する。さら
に、もしそのビットが現在実行されているプロセスに属
するならば、オンチップ・レジスタもまた設定される。
プロセスの切り替え中、オンチップ・レジスタはＤＲＡ
Ｍのコピーからロードされる。
【００４６】２．排他的モード・ロックのキャッシング
ＲＡＬＭは、ロックに関連した範囲にあるデータはロー
カル・キャッシュに格納できるとはいえ、該ロックを獲
得または解放するために常にＧＬＭ（場合によってはリ
モートＧＬＭ）と接触しなければならない。これは、ロ
ックに対するキャッシュされたコピーを記録するディレ
クトリの必要性をなくすためである。しかし、単一のプ
ロセッサが他のプロセッサからの競合アクセスなしに同
じロックを繰り返してアクセスする場合、これは無駄と
なる。
カル・キャッシュに格納できるとはいえ、該ロックを獲
得または解放するために常にＧＬＭ（場合によってはリ
モートＧＬＭ）と接触しなければならない。これは、ロ
ックに対するキャッシュされたコピーを記録するディレ
クトリの必要性をなくすためである。しかし、単一のプ
ロセッサが他のプロセッサからの競合アクセスなしに同
じロックを繰り返してアクセスする場合、これは無駄と
なる。
【００４７】本発明では、排他的モード・ロックの場合
にＧＬＭに接触することを避けるための最適化を提案す
る。この最適化では、もしロックが排他的モードで獲得
されるならば、ＲＡＬＭはロックをキャッシュすること
が可能となる。ＧＬＭはキャッシュされたロックを持つ
単一のノードを記憶しておくことのみを必要とする。解
放動作は、ＲＡＬＭにロックのコピーを保持し、単一の
プロセッサによる繰り返しアクセスはＲＡＬＭによって
直接処理される。もし他のプロセッサがロック（共有モ
ードまたは排他的モードのいずれか）の獲得を指示する
ならば、ＧＬＭはキャッシュされたロックを持つＲＡＬ
Ｍに対して放棄の要求を送る。次の解放動作の間、ＲＡ
ＬＭはロックのコピーを放棄する。この最適化を実現を
する上で必要とされるハードウェア・サポートは、排他
的モード・ロックのオーナを記録するＧＬＴエントリの
フィールドと、さらにキャッシュされたロックを解放動
作で放棄するかどうかを判断するＲＡＬＴエントリの放
棄ビットである。従来のアプローチとは異なって、ここ
でもディレクトリを必要としない。
にＧＬＭに接触することを避けるための最適化を提案す
る。この最適化では、もしロックが排他的モードで獲得
されるならば、ＲＡＬＭはロックをキャッシュすること
が可能となる。ＧＬＭはキャッシュされたロックを持つ
単一のノードを記憶しておくことのみを必要とする。解
放動作は、ＲＡＬＭにロックのコピーを保持し、単一の
プロセッサによる繰り返しアクセスはＲＡＬＭによって
直接処理される。もし他のプロセッサがロック（共有モ
ードまたは排他的モードのいずれか）の獲得を指示する
ならば、ＧＬＭはキャッシュされたロックを持つＲＡＬ
Ｍに対して放棄の要求を送る。次の解放動作の間、ＲＡ
ＬＭはロックのコピーを放棄する。この最適化を実現を
する上で必要とされるハードウェア・サポートは、排他
的モード・ロックのオーナを記録するＧＬＴエントリの
フィールドと、さらにキャッシュされたロックを解放動
作で放棄するかどうかを判断するＲＡＬＴエントリの放
棄ビットである。従来のアプローチとは異なって、ここ
でもディレクトリを必要としない。
【００４８】まとめとして、本発明の構成に関して以下
の事項を開示する。 （１）多重プロセッサ・システムにおいて、複数のオブ
ジェクトの破壊を防ぐ一方で、前記複数のオブジェクト
へのアクセスをインタリーブするためのコヒーレンス・
オブジェクト・コントローラであって、前記多重プロセ
ッサ・システムを構成するプロセッサから受け取った明
示的コヒーレンス・コマンドを実行するための手段と、
各プロセッサで維持される完了ビット・ベクトルを含
み、前記明示的コヒーレンス・コマンドの実行の完了を
示す手段と、前記明示的コヒーレンス・コマンドの実行
の完了が示されたときに、関連するプロセッサにおいて
第１のアドレス範囲を書込みモードまたは読出し専用モ
ードで保持する手段と、前記明示的コヒーレンス・コマ
ンドが解放コマンドである場合に、該コマンドの実行完
了を示したプロセッサにおいて第２のアドレス範囲を放
棄する手段と、を備えるコヒーレンス・オブジェクト・
コントローラ。 （２）プロセッサによって保持されたアドレス範囲のコ
ヒーレンスを維持する手段をさらに備える、上記（１）
に記載のコヒーレンス・オブジェクト・コントローラ。 （３）複数のプロセッサを含む多重プロセッサ・システ
ムにおいて、複数のオブジェクトの破壊を防ぐ一方で、
前記複数のオブジェクトへのアクセスをインタリーブす
るためのコヒーレンス・オブジェクト・コントローラで
あって、前記複数のプロセッサの一つから明示的コヒー
レンス・コマンドに応答してロック・コマンドを生成
し、前記ロック・コマンドに対する応答を受け取り、前
記一つのプロセッサに保持された完了ビット・ベクトル
中の、対応する明示的コヒーレンス・コマンドの完了を
示す完了ビットを設定する第１のロック・マネージャ
と、前記第１のロック・マネージャ（ＲＡＬＭ）から、
書込みモードまたは読出し専用モードのいずれかのモー
ドを示す前記ロック・コマンドを受け取り、前記ロック
・コマンドの許可または拒否を示す応答を生成する第２
のロック・マネージャとを備え、前記第１のロック・マ
ネージャ（ＲＡＬＭ）および前記第２のロック・マネー
ジャは、書込みモードのロック・コマンドを一時に一台
のプロセッサのみ許可することによって、複数のプロセ
ッサが前記オブジェクトを同時に変更することを特徴と
するコヒーレンス・オブジェクト・コントローラ。 （４）前記第２のロック・マネージャは、前記多重プロ
セッサ・システムの特定の処理ノードが書込みモードで
関連アドレス範囲を獲得したことを示すオーナ・フィー
ルドを有するグローバル・ロック・テーブルを含み、前
記第１のロック・マネージャは、前記特定の処理ノード
が前記アドレス範囲に対するロックを放棄すべきである
ことを示す放棄フィールドを有する獲得ロック・テーブ
ルを含むことを特徴とする上記（３）に記載のコヒーレ
ンス・オブジェクト・コントローラ。 （５）前記明示的コヒーレンス・コマンドは、書込みモ
ードもしくは読出し専用モードでメモリ・アドレスの一
範囲を獲得する獲得コマンド、または前記メモリ・アド
レスの一範囲を解放する解放コマンドであることを特徴
とする上記（３）に記載のコヒーレンス・オブジェクト
・コントローラ。 （６）前記獲得コマンドは、前記複数のプロセッサの一
つから出され、該一つのプロセッサは、前記獲得コマン
ドを出した後に前記獲得コマンドの完了を待つことなし
に他のコマンドを続けて実行することができ、さらに前
記獲得コマンドで指定された前記範囲にアクセスする前
に、前記完了ビット・ベクトルの対応するビットの設定
をチェックすることを特徴とする上記（５）に記載のコ
ヒーレンス・オブジェクト・コントローラ。 （７）他の全てのプロセッサによる前記範囲の解放を示
す参照回数が使用されることを特徴とする上記（６）に
記載のコヒーレンス・オブジェクト・コントローラ。 （８）第１のアドレスの範囲を持つ明示的コヒーレンス
書込みコマンドを出した各プロセッサは、前記第１のア
ドレス範囲への書込み前に、他のすべてのプロセッサに
よって前記第１のアドレス範囲が解放されるのを待つこ
とを特徴とする上記（３）に記載のコヒーレンス・オブ
ジェクト・コントローラ。 （９）多重プロセッサ・システムにおいて複数のオブジ
ェクトの破壊を防ぐ一方で、前記複数のオブジェクトへ
のアクセスをインタリーブする方法であって、前記多重
プロセッサ・システムを構成するプロセッサから受け取
った明示的コヒーレンスコマンドを実行するステップ
と、各プロセッサに保持される完了ビット・ベクトルに
より、前記明示的コヒーレンスコマンドの実行の完了を
示すステップと、前記明示的コヒーレンス・コマンドの
一つの完了が示されたときに該コマンドが出したプロセ
ッサにおいて第１のアドレスの範囲を書込みモードまた
は読出し専用モードで保持するステップと、前記明示的
コヒーレンス・コマンドが解放コマンドである場合に、
該コマンドの完了を示したプロセッサにおいて、第２の
アドレス範囲を放棄するステップと、を有する複数のオ
ブジェクトへのアクセスをインタリーブする方法。
の事項を開示する。 （１）多重プロセッサ・システムにおいて、複数のオブ
ジェクトの破壊を防ぐ一方で、前記複数のオブジェクト
へのアクセスをインタリーブするためのコヒーレンス・
オブジェクト・コントローラであって、前記多重プロセ
ッサ・システムを構成するプロセッサから受け取った明
示的コヒーレンス・コマンドを実行するための手段と、
各プロセッサで維持される完了ビット・ベクトルを含
み、前記明示的コヒーレンス・コマンドの実行の完了を
示す手段と、前記明示的コヒーレンス・コマンドの実行
の完了が示されたときに、関連するプロセッサにおいて
第１のアドレス範囲を書込みモードまたは読出し専用モ
ードで保持する手段と、前記明示的コヒーレンス・コマ
ンドが解放コマンドである場合に、該コマンドの実行完
了を示したプロセッサにおいて第２のアドレス範囲を放
棄する手段と、を備えるコヒーレンス・オブジェクト・
コントローラ。 （２）プロセッサによって保持されたアドレス範囲のコ
ヒーレンスを維持する手段をさらに備える、上記（１）
に記載のコヒーレンス・オブジェクト・コントローラ。 （３）複数のプロセッサを含む多重プロセッサ・システ
ムにおいて、複数のオブジェクトの破壊を防ぐ一方で、
前記複数のオブジェクトへのアクセスをインタリーブす
るためのコヒーレンス・オブジェクト・コントローラで
あって、前記複数のプロセッサの一つから明示的コヒー
レンス・コマンドに応答してロック・コマンドを生成
し、前記ロック・コマンドに対する応答を受け取り、前
記一つのプロセッサに保持された完了ビット・ベクトル
中の、対応する明示的コヒーレンス・コマンドの完了を
示す完了ビットを設定する第１のロック・マネージャ
と、前記第１のロック・マネージャ（ＲＡＬＭ）から、
書込みモードまたは読出し専用モードのいずれかのモー
ドを示す前記ロック・コマンドを受け取り、前記ロック
・コマンドの許可または拒否を示す応答を生成する第２
のロック・マネージャとを備え、前記第１のロック・マ
ネージャ（ＲＡＬＭ）および前記第２のロック・マネー
ジャは、書込みモードのロック・コマンドを一時に一台
のプロセッサのみ許可することによって、複数のプロセ
ッサが前記オブジェクトを同時に変更することを特徴と
するコヒーレンス・オブジェクト・コントローラ。 （４）前記第２のロック・マネージャは、前記多重プロ
セッサ・システムの特定の処理ノードが書込みモードで
関連アドレス範囲を獲得したことを示すオーナ・フィー
ルドを有するグローバル・ロック・テーブルを含み、前
記第１のロック・マネージャは、前記特定の処理ノード
が前記アドレス範囲に対するロックを放棄すべきである
ことを示す放棄フィールドを有する獲得ロック・テーブ
ルを含むことを特徴とする上記（３）に記載のコヒーレ
ンス・オブジェクト・コントローラ。 （５）前記明示的コヒーレンス・コマンドは、書込みモ
ードもしくは読出し専用モードでメモリ・アドレスの一
範囲を獲得する獲得コマンド、または前記メモリ・アド
レスの一範囲を解放する解放コマンドであることを特徴
とする上記（３）に記載のコヒーレンス・オブジェクト
・コントローラ。 （６）前記獲得コマンドは、前記複数のプロセッサの一
つから出され、該一つのプロセッサは、前記獲得コマン
ドを出した後に前記獲得コマンドの完了を待つことなし
に他のコマンドを続けて実行することができ、さらに前
記獲得コマンドで指定された前記範囲にアクセスする前
に、前記完了ビット・ベクトルの対応するビットの設定
をチェックすることを特徴とする上記（５）に記載のコ
ヒーレンス・オブジェクト・コントローラ。 （７）他の全てのプロセッサによる前記範囲の解放を示
す参照回数が使用されることを特徴とする上記（６）に
記載のコヒーレンス・オブジェクト・コントローラ。 （８）第１のアドレスの範囲を持つ明示的コヒーレンス
書込みコマンドを出した各プロセッサは、前記第１のア
ドレス範囲への書込み前に、他のすべてのプロセッサに
よって前記第１のアドレス範囲が解放されるのを待つこ
とを特徴とする上記（３）に記載のコヒーレンス・オブ
ジェクト・コントローラ。 （９）多重プロセッサ・システムにおいて複数のオブジ
ェクトの破壊を防ぐ一方で、前記複数のオブジェクトへ
のアクセスをインタリーブする方法であって、前記多重
プロセッサ・システムを構成するプロセッサから受け取
った明示的コヒーレンスコマンドを実行するステップ
と、各プロセッサに保持される完了ビット・ベクトルに
より、前記明示的コヒーレンスコマンドの実行の完了を
示すステップと、前記明示的コヒーレンス・コマンドの
一つの完了が示されたときに該コマンドが出したプロセ
ッサにおいて第１のアドレスの範囲を書込みモードまた
は読出し専用モードで保持するステップと、前記明示的
コヒーレンス・コマンドが解放コマンドである場合に、
該コマンドの完了を示したプロセッサにおいて、第２の
アドレス範囲を放棄するステップと、を有する複数のオ
ブジェクトへのアクセスをインタリーブする方法。
【図１】本発明にもとづくコヒーレンス・オブジェクト
・コントローラが実装された多重プロセッサの概略的構
成を示すブロック図である。
・コントローラが実装された多重プロセッサの概略的構
成を示すブロック図である。
【図２】処理ノード、特に処理ノード内にあるコヒーレ
ンス・オブジェクト・コントローラ、さらに完了ビット
・ベクトルを説明するためのブロック図である。
ンス・オブジェクト・コントローラ、さらに完了ビット
・ベクトルを説明するためのブロック図である。
【図３】最近獲得テーブル（ＲＡＬＴ）およびグローバ
ル・ロック・テーブル（ＧＬＴ）の一例を示す図であ
る。
ル・ロック・テーブル（ＧＬＴ）の一例を示す図であ
る。
【図４】獲得コマンドの流れを説明するためのフローチ
ャートである。
ャートである。
【図５】解放コマンドの流れを説明するためのフローチ
ャートである。
ャートである。
【図６】グローバル・ロック・マネージャ（ＧＬＭ）か
らの許可応答を受け取ることによって最近獲得ロック・
マネージャ（ＲＡＬＭ）が実行する動作のフローチャー
トである。
らの許可応答を受け取ることによって最近獲得ロック・
マネージャ（ＲＡＬＭ）が実行する動作のフローチャー
トである。
【図７】グローバル・ロック・マネージャ（ＧＬＭ）か
らの拒否応答を受け取ることによって最近獲得ロック・
マネージャ（ＲＡＬＭ）が実行する動作のフローチャー
トである。
らの拒否応答を受け取ることによって最近獲得ロック・
マネージャ（ＲＡＬＭ）が実行する動作のフローチャー
トである。
【図８】最近獲得ロック・マネージャ（ＲＡＬＭ）から
ロック・コマンドを受け取ることによってグローバル・
ロック・マネージャ（ＧＬＭ）が実行する動作のフロー
チャートである。
ロック・コマンドを受け取ることによってグローバル・
ロック・マネージャ（ＧＬＭ）が実行する動作のフロー
チャートである。
【図９】最近獲得ロック・マネージャ（ＲＡＬＭ）から
アンロック・コマンドを受け取ることによってグローバ
ル・ロック・マネージャ（ＧＬＭ）が実行する動作のフ
ローチャートである。
アンロック・コマンドを受け取ることによってグローバ
ル・ロック・マネージャ（ＧＬＭ）が実行する動作のフ
ローチャートである。
【符号の説明】
１ 処理ノード
２ プロセッサ
３ ネットワーク・インタフェース
５ キャッシュ
６ メモリ
７ ネットワーク
１０ ＣＯＣ
１５ ＧＬＭ
２０ ＲＡＬＭ
２５ ＣＢＶ
─────────────────────────────────────────────────────
フロントページの続き
(72)発明者 ベン−ホン・リン
アメリカ合衆国10606、 ニューヨーク
州 ホワイト プレインズ マーティン
アヴェニュー ４
(72)発明者 プラタップ・チャンドラ・パタナイク
アメリカ合衆国10562、 ニューヨーク
州 オッシニング バーンス ストリー
ト 213
(56)参考文献 特開 平８−314871（ＪＰ，Ａ)
特開 昭59−174962（ＪＰ，Ａ)
Ｓａｎｄｈｕ Ｈ．Ｓ．ｅｔ ａ
ｌ．，Ｔｈｅ Ｓｈａｒｅｄ Ｒｅｇｉ
ｏｎｓ Ａｐｐｒｏａｃｈ ｔｏ Ｓｏ
ｆｔｏｗａｒｅ Ｃａｃｈｅ Ｃｏｈｅ
ｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｐｒｏｃ
ｅｓｓｏｒｓ，ＡＣＭ ＳＩＧＰＬＡＮ
Ｎｏｔｉｃｅｓ，米国，ＡＣＭ，1993
年，Ｖｏｌ．28，Ｎｏ．７，ｐ．229−
238
Ｓａｎｄｈｕ Ｈ．Ｓ．，Ａｌｇｏｒ
ｉｔｈｍｓ ｆｏｒ Ｄｙｎａｍｉｃ
Ｓｏｆｔｗａｒｅ Ｃａｃｈｅ Ｃｏｈ
ｅｒｅｎｃｅ，Ｊｏｕｒｎａｌ ｏｆ
Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒ
ｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，米
国，Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ,
1995年，Ｖｏｌ．29，ｐ．142−157
(58)調査した分野(Int.Cl.7，ＤＢ名)
G06F 12/08
G06F 15/177
G06F 12/00
Claims (9)
- 【請求項１】多重プロセッサ・システムにおいて、複数
のオブジェクトの破壊を防ぐ一方で、前記複数のオブジ
ェクトへのアクセスをインタリーブするためのコヒーレ
ンス・オブジェクト・コントローラであって、 （ａ）複数のプロセッサの一つからコヒーレンス・コマ
ンドを受け取る最近獲得ロック・マネージャ（ＲＡＬ
Ｍ）であって、 メモリ・アドレスの一範囲を獲得する前記コヒーレンス
・コマンドは、前記複数のプロセッサの一つから出さ
れ、 前記コヒーレンス・コマンドは、書込みモードもしくは
読出し専用モードで前記メモリ・アドレスの一範囲を獲
得する獲得コマンド、または前記メモリ・アドレスの一
範囲を解放する解放コマンドであり、 前記複数のプロセッサの一つからのコヒーレンス・コマ
ンドに応答してロック・コマンドを生成し、前記ロック
・コマンドに対する応答を受け取り、前記一つのプロセ
ッサに保持された完了ビット・ベクトル中の、対応する
コヒーレンス・コマンドの完了を示す完了ビットを設定
する最近獲得ロック・マネージャ（ＲＡＬＭ）と、 （ｂ）前記ＲＡＬＭから、書込みモードまたは読出し専
用モードのいずれかのモードを示す前記ロック・コマン
ドを受け取り、前記ロック・コマンドの許可または拒否
を示す応答を生成するグローバル・ロック・マネージャ
（ＧＬＭ）と、 を備え、 前記ＲＡＬＭおよび前記ＧＬＭは、書込みモードのロッ
ク・コマンドを一時に一台のプロセッサのみ許可するこ
とによって、複数のプロセッサが前記オブジェクトを同
時に変更することを防ぎ、 メモリ・アドレスの一範囲を獲得する前記獲得コマンド
は、前記複数のプロセッサの一つから出され、該一つの
プロセッサは、前記獲得コマンドを出した後に前記獲得
コマンドの完了を待つことなしに他のコマンドを続けて
実行することができ、さらに、前記獲得コマンドで指定
された前記範囲にアクセスする前に、前記完了ビット・
ベクトルの対応するビットの設定をチェックすることを
特徴とするコヒーレンス・オブジェクト・コントロー
ラ。 - 【請求項２】多重プロセッサ・システムにおいて、複数
のオブジェクトの破壊を防ぐ一方で、前記複数のオブジ
ェクトへのアクセスをインタリーブするためのコヒーレ
ンス・オブジェクト・コントローラであって、 （ａ）複数のプロセッサの一つからコヒーレンス・コマ
ンドを受け取る最近獲得ロック・マネージャ（ＲＡＬ
Ｍ）であって、 前記コヒーレンス・コマンドは、書込みモードもしくは
読出し専用モードでメモリ・アドレスの一範囲を獲得す
る獲得コマンド、または前記メモリ・アドレスの一範囲
を解放する解放コマンドであり、 前記複数のプロセッサの一つからのコヒーレンス・コマ
ンドに応答してロック・コマンドを生成し、前記ロック
・コマンドに対する応答を受け取り、前記一つのプロセ
ッサに保持された完了ビット・ベクトル中の、対応する
コヒーレンス・コマンドの完了を示す完了ビットを設定
する最近獲得ロック・マネージャ（ＲＡＬＭ）と、 （ｂ）前記ＲＡＬＭから、書込みモードまたは読出し専
用モードのいずれかのモードを示す前記ロック・コマン
ドを受け取り、前記ロック・コマンドの許可または拒否
を示す応答を生成する、前記多重プロセッサ・システム
の各ノードに設けられたグローバル・ロック・マネージ
ャ（ＧＬＭ）と、 を備え、 前記ＲＡＬＭおよび前記ＧＬＭは、書込みモードのロッ
ク・コマンドを一時に一台のプロセッサのみ許可するこ
とによって、複数のプロセッサが前記オブジェクトを同
時に変更することを防ぎ、 それぞれのＧＬＭは、対応する割り当てられたアドレス
範囲のロックを保持し、 メモリ・アドレスの一範囲を獲得する前記獲得コマンド
は、前記複数のプロセッサの一つから出され、該一つの
プロセッサは、前記獲得コマンドを出した後に前記獲得
コマンドの完了を待つことなしに他のコマンドを続けて
実行することができ、さらに、前記獲得コマンドで指定
された前記範囲にアクセスする前に、前記完了ビット・
ベクトルの対応するビットの設定をチェックすることを
特徴とするコヒーレンス・オブジェクト・コントロー
ラ。 - 【請求項３】多重プロセッサ・システムにおいて、複数
のオブジェクトの破壊を防ぐ一方で、前記複数のオブジ
ェクトへのアクセスをインタリーブするためのコヒーレ
ンス・オブジェクト・コントローラであって、 （ａ）前記多重プロセッサ・システムを構成するプロセ
ッサから受け取ったコヒーレンス・コマンドであって、
書込みモードもしくは読出し専用モードでメモリ・アド
レスの一範囲を獲得する獲得コマンド、または前記メモ
リ・アドレスの一範囲を解放する解放コマンドである、
それぞれの前記コヒーレンス・コマンドを実行するため
の手段と、 （ｂ）各前記プロセッサのレジスタで保持される完了ビ
ット・ベクトルにより、前記コヒーレンス・コマンドの
実行の完了を示す手段と、 （ｃ）前記コヒーレンス・コマンドの実行の完了が示さ
れたときに、関連するプロセッサにおいて第１のアドレ
ス範囲を、前記コヒーレンス・コマンドが書込み獲得コ
マンドである場合は書込みモードで、また、前記コヒー
レンス・コマンドが読出し専用獲得コマンドである場合
は読出し専用モードで、保持する手段と、 （ｄ）前記コヒーレンス・コマンドが解放コマンドであ
る場合に、前記コヒーレンス・コマンドの実行完了を示
したプロセッサにおいて第２のアドレス範囲を放棄する
手段と、 を備え、 メモリ・アドレスの一範囲を獲得する前記獲得コマンド
は、前記複数のプロセッサの一つから出され、該一つの
プロセッサは、前記獲得コマンドを出した後に前記獲得
コマンドの完了を待つことなしに他のコマンドを続けて
実行することができ、さらに、前記獲得コマンドで指定
された前記範囲にアクセスする前に、前記完了ビット・
ベクトルの対応するビットの設定をチェックすることを
特徴とするコヒーレンス・オブジェクト・コントロー
ラ。 - 【請求項４】多重プロセッサ・システムにおいて、複数
のオブジェクトの破壊を防ぐ一方で、前記複数のオブジ
ェクトへのアクセスをインタリーブするためのコヒーレ
ンス・オブジェクト・コントローラであって、 （ａ）複数のプロセッサの一つから、コヒーレンス・コ
マンドである、書込みモードもしくは読出し専用モード
でメモリ・アドレスの一範囲を獲得する獲得コマンド、
または前記メモリ・アドレスの一範囲を解放する解放コ
マンドを受け取る最近獲得ロック・マネージャ（ＲＡＬ
Ｍ）であって、 前記複数のプロセッサの一つからのコヒーレンス・コマ
ンドに応答してロック・コマンドを生成し、前記ロック
・コマンドに対する応答を受け取り、前記一つのプロセ
ッサに保持された完了ビット・ベクトル中の、対応する
コヒーレンス・コマンドの完了を示す完了ビットを設定
する最近獲得ロック・マネージャ（ＲＡＬＭ）と、 （ｂ）前記ＲＡＬＭから、書込みモードまたは読出し専
用モードのいずれかのモードを示す前記ロック・コマン
ドを受け取り、前記ロック・コマンドの許可または拒否
を示す応答を生成するグローバル・ロック・マネージャ
（ＧＬＭ）と、 を備え、 メモリ・アドレスの一範囲を獲得する前記獲得コマンド
は、前記複数のプロセッサの一つから出され、前記獲得
コマンドを出した後に前記獲得コマンドの完了を待つこ
となしに、前記一つのプロセッサに他のコマンドを続け
て実行することを可能とさせ、さらに、前記獲得コマン
ドで指定された前記範囲にアクセスする前に、前記完了
ビット・ベクトルの対応するビットの設定が、前記プロ
セッサによりチェックされることを特徴とするコヒーレ
ンス・オブジェクト・コントローラ。 - 【請求項５】多重プロセッサ・システムにおいて、複数
のオブジェクトの破壊を防ぐ一方で、前記複数のオブジ
ェクトへのアクセスをインタリーブするためのコヒーレ
ンス・オブジェクト・コントローラであって、 前記多
重プロセッサ・システムを構成するプロセッサから受け
取ったコヒーレンス・コマンドを実行するための手段
と、 各プロセッサで保持される完了ビット・ベクトルを含
み、前記コヒーレンス・コマンドの実行の完了を示す手
段と、 前記コヒーレンス・コマンドの実行の完了が示されたと
きに、関連するプロセッサにおいて第１のアドレス範囲
を書込みモードまたは読出し専用モードで保持する手段
と、 前記コヒーレンス・コマンドが解放コマンドである場合
に、前記コヒーレンス・コマンドの実行完了を示したプ
ロセッサにおいて第２のアドレス範囲を放棄する手段
と、 を備え、 メモリ・アドレスの一範囲を獲得する獲得コマンドは、
前記複数のプロセッサの一つから出され、該一つのプロ
セッサは、前記獲得コマンドを出した後に前記獲得コマ
ンドの完了を待つことなしに他のコマンドを続けて実行
することができ、さらに、前記獲得コマンドで指定され
た前記範囲にアクセスする前に、前記完了ビット・ベク
トルの対応するビットの設定をチェックすることを特徴
とするコヒーレンス・オブジェクト・コントローラ。 - 【請求項６】複数のプロセッサを含む多重プロセッサ・
システムにおいて、複数のオブジェクトの破壊を防ぐ一
方で、前記複数のオブジェクトへのアクセスをインタリ
ーブするためのコヒーレンス・オブジェクト・コントロ
ーラであって、 前記複数のプロセッサの一つからコヒーレンス・コマン
ドに応答してロック・コマンドを生成し、前記ロック・
コマンドに対する応答を受け取り、前記一つのプロセッ
サに保持された完了ビット・ベクトル中の、対応するコ
ヒーレンス・コマンドの完了を示す完了ビットを設定す
る第１のロック・マネージャと、 前記第１のロック・マネージャから、書込みモードまた
は読出し専用モードのいずれかのモードを示す前記ロッ
ク・コマンドを受け取り、前記ロック・コマンドの許可
または拒否を示す応答を生成する第２のロック・マネー
ジャとを備え、 前記第１のロック・マネージャおよび前記第２のロック
・マネージャは、書込みモードのロック・コマンドを一
時に一台のプロセッサのみ許可することによって、複数
のプロセッサが前記オブジェクトを同時に変更すること
を防ぎ、 メモリ・アドレスの一範囲を獲得する獲得コマンドは、
前記複数のプロセッサの一つから出され、該一つのプロ
セッサは、前記獲得コマンドを出した後に前記獲得コマ
ンドの完了を待つことなしに他のコマンドを続けて実行
することができ、さらに、前記獲得コマンドで指定され
た前記範囲にアクセスする前に、前記完了ビット・ベク
トルの対応するビットの設定をチェックすることを特徴
とするコヒーレンス・オブジェクト・コントローラ。 - 【請求項７】他の全ての前記プロセッサによる前記範囲
の解放を示す、参照回数が使用されることを特徴とする
請求項１乃至６の何れか１つに記載のコヒーレンス・オ
ブジェクト・コントローラ。 - 【請求項８】第１のアドレスの範囲に対するコヒーレン
ス書込みコマンドを出した各プロセッサは、前記第１の
アドレス範囲への書込み前に、他のすべてのプロセッサ
によって前記第１のアドレス範囲が解放されるのを待つ
ことを特徴とする請求項１乃至７の何れか１つに記載の
コヒーレンス・オブジェクト・コントローラ。 - 【請求項９】多重プロセッサ・システムにおいて複数の
オブジェクトの破壊を防ぐ一方で、前記複数のオブジェ
クトへのアクセスをインタリーブする方法であって、
前記多重プロセッサ・システムを構成するプロセッサか
ら受け取ったコヒーレンス・コマンドを実行するステッ
プと、 各プロセッサに保持される完了ビット・ベクト
ルにより、前記コヒーレンス・コマンドの実行の完了を
示すステップと、 前記コヒーレンス・コマンドの一つの完了が示されたと
きに前記コヒーレンス・コマンドを出したプロセッサに
おいて第１のアドレスの範囲を書込みモードまたは読出
し専用モードで保持するステップと、 前記コヒーレンス・コマンドが解放コマンドである場合
に、前記コヒーレンス・コマンドの完了を示したプロセ
ッサにおいて、第２のアドレス範囲を放棄するステップ
と、 を有し、 メモリ・アドレスの一範囲を獲得する獲得コマンドは、
前記複数のプロセッサの一つから出され、該一つのプロ
セッサは、前記獲得コマンドを出した後に前記獲得コマ
ンドの完了を待つことなしに他のコマンドを続けて実行
することができ、さらに、前記獲得コマンドで指定され
た前記範囲にアクセスする前に、前記完了ビット・ベク
トルの対応するビットの設定をチェックすることを特徴
とする複数のオブジェクトへのアクセスをインタリーブ
する方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/711,750 US5802582A (en) | 1996-09-10 | 1996-09-10 | Explicit coherence using split-phase controls |
| US08/711750 | 1996-09-10 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH10105462A JPH10105462A (ja) | 1998-04-24 |
| JP3399501B2 true JP3399501B2 (ja) | 2003-04-21 |
Family
ID=24859359
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP24365297A Expired - Fee Related JP3399501B2 (ja) | 1996-09-10 | 1997-09-09 | 分割フェーズ制御を用いる明示的コヒーレンス |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5802582A (ja) |
| JP (1) | JP3399501B2 (ja) |
Families Citing this family (40)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6247025B1 (en) * | 1997-07-17 | 2001-06-12 | International Business Machines Corporation | Locking and unlocking mechanism for controlling concurrent access to objects |
| US6092156A (en) * | 1997-11-05 | 2000-07-18 | Unisys Corporation | System and method for avoiding deadlocks utilizing split lock operations to provide exclusive access to memory during non-atomic operations |
| US6321304B1 (en) * | 1999-01-22 | 2001-11-20 | Apple Computer, Inc. | System and method for deleting read-only head entries in multi-processor computer systems supporting cache coherence with mixed protocols |
| JP3481485B2 (ja) * | 1999-01-28 | 2003-12-22 | エヌイーシーコンピュータテクノ株式会社 | マルチプロセッサシステム |
| US6721739B1 (en) * | 2000-12-05 | 2004-04-13 | Silicon Graphics, Inc. | System and method for maintaining and recovering data consistency across multiple pages |
| US6751636B1 (en) | 2000-12-05 | 2004-06-15 | Silicon Graphics, Inc. | System and method for maintaining and recovering data consistency across multiple instances of a database |
| US6993523B1 (en) | 2000-12-05 | 2006-01-31 | Silicon Graphics, Inc. | System and method for maintaining and recovering data consistency in a data base page |
| EP1255201B1 (en) * | 2001-05-01 | 2009-12-23 | Sun Microsystems, Inc. | Shared memory multiprocessing system employing mixed broadcast snooping and directory based coherency protocols |
| US7222220B2 (en) * | 2001-05-01 | 2007-05-22 | Sun Microsystems, Inc. | Multiprocessing system employing address switches to control mixed broadcast snooping and directory based coherency protocols transparent to active devices |
| US6934720B1 (en) * | 2001-08-04 | 2005-08-23 | Oracle International Corp. | Automatic invalidation of cached data |
| US6973545B2 (en) * | 2002-06-28 | 2005-12-06 | Sun Microsystems, Inc. | System with a directory based coherency protocol and split ownership and access right coherence mechanism |
| EP1376370B1 (en) * | 2002-06-28 | 2017-06-14 | Oracle America, Inc. | Mechanism for starvation avoidance while maintaining cache consistency in computer systems |
| US6970980B2 (en) * | 2002-06-28 | 2005-11-29 | Sun Microsystems, Inc. | System with multicast invalidations and split ownership and access right coherence mechanism |
| US7120756B2 (en) * | 2002-06-28 | 2006-10-10 | Sun Microsystems, Inc. | Computer system including a promise array |
| US6928519B2 (en) * | 2002-06-28 | 2005-08-09 | Sun Microsystems, Inc. | Mechanism for maintaining cache consistency in computer systems |
| US7210006B2 (en) * | 2002-06-28 | 2007-04-24 | Sun Microsystems, Inc. | Computer system supporting read-to-write-back transactions for I/O devices |
| US6970979B2 (en) * | 2002-06-28 | 2005-11-29 | Sun Microsystems, Inc. | System with virtual address networks and split ownership and access right coherence mechanism |
| US7366843B2 (en) * | 2002-06-28 | 2008-04-29 | Sun Microsystems, Inc. | Computer system implementing synchronized broadcast using timestamps |
| US7136980B2 (en) * | 2002-06-28 | 2006-11-14 | Sun Microsystems, Inc. | Computer system implementing synchronized broadcast using skew control and queuing |
| US7363462B2 (en) * | 2003-04-04 | 2008-04-22 | Sun Microsystems, Inc. | Performing virtual to global address translation in processing subsystem |
| US7765381B2 (en) | 2003-04-04 | 2010-07-27 | Oracle America, Inc. | Multi-node system in which home memory subsystem stores global to local address translation information for replicating nodes |
| US7360056B2 (en) | 2003-04-04 | 2008-04-15 | Sun Microsystems, Inc. | Multi-node system in which global address generated by processing subsystem includes global to local translation information |
| US7225298B2 (en) | 2003-04-11 | 2007-05-29 | Sun Microsystems, Inc. | Multi-node computer system in which networks in different nodes implement different conveyance modes |
| US7360029B2 (en) * | 2003-04-11 | 2008-04-15 | Sun Microsystems, Inc. | Multi-node computer system in which interfaces provide data to satisfy coherency transactions when no owning device present in modified global access state node |
| US7529893B2 (en) * | 2003-04-11 | 2009-05-05 | Sun Microsystems, Inc. | Multi-node system with split ownership and access right coherence mechanism |
| GB2416416B (en) * | 2003-04-11 | 2006-11-22 | Sun Microsystems Inc | Multi-node computer system implementing global access state dependent transactions |
| US7945738B2 (en) | 2003-04-11 | 2011-05-17 | Oracle America, Inc. | Multi-node computer system employing a reporting mechanism for multi-node transactions |
| US8024526B2 (en) * | 2003-04-11 | 2011-09-20 | Oracle America, Inc. | Multi-node system with global access states |
| GB2416417B (en) * | 2003-04-11 | 2006-12-13 | Sun Microsystems Inc | Multi-node computer system with proxy transaction to read data from a non-owning memory device |
| US7814278B2 (en) | 2003-04-11 | 2010-10-12 | Oracle America, Inc. | Multi-node system with response information in memory |
| US7133977B2 (en) * | 2003-06-13 | 2006-11-07 | Microsoft Corporation | Scalable rundown protection for object lifetime management |
| US7373462B2 (en) * | 2005-03-29 | 2008-05-13 | International Business Machines Corporation | Snoop filter for filtering snoop requests |
| US7954002B2 (en) * | 2008-08-07 | 2011-05-31 | Telefonaktiebolaget L M Ericsson (Publ) | Systems and methods for bulk release of resources associated with node failure |
| US8145817B2 (en) * | 2009-04-28 | 2012-03-27 | Microsoft Corporation | Reader/writer lock with reduced cache contention |
| US8296524B2 (en) * | 2009-06-26 | 2012-10-23 | Oracle America, Inc. | Supporting efficient spin-locks and other types of synchronization in a cache-coherent multiprocessor system |
| US8640005B2 (en) * | 2010-05-21 | 2014-01-28 | Intel Corporation | Method and apparatus for using cache memory in a system that supports a low power state |
| US9288784B2 (en) * | 2012-05-18 | 2016-03-15 | Bose Corporation | Controlling communication mode changes in a communication system |
| GB2529148B (en) | 2014-08-04 | 2020-05-27 | Advanced Risc Mach Ltd | Write operations to non-volatile memory |
| US10846230B2 (en) | 2016-12-12 | 2020-11-24 | Intel Corporation | Methods and systems for invalidating memory ranges in fabric-based architectures |
| US10621103B2 (en) | 2017-12-05 | 2020-04-14 | Arm Limited | Apparatus and method for handling write operations |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5301290A (en) * | 1990-03-14 | 1994-04-05 | International Business Machines Corporation | Method for minimizing lock processing while ensuring consistency among pages common to local processor caches and a shared external store |
| JP2533266B2 (ja) * | 1991-06-14 | 1996-09-11 | インターナショナル・ビジネス・マシーンズ・コーポレイション | 共用デ―タシステムにおけるデ―タ資源のロッキング方法及びシステム間のデ―タロック管理方法 |
-
1996
- 1996-09-10 US US08/711,750 patent/US5802582A/en not_active Expired - Fee Related
-
1997
- 1997-09-09 JP JP24365297A patent/JP3399501B2/ja not_active Expired - Fee Related
Non-Patent Citations (2)
| Title |
|---|
| Ｓａｎｄｈｕ Ｈ．Ｓ．，Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｄｙｎａｍｉｃ Ｓｏｆｔｗａｒｅ Ｃａｃｈｅ Ｃｏｈｅｒｅｎｃｅ，Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，米国，Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１９９５年，Ｖｏｌ．２９，ｐ．１４２−１５７ |
| Ｓａｎｄｈｕ Ｈ．Ｓ．ｅｔ ａｌ．，Ｔｈｅ Ｓｈａｒｅｄ Ｒｅｇｉｏｎｓ Ａｐｐｒｏａｃｈ ｔｏ Ｓｏｆｔｏｗａｒｅ Ｃａｃｈｅ Ｃｏｈｅｒｅｎｃｅ ｏｎ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ，ＡＣＭ ＳＩＧＰＬＡＮ Ｎｏｔｉｃｅｓ，米国，ＡＣＭ，１９９３年，Ｖｏｌ．２８，Ｎｏ．７，ｐ．２２９−２３８ |
Also Published As
| Publication number | Publication date |
|---|---|
| US5802582A (en) | 1998-09-01 |
| JPH10105462A (ja) | 1998-04-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3399501B2 (ja) | 分割フェーズ制御を用いる明示的コヒーレンス | |
| JP2603369B2 (ja) | ローカルキャッシュに共通のページ間の一貫性を確保する方法 | |
| US6088769A (en) | Multiprocessor cache coherence directed by combined local and global tables | |
| US6625698B2 (en) | Method and apparatus for controlling memory storage locks based on cache line ownership | |
| US8281079B2 (en) | Multi-processor system receiving input from a pre-fetch buffer | |
| EP0349122B1 (en) | Method and apparatus for filtering invalidate requests | |
| US20070204111A1 (en) | Method and apparatus for reducing memory latency in a cache coherent multi-node architecture | |
| US6330643B1 (en) | Cache coherency protocols with global and local posted operations | |
| US7765381B2 (en) | Multi-node system in which home memory subsystem stores global to local address translation information for replicating nodes | |
| US5692149A (en) | Block replacement method in cache only memory architecture multiprocessor | |
| JP3748774B2 (ja) | キャッシュコヒーレンス共用ディスクコンピュータシステムにおけるｉ／ｏ転送 | |
| US6032228A (en) | Flexible cache-coherency mechanism | |
| KR20170069149A (ko) | 데이터 처리 시스템의 캐시 일관성을 위한 스누프 필터 | |
| JPH05210637A (ja) | 同時アクセス管理方法 | |
| JP2004505346A (ja) | 多重プロセッサアーキテクチャのためのキャッシュコヒーレンシシステムおよび方法 | |
| JPH0762836B2 (ja) | データ・アクセス管理装置および方法 | |
| JP2009064471A (ja) | マルチプロセッサ・システムにおけるキャッシュ・コヒーレンスにおいて用いるフォワード状態 | |
| JP2005519391A (ja) | 共有ベクトルの増加を伴わないｄｓｍマルチプロセッサシステムにおけるキャッシュコヒーレンスのための方法およびシステム | |
| JP2005234854A (ja) | マルチプロセッサシステム | |
| JP2004054931A (ja) | 分散メモリマルチプロセッサシステムにおけるメモリ移行のためのシステムおよび方法 | |
| US20050080998A1 (en) | Method and apparatus for coherent memory structure of heterogeneous processor systems | |
| WO2004091136A2 (en) | Multi-node system in which global address generated by processing subsystem includes global to local translation information | |
| US7143245B2 (en) | System and method for read migratory optimization in a cache coherency protocol | |
| EP1224553B1 (en) | Multi-processor system and method of accessing data therein | |
| CN111273860A (zh) | 一种基于网络和页粒度管理的分布式内存管理方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |