Parallelizing SOR for GPGPUs using alternate loop tiling

详细信息	查看全文 | 推荐本文 |

• 作者：Peng Di^a ; Hui Wu^a ; Jingling Xue^a ; ^{jingling@cse.unsw.edu.au} ; Feng Wang^b ; Canqun Yang^b
• 关键词：GPGPU ; DOACROSS parallelism ; Loop tiling ; Gauss&ndash ; Seidel ; SOR
• 刊名：Parallel Computing
• 出版年：2012
• 期刊代码：99_01678191
• 类别：cp
• 出版时间：June-July, 2012
• 卷：38
• 期：6-7
• 页码：310-328
• 文件大小：1624 K

摘要

Gauss-Seidel and SOR, which are widely used smoothers in multigrid methods, are difficult to parallelize, particularly on GPGPUs due to the existence of DOACROSS data dependences. In this paper, we present a new parallel SOR method that admits more efficient data-parallel SIMD execution than red-black SOR on GPGPUs. Our solution is obtained non-conventionally, by starting from a K-layer SOR method and then parallelizing it by applying a non-dependence-preserving scheme consisting of a new domain decomposition technique followed by a loop tiling technique called alternate tiling. Despite its relatively slower convergence, our new method outperforms red-black SOR by making a better balance between data reuse and parallelism and by trading off convergence rate for SIMD parallelism. Our experimental results highlight the importance of synergy between domain experts, compiler optimizations and performance tuning in maximizing the performance of PDE-like DOACROSS loops on GPGPUs.