Аннотация

В данной работе рассматривается задача создания компилятора языка C-DVM для вычислительных кластеров. В результате работы был реализован компилятор, включающий в себя лексический и синтаксический анализаторы, инструменты для семантического анализа и преобразования внутреннего представления программы и генератор целевого кода на языке C с вызовами функций библиотеки поддержки Lib-DVM.

Было проведено экспериментальное исследование, показавшее корректность и правильность работы реализованного компилятора.

Содержание

1 Введение. 4

2 Постановка задачи дипломной работы.. 9

3 Обзор существующих инструментальных средств для создания компиляторов 11

3.1 DMS Software Reengineering Toolkit 11

3.2 LLVM.. 13

3.3 Sage++. 15

3.4 ROSE. 17

3.5 Выводы.. 19

4 Описание реализации. 21

4.1 Инструментальная система ROSE. 21

4.2 Архитектура инструментальной системы ROSE. 22

4.3 Архитектура и принципы работы компилятора C-DVM.. 23

5 Экспериментальное исследование. 28

5.1 Тестирование работы компилятора на алгоритме Якоби решения системы линейных уравнений со спецификацией SHADOW_RENEW для локализации удалённых данных типа SHADOW... 32

5.2 Тестирование работы компилятора на алгоритме SOR решения системы линейных уравнений со спецификацией ACROSS для локализации удалённых данных типа SHADOW... 33

6 Заключение. 35

Список литературы.. 37

Приложение A. Описание прагм C-DVM.. 40

Приложение Б. Синтаксис языка C-DVM.. 43

Приложение В.. 47

Приложение Г. 52

1. Введение

Последние годы во всем мире происходит бурное внедрение вычислительных кластеров [1]. Это вызвано тем, что кластеры стали общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Вычислительный кластер – это мультикомпьютер, состоящий из множества отдельных компьютеров (узлов), связанных между собой единой коммуникационной системой. Каждый узел имеет свою локальную оперативную память. Любой кластер можно рассматривать как аппаратно-программную систему, имеющую общую коммуникационную систему, единый центр управления и планирования загрузки.

С 1992 года, когда кластеры стали самыми производительными вычислительными системами, резко возрос интерес к проблеме разработки для них параллельных прикладных программ [2]. К этому моменту уже было ясно, что трудоемкость разработки прикладных программ для многопроцессорных систем с распределенной памятью является главным препятствием для их широкого внедрения. За прошедший с тех пор период предложено много различных подходов к разработке параллельных программ, созданы десятки различных языков параллельного программирования и множество инструментальных средств.

Одним из таких языков является язык C-DVM [3], разработанный в Институте прикладной математики им. М.В. Келдыша РАН при активном участии студентов и аспирантов факультета ВМиК МГУ им. М.В.Ломоносова. C-DVM представляет собой стандартный язык последовательного программирования ANSI C, расширенный спецификациями параллелизма в соответствии с моделью DVM (Distributed Virtual Machine, Distributed Virtual Memory – распределённая виртуальная машина, распределённая виртуальная память) [4]. Спецификации параллелизма – это средства описания правил параллельного выполнения программ. Они оформлены в виде специальных DVM-указаний.

DVM-указания предоставляют следующие возможности описания параллельного выполнения программы:

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

В настоящее время компиляция программы на языке C-DVM выполняется в два этапа:

Рисунок 1. Схема компиляции программы на языке C-DVM

На первом этапе компилятор C-DVM [5] преобразует параллельную программу на языке C-DVM в программу на языке С, выполняющуюся в соответствии с моделью ОКМД по классификации Флинна (один поток команд – много данных) на каждом выделенном задаче процессоре. DVM-указания преобразуются в вызовы функций единой системы поддержки Lib-DVM [6], которая реализована на языке C и базируется на стандартной коммуникационной библиотеке MPI (Message Passing Interface) [7]. Поэтому система поддержки переносима на любые платформы, для которых существует реализация MPI.

На втором этапе программа на языке C, расширенная вызовами функций библиотеки поддержки, компилируется в исполняемый модуль компилятором языка C.

В последние годы изменилось направление развития процессоров – появляются многоядерные и многопоточные процессоры, гетерогенные кластеры, построенные на основе современных графических процессоров. Их эффективное использование требует более глубокого распараллеливания, обеспечивающее два уровня параллелизма – параллелизм между узлами кластера (технология MPI) и организация нескольких потоков процессора локально в рамках одного узла вычислительной системы (технология OpenMP [8]). С этими изменениями связано появление новых направлений развития модели DVM:

• эффективное распараллеливание программ для мультипроцессорных вычислительных кластеров – гибридная модель DVM/OpenMP [9];
• распараллеливание программ для гетерогенных кластеров, построенных на основе графических процессоров – модель DVMH [10].

Новые модели параллельных вычислений требуют создания нового компилятора, способного преобразовывать DVM-указания и OpenMP прагмы в исполняемый модуль.

Первоначально DVM-указания были оформлены в виде макросов DVM(<директива>). В настоящее время они переведены в формат прагм по аналогии с OpenMP, что позволяет программисту иметь одну версию программы для последовательного и параллельного выполнения, поскольку прагмы являются стандартным средством языка C и для стандартных компиляторов языка C (таких, как gcc) «невидимы». Новый формат DVM-указаний – первый этап в создании компилятора C-DVM/OpenMP для распараллеливания программ на вычислительные мультипроцессорные и гетерогенные кластеры.

В данной работе рассматривается разработка компилятора с языка C-DVM в язык C для нового формата языка C-DVM с DVM-указаниями в виде прагм. Новый компилятор C-DVM состоит из трёх частей [11]:

• front-end – синтаксический и семантический анализ программы на исходном языке, преобразование кода на более низкий уровень представления (по сравнению с исходным), обычно называемый промежуточным представлением компилятора;
• middle-end – внутренние преобразования промежуточного представления программы (например, оптимизация кода или генерация нового кода);
• back-end – преобразование внутреннего представления компилятора в код на целевом языке программирования.

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

1. Постановка задачи дипломной работы

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

Компилятор должен выполнять три группы задач, каждая из которых отвечает за определённые преобразования при переводе исходного кода в целевой:

• проверка правильности написания программы с точки зрения синтаксиса и семантики языка программирования C-DVM, генерация промежуточного представления исходного кода;
• преобразования программы в соответствии с моделью DVM – трансляция прагм DVM в вызовы функций системы поддержки Lib-DVM;
• генерация кода на языке C.

Для выполнения поставленных задач компилятор должен распознавать следующие три типа конструкций [3]:

• описательные прагмы. Содержащаяся в них информация должна быть сохранена для использования при преобразовании программы. Описания должны быть заменены;
• выполняемые прагмы. Должны быть заменены на вызовы соответствующих функций Lib-DVM;
• неявные(т.е. не отмеченные явно DVM-прагмами). К ним относятся:
  1. создание и уничтожение распределенных массивов;
  2. доступ к распределенным данным;
  3. функции ввода-вывода;
  4. инициализация и завершение параллельного выполнения;
  5. собственные вычисления;
  6. последовательные циклы.

В данной работе необходимо разработать компилятор с языка C-DVM с ограниченным набором DVM-прагм:

• описательные – distribute, align, shadow;
• выполняемые – parallel со спецификациями reduction, across, shadow_renew;
• неявные.

Подробное описание прагм дано в приложении А.