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

Лиходед Н. А., Полещук М. А.
2018

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

Лиходед Н. А., Полещук М. А. Построение двумерных зернистых параллельных вычислительных процессов. Известия Национальной академии наук Беларуси. Серия физико-математических наук. 2018;54(4):417-426. https://doi.org/10.29235/1561-2430-2018-54-4-417-426
Цитирование

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

Похожие публикации

Источник