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

московский государственный университет

им М В Ломоносова Механико-математический факультет

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

Водомеров Александр Николаевич

Методы и средства автоматизированного распараллеливания приложений в / распределенной среде

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

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

Москва - 2007

003060963

Работа выполнена на механико-математическом факультете и в Институте механики Московского государственного университета им М В Ломоносова

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

профессор

Васенин Валерий Александрович

Официальные опоненты доктор физико-математических наук,

профессор,

Серебряков Владимир Алексеевич

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

Гайсарян Сергей Суренович

Ведущая организация. Институт вычислительной математики

и математической геофизики СО РАН

Защита диссертации состоится « 29 » июня 2007 г в 14 часов на заседании диссертационного совета Д 002 087 01 в Институте системного программирования Российской академии наук по адресу 109004, Москва, ул Большая Коммунистическая, д 25

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

Автореферат разослан « мая 2007 г

Ученый секретарь диссертационного совета канд физ -мат наук

С П Прохоров

Общая характеристика работы Актуальность темы

Многие практически важные задачи требуют значительных вычислительных ресурсов, поэтому для их решения используются параллельные программы, работающие на большом числе процессоров В настоящее время наиболее известным и широко применяемым средством для создания таких программ является стандарт MPI (Message Passing Interface) Однако он обладает рядом недостатков MPI предоставляет лишь низкоуровневые операции — посылку и отправку сообщений При его использовании распределение вычислительной нагрузки и данных между узлами, обеспечение необходимых пересылок осуществляется в прикладной программе Данное обстоятельство приводит к тому, что разработка параллельных программ становится сложной задачей Между тем, многие механизмы, связанные с распределением нагрузки и данных между вычислительными узлами, являются достаточно общими, и реализация их заново в каждом параллельном приложении приводит к дублированию кода

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

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

лительных систем, в их числе

• гетерогенность (различное аппаратное и программное обеспечение),

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

• неоднородность каналов связи (пропускные способности различных каналов могут отличаться в 100-1000 раз),

• объективно более частые отказы вычислительных узлов и каналов связи

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

К настоящему времени сложился и апробирован целый ряд подходов к автоматизированному распараллеливанию программ В большинстве работ по этой тематике рассматриваются программы на функциональных языках Например, в MultiLisp используется язык Lisp, в GUM — язык Haskell В то же время большинство вычислительных приложений разрабатывается на традиционных императивных языках С, С++, Fortran Подобные языки существенно отличаются от функциональных, поэтому к ним неприменимы методы распараллеливания, разработанные в вышеупомянутых средствах Существующие на настоящее время средства распараллеливания прикладных программ на языках С, С++, Fortran обладают важными недостатками Например, Cilk рассчитан только на работу в SMP-машинах Программная система OpenTS позволяет работать на нескольких узлах, однако в меньшей степени приспособлена для использования в гетерогенной среде По причинам, изложенным выше, создание средства, позволяющего автоматизировать распараллеливание

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

Цели и задачи работы

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

1 разработка математической модели, описывающей распараллеливание и исследование его корректности в рамках этой модели,

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

3 реализация разработанных методов в виде программного комплекса,

4 исследование методов эффективной работы вычислительных приложений в условиях распределенной среды

Методы исследования

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

Научная новизна работы

Научной новизной обладают следующие результаты диссертационной работы

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

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

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

Практическая значимость

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

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

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

• приложение rt, используемое для построения высококачественных изображений методом трассировки лучей,

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

Апробация работы и публикации

Основные положения работы докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломовосов-2006», на международной конференции Finnish Data Processing Week'05 (г Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года), на международной конференции «Актуальные проблемы вычислительной математики», посвященной памяти H С Бахвалова (Москва, ИВМ РАН, 28-29 августа 2006 года), а также на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д ф -м н , проф В А Васе-нина и д т н , проф В В Корнеева (четыре доклада в течении 2005-2007 г г)

По материалам диссертации опубликовано восемь работ Структура работы

Работа состоит из введения, четырех глав, заключения, списка литературы и двух приложений Общий объем диссертации — 156 страниц (вместе с приложениями — 179 страницы) Список литературы включает 84 на/именования

Краткое содержание работы

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

Первая глава является вводной, в ней излагаются основные идеи и понятия автоматизированного распараллеливания программ

В данной главе содержится краткий обзор нескольких широко известных средств разработки параллельных программ, в том числе MPI, mpC,

DVM Анализируются их преимущества и недостатки Вводятся понятия статического и динамического распараллеливания

В качестве основного объекта исследований рассматривается Т-система — подход к автоматизированному распараллеливанию программ, разрабатываемый в ИПС РАН и МГУ им М В Ломоносова Основная идея Т-системы состоит в сочетании императивных и функциональных механизмов Императивные механизмы позволяют добиться высокой эффективности, недостижимой при использовании чисто функциональных языков В свою очередь, представление программы в функциональном виде позволяет проводить различные преобразования над программой, в том числе распараллеливать ее

Основные идеи Т-подхода состоят в следующем

• Параллельные программы разрабатываются на традиционных, широко распространенных языках, таких как FORTRAN, С, С++

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

• Для распараллеливания в программу добавляется небольшое число модификаторов, которые прозрачны для обычного компилятора

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

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

Основное отличие Т-системы от традиционных средств состоит в различных классах задач, на которые они ориентированы, и, как следствие,

в используемых методах и механизмах

Т-система предназначена для разработки приложений, обладающих следующими свойствами

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

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

• Сложность вычислений тех или иных частей программы заранее неизвестна и не может быть адекватно предсказана

• В алгоритме используются такие типы данных, как деревья, списки, хэш-массивы, строки

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

