normDDr (1158429), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

error code 450 'in lines '<error context>'and in lines'<error context>' reassignment for variable'<error context>

Функция strdep строит на основании Таблицы функциональных зависимостей (Table of functional dependencies) Граф информационных зависимостей (Data dependencies graph (DDG)), в котором в качестве вершин присутствуют только простые вершины (simple-nodes) и пока отсутствуют iteration-nodes и ordered-groups-nodes. Каждой строке Таблицы функциональных зависимостей (Table of functional dependencies) вида

соответствует строка зависимостей DDG вида

Для каждой переменной var, указанной в поле <dependency>, выбирается соответствующая строка Таблицы ‘Где-вычисляется’ (Where-compute table

Если эта строка соответствует переменной скалярного типа, то из строки выбирается <statement number>,который и является значением поля <dependency-node>.

Если строка соответствует переменной, определенной на области, то осуществляется проверка пустоты попарного пересечения всех <name-domains>, указанных в этой строке, и <need-domain>. Значениями полей <dependency-node> являются значения <statement number>, соответствующие непустому пересечению.

Функция pre модифицирует Таблицу функциональных зависимостей (Table of functional dependencies) и приводит ее к виду

исключая все зависимости другого вида. Модифицированная Таблица функциональных зависимостей (Table of functional dependencies) будет использоваться при обработке maximum strongly connected subgraphs (MSCS).

Функция posl осуществляет редукцию DDG, связанную с заменой всех вершин DDG, входящих в ordered groups, на <ordered groups number>, и соответствующей корректировкой зависимостей. Для этой цели используется Таблица последовательных групп (Table of ordered groups). Кроме этого, функция проверяет непротиворечивость порядка вычислений, заданного для ordered groups, и информационных зависимостей для переменных из ordered groups, определенных в DDG и копирует DDG во временный граф zav.

Функция test осуществляет редукцию DDG, связанную с заменой всех вершин DDG, входящих в iteration, на <iteration number>, и соответствующей корректировкой зависимостей.

Алгоритм редукции состоит из трех этапов и использует DDG и Таблицу структуры итераций (Table of iterations structure).

На первом этапе обрабатываются только операторы, входящие в итерации, а вложенные итерации, если они есть, не рассматриваются. Для каждой итерации из Таблицы структуры итераций (Table of iterations structure) выбираются <statement numbers> операторов, входящих в <list of boundary operators>, <list of initial operators>, <body-of-iteration>,<exit-condition>. Во временный граф zavit включаются строки зависимостей из DDG

для которых <graph-node>=<statement numbers>. При этом из списка зависимостей удаляются вершины, для которых <dependency-node>=<statement number>. Таким образом, в строках зависимостей графа zavit остаются только зависимости от операторов, не входящих в итерацию.

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

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

Кроме этого, во всех зависимостях <statement numbers> операторов, входящих в итерацию, заменяется на <iteration number> итерации, в которую эти операторы входят.

Таким образом, в результате работы функции test, построен граф DDG, временный граф zavit и временный граф zav. Две последние структуры будут использоваться при определении порядка выполнения операторов внутри итерации в процессе построения parallel layer scheme.

5.4.2Построение RDDG

Осуществляется поиск максимальных сильно связных подграфов (MSCS). MSCS - сильно связный подграф графа DDG, который не содержится ни в одном другом сильно связном подграфе графа DDG. Далее проводится редукция графа DDG: все MSCS заменяются вершинами специального типа.

Исходной информацией для поиска MSCS служит временный граф zav, вершины которого обозначим через vV, а дуги, выходящие из вершины v - через Adj(v). Алгоритм поиска MSCS (Reingold E.W, Nievergelt J., Deo N. Combinatorial algoruthms. Prentice-Hall, Englewood Cliffs, New Jersey, 1997):

for vV do num(x)=0

i=j=k=0

for vV do if num(x)=0 then FNDCYC(x,0)

procedure FNDCYC(v,u)

i=i+1

num(v)=i

for wAdj(v) do

if num(x)=0

then k=k+1; stack _k  w; FNDCYC(w,v); k=k-1

else

if num(w)<num(v) AND wu

then j=j+1; MSCS_j  (w, stack _k , stack _k-1 ,…,stack _t )

/*comment stack _k = w, stack _t = v endcomment */

endif

endif

Входная точка блока RDDG constructor - функция mssg.

Общая структура управления функции mssg приведена на следующей схеме.

m ssg angr angr1 sumzav sumzv1 angr2

perud1

Функция mssg реализует алгоритм, приведенный выше и строит Список максимальных сильно связных подграфов (List of MSCS).

Дальнейшая обработка связана с редукцией DDG и построением RDDG. Все вершины графа DDG, входящие в некоторый MSCS, заменяются на MSCS-number и, с учетом этой замены, корректируются зависимости.

Для этого рассматриваются все строки зависимостей DDG вида

для которых <graph node>=<statement number>, <statement number>MSCS. Из этих строк формируется одна строка, которая и получает номер MSCS-number. Значения <dependency nodes> для этой строки получаются в результате объединения всех <statement numbers> операторов, от которых зависят операторы, входящие в рассматриваемый MSCS. При этом удаляются повторные вхождения <statement numbers> и номера операторов, входящие в рассматриваемый MSCS.

После того, как все MSCS просмотрены, в графе DDG зависимости от номеров операторов, входящих в некоторый MSCS, заменяются на MSCS-number этого MSCS.

Функция angr выбирает очередной MSCS из Списка максимальных сильно связных подграфов (List of MSCS).

Функция angr1 исключает из обработки MSCS, состоящий из единственного <statement number> (петля в графе DDG).

Функция sumzav объединяет все зависимости операторов, входящих в состав выбранного MSCS. Результат: <statement numders> оператров, от которых зависят операторы из MSCS. Повторные зависимости удалены.

Функция sumzv1 удаляет из полученных предыдущей функцией зависимостей <statement numbers> операторов, входящих в рассматриваемый MSCS.

Функция angr2 дополняет граф DDG новой строкой зависимостей, соответствующей MSCS (у этой строки <graph-node>=<MSCS-number>).

Функция perud заменяет зависимости от номеров операторов, входящих в некоторый MSCS, на MSCS-number этого MSCS.

5.5Анализ графа информационных зависимостей (Data dependencies graph analyser).

Функции блока Анализ графа информационных зависимостей:

1. Частичное упорядочивание редуцированного графа информационных зависимостей (RDDG). Если существует дуга из P в Q (P,Q принадлежат V), то есть Q используеься для вычисления P, то P>Q (Q должна быть вычислена раньше P).

2. Выявление естественного параллелизма. Строится параллельная ярусная схема Parallel layer scheme: вычисления, соответствующие вершинам RDDG и принадлежащие одному и тому же ярусу, могут выполняться параллельно и независимо. Переход от текущего яруса схемы к следующему осуществляется после того, как все вычисления на текущем ярусе закончены.

Структура элемента <layer>:

<layer-number>::=<integer>

<node>::=<statement number> OR <iteration number><Parallel layer scheme> OR

<ordered group number> OR <MSCS number>

Алгоритм упорядочивания RDDG .

В начальный момент на первый ярус Parallel layer scheme помещается RDDG, состоящий из зависимостей вида

Далее на второй ярус переносятся все зависимости, у которых для <graph node> выполняется условие <graph node>=<dependency node> хотя бы для одной <dependency node> хотя бы одной зависимости (другими словами, зависимости для всех операторов, от которых зависят операторы первого яруса). После этого проводится корректировка этих двух ярусов: если зависимость для оператора присутствует на втором ярусе, то она удаляется с первого яруса. Кроме этого, если на первом ярусе оказывается вершина типа <iteration number>, то для нее, используя Таблицу структуры итераций (Table of iterations structure) и временный граф zavit, рекурсивно строится параллельная ярусная подсхема (parallel layer subscheme).

Процедура, определенная выше для первого и второго ярусов, выполняется для второго и третьего ярусов и так далее, пока не возникнет ситуация, когда на очередном ярусе будут только операторы, которые ни от чего не зависят. На этом процесс упорядочивания заканчивается (процесс всегда завершается , так как граф RDDG ацикличный).

Входная точка блока Data dependencies graph analyser - функция pord, которая и реализует данный алгоритм.

Характеристики

Список файлов учебной работы