(57)【特許請求の範囲】
【請求項１】
同期並列スレッドプロセッサで間接的な関数呼び出しを実行する方法において、
１つ以上の関数に対するポインタのセットを参照する間接的分岐命令を受け取るステップであって、前記ポインタがプログラムにおける前記関数のアドレスを指定するものであるステップと、
前記プログラムを実行する複数のスレッドを含むスレッドグループ内のアクティブなスレッドが指定する前記ポインタの２つが異なるもので、前記同期並列スレッドプロセッサでの前記間接的な関数呼び出しの実行中にアクティブなスレッドが発散することを指示するかどうか決定するステップと、
前記アクティブなスレッドが発散するときに、前記間接的分岐命令のアドレスを含む発散トークンを実行スタックにプッシュするステップと、
前記関数の発散しないスレッドのための第１の間接的な関数呼び出しのアドレスを指定するようにアクティブなプログラムカウンタを更新するステップと、
を備え、
前記スレッドグループ内のスレッドは同期することができ、
前記アクティブなスレッドが発散するときには、前記スレッドグループ内のスレッドは独立して実行される、
方法。
【請求項２】
前記間接的分岐命令を受け取るステップの前に、
前記間接的な関数呼び出しが実行された後に実行されるべき命令のターゲットアドレスを指定する呼び出し又はプレリターン命令を受け取るステップと、
実行スタックに呼び出しトークンをプッシュするステップと、
前記呼び出し又はプレリターン命令の直後のプログラムの命令を指定するようにアクティブなプログラムカウンタを更新するステップと、
を更に備える請求項１に記載の方法。
【請求項３】
前記呼び出しトークンは、トークンタイプ、ターゲットアドレス、及び、マスクを含み、前記マスクは、前記呼び出しトークンが前記実行スタックからポップされ、前記ターゲットアドレスにおいて前記プログラムの実行が継続するときに並列に処理されるべき前記スレッドグループ内の前記アクティブなスレッドを指示する、請求項２に記載の方法。
【請求項４】
前記発散トークンは、トークンタイプ及びマスクを含み、前記マスクは、アクティブであり、前記第１の間接的な関数読み出しとは異なる前記関数の関数読み出しを実行する前記スレッドグループ内のスレッドを指示する、請求項１に記載の方法。
【請求項５】
前記間接的分岐命令は、前記スレッドグループ内のアクティブなスレッドのための前記間接的な関数読み出しを実行するために、前記アクティブなスレッドに対応する前記ポインタのセットのうちの各独特のポインタに対して一度実行される、請求項１に記載の方法。
【請求項６】
前記間接的分岐命令のオペランドは、前記ポインタのセットを記憶するテーブル内の１つ以上のエントリーに対応するインデックスを記憶する前記スレッドグループ内の各スレッドにおいてレジスタを指定する、請求項１に記載の方法。
【請求項７】
前記間接的分岐命令のオペランドは、前記ポインタのセットを記憶する前記スレッドグループ内の各スレッドにおいてレジスタを指定する、請求項１に記載の方法。
【請求項８】
前記ポインタのセットのうちのポインタは、前記プログラムの実行の間に計算される、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本発明は、一般的に、グラフィック処理に係り、より詳細には、単一命令複数スレッド（ＳＩＭＴ：asingle-instruction, multiple-thread）アーキテクチャーにおいて関数ポインタを通して関数及びサブルーチンを間接的に呼び出すことができるようにするシステム及び方法に係る。
【背景技術】
【０００２】
[0002]現在のグラフィックデータ処理は、例えば、線型補間（linearinterpolation）、テッセレーション（tessellation）、ラスタ化（rasterization）、テクスチャマッピング（texturemapping）、デプステスティング（depth testing）、等、の特定のオペレーションをグラフィックデータに対して遂行するように開発されたシステム及び方法を含む。慣習的に、グラフィックプロセッサは、固定関数計算ユニットを使用してグラフィックデータを処理しているが、最近では、グラフィックプロセッサの各部分がプログラム可能とされ、このようなプロセッサで、頂点及び断片データを処理するための種々様々なオペレーションをサポートすることができる。
【０００３】
[0003]性能を更に高めるために、グラフィックプロセッサは、典型的に、パイプラインのような処理技術を実施し、グラフィックパイプラインの異なる部分全体にわたりできるだけ多くのグラフィックデータを並列に処理するように試みている。ＳＩＭＤ（single-instruction multiple-data：単一命令複数データ）アーキテクチャーをもつグラフィックプロセッサは、グラフィックパイプラインにおける並列処理量を最大にするように設計される。ＳＩＭＤアーキテクチャーでは、複数のデータ入力を処理するために、同じ命令が並列に実行される。単一命令複数スレッド（ＳＩＭＴ）のアーキテクチャーは、ＳＩＭＤアーキテクチャーより高い融通性を与える。というのは、スレッドグループ内のスレッドが、複数のデータ入力を処理するために命令のセットを通して異なる経路をたどれるからである。ＳＩＭＤ命令は、複数データ入力のベクトルに対してオペレーションを制御する単一制御スレッドの実行及び分岐振舞いを指定する。対照的に、ＳＩＭＴ命令は、そのデータ入力に対して動作する１つの個々の独立スレッドの実行及び分岐振舞いを指定し、又、ＳＩＭＴアーキテクチャーは、独立して自由に実行及び分岐する複数の独立スレッドにＳＩＭＴ命令を並列に適用する。処理効率を改善するために、進歩型制御フローには、スレッドが独立して分岐できる条件付きブレーク及びリターン命令が使用される。特に、ブレーク又はリターンを実行するスレッドは、ブレーク又はリターンを実行しないスレッドより早くに処理を完了することができる。条件付き命令の実行中に発散したスレッドは、次いで、それらスレッドが並列に実行されるように同期される。現在のＳＩＭＴアーキテクチャーは、各個々のスレッドが異なるポインタ値を有するような関数ポインタを通して関数及びサブルーチンを間接的に呼び出す能力を備えていない。Ｃのような多数のプログラミング言語は、間接的な関数呼び出しを有し、又、Ｃ＋＋のような他のものは、バーチャルな関数を有し、どちらも、プロセッサがポインタを経て間接的に関数を呼び出す能力を与える必要がある。テスト及び分岐の逐次チェーンに比して処理性能を改善するために、間接的分岐及び間接的分岐テーブルが使用される。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
[0004]従って、この技術では、関数ポインタを使用して間接的な関数呼び出しを行えるようにするＳＩＭＴアーキテクチャーが要望されている。
【課題を解決するための手段】
【０００５】
[0005]間接的な分岐命令は、同期並列スレッドプロセッサアーキテクチャーに対する間接的関数呼び出し能力を与えるためにアドレスレジスタを引数としてみなす。同期並列スレッドアーキテクチャーは、ＳＩＭＤ又はＳＩＭＴプロセッサとして機能するように構成できる。テスト及び分岐の逐次チェーンを使用するものに比して処理性能を改善する間接的分岐及び間接的分岐テーブルを実施するために間接的分岐命令が使用される。重要なことに、本発明は、スレッドが同じ分岐経路又は関数呼び出し経路をとるとき及びそれらが発散(diverging)分岐及び関数呼び出しからリターンするときにスレッドグループ内の複数のスレッドを並列に実行できるようにしながら、スレッドグループ内の個々のスレッドがスレッドグループ内の他のスレッドとは独立して分岐するための実行モデルを提供する。
【０００６】
[0006]並列処理ユニットは、条件付き制御命令の実行中に１つ以上のスレッドが発散するかどうか決定するステップを遂行するように構成される。制御命令は、同期、ブレーク及びリターンのためのスレッド処理ターゲットアドレスを設定するのに使用される。プログラムを退出するスレッドは、ディセーブルマスクによりアイドルと識別される。事象を待機する間にディセーブルされる他のスレッドは、発散スレッドが事象に到着すると、イネーブルすることができる。ディセーブルマスクの使用は、マルチスレッドＳＩＭＴアーキテクチャーにおいて条件付きリターン及びブレーク命令の使用を許す。
【０００７】
[0007]同期並列スレッドプロセッサにおいて間接的関数呼び出しを実行するための本発明の方法の種々の実施形態は、１つ以上の関数に対してポインタのセットを参照する第１の制御命令を受け取ることを含み、それらのポインタは、プログラムにおいて前記関数のアドレスを指定する。この方法は、次いで、スレッドグループ内のアクティブなスレッドに対応するポインタの２つが異なるものであって、アクティブなスレッドが同期並列スレッドプロセッサにおける前記間接的な関数呼び出しの実行中に発散することを指示するかどうか決定する。アクティブなスレッドが発散する場合には、第１の制御命令のアドレスを含む第１トークンが実行スタックにプッシュされる。第１関数のアドレスを指定するようにアクティブなプログラムカウンタが更新される。
【０００８】
[0008]本発明の種々の実施形態は、同期並列処理スレッドに対して間接的な関数呼び出しを実行するためのシステムを含む。このシステムは、実行スタック、コントローラ、及び複数の処理エンジンを備えている。実行スタックは、システムにより同時に実行される多数のスレッドに対してスレッド状態情報を記憶するように構成される。実行スタックに結合されて、制御命令を含むプログラム命令を受け取るように構成されたコントローラは、スレッド状態情報をプッシュ及びポップすることにより制御命令を実行し、並列に処理されねばならないスレッドグループ内のアクティブなスレッドを指示するアクティブなマスクを維持し、且ついずれかのアクティブなスレッドに対応する各独特のポインタに対して間接的な関数呼び出しの実行を直列化する。複数の処理エンジンは、プログラム命令を受け取り、そしてアクティブなマスクに基づき並列に処理されねばならないスレッドグループ内のスレッドに対して各プログラム命令を並列に実行するように構成される。
【０００９】
[0009]上述した本発明の特徴を詳細に理解できるように、前記で簡単に要約した本発明について、幾つかを添付図面に例示した実施形態を参照して、より詳細に説明する。しかしながら、添付図面は、本発明の典型的な実施形態を例示するに過ぎず、それ故、本発明の範囲をそれに限定するものではなく、本発明は、同等の効果を発揮できる他の実施形態も包含できるものであることに注意されたい。
【図面の簡単な説明】
【００１０】
【図１】本発明の１つ以上の態様を実施するように構成されたコンピュータシステムを示すブロック図である。
【図２】本発明の１つ以上の態様に基づく図１のコンピュータシステムのための並列処理サブシステムのブロック図である。
【図３】本発明の１つ以上の態様に基づく図２の並列処理サブシステムのための並列処理ユニットのブロック図である。
【図４Ａ】本発明の１つ以上の態様に基づく図３の並列処理ユニットのための命令ユニットのブロック図である。
【図４Ｂ】本発明の１つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図４Ｃ】本発明の１つ以上の態様に基づき関数ポインタを記憶するレジスタを参照する間接的分岐命令の概念図である。
【図５Ａ】本発明の１つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。
【図５Ｂ】本発明の１つ以上の態様に基づき一連のプログラム命令の実行中に実行スタックをアンワインドする（unwinding）ための方法ステップのフローチャートである。
【図６】本発明の１つ以上の態様に基づきプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし（populated）アンワインドする（unwound）かを示す概念図である。
【図７】本発明の１つ以上の態様に基づき条件付きリターンを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし（populated）アンワインドする（unwound）かを示す別の概念図である。
【図８】本発明の１つ以上の態様に基づき間接的な関数呼び出しを含むプログラム命令のシーケンスが実行されるときにスタックをどのようにポピュレートし（populated）アンワインドする（unwound）かを示す別の概念図である。
【発明を実施するための形態】
【００１１】
[0021]以下の説明では、本発明をより完全に理解するために多数の特定の細部について説明する。しかしながら、当業者であれば、これらの特定の細部の１つ以上がなくても、本発明を実施できることが明らかであろう。他の点について、本発明を不明瞭にしないために、良く知られた特徴は、説明しない。
［システムの概略］
【００１２】
[0022]図１は、本発明の１つ以上の態様を実施するように構成されたコンピュータシステム１００を示すブロック図である。このコンピュータシステム１００は、メモリブリッジ１０５を含むバス経路を経て通信する中央処理ユニット（ＣＰＵ）１０２及びシステムメモリ１０４を備えている。例えば、ノースブリッジ(Northbridge)チップでよいメモリブリッジ１０５は、バス又は他の通信経路１０６（例えば、ハイパートランスポートリンク）を経てＩ／Ｏ（入力／出力）ブリッジ１０７に接続される。例えば、サウスブリッジ(Southbridge)チップでよいＩ／Ｏブリッジ１０７は、１つ以上のユーザ入力装置１０８（例えば、キーボード、マウス）からユーザ入力を受け取り、そしてその入力を、経路１０２及びメモリブリッジ１０５を経てＣＰＵ１０２へ転送する。メモリブリッジ１０５には、バス又は他の通信経路１１３（例えば、ＰＣＩエクスプレス、アクセラレーテッドグラフィックポート又はハイパートランスポートリンク）を経て並列処理サブシステム１１２が結合され、一実施形態では、この並列処理サブシステム１１２は、ディスプレイ装置１１０（例えば、従来のＣＲＴ又はＬＣＤベースのモニタ）へピクセルを配送するグラフィックサブシステムである。Ｉ／Ｏブリッジ１０７には、システムディスク１１４も接続される。スイッチ１１６は、Ｉ／Ｏブリッジ１０７と、他のコンポーネント、例えば、ネットワークアダプタ１１８及び種々のアドイン(add-in)カード１２０及び１２１との間の接続をなす。又、Ｉ／Ｏブリッジ１０７には、ＵＳＢ又は他のポート接続部、ＣＤドライブ、ＤＶＤドライブ、フィルムレコーディング装置、等を含む他のコンポーネント（明確に示さず）を接続することもできる。図１における種々のコンポーネントを相互接続する通信経路は、適当なプロトコル、例えば、ＰＣＩ（周辺コンポーネント相互接続）、ＰＣＩ−エクスプレス（ＰＣＩ−Ｅ）、ＡＧＰ（アクセラレーテッドグラフィックポート）、ハイパートランスポート、或いは他のバス又はポイント・ツー・ポイント通信プロトコルを使用して実施することができ、そして異なる装置間の接続は、この技術で知られたように異なるプロトコルを使用することができる。
【００１３】
[0023]一実施形態では、並列処理サブシステム１１２は、例えば、ビデオ出力回路を含めて、グラフィック及びビデオ処理に最適な回路を組み込んでおり、そしてグラフィック処理ユニット（ＧＰＵ）を構成する。別の実施形態では、並列処理サブシステム１１２は、以下に詳細に述べる、基礎となる計算アーキテクチャーを保存しながら、汎用の処理に最適な回路を組み込んでいる。更に別の実施形態では、並列処理サブシステム１１２は、１つ以上の他のシステムエレメント、例えば、メモリブリッジ１０５、ＣＰＵ１０２、及びＩ／Ｏブリッジ１０７と一体化されて、システムオンチップ（ＳｏＣ）を形成することができる。
【００１４】
[0024]図２は、本発明の一実施形態に基づく並列処理サブシステム１１２を示す。この並列処理サブシステム１１２は、１つ以上の並列処理ユニット（ＰＰＵ）２０２を備え、その各々は、ローカル並列処理（ＰＰ）メモリ２０４に結合される。一般的に、並列処理サブシステムは、多数ＵのＰＰＵを含み、但し、Ｕ≧１である。（ここで、同じオブジェクトの複数のインスタンスは、オブジェクトを識別する参照番号と、必要に応じてインスタンスを識別するカッコ内の数字とで示される。）ＰＰＵ２０２及びＰＰメモリ２０４は、例えば、プログラム可能なプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、及びメモリ装置のような１つ以上の集積回路装置を使用して実施することができる。
【００１５】
[0025]ＰＰＵ２０２（０）について詳細に示すように、各ＰＰＵ２０２は、メモリブリッジ１０５へ接続される（又は別の実施形態では、ＣＰＵ１０２へ直結される）通信経路１１３を経てシステム１００の残り部分と通信するホストインターフェイス２０６を備えている。一実施形態では、通信経路１１３は、この技術で知られたように、各ＰＰＵ２０２に専用レーンが割り当てられるＰＣＩ−Ｅリンクである。又、他の通信経路が使用されてもよい。ホストインターフェイス２０６は、通信経路１１３へ送信するためにパケット（又は他の信号）を発生し、又、通信経路１１３から全ての到来パケット（又は他の信号）も受信して、それをＰＰＵ２０２の適当なコンポーネントへ向ける。例えば、処理タスクに関連したコマンドをフロントエンドユニット２１２に向ける一方、メモリオペレーション（例えば、ＰＰメモリ２０４からの読み取り又はそこへの書き込み）に関連したコマンドをメモリインターフェイス２１４に向けることができる。ホストインターフェイス２０６、フロントエンドユニット２１２、及びメモリインターフェイス２１４は、一般的に従来設計のものでよく、本発明にとって重要でないので、詳細な説明は省く。
【００１６】
[0026]各ＰＰＵ２０２は、高度な並列プロセッサを実施するのが好都合である。ＰＰＵ２０２（０）について詳細に示すように、ＰＰＵ２０２は、多数Ｃのコア２０８を含み、但し、Ｃ≧１である。各処理コア２０８は、非常に多数（例えば、数十又は数百）のスレッドを同時に実行することができ、各スレッドは、プログラムのインスタンスであり、マルチスレッド型処理コア２０８の一実施形態を以下に説明する。コア２０８は、フロントエンドユニット２１２から処理タスクを定義するコマンドを受け取るワーク配布ユニット２１０を経て、実行されるべき処理タスクを受け取る。このワーク配布ユニット２１０は、ワークを配布するための種々のアルゴリズムを実施することができる。例えば、一実施形態では、ワーク配布ユニット２１０は、各コア２０８から、そのコアが新たな処理タスクを受け入れるに充分なリソースを有するかどうか指示する「レディ」信号を受け取る。新たな処理タスクが到着すると、ワーク配布ユニット２１０は、レディ信号をアサートしているコア２０８にタスクを指定し、レディ信号をアサートしているコア２０８がない場合には、ワーク配布ユニット２１０は、コア２０８によりレディ信号がアサートされるまで、新たな処理タスクを保持する。当業者であれば、他のアルゴリズムも使用できると共に、ワーク配布ユニット２１０が到来する処理タスクを配布する特定のやり方は、本発明にとって重要ではないことが明らかであろう。
【００１７】
[0027]コア２０８は、種々の外部メモリ装置を読み取ったりそこに書き込んだりするためにメモリインターフェイス２１４と通信する。一実施形態では、メモリインターフェイス２１４は、ローカルＰＰメモリ２０４と通信するためのインターフェイスと、ホストインターフェイスへの接続とを含み、これにより、コアは、システムメモリ１０４、或いはＰＰＵ２０２に対してローカルではない他のメモリと通信することができる。メモリインターフェイス２１４は、一般的に従来設計のものでよく、詳細な説明は、省く。
【００１８】
[0028]コア２０８は、これに限定されないが、直線的及び非直線的なデータ変換、ビデオ及び／又はオーディオデータのフィルタリング、モデリングオペレーション（例えば、物理の法則を適用して、オブジェクトの位置、速度及び他の属性を決定する）、映像レンダリングオペレーション（例えば、頂点シェーダー、幾何学的シェーダー及び／又はピクセルシェーダープログラム）、等を含む種々様々なアプリケーションに関する処理タスクを実行するようにプログラムすることができる。ＰＰＵ２０２は、システムメモリ１０４及び／又はローカルＰＰメモリ２０４からのデータを内部（オンチップ）メモリへ転送し、そのデータを処理し、そしてその結果データをシステムメモリ１０４及び／又はローカルＰＰメモリ２０４へ書き戻すことができ、このようなデータは、例えば、ＣＰＵ１０２又は別の並列処理サブシステム１１２を含む他のシステムコンポーネントによりアクセスすることができる。
【００１９】
[0029]再び、図１を参照すれば、ある実施形態において、並列処理サブシステム１１２内のＰＰＵ２０２は、その幾つか又は全部が、レンダリングパイプラインを伴うグラフィックプロセッサであって、ＣＰＵ１０２及び／又はシステムメモリ１０４によりメモリブリッジ１０５及びバス１１３を経て供給されたグラフィックデータからピクセルデータを発生し、ローカルＰＰメモリ２０４（例えば、従来のフレームバッファを含むグラフィックメモリとして使用できる）と相互作用してピクセルデータを記憶及び更新し、そのピクセルデータをディスプレイ装置１１０へ配送し、等々に関連した種々のタスクを遂行するように構成することができる。ある実施形態では、ＰＰサブシステム１１２は、グラフィックプロセッサとして動作する１つ以上のＰＰＵ２０２、及び汎用の計算に使用される１つ以上の他のＰＰＵ２０２を含むことができる。ＰＰＵは、同じものでも異なるものでもよく、そして各ＰＰＵは、それ自身の専用のＰＰメモリ装置（１つ又は複数）を有してもよいし、専用のＰＰメモリ装置を有していなくてもよい。
【００２０】
[0030]動作に際して、ＣＰＵ１０２は、システム１００のマスタープロセッサであり、他のシステムコンポーネントのオペレーションを制御し整合させる。特に、ＣＰＵ１０２は、ＰＰＵ２０２のオペレーションを制御するコマンドを発行する。ある実施形態では、ＣＰＵ１０２は、各ＰＰＵ２０２のためのコマンドのストリームをプッシュバッファ（図１には明確に示さず）に書き込み、このプッシュバッファは、ＣＰＵ１０２及びＰＰＵ２０２の両方に対してアクセス可能なシステムメモリ１０４、ＰＰメモリ２０４、又は別の記憶位置に配置することができる。ＰＰＵ２０２は、プッシュバッファからコマンドストリームを読み取り、そしてＣＰＵ１０２のオペレーションとは非同期でそれらコマンドを実行する。
【００２１】
[0031]ここに示すシステムは、例示に過ぎず、変更や修正がなされ得ることが明らかであろう。ブリッジの数及び配列を含む接続技術は、必要に応じて変更することができる。例えば、ある実施形態では、システムメモリ１０４は、ブリッジを経ずに、ＣＰＵ１０２へ直結され、他の装置は、メモリブリッジ１０５及びＣＰＵ１０２を経てシステムメモリ１０４と通信する。他の別のトポロジーでは、並列処理サブシステム１１２は、Ｉ／Ｏブリッジ１０７へ接続され、又はメモリブリッジ１０５ではなく、ＣＰＵ１０２へ直結される。更に別の実施形態では、Ｉ／Ｏブリッジ１０７及びメモリブリッジ１０５が１つのチップへ一体化されてもよい。ここに示す特定のコンポーネントは、任意のものであり、例えば、いかなる数のアドインカード又は周辺装置がサポートされてもよい。ある実施形態では、スイッチ１１６が除去され、ネットワークアダプタ１１８及びアドインカード１２０、１２１がＩ／Ｏブリッジ１０７に直結される。
【００２２】
[0032]ＰＰＵ２０２とシステム１００の残り部分との接続を変更することもできる。ある実施形態では、ＰＰシステム１１２は、システム１００の拡張スロットに挿入できるアドインカードとして実施される。他の実施形態では、ＰＰＵ２０２は、単一チップ上で、メモリブリッジ１０５又はＩ／Ｏブリッジ１０７のようなバスブリッジと一体化することができる。更に別の実施形態では、ＰＰＵ２０２の幾つかの又は全部のエレメントを単一チップ上でＣＰＵ１０２と一体化することができる。
【００２３】
[0033]ＰＰＵには、ローカルメモリを含まずに、任意の量のローカルＰＰメモリを設けることができ、そしてローカルメモリ及びシステムメモリを任意の組合せで使用することができる。例えば、ＰＰＵ２０２は、一体化メモリアーキテクチャー（ＵＭＡ）実施形態ではグラフィックプロセッサであり、このような実施形態では、専用のグラフィック（ＰＰ）メモリがほとんど又は全く設けられず、又、ＰＰＵ２０２は、システムメモリを排他的又はほぼ排他的に使用する。ＵＭＡ実施形態では、ＰＰＵは、ブリッジチップ又はプロセッサチップに一体化されてもよく、或いは例えば、ブリッジチップを経てＰＰＵをシステムメモリに接続する高速リンク（例えば、ＰＣＩ−Ｅ）を伴う個別のチップとして設けられてもよい。
【００２４】
[0034]上述したように、並列処理サブシステムには、任意の数のＰＰＵを含ませることもできる。例えば、複数のＰＰＵを単一のアドインカードに設けることもできるし、又は複数のアドインカードを通信経路１１３に接続することもできるし、或いは１つ以上のＰＰＵをブリッジチップに一体化することもできる。複数ＰＰＵシステムのＰＰＵは、互いに同じものでもよいし異なるものでもよく、例えば、異なるＰＰＵは、異なる数のコア、異なる量のローカルＰＰメモリ、等を有してもよい。複数のＰＰＵが存在する場合には、それらを並列に動作させて、単一のＰＰＵで可能なものより高いスループットでデータを処理することができる。
【００２５】
[0035]１つ以上のＰＰＵを合体するシステムは、デスクトップ、ラップトップ又はハンドヘルドパーソナルコンピュータ、サーバー、ワークステーション、ゲームコンソール、埋め込まれたシステム、等々を含む種々の構成及びフォームファクタで実施することができる。
［コアの概略］
【００２６】
[0036]図３は、本発明の１つ以上の態様に基づく図２の並列処理サブシステム１１２のための並列処理ユニット２２０を示すブロック図である。このＰＰＵ２０２は、非常に多数のスレッドを並列に実行するように構成されたコア２０８（又は複数コア２０８）を備え、ここで、「スレッド(thread)」という語は、入力データの特定セットに対して実行される特定プログラムのインスタンスを指す。ある実施形態では、単一命令複数データ（ＳＩＭＤ）の命令発行技術を使用して、複数の独立した命令ユニットを設けずに、非常に多数のスレッドの並列実行がサポートされる。ある実施形態では、単一命令複数スレッド（ＳＩＭＴ）技術を使用し、処理エンジンのセットへ命令を発行するように構成された共通の命令ユニットを使用して、非常に多数の一般的に同期されたスレッドの並列実行がサポートされる。全ての処理エンジンが典型的に同じ命令を実行するＳＩＭＤ実行形態とは異なり、ＳＩＭＴの実行は、異なるスレッドが、所与のスレッドプログラムを通して、発散する実行経路を容易にたどれるようにする。当業者であれば、ＳＩＭＤ処理形態は、ＳＩＭＴ処理形態の機能的サブセットを表すことが理解されよう。
【００２７】
[0037]ＳＩＭＤマシンと同様に、ＳＩＭＴ並列処理コア２０８は、このコア２０８に含まれた複数の並列処理エンジン３０２にわたって異なるデータに対して単一の並列プログラムのインスタンスを実行する。従って、例えば、コア２０８は、該コア２０８内の並列処理エンジン３０２において一連の共通の命令を実行するように構成できる。単一の並列処理エンジン３０２への一連の命令は、前記で定義されたスレッドを構成し、そしてコア２０８内の並列処理エンジン３０２間のある数の現在実行中のスレッドの集合を、ここでは「ワープ(warp)」又は「スレッドグループ」と称する。更に、複数の関連スレッドグループは、コア２０８において同時にアクティブとなり得る（実行の異なる段階で）。スレッドグループのこの集合を、ここでは「協働スレッドアレー」（ＣＴＡ）と称する。
【００２８】
[0038]特定のＣＴＡのサイズは、ｍ＊ｋに等しい。但し、ｋは、スレッドグループ内の同時に実行されるスレッドの数で、典型的に、コア２０８における並列処理エンジン３０２の数の整数倍であり、そしてｍは、コア２０８において同時にアクティブなスレッドグループの数である。ＣＴＡのサイズは、一般的に、プログラマーと、ＣＴＡに利用可能なメモリ又はレジスタのようなハードウェアリソースの数とによって決定される。
【００２９】
[0039]一実施形態では、各コア２０８は、単一命令ユニット３１２からＳＩＭＴ命令を受け取るように構成されたＰ個（例えば、８個、１６個、等）の並列処理エンジン３０２のアレイを含む。各処理エンジン３０２は、機能的ユニット（例えば、演算論理ユニット、等）の同じセットを含むのが好都合である。機能的ユニットは、この技術で知られたように、手前の命令が終了する前に新たな命令を発行できるようなパイプライン型のものでよい。機能的ユニットの任意の組合せを設けることもできる。ある実施形態では、機能的ユニットは、整数及び浮動小数点演算（例えば、加算及び乗算）、比較演算、ブール演算（ＡＮＤ、ＯＲ、ＸＯＲ）、ビットシフト、及び種々の代数関数（例えば、平面補間、三角法、指数関数、及び対数関数、等）の組合せ、を含む種々のオペレーションをサポートし、そして同じ機能的ユニットハードウェアをレバレッジして（leveraged）、異なるオペレーションを遂行することができる。
【００３０】
[0040]各処理エンジン３０２は、ローカル入力データ、中間結果、等を記憶するためにローカルレジスタファイル（ＬＲＦ）３０４のスペースを使用する。一実施形態では、ローカルレジスタファイル３０４は、ある数のエントリーを各々有するＰ個のレーンに物理的又は論理的に分割される（各エントリーは、例えば、３２ビットワードを記憶する）。各処理エンジン３０２に１つのレーンが指定されると共に、異なるレーンの対応エントリーに、同じプログラムを実行する異なるスレッドに対するデータをポピュレートさせて（populated）、同期した並列実行を容易にすることができる。ＳＩＭＴ命令は、スレッドグループの各スレッドに対応する各レーンのレジスタエントリーにアクセスするレジスタオペランド（registeroperand）を指定することができる。ある実施形態では、各処理エンジン３０２は、それに指定されたレーンのＬＲＦエントリーにしかアクセスできない。ローカルレジスタファイル３０４におけるエントリーの全数は、処理エンジン３０２当たり複数の同時スレッドをサポートするに充分なほど大きいのが好都合である。
【００３１】
[0041]又、各処理エンジン３０２は、コア２０８内の全処理エンジン３０２間で共有されて異なるスレッド間でデータを転送するのに使用できるオンチップ共有メモリ３０６にアクセスすることができる。この共有メモリ３０６は、希望の大きさのものでよく、ある実施形態では、いずれの処理エンジン３０２も、等しく低い待ち時間（例えば、ローカルレジスタファイル３０４へのアクセスに匹敵する）で、共有メモリ３０６内の任意の位置から読み取り又はそこに書き込むことができる。ある実施形態では、共有メモリ３０６は、共有レジスタファイルとして実施され、他の実施形態では、共有メモリ３０６は、共有キャッシュメモリを使用して実施することができる。
【００３２】
[0042]共有メモリ３０６に加えて、ある実施形態では、付加的なオンチップパラメータメモリ及び／又はキャッシュ（１つ又は複数）３０８も設けられ、これは、例えば、従来のＲＡＭ又はキャッシュとして実施されてもよい。パラメータメモリ／キャッシュ３０８は、例えば、複数のスレッドにより必要になることのある状態パラメータ及び／又は他のデータ（例えば、種々の定数）を保持するのに使用できる。又、処理エンジン３０２は、メモリインターフェイス２１４を経てオフチップ「グローバル」メモリ３２０にアクセスすることができ、これは、例えば、ＰＰメモリ２０４及び／又はシステムメモリ１０４を含むことができ、システムメモリ１０４は、上述したように、メモリインターフェイス２１４によりホストインターフェイス２０６を経てアクセスすることができる。ＰＰＵ２０２の外部の任意のメモリをグローバルメモリ３２０として使用してもよいことを理解されたい。処理エンジン３０２は、この処理エンジン３０２がグローバルメモリ３２０にアクセスするのを許す相互接続部（明確に図示せず）を経てメモリインターフェイス２１４へ結合することができる。
【００３３】
[0043]一実施形態では、各処理エンジン３０２は、マルチスレッド型であり、例えば、ローカルレジスタファイル３０４の指定レーンの異なる部分における各スレッドに関連した現在状態情報を維持することにより、ある数Ｇ（例えば、２４）までのスレッドを同時に実行することができる。処理エンジン３０２は、異なるスレッドからの命令を効率のロスなく任意のシーケンスで発行できるように、あるスレッドから別のスレッドへ急速にスイッチするように設計されるのが好都合である。
【００３４】
[0044]命令ユニット３１２は、所与の処理サイクルに対して、同じ命令（ＩＮＳＴＲ）をＰ個の全処理エンジン３０２へ発行できるように構成される。従って、単一クロックサイクルのレベルにおいて、コア２０８は、Ｐ路(P-way)のＳＩＭＴ又はＳＩＭＤ設計を実質的に表わすマイクロアーキテクチャーを実施する。又、各処理エンジン３０２がマルチスレッド型で、Ｇ個までのスレッドを同時にサポートするので、この実施形態のコア２０８は、同時に実行するＰ＊Ｇ個までのスレッドを有することができる。例えば、Ｐ＝１６及びＧ＝２４の場合には、コア２０８が３８４個までの同時スレッドをサポートする。
【００３５】
[0045]命令ユニット３１２は、同じ命令をＰ個の全処理エンジン３０２へ並列に発行するので、コア２０８は、スレッドグループにおいてスレッドを処理するのに使用されるのが好都合である。ここで使用する「スレッドグループ」とは、グループの１つのスレッドが各処理エンジン３０２に指定されるようにして、異なる入力データに対して同じプログラムを実行するＰ個までのスレッドのグループを指す。スレッドグループは、Ｐ個より少ないスレッドを含んでもよく、この場合は、そのスレッドグループが処理されるときのサイクル中には処理エンジン３０２の幾つかがアイドル状態になる。又、スレッドグループは、Ｐ個より多くのスレッドを含んでもよく、この場合は、連続するクロックサイクルにわたり処理が行われる。各処理エンジン３０２は、Ｇ個までのスレッドを同時にサポートできるので、コア２０８において所与の時間にＧ個までのスレッドのグループを実行できることになる。
【００３６】
[0046]各クロックサイクルに、Ｇスレッドグループの選択された１つを形成しているＰ個の全スレッドに１つの命令が発行される。どのスレッドが現在アクティブであるか指示するために、関連スレッドに対する「アクティブマスク」を命令と共に含ませることができる。処理エンジン３０２は、アクティブマスク及びスレッドグループ識別子を使用して、命令を実行するときに、ローカルレジスタファイル３０４の指定レーンのどの部分を使用すべきか決定する。従って、所与のサイクルに、コア２０８の全ての処理エンジン３０２が、同じスレッドグループ内の異なるスレッドに対して同じ命令を同期状態で実行することができる。当業者であれば、スレッドグループ内の各スレッドのこのような同期並列実行がＳＩＭＤアーキテクチャーの特徴であることが明らかであろう。スレッドグループ内のスレッドが同期状態で実行するときには、処理エンジン３０２は、ＳＩＭＤ形態で命令を実行するように構成される。しかしながら、あるインスタンスでは、スレッドグループ内の幾つかのスレッドが、例えば、以下に述べるように、条件付き又は述語型命令、プログラムの分岐点での発散、等のために、一時的にアイドル状態になることがある。処理エンジン３０２は、ＳＩＭＤ又はＳＩＭＴエンジンとして機能するように構成されてもよい。
【００３７】
[0047]コア２０８のオペレーションは、コアインターフェイス３０３を経て制御されるのが好都合である。ある実施形態では、コアインターフェイス３０３は、処理されるべきデータ（例えば、原始データ、頂点データ、及び／又はピクセルデータ）、状態パラメータ、及びデータをどのように処理すべきか定義するコマンド（例えば、どんなプログラムを実行すべきか）をワーク配布ユニット２１０から受け取る。コアインターフェイス３０３は、処理されるべきデータを共有メモリ３０６に、そしてパラメータをパラメータメモリ３０８にロードすることができる。又、コアインターフェイス３０３は、命令ユニット３１２において各々の新たなスレッド又はスレッドグループを初期化し、次いで、スレッドの実行を開始するように命令ユニット３１２に信号する。スレッド又はスレッドグループの実行が完了すると、コア２０８は、コアインターフェイス３０３に通知するのが好都合である。次いで、コアインターフェイス３０３は、他のプロセスを開始し、例えば、共有メモリ３０６から出力データを検索し、及び／又は付加的なスレッド又はスレッドグループの実行のためにコア２０８を準備することができる。
【００３８】
[0048]ここに述べるコアアーキテクチャーは、例示に過ぎず、変更や修正が考えられることが明らかである。いかなる数の処理エンジンが含まれてもよい。ある実施形態では、各処理エンジンは、それ自身のローカルレジスタファイルを有し、スレッド当たりのローカルレジスタファイルエントリーの割り当ては、固定でもよいし、又は希望の通りに構成できてもよい。更に、１つのコア２０８しか示されていないが、ＰＰＵ２０２は、いかなる数のコア２０８を含んでもよく、それらコアは、互いに同じ設計のものであって、実行の振舞いが、どのコア２０８が特定の処理タスクを受け取るかに依存しないようにするのが好都合である。各コア２０８は、他のコア２０８とは独立して動作すると共に、それ自身の処理エンジン、共有メモリ、等を有するのが好都合である。
【００３９】
[0049]当業者であれば、図１、２及び３に示すアーキテクチャーは、本発明の範囲を何ら限定するものではなく、且つここに教示する技術は、本発明の範囲から逸脱せずに、これに限定されないが、１つ以上のＣＰＵ、１つ以上のマルチコアＣＰＵ、１つ以上のＧＰＵ、１つ以上のマルチコアＧＰＵ、等を含む任意の適切に構成された処理ユニットにおいて実施できることが理解されよう。
［スレッドアレー及び協働スレッドアレー］
【００４０】
[0050]ある実施形態では、図３のマルチスレッド処理コア２０８は、スレッドブロック又はスレッドアレーを使用して汎用計算を実行することができる。スレッドアレーは、入力データセットに対して同じプログラムを同時に実行して出力データセットを発生する多数（ｎ０）のスレッドより成る。スレッドアレーの各スレッドには、実行中にスレッドにアクセスできる独特のスレッド識別子（スレッドＩＤ）が指定される。このスレッドＩＤは、スレッドの処理振舞いについての種々の態様を制御する。例えば、スレッドＩＤを使用して、入力データセットのどの部分をスレッドが処理すべきか決定し、及び／又は出力データセットのどの部分をスレッドが発生し又は書き込むべきか決定することができる。
【００４１】
[0051]ある実施形態では、スレッドアレーは、「協働」スレッドアレー即ちＣＴＡとして配列される。各ＣＴＡは、入力データセットに対して同じプログラム（ここでは「ＣＴＡプログラム」と称される）を同時に実行して、出力データセットを発生するスレッドのグループである。ＣＴＡでは、スレッドは、スレッドＩＤに基づくやり方でデータを互いに共有することにより協働することができる。例えば、ＣＴＡでは、データをあるスレッドによって発生し、別のスレッドによって消費することができる。ある実施形態では、データを共有すべきポイントにおいてＣＴＡプログラムコードに同期命令を挿入して、消費側スレッドがデータへのアクセスを試みる前に発生側スレッドによりデータが実際に発生されるよう確保することができる。ＣＴＡのスレッド間でのデータ共有がもしあれば、その程度は、ＣＴＡプログラムによって決定され、従って、ＣＴＡを使用する特定のアプリケーションにおいて、ＣＴＡのスレッドは、ＣＴＡプログラムに基づいて実際にデータを互いに共有してもよいし、しなくてもよいことを理解されたい。
【００４２】
[0052]ある実施形態では、ＣＴＡのスレッドは、図３の共有メモリ３０６を使用して、入力データ及び／又は中間結果を同じＣＴＡの他のスレッドと共有する。例えば、ＣＴＡプログラムは、特定のデータを書き込むべき共有メモリ３０６内のアドレスを計算するための命令を含み、このアドレスは、スレッドＩＤの関数である。各スレッドは、それ自身のスレッドＩＤを使用して関数を計算し、そして対応する位置に書き込みを行う。アドレス関数は、異なるスレッドが異なる位置に書き込みを行い、関数が決定論的である限り、スレッドによって書き込まれる位置を予想できるように、定義されるのが好都合である。又、ＣＴＡプログラムは、データを読み取るべき共有メモリ３０６内のアドレスを計算するための命令を含むこともでき、そのアドレスは、スレッドＩＤの関数である。適当な関数を定義して、同期技術を与えることにより、予想可能なやり方で、ＣＴＡの１つのスレッドによって共有メモリ３０６内の所与の位置にデータを書き込み、そして同じＣＴＡの異なるスレッドによりその位置からデータを読み取ることができる。その結果、スレッド間での希望のデータ共有パターンをサポートすることができ、ＣＴＡのいずれのスレッドも、同じＣＴＡの他のスレッドとでデータを共有することができる。
【００４３】
[0053]ＣＴＡ（又は他の形式のスレッドアレー）は、データ並列分解に適した計算を遂行するのに使用されるのが好都合である。ここで使用する「データ並列分解」という語は、入力データに対して同じアルゴリズムを複数回並列に実行して出力データを発生することにより計算上の問題を解決する状態を含み、例えば、データ並列分解の１つの共通のインスタンスは、入力データセットの異なる部分に同じ処理アルゴリズムを適用して、出力データセットの異なる部分を発生することを含む。データ並列分解の影響を受け易い問題は、例えば、マトリクス代数、任意の次元数における線型及び／又は非線型変換（例えば、高速フーリエ変換）、及び種々のフィルタリングアルゴリズムを含み、このフィルタリングアルゴリズムは、任意の次元数のコンボリューションフィルタ、複数次元の分離可能なフィルタ、等を含む。入力データセットの各部分に適用されるべき処理アルゴリズムは、ＣＴＡプログラムにおいて指定され、そしてＣＴＡ内の各スレッドは、入力データセットの一部分に対して同じＣＴＡプログラムを実行するか、又は出力データセットの一部分を発生する。ＣＴＡプログラムは、広範囲の数学的及び論理的オペレーションを使用してアルゴリズムを実施することができ、又、プログラムは、条件付き又は分岐実行経路と、直接的及び／又は間接的メモリアクセスとを含むことができる。
【００４４】
[0054]一実施形態では、図１のＣＰＵ１０２で実行されるドライバプログラムは、ＣＴＡを定義するコマンドをメモリ（例えば、システムメモリ１０４）内のプッシュバッファ（明確に図示せず）へ書き込み、これは、ＰＰＵ２０２によりコマンドが読み取られるところである。これらコマンドは、ＣＴＡ内のスレッドの数、ＣＴＡを使用して処理されるべき入力データセットのグローバルメモリ３２０内の位置、実行されるべきＣＴＡプログラムのグローバルメモリ３２０内の位置、及び出力データを書き込むべきグローバルメモリ３２０内の位置のような状態パラメータに関連付けられるのが好都合である。この状態パラメータは、コマンドと一緒にプッシュバッファに書き込まれてもよい。コマンドに応答して、コアインターフェイス３０３は、状態パラメータをコア２０８（例えば、パラメータメモリ３０８）へロードし、次いで、ＣＴＡパラメータで指定されたスレッドの数が起動されるまでスレッドの起動を開始する。一実施形態では、コアインターフェイス３０３は、起動されたスレッドにスレッドＩＤを順次に指定する。より一般的には、ＣＴＡの全スレッドが同じコア２０８において同じプログラムを実行するので、１つのスレッドのみに各有効スレッドＩＤが指定される限り、いずれのスレッドにいずれのスレッドＩＤが指定されてもよい。独特の識別子（数字識別子を含むが、これに限定されない）をスレッドＩＤとして使用することができる。一実施形態では、ＣＴＡが、ある数（ｎ０）のスレッドを含む場合には、スレッドＩＤは、０からｎ０−１までの単なる逐次（一次元）インデックス値である。他の実施形態では、多次元インデックス機構を使用することができる。スレッドＩＤを参照することによってデータの共有が制御される限り、処理エンジンにスレッドを特定に指定しても、ＣＴＡの実行結果に影響が及ぶことはない。従って、ＣＴＡプログラムは、それを実行すべき特定のハードウェアとは独立したものでよい。
［マルチスレッド命令処理］
【００４５】
[0055]図４Ａは、本発明の１つ以上の態様に基づく、図３の並列処理ユニット２０２のための命令ユニット３１２を示すブロック図である。この命令ユニット３１２は、命令フェッチユニット４００と、命令キャッシュ４３０と、定数キャッシュ４１０と、ディスパッチャー４３５と、条件コードユニット４５０とを備えている。命令フェッチユニット４００は、処理されるべきデータと、データを処理するのに使用すべきプログラムに対応するプログラム識別子とを受け取る。アドレスレジスタ４４５は、プログラム命令によってロードされ及び読み取られるアドレス値を記憶する。スレッドグループ内のスレッドごとにアドレスレジスタ４４５にレジスタセットがある。本発明のある実施形態では、アドレスレジスタ４４５は、１６ビット値を記憶し、又、他の実施形態では、アドレスレジスタ４４５は、３２ビット値を記憶する。或いは又、アドレス値は、グローバルメモリ３２０、共有メモリ３０６、又はローカルレジスタファイル３０４に記憶される。
【００４６】
[0056]プログラムカウンタ記憶装置４０５は、各スレッドグループに対して実行されるべき次のプログラム命令（ＩＮＳＴＲ）を指示するアクティブなプログラムカウンタを記憶する。Ｇ＝２４のときには、プログラムカウンタ記憶装置４０５は、２４個のアクティブなプログラムカウンタを記憶する。同様に、スレッド状態記憶装置４２０は、各スレッドグループに対するアクティブなマスクを記憶し、アクティブなマスクの各ビットは、Ｐ個の処理エンジン３０２の整数に対応する。それ故、アクティブなマスクにおけるビット数は、スレッドグループにおけるスレッドの数である。又、スレッド状態記憶装置４２０は、各スレッドグループに対するディセーブルマスクも記憶する。ディセーブルマスクは、スレッドグループ内の各スレッドに対してフラグを含む。このフラグは、スレッドがイネーブルされたか、条件付きリターン命令の処理のためにディセーブルされたか、条件付きブレーク命令の処理のためにディセーブルされたか、又はスレッドがプログラムを退出したか、指示する。これら命令の処理、及びディセーブルマスクの決定は、図５Ａ、５Ｂ及び７を参照して説明する。
【００４７】
[0057]ＣＲＳ（呼び出し、リターン、同期）スタック４２５は、図４に実行スタック（０）ないし（Ｇ−１）として示された各スレッドグループのための実行スタックを含む。実行スタックは、例えば、トークンタイプ、トークンプログラムカウンタ及びトークンマスクのような状態情報を含むトークンをプッシュ及びポップするために制御命令の処理中に使用される。本発明のある実施形態では、ＣＲＳスタック４２５は、実行スタック４５５に対してグローバルメモリ３２０へのエントリーをこぼし、実行スタック４５５は、オーバーフローし、そしてＣＲＳスタック４２５にスペースが得られたときにこぼれたエントリーを回復させることができる。コントローラ４１５は、制御命令が実行されるときにＣＲＳスタック４２５からエントリーをプッシュ及びポップする。一実施形態では、６つのタイプの制御命令がある。即ち、条件付き分岐命令と、呼び出し命令と、プレブレーク(PreBreak)命令と、プレリターン(PreReturn)命令と、条件付きリターン命令と、同期命令と、条件付きブレーク命令である。別の実施形態は、それより多数又は少数のタイプの制御命令、並びに異なるタイプの制御命令を含んでもよい。
【００４８】
[0058]コントローラ４１５は、スレッドグループに対するアクティブなプログラムカウンタ及びアクティブなマスクを命令キャッシュ４３０に与える。この命令キャッシュ４３０は、アクティブなプログラムカウンタに対応する命令を得、そしてその命令及びアクティブなマスクをディスパッチャー４３５へ出力する。命令キャッシュ４３０は、当業者に知られたキャッシュ技術を使用して、グローバルメモリ３２０から命令を必要に応じて読み取る。コントローラ４１５は、制御命令が実行されるときに条件コードユニット４５０から制御情報４４０を経て制御情報を受け取る。この制御情報は、制御命令のタイプを示すトークンタイプと、スタックアンワインド(unwind)信号と、トークンをＣＲＳスタック４２５にプッシュしそしてスレッドグループに対するアクティブマスク及びディセーブルマスクを更新するのに必要な他のデータとを含む。
【００４９】
[0059]定数キャッシュ４１０は、命令のオペランドとして指定されたインデックス使用して読み取られる値を記憶する。本発明のある実施形態では、スレッドグループに対する定数にアクセスするためにインデックスが使用される。間接的な分岐がサポートされるときには、図４Ｂを参照して述べるように、関数ポインタが定数キャッシュ４１０に記憶される。スレッドグループの各スレッドは、異なるインデックスを使用することにより定数キャッシュ４１０内の異なる定数にアクセスできることに注意されたい。それ故、単一のスレッドグループ内の異なるスレッドは、異なる関数ポインタを使用して分岐し、ＳＩＭＴ処理中に発散を生じ得る。
【００５０】
[0060]ディスパッチャー４３５は、命令をデコードし、そして条件付き制御命令（条件付き分岐、条件付きブレーク、及び条件付きリターン）に対する条件付きデータを条件コードユニット４５０へ出力する。条件付きデータは、条件テスト及び比較値（制御命令により指定される）を含み、これに対して条件コードが適用される。従来、条件コードは、命令により指定された条件テストを比較値に対して評価し、真又は偽の結果を発生するのに使用される。整数値に対する８つの条件テストのうちの６つは、従来の条件テスト、例えば、より小さい(lessthan)（ＬＴ）、等しい(equal)（ＥＱ）、より大きい(greater than)（ＧＴ）、以下(less than or equal)（ＬＥ）、以上(greaterthan or equal)（ＧＥ）、及び不等(not equal)（ＮＥ）である。条件テストは、比較値が正であるか、ゼロであるか又は負であるか決定するのに使用される。
【００５１】
[0061]浮動小数点フォーマット値が使用されるときには、条件テストは、ＮａＮ（非数(not-a-number)）値のような非順序値に対する振舞いを定義する条件テストも含むことができる。ＮａＮは、数値に対して順序をもたず、それ故、従来の条件テストのための入力として、又は比較値を発生するのに使用されたときには、予期せぬ結果を生じさせる。８つの新たな条件テスト、例えば、ＬＥＧ、Ｕ、ＬＴＵ、ＥＱＵ、ＬＥＵ、ＧＴＵ、ＮＥＵ及びＧＥＵは、ＮａＮ値の明確なハンドリングを与える。ＬＥＧ（より小さい、等しい、又はより大きい）は、比較値がゼロ、正又は負であり、即ち順序付けされるときしか真とならない。Ｕ（非順序）は、比較値が非順序付けされ、即ちＮａＮであるときしか真とならない。ＬＴＵ（ゼロ未満又は非順序）は、比較値が負又はＮａＮであるときに真となる。ＥＱＵ（ゼロに等しい又は非順序）は、比較値がゼロ又はＮａＮであるときしか真とならない。ＬＥＵ（ゼロ以下又は非順序）は、比較値が負、ゼロ又はＮａＮのときしか真とならない。ＧＴＵ（ゼロより大きい又は非順序）は、比較値が正又はＮａＮであるときしか真とならない。ＮＥＵ(ゼロに等しくなく又は非順序）は、比較値が正、負又はＮａＮであるときしか真とならない。ＧＥＵ(ゼロ以上又は非順序)は、比較値が正、ゼロ又はＮａＮであるときしか真とならない。
【００５２】
[0062]他の２つの従来の条件テスト(整数及び浮動小数点値に対する)は、常に(ＴＲ)であって、決して（ＦＬ）ではない。オーバーフロー及び桁上げのような付加的な条件テストも使用でき、従って、条件テストの数が増加される。比較値は、プログラムの実行中に計算することができ、スレッドグループ内の各スレッドは、比較値を有してもよい。それ故、条件テストが評価されるときには、あるスレッドは、真の結果を発生し、一方、他のスレッドは、偽の結果を発生することがある。１つ以上のアクティブなスレッドが、他のアクティブなスレッドとは異なる条件テスト結果を生じるときには、スレッドが発散し、ＣＲＳスタック４３５を使用して、分岐の第１の側が実行を完了した後に実行される分岐の側に対してアクティブなマスク及びプログラムカウンタを含むトークンを記憶する。
【００５３】
[0063]又、条件付きデータに加えて、ディスパッチャーは、制御命令(呼び出し、ブレーク、リターン、分岐、等)、命令により指定されるターゲットプログラムカウンタ(アドレス)、及びアクティブなマスクを条件コードユニット４５０へ出力する。制御命令は、ディスパッチャー４３５によって処理エンジン２０３へ出力されない。むしろ、条件コードユニット４５０は、この条件コードユニット４５０によりコントローラへ出力された制御情報に含まれたアクティブなマスクに基づいて「テークン(taken)」マスクを決定する。より詳細には、条件コードユニット４５０は、条件テスト結果を使用して、命令により指定されたテスト条件に対して「真」と評価するアクティブなスレッドを指示する「テークンマスク」を決定する。真の比較テスト結果を指示するスレッドグループ内のスレッドに対するこのテークンマスクのビットがクリアされる。アクティブなマスク及びテークンマスクは、ディセーブルマスクを更新するように、コントローラ４１５によって使用することができる。異なる関数ポインタを有する２つ以上のスレッドで関数呼び出しが遂行されるときには、関数呼び出しが直列化されて、各独特の関数ポインタを指定するスレッドを実行すると共に、テークンマスクを使用して、各独特の関数ポインタに対するアクティブなスレッドを指示する。
【００５４】
[0064]条件コードユニット４５０は、テークンマスク及びトークンタイプを、制御情報４４０を経てコントローラ４１５へ出力する。ターゲットプログラムカウンタが呼び出し又は分岐制御命令により指定されるときには、テークンプログラムカウンタが条件コードユニット４５０により制御情報４４０を経てコントローラ４１５へ出力される。トークンタイプは、ディセーブルマスクを発生するために実行された制御命令のタイプを指示する。トークンタイプは、同期、呼び出し、発散、及びブレークを含む。スレッドに対する制御命令が、フライト中(in-flight)であり、即ちコントローラ４１５により出力されたが制御情報４４０を経てコントローラ４１５によりまだ受け取られていないときには、同じスレッドに対する別の命令がコントローラ４１５により出力されてはならないことに注意されたい。
【００５５】
[0065]ディスパッチャー４３５によって受け取られる他の命令（非制御命令）は、処理エンジン３０２へ出力するために待ち行列に入れられる。ディスパッチャー４３５は、命令を処理するのに必要な（計算又は記憶）リソースの利用性に基づき命令を出力するように構成されてもよい。ディスパッチャー４３５のある実施形態では、スコアボードスキームを使用して、リソースの利用性を追跡すると共に、どの命令を処理エンジン３０２へ出力できるか決定する。処理エンジン３０２が命令を受け取ると、その命令を実行するのに必要なオペランドを得るために読み取り要求が発生されて、その読み取り要求がＬＲＦ３０４又は共有メモリ３０６へ出力される。次いで、命令は、オペランドが得られたときに処理エンジン３０２によって処理される。
【００５６】
[0066]図４Ｂは、本発明の１つ以上の態様に基づき関数ポインタを参照するインデックスを記憶するレジスタを参照する間接的な分岐命令の概念図である。スレッドが条件テストを使用して独立して分岐するのを許すのに加えて、コア２０８は、ＢＲＸ命令を使用して間接的分岐及び間接的な関数呼び出しをサポートすることを含む。間接的な分岐及び関数呼び出しは、スイッチステートメントのようなＣ＋＋プログラミング特徴を実施するのに使用される。Ｃ＋＋言語は、プロセッサが関数ポインタを経て間接的に関数を呼び出すのを要求するランタイム関数バインディング及びバーチャル関数を使用する。この能力は、関数ポインタをオペランドとして受け容れるＢＲＸ命令により各個々のスレッドに対して設けられる。コンパイラーは、ＢＲＸ命令を使用してスイッチステートメントを実施して、間接的分岐を遂行すると共に、間接的分岐テーブルを構成し、テスト及び分岐の逐次チェーンの発生に比して性能を改善する。間接的な関数呼び出しに対してＢＲＸ命令が使用されるときには、ＰＲＥＴ（プレリターン）又はＣＡＬ（呼び出し）命令（図４Ｂには示さず）を先行させて、関数リターンアドレスをＣＲＳスタック４２５にプッシュさせる。
【００５７】
[0067]プログラムコード４７０における分岐命令ＢＲＸは、サブルーチンＭＹＳＵＢに対応する関数ポインタを指定する。コントローラ４１５は、ＢＲＸ命令を受け取ると、ＢＲＸ命令に対してオペランドとして指定されたレジスタを読み取る。この実施例では、アドレスレジスタ４４５における各スレッドのためのＡ２レジスタが、スレッドグループにおけるアクティブなスレッドに対するオペランドとして指定され、コントローラ４１５は、数値定数インデックス４７２を、命令キャッシュ４３０へ出力されるＢＲＸ命令のためのオペランドとして挿入する。オペランド、例えば、定数インデックス４７２は、定数キャッシュ４１０にアクセスするためのスレッドグループインデックスとして使用される。命令キャッシュ４３０は、ＢＲＸ命令を受け取ると、定数インデックス４７２を使用して、スレッドグループ内のアクティブなスレッドに対する関数ポインタのセットを記憶する定数キャッシュ４１０の１つ以上のエントリーを読み取る。本発明のある実施形態では、一度に１つの定数がアクセスされ、命令キャッシュ４３０は、読み取った要求を、アドレス値（定数インデックス４７２）に基づいて直列化する。図４Ｂに示すように、関数ＭＹＳＵＢを指すポインタ４７４が定数キャッシュ４１０のエントリーから読み取られる。
【００５８】
[0068]各スレッドに対するアドレスが異なるキャッシュインデックスを指定することがあるので、異なるスレッドに対して定数キャッシュ４１０から異なる関数ポインタが読み取られることがあることに注意されたい。全てのアクティブなスレッドが同じ関数ポインタを指定しないときには、アクティブなスレッドが発散し、そして各独特の関数ポインタ値に対してＢＲＸ命令が実行される。換言すれば、関数ポインタにより指定された異なる関数が、各独特の関数ポインタを共有するスレッドに対して直列に実行される。テークンマスク(takenmask)が制御情報４４０と共にディスパッチャー４３５により（条件コードユニット４５０を経て）コントローラ４１５へ出力され、第１の独特の関数ポインタを取り上げるスレッドを指示する。コントローラ４１５は、ＤＩＶＥＲＧＥトークンを、現在のアクティブなマスク及びＢＲＸ命令のプログラムカウンタと共に、ＣＲＳスタック４２５にプッシュする。ＤＩＶＥＲＧＥトークンは、図８を参照して述べるように、各独特の関数ポインタに対してＢＲＸ命令を繰り返すために、サブルーチンの実行が完了したときにポップされる。
【００５９】
[0069]図４Ｃは、本発明の１つ以上の態様に基づき、スレッドグループの各スレッドに対して１つずつ、スレッドグループに対する関数ポインタのセットを記憶するレジスタを参照する間接的な分岐命令の概念図である。本発明のこの実施形態では、関数ポインタのセットは、アドレスレジスタＡ２により指定されたアドレスレジスタ４４５のパー・スレッド(per-thread)エントリーに記憶される。プログラムコード４７８は、関数ポインタのセット、即ち関数ＭＹＳＵＢを指すポインタ４７６をアドレスレジスタに直接記憶し、関数ポインタを定数キャッシュ４１０に記憶するのではない。本発明のある実施形態では、ＬＲＦ３０４、共有メモリ３０６又はグローバルメモリ３２０のエントリーは、関数ポインタを記憶し、そしてオペランドとして指定され、スレッドグループ内のスレッドが発散して、異なるサブルーチンを実行できるようにする。関数ポインタをアドレスレジスタ４４５に記憶しない本発明の実施形態では、関数ポインタが、コントローラ４１５ではなく、処理エンジン３０２によって読み取られる。
【００６０】
[0070]図５Ａは、本発明の１つ以上の態様に基づき一連のプログラム命令を処理するための方法ステップのフローチャートである。当業者であれば、これら方法ステップを任意の順序で遂行するように構成されたいかなるシステムも本発明の範囲内に入ることが理解されよう。ステップ５００において、コントローラ４１５は、アクティブなプログラムカウンタを命令キャッシュ４３０へ出力することによりスレッドに対するアクティブなプログラムカウンタ（ＰＣ）の現在設定に対応するプログラム命令をフェッチする。ステップ５０５において、ディスパッチャー４３５は、命令が制御命令であるかどうか決定する。命令が制御命令であることをディスパッチャー４３５が決定すると、方法は、ステップ５０７へ進み、ディスパッチャー４３５は、制御命令を条件コードユニット４５０へ出力し、そして条件コードユニット４５０は、制御命令が呼び出し命令であるかどうか決定する。
【００６１】
[0071]命令が呼び出し命令であることを条件コードユニット４５０が決定すると、方法はステップ５０８へ進み、そして条件コードユニット４５０は、ＣＡＬＬのトークンタイプ、ターゲットプログラムカウンタ（呼び出し命令により指定された）、テークンマスク（アクティブなマスクに等しい）、及びトークンプログラムカウンタを含む制御情報を出力する。トークンプログラムカウンタは、サブルーチン呼び出しのリターンアドレスであり、スレッドのための次のプログラム命令を指すように増加されたアクティブなプログラムカウンタ、即ち「ノット・テークン(nottaken)」プログラムカウンタに等しい。呼び出し命令は、条件付きではないので、テークンマスクは、アクティブなマスクに等しい。又、制御情報は、ディスパッチャー４３５から受け取ったディセーブルマスクも含み得る。ステップ５０９において、コントローラ４１５は、プログラムカウンタ記憶装置４０５にスレッドグループに対して記憶されたアクティブなプログラムカウンタを、ターゲットプログラムカウンタにセットし、呼び出し命令を実行する。呼び出し命令は、ＣＲＳスタック４２５へトークンをプッシュすることによってネストレベルを高めるので、ディセーブルマスクは不変である。ディセーブルマスクは、ネストレベルを下げる命令が実行され且つＣＲＳスタック４２５からトークンがポップされたときに変化する。
【００６２】
[0072]各制御命令に対してＣＲＳスタック４２５へプッシュされる異なるトークンがテーブル１に概略的に示されている。本発明のある実施形態では、ＣＲＳスタック４２５各エントリーは、６４ビットである。トークンは、トークンタイプと、マスク（トークンマスク）と、トークンがポップされるときにスレッドグループの実行を再開すべき場所を指定するトークンプログラムカウンタとを含む。トークンタイプＩＤ＿ＳＹＮＣ、ＩＤ＿ＤＩＶＥＲＧＥ、ＩＤ＿ＣＡＬＬ、及びＩＤ＿ＢＲＥＡＫは、各々、ＳＳＹ命令、分岐（ＢＲＡ及びＢＲＸ）命令、ＣＡＬＬ及びＰｒｅＲｅｔｕｒｎ（ＰＲＥＴ）命令、及びＰｒｅＢｒｅａｋ（ＰＲＥＢＲＫ）命令に対応する。呼び出しトークンに含まれるマスクは、呼び出し／リターン分岐に遭遇したときに存在したアクティブなマスク（ａｃｔｉｖｅ＿ｍａｓｋ）であり、そして呼び出しトークンにおけるプログラムカウンタは、リターンプログラムカウンタ（ｎｏｔ＿ｔａｋｅｎ＿ｐｃ）である。リターンプログラムカウンタは、増加されたアクティブなプログラムカウンタに等しい呼び出し命令に続くプログラムの命令（即ち、フォールスルー(fall-through)命令）を指定する。
【表１】
0005701487.tif 000002
【００６３】
[0073]ステップ５０７において、制御命令が呼び出し命令でないことを条件コードユニット４５０が決定すると、方法はステップ５１０へ進み、そこで、条件コードユニット４５０は、制御命令がＳＳＹ（セット同期）、プレブレーク又はプレリターン命令であるか決定する。制御命令がＳＳＹ、ＰＲＥＢＲＫ又はＰＲＥＴ命令であることを条件コードユニット４５０が決定すると、ステップ５１２において、条件コードユニット４５０は、ＳＳＹ(同期)、ＰＲＥＢＲＫ(プレブレーク)又はＰＲＥＴ（プレリターン）のトークンタイプ、テークンマスクとしてのアクティブなマスク、及びコントローラ４１５への命令によりトークンプログラムカウンタとして指定されたｔａｒｇｅｔ＿ｐｃ（ターゲットプログラムカウント）を含む制御プログラムを出力し、そしてコントローラ４１５は、ＣＲＳスタック４２５にトークンをプッシュする。トークンに含まれたトークンマスクは、アクティブなマスクであり、ＳＳＹ、ＰＲＥＢＲＫ及びＰＲＥＴ命令は、ＣＲＳスタック４２５にトークンをプッシュするので、ディセーブルマスクは不変である。ステップ５１４では、コントローラ４１５は、プログラムカウンタ記憶装置４０５にスレッドに対して記憶されたアクティブなプログラムカウンタを増加して、スレッドに対する次の命令を指すようにする。
【００６４】
[0074]ここで、ステップ５０５に戻ると、命令が制御命令でないとディスパッチャー４３５が決定した場合には、方法はステップ５２０へ進み、ディスパッチャー４３５は、スレッドグループ内のスレッドを同期しなければならないことを示すｐｏｐ  ｓｙｎｃ（同期）フラグを命令が含むかどうか決定する。ｐｏｐ  ｓｙｎｃフラグは、ＳＳＹ命令の逆の意味を有する。ｐｏｐ  ｓｙｎｃフラグは、最後のＳＳＹ命令がｓｙｎｃトークン（トークンタイプＳＳＹ）をＣＲＳスタック４２５へプッシュさせたために発散したスレッドグループのスレッドが、ｐｏｐ  ｓｙｎｃフラグを含む命令に対して実行されるべきであることを指示する。ここに詳細に述べるように、このプロセスは、この最後のｓｙｎｃトークンがＣＲＳスタック４２５へプッシュされたときに存在したスレッド同期のレベルを再確立する。換言すれば、このプロセスは、最後のＳＳＹ命令に遭遇したときに存在したスレッド同期のレベルを再確立し、最後のＳＳＹ命令により指定されたターゲットアドレス（ＳＳＹトークンのトークンプログラムカウンタ）において実行を開始する。好ましい実施形態では、同期オペレーションは、キャリア命令（即ち、ｐｏｐ  ｓｙｎｃフラグを含む命令）の他のオペレーションの前に行われる。別の実施形態では、同期オペレーションは、個別の命令を使用して行われてもよいし、或いはキャリア命令の他のオペレーションの後に同期オペレーションを行うこともできる。制御命令は、ｐｏｐ  ｓｙｎｃフラグのためのキャリア命令ではないことに注意されたい。
【００６５】
[0075]ステップ５２０において、命令がｐｏｐ  ｓｙｎｃフラグを含むとディスパッチャー４３５が決定すると、ステップ５２５において、ディスパッチャー４３５は、条件コードユニット４５０を経てコントローラ４１５へ制御情報を出力し、コントローラ４１５は、ＣＲＳスタック４２５をアンワインド（unwind）するように進み、スレッドグループ内の（アクティブな）スレッドの同期をとる。コントローラ４１５へ出力される制御情報は、ＣＲＳスタック４２５をアンワインドしなければならないことを指示するアンワインドスタック信号を含む。キャリア命令は、スタックがアンワインドされ且つアクティブなスレッドが同期された後に実行される。ステップ５２５の詳細は、図５Ｂを参照して説明する。
【００６６】
[0076]ステップ５２０において、命令がｐｏｐ  ｓｙｎｃフラグを含まないとディスパッチャー４３５が決定すると、ステップ５２２において、ディスパッチャー４３５は、命令を処理エンジン３０２へ実行のために出力する。ステップ５２７において、ディスパッチャー４３５は、条件コードユニット４５０を経てコントローラ４１５へ増加ＰＣ信号を含む制御情報を出力し、そしてコントローラ４１５は、スレッドに対してプログラムカウンタ記憶装置４０５に記憶されたアクティブなプログラムカウンタを増加する。或いは又、増加されたアクティブなプログラムカウンタがコントローラ４１５へ出力される。
【００６７】
[0077]ここで、ステップ５１０へ戻ると、制御命令がＳＳＹ、ＰＲＥＢＲＫ又はＰＲＥＴ命令でないことを条件コードユニット４５０が決定した場合には、ステップ５３０において、条件コードユニット４５０は、制御命令が分岐命令であるかどうか決定する。分岐命令は、非条件付き分岐及び条件付き分岐命令（ＢＲＡ）と、非条件付き間接的分岐及び条件付き間接的分岐命令（ＢＲＸ）とを含む。ＢＲＸ命令は、１つ以上の関数ポインタをＢＲＸへのオペランドとして指定することにより間接的な関数呼び出しを実行するように使用される。
【００６８】
[0078]間接的な分岐命令は、分岐アドレス（関数ポインタ）をコンパイル時に決定する必要がないので、より大きな融通性を許すように使用できる。分岐ターゲットレジスタは、スレッドグループ内の全てのスレッドに使用される単一分岐アドレス（又は定数インデックス）を記憶することができる。分岐ターゲットレジスタには、プログラムの実行中に、計算値を書き込むことができる。或いは又、スレッドグループ内の各スレッドが、間接的な分岐命令に対して異なる分岐アドレスを指定し（直接的に又は定数キャッシュ４１０のインデックスとして）、テーブル１に示すＹ（１）発散を生じてもよい。各スレッドに対して分岐アドレス（１つ又は複数）が読み取られて、Ｐ路の間接的分岐を許す。各独特の分岐アドレス及び最後の独特の分岐アドレスに対して間接的な分岐命令が実行され、テーブル１に示すＹ（２）発散を生じ、ここで、ノット・テークンプログラムカウンタがＣＲＳスタック４２５にプッシュされる。スレッドは、条件付き分岐内の間接的な関数呼び出しのために発散し得ることに注意されたい。図８を参照して述べるように、各独特の分岐アドレスに対してスレッドの実行が直列化されるときにアクティブであるスレッドを指示するためにアクティブなマスクが使用される。
【００６９】
[0079]ステップ５３０において、制御命令が分岐命令でないことを条件コードユニット４５０が決定すると、それはリターン又はブレーク命令であり、そして呼び出し／リターン分岐に関連したサブルーチンの終了、又はプレブレーク分岐に関連した命令のループの終了に到達し、方法はステップ５３２へ進む。ステップ５３２において、条件コードユニット４５０は、コントローラ４１５へ出力されるテークンマスクを発生し、コントローラ４１５は、アクティブなスレッドの１つ以上が条件テスト結果に基づいて発散するかどうか決定する。条件付きリターン又はブレーク命令によって指定された条件テストに対して真と評価するアクティブなスレッドは、いずれも、テークンマスクによりディセーブルされる。これらのスレッドは、他のアクティブなスレッド（条件テストに対して偽と評価する）が実行を続ける間に、ディセーブルされてアイドル状態に保たれる。ディセーブルされたスレッドに対応するビットは、テークンマスクにおいてクリアされ、テークンマスクにおいてセットされたビットの数が、アクティブなマスクにおいてセットされたビットの数以下となるようにする。
【００７０】
[0080]ステップ５３２において、スレッドが発散しない（テークンマスクがアクティブなマスクに等しい）ことをコントローラ４１５が決定すると、ステップ５２５において、コントローラ４１５は、ＣＲＳスタック４２５をアンワインド（unwind）するように進む。アンワインドプロセス中に、リターン又はブレーク命令によりディセーブルされたスレッドは、図５Ｂを参照して更に説明するように、それに対応する呼び出しトークン（ＩＤ＿ＣＡＬＬ）又はプレブレークトークン（ＩＤ＿ＢＲＥＡＫ）がＣＲＳスタック４２５からポップされたときにイネーブルされる。
【００７１】
[0081]ステップ５３２において、スレッドが発散する（テークンマスクがアクティブなマスクに等しくない）ことをコントローラ４１５が決定すると、ステップ５３４において、コントローラ４１５は、変更されたディセーブルマスクを決定する。これらスレッドに対するディセーブルマスクの状態は、ｔａｋｅｎ＿ｍａｓｋビットがセットされたスレッドが、特定事象を待機する間アイドル状態であることを指示する値にセットされる。この事象は、プログラムの終了であるか、又はＣＲＳスタック４２５からポップされるべき特定のトークンに対するものである。
【００７２】
[0082]本発明のある実施形態では、０のディセーブル状態は、スレッドがイネーブルされることを指示し、１のディセーブル状態は、スレッドがリターン命令を実行し、且つＣＲＳスタック４２５からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、２のディセーブル状態は、スレッドがブレーク命令を実行し、且つＣＲＳスタック４２５からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして３のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。
【００７３】
[0083]ステップ５３６において、コントローラ４１５は、アクティブなマスクを変更する。より詳細には、「条件を取り入れた」スレッドグループ内のスレッドに対応するアクティブなマスクのビットがクリアされて、それらのスレッドが非アクティブとして現れるようにする。換言すれば、テークンマスクとアクティブなマスクとの間でビットワイズのＸＯＲ（排他的ＯＲ）が遂行され、変更型アクティブマスクを生成する。ステップ５３９では、コントローラ４１５が、スレッドに対する次の命令を実行するために、アクティブなプログラムカウンタを増加する。
【００７４】
[0084]ここで、ステップ５３０に戻ると、制御命令が分岐命令であることを条件コードユニット４５０が決定すると、ステップ５３５において、コントローラ４１５は、条件コードユニット４５０により与えられたテークンマスクに基づいていずれかのアクティブなスレッドが発散するかどうか決定する。ステップ５３５において、条件コードユニット４５０は、テークンマスク、トークンタイプ、及びターゲットプログラムカウンタを含む制御情報をコントローラ４１５へ出力する。ステップ５３５において、少なくとも１つのアクティブなスレッドがスレッドグループ内の他のアクティブなスレッドから発散することをコントローラ４１５が決定すると、ステップ５３７において、コントローラ４１５は、発散トークン（ＩＤ＿ＤＩＶＥＲＧＥ）をＣＲＳスタック４２５にプッシュする。トークンに含まれたトークンマスクは、ノット・テークンマスク（ｎｏｔ＿ｔａｋｅｎ＿ｍａｓｋ）であり、これは、条件テストに対して「真」と評価しないアクティブなスレッド、即ち分岐をとらないアクティブなスレッドを指示する。コントローラ４１５は、テークンマスク及びアクティブなマスクを使用してトークンマスクを決定することができる。トークンプログラムカウンタは、スレッドにおいて次の命令を指定するために増加されるアクティブなプログラムカウンタに等しい。
【００７５】
[0085]ステップ５４０において、コントローラ４１５は、条件テストに対して「真」と評価し即ち分岐をとるアクティブなスレッドを指示するテークンマスクとしてアクティブなマスクを決定する。ステップ５４５において、コントローラ４１５は、アクティブなプログラムカウンタを、分岐命令により指定されたターゲットプログラムカウンタ（アドレス）にセットする。
【００７６】
[0086]ステップ５３５において、アクティブなスレッドがどれも発散しないとコントローラ４１５が決定すると、ステップ５４２において、コントローラ４１５は、全てのアクティブなスレッドが分岐をとるかどうか決定する。それに代わるものとして、アクティブなスレッドがいずれも分岐をとらない場合には、条件コードユニット４５０が、０ｘ００００に等しいテークンマスクを出力する。ステップ５４４において、コントローラ４１５は、スレッドにおいて次の命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置４０５に記憶されたアクティブなプログラムカウンタを増加する。ステップ５４２において、全てのアクティブなスレッドが分岐をとるとコントローラ４１５が決定すると、ステップ５４５において、コントローラ４１５は、コントローラ４１５への分岐命令により指定されたターゲットプログラムカウンタ（アドレス）に等しくなるようにアクティブなプログラムカウンタを更新し、そしてコントローラ４１５は、分岐により指定された命令を実行するために、スレッドグループに対してプログラムカウンタ記憶装置４０５に変更されたアクティブなプログラムカウンタを記憶する。
【００７７】
[0087]ＣＲＳスタック４２５を使用すると、ＰＰＵ２０２は、スレッドの発散及び同期を行いながら、スレッドグループを処理できるようになる。ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状の条件及びサブルーチン内のスレッド完了を含む更に進歩した制御フローをサポートするのに使用される。各スレッドグループに対して単一のディセーブルマスクがスレッド状態記憶装置４２０に記憶され、そしてディセーブルマスクは、ＣＲＳスタック４２５からポップされたトークンと結合されて、ディセーブルされたスレッドグループ内のスレッドの実行を再開する。
【００７８】
[0088]図５Ｂは、本発明の１つ以上の態様に基づき図５Ａのステップ５２５を完了するためにＣＲＳスタック４２５をアンワインド（unwinding）する方法ステップのフローチャートである。ＣＲＳスタック４２５は、処理エンジン３０２により同時に実行できるＧスレッドグループの各々に対して実行スタック４５５を備え、各スレッドグループが、他のスレッドグループとは独立して進行できるようにする。ステップ５５０において、コントローラ４１５は、スレッドグループに対する実行スタック４５５が空であるかどうか決定し、もしそうであれば、ステップ５５２において、スレッドグループの実行が完了し、そして命令ユニット３１２は、スレッドグループが実行を完了したことをコアインターフェイス３０３に通知する。ステップ５５０において、実行スタック４５５が空でないことをコントローラ４１５が決定すると、ステップ５５５において、コントローラ４１５は、実行スタック４５５から実行スタック４５５の最上部にトークンをポップさせる。ステップ５６０において、コントローラ４１５は、トークンが呼び出し又はプレブレークトークンであるかどうか決定し、そしてトークンが呼び出し又はプレブレークトークンでないときには、ステップ５７０へ直接進む。
【００７９】
[0089]呼び出しトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きリターン命令の実行を完了しそして（ディセーブルマスクに基づいて）ディセーブルされたスレッドをイネーブルすべきであることを指示する。プレブレークトークンは、トークンマスクにおいてイネーブルされたビットに対応するスレッドグループ内の全スレッドが条件付きブレーク命令の実行を完了しそして（ディセーブルマスクに基づいて）ディセーブルされたスレッドをイネーブルすべきであることを指示する。スレッドグループ内のアクティブなスレッドは、トークンと共に記憶されるマスク、即ちトークンマスクにより指示される。重要なことに、呼び出し及びプレブレークループをネスト状にできるように、ディセーブルマスクを使用して、スレッドグループ内のスレッドをディセーブルする。ステップ５６０において、コントローラ４１５は、トークンが呼び出し又はプレブレークトークンであることを決定し、次いで、ステップ５６５において、コントローラ４１５は、スレッドに対してディセーブルマスクを更新する。より詳細には、トークンが呼び出しトークンであるときには、コントローラ４１５は、スレッドが条件付きリターン命令によってディセーブルされたことを指示する１のディセーブル状態をもち且つ呼び出しトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。トークンがプレブレークトークンであるときには、コントローラ４１５は、スレッドが条件付きブレーク命令によってディセーブルされたことを指示する２のディセーブル状態をもち且つプレブレークトークンマスクに基づいてアクティブである全てのスレッドに対してディセーブル状態をリセットする。
【００８０】
[0090]ステップ５６０において、トークンが呼び出しトークンでもプレブレークトークンでもないことをコントローラ４１５が決定すると、トークンは、ｓｙｎｃ又は発散のいずれかのトークンである。ステップ５７０において、コントローラ４１５は、アクティブなマスクをトークンからのマスクにセットし、次いで、ディセーブルされたスレッドを除去することにより、アクティブなマスクを更新する。より詳細には、ディセーブルされたことを指示するディセーブル状態を有するスレッドは、それらスレッドが誤って実行を再開するのを防止するために、（トークンから）更新されたアクティブなマスクにおけるそれらの対応ビットをクリアしている。これは、スレッドがイネーブルされないことをディセーブル状態が指示する限り、スレッドがインアクティブのままであることを保証する。換言すれば、アクティブなマスクは、スレッドグループ内の他のスレッドが条件付きブレーク又はリターン分岐の実行を完了するのを待っているスレッドグループ内のいずれかのスレッドの処理をディセーブルするように更新される。
【００８１】
[0091]ステップ５７５において、コントローラ４１５は、更新されたアクティブなマスクがゼロに等しく、スレッドグループ内のどのスレッドもアクティブでないことを指示するかどうか決定する。ステップ５７５において、どのスレッドもアクティブでないことをコントローラ４１５が決定すると、方法はステップ５５０へ戻り、別のトークンをポップする（又はプログラムの実行を完了する）。さもなければ、ステップ５８０において、コントローラ４１５は、アクティブなプログラムカウンタを、ステップ５５５においてポップされたトークンからのプログラムカウンタにセットする。
【００８２】
[0092]テーブル４に戻ると、呼び出しトークンのプログラムカウンタは、リターンプログラムカウンタである。アクティブなプログラムカウンタをリターンプログラムカウンタに等しくセットすることで、アクティブなスレッドが、呼び出し命令に続くプログラムの命令（即ち、フォールスルー命令）にリターンすることが規定される。ブレークトークンにおけるプログラムカウンタは、ループ後プログラムカウンタ(after-loopprogram counter)である。アクティブなプログラムカウンタをこのループ後プログラムカウンタにセットすることで、アクティブなスレッドが、ループ後プログラムカウンタにより指定されたアドレスをもつ命令へ分岐することが規定される。
【００８３】
[0093]ｓｙｎｃトークンに含まれたマスクは、それに対応するＳＳＹ命令が実行されたときに存在したアクティブなマスクである。従って、アクティブなマスクを、ｓｙｎｃトークンに含まれたマスクに等しくセットすると、ＳＳＹ命令に最初に遭遇したときにアクティブであったスレッドであって、介在する条件付きリターン又はブレーク命令によりディセーブルされるスレッドを除く全てのスレッドをアクチベートする。ｓｙｎｃトークンに含まれたプログラムカウンタは、ＳＳＹ命令により指定されたプログラムカウンタである。
【００８４】
[0094]分岐及び間接的分岐のための発散トークンに含まれたマスクは、ノット・テークン(nottaken)マスクである。一実施形態では、アクティブなマスクをノット・テークンマスクにセットすることは、発散トークンに関連した条件付き分岐の「イフ・サイド(if-side)」を実行する必要のあるスレッドをアクチベートする一方、その分岐の「エルス・サイド(else-side)」の実行を丁度完了したスレッドをインアクチベートするように作用する。２路発散を伴う分岐及び間接的分岐に対して発散トークンに含まれたプログラムカウンタは、ノット・テークンプログラムカウンタである。アクティブなプログラムカウンタをノット・テークンプログラムカウンタにセットすることで、新たにアクチベートされるスレッドが、条件付き分岐の「イフ・サイド」で第１の命令を実行することが規定される。このプロセスは、条件付き分岐の「イフ・サイド」の実行をイネーブルする。Ｐ路発散を伴う間接的分岐に対して発散トークンに含まれたプログラムカウンタは、アクティブなプログラムカウンタである。それ故、ＢＲＸ命令は、各独特の分岐アドレスに対して実行される。
【００８５】
[0095]テーブル２は、図５Ｂの方法ステップに対するＣプログラミング言語擬似コードを示し、ｄｉｓａｂｌｅ＿ｍａｓｋ．ｒｅｔｕｒｎは、スレッドが呼び出しトークンを待機するときにアサートされ、ｄｉｓａｂｌｅ＿ｍａｓｋ．ｂｒｅａｋは、スレッドがブレークトークンを待機するときにアサートされ、そしてｄｉｓａｂｌｅ＿ｍａｓｋ．ｅｏｓは、スレッドがプログラムを退出するときにアサートされる。図５Ａを参照して既に説明したように、本発明のある実施形態では、１のディセーブル状態は、スレッドがリターン命令を実行し、且つＣＲＳスタック４２５からマッチング呼び出しトークンがポップされるまでスレッドがディセーブルされることを指示し、２のディセーブル状態は、スレッドがブレーク命令を実行し、且つＣＲＳスタック４２５からマッチングプレブレークトークンがポップされるまでスレッドがディセーブルされることを指示し、そして３のディセーブル状態は、スレッドが退出となり且つプログラムの残り全体にわたってディセーブルされることを指示する。それ故、これらの実施形態では、ｄｉｓａｂｌｅ＿ｍａｓｋ．ｒｅｔｕｒｎは、ディセーブル状態が１であるときにアサートされ、ｄｉｓａｂｌｅ＿ｍａｓｋ．ｂｒｅａｋは、ディセーブル状態が２であるときにアサートされ、そしてｄｉｓａｂｌｅ＿ｍａｓｋ．ｅｏｓは、ディセーブル状態が３であるときにアサートされる。
【表２】
0005701487.tif 000003
【００８６】
[0096]ディセーブルマスクは、条件付きリターン及びブレーク、プレブレーク−ブレークループ内からのリターン、並びにネスト状条件及びサブルーチン内のスレッド完了、を処理するのに使用される。ディセーブルマスクの使用に代わるものは、スレッドディセーブル事象（条件付きリターン又はブレーク）が生じたときに実行スタック４５５をウオーク(walk)し、そして全ての関連トークンにおけるセーブされたアクティブなマスクを変更することである。しかしながら、実行スタック４５５をウオークすることは、実行スタック４５５が非常に深くて、グローバルメモリ３２０に記憶された部分を伴うので、潜在的に時間浪費である。それ故、ディセーブルマスクは、性能に関して効果的であり、同時に実行できるＧ個のスレッドの各々に対して１つのマスクしか必要としない。
【００８７】
[0097]テーブル３は、本発明の１つ以上の態様を例示するために「イフ・ゼン・エルス(if-then-else)」ステートメントを実施する分岐命令を含むプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表３】
0005701487.tif 000004
【００８８】
[0098]図６は、本発明の１つ以上の態様に基づき、テーブル３に示すプログラム命令のシーケンスが実行されるときに、ＣＲＳスタック４２５内の実行スタックをどのようにポピュレート（populated）しアンワインド（unwound）するかを概念的に例示する。
【００８９】
[0099]図示されたように、欄６００は、命令ユニット３１２がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄６０５は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、８つのスレッドを含み、そして８つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、０ｘｆｆである。又、アクティブなプログラムカウンタは、０の初期値を有すると仮定する。
【００９０】
[00100]コントローラ４１５は、最初に、０のプログラムカウンタ値に対応するＭＡＤ命令をフェッチする（ステップ５００）。ＭＡＤ命令は、制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２は、この命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ１に増加される（ステップ５２７）。次いで、コントローラ４１５は、ＳＳＹ命令をフェッチし、そしてトークンタイプＳＹＮＣ、アクティブなマスク（０ｘｆｆ）、及びＳＳＹ命令により指定されたターゲットプログラムカウンタ（ＬＡＢＥＬ１、ＰＣ＝７）を含むｓｙｎｃトークンを実行スタック４５５にプッシュする（ステップ５１２）。欄６１０は、各プログラム命令が実行された後に実行スタック４５５の最上部にあるトークンを示す。アクティブなプログラムカウンタは、０ｘ２へ増加される（ステップ５１４）。
【００９１】
[00101]次いで、コントローラ４１５は、条件ｘがゼロ未満である場合にターゲットプログラムカウンタアドレスＬＡＢＥＬ０（ＰＣ＝６）へ分岐するＢＲＡ  ＬＴ.ｘ命令をフェッチする。ＢＲＡ命令は、条件付き分岐命令であり、分岐テークン(taken)経路及びノット・テークン(not-taken)経路を決定するために条件テストが使用される。ＢＲＡ命令により指定された条件テスト（即ち、ｘは、０未満）を満足し、従って、分岐をとって、「イフ・ゼン・エルス(if-then-else)」ステートメントの「エルス・サイド」を実行するために、６つのスレッドが仮定される。１つ以上のアクティブなスレッドが発散するので、コントローラ４１５は、発散トークン（ＤＩＶ）を実行スタック４５５にプッシュする（ステップ５３７）。欄６１５は、各プログラム命令が実行された後に実行スタック４５５の最上部より１エントリー下のトークンＴＯＳ−１（スタックの最上部・マイナス・１）を示す。
【００９２】
[00102]発散トークンに含まれるマスクは、０ｘ０ｃの値を有し、これは、ノット・テークンマスクであり、条件テストを満足しなかった２つのスレッドを反映する。これら２つのスレッドは、分岐テークンのエルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、０ｘｆ３であり、アクティブなマスクは、テークンマスクにセットされる。発散トークンに含まれるプログラムカウンタは、０ｘ３の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第１命令（即ち、フォールスルー命令）のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、０ｘ６のターゲットプログラムカウンタにセットされる（ステップ５４５）。
【００９３】
[00103]次いで、コントローラ４１５は、ＡＤＤ命令をフェッチする。ＡＤＤ命令は、制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２は、この命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ７に増加される（ステップ５２７）。次いで、コントローラ４１５は、ｐｏｐ−ｓｙｎｃフラグ（．Ｓ）を含むＭＡＸ．Ｓ命令をフェッチする。ｐｏｐ−ｓｙｎｃフラグは、命令がプログラム内の同期ポイントであることを指定する。ｐｏｐ−ｓｙｎｃフラグが含まれるので、コントローラ４１５は、ＢＲＡ  ＬＴ.ｘによりプッシュされた発散トークンをポップし（ステップ５５５）、そしてアクティブなマスクを０ｘｃへ更新すると共に、アクティブなプログラムカウンタを０ｘ３にセットすることにより（ステップ５７０、５７５及び５８０）、実行スタック４５５をアンワインド（unwinds）する（ステップ５２５）。次いで、コントローラ４１５は、ＭＵＬ命令をフェッチする（条件付き分岐のイフ・サイド）。ＭＵＬ命令は制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２がこの命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ４に増加される（ステップ５２７）。
【００９４】
[00104]次いで、コントローラ４１５は、次のＭＵＬ命令（条件付き分岐のイフ・サイドに対する第２の命令）をフェッチする。このＭＵＬ命令も制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２がこの命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ５に増加される（ステップ５２７）。
【００９５】
[00105]次いで、コントローラ４１５は、ＬＡＢＥＬ１のターゲットプログラムカウンタ（ＰＣ＝７）を指定するＢＲＡ命令をフェッチする。ＢＲＡ命令は、常にとられる無条件命令であり、それ故、アクティブなスレッドは発散しない。アクティブなスレッドは、全て、分岐をとるので、アクティブなプログラムカウンタは、０ｘ７のターゲットプログラムカウンタにセットされる（ステップ５３５、５４２及び５４５）。
【００９６】
[00106]次いで、コントローラ４１５は、ｐｏｐ−ｓｙｎｃフラグ（．Ｓ）を含むＭＡＸ．Ｓ命令をフェッチし、そしてＳＳＹによってプッシュされたｓｙｎｃトークンをポップする（ステップ５５５）と共に、アクティブなマスクを０ｘｆｆに更新し且つアクティブなプログラムカウンタを０ｘ７にセットする（ステップ５７０、５７５及び５８０）ことにより、実行スタックをアンワインド（unwinds）する（ステップ５２５）。次いで、コントローラ４１５は、ＭＡＸ.Ｓ命令をフェッチし、スレッドが同期される（アクティブなマスクが０ｘｆｆである）ので、処理エンジン３０２は、この命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ８に増加される（ステップ５２７）。コントローラ４１５は、キャリア命令（ＭＡＸ）を実行するために、実行スタック４５５がアンワインドされてＭＡＸ．Ｓ命令の.Ｓ部分を処理した後に、ｐｏｐ−ｓｙｎｃフラグを無視しなければならないことに注意されたい。それ故、ｓｙｎｃトークンがポップされると、コントローラ４１５は、ｓｙｎｃトークンがポップされたときにセットされ且つキャリア命令が実行されるときにクリアされる状態のビットを各スレッドグループに対して維持する。
【００９７】
[00107]テーブル４は、本発明の１つ以上の態様を例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされる。
【表４】
0005701487.tif 000005
【００９８】
[00108]テーブル５は、テーブル４のプログラム命令のサブルーチン部分に対するＣプログラミング言語擬似コードを示す。
【表５】
0005701487.tif 000006
【００９９】
[00109]図７は、本発明の１つ以上の態様に基づき、条件付きリターンを含むテーブル４及び５に示すプログラム命令のシーケンスが実行されるときに、実行スタック４５５内の実行スタック４５５をどのようにポピュレート（populated）し、アンワインド（unwound）するかを示す別の概念図である。図示されたように、欄７００は、命令ユニット３１２がプログラム命令を実行する順序を示すと共に、このような各プログラム命令が実行されるときのアクティブなプログラムカウンタを指定する。欄７０５は、各プログラム命令が実行される前のアクティブなマスクの値を示す。欄７１０は、各プログラム命令が実行される前のディセーブルマスクの値を示す。説明上の目的のみで、スレッドグループは、８つのスレッドを含み、そして８つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、０ｘｆｆである。又、アクティブなプログラムカウンタは、５０の初期値を有すると仮定する。
【０１００】
[00110]コントローラ４１５は、先ず、ＳＵＢＲＯＵＴＩＮＥのターゲットプログラムカウンタ（ＰＣ＝０）を指定するアドレス５０においてＣＡＬＬ命令をフェッチする。トークンタイプＣＡＬＬ、アクティブなマスク（０ｘｆｆ）及びターゲットプログラムカウンタを含む呼び出しトークンが実行スタック４５５にプッシュされる（ステップ５０８）。全てのアクティブなスレッドがコールをとるので、アクティブなプログラムカウンタは、０ｘ０のターゲットプログラムカウンタにセットされる（ステップ５０９）。欄７１５は、各プログラム命令が実行された後に実行スタック４５５の最上部にあるトークンを示す。
【０１０１】
[00111]次いで、コントローラ４１５は、ＳＳＹ命令をフェッチし、そしてトークンタイプＳＹＮＣ、アクティブなマスク（０ｘｆｆ）、及びＳＳＹ命令により指定されたターゲットプログラムカウンタ（ＬＡＢＥＬ１、ＰＣ＝７）を含むｓｙｎｃトークンを実行スタック４５５にプッシュする（ステップ５１２）。欄７２０は、各プログラム命令が実行された後に実行スタック４５５の最上部より１エントリー下にあるトークンＴＯＳ−１（スタックの最上部・マイナス・１）を示す。アクティブなプログラムカウンタは、０ｘ２へ増加される（ステップ５１４）。
【０１０２】
[00112]次いで、コントローラ４１５は、ｘにより指定された比較値及びＬＡＢＥＬ０（ＰＣ＝６）のターゲットプログラムカウンタでＬＴ条件テストを指定するＢＲＡ命令をフェッチする。１つ以上のアクティブなスレッドが発散するので、コントローラ４１５は、発散トークン（ＤＩＶ）を実行スタック４５５にプッシュする（ステップ５３７）。欄７２５は、各プログラム命令が実行された後に実行スタック４５５の最上部より２エントリー下にあるトークンＴＯＳ−２（スタックの最上部・マイナス・２）を示す。
【０１０３】
[00113]発散トークンに含まれたマスクは、０ｘ０ｃの値を有し、これは、ノット・テークンマスクであり、逆の条件テストを満足しなかった２つのスレッドを反映する。これら２つのスレッドは、エルス・サイドとは対照的に、条件付き分岐のフォールスルーのイフ・サイドを実行する。テークンマスクは、０ｘｆ３であり、アクティブなマスクは、欄７０５に示すように、テークンマスクに等しくセットされる（ステップ５４０）。発散トークンに含まれるプログラムカウンタは、０ｘ２の値を有し、これは、ノット・テークンプログラムカウンタであり、条件付き分岐のイフ・サイドに関連した第１命令（即ち、フォールスルー命令）のアドレスを反映する。最終的に、アクティブなプログラムカウンタは、０ｘ５のターゲットプログラムカウンタにセットされる（ステップ５４５）。
【０１０４】
[00114]次いで、コントローラ４１５は、ｘにより指定された比較値でＧＴ条件テストを指定するＲＥＴ命令をフェッチする。１つ以上のアクティブなスレッドが発散するので、条件コードユニット４５０は、ディセーブルマスクを決定する（ステップ５３４）。変更型ディセーブルマスクは、０ｘ０００５である（各スレッドが２ビットフラグを有する）。というのは、アクティブなスレッドのうちの２つが条件テストを満足し、フラグを１にセットして、呼び出し命令を待機しているディセーブル状態を指示するからである。条件コードユニット４５０は、ディセーブルされたスレッドの実行をディセーブルするようにアクティブなマスクを変更する。それ故、アクティブなマスクは、０ｘｆ３から０ｘｆ０へ変化する（ステップ５３６）。最終的に、アクティブなプログラムカウンタは、０ｘ６の値に増加される（ステップ５３９）。
【０１０５】
[00115]次いで、コントローラ４１５は、ＡＤＤ命令をフェッチする。ＡＤＤ命令は、制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２は、この命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ７に増加される（ステップ５２７）。次いで、コントローラ４１５は、ｐｏｐ−ｓｙｎｃフラグ（．Ｓ）を含むＭＵＬ．Ｓ命令をフェッチする。ｐｏｐ−ｓｙｎｃフラグが含まれるので、コントローラ４１５は、ＢＲＡ発散トークンをポップし（ステップ５５５）、そしてアクティブなマスクを０ｘｃへ更新すると共に、アクティブなプログラムカウンタを０ｘ２にセットすることにより（ステップ５７０、５７５及び５８０）、実行スタック４５５をアンワインド（unwinds）する（ステップ５２５）。次いで、コントローラ４１５は、ＭＵＬ命令をフェッチする（条件付き分岐のイフ・サイド）。ＭＵＬ命令は制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２がこの命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ３に増加される（ステップ５２７）。
【０１０６】
[00116]次いで、コントローラ４１５は、次のＭＵＬ命令（条件付き分岐のイフ・サイドに対する第２の命令）をフェッチする。このＭＵＬ命令も制御命令ではなく、ｐｏｐ−ｓｙｎｃフラグを含まないので、処理エンジン３０２がこの命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ４に増加される（ステップ５２７）。
【０１０７】
[00117]次いで、コントローラ４１５は、ＬＡＢＥＬ１のターゲットプログラムカウンタ（ＰＣ＝７）を指定する（無条件）ＢＲＡ命令をフェッチする。アクティブなスレッドは、全て分岐をとるので、アクティブなプログラムカウンタは、０ｘ７のターゲットプログラムカウンタにセットされる（ステップ５３５、５４２及び５４５）。
【０１０８】
[00118]次いで、コントローラ４１５は、ｐｏｐ−ｓｙｎｃフラグ（．Ｓ）を含むＭＵＬ．Ｓ命令をフェッチし、そしてＳＳＹのｓｙｎｃトークンをポップする（ステップ５５５）と共に、アクティブなマスクを０ｘｆｃに更新し且つアクティブなプログラムカウンタを０ｘ８にセットする（ステップ５７０、５７５及び５８０）ことにより、実行スタックをアンワインド（unwinds）する（ステップ５２５）。次いで、コントローラ４１５は、ＭＵＬ.Ｓ命令をフェッチし、又、.Ｓ部分が実行されると共にスレッドが同期されるので、処理エンジン３０２は、この命令を実行し（ステップ５２２）、アクティブなプログラムカウンタが０ｘ８に増加される（ステップ５２７）。次いで、コントローラ４１５は、ＲＥＴ命令をフェッチし、そして呼び出しトークンをポップする（ステップ５５５）ことにより実行スタックをアンワインドする（ステップ５３２及び５２５）。コントローラ４１５は、呼び出しトークンを待機してディセーブルされたスレッドに対してディセーブル状態をクリアすることによりディセーブルマスクを更新する（ステップ５６５）。次いで、コントローラ４１５は、アクティブなマスクを０ｘｆｆへ更新し、アクティブなプログラムカウンタを０ｘ５１にセットする（ステップ５７０、５７５及び５８０）。次いで、コントローラ４１５は、ＡＤＤ命令をフェッチして、ＡＤＤ命令を処理エンジン３０２へ実行のために出力する。
【０１０９】
[00119]テーブル６は、本発明の１つ以上の態様に基づいてＢＲＸ命令を使用して間接的な関数呼び出しを遂行することを例示するためのプログラム命令のセットである。図示されたように、最も左の欄は、各プログラム命令に関連したプログラムカウンタを示し、そして最も右の欄は、セット内の種々のプログラム命令を示す。プログラム命令は、提示を容易にするためにアッセンブル擬似コードで表わされ、命令の実行は、図８を参照して詳細に説明する。
【表６】
0005701487.tif 000007
【０１１０】
[00120]関数ポインタを経て間接的な関数呼び出しを可能にするために、ＢＲＸ命令のターゲット（関数ポインタ）におけるプログラムコードは、分岐に使用される.Ｓ同期命令ではなくＲＥＴ命令で終了する。ＰＲＥＴ命令は、スレッド同期のための現在のアクティブなマスク（これは、ＢＲＸ命令に関連した全ての関数呼び出しの実行後に生じる）を使用して、ＣＲＳスタック４２５にプッシュされたリターンアドレスをＣＡＬＬトークンとして指定する。ＢＲＸ命令は、ＰＲＥＴ命令に従い、それが実行されるとき、アクティブなスレッドの少なくとも１つが、ＢＲＸオペランドにより指定された関数へ間接的に分岐する。その後のＲＥＴ命令が実行されるときには、他のアクティブなスレッドに対する既に延期された間接的な関数呼び出しの実行が、スレッド指定関数ポインタを使用して、ＢＲＸ命令の繰り返し実行により完了される。ＢＲＸ命令に対して最後の関数呼び出しが実行されるときには、最終的なＲＥＴ命令が、ＰＲＥＴ命令によりＣＲＳスタック４２５にプッシュされたＣＡＬＬトークンをポップし、そしてＣＡＬＬトークンと共にポップされるアクティブなマスクに基づいてスレッドが同期される状態でリターンアドレスへ制御を移行する。
【０１１１】
[00121]テーブル７は、テーブル６のプログラム命令のサブルーチン部分に対するＣプログラミング言語擬似コードを示す。
【表７】
0005701487.tif 000008
【０１１２】
[00122]図８は、本発明の１つ以上の態様に基づき、間接的な関数呼び出しを含むテーブル６に示すプログラム命令のシーケンスが実行されるときにＣＲＳスタック４２５がどのようにポップされアンワインド（unwound）されるかを示す別の概念的な図である。図示されたように、欄８００は、命令ユニット３１２がプログラム命令を実行する順序を示すと共に、各プログラム命令に対するアクティブなプログラムカウンタを指定する。欄８０５は、各プログラム命令が実行される前のアクティブなマスクの値を示す。説明上の目的のみで、スレッドグループは、８つのスレッドを含み、そして８つのスレッドは、全て、最初にアクティブであると仮定する。それ故、アクティブなマスクの初期値は、０ｘｆｆである。この実施例では、条件付き分岐命令の実行のためにディセーブルされるスレッドはない。又、アクティブなプログラムカウンタは、４の初期値を有すると仮定する。
【０１１３】
[00123]第１の命令ＩＡＤＤ .Ｃ１がフェッチされ、Ｒ２とＲ３に記憶された値の差が計算されて、条件コードレジスタＣ１に記憶される。ＣＲＳスタック４２５にプッシュされるトークンはなく、現在アクティブなマスクは不変であり（０ｘｆｆ）、そしてアクティブなプログラムカウンタは５に増加される。第１の条件付きＲ２Ａ命令がフェッチされ、条件テスト（ＬＴ）が条件コードＣ１に対して評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。条件コード指定子（Ｃ１）及びテストされるべき特定の条件（ＬＴ）は、行先レジスタに続きカッコで示されるＡ１。ＭＹＳＵＢ１を指す関数ポインタを記憶する定数キャッシュ４１０のエントリーに対応する定数インデックス（ｉ０）は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ４４５のＡ１エントリーに記憶される。換言すれば、値２（ＭＹ＿ＳＵＢ１に対応するプログラムカウンタ）は、条件コードＣ１が「より少ない(lessthan)」条件にセットされるところの全てのスレッドに対してＡ１へ移動される。ＣＲＳスタック４２５へプッシュされるトークンはなく、現在アクティブなマスクは不変であり（０ｘｆｆ）、そしてアクティブなプログラムカウンタは６に増加される。第２の条件付きＲ２Ａ命令がフェッチされると共に、第２の条件テスト（ＧＥ）が評価されて、どのアクティブなスレッドが命令を実行すべきか決定する。ＭＹＳＵＢ２を指す関数ポインタを記憶する定数キャッシュ４１０のエントリーに対応する定数インデックス（ｉ２）は、条件テストにパスするアクティブなスレッドに対してアドレスレジスタ４４５のＡ１エントリーに記憶される。ＣＲＳスタック４２５へプッシュされるトークンはなく、現在アクティブなマスクは不変であり（０ｘｆｆ）、そしてアクティブなプログラムカウンタは７に増加される。
【０１１４】
[00124]ＭＯＶ命令がフェッチされて実行され、関数の引数として値２を通す。ＣＲＳスタック４２５へプッシュされるトークンはなく、現在アクティブなマスクは不変であり（０ｘｆｆ）、そしてアクティブなプログラムカウンタは８に増加される。ＰＲＥＴ命令がフェッチされ、コントローラ４１５は、呼び出しトークン（ＣＡＬ）を実行スタック４５５にプッシュする。欄８０５に示すように、ＴＯＳ（スタックの最上部）は、０ｘｆｆのマスク（現在アクティブなマスク）と、ＡＦＴＥＲ＿ＦＵＮＣＴＩＯＮの第１命令のアドレス（１０）に対応する０ｘａのプログラムカウンタ（ＰＲＥＴ命令により指定される）とを含むプッシュされた呼び出しトークンを記憶する。
【０１１５】
[00125]間接的分岐命令ＢＲＸがフェッチされ、コントローラ４１５は、アドレスレジスタ４４５のＡ２エントリーに記憶された定数インデックスをＢＲＸ命令に挿入する。この実施例では、０ｘｆ３が、インデックスｉ０（ＭＹＳＵＢ１）を参照するスレッドに対するテークンマスクであり、且つ０ｘ０ｃが、インデックスｉ２（ＭＹＳＵＢ２）を参照するスレッドに対するテークンマスクであると仮定する。コントローラ４１５は、各独特の関数ポインタに対してＢＲＸ命令の実行を直列化する。ＢＲＸ命令は、発散トークン（ＤＩＶ）を実行スタック４５５へプッシュする。欄８１５は、プログラム命令が実行された後に実行スタック４５５の最上部より１エントリー下にあるトークンＴＯＳ−１（スタックの最上部・マイナス・１）を示す。発散トークンに含まれたマスクは、０ｘ０ｃの値を有し、これは、ノット・テークンマスクであり、ＭＹＳＵＢ１へ間接的に分岐しなかった６つのスレッドを指示する。発散トークンに含まれるプログラムカウンタは、９の値を有し、これは、ＢＲＸ命令のアドレスである。現在アクティブなマスクは０ｘｆ３へ更新され、又、アクティブなプログラムカウンタは、関数ＭＹＳＵＢ２のターゲットアドレス０にセットされる。
【０１１６】
[00126]ＭＹＳＵＢ２の第１関数であるＡＤＤがフェッチされて、アクティブなスレッドに対して処理エンジン３０２により実行され、レジスタＲ１に記憶された値を更新する。アクティブなプログラムカウンタが１に増加され、次の命令であるＲＥＴがフェッチされる。コントローラ４１５は、実行スタック４５５の最上部から発散トークンをポップし、アクティブなマスクを０ｘ０ｃにセットすると共に、アクティブなプログラムカウンタを９にセットする。次いで、コントローラ４１５は、ＢＲＸ命令をフェッチする。アクティブなスレッドは、全て、同じ関数ポインタ（インデックスｉ２）を指定するので、発散はなく、プッシュされるトークンもない。アクティブなプログラムカウンタは、インデックスｉ２に対応する関数ポインタ、即ちＭＹＳＵＢ１の第１命令、にセットされる。
【０１１７】
[00127]ＭＹＳＵＢ１の第１命令であるＡＤＤがフェッチされて、アクティブなスレッドに対して処理エンジン３０２により実行され、レジスタＲ１に記憶された値を更新する。アクティブなプログラムカウンタが３に増加され、リターン命令ＲＥＴがフェッチされる。コントローラ４１５は、実行スタック４５５の最上部から呼び出しトークンをポップし、アクティブなマスクを０ｘｆｆにセットすると共に、アクティブなプログラムカウンタを１０にセットする。次いで、コントローラ４１５は、ＡＦＴＥＲ＿ＦＵＮＣＴＩＯＮの第１命令をフェッチする。当業者であれば、テーブル６に示すコードは、アクティブなスレッドのサブセットがＢＲＸ命令の実行により間接的な関数呼び出しを遂行するように条件分岐内に含まれることが明らかであろう。
【０１１８】
[00128]ここに開示するシステム及び方法の１つの効果は、マルチスレッド型アーキテクチャーのスレッドを多数のスレッドグループに分断できることである。各スレッドグループ内で、個々のスレッドを互いに発散して、必要に応じてディセーブルし、条件付き分岐、間接的な関数呼び出し、ブレーク及びリターンを実行することができる。更に、各スレッドグループ内のスレッドは、処理効率のために必要に応じて同期することができる。その結果、可能なときに完全に並列な同期モードで動作すると共に、特定のスレッドグループ内でスレッドの発散が生じるときには分岐又はサブルーチンの実行やスレッドの実行が独立して行われるので最小限の性能低下しか受けないシステムが得られる。
【０１１９】
[00129]本発明の一実施形態は、コンピュータシステムに使用するためのプログラム製品として実施することができる。プログラム製品のプログラム（１つ又は複数）は、（ここに述べる方法を含む）実施形態の機能を定義し、そして種々のコンピュータ読み取り可能な記憶媒体に含ませることができる。ここに例示するコンピュータ読み取り可能な記憶媒体は、（ｉ）情報が永久的に記憶される書き込み不能の記憶媒体（例えば、コンピュータ内のリードオンリメモリ装置、例えば、ＣＤ−ＲＯＭドライブにより読み取り可能なＣＤ−ＲＯＭディスク、フラッシュメモリ、ＲＯＭチップ、又は任意の形式のソリッドステート不揮発性半導体メモリ）、及び（ii）変更可能な情報が記憶される書き込み可能な記憶媒体（例えば、ディスケットドライブ又はハードディスクドライブ内のフロッピーディスク、又は任意の形式のソリッドステートランダムアクセス半導体メモリ）を含むが、これらに限定されない。
【０１２０】
[00130]本発明は、特定の実施形態を参照して以上に説明した。しかしながら、当業者であれば、特許請求の範囲に述べる本発明の広い精神及び範囲から逸脱せずに種々の変更や修正がなされ得ることが理解されよう。従って、以上の説明及び添付図面は、例示のためのものであって、それに限定されるものではない。
【符号の説明】
【０１２１】
１００・・・システム、１０２・・・ＣＰＵ、１０４・・・システムメモリ、１０５・・・メモリブリッジ、１０６・・・通信経路、１０７・・・Ｉ／Ｏブリッジ、１０８・・・入力装置、１１０・・・ディスプレイ装置、１１２・・・並列処理サブシステム、１１３・・・通信経路、１１４・・・システムディスク、１１６・・・スイッチ、１１８・・・ネットワークアダプタ、１２０・・・アドインカード、１２１・・・アドインカード、２０２・・・ＰＰＵ、２０４・・・ＰＰメモリ、２０６・・・ホストインターフェイス、２０８・・・コア、２１０・・・ワーク配布ユニット、２１２・・・フロントエンド、２１４・・・メモリインターフェイス、３０２・・・処理エンジン、３０３・・・コアインターフェイス、３０４・・・ローカルレジスタファイル、３０６・・・共有メモリ、３０８・・・パラメータメモリ、３１２・・・命令ユニット、３２０・・・グローバルメモリ、４００・・・命令フェッチユニット、４０５・・・プログラムカウンタ記憶装置、４１０・・・定数キャッシュ、４１５・・・コントローラ、４２０・・・スレッド状態記憶装置、４２５・・・ＣＲＳスタック、４３０・・・命令キャッシュ、４３５・・・ディスパッチャー、４４０・・・制御情報、４４５・・・アドレスレジスタ、４５０・・・条件コードユニット、４５５・・・実行スタック、４７０・・・プログラムコード、４７２・・・定数インデックス、４７４・・・ロックビット、４７６・・・ポインタ、４７８・・・プログラムコード
【図１】
0005701487.tif 000009
【図２】
0005701487.tif 000010
【図３】
0005701487.tif 000011
【図４Ａ】
0005701487.tif 000012
【図４Ｂ】
0005701487.tif 000013
【図４Ｃ】
0005701487.tif 000014
【図５Ａ】
0005701487.tif 000015
【図５Ｂ】
0005701487.tif 000016
【図６】
0005701487.tif 000017
【図７】
0005701487.tif 000018
【図８】
0005701487.tif 000019