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

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

Гузев Вадим Борисович

РАСШИРЕНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ПАРАЛЛЕЛЬНЫМИ КОНСТРУКЦИЯМИ ДЛЯ МНОГОПРОЦЕССОРНЫХ и РАСПРЕДЕЛЕННЫХ СИСТЕМ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва - 2009

003493833

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

Научный руководитель:

кандидат физико-математических наук, профессор

Толмачев Игорь Леонидович

Официальные оппоненты:

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

кандидат технических наук, Костарев Александр Николаевич

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

Защита состоится "¿3" 2009 г. в часов на заседании

диссертационного совета Д 212.341 Ъ1 при Российском государственном социальном университете (г. Москва, ул. Вильгельма Пика, 4, зал диссертационного совета).

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

Автореферат разослан кслЬ|ц2009 года.

Ученый секретарь

диссертационного совета Д 212.341.07, к.ф.-м.н.

Чумакова Е.В.

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

Актуальность исследования. Для решения современных вычислительных задач постоянно создаются всё более мощные процессоры, позволяющие выполнять огромное количество операций в секунду. Многопроцессорные компьютеры (в т.ч. с многоядерными процессорами) получили огромное распространение в научной и образовательной сферах. Одновременно с этим разработчики вычислительной техники значительное внимание уделяют расширяемым системам, в которых производительность определяется количеством вычислительных узлов - процессоров, компьютеров, кластеров, объединяемых посредством высокоскоростной сети передачи данных. Между тем, разработка параллельных программ и обучение параллельному программированию всё ещё остаются нетривиальными задачами, что является основной причиной слабого использования заложенного в современных компьютерах потенциала. Одним из подходов, направленных на решение данной проблемы, является создание высокоуровневых, интуитивно понятных и надёжных языков программирования, а также систем времени исполнения (Runtime system) для данных языков, эффективно использующих возможности аппаратных платформ и легко расширяемых на произвольно заданное количество виртуальных узлов. Однако создание абсолютно новых параллельных языков программирования (К.Н. Ефимкин, А.Н. Адрианов, Ю.П. Кораблин, Ч. Лейзерсон), приводит к необходимости длительного и зачастую дорогостоящего обучения, что является очередной преградой широкому использованию параллельного программирования, т.к. языки остаются доступны лишь узкому кругу обученных программистов. В связи с этим весьма актуальной становится решаемая в рамках данной работы задача минимально необходимого и достаточного «гладкого» расширения широко распространенных современных объектно-ориентированных языков программирования конструкциями параллельного программирования (С.М. Абрамов, Ю.П. Сердюк, A.JI. Ластовецкий, Г.С. Итштейн, Н. Бентон, Л. Карделли, Ц. Фурнье, В. Саркар).

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

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

исчислением является возможность определения специальных связок (англ. join-patterns), которые позволяют выполнять некоторые действия при нахождении соответствий в поступающих по разным каналам сообщениях. Разработка join-исчисления привела к появлению целого семейства join-языков. В 2002 г. в Университете Южной Австралии создается язык Join Java, являющийся расширением языка Java. В 2003 г. корпорация Майкрософт спонсирует исследования по созданию языка Polyphonic С#, который позже был объединен с языком Ссо (COmega) и теперь является кандидатом на слияние в следующих релизах с языком С#. Исследования в направлении расширения существующих языков также ведут такие компании как IBM (язык Х10, расширяющий язык Java), Intel (Cluster OpenMP, расширяющий языки С++ и Fortran), Sun Microsystems (язык Fortress, расширяющий язык Fortran) и др.

Среди отечественных разработок стоит отметить три языка, разработанных в Институте программных систем РАН: Т++, Т# (Абрамов С.М., Адамович А.И., Роганов В.А.) и МС# (Сердюк Ю.П.).

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

Объект исследования: языки параллельного и распределенного программирования.

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

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

Задачи исследования:

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

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

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

4. Разработать язык параллельного программирования с использованием предложенных инструментальных средств.

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

Теоретико-методологическую основу исследования составили научные труды, посвященные параллельным расширениям языков программирования в отечественной и зарубежной науке (С.М. Абрамов, Ю.П. Сердюк, А.Л. Ластовецкий, Г.С. Итштейн, Н. Бентон, Л. Карделли, Ц. Фурнье, В. Саркар и др.); теория языков программирования и методов трансляции (Е.Л. Романов); теория алгоритмов (А. Тьюринг, Д. Кнут, А. Ахо, Дж. Ульман); теория мультиагентных систем (М. Вулдбридж, Ж. Фербер); теория формальных языков (Дж. Хопкрофт, Дж. Ульман); теория параллельных вычислений (Гергель В.П.).

