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

Текст из файла

37

Институт прикладной математики им. М.В.Келдыша
Российская Академия наук

Компилятор C-DVM

Детальный дизайн

Декабрь, 1999

Содержание

1 Назначение компилятора 3

1.1 Запуск компилятора 3

2 Структура компилятора 4

2.1 Структуры данных компилятора 4

2.2 Списковая память 5

2.3 Сканер и строковая память 6

2.4 Коды лексем 7

2.4.1 Терминалы 7

2.4.2 Разделители и операторы 7

2.4.3 Ключевые слова 8

2.4.4 Ключевые слова и идентификаторы C-DVM 8

2.5 Парсер 10

2.6 Структура дерева разбора 10

2.6.1 Терминалы, списки, скобки 10

2.6.2 Описания (СИ) 11

2.6.3 Операторы (СИ) 12

2.6.4 Выражения (СИ) 12

2.6.5 Директивы (C-DVM) 13

2.6.6 Поддирективы (C-DVM) 14

2.7 Преобразование дерева 14

2.8 Генерация 14

3 Компиляция конструкций C-DVM 14

3.1 Распределение данных 15

3.1.1 Директива DISTRIBUTE 15

3.1.2 Формат распределения GENBLOCK 16

3.1.3 Спецификация ONTO 16

3.1.4 Директива REDISTRIBUTE 17

3.1.5 Директива ALIGN 17

3.1.6 Директива REALIGN 18

3.1.7 Поддиректива TEMPLATE 18

3.1.8 Директива CREATE_TEMPLATE 19

3.2 Распределение вычислений (циклы и задачи) 19

3.2.1 Директива PARALLEL 19

3.2.2 Поддиректива ACROSS 20

3.2.3 Директива PROCESSORS и функция NUMBER_OF_PROCESSORS() 20

3.2.4 Директива TASK 21

3.2.5 Директива MAP 21

3.2.6 Директива TASK_REGION 22

3.2.7 Конструкция ON-block 22

3.2.8 Конструкция ON-loop 23

3.3 Теневые грани 23

3.3.1 Поддиректива SHADOW 23

3.3.2 Поддиректива SHADOW_RENEW 23

3.3.3 Директива SHADOW_GROUP 24

3.3.4 Директива CREATE_SHADOW_GROUP 24

3.3.5 Директива SHADOW_START 25

3.3.6 Поддиректива SHADOW_START 25

3.3.7 Директива SHADOW_WAIT 25

3.3.8 Поддиректива SHADOW_WAIT 26

3.4 Удаленный доступ 26

3.4.1 Директива и поддиректива REMOTE_ACCESS 26

3.4.2 Директива REMOTE_GROUP 27

3.4.3 Директива PREFETCH 27

3.4.4 Директива RESET 28

3.4.5 Удаленные ссылки 28

3.5 Редукционные операции 28

3.5.1 Директива REDUCTION_GROUP 28

3.5.2 Поддиректива REDUCTION 28

3.5.3 Редукционные переменные и операции 29

3.5.4 Директива REDUCTION_START 30

3.5.5 Директива REDUCTION_WAIT 30

3.6 Неявные конструкции 30

3.6.1 Создание и удаление распределенных массивов 30

3.6.2 Статические распределенные массивы 31

3.6.3 Доступ к распределенным данным 31

3.6.4 Собственные вычисления 32

3.6.5 Инициализация и завершение параллельного выполнения 32

3.6.6 Функции ввода-вывода 33

3.7 Отладочные расширения 34

3.7.1 Анализатор производительности. Циклы 34

3.7.2 Анализатор производительности. Интервалы 35

3.7.3 Отладчик. Трассировка данных 35

3.7.4 Отладчик. Трассировка вычислений 36

3.7.5 Пoследовательный код 36

1Назначение компилятора

