12 .Метод пирамид.
*В методе пирамид в исходном пространстве итераций выделяются независимые параллельные ветви, каждая из которых представляет собою «дерево» зависимых итераций, корень которого – одна из результирующих итераций исходного цикла. Если индексные выражения в теле цикла линейно зависимы, то итерации каждой параллельной ветви образуют пирамиду (в случае двумерного пространства итераций это – угол между некоторыми крайними векторами). Очевидно, что при таком порядке формирования ветвей в них неизбежно дублирование некоторых итераций.
Э
тот
метод используется в вычислительных
системах со стековой организацией, в
которых крайне нежелателен обмен
информацией между параллельными
процессами и затруднена синхронизация
между ними.
Если имеются такие ограничения, то исходное гнездо циклов требуется преобразовать таким образом, чтобы все параллельные ветви были автономны. То есть все использования переменных одной ветви соответствовали генерациям той же самой ветви.
Для этого:
1. в цикле выбираются все результирующие итерации. Каждая такая итерация служит основой отдельной параллельной ветви.
2. каждая ветвь формируется путем включения в нее всех итераций, информационно связанных с ранее включенными в эту ветвь итерациями.
«-»:необходимость дублирования некоторых операций в разных ветвях.
При ленейно-независимых индексных выражениях итерации каждой ветви образуют пирамиду в пространстве итераций, «натянутую на векторы», задающие направление зависимостей внутри итераций.
ПРИМЕР:
DO 10 I1=1,R1
DO 10 I2=1,R2
<ТЕЛО ЦИКЛА>
10 Continue
После использования метода пирамид получаются конструкции вида:
DO 10 CONC FOR ALL K{1,…,Rr}
DO 10 I1=1,R1
DO 10 I2=MAX{1,K-[(R1-I1)G2/G1]}, MIN{R2,K+[(R1-I1)H2/H1]}
<ТЕЛО ЦИКЛА>
10 Continue
Д
ля
векторно-конвейерной системы (SIMD)
метод пирамид очень неэффективен.
13. Распараллеливание линейных участков программ.
Распараллеливание линейных участков
Распараллеливание линейных участков применяется главным образом в системах с магистральной обработкой данных, когда одна команда разбивается на ряд последовательных микроопераций, выполняющихся над несколькими аргументами параллельно.
Факторами резко снижающим эффективность таких систем являются:
- команды условных и безусловных переходов,
- информационная зависимость операторов,
- косвенная адресация.
В настоящее время считается, что основной выигрыш при распараллеливании линейных участков получается при выявлении параллелизма на уровне отдельных операторов.
Рассмотрим i-тый участок памяти. Все переменные, которые изменяются на этом учаcтке можно отнести к одной из четырех категорий:
Только считываемые переменные Wi
Только записываемые переменные Xi
Сначала считываемые, а потом записываемые Yi
Сначала записываемые, а потом считываемые Zi
С учетом таких обозначений для любой пары операторов P1 и P2 на этом участке должны выполняться следующие соотношения:
(W1Y1Z1)(X2Y2Z2)=0
(X1Y1Z1)(W2Y2Z2)=0
Если эти условия выполняются, то операторы независимы и могут быть выполнены параллельно.
Алгоритм
Для рассмотрения одного из возможных алгоритмов распараллеливания введем следуюшие обозначения:
Ii – входные данные для i-того оператора, т.е. переменные в правой части оператора присваивания
Oi –выходные данные, т.е. переменные в левой части оператора присваивания.
Для независимости двух операторов i-го и j-го необходимо выполнения следующих соотношений:
Проверка этих условий является основной частью алгоритма автоматического выполнения параллелизма.
П
РИМЕР:
Пусть исходный линейный участок задан
орграфом
Есть матрица смежности для него
C
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Матрица передачи управления
L
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Очевидно, что для распараллеливания необходимы еще входные/выходные данные. Они так же представляются булевскими матрицами m на n, где n строк представляют операторы, а m столбцов - идентификаторы переменных. В нашем случае 5 переменных, поэтому матрица 8 строк и 5 столбцов
I
|
1 |
2 |
3 |
4 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
0 |
3 |
1 |
0 |
0 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
6 |
0 |
1 |
0 |
0 |
0 |
7 |
0 |
0 |
1 |
1 |
0 |
8 |
0 |
0 |
0 |
0 |
1 |
O
|
1 |
2 |
3 |
4 |
5 |
1 |
0 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
1 |
0 |
0 |
4 |
0 |
0 |
0 |
1 |
0 |
5 |
0 |
0 |
1 |
0 |
0 |
6 |
0 |
0 |
0 |
1 |
0 |
7 |
0 |
0 |
0 |
0 |
1 |
8 |
0 |
0 |
0 |
0 |
0 |
В этих матрицах соответствующий элемент равен единице в том случае если переменная с номером j является входной для оператора I. Для матрицы O, соответственно, та же единица соответствует выходной.
В результате работы предлагаемого алгоритма будет получена матрица Cp и Lp, которые однозначно описывают параллельную форму для исходного алгоритма, и соответствующая граф схема (уже параллельная) будет выглядеть так.
Для построения матрицы Cp сначала строится матрица последовательности выполнения операторов для исходного участка, матрица P.
P
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
5 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
7 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
8 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
В ней отображен порядок следования операторов.
Для построения матрицы Cp необходимо простроить две матрицы Pp (матрица неполного параллелизма) и Lp (матрица параллельной логики).
Алгоритм построения матрицы CP.
Стоятся вспомогательные матрицы Pp=P (матрица неполного параллелизма) и Lp=L (матрица параллельной логики)
Для всех пар (i, j), для которых элемент матрицы P равен единице («1»), вычисляется функция
IOij = (Ij Oi) (Ii Oj) (Oi Oj)
Если IOij = 0, то операторы i и j – независимы, т.е их можно выполнять параллельно или сохранить последовательность выполнения, для этого случая соответствующий элемент матрицы P устанавливается в нуль (PPij = 0).
Для сохранения логических связей вычисляется элементы
LPi = Li Lj,
где:
Li – i-тая строка матрицы Lp
Lj – j – итая строка матрицы L
В результате логическая связь, ведущая к оператору j будет идти и к оператору i.
Строится вспомогательная матрица Cp’= PP (
),
в которой сохраняются только прямые
связи длиной 1.Находим искомую матрицу Cp = Lp Cp’.
Данные матрицы имеют следующий вид:
Pp
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Lp
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Cp
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Недостатки алгоритма.
Все входящие и выходящие переменные рассматриваются как элементарные, анализ элементов не производиться, что влияет на качество полученной параллельной формы.
Если в исходной программе для экономии памяти один и тот же идентификатор обозначает разные переменные, то фактически независимые операторы будут считаться информационно-связанными.
ПРИМЕР:
1 A=B+C
2 D=A+E
3 A=X+Y
4 F=A*Z
1 A1=B+C
2 D=A1+E
3 A=X+Y
4 F=A*Z
На этом линейном участке все операторы должны выполнятся строго последовательно, однако если переписать как указано ниже, то пары операторов 1,2 и 3,4 являются независимы и могут выполнятся параллельно.
Виды зависимостей между переменными:
Информационная;
Конкуренционная:
1 типа;
2 типа;
Транзитивная;
Логическая.