(57)【特許請求の範囲】
【請求項１】
１つの方法であって、１つのプロセッサにおいて１つの命令シーケンスに含まれる１つの命令を実行して、前記プロセッサのために１つのロックを取得するのに役立つことと、前記ロックが利用可能でない場合、前記プロセッサにおける前記命令をスリープさせることとを含み、前記命令は、１つのイベントが生じるまでスリープし、
前記命令は、前記プロセッサによる前記ロックを取得するための１つの比較および交換動作を行う１つの比較および交換命令を備え、前記比較および交換動作は、１つのアトミック比較および交換動作を含み、前記比較および交換命令がスリープ状態である間、前記プロセッサは、前記１つの命令シーケンスに含まれる他の命令の実行を継続し、前記比較および交換命令が起動されてリタイアされるまで、前記他の命令はリタイアされないことを特徴とする方法。
【請求項２】
請求項１に記載の前記方法であって、前記ロックに対応する１つのメモリアドレスを監視することをさらに備え、前記ロックは、１つのメモリの１つの共有メモリ空間に対するプロセッサアクセスを制御することを特徴とする方法。
【請求項３】
請求項１に記載の前記方法であって、前記イベントが生じたかを決定するための１つのロック値を有する１つの宛先を監視することであって、前記宛先の前記監視は、以下の、前記ロック値における１つの変更と、前記ロック値を変更する試行とのうち、１つまたはそれ以上を観測することを含み、前記宛先は、１つのレジスタまたは１つのメモリ位置を含む、監視と、前記イベントの発生を検出することと、前記イベントが発生した場合、前記命令を起動することであって、前記イベントは、以下の、前記ロック値が変化した場合は前記ロックが利用可能になったことと、前記ロック値を変更する前記試行が発生した場合は前記ロックが潜在的に利用可能になったこととのうち、１つまたはそれ以上を備る、起動と、前記プロセッサが前記利用可能なロックを取得することとをさらに含むことを特徴とする方法。
【請求項４】
請求項１に記載の前記方法であって、前記命令のスリープ化は、以下の、複数の命令をロードすることと、前記複数の命令を実行することとのうち、１つまたそれ以上を含む複数の他のタスクを行うべく、前記プロセッサのための複数のリソースを用いることを放棄することを含むことを特徴とする方法。
【請求項５】
請求項４に記載の前記方法であって、前記複数のリソースの前記放棄は、
１つのレジスタプール内の複数のレジスタを放棄することと、
１つの命令キュー内の複数の命令キュー入力を放棄することと、
１つの記憶バッファ内の複数の記憶バッファ入力を放棄することと、
１つの再順序付けバッファ内の複数の再順序付けバッファ入力を放棄することとを含むことを特徴とする方法。
【請求項６】
１つのプロセッサであって、１つの命令シーケンスに含まれる１つの命令を実行して、前記プロセッサのために１つのロックを取得することが可能な１つの実行部と、前記プロセッサが前記ロックを取得できなかった場合、前記命令をスリープさせる１つのスリープ‐起動機構とを備え、前記命令は、１つのイベントが生じるまでスリープし、
前記命令は、前記プロセッサによる前記ロックを取得するための１つの比較および交換動作を行う１つの比較および交換命令を備え、前記比較および交換動作は、１つのアトミック比較および交換動作を含み、前記比較および交換命令がスリープ状態である間、前記プロセッサは、前記１つの命令シーケンスに含まれる他の命令の実行を継続し、前記比較および交換命令が起動されてリタイアされるまで、前記他の命令はリタイアされないことを特徴とするプロセッサ。
【請求項７】
請求項６に記載の前記プロセッサであって、前記イベントが生じたかを決定するための１つのロック値を有する１つの宛先を監視する監視論理であって、前記宛先の前記監視は、以下の、前記ロック値における１つの変更と、前記ロック値を変更する１つの試行とのうち、１つまたはそれ以上を観測することを含み、前記宛先は、１つの専用レジスタまたは１つのメモリ位置を含む、監視論理と、前記イベントの発生を検出する検出論理と、前記イベントが発生した場合、前記命令を起動する前記スリープ‐起動機構であって、前記イベントは、以下の、前記ロック値が変化した場合は前記ロックが利用可能になったことと、前記ロック値を変更する前記試行が発生した場合は前記ロックが潜在的に利用可能になったこととのうち、１つまたはそれ以上を備える、前記スリープ‐起動機構とをさらに備えることを特徴とするプロセッサ。
【請求項８】
請求項６に記載の前記プロセッサであって、前記命令のスリープ化は、以下の、複数の命令をロードすることと、前記複数の命令を実行することとのうち、１つまたそれ以上を含む複数の他のタスクを行うべく、前記プロセッサのための複数のリソースを用いることを放棄することを含むことを特徴とするプロセッサ。
【請求項９】
請求項８に記載の前記プロセッサであって、前記複数のリソースの前記放棄は、
１つのレジスタプール内の複数のレジスタを放棄することと、
１つの命令キュー内の複数の命令キュー入力を放棄することと、
１つの記憶バッファ内の複数の記憶バッファ入力を放棄することと、
１つの再順序付けバッファ内の複数の再順序付けバッファ入力を放棄することとを含むことを特徴とするプロセッサ。
【請求項１０】
請求項７に記載の前記プロセッサであって、前記プロセッサを１つのメモリに結合させる１つのバスインターフェイスをさらに備え、前記バスインターフェイスは、前記専用のレジスタをさらに備えることを特徴とするプロセッサ。
【請求項１１】
請求項６に記載の前記プロセッサであって、前記比較および交換命令を含む複数の命令を有する１つの命令の組をさらに備えることを特徴とするプロセッサ。
【請求項１２】
１つのシステムであって、１つの第１のプロセッサを含む複数のプロセッサであって、１つの命令シーケンスに含まれる１つの命令を実行して、前記第１のプロセッサのために１つのロックを取得することが可能な１つの実行部と、前記第１のプロセッサが前記ロックを取得できなかった場合、前記命令をスリープさせる１つのスリープ‐起動機構であって、前記命令は、１つのイベントが生じるまでスリープする、スリープ‐起動機構とを有する、第１のプロセッサと、前記複数のプロセッサに結合され、前記複数のプロセッサによって共有された、１つのメモリ空間を有する１つのメモリと、前記メモリおよび前記複数のプロセッサに結合され、前記メモリ空間に対するアクセスを制御する前記ロックを有する１つのロック記憶位置とを備え、
前記命令は、前記プロセッサによる前記ロックを取得するための１つの比較および交換動作を行う１つの比較および交換命令を備え、前記比較および交換動作は、１つのアトミック比較および交換動作を含み、前記比較および交換命令がスリープ状態である間、前記プロセッサは、前記１つの命令シーケンスに含まれる他の命令の実行を継続し、前記比較および交換命令が起動されてリタイアされるまで、前記他の命令はリタイアされないことを特徴とするシステム。
【請求項１３】
請求項１２に記載の前記システムであって、前記イベントが生じたかを決定するための１つのロック値を有する１つの宛先を監視する監視論理であって、前記宛先の前記監視は、以下の、前記ロック値における１つの変更と、前記ロック値を変更する１つの試行とのうち、１つまたはそれ以上を観測することを含み、前記宛先は、１つの専用レジスタまたは１つのメモリ位置を含む、監視論理と、前記イベントの発生を検出する検出論理と、前記イベントが発生した場合、前記命令を起動する前記スリープ‐起動機構であって、前記イベントは、以下の、前記ロック値が変化した場合は前記ロックが利用可能になったことと、前記ロック値を変更する前記試行が発生した場合は前記ロックが潜在的に利用可能になったこととのうち、１つまたはそれ以上を備える、前記スリープ‐起動機構とをさらに備えることを特徴とするシステム。
【請求項１４】
請求項１２に記載の前記システムであって、前記命令のスリープ化は、以下の、複数の命令をロードすることと、前記複数の命令を実行することとのうち、１つまたそれ以上を含む複数の他のタスクを行うべく、前記第１のプロセッサのための複数のリソースを用いることを放棄することを含むことを特徴とするシステム。
【請求項１５】
請求項１４に記載の前記システムであって、前記複数のリソースの前記放棄は、
１つのレジスタプール内の複数のレジスタを放棄することと、
１つの命令キュー内の複数の命令キュー入力を放棄することと、
１つの記憶バッファ内の複数の記憶バッファ入力を放棄することと、
１つの再順序付けバッファ内の複数の再順序付けバッファ入力を放棄することとを含むことを特徴とするシステム。
【請求項１６】
複数の命令の複数の組を表すデータを記憶する１つの機械読み取り可能媒体であって、複数の命令の前記複数の組は、機械によって実行される場合、以下の、１つのプロセッサにおいて１つの命令シーケンスに含まれる１つの命令を実行して、前記プロセッサのために１つのロックを取得するのに役立つことと、前記ロックが利用可能でない場合、前記プロセッサにおける前記命令をスリープさせることとを含み、前記命令は、１つのイベントが生じるまでスリープすることと、前記プロセッサによる前記ロックを取得するための１つの比較および交換動作を行う１つの比較および交換命令を備えることと、を前記機械に対して行わせ、前記比較および交換動作は、１つのアトミック比較および交換動作を含み、前記比較および交換命令がスリープ状態である間、前記プロセッサは、前記１つの命令シーケンスに含まれる他の命令の実行を継続し、前記比較および交換命令が起動されてリタイアされるまで、前記他の命令はリタイアされないことを特徴とする媒体。
【請求項１７】
請求項１６に記載の前記機械読み取り可能媒体であって、複数の命令の前記複数の組は、前記機械によって実行されると、前記ロックに対応する１つのメモリアドレスを監視することを前記機械に対してさらに行わせ、前記ロックは、１つのメモリの１つの共有メモリ空間に対するプロセッサアクセスを制御することを特徴とする媒体。
【請求項１８】
請求項１６に記載の前記機械読み取り可能媒体であって、複数の命令の前記複数の組は、前記機械によって実行されると、前記イベントが生じたかを決定するための１つのロック値を有する１つの宛先を監視することであって、前記宛先の前記監視は、以下の、前記ロック値における１つの変更と、前記ロック値を変更する試行とのうち、１つまたはそれ以上を観測することを含み、前記宛先は、１つのレジスタまたは１つのメモリ位置を含む、監視と、前記イベントの発生を検出することと、前記イベントが発生した場合、前記命令を起動することであって、前記イベントは、以下の、前記ロック値が変化した場合は前記ロックが利用可能になったことと、前記ロック値を変更する前記試行が発生した場合は前記ロックが潜在的に利用可能になったこととのうち、１つまたはそれ以上を備える、起動と、前記プロセッサのために前記利用可能なロックを取得することとを前記機械に対してさらに行わせることを特徴とする媒体。
【請求項１９】
請求項１６に記載の前記機械読み取り可能媒体であって、前記命令のスリープ化は、以下の、複数の命令をロードすることと、前記複数の命令を実行することとのうち、１つまたそれ以上を含む複数の他のタスクを行うべく、前記プロセッサのための複数のリソースを用いることを放棄することを含むことを特徴とする媒体。
【請求項２０】
請求項１９に記載の前記機械読み取り可能媒体であって、前記複数のリソースの前記放棄は、
１つのレジスタプール内の複数のレジスタを放棄することと、
１つの命令キュー内の複数の命令キュー入力を放棄することと、
１つの記憶バッファ内の複数の記憶バッファ入力を放棄することと、
１つの再順序付けバッファ内の複数の再順序付けバッファ入力を放棄することとを含むことを特徴とする媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の複数の実施形態は、プロセッサに関する。より特定的には、一実施形態は、１つのスリープ‐起動機構を用いて比較および交換動作を行うことに関する。
【背景技術】
【０００２】
典型的には、１つのマルチスレッドのプロセッサまたは１つのマルチプロセッサシステムは、複数の命令シーケンスを同時並行に処理することができる。複数の命令ストリームの実行を行わせる主な動機要因の１つは、その結果生じる処理利用における改善にある。マルチスレッドプロセッサは、異なる実行リソースにおいて、それらのリソースをよりよく利用することを試行して、複数の命令ストリームを同時並行に実行することを可能にする。さらに、マルチスレッドプロセッサは、高い待ち遅延が生じるか、または複数のイベントが生じるのを待つことの多い複数のプログラムについて、用いることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
典型的には、コンピュータシステムは、すべての複数のスレッドまたはプロセッサによって共有されるべき１つの単一リソースセットアップを有する。充分なリソースがないと、複数のプロセッサ（または複数のスレッド）間に重大な競合が生じる理由は、例えば、複数のプロセッサは、バスおよびメモリ帯域をを共有しているからである。この競合が特に明らかなのは、１つまたはそれ以上のプロセッサが１つのセマフォまたはロック（１つの単一プロセッサの他のデータ構造に対する排他的アクセスを許可するのみしばしば用いられるデータ構造のことを指す）が利用可能になるのを待つ場合である。これにより、複数のリソースのボトルネックならびにメモリ帯域、計算帯域、マイクロアーキテクチャ上の複数のリソース、および電力の無駄が生じる。また、複数のプロセッサの「占有待ち」は、システム内の他の複数のプロセッサの性能に対して悪影響を与えうる。
【課題を解決するための手段】
【０００４】
図１は、１つの共有メモリ空間１１４をアクセスする複数のプロセッサ１０２〜１０６を有するコンピュータシステムの一例を示すブロック図である。セマフォ（ロック）１１０は、共有空間１１４に対するアクセス１１２を取得することに関連した値を含むように割り当てられたメモリ１０８における１つの特定の場所である。プロセッサ１０２〜１０６のうちの１つが共有空間１１４にアクセスするためには、まずロック１１０にアクセスして、ロック位置１１０に記憶されたデータの状態（値）をテストし、最も単純な形式では、２つの値のいずれかをロック１１０に割り当てる。第１の値は、アクセス対象の共有空間１１４の利用可能性を示し、第２の値は、共有空間１１４の現在の利用を示すので、現在はアクセスのための利用はできない。また、ビット状態１および０を、ロック１１０のロックおよびロック解除状態のために用いることができる。
【０００５】
メモリ１０８をプロセッサ１０２〜１０６によってアクセスしてデータ転送を行うことは、典型的には、ロードおよび記憶動作の使用を伴う。ロード動作は、メモリ１０８内でアクセスされた１つの位置からメモリの内容を転送するのに対し、記憶動作は、メモリ１０８内でアクセスされたメモリ位置へデータを転送する。よって、ロード／記憶動作を用いて、メモリ１０８およびロック１１０をアクセスして、プロセッサ１０２〜１０６とメモリ１０８との間のデータ転送を行う。ロードおよび記憶アクセスは、それぞれ、読み出しおよび書き込みアクセスとも称される。読み出しを行う場合、キャッシュラインは修正、排他、共有、無効（ＭＥＳＩ）プロトコルなどの１つのプロトコルに従って、「共有未修正」または「排他」または「修正」のいずれかでプロセッサのキャッシュ内に存在する。キャッシュラインがこれらの複数の状態（例えば、無効）のうちの１つの状態で存在しない場合は、プロセッサ１０２〜１０６は、メモリ１０８からラインを取り出して、「共有未修正」または「排他」の状態にする。書き込みを行うためには、プロセッサ１０２〜１０６は、そのキャッシュ内でラインを「排他」または「修正」状態にするか、またはそれを取り出してキャッシュ内に入れて「排他」状態にする。「共有状態」は、同時並行読み出しに利用可能であるが、１つのプロセッサ１０２〜１０６だけが、読み出しまたは書き込みのためにラインを「排他」状態にすることができる。
【０００６】
セマフォの利用可能性を調査してセマフォを使用状態にするための１つの技法の一例は、アトミック読み出し‐修正‐書き込みシーケンス（例えば「テスト＆セット（ＴＳ）機構」）である。同期を実施するための１つの機構は、「比較および交換命令」であって、これは比較的効率的であるが、メモリ位置のキャッシュラインの排他的所有を要求するので、充分に効率的ではない。これにより、他の複数のプロセッサがメモリ位置を同時並行に読み出すことを防止する。
【０００７】
他の例には、「テスト＆テスト＆セット（ＴＴＳ）機構」が含まれる。ＴＴＳ機構は、比較的より効率的であるが、それは、セマフォがフリーでない間、プロセッサが第１のテストについて変数の共有状態の１つのローカルキャッシュコピーをアクセスするからである。しかしながら、１つのプロセッサがロックを取得しており、複数の他のプロセッサがロックを取り合って（例えば、セマフォがフリーかどうか確認するための同時試行読み取り）いる場合、ＴＴＳ機構は、複数の他のプロセッサの阻止またはボトルネックの防止に失敗する。ロック取得プロセッサは、他の全てのキャッシュから強制的に出される「排他」状態のロックのキャッシュラインを取得する。ロックを書き込むことが行われると、複数の他のプロセッサは、読み出しを試みて、それにより、取得プロセッサがその修正されたロック値をメモリに戻して、バストランザクションの１つのシーケンスにおいて、今度は共有されたデータを複数の他のプロセッサに転送する。
【発明を実施するための最良の形態】
【０００８】
以下に説明するのは、１つのスリープ‐起動機構を用いた比較および交換動作を行うための１つのシステムおよび方法である。以下の説明では、本発明の様々な実施形態のより完全理解を提供するために、論理の実施、操作符号、リソース分割、リソース共有、ならびにリソース二重実施、システム構成要素の型および相関性、および論理分割／統合選択肢などの数多くの特定の詳細を説明するであろう。しかしながら、本発明の実施形態は、そのような特定の詳細がなくとも、提供した開示に基づいて実施されるであろうことが、当業者にとって理解されるであろう。本発明を不明瞭にしないために、他のインスタンス、制御構造、ゲートレベル回路、および完全なソフトウェア命令シーケンスは、詳細に示していない。添付の説明で、通常の当業者は、必要以上の実験を行わずに適切な機能性を実現することができるであろう。
【０００９】
本発明の様々な実施形態を以下に説明する。様々な実施形態は、ハードウェア構成要素によって実施されてもよく、または複数の機械実行可能な命令で具体化されてもよく、当該命令は、１つの汎用または専用のプロセッサまたは機械または当該命令がプログラムされた論理回路に様々な実施形態を実施させるために用いられてもよい。代わりに、様々な実施形態は、ハードウェアおよびソフトウェアの１つの組み合わせによって実施されてもよい。
【００１０】
本発明の様々な実施形態は、１つのコンピュータプログラム製品として提供されてもよく、当該コンピュータプログラム製品は、複数の命令を記憶した１つの機械読み取り可能な媒体を含んでもよく、当該命令は、１つのコンピュータに本発明の様々な実施形態に従った１つの処理を実行させるために用いられてもよい。機械読み取り可能な媒体には、フロッピーディスケット、光ディスク、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、消去可能なプログラム可能読み取り専用メモリ（ＥＰＲＯＭ）、電気消去可能なプログラム可能読み取り専用メモリ（ＥＥＰＲＯＭ）、磁気または光カード、フラッシュメモリ、または電気的命令を記憶するために適した他の型の媒体／機械読み取り可能媒体が含まれるが、これに限定されない。さらに、本発明の様々実施形態は、１つのコンピュータプログラム製品としてダウンロードされてもよく、プログラムは、１つの遠隔コンピュータから１つの要求元コンピュータへ、搬送波または他の伝播媒体において実現された複数のデータ信号によって、１つの通信リンク（例えば、１つのモデムまたはネットワーク接続）を介して転送されてもよい。
【００１１】
図２は、命令２００のための１つの符号化手法の一実施形態を示すブロック図である。読み出し‐修正‐書き込み動作を行うための１つの命令（例えば、比較および交換（ＣＭＰＸＣＨＧ））２００を示す。命令２００は、１つの第１のソースデータを読み出し、それを他のソースデータと比較し、比較が所定の基準または条件に適合する場合（例えば、１つの比較が真である場合）、何らかの修正された値が１つの位置に書き込まれる。位置には、第１のソースデータの元の位置が含まれる。所定の条件に適合しない場合、当該位置の元データは変更されない。以下のような他の位置が、元データを除く位置のうち１つを含み、ステータスと共に更新されてもよい。
ｃｍｐｘｃｈｇ，ｓｒｃ（暗黙アキュムレータレジスタと共に）
アキュムレータレジスタＲＡＸは、期待ロック解除値を含む
ｉｆ  ａｃｃｕｍｕｌａｔｏｒ  ＝  ｄｅｓｔ  ｔｈｅｎ
ｚｅｒｏ−ｆｌａｇ  ＝  １
ｄｅｓｔ  ＝  ｓｒｃ
ｅｌｓｅ
ｚｅｒｏ＿ｆｌａｇ  ＝  ０
ａｃｃｕｍｕｌａｔｏｒ  ＝  ｄｅｓｔ
ｅｎｄｉｆ
【００１２】
命令２００には、命令２００をＣＭＰＸＣＨＧ命令として識別するために用いられる１つの操作符号オペランド２０２と、ソースおよび宛先に対応するＳＲＣ１，ＳＲＣ２，ＳＲＣ３，およびＤＥＳＴ２０４〜２１０に関連した複数のオペランドとを含む１つの単一アトミック命令を含む。
【００１３】
図３は、１つの命令２００を実施するための１つの処理アーキテクチャ３００の一実施形態を示すブロック図である。プロセッサ３０２は、１つの実行部３０４と、１つのレジスタファイル３０６（複数のレジスタ３０８を含む）と、１つのバス３１６によって共に結合された１つのデコーダ３１４とを有する中央処理装置（ＣＰＵ）を示す。レジスタファイル３０６には、複数の命令２００を実行するために実行部３０４によってアクセスされる複数のレジスタ３０８の１つの組が含まれる。命令２００には、図２の１つのＣＭＰＸＣＨＧ＿ＳＷ命令またはスリープ‐起動機構を有する１つの比較および交換命令（ＣＭＰＸＣＨＧ＿ＳＷ命令）の一実施形態が含まれる。
【００１４】
命令２００は、実行部３０４内に常駐するように示されており、複数の点線が、命令２００のオペランド２０２〜２１０からレジスタファイル３０６内の複数の対応するレジスタ３０８へと示されており。デコーダ３１４を用いて、命令２００をデコードして実行する。メモリ３２０は、１つのバス３１８を介して、バスインターフェイス部（ＢＩＵ）３１２と通信する。ＢＩＵ３１２を用いて、メモリ３２０およびプロセッサ３０２間でデータを転送する。命令２００についてのプログラムルーチン（動作シーケンス）は、メモリ３２０内に常駐することが意図されている。命令２００の実行前に、ＳＲＣ１、ＳＲＣ２、およびＳＲＣ３が複数のレジスタ３０８にロードされてもよい。一実施形態において、１つの処理‐比較‐オペランド（ＰＣＯ）レジスタ（図示せず）を用いて、命令２００の実行中の互いに異なる期間でのＳＲＣ２および／またはＤＥＳＴについての１つのレジスタとして機能してもよい。別の言い方をすれば、実行前に、ＳＲＣ１およびＳＲＣ３が複数のレジスタ３０８にロードされる一方で、ＳＲＣ２の情報がＰＣＯレジスタにロードされ、ＳＲＣ２情報についての専用レジスタとしての役割を果たす。
【００１５】
一実施形態において、命令２００には、ＣＭＰＸＣＨＧ＿ＳＷ命令が含まれ、それについて、スリープ‐起動機構を伴う比較および交換動作（ＣＭＰＸＣＨＧ＿ＳＷ機構）が処理アーキテクチャ３００によって実施および実行される。そのような機構は、（例えば、プロセッサ３０２において実施された）ハードウェアおよび／またはソフトウェア（例えば、機構の様々な機能を実施および実行するための同期符号）を用いて実施されてもよい。一実施形態において、（共有メモリ空間３２６に対するアクセスを得るための）所望のロック３２２が他のプロセッサによって取得されるなどで利用可能でない場合に、ＣＭＰＸＣＨＧ＿ＳＷ機構を用いて、１つのＣＭＰＸＣＨＧ＿ＳＷ命令をスリープさせる。その次に、取得プロセッサが共有メモリ空間３２６に対するアクセスを完了した場合、その後、今度は他のプロセッサが共有メモリ空間３２６に対するアクセス制御をすることができるように、ロック３２２を開放（またはロック解除）状態に再設定する必要がある場合がある。システムが共有メモリ３２６に対する制御をどのように解除するかは、１つの設計上の選択である（例えば、システムアーキテクチャによって要求されたようにする）。例えば、１つのロック解除されたステータス値が、直接ロック３２２に書き込まれてもよいし、または１つのレジスタ３０８に書き込み／セーブされてもよい。ＣＭＰＸＣＨＧ＿ＳＷ機構は、図７〜９を参照して、さらに開示される。
【００１６】
図４は、本発明の１つまたはそれ以上の実施形態を実施するのに用いられるコンピュータシステム４００の一例を示すブロック図である。コンピュータシステム（システム）は、１つまたはそれ以上のプロセッサ４０２〜４０６を含む。プロセッサ４０２〜４０６は、１つまたはそれ以上の単一スレッドまたは多スレッドプロセッサを含んでもよい。１つの典型的な多スレッドプロセッサは、複数のスレッドまたは複数の論理プロセッサを含んでもよく、複数の命令シーケンスをその複数のスレッドを用いて同時並行に処理できてもよい。また、プロセッサ４０２〜４０６は、１つまたはそれ以上のキャッシュ内部レベル（図示せず）と、プロセッサバス４１２と直接対話する１つのバスコントローラまたはバスインターフェイス部とを含んでもよい。
【００１７】
プロセッサバス４１２は、ホストバスまたはフロント側バスとしても知られるが、プロセッサ４０２〜４０６をシステムインターフェイス４１４に結合するために用いられてもよい。プロセッサバス４１２は、１つの制御バス４３２と、１つのアドレスバス４３４と、１つのデータバス４３６とを含んでもよい。制御バス４３２、アドレスバス４３４、およびデータバス４３６は、マルチドロップの双方向バスであってもよく、例えば、１つの２地点間バスに対向して３つまたはそれ以上のバスエージェントに接続されており、当該２地点間バスは、２つのバスエージェント間だけに接続されていてもよい。
【００１８】
システムインターフェイス４１４（またはチップセット）は、プロセッサバス４１２に接続されて、システム４００の複数の他の構成要素をプロセッサバス４１２にインターフェイスで連結させてもよい。例えば、システムインターフェイス４１４は、１つのメインメモリ４１６をプロセッサバス４１２にインタフェースで連結させるための１つのメモリコントローラ４１８を含んでもよい。メインメモリ４１６は、典型的には、１つまたはそれ以上のメモリカードと、１つの制御回路（図示せず）とを含む。また、システムインターフェイス４１４は、１つの入力／出力（Ｉ／Ｏ）インターフェイス４２０を含んでもよく、１つまたはそれ以上のＩ／ＯブリッジまたはＩ／Ｏ装置をプロセッサバス４１２にインターフェイスで連結させる。例えば、図示のように、Ｉ／Ｏインターフェイス４２０は、１つのＩ／Ｏブリッジ４２４をプロセッサバス４１２にインターフェイスで連結してもよい。Ｉ／Ｏブリッジ４２４は、システムインターフェイス４１４および１つのＩ／Ｏバス４２６の間のインタフェースする１つのバスブリッジとして動作してもよい。１つまたはそれ以上のＩ／Ｏコントローラおよび／またはＩ／Ｏ装置が、Ｉ／Ｏバス４２６に接続されて、図示のように、Ｉ／Ｏコントローラ４２８およびＩ／Ｏ装置４３０のようなものに接続されてもよい。Ｉ／Ｏバス４２６は、１つの周辺構成要素相互接続（ＰＣＩ）バスまたは他の型のＩ／Ｏバスを含んでもよい。
【００１９】
システム４００は、メインメモリ４１６と称される、１つのダイナミック記憶装置、もしくは１つのランダムアクセスメモリ（ＲＡＭ）またはプロセッサバス４１２に結合されて情報およびプロセッサ４０２〜４０６によって実行されるべき複数の命令を記憶するための他の装置を含んでもよい。また、メインメモリ４１６は、プロセッサ４０２〜４０６による複数の命令の実行中に複数の一時的な変数または他の中間情報を記憶するために用いられてもよい。システム４００は、プロセッサバス４１２に結合されて静的情報および複数の命令をプロセッサ４０２〜４０６のために記憶するための１つの読み取り専用メモリ（ＲＯＭ）および／または他の静的記憶装置（図示せず）を含んでもよい。
【００２０】
メインメモリ４１６またはダイナミック記憶装置は、情報および複数の命令を記憶するための１つの磁気ディスクまたは１つの光学ディスクを含んでもよい。Ｉ／Ｏ装置４３０は、１つの陰極線管（ＣＲＴ）または液晶ディスプレイ（ＬＣＤ）のような、１人のエンドユーザに対して情報を表示するための１つの表示装置（図示せず）を含んでもよい。例えば、インストールステータス、施行期間における残り時間、および他の情報の図および／またはテキストによる複数の表示を、見込み購買客に対して表示装置上に提示してもよい。また、Ｉ／Ｏ装置４３０は、１つの英数字入力装置のような、情報および／または複数のコマンド選択をプロセッサ４０２〜４０６に対して通信するための複数の英数字および他のキーを含む１つの入力装置（図示せず）を含んでもよい。他の型のユーザ入力装置としては、１つのマウス、１つのトラックボール、または複数のカーソル方向キーなどの、プロセッサ４０２〜４０６に対する方向情報および複数のコマンド選択を通信して、表示装置上におけるカーソルの動きを制御するためのカーソル制御器が含まれる。
【００２１】
また、システム４００は、例えば１つのローカルまたはワイドエリアネットワークをサポートする１つの通信リンクを提供するためにイーサネット、トークンリング、または複数の他の型の物理的接続機構に結合するための、１つのモデム、１つのネットワークインターフェイスカード、もしくは、複数の他の周知のインターフェイス装置のような、１つの通信装置（図示せず）を含んでもよい。別の言い方をすれば、システム４００は、数多くのクライアントおよび／またはサーバに対して、例えば１つの会社のイントラネットまたはインターネットのような１つの従来のネットワークインフラストラクチャを介して結合されてもよい。
【００２２】
上述の例より少なくまたは多く装備された１つのシステムが、ある実施については望ましい場合もあることが理解される。したがって、システム４００の構成は、価格上の制約、性能要件、技術上の改良、および／または他の状況などの数多くの要因によっては、実施毎に異なる場合がある。
【００２３】
注意すべきなのは、本明細書において説明されている複数の実施形態は、プロセッサ４０２〜４０６などの１つのプログラムされたプロセッサの制御下で実施されるが、代替実施形態においては、実施形態は、複数のフィールドプログラム可能ゲートアレイ（ＦＰＧＡ）、複数のトランジスタトランジスタ論理（ＴＴＬ）、または複数の特定用途向け集積回路（ＡＳＩＣ）などの任意のプログラム可能またはハードコードによる論理によって、全体的または部分的に実施されてもよい。加えて、本発明の複数の実施形態は、複数のプログラムされた汎用コンピュータ構成要素および／または複数のカスタム化されたハードウェア構成要素によって実施されてもよい。したがって、本明細書に開示された事項は、列挙された複数の実施形態が複数のハードウェア構成要素の１つの特定の組み合わせによって実施されるといった、本発明の様々な実施形態を１つの特定の実施形態に限定するように解釈されるものではない。
【００２４】
図５は、本発明の１つまたはそれ以上の実施形態を実施するのに用いられる１つのマルチスレッドプロセッサ５００の一実施形態を示すブロック図である。一実施形態によれば、１つのプロセッサ５００は、１つの単一集積回路として形成されてもよい。他の実施形態によれば、複数の集積回路が共に１つのプロセッサ５００を形成してもよく、また別の実施形態によれば、複数のハードウェアおよびソフトウェアルーチン（例えば、複数のバイナリ変換ルーチン）が共にプロセッサ５００を形成してもよい。プロセッサ５００は、図４のプロセッサ４０２〜４０６のうちの１つまたはそれ以上を含んでもよい。図示のように、１つのバス／メモリコントローラ５２０は、１つのフロントエンド５３０に対して実行するための複数の命令を提供してもよい。フロントエンド５３０は、複数の命令ポインタ５７０に従って、様々なスレッドから複数の命令の取り出しを導いてもよい。命令ポインタ論理は、再現されて、複数のスレッドをサポートしてもよい。
【００２５】
一実施形態によれば、フロントエンド５３０は、複数の命令を複数のスレッド／プロセッサ分割可能リソース５４０に対してさらなる実行のために与えてもよい。複数のスレッド／プロセッサ分割可能リソース５４０は、複数のスレッドがプロセッサ５００内でアクティブの場合に、複数の特定のスレッド専用の論理的に別個の複数の区画を含んでもよい。複数のスレッド／プロセッサ分割可能リソース５４０は、例えば、複数の命令キューを含んでもよい。１つの単一スレッドモードの場合、複数のスレッド／プロセッサ分割可能リソース５４０の複数の区画を組み合わせて、１つのスレッド専用の１つの単一の大きな区画を形成してもよい。
【００２６】
一実施形態によれば、プロセッサ５００は、再現状態５８０をも含んでもよい。再現状態５８０は、１つの論理プロセッサについてコンテキストを維持するのに充分な複数の状態変数を含んでもよい。再現状態５８０で、複数のスレッドが状態変数記憶の競合なしに実行してもよい。加えて、レジスタ割り当て論理が各スレッドについて再現されてもよい。再現状態関連論理は、複数の入力命令を実行のために準備するための適切なリソース区画と共に動作してもよい。
【００２７】
一実施形態によれば、複数のスレッド／プロセッサ分割可能リソース５４０は、複数の共有リソース５５０に対して複数の命令を渡してもよい。複数の共有リソース５５０は、複数の命令の出所に関係なく、複数の命令で動作してもよい。例えば、複数のスケジューラおよび実行部が、スレッドを意識しない複数の共有リソースであってもよい。複数の分割可能リソース５４０は、各アクティブスレッドにおいて継続的な進行を提供する１つの公平なやり方で、複数のスレッド間で交互に行うことによって、複数の命令を複数のスレッドから複数の共有リソース５５０に対して与えてもよい。
【００２８】
一実施形態によれば、複数の共有リソース５５０の後に、複数のスレッド／プロセッサ分割可能リソース５６０の別の組が続いてもよい。複数のスレッド／プロセッサ分割可能リソース５６０は、１つの再順序付けバッファなどの複数の廃棄リソースを含んでもよい。したがって、複数のスレッド／プロセッサ分割可能リソース５６０は、各スレッドからの複数の命令の実行が適切に終了し、かつ当該スレッドについて適切な状態が適切に更新されることを確実にしてもよい。
【００２９】
一実施形態によれば、１つのメモリ位置の一定のポーリングまたは複数の命令の実行すら必要とせずに、スリープ‐起動比較および交換を介して効率的な同期機能を実施する１つの機構が、複数のプログラマに対して提供されてもよい。例えば、メモリアクセスモニタ５１０は、メモリアクセスモニタ５１０が監視を許可されるであろう１つのメモリアクセス位置についての情報をプログラム可能であってもよい。従って、メモリアクセスモニタ５１０は、１つのモニタ位置情報レジスタ５１２を含んでもよく、モニタ位置情報レジスタは、比較論理５１４を用いてバス／メモリコントローラ５２０から受信したメモリ位置情報に対して比較される。
【００３０】
モニタ位置情報レジスタ５１２は、命令を再開または呼び起こさせるであろう周期の型および／またはアドレスを規定する詳細含んでもよい。モニタ５１０は、レジューム信号を開始する１つのタイムアウトカウンタを含んでもよい。また、モニタ５１０は、１つのバスを渡る情報に対応するアドレスを含む１つのレジスタ５１２を含んでもよい。バスおよび（例えば、タイムアウトカウンタを有する）レジスタ５１２間の１つの比較が行われる。任意の周期は、１つの明示的な書き込み周期の形式であってもよく、または所有のための１つの読み出し（例えば、キャッシュラインの排他的所有となる行為）または１つのキャッシュ可能なラインの排他的所有を得ようと試みる他のエージェントによる１つの無効化周期であってもよい。
【００３１】
図６は、ＣＭＰＸＣＨＧ＿ＳＷ機構６１４〜６１８を用いた複数のプロセッサ６０２〜６０６を有する１つのシステム６００の一実施形態を示すブロック図である。図示のように、システム６００は、１つのロック６３４を取り合う複数のプロセッサ６０２〜６０６を含み、ロックは、メモリ６３２内の共有空間／変数６３６に対する（矢印６３８によって示すような）複数のアクセスを制御するように割り当てられる。示された実施形態において、各プロセッサ６０２〜６０６は、ＣＭＰＸＣＨＧ＿ＳＷ機構６１４〜６１６を用い、当該機構は、各プロセッサ６０２〜６０６上で実施されたハードウェアであってもよく、ソフトウェアベースの１つの同期符号を用いて実行される。また、命令シーケンス例６２０〜６２４は、各プロセッサ６０２〜６０６について、一実施形態の明確性およびよりよい理解のために示されている。
【００３２】
図示のように、ＣＭＰＸＣＨＧ＿ＳＷ命令６０８は、プロセッサ６０２上で実行され、共有メモリ空間６３６に対するアクセスのためのロック６３４を取得するのに成功する。メモリ６３２の共有空間６３６は、プロセッサ６０２がセマフォを所有している期間、用いられてもよいが、プロセッサ６０２は、取得処理の間、排他状態のロック６３４を取得して、ロック６３４に対する複数の他の行為を防止してもよい。その後、共有状態を用いて、ロック６３４の１つのコピーを共有してもよい。一実施形態において、他のプロセッサ６０４〜６０６は、フリーでないロック６３４を試行する場合、プロセッサ６０４〜６０６におけるＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２をスリープにする。別の言い方をすれば、例えば、プロセッサ６０４が取得したロック６３４を得ようとシークする場合、ロック６３４はプロセッサ６０２によって使用中であることを示す１つの値がメモリ６３２から返されて、一実施形態において、ロック６３４が利用可能になるまでプロセッサ６０４を１つの連続する「ｗｈｉｌｅ」ループに入れる代わりに、プロセッサ６０４におけるＣＭＰＸＣＨＧ＿ＳＷ命令６１０をスリープさせる。同様に、プロセッサ６０６がシークしていて取り合いとなっているロック６３４がふさがっている場合、プロセッサ６０６におけるＣＭＰＸＣＨＧ＿ＳＷ命令６１２をもスリープさせる。
【００３３】
一実施形態において、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２を１つのスリープ状態にすることは、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２はアイドルであり、それを起動またはトリガする１つのイベントを待っていることを示す。ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２がアイドルまたはスリープ状態である間、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２が起動、実行、およびリタイアされるまで、プロセッサ６０６〜６０８は、複数の他の命令６２８〜６３０の実行などといった複数の他のタスクの実行を継続していてもよい。但し、命令６２８〜６３０は、リタイアされることはないであろう。別の言い方をすれば、任意の後続のロード（例えば、命令６２８または６３０）はその値を得て、複数の所定のタスクおよび計算を行うことができるが、プロセッサ６０４〜６０６において１つの一時的または投機的な状態で待機しうる。再順序バッファ（ＲＯＢ）からの任意の命令を順不同で実行できるが、最も古いＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２が起動されてリタイアされるまでは、まだ投機的段階にある新規またはより若い命令６２８〜６３０は、リタイアされなくてもよい。
【００３４】
プロセッサ６０４〜６０６に様々なタスクを行わせて、ローカルの共有コピー上で継続的にスピン待ち（ロードおよび比較）する代わりに、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２がスリープである間、プロセッサ６０４〜６０６がブロックまたはボトルネックしないようにするのに役立つ。この技法により、電力および時間の節約、ならびに性能の向上に役立つ。さらに、本技法は、同期している複数の処理の間で動的なデータ共有のない、同時並行進行に役立つ。例えば、１つのハッシュテーブルを１つのロック６３４によって保護して、複数の処理が同時にそれを更新しないようにすると想定すると、２つの処理がハッシュテーブルの互いに異なる部分の更新を必要とした場合（例えば、互いに異なるビンに要素を追加する）、本技法は、当該２つの処理が同時に進行することを許可しうる。これは、たとえ任意の他のプロセッサを動的に妨害しなくても、任意の他のプロセッサ上の全ての有益なワークを完全にブロックするという犠牲の上で、１つのプロセッサに更新を行わせるということと区別される。例えば、プロセッサ６０２は、ロックを所有して、適切なハッシュテーブルビンを見つけて、それをその値で更新してもよい。ところで、ロックを所有していないプロセッサ６０４も、適切なビンを見つけ、書き込まれるべき値および位置を準備してもよいが、プロセッサ６０４がロックを取得しＣＭＰＸＣＨＧ＿ＳＷ命令６０８をリタイアできるまでは、ハッシュテーブルを更新する複数の命令をリタイアしなくてもよい。
【００３５】
一実施形態において、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２の起動は、１つのイベントの発生でトリガされうる。イベントは、例えば、ロック６３４が解除される（そして、利用可能になる）こと、または（命令シーケンス例６２０において）ロック６３４を有するプロセッサ６０２によって１つの試行がなされて、ロック６３４の潜在的な利用可能性を示すロック値を書き換えることである。例えば、命令６１０がスリープ状態にある間、プロセッサ６０４は、１つの新たなロック値（例えば、ロックが解除される）をシークするか、または１つのプロセッサによるロック値を変更しようとする１つの試行（例えば、ロックが場合によっては解除され、共有空間６３６を含むキャッシュラインが無効化され、ロック６３４を含むキャッシュラインが無効化される）を観測することによって、ロック６３４の利用可能性を監視してもよい。１つのプロセッサによってロック値を変更しようとする試みがなされると（例えば、プロセッサ６０２が、ロック変数に書き込みを行う排他的所有を得るために、プロセッサ６０４〜６０６の（図示しない）複数のキャッシュ内の変数を無効化する）、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０の起動がトリガされる。その後、プロセッサ６０４は、新たな値を読み出し、再び、共有空間６３６内のロック６３４（例えば、ロック変数）を要求して、要求に応答してロック変数６３４を受信し、ＣＭＰＸＣＨＧ＿ＳＷ命令６１０が実行およびリタイアされ、（ＣＭＰＸＣＨＧ＿ＳＷ６１０命令がスリープしている間に実行された）複数の任意の他の命令６２８も、その後リタイアされる。プロセッサ６１０をスリープさせることによって、プロセッサ６０４は、典型的なロード、比較、および分岐シーケンスを通る継続的なストリーミングを回避することで、効率性を高めかつ電力を節約するのに役立つ。
【００３６】
一実施形態において、待ち（「Ｗｈｉｌｅ」ループ）がハードウェアにおいて実施されてもよいので、ＣＭＰＸＣＨＧ＿ＳＷ機構６１４〜６１８は、１つのソフトウェアベースのスピンループを回避するのに役立つ。一実施形態において、ＣＭＰＸＣＨＧ＿ＳＷ機構６１４〜６１６はハードウェアおよび／またはソフトウェアに基づいており、「Ｗｈｉｌｅ」ループをＭＰＸＣＨＧ＿ＳＷ命令６１０〜６１２のスリープに統合することで、「Ｗｈｉｌｅ」ループの継続的な実行を回避するのに役立つ。機構６１４〜６１６を実施および同期させるための同期符号の一例には、以下のものが含まれる。
ｅａｘ（ａｃｃｕｍｕｌａｔｏｒ）＝０  ／／  ０はフリーを示す
ｅｃｘ  ＝  １                    ／／  １はロック済みを示す
ｌａｂｅｌ：  ｃｍｐｘｃｈｇ  ［ｌｏｃｋ＿ｖａｒ］，ｅｃｘ；
／／  ｌｏｃｋ＿ｖａｒ  ＝  ０であれば、１  ｚｆに設定、ｌｏｃｋ＿ｖａｒ  ＝  １を設定
／／それ以外はｓｌｅｅｐ
ｊｎｅ  ｌａｂｅｌ            ／／  取得に失敗したら、再試行  
ｉｎｓｔｒ１；    ／／  複数の臨界領域命令  
ｉｎｓｔｒ２；    ／／  複数の臨界領域命令  
ｌｏｃｋ＿ｖａｒ  ＝  ０；      ／／  ロック解除
【００３７】
符号中、ｅａｘおよびｅｃｘ（また、ｅｂｘ，ｅｄｘなど）は、様々なレジスタを指し、また、総称して、Ｒ１またはＲｅｇ１，Ｒ２またはＲｅｇ２，Ｒ３またはＲｅｇ３，などとして知られ、ｚｆは、プロセッサのゼロフラグ状態レジスタを指し、および、ｊｎｅ（等しくなければジャンプ）は、試行が成功したかどうかを判断することを指し、試行が成功なかった場合は、ラベル（例えば、ｊｎｅラベル）に分岐して戻って、１つの命令を実行する。
【００３８】
図７は、ＣＭＰＸＣＨＧ＿ＳＷ機構を実行するための１つの処理の一実施形態を示すフロー図である。まず、処理ブロック７０２において、１つのマルチプロセッサシステムにおける１つのプロセッサは、１つのロックを取得するためにシークする。シークは、ロックの１つの排他的所有を必要としなくともよく、代わりに、ロックは１つの共有状態で取得されてもよいことが意図されている。判断ブロック７０４において、ロックが利用可能かどうかについての判断がなされる。ロックが利用可能な場合、プロセッサは、処理ブロック７０６において、従来の比較および交換動作を用いてそれを取得する。
【００３９】
一実施形態において、ロックが利用可能でない場合、処理ブロック７０８において、プロセッサにおけるＣＭＰＸＣＨＧ＿ＳＷ命令は、例えばロック値の１つの変化（または１つの試行済み変化）で起動されるまで、スリープされる。別の言い方をすれば、ロックが利用できない旨を示すメモリからの値がプロセッサに一旦返されると、ＣＭＰＸＣＨＧ＿ＳＷ命令を「Ｗｈｉｌｅ」ループ内で継続的にスピンさせて各ループでロックを再要求する代わりに、ロックをシークしているプロセッサにおけるＣＭＰＸＣＨＧ＿ＳＷ命令は、スリープされる。処理ブロック７１０において、プロセッサのメモリシステムは、ロックの利用可能性または潜在的な利用可能性を示しうるロック値のいかなる変化をも監視する。例えば、ロックにアクセスするプロセッサは、ロック値を変更しようと試行して、複数の他のプロセッサについてのロックを解除して、シークおよび取得を行ってもよい。そのような行為は、メモリシステムによって観測されてもよいし、スリープしているＣＭＰＸＣＨＧ＿ＳＷ命令を起動して、生じうるロック利用可能性を見守ってもよい。
【００４０】
一実施形態において、ＣＭＰＸＣＨＧ＿ＳＷ命令がスリープ中に、プロセッサのメモリシステムは、ロック値の変化を監視する。さらに、ＲＯＢ内の複数の他のＣＭＰＸＣＨＧ＿ＳＷおよびロード命令を含む複数の他の命令をロードおよび実行して、プロセッサが処理ブロック７１２において複数の他のタスクの実行を継続してもよい。言い換えれば、プロセッサにおけるＣＭＰＸＣＨＧ＿ＳＷ命令のスリープは、プロセッサを１つの継続スピンまたは「Ｗｈｉｌｅ」ループに入れさせないだけでなく、プロセッサをブロックまたは無能にしない。代わりに、順不同ではあるが、任意の数の後続の命令を臨界領域内にロードおよび投機的に実行してもよいが、最も古い命令（例えば、スリープしているＣＭＰＸＣＨＧ＿ＳＷ命令）がリタイアされるまでは、スリープしているＣＭＰＸＣＨＧ＿ＳＷ命令より若い命令は、リタイアされないようにしてもよい。どのプロセッサもブロックされず、複数の有益なタスクの実行を継続するので、電力時間の節約および性能の改善となる。
【００４１】
判断ブロック７１４において、ロック値が変化したか、または値を書き換えようとする試行がなされたかについての判断がなされる。もしそうでなければ、処理ブロック７１２において、複数の他の命令を実行する処理が継続する。しかしながら、ロック値を変更しようとする試行がなされたか、または値が変更された場合には、スリープしているＣＭＰＸＣＨＧ＿ＳＷ命令の起動が、処理ブロック７１６においてトリガされる。ＣＭＰＸＣＨＧ＿ＳＷ命令がいったん起動されて、ロックが利用可能となると、ロックは、処理ブロック７０６においてプロセッサによって取得される。ＣＭＰＸＣＨＧ＿ＳＷ命令の起動の一部として、その後、ＣＭＰＸＣＨＧ＿ＳＷ命令はリタイアされてもよい。また、臨界領域における、投機的に実行が行われた任意の後続の命令も、リタイアされてもよい。
【００４２】
図８は、ＣＭＰＸＣＨＧ＿ＳＷ機構を実施するための１つの状態機械８００の一実施形態を示すブロック図である。キャッシュラインがプロセッサ内で利用可能で、かつロックが利用可能である場合、初期ソフトウェア「Ｗｈｉｌｅ」ループが渡されて、命令（例えば、ＣＭＰＸＣＨＧ＿ＳＷ命令）が実行される。図示のように、ロードが８０２で発行される。キャッシュラインについて１つのヒット８０４があり、かつ、値を読み出した後に、ロックが利用可能である（ロックが「ロック解除された」）と判断された場合には、キャッシュラインの所有のための読み出し（ＲＦＯ）８０６を求める１つの要求が発行される。その後、ロックをアトミックに取得するための機構が開始されることにより、ロードなどの様々なマイクロ命令（ｕｏｐｓ）が開始されることとなる。
【００４３】
一実施形態において、ロードが８０２で発行されるが、８１０でキャッシュラインがミスされるかまたは他のプロセッサがそれを保持（例えば、ロックされる）か、もしくは単に、読み出しまたはロックされているか否かを知るのに充分なデータがキャッシュ内にない、ということなる。これには、バスを介して得るには多少時間がかかる場合があり、実行するのに数クロックかかる場合がある。これにより、８１２でメモリ順序バッファ（ＭＯＢ）内のロードがスリープすることになる。８１２でＭＯＢを用いて、ロードを含みかつバッファを記憶して、メモリ動作の適切な順序付けが保持されることを確実なものとする。また、ＭＯＢを用いて、１つのキャッシュミス、メモリ順序依存性、スリープ条件など、何らかの理由で完了しなかった複数のロードを再発行する。さらに、ＭＯＢは、複数のロードが完了しなかった複数の理由を追跡して、完了を妨げて条件に対処した後に、それらを起動する。一実施形態において、データはキャッシュ内にあり、値を読み出した後、８１０で、ロックされているか（例えば、他のプロセッサが所有しているか）が判断される。これにより、８１２でＭＯＢ内でロードがスリープすることとなる。一実施形態において、（１）キャッシュラインが利用可能になる場合（例えば、プロセッサのキャッシュ内にある場合）または（２）他のプロセッサが変数内の値を書き換えようとする場合のいずれかである場合、キャッシュラインを潜在的に利用可能にすると、ロードが８１４で起動するようにしてもよい。ロードが８１６で再発行され、８１８でキャッシュラインが利用可能である場合（例えば、１つのヒットがある場合）でかつロックが利用可能な（ロック解除された）場合、８０６で所有の要求が発行される。しかしながら、８２０でさらなるミスがある場合、８１２でロードはスリープに戻る。
【００４４】
一実施形態において、１つのタイムアウトカウンタを導入して、スリープ時間に対して１つの制約を提供してもよい。例えば、タイムアウトカウンタ８２２の開始で、プロセッサが８１２でスリープを開始してから所定の時間量が経過した後、スリープ時間は終了する。別の言い方をすれば、プロセッサは、他のプロセッサまたは１つのイベントによる起動を諦めて、代わりに、他のタスクを行う（例えば、処理ステップ８０６へ進む）。例えば、タイムアウトカウンタが必要となるのは、１つのロックが１つのイナクティブなプロセッサによって所有される場合であって、それにより、複数の他のプロセッサがロックを取得することがほとんどまたは全くできない状態で待つこととなりうる場合である。一実施形態において、タイムアウトカウンタによって起動されると、命令はロックを取得しようと試行して、１つの失敗条件でリタイアとなってもよい。他の実施形態において、起動されると、命令はロック取得の試行を風刺して、単に１つの失敗条件でリタイアとなってもよい。また、ロックを待つプロセッサ（例えば、スリープモードのＣＭＰＸＣＨＧ＿ＳＷ命令を有するプロセッサ）は、８２４でタイムアウトして、特定のロックを取得するのを諦め、複数の他のタスクを行って、効率的であることを継続する。また、８２４のタイムアウトにより、８１２のスリープ状態から抜け出すことになり、プロセッサが当分の間ロック取得をシークすることを示すこととなりうるが、他のプロセッサがラインを書き込んでいることを示すキャッシュの無効化を証明することはできなかった。
【００４５】
ＣＭＰＸＣＨＧ機構は、インテルのペンティアムプロセッサのような、任意の数のマイクロプロセッサアーキテクチャにおいて実施されてもよいし、かつそれらとの互換性があってもよい。そのようなアーキテクチャにおける変化は、プロセッサのＭＯＢおよびデータキャッシュ部（ＤＣＵ）とっては些細なものであってもよく、「スリープ」モードを実施するための状態機械８００をＤＣＵ内に設置してもよい。例えば、メモリシステム内の３ビットのデータを用いて、ロック済みまたはロック解除を示してもよく、それによって、１つのレジスタ（例えば、ｅａｘ）の最下位の３ビットに対して比較を行うことができる。しかしながら、任意の数のビット（例えば、３２）をメモリシステムにおいて用いて、ロック済み／ロック解除状態を示すことができ、数は必要なまたは所望の方法で分割することができる（例えば、ロックおよびロック解除のビットは、必ずしも等しくなくてもよい）。さらに、ＣＭＰＸＣＨＧ＿ＳＷ機構は、０および１の値をそれぞれロック解除およびロック値に用いて、３つの最下位ビットが充分であるようにしてもよい。一実施形態において、１つのスレッドが、１および０の代わりに、１つの識別（ＩＤ）値を挿入して、状態を示すことができる。また、任意のゼロでない値がロックを示す一方で、０がフリーを示すこともできる。一実施形態において、３ビットの期待フリー値と、メモリからロードされた複数のビットの値とが異なる場合、ロックはフリーでないとみなされるが、値が一致したら、ロックはフリーとみなされてもよいし、またはみなされなくてもよい。例えば、比較によって、現在の値と、ロック解除された値との１つの部分的な一致を示してもよい。部分的な比較によって、ロック取得の１つの試行を開始する１つの動作（例えば、処理ブロック８０６および８０８）を開始してもよい。しかしながら、すべてのビットをＣＭＰＸＣＨＧ＿ＳＷ機構を用いて比較する場合は、動作により、ロックが他のプロセッサによって取得されていることがわかる場合があり、符号内の分岐を取って再試行する場合がある。
【００４６】
一実施形態において、例えば、比較器がｅａｘ［２：０］の値（例えば、ｅａｘの下位３ビット）を保持し、データがｌｏａｄ＿ｗｉｔｈ＿ｓｔｏｒｅ＿ｉｎｔｅｎｔ  ｕｏｐのための１つのキャッシュ（例えば、Ｌ１キャッシュ）から返された場合は、ｅａｘ比較器に対して比較される。ｌｏａｄ＿ｗｉｔｈ＿ｓｔｏｒｅ＿ｉｎｔｅｎｔ  ｕｏｐは、ｃｍｐｘｃｈｇ＿ｓｗ命令の１つの構成ｕｏｐであり、使用中のメモリ位置の値を、１つのロック変数としてロードする。２つが等しい場合、値はライトバックバス上に書き戻される。２つが等しくない場合、ＤＣＵはライトバックを打ち切って、ロードをＭＯＢ内でスリープさせ、タイムアウトカウンタを開始する。ＭＯＢがロックキャッシュラインについて１つの無効化スヌープを検出する場合、ｌｏａｄ＿ｗｉｔｈ＿ｓｔｏｒｅ＿ｉｎｔｅｎｔ  ｕｏｐを起動および再発信する。その後、タイムアウトカウンタは、クロック毎に減分されてもよい。０に等しい場合、ＤＣＵは、１つのタイムアウト信号をＭＯＢに送ってもよい。ＭＯＢは、タイムアウト信号を受信するときに、ｌｏａｄ＿ｗｉｔｈ＿ｓｔｏｒｅ＿ｉｎｔｅｎｔ  ｕｏｐを発信する。この発信中に、ｌｏａｄ＿ｗｉｔｈ＿ｓｔｏｒｅ＿ｉｎｔｅｎｔ  ｕｏｐは実行完了し、比較結果に関係なく、リタイアとなる。
【００４７】
本発明の実施形態例の上述の説明において、様々な進歩的な局面の１つまたはそれ以上を理解する助けとなる開示を効率的に行う目的で、本発明の様々な特徴が共に１つの単一実施形態、図面、またはその説明にグループ化されることがあることが、理解されるべきである。複数の所定の実施形態例が複数の添付図面において説明されかつ示されてきたが、そのような複数の実施形態は例示にすぎず、限定的ではないこと、および本発明の複数の実施形態は、図示および説明された複数の特定の構成および仕組みに限定されるべきものではないことが理解されるべきである。なぜなら、本開示を検討した当業者にとって様々な修正が生じうるからである。
【図面の簡単な説明】
【００４８】
添付の複数のクレームは、本発明の複数の特徴を詳細に説明する。本発明の複数の実施形態およびその複数の利点は、添付の複数の図面と共に以下の詳細な説明から、最もよく理解されるであろう。  
【図１】１つの共有メモリ空間をアクセスする複数のプロセッサを有するコンピュータシステムの一例を示すブロック図である。
【図２】１つの命令についての１つの符号化手法の一実施形態を示すブロック図である。
【図３】スリープ‐起動機構を用いた比較および交換動作を有する１つの処理アーキテクチャの一実施形態を示すブロック図である。
【図４】本発明の１つまたはそれ以上の実施形態を実施するのに用いられるコンピュータシステムの一例を示すブロック図である。
【図５】本発明の１つまたはそれ以上の実施形態を実施するのに用いられるマルチスレッドプロセッサの一例を示すブロック図である。
【図６】スリープ‐起動機構を用いた比較および交換動作を行う複数のプロセッサを有する１つのシステムの一実施形態を示すブロック図である。
【図７】スリープ‐起動機構を用いた比較および交換動作を行うための１つの処理の一実施形態を示すフロー図である。
【図８】スリープ‐起動機構を用いた比較および交換動作のための状態機械の一実施形態を示すブロック図である。
【図１】
0005054665.tif 000002
【図２】
0005054665.tif 000003
【図３】
0005054665.tif 000004
【図４】
0005054665.tif 000005
【図５】
0005054665.tif 000006
【図６】
0005054665.tif 000007
【図７】
0005054665.tif 000008
【図８】
0005054665.tif 000009