C-DVM является расширением языка СИ специальными аннотациями для задания параллельного выполнения программы. Аннотации называются DVM-директивами. Компилятор C-DVM транслирует аннотированную программу в SPMD программу, которая содержит вызовы системы поддержки DVM (RTL).

Кроме чисто параллельного кода компилятор может генерировать расширенный отладочный код для использования возможностей анализатора производительности (PPPA) и отладчика, а также последовательный код (без вызовов RTL и, тем самым, без распараллеливания) с такими же отладочными расширениями.

1.1Запуск компилятора

Для переносимости C-DVM компилятор написан на ANSI-C. Компилятор запускается из командной строки (в UNIX и WINDOWS) следующей командой:

c_dvm [ options ] [ -o outfile ] infile

где:

infile - обязательный параметр; файл с исходной C-DVM программой; предполагается, что программа компилировалась любым обычным СИ-компилятором и является правильной как СИ программа;

-o outfile - необязательный параметр; имя файла для выходной сконвертированной программы; по умолчанию создается файл cdvm_out.c ;

options - один или более из следующих ключей:

-s - создавать последовательную программу (без распараллеливания, только трассировка или статистика); по умолчанию создается параллельная программа;

режимы трассировки:

-d1 - трассировка модификации распределенных данных,

-d2 - трассировка всех обращений к распределенным данным,

-d3 - трассировка модификации всех данных,

-d4 - трассировка всех обращений ко всем данным.

режимы сбора статистики:

-e1 - параллельные циклы и объемлющие их последовательные,

-e2 - параллельные циклы и пользовательские интервалы (INTERVAL);

-e3 - e1 + e2,

-e4 - e3 + все последовательные циклы.

прочие:

-v - выводить сообщения на терминал,

-w - разрешить все предупреждения,

-w- - запертить все предупреждения,

-xNNN - установить размер внутренних таблиц (по умолчанию -x16).

2Структура компилятора

Главная программа компилятора выполняет следующие шаги:

• запрашивает и проверяет параметры командной строки (функция cmd_line());

• запрашивает память для таблиц (буферов) переменной длины и инициализирует таблицы сканера и парсера;

• открывает входной и выходной файлы;

• вызывает сканер, который читает исходную программу и строит поток лексем;

• вызывает парсер, который читает поток лексем и строит дерево разбора программы; в свою очередь, парсер вызывает семантические программы для анализа исходной программы и построения требуемых выходных конструкций;

• если парсер успешно построил дерево разбора (не было найдено ошибок), то вызывается преобразователь (дерева), который заменяет исходные узлы дерева вновь построенными;

• и затем конструктор ("unparser") генерирует выходной файл.

2.1Структуры данных компилятора

Компиляция выполняется над внутренним представлением программы. Основные структуры данных, используемые для этого, следующие:

• строковая память для хранения лексем в символьном представлении (LX);

• списковая память, в которой строится дерево разбора (NDs);

• хеш-таблицы для быстрого поиска лексем и узлов дерева (HT0, HT1).

Размерами этих таблиц определяется максимальный размер исходной программы. Если он окажется недостаточным, то он может быть изменен параметром командной строки -xNNN.

Хеш-таблицы доступны с помошью функции HTfind(item,len,ht,ht_cmp,ht_new). Она ищет объект item длины len в таблице ht, используя функцию ht_cmp для сравнения объектов и функцию ht_new для записи нового объекта в таблицу. Возвращается номер ячейки в хеш-таблице. Содержимое ячейки интерпретируется вызывающей программой и функциями ht_cmp и ht_new.

2.2Списковая память

Списковая память используется для хранения следующих данных:

• синтаксические таблицы парсера;

• поток лексем;

• дерево разбора;

• стек парсера и семантических программ;

• списки областей видимости и описаний.

Каждый узел списковой памяти имеет четыре поля:

• C - код узла; обычно это внутренний номер оператора или выражения СИ или директивы C-DVM;

