(57)【特許請求の範囲】
【請求項１】
プロセッサと、
前記プロセッサに連結されたメモリと
を備え、
前記プロセッサは、
１又は複数のコアと、
ループの複数のオペレーションに関連するメモリ範囲情報をストアするために複数のエイリアスレジスタを含むレジスタファイルであって、前記メモリ範囲情報は、メモリ内の１又は複数のメモリ位置を参照する、前記レジスタファイルと、
前記複数のエイリアスレジスタのそれぞれを前記ループの対応するオペレーションに割り当てるレジスタ割り当て手段であって、前記割り当ては、ローテーションスケジュールに従って作成され、前記複数のエイリアスレジスタの少なくとも１つは、前記ループの第１のイタレーションの第１のオペレーションと、前記ループの後続するイタレーションの第２のオペレーションとに割り当てられる、前記レジスタ割り当て手段と
を有し、
前記１又は複数のコアの少なくとも１つは、エイリアスが存在するかを決定するために、前記複数のエイリアスレジスタの他の少なくとも１つにストアされているデータに対する、第１のエイリアスレジスタにストアされているデータの比較を実行する、システム。
【請求項２】
前記プロセッサは更に、
パイプライン化されたスケジュールに従って前記ループの前記複数のオペレーションをスケジュールするための命令スケジュール手段を有し、
前記ループの少なくとも１つのオペレーションは、前記ループの前記複数のオペレーションの順序と異なる実行スケジュールに従って実行される、請求項１に記載のシステム。
【請求項３】
第１のエイリアスレジスタは、第１のライフタイムの間は前記第１のオペレーションに割り当てられ、前記第１のエイリアスレジスタは、第２のライフタイムの間は第２のオペレーションに割り当てられ、前記第１のライフタイム及び前記第２のライフタイムは、重ならない期間である、請求項１に記載のシステム。
【請求項４】
前記第１のライフタイムは、前記ループの第１のイタレーションの範囲内であり、前記第２のライフタイムが、前記第１のイタレーションに連続する次のイタレーションである前記ループの第２のイタレーションの範囲内である、請求項３に記載のシステム。
【請求項５】
前記レジスタ割り当て手段は、関連するライフタイムが期限切れになった各エイリアスレジスタの内容を削除するためのローテーション一掃命令を実行する、請求項１から４のいずれか一項に記載のシステム。
【請求項６】
ローテーションレジスタファイルの複数のエイリアスレジスタのそれぞれを、ループの複数のイタレーションのためのローテーションシーケンスに従って連続して前記ループの対応するオペレーションに割り当てる手順であって、各エイリアスレジスタが、前記対応するオペレーションに基づきアクセスする１又は複数のメモリ位置のインディケーションをストアし、前記複数のエイリアスレジスタの１つは、前記ループの第１のイタレーションの第１のオペレーションと、前記ループの後続するイタレーションの第２のオペレーションとに割り当てられる、前記割り当てる手順と、
前記割り当てられた複数のエイリアスレジスタの少なくとも１つの内容を、１又は複数の他の割り当てられたエイリアスレジスタの内容と比較することで、エイリアス条件が存在するかを決定する手順と
をシステムに実行させる、プログラム。
【請求項７】
第１のエイリアスレジスタは、第１のライフタイムの間は前記第１のオペレーションに割り当てられ、前記第１のエイリアスレジスタは、第２のライフタイムの間は前記第２のオペレーションに割り当てられ、前記第１のライフタイム及び前記第２のライフタイムは、重ならない期間である、請求項６に記載のプログラム。
【請求項８】
前記第１のライフタイム及び前記第２のライフタイムは、前記ループの連続した隣り合う複数のイタレーション内に含まれる、請求項７に記載のプログラム。
【請求項９】
前記第１のライフタイム及び前記第２のライフタイムは、前記ループの隣り合わないイタレーションのなかにある、請求項７に記載のプログラム。
【請求項１０】
前記システムに更に、
同じ又は異なるイタレーションにある別のオペレーションに対する順序関係に基づいてオペレーションに対してライフタイムを割り当てる手順と、
対応するエイリアスレジスタを、前記ライフタイムの期間は前記オペレーションに割り当てる手順と
を実行させる、請求項６に記載のプログラム。
【請求項１１】
前記システムに、前記期間が期限切れになると、前記対応するエイリアスレジスタを、別のイタレーションの別のオペレーションに割り当て直す手順を実行させる、請求項１０に記載のプログラム。
【請求項１２】
前記システムに更に、順序関係の存在に応じて前記エイリアス条件が存在するかを決定する手順を実行させ、
前記順序関係は、
パイプライン化されたスケジュールに従って、前記ループの前記第２のオペレーションの後に実行するようスケジュールされた前記ループの前記第１のオペレーションと、
前記ループの第１のオペレーションが前記ループの前記第２のオペレーションの前に実行可能であるという前記ループでの指定と
に呼応して存在が示される、
請求項６から１１のいずれか一項に記載のプログラム。
【請求項１３】
レジスタファイルの複数のエイリアスレジスタのそれぞれを、ループの複数のイタレーションのためのローテーションシーケンスに従って連続して前記ループの対応するオペレーションに割り当てる段階であって、前記複数のエイリアスレジスタの１つを、前記ループの第１のイタレーションの第１のオペレーションと、前記ループの後続するイタレーションの第２のオペレーションとに割り当てることを含み、各エイリアスレジスタは、前記対応するオペレーションによりアクセスされる複数のメモリ位置のインディケーションをストアする、前記割り当てる段階と、
前記割り当てられた複数のエイリアスレジスタの少なくとも１つの内容を、１又は複数の他の割り当てられたエイリアスレジスタの内容と比較することで、エイリアス条件が存在するかを決定する段階と
を備える方法。
【請求項１４】
第１のエイリアスレジスタを、第１のライフタイムの間は前記第１のオペレーションに割り当て、前記第１のエイリアスレジスタを、第２のライフタイムの間は前記第２のオペレーションに割り当てる段階を更に備え、
前記第１のライフタイム及び前記第２のライフタイムは、重ならない期間である、請求項１３に記載の方法。
【請求項１５】
前記第１のライフタイム及び前記第２のライフタイムは、前記ループの連続した隣り合う複数のイタレーション内に含まれる、請求項１４に記載の方法。
【請求項１６】
第１のエイリアスレジスタを、第１のライフタイムの間は前記ループの第１のイタレーションの前記第２のオペレーションに割り当て、前記第１のエイリアスレジスタを、第２のライフタイムの間は前記ループの第２のイタレーションの前記第１のオペレーションに割り当てる段階を更に備え、
前記第１のライフタイム及び前記第２のライフタイムは、重ならない期間である、請求項１３に記載の方法。
【請求項１７】
同じイタレーション又は異なるイタレーションにある別のオペレーションに対する順序関係に基づいてオペレーションに対してライフタイムを割り当てる段階と、
対応するエイリアスレジスタを、前記ライフタイムの期間は前記オペレーションに割り当てる段階と
を更に備える、請求項１３に記載の方法。
【請求項１８】
前記期間が期限切れになると、前記対応するエイリアスレジスタを、別のイタレーションの別のオペレーションに割り当て直す段階を更に備える、請求項１７に記載の方法。
【請求項１９】
前記ループの前記第１のオペレーションに割り当てられた第１のエイリアスレジスタの内容を、前記第２のオペレーションに関する第２のライフタイムの間、前記第２のオペレーションに割り当てられた第２のエイリアスレジスタの内容と比較することにより、前記ループの第１のイタレーションにエイリアスが存在するかを決定する段階を更に備え、
前記第２のライフタイムは、前記第２のオペレーションの第２のスケジュールされた実行時間に対する前記第１のオペレーションの第１のスケジュールされた実行時間により決定される、請求項１３に記載の方法。
【請求項２０】
前記エイリアス条件が存在するかを決定する段階は、順序関係の存在に応じて実行され、
前記順序関係は、
パイプライン化されたスケジュールに従って、前記ループの前記第２のオペレーションの後に実行するようスケジュールされた前記ループの前記第１のオペレーションと、
前記ループの第１のオペレーションが前記ループの前記第２のオペレーションの前に実行可能であるという前記ループでの指定と
に呼応して存在が示される、請求項１３に記載の方法。
【請求項２１】
請求項１３から２０のいずれか一項の方法を実行するための手段を備える装置。
【請求項２２】
請求項１３から２０のいずれか一項の方法を実行する装置。
【請求項２３】
１又は複数のコアと、
ループの複数のオペレーションに関連するメモリ範囲情報をストアするために複数のエイリアスレジスタを含むレジスタファイルであって、前記メモリ範囲情報は、メモリ内の１又は複数のメモリ位置を参照する、前記レジスタファイルと、
前記複数のエイリアスレジスタのそれぞれを前記ループの対応するオペレーションに割り当てるためのレジスタ割り当て論理であって、前記割り当ては、ローテーションスケジュールに従って作成され、前記複数のエイリアスレジスタの少なくとも１つは、前記ループの第１のイタレーションの第１のオペレーションと、前記ループの後続するイタレーションの第２のオペレーションとに割り当てられる、前記レジスタ割り当て論理と
を備え、
前記１又は複数のコアの少なくとも１つは、エイリアスが存在するかを決定するために、前記複数のエイリアスレジスタの他の少なくとも１つにストアされているデータに対する、第１のエイリアスレジスタにストアされているデータの比較を実行する、
プロセッサ。
【請求項２４】
パイプライン化されたスケジュールに従って前記ループの前記複数のオペレーションをスケジュールするための命令スケジュール論理を更に備え、
前記ループの少なくとも１つのオペレーションは、前記ループの前記複数のオペレーションの順序と異なる実行スケジュールに従って実行される、
請求項２３に記載のプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
実施形態は、パイプライン化されたスケジュールされたオペレーションに関する。
【背景技術】
【０００２】
コンパイラが通常処理するタスクは、メモリ明確化（memory disambiguation）であり、これには、エイリアス解除された（unaliased）メモリアクセス（例えば、異なるメモリ位置を訪れるロード又はストア）の検出を含んで良い。これらのオペレーションは、より良い命令レベルの並列性のために、アウトオブオーダでスケジュールされてよい。これとは対照的に、同じメモリ位置を訪れるメモリオペレーションは、「エイリアス」と称され、アウトオブオーダでスケジュールすることができない。
【０００３】
メモリ明確化はしばしば、コンパイラ最適化（例えばソフトウェアパイプライニング）に含まれている。ソフトウェアパイプライニングは、連続したイタレーションの重複した実行によってループのための命令レベルの並列化を利用することができる。しかし、連続したイタレーションのオペレーションの実行の重複は、エイリアスを生成する場合がある。
【図面の簡単な説明】
【０００４】
【図１】本発明の実施形態における、エイリアスレジスタをスケジュールするためのシステムのブロック図である。
【０００５】
【図２Ａ】本発明の実施形態におけるエイリアスレジスタ割り当てスキームを示す。
【図２Ｂ】本発明の実施形態におけるエイリアスレジスタ割り当てスキームを示す。
【図２Ｃ】本発明の実施形態におけるエイリアスレジスタ割り当てスキームを示す。
【０００６】
【図３】本発明の別の実施形態におけるエイリアスレジスタ割り当てスキームを示す。
【０００７】
【図４】本発明の別の実施形態におけるエイリアスレジスタをスケジュールする方法のフローチャートを示す。
【０００８】
【図５】本発明の実施形態におけるプロセッサのブロック図である。
【０００９】
【図６】本発明の実施形態における複数のコアを含むプロセッサの実施形態を示す。
【００１０】
【図７】本発明の実施形態におけるシステムのブロック図である。
【発明を実施するための形態】
【００１１】
ランタイムで実行される最適化のために、メモリ明確化を実現するために、ハードウェアサポートが利用される場合がある。本発明の実施形態では、ハードウェアサポートは、複数のイタレーションのための実行される複数のオペレーションを含むループ等の循環コードに適用されてよい、複数のメモリアクセスレジスタ（「エイリアスレジスタ」）を含むレジスタファイル（例えばローテーションレジスタファイル）を含みうる。実施形態において、エイリアスレジスタは、メモリ明確化を実行して、ランタイムでエイリアスを実行するためにループのソフトウェアパイプライン化されたスケジュールに適用されてよい。
【００１２】
例えばスケジュールフェーズ中には、ループ内のメモリアクセス（例えば、オペレーションをロードしたり、又は、オペレーションをストアしたりする、ここでは「オペレーション」）が、エイリアスする（「データ投機」）ことができないと仮定することができる、例えば、メモリアクセス間に依存関係（例えば順序関係）がないと仮定することができる。
データ投機によって、より並列性が可能となり（例えば、オペレーションのアウトオブオーダ処理による計算リソースの効率的な利用）が可能となるが、一方で、エラーにつながりうる。例えば、メモリアクセスが互いにエイリアスを生じる場合（例えば、メモリアクセスが、重複するメモリ位置を対象とする場合）、又は、実行スケジュールのメモリアクセスの順序が、元のループにおけるその順序と異なっている場合には、データ投機が誤っていたことになる（例えばデータ投機が失敗する）。エイリアスを生じさせるようなこのケースをキャッチするために、各メモリアクセスは、アクセスが実行されたときの、アクセスのアドレスのメモリ範囲を記録するエイリアスレジスタを割り当てられることができる（例えば、アドレスから始まり、アクセスされたメモリ範囲）。アクセスのメモリ範囲は、全ての潜在的にエイリアスされる可能性のあるアクセスのエイリアスレジスタと比較され、マッチするものがある場合に、エイリアスが特定される（例えばデータ投機の失敗）。そのような失敗は、例えば復帰コードの実行によって処理されてよい。幾つかの実施形態では、復帰コードの実行は、ループの前のイタレーションにロールバックしてしまうこともあり、及び／又は、オペレーションを順序づけ直して、エイリアスを取り除いてしまうこともある。
【００１３】
概して、静的とローテーションという、２つの種類のエイリアスレジスタがある。静的なエイリアスレジスタは、ローテーションエイリアスレジスタと異なるよう利用される（例えば、命令にどのようにレジスタの比較がエンコードされるかについて）。静的なエイリアスレジスタとの比較を実行するために、静的なエイリアスレジスタのレジスタ数を明示的にエンコードしてよい。静的なレジスタとは対照的に、ローテーションエイリアスレジスタは通常、個々と比較されない。その代わりに、唯一のレジスタ数のみがエンコードされ、エンコードされたレジスタから始まり、最大番号のレジスタまでの、全てのレジスタが比較される。この技術は、エンコードを解決するが、偽の正を生じる可能性がある、例えば、レジスタが適切に割り当てられていないような場合に。
【００１４】
ローテーションエイリアスレジスタファイルについては、比較は「一方向」であってよい、例えば、比較が、最大番号のレジスタに向かって「下方向」ではなくて、「上方向チェック」であってよい。エイリアスレジスタファイルを指すベースポインタが存在していてよい。「ローテーション」では、ベースポインタが、上に移動し、元のものからベースポインタが指し示している現在のレジスタまで、全てのレジスタが一掃される。
【００１５】
本発明の実施形態は、ソフトウェアパイプライニングにおけるローテーションエイリアスレジスタを利用してよい。本明細書では、「レジスタ」又は「エイリアスレジスタ」は、「ローテーションエイリアスレジスタ」のことを指す。
【００１６】
図１は、本発明の実施形態におけるエイリアスレジスタをスケジュールするためのシステム１００のブロック図である。システム１００は、ダイナミックランダムアクセスメモリ（DRAM）１８０に連結されたプロセッサ１１０を含む。プロセッサ１１０は、命令を実行するための複数のコア1120, 1121…112nを含んで良い。プロセッサ１１０は、レジスタ割り当て論理１１４、命令スケジュール論理１１６、ローテーションレジスタファイル１１８、エイリアス検出論理１２０、及び、キャッシュ１２２を含む１又は複数のキャッシュメモリを含んで良い。実施形態では、レジスタ割り当て論理１１４、命令スケジュール論理１１６、及びエイリアス検出論理１２０の１又は複数が、ソフトウェア、ハードウェア、ファームウェア、又はこれらの組み合わせであってよい。例えば、レジスタ割り当て論理１１４は、実行ハードウェア又は専用ファームウェア又は専用回路又はこれらの組み合わせにより実行されるソフトウェアを含んで良い。命令スケジュール論理１１６は、ソフトウェア、ハードウェア、ファームウェア、又はこれらの組み合わせを含んでよい。例えば命令割り当て論理１１４は、実行ハードウェア又は専用ファームウェア又は専用回路又はこれらの組み合わせにより実行されるソフトウェアを含んで良い。
【００１７】
オペレーションにおいて、命令スケジュール論理１１６は、ループ（例えば、複数のN個のイタレーションのためにイタレーション実行される定義されたオペレーションのグループ）の実行のためのオペレーションのスケジュールを作成してよい。命令スケジュール論理１１６は、利用可能な計算リソースの効率利用を達成するために、オペレーション（例えばソフトウェアパイプライニング）をスケジュールしてよい。
【００１８】
ソフトウェアパイプライニングの結果として、命令スケジュール論理が生成する実行スケジュールによって、ループで指定されるオペレーションの実行の順序と比較して異なる実行の順序となる場合がある。例えば、２つのオペレーションのループ、オペレーションaとその後のオペレーションbが、命令スケジュール論理１１６によってスケジュールされてよく、これにより、利用可能な計算リソースを効率的に利用するために、各イタレーションにおいて、オペレーションbが行われた後にオペレーションaが行われるようになる。
【００１９】
レジスタ割り当て論理１１４は、ループの複数のイタレーションそれぞれについて、ローテーションレジスタファイル１１８の１セットのエイリアスレジスタの各エイリアスレジスタを、ループの対応するオペレーションに割り当ててよい。或る実施形態においては、２つのオペレーションに同時にエイリアスレジスタが割り当てられていない場合に、ローテーションレジスタファイル１１８の各エイリアスレジスタが、一度を超える回数割り当てられて良い、例えばエイリアスレジスタは、複数のエイリアスレジスタ（例えば有限数）をローテーションする、連続したオペレーションに割り当てられてよい。
【００２０】
各エイリアスレジスタは、メモリアクセスデータ、例えば、ループの対応するオペレーションがアクセスするDRAM１８０内の又はキャッシュ１２２の１又は複数のメモリ位置のメモリアドレス範囲をストアするために利用されてよい。或る実施形態では、エイリアス検出論理１２０によって、エイリアスレジスタの１つのコンテンツが、ローテーションレジスタファイル１１８のエイリアスレジスタの幾つかの他のもののコンテンツと比較されてよく、これにより、エイリアスが存在するか、例えば、同じ時間フレーム内の共通のメモリ位置へのアクセス（例えばロードオペレーション又はストアオペレーションにより）決定されてよい。
【００２１】
図２A、図２B、図２Cは、本発明の或る実施形態におけるレジスタ割り当てスキームを示す。図2Aで、例示的なループとして、擬似コードループ２１０が、オペレーションa及びオペレーションbを含む。オペレーションa及びbは両方とも、メモリアクセス、例えば、ロード又はストアオペレーション（ここでは「オペレーション」）である。
【００２２】
N＝３について、ループ２１０は、３つのイタレーションを実行する（i=0, 1, 2）。擬似コード２１０が記載するループにおいて、オペレーションaは、同じイタレーションのなかでオペレーションbより前に実行され、オペレーションaは更に、後続するイタレーションにおいて全てのaオペレーション及び全てのbオペレーションの前に実行される。
【００２３】
図2Bでは、ループについてソフトウェアパイプライン化されたスケジュール２２０が示されている。ソフトウェアパイプライン化されたスケジュール２２０では、イタレーション０のなかで、オペレーションaが、オペレーションbが実行された後に実行をスケジュールされる。イタレーション１において、オペレーションaは、オペレーションbが実行された後に実行されるようにスケジュールされる。イタレーション２では、オペレーションaが、オペレーションbが実行された後に実行されるようにスケジュールされる。ループ２１０と比較してオペレーションの順序づけ直しによってエイリアスが生じてよく、これは、ランタイムエイリアスモニタリングによって検出されてよい。エイリアスレジスタは、ランタイムエイリアスモニタリングが達成されるよう割り当てられて良い。
【００２４】
図2Cでは、エイリアスレジスタ割り当てスキーム２３０が、本発明の或る実施形態における解決方法を表している。X軸２３２は時間を示し、Y軸２３４は対応するエイリアスレジスタに関するレジスタ番号を示す。バー２４２から２５０は、オペレーションの「ライフタイム」を表す。第１のオペレーションのライフタイムは、第１のオペレーション（「生成オペレーション」）の実行から始まり、第２のオペレーションの実行で終わる期間として定義されてよく、第２のオペレーションの終了前に第１のオペレーションとエイリアスしてよい。各ライフタイムは、対応する生成オペレーションと称されている。例えば、ライフタイム２４４は、オペレーションbの実行が開始される時点t＝１において始まり、オペレーションaの実行が終了するt＝５で終了する（例えばイタレーション０における命令bが関連するライフタイム２４４をもつ）。
【００２５】
割り当てスキーム２３０は、各イタレーション内のループの各オペレーションにエイリアスレジスタを割り当てる（N＝３についてイタレーションi = 0, 1, 2）。ループのイタレーションiについて、a及びbのライフタイムがレジスタ2*i 及び2*i +1にそれぞれ割り当てられる。
【００２６】
例えば、イタレーション２３６（i=0, イタレーション 0）において、時間軸２３２の上の時間＝４において、オペレーションaが実行を開始する。エイリアスレジスタ０にストアされるべき、オペレーションaのメモリアクセスアドレス範囲は、レジスタ１から、アクティブオペレーションに関連づけられている最大番号のレジスタまで（例えば第１のイタレーション２３６及び第２のイタレーション２３８のオペレーションbに割り当てられているレジスタ１及び３）、より高い番号のエイリアスレジスタのそれぞれのストアされているアクセス範囲と比較される。（レジスタ２は、イタレーション２３８のオペレーションaに割り当てられ、これは、イタレーション２３６のオペレーションaのライフタイム２４２の完了に続いて実行されるので、考慮しない）。このようにして、エイリアスは、後続する割り当てられたエイリアスレジスタにストアされているストアされているメモリアクセス範囲とともに、第１の割り当てられているエイリアスレジスタにストアされているメモリアクセス範囲の比較により動的にキャッチすることができる。
【００２７】
時間t＝５において、イタレーション２３６（「イタレーション０」）のライフタイム２４２及び２４４が期限切れになっているので、t＝５からは、第１のイタレーション２３６のライフタイム２４２及び２４４の間に割り当てられたレジスタの更なる内容の比較はされない。この結果、レジスタ０及び１が、イタレーション２４０（「イタレーション２」）で再利用されてよく、これはt＝５から始まる。
【００２８】
エイリアスレジスタ割り当てスキーム２３０の例では、例えばループ２１０のメモリ位置の重複する利用のために、４つのローテーションレジスタ（番号０から３）のセットで、エイリアスのインスタンスを検出するためには十分である。パイプライン化されたスケジュール２２０に従って実行されるループ２１０は、イタレーション間隔（２２４、更に２２６）Δt=2を持ち、これは、連続したイタレーションの開始の間の期間である。レジスタ割り当てスキーム２３０のイタレーション間隔（２６０、更に２６２も）もΔt=2である。
【００２９】
エイリアスレジスタは、エイリアスを検出するためと比較を実行するために全部で４つのローテーションレジスタで十分なように割り当てることができる。より複雑なソフトウェアパイプライニングスキームをもつ２を超える数のオペレーションを含むループのためには、エイリアスの各インスタンスを検出するために、ローテーションレジスタのより大きなセットが必要となる場合がある。Nのいずれの値についても、ローテーションベースで有限数のセットのエイリアスレジスタ（Nより小さい数）が割り当てられてよく（例えば、第１のエイリアスレジスタから始まり、最大番号のエイリアスレジスタまでであり、循環的に繰り返されて良い）、これにより、エイリアスの検出が可能となる。
【００３０】
図３は、本発明の別の実施形態におけるレジスタ割り当てスキーム３００を示す。レジスタ割り当て３００は、ソフトウェアパイプライン化されたスケジュールを変更することなく、エイリアスレジスタの数を低減させることを目的とする。
【００３１】
時間軸３０２は、各オペレーションa及びbのライフタイムを測定してよい。レジスタ軸３０４は、各オペレーションのための対応するメモリアクセス範囲（例えば図１のDRAM１８０等のメモリ内のアドレス範囲）をストアするためにどのエイリアスレジスタが割り当てられているかを示して良い。例えば、イタレーション３０６（０番目のイタレーション）において、レジスタ０が、ライフタイム３１２をもつオペレーションaに関連するメモリアクセス範囲をストアして、レジスタ１が、ライフタイム３１４をもつオペレーションbに関連するメモリアクセス範囲をストアする。図２AからCの擬似コード２１０に示されているオペレーションaは、オペレーションbの前に行われることが意図されている。
【００３２】
エイリアスが第１のイタレーションのオペレーションa及びbの間に存在しないと保証するために、図３のスキーム３００において、オペレーションbのライフタイム３１４が、オペレーションaのライフタイム３１２の最後まで延長されて、エイリアスレジスタ１がライフタイム３１４のためのオペレーションbに割り当てられる。レジスタ割り当て３００において、あるイタレーションにおけるオペレーションaのライフタイムは同じイタレーション及び次のイタレーションにおいてオペレーションbのライフタイムを超えており、エイリアスのチェックは、エイリアスレジスタ０からエイリアスレジスタ１までを含む（ローテーションエイリアスレジスタの数値的順序における「上方向」）。更に、イタレーション３０６（「イタレーション０」）におけるオペレーションaのライフタイム３１２は、イタレーション３０８（「イタレーション１」）のオペレーションbのライフタイム３１８の間に生じるので、レジスタ０の内容は、レジスタ２の内容と比較されて、エイリアスが、ライフタイム３１２の間のオペレーションaとライフタイム３１８の間のオペレーションbとの間に存在するか、決定されてよい。
【００３３】
ライフタイム３１４は、t＝５で完了することに留意されたい。イタレーション３０８（「イタレーション１」）を見ると、ライフタイム３１４が完了しており、ライフタイム３１４を超えるレジスタ１が有用ではないために、エイリアスレジスタ１を、ライフタイム３１６をもつイタレーション３０８の中に含まれるオペレーションaの関連するメモリアクセス範囲をストアするために利用することができることに気づくだろう。破線３２４及び３２６は、ライフタイム３１８及び割り当てられたレジスタ２をもつオペレーションbを実行して、ライフタイム３１６及び割り当てられたレジスタ１をもつオペレーションaを実行することを含むイタレーションの３０８（イタレーション１）の境界を示す。
【００３４】
従ってレジスタは、循環的に割り当てることができ、例えばレジスタ１を利用して、ライフタイム３１４の間にイタレーション３０６のオペレーションbのメモリアクセス範囲をストアすることができ（例えば期間Δt = 1→5）、レジスタ１を更にイタレーション３０８で利用して、ライフタイム３１６（Δt= 6→7）中にオペレーションaのためのメモリアクセス範囲をストアしてよい。
【００３５】
イタレーション３１０（「イタレーション２」）は、破線３２６及び３２８によって境界を隔てられてよく、オペレーションbのメモリアクセス範囲をストアするためのレジスタ０を利用したライフタイム３２２(Δt= 5→9)を持つオペレーションbの実行と、イタレーション３１０のオペレーションaのメモリアクセス範囲をストアするためのレジスタ２を利用したライフタイム３２０(Δt= 8→9)を持つオペレーションaの実行とを含むが、これは、ライフタイム３１８が、t=7で期限切れとなり、これによりイタレーション３１０で再利用されるレジスタ２が使い尽くされるからである。従って、レジスタ２が連続したイタレーション（例えばオペレーションbのライフタイム３１８中のイタレーション３０８、更には、オペレーションaのライフタイム３２０中のイタレーション３１０においても）において再利用される（「レジスタ再利用」）。連続したイタレーションにおける、このレジスタの再利用技術は、図２AからCのループ２１０等のループの実行中にエイリアスを検出するために利用されるレジスタの総数を低減させることができる。更にレジスタ割り当て３００において、レジスタ０、１、２のセットが循環的に利用されて（例えばレジスタ０がライフタイム３１２(Δt = 4→5)中のイタレーション３０６で利用され（「イタレーション０」）、再度、ライフタイム３２２ (Δt = 5→9)中にイタレーション３１０（「イタレーション２」）が利用される）。
【００３６】
ループのソフトウェアパイプライン化されたスケジュールのためのエイリアスレジスタのローテーション割り当ての利用は、レジスタ割り当て問題を循環スケジュール問題に変換することと考えることができる。各依存関係（オペレーションの実行順序に基づくオペレーション間の関係）は、依存距離を持つと考えることができる（例えば依存オペレーション間のイタレーション数）。例えば図２AからC及び図３に示すように、２つの依存関係がある。
１）a→b：（例えば同じイタレーション）ゼロの距離（例えばイタレーションの間の距離）である、これは、同じイタレーションにおけるオペレーションaのライフタイムが、オペレーションｂのライフタイムと同じ又はこれより小さな数のレジスタを割り当てられることを意味する。２）a→b：（隣接するイタレーション）１の距離である、これは、或るイタレーションにおけるオペレーションaのライフタイムが、隣接するイタレーションのオペレーションｂのライフタイムと同じ又はこれより小さな数のレジスタを割り当てられ、ローテーションエイリアスレジスタが、ローテーションレジスタの数値的に「上方向」の順序でチェックされることを意味する。
【００３７】
本発明の実施形態では、依存関係のグラフに基づいて、「ライフタイムのためのソフトウェアパイプライン化されたスケジュール」を、ライフタイムをオペレーションとして取り扱うことにより作成することができ、ライフタイムをスケジュールするために、ソフトウェアパイプライニングアルゴリズムを適用することができる。
【００３８】
スケジューリングアプローチを形式化（formalized）することができ、これにより、ライフタイムをレジスタに「スケジュール」するレジスタ割り当て問題が定式化される（formulate）。例えばa(i)を、ループのイタレーションiのオペレーションaとして、r(a, i)を、スケジュールによりそれに割り当てられたレジスタとする。
【００３９】
スケジュールは、以下の制約を配慮する。
（１）全てのｉについて、モジュロ制約：r(a, i) = r(a, 0) + i * CここでＣは、スケジューラが決定する定数である。つまり、スケジュールのレジスタとして、オペレーションのライフタイムが一定期間に現れる。例えば図２AからCのブロック２３０では、オペレーションａのライフタイムが、図３の一定期間Ｃ＝２に現れ（レジスタ０及び２）、オペレーションａのライフタイムが、一定期間Ｃ＝１に現れる（レジスタ０及び１）。
（２）依存関係の制約：d ≧ 0であるとき、a(i)及びb(i+d)がエイリアスされるとすると、元の実行順序ではa(i)がb(i+d)の前であるが、これらは、ループのソフトウェアパイプライン化されたスケジュールでは順序付け直される。どのエイリアスもランタイム中に確実にキャッチされるよう、我々は全てのｉについてr(a, i) ≦r(b, i+d)とする。つまり、a(i)は、b(i+d)と同じレジスタを割り当てられ、又は、これより小さい数のレジスタを割り当てられることで、a(i)のメモリアドレス範囲を、b(i+d)のメモリアドレス範囲と比較させる。これは、ローテーションレジスタファイルの一方向比較特徴のためである。この制約は、距離がｄに等しく、待ち時間（レジスタについて）が０である依存関係a→bによりモデリングすることができる。
（３）リソース制約：２つのオペレーションのライフタイムが時間的に重複している場合、これらには同じレジスタを割り当てることができない。
【００４０】
伝統的なソフトウェアパイプライニングは、リソースと時間という２つの次元をもつ。一定期間における時間に対するオペレーション（開始期間「ＩＩ」）をスケジュールして、全ての依存関係及びリソース制約を配慮する。ここで提示するレジスタ割り当てにおいては、レジスタが、「時間」と同じように取り扱われてよく、時間は、「リソース」と同じように取り扱われてよく、ライフタイムは、「オペレーション」と同じように取り扱われてよく、エイリアスチェックは「依存関係」と同じように取り扱われてよい。
【００４１】
オペレーションにおいては、本発明の実施形態においては、以下の考慮点を考慮に入れて、スケジュールに到達するようことができてよい。
１．依存関係の構築
距離ｄの（a及びｂの間のイタレーション数）を持つ依存関係a→bが、ｄ＝０であるときを除き上述した依存関係の制約に従って依存関係のグラフに追加されるが、元の実行順序の同じイタレーションにおいてａは、ｂの後にある。更に、依存関係のグラフにおいてローカルサイクルを完了させない限りにおいて、以下の依存関係を、偽の正を回避するために追加することができ、ここで、ローカルサイクルとは、距離が全て０である依存関係からなる。d≧ 0である場合にa(i)及びb(i+d)がエイリアスされうると仮定すると、元の実行順序においても更にループのソフトウェアパイプライン化されたスケジュールにおいても、a(i)がb(i+d)の前である。この場合、b(i+d)が実行されているとき、a(i)をエイリアスを求めてチェックすべきではない。  これは、b(i+d)を確実にa (i)より大きな数のレジスタに割り当てるようにすることで実施することができる。つまり、全てのｉについて、r(a, i) < r(b, i+d)である。これは、距離がｄに等しく１の待ち時間をもつ依存関係a →bを追加することで行うことができる。偽の正は、更に、依存関係のグラフにおけるローカルサイクルを完了させない限り、以下の種類の依存関係を追加することで最小限に抑えることができる。同じイタレーションからのオペレーションａ及びｂにおいては、ａがｂを決してチェックしない場合が存在しうる。距離がゼロに等しく、待ち時間が１である依存関係b→aを追加することができる。
２．循環スケジュール
１）ローカル依存関係のみに基づいてライフタイムをスケジュールする。つまり、距離が０である依存関係のみを考慮して、全ての他のものを無視する。これにより、単一のループのイタレーションのライフタイムのためのスケジュールが生成される。様々な戦略が利用されて、スケジュールされるライフタイムに優先度をつけることができる。或る実施形態では、「ファーストフィット」と称されるシンプルなスケジュール戦略を用いてよい。つまり、１を超えるライフタイムのスケジュールの準備ができている場合、これを最も早い開始時間で優先させることができる。
２）全てのループのイタレーションのライフタイムは同じスケジュールを持つと仮定する。無視された依存関係を考慮して、２つの連続するループのイタレーションのライフタイムのスケジュールを重複させる。これにより、イタレーション間のレジスタの再利用が可能となる、よりコンパクトなスケジュールが生成される。ローカルスケジューリング及びコンパクト化するアプローチは、ファーストフィット戦略と一緒に利用されることで、効果的に偽の正を低減させることができる。
３．（上の）依存関係の構築でサイクル形成を回避するべく追加されなかった依存関係の処理省かれた依存関係a→bのそれぞれについて、スケジュールによって配慮されたか決定するべくチェックする。されなかった場合には、ｂを静的なエイリアスレジスタに移動させる。
４．レジスタ割り当てとローテーションレジスタ割り当ては、無限の数のレジスタを持つフラットな時空ダイアグラムを仮定することができる。ローテーションレジスタファイルのものにダイアグラムのレジスタ番号をマッピングする。更にローテーション命令を、各ＩＩサイクルについてループのソフトウェアパイプライン化されたスケジュールに挿入することができ、これにより、各ＩＩサイクルごとにＣ個の数の死んだライフタイムを「一掃」することができる。
【００４２】
図４は、本発明の実施形態におけるエイリアスレジスタを割り当てる方法のフローチャート４００である。ブロック４０２で、依存関係がライフタイム間に構築されてよい。ブロック４０４に進み、構築された依存関係とリソース制約とに従ってレジスタにライフタイムをスケジュールすることを含み、循環スケジュールを実行する。ブロック４０６に進み、ブロック４０２で考慮されなかった依存関係を処理してよい（例えば静的なエイリアスレジスタを利用することによって）。ブロック４０８に進み、複数のエイリアスレジスタをループのオペレーションに割り当ててよい（例えば、エイリアスレジスタは、各イタレーションのループの各オペレーションに割り当てられてよい）。エイリアスレジスタは、循環的に割り当てられてよく、ここで各レジスタは、各オペレーションのライフタイムに割り当てられ、各レジスタは、各オペレーションがアクセスするメモリアドレスのインディケーションをストアしてよい。幾つかの実施形態では、第１のイタレーションの第１のオペレーションに割り当てられた少なくとも１つのレジスタが、第１のオペレーションの関連するライフタイムが期限切れになった後から始まる連続したイタレーションの別のオペレーションにより再利用されてよい。従って、２つの連続するループのイタレーションのライフタイムは、イタレーションの間のレジスタを再利用してよいコンパクトなスケジュールを生じさせる場合がある。ブロック４１０に進み、ローテーション一掃命令が、スケジュールに追加され、完了したライフタイムに関するエイリアスレジスタを一掃（例えば削除）するべく実行されてよい。
【００４３】
図５を参照すると、本発明の実施形態におけるプロセッサのブロック図が示されている。図５に示すように、プロセッサ５００は、複数のコア５１０ａから５１０ｎをコアドメイン５１０内に含む、マルチコアプロセッサであってよい。コアの１又は複数は、本発明の実施形態において、エイリアスレジスタをループのオペレーションに割り当てるための、命令スケジュール論理、エイリアスレジスタ（例えばローテーションレジスタファイル）、及びレジスタ割り当て論理を含んでよい。
【００４４】
コアは、様々なコンポーネントを含むシステムエージェント又はアンコア５２０に、インターコネクト５１５を介して連結されてよい。分かるように、アンコア５２０は、最終レベルキャッシュであってよく、キャッシュコントローラ５３２を含む共有キャッシュ５３０を含んでよい。加えて、アンコアは、統合されたメモリコントローラ５４０と様々なインタフェース５５０とを含んでよい。
【００４５】
図５を更に参照して、プロセッサ５００は、例えばメモリバスを介して、システムメモリ５６０と通信してよい。加えて、インタフェース５５０によって、周辺機器、大容量記憶装置等の様々なオフチップのコンポーネントに対して接続を行うことができる。図５の実施形態はこの特定の実装例で示されているが、本発明の範囲はこの点に限定はされない。
【００４６】
図６を参照すると、複数のコアを含むプロセッサの実施形態が示されている。プロセッサ６００は、マイクロプロセッサ、エンベデッドプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、ネットワークプロセッサ、ハンドヘルドプロセッサ、アプリケーションプロセッサ、コプロセッサ、システムオンチップ（ＳＯＣ）、又はコードを実行するその他のデバイス等の任意のプロセッサ又は処理デバイスを含む。一実施形態では、プロセッサ６００が、少なくとも２つのコア、つまりコア６０１と６０２、を含み、これらは、非対称コア又は対称コア（例示されている実施形態）を含んでよい。しかし、プロセッサ６００は、対称であっても非対称であってもよい任意の数の処理エレメントを含んでよい。
【００４７】
一実施形態では、処理エレメントは、ソフトウェアスレッドをサポートするハードウェア又は論理である。ハードウェア処理エレメントの例には、実行状態又はアーキテクチャ状態等のプロセッサの状態を保持することができる、スレッドユニット、スレッドスロット、スレッド、処理ユニット、コンテキスト、コンテキストユニット、論理プロセッサ、ハードウェアスレッド、コア、及び／又は任意の他のエレメントが含まれる。言い換えると、処理エレメントは、一実施形態では、ソフトウェアスレッド、オペレーティングシステム、アプリケーション、又はその他のコード等の、コードと独立して関連することができる任意のハードウェアのことを指す。物理プロセッサは、通常、コア又はハードウェアスレッド等の任意の数の他の処理エレメントを潜在的に含む集積回路のことを指す。
【００４８】
コアはしばしば、独立したアーキテクチャ状態を維持することができる集積回路上に位置している論理であって、各独立して維持されるアーキテクチャ状態は、少なくとも幾つかの専用実行リソースと関連付けられている論理のことを指す。コアとは対照的に、ハードウェアスレッドとは、通常、独立したアーキテクチャ状態を維持することができる集積回路の上に位置する任意の論理であって、独立して維持されるアーキテクチャ状態は、実行リソースに対するアクセスを共有する論理のことを指す。分かるように、特定のリソースが共有され、他のものがアーキテクチャ状態に専用のとき、ハードウェアスレッドとコアとの間の命名の間の境界線は重なる。しかししばしば、コアとハードウェアスレッドは、オペレーティングシステムによって、個々の論理プロセッサとして見られ、ここでオペレーティングシステムは、各論理プロセッサ上のオペレーションを個々にスケジュールすることができる。
【００４９】
図６に示すように、物理プロセッサ６００は、２つのコア、つまりコア６０１及び６０２を含む。ここでコア６０１及び６０２は、対称コアとして考えられる（つまり、同じ構成、機能ユニット、及び／又は論理をもつコア）。他の実施形態では、コア６０１は、アウトオブオーダプロセッサコアを含み、コア６０２は、インオーダプロセッサコアを含む。しかし、コア６０１及び６０２は、任意のタイプのコア、例えばネーティブコア、ソフトウェア管理されたコア、ネーティブ命令セットアーキテクチャ（ＩＳＡ）を実行するよう適合されたコア、変換されたＩＳＡを実行するよう適合されたコア、共同設計されたコア、又は他の公知のコアから個々に選択されてよい。説明を更に進めるために、コア６０１に示す機能ユニットを更に詳細に説明する（コア６０２のユニットは同様にオペレーションするので）。
【００５０】
図示されているように、コア６０１は、２つのハードウェアスレッド６０１ａ及び６０１ｂを含み、これらは更に、ハードウェアスレッドスロット６０１ａ及び６０１ｂと称されてもよい。従って、一実施形態では、ソフトウェア実体（例えばオペレーティングシステム等）が、潜在的にプロセッサ６００を、４つのソフトウェアスレッドを同時に実行することができる、４つの別個のプロセッサ、つまり、４つの論理プロセッサ又は処理エレメントとして見る。上でほのめかしたように、第１のスレッドは、アーキテクチャ状態レジスタ６０１aに関連付けられており、第２のスレッドは、アーキテクチャ状態レジスタ６０１bに関連付けられており、第３のスレッドは、アーキテクチャ状態レジスタ６０２aに関連付けられており、第４のスレッドは、アーキテクチャ状態レジスタ６０２bに関連付けられ得る。
ここで、上述したように、アーキテクチャ状態レジスタ（601a, 601b, 602a, 及び602b）は、処理エレメント、スレッドスロット、又はスレッドユニットと称されて良い。例示したように、アーキテクチャ状態レジスタ６０１aは、アーキテクチャ状態レジスタ６０１bに複製され、これにより個々のアーキテクチャ状態／コンテキストが、論理プロセッサ６０１a及び論理プロセッサ６０１bのためにストアすることができる。コア６０１では、他のより小さいリソース、例えばアロケータ及びリネーマブロック６３０における命令ポインタ及びリネーム論理等も、更に、スレッド６０１a及び６０１bのために複製されてよい。幾つかのリソース、例えばリオーダ／リタイヤユニット６３５、ILTB６２０、ロード／ストアバッファ、及びキュー等も、パーティショニングによって共有されてよい。他のリソース、例えば汎用内部レジスタ、ページテーブルベースレジスタ、低レベルデータキャッシュ及びデータTLB６１５、実行ユニット６４０、及びアウトオブオーダユニット６３５の部分も、潜在的に完全に共有される。
【００５１】
プロセッサ６００はしばしば、完全に共有されてよい、パーティショニングにより共有されてよい、又は、処理エレメントによって又は処理エレメントに専用される、他のリソースを含んで良い。図６には、プロセッサの例示的な論理ユニット／リソースをもつ純粋に例示的なプロセッサの実施形態が示されている。プロセッサは、これらの機能ユニットのいずれかを含んでも省いてもよく、又、図示されていない任意の他の機能ユニット、論理、又はファームウェアを含んでもよい。図示しているように、コア６０１は、簡略化され、代表的なアウトオブオーダ（OOO）プロセッサコアを含む。しかし、インオーダプロセッサは、様々な異なる実施形態で利用されてよい。OOOコアは、実行され／取られる分岐を予測する分岐対象バッファ６２０と、命令のためのアドレス変換エントリをストアする命令変換バッファ（I-TLB）６２０とを含む。
【００５２】
コア６０１は更に、フェッチされたエレメントをデコードするための、フェッチユニット６２０に連結されたデコードモジュール６２５を含む。フェッチ論理は、一実施形態においては、それぞれ、スレッドスロット６０１a、６０１bに関連付けられた個々のシーケンサを含む。通常コア６０１は、第１のISAに関連付けられており、これは、プロセッサ６００上に実行可能な命令を定義／特定する。しばしば第１のISAの一部分である機械コード命令は、命令の一部分（オペコードと称される）を含み、これは、実行される命令又はオペレーションを参照／指定する。デコード論理６２５は、これら命令を、これらのオペコードから認識し、デコードされた命令を、第１のISAが定義するように処理するためにパイプラインへと渡す回路を含む。例えば一実施形態ではデコーダ６２５が、トランザクション命令等の特定の命令を認識するよう設計又は適合された論理を含む。デコーダ６２５による認識の結果、アーキテクチャ又はコア６０１は特定の、所定のアクションをとり、適切な命令に関連付けられたタスクを実行する。ここに記載したタスク、ブロック、オペレーション、及び方法のいずれかを、単一又は複数の命令に呼応して実行することができ、その幾つかが新たな又は古い命令であってよいことは留意に値する。
【００５３】
一例では、アロケータ及びリネーマブロック６３０は、命令処理結果をストアするためのレジスタファイル等のリソースをリザーブするためのアロケータを含む。しかし、スレッド601a及び601bは潜在的に、アウトオブオーダ実行が可能であり、アロケータ及びリネーマブロック６３０は更に、他のリソース、例えば命令の結果等をトラッキングするためのリオーダ・バッファをもリザーブする。ユニット６３０は、更に、プロセッサ６００の内部の他のレジスタにプログラム／命令参照レジスタをリネームするためのレジスタリネーマを含んで良い。リオーダ／リタイヤユニット６３５は、例えば上述したリオーダ・バッファ、ロードバッファ、及びストアバッファ等のコンポーネントを含み、これにより、アウトオブオーダ実行及びアウトオブオーダを実行した命令の後でのインオーダリタイヤをサポートする。
【００５４】
スケジューラ及び実行ユニットブロック６４０は、一実施形態では、実行ユニット上で命令／オペレーションをスケジュールするためのスケジューラユニットを含む。例えばスケジューラユニットは、パイプライン化されたスケジュールに従ってループのオペレーションをスケジュールしてよい。その実行ユニットに関連付けられたレジスタファイルが更に含まれ、情報命令処理結果をストアする。例示的な実行ユニットは、浮動小数点実行ユニット、整数実行ユニット、ジャンプ実行ユニット、ロード実行ユニット、ストア実行ユニット、及びその他の公知の実行ユニットを含む。
【００５５】
コア６０１及び６０２の１つ又は両方が、本発明の実施形態においてループの複数のオペレーションのそれぞれに対応するエイリアスレジスタファイル（６４２又は６４６）のエイリアスレジスタを割り当てる、対応するエイリアスレジスタファイル（６４２又は６４６）及び対応するレジスタ割り当て論理（６４４又は６４８）を含んでよい。エイリアスレジスタは、本発明の実施形態においてエイリアスを特定するために利用されてよい。
【００５６】
より低いレベルのデータキャッシュ及びデータ変換バッファ（D-TLB）６５１が、実行ユニット６４０に連結される。D-TLB 651は、最近の仮想／線形から物理アドレス変換をストアするためのものである。具体的な例として、プロセッサは、物理メモリを複数の仮想ページに分割するためのページテーブル構造を含んで良い。
【００５７】
ここでコア６０１及び６０２は、より高いレベル又は更に外側の（further-out）キャッシュ６１０へのアクセスを共有し、これは、最近フェッチされたエレメントをキャッシュするためのものである。より高いレベル又は更に外側とは、増加する、又は実行ユニットから更に離れる方向のキャッシュレベルのことを示す。一実施形態では、より高いレベルのキャッシュ６１０が、最終レベルのデータキャッシュであり、プロセッサ６００においてメモリ階層で最終キャッシュ、例えば第２又は第３レベルのデータキャッシュである。しかし、より高いレベルのキャッシュ６１０は、そのように限定はされず、命令キャッシュに関連づけられても、これを含んでも良い。トレースキャッシュ、つまり、命令キャッシュの一種類、は、その代わりに、最近デコードされたトレースをストアするためのデコーダ６２５の後に連結してもよい。
【００５８】
示されている構成では、プロセッサ６００も、バスインタフェースモジュール６０５を含む。歴史的には、コントローラ６７０が、プロセッサ６００の外部のコンピューティングシステムに含まれている。このシナリオでは、バスインタフェース６０５が、プロセッサ６００外のデバイス、例えばシステムメモリ６７５、チップセット（しばしば、メモリ６７５及びI／Oコントローラハブに接続して周辺機器に接続するためのメモリコントローラハブを含む）、メモリコントローラハブ、ノースブリッジ、又はその他の集積回路等を含む、と通信する。このシナリオでは、バス６０５が、マルチドロップバス、ポイントツーポイントインターコネクト、シリアルインターコネクト、パラレルバス、コヒーレントな（例えばキャッシュコヒーレントな）バス、階層状の（layered）プロトコルアーキテクチャ、差動バス（differential bus）、及びGTLバス等の任意の公知のインターコネクトを含んで良い。
【００５９】
メモリ６７５は、プロセッサ６００に専用であっても、システムの他のデバイスと共有されてもよい。メモリ６７５の様々なタイプに共通の例は、DRAM、SRAM、不揮発性メモリ（NVメモリ）、及びその他の公知のストレージデバイスを含む。デバイス６８０は、グラフィックアクセラレータ、プロセッサ、又は、メモリコントローラハブに連結されたカード、I／Oコントローラハブに連結されたデータストレージ、無線トランシーバ、フラッシュデバイス、オーディオコントローラ、ネットワークコントローラ、又はその他の公知のデバイスを含んでよい。
【００６０】
しかし、図示した実施形態では、コントローラ６７０がプロセッサ６００の一部分として示されていることに留意されたい。近年、SOC等の単一のダイに、より多くの論理及びデバイスが集積されるようになるにつれて、これらデバイスのそれぞれがプロセッサ６００に組み込まれ得るようになっている。例えば一実施形態では、メモリコントローラハブ６７０が、プロセッサ６００と同じパッケージ及び／又はダイに存在する。ここでは、コアの一部分（オンコアの部分）が、メモリ６７５又はグラフィックデバイス６８０等の他のデバイスとインタフェースするための１又は複数のコントローラ６７０を含む。これらデバイスとインタフェースするためのインターコネクト及びコントローラを含む構成は、しばしば、オンコアと称される（あるいはアンコア構成）。ある例として、バスインタフェース６０５は、メモリ６７５とインタフェースするためのメモリコントローラと、グラフィックデバイス６８０とインタフェースするためのグラフィックコントローラとを有するリングインターコネクトを含む。しかし、SOC環境では、更により多くのデバイス、例えばネットワークインタフェース、コプロセッサ、メモリ６７５、グラフィックデバイス６８０、及び、任意の他の公知のコンピュータデバイス／インタフェース等、を、単一のダイ又は集積回路に集積して、高い機能と低い電力消費とを持つ、スモールフォームファクタを提供してもよい。
【００６１】
実施形態は、多くの異なるシステムタイプに実装されてもよい。図７を参照すると、本発明の実施形態におけるシステムのブロック図が示されている。図７に示すように、マルチプロセッサシステム７００は、ポイントツーポイントインターコネクトシステムであり、ポイントツーポイントインターコネクト７５０を介して連結された第１のプロセッサ７７０と第２のプロセッサ７８０とを含む。図７に示すように、プロセッサ７７０及び７８０のそれぞれはマルチコアプロセッサであってよく、第１及び第２のプロセッサコア（つまりプロセッサコア７７４a及び７７４b及びプロセッサコア７８４a及び７８４b）を含んでよいが、潜在的に、より多くのコアがプロセッサ内に存在してもよい。
【００６２】
図７を依然参照すると、第１のプロセッサ７７０は更に、メモリコントローラハブ（MCH）７７２及びポイントツーポイント（P-P）インタフェース７７６及び７７８を含む。同様に、第２のプロセッサ７８０は、MCH７８２とP‐Pインタフェース７８６及び７８８とを含む。図７に示すように、MCH772及び７８２は、プロセッサを、それぞれのメモリ、つまり、メモリ７３２及びメモリ７３４に連結するが、これらは、それぞれのプロセッサにローカルに接続されたシステムメモリの部分（例えばDRAM）であってよい。プロセッサ７７０及び７８０のそれぞれは、本発明の実施形態において、レジスタファイルのエイリアスレジスタ（不図示）及びレジスタ割り当て論理（不図示）を含んでよく、これにより、エイリアスレジスタを、ループの複数のメモリアクセスオペレーションのそれぞれに割り当ててよい。エイリアスレジスタは、本発明の実施形態において、ループのオペレーションのパイプライン化されたスケジュールにより生じうるエイリアスを検出するために利用されてよい。
【００６３】
第１のプロセッサ７７０及び第２のプロセッサ７８０は、それぞれP−Pインターコネクト７６２及び７５４を介してチップセット７９０に連結されてよい。図７に示すように、チップセット７９０はP−Pインタフェース７９４及び７９８を含む。
【００６４】
更に、チップセット７９０は、P−Pインターコネクト７３９によって高いパフォーマンスのグラフィックエンジン７３８とチップセット７９０を連結するためのインタフェース７９２を含む。この代わりに、チップセット７９０が、インタフェース７９６を介して第１のバス７１６に連結されてよい。図７に示すように、様々な入出力（I／O）デバイス７１４が、第１のバス７１６を第２のバス７２０に連結するバスブリッジ７１８とともに、第１のバス７１６に連結されてよい。一実施形態では、例えばキーボード／マウス７２２、通信デバイス７２６、及びデータストアユニット７２８、例えばコード７３０を含んでよいディスクドライブ又はその他の大容量記憶装置等の様々なデバイスが第２のバス７２０に連結されてよい。更に、オーディオI／O７２４が第２のバス７２０に連結されてよい。実施形態は、スマートセルラーテレフォン、Ultrabook（登録商標）、タブレットコンピュータ、ネットブック等のモバイルデバイスを含む他のタイプのシステムに組み込むことができる。
【００６５】
以下の例が更なる実施形態に関している。
【００６６】
第１の例では、システムが、１又は複数のコアを含むプロセッサを含む。プロセッサは更に、ループの複数のオペレーションに関するメモリ範囲情報をストアするための複数のエイリアスレジスタを含むレジスタファイルも含む。メモリ範囲情報は、メモリ内の１又は複数のメモリ位置を参照する。プロセッサは更に、エイリアスレジスタそれぞれをループの対応するオペレーションに割り当てるためのレジスタ割り当て論理も含む。割り当ては、ローテーションスケジュールに従って行われてよく、エイリアスレジスタの少なくとも１つがループの第１のイタレーションの第１のオペレーション及びループの後続するイタレーションの第２のオペレーションに割り当てられる。
システムは更にプロセッサに連結されたメモリを含む。任意で、プロセッサは更に、パイプライン化されたスケジュールに従ってループのオペレーションをスケジュールするための命令スケジュール論理を含み、ここでループの少なくとも１つのオペレーションが、ループのオペレーションの順序とは異なる実行スケジュールに従って実行される。任意で、１又は複数のコアの１つが、第１のエイリアスレジスタにストアされているデータを、エイリアスレジスタの少なくとも他の１つにストアされているデータと比較することを実行して、エイリアスが存在するかを決定してよい。任意で、第１のエイリアスレジスタが、第１のライフタイムの間は第１のオペレーションに割り当てられてよく、第１のエイリアスレジスタが、第２のライフタイムの間は第２のオペレーションに割り当てられてよく、第１のライフタイム及び第２のライフタイムが、重ならない期間であってよい。任意で、第１のライフタイムがループの第１のイタレーションの範囲内であり、第２のライフタイムが、第１のイタレーションに連続する次のイタレーションであるループの第２のイタレーションの範囲内である。任意で、レジスタ割り当て論理が、ローテーション一掃命令を実行して、関連するライフタイムが期限切れになった各エイリアスレジスタの内容を削除してよい。
【００６７】
第２の例では、少なくとも１つのコンピュータ可読媒体が、実行されると、システムに、ローテーションレジスタファイルの複数のエイリアスレジスタのそれぞれを、ループの複数のイタレーションのためのローテーションシーケンスに従って連続してループの対応するオペレーションに割り当てる手順であって、各エイリアスレジスタが、対応するオペレーションがアクセスする１又は複数のメモリ位置のインディケーションをストアし、複数のエイリアスレジスタの１つは、ループの第１のイタレーションの第１のオペレーションと、ループの後続するイタレーションの第２のオペレーションとに割り当てられる、割り当てる手順を実行させる命令を含む。少なくとも１つのコンピュータ可読媒体は更に、割り当てられた複数のエイリアスレジスタの少なくとも１つの内容を、１又は複数の他の割り当てられたエイリアスレジスタの内容と比較することで、エイリアス条件が存在するかを決定するための命令も含む。第１のエイリアスレジスタを、第１のライフタイムの間は第１のオペレーションに割り当て、第１のエイリアスレジスタを、第２のライフタイムの間は第２のオペレーションに割り当て、第１のライフタイム及び第２のライフタイムは、重ならない期間であってよい。任意で、第１のライフタイム及び第２のライフタイムは、ループの連続した隣の複数のイタレーションのなかにある。
任意で、第１のライフタイム及び第２のライフタイムは、ループの隣り合わないイタレーションのなかにある。任意で、少なくとも１つのコンピュータ可読媒体は、実行されるとシステムに、順序関係に基づくオペレーションに対するライフタイムを、同じ又は異なるイタレーション内の別のオペレーションに割り当てさせ、対応するエイリアスレジスタを、ライフタイムの期間の間はオペレーションに割り当てさせる更なる命令を含む。任意で、少なくとも１つのコンピュータ可読媒体は、実行されるとシステムに、期間が期限切れになると、対応するエイリアスレジスタを、別のイタレーションの別のオペレーションに割り当て直させる命令を更に含む。任意で、少なくとも１つのコンピュータ可読媒体は、実行されるとシステムに、順序関係の存在に応じてエイリアスをチェックさせる命令を更に含み、順序関係は、パイプライン化されたスケジュールに従って、ループの第２のオペレーションの後に実行するようスケジュールされたループの第１のオペレーションと、ループの第１のオペレーションがループの第２のオペレーションの前に実行可能であるというループのインディケーションとに呼応して示される。
【００６８】
第３の例では、方法が、レジスタファイルの複数のエイリアスレジスタのそれぞれを、ループの複数のイタレーションのためのローテーションシーケンスに従って連続してループの対応するオペレーションに割り当てる段階であって、複数のエイリアスレジスタの１つを、ループの第１のイタレーションの第１のオペレーションと、ループの後続するイタレーションの第２のオペレーションとに割り当てることを含み、各エイリアスレジスタは、対応するオペレーションによりアクセスされる複数のメモリ位置のインディケーションをストアする、割り当てる段階を含む。e方法は更に、割り当てられた複数のエイリアスレジスタの少なくとも１つの内容を、１又は複数の他の割り当てられたエイリアスレジスタの内容と比較することで、エイリアス条件が存在するかを決定する段階を含む。任意で、方法は、第１のエイリアスレジスタを、第１のライフタイムの間は第１のオペレーションに割り当て、第１のエイリアスレジスタを、第２のライフタイムの間は第２のオペレーションに割り当てる段階を含み、第１のライフタイム及び第２のライフタイムは、重ならない期間である。
任意で、第１のライフタイム及び第２のライフタイムは、ループの連続した隣の複数のイタレーションのなかにある任意で、方法は、第１のエイリアスレジスタを、第１のライフタイムの間はループの第１のイタレーションの第２のオペレーションに割り当て、第１のエイリアスレジスタを、第２のライフタイムの間はループの第２のイタレーションの第１のオペレーションに割り当てる段階を含み、第１のライフタイム及び第２のライフタイムは、重ならない期間である。任意で、方法は、同じ板レーション又は異なるイタレーション内で別のオペレーションに対する順序関係に基づいてオペレーションに対してライフタイムを割り当てる段階と、対応するエイリアスレジスタを、ライフタイムの期間の間はオペレーションに割り当てる段階とを含む。任意で、方法は、期間が期限切れになると、対応するエイリアスレジスタを、別のイタレーションの別のオペレーションに割り当て直す段階を含む。任意で、方法は、ループの第１のオペレーションに割り当てられた第１のエイリアスレジスタの内容を、第２のオペレーションに関する第２のライフタイムの間、第２のオペレーションに割り当てられた第２のエイリアスレジスタの内容と比較することにより、ループの第１のイタレーションにエイリアスが存在するかを決定することを含み、第２のライフタイムは、第２のオペレーションの第２のスケジュールされた実行時間に対する第１のオペレーションの第１のスケジュールされた実行時間により決定される。
任意で、方法は、順序関係の存在に応じてエイリアスをチェックする段階を含み、順序関係は、パイプライン化されたスケジュールに従って、ループの第２のイタレーションの後に実行するようスケジュールされたループの第１のオペレーションと、ループの第１のオペレーションがループの第２のオペレーションの前に実行可能であるというループのインディケーションとに呼応して示される。
【００６９】
第４の例では、装置が、選択肢のうち１又は複数を含む、第３の例の方法を実行するよう構成されている。
【００７０】
第５の例では、プロセッサが、１又は複数のコアと、ループの複数のオペレーションに関連するメモリ範囲情報をストアするために複数のエイリアスレジスタを含むレジスタファイルであって、メモリ範囲情報は、メモリ内の１又は複数のメモリ位置を参照する、レジスタファイルと、複数のエイリアスレジスタのそれぞれをループの対応するオペレーションに割り当てるレジスタ割り当て論理とを含む。
割り当ては、ローテーションスケジュールに従って作成され、複数のエイリアスレジスタの少なくとも１つは、ループの第１のイタレーションの第１のオペレーションと、ループの後続するイタレーションの第２のオペレーションとに割り当てられる。システムは更に、プロセッサに連結されたメモリを含む。任意で、プロセッサは、パイプライン化されたスケジュールに従ってループの複数のオペレーションをスケジュールするための命令スケジュール論理を更に含み、ループの少なくとも１つのオペレーションは、ループの複数のオペレーションの順序と異なる実行スケジュールに従って実行される。任意で、１又は複数のコアの１つは、エイリアスが存在するかを決定するために、複数のエイリアスレジスタの他の少なくとも１つにストアされているデータに対する、第１のエイリアスレジスタにストアされているデータの比較を実行する。任意で、第１のエイリアスレジスタは、第１のライフタイムの間は第１のオペレーションに割り当てられ、第１のエイリアスレジスタは、第２のライフタイムの間は第２のオペレーションに割り当てられ、第１のライフタイム及び第２のライフタイムは、重ならない期間である。任意で、第１のライフタイムは、ループの第１のイタレーションの範囲内であり、第２のライフタイムが、第１のイタレーションに連続する次のイタレーションであるループの第２のイタレーションの範囲内である。任意で、レジスタ割り当て論理は、関連するライフタイムが期限切れになった各エイリアスレジスタの内容を削除するためのローテーション一掃命令を更に実行する。
【００７１】
実施形態は、多くの異なるタイプのシステムで利用してよい。例えば一実施形態では、通信デバイスは、ここに記載される様々な方法及び技術を実行するよう構成されてよい。もちろん、本発明の範囲は通信デバイスに限定はされず、他の実施形態が、命令を処理するための他のタイプの装置、又は、コンピューティングデバイス上で実行されることに呼応して、デバイスに、ここで記載される方法及び技術の１又は複数を実行させる命令を含む１又は複数の機械可読媒体を対象としていてよい。
【００７２】
実施形態はコードで実装されてよく、及び、システムを命令を実行するようプログラムするために利用することができる命令をストアした持続性記憶媒体にストアされてよい。ストア媒体は、これらに限定はされないが、フロッピー（登録商標）ディスク、光ディスク、固体ドライブ（ＳＳＤ）、ＣＤ−ＲＯＭ（コンパクトディスクリードオンリメモリ），ＣＤ−ＲＷ（コンパクトディスクリライタブル）、及び磁気光ディスク、リードオンリーメモリ（ＲＯＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）等のランダムアクセスメモリ（ＲＡＭ）、消去可能プログラマブルＲＯＭ（ＥＰＲＯＭ）、フラッシュメモリ、電気的消去可能プログラマブルＲＯＭ（ＥＥＰＲＯＭ（登録商標））、磁気又は光カード等の半導体素子、又は、電子命令をストアするのに適した任意の他のタイプの媒体を含んでよい任意のタイプのディスクを含んでよい。
【００７３】
本発明は、限定された数の実施形態に関して記載されたが、当業者であれば、様々な変形形態及び変形例を思いつくだろう。添付請求項はこれらの変形形態及び変形例を全て、本発明の真の精神及び範囲内に含まれるものとしてカバーすることを意図している。
【図１】
0006008265.tif 000002
【図２Ａ】
0006008265.tif 000003
【図２Ｂ】
0006008265.tif 000004
【図２Ｃ】
0006008265.tif 000005
【図３】
0006008265.tif 000006
【図４】
0006008265.tif 000007
【図５】
0006008265.tif 000008
【図６】
0006008265.tif 000009
【図７】
0006008265.tif 000010