並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム、方法及びコンピュータプログラム製品
【課題】並行処理アーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム、方法及びコンピュータ製品を提供すること。
【解決手段】動作において、スキャン演算命令が受信される。さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して、単一ビット値のシーケンスに対して実施される。
【解決手段】動作において、スキャン演算命令が受信される。さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して、単一ビット値のシーケンスに対して実施される。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本発明は、スキャン演算に関し、より具体的には、並行処理アーキテクチャを使用してスキャン演算を実施することに関する。
【背景技術】
【０００２】
[0002]並列プロセッサアーキテクチャは一般に、幅広い様々な計算アルゴリズムを実施するために使用される。こうしたアーキテクチャを使用して一般に実施されるアルゴリズムの一例は、スキャン演算（例えば「ａｌｌ−ｐｒｅｆｉｘ−ｓｕｍｓ」演算など）である。こうした１つのスキャン演算が、表１に定義されている。
【表１】
【０００３】
[0003]具体的には、配列［ａ０，ａｌ，…，ａｎ−１］、及び「Ｉ」を単位元とする演算子
【数１】
与えられると、表１の配列が返される。例えば、演算子
【数２】
が加算演算子である場合、配列［３ １ ７ ０ ４ １ ６ ３］に対してスキャン演算を実施すると、［０ ３ ４ １１ １１ １５ １６ ２２］が返されるなどである。上記の例では加算演算子が示されているが、こうした演算子は、２つのオペランドの任意の連結演算子であってもよい。
【０００４】
[0004]さらに、スキャン演算は、（表１に示されたような）排他的スキャン演算であっても、包括的スキャン演算であってもよい。排他的スキャンは、結果の各要素ｊが、入力配列の要素ｊまで（要素ｊを含まず）のすべての要素の和となるスキャンを指す。もう一方では、包括的スキャンでは、要素ｊを含むすべての要素が合計される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]これまで、並列プロセッサアーキテクチャを使用したスキャン演算などの計算アルゴリズムをより効率的に実施することが引き続き求められている。
【課題を解決するための手段】
【０００６】
[0006]並行処理アーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム、方法及びコンピュータ製品が提供される。動作において、スキャン演算命令が受信される。さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して、単一ビット値のシーケンスに対して実施される。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するための方法を示す図である。
【図２】本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステムを示す図である。
【図３】本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステムの結果を示す図である。
【図４】本発明の一実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図５】本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図６】本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図７】上記の様々な実施形態の様々なアーキテクチャ及び／又は機能が実施され得る、例示的なシステムを示す図である。
【発明を実施するための形態】
【０００８】
[0014]図１は、本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビットに対するスキャン演算を実施するための方法１００を示している。示されるように、スキャン演算命令が受け取られる。操作１０２を参照されたい。この説明のコンテキストでは、スキャン演算命令は、スキャン演算に対応する任意の命令或いはコマンドを指す。
【０００９】
[0015]さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンス値に対して実施される。操作１０４を参照されたい。この説明のコンテキストでは、処理要素は、並列プロセッサアーキテクチャの任意の構成要素を指す。さらに、単一ビット値のシーケンスは、１ビット値の任意のシーケンスを含み得る。一部の実施形態では、この設計によって、単一ビット入力に対するスキャン演算などの計算アルゴリズムが、より効率的に実施され得る。
【００１０】
[0016]さらに、この説明のコンテキストでは、スキャン演算は、現在の要素と、配列の少なくとも１つの前の要素とが関与する任意の演算を指し得る。例えば、様々な実施形態では、スキャン演算は。接頭部和スキャン演算、排他的スキャン演算、包括的スキャン演算、及び／又は他の任意のスキャン演算（例えば、より多くの又は少ない要素、及び／又は他の演算子などが関与する）を含み得る。
【００１１】
[0017]さらに、この説明のコンテキストでは、並列プロセッサアーキテクチャは、並列に動作する２つ以上の処理要素を含む任意のアーキテクチャを含んでもよい。一実施形態では、こうした並列プロセッサアーキテクチャは、グラフィックスプロセッサ（例えばグラフィックス処理装置（ＧＰＵ：ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）など）、又は例えばチップセット、システムオンチップ（ＳＯＣ：ｓｙｓｔｅｍ−ｏｎ−ｃｈｉｐ）、ＣＰＵに組み込まれたコア、個別プロセッサなどの形のグラフィックス処理能力を備えた他の集積回路の形を取ってもよい。別の実施形態では、上記の並行処理アーキテクチャは、ベクタプロセッサを含んでもよい。
【００１２】
[0018]次に、ユーザの要望により上記フレームワークがそれと共に実装されることも、実装されないこともある様々な任意選択のアーキテクチャ及び特徴に関して、より例示的な情報が示される。以下の情報は、例示するために述べられており、どんなやり方でも限定的と見なすべきでないことに強く留意されたい。以下の特徴のいずれもが、述べられた他の特徴を除外して、又は除外せずに任意選択で組み込まれ得る。
【００１３】
[0019]図２は、本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム２００を示している。任意選択として、このシステムは、図１の方法を実施するために実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００１４】
[0020]示されるように、並行処理アーキテクチャ２０２が提供される。こうした並行処理アーキテクチャは、複数の並列プロセッサ２０４を含む。示されていないが、こうした並列プロセッサは、所定の数のスレッドに対して動作可能であり得る。このために、並列プロセッサはそれぞれ並列に動作し得るが、対応するスレッドもまた、並列に動作してもよい。
【００１５】
[0021]一実施形態では、並行処理アーキテクチャは、１つ又は複数の単一命令多重データ（ＳＩＭＤ：ｓｉｎｇｌｅ ｉｎｓｔｒｕｃｔｉｏｎ ｍｕｌｔｉｐｌｅ ｄａｔａ）処理要素を含んでもよい。こうしたシステムでは、プロセッサによって実行されているスレッドをグループにまとめて、単一グループ内のすべてのスレッドがどんな瞬間においても、潜在的にそれぞれ異なるデータに対してであるが、正確に同じ命令を実行しているようにする。一実施形態では、こうしたやり方で動作するこのスレッド群は、「ワープ」と呼ばれることもある。さらに、こうしたグループ内の所定のスレッド数は、対応するプロセッサの「ワープサイズ」と呼ばれることもある。
【００１６】
[0022]別の実施形態では、上記の並列処理アーキテクチャは、グラフィックスプロセッサ、或いは（例えばチップセット、システムオンチップ（ＳＯＣ）、ＣＰＵに組み込まれたコア、個別プロセッサなどの形の）グラフィックス処理能力を備えた他の任意の集積回路を含んでもよい。別の実施形態では、上記の並行処理アーキテクチャは、Ｓｏｎｙ（登録商標）社、Ｔｏｓｈｉｂａ（登録商標）社、及びＩＢＭ（登録商標）社によって合同で開発されたＣｅｌｌ広帯域エンジンマイクロプロセッサアーキテクチャを指すＣｅｌｌプロセッサなど、１つ又は複数のベクトル処理要素を備えたプロセッサを含んでもよい。
【００１７】
[0023]引き続き図２を参照すると、並行処理アーキテクチャは、ローカル共有メモリ２０６を含んでもよい。並行処理アーキテクチャの並列プロセッサはそれぞれ、それ自体のローカル共有メモリへの読出し及び／又は書込みを行い得る。この共有メモリは、各プロセッサに関連する物理的に別個のメモリで構成されてもよく、或いはそれは、プロセッサ間で共有された１つ又は複数のメモリの別個に割り当てられた領域で構成されてもよい。さらに、示された実施形態では、共有メモリは、並行処理アーキテクチャのプロセッサが具現化される集積回路内で具現化されてもよい。
【００１８】
[0024]さらに、図では、グローバルメモリ２０８が含まれている。使用時、こうしたグローバルメモリは、並行処理アーキテクチャのすべてのプロセッサからアクセス可能である。示されるように、こうしたグローバルメモリは、上記の並行処理アーキテクチャのプロセッサが具現化される集積回路とは別個の集積回路内で具体化されてもよい。並行処理アーキテクチャは、図２の様々な集積回路内に特定のやり方で具現化されるように示されているが、システム構成要素は、要望に応じて、同じ集積回路内で具体化されることも、具現化されないこともあることに留意されたい。
【００１９】
[0025]さらに、図２のこのシステムは、要望に応じて、並行処理アーキテクチャを制御するためのドライバ２１０をさらに含んでもよい。一実施形態では、ドライバは、こうした制御を容易にするためのライブラリを含んでもよい。例えば、こうしたライブラリは、本明細書に述べられた機能性をインスタンス化し得るライブラリ呼出しを含んでもよい。
【００２０】
[0026]さらに、別の実施形態では、ドライバは、並行処理アーキテクチャ（例えばグラフィックスプロセッサなど）を使用して一般的な計算能力を提供することができ得る。こうしたドライバの一例は、ＮＶＩＤＩＡコーポレーション社によって提供されたＣＵＤＡ（商標）フレームワークと併せて提供されてもよい。使用時、ドライバは、並列処理アーキテクチャを図１の方法に従って動作するように制御するために使用してもよい。
【００２１】
[0027]図３は、本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビット入力へのスキャン演算を実施するためのシステム３００の結果を示している。オプションとして、このシステムは、図１〜２の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００２２】
[0028]図示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素３０２が備えられている。処理要素（例えばスレッド）はそれぞれ、１ビット値３０４を有する。一実施形態では、これらの１ビット値は、論理表現を評価することから導出されてもよい。この場合、１ビット値は、述部ビットと称されることもある。
【００２３】
[0029]操作において、スキャン演算命令は、並列プロセッサアーキテクチャによって受け取られてもよい。この場合、スキャンは、接頭部和スキャン演算命令を含んでもよい。スキャン演算命令に応答して、接頭部和スキャン演算命令は、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して実施されてもよい。
【００２４】
[0030]Ｎ個の処理要素のグループ（すなわちワープ）を横断して述部ビット入力の接頭部和スキャン演算（図の実施例の排他的スキャン）を行った結果、ｌｏｇ（Ｎ）ビットの整数がもたらされる。図３は、Ｎ＝１６個の処理要素（例えばスレッド）のワープのスキャンの結果３０６を示している。勿論、様々な実施形態において、任意の数の処理要素が使用されてもよい。処理要素に引き渡される値「ｉ」は、所与の述部ビットを１とする、より小さいインデックスを有する処理要素（例えばスレッド）の数であることに留意されたい。様々な実施形態では、この演算は、ストリーム圧縮及び基数ソートなど、複数の計算カーネルの基礎として使用されてもよい。
【００２５】
[0031]一部の場合では、完全に一般的なスキャン演算が、直接的なハードウェア実装に適さないことがある。例えば、スキャン演算は、任意の長さのシーケンス、及び多くの可能な数値タイプ（例えばｉｎｔ、ｆｌｏａｔ、ｓｈｏｒｔなど）に対処することを伴い得る。対照的に、固定長の小さいシーケンスに対するバイナリスキャンのプリミティブが、ハードウェアで実装され、マシン命令として提供されることがある。マルチプロセッサ内の処理要素の数は、アーキテクチャに関する既知の定数であり、数値タイプは、１ビット値に対して一定に保たれ得る。
【００２６】
[0032]図４は、本発明の一実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためにシステム４００を示している。オプションとして、このシステムは、図１〜３の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装され得る。やはり、上記の定義が、この説明でも当てはまり得る。
【００２７】
[0033]示されたように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素４０２が備えられている。さらに、複数の加算器４０４が含まれる。こうした加算器は、数を加算することができるどんな回路又は装置をも含み得る。
【００２８】
[0034]動作において、処理要素（例えばスレッド）はそれぞれ、１ビット値を保持してもよい。したがって、スキャン演算命令は、複数の処理要素によって受け取られるとき、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して実施されてもよい。この場合、加算器４０４の集まりは加算網（例えば回路）を形成し、この加算網は、処理装置４０２のそれぞれから１ビットの入力値を受け取り、スキャン演算の結果を各処理要素４０６に引き渡す。
【００２９】
[0035]図４は、１６個の処理要素を含んで示されているが、任意の数の処理要素が使用され得ることに留意されたい。さらに、図４のシステムは、排他的スキャンを実施するためのシステムとして示されている。別の実施形態では、このシステムは、包括的スキャンを実施するように構成されてもよい。
【００３０】
[0036]さらに、図４のシステムは、処理要素の数（Ｎ）に等しい深さで構成される。様々な他の実施形態で、このシステムは、深さを最小化するように構成されてもよい。こうした最小化は、任意の数の技術を使用して遂行されてもよい。
【００３１】
[0037]図５は、本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステム５００を示している。オプションとして、このシステムは、図１〜４の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００３２】
[0038]示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素５０２が備えられている。さらに、加算器５０４のツリーが含まれる。動作において、それぞれの処理要素５０２は、１ビット入力を与える。
【００３３】
[0039]オプションとして、この１ビット入力は、指定された述部レジスタから取られてもよい。これらの入力は、加算器のツリーを通して供給され、出力として接頭部和値５０６を、対応する処理要素に引き渡してもよい。一実施形態では、それぞれの出力は、各処理要素について指定されたデータレジスタ内に置かれてもよい。
【００３４】
[0040]示されたように、加算器５０４のツリーによって形成された加算システムは、要素Ｎを処理要素の数として、深さ値ｌｏｇ（Ｎ）を有する。しかし、一部の場合では、システム内の加算器の数を減らすことが望ましいことがある。したがって、加算器が減少し、アルゴリズムの深さが増加したシステムが使用されてもよい。
【００３５】
[0041]図６は、本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステム６００を示している。オプションとして、このシステムは、図１〜５の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００３６】
[0042]示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素６０２が備えられている。さらに、複数の加算器６０４が含まれる。動作において、それぞれの処理要素は、１ビット入力を与える。
【００３７】
[0043]システムの深さは、システムの待ち時間に直接相関することに留意されたい。したがって、システムの総面積が、総待ち時間よりも懸念される場合は、より少ない数の加算器を備えたシステム（例えば図６のシステム）が望ましいことがある。もう一方で、待ち時間が、総面積よりも懸念される場合は、より大きい数の加算器及びより小さい深さを有するシステム（例えば図５のシステム）が望ましいことがある。
【００３８】
[0044]いずれか実装形態を使用すると、１ビット入力のスキャンは、一般的な数のスキャンよりも遥かに安価になり得る。例えば、完全な３２ビット整数が合計される場合は、加算を実施するシステム内の加算器はそれぞれ、３２ビット加算器でなければならない。しかし、１ビット入力では、Ｎをシステム内の処理要素の数として、各加算器の幅はせいぜいｌｏｇ（Ｎ）である。この説明のコンテキストでは、加算器の幅は、加算器によって扱うことができる入力数が含み得るビットの最大数を指す。
【００３９】
[0045]図６の特定の場合及びコンテキストでは、それぞれの加算器は、入力当たりせいぜい４ビットに遭遇する。一実施形態では、加算器のツリーのそれぞれ異なるレベルで、それぞれ異なる幅の加算器が使用されてもよい。例えば、ツリーの第１のレベル６０６（すなわち入力のすぐ下）の加算器は、１ビット入力だけを含んでもよい。さらに、第２のレベル６０８は、２ビット入力だけを含んでもよい。
【００４０】
[0046]図２〜６のコンテキストで述べられるようなデータ経路を与えられると、ＳＩＭＤマルチプロセッサの処理要素を横断するバイナリスキャンは、マシン命令としてプログラムにさらされ得る（ｅｘｐｏｓｅ）。一実施形態では、各処理要素からレジスタ（「Ｒｐｒｅｄ」）内の１ビット述部を入力として取り、別のレジスタ（「Ｒｓｕｍ」）内の適切な接頭部和を各処理要素に返す述部スキャン命令（「ＰＳＣＡＮ」）が使用されてもよい。こうした命令が、以下の表２に示されている。
【表２】
【００４１】
[0047]この命令の操作は、図２〜６のシステムに直接対応する。処理要素はそれぞれ、システムの並列接頭部加算網の入力に述部ビットを与え、それぞれが単一の出力値を受け取る。
【００４２】
[0048]ほとんどのマルチプロセッサハードウェアは、計算中に処理要素を選択的に非アクティブ化するための機構を組み込む。これは一般に、名目上ＳＩＭＤのプロセッサアレイがプログラムの分岐経路を実行することを可能にするために行われる。こうした状況では、非アクティブ化された処理要素は、「ＰＳＣＡＮ」命令がアクティブ処理要素によって実行されるとき、並列接頭部計算に「０」を与えると仮定してもよい。しかし、別の実施形態では、非アクティブ処理要素が「１」を与える、命令の変形体が提供されてもよい。
【００４３】
[0049]さらに、図２〜６は、加算演算のコンテキストで述べられているが、他の演算も同様に適用することができる。例えば、スキャン演算及び加算器は、加算以外のどんな連結演算をも使用するように一般化してもよい。したがって、スキャン演算は、並列プロセッサアーキテクチャの複数の機能ユニットを使用して実施してもよい。
【００４４】
[0050]この場合、機能ユニットは、加算器、ブール論理演算子、算術及び論理演算子、並びに他の様々な機能ユニットを含んでもよい。さらに、示されたように、並列プロセッサアーキテクチャは、複数のレベルの機能ユニットを含んでもよい。この場合、レベルの数は、処理要素の数より小さい。さらに、レベルの数は、多くの場合、処理要素数の対数よりも小さいことがある。
【００４５】
[0051]マシン命令のコンテキストでは、加算命令と同様に、ＡＮＤ、ＯＲ及びＸＯＲなどの命令が使用されてもよい。さらに、１ビット入力では、ＭＩＮ、ＭＡＸ及び乗算などの演算が、これらの３つの上記１ビット操作に減少され得る。上述されたように、こうした命令のデータ経路は、構成要素をなす加算器ブロックが適切なＡＮＤ／ＯＲ／ＸＯＲゲートで置き換えられた、図３〜６に示されたものと同一であるように見える。さらに、例示的な一実施形態では、図３〜６のコンテキストで述べられたシステムは、パイプライン構成で実装されてもよい。この場合、こうしたパイプライン構成を実装するために、ラッチが使用されてもよい。
【００４６】
[0052]スキャン演算命令に対応するマシン命令は、様々なコンピュータプログラミング言語（例えばＣ、Ｃ＋＋など）を使用して実装されてもよいことに留意されたい。一実施形態では、単一のイントリンシックとして計算統一デバイスアーキテクチャ（ＣＵＤＡ商標：Ｃｏｍｐｕｔｅ Ｕｎｉｆｉｅｄ Ｄｅｖｉｃｅ Ａｒｃｈｉｔｅｃｔｕｒｅ）Ｃを使用して実装される。例えば、表３は、ＣＵＤＡ（商標）Ｃの命令を示しており、ただし、「ｉ」は、スレッドインデックスを表す。
【表３】
【００４７】
[0053]この機能性をさらすことへの別の手法は、プログラムによって明示的に計算された述部ではなく、処理要素の「アクティブ」ビットに対するバイナリ接頭部和を暗黙に実施することである。この構成の一例が、以下の表４に示されている。
【表４】
【００４８】
[0054]この場合、マルチプロセッサ「アクティブ」状態にアクセスするために使用するコンパイラ用に、基礎となるプロセッサ機構が存在してもよい。
【００４９】
[0055]勿論、これは、より高いレベルの言語でプリミティブをさらすことへの１つの可能な手法にすぎず、特にＣＵＤＡ（商標）Ｃに関係する。プリミティブマシンサポートをさらす他の手段が考慮される。実質的に異なる設計を有する言語（例えばデータ並列Ｃなど）が、それぞれ異なる言語レベル実施形態を使用することに留意されたい。
【００５０】
[0056]一実施形態では、処理要素、或いはスレッドの１つ又は複数のグループ（例えばワープ）は、協調型スレッド配列（ＣＴＡ：Ｃｏｏｐｅｒａｔｉｖｅ Ｔｈｒｅａｄ Ａｒｒａｙ）で共に実行されてもよい。したがって、並列プロセッサアーキテクチャは、処理要素間の調整を提供し得る。この場合、調整は、書き込まれる結果の宛先に関する調整を含んでもよい。一実施形態では、複数の処理要素は、オンチップ共有メモリを介して互いに伝達し、バリアを介して同期することができ得る。
【００５１】
[0057]複数のスレッドで構成されたＣＴＡを横断したスキャンを実施するとき、２つのレベルのスキャンが実施されてもよい。第１のスキャンは、それぞれのワープ内で行われてもよい。オプションとして、上述されたように、第１のスキャンは、「ＰＳＣＡＮ」プリミティブを用いて実装されてもよい。第２のスキャンは、各ワープから単一の値を受け取り、これらの部分和へのスキャンを実施してもよい。これらはすべて、３２のワープ幅の場合には、５ビット整数であることに留意されたい。
【００５２】
[0058]一実施形態では、１ビットのスキャンプリミティブが、各２進数字へのスキャンをそれぞれ独立に実施し、次いで結果を合計することによってマルチビット数の接頭部和を計算するために使用されてもよい。換言すると、並列プロセッサアーキテクチャは、マルチビット値の個々のビットのスキャンを個々に実施し、結果をビットシフトした後に個々のスキャンの結果を合計することによってマルチビット値に対するスキャン演算を実施してもよい。例えば、ワープ内の各スレッドに、５ビット値「ｘ＿ｉ」が与えられると仮定する。これらの値の接頭部和は、表５に示されるように計算されてもよい。
【表５】
【００５３】
[0059]この実装形態の結果は、完全スキャンカーネルを伴う実装形態と同じになる。しかし、「ＰＳＣＡＮ」が、実行のために単一の命令を使用すると仮定すると、これは、入力値のビット数が小さい場合、完全カーネルよりも遥かに効率的になり得る。スキャンカーネル関するさらなる情報は、その全体が参照として本明細書に組み込まれている、２００７年９月２７日に出願された特許出願第１１／８６２，９３８号、「ＳＹＳＴＥＭ，ＭＥＴＨＯＤ ＡＮＤ ＣＯＭＰＵＴＥＲ ＰＲＯＧＲＡＭ ＰＲＯＤＵＣＴ ＦＯＲ ＰＥＲＦＯＲＭＩＮＧ Ａ ＳＣＡＮ ＯＰＥＲＡＴＩＯＮ」に見ることができる。
【００５４】
[0060]上記の機能性は、並行処理アーキテクチャを含めて任意の所望の環境で使用されてもよく、効率的な並列カーネルの構成が望まれる様々な状況で実装されてもよいことに留意されたい。例えば、アイテムのキューが、操作されているデータに対応し、スレッド当たり最大１アイテムをキューに書き込むと仮定する。あらゆるスレッドが常に１アイテムを書き込む場合は、各スレッドは、キューポインタからのどのオフセットを、値として書き込むべきか常に分かっている。
【００５５】
[0061]しかし、個々の各スレッドが、値を書き込むかどうか選択する場合は、ワープ内のすべてのスレッドは、値の書込みの適切なオフセットを計算しなければならない。このオフセットの計算は、各スレッドが書込みを望んでいるかどうか判断する述部へのスキャンを使用することによって実装されてもよい。この計算は、表６に示されるようなバイナリスキャンプリミティブを使用して、単純かつ効率的に表現することができる。
【表６】
【００５６】
[0062]より簡潔な変形体は、ワープを横断してプロセッサの「アクティブ」ビットを暗黙的にスキャンすることによって作られ得る。例えば、こうした１つの変形体が、以下の表７に示されている。
【表７】
【００５７】
[0063]別の実施例として、スレッドのＣＴＡは、スレッド当たり１つの値で数列を制御していることがある。この実施例では、「ピポット」値が選択されてもよく、配列は、ピポット未満である配列内のすべての値が他のすべての数の前に来るように入れ替えてもよい。これは、例えばＱｕｉｃｋｓｏｒｔなどのアルゴリズムにおける一ステップである。
【００５８】
[0064]この演算を実施するために、述部「ｐ」を受け取る「ランク（）」プリミティブが定義されてもよい。述部が真であるスレッドは、述部が真である、より低いスレッドインデックスを有するスレッド数のカウントを受け取る。述部が偽であるスレッドは、述部が偽である、より低いスレッドインデックスを有するスレッド数のカウント、及び真の述部の総数を受け取る。表８は、ＣＵＤＡ（商標）の代表的な関数の一例を示しており、ただし、関数「ｃｔａ＿ｐｒｅｆｉｘ＿ｓｕｍ（）」は、２００７年９月２７日に出願された特許出願第１１／８６２，９３８号、「ＳＹＳＴＥＭ，ＭＥＴＨＯＤ ＡＮＤ ＣＯＭＰＵＴＥＲ ＰＲＯＧＲＡＭ ＰＲＯＤＵＣＴ ＦＯＲ ＰＥＲＦＯＲＭＩＮＧ Ａ ＳＣＡＮ ＯＰＥＲＡＴＩＯＮ」に述べられたやり方で、ワープ内スキャンに基づいて構築される。
【表８】
【００５９】
[0065]こうしたプリミティブが与えられると、パーティション関数が書き込まれ得る。例えば、表９は、こうした１つのパーティション関数の一例を示している。
【表９】
【００６０】
[0066]パーティションと同様に、数列のソートは、多くの適用例に役立つ別の演算である。上記に定義された「ｒａｎｋ（）」プリミティブに関しても容易に実装される。基数ソートの各パスは、比較述部に基づくのではなく、データ値の単一ビットの値に基づく「ｐａｒｔｉｔｉｏｎ（）」のやり方で単に入れ替えることである。この説明のコンテキストでは、基数ソートは、個々の桁を処理することによって整数をソートするソートアルゴリズムである。基数ソートを使用する実装形態の一例が、表１０に示されている。
【表１０】
【００６１】
[0067]様々な実施形態について上記に述べられているが、それらは、例示するためだけに提示されており、限定するものではないことを理解されたい。例えば、様々な他の実施形態では、上記の図のコンテキスト及び詳細で、任意の数のスキャンアルゴリズムが使用され実装されてもよい。
【００６２】
[0068]図７は、様々な上記実施形態の様々なアーキテクチャ及び／又は機能性が実装され得る例示的なシステム７００を示している。示されたように、通信バス７０２に接続された少なくとも１つのホストプロセッサ７０１を含むシステムが提供される。このシステムは、メインメモリ７０４をも含む。制御論理（ソフトウェア）及びデータは、ランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）の形を取り得るメインメモリに格納される。
【００６３】
[0069]このシステムは、グラフィックスプロセッサ７０６及びディスプレイ７０８、すなわちコンピュータモニタをも含む。一実施形態では、グラフィックスプロセッサは、複数のシェーダモジュール、ラスター化モジュールなどを含んでもよい。上記モジュールはそれぞれ、グラフィックス処理装置（ＧＰＵ）を形成するように、単一の半導体プラットフォーム上にでも位置し得る。
【００６４】
[0070]この説明では、単一の半導体プラットフォームは、単独のユニタリー半導体ベース集積回路またチップを指し得る。単一の半導体プラットフォームという用語は、オンチップ演算をシミュレートし、従来の中央処理装置（ＣＰＵ：ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）及びバス実装を使用するのに比べて大幅に改良された、向上した接続性を有するマルチチップモジュールを指し得ることに留意された。勿論、様々なモジュールもまた、それぞれ別々に位置することも、ユーザの要望による様々な組合せの半導体プラットフォームに位置することもある。
【００６５】
[0071]このシステムは、２次記憶装置７１０をも含み得る。２次記憶装置は、例えばハードディスクドライブ、及び／又はフロッピーディスクドライブ、磁気テープドライブ、コンパクトディスクドライブなどである取外し可能記憶ドライブを含む。取外し可能記憶ドライブは、よく知られているやり方で取外し可能記憶ユニットから読み出し、及び／又はそれに書き込む。
【００６６】
[0072]コンピュータプログラム、又はコンピュータ制御論理アルゴリズムは、メインメモリ及び／又は２次記憶装置内に格納されてもよい。こうしたコンピュータプログラムは、実行されるとき、システムが様々な機能を実施することを可能にする。メモリ、記憶装置及び／又は他の記憶装置は、コンピュータ読取り可能媒体の可能な例である。
【００６７】
[0073]一実施形態では、上記の様々な図のアーキテクチャ及び／又は機能性は、ホストプロセッサ、グラフィックスプロセッサ、ホストプロセッサとグラフィックスプロセッサの両方の能力の少なくとも一部が可能である集積回路（図示せず）、チップセット（すなわち関連する機能を実施するためのユニットとして働くように設計され、販売される集積回路群など）、及び／又はそれに関する他の任意の集積回路のコンテキストで実装されてもよい。さらに、上記の様々な図の要素割当て機能性は、１つの可能な実施形態では、ドライバ７１２の制御の下、上記集積回路のいずれかで実装されてもよい。
【００６８】
[0074]さらに、上記の様々な図のアーキテクチャ及び／又は機能性は、一般的なコンピュータシステム、回路基板システム、娯楽専用のゲームコンソールシステム、アプリケーション固有のシステム、及び／又は他の任意の所望のシステムのコンテキストで実装されてもよい。例えば、システムは、デスクトップコンピュータ、ラップトップコンピュータ、及び／また他の任意のタイプの論理の形を取ってもよい。さらに、システムは、それだけに限らないが、携帯情報端末（ＰＤＡ：ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｔａｎｔ）装置、携帯電話装置、テレビなどを含めて、他の様々な装置の形を取ってもよい。
【００６９】
[0075]さらに、示されてないが、このシステムは、通信のためにネットワーク（例えば通信ネットワーク、ローカルエリアネットワーク（ＬＡＮ：ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ）、無線ネットワーク、インターネットなどの広域ネットワーク（ＷＡＮ：ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ）、ピアツーピアネットワーク、ケーブルネットワークなど）に結合されてもよい。
【００７０】
[0076]様々な実施形態について上記で述べたが、それらは、例示するためだけに提示されており、限定するものではないことを理解されたい。したがって、好ましい実施形態の広さ及び範囲は、上記の例示的な実施形態のいずれかによって限定されるものではなく、添付の特許請求の範囲及びその等価物に従って定義されるものにすぎない。
【符号の説明】
【００７１】
２０２ 並行処理アーキテクチャ
２０４ 並列プロセッサ
２０６ ローカル共有メモリ
２０８ グローバルメモリ
２１０ ドライバ
３００ システム
３０２ 処理要素
３０４ １ビット値
３０６ 結果
４００ システム
４０２ 処理要素
４０４ 加算器
４０６ 処理要素
５００ システム
５０２ 処理要素
５０４ 加算器
５０６ 接頭部和値
６００ システム
６０２ 処理要素
６０４ 加算器
６０６ 第１レベル
６０８ 第２レベル
７０１ ホストプロセッサ
７０２ 通信バス
７０４ メインメモリ
７０６ グラフィックスプロセッサ
７０８ ディスプレイ
７１０ ２次記憶装置
【技術分野】
【０００１】
[0001]本発明は、スキャン演算に関し、より具体的には、並行処理アーキテクチャを使用してスキャン演算を実施することに関する。
【背景技術】
【０００２】
[0002]並列プロセッサアーキテクチャは一般に、幅広い様々な計算アルゴリズムを実施するために使用される。こうしたアーキテクチャを使用して一般に実施されるアルゴリズムの一例は、スキャン演算（例えば「ａｌｌ−ｐｒｅｆｉｘ−ｓｕｍｓ」演算など）である。こうした１つのスキャン演算が、表１に定義されている。
【表１】
【０００３】
[0003]具体的には、配列［ａ０，ａｌ，…，ａｎ−１］、及び「Ｉ」を単位元とする演算子
【数１】
与えられると、表１の配列が返される。例えば、演算子
【数２】
が加算演算子である場合、配列［３ １ ７ ０ ４ １ ６ ３］に対してスキャン演算を実施すると、［０ ３ ４ １１ １１ １５ １６ ２２］が返されるなどである。上記の例では加算演算子が示されているが、こうした演算子は、２つのオペランドの任意の連結演算子であってもよい。
【０００４】
[0004]さらに、スキャン演算は、（表１に示されたような）排他的スキャン演算であっても、包括的スキャン演算であってもよい。排他的スキャンは、結果の各要素ｊが、入力配列の要素ｊまで（要素ｊを含まず）のすべての要素の和となるスキャンを指す。もう一方では、包括的スキャンでは、要素ｊを含むすべての要素が合計される。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
[0005]これまで、並列プロセッサアーキテクチャを使用したスキャン演算などの計算アルゴリズムをより効率的に実施することが引き続き求められている。
【課題を解決するための手段】
【０００６】
[0006]並行処理アーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム、方法及びコンピュータ製品が提供される。動作において、スキャン演算命令が受信される。さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して、単一ビット値のシーケンスに対して実施される。
【図面の簡単な説明】
【０００７】
【図１】本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するための方法を示す図である。
【図２】本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステムを示す図である。
【図３】本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステムの結果を示す図である。
【図４】本発明の一実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図５】本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図６】本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステムを示す図である。
【図７】上記の様々な実施形態の様々なアーキテクチャ及び／又は機能が実施され得る、例示的なシステムを示す図である。
【発明を実施するための形態】
【０００８】
[0014]図１は、本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビットに対するスキャン演算を実施するための方法１００を示している。示されるように、スキャン演算命令が受け取られる。操作１０２を参照されたい。この説明のコンテキストでは、スキャン演算命令は、スキャン演算に対応する任意の命令或いはコマンドを指す。
【０００９】
[0015]さらに、スキャン演算命令に応答して、スキャン演算が、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンス値に対して実施される。操作１０４を参照されたい。この説明のコンテキストでは、処理要素は、並列プロセッサアーキテクチャの任意の構成要素を指す。さらに、単一ビット値のシーケンスは、１ビット値の任意のシーケンスを含み得る。一部の実施形態では、この設計によって、単一ビット入力に対するスキャン演算などの計算アルゴリズムが、より効率的に実施され得る。
【００１０】
[0016]さらに、この説明のコンテキストでは、スキャン演算は、現在の要素と、配列の少なくとも１つの前の要素とが関与する任意の演算を指し得る。例えば、様々な実施形態では、スキャン演算は。接頭部和スキャン演算、排他的スキャン演算、包括的スキャン演算、及び／又は他の任意のスキャン演算（例えば、より多くの又は少ない要素、及び／又は他の演算子などが関与する）を含み得る。
【００１１】
[0017]さらに、この説明のコンテキストでは、並列プロセッサアーキテクチャは、並列に動作する２つ以上の処理要素を含む任意のアーキテクチャを含んでもよい。一実施形態では、こうした並列プロセッサアーキテクチャは、グラフィックスプロセッサ（例えばグラフィックス処理装置（ＧＰＵ：ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）など）、又は例えばチップセット、システムオンチップ（ＳＯＣ：ｓｙｓｔｅｍ−ｏｎ−ｃｈｉｐ）、ＣＰＵに組み込まれたコア、個別プロセッサなどの形のグラフィックス処理能力を備えた他の集積回路の形を取ってもよい。別の実施形態では、上記の並行処理アーキテクチャは、ベクタプロセッサを含んでもよい。
【００１２】
[0018]次に、ユーザの要望により上記フレームワークがそれと共に実装されることも、実装されないこともある様々な任意選択のアーキテクチャ及び特徴に関して、より例示的な情報が示される。以下の情報は、例示するために述べられており、どんなやり方でも限定的と見なすべきでないことに強く留意されたい。以下の特徴のいずれもが、述べられた他の特徴を除外して、又は除外せずに任意選択で組み込まれ得る。
【００１３】
[0019]図２は、本発明の一実施形態による、単一ビット値のシーケンスに対してスキャン演算を実施するためのシステム２００を示している。任意選択として、このシステムは、図１の方法を実施するために実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００１４】
[0020]示されるように、並行処理アーキテクチャ２０２が提供される。こうした並行処理アーキテクチャは、複数の並列プロセッサ２０４を含む。示されていないが、こうした並列プロセッサは、所定の数のスレッドに対して動作可能であり得る。このために、並列プロセッサはそれぞれ並列に動作し得るが、対応するスレッドもまた、並列に動作してもよい。
【００１５】
[0021]一実施形態では、並行処理アーキテクチャは、１つ又は複数の単一命令多重データ（ＳＩＭＤ：ｓｉｎｇｌｅ ｉｎｓｔｒｕｃｔｉｏｎ ｍｕｌｔｉｐｌｅ ｄａｔａ）処理要素を含んでもよい。こうしたシステムでは、プロセッサによって実行されているスレッドをグループにまとめて、単一グループ内のすべてのスレッドがどんな瞬間においても、潜在的にそれぞれ異なるデータに対してであるが、正確に同じ命令を実行しているようにする。一実施形態では、こうしたやり方で動作するこのスレッド群は、「ワープ」と呼ばれることもある。さらに、こうしたグループ内の所定のスレッド数は、対応するプロセッサの「ワープサイズ」と呼ばれることもある。
【００１６】
[0022]別の実施形態では、上記の並列処理アーキテクチャは、グラフィックスプロセッサ、或いは（例えばチップセット、システムオンチップ（ＳＯＣ）、ＣＰＵに組み込まれたコア、個別プロセッサなどの形の）グラフィックス処理能力を備えた他の任意の集積回路を含んでもよい。別の実施形態では、上記の並行処理アーキテクチャは、Ｓｏｎｙ（登録商標）社、Ｔｏｓｈｉｂａ（登録商標）社、及びＩＢＭ（登録商標）社によって合同で開発されたＣｅｌｌ広帯域エンジンマイクロプロセッサアーキテクチャを指すＣｅｌｌプロセッサなど、１つ又は複数のベクトル処理要素を備えたプロセッサを含んでもよい。
【００１７】
[0023]引き続き図２を参照すると、並行処理アーキテクチャは、ローカル共有メモリ２０６を含んでもよい。並行処理アーキテクチャの並列プロセッサはそれぞれ、それ自体のローカル共有メモリへの読出し及び／又は書込みを行い得る。この共有メモリは、各プロセッサに関連する物理的に別個のメモリで構成されてもよく、或いはそれは、プロセッサ間で共有された１つ又は複数のメモリの別個に割り当てられた領域で構成されてもよい。さらに、示された実施形態では、共有メモリは、並行処理アーキテクチャのプロセッサが具現化される集積回路内で具現化されてもよい。
【００１８】
[0024]さらに、図では、グローバルメモリ２０８が含まれている。使用時、こうしたグローバルメモリは、並行処理アーキテクチャのすべてのプロセッサからアクセス可能である。示されるように、こうしたグローバルメモリは、上記の並行処理アーキテクチャのプロセッサが具現化される集積回路とは別個の集積回路内で具体化されてもよい。並行処理アーキテクチャは、図２の様々な集積回路内に特定のやり方で具現化されるように示されているが、システム構成要素は、要望に応じて、同じ集積回路内で具体化されることも、具現化されないこともあることに留意されたい。
【００１９】
[0025]さらに、図２のこのシステムは、要望に応じて、並行処理アーキテクチャを制御するためのドライバ２１０をさらに含んでもよい。一実施形態では、ドライバは、こうした制御を容易にするためのライブラリを含んでもよい。例えば、こうしたライブラリは、本明細書に述べられた機能性をインスタンス化し得るライブラリ呼出しを含んでもよい。
【００２０】
[0026]さらに、別の実施形態では、ドライバは、並行処理アーキテクチャ（例えばグラフィックスプロセッサなど）を使用して一般的な計算能力を提供することができ得る。こうしたドライバの一例は、ＮＶＩＤＩＡコーポレーション社によって提供されたＣＵＤＡ（商標）フレームワークと併せて提供されてもよい。使用時、ドライバは、並列処理アーキテクチャを図１の方法に従って動作するように制御するために使用してもよい。
【００２１】
[0027]図３は、本発明の一実施形態による、並行処理アーキテクチャを使用して単一ビット入力へのスキャン演算を実施するためのシステム３００の結果を示している。オプションとして、このシステムは、図１〜２の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００２２】
[0028]図示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素３０２が備えられている。処理要素（例えばスレッド）はそれぞれ、１ビット値３０４を有する。一実施形態では、これらの１ビット値は、論理表現を評価することから導出されてもよい。この場合、１ビット値は、述部ビットと称されることもある。
【００２３】
[0029]操作において、スキャン演算命令は、並列プロセッサアーキテクチャによって受け取られてもよい。この場合、スキャンは、接頭部和スキャン演算命令を含んでもよい。スキャン演算命令に応答して、接頭部和スキャン演算命令は、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して実施されてもよい。
【００２４】
[0030]Ｎ個の処理要素のグループ（すなわちワープ）を横断して述部ビット入力の接頭部和スキャン演算（図の実施例の排他的スキャン）を行った結果、ｌｏｇ（Ｎ）ビットの整数がもたらされる。図３は、Ｎ＝１６個の処理要素（例えばスレッド）のワープのスキャンの結果３０６を示している。勿論、様々な実施形態において、任意の数の処理要素が使用されてもよい。処理要素に引き渡される値「ｉ」は、所与の述部ビットを１とする、より小さいインデックスを有する処理要素（例えばスレッド）の数であることに留意されたい。様々な実施形態では、この演算は、ストリーム圧縮及び基数ソートなど、複数の計算カーネルの基礎として使用されてもよい。
【００２５】
[0031]一部の場合では、完全に一般的なスキャン演算が、直接的なハードウェア実装に適さないことがある。例えば、スキャン演算は、任意の長さのシーケンス、及び多くの可能な数値タイプ（例えばｉｎｔ、ｆｌｏａｔ、ｓｈｏｒｔなど）に対処することを伴い得る。対照的に、固定長の小さいシーケンスに対するバイナリスキャンのプリミティブが、ハードウェアで実装され、マシン命令として提供されることがある。マルチプロセッサ内の処理要素の数は、アーキテクチャに関する既知の定数であり、数値タイプは、１ビット値に対して一定に保たれ得る。
【００２６】
[0032]図４は、本発明の一実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためにシステム４００を示している。オプションとして、このシステムは、図１〜３の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装され得る。やはり、上記の定義が、この説明でも当てはまり得る。
【００２７】
[0033]示されたように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素４０２が備えられている。さらに、複数の加算器４０４が含まれる。こうした加算器は、数を加算することができるどんな回路又は装置をも含み得る。
【００２８】
[0034]動作において、処理要素（例えばスレッド）はそれぞれ、１ビット値を保持してもよい。したがって、スキャン演算命令は、複数の処理要素によって受け取られるとき、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して実施されてもよい。この場合、加算器４０４の集まりは加算網（例えば回路）を形成し、この加算網は、処理装置４０２のそれぞれから１ビットの入力値を受け取り、スキャン演算の結果を各処理要素４０６に引き渡す。
【００２９】
[0035]図４は、１６個の処理要素を含んで示されているが、任意の数の処理要素が使用され得ることに留意されたい。さらに、図４のシステムは、排他的スキャンを実施するためのシステムとして示されている。別の実施形態では、このシステムは、包括的スキャンを実施するように構成されてもよい。
【００３０】
[0036]さらに、図４のシステムは、処理要素の数（Ｎ）に等しい深さで構成される。様々な他の実施形態で、このシステムは、深さを最小化するように構成されてもよい。こうした最小化は、任意の数の技術を使用して遂行されてもよい。
【００３１】
[0037]図５は、本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステム５００を示している。オプションとして、このシステムは、図１〜４の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００３２】
[0038]示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素５０２が備えられている。さらに、加算器５０４のツリーが含まれる。動作において、それぞれの処理要素５０２は、１ビット入力を与える。
【００３３】
[0039]オプションとして、この１ビット入力は、指定された述部レジスタから取られてもよい。これらの入力は、加算器のツリーを通して供給され、出力として接頭部和値５０６を、対応する処理要素に引き渡してもよい。一実施形態では、それぞれの出力は、各処理要素について指定されたデータレジスタ内に置かれてもよい。
【００３４】
[0040]示されたように、加算器５０４のツリーによって形成された加算システムは、要素Ｎを処理要素の数として、深さ値ｌｏｇ（Ｎ）を有する。しかし、一部の場合では、システム内の加算器の数を減らすことが望ましいことがある。したがって、加算器が減少し、アルゴリズムの深さが増加したシステムが使用されてもよい。
【００３５】
[0041]図６は、本発明の別の実施形態による、並行処理アーキテクチャを使用してハードウェア内でスキャン演算を実施するためのシステム６００を示している。オプションとして、このシステムは、図１〜５の詳細のコンテキストで実装されてもよい。しかし、勿論、このシステムは、任意の所望の環境で実装されてもよい。この説明では、上記の定義が当てはまり得ることにも留意されたい。
【００３６】
[0042]示されるように、並列プロセッサアーキテクチャの一部として含まれた複数の処理要素６０２が備えられている。さらに、複数の加算器６０４が含まれる。動作において、それぞれの処理要素は、１ビット入力を与える。
【００３７】
[0043]システムの深さは、システムの待ち時間に直接相関することに留意されたい。したがって、システムの総面積が、総待ち時間よりも懸念される場合は、より少ない数の加算器を備えたシステム（例えば図６のシステム）が望ましいことがある。もう一方で、待ち時間が、総面積よりも懸念される場合は、より大きい数の加算器及びより小さい深さを有するシステム（例えば図５のシステム）が望ましいことがある。
【００３８】
[0044]いずれか実装形態を使用すると、１ビット入力のスキャンは、一般的な数のスキャンよりも遥かに安価になり得る。例えば、完全な３２ビット整数が合計される場合は、加算を実施するシステム内の加算器はそれぞれ、３２ビット加算器でなければならない。しかし、１ビット入力では、Ｎをシステム内の処理要素の数として、各加算器の幅はせいぜいｌｏｇ（Ｎ）である。この説明のコンテキストでは、加算器の幅は、加算器によって扱うことができる入力数が含み得るビットの最大数を指す。
【００３９】
[0045]図６の特定の場合及びコンテキストでは、それぞれの加算器は、入力当たりせいぜい４ビットに遭遇する。一実施形態では、加算器のツリーのそれぞれ異なるレベルで、それぞれ異なる幅の加算器が使用されてもよい。例えば、ツリーの第１のレベル６０６（すなわち入力のすぐ下）の加算器は、１ビット入力だけを含んでもよい。さらに、第２のレベル６０８は、２ビット入力だけを含んでもよい。
【００４０】
[0046]図２〜６のコンテキストで述べられるようなデータ経路を与えられると、ＳＩＭＤマルチプロセッサの処理要素を横断するバイナリスキャンは、マシン命令としてプログラムにさらされ得る（ｅｘｐｏｓｅ）。一実施形態では、各処理要素からレジスタ（「Ｒｐｒｅｄ」）内の１ビット述部を入力として取り、別のレジスタ（「Ｒｓｕｍ」）内の適切な接頭部和を各処理要素に返す述部スキャン命令（「ＰＳＣＡＮ」）が使用されてもよい。こうした命令が、以下の表２に示されている。
【表２】
【００４１】
[0047]この命令の操作は、図２〜６のシステムに直接対応する。処理要素はそれぞれ、システムの並列接頭部加算網の入力に述部ビットを与え、それぞれが単一の出力値を受け取る。
【００４２】
[0048]ほとんどのマルチプロセッサハードウェアは、計算中に処理要素を選択的に非アクティブ化するための機構を組み込む。これは一般に、名目上ＳＩＭＤのプロセッサアレイがプログラムの分岐経路を実行することを可能にするために行われる。こうした状況では、非アクティブ化された処理要素は、「ＰＳＣＡＮ」命令がアクティブ処理要素によって実行されるとき、並列接頭部計算に「０」を与えると仮定してもよい。しかし、別の実施形態では、非アクティブ処理要素が「１」を与える、命令の変形体が提供されてもよい。
【００４３】
[0049]さらに、図２〜６は、加算演算のコンテキストで述べられているが、他の演算も同様に適用することができる。例えば、スキャン演算及び加算器は、加算以外のどんな連結演算をも使用するように一般化してもよい。したがって、スキャン演算は、並列プロセッサアーキテクチャの複数の機能ユニットを使用して実施してもよい。
【００４４】
[0050]この場合、機能ユニットは、加算器、ブール論理演算子、算術及び論理演算子、並びに他の様々な機能ユニットを含んでもよい。さらに、示されたように、並列プロセッサアーキテクチャは、複数のレベルの機能ユニットを含んでもよい。この場合、レベルの数は、処理要素の数より小さい。さらに、レベルの数は、多くの場合、処理要素数の対数よりも小さいことがある。
【００４５】
[0051]マシン命令のコンテキストでは、加算命令と同様に、ＡＮＤ、ＯＲ及びＸＯＲなどの命令が使用されてもよい。さらに、１ビット入力では、ＭＩＮ、ＭＡＸ及び乗算などの演算が、これらの３つの上記１ビット操作に減少され得る。上述されたように、こうした命令のデータ経路は、構成要素をなす加算器ブロックが適切なＡＮＤ／ＯＲ／ＸＯＲゲートで置き換えられた、図３〜６に示されたものと同一であるように見える。さらに、例示的な一実施形態では、図３〜６のコンテキストで述べられたシステムは、パイプライン構成で実装されてもよい。この場合、こうしたパイプライン構成を実装するために、ラッチが使用されてもよい。
【００４６】
[0052]スキャン演算命令に対応するマシン命令は、様々なコンピュータプログラミング言語（例えばＣ、Ｃ＋＋など）を使用して実装されてもよいことに留意されたい。一実施形態では、単一のイントリンシックとして計算統一デバイスアーキテクチャ（ＣＵＤＡ商標：Ｃｏｍｐｕｔｅ Ｕｎｉｆｉｅｄ Ｄｅｖｉｃｅ Ａｒｃｈｉｔｅｃｔｕｒｅ）Ｃを使用して実装される。例えば、表３は、ＣＵＤＡ（商標）Ｃの命令を示しており、ただし、「ｉ」は、スレッドインデックスを表す。
【表３】
【００４７】
[0053]この機能性をさらすことへの別の手法は、プログラムによって明示的に計算された述部ではなく、処理要素の「アクティブ」ビットに対するバイナリ接頭部和を暗黙に実施することである。この構成の一例が、以下の表４に示されている。
【表４】
【００４８】
[0054]この場合、マルチプロセッサ「アクティブ」状態にアクセスするために使用するコンパイラ用に、基礎となるプロセッサ機構が存在してもよい。
【００４９】
[0055]勿論、これは、より高いレベルの言語でプリミティブをさらすことへの１つの可能な手法にすぎず、特にＣＵＤＡ（商標）Ｃに関係する。プリミティブマシンサポートをさらす他の手段が考慮される。実質的に異なる設計を有する言語（例えばデータ並列Ｃなど）が、それぞれ異なる言語レベル実施形態を使用することに留意されたい。
【００５０】
[0056]一実施形態では、処理要素、或いはスレッドの１つ又は複数のグループ（例えばワープ）は、協調型スレッド配列（ＣＴＡ：Ｃｏｏｐｅｒａｔｉｖｅ Ｔｈｒｅａｄ Ａｒｒａｙ）で共に実行されてもよい。したがって、並列プロセッサアーキテクチャは、処理要素間の調整を提供し得る。この場合、調整は、書き込まれる結果の宛先に関する調整を含んでもよい。一実施形態では、複数の処理要素は、オンチップ共有メモリを介して互いに伝達し、バリアを介して同期することができ得る。
【００５１】
[0057]複数のスレッドで構成されたＣＴＡを横断したスキャンを実施するとき、２つのレベルのスキャンが実施されてもよい。第１のスキャンは、それぞれのワープ内で行われてもよい。オプションとして、上述されたように、第１のスキャンは、「ＰＳＣＡＮ」プリミティブを用いて実装されてもよい。第２のスキャンは、各ワープから単一の値を受け取り、これらの部分和へのスキャンを実施してもよい。これらはすべて、３２のワープ幅の場合には、５ビット整数であることに留意されたい。
【００５２】
[0058]一実施形態では、１ビットのスキャンプリミティブが、各２進数字へのスキャンをそれぞれ独立に実施し、次いで結果を合計することによってマルチビット数の接頭部和を計算するために使用されてもよい。換言すると、並列プロセッサアーキテクチャは、マルチビット値の個々のビットのスキャンを個々に実施し、結果をビットシフトした後に個々のスキャンの結果を合計することによってマルチビット値に対するスキャン演算を実施してもよい。例えば、ワープ内の各スレッドに、５ビット値「ｘ＿ｉ」が与えられると仮定する。これらの値の接頭部和は、表５に示されるように計算されてもよい。
【表５】
【００５３】
[0059]この実装形態の結果は、完全スキャンカーネルを伴う実装形態と同じになる。しかし、「ＰＳＣＡＮ」が、実行のために単一の命令を使用すると仮定すると、これは、入力値のビット数が小さい場合、完全カーネルよりも遥かに効率的になり得る。スキャンカーネル関するさらなる情報は、その全体が参照として本明細書に組み込まれている、２００７年９月２７日に出願された特許出願第１１／８６２，９３８号、「ＳＹＳＴＥＭ，ＭＥＴＨＯＤ ＡＮＤ ＣＯＭＰＵＴＥＲ ＰＲＯＧＲＡＭ ＰＲＯＤＵＣＴ ＦＯＲ ＰＥＲＦＯＲＭＩＮＧ Ａ ＳＣＡＮ ＯＰＥＲＡＴＩＯＮ」に見ることができる。
【００５４】
[0060]上記の機能性は、並行処理アーキテクチャを含めて任意の所望の環境で使用されてもよく、効率的な並列カーネルの構成が望まれる様々な状況で実装されてもよいことに留意されたい。例えば、アイテムのキューが、操作されているデータに対応し、スレッド当たり最大１アイテムをキューに書き込むと仮定する。あらゆるスレッドが常に１アイテムを書き込む場合は、各スレッドは、キューポインタからのどのオフセットを、値として書き込むべきか常に分かっている。
【００５５】
[0061]しかし、個々の各スレッドが、値を書き込むかどうか選択する場合は、ワープ内のすべてのスレッドは、値の書込みの適切なオフセットを計算しなければならない。このオフセットの計算は、各スレッドが書込みを望んでいるかどうか判断する述部へのスキャンを使用することによって実装されてもよい。この計算は、表６に示されるようなバイナリスキャンプリミティブを使用して、単純かつ効率的に表現することができる。
【表６】
【００５６】
[0062]より簡潔な変形体は、ワープを横断してプロセッサの「アクティブ」ビットを暗黙的にスキャンすることによって作られ得る。例えば、こうした１つの変形体が、以下の表７に示されている。
【表７】
【００５７】
[0063]別の実施例として、スレッドのＣＴＡは、スレッド当たり１つの値で数列を制御していることがある。この実施例では、「ピポット」値が選択されてもよく、配列は、ピポット未満である配列内のすべての値が他のすべての数の前に来るように入れ替えてもよい。これは、例えばＱｕｉｃｋｓｏｒｔなどのアルゴリズムにおける一ステップである。
【００５８】
[0064]この演算を実施するために、述部「ｐ」を受け取る「ランク（）」プリミティブが定義されてもよい。述部が真であるスレッドは、述部が真である、より低いスレッドインデックスを有するスレッド数のカウントを受け取る。述部が偽であるスレッドは、述部が偽である、より低いスレッドインデックスを有するスレッド数のカウント、及び真の述部の総数を受け取る。表８は、ＣＵＤＡ（商標）の代表的な関数の一例を示しており、ただし、関数「ｃｔａ＿ｐｒｅｆｉｘ＿ｓｕｍ（）」は、２００７年９月２７日に出願された特許出願第１１／８６２，９３８号、「ＳＹＳＴＥＭ，ＭＥＴＨＯＤ ＡＮＤ ＣＯＭＰＵＴＥＲ ＰＲＯＧＲＡＭ ＰＲＯＤＵＣＴ ＦＯＲ ＰＥＲＦＯＲＭＩＮＧ Ａ ＳＣＡＮ ＯＰＥＲＡＴＩＯＮ」に述べられたやり方で、ワープ内スキャンに基づいて構築される。
【表８】
【００５９】
[0065]こうしたプリミティブが与えられると、パーティション関数が書き込まれ得る。例えば、表９は、こうした１つのパーティション関数の一例を示している。
【表９】
【００６０】
[0066]パーティションと同様に、数列のソートは、多くの適用例に役立つ別の演算である。上記に定義された「ｒａｎｋ（）」プリミティブに関しても容易に実装される。基数ソートの各パスは、比較述部に基づくのではなく、データ値の単一ビットの値に基づく「ｐａｒｔｉｔｉｏｎ（）」のやり方で単に入れ替えることである。この説明のコンテキストでは、基数ソートは、個々の桁を処理することによって整数をソートするソートアルゴリズムである。基数ソートを使用する実装形態の一例が、表１０に示されている。
【表１０】
【００６１】
[0067]様々な実施形態について上記に述べられているが、それらは、例示するためだけに提示されており、限定するものではないことを理解されたい。例えば、様々な他の実施形態では、上記の図のコンテキスト及び詳細で、任意の数のスキャンアルゴリズムが使用され実装されてもよい。
【００６２】
[0068]図７は、様々な上記実施形態の様々なアーキテクチャ及び／又は機能性が実装され得る例示的なシステム７００を示している。示されたように、通信バス７０２に接続された少なくとも１つのホストプロセッサ７０１を含むシステムが提供される。このシステムは、メインメモリ７０４をも含む。制御論理（ソフトウェア）及びデータは、ランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）の形を取り得るメインメモリに格納される。
【００６３】
[0069]このシステムは、グラフィックスプロセッサ７０６及びディスプレイ７０８、すなわちコンピュータモニタをも含む。一実施形態では、グラフィックスプロセッサは、複数のシェーダモジュール、ラスター化モジュールなどを含んでもよい。上記モジュールはそれぞれ、グラフィックス処理装置（ＧＰＵ）を形成するように、単一の半導体プラットフォーム上にでも位置し得る。
【００６４】
[0070]この説明では、単一の半導体プラットフォームは、単独のユニタリー半導体ベース集積回路またチップを指し得る。単一の半導体プラットフォームという用語は、オンチップ演算をシミュレートし、従来の中央処理装置（ＣＰＵ：ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）及びバス実装を使用するのに比べて大幅に改良された、向上した接続性を有するマルチチップモジュールを指し得ることに留意された。勿論、様々なモジュールもまた、それぞれ別々に位置することも、ユーザの要望による様々な組合せの半導体プラットフォームに位置することもある。
【００６５】
[0071]このシステムは、２次記憶装置７１０をも含み得る。２次記憶装置は、例えばハードディスクドライブ、及び／又はフロッピーディスクドライブ、磁気テープドライブ、コンパクトディスクドライブなどである取外し可能記憶ドライブを含む。取外し可能記憶ドライブは、よく知られているやり方で取外し可能記憶ユニットから読み出し、及び／又はそれに書き込む。
【００６６】
[0072]コンピュータプログラム、又はコンピュータ制御論理アルゴリズムは、メインメモリ及び／又は２次記憶装置内に格納されてもよい。こうしたコンピュータプログラムは、実行されるとき、システムが様々な機能を実施することを可能にする。メモリ、記憶装置及び／又は他の記憶装置は、コンピュータ読取り可能媒体の可能な例である。
【００６７】
[0073]一実施形態では、上記の様々な図のアーキテクチャ及び／又は機能性は、ホストプロセッサ、グラフィックスプロセッサ、ホストプロセッサとグラフィックスプロセッサの両方の能力の少なくとも一部が可能である集積回路（図示せず）、チップセット（すなわち関連する機能を実施するためのユニットとして働くように設計され、販売される集積回路群など）、及び／又はそれに関する他の任意の集積回路のコンテキストで実装されてもよい。さらに、上記の様々な図の要素割当て機能性は、１つの可能な実施形態では、ドライバ７１２の制御の下、上記集積回路のいずれかで実装されてもよい。
【００６８】
[0074]さらに、上記の様々な図のアーキテクチャ及び／又は機能性は、一般的なコンピュータシステム、回路基板システム、娯楽専用のゲームコンソールシステム、アプリケーション固有のシステム、及び／又は他の任意の所望のシステムのコンテキストで実装されてもよい。例えば、システムは、デスクトップコンピュータ、ラップトップコンピュータ、及び／また他の任意のタイプの論理の形を取ってもよい。さらに、システムは、それだけに限らないが、携帯情報端末（ＰＤＡ：ｐｅｒｓｏｎａｌ ｄｉｇｉｔａｌ ａｓｓｉｓｔａｎｔ）装置、携帯電話装置、テレビなどを含めて、他の様々な装置の形を取ってもよい。
【００６９】
[0075]さらに、示されてないが、このシステムは、通信のためにネットワーク（例えば通信ネットワーク、ローカルエリアネットワーク（ＬＡＮ：ｌｏｃａｌ ａｒｅａ ｎｅｔｗｏｒｋ）、無線ネットワーク、インターネットなどの広域ネットワーク（ＷＡＮ：ｗｉｄｅ ａｒｅａ ｎｅｔｗｏｒｋ）、ピアツーピアネットワーク、ケーブルネットワークなど）に結合されてもよい。
【００７０】
[0076]様々な実施形態について上記で述べたが、それらは、例示するためだけに提示されており、限定するものではないことを理解されたい。したがって、好ましい実施形態の広さ及び範囲は、上記の例示的な実施形態のいずれかによって限定されるものではなく、添付の特許請求の範囲及びその等価物に従って定義されるものにすぎない。
【符号の説明】
【００７１】
２０２ 並行処理アーキテクチャ
２０４ 並列プロセッサ
２０６ ローカル共有メモリ
２０８ グローバルメモリ
２１０ ドライバ
３００ システム
３０２ 処理要素
３０４ １ビット値
３０６ 結果
４００ システム
４０２ 処理要素
４０４ 加算器
４０６ 処理要素
５００ システム
５０２ 処理要素
５０４ 加算器
５０６ 接頭部和値
６００ システム
６０２ 処理要素
６０４ 加算器
６０６ 第１レベル
６０８ 第２レベル
７０１ ホストプロセッサ
７０２ 通信バス
７０４ メインメモリ
７０６ グラフィックスプロセッサ
７０８ ディスプレイ
７１０ ２次記憶装置
【特許請求の範囲】
【請求項１】
スキャン演算命令を受け取るステップと、
前記スキャン演算命令に応答して、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するステップと
を含む方法。
【請求項２】
前記スキャン演算が接頭部和スキャン演算を含む、請求項１に記載の方法。
【請求項３】
前記スキャン演算が包括的スキャン演算を含む、請求項１に記載の方法。
【請求項４】
前記スキャン演算が排他的スキャン演算を含む、請求項１に記載の方法。
【請求項５】
前記並列プロセッサアーキテクチャが前記処理要素間の調整のためのもの、請求項１に記載の方法。
【請求項６】
前記調整が、書き込まれる結果の宛先に関する調整を含む、請求項５に記載の方法。
【請求項７】
前記処理要素がそれぞれ、複数のスレッドを並列に実行する、請求項１に記載の方法。
【請求項８】
前記スキャン演算が、前記並列プロセッサアーキテクチャの複数の機能ユニットを使用して実施される、請求項１に記載の方法。
【請求項９】
前記機能ユニットが加算器を含む、請求項８に記載の方法。
【請求項１０】
前記機能ユニットがブール論理演算子を含む、請求項８に記載の方法。
【請求項１１】
前記機能ユニットが算術及び論理演算子を含む、請求項８に記載の方法。
【請求項１２】
前記並列プロセッサアーキテクチャが複数レベルの機能ユニットを含む、請求項８に記載の方法。
【請求項１３】
前記レベルの数が前記処理要素の数より小さい、請求項１２に記載の方法。
【請求項１４】
前記レベルの数が前記処理要素の数の対数より小さい、請求項１２に記載の方法。
【請求項１５】
前記並列プロセッサアーキテクチャが、マルチビット値の個々のビットのスキャンを個々に実施し、結果をビットシフトした後に前記個々のスキャンの結果を合計することによって前記マルチビット値に対する前記スキャン演算を実施する、請求項１に記載の方法。
【請求項１６】
前記並列プロセッサアーキテクチャが１つ又は複数の単一命令多重データプロセッサを含む、請求項１に記載の方法。
【請求項１７】
前記並列プロセッサアーキテクチャがグラフィックスプロセッサを含む、請求項１に記載の方法。
【請求項１８】
コンピュータ読取り可能媒体内に具体化されたコンピュータプログラム製品であって、
スキャン演算命令に応答して、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのコンピュータコードを備えるコンピュータプログラム製品。
【請求項１９】
複数の処理要素を含む並列プロセッサアーキテクチャと、
前記並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するための命令と
を備える装置。
【請求項２０】
前記並列プロセッサアーキテクチャが、バスを介してメモリ及びディスプレイと通信したままの状態である、請求項１９に記載の装置。
【請求項１】
スキャン演算命令を受け取るステップと、
前記スキャン演算命令に応答して、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するステップと
を含む方法。
【請求項２】
前記スキャン演算が接頭部和スキャン演算を含む、請求項１に記載の方法。
【請求項３】
前記スキャン演算が包括的スキャン演算を含む、請求項１に記載の方法。
【請求項４】
前記スキャン演算が排他的スキャン演算を含む、請求項１に記載の方法。
【請求項５】
前記並列プロセッサアーキテクチャが前記処理要素間の調整のためのもの、請求項１に記載の方法。
【請求項６】
前記調整が、書き込まれる結果の宛先に関する調整を含む、請求項５に記載の方法。
【請求項７】
前記処理要素がそれぞれ、複数のスレッドを並列に実行する、請求項１に記載の方法。
【請求項８】
前記スキャン演算が、前記並列プロセッサアーキテクチャの複数の機能ユニットを使用して実施される、請求項１に記載の方法。
【請求項９】
前記機能ユニットが加算器を含む、請求項８に記載の方法。
【請求項１０】
前記機能ユニットがブール論理演算子を含む、請求項８に記載の方法。
【請求項１１】
前記機能ユニットが算術及び論理演算子を含む、請求項８に記載の方法。
【請求項１２】
前記並列プロセッサアーキテクチャが複数レベルの機能ユニットを含む、請求項８に記載の方法。
【請求項１３】
前記レベルの数が前記処理要素の数より小さい、請求項１２に記載の方法。
【請求項１４】
前記レベルの数が前記処理要素の数の対数より小さい、請求項１２に記載の方法。
【請求項１５】
前記並列プロセッサアーキテクチャが、マルチビット値の個々のビットのスキャンを個々に実施し、結果をビットシフトした後に前記個々のスキャンの結果を合計することによって前記マルチビット値に対する前記スキャン演算を実施する、請求項１に記載の方法。
【請求項１６】
前記並列プロセッサアーキテクチャが１つ又は複数の単一命令多重データプロセッサを含む、請求項１に記載の方法。
【請求項１７】
前記並列プロセッサアーキテクチャがグラフィックスプロセッサを含む、請求項１に記載の方法。
【請求項１８】
コンピュータ読取り可能媒体内に具体化されたコンピュータプログラム製品であって、
スキャン演算命令に応答して、複数の処理要素を備えた並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するためのコンピュータコードを備えるコンピュータプログラム製品。
【請求項１９】
複数の処理要素を含む並列プロセッサアーキテクチャと、
前記並列プロセッサアーキテクチャを使用して単一ビット値のシーケンスに対してスキャン演算を実施するための命令と
を備える装置。
【請求項２０】
前記並列プロセッサアーキテクチャが、バスを介してメモリ及びディスプレイと通信したままの状態である、請求項１９に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００９−１６９９３５（Ｐ２００９−１６９９３５Ａ）
【公開日】平成２１年７月３０日（２００９．７．３０）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−２６３１５８（Ｐ２００８−２６３１５８）
【出願日】平成２０年１０月９日（２００８．１０．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０１２６１３００）エヌヴィディア コーポレイション (166)
【Ｆターム（参考）】
【公開日】平成２１年７月３０日（２００９．７．３０）
【国際特許分類】
【出願番号】特願２００８−２６３１５８（Ｐ２００８−２６３１５８）
【出願日】平成２０年１０月９日（２００８．１０．９）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０１２６１３００）エヌヴィディア コーポレイション (166)
【Ｆターム（参考）】
[ Back to top ]