Подход к оценке локальности зернистых вычислительных процессов, логически организованных в двумерную структуру
Аннотация
При реализации алгоритмов на многопроцессорных вычислительных устройствах важнейшую роль для достижения высокой производительности играет локальность — вычислительное свойство алгоритма, отражаюшее степень использования памяти с быстрым доступом. Для суперкомпьютеров с распределенной памятью быстрой считается локальная память вычислительного узла. Параллельные алгоритмы с меньшим объемом и лучшей структурой коммуникационных операций обладают лучшей локальностью. В работе на основе схемы расщепления с весами построен новый параллельный алгоритм численного решения трехмерного линейного уравнения теплопроводности. Алгоритм ориентирован на компьютеры с распределенной памятью, сочетает конвейерный и естественый параллелизм, использует 2D структуру процессов. Схема расщепления обладает естественным параллелизмом. Ранее для случая 1D структуры процессов было показано, что использование конвейерного параллелизма вместо части естественного параллелизма приводит к меньшим объемам и лучшей структуре коммуникационных операций. Построенный 2D алгоритм обобщает известный 1D алгоритм. Использование двумерных структур позволяет уменьшить объем и улучшить структуру коммуникационных операций, уменьшить время разгона и торможения вычислений. Поэтому 2D алгоритм обладает лучшей локальностью по сравнению с использованием 1D структуры процессов. Вычислительные эксперименты на суперкомпьютере показали преимущество нового параллельного алгоритма. По аналогии с представленным алгоритмом можно получить и исследовать параллельные алгоритмы для других схем метода дробных шагов. На примере алгоритма, реализующего схему расщепления, представлен подход к получению асимптотических оценок объема коммуникационных операций зернистых (т.е. уровня макроопераций) параллельных вычислительных процессов, логически организованных в двумерную структуру. Оценки могут быть использованы для сравнения коммуникационных затрат при получении альтернативных вариантов параллельных алгоритмов.
Ключевые слова
Полный текст:
PDFЛитература
Adutskevich E.V., Likhoded N.A. A consistent generation of pipeline parallelism and distribution of operations and data among processors. Programming and Computer Software. 2006. Vol. 32, no. 3. P. 166–176.
Bakhanovich S.V., Likhoded N.A., Mandrik P.A. Improvement of locality of parallel algorithms of the numerical solutions of the two-dimensional quasilinear parabolic equation. RUDN Journal of Mathematics, Information Sciences and Physics. 2014. No. 2. P. 211–215. (in Russian)
Voevodin V.V., Voevodin Vl.V. Parallel Computing. St. Petersburg, BKhV-Petersburg Publ., 2002. 608 p. (in Russian)
Voevodin Vl.V., Voevodin Vad.V. The fortunate locality of supercomputers Open Systems. 2013. No. 9. P. 12–15. (in Russian)
Gergel V.P., Strongin R.G. Introduction to parallel computing for multiprocessor systems. Nizhny Novgorod, Lobachevsky State University of Nizhny Novgorod, 2003. 184 p. (in Russian)
Koleshko S.B., Popov F.D. Mechanics of Liquids and Gases. Difference schemes. Tutorial. St. Petersburg, SPbGTU Publ., 2001. 72 p. (in Russian)
Korneev B.A., Levchenko V.D. Effective solving of three-dimensional gas dynamics problems with the Runge-Kutta discontinuous Galerkin method. Comput. Math. and Math. Phys. 2016. Vol. 56. P. 460–469. DOI: 10.1134/S0965542516030118.
Likhoded N.A. Sufficient conditions for the determination and use of data in the same granular parallel computation process. Computational Mathematics and Mathematical Physics. 2014. Vol. 54, no. 8. P. 1316–1326. (in Russian) DOI: 10.1134/s0965542514080077.
Likhoded N.A., Bakhanovich S.V., Zherelo A.V. Obtaining affine transformations to improve the locality of loop nests. Programming and Computer Software. 2005. Vol. 31, no. 5. P. 270–281. (in Russian) DOI: 10.1007/s11086-005-0036-2.
Likhoded N.A., Poleshchuk M.A. Tiled parallel 2D computational processes. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 2018. Vol. 54, no. 4. P. 417–426. (in Russian) DOI: 10.29235/1561-2430-2018-54-4-417-426.
Likhoded N.A., Tolstsikau А.А. Locality estimation of parallel algorithm for distributed memory computers. Proceedings of the National Academy of Sciences of Belarus. 2020. Vol. 64, no. 6. P. 647–656. (in Russian) DOI: 10.29235/1561-8323-2020-64-6-647-656.
Likhoded N.A., Tolstsikau A.A. Parallel sequences of grain computations. Proceedings of the National Academy of Sciences of Belarus. 2010. Vol. 54, no. 4. P. 36–41. (in Russian)
Tolstsikau A.A., Likhoded N.A. Algorithm partition correctness while organizing grained parallel computing processes. International Congress on Computer Science: Information Systems and Technologies (CSIST'2011) (Minsk, Belarus, October 31 – November 3, 2011). Minsk, Belarusian State University, 2011. Vol. 2. P. 122–126. (in Russian)
Tolstsikau A.A., Likhoded N.A. Parallel algorithm implementing split method for a distributed memory computer. Parallel Computational Technologies (PCT 2020) (Perm, Russia, March 31 – April 2, 2020). Short papers and posters. Chelyabinsk, Publishing of the South Ural State University, 2020. P. 287–297. (in Russian)
Yanenko N.N. The method of fractional steps for solving multi-dimensional problems of mathematical physics. Novosibirsk, Science, 1967. 196 p. (in Russian)
Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. Lecture Notes in Computer Science. Vol. 4959. Springer, 2008. P. 132–146. DOI: 10.1007/978-3-540-78791-4_9.
Buluc A., Gilberta J.R., Budak C. Solving path problems on the GPU. Parallel Computing. 2010. Vol. 36, no. 5–6. P. 241–253. DOI: 10.1016/j.parco.2009.12.002.
Dathathri R., Mullapudi R.T., Bondhugula U. Compiling affine loop nests for a dynamic scheduling runtime on shared and distributed memory. ACM Transactions on Parallel Computing (TOPC). 2016. Vol. 3, no. 2. DOI: 10.1145/2948975.
Lim A.W., Lam M.S. Maximizing parallelism and minimizing synchronization with affine partitions. Parallel Computing. 1998. Vol. 24, no. 3–4. P. 445–475. DOI: 10.1016/S0167-8191(98)00021-0.
Xue J. Loop tiling for parallelism. Springer Science & Business Media, 2000. 256 p. DOI: 10.1007/978-1-4615-4337-4.
Zhao J., Cohen A. Flextended tiles: a flexible extension of overlapped tiles for polyhedral compilation. ACM Transactions on Architecture and Code Optimization. 2019. Vol. 16, no. 4, article 47. DOI: 10.1145/3369382.
Zhao J., Di P. Optimizing the Memory Hierarchy by Compositing Automatic Transformations on Computations and Data. 53rd IEEE/ACM International Symposium on Microarchitecture (MICRO 2020) (Athens, Greece, October 17–21, 2020). IEEE, 2020. P. 427–441. DOI: 10.1109/micro50266.2020.00044.
DOI: http://dx.doi.org/10.14529/cmse210303