実行時ライブラリの実装

Omniの実行時ライブラリは，スレッドの生成および割り当てやループのスケジュー リング，スレッド間の同期処理，リダクション演算などの機能を提供している．

OMPCUDAの実行時ライブラリは，Omniにおいて逐次実行部で行っている処

理はCPUで行い，並列実行部で行っている処理はGPUで行う，という方針で実装 した．

単純なforループの並列化に最低限必要な関数として，GPU上で実行されるfor ループのスケジューリングを行う関数を実装した．さらに，forループの並列化と ともに利用されることの多いリダクション演算に必要な，GPU上で実行されるリ ダクション関数を実装した．OmniではCPU上で実行されるスレッド割り当ておよ び並列実行開始関数も提供しているが，これについてはプログラム変換機構による CUDA実行時ライブラリ関数の呼び出しへの書き換えが役割を果たしているため，

実行時ライブラリでは特に処理を行わない．

forループのスケジューリング

Omniにおけるforループの並列化は，実行時ライブラリが提供する，各スレッド が自らのスレッドIDを元に新たな部分ループを作成するための関数(スケジューリ ング関数)を用いて行われている．CUDAの実行時ライブラリにも一意のIDを得る

4.2 OMPCUDA : CUDA向けOpenMP の提案と実装 106

機能が備わっているため，OMPCUDAはこれを用いてOmniと同様に部分ループを 作成するための関数を提供することとした．

CUDAにおける並列実行は既存のCPUにおけるスレッド実行と異なり，CUDA BlockとCUDA Threadの2階層によって構成されている．GPUはCPUからの並 列実行開始指示を受けると，多数のCUDA Threadが同時に演算を開始する．同一 CUDA Block内のCUDA Threadは同時に異なる演算を行うことができず，また，

各CUDA Blockを構成するCUDA Threadの数は全CUDA Blockで同一である．し かし各CUDA Threadは固有のIDを持つため，このIDを用いて共有メモリ上の異 なるデータに対して同時に演算を行うことができる．

そのためCUDAにおける並列処理については，1CUDA Block内の複数CUDA Threadを用いた並列処理，複数CUDA Blockを用いるが各CUDA Block内では 1CUDA Threadのみを利用する並列処理，複数CUDA Block・複数CUDA Thread を用いた並列処理，以上の3種類の並列処理が考えられる．複数CUDA Block・複

数CUDA Threadを用いた並列処理が最も多くの演算を同時実行できるものの，同

一CUDA Block内の各CUDA Threadは同時に異なる演算を行えないため，対象問 題によっては複数のCUDA Threadを用いても性能向上が得られない可能性がある．

これに対して，単純なforループの並列化では各スレッドが同時に同じ演算を行 うことが多い．そのためforループの並列化をCUDAに割り当てるうえでは，複数 のCUDA Threadによる並列処理でも性能向上が可能であり，上記3種類の並列処 理のいずれにも対応付けることができると考えられる．

Omniはループ並列化におけるスケジューリング方法を複数提供しておりアプリ ケーションプログラマが選択することができる．OMPCUDAでは最も単純なスケ ジューリングである，ループのイタレーションを等分割したスタティックスケジュー リングのみを提供し，他のスケジューリング方法については検討を行うのみとする．

現在提供しているOMPCUDAにおけるforループのスケジューリング(割り当て) 例を図45に示す．

CUDA向けにおける最適なCUDA Block使用数・CUDA Thread使用数は，対 象プログラムの並列性や対象プログラム内の命令の構成，対象GPUの性能(主に 搭載しているSMの数)により左右される．現在はCUDA Thread使用数のデフォ ルト値として(CUDA Thread使用数については1CUDA Blockあたり256程度の

4.2 OMPCUDA : CUDA向けOpenMP の提案と実装 107

図 45: OMPCUDAにおけるforループのスケジューリング例

4.2 OMPCUDA : CUDA向けOpenMP の提案と実装 108

CUDA Threadを利用するべきであるという最適化指標が示されているため) 256を，

CUDA Block使用数についてはforループの並列度をCUDA Threadで割った値(た だしCUDAの仕様に定められている利用可能なCUDA Block数の上限を超えない ように調整する)としている．

なおOmniの実行時ライブラリは環境変数や実行時の関数呼び出しにより利用す るスレッドの数を変更することが可能となっている．OMPCUDAも最適なCUDA Block使用数・CUDA Thread使用数は対象問題に依存することから，実行時に関数 や環境変数を用いてCUDA Block使用数・CUDA Thread使用数を変更できるよう にした．

ただし，一般的に既存のOpenMPにおいてスレッド数として指定する意味がある のは実行環境に存在するCPU(コア)数程度の値であるのに対して，CUDAにおいて 最も高い性能が得られるCUDA Block数・CUDA Thread数は数百から数千である．

