(57)【要約】本発明の一実施形態は、コードの臨界領域を投機的に実行することによりロックを回避するのを容易にするシステムを提供する。動作中、システムは、プロセスがプログラム内のコードの臨界領域を、この臨界領域と関連するロックを最初に獲得せずに投機的に実行することを可能にする。その後、プロセスが、別のプロセスからの干渉するデータアクセスと遭遇せずに臨界領域を完了すれば、システムは、投機的実行中に行われた変更をコミットし、臨界領域を過ぎてプログラムの通常の非投機的実行を再開する。そうでなければ、臨界領域の実行中、別のプロセスからの干渉するデータアクセスと遭遇する場合、システムは、投機的実行中に行われた変更を廃棄し、臨界領域を再実行しようと試みる。
2006518077.tif 000002
【特許請求の範囲】
【請求項１】
コードの臨界領域を投機的に実行することによりロックを回避する方法であって、
プロセスがプログラム内のコードの臨界領域を、この臨界領域と関連するロックを最初に獲得せずに投機的に実行することを可能にする工程を有する方法において、
前記プロセスが、別のプロセスからの干渉するデータアクセスと遭遇せずに前記臨界領域を完了すれば、前記方法が、
前記投機的実行中に行われた変更をコミットする工程と、
前記臨界領域を過ぎて前記プログラムの通常の非投機的実行を再開する工程とを更に有し、
前記方法において、前記臨界領域の実行中、別のプロセスからの干渉するデータアクセスと遭遇すれば、前記方法が、
前記投機的実行中に行われた変更を廃棄する工程と、
０回以上、前記臨界領域を再実行しようと試みる工程とを更に有する方法。
【請求項２】
請求項１に記載の方法において、別のプロセスからのデータアクセスが前記臨界領域の前記投機的実行中に進行できる方法。
【請求項３】
請求項１に記載の方法において、前記臨界領域を再実行しようと試みる工程が、前記臨界領域を投機的に再実行することを含む方法。
【請求項４】
請求項３に記載の方法において、投機的実行での多数の試みの後、前記臨界領域を首尾良く完了しなければ、前記方法が、
前記臨界領域と関連するロックを獲得する工程と、
前記臨界領域を非投機的に実行する工程と、
前記臨界領域と関連する前記ロックを解除する工程とを更に有する方法。
【請求項５】
請求項１に記載の方法において、前記プロセスが前記臨界領域を投機的に実行することを可能にする前に、前記方法が、
レジスタ値と、前記プロセスに関連するその他の状態情報とをチェックポイントするチェックポイント動作を実行する工程を更に有する方法。
【請求項６】
請求項１に記載の方法において、前記臨界領域の投機的実行中にロード動作を実行する時に、前記方法が、対応のキャッシュラインをロードマークする工程を更に有する方法。
【請求項７】
請求項６に記載の方法において、前記対応のキャッシュラインをレベル１（Ｌ１）キャッシュでロードマークする方法。
【請求項８】
請求項１に記載の方法において、前記臨界領域の投機的実行中にストア動作を実行する時に、前記方法が、
独占的使用に対して対応のキャッシュラインをプリフェッチする工程と、
前記対応のキャッシュラインをストアマークする工程とを更に有する方法。
【請求項９】
請求項８に記載の方法において、キャッシュラインがコヒーレントである前記プロセッサに最も近いキャッシュレベルに前記対応のキャッシュラインをストアマークする方法。
【請求項１０】
請求項１に記載の方法において、前記干渉するデータアクセスが、
別のプロセスによりロードマークされたキャッシュラインに対する別のプロセスによるストアと、
別のプロセスによりストアマークされたキャッシュラインに対する別のプロセスによるロードまたはストアとを含むことができる方法。
【請求項１１】
請求項１に記載の方法において、前記臨界領域を実行する前に、前記プロセスが、
既存のプロセッサレジスタファイルをチェックポイントし、
前記プロセスに対するストアバッファにゲートを付けて前記ストアバッファが、前記投機的実行中に発生されたストアを送信しないようにするチェックポイント動作を実行する方法。
【請求項１２】
請求項１に記載の方法において、前記投機的実行中に行われた変更をコミットする工程が、
ストアマークされたキャッシュラインを、ロックされているかのように処理し、これにより、前記ストアマークされたキャッシュラインにアクセスする別のプロセスを待機させる工程と、
キャッシュラインからロードマークを消去する工程と、
前記投機的実行中に発生されたストアバッファエントリをメモリにコミットし、この場合、各ストアバッファエントリをコミットするのに、対応のキャッシュラインのマーク解除従ってロック解除を含む工程と、
投機的実行中に行なわれたレジスタファイルの変更をコミットする工程とを含む方法。
【請求項１３】
請求項１に記載の方法において、前記投機的実行中に行われた変更を廃棄する工程が、
前記投機的実行中に行われたレジスタファイルの変更を廃棄する工程と、
キャッシュラインからロードマークを消去する工程と、
前記投機的実行中に発生されたストアバッファエントリを空にする工程と、
キャッシュラインからストアマークを消去する工程とを含む方法。
【請求項１４】
コードの臨界領域を投機的に実行することによりロックを回避する装置であって、
プロセスがプログラム内のコードの臨界領域を、この臨界領域と関連するロックを最初に獲得せずに投機的に実行することを可能にするように構成された投機的実行機構と、
前記プロセスが、別のプロセスからの干渉するデータアクセスと遭遇せずに前記臨界領域を完了すれば、
前記投機的実行中に行われた変更をコミットし、
前記臨界領域を過ぎて前記プログラムの通常の非投機的実行を再開するように構成されたコミット機構と、
前記臨界領域の実行中、別のプロセスからの干渉するデータアクセスと遭遇すれば、
前記投機的実行中に行われた変更を廃棄し、
前記臨界領域を０回以上再実行しようと試みるように構成された再実行機構と
を具える装置。
【請求項１５】
請求項１４に記載の装置において、別のプロセスからのデータアクセスが前記臨界領域の前記投機的実行中に進行できるように前記投機的実行機構が構成された装置。
【請求項１６】
請求項１４に記載の装置において、前記再実行機構が、前記臨界領域を投機的に再実行するように構成された装置。
【請求項１７】
請求項１４に記載の装置において、投機的実行での多数の試みの後、前記臨界領域が首尾良く完了されなければ、前記再実行機構が、
前記臨界領域と関連するロックを獲得し、
前記臨界領域を非投機的に実行し、
前記臨界領域と関連する前記ロックを解除するように構成された装置。
【請求項１８】
請求項１４に記載の装置であって、前記プロセスが前記臨界領域を投機的に実行することを可能にする前に、レジスタ値と、前記プロセスに関連するその他の状態情報とをチェックポイントするように構成されたチェックポイント機構を更に具える装置。
【請求項１９】
請求項１４に記載の装置において、前記臨界領域の投機的実行中にロード動作を実行する時に、前記投機的実行機構が、対応のキャッシュラインをロードマークするように構成された装置。
【請求項２０】
請求項１９に記載の装置において、前記対応のキャッシュラインがレベル１（Ｌ１）キャッシュでロードマークされるようになっている装置。
【請求項２１】
請求項１３に記載の装置において、前記臨界領域の投機的実行中にストア動作を実行する時に、投機的実行機構が、
独占的使用に対して対応のキャッシュラインをプリフェッチし、
前記対応のキャッシュラインをストアマークするように構成された装置。
【請求項２２】
請求項２１に記載の装置において、キャッシュラインがコヒーレントである前記プロセッサに最も近いキャッシュレベルに前記対応のキャッシュラインがストアマークされるようになっている装置。
【請求項２３】
請求項１４に記載の装置において、前記干渉するデータアクセスが、
別のプロセスによりロードマークされたキャッシュラインに対する別のプロセスによるストアと、
別のプロセスによりストアマークされたキャッシュラインに対する別のプロセスによるロードまたはストアとを含むことができるようになっている装置。
【請求項２４】
請求項１４に記載の装置であって、チェックポイント機構を更に具える装置において、前記臨界領域の実行前に前記チェックポイント機構が、
既存のプロセッサレジスタファイルをチェックポイントし、
前記プロセスに対するストアバッファを、ゲートが付くように構成して前記ストアバッファが、前記投機的実行中に発生されたストアを送信しないように構成された装置。
【請求項２５】
請求項１４に記載の装置において、投機的実行中に行われた変更をコミットする間、前記コミット機構が、
ストアマークされたキャッシュラインを、ロックされているかのように処理し、これにより、前記ストアマークされたキャッシュラインにアクセスする別のプロセスを待機させ、
キャッシュラインからロードマークを消去し、
前記投機的実行中に発生されたストアバッファエントリをコミットし、この場合、各ストアバッファエントリをコミットするのに、対応のキャッシュラインのマーク解除従ってロック解除を含み、
投機的実行中に行なわれたレジスタファイルの変更をコミットするように構成された装置。
【請求項２６】
請求項１４に記載の装置において、前記投機的実行中に行われた変更を廃棄する間、前記コミット機構が、
前記投機的実行中に行われたレジスタファイルの変更を廃棄し、
キャッシュラインからロードマークを消去し、
前記投機的実行中に発生されたストアバッファエントリを空にし、
キャッシュラインからストアマークを消去するように構成された装置。
【請求項２７】
コードの臨界領域を投機的に実行することによりロックを回避するのを容易にするコンピュータシステムであって、
プロセッサと、
プロセスがプログラム内のコードの臨界領域を、この臨界領域と関連するロックを最初に獲得せずに投機的に実行することを可能にするように前記プロセッサ内に構成された投機的実行機構と、
前記プロセスが、別のプロセスからの干渉するデータアクセスと遭遇せずに前記臨界領域を完了すれば、
前記投機的実行中に行われた変更をコミットし、
前記臨界領域を過ぎて前記プログラムの通常の非投機的実行を再開するように前記プロセッサ内に構成されたコミット機構と、
前記臨界領域の実行中、別のプロセスからの干渉するデータアクセスと遭遇すれば、
前記投機的実行中に行われた変更を廃棄し、
前記臨界領域を０回以上再実行しようと試みるように前記プロセッサ内に構成された再実行機構と
を具えるコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（背景）
（発明の分野）
本発明は、コンピュータシステム内の性能を改善する技術に関する。特に、本発明は、コードの臨界領域を投機的に実行することにより、ロックの使用に含まれるオーバーヘッドを回避する方法及び装置に関する。
【背景技術】
【０００２】
（関連技術）
コンピュータシステム設計者は、従来の共有メモリマルチプロセッサ（ＳＭＰ）と同様に、最新世代のチップマルチプロセッサ（ＣＭＰ）内のマルチスレッドを支援する機構を現在開発している。適切なハードウェアサポートを用いて、マルチスレッドは、多数のアプリケーションの性能を劇的に高めることができる。しかし、マイクロプロセッサの性能が増大し続けるので、スレッド（プロセス）間の同期に費やされる時間が全体的な実行時間の大部分になってきている。実際、マルチスレッドアプリケーションがますますスレッドを用い始めているので、この同期オーバーヘッドは、アプリケーション性能を限定する支配的な要因になる。
【０００３】
プログラマーの観点から、同期はロックの使用により一般に達成される。スレッドがコードの臨界領域に入る前にロックが典型的に獲得され、この場合、スレッドが臨界領域を出た後にロックが解除される。別のスレッドが同じ臨界領域に入りたい場合、同じロックを獲得しようと試みなければならない。別のスレッドがこのロックを獲得できなければ、先行のスレッドがロックを入手しているので、先行のスレッドがロックを解除するまで別のスレッドが待たなければならない。（例えば、基本命令またはセマフォを介するような多くのやり方でロックを実装できることに留意すべきである。）
残念ながら、ロックを獲得するプロセスと、ロックを解除するプロセスとは、現代のマイクロプロセッサにおいて極めて時間を要する。これらは、ロードバッファ及びストアバッファを典型的にフラッシュする基本命令を含み、その結果として、完了するまでに、何千とまではいかないが何百ものプロセッササイクルを必要とする場合がある。
【０００４】
更に、マルチスレッドアプリケーションが、より多くのスレッドを用いるにつれて、より一層多くのロックが必要とされる。例えば、複数のスレッドが共有データ構造体にアクセスする必要があれば、全部のデータ構造体に対して１つのロックを用いるのは、性能上の理由から実用的でない。その代わり、粒度の細かい複数のロックを用いてデータ構造体のごく一部をロックするのが好ましい。これにより、データ構造体の異なる部分について複数のスレッドが並行して動作できる。しかし、データ構造体の異なる部分にアクセスするために複数のロックを獲得及び解除するのにも１つのスレッドを必要とする。
【０００５】
場合によっては、ロックが必要とされない時にロックが用いられる。例えば、多くのアプリケーションは、ロックを用いてこれらがマルチスレッドアプリケーションにとって「スレッドセーフ」であることを確実にする「スレッドセーフ」ライブラリルーチンを利用する。残念ながら、スレッドセーフライブラリルーチンがシングルスレッドアプリケーションにより呼び出された場合でも、これらロックの獲得及び解除に関わるオーバーヘッドは依然として生じる。
【０００６】
アプリケーションは、コードの臨界領域内において相互排除を確実にするのにロックを典型的に用いる。しかし、多くの場合、スレッドが臨界領域を同時に実行できても、これらスレッドは互いに干渉しない。これらの場合では、スレッドが実際に互いに干渉しそうにもない状況を防止するのに相互排除が用いられている。従って、多くの場合、ロックの獲得及び解除に関わるオーバーヘッドが大いに浪費されている。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
コードの臨界領域にアクセスする場合のロックの操作に関わるオーバーヘッドを減少させる方法及び装置が求められている。
【課題を解決するための手段】
【０００８】
（概要）
本発明の一実施形態は、コードの臨界領域を投機的に実行することによりロックを回避するのを容易にするシステムを提供する。動作中、システムは、プロセスがプログラム内のコードの臨界領域を、この臨界領域と関連するロックを最初に獲得せずに投機的に実行することを可能にする。その後、プロセスが、別のプロセスからの干渉するデータアクセスと遭遇せずに臨界領域を完了すれば、システムは、投機的実行中に行われた変更をコミットし、臨界領域を過ぎてプログラムの通常の非投機的実行を再開する。そうでなければ、臨界領域の実行中、別のプロセスからの干渉するデータアクセスと遭遇する場合、システムは、投機的実行中に行われた変更を廃棄し、臨界領域を再実行しようと試みる。
【０００９】
この実施形態の変形では、別のプロセスからのデータアクセスが臨界領域の投機的実行中に進行できる。
【００１０】
この実施形態の変形では、臨界領域を再実行しようと試みる工程が、臨界領域を投機的に再実行することを含む。
【００１１】
この実施形態の変形では、多数の投機的な試みの後、臨界領域を首尾良く完了しなければ、システムが、臨界領域と関連するロックを獲得し、次に、臨界領域を非投機的に実行する。システムは次に、ロックを解除する。
【００１２】
この実施形態の変形では、プロセスが臨界領域を投機的に実行することを可能にする前に、システムが、レジスタ値と、プロセスに関連するその他の状態情報とをチェックポイントするチェックポイント動作を実行する。
【００１３】
この実施形態の変形では、臨界領域の投機的実行中にロード動作を実行する時に、システムが対応のキャッシュラインを「ロードマークする」。この対応のキャッシュラインをレベル１（Ｌ１）キャッシュでロードマークできることに留意すべきである。
【００１４】
この実施形態の変形では、臨界領域の投機的実行中にストア動作を実行する時に、システムが、独占的使用に対して対応のキャッシュラインをプリフェッチし、しかも、この対応のキャッシュラインを「ストアマークする」。キャッシュラインがコヒーレントであるプロセッサに最も近いキャッシュレベルに、対応のキャッシュラインをストアマークできることに留意すべきである。
【００１５】
この実施形態の変形では、干渉するデータアクセスが、別のプロセスによりロードマークされたキャッシュラインに対する別のプロセスによるストアと、別のプロセスによりストアマークされたキャッシュラインに対する別のプロセスによるロードまたはストアとを含むことができる。
【００１６】
この実施形態の変形では、投機的実行中に行われた変更をコミットする間、システムがロードマークをキャッシュラインから消去し、投機的実行中に行なわれたレジスタファイルの変更をコミットする。また、システムは、ストアマークされたキャッシュラインを、ロックされているかのように処理し、これにより、ストアマークされたキャッシュラインにアクセスする別のプロセスを待機させる。システムは次に、投機的実行中に発生されたストアバッファエントリをメモリにコミットし、この場合、各ストアバッファエントリをコミットするのに、対応のキャッシュラインのマーク解除従ってロック解除を含む。
【００１７】
この実施形態の変形では、投機的実行中に行われた変更を廃棄する間、システムが、投機的実行中に行われたレジスタファイルの変更を廃棄し、キャッシュラインからロードマークを消去する。また、システムは、投機的実行中に発生されたストアバッファエントリを空にし、キャッシュラインからストアマークを消去する。
【００１８】
（詳細な説明）
いかなる当業者も本発明を製造し、かつ利用できるように以下の説明を開示し、特定用途及びその要件に照らして提示する。開示した実施形態の様々な修正が当業者にとって容易に明らかであり、ここで規定した一般的な原理を、本発明の精神及び範囲を逸脱することなく、その他の実施形態及び用途に適用できる。従って、本発明は、図示の実施形態に限定されるものではなく、ここで開示した原理及び特徴に相応する最大範囲を許容するものである。
【００１９】
（コンピュータシステム）
図１には、本発明の一実施形態によるコンピュータシステム１００を示す。コンピュータシステム１００は、メインフレームコンピュータ、デジタル信号プロセッサ、携帯型演算装置、電子手帳、デバイスコントローラ、装置内の計算エンジン、並びにマイクロプロセッサに基づくコンピュータシステムを含むがこれに限定しないあらゆる種類のコンピュータシステムを一般に含むことができる。図１に示すように、コンピュータシステム１００は、プロセッサ１０１と、メインメモリ（図示せず）に結合されたレベル２（Ｌ２）キャッシュ１２０とを含む。プロセッサ１０２の構造がプロセッサ１０１に類似するので、プロセッサ１０１のみを以下に説明する。
【００２０】
プロセッサ１０１は２つのレジスタファイル１０３，１０４を有し、これらの一方は「アクティブレジスタファイル」であり、他方はバックアップ「シャドウレジスタファイル」である。本発明の一実施形態では、プロセッサ１０１は、レジスタファイル１０３からすべての値をレジスタファイル１０４内に瞬時に複製するフラッシュコピー動作を行う。このことは、迅速なレジスタチェックポイント動作を容易にして投機的実行を支援する。
【００２１】
プロセッサ１０１は、加算器１０７及び乗算器１０８のような１つ以上の機能ユニットをも含む。これら機能ユニットは、レジスタファイル１０３または１０４から取出されたオペランドを含む計算動作を実行するのに用いられる。従来のプロセッサでのように、ロード及びストア動作はロードバッファ１１１及びストアバッファ１１２を通過する。
【００２２】
プロセッサ１０１は、このプロセッサ１０１により用いられそうなデータ項目を記憶するレベル１（Ｌ１）データキャッシュ１１５を更に含む。ここで留意すべきは、Ｌ１データキャッシュ１１５内の各ラインが「ロードマーキングビット」を含み、このロードマーキングビットは、ラインからのデータ値が投機的実行中にロードされたことを示すということである。このロードマーキングビットは、以下に図３〜８を参照して説明するように、いずれかの干渉するメモリ参照が投機的実行中に行われたかを決定するのに用いられる。プロセッサ１０１は、Ｌ１命令キャッシュ（図示せず）をも含む。
【００２３】
ロードマーキングが必ずしもＬ１データキャッシュ１１５で行われる必要がないことに留意すべきである。一般に、ロードマーキングを、Ｌ２キャッシュ１２０のようなあらゆるレベルのキャッシュで行うことができる。しかし、性能上の理由から、ロードマーキングは、できる限りプロセッサに近いキャッシュレベルで、この場合、Ｌ１データキャッシュ１１５で行われる。さもなければ、Ｌ１のヒットでさえ、ロードは、Ｌ２キャッシュ１２０へ行く必要がある。
【００２４】
Ｌ２キャッシュ１２０は、プロセッサ１０１内のＬ１データキャッシュ１１５（及び対応のＬ１命令キャッシュ）並びにプロセッサ１０２内のＬ１データキャッシュ１１７（及び対応のＬ１命令キャッシュ）と合わせて動作する。Ｌ２キャッシュ１２０は、発明者シャイレンダー・チョードリ（Ｓｈａｉｌｅｎｄｅｒ  Ｃｈａｕｄｈｒｙ）及びマルク・トレンブレイ（Ｍａｒｃ  Ｔｒｅｍｂｌａｙ）により２００２年６月２６日出願の「マルチプロセッサシステムにおいて投機的ロードを容易にする方法及び装置（Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｆａｃｉｌｉｔａｔｉｎｇ  Ｓｐｅｃｕｌａｔｉｖｅ  Ｌｏａｄｓ  ｉｎ  ａ  Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  Ｓｙｓｔｅｍ）」と題された米国特許出願第１０／１８６，１１８号明細書（米国特許出願公開第２００２／０１９９０６６号明細書）に記載されたリバースディレクトリ構造のようなコヒーレンシ機構１２２と関連付けられている。このコヒーレンシ機構１２２は、各キャッシュラインに対する「コピーバック情報」１２１を維持する。現バージョンのキャッシュラインを最初に別のプロセッサから取出さなければならないという場合には、このコピーバック情報１２１は、Ｌ２キャッシュ１２０から要求プロセッサへキャッシュラインを送信するのを容易にする。
【００２５】
Ｌ２キャッシュ１２０内の各ラインは、データ値が投機的実行中にラインに記憶されたかを示す「ストアマーキングビット」を含む。このストアマーキングビットは、以下に図３〜８を参照して説明するように、いずれかの干渉するメモリ参照が投機的実行中に行われたかを決定するのに用いられる。ストアマーキングが必ずしもＬ２キャッシュ１２０で行われる必要がないことに留意すべきである。
【００２６】
理想的に、ストアマーキングは、キャッシュラインがコヒーレントであるプロセッサに最も近いキャッシュレベルで行われる。ライトスルーＬ１データキャッシュに対して、書込みが自動的にＬ２キャッシュ１２０に伝播される。しかし、Ｌ１データキャッシュがライトバックキャッシュであれば、ストアマーキングをＬ１データキャッシュで実行する。（同じキャッシュラインを後で変更するその他のいかなるプロセッサもＬ１キャッシュからキャッシュラインを取出し、従って、ストアマークに気付くことをキャッシュコヒーレンスプロトコルが確実にすることに留意すべきである）。
【００２７】
（臨界領域の実行）
図２には、本発明の一実施形態により臨界領域がいかにして実行されるかを示す。図２の左側に示すように、臨界領域を実行するプロセッサは、臨界領域に入る前に、臨界領域と関連するロックを典型的に獲得する。ロックが別のプロセスにより獲得されていれば、別のプロセスがロックを解除するまでプロセスは待たなければならない場合がある。臨界領域から離れた際、プロセスはロックを解除する。（ここで留意すべきは、「スレッド」及び「プロセス」なる表現を、この明細書を通して同義的に用いるということである）。
【００２８】
ロックを共有データ構造体と関連付ける場合がある。例えば、共有データ構造体にアクセスする前、プロセスは共有データ構造体についてロックを獲得できる。次に、プロセスは、共有データ構造体にアクセスするコードの臨界領域を実行できる。プロセスが、共有データ構造体にアクセスし終わった後、プロセスはロックを解除する。
【００２９】
これとは対照的に、本発明では、プロセスはロックを獲得しないが、その代わり、臨界領域へ入る前にチェックポイント命令を実行する。その他のプロセスからの干渉なしに臨界領域が首尾良く終了されると、プロセスは、投機的実行中に行われた変更をコミットするコミット動作を実行する。この一連の事柄を、図３〜８を参照して以下に詳細に説明する。
【００３０】
ここで留意すべきは、本発明の一実施形態では、コンパイラがロック獲得命令をチェックポイント命令と置換え、しかも、対応のロック解除命令をコミット命令と置換えるということである。（置換えられた命令の間では、一対一対応が存在しない場合があることに留意すべきである。例えば、複数の命令から成る１つのロック獲得動作を１つのチェックポイント命令と置換えることができる。）上記の考察は、チェックポイント命令及びコミット命令を含むようにプロセッサの命令セットを拡大したと考える。これら命令を、図４〜７を参照して以下に詳細に説明する。
【００３１】
（プロセスの投機的実行）
図３には、本発明の一実施形態により投機的実行がいかにして行われるかを表すフローチャートを示す。プロセスは、コードの臨界領域に入る前にまず、チェックポイント命令を実行する（工程３０２）。次に、システムは、投機的実行の結果をコミットせず、臨界領域内のコードを投機的に実行する（工程３０４）。
【００３２】
この投機的実行中、システムは、別のプロセスにより行われたデータ参照を継続的に監視し（工程３０５）、干渉するデータアクセスが投機的実行中に行われたかを決定する（工程３０６）。行われなかったら、システムは、投機的実行中に行われた変更をコミットし（工程３０８）、次に、臨界領域を過ぎてプログラムの通常の非投機的実行を再開する（工程３１０）。
【００３３】
一方、干渉するデータアクセスを検出すれば、システムは、投機的実行中に行われた変更を廃棄し（工程３１２）、臨界領域を再実行しようと試みる（工程３１４）。
【００３４】
本発明の一実施形態では、システムは、０回、１回、２回またはそれ以上臨界領域を投機的に再実行しようと試みる。これらの試みが成功しなければ、システムは、臨界領域に入る前に臨界領域についてロックを獲得し、その後、臨界領域から離れた後にロックを解除する従来の技術に戻る。
【００３５】
干渉するデータアクセスが、別のプロセスによりロードマークされたキャッシュラインに対する別のプロセスによるストアを含むことができることに留意すべきである。干渉するデータアクセスが、別のプロセスによりストアマークされたキャッシュラインに対する別のプロセスによるロードまたはストアをも含むことができる。
【００３６】
干渉するデータアクセスを検出する回路を、従来のキャッシュコヒーレンス回路へちょっとした修正を行うことにより容易に実装できることにも留意すべきである。現在、この従来のキャッシュコヒーレンス回路は、所定のキャッシュラインが別のプロセッサによりアクセスされたかを示す信号を発生する。従って、これら信号を用いて、干渉するデータアクセスが行われたかを決定する。
【００３７】
（プロセスのチェックポイント）
図４には、本発明の一実施形態によるチェックポイント動作を表すフローチャートを示す。このフローチャートは、図３のフローチャートに示す工程３０２中に行なわれたことを示す。システムは、レジスタファイルをチェックポイントすることにより開始する（工程４０２）。この工程は、レジスタファイル１０３からレジスタファイル１０４へのフラッシュコピー動作を実行することを含む（図１参照）。レジスタ値をチェックポイントすることに加えて、このフラッシュコピーは、現在実行しているプロセスと関連する様々なステートレジスタをもチェックポイントできる。一般に、フラッシュコピー動作は、対応のスレッドを再始動できるのに充分な状態をチェックポイントする。
【００３８】
チェックポイント動作は、ストアバッファ１１２に「ゲートを付ける」ようにもする（工程４０４）。このことは、ストアバッファ内の既存のエントリがメモリサブシステムへ伝播することを可能にするが、投機的実行中に発生された新たなストアバッファエントリがそうすることを阻止する。
【００３９】
（プロセスのロードマーキング）
図５には、本発明の一実施形態によりロードマーキングが、投機的実行中、いかにして実行されるかを表すフローチャートを示す。臨界領域の投機的実行中、システムはロード動作を実行する。このロード動作の実行中、システムは、まず、Ｌ１データキャッシュ１１５からデータ項目をロードしようと試みる（工程５０２）。ロードがキャッシュヒットを引き起こせば、システムはＬ１データキャッシュ１１５内の対応のキャッシュラインを「ロードマークする」（工程５０６）。この工程は、キャッシュラインに対してロードマーキングビットを設定することを含む。そうでなければ、ロードがキャッシュミスを引き起こした場合、システムは、メモリ階層の最低レベルからキャッシュラインを取出し（工程５０８）、工程５０６へ進んでＬ１データキャッシュ１１５内のキャッシュラインをロードマークする。
【００４０】
（プロセスのストアマーキング）
図６には、本発明の一実施形態によりストアマーキングが、投機的実行中、いかにして実行されるかを表すフローチャートを示す。臨界領域の投機的実行中、システムはストア動作を実行する。このストア動作に対して、システムは、まず、独占的使用に対して対応のキャッシュラインをプリフェッチする（工程６０２）。ラインが既にキャッシュ内に位置付けられ、既に独占的使用状態にあれば、このプリフェッチ動作は何もしないことに留意すべきである。
【００４１】
この例では、Ｌ１データキャッシュ１１５がライトスルーキャッシュなので、ストア動作はＬ１データキャッシュ１１５からＬ２キャッシュ１２０へ伝播する。次に、システムは、Ｌ２データキャッシュ１１５においてストア動作に対応するキャッシュラインをロックしようと試みる（工程６０４）。対応のラインがＬ２キャッシュ１２０内にあれば（キャッシュヒット）、システムは、Ｌ２キャッシュ１２０内の対応のキャッシュラインを「ストアマークする」（工程６１０）。この工程は、キャッシュラインに対してストアマーキングビットを設定することを含む。そうでなければ、対応のラインがＬ２キャッシュ１２０内にない場合（キャッシュミス）、システムは、メモリ階層の最低レベルからキャッシュラインを取出し（工程６０８）、その後、工程６１０に進んでＬ２キャッシュ１２０内のキャッシュラインをストアマークする。
【００４２】
次に、工程６１０においてキャッシュラインをストアマークした後、システムはストアデータをストアバッファ１１２のエントリへ入力する（工程６１２）。ここで留意すべきは、次のコミット動作が行われるまで、または、投機的実行中に行われた変更が廃棄されるまで、このストアデータがストアバッファ１１２内にとどまるということである。
【００４３】
（コミット動作）
図７には、投機的実行が首尾良く完了した後、本発明の一実施形態によりコミット動作がいかにして実行されるかを表すフローチャートを示す。このフローチャートは、図３のフローチャートに示す工程３０８中に行なわれたことを示す。
【００４４】
システムは、ストアマークされたキャッシュラインを、あたかもそれらがロックされているかのように処理することにより開始する（工程７０２）。このことは、ストアマークされたラインを要求するその他のプロセスがこのラインにアクセスできる前に、このラインがもはやロックされていない時まで待機しなければならないことを意味する。このことは、従来のキャッシュ内にラインがロックされているやり方に類似する。
【００４５】
次に、システムは、Ｌ１データキャッシュ１１５からロードマークを消去する（工程７０４）。
【００４６】
次に、システムは、投機的実行中に発生されたストアバッファ１１２からのエントリをメモリ階層へコミットする（工程７０６）。各エントリがコミットされながら、Ｌ２キャッシュ１２０内の対応のラインはマーク解除される。
【００４７】
システムは、レジスタファイルの変更もコミットする（工程７０８）。例えば、この工程は、図１に示すシステムにおけるレジスタファイル１０３とレジスタファイル１０４との間でフラッシュコピーを実行することを含む。
【００４８】
（変更の廃棄）
図８には、投機的実行が不首尾に終了した後、本発明の一実施形態により変更がいかにして廃棄されるかを表すフローチャートを示す。このフローチャートは、図３のフローチャートに示す工程３１２中に行なわれたことを示す。システムは、まず、投機的実行中に行なわれたレジスタファイルの変更を廃棄する（工程８０２）。この工程は、投機的実行中に行なわれたレジスタファイルの変更を消去するか、単に無視することを含む。これを達成するのは容易である。その理由は、投機的実行を開始する前に、前のレジスタ値がチェックポイントされているからである。システムはＬ１データキャッシュ１１５内のキャッシュラインからロードマークも消去し（工程８０４）、投機的実行中に発生されたストアバッファエントリをメモリ階層へコミットせずに空にする（工程８０６）。同時に、システムは、対応のＬ２キャッシュラインをマーク解除する。最後に、本発明の一実施形態では、システムは、チェックポイント命令により指定された対象位置に分岐する（工程８０８）。この対象位置のコードは、図１の工程３１４を参照して上記で説明したように、臨界領域を再実行しようと試みる。
【００４９】
本発明の実施形態の前述の説明を、単なる例示及び説明目的に提示した。これらは包括的なものではなく、または、開示した形態について本発明を限定するものではない。従って、多くの修正及び変形が当業者にとって明らかである。加えて、上記の開示は本発明を限定するものではない。本発明の範囲は、特許請求の範囲により規定される。
【図面の簡単な説明】
【００５０】
【図１】図１は、本発明の一実施形態によるコンピュータシステムを示す。
【図２】図２は、本発明の一実施形態により臨界領域がいかにして実行されるかを示す。
【図３】図３は、本発明の一実施形態による投機的実行処理を表すフローチャートを示す。
【図４】図４は、本発明の一実施形態によるチェックポイント動作を表すフローチャートを示す。
【図５】図５は、本発明の一実施形態によりロードマーキングが、投機的実行中、いかにして実行されるかを表すフローチャートを示す。
【図６】図６は、本発明の一実施形態によりストアマーキングが、投機的実行中、いかにして実行されるかを表すフローチャートを示す。
【図７】図７は、投機的実行が首尾良く完了した後、本発明の一実施形態によりコミット動作がいかにして実行されるかを表すフローチャートを示す。
【図８】図８は、投機的実行が不首尾に終了した後、本発明の一実施形態により変更がいかにして廃棄されるかを表すフローチャートを示す。
【図１】
2006518077.tif 000003
【図２】
2006518077.tif 000004
【図３】
2006518077.tif 000005
【図４】
2006518077.tif 000006
【図５】
2006518077.tif 000007
【図６】
2006518077.tif 000008
【図７】
2006518077.tif 000009
【図８】
2006518077.tif 000010
【国際調査報告】
2006518077.tif 000011
2006518077.tif 000012
2006518077.tif 000013