(57)【特許請求の範囲】
【請求項１】
複数のプロセッサノードを含むマルチプロセッサシステムにおいて、データブロックの１組の予測されるリーダを決定する方法であって、該複数のプロセッサノードがネットワークを通じて互いに接続され、該複数のプロセッサノードの各々がメモリ及び該メモリに接続されたプロセッサを有し、該各プロセッサノードのメモリにはデータブロックが記録され、
該データブロックの１組の予測されるリーダを決定する方法は、
所与のプロセッサノードのプロセッサが、他のプロセッサノードからの書込み要求を受ける該所与のプロセッサノードのデータブロックの１組の現在のリーダを決定するステップであって、該１組の現在のリーダは、該書込み要求を受ける所与のプロセッサノードの最新に更新されたデータブロックのコピーを有するリーダを含み、該１組の現在のリーダは、該所与のプロセッサノードの該データブロックに関連するグローバル履歴に記録される、ステップと、
該所与のプロセッサノードが、該データブロックに関連する該グローバル履歴に記録されている少なくとも１組の付加的なリーダと該１組の現在のリーダとに基づいて、合併関数、交わり関数あるいはパターンベースの関数を用いることで、１組の予測されるリーダを生成するステップであって、該１組の予測されるリーダは、更新されるべき該データブロックのコピーを有するリーダを含み、該少なくとも１組の付加的なリーダは、該所与のプロセッサノードの該データブロックへ以前にアクセスしていたリーダを含む、ステップとを含む方法。
【請求項２】
請求項１に記載の方法において、該グローバル履歴が、該所与のプロセッサノードによって処理される複数組の以前のリーダからなり、該複数組の以前のリーダの全数は、該１組の予測されるリーダの生成に関連する指定された履歴の深さに対応する方法。
【請求項３】
請求項１に記載の方法において、該マルチプロセッサシステム内の各リーダが、複数のデータブロックそれぞれのためのアクセスされるビットを保持し、該アクセスされるビットが、特定のリーダが所与のデータブロックを実際に読み出したか否かを指定するものである方法。
【請求項４】
請求項１に記載の方法において、該所与のプロセッサノードの該データブロックにおいて要求される書込みが完了した後に、結果として生成されたデータブロックが該１組の予測されるリーダの各リーダに送信される方法。
【請求項５】
請求項１に記載の方法において、該生成するステップが、さらに、該１組の予測されるリーダを決定するために、該リーダのうちの１つあるいは複数のリーダに関連するキャッシュアドレス情報の少なくともサブセットとともに、該グローバル履歴に関する情報を利用する処理を含む方法。
【請求項６】
請求項１に記載の方法において、該生成するステップが、さらに、該１組の予測されるリーダを決定するために、該リーダのうちの１つあるいは複数のリーダに関連するプロセッサノード情報とともに、該グローバル履歴に関する情報を利用する処理を含む方法。
【請求項７】
請求項１に記載の方法において、該生成するステップが、さらに、該１組の予測されるリーダを決定するために、該リーダのうちの１つあるいは複数のリーダに関連するプログラムカウンタ情報とともに、該グローバル履歴に関する情報を利用する処理を含む方法。
【請求項８】
複数のプロセッサノードを含むマルチプロセッサシステムにおいて、データブロックの１組の予測されるリーダを決定するプロセッサノードであって、該複数のプロセッサノードがネットワークを通じて互いに接続され、該複数のプロセッサノードの各々がメモリ及び該メモリに接続されたプロセッサを有し、該各プロセッサノードのメモリにはデータブロックが記録され、
該データブロックの１組の予測されるリーダを決定するプロセッサノードは、
他のプロセッサノードからの書込み要求を受ける該プロセッサノードのデータブロックの１組の現在のリーダを決定する手段であって、該１組の現在のリーダは、該書込み要求を受ける該プロセッサノードの最新に更新されたデータブロックのコピーを有するリーダを含み、該１組の現在のリーダは、該プロセッサノードの該データブロックに関連するグローバル履歴に記録される、手段と、
該データブロックに関連する該グローバル履歴に記録されている少なくとも１組の付加的なリーダと該１組の現在のリーダとに基づいて、合併関数、交わり関数あるいはパターンベースの関数を用いることで、１組の予測されるリーダを生成する手段であって、該１組の予測されるリーダは、更新されるべき該データブロックのコピーを有するリーダを含み、該少なくとも１組の付加的なリーダは、該プロセッサノードの該データブロックへ以前にアクセスしていたリーダを含む、手段とを含むプロセッサノード。
【請求項９】
複数のプロセッサノードを含み、データブロックの１組の予測されるリーダを決定するマルチプロセッサシステムであって、該複数のプロセッサノードがネットワークを通じて互いに接続され、該複数のプロセッサノードの各々がメモリ及び該メモリに接続されたプロセッサを有し、該各プロセッサノードのメモリにはデータブロックが記録され、
該マルチプロセッサシステムは、
所与のプロセッサノードのプロセッサは、他のプロセッサノードからの書込み要求を受ける該所与のプロセッサノードのデータブロックの１組の現在のリーダを決定し、該１組の現在のリーダは、該書込み要求を受ける所与のプロセッサノードの最新に更新されたデータブロックのコピーを有するリーダを含み、該１組の現在のリーダは、該所与のプロセッサノードの該データブロックに関連するグローバル履歴に記録され、
該所与のプロセッサノードは、該データブロックに関連する該グローバル履歴に記録されている少なくとも１組の付加的なリーダと該１組の現在のリーダとに基づいて、合併関数、交わり関数あるいはパターンベースの関数を用いることで、１組の予測されるリーダを生成し、該１組の予測されるリーダは、更新されるべき該データブロックのコピーを有するリーダを含み、該少なくとも１組の付加的なリーダは、該所与のプロセッサノードの該データブロックへ以前にアクセスしていたリーダを含む、ことを特徴とするマルチプロセッサシステム。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明は全般にマルチプロセッサコンピュータ、および多数のプロセッサを備える他のタイプのプロセッシングシステムに関し、より詳細には、そのようなシステムにおいて用いるのに適したメモリ予測技術(prediction technique)に関する。
【０００２】
【発明の背景】
共有メモリマルチプロセッサシステム(shared-memory multiprocessor system)では、ユーザには、全てのプロセッサが、１つの共有メモリの格納状態を読み出し、かつ変更するように見える。そのようなシステムを実装する際の大きな問題点、特に、そのようなシステムが分散形システムである場合の問題点は、１つのプロセッサから別のプロセッサに値が伝搬し、実際の値が１つのプロセッサの近くで作成されても、システム内の多くの他のプロセッサによって用いられる場合があることである。その実装形態が、所与のプログラムの共有パターンを正確に予測することができたなら、分散形マルチプロセッサシステムのプロセッサノードは、その時間の多くをコンピューティングに費やすことができ、リモートの位置から値が取り込まれるのを待つことにあまり時間をかけずに済むであろう。ノンブロッキングキャッシュ(non-blocking cache)およびアウトオブオーダ命令実行(out-of-order instruction execution)のようなプロセッサ機構が開発されているにもかかわらず、分散形共有メモリシステムの比較的長いアクセス待ち時間は依然として、性能に対する重大な障害である。
【０００３】
予測技術を用いて、１つの作成場所からその予測される使用場所まで、できるだけ早期にデータを移動させるように試みることにより、分散形共有メモリシステム(distributed shared-memory system)内のアクセス待ち時間を低減している。これらの予測技術は典型的には、主に正確な動作に関連し、性能にも関連する通常の共有メモリコヒーレンスプロトコル(shared-memory coherence protocol)を補う。分散形共有メモリシステムでは、典型的にはディレクトリベース(directory-based)のコヒーレンスプロトコルが、プロセッサキャッシュのコヒーレンスを維持し、プロセッサノード間でデータを転送する。本質的には、コヒーレンスプロトコルはシステム内の全ての通信を実行する。コヒーレンスプロトコルは、データブロックが書き込まれたときには必ず、データブロックの共有コピーを無効にするか、更新するかのいずれかを行うことができる。更新処理は、生産側ノード(producer node)から消費側ノード(consumer node)にデータを転送することを含むが、データ転送の有用性を判定するためのフィードバック機構を提供しない。無効化処理(invalidation)は、無効にされたリーダがそのデータを使用していなければならないという点で、自然のフィードバック機構を提供するが、無効化処理は、宛先にデータを転送するための手段を提供しない。
【０００４】
S.S. MukherjeeおよびM.D. Hillの「Using Prediction to Accelerate Coherence Protocols」（Proceedings of the 25th Annual International Symposium on Computer Architecture (ISCA), June-July 1998）に記載される従来の予測アプローチは、コヒーレンスメッセージをトラッキングし、かつ予測するために、ディレクトリにおけるアドレスベースの２段予測器(2-level predictor)と、マルチプロセッサシステムのプロセッサノードのキャッシュとを用いる。A.laiおよびB. Falsafiの「Memory Sharing Predictor: The Key to a Speculative Coherent DSM」（Proceedings of the 26th Annual ISCA, May 1999）は、種々のノードからのメッセージをビットマップに融合することにより、これらの２段予測器が少ない空間を用いるために如何に変更できるかを記載しており、データの読出しを加速するために、その変更された予測器を如何に用いることができるかを示す。S. KaxirasおよびJ.R. Goodmanの「Improving CC-NUMA Performance Using Instruction-Based Prediction」（Proceedings of the 5th Annual IEEE Symposium on High- Performance Computer Architecture (HPCA), January 1999）に記載される別の１組の知られている予測技術は、移動共有（migratory sharing）、広域共有（wide sharing）および生産側−消費側共有のための命令ベースの予測を提供する。静的な命令はデータブロックからあまり離れていないため、命令ベース予測器は共有パターンを捕捉するためにほとんど空間を必要としない。
【０００５】
上記の認定された予測技術によって提供される進歩にもかかわらず、依然として、アクセス待ち時間をさらに低減し、それにより共有メモリマルチプロセッサシステムの実装を容易にするように、さらに改善する必要性がある。
【発明の概要】
【０００６】
本発明の目的は、共有メモリマルチプロセッサシステムにおいて、書込み要求を受けたデータブロックの１組の予測されるリーダを決定するための改善された技術を提供することである。
【０００７】
本発明の一実施例によれば、データブロックの現在の１組の予測されるリーダが決定され、その後、１組の予測されるリーダが、その現在の１組のリーダと、データブロックに関連するディレクトリのグローバル履歴(global history)の少なくとも一部を表す少なくとも１つの付加的な１組のリーダとに基づいて生成される。１つの実現可能な実装形態では、１組の予測されるリーダは、現在の１組のリーダと、付加的な１組あるいは複数組のリーダとに、ある関数を適用することにより生成される。その関数には、例えば、合併関数（union function）、交わり関数（intersection function）あるいはパターンベースの関数(pattern-based function)を用いることができ、ディレクトリおよびデータブロックは、マルチプロセッサシステムの特定のプロセッサノードに関連するメモリの要素の場合がある。
【０００８】
ディレクトリのグローバル履歴は、そのディレクトリによって処理された多数組の以前のリーダ(multiple sets of previous readers)を含み、複数組の以前のリーダの全数は、１組の予測されるリーダの生成に関連する指定された履歴の深さに対応する。グローバル履歴は、例えば、指定された履歴の深さに対応する多数の記憶場所を有するシフトレジスタに保持される場合がある。履歴の深さは２より大きい値、例えは４として選択されることが好ましい。
【０００９】
動作時に、書込み要求を受けたデータブロックに関連するディレクトリあるいは他のプロセッサノード要素は、現在の１組のリーダ内の各リーダに無効化要求(invalidation requestを送信し、現在の１組のリーダの各リーダから無効化確認応答を受信すると、書込み要求を生成したライタにデータブロックの有効なコピーを送信する。システム内の各リーダは、多数のデータブロックそれぞれのためのアクセスされるビットを保持することができ、所与のデータブロックのための特定のリーダのアクセスされるビットは、特定のリーダが所与のデータブロックを実際に読み出したか否かを指示する。そのアクセスされるビットの情報は、無効化確認応答とともに、特定のリーダによってディレクトリに送信される場合がある。データブロックにおいて要求される書込みが完了した後に、結果として生成されたデータブロックは、１組の予測されるリーダ内の各リーダに送信される。
【００１０】
本発明の別の実施例によれば、上記の関数は、動的に選択される場合がある。例えば、その関数は、マルチプロセッサシステムにおいて実行される多数のプログラムがそれぞれ独立して適用される関数を決定し、１組の予測されるリーダを決定するように、プログラム毎に選択することができる。別の例としては、その関数は、マルチプロセッサシステム上で実行される所与のプログラムによる実行時に、プログラム制御下で選択される場合がある。さらに別の例としては、その関数は、適用される関数が、それぞれ多数のデータブロックを含む、多数のメモリページそれぞれに対して独立して決定できるように、ページ毎に選択される場合がある。さらに別の例では、その関数は、ネットワーク利用に関する情報の少なくとも一部に基づいて選択される場合がある。これらの情報および他のタイプの情報の種々の組み合わせが、上記の関数の動的な選択において用いられる場合もある。
【００１１】
本発明による予測プロセスは、上記のディレクトリ情報とともに、キャッシュアドレス情報の指定されたサブセット、プロセッサノード識別情報、あるいはプログラムカウンタ情報のような付加情報を用いる場合がある。
【００１２】
本発明の予測技術は、従来の技術と比べて、誤って肯定的な結果を出すことが少なく、かつ誤って否定的な結果を出すことが少ないという両方の点から見て、改善された予測精度を提供する。
【００１３】
本発明のこれらの特徴および利点、および他の特徴および利点は、添付の図面および以下の詳細な説明から、さらに明らかになるであろう。
【００１４】
【発明の詳細な記述】
本明細書において、本発明は、典型的な分散形共有メモリマルチプロセッサシステムとともに例示されるであろう。しかしながら、本発明は、より一般的には、ディレクトリベース予測を使用することにより改善された性能を提供することが望まれる、任意の共有メモリマルチプロセッサシステムに適用することができることを理解されたい。本明細書において用いられる用語「マルチプロセッサ」は、２つもしくはそれより多くのプロセッサを用いて、検索された命令が実行される任意の装置を含むことを意図している。本発明による典型的なプロセッサは、例えば、マイクロプロセッサ、中央演算装置（Ｃentral Ｐrocessing Ｕnit：ＣＰＵ）、超長命令語（Ｖery Ｌong Ｉnstruction Ｗord：ＶＬＩＷ）プロセッサ、単一命令発行プロセッサ（single-issue processor）、複数命令発行プロセッサ（multi-issue processor）、デジタルシグナルプロセッサ、特定用途向け集積回路（Ａpplication-Ｓpecific Ｉntegrated Ｃircuit：ＡＳＩＣ）、パーソナルコンピュータ、メインフレームコンピュータ、ネットワークコンピュータ、ワークステーションおよびサーバ、ならびに他のタイプのデータプロセッシング装置、およびこれらの装置あるいは他の装置の一部または組み合わせを含む場合がある。
【００１５】
図１および図２は、分散形共有メモリマルチプロセッサシステム１００の、それぞ例示的な読出しおよび書込み要求の処理を示す。システム１００は、本発明のディレクトリベース予測(directory-based prediction)が実施される場合があるシステムのタイプの一例である。システム１００はノードＡ、ＢおよびＣを含み、そのノードはそれぞれ、対応するネットワークインターフェース（ＮetowrkＩnterface：ＮＩ）１０４Ａ、１０４Ｂおよび１０４Ｃを介して相互接続ネットワーク１２０に接続される。ノードＡ、ＢおよびＣはそれぞれ、図のように構成される、プロセッサ１０６Ａ、１０６Ｂおよび１０６Ｃと、メモリ１０８Ａ、１０８Ｂおよび１０８Ｃと、バス１１０Ａ、１１０Ｂおよび１１０Ｃとを含む。システム１００の所与のノードｉ（ｉ＝Ａ、Ｂ、Ｃ）内では、プロセッサ１０６ｉ、メモリ１０８ｉおよびネットワークインターフェース１０４ｉがそれぞれ、対応するバス１１０ｉに接続され、そのバス上で通信を行う。
【００１６】
システム１００内の各プロセッサ１０６ｉには、１組のキャッシュＬ１およびＬ２が関連し、各メモリ１０８ｉには、ディレクトリおよびキャッシュＬ３が関連する。メモリ１０８ｉはそれぞれ、対応する固有のディレクトリによって管理される。メモリ１０８ｉあるいはその一部は、データブロック、あるいは単にブロックと呼ばれる。システム１００内には多数のディレクトリが存在するが、この例示的な実施例の各ブロックは、それらのうちの１つのみによって管理される。リーダ(reader)あるいはライタ(writer)となるはずの装置が、ブロックの最新のコピーを持たない場合には、対応するディレクトリに、ブロックの最新のものを見つけるように要求する。そのディレクトリは、要求に応答するために、そのブロックの１つあるいは複数の現在のコピーを無効にしなければならない場合がある。
【００１７】
また図１には、ノードＡのプロセッサ１０６ＡがノードＢのメモリ１０８Ｂからデータを読み出す読出し動作の一例が示される。この動作の一部として、読出し要求（１）が、ノードＡからノードＢに進み、応答（２）がノードＢからノードＡに返送される。ノードＡは、そのローカルのキャッシュ階層、すなわちキャッシュＬ１、Ｌ２、Ｌ３内にデータをキャッシュする。ノードＢ内のディレクトリは、ノードＡがデータのコピーを有することについて指示を格納する。他のノードは、同じようにして、ノードＢからデータを読み出す。
【００１８】
本明細書において用いられる用語「リーダ(reader)」および「ライタ(writer)」は、限定はしないが、所与のプロセッサノードあるいはその関連するプロセッサ、およびプロセッサノードあるいはその関連するプロセッサの要素および部分を含むことを意図していることに留意されたい。
【００１９】
図２は、ノードＣのプロセッサ１０６Ｃが、ノードＢのメモリ１０８Ｂに存在している同じデータを書き込む書込み動作を示す。この動作の一部として、書込み要求（１）がノードＣからノードＢに進む。ノードＢのディレクトリは、ノードＡがそのデータのコピーを持っていることを認識しているので、ノードＡに無効化要求（２）を送信する。ノードＡは、そのデータのコピーを無効化したことに関する確認応答（３）を送信する。その後、ノードＢは、システム内にコピーが存在しないので、そのデータ（４）を書込みを行うためのノードＣに送信する。
【００２０】
したがって、システム１００内の所与のメモリブロックは、１つのプロセッサによって書き込みが行われる段階と、１つあるいは複数のプロセッサによって読出しが行われる段階との間を交互に行うものと考えることができる。所与のブロックに関連するディレクトリは、これらの交互に行われる段階を管理し、ブロックのうちの一致するものを常時保持する。
【００２１】
図１および図２に示されるキャッシュの特定の構成およびキャッシュレベルは単なる例示であり、任意の実施例に本発明の範囲を限定するものと解釈されるべきではないことに留意されたい。本発明は、多種多様なキャッシュアーキテクチャおよびマルチプロセッサシステム構成を用いて実施することができる。
【００２２】
図３は、１、２、３、４および５で示される５つのノードを有するシステム内の１つのブロックのためのこれらの交互に実施される段階の一例を示す。図面の左側は、１つのブロックに関係する読出しおよび書込みイベントの生のシーケンスを示しており、図面の右側は、上記の段階の概要を示している。この例から明らかなように、多数のリーダが、あるブロックの最も新しく生成されたものを検査することが一般に安全である。
【００２３】
例示的な実施例における本発明は、書込み要求がライタから、あるブロックに関連するディレクトリに進むとき、そのブロックの次の１組のリーダを予測するディレクトリベース予測機構を提供する。その機構は、ライタによって生成される値の同じような１組のリーダを予測し、ライタが書込みを終了した後に、この予測を用いて、全ての予測されるリーダにそのデータを転送する。システム内のブロックのための個別の履歴を保持するために、ブロック間、あるいは命令間を区別する従来の予測器とは異なり、本発明の予測機構は、ディレクトリによって供給される多数のブロックのための多数組のリーダを互いに組み合わせる。この情報を本明細書では、ディレクトリのグローバル履歴(global history of the directory)と呼ぶ。
【００２４】
以下に図４とともに記載されることになる例示的な実施例の実装形態の例では、４の履歴の深さが用いられる。すなわち、所与のブロックにおける現在の書込み動作に対して生成される予測される１組のリーダは、そのブロックの現在の１組のリーダ、および予測器シフトレジスタに格納される他の３つの最新の組のリーダの関数として決定される。
【００２５】
図４は、本発明の例示的な実施例におけるディレクトリベース予測器の動作の一例を示す。この例では、メモリおよびディレクトリ１２０に関連するデータブロックＸのための書込み要求が受信される。データブロックＸの現在のリーダは、ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ、ｉ、ｊ、ｋ、ｌ、ｍ等で示されるノードを含む、マルチプロセッサシステムの１組のノード｛ａ、ｂ、ｃ｝である。各ノードは、図１および図２とともに例示されたようなマルチプロセッサの１つのノードを表す場合がある。この例における予測器は、以下に記載されるように、シフトレジスタ１２２を用いる。
【００２６】
図５は、図４の例のディレクトリベース予測器の全体的なプロセッシング動作の流れ図である。その全体的な動作は、最初に図５を参照して記載され、その後、図４の例にその全体的な動作を適用する実施例が詳細に記載されるであろう。
【００２７】
図５のステップ２００では、ライタは、書き込まれることになるブロックのディレクトリに書込み要求メッセージを送信する。ステップ２０２では、ディレクトリが現在のリーダを無効にする。その後、ステップ２０４および２０６が、各リーダによって実行される。ステップ２０４では、潜在的なリーダに対応する所与のノードが、ディレクトリから無効化要求を受信する。ステップ２０６では、ノードが、無効化要求の確認応答とともに「アクセスされるビット」を返送する。
【００２８】
ステップ２０８に示されるように、ディレクトリは、リーダからの無効化確認応答を待つ。１組の該当するリーダが、返送されたアクセスされるビットが設定される１組の無効化されたノードとして決定される。ステップ２１０では、ディレクトリは、１組の該当するリーダを識別する情報を予測器に供給する。
【００２９】
その後、予測器は、該当する１組のリーダをシフトレジスタに加えて（ステップ２１２）、シフトレジスタ内の最も古い１組の以前のリーダを破棄し（ステップ２１４）、交わり演算あるいは合併演算を用いてその組の関数を予測し（ステップ２１６）、その予測をライタに送信する（ステップ２１８）。
【００３０】
ステップ２２０では、ディレクトリは、ブロックの有効なコピーをライタに送信する。このコピーは、ステップ２１８の予測とともにライタに送信される場合がある。ステップ２２２では、ライタが書込み動作を終了するまで待機する。書込み動作が完了した後、ライタは、ステップ２２４に示されるように、その予測の情報を用いて、新しいブロックを予測される各リーダに転送する。
【００３１】
新しいブロックを予測される各リーダに転送するための適当な時間を決定するのに適した技術は、例えば、S. Kaxirasによる「Identification and Optimization of Sharing Patterns for Scalable Shared-Memory Multiprocessors」（PhD. Thesis, Computer Science, University of Wisconsin-Madison, 1998）および上で引用したA.laiおよびB. Falsafiの「Memory Sharing Predictor: The Key to a Speculative Coherent DSM」（Proceedings of the 26th Annual ISCA, May 1999）に記載されている。
【００３２】
図５のステップ２１６の合併関数あるいは交わり関数の選択は、一般に、データ転送の所望の積極性の度合いに依存する。例えば、広帯域幅のシステムでは、合併関数に関連する、より積極的なデータ転送が適している場合があり、一方、狭帯域幅のシステムの場合、交わり関数の方が適している場合がある。これらの関数は一例として与えただけであり、他のタイプの関数を用いて本発明を実施することができることに留意されたい。別の例として、本発明とともにパターンベースの関数を用いることができる。そのような関数は、例えば、T. YehおよびY. Pattによる「Two-level Adaptive Branch Prediction」（Proceedings of the24th Annual ACM/IEEE International Symposium and Workshop on Microarchitecture, Los Alamitos, CA, November 1991）にさらに詳細に記載されており、参照して本明細書に援用する。
【００３３】
ステップ２１６の合併関数、交わり関数あるいは他の関数の間の選択は動的に行うことができる。例えば、その選択は、各プログラムが自らの動作モードを設定できるように、プログラム毎に行うことができる。別の例としては、関数の選択は、プログラムが必要に応じて実行時に動作モードを変更できるように、プログラムの制御下で実施される場合がある。別法では、その選択は、自らのモードを有する多数のデータブロックからなる場合がある、各メモリページについて、ページ毎に行うこともできるであろう。この場合には、オペレーティングシステムは、予測器に、種々のページの動作モードについて通知する場合がある。さらに別の例としては、関数の選択は、ネットワーク利用、例えば、合併関数を必要とする低ネットワーク利用、および交わり関数を必要とする高ネットワーク利用に応じて行うことができる。この場合には、ネットワークモニタ装置を用いて、予測機構にフィードバックを供給する場合がある。
【００３４】
再び図４の例を参照すると、データブロックＸに対する書込み要求が受信されるとき、現在のリーダは、｛ａ、ｂ、ｃ｝の組内のプロセッサである。予測器シフトレジスタ１２２は、図のように１だけシフトされ、｛ａ、ｂ、ｃ｝の組は、スロット０で示される最上位のスロットに組み込まれる。シフトされた結果として、スロット１、２および３はそれぞれ｛ａ、ｃ、ｅ、ｆ、ｇ｝、｛ａ、ｃ、ｄ｝および｛ａ、ｈ、ｉ、ｃ｝を含み、｛ｋ、ｌ、ｍ｝の組は、シフトレジスタから破棄される。所与の時点におけるシフトレジスタ１２２の現在の内容は、対応するディレクトリのグローバル履歴を表す。ディレクトリは、ノードａ、ｂおよびｃに無効化要求を送信することによりリーダを無効にし、無効化要求の確認応答を待ち、その後、要求するライタにデータブロックＸの有効なコピーを送信する。
【００３５】
予測器は、図５のステップ２０６により、上記の要因のうちの１つあるいは複数の要因に基づいて合併あるいは交わりを選択し、シフトレジスタ１２２内の組の合併あるいは交わりを決定する。シフトレジスタ内の組の合併は｛ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈ、ｉ｝の組であり、一方、シフトレジスタ内の組の交わりは｛ａ、ｃ｝の組である。いずれの場合でも、その結果は、予測器によってライタに送信される１組の予測されるリーダである。データブロックにおける書込み動作が完了した後、ライタは、新しいデータブロックを、予測される各リーダに転送する。データ転送の起動は、タイマによって、あるいはどのデータブロックが書き込まれるかに関係なく、ディレクトリに対する次の書込みによって、あるいはデータブロックに対する次の読出しによって、あるいは他の適切な技術によって行うことができる。データ転送は、ディレクトリがライタからデータのコピーを取り込み、それを予測されるリーダノードに送信することにより、実施することができる。
【００３６】
図４の例の予測器は、４の履歴の深さを用いる、すなわちシフトレジスタ１２２は所与のデータブロックの場合に、直前の４つの組のリーダを格納するが、本発明は、５以上あるいは３以下の履歴の深さを含む、他の履歴深さを用いて実施することができる。従来の予測器は一般に、２以下の履歴の深さを用いる。
【００３７】
上記の予測機構への正確なフィードバックを供給するために、各リーダは一般に、予測される読出しと実際の読出しとの間を区別できなければならない。ライタがあるキャッシュブロックへの排他的なアクセスを得るとき、本発明によるマルチプロセッサシステムは、そのブロックの将来の組のリーダを予測し、その後、書込みが完了した後に、ブロックのコピーが確実にそれらの予測されるリーダに転送されるようにする。フィーダバックループを閉じるために、システムは、それらの予測されるリーダの多くが、そのブロックを実際に如何に用いたかを知らなければならない。これがその場合であるか否かを見極めるために、システム内の各リーダは、ローカルにキャッシュされた各ラインに対して、上記の「アクセスされるビット(accessed bit)」を保持する場合がある。このアクセスされるビットは、キャッシュが書き込まれるときではなく、キャッシュが読み出されるときに設定されることを除いて、仮想メモリシステム内でページングするために保持される、いわゆる「ダーティビット(dirty bit)」に類似である。またアクセスされるビットは、キャッシュブロック細分性（granularity）において保持されるが、一方、ダーティビットは典型的にはページ細分性において保持される。次の無効化時に、各リーダは、アクセスされるビットの情報を無効化確認応答に載せて搬送する。その後、システムは、アクセスされるビットを用いて、次の予測のためにその状態を更新する。
【００３８】
ディレクトリによって実行されるか、そうでなければ実装されるものとして示される、本明細書で記載されるプロセッシング動作は、プログラム制御下のプロセッサのような、プロセッサノードの関連する要素によって実行されるか、あるいはそうでなければ実装される場合がある。
【００３９】
本発明の別の実施例では、ディレクトリ情報は、さらに動作を改善するために、他の情報によって補足されることができる。例えば、ディレクトリ情報は、キャッシュ−ブロック−アドレス情報(cache-block-address information)の指定されたサブセットで補足されることができる。そのような構成は、より高い予測精度を達成しつつ、従来のアドレスベース予測技術より少ない情報しか用いないことが有利である。本発明の他の実施例では、ディレクトリ情報は、キャッシュアドレス情報のサブセットを用いる場合も用いない場合もあり、プロセッサノードおよびプログラムカウンタ情報のような他のタイプの情報を組み合わせることができる。例えば、該発明は、所与の書込み要求の場合に１組の予測されるリーダを決定するプロセスにおいて、ディレクトリ、アドレス、プロセッサノードおよびプログラムカウンタ情報の種々の組み合わせを用いることができる。
【００４０】
本明細書で用いられる用語として、ディレクトリの「グローバル履歴(global history)」は、ディレクトリ情報単体に基づく履歴だけでなく、ディレクトリ情報と、アドレス、プロセッサノードあるいはプログラムカウンタ情報のような、最大限に利用可能な付加情報量より少ない量の付加情報とを含む履歴も含むことを意図している。例えば、グローバル履歴は、少数のアドレスビット、すなわち完全な１組の利用可能なアドレスビットより少ないアドレスビットの量で補足されたディレクトリ情報を含む場合がある。
【００４１】
表１ないし表６は、本発明、および対応する性能シミュレーション結果による、予測の例を掲載する６個一組の表を示す。図示される予測器は、ディレクトリ（ｄｉｒ）、アドレス（ａｄｄ）、プロセッサノード（ｐｉｄ）およびプログラムカウンタ（ｐｃ）情報の種々の組み合わせによる。予測器名は、「予測−関数（指標）depth」（depth＝深さ）の形をとり、予測−関数は予測器を更新するために用いられる関数であり、指標は予測器によって用いられるディレクトリ、アドレス、プロセッサノードおよびプログラムカウンタ情報の特定の組み合わせを示し、深さは履歴の深さである。アドレス（ａｄｄ）あるいはプログラムカウンタ（ｐｃ）情報の場合には、対応する識別子は、対応する数の情報のビットを示す添字を含む。
【００４２】
また、表１ないし表６に示される予測器は、用いられる特定の更新機構を示すために、直接型あるいは転送型のいずれかとしても分類される。直接更新機構では、データブロックが書き込まれるたびに、１組の無効化された実際のリーダを履歴として用いて、新しい予測を生成する。転送更新機構では、ライタが別のノードに関連する１組のリーダを無効にするとき、正確なライタによって用いることができるように、この履歴を適当な予測器エントリに転送する。したがって、転送型の更新は、無効化されたリーダが特定のライタに関連付けられることができるように、各データブロックのための最後のライタ情報を必要とする。表１、表２および表３は、直接更新機構を用いる予測器を掲載しており、一方、表４、表５および表６は、転送更新機構を用いる予測器を掲載する。
【００４３】
例として、表６の予測器union（pid＋dir＋add４）４は、プロセッサ番号、ディレクトリノード、および４ビットのデータブロックアドレスを用いてその予測状態に指標を付け、最後の２つの共有ビットマップの合併関数を行って、各指標に対する次のものを予測する、直接更新を用いる予測方式を表す。別の例として、ディレクトリノード、および８ビットのアドレス情報によって指標を付けられるラストビットマップ予測器は、用いられる特定の関数に応じて、union（dir＋add８）１あるいはinter（dir＋add８）１で示すことができる。１の履歴の深さを有する合併関数による予測器あるいは交わり関数による予測器は、ラストビットマップ予測器と同じである。
【００４４】
予測器のこれらの実施例および他の実施例に関するさらに細かい点は、S. KaxirasおよびC. Youngによる「Coherence Communication Prediction in Shared Memory Multiprocessor」（Proceedings of the 6th Annual IEEE Symposium on High- Performance Computer Architecture (HPCA), January 2000）に記載されている。
【００４５】
表１ないし表６に示される例示的な各予測器の場合、多数の性能パラメータが掲載される。これらは、予測器サイズ、感度、特定性、肯定試験（ＰＶＰ）の予測値および否定試験（ＰＶＮ）の予測値を含む。
【００４６】
予測器サイズは、予測器によって用いられるビットの数のlog２として測定される。
【００４７】
感度は、正確な予測と省略された予測との和に対する正確な予測の比であり、実際に共有化が行われるときに、予測器が共有化を如何に良好に予測するかを示す。感度の良い予測器は、共有化の場合の状況を見つけ、利用することに優れており、一方感度の悪い予測器は多くの状況を見逃す。
【００４８】
特定性は、回避された予測と余分な予測との和に対する回避された予測の比であり、共有されないデータにおいてリソースを無駄にしていない可能性を示す。
【００４９】
ＰＶＰは、正確な予測と余分な予測との和に対する正確な予測の比であり、全データ転送トラフィックの中の有用なデータ転送トラフィックの割合の指示を与える。
【００５０】
ＰＶＮは、回避された予測と省略された予測との和に対する回避された予測の比であり、共有されないブロックが、共有されないものとして正確に予測される可能性に関する指示を与える。
【００５１】
表１および表４はそれぞれ、直接更新および転送更新下で、性能をシミュレートした１組の実現可能な予測器のうちの最も高いＰＶＰを有する１０個の予測器を示す。このグループ内の全ての予測器は、深さ−履歴交わり関数予測器であり、非常に安定した共有関係においてのみ推測を行うことによりＰＶＰを最大にするであろう。最上位の１０個のうちの２個は、２つの表に共通である。直接更新および転送更新は、ＰＶＰにほとんど影響を受けないことがわかる。しかしながら、転送型の更新は、平均して、より感度が高い。高ＰＶＰ方式は、ラストビットマップおよび合併関数予測器方式に比べて感度が低い。これは、それらが、非常に豊富なトラフィックを生成するが、共有するための多くの機会を見逃してしまうことを意味する。
【００５２】
表２および表５は、それぞれ直接更新および転送型の更新を用いる１組の実現可能な予測器における特殊性に関しての上位１０個のそれぞれ方式を示す。
【００５３】
表３および表６は、それぞれ直接更新および転送型の更新を用いる１組の実現可能な予測器における感度に関しての上位１０個の方式を示す。すべて、この例において用いられている最大履歴深さ、即ち４の履歴深さをもつ合体（ユニオン）方式である。
【００５４】
表５および表６は、先に述べたとうり、それぞれ特殊性および感度に関する、１組の実現可能な転送型更新予測器の上位１０個の方式を示す。
【００５５】
表１ないし表６に示される予測器は単なる例示であり、本発明は、他のタイプの予測器を用いて実施できることを再び強調しておきたい。例えば、表１ないし表６の例の最大の履歴の深さは４であるが、他の予測器は、より大きい履歴の深さを用いる場合がある。
【００５６】
本発明は、任意の所望のタイプおよび構成のプロセッサを用いて、種々の異なるプロセッシングの応用形態および環境の要件を満足するように構成することができる。それゆえ、本発明の上記の実施例は、例示することだけを意図している。添付の請求の範囲内にある種々の別の実施例は当業者には明らかであろう。
【００５７】
【発明の効果】
上記のように、本発明によれば、共有メモリマルチプロセッサシステムにおいて、書込み要求を受けたデータブロックの１組の予測されるリーダを決定するための改善された技術を実現することができる。
【００５８】
【表１】
0004496455.tif 000002
【表２】
0004496455.tif 000003
【表３】
0004496455.tif 000004
【表４】
0004496455.tif 000005
【表５】
0004496455.tif 000006
【表６】
0004496455.tif 000007
【図面の簡単な説明】
【図１】本発明によるディレクトリベース予測器が実装される場合がある、分散形共有メモリマルチプロセッサの動作を示す図である。
【図２】本発明によるディレクトリベース予測器が実装される場合がある、分散形共有メモリマルチプロセッサの動作を示す図である。
【図３】一連のイベントおよび一群のリーダの一例を示す図である。
【図４】本発明によるディレクトリベース予測の一例を示す図である。
【図５】本発明によるディレクトリベース予測プロセスの流れ図である。
【図１】
0004496455.tif 000008
【図２】
0004496455.tif 000009
【図３】
0004496455.tif 000010
【図４】
0004496455.tif 000011
【図５】
0004496455.tif 000012