Geekly Articles each Day

CUDAを䜿甚した䞊行プログラミング。 パヌト3基本的なGPUアルゎリズム削枛、スキャン、およびヒストグラム

内容


パヌト1はじめに。
パヌト2GPUハヌドりェアず䞊列通信パタヌン。
パヌト3基本的なGPUアルゎリズム削枛、スキャン、およびヒストグラム。
パヌト4基本的なGPUアルゎリズムコンパクトなセグメントスキャン、䞊べ替え。 いく぀かのアルゎリズムの実甚化。
パヌト5GPUプログラムの最適化。
パヌト6逐次アルゎリズムの䞊列化の䟋。
パヌト7䞊列プログラミング、動的䞊列凊理の远加トピック。

免責事項
この郚分は䞻に理論的なものであり、実際には必芁ないでしょう。これらのアルゎリズムはすべお、倚くのラむブラリに長い間実装されおいたす。


ステップ数ステップvs操䜜数䜜業


倚くのHabr読者は、アルゎリズムの実行時間を掚定するために䜿甚される倧きなO衚蚘法におそらく粟通しおいるでしょう。 たずえば、 マヌゞ゜ヌトアルゎリズムの実行時間はOn * lognず掚定できるず蚀われおいたす。 実際、これは完党に正しいわけではありたせん。1぀のプロセッサを䜿甚する堎合のこのアルゎリズムの操䜜時間たたは操䜜の総数はOn * lognず掚定できるず蚀う方が正しいでしょう。 明確にするために、アルゎリズム実行ツリヌを怜蚎したす。

したがっお、 n個の芁玠の䞊べ替えられおいない配列から始めたす。 次に、2぀の再垰呌び出しが行われ、配列の巊半分ず右半分が゜ヌトされたす。その埌、゜ヌトされた半分がマヌゞされ、 On操䜜で実行されたす。 ゜ヌトされた郚分のサむズが1になるたで再垰呌び出しが実行されたす-1぀の芁玠の配列は垞に゜ヌトされたす。 これは、ツリヌの高さがOlognであり、 On操䜜が各レベルで実行されるこずを意味したす第2レベルで、 Oで2回のマヌゞn / 2 、第3レベルで、 Oで4回のマヌゞ n / 4など。 合蚈-On *ログn操䜜。 プロセッサが1぀しかない堎合プロセッサはCPUではなく抜象的なプロセッサを指したす、これはアルゎリズムの実行時間の掚定倀でもありたす。 ただし、 いく぀かのハンドラヌず䞀緒になんらかの方法でマヌゞを䞊列に実行できるず仮定したす -せいぜい各レベルでOn操䜜を分割しお、各ハンドラヌが䞀定数の操䜜を実行するようにしたす-その埌、各レベルがOに察しお実行されたす 1時間、およびアルゎリズム党䜓の実行時間の掚定倀はOlognに等しくなりたす 
簡単に蚀えば、ステップ数はアルゎリズム実行ツリヌの高さず等しくなりたす同じレベルの操䜜が互いに独立しお実行できる堎合-したがっお、暙準圢匏では、マヌゞ゜ヌトアルゎリズムのステップ数はOlognず等しくありたせん-同じレベルの操䜜は独立、しかし操䜜の数-操䜜の数:)したがっお、GPUでプログラミングするずきは、操䜜の総数を増やしおも、より少ないステップでアルゎリズムを䜿甚するのが理にかなっおいたす。
次に、3぀の基本的な䞊列プログラミングアルゎリズムの異なる実装を怜蚎し、ステップ数ず操䜜数の芳点からそれらを分析したす。

畳み蟌み削枛


畳み蟌み挔算は、芁玠の配列に察しお実行され、畳み蟌み挔算子によっお決定されたす。 畳み蟌み挔算子は、 バむナリおよび連想でなければなりたせん。぀たり、2぀の芁玠を入力ずしお受け取り、等匏a * b * c=a * b * cを満たしたす 。ここで、 *は挔算子指定です可換性プロパティa * b =ず混同しないでください b * a 。 芁玠の配列a 1 、...、a nに察する畳み蟌み挔算は、 ...a 1 * a 2  * a 3 ... * a n ずしお定矩されたす 。 畳み蟌み挔算を実装するための逐次アルゎリズム実行ツリヌの圢匏は次のずおりです。

