迭代空间交错条块并行Gauss-Seidel算法

Iterative Space Alternate Tiling Parallel Gauss-Seidel Algorithm

针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.

In order to optimize data locality, communication and synchronization overhead, this paper proposes a multi-layers symmetric Gauss-Seidel method. Then the serial execution model of this iterative method is given, which introduces the sequence of iterative space tile as the sequence of execution, and divides iteration space by time skewing. In this model, nodes of the tile can be updated many times to improve data locality. The parallel GS execution model based on iteration space tiling is presented, which uses an improved iteration space partition algorithm and reorders the tiles of iteration space to reduce cache misses, communication and synchronization cost. Finally the numerical results are presented to confirm the effectiveness of Gauss-Seidel parallelized with alternate tiling method, specifically compared with owner-computing and red-black Gauss-Seidel methods, and show that the new parallel iterative method has better parallel efficiency as well as scalability.