Компилятор C-DVM |
Содержание
2.1 Структуры данных компилятора
2.2 Списковая память
2.3 Сканер и строковая память
2.4 Коды лексем
2.4.1 Терминалы
2.4.2 Разделители и операторы
2.4.3 Ключевые слова
2.4.4 Ключевые слова и идентификаторы C-DVM
2.6.1 Терминалы, списки, скобки
2.6.2 Описания (СИ)
2.6.3 Операторы (СИ)
2.6.4 Выражения (СИ)
2.6.5 Директивы (C-DVM)
2.6.6 Поддирективы (C-DVM)
3 Компиляция конструкций C-DVM
3.1.1 Директива DISTRIBUTE
3.1.2 Формат распределения GENBLOCK
3.1.3 Спецификация ONTO
3.1.4 Директива REDISTRIBUTE
3.1.5 Директива ALIGN
3.1.6 Директива REALIGN
3.1.7 Поддиректива TEMPLATE
3.1.8 Директива CREATE_TEMPLATE
3.2.1 Директива PARALLEL
3.2.2 Поддиректива ACROSS
3.2.3 Директива PROCESSORS и функция NUMBER_OF_PROCESSORS()
3.2.4 Директива TASK
3.2.5 Директива MAP
3.2.6 Директива TASK_REGION
3.2.5 Директива MAP
3.2.6 Директива TASK_REGION
3.2.7 Конструкция ON-block
3.2.8 Конструкция ON-loop
3.3.1 Поддиректива SHADOW
3.3.2 Поддиректива SHADOW_RENEW
3.3.3 Директива SHADOW_GROUP
3.3.4 Директива CREATE_SHADOW_GROUP
3.3.5 Директива SHADOW_START
3.3.6 Поддиректива SHADOW_START
3.3.7 Директива SHADOW_WAIT
3.3.8 Поддиректива SHADOW_WAIT
3.4.1 Директива и поддиректива REMOTE_ACCESS
3.4.2 Директива REMOTE_GROUP
3.4.3 Директива PREFETCH
3.4.4 Директива RESET
3.4.5 Удаленные ссылки
3.5.1 Директива REDUCTION_GROUP
3.5.2 Поддиректива REDUCTION
3.5.3 Редукционные переменные и операции
3.5.4 Директива REDUCTION_START
3.5.5 Директива REDUCTION_WAIT
3.6.1 Создание и удаление распределенных массивов
3.6.2 Статические распределенные массивы
3.6.3 Доступ к распределенным данным
3.6.4 Собственные вычисления
3.6.5 Инициализация и завершение параллельного выполнения
3.6.6 Функции ввода-вывода
3.7.1 Анализатор производительности. Циклы
3.7.2 Анализатор производительности. Интервалы
3.7.3 Отладчик. Трассировка данных
3.7.4 Отладчик. Трассировка вычислений
3.7.5 Пoследовательный код
C-DVM является расширением языка СИ специальными аннотациями для задания параллельного выполнения программы. Аннотации называются DVM-директивами. Компилятор C-DVM транслирует аннотированную программу в SPMD программу, которая содержит вызовы системы поддержки DVM (RTL).
Кроме чисто параллельного кода компилятор может генерировать расширенный отладочный код для использования возможностей анализатора производительности (PPPA) и отладчика, а также последовательный код (без вызовов RTL и, тем самым, без распараллеливания) с такими же отладочными расширениями.
Для переносимости 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.1 Структуры данных компилятора
Компиляция выполняется над внутренним представлением программы. Основные структуры данных, используемые для этого, следующие:
Размерами этих таблиц определяется максимальный размер исходной программы. Если он окажется недостаточным, то он может быть изменен параметром командной строки -xNNN.
Хеш-таблицы доступны с помошью функции HTfind(item,len,ht,ht_cmp,ht_new). Она ищет объект item длины len в таблице ht, используя функцию ht_cmp для сравнения объектов и функцию ht_new для записи нового объекта в таблицу. Возвращается номер ячейки в хеш-таблице. Содержимое ячейки интерпретируется вызывающей программой и функциями ht_cmp и ht_new.
Списковая память используется для хранения следующих данных:
Каждый узел списковой памяти имеет четыре поля:
Для работы со списковой памятью предназначены функции:
Работа со списком атрибутов поддерживается функциями:
Семантический стек реализован как список в списковой памяти с корнем Stack и функциями SSpush и SSpop. Имеются функции (walk(N,sfun) и walkR(N)) для стандартного обхода дерева, вызывающие заданную семантическую функцию sfun для каждого проходимого узла.
Для работы с описаниями строится стек областей видимости (как список в списковой памяти) и списки описанных (к данному моменту) переменных для каждой области. Эти структуры поддерживаются функциями:
Основная функция сканера это функция scan(). При каждом вызове она:
LXcode -- это код текущей лексемы: для ключевых слов и разделителей это их внутреннй номер; для идентификаторов и констант -- номер их лексической категории. В последнем случае LXvalue содержит внутренний номер идентификатора или константы, т.е. ссылку на узел с кодом TOKEN. Символьное представление идентификаторов и констант хранится в строковой памяти и используется на шаге генерации. Для парсера идентификаторы и константы представлены их внутренними номерами, которые присваиваются им при первом появлении. Сканер сначала ищет текущую лексему в таблице лексем (используя хеш-таблицу) и дописывает ее туда, если ее не было.
Другие функции сканера:
2.4.1 Терминалы
LXEOF "LXEOF" -- конец файла TOKEN "TOKEN" -- лексема (ссылка в строковую память) DLM "DLM" -- разделитель во входном потоке KWD "KWD" -- ключевое слово во входном потоке LXX "LXX" -- список без разделителя LXI "IDENT" -- идентификатор LXN "NUMBER" -- числовая константа LXC "LXC" -- символьная константа LXR "REAL" -- число в плавающем формате LXS "STRING" -- строковая константа CPP "CPP" -- препроцессорный оператор
2.4.2 Разделители и операторы
SEMIC ";"
COMMA ","
LBA "("
LBS "{"
LBK "["
RBA ")"
RBK "]"
RBS "}"
POINT "."
QUEST "?"
COLON ":"
DIV "/"
ADIV "/="
COMM "/*" -- начало C комментария
CPPCOMM "//" -- начало C++ комментария
MOD "%"
AMOD "%="
ADD "+"
AADD "+="
INC "++"
SUB "-"
ASUB "-="
DEC "--"
ARROW "->"
MUL "*"
AMUL "*="
ASSIGN "="
EQU "=="
LT "<"
LE "<="
LSH "<<"
ALSH "<<="
GT ">"
GE ">="
RSH ">>"
ARSH ">>="
BNOT "~"
NOT "!"
NEQ "!="
BAND "&"
AAND "&="
AND "&&"
BOR "|"
AOR "|="
OR "||"
BXOR "^"
AXOR "^="
2.4.3 Ключевые слова
RETURN "return" IF "if" ELSE "else" WHILE "while" DO "do" FOR "for" BREAK "break" CONTINUE "continue" SWITCH "switch" CASE "case" DEFAULT "default" GOTO "goto" SIZEOF "sizeof" TYPEDEF "typedef" EXTERN "extern" STATIC "static" REGISTER "register" AUTO "auto" CONST "const" INT "int" SHORT "short" LONG "long" VOID "void" CHAR "char" SIGNED "signed" UNSIGNED "unsigned" FLOAT "float" DOUBLE "double" STRUCT "struct" UNION "union" ENUM "enum"
2.4.4 Ключевые слова и идентификаторы C-DVM
LX_DVM "DVM" PROCESSORS "PROCESSORS" DISTRIBUTE "DISTRIBUTE" BLOCK "BLOCK" GENBLOCK "GENBLOCK" ONTO "ONTO" ALIGN "ALIGN" WITH "WITH" TEMPLATE "TEMPLATE" SHADOW "SHADOW" LX_SG "SHADOW_GROUP" LX_RG "REDUCTION_GROUP" LX_RMG "REMOTE_GROUP" TASK "TASK" REDISTRIBUTE "REDISTRIBUTE" REALIGN "REALIGN" NEW "NEW" LX_CRTEMP "CREATE_TEMPLATE" PARALLEL "PARALLEL" ON "ON" REDUCTION "REDUCTION" SHRENEW "SHADOW_RENEW" ACROSS "ACROSS" LX_CRSG "CREATE_SHADOW_GROUP" CORNER "CORNER" SHSTART "SHADOW_START" SHWAIT "SHADOW_WAIT" SUM "SUM" PROD "PRODUCT" MAX "MAX" MIN "MIN" LX_OR "OR" LX_AND "AND" MAXLOC "MAXLOC" MINLOC "MINLOC" RSTART "REDUCTION_START" RWAIT "REDUCTION_WAIT" REMOTE "REMOTE_ACCESS" INDIRECT "INDIRECT_ACCESS" PREFETCH "PREFETCH" RESET "RESET" MAP "MAP" LX_TASKREG "TASK_REGION" INTERVAL "INTERVAL" DEBUG "DEBUG" LX_NUMBER_OF_PROC "NUMBER_OF_PROCESSORS" LX_FOR "FOR" LX_DO "DO" LX_main "main" LX_malloc "malloc" LX_free "free" optD0 "d0" optD1 "d1" optD2 "d2" optD3 "d3" optD4 "d4" optE0 "e0" optE1 "e1" optE2 "e2" optE3 "e3" optE4 "e4"
Назначение парсера:
Метод разбора -- простой рекурсивный спуск с возвратами в немногочисленных сомнительных случаях. Структура дерева разбора описана в следующем разделе.
Парсер реализован в виде рекурсивной функции Parse, использующей внутреннее представление синтаксиса, которое хранится в списковой памяти в виде дерева синтаксиса. Дерево синтаксиса строится функцией STXinit с помощью функций:
Парсер использует также следующие функции:
Нижеследующая таблица описывает структуру дерева разбора в такой форме. Для всех кодов узлов (слева) представлен фрагмент исходного текста, в котором через A и B обозначены подконструкции, соответствующие поддеревьям, на которые указывают, соответственно, поля A и B. AB соответствует поддереву под полем A узла, на который указывает поле B исходного узла. Когда разбиение исходного текста неочевидно, маркеры прокомментированы. Здесь описана только "свободная" структура. Зависимости и ограничения не упоминаются.
2.6.1 Терминалы, списки, скобки
TOKEN: -- A указывает позицию в строковой памяти
DLM: -- A - внутренний код разделителя
KWD: -- A - внутренний код ключевого слова
LXI: -- A - ссылка на узел с кодом TOKEN
LXN: -- A - ссылка на узел с кодом TOKEN
LXC: -- A - ссылка на узел с кодом TOKEN
LXR: -- A - ссылка на узел с кодом TOKEN
LXS: -- A - ссылка на узел с кодом TOKEN
CPP: -- A - директива препроцессора как строка
COMMA: A , B - список через запятую
LXX: A [B-tail] - B-список
XXlist: A [B-tail] - B-список
XXslist: A [B-tail] - B-список
LBA: "(" [A] ")"
LBS: "{" [A ] "}" - составной оператор
LBK: [A] "[" [B] "]" - операция индексации
2.6.2 Описания (СИ)
LXX: [AA-DVM_directive] BA-decl [ B-next ] XXdecl: [AA-storage_class] BA-type B-declarator-list XXtype: [AA-storage_class] BA-type B-abstract-declarator
Класс памяти :
STATIC: static [B] AUTO: auto [B] REGISTER: register [B] EXTERN: extern [B] TYPEDEF: typedef [B] CONST: const [B]
Тип (простые типы связаны в список полями B)
STRUCT: struct [A] ["{" AB-fields "}"]
UNION: union [A] ["{" AB-fields "}"]
ENUM: enum [A] ["{" B "}"]
VOID: void
TYPEDEF: B - typedef-name
UNSIGNED: unsigned [B]
SIGNED: signed [B]
CHAR: char [B]
SHORT: short [B]
LONG: long [B]
INT: int [B]
FLOAT: float [B]
DOUBLE: double [B]
Деклараторы:
0: AA-declarator [BA-initializer] B-list-tail
LXaster: * [B-"const"] A
LXfun: A "(" [B] ")"
Инициализаторы:
ASS: = A COLON: : A
Хвост списка деклараторов:
XXbody: "{" [A] "}" [B -- ";"]
XXclist: , A
SEMIC: ; - конец описания
2.6.3 Операторы (СИ)
XXoper: A
IF: if "(" AA ")" BA [else B]
WHILE: while "(" A ")" B
DO: do B while "(" A ")" ;
FOR: for "(" AA ; ABA ; BBA ")" B
SWITCH: switch "(" A ")" "{" B "}"
GOTO: goto A ;
LXskip: ;
RETURN: return [A] ;
LX_FOR: FOR "(" AA , BA ")" B
LX_DO: DO "(" AA-variable , BA ")" B
CONTINUE: continue ;
BREAK: break ;
COLON: A :
XXexpr: A ;
DEFAULT: default: [B]
CASE: case A : [B]
2.6.4 Выражения (СИ)
LBK: A "[" B "]"
POINT: A . B
ARROW: A -> B A
SS: A = B
AADD: A += B
ASUB: A -= B
AMUL: A *= B
ADIV: A /= B
AMOD: A %= B
ARSH: A >>= B
ALSH: A <<= B
AAND: A &= B
AXOR: A ^= B
AOR: A |= B
QUEST: A ? AB : BB
OR: A || B
AND: A && B
BOR: A | B
BXOR: A ^ B
BAND: A & B
EQU: A == B
NEQ: A != B
GT: A > B
GE: A >= B
LT: A < B
LE: A <= B
RSH: A >> B
LSH: A << B
ADD: [A] + B
SUB: [A] - B
MUL: A * B
DIV: A / B
MOD: A % B
LXinca: A ++
LXdeca: A --
NOT: ! B
BNOT: ~ B
SUB: - B
ADD: + B
INC: ++ B
DEC: -- B
SIZEOF: sizeof ( B )
LXaddr: & B
LXcont: * B
LXfun: A "(" [B] ")"
LXcast: "(" A ")" B
2.6.5 Директивы (C-DVM)
LX_DVM: DVM "(" [B-"*"] A ")"
DISTRIBUTE: DISTRIBUTE [ AA [ ONTO BA ] ] [ B-subdirs ] ALIGN: ALIGN [ AA WITH BA ] [ B-subdirs ] LX_SG: SHADOW_GROUP LX_RG: REDUCTION_GROUP LX_RMG: REMOTE_GROUP TASK: TASK PROCESSORS: PROCESSORS REDISTRIBUTE: REDISTRIBUTE AA [ ONTO BA ] [ B-"NEW" ] REALIGN: REALIGN AA WITH BA [ B-"NEW" ] LX_CRTEMP: CREATE_TEMPLATE A MAP: MAP A ONTO B LX_CRSG: CREATE_SHADOW_GROUP A ":" B-Renewees SHSTART: SHADOW_START A SHWAIT: SHADOW_WAIT A RSTART: REDUCTION_START A RWAIT: REDUCTION_WAIT A PREFETCH: PREFETCH A RESET: RESET A PARALLEL: PARALLEL AA ON BA [ B-clauses ] REMOTE: REMOTE_ACCESS [ A ":" ] B LX_TASKREG TASK_REGION A [ B-clause ] ON: ON A INTERVAL: INTERVAL [ A ] DEBUG: DEBUG A-number B-Debug_modes
Debug_modes -- это B-связные узлы: optD0: -d0 [ B ] optD1: -d1 [ B ] optD2: -d2 [ B ] optD3: -d3 [ B ] optD4: -d4 [ B ] optE0: -e0 [ B ] optE1: -e1 [ B ] optE2: -e2 [ B ] optE3: -e3 [ B ] optE4: -e4 [ B ]
Поддерево Renewees это LXX-список: DVMshad: A-DVMshw [ B-"CORNER" ] DVMshw: [ A ] "[" AB [ ":" BB ] "]"
2.6.6 Поддирективы (C-DVM)
TEMPLATE: ";" TEMPLATE A SHADOW: ";" SHADOW A-DVMshw SHRENEW: ";" SHADOW_RENEW B-Renewees SHSTART: ";" SHADOW_START A SHWAIT: ";" SHADOW_WAIT A ACROSS: ";" ACROSS B-Renewees REDUCTION: ";" REDUCTION [ A ":" ] B-Red_ops REMOTE: ":" REMOTE_ACCESS [ A ":" ] B
Поддерево Red_ops -- это LXX-список из:
SUM: SUM "(" A ")"
PROD: PROD "(" A ")"
MAX: MAX "(" A ")"
MIN: MIN "(" A ")"
LX_AND: AND "(" A ")"
LX_OR: OR "(" A ")"
MAXLOC: MAXLOC "(" A, B ")"
MINLOC: MINLOC "(" A, B ")"
Преобразование дерева выполняется в два этапа:
Функция UnPars обходит дерево и восстанавливает внешнее представление программы. Т.к. файл промежуточный, форматирование сравнительно простое. Заметим, что выходная программа составлена в терминах макрокоманд C-DVM, а не прямо в терминах вызовов RTL. Окончательная форма макроопределений может быть найдена в файле cdvm_c.h.