そのためアプリケーションプログラマが自らCUDA Block数・CUDA Thread数を指 定する場合は，CUDAにおける適切な並列度の指定に関する知識がなくては適切な 値を指定できない．これはアプリケーションプログラマに対して実行環境に関する知 識を習得する手間を削減するという本アプローチの趣旨に反している．OMPCUDA が自動的に常に適切なCUDA Block数・CUDA Thread数を求められるようにする ためにも，今後より多くのGPU環境や対象プログラムに対して適用実験を行う必 要がある．

なお，Omniが提供しているforループのスケジューリング方法の例としては，以下 のものが挙げられる．いずれも並列実行部において各スレッドが実行するスケジュー リング関数として実装されている．

1. 指定されたチャンクサイズを単位としたスタティックなラウンドロビンスケ ジューリング

2. 指定サイズのチャンクサイズを単位としたダイナミックスケジューリング 3. 指定されたチャンクサイズを最初の割り当て単位としたGuided Self Scheduling

OMPCUDAでもこれらの各スケジューリングアルゴリズムを実装することは可

能であると考えられる．しかしダイナミックなスケジューリングを行う場合には，

チャンクの再割り当てを行う際に多重割り当て等が起きないようCUDA Block内の

4.2 OMPCUDA : CUDA向けOpenMP の提案と実装 109

CUDA Thread同士またはCUDA Block間のCUDA Thread同士の待ち合わせや排 他制御が必要となる可能性がある．OMPCUDAではGPU全体で合計数千のCUDA

Threadを同時に実行することが予想されるため，待ち合わせにより性能が低下する

可能性のあるダイナミックスケジューリングよりもスタティックスケジューリング の方が適していると考え，今回の実装を選択した．

リダクション演算

“for”指示子や“DO”指示子といったループ並列化指示子とともに多くのOpenMP プログラムで利用されている指示子に“reduction”指示子がある．“reduction”指示 子は並列実行部を実行する際に並列実行の最後で全スレッドの持つ変数を足し込ん だり，全スレッドの持つ同名の変数の中で最も大きな値のみを並列実行部が終了し た後も残したりするために利用される指示子である．Omniでは“reduction”指示 子を実行時ライブラリのリダクション関数として実装している．OMPCUDAでは

“reduction”指示子を用いた処理の中でも最も典型的な処理である“全スレッドの持 つ同名な変数の総和を求める処理”を実行時ライブラリ関数として実装した．以下

この“全スレッドの持つ同名な変数の総和を求める処理”を単にリダクション演算と

呼ぶことにする．

GPUやCUDAを用いたリダクション演算については，既にいくつかの実装[103, 104]が知られている．OMPCUDAではOwensらの手法[105]をベースに SharedMem-oryを用いた並列リダクション関数を実装して利用することにした．ただしOwens らの手法はCUDA Block内のリダクション演算のみを扱っている．CUDA Block内 のリダクション演算はSharedMemoryを用いることで高速に行うことができる一方，

問題全体，すなわちCUDA Block間でのリダクション演算については，atomic演算 を用いたCUDA Block間での排他制御やCUDA Block間での待ち合わせを行いな がらGlobalMemoryに対して処理を行う必要があるため実行時間が長くなる可能性 がある．むしろCUDA Block単位でリダクション演算を行った結果をCPUに返し，

CPU上で最終的なリダクション演算を行った方が良い性能が得られることが考えら れる．

OMPCUDAではCUDA Block毎にリダクション演算を行った後，各CUDA Block 内の1CUDA Threadがatomic演算によって最終的なリダクションを行うという実 装を行った．そのため利用するCUDA Block数が増えるとCUDA Block間のリダク

4.2 OMPCUDA : CUDA向けOpenMP の提案と実装 110

ション時間が増大し，性能に悪影響を及ぼすと考えられる．この影響については次 節の性能評価で確認する．

OMPCUDAの実行モデルでは，OpenMP プログラムの共有メモリに対応する

CUDAの共有メモリとしてはGlobalMemoryのみを利用しているが，リダクショ ン演算ではSharedMemoryを利用している．このように実行時ライブラリ関数の中 でSharedMemoryを用いることで，アプリケーションプログラマには SharedMem-oryを意識させずにSharedMemoryを活用した高速化が行えると考えられる．例え

ばOMPCUDAの発展的な実装の案として，ループ並列部の内部にさらなる並列性が

見られる場合はループの並列化をGlobalMemoryを用いたCUDA Blockレベルでの 並列処理に対応付けたうえでループ内部の並列性をSharedMemoryを用いたCUDA

Threadレベルでの並列処理に対応付けることなどが考えられる．