Preview

Известия Национальной академии наук Беларуси. Серия физико-математических наук

Расширенный поиск

Построение двумерных зернистых параллельных вычислительных процессов

https://doi.org/10.29235/1561-2430-2018-54-4-417-426

Аннотация

Алгоритм, реализуемый на параллельном компьютере с распределенной памятью, имеет, как правило, зернистую структуру: множество операций разбито на подмножества, называемые зернами вычислений. Одним из современных подходов к получению зернистых вариантов алгоритмов является тайлинг – преобразование, основанное на информационных разрезах итерационного пространства, в результате которого получаются макрооперации-тайлы. Операции одного тайла выполняются атомарно, как одна единица вычислений, а обмен данными происходит массивами. В настоящей работе для алгоритмов, заданных вложенными многомерными циклами, предложен способ построения зернистых вычислительных процессов, логически организованных в двумерную структуру. По сравнению с одномерными структурами, использование двумерных структур возможно в меньшем числе случаев, но может иметь преимущества при реализации алгоритмов на параллельных компьютерах с распределенной памятью. К числу возможных преимуществ относятся уменьшение объема коммуникационных операций, уменьшение разгона и торможения вычислений, потенциально большее число вычислительных процессов, организация обменных операций только в пределах строк или столбцов процессов. Представленные исследования обобщают на случай двумерной структуры некоторые аспекты метода построения параллельных вычислительных процессов, организованных в одномерную структуру. В частности, исследована возможность организовать полностью загруженные работой параллельные вычислительные процессы. Показано, что при определенных ограничениях на структуру и длину циклов достаточно произвести тайлинг по трем координатам многомерного итерационного пространства. В более ранних теоретических исследованиях параллельность зернистых вычислений гарантировалась при наличии информационных разрезов по всем координатам итерационного пространства, а для более простого случая одномерной структуры – по двум координатам.

Об авторах

Н. А. Лиходед
Белорусский государственный университет, Минск
Беларусь
доктор физикоматематических наук, профессор кафедры вычислительной математики факультета прикладной математики и информатики


М. А. Полещук
Белорусский государственный университет, Минск
Беларусь
ассистент кафедры вычислительной математики факультета прикладной математики и информатики


Список литературы

1. Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, №. 6. – P. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4

2. Kim, D. Parameterized tiling for imperfectly nested loops / D. Kim, S. Rajopadhye // Technical Report CS-09-101. – Colorado State University, Department of Computer Science, February 2009. – 21 p.

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, №. 2. – P. 1–28. https://doi.org/10.1145/2948975

4. Лиходед, Н. А. Параллельные последовательности зернистых вычислений / Н. А. Лиходед, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 4. – С. 36–41.

5. Толстиков, А. А. Корректность разбиений алгоритмов при организации зернистых параллельных вычислительных процессов / А. А. Толстиков, Н. А. Лиходед // Междунар. конгресс по информатике: информационные системы и технологии CSIST’2011, 31 окт. – 3 нояб. 2011 г. – Минск: БГУ, 2011. – Т. 2. – С. 122–126.

6. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.

7. Соболевский, П. И. Двухуровневый тайлинг и его применение при пространственно-временном отображении алгоритмов на параллельные архитектуры / П. И. Соболевский, С. В. Баханович // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2016. –№ 2. – С. 85–97.

8. Parameterized tiled loops for free / L. Renganarayanan [et al.] // ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, California, USA, June 2007. – [S. l.], 2007. – P. 126–138. https://doi.org/ 10.1145/1250734.1250780

9. Самарский, А. А. Методы решения сеточных уравнений / А. А. Самарский, Е. С. Николаев. – М.: Наука, 1978. – 592 с.


Рецензия

Просмотров: 824


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)