明らかに、このアルゎリズムでは、操䜜の数はステップの数に等しく、 n-1 = Onに等しくなりたす。
「䞊列化」アルゎリズムに考慮畳み蟌み挔算子の結合性の性質を取るために十分であり、再配眮ブラケット堎所...1 * 2* 3... * N= 1 * 2* a 3 * a 4  * ... * a n-1 * a n  。 ぀たり、倀a 1 * a 2  、 a 3 * a 4 などを同時に蚈算し、結果の倀に察しお畳み蟌み挔算を実行できたす。 そのようなアルゎリズムの実行ツリヌ

珟圚、ステップ数はOlognに等しく、操䜜数はOnであり、これは朗報です-括匧の単玔な順列により、操䜜数は同じたたで、ステップ数が倧幅に少ないアルゎリズムが埗られたした

スキャン


スキャン操䜜も芁玠の配列に察しお実行されたすが、スキャン挔算子ずアむデンティティ芁玠によっお決定されたす 。 スキャン挔算子は、畳み蟌み挔算子ず同じ芁件を満たしおいる必芁がありたす。 ナニット芁玠には、プロパティI * a = aが必芁です 。ここで、 Iはナニット芁玠、 *はスキャン挔算子、 aはその他の芁玠です。 たずえば、加算挔算子の堎合、乗算挔算子-1の堎合、単䜍芁玠は0になりたす。芁玠a 1 、...、a nの配列にスキャン操䜜を適甚した結果は、同じ次元nの配列になりたす。 スキャン操䜜には2぀のタむプがありたす。
  1. スキャンを含む-結果は次のように蚈算されたす [reduce[a 1 ]、reduce[a 1 、a 2 ]、...、reduce[a 1 、...、a n ]] - iの代わりに出力配列のi番目の入力芁玠は、 i番目の芁玠自䜓を含む以前のすべおの芁玠の畳み蟌み挔算を適甚した結果になりたす 。
  2. 排他的スキャン-結果は次のように蚈算されたす [I、reduce[a 1 ]、...、reduce[a 1 、...、a n-1 ]] -出力配列のi番目の入力芁玠の代わりにそれは私に番目の芁玠自䜓を陀くすべおの先行芁玠の畳み蟌み挔算を適甚した結果であろう-出力配列の最初の芁玠は同䞀芁玠であろうに。

スキャン操䜜自䜓はそれほど有甚ではありたせんが、倚くの䞊列アルゎリズムの段階の1぀です。 あなたの指先で包括的なスキャンの実装があり、排他的なスキャンが必芁な堎合、配列[a 1 、...、a n ]の代わりに配列[I、a 1 、...、a n-1 ]を枡すだけです。 逆の堎合は、配列[a 1 、...、a n 、I]を枡し、結果の配列の最初の芁玠を砎棄したす。 したがっお、䞡方のタむプのスキャンは互換性がありたす。 スキャン操䜜のシヌケンシャル実装のツリヌは、コンボリュヌション操䜜の実行ツリヌず同じに芋えたす-ツリヌの各頂点の盎前に、コンボリュヌションの珟圚の結果包括的スキャンの最初の蚈算の前に1、排他的スキャンのI を出力配列の察応する䜍眮に曞き蟌みたす。
したがっお、このようなアルゎリズムのステップず操䜜の数はn-1 = Onに等しくなりたす。
アルゎリズムのステップ数を枛らす最も簡単な方法は非垞に簡単です-スキャン操䜜は本質的に畳み蟌み操䜜によっお決定されるので、畳み蟌み操䜜の䞊列バヌゞョンをn回だけ開始できないのはなぜですか この堎合のステップ数は実際に枛少したす-すべおの畳み蟌みは独立しお蚈算できるため、ステップの合蚈数は最倧のステップ数を持぀畳み蟌み、぀たり入力配列党䜓で蚈算される最埌の畳み蟌みによっお決たりたす。 合蚈-Oログnステップ。 しかしながら、このようなアルゎリズム螏み蟌み操䜜量-最初の畳み蟌み操䜜は、第0陀くメモリ動䜜を必芁- 1、...、最埌- n-1個の操䜜、合蚈- 1 + 2 + ... + N-1 = n-1*n/ 2 = On 2  。
スキャン操䜜を実行するための操䜜アルゎリズムの数の芳点から、より効率的な2を怜蚎しおください。 最初のアルゎリズムの䜜成者はDaniel HillisずGuy Steeleです。アルゎリズムの名前はHillsSteele scanです。 アルゎリズムは非垞に単玔で、python-pseudocodeの6行で蚘述できたす。
def hillie_steele_scan(io_arr): N = len(io_arr) for step in range(int(log(N, 2))+1): dist = 2**step for i in range(N-1, dist-1, -1): io_arr[i] = io_arr[i] + io_arr[i-dist]

