Подход к оценке локальности зернистых вычислительных процессов, логически организованных в двумерную структуру
Автор: А.А. Толстиков, С.В. Баханович, Н.А. Лиходед
Статья в выпуске: 3 т.10, 2021 года.
Бесплатный доступ
При реализации алгоритмов на многопроцессорных вычислительных устройствах важнейшую роль для достижения высокой производительности играет локальность — вычислительное свойство алгоритма, отражаюшее степень использования памяти с быстрым доступом. Для суперкомпьютеров с распределенной памятью быстрой считается локальная память вычислительного узла. Параллельные алгоритмы с меньшим объемом и лучшей структурой коммуникационных операций обладают лучшей локальностью. В работе на основе схемы расщепления с весами построен новый параллельный алгоритм численного решения трехмерного линейного уравнения теплопроводности. Алгоритм ориентирован на компьютеры с распределенной памятью, сочетает конвейерный и естественный параллелизм, использует 2D структуру процессов. Схема расщепления обладает естественным параллелизмом. Ранее для случая 1D структуры процессов было показано, что использование конвейерного параллелизма вместо части естественного параллелизма приводит к меньшим объемам и лучшей структуре коммуникационных операций. Построенный 2D алгоритм обобщает известный 1D алгоритм. Использование двумерных структур позволяет уменьшить объем и улучшить структуру коммуникационных операций, уменьшить время разгона и торможения вычислений. Поэтому 2D алгоритм обладает лучшей локальностью по сравнению с использованием 1D структуры процессов. Вычислительные эксперименты на суперкомпьютере показали преимущество нового параллельного алгоритма. По аналогии с представленным алгоритмом можно получить и исследовать параллельные алгоритмы для других схем метода дробных шагов. На примере алгоритма, реализующего схему расщепления, представлен подход к получению асимптотических оценок объема коммуникационных операций зернистых (т.е. уровня макроопераций) параллельных вычислительных процессов, логически организованных в двумерную структуру. Оценки могут быть использованы для сравнения коммуникационных затрат при получении альтернативных вариантов параллельных алгоритмов
Параллельные вычисления, многопроцессорная вычислительная система с распределенной памятью, уменьшение обменов данными, метод дробных шагов
Короткий адрес: https://sciup.org/147234531
IDR: 147234531 | УДК: 519.67 | DOI: 10.14529/cmse210303
An approach to estimate the locality of grained computation processes organized to a two-dimensional structure
Implementing algorithms for distributed memory computers, one should pay attention to locality, a computational property of the algorithm that reflects the usage of fast access memory, that plays an important role in achieving high performance. For computing systems with distributed memory the local memory of each node is considered fast. Usually the parallel algorithms have better locality if it has a smaller total size of communication data and a better structure of communication operations. In this work, a new parallel algorithm for the numerical solution of a three-dimensional linear heat equation is constructed on the basis of a splitting method with weights. The algorithm is specified for distributed memory computers, combines pipeline and natural parallelism, and uses a 2D process structure. For the case of 1D process structure it was shown that usage of a pipeline parallelism instead of part of natural parallelism reduces the total size of communication operations. The proposed 2D algorithm generalizes the known 1D algorithm. The usage of two-dimensional structures allows to reduce the total volume of communication operations and to reduce idle time of a pipeline. Therefore, the 2D algorithm has better locality compared to the 1D process structure. The computational experiments on a distributed computing sytem have shown the advantage of a new parallel algorithm. Proposed method can be used to obtain and to examine parallel algorithms for other schemes of the fractional step method. Additionally, the implemented splitting scheme algorithm shows an approach to obtain asymptotic estimation of the communication volume, presented method operates with granular (the macrooperation level) parallel computing processes organized logically into a two-dimensional structure. The estimations can be used to compare communication cost for alternative versions of parallel algorithms. The approach is developed on the basis of early result that allows to obtain asymptotic estimations of the communication operations volume of computational processes organized in a one-dimensional structure
Список литературы Подход к оценке локальности зернистых вычислительных процессов, логически организованных в двумерную структуру
- Адуцкевич Е.В., Лиходед Н.А. Согласованное получение конвейерного параллелизма и распределения операций и данных между процессорами // Программирование. 2006. Т. 32, № 3. С. 54–65.
- Баханович С.В., Лиходед Н.А., Мандрик П.А. Улучшение локальности параллельных алгоритмов численного решения двумерных квазилинейных параболических уравнений // Вестник Российского университета дружбы народов. Серия: Математика, информатика, физика. 2014. № 2. С. 211–215.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. Санкт-Петербург: БХВ-Петербург, 2002. 608 с.
- Воеводин Вл.В., Воеводин Вад.В. Спасительная локальность суперкомпьютеров // Открытые системы. 2013. № 9. С. 12–15.
- Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. Нижний Новгород: ННГУ им. Н.И. Лобачевского, 2003. 184 с.
- Колешко C.Б., Попов Ф.Д. Механика жидкости и газа. Разностные схемы. Учеб. пособие. СПб.: Изд-во СПбГТУ, 2001. 72 с.
- Корнеев Б.А., Левченко В. Д. Эффективное решение трехмерных задач газовой динамики Рунге—Кутты разрывным методом Галеркина// Журнал вычислительной математики и математической физики. 2016. № 3. С. 465–475. DOI: 10.7868/S0044466916030121.
- Лиходед Н.А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе // Журнал вычислительной математики и математической физики. 2014. № 8. С. 122–133. DOI: 10.7868/s0044466914080092.
- Лиходед Н.А., Баханович С.В., Жерело А.В. Получение аффинных преобразований для улучшения локальности гнезд циклов // Программирование. 2005. № 5. С. 52– 65. DOI: 10.1007/s11086-005-0036-2.
- Лиходед Н.А., Полещук М.А. Построение двумерных зернистых параллельных вычислительных процессов // Известия НАН Беларуси. Сер. физ.-мат. наук 2018. Т. 54, № 4. С. 417–426. DOI: 10.29235/1561-2430-2018-54-4-417-426.
- Лиходед Н.А., Толстиков А.А. Метод оценки локальности параллельных алгоритмов, ориентированных на компьютеры с распределенной памятью // Доклады НАН Беларуси. 2020. Т. 64, № 6. С. 647–656. DOI: 10.29235/1561-8323-2020-64-6-647-656.
- Лиходед Н.А., Толстиков А.А. Параллельные последовательности зернистых вычислений // Доклады НАН Беларуси. 2010. Т. 54, № 4. С. 36–41.
- Толстиков А.А., Лиходед Н.А. Корректность разбиений алгоритмов при организации зернистых параллельных вычислительных процессов // Международный конгресс по информатике: информационные системы и технологии (CSIST'2011) (Минск, 31 октября – 3 ноября 2011 г.). Минск: Белорусский государственный университет, 2011. Т. 2. С. 122–126.
- Толстиков А.А., Лиходед Н.А. Параллельный алгоритм метода расщепления для реализации на суперкомпьютерах с распределенной памятью // Международная научная конференция «Параллельные вычислительные технологии» (ПаВТ’2020) (Пермь, 31 марта – 2 апреля 2020 г.). Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2020. С. 287–297.
- Яненко Н.Н. Метод дробных шагов решения многомерных задач математической физики. Новосибирск: Изд-во «Наука». Сибирское отделение, 1967. 197 с.
- 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.
