Abstract
The Successive Over Relaxation (SOR) is a variant of the iterative Gauss-Seidel method for solving a linear system of equations Ax = b. The SOR algorithm is used within the NEMO (Nucleus for European Modelling of the Ocean) ocean model for solving the elliptical equation for the barotropic stream function. The NEMO performance analysis shows that the SOR algorithm introduces a significant communication overhead. Its parallel implementation is based on the Red-Black method and foresees a communication step at each iteration. An enhanced parallel version of the algorithm has been developed by acting on the size of the overlap region to reduce the frequency of communications. The overlap size must be carefully tuned for reducing the communication overhead without increasing the computing time. This work describes an analytical performance model of the SOR algorithm that can be used for establishing the optimal size of the overlap region.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Madec, G., et al.: NEMO ocean engine. Note du Pole de modellisation, Institut Pierre-Simon Laplace (IPSL), France, No 27 (2008) ISSN No 1288-1619
Tonani, T., Pinardi, N., Dobricic, S., Pujol, I., Fratianni, C.: A high-resolution free-surface model of the Mediterranean Sea. Ocean Science 4, 1–14 (2008)
Hageman, L., Young, D.: Applied Iterative Methods. Academic Press, New York (1981)
Bronshtein, I.N., Semendyayev, K.A.: Handbook of Mathematics, 3rd edn., p. 892. Springer, New York (1997)
Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., Van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edn. SIAM, Philadelphia, PA (1994)
Press, W.H., Flannery, B.P., Teukolsky, S.A., Vetterling, W.T.: Successive Overrelaxation (SOR). Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd edn., pp. 866–869. Cambridge University Press, Cambridge (1992)
Yavneh, I.: On Red Black SOR Smoothing in Multigrid. SIAM Journal on Scientific Computing 17(1), 180–192 (1994)
Niethammer, W.: The SOR method on parallel computers. Numer. Math. 56, 247–254 (1989)
Evans, D.J.: Parallel SOR iterative methods. Parallel Computing 1, 3–18 (1984)
Xie, D.: A New Block Parallel SOR Method and its Analysis. SIAM Journal on Scientific Computing 27(5), 1513–1533 (2006)
Benshila, R., et al.: Optimization of the SOR solver for parallel run. Technical report Version 1, LOCEAN-IPSL, France (2005)
Wallcraft, A.J., Chassignet, E.P., Hurlburt, H.E., Townsend, T.L.: 1/25o Atlantic Ocean Simulation Using HYCOM. DoD HPCMP Users (2005)
Meng, J., Skadron, K.: Performance modeling and automatic ghost zone optimization for iterative stencil loops on GPUs. In: Proceedings of the 23rd International Conference on Supercomputing, ICS 2009 (2009) ISBN: 978-1-60558-498-0, doi:10.1145/1542275.1542313
Grama, A.Y., Gupta, A., Karypis, G., Kumar, V.: Introduction to Parallel Computing, 2nd edn. Addison-Wesley, Harlow (2003)
Grama, A.Y., Gupta, A., Kumar, V.: Isoefficiency: measuring the scalability of parallel algorithms and architectures. IEEE Parallel Distributed Technology Systems Applications 1(3), 12–21 (1993) ISSN: 10636552
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Epicoco, I., Mocavero, S. (2012). The Performance Model of an Enhanced Parallel Algorithm for the SOR Method. In: Murgante, B., et al. Computational Science and Its Applications – ICCSA 2012. ICCSA 2012. Lecture Notes in Computer Science, vol 7333. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31125-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-31125-3_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31124-6
Online ISBN: 978-3-642-31125-3
eBook Packages: Computer ScienceComputer Science (R0)