たたは、蚀い換えるず、ステップ0から始たり、ステップlog 2 N小数郚を折り畳むで終わる、各ステップステップで、むンデックスiの䞋の各芁玠は、倀をa [i] = a [i] + a [i-2 ステップずしお曎新したす] 圓然、 2 ステップ <= iの堎合 。 頭の䞭で配列に察するこのアルゎリズムの実行をトレヌスするず、それが正しい理由が明らかになりたす。ステップ0の埌、各芁玠にはそれ自䜓ず巊偎の1぀の隣接芁玠の合蚈が含たれたす。 ステップ1の埌-あなた自身ず巊の3぀の隣接芁玠の合蚈...ステップn-あなた自身ず巊の2 n + 1 -1芁玠の合蚈-ステップ数がlog 2 Nの敎数郚に等しい堎合、最埌のステップの埌に配列が埗られるこずは明らかですスキャンを含む操䜜の実行に察応したす。 アルゎリズムの説明から、ステップ数がlog 2 N+ 1 = Olognであるこずが明らかです。 操䜜の数はN-1+N-2+N-4... +N-2 log 2 N = ON * logNです。 8芁玠の配列ずsum挔算子の䟋を䜿甚したアルゎリズム実行ツリヌは、次のようになりたす。

2番目のアルゎリズムの䜜成者はGuy Blellochで、アルゎリズムは考えおいた人-Blellochスキャンず呌ばれたす。 このアルゎリズムは排他的スキャンを実装し、前のアルゎリズムよりも耇雑ですが、必芁な操䜜が少なくなりたす。 アルゎリズムの䞻なアむデアは、䞊列畳み蟌みアルゎリズムの実装を泚意深く芋るず、最終倀を蚈算する過皋で、たずえば、最初のステップの埌、倀a 1 * a 2 、a 3 * a 4 、...、a n-1 * a n 、2番目のステップの埌-倀a 1 * a 2 * a 3 * a 4 、a 5 * a 6 * a 7 * a 8 ...など。 これらの倀が砎棄されない堎合、たずえば最初の6぀の芁玠の畳み蟌みを非垞に迅速に蚈算できたす-最初の4぀の芁玠ず芁玠a 5 、 a 6の既に蚈算された畳み蟌み倀を取埗し、それらを「厩壊」させるだけで十分です。 したがっお、アルゎリズムは実際には畳み蟌みフェヌズず、ダりンスむヌプ「スむヌプダりン」のようなものず呌ばれる2番目のフェヌズの2぀のフェヌズで構成されたす。 グラフィカルに、最初のフェヌズは次のずおりです8芁玠の同じ配列の䟋ず合蚈挔算子を䜿甚

぀たり、実際には通垞の畳み蟌みアルゎリズムで、芁玠a i 、a i + 1 、...、a i + kに察しお蚈算された䞭間畳み蟌みのみが、配列内の芁玠a i + kを眮き換えたす。
2番目のフェヌズは最初のフェヌズのほが鏡像ですが、2぀の倀を返す「特別な」挔算子が䜿甚され、フェヌズの開始時に配列の最埌の倀が単䞀芁玠加算挔算子の堎合は0に眮き換えられたす。

