Re-ordering/coloring이 타원형 방정식을 위한 반복 해법의 Open-MP 성능에 미치는 영향에 대한 연구 = A study on the effect of re-ordering/coloring on the Open-MP performance of iterative solvers for elliptic equation

국문 초록 (Abstract)

Gauss-Seidel (GS) 방법은 선형 시스템을 위한 multigrid 솔버의 robust smoother로 널리 사용되고 있다. 그러나, GS 방법은 Jacobi 방법과 달리 동일한 배열에 대해 읽고 쓰기가 수행되므로 병렬화 하기 어렵다. 따라서, GS 방법의 병렬 연산을 위한 정렬 격자의 Red-Black Gauss-Seidel (RBGS) 방법과 비정렬 격자의 Multicolor Gauss-Seidel (MCGS) 방법이 개발되었다.
본 연구에서는 새로운 RBGS 방법으로서 노드 순서가 다른 두 개의 2D 및 3D 배열을 사용하는 Red-Black-2A (RB-2A) 방법을 제안한다. RB-2A 방법에 대해 Open-MP 프로그래밍을 통한 병렬 계산 및 비정렬 격자의 재정렬 기법이 가지는 효과도 조사되었다.
Jacobi 및 GS방법의 계산 시간은 시스템의 캐시 크기에 매우 큰 영향을 받는 것으로 확인되었다. Jacobi 방법의 메모리 접근이 더욱 효율적이기 때문에 GS 방법의 반복 횟수가 Jacobi 방법의 절반인 경우에도 Jacobi 방법보다 느리다. 본 연구에서는 RB-2A방법이 가장 우수한 성능을 보였고, 직렬 계산에 한하여 재정렬 격자를 사용한 MCGS 방법이 가장 우수한 것으로 나타났다. 또한, 재정렬 격자를 사용하였을 때의 계산 시간은 최초의 비정렬 격자를 사용한 것보다 우수하였다. 병렬화의 효과로는, 격자 크기가 캐시 메모리 크기에 맞는 경우에는 병렬 계산을 통해 계산 속도가 super-linear로 증가하였으나, 격자 크기가 캐시 메모리 크기를 초과하는 조밀 격자의 경우 병렬 계산을 통한 계산 속도 증가는 크지 않았다.

다국어 초록 (Multilingual Abstract)

In this thesis, we investigate the effect of re-ordering/coloring on the Open-MP performance of iterative solvers for elliptic equation for structured grid and unstructured grid in two-dimensional (2D) and three-dimensional (3D) problems.
For structured grid, we develop a new ordering technique for nodes for Red-Black Gauss-Seidel (RBGS) method using two-dimensional array and three-dimensional array. Firstly, Jacobi and Gauss-Seidel (GS) methods are used to solve the 2D/3D elliptic equation. We discrete the problem by using a finite difference method (FDM). The GS method is known to converge in half the number of iterations compared to the Jacobi method for all grid resolutions, and does not require an additional array to store the variable information. However, the Gauss-Seidel method is not easily parallelized, as the information is read from and written back to the same array. Therefore, the RBGS method has been developed for parallel computing of GS method. In the RBGS method, we color the nodes by two colors in the structured mesh such as red and black. In this thesis, we propose a new RBGS method named Red-Black-2A (RB-2A) which uses two separate 2D/3D arrays with different node ordering. We also investigate the Red-Black-1A (RB-1A) method which uses one single 2D/3D array to compare to the RB-2A method. Moreover, we present the effect of cache size memory on CPU time in our simulation. The elapsed time of Jacobi and GS methods is strongly affected by the cache size of computation machine. The result shows that the RBGS method has the best performance at serial computation, especially on the RB-2A method.
Regarding to unstructured grid, we investigate the re-ordering technique for elements and nodes. Besides, we also study the multicolor technique for GS method as well as the effect of coloring with re-ordering mesh and without re-ordering mesh. The results show that the CPU time with re-ordering mesh is better than original mesh at serial computation.
Finally, we study parallel computation by using Open-MP programming. The advantage of OpenMP is that it does not require the data communication across the processors because the data of whole computational domain is stored on shared memory within a single computer. However, the drawback is that the data size stored using in OpenMP is limited to the number of thread processing. Furthermore, the OpenMP causes a large overhead time for the OpenMP directive. Similar to serial computation, the results show that the RBGS method has the best performance in parallel computation in the structured grid. Also, the CPU time in both serial computation and parallel computation is improved significantly with re-ordering mesh in unstructured mesh.

목차 (Table of Contents)

• Summary i
• Table of contents iii
• List of Tables iv
• List of Figures v
• List of Acronyms and Abbreviations vii
• List of Symbols viii
• 1. Introduction 1
• 2. Structured grid 5
• 2.1. Numerical method 5
• 2.1.1. Governing equation 5
• 2.1.2. Jacobi method 6
• 2.1.3. Gauss - Seidel method 7
• 2.2. Coloring for structured grid 8
• 2.2.1. Red-Black – 1A (RB-1A) method 9
• 2.2.2. Red-Black – 2A (RB-2A) method 10
• 2.2.3. The data memory access 11
• 2.2.4. Results and discussion 13
• 3. Unstructured grid 22
• 3.1. Multicolor for Gauss-Seidel (MCGS) method 22
• 3.2. Re-ordering technique for unstructured grid 24
• 3.3. Results and discussion 26
• 3.3.1. Serial computation case 29
• 3.3.2. Parallel performance with OpenMP programming 31
• 4. Conclusions 35
• 5. References 36
• Abstract 39
• Acknowledgements 40