Расширение объектно-ориентированных языков программирования параллельными конструкциями для многопроцессорных и распределенных систем

На правах рукописи

Гузев Вадим Борисович РАСШИРЕНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ПАРАЛЛЕЛЬНЫМИ КОНСТРУКЦИЯМИ ДЛЯ МНОГОПРОЦЕССОРНЫХ И РАСПРЕДЕЛЕННЫХ СИСТЕМ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва – 2009

Работа выполнена на кафедре Информационных технологий Российского Университета Дружбы Народов.

Научный консультант: кандидат физико-математических наук, профессор Толмачев Игорь Леонидович

Официальные оппоненты: доктор физико-математических наук, г.н.с. Института программных систем РАН Новосельцев Виталий Борисович, кандидат технических наук, Костарев Александр Николаевич

Ведущая организация: НИВЦ МГУ

Защита состоится “ ” 2009 г. в часов на заседании диссертационного совета Д 212.341.07 при Российском государственном социальном университете (г. Москва, ул. Вильгельма Пика, 4, зал диссертационного совета).

С диссертацией можно ознакомиться в библиотеке Российского государственного социального университета.

Автореферат разослан “ ” 2009 года.

Ученый секретарь диссертационного совета Д 212.341.07, к.ф.-м.н. Чумакова Е.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Для решения современных вычислительных задач постоянно создаются всё более мощные процессоры, позволяющие выполнять огромное количество операций в секунду. Многопроцессорные компьютеры (в т.ч. с многоядерными процессорами) получили огромное распространение в научной и образовательной сферах. Одновременно с этим разработчики вычислительной техники значительное внимание уделяют расширяемым системам, в которых производительность определяется количеством вычислительных узлов – процессоров, компьютеров, кластеров, объединяемых посредством высокоскоростной сети передачи данных. Между тем, разработка параллельных программ и обучение параллельному программированию всё ещё остаются нетривиальными задачами, что является основной причиной слабого использования заложенного в современных компьютерах потенциала. Одним из подходов, направленных на решение данной проблемы, является создание высокоуровневых, интуитивно понятных и надёжных языков программирования, а также систем времени исполнения (Runtime system) для данных языков, эффективно использующих возможности аппаратных платформ и легко расширяемых на произвольно заданное количество виртуальных узлов1.

Однако создание абсолютно новых параллельных языков программирования приводит к необходимости длительного и зачастую дорогостоящего обучения, что является очередной преградой широкому использованию параллельного программирования, т.к. языки остаются доступны лишь узкому кругу обученных программистов. В связи с этим весьма актуальной становится решаемая в рамках данной работы задача минимально необходимого и достаточного «гладкого» расширения широко распространенных современных объектно-ориентированных языков программирования конструкциями параллельного программирования.

Исследования в данной области непрерывно ведутся, начиная с 1980-х гг.

Было разработано множество расширений существующих языков: T++, Cilk, Unified Parallel C, Charm++, ZPL, HiPE, MultiLISP, Concurrent Haskell, Join Java, JoCaml и др. В 1995 г. Ц. Фурнье и Дж. Гонтье из института INRIA разрабатывают join-исчисление – процессную алгебру, представляющую формальный базис для разработки распределенных языков программирования.

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

join-patterns), которые позволяют выполнять некоторые действия при нахождении соответствий в поступающих по разным каналам сообщениях.

Разработка join-исчисления привела к появлению целого семейства join-языков.

В 2002 г. в Университете Южной Австралии создается язык Join Java, В терминологии, принятой при описании распределенных систем, виртуальным узлом (также могут использоваться названия «место», «сайт») называется виртуальный мультипроцессор с разделяемой памятью.

являющийся расширением языка Java. В 2003 г. корпорация Майкрософт спонсирует исследования по созданию языка Polyphonic C#, который позже был объединен с языком C (COmega) и теперь является кандидатом на слияние в следующих релизах с языком C#. Исследования в направлении расширения существующих языков также ведут такие компании как IBM (язык X10, расширяющий язык Java), Intel (Cluster OpenMP, расширяющий языки C++ и Fortran), Sun Microsystems (язык Fortress, расширяющий язык Fortran) и др.

