Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР СУЩЕСТВУЮЩИХ ПАРАЛЛЕЛЬНЫХ ЯЗЫКОВ
ПРОГРАММИРОВАНИЯ 14
1.1. CILK 14
1.2.Т++ 18
АФС 21
POLYPHONIC С# 24
Х10 28
МС# 31
Основные выводы 40
ГЛАВА 2. ТЕХНОЛОГИЯ РАСШИРЕНИЯ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ
ПРОГРАММИРОВАНИЯ СРЕДСТВАМИ ПОДДЕРЖКИ ПАРАЛЛЕЛИЗМА 42
Синхронные функции 45
Асинхронные функции 46
перемещаемые функции 47
Объекты функциональных типов 50
Автоматическая сериализация / десериализация объектов 52
Асинхронные прокси-функции 53
Синхронные прокси-функции 53
Связки функций 54
Формальный базис для расширенных языков (|(-исчисление) 57
2.10. Эффективность программирования па языке parallel С# 67
Числа Фибоначчи 67
Решето Эратосфена 73
Бинарный семафор 75
Перемножение матриц 76
Поиск слов в тексте 77
2.11. Основные выводы 79
ГЛАВА 3. РЕАЛИЗАЦИЯ Ц-ИСЧИСЛЕНИЯ 80
Формальная грамматика 80
Транслятор 81
Общие положения 81
Трансляция функциональных типов 83
Трансляция асинхронных функций 84
Трансляция статических асинхронных функций 85
Трансляция перемещаемых функций 86
Трансляция статических перемещаемых функций .". 86
Трансляция связок методов 87
3.3. Распределённая система времени исполнения 93
Основные положения 93
Схема программного обеспечения главного узла кластера 95
Менеджер распределения нагрузки 96
Схема программного обеспечения рабочего узла кластера 98
Утилиты управления вычислительной системой 100
Транспорт 100
Сбор статистики о работе приложений 101
Реализация распределенной системы времени исполнения 102
3.4. Основные выводы 103
ЗАКЛЮЧЕНИЕ 106
СПИСОК ЛИТЕРАТУРЫ 108
ПРИЛОЖЕНИЕ 1. ИСХОДНЫЙ КОД РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ ЧИСЕЛ ФИБОНАЧЧИ
(РАСПРЕДЕЛЕННЫЙ ВАРИАНТ, НА ЯЗЫКЕ С#) 119
ПРИЛОЖЕНИЕ 2. ПРИМЕР ТРАНСЛИРОВАННОЙ В ЯЗЫК С# РАСПРЕДЕЛЕННОЙ ВЕРСИИ
ПРОГРАММЫ НА ЯЗЫКЕ PARALLEL С#, ВЫЧИСЛЯЮЩЕЙ ЧИСЛА ФИБОНАЧЧИ :..... 124
ПРИЛОЖЕНИЕ 3. РЕШЕНИЕ ПРОБЛЕМЫ САНТА-КЛАУСА (РАСПРЕДЕЛЕННЫЙ ВАРИАНТ, НА
ЯЗЫКЕ PARALLEL С#) 129
ПРИЛОЖЕНИЕ 4. ПРИМЕР РЕАЛИЗАЦИИ ФУНКЦИОНАЛЬНЫХ ТИПОВ 137
ПРИЛОЖЕНИЕ 5. ПОРЯДОК УСТАНОВКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ «PARALLEL С#
CLUSTER EDITION» НА КЛАСТЕРНУЮ УСТАНОВКУ СЕМЕЙСТВА СКИФ 140
ПРИЛОЖЕНИЕ 6. АКТ ОБ ИСПОЛЬЗОВАНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ... 142
Введение к работе
Актуальность работы.
Для решения современных вычислительных задач постоянно создаются всё более мощные процессоры, позволяющие выполнять огромное количество операций в секунду. Многопроцессорные компьютеры (в т.ч. с многоядерными процессорами) получили широкое распространение в научной и образовательной сферах. Наряду с этим разработчики вычислительной техники значительное внимание уделяют расширяемым системам, в которых производительность определяется количеством вычислительных узлов -процессоров, компьютеров, кластеров, объединяемых посредством высокоскоростной сети передачи данных. Между тем, разработка параллельных программ и обучение параллельному программированию всё ещё остаются нетривиальными задачами, что является основной причиной слабого использования заложенного в современных компьютерах потенциала. Одним из подходов, направленных на решение данной проблемы, является создание высокоуровневых, интуитивно понятных и надёжных языков программирования, а также систем времени исполнения (Runtime system) для данных языков, эффективно использующих возможности аппаратных платформ и легко расширяемых на произвольно заданное количество виртуальных узлов.' Однако создание абсолютно новых параллельных языков программирования приводит к необходимости длительного и затратного обучения, что является очередной преградой широкому использованию параллельного программирования, т.к. языки остаются доступны лишь узкому кругу
1 В терминологии, принятой при описании распределенных систем [1], виртуальным узлом (также могут использоваться названия «место», «сайт») называется виртуальный мультипроцессор с разделяемой памятью.
5 обученных специалистов. В связи с этим весьма актуальной становится решаемая в рамках данной работы задача «гладкого» расширения широко распространенных современных объектно-ориентированных языков программирования средствами параллельного программирования.
Исследования в данной области непрерывно ведутся, начиная с 1980-х гг. Было разработано множество расширений существующих языков: Т++ [2], Cilk [3], Unified Parallel С [4], Charm++ [5], ZPL [6], HiPE [7], MultiLISP [8], Concurrent Haskell [9], Join Java [10], JoCaml [11] и др. В 1992 P. Милнер, Ё. Пэрроу и Д. Уолкер разработали л-исчисление [12], процессную алгебру, (являющуюся расширением CCS-исчисления, Calculus of Communicating Systems), основная цель которой - помочь при описании параллельных вычислений, конфигурация которых может меняться во время самих вычислений. В 1995 г. Ц. Фурнье и Дж. Гонтье из института INRIA разрабатывают join-исчисление [13] - процессную алгебру, представляющую формальный базис для разработки распределенных языков программирования. Данное расширение имеет важное преимущество по сравнению с я> исчислением — возможность определения образцов связок (join-patterns), которые позволяют выполнять некоторые действия при нахождении соответствий в поступающих по разным каналам сообщениям. Разработка join-исчисления привела к появлению целого семейства join-языков. В 2002 г. в Университете Южной Австралии создается язык Join Java [10], являющийся расширением языка Java. В 2003 г. корпорация Майкрософт спонсирует исследования по созданию языка Polyphonic С#, который позже был объединен с языком Сш [14] и теперь является кандидатом на слияние в следующих версиях с языком С#. Исследования в направлении расширения существующих языков также ведут такие компании как IBM (язык XI0 [15], расширяющий язык Java), Intel (Cluster OpenMP [16], расширяющий языки C++ и Fortran), Sun
Microsystems (язык Fortress [17], расширяющий язык Fortran) и др. Все предложенные расширения являются оптимизированными под конкретные базовые языки.
Среди отечественных разработок на сегодняшний день, к сожалению, можно выделить лишь три языка, разработанных в Институте программных систем РАН: Т++ [2, 18, 19] (расширение языка C++, созданное в рамках суперкомпьютерной программы СКИФ [20, 21] России и Белоруссии), Т# [22] и МС# [23] (оба языка являются расширениями языка С#). Автор данной диссертации участвовал в разработке языка МС#, в процессе работы над которым появились новые идеи, которые стали основой для данной работы.
Цель работы. Цель диссертационной работы - поддержка параллельного программирования для многопроцессорных и распределенных систем на базе существующих широко распространенных объектно-ориентированных языков программирования.
Методы исследования. В работе используются методы формального описания исчислений с помощью абстрактных химических машин, теории компиляции, теории параллельного программирования, теории алгоритмов, теории мультиагентных систем и технологий построения кластерных систем. Научная новизна результатов исследования.
1. Впервые предложена технология расширения языков с помощью асинхронных, синхронных и перемещаемых функций, объектов функциональных типов, автоматической генерации прокси-функций, автоматической сериализации и десериализации объектов при пересылке между виртуальными узлами, и связок асинхронных и синхронных функций, служащих средством синхронизации потоков, что обеспечивает простую интерпретацию наследуемых языков.
2. Задана формальная семантика предложенных конструкций с
помощью абстрактных химических машин, что позволяет
существенно упростить реализацию этих конструкций для различных
языков программирования.
Практическая значимость работы. Разработанная технология
расширения существующих объектно-ориентированных языков
программирования (имеющих встроенные механизмы
сериализации/десериализации) позволяет повысить эффективность работы
программистов при написании параллельных программ на расширенных языках
за счет компактного синтаксиса и автоматической генерации кода в базовых
языках. При этом среднее отношение объема сгенерированного кода к объему,
написанному разработчиком равно =10 к 1. Поскольку модель предполагает
внесение минимальных изменений в распространенные языки
программирования, существенно сокращаются временные и финансовые
расходы на обучение программистов уже знакомых с базовым (расширяемым)
языком.
Апробация работы. Основные результаты работы представлялись на следующих конференциях и семинарах:
"The 2008 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'08)", Monte Carlo Resort, Las Vegas, Nevada, USA (July 14-17, 2008);
"XLIV Всероссийской Конференции по Проблемам Математики, Информатики, Физики и Химии, секция "Программные Системы", г. Москва, Российский Университет Дружбы Народов (21-25 апреля 2008
г.);
"Всероссийская научная конференция "Научный сервис в сети Интернет: технологии распределенных вычислений", г. Новороссийск (19-24 сентября 2005 г.);
"П-й Белорусский космический конгресс", Минск (25-27 октября 2005 г.);
"ХП-ой международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2003)", г. Владимир (30 июня - 5 июля 2003 г.);
"Международная конференция Parallel Computing Technologies 2003 (РАСГ2003)", Нижний Новгород (15-19 сентября 2003);
"Технологии Microsoft в научных исследованиях и высшем образовании", Научно-техническая конференция по программированию, Москва (15-17 июня, 2003 г.);
"1st International Workshop on С# and .NET Technologies on Algorithms, Computer Graphics, Visualization, Distributed and WEB Computing (C# and .NET Technologies'2003)", University of West Bohemia, Plzen, Czech Republic (5-7 February, 2003);
сообщения и доклады на научно-практических и научно-методических конференциях РУДН в 2007-2009 гг.
Основное содержание диссертации отражено в 8 научных работах, включая одну публикацию в издании из списка ВАК.
Структура и объем работы.
Диссертационная работа состоит из введения, 3 глав, заключения, библиографического списка, включающего 105 наименований. Общий объем основного текста диссертации 107 страниц. В работе содержатся 10 рисунков и 8 таблиц.
Содержание работы.
В первой главе выполнен аналитический обзор параллельных языков программирования CILK, АФС, Т++, Polyphonic С#, XI0 и МС#. Отмечается тенденция увеличения уровня абстракции и гранул параллелизма в создаваемых языках программирования. Показано, что создателей новых параллельных языков программирования интересует не столько распараллеливание отдельных арифметических операций, сколько распараллеливание на уровне функций и объектов. При этом основными требованиями к параллельным языкам являются:
запуск функций в параллельном режиме на текущем виртуальном узле вычислительной системы;
запуск функций в параллельном режиме на наименее загруженном узле вычислительной системы;
синхронизация параллельно исполняемых функций (в т.ч. исполняемых на разных виртуальных узлах вычислительной системы);
многократный двусторонний обмен данными между параллельно исполняемыми функциями (в т.ч. на разных виртуальных узлах).
Вторая глава посвящена описанию новой, практически использованной в рамках данной работы при создании языка Parallel С#, технологии расширения существующих объектно-ориентированных языков программирования средствами поддержки параллелизма.
Каждый язык программирования характеризуется определенным набором базовых элементов. Например, все функциональные языки содержат элементы "функция", "вызов функции", "область видимости". А все объектно-ориентированные языки программирования содержат элементы "объект", "класс", "метод".
10 Основная идея предлагаемой технологии расширения, состоит в том, что посредством добавления шести новых элементов можно расширить класс объектно-ориентированных языков программирования до класса объектно-ориентированных языков со встроенной синтаксической поддержкой параллельного программирования, удовлетворив при этом требования, сформулированные в выводах главы 1. Ниже приведен список этих элементов, с перечислением существующих языков, в которых эти элементы используются:
Порождение нового потока на локальном виртуальном узле с помощью асинхронных функций (async-методы в Polyphonic С#);
Синхронизация асинхронных и синхронных функций с помощью связок функций (связки в Polyphonic С#);
Использование объектов функциональных типов (функциональные языки программирования);
Порождение нового потока на другом виртуальном узле с помощью перемещаемых функций ("Т-функции" в Т++, movable-методы в МС#);
Автоматическая сериализация и десериализация объектов при пересылке между виртуальными узлами (МС#);
Автоматическая генерация прокси-функций (tptr в Т++). Экспериментально показано (на примере реализации языка Parallel С#, а
также разработанной на данном языке серии параллельных программ), что добавления этих конструкций достаточно для написания встречающихся в практике параллельных программ. Стоит подчеркнуть, что с помощью данных конструкций можно легко расширить многие другие языки программирования, в которых есть встроенные механизмы сериализации, такие как Java и Nemerle, т.е. модель рассчитана не на один конкретный язык программирования.
На рис. 1.1 приведена схема расширения объектно-ориентированных языков программирования с помощью вышеуказанных элементов:
Объектно-ориентированный язык программирования
Параллельный язык программирования
Распределенный параллельный язык программирования
Асинхронные функі^
ещаемые функции
дии І— j Переме
Связки функции I—
Автоматическая генераї прокси-функций
Объекты функциональных типов
І Автоматическая
сериапизация и | десериализация объектов
Рисунок 1.1. Модель расширения объектно-ориентированных языков программирования для поддержки параллелизма
В разделах 2.1-2.8 подробно рассматриваются составляющие указанной выше схемы.
В разделе 2.9 описывается формальный базис для семейства расширенных языков, а в разделе 2.10 произведен детальный анализ получаемого семейства языков на примерах программ (вычисление чисел Фибоначчи, построение решета Эратосфена, использование бинарного семафора в распределенных программах, перемножение матриц, поиск слов в больших текстах и проблема Санта-Клауса), написанных на языке Parallel С#.
Показано, что количество строк кода в программах на языке Parallel С# (по сравнению с версиями на языке С#) сокращается:
для распределенных программ - в -10 раз;
для нераспределенных программ - в ~1,7 раз.
В третьей главе описываются особенности практических реализаций систем исполнения, основанных на описанном |[-исчислении:
1. Parallel С# Many Core Edition - система программирования, позволяющая компилировать и исполнять программы, написанные на
12 языке программирования Parallel С# в локальном режиме на Windows-машинах (в т.ч. на многоядерных машинах). 2. Parallel С# Cluster Edition — система программирования, позволяющая компилировать и исполнять программы, написанные на языке программирования Parallel С# на Linux-кластерах. Реализация Parallel С# состоит из компилятора и системы времени исполнения. Компиляция программ, написанных на языке Parallel С#, производится в две стадии:
Трансляция программы из языка Parallel С# в язык С#;
Компиляция сгенерированных С#-файлов стандартным С# компилятором (esc для платформы Microsoft .Net и gmes для платформы Mono), с подключением библиотек распределенной системы исполнения.
В качестве инструментов для практической реализации транслятора были выбраны GPLEX (генератор лексеров) и GPPG (генератор LALR(l) парсеров). Данный выбор был обусловлен тем, что эти инструменты генерируют код на языке С#, а также упрощают задачу интеграции со средой разработки Microsoft Visual Studio (с помощью дополнительного инструмента — Managed Babel).
Трансляция программ с языка Parallel С# в язык С# состоит из нескольких этапов:
Разбиение программы на токены с помощью лексера.
Разбор потока токенов с помощью парсера и генерация абстрактного синтаксического дерева (AST).
Двухфазная трансформация AST-дерева с помощью паттерна IVisitor.
Генерация кода на языке С# (также с помощью паттерна IVisitor).
В разделах 3.1-3.2 детально описываются грамматика языка Parallel С#, а также принципы трансляции основных языковых элементов в язык низшего уровня (в данном случае - С#).
