Мелкозернистый параллелизм

ЛЕКЦИЯ 5.

Мелкозернистый параллелизм обеспечивается за счет параллелизма внутри базовых блоков (ББ), которые являются частями программ, не содержащими

условных и безусловных переходов. Этот вид параллелизма реализуется блока-

ми одного процессора: различными АЛУ, умножителями, блоками обращения к

памяти, хранения адреса, переходов и так далее.

Принципы распараллеливания и планирования базовых блоков.

Размер ББ и его увеличение.Базовые блоки невелики по размеру (5 − 20

команд) и даже при оптимальном планировании параллелизм не может быть

большим. На рисунке точками представлена экспериментальная зависимость

ускорения от размера базового блока. Поле полученных в экспериментах ре-

зультатов ограничено контуром (точками представлены значения для некото-

рых ББi).

	r

w

На основе рисунка с учетом вероятностных характеристик контура ре-

зультатов можно получить следующую качественную зависимость:

h = a + b w,

где a и b — константы (a ≈ 1, b ≈ 0,15), h - средняя ширина параллелизма (чис-

ло параллельных ветвей), w – число команд в программе. Следовательно,

можно сказать, что

Здесь: tпар и tпосл – времена параллельного и последовательного исполнения одного и того же отрезка программы.

Таким образом, основной путь увеличения скалярного параллелизма про-

граммы − это удлинение ББ, а развертка − наиболее простой способ для этого.

Цикл:

DO 1 I=1,N

C(I) = A(I) + B(I)

1 CONTINUE

имеет небольшую длину ББ, но ее можно увеличить путем развертки приведен-

ного цикла на две, четыре и так далее итераций, как показано ниже

DO 1 I=1,N,2

C(I) = A(I) + B(I)

C(I+1) = A(I+1) + B(I+1)

1 CONTINUE

DO 1 I=1,N,4

C(I) = A(I) + B(I)

C(I+1) = A(I+1) + B(I+1)

C(I+2) = A(I+2) + B(I+2)

C(I+3) = A(I+3) + B(I+3)

1 CONTINUE

К сожалению, развертка возможна только, если:

• все итерации можно выполнять параллельно;

• в теле цикла нет условных переходов.

Метод Фишера. Существует большое количество методов увеличения па

раллелизма при обработке базовых блоков . Но в большинстве случаев тело

цикла содержит операторы переходов. Достаточно универсальный метод пла-

нирования трасс с учетом переходов предложил в 80-е годы J.Fisher . Рас-

смотрим этот метод на примере рисуна. На схеме в кружках представлены но-

мера вершин, а рядом − вес вершины (время ее исполнения); на выходах опера-

торов переходов проставлены вероятности этих переходов.

Возможны три варианта путей исполнения тела цикла:

• путь 1-2-4 обладает объемом вычислений (5+5+5) и вероятностью

0.8*0.8=0.64;

• путь 1-2 имеет объем вычислений 5+5 и вероятность 0.8*0.2=0.16;

• путь 1-3 имеет объем вычислений 5+1 и вероятность 0.2.

Примем путь 1-2-4 в качестве главной трассы. Остальные пути будем считать простыми трассами. Ограничимся рассмотрением метода планирования трасс только по отношению к главной трассе.

Если метод планирования трасс не применяется, то главная трасса состоит из трех независимых блоков. Суммарное время выполнения этих блоков будет в соответствии с вышеприведенными формулами равным:

В методе планирования трасс предлагается считать главную трассу единым ББ, который выполняется с вероятностью 0,64. Если переходов из данной трассы в другие трассы нет, то объединенный ББ выполняется за время

Таким образом, выигрыш во времени выполнения главной трассы составил Т1/Т2 = 1.8 раз. В общем случае при объединении k блоков с равным временем исполнения w получаем:

При построении ЯПФ объединенного ББ и дальнейшем планировании команды могут перемещаться из одного исходного ББ в другой, оказываясь выше или ниже оператора перехода, что может привести к нарушению логики выполнения программы.

Чтобы исключить возможность неправильных вычислений, вводятся ком-

пенсационные коды. Рассмотрим примеры рисунок. Пусть текущая трасса

(рис.а) состоит из операций 1, 2, 3. Предположим, что операция 1 не являет-

ся срочной и перемещается поэтому ниже условного перехода 2. Но тогда опе-

рация 4 читает неверное значение a. Чтобы этого не произошло, компилятор

вводит компенсирующую операцию 1 (рис.б).

Пусть теперь операция 3 перемещается выше оператора IF. Тогда операция 5 считает неверное значение d. Если бы значение d не использовалось на расположенном вне трассы крае перехода, то перемещение операции 3 выше оператора IF было бы допустимым.

г)

Рассмотрим переходы в трассу извне. Пусть текущая трасса содержит операции 1, 2, 3 (рис.в). Предположим, что компилятор перемещает операцию 3

в положение между операциями 1 и 2. Тогда в операции 3 будет использовано

неверное значение a. Во избежание этого, необходимо ввести компенсирующий

код 3 (рис.г).

Порядок планирования трасс для получения конечного результата таков:

1. Выбор очередной трассы и ее планирование (распараллеливание и размещение по процессорам).

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

операций.

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

Основным объектом распараллеливания в области скалярного параллелизма являются базавые блоки. Если ББ представлен на язык высокого уровня, тогда распараллеливанию подвергаются арифметические выражения. Если ББ

представлен на ассемблер или в машинных кодах, то распараллеливается отре-

зок программы. Эти операции отличаются. Далее будут рассмотрены оба под-

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