При использовании Т-системы программы разрабатываются на языке ТС Он представляет собой язык С, расширенный несколькими новыми ключевыми словами (модификаторами) Наиболее важными из них являются tfгш и -Ьуа1 Модификатор tfun указывается перед функцией и означает, что объявляемая функция является Т-функцией

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

Результатом вызова Т-функции является специальное значение, которое называется «неготовым» После того, как функция закончит вычисление, значение будет содержать некоторый результат — число, строку

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

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

• Разработанные с помощью Т-системы программы работают неустойчиво При проведении вычислений на некоторых прикладных программах наблюдались случаи «зависания» и аварийного завершения Подробный анализ нескольких таких случаев показал, что они вызваны особенностями самих алгоритмов распараллеливания

• Отсутствует четкая семантика ключевых слов языка ТС, что существенно затрудняет разработку прикладных программ пользователями

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

• Используемые в ОрепТЗ алгоритмы планирования и механизмы передачи данных работают эффективно лишь на небольшом числе узлов (не более 20-30)

Среди причин, приводящих к таким недостаткам, можно выделить две наиболее важные

• Отсутствует формальная модель процесса распараллеливания, проводимого Т-системой

• Программная реализация имеет монолитную архитектуру, без разделения на уровни или модули, что значительно затрудняет модификацию кода

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

Во второй главе излагается математическая модель используемого способа распараллеливания программ Основная цель создания математической модели — обеспечение корректности распараллеливания

Соблюдение корректности чрезвычайно важно при разработки любых средств автоматизированного преобразования программ В противном случае их применение становится нецелесообразным В отличие от последовательных программ, работа параллельных программ недетерми-нированна из-за случайных задержек сообщений в коммуникационной сети Ошибки, возникающие в подобных ситуациях (race conditions), проявляются с малой вероятностью, поэтому обнаружить их традиционными способами тестирования программного обеспечения достаточно трудно По этой причине становится актуальной разработка математической модели Т-системы и исследование корректности используемых механизмов распараллеливания

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

Определение 2. Абстрактной машиной для множества программ П называется четверка (S,T,so,a), где S — некоторое непустое множество состояний, Т СП х S х S — множество допустимых переходов, so Е S — некоторый выделенный элемент S, обозначающий начальное состояние, а — частичная функция из S в Ans, возвращающая результат выполнения

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

• формально задается язык и его параллельное расширение,

• выполнение последовательной программы задается с помощью некоторой абстрактной машины M.seq,

• выполнение параллельной программы задается с помощью некоторой параллельной абстрактной машины Мраг,

• доказывается корректность метода распараллеливания на выбранном множестве программ

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

В разделе 2 4 2 описывается машина Л4раг, моделирующая распараллеливание в наиболее простом случае, а именно — на многопроцессорной машине с общей памятью Машина Л4раг получается из машины Л4зед в результате нескольких изменений Наиболее важное из них состоит в том, что переменные могут содержать либо обычные готовые значения из, либо неготовые значения Неготовые значения представляются в виде натуральных чисел, содержащих номера специальных объектов, называемых заменителями (placeholder) Каждый заменитель может либо содержать вычисленное значение, доступное для чтения всем функциям, либо не содержать никакого значения (для значений в процессе вычисления) В отличие от машины Л4еед, в машине М.рат вычисление выражений может вызывать ожидание Кроме того, в машине Л4раг по-другому

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

Машины MSeg и Л4раг позволяют строго сформулировать метод распараллеливания, применяемый в Т-системе, а также дать формальную семантику интуитивным понятиям «Т-функциям» и «Т-переменная» Распараллеливание, проводимое Т-системой, состоит в том, что программа для машины MSeg дополняется вызовами функции -watt и выполняется на машине Л4.раг

В разделе 2 5 доказывается ряд утверждений о свойствах машины Л4раГ> в том числе корректность распараллеливания

Определение 3. Программа Р называется корректной для машины Л4ее( если ее выполнение завершается за конечное число переходов в состоянии, в котором нет функций

Теорема 1. Пусть Р — корректная программа, выполнение которой завершается за п переходов на машине A4seg Тогда существует порядок выполнения ее на машине М.рт, который содержит ровно п переходов, причем состояния машин на каждом шаге соответствуют друг другу

Ключевым утверждением в доказательстве корректности распараллеливания является лемма о выполнении в машине Л4раг ромбического свойства (diamond property)

Лемма 1 (Ромбическое свойство). Пусть из некоторого состояния st\ возможны два перехода в различные состояния st2 и st$ Тогда существуют изоморфные состояния sti и st'A, такие, что возможен переход из 5¿2 б sti, а также из sts в st\ (переходы в различных Т-функциях коммутируют с точностью до изоморфизма)

Теорема 2. Рассмотрим некоторое допустимое состояние st Пусть существует порядок выполнения программы Р, который начинается в

вЬ и приводит в некоторое конечное состояние вЬ¡т за п переходов Тогда любой порядок выполнения программы, Р, начинающийся в вЬ, содержит не более п переходов и может быть продолжен до состояния = зЬ^п так, что его суммарная длина будет равна п

Теорема 3. Пусть Р — корректная программа для машины Л4эед, выполняющаяся за п переходов Тогда любой порядок ее выполнения на машине Мраг завершается за п переходов и приводит к одинаковому результату

Следствие 1. Метод распараллеливания, применяемый в Т-системе, корректен на множестве Щ^у

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

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

В разделе 2 8 излагается обобщение предложенной модели на случай нескольких узлов, взаимодействующих между собой путем посылки сообщений по сети Для этой цели вводится машина Мйг^г Переходы в ней делятся на два типа — существенные и служебные Существенные представляют собой выполнение команд в Т-функциях, а служебные — пересылку и обработку сообщений Для доказательства корректности распараллеливания в машине М^зк используется подход на основе уточнения В разделе 2 10 излагаются различные способы анализа эффективности сформулированного метода распараллеливания Поскольку матема-

тическая модель, учитывающая время выполнения команд и сетевые задержки оказывается чересчур сложной, то для исследования производительности программ используется метод имитационного моделирования с применением компьютера (computer simulation) Для этой цели автором было разработано инструментальное средство, получившее название симулятор Симулятор реализован на чистом функциональном языке Haskell Наличие строго описанной семантики языка Haskell делает возможным реализацию семантики языка в точном соответствии с математической моделью Симулятор позволяет оценивать эффективность распараллеливания программ с помощью Т-системы на различных вычислительных установках

В заключительной части главы описываются основные отличия предложенной модели от семантики Т-переменных и Т-функций, реализованной в OpenTS (формальная модель OpenTS отсутствует), а также проводится сравнение с математическими моделями других средств распараллеливания

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

• производительность,

• модифицируемость,

• корректность распараллеливания,

• способность работать в условиях неоднородной распределенной вычислительной среды

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

методами) Одним из наиболее важных элементов архитектуры Ш-ууТБ является ее разбиение ее на модули Для этой цели используется один из наиболее известных подходов к данному вопросу — принцип сокрытия информации, предложенный Д Парнасом Большое внимание уделяется выделению интерфейсов модулей Они разрабатываются так, чтобы минимизировать возможную информацию одного модуля о внутренних структурах данных и алгоритмах другого модуля В разделе 3 5 описываются назначение и интерфейсы модулей ядра Мете-ТЭ

