(57)【特許請求の範囲】
【請求項１】
相互接続と、
それぞれが前記相互接続に接続され、メモリ・サブシステムを共有する複数のプロセッサ及びメッシュ・コヒーレンス・ユニットを有する複数のプロセッサ・ノードと、
ロック値及びキー値を有し、前記ロック値は第１プロセッサ・ノードによって生成され、前記第１プロセッサ・ノードの前記メッシュ・コヒーレンス・ユニット内に記憶され、前記キー値は前記ロック値及び前記第１プロセッサ・ノード・メモリ・サブシステムのメモリアドレスから演算可能であり、前記キー値は前記メモリアドレスに対して第２プロセッサ・ノードによりアクセス可能なように前記第２プロセッサ・ノードに提供されるロック及びキー機構と、を備えるコンピュータシステム。
【請求項２】
前記第１プロセッサ・ノードの前記メッシュ・コヒーレンス・ユニットは、他のプロセッサ・ノードからの前記ロック値でのメモリアクセス要求を受け付けない請求項１に記載のコンピュータシステム。
【請求項３】
前記メモリアドレスは、前記メモリ・サブシステム内のメモリ・ページの物理的なアドレス空間を表す請求項１に記載のコンピュータシステム。
【請求項４】
前記ロック及びキー機構は、
前記キー値を、前記ロック値及び前記メモリ・アドレスの関数として演算する手段と、
前記キー値を前記第２プロセッサ・ノードに提供する手段と、を更に備える請求項１に記載のコンピュータシステム。
【請求項５】
前記ロック及びキー機構は、
前記第１プロセッサ・ノードに、前記キー値及び前記メモリアドレスを前記第１プロセッサ・ノードに提供することにより前記メモリアドレスへのアクセス要求を行わせ、前記前記第１プロセッサ・ノードに前記記憶したロック値及び受信したメモリアドレスから一時値（ｔｅｍｐ  ｖａｌｕｅ）を演算させる手段と、
前記一時値が前記キー値に一致した時に、前記アクセス要求の進行を許可する手段と、を更に備える請求項４に記載のコンピュータシステム。
【請求項６】
前記ロック及びキー機構は、
不正に当該コンピュータシステムの内部情報を得ることを目的としたソフトウエアが、前記メモリアドレス及び前記キー値から前記ロック値を演算するのを防止する手段を更に備える請求項５に記載のコンピュータシステム。
【請求項７】
集積化されたメッセージを送ることを有する分配共有メモリマルチプロセッサシステム内におけるメモリ保護の方法であって、
プロセッサ、共有可能なメモリ・サブシステム、メッシュ・コヒーレンス・ユニット（ＭＣＵ）及びそれらの通信結合のためのバスを有する第１プロセッサ・ノードを提供し、
プロセッサ、共有可能なメモリサブシステム、メッシュ・コヒーレンス・ユニット（ＭＣＵ）及びそれらの通信結合のためのバスを有する第２プロセッサ・ノードを提供し、
前記第１プロセッサ・ノードの前記ＭＣＵ及び前記第２プロセッサ・ノードの前記ＭＣＵに結合された相互接続により、前記第１プロセッサ・ノードと前記第２プロセッサ・ノードとを通信で接続し、
前記第１プロセッサ・ノードは、ロック値を生成して前記ロック値を前記第１プロセッサ・ノードの前記ＭＣＵ内に記憶し、
前記第１プロセッサ・ノードは、前記ロック値及びメモリアドレスの関数としてキー値を演算し、前記キー値及び前記メモリアドレスを前記第２のプロセッサ・ノードに通信し、
前記第２プロセッサ・ノードは、前記第１プロセッサ・ノードに対して前記キー値及び前記メモリアドレスを通信することにより、メモリアクセスへの要求を開始し、
前記第１プロセッサ・ノードは、前記ロック値及び前記メモリアドレスの関数として一時値（ｔｅｍｐ  ｖａｌｕｅ）を演算し、そして
前記第１プロセッサ・ノードは、前記一時値が前記キー値に一致したなら、前記第２プロセッサ・ノードに前記メモリアドレスへのアクセスを許可する方法。
【請求項８】
前記ロック値の記憶は、他のプロセッサ・ノードからのメモリアクセル要求を受け付けないように、前記第１プロセッサ・ノードの前記ＭＣＵの一部分に前記ロック値を記憶することを備える請求項７に記載の方法。
【請求項９】
前記第１プロセッサ・ノードのキー値keyの演算は、key=f(lock,addr)の式を使用した前記キー値の演算を備え、ここでlockはロック値であり、addrは前記keyが演算される前記メモリアドレスであり、fは前記キー値を演算する関数である請求項７に記載の方法。
【請求項１０】
前記第１プロセッサ・ノードの一時値tempの演算は、temp=f(lock,addr)の式を使用した前記一時値の演算を備え、ここでlockはロック値であり、addrは前記第２プロセッサ・ノードにより通信される前記メモリアドレスであり、fは前記一時値を演算する関数である請求項７に記載の方法。
【請求項１１】
イニシエータ・ノード（アクセスを実行するノード）及びターゲット・ノード（アクセスされたノード）を含むマルチ・プロセッサ・ノードコンピュータシステムにおけるメモリ保護の方法であって、
前記ターゲット・ノードが、ロック値を生成して記憶し、
前記ターゲット・ノードが、前記ロック値及び前記ターゲット・ノードの共有可能なメモリのメモリアドレスを使用して、キー値を演算し、
前記イニシエータ・ノードが、前記キー値及び前記メモリアドレスを受信し、
前記イニシエータ・ノードが、次に前記キー値及び前記メモリアドレスを前記ターゲット・ノードに送り、
前記ターゲット・ノードが、前記キー値及び前記メモリアドレスを受信し、
前記ターゲット・ノードが、受信した前記メモリアドレス及び記憶している前記ロック値を使用して一時値を演算し、
前記ターゲット・ノードが、前記一時値と受信した前記キー値を比較して、もし前記一時値が受信した前記キー値に一致すれば、前記イニシエータ・ノードに、前記共有可能なメモリの受信した前記メモリアドレスでのアクセス権を与える方法。
【請求項１２】
前記ロック値の記憶は、前記ロック値の共有不可能なメモリへの書き込みを備える請求項１１に記載の方法。
【請求項１３】
共有可能なメモリの前記アドレスは、前記共有不可能なメモリのページに関係する請求項１１に記載の方法。
【請求項１４】
共有可能なメモリの前記アドレスは、複数ビットを含む請求項１１に記載の方法。
【請求項１５】
不正に当該コンピュータシステムの内部情報を得ることを目的としたソフトフエアが前記メモリアドレス及び前記キー値から前記ロック値を演算するのを防止する手段は、
第１の時間期間が経過した後には前記ロック値を再生成する手段と、
再生成した前記ロック値に基づいて、前記第２プロセッサ・ノードが関数を逆にするには、前記第１の期間より大きな第２の期間が必要になるように、前記キー値を演算する関数を選択する手段と、を更に備える請求項６に記載のコンピュータシステム。
【発明の詳細な説明】
出願中の他の出願の参照
本発明は、発明者がWofl-Dietrich Weberで、共通の譲受人であり、「統合されたメッセージ・パッシング（送り）を有するキャッシュ・コヒーレンス・ユニット及び分散共有メモリマルチプロセッサシステム用メモリ保護」の名称で、１９９８年１月７日に出願された審査中の出願シリアル番号９／００３，７２１に関係する。
発明の背景
１．発明の分野
本発明は、一般的にはコンピュータ通信プロトコルに関し、特にマルチプロセッシング・コンピュータシステムにおけるキャッシュ・コヒーレンス・プロトコル(cache coherence protocol)を統合したメッセージ・パッシング・プロトコル(message passing protocol)に関する。
２．背景技術の議論
マルチプロセッサ・データ・コンピュータシステムは、高速相互接続ネットワーク上で通信する複数のプロセッサ・ノードで構成される。各プロセッサ・ノードは、典型的にはプロセッサとローカル・ランダム・アクセス・メモリ（ＲＡＭ）を有する。演算上の問題は、異なるプロセッサ・ノードで利用可能な特定の資源の利用が最大化されるように、プロセッサ・ノードに分割される。問題のプロセッサ・ノードへの分割は、結果を生成するのに必要な時間も低減し、それにより演算を促進する。しかし、仕事の分割は、必然的に１つのプロセッサ・ノードで実行するプロセスが他のプロセッサ・ノードで実行される計算の結果に依存するということを意味する。いろいろなプロセッサは、相互接続ネットワーク上で通信してそれらの特定の問題に関係する情報を交換しなければならず、更にプロセスを同期させなければならない。
マルチプロセッサシステムの性能レベルは、プロセッサが相互に通信できるスピードに依存している。共有メモリの例では、各プロセッサは他のプロセッサが書き込んでいるものを単純に読むことができるので、通信は非常に速い。しかし、このモデルは、通信プロセスを、それぞれの他のメモリの重大な領域に不注意に上書きすることによる相互の干渉から保護するものではない。メッセージ・パッシング・モデルでは、各プロセッサはその固有のメモリにのみアクセスでき、明白にメッセージを作り上げてそれを他のプロセッサに送ることによって他のプロセッサと通信できるだけである。このモデルは、それぞれの他のメモリへの書込みができないので、相互に通信プロセッサの保護を提供する。しかし、このモデルは、典型的にはオペレーティングシステムが送信の両側（送り側と受け側）で呼び出されなければならないので、非効率的でもある。これらのオペレーティングシステムは、プロセッサ間での通信も遅くする。このように、受け側でオペレーティングシステムの介在の必要がまったく無しに、通信プロセスがそれぞれの他のメモリ内の指定された領域に直接アクセスすることを可能にし、しかし同時にメモリの他の領域への不注意なアクセスからの保護を可能にすることが望まれている。あるプロセッサがハードウエア又はソフトウエアの故障に起因して他のプロセッサがそのメモリを不注意に改悪することからそれ自体を保護することを可能にする機構が、1995年９月５日にWikesに与えられた米国特許第5,448,698号に開示されている。Wikesの保護チェック機構は、ある個数のメモリ領域に対するキーを特定するターゲット（目標）で保護テーブルを使用する。Wikesの特許に開示された機構は、テーブルがハードウエアに構築されなければならず、本質的にある限られた個数の入口のみを含む記憶空間を必要とするという欠点を有する。
発明の概要
本発明は、複数のプロセッサ・ノードと相互接続を有するコンピュータシステムに属する。各プロセッサ・ノードは、相互接続に接続され、メモリとメモリに接続されたメモリバスとを有する。各プロセッサ・ノードは、複数のプロセッサを有し、各プロセッサはキャッシュを有する。コンピュータシステムは、メモリバスと相互接続の間のメッセージとメモリ・アクセス・リクエスト（要求）を制御するためのメッシュ・コヒーレンス・ユニット（mesh coherence unit）を有する。コンピュータシステムは、ロックとキー機構を有し、そこではアクセスされたメモリを有するプロセッサ・ノードは、メモリ・アドレスからの機能により演算するロック値、キー値及び一時的な値を保持し、メモリ・アクセスをリクエストしたプロセッサ・ノードは、一時的な値がキー値に一致する時メモリ・アクセスを許す。
本発明の他の目的は、ターゲット側でオペレーティングシステムの呼出（コール）が必要ないメッセージ・パッシング・システムを提供することである。
他の目的は、異なるプロセッサ・ノードで動作しているプロセスの保護を提供して、各プロセスをダメージ（損傷）から保護することである。
更に別の目的は、余分なハードウエア及び記憶空間を必要とし、及び本質的に入口の個数の制限を伴うテーブルの使用を避けることである。
本発明のこれら及び他の目的は、以下の本発明の詳細な説明及び付属の図面から、当業者には明らかになるであろう。
【図面の簡単な説明】
図１は、複数のプロセッサ・ノードを有する本発明のコンピュータシステムの機能ブロック図である。
図２は、図１のプロセッサ・ノードの機能ブロック図である。
図３Ａと図３Ｂは、ロックを設定する１つの実施例を示す。
図４Ａと図４Ｂは、キーｘを作成するターゲット・ノードによりイニシエータ・ノードにページｘへのアクセス権利を与える１つの実施例を示す。
図５Ａと図５Ｂは、ターゲットとイニシエータ・ノードの間で作ることのできるリモート・ノードからのアクセス方法の１つの実施例を示す。
好適な実施例の詳細な説明
本発明は、スケーラブル共有メモリ・マルチプロセッシング・コンピュータシステムにおける通信プロトコルのためのシステム及び方法に属する。スケーラブル共有メモリ・マルチプロセッシング・コンピュータシステムは、プロセッサが相互に通信できる相互接続に接続された複数のプロセッサを有する。メッセージが渡される従来の機構は、入力／出力チャンネル及び相互接続を介している。
本発明のシステムでは、同一の通信チャンネルがキャッシュ・コヒーレンス及びメッセージ・パッシングの両方のために使用され、メッセージが交換されるレートを著しく増加させる。各プロセッサは、プロセッサ間ノード・キャッシュ・コヒーレンス・プロトコルと強固に統合されたメッセージ・パッシング・プロトコルを使用してメッセージを送り及び受けることにより、他のプロセッサ・ノードのプロセッサと通信する。同時に、ロック及びキー機構が、メッセージ・パッシングを介してのみ通信するプロセッサ・ノード間に保護バリア（障壁）を立てる。以前の従来技術のWikesの装置に対して、本発明はハードウエア・ストレージ（記憶）をほとんど必要とせず、非常に多数のメモリ領域をカバーできる。
図１は、本発明によるコンピュータシステム１００の機能ブロック図であり、多重プロセッサ・ノード１０２ａ−ｔと、ノード１０２ａ−ｔ間の点間通信を提供するプロセッサ・ノード相互接続１０４とを有する。それぞれのプロセッサ・ノード１０２ａ−ｔは、スタンドアロン・コンピュータシステムとして又は他のプロセッサ・ノードと共有メモリで関係するように構成されている。「サイト」という語は、メモリにおける物理的なアドレス空間を共有するプロセッサ・ノードのグループを示すのに使用される。選択されたプロセッサ・ノード１０２ａ−ｄ，１０２ｆ−ｉ，１０２ｌ−ｏ及び１０２ｑ−ｔは、それぞれサイト１０６ａ，１０６ｂ，１０６ｃ及び１０６ｄとして構成されている。他のプロセッサ・ノード１０２ｅ，１０２ｊ，１０２ｋ及び１０２ｐも、相互接続１０４を介して接続されているが、メモリを共有しておらず、共通のサイトに接続されていない。異なるサイトのこのようなプロセッサ・ノードは、メッセージ・パッシングを介して通信する。例えば、サイト１０６ａにおけるプロセッサ・ノードは、他のサイトのプロセッサ・ノード、例えばサイト１０６ｃのプロセッサ・ノード１０２ｎと相互接続１０４を介して通信する。
本発明は、例示のシステム１００（図１）に示したように、プロセッサ・ノード１０２ａ−ｔ間の統合されたメッセージ・パッシングでキャッシュ・コヒーレンスを実行する。あるサイトにおけるプロセッサ・ノード、例えばサイト１０６ａのプロセッサ・ノード１０２ａ−ｄは、物理的なアドレスメモリ空間を共有する。更に、それぞれのプロセッサ・ノードは、それぞれのキャッシュメモリ２０４ａ−ｄ（図２）を有する多重プロセッサ２０２ａ−ｄ（図２）を有する。このように、キャッシュ・コヒーレンスの必要は、プロセッサ２０２ａ−ｄのキャッシュ２０４ａ−ｄ間で、ノード１０２内だけでなく、異なるプロセッサ・ノード１０２ａ−ｔでも維持される。例えば、ノード１０２ａにおけるキャッシュは、ノード１０２ｂ−ｄにおけるキャッシュとコヒーレントでなければならない。
本発明は、更にメモリ保護機構を有する。メモリ保護機構は、サイト１０６ａ−ｄ内のプロセッサ・ノードの共有物理アドレス空間へのアクセスを許し、サイト１０６ａ−ｄ以外のプロセッサ・ノード１０２ａ−ｔの共有物理アドレス空間へのアクセスを拒絶する。例えば、プロセッサ・ノード１０２ｅは、プロセッサ・ノード１０２ａにメッセージを送ることができる。しかし、プロセッサ・ノード１０２ｅはサイト１０６ａ内にはないので、プロセッサ・ノード１０２ｅはサイト１０６ａの物理アドレス空間でのメモリアクセス動作を実行できない。
図２は、プロセッサ・ノード１０２の機能ブロック図である。プロセッサ・ノード１０２は、例えば、図１のプロセッサ・ノード１０２ａ−ｔであり、それぞれキャッシュ２０４ａ−ｄを有するプロセッサ２０２ａ−ｄと、メモリ・サブシステム２０６と、入力／出力サブシステム２０８と、メッシュ・コヒーレンス・ユニット（ＭＣＵ）２１０とを有する。それぞれの機能ユニット２０２ａ−ｄ，２０６，２０８及び２１０は、バス２１２に接続され、ユニット間で制御、アドレス及びデータ信号を送ることができる。メッシュ・コヒーレンス・ユニット２１０は、相互接続１０４に接続されている。
プロセッサ２０２ａ−ｄ、メモリ・サブシステム２０６、入力／出力サブシステム２０８、及びバス２１２は、ノード当り１個又はそれ以上のプロセッサを商業的に利用できる。メッシュ・コヒーレンス・ユニット２１０は、プロセッサ間ノード・キャッシュ・コヒーレンス、プロセッサ間ノード・メッセージ、パッシング、及びプロセッサ間ノード・メモリ保護を統合する。
マルチプロセッサシステムでは、異なるプロセッサは、典型的にはそれらの仕事を統合するため相互に通信しなければならない。１つのプロセッサの不完全なソフトウエア又はハードウエアが他のプロセッサを改悪する可能性を制限するため、及び／又は異なるプロセッサ間のアクセスの保護を実行するため、いくつかのプロセッサは１つのプロセッサが他のプロセッサのメモリから直接読み出したり直接書き込むのを許さない。代わりに、これらのプロセッサはプロセッサにメッセージの交換だけを許す。直接メモリ・アクセスと異なり、メッセージは受けたプロセッサによって処理及びスクリーンされなければならず、従ってこの形式の通信は典型的には効率が悪い。
本発明の機構は、プロセッサにそれぞれの他のメモリに直接アクセスすることを許すが、プロセッサに不完全なソフトウエア又はハードウエアに対する保護を維持させる。しかし、この機構は通信ソフトウエアの悪意の意志に対しての保護は提供しない。他の実施例では、この機構は悪意のソフトウエアに対しての保護を提供するが、少し複雑なハードウエアが必要である。
この機構は、ロック及びキー・シナリオに依存している。アクセスを実行するプロセッサ・ノード（「イニシエータ」・ノード）は、キーを使用するが、アクセスされたプロセッサ・ノード（「ターゲット」・ノード）はロック（ｌｏｃｋ）を保持する。各ターゲットは、ロックとして働く大きな数を発生させる。この数は、他のプロセッサ・ノードからのメモリ・アクセス要求を受けないハードウエアに記憶される。
図３Ａと図３Ｂは、ロックを設定する１つの実施例を示す。図３Ａは、ロックを発生するソフトウエア・ステップ３１０と、アクセス保護ハードウエアにロックを記憶するハードウエア・ステップ３２０のブロック図である。図３Ｂは、ロック３５０が保護チェック機構３３０内にあり、保護チェック機構３３０がメッシュ・コヒーレンス・ユニット（ＭＣＵ）３４０内にあることを示す。
アクセス保護は、メモリ・ページ・ベースで保持され、典型的にはページは約４ｋバイトのメモリを表す。もしターゲットがいくつかのイニシエータに特定のページへのアクセス権を与えることを望むなら、次の式を使用してキー（ｋｅｙ）を作る。
ｋｅｙ＝ｆ（ｌｏｃｋ，ａｄｄｒ）                （１）
但し、ｌｏｃｋはロックの数（ロック数）であり、ａｄｄｒはキーが作られるページのアドレスであり、ｆは単純な関数である。キーとアドレスは、次にイニシエータに送られる。
図４Ａと図４Ｂは、ターゲット・ノードがキーｘを作ることにより、イニシエータ・ノードにページｘへのアクセス権を与える１つの実施例を示す。図４Ａは、ロックとアドレスからキーを作るソフトウエア・ステップ４１０と、そのキーをページｘへのアクセス権が与えられたノードに送るソフトウエア・ステップ４２０を示す。図４Ｂは、キー４３０がメッシュ・コヒーレンス・ユニット（ＭＣＵ）４４０と４６０の間で相互接続４５０を通してどのように送られるかを示す。
イニシエータがページにアクセスすることを望む時、それはアドレスに沿ってターゲットにキーを送る。ターゲットでは、ハードウエアが入ってくるアドレスとロックから次の式で“ｔｅｍｐ”の値（一時値）を演算することによりアクセスをチェックする。
ｔｅｍｐ＝ｆ（ｌｏｃｋ，ａｄｄｒ）          （２）
もしｔｅｍｐの値がアクセスと一緒に送られたキーに一致するならば、アクセスは進めることが許される。そうでなければ、アクセスは拒絶される。
図５Ａと図５Ｂは、離れたノードからのアクセスが、ターゲットとイニシエータ・ノードの間でどのように作られるかの１つの実施例を示す。図５Ａは、ステップ５１０でキーと一緒にページｘに到着するアクセス要求を示すブロック図である。ｔｅｍｐの値は、ステップ５２０でロックとアドレスの関数として演算される。ｔｅｍｐの値は、ステップ５３０でキーの値と比較され、もしそれらが等しければ、アクセス要求がステップ５４０で受け付けられ、そうでなければアクセス要求はステップ５５０で拒絶される。図５Ｂは、アクセス要求５９０が、メッシュ・コヒーレンス・ユニット（ＭＣＵ）５６０と５８０の間で相互接続５７０を通してどのように受け付けられ又は拒絶されるかを示す。
もっとも簡単な形では、関数ｆは単なる排他的論理和（ＥＸＯＲ）関数である。次に、この機構は、イニシエータのソフトウエアがターゲットによって与えられたキーを使用するだけではアクセスが与えられないメモリ領域への偶然のアクセスに対する保護を提供する。関数が容易に逆にされる場合には、悪意のソフトウエアにとって、次の式のターゲット・ロック（ｌｏｃｋ）値を推論するキー（ｋｅｙ）を発生させることは比較的容易である。
ｌｏｃｋ＝ｆ２（ｋｅｙ，ａｄｄｒ）            （３）
ここで、ｆ２はｆの逆であり、次のような式である。
ｘ＝ｆ２（ｆ（ｘ，ｙ），ｙ）                  （４）
このように、悪意のソフトウエアがターゲット・メモリの他の領域に対するキーを作る可能性が存在し、この場合には、この機構は保護を提供しない。
しかし、容易に逆にできない関数ｆを使用することにより、悪意のソフトウエアに対する保護を実現することもできる。例えば、キーが次の式であるとし、
ｋｅｙ＝ｍｏｄ（ａｄｄｒ，ｌｏｃｋ）          （５）
ａｄｄｒが十分に多い量のビットを有するように選択されるならば、悪意のソフトウエアが所定のアドレス／キーの組合せからロック値を計算するのは非常な時間の消費になる。悪意のソフトウエアにより実行できる逆計算より、ロック値がより頻繁に変更される限り、保護が維持される。ここで説明した例示の実施例は、説明のためであり、限界を意図したものではない。従って、この分野の当業者には以下の請求の範囲の範囲と本質から離れずに他の実施例が実現できることが認識できるであろう。
【図１】
0003983820.tif 000002
【図２】
0003983820.tif 000003
【図３Ａ】
0003983820.tif 000004
【図３Ｂ】
0003983820.tif 000005
【図４Ａ】
0003983820.tif 000006
【図４Ｂ】
0003983820.tif 000007
【図５Ａ】
0003983820.tif 000008
【図５Ｂ】
0003983820.tif 000009