Среди отечественных разработок стоит отметить три языка, разработанных в Институте программных систем РАН: T++, T# и MC#. Автор диссертации участвовал в разработке языка MC#, в процессе работы над которым появились новые идеи, ставшие в итоге основой для данной работы.

Цель исследований. Поддержка параллельного программирования для многопроцессорных и распределенных систем на базе существующих широко распространенных объектно-ориентированных языков программирования.

Основные задачи.

Выделение достаточного набора языковых конструкций для поддержки 1.

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

Разработка формального базиса (специального исчисления), 2.

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

Программная реализация нового языка Parallel C#, являющегося 3.

расширением языка C#. Проведение экспериментальных исследований на кластерных и многопроцессорных установках.

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

Основные положения, выносимые на защиту.

Модель «гладкого» расширения существующих языков 1.

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

Язык программирования Parallel C#, в котором реализована 2.

предлагаемая модель расширения для языка C#.

Реализация системы программирования Parallel C#:

3.

• для кластерных архитектур на базе Linux-платформ;

Сериализация объектов (serialization) – процесс перевода в битовую последовательность объектов, находящихся в оперативной памяти.

Десериализация объектов (deserialization) – процесс восстановления объектов в оперативной памяти компьютера из заданной битовой последовательности (процесс, обратный сериализации).

для многоядерных/многопроцессорных компьютеров на базе • Windows-платформ.

Научная новизна результатов исследования.

Впервые предложена технология расширения языков с помощью 1.

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

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

Практическая значимость работы. Разработанная технология расширения существующих объектно-ориентированных языков программирования позволяет повысить эффективность работы программистов при написании параллельных программ на расширенных языках за счет компактного синтаксиса и автоматической трансляции кода в базовые языки.

При этом в среднем отношение объема сгенерированного кода к объему, написанному программистом равно 10 к 1. Поскольку модель предполагает внесение минимальных изменений в распространенные языки программирования, существенно сокращаются временные и финансовые расходы на обучение программистов уже знакомых с базовым (расширяемым) языком.

Реализация результатов работы. Результаты работы внедрены в ЗАО «СиБОСС» в виде программного комплекса и проектной документации (акт об использовании результатов диссертационной работы от 25.05.2009 г.).

Апробация работы. Основные результаты работы представлялись на следующих конференциях и семинарах: “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 г.);

“II-й Белорусский космический конгресс”, Минск (25-27 октября 2005 г.);

