汎用プロセッサによるリターゲティングされたグラフィックプロセッサ加速コードの実行
【課題】マルチコアグラフィックプロセッサ（マルチコアＧＰＵ）により実行するために書かれ、共有メモリをもつ汎用プロセッサにより実行するためのシステム。
【解決手段】本発明は、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、汎用のＣＰＵにより実行するように変換する技術について述べる。マルチコアＧＰＵの特定の特徴に依存するアプリケーションプログラムの部分は、トランスレータにより、汎用ＣＰＵで実行するように変換される。アプリケーションプログラムは、同期独立インストラクションの領域へと区画化される。インストラクションは、収斂又は発散として分類され、領域と領域との間で共有される発散メモリ参照が複写される。汎用ＣＰＵによる実行中に種々のスレッド間でのメモリの正しい共有を保証するためにスレッドループが挿入される。
【解決手段】本発明は、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、汎用のＣＰＵにより実行するように変換する技術について述べる。マルチコアＧＰＵの特定の特徴に依存するアプリケーションプログラムの部分は、トランスレータにより、汎用ＣＰＵで実行するように変換される。アプリケーションプログラムは、同期独立インストラクションの領域へと区画化される。インストラクションは、収斂又は発散として分類され、領域と領域との間で共有される発散メモリ参照が複写される。汎用ＣＰＵによる実行中に種々のスレッド間でのメモリの正しい共有を保証するためにスレッドループが挿入される。
【発明の詳細な説明】
【関連出願の相互参照】
【０００１】
[0001]本出願は、２００８年４月９日に出願された“SystemFor Executing GPU-Accelerated Code on Multi-Core Architecture”と題する米国プロビジョナル特許出願第６１／０４３，７０８号（代理人管理番号ＮＶＤＡ／ＳＣ−０８−０００７−ＵＳ０）の利益を主張する。この関連出願の対象資料を参考としてここに援用する。
【技術分野】
【０００２】
[0002]本発明の実施形態は、一般に、コンパイラープログラムに係り、より詳細には、マルチコアグラフィックプロセッサにより実行するために書かれ、共有メモリをもつ汎用プロセッサにより実行するためにリターゲティングされたアプリケーションプログラムに係る。
【背景技術】
【０００３】
[0003]近代的なグラフィック処理システムは、典型的に、マルチスレッド的にアプリケーションを実行するように構成されたマルチコアグラフィック処理ユニット（ＧＰＵ）を備えている。又、グラフィック処理システムは、実行スレッド間に共有され且つ各スレッド専用とされた部分をもつメモリも備えている。
【０００４】
[0004]ＮＶＩＤＩＡのＣＵＤＡＴＭ（コンピュート・ユニファイド・デバイス・アーキテクチャー）技術は、プログラマーや開発者が、ビデオ及びオーディオエンコーディング、油田及びガス田踏査のためのモデリング、及び医療像形成のような複雑な計算上の問題を解決するためのソフトウェアアプリケーションを書くことができるようにするＣ言語環境を提供する。これらのアプリケーションは、マルチコアＧＰＵにより並列に実行するように構成され、典型的に、マルチコアＧＰＵの特定の特徴に依存している。汎用の中央処理ユニット（ＣＰＵ）には同じ特定の特徴が得られないので、ＣＵＤＡを使用して書かれたソフトウェアアプリケーションは、汎用のＣＰＵで実行するように移行できないことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]上述したように、この技術では、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、プログラマーにアプリケーションプログラムの変更を要求することなく、汎用ＣＰＵで実行できるようにする技術が要望されている。
【課題を解決するための手段】
【０００６】
[0006]本発明の一実施形態は、変換されたアプリケーションプログラムを実行するように汎用プロセッサを構成するための方法について述べる。この方法は、マルチコアグラフィック処理システムで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムから変換されたものである前記変換されたアプリケーションプログラムを受け取り、そしてその変換されたアプリケーションプログラムをコンパイルして、汎用プロセッサにより実行するためのコンパイルされたコードを発生することを含む。コンパイルされたコードを実行するために利用できる汎用プロセッサ内の実行コアの数が決定され、その数の実行コアをイネーブルするように汎用プロセッサが構成される。コンパイルされたコードは、その数の実行コアを含む汎用プロセッサによって実行するために起動される。
【０００７】
[0007]ここに開示する方法の１つの効果は、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、変更せずに汎用ＣＰＵへ移行できることである。マルチコアＧＰＵの特定の特徴に依存するアプリケーションの部分は、トランスレータにより、汎用ＣＰＵで実行するように変換される。アプリケーションプログラムは、同期独立インストラクションの領域へ区画化される。これらインストラクションは、収斂又は発散として分類され、領域間で共有される発散メモリ参照が複写される。汎用ＣＰＵにより実行される間に種々のスレッド間にメモリの正しい共有を保証するためにスレッドループが挿入される。
【０００８】
[0008]上述した本発明の特徴を詳細に理解できるように、前記で簡単に要約した本発明について、幾つかを添付図面に例示した実施形態を参照して、より詳細に説明する。しかしながら、添付図面は、本発明の典型的な実施形態を例示するに過ぎず、それ故、本発明の範囲をそれに限定するものではなく、本発明は、同等の効果を発揮できる他の実施形態も包含できるものであることに注意されたい。
【図面の簡単な説明】
【０００９】
【図１】コンピュータシステムを示すブロック図である。
【図２】本発明の一実施形態によるコンピュータシステムを例示するブロック図である。
【図３Ａ】マルチコアグラフィック処理ユニットにより実行するために書かれたコードを、本発明の一実施形態により、汎用プロセッサにより実行するためのコードに変換するための方法ステップを示すフローチャートである。
【図３Ｂ】本発明の一実施形態により、入力コードを区画化されたコードに変換するところを示す概念図である。
【図３Ｃ】本発明の一実施形態により、入力コードを最適化されたコードに変換するところを示す概念図である。
【図４】本発明の一実施形態により、変換されたコードを汎用プロセッサによって実行するための方法ステップを示すフローチャートである。
【発明を実施するための形態】
【００１０】
[0015]以下の説明では、本発明をより完全に理解するために多数の特定の細部について説明する。しかしながら、当業者であれば、これらの特定の細部の１つ以上がなくても、本発明を実施できることが明らかであろう。他の点について、本発明を不明瞭にしないために、良く知られた特徴は、説明しない。
【００１１】
[0016]図１は、ＣＵＤＡを使用して書かれたコードを実行するように構成されたコンピュータシステム１００を示すブロック図である。このコンピュータシステム１００は、メモリブリッジ１０５を含むバス経路を経て通信するＣＰＵ１０２及びシステムメモリ１０４を備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ１０５は、バス又は他の通信経路１０６（例えば、ハイパートランスポートリンク）を経てＩ／Ｏ（入力／出力）ブリッジ１０７に接続される。例えば、サウスブリッジ(Southbridge)チップでよいＩ／Ｏブリッジ１０７は、１つ以上のユーザ入力装置１０８（例えば、キーボード、マウス）からユーザ入力を受け取り、そしてその入力を、経路１０６及びメモリブリッジ１０５を経てＣＰＵ１０２へ転送する。メモリブリッジ１０５には、バス又は他の通信経路１１３（例えば、ＰＣＩエクスプレス、アクセラレーテッドグラフィックポート又はハイパートランスポートリンク）を経てマルチスレッド型処理サブシステム１１２が結合される。一実施形態では、このマルチスレッド型処理サブシステム１１２は、ディスプレイ装置１１０（例えば、従来のＣＲＴ又はＬＣＤベースのモニタ）へピクセルを配送するグラフィックサブシステムである。Ｉ／Ｏブリッジ１０７には、システムディスク１１４も接続される。スイッチ１１６は、Ｉ／Ｏブリッジ１０７と、他のコンポーネント、例えば、ネットワークアダプタ１１８及び種々のアドイン(add-in)カード１２０、１２１との間の接続をなす。又、Ｉ／Ｏブリッジ１０７には、ＵＳＢ又は他のポート接続部、ＣＤドライブ、ＤＶＤドライブ、フィルムレコーディング装置、等を含む他のコンポーネント（明確に示さず）を接続することもできる。図１における種々のコンポーネントを相互接続する通信経路は、適当なプロトコル、例えば、ＰＣＩ（周辺コンポーネント相互接続）、ＰＣＩ−エクスプレス（ＰＣＩ−Ｅ）、ＡＧＰ（アクセラレーテッドグラフィックポート）、ハイパートランスポート、或いは他のバス又はポイント・ツー・ポイント通信プロトコルを使用して実施することができ、そして異なる装置間の接続は、この技術で知られたように異なるプロトコルを使用することができる。
【００１２】
[0017]ＣＰＵ１０２は、コンピュータシステム１００の制御プロセッサとして動作し、他のシステムコンポーネントの動作を管理し且つ整合させる。特に、ＣＰＵ１０２は、マルチスレッド型処理サブシステム１１２内の並列プロセッサ１３４の動作を制御するコマンドを発生する。ある実施形態では、ＣＰＵ１０２は、並列プロセッサ１３４のためのコマンドのストリームをコマンドバッファ（図示せず）に書き込み、コマンドバッファは、システムメモリ１０４、サブシステムメモリ１３８、或いはＣＰＵ１０２及び並列プロセッサ１３４の両方にアクセス可能な別の記憶位置に常駐することができる。並列プロセッサ１３４は、コマンドバッファからコマンドストリームを読み取り、そしてＣＰＵ１０２のオペレーションに対して非同期でコマンドを実行する。
【００１３】
[0018]システムメモリ１０４は、オペレーティングシステムの実行映像、装置ドライバ１０３、及びマルチスレッド型処理サブシステム１１２により実行するように構成されたＣＵＤＡコード１０１を備えている。ＣＵＤＡコード１０１は、マルチスレッド型処理サブシステム１１２で実行されるように意図されたプログラミングインストラクションを組み込んでいる。この説明の文脈において、コードとは、コンピュータコード、インストラクション、及び／又はプロセッサを使用して実行できるファンクションを指す。例えば、種々の実施形態において、コードは、Ｃコード、Ｃ＋＋コード、等を含んでもよい。一実施形態において、コードは、コンピュータ言語の言語拡張（例えば、Ｃ、Ｃ＋＋、等の拡張）を含んでもよい。
【００１４】
[0019]オペレーティングシステムは、コンピュータシステム１００のオペレーションを管理し整合するための詳細なインストラクションを与える。装置ドライバ１０３は、マルチスレッド型処理サブシステム１１２、特に、並列プロセッサ１３４のオペレーションを管理し整合するための詳細なインストラクションを与える。更に、装置ドライバ１０３は、並列プロセッサ１３４に対して特別に最適化されたマシンコードを発生するための編集設備を備えてもよい。又、装置ドライバ１０３は、ＮＶＩＤＩＡ社により提供されるＣＵＤＡＴＭフレームワークに関連して設けられてもよい。
【００１５】
[0020]一実施形態では、マルチスレッド型処理サブシステム１１２は、１つ以上の並列プロセッサ１３４を組み込んでおり、これら並列プロセッサは、例えば、プログラム可能なプロセッサ、特定用途向け集積回路（ＡＳＩＣ）のような１つ以上の集積回路装置を使用して実施することができる。並列プロセッサ１３４は、グラフィック及びビデオ処理に最適な回路を含み、例えば、ビデオ出力回路、及びグラフィック処理回路（ＧＰＵ）を含む。別の実施形態では、マルチスレッド型処理サブシステム１１２は、メモリブリッジ１０５、ＣＰＵ１０２、及びＩ／Ｏブリッジ１０７のような１つ以上の他のシステム要素と一体化されて、システムオンチップ（ＳｏＣ）を形成することができる。１つ以上の並列プロセッサ１３４がディスプレイ装置１１０へデータを出力してもよいし、又は各並列プロセッサ１３４が１つ以上のディスプレイ装置１１０にデータを出力してもよい。
【００１６】
[0021]並列プロセッサ１３４は、１つ以上の処理コアを含む高度に並列なプロセッサを実施するのが好都合であり、各処理コアは、非常に多数のスレッドを同時に実行することができ、又、各スレッドは、コード１０１のようなプログラムのインスタンスである。並列プロセッサ１３４は、これに限定されないが、直線的及び非直線的なデータ変換、ビデオ及び／又はオーディオデータのフィルタリング、モデリングオペレーション（例えば、物理の法則を適用して、物体の位置、速度及び他の属性を決定する）、映像レンダリングオペレーション（例えば、モザイクシェーダー、頂点シェーダー、幾何学的シェーダー、及び／又はピクセルシェーダープログラム）、等を含む種々様々なアプリケーションに関連した処理タスクを実行するようにプログラムすることができる。並列プロセッサ１３４は、システムメモリ１０４及び／又はローカルサブシステムメモリ１３８からローカル（オンチップ）メモリへデータを転送し、データを処理し、そして結果のデータをシステムメモリ１０４及び／又はサブシステムメモリ１３８へ書き込み、そこで、このデータは、ＣＰＵ１０２又は別のマルチスレッド型処理サブシステム１１２を含む他のシステムコンポーネントによってアクセスすることができる。
【００１７】
[0022]並列プロセッサ１３４は、任意の量のサブシステムメモリ１３８が設けられてもよく、又、サブシステムメモリ１３８を含まなくてもよく、更に、サブシステムメモリ１３８及びシステムメモリ１０４を任意の組み合わせで使用してもよい。例えば、並列プロセッサ１３４は、一体化メモリアーキテクチャー（ＵＭＡ）実施形態では、グラフィックプロセッサでよい。このような実施形態では、専用のサブシステムメモリ１３８は、ほとんど又は全く設けられず、そして並列プロセッサ１３４は、システムメモリ１０４を排他的に又はほぼ排他的に使用する。ＵＭＡ実施形態では、並列プロセッサ１３４は、ブリッジチップ又はプロセッサチップに一体化されてもよいし、或いはブリッジチップ又は他の通信手段を経て並列プロセッサ１３４をシステムメモリ１０４に接続する高速リンク（例えば、ＰＣＩ−Ｅ）と共に個別のチップとして設けられてもよい。
【００１８】
[0023]上述したように、マルチスレッド型処理サブシステム１１２には、多数の並列プロセッサ１３４を含ませることができる。例えば、複数の並列プロセッサ１３４を単一のアドインカードに設けることもできるし、複数のアドインカードを通信経路１１３に接続することもできるし、又は１つ以上の並列プロセッサ１３４をブリッジチップに一体化することもできる。複数の並列プロセッサ１３４が存在する場合には、それらの並列プロセッサ１３４は、単一の並列プロセッサ１３４で可能である以上に高いスループットでデータを処理するように並列に動作することができる。１つ以上の並列プロセッサ１３４を組み込んだシステムは、デスクトップ、ラップトップ、ハンドヘルドパーソナルコンピュータ、サーバー、ワークステーション、ゲームコンソール、埋め込み型システム、等を含む種々のコンフィギュレーション及びフォームファクタで実施することができる。
【００１９】
[0024]並列プロセッサ１３４の幾つかの実施形態では、単一インストラクション・複数データ（ＳＩＭＤ）インストラクション発行技術を使用して、複数の独立したインストラクションユニットを設けずに非常に多数のスレッドの並列実行をサポートする。他の実施形態では、単一インストラクション・複数スレッド（ＳＩＭＴ）技術を使用して、非常に多数の一般的に同期されたスレッドの並列実行をサポートする。全ての処理エンジンが典型的に同じインストラクションを実行するＳＩＭＤ実行形態とは異なり、ＳＩＭＴの実行は、異なるスレッドが、所与のスレッドプログラムを通して、発散する実行経路を容易にたどれるようにする。当業者であれば、ＳＩＭＤ処理形態は、ＳＩＭＴ処理形態の機能的サブセットを表すことが理解されよう。並列プロセッサ１３４内のファンクションユニットは、整数及び浮動小数点演算（例えば、加算及び乗算）、比較演算、ブール演算（ＡＮＤ、ＯＲ、ＸＯＲ）、ビットシフト、及び種々の代数関数の計算（例えば、二次元補間、三角法、指数関数、対数関数、等）を含む種々のオペレーションをサポートする。
【００２０】
[0025]並列プロセッサ１３４の処理コア（図示せず）内の特定の処理ユニット（図示せず）へ送信される一連のインストラクションは、既に定義されたスレッドを構成し、そして１つの処理コア内で処理ユニットにわたって同時に実行されるある数のスレッドの集合を、ここでは、「スレッドグループ」と称する。ここで使用される「スレッドグループ」は、異なる入力データに対して同じプログラムを実行するスレッドのグループを指し、グループの各スレッドは、処理コア内の異なる処理ユニットに指定される。１つのスレッドグループは、処理ユニットの数より少ないスレッドを含んでもよく、この場合、ある処理ユニットは、そのスレッドグループが処理されているときのサイクル中にアイドル状態となる。又、１つのスレッドグループは、処理ユニットの数より多くのスレッドを含んでもよく、この場合、処理は、複数のクロックサイクルにわたって行われる。
【００２１】
[0026]各処理コアは、Ｇ個までのスレッドグループを同時にサポートできるので、並列プロセッサ１３４内の処理コアの数をＭとすれば、所与の時間に処理コアにおいてＧｘＭ個までのスレッドグループを実行できることになる。更に、処理コア内で同時に複数の関連スレッドグループがアクティブになり得る（異なる実行段階において）。スレッドグループのこの集合を、ここでは、「協働スレッドアレイ」（ＣＴＡ）と称する。ＣＴＡのサイズは、一般的に、プログラマーにより、ＣＴＡに利用できるメモリ又はレジスタのようなハードウェアリソースの量で決定される。ＣＵＤＡプログラミングモデルは、ＧＰＵアクセラレータのシステムアーキテクチャーを表す。排他的ローカルアドレススペースが各スレッドに利用でき、そしてＣＴＡごとの共有アドレススペースを使用して、ＣＴＡ内のスレッド間にデータを通す。又、処理コアは、オフチップの「グローバル」メモリにアクセスすることもでき、これは、例えば、サブシステムメモリ１３８及び／又はシステムメモリ１０４を含むことができる。
【００２２】
[0027]ＣＵＤＡアプリケーションプログラムのホスト部分は、カーネルファンクションがＣＴＡ処理を指定する間に、従来の方法及びツールを使用してコンパイルされる。最も高いレベルにおいて、ＣＵＤＡメモリモデルは、ホスト及び装置のメモリスペースを分離し、ホストコード及びカーネルコードがそれらの各メモリスペースに直接アクセスすることしかできないようにする。ＡＰＩ（アプリケーションプログラミングインターフェイス）ファンクションは、ホスト及び装置のメモリスペース間でデータをコピーするのを許す。ＣＵＤＡプログラミングモデルの共有メモリＣＰＵ実行では、制御ＣＰＵスレッドが、潜在的なデータ競合を伴わずに、並列ＣＴＡと並列に実行することができる。ホストメモリスペースは、Ｃプログラミング言語によって定義され、そして装置メモリスペースは、グローバル、定数、ローカル、共有及びテクスチャとして指定される。全てのスレッドは、グローバル、定数及びテクスチャメモリスペースにアクセスすることができる。上述したように、ローカルスペースへのアクセスは、単一スレッドに制限され、そして共有スペースへのアクセスは、ＣＴＡ内のスレッドに制限される。このメモリモデルは、待ち時間の短いアクセスに対して小さなメモリスペースの使用を奨励し、そして典型的に待ち時間の長い大きなメモリスペースの賢明な使用を奨励する。
【００２３】
[0028]コード１０１のようなＣＵＤＡプログラムは、典型的に、１つ、２つ又は３つの次元、例えば、ｘ、ｙ及びｚにおいて、ＣＴＡの同期又は非同期実行のセットとして編成される。３タプルインデックスは、スレッドブロック内のスレッドを独特に識別する。スレッドブロックそれ自体は、暗示的に定義された２タプル変数により区別される。これらインデックスの範囲は、ランタイムに定義され、そしてランタイム環境は、インデックスが何らかのハードウェア制限に適合することをチェックする。各ＣＴＡは、並列プロセッサ１３４により他のＣＴＡと並列に実行される。各並列プロセッサ１３４が１つ以上のＣＴＡを実行するようにして、多数のＣＴＡが並列に実行される。ランタイム環境は、ＣＵＤＡコード１０１の実行を必要に応じて同期又は非同期で管理する役割を果たす。ＣＴＡ内のスレッドは、共有メモリと、ｓｙｎｃｈｔｈｒｅａｄｓ（）と称されるバリア同期プリミティブとの使用により、互いに通信し且つ同期する。ＣＵＤＡは、スレッドブロック内のスレッドが同時に生きていることを保証すると共に、スレッドブロック内のスレッドが迅速なバリア同期及びローカルデータ共有を遂行するためのコンストラクトを与える。（１つ以上の次元によって定義される）ＣＴＡ内の個別のスレッドブロックは、それらの生成、実行又は退出について何ら順序付けを課さない。更に、並列なＣＴＡは、Ｉ／Ｏを含むシステムコールへのアクセスが許されない。ＣＵＤＡプログラミングモデルは、並列なＣＴＡ間にグローバルな同期を強要するだけであり、ＣＴＡ内のブロック間での限定された通信に対して固有のアトミックなオペレーションを与える。
【００２４】
[0029]カーネルと称される各スレッドの本体は、メモリモデルアノテーション及びバリア同期プリミティブを用いて標準Ｃで表わされるＣＵＤＡを使用して指定される。ＣＵＤＡプログラムのセマンティックは、バリア同期プリミティブによって暗示されるメモリの順序付けを尊重する順序でＣＴＡ内の全てのスレッドにより各カーネルが実行されるというものである。特に、バリア同期プリミティブの前に生じるＣＴＡ内の全ての共有メモリ参照は、バリア同期プリミティブの後に生じる共有メモリ参照の前に完了しなければならない。
【００２５】
[0030]カーネルコードにおけるバリア同期プリミティブの各インスタンスは、概念的に個別の論理的バリアを表わし、スタティックとして取り扱われねばならない。ＣＵＤＡスレッドが“if-else”コンストラクトの異なる分岐を取り得るときには、そのコンストラクトの両経路においてバリア同期プリミティブを呼び出すのは不法である。スレッドブロック内の全てのスレッドは、同期プリミティブの１つに到達するが、スレッドが全部到達するか全く到達しないかのいずれかを各々要求する別々のバリアを表わす。それ故、このようなカーネルは、正しく実行されない。より一般的には、ＣＵＤＡコードは、スレッドブロック内の異なるスレッドに対して異なる振舞いをする制御フローコンストラクト内に同期プリミティブが収容される場合には、正しく実行されると保証されない。
【００２６】
[0031]図２は、本発明の一実施形態によるコンピュータシステム２００を示すブロック図である。コンピュータシステム１００は、ＣＰＵ２０２と、メモリブリッジ２０５を含むバス経路を経て通信するシステムメモリ２０４とを備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ２０５は、バス又は他の通信経路１０６（例えば、ハイパートランスポートリンク）を経てＩ／Ｏ（入力／出力）ブリッジ１０７に接続される。ＣＰＵ２０２は、ディスプレイ装置２１０（例えば、従来のＣＲＴ又はＬＣＤベースのモニタ）に表示するための出力を発生する。
【００２７】
[0032]マルチスレッド型処理サブシステム１１２は、コンピュータシステム２００には含まれず、ＣＵＤＡコード１０１は、ＣＰＵ２０２のような汎用プロセッサによって実行するように適応されない。ＣＵＤＡコード１０１は、マルチスレッド型処理サブシステム１１２によって実行するように適応され、トランスレータ２２０を使用して変換されて、バリア同期プリミティブを含まない変換されたコード２０１を発生する。ＣＰＵ２０２がコード１０１により表わされたプログラムを実行するために、コード１０１を先ずコード２０１に変換しなければならない。変換されたコードは、次いで、ＣＰＵ２０２によって実行するために、コンパイラー２２５によりコンパイルされる。コンパイラー２２５は、ＣＰＵ２０２に対して特有の最適化を遂行することができる。コードを変換することは、第１のコンピュータ言語で書かれたコードを、第２のコンピュータ言語に変換することを指す。コードをコンパイルすることは、コンピュータ言語（例えば、ソースコード）で書かれたコードを、別のコンピュータ言語（例えば、オブジェクトコード）に変換することを指す。トランスレータ２２０は、図３Ａを参照して説明し、コンパイラー２２５は、図４を参照して説明する。コンパイラー２２５は、コード１０１と、コード２０１と、ＣＰＵ２０２との間をインターフェイスするように構成された装置ドライバ２０３内に含まれる。ランタイム環境２２７は、コンパイルされたコードに対するファンクション、例えば、入力及び出力、メモリ管理、等を実施するように構成される。又、ランタイム環境２２７は、ＣＰＵ２０２により実行するためのコンパイルされたコードを起動する。トランスレータ２２０は、ＣＵＤＡスレッドグループの微粒度スレッドにわたるオペレーションを単一のＣＰＵスレッドへと直列化するための最適化変換を遂行し、一方、ランタイム環境２２７は、スレッドグループを、ＣＰＵ２０２により並列処理するためのワークユニットとしてスケジュールする。
【００２８】
[0033]汎用ＣＰＵにより実行するためにＧＰＵで実行されるように設計されたＣＵＤＡアプリケーションの一次障害防止移行性は、並列性の粒度である。従来のＣＰＵは、単一のＣＵＤＡ ＣＴＡに要求される数百のハードウェアスレッドコンテクストをサポートしない。それ故、汎用ＣＰＵにおいてＣＵＤＡプログラミングモデルを実施するシステムの一次目標は、タスクレベルの並列性を、利用可能なＣＰＵコアに分配することである。それと同時に、システムは、過剰なスケジューリングオーバーヘッド及び頻繁なコア間同期を防止するためにタスク内のマイクロスレッドを単一のＣＰＵスレッドへと合併しなければならない。
【００２９】
[0034]図３Ａは、本発明の一実施形態に基づき、例えば、マルチスレッド型処理サブシステム１１２のようなマルチコアグラフィック処理システムにより実行するために書かれたコード１０１を、例えば、ＣＰＵ２０２のような汎用プロセッサによって実行するためのコード２０１へ変換する方法ステップのフローチャートである。トランスレータ２２０は、図３Ａに示されたステップの１つ以上を遂行して、コード１０１に使用されるバリア同期プリミティブのセマンティックを保存する。トランスレータ２２０は、バリア同期プリミティブの周りでコード１０１を区画化することによって並列スレッドを「アンロール(unroll)」し、共有状態の使用を減少し、メモリアクセスに対する参照の位置関係を改善し、そして汎用プロセッサにより実行するためのＣＵＤＡ特有のコードを変換するためのスレッドループを挿入する。マルチスレッド型処理サブシステム１１２により実行するためにターゲットとされるＣＵＤＡコード１０１を変更せずにＣＰＵ２０２を使用してコード２０１を実行する良好な実行性能を得ることができる。コンパイラー２２５は、ＣＰＵ２０２により与えられるベクトルインストラクション能力を利用し、そして実行のためにコード２０１をコンパイルするときに最適化を遂行することができる。
【００３０】
[0035]ステップ３００において、トランスレータ２２０は、マルチスレッド型処理サブシステム１１２、又は１つ以上の並列プロセッサ１３４を含むプロセッサのようなマルチコアＧＰＵにより実行するために書かれたコード１０１、例えば、ＣＵＤＡコード１０１を受け取る。ステップ３００で受け取られたコードは、エッジによって接続された基本的ブロックノードより成る制御フローグラフとして表わすことができる。各々の基本的ブロックは、例えば、ＣＰＵ２０２のようなターゲット環境により遂行されるオペレーションを指定する。ステップ３０５において、トランスレータ２２０は、バリア同期プリミティブの周りでＣＵＤＡコード１０１を区画化して、区画化されたコードを発生する。区画化されたコードが図３Ｂ及び３Ｃに示されており、これらの図を参照して区画化プロセスを説明する。同期区画は、区画内の基本的ブロックの制御フロー及びデータフロー特性によりオペレーションの順序付けが完全に決定されるところのコードの領域である。区画は、並列スレッドを実行するために区画の周りにスレッドループを挿入できるという特性を有する。制御フローグラフを使用して、各同期スレッド(synchthread)プリミティブをエッジに置き換え、基本的ブロックノードを異なる区画に分離することにより、同期区画制御フローグラフを発生することができる。
【００３１】
[0036]ステップ３１０において、区画化されたコードを分類し、各ステートメントが収斂又は発散のいずれかとして識別されるようにする。区画化されたコードは、式及びステートメントを含むことができる。式は、定数、暗示的スレッドＩＤ、及びプログラマーにより形成される名前付き変数を伴うが、副作用や指定をもたない計算である。簡単なステートメントは、単一の指定を生じる計算式として定義される。又、一般的ステートメントは、バリア、制御フロー条件又はループコンストラクト、或いはステートメントの逐次ブロックを表すこともできる。ＣＴＡ次元ｘ、ｙ及びｚは、コードを通して伝播され、各オペレーションがＣＴＡ次元の１つ以上に依存するかどうか決定する。次元ｘ、ｙ及び／又はｚにおいてスレッドＩＤ(threadID)（スレッド識別子）を参照するオペレーションは、発散と考えられる。というのは、ＣＴＡ次元を参照するスレッドは、実行中に同じＣＴＡの他のスレッドから発散し得るからである。例えば、スレッドＩＤ．ｘ(threadID.x)に依存するオペレーションは、ｘ次元に対して発散である。スレッドＩＤ．ｘに依存しない別のオペレーションは、ｘ次元において収斂である。発散ステートメントは、それらが参照する各ＣＴＡ次元に対してスレッドループを要求する。
【００３２】
[0037]ステップ３１５において、区画化されたコードは、分類情報を使用して性能に対して最適化され、最適化されたコードを発生する。例えば、区画内のインストラクションは、オペレーションを融合させるように再順序付けされ、同じ分類をもつオペレーションが一緒にグループ編成されて、ステップ３２５で挿入される同じスレッドループ内に入ることができるようにする。分散ベクトルにおいてスレッドＩＤ次元がより少ないオペレーションが、より多くのスレッドＩＤ次元に依存するオペレーションに先行するように、オペレーションが順序付けされる。この再順序付けは、有効である。というのは、ステートメントは、それが依存するステートメントの分散ベクトルのスーパーセットである分散ベクトルを有していなければならないからである。従って、分散ベクトルに１つの次元しかもたないステートメントは、分散ベクトルに異なる次元又は２つ以上の次元をもつステートメントに依存することができない。
【００３３】
[0038]ステップ３２０において、最適化されたコードにおけるスレッド−ローカルメモリ参照は、オブジェクトの各インスタンスが、値を記憶すべき独特の位置をもつよう保証するために、必要に応じてアレイ参照へ昇格される。特に、ある区画から別の区画へ搬送されるデータは、各区画においてそれが得られるように複写される必要がある。次の条件の１つを満足する変数は、アレイ参照へ昇格される。即ち、クロス区画依存性（ある区画において指定され、そして別の区画において参照される）を有するローカル変数。
【００３４】
[0039]ステップ３２０において、トランスレータ２２０は、スレッド−ローカルメモリ参照をアレイ参照へ昇格させる。テーブル１に示すプログラムは、同期バリアプリミティブ及び発散参照を含む。
【表１】
【００３５】
[0040]テーブル１に示すプログラムは、同期スレッドプリミティブの前に第１区画へそして同期スレッドプリミティブの後に第２区画へと区画化される。第２区画は、第１区画で計算された参照（左インデックス(leftIndex)及び右インデックス(rightIndex)）を含み、ＣＴＡ次元から従属する。発散参照が昇格されない場合には、第２区画は、第１区画の最後の繰り返しにより計算された値を誤って使用する。第２区画は、第１区画のｔｈｒｅａｄＩｄ．ｘの各対応する繰り返しに対して計算された値を使用しなければならない。計算が正しいことを保証するために、発散参照は、テーブル２に示すように昇格される。
【表２】
【００３６】
[0041]ステップ３２５において、スレッドＩＤ次元を分散ベクトルに含むステートメントに対してスレッドループが発生される。ループ交換、ループ分裂及びループ不変量除去と同等の変換を同時に評価して、最良の冗長性除去を達成するために、適応ループネストが使用される。ネスト状のループは、アプリケーションに最も適するようにスレッドＩＤタプルの各次元の値に対して動的に発生されるのであって、特定のループネストを仮定して、そのネストに基づいてアプリケーションを評価するのではない。ステップ３１５においてステートメントが順序付けされた後に、分散ベクトルに次元を含むステートメントの周りのみでスレッドＩＤ次元に対してループを発生することができる。ループのオーバーヘッドを除去するために、トランスレータ２２０は、あるものが他のもののサブセットである分散ベクトルを有するような隣接ステートメントグループを融合することができる。
【００３７】
[0042]図３Ｂは、本発明の一実施形態により、入力コード１０１を区画されたコード３５０へ変換するところを示す概念図である。入力コード３３０は、マルチスレッド型処理サブシステム１１２により実行するように構成され、同期バリアインストラクション３３６で分離されたコードシーケンス３３１及び３３２を含む。ＣＴＡにおける全てのスレッドは、いずれか１つのスレッドがコードシーケンス３３２の実行を開始する前にコードシーケンス３３１の実行を完了する。トランスレータ２２０は、入力コード３３０を区画化して、区画化されたコード３５０を発生し、区画３５１は、コードシーケンス３３１により表わされたインストラクションを含み、そして区画３５２は、コードシーケンス３３２により表わされたインストラクションを含む。区画化されたコード３５０が、同期バリアインストラクションを本来サポートしない汎用プロセッサにより実行されるときに、同期セマンティックが維持されるように保証するために、スレッドループ３５３が区画３５２の周りに挿入される。この実施例では、コード区画３５１が収斂参照を含み、区画３５２が発散参照を含む。それ故、スレッドループ３５３が区画３５２の周りに挿入される。
【００３８】
[0043]図３Ａのステップ３２５において、トランスレータ２２０は、（スレッドループ３５３のような）スレッドループを、最適化されたコードに挿入し、ＣＰＵ２０２により実行するために変換されたコード２０１を発生する。各区画は、各ＣＴＡ次元に対して挿入されたスレッドループを有することができる。同期区画化及びスレッドループ挿入の一実施例がテーブル３及び４に示されている。テーブル３に示されたプログラムは、テーブル４に示されたプログラムへと変換される。
【表３】
【００３９】
[0044]テーブル３のプログラムは、ＣＴＡにおける種々のスレッド間でのメモリの正しい共有を保証するために明確な同期を使用する。トランスレータ２２０は、プログラムを、ｘＣＴＡ次元に各々依存する２つの区画に区画化する。それ故、スレッドループは、変換されたプログラムがオペレーションを正しい順序で遂行するよう保証するために２つの区画の各々の周りに挿入される。
【表４】
【００４０】
[0045]汎用プロセッサにより実行するためのプログラムを挿入するより簡単な技術は、各ＣＴＡ次元に対して明確なスレッドループを挿入し、同じ区画内の参照に対する次元依存性を決定する必要がないようにすることである。例えば、テーブル５に示すプログラムは、テーブル６に示すプログラムへ変換される。次元の依存性を決定することなくプログラムが形成されるので、テーブル５において挿入されるスレッドループの１つ以上が不必要であることに注意されたい。
【表５】
【表６】
【００４１】
[0046]図３Ｃは、本発明の一実施形態により、入力コード３３３を、最適化されたコード３６０へ変換するところを示す概念図である。入力コード３３３は、マルチスレッド型処理サブシステム１１２により実行するように構成され、同期バリアインストラクション３３５で分離されたコードシーケンス３３４及び３３８を含む。ＣＴＡにおける全てのスレッドは、いずれか１つのスレッドがコードシーケンス３３８の実行を開始する前にコードシーケンス３３４の実行を完了する。トランスレータ２２０は、入力コード３３３を区画化して、区画化されたコード３６０を発生し、区画３６１は、コードシーケンス３３４により表わされたインストラクションを含み、そして区画３６２、３６４及び３６５は、コードシーケンス３３８により表わされたインストラクションを含む。
【００４２】
[0047]区画３６２は、第１のＣＴＡ次元において発散であるインストラクションの第１部分を含む。区画３６４は、収斂であるインストラクションの第２部分を含む。区画３６５は、第２のＣＴＡ次元において発散であるインストラクションの第３部分を含む。同期バリアインストラクションを本来サポートしない汎用プロセッサによって区画化されたコード３６０が実行されるときに同期セマンティックが維持されるように保証するために、区画３６２の周りにスレッドループ３６３が挿入される。第１のＣＴＡ次元に対してスレッドループ３６３が繰り返される。スレッドループ３６６が、第２のＣＴＡ次元に対して繰り返されるように区画３６５の周りに挿入される。
【００４３】
[0048]テーブル７は、例示的ＣＵＤＡカーネルを示し、テーブル８は、汎用プロセッサにより実行するためのＣＵＤＡカーネルの変換を示す。例示的カーネルは、小さなマトリクスのリストを乗算する。各スレッドブロックは、リストから１つの小さなマトリクス乗算を計算し、一方、各スレッドは、そのブロックに対して結果のマトリクスの１つのエレメントを計算する。
【表７】
【００４４】
[0049]テーブル７の行（９）のステートメントは、列がｘ次元に依存し、行がｙ次元に依存するので、（ｘ、ｙ）の分散ベクトルを有することに注意されたい。ｚ次元は決して使用されず、従って、ｚに対して繰り返されるループが挿入されることはない。テーブル７に示す例示的カーネルにおいてステートメント５及び６のようなケースを決定するために、典型的なコスト分析技術を使用することができる。各々が１つのスレッドＩＤ次元にしか依存しないので、ｘ及びｙインデックスループのいずれかのネスト順序を選択することで、ステートメントの冗長な実行、又は区画のメインループネストの外部の冗長なループのいずれかが強制される。
【表８】
【００４５】
[0050]図４は、本発明の一実施形態に基づき、ＣＰＵ２０２のような汎用プロセッサにより、変換されたコード２０１を実行するための方法ステップのフローチャートである。ステップ４００において、コンパイラー２２５は、ＣＰＵ特有の最適化を任意に遂行する変換されたコード２０１をコンパイルして、コンパイルされたコードを発生する。ステップ４０５において、ＣＰＵ２０２に得られる実行コア４００の数は、装置ドライバ２０３により決定される。変換されたコード２０１は、性能改善のために利用可能な実行コアにおいて実行するように自動的にスケーリングされる。ステップ４１０において、ランタイム環境２２７又は装置ドライバ２０３は、変換されたコード２０１を実行する実行コアの数をイネーブルするようにＣＰＵ２０２を構成する。
【００４６】
[0051]ランタイム環境２２７は、環境変数により制御できる多数のオペレーティングシステム（ＯＳ）ランタイムスレッドを生成することができる。デフォールトとして、システム内のコアの数を、ＯＳランタイムスレッドの数として使用してもよい。ステップ４１０において、起動されるべきＣＵＤＡスレッドの数を評価して、ランタイムスレッドの数に統計学的に区画化することができる。各ランタイムスレッドは、コンパイルされたコードの一部分を逐次に実行し、バリアにおいて待機する。全てのランタイムスレッドがバリアに到達したときに、ＣＴＡが完了となる。ステップ４１５では、ランタイム環境２２７又は装置ドライバ２０３が、ＣＰＵ２０２により実行するためにコンパイルされたコードを起動する。
【００４７】
[0052]トランスレータ２２０、コンパイラー２２５及びランタイム環境２２７は、ＣＵＤＡアプリケーションプログラムを、汎用ＣＰＵにより実行するためのコードへ変換するのに使用される。ＣＵＤＡプログラミングモデルは、バルク同期タスクの並列性をサポートし、各タスクは、微粒度のＳＰＭＤスレッドより成る。ＣＵＤＡプログラミングモデルの使用は、ＧＰＵにより実行するための特殊なコードを書き込もうとするプログラマーに制限される。この特殊なコードは、プログラマーがＣＵＤＡアプリケーションプログラムをリライトすることを要求せずに、汎用ＣＰＵにより実行するように変換することができる。ＣＵＤＡによりサポートされる３つの重要なアブストラクションは、ＳＰＭＤスレッドブロック、バリア同期、及び共有メモリである。トランスレータ２２０は、ＣＵＤＡスレッドブロックの微粒度スレッドにわたるオペレーションを、単一のＣＰＵスレッドへと直列化し、そしてＣＵＤＡアプリケーションプログラムを変換するための最適化変換を遂行する。
【００４８】
[0053]以上、本発明の実施形態を説明したが、本発明の基本的な範囲から逸脱せずに、本発明の他の実施形態及び更に別の実施形態を案出することもできる。例えば、本発明の態様は、ハードウェア、又はソフトウェア、或いはハードウェアとソフトウェアの組合せで実施することもできる。本発明の一実施形態は、コンピュータシステムに使用するためのプログラム製品として実施することができる。プログラム製品のプログラム（１つ又は複数）は、（ここに述べる方法を含む）実施形態の機能を定義し、そして種々のコンピュータ読み取り可能な記憶媒体に含ませることができる。ここに例示するコンピュータ読み取り可能な記憶媒体は、（ｉ）情報が永久的に記憶される書き込み不能の記憶媒体（例えば、コンピュータ内のリードオンリメモリ装置、例えば、ＣＤ−ＲＯＭドライブにより読み取り可能なＣＤ−ＲＯＭディスク、フラッシュメモリ、ＲＯＭチップ、又は任意の形式のソリッドステート不揮発性半導体メモリ）、及び（ii）変更可能な情報が記憶される書き込み可能な記憶媒体（例えば、ディスケットドライブ又はハードディスクドライブ内のフロッピーディスク、又は任意の形式のソリッドステートランダムアクセス半導体メモリ）を含むが、これらに限定されない。このようなコンピュータ読み取り可能な記憶媒体は、本発明のファンクションを指令するコンピュータ読み取り可能なインストラクションを搬送するとき、本発明の実施形態となる。それ故、本発明の範囲は、特許請求の範囲によって決定される。
【符号の説明】
【００４９】
１００・・・コンピュータシステム、１０１・・・コード、１０２・・・ＣＰＵ、１０３・・・装置ドライバ、１０４・・・システムメモリ、１０５・・・メモリブリッジ、１０６・・・通信経路、１０７・・・Ｉ／Ｏブリッジ、１０８・・・入力装置、１１０・・・ディスプレイ装置、１１２・・・マルチスレッド型処理サブシステム、１１３・・・通信経路、１１４・・・システムディスク、１１６・・・スイッチ、１１８・・・ネットワークアダプタ、１２０・・・アドインカード、１２１・・・アドインカード、１３４・・・並列プロセッサ、１３８・・・サブシステムメモリ、２００・・・コンピュータシステム、２０１・・・コード、２０２・・・ＣＰＵ、２０３・・・装置ドライバ、２０４・・・システムメモリ、２０５・・・メモリブリッジ、２１０・・・ディスプレイ装置、２２０・・・トランスレータ、２２５・・・コンパイラー、２２７・・・ランタイム環境
【関連出願の相互参照】
【０００１】
[0001]本出願は、２００８年４月９日に出願された“SystemFor Executing GPU-Accelerated Code on Multi-Core Architecture”と題する米国プロビジョナル特許出願第６１／０４３，７０８号（代理人管理番号ＮＶＤＡ／ＳＣ−０８−０００７−ＵＳ０）の利益を主張する。この関連出願の対象資料を参考としてここに援用する。
【技術分野】
【０００２】
[0002]本発明の実施形態は、一般に、コンパイラープログラムに係り、より詳細には、マルチコアグラフィックプロセッサにより実行するために書かれ、共有メモリをもつ汎用プロセッサにより実行するためにリターゲティングされたアプリケーションプログラムに係る。
【背景技術】
【０００３】
[0003]近代的なグラフィック処理システムは、典型的に、マルチスレッド的にアプリケーションを実行するように構成されたマルチコアグラフィック処理ユニット（ＧＰＵ）を備えている。又、グラフィック処理システムは、実行スレッド間に共有され且つ各スレッド専用とされた部分をもつメモリも備えている。
【０００４】
[0004]ＮＶＩＤＩＡのＣＵＤＡＴＭ（コンピュート・ユニファイド・デバイス・アーキテクチャー）技術は、プログラマーや開発者が、ビデオ及びオーディオエンコーディング、油田及びガス田踏査のためのモデリング、及び医療像形成のような複雑な計算上の問題を解決するためのソフトウェアアプリケーションを書くことができるようにするＣ言語環境を提供する。これらのアプリケーションは、マルチコアＧＰＵにより並列に実行するように構成され、典型的に、マルチコアＧＰＵの特定の特徴に依存している。汎用の中央処理ユニット（ＣＰＵ）には同じ特定の特徴が得られないので、ＣＵＤＡを使用して書かれたソフトウェアアプリケーションは、汎用のＣＰＵで実行するように移行できないことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]上述したように、この技術では、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、プログラマーにアプリケーションプログラムの変更を要求することなく、汎用ＣＰＵで実行できるようにする技術が要望されている。
【課題を解決するための手段】
【０００６】
[0006]本発明の一実施形態は、変換されたアプリケーションプログラムを実行するように汎用プロセッサを構成するための方法について述べる。この方法は、マルチコアグラフィック処理システムで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムから変換されたものである前記変換されたアプリケーションプログラムを受け取り、そしてその変換されたアプリケーションプログラムをコンパイルして、汎用プロセッサにより実行するためのコンパイルされたコードを発生することを含む。コンパイルされたコードを実行するために利用できる汎用プロセッサ内の実行コアの数が決定され、その数の実行コアをイネーブルするように汎用プロセッサが構成される。コンパイルされたコードは、その数の実行コアを含む汎用プロセッサによって実行するために起動される。
【０００７】
[0007]ここに開示する方法の１つの効果は、マルチコアＧＰＵで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムを、変更せずに汎用ＣＰＵへ移行できることである。マルチコアＧＰＵの特定の特徴に依存するアプリケーションの部分は、トランスレータにより、汎用ＣＰＵで実行するように変換される。アプリケーションプログラムは、同期独立インストラクションの領域へ区画化される。これらインストラクションは、収斂又は発散として分類され、領域間で共有される発散メモリ参照が複写される。汎用ＣＰＵにより実行される間に種々のスレッド間にメモリの正しい共有を保証するためにスレッドループが挿入される。
【０００８】
[0008]上述した本発明の特徴を詳細に理解できるように、前記で簡単に要約した本発明について、幾つかを添付図面に例示した実施形態を参照して、より詳細に説明する。しかしながら、添付図面は、本発明の典型的な実施形態を例示するに過ぎず、それ故、本発明の範囲をそれに限定するものではなく、本発明は、同等の効果を発揮できる他の実施形態も包含できるものであることに注意されたい。
【図面の簡単な説明】
【０００９】
【図１】コンピュータシステムを示すブロック図である。
【図２】本発明の一実施形態によるコンピュータシステムを例示するブロック図である。
【図３Ａ】マルチコアグラフィック処理ユニットにより実行するために書かれたコードを、本発明の一実施形態により、汎用プロセッサにより実行するためのコードに変換するための方法ステップを示すフローチャートである。
【図３Ｂ】本発明の一実施形態により、入力コードを区画化されたコードに変換するところを示す概念図である。
【図３Ｃ】本発明の一実施形態により、入力コードを最適化されたコードに変換するところを示す概念図である。
【図４】本発明の一実施形態により、変換されたコードを汎用プロセッサによって実行するための方法ステップを示すフローチャートである。
【発明を実施するための形態】
【００１０】
[0015]以下の説明では、本発明をより完全に理解するために多数の特定の細部について説明する。しかしながら、当業者であれば、これらの特定の細部の１つ以上がなくても、本発明を実施できることが明らかであろう。他の点について、本発明を不明瞭にしないために、良く知られた特徴は、説明しない。
【００１１】
[0016]図１は、ＣＵＤＡを使用して書かれたコードを実行するように構成されたコンピュータシステム１００を示すブロック図である。このコンピュータシステム１００は、メモリブリッジ１０５を含むバス経路を経て通信するＣＰＵ１０２及びシステムメモリ１０４を備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ１０５は、バス又は他の通信経路１０６（例えば、ハイパートランスポートリンク）を経てＩ／Ｏ（入力／出力）ブリッジ１０７に接続される。例えば、サウスブリッジ(Southbridge)チップでよいＩ／Ｏブリッジ１０７は、１つ以上のユーザ入力装置１０８（例えば、キーボード、マウス）からユーザ入力を受け取り、そしてその入力を、経路１０６及びメモリブリッジ１０５を経てＣＰＵ１０２へ転送する。メモリブリッジ１０５には、バス又は他の通信経路１１３（例えば、ＰＣＩエクスプレス、アクセラレーテッドグラフィックポート又はハイパートランスポートリンク）を経てマルチスレッド型処理サブシステム１１２が結合される。一実施形態では、このマルチスレッド型処理サブシステム１１２は、ディスプレイ装置１１０（例えば、従来のＣＲＴ又はＬＣＤベースのモニタ）へピクセルを配送するグラフィックサブシステムである。Ｉ／Ｏブリッジ１０７には、システムディスク１１４も接続される。スイッチ１１６は、Ｉ／Ｏブリッジ１０７と、他のコンポーネント、例えば、ネットワークアダプタ１１８及び種々のアドイン(add-in)カード１２０、１２１との間の接続をなす。又、Ｉ／Ｏブリッジ１０７には、ＵＳＢ又は他のポート接続部、ＣＤドライブ、ＤＶＤドライブ、フィルムレコーディング装置、等を含む他のコンポーネント（明確に示さず）を接続することもできる。図１における種々のコンポーネントを相互接続する通信経路は、適当なプロトコル、例えば、ＰＣＩ（周辺コンポーネント相互接続）、ＰＣＩ−エクスプレス（ＰＣＩ−Ｅ）、ＡＧＰ（アクセラレーテッドグラフィックポート）、ハイパートランスポート、或いは他のバス又はポイント・ツー・ポイント通信プロトコルを使用して実施することができ、そして異なる装置間の接続は、この技術で知られたように異なるプロトコルを使用することができる。
【００１２】
[0017]ＣＰＵ１０２は、コンピュータシステム１００の制御プロセッサとして動作し、他のシステムコンポーネントの動作を管理し且つ整合させる。特に、ＣＰＵ１０２は、マルチスレッド型処理サブシステム１１２内の並列プロセッサ１３４の動作を制御するコマンドを発生する。ある実施形態では、ＣＰＵ１０２は、並列プロセッサ１３４のためのコマンドのストリームをコマンドバッファ（図示せず）に書き込み、コマンドバッファは、システムメモリ１０４、サブシステムメモリ１３８、或いはＣＰＵ１０２及び並列プロセッサ１３４の両方にアクセス可能な別の記憶位置に常駐することができる。並列プロセッサ１３４は、コマンドバッファからコマンドストリームを読み取り、そしてＣＰＵ１０２のオペレーションに対して非同期でコマンドを実行する。
【００１３】
[0018]システムメモリ１０４は、オペレーティングシステムの実行映像、装置ドライバ１０３、及びマルチスレッド型処理サブシステム１１２により実行するように構成されたＣＵＤＡコード１０１を備えている。ＣＵＤＡコード１０１は、マルチスレッド型処理サブシステム１１２で実行されるように意図されたプログラミングインストラクションを組み込んでいる。この説明の文脈において、コードとは、コンピュータコード、インストラクション、及び／又はプロセッサを使用して実行できるファンクションを指す。例えば、種々の実施形態において、コードは、Ｃコード、Ｃ＋＋コード、等を含んでもよい。一実施形態において、コードは、コンピュータ言語の言語拡張（例えば、Ｃ、Ｃ＋＋、等の拡張）を含んでもよい。
【００１４】
[0019]オペレーティングシステムは、コンピュータシステム１００のオペレーションを管理し整合するための詳細なインストラクションを与える。装置ドライバ１０３は、マルチスレッド型処理サブシステム１１２、特に、並列プロセッサ１３４のオペレーションを管理し整合するための詳細なインストラクションを与える。更に、装置ドライバ１０３は、並列プロセッサ１３４に対して特別に最適化されたマシンコードを発生するための編集設備を備えてもよい。又、装置ドライバ１０３は、ＮＶＩＤＩＡ社により提供されるＣＵＤＡＴＭフレームワークに関連して設けられてもよい。
【００１５】
[0020]一実施形態では、マルチスレッド型処理サブシステム１１２は、１つ以上の並列プロセッサ１３４を組み込んでおり、これら並列プロセッサは、例えば、プログラム可能なプロセッサ、特定用途向け集積回路（ＡＳＩＣ）のような１つ以上の集積回路装置を使用して実施することができる。並列プロセッサ１３４は、グラフィック及びビデオ処理に最適な回路を含み、例えば、ビデオ出力回路、及びグラフィック処理回路（ＧＰＵ）を含む。別の実施形態では、マルチスレッド型処理サブシステム１１２は、メモリブリッジ１０５、ＣＰＵ１０２、及びＩ／Ｏブリッジ１０７のような１つ以上の他のシステム要素と一体化されて、システムオンチップ（ＳｏＣ）を形成することができる。１つ以上の並列プロセッサ１３４がディスプレイ装置１１０へデータを出力してもよいし、又は各並列プロセッサ１３４が１つ以上のディスプレイ装置１１０にデータを出力してもよい。
【００１６】
[0021]並列プロセッサ１３４は、１つ以上の処理コアを含む高度に並列なプロセッサを実施するのが好都合であり、各処理コアは、非常に多数のスレッドを同時に実行することができ、又、各スレッドは、コード１０１のようなプログラムのインスタンスである。並列プロセッサ１３４は、これに限定されないが、直線的及び非直線的なデータ変換、ビデオ及び／又はオーディオデータのフィルタリング、モデリングオペレーション（例えば、物理の法則を適用して、物体の位置、速度及び他の属性を決定する）、映像レンダリングオペレーション（例えば、モザイクシェーダー、頂点シェーダー、幾何学的シェーダー、及び／又はピクセルシェーダープログラム）、等を含む種々様々なアプリケーションに関連した処理タスクを実行するようにプログラムすることができる。並列プロセッサ１３４は、システムメモリ１０４及び／又はローカルサブシステムメモリ１３８からローカル（オンチップ）メモリへデータを転送し、データを処理し、そして結果のデータをシステムメモリ１０４及び／又はサブシステムメモリ１３８へ書き込み、そこで、このデータは、ＣＰＵ１０２又は別のマルチスレッド型処理サブシステム１１２を含む他のシステムコンポーネントによってアクセスすることができる。
【００１７】
[0022]並列プロセッサ１３４は、任意の量のサブシステムメモリ１３８が設けられてもよく、又、サブシステムメモリ１３８を含まなくてもよく、更に、サブシステムメモリ１３８及びシステムメモリ１０４を任意の組み合わせで使用してもよい。例えば、並列プロセッサ１３４は、一体化メモリアーキテクチャー（ＵＭＡ）実施形態では、グラフィックプロセッサでよい。このような実施形態では、専用のサブシステムメモリ１３８は、ほとんど又は全く設けられず、そして並列プロセッサ１３４は、システムメモリ１０４を排他的に又はほぼ排他的に使用する。ＵＭＡ実施形態では、並列プロセッサ１３４は、ブリッジチップ又はプロセッサチップに一体化されてもよいし、或いはブリッジチップ又は他の通信手段を経て並列プロセッサ１３４をシステムメモリ１０４に接続する高速リンク（例えば、ＰＣＩ−Ｅ）と共に個別のチップとして設けられてもよい。
【００１８】
[0023]上述したように、マルチスレッド型処理サブシステム１１２には、多数の並列プロセッサ１３４を含ませることができる。例えば、複数の並列プロセッサ１３４を単一のアドインカードに設けることもできるし、複数のアドインカードを通信経路１１３に接続することもできるし、又は１つ以上の並列プロセッサ１３４をブリッジチップに一体化することもできる。複数の並列プロセッサ１３４が存在する場合には、それらの並列プロセッサ１３４は、単一の並列プロセッサ１３４で可能である以上に高いスループットでデータを処理するように並列に動作することができる。１つ以上の並列プロセッサ１３４を組み込んだシステムは、デスクトップ、ラップトップ、ハンドヘルドパーソナルコンピュータ、サーバー、ワークステーション、ゲームコンソール、埋め込み型システム、等を含む種々のコンフィギュレーション及びフォームファクタで実施することができる。
【００１９】
[0024]並列プロセッサ１３４の幾つかの実施形態では、単一インストラクション・複数データ（ＳＩＭＤ）インストラクション発行技術を使用して、複数の独立したインストラクションユニットを設けずに非常に多数のスレッドの並列実行をサポートする。他の実施形態では、単一インストラクション・複数スレッド（ＳＩＭＴ）技術を使用して、非常に多数の一般的に同期されたスレッドの並列実行をサポートする。全ての処理エンジンが典型的に同じインストラクションを実行するＳＩＭＤ実行形態とは異なり、ＳＩＭＴの実行は、異なるスレッドが、所与のスレッドプログラムを通して、発散する実行経路を容易にたどれるようにする。当業者であれば、ＳＩＭＤ処理形態は、ＳＩＭＴ処理形態の機能的サブセットを表すことが理解されよう。並列プロセッサ１３４内のファンクションユニットは、整数及び浮動小数点演算（例えば、加算及び乗算）、比較演算、ブール演算（ＡＮＤ、ＯＲ、ＸＯＲ）、ビットシフト、及び種々の代数関数の計算（例えば、二次元補間、三角法、指数関数、対数関数、等）を含む種々のオペレーションをサポートする。
【００２０】
[0025]並列プロセッサ１３４の処理コア（図示せず）内の特定の処理ユニット（図示せず）へ送信される一連のインストラクションは、既に定義されたスレッドを構成し、そして１つの処理コア内で処理ユニットにわたって同時に実行されるある数のスレッドの集合を、ここでは、「スレッドグループ」と称する。ここで使用される「スレッドグループ」は、異なる入力データに対して同じプログラムを実行するスレッドのグループを指し、グループの各スレッドは、処理コア内の異なる処理ユニットに指定される。１つのスレッドグループは、処理ユニットの数より少ないスレッドを含んでもよく、この場合、ある処理ユニットは、そのスレッドグループが処理されているときのサイクル中にアイドル状態となる。又、１つのスレッドグループは、処理ユニットの数より多くのスレッドを含んでもよく、この場合、処理は、複数のクロックサイクルにわたって行われる。
【００２１】
[0026]各処理コアは、Ｇ個までのスレッドグループを同時にサポートできるので、並列プロセッサ１３４内の処理コアの数をＭとすれば、所与の時間に処理コアにおいてＧｘＭ個までのスレッドグループを実行できることになる。更に、処理コア内で同時に複数の関連スレッドグループがアクティブになり得る（異なる実行段階において）。スレッドグループのこの集合を、ここでは、「協働スレッドアレイ」（ＣＴＡ）と称する。ＣＴＡのサイズは、一般的に、プログラマーにより、ＣＴＡに利用できるメモリ又はレジスタのようなハードウェアリソースの量で決定される。ＣＵＤＡプログラミングモデルは、ＧＰＵアクセラレータのシステムアーキテクチャーを表す。排他的ローカルアドレススペースが各スレッドに利用でき、そしてＣＴＡごとの共有アドレススペースを使用して、ＣＴＡ内のスレッド間にデータを通す。又、処理コアは、オフチップの「グローバル」メモリにアクセスすることもでき、これは、例えば、サブシステムメモリ１３８及び／又はシステムメモリ１０４を含むことができる。
【００２２】
[0027]ＣＵＤＡアプリケーションプログラムのホスト部分は、カーネルファンクションがＣＴＡ処理を指定する間に、従来の方法及びツールを使用してコンパイルされる。最も高いレベルにおいて、ＣＵＤＡメモリモデルは、ホスト及び装置のメモリスペースを分離し、ホストコード及びカーネルコードがそれらの各メモリスペースに直接アクセスすることしかできないようにする。ＡＰＩ（アプリケーションプログラミングインターフェイス）ファンクションは、ホスト及び装置のメモリスペース間でデータをコピーするのを許す。ＣＵＤＡプログラミングモデルの共有メモリＣＰＵ実行では、制御ＣＰＵスレッドが、潜在的なデータ競合を伴わずに、並列ＣＴＡと並列に実行することができる。ホストメモリスペースは、Ｃプログラミング言語によって定義され、そして装置メモリスペースは、グローバル、定数、ローカル、共有及びテクスチャとして指定される。全てのスレッドは、グローバル、定数及びテクスチャメモリスペースにアクセスすることができる。上述したように、ローカルスペースへのアクセスは、単一スレッドに制限され、そして共有スペースへのアクセスは、ＣＴＡ内のスレッドに制限される。このメモリモデルは、待ち時間の短いアクセスに対して小さなメモリスペースの使用を奨励し、そして典型的に待ち時間の長い大きなメモリスペースの賢明な使用を奨励する。
【００２３】
[0028]コード１０１のようなＣＵＤＡプログラムは、典型的に、１つ、２つ又は３つの次元、例えば、ｘ、ｙ及びｚにおいて、ＣＴＡの同期又は非同期実行のセットとして編成される。３タプルインデックスは、スレッドブロック内のスレッドを独特に識別する。スレッドブロックそれ自体は、暗示的に定義された２タプル変数により区別される。これらインデックスの範囲は、ランタイムに定義され、そしてランタイム環境は、インデックスが何らかのハードウェア制限に適合することをチェックする。各ＣＴＡは、並列プロセッサ１３４により他のＣＴＡと並列に実行される。各並列プロセッサ１３４が１つ以上のＣＴＡを実行するようにして、多数のＣＴＡが並列に実行される。ランタイム環境は、ＣＵＤＡコード１０１の実行を必要に応じて同期又は非同期で管理する役割を果たす。ＣＴＡ内のスレッドは、共有メモリと、ｓｙｎｃｈｔｈｒｅａｄｓ（）と称されるバリア同期プリミティブとの使用により、互いに通信し且つ同期する。ＣＵＤＡは、スレッドブロック内のスレッドが同時に生きていることを保証すると共に、スレッドブロック内のスレッドが迅速なバリア同期及びローカルデータ共有を遂行するためのコンストラクトを与える。（１つ以上の次元によって定義される）ＣＴＡ内の個別のスレッドブロックは、それらの生成、実行又は退出について何ら順序付けを課さない。更に、並列なＣＴＡは、Ｉ／Ｏを含むシステムコールへのアクセスが許されない。ＣＵＤＡプログラミングモデルは、並列なＣＴＡ間にグローバルな同期を強要するだけであり、ＣＴＡ内のブロック間での限定された通信に対して固有のアトミックなオペレーションを与える。
【００２４】
[0029]カーネルと称される各スレッドの本体は、メモリモデルアノテーション及びバリア同期プリミティブを用いて標準Ｃで表わされるＣＵＤＡを使用して指定される。ＣＵＤＡプログラムのセマンティックは、バリア同期プリミティブによって暗示されるメモリの順序付けを尊重する順序でＣＴＡ内の全てのスレッドにより各カーネルが実行されるというものである。特に、バリア同期プリミティブの前に生じるＣＴＡ内の全ての共有メモリ参照は、バリア同期プリミティブの後に生じる共有メモリ参照の前に完了しなければならない。
【００２５】
[0030]カーネルコードにおけるバリア同期プリミティブの各インスタンスは、概念的に個別の論理的バリアを表わし、スタティックとして取り扱われねばならない。ＣＵＤＡスレッドが“if-else”コンストラクトの異なる分岐を取り得るときには、そのコンストラクトの両経路においてバリア同期プリミティブを呼び出すのは不法である。スレッドブロック内の全てのスレッドは、同期プリミティブの１つに到達するが、スレッドが全部到達するか全く到達しないかのいずれかを各々要求する別々のバリアを表わす。それ故、このようなカーネルは、正しく実行されない。より一般的には、ＣＵＤＡコードは、スレッドブロック内の異なるスレッドに対して異なる振舞いをする制御フローコンストラクト内に同期プリミティブが収容される場合には、正しく実行されると保証されない。
【００２６】
[0031]図２は、本発明の一実施形態によるコンピュータシステム２００を示すブロック図である。コンピュータシステム１００は、ＣＰＵ２０２と、メモリブリッジ２０５を含むバス経路を経て通信するシステムメモリ２０４とを備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ２０５は、バス又は他の通信経路１０６（例えば、ハイパートランスポートリンク）を経てＩ／Ｏ（入力／出力）ブリッジ１０７に接続される。ＣＰＵ２０２は、ディスプレイ装置２１０（例えば、従来のＣＲＴ又はＬＣＤベースのモニタ）に表示するための出力を発生する。
【００２７】
[0032]マルチスレッド型処理サブシステム１１２は、コンピュータシステム２００には含まれず、ＣＵＤＡコード１０１は、ＣＰＵ２０２のような汎用プロセッサによって実行するように適応されない。ＣＵＤＡコード１０１は、マルチスレッド型処理サブシステム１１２によって実行するように適応され、トランスレータ２２０を使用して変換されて、バリア同期プリミティブを含まない変換されたコード２０１を発生する。ＣＰＵ２０２がコード１０１により表わされたプログラムを実行するために、コード１０１を先ずコード２０１に変換しなければならない。変換されたコードは、次いで、ＣＰＵ２０２によって実行するために、コンパイラー２２５によりコンパイルされる。コンパイラー２２５は、ＣＰＵ２０２に対して特有の最適化を遂行することができる。コードを変換することは、第１のコンピュータ言語で書かれたコードを、第２のコンピュータ言語に変換することを指す。コードをコンパイルすることは、コンピュータ言語（例えば、ソースコード）で書かれたコードを、別のコンピュータ言語（例えば、オブジェクトコード）に変換することを指す。トランスレータ２２０は、図３Ａを参照して説明し、コンパイラー２２５は、図４を参照して説明する。コンパイラー２２５は、コード１０１と、コード２０１と、ＣＰＵ２０２との間をインターフェイスするように構成された装置ドライバ２０３内に含まれる。ランタイム環境２２７は、コンパイルされたコードに対するファンクション、例えば、入力及び出力、メモリ管理、等を実施するように構成される。又、ランタイム環境２２７は、ＣＰＵ２０２により実行するためのコンパイルされたコードを起動する。トランスレータ２２０は、ＣＵＤＡスレッドグループの微粒度スレッドにわたるオペレーションを単一のＣＰＵスレッドへと直列化するための最適化変換を遂行し、一方、ランタイム環境２２７は、スレッドグループを、ＣＰＵ２０２により並列処理するためのワークユニットとしてスケジュールする。
【００２８】
[0033]汎用ＣＰＵにより実行するためにＧＰＵで実行されるように設計されたＣＵＤＡアプリケーションの一次障害防止移行性は、並列性の粒度である。従来のＣＰＵは、単一のＣＵＤＡ ＣＴＡに要求される数百のハードウェアスレッドコンテクストをサポートしない。それ故、汎用ＣＰＵにおいてＣＵＤＡプログラミングモデルを実施するシステムの一次目標は、タスクレベルの並列性を、利用可能なＣＰＵコアに分配することである。それと同時に、システムは、過剰なスケジューリングオーバーヘッド及び頻繁なコア間同期を防止するためにタスク内のマイクロスレッドを単一のＣＰＵスレッドへと合併しなければならない。
【００２９】
[0034]図３Ａは、本発明の一実施形態に基づき、例えば、マルチスレッド型処理サブシステム１１２のようなマルチコアグラフィック処理システムにより実行するために書かれたコード１０１を、例えば、ＣＰＵ２０２のような汎用プロセッサによって実行するためのコード２０１へ変換する方法ステップのフローチャートである。トランスレータ２２０は、図３Ａに示されたステップの１つ以上を遂行して、コード１０１に使用されるバリア同期プリミティブのセマンティックを保存する。トランスレータ２２０は、バリア同期プリミティブの周りでコード１０１を区画化することによって並列スレッドを「アンロール(unroll)」し、共有状態の使用を減少し、メモリアクセスに対する参照の位置関係を改善し、そして汎用プロセッサにより実行するためのＣＵＤＡ特有のコードを変換するためのスレッドループを挿入する。マルチスレッド型処理サブシステム１１２により実行するためにターゲットとされるＣＵＤＡコード１０１を変更せずにＣＰＵ２０２を使用してコード２０１を実行する良好な実行性能を得ることができる。コンパイラー２２５は、ＣＰＵ２０２により与えられるベクトルインストラクション能力を利用し、そして実行のためにコード２０１をコンパイルするときに最適化を遂行することができる。
【００３０】
[0035]ステップ３００において、トランスレータ２２０は、マルチスレッド型処理サブシステム１１２、又は１つ以上の並列プロセッサ１３４を含むプロセッサのようなマルチコアＧＰＵにより実行するために書かれたコード１０１、例えば、ＣＵＤＡコード１０１を受け取る。ステップ３００で受け取られたコードは、エッジによって接続された基本的ブロックノードより成る制御フローグラフとして表わすことができる。各々の基本的ブロックは、例えば、ＣＰＵ２０２のようなターゲット環境により遂行されるオペレーションを指定する。ステップ３０５において、トランスレータ２２０は、バリア同期プリミティブの周りでＣＵＤＡコード１０１を区画化して、区画化されたコードを発生する。区画化されたコードが図３Ｂ及び３Ｃに示されており、これらの図を参照して区画化プロセスを説明する。同期区画は、区画内の基本的ブロックの制御フロー及びデータフロー特性によりオペレーションの順序付けが完全に決定されるところのコードの領域である。区画は、並列スレッドを実行するために区画の周りにスレッドループを挿入できるという特性を有する。制御フローグラフを使用して、各同期スレッド(synchthread)プリミティブをエッジに置き換え、基本的ブロックノードを異なる区画に分離することにより、同期区画制御フローグラフを発生することができる。
【００３１】
[0036]ステップ３１０において、区画化されたコードを分類し、各ステートメントが収斂又は発散のいずれかとして識別されるようにする。区画化されたコードは、式及びステートメントを含むことができる。式は、定数、暗示的スレッドＩＤ、及びプログラマーにより形成される名前付き変数を伴うが、副作用や指定をもたない計算である。簡単なステートメントは、単一の指定を生じる計算式として定義される。又、一般的ステートメントは、バリア、制御フロー条件又はループコンストラクト、或いはステートメントの逐次ブロックを表すこともできる。ＣＴＡ次元ｘ、ｙ及びｚは、コードを通して伝播され、各オペレーションがＣＴＡ次元の１つ以上に依存するかどうか決定する。次元ｘ、ｙ及び／又はｚにおいてスレッドＩＤ(threadID)（スレッド識別子）を参照するオペレーションは、発散と考えられる。というのは、ＣＴＡ次元を参照するスレッドは、実行中に同じＣＴＡの他のスレッドから発散し得るからである。例えば、スレッドＩＤ．ｘ(threadID.x)に依存するオペレーションは、ｘ次元に対して発散である。スレッドＩＤ．ｘに依存しない別のオペレーションは、ｘ次元において収斂である。発散ステートメントは、それらが参照する各ＣＴＡ次元に対してスレッドループを要求する。
【００３２】
[0037]ステップ３１５において、区画化されたコードは、分類情報を使用して性能に対して最適化され、最適化されたコードを発生する。例えば、区画内のインストラクションは、オペレーションを融合させるように再順序付けされ、同じ分類をもつオペレーションが一緒にグループ編成されて、ステップ３２５で挿入される同じスレッドループ内に入ることができるようにする。分散ベクトルにおいてスレッドＩＤ次元がより少ないオペレーションが、より多くのスレッドＩＤ次元に依存するオペレーションに先行するように、オペレーションが順序付けされる。この再順序付けは、有効である。というのは、ステートメントは、それが依存するステートメントの分散ベクトルのスーパーセットである分散ベクトルを有していなければならないからである。従って、分散ベクトルに１つの次元しかもたないステートメントは、分散ベクトルに異なる次元又は２つ以上の次元をもつステートメントに依存することができない。
【００３３】
[0038]ステップ３２０において、最適化されたコードにおけるスレッド−ローカルメモリ参照は、オブジェクトの各インスタンスが、値を記憶すべき独特の位置をもつよう保証するために、必要に応じてアレイ参照へ昇格される。特に、ある区画から別の区画へ搬送されるデータは、各区画においてそれが得られるように複写される必要がある。次の条件の１つを満足する変数は、アレイ参照へ昇格される。即ち、クロス区画依存性（ある区画において指定され、そして別の区画において参照される）を有するローカル変数。
【００３４】
[0039]ステップ３２０において、トランスレータ２２０は、スレッド−ローカルメモリ参照をアレイ参照へ昇格させる。テーブル１に示すプログラムは、同期バリアプリミティブ及び発散参照を含む。
【表１】
【００３５】
[0040]テーブル１に示すプログラムは、同期スレッドプリミティブの前に第１区画へそして同期スレッドプリミティブの後に第２区画へと区画化される。第２区画は、第１区画で計算された参照（左インデックス(leftIndex)及び右インデックス(rightIndex)）を含み、ＣＴＡ次元から従属する。発散参照が昇格されない場合には、第２区画は、第１区画の最後の繰り返しにより計算された値を誤って使用する。第２区画は、第１区画のｔｈｒｅａｄＩｄ．ｘの各対応する繰り返しに対して計算された値を使用しなければならない。計算が正しいことを保証するために、発散参照は、テーブル２に示すように昇格される。
【表２】
【００３６】
[0041]ステップ３２５において、スレッドＩＤ次元を分散ベクトルに含むステートメントに対してスレッドループが発生される。ループ交換、ループ分裂及びループ不変量除去と同等の変換を同時に評価して、最良の冗長性除去を達成するために、適応ループネストが使用される。ネスト状のループは、アプリケーションに最も適するようにスレッドＩＤタプルの各次元の値に対して動的に発生されるのであって、特定のループネストを仮定して、そのネストに基づいてアプリケーションを評価するのではない。ステップ３１５においてステートメントが順序付けされた後に、分散ベクトルに次元を含むステートメントの周りのみでスレッドＩＤ次元に対してループを発生することができる。ループのオーバーヘッドを除去するために、トランスレータ２２０は、あるものが他のもののサブセットである分散ベクトルを有するような隣接ステートメントグループを融合することができる。
【００３７】
[0042]図３Ｂは、本発明の一実施形態により、入力コード１０１を区画されたコード３５０へ変換するところを示す概念図である。入力コード３３０は、マルチスレッド型処理サブシステム１１２により実行するように構成され、同期バリアインストラクション３３６で分離されたコードシーケンス３３１及び３３２を含む。ＣＴＡにおける全てのスレッドは、いずれか１つのスレッドがコードシーケンス３３２の実行を開始する前にコードシーケンス３３１の実行を完了する。トランスレータ２２０は、入力コード３３０を区画化して、区画化されたコード３５０を発生し、区画３５１は、コードシーケンス３３１により表わされたインストラクションを含み、そして区画３５２は、コードシーケンス３３２により表わされたインストラクションを含む。区画化されたコード３５０が、同期バリアインストラクションを本来サポートしない汎用プロセッサにより実行されるときに、同期セマンティックが維持されるように保証するために、スレッドループ３５３が区画３５２の周りに挿入される。この実施例では、コード区画３５１が収斂参照を含み、区画３５２が発散参照を含む。それ故、スレッドループ３５３が区画３５２の周りに挿入される。
【００３８】
[0043]図３Ａのステップ３２５において、トランスレータ２２０は、（スレッドループ３５３のような）スレッドループを、最適化されたコードに挿入し、ＣＰＵ２０２により実行するために変換されたコード２０１を発生する。各区画は、各ＣＴＡ次元に対して挿入されたスレッドループを有することができる。同期区画化及びスレッドループ挿入の一実施例がテーブル３及び４に示されている。テーブル３に示されたプログラムは、テーブル４に示されたプログラムへと変換される。
【表３】
【００３９】
[0044]テーブル３のプログラムは、ＣＴＡにおける種々のスレッド間でのメモリの正しい共有を保証するために明確な同期を使用する。トランスレータ２２０は、プログラムを、ｘＣＴＡ次元に各々依存する２つの区画に区画化する。それ故、スレッドループは、変換されたプログラムがオペレーションを正しい順序で遂行するよう保証するために２つの区画の各々の周りに挿入される。
【表４】
【００４０】
[0045]汎用プロセッサにより実行するためのプログラムを挿入するより簡単な技術は、各ＣＴＡ次元に対して明確なスレッドループを挿入し、同じ区画内の参照に対する次元依存性を決定する必要がないようにすることである。例えば、テーブル５に示すプログラムは、テーブル６に示すプログラムへ変換される。次元の依存性を決定することなくプログラムが形成されるので、テーブル５において挿入されるスレッドループの１つ以上が不必要であることに注意されたい。
【表５】
【表６】
【００４１】
[0046]図３Ｃは、本発明の一実施形態により、入力コード３３３を、最適化されたコード３６０へ変換するところを示す概念図である。入力コード３３３は、マルチスレッド型処理サブシステム１１２により実行するように構成され、同期バリアインストラクション３３５で分離されたコードシーケンス３３４及び３３８を含む。ＣＴＡにおける全てのスレッドは、いずれか１つのスレッドがコードシーケンス３３８の実行を開始する前にコードシーケンス３３４の実行を完了する。トランスレータ２２０は、入力コード３３３を区画化して、区画化されたコード３６０を発生し、区画３６１は、コードシーケンス３３４により表わされたインストラクションを含み、そして区画３６２、３６４及び３６５は、コードシーケンス３３８により表わされたインストラクションを含む。
【００４２】
[0047]区画３６２は、第１のＣＴＡ次元において発散であるインストラクションの第１部分を含む。区画３６４は、収斂であるインストラクションの第２部分を含む。区画３６５は、第２のＣＴＡ次元において発散であるインストラクションの第３部分を含む。同期バリアインストラクションを本来サポートしない汎用プロセッサによって区画化されたコード３６０が実行されるときに同期セマンティックが維持されるように保証するために、区画３６２の周りにスレッドループ３６３が挿入される。第１のＣＴＡ次元に対してスレッドループ３６３が繰り返される。スレッドループ３６６が、第２のＣＴＡ次元に対して繰り返されるように区画３６５の周りに挿入される。
【００４３】
[0048]テーブル７は、例示的ＣＵＤＡカーネルを示し、テーブル８は、汎用プロセッサにより実行するためのＣＵＤＡカーネルの変換を示す。例示的カーネルは、小さなマトリクスのリストを乗算する。各スレッドブロックは、リストから１つの小さなマトリクス乗算を計算し、一方、各スレッドは、そのブロックに対して結果のマトリクスの１つのエレメントを計算する。
【表７】
【００４４】
[0049]テーブル７の行（９）のステートメントは、列がｘ次元に依存し、行がｙ次元に依存するので、（ｘ、ｙ）の分散ベクトルを有することに注意されたい。ｚ次元は決して使用されず、従って、ｚに対して繰り返されるループが挿入されることはない。テーブル７に示す例示的カーネルにおいてステートメント５及び６のようなケースを決定するために、典型的なコスト分析技術を使用することができる。各々が１つのスレッドＩＤ次元にしか依存しないので、ｘ及びｙインデックスループのいずれかのネスト順序を選択することで、ステートメントの冗長な実行、又は区画のメインループネストの外部の冗長なループのいずれかが強制される。
【表８】
【００４５】
[0050]図４は、本発明の一実施形態に基づき、ＣＰＵ２０２のような汎用プロセッサにより、変換されたコード２０１を実行するための方法ステップのフローチャートである。ステップ４００において、コンパイラー２２５は、ＣＰＵ特有の最適化を任意に遂行する変換されたコード２０１をコンパイルして、コンパイルされたコードを発生する。ステップ４０５において、ＣＰＵ２０２に得られる実行コア４００の数は、装置ドライバ２０３により決定される。変換されたコード２０１は、性能改善のために利用可能な実行コアにおいて実行するように自動的にスケーリングされる。ステップ４１０において、ランタイム環境２２７又は装置ドライバ２０３は、変換されたコード２０１を実行する実行コアの数をイネーブルするようにＣＰＵ２０２を構成する。
【００４６】
[0051]ランタイム環境２２７は、環境変数により制御できる多数のオペレーティングシステム（ＯＳ）ランタイムスレッドを生成することができる。デフォールトとして、システム内のコアの数を、ＯＳランタイムスレッドの数として使用してもよい。ステップ４１０において、起動されるべきＣＵＤＡスレッドの数を評価して、ランタイムスレッドの数に統計学的に区画化することができる。各ランタイムスレッドは、コンパイルされたコードの一部分を逐次に実行し、バリアにおいて待機する。全てのランタイムスレッドがバリアに到達したときに、ＣＴＡが完了となる。ステップ４１５では、ランタイム環境２２７又は装置ドライバ２０３が、ＣＰＵ２０２により実行するためにコンパイルされたコードを起動する。
【００４７】
[0052]トランスレータ２２０、コンパイラー２２５及びランタイム環境２２７は、ＣＵＤＡアプリケーションプログラムを、汎用ＣＰＵにより実行するためのコードへ変換するのに使用される。ＣＵＤＡプログラミングモデルは、バルク同期タスクの並列性をサポートし、各タスクは、微粒度のＳＰＭＤスレッドより成る。ＣＵＤＡプログラミングモデルの使用は、ＧＰＵにより実行するための特殊なコードを書き込もうとするプログラマーに制限される。この特殊なコードは、プログラマーがＣＵＤＡアプリケーションプログラムをリライトすることを要求せずに、汎用ＣＰＵにより実行するように変換することができる。ＣＵＤＡによりサポートされる３つの重要なアブストラクションは、ＳＰＭＤスレッドブロック、バリア同期、及び共有メモリである。トランスレータ２２０は、ＣＵＤＡスレッドブロックの微粒度スレッドにわたるオペレーションを、単一のＣＰＵスレッドへと直列化し、そしてＣＵＤＡアプリケーションプログラムを変換するための最適化変換を遂行する。
【００４８】
[0053]以上、本発明の実施形態を説明したが、本発明の基本的な範囲から逸脱せずに、本発明の他の実施形態及び更に別の実施形態を案出することもできる。例えば、本発明の態様は、ハードウェア、又はソフトウェア、或いはハードウェアとソフトウェアの組合せで実施することもできる。本発明の一実施形態は、コンピュータシステムに使用するためのプログラム製品として実施することができる。プログラム製品のプログラム（１つ又は複数）は、（ここに述べる方法を含む）実施形態の機能を定義し、そして種々のコンピュータ読み取り可能な記憶媒体に含ませることができる。ここに例示するコンピュータ読み取り可能な記憶媒体は、（ｉ）情報が永久的に記憶される書き込み不能の記憶媒体（例えば、コンピュータ内のリードオンリメモリ装置、例えば、ＣＤ−ＲＯＭドライブにより読み取り可能なＣＤ−ＲＯＭディスク、フラッシュメモリ、ＲＯＭチップ、又は任意の形式のソリッドステート不揮発性半導体メモリ）、及び（ii）変更可能な情報が記憶される書き込み可能な記憶媒体（例えば、ディスケットドライブ又はハードディスクドライブ内のフロッピーディスク、又は任意の形式のソリッドステートランダムアクセス半導体メモリ）を含むが、これらに限定されない。このようなコンピュータ読み取り可能な記憶媒体は、本発明のファンクションを指令するコンピュータ読み取り可能なインストラクションを搬送するとき、本発明の実施形態となる。それ故、本発明の範囲は、特許請求の範囲によって決定される。
【符号の説明】
【００４９】
１００・・・コンピュータシステム、１０１・・・コード、１０２・・・ＣＰＵ、１０３・・・装置ドライバ、１０４・・・システムメモリ、１０５・・・メモリブリッジ、１０６・・・通信経路、１０７・・・Ｉ／Ｏブリッジ、１０８・・・入力装置、１１０・・・ディスプレイ装置、１１２・・・マルチスレッド型処理サブシステム、１１３・・・通信経路、１１４・・・システムディスク、１１６・・・スイッチ、１１８・・・ネットワークアダプタ、１２０・・・アドインカード、１２１・・・アドインカード、１３４・・・並列プロセッサ、１３８・・・サブシステムメモリ、２００・・・コンピュータシステム、２０１・・・コード、２０２・・・ＣＰＵ、２０３・・・装置ドライバ、２０４・・・システムメモリ、２０５・・・メモリブリッジ、２１０・・・ディスプレイ装置、２２０・・・トランスレータ、２２５・・・コンパイラー、２２７・・・ランタイム環境
【特許請求の範囲】
【請求項１】
変換されたアプリケーションプログラムを実行するように構成されたコンピューティングシステムであって、
コンパイラーを実行するように構成された汎用プロセッサと、
前記プロセッサに結合され、前記変換されたアプリケーションプログラム及びコンパイルされたコードを記憶するように構成されたシステムメモリと、
を備え、前記コンパイラーは、
マルチコアグラフィック処理ユニットで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムから変換されたものである前記変換されたアプリケーションプログラムを受け取り、
前記変換されたアプリケーションプログラムをコンパイルして、前記汎用プロセッサにより実行するためのコンパイルされたコードを発生する、
というように構成され、更に、
装置ドライバであって、
前記変換されたアプリケーションプログラムを実行するのに利用できる前記汎用プロセッサ内の実行コアの数を決定し、
前記数の実行コアをイネーブルするように前記汎用プロセッサを構成する、
というように構成された装置ドライバと、
前記数の実行コアを含む前記汎用プロセッサにより実行するために前記コンパイルされたコードを起動するように構成されたランタイム環境と、
を備えるコンピューティングシステム。
【請求項２】
前記変換されたアプリケーションプログラムは、協働スレッドアレイにおけるスレッドのいずれか１つが前記変換されたアプリケーションプログラムの第２領域の実行を開始する前にその協働スレッドアレイにおける全てのスレッドが区画化されたアプリケーションプログラムの第１領域の実行を完了するよう保証するために、前記区画化されたアプリケーションプログラムの第１領域の周りに第１ループネストを含む、請求項１に記載のコンピューティングシステム。
【請求項３】
前記第１ループは、前記協働スレッドアレイの１つ以上の次元に対して繰り返される、請求項２に記載のコンピュータシステム。
【請求項４】
前記変換されたアプリケーションプログラムは、前記アプリケーションプログラムを、同期独立インストラクションの領域へと区画化して、区画化されたアプリケーションプログラムを発生し、そしてその区画化されたアプリケーションプログラムの少なくとも１つの領域の周りにループを挿入することにより発生され、前記ループは、前記マルチコアグラフィック処理ユニット内の並列プロセッサにより同時に実行される多数のスレッドに対応する協働スレッドアレイ次元に対して繰り返される、請求項１に記載のコンピューティングシステム。
【請求項５】
前記区画化されたアプリケーションプログラムの第１領域は、同期バリアインストラクションの前にあるインストラクションを含み、前記区画化されたアプリケーションプログラムの第２領域は、前記同期バリアインストラクションの後にあるインストラクションを含む、請求項４に記載のコンピューティングシステム。
【請求項６】
前記区画化されたアプリケーションプログラムの少なくとも１つの領域の周りに付加的なループを挿入して、前記変換されたアプリケーションプログラムを発生し、前記付加的なループは、異なる協働スレッドアレイ次元に対して繰り返される、請求項５に記載のコンピューティングシステム。
【請求項７】
前記区画化されたアプリケーションプログラムは、各ステートメントを、前記協働スレッドアレイ次元に対して収斂又は発散のいずれかとして識別するように分類される、請求項４に記載のコンピューティングシステム。
【請求項８】
前記汎用プロセッサは、更に、前記コンパイルされたコードを実行するように構成される、請求項１に記載のコンピュータシステム。
【請求項９】
前記汎用プロセッサは、更に、前記汎用プロセッサに特有の最適化を遂行するように構成される、請求項１に記載のコンピュータシステム。
【請求項１０】
マルチコアグラフィック処理ユニットで実行するために並列プログラミングモデルを使用して書かれた前記アプリケーションプログラムは、ＣＵＤＡ（コンピュート・ユニファイド・デバイス・アーキテクチャー）アプリケーションプログラムである、請求項１に記載のコンピューティングシステム。
【請求項１】
変換されたアプリケーションプログラムを実行するように構成されたコンピューティングシステムであって、
コンパイラーを実行するように構成された汎用プロセッサと、
前記プロセッサに結合され、前記変換されたアプリケーションプログラム及びコンパイルされたコードを記憶するように構成されたシステムメモリと、
を備え、前記コンパイラーは、
マルチコアグラフィック処理ユニットで実行するために並列プログラミングモデルを使用して書かれたアプリケーションプログラムから変換されたものである前記変換されたアプリケーションプログラムを受け取り、
前記変換されたアプリケーションプログラムをコンパイルして、前記汎用プロセッサにより実行するためのコンパイルされたコードを発生する、
というように構成され、更に、
装置ドライバであって、
前記変換されたアプリケーションプログラムを実行するのに利用できる前記汎用プロセッサ内の実行コアの数を決定し、
前記数の実行コアをイネーブルするように前記汎用プロセッサを構成する、
というように構成された装置ドライバと、
前記数の実行コアを含む前記汎用プロセッサにより実行するために前記コンパイルされたコードを起動するように構成されたランタイム環境と、
を備えるコンピューティングシステム。
【請求項２】
前記変換されたアプリケーションプログラムは、協働スレッドアレイにおけるスレッドのいずれか１つが前記変換されたアプリケーションプログラムの第２領域の実行を開始する前にその協働スレッドアレイにおける全てのスレッドが区画化されたアプリケーションプログラムの第１領域の実行を完了するよう保証するために、前記区画化されたアプリケーションプログラムの第１領域の周りに第１ループネストを含む、請求項１に記載のコンピューティングシステム。
【請求項３】
前記第１ループは、前記協働スレッドアレイの１つ以上の次元に対して繰り返される、請求項２に記載のコンピュータシステム。
【請求項４】
前記変換されたアプリケーションプログラムは、前記アプリケーションプログラムを、同期独立インストラクションの領域へと区画化して、区画化されたアプリケーションプログラムを発生し、そしてその区画化されたアプリケーションプログラムの少なくとも１つの領域の周りにループを挿入することにより発生され、前記ループは、前記マルチコアグラフィック処理ユニット内の並列プロセッサにより同時に実行される多数のスレッドに対応する協働スレッドアレイ次元に対して繰り返される、請求項１に記載のコンピューティングシステム。
【請求項５】
前記区画化されたアプリケーションプログラムの第１領域は、同期バリアインストラクションの前にあるインストラクションを含み、前記区画化されたアプリケーションプログラムの第２領域は、前記同期バリアインストラクションの後にあるインストラクションを含む、請求項４に記載のコンピューティングシステム。
【請求項６】
前記区画化されたアプリケーションプログラムの少なくとも１つの領域の周りに付加的なループを挿入して、前記変換されたアプリケーションプログラムを発生し、前記付加的なループは、異なる協働スレッドアレイ次元に対して繰り返される、請求項５に記載のコンピューティングシステム。
【請求項７】
前記区画化されたアプリケーションプログラムは、各ステートメントを、前記協働スレッドアレイ次元に対して収斂又は発散のいずれかとして識別するように分類される、請求項４に記載のコンピューティングシステム。
【請求項８】
前記汎用プロセッサは、更に、前記コンパイルされたコードを実行するように構成される、請求項１に記載のコンピュータシステム。
【請求項９】
前記汎用プロセッサは、更に、前記汎用プロセッサに特有の最適化を遂行するように構成される、請求項１に記載のコンピュータシステム。
【請求項１０】
マルチコアグラフィック処理ユニットで実行するために並列プログラミングモデルを使用して書かれた前記アプリケーションプログラムは、ＣＵＤＡ（コンピュート・ユニファイド・デバイス・アーキテクチャー）アプリケーションプログラムである、請求項１に記載のコンピューティングシステム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【公開番号】特開２００９−２５９２４１（Ｐ２００９−２５９２４１Ａ）
【公開日】平成２１年１１月５日（２００９．１１．５）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−８８９７２（Ｐ２００９−８８９７２）
【出願日】平成２１年４月１日（２００９．４．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０１２６１３００）エヌヴィディア コーポレイション (166)
【Ｆターム（参考）】
【公開日】平成２１年１１月５日（２００９．１１．５）
【国際特許分類】
【出願番号】特願２００９−８８９７２（Ｐ２００９−８８９７２）
【出願日】平成２１年４月１日（２００９．４．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０１２６１３００）エヌヴィディア コーポレイション (166)
【Ｆターム（参考）】
[ Back to top ]