同期並列スレッドプロセッサにおける間接的な関数呼び出し命令
【課題】関数ポインタを使用して間接的な関数呼び出しを行えるようにするSIMTアーキテクチャーを提供する。
【解決手段】間接的な分岐命令は、単一命令複数スレッド(SIMT)プロセッサアーキテクチャーに対する間接的な関数呼び出し能力を与えるためにアドレスレジスタを引数としてみなす。間接的な分岐命令は、間接的な関数呼び出し、バーチャルな関数呼び出し、及びスイッチステートメントを実施して、テスト及び分岐の逐次チェーンの使用に比して処理性能を改善するのに使用される。
【解決手段】間接的な分岐命令は、単一命令複数スレッド(SIMT)プロセッサアーキテクチャーに対する間接的な関数呼び出し能力を与えるためにアドレスレジスタを引数としてみなす。間接的な分岐命令は、間接的な関数呼び出し、バーチャルな関数呼び出し、及びスイッチステートメントを実施して、テスト及び分岐の逐次チェーンの使用に比して処理性能を改善するのに使用される。
【発明の詳細な説明】
【技術分野】
【0001】
[0001]本発明は、一般的に、グラフィック処理に係り、より詳細には、単一命令複数スレッド(SIMT:a single-instruction, multiple-thread)アーキテクチャーにおいて関数ポインタを通して関数及びサブルーチンを間接的に呼び出すことができるようにするシステム及び方法に係る。
【背景技術】
【0002】
[0002]現在のグラフィックデータ処理は、例えば、線型補間(linear interpolation)、テッセレーション(tessellation)、ラスタ化(rasterization)、テクスチャマッピング(texture mapping)、デプステスティング(depth testing)、等、の特定のオペレーションをグラフィックデータに対して遂行するように開発されたシステム及び方法を含む。慣習的に、グラフィックプロセッサは、固定関数計算ユニットを使用してグラフィックデータを処理しているが、最近では、グラフィックプロセッサの各部分がプログラム可能とされ、このようなプロセッサで、頂点及び断片データを処理するための種々様々なオペレーションをサポートすることができる。
【0003】
[0003]性能を更に高めるために、グラフィックプロセッサは、典型的に、パイプラインのような処理技術を実施し、グラフィックパイプラインの異なる部分全体にわたりできるだけ多くのグラフィックデータを並列に処理するように試みている。SIMD(single-instruction multiple-data:単一命令複数データ)アーキテクチャーをもつグラフィックプロセッサは、グラフィックパイプラインにおける並列処理量を最大にするように設計される。SIMDアーキテクチャーでは、複数のデータ入力を処理するために、同じ命令が並列に実行される。単一命令複数スレッド(SIMT)のアーキテクチャーは、SIMDアーキテクチャーより高い融通性を与える。というのは、スレッドグループ内のスレッドが、複数のデータ入力を処理するために命令のセットを通して異なる経路をたどれるからである。SIMD命令は、複数データ入力のベクトルに対してオペレーションを制御する単一制御スレッドの実行及び分岐振舞いを指定する。対照的に、SIMT命令は、そのデータ入力に対して動作する1つの個々の独立スレッドの実行及び分岐振舞いを指定し、又、SIMTアーキテクチャーは、独立して自由に実行及び分岐する複数の独立スレッドにSIMT命令を並列に適用する。処理効率を改善するために、進歩型制御フローには、スレッドが独立して分岐できる条件付きブレーク及びリターン命令が使用される。特に、ブレーク又はリターンを実行するスレッドは、ブレーク又はリターンを実行しないスレッドより早くに処理を完了することができる。条件付き命令の実行中に発散したスレッドは、次いで、それらスレッドが並列に実行されるように同期される。現在のSIMTアーキテクチャーは、各個々のスレッドが異なるポインタ値を有するような関数ポインタを通して関数及びサブルーチンを間接的に呼び出す能力を備えていない。Cのような多数のプログラミング言語は、間接的な関数呼び出しを有し、又、C++のような他のものは、バーチャルな関数を有し、どちらも、プロセッサがポインタを経て間接的に関数を呼び出す能力を与える必要がある。テスト及び分岐の逐次チェーンに比して処理性能を改善するために、間接的分岐及び間接的分岐テーブルが使用される。
【発明の概要】
【発明が解決しようとする課題】
【0004】
[0004]従って、この技術では、関数ポインタを使用して間接的な関数呼び出しを行えるようにするSIMTアーキテクチャーが要望されている。
【課題を解決するための手段】
【0005】
[0005]間接的な分岐命令は、同期並列スレッドプロセッサアーキテクチャーに対する間接的関数呼び出し能力を与えるためにアドレスレジスタを引数としてみなす。同期並列スレッドアーキテクチャーは、SIMD又はSIMTプロセッサとして機能するように構成できる。テスト及び分岐の逐次チェーンを使用するものに比して処理性能を改善する間接的分岐及び間接的分岐テーブルを実施するために間接的分岐命令が使用される。重要なことに、本発明は、スレッドが同じ分岐経路又は関数呼び出し経路をとるとき及びそれらが発散(diverging)分岐及び関数呼び出しからリターンするときにスレッドグループ内の複数のスレッドを並列に実行できるようにしながら、スレッドグループ内の個々のスレッドがスレッドグループ内の他のスレッドとは独立して分岐するための実行モデルを提供する。
【0006】
[0006]並列処理ユニットは、条件付き制御命令の実行中に1つ以上のスレッドが発散するかどうか決定するステップを遂行するように構成される。制御命令は、同期、ブレーク及びリターンのためのスレッド処理ターゲットアドレスを設定するのに使用される。プログラムを退出するスレッドは、ディセーブルマスクによりアイドルと識別される。事象を待機する間にディセーブルされる他のスレッドは、発散スレッドが事象に到着すると、イネーブルすることができる。ディセーブルマスクの使用は、マルチスレッドSIMTアーキテクチャーにおいて条件付きリターン及びブレーク命令の使用を許す。
【0007】
[0007]同期並列スレッドプロセッサにおいて間接的関数呼び出しを実行するための本発明の方法の種々の実施形態は、1つ以上の関数に対してポインタのセットを参照する第1の制御命令を受け取ることを含み、それらのポインタは、プログラムにおいて前記関数のアドレスを指定する。この方法は、次いで、スレッドグループ内のアクティブなスレッドに対応するポインタの2つが異なるものであって、アクティブなスレッドが同期並列スレッドプロセッサにおける前記間接的な関数呼び出しの実行中に発散することを指示するかどうか決定する。アクティブなスレッドが発散する場合には、第1の制御命令のアドレスを含む第1トークンが実行スタックにプッシュされる。第1関数のアドレスを指定するようにアクティブなプログラムカウンタが更新される。
【0008】
[0008]本発明の種々の実施形態は、同期並列処理スレッドに対して間接的な関数呼び出しを実行するためのシステムを含む。このシステムは、実行スタック、コントローラ、及び複数の処理エンジンを備えている。実行スタックは、システムにより同時に実行される多数のスレッドに対してスレッド状態情報を記憶するように構成される。実行スタックに結合されて、制御命令を含むプログラム命令を受け取るように構成されたコントローラは、スレッド状態情報をプッシュ及びポップすることにより制御命令を実行し、並列に処理されねばならないスレッドグループ内のアクティブなスレッドを指示するアクティブなマスクを維持し、且ついずれかのアクティブなスレッドに対応する各独特のポインタに対して間接的な関数呼び出しの実行を直列化する。複数の処理エンジンは、プログラム命令を受け取り、そしてアクティブなマスクに基づき並列に処理されねばならないスレッドグループ内のスレッドに対して各プログラム命令を並列に実行するように構成される。
【0009】
[0009]上述した本発明の特徴を詳細に理解できるように、前記で簡単に要約した本発明について、幾つかを添付図面に例示した実施形態を参照して、より詳細に説明する。しかしながら、添付図面は、本発明の典型的な実施形態を例示するに過ぎず、それ故、本発明の範囲をそれに限定するものではなく、本発明は、同等の効果を発揮できる他の実施形態も包含できるものであることに注意されたい。
【図面の簡単な説明】
【0010】
【図1】本発明の1つ以上の態様を実施するように構成されたコンピュータシステムを示すブロック図である。
【図2】本発明の1つ以上の態様に基づく図1のコンピュータシステムのための並列処理サブシステムのブロック図である。
【図3】本発明の1つ以上の態様に基づく図2の並列処理サブシステムのための並列処理ユニットのブロック図である。
【図4A】本発明の1つ以上の態様に基づく図3の並列処理ユニットのための命令ユニットのブロック図である。
【図4B】本発明の1つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図4C】本発明の1つ以上の態様に基づき関数ポインタを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図5A】本発明の1つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。
【図5B】本発明の1つ以上の態様に基づき一連のプログラム命令の実行中に実行スタックをアンワインドする(unwinding)ための方法ステップのフローチャートである。
【図6】本発明の1つ以上の態様に基づきプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す概念図である。
【図7】本発明の1つ以上の態様に基づき条件付きリターンを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す別の概念図である。
【図8】本発明の1つ以上の態様に基づき間接的な関数呼び出しを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す別の概念図である。
【発明を実施するための形態】
【0011】
[0021]以下の説明では、本発明をより完全に理解するために多数の特定の細部について説明する。しかしながら、当業者であれば、これらの特定の細部の1つ以上がなくても、本発明を実施できることが明らかであろう。他の点について、本発明を不明瞭にしないために、良く知られた特徴は、説明しない。
[システムの概略]
【0012】
[0022]図1は、本発明の1つ以上の態様を実施するように構成されたコンピュータシステム100を示すブロック図である。このコンピュータシステム100は、メモリブリッジ105を含むバス経路を経て通信する中央処理ユニット(CPU)102及びシステムメモリ104を備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ105は、バス又は他の通信経路106(例えば、ハイパートランスポートリンク)を経てI/O(入力/出力)ブリッジ107に接続される。例えば、サウスブリッジ(Southbridge)チップでよいI/Oブリッジ107は、1つ以上のユーザ入力装置108(例えば、キーボード、マウス)からユーザ入力を受け取り、そしてその入力を、経路102及びメモリブリッジ105を経てCPU102へ転送する。メモリブリッジ105には、バス又は他の通信経路113(例えば、PCIエクスプレス、アクセラレーテッドグラフィックポート又はハイパートランスポートリンク)を経て並列処理サブシステム112が結合され、一実施形態では、この並列処理サブシステム112は、ディスプレイ装置110(例えば、従来のCRT又はLCDベースのモニタ)へピクセルを配送するグラフィックサブシステムである。I/Oブリッジ107には、システムディスク114も接続される。スイッチ116は、I/Oブリッジ107と、他のコンポーネント、例えば、ネットワークアダプタ118及び種々のアドイン(add-in)カード120及び121との間の接続をなす。又、I/Oブリッジ107には、USB又は他のポート接続部、CDドライブ、DVDドライブ、フィルムレコーディング装置、等を含む他のコンポーネント(明確に示さず)を接続することもできる。図1における種々のコンポーネントを相互接続する通信経路は、適当なプロトコル、例えば、PCI(周辺コンポーネント相互接続)、PCI−エクスプレス(PCI−E)、AGP(アクセラレーテッドグラフィックポート)、ハイパートランスポート、或いは他のバス又はポイント・ツー・ポイント通信プロトコルを使用して実施することができ、そして異なる装置間の接続は、この技術で知られたように異なるプロトコルを使用することができる。
【0013】
[0023]一実施形態では、並列処理サブシステム112は、例えば、ビデオ出力回路を含めて、グラフィック及びビデオ処理に最適な回路を組み込んでおり、そしてグラフィック処理ユニット(GPU)を構成する。別の実施形態では、並列処理サブシステム112は、以下に詳細に述べる、基礎となる計算アーキテクチャーを保存しながら、汎用の処理に最適な回路を組み込んでいる。更に別の実施形態では、並列処理サブシステム112は、1つ以上の他のシステムエレメント、例えば、メモリブリッジ105、CPU102、及びI/Oブリッジ107と一体化されて、システムオンチップ(SoC)を形成することができる。
【0014】
[0024]図2は、本発明の一実施形態に基づく並列処理サブシステム112を示す。この並列処理サブシステム112は、1つ以上の並列処理ユニット(PPU)202を備え、その各々は、ローカル並列処理(PP)メモリ204に結合される。一般的に、並列処理サブシステムは、多数UのPPUを含み、但し、U≧1である。(ここで、同じオブジェクトの複数のインスタンスは、オブジェクトを識別する参照番号と、必要に応じてインスタンスを識別するカッコ内の数字とで示される。)PPU202及びPPメモリ204は、例えば、プログラム可能なプロセッサ、特定用途向け集積回路(ASIC)、及びメモリ装置のような1つ以上の集積回路装置を使用して実施することができる。
【0015】
[0025]PPU202(0)について詳細に示すように、各PPU202は、メモリブリッジ105へ接続される(又は別の実施形態では、CPU102へ直結される)通信経路113を経てシステム100の残り部分と通信するホストインターフェイス206を備えている。一実施形態では、通信経路113は、この技術で知られたように、各PPU202に専用レーンが割り当てられるPCI−Eリンクである。又、他の通信経路が使用されてもよい。ホストインターフェイス206は、通信経路113へ送信するためにパケット(又は他の信号)を発生し、又、通信経路113から全ての到来パケット(又は他の信号)も受信して、それをPPU202の適当なコンポーネントへ向ける。例えば、処理タスクに関連したコマンドをフロントエンドユニット212に向ける一方、メモリオペレーション(例えば、PPメモリ204からの読み取り又はそこへの書き込み)に関連したコマンドをメモリインターフェイス214に向けることができる。ホストインターフェイス206、フロントエンドユニット212、及びメモリインターフェイス214は、一般的に従来設計のものでよく、本発明にとって重要でないので、詳細な説明は省く。
【0016】
[0026]各PPU202は、高度な並列プロセッサを実施するのが好都合である。PPU202(0)について詳細に示すように、PPU202は、多数Cのコア208を含み、但し、C≧1である。各処理コア208は、非常に多数(例えば、数十又は数百)のスレッドを同時に実行することができ、各スレッドは、プログラムのインスタンスであり、マルチスレッド型処理コア208の一実施形態を以下に説明する。コア208は、フロントエンドユニット212から処理タスクを定義するコマンドを受け取るワーク配布ユニット210を経て、実行されるべき処理タスクを受け取る。このワーク配布ユニット210は、ワークを配布するための種々のアルゴリズムを実施することができる。例えば、一実施形態では、ワーク配布ユニット210は、各コア208から、そのコアが新たな処理タスクを受け入れるに充分なリソースを有するかどうか指示する「レディ」信号を受け取る。新たな処理タスクが到着すると、ワーク配布ユニット210は、レディ信号をアサートしているコア208にタスクを指定し、レディ信号をアサートしているコア208がない場合には、ワーク配布ユニット210は、コア208によりレディ信号がアサートされるまで、新たな処理タスクを保持する。当業者であれば、他のアルゴリズムも使用できると共に、ワーク配布ユニット210が到来する処理タスクを配布する特定のやり方は、本発明にとって重要ではないことが明らかであろう。
【0017】
[0027]コア208は、種々の外部メモリ装置を読み取ったりそこに書き込んだりするためにメモリインターフェイス214と通信する。一実施形態では、メモリインターフェイス214は、ローカルPPメモリ204と通信するためのインターフェイスと、ホストインターフェイスへの接続とを含み、これにより、コアは、システムメモリ104、或いはPPU202に対してローカルではない他のメモリと通信することができる。メモリインターフェイス214は、一般的に従来設計のものでよく、詳細な説明は、省く。
【0018】
[0028]コア208は、これに限定されないが、直線的及び非直線的なデータ変換、ビデオ及び/又はオーディオデータのフィルタリング、モデリングオペレーション(例えば、物理の法則を適用して、オブジェクトの位置、速度及び他の属性を決定する)、映像レンダリングオペレーション(例えば、頂点シェーダー、幾何学的シェーダー及び/又はピクセルシェーダープログラム)、等を含む種々様々なアプリケーションに関する処理タスクを実行するようにプログラムすることができる。PPU202は、システムメモリ104及び/又はローカルPPメモリ204からのデータを内部(オンチップ)メモリへ転送し、そのデータを処理し、そしてその結果データをシステムメモリ104及び/又はローカルPPメモリ204へ書き戻すことができ、このようなデータは、例えば、CPU102又は別の並列処理サブシステム112を含む他のシステムコンポーネントによりアクセスすることができる。
【0019】
[0029]再び、図1を参照すれば、ある実施形態において、並列処理サブシステム112内のPPU202は、その幾つか又は全部が、レンダリングパイプラインを伴うグラフィックプロセッサであって、CPU102及び/又はシステムメモリ104によりメモリブリッジ105及びバス113を経て供給されたグラフィックデータからピクセルデータを発生し、ローカルPPメモリ204(例えば、従来のフレームバッファを含むグラフィックメモリとして使用できる)と相互作用してピクセルデータを記憶及び更新し、そのピクセルデータをディスプレイ装置110へ配送し、等々に関連した種々のタスクを遂行するように構成することができる。ある実施形態では、PPサブシステム112は、グラフィックプロセッサとして動作する1つ以上のPPU202、及び汎用の計算に使用される1つ以上の他のPPU202を含むことができる。PPUは、同じものでも異なるものでもよく、そして各PPUは、それ自身の専用のPPメモリ装置(1つ又は複数)を有してもよいし、専用のPPメモリ装置を有していなくてもよい。
【0020】
[0030]動作に際して、CPU102は、システム100のマスタープロセッサであり、他のシステムコンポーネントのオペレーションを制御し整合させる。特に、CPU102は、PPU202のオペレーションを制御するコマンドを発行する。ある実施形態では、CPU102は、各PPU202のためのコマンドのストリームをプッシュバッファ(図1には明確に示さず)に書き込み、このプッシュバッファは、CPU102及びPPU202の両方に対してアクセス可能なシステムメモリ104、PPメモリ204、又は別の記憶位置に配置することができる。PPU202は、プッシュバッファからコマンドストリームを読み取り、そしてCPU102のオペレーションとは非同期でそれらコマンドを実行する。
【0021】
[0031]ここに示すシステムは、例示に過ぎず、変更や修正がなされ得ることが明らかであろう。ブリッジの数及び配列を含む接続技術は、必要に応じて変更することができる。例えば、ある実施形態では、システムメモリ104は、ブリッジを経ずに、CPU102へ直結され、他の装置は、メモリブリッジ105及びCPU102を経てシステムメモリ104と通信する。他の別のトポロジーでは、並列処理サブシステム112は、I/Oブリッジ107へ接続され、又はメモリブリッジ105ではなく、CPU102へ直結される。更に別の実施形態では、I/Oブリッジ107及びメモリブリッジ105が1つのチップへ一体化されてもよい。ここに示す特定のコンポーネントは、任意のものであり、例えば、いかなる数のアドインカード又は周辺装置がサポートされてもよい。ある実施形態では、スイッチ116が除去され、ネットワークアダプタ118及びアドインカード120、121がI/Oブリッジ107に直結される。
【0022】
[0032]PPU202とシステム100の残り部分との接続を変更することもできる。ある実施形態では、PPシステム112は、システム100の拡張スロットに挿入できるアドインカードとして実施される。他の実施形態では、PPU202は、単一チップ上で、メモリブリッジ105又はI/Oブリッジ107のようなバスブリッジと一体化することができる。更に別の実施形態では、PPU202の幾つかの又は全部のエレメントを単一チップ上でCPU102と一体化することができる。
【0023】
[0033]PPUには、ローカルメモリを含まずに、任意の量のローカルPPメモリを設けることができ、そしてローカルメモリ及びシステムメモリを任意の組合せで使用することができる。例えば、PPU202は、一体化メモリアーキテクチャー(UMA)実施形態ではグラフィックプロセッサであり、このような実施形態では、専用のグラフィック(PP)メモリがほとんど又は全く設けられず、又、PPU202は、システムメモリを排他的又はほぼ排他的に使用する。UMA実施形態では、PPUは、ブリッジチップ又はプロセッサチップに一体化されてもよく、或いは例えば、ブリッジチップを経てPPUをシステムメモリに接続する高速リンク(例えば、PCI−E)を伴う個別のチップとして設けられてもよい。
【0024】
[0034]上述したように、並列処理サブシステムには、任意の数のPPUを含ませることもできる。例えば、複数のPPUを単一のアドインカードに設けることもできるし、又は複数のアドインカードを通信経路113に接続することもできるし、或いは1つ以上のPPUをブリッジチップに一体化することもできる。複数PPUシステムのPPUは、互いに同じものでもよいし異なるものでもよく、例えば、異なるPPUは、異なる数のコア、異なる量のローカルPPメモリ、等を有してもよい。複数のPPUが存在する場合には、それらを並列に動作させて、単一のPPUで可能なものより高いスループットでデータを処理することができる。
【0025】
[0035]1つ以上のPPUを合体するシステムは、デスクトップ、ラップトップ又はハンドヘルドパーソナルコンピュータ、サーバー、ワークステーション、ゲームコンソール、埋め込まれたシステム、等々を含む種々の構成及びフォームファクタで実施することができる。
[コアの概略]
【0026】
[0036]図3は、本発明の1つ以上の態様に基づく図2の並列処理サブシステム112のための並列処理ユニット220を示すブロック図である。このPPU202は、非常に多数のスレッドを並列に実行するように構成されたコア208(又は複数コア208)を備え、ここで、「スレッド(thread)」という語は、入力データの特定セットに対して実行される特定プログラムのインスタンスを指す。ある実施形態では、単一命令複数データ(SIMD)の命令発行技術を使用して、複数の独立した命令ユニットを設けずに、非常に多数のスレッドの並列実行がサポートされる。ある実施形態では、単一命令複数スレッド(SIMT)技術を使用し、処理エンジンのセットへ命令を発行するように構成された共通の命令ユニットを使用して、非常に多数の一般的に同期されたスレッドの並列実行がサポートされる。全ての処理エンジンが典型的に同じ命令を実行するSIMD実行形態とは異なり、SIMTの実行は、異なるスレッドが、所与のスレッドプログラムを通して、発散する実行経路を容易にたどれるようにする。当業者であれば、SIMD処理形態は、SIMT処理形態の機能的サブセットを表すことが理解されよう。
【0027】
[0037]SIMDマシンと同様に、SIMT並列処理コア208は、このコア208に含まれた複数の並列処理エンジン302にわたって異なるデータに対して単一の並列プログラムのインスタンスを実行する。従って、例えば、コア208は、該コア208内の並列処理エンジン302において一連の共通の命令を実行するように構成できる。単一の並列処理エンジン302への一連の命令は、前記で定義されたスレッドを構成し、そしてコア208内の並列処理エンジン302間のある数の現在実行中のスレッドの集合を、ここでは「ワープ(warp)」又は「スレッドグループ」と称する。更に、複数の関連スレッドグループは、コア208において同時にアクティブとなり得る(実行の異なる段階で)。スレッドグループのこの集合を、ここでは「協働スレッドアレー」(CTA)と称する。
【0028】
[0038]特定のCTAのサイズは、m*kに等しい。但し、kは、スレッドグループ内の同時に実行されるスレッドの数で、典型的に、コア208における並列処理エンジン302の数の整数倍であり、そしてmは、コア208において同時にアクティブなスレッドグループの数である。CTAのサイズは、一般的に、プログラマーと、CTAに利用可能なメモリ又はレジスタのようなハードウェアリソースの数とによって決定される。
【0029】
[0039]一実施形態では、各コア208は、単一命令ユニット312からSIMT命令を受け取るように構成されたP個(例えば、8個、16個、等)の並列処理エンジン302のアレイを含む。各処理エンジン302は、機能的ユニット(例えば、演算論理ユニット、等)の同じセットを含むのが好都合である。機能的ユニットは、この技術で知られたように、手前の命令が終了する前に新たな命令を発行できるようなパイプライン型のものでよい。機能的ユニットの任意の組合せを設けることもできる。ある実施形態では、機能的ユニットは、整数及び浮動小数点演算(例えば、加算及び乗算)、比較演算、ブール演算(AND、OR、XOR)、ビットシフト、及び種々の代数関数(例えば、平面補間、三角法、指数関数、及び対数関数、等)の組合せ、を含む種々のオペレーションをサポートし、そして同じ機能的ユニットハードウェアをレバレッジして(leveraged)、異なるオペレーションを遂行することができる。
【0030】
[0040]各処理エンジン302は、ローカル入力データ、中間結果、等を記憶するためにローカルレジスタファイル(LRF)304のスペースを使用する。一実施形態では、ローカルレジスタファイル304は、ある数のエントリーを各々有するP個のレーンに物理的又は論理的に分割される(各エントリーは、例えば、32ビットワードを記憶する)。各処理エンジン302に1つのレーンが指定されると共に、異なるレーンの対応エントリーに、同じプログラムを実行する異なるスレッドに対するデータをポピュレートさせて(populated)、同期した並列実行を容易にすることができる。SIMT命令は、スレッドグループの各スレッドに対応する各レーンのレジスタエントリーにアクセスするレジスタオペランド(register operand)を指定することができる。ある実施形態では、各処理エンジン302は、それに指定されたレーンのLRFエントリーにしかアクセスできない。ローカルレジスタファイル304におけるエントリーの全数は、処理エンジン302当たり複数の同時スレッドをサポートするに充分なほど大きいのが好都合である。
【0031】
[0041]又、各処理エンジン302は、コア208内の全処理エンジン302間で共有されて異なるスレッド間でデータを転送するのに使用できるオンチップ共有メモリ306にアクセスすることができる。この共有メモリ306は、希望の大きさのものでよく、ある実施形態では、いずれの処理エンジン302も、等しく低い待ち時間(例えば、ローカルレジスタファイル304へのアクセスに匹敵する)で、共有メモリ306内の任意の位置から読み取り又はそこに書き込むことができる。ある実施形態では、共有メモリ306は、共有レジスタファイルとして実施され、他の実施形態では、共有メモリ306は、共有キャッシュメモリを使用して実施することができる。
【0032】
[0042]共有メモリ306に加えて、ある実施形態では、付加的なオンチップパラメータメモリ及び/又はキャッシュ(1つ又は複数)308も設けられ、これは、例えば、従来のRAM又はキャッシュとして実施されてもよい。パラメータメモリ/キャッシュ308は、例えば、複数のスレッドにより必要になることのある状態パラメータ及び/又は他のデータ(例えば、種々の定数)を保持するのに使用できる。又、処理エンジン302は、メモリインターフェイス214を経てオフチップ「グローバル」メモリ320にアクセスすることができ、これは、例えば、PPメモリ204及び/又はシステムメモリ104を含むことができ、システムメモリ104は、上述したように、メモリインターフェイス214によりホストインターフェイス206を経てアクセスすることができる。PPU202の外部の任意のメモリをグローバルメモリ320として使用してもよいことを理解されたい。処理エンジン302は、この処理エンジン302がグローバルメモリ320にアクセスするのを許す相互接続部(明確に図示せず)を経てメモリインターフェイス214へ結合することができる。
【0033】
[0043]一実施形態では、各処理エンジン302は、マルチスレッド型であり、例えば、ローカルレジスタファイル304の指定レーンの異なる部分における各スレッドに関連した現在状態情報を維持することにより、ある数G(例えば、24)までのスレッドを同時に実行することができる。処理エンジン302は、異なるスレッドからの命令を効率のロスなく任意のシーケンスで発行できるように、あるスレッドから別のスレッドへ急速にスイッチするように設計されるのが好都合である。
【0034】
[0044]命令ユニット312は、所与の処理サイクルに対して、同じ命令(INSTR)をP個の全処理エンジン302へ発行できるように構成される。従って、単一クロックサイクルのレベルにおいて、コア208は、P路(P-way)のSIMT又はSIMD設計を実質的に表わすマイクロアーキテクチャーを実施する。又、各処理エンジン302がマルチスレッド型で、G個までのスレッドを同時にサポートするので、この実施形態のコア208は、同時に実行するP*G個までのスレッドを有することができる。例えば、P=16及びG=24の場合には、コア208が384個までの同時スレッドをサポートする。
【0035】
[0045]命令ユニット312は、同じ命令をP個の全処理エンジン302へ並列に発行するので、コア208は、スレッドグループにおいてスレッドを処理するのに使用されるのが好都合である。ここで使用する「スレッドグループ」とは、グループの1つのスレッドが各処理エンジン302に指定されるようにして、異なる入力データに対して同じプログラムを実行するP個までのスレッドのグループを指す。スレッドグループは、P個より少ないスレッドを含んでもよく、この場合は、そのスレッドグループが処理されるときのサイクル中には処理エンジン302の幾つかがアイドル状態になる。又、スレッドグループは、P個より多くのスレッドを含んでもよく、この場合は、連続するクロックサイクルにわたり処理が行われる。各処理エンジン302は、G個までのスレッドを同時にサポートできるので、コア208において所与の時間にG個までのスレッドのグループを実行できることになる。
【0036】
[0046]各クロックサイクルに、Gスレッドグループの選択された1つを形成しているP個の全スレッドに1つの命令が発行される。どのスレッドが現在アクティブであるか指示するために、関連スレッドに対する「アクティブマスク」を命令と共に含ませることができる。処理エンジン302は、アクティブマスク及びスレッドグループ識別子を使用して、命令を実行するときに、ローカルレジスタファイル304の指定レーンのどの部分を使用すべきか決定する。従って、所与のサイクルに、コア208の全ての処理エンジン302が、同じスレッドグループ内の異なるスレッドに対して同じ命令を同期状態で実行することができる。当業者であれば、スレッドグループ内の各スレッドのこのような同期並列実行がSIMDアーキテクチャーの特徴であることが明らかであろう。スレッドグループ内のスレッドが同期状態で実行するときには、処理エンジン302は、SIMD形態で命令を実行するように構成される。しかしながら、あるインスタンスでは、スレッドグループ内の幾つかのスレッドが、例えば、以下に述べるように、条件付き又は述語型命令、プログラムの分岐点での発散、等のために、一時的にアイドル状態になることがある。処理エンジン302は、SIMD又はSIMTエンジンとして機能するように構成されてもよい。
【0037】
[0047]コア208のオペレーションは、コアインターフェイス303を経て制御されるのが好都合である。ある実施形態では、コアインターフェイス303は、処理されるべきデータ(例えば、原始データ、頂点データ、及び/又はピクセルデータ)、状態パラメータ、及びデータをどのように処理すべきか定義するコマンド(例えば、どんなプログラムを実行すべきか)をワーク配布ユニット210から受け取る。コアインターフェイス303は、処理されるべきデータを共有メモリ306に、そしてパラメータをパラメータメモリ308にロードすることができる。又、コアインターフェイス303は、命令ユニット312において各々の新たなスレッド又はスレッドグループを初期化し、次いで、スレッドの実行を開始するように命令ユニット312に信号する。スレッド又はスレッドグループの実行が完了すると、コア208は、コアインターフェイス303に通知するのが好都合である。次いで、コアインターフェイス303は、他のプロセスを開始し、例えば、共有メモリ306から出力データを検索し、及び/又は付加的なスレッド又はスレッドグループの実行のためにコア208を準備することができる。
【0038】
[0048]ここに述べるコアアーキテクチャーは、例示に過ぎず、変更や修正が考えられることが明らかである。いかなる数の処理エンジンが含まれてもよい。ある実施形態では、各処理エンジンは、それ自身のローカルレジスタファイルを有し、スレッド当たりのローカルレジスタファイルエントリーの割り当ては、固定でもよいし、又は希望の通りに構成できてもよい。更に、1つのコア208しか示されていないが、PPU202は、いかなる数のコア208を含んでもよく、それらコアは、互いに同じ設計のものであって、実行の振舞いが、どのコア208が特定の処理タスクを受け取るかに依存しないようにするのが好都合である。各コア208は、他のコア208とは独立して動作すると共に、それ自身の処理エンジン、共有メモリ、等を有するのが好都合である。
【0039】
[0049]当業者であれば、図1、2及び3に示すアーキテクチャーは、本発明の範囲を何ら限定するものではなく、且つここに教示する技術は、本発明の範囲から逸脱せずに、これに限定されないが、1つ以上のCPU、1つ以上のマルチコアCPU、1つ以上のGPU、1つ以上のマルチコアGPU、等を含む任意の適切に構成された処理ユニットにおいて実施できることが理解されよう。
[スレッドアレー及び協働スレッドアレー]
【0040】
[0050]ある実施形態では、図3のマルチスレッド処理コア208は、スレッドブロック又はスレッドアレーを使用して汎用計算を実行することができる。スレッドアレーは、入力データセットに対して同じプログラムを同時に実行して出力データセットを発生する多数(n0)のスレッドより成る。スレッドアレーの各スレッドには、実行中にスレッドにアクセスできる独特のスレッド識別子(スレッドID)が指定される。このスレッドIDは、スレッドの処理振舞いについての種々の態様を制御する。例えば、スレッドIDを使用して、入力データセットのどの部分をスレッドが処理すべきか決定し、及び/又は出力データセットのどの部分をスレッドが発生し又は書き込むべきか決定することができる。
【0041】
[0051]ある実施形態では、スレッドアレーは、「協働」スレッドアレー即ちCTAとして配列される。各CTAは、入力データセットに対して同じプログラム(ここでは「CTAプログラム」と称される)を同時に実行して、出力データセットを発生するスレッドのグループである。CTAでは、スレッドは、スレッドIDに基づくやり方でデータを互いに共有することにより協働することができる。例えば、CTAでは、データをあるスレッドによって発生し、別のスレッドによって消費することができる。ある実施形態では、データを共有すべきポイントにおいてCTAプログラムコードに同期命令を挿入して、消費側スレッドがデータへのアクセスを試みる前に発生側スレッドによりデータが実際に発生されるよう確保することができる。CTAのスレッド間でのデータ共有がもしあれば、その程度は、CTAプログラムによって決定され、従って、CTAを使用する特定のアプリケーションにおいて、CTAのスレッドは、CTAプログラムに基づいて実際にデータを互いに共有してもよいし、しなくてもよいことを理解されたい。
【0042】
[0052]ある実施形態では、CTAのスレッドは、図3の共有メモリ306を使用して、入力データ及び/又は中間結果を同じCTAの他のスレッドと共有する。例えば、CTAプログラムは、特定のデータを書き込むべき共有メモリ306内のアドレスを計算するための命令を含み、このアドレスは、スレッドIDの関数である。各スレッドは、それ自身のスレッドIDを使用して関数を計算し、そして対応する位置に書き込みを行う。アドレス関数は、異なるスレッドが異なる位置に書き込みを行い、関数が決定論的である限り、スレッドによって書き込まれる位置を予想できるように、定義されるのが好都合である。又、CTAプログラムは、データを読み取るべき共有メモリ306内のアドレスを計算するための命令を含むこともでき、そのアドレスは、スレッドIDの関数である。適当な関数を定義して、同期技術を与えることにより、予想可能なやり方で、CTAの1つのスレッドによって共有メモリ306内の所与の位置にデータを書き込み、そして同じCTAの異なるスレッドによりその位置からデータを読み取ることができる。その結果、スレッド間での希望のデータ共有パターンをサポートすることができ、CTAのいずれのスレッドも、同じCTAの他のスレッドとでデータを共有することができる。
【0043】
[0053]CTA(又は他の形式のスレッドアレー)は、データ並列分解に適した計算を遂行するのに使用されるのが好都合である。ここで使用する「データ並列分解」という語は、入力データに対して同じアルゴリズムを複数回並列に実行して出力データを発生することにより計算上の問題を解決する状態を含み、例えば、データ並列分解の1つの共通のインスタンスは、入力データセットの異なる部分に同じ処理アルゴリズムを適用して、出力データセットの異なる部分を発生することを含む。データ並列分解の影響を受け易い問題は、例えば、マトリクス代数、任意の次元数における線型及び/又は非線型変換(例えば、高速フーリエ変換)、及び種々のフィルタリングアルゴリズムを含み、このフィルタリングアルゴリズムは、任意の次元数のコンボリューションフィルタ、複数次元の分離可能なフィルタ、等を含む。入力データセットの各部分に適用されるべき処理アルゴリズムは、CTAプログラムにおいて指定され、そしてCTA内の各スレッドは、入力データセットの一部分に対して同じCTAプログラムを実行するか、又は出力データセットの一部分を発生する。CTAプログラムは、広範囲の数学的及び論理的オペレーションを使用してアルゴリズムを実施することができ、又、プログラムは、条件付き又は分岐実行経路と、直接的及び/又は間接的メモリアクセスとを含むことができる。
【0044】
[0054]一実施形態では、図1のCPU102で実行されるドライバプログラムは、CTAを定義するコマンドをメモリ(例えば、システムメモリ104)内のプッシュバッファ(明確に図示せず)へ書き込み、これは、PPU202によりコマンドが読み取られるところである。これらコマンドは、CTA内のスレッドの数、CTAを使用して処理されるべき入力データセットのグローバルメモリ320内の位置、実行されるべきCTAプログラムのグローバルメモリ320内の位置、及び出力データを書き込むべきグローバルメモリ320内の位置のような状態パラメータに関連付けられるのが好都合である。この状態パラメータは、コマンドと一緒にプッシュバッファに書き込まれてもよい。コマンドに応答して、コアインターフェイス303は、状態パラメータをコア208(例えば、パラメータメモリ308)へロードし、次いで、CTAパラメータで指定されたスレッドの数が起動されるまでスレッドの起動を開始する。一実施形態では、コアインターフェイス303は、起動されたスレッドにスレッドIDを順次に指定する。より一般的には、CTAの全スレッドが同じコア208において同じプログラムを実行するので、1つのスレッドのみに各有効スレッドIDが指定される限り、いずれのスレッドにいずれのスレッドIDが指定されてもよい。独特の識別子(数字識別子を含むが、これに限定されない)をスレッドIDとして使用することができる。一実施形態では、CTAが、ある数(n0)のスレッドを含む場合には、スレッドIDは、0からn0−1までの単なる逐次(一次元)インデックス値である。他の実施形態では、多次元インデックス機構を使用することができる。スレッドIDを参照することによってデータの共有が制御される限り、処理エンジンにスレッドを特定に指定しても、CTAの実行結果に影響が及ぶことはない。従って、CTAプログラムは、それを実行すべき特定のハードウェアとは独立したものでよい。
[マルチスレッド命令処理]
【0045】
[0055]図4Aは、本発明の1つ以上の態様に基づく、図3の並列処理ユニット202のための命令ユニット312を示すブロック図である。この命令ユニット312は、命令フェッチユニット400と、命令キャッシュ430と、定数キャッシュ410と、ディスパッチャー435と、条件コードユニット450とを備えている。命令フェッチユニット400は、処理されるべきデータと、データを処理するのに使用すべきプログラムに対応するプログラム識別子とを受け取る。アドレスレジスタ445は、プログラム命令によってロードされ及び読み取られるアドレス値を記憶する。スレッドグループ内のスレッドごとにアドレスレジスタ445にレジスタセットがある。本発明のある実施形態では、アドレスレジスタ445は、16ビット値を記憶し、又、他の実施形態では、アドレスレジスタ445は、32ビット値を記憶する。或いは又、アドレス値は、グローバルメモリ320、共有メモリ306、又はローカルレジスタファイル304に記憶される。
【0046】
[0056]プログラムカウンタ記憶装置405は、各スレッドグループに対して実行されるべき次のプログラム命令(INSTR)を指示するアクティブなプログラムカウンタを記憶する。G=24のときには、プログラムカウンタ記憶装置405は、24個のアクティブなプログラムカウンタを記憶する。同様に、スレッド状態記憶装置420は、各スレッドグループに対するアクティブなマスクを記憶し、アクティブなマスクの各ビットは、P個の処理エンジン302の整数に対応する。それ故、アクティブなマスクにおけるビット数は、スレッドグループにおけるスレッドの数である。又、スレッド状態記憶装置420は、各スレッドグループに対するディセーブルマスクも記憶する。ディセーブルマスクは、スレッドグループ内の各スレッドに対してフラグを含む。このフラグは、スレッドがイネーブルされたか、条件付きリターン命令の処理のためにディセーブルされたか、条件付きブレーク命令の処理のためにディセーブルされたか、又はスレッドがプログラムを退出したか、指示する。これら命令の処理、及びディセーブルマスクの決定は、図5A、5B及び7を参照して説明する。
【0047】
[0057]CRS(呼び出し、リターン、同期)スタック425は、図4に実行スタック(0)ないし(G−1)として示された各スレッドグループのための実行スタックを含む。実行スタックは、例えば、トークンタイプ、トークンプログラムカウンタ及びトークンマスクのような状態情報を含むトークンをプッシュ及びポップするために制御命令の処理中に使用される。本発明のある実施形態では、CRSスタック425は、実行スタック455に対してグローバルメモリ320へのエントリーをこぼし、実行スタック455は、オーバーフローし、そしてCRSスタック425にスペースが得られたときにこぼれたエントリーを回復させることができる。コントローラ415は、制御命令が実行されるときにCRSスタック425からエントリーをプッシュ及びポップする。一実施形態では、6つのタイプの制御命令がある。即ち、条件付き分岐命令と、呼び出し命令と、プレブレーク(PreBreak)命令と、プレリターン(PreReturn)命令と、条件付きリターン命令と、同期命令と、条件付きブレーク命令である。別の実施形態は、それより多数又は少数のタイプの制御命令、並びに異なるタイプの制御命令を含んでもよい。
【0048】
[0058]コントローラ415は、スレッドグループに対するアクティブなプログラムカウンタ及びアクティブなマスクを命令キャッシュ430に与える。この命令キャッシュ430は、アクティブなプログラムカウンタに対応する命令を得、そしてその命令及びアクティブなマスクをディスパッチャー435へ出力する。命令キャッシュ430は、当業者に知られたキャッシュ技術を使用して、グローバルメモリ320から命令を必要に応じて読み取る。コントローラ415は、制御命令が実行されるときに条件コードユニット450から制御情報440を経て制御情報を受け取る。この制御情報は、制御命令のタイプを示すトークンタイプと、スタックアンワインド(unwind)信号と、トークンをCRSスタック425にプッシュしそしてスレッドグループに対するアクティブマスク及びディセーブルマスクを更新するのに必要な他のデータとを含む。
【0049】
[0059]定数キャッシュ410は、命令のオペランドとして指定されたインデックス使用して読み取られる値を記憶する。本発明のある実施形態では、スレッドグループに対する定数にアクセスするためにインデックスが使用される。間接的な分岐がサポートされるときには、図4Bを参照して述べるように、関数ポインタが定数キャッシュ410に記憶される。スレッドグループの各スレッドは、異なるインデックスを使用することにより定数キャッシュ410内の異なる定数にアクセスできることに注意されたい。それ故、単一のスレッドグループ内の異なるスレッドは、異なる関数ポインタを使用して分岐し、SIMT処理中に発散を生じ得る。
【0050】
[0060]ディスパッチャー435は、命令をデコードし、そして条件付き制御命令(条件付き分岐、条件付きブレーク、及び条件付きリターン)に対する条件付きデータを条件コードユニット450へ出力する。条件付きデータは、条件テスト及び比較値(制御命令により指定される)を含み、これに対して条件コードが適用される。従来、条件コードは、命令により指定された条件テストを比較値に対して評価し、真又は偽の結果を発生するのに使用される。整数値に対する8つの条件テストのうちの6つは、従来の条件テスト、例えば、より小さい(less than)(LT)、等しい(equal)(EQ)、より大きい(greater than)(GT)、以下(less than or equal)(LE)、以上(greater than or equal)(GE)、及び不等(not equal)(NE)である。条件テストは、比較値が正であるか、ゼロであるか又は負であるか決定するのに使用される。
【0051】
[0061]浮動小数点フォーマット値が使用されるときには、条件テストは、NaN(非数(not-a-number))値のような非順序値に対する振舞いを定義する条件テストも含むことができる。NaNは、数値に対して順序をもたず、それ故、従来の条件テストのための入力として、又は比較値を発生するのに使用されたときには、予期せぬ結果を生じさせる。8つの新たな条件テスト、例えば、LEG、U、LTU、EQU、LEU、GTU、NEU及びGEUは、NaN値の明確なハンドリングを与える。LEG(より小さい、等しい、又はより大きい)は、比較値がゼロ、正又は負であり、即ち順序付けされるときしか真とならない。U(非順序)は、比較値が非順序付けされ、即ちNaNであるときしか真とならない。LTU(ゼロ未満又は非順序)は、比較値が負又はNaNであるときに真となる。EQU(ゼロに等しい又は非順序)は、比較値がゼロ又はNaNであるときしか真とならない。LEU(ゼロ以下又は非順序)は、比較値が負、ゼロ又はNaNのときしか真とならない。GTU(ゼロより大きい又は非順序)は、比較値が正又はNaNであるときしか真とならない。NEU(ゼロに等しくなく又は非順序)は、比較値が正、負又はNaNであるときしか真とならない。GEU(ゼロ以上又は非順序)は、比較値が正、ゼロ又はNaNであるときしか真とならない。
【0052】
[0062]他の2つの従来の条件テスト(整数及び浮動小数点値に対する)は、常に(TR)であって、決して(FL)ではない。オーバーフロー及び桁上げのような付加的な条件テストも使用でき、従って、条件テストの数が増加される。比較値は、プログラムの実行中に計算することができ、スレッドグループ内の各スレッドは、比較値を有してもよい。それ故、条件テストが評価されるときには、あるスレッドは、真の結果を発生し、一方、他のスレッドは、偽の結果を発生することがある。1つ以上のアクティブなスレッドが、他のアクティブなスレッドとは異なる条件テスト結果を生じるときには、スレッドが発散し、CRSスタック435を使用して、分岐の第1の側が実行を完了した後に実行される分岐の側に対してアクティブなマスク及びプログラムカウンタを含むトークンを記憶する。
【0053】
[0063]又、条件付きデータに加えて、ディスパッチャーは、制御命令(呼び出し、ブレーク、リターン、分岐、等)、命令により指定されるターゲットプログラムカウンタ(アドレス)、及びアクティブなマスクを条件コードユニット450へ出力する。制御命令は、ディスパッチャー435によって処理エンジン203へ出力されない。むしろ、条件コードユニット450は、この条件コードユニット450によりコントローラへ出力された制御情報に含まれたアクティブなマスクに基づいて「テークン(taken)」マスクを決定する。より詳細には、条件コードユニット450は、条件テスト結果を使用して、命令により指定されたテスト条件に対して「真」と評価するアクティブなスレッドを指示する「テークンマスク」を決定する。真の比較テスト結果を指示するスレッドグループ内のスレッドに対するこのテークンマスクのビットがクリアされる。アクティブなマスク及びテークンマスクは、ディセーブルマスクを更新するように、コントローラ415によって使用することができる。異なる関数ポインタを有する2つ以上のスレッドで関数呼び出しが遂行されるときには、関数呼び出しが直列化されて、各独特の関数ポインタを指定するスレッドを実行すると共に、テークンマスクを使用して、各独特の関数ポインタに対するアクティブなスレッドを指示する。
【0054】
[0064]条件コードユニット450は、テークンマスク及びトークンタイプを、制御情報440を経てコントローラ415へ出力する。ターゲットプログラムカウンタが呼び出し又は分岐制御命令により指定されるときには、テークンプログラムカウンタが条件コードユニット450により制御情報440を経てコントローラ415へ出力される。トークンタイプは、ディセーブルマスクを発生するために実行された制御命令のタイプを指示する。トークンタイプは、同期、呼び出し、発散、及びブレークを含む。スレッドに対する制御命令が、フライト中(in-flight)であり、即ちコントローラ415により出力されたが制御情報440を経てコントローラ415によりまだ受け取られていないときには、同じスレッドに対する別の命令がコントローラ415により出力されてはならないことに注意されたい。
【0055】
[0065]ディスパッチャー435によって受け取られる他の命令(非制御命令)は、処理エンジン302へ出力するために待ち行列に入れられる。ディスパッチャー435は、命令を処理するのに必要な(計算又は記憶)リソースの利用性に基づき命令を出力するように構成されてもよい。ディスパッチャー435のある実施形態では、スコアボードスキームを使用して、リソースの利用性を追跡すると共に、どの命令を処理エンジン302へ出力できるか決定する。処理エンジン302が命令を受け取ると、その命令を実行するのに必要なオペランドを得るために読み取り要求が発生されて、その読み取り要求がLRF304又は共有メモリ306へ出力される。次いで、命令は、オペランドが得られたときに処理エンジン302によって処理される。
【0056】
[0066]図4Bは、本発明の1つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的な分岐命令の概念図である。スレッドが条件テストを使用して独立して分岐するのを許すのに加えて、コア208は、BRX命令を使用して間接的分岐及び間接的な関数呼び出しをサポートすることを含む。間接的な分岐及び関数呼び出しは、スイッチステートメントのようなC++プログラミング特徴を実施するのに使用される。C++言語は、プロセッサが関数ポインタを経て間接的に関数を呼び出すのを要求するランタイム関数バインディング及びバーチャル関数を使用する。この能力は、関数ポインタをオペランドとして受け容れるBRX命令により各個々のスレッドに対して設けられる。コンパイラーは、BRX命令を使用してスイッチステートメントを実施して、間接的分岐を遂行すると共に、間接的分岐テーブルを構成し、テスト及び分岐の逐次チェーンの発生に比して性能を改善する。間接的な関数呼び出しに対してBRX命令が使用されるときには、PRET(プレリターン)又はCAL(呼び出し)命令(図4Bには示さず)を先行させて、関数リターンアドレスをCRSスタック425にプッシュさせる。
【0057】
[0067]プログラムコード470における分岐命令BRXは、サブルーチンMYSUBに対応する関数ポインタを指定する。コントローラ415は、BRX命令を受け取ると、BRX命令に対してオペランドとして指定されたレジスタを読み取る。この実施例では、アドレスレジスタ445における各スレッドのためのA2レジスタが、スレッドグループにおけるアクティブなスレッドに対するオペランドとして指定され、コントローラ415は、数値定数インデックス472を、命令キャッシュ430へ出力されるBRX命令のためのオペランドとして挿入する。オペランド、例えば、定数インデックス472は、定数キャッシュ410にアクセスするためのスレッドグループインデックスとして使用される。命令キャッシュ430は、BRX命令を受け取ると、定数インデックス472を使用して、スレッドグループ内のアクティブなスレッドに対する関数ポインタのセットを記憶する定数キャッシュ410の1つ以上のエントリーを読み取る。本発明のある実施形態では、一度に1つの定数がアクセスされ、命令キャッシュ430は、読み取った要求を、アドレス値(定数インデックス472)に基づいて直列化する。図4Bに示すように、関数MYSUBを指すポインタ474が定数キャッシュ410のエントリーから読み取られる。
【0058】
[0068]各スレッドに対するアドレスが異なるキャッシュインデックスを指定することがあるので、異なるスレッドに対して定数キャッシュ410から異なる関数ポインタが読み取られることがあることに注意されたい。全てのアクティブなスレッドが同じ関数ポインタを指定しないときには、アクティブなスレッドが発散し、そして各独特の関数ポインタ値に対してBRX命令が実行される。換言すれば、関数ポインタにより指定された異なる関数が、各独特の関数ポインタを共有するスレッドに対して直列に実行される。テークンマスク(taken mask)が制御情報440と共にディスパッチャー435により(条件コードユニット450を経て)コントローラ415へ出力され、第1の独特の関数ポインタを取り上げるスレッドを指示する。コントローラ415は、DIVERGEトークンを、現在のアクティブなマスク及びBRX命令のプログラムカウンタと共に、CRSスタック425にプッシュする。DIVERGEトークンは、図8を参照して述べるように、各独特の関数ポインタに対してBRX命令を繰り返すために、サブルーチンの実行が完了したときにポップされる。
【0059】
[0069]図4Cは、本発明の1つ以上の態様に基づき、スレッドグループの各スレッドに対して1つずつ、スレッドグループに対する関数ポインタのセットを記憶するレジスタを参照する間接的な分岐命令の概念図である。本発明のこの実施形態では、関数ポインタのセットは、アドレスレジスタA2により指定されたアドレスレジスタ445のパー・スレッド(per-thread)エントリーに記憶される。プログラムコード478は、関数ポインタのセット、即ち関数MYSUBを指すポインタ476をアドレスレジスタに直接記憶し、関数ポインタを定数キャッシュ410に記憶するのではない。本発明のある実施形態では、LRF304、共有メモリ306又はグローバルメモリ320のエントリーは、関数ポインタを記憶し、そしてオペランドとして指定され、スレッドグループ内のスレッドが発散して、異なるサブルーチンを実行できるようにする。関数ポインタをアドレスレジスタ445に記憶しない本発明の実施形態では、関数ポインタが、コントローラ415ではなく、処理エンジン302によって読み取られる。
【0060】
[0070]図5Aは、本発明の1つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。当業者であれば、これら方法ステップを任意の順序で遂行するように構成されたいかなるシステムも本発明の範囲内に入ることが理解されよう。ステップ500において、コントローラ415は、アクティブなプログラムカウンタを命令キャッシュ430へ出力することによりスレッドに対するアクティブなプログラムカウンタ(PC)の現在設定に対応するプログラム命令をフェッチする。ステップ505において、ディスパッチャー435は、命令が制御命令であるかどうか決定する。命令が制御命令であることをディスパッチャー435が決定すると、方法は、ステップ507へ進み、ディスパッチャー435は、制御命令を条件コードユニット450へ出力し、そして条件コードユニット450は、制御命令が呼び出し命令であるかどうか決定する。
【0061】
[0071]命令が呼び出し命令であることを条件コードユニット450が決定すると、方法はステップ508へ進み、そして条件コードユニット450は、CALLのトークンタイプ、ターゲットプログラムカウンタ(呼び出し命令により指定された)、テークンマスク(アクティブなマスクに等しい)、及びトークンプログラムカウンタを含む制御情報を出力する。トークンプログラムカウンタは、サブルーチン呼び出しのリターンアドレスであり、スレッドのための次のプログラム命令を指すように増加されたアクティブなプログラムカウンタ、即ち「ノット・テークン(not taken)」プログラムカウンタに等しい。呼び出し命令は、条件付きではないので、テークンマスクは、アクティブなマスクに等しい。又、制御情報は、ディスパッチャー435から受け取ったディセーブルマスクも含み得る。ステップ509において、コントローラ415は、プログラムカウンタ記憶装置405にスレッドグループに対して記憶されたアクティブなプログラムカウンタを、ターゲットプログラムカウンタにセットし、呼び出し命令を実行する。呼び出し命令は、CRSスタック425へトークンをプッシュすることによってネストレベルを高めるので、ディセーブルマスクは不変である。ディセーブルマスクは、ネストレベルを下げる命令が実行され且つCRSスタック425からトークンがポップされたときに変化する。
【0062】
[0072]各制御命令に対してCRSスタック425へプッシュされる異なるトークンがテーブル1に概略的に示されている。本発明のある実施形態では、CRSスタック425各エントリーは、64ビットである。トークンは、トークンタイプと、マスク(トークンマスク)と、トークンがポップされるときにスレッドグループの実行を再開すべき場所を指定するトークンプログラムカウンタとを含む。トークンタイプID_SYNC、ID_DIVERGE、ID_CALL、及びID_BREAKは、各々、SSY命令、分岐(BRA及びBRX)命令、CALL及びPreReturn(PRET)命令、及びPreBreak(PREBRK)命令に対応する。呼び出しトークンに含まれるマスクは、呼び出し/リターン分岐に遭遇したときに存在したアクティブなマスク(active_mask)であり、そして呼び出しトークンにおけるプログラムカウンタは、リターンプログラムカウンタ(not_taken_pc)である。リターンプログラムカウンタは、増加されたアクティブなプログラムカウンタに等しい呼び出し命令に続くプログラムの命令(即ち、フォールスルー(fall-through)命令)を指定する。
【表1】
【0063】
[0073]ステップ507において、制御命令が呼び出し命令でないことを条件コードユニット450が決定すると、方法はステップ510へ進み、そこで、条件コードユニット450は、制御命令がSSY(セット同期)、プレブレーク又はプレリターン命令であるか決定する。制御命令がSSY、PREBRK又はPRET命令であることを条件コードユニット450が決定すると、ステップ512において、条件コードユニット450は、SSY(同期)、PREBRK(プレブレーク)又はPRET(プレリターン)のトークンタイプ、テークンマスクとしてのアクティブなマスク、及びコントローラ415への命令によりトークンプログラムカウンタとして指定されたtarget_pc(ターゲットプログラムカウント)を含む制御プログラムを出力し、そしてコントローラ415は、CRSスタック425にトークンをプッシュする。トークンに含まれたトークンマスクは、アクティブなマスクであり、SSY、PREBRK及びPRET命令は、CRSスタック425にトークンをプッシュするので、ディセーブルマスクは不変である。ステップ514では、コントローラ415は、プログラムカウンタ記憶装置405にスレッドに対して記憶されたアクティブなプログラムカウンタを増加して、スレッドに対する次の命令を指すようにする。
【0064】
[0074]ここで、ステップ505に戻ると、命令が制御命令でないとディスパッチャー435が決定した場合には、方法はステップ520へ進み、ディスパッチャー435は、スレッドグループ内のスレッドを同期しなければならないことを示すpop sync(同期)フラグを命令が含むかどうか決定する。pop syncフラグは、SSY命令の逆の意味を有する。pop syncフラグは、最後のSSY命令がsyncトークン(トークンタイプSSY)をCRSスタック425へプッシュさせたために発散したスレッドグループのスレッドが、pop syncフラグを含む命令に対して実行されるべきであることを指示する。ここに詳細に述べるように、このプロセスは、この最後のsyncトークンがCRSスタック425へプッシュされたときに存在したスレッド同期のレベルを再確立する。換言すれば、このプロセスは、最後のSSY命令に遭遇したときに存在したスレッド同期のレベルを再確立し、最後のSSY命令により指定されたターゲットアドレス(SSYトークンのトークンプログラムカウンタ)において実行を開始する。好ましい実施形態では、同期オペレーションは、キャリア命令(即ち、pop syncフラグを含む命令)の他のオペレーションの前に行われる。別の実施形態では、同期オペレーションは、個別の命令を使用して行われてもよいし、或いはキャリア命令の他のオペレーションの後に同期オペレーションを行うこともできる。制御命令は、pop syncフラグのためのキャリア命令ではないことに注意されたい。
【0065】
[0075]ステップ520において、命令がpop syncフラグを含むとディスパッチャー435が決定すると、ステップ525において、ディスパッチャー435は、条件コードユニット450を経てコントローラ415へ制御情報を出力し、コントローラ415は、CRSスタック425をアンワインド(unwind)するように進み、スレッドグループ内の(アクティブな)スレッドの同期をとる。コントローラ415へ出力される制御情報は、CRSスタック425をアンワインドしなければならないことを指示するアンワインドスタック信号を含む。キャリア命令は、スタックがアンワインドされ且つアクティブなスレッドが同期された後に実行される。ステップ525の詳細は、図5Bを参照して説明する。
【0066】
[0076]ステップ520において、命令がpop syncフラグを含まないとディスパッチャー435が決定すると、ステップ522において、ディスパッチャー435は、命令を処理エンジン302へ実行のために出力する。ステップ527において、ディスパッチャー435は、条件コードユニット450を経てコントローラ415へ増加PC信号を含む制御情報を出力し、そしてコントローラ415は、スレッドに対してプログラムカウンタ記憶装置405に記憶されたアクティブなプログラムカウンタを増加する。或いは又、増加されたアクティブなプログラムカウンタがコントローラ415へ出力される。
【0067】
[0077]ここで、ステップ510へ戻ると、制御命令がSSY、PREBRK又はPRET命令でないことを条件コードユニット450が決定した場合には、ステップ530において、条件コードユニット450は、制御命令が分岐命令であるかどうか決定する。分岐命令は、非条件付き分岐及び条件付き分岐命令(BRA)と、非条件付き間接的分岐及び条件付き間接的分岐命令(BRX)とを含む。BRX命令は、1つ以上の関数ポインタをBRXへのオペランドとして指定することにより間接的な関数呼び出しを実行するように使用される。
【0068】
[0078]間接的な分岐命令は、分岐アドレス(関数ポインタ)をコンパイル時に決定する必要がないので、より大きな融通性を許すように使用できる。分岐ターゲットレジスタは、スレッドグループ内の全てのスレッドに使用される単一分岐アドレス(又は定数インデックス)を記憶することができる。分岐ターゲットレジスタには、プログラムの実行中に、計算値を書き込むことができる。或いは又、スレッドグループ内の各スレッドが、間接的な分岐命令に対して異なる分岐アドレスを指定し(直接的に又は定数キャッシュ410のインデックスとして)、テーブル1に示すY(1)発散を生じてもよい。各スレッドに対して分岐アドレス(1つ又は複数)が読み取られて、P路の間接的分岐を許す。各独特の分岐アドレス及び最後の独特の分岐アドレスに対して間接的な分岐命令が実行され、テーブル1に示すY(2)発散を生じ、ここで、ノット・テークンプログラムカウンタがCRSスタック425にプッシュされる。スレッドは、条件付き分岐内の間接的な関数呼び出しのために発散し得ることに注意されたい。図8を参照して述べるように、各独特の分岐アドレスに対してスレッドの実行が直列化されるときにアクティブであるスレッドを指示するためにアクティブなマスクが使用される。
【0069】
[0079]ステップ530において、制御命令が分岐命令でないことを条件コードユニット450が決定すると、それはリターン又はブレーク命令であり、そして呼び出し/リターン分岐に関連したサブルーチンの終了、又はプレブレーク分岐に関連した命令のループの終了に到達し、方法はステップ532へ進む。ステップ532において、条件コードユニット450は、コントローラ415へ出力されるテークンマスクを発生し、コントローラ415は、アクティブなスレッドの1つ以上が条件テスト結果に基づいて発散するかどうか決定する。条件付きリターン又はブレーク命令によって指定された条件テストに対して真と評価するアクティブなスレッドは、いずれも、テークンマスクによりディセーブルされる。これらのスレッドは、他のアクティブなスレッド(条件テストに対して偽と評価する)が実行を続ける間に、ディセーブルされてアイドル状態に保たれる。ディセーブルされたスレッドに対応するビットは、テークンマスクにおいてクリアされ、テークンマスクにおいてセットされたビットの数が、アクティブなマスクにおいてセットされたビットの数以下となるようにする。
【0070】
[0080]ステップ532において、スレッドが発散しない(テークンマスクがアクティブなマスクに等しい)ことをコントローラ415が決定すると、ステップ525において、コントローラ415は、CRSスタック425をアンワインド(unwind)するように進む。アンワインドプロセス中に、リターン又はブレーク命令によりディセーブルされたスレッドは、図5Bを参照して更に説明するように、それに対応する呼び出しトークン(ID_CALL)又はプレブレークトークン(ID_BREAK)がCRSスタック425からポップされたときにイネーブルされる。
【0071】
[0081]ステップ532において、スレッドが発散する(テークンマスクがアクティブなマスクに等しくない)ことをコントローラ415が決定すると、ステップ534において、コントローラ415は、変更されたディセーブルマスクを決定する。これらスレッドに対するディセーブルマスクの状態は、taken_maskビットがセットされたスレッドが、特定事象を待機する間アイドル状態であることを指示する値にセットされる。この事象は、プログラムの終了であるか、又はCRSスタック425からポップされるべき特定のトークンに対するものである。
【0072】
[0082]本発明のある実施形態では、0のディセーブル状態は、スレッドがイネーブルされることを指示し、1のディセーブル状態は、スレッドがリターン命令を実行し、且つCRSスタック425からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、2のディセーブル状態は、スレッドがブレーク命令を実行し、且つCRSスタック425からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして3のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。
【0073】
[0083]ステップ536において、コントローラ415は、アクティブなマスクを変更する。より詳細には、「条件を取り入れた」スレッドグループ内のスレッドに対応するアクティブなマスクのビットがクリアされて、それらのスレッドが非アクティブとして現れるようにする。換言すれば、テークンマスクとアクティブなマスクとの間でビットワイズのXOR(排他的OR)が遂行され、変更型アクティブマスクを生成する。ステップ539では、コントローラ415が、スレッドに対する次の命令を実行するために、アクティブなプログラムカウンタを増加する。
【0074】
[0084]ここで、ステップ530に戻ると、制御命令が分岐命令であることを条件コードユニット450が決定すると、ステップ535において、コントローラ415は、条件コードユニット450により与えられたテークンマスクに基づいていずれかのアクティブなスレッドが発散するかどうか決定する。ステップ535において、条件コードユニット450は、テークンマスク、トークンタイプ、及びターゲットプログラムカウンタを含む制御情報をコントローラ415へ出力する。ステップ535において、少なくとも1つのアクティブなスレッドがスレッドグループ内の他のアクティブなスレッドから発散することをコントローラ415が決定すると、ステップ537において、コントローラ415は、発散トークン(ID_DIVERGE)をCRSスタック425にプッシュする。トークンに含まれたトークンマスクは、ノット・テークンマスク(not_taken_mask)であり、これは、条件テストに対して「真」と評価しないアクティブなスレッド、即ち分岐をとらないアクティブなスレッドを指示する。コントローラ415は、テークンマスク及びアクティブなマスクを使用してトークンマスクを決定することができる。トークンプログラムカウンタは、スレッドにおいて次の命令を指定するために増加されるアクティブなプログラムカウンタに等しい。
【0075】
[0085]ステップ540において、コントローラ415は、条件テストに対して「真」と評価し即ち分岐をとるアクティブなスレッドを指示するテークンマスクとしてアクティブなマスクを決定する。ステップ545において、コントローラ415は、アクティブなプログラムカウンタを、分岐命令により指定されたターゲットプログラムカウンタ(アドレス)にセットする。
【0076】
[0086]ステップ535において、アクティブなスレッドがどれも発散しないとコントローラ415が決定すると、ステップ542において、コントローラ415は、全てのアクティブなスレッドが分岐をとるかどうか決定する。それに代わるものとして、アクティブなスレッドがいずれも分岐をとらない場合には、条件コードユニット450が、0x0000に等しいテークンマスクを出力する。ステップ544において、コントローラ415は、スレッドにおいて次の命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置405に記憶されたアクティブなプログラムカウンタを増加する。ステップ542において、全てのアクティブなスレッドが分岐をとるとコントローラ415が決定すると、ステップ545において、コントローラ415は、コントローラ415への分岐命令により指定されたターゲットプログラムカウンタ(アドレス)に等しくなるようにアクティブなプログラムカウンタを更新し、そしてコントローラ415は、分岐により指定された命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置405に変更されたアクティブなプログラムカウンタを記憶する。
【0077】
[0087]CRSスタック425を使用すると、PPU202は、スレッドの発散及び同期を行いながら、スレッドグループを処理できるようになる。ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状の条件及びサブルーチン内のスレッド完了を含む更に進歩した制御フローをサポートするのに使用される。各スレッドグループに対して単一のディセーブルマスクがスレッド状態記憶装置420に記憶され、そしてディセーブルマスクは、CRSスタック425からポップされたトークンと結合されて、ディセーブルされたスレッドグループ内のスレッドの実行を再開する。
【0078】
[0088]図5Bは、本発明の1つ以上の態様に基づき図5Aのステップ525を完了するためにCRSスタック425をアンワインド(unwinding)する方法ステップのフローチャートである。CRSスタック425は、処理エンジン302により同時に実行できるGスレッドグループの各々に対して実行スタック455を備え、各スレッドグループが、他のスレッドグループとは独立して進行できるようにする。ステップ550において、コントローラ415は、スレッドグループに対する実行スタック455が空であるかどうか決定し、もしそうであれば、ステップ552において、スレッドグループの実行が完了し、そして命令ユニット312は、スレッドグループが実行を完了したことをコアインターフェイス303に通知する。ステップ550において、実行スタック455が空でないことをコントローラ415が決定すると、ステップ555において、コントローラ415は、実行スタック455から実行スタック455の最上部にトークンをポップさせる。ステップ560において、コントローラ415は、トークンが呼び出し又はプレブレークトークンであるかどうか決定し、そしてトークンが呼び出し又はプレブレークトークンでないときには、ステップ570へ直接進む。
【0079】
[0089]呼び出しトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きリターン命令の実行を完了しそして(ディセーブルマスクに基づいて)ディセーブルされたスレッドをイネーブルすべきであることを指示する。プレブレークトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きブレーク命令の実行を完了しそして(ディセーブルマスクに基づいて)ディセーブルされたスレッドをイネーブルすべきであることを指示する。スレッドグループ内のアクティブなスレッドは、トークンと共に記憶されるマスク、即ちトークンマスクにより指示される。重要なことに、呼び出し及びプレブレークループをネスト状にできるように、ディセーブルマスクを使用して、スレッドグループ内のスレッドをディセーブルする。ステップ560において、コントローラ415は、トークンが呼び出し又はプレブレークトークンであることを決定し、次いで、ステップ565において、コントローラ415は、スレッドに対してディセーブルマスクを更新する。より詳細には、トークンが呼び出しトークンであるときには、コントローラ415は、スレッドが条件付きリターン命令によってディセーブルされたことを指示する1のディセーブル状態をもち且つ呼び出しトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。トークンがプレブレークトークンであるときには、コントローラ415は、スレッドが条件付きブレーク命令によってディセーブルされたことを指示する2のディセーブル状態をもち且つプレブレークトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。
【0080】
[0090]ステップ560において、トークンが呼び出しトークンでもプレブレークトークンでもないことをコントローラ415が決定すると、トークンは、sync又は発散のいずれかのトークンである。ステップ570において、コントローラ415は、アクティブなマスクをトークンからのマスクにセットし、次いで、ディセーブルされたスレッドを除去することにより、アクティブなマスクを更新する。より詳細には、ディセーブルされたことを指示するディセーブル状態を有するスレッドは、それらスレッドが誤って実行を再開するのを防止するために、(トークンから)更新されたアクティブなマスクにおけるそれらの対応ビットをクリアしている。これは、スレッドがイネーブルされないことをディセーブル状態が指示する限り、スレッドがインアクティブのままであることを保証する。換言すれば、アクティブなマスクは、スレッドグループ内の他のスレッドが条件付きブレーク又はリターン分岐の実行を完了するのを待っているスレッドグループ内のいずれかのスレッドの処理をディセーブルするように更新される。
【0081】
[0091]ステップ575において、コントローラ415は、更新されたアクティブなマスクがゼロに等しく、スレッドグループ内のどのスレッドもアクティブでないことを指示するかどうか決定する。ステップ575において、どのスレッドもアクティブでないことをコントローラ415が決定すると、方法はステップ550へ戻り、別のトークンをポップする(又はプログラムの実行を完了する)。さもなければ、ステップ580において、コントローラ415は、アクティブなプログラムカウンタを、ステップ555においてポップされたトークンからのプログラムカウンタにセットする。
【0082】
[0092]テーブル4に戻ると、呼び出しトークンのプログラムカウンタは、リターンプログラムカウンタである。アクティブなプログラムカウンタをリターンプログラムカウンタに等しくセットすることで、アクティブなスレッドが、呼び出し命令に続くプログラムの命令(即ち、フォールスルー命令)にリターンすることが規定される。ブレークトークンにおけるプログラムカウンタは、ループ後プログラムカウンタ(after-loop program counter)である。アクティブなプログラムカウンタをこのループ後プログラムカウンタにセットすることで、アクティブなスレッドが、ループ後プログラムカウンタにより指定されたアドレスをもつ命令へ分岐することが規定される。
【0083】
[0093]syncトークンに含まれたマスクは、それに対応するSSY命令が実行されたときに存在したアクティブなマスクである。従って、アクティブなマスクを、syncトークンに含まれたマスクに等しくセットすると、SSY命令に最初に遭遇したときにアクティブであったスレッドであって、介在する条件付きリターン又はブレーク命令によりディセーブルされるスレッドを除く全てのスレッドをアクチベートする。syncトークンに含まれたプログラムカウンタは、SSY命令により指定されたプログラムカウンタである。
【0084】
[0094]分岐及び間接的分岐のための発散トークンに含まれたマスクは、ノット・テークン(not taken)マスクである。一実施形態では、アクティブなマスクをノット・テークンマスクにセットすることは、発散トークンに関連した条件付き分岐の「イフ・サイド(if-side)」を実行する必要のあるスレッドをアクチベートする一方、その分岐の「エルス・サイド(else-side)」の実行を丁度完了したスレッドをインアクチベートするように作用する。2路発散を伴う分岐及び間接的分岐に対して発散トークンに含まれたプログラムカウンタは、ノット・テークンプログラムカウンタである。アクティブなプログラムカウンタをノット・テークンプログラムカウンタにセットすることで、新たにアクチベートされるスレッドが、条件付き分岐の「イフ・サイド」で第1の命令を実行することが規定される。このプロセスは、条件付き分岐の「イフ・サイド」の実行をイネーブルする。P路発散を伴う間接的分岐に対して発散トークンに含まれたプログラムカウンタは、アクティブなプログラムカウンタである。それ故、BRX命令は、各独特の分岐アドレスに対して実行される。
【0085】
[0095]テーブル2は、図5Bの方法ステップに対するCプログラミング言語擬似コードを示し、disable_mask.returnは、スレッドが呼び出しトークンを待機するときにアサートされ、disable_mask.breakは、スレッドがブレークトークンを待機するときにアサートされ、そしてdisable_mask.eosは、スレッドがプログラムを退出するときにアサートされる。図5Aを参照して既に説明したように、本発明のある実施形態では、1のディセーブル状態は、スレッドがリターン命令を実行し、且つCRSスタック425からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、2のディセーブル状態は、スレッドがブレーク命令を実行し、且つCRSスタック425からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして3のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。それ故、これらの実施形態では、disable_mask.returnは、ディセーブル状態が1であるときにアサートされ、disable_mask.breakは、ディセーブル状態が2であるときにアサートされ、そしてdisable_mask.eosは、ディセーブル状態が3であるときにアサートされる。
【表2】
【0086】
[0096]ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状条件及びサブルーチン内のスレッド完了、を処理するのに使用される。ディセーブルマスクの使用に代わるものは、スレッドディセーブル事象(条件付きリターン又はブレーク)が生じたときに実行スタック455をウオーク(walk)し、そして全ての関連トークンにおけるセーブされたアクティブなマスクを変更することである。しかしながら、実行スタック455をウオークすることは、実行スタック455が非常に深くて、グローバルメモリ320に記憶された部分を伴うので、潜在的に時間浪費である。それ故、ディセーブルマスクは、性能に関して効果的であり、同時に実行できるG個のスレッドの各々に対して1つのマスクしか必要としない。
【0087】
[0097]テーブル3は、本発明の1つ以上の態様を例示するために「イフ・ゼン・エルス(if-then-else)」ステートメントを実施する分岐命令を含むプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表3】
【0088】
[0098]図6は、本発明の1つ以上の態様に基づき、テーブル3に示すプログラム命令のシーケンスが実行されるときに、CRSスタック425内の実行スタックをどのようにポピュレート(populated)しアンワインド(unwound)するかを概念的に例示する。
【0089】
[0099]図示されたように、欄600は、命令ユニット312がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄605は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。又、アクティブなプログラムカウンタは、0の初期値を有すると仮定する。
【0090】
[00100]コントローラ415は、最初に、0のプログラムカウンタ値に対応するMAD命令をフェッチする(ステップ500)。MAD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x1に増加される(ステップ527)。次いで、コントローラ415は、SSY命令をフェッチし、そしてトークンタイプSYNC、アクティブなマスク(0xff)、及びSSY命令により指定されたターゲットプログラムカウンタ(LABEL1、PC=7)を含むsyncトークンを実行スタック455にプッシュする(ステップ512)。欄610は、各プログラム命令が実行された後に実行スタック455の最上部にあるトークンを示す。アクティブなプログラムカウンタは、0x2へ増加される(ステップ514)。
【0091】
[00101]次いで、コントローラ415は、条件xがゼロ未満である場合にターゲットプログラムカウンタアドレスLABEL0(PC=6)へ分岐するBRA LT.x命令をフェッチする。BRA命令は、条件付き分岐命令であり、分岐テークン(taken)経路及びノット・テークン(not-taken)経路を決定するために条件テストが使用される。BRA命令により指定された条件テスト(即ち、xは、0未満)を満足し、従って、分岐をとって、「イフ・ゼン・エルス(if-then-else)」ステートメントの「エルス・サイド」を実行するために、6つのスレッドが仮定される。1つ以上のアクティブなスレッドが発散するので、コントローラ415は、発散トークン(DIV)を実行スタック455にプッシュする(ステップ537)。欄615は、各プログラム命令が実行された後に実行スタック455の最上部より1エントリー下のトークンTOS−1(スタックの最上部・マイナス・1)を示す。
【0092】
[00102]発散トークンに含まれるマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、条件テストを満足しなかった2つのスレッドを反映する。これら2つのスレッドは、分岐テークンのエルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、0xf3であり、アクティブなマスクは、テークンマスクにセットされる。発散トークンに含まれるプログラムカウンタは、0x3の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第1命令(即ち、フォールスルー命令)のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、0x6のターゲットプログラムカウンタにセットされる(ステップ545)。
【0093】
[00103]次いで、コントローラ415は、ADD命令をフェッチする。ADD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x7に増加される(ステップ527)。次いで、コントローラ415は、pop−syncフラグ(.S)を含むMAX.S命令をフェッチする。pop−syncフラグは、命令がプログラム内の同期ポイントであることを指定する。pop−syncフラグが含まれるので、コントローラ415は、BRA LT.xによりプッシュされた発散トークンをポップし(ステップ555)、そしてアクティブなマスクを0xcへ更新すると共に、アクティブなプログラムカウンタを0x3にセットすることにより(ステップ570、575及び580)、実行スタック455をアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL命令をフェッチする(条件付き分岐のイフ・サイド)。MUL命令は制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x4に増加される(ステップ527)。
【0094】
[00104]次いで、コントローラ415は、次のMUL命令(条件付き分岐のイフ・サイドに対する第2の命令)をフェッチする。このMUL命令も制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x5に増加される(ステップ527)。
【0095】
[00105]次いで、コントローラ415は、LABEL1のターゲットプログラムカウンタ(PC=7)を指定するBRA命令をフェッチする。BRA命令は、常にとられる無条件命令であり、それ故、アクティブなスレッドは発散しない。アクティブなスレッドは、全て、分岐をとるので、アクティブなプログラムカウンタは、0x7のターゲットプログラムカウンタにセットされる(ステップ535、542及び545)。
【0096】
[00106]次いで、コントローラ415は、pop−syncフラグ(.S)を含むMAX.S命令をフェッチし、そしてSSYによってプッシュされたsyncトークンをポップする(ステップ555)と共に、アクティブなマスクを0xffに更新し且つアクティブなプログラムカウンタを0x7にセットする(ステップ570、575及び580)ことにより、実行スタックをアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MAX.S命令をフェッチし、スレッドが同期される(アクティブなマスクが0xffである)ので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x8に増加される(ステップ527)。コントローラ415は、キャリア命令(MAX)を実行するために、実行スタック455がアンワインドされてMAX.S命令の.S部分を処理した後に、pop−syncフラグを無視しなければならないことに注意されたい。それ故、syncトークンがポップされると、コントローラ415は、syncトークンがポップされたときにセットされ且つキャリア命令が実行されるときにクリアされる状態のビットを各スレッドグループに対して維持する。
【0097】
[00107]テーブル4は、本発明の1つ以上の態様を例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表4】
【0098】
[00108]テーブル5は、テーブル4のプログラム命令のサブルーチン部分に対するCプログラミング言語擬似コードを示す。
【表5】
【0099】
[00109]図7は、本発明の1つ以上の態様に基づき、条件付きリターンを含むテーブル4及び5に示すプログラム命令のシーケンスが実行されるときに、実行スタック455内の実行スタック455をどのようにポピュレート(populated)し、アンワインド(unwound)するかを示す別の概念図である。図示されたように、欄700は、命令ユニット312がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄705は、各プログラム命令が実行される前のアクティブなマスクの値を示す。欄710は、各プログラム命令が実行される前のディセーブルマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。又、アクティブなプログラムカウンタは、50の初期値を有すると仮定する。
【0100】
[00110]コントローラ415は、先ず、SUBROUTINEのターゲットプログラムカウンタ(PC=0)を指定するアドレス50においてCALL命令をフェッチする。トークンタイプCALL、アクティブなマスク(0xff)及びターゲットプログラムカウンタを含む呼び出しトークンが実行スタック455にプッシュされる(ステップ508)。全てのアクティブなスレッドがコールをとるので、アクティブなプログラムカウンタは、0x0のターゲットプログラムカウンタにセットされる(ステップ509)。欄715は、各プログラム命令が実行された後に実行スタック455の最上部にあるトークンを示す。
【0101】
[00111]次いで、コントローラ415は、SSY命令をフェッチし、そしてトークンタイプSYNC、アクティブなマスク(0xff)、及びSSY命令により指定されたターゲットプログラムカウンタ(LABEL1、PC=7)を含むsyncトークンを実行スタック455にプッシュする(ステップ512)。欄720は、各プログラム命令が実行された後に実行スタック455の最上部より1エントリー下にあるトークンTOS−1(スタックの最上部・マイナス・1)を示す。アクティブなプログラムカウンタは、0x2へ増加される(ステップ514)。
【0102】
[00112]次いで、コントローラ415は、xにより指定された比較値及びLABEL0(PC=6)のターゲットプログラムカウンタでLT条件テストを指定するBRA命令をフェッチする。1つ以上のアクティブなスレッドが発散するので、コントローラ415は、発散トークン(DIV)を実行スタック455にプッシュする(ステップ537)。欄725は、各プログラム命令が実行された後に実行スタック455の最上部より2エントリー下にあるトークンTOS−2(スタックの最上部・マイナス・2)を示す。
【0103】
[00113]発散トークンに含まれたマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、逆の条件テストを満足しなかった2つのスレッドを反映する。これら2つのスレッドは、エルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、0xf3であり、アクティブなマスクは、欄705に示すように、テークンマスクに等しくセットされる(ステップ540)。発散トークンに含まれるプログラムカウンタは、0x2の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第1命令(即ち、フォールスルー命令)のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、0x5のターゲットプログラムカウンタにセットされる(ステップ545)。
【0104】
[00114]次いで、コントローラ415は、xにより指定された比較値でGT条件テストを指定するRET命令をフェッチする。1つ以上のアクティブなスレッドが発散するので、条件コードユニット450は、ディセーブルマスクを決定する(ステップ534)。変更型ディセーブルマスクは、0x0005である(各スレッドが2ビットフラグを有する)。というのは、アクティブなスレッドのうちの2つが条件テストを満足し、フラグを1にセットして、呼び出し命令を待機しているディセーブル状態を指示するからである。条件コードユニット450は、ディセーブルされたスレッドの実行をディセーブルするようにアクティブなマスクを変更する。それ故、アクティブなマスクは、0xf3から0xf0へ変化する(ステップ536)。最終的に、アクティブなプログラムカウンタは、0x6の値に増加される(ステップ539)。
【0105】
[00115]次いで、コントローラ415は、ADD命令をフェッチする。ADD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x7に増加される(ステップ527)。次いで、コントローラ415は、pop−syncフラグ(.S)を含むMUL.S命令をフェッチする。pop−syncフラグが含まれるので、コントローラ415は、BRA発散トークンをポップし(ステップ555)、そしてアクティブなマスクを0xcへ更新すると共に、アクティブなプログラムカウンタを0x2にセットすることにより(ステップ570、575及び580)、実行スタック455をアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL命令をフェッチする(条件付き分岐のイフ・サイド)。MUL命令は制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x3に増加される(ステップ527)。
【0106】
[00116]次いで、コントローラ415は、次のMUL命令(条件付き分岐のイフ・サイドに対する第2の命令)をフェッチする。このMUL命令も制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x4に増加される(ステップ527)。
【0107】
[00117]次いで、コントローラ415は、LABEL1のターゲットプログラムカウンタ(PC=7)を指定する(無条件)BRA命令をフェッチする。アクティブなスレッドは、全て分岐をとるので、アクティブなプログラムカウンタは、0x7のターゲットプログラムカウンタにセットされる(ステップ535、542及び545)。
【0108】
[00118]次いで、コントローラ415は、pop−syncフラグ(.S)を含むMUL.S命令をフェッチし、そしてSSYのsyncトークンをポップする(ステップ555)と共に、アクティブなマスクを0xfcに更新し且つアクティブなプログラムカウンタを0x8にセットする(ステップ570、575及び580)ことにより、実行スタックをアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL.S命令をフェッチし、又、.S部分が実行されると共にスレッドが同期されるので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x8に増加される(ステップ527)。次いで、コントローラ415は、RET命令をフェッチし、そして呼び出しトークンをポップする(ステップ555)ことにより実行スタックをアンワインドする(ステップ532及び525)。コントローラ415は、呼び出しトークンを待機してディセーブルされたスレッドに対してディセーブル状態をクリアすることによりディセーブルマスクを更新する(ステップ565)。次いで、コントローラ415は、アクティブなマスクを0xffへ更新し、アクティブなプログラムカウンタを0x51にセットする(ステップ570、575及び580)。次いで、コントローラ415は、ADD命令をフェッチして、ADD命令を処理エンジン302へ実行のために出力する。
【0109】
[00119]テーブル6は、本発明の1つ以上の態様に基づいてBRX命令を使用して間接的な関数呼び出しを遂行することを例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされ、命令の実行は、図8を参照して詳細に説明する。
【表6】
【0110】
[00120]関数ポインタを経て間接的な関数呼び出しを可能にするために、BRX命令のターゲット(関数ポインタ)におけるプログラムコードは、分岐に使用される.S同期命令ではなくRET命令で終了する。PRET命令は、スレッド同期のための現在のアクティブなマスク(これは、BRX命令に関連した全ての関数呼び出しの実行後に生じる)を使用して、CRSスタック425にプッシュされたリターンアドレスをCALLトークンとして指定する。BRX命令は、PRET命令に従い、それが実行されるとき、アクティブなスレッドの少なくとも1つが、BRXオペランドにより指定された関数へ間接的に分岐する。その後のRET命令が実行されるときには、他のアクティブなスレッドに対する既に延期された間接的な関数呼び出しの実行が、スレッド指定関数ポインタを使用して、BRX命令の繰り返し実行により完了される。BRX命令に対して最後の関数呼び出しが実行されるときには、最終的なRET命令が、PRET命令によりCRSスタック425にプッシュされたCALLトークンをポップし、そしてCALLトークンと共にポップされるアクティブなマスクに基づいてスレッドが同期される状態でリターンアドレスへ制御を移行する。
【0111】
[00121]テーブル7は、テーブル6のプログラム命令のサブルーチン部分に対するCプログラミング言語擬似コードを示す。
【表7】
【0112】
[00122]図8は、本発明の1つ以上の態様に基づき、間接的な関数呼び出しを含むテーブル6に示すプログラム命令のシーケンスが実行されるときにCRSスタック425がどのようにポップされアンワインド(unwound)されるかを示す別の概念的な図である。図示されたように、欄800は、命令ユニット312がプログラム命令を実行する順序を示すと共に、各プログラム命令に対するアクティブなプログラムカウンタを指定する。欄805は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。この実施例では、条件付き分岐命令の実行のためにディセーブルされるスレッドはない。又、アクティブなプログラムカウンタは、4の初期値を有すると仮定する。
【0113】
[00123]第1の命令IADD .C1がフェッチされ、R2とR3に記憶された値の差が計算されて、条件コードレジスタC1に記憶される。CRSスタック425にプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは5に増加される。第1の条件付きR2A命令がフェッチされ、条件テスト(LT)が条件コードC1に対して評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。条件コード指定子(C1)及びテストされるべき特定の条件(LT)は、行先レジスタに続きカッコで示されるA1。MYSUB1を指す関数ポインタを記憶する定数キャッシュ410のエントリーに対応する定数インデックス(i0)は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ445のA1エントリーに記憶される。換言すれば、値2(MY_SUB1に対応するプログラムカウンタ)は、条件コードC1が「より少ない(less than)」条件にセットされるところの全てのスレッドに対してA1へ移動される。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは6に増加される。第2の条件付きR2A命令がフェッチされると共に、第2の条件テスト(GE)が評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。MYSUB2を指す関数ポインタを記憶する定数キャッシュ410のエントリーに対応する定数インデックス(i2)は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ445のA1エントリーに記憶される。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは7に増加される。
【0114】
[00124]MOV命令がフェッチされて実行され、関数の引数として値2を通す。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは8に増加される。PRET命令がフェッチされ、コントローラ415は、呼び出しトークン(CAL)を実行スタック455にプッシュする。欄805に示すように、TOS(スタックの最上部)は、0xffのマスク(現在アクティブなマスク)と、AFTER_FUNCTIONの第1命令のアドレス(10)に対応する0xaのプログラムカウンタ(PRET命令により指定される)とを含むプッシュされた呼び出しトークンを記憶する。
【0115】
[00125]間接的分岐命令BRXがフェッチされ、コントローラ415は、アドレスレジスタ445のA2エントリーに記憶された定数インデックスをBRX命令に挿入する。この実施例では、0xf3が、インデックスi0(MYSUB1)を参照するスレッドに対するテークンマスクであり、且つ0x0cが、インデックスi2(MYSUB2)を参照するスレッドに対するテークンマスクであると仮定する。コントローラ415は、各独特の関数ポインタに対してBRX命令の実行を直列化する。BRX命令は、発散トークン(DIV)を実行スタック455へプッシュする。欄815は、プログラム命令が実行された後に実行スタック455の最上部より1エントリー下にあるトークンTOS−1(スタックの最上部・マイナス・1)を示す。発散トークンに含まれたマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、MYSUB1へ間接的に分岐しなかった6つのスレッドを指示する。発散トークンに含まれるプログラムカウンタは、9の値を有し、これは、BRX命令のアドレスである。現在アクティブなマスクは0xf3へ更新され、又、アクティブなプログラムカウンタは、関数MYSUB2のターゲットアドレス0にセットされる。
【0116】
[00126]MYSUB2の第1関数であるADDがフェッチされて、アクティブなスレッドに対して処理エンジン302により実行され、レジスタR1に記憶された値を更新する。アクティブなプログラムカウンタが1に増加され、次の命令であるRETがフェッチされる。コントローラ415は、実行スタック455の最上部から発散トークンをポップし、アクティブなマスクを0x0cにセットすると共に、アクティブなプログラムカウンタを9にセットする。次いで、コントローラ415は、BRX命令をフェッチする。アクティブなスレッドは、全て、同じ関数ポインタ(インデックスi2)を指定するので、発散はなく、プッシュされるトークンもない。アクティブなプログラムカウンタは、インデックスi2に対応する関数ポインタ、即ちMYSUB1の第1命令、にセットされる。
【0117】
[00127]MYSUB1の第1命令であるADDがフェッチされて、アクティブなスレッドに対して処理エンジン302により実行され、レジスタR1に記憶された値を更新する。アクティブなプログラムカウンタが3に増加され、リターン命令RETがフェッチされる。コントローラ415は、実行スタック455の最上部から呼び出しトークンをポップし、アクティブなマスクを0xffにセットすると共に、アクティブなプログラムカウンタを10にセットする。次いで、コントローラ415は、AFTER_FUNCTIONの第1命令をフェッチする。当業者であれば、テーブル6に示すコードは、アクティブなスレッドのサブセットがBRX命令の実行により間接的な関数呼び出しを遂行するように条件分岐内に含まれることが明らかであろう。
【0118】
[00128]ここに開示するシステム及び方法の1つの効果は、マルチスレッド型アーキテクチャーのスレッドを多数のスレッドグループに分断できることである。各スレッドグループ内で、個々のスレッドを互いに発散して、必要に応じてディセーブルし、条件付き分岐、間接的な関数呼び出し、ブレーク及びリターンを実行することができる。更に、各スレッドグループ内のスレッドは、処理効率のために必要に応じて同期することができる。その結果、可能なときに完全に並列な同期モードで動作すると共に、特定のスレッドグループ内でスレッドの発散が生じるときには分岐又はサブルーチンの実行やスレッドの実行が独立して行われるので最小限の性能低下しか受けないシステムが得られる。
【0119】
[00129]本発明の一実施形態は、コンピュータシステムに使用するためのプログラム製品として実施することができる。プログラム製品のプログラム(1つ又は複数)は、(ここに述べる方法を含む)実施形態の機能を定義し、そして種々のコンピュータ読み取り可能な記憶媒体に含ませることができる。ここに例示するコンピュータ読み取り可能な記憶媒体は、(i)情報が永久的に記憶される書き込み不能の記憶媒体(例えば、コンピュータ内のリードオンリメモリ装置、例えば、CD−ROMドライブにより読み取り可能なCD−ROMディスク、フラッシュメモリ、ROMチップ、又は任意の形式のソリッドステート不揮発性半導体メモリ)、及び(ii)変更可能な情報が記憶される書き込み可能な記憶媒体(例えば、ディスケットドライブ又はハードディスクドライブ内のフロッピーディスク、又は任意の形式のソリッドステートランダムアクセス半導体メモリ)を含むが、これらに限定されない。
【0120】
[00130]本発明は、特定の実施形態を参照して以上に説明した。しかしながら、当業者であれば、特許請求の範囲に述べる本発明の広い精神及び範囲から逸脱せずに種々の変更や修正がなされ得ることが理解されよう。従って、以上の説明及び添付図面は、例示のためのものであって、それに限定されるものではない。
【符号の説明】
【0121】
100・・・システム、102・・・CPU、104・・・システムメモリ、105・・・メモリブリッジ、106・・・通信経路、107・・・I/Oブリッジ、108・・・入力装置、110・・・ディスプレイ装置、112・・・並列処理サブシステム、113・・・通信経路、114・・・システムディスク、116・・・スイッチ、118・・・ネットワークアダプタ、120・・・アドインカード、121・・・アドインカード、202・・・PPU、204・・・PPメモリ、206・・・ホストインターフェイス、208・・・コア、210・・・ワーク配布ユニット、212・・・フロントエンド、214・・・メモリインターフェイス、302・・・処理エンジン、303・・・コアインターフェイス、304・・・ローカルレジスタファイル、306・・・共有メモリ、308・・・パラメータメモリ、312・・・命令ユニット、320・・・グローバルメモリ、400・・・命令フェッチユニット、405・・・プログラムカウンタ記憶装置、410・・・定数キャッシュ、415・・・コントローラ、420・・・スレッド状態記憶装置、425・・・CRSスタック、430・・・命令キャッシュ、435・・・ディスパッチャー、440・・・制御情報、445・・・アドレスレジスタ、450・・・条件コードユニット、455・・・実行スタック、470・・・プログラムコード、472・・・定数インデックス、474・・・ロックビット、476・・・ポインタ、478・・・プログラムコード
【技術分野】
【0001】
[0001]本発明は、一般的に、グラフィック処理に係り、より詳細には、単一命令複数スレッド(SIMT:a single-instruction, multiple-thread)アーキテクチャーにおいて関数ポインタを通して関数及びサブルーチンを間接的に呼び出すことができるようにするシステム及び方法に係る。
【背景技術】
【0002】
[0002]現在のグラフィックデータ処理は、例えば、線型補間(linear interpolation)、テッセレーション(tessellation)、ラスタ化(rasterization)、テクスチャマッピング(texture mapping)、デプステスティング(depth testing)、等、の特定のオペレーションをグラフィックデータに対して遂行するように開発されたシステム及び方法を含む。慣習的に、グラフィックプロセッサは、固定関数計算ユニットを使用してグラフィックデータを処理しているが、最近では、グラフィックプロセッサの各部分がプログラム可能とされ、このようなプロセッサで、頂点及び断片データを処理するための種々様々なオペレーションをサポートすることができる。
【0003】
[0003]性能を更に高めるために、グラフィックプロセッサは、典型的に、パイプラインのような処理技術を実施し、グラフィックパイプラインの異なる部分全体にわたりできるだけ多くのグラフィックデータを並列に処理するように試みている。SIMD(single-instruction multiple-data:単一命令複数データ)アーキテクチャーをもつグラフィックプロセッサは、グラフィックパイプラインにおける並列処理量を最大にするように設計される。SIMDアーキテクチャーでは、複数のデータ入力を処理するために、同じ命令が並列に実行される。単一命令複数スレッド(SIMT)のアーキテクチャーは、SIMDアーキテクチャーより高い融通性を与える。というのは、スレッドグループ内のスレッドが、複数のデータ入力を処理するために命令のセットを通して異なる経路をたどれるからである。SIMD命令は、複数データ入力のベクトルに対してオペレーションを制御する単一制御スレッドの実行及び分岐振舞いを指定する。対照的に、SIMT命令は、そのデータ入力に対して動作する1つの個々の独立スレッドの実行及び分岐振舞いを指定し、又、SIMTアーキテクチャーは、独立して自由に実行及び分岐する複数の独立スレッドにSIMT命令を並列に適用する。処理効率を改善するために、進歩型制御フローには、スレッドが独立して分岐できる条件付きブレーク及びリターン命令が使用される。特に、ブレーク又はリターンを実行するスレッドは、ブレーク又はリターンを実行しないスレッドより早くに処理を完了することができる。条件付き命令の実行中に発散したスレッドは、次いで、それらスレッドが並列に実行されるように同期される。現在のSIMTアーキテクチャーは、各個々のスレッドが異なるポインタ値を有するような関数ポインタを通して関数及びサブルーチンを間接的に呼び出す能力を備えていない。Cのような多数のプログラミング言語は、間接的な関数呼び出しを有し、又、C++のような他のものは、バーチャルな関数を有し、どちらも、プロセッサがポインタを経て間接的に関数を呼び出す能力を与える必要がある。テスト及び分岐の逐次チェーンに比して処理性能を改善するために、間接的分岐及び間接的分岐テーブルが使用される。
【発明の概要】
【発明が解決しようとする課題】
【0004】
[0004]従って、この技術では、関数ポインタを使用して間接的な関数呼び出しを行えるようにするSIMTアーキテクチャーが要望されている。
【課題を解決するための手段】
【0005】
[0005]間接的な分岐命令は、同期並列スレッドプロセッサアーキテクチャーに対する間接的関数呼び出し能力を与えるためにアドレスレジスタを引数としてみなす。同期並列スレッドアーキテクチャーは、SIMD又はSIMTプロセッサとして機能するように構成できる。テスト及び分岐の逐次チェーンを使用するものに比して処理性能を改善する間接的分岐及び間接的分岐テーブルを実施するために間接的分岐命令が使用される。重要なことに、本発明は、スレッドが同じ分岐経路又は関数呼び出し経路をとるとき及びそれらが発散(diverging)分岐及び関数呼び出しからリターンするときにスレッドグループ内の複数のスレッドを並列に実行できるようにしながら、スレッドグループ内の個々のスレッドがスレッドグループ内の他のスレッドとは独立して分岐するための実行モデルを提供する。
【0006】
[0006]並列処理ユニットは、条件付き制御命令の実行中に1つ以上のスレッドが発散するかどうか決定するステップを遂行するように構成される。制御命令は、同期、ブレーク及びリターンのためのスレッド処理ターゲットアドレスを設定するのに使用される。プログラムを退出するスレッドは、ディセーブルマスクによりアイドルと識別される。事象を待機する間にディセーブルされる他のスレッドは、発散スレッドが事象に到着すると、イネーブルすることができる。ディセーブルマスクの使用は、マルチスレッドSIMTアーキテクチャーにおいて条件付きリターン及びブレーク命令の使用を許す。
【0007】
[0007]同期並列スレッドプロセッサにおいて間接的関数呼び出しを実行するための本発明の方法の種々の実施形態は、1つ以上の関数に対してポインタのセットを参照する第1の制御命令を受け取ることを含み、それらのポインタは、プログラムにおいて前記関数のアドレスを指定する。この方法は、次いで、スレッドグループ内のアクティブなスレッドに対応するポインタの2つが異なるものであって、アクティブなスレッドが同期並列スレッドプロセッサにおける前記間接的な関数呼び出しの実行中に発散することを指示するかどうか決定する。アクティブなスレッドが発散する場合には、第1の制御命令のアドレスを含む第1トークンが実行スタックにプッシュされる。第1関数のアドレスを指定するようにアクティブなプログラムカウンタが更新される。
【0008】
[0008]本発明の種々の実施形態は、同期並列処理スレッドに対して間接的な関数呼び出しを実行するためのシステムを含む。このシステムは、実行スタック、コントローラ、及び複数の処理エンジンを備えている。実行スタックは、システムにより同時に実行される多数のスレッドに対してスレッド状態情報を記憶するように構成される。実行スタックに結合されて、制御命令を含むプログラム命令を受け取るように構成されたコントローラは、スレッド状態情報をプッシュ及びポップすることにより制御命令を実行し、並列に処理されねばならないスレッドグループ内のアクティブなスレッドを指示するアクティブなマスクを維持し、且ついずれかのアクティブなスレッドに対応する各独特のポインタに対して間接的な関数呼び出しの実行を直列化する。複数の処理エンジンは、プログラム命令を受け取り、そしてアクティブなマスクに基づき並列に処理されねばならないスレッドグループ内のスレッドに対して各プログラム命令を並列に実行するように構成される。
【0009】
[0009]上述した本発明の特徴を詳細に理解できるように、前記で簡単に要約した本発明について、幾つかを添付図面に例示した実施形態を参照して、より詳細に説明する。しかしながら、添付図面は、本発明の典型的な実施形態を例示するに過ぎず、それ故、本発明の範囲をそれに限定するものではなく、本発明は、同等の効果を発揮できる他の実施形態も包含できるものであることに注意されたい。
【図面の簡単な説明】
【0010】
【図1】本発明の1つ以上の態様を実施するように構成されたコンピュータシステムを示すブロック図である。
【図2】本発明の1つ以上の態様に基づく図1のコンピュータシステムのための並列処理サブシステムのブロック図である。
【図3】本発明の1つ以上の態様に基づく図2の並列処理サブシステムのための並列処理ユニットのブロック図である。
【図4A】本発明の1つ以上の態様に基づく図3の並列処理ユニットのための命令ユニットのブロック図である。
【図4B】本発明の1つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図4C】本発明の1つ以上の態様に基づき関数ポインタを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図5A】本発明の1つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。
【図5B】本発明の1つ以上の態様に基づき一連のプログラム命令の実行中に実行スタックをアンワインドする(unwinding)ための方法ステップのフローチャートである。
【図6】本発明の1つ以上の態様に基づきプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す概念図である。
【図7】本発明の1つ以上の態様に基づき条件付きリターンを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す別の概念図である。
【図8】本発明の1つ以上の態様に基づき間接的な関数呼び出しを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし(populated)アンワインドする(unwound)かを示す別の概念図である。
【発明を実施するための形態】
【0011】
[0021]以下の説明では、本発明をより完全に理解するために多数の特定の細部について説明する。しかしながら、当業者であれば、これらの特定の細部の1つ以上がなくても、本発明を実施できることが明らかであろう。他の点について、本発明を不明瞭にしないために、良く知られた特徴は、説明しない。
[システムの概略]
【0012】
[0022]図1は、本発明の1つ以上の態様を実施するように構成されたコンピュータシステム100を示すブロック図である。このコンピュータシステム100は、メモリブリッジ105を含むバス経路を経て通信する中央処理ユニット(CPU)102及びシステムメモリ104を備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ105は、バス又は他の通信経路106(例えば、ハイパートランスポートリンク)を経てI/O(入力/出力)ブリッジ107に接続される。例えば、サウスブリッジ(Southbridge)チップでよいI/Oブリッジ107は、1つ以上のユーザ入力装置108(例えば、キーボード、マウス)からユーザ入力を受け取り、そしてその入力を、経路102及びメモリブリッジ105を経てCPU102へ転送する。メモリブリッジ105には、バス又は他の通信経路113(例えば、PCIエクスプレス、アクセラレーテッドグラフィックポート又はハイパートランスポートリンク)を経て並列処理サブシステム112が結合され、一実施形態では、この並列処理サブシステム112は、ディスプレイ装置110(例えば、従来のCRT又はLCDベースのモニタ)へピクセルを配送するグラフィックサブシステムである。I/Oブリッジ107には、システムディスク114も接続される。スイッチ116は、I/Oブリッジ107と、他のコンポーネント、例えば、ネットワークアダプタ118及び種々のアドイン(add-in)カード120及び121との間の接続をなす。又、I/Oブリッジ107には、USB又は他のポート接続部、CDドライブ、DVDドライブ、フィルムレコーディング装置、等を含む他のコンポーネント(明確に示さず)を接続することもできる。図1における種々のコンポーネントを相互接続する通信経路は、適当なプロトコル、例えば、PCI(周辺コンポーネント相互接続)、PCI−エクスプレス(PCI−E)、AGP(アクセラレーテッドグラフィックポート)、ハイパートランスポート、或いは他のバス又はポイント・ツー・ポイント通信プロトコルを使用して実施することができ、そして異なる装置間の接続は、この技術で知られたように異なるプロトコルを使用することができる。
【0013】
[0023]一実施形態では、並列処理サブシステム112は、例えば、ビデオ出力回路を含めて、グラフィック及びビデオ処理に最適な回路を組み込んでおり、そしてグラフィック処理ユニット(GPU)を構成する。別の実施形態では、並列処理サブシステム112は、以下に詳細に述べる、基礎となる計算アーキテクチャーを保存しながら、汎用の処理に最適な回路を組み込んでいる。更に別の実施形態では、並列処理サブシステム112は、1つ以上の他のシステムエレメント、例えば、メモリブリッジ105、CPU102、及びI/Oブリッジ107と一体化されて、システムオンチップ(SoC)を形成することができる。
【0014】
[0024]図2は、本発明の一実施形態に基づく並列処理サブシステム112を示す。この並列処理サブシステム112は、1つ以上の並列処理ユニット(PPU)202を備え、その各々は、ローカル並列処理(PP)メモリ204に結合される。一般的に、並列処理サブシステムは、多数UのPPUを含み、但し、U≧1である。(ここで、同じオブジェクトの複数のインスタンスは、オブジェクトを識別する参照番号と、必要に応じてインスタンスを識別するカッコ内の数字とで示される。)PPU202及びPPメモリ204は、例えば、プログラム可能なプロセッサ、特定用途向け集積回路(ASIC)、及びメモリ装置のような1つ以上の集積回路装置を使用して実施することができる。
【0015】
[0025]PPU202(0)について詳細に示すように、各PPU202は、メモリブリッジ105へ接続される(又は別の実施形態では、CPU102へ直結される)通信経路113を経てシステム100の残り部分と通信するホストインターフェイス206を備えている。一実施形態では、通信経路113は、この技術で知られたように、各PPU202に専用レーンが割り当てられるPCI−Eリンクである。又、他の通信経路が使用されてもよい。ホストインターフェイス206は、通信経路113へ送信するためにパケット(又は他の信号)を発生し、又、通信経路113から全ての到来パケット(又は他の信号)も受信して、それをPPU202の適当なコンポーネントへ向ける。例えば、処理タスクに関連したコマンドをフロントエンドユニット212に向ける一方、メモリオペレーション(例えば、PPメモリ204からの読み取り又はそこへの書き込み)に関連したコマンドをメモリインターフェイス214に向けることができる。ホストインターフェイス206、フロントエンドユニット212、及びメモリインターフェイス214は、一般的に従来設計のものでよく、本発明にとって重要でないので、詳細な説明は省く。
【0016】
[0026]各PPU202は、高度な並列プロセッサを実施するのが好都合である。PPU202(0)について詳細に示すように、PPU202は、多数Cのコア208を含み、但し、C≧1である。各処理コア208は、非常に多数(例えば、数十又は数百)のスレッドを同時に実行することができ、各スレッドは、プログラムのインスタンスであり、マルチスレッド型処理コア208の一実施形態を以下に説明する。コア208は、フロントエンドユニット212から処理タスクを定義するコマンドを受け取るワーク配布ユニット210を経て、実行されるべき処理タスクを受け取る。このワーク配布ユニット210は、ワークを配布するための種々のアルゴリズムを実施することができる。例えば、一実施形態では、ワーク配布ユニット210は、各コア208から、そのコアが新たな処理タスクを受け入れるに充分なリソースを有するかどうか指示する「レディ」信号を受け取る。新たな処理タスクが到着すると、ワーク配布ユニット210は、レディ信号をアサートしているコア208にタスクを指定し、レディ信号をアサートしているコア208がない場合には、ワーク配布ユニット210は、コア208によりレディ信号がアサートされるまで、新たな処理タスクを保持する。当業者であれば、他のアルゴリズムも使用できると共に、ワーク配布ユニット210が到来する処理タスクを配布する特定のやり方は、本発明にとって重要ではないことが明らかであろう。
【0017】
[0027]コア208は、種々の外部メモリ装置を読み取ったりそこに書き込んだりするためにメモリインターフェイス214と通信する。一実施形態では、メモリインターフェイス214は、ローカルPPメモリ204と通信するためのインターフェイスと、ホストインターフェイスへの接続とを含み、これにより、コアは、システムメモリ104、或いはPPU202に対してローカルではない他のメモリと通信することができる。メモリインターフェイス214は、一般的に従来設計のものでよく、詳細な説明は、省く。
【0018】
[0028]コア208は、これに限定されないが、直線的及び非直線的なデータ変換、ビデオ及び/又はオーディオデータのフィルタリング、モデリングオペレーション(例えば、物理の法則を適用して、オブジェクトの位置、速度及び他の属性を決定する)、映像レンダリングオペレーション(例えば、頂点シェーダー、幾何学的シェーダー及び/又はピクセルシェーダープログラム)、等を含む種々様々なアプリケーションに関する処理タスクを実行するようにプログラムすることができる。PPU202は、システムメモリ104及び/又はローカルPPメモリ204からのデータを内部(オンチップ)メモリへ転送し、そのデータを処理し、そしてその結果データをシステムメモリ104及び/又はローカルPPメモリ204へ書き戻すことができ、このようなデータは、例えば、CPU102又は別の並列処理サブシステム112を含む他のシステムコンポーネントによりアクセスすることができる。
【0019】
[0029]再び、図1を参照すれば、ある実施形態において、並列処理サブシステム112内のPPU202は、その幾つか又は全部が、レンダリングパイプラインを伴うグラフィックプロセッサであって、CPU102及び/又はシステムメモリ104によりメモリブリッジ105及びバス113を経て供給されたグラフィックデータからピクセルデータを発生し、ローカルPPメモリ204(例えば、従来のフレームバッファを含むグラフィックメモリとして使用できる)と相互作用してピクセルデータを記憶及び更新し、そのピクセルデータをディスプレイ装置110へ配送し、等々に関連した種々のタスクを遂行するように構成することができる。ある実施形態では、PPサブシステム112は、グラフィックプロセッサとして動作する1つ以上のPPU202、及び汎用の計算に使用される1つ以上の他のPPU202を含むことができる。PPUは、同じものでも異なるものでもよく、そして各PPUは、それ自身の専用のPPメモリ装置(1つ又は複数)を有してもよいし、専用のPPメモリ装置を有していなくてもよい。
【0020】
[0030]動作に際して、CPU102は、システム100のマスタープロセッサであり、他のシステムコンポーネントのオペレーションを制御し整合させる。特に、CPU102は、PPU202のオペレーションを制御するコマンドを発行する。ある実施形態では、CPU102は、各PPU202のためのコマンドのストリームをプッシュバッファ(図1には明確に示さず)に書き込み、このプッシュバッファは、CPU102及びPPU202の両方に対してアクセス可能なシステムメモリ104、PPメモリ204、又は別の記憶位置に配置することができる。PPU202は、プッシュバッファからコマンドストリームを読み取り、そしてCPU102のオペレーションとは非同期でそれらコマンドを実行する。
【0021】
[0031]ここに示すシステムは、例示に過ぎず、変更や修正がなされ得ることが明らかであろう。ブリッジの数及び配列を含む接続技術は、必要に応じて変更することができる。例えば、ある実施形態では、システムメモリ104は、ブリッジを経ずに、CPU102へ直結され、他の装置は、メモリブリッジ105及びCPU102を経てシステムメモリ104と通信する。他の別のトポロジーでは、並列処理サブシステム112は、I/Oブリッジ107へ接続され、又はメモリブリッジ105ではなく、CPU102へ直結される。更に別の実施形態では、I/Oブリッジ107及びメモリブリッジ105が1つのチップへ一体化されてもよい。ここに示す特定のコンポーネントは、任意のものであり、例えば、いかなる数のアドインカード又は周辺装置がサポートされてもよい。ある実施形態では、スイッチ116が除去され、ネットワークアダプタ118及びアドインカード120、121がI/Oブリッジ107に直結される。
【0022】
[0032]PPU202とシステム100の残り部分との接続を変更することもできる。ある実施形態では、PPシステム112は、システム100の拡張スロットに挿入できるアドインカードとして実施される。他の実施形態では、PPU202は、単一チップ上で、メモリブリッジ105又はI/Oブリッジ107のようなバスブリッジと一体化することができる。更に別の実施形態では、PPU202の幾つかの又は全部のエレメントを単一チップ上でCPU102と一体化することができる。
【0023】
[0033]PPUには、ローカルメモリを含まずに、任意の量のローカルPPメモリを設けることができ、そしてローカルメモリ及びシステムメモリを任意の組合せで使用することができる。例えば、PPU202は、一体化メモリアーキテクチャー(UMA)実施形態ではグラフィックプロセッサであり、このような実施形態では、専用のグラフィック(PP)メモリがほとんど又は全く設けられず、又、PPU202は、システムメモリを排他的又はほぼ排他的に使用する。UMA実施形態では、PPUは、ブリッジチップ又はプロセッサチップに一体化されてもよく、或いは例えば、ブリッジチップを経てPPUをシステムメモリに接続する高速リンク(例えば、PCI−E)を伴う個別のチップとして設けられてもよい。
【0024】
[0034]上述したように、並列処理サブシステムには、任意の数のPPUを含ませることもできる。例えば、複数のPPUを単一のアドインカードに設けることもできるし、又は複数のアドインカードを通信経路113に接続することもできるし、或いは1つ以上のPPUをブリッジチップに一体化することもできる。複数PPUシステムのPPUは、互いに同じものでもよいし異なるものでもよく、例えば、異なるPPUは、異なる数のコア、異なる量のローカルPPメモリ、等を有してもよい。複数のPPUが存在する場合には、それらを並列に動作させて、単一のPPUで可能なものより高いスループットでデータを処理することができる。
【0025】
[0035]1つ以上のPPUを合体するシステムは、デスクトップ、ラップトップ又はハンドヘルドパーソナルコンピュータ、サーバー、ワークステーション、ゲームコンソール、埋め込まれたシステム、等々を含む種々の構成及びフォームファクタで実施することができる。
[コアの概略]
【0026】
[0036]図3は、本発明の1つ以上の態様に基づく図2の並列処理サブシステム112のための並列処理ユニット220を示すブロック図である。このPPU202は、非常に多数のスレッドを並列に実行するように構成されたコア208(又は複数コア208)を備え、ここで、「スレッド(thread)」という語は、入力データの特定セットに対して実行される特定プログラムのインスタンスを指す。ある実施形態では、単一命令複数データ(SIMD)の命令発行技術を使用して、複数の独立した命令ユニットを設けずに、非常に多数のスレッドの並列実行がサポートされる。ある実施形態では、単一命令複数スレッド(SIMT)技術を使用し、処理エンジンのセットへ命令を発行するように構成された共通の命令ユニットを使用して、非常に多数の一般的に同期されたスレッドの並列実行がサポートされる。全ての処理エンジンが典型的に同じ命令を実行するSIMD実行形態とは異なり、SIMTの実行は、異なるスレッドが、所与のスレッドプログラムを通して、発散する実行経路を容易にたどれるようにする。当業者であれば、SIMD処理形態は、SIMT処理形態の機能的サブセットを表すことが理解されよう。
【0027】
[0037]SIMDマシンと同様に、SIMT並列処理コア208は、このコア208に含まれた複数の並列処理エンジン302にわたって異なるデータに対して単一の並列プログラムのインスタンスを実行する。従って、例えば、コア208は、該コア208内の並列処理エンジン302において一連の共通の命令を実行するように構成できる。単一の並列処理エンジン302への一連の命令は、前記で定義されたスレッドを構成し、そしてコア208内の並列処理エンジン302間のある数の現在実行中のスレッドの集合を、ここでは「ワープ(warp)」又は「スレッドグループ」と称する。更に、複数の関連スレッドグループは、コア208において同時にアクティブとなり得る(実行の異なる段階で)。スレッドグループのこの集合を、ここでは「協働スレッドアレー」(CTA)と称する。
【0028】
[0038]特定のCTAのサイズは、m*kに等しい。但し、kは、スレッドグループ内の同時に実行されるスレッドの数で、典型的に、コア208における並列処理エンジン302の数の整数倍であり、そしてmは、コア208において同時にアクティブなスレッドグループの数である。CTAのサイズは、一般的に、プログラマーと、CTAに利用可能なメモリ又はレジスタのようなハードウェアリソースの数とによって決定される。
【0029】
[0039]一実施形態では、各コア208は、単一命令ユニット312からSIMT命令を受け取るように構成されたP個(例えば、8個、16個、等)の並列処理エンジン302のアレイを含む。各処理エンジン302は、機能的ユニット(例えば、演算論理ユニット、等)の同じセットを含むのが好都合である。機能的ユニットは、この技術で知られたように、手前の命令が終了する前に新たな命令を発行できるようなパイプライン型のものでよい。機能的ユニットの任意の組合せを設けることもできる。ある実施形態では、機能的ユニットは、整数及び浮動小数点演算(例えば、加算及び乗算)、比較演算、ブール演算(AND、OR、XOR)、ビットシフト、及び種々の代数関数(例えば、平面補間、三角法、指数関数、及び対数関数、等)の組合せ、を含む種々のオペレーションをサポートし、そして同じ機能的ユニットハードウェアをレバレッジして(leveraged)、異なるオペレーションを遂行することができる。
【0030】
[0040]各処理エンジン302は、ローカル入力データ、中間結果、等を記憶するためにローカルレジスタファイル(LRF)304のスペースを使用する。一実施形態では、ローカルレジスタファイル304は、ある数のエントリーを各々有するP個のレーンに物理的又は論理的に分割される(各エントリーは、例えば、32ビットワードを記憶する)。各処理エンジン302に1つのレーンが指定されると共に、異なるレーンの対応エントリーに、同じプログラムを実行する異なるスレッドに対するデータをポピュレートさせて(populated)、同期した並列実行を容易にすることができる。SIMT命令は、スレッドグループの各スレッドに対応する各レーンのレジスタエントリーにアクセスするレジスタオペランド(register operand)を指定することができる。ある実施形態では、各処理エンジン302は、それに指定されたレーンのLRFエントリーにしかアクセスできない。ローカルレジスタファイル304におけるエントリーの全数は、処理エンジン302当たり複数の同時スレッドをサポートするに充分なほど大きいのが好都合である。
【0031】
[0041]又、各処理エンジン302は、コア208内の全処理エンジン302間で共有されて異なるスレッド間でデータを転送するのに使用できるオンチップ共有メモリ306にアクセスすることができる。この共有メモリ306は、希望の大きさのものでよく、ある実施形態では、いずれの処理エンジン302も、等しく低い待ち時間(例えば、ローカルレジスタファイル304へのアクセスに匹敵する)で、共有メモリ306内の任意の位置から読み取り又はそこに書き込むことができる。ある実施形態では、共有メモリ306は、共有レジスタファイルとして実施され、他の実施形態では、共有メモリ306は、共有キャッシュメモリを使用して実施することができる。
【0032】
[0042]共有メモリ306に加えて、ある実施形態では、付加的なオンチップパラメータメモリ及び/又はキャッシュ(1つ又は複数)308も設けられ、これは、例えば、従来のRAM又はキャッシュとして実施されてもよい。パラメータメモリ/キャッシュ308は、例えば、複数のスレッドにより必要になることのある状態パラメータ及び/又は他のデータ(例えば、種々の定数)を保持するのに使用できる。又、処理エンジン302は、メモリインターフェイス214を経てオフチップ「グローバル」メモリ320にアクセスすることができ、これは、例えば、PPメモリ204及び/又はシステムメモリ104を含むことができ、システムメモリ104は、上述したように、メモリインターフェイス214によりホストインターフェイス206を経てアクセスすることができる。PPU202の外部の任意のメモリをグローバルメモリ320として使用してもよいことを理解されたい。処理エンジン302は、この処理エンジン302がグローバルメモリ320にアクセスするのを許す相互接続部(明確に図示せず)を経てメモリインターフェイス214へ結合することができる。
【0033】
[0043]一実施形態では、各処理エンジン302は、マルチスレッド型であり、例えば、ローカルレジスタファイル304の指定レーンの異なる部分における各スレッドに関連した現在状態情報を維持することにより、ある数G(例えば、24)までのスレッドを同時に実行することができる。処理エンジン302は、異なるスレッドからの命令を効率のロスなく任意のシーケンスで発行できるように、あるスレッドから別のスレッドへ急速にスイッチするように設計されるのが好都合である。
【0034】
[0044]命令ユニット312は、所与の処理サイクルに対して、同じ命令(INSTR)をP個の全処理エンジン302へ発行できるように構成される。従って、単一クロックサイクルのレベルにおいて、コア208は、P路(P-way)のSIMT又はSIMD設計を実質的に表わすマイクロアーキテクチャーを実施する。又、各処理エンジン302がマルチスレッド型で、G個までのスレッドを同時にサポートするので、この実施形態のコア208は、同時に実行するP*G個までのスレッドを有することができる。例えば、P=16及びG=24の場合には、コア208が384個までの同時スレッドをサポートする。
【0035】
[0045]命令ユニット312は、同じ命令をP個の全処理エンジン302へ並列に発行するので、コア208は、スレッドグループにおいてスレッドを処理するのに使用されるのが好都合である。ここで使用する「スレッドグループ」とは、グループの1つのスレッドが各処理エンジン302に指定されるようにして、異なる入力データに対して同じプログラムを実行するP個までのスレッドのグループを指す。スレッドグループは、P個より少ないスレッドを含んでもよく、この場合は、そのスレッドグループが処理されるときのサイクル中には処理エンジン302の幾つかがアイドル状態になる。又、スレッドグループは、P個より多くのスレッドを含んでもよく、この場合は、連続するクロックサイクルにわたり処理が行われる。各処理エンジン302は、G個までのスレッドを同時にサポートできるので、コア208において所与の時間にG個までのスレッドのグループを実行できることになる。
【0036】
[0046]各クロックサイクルに、Gスレッドグループの選択された1つを形成しているP個の全スレッドに1つの命令が発行される。どのスレッドが現在アクティブであるか指示するために、関連スレッドに対する「アクティブマスク」を命令と共に含ませることができる。処理エンジン302は、アクティブマスク及びスレッドグループ識別子を使用して、命令を実行するときに、ローカルレジスタファイル304の指定レーンのどの部分を使用すべきか決定する。従って、所与のサイクルに、コア208の全ての処理エンジン302が、同じスレッドグループ内の異なるスレッドに対して同じ命令を同期状態で実行することができる。当業者であれば、スレッドグループ内の各スレッドのこのような同期並列実行がSIMDアーキテクチャーの特徴であることが明らかであろう。スレッドグループ内のスレッドが同期状態で実行するときには、処理エンジン302は、SIMD形態で命令を実行するように構成される。しかしながら、あるインスタンスでは、スレッドグループ内の幾つかのスレッドが、例えば、以下に述べるように、条件付き又は述語型命令、プログラムの分岐点での発散、等のために、一時的にアイドル状態になることがある。処理エンジン302は、SIMD又はSIMTエンジンとして機能するように構成されてもよい。
【0037】
[0047]コア208のオペレーションは、コアインターフェイス303を経て制御されるのが好都合である。ある実施形態では、コアインターフェイス303は、処理されるべきデータ(例えば、原始データ、頂点データ、及び/又はピクセルデータ)、状態パラメータ、及びデータをどのように処理すべきか定義するコマンド(例えば、どんなプログラムを実行すべきか)をワーク配布ユニット210から受け取る。コアインターフェイス303は、処理されるべきデータを共有メモリ306に、そしてパラメータをパラメータメモリ308にロードすることができる。又、コアインターフェイス303は、命令ユニット312において各々の新たなスレッド又はスレッドグループを初期化し、次いで、スレッドの実行を開始するように命令ユニット312に信号する。スレッド又はスレッドグループの実行が完了すると、コア208は、コアインターフェイス303に通知するのが好都合である。次いで、コアインターフェイス303は、他のプロセスを開始し、例えば、共有メモリ306から出力データを検索し、及び/又は付加的なスレッド又はスレッドグループの実行のためにコア208を準備することができる。
【0038】
[0048]ここに述べるコアアーキテクチャーは、例示に過ぎず、変更や修正が考えられることが明らかである。いかなる数の処理エンジンが含まれてもよい。ある実施形態では、各処理エンジンは、それ自身のローカルレジスタファイルを有し、スレッド当たりのローカルレジスタファイルエントリーの割り当ては、固定でもよいし、又は希望の通りに構成できてもよい。更に、1つのコア208しか示されていないが、PPU202は、いかなる数のコア208を含んでもよく、それらコアは、互いに同じ設計のものであって、実行の振舞いが、どのコア208が特定の処理タスクを受け取るかに依存しないようにするのが好都合である。各コア208は、他のコア208とは独立して動作すると共に、それ自身の処理エンジン、共有メモリ、等を有するのが好都合である。
【0039】
[0049]当業者であれば、図1、2及び3に示すアーキテクチャーは、本発明の範囲を何ら限定するものではなく、且つここに教示する技術は、本発明の範囲から逸脱せずに、これに限定されないが、1つ以上のCPU、1つ以上のマルチコアCPU、1つ以上のGPU、1つ以上のマルチコアGPU、等を含む任意の適切に構成された処理ユニットにおいて実施できることが理解されよう。
[スレッドアレー及び協働スレッドアレー]
【0040】
[0050]ある実施形態では、図3のマルチスレッド処理コア208は、スレッドブロック又はスレッドアレーを使用して汎用計算を実行することができる。スレッドアレーは、入力データセットに対して同じプログラムを同時に実行して出力データセットを発生する多数(n0)のスレッドより成る。スレッドアレーの各スレッドには、実行中にスレッドにアクセスできる独特のスレッド識別子(スレッドID)が指定される。このスレッドIDは、スレッドの処理振舞いについての種々の態様を制御する。例えば、スレッドIDを使用して、入力データセットのどの部分をスレッドが処理すべきか決定し、及び/又は出力データセットのどの部分をスレッドが発生し又は書き込むべきか決定することができる。
【0041】
[0051]ある実施形態では、スレッドアレーは、「協働」スレッドアレー即ちCTAとして配列される。各CTAは、入力データセットに対して同じプログラム(ここでは「CTAプログラム」と称される)を同時に実行して、出力データセットを発生するスレッドのグループである。CTAでは、スレッドは、スレッドIDに基づくやり方でデータを互いに共有することにより協働することができる。例えば、CTAでは、データをあるスレッドによって発生し、別のスレッドによって消費することができる。ある実施形態では、データを共有すべきポイントにおいてCTAプログラムコードに同期命令を挿入して、消費側スレッドがデータへのアクセスを試みる前に発生側スレッドによりデータが実際に発生されるよう確保することができる。CTAのスレッド間でのデータ共有がもしあれば、その程度は、CTAプログラムによって決定され、従って、CTAを使用する特定のアプリケーションにおいて、CTAのスレッドは、CTAプログラムに基づいて実際にデータを互いに共有してもよいし、しなくてもよいことを理解されたい。
【0042】
[0052]ある実施形態では、CTAのスレッドは、図3の共有メモリ306を使用して、入力データ及び/又は中間結果を同じCTAの他のスレッドと共有する。例えば、CTAプログラムは、特定のデータを書き込むべき共有メモリ306内のアドレスを計算するための命令を含み、このアドレスは、スレッドIDの関数である。各スレッドは、それ自身のスレッドIDを使用して関数を計算し、そして対応する位置に書き込みを行う。アドレス関数は、異なるスレッドが異なる位置に書き込みを行い、関数が決定論的である限り、スレッドによって書き込まれる位置を予想できるように、定義されるのが好都合である。又、CTAプログラムは、データを読み取るべき共有メモリ306内のアドレスを計算するための命令を含むこともでき、そのアドレスは、スレッドIDの関数である。適当な関数を定義して、同期技術を与えることにより、予想可能なやり方で、CTAの1つのスレッドによって共有メモリ306内の所与の位置にデータを書き込み、そして同じCTAの異なるスレッドによりその位置からデータを読み取ることができる。その結果、スレッド間での希望のデータ共有パターンをサポートすることができ、CTAのいずれのスレッドも、同じCTAの他のスレッドとでデータを共有することができる。
【0043】
[0053]CTA(又は他の形式のスレッドアレー)は、データ並列分解に適した計算を遂行するのに使用されるのが好都合である。ここで使用する「データ並列分解」という語は、入力データに対して同じアルゴリズムを複数回並列に実行して出力データを発生することにより計算上の問題を解決する状態を含み、例えば、データ並列分解の1つの共通のインスタンスは、入力データセットの異なる部分に同じ処理アルゴリズムを適用して、出力データセットの異なる部分を発生することを含む。データ並列分解の影響を受け易い問題は、例えば、マトリクス代数、任意の次元数における線型及び/又は非線型変換(例えば、高速フーリエ変換)、及び種々のフィルタリングアルゴリズムを含み、このフィルタリングアルゴリズムは、任意の次元数のコンボリューションフィルタ、複数次元の分離可能なフィルタ、等を含む。入力データセットの各部分に適用されるべき処理アルゴリズムは、CTAプログラムにおいて指定され、そしてCTA内の各スレッドは、入力データセットの一部分に対して同じCTAプログラムを実行するか、又は出力データセットの一部分を発生する。CTAプログラムは、広範囲の数学的及び論理的オペレーションを使用してアルゴリズムを実施することができ、又、プログラムは、条件付き又は分岐実行経路と、直接的及び/又は間接的メモリアクセスとを含むことができる。
【0044】
[0054]一実施形態では、図1のCPU102で実行されるドライバプログラムは、CTAを定義するコマンドをメモリ(例えば、システムメモリ104)内のプッシュバッファ(明確に図示せず)へ書き込み、これは、PPU202によりコマンドが読み取られるところである。これらコマンドは、CTA内のスレッドの数、CTAを使用して処理されるべき入力データセットのグローバルメモリ320内の位置、実行されるべきCTAプログラムのグローバルメモリ320内の位置、及び出力データを書き込むべきグローバルメモリ320内の位置のような状態パラメータに関連付けられるのが好都合である。この状態パラメータは、コマンドと一緒にプッシュバッファに書き込まれてもよい。コマンドに応答して、コアインターフェイス303は、状態パラメータをコア208(例えば、パラメータメモリ308)へロードし、次いで、CTAパラメータで指定されたスレッドの数が起動されるまでスレッドの起動を開始する。一実施形態では、コアインターフェイス303は、起動されたスレッドにスレッドIDを順次に指定する。より一般的には、CTAの全スレッドが同じコア208において同じプログラムを実行するので、1つのスレッドのみに各有効スレッドIDが指定される限り、いずれのスレッドにいずれのスレッドIDが指定されてもよい。独特の識別子(数字識別子を含むが、これに限定されない)をスレッドIDとして使用することができる。一実施形態では、CTAが、ある数(n0)のスレッドを含む場合には、スレッドIDは、0からn0−1までの単なる逐次(一次元)インデックス値である。他の実施形態では、多次元インデックス機構を使用することができる。スレッドIDを参照することによってデータの共有が制御される限り、処理エンジンにスレッドを特定に指定しても、CTAの実行結果に影響が及ぶことはない。従って、CTAプログラムは、それを実行すべき特定のハードウェアとは独立したものでよい。
[マルチスレッド命令処理]
【0045】
[0055]図4Aは、本発明の1つ以上の態様に基づく、図3の並列処理ユニット202のための命令ユニット312を示すブロック図である。この命令ユニット312は、命令フェッチユニット400と、命令キャッシュ430と、定数キャッシュ410と、ディスパッチャー435と、条件コードユニット450とを備えている。命令フェッチユニット400は、処理されるべきデータと、データを処理するのに使用すべきプログラムに対応するプログラム識別子とを受け取る。アドレスレジスタ445は、プログラム命令によってロードされ及び読み取られるアドレス値を記憶する。スレッドグループ内のスレッドごとにアドレスレジスタ445にレジスタセットがある。本発明のある実施形態では、アドレスレジスタ445は、16ビット値を記憶し、又、他の実施形態では、アドレスレジスタ445は、32ビット値を記憶する。或いは又、アドレス値は、グローバルメモリ320、共有メモリ306、又はローカルレジスタファイル304に記憶される。
【0046】
[0056]プログラムカウンタ記憶装置405は、各スレッドグループに対して実行されるべき次のプログラム命令(INSTR)を指示するアクティブなプログラムカウンタを記憶する。G=24のときには、プログラムカウンタ記憶装置405は、24個のアクティブなプログラムカウンタを記憶する。同様に、スレッド状態記憶装置420は、各スレッドグループに対するアクティブなマスクを記憶し、アクティブなマスクの各ビットは、P個の処理エンジン302の整数に対応する。それ故、アクティブなマスクにおけるビット数は、スレッドグループにおけるスレッドの数である。又、スレッド状態記憶装置420は、各スレッドグループに対するディセーブルマスクも記憶する。ディセーブルマスクは、スレッドグループ内の各スレッドに対してフラグを含む。このフラグは、スレッドがイネーブルされたか、条件付きリターン命令の処理のためにディセーブルされたか、条件付きブレーク命令の処理のためにディセーブルされたか、又はスレッドがプログラムを退出したか、指示する。これら命令の処理、及びディセーブルマスクの決定は、図5A、5B及び7を参照して説明する。
【0047】
[0057]CRS(呼び出し、リターン、同期)スタック425は、図4に実行スタック(0)ないし(G−1)として示された各スレッドグループのための実行スタックを含む。実行スタックは、例えば、トークンタイプ、トークンプログラムカウンタ及びトークンマスクのような状態情報を含むトークンをプッシュ及びポップするために制御命令の処理中に使用される。本発明のある実施形態では、CRSスタック425は、実行スタック455に対してグローバルメモリ320へのエントリーをこぼし、実行スタック455は、オーバーフローし、そしてCRSスタック425にスペースが得られたときにこぼれたエントリーを回復させることができる。コントローラ415は、制御命令が実行されるときにCRSスタック425からエントリーをプッシュ及びポップする。一実施形態では、6つのタイプの制御命令がある。即ち、条件付き分岐命令と、呼び出し命令と、プレブレーク(PreBreak)命令と、プレリターン(PreReturn)命令と、条件付きリターン命令と、同期命令と、条件付きブレーク命令である。別の実施形態は、それより多数又は少数のタイプの制御命令、並びに異なるタイプの制御命令を含んでもよい。
【0048】
[0058]コントローラ415は、スレッドグループに対するアクティブなプログラムカウンタ及びアクティブなマスクを命令キャッシュ430に与える。この命令キャッシュ430は、アクティブなプログラムカウンタに対応する命令を得、そしてその命令及びアクティブなマスクをディスパッチャー435へ出力する。命令キャッシュ430は、当業者に知られたキャッシュ技術を使用して、グローバルメモリ320から命令を必要に応じて読み取る。コントローラ415は、制御命令が実行されるときに条件コードユニット450から制御情報440を経て制御情報を受け取る。この制御情報は、制御命令のタイプを示すトークンタイプと、スタックアンワインド(unwind)信号と、トークンをCRSスタック425にプッシュしそしてスレッドグループに対するアクティブマスク及びディセーブルマスクを更新するのに必要な他のデータとを含む。
【0049】
[0059]定数キャッシュ410は、命令のオペランドとして指定されたインデックス使用して読み取られる値を記憶する。本発明のある実施形態では、スレッドグループに対する定数にアクセスするためにインデックスが使用される。間接的な分岐がサポートされるときには、図4Bを参照して述べるように、関数ポインタが定数キャッシュ410に記憶される。スレッドグループの各スレッドは、異なるインデックスを使用することにより定数キャッシュ410内の異なる定数にアクセスできることに注意されたい。それ故、単一のスレッドグループ内の異なるスレッドは、異なる関数ポインタを使用して分岐し、SIMT処理中に発散を生じ得る。
【0050】
[0060]ディスパッチャー435は、命令をデコードし、そして条件付き制御命令(条件付き分岐、条件付きブレーク、及び条件付きリターン)に対する条件付きデータを条件コードユニット450へ出力する。条件付きデータは、条件テスト及び比較値(制御命令により指定される)を含み、これに対して条件コードが適用される。従来、条件コードは、命令により指定された条件テストを比較値に対して評価し、真又は偽の結果を発生するのに使用される。整数値に対する8つの条件テストのうちの6つは、従来の条件テスト、例えば、より小さい(less than)(LT)、等しい(equal)(EQ)、より大きい(greater than)(GT)、以下(less than or equal)(LE)、以上(greater than or equal)(GE)、及び不等(not equal)(NE)である。条件テストは、比較値が正であるか、ゼロであるか又は負であるか決定するのに使用される。
【0051】
[0061]浮動小数点フォーマット値が使用されるときには、条件テストは、NaN(非数(not-a-number))値のような非順序値に対する振舞いを定義する条件テストも含むことができる。NaNは、数値に対して順序をもたず、それ故、従来の条件テストのための入力として、又は比較値を発生するのに使用されたときには、予期せぬ結果を生じさせる。8つの新たな条件テスト、例えば、LEG、U、LTU、EQU、LEU、GTU、NEU及びGEUは、NaN値の明確なハンドリングを与える。LEG(より小さい、等しい、又はより大きい)は、比較値がゼロ、正又は負であり、即ち順序付けされるときしか真とならない。U(非順序)は、比較値が非順序付けされ、即ちNaNであるときしか真とならない。LTU(ゼロ未満又は非順序)は、比較値が負又はNaNであるときに真となる。EQU(ゼロに等しい又は非順序)は、比較値がゼロ又はNaNであるときしか真とならない。LEU(ゼロ以下又は非順序)は、比較値が負、ゼロ又はNaNのときしか真とならない。GTU(ゼロより大きい又は非順序)は、比較値が正又はNaNであるときしか真とならない。NEU(ゼロに等しくなく又は非順序)は、比較値が正、負又はNaNであるときしか真とならない。GEU(ゼロ以上又は非順序)は、比較値が正、ゼロ又はNaNであるときしか真とならない。
【0052】
[0062]他の2つの従来の条件テスト(整数及び浮動小数点値に対する)は、常に(TR)であって、決して(FL)ではない。オーバーフロー及び桁上げのような付加的な条件テストも使用でき、従って、条件テストの数が増加される。比較値は、プログラムの実行中に計算することができ、スレッドグループ内の各スレッドは、比較値を有してもよい。それ故、条件テストが評価されるときには、あるスレッドは、真の結果を発生し、一方、他のスレッドは、偽の結果を発生することがある。1つ以上のアクティブなスレッドが、他のアクティブなスレッドとは異なる条件テスト結果を生じるときには、スレッドが発散し、CRSスタック435を使用して、分岐の第1の側が実行を完了した後に実行される分岐の側に対してアクティブなマスク及びプログラムカウンタを含むトークンを記憶する。
【0053】
[0063]又、条件付きデータに加えて、ディスパッチャーは、制御命令(呼び出し、ブレーク、リターン、分岐、等)、命令により指定されるターゲットプログラムカウンタ(アドレス)、及びアクティブなマスクを条件コードユニット450へ出力する。制御命令は、ディスパッチャー435によって処理エンジン203へ出力されない。むしろ、条件コードユニット450は、この条件コードユニット450によりコントローラへ出力された制御情報に含まれたアクティブなマスクに基づいて「テークン(taken)」マスクを決定する。より詳細には、条件コードユニット450は、条件テスト結果を使用して、命令により指定されたテスト条件に対して「真」と評価するアクティブなスレッドを指示する「テークンマスク」を決定する。真の比較テスト結果を指示するスレッドグループ内のスレッドに対するこのテークンマスクのビットがクリアされる。アクティブなマスク及びテークンマスクは、ディセーブルマスクを更新するように、コントローラ415によって使用することができる。異なる関数ポインタを有する2つ以上のスレッドで関数呼び出しが遂行されるときには、関数呼び出しが直列化されて、各独特の関数ポインタを指定するスレッドを実行すると共に、テークンマスクを使用して、各独特の関数ポインタに対するアクティブなスレッドを指示する。
【0054】
[0064]条件コードユニット450は、テークンマスク及びトークンタイプを、制御情報440を経てコントローラ415へ出力する。ターゲットプログラムカウンタが呼び出し又は分岐制御命令により指定されるときには、テークンプログラムカウンタが条件コードユニット450により制御情報440を経てコントローラ415へ出力される。トークンタイプは、ディセーブルマスクを発生するために実行された制御命令のタイプを指示する。トークンタイプは、同期、呼び出し、発散、及びブレークを含む。スレッドに対する制御命令が、フライト中(in-flight)であり、即ちコントローラ415により出力されたが制御情報440を経てコントローラ415によりまだ受け取られていないときには、同じスレッドに対する別の命令がコントローラ415により出力されてはならないことに注意されたい。
【0055】
[0065]ディスパッチャー435によって受け取られる他の命令(非制御命令)は、処理エンジン302へ出力するために待ち行列に入れられる。ディスパッチャー435は、命令を処理するのに必要な(計算又は記憶)リソースの利用性に基づき命令を出力するように構成されてもよい。ディスパッチャー435のある実施形態では、スコアボードスキームを使用して、リソースの利用性を追跡すると共に、どの命令を処理エンジン302へ出力できるか決定する。処理エンジン302が命令を受け取ると、その命令を実行するのに必要なオペランドを得るために読み取り要求が発生されて、その読み取り要求がLRF304又は共有メモリ306へ出力される。次いで、命令は、オペランドが得られたときに処理エンジン302によって処理される。
【0056】
[0066]図4Bは、本発明の1つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的な分岐命令の概念図である。スレッドが条件テストを使用して独立して分岐するのを許すのに加えて、コア208は、BRX命令を使用して間接的分岐及び間接的な関数呼び出しをサポートすることを含む。間接的な分岐及び関数呼び出しは、スイッチステートメントのようなC++プログラミング特徴を実施するのに使用される。C++言語は、プロセッサが関数ポインタを経て間接的に関数を呼び出すのを要求するランタイム関数バインディング及びバーチャル関数を使用する。この能力は、関数ポインタをオペランドとして受け容れるBRX命令により各個々のスレッドに対して設けられる。コンパイラーは、BRX命令を使用してスイッチステートメントを実施して、間接的分岐を遂行すると共に、間接的分岐テーブルを構成し、テスト及び分岐の逐次チェーンの発生に比して性能を改善する。間接的な関数呼び出しに対してBRX命令が使用されるときには、PRET(プレリターン)又はCAL(呼び出し)命令(図4Bには示さず)を先行させて、関数リターンアドレスをCRSスタック425にプッシュさせる。
【0057】
[0067]プログラムコード470における分岐命令BRXは、サブルーチンMYSUBに対応する関数ポインタを指定する。コントローラ415は、BRX命令を受け取ると、BRX命令に対してオペランドとして指定されたレジスタを読み取る。この実施例では、アドレスレジスタ445における各スレッドのためのA2レジスタが、スレッドグループにおけるアクティブなスレッドに対するオペランドとして指定され、コントローラ415は、数値定数インデックス472を、命令キャッシュ430へ出力されるBRX命令のためのオペランドとして挿入する。オペランド、例えば、定数インデックス472は、定数キャッシュ410にアクセスするためのスレッドグループインデックスとして使用される。命令キャッシュ430は、BRX命令を受け取ると、定数インデックス472を使用して、スレッドグループ内のアクティブなスレッドに対する関数ポインタのセットを記憶する定数キャッシュ410の1つ以上のエントリーを読み取る。本発明のある実施形態では、一度に1つの定数がアクセスされ、命令キャッシュ430は、読み取った要求を、アドレス値(定数インデックス472)に基づいて直列化する。図4Bに示すように、関数MYSUBを指すポインタ474が定数キャッシュ410のエントリーから読み取られる。
【0058】
[0068]各スレッドに対するアドレスが異なるキャッシュインデックスを指定することがあるので、異なるスレッドに対して定数キャッシュ410から異なる関数ポインタが読み取られることがあることに注意されたい。全てのアクティブなスレッドが同じ関数ポインタを指定しないときには、アクティブなスレッドが発散し、そして各独特の関数ポインタ値に対してBRX命令が実行される。換言すれば、関数ポインタにより指定された異なる関数が、各独特の関数ポインタを共有するスレッドに対して直列に実行される。テークンマスク(taken mask)が制御情報440と共にディスパッチャー435により(条件コードユニット450を経て)コントローラ415へ出力され、第1の独特の関数ポインタを取り上げるスレッドを指示する。コントローラ415は、DIVERGEトークンを、現在のアクティブなマスク及びBRX命令のプログラムカウンタと共に、CRSスタック425にプッシュする。DIVERGEトークンは、図8を参照して述べるように、各独特の関数ポインタに対してBRX命令を繰り返すために、サブルーチンの実行が完了したときにポップされる。
【0059】
[0069]図4Cは、本発明の1つ以上の態様に基づき、スレッドグループの各スレッドに対して1つずつ、スレッドグループに対する関数ポインタのセットを記憶するレジスタを参照する間接的な分岐命令の概念図である。本発明のこの実施形態では、関数ポインタのセットは、アドレスレジスタA2により指定されたアドレスレジスタ445のパー・スレッド(per-thread)エントリーに記憶される。プログラムコード478は、関数ポインタのセット、即ち関数MYSUBを指すポインタ476をアドレスレジスタに直接記憶し、関数ポインタを定数キャッシュ410に記憶するのではない。本発明のある実施形態では、LRF304、共有メモリ306又はグローバルメモリ320のエントリーは、関数ポインタを記憶し、そしてオペランドとして指定され、スレッドグループ内のスレッドが発散して、異なるサブルーチンを実行できるようにする。関数ポインタをアドレスレジスタ445に記憶しない本発明の実施形態では、関数ポインタが、コントローラ415ではなく、処理エンジン302によって読み取られる。
【0060】
[0070]図5Aは、本発明の1つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。当業者であれば、これら方法ステップを任意の順序で遂行するように構成されたいかなるシステムも本発明の範囲内に入ることが理解されよう。ステップ500において、コントローラ415は、アクティブなプログラムカウンタを命令キャッシュ430へ出力することによりスレッドに対するアクティブなプログラムカウンタ(PC)の現在設定に対応するプログラム命令をフェッチする。ステップ505において、ディスパッチャー435は、命令が制御命令であるかどうか決定する。命令が制御命令であることをディスパッチャー435が決定すると、方法は、ステップ507へ進み、ディスパッチャー435は、制御命令を条件コードユニット450へ出力し、そして条件コードユニット450は、制御命令が呼び出し命令であるかどうか決定する。
【0061】
[0071]命令が呼び出し命令であることを条件コードユニット450が決定すると、方法はステップ508へ進み、そして条件コードユニット450は、CALLのトークンタイプ、ターゲットプログラムカウンタ(呼び出し命令により指定された)、テークンマスク(アクティブなマスクに等しい)、及びトークンプログラムカウンタを含む制御情報を出力する。トークンプログラムカウンタは、サブルーチン呼び出しのリターンアドレスであり、スレッドのための次のプログラム命令を指すように増加されたアクティブなプログラムカウンタ、即ち「ノット・テークン(not taken)」プログラムカウンタに等しい。呼び出し命令は、条件付きではないので、テークンマスクは、アクティブなマスクに等しい。又、制御情報は、ディスパッチャー435から受け取ったディセーブルマスクも含み得る。ステップ509において、コントローラ415は、プログラムカウンタ記憶装置405にスレッドグループに対して記憶されたアクティブなプログラムカウンタを、ターゲットプログラムカウンタにセットし、呼び出し命令を実行する。呼び出し命令は、CRSスタック425へトークンをプッシュすることによってネストレベルを高めるので、ディセーブルマスクは不変である。ディセーブルマスクは、ネストレベルを下げる命令が実行され且つCRSスタック425からトークンがポップされたときに変化する。
【0062】
[0072]各制御命令に対してCRSスタック425へプッシュされる異なるトークンがテーブル1に概略的に示されている。本発明のある実施形態では、CRSスタック425各エントリーは、64ビットである。トークンは、トークンタイプと、マスク(トークンマスク)と、トークンがポップされるときにスレッドグループの実行を再開すべき場所を指定するトークンプログラムカウンタとを含む。トークンタイプID_SYNC、ID_DIVERGE、ID_CALL、及びID_BREAKは、各々、SSY命令、分岐(BRA及びBRX)命令、CALL及びPreReturn(PRET)命令、及びPreBreak(PREBRK)命令に対応する。呼び出しトークンに含まれるマスクは、呼び出し/リターン分岐に遭遇したときに存在したアクティブなマスク(active_mask)であり、そして呼び出しトークンにおけるプログラムカウンタは、リターンプログラムカウンタ(not_taken_pc)である。リターンプログラムカウンタは、増加されたアクティブなプログラムカウンタに等しい呼び出し命令に続くプログラムの命令(即ち、フォールスルー(fall-through)命令)を指定する。
【表1】
【0063】
[0073]ステップ507において、制御命令が呼び出し命令でないことを条件コードユニット450が決定すると、方法はステップ510へ進み、そこで、条件コードユニット450は、制御命令がSSY(セット同期)、プレブレーク又はプレリターン命令であるか決定する。制御命令がSSY、PREBRK又はPRET命令であることを条件コードユニット450が決定すると、ステップ512において、条件コードユニット450は、SSY(同期)、PREBRK(プレブレーク)又はPRET(プレリターン)のトークンタイプ、テークンマスクとしてのアクティブなマスク、及びコントローラ415への命令によりトークンプログラムカウンタとして指定されたtarget_pc(ターゲットプログラムカウント)を含む制御プログラムを出力し、そしてコントローラ415は、CRSスタック425にトークンをプッシュする。トークンに含まれたトークンマスクは、アクティブなマスクであり、SSY、PREBRK及びPRET命令は、CRSスタック425にトークンをプッシュするので、ディセーブルマスクは不変である。ステップ514では、コントローラ415は、プログラムカウンタ記憶装置405にスレッドに対して記憶されたアクティブなプログラムカウンタを増加して、スレッドに対する次の命令を指すようにする。
【0064】
[0074]ここで、ステップ505に戻ると、命令が制御命令でないとディスパッチャー435が決定した場合には、方法はステップ520へ進み、ディスパッチャー435は、スレッドグループ内のスレッドを同期しなければならないことを示すpop sync(同期)フラグを命令が含むかどうか決定する。pop syncフラグは、SSY命令の逆の意味を有する。pop syncフラグは、最後のSSY命令がsyncトークン(トークンタイプSSY)をCRSスタック425へプッシュさせたために発散したスレッドグループのスレッドが、pop syncフラグを含む命令に対して実行されるべきであることを指示する。ここに詳細に述べるように、このプロセスは、この最後のsyncトークンがCRSスタック425へプッシュされたときに存在したスレッド同期のレベルを再確立する。換言すれば、このプロセスは、最後のSSY命令に遭遇したときに存在したスレッド同期のレベルを再確立し、最後のSSY命令により指定されたターゲットアドレス(SSYトークンのトークンプログラムカウンタ)において実行を開始する。好ましい実施形態では、同期オペレーションは、キャリア命令(即ち、pop syncフラグを含む命令)の他のオペレーションの前に行われる。別の実施形態では、同期オペレーションは、個別の命令を使用して行われてもよいし、或いはキャリア命令の他のオペレーションの後に同期オペレーションを行うこともできる。制御命令は、pop syncフラグのためのキャリア命令ではないことに注意されたい。
【0065】
[0075]ステップ520において、命令がpop syncフラグを含むとディスパッチャー435が決定すると、ステップ525において、ディスパッチャー435は、条件コードユニット450を経てコントローラ415へ制御情報を出力し、コントローラ415は、CRSスタック425をアンワインド(unwind)するように進み、スレッドグループ内の(アクティブな)スレッドの同期をとる。コントローラ415へ出力される制御情報は、CRSスタック425をアンワインドしなければならないことを指示するアンワインドスタック信号を含む。キャリア命令は、スタックがアンワインドされ且つアクティブなスレッドが同期された後に実行される。ステップ525の詳細は、図5Bを参照して説明する。
【0066】
[0076]ステップ520において、命令がpop syncフラグを含まないとディスパッチャー435が決定すると、ステップ522において、ディスパッチャー435は、命令を処理エンジン302へ実行のために出力する。ステップ527において、ディスパッチャー435は、条件コードユニット450を経てコントローラ415へ増加PC信号を含む制御情報を出力し、そしてコントローラ415は、スレッドに対してプログラムカウンタ記憶装置405に記憶されたアクティブなプログラムカウンタを増加する。或いは又、増加されたアクティブなプログラムカウンタがコントローラ415へ出力される。
【0067】
[0077]ここで、ステップ510へ戻ると、制御命令がSSY、PREBRK又はPRET命令でないことを条件コードユニット450が決定した場合には、ステップ530において、条件コードユニット450は、制御命令が分岐命令であるかどうか決定する。分岐命令は、非条件付き分岐及び条件付き分岐命令(BRA)と、非条件付き間接的分岐及び条件付き間接的分岐命令(BRX)とを含む。BRX命令は、1つ以上の関数ポインタをBRXへのオペランドとして指定することにより間接的な関数呼び出しを実行するように使用される。
【0068】
[0078]間接的な分岐命令は、分岐アドレス(関数ポインタ)をコンパイル時に決定する必要がないので、より大きな融通性を許すように使用できる。分岐ターゲットレジスタは、スレッドグループ内の全てのスレッドに使用される単一分岐アドレス(又は定数インデックス)を記憶することができる。分岐ターゲットレジスタには、プログラムの実行中に、計算値を書き込むことができる。或いは又、スレッドグループ内の各スレッドが、間接的な分岐命令に対して異なる分岐アドレスを指定し(直接的に又は定数キャッシュ410のインデックスとして)、テーブル1に示すY(1)発散を生じてもよい。各スレッドに対して分岐アドレス(1つ又は複数)が読み取られて、P路の間接的分岐を許す。各独特の分岐アドレス及び最後の独特の分岐アドレスに対して間接的な分岐命令が実行され、テーブル1に示すY(2)発散を生じ、ここで、ノット・テークンプログラムカウンタがCRSスタック425にプッシュされる。スレッドは、条件付き分岐内の間接的な関数呼び出しのために発散し得ることに注意されたい。図8を参照して述べるように、各独特の分岐アドレスに対してスレッドの実行が直列化されるときにアクティブであるスレッドを指示するためにアクティブなマスクが使用される。
【0069】
[0079]ステップ530において、制御命令が分岐命令でないことを条件コードユニット450が決定すると、それはリターン又はブレーク命令であり、そして呼び出し/リターン分岐に関連したサブルーチンの終了、又はプレブレーク分岐に関連した命令のループの終了に到達し、方法はステップ532へ進む。ステップ532において、条件コードユニット450は、コントローラ415へ出力されるテークンマスクを発生し、コントローラ415は、アクティブなスレッドの1つ以上が条件テスト結果に基づいて発散するかどうか決定する。条件付きリターン又はブレーク命令によって指定された条件テストに対して真と評価するアクティブなスレッドは、いずれも、テークンマスクによりディセーブルされる。これらのスレッドは、他のアクティブなスレッド(条件テストに対して偽と評価する)が実行を続ける間に、ディセーブルされてアイドル状態に保たれる。ディセーブルされたスレッドに対応するビットは、テークンマスクにおいてクリアされ、テークンマスクにおいてセットされたビットの数が、アクティブなマスクにおいてセットされたビットの数以下となるようにする。
【0070】
[0080]ステップ532において、スレッドが発散しない(テークンマスクがアクティブなマスクに等しい)ことをコントローラ415が決定すると、ステップ525において、コントローラ415は、CRSスタック425をアンワインド(unwind)するように進む。アンワインドプロセス中に、リターン又はブレーク命令によりディセーブルされたスレッドは、図5Bを参照して更に説明するように、それに対応する呼び出しトークン(ID_CALL)又はプレブレークトークン(ID_BREAK)がCRSスタック425からポップされたときにイネーブルされる。
【0071】
[0081]ステップ532において、スレッドが発散する(テークンマスクがアクティブなマスクに等しくない)ことをコントローラ415が決定すると、ステップ534において、コントローラ415は、変更されたディセーブルマスクを決定する。これらスレッドに対するディセーブルマスクの状態は、taken_maskビットがセットされたスレッドが、特定事象を待機する間アイドル状態であることを指示する値にセットされる。この事象は、プログラムの終了であるか、又はCRSスタック425からポップされるべき特定のトークンに対するものである。
【0072】
[0082]本発明のある実施形態では、0のディセーブル状態は、スレッドがイネーブルされることを指示し、1のディセーブル状態は、スレッドがリターン命令を実行し、且つCRSスタック425からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、2のディセーブル状態は、スレッドがブレーク命令を実行し、且つCRSスタック425からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして3のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。
【0073】
[0083]ステップ536において、コントローラ415は、アクティブなマスクを変更する。より詳細には、「条件を取り入れた」スレッドグループ内のスレッドに対応するアクティブなマスクのビットがクリアされて、それらのスレッドが非アクティブとして現れるようにする。換言すれば、テークンマスクとアクティブなマスクとの間でビットワイズのXOR(排他的OR)が遂行され、変更型アクティブマスクを生成する。ステップ539では、コントローラ415が、スレッドに対する次の命令を実行するために、アクティブなプログラムカウンタを増加する。
【0074】
[0084]ここで、ステップ530に戻ると、制御命令が分岐命令であることを条件コードユニット450が決定すると、ステップ535において、コントローラ415は、条件コードユニット450により与えられたテークンマスクに基づいていずれかのアクティブなスレッドが発散するかどうか決定する。ステップ535において、条件コードユニット450は、テークンマスク、トークンタイプ、及びターゲットプログラムカウンタを含む制御情報をコントローラ415へ出力する。ステップ535において、少なくとも1つのアクティブなスレッドがスレッドグループ内の他のアクティブなスレッドから発散することをコントローラ415が決定すると、ステップ537において、コントローラ415は、発散トークン(ID_DIVERGE)をCRSスタック425にプッシュする。トークンに含まれたトークンマスクは、ノット・テークンマスク(not_taken_mask)であり、これは、条件テストに対して「真」と評価しないアクティブなスレッド、即ち分岐をとらないアクティブなスレッドを指示する。コントローラ415は、テークンマスク及びアクティブなマスクを使用してトークンマスクを決定することができる。トークンプログラムカウンタは、スレッドにおいて次の命令を指定するために増加されるアクティブなプログラムカウンタに等しい。
【0075】
[0085]ステップ540において、コントローラ415は、条件テストに対して「真」と評価し即ち分岐をとるアクティブなスレッドを指示するテークンマスクとしてアクティブなマスクを決定する。ステップ545において、コントローラ415は、アクティブなプログラムカウンタを、分岐命令により指定されたターゲットプログラムカウンタ(アドレス)にセットする。
【0076】
[0086]ステップ535において、アクティブなスレッドがどれも発散しないとコントローラ415が決定すると、ステップ542において、コントローラ415は、全てのアクティブなスレッドが分岐をとるかどうか決定する。それに代わるものとして、アクティブなスレッドがいずれも分岐をとらない場合には、条件コードユニット450が、0x0000に等しいテークンマスクを出力する。ステップ544において、コントローラ415は、スレッドにおいて次の命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置405に記憶されたアクティブなプログラムカウンタを増加する。ステップ542において、全てのアクティブなスレッドが分岐をとるとコントローラ415が決定すると、ステップ545において、コントローラ415は、コントローラ415への分岐命令により指定されたターゲットプログラムカウンタ(アドレス)に等しくなるようにアクティブなプログラムカウンタを更新し、そしてコントローラ415は、分岐により指定された命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置405に変更されたアクティブなプログラムカウンタを記憶する。
【0077】
[0087]CRSスタック425を使用すると、PPU202は、スレッドの発散及び同期を行いながら、スレッドグループを処理できるようになる。ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状の条件及びサブルーチン内のスレッド完了を含む更に進歩した制御フローをサポートするのに使用される。各スレッドグループに対して単一のディセーブルマスクがスレッド状態記憶装置420に記憶され、そしてディセーブルマスクは、CRSスタック425からポップされたトークンと結合されて、ディセーブルされたスレッドグループ内のスレッドの実行を再開する。
【0078】
[0088]図5Bは、本発明の1つ以上の態様に基づき図5Aのステップ525を完了するためにCRSスタック425をアンワインド(unwinding)する方法ステップのフローチャートである。CRSスタック425は、処理エンジン302により同時に実行できるGスレッドグループの各々に対して実行スタック455を備え、各スレッドグループが、他のスレッドグループとは独立して進行できるようにする。ステップ550において、コントローラ415は、スレッドグループに対する実行スタック455が空であるかどうか決定し、もしそうであれば、ステップ552において、スレッドグループの実行が完了し、そして命令ユニット312は、スレッドグループが実行を完了したことをコアインターフェイス303に通知する。ステップ550において、実行スタック455が空でないことをコントローラ415が決定すると、ステップ555において、コントローラ415は、実行スタック455から実行スタック455の最上部にトークンをポップさせる。ステップ560において、コントローラ415は、トークンが呼び出し又はプレブレークトークンであるかどうか決定し、そしてトークンが呼び出し又はプレブレークトークンでないときには、ステップ570へ直接進む。
【0079】
[0089]呼び出しトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きリターン命令の実行を完了しそして(ディセーブルマスクに基づいて)ディセーブルされたスレッドをイネーブルすべきであることを指示する。プレブレークトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きブレーク命令の実行を完了しそして(ディセーブルマスクに基づいて)ディセーブルされたスレッドをイネーブルすべきであることを指示する。スレッドグループ内のアクティブなスレッドは、トークンと共に記憶されるマスク、即ちトークンマスクにより指示される。重要なことに、呼び出し及びプレブレークループをネスト状にできるように、ディセーブルマスクを使用して、スレッドグループ内のスレッドをディセーブルする。ステップ560において、コントローラ415は、トークンが呼び出し又はプレブレークトークンであることを決定し、次いで、ステップ565において、コントローラ415は、スレッドに対してディセーブルマスクを更新する。より詳細には、トークンが呼び出しトークンであるときには、コントローラ415は、スレッドが条件付きリターン命令によってディセーブルされたことを指示する1のディセーブル状態をもち且つ呼び出しトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。トークンがプレブレークトークンであるときには、コントローラ415は、スレッドが条件付きブレーク命令によってディセーブルされたことを指示する2のディセーブル状態をもち且つプレブレークトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。
【0080】
[0090]ステップ560において、トークンが呼び出しトークンでもプレブレークトークンでもないことをコントローラ415が決定すると、トークンは、sync又は発散のいずれかのトークンである。ステップ570において、コントローラ415は、アクティブなマスクをトークンからのマスクにセットし、次いで、ディセーブルされたスレッドを除去することにより、アクティブなマスクを更新する。より詳細には、ディセーブルされたことを指示するディセーブル状態を有するスレッドは、それらスレッドが誤って実行を再開するのを防止するために、(トークンから)更新されたアクティブなマスクにおけるそれらの対応ビットをクリアしている。これは、スレッドがイネーブルされないことをディセーブル状態が指示する限り、スレッドがインアクティブのままであることを保証する。換言すれば、アクティブなマスクは、スレッドグループ内の他のスレッドが条件付きブレーク又はリターン分岐の実行を完了するのを待っているスレッドグループ内のいずれかのスレッドの処理をディセーブルするように更新される。
【0081】
[0091]ステップ575において、コントローラ415は、更新されたアクティブなマスクがゼロに等しく、スレッドグループ内のどのスレッドもアクティブでないことを指示するかどうか決定する。ステップ575において、どのスレッドもアクティブでないことをコントローラ415が決定すると、方法はステップ550へ戻り、別のトークンをポップする(又はプログラムの実行を完了する)。さもなければ、ステップ580において、コントローラ415は、アクティブなプログラムカウンタを、ステップ555においてポップされたトークンからのプログラムカウンタにセットする。
【0082】
[0092]テーブル4に戻ると、呼び出しトークンのプログラムカウンタは、リターンプログラムカウンタである。アクティブなプログラムカウンタをリターンプログラムカウンタに等しくセットすることで、アクティブなスレッドが、呼び出し命令に続くプログラムの命令(即ち、フォールスルー命令)にリターンすることが規定される。ブレークトークンにおけるプログラムカウンタは、ループ後プログラムカウンタ(after-loop program counter)である。アクティブなプログラムカウンタをこのループ後プログラムカウンタにセットすることで、アクティブなスレッドが、ループ後プログラムカウンタにより指定されたアドレスをもつ命令へ分岐することが規定される。
【0083】
[0093]syncトークンに含まれたマスクは、それに対応するSSY命令が実行されたときに存在したアクティブなマスクである。従って、アクティブなマスクを、syncトークンに含まれたマスクに等しくセットすると、SSY命令に最初に遭遇したときにアクティブであったスレッドであって、介在する条件付きリターン又はブレーク命令によりディセーブルされるスレッドを除く全てのスレッドをアクチベートする。syncトークンに含まれたプログラムカウンタは、SSY命令により指定されたプログラムカウンタである。
【0084】
[0094]分岐及び間接的分岐のための発散トークンに含まれたマスクは、ノット・テークン(not taken)マスクである。一実施形態では、アクティブなマスクをノット・テークンマスクにセットすることは、発散トークンに関連した条件付き分岐の「イフ・サイド(if-side)」を実行する必要のあるスレッドをアクチベートする一方、その分岐の「エルス・サイド(else-side)」の実行を丁度完了したスレッドをインアクチベートするように作用する。2路発散を伴う分岐及び間接的分岐に対して発散トークンに含まれたプログラムカウンタは、ノット・テークンプログラムカウンタである。アクティブなプログラムカウンタをノット・テークンプログラムカウンタにセットすることで、新たにアクチベートされるスレッドが、条件付き分岐の「イフ・サイド」で第1の命令を実行することが規定される。このプロセスは、条件付き分岐の「イフ・サイド」の実行をイネーブルする。P路発散を伴う間接的分岐に対して発散トークンに含まれたプログラムカウンタは、アクティブなプログラムカウンタである。それ故、BRX命令は、各独特の分岐アドレスに対して実行される。
【0085】
[0095]テーブル2は、図5Bの方法ステップに対するCプログラミング言語擬似コードを示し、disable_mask.returnは、スレッドが呼び出しトークンを待機するときにアサートされ、disable_mask.breakは、スレッドがブレークトークンを待機するときにアサートされ、そしてdisable_mask.eosは、スレッドがプログラムを退出するときにアサートされる。図5Aを参照して既に説明したように、本発明のある実施形態では、1のディセーブル状態は、スレッドがリターン命令を実行し、且つCRSスタック425からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、2のディセーブル状態は、スレッドがブレーク命令を実行し、且つCRSスタック425からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして3のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。それ故、これらの実施形態では、disable_mask.returnは、ディセーブル状態が1であるときにアサートされ、disable_mask.breakは、ディセーブル状態が2であるときにアサートされ、そしてdisable_mask.eosは、ディセーブル状態が3であるときにアサートされる。
【表2】
【0086】
[0096]ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状条件及びサブルーチン内のスレッド完了、を処理するのに使用される。ディセーブルマスクの使用に代わるものは、スレッドディセーブル事象(条件付きリターン又はブレーク)が生じたときに実行スタック455をウオーク(walk)し、そして全ての関連トークンにおけるセーブされたアクティブなマスクを変更することである。しかしながら、実行スタック455をウオークすることは、実行スタック455が非常に深くて、グローバルメモリ320に記憶された部分を伴うので、潜在的に時間浪費である。それ故、ディセーブルマスクは、性能に関して効果的であり、同時に実行できるG個のスレッドの各々に対して1つのマスクしか必要としない。
【0087】
[0097]テーブル3は、本発明の1つ以上の態様を例示するために「イフ・ゼン・エルス(if-then-else)」ステートメントを実施する分岐命令を含むプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表3】
【0088】
[0098]図6は、本発明の1つ以上の態様に基づき、テーブル3に示すプログラム命令のシーケンスが実行されるときに、CRSスタック425内の実行スタックをどのようにポピュレート(populated)しアンワインド(unwound)するかを概念的に例示する。
【0089】
[0099]図示されたように、欄600は、命令ユニット312がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄605は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。又、アクティブなプログラムカウンタは、0の初期値を有すると仮定する。
【0090】
[00100]コントローラ415は、最初に、0のプログラムカウンタ値に対応するMAD命令をフェッチする(ステップ500)。MAD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x1に増加される(ステップ527)。次いで、コントローラ415は、SSY命令をフェッチし、そしてトークンタイプSYNC、アクティブなマスク(0xff)、及びSSY命令により指定されたターゲットプログラムカウンタ(LABEL1、PC=7)を含むsyncトークンを実行スタック455にプッシュする(ステップ512)。欄610は、各プログラム命令が実行された後に実行スタック455の最上部にあるトークンを示す。アクティブなプログラムカウンタは、0x2へ増加される(ステップ514)。
【0091】
[00101]次いで、コントローラ415は、条件xがゼロ未満である場合にターゲットプログラムカウンタアドレスLABEL0(PC=6)へ分岐するBRA LT.x命令をフェッチする。BRA命令は、条件付き分岐命令であり、分岐テークン(taken)経路及びノット・テークン(not-taken)経路を決定するために条件テストが使用される。BRA命令により指定された条件テスト(即ち、xは、0未満)を満足し、従って、分岐をとって、「イフ・ゼン・エルス(if-then-else)」ステートメントの「エルス・サイド」を実行するために、6つのスレッドが仮定される。1つ以上のアクティブなスレッドが発散するので、コントローラ415は、発散トークン(DIV)を実行スタック455にプッシュする(ステップ537)。欄615は、各プログラム命令が実行された後に実行スタック455の最上部より1エントリー下のトークンTOS−1(スタックの最上部・マイナス・1)を示す。
【0092】
[00102]発散トークンに含まれるマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、条件テストを満足しなかった2つのスレッドを反映する。これら2つのスレッドは、分岐テークンのエルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、0xf3であり、アクティブなマスクは、テークンマスクにセットされる。発散トークンに含まれるプログラムカウンタは、0x3の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第1命令(即ち、フォールスルー命令)のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、0x6のターゲットプログラムカウンタにセットされる(ステップ545)。
【0093】
[00103]次いで、コントローラ415は、ADD命令をフェッチする。ADD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x7に増加される(ステップ527)。次いで、コントローラ415は、pop−syncフラグ(.S)を含むMAX.S命令をフェッチする。pop−syncフラグは、命令がプログラム内の同期ポイントであることを指定する。pop−syncフラグが含まれるので、コントローラ415は、BRA LT.xによりプッシュされた発散トークンをポップし(ステップ555)、そしてアクティブなマスクを0xcへ更新すると共に、アクティブなプログラムカウンタを0x3にセットすることにより(ステップ570、575及び580)、実行スタック455をアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL命令をフェッチする(条件付き分岐のイフ・サイド)。MUL命令は制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x4に増加される(ステップ527)。
【0094】
[00104]次いで、コントローラ415は、次のMUL命令(条件付き分岐のイフ・サイドに対する第2の命令)をフェッチする。このMUL命令も制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x5に増加される(ステップ527)。
【0095】
[00105]次いで、コントローラ415は、LABEL1のターゲットプログラムカウンタ(PC=7)を指定するBRA命令をフェッチする。BRA命令は、常にとられる無条件命令であり、それ故、アクティブなスレッドは発散しない。アクティブなスレッドは、全て、分岐をとるので、アクティブなプログラムカウンタは、0x7のターゲットプログラムカウンタにセットされる(ステップ535、542及び545)。
【0096】
[00106]次いで、コントローラ415は、pop−syncフラグ(.S)を含むMAX.S命令をフェッチし、そしてSSYによってプッシュされたsyncトークンをポップする(ステップ555)と共に、アクティブなマスクを0xffに更新し且つアクティブなプログラムカウンタを0x7にセットする(ステップ570、575及び580)ことにより、実行スタックをアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MAX.S命令をフェッチし、スレッドが同期される(アクティブなマスクが0xffである)ので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x8に増加される(ステップ527)。コントローラ415は、キャリア命令(MAX)を実行するために、実行スタック455がアンワインドされてMAX.S命令の.S部分を処理した後に、pop−syncフラグを無視しなければならないことに注意されたい。それ故、syncトークンがポップされると、コントローラ415は、syncトークンがポップされたときにセットされ且つキャリア命令が実行されるときにクリアされる状態のビットを各スレッドグループに対して維持する。
【0097】
[00107]テーブル4は、本発明の1つ以上の態様を例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表4】
【0098】
[00108]テーブル5は、テーブル4のプログラム命令のサブルーチン部分に対するCプログラミング言語擬似コードを示す。
【表5】
【0099】
[00109]図7は、本発明の1つ以上の態様に基づき、条件付きリターンを含むテーブル4及び5に示すプログラム命令のシーケンスが実行されるときに、実行スタック455内の実行スタック455をどのようにポピュレート(populated)し、アンワインド(unwound)するかを示す別の概念図である。図示されたように、欄700は、命令ユニット312がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄705は、各プログラム命令が実行される前のアクティブなマスクの値を示す。欄710は、各プログラム命令が実行される前のディセーブルマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。又、アクティブなプログラムカウンタは、50の初期値を有すると仮定する。
【0100】
[00110]コントローラ415は、先ず、SUBROUTINEのターゲットプログラムカウンタ(PC=0)を指定するアドレス50においてCALL命令をフェッチする。トークンタイプCALL、アクティブなマスク(0xff)及びターゲットプログラムカウンタを含む呼び出しトークンが実行スタック455にプッシュされる(ステップ508)。全てのアクティブなスレッドがコールをとるので、アクティブなプログラムカウンタは、0x0のターゲットプログラムカウンタにセットされる(ステップ509)。欄715は、各プログラム命令が実行された後に実行スタック455の最上部にあるトークンを示す。
【0101】
[00111]次いで、コントローラ415は、SSY命令をフェッチし、そしてトークンタイプSYNC、アクティブなマスク(0xff)、及びSSY命令により指定されたターゲットプログラムカウンタ(LABEL1、PC=7)を含むsyncトークンを実行スタック455にプッシュする(ステップ512)。欄720は、各プログラム命令が実行された後に実行スタック455の最上部より1エントリー下にあるトークンTOS−1(スタックの最上部・マイナス・1)を示す。アクティブなプログラムカウンタは、0x2へ増加される(ステップ514)。
【0102】
[00112]次いで、コントローラ415は、xにより指定された比較値及びLABEL0(PC=6)のターゲットプログラムカウンタでLT条件テストを指定するBRA命令をフェッチする。1つ以上のアクティブなスレッドが発散するので、コントローラ415は、発散トークン(DIV)を実行スタック455にプッシュする(ステップ537)。欄725は、各プログラム命令が実行された後に実行スタック455の最上部より2エントリー下にあるトークンTOS−2(スタックの最上部・マイナス・2)を示す。
【0103】
[00113]発散トークンに含まれたマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、逆の条件テストを満足しなかった2つのスレッドを反映する。これら2つのスレッドは、エルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、0xf3であり、アクティブなマスクは、欄705に示すように、テークンマスクに等しくセットされる(ステップ540)。発散トークンに含まれるプログラムカウンタは、0x2の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第1命令(即ち、フォールスルー命令)のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、0x5のターゲットプログラムカウンタにセットされる(ステップ545)。
【0104】
[00114]次いで、コントローラ415は、xにより指定された比較値でGT条件テストを指定するRET命令をフェッチする。1つ以上のアクティブなスレッドが発散するので、条件コードユニット450は、ディセーブルマスクを決定する(ステップ534)。変更型ディセーブルマスクは、0x0005である(各スレッドが2ビットフラグを有する)。というのは、アクティブなスレッドのうちの2つが条件テストを満足し、フラグを1にセットして、呼び出し命令を待機しているディセーブル状態を指示するからである。条件コードユニット450は、ディセーブルされたスレッドの実行をディセーブルするようにアクティブなマスクを変更する。それ故、アクティブなマスクは、0xf3から0xf0へ変化する(ステップ536)。最終的に、アクティブなプログラムカウンタは、0x6の値に増加される(ステップ539)。
【0105】
[00115]次いで、コントローラ415は、ADD命令をフェッチする。ADD命令は、制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x7に増加される(ステップ527)。次いで、コントローラ415は、pop−syncフラグ(.S)を含むMUL.S命令をフェッチする。pop−syncフラグが含まれるので、コントローラ415は、BRA発散トークンをポップし(ステップ555)、そしてアクティブなマスクを0xcへ更新すると共に、アクティブなプログラムカウンタを0x2にセットすることにより(ステップ570、575及び580)、実行スタック455をアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL命令をフェッチする(条件付き分岐のイフ・サイド)。MUL命令は制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x3に増加される(ステップ527)。
【0106】
[00116]次いで、コントローラ415は、次のMUL命令(条件付き分岐のイフ・サイドに対する第2の命令)をフェッチする。このMUL命令も制御命令ではなく、pop−syncフラグを含まないので、処理エンジン302がこの命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x4に増加される(ステップ527)。
【0107】
[00117]次いで、コントローラ415は、LABEL1のターゲットプログラムカウンタ(PC=7)を指定する(無条件)BRA命令をフェッチする。アクティブなスレッドは、全て分岐をとるので、アクティブなプログラムカウンタは、0x7のターゲットプログラムカウンタにセットされる(ステップ535、542及び545)。
【0108】
[00118]次いで、コントローラ415は、pop−syncフラグ(.S)を含むMUL.S命令をフェッチし、そしてSSYのsyncトークンをポップする(ステップ555)と共に、アクティブなマスクを0xfcに更新し且つアクティブなプログラムカウンタを0x8にセットする(ステップ570、575及び580)ことにより、実行スタックをアンワインド(unwinds)する(ステップ525)。次いで、コントローラ415は、MUL.S命令をフェッチし、又、.S部分が実行されると共にスレッドが同期されるので、処理エンジン302は、この命令を実行し(ステップ522)、アクティブなプログラムカウンタが0x8に増加される(ステップ527)。次いで、コントローラ415は、RET命令をフェッチし、そして呼び出しトークンをポップする(ステップ555)ことにより実行スタックをアンワインドする(ステップ532及び525)。コントローラ415は、呼び出しトークンを待機してディセーブルされたスレッドに対してディセーブル状態をクリアすることによりディセーブルマスクを更新する(ステップ565)。次いで、コントローラ415は、アクティブなマスクを0xffへ更新し、アクティブなプログラムカウンタを0x51にセットする(ステップ570、575及び580)。次いで、コントローラ415は、ADD命令をフェッチして、ADD命令を処理エンジン302へ実行のために出力する。
【0109】
[00119]テーブル6は、本発明の1つ以上の態様に基づいてBRX命令を使用して間接的な関数呼び出しを遂行することを例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされ、命令の実行は、図8を参照して詳細に説明する。
【表6】
【0110】
[00120]関数ポインタを経て間接的な関数呼び出しを可能にするために、BRX命令のターゲット(関数ポインタ)におけるプログラムコードは、分岐に使用される.S同期命令ではなくRET命令で終了する。PRET命令は、スレッド同期のための現在のアクティブなマスク(これは、BRX命令に関連した全ての関数呼び出しの実行後に生じる)を使用して、CRSスタック425にプッシュされたリターンアドレスをCALLトークンとして指定する。BRX命令は、PRET命令に従い、それが実行されるとき、アクティブなスレッドの少なくとも1つが、BRXオペランドにより指定された関数へ間接的に分岐する。その後のRET命令が実行されるときには、他のアクティブなスレッドに対する既に延期された間接的な関数呼び出しの実行が、スレッド指定関数ポインタを使用して、BRX命令の繰り返し実行により完了される。BRX命令に対して最後の関数呼び出しが実行されるときには、最終的なRET命令が、PRET命令によりCRSスタック425にプッシュされたCALLトークンをポップし、そしてCALLトークンと共にポップされるアクティブなマスクに基づいてスレッドが同期される状態でリターンアドレスへ制御を移行する。
【0111】
[00121]テーブル7は、テーブル6のプログラム命令のサブルーチン部分に対するCプログラミング言語擬似コードを示す。
【表7】
【0112】
[00122]図8は、本発明の1つ以上の態様に基づき、間接的な関数呼び出しを含むテーブル6に示すプログラム命令のシーケンスが実行されるときにCRSスタック425がどのようにポップされアンワインド(unwound)されるかを示す別の概念的な図である。図示されたように、欄800は、命令ユニット312がプログラム命令を実行する順序を示すと共に、各プログラム命令に対するアクティブなプログラムカウンタを指定する。欄805は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、8つのスレッドを含み、そして8つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、0xffである。この実施例では、条件付き分岐命令の実行のためにディセーブルされるスレッドはない。又、アクティブなプログラムカウンタは、4の初期値を有すると仮定する。
【0113】
[00123]第1の命令IADD .C1がフェッチされ、R2とR3に記憶された値の差が計算されて、条件コードレジスタC1に記憶される。CRSスタック425にプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは5に増加される。第1の条件付きR2A命令がフェッチされ、条件テスト(LT)が条件コードC1に対して評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。条件コード指定子(C1)及びテストされるべき特定の条件(LT)は、行先レジスタに続きカッコで示されるA1。MYSUB1を指す関数ポインタを記憶する定数キャッシュ410のエントリーに対応する定数インデックス(i0)は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ445のA1エントリーに記憶される。換言すれば、値2(MY_SUB1に対応するプログラムカウンタ)は、条件コードC1が「より少ない(less than)」条件にセットされるところの全てのスレッドに対してA1へ移動される。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは6に増加される。第2の条件付きR2A命令がフェッチされると共に、第2の条件テスト(GE)が評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。MYSUB2を指す関数ポインタを記憶する定数キャッシュ410のエントリーに対応する定数インデックス(i2)は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ445のA1エントリーに記憶される。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは7に増加される。
【0114】
[00124]MOV命令がフェッチされて実行され、関数の引数として値2を通す。CRSスタック425へプッシュされるトークンはなく、現在アクティブなマスクは不変であり(0xff)、そしてアクティブなプログラムカウンタは8に増加される。PRET命令がフェッチされ、コントローラ415は、呼び出しトークン(CAL)を実行スタック455にプッシュする。欄805に示すように、TOS(スタックの最上部)は、0xffのマスク(現在アクティブなマスク)と、AFTER_FUNCTIONの第1命令のアドレス(10)に対応する0xaのプログラムカウンタ(PRET命令により指定される)とを含むプッシュされた呼び出しトークンを記憶する。
【0115】
[00125]間接的分岐命令BRXがフェッチされ、コントローラ415は、アドレスレジスタ445のA2エントリーに記憶された定数インデックスをBRX命令に挿入する。この実施例では、0xf3が、インデックスi0(MYSUB1)を参照するスレッドに対するテークンマスクであり、且つ0x0cが、インデックスi2(MYSUB2)を参照するスレッドに対するテークンマスクであると仮定する。コントローラ415は、各独特の関数ポインタに対してBRX命令の実行を直列化する。BRX命令は、発散トークン(DIV)を実行スタック455へプッシュする。欄815は、プログラム命令が実行された後に実行スタック455の最上部より1エントリー下にあるトークンTOS−1(スタックの最上部・マイナス・1)を示す。発散トークンに含まれたマスクは、0x0cの値を有し、これは、ノット・テークンマスクであり、MYSUB1へ間接的に分岐しなかった6つのスレッドを指示する。発散トークンに含まれるプログラムカウンタは、9の値を有し、これは、BRX命令のアドレスである。現在アクティブなマスクは0xf3へ更新され、又、アクティブなプログラムカウンタは、関数MYSUB2のターゲットアドレス0にセットされる。
【0116】
[00126]MYSUB2の第1関数であるADDがフェッチされて、アクティブなスレッドに対して処理エンジン302により実行され、レジスタR1に記憶された値を更新する。アクティブなプログラムカウンタが1に増加され、次の命令であるRETがフェッチされる。コントローラ415は、実行スタック455の最上部から発散トークンをポップし、アクティブなマスクを0x0cにセットすると共に、アクティブなプログラムカウンタを9にセットする。次いで、コントローラ415は、BRX命令をフェッチする。アクティブなスレッドは、全て、同じ関数ポインタ(インデックスi2)を指定するので、発散はなく、プッシュされるトークンもない。アクティブなプログラムカウンタは、インデックスi2に対応する関数ポインタ、即ちMYSUB1の第1命令、にセットされる。
【0117】
[00127]MYSUB1の第1命令であるADDがフェッチされて、アクティブなスレッドに対して処理エンジン302により実行され、レジスタR1に記憶された値を更新する。アクティブなプログラムカウンタが3に増加され、リターン命令RETがフェッチされる。コントローラ415は、実行スタック455の最上部から呼び出しトークンをポップし、アクティブなマスクを0xffにセットすると共に、アクティブなプログラムカウンタを10にセットする。次いで、コントローラ415は、AFTER_FUNCTIONの第1命令をフェッチする。当業者であれば、テーブル6に示すコードは、アクティブなスレッドのサブセットがBRX命令の実行により間接的な関数呼び出しを遂行するように条件分岐内に含まれることが明らかであろう。
【0118】
[00128]ここに開示するシステム及び方法の1つの効果は、マルチスレッド型アーキテクチャーのスレッドを多数のスレッドグループに分断できることである。各スレッドグループ内で、個々のスレッドを互いに発散して、必要に応じてディセーブルし、条件付き分岐、間接的な関数呼び出し、ブレーク及びリターンを実行することができる。更に、各スレッドグループ内のスレッドは、処理効率のために必要に応じて同期することができる。その結果、可能なときに完全に並列な同期モードで動作すると共に、特定のスレッドグループ内でスレッドの発散が生じるときには分岐又はサブルーチンの実行やスレッドの実行が独立して行われるので最小限の性能低下しか受けないシステムが得られる。
【0119】
[00129]本発明の一実施形態は、コンピュータシステムに使用するためのプログラム製品として実施することができる。プログラム製品のプログラム(1つ又は複数)は、(ここに述べる方法を含む)実施形態の機能を定義し、そして種々のコンピュータ読み取り可能な記憶媒体に含ませることができる。ここに例示するコンピュータ読み取り可能な記憶媒体は、(i)情報が永久的に記憶される書き込み不能の記憶媒体(例えば、コンピュータ内のリードオンリメモリ装置、例えば、CD−ROMドライブにより読み取り可能なCD−ROMディスク、フラッシュメモリ、ROMチップ、又は任意の形式のソリッドステート不揮発性半導体メモリ)、及び(ii)変更可能な情報が記憶される書き込み可能な記憶媒体(例えば、ディスケットドライブ又はハードディスクドライブ内のフロッピーディスク、又は任意の形式のソリッドステートランダムアクセス半導体メモリ)を含むが、これらに限定されない。
【0120】
[00130]本発明は、特定の実施形態を参照して以上に説明した。しかしながら、当業者であれば、特許請求の範囲に述べる本発明の広い精神及び範囲から逸脱せずに種々の変更や修正がなされ得ることが理解されよう。従って、以上の説明及び添付図面は、例示のためのものであって、それに限定されるものではない。
【符号の説明】
【0121】
100・・・システム、102・・・CPU、104・・・システムメモリ、105・・・メモリブリッジ、106・・・通信経路、107・・・I/Oブリッジ、108・・・入力装置、110・・・ディスプレイ装置、112・・・並列処理サブシステム、113・・・通信経路、114・・・システムディスク、116・・・スイッチ、118・・・ネットワークアダプタ、120・・・アドインカード、121・・・アドインカード、202・・・PPU、204・・・PPメモリ、206・・・ホストインターフェイス、208・・・コア、210・・・ワーク配布ユニット、212・・・フロントエンド、214・・・メモリインターフェイス、302・・・処理エンジン、303・・・コアインターフェイス、304・・・ローカルレジスタファイル、306・・・共有メモリ、308・・・パラメータメモリ、312・・・命令ユニット、320・・・グローバルメモリ、400・・・命令フェッチユニット、405・・・プログラムカウンタ記憶装置、410・・・定数キャッシュ、415・・・コントローラ、420・・・スレッド状態記憶装置、425・・・CRSスタック、430・・・命令キャッシュ、435・・・ディスパッチャー、440・・・制御情報、445・・・アドレスレジスタ、450・・・条件コードユニット、455・・・実行スタック、470・・・プログラムコード、472・・・定数インデックス、474・・・ロックビット、476・・・ポインタ、478・・・プログラムコード
【特許請求の範囲】
【請求項1】
同期並列処理スレッドに対して間接的な関数呼び出しを実行するシステムにおいて、
このシステムにより同時に実行される多数のスレッドのためのスレッド状態情報を記憶するように構成された実行スタックと、
前記実行スタックに結合されて、
制御命令を含むプログラム命令を受け取り、
前記スレッド状態情報をプッシュ及びポップすることにより前記制御命令を実行し、
並列に処理されるべきスレッドグループ内のアクティブなスレッドを指示するアクティブなマスクを維持し、そして
いずれかのアクティブなスレッドに対応する各独特なポインタに対して間接的な関数呼び出しの実行を直列化する、
というように構成されたコントローラと、
プログラム命令を受け取り、前記アクティブなマスクに基づいて並列に処理されるべきスレッドグループ内のスレッドに対して各プログラム命令を並列に実行するように構成された複数の処理エンジンと、
を備えるシステム。
【請求項2】
前記コントローラは、更に、分岐命令が実行され、スレッドグループ内の1つ以上のアクティブなスレッドが発散するときに、前記実行スタックにプッシュされる前記スレッド状態情報にトークンタイプ、ターゲットアドレス及びマスクを含ませるように構成され、前記マスクは、前記スレッド状態情報が前記実行タスクからポップされるときに並列に処理されるべきスレッドグループ内のスレッドを指示する、請求項1に記載のシステム。
【請求項3】
前記コントローラは、更に、前記間接的な関数呼び出しのうちの第1の間接的な関数呼び出しに対応するポインタとは異なるポインタを有する前記スレッドグループ内のいずれかのアクティブなスレッドの処理をディセーブルするように前記アクティブなマスクを変更するように構成される、請求項1に記載のシステム。
【請求項4】
間接的な分岐制御命令のオペランドは、ポインタのセットを記憶するテーブル内の1つ以上のエントリーに対応するインデックスを記憶する前記スレッドグループのスレッドごとにレジスタを指定する、請求項1に記載のシステム。
【請求項5】
間接的な分岐制御命令のオペランドは、前記ポインタのセットを記憶する前記スレッドグループの各スレッドにおいてレジスタを指定する、請求項1に記載のシステム。
【請求項1】
同期並列処理スレッドに対して間接的な関数呼び出しを実行するシステムにおいて、
このシステムにより同時に実行される多数のスレッドのためのスレッド状態情報を記憶するように構成された実行スタックと、
前記実行スタックに結合されて、
制御命令を含むプログラム命令を受け取り、
前記スレッド状態情報をプッシュ及びポップすることにより前記制御命令を実行し、
並列に処理されるべきスレッドグループ内のアクティブなスレッドを指示するアクティブなマスクを維持し、そして
いずれかのアクティブなスレッドに対応する各独特なポインタに対して間接的な関数呼び出しの実行を直列化する、
というように構成されたコントローラと、
プログラム命令を受け取り、前記アクティブなマスクに基づいて並列に処理されるべきスレッドグループ内のスレッドに対して各プログラム命令を並列に実行するように構成された複数の処理エンジンと、
を備えるシステム。
【請求項2】
前記コントローラは、更に、分岐命令が実行され、スレッドグループ内の1つ以上のアクティブなスレッドが発散するときに、前記実行スタックにプッシュされる前記スレッド状態情報にトークンタイプ、ターゲットアドレス及びマスクを含ませるように構成され、前記マスクは、前記スレッド状態情報が前記実行タスクからポップされるときに並列に処理されるべきスレッドグループ内のスレッドを指示する、請求項1に記載のシステム。
【請求項3】
前記コントローラは、更に、前記間接的な関数呼び出しのうちの第1の間接的な関数呼び出しに対応するポインタとは異なるポインタを有する前記スレッドグループ内のいずれかのアクティブなスレッドの処理をディセーブルするように前記アクティブなマスクを変更するように構成される、請求項1に記載のシステム。
【請求項4】
間接的な分岐制御命令のオペランドは、ポインタのセットを記憶するテーブル内の1つ以上のエントリーに対応するインデックスを記憶する前記スレッドグループのスレッドごとにレジスタを指定する、請求項1に記載のシステム。
【請求項5】
間接的な分岐制御命令のオペランドは、前記ポインタのセットを記憶する前記スレッドグループの各スレッドにおいてレジスタを指定する、請求項1に記載のシステム。
【図1】
【図2】
【図3】
【図4A】
【図4B】
【図4C】
【図5A】
【図5B】
【図6】
【図7】
【図8】
【図2】
【図3】
【図4A】
【図4B】
【図4C】
【図5A】
【図5B】
【図6】
【図7】
【図8】
【公開番号】特開2013−16192(P2013−16192A)
【公開日】平成25年1月24日(2013.1.24)
【国際特許分類】
【外国語出願】
【出願番号】特願2012−193483(P2012−193483)
【出願日】平成24年9月3日(2012.9.3)
【分割の表示】特願2009−56460(P2009−56460)の分割
【原出願日】平成21年3月10日(2009.3.10)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(501261300)エヌヴィディア コーポレイション (166)
【Fターム(参考)】
【公開日】平成25年1月24日(2013.1.24)
【国際特許分類】
【出願番号】特願2012−193483(P2012−193483)
【出願日】平成24年9月3日(2012.9.3)
【分割の表示】特願2009−56460(P2009−56460)の分割
【原出願日】平成21年3月10日(2009.3.10)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(501261300)エヌヴィディア コーポレイション (166)
【Fターム(参考)】
[ Back to top ]