|№пуТ8|

Рис 1 Декомпозиция модулей ^-й^ТБ

В разделе 3 6 описываются основные программные механизмы, используемые в Ме^ГЭ активные сообщения, сериализация, асинхронная обработка сообщений, оптимизация локальных операций, координация

вычислений в слабо связанных комплексах

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

Важным элементом разработки NewTS является симулягпор Его использование дает ряд преимуществ по сравнению со способами разработки Т-системы, практиковавшимися до появления NewTS Перечислим основные из них

• Наличие промежуточного звена (симулятора) позволяет добиться значительно большей степени соответствия между формальной математической моделью и программной реализацией на С++

• Облегчается апробация новых механизмов работы Например, стандартный планировщик NewTS занимает 260 строк, Т01да как его аналог в симуляторе — всего 60

• С помощью симулятора становится возможным исследовать распределенные алгоритмы в условиях, трудно достижимых на практике, например, при сетевой задержке 10 не и пропускной способности в 100 Гбайт/с

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

Представленная модель разработки позволила Е А Степанову (одному из разработчиков новой версии Т-системы) за относительно небольшое время разработать два новых планировщика для NewTS balancing (балансирующий) и fishmg («рыбацкий») Заметим, что после интенсивного

тестирования на симуляторе реализации этих алгоритмов в коде ядра NewTS сразу показали высокую эффективность на многих прикладных задачах

Реализация описанной архитектуры позволила разработать новую версию Т-системы, удовлетворяющую поставленным требованиям Версия NewTS превосходит предыдущие по скорости и надежности Реализованы новые возможности, недоступные ранее в рамках архитектуры OpenTS, в том числе одновременная работа на узлах с различной программно-аппаратной архитектурой, подключение и отключение узлов Представленная архитектура обладает большой гибкостью За относительное небольшое время в NewTS были опробованы различные стратегии планирования, методы подсчета ссылок, механизмы передачи данных Во всех этих случаях удалось ограничиться изменением относительно небольшого объема кода Модульная структура дала основу для коллективной разработки NewTS (в настоящий момент в разработке NewTS в различной степени участвуют 6 человек)

В четвертой главе описываются результаты практических испытаний NewTS Приложения, на которых проводились измерения, разделены на три группы микротесты (microbenchmark), модельные программы и прикладные задачи

В качестве микротестов используются два небольших теста fib и tvarbench Первая измеряет скорость выполнения типичных операций создание Т-функции, планирование, переключение контекста между Т-функциями Тест tvarbench измеряет время, необходимое на создание Т-переменной, запись в нее значения и удаление Т-переменной Результаты измерений (см табл 1) показывают, что на тесте fib NewTS работает в 20,6 раз быстрее, чем OpenTS, а на тесте tvarbench — более, чем в 1000 раз Вместе с тем, необходимо учитывать, что производительность прикладных программ определяется множеством факторов, и не зависит прямо пропорционально от скорости работы ядра на данных тестах

Модельные программы представляют собой небольшие приложения,

Таблица 1 Результаты измерений производительности теста fib

Характеристика Значение параметра п

30 3 Г 32 33 34 35

Чисто Т-функций, млн 2,69 4,36 7,05 11,41 18,45 29,86

Время счета Ке^уТБ, с 2,17 3,51 5,66 9,18 14,82 23,99

Время счета ОрепТБ, с 44,60 72,68 117,08 190,26 307,08 492,05

Ускорение (Ке-даТБ к ОрепТЭ) 20,6 20,7 20,7 20,7 20,7 20,5

Время на одну функцию, мкс 0,81 0,81 0,81 0,81 0 80 0,80

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

Таблица 2 Результаты измерений производительности теста prgdemo

КПД, % Число вычислительных узлов

1 2 3 4 5 6 7 8

NewTS 99,9 99,5 97,8 98,7 98,5 96,8 94,1 94,1

OpenTS 99,8 76 3 70,1 57,4 50,7 46,9 42,6 39,8

NewTS обладает большей масштабируемостью, чем предыдущая реализации Т-системы — OpenTS (см табл 2)

