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

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

24

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

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

Предварительный дизайн

Декабрь, 1999

Содержание

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

1.1 Распараллеливание 3

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

2 Последовательность компиляции 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1Распараллеливание

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

• Описательные директивы. Содержащаяся в них информация должна быть сохранена для использования при преобразовании программы. Описания должны быть заменены.

• Выполняемые директивы. Заменяются на вызовы соответствующих функций RTL.

• Структурные директивы. Требуют анализа и преобразования структуры программы.

• Неявные (т.е. не отмеченные явно DVM-директивами).
  К ним относятся:

• создание и уничтожение распределенных массивов;

• доступ к распределенным данным;

• функции ввода-вывода;

• инициализация и завершение параллельного выполнения;

• собственные вычисления;

• последовательные циклы.

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

Для анализатора производительности компилятор должен обрабатывать:

• специальную директиву INTERVAL;

• начало и завершение выполнения (локальной части) параллельных циклов;

• начало и завершение выполнения некоторых последовательных циклов.

Эти действия реализуются вызовами соответствующих функций анализатора.

Для отладчика компилятор должен обеспечить:

• трассировку доступа к данным;

• регистрацию инициализированных переменных;

• трассировку начала каждой итерации цикла или начала выполнения подзадачи.

Все это реализуется вызовами соответствующих функций отладчика. Точка регистрации инициализированных переменных определяется компилятором.

Режим последовательного выполнения нужен для получения временных характеристик исходной программы и "эталонной" трассировки для отладки в режиме сравнения трассировки. В этом режиме все DVM-директивы игнорируются за исключением следующих:

• параллельные циклы для анализатора производительности;

• редукционные переменные для правильной работы трассировщика;

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

2Последовательность компиляции

Компиляция C-DVM программы выполняется в следующей последовательности.

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

• Дерево анализируется для сбора глобальной информации.

• Дерево преобразуется и расширяется.

• По модифицированному дереву генерируется выходной код.

Для удобства и большей гибкости сгенерированная программа не содержит прямых вызовов функций RTL. Она содержит макрокоманды со всей необходимой информацией, скрывающие низкоуровневые детали интерфейса RTL. Окончательная генерация выполняется препроцессором СИ с использованием макроопределений, содержащихся в файле cdvm_c.h.

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

Необходимость преобразования программы для параллельного выполнения вызвана распределением данных и вычислений.

Распределение данных состоит в разбиении массивов на части и размещении этих частей в локальной памяти разных процессоров. На каждом процессоре RTL определяет размер локальной части (с учетом теневых граней) и выделяет память для неё. Для программы эта локальная часть массива доступна через хендлер массива. Следовательно, исходные последовательные операторы для создания массива и доступа к его элементам должны быть найдены в исходном коде и заменены.

Распределение вычислений состоит в разбиении индексного пространства цикла на части и выполнения на разных процессорах разных множеств витков цикла. На каждом процессоре локальная часть параллельного цикла описывается дескриптором цикла. Т.о. заголовки цикла должны быть преобразованы.

В этом разделе описаны эти и другие преобразования конструкций C-DVM, выполняемые компилятором.

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

3.1.1Директива DISTRIBUTE

Контекст и синтаксис.

DVM( ["*"] DISTRIBUTE [ format...] [ ONTO target ]

[ ; SHADOW-clause ] [ ; TEMPLATE-clause ] )

C-declaration ;

Выход компилятора.

long array-id [ rank+1 ];

Замечание. Исходное описание заменено. Вся прочая информация из описания и директивы будет использоваться при генерации других конструкций и при распознавании ссылок к распределенным данным.

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

Контекст и синтаксис.

DVM(DISTRIBUTE ... "[" GENBLOCK( int-array ) "]"... )

DVM(REDISTRIBUTE ... "[" GENBLOCK( int-array ) "]"... )

Выход компилятора.

DVM_GENBLOCK(am,ps,k,gbs);

Замечание. Эта макрокоманда генерируется не в точке описания, а в общей последовательности (явного или неявного) создания массива. Макрокоманда DVM_GENBLOCK(am,ps,k,gbs) расширяется в

DVM_AM=am? am : getam_();

DVM_PS=ps? ps : getps_(NULL);

genbli_(&DVM_PS, &DVM_AM, (AddrType*) gbs, k);

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

Контекст и синтаксис.

DVM(DISTRIBUTE ... ONTO target ... )

Выход компилятора.

DVM_ONTO(ps,k,ls,hs)

Замечание. Эта макрокоманда генерируется не в точке описания, а в общей последовательности (явного или неявного) создания массива. Она создает процессорную подсистему, которая будет использоваться вместо текущей (используемой по умолчанию). Макрокоманда DVM_ONTO(ps,k,ls,hs) расширяется в

DVM_PS=ps;

DVM_PS=crtps_(&DVM_PS, ls, hs, DVM_0000);

3.1.4Директива REDISTRIBUTE

Контекст и синтаксис.

DVM(REDISTRIBUTE array format... [ NEW ] ) ;

Выход компилятора.

DVM_REDISTRIBUTE(amv,ps,k,axs,new);

Замечание. Выполнимая директива конвертируется в оператор. Макрокоманда DVM_REDISTRIBUTE(amv,ps,k,axs,new) расширяется в

{DVM_PS=ps;

redis_((AMViewRef*) amv, &DVM_PS, k, axs, 0, new);

}

3.1.5Директива ALIGN

Контекст и синтаксис.

DVM(["*"] ALIGN [ "["dummy-var"]"... ]

WITH base "["align-expr"]"...

[ ; SHADOW-clause ] )

C-declaration ;

Выход компилятора.

long array-id [ rank+1 ];

Замечание. Исходное описание заменено. Вся прочая информация из описания и директивы будет использоваться при генерации других конструкций и при распознавании ссылок к распределенным данным.

3.1.6Директива REALIGN

Контекст и синтаксис.

DVM( REALIGN array "["dummy-var"]"...

WITH base "["align-expr"]"... ) ;

Выход компилятора.

DVM_REALIGN(arr,base,k,i,a,b,new);

Замечание. Выполнимая директива конвертируется в оператор. Макрокоманда DVM_REALIGN(arr,base,k,i,a,b,new) расширяется в

{realn_(arr, (PatternRef*)(base), i, a, b, new);

}

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

Контекст и синтаксис.

DVM(DISTRIBUTE ... ; TEMPLATE [ "["size"]"... ] )

void * template-id ;

Выход компилятора.

AMViewRef template-id;

Замечание. Исходное описание заменено. Форматы распределения будут использованы при создании темплейта. Если размер (size) задан, то создание будет неявным.

3.1.8Директива CREATE_TEMPLATE

Контекст и синтаксис.

DVM(CREATE_TEMPLATE template-id "["size"]"... ) ;

Выход компилятора.

DVM_CREATE_TEMPLATE(am,t,r,di);

DVM_DISTRIBUTE(amv,ps,k,axs);

Замечание. Выполнимая директива конвертируется в оператор. Макрокоманда DVM_CREATE_TEMPLATE(am,t,r,di) расширяется в

{if(am==0) DVM_AM=getam_();

else DVM_AM=am;

t=crtamv_( (AMRef*)DVM_AM, r, di, 0);

}

Макрокоманда DVM_DISTRIBUTE(amv,ps,k,axs) расширяется в

{DVM_PS=ps;

DVM_AMV=amv;

distr_( &DVM_AMV, &DVM_PS, k, axs, 0);

}

Эти макрокоманды генерируются также для создания и распределения неявного темплейта для любого массива со спецификацией DISTRIBUTE.

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

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

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

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

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

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