Iterative Space Alternate Tiling Parallel Gauss-Seidel Algorithm

Abstract: 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