В разделе 4 3 описываются результаты испытаний NewTS на использующихся на практике приложениях В качестве их выступают программный комплекс Vortex и программа RT

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

таблице 3

Таблица 3 Результаты измерений работы программы Vortex

Время, с Число процессоров

1 2 3 4 5 6 7 8 9 10 И 12

Набл 295,4 168,5 119,7 96,4 83,2 75,4 67,6 62,8 58,5 54,5 55,1 51,2

■^Ш! С 295,4 161,1 116,4 94,0 80,6 71,7 65,3 60,5 56,7 53,8 51,3 49,3

Граф зависимостей по данным программы Vortex обладает структурой, которая не позволяет распараллелить его полностью В алгоритме можно условно выделить две части, первая из которых выполняется на одном процессоре, а вторая — параллельно Непосредственные измерения показали, что при выбранных параметрах запуска ^"посл — 26,9 с и Гпар = 268,5 с В этой связи, минимальное возможное время работы может быть оценено как Ттт = Тиосл +Tnap/n Анализ результатов измерений показывает, что время работы Vortex с NewTS достаточно близко теоретически возможному (см габл 3)

Программа RT создает реалистичные изображения методом трассировки лучей Измерения проводились как на однородном, так и на неоднородном вычислительном комплексе В качестве однородного комплекса использовался вычислительный кластере МВС-15000М, расположенный в МСЦ РАН Результаты приведены в табл 4

Таблица 4 Результаты измерений эффективности программы RT

Число процессоров 2 4 8 12 16 24 32 48 64 80

КПД, % 99,9 99,6 98,4 98,3 96,6 93,9 90,1 86,0 79,0 70,0

При испытаниях на неоднородном вычислительном комплексе использовались четыре персональных компьютера, различающиеся архитектурой процессора, производительностью, объемом памяти и программным обеспечением Результаты измерений приведены в табл 5, через пг обозначен г-тый узел, идеальное время рассчитано по формуле Х^ = Т'1)"1

Таблица 5 Измерения эффективности работы на неоднородном поле

Конфигурация Наблюдаемое время, с Идеальное время, с КПД,%

Щ + щ 68,18 68,15 99,9

Щ + п2 4- п3 52,70 51,21 97,1

Щ + П2 + П3 + щ 45,88 44,48 96,9

т + п3 + щ 58,83 56,71 96,3

Щ + ГЦ 134,36 127,95 95 2

Щ + 714 82,25 78,26 95,1

щ + и2 + щ 80,76 78,92 97,7

Результаты проведенных измерений позволяют сделать следующие выводы

• Несмотря на введение модульной архитектуры и реализации дополнительных механизмов абстракции для увеличения гибкости, скорость работы базовых механизмов в NewTS существенно выше, чем в предыдущей версии Т-системы

• NewTS имеет значительно большую масштабируемость по числу узлов, чем OpenTS

• На исследуемых задачах NewTS достигает высокой эффективности как на однородном вычислительном поле, так и на неоднородном

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

В приложении А приведены ключевые фрагменты модели NewTS на языке Haskell

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

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

В рамках диссертационной работы получены следующие результаты

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

2 Построено описание математической модели на чистом (pure) языке Haskell Оно может быть использовано как спецификация для программных реализаций модели На основе данного описания разработан симулятор — инструментальное средство, позволяющее моделировать выполнение параллельных программ и исследовать эффективность распараллеливания программ на различных вычислительных установках

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

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

Публикации по теме диссертации

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

1 Васенин В А , Водомеров А Н , Инюхин А В Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные технологии — 2007 — №5, приложение — 32 с

2 Водомеров А Н Распределенная общая память в системах с массовым параллелизмом // Технологии высокопроизводительных информационно-вычислительных систем / Под ред В А Васенина Переславль-Залесский Изд-во Ун-та г Переславля, 2003 132 с

3 Водомеров А Н Организация эффективного доступа к данным в параллельных вычислительных программах // Ломоносовские чтения Тез доют науч конф 18—28 апреля 2005, Москва, МГУ им М В Ломоносова - М Изд-во МГУ, 2005 - С 61-62

4 Водомеров А Н О корректности некоторых методов автоматического распараллеливания программ / / Ломоносовские чтения Тез докл науч конф 17—27 апреля 2006, Москва, МГУ им М В Ломоносова - М Изд-во МГУ, 2006 - С 45-46

5 Водомеров А Н Построение формальной модели Т-системы и исследование ее корректности // Вычислительные методы и программирование - 2006 — Т 7, № 2 — С 192-199

6 Водомеров А Н , Конев И М О некоторых способах создания эффективных распределенных вычислительных приложений // Тр II международной конференции по проблемам управления МКПУ-2006, 20-22 июня 2006, ИПУ РАН, Москва - М ИПУ РАН -С 137

7 Водомеров А Н , Конев И М , Степанов Е А Некоторые методы организации высокопроизводительных вычислений в распределенной среде // Тр IX Междунар конф Проблемы функционирования информационных сетей ПФИС- 2006 (31 июля — 3 августа 2006, ИВМиМГ СО РАН, Новосибирск) / Под ред В К Попкова, А С Родионова - Новосиб РИЦ Прайс-курьер, 2006 - С 78-82

8 Abramov S , Adamovich А , Inyukhm A, Moskovsky А , Roganov V , Shevchuk Е , Shevchuk Yu , Vodomerov A OpenTS An Outline of Dynamic Parallelization Approach // Parallel Computing Technologies 8th International Conference, Krasnoyarsk, Russia, September 5—9, 2005 / Ed by V Malyshkm - Sprmger-Verlag, 2005 - Vol 3606 of Lecture Notes m Computer Science — Pp 303—312

Подписано в печать 28 05 2007 г Исполнено 28 05 2007 г Печать трафаретная

