О распараллеливании циклов принято говорить в терминах пространства итераций (Лампорт Л., 70-е годы). Рассмотрим для примера следующий циклический фрагмент программы (T – тело цикла):

(1)

Пространством итераций гнезда циклов (1) называется множество целочисленных векторов

В терминах пространства итераций задача распараллеливания гнезда циклов (1) ставится как задача разбиения множества на подмножества такие, что вычисления тела цикла в каждом из них могут быть выполнены одновременно (с сохранением информационных связей исходного цикла, естественно).

Рис. 1.  Общая структура распараллеливающего компилятора.

В зависимости от типа областей выделяют несколько методов распараллеливания циклов:

• метод параллелепипедов;
• метод гиперплоскостей;
• метод пирамид.

• тело цикла не содержит условных и безусловных переходов вне тела;
• внутри тела цикла передача управления осуществляется только вперед;
• тело цикла не содержит операторов ввода-вывода и обращений к подпрограммам;
• все индексные выражения линейны, т.е. отсутствуют индексы вида ;
• отсутствует косвенная адресация вида ;
• индексы не изменяются в теле цикла;
• выполнено условие Рассела – в теле цикла не используется простая неиндексированная переменная раньше, чем этой переменной в теле цикла присваивается некоторое значение, например,

FOR i=1, N
  S:= S + X(i)

Здесь начальное значение переменной , полагается, присвоено вне цикла.

Рассмотрим следующее гнездо циклов

(2)

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

Рис. 2.  К прим. 1 Структура информационных связей в теле цикла

Из рис. 2 следует, что в цикле (2) информационно связаны, например, следующие итерации (на рисунке выделены жирным):

Из структуры информационных связей следует, что пространство итераций можно разбить на параллелепипеды так, как показано на рис. 3.

Рис. 3.  Разбивка пространства итераций на параллелепипеды.

Для случая, показанного на Рис.3 (а), вычисления могут быть организованы по следующей схеме:

parbegin
  X(2,2):= X(1,1)**2;
  X(2,3):= X(1,2)**2;
  X(2,4):= X(1,3)**2
parend;
parbegin
  X(3,2):= X(2,1)**2;
  X(3,3):= X(2,2)**2;
  X(3,4):= X(2,3)**2
parend;
..............

Аналогично, для случая, показанного на рис. 3 (б), вычисления могут быть организованы по следующей схеме:

parbegin
  X(2,2):= X(1,1)**2;
  X(3,2):= X(2,1)**2;
  X(4,2):= X(3,1)**2;
  X(5,2):= X(4,1)**2
parend;
parbegin
  X(2,3):= X(1,2)**2;
  X(3,3):= X(2,2)**2;
  X(4,3):= X(3,2)**2;
  X(5,3):= X(4,2)**2
parend;
..............

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

Пример 2. Рассмотрим следующее гнездо циклов

FOR i=1, l DO
FOR j=2, m DO
FOR k=2, n DO
x(j,k):= f(x(j + 1, k),x(j , k + 1),x(j - 1, k),x( j, k - 1));

Здесь пространство итераций (является трехмерным), , .

В рассматриваемой программе в каждой точке вычисление значения производится с использование значений в 4-х соседних точках. Причем соседи , точки , которые ближе к началу координат, лежат в плоскости , а соседи этой точки , которые расположены дальше от начала координат, лежат в плоскости . Другими словами, при вычислении при значения , уже вычислены при этом , а значения , — еще не вычислены, т.е. являются "старыми", вычислены при .

Например, при вычислении при используются точки , , которые еще не пересчитаны при данном (т.е. лежат на плоскости ), а также точки , , которые уже пересчитаны при данном (т.е. лежат в плоскости ) – см. Рис.4.

Рис. 4.  К прим. 2 m = n = 7. Точки a, b лежат на прямой k = -j + 7, а точки c, d — на прямой k = -j + 5.

Все точки пространства итераций, лежащие на плоскостях, проходящих через прямые

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

1. В цикле выбираются все результирующие итерации, т.е. итерации, "вырабатывающие" переменные, не используемые далее в теле цикла. Каждая такая итерация послужит основой для формирования отдельной параллельной ветви и будет последней итерацией в этой ветви.
2. Ветвь формируется включением в нее всех итераций, которые информационно связаны с выделенной итерацией. Затем аналогично в ветвь включаются все итерации, информационно связанные с уже выделенными итерациями и т.д.

Рассмотрим гнездо циклов

FOR j=1, n DO
  FOR k=2, 5 DO
    x(j, k):= x(j + 1, k) + x(j, k - 1));

Итерации, соответствующие этому гнезду циклов, имеют вид

Таблица 1    

		(, )
1	2	(1,2) = (2,2) + (1,1)
1	3	(1,3) = (2,3) + (1,2)
1	4	(1,4) = (2,4) + (1,3)
1	5	(1,5) = (2,5) + (1,4)
2	2	(2,2) = (3,2) + (1,1)
2	3	(2,3) = (3,3) + (1,2)
2	4	(2,4) = (3,4) + (1,3)
2	5	(2,5) = (3,5) + (1,4)
...	...	...

При вычислении последней итераций является итерация . Поэтому в методе пирамид первая ветвь имеет вид

При вычислении последней итераций является итерация , в которой используется ранее вычисленная переменная . Поэтому вторая ветвь имеет вид

Аналогично, для третьей ветви

и четвертой ветви

И т.д

1. Обмен данными между процессорами через коммуникационную систему требует значительного времени (латентность коммуникационной системы велика по сравнению со временем выполнения одной машинной команды). Поэтому вычислительная работа должна распределяться между процессорами крупными порциями. Для автоматического распараллеливания на векторно-конвейерных вычислительных системах и векторно-параллельных вычислительных систем достаточно проанализировать на предмет возможности параллельного выполнения только внутренние циклы программы. В случае мультикомпьютеров и вычислительных кластеров приходилось анализировать объемлющие циклы для нахождения более крупных порций работы. Однако крупные фрагменты программы могут включать в себя вызовы процедур и функций, что требует сложного межпроцедурного анализа.
2. В отличие от многопроцессорных ЭВМ с общей памятью, на системах с распределенной памятью необходимо произвести не только распределение вычислений, но и распределение данных. Наличие распределенных данных порождает проблему обеспечения эффективного доступа к удаленным данным. Эта проблема требует анализа индексных выражений не только внутри одного цикла, но и между разными циклами, а также поиска сегментов данных, которые должны быть пересланы с одного процессора на другой.
3. Распределение вычислений и данных по процессорам вычислительной системы должно быть произведено таким образом, чтобы обеспечить сбалансированность загрузки процессоров. Несбалансированность загрузки процессоров может привести к тому, что параллельная программа будет выполняться гораздо медленнее исходной последовательной программы.