(57)【要約】【課題】スキャン演算を効率的に遂行するシステム、方法、及びコンピュータ・プログラムプロダクトを提供する。【解決手段】使用中に、並列処理装置アーキテクチャを利用することによって、要素の配列がトラバースされる。そのような並列処理装置アーキテクチャは複数のプロセッサを含み、各プロセッサは物理的に所定数のスレッドを並列に実行することができる。効率を目的として、少なくとも１つのプロセッサの所定数のスレッドは、該所定数のスレッドの関数である数（例えば、倍数）の要素を伴うスキャン演算を遂行するように実行されることができる。【選択図】  図２
2009116854.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ所定数のスレッドを並行して物理的に実行することのできる複数のプロセッサを含む並列処理装置アーキテクチャを利用することによって、要素の配列をトラバースするステップと、
少なくとも１つの前記プロセッサの前記所定数のスレッドを実行して、前記所定数のスレッドの関数である数の要素を伴うスキャン演算を遂行するステップと、
を備える方法。
【請求項２】
前記スレッドの各々が、異なるデータ上で単一の命令を実行する、請求項１に記載の方法。
【請求項３】
前記並列処理装置アーキテクチャがグラフィックス・プロセッサを含む、請求項１に記載の方法。
【請求項４】
前記スキャン演算が全プレフィックス合計演算を含む、請求項１に記載の方法。
【請求項５】
前記要素の配列が単一方向にトラバースされる、請求項１に記載の方法。
【請求項６】
ＸＯＲ演算を利用して前記要素の配列がトラバースされる、請求項１に記載の方法。
【請求項７】
前記関数が倍数を含む、請求項１に記載の方法。
【請求項８】
前記倍数が１である、請求項７に記載の方法。
【請求項９】
前記倍数が少なくとも２である、請求項７に記載の方法。
【請求項１０】
前記配列の複数の部分の各々が前記所定数に等しい数の前記要素を含み、前記スキャン演算が前記配列の複数の部分上で遂行される、請求項９に記載の方法。
【請求項１１】
前記配列の複数の部分が重複しない、請求項１０に記載の方法。
【請求項１２】
前記複数の部分のうちの第１の部分について前記スキャン演算を遂行している前記スレッドと、前記複数の部分のうちの第２の部分について前記スキャン演算を遂行している前記スレッドとの間で、同期が遂行される、請求項１０に記載の方法。
【請求項１３】
前記配列の前記複数の部分について遂行された前記スキャン演算の結果が記憶される、請求項１０に記載の方法。
【請求項１４】
前記配列の前記複数の部分について遂行された前記スキャン演算の前記結果が使用されて、前記スキャン演算が完了する、請求項１３に記載の方法。
【請求項１５】
コンピュータ読み取り可能媒体に統合されたコンピュータ・プログラムプロダクトであって、
それぞれ所定数のスレッドを並行して物理的に実行することのできる複数のプロセッサを含む並列処理装置アーキテクチャを利用することによって、要素の配列をトラバースするコンピュータ・コードと、
少なくとも１つの前記プロセッサの前記所定数のスレッドを実行して、前記所定数のスレッドの関数である数の前記要素を伴うスキャン演算を遂行するコンピュータ・コードと、
を備えるコンピュータ・プログラムプロダクト。
【請求項１６】
前記コンピュータ・コードは、グラフィックス・プロセッサを利用して汎用計算能力を提供することのできるドライバのコンポーネントである、請求項１５に記載のコンピュータ・プログラムプロダクト。
【請求項１７】
前記要素の配列を単一方向にトラバースするコンピュータ・コードをさらに備える、請求項１５に記載のコンピュータ・プログラムプロダクト。
【請求項１８】
ＸＯＲ演算を利用して前記要素の配列をトラバースするコンピュータ・コードをさらに備える、請求項１５に記載のコンピュータ・プログラムプロダクト。
【請求項１９】
それぞれ所定数のスレッドを並行して物理的に実行することのできる複数のプロセッサを含む並列処理装置アーキテクチャと、
前記並列処理装置アーキテクチャと通信して、少なくとも１つの前記プロセッサの前記所定数のスレッドを実行し、前記所定数のスレッドの関数である数の配列要素を伴うスキャン演算を遂行するドライバと、
を備えるシステム。
【請求項２０】
前記並列処理装置アーキテクチャはバスを経由してメモリへ結合される、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本発明は並列処理装置アーキテクチャに関し、更に具体的には、並列処理装置アーキテクチャを使用して計算アルゴリズムを実行することに関する。
【背景技術】
【０００２】
[0002]並列処理装置アーキテクチャは、異なる計算アルゴリズムの広い配列を遂行するために、普通に使用される。そのようなアーキテクチャを使用して普通に遂行されるアルゴリズムの例は、スキャン演算である（例えば、「全プレフィックス合計（ａｌｌ−ｐｒｅｆｉｘ−ｓｕｍｓ）」演算）。そのような１つのスキャン演算は表１で規定される。
【表１】
2009116854.tif 000003
[0003]具体的には、配列［ａ０，ａ１，…，ａｎ−１］が与えられ、「Ｉ」が演算子に対する単位元であるとすれば、表１の配列が返される。例えば、もし演算子
2009116854.tif 000004
が加法演算子であるならば、配列［３  １  ７  ０  ４  １  ６  ３］へのスキャン演算は、［０  ３  ４  １１  １１  １５  １６  ２２］などを返す。上記の例では、加法演算子が記述されたが、そのような演算子は、２つのオペランド上で演算する任意の２進結合演算子(binary associativeoperator)である。
【０００３】
[0004]多数の要素を有する配列上で、そのようなスキャン演算を効率的に遂行するためには、要素は「木」のようにトラバースされる。例えば、要素は「葉」と見なされ、「葉」は第１のレベルで処理されて第１の要素の合計を含む第２のレベルの要素が生成され、一時的に記憶される。その後で、第２のレベルの要素が同じように処理され、このような処理が根に到達するまで続く。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
[0005]並列処理装置アーキテクチャを使用して、そのような処理に対応するためには、各々の配列要素がプロセッサの特定のスレッドへ割り当てられる。典型的には、限定された数のプロセッサが存在し、各プロセッサは限定された数のスレッドを有する（スレッドの数は、しばしば、配列要素の数よりもずっと少ない）。更に、スレッドは1つのレベルから次のレベルまでデータを共有するから、先行する処理レベルは、次のレベルへ移動する前に完全に終了されなければならない。
【０００５】
[0006]これは、他方では、各処理レベルでの同期を必要とする。言い換えれば、スキャン演算は、特定のレベルにおいて、次のレベルへ移動する前に、割り当てられるべきスレッドを待機し、各配列要素の処理を完了しなければならない。例えば、クロック・サイクル当たり１つの要素上で演算することのできる３２個のスレッドによって演算されている１０２４個の要素が与えられるとすれば、上記のアルゴリズムは次の処理レベルへ移動する前に３２のクロック・サイクルを待機しなければならない。使用に当たって、先行する同期は、潜在的に待機スレッド及び追加の待ち時間を生じる。
【発明を実施するための最良の形態】
【０００６】
[0012]図１は、本発明の１つの実施形態に従って、並列処理装置アーキテクチャ１０１を利用してスキャン演算を効率的に遂行するシステム１００を示す。本説明の文脈において、並列処理装置アーキテクチャは、並列に演算する２つ以上のプロセッサ１０２Ａ〜Ｎを含む任意のアーキテクチャを含んでもよい。１つの実施形態において、そのような並列処理装置アーキテクチャは、グラフィックス・プロセッサ（例えば、グラフィックス処理装置（ＧＰＵ））、又はグラフィックス処理能力を装備した中央処理装置（ＣＰＵ）又はチップセットの形態をとってもよい。しかしながら、もちろん、並列処理装置アーキテクチャが他の形態をとる他の実施形態も考慮されてもよい（例えば、汎用コンピューティング・プロセッサ）。
【０００７】
[0013]更に示されるように、並列処理装置アーキテクチャの複数プロセッサの各々は、所定数のスレッド１０４を並行して物理的に実行することができる。１つの実施形態において、スレッドのそのような物理的実行とは、論理的実行（例えば、タイムスライシング手法を使用すること）ではなく、多数のスレッドが物理的に同時に実行されることを意味する。
【０００８】
[0014]オプションとして、各プロセッサのスレッドは、単一命令・複数データ（ＳＩＭＤ）のやり方で演算してもよい。言い換えれば、プロセッサの全スレッドは、同じ命令を同時に実行するが、異なるデータ上で実行する。１つの実施形態において、そのようなやり方で演算しているスレッドの集合は、「ワープ」（ｗａｒｐ）と呼ばれる。更に、スレッドの所定数は、対応するプロセッサの「ワープ・サイズ」と呼ばれる。
【０００９】
[0015]使用に当たって、要素の配列は並列処理装置アーキテクチャを利用することによってトラバースされる。本説明の文脈において、要素のそのような配列は、スキャン演算へ供されることのできる任意の値の集合を含む。例えば、１つの実施形態において、値の配列は、一般的に式［Ａ，Ｂ，Ｃ，．．．，Ｎ］によって表される。ここで、示される値は数値である。もちろん、そのような要素配列は例証を目的としてのみ記述され、どのような意味においても限定と解釈されるべきではない。
【００１０】
[0016]配列要素のトラバース中に、スキャン演算が遂行される。本説明の文脈において、スキャン演算とは、配列の現在の要素及び少なくとも１つの前の要素（もしあれば）を伴う任意の演算を意味する。１つの実施形態において、スキャン演算は全プレフィックス合計演算を含んでもよい。例示的な全プレフィックス合計演算に関する更なる情報は、図２で図解される異なった実施形態の説明中に記述される。もちろん、上記の定義を満足する限り、他のスキャン演算（例えば、より多いか少ない要素及び他の演算子を伴う演算）が考慮される。
【００１１】
[0017]効率を目的として、少なくとも１つのプロセッサの所定数のスレッドは、所定数のスレッド（例えば、前記の「ワープ・サイズ」）の関数である数の要素を伴うスキャン演算を遂行するために実行されてもよい。例えば、１つの実施形態において、所定数のスレッドが実行されて、所定数の倍数である数の要素を伴うスキャン演算が遂行されてもよい。本説明の文脈において、スレッドの所定数の前述した倍数は、任意の整数（例えば、１，２，３，４，５，．．．Ｎ）を含む。図１で示される実施形態において、スキャン演算は、スレッドの所定数に等しい数の要素を伴ってもよい（すなわち倍数は１に等しい）。
【００１２】
[0018]いずれにせよ、特定のプロセッサの各スレッドは、関連するスキャン演算を遂行するための要素を割り当てられる。このため、スレッド間の同期に関連づけられた処理は、全面的に回避されるとまではいかなくても低減される。言い換えれば、上記の設計の結果として、各スレッドはスキャン演算を遂行するため正確に１つの要素を割り当てられ、特定のプロセッサの全スレッドが同時に終了するようにされる。オプションとして、更なる効率を提供するために、要素の配列はＸＯＲ演算などを利用してトラバースされてもよい。
【００１３】
[0019]ユーザの所望に従って、前述したフレームワークが実現されても実現されなくてもよい様々な任意的アーキテクチャ及び特徴に関して、更に例証的な情報が今から記述される。具体的には、スキャン演算とともに、ＸＯＲ演算を使用して要素配列をトラバースする少なくとも１つの追加の実施形態が記述される。強く注意されることは、下記の情報が例証のみを目的として記述され、いかなる意味でも限定と解釈されてはならないことである。下記の特徴のいずれも、説明される他の特徴を排除し、または排除しないで任意的に組み込まれてもよい。
【００１４】
[0020]図２は、本発明の他の実施形態に従って、配列Ｐ上でＸＯＲスキャン演算を遂行する方法２００を示す。オプションとして、この方法は図１の機能及びアーキテクチャの環境で実現されてもよい。例えば、この方法は、例えば図１で示される並列処理装置アーキテクチャの特定のプロセッサのスレッドによって、複数の配列要素にわたって並列に実施されてもよい。しかしながら、もちろん、この方法は任意の所望の環境（例えば、図１の設計規準を有しない）で実施されてもよい。更に注意されるべきことは、前述した定義は本説明に適用されてもよいことである。
【００１５】
[0021]図示されるように、方法は、変数Ｄを「１」へ設定して変数Ｄを初期化することによって始まる。演算２０２を参照されたい。もちろん、そのような初期化は任意であり、もし初期化が存在すれば、任意の所望のやり方で遂行されてもよい。次に、方法は、変数Ｄがワープ・サイズへ到達するまで、ｗｈｉｌｅループ２０３の中で継続する。決定２０４を参照されたい。
【００１６】
[0022]再び、ワープ・サイズとは、並列処理装置アーキテクチャの特定のプロセッサで並行して物理的に実行されるスレッドの所定数を意味する。更に、ｗｈｉｌｅループの中で同期は必ずしも要求されない。具体的には、配列要素の数をワープ・サイズ以下に限定することによって、スレッド間の同期は必ずしも要求されない。前述したように、そのような同期は、スキャン演算が、割り当てられるべきスレッドを待機し、特定のレベルにおいて、次のレベルへ移動する前に、各配列要素の処理を完了しなければならない事態を伴う。このため、ここでのロック・ステップ設計は、潜在的に、後続のスレッドが読み出し又は書き込み等を必要とするメモリ共有部分への書き込みを、第１のスレッドが終了しないという事態を回避する。
【００１７】
[0023]まもなく明らかになるように、ｗｈｉｌｅループ２０３の各々の繰り返しについて、変数Ｄは２の因子だけ増加する。そのように変数Ｄを２の因子によって増分することによって、配列は２分木として処理される。そのような状況において、変数Ｄはそのような木のレベルに相関する。
【００１８】
[0024]使用中、変数Ｄがワープ・サイズよりも小さい間、演算２０６〜２０８で示されるように、条件付き分岐が進行する。具体的には、最初に、変数Ｄ及びスレッド・ローカル変数ｉｄｘを伴うビット単位ＡＮＤ演算(bitwise AND operation)によって、その結果が「０」よりも大きいかどうかを決定する。決定２０６を参照されたい。そのようなスレッド・ローカル変数ｉｄｘは、複数の活動スレッドの中で、特定のスレッドのグローバル索引を意味する。１つの実施形態において、ｉｄｘは、使用中にスレッドへ割り当てられるローカル変数を含んでもよい。そのようなスレッド・ローカル変数は、ハードウェアによって割り当てられ、更に、レジスタの中で追跡／記憶される。
【００１９】
[0025]表２は、Ｄ及びｉｄｘの異なる値に対する決定２０６の結果を例証する。
【表２】
2009116854.tif 000005
[0026]決定２０６において、もしビット単位ＡＮＤ演算が「０」よりも大きいならば、配列Ｐの特定の要素が更新される。具体的には、上記の表２で記述されるように、奇数の要素のみが、対応するスレッドによって木の最低レベルで更新される。以下同様である。
【００２０】
[0027]ビット単位ＡＮＤ演算が決定２０６で「０」よりも大きくなると、配列Ｐの特定の要素Ｐ［ｉｄｘ］は、下記の式１に基づいて更新される。
【００２１】
2009116854.tif 000006
そのような配列要素Ｐ［ｉｄｘ］の値は、変数ｉｄｘ及び（Ｄ−１）の値を伴うビット単位ＯＲ演算(bitwise OR operation)と、その結果及び変数Ｄの値のビット単位ＸＯＲ演算(bitwise XOR operation)との、関数であると示される。
【００２２】
[0028]表３は、ｉｄｘ及びＤの様々な値について、Ｐ［ｉｄｘ］として合計される様々な要素の概要を例証する。
【表３】
2009116854.tif 000007
演算の他の例は、図３で示される８要素配列を伴う異なる実施形態の文脈において記述される。
【００２３】
[0029]演算２０８の後で、変数Ｄは２倍にされる。演算２１０を参照されたい。その後で、変数Ｄがワープ・サイズよりも小さくなくなるまで、ｗｈｉｌｅループの中で演算が継続する。再び、決定２０４を参照されたい。１つの実施形態において、ｗｈｉｌｅループの終わりは、この方法の終了を生じる。そのような実施形態において、結果は包含的ＸＯＲスキャンの形態をとる。
【００２４】
[0030]他の実施形態において、下記で記述されるように、方法は任意的に式２が実施される演算２１２へ進行することもできる。
【００２５】
2009116854.tif 000008
式「ｏｖａｌ＝Ｐ［ｉｄｘ］」は、ループが始まる前に演算２０２で実行されることに注意すべきである。そうでなければ、Ｐ［ｉｄｘ］はループ内で計算された新しい値を有し、正しくない結果（例えば、オール・ゼロ）を生じる。
【００２６】
[0031]使用中、式２の計算は、包含的ＸＯＲの結果を排他的ＸＯＲの結果へ変換する役目をすることができる。排他的スキャンは、結果の各要素ｊが、入力配列の中の要素ｊまでの全ての要素（ただし、要素ｊを含まない）の合計であるスキャンを意味してもよい。他方、包含的スキャンでは、要素ｊを含む全ての要素が合計される。演算２１２で記述されるように、結果の配列を右へ１つの要素だけシフトし、単位元を挿入することによって、排他的スキャンは包含的スキャンから生成可能である。排他的スキャンは、結果の各要素ｊが、入力配列の中のｊまでの全ての要素（ただし、ｊを含まない）の合計であるスキャンを意味することに注意すべきである。他方、包含的スキャンは、ｊを含む全ての要素が合計されるスキャンである。
【００２７】
[0032]使用中、前述した方法は、複数のスレッドで並列に実行されてもよく、各ワープの中の全スレッドは、ワープ・サイズに等しい数の要素のスキャンを計算する。方法は、ビット単位ＸＯＲ演算を使用し、木のように配列をトラバースすることによって、スキャン演算の結果を構築する。木の各レベルＤにおいて、方法は、スレッドによって読み出されたアドレスを計算するために、各スレッドインデックスの下位Ｄビットを有する２ＤのＸＯＲを計算する。実際には、所与の機械についてワープ・サイズが固定されているので、上記の方法のｗｈｉｌｅループが展開される。
【００２８】
[0033]前述した方法を実現するために使用される例示的な疑似コードは、表４で記述される。もちろん、そのような疑似コードは、例証のみを目的として記述され、いかなる意味でも限定と解釈されてはならない。
【表４】
2009116854.tif 000009
[0034]１つの実施形態において、この方法は、任意の所望のプログラミング・フレームワークを利用して実現される。１つの実施形態において、そのような手法は、グラフィックス・プロセッサを利用して汎用計算能力を提供するドライバを使用して実現されてもよい。そのようなドライバの例は、ＮＶＩＤＩＡ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＣＵＤＡ（商標）フレームワークと関連して提供される。表５は、そのような実現をサポートする例示的なコードを例証する。再び、強く注意されることは、そのような実現が例証のみを目的として記述され、いかなる意味でも限定と解釈されてはならないことである。
【表５】
2009116854.tif 000010
[0035]図３は、本発明の他の実施形態に従った例示的なＸＯＲスキャン演算３００を示す。オプションとして、このスキャンは、図２の方法の例示的な演算を表すことができる。例えば、８つの要素を伴う要素配列３０２の複数のパスが例証される。
【００２９】
[0036]具体的には、第１のパス３０４は、要素１，３，５，７などの更新を伴うように示される。そのような要素の選択は、図２の決定２０６によって指図される。例えば、Ｄ＝１であるときの上記の表２を参照されたい。更に、そのような置換の値は、複数のＸＯＲ演算３０５を使用して作られ、図２の演算２０８に従って計算される。例えば、式１に注意されたい。
【００３０】
[0037]演算は、更に、図示されるように第２のパス３０６及び第３のパス３０８へ継続する。更に例証されるように、第３のパスの最終要素３１０は、要素配列の全要素の合計を含む。
【００３１】
[0038]図３で例証されるように、ＸＯＲ演算は、効率を目的として、単一方向への（例えば、下方への）配列のトラバースを提供する。本説明の文脈において、そのような単一方向トラバースは、追加の処理を要求する反対方向のトラバースを回避するトラバースを意味する。図３の実施形態の特定の状況において、そのような反対方向のトラバースは、配列の上方掃引を伴う。もちろん、幾つかの実施形態において、複数方向のトラバースの使用が考慮される。
【００３２】
[0039]ＸＯＲ演算の使用は、例証のみを目的として記述されることに注意すべきである。表３で記述される機能と類似した機能を提供する他の演算子（例えば、マイナス演算子）を使用する他の実施形態も考慮される。幾つかの実施形態において、任意の適切なトラバーススキームが使用されてもよい。
【００３３】
[0040]図４は、本発明の更に他の実施形態に従って、より大きい要素配列上でスキャン演算を遂行するフレームワーク４００を示す。オプションとして、このフレームワークは、図１〜図３の機能及び特徴を使用して実現することができる。しかしながら、もちろん、このフレームワークは、任意の所望の環境で実現されてもよい。再び、前述した定義は、本説明に適用される。
【００３４】
[0041]現在の実施形態において、これまでの図で説明されたやり方で処理するには大きすぎる要素配列４０２が提供されてもよい。具体的には、配列の要素の数に対処するのに十分なスレッドが、特定のプロセッサに存在しないかも知れない。そのような場合、値の配列は複数のブロック４０４へ分割されてもよい。そのようなブロックのサイズは、例えば、特定のプロセッサによって並行して物理的に実行されるスレッドの数に等しい要素の数（例えば、ワープなど）を含んでもよい。
【００３５】
[0042]このため、各ブロックは、ワープへ割り当てられてもよい。この設計によって、ワープの各スレッドは、対応するブロックの特定の要素を割り振られる。更に、複数のプロセッサの各々は、関連するブロックの要素を処理してスキャン演算を遂行する。例えば、図２を参照されたい。
【００３６】
[0043]次に、各ブロックのスキャン結果は、スキャン演算の完了における使用のために、補助配列４０６の中に記憶されてもよい。具体的には、各ブロックの最後の要素は、そのような補助配列の中に記憶されてもよい。更に、そのような補助配列の要素は、一方では、スキャン結果４０８の追加の配列を生成するためにスキャンされてもよい。それから、そのようなスキャン結果が、元のスキャンされたブロック４０４へ加えられてもよい。具体的には、項目４０６／４０８が包含的スキャンを表す場合、図示されるように、スキャン結果ｉが元のスキャンされたブロックｉ＋１の各要素へ加えられてもよい。このため、スキャンされた要素の最終配列が提供される。図示されていないが、項目４０６／４０８が排他的スキャンを表す場合、スキャン結果ｉは元のスキャンされたブロックｉの各要素へ加えられてもよい。もちろん、本実施例は加法演算子を伴うが、そのような演算子は、様々な実施形態において、疑いなく非限定的に、乗法、最大、最小、ビット単位ＡＮＤ／ＯＲなどを含んでもよい。
【００３７】
[0044]こうして、単一ワープＸＯＲスキャン演算は、より大きい配列へ拡張される。要約すると、大きな配列Ａのプレフィックス合計は、副配列Ａｉのスキャンの結果の最後の要素を副配列Ａｊのスキャンの結果の全要素へ加えることによって、多くの非重複配列部分（例えば、Ａの副配列のプレフィックス合計）から計算可能である。こうして、そのような特性は、Ｂ個のスレッドでＢ個の要素をスキャンできるアルゴリズムを設計するために役立てられる。ここで、Ｂはワープ・サイズの倍数である。
【００３８】
[0045]１つの具体的な使用例において、各スレッドｉはデバイス・メモリから１つの要素をロードし、この要素を共有メモリ内の配列Ｐの場所ｉの中に記憶する。次に、上記のアルゴリズムが、全スレッドによって配列Ｐ上で実行されてもよい。これは、（ワープ・サイズ）個の要素からなる（Ｂ／ワープ・サイズ）個の副配列を今や含むＰを生じる。ここで要素の各々は、入力の対応する要素のプレフィックス合計を含む。次に、これらの各副配列スキャンの最後の要素は、対応するワープｗの１つのスレッドによって、他の共有配列Ｑ（（Ｂ／ワープ・サイズ）個の要素のみを有する）の要素ｗへ複写される。次に、この配列がスキャンされる。最後に、ワープｗ（＝ｆｌｏｏｒ（ｉ／ｗａｒｐ＿ｓｉｚｅ））からの各スレッドｉが、配列Ｑの要素ｗを配列Ｐの要素ｉへ加える。こうして、配列Ｐは入力配列の完全なプレフィックススキャンを含む。
【００３９】
[0046]再び、ブロック・サイズは、ワープ・サイズ（即ち、特定のプロセッサによって並行して物理的に実行されるスレッドの数）と等しい要素数を含むように設定されるので、同期は必ずしもブロックのスキャンの中で要求されない。しかしながら、そのような設計の見地から同期は低減されてもよいが、様々な点で幾つかの同期が利用されてもよい。例えば、配列の異なる部分（例えば、ブロックなど）上でスキャン演算を遂行するスレッドの間で、同期が遂行されてもよい。
【００４０】
[0047]表６は、図４のフレームワークを実現するために使用されてもよい例示的な疑似コードを記述する。示されるように、様々な障壁点で同期が提供される。もちろん、このような疑似コードは、例証のみを目的として記述され、いかなる意味でも限定と解釈されてはならない。
【表６】
2009116854.tif 000011
注意すべきは、１つの実施形態において、前記「warpscan」関数が、ただ１つのワープではなく多くのワープによって、表６の疑似コード内で同時に実行されることである。
【００４１】
[0048]上記の疑似コードにおいて、用語「BARRIER」は、いずれかのスレッドが先へ進む前に全てのスレッドが到達しなければならない障壁同期点を意味する。様々な実施形態において、これは読み出し後の書き込み（ＷＡＲ）及び書き込み後の読み出し（ＲＡＷ）データハザードを回避するために使用されることができる。
【００４２】
[0049]前述した実施形態と同じく、この手法は、所望のプログラミング・フレームワークを利用して実現される。１つの可能な実施形態において、前述した機能は、前述したＣＵＤＡ（商標）フレームワークに関連したドライバによって提供される。表７は、そのような実現をサポートする例示的なコードを例証する。
【表７】
2009116854.tif 000012
[0050]前述したスキャン演算は、並列で行われるソート（例えば、基数ソート）、字句解析、文字列比較、多項式評価、ストリーム圧縮、ヒストグラム及びデータ構造（例えば、グラフ、木、範囲総和テーブル）の構築を非限定的に含む様々なアプリケーションで使用されることに注意されたい。もちろん、このようなアプリケーションは例として記述される。なぜなら、他のアプリケーションが考慮されるからである。
【００４３】
[0051]図５は、前述した様々な実施形態の様々なアーキテクチャ及び／又は機能が実現される例示的なシステム５００を図解する。図示されるように、通信バス５０２へ接続された少なくとも１つのホスト・プロセッサ５０１を含むシステムが提供される。システムは、更に、メイン・メモリ５０４を含む。制御論理（ソフトウェア）及びデータは、ランダム・アクセス・メモリ（ＲＡＭ）の形態を取るメイン・メモリの中に記憶される。
【００４４】
[0052]システムは、更に、グラフィックス・プロセッサ５０６及びディスプレイ５０８、即ち、コンピュータ・モニタを含む。１つの実施形態において、グラフィックス・プロセッサは、複数のシェーダ・モジュール、ラスタライズ・モジュールなどを含む。これらモジュールの各々は、単一の半導体プラットフォーム上に配置され、グラフィックス処理装置（ＧＰＵ）を形成してもよい。
【００４５】
[0053]本説明において、単一の半導体プラットフォームとは、単一の単体半導体ベース・集積回路又はチップを意味する。注意すべきことは、「単一の半導体プラットフォーム」の用語は、オンチップ演算をシミュレートして、増大された接続性を有し、従来の中央処理装置（ＣＰＵ）及びバスの実装を利用より実質的な改善を生じせしめるマルチチップ・モジュールを意味してもよい。もちろん、ユーザの所望に従って、様々なモジュールが別々に配置されるか、半導体プラットフォームの様々な組み合わせの中に配置されてもよい。
【００４６】
[0054]システムは、更に、２次記憶装置５１０を含む。２次記憶装置は、例えば、ハードディスク・ドライブ及び／又は取り外し可能な記憶ドライブを含む。取り外し可能な記憶ドライブは、フロッピーディスク・ドライブ、磁気テープ・ドライブ、コンパクト・ディスク・ドライブなどである。取り外し可能な記憶ドライブは、周知のやり方で、取り外し可能な記憶装置からの読み出し及び／又は書き込みを行う。
【００４７】
[0055]コンピュータ・プログラム、又はコンピュータ制御論理アルゴリズムは、メイン・メモリ及び／又は２次記憶装置の中に記憶される。そのようなコンピュータ・プログラムは、実行されるとき、様々な機能をシステムに遂行させる。メモリ、記憶装置、及び／又は他の記憶装置は、コンピュータ読み取り可能媒体の可能な例である。
【００４８】
[0056]１つの実施形態において、説明した様々な図面のアーキテクチャ及び／又は機能は、ホスト・プロセッサ、グラフィックス・プロセッサ、ホスト・プロセッサ及びグラフィックス・プロセッサの双方の能力の少なくとも一部分を有する集積回路（不図示）、チップセット（即ち、関連した機能を遂行する装置として作動するように設計され販売される集積回路群など）、及び／又は類似の他の集積回路のもとで実現される。更に、説明した様々な図面のそのようなスキャン関連機能は、１つの可能な実施形態において、ドライバ５１２の制御のもとで、前述した任意の集積回路の中で実現されてもよい。
【００４９】
[0057]更にまた、前述した様々な図面のアーキテクチャ及び／又は機能は、汎用コンピュータ・システム、回路基板システム、娯楽目的専用のゲーム・コンソール・システム、アプリケーション特有のシステム、及び／又は他の所望のシステムのもとで実現される。例えば、システムは、デスクトップ・コンピュータ、ラップトップ・コンピュータ、及び／又は他の型の論理の形態を取ってもよい。更にまた、システムは様々な他のデバイスの形態を取ってもよく、非限定的に、パーソナル・ディジタル・アシスタント（ＰＤＡ）デバイス、移動電話デバイス、テレビなどが含まれる。
【００５０】
[0058]更に、図示されてはいないが、システムは、通信を目的として、ネットワーク［例えば、電気通信ネットワーク、ローカルエリアネットワーク（ＬＡＮ）、無線ネットワーク、インターネットなどの広域ネットワーク（ＷＡＮ）、ピアツーピア・ネットワーク、ケーブル・ネットワーク）］へ結合されてもよい。
【００５１】
[0059]これまで様々な実施形態が説明されたが、それらは単なる例として呈示され、限定として呈示されるものではないことを理解すべきである。したがって、好ましい実施形態の広さ及び範囲は、前述した例示的実施形態によって限定されてはならず、特許請求の範囲及びそれらの等価物に従ってのみ規定されるべきである。
【図面の簡単な説明】
【００５２】
【図１】本発明の１つの実施形態に従って、並列処理装置アーキテクチャを利用してスキャン演算を効率的に遂行するシステムを示す。
【図２】本発明の他の実施形態に従って、配列上でＸＯＲスキャン演算を遂行する方法を示す。
【図３】本発明の他の実施形態に従った例示的なＸＯＲスキャン演算を図解する。
【図４】本発明の更に他の実施形態に従って、より大きい配列要素上でスキャン演算を遂行するフレームワークを示す。
【図５】前述した様々な実施形態の様々なアーキテクチャ及び／又は機能が実現される例示的システムを図解する。
【符号の説明】
【００５３】
１００…システム、１０１…並列処理装置アーキテクチャ、１０２Ａ…プロセッサ、１０２Ｂ…プロセッサ、１０２Ｎ…プロセッサ、１０４…スレッド、１１０…スキャン、３００…ＸＯＲスキャン演算、３０２…要素の配列、３０４…第１のパス、３０５…ＸＯＲ演算、３０６…第２のパス、３０８…第３のパス、３１０…最終の要素、４００…フレームワーク、４０２…要素の配列、４０４…元のスキャンされたブロック、４０６…補助配列、４０８…スキャン結果の追加の配列、４１０…、５００…例示的なシステム、５０１…ホスト・プロセッサ、５０２…通信バス、５０４…メイン・メモリ、５０６…グラフィックス・プロセッサ、５０８…ディスプレイ、５１０…２次記憶装置、５１２…ドライバ
【図１】
2009116854.tif 000013
【図２】
2009116854.tif 000014
【図３】
2009116854.tif 000015
【図４】
2009116854.tif 000016
【図５】
2009116854.tif 000017
【外国語明細書】
2009116854000001.pdf