Заказ № 547 Тираж 100 экз

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш , 36 (495) 975-78-56 www autoreferat ru

Введение

Актуальность темы.

Цели и задачи работы.

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

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

Научная новизна работы.

Практическая значимость

Доклады и печатные публикации.

Структура работы.

1 Автоматизированное распараллеливание программ

1.1 Введение.

1.2 MPI.

1.3 трС.

1.4 DVM-система.

1.5 Т-система.

1.5.1 Основные идеи Т-системы.

1.5.2 Классы программ, на которые ориентирована Т-система.

1.5.3 Базовые механизмы Т-системы

1.5.4 Другие подходы к автоматизированному распараллеливанию

1.6 Краткий обзор истории Т-подхода.

1.6.1 Ранние версии Т-системы.

1.6.2 OpenTS.

1.7 Трудности Т-подхода.

2 Математическая модель распараллеливания программ

2.1 Корректность распараллеливания программ.

2.1.1 Корректность Т-системы.

2.2 Методы формального описания языков.

2.2.1 Основные подходы к описанию семантики языков

2.2.2 Семантика языка ТС.

2.2.3 Операционная семантика.

2.3 Формализация понятия корректности.

2.3.1 Описание Т-системы.

2.4 Базовая модель Т-системы.

2.4.1 Абстрактная машина Mseq.

2.4.2 Абстрактная машина Мраг.

2.4.3 Описание распараллеливания.

2.5 Корректность преобразований в базовой модели.

2.6 Расширение базовой модели.

2.6.1 Условие завершения работы.

2.6.2 Несоответствия между базовой моделью и языком С.

2.6.3 Расширение множества операторов.

2.6.4 Указатели и глобальные переменные.

2.7 Детализация модели.

2.8 Работа на нескольких узлах.

2.9 Реализация модели

2.10 Исследование эффективности.

2.10.1 Аналитические оценки эффективности.

2.10.2 Имитационное моделирование.

2.10.3 Прогнозирование исполнения программ

2.11 Отличия от OpenTS.

2.11.1 Обеспечение корректности в OpenTS.

2.11.2 Совместимость с С

2.11.3 Т-указатели.

2.11.4 Передача аргументов через tout.

2.12 Похожие работы.

2.13 Выводы.

3 Программная архитектура NewTS

3.1 Понятие программной архитектуры.

3.2 Архитектура OpenTS.

3.3 Требования к архитектуре Т-системы.

3.4 Методы разработки архитектуры NewTS.

3.5 Выделение модулей в NewTS.

3.5.1 Принцип сокрытия информации.

3.5.2 Выделение интерфейсов модулей.

3.5.3 Структура модулей.

3.5.4 Структура использования

3.5.5 Автоматический контроль зависимостей.

3.6 Механизмы NewTS

3.6.1 Активные сообщения.

3.6.2 Сериализация как элемент архитектуры.

3.6.3 Асинхронная обработка сообщений.

3.6.4 Оптимизация локальных операций.

3.6.5 Координация вычислений в слабосвязанных комплексах.

3.7 Использование формальной модели.

3.8 Выводы.

4 Практические испытания

4.1 Микротесты

4.1.1 Тест fib.

4.1.2 Тест tvarbench.

4.1.3 Недостатки микротестов.

4.2 Модельные программы.

4.2.1 Тест prgdemo.

4.3 Прикладные задачи.

4.3.1 Программный комплекс Vortex

4.3.2 Программа RT.

4.4 Выводы.

Актуальность темы

Многие практически важные задачи требуют значительных вычислительных ресурсов, поэтому для их решения используются параллельные программы, работающие на большом числе процессоров. В настоящее время наиболее известным и широко применяемым средством для создания таких программ является стандарт MPI (Message Passing Interface) [66]. Однако он обладает рядом недостатков. MPI предоставляет лишь низкоуровневые операции — посылку и отправку сообщений. При его использовании распределение вычислительной нагрузки и данных между узлами, обеспечение необходимых пересылок осуществляется в прикладной программе. Данное обстоятельство приводит к тому, что разработка параллельных программ становится сложной задачей. Между тем, многие механизмы, связанные с распределением нагрузки и данных между вычислительными узлами, являются достаточно общими, и реализация их заново в каждом параллельном приложении приводит к дублированию кода.

Для преодоления описанных трудностей были созданы различные средства, упрощающие разработку параллельных программ. Среди них можно выделить средства автоматизированного распараллеливания приложений [33, 2, 19, 9, 70]. При их использовании программа разрабатывается как последовательная, а затем во время компиляции или в процессе работы, происходит ее преобразование в параллельную. Основным преимуществом подобных средств является тот факт, что они сокращают объем затрат, необходимых для разработки параллельных программ.

Отметим еще одну причину, по которой исследование методов и средств автоматизированного распараллеливания программ представляет интерес. В последнее время получили повсеместное распространение неоднородные по аппаратно-программной платформе и территориально распределенные вычислительные установки, построенные по архитектуре GRID [48]. Они имеют ряд особенностей, отличающих их от традиционных вычислительных систем, в их числе:

• гетерогенность (различное аппаратное и программное обеспечение);

• различная производительность вычислительных узлов, входящих в состав комплекса;

• неоднородность каналов связи (пропускные способности различных каналов могут отличаться в 100-1000 раз);

• объективно более частые отказы вычислительных узлов и каналов связи.

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