• A, B - ссылки на поддеревья операндов или подструктур; они бывают равны 0 для необязательных компонент или унарных операторов; в исключительных случаях эти поля содержат не ссылки на поддеревья: например, у узла, описывающего лексему, оно содержит ссылку в строковую память;

• D - список атрибутов узла; главный "атрибут" узла для компилятора -- NEW -- преобразованное поддерево.

Для работы со списковой памятью предназначены функции:

• NDinit() чистит буфер списковой памяти и создает список свободных узлов;

• NDD(c,a,b,d) создает и заполняет новый узел;

• mk(c,a,b) создает или находит существующий узел (c,a,b,?);

• NDdel(N) удаляет узел N;

• wN(N,c,a,b) заполняет поля C, A и B узла N.

• A, B, C и D(N) читают соответствующее поле узла N;

• wA, wB, wC и wD(N,x) записывают значение x в соответствующее поле узла N;

• NDget(N,path) запрашивает поддерево по "пути"; например NDget(N, 122) означает C(A(A(N))).

Работа со списком атрибутов поддерживается функциями:

• set(c,N,V) присваивает значение V атрибуту c узла N;

• get(c,N) читает значение атрибута c узла N;

• del(c,N) удаляет атрибут c у узла N.

Семантический стек реализован как список в списковой памяти с корнем Stack и функциями SSpush и SSpop. Имеются функции (walk(N,sfun) и walkR(N)) для стандартного обхода дерева, вызывающие заданную семантическую функцию sfun для каждого проходимого узла.

Для работы с описаниями строится стек областей видимости (как список в списковой памяти) и списки описанных (к данному моменту) переменных для каждой области. Эти структуры поддерживаются функциями:

• openScope() вталкивает стек областей видимости при входе в новую область;

• closeScope() выталкивает стек областей при выходе;

• addDecl(N,spec,dvm) сохраняет описание в списке текущей области видимости;

• Decl(lx) возвращает 0, если lx не определен;

• whatis(N) находит и распаковывает описание и директиву (если она есть) в глобальные переменные для семантических программ;

• и некоторыми другими.

2.3Сканер и строковая память

Основная функция сканера это функция scan(). При каждом вызове она:

• пропускает "пустые" символы, в частности, комментарии;

• если надо, читает очередную строку исходного файла;

• определяет тип следующей лексемы по первому символу;

• продвигается через символы следующей лексемы;

• ищет ее (или записывает) в таблицу лексем;

• устанавливает глобальные переменные LXcode и LXval.

LXcode - это код текущей лексемы: для ключевых слов и разделителей это их внутреннй номер; для идентификаторов и констант -- номер их лексической категории. В последнем случае LXvalue содержит внутренний номер идентификатора или константы, т.е. ссылку на узел с кодом TOKEN. Символьное представление идентификаторов и констант хранится в строковой памяти и используется на шаге генерации. Для парсера идентификаторы и константы представлены их внутренними номерами, которые присваиваются им при первом появлении. Сканер сначала ищет текущую лексему в таблице лексем (используя хеш-таблицу) и дописывает ее туда, если ее не было.

Другие функции сканера:

• LXinit() инициализирует таблицы сканера;

• LX_get(t) выделяет следующую лексему, пропуская символы типа t (определяемого по таблице LXcd, например десятичные цифры, шестнадцатиричные цифры, буквы);

• comment() пропускает комментрии;

• LXfind(lxcode) ищет текущую лексему в таблице лексем; новую записывает;

• LXW(token) извлекает символьное представление лексемы по номеру;

• Token(s) создает узел TOKEN для строки s;

• LxiS(s) создает узел LXI (идентификатор) для строки s;

• Lxi(token) создает узел LXI (идентификатор) для лесемы token;

• Lxn(n) создает узел LXN (число) для целого числа n.

2.4Коды лексем

2.4.1Терминалы

LXEOF "LXEOF" -- конец файла

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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