Для достижения цели исследования, решения поставленных задач был использован комплекс методов, адекватных объекту и предмету исследования: теоретический анализ научной литературы, описание формальной семантики с помощью абстрактных химических машин (Дж. Бэрри, Дж. Боудол) и нотации Бэкуса-Наура (Н. Хомский), технологии построения кластерных систем (Гергель В.П.), семантические методы анализа программ (Ю.П. Кораблин, Н.Л. Куликова, Е.В. Чумакова). Замеры производительности выполнены с использованием кластерной установки СКИФ Первенец.

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

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

Этапы исследования.

Первый этап (октябрь 2006 - сентябрь 2007) - постановка проблемы исследования, определение объекта и предмета исследования, цели и задач. Проведение теоретического анализа научных исследований по изучаемой проблематике.

Второй этап (октябрь 2007 - сентябрь 2008) - разработка технологии расширения языков программирования, разработка и реализации плана экспериментальной работы.

Третий этап (октябрь 2008 - сентябрь 2009) - обработка и анализ полученных результатов исследования, оформление результатов исследования.

Отличие теоретических и эмпирических данных исследования от результатов, полученных другими авторами, состоит в том, что впервые

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

База исследования. Исследование проведено на базе кластерной установки СКИФ Первенец-М, установленной в ИПС РАН в г. Переславле-Залесском.

Основные результаты, полученные лично соискателем, и их научная новизна состоит в том, что:

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

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

