(57)【要約】      （修正有）【課題】ハードウェア・プラットフォームから切り離した仮想の並列処理アーキテクチャ及び命令セットを提供する。【解決手段】仮想アーキテクチャは、異なる仮想スレッド間で複数レベルのデータ共有及び調整（例えば、同期）を有する複数仮想スレッドの同時実行をサポートする仮想プロセッサ、並びに仮想プロセッサを制御する仮想実行ドライバを定義する。仮想プロセッサの仮想命令セット・アーキテクチャは、仮想スレッドの振る舞いを定義するために使用され、並列スレッド振る舞い、例えばデータ共有及び同期に関する命令を含む。仮想プラットフォームを使用して、プログラマは、仮想スレッドが同時に実行してデータを処理するアプリケーション・プログラムを開発できる。仮想のトランスレータ及びドライバは、アプリケーション・コードをプログラマから透過的にアプリケーション・コードが実行される特定のハードウェアに適応させる。【選択図】図３
2008276740.tif 000002
【特許請求の範囲】
【請求項１】
並列処理動作を定義する方法であって、
協調的仮想スレッド・アレイにおける複数の仮想スレッドの各々について行われる動作シーケンスを定義する第１のプログラム・コードを提供するステップと、
前記複数の仮想スレッドの代表的仮想スレッドについて実行されるスレッド単位命令シーケンスを定義する仮想スレッド・プログラムへ前記第１のプログラム・コードをコンパイルし、前記スレッド単位命令シーケンスが、前記代表的仮想スレッドと前記複数の仮想スレッドの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含むステップと、
前記仮想スレッド・プログラムを記憶するステップと
を備える方法。
【請求項２】
前記記憶された仮想スレッド・プログラムを、目標プラットフォーム・アーキテクチャに合致する命令シーケンスへ翻訳するステップ
を備える、請求項１に記載の方法。
【請求項３】
入力データセットを処理して出力データセットを生成するように適応させられた協調的仮想スレッドのアレイを定義する第２のプログラム・コードを提供し、前記アレイ内の各仮想スレッドが前記仮想スレッド・プログラムを同時に実行するステップと、
前記第２のプログラム・コードを仮想関数ライブラリ内の関数呼び出しシーケンスへ変換し、前記ライブラリが前記協調的仮想スレッドのアレイを初期化及び実行させる仮想関数を含むステップと、
前記関数呼び出しシーケンスを記憶するステップと
を備える、請求項１に記載の方法。
【請求項４】
前記記憶された仮想スレッド・プログラム及び前記関数呼び出しシーケンスを、目標プラットフォーム・アーキテクチャ上で実行可能なプログラム・コードへ翻訳し、前記実行可能プログラム・コードが、前記協調的仮想スレッドのアレイを実行する１つ又は複数のプラットフォーム・スレッドを定義するステップ
を備える、請求項３に記載の方法。
【請求項５】
前記目標プラットフォーム・アーキテクチャに合致するコンピュータ・システム上で前記実行可能プログラム・コードを実行して前記出力データセットを生成するステップと、
前記出力データセットを記憶メディア上に記憶するステップと
を備える、請求項４に記載の方法。
【請求項６】
前記スレッド単位命令シーケンスが、前記１つ又は複数の他の仮想スレッドが前記シーケンス内の特定点に達する時間まで、前記代表的仮想スレッドの動作の実行を前記特定点で一時停止する命令を含む、請求項１に記載の方法。
【請求項７】
前記スレッド単位命令シーケンスが、前記１つ又は複数の他の仮想スレッドがアクセスを有する共有メモリ内に前記代表的仮想スレッドがデータを記憶する命令を含む、請求項１に記載の方法。
【請求項８】
前記スレッド単位命令シーケンスが、前記１つ又は複数の他の仮想スレッドがアクセスを有する共有メモリ内に記憶されたデータを前記代表的仮想スレッドがアトミックに読み出し及び更新する命令を含む、請求項１に記載の方法。
【請求項９】
前記仮想スレッド・プログラムが、複数の仮想状態空間の１つで変数を定義する変数定義ステートメントを含み、前記複数の仮想状態空間の異なるものが前記仮想スレッド間のデータ共有の異なるモードに対応する、請求項１に記載の方法。
【請求項１０】
前記データ共有のモードが、スレッド単位非共有モード及びグローバル共有モードを含む、請求項９に記載の方法。
【請求項１１】
前記データ共有のモードが、スレッド単位非共有モード、１つの仮想スレッド・アレイ内の共有モード、及びグローバル共有モードを含む、請求項９に記載の方法。
【請求項１２】
前記データ共有のモードが、スレッド単位非共有モード、１つの仮想スレッド・アレイ内の共有モード、複数の仮想スレッド・アレイ間の共有モード、及びグローバル共有モードを含む、請求項９に記載の方法。
【請求項１３】
目標プロセッサを動作させる方法であって、
入力データセットを処理して出力データセットを生成するように適応させられた仮想スレッド・アレイにおける複数の仮想スレッドの各々について行われる動作シーケンスを定義する第１の部分を含む入力プログラム・コードを提供するステップと、
前記入力プログラム・コードが、更に、前記仮想スレッド・アレイの次元を定義する第２の部分を含むステップと、
前記複数の仮想スレッドの代表的仮想スレッドについて実行されるスレッド単位命令シーケンスを定義する仮想スレッド・プログラムへ前記入力プログラム・コードの前記第１の部分をコンパイルし、前記スレッド単位命令シーケンスが、前記代表的仮想スレッドと前記複数の仮想スレッドの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含むステップと、
前記入力プログラム・コードの前記第２の部分を、仮想関数ライブラリへの関数呼び出しシーケンスへ変換し、前記ライブラリが、前記協調的仮想スレッドのアレイを初期化及び実行させる仮想関数を含むステップと、
前記仮想スレッド・プログラム及び前記関数呼び出しシーケンスを目標プラットフォーム・アーキテクチャ上で実行可能なプログラム・コードへ翻訳し、前記実行可能なプログラム・コードが、前記協調的仮想スレッドのアレイを実行する１つ又は複数の現実スレッドを定義するステップと、
前記目標プラットフォーム・アーキテクチャに合致するコンピュータ・システム上で前記実行可能プログラム・コードを実行して前記出力データセットを生成するステップと、
前記出力データセットを記憶メディアに記憶するステップと
を備える方法。
【請求項１４】
前記入力プログラム・コードの前記第２の部分が、前記仮想スレッド・アレイのために複数の次元を定義するプログラム・コードを含む、請求項１３に記載の方法。
【請求項１５】
前記入力プログラム・コードの前記第２の部分が、更に、
仮想スレッド・アレイより成るグリッドの１つ又は複数の次元を定義する関数呼び出しを含み、前記グリッド内の各アレイが実行される、
請求項１４に記載の方法。
【請求項１６】
前記目標プラットフォーム・アーキテクチャがマスタ・プロセッサ及びコプロセッサを含み、前記翻訳する行為が、
前記コプロセッサ上で定義された複数のスレッドによって並列に実行可能なプログラム・コードへ前記仮想スレッド・プログラムを翻訳するステップと、
前記コプロセッサのためにドライバ・プログラムへの呼び出しシーケンスへ前記関数呼び出しシーケンスを翻訳し、前記ドライバ・プログラムが前記マスタ・プロセッサ上で実行するステップと
を含む、請求項１３に記載の方法。
【請求項１７】
前記目標プラットフォーム・アーキテクチャが中央処理装置（ＣＰＵ）を含み、前記翻訳する行為が、
前記仮想スレッド・プログラム及び前記関数呼び出しシーケンスの少なくとも一部分を、前記仮想スレッドの数よりも少ない数のＣＰＵスレッドを使用して前記仮想スレッド・アレイを実行する目標プログラム・コードへ翻訳するステップ
を含む、請求項１３に記載の方法。
【請求項１８】
目標プロセッサを動作させる方法であって、
入力データセットを処理して出力データセットを生成するように適応させられた仮想スレッド・アレイにおける複数の仮想スレッドの代表的仮想スレッドについて実行されるスレッド単位命令シーケンスを定義する仮想スレッド・プログラムを取得するステップと、
前記スレッド単位命令シーケンスが、前記代表的仮想スレッドと前記複数の仮想スレッドの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含むステップと、
前記仮想スレッド・アレイの次元を定義する追加のプログラム・コードを取得するステップと、
前記仮想スレッド・プログラム及び前記追加のプログラム・コードを、前記目標プラットフォーム・アーキテクチャ上で実行可能なプログラム・コードへ翻訳し、前記実行可能なプログラム・コードが、前記仮想スレッド・アレイを実行する１つ又は複数のプラットフォーム・スレッドを定義するステップと、
前記目標プラットフォーム・アーキテクチャに合致するコンピュータ・システム上で前記実行可能なプログラム・コードを実行して前記出力データセットを生成し、前記出力データセットをメモリに記憶するステップと
を備える方法。
【請求項１９】
前記仮想スレッド・プログラムを取得する前記行為が、
高級プログラミング言語で書かれたソース・プログラム・コードを取得するステップと、
前記ソース・プログラム・コードをコンパイルして前記仮想スレッド・プログラムを生成するステップと
を含む、請求項１８に記載の方法。
【請求項２０】
前記仮想スレッド・プログラムを取得する前記行為が、
前記仮想スレッド・プログラムを記憶メディアから読み出すステップ
を含む、請求項１８に記載の方法。
【請求項２１】
前記仮想スレッド・プログラムを取得する前記行為が、
ネットワークを介して前記仮想スレッド・プログラムをリモート・コンピュータ・システムから受け取るステップ
を含む、請求項１８に記載の方法。
【発明の詳細な説明】
【発明の背景】
【０００１】
[0001]本発明は一般的には並列処理に関し、具体的には、並列スレッド・コンピューティングのための仮想アーキテクチャ及び命令セットに関する。
【０００２】
[0002]並列処理において、複数の処理装置（例えば、複数のプロセッサ・チップ又は単一チップ内の複数の処理コア）が同時に動作してデータを処理する。そのようなシステムは、複数部分への分解に適した問題を解決するために使用される。１つの例は画像フィルタリングである。この場合、１つの出力画像（又は複数の出力画像）の各画素は、１つの入力画像（又は複数の入力画像）の或る数の画素から計算される。各々の出力画素の計算は、一般的に全ての他の出力画素計算から独立しているので、異なる処理装置は異なる出力画素を並列に計算することができる。他の多くの問題も並列分解が容易である。一般的に、Ｎ個の路による並列実行は、そのような問題解決を、おおまかにＮの因子だけ高速にする。
【０００３】
[0003]他の種の問題も、並列実行スレッドを相互に調整できれば、容易に並列処理することができる。１つの例は高速フーリエ変換（ＦＦＴ）である。ＦＦＴは再帰的アルゴリズムであって、各々の段階で、前の段階の出力に計算が行われて新しい値が生成され、この新しい値は出力段階に到達するまで次の段階の入力として使用される。単一の実行スレッドは、前の段階から信頼できる出力データを確実に取得できるかぎり、複数段階行うことができる。もしタスクを複数のスレッドへ分割するのであれば、或る一定の調整機構を提供して、例えば、まだ書き込まれていない入力データをスレッドが読み出さないようにしなければならない。（この問題の１つの解決法は、２００５年１２月１５日に出願された同一出願人による同時係属米国特許出願第１１／３０３，７８０号で説明されている。）
【０００４】
[0004]しかし、並列処理システムのプログラミングは難しい。プログラマは、通常、処理ユニットが実際に実行できるコードを作り出すため、利用可能な処理装置の数及び能力（命令セット、データ・レジスタの数、相互接続など）を知っていなければならない。機械特有コンパイラは、この分野で相当の援助を提供できるが、異なるプロセッサへコードを移植する度に、コードを再コンパイルすることが依然として必要である。
【０００５】
[0005]更に、並列処理アーキテクチャの様々な様相が急速に発展している。例えば、新しいプラットフォーム・アーキテクチャ、命令セット、及びプログラミング・モデルが継続的に開発されている。並列アーキテクチャの様々な様相（例えば、プログラミング・モデル又は命令セット）は１つの世代から次の世代へと変化するので、それに従ってアプリケーション・プログラム、ソフトウェア・ライブラリ、コンパイラ、並びに他のソフトウェア及びツールも変化しなければならない。この非定常性は、並列処理コードの開発及び維持へ相当のオーバーヘッドを付加する。
【０００６】
[0006]スレッド間の調整が必要とされるとき、並列プログラミングは一層難しくなる。プログラマは、特定のプロセッサ又はコンピュータ・システムの中で、どのような機構がスレッド間通信をサポート（又はエミュレート）するために利用可能であるかを決定し、利用可能な機構を有効に使うコードを書かなければならない。異なるコンピュータ・システムでは利用可能及び／又は最適メカニズムは、一般的に異なることから、この種の並列コードは一般的に移植することができず、並列コードが実行される各々のハードウェア・プラットフォーム毎、コードを書き直さなければならない。
【０００７】
[0007]更に、プロセッサの実行可能なコードを提供することに加えて、プログラマは、更に、「マスタ」プロセッサの制御コードを提供しなければならない。制御コードは様々な処理装置の動作を調整し、例えば、どのようなプログラムを実行すべきか、どのような入力データを処理すべきかを各々の処理装置に命令する。そのような制御コードは、通常、特定のマスタ・プロセッサ及びプロセッサ間通信プロトコルに対して特有であり、もし異なるマスタ・プロセッサが代用されるのであれば、通常、書き直さなれければならない。
【０００８】
[0008]並列処理コードのコンパイル及び再コンパイルの困難性は、コンピューティング・テクノロジの発展と共にユーザがシステムをアップグレードしようとする意欲を低下させる。したがって、コンパイルされた並列処理コードを特定のハードウェア・プラットフォームから切り離して、目標とする並列アプリケーション及びツールのために安定した並列処理アーキテクチャ及び命令セットを提供することが望ましい。
【発明の概要】
【０００９】
[0009]本発明の実施形態は、並列スレッド・コンピューティングの仮想アーキテクチャ及び仮想命令セットを提供する。仮想並列アーキテクチャは、異なる仮想スレッド間で複数レベルのデータ共有及び調整（例えば、同期）を有する複数の仮想スレッドの同時実行をサポートする仮想プロセッサ、並びに仮想プロセッサを制御する仮想実行ドライバを定義する。仮想プロセッサの仮想命令セット・アーキテクチャは、仮想スレッドの振る舞いを定義するために使用され、並列スレッド振る舞い、例えば、データ共有及び同期に関系する命令を含む。仮想並列プラットフォームを使用して、プログラマは、仮想スレッドが同時に実行してデータを処理するアプリケーション・プログラムを開発することができる。アプリケーション・プログラムは、高度に移植可能な中間形態で、例えば、仮想並列プラットフォームを目標にしたプログラム・コードとして記憶及び配布される。導入時又は実行時に、ハードウェア特有仮想命令トランスレータ（ｔｒａｎｓｌａｔｏｒ）及び実行ドライバは、中間形態アプリケーション・コードを、このアプリケーション・コードが実行される特定のハードウェアへ適応させる。結果として、アプリケーション・プログラムは、一層移植可能となり、開発が容易になる。なぜなら、開発プロセスは特定の処理ハードウェアから独立しているからである。
【００１０】
[0010]本発明の１つの様相によれば、並列処理動作を定義する方法は、協調的仮想スレッドから成るアレイ内の多数の仮想スレッドの各々について実行される動作シーケンスを定義する第１のプログラム・コードを提供することを含む。第１のプログラム・コードは、アレイの代表的仮想スレッドについて実行されるスレッド単位命令のシーケンスを定義する仮想スレッド・プログラムへコンパイルされ、スレッド単位命令のシーケンスは、代表的仮想スレッドとアレイの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含む。仮想スレッド・プログラムは記憶され（例えば、メモリ又はディスクに）、後で目標プラットフォーム・アーキテクチャに合致する命令のシーケンスへ翻訳可能である。
【００１１】
[0011]更に、入力データセットを処理して出力データセットを生成するように適応させられた協調的仮想スレッドのアレイを定義ために、第２のプログラム・コードを提供することが可能である。アレイ内の各仮想スレッドは仮想スレッド・プログラムを同時に実行する。第２のプログラム・コードは、有利には、仮想関数ライブラリの関数呼び出しシーケンスへ変換される。ライブラリは、協調的仮想スレッドのアレイを初期化及び実行させる仮想関数を含む。この関数呼び出しシーケンスも記憶可能である。記憶された仮想スレッド・プログラム及び関数呼び出しシーケンスは、目標プラットフォーム・アーキテクチャの上で実行可能なプログラム・コードへ翻訳可能である。実行可能プログラム・コードは、協調的仮想スレッドのアレイを実行する１つ又は複数のプラットフォーム・スレッドを定義する。実行可能なプログラム・コードは目標プラットフォーム・アーキテクチャに合致したコンピュータ・システムの上で実行することができ、記憶メディア（例えば、コンピュータ・メモリ、ディスクなど）に記憶可能な出力データセットを生成することができる。
【００１２】
[0012]前述したように、仮想スレッド・プログラム・コード内のスレッド単位命令シーケンスは、有利には、代表的仮想スレッドとアレイの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含む。例えば、スレッド単位命令シーケンスは、１つ又は複数の他の仮想スレッドがシーケンス内の特定の点に達するまで、この特定の点における代表的仮想スレッドの動作の実行を一時停止する命令、１つ又は複数の他の仮想スレッドがアクセスを有する共有メモリの中に代表的仮想スレッドがデータを記憶する命令、１つ又は複数の他の仮想スレッドがアクセスを有する共有メモリの中に記憶されたデータを代表的仮想スレッドがアトミックに読み出し及び更新する命令などを含んでもよい。
【００１３】
[0013]仮想スレッド・プログラムは、更に、多数の仮想状態空間の１つで変数を定義する変数定義ステートメントを含んでもよい。異なる仮想状態空間は、仮想スレッド間のデータ共有の異なるモードに対応する。１つの実施形態において、少なくともスレッド単位非共有モード及びグローバル共有モードがサポートされる。他の実施形態では、追加モード、例えば、仮想スレッドの１つのアレイ内の共有モード、及び／又は仮想スレッドの複数のアレイ間の共有モードもサポートされてもよい。
【００１４】
[0014]本発明の他の様相によれば、目標プロセッサを動作させる方法は、入力プログラム・コードを提供することを含む。入力プログラム・コードは第１の部分及び第２の部分を含む。第１の部分は、入力データセットを処理して出力データセットを生成するように適応させられた仮想スレッドの１つのアレイにおける多数の仮想スレッドの各々について実行される動作シーケンスを定義し、第２の部分は上記仮想スレッドのアレイの次元を定義する。入力プログラム・コードの第１の部分は、アレイの代表的仮想スレッドのために実行されるスレッド単位命令のシーケンスを定義する仮想スレッド・プログラムへコンパイルされる。スレッド単位命令シーケンスは、代表的仮想スレッドとアレイの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含む。入力プログラム・コードの第２の部分は、仮想関数ライブラリへの関数呼び出しシーケンスへ変換される。ライブラリは、協調的仮想スレッドのアレイを初期化して実行させる仮想関数を含む。仮想スレッド・プログラム及び関数呼び出しシーケンスは、目標プラットフォーム・アーキテクチャの上で実行可能なプログラム・コードへ翻訳される。実行可能なプログラム・コードは、協調的仮想スレッドのアレイを実行する１つ又は複数の現実スレッドを定義する。実行可能なプログラム・コードは、目標プラットフォーム・アーキテクチャに合致するコンピュータ・システムの上で実行され、記憶メディアに記憶可能な出力データセットを生成する。
【００１５】
[0015]幾つかの実施形態において、仮想スレッドのアレイは、２つ以上の次元で定義可能である。更に、入力プログラム・コードの第２の部分も、仮想スレッドのアレイのグリッドの１つ又は複数の次元を定義する関数呼び出しを含んでもよく、グリッド内の各々のアレイが実行される。
【００１６】
[0016]任意の目標プラットフォーム・アーキテクチャが使用されてもよい。幾つかの実施形態において、目標プラットフォーム・アーキテクチャは、マスタ・プロセッサ及びコプロセッサを含む。翻訳中に、仮想スレッド・プログラムは、コプロセッサ上で定義された多数のスレッドによって並列に実行可能なプログラム・コードへ翻訳可能であり、関数呼び出しシーケンスは、マスタ・プロセッサ上で実行するコプロセッサのためにドライバ・プログラムへの呼び出しシーケンスへ翻訳される。他の実施形態において、目標プラットフォーム・アーキテクチャは中央処理装置（ＣＰＵ）を含む。翻訳中に、仮想スレッド・プログラム及び関数呼び出しシーケンスの少なくとも一部分は、仮想スレッドの数よりも少ない或る数のＣＰＵスレッドを使用して仮想スレッド・アレイを実行する目標プログラム・コードへ翻訳される。
【００１７】
[0017]本発明の更に他の実施形態によれば、目標プロセッサを動作させる方法は、入力データセットを処理して出力データセットを生成するように適応させられた仮想スレッド・アレイにおける多数の仮想スレッドの代表的仮想スレッドについて実行されるスレッド単位命令シーケンスを定義する仮想スレッド・プログラムを取得することを含む。スレッド単位命令シーケンスは、代表的仮想スレッドとアレイの１つ又は複数の他の仮想スレッドとの間の協調的振る舞いを定義する少なくとも１つの命令を含む。仮想スレッド・アレイの次元を定義する追加のプログラム・コードも取得される。仮想スレッド・プログラム及び追加のプログラム・コードは、目標プラットフォーム・アーキテクチャの上で実行可能なプログラム・コードへ翻訳され、実行可能なプログラム・コードは、仮想スレッド・アレイを実行する１つ又は複数のプラットフォーム・スレッドを定義する。実行可能なプログラム・コードは、目標プラットフォーム・アーキテクチャに合致したコンピュータ・システム上で実行され、出力データセットを生成して、出力データセットをメモリ内に記憶する。
【００１８】
[0018]幾つかの実施形態において、仮想スレッド・プログラムは、高級プログラミング言語で書かれたソース・プログラム・コードを受け取り、コンパイルして仮想スレッド・プログラムを生成することによって取得されてもよい。代替として、仮想スレッド・プログラムは、記憶メディアから読み出されるか、ネットワークを介してリモート・コンピュータ・システムから受け取られてもよい。読み出され又は受け取られる仮想スレッド・コードは、事前に高級言語からコンパイルされているか、仮想命令セット・アーキテクチャに合致するコードとして直接作成されていることを理解すべきである。
【００１９】
[0019]下記の詳細な説明は、添付の図面と共に、本発明の性質及び利点の一層良好な理解を提供する。
【発明の詳細な説明】
【００２０】
[0030]本発明の実施形態は、並列スレッド・コンピューティングのための仮想アーキテクチャ及び命令セットを提供する。仮想アーキテクチャは、異なるスレッド間で複数レベルのデータ共有及び調整（例えば、同期）を有する複数スレッドの同時実行をサポートするプロセッサのモデル、及びモデル・プロセッサを制御する仮想実行ドライバを提供する。処理スレッドの振る舞いを定義するために使用される仮想命令セットは、並列スレッド振る舞いに関する命令、例えば、或るスレッド間でデータの共有を許す命令、及び異なるスレッドがプログラム内の或るプログラマ特定点で同期することを要求する命令を含む。仮想プラットフォームを使用して、プログラマは、データを処理するために同時及び協調的スレッドが実行されるアプリケーション・プログラムを開発することができる。ハードウェア特有仮想命令トランスレータ及び実行ドライバは、アプリケーション・コードが実行される特定のハードウェアへアプリケーション・コードを適応させる。結果として、アプリケーション・プログラムは移植が一層可能となり、開発が容易になる。なぜなら、開発プロセスは特定の処理ハードウェアから独立しているからである。
【００２１】
１．システムの概観
[0031]図１は、本発明の実施形態に従ったコンピュータ・システム１００のブロック図である。コンピュータ・システム１００は、メモリ・ブリッジ１０５を含むバス経路を介して通信する中央処理装置（ＣＰＵ）１０２及びシステム・メモリ１０４を含む。例えば、ノースブリッジ・チップであってもよいメモリ・ブリッジ１０５は、バス又は他の通信経路１０６（例えば、ＨｙｐｅｒＴｒａｎｓｐｏｒｔリンク）を介してＩ／Ｏ（入力／出力）ブリッジ１０７へ接続される。例えば、サウスブリッジ・チップであってもよいＩ／Ｏブリッジ１０７は、ユーザ入力を１つ又は複数のユーザ入力デバイス１０８（例えば、キーボード、マウス）から受け取り、バス１０６及びメモリ・ブリッジ１０５を介して入力をＣＰＵ１０２へ回送する。並列処理サブシステム１１２は、バス又は他の通信経路１１３（例えば、ＰＣＩ  Ｅｘｐｒｅｓｓ又はＡｃｃｅｌｅｒａｔｅｄ  Ｇｒａｐｈｉｃｓ  Ｐｏｒｔリンク）を介してメモリ・ブリッジ１０５へ結合される。１つの実施形態において、並列処理サブシステム１１２は、画素をディスプレイ・デバイス１１０（例えば、通常のＣＲＴ又はＬＣＤベースのモニタ）へ引き渡すグラフィックス・サブシステムである。システム・ディスク１１４もＩ／Ｏブリッジ１０７へ接続される。スイッチ１１６は、Ｉ／Ｏブリッジ１０７と、他のコンポーネント、例えば、ネットワーク・アダプタ１１８及び様々なアドイン・カード１２０及び１２１との間の接続を提供する。ＵＳＢ又は他のポート接続、ＣＤドライブ、ＤＶＤドライブなどを含む他のコンポーネント（明示的には示されない）も、Ｉ／Ｏブリッジ１０７へ接続されてもよい。図１の様々なコンポーネントを相互接続する通信経路は、任意の適切なプロトコル、例えば、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）、ＰＣＩ  Ｅｘｐｒｅｓｓ（ＰＣＩ−Ｅ）、ＡＧＰ（Ａｃｃｅｌｅｒａｔｅｄ  Ｇｒａｐｈｉｃｓ  Ｐｏｒｔ）、ＨｙｐｅｒＴｒａｎｓｐｏｒｔ、又は任意の他のバス又はポイントツーポイント通信プロトコルを使用して実現されてもよく、異なるデバイス間の接続は、当技術分野で公知の異なるプロトコルを使用してもよい。
【００２２】
[0032]並列処理サブシステム１１２は、並列処理装置（ＰＰＵ）１２２及び並列処理（ＰＰ）メモリ１２４を含む。これらは、例えば、１つ又は複数の集積回路デバイス、例えば、プログラム可能プロセッサ、アプリケーション特有集積回路（ＡＳＩＣ）、及びメモリ・デバイスを使用して実現されてもよい。ＰＰＵ１２２は、有利には、１つ又は複数の処理コアを含む高度並列プロセッサを実現する。処理コアの各々は、多数の（例えば、数百の）スレッドを同時に実行することができる。ＰＰＵ１２２は多種の計算を行うようにプログラム可能である。そのような計算の中には、線形及び非線形データ変換、ビデオ及び／又はオーディオ・データのフィルタリング、モデリング（例えば、物理法則を適用して物体の位置、速度、及び他の属性を決定すること）、画像のレンダリングなどが含まれる。ＰＰＵ１２２は、システム・メモリ１０４及び／又はＰＰメモリ１２４から内部メモリへデータを転送し、データを処理し、結果のデータをシステム・メモリ１０４及び／又はＰＰメモリ１２４へ返してもよい。そのようなデータは、例えば、ＣＰＵ１０２を含む他のシステム・コンポーネントからアクセス可能である。幾つかの実施形態において、ＰＰＵ１２２はグラフィックス・プロセッサであり、メモリ・ブリッジ１０５及びバス１１３を介してＣＰＵ１０２及び／又はシステム・メモリ１０４によって供給されたグラフィックス・データから画素データを生成すること、ＰＰメモリ１２４（このメモリは、例えば、従来のフレーム・バッファを含むグラフィックス・メモリとして使用可能である）と交信して画素データを記憶及び更新すること、画素データをディスプレイ１１０へ引き渡すことなどに関する様々なタスクを行うように構成可能である。幾つかの実施形態において、ＰＰサブシステム１１２は、グラフィックス・プロセッサとして動作する１つのＰＰＵ１２２及び汎用計算に使用される別のＰＰＵ１２２を含んでもよい。ＰＰＵは同格のもの又は異なるものであってもよく、各々のＰＰＵは自分自身の専用ＰＰメモリ・デバイスを有してもよい。
【００２３】
[0033]ＣＰＵ１０２はシステム１００のマスタ・プロセッサとして動作し、他のシステム・コンポーネントの動作を制御及び調整する。具体的には、ＣＰＵ１０２は、ＰＰＵ１２２の動作を制御するコマンドを出す。幾つかの実施形態において、ＣＰＵ１０２はＰＰＵ１２２のためにコマンドのストリームをコマンド・バッファへ書き込む。コマンド・バッファは、システム・メモリ１０４、ＰＰメモリ１２４、又はＣＰＵ１０２及びＰＰＵ１２２の両者からアクセスできる他の記憶場所にあってもよい。ＰＰＵ１２２はコマンド・バッファからコマンド・ストリームを読み出し、ＣＰＵ１０２の動作とは同期しないでコマンドを実行する。
【００２４】
[0034]本明細書で示されるシステムは例示であって、変形及び修正が可能であることが理解される。ブリッジの数及び配列を含む接続トポロジは、所望のように修正されてもよい。例えば、幾つかの実施形態において、システム・メモリ１０４はブリッジを介することなくＣＰＵ１０２へ直接接続され、他のデバイスはメモリ・ブリッジ１０５及びＣＰＵ１０２を介してシステム・メモリ１０４と通信する。他の代替のトポロジにおいて、ＰＰサブシステム１１２はメモリ・ブリッジ１０５ではなくＩ／Ｏブリッジ１０７へ接続される。更に他の実施形態において、Ｉ／Ｏブリッジ１０７及びメモリ・ブリッジ１０５は単一のチップへ集積されてもよい。本明細書で示された特定のコンポーネントは自由に選択でき、例えば、任意の数のアドイン・カード又は周辺デバイスがサポートされてもよい。幾つかの実施形態において、スイッチ１１６は削除され、ネットワーク・アダプタ１１８並びにアドイン・カード１２０及び１２１がＩ／Ｏブリッジ１０７へ直接接続する。
【００２５】
[0035]ＰＰＵ１２２からシステム１００の残部への接続も変更されてもよい。幾つかの実施形態において、ＰＰシステム１１２は、システム１００の拡張スロットへ挿入されるアドイン・カードとして実現される。他の実施形態において、ＰＰＵは、バス・ブリッジ、例えば、メモリ・ブリッジ１０５又はＩ／Ｏブリッジ１０７と一緒に、単一チップの上に集積可能である。更に他の実施形態において、ＰＰＵ１２２の幾つか又は全部の要素がＣＰＵ１０２と一緒に集積されてもよい。
【００２６】
[0036]ＰＰＵは、ローカルメモリを含まないで、任意の量のローカルＰＰメモリを設けられてもよく、ローカルメモリ及びシステム・メモリを任意の組み合わせで使用してもよい。例えば、ＰＰＵ１２２は、一体化メモリ・アーキテクチャ（ＵＭＡ）実施形態としてグラフィックス・プロセッサであってもよい。そのような実施形態では、専用グラフィックス・メモリは殆ど又は全く設けられず、ＰＰＵ１２２はシステム・メモリを排他的又は殆ど排他的に使用する。ＵＭＡ実施形態において、ＰＰＵはブリッジ・チップの中に集積されるか、離散的チップとして提供されて、高速リンク（例えば、ＰＣＩ−Ｅ）がＰＰＵをブリッジ・チップ及びシステム・メモリへ接続する。
【００２７】
[0037]更に理解すべきは、任意の数のＰＰＵをシステム内に含めることができることである。それは、例えば、複数のＰＰＵを単一のアドイン・カードに含め、複数のアドイン・カードを経路１１３へ接続し、及び／又は１つ又は複数のＰＰＵをシステム・マザーボードへ直接接続することによって行う。複数のＰＰＵは並列に動作可能であり、単一のＰＰＵよりも高いスループットでデータを処理する。
【００２８】
[0038]当業者は、更に、ＣＰＵ及びＰＰＵが単一のデバイスへ集積され得ること、ＣＰＵ及びＰＰＵが様々なリソース、例えば、命令論理、バッファ、キャッシュ、メモリ、処理エンジンなどを共有可能なこと、又は別々のリソースを並列処理及び他の動作のために設けてもよいことを認識する。したがって、本明細書の中でＰＰＵと関連づけて説明される回路及び／又は機能の任意のもの及び全部が、適切に装備されたＣＰＵの中で実現されてもよく、そのようなＣＰＵによって達成されてもよい。
【００２９】
[0039]ＰＰＵを組み込んだシステムは、デスクトップ、ラップトップ、又は携帯用・パーソナル・コンピュータ、サーバ、ワークステーション、ゲームコンソール、組み込みシステムなどを含む多様な構成及び形態因子の中で実現されてもよい。
【００３０】
[0040]更に、本発明の１つの利点として、特定のコンピューティング・ハードウェアからの独立性が増加することを当業者は理解する。したがって、本発明の実施形態は、ＰＰＵを設けないシステムを含む任意のコンピュータ・システムを使用して、実施されてもよいことを理解すべきである。
【００３１】
２．仮想プログラミング・モデルの概観
[0041]本発明の実施形態において、コンピューティング・システムのＰＰＵ１２２又は他のプロセッサを使用して、スレッド・アレイを使用する汎用計算を実行することが望ましい。本明細書で使用されるように、「スレッド・アレイ」とは、入力データセット上で同じプログラムを同時に実行して出力データセットを生成する多数の（ｎ０個の）スレッドのグループである。スレッド・アレイ内の各スレッドは一意のスレッド識別子（スレッドＩＤ）を割り当てられる。スレッドＩＤは、スレッドの実行中にスレッドへアクセス可能である。スレッドＩＤは、１次元又は多次元の数値（例えば、０からｎ０−１）として定義可能であり、スレッドの処理振る舞いの様々な様相を制御する。例えば、スレッドＩＤは、入力データセットのどの部分をスレッドが処理すべきかを決定し、及び／又は出力データセットのどの部分をスレッドが作成又は書き込むべきかを決定するために使用される。
【００３２】
[0042]幾つかの実施形態において、スレッド・アレイは、「協調的」スレッド・アレイ又はＣＴＡである。他のタイプのスレッド・アレイと同じように、ＣＴＡは、入力データセット上で同じプログラム（本明細書では「ＣＴＡプログラム」と呼ばれる）を同時に実行して、出力データセットを作成する複数スレッドのグループである。ＣＴＡにおいて、スレッドは、スレッドＩＤに依存する仕方でデータを相互に共有することによって協力することができる。例えば、ＣＴＡにおいて、データは１つのスレッドによって作成され、他のスレッドによって消費されることが可能である。幾つかの実施形態において、消費するスレッドがデータへのアクセスを試みる前に、作成するスレッドによってデータが実際に作成されたことを保証するため、データが共有される地点で、同期命令がＣＴＡプログラム・コードの中に挿入されることが可能である。ＣＴＡスレッド間のデータ共有の範囲は、あるとすれば、ＣＴＡプログラムによって決定される。したがって、ＣＴＡを使用する特定のアプリケーションにおいて、ＣＴＡスレッドは、ＣＴＡプログラムに依存して、相互にデータを実際に共有しても共有しなくてもよく、「ＣＴＡ」及び「スレッド・アレイ」の用語は、本明細書では同じ意味で使用されることを理解すべきである。
【００３３】
[0043]幾つかの実施形態において、ＣＴＡ内のスレッドは、同じＣＴＡ内の他のスレッドと、入力データ及び／又は中間結果を共有する。例えば、ＣＴＡプログラムは、特定のデータが書き込まれる共有メモリ内のスレッドＩＤの関数であるアドレスを計算する命令を含んでもよい。各々のスレッドは自分自身のスレッドＩＤを使用して関数を計算し、対応する場所へ書き込む。アドレス関数は、有利には、異なるスレッドが、異なる場所に書き込むように定義される。関数が決定論的である限り、スレッドによって書き込まれる場所は予測可能である。ＣＴＡプログラムは、更に、データが読み出される共有メモリ内のスレッドＩＤの関数であるアドレスを計算する命令を含むことができる。適切な関数を定義し、同期手法を提供することによって、データはＣＴＡの１つのスレッドによって共有メモリ内の所与の場所へ書き込まれ、同じＣＴＡの異なるスレッドによって、予測可能な仕方で上記所与の場所から読み出されることが可能である。その結果、スレッド間データ共有の所望のパターンがサポートされ、ＣＴＡ内の任意のスレッドが同一ＣＴＡ内の他のスレッドとデータを共有することができる。
【００３４】
[0044]ＣＴＡ（又は他のタイプのスレッド・アレイ）は、有利には、データ並列分解に適した計算を行うために使用される。本明細書で使用されるように、「データ並列分解」とは、入力データ上で同じアルゴリズムを並列に複数回実行して出力データを生成することによって、計算問題が解決される任意の場合を含む。例えば、データ並列分解の１つの例は、入力データセットの異なる部分へ同じ処理アルゴリズムを適用して出力データセットの異なる部分を生成することを引き起こす。データ並列分解に適した問題の例は、行列環、任意数の次元における線形及び／又は非線形変換（例えば、高速フーリエ変換）、及び様々なフィルタリング・アルゴリズムを含む。フィルタリング・アルゴリズムには、任意数の次元における畳み込みフィルタ、複数次元における分離フィルタなどが含まれる。入力データセットの各部分に適用される処理アルゴリズムは、ＣＴＡプログラム中で特定され、ＣＴＡ内の各スレッドは、入力データセットの一部分の上で同じＣＴＡプログラムを実行する。ＣＴＡプログラムは、広範囲の数学及び論理演算を使用してアルゴリズムを実現することができ、プログラムは条件付き又は分岐実行経路、及び直接及び／又は間接メモリ・アクセスを含むことができる。
【００３５】
[0045]ＣＴＡ、及びＣＴＡの実行は、前述した出願第１１／３０３，７８０号に詳細で説明される。
【００３６】
[0046]幾つかの場合において、関係のあるＣＴＡ（より一般的には、スレッド・アレイ）の「グリッド」を定義することが有用である。本明細書で使用されるように、ＣＴＡの「グリッド」とは或る数の（ｎ１個の）ＣＴＡの集まりである。集まりの中の全ＣＴＡは同じサイズ（即ち、スレッド数）であり、同じＣＴＡプログラムを実行する。グリッド内のｎ１個のＣＴＡは、有利には、相互に独立である。これは、グリッド内のＣＴＡ実行が、グリッド内の他のＣＴＡ実行によって影響されないことを意味する。明らかなように、この特徴は、利用可能な処理コア間にＣＴＡを配分するとき著しい柔軟性を提供する。
【００３７】
[0047]グリッド内の異なるＣＴＡを区別するため、「ＣＴＡ識別子」（又はＣＴＡ  ＩＤ）が、有利には、グリッドの各ＣＴＡへ割り当てられる。スレッドＩＤのように、任意の一意の識別子（非限定的に、数値識別子を含む）をＣＴＡ  ＩＤとして使用することができる。１つの実施形態において、ＣＴＡ  ＩＤは、０からｎ１−１までの単純に順次の（１次元の）索引値である。他の実施形態では、多次元索引スキームを使用することができる。ＣＴＡ  ＩＤはＣＴＡの全スレッドに共通であり、グリッド内の所与のＣＴＡスレッドは、例えば、入力データを読み出すソース場所及び／又は出力データを書き込むデスティネーション場所を決定するために、スレッドＩＤと一緒にＣＴＡ  ＩＤを使用できる。このようにして、同じグリッドの異なるＣＴＡ内のスレッドは、同じデータセットの上で同時に動作してもよい。もっとも、幾つかの実施形態において、グリッド内の異なるＣＴＡ間でデータを共有することはサポートされていない。
【００３８】
[0048]ＣＴＡのグリッドを定義することは有用である。例えば、複数のＣＴＡを使用して、単一の大きな問題の異なる部分を解くことが望まれる場合にそうである。例えば、フィルタリング・アルゴリズムを行って、高品位テレビ（ＨＤＴＶ）画像を生成することが望まれるかも知れない。当技術分野で知られるように、ＨＤＴＶ画像は２百万個を超える画素を含むことは可能である。もし各々のスレッドが１つの画素を生成するならば、実行されるスレッドの数は、単一のＣＴＡ内で処理可能なスレッド数を超過する（合理的なサイズ及びコストの処理プラットフォームが、通常の手法を使用して構築されると仮定する）。
【００３９】
[0049]この大きな処理タスクは、多数のＣＴＡ間で画像を分割することによって管理可能である。各々のＣＴＡは出力画素の異なる部分（例えば、１６×１６タイル）を生成する。全てのＣＴＡは同じプログラムを実行し、スレッドはＣＴＡ  ＩＤ及びスレッドＩＤの組み合わせを使用して、入力データを読み出す場所及び出力データを書き込む場所を決定し、各々のＣＴＡが入力データセットの正しい部分上で動作し、出力データセットの自己部分を正しい場所へ書き込む。
【００４０】
[0050]注意すべきことは、ＣＴＡ内の（データを共有できる）スレッドとは異なり、グリッド内のＣＴＡは、有利には、相互にデータを共有せず、又は相互に依存しないことである。即ち、同じグリッドの２つのＣＴＡは順次に（どのような順序でも）又は同時に実行可能であり、依然として同じ結果を作成することができる。その結果、処理プラットフォーム（例えば、図１のシステム１００）は、ＣＴＡのグリッドを実行して結果を取得することができる。この取得は、最初に１つのＣＴＡを実行し、続いて次のＣＴＡを実行し、以下同様にグリッドの全ＣＴＡを実行してしまうことによって行われる。代替として、もし十分なリソースが利用可能であれば、処理プラットフォームは同じグリッドを実行し、複数のＣＴＡを並列に実行することによって、同じ結果を取得することができる。
【００４１】
[0051]幾つかの場合、ＣＴＡの複数（ｎ２）のグリッドを定義することが望ましいかも知れない。この場合、各々のグリッドはデータ処理プログラム又はタスクの異なる部分を実行する。例えば、データ処理タスクは或る数の「解法ステップ」へ分割されてもよく、各々の解法ステップはＣＴＡのグリッドを実行することによって行われる。他の例として、データ処理タスクは、連続した入力データセット（例えば、ビデオデータの連続フレーム）の上で同一又は類似の動作を実行することを含んでもよい。ＣＴＡグリッドは各入力データセットについて実行可能である。仮想プログラミング・モデルは、有利には、少なくともこれら３レベルの作業定義（即ち、スレッド、ＣＴＡ、及びＣＴＡグリッド）をサポートする。もし望まれるならば、追加のレベルもサポートされてもよい。
【００４２】
[0052]特定の問題を解決するために使用されるＣＴＡサイズ（スレッドの数ｎ０）、グリッドサイズ（ＣＴＡの数ｎ１）、及びグリッド数（ｎ２）は、問題分解を定義するプログラマ又は自動化エージェントの問題及び選好パラメータに依存することが理解される。したがって、幾つかの実施形態において、ＣＴＡサイズ、グリッドサイズ、及びグリッド数は、有利には、プログラマによって定義される。
【００４３】
[0053]ＣＴＡアプローチから利益を得る問題は、通常、並列に処理可能な多数のデータ要素の存在によって特徴づけられる。幾つかの場合、データ要素は出力要素であり、出力要素の各々は、入力データセットの異なる（可能性として重複する）部分に同じアルゴリズムを行うことによって生成される。他の場合、データ要素は入力要素であり、入力要素の各々は同じアルゴリズムを使用して処理される。
【００４４】
[0054]そのような問題は、常に、少なくとも２つのレベルへ分解され、前述したスレッド、ＣＴＡ、及びグリッドへマップされる。例えば、各々のグリッドは、複雑なデータ処理タスクの中で１つの解法ステップの結果を表すことができる。各々のグリッドは、有利には、或る数の「ブロック」へ分割され、ブロックの各々は単一のＣＴＡとして処理可能である。各々のブロックは、有利には、複数の「要素」、即ち、解かれる問題の要素部分（例えば、単一の入力データ点又は単一の出力データ点）を含有する。ＣＴＡの中で、各々のスレッドは１つ又は複数の要素を処理する。
【００４５】
[0055]図２Ａ及び図２Ｂは、本発明の実施形態で使用される仮想プログラミング・モデルにおけるグリッド、ＣＴＡ、及びスレッド間の関係を図示する。図２Ａは或る数のグリッド２００を示し、各々のグリッドはＣＴＡ２０２の２次元（２Ｄ）アレイから作られる。（ここで、類似オブジェクトの複数のインスタンスは、オブジェクト識別する参照数字、及び必要な場合にはインスタンスを識別する括弧内の数字で表される。）ＣＴＡ２０２（０，０）について図２Ｂで示されるように、各々のＣＴＡ２０２はスレッド（Θ）２０４の２Ｄアレイを含む。各グリッド２００の各ＣＴＡ２０２内の各スレッド２０４について、形式Ｉ＝［ｉｇ，ｉｃ，ｉｉ］の一意識別子が定義される。ここで、グリッド識別子ｉｇはグリッドを一意に識別し、ＣＴＡ  ＩＤ  ｉｃはグリッド内のＣＴＡを一意に識別し、スレッドＩＤ  ｉｉはＣＴＡ内のスレッドを一意に識別する。この実施形態において、識別子Ｉは１次元グリッド識別子ｉｇ、２次元ＣＴＡ識別子ｉｃ、及び２次元スレッド識別子ｉｉから構築されることが可能である。他の実施形態において、一意の識別子Ｉは、０≦ｉｇ＜ｎ２；０≦ｉｃ＜ｎ１；及び０≦ｉｉ＜ｎ０の三つ組み整数である。更に、他の実施形態において、グリッド識別子、ＣＴＡ識別子、及びスレッド識別子の任意のもの又は全部が、１次元整数、２Ｄ座標対、３Ｄ三つ組みなどで表現されてもよい。一意のスレッド識別子Ｉは、例えば、１つのグリッド全体又は複数のグリッドについて入力データセットを包含するアレイ内で入力データのソース場所を決定するため、及び／又は１つのグリッド全体又は複数のグリッドについて出力データセットを包含するアレイ内で出力データを記憶する目標場所を決定するために使用されることが可能である。
【００４６】
[0056]例えば、ＨＤＴＶ画像の場合、各々のスレッド２０４は出力画像の画素に対応してもよい。ＣＴＡ２０２のサイズ（スレッド２０４の数）は、問題分解での選択事項であり、単一のＣＴＡ２０２におけるスレッド最大数の制約（これはプロセッサ・リソースの有限性を反映する）のみによって限定される。グリッド２００はＨＤＴＶデータのフレーム全体に対応可能であり、又は複数のグリッドが単一のフレームにマップされることができる。
【００４７】
[0057]幾つかの実施形態において、問題分解は均一である。これは、全てのグリッド２００が同じ数及び同じ配列のＣＴＡ２０２を有し、全てのＣＴＡ２０２が同じ数及び同じ配列のスレッド２０４を有することを意味する。他の実施形態において、分解は非均一であってもよい。例えば、異なるグリッドは、異なる数のＣＴＡを含んでもよく、異なるＣＴＡ（同じグリッド又は異なるグリッド内の）は、異なる数のスレッドを含んでもよい。
【００４８】
[0058]上記で定義されたＣＴＡは、数十又は数百の同時スレッドを含むことができる。ＣＴＡが実行される並列処理システムは、そのような多数の同時スレッドをサポートしてもサポートしなくてもよい。１つの様相において、本発明はそのようなハードウェア制限からプログラマを解き放す。これは、実際のハードウェア能力がどのようなものであれ、プログラマがＣＴＡ及びＣＴＡグリッドのモデルを使用して処理タスクを定義できるようにすることによってなされる。例えば、プログラマはコード（ＣＴＡプログラム）を書き、ＣＴＡの単一の代表的スレッドによって行われる処理タスクを定義し、ＣＴＡを或る数のそのようなスレッドとして定義し（スレッドの各々は一意の識別子を有する）、グリッドを或る数のＣＴＡとして定義する（ＣＴＡの各々は一意の識別子を有する）ことができる。下記で説明するように、そのようなコードは、特定のプラットフォーム上で実行されるコードへ自動的に翻訳される。例えば、もしＣＴＡが、或る数ｎ０の同時スレッドを含むものと定義され、しかし目標プラットフォームが、１つのスレッドしかサポートしないならば、トランスレータは、ｎ０個のスレッドの全てに割り当てられたタスクを行う１つの現実スレッドを定義することができる。もし目標プラットフォームが、２つ以上ではあるがｎ０個よりも少ない同時スレッドをサポートするならば、所望に応じてタスクを利用可能スレッド数へ分割することができる。
【００４９】
[0059]したがって、ＣＴＡ及びグリッドのプログラミング・モデルは、仮想モデル、即ち、特定の物理的現実から切り離されたプログラマへの概念的援助であるモデルとして理解されるべきである。ＣＴＡ及びグリッドの仮想モデルは、様々な程度の並列処理ハードウェア・サポートを有する多様な目標プラットフォームとして現実化可能である。具体的には、本明細書で使用される「ＣＴＡスレッド」の用語は、（可能性として、１つ又は複数の他の処理タスクと協力する）離散的処理タスクの仮想モデルを意味し、ＣＴＡスレッドは目標プラットフォーム上のスレッドに対して１対１でマップしてもマップしなくてもよいことを理解すべきである。
【００５０】
３．仮想アーキテクチャ
[0060]本発明の１つの様相によれば、ＣＴＡ及びＣＴＡグリッドを実行する仮想並列アーキテクチャが定義される。仮想並列アーキテクチャは、多数の同時ＣＴＡスレッドの実行をサポートする並列プロセッサ及び関連メモリ空間を表現する。多数の同時ＣＴＡスレッドは協調的に振る舞うことができ、例えば、所望の時点で相互にデータを共有し同期する。この仮想並列アーキテクチャは、多様な現実プロセッサ及び／又は処理システムの上にマップ可能である。そのような現実プロセッサ及び／又は処理システムには、例えば、図１のシステム１００のＰＰＵ１２２が含まれる。仮想アーキテクチャは、有利には、異なるレベルのデータ共有及びアクセス・タイプをサポートする或る数の仮想メモリ空間、及び仮想プロセッサによって実行可能な関数の全部を識別する仮想命令セット・アーキテクチャ（ＩＳＡ）を定義する。仮想アーキテクチャは、更に、有利には、仮想実行ドライバを定義する。仮想実行ドライバを、例えば、ＣＴＡ又はＣＴＡグリッドを定義及び起動することによって、ＣＴＡ実行を制御するために使用することができる。
【００５１】
[0061]図３は、本発明の実施形態に従った仮想アーキテクチャ３００のブロック図である。仮想アーキテクチャ３００は仮想プロセッサ３０２を含み、仮想プロセッサ３０２は、多数のＣＴＡスレッドを並列に実行するように構成された仮想コア３０８を有する。仮想アーキテクチャ３００は、更に、仮想プロセッサ３０２へアクセス可能なグローバルメモリ３０４、及び仮想プロセッサ３０２の動作を制御するコマンドを供給する仮想ドライバ３２０を含む。仮想ドライバ３２０はグローバルメモリ３０４へのアクセスも有する。
【００５２】
[0062]仮想プロセッサ３０２は、仮想ドライバ３２０からコマンドを受け取って解釈するフロントエンド３０６、及び単一ＣＴＡのｎ０個の全スレッドを同時に実行できる実行コア３０８を含む。仮想コア３０８は多数の（ｎ０個以上の）仮想処理エンジン３１０を含む。１つの実施形態において、各々の仮想処理エンジン３１０は１つのＣＴＡスレッドを実行する。仮想処理エンジン３１０はそれぞれのＣＴＡスレッドを同時に実行するが、必ずしも並列に実行することはない。１つの実施形態において、仮想アーキテクチャ３００は仮想処理エンジン３１０の数Ｔ（例えば、３８４、５００、７６８など）を特定する。この数はＣＴＡ内のスレッド数ｎ０の上限を設定する。理解すべきは、仮想アーキテクチャ３００の現実が、特定された数Ｔよりも少ない物理的処理エンジンを含んでもよく、単一の処理エンジンが幾つかのＣＴＡスレッド、単一の「現実」（即ち、プラットフォームでサポートされた）スレッド又は同時の複数現実スレッドとして実行できることである。
【００５３】
[0063]仮想プロセッサ３０２は、更に、仮想命令装置３１２を含む。仮想命令装置３１２は、仮想処理エンジン３１０がそれぞれのＣＴＡスレッドについて命令を供給されるように維持する。命令は、仮想アーキテクチャ３００の一部分である仮想ＩＳＡによって定義される。並列スレッド・コンピューティングの仮想ＩＳＡの例は、下記で説明される。命令装置３１２は、命令を仮想処理エンジン３１０へ供給する過程で、ＣＴＡスレッド同期及びＣＴＡスレッド振る舞いの他の協調的様相を管理する。
【００５４】
[0064]仮想コア３０８は、異なるレベルのアクセス可能性を有する内部データ記憶装置を提供する。特殊レジスタ３１１は読み出し可能であるが、仮想処理エンジン３１０のよる書き込みは不可能であり、図２の問題分解モデル内の各ＣＴＡスレッド「位置」を定義するパラメータを記憶するために使用される。１つの実施形態において、特殊レジスタ３１１は、ＣＴＡスレッドごとに（又は仮想処理エンジン３１０ごとに）、スレッドＩＤを記憶する１つのレジスタを含む。各々のスレッドＩＤレジスタは、仮想処理エンジン３１０のそれぞれの１つによってのみアクセス可能である。特殊レジスタ３１１は、更に、追加のレジスタを含んでもよく、これら追加のレジスタは全てのＣＴＡスレッド（又は全ての仮想処理エンジン３１０）によって読み込み可能であり、ＣＴＡ識別子、ＣＴＡ次元、ＣＴＡが属するグリッドの次元、及びＣＴＡが属するグリッドの識別子を記憶する。特殊レジスタ３１１は、仮想ドライバ３２０からフロントエンド３０６を介して受け取られたコマンドに応答して初期化中に書き込まれ、ＣＴＡ実行の間に変化しない。
【００５５】
[0065]仮想ローカルレジスタ３１４は、各々のＣＴＡスレッドによってスクラッチ空間として使用される。各々のレジスタは、１つのＣＴＡスレッド（又は１つの仮想処理エンジン３１０）の排他的使用に割り振られ、ローカルレジスタ３１４内のデータは、ローカルレジスタが割り振られたＣＴＡスレッドへのみアクセス可能である。共有メモリ３１６は、（単一のＣＴＡ内の）全てのＣＴＡスレッドへアクセス可能である。共有メモリ３１６内の場所は、同じＣＴＡ内のＣＴＡスレッド（又は仮想コア３０８内の仮想処理エンジン）へアクセス可能である。パラメータ・メモリ３１８はランタイムパラメータ（定数）を記憶する。ランタイムパラメータはＣＴＡスレッド（又は仮想処理エンジン３１０）によって読み出し可能であるが、書き込みはできない。１つの実施形態において、仮想ドライバ３２０はパラメータをパラメータ・メモリ３１８に提供するが、この提供は、これらのパラメータを使用するＣＴＡの実行開始を仮想プロセッサ３０２に命令する前に行われる。ＣＴＡ内のＣＴＡスレッド（又は仮想コア３０８内の仮想処理エンジン３１０）は、メモリ・インタフェース３２２を介してグローバルメモリ３０４にアクセスすることができる。
【００５６】
[0066]仮想アーキテクチャ３００において、仮想プロセッサ３０２は仮想ドライバ３２０の制御のもとでコプロセッサとして動作する。仮想アーキテクチャの仕様は、有利には、仮想アプリケーション・プログラム・インタフェース（ＡＰＩ）を含む。仮想ＡＰＩは、仮想ドライバ３２０によって認識される関数呼び出し、及び各々の関数呼び出しが作成するように期待される振る舞いを識別する。並列スレッド・コンピューティングを目的とする仮想ＡＰＩの例示的関数呼び出しは、下記で説明される。
【００５７】
[0067]仮想アーキテクチャ３００は、様々なハードウェア・プラットフォームの上で現実化可能である。１つの実施形態において、仮想アーキテクチャ３００は、図１のシステム１００の中で現実化され、ＰＰＵ１２２は仮想プロセッサ３０２を実現し、ＣＰＵ１０２上で実行するＰＰＵドライバ・プログラムは仮想ドライバ３２０を実現する。グローバルメモリ３０４は、システム・メモリ１０４及び／又はＰＰメモリ１２４の中で実現可能である。
【００５８】
[0068]１つの実施形態において、ＰＰＵ１２２は１つ又は複数の処理コアを含む。処理コアは、単一命令複数データ（ＳＩＭＤ）及びマルチスレッド手法を使用して、（仮想命令装置３１２を実現する）単一の命令装置からの多数の（例えば、３８４又は７６８個の）スレッドの同時実行をサポートする。各々のコアはＰ個の（例えば、８個、１６個などの）並列処理エンジン３０２のアレイを含む。処理エンジン３０２は命令装置からＳＩＭＤ命令を受け取って実行するように構成され、Ｐ個のスレッドまでのグループが並列に処理されることを可能にする。コアはマルチスレッドされ、処理エンジンはＧ個（例えば、２４個）までのスレッド・グループを同時に実行することができる。この同時実行は、例えば、各々のスレッドに関連した最新状態情報を維持し、処理エンジンが１つのスレッドから他のスレッドへ迅速に切り換わることによって行われる。こうして、コアは、同時に、各々Ｐ個のスレッドから成るＧ個のＳＩＭＤグループ、即ち、全部でＰ＊Ｇ個の同時スレッドを同時に実行する。この現実化において、Ｐ＊Ｇ≧ｎ０である限り、（仮想の）ＣＴＡスレッドと、現実のＰＰＵ１２２の上で実行している同時スレッドとの間に、１対１の対応が存在し得る。
【００５９】
[0069]特殊レジスタ３１１はＰＰＵ１２２の中で実現可能である。この実現は、各々の処理コアにＰ＊Ｇ項目レジスタ・ファイルを提供し、各々の項目がスレッドＩＤを記憶できるようにし、更にＣＴＡ  ＩＤ、グリッドＩＤ、並びにＣＴＡ次元及びグリッド次元を記憶するためのグローバル読み出し可能レジスタの集合を提供することによって行われる。代替として、特殊レジスタ３１１は他の記憶場所を使用して実現可能である。
【００６０】
[0070]ローカルレジスタ３１４は、ＰＰＵ１２２の中でローカルレジスタ・ファイルとして実現可能である。ローカルレジスタ・ファイルは物理的又は論理的にＰ個のレーン（ｌａｎｅ）に分割され、各々のレーンは或る数の項目を有する（ここで、各々の項目は、例えば、３２ビット・ワードを記憶できる）。Ｐ個の処理エンジンの各々へ１つのレーンを割り当て、異なるレーンの中の対応する項目に、同じプログラムを実行する別々のスレッドのデータを入れて、ＳＩＭＤ実行を容易にすることができる。レーンの異なる部分は、Ｇ個の同時スレッド・グループの異なるものへ割り振られ、したがってローカルレジスタ・ファイル内の所与の項目は、特定のスレッドへのみアクセス可能である。１つの実施形態において、ローカルレジスタ・ファイル内の或る項目は、スレッド識別子を記憶するために予約され、特殊レジスタ３１１の１つを実現する。
【００６１】
[0071]共有メモリ３１６は、ＰＰＵ１２２の中で、共有レジスタ・ファイルとして実現されてもよく、処理エンジンが共有メモリ内の場所との間で読み出し又は書き込みを可能にする相互接続を有する共有オンチップ・キャッシュメモリとして実現されてもよい。パラメータ・メモリ３１８は、ＰＰＵ１２２の中で、同じ共有レジスタ・ファイル又は共有メモリ３１６を実現する共有キャッシュメモリの中の指定セクションとして実現されてもよく、処理エンジンが読み出し専用アクセスを有する別個の共有レジスタ・ファイル又はオンチップ・キャッシュメモリとして実現されてもよい。１つの実施形態において、パラメータ・メモリを実現する区域は、更に、ＣＴＡ  ＩＤ及びグリッドＩＤ並びにＣＴＡ次元及びグリッド次元を記憶するために使用され、特殊レジスタ３１１の一部分を実現する。
【００６２】
[0072]１つの実施形態において、図１のＣＰＵ１０２で実行するＰＰＵドライバ・プログラムは、メモリ（例えば、システム・メモリ１０４）内のプッシュバッファ（明示的には示されない）へコマンドを書き込むことによって、仮想ＡＰＩ関数呼び出しに応答する。コマンドはプッシュバッファからＰＰＵ１２２によって読み出される。コマンドは、有利には、状態パラメータ、例えば、ＣＴＡ内のスレッドの数、ＣＴＡを使用して処理される入力データセットのグローバルメモリ内の場所、実行されるＣＴＡプログラムのグローバルメモリ内の場所、及び出力データが書き込まれるグローバルメモリ内の場所に関連づけられる。コマンド及び状態パラメータに応答して、ＰＰＵ１２２は状態パラメータを自分のコアの１つへロードし、ＣＴＡパラメータ内で特定された或る数のスレッドが起動されてしまうまで、スレッドの起動を始める。１つの実施形態において、ＰＰＵ１２２は制御論理を含み、この制御論理はスレッドが起動されるときスレッドＩＤをスレッドへ順次に割り当てる。スレッドＩＤは、例えば、ローカルレジスタ・ファイル内の指定場所、又はこの目的だけの特殊レジスタの中に記憶できる。
【００６３】
[0073]代替の実施形態において、仮想アーキテクチャ３００は（例えば、幾つかのＣＰＵにおける）単一スレッド処理コアで現実化される。処理コアは、ｎ０個よりも少ない現実のスレッドを使用して全てのＣＴＡスレッドを実行する。仮想プログラミング・モデルが、異なるＣＴＡスレッド関連づける処理タスクは、例えば、１つのＣＴＡスレッドのためにタスク（又はタスクの一部分）を実行し、続いて次のＣＴＡスレッドのために実行し、以下同様に実行することによって単一のスレッドへ結合できる。ベクトル実行、ＳＩＭＤ実行、及び／又は機械内で利用可能な他の形式の並列実行は、複数ＣＴＡスレッドに関連づけられた処理タスクを並列に実行、又は同じＣＴＡスレッドに関連づけられた複数の処理タスクを並列に実行するために活用できる。こうして、ＣＴＡが、単一のスレッド、ｎ０個のスレッド、又は他の数のスレッドを使用して現実化できる。下記で説明されるように、仮想命令トランスレー
タは、有利には、目標仮想アーキテクチャ３００へ書かれたコードを目標プラットフォームに特有の命令へ翻訳する。
【００６４】
[0074]本明細書で説明された仮想アーキテクチャは例であること、そして変形及び修正が可能であることが理解される。例えば、１つの代替の実施形態において、各々の仮想処理エンジンは、スレッドに割り当てられた一意のスレッドＩＤを記憶し、ローカル仮想レジスタ内の空間をこの目的に使用することのない専用のスレッドＩＤレジスタを有してもよい。
【００６５】
[0075]他の例として、仮想アーキテクチャは仮想コア３０８の内部構造の詳細を多かれ少なかれ特定してもよい。例えば、仮想コア３０８がＰ個のマルチスレッド仮想処理エンジンを含み、Ｐ路ＳＩＭＤグループ内のＣＴＡスレッドを実行するために処理エンジンが使用され、Ｇ個までのＳＩＭＤグループがコア３０８の中に共存し、Ｐ＊ＧがＴ（ＣＴＡ内のスレッドの最大数）を決定することを特定してもよい。異なるタイプのメモリ及び異なる共有レベルも特定可能である。
【００６６】
[0076]仮想アーキテクチャは、ハードウェア及び／又はソフトウェア要素の組み合わせを使用して各々のコンポーネントを定義及び制御する多様なコンピュータ・システムで現実化されてもよい。例として、ハードウェア・コンポーネントを使用する１つの現実化が説明されたが、本発明は特定のハードウェア現実からプログラミング・タスクの切り離しに関することを理解すべきである。
【００６７】
４．仮想アーキテクチャのプログラミング
[0077]図４は、本発明の実施形態に従って、仮想アーキテクチャ３００を使用して目標プロセッサ又は目標プラットフォーム４４０を動作させる概念的モデル４００である。モデル４００が示すように、仮想アーキテクチャ３００の存在は、目標プロセッサ又はプラットフォームのハードウェア実現から、コンパイルされたアプリケーション及びＡＰＩを切り離す。
【００６８】
[0078]アプリケーション・プログラム４０２は、前述した仮想プログラミング・モデルを利用するデータ処理アプリケーションを定義する。定義には、単一ＣＴＡ及び／又はＣＴＡグリッドの定義が含まれる。一般的に、アプリケーション・プログラム４０２は複数の様相を含む。第１に、プログラムは単一ＣＴＡスレッドの振る舞いを定義する。第２に、プログラムは（ＣＴＡスレッドの数で）ＣＴＡの次元を定義し、もしグリッドが使用されるのであれば、（ＣＴＡの数で）グリッドの次元を定義する。第３に、プログラムは、ＣＴＡ（又はグリッド）によって処理される入力データセットを定義し、また出力データセットが記憶される場所を定義する。第４に、プログラムは、例えば、各々のＣＴＡ又はグリッドをいつ起動するかを含む、全体的な処理振る舞いを定義する。プログラムは、ＣＴＡ又はグリッドの次元、新しいＣＴＡ又はグリッドの起動を控えるかどうかなどを動的に決定する追加のコードを含んでもよい。
【００６９】
[0079]アプリケーション・プログラム４０２は、高級プログラミング言語、例えば、Ｃ／Ｃ＋＋、ＦＯＲＴＲＡＮなどで書かれてもよい。１つの実施形態において、アプリケーションＣ／Ｃ＋＋プログラムは、１つの（仮想）ＣＴＡスレッドの振る舞いを直接特定する。他の実施形態において、アプリケーション・プログラムはデータ並列言語（例えば、Ｆｏｒｔｒａｎ  ９０、Ｃ＊、又はＤａｔａ−Ｐａｒａｌｌｅｌ  Ｃ）を使用して書かれ、アレイ及び集合体データ構造へのデータ並列動作を特定する。そのようなプログラムは、１つの（仮想）ＣＴＡスレッドの振る舞いを特定する仮想ＩＳＡプログラム・コードにコンパイルできる。ＣＴＡスレッドの振る舞いを定義できるようにするため、言語拡張又は関数ライブラリが提供され、これらを介して、プログラマは並列ＣＴＡスレッド振る舞いを特定することができる。例えば、特殊記号又は変数は、スレッドＩＤ、ＣＴＡ  ＩＤ、及びグリッドＩＤに対応するように定義され、関数が提供される。関数を介して、プログラマは、ＣＴＡスレッドが他のＣＴＡスレッドといつ同期すべきかを指示することができる。
【００７０】
[0080]アプリケーション・プログラム４０２がコンパイルされるとき、コンパイラ４０８は、ＣＴＡスレッド振る舞いを定義するアプリケーション・プログラム４０２の部分について、仮想ＩＳＡコード４１０を生成する。１つの実施形態において、仮想ＩＳＡコード４１０は図３の仮想アーキテクチャ３００の仮想ＩＳＡとして表現される。仮想ＩＳＡコード４１０はプログラム・コードであるが、必ずしも特定の目標プラットフォーム上で実行できる形式ではない。仮想ＩＳＡコード４１０は他のプログラム・コードと同じように記憶及び／又は配布される。他の実施形態において、アプリケーション・プログラムは全体的又は部分的に仮想ＩＳＡコード４１０として特定されてもよく、コンパイラ４０８は全体的又は部分的にバイパスされてもよい。
【００７１】
[0081]仮想命令トランスレータ４１２は仮想ＩＳＡコード４１０を目標ＩＳＡコード４１４へ変換する。幾つかの実施形態において、目標ＩＳＡコード４１４は、目標プラットフォーム４４０によって直接実行できるコードである。例えば、図４の点線ボックスによって示されるように、１つの実施形態において、目標ＩＳＡコード４１４はＰＰＵ１２２内の命令装置４３０によって受け取られ、正しくデコードされる。目標プラットフォーム４４０の仕様に依存して、仮想ＩＳＡコード４１０は、目標プラットフォーム４４０上でｎ０個のスレッドの各々によって実行されるスレッド単位コードへ翻訳されてもよい。代替として、仮想ＩＳＡコード４１０はｎ０個よりも少ないスレッドとして実行されるプログラム・コードへ翻訳されてもよく、各々のスレッドが２つ以上のＣＴＡスレッドに関する処理タスクを含む。
【００７２】
[0082]幾つかの実施形態において、ＣＴＡ及び／又はグリッドの次元定義、並びに入力データセット及び出力データセットの定義は、仮想ＡＰＩによって取り扱われる。アプリケーション・プログラム４０２は、仮想ＡＰＩ関数のライブラリ４０４への呼び出しを含んでもよい。１つの実施形態において、仮想ＡＰＩの仕様（例えば、関数名、入力、出力、及び効果を含むが、実現の詳細は含まない）がプログラマへ提供され、プログラマは仮想ＡＰＩ呼び出しをアプリケーション・プログラム４０２の中へ直接組み込んで、仮想ＡＰＩコード４０６を直接生成する。他の実施形態において、仮想ＡＰＩコード４０６は、他の構文を使用してＣＴＡ及びグリッドを定義するアプリケーション・プログラム４０２をコンパイルすることによって生成される。
【００７３】
[0083]仮想ＡＰＩコード４０６は、仮想実行ドライバ４１６を提供することによって部分的に現実化される。仮想実行ドライバ４１６はコード４０６の仮想ＡＰＩコマンドを目標ＡＰＩコマンド４１８へ翻訳し、目標ＡＰＩコマンド４１８は目標プラットフォーム４４０によって処理されてもよい。例えば、図４の点線ボックスによって示されるように、１つの実施形態において、目標ＡＰＩコマンド４１８はＰＰＵドライバ４３２によって受け取られ、処理されてもよい。ＰＰＵドライバ４３２は、対応するコマンドをＰＰＵ１２２のフロントエンド４３４へ通信する。（この実施形態において、仮想実行ドライバ４１６は、ＰＰＵドライバ４３２の１つの様相又は部分であってもよい。）他の実施形態において、仮想実行ドライバはコプロセッサのドライバに対応しなくてもよい。仮想実行ドライバは単純に、仮想実行ドライバを実行する同じプロセッサ上で、他のプログラム又はスレッドを起動する制御プログラムであってもよく仮想実行ドライバを実行する同じプロセッサ上で、他のプログラム又はスレッドを起動する。
【００７４】
[0084]理解すべきは、仮想命令トランスレータ４１２及び仮想実行ドライバ４１６は、ＣＴＡ実行をサポート可能な任意のプラットフォーム又はアーキテクチャのために作成できることである。異なるプラットフォーム又はアーキテクチャの仮想命令トランスレータ４１２が同じ仮想ＩＳＡから翻訳できる範囲で、同じ仮想ＩＳＡコード４１０を任意のプラットフォーム又はアーキテクチャと共に使用できる。こうして、アプリケーション・プログラム４０２は、各々の可能なプラットフォーム又はアーキテクチャのために再コンパイルされる必要はない。
【００７５】
[0085]更に、目標プラットフォーム４４０が、図４で示されるようなＰＰＵ及び／又はＰＰＵドライバを含むことは必要でない。例えば、１つの代替の実施形態において、目標プラットフォームはＣＰＵであり、このＣＰＵはソフトウェア手法を使用して多数のスレッドの同時実行をエミュレートし、目標ＩＳＡコード及び目標ＡＰＩコマンドは、目標ＣＰＵによって実行されるプログラム（又は相互に通信するプログラムのグループ）内の命令に対応する。目標ＣＰＵは、例えば、シングルコア又はマルチコアのＣＰＵであってもよい。
【００７６】
５．仮想ＩＳＡの例
[0086]本発明の実施形態に従った仮想ＩＳＡの例を、今から説明する。前述したように、仮想ＩＳＡは、有利には、前述した仮想プログラミング・モデル（ＣＴＡ及びグリッド）に対応する。したがって、この実施形態において、コンパイラ４０８によって生成された仮想ＩＳＡコード４１０は、図３の仮想コア３０８内で仮想処理エンジン３１０の１つによって実行される単一ＣＴＡスレッドの振る舞いを定義する。振る舞いは他のＣＴＡスレッドとの協調的交信、例えば、同期及び／又はデータ共有を含んでもよい。
【００７７】
[0087]理解すべきは、本明細書で説明される仮想ＩＳＡは、単なる例であること、及び本明細書で説明される特定の要素、又は要素の組み合わせは、本発明の範囲を限定しないことである。幾つかの実施形態において、プログラマは仮想ＩＳＡでコードを書いてもよく、他の実施形態において、プログラマは他の高級言語（例えば、ＦＯＲＴＲＡＮ、Ｃ、Ｃ＋＋）でコードを書き、コンパイラ４０８が仮想ＩＳＡコードを生成する。プログラマは、更に、或る部分は高級言語で書かれ、他の部分は仮想ＩＳＡで書かれる「混合」コードを書くことが可能である。
【００７８】
５．１．特殊変数
[0088]図５は、例示的仮想ＩＳＡによって定義された「特殊」変数を列挙する表５００である（本明細書では、特殊変数を知らせるため「％」接頭辞が使用される）。これらの変数は図２のプログラミング・モデルに関する。このプログラミング・モデルにおいて、各々のスレッド２０４はＣＴＡ２０２内の位置によって識別され、転じてＣＴＡ２０２は、或る数のグリッド２００の中にある特定の１つに存在する。幾つかの実施形態において、表５００の特殊変数は、図３の仮想アーキテクチャ３００の特殊レジスタ３１１に対応する。
【００７９】
[0089]表５００において、ＣＴＡ及びグリッドの各々は３次元空間で定義されること、及び異なるグリッドは１次元空間で順次に番号を付けられることが想定される。仮想ＩＳＡは、ＣＴＡが起動されたとき図５の特殊変数が初期化されることを期待し、仮想ＩＳＡコードは、初期化なしに、これらの変数を単純に使用することができる。特殊変数の初期化は、仮想ＡＰＩを参照して下記で説明される。
【００８０】
[0090]図５で示されるように、特殊変数％ｎｔｉｄ＝（％ｎｔｉｄ．ｘ，％ｎｔｉｄ．ｙ，％ｎｔｉｄ．ｚ）の最初の３ベクトルは、ＣＴＡの次元を（スレッドの数で）定義する。ＣＴＡの全てのスレッドは同じ％ｎｔｉｄベクトルを共有できる。仮想アーキテクチャ３００において、％ｎｔｉｄベクトルの値は、後述するように、ＣＴＡの次元を確立する仮想ＡＰＩ関数呼び出しを介して仮想プロセッサ３０２へ提供されることが期待される。
【００８１】
[0091]図５で示されるように、特殊変数％ｔｉｄ＝（％ｔｉｄ．ｘ，％ｔｉｄ．ｙ，％ｔｉｄ．ｚ）の２番目の３ベクトルは、ＣＴＡにおける所与のスレッドのスレッドＩＤを参照する。図３の仮想アーキテクチャ３００において、ＣＴＡの各々のスレッドが起動されるとき、制約０≦％ｔｉｄ．ｘ＜％ｎｔｉｄ．ｘ、０≦％ｔｉｄ．ｙ＜％ｎｔｉｄ．ｙ、及び０≦％ｔｉｄ．ｚ＜ｎｔｉｄ．ｚを満足させる一意の％ｔｉｄベクトルを仮想プロセッサ３０２が割り当てることが期待される。１つの実施形態において、％ｔｉｄベクトルはパック３２ビット・ワードとして記憶されるように定義されてもよい（例えば、％ｔｉｄ．ｘには１６ビット、％ｔｉｄ．ｙには１０ビット、％ｔｉｄ．ｚには６ビット）。
【００８２】
[0092]図５で示されるように、特殊変数％ｎｃｔａｉｄ＝（％ｎｃｔａｉｄ．ｘ，％ｎｃｔａｉｄ．ｙ，％ｎｃｔａｉｄ．ｚ）の３番目の３ベクトルは、グリッドの次元を（ＣＴＡの数で）定義する。図３の仮想アーキテクチャ３００において、ＣＴＡのグリッドの次元を確立する仮想ＡＰＩ関数呼び出しを介して、％ｎｃｔａｉｄベクトルの値が仮想プロセッサ３０２へ提供されることが期待される。
【００８３】
[0093]図５で示されるように、特殊変数％ｃｔａｉｄ＝（％ｃｔａｉｄ．ｘ，％ｃｔａｉｄ．ｙ，％ｃｔａｉｄ．ｚ）の4番目の３ベクトルは、グリッドにおける所与のＣＴＡのＣＴＡ  ＩＤを参照する。図３の仮想アーキテクチャ３００において、ＣＴＡが起動されるとき、ＣＴＡについて制約０≦％ｃｔａｉｄ．ｘ＜％ｎｃｔａｉｄ．ｘ、０≦％ｃｔａｉｄ．ｙ＜％ｎｃｔａｉｄ．ｙ、及び０≦％ｃｔａｉｄ．ｚ＜％ｎｃｔａｉｄ．ｚを満足させる一意の％ｃｔａｉｄベクトルが仮想プロセッサ３０２へ提供されることが期待される。
【００８４】
[0094]特殊変数は、更に、ＣＴＡが属するグリッドのためにグリッド識別子を提供するスカラー％ｇｒｉｄｉｄ変数を含む。図３の仮想アーキテクチャ３００において、％ｇｒｉｄｉｄ値が仮想プロセッサ３０２へ提供されて、現在のＣＴＡを一部分とするグリッドを識別することが期待される。％ｇｒｉｄｉｄ値は、有利には、例えば、複数のグリッドが使用されて大きな問題の異なる部分を解決するとき、仮想ＩＳＡコードの中で使用される。
【００８５】
５．２．プログラムで定義される変数及び仮想状態空間
[0095]仮想ＩＳＡによって、プログラマ（又はコンパイラ）は任意の数の変数を定義して、処理されているデータ項目を表すことができる。変数は、型及び「仮想状態空間」によって定義される。仮想状態空間は、変数がどのように使用されるか、また変数がどの範囲まで共有されるかを指示する。変数は、目標プラットフォームで利用可能なレジスタ又は他のメモリ構造を使用して現実化される。多くの目標プラットフォームにおいて、状態空間は特定の変数の現実化に使用されるメモリ構造の選択に影響を及ぼし得る。
【００８６】
[0096]図６は、例示的仮想ＩＳＡ実施形態でサポートされる変数型を列挙する表６００である。４つの型がサポートされる。即ち、型を有しないビット、符号付き整数、符号のない整数、及び浮動小数点である。型を有しない変数は、単純に単一のビット又は特定長ビットのグループである。符号付き及び符号のない整数形式、並びに浮動小数点形式は、通常の形式（例えば、ＩＥＥＥ７５４標準）に従って定義されてもよい。
【００８７】
[0097]この実施形態において、各々の型について複数の幅がサポートされ、幅を特定するためパラメータ＜ｎ＞が使用される。したがって、例えば、．ｓ１６は１６ビット符号付き整数を、．ｆ３２は３２ビット浮動小数点数を表し、以下同様である。表６００で示されるように、幾つかの変数型は或る一定の幅へ制限される。例えば、浮動小数点変数は少なくとも１６ビットでなければならず、整数型は少なくとも８ビットでなければならない。仮想ＩＳＡの現実化は、特定された幅の全てをサポートすることを期待される。もしプロセッサのデータ経路及び／又はレジスタが、最も広い幅よりも狭ければ、当技術分野で知られるように、複数のレジスタ及びプロセッサ・サイクルを使用して、より広い型を取り扱うことができる。
【００８８】
[0098]注意すべきは、本明細書で使用されるデータの型及び幅は、例であって、本発明を限定しないことである。
【００８９】
[0099]図７は、例示的仮想ＩＳＡでサポートされる仮想状態空間を列挙する表である。９つの状態空間が定義され、これらは図３の仮想アーキテクチャにおける異なる共有レベル及び可能な記憶場所に対応する。
【００９０】
[0100]最初の３つの状態空間はスレッド・レベルで共有される。これは、各々のＣＴＡスレッドが変数の別々のインスタンスを有し、ＣＴＡスレッドは他のＣＴＡスレッドのインスタンスへのアクセスを有しないことを意味する。仮想レジスタ（．ｒｅｇ）状態空間は、有利には、オペランド、一時値（ｔｅｍｐｏｒａｒｙ  ｖａｌｕｅ）、及び／又は各々のＣＴＡスレッドによって行われる計算の結果を定義するために使用される。プログラムは任意の数の仮想レジスタを宣言できる。仮想レジスタは、計算されたアドレスではなく、静的なコンパイル時の名前によってのみアドレス可能である。この状態空間は、図３の仮想アーキテクチャ３００におけるローカル仮想レジスタ３１４に対応する。
【００９１】
[0101]特殊レジスタ（．ｓｒｅｇ）状態空間は、仮想アーキテクチャ３００の特殊レジスタ３１１に記憶される図５の既定の特殊変数に対応する。幾つかの実施形態において、仮想ＩＳＡコードは．ｓｒｅｇ空間内で他の変数を宣言しなくてもよいが、特殊変数を計算への入力として使用してもよい。全てのＣＴＡスレッドは．ｓｒｅｇ状態空間内の変数を読み出すことができる。％ｔｉｄ（又はそのコンポーネント）の場合、各々のＣＴＡスレッドは自分の一意のスレッド識別子を読み出す。．ｓｒｅｇ状態空間内の他の変数の場合、同じＣＴＡ内の全てのＣＴＡスレッドは、同じ値を読み出す。
【００９２】
[0102]スレッド単位（ｐｅｒ−ｔｈｒｅａｄ）ローカルメモリ（．ｌｏｃａｌ）変数は、ＣＴＡスレッド単位で割り振り及びアドレスされるグローバルメモリ３０４の領域に対応する。言い換えれば、ＣＴＡスレッドが．ｌｏｃａｌ変数にアクセスするとき、ＣＴＡスレッドは変数の自分自身のインスタンスにアクセスし、１つのＣＴＡスレッド内で行われた．ｌｏｃａｌ変数への変更は、他のＣＴＡスレッドに影響しない。．ｒｅｇ及び．ｓｒｅｇ状態空間とは異なり、スレッド単位ローカルメモリは、計算されたアドレスを使用してアドレスされることが可能である。
【００９３】
[0103]次の２つの状態空間はＣＴＡ単位（ｐｅｒ−ＣＴＡ）変数を定義する。これは、各々のＣＴＡが変数の１つのインスタンスを有し、このインスタンスがＣＴＡ（仮想）スレッドの任意のものによってアクセスされてもよいことを意味する。共有（．ｓｈａｒｅｄ）変数は、ＣＴＡスレッドの任意のものによって読み出し又は書き込まれてもよい。幾つかの実施形態において、この状態空間は仮想アーキテクチャ３００（図３）の仮想共有メモリ３１６へマップする。仮想アーキテクチャ３００の現実化において、．ｓｈａｒｅｄ状態空間はオンチップ共有メモリ実現（例えば、共有レジスタ・ファイル又は共有キャッシュメモリ）の上にマップでき、他の現実化においては、．ｓｈａｒｅｄ状態空間は、他のグローバルアクセス可能メモリとして割り振り及びアドレスされるオフチップ・メモリのＣＴＡ単位領域にマップできる。
【００９４】
[0104]パラメータ（．ｐａｒａｍ）変数は読み出し専用であり、ＣＴＡ内の任意の（仮想）スレッドによって読み出されることが可能である。この状態空間は、仮想アーキテクチャ３００のパラメータ・メモリ３１８へマップし、例えば、オンチップ共有パラメータ・メモリ又はキャッシュメモリの中で現実化されるか、他のグローバルアクセス可能メモリと同じように割り振り及びアドレスされるグローバルアクセス可能オフチップ・メモリの領域の中で現実化されることが可能である。これらの変数は、仮想ドライバ３２０からのドライバ・コマンドに応答して初期化されることが期待される。
【００９５】
[0105]定数（．ｃｏｎｓｔ）状態空間は、グリッド内のＣＴＡの（仮想）スレッドによって読み出されることの可能な（しかし、修正されない）グリッドごとの定数を定義するために使用される。仮想アーキテクチャ３００において、．ｃｏｎｓｔ状態空間は、ＣＴＡスレッドが読み出し専用アクセスを有するグローバルメモリ内の領域へマップされてよもい。．ｃｏｎｓｔ状態空間は、オンチップ共有パラメータ・メモリ又はキャッシュメモリの中、又は他のグローバルアクセス可能メモリと同じように割り振り及びアドレスされるグローバルアクセス可能オフチップ・メモリのグリッド単位（ｐｅｒ−ｇｒｉｄ）領域の中で現実化されることが可能である。．ｐａｒａｍ状態空間と同じように、．ｃｏｎｓｔ状態空間内の変数は、仮想ドライバ３２０からのドライバ・コマンドに応答して初期化されることが期待される。
【００９６】
[0106]残りの３つの状態空間は「文脈」変数を定義する。これらの変数は、アプリケーションに関連したＣＴＡ内の（仮想）スレッドからアクセス可能である。これらの状態空間は、仮想アーキテクチャ３００内のメモリ３０４にマップする。グローバル（．ｇｌｏｂａｌ）変数は汎用目的に使用されることが可能である。幾つかの実施形態において、共有テクスチャ（．ｔｅｘ）及びサーフェイス（．ｓｕｒｆ）の特有状態空間も定義されてもよい。これらの状態空間は、例えば、グラフィックス関連アプリケーションに有用可能であり、２Ｄ（又は幾つかの実施形態では３Ｄ）アレイの各画素に対応するデータ値を提供するグラフィックス・テクスチャ及び画素サーフェイス・データ構造へのアクセスを定義及び提供するために使用できる。
【００９７】
[0107]図４の仮想ＩＳＡコード４１０において、変数は、状態空間、型、及び名前を特定することによって宣言される。名前はプレースホルダであり、プログラマ又はコンパイラによって選択されてもよい。したがって、例えば、
．ｒｅｇ  ．ｂ３２  ｖｒｌ；
は、ｖｒｌと名前を付けられた仮想レジスタ状態空間で型のない３２ビット変数を宣言する。仮想ＩＳＡコードの後続の行は、例えば、演算のソース又はデスティネーションとして、ｖｒｌを参照することができる。
【００９８】
[0110]例示的仮想ＩＳＡは、更に、仮想変数のアレイ及びベクトルをサポートする。例えば、
．ｇｌｏｂａｌ  ．ｆ３２  ｒｅｓｕｌｔＡｒｒａｙ［１０００］［１０００］；
は、３２ビット浮動小数点数の仮想グローバルアクセス可能１０００×１０００アレイを宣言する。仮想命令トランスレータ４１２は、割り当てられた状態空間に対応するアドレス可能メモリ領域へアレイをマップできる。
【００９９】
[0113]１つの実施形態におけるベクトルは、ベクトル接頭辞．ｖ＜ｍ＞を使用して定義されてもよい。ここでｍはベクトルの成分の数である。例えば、
．ｒｅｇ  ．ｖ３  ．ｆ３２  ｖｐｏｓ；
は、スレッド単位仮想レジスタ状態空間内の３２ビット浮動小数点数の３成分ベクトルを宣言する。ベクトルが一度宣言されると、その成分は接尾辞を使用して識別されてもよい。例えば、ｖｐｏｓ．ｘ、ｖｐｏｓ．ｙ、ｖｐｏｓ．ｚのようになる。１つの実施形態において、ｍ＝２，３，又は４が許され、成分を識別するため、接尾辞、例えば、（．ｘ，．ｙ，．ｚ，．ｗ）、（．０，．１，．２，．３）、又は（．ｒ，．ｇ，．ｂ，．ａ）が使用される。
【０１００】
[0116]変数は仮想であるから、仮想ＩＳＡコード４１０は、任意の状態空間の中で任意の数の変数を定義又は参照してもよい（例外は．ｓｒｅｇである。この場合、変数は予め定義されている）。仮想ＩＳＡコード４１０の中で特定の状態空間について定義される変数の数は、特定のハードウェア実現の中の対応する型の記憶量を超過することが可能である。仮想命令トランスレータ４１２は、有利には、適切な記憶管理命令（例えば、レジスタとオフチップ・メモリ間でデータを移動すること）を含んで、必要とされるとき変数を利用可能にするように構成される。仮想命令トランスレータ４１２は、更に、一時変数が最早必要とされない場合を検出し、一時変数に割り振られた空間を他の変数に再使用させることができる。レジスタを割り振る従来のコンパイラ手法が使用できる。
【０１０１】
[0117]更に、例示的仮想ＩＳＡはベクトル変数の型を定義するが、目標プラットフォームがベクトル変数をサポートすることは要求されない。仮想命令トランスレータ４１２は、適切な数（例えば、２、３、又は４）のスカラーの集まりとして、ベクトル変数を実現できる。
【０１０２】
５．３．仮想命令
[0118]図８Ａ〜図８Ｈは、例示的仮想ＩＳＡで定義された仮想命令を列挙する表である。命令は、命令の効果によって定義される。例えば、１つ又は複数のオペランドを使用して特定の結果を計算し、この結果をデスティネーション・レジスタの中に置き、レジスタ値を設定する、などである。大部分の仮想命令は、入力及び／又は出力の形式を識別するような型に分けられ、命令実行の様相は型に依存する可能性がある。命令の一般形式は、次のとおりである。
ｎａｍｅ．＜ｔｙｐｅ＞  ｒｅｓｕｌｔ，ｏｐｅｒａｎｄｓ；
【０１０３】
[0120]ここで、ｎａｍｅは命名の名前であり、．＜ｔｙｐｅ＞は図６で列挙された型のプレースホルダであり、ｒｅｓｕｌｔは結果を記憶する変数であり、ｏｐｅｒａｎｄｓは１つ又は複数の変数であって、これらの変数は入力として命令へ提供される。１つの実施形態において、仮想アーキテクチャ３００は、レジスタ間（ｒｅｇｉｓｔｅｒ−ｔｏ−ｒｅｇｉｓｔｅｒ）プロセッサである。メモリ・アクセス（図８Ｆ）以外の演算のｒｅｓｕｌｔ及びｏｐｅｒａｎｄｓは、仮想レジスタ状態空間．ｒｅｇ（又は幾つかのオペランドの場合には、特殊レジスタ状態空間．ｓｒｅｇ）の中の変数であることを要求される。
【０１０４】
[0121]目標プラットフォームは、仮想ＩＳＡの命令の各々を現実化することを期待される。命令は、特定された効果を作成する対応機械命令（本明細書では、「ハードウェア・サポート」と呼ばれる）、又は実行されたとき、特定された効果を作成する機械命令のシーケンスとして現実化できる（本明細書では、「ソフトウェア・サポート」と呼ばれる）。特定の目標プラットフォームに対する仮想命令トランスレータ４１２は、有利には、各々の仮想命令に対応する機械命令又は機械命令シーケンスを識別するように構成される。
【０１０５】
[0122]下記のサブセクションは、図８Ａ〜図８Ｈで列挙された命令の様々な種類を説明する。理解すべきは、本明細書で呈示された命令のリストは例であること、及び仮想ＩＳＡは本明細書で明示的に説明されない追加の命令を含んでもよく、本明細書で説明された命令の幾つか又は全部を排除できることである。
【０１０６】
５．３．１  仮想命令−算術
[0123]図８Ａは、例示的仮想ＩＳＡで定義された算術演算を列挙する表８００である。この実施形態において、仮想アーキテクチャはレジスタ間算術のみをサポートし、全ての算術演算は１つ又は複数の仮想レジスタ・オペランド（図８Ａのａ，ｂ，ｃで表される）を操作して、仮想レジスタへ書き込まれる結果（ｄ）を作成する。こうして、算術演算のオペランド及びデスティネーションは、常に、仮想レジスタ状態空間．ｒｅｇの中にあるが、例外として、図５の（特殊レジスタ状態空間．ｓｒｅｇの中にある）特殊レジスタをオペランドとして使用することができる。
【０１０７】
[0124]表８００の算術演算のリストは、４つの基本的算術演算を含む。即ち、加算（ａｄｄ）、減算（ｓｕｂ）、乗算（ｍｕｌ）、及び除算（ｄｉｖ）である。これらの演算は、整数及び浮動小数点データの全ての型で実行可能であり、入力と同じ型の結果を作成する。幾つかの実施形態において、丸めモード修飾子を命令に付加し、結果をどのように丸め、整数オペランドの場合に飽和限度を課すべきかどうかをプログラマに特定させることができる。
【０１０８】
[0125]オペランドａ，ｂ，ｃを有する３複合算術演算もサポートされる。即ち、乗算・加算（ｍａｄ）、融合乗算・加算（ｆｍａ）、及び絶対差分合計（ｓａｄ）である。乗算・加算は積ａ＊ｂを計算し（丸めは括弧で指示される）、結果にｃを加える。融合乗算・加算はｍａｄとは異なり、ｃを加える前に積ａ＊ｂは丸められない。絶対差分合計は、絶対値｜ａ−ｂ｜を計算した後、ｃを加える。
【０１０９】
[0126]剰余（ｒｅｍ）演算は整数オペランド上でのみ実行され、オペランドａがオペランドｂによって割られるとき、剰余（ａ  ｍｏｄ  ｂ）を計算する。絶対値（ａｂｓ）及び否定（ｎｅｇ）は単項演算であって、浮動小数点又は符号付き整数形式のオペランドａへ適用できる。整数又は浮動小数点オペランドへ適用できる最小（ｍｉｎ）及び最大（ｍａｘ）演算は、より小さいオペランド、又はより大きいオペランドへ、デスティネーション・レジスタを設定する。１つ又は双方のオペランドが、（例えば、ＩＥＥＥ７５４標準に従って）非正規数である特殊ケースも、特定されてもよい。
【０１１０】
[0127]表８００内の残りの演算は、浮動小数点型についてのみ行われる。端数（ｆｒｃ）演算は、その入力の端数部分を返す。正弦（ｓｉｎ）、余弦（ｃｏｓ）、及び比の逆正接（ａｔａｎ２）は、三角関数に対応する便利な命令を提供する。底２の対数（ｌｇ２）及び累乗法（ｅｘ２）もサポートされる。逆数（ｒｃｐ）、平方根（ｓｑｒｔ）、及び逆平方根（ｒｓｑｒｔ）もサポートされる。
【０１１１】
[0128]算術演算のこのリストは例であって、本発明を限定しないことに注意すべきである。他の演算又は演算の組み合わせがサポートされてもよく、それらの演算の中には、十分な頻度の呼び出しを期待される演算が含まれる。
【０１１２】
[0129]幾つかの実施形態において、仮想ＩＳＡは、更に、ベクトル演算を定義する。図８Ｂは、例示的仮想ＩＳＡによってサポートされるベクトル演算を列挙する表８１０である。ベクトル演算は、オペランド・ベクトルａ及びｂのスカラー点乗積ｄを計算する点乗積（ｄｏｔ）演算、オペランド・ベクトルａ及びｂのベクトル交差積ｄを計算する交差積（ｃｒｏｓｓ）演算、及びオペランド・ベクトルａのスカラー長ｄを計算する量（ｍａｇ）演算を含む。ベクトル簡約（ｖｒｅｄ）演算は、ベクトル・オペランドａの要素を横切って特定演算＜ｏｐ＞を反復して行うことによってスカラー結果ｄを計算する。１つの実施形態において、簡約演算ａｄｄ、ｍｕｌ、ｍｉｎ、及びｍａｘのみが、浮動小数点ベクトルに対してサポートされる。整数ベクトルについては、追加の簡約演算（例えば、下記で説明するように、ａｎｄ、ｏｒ、及びｘｏｒ）もサポートされてもよい。
【０１１３】
[0130]これらの演算に加えて、（図８Ｂには列挙されていない）他のベクトル演算、例えば、ベクトル加算、ベクトル・スケーリングなども、仮想ＩＳＡで定義されてもよい。
【０１１４】
[0131]前述したように、仮想アーキテクチャ３００の幾つかのハードウェア現実化は、ベクトル処理をサポートしないかも知れない。そのような現実化の仮想命令トランスレータ４１２は、有利には、スカラー機械命令の適切なシーケンスを生成して、これらの演算を行うように適応させられる。当業者は適切なシーケンスを決定することができよう。
【０１１５】
５．３．２．仮想命令−選択及びレジスタ設定
[0132]図８Ｃは、例示的仮想ＩＳＡ内で定義される選択及びレジスタ設定演算を列挙する表８２０である。任意の数値データ型の上で行うことのできるこれらの演算は、比較演算のアウトカムに基づいてデスティネーション・レジスタを設定する。基本的選択（ｓｅｌ）演算は、もしｃが非ゼロであればオペランドａを選択し、もしｃが０であれば、オペランドｂを選択する。比較及び設定（ｓｅｔ）は、オペランドａ及びｂの上で比較演算＜ｃｍｐ＞を行って比較結果ｔを生成し、次に比較結果ｔが真（〜０）であるか偽（０）であるかに基づいて、デスティネーション・レジスタｄをブールの真（〜０）又は偽（０）へ設定する。１つの実施形態において、許される比較演算＜ｃｍｐ＞は、等しい（もしａ＝ｂであれば、ｔは真である）、より大きい（もしａ＞ｂであれば、ｔは真である）、より小さい（もしａ＜ｂであれば、ｔは真である）、より大きいか等しい（もしａ≧ｂであれば、ｔは真である）、より小さいか等しい（もしａ≦ｂであれば、ｔは真である）、及び他の比較を含む。他の比較には、例えば、ａ及び／又はｂが数値であるか、又は無定義値であるかが含まれる。
【０１１６】
[0133]ｓｅｔｂ演算は、比較及び設定の変形であって、比較演算＜ｃｍｐ＞の結果ｔと第３のオペランドｃとの間で更なるブール演算＜ｂｏｐ＞を行う。ブール演算ｔ＜ｂｏｐ＞ｃの結果は、デスティネーション・レジスタｄがブールの真又は偽へ設定されるかどうかを決定する。１つの実施形態において、許されるブール演算＜ｂｏｐ＞は、ａｎｄ、ｏｒ、及びｘｏｒを含む（下記で説明する図８Ｃを参照）。ｓｅｔｐ演算はｓｅｔｂと類似しているが、例外は、２つの１ビット「述語」デスティネーション・レジスタが設定されることである。即ち、デスティネーション・レジスタｄ１はｔ＜ｂｏｐ＞ｃの結果へ設定され、デスティネーション・レジスタｄ２は（！ｔ）＜ｂｏｐ＞ｃの結果へ設定される。
【０１１７】
５．３．３．仮想命令−論理及びビット操作
[0134]図８Ｄは、例示的仮想ＩＳＡの中で定義される論理及びビット操作演算を列挙する表８３０である。ビットごとのブール演算ａｎｄ、ｏｒ、及びｘｏｒは、オペランドａ及びｂの各ビット上で特定演算を行い、レジスタｄ内の対応するビットを結果へ設定することによって行われる。ビットごとの否定（ｎｏｔ）演算は、オペランドａの各ビットを反転し、論理否定（ｃｎｏｔ）演算は、もしａが０（ブールの偽）であれば、デスティネーション・レジスタを１（ブールの真）へ設定し、そうでなければ０（ブールの偽）へ設定する。
【０１１８】
[0135]ビット・シフトは左シフト（ｓｈｌ）及び右シフト（ｓｈｒ）演算によってサポートされ、これらの演算はオペランドｂによって特定されたビット数だけオペランドａ内のビット・フィールドを左又は右へシフトする。符号付き形式の場合、右シフトは、有利には、符号ビットに基づいて先導ビットを充填し、符号が付いていない形式の場合、右シフトは先導ビットを０で充填する。
【０１１９】
５．３．４．仮想命令−形式変換
[0136]図８Ｅは、例示的仮想ＩＳＡで定義される形式変換演算を列挙する表８４０である。形式変換（ｃｖｔ）命令は、第１の型＜ａｔｙｐｅ＞のオペランドａを目標型＜ｄｔｙｐｅ＞の同値へ変換し、結果をデスティネーション・レジスタｄの中に記憶する。１つの実施形態において、有効な型は図６に列挙される。型のない値（．ｂ＜ｎ＞）は整数又は浮動小数点型との間で変換することはできない。形式変換命令の変形によって、プログラマは丸めモード＜ｍｏｄｅ＞を指定することができる。目標型として表現されたときに飽和する数の取り扱いも、指定されてもよい。
【０１２０】
５．３．５．仮想命令−データ移動及びデータ共有
[0137]図８Ｆは、例示的仮想ＩＳＡで定義されるデータ移動及びデータ共有命令を列挙する表８５０である。移動（ｍｏｖ）演算は、デスティネーション・レジスタｄを即値オペランドａの値へ設定するか、もしオペランドａがレジスタであれば、レジスタａの内容へ設定する。移動演算は、仮想レジスタ・タイプの状態空間、例えば、図７の．ｒｅｇ及び．ｓｒｅｇへ制限することができる。
【０１２１】
[0138]ロード（ｌｄ）命令は、メモリ内のソース場所からデスティネーション・レジスタｄへ値をロードする。デスティネーション・レジスタｄは、１つの実施形態において、仮想レジスタ（．ｒｅｇ）状態空間の中に存在しなければならない。．＜ｓｐａｃｅ＞修飾子は、ソース場所の状態空間を指定し、図７のアドレス可能状態空間、例えば、．ｒｅｇ及び．ｓｒｅｇ以外の空間へ限定されることができる（．ｒｅｇ及び．ｓｒｅｇ空間では、代わりに移動演算を使用することができる）。この実施形態における仮想アーキテクチャ３００はレジスタ間プロセッサであるから、ロード命令は、有利には、アドレス可能状態空間から仮想レジスタ．ｒｅｇ状態空間へ変数を転送するために使用され、変数はオペランドとして使用できるようになる。
【０１２２】
[0139]特有のソース場所は、様々な方法で定義され、異なるアドレス・モードをサポートするソース・パラメータ＜ｓｒｃ＞を使用して識別される。例えば、幾つかの実施形態において、ソース・パラメータ＜ｓｒｃ＞は、ｄの中に記憶される値を有する名前付きアドレス可能変数、ソース・アドレスを保持するレジスタへの参照、（即値オペランドとして供給される）オフセット値へ加えられるアドレスを保持するレジスタへの参照、又は即値絶対アドレスの任意の１つであってもよい。
【０１２３】
[0140]同様に、記憶（ｓｔ）演算は、ソース・レジスタａ内の値を、デスティネーション・パラメータ＜ｄｓｔ＞によって識別されたメモリ場所へ記憶する。１つの実施形態におけるソース・レジスタａは、．ｒｅｇ状態空間の中に存在しなければならない。デスティネーションは書き込み可能及びアドレス可能状態空間（例えば、図７の．ｌｏｃａｌ、．ｇｌｏｂａｌ、又は．ｓｈａｒｅｄ）の中に存在しなければならない。デスティネーション・パラメータ＜ｄｓｔ＞は、ロード命令のソース・パラメータ＜ｓｒｃ＞と同じように、様々な方法で定義されて異なるアドレス・モードをサポートすることができる。記憶命令は、例えば、レジスタからアドレス可能状態空間へ演算結果を転送するために使用できる。
【０１２４】
[0141]テクスチャ及びサーフェイス状態空間が提供される実施形態において、追加の仮想命令は、テクスチャ・メモリ状態空間（ｔｅｘ）から読み出し、サーフェイスメモリ状態空間から読み出し（ｓｕｌｄ）及び書き込む（ｓｕｓｔ）ために使用されてもよい。テクスチャ読み出しのオペランド（ｔ，ｘ，ｙ）は、テクスチャ識別（ｔ）及び座標（ｘ，ｙ）を指定する。同様に、サーフェイス読み出し又は書き込みのオペランド（ｓ，ｘ，ｙ）は、サーフェイス識別子（ｓ）及び座標（ｘ，ｙ）を指定する。
【０１２５】
[0142]ＣＴＡスレッドは、他のＣＴＡスレッドとデータを共有することによって、他のＣＴＡスレッドと協力してもよい。例えば、ＣＴＡ内のデータを共有するため、ＣＴＡスレッドはロード及び記憶仮想命令（並びに下記で説明するアトミック更新命令ａｔｏｍ）を使用して、ＣＴＡ単位仮想状態空間との間でデータを読み書きすることができる。こうして、１つのＣＴＡスレッドは、適切に定義されたデスティネーション・アドレスを有するｓｔ．ｓｈａｒｅｄ命令を使用して．ｓｈａｒｅｄ状態空間へデータを書き込むことができ、同じＣＴＡ内の他のＣＴＡスレッドは、続いてｌｄ．ｓｈａｒｅｄ命令内の同じアドレスを使用することによってデータを読み出すことができる。この後で説明する同期命令（例えば、ｂａｒ及びｍｅｍｂａｒ）は、ＣＴＡスレッドの全体でデータ共有演算の適切なシーケンス、例えば、データ作成ＣＴＡスレッドがデータを書き込み、その後でデータ消費ＣＴＡスレッドがデータを読み出すシーケンスを確保するために使用できる。同様に、ｓｔ．ｇｌｏｂａｌ及びｌｄ．ｇｌｏｂａｌ命令は、同じＣＴＡ内のＣＴＡスレッド、同じグリッド内のＣＴＡ、及び／又は同じアプリケーション内の異なるグリッド間で、協力してデータを共有するために使用できる。
【０１２６】
５．３．６．仮想命令−プログラム制御
[0143]図８Ｇは、例示的仮想ＩＳＡで提供されるプログラム制御演算を列挙する表８６０である。これらの制御演算は、当業者には良く知られていると思われるが、ログラマがプログラム実行をリダイレクトすることを可能にする。分岐（ｂｒａ）はプログラムの流れを目標場所＜ｔａｒｇｅｔ＞へリダイレクトする。幾つかの実施形態において、分岐目標は、仮想ＩＳＡコード内で英数字ラベルを目標命令の前に置き、このラベルを分岐命令の目標識別子＜ｔａｒｇｅｔ＞として使用することによって定義される。例えば、１つの実施形態において、
ｌａｂｅｌ：  ａｄｄ．ｉｎｔ３２  ｄ，ｖｒｌ，ｖｒ２；
は、ラベルｌａｂｅｌを有する分岐目標としてａｄｄ命令を識別する。次の命令、
ｂｒａ  ｌａｂｅｌ；
は、コード内のどこかにあって、ラベル付けされた命令へ実行をリダイレクトする。
【０１２７】
[0148]ｃａｌｌ及び返却（ｒｅｔ）命令は、関数及びサブルーチン呼び出しをサポートする。ｆｎａｍｅは関数又はサブルーチンを識別する。（１つの実施形態において、「サブルーチン」とは、単に返却値が無視される関数である。）関数ｆｎａｍｅは．ｆｕｎｃディレクティブを使用して宣言でき、関数を定義する仮想ＩＳＡコードも提供されてもよい。中括弧｛｝又は他のグループ記号は、関数又はサブルーチンを定義するコードを、他の仮想ＩＳＡコードから分離するために使用できる。
【０１２８】
[0149]関数の場合、パラメータ・リスト＜ｒｖ＞は、返却値をどこに記憶するかを識別するために指定できる。関数及びサブルーチンの両者において、入力引数は、引数リスト＜ａｒｇｓ＞で指定される。ｃａｌｌが実行されるとき、次の命令のアドレスが記憶され、ｒｅｔが実行されるとき、記憶されたアドレスへの分岐が取られる。
【０１２９】
[0150]ｅｘｉｔ命令は、この命令に遭遇したＣＴＡスレッドを終了させる。トラップ命令は、プロセッサ定義又はユーザ定義のトラップ・ルーチンを起動する。中断点（ｂｒｋｐｔ）命令は実行を一時停止し、例えば、デバッグ目的に有用である。無操作命令（ｎｏｐ）は、実行されたとき効果を有しない命令である。無操作命令は、例えば、どれほど遅れて次の演算が実行できるかを制御するために使用されてもよい。
【０１３０】
５．３．７．仮想命令−並列スレッド
[0151]図８Ｈは、本発明の実施形態に従った例示的仮想ＩＳＡで提供される明示並列仮想命令を列挙する表８７０である。これらの命令は、ＣＴＡ実行に望まれる協調的スレッド振る舞い、例えば、ＣＴＡスレッド間のデータ交換をサポートする。
【０１３１】
[0152]障壁（ｂａｒ）命令は、この命令に達するＣＴＡスレッドが、更なる命令を実行する前に待機すべきことを指示する。待機する時間は、（同じＣＴＡ内の）他の全ＣＴＡスレッドが同じ障壁命令に達するまでである。任意の数の障壁命令がＣＴＡプログラム内で使用されてもよい。１つの実施形態において、障壁命令は（どれほど多くの障壁が使用されようとも）パラメータを必要としない。なぜなら、どのスレッドも（ｎ＋１）番目の障壁へ進む前に、全てのＣＴＡスレッドがｎ番目の障壁に到達しなければならないからである。
【０１３２】
[0153]他の実施形態において、障壁命令は例えば、特定の障壁で待機すべきＣＴＡスレッドの数（又は特定のＣＴＡスレッドの識別子）を指定することによって、パラメータ化されても。
【０１３３】
[0154]更に他の実施形態は、「待機」及び「非待機」障壁の両者を提供する。待機障壁命令において、ＣＴＡスレッドは、他の関連性のあるＣＴＡスレッドも障壁に到達するまで待機する。非待機命令において、ＣＴＡスレッドは、このスレッドが到着したが、他のＣＴＡスレッドが到着する前に継続できることを指示する。所与の障壁において、幾つかのＣＴＡスレッドは、他のＣＴＡスレッドの非待機中に待機していてもよい。
【０１３４】
[0155]幾つかの実施形態において、ｂａｒ仮想命令は、共有メモリ状態空間を使用して、協力又はデータを共有しているＣＴＡスレッドを同期させるために使用されてもよい。例えば、（ＣＴＡスレッドの幾つか又は全部を含んでもよい）ＣＴＡスレッドのセットの各スレッドが、スレッド単位変数（例えば、．ｆｐ３２仮想レジスタ変数ｍｙＤａｔａ）の中で或るデータを作成し、セット内の他のＣＴＡスレッドによって、作成されたデータを読み出すと仮定する。命令シーケンスは、次のとおりである。
ｓｔ．ｓｈａｒｅｄ．ｆｐ３２  ｍｙＷｒｉｔｅＡｄｄｒｅｓｓ，ｍｙＤａｔａ；
ｂａｒ；
Ｉｄ．ｓｈａｒｅｄ．ｆｐ３２  ｍｙＤａｔａ，ｍｙＲｅａｄＡｄｄｒｅｓｓ；
ここで、ｍｙＷｒｉｔｅＡｄｄｒｅｓｓ及びｍｙＲｅａｄＡｄｄｒｅｓｓは、．ｓｈａｒｅｄ状態空間内のアドレスに対応するスレッド単位変数であり、上記の命令シーケンスは所望の振る舞いを提供する。各々のＣＴＡスレッドが、作成されたデータを共有メモリへ書き込んだ後、各々のＣＴＡスレッドは、全てのＣＴＡスレッドがデータを記憶してしまうまで待機し、次に共有メモリから（異なるＣＴＡスレッドによって書き込まれた可能性のある）データを読み出すように進行する。
【０１３５】
[0156]メモリ障壁（ｍｅｍｂａｒ）命令は、各々のＣＴＡスレッドの既に要求されたメモリ演算（又は少なくとも全ての書き込み演算）が完了されるまで各ＣＴＡスレッドが待機すべきことを指示する。この命令は、ｍｅｍｂａｒ命令の後で起こるメモリ・アクセスが、メモリ・アクセス前の書き込み演算の結果を見ることを保証する。１つの実施形態におけるｍｅｍｂａｒ命令は、任意的な状態空間名＜ｓｐａｃｅ＞を使用して、特定された状態空間を目標とするメモリ演算へｍｅｍｂａｒ命令の範囲を制限する。指定された状態空間は、メモリ状態空間でなければならない（例えば、．ｒｅｇ又は．ｓｒｅｇ状態空間であってはならない）。もし状態空間名が特定されなければ、ＣＴＡスレッドは、全てのメモリ状態空間を目標とする全ての係属演算が完了するまで待機する。
【０１３６】
[0157]アトミック更新（ａｔｏｍ）命令は、参照＜ｒｅｆ＞によって識別される共有変数ａへのアトミック更新（読み出し−修正−書き込み）を生じる。共有変数ａは任意の共有状態空間の中に存在可能であり、他のメモリ参照と同じように、様々なアドレス・モードが使用できる。例えば、＜ｒｅｆ＞は、名前付きアドレス可能変数ａ、変数ａのアドレスを保持するレジスタへの参照、変数ａを突き止めるため（即値オペランドとして供給される）オフセット値へ加えられるアドレスを保持するレジスタへの参照、又は変数ａの即値絶対アドレスの任意のものであってもよい。ＣＴＡスレッドは、共有状態空間場所からデスティネーション・レジスタｄへ変数ａをロードし、オペランドａ及び（演算に依存して）第２及び第３のオペランドｂ及びｃの上で行われる特定演算＜ｏｐ＞を使用して変数ａを更新し、更新結果は、＜ｒｅｆ＞によって識別される場所へ戻される。デスティネーション・レジスタｄは、ａの最初のロード値を保持する。ロード、更新、及び記憶演算はアトミックに行われ、第１のＣＴＡスレッドがアトミック更新を実行している間、他のＣＴＡスレッドが変数ａにアクセスしないように保証する。１つの実施形態において、変数ａは．ｇｌｏｂａｌ又は．ｓｈａｒｅｄ状態空間へ限定され、前述したロード及び記憶演算と同じやり方で指定されてもよい。
【０１３７】
[0158]幾つかの実施形態において、或る一部の演算のみがアトミック更新として行われもよい。例えば、１つの実施形態において、もしａが浮動小数点型であれば、次の演算＜ｏｐ＞のみが指定されてもよい。即ち、ａをｂへ加算する演算、ａ及びｂの最小値又は最大値でａを置換する演算、及び、もしａがｂに等しければａをｃで置換し、そうでなければａを不変のままに残す三項比較・交換演算である。整数ａの場合、追加の演算がサポートされてもよく、例えば、オペランドａ及びｂの間のビットごとのａｎｄ、ｏｒ、及びｘｏｒ、並びにオペランドａの増分又は減分である。他のアトミック演算、又は演算の組み合わせもサポートできる。
【０１３８】
[0159]ｖｏｔｅ命令は、ＣＴＡスレッドの既定のグループにわたってブール（例えば、型．ｂｌ）オペランドａに簡約演算，＜ｏｐ＞を行う。１つの実施形態において、仮想アーキテクチャは、ＣＴＡスレッドがＳＩＭＤグループの中で実行され、既定のグループがＳＩＭＤグループに対応することを指定する。他の実施形態において、ＣＴＡスレッドの他のグループは、仮想アーキテクチャ又はプログラマによって定義されてもよい。簡約演算＜ｏｐ＞は、グループ内のＣＴＡスレッドにわたるオペランドａの簡約、及び．＜ｏｐ＞修飾子によって特定された簡約演算に基づいて、結果の値ｄをブールの真又は偽の状態への設定を引き起こす。１つの実施形態において、許される簡約演算は次のとおりである。即ち、（１）．ａｌｌ。この場合、もしグループ内の全てのＣＴＡスレッドについてａが真であれば、ｄは真であり、そうでなければ偽である。（２）．ａｎｙ。この場合、もしグループ内の任意のＣＴＡスレッドについてａが真であれば、ｄは真である。（３）．ｕｎｉ。この場合、グループ内の全ての活動ＣＴＡスレッドについてａが同値（真又は偽）を有するならば、ｄは真である。
【０１３９】
５．３．８．仮想命令−断定実行（ｐｒｅｄｉｃａｔｅｄ  ｅｘｅｃｕｔｉｏｎ）
[0160]幾つかの実施形態において、仮想ＩＳＡは命令の断定実行をサポートする。断定実行において、ブールの「保護述語」値が命令に関連づけられ、実行時に保護述語が真であると評価される場合にのみ、命令が実行する。
【０１４０】
[0161]例示的仮想ＩＳＡにおいて、保護述語は任意の１ビット・ブール仮想レジスタ変数（本明細書ではＰで表記される）であってもよい。断定実行は、命令の操作符号の前に述語保護＠Ｐ又は非述語保護＠！Ｐを置くことによって示される。値は、例えば、表８２０（図８Ｃ）のｓｅｔｐ命令のように、ブール結果を作成する命令のデスティネーション・レジスタとしてＰを識別することによって、述語レジスタの中に確立される。＠Ｐ又は＠！Ｐ保護述語に出会うと、仮想プロセッサはＰレジスタを読み出す。＠Ｐ保護の場合、もしＰが真であれば、命令が実行され、真でなければ、命令は省略される。＠！Ｐ保護の場合、もしＰが偽であれば、命令は実行され、そうでなければ、省略される。述語Ｐは、断定命令に出会った各々のＣＴＡスレッドについて実行時に評価される。こうして、幾つかのＣＴＡスレッドは断定命令を実行してもよく、その間、他のＣＴＡスレッドは実行しない。
【０１４１】
[0162]幾つかの実施形態において、述語は、命令が実行するときに設定されてもよい。例えば、表８００〜８７０（図８Ａ〜図８Ｈ）の仮想命令の一部は、述語レジスタを出力として指定するパラメータを受け入れてもよい。そのような命令は、命令結果の或る特性に基づいて特定述語レジスタを更新する。例えば、述語レジスタは、算術演算の結果が特殊数値（例えば、ゼロ、無限大、又はＩＥＥＥ７５４浮動小数点演算の非数値）であるかどうか、などを指示するために使用されてもよい。
【０１４２】
６．仮想命令トランスレータ
[0163]図４を参照したとき言及したように、仮想命令トランスレータ４１２は特定のプラットフォーム・アーキテクチャを目標にする。仮想命令トランスレータ４１２は、図１のＣＰＵ１０２のようなプロセッサ上で実行するソフトウェア・プログラムとして実現可能であり、仮想ＩＳＡコード４１０を受け取り、それを目標ＩＳＡコード４１４へ翻訳する。目標ＩＳＡコード４１４は、仮想命令トランスレータ４１２が目標とする特定のプラットフォーム・アーキテクチャの上で（例えば、図１のＰＰＵ１２２によって）実行できる。仮想命令トランスレータ４１２は、仮想ＩＳＡコード４１０内で宣言された仮想変数を、プロセッサ・レジスタ、オンチップ・メモリ、オフチップ・メモリなどを含む利用可能な記憶装置上の場所にマップする。幾つかの実施形態において、仮想命令トランスレータ４１２は、仮想状態空間の各々を特定タイプの記憶装置の上にマップする。例えば、．ｒｅｇ状態空間はスレッド特有データ・レジスタの上、．ｓｈａｒｅｄ状態空間はプロセッサの共有可能メモリの上に、．ｇｌｏｂａｌ状態空間は、アプリケーション・プログラムに割り振られた仮想メモリの領域の上に、マップできる。以下同様である。他のマッピングも可能である。
【０１４３】
[0164]仮想ＩＳＡコード４１０内の仮想命令は機械命令へ翻訳される。１つの実施形態において、仮想命令トランスレータ４１２は、対応する機械命令が、ＣＴＡスレッドを実行するプロセッサの命令セットの中に存在するかどうかに依存して、各々の仮想ＩＳＡ命令を、対応する機械命令又は機械命令シーケンスへマップするように構成される。
【０１４４】
[0165]仮想命令トランスレータ４１２は、更に、ＣＴＡスレッドを目標プラットフォーム・アーキテクチャ内の「物理」スレッド又はプロセスの上にマップする。例えば、もし目標プラットフォーム・アーキテクチャが少なくともｎ０個の同時スレッドをサポートするならば、各々のＣＴＡスレッドは１つの物理スレッドの上にマップ可能であり、仮想命令トランスレータ４１２は、ｎ０個の一意の識別子を有するｎ０個のスレッドのために目標プラットフォーム４４０がコードを実行することを期待して、単一のＣＴＡスレッドのために仮想命令コードを生成することができる。もし目標プラットフォーム・アーキテクチャが、ｎ０個よりも少ないスレッドをサポートするならば、仮想命令トランスレータ４１２は、このコードがＣＴＡごとに一回実行されることを期待して、複数のＣＴＡスレッドに対応する命令を組み込んだ仮想ＩＳＡコード４１０を生成し、複数のＣＴＡスレッドを単一の物理スレッド又はプロセスへマップすることができる。
【０１４５】
[0166]具体的には、データ共有（例えば、．ｓｈａｒｅｄ又は．ｇｌｏｂａｌ状態空間にアクセスするロード、記憶、及びアトミック更新命令）及び／又は協調的スレッド振る舞い（例えば、障壁、アトミック更新、及び図８Ｈの他の命令）に関する仮想命令は、機械命令又は機械命令シーケンスへ翻訳される。ＣＴＡ実行に最適化される目標プラットフォーム・アーキテクチャは、有利には、ハードウェアでサポートされた障壁命令を含み、例えば、命令装置内にカウンタ及び／又はレジスタを用いて、障壁命令に到着したスレッドの数をカウントしてフラグを設定する。このフラグは、スレッドが障壁で待機している間、更なる命令がスレッドのために出されないように防止する。他の目標アーキテクチャは、スレッドの同期について直接のハードウェア・サポートを提供しないこともある。その場合、所望の振る舞いを作り出すために他のスレッド間通信手法（例えば、セマフォ、メモリ内の状況アレイなど）が使用可能である。
【０１４６】
[0167]断定命令も機械命令へ翻訳される。幾つかの場合、目標ハードウェアは断定実行を直接サポートする。他の場合、述語は、例えば、プロセッサ・レジスタに記憶されてもよい。レジスタに質問し断定命令の周りを条件的に分岐することによって所望の実行時振る舞いを作り出すため、条件付き分岐命令などが使用されてもよい。
【０１４７】
[0168]図９は、本発明の実施形態に従って仮想命令トランスレータを使用するプロセス９００の流れ図である。ステップ９０２では、プログラマがＣＴＡプログラム・コードを高級言語で書く。１つの実施形態において、ＣＴＡプログラム・コードは、単一のＣＴＡスレッドの所望される振る舞いを定義し、（ＣＴＡ  ＩＤ及び／又はグリッドＩＤを含む）スレッドＩＤをパラメータとして使用して、ＣＴＡスレッドの振る舞いの様相を定義又は制御してもよい。例えば、読み出されるか書き込まれる共有メモリの場所は、スレッドＩＤの関数として決定されてもよく、同じＣＴＡ内の異なるＣＴＡスレッドは、共有メモリ内の異なるメモリ場所との間で読み書きする。１つの実施形態において、ＣＴＡプログラム・コードはアプリケーション・プログラム・コード（例えば、図４のプログラム・コード４０２）の一部分として含まれる。ＣＴＡスレッド振る舞いを定義することに加えて、アプリケーション・プログラム・コードは、更に、ＣＴＡ及び／又はグリッドを定義し、入力及び出力データセットなどをセットアップすることができる。
【０１４８】
[0169]ステップ９０４では、コンパイラ（例えば、図４のコンパイラ４０８）が、高級言語コードから単一（仮想）ＣＴＡスレッドの振る舞いを定義する仮想ＩＳＡコードを生成する。もしコードがＣＴＡプログラム・コード及び他のコードの両者を含むならば、コンパイラ４０８はＣＴＡプログラム・コードを残りのコードから分離してもよく、これによりＣＴＡプログラム・コードのみを使用して仮想ＩＳＡコードを生成する。１つの言語で書かれたプログラム・コードを他の（仮想）言語へコンパイルする従来の手法が使用されてもよい。注意すべきは、生成されたコードは仮想言語であるから、コンパイラを特定のハードウェアへ束縛又は最適化する必要はないことである。コンパイラは、入力コードの特定のシーケンスから生成された仮想ＩＳＡコードを最適化できる（例えば、仮想ＩＳＡ命令の短いシーケンスを選好する）。仮想ＩＳＡ内のプログラム・コードは、ディスク上のメモリに記憶され、及び／又は多様なプラットフォーム・アーキテクチャへ配布されてもよい。そのようなアーキテクチャの中には、図３の仮想アーキテクチャ３００と物理的に類似しないアーキテクチャが含まれる。仮想ＩＳＡ内のコードは機械から独立しており、仮想命令トランスレータを利用できる任意の目標プラットフォーム上で実行できる。代替の実施形態において、プログラマがＣＴＡプログラム・コードを仮想ＩＳＡの中に直接書き込んでもよく、仮想ＩＳＡコードがプログラムによって自動的に生成されてもよい。もしプログラム・コードが最初に仮想ＩＳＡコードとして作られるならば、コンパイル・ステップ９０４は省略されてもよい。
【０１４９】
[0170]ステップ９０６では、仮想命令トランスレータ（例えば、図４のトランスレータ４１２）が仮想ＩＳＡコードを読み出し、目標プラットフォーム上で実行可能な目標ＩＳＡコードを生成する。コンパイラとは異なり、仮想命令トランスレータは特定の（現実）プラットフォーム・アーキテクチャを目標とし、有利には、このアーキテクチャ上で最良パフォーマンスを達成するように目標ＩＳＡコードを適応及び最適化するように構成される。目標アーキテクチャが少なくともｎ０個のスレッドをサポートする１つの実施形態では、ＣＴＡを実現化するためにｎ０個のスレッドの各々によって同時に実行可能な仮想命令トランスレータが目標スレッド・プログラムを生成する、他の実施形態において、仮想命令トランスレータは、ソフトウェア手法（例えば、命令シーケンス）を使用してｎ０個の同時スレッドをエミュレートする目標プログラムを生成する。各々の同時スレッドは、仮想ＩＳＡコードに対応する命令を実行する。トランスレータは、プログラムの導入時、プログラムの初期化中、又はプログラム実行のジャストインタイム時間に動作してもよい。
【０１５０】
[0171]ステップ９０８では、目標プラットフォーム内のプロセッサ（例えば、図１のＰＰＵ１２２）が、目標ＩＳＡコードを実行してデータを処理する。幾つかの実施形態において、ステップ９０８は、更に下記で説明するように、プロセッサの振る舞いを制御するために、コマンド及び状態パラメータをプロセッサへ供給することを含んでもよい。
【０１５１】
[0172]プロセス９００は例示であり、変形及び修正が可能であることが理解される。順次に起こるものとして説明されたステップは、並列に実行されてもよく、ステップの順序が変更されてもよく、ステップが修正又は組み合わせられてもよい。例えば、幾つかの実施形態において、プログラマは仮想ＩＳＡコードを生成するコンパイラの必要性を除いて仮想ＩＳＡを直接使用してＣＴＡプログラム・コードを書いてもよい。他の実施形態において、ＣＴＡプログラム・コードは大きなアプリケーション・プログラムの一部分として書かれる。この大きなアプリケーション・プログラムも、例えば、特定の問題を解くために実行されるＣＴＡ及び／又はＣＴＡグリッドの次元を定義するコードを含む。１つの実施形態において、ＣＴＡプログラムを記述するコード部分のみが仮想ＩＳＡコードへコンパイルされ、他の部分は他の（現実又は仮想の）命令セットへコンパイルされてもよい。
【０１５２】
[0173]他の実施形態では、１つの仮想命令トランスレータが、異なる目標プラットフォームに適応された目標コードの複数のバージョンを生成するように構成されてもよい。例えば、トランスレータは、高級言語（例えば、Ｃ）のプログラム・コード、ＰＰＵの機械コード、及び／又はソフトウェア手法を使用してＰＰＵの振る舞いをエミュレートするシングルコア又はマルチコアＣＰＵの機械コードを作成できる。
【０１５３】
７．仮想実行ドライバ
[0174]幾つかの実施形態において、仮想ＩＳＡコード４１０及び仮想命令トランスレータ４１２は、ＣＴＡの各スレッドのために実行されるＣＴＡプログラム・コードを生成するために使用される。図２Ａ〜図２Ｂのプログラミング・モデルに関して、ＣＴＡプログラムの指定は、各々のＣＴＡスレッド２０４のための処理タスクを定義する。モデルを完成するため、ＣＴＡ２０２の次元、グリッド内のＣＴＡの数、処理される入力データセット等を定義することも必要である。そのような情報は、本明細書では「ＣＴＡ制御情報」と呼ばれる。
【０１５４】
[0175]図４で示されるように、幾つかの実施形態において、アプリケーション・プログラム４０２は、仮想ライブラリ４０４内の関数への呼び出しを使用することによって、ＣＴＡ制御情報を指定する。１つの実施形態において、仮想ライブラリ４０４は様々な関数呼び出しを含み、プログラマは関数呼び出しを介してＣＴＡ又はＣＴＡグリッドを定義し、いつ実行を開始するかを指示することができる。
【０１５５】
[0176]図１０は、例示的仮想ライブラリ４０４で利用可能な関数を列挙する表１０００である。関数の第１のグループはＣＴＡの定義に関する。具体的には、ｉｎｉｔＣＴＡ関数は新しいＣＴＡを作るために呼び出される最初の関数である。この関数によって、プログラマはＣＴＡの次元（ｎｔｉｄ．ｘ，ｎｔｉｄ．ｙ，ｎｔｉｄ．ｚ）を定義し、新しいＣＴＡへ識別子ｃｎａｍｅを割り当てることができる。ｓｅｔＣＴＡＰｒｏｇｒａｍ関数は、ＣＴＡ  ｃｎａｍｅの各スレッドによって実行されるＣＴＡプログラムを指定する。パラメータｐｎａｍｅは、所望のＣＴＡプログラム（例えば、仮想ＩＳＡコードのプログラム）に対応する論理プログラム識別子である。ｓｅｔＣＴＡＩｎｐｕｔＡｒｒａｙ関数は、プログラマが、ＣＴＡｃｎａｍｅが入力データを読み出すグローバルメモリ内のソース場所（開始アドレス及びサイズ）を指定できるようにし、ｓｅｔＣＴＡＯｕｔｐｕｔＡｒｒａｙ関数は、プログラマが、ＣＴＡ  ｃｎａｍｅが出力データを書き込むグローバルメモリ内の目標場所（開始アドレス及びサイズ）を指定できるようにする。ｓｅｔＣＴＡＰａｒａｍｓ関数は、ＣＴＡ  ｃｎａｍｅのためにランタイム定数パラメータを設定するために使用される。プログラマは、パラメートのリストを、例えば、（名前、値）の対として、関数へ提供する。
【０１５６】
[0177]１つの実施形態において、ｓｅｔＣＴＡＰａｒａｍｓ関数は、更に、仮想ＩＳＡコード４１０を生成するとき、コンパイラ４０８によって使用されてもよい。ｓｅｔＣＴＡＰａｒａｍｓ関数はＣＴＡのためにランタイムパラメータを定義するので、コンパイラ４０８は、この関数が各々のパラメータを．ｐａｒａｍ状態空間内の仮想変数として定義するものと解釈することができる。
【０１５７】
[0178]表１０００は、更に、ＣＴＡグリッドの定義に関する関数を列挙する。ｉｎｉｔＧｒｉｄ関数は、新しいグリッドを作るために呼び出される最初の関数である。この関数によって、プログラマは、グリッドの次元（ｎｃｔａｉｄ．ｘ，ｎｃｔａｉｄ．ｙ，ｎｃｔａｉｄ．ｚ）を定義し、グリッド上で実行されるＣＴＡ  ｃｎａｍｅを認識し、新しく定義されたグリッドへ識別子ｇｎａｍｅを割り当てることができる。ｓｅｔＧｒｉｄＩｎｐｕｔＡｒｒａｙ及びｓｅｔＧｒｉｄＯｕｔｐｕｔＡｒｒａｙ関数は、ＣＴＡレベル関数と類似しており、単一の入力及び／又は出力アレイがグリッド内の全ＣＴＡの全スレッドのために定義されることを可能にする。ｓｅｔＧｒｉｄＰａｒａｍｓ関数は、グリッドｇｎａｍｅ内の全ＣＴＡのためにランタイム定数パラメータを設定するために使用される。コンパイラ４０８は、この関数が．ｃｏｎｓｔ状態空間内の仮想変数として各パラメータを定義するものと解釈することができる。
【０１５８】
[0179]ｌａｕｎｃｈＣＴＡ及びｌａｕｎｃｈＧｒｉｄ関数は、特定されたＣＴＡ  ｃｎａｍｅ又はグリッドｇｎａｍｅの実行を開始すべきことを知らせる。
【０１５９】
[0180]仮想ＡＰＩは、更に、他の関数を含んでもよい。例えば、幾つかの実施形態は、複数ＣＴＡの実行を調整するために使用可能な同期関数を提供する。例えば、もし第１のＣＴＡ（又はグリッド）の出力が第２のＣＴＡ（又はグリッド）の入力として使用されるのであれば、ＡＰＩは関数（又はｌａｕｎｃｈ関数のパラメータ）を含んでもよく、この関数を介して、仮想実行ドライバに、第１のＣＴＡ（又はグリッド）の実行が完了するまで、第２のＣＴＡ（又はグリッド）が起動されるべきでないことを指令できる。
【０１６０】
[0181]本発明の実施形態によれば、表１０００の関数呼び出しのいずれか又は全部が、アプリケーション・プログラムの中に含められてもよい。このアプリケーション・プログラムも、実行されるＣＴＡプログラム（又は、もしアプリケーション内に複数のＣＴＡが存在するならば、複数のプログラム）を定義する。コンパイル時に、関数呼び出しはアプリケーション・プログラム・インタフェース（ＡＰＩ）ライブラリ４０４への呼び出しとして処置され、仮想ＡＰＩコード４０６を生成する。
【０１６１】
[0182]仮想ＡＰＩコードは、仮想ライブラリ内の各関数を実現する仮想実行ドライバ４１８を使用して現実化される。１つの実施形態において、仮想実行ドライバ４１８は、ＣＴＡスレッドを現実化するＰＰＵ１２２を制御する図１のＣＰＵ１０２上で実行するドライバ・プログラムである。図１０の表１０００内の様々な関数呼び出しは、ドライバがプッシュバッファを介してコマンドをＰＰＵ１２２へ提供するように実現される。他の実施形態において、ＣＰＵは１つ又は複数のプログラムを実行してＣＴＡを現実化し、仮想実行ドライバ４１８はパラメータをセットアップして、ＣＰＵによるそのようなプログラムの実行を制御する。
【０１６２】
[0183]本明細書で説明される仮想ＡＰＩは例であって、変形及び修正が可能であることが理解される。他の関数、又は関数の組み合わせがサポートされることは可能である。当技術分野で公知の仮想ＡＰＩ手法が、本発明の目的に適応可能である。
【０１６３】
更なる実施形態
[0184]本発明は特有の実施形態に関して説明されたが、当業者は多数の変更が可能であることを認識する。例えば、本明細書で説明される特有の仮想アーキテクチャ、仮想命令、及び仮想ＡＰＩ関数は必要でなく、同時の協調的スレッドをサポートする他の仮想のアーキテクチャ、命令、及び／又は関数が置き換えられることが可能である。更に、これまで説明された実施形態は、全てのブロックが同数の要素を有し、全てのＣＴＡが同数のスレッドを有して同じＣＴＡプログラムを実行する、などの場合を基準としてもよい。幾つかのアプリケーションにおいて、例えば、複数の従属グリッドが使用される場合、プログラムを実行する異なるグリッド内のＣＴＡを、又は異なる数及び／又はサイズのグリッドを有することが望ましいかも知れない。
【０１６４】
[0185]本明細書では「協調的スレッド・アレイ」を基準としたが、幾つかの実施形態は、同時スレッド間のデータ共有がサポートされないスレッド・アレイを使用できることを理解すべきである。そのようなデータ共有がサポートされる他の実施形態において、所与のアプリケーションについて定義されたスレッドは、データを実際に共有しても共有しなくてもよい。
【０１６５】
[0186]更に、これまで説明された実施形態は、複数のスレッドを有するスレッド・アレイを基準にしたが、「退化した」場合、スレッド・アレイは１つだけのスレッドを有してもよいことを理解すべきである。こうして、本発明は、１つ又は複数のシングルスレッド・コア又はマルチスレッド・コアを有するＣＰＵ上で実行されるプログラムの拡張性を提供するように応用可能である。本明細書で説明された手法を使用して、スレッドが任意の数の利用可能なＣＰＵコアに分散可能な仮想ＩＳＡコードの変更又は再コンパイルを必要仕方で、（例えば、オペレーティング・システムの機能を使用して）仮想ＩＳＡコードの変更又は再コンパイルを必要としないプログラムを書くことができる。
【０１６６】
[0187]「仮想」及び「現実」の用語は、本明細書において、問題の解法を記述するためプログラマによって使用される概念的プログラミング・モデルの、プログラムが究極的に実行できる実際のコンピュータ・システムからの切り離しを反映するために使用される。「仮想」プログラミング・モデル及びその関連アーキテクチャによって、プログラマは並列処理タスクの高レベル観察を得ることができ、コンポーネントが本明細書で説明された仮想アーキテクチャ・コンポーネントと１対１でマップする実際のコンピューティング・システム又はデバイスは、存在しても存在しなくてもよいことを理解すべきである。仮想ＩＳＡコード及び仮想ＡＰＩコードを含む仮想コードは、有利には、実際の処理デバイスの命令セットと１対１に対応しても対応しなくてもよい言語のコードとして現実化される。全てのプログラム・コードと同じように、本明細書で参照される仮想コードは、有形メディア（例えば、メモリ又はディスク）に記憶され、ネットワークで送信され、その他同様の取り扱いを受けることができる。
【０１６７】
[0188]仮想ＩＳＡ及び／又は仮想ＡＰＩコード、仮想命令トランスレータ、仮想ドライバ、コンパイラ、仮想関数ライブラリなどを含むが、これらに限定されない、本発明の様々な特徴を組み込んだコンピュータ・プログラムは、記憶及び／又は伝送のために様々なコンピュータ読み取り可能メディアの上に符号化されてもよい。適切なメディアは、磁気ディスク又はテープ、光記憶メディア、例えば、コンパクト・ディスク（ＣＤ）、又はＤＶＤ（ディジタル万能ディスク）、フラッシュ・メモリなどを含む。そのようなプログラムは、更に、インターネットを含む多様なプロトコルに合致する有線、光、及び／又は無線ネットワークを介して伝送されるように適応した搬送波信号を使用して、符号化及び伝送されてもよい。プログラム・コードを符号化されたコンピュータ読み取り可能記憶メディアは、互換性デバイスと共にパッケージされてもよく、また、プログラム・コードは他のデバイスとは別個に（例えば、インターネットのダウンロードを介して）提供されてもよい。
【０１６８】
[0189]更に、或る一部の行動は、本明細書では「プログラマ」によって取られると説明されてもよい。プログラマは、人間であるか、人間の介入を殆ど又は全く受けないでプログラム・コードを生成する自動プロセスであるか、プログラム・コードを生成するために、自動又は部分的自動プロセスと、交信する人間との組み合わせであることが考えられる。
【０１６９】
[0190]更に、本明細書で説明される実施形態は、特定の目標プラットフォームの特徴を基準にするが、本発明はこのようなプラットフォームに限定されない。実際に、仮想アーキテクチャはハードウェア及び／又はソフトウェア・コンポーネントの任意の組み合わせで現実化可能である。同じ仮想アーキテクチャの異なる現実化は、効率及び／又はスループットで異なることが想定できることを、当業者は理解する。しかし、そのような差異は本発明と無関係である。
【０１７０】
[0191]したがって、本発明は特定の実施形態に関して説明されたが、本発明は、続く請求の範囲内で全ての変更及び均等物を対象とするように意図されることが理解される。
【図面の簡単な説明】
【０１７１】
【図１】本発明の実施形態に従ったコンピュータ・システムのブロック図である。
【図２Ａ】本発明の実施形態で使用されるプログラミング・モデルのグリッド、スレッド・アレイ、及びスレッドの間の関係を図示する。
【図２Ｂ】本発明の実施形態で使用されるプログラミング・モデルのグリッド、スレッド・アレイ、及びスレッドの間の関係を図示する。
【図３】本発明の実施形態に従った仮想アーキテクチャのブロック図である。
【図４】本発明の実施形態に従って仮想アーキテクチャを使用し目標プロセッサを動作させる概念モデルである。
【図５】本発明の実施形態に従った仮想命令セット・アーキテクチャ（ＩＳＡ）によって定義される特殊変数を列挙する表である。
【図６】本発明の実施形態に従った仮想ＩＳＡの中でサポートされる変数型を列挙する表である。
【図７】本発明の実施形態に従った仮想ＩＳＡの中でサポートされる仮想状態空間を列挙する表である。
【図８Ａ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｂ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｃ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｄ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｅ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｆ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｇ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図８Ｈ】本発明の実施形態に従った仮想ＩＳＡの中で定義される仮想命令を列挙する表である。
【図９】本発明の実施形態に従った仮想命令トランスレータを使用するプロセスの流れ図である。
【図１０】本発明の実施形態に従って仮想実行ドライバのために仮想ライブラリの中で利用可能な関数を列挙する表である。
【符号の説明】
【０１７２】
１００…コンピュータ・システム、１０２…中央処理装置（ＣＰＵ）、１０４…システム・メモリ、１０５…メモリ・ブリッジ、１０６…通信経路、１０７…入力／出力ブリッジ、１０８…ユーザ入力デバイス、１１０…ディスプレイ、１１２…並列処理サブシステム、１１３…他の通信経路、１１４…システム・ディスク、１１６…スイッチ、１１８…ネットワーク・アダプタ、１２０…アドイン・カード、１２１…アドイン・カード、１２２…並列処理装置（ＰＰＵ）、１２４…並列処理（ＰＰ）メモリ、２００…グリッド、２００（０）…グリッド、２００（１）…グリッド、２００（２）…グリッド、２０２…スレッド・アレイ、２０２（０，０）…協調的スレッド・アレイ、２０２（０，１）…協調的スレッド・アレイ、２０２（０，２）…協調的スレッド・アレイ、２０２（１，０）…協調的スレッド・アレイ、２０２（１，１）…協調的スレッド・アレイ、２０２（２，０）…協調的スレッド・アレイ、２０４…スレッド、２０４（０，０）…スレッド、２０４（０，１）…スレッド、２０４（０，２）…スレッド、２０４（１，０）…スレッド、２０４（１，１）…スレッド、２０４（２，０）…スレッド、３００…仮想アーキテクチャ、３０２…仮想プロセッサ、３０４…グローバルメモリ、３０６…フロントエンド、３０８…仮想コア、３１０…仮想処理エンジン、３１１…特殊レジスタ、３１２…仮想命令装置、３１４…ローカルレジスタ、３１６…共有メモリ、３１８…パラメータ・メモリ、３２０…仮想ドライバ、３２２…メモリ・インタフェース、４００…概念的モデル、４０２…アプリケーション・プログラム、４０４…ライブラリ、４０６…仮想ＡＰＩコード、４０８…コンパイラ、４１０…仮想ＩＳＡコード、４１２…仮想命令トランスレータ、４１４…目標ＩＳＡコード、４１６…仮想実行ドライバ、４１８…目標ＡＰＩコマンド、４３０…命令装置、４３２…並列処理装置ドライバ、４３４…フロントエンド、４４０…目標プロセッサ又は目標プラットフォーム、５００…特殊変数の表、６００…変数型の表、７００…仮想状態空間の表、８００…算術演算の表、８１０…ベクトル演算の表、８２０…選択及びレジスタ設定演算の表、８３０…論理及びビット操作演算の表、８４０…形式変換演算の表、８５０…データ移動及びデータ共有命令の表、８６０…プログラム制御演算の表、８７０…明示並列仮想命令の表、９００…仮想命令トランスレータの使用プロセス、１０００…仮想ライブラリで利用できる関数の表、ＡＰＩ…アプリケーション・プログラム・インタフェース（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍ  ｉｎｔｅｒｆａｃｅ）、ＣＴＡ…協調的スレッド・アレイ（ｃｏｏｐｅｒａｔｉｖｅ  ｔｈｒｅａｄ  ａｒｒａｙ）、ＩＳＡ…命令セット・アーキテクチャ（ｉｎｓｔｒｕｃｔｉｏｎ  ｓｅｔ  ａｒｃｈｉｔｅｃｔｕｒｅ）、ＰＰ…並列処理（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｉｎｇ）、ＰＰＵ…並列処理装置（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）
【図１】
2008276740.tif 000003
【図２Ａ】
2008276740.tif 000004
【図２Ｂ】
2008276740.tif 000005
【図３】
2008276740.tif 000006
【図４】
2008276740.tif 000007
【図５】
2008276740.tif 000008
【図６】
2008276740.tif 000009
【図７】
2008276740.tif 000010
【図８Ａ】
2008276740.tif 000011
【図８Ｂ】
2008276740.tif 000012
【図８Ｃ】
2008276740.tif 000013
【図８Ｄ】
2008276740.tif 000014
【図８Ｅ】
2008276740.tif 000015
【図８Ｆ】
2008276740.tif 000016
【図８Ｇ】
2008276740.tif 000017
【図８Ｈ】
2008276740.tif 000018
【図９】
2008276740.tif 000019
【図１０】
2008276740.tif 000020
【外国語明細書】
2008276740000001.pdf