Алгоритм распараллеливания ациклических участков программы состоит из четырех этапов:
Построение графа зависимостей по данным.
Граф зависимостей по данным между операторами программы (Data Dependence Graph, DDG) строится на основе информационной, логической и конкуренционной зависимости между операторами программы. Заметим, что о зависимости по данным можно говорить на разных уровнях — от отдельных инструкций, до более крупных программных блоков.
Информационная зависимость между операторами программы. Оператор зависит от оператора A информационно, если оператор "вырабатывает" некоторую переменную , которую использует оператор . Другими словами, оператор зависит от оператора информационно, если 1)существует путь от входного оператора программы, проходящий через операторы , , и 2)оператор является последним перед оператором этого пути, "вырабатывающий" значение переменной , которое используется оператором .
Формально информационную зависимость оператора от оператор можно записать в следующем виде:

где — совокупность входных переменных оператора , — совокупность выходных переменных оператора , – пустое множество.
Логическая зависимость между операторами программы. Оператор B зависит от оператора логически, если 1)существует путь от входного оператора программы до оператора и 2)оператор является "распознавателем", решающим будет или нет выполняться оператор .
Конкуренционная зависимость между операторами программы. Операторы , зависят друг от друга конкуренционно, если 1)существуют пути от входного оператора программы как до оператора , так и до оператора , и 2)операторы и "вырабатывают" одну и ту же переменную .
Формально конкуренционную зависимость операторов , можно записать в следующем виде:

Пример 1
Пример 1. Рассмотрим следующую задачу. Пользователь вводит относительные адреса x, y начала и конца массива. Известно, что переменная, имеющее наибольшее значение соответствует концу массива, а переменная, имеющая наименьшее значение, – началу массива. Требуется распечатать массив, а также нижнюю и верхнюю его границы.
Рассмотрим также следующую программу, которая решает поставленную задачу (слева даны обозначения операторов программы; c – база массива):
A  ввод (x, y);
B  l := x;
C  h := y;
D  v := c+x;
E  z := c+y;
P  если x>y то F иначе G;
F  h := x; l := y;
G  печать от min (z, v) до max (z, v);
H  печать (l, h);
Граф зависимостей этой программы изображен на рис. 1. Конкуренционная зависимость в программе имеет место, поскольку ()()O, ()()O
Рис. 1.  К примеру 1. Граф зависимостей программы.
Большой размер графа усложняет последующие этапы распараллеливания программы. Для уменьшения размера графа целесообразно произвести сжатие линейных участков программы в обобщенные операторы, т. е. выделить в исходном графе линейные подграфы и поставить в соответствие каждому из них одну обобщенную вершину графа. Сохраним за преобразованным графом обозначение . Таким образом, вершинами графа являются операторы исходной программы, а также фрагменты исходной программы в виде линейных участков.
Построение ярусно-параллельной формы программы.
Алгоритм построения ярусно-параллельной формы программы:
  1. На первый ярус ЯПФ заносятся все операторы, в которые не идут стрелки графа зависимостей ;
  2. Если построено ярусов, то в -й ярус заносятся все те операторы, которые имеют входящие стрелки только от первых k ярусов.
Пример 2
Построим ЯПФ для программы, граф зависимостей которой приведен на рис. 2.
Входящие стрелки отсутствуют только у оператора . Поэтому на первый ярус ЯПФ помещаем только этот оператор.
Входящие стрелки только от операторов 1-го яруса имеют операторы , , , , . Поэтому помещаем их на второй ярус.
Входящие стрелки только от операторов 1-го и 2-го ярусов имеют операторы , . Помещаем их на третий ярус.
Наконец, входящие стрелки только от операторов 1-го, 2-го и 3-го ярусов имеет только оператора . Помещаем этот оператор на четвертый ярус (см. рис. 2)
Рис. 2.  Ярусно-параллельная форма для программы, граф зависимостей которой приведен на рис. 1.
Из алгоритма построения ЯПФ следует, что все операторы, находящиеся на одном уровне этой формы могут выполняться параллельно. Ярус ЯПФ иногда называется уровнем готовности операторов.
Ярусы ЯПФ устанавливают между операторами отношение предшествования — к моменту начала вычислений на -м ярусе должны быть закончены вычисления на -м ярусе.
С ЯПФ связан ряд важных понятий. Высотой ЯПФ называется количество ее ярусов. Шириной яруса ЯПФ называется количество операторов на этом ярусе. Шириной ЯПФ называется максимальная из ширин ярусов данной ЯПФ. ЯПФ данного алгоритма, имеющая минимальную высоту, называется минимальной ЯПФ или максимально-параллельной ЯПФ. Ширина минимальной ЯПФ называется шириной алгоритма, а ее высота – высотой алгоритма. Ширина алгоритма и высота алгоритма представляют собой примеры мер параллелизма алгоритма.
Составление по ЯПФ параллельной программы.
Рассмотрим использование ЯПФ для разбиения последовательной программы на легковесные процессы (нити) с целью выполнения программы на мультикомпьютере. В главе 1 мы отмечали, что в этом случае накладные расходы на коммуникацию минимальны, поскольку все нити разделяют одно адресное пространство, а синхронизационные операции выполняются проще и быстрее, чем для обычных процессов.
Очевидно, что разбиение программы на нити многовариантно. В качестве критерия оптимальности разбиения естественно использовать время выполнения программы. Для определения этого времени в качестве веса узлов графа зависимостей по данным используем время выполнения этих узлов в последовательной программе.
Время выполнения узла может быть найдено с помощью профилирования программы. Для получения более точных результатов можно воспользоваться аппаратными таймерами, имеющимися на большинстве современных мультипроцессоров.
Поскольку целью разбиения является получение выигрыша по времени, количество нитей, на которые производится разбиение, обычно принимается равным количеству процессоров в системе. По этой же причине при разбиении следует стремиться к тому, чтобы времена выполнения всех нитей были достаточно близки друг к другу (задача балансировки загрузки – см. главу 1).
Разбиения выполняется последовательно по ярусам ЯПФ – к моменту начала разбиения -го яруса должно быть закончено разбиение -го яруса. При разбиении на -ом ярусе для каждого узла производится локально оптимальный выбор нити, в которую он должен быть включен — делается попытка включить его в каждой из имеющихся нитей, после чего выбирается лучший вариант. Очевидно, что при этом каждый раз производится пересчет времени выполнения каждой из нитей. Оптимизация должна производиться с учетом потерь времени на синхронизацию нитей, если они обмениваются между собой данными. Организация синхронизации нитей также является задачей рассматриваемого этапа распараллеливания.
Эффективность мультипроцессорной программы в значительной мере зависит от эффективности использования ею кэш-памяти, поскольку близко расположенные в памяти данные преимущественно размещаются в более быстрой кэш-памяти. При разбиении программы на нити это обстоятельство также следует учитывать (путем эмуляции кэш-памяти процессора, на котором будет выполняться данная нить, и соответствующей корректировки времени выполнения узла).
Отображение полученной программы на архитектуру используемой параллельной вычислительной системы.
Положим, что исходная последовательная программа разбита на нити так, как описано в предыдущем разделе. Поскольку количество нитей равно количеству процессоров в мультипроцессоре, данный этап не представляет сложности.