3. Задана формальная семантика предложенных конструкций (упрощенный вариант исчисления МС# 2.0), что позволяет существенно упростить реализацию этих конструкций для различных языков программирования.

4. Разработан язык программирования Parallel С#, при реализации которого была использована предложенная технология расширения для языка С#.

5. Реализованы две системы программирования для Parallel С#, состоящие из транслятора и систем времени исполнения:

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

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

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

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

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

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

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

1. На основе результатов анализа языков параллельного программирования CILK, АФС, Т++, Polyphonic С#, Х10, и МС# выделен следующий набор функциональных требований:

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

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

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

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

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

• порождение нового потока на текущем узле с помощью асинхронных функций;

• синхронизация асинхронных и синхронных функций с помощью связок функций;

• использование объектов функциональных типов;

• порождение нового потока на другом виртуальном узле с помощью перемещаемых функций;

• автоматическая сериализация и десериализация объектов при пересылке между виртуальными узлами;

• автоматическая генерация прокси-функций.

3. Разработана технология «гладкого» расширения существующих языков программирования, базирующаяся на основе предложенного в п.2 набора языковых конструкций. Описана формальная семантика предложенных конструкций (||-исчисление) с помощью механизма абстрактных химических машин. Стоит отметить, что с помощью данных конструкций можно расширить многие языки программирования, например, Java, Nemerle и др., т.е. представленная технология рассчитана не только на один конкретный язык программирования.

4. Разработан язык программирования Parallel С#, при реализации которого была использована предложенная технология расширения для языка С#.

5. Реализованы две системы программирования для Parallel С#, состоящие из транслятора и систем времени исполнения:

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

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

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

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

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

Структура диссертации: диссертационная работа состоит из введения, трёх глав, заключения, списка литературы и приложений. Общий объем диссертации 143 страницы. Работа содержит 8 таблиц, 10 рисунков и 6 приложений. Список литературы включает 105 наименований.

II. ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении обоснована актуальность работы и формулируются основные задачи диссертации.

В первой главе - «Аналитический обзор существующих параллельных языков программирования» выполнен аналитический обзор параллельных языков программирования CILK, АФС, Т++, Polyphonic С#, Х10 и МС# с целью выделения основных семантических конструкций, которые должны поддерживать современные параллельные языки программирования. Отмечается тенденция увеличения уровня абстракции и гранул параллелизма в создаваемых языках программирования. Показано, что создателей новых параллельных языков программирования интересует не столько распараллеливание отдельных арифметических операций, сколько распараллеливание на уровне функций и объектов.

При этом основными функциональными требованиями к параллельным языкам программирования являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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() s async Resultl(int x) S async Result2(int y){return x+y;)

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

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

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

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

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

1. Порождение нового потока на текущем узле с помощью асинхронных функций (async-методы в Polyphonic С#).

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

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

4. Порождение нового потока на другом виртуальном узле с помощью перемещаемых функций ("Т-функции" в Т++, movable-методы в МС#).

5. Автоматическая сериализация и десериализация объектов при пересылке между виртуальными узлами (МС#).

6. Автоматическая генерация прокси-функций (tptr в Т++). Экспериментально показано (на примере реализации языка Parallel С#, а

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

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

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

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

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

В ||-исчислении используются следующие обозначения: о - имена объектов; $т - синхронные методы; ат - асинхронные методы; тт -перемещаемые методы; б, г, ... - названия виртуальных узлов. Имена могут быть простыми или составными: во втором случае объекты от методов разделяются точкой, например, о.ат. Кроме того, имена могут иметь нижние индексы, например, 5 , о и т.д. Конечный список выражений обозначается Ё.

Как и в ]от-исчислении базовая часть грамматики ||-исчисления состоит из процессов Р, объявлений Б и связок АЛЫ. Кроме того, требуется, чтобы каждая из связок АЛЫ не являлась частью другой связки (с точностью до перестановки местами входящих в связки заголовков методов).

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

Синтаксическая категория Выражение Комментарий

AJ::= Заголовок асинхронной связки

прототип объявления асинхронного метода

\AJ &AJ связка асинхронных методов

SM::= sm (e) Прототип синхронного метода

SJ::= SM&AJ Синхронная связка

D:.= Объявление методов объектов

1 пустой объект

1 d{E):P именованный процесс

\AJ-P правило реакции для асинхронной связки

| SJ ' return E правило реакции для синхронной связки

1 D.D дизъюнкция определений

Объявление объектов

x = D объявление одного объекта

1 0.0 объявление нескольких объектов (композитное объявление)

Выражения

и Имя

числовые/строчные/буквенные значения (не описываем здесь)

1 am асинхронный метод

| sm синхронный метод

1 вызов синхронного метода

P::= Процессы

0 пустой процесс

| x.sm (/-*') вызов синхронного метода

1 X .¿911 (if) —^¿y вызов асинхронного метода на локальном виртуальном узле

и

x.rrm (E) —>s вызов перемещаемого метода на виртуальном узле 5

\P ||P параллельное исполнение

\ob\x = Dm P локальное определение объекта х в процессе Р

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

Для описания операционной семантики ||-исчисления опишем правила в стиле распределенной рефлексивной химической абстрактной машины (distributed reflexive chemical abstract machine), описанной в работе Ц. Фурнье и Дж. Гонтье .

Определение 5. Химическое решение CS - это отношение S[D f-P], состоящее из множества виртуальных узлов S, в котором каждый виртуальный узел связан с множеством о & о объявлений этого виртуального узла и множеством Р исполняемых на виртуальном узле процессов. Введем следующие обозначения:

1. Р {Е} - обозначает процесс Р, в котором встречается выражение Е, а выражение Р {Е / Е } определяет процесс, получающийся при замене Е на Е в процессе Р.

2. о = {AJ > Р) - обозначает объявление объекта, в котором обязательно содержится связка AJ > Р.

3. * =Ф у - обозначает подстановку, которая заменяет каждое вхождение соответствующим значением у, (при условии, что длины векторов х и у совпадают).

4. Выражение вида О(х) называется локализованным объектом, относительно виртуального узла s, что означает, что объект был создан и находится на виртуальном узле s. Асинхронные и синхронные методы локализованных объектов относительно виртуального узла s будем называть локализованными методами, относительно виртуального узла s.

5. Пусть сг и е - некоторые подстановки, удовлетворяющие условию domain (а)Глс1оппт (f)=0> где domain (х) _ область Определения X. ТоГДа выражение о-в означает новую подстановку с областью определения

Serdyuk Y. A formal basis for the MC# programming language, http://mcsharp.net/pubIications/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.

domain(a ° 0) - domain(cr) \j domam(O), в которой ДЛЯ каждого имени и верно следующее:

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

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

1. ЛГЩ.:дГ|-01*лГ|-1

2. PAR. *[(-Л||Р2] ^[ЬЛ.Рг]

3. DEP. s [ |- obj о in P ] ^ s [ osa |- Pa ]

где О - присваивает свободные имена (относительно виртуального узла s) объектам, описанным в о

4. SYNC-CALL.

s [о= {sm(x)-.P} \-o.sm(y)] -> j[o= {sm(x)-.P} f-P(3t=*y)]

5. ASYNC-CALL: s [о = {АР > P}\oAJa\-» 5 [o = {AJ% > P) |-P <J]

где a - подстановка, присваивающая свободные имена (относительно виртуального взла s) объектам, описанным в асинхронной связке AJ

6. JOINT-CALL: s Го = IsmHx ) & AJS > return £} \-P{sm(y)}, oMo]

i[o= {sms(x)&AJ* ' return E] о a I sm(y)}]

где a - подстановка, присваивающая фактические значения формальным параметрам

7. MOVABLE-CALL:

j[o' о.тт(х)—> г] || /"[(-] ^ J [ о' [-] || г [ о' СГ ¡-(о.тт(х))а] где а - подстановка, присваивающая свободные имена (относительно виртуального узла г) объектам, описанным в о

8. REMOTE-SYNC-CALL. s [о = Ds |-] || г [о = Ds |- P {o-sm(3c)}] -

s [о = DS; 02=F'V 02.am(0.sm(x))] || r [o = Ds-o2=F' P {o2.sm() 1 o.sm(x )}] где rt su определение D = sm( x)&AJ * return E с некоторыми A J и E, a 02 - это новый объект с объявлением F - smQ & ат( х ) ► return Е на виртуальных узлах sur

9. REMOTE-ASYNC-CALL: s (о = Ds (-] Il r[o = Ds (- o.am(x )] -

•s [o = Ds \-o.am{x)] || r[o = D* ¡-] где r + s и объявление D содержит асинхронную связку AJ'P или синхронную связку SJ ' return Е, где A J и S J соответственно содержат асинхронный метод am.

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

В конце главы произведен детальный анализ получаемого семейства языков на примерах программ (вычисление чисел Фибоначчи, построение

решета Эратосфена, перемножение матриц и поиск слов в больших текстах), написанных на языке Parallel С#. Приведен полный код программ.

В третьей главе - «Реализация ||-исчисления» описываются особенности двух практических реализаций систем программирования, основанных на описанном ||-исчислении, позволяющих компилировать и исполнять программы, написанные на языке Parallel С# в локальном режиме на Windows-машинах и в распределенном режиме на Linux-кластерах.

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

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

2. Компиляция сгенерированных С#-файлов стандартным С# компилятором (csc для платформы Microsoft .Net и gmcs для платформы Mono), с подключением библиотек распределенной системы исполнения.

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

Рнс.2 Схема ПО главного узла

Каждый из узлов кластера должен быть доступен с других узлов посредством протоколов Я8Н/88Н. Для того чтобы пользовательскую

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

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

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

На рис.3 приведен график с замерами производительности программы поиска слов в больших текстах, написанной на языке Parallel С#.

35 30 25

а

| 20

10 5 0

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

Основные выводы по результатам исследования:

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

17

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

Разработаны правила трансляции новых синтаксических конструкций в базовые языки и представлена в качестве демонстрации практическая реализация данных правил на примере языка Parallel С# (расширение существующего языка С#). Стоит отметить, что с помощью данных конструкций можно расширить многие языки программирования, например, Java, Nemerle и др., т.е. представленная технология рассчитана не только на один конкретный язык программирования. Разработаны транслятор и две системы времени исполнения языка Parallel С# - для многопроцессорных и кластерных архитектур (обе системы оформлены как проект с открытым исходным кодом и доступны в Internet по адресу: wvw.parallelcsharp.com'). Реализованы тестовые программы и произведены замеры производительности этих программ на кластере, показавшие приемлемый уровень ускорения на разном числе процессоров. Разработанная в диссертации технология расширения существующих языков программирования позволяет повысить эффективность работы программистов при написании параллельных программ за счет компактного и понятного синтаксиса, а также автоматической генерации кода при трансляции в базовые языки. Кроме того, т.к. технология предполагает внесение минимальных изменений в существующие языки программирования, то существенно сокращаются временные и финансовые расходы на обучение программистов уже знакомых с базовым (расширяемым) языком, что является сегодня существенным барьером для распространения параллельных технологий.

III. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Петров A.B., Гузев В.Б. МС# - универсальный язык параллельного программирования. // Информационные технологии, М.:Изд-во Машиностроение, 2008, №4, с. 29-32. (0,25 п.л.) (издание рекомендовано ВАК РФ).

Гузев В.Б. Как решить проблему Санта-Клауса на языке Parallel С#. Сборник работ студентов-победителей международных, всероссийских и университетских конкурсов, конференций, олимпиад 2008-2009 гг., М.:Изд-во РУДН, 2009, с. 8-19. (0,37 п.л.).

Guzev V.B. Parallel С#: The usage of chords and higher-order functions in the design of parallel programming languages. In proc. of "The 2008 International Conference on Parallel and Distributed Processing Techniques and Applications", Las Vegas, USA, CSREA Press, 2008, pp. 833-837. (0,31 п.л.).

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

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

5. Сердюк Ю.П., Гузев В.Б. МС# Grid System: подход к Grid-вычислениям на

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

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

изображений в реальном времени на языке параллельного программирования МС#. Труды И-го Белорусского космического конгресса, 25-27 октября 2005 г., Минск: ОИПИ HAH Беларуси, 2005, с. 173-177. (0,16 п.л.).

7. Serdyuk Y.P., Guzev V.B. Asynchronous Parallel Programming Language Based

on the Microsoft .NET Platform. Proc. "7th International Conference PACT'2003", Нижний Новгород: Lecture Notes in Computer Science, v. 2763, Springer Berlin / Heidelberg, 2003, pp. 236-243. (0,25 пл.).

8. Гузев В.Б., Сердюк, Ю.П., Чудинов A.M. МС#: An Asynchronous 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. (0,21 пл.).

Общий объем публикаций по теме диссертации составляет -1,79 п.л.

Гузев Вадим Борисович

РАСШИРЕНИЕ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ПАРАЛЛЕЛЬНЫМИ КОНСТРУКЦИЯМИ ДЛЯ МНОГОПРОЦЕССОРНЫХ И РАСПРЕДЕЛЕННЫХ СИСТЕМ

Специальность 05.13.11 -математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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

Изготовление оригинал-макета: Гузев Вадим Борисович

Подписано в печать: 18.11.2009

Заказ № 3090 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР СУЩЕСТВУЮЩИХ ПАРАЛЛЕЛЬНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ.

1.1. cilk.

1.2. Т++.

1.3. АФС.

1.4. Polyphonic С#.

1.5.Х Ю.

1.6. МС#.

Актуальность работы.

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

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

Исследования в данной области непрерывно ведутся, начиная с 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 (язык Х10 [15], расширяющий язык Java), Intel (Cluster OpenMP [16], расширяющий языки С++ и Fortran), Sun

Microsystems (язык Fortress [17], расширяющий язык Fortran) и др. Все предложенные расширения являются оптимизированными под конкретные базовые языки.

Среди отечественных разработок на сегодняшний день, к сожалению, можно выделить лишь три языка, разработанных в Институте программных систем РАН: Т++ [2, 18, 19] (расширение языка С++, созданное в рамках суперкомпьютерной программы СКИФ [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 таблиц.

Основные результаты работы:

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

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

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

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

Заключение

1. Berger М. Towards Abstractions For Distributed Systems. // Электронный ресурс. 2004. - Режим доступа:http://www.informatics.sussex.ac.uk/users/mfb21/publications/phd/thesis.pdf

2. OpenTS :: Описание языка Т++. // Электронный ресурс. 2006. - Режим доступа: http://www.opents.net/index.php/ru/lang-tpp.

3. The Cilk Project. // Электронный ресурс. 1994, - Режим доступа: http://supertech.csail.mit.edu/cilk/.

4. UPC Language Specification. // Электронный ресурс. 2005. - Режим доступа: https://upc-wiki.lbl.gOv/UPC/images/f/f6/Upcspecsl.2.pdf.

5. Kaleev L. V., Sanjeev К. Charm++: Parallel Programming with Message-Driven Objects. // in "Parallel Programming using С++", by Gregory V. Wilson and Paul Lu. MIT Press. 1996. - C. 175-213.

6. ZPL. // Электронный ресурс. 1997. - Режим доступа: http://www.cs.washington.edu/research/zpl/home/index.html.

7. High-Performance Erlang. // Электронный ресурс. 1998. - Режим доступа: http://www.it.uu.se/research/group/hipe/.

8. Halstead R.H., Jr., MULTILISP: a language for concurrent symbolic computation. // ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 1985. -№4. - C. 501-538.

9. Jones S.P., Gordon A., Finne S. Concurrent Haskell. // ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (PoPL). -1996.

10. Sangiorgi D., Walker D. The Pi-calculus: a Theory of Mobile Processes. // Cambridge University Press. 2001. - ISBN 0521781779.

11. 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. - C. 268-332.

12. М.Исследовательский язык программирования С00. // Электронный ресурс. 2005. - Режим доступа: http://research.microsoft.com/en-us/um/cambridge/proj ects/comega/.

13. The XI0 Programming Language. // Электронный ресурс. 2004. - Режим доступа:http://domino.research.ibm.eom/comm/researchprojects.nsf/pages/xlO.index.h tml.

14. Библиотека Cluster OpenMP для компиляторов Intel® для ОС Linux. // Электронный ресурс. 2008. - Режим доступа: http://www.intel.com/cd/software/products/emea/rus/379901 .htm.

15. Project Fortress Community. // Электронный ресурс. 2008. - Режим доступа: http://projectfortress.sun.com/Projects/Community/.

16. Суперкомпьютерная программа «СКИФ» союзного государства. // Электронный ресурс. 2002. - Режим доступа: http://skif.pereslavl.ru.

17. Абламейко С. В., Абрамов С. М., Анищенко В. В., Парамонов Н. Н., Чиж О. П. Суперкомпьютерные конфигурации СКИФ. // Минск: ОИПИ НАН Беларуси, 2005. 170 с. - ISBN 985-6744-19-9.

18. Сайт проекта МС#. // Электронный ресурс. — 2007. — Режим доступа: http://www.mcsharp.net.

19. Кораблин Ю. П. Язык асинхронных функциональных схем и его операционная семантика // Известия академии наук. Теория и системы управления. 1996. - №5. - С. 42-53.

20. Кораблин Ю. П., Налитов С. Д., Куликова Н. JI. Распределенное программирование на языке АФС. М.: Изд. МЭИ, 1995. - 40 с.

21. Хендерсон П. Функциональное программирование: Применение и реализация. // М.: Мир, 1983. 349 с.

22. Hoare C.A.R. Communicating Sequential 'Processes // Comm. of the ACM.-1978. v. 21. - №8. - C. 666-677.

23. Benton N., Cardelli L., Fournet C. Modern Concurrency Abstractions for C#. // ACM Transactions on Programming Languages and Systems. T.26. - №5. -2004. - C. 769-804.

24. Standard ECMA-334: C# Language Specification. // Электронный ресурс. -2001. http://www.ecma-international.org/publications/standards/Ecma-334.htm.

25. Монахов В. Язык программирования Java и среда NetBeans. / СПб.: БХВ-Петербург, 2008. С. 627.

26. MPI: A Message Passing Interface Standard. Version 2.2. // Электронный ресурс. 2009. - http://www.mpi-forum.Org/docs/mpi-2.2/mpi22-report.pdf.

27. Домашняя страница языка программирования Nemerle. // Электронный ресурс. 2003. — http://nemerle.org.

28. Microsoft .Net Framework. // Электронный ресурс. — 2008. -http://www.microsofl.com/NET/.

29. Сердюк Ю.П. Формальный базис для языка программирования МС#. // Электронный ресурс. 2007. - Режим доступа: http://mcsharp.net/publications/formalbasisextendedabstract.pdf.

30. Serdyuk Y. МС# 2.0: a language for concurrent distributed programming on .NET. // In proceedings of .NET Technologies 2006 conference. Plzen, Czech Republic, 2006.

31. Prasad S., Arun-Kumar S. An Introduction to Operational Semantics. // Электронный ресурс., 2003. - Режим доступа: http://www.cse.iitd.ernet.in/~sanjiva/opsem.ps.

32. Berry G., Boudol G. The;chemical abstract machine. // In POPL '90: Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York, NY, USA: ACM Press, 1990. - C. 8194.

33. Fournet С., Gonthier G. The reflexive chemical abstract machine and the join-calculus. // In Proceedings of POPL'96. ACM, Jan. 1996. - C. 372-385.

34. Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters. // Электронный ресурс. Режим доступа: http://labs.google.com/papers/mapreduce-osdi04.pdf.

35. Сайт проекта Parallel С#. // Электронный ресурс. 2008. - Режим доступа: http://www.parallelcsharp.com.

36. Проект Mono. // Электронный ресурс. 2004. - Режим доступа: http://www.mono-project.com.

37. Gough J. Compiling for the .NET Common Language Runtime (CLR). / Prentice Hall PTR- 2002. ISBN 0-13-062296-6.

38. Gough J. The GPLEX Scanner Generator. // Электронный ресурс. 2008. -Режим доступа: http://plas2003.fit.qut.edu.au/gplex/.

39. Gough J., Kelly W. The GPPG Parser Generator. // Электронный ресурс. -2005. Режим доступа: http://plas.fit.qut.edu.au/gppg/.

40. Managed Babel System. / Электронный ресурс. 2006. - Режим доступа: http://msdn;microsoft.com/en-us/library/bbl65037%28VS.80%29.aspx.

41. Martin R. The Principles, Patterns, and Practices of Agile Software Development. / Prentice Hall 2002. - ISBN 0-13-597444-5.

42. The SSH Protocol. // Электронный ресурс. 2001. - Режим доступа: http://www.snailbook.com/protocols.html.

43. Linux NFS FAQ. // Электронный ресурс. 1984. - Режим доступа: http://nfs.sourceforge.net.

44. Trono J.A. A new exercise in concurrency. // SIGCSE Bulletin, 26(3):8-10, 1994. Corrigendum: 26(4):63.

45. Ben-Ari M. How to solve the Santa Claus problem. // Concurrency: Practice & Experience, 10(6). 1998. - C. 485-496.

46. Benton N. Jingle bells: Solving the santa claus problem in polyphonic c#. // Microsoft Research, Tech. Rep., Электронный ресурс. 2003. - Режим доступа: http://research.microsoft.com/~nick/polyphony/santa.pdf.

47. Костарев А. Н. Разработка инструментального комплекса для создания и семантического анализа распределенных информационных систем. Дис. на соиск. уч. ст. к-та техн. наук. М., 2004. - 138 с.

48. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления СПб.: БХВ-Петербург, 2002. - 608с.

49. Titanium Language Reference Manual. // Электронный ресурс. 2006. -Режим доступа:http://www.cs.berkeley.edu/Research/Projects/titanium/doc/lang-ref.pdf.

50. TRINDER P. W., LOIDL H.-W., POINTON R. F. (2002). // Parallel and Distributed Haskells. // Journal of Functional Programming. 2002. - №12-C. 469-510.

51. Fournet C. The Join-Calculus: a Calculus for Distributed Mobile Programming. // PhD thesis, Ecole Polytechnique, Palaiseau, November 1998. INRIA TU-0556. Электронный ресурс. 1998. - Режим доступа: http://research.microsoft.com/~fournet.

52. Courtois P. J., Heymans F., Parnas D. L. Concurrent control with "readers" and "writers". // Communications of the ACM. -T. 14. -№10. -1971. C. 667668.

53. Hemmendinger D. A correct implementation of general semaphores. // ACM SIGOPS Operating Systems Review. T.22. - №3. -1988. - C. 42-44.

54. Hemmendinger D. Comments on "a correct and unrestrictive implementation of general semaphores". // ACM SIGOPS Operating Systems Review. T.23. -№1.-1989.- C. 7-8.

55. Chudinov A., Guzev V., Serdyuk Y. MC#: An Asynchronous Parallel Programming Language for Cluster and GRID-Architectures. // In proc. of C# and .NET Technologies' 2003. Plzen, Czech Republic. - 2003. - C. 21-24. -ISBN 80-903100-3-6.

56. Абрамов C.M. Суперкомпьютеры семейства "СКИФ": вчера, сегодня, завтра. // Информационные и математические технологии в науке и управлении. Труды XII Байкальской Всероссийской конференции. -Иркутск, 2007. Часть II. - С. 6-12.

57. Антонов А.С. Параллельное программирование с использованием технологии MPI. / М.: Изд-во МГУ, 2004. 71 с. - ISBN 5-211-04907-1.

58. Антонов А.С. Параллельное программирование с использованием технологии ОрепМР: Учебное пособие. / М.: Изд-во МГУ, 2009. 77 с. -ISBN 978-5-211-05702-9.

59. Воеводин В.В. Вычислительная математика и структура алгоритмов. / М.: Изд-во МГУ, 2006. 112 с. - ISBN 5-211-05310-9.

60. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием С++. / Вильяме, 2004. 672 с. - ISBN 5-8459-0686-5, 013-101376-9.

61. Эндрюс Г. Основы многопоточного, параллельного и распределенного программирования. / Вильяме, 2003. 512 с. - ISBN 5-8459-0388-2, 02013-5752-6.

62. Ахо А., Лам М., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструментарий, 2 издание. / Вильяме, 2008. 1184 с. - ISBN 978-58459-1349-4, 0-321-48681-1.

63. Карпов Ю. Теория и технология программирования. Основы построения трансляторов. / BHV-Санкт-Петербург, 2004. 272 с. - ISBN: 5-94157285-9.

64. Хантер Р. Основные концепции компиляторов. / Вильяме, 2002. 256 с. -ISBN: 5-8459-0360-2.

65. Петров А., Гузев В. MC# универсальный язык параллельного программирования. // Журнал "Информационные технологии". - №4. -2008. - С. 29-32.

66. Barendregt Н.Р. The Lambda Calculus: Its Syntax and Semantics. / Studies in Logic and the Foundations of Mathematics, v. 103. Amsterdam: North-Holland, 1984. - 654 c. - ISBN 0-444-87508-5.

67. Абрамов С.М., Кузнецов А.А., Роганов В.А. Кроссплатформенная версия Т-системы с открытой архитектурой. // Вычислительные методы и программирование. 2007. - Т. 8. - №1. - Раздел 2. - С. 175-180.

68. Троелсен Э. Язык программирования С# 2005 (Си Шарп) и платформа .NET 2.0. Вильяме, 2007. - 1168 с. - ISBN 978-5-8459-1124-7, 1-59059419-3.

69. Таненбаум Э., Стен М. Распределенные системы. Принципы и парадигмы. / Питер, 2003. 880 с. - ISBN 5-272-00053-6.

70. Буч Г., Максимчук Р., Энгл М., Янг Б., Коналлен Д., Хьюстон К. Объектно-ориентированный анализ и проектирование с примерами приложений, третье издание. / Вильяме, 2008. 720 с. - ISBN 978-5-84591401-9.

71. Goetz В., Peierls Т., Bloch J., Bowbeer J., Holmes D., Lea D. Java Concurrency in Practice. / Addison Wesley Professional, 2006. 384 c. - ISBN 0-321-34960-1.

72. Шредер К. Linux. Сборник рецептов. / Питер, 2006. 432 с. - ISBN 5-46901188-7.

73. Роббинс Д. Отладка приложений Microsoft .NET и Microsoft Windows. / Русская Редакция, 2004. 736 с. - ISBN 5-7502-0243-0, 0-7356-1536-5.

74. Маклин С., Нафтел Д., Уильяме К. Microsoft .NET Remoting. / Русская Редакция, 2003. 384 с. - ISBN 5-7502-0229-1.

75. Робинсон С., Корнес О., Глинн Д. и др. С# для профессионалов. / ЛОРИ, 2005. 1480 с. - ISBN 5-85582-187-0.

76. Керниган Б., Ритчи Д. Язык программирования Си. / Санкт-Петербург: Невский диалект, 2001. 352 с. - ISBN 5794000457.

77. Страуструп Б. Язык программирования С++. Специальное издание. / Бином, 2007. 1099 с. - ISBN 978-5-7989-0226-2.

78. Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. / Вильяме, 2002. 528 с. - ISBN 5-8459-0261-4, 0201-44124-1.

79. Немеет Э., Снайдер Г., Хейн Т. Руководство администратора Linux. / Вильяме, 2007. 1072 с. - ISBN 978-5-8459-1093-6.

80. Hoare C.A.R. Monitors: An operating system structuring concept. // Communications of the ACM T.17. - №10. - 1974. - C. 549-557. - ISSN: 0001-0782.

81. Hoare C.A.R. Communicating Sequential Processes. / Prentice-Hall. 1985. -256 c. - ISBN: 0-131-53271-5.

82. Gosling J., Joy В., Steele G. Threads and locks. // In "The Java Language Specification". Prentice Hall PTR, 2000. - Глава 17. - С. 429-448. - ISBN 0-201-31008-2.

83. Parallel.ru: Технологии параллельного программирования. // Электронный ресурс. 2009. - Режим доступа: http://parallel.ru/tech/.

84. Норма. Система построения параллельных программ. // Электронный ресурс. 2007. - Режим доступа: http://www.keldysh.ru/pages/norma/.

85. Аветисян А., Бабкова В., Монаков А. Обеспечение высокопродуктивного программирования для современных параллельных платформ. // Электронный ресурс. 2009. - Режим доступа: http://wmv.citforum.ru/programming/ digest/highproductive/.

86. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. / БХВ-Петербург, 2002. -400 с. ISBN 5-94157-188-7.

87. Корнеев В. Параллельное программирование в MPI. / Институт компьютерных исследований, 2003. 304 с. - ISBN 5-93972-239-3.

88. PVM: Parallel Virtual Machine. // Электронный ресурс. 2007. -Режим доступа: http://www.csm.oml.gov/pvm/.

89. Axum Programmer's Guide. // Электронный ресурс. 2008. -Режим доступа: http://download.microsoft.eom/download/B/D/5/BD51FFB2-C777-43B0-AC24-BDE3C88E231F/Axum%20Programmers%20Guide.pdf.

90. Concurrency and Coordination Runtime. // Электронный ресурс. -2009. Режим доступа: http://msdn.microsoft.com/en-us/library/bb905470.aspx.

91. Гергель В. Теория и практика параллельных вычислений. / Бином. Лаборатория знаний, 2007. 424 с. - ISBN 978-5-94774-645-7, 978-5-95560096-3.

92. Джоунз Г. Програмирование на языке Оккам / Пер. с англ. Л. В. Шабанова, под ред. Ю. Г. Дадаева. М: Мир, 1989. - 208с.: ил. ISBN 5-03001155-2.

93. Богачев К. Основы параллельного программирования. / Бином. Лаборатория знаний, 2003. 344 с. - ISBN 5-94774-037-0.