(57)【要約】一実施形態において、システムは、Ｓ個の段を含むループの演算を実行する少なくとも１つのコアを含むプロセッサを含む。当該システムは、前記ループの第１の変数に関連付けられた対応するレジスタのライフタイムを延ばし、且つ、前記レジスタの内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入手段をさらに含む。当該システムは、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）をさらに含む。他の実施形態も説明され、特許請求される。
2016519375.tif 000002
【特許請求の範囲】
【請求項１】
ループの演算を実行する少なくとも１つのコアと、
前記ループの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、前記レジスタの内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入手段と、
を含むプロセッサと、
ダイナミックランダムアクセスメモリ（ＤＲＡＭ）と、
を備えたシステム。
【請求項２】
前記プロセッサは、前記レジスタを第２のレジスタにリネームするモジュロ変数展開手段をさらに含む、請求項１記載のシステム。
【請求項３】
前記モジュロ変数展開手段は、さらに、前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタにリネームする、請求項２記載のシステム。
【請求項４】
前記プロセッサは、実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットする、請求項１乃至３いずれか一項記載のシステム。
【請求項５】
前記プロセッサは、前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償手段であって、各イテレーションはＳ個の段を含む、補償手段をさらに含む、請求項１記載のシステム。
【請求項６】
前記補償手段は、さらに、前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた前記レジスタのライブアウト値を回復させる、請求項５記載のシステム。
【請求項７】
前記プロセッサは、前記補償手段による前記ストア演算の再実行及び前記レジスタの前記ライブアウト値の回復の前に前記例外を処理するハンドラ手段をさらに含む、請求項６記載のシステム。
【請求項８】
前記プロセッサは、さらに、前記例外に応答して、（Ｎ−Ｓ＋Ｍ＋１）番目のイテレーションから始まるよう前記ループの実行を再開する、請求項７記載のシステム。
【請求項９】
命令を含む少なくとも１つのコンピュータ読み取り可能媒体であって、前記命令は、実行されたときに、システムが、
パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信することであって、前記ループの各イテレーションは、レジスタに変数のそれぞれの値を割り当てるそれぞれの割り当て演算と、前記イテレーションにおいて決定された値をメモリに記憶させるそれぞれのストア演算と、を含む、受信することと、
前記それぞれのストア演算の実行を遅延させ、且つ、各イテレーションにおける前記レジスタのそれぞれのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入することと、
を可能にする、少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１０】
前記ループの第１のイテレーションの前記変数の値が割り当てられる、第１のレジスタ名を有する第１のレジスタの使用を、第２のレジスタ名を有する第２のレジスタで置換するモジュロ変数展開命令をさらに含む、請求項９記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１１】
複数のイテレーションの各イテレーションにおいて、対応するレジスタを、前記第１のレジスタ名を有する前記第１のレジスタから、対応する異なるレジスタ名を有する対応する異なるレジスタに置換する命令をさらに含む、請求項１０記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１２】
実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットする命令をさらに含む、請求項９乃至１１いずれか一項記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１３】
前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションの第１のストア演算を再実行する命令であって、前記ループの各イテレーションはＳ個の段を含む、命令をさらに含む、請求項９記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１４】
前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させる命令をさらに含む、請求項１３記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１５】
前記第１のレジスタの前記ライブアウト値の回復の前に前記例外を処理する命令をさらに含む、請求項１４記載の少なくとも１つのコンピュータ読み取り可能媒体。
【請求項１６】
パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信するステップであって、各イテレーションは、レジスタに前記イテレーションに関連付けられた変数の第１の値を割り当てる割り当て演算と、前記イテレーションの実行から決定された第２の値をメモリに記憶させるストア演算と、を含む、ステップと、
それぞれの前記ストア演算の実行を遅延させ、且つ、それぞれの前記イテレーションにおける前記レジスタのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入するステップと、
を含む方法。
【請求項１７】
第１のイテレーションにおける前記変数に関連付けられた前記レジスタを、第１のレジスタから第１の置換レジスタに置換し、前記第１の置換レジスタを、前記ループの後続のイテレーションにおける前記変数に再割り当てするステップをさらに含む、請求項１６記載の方法。
【請求項１８】
特定のイテレーションにおいて発生した例外に応答して、ハンドラコードの実行を介して前記例外を処理するステップをさらに含む、請求項１６記載の方法。
【請求項１９】
前記ループの最も直近に終了したイテレーションの結果をコミットするステップをさらに含む、請求項１８記載の方法。
【請求項２０】
前記最も直近に終了したイテレーションから始まるよう前記ループの実行を再開するステップをさらに含む、請求項１９記載の方法。
【請求項２１】
請求項１６乃至２０いずれか一項記載の方法を実行する手段を備えた装置。
【請求項２２】
ループの演算を実行する少なくとも１つのコアと、
前記ループの第１のイテレーションの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、イテレーションにおいて決定される、第２の変数の値の内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入ロジックと、
を備えたプロセッサ。
【請求項２３】
前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタに置換するモジュロ変数展開手段をさらに備えた、請求項２２記載のプロセッサ。
【請求項２４】
前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償手段であって、各イテレーションはＳ個の段を含む、補償手段をさらに備えた、請求項２２記載のプロセッサ。
【請求項２５】
前記補償手段は、さらに、前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させる、請求項２４記載のプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
実施形態は、パイプラインソフトウェア（pipelined  software）に関する。
【背景技術】
【０００２】
ソフトウェアパイプライニングは、計算集約ループ（computationally-intensive  loop）の複数のイテレーションの実行をオーバーラップすることにより、計算集約ループのスループットを増加させることができるコンパイラ技術である。オーバーラップされる複数のイテレーションにおいて、いくつかのイテレーションは、例えば演算の実行の順序はループ内に示される実行順序とは異なることがある、といった演算の順序の逆転に起因して、投機的（speculative）であり得る。投機的イテレーション中に発生する例外は、そのイテレーションの結果を無効なものにすることがある。無効な結果を修正するための１つの技術は、ループイテレーションの全ての以前の結果を破棄して、ループ計算を再度開始すること（ロールバック）であるが、これは、計算リソース及び時間の観点でコストがかかり得る。
【図面の簡単な説明】
【０００３】
【図１】本発明の一実施形態に従った、ループの実行を最適化するシステムのブロック図。
【図２】本発明の一実施形態に従った、パイプラインスケジュールループのための最適化スキームの図。
【図３】本発明の一実施形態に従った、パイプラインスケジュールループの実行を最適化する方法のフロー図。
【図４】本発明の一実施形態に従ったプロセッサのブロック図。
【図５】本発明の一実施形態に従った、複数のコアを含むプロセッサの一実施形態を示す図。
【図６】本発明の一実施形態に従ったシステムのブロック図。
【発明を実施するための形態】
【０００４】
アトミック実行サポート（atomic  execution  support）による動的な最適化におけるロールバックオーバーヘッドに対処するための装置及び方法が、本明細書で提示される。本発明の実施形態において、ソフトウェアパイプラインループ（software  pipelined  loop）の動的なバイナリ最適化におけるロールバックオーバーヘッドを低減させることができるコード生成技術が提示される。
【０００５】
アトミック領域（atomic  region）は、積極的投機（aggressive  speculation）（データ及びコントロールの両方）が実行されるコードの領域を指定し得、アップデートが、アトミック領域の最後でコミットされ得る。アトミック領域は、最適化範囲を制限するので、アトミック領域サイズを増大させることが重要であり得る。しかしながら、例えば、予期せぬ挙動（例えば、投機失敗例外（speculation  failure  exception）、サイドイグジット（side  exit）、メモリフォールト）が検出されたとき、より大きなアトミック領域サイズは、増大されたロールバックオーバーヘッドの下振れ（downside）を有し、領域内でなされたいかなる進行も破棄され得、実行が、その領域の最初にロールバックされ得、ループが、あまり積極的でない最適化（less  aggressive  optimization）を伴って繰り返され得る。
【０００６】
予期せぬ挙動（例えば、例外、フォールト、投機失敗、サイドイグジット）に応答して、本発明の実施形態は、最後の非投機的イテレーションの結果の回復を可能にし、前のコミット以降のイテレーションをコミットする。これは、前のイテレーションの「ライブアウト（live-out）」値の追加のコピーを保持し、メモリの内容を損なうことなく投機的イテレーションによる影響を受けないままであるようストア演算を遅延させることにより、実現することができる。
【０００７】
図１は、本発明の一実施形態に従った、ループの実行を最適化するシステム１００のブロック図である。システム１００は、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）１８０に接続されたプロセッサ１１０を含む。プロセッサ１１０は、命令を実行する１以上のコア１１２０、１１２１．．．１１２ｎを含み得る。プロセッサ１１０はまた、命令スケジュールロジック１１４、モジュロ変数展開ロジック（modulo  variable  expansion  logic）１１６、段挿入ロジック１１８、補償ロジック（compensation  logic）１２０、及び、キャッシュ１２２を含む１以上のキャッシュメモリを含み得る。命令スケジュールロジック１１４、モジュロ変数展開ロジック１１６、段挿入ロジック１１８、及び補償ロジック１２０は、ソフトウェア、ファームウェア、ハードウェア、又はこれらの組合せにより実装され得る。
【０００８】
動作中、複数の演算を含むループは、コア１１２０等、コアのうちの１つで実行され得る。命令スケジュールロジック１１４は、パイプラインスケジュール（pipelined  schedule）に従って、ループのイテレーションをスケジュールすることができる。いくつかの実施形態において、第１のイテレーションの演算のうちの１以上は、第２のイテレーション（すなわち後のイテレーション）における演算のうちの１以上が実行されるようスケジュールされた後に（例えばそのような演算より後に）実行されるようスケジュールされ得る。モジュロ変数展開ロジック１１６は、第１のイテレーションの１以上の演算の、後のイテレーションの１以上の演算に対する依存性を低減させるために、ループの変数Ｘの値が割り当てられているレジスタのレジスタ名をリネームすることができる（例えば、レジスタＸの代わりに置換レジスタＸｉを用いて）。
【０００９】
ループは、イテレーションを複数実行し、各イテレーションは、通常、複数の段を含む。イテレーションの各段は、イテレーションの開始と直後のイテレーションの開始との間に複数のサイクル（「イテレーション間隔（ＩＩ）」）を含む。段挿入ロジック１１８は、リネームされたレジスタのライフタイム（例えば、割り当て値を含むようレジスタが信頼される時間）を延ばし、且つ、リネームされたレジスタの内容の記憶を遅延させるために、ランタイムにおける実行の前に、ループの各イテレーションに段を挿入することができる。補償ロジック１２０は、実行されなかった任意の遅延されたストア（store）の実行を終了させ、ループが終了した後、最終値をレジスタＸに返すことができる。
【００１０】
図２は、本発明の一実施形態に従った、パイプラインスケジュールループ（pipeline  scheduled  loop）のための最適化スキームを示している。例示的なループとして、擬似コードループ２１０は、値をレジスタＸに割り当てる割り当て演算（Ｘ←）と、その後に続く２つの乗算演算（ＭＵＬＴ）と、その後に続く、イテレーションにおいて決定された値（例えば、レジスタＸ内の値又は別の値）を、例えば図１のＤＲＡＭ１８０といったメモリのメモリ位置に記憶させるストア演算（ＳＴＯＲＥ）と、を含む。
【００１１】
ソフトウェアパイプラインスケジュール２２０は、図１の命令スケジュールロジック１１４等のソフトウェアスケジュールロジックにより決定され得るパイプラインスケジュールに従ったループ２１０の３つのイテレーションの実行を表す。イテレーション０、１、２は、各イテレーションの開始に関して、２つのサイクルの開始間隔（ＩＩ）だけ離されている。各イテレーションは、複数の段に分割され得、各段は、ＩＩサイクルを含み得る。例えば、パイプラインスケジュール２２０において、各イテレーションは、３個の段を含む。例えば、イテレーション０は、段１〜３（サイクル０〜５）を含む。このスケジュールは、繰り返される安定状態（steady  state）に達し得る。安定状態は、１つのイテレーションの演算の各々を含むカーネル２２４により表され得る。カーネルは、破線ボックス２２４により示されるように、ＩＩサイクルごとに繰り返される。
【００１２】
イテレーション１及び２は、利用可能であり得る計算リソースを利用するためにパイプラインスケジュールされ得、したがって、イテレーション０、１、及び２は、並列して実行され得る。例えば、イテレーション０が実行中である場合、イテレーション１及び２は、イテレーション０が実行されている間に実行されることになるため、「投機的である」とみなされ得、したがって、イテレーション１及び２は、イテレーション０の実行中に変わり得るイテレーション変数に対する依存性に起因して、ループ２１０の正確なイテレーションであることもあればループ２１０の正確なイテレーションでないこともある。例えば、サイクル０においてレジスタＸに記憶された値が、イテレーション０のサイクル３において変わる場合、（イテレーション１の）サイクル２におけるレジスタＸ内の値は、イテレーション０の終了時におけるＸの値に一致しないことになり、したがって、イテレーション１内の任意の計算は、不正確であり得、破棄され得、例えば、イテレーション０にロールバックされ得る。Ｘの共通レジスタの使用は、ループ２１０の投機的イテレーションにおける不必要な依存性を作り出し得る。
【００１３】
複数のイテレーションが並列して実行されるので、例えば、特定のイテレーションにおいて信頼できる割り当て値をレジスタＸが保持するサイクル／段の範囲といった、レジスタＸの「ライフタイム」は、他のイテレーションにおけるレジスタＸの１以上のライフタイムとオーバーラップし得る。実行中にオーバーラップするイテレーション間の依存性を回避するために、レジスタＸは、「リネーム」され得、スケジュール２４０に示されるように、例えば、各イテレーションにおいて異なる名前を有する置換レジスタに割り当てられ得る。各ライフタイムは、３つのイテレーションに及び、したがって、Ｘのライフタイムの３つの異なるインスタンス（Ｘ０、Ｘ１、及びＸ２）が使用される。各イテレーションにおけるＸｉのライフタイムが、例えば、Ｘ０のライフタイム２４２（イテレーション０）、Ｘ１のライフタイム２４４（イテレーション１）、Ｘ２のライフタイム２４６（イテレーション２）、Ｘ０のライフタイム２４８（イテレーション３）、及びＸ１のライフタイム２５０（イテレーション４）として示されている。
【００１４】
パイプラインスケジュール２４０に示される例において、ループは、３つのイテレーションごとに１回、条件付きでコミットする（例えば、条件付きコミット）。スケジュール２４０に示されるように、例外（例えばオーバーフロー例外）が、例えば、サイクル９の終了時におけるコミットといった、コミットポイントの前に、イテレーション３のサイクル９において発生する。本発明の実施形態は、予期せぬ挙動がパイプラインループにおいて発生したとき、完全なロールバックを回避することにより、破棄されるワーク（work）を低減させることを意図するものである。
【００１５】
一般に、パイプラインスケジューリングに関連する問題は、以下のように定式化され得る。
Ｓ：１つのイテレーションにおける段の総数
Ｅ：例外、メモリフォールト、投機失敗、及びサイドイグジット等の、アトミック領域においてロールバックを必要とする予期せぬ挙動
Ｎ：Ｅが発生するイテレーションカウント（０から始まる）
Ｍ：Ｅが発生するイテレーション内の段数（０から始まる）
Ｅが（イテレーション＝Ｎ、段＝Ｍ）において発生したとき、イテレーション（Ｎ−Ｓ＋Ｍ）は終了している。イテレーション（Ｎ−Ｓ＋Ｍ）の終了時における状態を回復させ、コミットを行うのが望ましい。イベントＥが処理され得、ループの実行が、イテレーション（Ｎ−Ｓ＋Ｍ＋１）から始まるよう再開され得る。
【００１６】
予期せぬ挙動が、ソフトウェアパイプラインループの実行中に発生したとき、生成されたコードは、コミットポイントを特定できるように、最も直近に終了したイテレーションを回復させることができ得る。この回復を実現するために、２つのマシン状態、すなわち、レジスタ状態（Ｘ０、Ｘ１、Ｘ２）及びメモリ状態（ＳＴＯＲＥ）が回復される。
【００１７】
レジスタ状態の回復
「ループバックエッジ（loop  back  edge）」にわたってライブ（live）であるレジスタ及び「ライブアウトレジスタ（live-out  register）」が対象とされる。レジスタに割り当てられた値は、その値を待っている、実行される命令が存在する場合、「ライブ」であるとみなされ得、したがって、その値は、レジスタ内に保持され、実行される命令により利用可能である。「ループバックエッジ」とは、ループイテレーションの終了ポイントを指し、ループの次のイテレーションの開始ポイントでもある。「ループバックエッジにわたってライブである」レジスタ値Ｑとは、連続するイテレーションにわたってライブであるレジスタ（例えばレジスタＲ）に割り当てられた値を指し、連続するイテレーションにわたってライブであるとは、例えば、第１のイテレーションが終了した後に、次のイテレーションにおいてレジスタＲに記憶された値Ｑを用いる場合等である。「ライブアウトレジスタ」とは、ループが終了した後にループ外の演算により用いられる値が割り当てられたレジスタを指す。全ての他のレジスタ（例えば、「ライブアウトである」値又は「ループバックエッジにわたってライブである」値が割り当てられていないレジスタ）は、コミットが終了した後にループが実行を再開するときに、再初期化され得る。このような「ライブアウトレジスタ」及び／又は「ループバックエッジにわたってライブであるレジスタ」に関して、前に終了したイテレーション（例えば、現在実行中のイテレーション２の前に終了した、スケジュール２４０におけるイテレーション１）からの値が、例えばサイクル８〜９において例外が発生したときに、アライブ（alive）のまま保たれることになる。前のイテレーション（例えばイテレーション１）からの値は、各イテレーションにおいてある段（例えば、２つのサイクル）だけ各ライブアウトレジスタのライブ範囲（live  range）を拡張して、Ｘ個のレジスタの各々をリネームする（例えば、Ｘ個のレジスタの各々を、対応する名前を有する独立したレジスタで置換する）ことにより、アライブのまま保たれ得る。
【００１８】
リネームされたライブアウトレジスタの延ばされたライフタイムが、スケジュール２６０に示されている。追加の段２６４を加えてライフタイム２４４をライフタイム２７４に延ばすことにより、Ｘ１の値は、サイクル８〜９において利用可能なままとなる。スケジュール２６０において、イテレーション３のＸのレジスタは、Ｘ３にリネームされており、これにより、イテレーション１からのＸ１の値が、サイクル９の終了時まで維持されることが可能になるので、イテレーション３（サイクル９）において乗算演算に関連する例外が発生した場合、Ｘ１に割り当てられた値を使用することにより、イテレーション１のレジスタ状態を回復させることができることに留意されたい。
【００１９】
メモリ状態の回復
ストア演算が、メモリに対して最終的な影響を及ぼすので（例えば、アトミック領域全体がロールバックされない限り回復可能でない）、現在のカーネル中に実行される全てのストア演算は、投機的イテレーションからではなく、非投機的イテレーション（例えば、現在のカーネルが実行されるときに終了している最も直近のイテレーション）からもたらされるべきである。パイプラインスケジューラは、スケジュールの最後の段における全てのストアを保つ、例えば、パイプラインスケジューラは、ストアを投機しない。したがって、全てのストアが、イテレーションの最後の段においてスケジュールされると想定され得る。現在のカーネル（２４０におけるサイクル８〜９）が実行されるとき、ストア演算は、イテレーション２からもたらされており、イテレーション２は終了していないので、イテレーション２は、投機的イテレーションである。最も直近に終了したイテレーションは、イテレーション１であり、これは、非投機的である。したがって、スケジュール２６０に示されるように、１つの段（例えば、２６２、２６６、２６８、２７０、２７２）を各イテレーションに追加することにより、ストアが遅延され得る。追加の段により、現在の段（例えば段５）において実行される全てのストアが、非投機的イテレーションからのものとなる。現在のカーネル（サイクル８〜９）において、イテレーション１は、ストア演算を除いて適切に終了している。予期せぬ挙動（例えば例外）が発生した場合、ストア演算を再実行して、イテレーション１を終了させることができる。一般化すると、イテレーションＮにおける段Ｍでの例外は、イテレーション（Ｎ−Ｓ＋Ｍ）の結果の回復及びコミットをトリガし得る（イテレーション１におけるストア演算が、メモリフォールトを生じさせた場合、イテレーション１の結果は回復できず、イテレーション０の最後のコミットポイントにロールバックされ、イテレーション０から実行が再開する）。
【００２０】
拡張段挿入
１及び２の組合せは、ライブアウトレジスタ及びストア演算のための各スケジュールの最後に拡張段（例えば、段２６２、２６６、２６８、２７０、２７２）を挿入することにより機能し得る。ロールバックが生じるときに、非投機的イテレーションのための拡張段の実行が終了する。
【００２１】
ランタイムサポート
メモリフォールト及び例外を処理するランタイムコードは、本明細書で説明するコード生成技術をサポートすることができる。例外が発生したときに、例外ハンドラを実行して、例外を処理することができる。例外ハンドラの実行後、最後の非投機的イテレーションの状態を回復させる補償コードブロックが実行され得る。この補償コードブロックは、スケジュール２６０における拡張段（例えば、２６４）の実行を含み得、また、例えば、Ｘ０、Ｘ１、Ｘ２、Ｘ３（これらの全てがサイクル９においてライブである）といった元のライブアウトレジスタ値の回復を含み得る。例２６０において、補償コードブロックの実行は、レジスタＸへのレジスタＸ３の内容のコピーを含む。なぜならば、リネームされたレジスタＸ０〜Ｘ３は、パイプラインループの内部にあるからである。補償コードブロックは、イテレーションごとに異なり得、各補償コードブロックの実行は、レジスタＸ０、Ｘ１、Ｘ２、Ｘ３のうちの１つの内容をレジスタＸにコピーし得る（例えば、図２におけるサイクル９において発生した例外に関しては、イテレーション１の補償ブロックが実行され得、この補償ブロックが、Ｘ１をＸにコピーする）。補償ブロックの実行後、コミットを実行して、前に終了したイテレーション（例えば、スケジュール２６０におけるイテレーション１）の結果を記録することができる。
【００２２】
図３は、本発明の１以上の実施形態に従った、ループの演算をスケジュールする方法のフロー図である。ブロック３０２において、ループのパイプラインスケジュールが、コンパイル時に、パイプラインスケジューラから受信される。ブロック３０４に進み、レジスタ（例えばＸ）を、周期的に割り当てられることになる複数のレジスタ（例えば、図２の２６０におけるＸ０、Ｘ１、Ｘ２、Ｘ３）のうちの１つにリネームするといったモジュロ変数展開が、コンパイル時に実行される。ブロック３０６に進み、追加の段が、コンパイル時に追加され得る。追加の段は、例えば、１以上のストアが追加の段に遅延されシフトされ得る、ループの変更されたパイプラインスケジュールを形成するための、ループのパイプラインスケジュールの各イテレーションにおける１以上の「無演算（no-op）」を含む。ブロック３０６において、さらに、補償コード（「補償ブロック」）が、ループコードに追加される。ブロック３０８に進み、ループの変更されたパイプラインスケジュールが、ランタイムに実行され得る。判断菱形３１０に進み、ループの実行が終了している（例えば、例外がない）場合、方法は３２０で終了する。ループの実行が終了していない場合、判断菱形３１２に進み、例外が検出されない場合には、変更されたパイプラインスケジュールの実行が、ブロック３０８において継続する。例外が発生した場合、ブロック３１４に進み、例外に応答して、例外ハンドラが、ランタイムに実行される。ブロック３１６に進み、コードの補償ブロックが、ランタイムに実行され得、実行されなかった任意の遅延されたストアの実行を終了させ、最終値をレジスタＸに返す。ブロック３１８に進み、最も直近に終了したイテレーションがコミットされる。方法は３２０で終了する。
【００２３】
次に図４を参照すると、本発明の一実施形態に従ったプロセッサのブロック図が示されている。図４に示されるように、プロセッサ４００は、コアドメイン４１０内に複数のコア４１０ａ〜４１０ｎを含むマルチコアプロセッサとすることができる。これらのコアのうちの１以上は、例えば例外からの回復の際の効率を上げるための、本発明の実施形態に従ってパイプラインスケジュールにおけるループの各イテレーションに段を追加する段挿入ロジック（例えば、４１２ａ、４１２ｂ．．．４１２ｎ）を含み得る。本発明の実施形態において、段挿入ロジックは、ソフトウェア、ファームウェア、ハードウェア、又はこれらの組合せとして実装され得る。
【００２４】
これらのコアは、インターコネクト４１５を介して、様々なコンポーネントを含むシステムエージェント又はアンコア４２０に接続され得る。図示されるように、アンコア４２０は、最終レベルキャッシュであり得、且つキャッシュコントローラ４３２を含む共有キャッシュ４３０を含み得る。加えて、アンコアは、統合メモリコントローラ４４０及び様々なインタフェース４５０を含み得る。
【００２５】
図４をさらに参照すると、プロセッサ４００は、例えばメモリバスを介して、システムメモリ４６０と通信することができる。加えて、インタフェース４５０を介して、周辺デバイス、大容量ストレージ等の様々なオフチップコンポーネントに対して接続を行うことができる。図４の実施形態ではこの特定の実装で示されているが、本発明の範囲は、この点に限定されるものではない。
【００２６】
図５を参照すると、複数のコアを含むプロセッサの一実施形態が示されている。プロセッサ５００は、マイクロプロセッサ、組み込みプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、ネットワークプロセッサ、ハンドヘルドプロセッサ、アプリケーションプロセッサ、コプロセッサ、システムオンチップ（ＳＯＣ）、又はコードを実行する他のデバイス等の、任意のプロセッサ又は処理デバイスを含む。一実施形態において、プロセッサ５００は、少なくとも２つのプロセッサ（コア５０１及び５０２）を含み、これらのコアは、非対称コア又は対称コア（図示される実施形態）を含み得る。しかしながら、プロセッサ５００は、対称であっても非対称であってもよい任意の数の処理エレメントを含んでもよい。
【００２７】
一実施形態において、処理エレメントとは、ソフトウェアスレッドをサポートするハードウェア又はロジックを指す。ハードウェア処理エレメントの例は、実行状態又はアーキテクチャ状態等のプロセッサの状態を保持することができる、スレッドユニット、スレッドスロット、スレッド、プロセスユニット、コンテキスト、コンテキストユニット、論理プロセッサ、ハードウェアスレッド、コア、及び／又は任意の他のエレメントを含む。すなわち、一実施形態において、処理エレメントとは、ソフトウェアスレッド、オペレーティングシステム、アプリケーション、又は他のコード等の、独立してコードに関連付けることができる任意のハードウェアを指す。物理プロセッサとは、通常、コア又はハードウェアスレッド等の任意の数の他の処理エレメントを潜在的に含む集積回路を指す。
【００２８】
コアとは、しばしば、独立したアーキテクチャ状態を維持することができる集積回路上に位置するロジックであって、各独立して維持されるアーキテクチャ状態は、少なくともいくつかの専用実行リソースに関連付けられている、ロジックを指す。コアとは対照的に、ハードウェアスレッドとは、通常、独立したアーキテクチャ状態を維持することができる集積回路上に位置する任意のロジックであって、独立して維持されるアーキテクチャ状態は、実行リソースに対するアクセスを共有する、ロジックを指す。理解され得るように、所定のリソースが共有され、他のリソースがあるアーキテクチャ状態に専用であるとき、ハードウェアスレッドの命名（nomenclature）とコアの命名との間の境界線はオーバーラップする。しかしながら、しばしば、コア及びハードウェアスレッドは、オペレーティングシステムにより、別個の論理プロセッサとしてみなされ、オペレーティングシステムは、各論理プロセッサ上の演算を個別にスケジュールすることができる。
【００２９】
図５に示されるように、物理プロセッサ５００は、２つのコア（コア５０１及び５０２）を含む。ここで、コア５０１及び５０２は、対称コア（すなわち、同じ構成、機能ユニット、及び／又はロジックを有するコア）とみなされる。別の実施形態において、コア５０１は、アウトオブオーダプロセッサコア（out-of-order  processor  core）を含むのに対し、コア５０２は、インオーダプロセッサコア（in-of-order  processor  core）を含む。しかしながら、コア５０１及び５０２は、任意のタイプのコア、例えば、ネイティブコア、ソフトウェア管理コア（software  managed  core）、ネイティブ命令セットアーキテクチャ（ＩＳＡ）を実行するよう適合されたコア、変換されたＩＳＡを実行するよう適合されたコア、共同設計されたコア、又は他の既知のコアから個々に選択されてもよい。説明をさらに進めるために、コア５０１内に示される機能ユニットについて、以下でさらに詳細に説明する（コア５０２内のユニットも同様に動作する）。
【００３０】
図示されるように、コア５０１は、２つのハードウェアスレッド５０１ａ及び５０１ｂを含む。これらは、ハードウェアスレッドスロット５０１ａ及び５０１ｂと呼ばれてもよい。したがって、一実施形態において、オペレーティングシステム等のソフトウェアエンティティは、潜在的に、プロセッサ５００を、４つのソフトウェアスレッドを同時に実行することができる４つの別個のプロセッサ、すなわち、４つの論理プロセッサ又は処理エレメントとしてみなす。上記で示唆したように、第１のスレッドは、アーキテクチャ状態レジスタ５０１ａに関連付けられ、第２のスレッドは、アーキテクチャ状態レジスタ５０１ｂに関連付けられ、第３のスレッドは、アーキテクチャ状態レジスタ５０２ａに関連付けられ得、第４のスレッドは、アーキテクチャ状態レジスタ５０２ｂに関連付けられ得る。ここで、上述したように、アーキテクチャ状態レジスタの各々（５０１ａ、５０１ｂ、５０２ａ、及び５０２ｂ）は、処理エレメント、スレッドスロット、又はスレッドユニットと呼ばれてもよい。例示されるように、アーキテクチャ状態レジスタ５０１ａは、アーキテクチャ状態レジスタ５０１ｂに複製されるので、個々のアーキテクチャ状態／コンテキストは、論理プロセッサ５０１ａ及び論理プロセッサ５０１ｂのために記憶することができる。コア５０１では、アロケータ及びリネーマブロック５３０における命令ポインタ及びリネーミングロジック等の他のより小さなリソースも、スレッド５０１ａ及び５０１ｂのために複製され得る。リオーダ／リタイヤメントユニット５３５におけるリオーダバッファ、ＩＬＴＢ５２０、ロード／ストアバッファ、及びキュー等のいくつかのリソースも、パーティショニング（partitioning）により共有され得る。汎用内部レジスタ、ページテーブルベースレジスタ、下位レベルデータキャッシュ及びデータＴＬＢ５１５、実行ユニット５４０、及びアウトオブオーダユニット５３５の一部等の他のリソースも、潜在的に完全に共有される。
【００３１】
プロセッサ５００は、完全に共有され得る、パーティショニングにより共有され得る、あるいは、処理エレメントにより／処理エレメントに専用され得る、他のリソースをしばしば含む。図５において、プロセッサの例示的な論理ユニット／リソースを有する純粋に例示的なプロセッサの一実施形態が示されている。プロセッサは、これらの機能ユニットのいずれかを含んでも省いてもよく、図示されていない任意の他の既知の機能ユニット、ロジック、又はファームウェアを含んでもよい。図示されるように、コア５０１は、簡略化された代表的なアウトオブオーダ（ＯＯＯ）プロセッサコアを含む。しかしながら、異なる実施形態では、インオーダプロセッサが使用されてもよい。ＯＯＯコアは、実行される／取られる分岐を予測する分岐ターゲットバッファ５２０と、命令のためのアドレス変換エントリを記憶する命令変換バッファ（Ｉ−ＴＬＢ）５２０と、を含む。
【００３２】
コア５０１は、フェッチユニット５２０に接続された、フェッチされたエレメントをデコードするデコードモジュール５２５をさらに含む。一実施形態において、フェッチロジックは、スレッドスロット５０１ａ、５０１ｂにそれぞれ関連付けられた別個のシーケンサを含む。通常、コア５０１は、プロセッサ５００上で実行可能な命令を定義／指定する第１のＩＳＡに関連付けられている。しばしば、第１のＩＳＡの一部分であるマシンコード命令は、実行される命令又は演算を参照／指定する、命令の一部分（オペコードと呼ばれる）を含む。デコードロジック５２５は、これら命令を、これらのオペコードから認識して、デコードされた命令を、第１のＩＳＡにより定義されたように処理するためにパイプラインへと渡す回路を含む。例えば、一実施形態において、デコーダ５２５は、トランザクション命令等の特定の命令を認識するよう設計又は適合されたロジックを含む。デコーダ５２５による認識の結果として、アーキテクチャ又はコア５０１は、特定の予め定められたアクションを取り、適切な命令に関連付けられたタスクを実行する。いくつかが新しい命令であっても古い命令であってもよい１以上の命令に応じて、本明細書で説明したタスク、ブロック、演算、及び方法のいずれかを実行できることに留意することは重要である。
【００３３】
一例において、アロケータ及びリネーマブロック５３０は、命令処理結果を記憶するレジスタファイル等のリソースを予約するアロケータを含む。しかしながら、スレッド５０１ａ及び５０１ｂは、潜在的にアウトオブオーダ実行が可能であり、アロケータ及びリネーマブロック５３０は、命令結果を追跡するためのリオーダバッファ等の他のリソースも予約する。ユニット５３０はまた、プログラム／命令参照レジスタを、プロセッサ５００内部の他のレジスタにリネームするレジスタリネーマを含み得る。リオーダ／リタイヤメントユニット５３５は、アウトオブオーダ実行と、アウトオブオーダ実行後の命令のインオーダリタイヤメントと、をサポートするための、上述したリオーダバッファ、ロードバッファ、及びストアバッファ等のコンポーネントを含む。
【００３４】
一実施形態において、スケジューラ及び実行ユニットブロック５４０は、実行ユニット上での命令／演算をスケジュールするスケジューラユニットを含む。例えば、スケジューラユニットは、パイプラインスケジュールに従って、ループの演算をスケジュールすることができる。情報命令処理結果を記憶するための、実行ユニットに関連付けられたレジスタファイルがさらに含まれる。例示的な実行ユニットは、浮動小数点実行ユニット、整数実行ユニット、ジャンプ実行ユニット、ロード実行ユニット、ストア実行ユニット、及び他の既知の実行ユニットを含む。
【００３５】
コア５０１及び５０２のうちの一方又は双方が、本発明の実施形態に従ってパイプラインスケジュールループの各イテレーションに追加の段を挿入するコード生成ロジック（５４２、５４６）を含み得る。コード生成ロジック（５４２、５４６）はまた、本発明の実施形態に従って、ループイテレーションの変数が割り当てられた１以上のレジスタをリネームすることができる。
【００３６】
下位レベルデータキャッシュ及びデータ変換バッファ（Ｄ−ＴＬＢ）５５１が、実行ユニット５４０に接続される。Ｄ−ＴＬＢ５５１は、最近の仮想／線形からの物理アドレス変換を記憶するためのものである。具体例として、プロセッサは、物理メモリを複数の仮想ページに分割するためのページテーブル構造を含み得る。
【００３７】
ここで、コア５０１及び５０２は、最近フェッチされたエレメントをキャッシュする上位レベル又はさらに外側の（further-out）キャッシュ５１０へのアクセスを共有する。上位レベル又はさらに外側とは、増加する、あるいは実行ユニットからさらに離れるキャッシュレベルを指す。一実施形態において、上位レベルキャッシュ５１０は、最終レベルデータキャッシュ、すなわち、プロセッサ５００におけるメモリ階層の最終キャッシュであり、例えば、第２レベルデータキャッシュ又は第３レベルデータキャッシュである。しかしながら、上位レベルキャッシュ５１０は、そのように限定されるものではなく、命令キャッシュに関連付けられてもよいし、命令キャッシュを含んでもよい。命令キャッシュの一種であるトレースキャッシュが、代わりに、最近デコードされたトレースを記憶するために、デコーダ５２５の後に接続されてもよい。
【００３８】
図示される構成において、プロセッサ５００はまた、バスインタフェースモジュール５０５を含む。歴史的には、コントローラ５７０が、プロセッサ５００外部のコンピューティングシステムに含まれていた。このシナリオでは、バスインタフェース５０５が、プロセッサ５００外部のデバイス、例えば、システムメモリ５７５、チップセット（メモリ５７５に接続するためのメモリコントローラハブと、周辺デバイスに接続するためのＩ／Ｏコントローラハブと、をしばしば含む）、メモリコントローラハブ、ノースブリッジ、又は他の集積回路と通信する。また、このシナリオでは、バス５０５が、マルチドロップバス、ポイントツーポイントインターコネクト、シリアルインターコネクト、パラレルバス、コヒーレントな（例えばキャッシュコヒーレントな）バス、レイヤ化されたプロトコルアーキテクチャ、差動バス、及びＧＴＬバス等の任意の既知のインターコネクトを含み得る。
【００３９】
メモリ５７５は、プロセッサ５００に専用であってもよいし、システム内の他のデバイスと共有されてもよい。メモリ５７５のタイプの一般的な例は、ＤＲＡＭ、ＳＲＡＭ、不揮発性メモリ（ＮＶメモリ）、及び他の既知の記憶デバイスを含む。デバイス５８０は、グラフィックアクセラレータ、メモリコントローラハブに接続されるプロセッサ又はカード、Ｉ／Ｏコントローラハブに接続されるデータストレージ、無線トランシーバ、フラッシュデバイス、オーディオコントローラ、ネットワークコントローラ、又は他の既知のデバイスを含んでもよいことに留意されたい。
【００４０】
しかしながら、図示される実施形態では、コントローラ５７０が、プロセッサ５００の一部として示されていることに留意されたい。近年、より多くのロジック及びデバイスが、ＳＯＣ等の単一のダイ上に集積されるようになるにつれて、これらデバイスの各々が、プロセッサ５００に組み込まれ得るようになっている。例えば、一実施形態において、メモリコントローラハブ５７０は、プロセッサ５００と同じパッケージ及び／又はダイ上に存在する。ここで、コアの一部分（オンコア部分）は、メモリ５７５又はグラフィックスデバイス５８０等の他のデバイスとインタフェースをとるための１以上のコントローラ５７０を含む。そのようなデバイスとインタフェースをとるためのインターコネクト及びコントローラを含む構成は、しばしば、オンコア（又はアンコア構成）と呼ばれる。一例として、バスインタフェース５０５は、メモリ５７５とインタフェースをとるためのメモリコントローラと、グラフィックスデバイス５８０とインタフェースをとるためのグラフィックスコントローラと、を有するリングインターコネクトを含む。しかしながら、ＳＯＣ環境では、高機能及び低電力消費を有するスモールフォームファクタを提供するために、さらに多くのデバイス、例えば、ネットワークインタフェース、コプロセッサ、メモリ５７５、グラフィックスデバイス５８０、及び任意の他の既知のコンピュータデバイス／インタフェースが、単一のダイ又は集積回路上に集積されてもよい。
【００４１】
実施形態は、多くの異なるシステムタイプに実装され得る。次に図６を参照すると、本発明の一実施形態に従ったシステムのブロック図が示されている。図６に示されるように、マルチプロセッサシステム６００は、ポイントツーポイントインターコネクトシステムであり、ポイントツーポイントインターコネクト６５０を介して接続された第１のプロセッサ６７０及び第２のプロセッサ６８０を含む。図６に示されるように、プロセッサ６７０及び６８０の各々は、マルチコアプロセッサとすることができ、第１のプロセッサコア及び第２のプロセッサコア（すなわち、プロセッサコア６７４ａ及び６７４ｂ並びにプロセッサコア６８４ａ及び６８４ｂ）を含むが、潜在的により多くのコアがプロセッサ内に存在してもよい。
【００４２】
引き続き図６を参照すると、第１のプロセッサ６７０は、メモリコントローラハブ（ＭＣＨ）６７２並びにポイントツーポイント（Ｐ−Ｐ）インタフェース６７６及び６７８をさらに含む。同様に、第２のプロセッサ６８０は、ＭＣＨ６８２並びにＰ−Ｐインタフェース６８６及び６８８を含む。図６に示されるように、ＭＣＨ６７２及び６８２は、プロセッサを、それぞれのメモリ、すなわち、メモリ６３２及びメモリ６３４に接続する。これらは、それぞれのプロセッサにローカルに接続されたシステムメモリ（例えばＤＲＡＭ）の一部であってよい。プロセッサ６７０及び６８０の各々は、本発明の実施形態に従ってパイプラインスケジュールループの各イテレーションに追加の段を挿入する段挿入ロジック（図示せず）を含み得、本発明の実施形態に従って、パイプラインスケジュールループの各イテレーションに関連付けられたレジスタをリネームするモジュロ変数展開ロジックをさらに含み得る。追加の段は、ループの全ての結果を破棄するよりも、例外からのより効率的な回復を可能にし得る。より効率的な回復は、本発明の実施形態に従ったライブアウト変数（例えば、ループ外で使用される、ループ内で生成された値を有する変数）の延ばされたライフタイムに少なくとも部分的に起因し得る。プロセッサはまた、本発明の実施形態に従って、リネームされたレジスタに記憶された値を回復させ、ストア演算を終了させる補償ロジックを含み得る。第１のプロセッサ６７０及び第２のプロセッサ６８０は、Ｐ−Ｐインターコネクト６６２及び６５４をそれぞれ介して、チップセット６９０に接続され得る。図６に示されるように、チップセット６９０は、Ｐ−Ｐインタフェース６９４及び６９８を含む。
【００４３】
さらに、チップセット６９０は、Ｐ−Ｐインターコネクト６３９を介してチップセット６９０を高性能グラフィックスエンジン６３８に接続するインタフェース６９２を含む。同様に、チップセット６９０は、インタフェース６９６を介して第１のバス６１６に接続され得る。図６に示されるように、様々な入力／出力（Ｉ／Ｏ）デバイス６１４が、第１のバス６１６を第２のバス６２０に接続するバスブリッジ６１８とともに、第１のバス６１６に接続され得る。一実施形態において、例えば、キーボード／マウス６２２、通信デバイス６２６、及びデータ記憶ユニット６２８（コード６３０を含み得るディスクドライブ又は他の大容量記憶デバイス等）を含む様々なデバイスが、第２のバス６２０に接続され得る。さらに、オーディオＩ／Ｏ６２４が、第２のバス６２０に接続され得る。実施形態は、スマート携帯電話機、ウルトラブック（登録商標）、タブレットコンピュータ、ネットブック等のモバイルデバイスを含む他のタイプのシステムに組み込むことができる。
【００４４】
以下の例は、さらなる実施形態に関する。
【００４５】
第１の例において、システムは、ループの演算を実行する少なくとも１つのコアと、前記ループの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、前記レジスタの内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入手段と、を含むプロセッサを含む。当該システムは、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）をさらに含む。前記プロセッサは、任意的に、前記レジスタを第２のレジスタにリネームするモジュロ変数展開ロジックを含む。前記モジュロ変数展開ロジックは、さらに、前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタにリネームすることができる。前記プロセッサは、任意的に、前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償ロジックであって、前記ループの各イテレーションはＳ個の段を含む、補償ロジックを含む。前記補償ロジックは、前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションにおける前記レジスタのライブアウト値を回復させることができる。前記プロセッサは、任意的に、前記ストア演算の再実行及び前記レジスタの前記ライブアウト値の回復の前に前記例外を処理するハンドラロジックを含む。前記プロセッサは、任意的に、前記例外に応答して、（Ｎ−Ｓ＋Ｍ＋１）番目のイテレーションから始まるよう前記ループの実行を再開する。前記プロセッサは、任意的に、実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットする。
【００４６】
第２の例において、少なくとも１つのコンピュータ読み取り可能媒体は命令を含み、前記命令は、実行されたときに、システムが、パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信することを可能にする。前記ループの各イテレーションは、レジスタに変数のそれぞれの値を割り当てるそれぞれの割り当て演算と、前記イテレーションにおいて決定された値をメモリに記憶させるそれぞれのストア演算と、を含み得る。前記命令は、実行されたときに、前記システムが、前記それぞれのストア演算の実行を遅延させ、且つ、各イテレーションにおける前記レジスタのそれぞれのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入することを可能にし得る。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、前記ループの第１のイテレーションの前記変数の値が割り当てられる、第１のレジスタ名を有する第１のレジスタを、第２のレジスタ名を有する第２のレジスタで置換するモジュロ変数展開命令を含んでもよい。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、複数のイテレーションの各イテレーションにおいて、前記第１のレジスタ名を有する前記第１のレジスタを、対応する異なるレジスタ名を有する対応する異なるレジスタに置換する命令を含んでもよい。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションの第１のストア演算を再実行する命令であって、前記ループの各イテレーションはＳ個の段を含む、命令を含んでもよい。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させる命令を含んでもよい。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、前記第１のレジスタの前記ライブアウト値の回復の前に前記例外を処理する命令を含んでもよい。当該少なくとも１つのコンピュータ読み取り可能媒体は、任意的に、実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットする命令を含んでもよい。
【００４７】
第３の例において、方法は、パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信するステップを含む。各イテレーションは、レジスタに前記イテレーションに関連付けられた変数の値を割り当てる割り当て演算と、前記レジスタの内容をメモリに記憶させるそれぞれのストア演算と、を含む。当該方法は、前記それぞれのストア演算の実行を遅延させ、且つ、それぞれの前記イテレーションにおける前記レジスタのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入するステップをさらに含む。当該方法は、任意的に、第１のイテレーションにおける前記変数に関連付けられた前記レジスタを、第１のレジスタ名から第１の置換レジスタに置換し、前記第１の置換レジスタを、前記ループの後続のイテレーションにおける前記変数に再割り当てするステップを含んでもよい。当該方法は、任意的に、特定のイテレーションにおいて発生した例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットするステップを含んでもよい。当該方法は、任意的に、特定のイテレーションにおいて発生した例外に応答して、ハンドラコードの実行を介して前記例外を処理するステップをさらに含んでもよい。当該方法は、任意的に、前記ループの最も直近に終了したイテレーションをコミットし、前記最も直近に終了したイテレーションから始まるよう前記ループの実行を再開するステップを含んでもよい。
【００４８】
第４の例において、ループを実行するプロセッサは、ループの演算を実行する少なくとも１つのコアと、前記ループの第１のイテレーションの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、前記レジスタの内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入ロジックと、を含む。当該プロセッサは、任意的に、前記レジスタを第２のレジスタにリネームする、あるいは、前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタにリネームするリネーミングロジックを含んでもよい。当該プロセッサは、任意的に、前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償ロジックであって、各イテレーションはＳ個の段を含む、補償ロジックを含んでもよい。当該プロセッサは、任意的に、前記補償ロジックが前記ストア演算を再実行する前に前記例外を処理するハンドラロジックを含んでもよい。前記補償ロジックは、任意的に、前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させてもよい。当該プロセッサは、前記例外に応答して、最も直近に終了したイテレーションから始まるよう前記ループの実行を再開することができる。当該プロセッサは、任意的に、実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットしてもよい。
【００４９】
実施形態は、多くの異なるタイプのシステムにおいて用いることができる。例えば、一実施形態において、通信デバイスが、本明細書で説明した様々な方法及び技術を実行するよう構成され得る。もちろん、本発明の範囲は、通信デバイスに限定されるものではなく、代わりに、他の実施形態は、命令を処理するための他のタイプの装置、又は、コンピューティングデバイス上で実行されたことに応じて、コンピューティングデバイスに、本明細書で説明した方法及び技術のうちの１以上を実行させる命令を含む１以上のマシン読み取り可能媒体を対象とし得る。
【００５０】
実施形態は、コードにより実装されてもよく、命令を記憶した非一時的な記憶媒体に記憶されてもよい。そのようなコードを使用して、命令を実行するようシステムをプログラムすることができる。記憶媒体は、フロッピディスク、光ディスク、ソリッドステートドライブ（ＳＳＤ）、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、コンパクトディスクリライタブル（ＣＤ−ＲＷ）、光磁気ディスク、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、消去可能なプログラム可能な読み取り専用メモリ（ＥＰＲＯＭ）、フラッシュメモリ、電気的に消去可能なプログラム可能な読み取り専用メモリ（ＥＥＰＲＯＭ）等の読み取り専用メモリ（ＲＯＭ）及びランダムアクセスメモリ（ＲＡＭ）等の半導体デバイス、磁気カード、光カード、又は電子的命令を記憶するのに適した任意の他のタイプの媒体を含み得るが、これらに限定されるものではない。
【００５１】
限定された数の実施形態を参照して本発明について説明したが、当業者は、これら実施形態からの多数の変更形態及び変形形態を理解するであろう。添付の請求項は、本発明の真の主旨及び範囲内に属する全てのそのような変更形態及び変形形態をカバーすることが意図されている。
【図１】
2016519375.tif 000003
【図２】
2016519375.tif 000004
【図３】
2016519375.tif 000005
【図４】
2016519375.tif 000006
【図５】
2016519375.tif 000007
【図６】
2016519375.tif 000008
【手続補正書】
【提出日】平成27年11月9日(2015.11.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ループの演算を実行する少なくとも１つのコアと、
前記ループの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、前記レジスタの内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入手段と、
を含むプロセッサと、
ダイナミックランダムアクセスメモリ（ＤＲＡＭ）と、
を備えたシステム。
【請求項２】
前記プロセッサは、前記レジスタを第２のレジスタにリネームするモジュロ変数展開手段をさらに含む、請求項１記載のシステム。
【請求項３】
前記モジュロ変数展開手段は、さらに、前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタにリネームする、請求項２記載のシステム。
【請求項４】
前記プロセッサは、実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットする、請求項１乃至３いずれか一項記載のシステム。
【請求項５】
前記プロセッサは、前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償手段であって、各イテレーションはＳ個の段を含む、補償手段をさらに含む、請求項１記載のシステム。
【請求項６】
前記補償手段は、さらに、前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた前記レジスタのライブアウト値を回復させる、請求項５記載のシステム。
【請求項７】
前記プロセッサは、前記補償手段による前記ストア演算の再実行及び前記レジスタの前記ライブアウト値の回復の前に前記例外を処理するハンドラ手段をさらに含む、請求項６記載のシステム。
【請求項８】
前記プロセッサは、さらに、前記例外に応答して、（Ｎ−Ｓ＋Ｍ＋１）番目のイテレーションから始まるよう前記ループの実行を再開する、請求項７記載のシステム。
【請求項９】
システムに、
パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信させ、ここで、前記ループの各イテレーションは、レジスタに変数のそれぞれの値を割り当てるそれぞれの割り当て演算と、前記イテレーションにおいて決定された値をメモリに記憶させるそれぞれのストア演算と、を含み、
前記それぞれのストア演算の実行を遅延させ、且つ、各イテレーションにおける前記レジスタのそれぞれのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入させる、
コンピュータプログラム。
【請求項１０】
前記システムに、さらに、
前記ループの第１のイテレーションの前記変数の値が割り当てられる、第１のレジスタ名を有する第１のレジスタを、第２のレジスタ名を有する第２のレジスタで置換させる、請求項９記載のコンピュータプログラム。
【請求項１１】
前記システムに、さらに、
複数のイテレーションの各イテレーションにおいて、対応するレジスタを、前記第１のレジスタ名を有する前記第１のレジスタから、対応する異なるレジスタ名を有する対応する異なるレジスタに置換させる、請求項１０記載のコンピュータプログラム。
【請求項１２】
前記システムに、さらに、
実行されている現在のイテレーションにおける例外に応答して、前記ループの最も直近に終了したイテレーションの結果をコミットさせる、請求項９乃至１１いずれか一項記載のコンピュータプログラム。
【請求項１３】
前記システムに、さらに、
前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションの第１のストア演算を再実行させ、ここで、前記ループの各イテレーションはＳ個の段を含む、請求項９記載のコンピュータプログラム。
【請求項１４】
前記システムに、さらに、
前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させる、請求項１３記載のコンピュータプログラム。
【請求項１５】
前記システムに、さらに、
前記第１のレジスタの前記ライブアウト値の回復の前に前記例外を処理させる、請求項１４記載のコンピュータプログラム。
【請求項１６】
パイプラインスケジュールに従って並列して実行される複数のイテレーションを含むループの前記パイプラインスケジュールを受信するステップであって、各イテレーションは、レジスタに前記イテレーションに関連付けられた変数の第１の値を割り当てる割り当て演算と、前記イテレーションの実行から決定された第２の値をメモリに記憶させるストア演算と、を含む、ステップと、
それぞれの前記ストア演算の実行を遅延させ、且つ、それぞれの前記イテレーションにおける前記レジスタのライフタイムを延ばすために、前記パイプラインスケジュールの各イテレーションに遅延段を挿入するステップと、
を含む方法。
【請求項１７】
第１のイテレーションにおける前記変数に関連付けられた前記レジスタを、第１のレジスタから第１の置換レジスタに置換し、前記第１の置換レジスタを、前記ループの後続のイテレーションにおける前記変数に再割り当てするステップをさらに含む、請求項１６記載の方法。
【請求項１８】
特定のイテレーションにおいて発生した例外に応答して、ハンドラコードの実行を介して前記例外を処理するステップをさらに含む、請求項１６記載の方法。
【請求項１９】
前記ループの最も直近に終了したイテレーションの結果をコミットするステップをさらに含む、請求項１８記載の方法。
【請求項２０】
前記最も直近に終了したイテレーションから始まるよう前記ループの実行を再開するステップをさらに含む、請求項１９記載の方法。
【請求項２１】
請求項１６乃至２０いずれか一項記載の方法を実行する手段を備えた装置。
【請求項２２】
ループの演算を実行する少なくとも１つのコアと、
前記ループの第１のイテレーションの第１の変数に関連付けられたレジスタのライフタイムを延ばし、且つ、イテレーションにおいて決定される、第２の変数の値の内容の記憶を遅延させるために、遅延段を前記ループに追加する段挿入ロジックと、
を備えたプロセッサ。
【請求項２３】
前記ループの複数のイテレーションの各イテレーションにおける前記レジスタを、前記レジスタからそれぞれの異なるレジスタに置換するモジュロ変数展開手段をさらに備えた、請求項２２記載のプロセッサ。
【請求項２４】
前記ループのＮ番目のイテレーションのＭ番目の段における例外に応答して、前記ループの（Ｎ−Ｓ＋Ｍ）番目のイテレーションのストア演算を再実行する補償手段であって、各イテレーションはＳ個の段を含む、補償手段をさらに備えた、請求項２２記載のプロセッサ。
【請求項２５】
前記補償手段は、さらに、前記ループの前記Ｎ番目のイテレーションにおける前記例外に応答して、前記ループの前記（Ｎ−Ｓ＋Ｍ）番目のイテレーションに関連付けられた第１のレジスタのライブアウト値を回復させる、請求項２４記載のプロセッサ。
【請求項２６】
請求項９乃至１５いずれか一項記載のコンピュータプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【国際調査報告】
2016519375.tif 000009
2016519375.tif 000010