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

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

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

<name-domain>::=<token code>

Значения поля <dependencies> таблицы в зависимости от типа оператора:

Значением поля <term-dependencies> таблицы является ссылка на список зависимостей следующего вида:

Структура элемента term-dependency в зависимости от типа терма арифметического или логического выражения (для термов других типов информационная зависимость отсутствует и они поэтому в таблицу не заносятся):

<name-scalar>::=<token code>

<name-var>::=<token code>

<name-result>::=<token code>

<ind-expr>::=<sequence of token codes>

<new-ind-expr>::=<sequence of token codes>

<need-domain>::=<token code>

Значением поля <parameter-dependencies> таблицы является ссылка на список зависимостей следующего вида:

Структура элемента param-dependency в зависимости от типа параметра раздела (для параметров других типов информационная зависимость отсутствует и они поэтому в таблицу не заносятся):

<name-var>::=<token code>

<need-domain>::=<token code>

Для оптимизации алгоритмов анализа и обработки информационных зависимостей между переменными компилятор использует также две вспомогательные таблицы - Таблицу ‘Что-вычисляется’ (What-compute table) и Таблицу ‘Где-вычисляется’ (Where-compute table).

3.12.1Таблица ‘Что-вычисляется’ (What-compute table)

Строка Таблицы ‘Что-вычисляется’ (What-compute table) имеет вид:

<statement number>::=<integer>

<name-variable>::=<token code>

<name-domain>::=<token code> OR ‘S’

Эта информация означает, что в операторе с номером statement number вычисляется переменная с именем name-variable на области name-domain (если name-variable - имя скалярной переменной, то <name-domain>=’S’).

3.12.2Таблица ‘Где-вычисляется’ (Where-compute table)

Строка Таблицы ‘Где-вычисляется’ (Where-compute table) имеет вид:

<statement number>::=<integer>

<name-variable>::=<token code>

<name-domain>::=<token code> OR ‘S’

Эта информация означает, что переменная с именем name-variable вычисляется в операторе с номером statement number на области name-domain (если name-variable - имя скалярной переменной, то <name-domain>=’S’).

Эта таблица позволяет, в частности, эффективно реализовать проверку свойства однократного присваивания (single assignment) для переменных Норма-раздела.

3.13Таблица тел операторов (Table of operators body)

Таблица тел операторов (Table of operators body) предназначена для хранения тел операторов в форме, ориентированной на генерацию выходной Fortran-программы. У переменных, входящих в операторы, восстановлены индексные выражения, вместо имен, описанных как DOMAIN PARAMETERS, подставлены их значения, имена итерируемых переменных заменены на соответствующие имена переменных-результатов (с предыдущего или текущего шага итерации).

Строка Таблицы тел операторов (Table of operators body) имеет вид:

3.14Таблица форматов ввода-вывода (Table of input-output formats)

Таблица форматов ввода-вывода (Table of input-output formats) предназначена для хранения атрибутов ввода-вывода для input-variable и output-variable.

Строка Таблицы форматов ввода-вывода (Table of input-output formats) имеет вид:

<statement number>::=<integer>

<name-variable>::=<token code>

<name-domain>::=<token code> OR ‘S’

<attribute>::=<sequence of token codes>

Эта информация означает, что переменная с именем name-variable является input-variable или output-variable в операторе с номером statement number на области name-domain (если name-variable - имя скалярной переменной, то <name-domain>=’S’) и имеет атрибуты attribute.

3.15Граф информационных зависимостей (Data dependencies graph (DDG))

DDG G(V,E) - иерархический ориентированный граф. V - множество вершин графа, каждая вершина соответствует некоторому Норма-оператору, итерации или описанию входных или выходных переменных. E - множество дуг графа, которые отображают наличие информационных зависимостей между переменными: если переменная X зависит от переменной Y, то сущемтвуеь дуга e от X к Y.

Все конструкции языка Норма iteration заменяются на специальные вершины графа (iteration-вершины). Iteration-вершинам соответствуют подграфы графа DDG.

Все упорядоченные последовательности операторов (ordered groups - группы предложений Норма-программы, для которых задан режим последовательного выполнения) заменяются на специальные вершины графа (ordered-groups-nodes).

DDG представляется следующей структурой данных: для каждой вершины vV определена строка зависимостей, в которую входят вершины DDG, от которых v зависит.

<dependency-node>::=<node>

<graph-node>::=<node>

<node>::=<statement number> OR <iteration number> OR <ordered group number>

3.16Редуцированныйграф информационных зависимостей (Reduced data dependencies graph (RDDG))

Граф DDG преобразуется в редуцированный граф информационных зависимостей (RDDG). RDDG - иерархический ориентированный ациклический граф.

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

Таким образом, RDDG состоит из MSCS-вершин, iteration-вершин, ordered-groups-вершин и simple-вершин (остальных вершин).

RDDG представляется следующей структурой данных: для каждой вершины vV определена строка зависимостей, в которую входят вершины RDDG, от которых v зависит.

<r-dependency-node>::=<node>

<r-graph-node>::=<node>

<node>::=<statement number> OR <iteration number> OR <ordered group number> OR

<MSCS number>

3.17Список максимальных сильно связных подграфов (List of MSCS)

MSCS - сильно связный подграф графа DDG, который не содержится ни в одном другом сильно связном подграфе графа DDG.

Элемент Списка максимальных сильно связных подграфов (List of MSCS) представляется следующей структурой данных:

3.18Список для представления параллельной ярусной схемы (List for parallel layer scheme representation)

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

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

Parallel layer scheme представляется следующей структурой данных:

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

<layer-number>::=<integer>

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

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

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