4.2 Процедура приводимости к ппф

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

Алгоритм преобразования программы к ппф

1. Заменить каждую максимально-параллельную цепочку параллельным групповым оператором ( оператор является либо параллельным участком или взаимно параллельными участками)

{ S_i, S_i+1, … , S_i+n}

2. Заменить каждую максимально последовательную цепочку последовательным групповым оператором:

{ S_{i →} S_i+1, S_{i+1 →} S_i+2, … , S_{i+(k-1) →} S_i+k} → S_i+k

{ S_i, S_i+1, … , S_i+k}

3. Повторять шаги 1 и 2 до тех пор, пока не останется ни одной максимально паралельной либо максимально последовательной цепочек. В результате программа имеет вид одного участка, называемого ППФ.

Пример (на основе графа управления программой (рис .3)):

Рисунок 3 – Пример приведения программы К ППФ

4.3 Метод формирования параллельных групповых операторов

Обозначение множеств:

1. U – множество всех S_i операторов программы.

2. U_i – множество операторов программы (элементарных и групповых, рассмотренных на i-ом шаге программы);

3. _{i -} множество всех параллельных групповых операторов программы, полученных до i-го шага и на i-м шаге включительно.

4. _i‘ - множество параллельных операторов, формирующих групповой оператор на i-ом шаге.

_i-1 + _i ‘ = _i

5. K_i – множество последовательных операций, не входящих в параллельные участки, то есть те операторы, для которых будет применяться алгоритм распараллеливания. Таким образом, метод формирования групповых операторов направлен на выделение из множества U_i всех операторов программы, множеств операторов являющихся параллельными и операторов, являющихся последовательными (не входящими в _i‘).

Шаги алгоритма:

1. Руководствуюсь понятиями зависимости и независимости операций сформировать матрице независимости C ⁱ_pq для одиночных и групповых операторов, рассмотренных на i-м шаге. Строки p и столбцы q идентифицируются одинаковым образом операторами, рассмотренными на i-м шаге.

2. Если операторы S_i и S_q являются независимыми, то элемент С[p,q]=1.

3. Для любого S_p обозначим С[p,q]=1 при p=q

4. Обозначим

p={k, k+1, k+2, …}

q={…, m-2, m-1, m}

Алгоритм предполагает выделение последовательных операторов S_k, S_k+1, S_m-1, S_m, для которых выполнялось бы условие:

С[p,q]=1.

И при этом элементы С[p,q] образуют квадратную матрицу порядка n’ , где r n’ n

5. Если таких матриц несколько, то выбирается та, у которой номера операторов являются наименьшими

Таким образом, операторы S_k, S_k+1 представляют собой вышестоящие операторы (индексы строк), S_m, S_m-1 – нижестоящие (индексы столбцов), а сама процедура определяет порядок просмотра матрицы независимости C ⁱ_pq и выделения в ней квадратной матрицы. Сама последовательность S_k, S_k+1, S_m-1, S_m определяет независимые нижестоящие операторы от вышестоящих.

Пример:

Матрица (2) не может быть интерпретирована, так как номера операторов в ней больше, чем в (1). Матрица (3) не может быть интерпретирована, так как по ней не может быть сформирована последовательность операторов S_k, S_k+1, S_m-1, S_m, где S_k – вышестоящие операторы программы.

6. Отнести сформированную последовательность к множеству _i‘ (параллельных операторов, выделяемых на i-ом шаге), остальные операторы к множеству k_i.

7. На основе множества _i‘ сформировать параллельный групповой оператор, рассмотренный в множестве U_i+1.

Таким образом, на основе анализа множества _i‘ может быть осуществлено разворачивание ППФ к ее графу параллельного выполнения.

Пример разворачивания: U_n = {S_7, } представлен на рис .4.

Рисунок 4 – Пример разворачивания ППФ(1)

U_{n-1 =} { }

_n-1 = { }

U_{n-2 =} { }

U_{n-3 =} { }

U_{n-4 =} { }

_n-4 = { S_4, S₅}

U_{n-5 =} { S_1, S_2, S_3, S_4, S_5, S_6, S₇ }

_n-4‘ = { S_1, S₂}

Рисунок 5 - Пример разворачивания ППФ(2)

Прямая процедура предполагает формирование множеств U_i, _i^’ при разворачивании ППФ множество интерпретируется в обратном порядке шагов.