Зависимость по данным.

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

Программные объекты А и В (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие:

(InB □ ОшА) □ (InA □ OutB) □ (OutA □ OutB) = 0, (2.1)

где In(A) - набор входных, a Out(A) - набор выходных переменных объекта А. Если условие (2.1) не выполняется, то между А и В существует зависимость и они не могут выполняться параллельно.

Если условие (2.1) нарушается в первом терме, то такая зависимость называется прямой. Приведем пример:

A: R = Rl + R2 В: Z = R + С

Здесь операторы А и В не могут выполняться одновременно, так как результат А является операндом В.

Если условие нарушено во втором терме, то такая зависимость называется

обратной:

A: R = Rl + R2 В: Rl = CI + С2

Здесь операторы А и В не могут выполняться одновременно, так как выполнение В вызывает изменение операнда в А.

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

A: R = Rl + R2 В: R = CI + С2

Здесь одновременное выполнение операторов дает неопределенный результат.

Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей.

Наиболее общей формой представления этих зависимостей является информационный граф задачи (ИГ). Пример ИГ, описывающего логику конкретной задачи, дан на рис.2.1. В свое первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.

Рис.2.1. Информационный граф математического выражения и порядок выполнения операций в выражении.

Более определенной формой представления параллелизма является ярусно-параллельная форма (ЯПФ): алгоритм вычислений представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви), не зависящие друг от друга, в первый ярус — операторы, зависящие только от нулевого яруса, во второй — от первого яруса и т. д.

Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: bi - ширина i-ro яруса; В - ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из Ы, i = 1, 2, ...); Ь — длина яруса (время операций) и L длина графа; г — коэффициент заполнения ярусов; 8 — коэффициент разброса указанных параметров и т. д.