Московский государственный университет им. М.В. Ломоносова,
Факультет вычислительной математики и кибернетики
Кафедра системного программирования
Дипломная работа
Преобразование программ на языке C-DVM в программы для кластера
Выполнила:
студентка группы №527
Коваленко А.И.
Научный руководитель:
проф., доктор физ.-мат. наук
Крюков В.А.
Москва 2012
Аннотация
В данной работе рассматривается задача создания компилятора языка C-DVM для вычислительных кластеров. В результате работы был реализован компилятор, включающий в себя лексический и синтаксический анализаторы, инструменты для семантического анализа и преобразования внутреннего представления программы и генератор целевого кода на языке C с вызовами функций библиотеки поддержки Lib-DVM.
Было проведено экспериментальное исследование, показавшее корректность и правильность работы реализованного компилятора.
Содержание
Аннотация 2
Содержание 3
1Введение 4
2Постановка задачи дипломной работы 10
3Обзор существующих инструментальных средств для создания компиляторов 12
3.1DMS Software Reengineering Toolkit 12
3.2LLVM 14
3.3Sage++ 16
3.4ROSE 18
3.5Выводы 20
4Описание реализации 22
4.1Инструментальная система ROSE 22
4.2Архитектура инструментальной системы ROSE 23
4.3Архитектура и принципы работы компилятора C-DVM 24
5Экспериментальное исследование 30
5.1Тестирование работы компилятора на алгоритме Якоби решения системы линейных уравнений со спецификацией SHADOW_RENEW для локализации удалённых данных типа SHADOW 34
5.2Тестирование работы компилятора на алгоритме SOR решения системы линейных уравнений со спецификацией ACROSS для локализации удалённых данных типа SHADOW 35
6Заключение 37
Список литературы 39
Приложение A. Описание прагм C-DVM 41
Приложение Б. Синтаксис языка C-DVM 44
Приложение В 48
Приложение Г 53
1Введение
Последние годы во всем мире происходит бурное внедрение вычислительных кластеров [1].. Это вызвано тем, что кластеры стали общедоступными и дешевыми аппаратными платформами для высокопроизводительных вычислений. Вычислительный кластер – это мультикомпьютер, состоящий из множества отдельных компьютеров (узлов), связанных между собой единой коммуникационной системой. Каждый узел имеет свою локальную оперативную память. Любой кластер можно рассматривать как аппаратно-программную систему, имеющую общую коммуникационную систему, единый центр управления и планирования загрузки.
С 1992 года, когда кластеры стали самыми производительными вычислительными системами, резко возрос интерес к проблеме разработки для них параллельных прикладных программ [2].. К этому моменту уже было ясно, что трудоемкость разработки прикладных программ для многопроцессорных систем с распределенной памятью является главным препятствием для их широкого внедрения. За прошедший с тех пор период предложено много различных подходов к разработке параллельных программ, созданы десятки различных языков параллельного программирования и множество инструментальных средств.
Одним из таких языков является язык C-DVM [3]., разработанный в Институте прикладной математики им. М.В. Келдыша РАН при активном участии студентов и аспирантов факультета ВМиК МГУ им. М.В.Ломоносова. C-DVM представляет собой стандартный язык последовательного программирования ANSI C, расширенный спецификациями параллелизма в соответствии с моделью DVM (Distributed Virtual Machine, Distributed Virtual Memory – распределённая виртуальная машина, распределённая виртуальная память) [4].. Спецификации параллелизма – это средства описания правил параллельного выполнения программ. Они оформлены в виде специальных DVM-указаний.
DVM-указания предоставляют следующие возможности описания параллельного выполнения программы:
распределение элементов массива между процессорами;
распределение витков цикла между процессорами;
спецификация параллельно выполняющихся секций программы (параллельных задач) и отображение их на процессоры;
организация эффективного доступа к удаленным (расположенным на других процессорах) данным;
организация эффективного выполнения редукционных операций - глобальных операций с расположенными на различных процессорах данными (например, суммирование или нахождение максимального или минимального значения).
В настоящее время компиляция программы на языке C-DVM выполняется в два этапа:
компилятор C-DVM
компилятор C + коммуникационная библиотека MPI
программа на языке C-DVM
программа на языке C с вызовами функций библиотеки Lib-DVM
этап 1
этап 2
исполняемый модуль
Рисунок 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.
компилятор C + коммуникационная библиотека MPI
программа на языке C-DVM c DVM-указаниями в формате макросов
программа на языке C с вызовами функций библиотеки Lib-DVM
этап 1
этап 2
исполняемый модуль
программа на языке C-DVM c DVM-указаниями в формате прагм
существующий компилятор C-DVM
новый компилятор C-DVM
Рисунок 2. Схема компиляции программы на языке C-DVM в системе DVM существующим и новым компиляторами C-DVM
|