К настоящему времени сложился и апробирован целый ряд подходов к автоматизированному распараллеливанию программ. В большинстве работ по этой тематике рассматриваются программы на функциональных языках. Например, в MultiLisp [54] используется язык Lisp, в GUM [53] — язык Haskell. В то же время большинство вычислительных приложений разрабатывается на традиционных императивных языках С, С++, Fortran. Подобные языки существенно отличаются от функциональных, поэтому к ним неприменимы методы распараллеливания, разработанные в вышеупомянутых средствах. Существующие на настоящее время средства распараллеливания прикладных программ на языках С, С++, Fortran обладают важными недостатками. Например, Cilk [49] рассчитан только на работу в SMP-машинах. Программная система OpenTS [19] позволяет работать на нескольких узлах, однако в меньшей степени приспособлена для использования в гетерогенной среде. По причинам, изложенным выше, создание средства, позволяющего автоматизировать распараллеливание прикладных вычислительных программ, а также способного эффективно работать в условиях распределенной вычислительной среды, является крайне актуальной задачей.

Цели и задачи работы

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

1. разработка математической модели, описывающей распараллеливание и исследование его корректности в рамках этой модели.

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

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

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

Методы исследования

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

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

В рамках диссертационной работы получены следующие результаты:

1. разработана математическая модель, позволяющая формально описать распараллеливание программ и доказать его корректность;

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

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

Научная новизна работы

Научной новизной обладают следующие результаты диссертационной работы.

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

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

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

Практическая значимость

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

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

• программный комплекс Vortex, предназначенный для моделирования двумерного нестационарного обтекания твердых тел потоком несжимаемой среды [17,18];

• приложение rt, используемое для построения высококачественных изображений методом трассировки лучей [2];

• приложение insertdoc, осуществляющее анализ и индексирование текстовых документов в составе системы автоматизированного обработки тематической информации в больших и сверхбольших коллекциях [5, 7];

Доклады и печатные публикации

Основные положения работы докладывались на международных научных конференциях студентов, аспирантов и молодых ученых «Ломоносов-2005», «Ломоносов-2006», «Ломоносов-2007», на международной конференции Finnish Data Processing

Week'05 (г. Петрозаводск, 17-20 мая 2005 года), на третьей международной конференции по проблемам управления МКПУ-2006 (Москва, ИПУ РАН, 20-22 июня 2006 года), на IX международной конференции «Проблемы функционирования информационных сетей» ПФИС-2006 (Новосибирск, 31 июля - 3 августа 2006 года), на международной конференции «Актуальные проблемы вычислительной математики», посвященной памяти Н. С. Бахвалова (Москва, ИВМ РАН, 28-29 августа 2006 года), на семинаре ИСП РАН (2007 г.), семинаре отдела систем математического обеспечения ВЦ РАН (2007 г.), а также на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н., проф. В.А. Васенина и д.т.н., проф. В. В. Корнеева (четыре доклада в течении 2005-2007 г. г.).

По материалам диссертации опубликовано восемь работ [8,10,11,12,13,14,15, 70].

Структура работы

Работа состоит из введения, четырех глав, заключения, списка литературы, и двух приложений. Общий объем диссертации — 156 страниц (вместе с приложениями — 179 страниц). Список литературы включает 84 наименования.

4.4 Выводы

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

• Несмотря на введение модульной архитектуры и реализации дополнительных механизмов абстракции для увеличения гибкости и расширяемости, скорость работы базовых механизмов (создание Т-переменных и операции с ними, вызов функций и планирование) в NewTS существенно выше, чем в предыдущей версии Т-системы,

• NewTS имеет значительно большую масштабируемость по числу узлов, чем OpenTS.

• На исследуемых задачах NewTS достигает высокой эффективности как на однородном вычислительном поле, так и на неоднородном.

Заключение

В диссертационной работе получены следующие результаты.

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

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

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

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

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

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

1. Адельсон-Велъский Г. М., Арлазаров В. Л., Донской М. В. Программирование игр. — М.: Наука. Глав. ред. физ.-мат. лит., 1978.— 256 с.

2. Александреску А. Современное проектирование на С++, испр. изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2004,— 336 с.

3. Афонин С. А., Козицын А. С. Поиск текстовых документов с учетом их логической структуры // Тр. XII Междунар. конф. по вычислительной механике и современным прикладным программным системам (ВМСППС). — Владимир: МАИ, 2003.-С. 74.

4. Басс Л., Клементе П., Кацман Р. Архитектура программного обеспечения на практике: Пер. с англ. — 2-е изд. — СПб.: Питер, 2006.— 576 с.

5. Васенин В. А., Афонин С. А. К разработке моделей эффективного поиска информации в сети интернет // Тр. Всерос. науч. конф. «Научный сервис в сети Интернет 2003» (22-27 сентября 2003, г. Новороссийск). М.: Изд-во МГУ, 2003. — С. 252-255.

6. Васенин В. А., Водомеров А. Н., Инюхин А. В. Средства автоматизированного динамического распараллеливания программ на основе сочетания императивных и функциональных механизмов // Информационные технологии. — 2007. — № 5. — 32 с.

7. Васенин В. А., Роганов В. A. GRACE: распределенные приложения в интернет // Открытые системы. — 2001. — № 5. — С. 29-33.

8. Водомеров А. Н. Распределенная общая память в системах с массовым параллелизмом // Технологии высокопроизводительных информационно-вычислительных систем / Под ред. В. А. Васенина. — Переславль-Залесский: Изд-во Ун-та г. Псрсславля, 2003.— С. 119-126.

9. Водомеров А. Н. Организация эффективного доступа к данным в параллельных вычислительных программах // Тез. докл. науч. конф. «Ломоносовские чтения» (18-28 апреля, МГУ им. Ломоносова, Москва). — М.: Изд-во МГУ, 2005. — С. 6162.

10. Водомеров А. Н. О корректности некоторых методов автоматического распараллеливания программ // Тез. докл. науч. конф. «Ломоносовские чтения» (18-28 апреля, МГУ им. Ломоносова, Москва). — М.: Изд-во МГУ, 2006.— С. 45-46.