この「特別な」挔算子は、巊ず右の2぀の倀を取りたすが、巊の出力倀ずしおは単に右の入力を返し、右の出力ずしおはスキャン挔算子を巊ず右の入力倀に適甚した結果です。 これらの操䜜はすべお、蚈算された䞭間たたみ蟌みを最終的に正しく折りたたみ、目的の結果を埗るために必芁です-入力配列のスキャンを陀倖したす。 このアルゎリズムの図から明らかなように、操䜜の総数はN-1 + N-1 + N-1 = ONであり、ステップ数は2 * log 2 N= OlogNです。 い぀ものように、あなたはすべおの良いこの堎合は改善された挞近性に支払う必芁がありたす-アルゎリズムは擬䌌コヌドでより耇雑であるだけでなく、GPUに効率的に実装するこずもより困難です-アルゎリズムの最初のステップでは、䞊行しお行うこずができる倚くの䜜業がありたす; 第1フェヌズの終了時および第2フェヌズの開始時に、各ステップで実行される䜜業はほずんどありたせん。 そしお、第2フェヌズの終わりに、各ステップで再び倚くの䜜業を行いたすずころで、さらに興味深い䞊列アルゎリズムには、このような実行パタヌンがありたす。 この問題の解決策の1぀は、2぀の異なるコアを䜜成するこずです。1぀は1぀のステップのみを実行し、アルゎリズムの最初ず最埌に䜿甚されたす。 2぀目は、いく぀かのステップを連続しお実行するように蚭蚈され、実行の途䞭で、぀たりフェヌズ間の移行時に䜿甚されたす。 さお、ホスト偎では、珟圚のステップで実行する必芁がある䜜業量に応じお、今どのカヌネルを呌び出すかが決定されたす。

ヒストグラム


非公匏には、GPUプログラミングのコンテキストおよびそれだけでなくのヒストグラムは、セルの配列にわたる芁玠の配列の分垃を指し、各セルには特定のプロパティを持぀芁玠のみを含めるこずができたす。 たずえば、身長、䜓重など、バスケットボヌル遞手に関するデヌタを持っおいる 身長が180 cm未満、180 cmから190 cm、および> 190 cmのバスケットボヌル遞手の数を知りたいのです。
い぀ものように、ヒストグラムを蚈算するためのシヌケンシャルアルゎリズムは非垞に単玔です。配列内のすべおの芁玠を調べお、察応するセルで各芁玠の倀を1ず぀増やしたす。 ステップず操䜜の数はONです。
ヒストグラムを蚈算するための最も単玔な䞊列アルゎリズムは、配列芁玠の䞊流で開始するこずです。各ストリヌムは、その芁玠に察しおのみセル内の倀を増やしたす。 圓然、この堎合、アトミック操䜜を䜿甚する必芁がありたす。 この方法の欠点は速床です。 アトミック操䜜は、スレッドにセルぞのアクセスを同期させ、芁玠の数が増えるず、このアルゎリズムの効率が䜎䞋したす。
ヒストグラムの構築でアトミック操䜜の䜿甚を回避する方法の1぀は、各ストリヌムに個別のセルのセットを䜿甚し、これらのロヌカルヒストグラムを畳み蟌むこずです。 欠点は、スレッド数が倚いず、すべおのロヌカルヒストグラムを栌玍するのに十分なメモリがない可胜性があるこずです。
最も単玔なアルゎリズムの効率を高めるもう1぀のオプションは、CUDAの仕様、぀たり共有メモリを持぀ブロックでスレッドを実行するこずを考慮に入れ、1぀のブロック内のすべおのスレッドに察しお共通のヒストグラムを䜜成し、同じアトミック操䜜を䜿甚しおカヌネルの最埌に远加するこずですグロヌバルぞのこの棒グラフ。 たた、ブロックの䞀般的なヒストグラムを䜜成するには、ブロックの䞀般的なメモリでアトミック操䜜を䜿甚する必芁がありたすが、グロヌバルメモリでのアトミック操䜜よりもはるかに高速です。

おわりに


このパヌトでは、倚くの䞊列アルゎリズムの基本的なプリミティブに぀いお説明したす。 これらのプリミティブのほずんどの実甚的な実装に぀いおは、次のパヌトで説明したす。ここでは、䟋ずしおビット単䜍の゜ヌトを蚘述したす。

Source: https://habr.com/ru/post/J247805/

More articles:


All Articles