(57)【要約】【課題】  演算処理装置の演算速度を向上し、演算処理装置によるデータ処理の効率を向上する。【解決手段】  スレッドを並列に実行する複数の演算コアを有する演算処理装置の制御部が演算コアに、スレッドの所定数毎に、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行させ、リダクション演算により得られたデータを、アトミック処理により、対応する記憶領域内のデータに加えさせる。【選択図】    図１
2014106715.tif 000002
【特許請求の範囲】
【請求項１】
スレッドを並列に実行する複数の演算コアと、前記演算コアを制御する制御部とを有する演算処理装置の制御プログラムにおいて、
前記制御部が、
前記演算コアに、前記スレッドの所定数毎に、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行させ、
前記演算コアに、前記リダクション演算により得られたデータを、アトミック処理により、対応する記憶領域内のデータに加えさせることを特徴とする演算処理装置の制御プログラム。
【請求項２】
前記制御部が、
前記演算コアに、前記所定数のスレッドの１つを着目スレッドとして順次に選択させ、
前記着目スレッドがデータを書き込む記憶領域にデータを書き込むスレッドのいずれかに、前記着目スレッドのデータとの前記リダクション演算を実行させ、
前記所定数のスレッドの全てが前記着目スレッドとして選択された後、前記リダクション演算を実行したスレッドに、前記リダクション演算により得られたデータを、前記アトミック処理により、対応する記憶領域内のデータに加えさせることを特徴とする請求項１記載の演算処理装置の制御プログラム。
【請求項３】
前記制御部が、
前記演算コアに、前記着目スレッドがデータを書き込む記憶領域にデータを書き込むスレッドのうち前記着目スレッド以外のスレッドのいずれかに、動作を終了させることを特徴とする請求項２記載の演算処理装置の制御プログラム。
【請求項４】
前記制御部が、
前記演算コアに、演算の実行が可能な有効スレッドを前記着目スレッドとして順次に設定させ、
前記演算コアに、前記有効スレッドのデータの前記リダクション演算を実行させることを特徴とする請求項２または請求項３記載の演算処理装置の制御プログラム。
【請求項５】
スレッドを並列に実行する複数の演算コアと、前記演算コアを制御する制御部とを有する演算処理装置の制御方法において、
前記制御部が、
前記演算コアに、前記スレッドの所定数毎に、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行させ、
前記演算コアに、前記リダクション演算により得られたデータを、アトミック処理により、対応する記憶領域内のデータに加えさせることを特徴とする演算処理装置の制御方法。
【請求項６】
スレッドを並列に実行する複数の演算コアと、
前記演算コアに、前記スレッドの所定数毎に、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行させ、前記リダクション演算により得られたデータを、アトミック処理により、対応する記憶領域内のデータに加えさせる制御部を備えることを特徴とする演算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算処理装置の制御プログラム、演算処理装置の制御方法および演算処理装置に関する。
【背景技術】
【０００２】
ＧＰＵ（Graphics Processing Unit）等のアクセラレータは、並列に動作する数十から数千個の演算器や演算コアを含み、１つの命令で複数のデータ値を処理可能なＳＩＭＤ（Single Instruction Multiple Data）ユニットを有する。
【０００３】
結合法則と交換法則が成り立つリダクション演算は、演算の順序に依らず演算結果が得られるため、ＳＩＭＤユニット等を用いて並列処理が可能である。ここで、リダクション演算は、複数のデータ値を演算して１つのデータ値を求める演算であり、加算、乗算、最大値の計算、あるいは最小値の計算などを含む。
【０００４】
一方、データの演算結果によって次の演算先が決定されるヒストグラム計算等のリダクション演算は、アトミック処理を用いて演算結果を求めることが好ましい。アトミック処理は、記憶装置からデータを読み、加算などの演算を実行し、演算結果を記憶装置に書き込むまでの処理を、並列に動作する他のプロセスやスレッドに邪魔されずに実行するものである。
【０００５】
並列処理を実行可能なプロセッサにおけるリダクション演算の工夫は、以前から行われている（例えば、特許文献１参照。）。ＳＩＭＤユニットでは、項毎に書き込み先が変わるリダクション演算を効率よく行う工夫もなされている（例えば、特許文献２参照。）。並列度が数千を超えるような大規模な並列処理が可能なプロセッサにおいて、項毎に書き込み先が変わるリダクションを行うには、アトミック処理を利用する方法が考えられる。しかし、データを書き込む記憶領域へのアクセスが競合する場合、アトミック処理は逐次に実行されるため、効率が悪い。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００５−５１４６７８号公報
【特許文献２】特表２０１１−５１４５９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
記憶領域へのアクセスが競合するリダクション演算がアトミック処理により実行される場合、演算処理装置によるデータ処理の効率は、アトミック処理が発生しない場合に比べて低下する。
【０００８】
１つの側面では、本発明の目的は、従来に比べて、演算処理装置の演算速度を向上し、演算処理装置によるデータ処理の効率を向上することである。
【課題を解決するための手段】
【０００９】
一形態における演算処理装置の制御プログラム、演算処理装置の制御方法、および演算処理装置では、スレッドを並列に実行する複数の演算コアを有する演算処理装置の制御部が、演算コアに、スレッドの所定数毎に、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行させ、リダクション演算により得られたデータを、アトミック処理により、対応する記憶領域内のデータに加えさせる。
【発明の効果】
【００１０】
従来に比べて、演算処理装置の演算速度を向上でき、演算処理装置によるデータ処理の効率を向上できる。
【図面の簡単な説明】
【００１１】
【図１】一実施形態における演算処理装置の例を示す。
【図２】図１に示した演算処理装置の動作の例を示す。
【図３】別の実施形態における演算処理装置の例を示す。
【図４】図３に示した演算処理装置の動作の例を示す。
【図５】図３に示した共有メモリに登録される配列変数の例を示す。
【図６】図４に示したフローによるリダクション演算の実行例を示す。
【図７】図３に示したデータメモリに登録される配列変数の例を示す。
【図８】図４に示したフローを実行する制御プログラムの例を示す。
【図９】図８に示した関数ａｔｏｍｉｃａｄｄＷを用いてヒストグラムを作成する制御プログラムの例を示す。
【図１０】関数ａｔｏｍｉｃａｄｄを用いてヒストグラムを作成する制御プログラムの例を示す。
【図１１】図３に示した演算処理装置が搭載されるシステムの例を示す。
【図１２】図９および図１０に示した制御プログラムによるヒストグラムの作成処理時間のビン数依存性を示す。
【図１３】図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムの別の例を示す。
【図１４】図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムのさらなる別の例を示す。
【図１５】図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムのさらなる別の例を示す。
【発明を実施するための形態】
【００１２】
以下、図面を用いて実施形態を説明する。
【００１３】
図１は、一実施形態における演算処理装置の例を示す。例えば、演算処理装置は、ＧＰＵである。ＧＰＵは、汎用的なデータ処理を実行可能なＧＰＧＰＵ（General Purpose Graphics Processing Unit）でもよい。
【００１４】
例えば、演算処理装置は、実行ユニット１０、データメモリ２０および命令メモリ３０を有する。実行ユニット１０は、スレッドを並列に実行する複数の演算コア１２および演算コア１２の動作を制御する制御部１４を有する。例えば、制御部１４は、演算コア１２のスケジューラとして機能し、命令メモリ３０に格納された制御プログラムに基づいて実行される処理を、処理の最小単位である複数のスレッドに分割し、分割したスレッドを演算コアに並列に実行させる。すなわち、制御部１４は、演算コア１２に制御プログラムを実行させる。なお、複数の演算コア１２の数に対応する所定数のスレッドは、共通の命令に基づいて複数の演算コア１２により並列に実行されるため、命令単位で同期が保証される。
【００１５】
データメモリ２０は、予め割り当てられた複数の記憶領域ＭＡを有する。演算コア１２による演算で得られたデータは、各記憶領域ＭＡに格納されたデータに加えられる。例えば、記憶領域ＭＡへのデータの足し込みは、リードモディファイライト手法により、記憶領域ＭＡからのデータの読み出し、データの修正（演算）および修正したデータの記憶領域ＭＡへの書き込みにより実行される。複数の演算コア１２による１つの記憶領域ＭＡへのデータの足し込みが競合すると、データが破壊されるおそれがある。このため、記憶領域ＭＡへのデータの足し込みは、競合によるデータの破壊を避けられるアトミック処理で実行される。以下の説明では、リードモディファイライトによるデータの記憶領域への足し込みは、書き込みとも称する。
【００１６】
図２は、図１に示した演算処理装置の動作の例を示す。図２に示したフローは、制御部１４が命令メモリ３０に格納されたプログラムを演算コア１２に実行させることで実現される。すなわち、図２は、演算処理装置の制御プログラムの内容および演算処理装置の制御方法の内容を示す。
【００１７】
まず、ステップＳ１０において、実行ユニット１０は、制御プログラムにより実行される複数のスレッドのうち所定数のスレッドを選択する。図３以降の実施形態では、制御プログラムの実行に使用される複数のスレッドの塊をスレッド群またはブロックと称し、選択される所定数のスレッドの塊をサブスレッド群またはワープと称する。
【００１８】
次に、ステップＳ２０において、実行ユニット１０は、所定数のスレッドの中から、データを書き込む記憶領域ＭＡが同じスレッドの有無を検索する。データを書き込む記憶領域ＭＡが複数のスレッドで同じ場合、ステップＳ３０において、実行ユニット１０は、データを書き込む記憶領域が同じスレッドのデータのリダクション演算を実行する。例えば、データを書き込む記憶領域ＭＡが３以上のスレッドで同じ場合、２つのスレッドの一方に、スレッドの他方のデータとのリダクション演算を実行させる動作が繰り返される。
【００１９】
なお、この実施形態および図３以降の実施形態で使用するリダクション演算は、結合法則と交換法則が成り立つ複数項の１種類の演算子による演算とする。この種のリダクション演算は、項を演算する順序に依らず、答えを求めることができる。演算は、加算だけでなく、乗算や最大値を求める演算、最小値を求める演算などでも、リダクション演算となりうる。
【００２０】
ステップＳ４０において、実行ユニット１０は、選択した所定数のスレッドの中に、ステップＳ２０の判定を実行していないスレッドがある場合、ステップ２０の処理に移行する。また、実行ユニット１０は、所定数のスレッドの全てがステップＳ２０の判定を完了した場合、ステップＳ５０の処理に移行する。
【００２１】
ステップＳ５０において、実行ユニット１０は、ステップＳ３０によるリダクション演算の実行により得られたデータを、アトミック処理により、対応する記憶領域ＭＡ内に格納されたデータに加える。例えば、アトミック処理による記憶領域ＭＡへのデータの書き込みは、リダクション演算の演算結果を保持したスレッドにより実行される。
【００２２】
図２に示したフローにより、アトミック処理により所定数のスレッドの各々のデータを記憶領域ＭＡ内に格納されたデータに順次に加える場合に比べて、アトミック処理の回数を減らすことができる。例えば、制御部１４が、所定数のスレッドの塊を切り替えながら、図２の動作を並列に実行する場合にも、アトミック処理の回数を減らすことができる。この結果、従来に比べて、演算処理装置の演算速度を向上でき、演算処理装置によるデータ処理の効率を向上できる。
【００２３】
図２に示したフローにより処理される演算の例として、例えば、式（１）がある。式（１）では、データを加える記憶領域ＭＡは、データ値によって決定される。式（１）において、”Ｓｉ”はｉ番目の記憶領域ＭＡに加えられるデータを示す。ヒストグラムでは、”ｉ”はビン番号に対応し、”Ｓｉ”は１つのビンの高さ（頻度）に対応する。”ａｊ”はｊ番目のデータであり、”ｆ（ａｊ）”は、データを加える記憶領域ＭＡを”ａｊ”から求める関数である。例えば、身長のヒストグラムの生成では、”ａｊ”は身長データである。
【００２４】
【数１】
2014106715.tif 000003
【００２５】
式（１）に示すような処理の並列化は、従来、アトミック処理を用いて対応していた。この実施形態では、式（１）に示すような処理を並列化する際に、リダクション演算で処理可能な演算を、アトミック処理の前に実行する。これにより、従来に比べて、アトミック処理の回数を減らすことができ、アトミック処理の競合頻度を下げることができる。この結果、従来に比べて、演算処理装置の演算速度を向上でき、演算処理装置によるデータ処理の効率を向上できる。
【００２６】
図３は、別の実施形態における演算処理装置の例を示す。例えば、演算処理装置は、ＧＰＵである。演算処理装置は、スレッド制御装置１００、実行ユニット２００、メモリ制御装置３００、データメモリ４００および命令メモリ５００を有する。例えば、演算処理装置は、基板に搭載された複数の半導体チップや記憶装置を含み、スレッド制御装置１００、実行ユニット２００、メモリ制御装置３００、データメモリ４００および命令メモリ５００は、半導体チップのいずれかに搭載される。なお、スレッド制御装置１００、実行ユニット２００、メモリ制御装置３００、データメモリ４００および命令メモリ５００は、単一の半導体チップに搭載されてもよい。
【００２７】
スレッド制御装置１００は、上位のコントローラから制御プログラムの実行の指示を受け、複数のスレッドを含むスレッド群を実行する実行ユニット２００を決定し、実行を決定した実行ユニット２００にスレッド群を投入する。スレッド制御装置１００は、スレッド群を実行可能な実行ユニット２００がない場合、スレッド群の実行ユニット２００への投入を待つ。そして、スレッド制御装置１００は、実行中のスレッド群を完了した実行ユニット２００に、待ち状態のスレッド群を投入する。なお、スレッド制御装置１００は、実行ユニット２００によるスレッドの実行能力に余裕がある場合、複数のスレッド群を１つの実行ユニット２００に投入してもよい。
【００２８】
各実行ユニット２００は、スレッドスケジューラ２１０、複数の演算コア２２０、レジスタファイル２３０、ロード／ストアユニット２４０および共有メモリ２５０を有する。スレッドスケジューラ２１０は、スレッド制御装置１００から受けるスレッド群中のスレッドを演算コア２２０に割り当てる機能と、複数の演算コア２２０により並列に実行されるスレッドを、所定数のクロックサイクル毎に切り替える機能を有する。なお、図３では、演算処理装置は、４つの実行ユニット２００を有するが、少なくとも１つの実行ユニット２００を有すればよい。
【００２９】
スレッドスケジューラ２１０は、スレッド制御装置１００から投入されるスレッド群を、所定数のスレッドを含むサブスレッド群単位で演算コア２２０に実行させる。例えば、サブスレッド群は、実行ユニット２００内の演算コア２２０の数と同じ数のスレッドを有し、共通の命令ポインタを持つ。このように、サブスレッド群内のスレッドの数は、ハードウエアに依存して決まる。これに対して、スレッド群内のスレッドの数は、ユーザにより設計される制御プログラムに依存して決まる。このため、スレッド群のスレッド数が、サブスレッド群のスレッド数より少ない場合、無効なスレッドを実行する演算コア２２０が発生する。無効なスレッドを実行する演算コア２２０による演算結果は、制御プログラムによりマスクされる。
【００３０】
そして、サブスレッド群のスレッドは、スレッドスケジューラ２１０が命令メモリ５００からフェッチする命令に基づいて、演算コア２２０により並列に実行される。サブスレッド群のスレッドは、共通の命令に基づいて演算コア２２０により並列に実行されるため、命令単位で同期が保証される。ここで、複数の実行ユニット２００のスレッドスケジューラ２１０と命令メモリ５００は、共通の信号線で接続されてもよく、互いに独立の信号線で接続されてもよい。
【００３１】
この例では、各実行ユニット２００は、８つの演算コア２２０を有するが、演算コア２２０の数は、実行ユニット２００毎に２つ以上であればよい。後述するように、スレッドを示すスレッド番号等を求めるビット演算を容易にするために、サブスレッド群中のスレッド数を、２のｎ乗個（ｎは正の整数）とすることが好ましい。
【００３２】
また、スレッドスケジューラ２１０は、演算コア２２０が使用するレジスタファイル２３０内のレジスタを割り当てる機能を有する。さらに、スレッドスケジューラ２１０は、ロード／ストアユニット２４０を制御することで、レジスタファイル２３０、共有メモリ２５０およびデータメモリ４００との間でデータを相互に転送させる機能を有する。
【００３３】
レジスタファイル２３０は、複数のレジスタを有する。例えば、レジスタは、演算コア２２０毎に割り当てられ、１つの演算コア２２０に割り当てられたレジスタは、他の演算コア２２０から参照されない。処理性能の点から、サブスレッド群中のスレッドすべてに同時、ないし数サイクルで処理できるように、レジスタファイル２３０の内部は並列化されていることが望ましい。ロード／ストアユニット２４０を介して共有メモリ２５０からレジスタに転送されたデータは、対応する演算コア２２０により演算され、演算結果は、ロード／ストアユニット２４０を介して共有メモリ２５０に書き込まれる。すなわち、各実行ユニット２００内の複数の演算コア２２０は、レジスタファイル２３０内の対応するレジスタにそれぞれ保持されたデータを用いて、スレッドスケジューラ２１０によりフェッチされた命令を並列に実行する。
【００３４】
ロード／ストアユニット２４０は、スレッドスケジューラ２１０によりフェッチされる命令に基づいて、レジスタファイル２３０と共有メモリ２５０との間でデータを転送し、あるいは、共有メモリ２５０とデータメモリ４００との間でデータを転送する。例えば、共有メモリ２５０は、スレッド群毎に領域が割り当てられ、１つのスレッド群に割り当てられた領域は、別のスレッド群から参照されない。共有メモリ２５０は、実行ユニット２００の内部に配置されるため、実行ユニットの外部に配置されるデータメモリ４００に比べてアクセス時間は短い。尚、ロード／ストアユニット２４０は、内部が並列化されていてもよい。この場合、サブスレッド群中のスレッドから同時に異なるアドレスに対してメモリアクセスがあった場合、同時に処理することが可能となる。
【００３５】
メモリ制御装置３００は、データメモリ４００のアクセスを制御し、データメモリ４００から読み出したデータをロード／ストアユニット２４０に出力し、ロード／ストアユニット２４０から受けたデータをデータメモリ４００に書き込む。なお、複数の実行ユニット２００のロード／ストアユニット２４０とメモリ制御装置３００とは、共通の信号線で接続されてもよく、互いに独立の信号線で接続されてもよい。
【００３６】
データメモリ４００および命令メモリ５００は、単一の半導体メモリ装置内に共存されてもよく、別々の半導体メモリ装置に分けてもよい。また、データメモリ４００が複数の半導体メモリ装置を含む場合、演算処理装置は、半導体メモリ装置のアクセスをそれぞれ制御する複数のメモリ制御装置を有してもよい。さらに、演算処理装置は、データキャッシュや命令キャッシュを有してもよい。
【００３７】
なお、図３に示した演算処理装置として、例えば、ＮＶＩＤＩＡ（登録商標）社のＧＰＵが利用可能である。この場合、実行ユニット２００は、ＳＭ（Streaming Multiprocessor）に対応し、スレッド群およびサブスレッド群は、ブロックおよびワープにそれぞれ対応する。
【００３８】
図４は、図３に示した演算処理装置の動作の例を示す。図４は、アトミック処理の回数を従来に比べて減らし、リダクション演算を効率的に実行する制御プログラムのフローの一例である。図４のフローは、実行ユニット２００のスレッドスケジューラ２１０が命令をフェッチすることにより、複数の演算コア２２０で並列に実行される。換言すれば、図４のフローは、サブスレッド群ＳＴのスレッド毎に実行される。図４において、太枠で示す処理は、共有メモリ２５０へのアクセスの発生、またはサブスレッド群内での他のスレッドによる参照が発生することを示す。
【００３９】
まず、ステップＳ１００において、実行ユニット２００は、リダクション演算で使用するデータを格納するデータ格納領域を、共有メモリ２５０上に配列変数ｄａｔａＢｕｆｆｅｒ（図５）として登録する。また、実行ユニット２００は、データを書き込むデータメモリ４００上の記憶領域を示すアドレス（以下、書き込みアドレスとも称する）を格納するアドレス格納領域を、共有メモリ２５０上に配列変数ｏｆｆｓｅｔＢｕｆｆｅｒ（図５）として登録する。例えば、書き込みアドレスは、図７に示すヒストグラムの生成処理において、各ビンの値が格納される領域を示す。
【００４０】
この例では、サブスレッド群のスレッド数は、命令を実行する演算コア２２０の数と同じ”８”である。例えば、図５に示す各サブスレッド群ＳＴ（ＳＴ０、ＳＴ１、...）において、各スレッドのデータの相対的な格納位置および書き込みアドレスの相対的な格納位置は、配列変数の添え字を２進数値で表した場合に下位３ビットで表される。データおよび書き込みアドレスは、制御プログラム中の関数の引数として与えられる。例えば、書き込みアドレスは、図３に示したデータメモリ４００の所定の記憶領域を示す。
【００４１】
次に、ステップＳ１０２において、実行ユニット２００は、サブスレッド群ＳＴの各スレッドを示す番号を取得し、領域ｔＩＤＢｌｏｃｋに格納する。例えば、領域ｔＩＤＢｌｏｃｋは、スレッド毎にレジスタファイル２３０内に割り当てられる。例えば、サブスレッド群ＳＴ１の１番目のスレッドは、領域ｔＩＤＢｌｏｃｋに”０”が格納され、サブスレッド群ＳＴ１の６番目のスレッドは、領域ｔＩＤＢｌｏｃｋに”５”が格納される。
【００４２】
次に、ステップＳ１０４において、実行ユニット２００は、実行するサブスレッド群ＳＴの先頭のスレッド番号を取得する。先頭のスレッド番号は、スレッド群内のスレッド番号であり、各配列変数ｄａｔａＢｕｆｆｅｒ、ｏｆｆｓｅｔＢｕｆｆｅｒの添え字と同じ値である。例えば、図５に示すように、サブスレッド群ＳＴ１の先頭のスレッド番号は”８”である。
【００４３】
次に、ステップＳ１０６において、実行ユニット２００は、実行するサブスレッド群ＳＴにおいてリダクション演算の結果を格納する変数ｓｕｍを”０”に初期化する。例えば、変数ｓｕｍは、実行するサブスレッド群ＳＴのスレッド毎にレジスタファイル２３０内に割り当てられる。
【００４４】
次に、ステップＳ１０８において、実行ユニット２００は、サブスレッド群ＳＴ内で演算の実行が可能なスレッド（以下、有効スレッドと称する）を求める。有効スレッドを除くスレッドは、リダクション演算を実行しないスレッド（以下、無効スレッドと称する）である。実行ユニット２００は、有効スレッドを示す情報を、共有メモリ２５０内の識別領域ａｃｔｉｖｅ（図５）に格納する。図５に示すように、識別領域ａｃｔｉｖｅには、例えば、サブスレッド群のスレッドにそれぞれ対応し、ビット値”１”が有効スレッドを示し、ビット値”０”が無効スレッドを示すビットが割り当てられる（この例では、８ビット）。
【００４５】
次に、ステップＳ１１０において、実行ユニット２００は、未処理の有効スレッドの有無を判定する。例えば、実行ユニット２００は、識別領域ａｃｔｉｖｅにビット値”１”が格納された場合に未処理の有効スレッドがあると判断し、識別領域にビット値”１”が格納されていない場合に未処理の有効スレッドがなくなったと判断する。未処理の有効スレッドがある場合、ステップＳ１１２からステップＳ１２０の処理が実行され、未処理の有効スレッドがない場合、ステップＳ１２２の処理が実行される。
【００４６】
ステップＳ１１２において、実行ユニット２００は、未処理の有効スレッドのスレッド番号の先頭番号（すなわち、未処理の有効スレッドのうち、最も小さいスレッド番号）を求め、求めた値を変数ｒＩＤに格納する。以降では、変数ｒＩＤは、着目スレッド番号ｒＩＤとも称する。変数ｒＩＤは、実行するサブスレッド群ＳＴのスレッド毎にレジスタファイル２３０内に割り当てられる。
【００４７】
未処理の有効スレッドの１つを着目スレッドｒＩＤに設定するステップＳ１１２では、演算の実行が許可されない無効スレッドは着目スレッドｒＩＤに設定されない。これにより、無効なデータのリダクション演算の実行を避けることができる。
【００４８】
次に、ステップＳ１１４において、実行ユニット２００は、着目スレッド番号ｒＩＤにより示されるスレッドに対応する識別領域ａｃｔｉｖｅのビット値を”０”に書き換えて、着目スレッドを処理済みのスレッドとする。
【００４９】
次に、ステップＳ１１６において、実行ユニット２００は、各有効スレッドの書き込みアドレスと、着目スレッドの書き込みアドレスとが同じか否かを判断する。書き込みアドレスが互いに同じ場合、ステップＳ１１８の処理が実行される。書き込みアドレスが互いに異なる場合、ステップＳ１１０の処理に戻る。
【００５０】
ステップＳ１１８において、実行ユニット２００は、書き込みアドレスが互いに同じ場合に、各有効スレッドの番号が、着目スレッド番号ｒＩＤより大きいか否かを判断する。有効スレッドの番号が、着目スレッド番号ｒＩＤより大きい場合、その有効スレッドはリダクション演算を実行するスレッドでないと判定され、処理は終了する。処理が終了したスレッドは、有効スレッドとして扱われ、着目スレッドとしても扱われるが、ステップＳ１２２の処理を実行しない。
【００５１】
有効スレッドの番号が、着目スレッド番号ｒＩＤ以下の場合、その有効スレッドはリダクション演算を実行するスレッド（以下、演算スレッドとも称する）であると判定され、ステップＳ１２０の処理が実行される。
【００５２】
ステップＳ１２０において、実行ユニット２００は、演算スレッドにリダクション演算を実行させ、着目スレッド番号ｒＩＤのスレッドのデータを演算スレッドの変数ｓｕｍに加える。ステップＳ１２０の後、処理はステップＳ１１０に戻る。なお、図１および図２と同様に、この実施形態で使用するリダクション演算も、結合法則と交換法則が成り立つ複数項の１種類の演算子による演算である。
【００５３】
一方、未処理の有効スレッドがなくなった場合、ステップＳ１２２において、実行ユニット２００は、アトミック加算を実行し、データが格納された変数ｓｕｍの値を、データメモリ４００内の書き込みアドレスが示す領域に加える。
【００５４】
図５は、図３に示した共有メモリ２５０に登録される配列変数の例を示す。上述したように、リダクション演算で使用するデータは、データ格納領域の配列変数ｄａｔａＢｕｆｆｅｒにより示される領域に格納される。サブスレッド群ＳＴ１に割り当てられた配列変数ｄａｔａＢｕｆｆｅｒ［８］−ｄａｔａＢｕｆｆｅｒ［１５］の値Ａ−Ｈは、データの例を示す。サブスレッド群ＳＴ１に割り当てられたｏｆｆｓｅｔＢｕｆｆｅｒ［８］−ｏｆｆｓｅｔＢｕｆｆｅｒ［１５］の値ａ、ｂ、ｃは、書き込みアドレスを示す。データＡ−Ｈおよびアドレス値ａ、ｂ、ｃは、図６の説明で使用する。
【００５５】
図６は、図４に示したフローによるリダクション演算の実行例を示す。この例では、サブスレッド群ＳＴ１は、スレッド番号ｔＩＤＢｌｏｃｋ（＝０−７）で示される８つのスレッドを含む。ループ回数は、図４のステップＳ１１０における”Ｙｅｓ”の分岐回数である。この例では、５番目のスレッド（ｔＩＤＢｌｏｃｋ＝４）は無効スレッドであるため、サブスレッド群ＳＴ１は７つの有効スレッドを含み、ループ回数は７回である。
【００５６】
実線のスレッドは有効スレッドを示し、破線のスレッドは無効スレッドを示す。太枠のスレッドは、各ループにおいて、未処理の有効スレッドのうち、スレッド番号ｔＩＤＢｌｏｃｋが最も小さいスレッドであり、図４のステップＳ１１２の変数ｒＩＤで示される着目スレッドである。図６に示すように、ループ毎に、所定数のスレッド中の有効スレッドの１つが、スレッド番号ｔＩＤＢｌｏｃｋの小さい順に着目スレッドとして選択される。
【００５７】
網掛けのスレッドは、図４に示したステップＳ１１８において”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立し、処理が終了したスレッドである。上述したように、処理が終了したスレッドは、有効スレッドとして扱われ、着目スレッドとしても扱われるが、図４に示したステップＳ１２０とステップＳ１２２の処理を実行しない。各スレッドが扱うデータおよびリダクション演算の結果を書き込む領域を示すアドレス（すなわち、書き込みアドレス）は、図５に示す値とする。
【００５８】
まず、１回目のループでは、図４のステップＳ１１６において、７つの有効スレッドの書き込みアドレスと、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝０）の書き込みアドレス（＝ａ）とが比較される。この例では、着目スレッドの書き込みアドレスと同じ書き込みアドレスを有するスレッドは、着目スレッド自身である。このため、着目スレッドは、図４のステップＳ１１８の処理を実行する。
【００５９】
ステップＳ１１８において、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝０）は、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立しないため、ステップＳ１２０を実行し、変数ｓｕｍに自身のデータ”Ａ”を加える（図６（ａ））。すなわち、スレッド（ｔＩＤＢｌｏｃｋ＝０）は、リダクション演算を実行する。着目スレッドを除く他の有効スレッドは、書き込みアドレスが着目スレッドの書き込みアドレスと異なるため、１回目のループは終了する。
【００６０】
次に、２回目のループでは、７つの有効スレッドの書き込みアドレスと、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝１）の書き込みアドレス（＝ｂ）とが比較される。そして、１回目のループと同様に、着目スレッド自身は、ステップＳ１２０によりリダクション演算を実行し、変数ｓｕｍに自身のデータ”Ｂ”を加える（図６（ｂ））。着目スレッドの書き込みアドレスと同じ書き込みアドレスを有する６番目のスレッド（ｔＩＤＢｌｏｃｋ＝５）は、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立するため、網掛けで示すように、処理を終了する（図６（ｃ））。処理を終了したスレッドは、図４に示したループを終了するため、ステップＳ１１０からステップＳ１２２の処理を実行しない。
【００６１】
すなわち、着目スレッドの書き込みアドレスと同じ書き込みアドレスを有するスレッドで、スレッド番号が着目スレッドのスレッド番号より大きいスレッドは、動作を終了する。これにより、別のスレッドにデータを既に加えられたスレッドは、図４のステップＳ１２２のアトミック処理を実行しない。したがって、複数のスレッドが図４に示したフローを並列に実行する場合にも、ステップＳ１２２のアトミック処理により、１つのデータが複数のスレッドによって重複して加えられることはない。
【００６２】
次に、３回目のループでは、１回目および２回目のループと同様に、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝２）は、リダクション演算を実行し、変数ｓｕｍに自身のデータ”Ｃ”を加える（図６（ｄ））。また、２回目のループと同様に、着目スレッドの書き込みアドレスと同じ書き込みアドレスを有する４番目、７番目、８番目のスレッド（ｔＩＤＢｌｏｃｋ＝３、６、７）は、ステップＳ１１８において、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立する。このため、４番目、７番目、８番目のスレッドは、網掛けで示すように処理を終了し、これ以降、ステップＳ１１０からステップＳ１２２の処理を実行しない（図６（ｅ、ｆ、ｇ））。
【００６３】
次に、４回目のループでは、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝３）の書き込みアドレスと同じ書き込みアドレスを有するスレッドは、３番目、４番目、７番目、８番目のスレッド（ｔＩＤＢｌｏｃｋ＝２、３、６、７）である。３番目のスレッド（ｔＩＤＢｌｏｃｋ＝２）は、ステップＳ１１８において、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立しないため、ステップＳ１２０によりリダクション演算を実行し、変数ｓｕｍ（＝Ｃ）に着目スレッドのデータ”Ｄ”を加える（図６（ｈ））。
【００６４】
すなわち、着目スレッドの書き込みアドレスと同じ書き込みアドレスを有するスレッドが複数存在する場合、スレッド番号が最も小さいスレッドが、着目スレッドのデータとのリダクション演算を実行し、ステップＳ１２２のアトミック処理を実行する。また、これにより、複数のスレッドが図４に示したフローを並列に実行する場合にも、ステップＳ１２２のアトミック処理により、１つのデータが複数のスレッドによって重複して加えられることはない。４番目のスレッドである着目スレッドは、３回目のループで処理を終了したため、ステップＳ１１０からステップＳ１２２の処理を実行せず、ステップＳ１２０による変数ｓｕｍの加算を実行しない（図６（ｉ））。
【００６５】
次に、５回目のループでは、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝５）の書き込みアドレスと同じ書き込みアドレスを有するスレッドは、２番目のスレッド（ｔＩＤＢｌｏｃｋ＝１）である。２番目のスレッドは、ステップＳ１１８において、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立しないため、ステップＳ１２０によりリダクション演算を実行し、変数ｓｕｍ（＝Ｂ）に着目スレッドのデータ”Ｆ”を加える（図６（ｊ））。６番目のスレッドである着目スレッドは、３回目のループで処理を終了したため、ステップＳ１１０からステップＳ１２２の処理を実行せず、ステップＳ１２０による変数ｓｕｍの加算を実行しない（図６（ｋ））。
【００６６】
次に、６回目のループでは、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝６）の書き込みアドレスと同じ書き込みアドレスを有するスレッドは、３番目、４番目、７番目、８番目のスレッド（ｔＩＤＢｌｏｃｋ＝２、３、６、７）である。３番目のスレッド（ｔＩＤＢｌｏｃｋ＝３）は、ステップＳ１１８において、”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立しないため、ステップＳ１２０によりリダクション演算を実行し、変数ｓｕｍ（＝Ｃ＋Ｄ）に着目スレッドのデータ”Ｇ”を加える（図６（ｌ））。
【００６７】
４番目のスレッドおよび着目スレッドである７番目のスレッドは、３回目のループで処理を終了したため、ステップＳ１２０による変数ｓｕｍの加算を実行しない（図６（ｍ、ｎ））。換言すれば、着目スレッドと同じ書き込みアドレスのスレッドのうち、スレッド番号が最も小さいスレッド（ｔＩＤＢｌｏｃｋ＝２）が、着目スレッドのデータとのリダクション演算を実行する。８番目のスレッドは、３回目のループで処理を終了したため、ステップＳ１２０による変数ｓｕｍの加算を実行しない。
【００６８】
次に、７回目のループでは、着目スレッド（ｒＩＤ＝ｔＩＤＢｌｏｃｋ＝７）の書き込みアドレスと同じ書き込みアドレスを有するスレッドは、３番目、４番目、７番目、８番目のスレッド（ｔＩＤＢｌｏｃｋ＝２、３、６、７）である。３番目のスレッドは、ステップＳ１１８において”ｒＩＤ＜ｔＩＤＢｌｏｃｋ”が成立しないため、ステップＳ１２０によりリダクション演算を実行し、変数ｓｕｍ（＝Ｃ＋Ｄ＋Ｇ）に着目スレッドのデータ”Ｈ”を加える（図６（ｏ））。４番目、７番目のスレッドおよび着目スレッドである８番目のスレッドは、３回目のループで処理を終了したため、ステップＳ１２０による変数ｓｕｍの加算を実行しない。（図６（ｐ、ｑ、ｒ））。
【００６９】
以上の処理により、７つのデータＡ、Ｂ、Ｃ、Ｄ、Ｆ、Ｇ、Ｈは、アトミック加算を実行することなく書き込みアドレス毎に加算され、１番目、２番目、３番目のスレッドの変数ｓｕｍとして保持される。この後、３つのスレッドは、図４に示したステップＳ１２２により、アトミック加算をそれぞれ実行し、各々の変数ｓｕｍを、データメモリ４００内の書き込みアドレスで指定される領域に書き込む。図６に示した例では、アトミック加算の回数を、スレッド毎にアトミック加算を実行する場合の７回から、衝突のない３回に減らすことができる。この結果、従来に比べて、演算処理装置の演算速度を向上でき、演算処理装置によるデータ処理の効率を向上できる。
【００７０】
図７は、図３に示したデータメモリ４００に登録される配列変数の例を示す。ｂａｓｅは、配列の先頭アドレスを示し、ｏｆｆｓｅｔは、データを加える記憶領域のインデックスを示す。ここでは、図６との対応を分かりやすくするために、ｏｆｆｓｅｔにより得られる値をアドレスａ、ｂ、ｃ（図６に示した書き込みアドレス）として示す。各書き込みアドレスで示される領域には、図６のリダクション演算により得られたデータＡ、Ｂ＋Ｆ、Ｃ＋Ｄ＋Ｇ＋Ｈが、アトミック加算によりそれぞれ書き込まれる。例えば、ヒストグラムの生成では、データＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈは、”１”であり、記憶領域に書き込まれたデータＡ、Ｂ＋Ｆ、Ｃ＋Ｄ＋Ｇ＋Ｈにより、各ビンの頻度が表される。
【００７１】
図４および図６に示した処理は、ヒストグラムに限らず、乗算処理、最大値を求める処理または最小値を求める処理に適用できる。書き込みアドレス毎にデータが乗じられる乗算処理では、図４のステップＳ１０６において、変数ｓｕｍが”１”に初期化され、図４のステップＳ１２０において、着目スレッドのデータが、リダクション演算により、演算スレッドの変数ｓｕｍに乗じられる。また、図６の（ａ）、（ｂ）、（ｄ）では、リダクション演算により、着目スレッドの変数ｓｕｍ（＝１）に、自身のデータが乗じられる。さらに、図６の（ｈ）、（ｊ）、（ｌ）、（ｏ）では、着目スレッドｒＩＤと同じ書き込みアドレスのスレッドのうち、スレッド番号が最も小さいスレッドの変数ｓｕｍに、着目スレッドのデータが乗じられる。
【００７２】
書き込みアドレス毎にデータの最大値を求める処理では、図４のステップＳ１０６において、変数ｓｕｍが設定可能な最小値に初期化され、図４のステップＳ１２０において、リダクション演算により、演算スレッドの変数ｓｕｍと着目スレッドのデータのうち大きい方が変数ｓｕｍに設定される。また、図６の（ａ）、（ｂ）、（ｄ）では、リダクション演算により、着目スレッドの変数ｓｕｍ（ステップＳ１０６で設定された最小値）が着目スレッドのデータに置き換えられる。さらに、図６の（ｈ）、（ｊ）、（ｌ）、（ｏ）では、着目スレッドｒＩＤと同じ書き込みアドレスのスレッドのうち、スレッド番号が最も小さいスレッドの変数ｓｕｍと着目スレッドのデータのうち大きい方が変数ｓｕｍに設定される。
【００７３】
書き込みアドレス毎にデータの最小値を求める処理では、図４のステップＳ１０６において、変数ｓｕｍが設定可能な最大値に初期化され、図４のステップＳ１２０において、リダクション演算により、演算スレッドの変数ｓｕｍと着目スレッドのデータのうち小さい方が変数ｓｕｍに設定される。また、図６の（ａ）、（ｂ）、（ｄ）では、リダクション演算により、着目スレッドの変数ｓｕｍ（ステップＳ１０６で設定された最大値）が着目スレッドのデータに置き換えられる。さらに、図６の（ｈ）、（ｊ）、（ｌ）、（ｏ）では、着目スレッドｒＩＤと同じ書き込みアドレスのスレッドのうち、スレッド番号が最も小さいスレッドの変数ｓｕｍと着目スレッドのデータのうち小さい方が変数ｓｕｍに設定される。
【００７４】
図８は、図４に示したフローを実行する制御プログラムの例を示す。図８は、ＮＶＩＤＩＡ社により提供されたプログラム開発環境であるＣＵＤＡ（登録商標；Compute Unified Device Architecture）を用いて記述した。図８の左側に示したステップ番号Ｓ１００−Ｓ１２２は、対応する図４の処理を示す。図８では、倍精度浮動小数点のデータのリダクション演算を実行する。なお、ＮＶＩＤＩＡ社のＧＰＵでは、スレッド群はブロックと称され、サブスレッド群はワープと称される。このため、以下では、スレッド群をブロックと称し、サブスレッド群をワープと称する場合がある。
【００７５】
１−２行目の記述は、関数ヘッダであり、”＿＿ｄｅｖｉｃｅ＿＿”は、ＧＰＵにより実行される関数で、ＧＰＵで実行する関数から呼び出し可能であることを示す。”ｂａｓｅ”、”ｏｆｆｓｅｔ”は、図７で説明したように、図３のデータメモリ４００に割り当てられる配列の先頭アドレスと、データを加える記憶領域を示すインデックスとをそれぞれ示す。”ｄａｔａＢｕｆｅｒ”、”ｏｆｆｓｅｔＢｕｆｆｅｒ”は、図５で説明したように、共有メモリ２５０に割り当てられるデータを格納する配列変数と、書き込みアドレスを格納する配列変数をそれぞれ示す。
【００７６】
図５に示したように、３行目の記述により、データが共有メモリ２５０に書き込まれ、４行目の記述により、書き込みアドレスが共有メモリ２５０に書き込まれる。”ｔｈｒｅａｄＩｄｘ．ｘ”は、図５に配列を示す数値で示したように、ブロック（スレッド群）内のスレッド番号（通し番号）を示す。”ｔｈｒｅａｄＩｄｘ．ｘ”の”．ｘ”は、スレッドが、ｘ方向（一次元）に配置されることを示す。スレッドがｘ方向、ｙ方向、ｚ方向の三次元で配置される場合、ブロック内のスレッド番号は、式（２）により取得される。式（２）において、”ｂｌｏｃｋＤｉｍ．ｘ”、”ｂｌｏｃｋＤｉｍ．ｙ”、”ｂｌｏｃｋＤｉｍ．ｚ”は、３次元で示されるブロックのｘ方向、ｙ方向、ｚ方向の大きさを示す。式（２）において、”＊”は、乗算を示す。
（（（ｔｈｒｅａｄＩｄｘ．ｚ＊ｂｌｏｃｋＤｉｍ．ｙ）＋ｔｈｒｅａｄＩｄｘ．ｙ）＊ｂｌｏｃｋＤｉｍ．ｘ）＋ｔｈｒｅａｄＤｉｘ．ｘ  ‥‥（２）
５行目の記述により、スレッド番号をワープのサイズ”ｗａｒｐＳｉｚｅ−１”とビット演算することで、ワープ内でのスレッド番号がそれぞれ求められる。６行目の記述により、ワープ内の先頭のスレッド番号が求められる。
【００７７】
７行目の記述では、２０行目の記述を簡単にするために、共有メモリ２５０内のデータを格納する領域の先頭アドレスをｗＤＡＴＡと定義する。８行目の記述では、１６行目の記述を簡単にするために、共有メモリ２５０内の書き込みアドレスを格納する領域の先頭アドレスをｗＡｄｄｒと定義する。
【００７８】
１０行目の記述により、各スレッドの変数ｓｕｍが”０”に初期化される。１１行目の記述により、ワープ内の有効スレッドが求められ、共有メモリ２５０内の識別領域ａｃｔｉｖｅに格納される。ここで、”＿＿ｂａｌｌｏｔ（ｔｒｕｅ）”は、有効スレッドのビット値＝”１”または無効スレッドのビット値＝”０”を戻り値とするボート関数である。この関数の戻り値は、ワープ内のスレッド番号（図６に示した例では０から７）に対して下位から1ビットずつ割り当てられる。”＿＿ｂｒｅｖ”は、３２ビットの引数を取り、ビット値の配列を上位と下位とで反転させたものを戻り値とするビットリーバス関数である。
【００７９】
１２行目の記述では、１３行目からのループにおいて有効スレッドを１つずつ順に処理していく際に、図６に網掛けで示した処理済みのスレッドに対応するビットを”０”にリセットするためのマスク値ｍａｓｋの初期値を計算する。
【００８０】
１３行目の記述により、全ての有効スレッドが処理済みになるまでループが繰り返される。ここで、”＿＿ｐｏｐｃ（ａｃｔｉｖｅ）”は、未処理の有効スレッドの数を求めるポピュレーションカウント関数である。
【００８１】
１４行目の記述により、ワープ内における未処理の有効スレッドのうち、スレッド番号が最も小さいスレッドである着目スレッドが求められる。ここで、”＿＿ｃｌｚ（ａｃｔｉｖｅ）”は、３２ビットの正数を引数に取り、最も桁の大きいビットから連続する０の数を求めるカウントリーディングゼロ関数である。
【００８２】
１５行目の記述により、マスク値ｍａｓｋを着目スレッドの番号ｒＩＤ分右シフトした値を用いて、着目スレッドが処理済みにされる。１６行目の記述により、各有効スレッドの書き込みアドレスが、着目スレッドの書き込みアドレスｏｆｆｓｅｔと同じか否かが判定され、同じ場合（図４のステップＳ１１６の”Ｙｅｓ”）、１７行目の処理に移行される。
【００８３】
１７行目の記述により、各有効スレッドの番号が、着目スレッドの番号ｒＩＤより大きいか否かが判定される。有効スレッドの番号が、着目スレッドの番号ｒＩＤより大きい場合、当該有効スレッドが、リダクション加算を実行するスレッドではないと判定される。この場合、１８行目の記述により、関数の残りの処理がスキップされ、呼び出し元に戻され、処理が終了する。
【００８４】
有効スレッドの番号が、着目スレッドの番号ｒＩＤ以下の場合、当該有効スレッドがリダクション加算を実行するスレッド、すなわち、演算スレッドであると判定される。この場合、２０行目の記述により、当該有効スレッドのデータに着目スレッドのデータが加えられる。すなわち、書き込みアドレスが互いに同じデータを加算するリダクション加算が、ワープ内で実行される。
【００８５】
２３行目の記述により、ワープ内でリダクション加算されたデータが、関数ａｔｏｍｉｃＡｄｄを用いて、データメモリ４００内の所定の記憶領域に格納されたデータに加えられる。すなわち、２０行目の記述でリダクション加算によりワープ内で加算されたデータが、アトミック処理によりデータメモリ４００に書き込まれる。
【００８６】
２３行目の記述で呼び出される関数ａｔｏｍｉｃＡｄｄは、倍精度浮動小数点のアトミック加算命令である。関数ａｔｏｍｉｃＡｄｄが、倍精度浮動小数点でサポートされていない場合でも、６４ビット整数のアトミック比較交換命令である関数ａｔｏｍｉｃＣＡＳ（Compare And Swap）を利用できれば、この処理を実現することができる。この場合、関数ａｔｏｍｉｃＣＡＳは、関数ａｔｏｍｉｃＡｄｄを実現する記述内で使用される。関数ａｔｏｍｉｃＣＡＳを利用した倍精度浮動小数点の関数ａｔｏｍｉｃＡｄｄの記述は、「NVIDIA Co. CUDA C Programming Guide Version 4.2.: NVIDIA Co., 2012」に記載されている。
【００８７】
なお、図８では、ワープ（サブスレッド群ＳＴ）単位にリダクション加算を実行する例を説明したが、ブロック（スレッド群）単位でリダクション加算を実行することも考えられる。ブロック単位でリダクション加算を実行する場合、ワープ単位でリダクション加算を実行する場合に比べてアトミック加算の数を減らせる可能性がある。
【００８８】
また、図８では、有効スレッドをスキャンして、リダクション加算が実行されるが、ブロック単位でリダクション加算する場合には、図８と同様に、ブロック内部をスキャンすればよい。あるいは、まず図８の要領でワープ毎にスキャンとリダクション加算を行い、その後、ブロックでスキャンとリダクション加算を実行してもよい。
【００８９】
一方、スレッドはワープ単位で命令ポインタを持ち、ワープ単位で実行されるため、複数のワープを含むブロック単位でリダクション加算を実行する場合、同じ命令コードが実行されるとは限らない。また、ブロック単位でリダクション加算を実行する場合、共有メモリ２５０へのデータの書き込みの前後で”＿＿ｓｙｎｃｔｈｒｅａｄｓ（）”を用いてバリア同期が取られるが、分岐が発生した場合にロックする可能性がある。”＿＿ｓｙｎｃｔｈｒｅａｄｓ（）”は、ブロック内のスレッド間でバリア同期を取る関数であり、ブロック内の全ての有効スレッドが”＿＿ｓｙｎｃｔｈｒｅａｄｓ（）”で待ち合わせる。”＿＿ｓｙｎｃｔｈｒｅａｄｓ（）”を飛び越すものは、無効スレッドなので、影響しない。
【００９０】
これに対して、ワープ単位でリダクション加算を実行する場合、命令単位で同期が保証されるため、明示的なバリア同期が不要で、ロックの問題は生じない。
【００９１】
図９は、図８に示した関数ａｔｏｍｉｃａｄｄＷを用いてヒストグラムを作成する制御プログラムの例を示す。
【００９２】
１−３行目の記述は、関数ヘッダであり、”＿＿ｇｌｏｂａｌ＿＿”は、ＧＰＵにより実行される関数で、ＧＰＵの上位のコントローラであるホストプロセッサで実行する関数から呼び出し可能であることを示す。”ｄｓｔＤａｔａ”は、ヒストグラムとなる配列変数の先頭アドレスを示し、例えば、図７に示したアドレス値”ａ”に対応する。”ｎｕｍＢｉｎ”はヒストグラムのビン数を示し、”ｌｏｗｅｒ”は、ヒストグラムの分布の下限値を示し、”ｗｉｄｔｈ”は、ヒストグラムのビン幅（この例では、等幅）を示す。”ｓｒｃＤａｔａ”は、ヒストグラムの作成に使用する元データが格納される領域の先頭アドレスを示す。”ｎｕｍＤａｔａ”は、ヒストグラムを生成する元のデータの数を示す。”ｎｕｍＴｈｒｅａｄｓ”は、ヒストグラムの作成に使用するブロックのスレッド数を示す。
【００９３】
４−５行目の記述により、共有メモリ２５０上にデータを格納する配列変数ｄａｔａＢｕｆｆｅｒ（図５）と、書き込みアドレスを格納する配列変数ｏｆｆｓｅｔＢｕｆｆｅｒ（図５）が確保される。この例では、ブロック毎に１２８個の領域が確保される。例えば、１つのスレッド群は、図５に示したように、８個のスレッドを各々含む１６個のサブスレッド群ＳＴ（ワープ）を有する。
【００９４】
６行目の記述により、ブロック内の処理するスレッドの番号（通し番号）が変数ｘＩＤに代入される。なお、この例においても、ブロック内のスレッドは、ｘ方向（一次元）に配置される。７行目の記述により、スレッド番号が”ｎｕｍＴｈｒｅａｄｓ”未満である場合、処理するスレッドであると判断され、８−１０行目の処理が実行される。
【００９５】
８行目の記述により、スレッド番号がデータ数より小さい間、ループ用のカウンタ値ｏｆｆｓｅｔがストライド値ＭＡＩＭＵＭ＿ＴＨＲＥＡＤＳだけ増やされ、９−１０行目の処理が実行される。すなわち、ヒストグラムを作成するデータがストライド値ＭＡＸＩＭＵＭ＿ＴＨＲＥＡＤＳ毎に分けられ、その中のｘＩＤ番目のデータを処理するようにループが組まれる。
【００９６】
９行目の記述により、ｘＩＤ番目のデータがどのビン番号ｂｉｎＩＤに属するかが求められる。そして、１０行目の記述により、図８に示した関数ａｔｏｍｉｃＡｄｄＷが呼び出される。１０行目の” ｄｓｔＤａｔａ”、”１”、”ｂｉｎＩＤ”、”ｄａｔａＢｕｆｆｅｒ”、”ｏｆｆｓｅｔＢｕｆｆｅｒ”は、図８の１−２行目の”ｂａｓｅ”、”ｄａｔａ”、”ｏｆｆｓｅｔ”、”ｄａｔａＢｕｆｆｅｒ”、”ｏｆｆｓｅｔＢｕｆｆｅｒ”にそれぞれ対応する。
【００９７】
関数ａｔｏｍｉｃＡｄｄＷの呼び出しにより、ヒストグラム領域の先頭アドレスｄｓｔＤａｔａにビン番号ｂｉｎＩＤを示すインデックスを加えて求まる記憶領域に、”１”が加えられる。すなわち、ヒストグラムにおける所定のビンの値が”１”増加する。例えば、図３に示した８個の演算コア２２０は、図９に示した制御プログラムを並列に実行し、各制御プログラムは、図８に示した制御プログラムを呼び出す。これにより、関数ａｔｏｍｉｃＡｄｄＷを用いて、図６に示した各ループでの処理がワープ毎に並列に実行される。
【００９８】
図１０は、関数ａｔｏｍｉｃＡｄｄを用いてヒストグラムを作成する制御プログラムの例を示す。図１０の制御プログラムは、図９の４−５行目の記述がなく、８行目の記述において、図９の関数ａｔｏｍｉｃＡｄｄＷの代わりに関数ａｔｏｍｉｃＡｄｄが呼び出されることを除き、図９の制御プログラムと同様である。図１０の１−３行目は、変数の型が異なることを除き、図９の１−３行目と同様である。図１０の４−７行目は、図９の６−９行目と同様である。
【００９９】
図１０では、８行目の関数ａｔｏｍｉｃＡｄｄの呼び出しにより、配列ｄｓｔＤａｔａ［ｂｉｎＩＤ］で示されるヒストグラム領域に”１”が加えられる。関数ａｔｏｍｉｃＡｄｄは、複数のスレッドにより重複して呼び出されるが、アトミック処理のため、書き込み先が同じ処理は逐次に処理される。すなわち、図１０では、データが属するビン番号ｂｉｎＩＤを求める毎に関数ａｔｏｍｉｃＡｄｄが呼び出され、書き込み先が同じ場合は逐次処理が実行される。このため、図１０の制御プログラムの演算効率は、図９の制御プログラムの演算効率より低い。
【０１００】
図１１は、図３に示した演算処理装置が搭載されるシステムＳＹＳの例を示す。システムＳＹＳは、演算処理装置１０００、２０００、記憶装置３０００、周辺制御装置４０００、ハードディスクドライブ装置５０００およびネットワークインタフェース６０００を有する。例えば、システムＳＹＳは、サーバ等のコンピュータシステムである。なお、システムＳＹＳの構成は、図１１に示した例に限定されない。
【０１０１】
例えば、演算処理装置１０００はＧＰＵであり、演算処理装置２０００はＣＰＵ（Central Processing Unit）である。なお、情報処理装置１０００は、複数のＧＰＵコアを有してもよく、情報処理装置２０００は、複数のＣＰＵコアを有してもよい。演算処理装置１０００は、図３に示したスレッド制御装置１００および実行ユニット２００と、記憶装置６００とを有する。
【０１０２】
例えば、記憶装置６００は、図３に示したメモリ制御装置３００、データメモリ４００および命令メモリ５００を含む。例えば、記憶装置６００は、実行ユニット２００により実行される制御プログラムと、制御プログラムにより処理されるデータとを格納する記憶領域を有する。制御プログラムにより処理されるデータを格納する記憶領域の例は、図７に示される。
【０１０３】
演算処理装置２０００は、図３に示した上位のコントローラの一例であり、データ処理を実行するとともに演算処理装置１０００が実行するデータ処理を管理する実行ユニット２１０を有する。例えば、記憶装置３０００は、実行ユニット２１０により実行されるデータ処理プログラムと、データ処理プログラムにより処理されるデータとを格納する記憶領域を有する。なお、記憶装置３００は、演算処理装置２０００の内部に設けられてもよい。
【０１０４】
周辺制御装置４０００は、演算処理装置２０００からの指示に基づいて、ハードディスクドライブ装置５０００およびネットワークインタフェース６０００の動作を制御する。例えば、ハードディスクドライブ装置５０００は、ネットワークからの情報を格納し、ネットワークに出力する情報を格納する。ネットワークインタフェース６０００は、システムとネットワークとの間の情報の授受を制御する。
【０１０５】
例えば、演算処理装置１０００、２０００がそれぞれ実行するプログラムは、ネットワークからハードディスクドライブ装置５０００や記憶装置４００、３０００に転送されてもよい。また、周辺制御装置４０００は光学ドライブ装置を接続してもよい。この場合、演算処理装置１０００、２０００がそれぞれ実行するプログラムは、光学ドライブ装置に装着される光ディスクを介して、ハードディスクドライブ装置５０００や記憶装置４００、３０００に転送される。
【０１０６】
図１２は、図９および図１０に示した制御プログラムによるヒストグラムの作成処理時間のビン数依存性を示す。特に限定されないが、図１２の評価では、図１１に示したシステムＳＹＳが使用され、演算処理装置１０００はＮＶＩＤＩＡ社のＧＰＵ（Ｃ２０７５）であり、演算処理装置２０００はＩｎｔｅｌ（登録商標）社のＣＰＵ（Ｃｏｒｅ  ｉ７  ３９６０Ｘ）である。
【０１０７】
図１２の評価に使用したヒストグラム用のデータは、フラットな分布の乱数により生成され、倍精度浮動小数点で０以上１未満の値であり、データ数は１０７個（＝ｎｕｍＤａｔａ）である。図１２は、横軸に示したビン数（＝ｎｕｍＢｉｎ）を１から１０７まで変化させた場合の各ビン数での処理時間を示す。
【０１０８】
例えば、倍精度浮動小数点の値をビン数個（＝ｎｕｍＢｉｎ）格納する領域が、”ｄｓｔＤａｔａ”を先頭アドレスとする配列変数（ヒストグラムのビンに対応）として確保される。ヒストグラムの分布の下限値を示す”ｌｏｗｅｒ”は０に固定され、ヒストグラムのビン幅を示す”ｗｉｄｔｈ”は、”１．０／ｎｕｍＢｉｎ”である。ヒストグラムの作成に使用するブロックのスレッド数を示す”ｎｕｍＴｈｒｅａｄｓ”は、１０４８５７６に固定される。
【０１０９】
図１２の特性は、図８で説明したアトミック比較交換命令（ａｔｏｍｉｃＣＡＳ）を利用したアトミック加算命令（ａｔｏｍｉｃＡｄｄ）を用いて求められた。ビン数が少なく、アトミック処理の競合頻度が高い場合に（例えば、ビン数が数十個以下）、関数ａｔｏｍｉｃＡｄｄＷは、関数ａｔｏｍｉｃＡｄｄに比べて処理時間の低減に有効なことが分かる。例えば、全てのアトミック処理が競合する１ビン（ｎｕｍＢｉｎ＝１）の場合、関数ａｔｏｍｉｃＡｄｄＷ（図９）によるヒストグラムは、関数ａｔｏｍｉｃＡｄｄ（図１０）によるヒストグラムに比べて、約７８０倍高速に生成できる。これは、ビン数が少ないほど、図６に示したループ内でのデータの加算回数が増加し、アトミック処理（アトミック加算）の回数が減少するためである。
【０１１０】
なお、３２ビット整数のアトミック加算命令（ａｔｏｍｉｃＡＤＤ）を使用してヒストグラムが生成される場合、図９および図１０の記述は、次のように変更される。すなわち、図９の１行目の”ｄｏｕｂｌｅ  ｄｓｔＤＡＴＡ”および４行目の”ｄｏｕｂｌｅ  ｄａｔａＢｕｆｆｅｒ［１２８］”は、”ｉｎｔ  ｄｓｔＤＡＴＡ”および”ｉｎｔ  ｄａｔａＢｕｆｆｅｒ［１２８］”に変更される。図１０の”ｄｏｕｂｌｅ  ｄｓｔＤＡＴＡ”は、”ｉｎｔ  ｄｓｔＤＡＴＡ”に変更される。この場合、”ｎｕｍＢｉｎ＝１”において、関数ａｔｏｍｉｃＡｄｄＷ（図９）によるヒストグラムは、関数ａｔｏｍｉｃＡｄｄ（図１０）によるヒストグラムに比べて、８．６倍高速に生成できる。
【０１１１】
図１３は、図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムの別の例を示す。図８と同様の記述については、詳細な説明は省略する。図１３は、シャッフル命令を使って図８を書き換えたものである。シャッフル命令により、共有メモリ２５０を用いることなくワープ内のスレッド間でデータが交換可能になる。シャッフル命令は、「NVIDIA Co. CUDA C Programming Guide Version 4.2.: NVIDIA Co., 2012」に記載されている。
【０１１２】
共有メモリ２５０を用いないため、図１３の記述はブロックの形に非依存になる。非依存にするために使用した”ａｓｍ（）”は、「Using Inline PTX Assembly In CUDA. NVIDIA Co., 2011.」に記載されている。”％％ｌａｎｅｉｄ”は、「PARALLEL THREAD EXECUTION ISA VERSION 3.0.: NVIDIA Co., 2012.」の９章に記載されている。
【０１１３】
２−３行目の記述は、倍精度浮動小数点のｄａｔａ（６４ビット）を、２つの３２ビット整数ｄａｔａＨ、ｄａｔａＬに分けて格納することを示す。４−５行目の記述は、ワープ内のスレッド番号を取得し、変数ｌａｎｅＩＤに代入することを示す。”ａｓｍ（）”により、ＣＵＤＡのアセンブラであるＰＴＸ（Parallel Thread eXecution）が埋め込まれる。ＰＴＸにより、ワープ内のスレッド番号を直接取得できる。なお、ＣＵＤＡの関数には、ワープ内のスレッド番号を直接取得する方法はない。
【０１１４】
６行目の記述により、アトミック加算を行うかどうかの判定結果をスレッド自身で格納する変数ｗｒｉｔｅＦｌａｇが初期化される。８−１１行目の記述は、図８の１０−１４行目と同様である。１２行目の記述では、図８の１５行目と同様に、処理中のスレッドが処理済みとされる。１３行目の記述は、シャッフル命令を用いて、自身の書き込み先と処理中のスレッドの書き込み先とが同じかどうかを判定するものである。”＿＿ｓｈｆｌ（ｏｆｆｓｅｔ，ｒＩＤ）”は、ワープ内のスレッド番号ｒＩＤのｏｆｆｓｅｔを取得するための関数である。
【０１１５】
１４行目の記述では、図８の１６行目と同様に、処理中のスレッドのワープ内でのスレッド番号が、ワープ内の着目するスレッド番号よりも小さいかどうかが判定される。１５行目の記述は、処理中のスレッドにおけるワープ内のスレッド番号が、ワープ内の着目するスレッド番号よりも小さい場合に、変数ｗｒｉｔｅＦｌａｇが、アトミック処理を実行しない”ｆａｌｓｅ”に設定される。
【０１１６】
１７−１９行目の記述により、シャッフル命令を用いて、スレッド番号ｒＩＤにより示されるスレッドのデータが取得される。”＿＿ｓｈｆｌ（）”は、３２ビット整数を扱うため、処理は３２ビットずつの２つに分けて実行される。
【０１１７】
２０行目の記述では、図８の２０行目と同様に、ワープ内でリダクション加算が実行される。２３行目の記述により、アトミック処理を実行するかどうかが判定される。そして、２４行目の記述では、図８の２３行目と同様に、ワープ内でリダクションした値が、書き込み先にアトミック加算される。
【０１１８】
図１４は、図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムのさらなる別の例を示す。図８および図１３と同様の記述については、詳細な説明は省略する。上述した図８および図１３は、アドレスの代わりに配列変数のインデックスを使用した。これは、配列変数としてアクセスされることと、インデックスの方が実際のアドレスよりもビット数が少ないことを想定しているためである。図１４では、インデックスを用いずにアドレスをそのまま使う例が示される。
【０１１９】
図１４の”ａｔｏｍｉｃＡｄｄＷ（）”は、”ａｔｏｍｉｃＡｄｄ（）”と同じ引数である。”ａｔｏｍｉｃＡｄｄ（）”を使用し、その戻り値を用いない制御プログラムでは、”ａｔｏｍｉｃＡｄｄ（）”を”ａｔｏｍｉｃＡｄｄＷ（）”に置き換えて使用できる。例えば、図１０でも、”ａｔｏｍｉｃＡｄｄ（）”は、”ａｔｏｍｉｃＡｄｄＷ（）”に書き換え可能である。
【０１２０】
図１４の１行目の関数ヘッダにおいて、”ａｄｄｒｅｓｓ”は、データメモリ４００へのデータの書き込みアドレスを示し、”ｄａｔａ”は、書き込みアドレスで指定される領域に加算されるデータを示す。
【０１２１】
２−３行目の記述は、図１３の２−３行目と同様である。４−５行目の記述は、書き込みアドレスを、２つの３２ビット整数ａｄｄｒＨ、ａｄｄｒＬに分けて格納することを示す。６−１４行目の記述は、図１３の４−１２行目と同様である。
【０１２２】
１５行目の記述は、図１３の１３行目と同様に、シャッフル命令を用いて、自身の書き込み先と処理中のスレッドの書き込み先とが同じかどうかを判定するものである。１６−２５行目の記述は、図１３の１４−２３行目と同様である。そして、２６行目の記述では、図１３の２４行目と同様に、ワープ内でリダクションした値が、書き込み先にアトミック加算される。
【０１２３】
図１５は、図４に示したフローを、共有メモリを使わずに実行するよう変更した制御プログラムのさらなる別の例を示す。図８および図１４と同様の記述については、詳細な説明は省略する。図１５では、アトミック処理前にメモリに保持された値を返すコードが図１４に対して追加される。これにより、図１５では、既存の”ａｔｏｍｉｃＡｄｄ（）”と同様の振る舞いを実現できる。すなわち、アトミック処理前のメモリに保持された値を返し、あるいは、アトミック処理後にメモリに保持された値を返す既存の開発環境との互換性を維持できる。なお、図１５においても、図１４と同様に、”ａｔｏｍｉｃＡｄｄ（）”を”ａｔｏｍｉｃＡｄｄＷＲ（）”に置き換えて使用できる。
【０１２４】
１−７行目の記述は、図１４の１−７行目と同様である。８行目の記述では、データメモリ４００の同じ書き込みアドレスに対して、データを書き込むスレッドの番号が初期化される。１０−１６行目の記述は、図１４の１０−１６行目と同様である。
【０１２５】
１７行目の記述では、データメモリ４００の同じ書き込みアドレスにデータを書き込むスレッドの番号が更新される。ここでは、スレッド番号が最も小さいスレッドが処理を担当する。２０−２３行目の記述は、図１４の１９−２２行目と同様である。
【０１２６】
２７行目の記述では、アトミック処理前の値を格納する変数ｏｌｄＶａｌｕｅが”０”に初期化される。２８行目の記述では、アトミック処理を行うかどうかが判定される。２９行目の記述では、ワープ内でリダクション加算された値が、データメモリ４００内のデータの書き込み先にアトミック加算され、加算前の値が変数ｏｌｄＶａｌｕｅに代入される。３２−３７行目の記述では、書き込みを担当したスレッドから、”ｏｌｄＶａｌｕｅ”が取得される。”ｏｌｄＶａｌｕｅ”は６４ビットなので、３２ビットの二つのデータに分けてやり取りする。
【０１２７】
３９行目の記述では、”ｏｌｄＶａｌｕｅ＋（ｓｕｍ−ｄａｔａ）”が関数の戻り値として返される。これにより、関数ａｔｏｍｉｃＡｄｄとの互換性が維持される。なお、”ｓｕｍ”から”ｄａｔａ”を引くと誤差が若干増えるため、２３行目で、自身のスレッド番号より大きい場合のみ”ｓｕｍ”に”ｄａｔａ”を加えてもよい。
【０１２８】
また、図７から図１５では、ヒストグラムを作成する例（加算）について説明したが、乗算、最大値計算、最小値計算において、ワープ内でリダクション演算を実行した後、アトミック処理を実行してもよい。
【０１２９】
以上、この実施形態においても、図１および図２に示した実施形態と同様に、アトミック処理の競合頻度を下げることができ、従来に比べて、演算処理装置の演算速度を向上でき、演算処理装置によるデータ処理の効率を向上できる。
【０１３０】
さらに、この実施形態では、着目スレッドのデータを加える記憶領域と同じ記憶領域にデータを加えるスレッドが複数存在する場合、スレッド番号が同じか、小さいスレッドが着目スレッドのデータとのリダクション演算を実行する。また、着目スレッドのデータを加える記憶領域と同じ記憶領域にデータを加えるスレッドで、スレッド番号の最も小さいスレッドが、アトミック処理を実行する。
【０１３１】
これにより、複数のスレッドが図４に示したフローを並列に実行する場合にも、ステップＳ１２２のアトミック処理により、１つのデータが複数のスレッドによって重複して加えられることはない。この結果、複数のスレッドでリダクション演算を実行する場合にも、演算処理装置は、正しい演算結果を求めることができる。
【０１３２】
また、図４のステップＳ１０８、Ｓ１１０、Ｓ１１２により、演算の実行が可能な有効スレッドが着目スレッドに順次に設定され、演算の実行が許可されない無効スレッドは着目スレッドに設定されない。さらに、リダクション演算は、有効スレッドのデータに対して実行され、無効スレッドのデータに対して実行されない。これにより、無効なデータのリダクション演算の実行を避けることができる。
【０１３３】
以上の詳細な説明により、実施形態の特徴点および利点は明らかになるであろう。これは、特許請求の範囲がその精神および権利範囲を逸脱しない範囲で前述のような実施形態の特徴点および利点にまで及ぶことを意図するものである。また、当該技術分野において通常の知識を有する者であれば、あらゆる改良および変更に容易に想到できるはずである。したがって、発明性を有する実施形態の範囲を前述したものに限定する意図はなく、実施形態に開示された範囲に含まれる適当な改良物および均等物に拠ることも可能である。
【符号の説明】
【０１３４】
１０‥実行ユニット；１２‥演算コア；１４‥制御部；２０‥データメモリ；３０‥命令メモリ；１００‥スレッド制御装置；２００‥実行ユニット；２１０‥スレッドスケジューラ；２２０‥複数の演算コア；２３０‥レジスタファイル；２４０‥ロード／ストアユニット；２５０‥共有メモリ；３００‥メモリ制御装置；４００‥データメモリ；５００‥命令メモリ；６００‥記憶装置；１０００、２０００‥演算処理装置；３０００‥記憶装置；４０００‥周辺制御装置；５０００‥ハードディスクドライブ装置；６０００‥ネットワークインタフェース；ＭＡ‥記憶領域；ＳＹＳ‥システム
【図１】
2014106715.tif 000004
【図２】
2014106715.tif 000005
【図３】
2014106715.tif 000006
【図４】
2014106715.tif 000007
【図５】
2014106715.tif 000008
【図６】
2014106715.tif 000009
【図７】
2014106715.tif 000010
【図８】
2014106715.tif 000011
【図９】
2014106715.tif 000012
【図１０】
2014106715.tif 000013
【図１１】
2014106715.tif 000014
【図１２】
2014106715.tif 000015
【図１３】
2014106715.tif 000016
【図１４】
2014106715.tif 000017
【図１５】
2014106715.tif 000018