5. Особенности распараллеливания программы путем приведения ее к ппф

Различные операторы циклов и передачи управления снижают степень эффективности распараллеливания. Поэтом определены правила для интерпретирования входных операторов программ, изменяющих порядок их выполнения:

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

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

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

5.1 Понятие двумерной модели вычислительного процесса

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

Названная модель задается в форме системы уравнений в следующем виде:

q_t=(M₀, P\\_t-1);

A_t =A_t-1\ + A_t-1;

^*A_t=F₁(A_t, q_t);

⁺ A_t=F₂(^*A_t, J);

^PA_t=F₃(⁺ A_t, q_t);

^- A_t=F₄(^p A_t, q_t);

где q_t - текущее состояние памяти (значение информационных и управляющих переменных);

P\\_t-1 - предыстория процесса в момент времени t (вычислительный процесс, выполняющийся до (t-1) шага включительно, вызывающий изменения состояния памяти);

М₀ – начальное состояние памяти (начальные значения переменных);

A_t - множество операций, находящихся к моменту времени t в выключенном состоянии (то есть операции, которые не готовы к выполнению, так как для них не подготовлены исходные данные и соответствующие управляющие сигналы);

^*A_t - множество операций, для которых в текущий момент времени t дано разрешение на включение (для них подготовлены исходные данные, восполнена синхронизация, т.е. готовы быть запущенными);

Таким образом, операции выбирается из A_t такие, что состояние памяти q_t определяет готовые для их выполнения информационно-управляющие переменные.

Множество A_t формируется из множества не включившихся до (t-1) шага операций, исключаются операции, которым на (t-1) шаге дано разрешение на включение. Операции, принадлежащие одному множеству, переводятся в другое множество в момент времени (t-1).

⁺ A_t – множество операций, включающихся в момент времени t;

^PA_t – множество операций, работающих в момент времени t.

Множеств ⁺A_t определяется на основе операций, готовых к включению, с учетом структурно-временных характеристик ВС и свободных ресурсов ВС.

Таким образом, J определяет наличие свободной памяти процессоров, необходимых для активизации задач.

Множество ^PA_t формируется с учетом включившихся в момент t операций на основе текущего состояния памяти.

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

^- A_t – множество операций, выключающихся в момент времени t. Формируется из множества работающих с учетом требуемого для их выключения состояния памяти, то есть работающая операция переводит значение переменных в некоторое требуемое состояние и может быть выключена.