Numerical performance of a sweep parallel algorithm on distributed memory multiprocessors
Keywords:
mathematical simulation
parallel algorithms
high performance computing
Schrödinger equation
Abstract
An efficient sweep parallel algorithm used when solving the nonlinear Schrödinger equation by the implicit Crank-Nicolson scheme with a spatial and time mesh refinement mechanism is considered. Its performance on distributed-memory multiprocessors is analyzed. It is shown on the basis of computational experiments and the well-known theoretical model (Amdahl’s law) that the proposed algorithm scales well and achieves efficiency and speedup over the sequential algorithm up to 0.7 and 30, respectively. The effect of the numerical mesh size (range, 104-106) and the network communication delays (CPU number range, 6 mdash; 128) on the performance of computing is discussed. Keywords: mathematical simulation, parallel algorithms, high performance computing, Schrödinger equation
Downloads
Published
2008-10-02
Issue
Section
Section 1. Numerical methods and applications
References
- Thomas L.H. Elliptic problems in linear difference equations over a network. Technical report. New York: Columbia University Press, 1949.
- Hockney R.W., Jesshope C.R. Parallel computers: architecture, programming and algorithms. Bristol: IOP Publishing Ltd., 1981.
- Cox C. L. Implemention of a divide and conquer cyclic reduction algorithm on the FPS T-20 hypercube // Proc. of the Third Conference on Hypercube Concurrent Computers and Applications. January 1989. Pasadena, California, United States. 1532-1538.
- Ortega J.M., Voigt R.G. Solution of partial differential equations on vector and parallel computers // SIAM Rev., June 1985. 149-240.
- Sun X.-H., Zhang H., Ni L.M. Efficient tridiagonal solvers on multicomputers // IEEE Transactions on Computers. 1992. 41, N 3. 286-296.
- Sun X.-H., Moitra S. A fast parallel tridiagonal algorithm for a class of CFD applications. NASA Technical Paper N 3585. 1996.
- Chawla M.M., Passi K., Zalik R.A. A recursive partitioning algorithm for inverting tridiagonal matrices // Int. J. Computer Math. 1990. 35. 153-158.
- Povitsky A. Parallel directionally split solver based on reformulation of pipelined Thomas algorithm. ICASE Technical Report N 45. 1998.
- Яненко Н.Н., Коновалов А.Н., Бугров А.Н., Шустов Г.В. Об организации параллельных вычислений и «распараллеливание» прогонки // Числ. методы механики сплошн. среды. 1978. 9, № 7. 139-146.
- Paasonen V.I. Boundary conditions of high-order accuracy at the poles of curvilinear coordinate systems // Russian Journal of Numerical Analysis and Mathematical Modelling. 1999. 14, N 4. 369-382.
- Паасонен В.И. Параллельный алгоритм для компактных схем в неоднородных областях // Вычислительные технологии. 2003. 8, № 3. 98-106.
- Паасонен В.И. Сходимость параллельного алгоритма для компактных схем в неоднородных областях // Вычислительные технологии. 2005. 10, № 5. 81-89.
- Воеводин А.Ф., Шугрин С.М. Методы решения одномерных эволюционных систем. Новосибирск: Наука, 1993.
- Кудряшова Т.А., Поляков С.В. О некоторых методах решения краевых задач на многопроцессорных вычислительных системах // Труды IV международной конференции по математическому моделированию. 27 июня - 1 июля 2000 г., Москва (под ред. Л.А. Уваровой). 2. 134-145. М.: СТАНКИН, 2001.
- Amdahl G. Validity of the single processor. Approach to achieving large-scale computing capabilities // Proceedings of the AFIPS Conference. 1967. 483-485.
- Рычков А.Д. Численные методы и параллельные вычисления // Учебное пособие. Новосибирск: СибГУТИ, 2007.
- Прокопьева Л.Ю., Чубаров Д.Л. Производительность параллельной прогонки // Труды IV Российско-германской школы по параллельным вычислениям и высокопроизводительным вычислительным системам. Новосибирск: ИВТ СО РАН, 2007.
- Витковский В.Э., Федорук М.П. Численное исследование свойств решений нелинейного уравнения Шредингера при распространении лазерных импульсов в световодах // Вычислительные технологии. 2008. 13, № 6.
