6.1 Постановка задачи распараллеливания

Любая операция а_j , входящая в состав участка  (выражения) представлена в виде:

а_j = {j, _j, in а_j, out а_j, w_j, | in а_j|, | w_j | } (6)

| | - мощность (количество элементов, входящих в множество);

_{j -} тип операции, определяет как выполнимое вычислительное действие, так и количество входных в операцию переменных.

in а_j - множество переменных, являющихся входными в данный оператор а_j;

out а_j - множество результатов;

w_{j –} множество номеров операций , использующих результаты данной j-ой операции;

_j позволяет определить те выражения, на основании которых идентифицируется возможность выполнения данной j-ой операции на k-ый ярус ЯПФ.

Множество w_j, использование которого определяет возможность вычленения последовательных операций на (к+1), (к+2), …, (к+n) ярусы ЯПФ.

Если обозначить через J_ множество номеров операций -го участка, то при

W_j = {j_1, j_2, j_{3, …,} j_n}

j J_, j₁ J_, j₂ J_,, … , j_n J_

Требования для операций J_i

1. j j_i (операция не может использовать собственный результат).

2. Для любой операции j_i in a_ji a_j 0. Таким образом, в W_j перечисляются номера всех операций, использующих результаты j.

3. Любая операция j_i является входящей в участок программы:

j_i J_.

Правила построения таблицы для распараллеливания

Метод распараллеливания предполагает формирование множества операций: ^*A_{t ,} ⁺A_{t ,} ^pA_{t ,} ^-A_t.

Для каждого дискретного момента времени, сопоставляемого с некоторым ярусом ЯПФ, таким образом, цель метода распараллеливания состоит в формировании указанных множеств. Реализация метода выполняется на основе таблицы №1, формируемой в соответствии с формулой (6).

Таблица №1 – Правила формирования множеств для распараллеливания

№ n/n

Тип операции

Входные операнды (dp1, dp2, …, dpn)

Результаты dj

Wj

|in aj|

| wj|

Правила:

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

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

3. Вычисления внутри каждого участка должно заканчиваться выполнением операции присваивания его результата некоторой переменной.

Для реализации оптимального распараллеливания должно выполняться уникальное именование результатов каждой из операций.

6.2 Условия формирования множества *Aк (функция f1 - функция двумерной модели)

1. Готовность операции к выполнению (a_j ^*A_к) :

^*A_к =

Для (7) - данная операция a_j представляет собой присваивание значений внешних по отношению к участку внутренним в этом участке именам.

Для (8) – Out ^pa_ij - множество переменных результатов, сформированных на предшествующих ярусах от 0 до (k-1), которые используются при вычислении данной операции a_j.

Результирующий вид:

In a_j 