normPDr (1158438), страница 2

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

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

Создаваемые структуры данных: data dependencies graph (DDG).

1. редукция графа информационных зависимостей (DDG)

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

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

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

Используемые структуры данных: data dependencies graph (DDG), table of iterations structures.

Создаваемые структуры данных: reduced data dependencies graph (RDDG), list of MSCS.

Интерфейс управления.

Блок Построение графа информационных зависимостей вызывается из блока Синтаксический анализ Норма-раздела.

Блок Построение графа информационных зависимостей вызывает блок Анализ графа информационных зависимостей.

Интерфейс по данным.

Блок Построение графа информационных зависимостей получает table of functional dependencies от блока Синтаксический анализ Норма-раздела.

Блок Построение графа информационных зависимостей передает RDDG блоку Анализ графа информационных зависимостей.

Структура блока построения графа информационных зависимостей.

Блок Построение графа информационных зависимостей состоит из двух основных компонентов:

1. Построение DDG.

Функции: построение графа информационных зависимостей DDG.

1. Построение RDDG.

Функции: построение редуцированного графа информационных зависимостей (RDDG).

4.5Анализ графа информационных зависимостей

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

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

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

Используемые структуры данных: reduced data dependencies graph (RDDG), table of iterations structures.

Создаваемые структуры данных: список для представления parallel layer scheme.

Интерфейс управления.

Блок Анализ графа информационных зависимостей вызывается из блока Построение графа информационных зависимостей.

Блок Анализ графа информационных зависимостей вызывает блок Генератор внутреннего представления Fortran DVM программы.

Интерфейс по данным.

Блок Анализ графа информационных зависимостей принимает RDDG от блока Построение графа информационных зависимостей.

Блок Анализ графа информационных зависимостей передает parallel layer scheme блоку Генератор внутреннего представления Fortran DVM программы.

4.6Генератор внутреннего представления Fortran DVM программы

Функции блока Генератор внутреннего представления Fortran DVM программы:

1. реализация описаний переменных языка Норма: во внутреннем представлении строятся описания переменных и предложения распределения данных на языке Fortran DVM,

Используемые структуры данных: table of distribution indexes, symbol table, constant table, table of domains, table of shadow variables.

Создаваемые структуры данных: table of distributed variables, intermediate representation of Fortran DVM programs.

1. реализация parallel layer scheme - трансляция parallel layer scheme во внутреннее представление на языке Fortran DVM:

1. реализация MSCS-вершин parallel layer scheme - строятся операторы Fortran DVM для MSCS-вершин

2. реализация iteration-вершин parallel layer scheme - строятся операторы Fortran DVM для iteration-вершин

3. реализация ordered-groups-вершин parallel layer scheme - строятся операторы Fortran DVM для ordered-groups-вершин

4. реализация simple-вершин parallel layer scheme - строятся операторы Fortran DVM для simple-вершин

Parallel layer scheme отображается на целевую вычислительную систему с учетом модели ее архитектуры. После того, как такое отображение для анализируемого Норма-раздела построено, учитывается модель памяти (распределенная или общая) и заданное число процессоров. Если анализируемый Норма-раздел является распределенным разделом, то используется модель с распределенной памятью, иначе - модель с общей памятью.

Используемые структуры данных: table of distribution indexes, parallel layer scheme, table of iterations structures, list of MSCS, table of ordered groups, table of shadow variables, symbol table, table of domains, table of operators bodies, table of input-output formats.

Создаваемые структуры данных: intermediate representation of Fortran DVM programs, input variables queue.

Интерфейс управления.

Блок Генератор внутреннего представления Fortran DVM программы вызывается из блока Анализ графа информационных зависимостей.

Блок Генератор внутреннего представления Fortran DVM программы вызывает блок Генератор кода Fortran DVM программы.

Интерфейс по данным.

Блок Генератор внутреннего представления Fortran DVM программы получает parallel layer scheme от блока Анализ графа информационных зависимостей.

Блок Генератор внутреннего представления Fortran DVM программы передает intermediate representation of Fortran DVM programs блоку Генератор кода Fortran DVM программы.

4.7Генератор кода Fortran DVM программы

Функции блока Генератор кода Fortran DVM программы:

1) Перевод внутреннего представления Fortran DVM-программы в текстовую форму (последовательность строк, каждая из которых состоит из последовательности символов) и передача этой формы блоку Генератор листинга.

Используемые структуры данных: symbol table, constant table, intermediate representation of Fortran DVM programs.

Интерфейс управления.

Блок Генератор кода Fortran DVM программы вызывается из блока Генератор внутреннего представления Fortran DVM программы

Блок Генератор кода Fortran DVM программы вызывает блок Генератор листинга и блок Анализатор входных файлов.

Интерфейс по данным.

Блок Генератор кода Fortran DVM программы получает intermediate representation of Fortran DVM programs от блока Генератор внутреннего представления Fortran DVM программы

Блок Генератор кода Fortran DVM программы передает Fortran DVM-программу в текстовой форме блоку Генератор листинга.

4.8Анализатор входных файлов

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

1. Переупорядочивание данных из входных файлов для Норма-раздела и подготовка вводного файла для целевой Fortran DVM-программы,

2. Обнаружение и фиксация ошибок во входных файлах (например, недостаточно данных во входном файле для вводимой переменной, несоответствие типов и т.д.)

Используемые структуры данных: input variables queue, table of input-output formats, symbol table, constant table, table of domains, list of errors.

Интерфейс управления.

Блок Анализатор входных файлов вызывается из блока Генератор кода Fortran DVM программы.

Блок Анализатор входных файлов вызывает блок Завершение компиляции раздела.

Интерфейс по данным.

Блок Анализатор входных файлов читает входные файлы данных для Норма-раздела и создает новый вводной файл для целевой Fortran DVM-программы.

4.9Генератор листинга

Функции блока Генератор листинга:

1. вывод исходных текстов Норма-программы, Fortran DVM-программы, сообщений компилятора в файл <listing-file>,

2. вывод Fortran DVM-программы в файл <target-file>,

3. вывод исходных текстов Норма-программы, Fortran DVM-программы, сообщений компилятора на экран,

4. генерация текстов сообщений об ошибках и предупреждений для соответствующих строк файла <listing-file> или экрана.

Используемые структуры данных: symbol table, list of errors, statements-lines table.

Интерфейс управления.

Блок Генератор листинга вызывается из блока Синтаксический анализ Норма-раздела, блока Генератор кода Fortran DVM программы.

Блок Генератор листинга является интерфейсным (вывод) блоком компилятора.

Интерфейс по данным.

Блок Генератор листинга получает Fortran DVM-программу в текстовой форме от блока Генератор кода Fortran DVM программы.

Блок Генератор листинга читает файл с исходным текстом Норма-программы.

Блок Генератор листинга осуществляетс запись в <target-file>, <listing-file>, отображает <listing-file> на экран.

4.10Завершение компиляции раздела

Функции блока Завершение компиляции раздела:

1. генерация сообщений о процессе компиляции (время компиляции раздела, число ошибок и предупреждений),

2. чистка структур данных.

Используемые структуры данных: структуры данных для компиляции Норма-раздела.

Интерфейс управления.

Блок Завершение компиляции раздела вызывается из блока Анализатор входных файлов.

Блок Завершение компиляции раздела является завершающей частью блока Компиляция Норма-раздела.

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

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