граф зависимостей по данным
Data Dependence Graph
DDG
Граф зависимостей по данным между операторами программы строится на основе информационной, логической и конкуренционной зависимости между операторами программы. Кроме зависимостей по данным между операторами программы широко используются зависимости по данным на более высоком уровне — на уровне более или менее крупных программных блоков.
информационная зависимость между операторами программы
Оператор B зависит от оператора A информационно, если оператор A "вырабатывает" некоторую переменную x, которую использует оператор B.
логическая зависимость между операторами программы
Оператор B зависит от оператора A логически, если 1)существует путь от входного оператора программы до оператора A и 2) оператор A является "распознавателем", решающим будет или нет выполняться оператор B.
конкуренционная зависимость между операторами программы
Операторы A, B зависят друг от друга конкуренционно, если 1)существуют пути от входного оператора программы как до оператора A, так и до оператора B, и 2)операторы A, B "вырабатывают" одну и ту же переменную x.
ярусно-параллельная форма программы
ЯПФ программы
На первый ярус ЯПФ программы заносятся все операторы, в которые не идут стрелки графа зависимостей по данным. Если построено k ярусов, то на (k+1)-й ярус заносятся все те операторы, которые имеют входящие стрелки только от первых k ярусов. Из алгоритма построения ЯПФ следует, что все операторы, находящиеся на одном уровне этой формы могут выполняться параллельно.
ярус ЯПФ
уровень готовности оператора
Уровень готовности оператора - это ярус ЯПФ, на котором находится данный оператор.
высота ярусно-параллельной формы программы
высота ЯПФ программы
высота ЯПФ
Высота ЯПФ программы называется количество ее ярусов в ЯПФ.
ширина яруса ярусно-параллельной форм программы
ширина яруса ЯПФ программы
ширина яруса ЯПФ
Ширина яруса ЯПФ программы называется количество операторов программы на этом ярусе.
ширина ярусно-параллельной формы программы
ширина ЯПФ программы
ширина ЯПФ
Ширина ЯПФ программы называется максимальная из ширин ярусов данной ЯПФ.
минимальная ярусно-параллельной форма алгоритма
минимальная ЯПФ алгоритма
минимальная ЯПФ
максимально-параллельная ярусно-параллельная форма алгоритма
максимально-параллельная ЯПФ
ЯПФ программы, которая соответствует данному алгоритму и имеет минимальную высоту, называется минимальная ЯПФ.
ширина алгоритма
Шириной алгоритма называется ширина минимальной ЯПФ этого алгоритма.
высота алгоритма
Высотой алгоритма называется высота минимальной ЯПФ этого алгоритма.