著者

加藤 誠也 須田 礼仁 玉田 嘉紀

雑誌

研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.2012, no.5, pp.1-11, 2012-05-25

---

近年 GPU は計算能力において目覚しい発展を続けており,NVIDIA の CUDA C に代表される演算用の言語の導入などによって,科学技術計算分野において重要な役目を担うようになっている.その一方で,CUDA のプログラミングモデルである SIMT (Single Instruction Multiple Threads) の特徴として,ダイバージェンスと呼ばれる問題があり,GPU の実行率が低下するため,GPU は CPU に比べると条件分岐の影響を受けやすい.そのため,条件分岐の最適化がより重要になっている.本論文では,GPU のダイバージェンスを削減し,実行率を向上させるための手法として,動的割り付け・分岐統一化の 2 つの手法を提案する.動的割り付けは主にデータごとに長さの異なるループが実行されるカーネルに対して適用可能である.これは,CUDA におけるブロック単位でデータを割り当て,ブロック内で各スレッドに動的にデータを割り当てることで,各スレッドに割り当てられるデータの処理量を均等にし,GPU の実行率を高める手法である.分岐統一化はデータに応じた条件分岐によって処理の大半が分かれているカーネルに対して適用可能である.これは,各スレッドに複数のデータを割り当てて,ある分岐方向の処理を行う際に,各スレッドが自分の持つデータの中からその方向に分岐するデータを選んでそれに対して処理を行うようにすることで,各スレッドに各条件分岐の実行中に実行するデータがあるようにして,GPU の実行率を上げることができるという手法である.これらの手法の有効性は,サンプルコードを用いた実験によって確認した.Recently, GPUs have progressed tremendously in computational power. Thus, the role of GPUs has become important in the field of computational science with the introduction of programing languages for GPU computation such as NVIDIA CUDA C. On the other hand, a problem called branch divergence has appeared as the feature of the programming model of CUDA called SIMT (Single Instruction Multiple Threads). Because of this, GPUs are more likely to be affected by conditional branch instructions than CPUs. Therefore, optimization of conditional branch is very important on GPUs in order to utilize the entire computational power. This paper proposes two techniques for reducing branch divergence on GPUs. Dynamic work assignment is applicable when almost every part of the kernel is a loop whose number of iterations is different with respect to input data. This technique increases the GPU execution rate by assigning data to each CUDA block and assigning data to each thread dynamically in the block so that the amount of computation of each thread becomes equal to others in the block. Branch path unification is applicable when almost every part of the kernel executes the different branch path by a conditional branch depending on data. This technique increases the GPU execution rate by assigning multiple data to a thread and exchanging the order of data assigned to threads so that the same branch path is executed by as many threads as possible and all the branch paths are executed one after the other. The effectiveness of these techniques has been confirmed by the experiments with the sample codes.