11. Водомеров А. Н. Построение формальной модели Т-системы и исследование ее корректности // Вычислительные методы и программирование. — 2006. — Т. 7, № 2.-С. 192-199.

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

13. Григоренко Д. А. Вопросы программной реализации лагранжевых вихревых методов // Избр. тр. XVII Междунар. Интернет-конференции молодых ученых и студентов по проблемам машиноведения (МИКМУС-2005). — М.: Изд-во ИМАШ РАН, 2006.-С. 121-124.

14. Душкин Р. В. Функциональное программирование на языке Haskell. — М.: ДМК-пресс, 2006.- 608 с.

15. Инюхин А. В. Математическое и программное обеспечение вычислительных систем с динамическим параллелизмом: Дис. канд. ф.-м. наук: 05.13.11 / МГУ им. М.В. Ломоносова. — М., 2007.

16. Коновалов Н. А., Крюков В. А. Параллельные программы для вычислительных кластеров и сетей // Открытые системы. — 2002. — № 3. — С. 12-18.

17. Крюков В. А. Разработка параллельных программ для вычислительных кластеров и сетей // Информационнные технологии и вычислительные системы. — 2003. — № 1.-С. 42-61.

18. Моделирование нестационарных нагрузок при движении тел в вязкой жидкости: Отчет №4775 / С. В. Гувернюк, Г. Я. Дынникова, П. Р. Андронов и др.; Ин-т механики МГУ. М., 2005. - 93 с.

19. На пути к верификации С-программ. часть 1. язык C-light / В. А. Непомнящий, И. С. Ануреев, И. Н. Михайлов, А. В. Промский.- 2001.— (Препр./ РАН. Сиб. Отд-ние. ИСИ; №84).

20. На пути к верификации С-программ. часть 2. язык C-light-kernel и его аксиоматическая семантика / В. А. Непомнящий, И. С. Ануреев, И. Н. Михайлов,

21. A. В. Промский, 2001.- (Препр./ РАН. Сиб. Отд-ние. ИСИ; №87).

22. На пути к верификации С-программ. язык C-light и его формальная семантика /

23. B. А. Непомнящий, И. С. Ануреев, И. Н. Михайлов, А. В. Промский // Программирование. — 2002. № 6. — С. 65-80.

24. Промский А. В. Формальная семантика C-light программ и их верификация методом Хоара: Дис. .канд. физ.-мат. наук: 05.13.11 / ИСИ СО РАН. — Новосибирск, 2004,- 158 с.

25. Степанов Е. А., Конев И. М. Автоматизация динамического распараллеливания программ: планирование и управление памятью // Приложение к журналу « Информационные технологии». — № 11. М.: Изд-во «Новые технологии», 2007.— 32 с. — В печати.

26. Страуструп Б. Дизайн и эволюция языка С++. — 1-ое изд. — П.: Издательский дом "Питер", 2006.- С. 448.

27. Т-система с открытой архитектурой / С. М. Абрамов, А. И. Адамович, А. В. Иню-хин и др. // Тр. Междунар. науч. конф. «Суперкомпьютерные системы и их применение SSA'2004» (26-28 октября 2004, г. Минск). Минск: ОИПИ НАН Беларуси, 2004.-С. 18-22.

28. Таненбаум Э. Современные операционные системы: Пер. с англ. — 2-е изд. — СПб.: Питер, 2004. 1040 с.

29. Филд А., Харрисон II. Функциональное программирование / Под ред. В. А. Горбатова. — М., 1993.— 637 с. — перевод с английского М. В. Горбатовой, А.А. Ря-бинина, канд. техн. наук В. J1. Торхова, М. В. Федорова.

30. Эндрюс Г. Основы многопоточного, параллельного и распределенного программирования: Пер. с англ. — М. и др.: Вильяме, 2003. — 512 с.

31. Active Messages: A Mechanism for Integrated Communication and Computation / T. von Eicken, D. E. Culler, S. C. Goldstein, К. E. Schauser // 19th International Symposium on Computer Architecture. — Gold Coast, Australia: ACM Press, 1992.— Pp. 256-266.

32. Baker H. G., Hewitt C. The incremental garbage collection of processes // Proc. of Symposium on AI and Programming Languages.— Vol. 12 of ACM SIGPLAN Notices. — N.Y.: ACM Press, 1977.- Pp. 55-59.

33. Beal S. slln: the serialization framework for С++. — 2006. — Nov. — Электрон, текст, док. http://slln.net/.

34. Boost С++ libraries. — 2007. — Электрон, текст, док. http://www.boost.org/.

35. The Definition of Standard ML Revised / R. Milner, M. Tofte, R. Harper, D. MacQueen. - MIT Press, 1997.- 128 pp.

36. Design Patterns: Elements of Reusable Object-Oriented Software / E. Gamma, R. Helm, R. Johnson, J. Vlissides. — 1st edition.— Addison-Wesley Professional, 1995.- 395 pp.

37. Executable specifications: Creating testable, enforceable designs: Tech. rep.: Foundations of Software Engineering, Microsoft Research, 2001.

38. Flanagan C., Felleisen M. The semantics of future and its use in program optimization // Proc. of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, San Francisco, California. — N.Y.: ACM Press, 1995.— Pp. 209-220.

39. Frigo M., Leiserson С. E., Randall К. H. The implementation of the Cilk-5 multithreaded language // Proc. of the ACM SIGPLAN 1998 conference on Programming language design and implementation.— New York, NY, USA: ACM Press, 1998.-Pp. 212-223.

