(57)【要約】本発明の一実施形態は、シングルプロセッサパイプライン内のヘッドスレッドおよび推論的スレッドのインターリーブ実行を容易にするシステムを提供する。このシステムは、ヘッドスレッドを用いてプログラム命令を実行することによって、および、推論的スレッドを用いて、ヘッドスレッドに先んじてプログラム命令を推論的に実行することによって、動作する。このヘッドスレッドおよび推論的スレッドは、シングルプロセッサパイプラインの時間多重化インターリーブを通して同時に実行する。
2005529383.tif 000002
【特許請求の範囲】
【請求項１】
シングルプロセッサパイプライン内のヘッドスレッドおよび推論的スレッドのインターリーブ実行のための方法であって、該方法は、
該ヘッドスレッドを用いてプログラム命令を実行するステップと、
該推論的スレッドを用いて該ヘッドスレッドの前にプログラム命令を推論的に実行するステップと
を包含し、
該ヘッドスレッドおよび該推論的スレッドは、該シングルプロセッサパイプラインの時間多重化インターリーブを通して同時に実行する、方法。
【請求項２】
前記推論的スレッドは、１つ以上の推論的スレッドを含む、請求項１に記載の方法。
【請求項３】
前記推論的スレッドが実行を開始したという、前記プログラム中のあるポイントに前記ヘッドスレッドが到達するとき、該ヘッドスレッドと該推論的スレッドとの間の結合演算を実行するステップをさらに包含する、請求項１に記載の方法。
【請求項４】
前記ヘッドスレッドは、メモリ素子のプライマリバージョンで動作し、
前記推論的スレッドは、該メモリ素子の空間−時間次元バージョンで動作し、
前記結合演算を実行するステップは、該メモリ素子のプライマリバージョン内に該メモリ素子の該空間−時間次元バージョンをマージするステップを含み、これにより、該メモリ素子の該空間−時間次元バージョンに対する更新は、メモリ素子の対応するプライマリバージョンに組み込まれる、請求項３に記載の方法。
【請求項５】
前記推論的スレッドがメモリ素子に対する読み出し動作を実行する場合、前記方法は、
該メモリ素子の前記空間−時間次元バージョンが存在するかどうかを判定するステップと、
該メモリ素子の該空間−時間次元バージョンが存在する場合、該メモリ素子の該空間−時間次元バージョンを読み出すステップと、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該プライマリバージョンを読み出すステップと、
該メモリ素子に関連するステータス情報を更新して、該メモリ素子が該推論的スレッドによって読み出されたことを示すステップと
をさらに包含する、請求項４に記載の方法。
【請求項６】
前記推論的スレッドがメモリ素子に対する書き込み動作を実行する場合、前記方法は、
該メモリ素子の該空間−時間次元バージョンが存在するかどうかを判定するステップと、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該空間−時間次元バージョンを作成するステップと、
該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行するステップと
をさらに包含する、請求項４に記載の方法。
【請求項７】
前記ヘッドスレッドがメモリ素子に対する読み出し動作を実行する場合、前記方法は、該メモリ素子の該プライマリバージョンに対する読み出し動作を実行するステップをさらに包含する、請求項４に記載の方法。
【請求項８】
前記ヘッドスレッドがメモリ素子に対する書き込み動作を実行する場合、前記方法は、
該メモリ素子の該プライマリバージョンに対する書き込み動作を実行するステップと、
該メモリ素子に関連するステータス情報をチェックして、該メモリ素子が該推論的スレッドによって読み出されたかどうかを判定するステップと、
該メモリ素子が該推論的スレッドによって読み出された場合、該推論的スレッドが該書き込み動作の結果を読み出すことが可能となるように、該推論的スレッドをロールバックするステップと、
該メモリ素子が該推論的スレッドによって読み出されていない場合、該空間−時間次元バージョンが存在する場合に該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行するステップと
をさらに包含する、請求項４に記載の方法。
【請求項９】
前記メモリ素子は、オブジェクト指向プログラミングシステム内で定義されたオブジェクトを含む、請求項４に記載の方法。
【請求項１０】
前記ヘッドスレッドおよび前記推論的スレッドは、別々のハードウェアレジスタファイルにアクセスする、請求項１に記載の方法。
【請求項１１】
コンピュータによって実行される場合に、シングルプロセッサパイプライン内のヘッドスレッドおよび推論的スレッドのインターリーブ実行のための方法をコンピュータに実行させる命令を格納するコンピュータ読み出し可能格納媒体であって、該方法は、
該ヘッドスレッドを用いてプログラム命令を実行するステップと、
該推論的スレッドを用いて該ヘッドスレッドの前にプログラム命令を推論的に実行するステップと
を包含し、
該ヘッドスレッドおよび該推論的スレッドは、該シングルプロセッサパイプラインの時間多重化インターリーブを通して同時に実行する、コンピュータ読み出し可能格納媒体。
【請求項１２】
前記推論的スレッドは、１つ以上の推論的スレッドを含む、請求項１１に記載のコンピュータ読み出し可能格納媒体。
【請求項１３】
前記方法は、前記推論的スレッドが実行を開始したという、前記プログラム中のあるポイントに前記ヘッドスレッドが到達するとき、該ヘッドスレッドと該推論的スレッドとの間の結合演算を実行するステップをさらに包含する、請求項１１に記載のコンピュータ読み出し可能格納媒体。
【請求項１４】
前記ヘッドスレッドは、メモリ素子のプライマリバージョンで動作し、
前記推論的スレッドは、該メモリ素子の空間−時間次元バージョンで動作し、
前記結合演算を実行するステップは、該メモリ素子のプライマリバージョン内に該メモリ素子の該空間−時間次元バージョンをマージするステップを含み、これにより、該メモリ素子の該空間−時間次元バージョンに対する更新は、メモリ素子の対応するプライマリバージョンに組み込まれる、請求項１３に記載のコンピュータ読み出し可能格納媒体。
【請求項１５】
前記推論的スレッドがメモリ素子に対する読み出し動作を実行する場合、前記方法は、
該メモリ素子の前記空間−時間次元バージョンが存在するかどうかを判定するステップと、
該メモリ素子の該空間−時間次元バージョンが存在する場合、該メモリ素子の該空間−時間次元バージョンを読み出すステップと、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該プライマリバージョンを読み出すステップと、
該メモリ素子に関連するステータス情報を更新して、該メモリ素子が該推論的スレッドによって読み出されたことを示すステップと
をさらに包含する、請求項１４に記載のコンピュータ読み出し可能格納媒体。
【請求項１６】
前記推論的スレッドがメモリ素子に対する書き込み動作を実行する場合、前記方法は、
該メモリ素子の該空間−時間次元バージョンが存在するかどうかを判定するステップと、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該空間−時間次元バージョンを作成するステップと、
該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行するステップと
をさらに包含する、請求項１４に記載のコンピュータ読み出し可能格納媒体。
【請求項１７】
前記ヘッドスレッドがメモリ素子に対する読み出し動作を実行する場合、前記方法は、該メモリ素子の該プライマリバージョンに対する読み出し動作を実行するステップをさらに包含する、請求項１４に記載のコンピュータ読み出し可能格納媒体。
【請求項１８】
前記ヘッドスレッドがメモリ素子に対する書き込み動作を実行する場合、前記方法は、
該メモリ素子の該プライマリバージョンに対する書き込み動作を実行するステップと、
該メモリ素子に関連するステータス情報をチェックして、該メモリ素子が該推論的スレッドによって読み出されたかどうかを判定するステップと、
該メモリ素子が該推論的スレッドによって読み出された場合、該推論的スレッドが該書き込み動作の結果を読み出すことが可能となるように、該推論的スレッドをロールバックするステップと、
該メモリ素子が該推論的スレッドによって読み出されていない場合、該空間−時間次元バージョンが存在する場合に該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行するステップと
をさらに包含する、請求項１４に記載のコンピュータ読み出し可能格納媒体。
【請求項１９】
前記メモリ素子は、オブジェクト指向プログラミングシステム内で定義されたオブジェクトを含む、請求項１４に記載のコンピュータ読み出し可能格納媒体。
【請求項２０】
前記ヘッドスレッドおよび前記推論的スレッドは、別々のハードウェアレジスタファイルにアクセスする、請求項１１に記載のコンピュータ読み出し可能格納媒体。
【請求項２１】
シングルプロセッサパイプライン内のヘッドスレッドおよび推論的スレッドのインターリーブ実行を支援する装置であって、該装置は、
プロセッサと、
該プロセッサ内のプロセッサパイプラインと、
実行メカニズムであって、
該ヘッドスレッドを用いてプログラム命令を実行し、
該推論的スレッドを用いて該ヘッドスレッドの前にプログラム命令を推論的に実行する
ように構成された該プロセッサ内の実行メカニズムと
を備え、
該実行メカニズムは、該プロセッサパイプラインの時間多重化インターリーブを通して、該ヘッドスレッドおよび該推論的スレッドを同時に実行するように構成される、装置。
【請求項２２】
前記推論的スレッドは、１つ以上の推論的スレッドを含む、請求項２１に記載の装置。
【請求項２３】
前記推論的スレッドが実行を開始したという、前記プログラム中のあるポイントに前記ヘッドスレッドが到達するとき、該ヘッドスレッドと該推論的スレッドとの間の結合演算を実行するように構成される結合メカニズムをさらに備える、請求項２１に記載の装置。
【請求項２４】
前記ヘッドスレッドは、メモリ素子のプライマリバージョンで動作し、
前記推論的スレッドは、該メモリ素子の空間−時間次元バージョンで動作し、
前記結合メカニズムは、該メモリ素子のプライマリバージョン内に該メモリ素子の該空間−時間次元バージョンをマージするように構成され、これにより、該メモリ素子の該空間−時間次元バージョンに対する更新は、メモリ素子の対応するプライマリバージョンに組み込まれる、請求項２３に記載の装置。
【請求項２５】
前記推論的スレッドがメモリ素子に対する読み出し動作を実行する場合、前記実行メカニズムは、
該メモリ素子の前記空間−時間次元バージョンが存在するかどうかを判定し、
該メモリ素子の該空間−時間次元バージョンが存在する場合、該メモリ素子の該空間−時間次元バージョンを読み出し、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該プライマリバージョンを読み出し、
該メモリ素子に関連するステータス情報を更新して、該メモリ素子が該推論的スレッドによって読み出されたことを示す
ように構成される、請求項２４に記載の装置。
【請求項２６】
前記推論的スレッドがメモリ素子に対する書き込み動作を実行する場合、前記実行メカニズムは、
該メモリ素子の該空間−時間次元バージョンが存在するかどうかを判定し、
該メモリ素子の該空間−時間次元バージョンが存在しない場合、該メモリ素子の該空間−時間次元バージョンを作成し、
該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行する
ように構成される、請求項２４に記載の装置。
【請求項２７】
前記ヘッドスレッドがメモリ素子に対する読み出し動作を実行する場合、前記実行メカニズムは、該メモリ素子の該プライマリバージョンに対する読み出し動作を実行するように構成される、請求項２４に記載の装置。
【請求項２８】
前記ヘッドスレッドがメモリ素子に対する書き込み動作を実行する場合、前記実行メカニズムは、
該メモリ素子の該プライマリバージョンに対する書き込み動作を実行し、
該メモリ素子に関連するステータス情報をチェックして、該メモリ素子が該推論的スレッドによって読み出されたかどうかを判定し、
該メモリ素子が該推論的スレッドによって読み出された場合、該推論的スレッドが該書き込み動作の結果を読み出すことが可能となるように、該推論的スレッドをロールバックし、
該メモリ素子が該推論的スレッドによって読み出されていない場合、該空間−時間次元バージョンが存在する場合に該メモリ素子の該空間−時間次元バージョンに対する書き込み動作を実行する
ように構成される、請求項２４に記載の装置。
【請求項２９】
前記メモリ素子は、オブジェクト指向プログラミングシステム内で定義されたオブジェクトを含む、請求項２４に記載の装置。
【請求項３０】
前記ヘッドスレッドおよび前記推論的スレッドは、別々のハードウェアレジスタファイルにアクセスする、請求項２１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータシステムの性能を改善する技術に関する。より詳細には、本発明は、シングルプロセッサパイプライン内の非推論的スレッドおよび関連する推論的スレッドのインターリーブ実行を支援する方法および装置に関する。
【背景技術】
【０００２】
マイクロプロセッサのクロックスピードが指数関数的に増加し続けるにつれて、これらのより高速のクロックスピードに合わせて、プロセッサパイプラインを設計することがますます困難になりつつある。なぜなら、各パイプラインステージでは、必要なコンピュータ演算を実行するために利用可能な時間が少ないからである。この問題に取り組むために、シングルプロセッサパイプライン内のラウンドロビンの様態で、関連性のないプロセッサスレッドの実行を静的にインターリーブする可能性の調査を開始した設計者もいる。この様に、Ｎ個の関連性のないスレッドがインターリーブされる場合、所与のスレッドに対する命令は、全Ｎ個の連続的なパイプラインステージに対して１回だけ行われるように見える。従って、Ｎ個のスレッドは、それぞれ、プロセッサの固有クロックレートの１／Ｎで走る。例えば、４つのスレッド（それぞれは３ＧＨｚで走る）は、集合的には１２ＧＨｚのプロセッサ上で走ることが可能である。
【０００３】
このインターリーブ技術は、待ち時間要件を緩和し、これによって、高速プロセッサパイプラインを設計することが非常に容易になる。例えば、４つの関連性のないスレッドがインターリーブされる場合、データキャッシュアクセス（または、加算演算）は、所与のスレッドの性能にマイナスの影響を与えることなく、最大４つのパイプラインステージを取ることが可能である。
【０００４】
シングルパイプライン内のマルチスレッドの実行をインターリーブすることは、多くの利点を有する。これは、別々のパイプラインでスレッドを実行することに比べて、電力および面積を節約する。また、シングルパイプラインに対して、非常に大きなスループットを提供する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、マルチスレッド化され得ないアプリケーションまたはベンチマークは、このインターリーブ技術から利益を得ない。このことは、シングルスレッドの性能が、コンピュータシステムを購入する多くのカスタマーにとって重要であるために、問題となる。結果として、コンピュータシステムの性能を比較するためにカスタマーが用いるベンチマークは、概して、シングルスレッドの性能を評価する。
【０００６】
従って、必要とされるのは、シングルスレッドのアプリケーションにマルチスレッドの静的時間多重化実行の利点を提供する方法および装置である。
【課題を解決するための手段】
【０００７】
（要旨）
本発明の一つの実施形態は、シングルプロセッサパイプライン内のヘッドスレッドおよび推論的スレッドのインターリーブ実行を容易にするシステムを提供する。このシステムは、ヘッドスレッドを用いてプログラム命令を実行し、推論的スレッドを用いてヘッドスレッドの前にプログラム命令を推論的に実行することによって動作する。ヘッドスレッドおよび推論的スレッドは、シングルプロセッサパイプラインの時間多重化インターリーブを通して同時に実行する。
【０００８】
この実施形態の改変では、推論的スレッドは、１つ以上の推論的スレッドを含む。
【０００９】
この実施形態の改変では、システムは、推論的スレッドが実行を開始したという、プログラム中のあるポイントにヘッドスレッドが到達するとき、ヘッドスレッドと推論的スレッドとの間の結合演算を実行する。
【００１０】
さらなる改変では、ヘッドスレッドは、メモリ素子のプライマリバージョンで動作し、推論的スレッドは、メモリ素子の空間−時間次元バージョンで動作する（「Ｓｕｐｐｏｒｔｉｎｇ  Ｓｐａｃｅ−Ｔｉｍｅ  Ｄｉｍｅｎｓｉｏｎａｌ  Ｐｒｏｇｒａｍ  Ｅｘｅｃｕｔｉｏｎ  ｂｙ  Ｓｅｌｅｃｔｉｖｅｌｙ  Ｖｅｒｓｉｏｎｉｎｇ  Ｍｅｍｏｒｙ  Ｕｐｄａｔｅｓ」と称された、米国特許第６，３５３，８８１号でなされている）。この改変では、結合演算を実行するステップは、メモリ素子のプライマリバージョン内にメモリ素子の空間−時間次元バージョンをマージするステップを含み、これにより、メモリ素子の空間−時間次元バージョンに対する更新は、メモリ素子の対応するプライマリバージョンに組み込まれる。
【００１１】
さらなる改変では、推論的スレッドがメモリ素子に対する読み出し動作を実行する場合、システムは、メモリ素子の前記空間−時間次元バージョンが存在するかどうかを判定する。メモリ素子の空間−時間次元バージョンが存在する場合、システムは、メモリ素子の空間−時間次元バージョンを読み出す。メモリ素子の空間−時間次元バージョンが存在しない場合、システムは、メモリ素子のプライマリバージョンを読み出す。また、システムは、メモリ素子に関連するステータス情報を更新して、メモリ素子が推論的スレッドによって読み出されたことを示す。
【００１２】
さらなる改変では、推論的スレッドがメモリ素子に対する書き込み動作を実行する場合、システムは、メモリ素子の空間−時間次元バージョンが存在するかどうかを判定する。メモリ素子の空間−時間次元バージョンが存在しない場合、システムは、メモリ素子の空間−時間次元バージョンを作成し、メモリ素子の空間−時間次元バージョンに対する書き込み動作を実行する。
【００１３】
さらなる改変では、ヘッドスレッドがメモリ素子に対する読み出し動作を実行する場合、システムは、メモリ素子のプライマリバージョンに対する読み出し動作を実行する。
【００１４】
さらなる改変では、ヘッドスレッドがメモリ素子に対する書き込み動作を実行する場合、システムは、メモリ素子のプライマリバージョンに対する書き込み動作を実行する。また、システムは、メモリ素子に関連するステータス情報をチェックして、メモリ素子が推論的スレッドによって読み出されたかどうかを判定する。メモリ素子が推論的スレッドによって読み出された場合、システムは、推論的スレッドが書き込み動作の結果を読み出すことが可能となるように、推論的スレッドをロールバックする。メモリ素子が推論的スレッドによって読み出されていない場合、システムは、空間−時間次元バージョンが存在する場合にメモリ素子の空間−時間次元バージョンに対する書き込み動作を実行する。
【００１５】
さらなる改変では、メモリ素子は、オブジェクト指向プログラミングシステム内で定義されたオブジェクトを含む。
【００１６】
この実施形態の改変では、ヘッドスレッドおよび推論的スレッドは、別々のハードウェアレジスタファイルにアクセスする。
【発明を実施するための最良の形態】
【００１７】
（詳細な説明）
以下の説明は、当業者が本発明を利用することが可能であるように提示され、特定の用途およびその必要要件のコンテキストで提供される。開示された実施形態の様々な修正は、当業者に容易に明らかであり、本明細書中において定義された一般的な原理は、本発明の意図および範囲を逸脱することなく、他の実施形態および用途に適用され得る。従って、本発明は、示された実施形態に制限されず、本明細書中に開示された原理および特徴に一致する最大限の範囲に従う。
【００１８】
この詳細な説明に記載されたデータ構造およびコードは、通常、コンピュータ読み出し可能媒体に格納される。このコンピュータ読み出し可能媒体は、コンピュータシステムによって利用されるコードおよび／またはデータを格納することが出来る任意のデバイスまたは媒体であり得る。これは、磁気デバイスおよび光デバイス（例えば、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）およびＤＶＤ（デジタル多目的ディスクまたはデジタルビデオディスク））、ならびに、（信号が変調される搬送波を伴う、または伴わない）伝送媒体内で具現化されたコンピュータ命令信号を含むが、これらに制限されない。例えば、伝送媒体は、インターネット等の通信ネットワークを含んでもよい。
【００１９】
（コンピュータシステム）
図１は、本発明の実施形態による、コンピュータシステムを示す。図１に示された実施形態では、シリコンダイ１００は、少なくとも１つの中央演算処理装置（ＣＰＵ）１０２を含む。ＣＰＵ１０２は、概して、複数のスレッドが同時に実行可能である任意のタイプのコンピュータ計算デバイスを含み得る。
【００２０】
ＣＰＵ１０２は、ＣＰＵ１０２によって実行される命令を含む命令キャッシュ１１２、および、ＣＰＵ１０２によって演算されるデータを含むデータキャッシュ１０６を含む。本発明の１つの実施形態では、データキャッシュ１０６は、６４バイトキャッシュラインを有する６４キロバイト４ウェイセットアソシアティブデータキャッシュである。
【００２１】
データキャッシュ１０６および命令キャッシュ１１２は、レベル２（Ｌ２）キャッシュに接続され、このＬ２キャッシュは、メモリコントローラ１１１に接続される。メモリコントローラ１１１は、チップ外に置かれたダイナミックランダムアクセスメモリ（ＤＲＡＭ）１０８に接続される。
【００２２】
命令キャッシュ１１２は、命令を４つの別々の命令キュー１１４〜１１７内に入れる。この４つの別々の命令キュー１１４〜１１７は、４つの別々の実行スレッドに関連する。キュー１１４〜１１７からの命令は、マルチプレクサ１０９を通して送られる。このマルチプレクサ１０９は、命令が実行パイプライン１０７に送られる前に、ラウンドロビンの様態で命令キュー１１４〜１１７からの命令をインターリーブする。図１に示されるように、所与の命令キューからの命令は、実行パイプライン１０７において４番目毎の命令スロットを占める。なお、プロセッサ１０２の他のインプリメンテーションは、４より多いキューからの命令をインターリーブしてもよく、４より少ないキューからの命令をインターリーブしてもよい。
【００２３】
異なるスレッド間でパイプラインスロットが回転しているため、待ち時間が緩和し得る。例えば、データキャッシュ１０６からのロードは、パイプラインを立ち往生させることなく、最大４つのパイプラインステージを取ることが可能であり、また、算術演算は、最大４つのパイプラインステージを取ることが可能である。本発明の１つの実施形態では、このインターリーブは「静的」であり、つまり、各命令キューが実行パイプライン１０７の４番目毎の命令スロットに関連しており、この関連は、経時的に動的には変化しないことを意味する。
【００２４】
命令キュー１１４〜１１７は、対応するレジスタファイル１１８〜１２１にそれぞれ関連する。それらのレジスタファイル１１８〜１２１は、命令キュー１１４〜１１７からの命令によって操作されるオペランドを含む。なお、実行パイプライン１０７の命令は、データキャッシュ１０６とレジスタファイル１１８〜１１９との間でデータを転送させ得る。（本発明の別の実施形態では、レジスタファイル１１８〜１２１は、命令キュー１１４〜１１７に関連する別々のスレッド間で仕切られたシングルラージマルチポートレジスタファイル内に一元管理される。）
なお、本発明は、概して、シングルパイプラインのマルチスレッドの同時インターリーブ実行を支援する任意のコンピュータシステムに適用され、図示されたコンピューティングシステムに制限されることを意図していない。例えば、本発明は、上記の固定インターリーブラウンドロビンスケジューリングスキームに制限されることを意図しないが、概して、命令キューから命令をインターリーブする任意の時間多重化スケジューリングスキームに適用され得る。
【００２５】
（メソッドの空間−時間次元実行）
図２Ａは、シングルヘッドスレッド２０２による従来のコンピュータシステムにおける、メソッドの連続的実行を示す。プログラムを実行する際に、ヘッドスレッド２０２は、シーケンスにおける多くのメソッド（メソッドＡ２０４、メソッドＢ２０６およびメソッドＣ２０８を含む）を実行する。
【００２６】
対称的に、図２Ｂは、本発明の実施形態による、メソッドの空間および時間次元の実行を示す。図２Ｂでは、最初、ヘッドスレッド２０２は、メソッドＡ２０４を実行し、続いて、メソッドＢ２０６を実行する。（例えば、メソッドＢ２０６は、ボイド、または、メソッドＣ２０８によって用いられないいくつかの他の値を返すと仮定する。あるいは、メソッドＣ２０８がメソッドＢ２０６によって返された値を用いる場合、メソッドＣ２０８は、メソッドＢ２０６からの予測戻り値を用いると仮定する。）
ヘッドスレッド２０２がメソッドＢ２０６を実行するとき、推論的スレッド２０３は、ヒープの別々の空間−時間次元においてメソッドＣ２０８を実行する。ヘッドスレッド２０２がメソッドＢ２０６を首尾良く実行する場合、推論的スレッド２０３は、ヘッドスレッド２０２に結合される。この結合演算は、推論的スレッド２０３に関連する状態をヘッドスレッド２０２に関連する状態にマージさせて、ヒープの空間−時間次元を崩壊させること（ｃｏｌｌａｐｓｉｎｇ）に関する。
【００２７】
いくつかの理由により推論的スレッド２０３がメソッドＣ２０８を実行する際に問題に遭遇した場合、推論的スレッド２０３は、ロールバック演算を実行する。このロールバック演算は、推論的スレッド２０３がメソッドＣ２０８を再び実行しようと試みることを可能にする。あるいは、ヘッドスレッド２０２は、非推論的にメソッドＣ２０８を実行可能であり、推論的スレッド２０３は、次のメソッドを実行可能である。
【００２８】
推論的スレッド２０３がメソッドＣ２０８を実行する際に問題に遭遇し得る多くの理由がある。１つの問題は、メソッドＢ２０６を実行するヘッドスレッド２０２がメモリ素子（オブジェクト）に値を書き込む前に、推論的スレッド２０３が同じメモリ素子を読み出したときに起こる。推論的スレッド２０３の読み出し時間において、このメモリ素子でヒープの２つの空間−時間次元が崩壊しているときに、同じメモリ素子が読み出され得る。この場合、推論的スレッド２０３は、ヘッドスレッド２０２によって書き込まれる値を読み出すべきであるが、代わりに、以前の値を読み込んでしまう。この場合、このシステムが推論的スレッド２０３をロールバックさせることにより、推論的スレッド２０３は、ヘッドスレッド２０２によって書き込まれた値を読み出し得る。
【００２９】
なお、用語「メモリ素子」は、概して、コンピュータプログラムによってアクセスされ得る任意のメモリユニットを言う。例えば、用語「メモリ素子」は、１ビット、１バイトまたは１ワードのメモリを指してもよく、オブジェクト指向プログラミングシステム内で定義されたデータ構造またはオブジェクトを指してもよい。
【００３０】
図３は、本発明の実施形態による、メソッドの空間−時間次元実行中のシステムスタックの状態を示す。なお、Ｊａｖａ（登録商標）プログラミング言語等のプログラミング言語では、メソッドが別のメソッドのスタックフレームを修正することができないため、メソッドＢ２０６が実行される前とメソッドＣ２０８が実行される前とは、システムスタックは概して同じである。（メソッドＢ２０６がシステムスタックを通してパラメータを戻す場合、これは完全に真ではない。しかし、戻りパラメータは、明白に、以下に示すように取り扱われ得る。）図３を参照して、スタック３００は、メソッドＡ２０４が実行している間、メソッドＡのフレーム３０２を含む。メソッドＡ２０４が戻るとき、メソッドＢ２０６は開始し、メソッドＡフレーム３０２は、メソッドＢフレーム３０４と交換される。最後に、メソッドＢ２０６が戻るとき、メソッドＣ２０８は開始し、メソッドＢフレーム３０４はメソッドＣフレーム３０６と交換される。なお、メソッドＢ２０６が実行される直前とメソッドＣ２０８が実行される直前とは、スタック３００が同じスタックであるため、最初にメソッドＢ２０６を実行することなく、スタック３００のコピーを用いてメソッドＣ２０８を実行することが可能である。
【００３１】
推論的に実行された演算の結果を元に戻すために、メモリに対する更新が変更される必要がある。メモリに対する全更新を変更することに関するオーバーヘッドは、変更を実行するためにメモリ要件を増加し、キャッシュ性能を低下させ、ハードウェアをより必要とするため、法外に高価であり得る。
【００３２】
幸運にも、メモリに対する全更新の変更が必要とされるわけではない。例えば、システムスタック上のローカル変数（例えば、ループカウンタ）に対する更新は、通常、ローカル変数を更新しているスレッドに関連するのみである。従って、これらのローカル変数に対する更新を変更する推論的スレッドさえも必要ではない。
【００３３】
従来のプログラミング言語（例えば、Ｃ）で書かれたプログラムを実行するとき、通常、どの更新がヒープに関連しているか、どの更新がシステムスタックに関連しているかを決定することはできない。通常、これらのプログラムは、高レベル言語表現から、特定のマシンアーキテクチャに対する実行可能コードへとコンパイルされる。このコンパイルプロセスは、通常、ヒープおよびシステムスタックに対する更新間の違いを取り除く。
【００３４】
同じことは、新規のプラットフォーム独立型コンピュータ言語（例えば、Ｐａｌｏ  Ａｌｔｏ，ＣａｌｉｆｏｒｎｉａのＳＵＮ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．から配布されるＪＡＶＡ（登録商標）プログラミング言語）にはあてはまらない。（Ｓｕｎ、  ｔｈｅ  Ｓｕｎ  ｌｏｇｏ、  Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ、およびＪａｖａ（登録商標）は、米国および他国において、ＳＵＮ  Ｍｉｃｒｏｓｙｓｔｅｍｓ，Ｉｎｃ．の登録商標である）。Ｊａｖａ（登録商標）プログラミング言語でかかれたプログラムは、通常、Ｊａｖａ（登録商標）バイトコードを含むクラスファイルへと通常コンパイルされる。このクラスファイルは、コンピュータネットワークを介して離れたコンピュータシステムに送信され、その離れたコンピュータシステム上で実行され得る。Ｊａｖａ（登録商標）バイトコードは、「プラットフォーム独立」と呼ばれる。なぜなら、コンピューティングプラットフォームがＪａｖａ（登録商標）仮想マシンを提供する限り、幅広いコンピューティングプラットフォームにおいてそれらは実行され得るからである。
【００３５】
Ｊａｖａ（登録商標）バイトコードは、インタプリタまたはジャストインタイム（ＪＩＴ）コンパイラを用いることによって、特定のコンピューティングプラットフォーム上で実行され得、Ｊａｖａ（登録商標）バイトコードをその特定のコンピューティングプラットフォームに対するマシンコードに変換する。あるいは、Ｊａｖａ（登録商標）バイトコードは、その特定のコンピューティングプラットフォーム上で走るＪａｖａ（登録商標）バイトコードエンジン上で直接実行され得る。
【００３６】
幸運にも、Ｊａｖａ（登録商標）バイトコードは、従来のマシンコードよりもシンタクチック（ｓｙｎｔａｃｔｉｃ）な情報を含む。特に、Ｊａｖａ（登録商標）バイトコードは、システムスタックのローカル変数に対するアクセスと、システムヒープに対するアクセスとの間で異なる。さらに、Ｊａｖａ（登録商標）プログラミング言語で書かれたプログラムでは、プリミティブタイプと参照タイプとの間の変換は可能ではない。このような変換は、コンパイル時に、システムスタックに対するアクセスとシステムヒープへのアクセスとを区別することを困難にし得る。
【００３７】
（空間−時間次元実行を支援するデータ構造）
図４は、本発明の実施形態による、スタックとヒープとの間のメモリの分割方法を示す。図４では、メモリ４００は、ヒープ４０２、スレッド用スタック４０４および推論的ヒープ４０６を含む多くの領域に分割される。ヒープ４０２は、オブジェクトが割り当てられるメモリの領域を含む。ヒープ４０２は、さらに、ガーベッジコレクション目的で、より若い世代の領域４０８とより古い世代の領域４１０とに分割される。性能の理由から、ガーベッジコレクタは、通常、より古い世代のオブジェクトとより若い世代のオブジェクトとを別々に取り扱う。スレッド用スタック４０４は、様々なスレッド用のスタックが割り当てられるメモリの領域を含む。推論的ヒープ４０６は、全メモリ素子の空間−時間次元値を含む。ここで、ヒープの２つの空間−時間次元は崩壊していない。これは、オブジェクトの空間−時間次元バージョン（例えば、図５に示されるオブジェクト５００、および推論的スレッド２０３によって作成されたオブジェクトのバージョン５１０）を含む。ガーベッジコレクション目的で、推論的スレッド２０３によって作成されたこれらのオブジェクトは、より若い世代領域４０８内のオブジェクトよりもより若い世代に所属しているように取り扱われ得る。
【００３８】
図５は、本発明の実施形態による、オブジェクトのプライマリバージョン５００およびオブジェクトの空間−時間次元バージョン５１０の構造を示す。
【００３９】
オブジェクトのプライマリバージョン５００は、オブジェクト参照ポインタ５０１によって参照される。オブジェクト指向プログラミングシステム内に定義された任意のオブジェクトのように、オブジェクトのプライマリバージョン５００は、データ領域５０８を含む。このデータ領域５０８は、オブジェクトのプライマリバージョン５００に関連するデータを含む１つ以上のフィールドを含む。オブジェクトのプライマリバージョン５００は、また、メソッドベクトルテーブルポインタ５０６を含む。メソッドベクトルテーブルポインタ５０６は、オブジェクトのプライマリバージョン５００で呼び出され得るメソッドを指すベクトルを含むテーブルを指す。
【００４０】
オブジェクト５００のプライマリバージョンはまた、空間−時間次元バージョンポインタ５０２を含む。この空間−時間次元バージョンポインタ５０２は、２つの空間−時間次元がこのオブジェクトにおいて崩壊していない場合、オブジェクトの空間−時間次元バージョン５１０を指す。なお、本発明の図示された実施形態では、空間−時間次元バージョン５１０は、常に、空間−時間次元バージョンポインタ５０２を通して間接的に参照される。オブジェクトのプライマリバージョン５００は、さらにステータスワード５０４を含む。このステータスワード５０４は、データ領域５０８からのどのフィールドが推論的スレッド２０３によって書き込まれるのか、または読み出されるのかを特定するステータス情報を含む。オブジェクトの空間−時間次元バージョン５１０は、データ領域５１８のみを含む。
【００４１】
図６は、本発明の実施形態による、ステータスワード５０４の構造を示す。この実施形態では、ステータスワード５０４は、チェックポイント番号６０２および推論的ビット６０３を含む。推論的ビット６０３は、読み出しビット６０４および書き込みビット６０６を含む。推論的スレッド２０３による読み出しまたは書き込みが原因で、ステータスワード５０４が更新される必要があるとき、チェックポイント番号６０２は、システムの現在に時間で更新される。システムの時間次元における現在の時間は、結合またはロールバックにおいて別々に進む。これにより、チェックポイント番号６０２は、推論的ビット６０３の限定子として用いられ得る。チェックポイント番号６０２が現在の時間よりも小さい場合、推論的ビット６０３はリセットとして解釈され得る。
【００４２】
読み出しビット６０４は、最後の結合またはロールバック以来、データ領域５０８内のどのフィールドが読み出されたかを追跡する。同様に、書き込みビット６０６は、最後の結合またはロールバック以来、データ領域５０８内のどのフィールドが書き込まれたかを追跡する。本発明の１つの実施形態では、読み出しビット６０４は、データ領域５０８内の各フィールドに対して１ビット含む。別の実施形態では、読み出しビットは、データ領域５０８内のフィールドの数よりも少ないビットを含む。この実施形態では、読み出しビット６０４内の各ビットは、データ領域５０８の複数のフィールドに対応する。例えば、８つの読み出しビットがある場合、各ビットは、８番目毎のフィールドに対応する。書き込みビット６０６は、同様に、データ領域５０８内の１つまたは複数のフィールドに対応し得る。
【００４３】
（空間−時間次元更新プロセス）
空間−時間ディメンジョニングは、選択されたメモリ更新中に起こる。ローカル変数およびシステムスタックへのオペランドアクセスに対して、空間−時間次元バージョンは存在せず、特別なことは何も起こらない。ヒープ４０２のオブジェクトに対するヘッドスレッド２０２による読み出し動作中に、特別なことは何も起こらない。
【００４４】
特別な演算は、ヘッドスレッド２０２による書き込み動作、および、推論的スレッド２０３による書き込み動作に関連する。これらの特別な演算は、図７、８および９を参照して以下でより詳細に説明される。
【００４５】
図７は、本発明の実施形態による、ヘッドスレッド２０２によるオブジェクトに対する書き込み動作に関連する演算を示すフローチャートである。このシステムは、２つの空間−時間次元がこの時点で崩壊していない場合、オブジェクトのプライマリバージョン５００およびオブジェクトの空間−時間次元バージョン５１０へと書き込む（ステップ７０２）。次に、このシステムは、オブジェクトのプライマリバージョン５００内のステータスワード５０４をチェックして、ロールバックが必要とされるかどうかを判定する（ステップ７０４）。推論的スレッド２０３が以前にデータ要素を読み出す場合、ロールバックが必要とされる。同じメモリ素子は、推論的スレッド２０３による読み出し時に、２つのヒープの空間−時間次元がこのメモリ素子で崩壊しているとき、読み出され得る。また、推論的スレッド２０３がオブジェクトに以前に書き込み、オブジェクトの２つの次元はこの素子で崩壊していないことを保証する場合、および、現在の書き込み動作がオブジェクトのプライマリバージョン５００とオブジェクトの空間−時間次元バージョン５１０との両方を更新する場合、ロールバックが必要とされる。
【００４６】
ロールバックが必要とされる場合、システムは、推論的スレッド２０３にロールバック演算を実行させる（ステップ７０６）。このロールバック演算によって、推論的スレッド２０３は、ヘッドスレッド２０２がオブジェクトに書き込んだ後、オブジェクトから読み出すことが可能となる（または、そのオブジェクトへ書き込むことが可能となる）。
【００４７】
なお、図７に示された本発明の実施形態では、システムは、プライマリバージョン５００と空間−時間次元バージョン５１０との両方に対する書き込みを実行する。別の実施形態では、最初、システムは、推論的スレッド２０３が空間−時間次元バージョン５１０に以前に書き込まれたかどうかを判定するためにチェックする。書き込まれていない場合、システムは、プライマリバージョン５００と空間−時間次元バージョン５１０との両方に書き込む。書き込まれた場合、システムは、プライマリバージョン５００に書き込むのみである。
【００４８】
図８は、本発明の実施形態による、推論的スレッド２０３によるオブジェクトに対する読み出し動作に関連する演算を示すフローチャートである。この読み出し動作中、システムは、オブジェクトのプライマリバージョン５００内のステータスワード５０４のステータスビットを設定し、プライマリバージョン５００が読み出されたことを示す（ステップ８０２）。その後、推論的スレッド２０３は、空間−時間次元バージョン５１０が存在する場合、それを読み出す。存在しない場合、推論的スレッド２０３は、プライマリバージョン５００を読み出す。
【００４９】
図９は、本発明の実施形態による、推論的スレッド２０３によるメモリ素子に対する書き込み動作に関連する演算を示すフローチャートである。空間−時間次元バージョン５１０が存在しない場合、そのシステムは、空間−時間次元バージョン５１０を推論的ヒープ４０６に作成する（ステップ９０２）。また、このシステムは、ステータスワード５０４を更新して、このような更新が必要な場合、推論的スレッド２０３がオブジェクトに書き込んだことを示す（ステップ９０３）。このシステムは、次に、空間−時間次元バージョン５１０に書き込む（ステップ９０４）。プライマリバージョン５００と空間−時間次元バージョン５１０との両方に対する書き込み、あるいは、図７を参照して上記されたようなプライマリバージョン５００のみに対する書き込みの間を、ヘッドスレッド２０２が後で選択する必要がある場合、このような更新が必要である。
【００５０】
図１０は、本発明の実施形態による、ヘッドスレッド２０２と推論的スレッド２０３との間の結合演算に関連する演算を示すフローチャートである。例えば、推論的スレッド２０３が実行を開始するプログラムにおいて、ヘッドスレッド２０２があるポイントに到達するときに、結合演算が起こる。この結合演算によって、推論的スレッド２０３に関連する状態は、ヘッドスレッド２０２に関連する状態とマージされる。これは、推論的スレッドのスタック２０３をヘッドスレッドのスタック２０２にコピーする、および／または、マージすることに関連する（ステップ１００２）。また、これは、オブジェクトの空間−時間次元とオブジェクトのプライマリバージョンとをマージすること（ステップ１００４）に関し、おそらく、推論的ヒープ４０６をガーベッジコレクトすること（ステップ１００６）に関する。本発明の１実施形態において、スレッド２０２または２０３のうちの一方は、ステップ１００２および１００６を実行し、他方のスレッドは、ステップ１００４を実行する。
【００５１】
図１１は、本発明の別の実施形態による、ヘッドスレッド２０２と推論的スレッド２０３との間の結合演算に関連する演算を示すフローチャートである。この実施形態では、推論的スレッド２０３は、擬似ヘッドスレッドとして実行する。擬似ヘッドスレッドとして、推論的スレッド２０３は、オブジェクトの参照空間−時間次元バージョンに対して間接化技法（ｉｎｄｉｒｅｃｔｉｏｎ）を用いるが、オブジェクトをマークすることも、バージョンを作成することもない。推論的スレッド２０３が擬似ヘッドスレッドとして行動している一方で、ヘッドスレッド２０２は、オブジェクトのプライマリバージョンを更新する。
【００５２】
（さらなる推論的スレッドへの拡張）
本発明はシングル推論的スレッドの場合に対して説明されてきたが、本発明は、並列にデータオブジェクトの複数の空間−時間次元バージョンで動作する複数の推論的スレッドを提供するように拡張され得る。
【００５３】
（インターリーブ実行）
図１２は、本発明の実施形態による、ヘッドスレッドおよび関連する推論的スレッドのインターリーブ実行を示すフローチャートである。図１を参照して、ヘッドスレッド２０２、推論的スレッド２０３（および、可能な場合、ヘッドスレッド２０２に対する他の推論的スレッド）は、プロセッサ１０２で同時に実行される。
【００５４】
なお、これらのスレッドからの命令は、ラウンドロビンの様態で時間多重化されて、同じ命令パイプライン１０７において実行する。これは、ＣＰＵ１０２のシングルスレッド実行のスピードを効果的に増加させる。なぜなら、ヘッドスレッド２０２、推論的スレッド２０３、および可能ならば他の推論的スレッドは、ＣＰＵ１０２で同時に実行し、同じ実行のスレッドに対して仕事を実行しているからである。
【００５５】
さらに、なお、本発明は、本明細書中に記載された推論的実行の正確な形式に制限されない。概して、本発明は、マルチスレッドを利用する推論的実行の任意のタイプに適用され得る。
【００５６】
本発明の上記の実施形態は、例示および説明することのみを目的として示されてきた。それらは、完全に網羅していることを意図しておらず、開示された形式に本発明を制限することも意図していない。従って、多くの修正および改変が当業者に明らかである。さらに、上記の開示は、本発明に制限することを意図していない。本発明の範囲は、添付の特許請求の範囲に定義される。
【図面の簡単な説明】
【００５７】
【図１】図１は、本発明の実施形態による、コンピュータシステムを示す。
【図２Ａ】図２Ａは、シングルスレッドによる、メソッドの連続的実行を示す。
【図２Ｂ】図２Ｂは、本発明の実施形態による、メソッドの空間および時間次元実行を示す。
【図３】図３は、本発明の実施形態による、メソッドの空間および時間次元実行中のシステムスタックの状態を示す。
【図４】図４は、本発明の実施形態による、スタックとヒープとの間のメモリの分割方法を示す。
【図５】図５は、本発明の実施形態による、オブジェクトのプライマリバージョンおよび空間−時間次元バージョンの構造を示す。
【図６】図６は、本発明の実施形態による、オブジェクトのステータスワードの構造を示す。
【図７】図７は、本発明の実施形態による、ヘッドスレッドによってメモリ素子に対する書き込みを実行することに関する演算を示すフローチャートである。
【図８】図８は、本発明の実施形態による、推論的スレッドによってメモリ素子に対する読み出しを実行することに関する演算を示すフローチャートである。
【図９】図９は、本発明の実施形態による、推論的スレッドによってメモリ素子に対する書き込みを実行することに関する演算を示すフローチャートである。
【図１０】図１０は、本発明の実施形態による、ヘッドスレッドと推論的スレッドとの間の結合を実行することに関する演算を示すフローチャートである。
【図１１】図１１は、本発明の別の実施形態による、ヘッドスレッドと推論的スレッドとの間の結合を実行することに関する演算を示すフローチャートである。
【図１２】図１２は、本発明の実施形態による、ヘッドスレッドおよび関連する推論的スレッドのインターリーブ実行を示すフローチャートである。
【図１】
2005529383.tif 000003
【図２Ａ】
2005529383.tif 000004
【図２Ｂ】
2005529383.tif 000005
【図３】
2005529383.tif 000006
【図４】
2005529383.tif 000007
【図５】
2005529383.tif 000008
【図６】
2005529383.tif 000009
【図７】
2005529383.tif 000010
【図８】
2005529383.tif 000011
【図９】
2005529383.tif 000012
【図１０】
2005529383.tif 000013
【図１１】
2005529383.tif 000014
【図１２】
2005529383.tif 000015
【国際調査報告】
2005529383.tif 000016