A Parallel SOR Algorithm for Linear Systems on SMP

Reservoir simulation is an important area in high performance computing. SOR (successive over relaxation) iterative solution technique is used to solve the pressure equations in simulation. Parallel implementation of iterative solution technique is important for decreasing simulation execution time and improving simulation precision. Current published approaches are mostly restricted to implement parallel algorithms based on data partition in one iteration step. However, these approaches do not consider partitioning and merging iteration space, which makes algorithm have a very low efficiency. Considering the characteristics of SOR and SMP (symmetric multi-processors) system, using OpenMP as an implementation tool of parallel program, a parallel SOR algorithm is proposed. The parallel algorithm makes data in different area execute a number of iteration steps in parallel by rearranging points updating sequence. A new strategy of data partition and merging iteration steps during solving pressure equations in reservoir simulation is discussed. The new algorithm enables the locality of a program to be improved by iteration reordering, and the synchronization times to be decreased by merging iteration steps. Shape of each mesh block in different iteration step is presented. Compared with the current parallel implementation of SOR, this algorithm can decrease cost of synchronization and improve data locality. The experimental results on speedup and efficiency are also presented.