40. Goetz B. Java theory and practice: Anatomy of a flawed microbenchmark // IBM developerWorks. — 2005. http://www-128.ibm.com/developerworks/java/library/j-jtp02225.html.

41. Gordon M. J. The Denotational Description Of Programming Languages. — Springer-Verlag, 1979. 160 pp.

42. Greanier Т. M. Flatten your objects: discover the secrets of the Java Serialization API. — 2000. — July. — Электрон, текст, док. http://www.javaworld.com/javaworld/jw-07-2000/jw-0714-flatten.html.

43. GUM: a portable parallel implementation of Haskell / P. W. Trinder, K. Hammond, J. J. S. Mattson et al. // Proc. of the ACM SIGPLAN 1996 conference on Programming language design and implementation. — N.Y.: ACM Press, 1996. — Pp. 79-88.

44. Halstead R. H. Implementation of Multilisp: Lisp on Multiprocessor // Proc. of the 1984 ACM Symposium on LISP and functional programming, Austin, Texas, United States. N.Y.: ACM Press, 1984,- Pp. 9-17.

45. A history of haskell: being lazy with class // The Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III) San Diego, California, June 9-10, 2007. 2007.

46. ISO/IEC 9899, Programming languages — C.

47. Jones С. B. The Early Search for Tractable Ways of Reasoning about Programs // IEEE Annals of the History of Computing. — 2003. Vol. 25, no. 2. - Pp. 26-49.

48. Knizhnik K. Reflection Package for С++. — 2004. — Электрон, версия печ. публикации. http://www.garret.ru/~knizhnik/cppreflection/docs/reflect.html.

49. Lamport L. An axiomatic semantics of concurrent programming languages // Proc. NATO Advanced Course on Logics and Models of Concurrent Systems / Ed. by K. Apt.- Springer-Verlag, 1985.-Pp. 77-122.

50. Lastovetsky A. L. mpC: a multi-paradigm programming language for massively parallel computers Ц ACM SIGPLAN Notices. 1996. - Vol. 31, no. 2. - Pp. 13-20.

51. Liang S., Hudak P., Jones M. Monad transformers and modular interpreters // Proc. 22nd ACM SIGPLAN-SIGACT Symposium on Principles of programming languages, San Francisco, California, January 23-25.— N.Y.: ACM Press, 1995.

52. Meyers S. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library (Paperback).— Addison Wesley Professional, 2001. —June.— 288 pp.

53. Mitzenmacher M. Analyses of load stealing models based on differential equations // SPAA '98: Proc. of the tenth annual ACM symposium on Parallel algorithms and architectures. New York, NY, USA: ACM Press, 1998.- Pp. 212-221.

54. Moggi E. An Abstract View of Programming Languages: Tech. Rep. ECS-LFCS-90-113: Lab. for Found, of Сотр. Sci., University of Edinburgh, 1989.

55. Moreau L. The Semantics of Future in the Presence of First-Class Continuations and Side-effects: Tech. Rep. ECSTR M95/3: Department of Electronics and Computer Science, University of Southampton, 1995.

56. MPI Standard vl.2.— 1997. —July.— Электрон, версия печ. публикации, http: / / www.mpi-forum.org/docs/mpi-20.ps.

57. MPI Standard v2.0.— 1997. —July.— Электрон, версия печ. публикации, http: / / www.mpi-forum.org/docs/mpi-20.ps.

58. Norrish M. С formalised in HOL: Tech. Rep. UCAM-CL-TR-453: University of Cambridge, Computer Laboratory, 1998.

59. The OpenTS dynamic parallelization system approach / S. Abramov, A. Moskovsky, V. Roganov, E. Shevchuk // Proc. PARA'06 Workshop on State-of-the-Art in Scientific and Parallel Computing, Umea, Sweden, June 18-21. — 2006.

60. Papaspyrou N. S. A Formal Semantics for the С programming language: Doctoral dissertation / National Technical University of Athens. — Athens, 1998.

61. Parnas D. L. On the criteria to be used in decomposing systems into modules // Communications of the ACM.— 1972.- Vol. 15, no. 12. — Pp. 1053-1058.

62. Plotkin G. D. A Structural Approach to Operational Semantics: Tech. Rep. DAIMI FN-19: Computer Science Department, Aarhus University, Aarhus, Denmark, 1981.

63. Plotkin G. D. The Origins of Structural Operational Semantics // Journal of Logic and Algebraic Programming. — 2004. — Vol. 60. — Pp. 3-15.

64. Ponder C. G., McGeer P. C., Ng A. P. Are applicative languages inefficient? // SIGPLAN Notices. 1988. - June. - Vol. 23, no. 6. - Pp. 135-139.

65. Slonneger K., Kurtz B. L. Formal Syntax and Semantics of Programming Languages. — Addison-Wesley Longman, 1995. — 637 pp.

66. Stoy J. E. Denotational Semantics of Programming Languages: The Scott-Strachey Approach to Programming Language Theory. — MIT Press, Camb., Mass., 1977.— 414 pp.

67. Stroustrup B. The Design of C++0x // C/C++ User Journal, May 11.- 2005.

68. Sutter H. Exceptional С++.— 1st edition.— Addison-Wesley Professional, 1999. — 240 pp.

69. Sutter H., Alexandrescu A. С++ Coding Standards: 101 Rules, Guidelines, and Best Practices. — 1st edition. — Addison Wesley Professional, 2004. — 240 pp.

70. Tanenbaum A. S., Herder J. N., Bos H. Can We Make Operating Systems Reliable and Secure? // Computer. 2006. - Vol. 39, no. 5. - Pp. 44-51.

71. Turner D. A. Functional programs as executable specifications // Proc. of a discussion meeting of the Royal Society of London on Mathematical logic and programming languages. — Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1985.- Pp. 29-54.