(57)【要約】プロセッサ内のハードウェア並列実行レーン内で命令を効率的に処理するためのシステムおよび方法を提供する。識別されたループ内の所与の分岐点に応じて、コンパイラは、実行されると、処理対象の次の超大命令語（ＶＬＩＷ）のサイズを判断し、ターゲットプロセッサ内の複数の対応するＰＣレジスタに格納する複数のポインタ値を判断する、コードを生成する。更新されたＰＣレジスタは、所与の分岐点と対応する収束点との間の異なる基本ブロックから混ぜ合わされた命令をポイントする。ターゲットプロセッサは、単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャを含む。所与のレーンに対する割当ては、所与の分岐点において所与のレーンに対して実行時に検出された分岐方向に基づく。プロセッサは、ＰＣレジスタを実行レーンにマッピングするためのベクトルレジスタを含む。【選択図】図６
2016508640.tif 000002
【特許請求の範囲】
【請求項１】
単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャ内の複数の並列実行レーンと、
複数のプログラムカウンタ（ＰＣ）レジスタと、
所与の超大命令語（ＶＬＩＷ）内の複数の命令をフェッチするように構成された制御ロジックであって、前記複数のＰＣレジスタの各々は、前記複数の命令のうち一意の命令をポイントしているポインタ値を格納する、制御ロジックと、
を備え、
前記複数の実行レーンは、前記所与のＶＬＩＷ内のフェッチされた前記複数の命令を同時に実行するように構成されている、
プロセッサ。
【請求項２】
識別子（ＩＤ）を特定のビット範囲内に格納するように構成されたベクトルレジスタをさらに備え、
各ビット範囲は、前記複数の実行レーンのうち対応する実行レーンと関連付けられており、所与のＩＤは、前記複数のＰＣレジスタのうち所与のＰＣレジスタを識別する、請求項１に記載のプロセッサ。
【請求項３】
処理されるＶＬＩＷのサイズを格納するように構成されたサイズレジスタをさらに備える、請求項２に記載のプロセッサ。
【請求項４】
前記ベクトルレジスタに格納された有効なＩＤの数は、前記サイズレジスタに格納されたサイズと等しい、請求項３に記載のプロセッサ。
【請求項５】
前記制御ロジックは、
前記サイズレジスタに格納されたサイズに等しい数のフェッチされた命令を復号することと、
前記復号された命令のうち所与の命令を、少なくとも、前記複数の実行レーンのうち所与の実行レーンと関連付けられた前記ベクトルレジスタに格納されたＩＤと、前記複数のＰＣレジスタに格納された対応するポインタ値と、に基づいて、前記所与の実行レーンに割り当てることと、
を行うようにさらに構成されている、請求項３に記載のプロセッサ。
【請求項６】
前記複数の実行レーンのうち関連付けられた実行レーンは、資源に依存しない複数の命令をポイントしている前記複数のＰＣレジスタのうち所与のＰＣレジスタに応じて、前記資源に依存しない複数の命令を同時に実行するようにさらに構成されている、請求項５に記載のプロセッサ。
【請求項７】
前記制御ロジックは、ループの終わりに達している前記複数の実行レーンのうち所与の実行レーンに応じて、
前記所与の実行レーンが、前記ループの開始に分岐して戻るようにスケジューリングされているという実行時の判断に応じて、前記ベクトルレジスタ内の対応するビット範囲内にスリープ状態を書き込むことと、
前記所与の実行レーンが、前記ループの外部に分岐するようにスケジューリングされているという実行時の判断に応じて、前記ベクトルレジスタ内の前記対応するビット範囲内に終了状態を書き込むことと、
を行うようにさらに構成されている、請求項５に記載のプロセッサ。
【請求項８】
前記制御ロジックは、前記スリープ状態または前記終了状態にある前記所与の実行レーンに応じて、
前記所与の実行レーンの実行を停止することと、
少なくとも次のプログラムカウンタ（ＰＣ）と、所与のトレースに関する作業項目識別子（ＩＤ）と、を格納することと、
を行うようにさらに構成されている、請求項７に記載のプロセッサ。
【請求項９】
前記制御ロジックは、前記複数の実行レーンの各実行レーンが、前記スリープ状態または前記終了状態にあるという判断に応じて、それぞれ格納された次のＰＣに分岐することによって、実行レーンごとの実行を再開するようにさらに構成されている、請求項８に記載のプロセッサ。
【請求項１０】
前記制御ロジックは、前記複数の実行レーンの各実行レーンが停止されており、且つ、少なくとも１つの実行レーンが、別の実行レーンと異なる状態であることに応じて、それぞれ格納された次のＰＣに分岐することによって、スリープ状態にある実行レーンのみ実行を再開するようにさらに構成されている、請求項９に記載のプロセッサ。
【請求項１１】
コンピュータシステムの少なくとも１つのプロセッサによる実行のために構成された少なくとも１つのプログラムを格納しているコンピュータ可読記憶媒体であって、前記少なくとも１つのプログラムは、
ソフトウェアスレッドをハードウェア並列レーンに割り当てることと、
複数のプログラム命令内のループと対応する基本ブロックとを識別することと、
識別されたループ内の所与の分岐点に応じて、所与の超大命令語（ＶＬＩＷ）のサイズを判断することと、第１の数のプログラムカウンタ（ＰＣ）ポインタ値を、単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャを含むターゲットプロセッサ内の複数の並列実行レーンに実行時に割り当てることと、
を実行可能な命令を含む、
コンピュータ可読記憶媒体。
【請求項１２】
所与の実行レーンに対する割り当ては、前記所与の分岐点において前記所与の実行レーンに関して実行時に検出された分岐方向に基づいている、請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
フェッチされる次のＶＬＩＷ内の第２の数の命令を用いて前記サイズを更新するように実行可能な命令をさらに含む、請求項１２に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記第２の数のＰＣポインタ値の各々を、前記次のＶＬＩＷ内の前記第２の数の命令のうち一意の命令に対応するポインタを用いて更新することと、
前記複数の実行レーンの各々を、前記更新されたＰＣポインタ値のうち所与のＰＣポインタ値にマッピングする、複数のインデックスを更新することと、
を実行可能な命令をさらに含む、請求項１３に記載のコンピュータ可読記憶媒体。
【請求項１５】
所与の超大命令語（ＶＬＩＷ）内の複数の命令をフェッチすることであって、複数のＰＣレジスタの各々は、前記複数の命令のうち一意の命令をポイントしているポインタ値を格納する、ことと、
前記所与のＶＬＩＷ内のフェッチされた前記複数の命令を、単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャ内の複数の並列実行レーンで同時に実行することと、
を含む方法。
【請求項１６】
識別子（ＩＤ）を、ベクトルレジスタの特定のフィールドに格納することをさらに含み、
各フィールドは、前記複数の実行レーンのうち対応する実行レーンと関連付けられており、
所与のＩＤは、前記複数のＰＣレジスタのうち所与のＰＣレジスタを識別する、請求項１５に記載の方法。
【請求項１７】
処理されるＶＬＩＷのサイズを格納することをさらに含む、請求項１６に記載の方法。
【請求項１８】
前記ベクトルレジスタに格納されている有効なＩＤの数は、前記格納されたサイズに等しい、請求項１７に記載の方法。
【請求項１９】
前記格納されたサイズに等しい数のフェッチされた命令を復号することと、
前記復号された命令のうち所与の命令を、少なくとも、前記複数の実行レーンのうち所与のレーンと関連付けられた前記ベクトルレジスタに格納されたＩＤと、前記複数のＰＣレジスタに格納された対応するポインタ値と、に基づいて、前記所与の実行レーンに割り当てることと、
をさらに含む、請求項１７に記載の方法。
【請求項２０】
前記複数のＰＣレジスタのうち所与のＰＣレジスタが、資源に依存しない複数の命令をポイントしていることを検出したことに応じて、前記資源に依存しない複数の命令を、前記複数の実行レーンのうち関連付けられた実行レーンで同時に実行することをさらに含む、請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、コンピューティングシステムに関し、より詳細には、プロセッサ内のハードウェア並列実行レーンで命令を効率的に処理することに関する。
【背景技術】
【０００２】
コンピュータシステムのスループットを向上させるために、タスクの並列化が用いられている。この目的のために、コンパイラは、並列化されたタスクをプログラムコードから抽出して、システムハードウェア上で並行して実行し得る。ハードウェア上での並列実行を向上するために、プロセッサは、複数の並列実行レーン（例えば、単一命令複数語（ＳＩＭＤ）マイクロアーキテクチャ内など）を含み得る。このタイプのマイクロアーキテクチャは、特定のソフトウェアアプリケーションに対して、単一レーンのマイクロアーキテクチャまたは汎用マイクロアーキテクチャよりも高い命令スループットを提供し得る。ＳＩＭＤマイクロアーキテクチャから恩恵を受けるタスクのいくつかの例は、ビデオグラフィックスレンダリング、暗号化、およびガーベジコレクションを含む。
【０００３】
多くの場合、特定のソフトウェアアプリケーションは、各作業項目の実行や並列関数呼出しがその内部のデータ依存となるようなデータ並列処理を有する。例えば、第１の作業項目が第２の作業項目から独立したデータである場合には、第１および第２の作業項目の各々は、ＳＩＭＤマイクロアーキテクチャ内の別個の並列実行レーン上に同時にスケジューリングされている。しかし、第１および第２の作業項目の各々で実行されるある量の命令は、データ依存の場合がある。分岐命令として実装された条件テストは、第１の作業項目に対してパスし得るが、各作業項目に対するデータに依存する第２の作業項目に対しては不合格になり得る。
【０００４】
第２の作業項目が、実行を停止して、第１の作業項目が進行中の実行を継続するのを待機するので、並列実行の効率が低下し得る。パスしたテストに起因して２〜３の作業項目だけが実行を継続し、他方、不合格になったテストのために、ほとんどの作業項目がアイドルである場合には、効率の悪さが増大する。
【発明の概要】
【課題を解決するための手段】
【０００５】
プロセッサ内のハードウェア並列実行レーンで命令を効率的に処理するためのシステムおよび方法を検討する。様々な実施形態では、プロセッサは、単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャ内に複数の並列実行レーンを含む。プロセッサは、複数のプログラムカウンタ（ＰＣ）レジスタを含み得る。加えて、プロセッサは、可変長ＶＬＩＷ（ｖｅｒｙ  ｌａｒｇｅ  ｉｎｓｔｒｕｃｔｉｏｎ  ｗｏｒｄ）のサイズを格納するためのサイズレジスタを含み得る。プロセッサ内の制御ロジックは、サイクル内で、格納したサイズに等しい数の所与のＶＬＩＷ内の命令をフェッチし得る。制御ロジックは、格納したサイズに等しい数のＰＣレジスタを利用して、所与のＶＬＩＷ内の命令をフェッチし得る。複数のＰＣレジスタの各々は、複数のフェッチした命令のうち一意の命令をポイントしているポインタ値を格納する。複数の実行レーンは、所与のＶＬＩＷ内でいくつかの命令を同時に実行し得る。
【０００６】
また、プロセッサは、複数の実行レーンのうち対応する実行レーンと関連付けられたビット範囲を有するベクトルレジスタを含み得る。ビット範囲は識別子（ＩＤ）を格納し得る。所与のＩＤは、複数のＰＣレジスタのうち所与のＰＣレジスタを識別し得る。所与のＰＣレジスタは、実行用に関連付けられたレーンに対してフェッチされたＶＬＩＷ内の所与の命令をポイントしているポインタ値を格納し得る。
【０００７】
いくつかの実施形態では、バックエンドコンパイラは、ソフトウェアアプリケーションのプログラム命令を検査して、ループおよび対応する基本ブロックを識別する。ループ内の分岐点は、分岐命令を含み得る。例えば、ｉｆ−ｅｌｓｅｉｆ−ｅｌｓｅ構成、ｉｆ−ｅｌｓｅ構成、ｃａｓｅ構成などが、識別されたループ内のプログラム命令内で使用され得る。分岐点と対応する収束点との間で、翻訳されてコンパイルされたプログラム命令の実行中に、複数のトレースパスがトラバースされ得る。
【０００８】
コンパイル中、識別されたループ内の所与の分岐点に応じて、コンパイラは、翻訳されコンパイルされたプログラム命令を用いて、挿入するためのコードを生成し得る。挿入されるコードは、実行される際に、処理する次のＶＬＩＷのサイズを判断して、対応するＰＣレジスタ内に格納するポインタ値を判断し得る。更新されたＰＣレジスタは、所与の分岐点と対応する収束点との間の異なる基本ブロックから混ぜ合わされた命令をポイントし得る。例えば、４つの命令を有する基本ブロックＡと、６つの命令を有する基本ブロックＢとが、所与の分岐点と対応する収束点との間に存在する場合には、コンパイラは、命令を、６つのＶＬＩＷ内に配置し得る。最初の４つのＶＬＩＷは、基本ブロックＡおよび基本ブロックＢの各々から１つの命令を含み得る。２つの対応するＰＣレジスタが、これらの命令をポイントするように更新され得る。第１のＶＬＩＷは、基本ブロックＡおよび基本ブロックＢの各々からの第１の命令を含み得る。第２のＶＬＩＷは、基本ブロックＡおよび基本ブロックＢの各々からの第２の命令を含んでもよく、以下同様である。ＰＣレジスタが再度更新されて、基本ブロックＡおよび基本ブロックＢの各々の関連付けられた命令をポイントする。最後の２つのＶＬＩＷは、ｎｏｐ（ノーオペレーション）とともにグループ化された基本ブロックＢからの命令を含み得る。
【０００９】
所与のレーンに対する割り当ては、実行時に、所与の分岐点で、所与のレーンに対して検出された分岐方向に基づき得る。前述の例を続けると、ＶＬＩＷが、基本ブロックＡおよび基本ブロックＢから生成された第２のＶＬＩＷであって、所与のレーンに対する分岐命令が選択される場合には、所与のレーンには、第２のＶＬＩＷ内の基本ブロックＡ内の第２の命令が割り当てられ得る。分岐命令が選択されない場合、所与のレーンには、第２のＶＬＩＷ内の基本ブロックＢ内の第２の命令が割り当てられ得る。関連付けられたＰＣレジスタは、分岐方向に基づき、基本ブロックＡまたは基本ブロックＢの何れかの第２の命令をポイントしているポインタ値を格納する。
【００１０】
これらおよび他の実施形態は、以下の記述および図を参照すると、さらに理解されるであろう。
【図面の簡単な説明】
【００１１】
【図１】単一命令複数データ（ＳＩＭＤ）パイプライン実行フローの一実施形態の一般化されたブロック図である。
【図２】制御フローグラフの一実施形態の一般化されたブロック図である。
【図３】制御フローグラフに対する実行順序の一実施形態の一般化されたブロック図である。
【図４】プロセッサに対するＳＩＭＤマイクロアーキテクチャの論理レイアウトの一実施形態の一般化されたブロック図である。
【図５】オブジェクトコード配置の一実施形態の一般化されたブロック図である。
【図６】コンパイラ技術を用いて、プロセッサ内で複数の作業項目の並列実行を最適化するための方法の一実施形態の一般化されたフロー図である。
【図７】ハードウェア技術を用いて、プロセッサ内で複数の作業項目の並列実行を最適化するための方法の一実施形態の一般化されたフロー図である。
【図８】ハードウェア技術を用いて、プロセッサ内で複数の作業項目の並列実行を最適化するための方法の別の実施形態の一般化されたフロー図である。
【図９】オブジェクトコード配置の別の実施形態の一般化されたブロック図である。
【発明を実施するための形態】
【００１２】
実施形態は、様々な修正および代替形式を受け入れる余地があるが、特定の実施形態が例として図面に示され、本明細書で詳細に説明されている。しかし、図面およびそれに関する詳細な説明は、実施形態が、開示された特定の形式に限定されることを意図しておらず、それとは逆に、添付の請求項によって定義されるように、実施形態の趣旨および範囲に含まれる全ての修正、均等物および代替手段を包含することが理解されるべきである。
【００１３】
以下の記載では、実施形態の完全な理解を提供するために、多数の具体的な詳細が記載されている。しかし、当業者は、これらの具体的な詳細なしに、実施形態が実施され得ることを理解するはずである。いくつかの場合には、実施形態を曖昧にするのを避けるために、周知の回路、構造および技術が詳細に示されていない。
【００１４】
図１を参照すると、単一命令複数データ（ＳＩＭＤ）パイプライン実行フロー１００の一実施形態を示す一般化されたブロック図が示されている。命令１０２〜１０８はフェッチされ、関連するデータと共にＳＩＭＤパイプラインに送信されてもよい。並列で垂直な実行レーン内の複数の計算ユニットが示されている。いくつかの計算ユニットは、アクティブな計算ユニット１１０である。他の計算ユニットは、所与のパイプステージ中に無効にされていることに起因する、非アクティブな計算ユニット１１２である。制御ロジックおよび記憶素子（例えば、パイプラインレジスタなど）は、説明を容易にするために示されていない。
【００１５】
ハードウェア計算ユニットは、関連付けられたデータを使用して、所与の作業項目の所与の命令の実行を行うハードウェアを含む。このハードウェアは、加算、乗算、ゼロ検出、ビット単位シフト、除算、ビデオグラフィックスおよびマルチメディア命令、または、プロセッサ設計の当業者に周知の他の操作を実行するように構成された演算論理装置を含んでもよい。ＳＩＭＤパイプライン内に並列実行レーンを有するプロセッサの例は、グラフィック処理装置（ＧＰＵ）、デジタル信号処理（ＤＳＰ）などを含む。一実施形態では、ＳＩＭＤパイプラインは、ビデオカード上に配置されてもよい。別の実施形態では、ＳＩＭＤパイプラインは、マザーボード上に統合されてもよい。
【００１６】
ＳＩＭＤパイプラインは、ゲーム、エンタテインメント、科学および医療分野で使用される多種多様なデータ並列アプリケーションに対する計算性能を向上させ得る。かかるアプリケーションは、一般に、多数のオブジェクトについて同じプログラムを実行することを伴う。各オブジェクトは、他のオブジェクトと関係なく処理されるが、同じ順序の操作が使用されるので、ＳＩＭＤマイクロアーキテクチャは、相当な性能強化を提供する。ＧＰＵは、非グラフィック計算用にも想定されている。
【００１７】
ソフトウェアアプリケーションは、関数呼出しまたは計算カーネルの集合、および、内部関数の集合を含んでもよい。ソフトウェアプログラマは、関数呼出しを定義してもよく、他方、内部関数は所与のライブラリ内で定義されてもよい。例えば、ソフトウェアアプリケーションは、例えば画像ファイルなどの２次元（２Ｄ）配列のデータのデータ処理を実行し得る。ソフトウェアアプリケーションは、ソフトウェアプログラマによって開発されたアルゴリズムを、２Ｄ画像の画素ごとまたは２次元行列の要素ごとに、実行し得る。所与の関数呼出しは、インデックス空間を介して呼び出されてもよい。インデックス空間は、次元空間とも呼ばれ得る。データ並列ソフトウェアアプリケーションに対して、Ｎ次元計算領域は、１、２もしくは３次元空間、または、インデックス空間を定義してもよい。一例は、２Ｄ画像内の画素である。
【００１８】
関数呼出しは、データの１つ以上のレコードと照合されて、１つ以上の計算の作業項目を生成してもよい。従って、２つ以上の作業項目は、単一の関数呼出しの同じ命令を利用し得るが、データの異なるレコードについて動作し得る。関数呼出しは、フォーク（ｆｏｒｋ）を生成する制御フロー転送命令を含んでもよく、他方、コンピュータプログラム内のフォークは、通常、共通の定義によってソフトウェアスレッドを生成する。インデックス空間内の所与の時点における関数呼出しの所与のインスタンスが、「作業項目」と呼ばれてもよい。作業項目は、作業ユニットとも呼ばれてよい。前述の例を続けると、作業項目は、２Ｄ画像の所与の画素（所与のインデックス）に対応するデータのレコードについて、関数呼出し内の１つ以上の命令で動作してもよい。通常、作業項目は、関連付けられた一意の識別子（ＩＤ）を有する。
【００１９】
インデックス空間は、十分なハードウェアサポートがある場合に並行して実行する作業項目の総数を定義してもよい。例えば、インデックス空間は、２８０の数の作業項目を定義してもよいが、ＧＰＵは、いつでも６４の作業項目の同時実行をサポートし得る。作業項目の総数は、グローバルな作業サイズを定義し得る。作業項目は、さらに作業グループにグループ化され得る。各作業グループは、一意の識別子（ＩＤ）を有してもよい。所与の作業グループ内の作業項目は、相互に通信して、実行を同期させ、メモリアクセスを調整することが可能であってよい。いくつかの作業項目は、ＳＩＭＤ方式でＧＰＵ上での同時実行のためにウェーブフロント（ｗａｖｅ  ｆｒｏｎｔ）にクラスタ化されてもよい。２８０の総作業項目に対する前述の例に関して、ウェーブフロントは６４の作業項目を含んでもよい。
【００２０】
命令１０２〜１０８は、フェッチされて、関連付けられたデータと共にＳＩＭＤパイプラインに入ってもよい。命令１０４は、例えば条件分岐などの制御フロー転送命令であってよい。命令１０６は、条件が真の場合に実行されるパス内の第１の命令であってよい。命令１０８は、条件が偽の場合に実行されるパス内の第１の命令であってよい。例えば、分岐命令１０４は、高水準言語プログラムにおけるＩＦ文と関連付けられてもよい。命令１０６は、高水準言語プログラムにおけるＴＨＥＮ文と関連付けられてもよい。命令１０８は、高水準言語プログラムにおけるＥＬＳＥ文と関連付けられてもよい。
【００２１】
所与の行内の各計算ユニットは、同じ計算ユニットであってよい。これらの計算ユニットの各々は、同じ命令であるが、異なる作業項目と関連付けられた異なるデータについて動作してもよい。図に示すように、いくつかの作業項目は、条件分岐命令１０４によって提供されたテストをパスし、他の作業項目はテストに不合格になる。ＳＩＭＤパイプライン内の制御ロジックは、利用可能なパスの各々を実行して、現在のパスを選択しなかった作業項目に対応する実行ユニット（例えば、計算ユニットなど）を選択的に無効にしてもよい。例えば、Ｉｆ−Ｔｈｅｎ−Ｅｌｓｅ構成文の実行中、ＳＩＭＤアーキテクチャの各列内には、「Ｔｈｅｎ」（パスＡ）および「Ｅｌｓｅ」（パスＢ）のパスを実行するように構成された実行ユニットがある。
【００２２】
第１および第２の作業項目が実行を停止して、第３の作業項目が進行中の実行を継続するのを待機すると、並列実行の効率が低下し得る。従って、分岐命令１０４の実行後、所与の行における全ての計算ユニットがアクティブな計算ユニット１１０というわけではない。図に示すように、１つ以上の計算ユニットは、実行に関して無効にされた非アクティブな計算ユニット１１２である。多数の計算ユニットが所与のパイプステージ中に非アクティブである場合には、ＳＩＭＤコアの効率およびスループットが低下する。一実施形態では、「Ｅｌｓｅ」パスは、関数呼出しに対するリターン（ｒｅｔｕｒｎ）である。関数呼出しの実行が終了して、対応する作業項目がアイドルになる。しかし、ＳＩＭＤコア内の隣接する作業項目は、実行を継続してもよい。
【００２３】
ここで図２を参照すると、制御フローグラフ２００の一実施形態を示す一般化されたブロック図が示されている。一般的に言えば、制御フローグラフは、コンパイラ最適化器および静的解析ツールによって使用され得る。制御フローグラフ２００は、プログラムまたはプログラムの一部が、その実行中にトラバースされ得る全てのパスを表し得る。制御フローグラフでは、グラフ内の各ノードは、基本ブロックを表している。ほとんどの表現は、制御が制御フローグラフに入るための入口ブロックと、制御が制御フローグラフを出るための出口ブロックと、を含む。
【００２４】
コンパイル中、ソフトウェアアプリケーションは、基本ブロック０（ＢＢ  ０）から基本ブロック７（ＢＢ  ７）まで番号付けされた８つの基本ブロック（ＢＢ）を有する制御フローグラフ２００を提供し得る。８つの基本ブロックが示されているが、他の例では、別の数の基本ブロックが使用され得る。制御フローグラフ２００において、基本ブロック１が入口ブロックであり、基本ブロック６が出口ブロックである。基本ブロック０〜７の各々は、１つの入口点と１つの出口点とを有する命令のストレートラインシーケンスである。制御フローグラフ２００は、ループを表してもよい。ループの内部では、制御フローグラフ２００は、基本ブロック１〜４を有するＩＦ−ＴＨＥＮ−ＥＬＳＥ構成と、基本ブロック４〜６を有するＩＦ構成と、を表してもよい。
【００２５】
ここで図３を参照すると、制御フローグラフに対する実行順序３００の一実施形態を示す一般化されたブロック図が示されている。実行順序３１０は、既に示した制御フローグラフ２００がＳＩＭＤパイプラインに割り当てられた場合の典型的な実行順序を表している。単一のループの繰返しに対する実行時間は、ループ内の各基本ブロック（例えば、ＢＢ  １〜ＢＢ  ６など）の実行時間の合計である。しかし、所与の作業項目および対応するハードウェア実行レーンに対して、ＢＢ  ２およびＢＢ  ３のうち１つのみが実行される。同様に、ＢＢ  ５が所与の作業項目に対してスキップされ得る。特定の基本ブロックが所与の作業項目に対して実行されない可能性があるが、関連付けられた実行時間は、ループの繰返しに対する実行時間の総合計に寄与する。
【００２６】
実行順序３２０は、既に示した制御フローグラフ２００が、修正されたＳＩＭＤパイプラインに割り当てられた場合の代替の実行順序を表している。単一のループの繰返しに対する実行時間は、ループ内の各基本ブロックの実行時間の合計ではなく、単一のループの繰返し内で実際に実行された基本ブロックの実行時間の合計である。実行順序３２０は、制御フローグラフ２００の実行を変換する。コンパイラは、ソースコードのオブジェクトコードへのコンパイル中に、この変換を実行し得る。
【００２７】
いくつかの実施形態では、コンパイラは、各基本ブロックの終わりにコードを生成し、そのコードは、実行される際に、次に実行する基本ブロックを識別する。生成コードは、基本ブロックの終わりに挿入され得る。あるいは、制御を次の基本ブロックに転送する前に、制御フローを追加のコードに転送するために、分岐命令が基本ブロックの終わりに挿入され得る。追加のコードは、中央基本ブロックを示すＢＢ  Ｃによって表される。実行時、分岐する基本ブロックの各々（例えば、ＢＢ  １、ＢＢ  ４、ＢＢ  ６など）は、制御の転送先となる次の基本ブロックを識別する。識別は、分岐解決に基づくものであり、分岐解決は、データの特定レコードおよび分岐命令にさらに基づいている。実行時、ＢＢ  Ｃは、ターゲットの基本ブロックのアドレスを各作業項目から受信して、それぞれのターゲットの基本ブロックを実行するためのスレッドレジスタをセットアップする。ＳＩＭＤパイプライン内で実行されている異なる作業項目にわたって、所与の作業項目は、分岐、ジャンプおよびケース文などのように、制御フロー転送命令に対する単一のターゲットを有する。
【００２８】
実行順序３２０では、ＢＢ  ４の完了時に、第１の作業項目は、ＢＢ  ５に分岐して、対応するアドレスをＢＢ  Ｃに渡し得る。ＢＢ  ４の完了時に、第２の作業項目は、ＢＢ  ６に分岐して、対応するアドレスをＢＢ  Ｃに渡し得る。ターゲットプロセッサは、同時に実行される各ターゲット基本ブロックからの命令を含む、動的超大命令語（ＤＶＬＩＷ：ｄｙｎａｍｉｃ  ｖｅｒｙ  ｌａｒｇｅ  ｉｎｓｔｒｕｃｔｉｏｎ  ｗｏｒｄ）を生成し得る。ターゲットプロセッサによって実行される際に、コンパイラによって生成されたコードは、次のプログラムカウンタ（ＰＣ）値に応じて実行する次のＤＶＬＩＷのサイズを更新し得る。加えて、実行される際に、生成されたコードは、所与の並列実行レーン内で実行されている所与の作業項目と、所与のＰＣレジスタをポイントしているプログラムカウンタ識別子（ＰＣ  ＩＤ）との間のマッピングを更新し得る。所与のＰＣレジスタは、フェッチされる次のＤＶＬＩＷ内の命令のうち関連付けられた命令をポイントしているポインタまたはアドレスを保持し得る。
【００２９】
図４を参照すると、プロセッサに対するＳＩＭＤマイクロアーキテクチャの論理レイアウト４００の一実施形態を示す一般化されたブロック図が示されている。プロセッサは、データおよび命令を格納するためのダイナミックランダムアクセスメモリ（ＤＲＡＭ）４５０を有する。いくつかの実施形態では、所与のレベルのキャッシュメモリサブシステムが、ＤＲＡＭに加えて使用される。図に示すように、プロセッサは、計算ユニットの行ごとに、制御ロジック４２０と一緒にグループ化された比較的小規模のキャッシュメモリサブシステム４３０を有してもよい。説明を簡略にするために、パイプラインレジスタなどの記憶素子が示されていないが、プロセッサ内のデータフローは、パイプライン化されてもよい。所与のパイプラインのステージでは、このステージ内の関連付けられた命令が、既に不合格になったテスト（例えば、選ばれなかった分岐など）に基づいて実行されない場合には、計算ユニットは使用されない可能性がある。
【００３０】
ＳＩＭＤパイプラインは、レーンＡ〜Ｆを有する作業項目４６０を含む。レーンＡ〜Ｆの各々は、計算ユニットを含む垂直で並列なハードウェアレーンの各々に対応し得る。ＳＩＭＤパイプラインは、複数のプログラムカウンタ（ＰＣ）レジスタ４６６ａ〜４６６ｇを含む。ＰＣレジスタ４６６ａ〜４６６ｇの各々は、例えばｉ−キャッシュなどのメモリからフェッチする次のＤＶＬＩＷ内の関連付けられた命令をポイントしているポインタ値またはアドレスを格納し得る。動的超大命令語（ＤＶＬＩＷ）４６４は、例えばＩｎｓｔｒ  Ａ〜Ｉｎｓｔｒ  Ｇなどの複数の命令を含む。ＤＶＬＩＷ  ４６４内の命令Ｉｎｓｔｒ  Ａ〜Ｉｎｓｔｒ  Ｇの各々は、制御フローグラフ内の実行トレースを表す。ＤＶＬＩＷ  ４６４は、ＰＣレジスタ４６６ａ〜４６６ｇ内に格納された有効なポインタ値に基づいて、構築され配置され得る。ＳＩＭＤパイプラインを含むプロセッサは、ＤＶＬＩＷ  ４６４のサイズ、すなわち長さを格納するサイズレジスタ４６８をさらに含み得る。いくつかの実施形態では、サイズは、可変長ＤＶＬＩＷ内の命令数を表す整数であり得る。
【００３１】
また、パイプラインは、ベクトルレジスタ４６２を含んでもよい。ベクトルレジスタ４６２は、並列実行レーンの各々に対して、エントリ、フィールドまたはビット範囲を含んでもよい。各エントリは、ＰＣレジスタ４６６ａ〜４６６ｇのうち所与のＰＣレジスタを識別するための第１のビット数と、特別コードをサポートするための第２のビット数と、を含む、ビット総数を含んでもよい。特別コードは、待ち状態またはスリープ状態、ループ終了状態、ループを終了するため以外の実行を停止するためのバリア識別子、イベント識別子などを識別してもよい。
【００３２】
一例では、作業項目４６０内のレーンＢは、ＳＩＭＤパイプライン内の左から２番目の垂直な実行レーンに対応し得る。ベクトルレジスタ４６２内に格納された「ＰＣ  Ｂ」は、レーンＢと関連付けられて、ＤＶＬＩＷ  ４６４内の最初の命令をポイントし得る。ＰＣレジスタ４６６ｂは、ＤＶＬＩＷ  ４６４内のＩｎｓｔｒ  Ｂをポイントするアドレスまたはポインタ値を格納し得る。従って、レーンＢは、Ｉｎｓｔｒ  Ｂを受信して処理し得る。
【００３３】
図示していないが、命令キャッシュ（ｉ−キャッシュ）は、複数のＰＣ値を同時に受信するための複数のポートを含んでもよい。所与のクロックサイクルでは、ｉ−キャッシュは、ＤＶＬＩＷ  ４６４内の１つ以上の命令を同時にフェッチしてもよい。ｉ−キャッシュは、ＰＣレジスタ４６６ａ〜４６６ｇに格納された複数の受信した有効なＰＣ値を用いてもよい。ｉ−キャッシュは、ＰＣレジスタ４６６ａ〜４６６ｇに格納された複数のポインタまたはアドレスに加えて、サイズレジスタ４６８に格納されたサイズを受信してもよい。ｉ−キャッシュは、同一の有効なキャッシュラインまたはキャッシュセット内の１つ以上の命令にアクセスするための複数のデータポートを有してもよい。この場合、フェッチする有効な命令の数は、サイズレジスタ４６８からの受信したサイズに等しくなり得る。
【００３４】
ここで図５を参照すると、実行用に使用されるコード配置５００を示す一実施形態の一般化されたブロック図が示されている。ＳＩＭＤパイプラインを有するターゲットプロセッサは、複数のＰＣレジスタに格納されたポインタまたはアドレス値を用いて、ＤＶＬＩＷを構築してもよい。ターゲットプロセスは、各作業項目と関連付けられたデータのレコードを用いて、結果として生じたＤＶＬＩＷを実行してもよい。コード配置５００は、図２および図３にそれぞれ示す、制御フローグラフ２００および付随する実行順序３２０に関してプロセッサにより生成され得る、実行されたコードレイアウトを示している。コード配置５００は、実行順序３２０に対する、実行時におけるＰＣレジスタのＤＶＬＩＷ内の命令への割り当てを示している。この例では、４つのＰＣレジスタが使用される。
【００３５】
基本ブロックコード５０４は、各基本ブロックに対するコードを表す。例えば、基本ブロック０〜３，７に対するコードの１つのコピーが、配置５００内で実行されると示されている。基本ブロック４〜５に対するコードの２つのコピーが、配置５００内で実行されていると示されている。基本ブロック６に対するコードの４つのコピーが、配置５００内で実行されている。
【００３６】
コード５０２は、ループなどの領域のエントリに対して、コンパイラによって生成および挿入され得る。後に実行される場合、コード５０２は、次のＤＶＬＩＷのサイズを更新し、フェッチされたＤＶＬＩＷ内の命令と、ターゲットプロセッサ内のＰＣレジスタとの間のマッピングを更新し得る。例えば、ターゲットプロセッサ内のサイズレジスタおよびベクトルレジスタは、それらに格納された内容を、実行されたコード５０２によって更新させてもよい。図に示すように、コード５０２は、基本ブロック０，１，７の開始時に挿入され得る。
【００３７】
コード５０６は、基本ブロック１，４，６などの分岐点に移行するために、コンパイラによって生成および挿入され得る。後に実行される場合、コード５０６は、ＤＶＬＩＷのサイズ変更、および、フェッチされたＤＶＬＩＷ内の命令とターゲットプロセッサ内のＰＣレジスタとの間の対応するマッピング変更を判断し得る。従って、サイズおよびマッピングが、制御フローグラフ内の分岐点および収束点において更新される。コンパイラは、ＤＶＬＩＷのサイズが変わる点、および、マッピングが変わる点を識別する。第１のインデックスがトレース識別子（ＩＤ）を示し、第２のインデックスが基本ブロック（ＢＢ）ＩＤを示す表記法ＢＢＣ（０，１）を使用すると、コード５０６を挿入するための識別された点は、ＢＢＣ（０，１）、ＢＢＣ（０，４）、ＢＢＣ（０，６）、ＢＢＣ（１，４）、ＢＢＣ（１，６）、ＢＢＣ（２，６）およびＢＢＣ（３，６）に存在し得る。この例におけるトレースＩＤは、対応するＰＣレジスタと同じであってよい。
【００３８】
制御フローグラフ２００の実行の開始時に、コード５０２は、初期化ステップを実行して、ＤＶＬＩＷサイズを１に設定してもよい。ベクトルレジスタの各エントリ内のＰＣ  ＩＤが、例えばＰＣ  ０などのように、ＢＢ  ０内の同じ命令をポイントするように設定されてもよい。ＰＣ  ０は、値０または別の適切な開始アドレスを格納してもよい。図に示すように、４つの可能な並列トレースが存在しているが、作業項目の数は独立であってよい。例えば、ＳＩＭＤパイプラインは、割り当てられた作業項目を処理するための、８、１６、６４または別の数の並列実行レーンを有してもよい。ＳＩＭＤパイプライン内の各作業項目は、ベクトルレジスタ内に０が格納されたＰＣ  ＩＤを有しており、同じ命令を実行し得る。各作業項目に対するこの同じ命令は、ＢＢ  ０からの命令である。ＢＢ  ０内の命令は、各作業項目によって１つずつ実行され、各命令フェッチの後にＰＣが増加する。
【００３９】
ＢＢ  ０の実行が完了した後、ループ入口ブロックであるＢＢ  １が次に処理される。コード５０２は、ＢＢ  １の開始時に、ＤＶＬＩＷサイズを１として保持し、各作業項目に対するＰＣ  ＩＤを０として保持する。ベクトルレジスタのエントリの各々のＰＣ  ＩＤは、例えばＰＣ  ０などのように、ＢＢ  １内の同じ命令をポイントするように設定され得る。ＰＣは、ＢＢ  ０の完了時に達した値から増加した値のままであってよい。ＢＢ  １内の命令は、各作業項目によって１つずつ実行され、各命令フェッチ後にＰＣが増加する。
【００４０】
実行される際に、コード５０６は、ＢＢ  １の終わりにあるＢＢＣ（０，１）において、格納されたＤＶＬＩＷサイズを１から２に変更する。ここで、ＢＢ  ３内の命令は、フェッチされたＤＶＬＩＷに追加される。さらに、実行される際に、コード５０６は、ＢＢＣ（０，１）にて、ＢＢ  ３に分岐する作業項目に対するベクトルレジスタ内のエントリを、値ＰＣ  １を格納するように設定する。ＢＢ  ２に分岐する作業項目に対するベクトルレジスタ内のエントリは、ＰＣ  ０を継続して格納することにより、変更されないままである。０および１の値がこのように使用されるが、対応する指示およびマッピングを設定するために他の数値が使用されてもよい。この時点で、ＤＶＬＩＷは２つの命令を有し、これらは、２つの別個の基本ブロックＢＢ  ２およびＢＢ  ３からフェッチされ混ぜ合わされた命令である。複数のＰＣレジスタが継続して増加されるので、フェッチされたＤＶＬＩＷは、ＢＢ  ２の処理が完了するまで、これらの２つの基本ブロックからの混ぜ合わされた命令を含み続ける。
【００４１】
ＢＢ  ２の完了時に、ＤＶＬＩＷサイズは２のままである。ベクトルレジスタ内に格納されたＰＣ  ＩＤもそれらの値のままである。しかし、この時、ＰＣ  ０は、ＢＢ  ２ではなく、ＢＢ  ４内の命令に対応する。ＢＢＣ（０，４）の完了時に、コード５０６は、トレース０内のＢＢ  ４の終わりにおいて、３を格納するようにサイズレジスタを更新し、ＢＢ  ６に分岐する作業項目に対するベクトルレジスタ内のエントリを、ＰＣ  ２を格納するように更新する。複数のＰＣレジスタ内に格納された複数のアドレスおよび格納されたサイズをｉ−キャッシュに送信した後に、３つの命令がｉ−キャッシュからフェッチされる。長さ３のＤＶＬＩＷは、フェッチされた命令からターゲットプロセス内で構築される。ＤＶＬＩＷは、ＢＢ  ３またはＢＢ  ４と、ＢＢ  ５と、ＢＢ  ６とから混ぜ合わされた命令を含む。
【００４２】
ベクトルレジスタ内に関連する格納された０のＰＣ  ＩＤを有する作業項目は、ＢＢ（０，５）からフェッチされた命令を得る。ベクトルレジスタ内に関連する格納された１のＰＣ  ＩＤを有する作業項目は、どの程度までアドレスが増加されているかに応じて、ＢＢ（１，３）またはＢＢ（１，４）の何れかから結果を得る。ベクトルレジスタ内に関連する格納された２のＰＣ  ＩＤを有する作業項目は、ＢＢ（２，６）からフェッチされた命令を得る。
【００４３】
ＢＢＣ（１，４）の完了時に、コード５０６は、トレース１内のＢＢ  ４の終わりにおいて、４を格納するようにサイズレジスタを更新し、ＢＢ（３，６）に分岐する作業項目に対するエントリを、３のＰＣ  ＩＤを格納するように更新する。複数のＰＣレジスタ内に格納された複数のアドレスおよび格納されたサイズをｉ−キャッシュに送信した後に、４つの命令がｉ−キャッシュからフェッチされる。長さ４のＤＶＬＩＷは、フェッチされた命令からターゲットプロセッサ内で構築される。ＤＶＬＩＷは、ＢＢ  ６の第１のコピーと、ＢＢ  ５の単一のコピーと、ＢＢ  ６の第２のコピーと、ＢＢ  ６の第３のコピーと、から混ぜ合わされた命令を含む。ベクトルレジスタ内に関連する格納された０のＰＣ  ＩＤを有する作業項目は、ＢＢ（０，６）からフェッチされた命令を得る。ベクトルレジスタ内に関連する格納された１のＰＣ  ＩＤを有する作業項目は、ＢＢ（１，５）から結果を得る。ベクトルレジスタ内に関連する格納された２のＰＣ  ＩＤを有する作業項目は、ＢＢ（２，６）からフェッチされた命令を得る。ベクトルレジスタ内に関連する格納された３のＰＣ  ＩＤを有する作業項目は、ＢＢ（３，６）からフェッチされた命令を得る。
【００４４】
ＢＢ（０，６）、ＢＢ（１，６）、ＢＢ（２，６）およびＢＢ（３，６）の各々に対して、制御フローは、ＢＢ  ６の終わりにおいて、ループの別の繰り返しのためにＢＢ  １に戻ってもよいし、ループを終了してもよい。関連付けられた分岐命令および対応するレコード内のデータは、実行時に制御フローの方向を判断するであろう。いくつかの作業項目は、別の繰り返しを継続してもよく、他の作業項目は、ループを終了してもよい。特別コード状態は、ベクトルレジスタ内の対応するエントリ内に格納され、どのパスが選ばれるかを示してもよい。所与の作業項目が別のループの繰返しを継続し、複数の作業項目のうち少なくとも１つの他の作業項目が、関連付けられた基本ブロックに対するコードを処理しているという判断に応じて、スリープ状態符号化は、所与の作業項目に対するベクトルレジスタ内の関連付けられたエントリに格納され得る。
【００４５】
所与の作業項目がループを終了するという判断に応じて、終了状態符号化は、所与の作業項目に対するベクトルレジスタ内の関連付けられたエントリに格納され得る。スリープ状態符号化および終了状態符号化の各々は、ループ繰返し中に使用されるＰＣ  ＩＤから一意であって、互いに一意である。いくつかの実施形態では、スリープ状態または終了状態にある所与の作業項目に対して、コード５０６は、所与の作業項目の実行を停止して、少なくとも次のプログラムカウンタ（ＰＣ）および作業項目識別子（ＩＤ）を、例えば高速読み出しのためのスタックメモリなどのメモリに格納する。
【００４６】
コード５０６は、ＢＢ  ６の終わりにおいて、各作業項目の状態をチェックし得る。各作業項目がスリープ状態であるか、または各作業項目が終了状態であるという判断に応じて、プロセッサは、コード５０６を実行している間に、それぞれの格納された次のＰＣに分岐することにより、各作業項目に対する実行を再開し得る。各作業項目が停止されており、且つ、少なくとも１つの作業項目が別の作業項目と異なる状態にあるという判断に応じて、プロセッサは、コード５０６を実行している間に、それぞれの格納された次のＰＣに分岐することにより、スリープ状態にある作業項目のみについて実行を再開し得る。少なくとも１つの作業項目が、依然として、ループ内の基本ブロックにある命令を処理している場合には、その少なくとも１つの作業項目について実行を継続する一方で、特別な状態にある他の作業項目を待機する。スリープ状態を終えている作業項目は、ＢＢ  １に分岐して戻る。また、コード５０２は、ＢＢ  １の開始時に、ベクトルレジスタおよびサイズレジスタを初期化する。終了状態を終えている作業項目は、ＢＢ  ７に分岐する。また、コード５０２は、ＢＢ  ７の開始時に、それに応じて、ベクトルレジスタおよびサイズレジスタを再初期化する。
【００４７】
前述の例では、ループは単一の出口を有する。複数の出口を有する他の場合には、例えば、少なくとも次のＰＣおよび作業項目ＩＤなどのような対応する状態情報が、例えばスタックなどのメモリに格納され得る。後に、状態情報は、再開のために、例えばスタックからポップするなどのように取得され得る。スリープ状態または終了状態にある両方の作業項目は、例えばスタックなどのメモリに格納された状態情報を有し得る。異なる作業項目が異なるループ繰返しでループを終了し得るので、状態情報を有する複数のエントリが、例えばスタックなどのメモリに置かれ得る。再開時において、実行される際に、コンパイラ生成コードが状態情報をポップして、同じ次のＰＣから再開する作業項目に対する情報を組み合わせ得る。
【００４８】
ここで図６を参照すると、コンパイラ技術を用いて、プロセッサ内で複数の作業項目の並列実行を最適化するための方法６００の一実施形態が示されている。議論を進めるために、本実施形態、および後述する方法の後続の実施形態におけるステップは、連続した順序で示されている。しかし、他の実施形態では、いくつかのステップは、示されたものとは異なる順番で起こってもよく、いくつかのステップは同時に実行されてもよく、いくつかのステップは他のステップと組み合わされてもよく、また、いくつかのステップは存在しなくてもよい。
【００４９】
ブロック６０２では、ソフトウェアプログラムまたはサブルーチンが検出され解析され得る。プログラムコードは、設計者により、例えばＣまたは別の言語などの高水準言語で書かれてもよい。このソフトウェアプログラムは、ゲーム、ビジネス、医療および他の分野などにおいて、並列データアプリケーションのコンパイルおよび実行のために書かれてもよい。プログラムコードは、ソフトウェアアプリケーション、サブルーチン、ダイナミックリンクライブラリ、または他の任意の部分を指してもよい。パス名は、ユーザーによりコマンドプロンプトに対して入力され得る。あるいは、パス名は、ソースコードのコンパイルを開始するために、所与のディレクトリ位置、またはその他から読み込まれてもよい。プログラムコード内の命令は、検査され、翻訳され、最適化されて、コンパイル中にさらに処理されてもよい。
【００５０】
いくつかの実施形態では、ソースコードが静的にコンパイルされる。かかる実施形態では、フロントエンドのコンパイル中に、ソースコードが中間表現（ＩＲ）に翻訳されてもよい。バックエンドのコンパイルステップは、ＩＲを機械コードに翻訳してもよい。静的なバックエンドコンパイルは、さらなる変換および最適化を実行してもよい。他の実施形態では、ソースコードは、ジャストインタイム（ＪＩＴ）方式でコンパイルされる。ＪＩＴ方式は、システム構成を取得した後に、適切なバイナリコードを生成し得る。何れの方法でも、コンパイラは、関数呼出し、ループ、ループ内のトレースおよびプログラムコード内の基本ブロックを識別し得る。１つ以上の制御フローグラフが、プログラム解析中に構築され得る。
【００５１】
様々な実施形態では、プログラムコードは、例えば汎用プロセッサなどのプロセッサ上でコンパイルされる。プログラムコードは、ターゲットプロセッサに対してコンパイルされてもよく、ターゲットプロセッサは、例えばＳＩＭＤマイクロアーキテクチャなどの並列マイクロアーキテクチャを含む。データの１つ以上の関連付けられたレコードは、１つ以上の作業項目を生成するために、関数呼出しに割り当てられてもよい。
【００５２】
プログラムコード内の任意の分岐点を検出する前に、コンパイラは、解析され翻訳された命令を、それらがプログラムコード内に出現する通りにメモリ内に配置し得る。基本的に、コンパイラは、１のサイズを有するＶＬＩＷを生成している場合がある。コンパイラが、識別されたループ内で分岐点を検出すると（条件ブロック６０４：はい）、ブロック６０６において、実行されると、フェッチする次のＶＬＩＷのサイズを更新する、生成されたコードが挿入されてもよい。コンパイラは、コードおよびデータのレコードを、ターゲットプロセッサが超大命令語（ＶＬＩＷ）を生成するのを可能にするような方法でセットアップしてもよい。コンパイラは、分岐点と対応する収束点との間の複数の基本ブロックから混ぜ合わされた命令のプログラムカウンタ（ＰＣ）値を追跡してもよい。生成されたコードが実行される際に、複数のＰＣ値が、後でターゲットプロセッサに伝達され得る。データの１つ以上の関連付けられたレコードは、ＶＬＩＷ内の混ぜ合わされた命令を一緒にするために追跡され、１つ以上の関連付けられた作業項目を生成する。
【００５３】
ブロック６０８では、コンパイラは、実行される際に、ＶＬＩＷ内の命令をポイントしている複数のＰＣレジスタを、ターゲットプロセッサ内の複数の並列実行レーンのうち所与のレーンにマッピングするようなコードを挿入し得る。あるいは、マッピングは、オフセットと作業項目ＩＤとの間であってよい。ブロック６１０では、コンパイラは、実行される際に、ＶＬＩＷサイズと、フェッチする次のＶＬＩＷのマッピングとを更新する、生成されたコードを挿入し得る。ブロック６１２では、実行される際に、スリープ状態または終了状態になろうとしている実行レーンに対する状態情報を格納する、生成されたコードが、ループの終わりに挿入され得る。
【００５４】
ここで図７を参照すると、ハードウェア技術を使用して、プロセッサ内で複数の作業項目の並列実行を最適化するための方法７００の一実施形態が示されている。議論を進めるために、本実施形態、および後述する方法の後続の実施形態におけるステップは、連続した順序で示されている。しかし、他の実施形態では、いくつかのステップは、示されたものとは異なる順番で起こってもよく、いくつかのステップは同時に実行されてもよく、いくつかのステップは他のステップと組み合わされてもよく、また、いくつかのステップは、存在しなくてもよい。
【００５５】
ブロック７０２では、データの関連付けられたレコードが、複数の作業項目を生成するために、コンパイル済みコードに割り当てられる。いくつかの実施形態では、オペレーティングシステムが割り当てを実行し得る。ブロック７０４では、作業項目が、単一命令複数データ（ＳＩＭＤ）マイクロアーキテクチャを有するターゲットプロセッサに対してスケジューリングされる。ブロック７０６では、フェッチする次のＶＬＩＷのサイズを有するサイズレジスタが更新される。ブロック７０８では、複数のＰＣレジスタのうち１つ以上のＰＣレジスタが更新される。複数のＰＣレジスタは、構築されるＶＬＩＷ内の対応する語へのポインタまたはアドレスを格納し得る。
【００５６】
ブロック７１０では、作業項目を実行している並列実行レーンに複数のＰＣレジスタをマッピングするために使用されるベクトルレジスタが更新される。並列実行レーンのうち所与の並列実行レーンに対応する特定のフィールドまたはエントリが、ＰＣ識別子（ＩＤ）を格納し得る。ＰＣ  ＩＤは、関連付けられた実行レーンによって処理するために、命令のアドレスを読み取る複数のＰＣレジスタのうち１つのＰＣレジスタを識別し得る。更新されたサイズおよび複数のプログラムカウンタ（ＰＣ）を使用して、ブロック７１２では、プロセッサは、更新されたサイズに等しい数の命令をｉ−キャッシュからフェッチしてもよい。フェッチされた命令は、ループ内の分岐点と収束点との間の別個の基本ブロックからのものであってよい。ブロック７１４では、ターゲットプロセッサは、フェッチした命令を有するＶＬＩＷを構築するために、ベクトルレジスタを読み取ってもよい。ベクトルレジスタに格納されたマッピング情報は、所与の作業項目および対応する実行レーンに対して、ＶＬＩＷ内のどの命令を処理すべきかを判断し得る。ターゲットプロセッサは、フェッチした命令を、作業項目を実行している並列実行レーンにマッピングし得る。
【００５７】
ここで図８を参照すると、ハードウェア技術を使用して、プロセッサ内で複数の作業項目の並列実行を最適化するための方法８００の別の実施形態が示されている。議論を進めるために、本実施形態、および後述する方法の後続の実施形態のステップは、連続した順序で示されている。しかし、他の実施形態では、いくつかのステップは、示すものとは異なる順番で起こってもよく、いくつかのステップは同時に実行されてもよく、いくつかのステップは他のステップと組み合わされてもよく、いくつかのステップは、存在しなくてもよい。
【００５８】
ブロック８０２では、構築されたＶＬＩＷ内の命令は、ターゲットプロセッサ内の並列実行レーンを用いて、同時に実行される。所与の作業項目についてループの終わりに達し（条件ブロック８０４：はい）、アクティブな作業項目が検出されない（条件ブロック８０６：いいえ）場合には、ブロック８１０において、それぞれの状態情報が、並列実行レーンに割り当てられた作業項目ごとに読み取られる。状態情報は、少なくとも次のＰＣおよび作業項目ＩＤを含み得る。状態情報は、並列実行レーン内で実行を継続するために使用され得る。
【００５９】
所与の作業項目についてループの終わりに達し（条件ブロック８０４：はい）、何れかの作業項目がアクティブであると検出された（条件ブロック８０６：はい）場合には、ブロック８１２において、所与の作業項目に対する状態情報が、後で使用するために格納される。所与の作業項目は、実行を停止させてもよいし、スリープ状態または終了状態に置かれてもよい。
【００６０】
ここで図９を参照すると、オブジェクトコード配置９００を示す別の実施形態の一般化されたブロック図が示されている。コード配置９００は、図２および図３にそれぞれ示す制御フローグラフ２００および付随する実行順序３２０に対するコードを実行する際にプロセッサによって生成される配置の一実施形態を示している。コード５０２〜５０６は、既に説明したものと同じ機能を実行し得る。
【００６１】
基本ブロックのサイズはコンパイル時に分かっている。コンパイラは、ＰＣを追跡して、初期化コードを最小限にしてＤＶＬＩＷサイズを削減するようにプログラムコードの命令をスケジューリングし得る。制御フローグラフ２００およびコード配置５００を使用する前述の例では、ＢＢ  ６の４つのコピーが使用される。コンパイラは、ギャップを取り入れることにより、トレース数および付随のＰＣレジスタＩＤを削減し得る。ギャップは、ｎｏｐ操作を利用し得る。
【００６２】
コード配置５００に関して前述したステップがここで使用され得る。ＢＢ  ２の完了時に、ＤＶＬＩＷサイズは２のままである。しかし、フェッチされたＤＶＬＩＷ内の２つの命令のうち１つの命令は、配置９００内のギャップを提供するｎｏｐ操作である。ＰＣレジスタＩＤ  ０はｎｏｐ操作に対応しており、ＰＣレジスタＩＤ  １はＢＢ  ３内の命令に対応している。ＢＢ  ３の完了時に、ＤＶＬＩＷは、２から１に減らされる。この時、ＰＣレジスタＩＤ  ０はＢＢ  ４内の命令に対応しており、ＰＣレジスタＩＤ  １はｎｏｐ操作に対応している。
【００６３】
ＢＢＣ（０，４）の完了時に、プロセッサは、トレース０内のＢＢ  ４の終わりにおいてコード５０６の実行中に、サイズレジスタを１から２に更新する。また、実行されたコード５０６は、ＢＢ  ６に分岐している作業項目に対するベクトルレジスタ内のエントリを、ＰＣ  ＩＤ  １を格納するように更新する。２つのＰＣレジスタ値および格納されたサイズをｉ−キャッシュに送信した後に、２つの命令がｉ−キャッシュからフェッチされ得る。２つのフェッチされた命令は、ＢＢ  ５およびＢＢ  ６からの混ぜ合わされた命令を含む。ベクトルレジスタ内に関連する格納された０のＰＣレジスタＩＤを有する作業項目は、ＢＢ（０，５）からフェッチされた命令を得る。ベクトルレジスタ内に関連する格納された１のＰＣレジスタＩＤを有する作業項目は、ＢＢ（１，６）からフェッチされた命令を得る。
【００６４】
ＢＢ（１，６）の完了時に、コード５０６は、ＤＶＬＩＷサイズを２から１に更新する。ＢＢ（１，６）に対応する作業項目は、実行を停止して、状態情報を格納し、次のＰＣで実行を再開するまで待機する。次のＰＣは、ＢＢ  １またはＢＢ  ７をポイントしてもよい。前述したように、他のステップが実行されてもよい。コード配置９００は、検出された所与の分岐点と対応する収束点との間の第１のトレースパスが、所与の分岐点と対応する収束点との間の第２のトレースパスよりも小さいという判断に応じて、コンパイラが、第１のトレースパスの完了と対応する収束点との間で生成されたＶＬＩＷ内の第２のトレースパスに対応する命令とともにｎｏｐをグループ化し得ることを示す。
【００６５】
前述した実施形態の各々に対して、コードを、ループの外部でループ内のコードと並列化することによって、さらなる並列化が生じてもよい。例えば、ＢＢ  ７に対するプログラムコードは、ループを完了する作業項目に対するプログラムを終了するために、ＢＢ  １と並列化されてもよい。また、ＰＣレジスタＩＤが、単一の命令ではなく、ＶＬＩＷ内の複数の資源に依存しない命令に対応していることの検出に応じて、関連付けられた作業項目および実行レーンが、実行レーン内の複数の資源に依存しない命令を同時に実行してもよい。
【００６６】
さらに、コンパイラは、レジスタ割当てを使用して、ＤＶＬＩＷサイズを削減してもよい。プログラムコードは、次の文：Ｘ＝（Ａ＋Ｂ）＋（Ｂ＋Ｍ）を含み得る。ここでは、２つの演算が同じ演算コードを使用する。第１のトレースは、Ｔ１＝Ａ＋ＢなどのＡＤＤ演算を含む。第２のトレースは、Ｔ２＝Ｃ＋ＤなどのＡＤＤ演算を含む。０などのＰＣレジスタＩＤを有する基本ブロックＸ（ＢＢ  Ｘ）からのＴ１を使用する作業項目がある。１などのＰＣレジスタＩＤを有するＢＢ  ＹからのＴ２を使用する他の作業項目がある。第１のオペランド対「Ｃ」および「Ａ」、第２のオペランド対「Ｂ」および「Ｄ」、ならびに、結果対「Ｔ１」および「Ｔ２」の各々が、ＢＢ  ＸおよびＢＢ  Ｙ内の同じレジスタに割り当てられる場合には、式ｒ３＝ｒ１＋ｒ２が、１のサイズを有するＤＶＬＩＷとして使用され得る。復号時間を節約するか、またはスロットを解放するために、対応するＰＣレジスタＩＤが０に設定され得る。
【００６７】
前述の実施形態は、ソフトウェアを含み得ることに留意されたい。かかる実施形態では、方法および／または機構を実装するプログラム命令は、コンピュータ可読媒体上で伝達され、または格納され得る。プログラム命令を格納するように構成されている多数のタイプの媒体が利用可能であり、ハードディスク、フロッピィ（登録商標）ディスク、ＣＤ−ＲＯＭ、ＤＶＤ、フラッシュメモリ、プログラマブルＲＯＭ（ＰＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および、様々な他の形式の揮発性または不揮発性記憶装置を含む。一般的に言えば、コンピュータアクセス可能記憶媒体は、命令および／またはデータをコンピュータに提供するために、使用中にコンピュータによってアクセス可能な任意の記憶媒体を含み得る。例えば、コンピュータアクセス可能記憶媒体は、磁気または光媒体などの記憶媒体、例えば、ディスク（固定または取り外し可能）、テープ、ＣＤ−ＲＯＭもしくはＤＶＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、または、Ｂｌｕ−Ｒａｙ（登録商標）を含み得る。記憶媒体は、ＲＡＭ（例えば、シンクロナスダイナミックＲＡＭ（ＳＤＲＡＭ）、ダブルデータレート（ＤＤＲ、ＤＤＲ２、ＤＤＲ３など）ＳＤＲＡＭ、低電力ＤＤＲ（ＬＰＤＤＲ２など）ＳＤＲＡＭ、ラムバスＤＲＡＭ（ＲＤＲＡＭ）、スタティックＲＡＭ（ＳＲＡＭ）など）、ＲＯＭ、フラッシュメモリ、ユニバーサルシリアルバス（ＵＳＢ）インタフェースなどの周辺インタフェースを経由してアクセス可能な不揮発性メモリ（例えば、フラッシュメモリ）などの、揮発性または不揮発性メモリ媒体をさらに含み得る。記憶媒体は、微小電気機械システム（ＭＥＭＳ）、ならびに、ネットワークおよび／または無線リンクなどの通信媒体を経由してアクセス可能な記憶媒体を含み得る。
【００６８】
さらに、プログラム命令は、例えばＣなどの高水準プログラミング言語、例えばＶｅｒｉｌｏｇ、ＶＨＤＬなどの設計言語（ＨＤＬ）、または、例えばＧＤＳ  ＩＩストリーム形式（ＧＤＳＩＩ）などのデータベース形式、におけるハードウェア機能の動作レベル記述またはレジスタ転送レベル（ＲＴＬ）記述を含み得る。いくつかの場合には、記述は、合成ライブラリからのゲートのリストを含むネットリストを生成するために記述を合成し得る合成ツールによって読み取られてもよい。ネットリストは、システムを含むハードウェアの機能を表すゲートのセットを含む。ネットリストは、次いで、マスクに適用される幾何学形状を記述するデータセットを生成するために配置され、ルーティングされ得る。マスクは、次いで、システムに対応する半導体回路または複数の回路を製造するために様々な半導体作製ステップで使用され得る。あるいは、コンピュータアクセス可能記憶媒体上の命令は、必要に応じて、ネットリスト（合成ライブラリの有無にかかわらず）またはデータセットであってよい。また、命令は、Ｃａｄｅｎｃｅ（登録商標）、ＥＶＥ（登録商標）およびＭｅｎｔｏｒ  Ｇｒａｐｈｉｃｓ（登録商標）などのベンダーからのハードウェアベースタイプのエミュレータによるエミュレーションのために利用され得る。
【００６９】
上記実施形態はかなり詳細に説明されているが、上述した開示が完全に理解されると、多数の変形および修正が当業者において明らかになるであろう。以下の請求項は、かかる変形および修正の全てを包含すると解釈されることを意図する。
【図１】
2016508640.tif 000003
【図２】
2016508640.tif 000004
【図３】
2016508640.tif 000005
【図４】
2016508640.tif 000006
【図５】
2016508640.tif 000007
【図６】
2016508640.tif 000008
【図７】
2016508640.tif 000009
【図８】
2016508640.tif 000010
【図９】
2016508640.tif 000011
【国際調査報告】
2016508640.tif 000012
2016508640.tif 000013
2016508640.tif 000014