Метод оценки локальности параллельных алгоритмов, ориентированных на компьютеры с распределенной памятью
https://doi.org/10.29235/1561-8323-2020-64-6-647-656
Аннотация
Степень использования памяти с быстрым доступом отражает вычислительное свойство алгоритма, называемое локальностью. Для параллельных компьютеров с распределенной памятью быстрой считается локальная память вычислительного узла. При реализации алгоритмов на многопроцессорных вычислительных устройствах использование локальности играет важнейшую роль для достижения высокой производительности. Основной задачей исследования локальности параллельного алгоритма является оценка числа и объема коммуникационных операций. В этой работе сформулированы и доказаны утверждения, позволяющие получить асимптотические оценки объема коммуникационных операций вычислительных процессов, реализуемых на параллельных компьютерах с распределенной памятью. Получены выражения, характеризующие число данных, для которых требуются коммуникации, и число процессов, вовлеченных в пересылки этих данных. Эти оценки могут быть использованы для сравнения коммуникационных затрат при получении альтернативных вариантов параллельных алгоритмов.
Об авторах
Н. А. Лиходед
Белорусский государственный университет
Беларусь
Беларусь
Лиходед Николай Александрович – д-р физ.-мат. наук, профессор
пр. Независимости, 4, 220030, Минск
А. А. Толстиков
Белорусский государственный университет
Беларусь
Беларусь
Толстиков Алексей Александрович – ст. преподаватель
пр. Независимости, 4, 220030, Минск
Список литературы
1. Воеводин, Вл. В. Спасительная локальность суперкомпьютеров / Вл. В. Воеводин, Вад. В. Воеводин // Открытые системы. – 2013. – № 9. – С. 12–15.
2. Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, N 6. – P. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4
3. Dathathri, R. Compiling affine loop nests for a dynamic scheduling runtime on shared and distributed memory / R. Dathathri, R. T. Mullapudi, U. Bondhugula // ACM Transactions on Parallel Computing (TOPC). – 2016. – Vol. 3, N 2. – P. 1–28. https://doi.org/10.1145/2948975
4. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб., 2002. – 608 с.
5. Адуцкевич, Е. В. Согласованное получение конвейерного параллелизма и распределения операций и данных между процессорами / Е. В. Адуцкевич, Н. А. Лиходед // Программирование. – 2006. – Т. 35, № 3. – С. 52–65.
6. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula [et al.] // Lecture notes in computer science. – 2008. – N 4959. – P. 132–146. https://doi.org/10.1007/978- 3-540-78791-4_9
7. Лиходед, Н. А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе / Н. А. Лиходед // Журн. вычисл. математики и матем. физики. – 2014. – Т. 54, № 8. – С. 1356. https://doi.org/10.7868/S0044466914080092
8. Лиходед, Н. А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма / Н. А. Лиходед, М. А. Полещук // Докл. Нац. акад. наук Беларуси. – 2015. – Т. 59, № 4. – С. 25–33.
9. Гергель, В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем / В. П. Гергель, Р. Г. Стронгин. – Нижний Новгород, 2003. – 184 с.
10. Лиходед, Н. А. Параллельные последовательности зернистых вычислений / Н. А. Лиходед, А. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 4. – С. 36–41.
11. Баханович, С. В. Улучшение локальности параллельных алгоритмов численного решения двумерных квазилинейных параболических уравнений / С. В. Баханович, Н. А. Лиходед, П. А. Мандрик // Вестн. Рос. ун-та дружбы народов. Сер. Математика. Информатика. Физика. – 2014. – № 2. – С. 211–215.
Рецензия
Просмотров: 636
Послать статью по эл. почте 