(57)【特許請求の範囲】
【請求項１】
投機的に実行されるスレッドのローカルにリタイアされた命令に関するデータを記憶する複数のデータ・キャッシュ・ユニット（DCU）であって、各ラインの投機的更新状態を分類するためのライン毎のバージョン・ビットを含む、DCUと；
前記複数のDCUのラインからのデータをマージする、前記複数のDCUに結合されたマージング・レベル・キャッシュ（MLC）であって、キャッシュ・ラインが投機的な状態を含むことを示すキャッシュ・ライン毎の投機的ビットおよびチャンクへの変更を示す最終バージョン・ビットを含む、MLCと；
前記投機的に実行されるスレッドの命令をグローバルにリタイアさせるコア間メモリ整合性モジュール（ICMC）であって、グローバルにリタイアされる前記命令に関するデータは前記MLCに記憶されるものである、前記コア間メモリ整合性モジュール（ICMC）とを有する、
装置。
【請求項２】
請求項１記載の装置であって、前記ICMCがさらに：
投機的に実行されるスレッドの順序付け命令を、ローカルにリタイアされたのちに記憶する複数のメモリ先入れ先出し（FIFO:  first  in,  first  out）待ち行列を有しており、前記メモリFIFO待ち行列内の各エントリーは、コミットすべき次の命令が存在するメモリFIFO待ち行列の先頭を同定するプログラム順ポインタ（POP）を含む、
装置。
【請求項３】
請求項２記載の装置であって、前記ICMCがさらに：
複数の投機的に実行されるスレッドの順序付け命令をもとのプログラム順とするためのフロー再構成を前記ICMCが行う際に、前記複数のメモリFIFO待ち行列のいずれを選択するのかを切り換えるスイッチを有する、
装置。
【請求項４】
請求項２記載の装置であって、前記ICMCがさらに：
前記複数のメモリFIFO待ち行列内に位置されるストア命令によって更新されるべき前記MLCのラインを同定する更新記述テーブル（UDT）を有する、
装置。
【請求項５】
請求項３記載の装置であって、前記ICMCがさらに：
前記投機的に実行されるスレッドの実行中の投機ミスを是正するために前の状態にロールバックするレジスタ・チェックポインティング論理を有する、
装置。
【請求項６】
前記投機的に実行されるスレッドの命令を処理する複数の機能ユニットをさらに有する、請求項１記載の装置。
【請求項７】
前記MLCに結合されたL3キャッシュをさらに有する、請求項１記載の装置。
【請求項８】
コードのある領域からの第一および第二のスレッドをそれぞれ第一および第二の処理コアにおいて投機的に実行する段階と；
前記第一および第二の処理コアのそれぞれの第一レベル・キャッシュにおいて前記第一および第二のスレッドの各命令をローカルにリタイアさせる段階と；
共有されるマージング・レベル・キャッシュにおいて前記第一および第二のスレッドの各命令をグローバルにリタイアさせる段階と；
前記第一および第二の処理コアのそれぞれに対応するメモリ先入れ先出し（FIFO）待ち行列に、前記第一および第二のスレッドの実行された各順序付け命令を記憶する段階と；
投機的に実行される前記第一のスレッドと前記第二のスレッドの前記順序付け命令を、コードの前記領域におけるもとのプログラム順とするためのフロー再構成を要求する条件が、前記第一および第二のスレッドの実行中に発生したことを判別する段階と；
記憶された実行された順序付け命令を使ってコードの前記領域のフローを再構成する段階とを含む、
方法。
【請求項９】
請求項８記載の方法であって、さらに：
前記メモリFIFO待ち行列の一方に記憶されている投機的に実行されたコードの領域の前記第一の順序付け命令を読み出す段階と；
前記第一の順序付け命令に関連付けられたプログラム順ポインタ（POP）値を読み出す段階と；
前記POP値がメモリFIFO切り換えを示す場合、他方のメモリFIFO待ち行列に切り換えて、その第一の記憶されている命令を読み出す段階とを含む、
方法。
【請求項１０】
前記POP値が、前記メモリFIFO待ち行列に記憶されている前記順序付け命令毎の１ビット値である、請求項９記載の方法。
【請求項１１】
前記POP値がメモリFIFO切り換えがないことを示す場合、前記メモリFIFO待ち行列の次の記憶されている命令を読み出す段階をさらに含む、
請求項９記載の方法。
【請求項１２】
記憶された実行された順序付け命令を使ってコードの前記領域のフローを再構成する前記段階を、ソフトウェアが実行する、請求項８記載の方法。
【請求項１３】
記憶された実行された順序付け命令を使ってコードの前記領域のフローを再構成する前記段階を、ハードウェアのコア間メモリ整合性モジュール（ICMC）が実行する、請求項８記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の諸実施形態は、概括的には情報処理の分野に関し、より詳細にはコンピューティング・システムおよびマイクロプロセッサにおけるマルチスレッド実行の分野に関する。
【背景技術】
【０００２】
単一スレッド・プロセッサは、命令レベルの並列（ILP:  instruction  level  parallelism）を利用することによりここ数十年の間に著しいパフォーマンス上の改善を遂げた。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
しかしながら、この種の並列は時に利用するのが困難であり、複雑なハードウェア構造を必要とするため、実用できないほどの電力消費および設計上の複雑さをもたらしうる。さらに、複雑さおよび電力のこの増大のため、見返りは低減する。チップ・マルチプロセッサ（CMP:  chip  multiprocessor）が、そこそこの電力予算のもとでさらなるプロセッサ・パフォーマンス改善を与えるための有望な代替として登場している。
【課題を解決するための手段】
【０００４】
課題は請求項記載の手段により達成される。
【図面の簡単な説明】
【０００５】
本発明の諸実施形態は、限定ではなく例として、付属の図面において図示される。図面において、同様の参照符号は同様の要素を指す。
【図１】細粒度のマルチスレッド・システムの少なくとも一つの実施形態についてのハードウェアおよびソフトウェア要素を示すブロック図である。
【図２】SpMTを利用する例示的なフローを示す図である。
【図３】四つの基本ブロックで形成される小さなループの例示的な細粒度のスレッド分解を示す図である。
【図４】二つの処理コアにおいて実行される二つのスレッドの例であって、互いの間にデータ依存性グラフ（DDG:  Data  Dependence  Graph）として示される二通りのデータ依存性をもつ場合を示す図である。
【図５】制御フローを考えるときの、スレッド分割の結果の三つの異なる例を示す図である。
【図６】いくつかの実施形態の分割方式の概観を示す図である。
【図７】オプティマイザにおいて細粒度のSpMTを利用するプログラム・コードを生成するための方法の実施形態を示す図である。
【図８】例示的なマルチレベル・グラフを示す図である。
【図９】粗視化方法の実施形態を示す図である。
【図１０】粗視化方法の擬似コード表現の実施形態を示す図である。
【図１１】FIFO待ち行列中に託されるスレッドの実施形態を示す図である。
【図１２】最適化される領域についてPOPマークを決定するための方法の実施形態を示す図である。
【図１３】ハンモックをもつループを使う例を示す図である。
【図１４】POPマークを使うフローを再構成する方法の実施形態を示す図である。
【図１５】スレッド順序再構成機構の実施形態が用いられうるマルチコア・システムの実施形態を示すブロック図である。
【図１６】協働モードで動作するタイルの例を示す図である。
【図１７】本発明の少なくとも一つの実施形態に基づく、投機的マルチスレッディングをサポートする例示的なメモリ階層構造を示すブロック図である。
【図１８】最適化されたモードでストアがグローバルにリタイアさせられるときに行われるアクションの方法の実施形態を示す図である。
【図１９】最適化されたモードでロードがグローバルにリタイアさせられようとしているときに行われるアクションの方法の実施形態を示す図である。
【図２０】ICMCの実施形態を示す図である。
【図２１】チェックポインティング機構のROBの少なくとも一つの実施形態を示す図である。
【図２２】レジスタ・チェックポインティング・ハードウェアの少なくとも一つの実施形態を示すブロック図である。
【図２３ａ】チェックポイントを使う実施形態を示す図の第一の部分である。
【図２３ｂ】チェックポイントを使う実施形態を示す図の第二の部分である。
【図２３ｃ】チェックポイントを使う実施形態を示す図の第三の部分である。
【図２４】スレッド・レベルの再構成を利用するマルチプロセッサの実施形態を示す図である。
【図２５】本発明のある実施形態が使用されうるフロント・サイド・バス（FSB:  front-side-bus）コンピュータ・システムを示す図である。
【図２６】本発明のある実施形態に基づくシステムのブロック図である。
【図２７】本発明のある実施形態に基づくシステム実施形態のブロック図である。
【図２８】本発明のある実施形態に基づくシステム実施形態のブロック図である。
【発明を実施するための形態】
【０００６】
本発明の諸実施形態は、シーケンシャル・プログラムを複数のスレッドまたは実行のストリームに分解し、それらを並列に実行し、シーケンシャルな実行を再構成する技法に関する。たとえば、本稿で記載される実施形態のいくつかは、任意に複数のスレッドに割り当てられたときに命令のシーケンシャルな順序を再構成することを許容する。よって、本稿に記載されるこれらの実施形態は、シーケンシャルなプログラムを複数のスレッドまたは実行のストリームに分解する任意の技法とともに使用されうる。特に、本稿では、命令の粒度で投機的スレッドに分解されたアプリケーションのシーケンシャルな順序を再構成するために使用されうる。
【０００７】
投機的マルチスレッディング（speculative  multithreading）は、シーケンシャルなコードが異なるコアまたは同じコアの異なる論理プロセッサ（機能単位）において並列に実行されるべきスレッドに分解される並列化技法である。投機的マルチスレッディング（「SpMT」）は、単一スレッド・パフォーマンスを増進するよう、複数のコアまたは機能単位をてこ入れしうる。SpMTは、ランタイム条件に依存して原子的にコミット（commit）または破棄（squash）されうるスレッドをサポートする。
【０００８】
以下で異なるコアで走るスレッドのコンテキストで論じる際、本稿で論じられる概念は、投機的マルチスレッディング様実行についても適用可能である。すなわち、本稿で論じられる概念は、同じコアの異なるSMT論理プロセッサ上で走る投機的スレッドについても適用可能である。
【０００９】
〈細粒度SpMTパラダイム〉
投機的マルチスレッディングは、単一スレッド・パフォーマンスを増進するよう複数コアをてこ入れする。投機的マルチスレッディングは、ランタイム条件に依存して原子的にコミットまたは破棄されうるスレッドをサポートする。伝統的な投機的マルチスレッディング方式では、各スレッドは連続する命令の大きなチャンク〔かたまり〕（たとえばループ反復工程または関数呼び出し）を実行する。概念的に、これは動的な命令ストリームをチャンクに分割してそれらを並列に実行することと等価である。しかしながら、この種の分割はスレッド間のあまりに多くの依存性をもたらすことがある。このことは、利用できるTLPを制限し、パフォーマンスの害になる。細粒度SpMTでは、命令は、伝統的なスレッド方式よりも細かい粒度でスレッド間に分配されうる。この意味で、この新しいモデルは、以前のスレッド利用パラダイムの上位集合〔スーパーセット〕であり、伝統的な方式よりもTLPをよりよく活用できる。
【００１０】
以下では、複数のハードウェア・コンテキスト、すなわち処理コアを使って単一スレッドのアプリケーションを高速化する静的または動的なオプティマイザを使う投機的マルチスレッディング・パラダイムの実施形態が記述される。シーケンシャル・コードまたは動的ストリームは非常に細かい粒度（個々の命令レベル）で複数の投機的スレッドに分解される。これは、連続する命令からなる大きなチャンクがスレッドに割り当てられる伝統的なスレッド利用技法とは対照的である。この柔軟性のおかげで、伝統的な分割方式だったら多数のスレッド間データ依存性を生じてパフォーマンスが制限されてしまうことがありうるシーケンシャル・アプリケーションに対してTLPが利用できる。このことはまた、スレッドの作業バランスを改善し、および／または利用されうるメモリ・レベルの並列の量を増大させうる。
【００１１】
スレッド間データ依存性がある場合、それを扱う三つの異なるアプローチが記述される：１）明示的なスレッド間通信を使う；２）これらの依存性をローカルに満たすために事前計算スライス（pre-computation  slices）（複製された命令）を使う；および／または３）それらの依存性を無視し、依存性がないと推定し、ハードウェアに潜在的な違反を検出させる。この細粒度スレッディングでは、スレッド内の制御フローはローカルに管理され、その割り当てられた命令の実行に影響するスレッド中のブランチを含むことを必要とするのみである。したがって、コア・フロントエンドは、スレッドの制御フローを扱うために、あるいは分岐予測ミスを管理するためにいかなる追加的なハードウェアも必要とせず、各コアは独立して命令をフェッチし、実行し、コミットする（明示的なスレッド間通信によって起こる同期ポイントを除いて）。
【００１２】
図１は、細粒度〔細かい粒度〕のマルチスレッディング・システムの少なくとも一つの実施形態のためのハードウェアおよびソフトウェア要素を示すブロック図である。もとのスレッド１０１は、スレッド生成のための単数または複数のモジュール１０３を含むコンパイラ、オプティマイザなどのようなソフトウェアに供給される。スレッドまたはその諸領域は、単数または複数のモジュール１０５によって複数のスレッドに分解される。各スレッドは、自分のコア／ハードウェア・コンテキスト１０７上で実行される。これらのコア／コンテキスト１０７は、もとのプログラム順序を再構成するための論理またはその部分集合１０９、メモリ状態のための論理１１１、レジスタ状態のための論理１１３および他の論理１１５といったいくつかの異なる論理コンポーネントに結合される。
【００１３】
図２は、SpMTを利用する例示的なフローを示している。２０１において、シーケンシャル・アプリケーション（プログラム）がコンパイラ、オプティマイザまたは他のエンティティによって受領される。このプログラムは、実行可能コードまたはソース・コードの形であってもよい。
【００１４】
シーケンシャル・アプリケーションの少なくとも一部分は、２０３で、一つまたは複数の最適化された領域を形成する、細粒度のスレッドに分解される。この分解の諸実施形態は後述するが、これはコンパイラ、オプティマイザまたは他のエンティティによって実行されてもよい。
【００１５】
２０５では、シーケンシャル・アプリケーションは通常通りに実行される。２０７では、アプリケーションが最適化された領域にはいるべきかどうかの判定がされる。典型的には、派生（spawn）命令は、最適化された領域の先頭を表す。この命令または等価物は通常、プログラムの実行に先立って、たとえばコンパイラにより追加される。
【００１６】
コードが通常通りに処理されるべきであれば、２０５において通常通りに実行される。しかしながら、派生命令があった場合には、最適化された領域について一つまたは複数のスレッドが生成され、２０９で、プログラムは協働（投機的マルチスレッディング）モードで実行される。これは２１１で最適化された領域の完了が判別されるまで続く。
【００１７】
最適化された領域が完了すると、コミットされて２１３でアプリケーションの通常実行が続けられる。
【００１８】
〈細粒度のスレッド分解〉
細粒度のスレッド分解は、シーケンシャル・コードまたは動的ストリームからのスレッドの生成であり、個々の命令はスレッド間で柔軟に分配される。これは、動的オプティマイザによって、あるいはコンパイル時に静的に実施されうる。
【００１９】
図３は、四つの基本ブロック（A、B、C、D）で形成される小さなループの例示的な細粒度のスレッド分解を示している。各基本ブロックは、Ai、Bi、Ci、Diとラベル付けされるいくつかの命令からなる。図の左側は、ループのもとの制御フロー・グラフ（CFG:  control-flow  graph）と、あるコンテキスト中で実行されるときの動的ストリームの一片を時間を追って示している。図の右側は、二つのスレッドへの一つの可能な細粒度のスレッド分解の結果を示しており、各スレッドは自分のコンテキストをもつ。結果として得られる各スレッドのCFGおよびそれらのスレッドが並列に実行されるときの動的ストリームが図に示されている。このスレッド分解は、命令の大きなチャンクがスレッドに割り当てられる伝統的な方式よりも柔軟である（典型的には、伝統的なスレッディング方式はループ反復工程を各スレッドに割り当てる）。図３では例としてループが示されているが、細粒度のスレッド分解は、いかなる高レベルのコード構造とも直交し、いかなるシーケンシャル・コードまたは動的ストリームにも適用されうる。
【００２０】
個々の命令をスレッド間で分配する柔軟性は、それらを生成するための異なるポリシーを実装するためにてこ入れされてもよい。シーケンシャル・コードまたは動的ストリームのスレッド分解に寄与し、スレッド・レベルの並列をよりよく活用することを許容しうるポリシーのいくつかは、これに限られないが、次のうちの一つまたは複数を含む：１）スレッド間データ依存性の量を最小にするようスレッドに命令が割り当てられる；２）スレッドの作業負荷を均衡させるようスレッドに命令が割り当てられる（細粒度のスレッド分解は、スレッドを均衡させようとする決定が命令レベルでできるので、作業負荷バランスの微調整を許容する）；および３）メモリ・レベルの並列（MLP:  memory  level  parallelism）をよりよく活用するようスレッドに命令が割り当てられてもよい。MLPは、メモリが限られたアプリケーションのための並列の源である。これらのアプリケーションについては、MLPの増大はパフォーマンスの著しい向上につながりうる。細粒度のスレッド分解は、MLPを増大させるためにスレッド間でロード命令を分配することを許容する。
【００２１】
〈スレッド間データ依存性管理〉
投機的マルチスレッディング・パラダイムの論点の一つは、スレッド間データ依存性を扱うことである。スレッド間のデータ依存性を解決するための、１）事前計算（pre-computation）および２）通信（communication）の二つの機構を下記で述べる。
【００２２】
第一の機構は、スレッド間データ依存性を分解してそれらをローカルに満足させるための事前計算スライス（略して「pスライス（pslice）」）の使用である。たとえば、スレッドT2によって生成されるデータを必要とする、スレッドT1に割り当てられた命令「I」があるとすると、そのpスライスに属するすべての必要とされる命令（Iによって必要とされる前記データを生成するために必要とされる命令からなる部分集合）でT1に割り当てられていないものがT1中に複製される（重複される）。これらの命令は、本稿では複製された命令と称される。これらの複製された命令は通常の命令として扱われ、スレッドに割り当てられた残りの命令と一緒にスケジューリングされる。結果として、投機的スレッドでは、複製された命令が残りの命令と混合され、スレッドの実行時間を最小化するために再配列されうる。さらに、値を事前計算することは、そのpスライスに属するすべての命令を複製することは含意しない。後述するように、その値を計算するために必要とされる中間データの一部は異なるスレッドにおいて計算されて通信されることができるからである。
【００２３】
第二に、（ｉ）ローカルに満足するためにはあまりに多くの複製された命令を必要とすることがありうる、あるいは（ｉｉ）実行時間を害することなくある量のサイクルだけ遅延されてもよいような依存性は、明示的なスレッド間通信を通じて解決される。これは、複製されなければならない命令の量を減らすが、明示的な通信それぞれについて同期ポイントを導入する（少なくとも受領側命令において）。
【００２４】
図４は、データ依存性グラフ（「DDG」）として示される二つのデータ依存性をもつ、二つの処理コアで実行されるべき二つのスレッドの例を示している。しかしながら、当業者は、本稿に記載される並べ替え実施形態は、より多数のスレッドへの分解および／またはその上で分解されたスレッドを実行すべきより多数のコアもしくは論理プロセッサを含む細粒度のマルチスレッドとともに利用されてもよいことを認識するであろう。図では、丸は命令であり、矢印は二つの命令の間のデータ依存性を表す。
【００２５】
左側には、もとのシーケンシャルな制御フロー・グラフ（「CFG」）と、ループのシーケンシャル実行のための、命令の例示的な動的な実行ストリームがある。このCFGにおいて、命令「ｂ」および「ｄ」は命令「ａ」へのデータ依存性をもつ。
【００２６】
右側は、左側のシーケンシャル・ループCFGに対する例示的なスレッド分解を示している。二つのCFGおよび二つの動的な実行ストリームは、ひとたびループが命令の粒度で二つのスレッドに分解されると生成される（命令D1は両方のスレッドで複製される）。これは、二つの分解されたスレッドに対する分解された制御フロー・グラフを示しており、また、ループの分解されたスレッドの同時並行実行のための、見本となる可能な動的実行ストリームをも示している。このために、派生命令が実行され、派生元（spawner）スレッドおよび被派生者（spawnee）スレッドが、それら二つの実行ストリーム間のいかなる明示的な順序（order）もなしに、それらの割り当てられた命令のフェッチおよび実行を始めることが想定される。右側は、この例における異なるスレッド実行ストリームに属する二つの所与の命令の間の順序を知ることが、自明ではないことを示している。見て取れるように、一つの依存性は、事前計算スライスを通じて解決される。事前計算スライスは、スレッド１における一つの複製された命令（「ａ」）を必要とする。もう一方の依存性は、明示的な通信（「ｈ」と「ｆ」の間の）を通じて解決される。
【００２７】
スレッド分解時には予見されなかった追加的な依存性がランタイムに現れることがありうる。細粒度のSpMTを実装するシステム（ハードウェア、ファームウェア、ソフトウェアおよびそれらの組み合わせ）は、そのような依存性の違反を検出して、問題のあるスレッド（単数または複数）を破棄し、その実行をリスタートするべきである。
【００２８】
少なくとも一つの実施形態については、分解された命令ストリームからのシーケンシャルな実行の再構成はハードウェアで行われる。いくつかの実施形態については、このハードウェア機能は、のちに詳述するコア間メモリ整合性モジュール（ICMC:  Inter-Core  Memory  Coherency  Module）によって実行される。
【００２９】
〈制御フロー管理〉
細粒度のSpMTを使って、命令の粒度で命令をスレッドに分配してそれらの命令を並列に実行する際、もとのシーケンシャルな実行の制御フローが考慮および／または管理されるべきである。たとえば、制御フローは、投機的スレッドが生成されるときにソフトウェアによって管理されてもよい。よって、細粒度のSpMTを使うプロセッサのフロント・エンドは、細粒度のSpMTスレッドの制御フローを扱うために、あるいはブランチ予測ミスを管理するために、いかなる追加的なハードウェアも必要としない。むしろ、所与のスレッドについての制御投機は、その場にある通常の予測および復元機構を使うことによって、実行するコンテキストにおいてローカルに管理される。
【００３０】
細粒度のSpMTでは、すべてのスレッドは、その命令のための制御経路を計算するために必要とするすべての分枝を含む。所与のスレッドのいずれかの命令を実行するために必要とされるがそのスレッドにもともと含まれてはいなかった分枝は、複製される。すべての分枝がすべてのスレッドにおいて必要とされるわけではなく、命令の実行に影響するものだけが必要とされることを注意しておく。さらに、スレッド中に分岐命令を有することは、該スレッド中のこの分岐を計算するために必要とされるすべての命令も含まれる必要があることを意味するわけではない。というのも、SpMTパラダイムは、スレッド間通信を許容するからである。たとえば、考えられるシナリオとして、一つのスレッドだけが分岐条件を計算し、それを残りのスレッドに通信する。もう一つのシナリオは、所与の分岐の制御フローの計算が完全にすべてのスレッドの間に拡散されるというものである。
【００３１】
図５は、制御フローを考えるときのスレッド分割の結果の三つの異なる例を示している。制御フローに関わる命令は強調されており、矢印は明示的なスレッド間通信を示す。見て取れるように、三つすべての場合において、分岐（もとのコードにおけるBz  LABEL）はそれを必要とするすべてのスレッド（T1およびT2）において複製されている。単一の制御フロー計算（ａ）の場合、分岐を計算する命令はT2によって実行され、結果がT1に送られる。制御フローの完全な複製（ｂ）では、計算は両方のスレッド（T1およびT2）で複製され、明示的な通信の必要はない。分岐の計算は、プログラム中の他のどの計算とも同じように分割され、よって、明示的に通信する異なるスレッド（実はその分岐などどうでもよいスレッドも含む）の間で分割されることがありうる。この例は、制御フローの分割計算（ｃ）において示されている。
【００３２】
少なくとも一つの実施形態については、シーケンシャルなコード片は、通常のツールによっては効率的に並列化されることができない完全なシーケンシャル・プログラムであってもよい。少なくとも一つの他の実施形態については、シーケンシャルなコードは、並列化されたアプリケーションのシリアル部分であってもよい。投機的マルチスレッディングは、計算量効率的な非常にワイドなコアとして振る舞うマルチコア・アーキテクチャが、単一スレッドのアプリケーションをより高速に実行できるようにする。
【００３３】
本稿に記載される少なくともいくつかの実施形態については、もとの単一スレッドのアプリケーションまたはその一部がいくつかの投機的スレッドに分割されており、各スレッドがもとのシーケンシャルなアプリケーションまたは部分の作業全体の部分集合を実行すると想定される。そのような分解は、たとえば外部ツール（たとえば、動的オプティマイザ、コンパイラなど）によって実行されてもよい。
【００３４】
〈単一スレッド・プログラムからの複数の投機スレッドの生成〉
シーケンシャルなアプリケーションが投機的スレッドに分解される処理フェーズは、本稿では「アナフェーズ（anaphse）」と称される。議論のため、そのような分解はコンパイル時に行われると想定するが、上述したように、そのような分解はコンパイラ以外の他の外部ツール（たとえば動的オプティマイザ）を介して行われてもよい。SpMTスレッドは、アプリケーションの実行時間の大半をカバーする諸領域について生成される。本節では、このモデルにおいて考えられる投機的スレッドについてまず述べ、そして関連する実行モデル、そして最後にそれらを生成するためのコンパイラ技法へと進む。
【００３５】
投機的スレッドの間ではスレッド間依存性が生じうる。これらの依存性は、ある投機的スレッドにおいて生成される値が別の投機的スレッドで必要とされるときに生じる。スレッド間依存性は、コードを解析することによって、および／またはプロファイル情報を使うことによってコンパイル時に検出されうる。しかしながら、コンパイル時にすべての可能な依存性が検出されるのではないこと、スレッドへの分解が投機的な仕方で実行されることもありうる。少なくとも一つの実施形態については、ハードウェアが、異なる投機的スレッドに割り当てられた二つの命令の間でランタイムに生じうる、それらのスレッドをコンパイラが生成したときには考慮されなかったメモリ依存性を扱う役割を担う。
【００３６】
コンパイル時に同定されるすべてのスレッド間依存性については、それらを扱うために投機的スレッド内に適切なコードが生成される。具体的には、以下の技法の一つが適用される：（ｉ）明示的な通信によって依存性が満足される；あるいは（ｉｉ）依存性が事前計算スライス（pスライス）、すなわち消費されるデータ（「ライブイン（live-ins）」）を生成するために必要とされる命令の部分集合によって満足される。pスライスに含まれる命令は、二つ以上のスレッドに割り当てられる必要があることがありうる。したがって、投機的スレッドは、図３における命令D1の場合のように、複製された命令を含むことがありうる。
【００３７】
最後に、各投機的スレッドは、制御フローの観点からは自己完結的である。これは、各スレッドが、それ自身の実行を解決するために必要とするすべての分枝をもつということを意味する。これを達成するためには、スレッドの命令の実行に影響する分枝が同じスレッドに置かれる必要があることを注意しておく。分枝が二つ以上のスレッドに置かれる必要がある場合には、その分枝は複製される。これも、スレッドが生成されるときにコンパイラによって扱われる。
【００３８】
実行に関しては、投機的スレッドは、下記で例解するようなマルチコア・プロセッサ上で協働的な仕方で実行される。図６では、いくつかの実施形態の分解方式が呈示されている。この議論のために、投機的スレッド（スレッドid  0（「tid0」）およびスレッドid  1（「tid1」）に対応）が二つの異なるコアによって（たとえば図１５のタイルを参照）、あるいは同じもしくは異なるコアの二つの異なる論理プロセッサによって同時並行して実行されると想定される。しかしながら、当業者は、普通ならシーケンシャルな命令のセットの同時並行的な実行を行うためのタイルが二つより多くのタイルを含んでいてもよいことを認識するであろう。同様に、本稿に記載される技法は、コア当たり複数のSMT論理プロセッサを含むシステムに適用可能である。
【００３９】
上で論じたように、コンパイラまたは同様のエンティティが、特定の領域（今の例解では領域B  ６１０）が投機的マルチスレッディングを適用するために好適であることを検出する。次いでこの領域６１０は、アプリケーション・コード内のどこかほかの場所に領域６１０の最適化されたバージョン６４０としてマップされる投機的スレッド６２０、６３０に分解される。
【００４０】
派生命令（spawn  instruction）６５０が、もとのコードにおいて、最適化された領域（領域B  ６１０）にはいる前に挿入される。派生オペレーションは、新たなスレッドを生成し、派生元および被派生者の投機的スレッドの両方は、コードの最適化されたバージョン６４０の実行を開始する。図示した例では、派生元スレッドは投機的スレッドの一つ（たとえば６２０）を実行してもよく、一方、被派生者スレッドはもう一つの投機的スレッド（たとえば６３０）を実行してもよい。
【００４１】
二つの投機的スレッドが協働的な仕方であるとき、スレッド間依存性が明示的な通信によって満たされるときに、両者の間の同期が行われる。しかしながら、通信は、適切な通信機構が置かれる限りにおいて消費者側において同期を含意しうるのみである。これらの通信のためには通常のメモリまたは専用論理を使うことができる。
【００４２】
他方、協働的なモードにある間に違反、例外および／または割り込みが起こることがあり、投機的スレッドはロールバックされる必要があることがある。これは、ソフトウェア・スレッドには完全に透明な仕方でハードウェアによって扱われる、あるいはそれを扱うための何らかの追加的なコード（たとえばロールバック・コード６６０参照）をコンパイル時に含めることによって扱われることができる。
【００４３】
両方のスレッドが最後の命令に達するとき、それらは最適化された領域の出口に同期し、投機的状態は非投機的になり、実行は一つの単一スレッドで継続し、タイルは単一コア・モードを再開する。本稿で用いられるところの「タイル（tile）」は、図１５との関連でさらに詳述される。一般に、タイルとは、普通ならシーケンシャルな命令のセットの異なる部分を同時並行して実行するよう作用する二つ以上のコアのグループである（ここで、「異なる」部分とはいっても、複製された命令を含んでいてもよい）。
【００４４】
投機的スレッドは、典型的にはコンパイル時に生成される。よって、コンパイラは：（ｉ）アプリケーションをプロファイリングし、（２）コードを解析して並列化のために最も便利なコード領域を検出し、（３）選択された領域を投機的スレッドに分解し、（４）最適化されたコードおよびロールバック・コードを生成する役割を担う。さらに、本稿で論じられる技法は、あらゆる型のループおよび非ループ・コードに適用されうる。少なくとも一つの実施形態については、投機的スレッドが生成されるループは展開〔アンロール〕されてもよく、および／または頻繁に実行されるルーチンがインライン化されてもよい。
【００４５】
図７は、オプティマイザにおいて細粒度のSpMTを利用する、プログラム・コードを生成する方法のある実施形態を示している。７０１では、「もとの」プログラム・コードが受領または生成される。このプログラム・コードは典型的にはいくつかのコード領域を含む。
【００４６】
７０３において、もとのプログラム・コードは、データ依存性グラフ（DDG）および制御フロー・グラフ（CFG）を生成するために使われる。あるいはまた、DDGおよびCFGはオプティマイザによって受領されてもよい。
【００４７】
これらのグラフが解析されて、マルチスレッド式の投機的実行の候補となる一つまたは複数の領域が探される。たとえば、「ホット」な領域は、SpMTが有益であろうことを指示しうる。この解析の一環として、DDGにおけるノード（x86命令のような）およびエッジは、それらの動的発生および命令と命令の間に何回データ依存性（レジスタまたはメモリ）が発生するかによって重み付けされる。CFGにおける制御エッジは、取られる経路の頻度によって重み付けされる。このプロファイリング情報がグラフに加えられ、両方のグラフは７０５において、プログラム依存性グラフ（PDG:  program  dependence  graph）に畳み込まれる。他の実施形態では、これらのグラフは畳み込まれない。
【００４８】
いくつかの実施形態では、PDGは、たとえばコード並べ替え（code  reordering）、定数伝播（constant  propagation）、ループ展開（loop  unrolling）およびルーチン特殊化（routine  specialization）のような安全なデータ・フローおよび制御フロー・コード変換を適用することによって最適化される。
【００４９】
７０７では、粗視化（coarsening）が実行される。粗視化の間、所望されるパーティションの数（たとえば、二つのスレッドの場合二つのパーティション）と同数のノードがあるようになるまで、ノード（命令）は逐次反復的により大きなノードに畳み込まれる（collapsed）。粗視化は比較的良好なパーティションを与える。
【００５０】
粗視化ステップでは、グラフ・サイズは、ノードの対をスーパーノードに畳み込むことによって逐次的に縮小され、最終的なグラフはスレッドと同数のスーパーノードをもち、命令のスレッドへの第一のパーティションを記述する。このプロセスの間、種々のレベルのスーパーノードが、マルチレベル・グラフにおいて生成される（例示的なマルチレベル・グラフは図８に示される）。所与のレベルからのノードは、その下のレベルからの一つまたは複数のノードを含む。これは、図８において見て取れる。この図では、レベル０のノードが個々の命令である。より粗いノードはスーパーノードと称され、用語ノードおよびスーパーノードは本明細書を通じて交換可能に称される。また、いちばん下のレベルがもとのグラフ（アルゴリズムのこのステップに渡されたグラフ）を含み、いちばん上のレベルは生成するのが所望されるスレッドと同数のスーパーノードのみを含むよう、各レベルはだんだん少数のノードをもつ。あるスーパーノードに属する諸ノードは、同じスレッドに割り当てられる。
【００５１】
そうするために、ある実施形態では、レベルiにおけるグラフにおいて粗視化するためにノードの対が選ばれ、両ノードを含むスーパーノードがレベルi＋1で構築される。これの例は、図８に見ることができる。この図では、レベル０のノードａおよびｂが結合されてレベル１のノードａｂを形成している。すべてのノードが次のレベルに投射されてしまうか、それ以上畳み込むべき有効な対がなくなるかするまでこれが反復される。そうなったとき、現在のレベルにおいて畳み込まれていないノードは単に次のレベルに新しいスーパーノードとして加えられる。このようにして、新しいレベルが完成され、所望される数のスーパーノード（スレッド）が得られるまで、アルゴリズムはこの新しいレベルについて繰り返される。
【００５２】
グラフを粗視化するとき、少なくとも一つの実施形態については、最高の優先度は、クリティカルパスに属する命令の融合に与えられる。タイ〔同順〕の場合には、優先度は、共通の祖先がより多数である命令に与えられる。共通の祖先の数が多いほど、接続性（connectivity）が強く、よってそれらを同じスレッド中に融合することがより適切であることが通例である。他方、スレッド間で作業負荷を適切に分配するために、（１）互いに依存しないノードどうしおよび（２）不良（delinquent）ロードおよびその消費者の融合には非常に低い優先度が与えられる。プロファイリングの間、L2キャッシュにおいて有意なミス率をもつロードは、不良であると考えられうる。
【００５３】
図９は、粗視化方法のある実施形態を示している。９２０では、マルチレベル・グラフが生成される。当該領域の諸命令はマルチレベル・グラフの第一レベルにあり、マルチレベル・グラフの現在レベルは０のような初期値に設定される。図８を見ると、これはマルチレベル・グラフにおけるL0となる。
【００５４】
９３０では、パーティション〔分割〕数が所望されるスレッド数よりも多いかどうかの判定がされる。たとえば、パーティション数が２よりも多いか（２つでなく３つのスレッドが生成されるか）？
そのパーティション数が得られたら、粗視化は完了である。しかしながら、パーティション数が所望されるより多い場合、９４０で行列が生成される。再び例として図８を見ると、レベル０におけるパーティションの数は９であり、よって次のレベル（L1）を生成するための行列が生成される必要がある。
【００５５】
ある実施形態では、行列の生成は三つのサブルーチンを含む。９７１では、行列Mは初期化され、その値は０に設定される。行列Mは、ノード間の関係をもって構築される。ここで、行列位置M[i,j]はノードiとjの間の関係比を記述し、M[i,j]＝M[j,i]である。そのような比は、0（最悪の比）から2（最善の比）までの間の範囲の値であり、その比が大きいほど、二つのノードはより関係している。すべて０に初期化されたのち、行列Mのセルは、一組のあらかじめ定義された基準に従って充填される。そのような基準の第一は、不良ロードの検出である。不良ロードは、しばしばキャッシュにおいてミスしそうなロード命令であり、よってパフォーマンスに影響する。ある実施形態では、ミス率が閾値（たとえば10%）より高い不良ロードが判別される。不良ロードをもつノードおよびその事前計算スライスの形成は、これらのロードを、それらの消費者とは切り離してモデル化する洗練（後述）を許容するために好まれる。したがって、不良ロードを消費者と接続するデータ・エッジは非常に低い優先度を与えられる。ある実施形態では、ノードの比は、後続のスラックおよび共通先祖評価に関わりなく、行列M中の0.1（非常に低い優先度）に固定される。したがって、不良ノードとして同定された行列M中のノードについては値0.1が与えられる。このことのある実施形態の擬似コード表現が図１０に表されている。
【００５６】
９７２では、PDGの各エッジのスラック（slack）が計算され、行列Mがしかるべく更新される。スラックとは、全実行時間に影響することなく命令がその実行を遅延させるためにもつ自由度である。そのようなスラックを計算するために、まず、各命令についての最も早い発送（dispatch）時間が計算される。この計算のためには、データ依存性だけが考慮される。さらに、異なる反復工程間の依存性は無視される。このあと、各命令の最も遅い発送時間が同様のまたは同じ仕方で計算される。各エッジのスラックは、消費者および生産者ノードのそれぞれ最も早い発送時間と最も遅い発送時間の間の差として定義される。このような仕方でスラックをもたないエッジ（制御エッジおよび反復工程間依存性）は、デフォルトのスラック値（たとえば100）をもつ。非常に低いスラックをもつエッジによって接続される二つのノードiおよびjはクリティカルパスの一部と考えられ、より高い優先度で畳み込まれる。クリティカル・エッジとは、スラック0をもつエッジであり、それらのノードの比M[I,j]およびM[j,i]は最善の比（たとえば2.0）に設定される。このことの擬似コード表現が図１０に表されている。
【００５７】
９７３において、行列Mの残りのノードが共通の先祖を見ることによって充填される。各ノード対(i,j)が共有する祖先命令の数は、エッジを後ろ向きにたどることによって計算される。これは、依存する命令を同じスレッドに割り当て、独立な命令を異なるスレッドに割り当てる助けになる。ある実施形態では、各対のノードの先祖関係は、それらの前任者（antecessor）の交わりとそれらの前任者の合併との間の比として計算される。次の式は、ノードiとjの間の比（R）を定義する。
【００５８】
【数１】
0005547208.tif 000002
関数P(i)およびP(j)は、ノードiまたはjを含む、先祖（predecessor）iまたはjの集合を表す。ある実施形態では、動的命令ストリームに対してより深い影響をもつ命令により重要性を与えるために、P(i)中の各先祖命令は、そのプロファイルされた実行頻度によって重み付けされる。
【００５９】
この比は、二つのノードがどのくらい関係しているかを、ある程度、記述する。二つのノードが、グラフを後ろ向きにたどるときに重要な量のノードを共有する場合、それは、両者が多くの計算を共有することを意味し、よってそれらを同じスレッドにマッピングすることに意味がある。それらは、行列Mにおいて大きな関係比をもつべきである。他方、二つのノードが共通の先祖をもたない場合、両者は独立であり、異なるスレッドにマッピングされるよき候補である。
【００６０】
再帰（recurrence）の存在のもとでは、多くのノードは比1.0をもつ（すべての先祖を共有する）。この問題を解決するために、比は二度計算される。一回は通例通りに、そして二回目は異なる反復工程（再帰）の間の依存性を無視してである。最終的な比は、これら二つの和である。これは、得られるスレッディングの品質を改善し、結果としてパフォーマンスを向上させる。最終的な比は、行列Mのセルの残りを充填するために使われる。このことの擬似コード表現が図１０に表されている。
【００６１】
三つの呈示される基準のどれもが、よいスレッドを生成するためにオン／オフされうることを注意しておく。
【００６２】
９４０で行列が充填されたとき、９５０で現在レベルがインクリメントされ、９６０でノードは畳み込まれる。この畳み込みは、諸対のノードを新しいスーパーノードに畳み込む。各ノード対について、該ノード対がある条件の集合を満たす場合、それらのノードは畳み込まれる。たとえば、ある実施形態において、所与のノードについて、畳み込みのための条件は、ノードiもjも前のレベルから現在レベルにかけて畳み込まれていないということである。もう一つの実施形態では、M[i,j]の値は、任意のkについてM[i,k]よりも高々5%小さいだけであり、任意の一つのノードについてM[l,j]より高々5%小さいだけであるべきである。換言すれば、有効な対は、高い比の値をもつ対であり、ノードは、その最良オプションよりも高々5%悪いだけの別のノードとだけパートナーを組むことができる。有効なパートナーをもたないノードは、次のレベルに投射され、一つのノードはレベル当たり一回しか畳み込まれることができない。
【００６３】
畳み込み後、逐次反復プロセスは、９３０で、パーティション数の決定に戻る。
【００６４】
行列の大きさが小さくなるにつれ、ノードは（もとのノードがある）レベル０からの二つ以上のノードを含みうるため、レベル０におけるすべての依存性は残りのレベルに投射される。たとえば、図８でレベル１にあるノードａｂは、レベル０におけるノードａおよびｂならびにノードｂおよびｃの間のすべての依存性によって、ノードｃｄに接続される。したがって、行列Ｍはすべてのレベルにおいて自然に充填される。
【００６５】
粗視化が完了すると、７０９においてマルチレベル・グラフが形成されたことになる。ある実施形態では、このマルチレベル・グラフは７１１において再評価され、洗練される。洗練（refinement）も、最上位レベルから最下位レベルまでマルチレベル・グラフの諸レベルを歩み、各レベルにおいて一つのノードを別のパーティションに動かすことによってよりよいパーティションを見出そうとする逐次反復プロセスである。動きの例として図８に見られるところでは、レベル２において、ノードｅｆｇがスレッド０にあるべきかスレッド１にあるべきかの判断がなされる。洗練は、粗視化の間に見出されたすでに「よい」パーティションを洗練することによって、よりよいパーティションを見出す。各洗練試行における調べられたパーティションは、分解された命令だけでなく、各スレッド内に、その制御独立な実行を許容するよう、すべての必要な分枝ならびに必要とされるすべての通信およびpスライスを含む。したがって、コンパイラがどのようにスレッド間依存性を管理するかを決定するのは、洗練プロセスの間である。
【００６６】
各レベルにおいて、パーティションを改善するためにカーニハン・リン（K-L:  Kernighan-Lin）アルゴリズムが使われる。K-Lアルゴリズムは次のようにはたらく：レベルlにおける各スーパーノードnについて、nを別のスレッドtidに移すことの利得F(n,tid)が、ある目的関数を使って計算される。スーパーノードをあるスレッドから別のスレッドに移すことは、そのスーパーノードに属すすべてのレベル０ノードを動かすことを含意する。そこで、最高のF(n,tid)をもつスーパーノードが選ばれ、移動される。これが、すべてのスーパーノードが移されるまで繰り返される。ノードは二回は動かせないことを注意しておく。また、たとえ新しい解が目的関数に基づいて直前の解よりも悪いとしても、すべてのノードが動かされることに注意しておく。これは、K-Lアルゴリズムが局所最適解を克服することを許容する。
【００６７】
ひとたびすべてのノードが移動されたら、そのレベルではラウンドは完了である。レベルがN個のノードを含む場合、あるラウンドの間にはN＋1個の解（パーティション）がある。ノード移動当たり一つと、初期のものである。これらの解のうちの最良のものが選ばれる。最良の解が初期のものと異なる（すなわち最良の解が少なくとも一つのノードを動かすことを含む）場合には、もう一つのラウンドが同じレベルで実行される。これは、現在レベルにおいてよりよい解がみつかったので、現在レベルにおける他の潜在的な動きが探索されるのである。上位レベルでの動きは下位レベルでのノードを引きずることを注意しておく。したがって、レベルlで解が見出されるとき、これはレベルl−1での出発点である。この方法論の利点は、少数のノードしかなくK-Lアルゴリズムの振る舞いのよい上位レベルで、よい解が見出されることができるということである。より下位のレベルでは、しばしばK-Lが何もないところから出発してよい解を見出すにはあまりに多くのノードがあるのだが、アルゴリズムがすでによい解から出発するので、下位のレベルでのタスクは、単に、細かい粒度の改善を与えることである。通常、利得の大半は上位レベルで達成される。よって、所望されるなら、アルゴリズムの計算時間を短縮するために低位レベルを横切ることを避けるために、ヒューリスティックが使用されてもよい。
【００６８】
こうして、所与のレベルにおいて、各ノードnを別のスレッドに動かすことの恩恵が、目的関数を使い、動きをフィルタリングし、スレッド間依存性を見ることによって作られる。ある実施形態では、前記目的関数をもってパーティションを評価する前に、動きフィルタリングおよびスレッド間依存性評価が実行される。
【００６９】
所与のレベルにおけるすべてのノードを動かそうとすることは、特にPDGに多くのノードがあるときはコスト高である。ノードはまず、スレッド間の作業負荷バランスを改善するという点でより大きな影響をもつおよび／またはスレッド間依存性を減らすノードにフィルタリングされてもよい。作業負荷バランスを改善するために、焦点は、作業負荷バランスを助けうる上位Kノードに置かれる。作業負荷バランスは、所与のスレッドに割り当てられる動的命令の最大の推定される数を、所与のスレッドに割り当てられる動的命令の総数によって推定される動的命令の総数によって割ることによって計算される。スレッド間の良好なバランスは0.5であってもよい。上位L個のノードは、スレッド間依存性の数を減らすために使われる。ある実施形態では、LおよびKは10である。
【００７０】
ある動きによって導出されるパーティションを評価する前に、スレッド間依存性について何をすべきかおよびいくつかの命令が複製されるべきかどうかについての決定がなされる。この決定は、制御フローの、可能性としての再構成を含む。これらは、明示的に通信されるまたは命令複製をもって事前計算されることができる。すべての必要とされる分岐命令がそれを必要とするスレッド内にあるよう、いくつかの制御命令がそれらのスレッドにおいて複製される必要がある。
【００７１】
特定のパーティションを評価する前に、アルゴリズムは、スレッド間依存性をどのように管理するかを決定する。これは：１）明示的なスレッド間通信を使って充足される（通信は明示的な送信／受信命令をもってまたは命令ヒントによってマークされることができ、スレッド間の同期を導入する（少なくとも受信者端において））；２）これらの依存性をローカルに満足させるために事前計算スライスを使うことによって充足される（事前計算スライスは、依存性をローカルに満足するために必要な最小限の命令からなり、これらの命令は、通信を回避するために、他のコアに複製されることができる）、および／または３）、非常にまれである場合に依存性がないと投機的に仮定して無視され、潜在的な違反が発生した場合にはハードウェアに検出させることができる。
【００７２】
依存性を通信することは、通信される値は、生産者がその対応するコアのROBの先頭に達するときに、共有されるL2キャッシュ（後述）を通って進むので、比較的高価である。他方、過剰な複製される命令は、投機的スレッドの実行を遅延させ、パフォーマンスにも影響することになりかねない。したがって、各スレッド間依存性についての最も好適な代替の選択が、パフォーマンスに対する影響をもちうる。
【００７３】
ある実施形態では、複製されるべき命令の重み付けされた量が特定の閾値を超えない場合に、依存性を事前計算する決定が肯定的になされる。それ以外の場合には、依存性は明示的な通信によって満足される。我々の実験では、値500が良好な閾値として見出されている。もっとも、他の環境および実施形態では他の値がより好適であることがありうる。
【００７４】
スレッド間依存性を与えられたとき、アルゴリズムは、ローカルに依存性を満足させるための推定される複製される動的命令の量が閾値を超える場合に、該スレッド間依存性を明示的に通信することを決定してもよい。それ以外の場合には、依存性のpスライスが構築され、宛先スレッドにおいて複製されてもよい。
【００７５】
各領域について有効な閾値を適切に定義するために、いくつかの代替的なパーティションが、複製閾値および外側ループの展開因子を変更するマルチレベル・グラフ・パーティショニング・アプローチによって生成される。次いで、最終的なコード生成のための最良の候補が、期待される高速化を考えることによって選択されうる。期待される高速化が最大の候補が選択される。タイの場合には、スレッドの間での命令のよりよい均衡を与える代替が選ばれる。
【００７６】
洗練の間、各パーティション（スレッディング解）は、評価され、他のパーティションと比べられる必要がある。目的関数は、マルチコア・プロセッサのタイル上で走るときのこのパーティションについての実行時間を推定する。ある実施形態では、パーティションの実行時間を推定するために、プロファイリングによって得られた当該領域の20000動的命令のストリームが使用される。この命令のシーケンスを使って、実行時間が、データ依存性、スレッド間の通信、発行幅（issues  width）リソースおよびターゲット・コアのROBのサイズを考慮に入れる単純なパフォーマンス・モデルに基づいて、最長のスレッドとして推定される。
【００７７】
洗練が完了すると、７１３において、コードの当該領域の最適化されたバージョンを表す複数のスレッドを与える。７１５では、それらのスレッドが生成されたのち、コンパイラがそれらのスレッドを実行するためのコードを生成する。この生成は、適切な点において派生（spawn）命令を挿入し、異なるスレッドに属する命令を論理アドレス空間の異なるエリアにおいてマッピングし、分岐オフセットをしかるべく調整することを含む。
【００７８】
〈分解された命令ストリームからのシーケンシャル実行の再構成〉
上で論じたように、もとの単一スレッドのアプリケーションはいくつかの投機的スレッドに分解され、各スレッドはもとのシーケンシャル・アプリケーションの作業全体の部分集合を実行する。生成されたスレッドはたいていの時間は並列に実行されうるが、プログラムの並列化は、投機的に生成されたものなので、時に正しくないことがありうる。したがって、これらのスレッドを実行するハードウェアは、これらの状況を識別し、そうした状況から回復できるべきである。そのようなハードウェア機構は、投機的状態を保持するためのバッファリング（たとえば、明示的なバッファ、追加的状態をもって拡張されたメモリ階層構造などを使う）および諸スレッドに割り当てられた諸命令のシーケンス順を決定する論理に依拠する。
【００７９】
投機的マルチスレッディング実行のシーケンス順を決定／再構成することは、スレッド（単数または複数）有効確認およびメモリ整合性のために必要とされる。プログラムの結果に影響するシーケンス順違反は、検出され、訂正されるべきである（スレッド有効確認（thread  validation））。たとえば、ロードは、正しい値を生成したストアが異なるコアにおいて実行されたために、古くなった値を読んでしまう。さらに、外部装置およびソフトウェアにとっては、投機的スレッドの実行は、あたかももとのアプリケーションがシーケンス順通りに実行されたかのように見えるべきである（メモリ整合性（memory  consistency））。こうして、メモリ更新は、もとの単一スレッドのアプリケーションが実行されたとした場合と同じ順序でネットワーク相互接続に対して見えるべきである。
【００８０】
ある実施形態では、投機的マルチスレッディングは、完全な一反復工程（または連続する複数の反復工程のかたまり）を各スレッドに割り当てることによって、複数のループ反復工程を並列に実行する。あるコアによって反復工程iにおいて実行される派生命令は、別のコアにおいて反復工程i＋1の実行を開始させる新しいスレッドを生成する。この場合、派生元（spawner）スレッドによって実行されるすべての命令は、被派生者（spawnee）によって実行される命令よりも古い。したがって、シーケンス順を再構成することはストレートであり、スレッドは、生成されたのと同じ順序で有効確認される。
【００８１】
細粒度の投機的マルチスレッディングを使う実施形態では、シーケンシャルなコードが命令の粒度でスレッドに分解され、いくつかの命令は二つ以上のスレッドに割り当てられてもよい（複製された命令と称される）。細粒度の投機的マルチスレッディングを使う実施形態では、明確のために二つのスレッドが二つのコアにおいて実行されると想定して、派生命令が実行され、派生元スレッドおよび被派生者スレッドが、両者の間のいかなる明示的な順序もなしに、それらの割り当てられた命令のフェッチおよび実行を始める。そのようなパラダイムの例が図３に示されている。ここでは、もとのシーケンシャルなCFGおよび可能な動的ストリームが左側に示されており、可能なスレッド分解が右側に示されている。二つの所与の命令の間の順序を知ることが自明ではないことを注意しておく。
【００８２】
本稿における諸実施形態は、細粒度の投機的スレッディングの想定のもとで、メモリ命令のシーケンス順を再構成することに焦点を当てる。しかしながら、ここで導入される記述は、メモリのほか、他のいかなるプロセッサ状態についてのシーケンス順の再構成に外挿されてもよい。並列実行においては、もとのシーケンス順を再構成できることが有用である理由は数多くあり、プロセッサ整合性をサポートする、デバッグするまたはプログラムを解析することが含まれる。そのような再構成をするコスト効率のよい機構は、次の特徴のうちの一つまたは複数を含んでいてもよい：１）単純なPOPマーク（これはほんの数ビットでもよい）の、静的命令の部分集合への割り当て（すべての命令が必ずしもマークされる必要はない；所望される順序を再構成することが重要な部分集合だけでよい）；および２）たとえ命令が非常に細かい粒度（個々の命令レベル）で複数のスレッドに分解されたとしても順序の再構成。
【００８３】
本稿で用いるところでは、「スレッド順（thread  order）」は、スレッドが自らの割り当てられた諸命令を見る順序であり、「プログラム順（program  order）」は、もとのシーケンシャルなストリームにおいてすべての命令がどのように見えるかの順序である。スレッド順は、各スレッドは自らの命令を順にフェッチおよびコミットするので、再構成されうる。よって、スレッド順序付けは、スレッドによってコミットされたすべての命令をFIFO待ち行列に入れることによって満たされうる（図１１に示す）。スレッド順において最も古い命令がFIFOの先頭にある命令であり、最も若い命令が末尾にある命令である。ここで、「順」「シーケンス順」および「プログラム順」の用語は交換可能に使われている。
【００８４】
細粒度マルチスレッディングでは、命令が少なくとも一つのスレッドに属さなければならないという制約はあるが、命令のスレッドへの任意の割り当てが可能である。削除される命令（ハードウェアまたはソフトウェア最適化によって削除される命令）がある場合における、本稿で論じられることの拡張はストレートである。再構成すべきプログラム順は、そのような削除される命令がないもとの順序だからである。
【００８５】
プログラム順の再構成は、図１１に示されるように、POPマークによって指定される順序でスレッド順序付けFIFO待ち行列を選択するスイッチをもつことによってもよい。本質的には、POPマークは、いつ、どのFIFOをスイッチが選択すべきかを示す。各FIFO待ち行列は、スレッド順にスレッドに割り当てられた諸順序付け命令を有する。POPマークによって調整されてスイッチをあるFIFO待ち行列から別のFIFO待ち行列に動かすことによって、メモリはプログラム順に更新される。所与の時点において、メモリは、対応するFIFO待ち行列の第一の順序付け命令（ordering  instruction）をもって更新される。次いで、その命令はその待ち行列からポップされ、そのPOP値が読まれて、スイッチが指定されたFIFO待ち行列に動かされる。
【００８６】
シーケンシャルなプログラム順における第一の順序付け命令が順序のどこに存在するかは、出発点を与えるために、既知であるべきである。POPポインタは、次の順序付け命令の特性を記述しうるものであり、第一の順序付け命令はいかなる先行順序付け命令ももたない。この開始マークは、少なくとも一つの実施形態については、レジスタ中にエンコードされる。あるいはまた、第一の順序付け命令は静的FIFO待ち行列に割り当てられる。当業者は、第一のマークを定義するための他の多くの実装が、記述される実施形態の範囲内であることを認識するであろう。
【００８７】
本稿に記載される機構の諸実施形態を使って、メモリはシーケンシャルなプログラム順において更新されうる。しかしながら、他の実施形態は、静的なプログラムにマークを追加することによって特定の順序が強制される、任意の並列パラダイムに簡単に拡張されうる。
【００８８】
さまざまな実施形態について、順序付け命令をマークするエンティティは、コンパイラ、動的バイナリ・オプティマイザ（DBO:  Dynamic  Binary  Optimizer）またはハードウェアでありうる。POPマークによって指定されるスレッドの論理的な識別子を、物理的なスレッド（OSスレッド、ハードウェア・スレッド、……）にマッピングするエンティティは、若干の実施例を挙げると、OSまたはハードウェアでありうる。マークがユーザー・レベルまたはOSレベルで定義される場合、命令コーディングの一部を通じて、あるいはユーザーに可視なハードウェア（メモリ、特定ユーザー可視バッファなど）において可視となるであろう。マークがハードウェアによって定義される場合、ハードウェアはプログラムの静的な制御フローの知識を有していることが想定される。こうして、ハードウェアにおいてマークを定義する少なくともいくつかの実施形態については、ハードウェアに制御フローを通知するためにソフトウェアを使うというハードウェア／ソフトウェア・ハイブリッド・アプローチが使用される。
【００８９】
制御フロー（たとえば基本ブロック）のないコードでは、ストア命令の順序を決定できる。スレッド１に割り当てられるプログラム順で次のストアSi+1よりも前の、スレッド０に割り当てられるストアSiは、1のPOPをもつことになる。これは、次の順序付け命令がスレッド１に割り当てられていることを意味する。これらのPOPは、いかなる種類のコード（ハンモック、ループ、……）の存在においても適正な順序をマークする。分岐命令は二つのPOPをもってマークされる。一つは、その分岐が行われる場合のプログラム順で次の順序付け命令を含むスレッドを示し、もう一つは、その分岐が行われない場合のものを示す。最後に、命令のスレッドへの割り当てに依存して、すべてのストアやすべての分岐がPOPによってマークされる必要はない。
【００９０】
典型的には、POPマークがあるFIFO待ち行列から別のFIFO待ち行列への変化を示すマークであれば、ストア命令の一部および分岐の一部だけがマークされる――ある順序付け命令に取り付けられたPOP値がなければ、それは次の順序付け命令は同じFIFO待ち行列に存在する（同じスレッドに割り当てられた）ことを意味する。しかしながら、命令の均一なマーキングを所望する一つまたは複数の実施形態については、すべての順序付け命令にマークすることができる。本稿に記載される例示的な実施形態については、すべての順序付け命令がマークされる必要はないと想定される。これは、この見本の実施形態がより複雑な論理を必要とするという意味で、すべての順序付け命令をマークする実施形態の上位集合である。
【００９１】
アーキテクチャ上の副作用をもたないよう「偽の（fake）」順序付け命令が設計されてもよいことを注意しておくべきである。あるいはまた、諸実施形態は、アーキテクチャ上の副作用をもつ「偽の」順序付け命令を用いることも、そうした副作用が制御下にある限り、可能である。たとえば、raxが対応する基本ブロックにおいてライブインではなく、それにおいて再定義されている場合、「and  rax,  rax」のような命令でありうる。
【００９２】
複数スレッドに割り当てられる命令は、上で論じたような「複製された命令」である。複製された命令の管理は、ストレートな仕方で扱いうる。同じ命令の個々のインスタンスの間の順序は、順序付け命令の残りに対する順序が維持される限り、重要ではない。よって、インスタンス間の任意の順序を選びうる。必要とされるPOPマークの量を最小にする順序が、もしこれが本当に問題なら、使用されてもよい。たとえば、命令Iがスレッド０、１、２に割り当てられる場合、三つのインスタンスの有効な順序はI0,I1,I2（ここで、数字はスレッド識別子を表す）またはI2,I0,I1または他の任意の順序である。以前および今後の順序付け命令に対してPOPポインタが正しければよい。
【００９３】
最適化された領域のコード生成の間に、プログラム順ポインタ（POP:  Program  Order  Pointer）が生成され、最適化されたコードに挿入される。細粒度の投機的マルチスレッディングでは、所望されるシーケンス順を再構成するために有用な命令の相対順序がマークされる。これらの命令は「順序付け命令（ordering  instruction）」である。本発明の諸実施形態はメモリを正しく更新するためにメモリ順序付けを再構成しようとするので、ストア命令および分岐は順序付け命令の例である。順序付け命令は、シーケンシャルなプログラム順において次の順序付け命令を含むスレッドIDをコードするNビットを用いてマーク付けされてもよい。（ここで、Mをスレッド数として、
【００９４】
【数２】
0005547208.tif 000003
である。）POPマークは、命令ヒントとして命令とともにエンコードされてもよいし、POPマークをどのように命令にマッピングするかがシステムにわかる限り、他の場所に存在してもよい。
【００９５】
図１２は、ある最適化された領域についてのPOPマークを決定するための方法のある実施形態を示している。１２０１で当該領域の命令がパースされる。この命令は、最適化された領域の最初のものであってもよいし、その命令の後に現れる何らかの命令であってもよい。
【００９６】
１２０３で、この命令が順序付け命令かどうかの判定がなされる。命令が順序付け命令でなければ、POPマークを受け取らず、これが最適化された領域の最後の命令かどうかの判定がなされる。いくつかの実施形態では、POPマークはすべての命令について生成される。命令が最後の命令でない場合、１２０９で、当該領域の次の命令がパースされる。
【００９７】
その命令が順序付け命令である場合、１２１１で、当該領域は、該順序付け命令とのシーケンス順において次の順序付け命令を求めてパースされる。１２１３で、その後続の順序付け命令が異なるスレッドに属するかどうかの判定がなされる。該後続の順序付け命令が異なるスレッドに属する場合、スレッド切り換えがなされることを示すPOPマークが１２１７において作成され、１２０５で、それがそのスレッドの最後の命令であったかどうかの判定がなされる。
【００９８】
後続の順序付け命令が別のスレッドに属するものでない場合、１２０３において見出されたこの前の順序付け命令が同じスレッドに属するとマークされる。いくつかの実施形態では、このマーク付けは「X」であり、他の実施形態ではPOPマークは前の順序付け命令と同じままである。
【００９９】
いくつかの実施形態では、いつ異なるPOP値を割り当てるかについてのあらかじめ設定された規則がある。たとえば、いくつかの実施形態では、スレッドTiに割り当てられたストア命令Siが与えられるとき、１）Siのあとに、間に何の分岐もなしにTiとは異なるスレッドTjに割り当てられたストアSjが存在する場合、Siは、POP値Tjをもってマーク付けされる；２）Siと次の分岐Bとの間に、Tiとは異なるスレッドTjに割り当てられる他のストアSがない場合、SiはPOP値Tjをもってマーク付けされる；３）それ以外の場合、ストアSiをマークする必要はない。
【０１００】
いくつかの実施形態では、スレッドTiに割り当てられた条件分岐命令Biが与えられるとき、１）分岐が行われるときの次の順序付け命令（分岐であってもストアであってもよい）がTiとは異なるTjに割り当てられる場合、Biは、その分岐成功（taken）POPマークにおいてPOP値Tjをもってマーク付けされる。それ以外の場合には、分岐成功POPマークをBiに割り当てる必要はない；２）分岐が行われないときの次の順序付け命令（分岐であってもストアであってもよい）がTiとは異なるTjに割り当てられる場合、Biは、そのフォールスルー（fallthru）POPマークにおいてPOP値Tjをもってマーク付けされる。それ以外の場合には、フォールスルーPOPマークをBiに割り当てる必要はない。
【０１０１】
いくつかの実施形態では、スレッドTiに割り当てられた無条件分岐命令Biが与えられるとき、条件分岐と同じアルゴリズムが適用されるが、分岐成功POP値の計算だけが行われる。
【０１０２】
いくつかの実施形態では、N通りの可能な経路P1…Pnをもつ間接分岐が、間に何の順序付け命令もなしであとに続くTiにおける順序付け命令が与えられるとき、次の順序付け命令はTiとは異なるスレッドTjに属するとして、経路PkはPOP値TjをもってTi内の「偽の」順序付け命令を実行することになる。偽の順序付け命令とは、単に、もっぱら順序付けの整合性を保つ目的のための命令である。アーキテクチャ上の副作用がない限り、個別的命令であっても、汎用オペコードであってもよい。
【０１０３】
図１３は、ハンモックをもつループを使う例を示している。この実施形態において、プログラム順は再構成されてもよく、順序付け命令はストアおよび分岐である。簡単のため、順序付け命令だけが示されているが、当業者は、他の命令が存在することを認識するであろう。図１３に示される順序付け命令は、それぞれスレッド０と１のどちらに割り当てられたかを示すことでマークされている。条件分岐は、二つのPOPマークをもち、一方、ストアおよび無条件分岐は一つしかもたない。POPマーク「X」は、このマークが必要とされないことを意味する。POPマーク「？」は、完全な制御フローが示されていないため、未知であることを意味する。右下部分には、ループが二回実行され、各反復工程がハンモックの異なる経路をたどるときにプログラム順がどのように再構成されるかが示されている。簡単のため、コードは二つのスレッドに分解されると想定した。ただし、本機構は、POPマークに十分なビットが与えられればではあるが、任意の数のスレッドとともに機能することが意図されている。なお、順序付け命令だけが描かれている。
【０１０４】
ストア命令S5は両方のスレッドに割り当てられており、二つのポップ・マークをもつ。他のすべてのストアは一つのPOPマークをもつ。無条件分岐も一つのPOPマークをもつ（分岐成功POPマークT）。条件分岐は二つのPOPマークをもつ：分岐成功（taken）のPOPマーク（T）と、分岐不成功（not  taken）のPOPマーク（NT）である。第一の命令、ストア（store）S1は、スレッド０に割り当てられ、シーケンス順で次の順序付け命令S2がスレッド１に割り当てられているので、POP値1をもつ。ストアS3は、シーケンス順で次の順序付け命令が同じスレッド０に割り当てられているので、POP値を必要としない（よって「X」）。このように、あるFIFO待ち行列から別のFIFO待ち行列への変化を示すマークをエンコードする必要はない。条件分岐B1は、分岐が行われるとき、次の順序付け命令は同じスレッド０に割り当てられているので、分岐成功POP値を必要としない。しかしながら、B1は、分岐が行われないときは次の順序付け命令S6は他方のスレッドに割り当てられているので、分岐不成功POP値は必要とする。この場合、マークは1である。もう一つの個別的な事例として、ストアS5は両方のスレッドに割り当てられている（複製されている）。この場合、その二つのインスタンスの間の順序は重要ではない。図において、スレッド０内のストアS4にはPOPポインタを割り当てず、スレッド０および１におけるS5インスタンスにはそれぞれPOPポインタ1および0を割り当てることによって、スレッド０におけるS5のインスタンスはスレッド１におけるインスタンスより先行する。しかしながら、これは逆でもよい。ただし、POP値は異なってくる。
【０１０５】
図１３の右下部は、プログラムは｛基本ブロックA,B,C,E,B,D,E,……｝からなる実行ストリームに従うと想定して、POPポインタを使うことによって順序付け命令どうしがどのように関係付けられるかを示している。本図のこの部分では、ボックスXの中心から出ていく線は「X内の命令の実行後」を意味し、ボックスXの先頭に到着する矢印付きの線は、「X内の命令の実行前」を意味する。このプログラム・フローは、二回、ループを通して実行することを含む。ここで、ループを通じた各反復工程はハンモックの異なる経路をたどる。よって、グローバルな順序は、S1,S2,S3,B1,S4,S50,S51,B2,S7,S8,B4,S2,B1,S6,…である。
【０１０６】
上記したのは、適正なシーケンシャルなプログラム順をもってメモリを更新するためにスレッドに任意に割り当てられたストア命令および分岐にマークする実施形態である。少なくとも一つの実施形態については、分解されたスレッドは命令レベルで構築され、諸コアの実行を結合させ、マルチコア設計における単一スレッド・パフォーマンスを改善する。コンパイル時に生成されたスレッドの実行をサポートするハードウェア機構の実施形態はのちに詳細に論じられる。これらのスレッドは、もとのアプリケーションの細粒度の投機的分解から帰結し、修正されたマルチコア・システムのもとで実行される。修正されたマルチコア・システムは：（１）スレッド間の違反を検出する機構；（２）もとのシーケンス順を再構成する機構；および（３）投機ミス（misspeculations）を扱うためのチェックポインティングおよび復元機構を含む。
【０１０７】
諸実施形態は、マルチコア・システムにおける単一スレッド・アプリケーションを、細かい粒度の仕方で分解することによって高速化する。コンパイラは、単一スレッドのアプリケーションまたは並列アプリケーションのシーケンシャルな領域からの命令を、投機的マルチスレッディングをサポートするマルチコア・システムにおいて並列に実行できるスレッドに分配する役割を担う。当業者は、これは、並列化されたコードが与えられるときに任意の種類の順序を再構成することにも拡張されうることを認識するであろう。いくつかの代替的な実施形態は、これに限られないが、１）制御フローを再構成する（順序付け命令は分岐だけ）；２）プログラム・フロー全体を再構成する（すべての命令が順序付け命令であり、割り当てられたPOPマークをもつべき）；３）メモリ・フローを再構成する（分岐、ロードおよびストアが順序付け命令である）；４）並列プログラムの諸命令の特定の順序を、該並列プログラムを有効確認、デバッグ、試験または調整するために、強制する（すでに並列化されたコードから出発し、命令間の特定の順序を強制するために、ユーザー／コンパイラ／解析ツールがPOPマークを命令に割り当て、各ポイントでプログラムのシーケンシャルなビューがどのように見えるかを見る）。
【０１０８】
POPマークを使ってフローを再構成する方法のある実施形態が図１４に示されている。上で詳述したように、プログラム・フローを再構成するために使われる順序付け命令はストアおよび分岐である。１４０１において、プログラムは複数のコアを使って投機的に実行される。この実行の間、各スレッドの命令は該命令が割り当てられたスレッドにおいてローカルにリタイアさせられ、ICMCを介してMLCによってグローバルにリタイアさせられる。
【０１０９】
１４０３では、フロー（プログラム、制御、メモリなど）が復元または再構成されることを要求する条件が見出される。たとえば、最適化された領域を実行するコアどうしの間で不整合なメモリ値が見出されている。もちろん、フローは、実行の間に見出される条件ではない微調整など他の理由でも再構成されることができる。
【０１１０】
１４０５では、最初の（最も古い）順序付け命令が下の適切なFIFO（これらのFIFOはmemFIFOまたはメモリFIFO待ち行列と呼ばれる）から取得され、プログラムが実行されるにつれて中身を入れられる。この命令の位置は、上記した方法の一つによって示される。先に論じたハンモックをもつループを例として使うと、第一の命令はストアs1であり、スレッド０に属する。命令がリタイアさせられる際、そのPOP値（単数または複数）を含む命令が、フローを再構成する機構によって識別可能な適切なFIFOまたは別の場所に記憶される。
【０１１１】
１４０７では、その命令のPOP値が読まれる。ここでもまた、図４を見て、ストアs1命令のためのPOPマーク値は「1」である。
【０１１２】
１４０９では、これが最後の順序付け命令であるか否かの判定がなされる。もしそうであれば、フローは決定されたことになる。もしそうでなければ、１４１１で、FIFOを切り換えるべきか否かの判定がなされる。POP値が前に取得された命令のスレッドと異なる場合には切り換えが行われる。前の例において、読まれた値「1」は、次のプログラム・フロー命令が、スレッド０に属していたストアs1命令とは異なるスレッド１に属することを示す。その値がXであったなら、それは次のプログラム・フロー命令が同じスレッドに属し、FIFO切り換えがないことを示す。前の例では、このようなことは、ストアs3分岐が取得された後に起こる。
【０１１３】
切り換えがなされるべきである場合、POP値によって示されるFIFOが選択され、１４１３において、そのFIFO内の最も古い命令がそのPOP値とともに読まれる。切り換えがなされるべきでない場合、FIFOは切り換えられず、１４１５において、次に最も古い命令がFIFOから読まれる。命令を読み込んで、読み込まれたPOP値に基づいてFIFOを切り換えるプロセスは、プログラム・フローが再生成され終わるまで、あるいはFIFOが使い果たされるまで続く。ある実施形態では、FIFOは、使い果たされた場合、別の記憶場所（メイン・メモリのような）から補充される。ある実施形態では、プログラムの実行は、プログラムの実行をどこで再開するかを決定するために前記フローを使うことによって続く。
【０１１４】
ある実施形態では、後述するICMCが上記の方法を実行する。もう一つの実施形態では、ソフトウェア・ルーチンが上記の方法を実行する。
【０１１５】
〈マルチコア投機的マルチスレッディング・プロセッサおよびシステムの諸実施形態〉
図１５は、スレッド順序付け再構成機構の諸実施形態を用いることのできるマルチコア・システムのある実施形態を示すブロック図である。参照の簡便のため簡略化された図１５のシステムは、追加的な要素を有していてもよいが、そのような要素は図１５には明示的に示されてはいない。
【０１１６】
上で論じたように、細粒度のSpMTエコシステムでは、プログラムは一つまたは複数の処理コア上で実行されるべき一つまたは複数のスレッドに分割される。これらの処理コアはそれぞれスレッドを処理し、この処理の結果は、プログラムが単一コア上で単一スレッドとして実行された場合と同じ結果を生成するよう（ただし分割および／または並列実行のほうが高速であるべきである）、マージされる。異なるコアによるそのような処理の間、実行の状態は投機的である。スレッドがその最後の命令に到達するとき、スレッドは最適化された領域の出口に同期し、投機的状態は非投機的になり、実行は一つの単一スレッドをもって続き、タイルはそのプログラムについての単一コア・モードに戻る。本稿で用いるところの「タイル」については、図１５との関連で下記においてさらに詳述する。一般に、タイルは、普通ならシーケンシャルな諸命令のセットの異なる諸部分を同時並行して実行するようはたらく二つ以上のコアの群である（ここで、「異なる」諸部分とはいっても複製された命令を含んでいてもよい）。
【０１１７】
図１５は、二つのタイル１５３０、１５４０に論理的に分割されているマルチコア・システムを示している。少なくとも一つの実施形態については、本システムの処理コア１５２０はx86アーキテクチャに基づくが、処理コア１５２０はパワーPCなどといったいかなるアーキテクチャのものであってもよい。少なくとも一つの実施形態について、本システムの処理コア１５２０は順序外に（out-of-order）命令を実行するが、そのような実施形態は限定するものと解釈すべきではない。本稿で論じられる機構は、命令を順序通りに（in-order）実行するコアにも等しく適用可能でありうる。少なくとも一つの実施形態について、タイル１５３０、１５４０の一つまたは複数は、専用の（private）第一レベルのライトスルー・データ・キャッシュ（「DCU」）および命令キャッシュ（「IC」）をもって二つのコア１５２０を実装する。これらのキャッシュICおよびDCUは、分割されたトランザクション・バス１５６０を通じて共有されるコピーバックL2  １５５０キャッシュに結合されていてもよい。最後に、L2キャッシュ１５５０は別の相互接続ネットワーク１５７０を通じてメイン・メモリ１５８０およびタイル１５３０、１５４０の残りの部分に結合される。
【０１１８】
L2キャッシュ１５５０はMLC（「Merging  Level  Cache［マージング・レベル・キャッシュ］」）と呼ばれ、タイルの諸コアの間で共有されるキャッシュである。図１５に示される実施形態については、共有されるキャッシュの第一レベルは第二レベル・キャッシュである。処理コア（スレッド）の間のマージングが実行されるのは、このマージング・レベル・キャッシュにおいてである。しかしながら、他の実施形態では、L2キャッシュは必ずしもタイルのコア間のマージング・レベル・キャッシュでなくてもよい。他の実施形態については、MLCはメモリ階層構造の任意のレベルにおける共有されるキャッシュであってもよい。
【０１１９】
少なくとも一つの実施形態については、図１５に示されるタイル１５３０、１５４０は二つの異なる動作モードをもつ：単一コア（通常）モードおよび協働モードである。タイル内の諸処理コア１５２０は、タイルが単一コア・モードにあるときは通常のスレッドを実行し、タイルが協働モードにあるときは同じ分解されたアプリケーションからの投機的スレッド（各コアにおいて一つのスレッド）を実行する。
【０１２０】
最適化されたコードの実行は、スレッドを有するタイルについて協働モードで実行されるべきであることを注意しておくべきである。したがって、これら二つのスレッドが最適化されたコードの実行を開始し、派生命令がトリガーするとき、それらのコアは単一コア・モードから協働コア・モードに遷移する。
【０１２１】
協働モードがアクティブ化されて二つの投機的スレッドがタイル（たとえば１５３０または１５４０）上で走っているとき、明示的な通信によってスレッド間依存性が満足させられる必要があるときに、両者の間の同期が行われる。しかしながら、通信は、消費者側だけでの同期を含意してもよい。通常のメモリまたは専用の論理がこれらの通信のために使用されてもよい。
【０１２２】
通常実行モードまたは通常モード（または単一モード）は、処理コアが非投機的マルチスレッディング・コードを実行していて、その間、タイル内の他の処理コアがアイドルであるか別のアプリケーションを実行しているときである。たとえば、タイル１５３０の処理コア０は非投機的マルチスレッディング・コードを実行しており、コア１はアイドルである。投機的実行モードまたは投機的モードは、両方のコアが協働して投機的マルチスレッディング・コードを実行しているときをいう。通常および投機的モードにおいて、各コアは、独立して命令をフェッチし、実行し、リタイアさせる。投機的モードでは、チェックポイント（後述）が規則的な間隔で取られ、メモリ違反が見出された場合には前の整合的な状態へのロールバックがなされることができる。
【０１２３】
処理コアは、ひとたび一方のコアが派生命令をリタイアさせると、通常モードから投機的モードに遷移する（他方のコアがアイドルであるとしている。そうでなければ、実行は通常モードで再開される）。他方、処理コアは、ひとたびアプリケーションがスレッドに分解されていないコード領域にジャンプするか、メモリ違反が検出されるかすると、投機的モードから通常モードに遷移する。メモリ違反は、一つのコアにおいて実行しているロードが別のコアにおいて実行されるストアによって生成されるデータを必要とするときに起こる。これは、システムが、異なるスレッドに割り当てられた命令の実行の間の順序を保証できないために起こる。メモリ違反の存在のもとでは、ICMCによって生成される破棄信号がすべてのコアおよびキャッシュに伝搬させられ、状態は前の整合的な状態にロールバックされ、実行は通常モードで再開される。
【０１２４】
アーキテクチャ上のメモリ状態を更新し、もとのシーケンシャルなプログラム順における潜在的なメモリ違反がないかどうかチェックするために、もとのプログラム順の再構成がなされる。ある実施形態では、これは、各処理コアのローカルにリタイアさせられたメモリ命令すべてをのちにさらに詳述する対応するFIFO構造に入れ、何らかの命令マークによってもとのシーケンシャルなプログラム順においてこれらの待ち行列内の先頭の命令にアクセスし、これを除去することによってなされる。命令がある処理コアにおいてリタイアするとき、これは、該命令がその処理コアにおいて最も古い命令であり、その対応するFIFOの末尾に置かれることを意味する（ローカルなリタイアと称される）。メモリ階層構造は、システムにおける最も古い命令（いずれかのFIFOの先頭にある）を連続的に取得し、MLCおよびその関連付けられたビットに、シーケンシャルなプログラム順にアクセスする（命令のグローバルなリタイアと称される）。
【０１２５】
図１６は、協働モードで動作するタイルの例を示している。この図では、命令３および４はそれぞれコア１および０においてローカルにリタイアさせられている。ICMCはプログラム順においてグローバルにコミットされた命令０、１および２を有し、しかるべくMLCを更新する。ICMCはメモリ違反がないかどうかのチェックもする。
【０１２６】
コア間メモリ整合性モジュール（ICMC）モジュールは分解されたスレッドをサポートし、次のうちの一つまたは複数を制御しうる：１）メモリ動作をソートし、分解されたアプリケーションによってなされる変化を、それがシーケンシャルに実行されたかのように他のタイルに見えるようにする；２）タイルの諸コア上で走っている諸スレッドの間のメモリ依存性違反を識別する；３）メモリおよびレジスタ・チェックポイントを管理する；および／または４）予測ミス、例外または割り込みの場合にコア内のロールバック機構をトリガーする。
【０１２７】
少なくとも一つの実施形態については、ICMCは処理コアにほとんど干渉しない。よって、協働モードを処理する際、コアは、ほとんどの時間、分離された仕方で投機的スレッドからの命令をフェッチし、実行し、リタイアさせる。次いで、命令の部分集合が、リタイアした後、実行の有効確認を行うためにICMCに送られる。少なくとも一つの実施形態については、ICMCによって考えられる命令のセットは、メモリおよび制御命令に限定される。
【０１２８】
協働モードで実行するとき、ICMCは、メモリ違反を検出して正しくメモリを更新するために、投機的スレッドに任意に割り当てられたメモリ命令のもとのシーケンス順を再構成する。そのような順序は、プログラム順ポインタ（POP）ビットと呼ばれるマークを使ってICMCによって再構成される。POPビットは、コンパイラによって、メモリ命令およびある種の無条件分岐内に含められる。
【０１２９】
〈投機的マルチスレッディングのための例示的なメモリ階層構造〉
図１７は、本発明の少なくとも一つの実施形態に基づく投機的マルチスレッディングをサポートする例示的なメモリ階層構造を示すブロック図である。通常の動作モード（非投機的）では、メモリ階層構造は通常の階層構造として作用する。すなわち、伝統的なメモリ階層構造プロトコル（MESIまたは他の任意のもの）が必要に応じてキャッシュ・ラインを伝搬させ、無効化する。
【０１３０】
図１７の階層構造は、一つまたは複数の処理コア（処理コア１７０１および１７０３）を含む。階層構造の各処理コアは、図で「L1」と記されている、専用の第一レベル・データ・キャッシュ・ユニット（DCU:  data  cache  unit）１７０５を有する。これらの処理コアはまた、少なくとも一つのより上位レベルのキャッシュを共有する。図示した実施形態では、処理コア１７０１および１７０３は、第二レベルのデータ・キャッシュ１７０９および最終レベル・キャッシュ（last-level  cache）「L3」  １７１１を共有する。階層構造はまた、メイン・メモリのようなメモリ１７１３およびハードディスク、光学式ドライブなどといった他の記憶装置をも含んでいる。さらに、階層構造は、コアが協働モードで実行するときにタイル内部のコアの活動を制御することを担う、コア間メモリ整合性モジュール（ICMC）１７１５と呼ばれるコンポーネントを含んでいる。このモジュールは回路、ソフトウェアまたはそれらの組み合わせであってもよい。メモリ階層構造のこれらの例示的なコンポーネントのそれぞれについては、のちに詳細に論じる。
【０１３１】
〈データ・キャッシュ・ユニット（DCU）〉
通常モードで動作するとき、DCUはライトスルーであり、通常のL1データ・キャッシュとして動作する。投機的モードでは、DCUはライトスルーでもライトバックでもなく、置換の起こったダーティーなラインは破棄される。さらに、修正された値は伝搬させられない。通常モードからのこれらの変化は、バージョン生成（versioning）を許容する。というのも、のちに論じるように、マージおよび最終的に正しい値がマージング・レベル・キャッシュ（「MLC」）内に存在するからである。
【０１３２】
ある実施形態では、DCUは、ライン毎にバージョン生成ビット（versioned  bit）（「V」）を含めることによって拡張される。このビットは、投機モードにおいて、およびモード間を遷移するときにのみ使われる。このビットは、現在の投機的マルチスレッディング・コード領域を実行する間に更新されたラインを同定する。実装に依存して、投機的モードでは、ラインが修正されるとき、その変化を示すために、そのバージョン生成ビットは1に設定される。もちろん、他の実装では、同じことを示すのにバージョン生成ビット値0を使い、値1を変化なしに使うこともできる。
【０１３３】
通常モードから投機的モードに遷移するとき、Vビットは、変化なしを示す値にリセットされる。投機的モードから通常モードに遷移するとき、変更されたラインを示すよう設定されたバージョン生成ビットをもつすべてのラインは、無効に修正され、バージョン生成ビットはリセットされる。そのような遷移は、当該領域の終わりをマークする命令がグローバルにリタイアするとき、あるいはICMCによって破棄信号が出されるときに起こる（破棄信号については後述）。
【０１３４】
投機的モードでは、各DCUは独立して機能し、よって各DCUは各データ片の潜在的なバージョンをもつ。したがって、修正された値はキャッシュのより上位レベルに伝搬されない。MLCは、異なるDCUキャッシュ・ライン値の間でマージングが実行されるレベルであり、マージングは、これまでの節で説明したように、もとのシーケンシャルなプログラム・セマンティクスに従って行われる。投機的モードから通常モードへ遷移するとき、有効なラインだけがMLCに存在する。よって、投機的なラインはDCUにおいてクリアされる。ストア・オペレーションは、それらがグローバルにコミットするときにもとの順序でLCキャッシュを更新することを担うICMCに送られる。
【０１３５】
〈マージング・レベル・キャッシュ〉
ある実施形態では、L2キャッシュ１７０９は、処理コアの間の共有されるキャッシュであるMLCとしてはたらく。しかしながら、他の実施形態については、L2キャッシュは必ずしも処理コア間のマージング・レベル・キャッシュである必要はない。他の実施形態については、MLCはメモリ階層構造の別のレベルにおける共有されるキャッシュである。
【０１３６】
図のように、MLCは、キャッシュ・ライン毎に投機的（speculative）（「S」）ビットと、チャンク毎に二つの最終バージョン（last-version）（「LV」）ビットとを含めることによって、典型的なキャッシュから拡張される（もちろん、より多くの処理コアについてはより多くのLVビットがあるであろう）。チャンクは、二つの投機的スレッドの間のメモリ曖昧さ解決（memory  disambiguation）が（よって、メモリ違反が）検出される粒度である。それは、１バイトからライン・サイズまでの間の範囲であることができ、精度と領域との間のトレードオフである。
【０１３７】
Sビットは、キャッシュ・ラインが投機的状態を含むことを示す。これは、のちに論じるように、チェックポイントが実行され、メモリが再び安全であるときにクリアされる。他方、LVビットは、どのコアが各チャンクに対する最後の変更を実行したかを示す。たとえば、ある実施形態では、ラインの第一のチャンクについての「01」のLV値は、コア１が、そのチャンクに対して変更を行った最後のコアであったことを示す。これらのビットは、ストア命令がグローバルにリタイアする際に設定され、通常モードに戻る遷移があるまでクリアされない（チェックポイントとチェックポイントの間でクリアされるSビットと違って）。グローバルなリタイアは、もとのプログラム順で行われる。さらに、ストアは、複製されるか否かを同定するためにタグ付けされる。これは、システムがメモリ違反を捕捉できることを保証する助けになる。すべてのラインについてのLVビットは、デフォルトでは、どのコアからの読みも正しいことを示すよう設定される。
【０１３８】
最適化されたモードでストアがグローバルにリタイアさせられるときに行われる諸行動の方法のある実施形態が図１８に示されている。１８０１では、ストアがMLCをミスした（すなわち、L2キャッシュミスであった）かどうかの判定がなされる。ストアがミスであった場合、１８０３において、グローバル・リタイアは、そのラインがMLCに存在するようになるまで停止される。ストアがMLC内に存在していた場合（あるいはそのラインがMLCに到着するとき）、１８０５において、そのラインがダーティーであったかどうかの判定がなされる。非投機的データでダーティーである（たとえばSビットがセットされていない）場合には、１８０７において、そのラインはメモリ階層構造における次のレベルにライトバックされる（written  back）。それに関わりなく、１８０９で、そのデータは修正され、Sビットは1に設定される。
【０１３９】
１８１１においてストアが複製されているかどうかの判定がなされる。ストアが複製されているのでない場合、１８１３において、各修正されたチャンクに対応するLVビットは、そのストアを実行しているコアについては1に、他のコアについては0に設定される。ストアが複製されている場合には、１８１５において別の判定がなされる。この判定は、ストアが最初のコピーであったかどうかである。ストアが複製されており、それが最初のコピーである場合、１８１３において、各修正されたチャンクに対応するLVビットは、そのストアを実行しているコアについては1に、他のコアについては0に設定される。ストアが複製されており、最初のコピーでない場合には、１８１７において、そのストアを実行しているコアについては1に設定され、それ以外はそのままにされる。
【０１４０】
最適化されたモードでロードがグローバルにリタイアさせられようとするときに行われる諸行動の方法のある実施形態が図１９に示されている。１９０１では、ロードがMLCをミスしたかどうかの判定がなされる。ロードがミスであった場合、１９０３において、充填要求がメモリ構想構造における次のレベルに送られ、ロードは正しくグローバルにリタイアさせられる。
【０１４１】
ヒットであった場合には、１９０５において、対応するチャンクのLVビットのいずれかが0であるかどうかの判定がなされる。そのようなLVビットのいずれかが対応するコアについて値0をもつ場合、それは、その特定のコアがデータの最終バージョンを生成したのではないことを意味する。よって、１９０７において、破棄信号が生成され、状態はロールバックされ、システムは投機的モードから通常モードに遷移する。それ以外の場合には、１９０９において、ロードは正しくグローバルにリタイアさせられる。
【０１４２】
さらに、いくつかの実施形態では、他のイベントがあるときのMLCの振る舞いは次のとおりである：１）現在のチェックポイントが満足いくように終了したとき（チェックポイントの最後の命令が正しくグローバルにリタイアするとき）、すべてのラインの投機的（S）ビットは0に設定される。LVビットは、実行が投機的モードから通常モードに遷移するまでクリアされないことを注意しておく。２）SビットがセットされたラインがMLCから置換されるとき、破棄信号が生成される。これは、現在のキャッシュ構成が、最後のチェックポイント以降の投機的メモリ状態全体を保持できないことを意味する。チェックポイントは規則的に取られているので、我々のシミュレーションから観察されるように、これが起こるのはまれである。しかしながら、これが問題であれば、破棄の量を減らすために、洗練された置換アルゴリズム（replacement  algorithm）（投機的ラインが低優先度を与えられる）または犠牲者キャッシュ（victim  cache）を使ってもよい。３）投機的モードから通常モードに遷移するとき、すべてのSビットをクリアすることに加えて、LVビットもクリアされる（1に設定される）。４）破棄信号が出されるとき、投機的ビットが1に設定されているすべてのラインが無効に設定され（同じことはすべてのDCUにおいて起こる）、Sビットはリセットされる。また、LVビットはクリアされる（1に設定される）。
【０１４３】
〈コア間メモリ整合性モジュール（ICMC）〉
通常のキャッシュ・レベルに加えて、のちにさらに詳しく論じる他の構造がある。これらの追加的な構造は、コア間メモリ整合性モジュール（「ICMC」）を構成する。ICMCと、DCUおよびMLCのラインに付加されたビットとは、通常モードでは使用されない。ICMCは、順序付け命令を受け取り、それらを三つの構造を通じて扱う：１）メモリFIFO；２）更新記述テーブル（UDT:  update  description  table）；および３）レジスタ・チェックポインティング論理である（図２０参照）。ICMCは、マルチスレッド・アプリケーションによってなされた変更を、あたかもシーケンシャルに実行されたかのように他のタイルに見えるようにし、タイルの諸コア上で走る諸スレッド間のメモリ依存性違反を検出するために、順序付け命令をソートする。ICMCおよびタイル内部のメモリ階層構造は、協働モードで走っている各コアが、もとのシーケンシャルな実行が生成するであろうのと同じ状態をコミットしつつ、自分のメモリ状態を更新することを許容する。それは、複数のL1キャッシュにおいて同じラインの異なるバージョンを許容し、投機的な更新がタイル外部に伝搬するのを避けることによる。さらに、レジスタ・チェックポイントは、投機ミスを訂正するために前の状態にロールバックすることを許容する。
【０１４４】
ICMCは、メモリFIFO（memFIFO）と呼ばれる、コア当たり一つのFIFO待ち行列を実装する。コアが順序付け命令をリタイアさせるとき、その命令はそのコアに付随するmemFIFOに記憶される。ICMCはPOPビットに基づいてmemFIFOからのそれらの命令を処理し、除去する。最後のコミットされた命令のPビットの値は、memFIFOの先頭を同定し、そこに、コミットすべき次の命令が存在する。命令がICMCによってコミットされるのは、もとのシーケンス順においてシステム中で最も古い命令になったときであることを注意しておく。したがって、これはストア命令が共有されるキャッシュ・レベルを更新し、タイル外部に可視になってもよい順序である。下記の議論の間じゅう、命令がリタイアするのは、コア中で最も古い命令になり、リタイアが起こったときである。これに対し、命令がグローバルにコミットする、あるいは略してコミットするのは、その命令がタイル内で最も古いためにICMCによって処理されるときである。
【０１４５】
memFIFOは：１）命令の型（ロード、ストア、分岐、チェックポイント）を同定する型ビット；２）POP値；３）メモリ・アドレス；４）メモリ・アドレスのサイズを記述する諸ビット；５）ストア値のための諸ビット；および６）複製された（replicated）（rep）命令をマークするためのビットを含んでいてもよい。複製された命令がマークされるのは、ICMCに依存性違反をチェックさせるのを回避するためである。
【０１４６】
memFIFOは、各コアが、独立して命令をフェッチし、実行し、リタイアさせることを許容する。同期は、コアが他方のコアが命令をリタイアさせるのを妨げるときに起こるだけである。コアは最終的にはそのmemFIFOを充填させ、そのリタイアさせられた命令の一つまたは複数がmemFIFOを出るまで停止してもよい。これが起こるのは、コミットすべき次の命令が異なるコアによって実行される必要があり、この命令がまだリタイアしていないときである。
【０１４７】
タイル内のキャッシュ整合性プロトコルおよびキャッシュ・モジュールは、複数の第一キャッシュ・レベルにおける同じラインの異なるバージョンを許容するためにわずかに修正される。さらに、投機的な更新がタイル外で伝搬するのを避けるためにも、何らかの変更が必要とされる。L1データ・キャッシュは、ラインが更新されるときに、協働モードにおいて他のL1キャッシュを無効化せず、よって、各L1キャッシュは同じデータの異なるバージョンをもつことがありうるのである。上で論じたように、あるコアにおけるラインのVビットは、ストア命令がそのコアにおいて実行し、{ref}と同様のそのラインを更新するときに設定される。L1に対するそのような投機的更新は、共有されるL2キャッシュに伝搬（ライトスルー）させられない。ストア・オペレーションはICMCに送られ、コミットするときにL2キャッシュを更新することになる。よって、VビットがセットされたラインがL1から置換されるとき、その内容は破棄される。最後に、コアが協働モードから単一コア・モードに遷移するとき、VビットがセットされたすべてのL1ラインは無効化される。正しいデータはL2およびICMCに存在するからである。
【０１４８】
ストアがコミットするとき、対応するL2ラインを更新し、そのSビットを1に設定する。そのようなSビットは、ラインが最後のチェックポイント以降に修正されていることを記述する。ひとたび新しいチェックポイントが取られると、Sビットはクリアされる。投機ミスの場合、スレッドはロールバックされ、Sビットがセットされているラインは無効化される。よって、非投機的なダーティーなラインが投機的なストアによって更新されるとき、そのラインの有効な非投機的バージョンをメモリ階層構造中のどこかにもつためには、そのラインは次のメモリ・レベルにライトバックされなければならない。投機的状態はL2キャッシュを越えては進めないので、投機的（S）とマークされたラインのL2からの放逐は、前のチェックポイントにロールバックしてもとのアプリケーションの実行を再開することを含意する。
【０１４９】
他方、LVビットは、特定のチャンクの最後のバージョンをどのコアがもつかを示す。ストアがコミットするとき、そのコアに属する修正されたチャンクのLVビットを1に設定し、残りをリセットする。ストアが複製（両方のコアによって実行される）とタグ付けされている場合には、両方のコアが最新のコピーをもつことになる。この場合、LVビットは11に設定される。ロードのグローバル・コミットに際しては、これらのビットは、そのロードを実行したコアがデータの最後のバージョンをもつコアであったかどうかを見るためにチェックされる。そのロードを実行したコアを表すLVビットが0であり、他方のコアについてのビットは1であれば、違反が検出され、それらのスレッドは破棄される。これは、各コアが独立して命令をフェッチし、実行し、リタイアさせ、諸L1キャッシュも互いから分離して機能するため、ロードが正しい値を読むことをシステムが保証できるのはこれが同じコアにおいて生成された場合だけであるからである。
【０１５０】
UDTは、memFIFO待ち行列内に位置されるストア命令（まだグローバルにリタイアさせられていないストア）によって更新されるべきL2ラインを記述するテーブルである。少なくとも一つの実施形態については、UDTはキャッシュ（たとえばフルアソシアティブ、32エントリー）として構成される。ここで、各エントリーはラインを同定し、スレッド当たり次のフィールドをもつ：有効ビット（valid  bit）（V）およびFIFOエントリーid。FIFOエントリーidはそのスレッドのFIFOエントリーへのポインタである。UDTは、共有されるL2キャッシュからL1キャッシュへの充填を、そのラインを更新するためのペンディングのストアがまだある限りは遅延させる。これは、L2からの古くなったラインをもってL1を充填することを避ける助けになる。具体的には、所与のコアのL1への充填は、その特定のコアについての諸memFIFOにペンディングのストアがなくなる（そのライン・タグについてUDT中にエントリーがない）まで遅らされる。よって、要求されるラインについてUDT中にエントリーが存在し、そのコアに対応する有効ビットが1に設定されているならば、DCU充填は遅延要求バッファに置かれる。ひとたびその有効なビットが非セットにされたら、そのような充填は処理される。他のコアによるその同じラインへのストアを待つ必要はない。というのも、メモリ依存性があるとしたら、LVビットが常にそれを検出し、二つのコアが同じラインの異なる部分にアクセスする場合にはICMCがL2における更新を適正にマージするからである。
【０１５１】
投機的モードでは、ストアがローカルにリタイアさせられ、FIFO待ち行列に加えられるとき、UDTが更新される。ここで、エントリーが利用可能であるとする。エントリーがそのラインについて存在しなければ、新しいエントリーが生成され、タグが充填され、そのスレッドの有効ビットがセットされ、対応するFIFOエントリーidが、ストアが置かれているFIFOエントリーのIDで更新され、他方のコアに対応する有効ビットが非セットにされる。そのラインについてすでにエントリーが存在していれば、そのスレッドの有効ビットはセットされ、対応するFIFOエントリーidは、ストアが置かれているFIFOエントリーのidで更新される。
【０１５２】
ストアがグローバルにリタイアさせられるとき、ストアはUDTにおいてその対応するエントリーを見出す（これは常にヒットである）。そのコアのFIFOエントリーidがリタイアさせられるストアのUDTにおけるidと一致すれば、対応する有効ビットは0に設定される。エントリーの両方の有効ビットが0であれば、UDTエントリーは解放され、その後やってくる要求のために再利用されてもよい。投機的から通常モードに遷移するとき、UDTはクリアされる。
【０１５３】
オーバーフローを避けるために、UDT「ストップ・アンド・ゴー（Stop  and  Go）」機構が実装される。UDT中の利用可能なエントリーの数が少なく、オーバーフローのリスクがあるとき、コアが新しいストアをローカルにリタイアさせるのを防ぐためにコアに信号が送られる。クレジット・ベースの制御は実装できないことを注意しておく。というのも、UDTはいくつかのコアから書かれることのできる共有される構造だからである。さらに、デッドロックを避け、進行を保証するために、コアはN−1個より多くのUDTエントリーを使うことはできない。ここで、Nはエントリーの総数である。そのような場合、そのコアは新しいストアをローカルにリタイアさせることを妨げられる。これは、他方のスレッドがシステム中の最も古い命令を実行しているスレッドである場合、該他方のスレッドが進行する余地を残す。
【０１５４】
UDT中のエントリーは次のフィールドをもつ：L2キャッシュ・ラインを同定するタグ、それに加えて各コアについてのmemFIFOエントリーidに取り付けられている有効ビット。memFIFOエントリーidは、そのラインを更新する最後のストアのその特定のmemFIFOのエントリー番号である。ストアがUDT中にエントリーのないラインを書く場合、新しいエントリーを割り当てる。これに対し、コミットされたストアがmemFIFOエントリーIDによってポイントされる場合、その有効ビットは偽に設定され、両方の有効ビットが偽である場合、エントリーはUDTから除去される。
【０１５５】
ICMCは、下記に詳述するレジスタ・チェックポインティング論理を含んでいてもよい。上で論じた構造（たとえばICMCおよびS、VおよびLVビット）は、コア間のこの専用／共有インターフェースが上下に動かされる実施形態については、メモリ階層構造中のどこかほかの場所に存在してもよい。したがって、本稿に記載される諸実施形態は、いかなる特定のメモリ・サブシステム構成において用いられてもよい。
【０１５６】
〈投機的に並列化されたコードのアーキテクチャ上のレジスタ状態の計算〉
本稿で論じられる再構成方式の諸実施形態は、特定の投機が誤っているときに、状態を正しい状態にロールバックするためのレジスタ・チェックポインティングを含む。チェックポイントの頻度はパフォーマンスにおいて重要な関わりをもつ。チェックポイントが頻繁であるほど、投機ミスに起因するオーバーヘッドは低くなるが、チェックポイントを生成するためのオーバーヘッドは高くなる。本節では、単一スレッド・コードのためのアーキテクチャ上のレジスタ状態の頻繁なチェックポイントを取ることができ、その計算がきわめて低いオーバーヘッドで複数のコアの間に分割および分配される方式が記載される。
【０１５７】
レジスタ・チェックポインティングのための機構の少なくとも一つの実施形態は、コアが命令をリタイアさせ、実行リソースを再生し（reclaim）、他のコアが停止しているときでさえ前向きの進行を行い続けることを許容する。本節で記述されるレジスタ・チェックポインティングは、安全な早期のレジスタ再生を許容し、それによりレジスタ・ファイルに対する圧力をほとんど増すことなく前向きの進行をする。本発明の少なくとも一つの実施形態については、チェックポイントは非常に頻繁に（数百命令毎に）取られ、それにより、割り込みまたはデータ投機ミスに起因してロールバックが必要とされるときに無駄にされる仕事の量はほとんどない。このように、開示される諸機構の実施形態により、データ投機ミスのオーバーヘッドが低減されるので、より積極的な最適化を実行することができる。
【０１５８】
従来の投機的マルチスレッディングとは対照的に、本発明の諸実施形態は、完全なアーキテクチャ上の状態（architectural  state）を生成する必要はない。その代わり、アーキテクチャ上の状態は、複数のコアによって部分的に計算されることができる。これにより、伝統的な投機的マルチスレッディング方式よりも細かい粒度でコアの間で命令が分配される、より柔軟なスレッディングが許容される。
【０１５９】
本発明の少なくとも一つの実施形態によれば、コアは、特定のポイントにおけるアーキテクチャ上の状態を得るために同期する必要はない。本技法は、アーキテクチャ上の状態を実質的にシームレスにマージし、ビルドする。
【０１６０】
本発明の諸実施形態は、もとの単一スレッドのアプリケーションが実行されたとした場合と同じ結果をもつようコミットされるために、コアによってリタイアさせられた命令が記憶されるROB（Reorder  Buffer［並べ替えバッファ］）を生成する。しかしながら、スレッドは非同期的に実行されるので、このROB中のエントリーはシーケンシャルに割り当てられるのではない。そうではなく、割り当てられる命令の数も種類もわからない領域がある。この状況は、たとえば、コア１から実行される命令の後にコミットされるべきコードの領域をコア０が実行している場合に起こりうる。この場合、この概念的なROBにおいては、コア１によってすでにリタイアさせられた命令と、コア１によってまだ実行／リタイアされていない命令に属するコア０による被リタイア命令との間に、ギャップがある。
【０１６１】
図２１は、チェックポインティング機構のROBの少なくとも一つの実施形態を示している。このROBにおいて、GRetire_0はコア０によってリタイアさせられた最後の命令をポイントし、GRetire_1はコア１によってリタイアさせられた最後の命令をポイントする。見て取れるように、コア０はコア１より先行し、よってGRetire_0とGRetire_1との間には、ROBにおけるギャップがある（影付きの領域で示す）。所与の時点において、完全なチェックポイントは（コア０または１のいずれかにおける）レジスタ・ファイル中の物理的なレジスタへのポインタをもつ。ここで、各論理的レジスタについて値が存在する。
【０１６２】
チェックポイント（ckp）は、各コアによって、該コアがあらかじめ定義された量の命令をリタイアさせるたびに置かれる。システムにおいて最も若い命令をリタイアさせるコアによって置かれるチェックポイントは部分的チェックポイントであることを注意しておく。置かれるチェックポイントより古いすべての命令を他のコアがリタイアさせ終わるまでは、このコアが実際にこの実行ポイントについてのアーキテクチャ上の状態を生成することは保証できない。
【０１６３】
これに対して、システムにおいて最も若い命令をリタイアさせるのでないコアによって置かれるチェックポイントは、完全なチェックポイントである。これはそのコアが、他のコアが実行した、当該チェックポイントより古い命令を知っているからである。したがって、そのコアは、その時点においてアーキテクチャ上の値のそれぞれがどこに存在するかを知っている。この例におけるコア０がなぜ、所定数の命令後に部分的チェックポイントであっても定期的にチェックポイントを置くかの理由は、これらの部分的チェックポイントによってポイントされないすべての物理的レジスタが再生されるからである。この特徴により、このコアは、そのレジスタ・ファイルに対する圧力の増加ほとんどなしで、前に進行できる。さらに、コア１がこのチェックポイントに到達するとすぐ、この時点におけるアーキテクチャ上の状態に属するコア０によって生成された値を含むレジスタがまだ再生されていないことが保証され、それにより、コア１から来る情報をもって完全なチェックポイントがビルドされうる。さらに、コア１によって上書きされたために当該チェックポイントに属さなかったコア０において割り当てられたレジスタも解放されることができる。
【０１６４】
システムにおいて最も若いのでない命令をリタイアさせるコア（たとえばコア１）によってより若い完全なチェックポイントが置かれるとすぐに、チェックポイントは解放されることができ、その物理的レジスタは再生されることができる。しかしながら、命令がシステムで最も古いものになるときに実行される何らかの有効確認がスレッディング方式によって要求されていることがありうる。したがって、有効確認が失敗した場合には、この命令より古いチェックポイントがそこにロールバックするために使用される。この筋書きでは、完全なチェックポイントは、関連付けられた完全なチェックポイントをもつ別の命令がシステム中で最も古いものになり、適正に有効確認されたあとに、解放される。
【０１６５】
スレッドによって実行されるすべての命令は、この命令に関連付けられたチェックポイントが復元される場合にジャンプするための、もとの（original）コードにおけるその命令の命令ポインタ（IP:  instruction  pointer）である関連付けられたIP_origをもつ。実行される命令のIPとそのIP_origとの間の変換はメモリに記憶される（ある実施形態では、コンパイラまたは動的オプティマイザがこの変換テーブルの生成を受け持つ）。こうして、データ投機ミスまたは割り込みのためにチェックポイントが復元されるときは常に、実行は、復元されるチェックポイントに関連付けられた、もとの単一スレッドのアプリケーションのIP_origにおいて続けられることになる。
【０１６６】
先行するコアと後続するコアは常に同じではなく、この役割は、もとのアプリケーションが諸スレッドに変換された仕方に依存して、時間とともに変わることがありうることを注意しておくべきである。
【０１６７】
所与の時点において、完全なチェックポイントは（コア０または１における）レジスタ・ファイル中の物理的なレジスタへのポインタをもつ。ここで、各論理的レジスタについて値が存在する。すべての命令がグローバルにコミットされ終わり、より若いチェックポイントが完全になったときに、チェックポイントは解放されることができ、その物理的レジスタは再生されることができる。
【０１６８】
コンパイラによって挿入されたCKP命令が見出され、最後のチェックポイント（CKP_DIST_CTE）以降少なくともある最小数の動的命令がグローバルにコミットされたときに、チェックポイントが置かれる。この論理は図１５に示されている。このCKP命令は、チェックポイントともに記憶される復元コードのIPをもち、それにより、割り込みまたはデータ投機ミスが起こるとき、直前のチェックポイントによってポイントされる値が、アプリケーションの実行を再開するコアにコピーされる。
【０１６９】
図２２は、レジスタ・チェックポインティング・ハードウェアの少なくとも一つの実施形態を示すブロック図である。少なくとも一つの実施形態について、図示されるレジスタ・チェックポインティング・ハードウェアの一部は、あるタイルの諸コアの間／うちにある。たとえば、ある実施形態では、論理ゲートはタイルの外にあり、LREG_FIFOはICMCの一部である。ある実施形態では、ICMCは次のうちの一つまたは複数を含む：１）コア毎のFIFO待ち行列（LREG_FIFO）；２）LREG_FIFO毎のポインタの集合；および３）LREG_FIFO毎のチェックポイント・テーブルのプール。たとえば、NORゲートの代わりにマルチプレクサ（MUX）のような他の論理が使われてもよい。
【０１７０】
論理的レジスタに書き込みをするリタイアされた命令は、LREG_FIFO中にエントリーを割り当てる。図２２は、エントリーの構成要素を示している：１）このエントリーに関連付けられたアーキテクチャ上の状態チェックポイントがある場合に1にセットされるckpという名前のフィールド；当該命令が上書きする論理的レジスタの識別子を記憶するLDestフィールド；および３）プログラム順において次の命令を含むスレッドを同定するPOPフィールド。POPポインタは、単一スレッドのアプリケーションがシーケンシャルに実行されたとした場合と同じ結果を得るために、種々のスレッドからの命令がリタイアすべき順序を同定するための機構である。しかしながら、本発明は、単一スレッドのアプリケーションから生成された種々のスレッドの命令の間の順序を同定するために使用されうる任意の他の機構とともに機能できる。
【０１７１】
ポインタの集合は、次のものを含む：１）LREG_FIFOの最初の未使用のエントリーをポイントする、コア毎のRetirePポインタ。ここで、新しいリタイアさせられた命令はこのレジスタによってポイントされるエントリーを割り当てる；２）順にLREG_FIFOエントリーを割り当て解除するために使われる、LREG_FIFO中の最も古い割り当てられたエントリーをポイントするコア毎のCommitPポインタ；および３）完全なチェックポイントをビルドするために進められた（walked）LREG_FIFO中の最後のエントリーをポイントする、コア毎のGretireポインタ。また、CHKP_Dist_CTEレジスタまたは定数値も示されている。このレジスタは、LREG_FIFO中の二つのチェックポイントの間のエントリー数で表した距離（distance）を定義する。また、最後のチェックポイント後にLREG_FIFOにおいて割り当てられたエントリー数を数える（count）LREG_FIFO毎のInst_CNTレジスタも示されている。
【０１７２】
LREG_FIFO毎のチェックポイント・テーブルのプールは、フライト中の（in-flight）チェックポイントの最大数を定義する。チェックポイントの各プールは、チェックポイントが順に割り当てられ、再生されるFIFO待ち行列として機能する。チェックポイントは、該チェックポイントが生成された命令のIP、ロールバック・コードのIPおよびアーキテクチャにおける各論理的レジスタのためのエントリーを含む。これらのエントリーのそれぞれは：当該チェックポイントに先立って生成された最後の値がその特定の論理的レジスタについて存在する物理的なレジスタ（「PDest」）；PDest識別子が直前のチェックポイントにおけるPDestと異なる場合に1に設定される上書き（overwritten）ビット（「O」）；および論理的レジスタのアーキテクチャ上の状態が別のコアに存在する場合に1に設定される遠隔（remote）ビット（「R」）。これらのビットについては下記で詳述する。
【０１７３】
図２２はまた、スレッドの一つから来る命令のIPおよびスレッドidによってインデックスされ、そのスレッドのその特定のIPにおけるアーキテクチャ上の状態が復元されるときにジャンプするためのもとの単一スレッドのアプリケーションのIPにマッピングする、アプリケーション・メモリ・スペース内に位置されるデータ構造をも示している。
【０１７４】
新しいアーキテクチャ上のレジスタ値を生成する命令をコアがリタイアさせるたびに、この命令は対応するLREG_FIFO中に新しいエントリーを割り当てる。次いで、アクティブなチェックポイント内のエントリーが、その命令が上書きする論理的レジスタについて読まれる。Oビットがセットされているとき、エントリーに記憶されているPDest識別子は再生される。次いで、Oビットがセットされ、Rビットが非セットにされる。最後に、PDestフィールドが、リタイアさせられた命令が割り当てた物理的レジスタの識別子をもって更新される。ひとたびアクティブなチェックポイントが更新されたら、InstCNTカウンタが減らされ、該カウンタが0になったら、現在のチェックポイントは次のチェックポイントにコピーされ、この次のチェックポイントがアクティブなチェックポイントとなり、新しいアクティブなチェックポイントにおけるすべてのOビットはリセットされ、InstCNTレジスタは再びCHKP_Dist_CTEにセットされる。
【０１７５】
GRetireポインタがRetirePポインタに一致する場合、これは、この命令がシステムにおける最も若い命令ではなく、図１４の例におけるコア１として振る舞うべきであることを意味する。こうして、POPビットがチェックされ、それが他のコアをポイントするとき、該他のコアのGRetireポインタは、ポイントしているPOPポインタが見出されるまで該他のコアのLREG_FIFOを進める（walk）ために使われる。進められる（walked）すべてのエントリーについて、LDest値が読まれ、アクティブなチェックポイントは次のようにして更新される：Oビットがセットされているとき、PDestに書かれている物理的なレジスタの識別子が再生される。次いで、Oビットがリセットされ、PDestが更新される。ckpビットが1にセットされたエントリーであれば、部分的チェックポイントは、アクティブなチェックポイント情報をもって完了される。このマージは、部分的チェックポイントにおける全PDestを再生することに関わり、部分的なチェックポイントのOビットがセットされ、アクティブなチェックポイントにおけるRビットがリセットされる。次いで、これらのエントリーのOビットをリセットしてアクティブなチェックポイントが更新される。他方、GRetireポインタがRetirePに一致しない場合、システム中の最も若い命令が既知なので、何もされない。
【０１７６】
最後に、チェックポイントは、そのチェックポイントまでロールバックすることは必要でないと判定されるときに、解放されることができる。すべてのリタイアさせられた命令が正しく、いかなる例外も起こさないことが保証されるならば、チェックポイントは、より若いチェックポイントが完了する前に、解放されてもよい。対照的に、リタイアさせられた命令が、スレッディング方式においてそうであるように、さらなる有効確認を必要とすることもありうる。この有効確認は、命令がシステム中で最も古いものになるときに行われる。この場合、チェックポイントは、関連付けられたチェックポイントをもつより若い命令がシステム中で最も古いものになり、有効確認が正しいと、すぐに解放されることができる。
【０１７７】
割り込みまたはデータ投機ミスが発生するときは常に、直前のチェックポイントによってポイントされる値は、アプリケーションの実行を再開するコアにコピーされるべきである。このコピーは、ハードウェアによってまたはソフトウェアによって、これらの値を明示的にコピーするサービス・ルーチンの先頭として行われてもよい。ひとたびアーキテクチャ上の状態がコピーされると、スレッドのIPからもとのIPに変換するために使用されるテーブルは、もとの単一スレッドのアプリケーションのIPを得るためにチェックポイントが置かれたところの命令のIPを加えられる（チェックポイントが置かれる時点までにIPは記憶された）。次いで、得られたもとのIPにジャンプして実行が再開し、諸スレッドが再び派生されることができる当該アプリケーション中の別のポイントが見出されるまで、もとの単一スレッドのアプリケーションが実行される。上記の詳細な図解が図２３ａ〜ｃに示されている。
【０１７８】
〈例示的なSpMTシステム〉
図２４は、スレッド・レベル再構成を利用するマイクロプロセッサのある実施形態を示している。特に、図２４は、一つまたは複数のプロセッサ・コア２４０５および２４１０を有するマイクロプロセッサ２４００を示している。各プロセッサ・コアはそれぞれローカル・キャッシュ２４０７および２４１３が付随している。図２４にはまた、ローカル・キャッシュ２４０７および２４１３のそれぞれに記憶された情報の少なくとも一部の諸バージョンを記憶しうる共有キャッシュ・メモリ２４１５も示されている。いくつかの実施形態では、マイクロプロセッサ２４００は、統合されたメモリ・コントローラ、統合されたグラフィクス・コントローラおよびI/O制御のようなコンピュータ・システム内の他の機能を実行するための他の論理といった、図２４に示されない他の論理をも含んでいてもよい。ある実施形態では、マルチプロセッサ・システムにおける各マイクロプロセッサまたはマルチコア・プロセッサにおける各プロセッサ・コアは、少なくとも一つの実施形態に基づく、分解された命令ストリームからシーケンシャルな実行を再構成するための論理２４１９を含んでいたり、あるいは他の形で該論理２４１９に関連付けられたりしていてもよい。論理は、一部の従来技術の実装よりも複数のコアまたはプロセッサの間でのより効率的なリソースの割り当てを可能にするための回路、ソフトウェア（有形な媒体において具現される）または両方を含んでいてもよい。
【０１７９】
図２５は、たとえば、本発明のある実施形態が使用されうる、フロント・サイド・バス（FSB:  front-side-bus）・コンピュータ・システムを示している。どのプロセッサ２５０１、２５０５、２５１０または２５１５も、プロセッサ・コア２５２５、２５２７、２５３３、２５３７、２５４３、２５４７、２５５３、２５５７の一つの中のまたは該プロセッサ・コアの一つに他の形で関連付けられた任意のローカルなレベル１（L1）キャッシュ・メモリ２５２０、２５２７、２５３０、２５３５、２５４０、２５４５、２５５０、２５５５からの情報にアクセスしてもよい。さらに、どのプロセッサ２５０１、２５０５、２５１０または２５１５も、共有されるレベル２（L2）キャッシュ２５０３、２５０７、２５１３、２５１７の任意のものからの、あるいはシステム・メモリ２５６０からの情報にチップセット２５６５を介してアクセスしてもよい。図２５におけるプロセッサの一つまたは複数は、少なくとも一つの実施形態に基づく、分解された命令ストリームからシーケンシャルな実行を再構成するための論理２５１９を含む、または該論理２５１９に他の形で関連付けられていてもよい。
【０１８０】
図２５に示されるFSBコンピュータ・システムに加えて、本発明のさまざまな実施形態との関連で、ポイントツーポイント（P2P）相互接続システムおよびリング相互接続システムを含む他のシステム構成が使用されてもよい。
【０１８１】
ここで図２６を参照するに、本発明のある実施形態に基づくシステム２６００のブロック図が示されている。システム２６００は一つまたは複数の処理要素２６１０、２６１５を含んでいてもよく、それらの処理要素はグラフィクス・メモリ・コントローラ・ハブ２６２０（GMCH:  graphics  memory  controller  hub）に結合される。追加的な処理要素２６１５が任意的であるという性質は図２６において破線で表されている。
【０１８２】
各処理要素は、単一コアであってもよく、あるいは代替的に複数のコアを含んでいてもよい。処理要素は、任意的に、統合されたメモリ・コントローラおよび／または統合されたI/O制御論理のような、処理コア以外の他のダイ上要素を含んでいてもよい。また、少なくとも一つの実施形態について、処理要素のコア（単数または複数）は、コア当たり二つ以上のハードウェア・スレッド・コンテキストを含んでいてもよいという意味でマルチスレッドであってもよい。
【０１８３】
図２６は、GMCH  ２６２０がメモリ２６４０に結合されてもよいことを示している。メモリ２６４０はたとえば、動的ランダム・アクセス・メモリ（DRAM）であってもよい。DRAMは、少なくとも一つの実施形態については、不揮発性キャッシュに関連付けられていてもよい。
【０１８４】
GMCH  ２６２０はチップセットまたはチップセットの一部であってもよい。GMCH  ２６２０はプロセッサ（単数または複数）２６１０、２６１５と通信し、プロセッサ（単数または複数）２６１０、２６１５とメモリ２６４０との間の対話を制御してもよい。GMCH  ２６２０はまた、プロセッサ（単数または複数）２６１０、２６１５とシステム２６００の他の要素との間の加速されたバス・インターフェースとして機能してもよい。少なくとも一つの実施形態については、GMCH  ２６２０は、プロセッサ（単数または複数）２６１０、２６１５と、フロント・サイド・バス（FSB）２６９５のようなマルチドロップ・バスを介して通信する。
【０１８５】
さらに、GMCH  ２６２０は（フラット・パネル・ディスプレイのような）ディスプレイ２６４０に結合されている。GMCH  ２６２０は統合されたグラフィクス・アクセラレータを含んでいてもよい。GMCH  ２６２０はさらに、システム２６００にさまざまな周辺機器を結合するために使用されうる入出力（I/O）コントローラ・ハブ（ICH:  input/output  controller  hub）２６５０に結合される。図２６の実施形態にはたとえば、ICH  ２６５０に結合された別個のグラフィクス・デバイスであってもよい外部グラフィクス・デバイス２６６０が、もう一つの周辺機器２６７０とともに示されている。
【０１８６】
あるいはまた、追加的なまたは異なる処理要素もシステム２６００に存在していてもよい。たとえば、追加的な処理要素（単数または複数）２６１５は、プロセッサ２６１０と同じ追加的なプロセッサ（単数または複数）、プロセッサ２６１０と異質または非対称である追加的なプロセッサ（単数または複数）、アクセラレータ（たとえばグラフィクス・アクセラレータまたはデジタル信号処理（DSP:  digital  signal  processing）ユニットのような）、現場プログラム可能なゲート・アレイ（field  programmable  gate  array）または他の任意の処理要素を含んでいてもよい。物理的なリソース２６１０、２６１５の間には、アーキテクチャ上、マイクロアーキテクチャ上、熱的、電力消費特性などを含む一連の利点の指標の面で、多様な相違がありうる。これらの相違は、処理要素２６１０、２６１５の間の非対称性および異質性として事実上現れてもよい。少なくとも一つの実施形態については、さまざまな処理要素２６１０、２６１５は同じダイ・パッケージに存在してもよい。
【０１８７】
ここで図２７を参照するに、本発明のある実施形態に基づく第二のシステム実施形態２７００のブロック図が示されている。図２７に示されるように、マルチプロセッサ・システム２７００はポイントツーポイント相互接続システムであり、ポイントツーポイント相互接続２７５０を介して結合された、第一の処理要素２７７０および第二の処理要素２７８０を含む。図２７に示されるように、処理要素２７７０および２７８０のそれぞれは、第一および第二の処理コア（すなわち、プロセッサ・コア２７７４ａおよび２７７４ｂならびにプロセッサ・コア２７８４ａおよび２７８４ｂ）を含む、マルチコア・プロセッサであってもよい。
【０１８８】
あるいはまた、処理要素２７７０、２７８０の一つまたは複数が、アクセラレータまたは現場プログラム可能なゲート・アレイのようなプロセッサ以外の要素であってもよい。
【０１８９】
二つの処理要素２７７０、２７８０しか示していないが、本発明の範囲はそのように限定されるものではないことは理解しておくべきである。他の実施形態では、所与のプロセッサ内に一つまたは複数の追加的な処理要素が存在していてもよい。
【０１９０】
第一の処理要素２７７０はさらに、メモリ・コントローラ・ハブ（MCH）２７７２およびポイントツーポイント（P-P）インターフェース２７７６および２７７８を含んでいてもよい。同様に、第二の処理要素２７８０は、MCH  ２７８２およびP-Pインターフェース２７８６および２７８８を含んでいてもよい。プロセッサ２７７０、２７８０は、PtPインターフェース２７７８、２７８８を使ってポイントツーポイント（PtP）インターフェース２７５０を介してデータを交換してもよい。図２７に示されるように、MCH  ２７７２および２７８２はプロセッサをそれぞれのメモリ、すなわちメモリ２７４２およびメモリ２７４４に結合する。これらは、それぞれのプロセッサにローカルに取り付けられたメイン・メモリの一部であってもよい。
【０１９１】
プロセッサ２７７０、２７８０は、ポイントツーポイント・インターフェース回路２７７６、２７９４、２７８６、２７９８を使って個々のPtPインターフェース２７５２、２７５４を介して、それぞれチップセット２７９０とデータを交換してもよい。チップセット２７９０はまた、高性能グラフィクス・インターフェース２７３９を介して高性能グラフィクス回路２７３８ともデータを交換してもよい。本発明の諸実施形態は、任意の数のプロセッサ・コアを有する任意のプロセッサ内に、あるいは図２７のPtPバス・エージェントのそれぞれの中に位置されてもよい。ある実施形態では、任意のプロセッサ・コアがローカルなキャッシュ・メモリ（図示せず）を含んでいたり、あるいは他の形でローカルなキャッシュ・メモリに関連付けられたりしていてもよい。さらに、共有キャッシュ（図示せず）が、両方のプロセッサの外で、それでいて両プロセッサにp2p相互接続を介して接続されているいずれかのプロセッサに含まれていてもよく、それにより、プロセッサが低電力モードにされる場合に、一方または両方のプロセッサのローカルなキャッシュ情報が共有キャッシュに記憶されてもよい。図２７のプロセッサまたはコアの一つまたは複数は、少なくとも一つの実施形態に基づく、分解された命令ストリームからシーケンシャルな実行を再構成するための論理２７１９を含んでいたり、あるいは他の形で該論理２７１９に関連付けられていたりしてもよい。
【０１９２】
第一の処理要素２７７０および第二の処理要素２７８０は、それぞれP-P相互接続２７７６、２７８６および２７８４を介してチップセット２７９０に結合されていてもよい。図２７に示されるように、チップセット２７９０はP-Pインターフェース２７９４および２７９８を含む。さらに、チップセット２７９０は、チップセット２７９０を高性能グラフィクス・エンジン２７４８と結合するためのインターフェース２７９２を含む。ある実施形態では、バス２７４９がチップセット２７９０にグラフィクス・エンジン２７４８を結合するために使われてもよい。あるいはまた、ポイントツーポイント相互接続２７４９がこれらのコンポーネントを結合してもよい。
【０１９３】
一方、チップセット２７９０は第一のバス２７１６にインターフェース２７９６を介して結合されてもよい。ある実施形態では、第一のバス２７１６は周辺コンポーネント相互接続（PCI:  Peripheral  Component  Interconnect）バスまたはPCIエクスプレス（PCI  Express）バスもしくは他の第三世代のI/O相互接続バスのようなバスであってもよい。ただし、本発明の範囲はそのように限定されるものではない。
【０１９４】
図２７に示されるように、さまざまなI/Oデバイス２７１４が、第一のバス２７１６を第二のバス２７２０に結合するバス・ブリッジ２７１８とともに、第一のバス２７１６に結合されうる。ある実施形態では、第二のバス２７２０は低ピン数（LPC:  low  pin  count）バスであってもよい。ある実施形態では、たとえばキーボード／マウス２７２２、通信デバイス２７２６およびデータ記憶ユニット２７２８を含むさまざまなデバイスが第二のバス２７２０に結合されてもよい。データ記憶ユニット２７２８は、コード２７３０を含んでいてもよいディスク・ドライブまたは他の大容量記憶装置といったものである。コード２７３０は、上記の一つまたは複数の実施形態に基づいて命令および／またはプログラム順ポインタを順序付けることを含んでいてもよい。さらに、オーディオI/O  ２７２４が第二のバス２７２０に結合されてもよい。他のアーキテクチャが可能であることを注意しておく。たとえば、図２７のポイントツーポイント・アーキテクチャの代わりに、システムはマルチドロップ・バスまたは他のそのようなアーキテクチャを実装してもよい。
【０１９５】
ここで図２８を参照すると、本発明のある実施形態に基づく第三のシステム実施形態２８００のブロック図が示されている。図２７および図２８における同様の要素は同様の参照符号を帯びており、図２７のある種の側面は、図２８の他の側面を埋没させるのを避けるために図２８からは省略されている。
【０１９６】
図２８は、処理要素２７７０、２７８０が、それぞれ統合されたメモリおよびI/O制御論理（CL:  control  logic）２７７２および２７８２を含んでいてもよいことを示している。少なくとも一つの実施形態については、CL  ２７７２、２７８２は、図２６および図２７との関連で上記したようなメモリ・コントローラ・ハブ論理（MCH）を含んでいてもよい。さらに、CL  ２７７２、２７８２は、I/O制御論理をも含んでいてもよい。図２８は、CL  ２７７２、２７８２にメモリ２７４２、２７４４が結合されているだけでなく、I/Oデバイス２８１４も制御論理２７７２、２７８２に結合されていることを示している。レガシーI/Oデバイス２８１５はチップセット２７９０に結合される。
【０１９７】
本稿に開示される機構の諸実施形態は、ハードウェア、ソフトウェア、ファームウェアまたはそのような実装アプローチの組み合わせにおいて実装されてもよい。本発明の諸実施形態は、少なくとも一つのプロセッサと、データ記憶システム（揮発性および不揮発性のメモリおよび／または記憶素子を含む）と、少なくとも一つの入力装置と、少なくとも一つの出力装置とを有するプログラム可能なシステム上で実行されるコンピュータ・プログラムとして実装されてもよい。
【０１９８】
図２７に示されたコード２７３０のようなプログラム・コードが、本稿に記載される機能を実行し、出力情報を生成するために、入力データに適用されてもよい。たとえば、プログラム・コード２７３０は、図２５に示される方法２５００、２５５０の諸実施形態を実行するためにコードされるオペレーティング・システムを含んでいてもよい。したがって、本発明の諸実施形態は、本発明の諸実施形態の動作を実行するための命令を含む、あるいは本稿に記載される構造、回路、装置、プロセッサおよび／またはシステム特徴を定義するHDLのような設計データを含む機械可読媒体をも含む。そのような実施形態は、プログラム・プロダクトとも称されうる。
【０１９９】
そのような機械可読記憶媒体は、限定することなく、機械またはデバイスによって製造されるまたは形成される要素の有形な配列を含んでいてもよく、ハードディスク；フロッピー（登録商標）ディスク、光学式ディスク、コンパクトディスク読み出し専用メモリ（CD-ROM）、書き換え可能型コンパクトディスク（CD-RW）および光磁気ディスクを含む他の任意の型のディスク；読み出し専用メモリ（ROM）、動的ランダム・アクセス・メモリ（DRAM）、静的ランダム・アクセス・メモリ（SRAM）、消去可能なプログラム可能型読み出し専用メモリ（EPROM）、フラッシュメモリ、電気的に消去可能なプログラム可能型読み出し専用メモリ（EEPROM）ランダム・アクセス・メモリ（RAM）といった半導体デバイス；磁気または光学式カードまたは電子的な命令を記憶するのに好適な他の任意の型の媒体を含む。
【０２００】
出力情報は、既知の仕方で、一つまたは複数の出力デバイスに加えられてもよい。本願の目的のためには、処理システムは、たとえばデジタル信号プロセッサ（DSP:  digital  signal  processor）、マイクロコントローラ、特定用途向け集積回路（ASIC:  application  specific  integrated  circuit）またはマイクロプロセッサのようなプロセッサを有する任意のシステムを含む。
【０２０１】
プログラムは、処理システムと連絡するために、高レベルの手続き型のまたはオブジェクト指向型のプログラミング言語で実装されてもよい。プログラムは、望むならアセンブリまたは機械語で実装されてもよい。実際、本稿に記載される機構はいかなる特定のプログラミング言語にも範囲において限定されない。いずれにせよ、言語はコンパイルされる言語でもインタープリター言語でもよい。
【０２０２】
少なくとも一つの実施形態の一つまたは複数の側面は、プロセッサ内でさまざまな論理を表現する機械可読媒体上に記憶される表現データであって、機械によって読み込まれたときに、該機械に、本稿に記載される技法を実行するための論理を作成させるものによって実装されてもよい。「IPコア」として知られるそのような表現は有形の機械可読媒体上に記憶され、実際に前記論理またはプロセッサをなす製作機械中にロードするために、さまざまな顧客または製造施設に供給されてもよい。
【０２０３】
このように、方法、装置の諸実施形態を記述してきた。上記の記述は制約するものではなく例示するものであることが意図されていることは理解しておくべきである。上記の記述を読み、理解すれば、当業者には他の多くの実施形態が明白であろう。したがって、本発明の範囲は、付属の請求項を参照して、そのような請求項に資格のある全等価物の範囲をもって決定されるべきである。
【図１】
0005547208.tif 000004
【図２】
0005547208.tif 000005
【図３】
0005547208.tif 000006
【図４】
0005547208.tif 000007
【図５】
0005547208.tif 000008
【図６】
0005547208.tif 000009
【図７】
0005547208.tif 000010
【図８】
0005547208.tif 000011
【図９】
0005547208.tif 000012
【図１０】
0005547208.tif 000013
【図１１】
0005547208.tif 000014
【図１２】
0005547208.tif 000015
【図１３】
0005547208.tif 000016
【図１４】
0005547208.tif 000017
【図１５】
0005547208.tif 000018
【図１６】
0005547208.tif 000019
【図１７】
0005547208.tif 000020
【図１８】
0005547208.tif 000021
【図１９】
0005547208.tif 000022
【図２０】
0005547208.tif 000023
【図２１】
0005547208.tif 000024
【図２２】
0005547208.tif 000025
【図２３ａ】
0005547208.tif 000026
【図２３ｂ】
0005547208.tif 000027
【図２３ｃ】
0005547208.tif 000028
【図２４】
0005547208.tif 000029
【図２５】
0005547208.tif 000030
【図２６】
0005547208.tif 000031
【図２７】
0005547208.tif 000032
【図２８】
0005547208.tif 000033