Распараллеливание циклов. 
Параллельное программирование на основе технологий openmp, mpi, cuda

Известно, что более 90% (как правило, значительно более, т. е. 99.999…%) из времени решения задачи выполняется всего 10% (и меньше) текста программы (так называемое соотношение 90:10). Эти 10 % текста — циклы. Именно этими участками текста программы и следует заниматься при ее распараллеливании.

Распараллеливание циклов подразумевает большую степень гранулярности, чем пооперационное распараллеливание. Обычно гранулой при таком подходе считается одна итерация распараллеливаемого цикла.

Пусть в программе есть цикл, между итерациями которого нет информационной зависимости, например:

Итерации этого цикла могут быть выполнены в любом порядке, в том числе, одновременно друг с другом.

Для параллельной системы из п вычислительных элементов (процессоров) может быть реализовано:

Блочное распределение по N / п итераций (если N не делится нацело на я, то загрузка процессоров будет неодинаковой). При этом разные вычислительные узлы будут выполнять следующие фрагменты программы (в этих фрагментах через N0, N1, … Nk обозначены соответствующие количества итераций):

//доля процессора 0, N0 = N / п //доля процессора 1, N0 = 2*N/n.

//доля процессора п-1 = к, …

Циклическое распределение тоже по N/п итераций:

//доля процессора 0.

//доля процессора 1

//доля процессора п-1

Блочно-циклическое распределение:

//доля процессора 0 //доля процессора 1.

Для больших задач типичной является ситуация, когда основной объем вычислений определяется совокупностью вложенных друг в друга циклов (гнездом циклов):

Пространством итераций гнезда тесно вложенных циклов называют множество целочисленных векторов { [О, О, U-1, …], [О, О, U-2], … }, координаты которых задаются значениями индексных переменных всех циклов данного гнезда.

Задача распараллеливания в этом случае сводится к разбиению этого множества векторов на подмножества таким образом, чтобы итерации этих подмножеств могли быть выполнены параллельно.

Существуют следующие методы разбиения: координат, гиперплоскостей, параллелепипедов, пирамид и более сложные.

Метод координат заключается в том, что пространство итераций фрагмента разбивается на гиперплоскости, перпендикулярные одной из координатных осей.

Пусть, например, есть гнездо циклов:

Разбиение пространства итераций по измерению / (гиперплоскоскостями, перпендикулярными оси /) приводит к разрыву информационных зависимостей. Следовательно, такое распараллеливание неприемлемо. Однако возможно применение метода координат с разбиением пространства итераций гиперплоскостями, перпендикулярными осиу.

Все такие операции назначаются для выполнения на одном процессоре.

При использовании метода гиперплоскостей пространство итераций размерности п разбивается на подпространства размерности от 1 до п — 1 таким образом, чтобы все операции, соответствующие точкам одного подпространства, могли выполняться параллельно. Каждое такое подпространство есть гиперплоскость, не обязательно перпендикулярная какой-либо оси координат.

Например, для такого гнезда: метод координат нс годится.

Однако существуют удовлетворяющие условию / + j = const гиперплоскости, проходящие через нс содержащие информационных зависимостей вершины. При этом параллельно работающим процессорам следует назначить вычисления тела цикла для каждой из гиперплоскостей, для которых i + j = const.

Метод параллелепипедов является логическим развитием двух предыдущих методов и заключается в разбиении пространства итераций на /7-мерные параллелепипеды с использованием ортогональных гиперплоскостей, весь объем каждого из которых назначается отдельному процессору.

Возможны и другие более сложные методы распределения пространства итераций при соблюдении основного принципа: параллельно выполняемые итерации не должны информационно зависеть друг от друга.