Компилятор C-DVM
Детальный дизайн
* 22 June 2000 *


Содержание

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

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

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

2.1 Структуры данных компилятора
2.2 Списковая память
2.3 Сканер и строковая память
2.4 Коды лексем

2.4.1 Терминалы
2.4.2 Разделители и операторы
2.4.3 Ключевые слова
2.4.4 Ключевые слова и идентификаторы C-DVM

2.5 Парсер
2.6 Структура дерева разбора

2.6.1 Терминалы, списки, скобки
2.6.2 Описания (СИ)
2.6.3 Операторы (СИ)
2.6.4 Выражения (СИ)
2.6.5 Директивы (C-DVM)
2.6.6 Поддирективы (C-DVM)

2.7 Преобразование дерева
2.8 Генерация

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

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

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 Распределение вычислений (циклы и задачи)

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 Теневые грани

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 Удаленный доступ

3.4.1 Директива и поддиректива REMOTE_ACCESS
3.4.2 Директива REMOTE_GROUP
3.4.3 Директива PREFETCH
3.4.4 Директива RESET
3.4.5 Удаленные ссылки

3.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 Неявные конструкции

3.6.1 Создание и удаление распределенных массивов
3.6.2 Статические распределенные массивы
3.6.3 Доступ к распределенным данным
3.6.4 Собственные вычисления
3.6.5 Инициализация и завершение параллельного выполнения
3.6.6 Функции ввода-вывода

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

3.7.1 Анализатор производительности. Циклы
3.7.2 Анализатор производительности. Интервалы
3.7.3 Отладчик. Трассировка данных
3.7.4 Отладчик. Трассировка вычислений
3.7.5 Пoследовательный код


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 Структура компилятора

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 Коды лексем

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"

2.5 Парсер

Назначение парсера:

Метод разбора -- простой рекурсивный спуск с возвратами в немногочисленных сомнительных случаях. Структура дерева разбора описана в следующем разделе.

Парсер реализован в виде рекурсивной функции Parse, использующей внутреннее представление синтаксиса, которое хранится в списковой памяти в виде дерева синтаксиса. Дерево синтаксиса строится функцией STXinit с помощью функций:

Парсер использует также следующие функции:

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

Нижеследующая таблица описывает структуру дерева разбора в такой форме. Для всех кодов узлов (слева) представлен фрагмент исходного текста, в котором через 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 ")"

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

Преобразование дерева выполняется в два этапа:

2.8 Генерация

Функция UnPars обходит дерево и восстанавливает внешнее представление программы. Т.к. файл промежуточный, форматирование сравнительно простое. Заметим, что выходная программа составлена в терминах макрокоманд C-DVM, а не прямо в терминах вызовов RTL. Окончательная форма макроопределений может быть найдена в файле cdvm_c.h.

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