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

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

В терминах пространства итераций задача распараллеливания гнезда циклов (1) ставится как задача разбиения множества на подмножества такие, что вычисления тела цикла в каждом из них могут быть выполнены одновременно (с сохранением информационных связей исходного цикла, естественно).
Распараллеливание циклов производится компиляторами. Если речь идет о распараллеливании для векторно-конвейерной вычислительной системы или для векторно-параллельной вычислительной системы, то такой компилятор называется векторизующим компилятором. Аналогично, если речь идет о распараллеливание циклов для многопроцессорной вычислительной системы, то говорят о распараллеливающем компиляторе, общая структура которого представлена на рис. 1.
На этапе синтаксического анализа производится синтаксический анализ последовательной программы, проверяется выполнение некоторых ограничений на тела циклов (линейность индексных выражений, отсутствие операторов и обращений к подпрограммам и т.п. - см. ниже). Кроме того, на этапе синтаксического анализа оценивается время выполнения программы. Недостающую информацию для такой оценки компилятор может запрашивать у пользователя в диалоговом режиме.
На этапе распараллеливания циклов проверяется выполнение всех необходимых ограничений на тела циклов (в частности, условия Рассела - см. ниже). Здесь же для каждого цикла из множества методов, реализованных в компиляторе, производится выбор метода распараллеливания. Для вложенных циклов анализ производится, начиная с внутренних циклов. Для циклов, которые не распараллеливаются, компилятором выдается информация о конкретных причинах невозможности распараллеливания.
Рис. 1.  Общая структура распараллеливающего компилятора.
На этапе оценки качества распараллеливания оценивается степень распараллеливания каждого из циклов и на этой основе производится оценка ускорения параллельной программы по сравнению с исходной последовательной программой. Если это ускорение является неудовлетворительным, то на основе информации, выданной компилятором на предыдущем этапе, пользователь может попытаться преобразовать циклы так, чтобы они могли быть эффективно распараллелены.
На этапе генерации параллельной программы генерируется программа на параллельном ЯВУ.
На этапе генерации машинного кода компилятор генерирует код для используемой параллельной вычислительной системы.
В зависимости от типа областей выделяют несколько методов распараллеливания циклов:
Методы распараллеливания применимы только при выполнении ряда ограничений на операторы тела цикла. Эти ограничения зависят от типа ЭВМ и метода распараллеливания. Перечислим основные из этих ограничений:
FOR i=1, N
  S:= S + X(i)

Здесь начальное значение переменной , полагается, присвоено вне цикла.
Метод параллелепипедов.
Проиллюстрируем идею метода параллелепипедов распараллеливания циклов на примере.
Пример 1
Рассмотрим следующее гнездо циклов
 (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
Пример 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. Ветвь формируется включением в нее всех итераций, которые информационно связаны с выделенной итерацией. Затем аналогично в ветвь включаются все итерации, информационно связанные с уже выделенными итерациями и т.д.
Таким образом, в методе пирамид каждую ветвь включается вся история вычислений результирующей итерации. При этом, очевидно, различные итерации могут дублироваться в различных ветвях. Для балансировки загрузки процессоров используемой МВС ветви затем могут быть "склеены" так, что суммарная вычислительная сложность итоговых ветвей была примерно одинаковой.
Пример 3
Рассмотрим гнездо циклов
FOR j=1, n DO
  FOR k=2, 5 DO
    x(j, k):= x(j + 1, k) + x(j, k - 1));
Итерации, соответствующие этому гнезду циклов, имеют вид
Таблица 1    
(, )
12(1,2) = (2,2) + (1,1)
13(1,3) = (2,3) + (1,2)
14(1,4) = (2,4) + (1,3)
15(1,5) = (2,5) + (1,4)
22(2,2) = (3,2) + (1,1)
23(2,3) = (3,3) + (1,2)
24(2,4) = (3,4) + (1,3)
25(2,5) = (3,5) + (1,4)
.........

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

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

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

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

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