(57)【要約】【課題】ユーザプログラムの複製コピーの実行ポイントをアラインメントする方法及びシステムを提供する。【解決手段】本発明にかかるプロセッサベースの方法は、第１のプロセッサ及び第２のプロセッサで実行されるユーザプログラムの複製コピーの実行ポイントをアラインメントすることであって、第１のプロセッサにおいてユーザプログラムにより実行されるメモリストアのデータのみを、第１のプロセッサのメモリから第２のプロセッサのメモリへコピーすること、及び第１のプロセッサからのユーザプログラムのレジスタ状態を、第２のプロセッサによる使用のためにコピーすること、によってアラインメントすることを含む。【選択図】図３
2006209768.tif 000002
【特許請求の範囲】
【請求項１】
第１のプロセッサ及び第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）で実行されるユーザプログラムの複製コピーの実行ポイントをアラインメントすることであって、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）において前記ユーザプログラムにより実行されるメモリストアのデータのみを、前記第１のプロセッサのメモリ（４６）から前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）のメモリ（４６）へコピーすること、及び
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）からの前記ユーザプログラムのレジスタ状態を、前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）による使用のためにコピーすること、によってアラインメントすること
を含む、プロセッサベースの方法。
【請求項２】
前記コピーすることの前に、前記第１のプロセッサ及び前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）のそれぞれにおけるリタイヤ命令カウンタの値がほぼ同じになるまで、前記ユーザプログラムの少なくとも１つが実行することを許可すること、
各ユーザプログラムの所定の個数の命令を実行すること、
前記実行することとほぼ同時に、前記ユーザプログラムのそれぞれがメモリにデータを記憶するロケーションのメモリアドレスを記録すること、及び
前記ユーザプログラムのそれぞれがデータを記憶する前記メモリアドレスの和集合を求めること
をさらに含み、
前記データをコピーすることは、
メモリアドレスの前記和集合によって画定されたメモリアドレスからのデータのみをコピーすること
をさらに含む、請求項１に記載のプロセッサベースの方法。
【請求項３】
前記リタイヤ命令カウンタの値の正確度の証拠を収集すること、及び
前記収集した証拠に基づいて、前記所定の個数を調整すること
をさらに含む、請求項２に記載のプロセッサベースの方法。
【請求項４】
前記調整することは、
前記リタイヤ命令カウンタの値の不正確度が前記所定の個数以上であることを前記正確度の証拠が示唆している場合に、前記所定の個数を増加させること、又は、
前記リタイヤ命令カウンタの値の不正確度が前記所定の個数未満であることを前記正確度の証拠が示唆している場合に、前記所定の個数を減少させること、の一方
をさらに含む、請求項３に記載のプロセッサベースの方法。
【請求項５】
前記ユーザプログラムの前記複製コピーがそれぞれ所定の期間内にシステムレベルコールを行わなかったと判断した後にアラインメントすること
をさらに含む、請求項１に記載のプロセッサベースの方法。
【請求項６】
前記判断することは、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）からの情報を前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に提供することであって、前記情報は、前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）で実行されるユーザプログラムが所定の時間内にシステムレベルコールを行っていなかったことを示す、前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）からの情報を前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に提供すること、及び
前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）からの情報を使用して、前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）で実行される前記ユーザプログラムの複製コピーが前記所定の時間内にシステムレベルコールを行ったかどうかを、前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）によって判断すること
をさらに含む、請求項５に記載のプロセッサベースの方法。
【請求項７】
各プロセッサ（ＰＡ、ＰＢ、ＰＣ）の前記ユーザプログラムの、前記所定の時間内にシステムコールを行わなかったと判断された部分内において、各ユーザプログラムにシステムコールを挿入すること
をさらに含む、請求項５に記載のプロセッサベースの方法。
【請求項８】
ユーザプログラムを実行する第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）であって、第１のメモリ（４６）に連結された、第１のプロセッサと、
前記ユーザプログラムの複製コピーをほぼ同時に実行する第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）であって、第２のメモリ（４６）に連結された、第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）と、
を備え、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
前記第１のメモリ（４６）のメモリストアロケーションからのデータを前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に提供するように動作でき、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に前記ユーザプログラムのレジスタ状態を提供するように動作できる
システム。
【請求項９】
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）がデータを提供する前に、前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
自身の各ユーザプログラムの所定の個数の命令を実行するように動作でき、且つ、ほぼ同時に、前記所定の個数の命令におけるメモリストアのアドレスの第１のリストを作成するように動作でき、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）がデータを提供する前に、前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
自身の各ユーザプログラムの所定の個数の命令を実行するように動作でき、且つ、ほぼ同時に、前記所定の個数の命令におけるメモリストアのアドレスの第２のリストを作成するように動作でき、
前記第１のプロセッサ及び前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
自身の各リストを交換するように動作でき、
前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）によって提供された前記データは、
前記第１のリスト及び前記第２のリストの和集合の前記メモリロケーションからのデータである
請求項８に記載のシステム。
【請求項１０】
実質的に各ユーザプログラム命令の少なくとも完了時の状態を変更する、前記第１のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に関連した第１のリタイヤ命令カウンタと、
実質的に各複製コピーのユーザプログラム命令の少なくとも完了時の状態を変更する、前記第２のプロセッサ（ＰＡ、ＰＢ、ＰＣ）に関連した第２のリタイヤ命令カウンタと
をさらに備え、
各プロセッサが前記所定の個数の命令を実行する前に、少なくとも１つのプロセッサ（ＰＡ、ＰＢ、ＰＣ）は、
前記第１のリタイヤ命令カウンタの値及び前記第２のリタイヤ命令カウンタの値がほぼ等しくなるまで命令を実行するように動作できる
請求項９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザプログラムにおける実行ポイントのアラインメントに関する。
【０００２】
［関連出願の相互参照］
本出願は、「Method and System of Determining Whether An Application Program Has Made A System Level Call」と題する同時係属中の米国特許出願第１１／０４２，９８１号（ＣＲ参照番号２１６２−３０６００）に関連する。
【背景技術】
【０００３】
緩やかなロックステッププロセッサ（loosely lock-stepped processor）は、ユーザプログラムの複製コピーを実行するプロセッサであるが、これらのプロセッサは、ユーザプログラムの自身の各コピーを同じ歩調で実行する必要もなければ、同じウォールクロック時刻に実行する必要もない。緩やかなロックステッププロセッサは、宇宙線によって引き起こされるような計算誤りを検出して訂正するのに使用することができ、また、ユーザプログラムがハードウェア障害にもかかわらず動作し続けることを確実にするのに使用することもできる。
【０００４】
クロック周波数のわずかな相違のため、又は、或るプロセッサでは遭遇したが、他のプロセッサでは遭遇していない訂正可能なソフトエラーのため、或るプロセッサは、ユーザプログラム内の自身の実行ポイントにおいて進む（lead）ことがあり、プロセッサにおいてユーザプログラムが進んでいるのか、それとも遅れているのかを判断することは難しい。プログラムカウンタ又は命令ポインタの比較は、ユーザプログラムの実行ポイントを十分に特定することができない。その理由は、すべてのユーザプログラムは、同じソフトウェアループにあるが、ループの異なる繰り返しに存在することがあり、命令ポインタが同じ場合もあるからである。さらに、いくつかのプロセッサは、自身の性能監視ユニットに、各リタイヤ命令（retired instruction）でカウントを試みるリタイヤ命令カウンタ（retired instruction counter）を実施する。リタイヤ命令カウンタは性能監視目的で含まれ、必ずしも、ありとあらゆるリタイヤ命令を正しくカウントするとは限らないことから、リタイヤ命令カウンタの値の比較は十分でない場合がある。例えば、リタイヤ命令カウンタが特定の値に達すると、プロセッサによっては、新たな命令のロードを中止する機能を有するものもある。しかしながら、パイプラインプロセッサは、スライディングストップ（sliding stop）として知られている、完了する命令、及び、リタイヤ命令カウンタによってカウントされない命令をパイプラインに依然としていくつか有することがある。その上、プロセッサ製造業者は、自身のリタイヤ命令カウンタが１００パーセント正確であることを保証しない。
【発明の開示】
【課題を解決するための手段】
【０００５】
上記の問題は、メモリストアをコピーすることによってユーザプログラムの複製コピーの実行ポイントをアラインメントする方法及びシステムによって大部分解決される。例示の実施の形態のいくつかは、第１のプロセッサ及び第２のプロセッサで実行されるユーザプログラムの複製コピーの実行ポイントをアラインメントすることであって、第１のプロセッサにおいてユーザプログラムにより実行されるメモリストアのデータのみを、第１のプロセッサのメモリから第２のプロセッサのメモリへコピーすること、及び第１のプロセッサからのユーザプログラムのレジスタ状態を、第２のプロセッサによる使用のためにコピーすること、によってアラインメントすること、を含む方法であり得る。
【０００６】
次に、本発明の例示の実施の形態の詳細な説明について、添付図面が参照される。
【発明を実施するための最良の形態】
【０００７】
［表記及び専門用語］
以下の説明及び特許請求の範囲の全体を通じて、特定のシステムコンポーネントを参照するために、一定の用語が使用される。当業者には分かるように、コンピュータ企業は、或るコンポーネントを異なる名前で参照することがある。この文書は、名前は異なるが機能は異ならないコンポーネントを区別するつもりはない。以下の考察及び特許請求の範囲では、用語「含む」及び「備える」は、オープンエンドな形式で使用され、したがって、「含むが、これらに限定されるものではない」との意味に解釈されるべきである。また、用語「連結する」は、間接的な接続又は直接的な接続のいずれかを意味するように意図されている。したがって、第１のデバイスが第２のデバイスに連結する場合、その接続は、直接的な接続を通じている場合もあるし、他のデバイス及び接続を介して間接的な接続を通じている場合もある。
【０００８】
［詳細な説明］
以下の考察は、本発明のさまざまな実施の形態を対象にする。これらの実施の形態の１つ又は複数は好ましいものとすることができるが、開示した実施の形態は、開示の範囲を限定するものとして解釈されるべきでなく、それ以外に使用されるべきでない。これに加えて、以下の説明は幅広い用途を有すること、及び、どの実施の形態の考察も、その実施の形態の例示にすぎないことが意図されており、開示の範囲がその実施の形態に限定されることを暗示するようには意図されていないことが当業者には理解されよう。
【０００９】
図１は、本発明の実施の形態によるコンピューティングシステム１０００を示している。詳細には、コンピューティングシステム１０００は、複数のマルチプロセッサコンピュータシステム１０を備えることができる。いくつかの実施の形態では、２つのマルチプロセッサコンピュータシステム１０のみを使用することができ、したがって、コンピューティングシステム１０００は、二重化冗長（ＤＭＲ；dual-modular redundant）システムを実施することができる。図１に示すように、コンピューティングシステム１０００は、３つのマルチプロセッサコンピュータシステム１０を備え、したがって、三重化冗長（ＴＭＲ；tri-modular redundant）システムを実施する。コンピュータシステムが二重化冗長であるのか、それとも三重化冗長であるのかにかかわらず、コンピューティングシステム１０００は、マルチプロセッサコンピュータシステム全体にわたってユーザプログラムを冗長に実行することにより、フォールトトレランスを実施する。
【００１０】
本発明の実施の形態によれば、各マルチプロセッサコンピュータシステム１０は、好ましくは、１つ又は複数のプロセッサを備え、図１に示すように、４つのプロセッサを備える。図１の各プロセッサは、プロセッサを示す頭文字「Ｐ」を有する。さらに、各プロセッサには、マルチプロセッサコンピュータシステム１０Ａ、１０Ｂ、及び１０Ｃの１つの内部におけるプロセッサの物理ロケーションをそれぞれ示す「Ａ」、「Ｂ」、又は「Ｃ」の文字名称も与えられる。最後に、各プロセッサには、各マルチプロセッサコンピュータシステム内のそのプロセッサのロケーションを示す数字名称が与えられる。したがって、例えば、マルチプロセッサコンピュータシステム１０Ａのプロセッサは、名称「ＰＡ１」、「ＰＡ２」、「ＰＡ３」、及び「ＰＡ４」を有する。
【００１１】
本発明の実施の形態によれば、各マルチプロセッサコンピュータシステム１０からの少なくとも１つのプロセッサは、論理的にグループ化されて、論理プロセッサ１２を形成することができる。図１に示す例示の実施の形態では、プロセッサＰＡ３、ＰＢ３、及びＰＣ３がグループ化されて、論理プロセッサ１２を形成することができる。本発明の実施の形態によれば、論理プロセッサ内の各プロセッサは、同じユーザプログラムをほぼ同時に実行し、したがって、フォールトトレランスを実施する。より詳細には、論理プロセッサ内の各プロセッサは、ユーザプログラムの同じ命令ストリームの提供を受けて、同じ結果を計算する（誤差がないと仮定して）が、論理プロセッサ内のプロセッサは、厳密なロックステップではなく、サイクルごとのロックステップでもない。これらのプロセッサは、緩やかなロックステップであり、割り込みのハンドリングは、システムコール（後述）等のランデブー機会に基づいて行われる。いくつかの実施の形態によれば、プロセッサは非決定的な実行を有する場合があり、したがって、厳密なロックステップは実行可能でない場合がある。プロセッサの１つが故障した場合、１つ又は複数の残りのプロセッサは、全体のシステム性能に影響を与えることなく続行することができる。
【００１２】
論理プロセッサ内に同じユーザプログラムを実行する２つ又は３つ以上のプロセッサが存在しうるため、入出力（Ｉ／Ｏ）デバイス１４及び１６に対する読み出しや書き込み等の二重（duplicate）読み出し及び二重書き込みが発生する場合がある。Ｉ／Ｏデバイス１４及び１６は、任意の適切なＩ／Ｏデバイスとすることができ、例えば、ネットワークインターフェースカード、フロッピー(登録商標)ドライブ、ハードディスクドライブ、ＣＤ−ＲＯＭドライブ、及び／又はキーボードとすることができる。障害検出の目的で読み出し及び書き込みを比較するために、各論理プロセッサは、自身を同期ロジックに関連付けている。例えば、プロセッサＰＡ１、ＰＢ１、及びＰＣ１は、同期ロジック１８に関連付けられた論理プロセッサを形成する。同様に、プロセッサＰＡ２、ＰＢ２、及びＰＣ２は、同期ロジック２０に関連付けられた論理プロセッサを形成する。論理プロセッサ１２は、同期ロジック２２に関連付けられている。最後に、プロセッサＰＡ４、ＰＢ４、及びＰＣ４は、同期ロジック２４に関連付けられた論理プロセッサを形成する。このように、各マルチプロセッサコンピュータシステム１０は、それぞれを、相互接続２６を経由して同期ロジック１８、２０、２２、及び２４のそれぞれに連結する。相互接続２６は、周辺機器相互接続（ＰＣＩ）バスであってもよく、詳細には、直列化ＰＣＩ（serialized PCI）バスである。ただし、他の通信方式も同等に使用することができる。
【００１３】
各同期ロジック１８、２０、２２、及び２４は、投票者ロジックユニットを備え、例えば、同期ロジック２２の投票者ロジック２８を備える。以下の考察は、同期ロジック２２の投票者ロジック２８を対象にしているが、同期ロジック１８、２０、２２、及び２４のそれぞれの各投票者ロジックユニットにも等しく適用することができる。投票者ロジック２８は、プロセッサからの読み出し要求及び書き込み要求を集約するように動作し、場合によっては、論理プロセッサの同期のために、プロセッサ間の情報交換の役割を果たす。説明のために、論理プロセッサ１２の各プロセッサがユーザプログラムの自身のコピーを実行することについて考察し、各プロセッサがネットワークインターフェース３４に対する読み出し要求を生成することについて考察する。論理プロセッサ１２の各プロセッサは、自身の読み出し要求を投票者ロジック２８に送信する。投票者ロジック２８は、各読み出し要求を受信し、それら読み出し要求を比較し、（読み出し要求が一致すると仮定して）ネットワークインターフェース３４に単一の読み出し要求を発行する。
【００１４】
同期ロジックによって発行された単一読み出し要求に応答して、例示のネットワークインターフェース３４は、要求された情報を投票者ロジック２８に返信する。次に、投票者ロジックは、要求された情報を複製して、論理プロセッサ内のプロセッサのそれぞれに渡す。同様に、パケットメッセージの書き込みや他のプログラム（他の論理プロセッサ上で実行されることがある）へのパケットメッセージの転送等の他の入出力機能についても、同期ロジックは、それらの要求が一致することを確認し、次いで、単一の要求を適切なロケーションに転送する。論理プロセッサのいずれか１つのプロセッサが適切に機能しない場合（例えば、要求を生成できない場合、指定された時間内に要求を生成できない場合、一致しない要求を生成する場合、又は、完全に故障している場合）、全体のユーザプログラムは、論理プロセッサの残りの１つ又は複数のプロセッサの要求に基づいて続行する。
【００１５】
外部インターフェース（ネットワークインターフェース３４等）に対する読み出し及び書き込みの集約、及び、それら外部インターフェースから返信されたデータの複製に加えて、同期ロジックは、日時情報の要求が行われた時に各プロセッサに同じ日時が確実に提供されるようにする役割も果たす。詳細には、ユーザプログラムは、それらユーザプログラムの実行における一定のポイントで、日時情報を要求するシステムコールを行うことがある。システムコールは、オペレーティングシステムプログラム等の（ユーザモードよりも高い特権モードで実行される）特権プログラムに対するあらゆるコールである。日時情報を得るためのシステムコールは、システムコールのカテゴリーに分類されるプログラムファミリーの単なる一例にすぎず、割り込みをハンドリングする際のシステムコールの役割は、以下でより十分に考察する。ユーザプログラムにおける対応するポイントにおいて（それらの対応するポイントが実行された時のウォールクロック時刻が異なるにもかかわらず）同じ日時を各ユーザプログラムに提供するために、論理プロセッサ内の各プロセッサが内部的に時刻を導き出すのではなく、本発明の実施の形態による同期ロジックが論理プロセッサ内の各プロセッサに日時情報を提供する。
【００１６】
図２は、マルチプロセッサコンピュータシステム１０をより詳細に示している。詳細には、図２は、本発明の実施の形態によるマルチプロセッサコンピュータシステム１０が、複数のプロセッサを有することができ、図２の例示の事例では４つのこのようなプロセッサ３４、３６、３８、及び４０を有することができることを示している。４つのプロセッサのみが示されているが、本発明の範囲及び精神から逸脱することなく、任意の個数のプロセッサを使用することができる。プロセッサ３４〜４０は、個別にパッケージングされたプロセッサとすることができ、プロセッサのパッケージは、単一のパッケージ内に２つ又は３つ以上のプロセッサダイを備えるか、又は、単一のダイ上に複数のプロセッサを備える。プロセッサのそれぞれは、プロセッサバス４４を経由してＩ／Ｏブリッジ及びメモリコントローラ４２（以下、Ｉ／Ｏブリッジ４２という）に連結することができる。Ｉ／Ｏブリッジ４２は、メモリバス４５を経由してプロセッサ３４〜４０を１つ又は複数のメモリモジュール４６に連結する。したがって、Ｉ／Ｏブリッジ４２は、１つ又は複数のメモリモジュール４６によって画定されたメモリ領域に対する読み出し及び書き込みを制御することができる。また、Ｉ／Ｏブリッジ４２は、バスライン４３によって示すように、プロセッサ３４〜４０のそれぞれが同期ロジック（図２に図示せず）に連結することも可能にすることができる。
【００１７】
図２をさらに参照して、１つ又は複数のメモリモジュール４６によって画定されたメモリを、各プロセッサにつき１つのパーティションに区画することができる。したがって、プロセッサのそれぞれは、独立に動作することが可能になる。代替的な実施の形態では、各プロセッサは、それ自身の一体化されたメモリコントローラを有することができ、したがって、各プロセッサは、それ自身の専用メモリを有することができ、これも本発明の考慮の範囲内にある。プロセッサ３４〜４０は、厳密なロックステップ実行に適していない非決定的プロセッサとすることもできる。
【００１８】
図２は、各マルチプロセッサコンピュータシステム１０が、Ｉ／Ｏブリッジ４２とメモリモジュール４６との間に連結された再統合ロジック４８を備えることもさらに示している。図１の例示の実施の形態は、再統合ロジックの相互接続（ライン５１）をリング形式で示しているが、任意のネットワークトポロジを同等に使用することができる（例えば、リング、ツリー、二重リング、完全接続）。動作時において、再統合論理ロジック４８は、Ｉ／Ｏブリッジ４２に対してトランスペアレントであり、１つ又は複数のメモリモジュール４６に対する読み出し及び書き込みを妨げない。しかしながら、論理プロセッサ内の或るプロセッサが障害に遭遇し、再起動する必要がある場合に、再統合ロジック４８は、以前故障したプロセッサが、論理プロセッサの故障していないプロセッサと同じポイントで開始できるように、別のプロセッサから少なくともユーザプログラムメモリのコピーを可能にする。
【００１９】
緩やかなロックステップシステムでは、或るプロセッサが進んだり遅れたりすることがある理由は多く存在し得る。例えば、各プロセッサはほぼ同じクロック周波数で命令を実行することができるが、実際のクロック周波数の差は小さくても、時間の経過によってかなりの差になることがある。その上、本発明の少なくともいくつかの実施の形態に従って実施されたプロセッサは、非決定的な実行を有し、したがって、たとえ正確に同じユーザプログラムが提供されても、プロセッサは、ユーザプログラムの同じ実行ポイントに到達するのに実行ステップ数が大きく異なる場合がある。さらにまた、いくつかのプロセッサは、データアクセス問題及び／又はエラーに遭遇する可能性もある。いくつかの例として、或るプロセッサが、他のプロセッサが遭遇することができないキャッシュミスに遭遇することがある、或るプロセッサが訂正可能なメモリエラーに遭遇することがあり、したがって、残りのプロセッサには必要とされない回復ルーチンの実行を必要とすることがある、及び、或るプロセッサがトランスレーション・ルックアサイド・バッファ（Translation Look-aside Buffer）のミスに遭遇することがあり、それによって、ユーザプログラムの最終結果に影響を与えないが付加的処理が行われる、といったものがある。これらの場合も、プロセッサは、最終的に、ユーザプログラムの同じ実行ポイントに到達するが、実行される命令数、及び、それらの命令を実行するのに必要な時間は、同じでないことがある。
【００２０】
論理プロセッサのプロセッサが同じ命令ストリームを実行しているが、その命令ストリームの同じポイントに存在しないことがあるという考えに留意して、このような環境における割り込みのハンドリングに考察を移す。たとえ、同じ割り込みが、正確に同じウォールクロック時刻で各プロセッサにアサートされても、それら各プロセッサの緩やかなロックステップ実行により、割り込みは、各プロセッサの命令ストリームの同じポイントでアサートされないことがある。この問題は、割り込みアサート自体が非同期であることによってさらに悪化する。適切なオペレーションを確保するために、論理プロセッサ内の各プロセッサは、ユーザプログラムの命令ストリームの同じ実行ポイントで、割り込みにサービスを提供する必要がある。本発明の実施の形態によれば、割り込みが命令ストリームの同じ実行ポイントでサービスを受けることを確保することは、割り込みにサービスを提供するためのランデブーポイントについて合意するメカニズムとして同期ロジックを利用することによって行われる。
【００２１】
本発明の実施の形態によれば、論理プロセッサ内のプロセッサは、特定の割り込みがアサートされたこと、及び、割り込みにサービスを提供するための提案されたポイント、を互いに通信する。換言すると、論理プロセッサ内のプロセッサは、どの割り込みにサービスを提供すべきか（又は最初にサービスを提供すべきか）について合意し、また、割り込みにサービスを提供するためのポイントについても合意する。図３は、協力して割り込みのサービス提供を調整するさまざまなコンポーネントのオペレーションを説明するために、部分的なコンピューティングシステム１０００を示している。図３は、論理プロセッサ５０が、この場合、２つのプロセッサＰＡ１及びＰＢ１のみを備えるという意味で、図１のシステムを簡略化したものである。また、図３は、別の意味では、各プロセッサのメモリパーティション５２を示し、プロセッサがＩ／Ｏブリッジ４２を通じてメモリパーティション及び投票者ロジックにどのように連結するかを示しているので、図１よりも詳細化されている。このように、図３の論理プロセッサ５０は、マルチプロセッサコンピュータシステム１０Ａ及び１０Ｂからのそれぞれ１つのプロセッサを備える。プロセッサＰＡ１は、Ｉ／Ｏブリッジ４２Ａに連結し、Ｉ／Ｏブリッジ４２Ａは、同期ロジック１８及びＰＡ１プロセッサのメモリパーティション５２Ａの双方に連結する。プロセッサＰＢ１は、その各Ｉ／Ｏブリッジ４２Ｂに連結し、Ｉ／Ｏブリッジ４２Ｂは、同期ロジック１８及びＰＢ１プロセッサのメモリパーティション５２Ｂに連結する。
【００２２】
少なくともいくつかの実施の形態によれば、論理プロセッサのプロセッサに、割り込みにサービスを提供するためのランデブーポイントを確立するための情報を交換させるには、各プロセッサが同期ロジック１８の投票者論理回路５６における同期レジスタ５４に情報を書き込むことが必要とされる。本発明の実施の形態によれば、ランデブーポイントは、任意の適切な位置とすることができ、ディスパッチャプログラムが実行され、他のタスクを実行に設定する各時刻、トラップ及び障害ハンドラ、ユーザプログラムによって行われたシステムコール等とすることができる。システムコールがランデブーポイントのバルクであると想定されるため、本明細書の残りの部分ではこれらランデブーポイントをシステムコールと呼ぶ。しかしながら、用語「システムコール」は、この場合、一般的に、任意の可能なランデブーポイントを指すために使用されることが理解されよう。システムコール番号は、システムコールが任意の開始点（starting point）から行われた回数を示す番号とすることができる。例えば、図３のロケーション７２は、システムコール番号が存在するメモリパーティション５２のロケーションを示している。代替的な実施の形態では、システムコール番号は、メモリパーティション５２以外に位置するレジスタにも同等に記憶することができる。図３に示す実施の形態では、同期レジスタ５４は、事前に指定されたメモリロケーションであるが、データを書き込むことができるロケーションならばどのロケーションでも十分である。プロセッサの一部又はすべてが自身の各情報を書き込んだ後、投票者ロジック５６は、同期レジスタ５４の情報を、メモリパーティション５２のそれぞれにおける対応する１組のレジスタ５７にライトバックする。レジスタ５４と同様に、レジスタ５７は、メモリパーティション５２に事前に指定されたメモリロケーションであるが、データを書き込むことができるロケーションならばどのロケーションでも十分である。同期ロジックへ情報を書き込むことによって、残りのプロセッサが割り込みを調べるのを待っている間、ユーザプログラムの処理を続けることが可能になる。情報を交換することによって、論理プロセッサ内のプロセッサは、ユーザプログラムのどのポイントで割り込みにサービスを提供するかを調整する。
【００２３】
任意の時刻にプロセッサに割り込みをアサートすることは、割り込み情報を含んだパケットベースのメッセージを介して行うことができる。また、割り込みは、或るプロセッサクロックサイクル数の後に満了するように設定されたタイマ等の内部信号源からプロセッサにアサートすることもできる。このようなパケット又は内部割込みがプロセッサによって受信され検出されると、ユーザプログラムは一時停止され、割り込みハンドラルーチンが起動される。割り込みハンドラルーチンの目的は、ランデブーポイントを特定するプロセスを開始することである。割り込みによって要求されたサービスに関する動作は、割り込みハンドラルーチンによっては行われない。システムコールは、ランデブーポイントをスケジューリングしたプロセスが完了したポイントであり、また、割り込みにサービスを提供するプログラムのスケジューリングが行われたポイントでもある。システムコールに基づく割り込みのスケジューリングに関するより多くの情報については、「Method and System of Loosely Lock-Stepped Non-Deterministic Processors」と題する同時係属中の米国特許出願第１１／０４２，５４８号（ＣＲ参照番号２１６２−２２１００）を参照することができる。
【００２４】
このように、本発明の実施の形態によると、割り込みのサービス提供の調整は、システムコール及び他のオペレーティングシステム遷移において行われる。しかしながら、長期間の間、システムコールを行わないユーザプログラムが存在し得る。したがって、論理プロセッサ内のプロセッサが、実行しているユーザプログラムの部分について大幅に異なる可能性があり、且つ／又は、さらに、割り込みにサービスを提供する十分な機会がない可能性がある。十分な頻度でシステムコールを行わないユーザプログラムは、「非協調プロセス（uncooperative process）」と呼ばれる。
【００２５】
本発明の実施の形態による非協調プロセスのハンドリングは、いくつかの段階を有する。第１段階は、ユーザプログラムが確かに非協調的であることを識別することである。第２段階は、ユーザプログラムが異なる（必ずしもそうとは限らないが）可能性があるメモリロケーションを特定することである。第３段階は、論理プロセッサの各プロセッサにおける非協調プロセスが同じ実行ステージにあることを保証する動作を行うことであり、これは、実行ポイントのアラインメントとしても知られている。最後に、最終段階は、かつて非協調プロセスだったものを変更すること、とすることができる。これらの段階のそれぞれについて次に取り扱うことにする。
【００２６】
いくつかの実施の形態では、ユーザプログラムがあまりにも稀にしかシステムコールを行わず、したがって、非協調的であるとみなされることを特定することには、タイマの使用を必要とする。ユーザプログラムがタイマの満了前にシステムコールを行わないと、そのユーザプログラムは非協調プロセスである。また、本発明のいくつかの実施の形態によれば、プロセッサのディスパッチャプログラム（最も高い特権状態であるカーネルモードで動作する）が、ユーザプログラムを実行にセットするごとに、ディスパッチャは、プロセッサのリタイヤ命令カウンタをリセットし、ユーザ（最低レベル特権）命令のみをカウントするようにそのリタイヤ命令カウンタを設定し、非協調プロセスタイマを始動し、現在のシステムコール番号の表示を記憶する。リタイヤ命令カウンタは、例えば、ほとんどの市販のプロセッサの性能監視ユニットで実施されるカウンタである。リタイヤ命令カウンタの値は、プロセッサによる各ユーザレベル命令の実行完了時にインクリメントされる。非協調プロセスタイマに関して、インターバルタイムカウンタ（ＩＴＣ；Interval Time Counter）レジスタ及びインターバルタイムマッチ（ＩＴＭ；Interval Time Match）レジスタを装備することによって、Intel（登録商標）により製造されたＩｔａｎｉｕｍ（登録商標）プロセッサを、非協調プロセスを検出するのに使用することができる。Ｉｔａｎｉｕｍ（登録商標）プロセッサが使用される場合、コンパイラが挿入した、例えばｌｏａｄ．ｓ及びｌｏａｄ．ｃｈｋの対といった投機的命令（speculative instruction）は、リタイヤ命令カウント値に大きな影響を与える可能性があるので、ユーザプログラムで許可されないことに留意されたい。ＩＴＣは、プロセッサの電源投入時にカウントを開始するフリーランニングカウンタ（free running counter）である。「フリーランニング」ということは、ＩＴＣが、実行される命令の個数及び／又はタイプにかかわらずカウントし、どの命令（特権にかかわらず）によってもＩＴＣを停止させることができず、どのユーザ命令によってもＩＴＣの値を変更できないことを意味する。これらの実施の形態で非協調プロセスタイマを始動することは、したがって、ＩＴＣの値を読み出すこと、及び、所望の時間が経過した時にＩＴＣの値を表す値をＩＴＭに置くことを意味する。ＩＴＣレジスタ及びＩＴＭレジスタの値が等しい場合、インターバルタイマ割り込みがアサートされる。これらの例示の実施の形態の非協調プロセスタイマは真に「満了」していないが、ここから先では、非協調プロセスタイマとして使用されるどのタイマのタイプのシステムにも一般に当てはまるように、ＩＴＭと一致するＩＴＣの値の考察を「タイマの満了」と呼ぶことにする。ＩＴＣ／ＩＴＭタイプのタイミング機能を実施しないプロセッサの場合、周期的タイマ割り込みを、レジスタと組み合わせて使用し、割り込みの回数を追跡することができ、所定の個数の周期的タイマ割り込みが発生した後に非協調プロセスに関連したタスクを実行することができる。再び、非協調プロセスタイマの一般論に移って、タイマの満了時に、非協調プロセスハンドラルーチンを起動する割り込みがアサートされる。非協調プロセスハンドラルーチンは、タイマに��って規定された期間中に少なくとも１つのシステムコールがあったかどうかをチェックする。このタイマによって規定された期間は、いくつかの実施の形態では、およそ１００マイクロ秒程度とすることができる。代替的な実施の形態では、システムコールは、タイマをリセットして、非協調プロセスハンドラルーチンのトリガを回避することができるが、これらのリセットは、多大なコストを要するカーネルモードプロセスコールを必要とすることがある。非協調プロセッサタイマに関連した割り込みは、各プロセッサの内部でハンドリングされ（確かに、ユーザプロセスが協調的である場合、非協調プロセスタイマが満了したことは、他のプロセスに通信されない）、したがって、論理プロセッサのさまざまなプロセッサにわたって調整されたサービス提供を必要とする、入出力要求等の割り込みとは異なるタイプの割り込みとみなすことができる。
【００２７】
図４（図４Ａ及び図４Ｂを含む）は、本発明の実施の形態による非協調プロセスハンドラのフロー図を示している。詳細には、非協調プロセスハンドラは、非協調プロセスタイマの満了後の割り込みのアサートによって開始することができる（ブロック４００）。割り込みを無効にした（ブロック４０２）後、非協調プロセスハンドラは、現在のシステムコール番号（たとえば、図３のロジック７２から）、及び、開始時にディスパッチャにより記憶されたシステムコール番号を読み出す（ブロック４０４）。割り込みを無効にすることは、明示的なステップとすることもできるし、割り込みハンドラの入る時に自動的に行うこともできる。現在のシステムコール番号がディスパッチャによって開始時に記憶されたシステムコール番号と同じである（ブロック４０６）ということは、ユーザプログラムが、非協調プロセスタイマによって規定された期間中にシステムコールを行わなかったことを示し、したがって、ユーザプログラムが非協調プロセスであることを示す。他方、現在のシステムコール番号が、記憶されたシステムコール番号と同じでない場合には（再びブロック４０６）、そのプロセスは協調的であり、したがって、例示の方法は、非協調プロセスタイマをリセットし（ブロック４１７）、現在のシステムコール番号を保存し（ブロック４１９）、割り込みを有効にし（ブロック４１８）、そしてユーザプログラムにリターンする（ブロック４２０）。
【００２８】
本発明の実施の形態によれば、ユーザプログラムが論理プロセッサの少なくとも１つのプロセッサ内で非協調的になることによって、他のプロセッサとのデータの交換が起動され、論理プロセッサの他のプロセッサがその非協調性に同意するかどうかが判断される。引き続き図４を参照して、現在のシステムコール番号が、ディスパッチャによって記憶されたシステムコール番号と同じである場合（ブロック４０６）、次のステップは、未確認のランデブーオペレーションがあるかどうかの判断である（ブロック４０８）（以下で考察する）。未確認のランデブーがない場合、次のステップは、ユーザプログラムの非協調性の表示を、現在のリタイヤ命令カウンタ（ＲＩＣ）の値と共に、投票者ロジック５６の同期レジスタ５４に書き込むことである（ブロック４１０）。その後、非協調プロセスハンドラルーチンは、同期データの返信を投票者ロジックのソフトウェアループで待機する（ブロック４１２）。
【００２９】
いくつかの実施の形態では、どの時点においても、データの交換は１つしか進行できないので、非協調プロセスタイマの満了時にまだ完了していないランデブーポイントである未確認のランデブーをスケジューリングしようとする試みが行われている場合（再びブロック４０８）、次のステップは、投票者ロジックが同期データを書き込むまでソフトウェアループで待機することである（ブロック４２２）。ライトバックされた同期データは、前の割り込み（非協調プロセスハンドラルーチンの現在の実行をトリガした非協調プロセスタイマ満了割り込みではない）についてのものであることに留意して、返信されたデータは、ランデブーポイントのスケジューリングに使用される（ブロック４２４）。ランデブーポイントのスケジューリングに関するより多くの情報については、「Method and System of Loosely Lock-Stepped Non-Deterministic Processors」と題する米国特許出願第１１／０４２，５４８号（ＣＲ参照番号２１６２−２２１００））を参照することができる。ランデブーポイントのスケジューリング（ブロック４２４）の後、プロセスは、ユーザプログラムの非協調性の表示を、現在のリタイヤ命令カウンタの値と共に、投票者ロジック５６の同期レジスタ５４に書き込むことに進み（ブロック４１０）、データの返信をソフトウェアループで待機する（ブロック４１２）。
【００３０】
ユーザプログラムが非協調的であることにプロセッサが合意しない場合には（ブロック４１４）、返信されたデータの解析が行われて、ユーザプログラムが他のプロセッサにおいて協調的であるかどうかが判断される（ブロック４１６）。例えば、一方のプロセッサの非協調プロセスタイマは、ユーザプログラムによるシステムコールの直前に満了する（又は繰り返す）ことがある一方、論理プロセッサの第２のプロセッサのユーザプログラムは、満了直前にシステムコールを行うことがある。したがって、一方のプロセッサは、プロセスが非協調的であることを示し、第２のプロセッサは、提案したランデブーポイントの書き込みを含めて、次の割り込みをハンドリングするためのランデブーポイントのスケジューリングを試みる。この解析によって、ユーザプログラムがまもなくシステムコールを行うことが明らかになると（ブロック４１６）、非協調プロセスタイマがリセットされ（ブロック４１７）、現在のシステムコール番号が保存され（ブロック４１９）、割り込みが有効にされ（ブロック４１８）、そして、ユーザプログラムが実行を継続でき、まもなく再び協調的となるように、プロセスはリターンする（ブロック４２０）。
【００３１】
さらに図４を参照して、ユーザプログラムが非協調的であることに論理プロセッサのすべてのプロセッサが合意した場合（ブロック４１４）、ユーザプログラムのリタイヤ命令カウンタがプロセッサの最も高いリタイヤ命令カウンタと同じになるまで、プロセッサがユーザプログラムを先に進めて実行することによって、ユーザプログラムのさまざまなコピーをアラインメントするプロセスは開始する（ブロック４２６）（リタイヤ命令カウンタの値は、ブロック４１０において、各プログラムの非協調性の表示と共に交換されるので、各プロセッサはその情報を知っている）。場合によっては、図４の例示の非協調プロセスハンドラが動作しているプロセッサは、最も高いリタイヤ命令カウンタを有し、したがって、ユーザプログラムは、適切なポイントにいる。最も高いリタイヤ命令カウンタの値に向けて先に実行することは、多くの形態を取ることができる。現在のプロセッサのリタイヤ命令カウンタの値が、最も高いリタイヤ命令カウンタの値よりもかなり遅れている場合、タイマを始動することができ、タイマの活動時間の期間中、ユーザプログラムの実行を可能にすることができる。或いは、タイマ期間の間、ユーザプログラムが実行することを可能にするために、又は、最も高いリタイヤ命令カウンタの値に近いリタイヤ命令カウンタを得るのにタイマが使用された後のいずれかで、プロセッサを単一命令モード（single instruction mode）に置くことができる。この単一命令モードでは、リタイヤ命令カウンタが最も高いリタイヤ命令カウンタの値と一致するまで、ユーザプログラムは単一ステップで実行される。
【００３２】
例示の図４のブロック４２６の完了後、論理プロセッサのすべてのプロセッサは、同じリタイヤ命令カウンタの値にあるが、背景技術の項で考察した理由から、ユーザプログラムが実際に命令ストリームの同じ実行ポイントにあるという保証はない。したがって、図４の例示のステップを実行している各プロセッサにおける次のステップは、ユーザプログラムにおいて所定の個数の命令を前に進めて実行すると同時に、メモリストアのアドレスを記録することである（ブロック４２８）。この所定の個数は、図では「Ｎ」で示されている。Ｎの値は、特定のブランド及びモデルのプロセッサでテストを行うことによって求めることができ、同じ命令ストリームを提供されたプロセッサ間のリタイヤ命令カウンタの値の少なくとも最大誤差を表すものである。換言すると、Ｎの値は、プロセッサのリタイヤ命令カウンタ（ユーザプログラムがディスパッチされた時にゼロにされる）が等しい時のプロセッサの実行ポイント間の実際の命令の最大個数とすることができる。いくつかの実施の形態では、Ｎの値は、最大誤差の複数倍にすることができ、場合によっては、Ｎの値は、たとえば１，０００となるように選択される。
【００３３】
図４のブロック４２８をさらに参照して、Ｉｔａｎｉｕｍ（登録商標）プロセッサを使用して実施される実施の形態では、ユーザプログラムのメモリへの書き込みアクセスのそれぞれにおいてトリガするマスク値でＩｔａｎｉｕｍ（登録商標）の「データブレークポイントレジスタ」を設定することによって、ユーザプログラムの各メモリに対するユーザプログラムのストアが記録される。ユーザプログラムは、割り込みが有効にされた状態で、少なくともＮ個の命令の間続行することが許可される。Ｎ個の命令の実行中、データブレークポイントレジスタのマスク値がメモリアクセスによって満たされると、割り込みがアサートされる。そのメモリアクセスがストアであった場合に、このアサートされた割り込みは、アドレスを記録する割り込みハンドラを実行させる。ユーザプログラムがＮ個の命令を前に進めて実行していない限り、各メモリアクセスが、ストアアドレスを記録する割り込みをトリガすると、ユーザプログラムは再び実行を許可される。データブレークポイントレジスタを設定することに加えて、少なくともいくつかの実施の形態は、十分大きな時間値で設定されるタイマも装備し、ユーザプログラムがメモリアクセスを含まず、したがってメモリストアを含まない場合に、このタイマが、ユーザプログラムの実行をブレークして少なくともＮ個の命令が実行されたかどうかを判断するための方法を提供するようにされる。ユーザプログラムが少なくともＮ個の命令を前に進めて実行すると、データブレークポイントレジスタがクリアされ、割り込みが無効にされ、図４の例示のプロセスが再開される。他の製造業者が提供しているプロセッサは、Ｉｔａｎｉｕｍ（登録商標）のデータブレークポイントレジスタの能力と同様の能力を有することもできるし、等価なロジックを追加してこの機能を提供することもできる。
【００３４】
Ｎ個の命令のストアアドレス（もしあれば）を記録した後、ランデブーポイントを決定するためのデータの交換と同様の方法で、記録されたアドレスが投票者ロジックに書き込まれるか、又は、Ｎ個の命令においてストアが行われなかったことを示す表示が投票者ロジックに書き込まれる（ブロック４３０）。これ以降、記録されたストアアドレスについて言及する場合、Ｎ個の命令においてストアが行われなかったことを示す表示も暗黙的に含まれる。このように、記録されたストアアドレスは、投票者ロジックのレジスタ５４に書き込まれるか、又は、投票者ロジックの、記録されたストアアドレスの交換専用のレジスタに書き込まれる。すべてのプロセッサが、ユーザプログラムの非協調性に合意していることに留意すると、最終的には、すべてのプログラムが、記録されたストアアドレスのリストを書き込み、すべてのデータが投票者ロジックに一旦書き込まれると、それらデータは、プロセッサ、たとえばレジスタ５７にライトバックされる。例示の図４は、プロセッサの観点からのフロー図であり、詳細には、非協調プロセスハンドラルーチンの観点からのフロー図である。各プロセッサへのデータのライトバックは、論理プロセッサの他のすべてのプロセッサが自身の各データを書き込んだ後（又はタイムアウトした後）、投票者ロジックによって実行される。したがって、ステップ４３２は、投票者ロジックがデータを返信するのを各プロセッサが待機していることを示している。データセットのサイズに応じて、同期ロジックを通じた情報の交換は、数回の繰り返しを要することがあり、したがって、ブロック４３０及び４３２によって示す方法は、複数回繰り返されることがある。したがって、各プロセッサは、他のプロセッサからの、記録されたストアアドレスの返信をソフトウェアループで待機する（ブロック４３２）。
【００３５】
次のステップは、各プロセッサが、すべてのプロセッサによって提供された情報からストアアドレスの和集合を計算することである（ブロック４３８）。たとえば、第１のプロセッサが｛１，２，３，４｝のストアアドレス集合を記録し、且つ、第２のプロセッサが｛２，３，４，５｝のストアアドレス集合を記録している場合、これら記録されたストアアドレスの和集合は｛１，２，３，４，５｝となる。記録されたストアアドレスの和集合は、プロセッサ間のメモリが異なる可能性があるメモリロケーションのリストを表している。その後、各プロセッサは、和集合の自身のストアアドレスのそれぞれにおける値を、ユーザプログラムのレジスタ状態と共に、論理プロセッサ内の他のプロセッサへ送信する（ブロック４４０）。このようにして、論理プロセッサ内の各プロセッサは、論理プロセッサ内のどのプロセッサが送信元（source）プロセッサであるかに基づいて、自身のメモリ及びレジスタ状態を内部で訂正するのに必要とされるすべての情報を有する。
【００３６】
次のステップは、プロセッサが協働して送信元プロセッサを特定することである（ブロック４３４）。送信元プロセッサは、実行ポイントにおいて先行するプロセッサである必要はなく、実際、送信元プロセッサの選択は任意とすることができる。協働して送信元プロセッサを選択することは、レジスタ５４に書き込んで、投票者ロジックが各プロセッサから供給されたデータをすべてのプロセッサへ返す等、投票者ロジックを通じて情報を交換することを含むことができる。いくつかの実施の形態では、送信元プロセッサはあらかじめ定められ、したがって、ブロック４３４及び４３６は、プロセッサがオンラインで実行される時やプロセッサに故障の疑いがある時等、その他の時に行うことができる。他の方法も等しく使用することができる。図４の例示の方法が動作しているプロセッサが送信元プロセッサである場合（ブロック４３６）、データを置換することは必要とされない。したがって、次のブロック４４４を飛ばして、非協調プロセスタイマがリセットされ（ブロック４１７）、現在のシステムコール番号が保存され（ブロック４１９）、割り込みが有効にされ（ブロック４１８）、そして、プロセスはユーザプログラムにリターンする（ブロック４２０）。
【００３７】
他方、例示のプロセスが実行されているプロセッサが送信元でない場合（再びブロック４３６）、プロセッサは、各ストアアドレスにおける値及びユーザプログラムのレジスタ状態を送信元プロセッサから取り込み、自身の対応するメモリの値及びレジスタ状態を置換する（ブロック４４５）。このレジスタ状態は、ユーザプログラムの現在の状況及び実行ポイントを規定する、プロセッサのさまざまなレジスタの状態と共に、現在のプログラムカウンタの値を含む。送信元でないプロセッサで実行が再開された時、それら送信元でないプロセッサは、送信元プロセッサと同じロケーションで再開し、同じメモリ状態を有する。
【００３８】
少なくともいくつかの実施の形態によれば、各プロセッサがユーザプログラムの非協調性に合意した時にアラインメントを強制するだけで、ユーザプログラムの非協調性にかかわらず、適切なオペレーションを確保するのに十分な場合がある。少なくともいくつかの実施の形態では、各プロセッサは、ユーザプログラムにシステムコールを仕掛けて（ブロック４４４）、ユーザプログラムの少なくとも非協調プロセスの指定を引き起こした部分が再びそのようにならないことを確実にする。この事前対策ステップは多くの形態を取ることができる。いくつかの実施の形態では、ユーザプログラムの好ましくない部分（ほとんどはソフトウェアループ）が、システムコールを含むように変更される。これは、例えば、ノーオペレーション命令（ＮＯＰ）をシステムコール（例えば、日時コール）と置換することによって行われる。ユーザプログラム命令ストリームが単なる置換を許容していない場合には、命令は、その置換される命令を指し示す分岐命令、システムコール、及びリターン分岐命令と置換される。これらの変更は、ユーザプログラムがメインメモリに存在するときにユーザプログラムに対して行うことができ、且つ／又は、ユーザプログラムがディスクドライブ等の長期記憶デバイスに存在するときにユーザプログラムに対して行うことができる。さらに別の代替的な実施の形態では、プロセッサハードウェアは、命令ストリームの特定のポイントに割り込みを挿入するメカニズムをサポートすることができ、その割り込みは、アラインメント及び割り込みスケジューリングのためのシステムコールをトリガすることができる。たとえば、Ｉｔａｎｉｕｍ（登録商標）プロセッサファミリは、「命令ブレークポイントレジスタ」として知られている、プロセッサ内のレジスタをサポートする。このブレークポイントレジスタには、命令ポインタ値をロードすることができる。実際の命令ポインタがブレークポイントレジスタの値と一致すると、割り込みがトリガされる。この例示のメカニズムは、割り込みをトリガするのに使用され、この割り込みは、次に、同期目的でシステムコールをトリガする。このハードウェアベースのメカニズムは、すべてのアーキテクチャで利用可能でない場合があるが、ユーザプログラムを変更する実施の形態は、汎用的な適用を有することができる。その後、非協調プロセスタイマはリセットされ（ブロック４１７）、現在のシステムコール番号は保存され（ブロック４１９）、割り込みが有効にされ（ブロック４１８）、割り込みハンドラはユーザプログラムにリターンする（ブロック４２０）。
【００３９】
実行されたＮ個の命令内にメモリストアがない場合には、送信元ではない各プロセッサは、自身のレジスタ状態のみを送信元プロセッサのレジスタ状態と置換し、ユーザプログラムが実行を再開すると、それらユーザプログラムは同じポイントで再開する。Ｎは、ユーザプログラムの実行ポイント間の最大誤差となるように決定されるので、メモリストアが、それらＮ個の命令の期間中に行われない場合、ユーザプログラムの各メモリを変更することなく各ユーザプログラムを同じポイントで再開させることは、それらユーザプログラムのメモリが異ならないので、可能である。したがって、本明細書で説明したさまざまな実施の形態は、交換する必要があるデータを大幅に少なくでき、最良の場合には、交換されるデータが全くないので、たとえば、ユーザプログラムのメモリ全体のクローンを作成すること及び／又はメモリページのクローンを作成することを上回る大きな利点を有し、ユーザプログラムのレジスタ状態を残しておく（save）ということが分かる。
【００４０】
図５Ａは、図４の概念をさらに示すために、２つのプロセッサＰＡ１及びＰＢ１によって実行される複数の命令を示している。この説明は、３つのプロセッサにも等しく適用することができるが、図を過度に複雑にしないように２つが使用されている。詳細には、各プロセッサは、命令（ＩＮＳＴ）１〜１０を含む自身の各ユーザプログラムが非協調的であると判断しているものとみなす（図４のブロック４１０、４１２、及び４１４）。さらに、各プロセッサは、最も高いリタイヤ命令ポインタの値（図５Ａの場合、ＲＩＣ＝Ａ）にユーザプログラムをステップさせているものとみなす（図４のブロック４２６）。リタイヤ命令のカウントを担当するハードウェアの不完全性のため、２つのプロセッサのリタイヤ命令カウンタの値が等しいにもかかわらず、ユーザプログラムの実行ポイントは、２つのプロセッサ間で異なる場合がある。図５Ａは、２つのプロセッサのリタイヤ命令カウンタの値が等しいにもかかわらず、プロセッサＰＢ１が、２つの命令だけプロセッサＰＡ１に先行していることを示している。さらに、ユーザプログラムの平均的なタイムスライスの期間中に遭遇する命令数にわたってリタイヤ命令をカウントする際に起こり得る最も大きな誤差は、場合によっては経験的なテストを通じて、２であると判断されるものとみなす。
【００４１】
この例示の場合、Ｎの値は、２以上の値に等しく設定することができ、４が使用される。各ユーザプログラムは、４つの命令を先に進めてステップすることが許可されると同時に、ストアアドレスのリストを作成する（図４のブロック４２８）。この例示の場合、各命令がメモリストアであり、したがって、各プロセッサは、各命令のストアアドレスを記録するものとみなす。プロセッサＰＡ１によって記録されたアドレス５００は、したがって、命令｛４，５，６，７｝のストアアドレスである。同様に、プロセッサＰＢ１によって記録されたアドレス５０２は、したがって、命令｛６，７，８，９｝のストアアドレスである。これら記録されたストアアドレスは、プロセッサ間で交換される（図４のブロック４３０、４３２）。次に、各プロセッサは、ストアアドレスの和集合を計算し（図４のブロック４３８）、この和集合は｛４，５，６，７，８，９｝となる（図４のブロック４３８）。これらの前提が与えられると、２つの集合の和集合は、２つのプロセッサのメモリが（誤差の幅（margin）で）異なる可能性のあるすべてのロケーションを表している。その後、ストアアドレスの和集合の値は、プロセッサ間で交換される（図４のブロック４４０）。次に、送信元プロセッサが選択され（図４のブロック４３４及び４３６）、送信元でないすべてのプロセッサは、和集合のメモリアドレスの値を送信元プロセッサからの値と置換し、また、自身の各レジスタ状態を送信元プロセッサのレジスタ状態と置換する（図４のブロック４４５）。
【００４２】
図５Ｂは、プロセッサＰＡ１が送信元として選択され、したがって、プロセッサＰＡ１の値及びレジスタ状態がプロセッサＰＢ１の値及びレジスタ状態に取って代わる場合を示している。プロセッサのそれぞれがこの第１の例示の場合に再開すると、プロセッサは命令８で実行を開始する（矢印５０４）。プロセッサＰＢ１は、命令８及び９を重複して実行するが、前の実行の効果は、プロセッサＰＡ１からのデータのコピーによって置き換えられる。同様に、図５Ｃは、プロセッサＰＢ１が送信元として選択され、したがって、プロセッサＰＢ１の値及びレジスタ状態がプロセッサＰＡ１の値及びレジスタ状態に取って代わる場合を示している。プロセッサのそれぞれがこの第２の例示の場合に再開すると、プロセッサは、命令１０で実行を開始する（矢印５０６）。プロセッサＰＡ１は、命令８及び９を実行しなかったが、それにもかかわらず、それらの命令の効果は、プロセッサＰＢ１からのメモリロケーションの値のコピーのため存在し、また、レジスタ状態のコピーのため存在する。
【００４３】
送信元として選択されたプロセッサからのメモリロケーションの値を提供することは、多くの形態を取ることができる。いくつかの実施の形態では、メモリロケーションの値は、論理プロセッサの各投票者ロジックを使用して交換される。投票者ロジックの使用は、Ｎの値が小さい場合等、交換するデータ量が比較的小さい場合に実際的となり得る。他の実施の形態では、メモリロケーションの値は、各プロセッサの再統合ロジック４８（図２）を使用して交換される。さらに別の実施の形態では、メモリロケーションの値は、ネットワーク１７（図１）にわたるパケットメッセージを使用して交換される。
【００４４】
図６は、図４の方法をさらに示すために、イベント割り込みに関係した非協調プロセスのハンドリングを示す時間表である。詳細には、図６は、各プロセッサがシステムコール番号１９９９に遭遇する状況を示している。プロセッサＰＡ１の場合、割り込み５は、非協調プロセスタイマの満了前にアサートされ、したがって、プロセッサＰＡ１は、システムコール番号２０００で割り込み５のサービス提供を提案する（ライン６００）。割り込み５のサービス提供を提案した直後、プロセッサＰＡ１の非協調プロセスタイマは満了し、ランデブーが未確認であるため、プロセッサＰＡ１は、投票者ロジックが前の提案からの同期データを書き込むのを待機してスピンする（spin）（図４のブロック４２２）。これに対して、プロセッサＰＢ１は、割り込みがアサートされる前に、自身の非協調プロセスタイマを満了させ、したがって、プロセッサＰＢ１は、非協調プロセス情報を同期レジスタ５４に書き込み（ライン６０２；図４のブロック４１０）、確認をソフトウェアループで待機する（図４のブロック４１２）。その後、投票者ロジックは、同期データを各プロセッサにライトバックする（ライン６０４）。プロセッサが割り込みのサービス提供に合意せず、非協調プロセス割り込みの即時動作性から、プロセッサＰＡ１は、割り込み５を今後再び提案できるようにリストに書き込み（ブロック４２４）、非協調プロセスの表示を同期レジスタに書き込み（ライン６０６；図４のブロック４１０）、そして、確認をソフトウェアループで待機する（図４のブロック４１２）。
【００４５】
プロセッサＰＢ１について、プロセッサは、非協調プロセスに関して合意しない（ブロック４１４）（プロセッサＰＡ１は、アプリケーションプログラムが非協調であることを示すのではなく、割り込みにサービスを提供することを提案した）。その上、プロセッサＰＡ１によって提案されたシステムコール番号（この例示の場合にはシステムコール２０００）は、プロセッサＰＢ１のシステムコールが次に行われることを意味するものではなく、提案したシステムコール番号２０００は、プロセッサＰＡ１もシステムコール番号１９９９に達していることを暗に意味するものである（図４のブロック４１６）。したがって、プロセッサＰＢ１は、非協調プロセスの表示の第２の書き込みを行い（ライン６０８；図４のブロック４１０）、この場合も、確認をソフトウェアループで待機する（ブロック４１２）。その後、投票者ロジック５６は、同期データを各プロセッサに書き込む（ライン６１０）。この例示の第２の書き込みでは、プロセッサは、非協調ステータスに合意し（各プロセッサについてブロック４１４）、したがって、各プロセッサは、ユーザプログラムの実行ポイントをアラインメントするプロセスを開始する。
【００４６】
また、図６は、投票者ロジックに書き込まれた同期データが一致しないにもかかわらず、ユーザプログラムの非協調性がまもなく終了する可能性があるという情報をプロセッサが収集する状況も示している。詳細には、図６は、プロセッサＰＡ１が、この例示の場合にはシステムコール番号３０００のシステムコールを行うこともさらに示している（領域６１４）。システムコールプロセスの一部として、プロセッサＰＡ１は、次のランデブーポイントを提案又は広告する（ライン６１６）。これに対して、プロセッサＰＢ１は、自身の非協調プロセスタイマをシステムコール前に満了させ、したがって、非協調プロセスの表示を書き込み（ライン６１８；図４のブロック４１０）、確認をソフトウェアループで待機する（図４のブロック４１２）。投票者ロジックが同期データを返信すると（ライン６２０）、プロセッサＰＡ１は、不一致に気付き、再び、同期データの書き込みを試みる（ライン６２２；図４のブロック４１４）。これに対して、プロセッサＰＢ１は、同期データを受信し（ライン６２０）、プロセッサがユーザプログラムの非協調性について合意しない（図４のブロック４１４）一方、プロセッサＰＡ１からの提案されたランデブー情報は、システムコールが次に行われることを示している（図４のブロック４１６）。したがって、プロセッサＰＢ１は、システムコールが行われるまで、ユーザプログラムの実行を継続する。その後の或る時に、プロセッサは、プロセッサＰＡ１によって最初に提案された割り込みに合意する。
【００４７】
ここまで説明した実施の形態は、Ｎの値が静的であり、事前に決定されていると仮定している。代替的な実施の形態では、Ｎの値が順応して（adaptively）変更される。図７は、Ｎの値に対する順応変更を実施するアルゴリズムのフロー図を示している。図７の例示の方法は、スタンドアロンプロセスとして実施することもできるし、図４の方法内に組み込むこともでき、たとえば、リタイヤ命令カウント値が一致するまで前に進めて実行すること（図４のブロック４２６）、及びＮ個の命令を前に進めて実行すること（図４のブロック４２８）の間に組み込むことができる。このプロセスは開始して（ブロック７００）、リタイヤ命令カウンタの正確度の証拠の収集に移る。いくつかの実施の形態では、リタイヤ命令カウンタの値が等しい場合、プロセッサ間の命令ポインタの値が比較される。たとえば、リタイヤ命令カウンタの値が等しい場合において、命令ポインタが同じであるとき、これは、リタイヤ命令カウンタに誤差がないことの証拠である。したがって、これらの実施の形態は、最も高いリタイヤ命令カウンタの値に向けて先に進めてステップした後、同期ロジックを使用して命令ポインタを交換すること等により、命令ポインタを交換することを必要とする。いくつかの実施の形態では、各プロセッサは、自身の記録されたストアアドレスの集合のサイズをストアアドレスの集合の和集合と比較する。たとえば、プロセッサが、自身のストアの集合のサイズが５エントリであり、すべてのストアアドレスの集合の和集合のサイズが５エントリであると計算すると、これは、プロセッサ間のリタイヤ命令カウンタの値に誤差がないか、又は、小さな誤差しかないことの証拠である。これに対して、プロセッサが、自身のストアアドレスの集合のサイズが５エントリであり、和集合のサイズが１０（二重化冗長システムで）であるか、又は、１５（三重化冗長システムで）であると計算すると、これは、リタイヤ命令カウンタの値の誤差が、Ｎの選択された値又は提供された値と等しいか又はそれよりも大きいかのいずれかであることの証拠である。
【００４８】
リタイヤ命令カウンタの正確度の証拠を収集する正確なメカニズムの如何を問わず、次のステップは、リタイヤ命令の誤差がＮの値に近づいていることをその証拠が示すかどうかを判断することであり（ブロック７０４）、たとえば、誤差がＮ以上であることをその証拠が示唆するかどうかを判断することである。そうである場合、Ｎの値は調整されるべきであり（ブロック７０６）、証拠のログはリセットされる（ブロック７１６）（以下でさらに考察）。Ｎの値の増加又は減少は、他のプロセッサの協議なしに、各プロセッサが完了することもできるし、Ｎの値を増加させる判断は、それらプロセッサによるデータの交換を起動して、変更の正確な値について合意することもできる。
【００４９】
リタイヤ命令カウンタの不正確度がＮの値に近づいていることを証拠が示唆していない場合、次のステップは、収集された証拠をログ記録することである（ブロック７０８）。したがって、たとえ、リタイヤ命令カウンタの誤差がＮよりも大きい可能性があることを、収集された証拠の１つの事例が示していたとしても、（この場合、ユーザプログラムの複製コピーが正しくアラインメントされていない可能性があるので）Ｎの値の増加を行うべきである（ブロック７０４及び７０６）一方、Ｎの値を低くすることは、大きな証拠の集合に基づいて行われる。この証拠の集合のサイズが十分に大きくない場合（ブロック７１０）、プロセスは終了する（ブロック７１８）。他方、証拠の集合のサイズが十分に大きい場合（ブロック７１２）、たとえば、１週間のデータ又は１カ月のデータである場合、リタイヤ命令カウンタの値に起こり得る誤差が、Ｎの現在の値よりもはるかに小さいかどうかについての判断が行われる（ブロック７１２）。たとえば、プロセッサ間のリタイヤ命令カウンタの値の正確度が１０カウント以下であるが、Ｎがおよそ１０００程度である場合、Ｎの値を削減することができる（ブロック７１４）。他方、プロセッサ間のリタイヤ命令カウンタの値の正確度が１００カウントであり、Ｎがおよそ２００程度である場合、Ｎの値は変更されるべきではない。次のステップでは、証拠のログ記録がリセットされ（ブロック７１６）、プロセスは終了する（ブロック７１８）。
【００５０】
上記考察は、本発明の原理及びさまざまな実施の形態の例示であるように意図されている。当業者には、上記開示を十分に理解することによって、多数の変形及び変更が明らかになるであろう。たとえば、Ｉｔａｎｉｕｍ（登録商標）プロセッサが使用される場合に、そのコンパイラベースの投機的命令を使用できることを述べたが、プロセッサベースの投機は、リタイヤ命令カウンタに悪影響を与えるおそれがないので、上述した例示の方法及びシステムは、プロセッサベースの投機（たとえば、分岐予測投機及び命令リオーダ（reorder））と共に機能する。さらに、上述したさまざまな実施の形態は、非協調的という用語が定義された通りに、ユーザプログラムが非協調的であると判断された時にのみデータ交換を実行することに関係しているが、本発明の代替的な実施の形態では、メモリストアの記録並びにデータ及びレジスタ状態の交換は、割り込みのアサート時及び／又はあらゆるシステムコール時等の都合の良い任意の時刻に行うことができる。その上、図４の例示の実施の形態は、リタイヤ命令カウンタの値が一致するまで、各プロセッサが前に進めて実行することを説明している。しかしながら、Ｎ個の命令を実行した時のリタイヤ命令カウンタの値の差を、Ｎの値のサイズにおいて考慮することができる。たとえば、プロセッサが１００命令のリタイヤ命令カウント値の差を有する場合、Ｎの値は、１００に、リタイヤ命令カウンタについて予測できる誤差の最大量を加えたものとすることができる。添付の特許請求の範囲は、このようなすべての変形及び変更を包含するように解釈されることが意図されている。
【図面の簡単な説明】
【００５１】
【図１】本発明の実施の形態によるコンピューティングシステムを示す図である。
【図２】本発明の実施の形態によるコンピューティングシステムをより詳細に示す図である。
【図３】本発明の実施の形態による部分的なコンピューティングシステムを示す図である。
【図４Ａ】本発明の実施の形態による非協調プロセスハンドラのフロー図である。
【図４Ｂ】本発明の実施の形態による非協調プロセスハンドラのフロー図である。
【図５Ａ】図４の方法を示すための複数の命令を示す図である。
【図５Ｂ】図４の方法を示すための複数の命令を示す図である。
【図５Ｃ】図４の方法を示すための複数の命令を示す図である。
【図６】本発明の実施の形態によるイベント割り込みに関連して非協調プロセスをハンドリングする時間表を示す図である。
【図７】本発明の実施の形態に従って使用されるＮの値を順応して調整するフロー図である。
【符号の説明】
【００５２】
１０Ａ，１０Ｂ，１０Ｃ・・・マルチコンピュータシステム
１２・・・論理プロセッサ
１４，１６・・・Ｉ／Ｏデバイス
１７・・・ネットワーク
１８，２０，２２，２４・・・同期ロジック
２６・・・相互接続
２８・・・投票者ロジック
３４・・・ネットワークインターフェース
４２，４２Ａ，４２Ｂ・・・Ｉ／Ｏブリッジ
４４・・・プロセッサバス
４５・・・メモリバス
４６・・・メモリモジュール
４８・・・再統合ロジック
５２Ａ，５２Ｂ・・・メモリパーティション
５４・・・同期レジスタ
５６・・・投票者ロジック
【図１】
2006209768.tif 000003
【図２】
2006209768.tif 000004
【図３】
2006209768.tif 000005
【図４Ａ】
2006209768.tif 000006
【図４Ｂ】
2006209768.tif 000007
【図５Ａ】
2006209768.tif 000008
【図５Ｂ】
2006209768.tif 000009
【図５Ｃ】
2006209768.tif 000010
【図６】
2006209768.tif 000011
【図７】
2006209768.tif 000012