“XII-ой международная конференция по вычислительной механике и современным прикладным программным системам (ВМСППС'2003)”, г. Владимир (30 июня - 5 июля г.);

“Международная конференция Parallel Computing Technologies (PACT'2003)”, Нижний Новгород (15-19 сентября 2003);

“Технологии Microsoft в научных исследованиях и высшем образовании”, Научно-техническая конференция по программированию, Москва (15-17 июня, 2003 г.);

“1st International Workshop on C# 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- February, 2003);

сообщения и доклады на научно-практических и научно методических конференциях РУДН в 2007-2008 гг.

Основное содержание диссертации отражено в 8 научных работах, включая одну публикацию в издании из списка ВАК.

Объем и структура работы. Диссертационная работа состоит из введения, 3 глав, заключения, библиографического списка, включающего наименований. Общий объем основного текста диссертации 107 страниц. В работе содержатся 10 рисунков и 8 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ВО ВВЕДЕНИИ обоснована актуальность работы и формулируются основные задачи диссертации.

В ПЕРВОЙ ГЛАВЕ выполнен аналитический обзор параллельных языков программирования CILK, АФС, T++, Polyphonic C#, X10 и MC# с целью выделения основных семантических конструкций, которые должны поддерживать современные параллельные языки программирования.

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

1. запуск функций в параллельном режиме на текущем виртуальном узле вычислительной системы;

2. запуск функций в параллельном режиме на наименее загруженном узле вычислительной системы;

3. синхронизация параллельно исполняемых функций (в т.ч.

исполняемых на разных виртуальных узлах вычислительной системы);

4. многократный двусторонний обмен данными между параллельно исполняемыми функциями (в т.ч. на других виртуальных узлах вычислительной системы).

ВТОРАЯ ГЛАВА посвящена описанию новой, практически использованной в рамках данной работы при создании языка Parallel C#, технологии расширения существующих объектно-ориентированных языков программирования средствами поддержки параллелизма.

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

Основная идея предлагаемой технологии расширения, состоит в том, что посредством добавления шести новых элементов можно расширить класс объектно-ориентированных языков программирования до класса объектно ориентированных языков со встроенной поддержкой параллельного программирования, удовлетворив при этом требования, сформулированные в выводах главы 1.

Ниже приведен список этих элементов, с перечислением существующих языков, в которых эти элементы используются:

Порождение нового потока на текущем узле с помощью асинхронных 1.

функций (async-методы в Polyphonic C#).

Синхронизация асинхронных и синхронных функций с помощью 2.

связок функций (связки в Polyphonic C#).

Использование объектов функциональных типов (функциональные 3.

языки программирования).

Порождение нового потока на другом виртуальном узле с помощью 4.

перемещаемых функций ("Т-функции" в Т++, movable-методы в MC#).

Автоматическая сериализация и десериализация объектов при 5.

пересылке между виртуальными узлами (MC#).

6. Автоматическая генерация прокси-функций (tptr в Т++).

На Error: Reference source not found приведена общая схема расширения объектно-ориентированных языков программирования с помощью вышеуказанных элементов:

Объектно- Распределенный Параллельныйязык ориентированный язык параллельныйязык программирования программирования программирования + + Асинхронные функции Перемещаемыефункции + + Автоматическая генерация Связки функции прокси-функций + + Автоматическая Объекты функциональных сериализация и типов десериализация объектов Рис. 1. Модель расширения объектно-ориентированных языков программирования для поддержки параллелизма Экспериментально показано (на примере реализации языка Parallel C#, а также разработанной на данном языке серии параллельных программ), что добавления этих конструкций достаточно для написания встречающихся в практике параллельных программ. Стоит подчеркнуть, что с помощью данных конструкций можно легко расширить многие другие языки программирования, в которых есть встроенные механизмы сериализации, такие как Java и Nemerle, т.е. модель рассчитана не на один конкретный язык программирования.

В разделах 2.1-2.3 описаны синхронные, асинхронные и перемещаемые типы функций для параллельных вычислительных систем.

Определение 1: Синхронная функция – функция, при вызове которой сторона, инициировавшая вызов функции, приостанавливает свою работу до завершения выполнения вызванной функции на том же виртуальном узле вычислительной системы, где был произведен вызов.

Определение 2: Асинхронная функция – функция, при вызове которой сторона, инициировавшая вызов, не приостанавливает свою работу после вызова функции, а продолжает выполняться параллельно с вызванной функцией на текущем виртуальном узле вычислительной системы.

Определение 3: Перемещаемая функция – подтип асинхронной функции, выполнение которой может производиться на любом из виртуальных узлов вычислительной системы.

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

В разделе 2.4 вводятся объекты функциональных типов, которые можно использовать при объявлении полей и свойств классов, в качестве локальных переменных, а также передавать в качестве параметров другим функциям, в том числе перемещаемым. Для передачи объектов между виртуальными узлами вычислительной системы используются механизмы автоматической сериализации/десериализации, которые описаны в разделе 2.5.

В разделах 2.6-2.7 описывается механизм автоматической генерации прокси-объектов для объектов функциональных типов (т.н. «прокси-функций») при их передаче другим функциям в качестве параметров. Прокси-функция содержит информацию о сигнатуре базовой функции и расположении оригинального виртуального узла, где была создана прокси-функция, что обеспечивает возможность удаленного вызова функции с других виртуальных узлов системой времени исполнения. В зависимости от типа базовой функции, для которой создается прокси-функция (асинхронная или синхронная), сама прокси-функция может быть асинхронной или синхронной.

В разделе 2.8 вводится определение "связок функций" (join patterns), которое заимствовано из языка Polyphonic C#.

Определение 4: Связка функций – это средство синхронизации нескольких параллельно исполняемых потоков, в котором:

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

- может быть объявлено только одно тело связки функций (набор команд), которое срабатывает тогда и только тогда, когда все функции, объявленные в заголовке связки, были вызваны;

- тело связки возвращает результат того же типа, что и объявленная в заголовке связки синхронная функция (если она присутствует).

Пример объявления связки в языке Parallel C#:

int Get() & async Result(int x) { return x;

} В данном примере в связке определены асинхронная функция Result и синхронная функция Get. Тело связки состоит из одного оператора – возврата целочисленного значения, поступившего при вызове функции Result.

При вызове функции Result производится проверка: если функция Get ещё не была вызвана, то параметры вызова функции Result ставятся в специальную очередь параметров. Как только функция Get будет вызвана, то параметры для тела связки будут браться из этой очереди.

Если же на момент вызова функции Result функция Get уже была вызвана, то происходит срабатывание связки (и соответственно из очереди потоков функции Get извлекается один приостановленный поток функция Get, и ей передаются параметры, переданные при запуске функции Result).

Наоборот: при вызове функции Get производится проверка, не была ли уже вызвана функция Result. Если эта функция вызвана не была, то текущий поток (вызвавший функцию Get) блокируется до тех пор, пока функция Result не будет вызвана. При этом заблокированный поток ставится в специальную очередь потоков, относящуюся к функции Get. Когда будет произведен вызов функции Result, сработает тело связки, а вместе с тем произойдёт чтение и извлечение параметров из этой очереди.

Если же на момент вызова функции Get функция Result уже была вызвана, то тело связки срабатывает моментально (и производится чтение и извлечение параметров из очереди функции Result).

Функции могут участвовать одновременно в нескольких связках, что может использоваться при решении классических задач типа "Поставщик Потребитель", где несколько поставщиков могут поставлять различные типы объектов, а один потребитель должен их обрабатывать. В следующем примере функция Get участвует одновременно в двух связках:

static int Get() & async Result(int x) {return x;

} static int Get() & async Result1(int x) & async Result2(int y){return x+y;

} В разделе 2.9 описывается формальный базис для получаемых с помощью описанной выше модели расширения языков путем введения специального исчисления, которое для краткости назовем «||-исчислением» (читается как «параллельное исчисление»). Основное отличие ||-исчисления от исчисления языка MC# 2.0 состоит в том, что в качестве базовой операции используется вызов функции, а не отправка сообщения. В зависимости от типа вызываемой функции и месторасположения оригинального виртуального узла, к которому привязана функция, вызов функции осуществляется на удаленном или локальном узле и таким образом само понятие «отправки и получения сообщений» становится не нужным. Кроме того, ссылки на функции можно передавать в качестве параметров другим функциям, т.е. они являются полноценными объектами. Ниже будет рассмотрена грамматика данного исчисления и его операционная семантика.

В ||-исчислении используются следующие обозначения: o – имена объектов;

sm – синхронные методы;

am – асинхронные методы;

mm – перемещаемые методы;

s, r, … – названия виртуальных узлов. Имена могут быть простыми или составными: во втором случае объекты от методов разделяются точкой, например, o.am. Кроме того, имена могут иметь нижние ~ индексы, например, s1, o2 и т.д. Конечный список выражений обозначается E.

В таблице 1 приведены базовые конструкции синтаксиса ||-исчисления:

Табл. 1.

Синтаксическая категория Выражение Комментарий AJ::= Заголовок асинхронной связки () ~ прототип объявления асинхронного метода aE m | AJ1 & AJ2 связка асинхронных методов ()~ SM::= Прототип синхронного метода sm E SJ::= SM & AJ Синхронная связка D::= Объявление методов объектов пустой объект () ~ | d E :P именованный процесс правило реакции для асинхронной связки | AJ P правило реакции для синхронной связки | SJ return E | D1, D2 дизъюнкция определений O::= Объявление объектов x=D объявление одного объекта | O1;

O2 объявление нескольких объектов (композитное объявление) E::= Выражения u имя |… числовые/строчные/буквенные значения (не описываем здесь) | am асинхронный метод | sm синхронный метод () ~ | sm E вызов синхронного метода P ::= Процессы 0 пустой процесс () ~ | x.s вызов синхронного метода mE | вызов асинхронного метода на локальном виртуальном узле () ~ x.am E ls ls | () вызов перемещаемого метода на виртуальном узле s ~ x.m E s m | P1 || P2 параллельное исполнение | obj x = D in P локальное определение объекта x в процессе P Как и в join-исчислении базовая часть грамматики ||-исчисления состоит из трёх синтаксических категорий – процессов P, объявлений D и связок AJ/SJ.

Кроме того, требуется, чтобы каждая из связок AJ/SJ не являлась частью другой связки (с точностью до перестановки местами входящих в связки заголовков методов).

Из табл.1 видно, что синтаксис ||-исчисления (а далее будет показано, что и семантика тоже) является дальнейшей модификацией формального исчисления для языка MC# 2.0, описанного в работе Ю.П.Сердюка4. Основное отличие заключается в том, что вместо каналов здесь используются асинхронные методы, вместо обработчиков канальных сообщений – синхронные методы, а вместо отправки сообщений используется более высокоуровневое средство – вызовы методов. Данные изменения были продиктованы стремлением скрыть от пользователей языка понятие каналов (и соответственно, обработчиков каналов), чтобы облегчить процесс обучения новым, расширенным параллельным языкам программирования. Так, отсутствие сообщений в исчислении сделало ненужными операторы для отправки и получения сообщений.

Для описания операционной семантики ||-исчисления опишем правила в стиле распределенной рефлексивной химической абстрактной машины (distributed reflexive chemical

Abstract

machine), описанной в работе Ц. Фурнье и Дж. Гонтье5.

Определение 5. Химическое решение CS – это отношение S[DP], состоящее из множества виртуальных узлов S, в котором каждый виртуальный узел si связан с множеством Di D объявлений этого виртуального узла и множеством Pi P исполняемых на виртуальном узле процессов.

Введем следующие обозначения:

1. P {E} – обозначает процесс P, в котором встречается выражение E, а выражение P {E2 / E1} определяет процесс, получающийся при замене E на E2 в процессе P.

2. o = {AJ P} – обозначает объявление объекта, в котором обязательно содержится связка AJ P.

~ ~ 3. x y – обозначает подстановку, которая заменяет каждое вхождение ~ x i соответствующим значением ~i (при условии, что длины векторов ~ y x ~ и y совпадают).

4. Выражение вида Os( ~ ) называется локализованным объектом, x относительно виртуального узла s, что означает, что объект был создан и находится на виртуальном узле s. Асинхронные и синхронные методы локализованных объектов относительно виртуального узла s будем Serdyuk Y. A formal basis for the MC# programming language, http://mcsharp.net/publications/formal_basis_extended_abstract.pdf Fournet C., Gonthier G. The Join Calculus: A Language for Distributed Mobile Programming. In Proceedings of the Applied Semantics Summer School (APPSEM), Caminha. Springer-Verlag, 2000, pp. 268-332.

называть локализованными методами, относительно виртуального узла s.

5. Пусть и – некоторые подстановки, удовлетворяющие условию domain ( ) domain ( ) =, где domain (x ) – область определения x. Тогда выражение означает новую подстановку с областью определения domain ( ) = domain ( ) domain ( ), в которой для каждого имени u верно следующее:

(u ), если u domain ( ) u ( ) = (u ), если u domain ( ) u, в остальных случаях Набор аксиом в ||-исчислении будет полностью, с точностью до смены обозначений, повторять аксиомы исчисления MC# 2.0 (приведены в самой диссертации).

Операционная семантика ||-исчисления задается правилами, рассмотренными ниже. В каждом правиле отображаются только те процессы и объявления, которые затрагиваются в данном вычислительном шаге.

1. NULL: s [ 0] s [] 2. PAR: s [ P1 || P2 ] s [ P1, P2 ] 3. DEF: s [ obj o in P ] s [ os P ] где – присваивает свободные имена (относительно виртуального узла s) объектам, описанным в o 4. SYNC-CALL:

~ ~ ~ ~ ~ s [o = {sm( x ):P} o.sm( y ) ] s [o = {sm( x ):P} P( x y )] s [o = {AJ s P} o.AJ ] s [o = {AJ s P} P ] 5. ASYNC-CALL:

где – подстановка, присваивающая свободные имена (относительно виртуального взла s) объектам, описанным в асинхронной связке AJ ~ ~ 6. JOINT-CALL: s [o = {sms( x ) & AJ s return E} P{sm( y )}, o.AJ ] ~ ~ ~ ~ s [o = {sms( x ) & AJ s return E} P{E( x y / sm( y )}] где – подстановка, присваивающая фактические значения формальным параметрам 7. MOVABLE-CALL:

s[ o s o.mm(x) r] r[] s [ o s ] r [ o s (o.mm(x))] где – подстановка, присваивающая свободные имена (относительно виртуального узла r) объектам, описанным в o ~ s [o = D s] r [o = D s P {o.sm( x )}] 8. REMOTE-SYNC-CALL:

s [o = Ds;

o2=F r o2.am(o.sm( ~ ))] x r [o = D ;

o2=F P {o2.sm() / o.sm( ~ )}] s r x ~ где r s и определение D = sm( x ) & AJ return E с некоторыми AJ и E, а o2 – это ~ новый объект с объявлением F = sm() & am( x )return E на виртуальных узлах s и r ~ s [o = D s] r[o = D s o.am( x )] 9. REMOTE-ASYNC-CALL:

s [o = D s o.am( ~ )] r[o = D s] x где r s и объявление D содержит асинхронную связку AJP или синхронную связку SJ return E, где AJ и SJ соответственно содержат асинхронный метод am.

Приведенная выше семантика предложенных конструкций с помощью абстрактных химических машин, позволяет существенно упростить реализацию этих конструкций для различных языков программирования.

В разделе 2.10 произведен детальный анализ получаемого семейства языков на примерах программ (вычисление чисел Фибоначчи, построение решета Эратосфена, перемножение матриц и поиск слов в больших текстах), написанных на языке Parallel C#. Приведен полный код программ, а также замеры производительности на кластерных установках. На Рис. 2 приведен график с замерами производительности программы поиска слов в больших текстах, написанной на языке Parallel C#.

Ускорение 2 4 8 16 Полученное Количество процессоров Линейное Рис. 2 График ускорения вычислений на примере поиска слов в тексте Замеры проводились на кластере СКИФ в конфигурации: двухпроцессорных узлов, процессоры AMD Athlon™ MP 1800+ с использованной системой Parallel C# Cluster Edition, ОС: Linux.

В ТРЕТЬЕЙ ГЛАВЕ описываются особенности двух практических реализаций систем программирования, основанных на описанном || исчислении, позволяющих компилировать и исполнять программы, написанные на языке Parallel C# в локальном режиме на Windows-машинах и в распределенном режиме на Linux-кластерах.

Реализация системы программирования Parallel C# состоит из компилятора и системы времени исполнения. Компиляция программ производится в две стадии:

Трансляция программы из языка Parallel C# в язык C#.

1.

Компиляция сгенерированных C#-файлов стандартным C# 2.

компилятором (csc для платформы Microsoft.Net и gmcs для платформы Mono), с подключением библиотек распределенной системы исполнения.

В разделах 3.1-3.2 детально описываются грамматика языка Parallel C#, а также принципы трансляции основных языковых элементов в базовый язык C#.

Раздел 3.3 посвящен вопросам реализации распределенной системы времени исполнения для кластерных архитектур на базе Linux, где выделяются одна главная машина, с которой запускаются все пользовательские приложения, а также рабочие узлы, на которых производится основная часть вычислений. На главной машине запускается менеджер распределения ресурсов, основной функцией которого является планирование и распределение запросов на исполнение перемещаемых методов (рис. 3). На рабочих узлах запускаются копии программы WorkNode, единственной функцией которой является запуск и остановка копий клиентских приложений на узлах.

Пользовательское приложение Менеджер распределения ресурсов Потоки выполнения перемещаемых методов Входящие сообщения Обслуживающие потоки Таблица объектов Communicator Перемещаемые методы...

Входящие сообщения...

Apps Прокси вызовы Очереди Пул потоков переданных параметров прокси-вызовов Nodes Пользовательские объекты и потоки Рис. 3 Схема ПО главного узла Каждый из узлов кластера должен быть доступен с других узлов посредством протоколов RSH/SSH. Для того чтобы пользовательскую программу можно было запустить на рабочих узлах, необходимо, чтобы исполняемые файлы этой программы находились на всех узлах кластера и пути к ним совпадали на всех узлах – это легко реализуется с помощью файловой системы NFS.

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

Коммуникатор содержит необходимую логику для принятия и запуска перемещаемых методов, прокси-вызовов и т.д.

При передаче прокси-функции в другую функцию автоматически создается прокси-объект, который регистрируется в специальной хеш-таблице коммуникатора, по которой коммуникатор находит зарегистрированные прокси-функции, когда приходят соответствующие команды.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ Предложена модель расширения существующих объектно 1.

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

2. Разработаны правила трансляции новых синтаксических конструкций в базовые языки и представлена в качестве демонстрации практическая реализация данных правил на примере языка Parallel C# (расширение существующего языка C#). Стоит отметить, что с помощью данных конструкций можно расширить многие языки программирования, например, Java, Nemerle и др., т.е. представленная модель рассчитана не только на один конкретный язык программирования.

Разработаны транслятор и две системы времени исполнения языка 3.

Parallel C# – для многопроцессорных и кластерных архитектур (обе системы оформлены как проект с открытым исходным кодом и доступны в Internet по адресу: www.parallelcsharp.com). Реализованы тестовые программы и произведены замеры производительности этих программ на кластере, показавшие приемлемый уровень ускорения на разном числе процессоров.

Разработанная в диссертации модель расширения существующих 4.

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

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

Публикации автора по теме диссертации 1. Гузев В.Б. Как решить проблему Санта-Клауса на языке Parallel C#.

Сборник работ студентов-победителей международных, всероссийских и университетских конкурсов, конференций, олимпиад 2008-2009 гг., М.:Изд-во РУДН, 2009, c. 8-19.

Гузев В.Б. Parallel C#: The usage of chords and higher-order functions in 2.

the design of parallel programming languages. In proc. of “The International Conference on Parallel and Distributed Processing Techniques and Applications”, Las Vegas, USA, CSREA Press, 2008, c.

833-837.

Гузев В.Б. Использование связок и функций высшего порядка для 3.

разработки языков параллельного программирования. Труды XLIV Всероссийской Конференции по Проблемам Математики, Информатики, Физики и Химии, секция “Программные Системы”, М.:Изд-во РУДН, 2008, c. 5-14.

Петров А.В., Гузев В.Б. MC# – универсальный язык параллельного 4.

программирования. // "Информационные технологии", №4, М.:Изд во Машиностроение, 2008, c. 29-32.

Сердюк Ю.П., Гузев В.Б. MC# Grid System: подход к Grid 5.

вычислениям на основе языка параллельного, распределенного программирования. – Труды Всероссийской научной конференции “Научный сервис в сети Интернет: технологии распределенных вычислений”, 19-24 сентября 2005, г. Новороссийск”, М.:Изд-во МГУ, 2005, c. 41-43.

Гузев В.Б., Молодченков А.И., Сердюк Ю.П. Решение задач 6.

обработки изображений в реальном времени на языке параллельного программирования MC#. Труды II-го Белорусского космического конгресса, 25-27 октября 2005 г., Минск: ОИПИ НАН Беларуси, 2005, c. 173-177.

Сердюк Ю.П., Гузев В.Б. Asynchronous Parallel Programming 7.

Language Based on the Microsoft.NET Platform. Proc. “7th International Conference PACT'2003”, Нижний Новгород: Lecture Notes in Computer Science, v. 2763, Springer Berlin / Heidelberg, 2003, c. 236-243.

Гузев В.Б., Сердюк, Ю.П., Чудинов А.М. MC#: An Asynchronous 8.

Parallel Programming Language for Cluster and GRID-Architectures.

Proc. of “C# and.NET Technologies'2003, 1st Int. Workshop on C# and.NET Technologies on Algorithms, Computer Graphics, Visualization, Distributed and WEB Computing”, 6-8 February, 2003, Plzen, Czech Republic, v. 1, №1-3, Plzen: Union Agency Science Press, 2003, c. 21-24.