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

УДК 004.432, 004.434:5, 004.442, 004.451.45

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

цО'+ох • -Арыков Сергей Борисович

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

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

-2 ЛЕН 2010

Новосибирск - 2010

004614924

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

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

профессор,

Малышкин Виктор Эммануилович

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

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

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

Скопин Игорь Николаевич

Ведущая организация: Нижегородский государственный уни-

верситет им. Н.И. Лобачевского

Защита состоится 17 декабря 2010 г. в 15 час. 30 мин. на заседании диссертационного совета ДМ003.032.01 в Учреждении Российской академии наук Институте систем информатики им. А.П. Ершова Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Акад. Лаврентьева, д. 6.

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

Автореферат разослан 15 ноября 2010 г.

Ученый секретарь диссертационного совета,

канд. физ.-мат. наук

'S

Мурзин Ф. А.

Общая характеристика работы

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

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

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

Значительным шагом на этом пути можно считать такие системы, как НРР, БУМ, трС. Они берут на себя заботу о реализации коммуникаций, син-хронизаций и некоторых других проблемах, однако, в силу излишне жестко

заданного управления (что характерно для всех императивных языков), автоматически выявить внутренний параллелизм алгоритма часто не удаётся.

С повсеместным распространением многоядерных процессоров задача разработки параллельной программы ещё более усложняется, поскольку эффективно распределить доступные ресурсы между крупными взаимодействующими последовательными процессами затруднительно. Это породило множество исследовательских проектов, направленных на поиск более подходящей модели вычислений. Среди российских разработок можно отметить проект МАРС (языки Барс и Поляр), систему НОРМА, систему OpenTS; среди зарубежных — библиотеку PLASMA, системы ALF, Charm++, SMP superscalar и другие.

Одним из новых подходов, альтернативных программированию на основе параллельно-последовательной модели вычислений, является фрагменти-рованное программирование. К его основным преимуществам можно отнести возможность автоматической генерации параллельной программы, возможность автоматически обеспечить программам ряд динамических свойств, лучшую переносимость между вычислителями различной архитектуры, а также возможность выполнить формальный анализ параллельной программы. Этот подход в настоящее время активно развивается, и в существующих проектах (PLASMA, ALF, Charm++) реализованы лишь его отдельные элементы. Поэтому дальнейшее развитие средств фрагментированного программирования является актуальной задачей.

Объект и предмет исследования. Объектом исследования является фраг-ментированное программирование. Предмет исследования — языки и системы фрагментированного программирования.

Цель работы. Целью диссертационной работы является разработка языка и системы фрагментированного параллельного программирования задач численного моделирования.

Для достижения поставленной цели были сформулированы следующие задачи:

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

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

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

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

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

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

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

2. Совокупность способов задания управления во фрагментированной программе, включая массовое управление.

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

- алгоритмы генерации управляющих операторов, поддерживающие массовое управление;

- методика представления асинхронной программы на языке С++.

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

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

На защиту выносятся:

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

2. Язык фрагментированного программирования Аспект.

3. Система фрагментированного программирования Аспект и алгоритмы её реализации.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались:

- на Конференции молодых ученых ИВМиМГ СО РАН (Новосибирск, 2005 и 2006 гг.);

- на VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск,

2007 г.);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)» (Санкт-Петербург, 28 января — 1 февраля

2008 г.);

- на VI Всероссийской конференции студентов, аспирантов и молодых ученых «Молодёжь и современные информационные технологии» (Томск, 26-28 февраля 2008 г.);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)» (Нижний Новгород, 30 марта — 3 апреля

2009 г.);

- на Международной научной конференции «Parallel Computer Technologies (РаСТ-2009)» (Новосибирск, 31 августа — 4 сентября 2009 г.);

- на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (Уфа, 29 марта — 2 апреля 2010 г.);

- на научных семинарах «Математическое и архитектурное обеспечение параллельных вычислений» (отдел МО ВВС Института вычислительной математики и математической геофизики СО РАН), «Архитектура,

системное и прикладное программное обеспечение кластерных суперЭВМ» (расширенный семинар ССКЦ, НГУ, Центра Компетенции СО РАН — INTEL), «Системное программирование», «Конструирование и оптимизация программ» (объединённые семинары кафедры программирования НГУ и Института систем информатики имени А.П. Ершова СО РАН).

Публикации. По теме диссертации опубликовано 11 работ, в том числе 3 статьи в рецензируемых журналах и 4 статьи в сборниках трудов международных конференций.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 125 наименований и пяти приложений. Общий объем работы составляет 195 страниц, из них 151 страница основного текста, включая 13 таблиц и 23 рисунка. Общий объем программного кода составляет 9702 строки.

Содержание работы

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

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

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

Раздел 1.2 посвящен детальному анализу средств разработки асинхронных программ. Рассматривается пять проектов: МАРС (Вычислительный центр СО АН СССР), OpenTS (Исследовательский центр мультипроцессорных систем ИПС РАН), Charm++ (Иллинойский университет в Урбана-Шампейн), Граф Плюс (Самарский государственный аэрокосмический университет) и PLASMA (совместный проект университета штата Теннесси, Калифорнийского университета в Беркли и университета штата Колорадо в Денвере). Для каждого проекта описывается модель вычислений, язык программирования и особенности реализации, анализируются достоинства и недостатки, приводится пример программы.

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

Вторая глава посвящена исследованию теоретических основ фрагменти-рованного подхода к программированию.

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

Определение 1. Фрагментированное программирование ~ это представление алгоритма решения задачи в виде множества фрагментов данных и множества фрагментов кода. Фрагмент кода получает на вход набор входных фрагментов данных, на основе которых вычисляет набор выходных фрагментов данных. Подстановка фрагментов данных в качестве параметров фрагмента кода называется применением фрагмента кода к фрагментам данных (один и тот же фрагмент кода может применяться к различным фрагментам данных). Совокупность фрагмента кода и его входных и выходных фрагментов данных называется фрагментом вычислений. На множестве фрагментов вычислений задаётся строгий частичный порядок.

Определение 2. Управление — это множество ограничений на порядок выполнения фрагментов вычислений.

Раздел 2.2 посвящен разработке подходящей модели вычислений для фрагментированного программирования численных задач. В качестве базовой выбрана асинхронной модель вычислений. Даётся формальное определение простой асинхронной модели, асинхронной модели со структурными А-блока-ми, асинхронной модели с массовыми А-блоками. В этих моделях управление скрывается внутри управляющих операторов, что делает его недоступным для анализа, который необходим для автоматического/автоматизированного распределения ресурсов. Поэтому предлагается асинхронная модель вычислений с управлением на основе строгого частичного порядка, которая представляет информацию об управлении на уровне модели.

Определение 3. Асинхронная программа с управлением на основе строгого частичного порядка представляет собой набор Р — (М, Л), где М - конечное множество переменных, М = [х\,хг,..., хт\; А - конечное множество А-блоков,

Множество М называется памятью. Память М = X и К состоит из множества X = (х, >',..., г) простых переменных и множества У = [х,у, ...,£}, разбитого на конечное число счётных, непересекающихся, линейно упорядоченных подмножеств, которые называются массивами, или структурными переменными. Элементы массива х = {хь*2>- • • называются компонентами х; компонент х, обозначается х[г]. X П У = 0. Запись нового значения в переменную стирает предыдущее значение.

Пусть N — множество натуральных чисел, С с А х N. Элемент (А к, 0 е С обозначается А'к и называется г-м экземпляром А-блока А*. Пусть NЛt = {/ € N | (Ак, 0 е С7}. А-блок А/с называется простым, если — одноэлементное множество, и массовым, если Л^ содержит более одного элемента. Множество называется областью применимости А-блока А

Экземпляр А-блока А'к описывается четвёркой (Мк,Т'к,0'к,К'к), где М'к —

подмножество памяти М, используемое экземпляром А-блока А'к, причём М'к -

Т'к/ и 0'к/ и 0[о \ Т'к — триггер-функция, представляющая собой предикат

Т'к(х\, хг,... ,х{), е ^ = 1,/; 0'к — операция, которая по значениям

входных переменных х\, хг,. ■., хт вычисляет значения выходных переменных

>"ь У2. • • • ,Уп, е 0'к[, у, е 0'к01> 5 = 1> 'и> ' = 1, п, при этом количество

входных и выходных параметров всех экземпляров одного А-блока совпадает:

= |0^|)Л(|0^| = р € II, ц е II, рфд\ И[ есть строгий частичный

порядок, заданный на подмножестве С'к экземпляров А-блоков А-программы

Л: (С'к,Я'к), который будем также обозначать {С'к, <). Як = и Н'к, Я - и^ь

/ к

Операция 0'к есть либо множество частично рекурсивных функций /ь /2,..., /л, каждая из которых вычисляет одну выходную переменную

Л = /\(Х1,Х2,...,Хт),у2 = ¡2{Х\,ХЪ...,Хт,),...,у п = /п(Х\, Х2,. ■ . , Хт), X, 6 у, € С^ , либо А-программа Р' = (М', А'), которая вычисляет все переменные из 0'кд . А-блок называется атомарным, если 0\ = {/ь/г, ■ ■ • ,/я), и структурным, если 0'к = Р'.

Определение 4. Асинхронная система есть набор правил, позволяющих произвести вычисления для заданной асинхронной программы Р:

1. При запуске А-программы на исполнение формируется множество А' готовых к исполнению экземпляров А-блоков А'к: А' = {А'к | ->В(Вц,А'к) е Я Л Т[ = ИСТИНА}.

2. Из множества готовых экземпляров А' выделяется некоторое подмножество А", экземпляры которого запускаются на исполнение. Исполнение экземпляра А-блока А'к состоит в вычислении его операции Ок, проверке значений триггер-функций всех экземпляров Врч, у которых после вычисления 0'к все предшествующие экземпляры А-блоков оказались вычисленными, и добавлении в множество А' тех Вд, у которых триггер-функции имеют значение ИСТИНА. Вычисление операции 0'к состоит либо в вычислении всех функций /ь /г,..., /„, либо в вычислении А-программы Р', которая вычисляется по тем же правилам, что и исходная А-программа Р. В последнем случае 0'к{ с М', О^ с М', а операция 0'к считается вычиленной, когда А-программа Р' завершила своё исполнение. Экземпляры исполняются независимо друг от друга, каждый экземпляр исполняется не более одного раза.

3. Исполнение А-программы завершается, когда ни один экземпляр А-блока не исполняется и множество готовых экземпляров пусто: А' = 0.

Если в асинхронной модели с управлением на основе строгого частичного порядка рассматривать каждую переменную (простую либо компонент

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

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

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

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

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

Алгоритм 2 позволяет сгенерировать управляющий оператор для экземпляра А-блока А'к асинхронной программы Р с управлением на основе строгого частичного порядка используя формальное определение управляющих операторов на основе счётчиков зависимостей по переменным.

Применяя алгоритм 1 или алгоритм 2 ко всем экземплярам А-блоков, можно преобразовать асинхронную программу с управлением на основе

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

Третья глава посвящена описанию языка программирования Аспект, позволяющего разрабатывать фрагментированные параллельные программы.

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

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

В разделе 3.2 рассматривается формальный синтаксис и семантика языка Аспект. Пример простой Аспект-программы показана на рис. 1.

Раздел préfacé позволяет задать определения внешнего языка. Раздел data fragments позволяет определить фрагменты данных, раздел code fragments — фрагменты кода, раздел task data — данные задачи (статические и динамические), раздел task computations — фрагменты вычислений, раздел task control — управление, в котором слева от символа «<» указывается предшествующий экземпляр фрагмента вычислений, а справа — зависимый экземпляр фрагмента вычислений.

Множество номеров экземпляров массового фрагмента вычислений

program MultMatrix préfacé {

const int M = 3, N = 3;

};

data fragments

double Matrix[M][M]; code fragments

Huit(in Matrix X, Matrix Y, Matrix Z; out Matrix Z) { for(int i=0; i<M; ++i) for (int k=0; k<M; ++k) for(int j=0; j<M; ++j)

ZCi][jl += X[i] [k]*Y[k] [j] ;

>;

task data

Matrix A [N] [N] , B[N][N], C[N][N]; task computations

S[i] Ij] [k] : Mult(A[i][k], B[k][j], C[i] [j] , C[i][j]) where i: 0..N-1, j: 0..N-1, k: 0..N-1; task control

S[i][j][k] < SCi][j][k+l];

end

Рис. 1. Аспект-программа умножения матриц

задаётся декартовым произведением индексов. Множество значений каждого индекса определяется в разделе task computations после ключевого слова where указанием нижнего и верхнего пределов диапазона натуральных чисел с шагом, равным единице. При определении одного индекса допускается использовать значение другого, например, j: i+l..N-l, но граф зависимостей между индексами должен быть ациклическим.

Управление может быть задано статически (с помощью раздела task control) и динамически (с помощью триггер-функций, записанных на внешнем языке). Статическое управление возможно задать как между разными фрагментами вычислений (например, А < В), так и между экземплярами одного и того же фрагмента вычислений (см. рис. 1). Поддерживается простое управление (между конкретными экземплярами), например, А[5] < В[5]; сложное управление (с использованием логических операций), например, (А | (В & С)) < D; и массовое управление (между всем экземплярами сразу),

например, А[1] < В[)]. Для обозначения всех экземпляров фрагмента вычислений используется пустой индекс [].

Для указания связи между предшествующим и зависимым экземплярами в случае массового управления допускается использовать выражения вида у = х ± Ь, где х — идентификатор, а Ь — константа. Множество значений идентификатора можно ограничить с помощью предиката.

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

В четвёртой главе описывается реализация системы фрагментированного программирования Аспект и порядок работы с системой.

Раздел 4.1 посвящён программной архитектуре. В её основе лежит разделение системы на два компонента: транслятор с языка Аспект и исполнительную подсистему. Транслятор осуществляет перевод Аспект-программы в асинхронную программу с массовыми А-блоками на языке С++, а исполнительная подсистема обеспечивает поддержку времени выполнения (управление потоками, памятью, очередями готовых А-блоков).

Процесс разработки программы в системе Аспект показан на рис. 2. На

Рис. 2. Разработка программы в системе Аспект

вход транслятору подаётся текст программы на языке Аспект, на выходе генерируется асинхронная программа на С++, которую необходимо скомпилировать вместе с исполнительной подсистемой компилятором С++.

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

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

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

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

Алгоритм 4 позволяет сгенерировать код, проверяющий экземпляр А-блока на готовность к исполнению.

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

В разделе 4.3 рассматривается реализация исполнительной подсистемы, ориентированная на архитектуру с общей памятью. Её структура представлена на рис. 3.

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

Ядро

Менеджер потоков

Менеджер памяти

Планировщик

Слой абстрагирования от ОС

Рис. 3. Архитектура исполнительной подсистемы

ресурсов, работа с потоками, функции для работы со временем и другие). Это позволяет переносить исполнительную подсистему из одной ОС в другую заменой лишь одного, выделенного слоя.

Менеджер потоков управляет распределением работы между процессорами (ядрами). Менеджер памяти управляет распределением памяти в системе, осуществляет её выделение/освобождение для очередей и А-программ. Планировщик управляет набором очередей, каждая из которых имеет определённый приоритет и реализована в виде монитора.

Идея алгоритма планирования заимствована из реализации планировщика ядра ОС Linux версии 2.6. Алгоритм имеет сложность O(l) и заключается в следующем: при каждом вызове метода get() очереди просматриваются в порядке убывания приоритетов; если в текущей очереди имеется готовый экземпляр А-блока, он запускается на исполнение. Таким образом, экземпляры А-блоков из очередей с более высоким приоритетом всегда будут запущены на исполнение раньше, чем экземпляры из очередей с более низким приоритетом. Если в очереди с некоторым приоритетом имеется несколько экземпляров, выбирается первый из них.

В разделе 4.4 рассмотрен порядок работы с системой. Описывается способ трансляции Аспект-программы и её окончательной сборки в исполняемый файл. Рассматриваются возможности системы по отладке Аспект-программ.

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

В разделе 5.1 описывается тестовая среда и методика испытаний.

В разделе 5.2 рассматривается тестирование исполнительной подсистемы на специальных тестах, разработанных для проверки её характеристик. Накладные расходы при исполнении Аспект-программы складываются из накладных расходов исполнительной подсистемы и накладных расходов на исполнение управляющих операторов. Для каждого типа расходов разработаны отдельные тесты, результаты которых подтверждают основные характеристики, заложенные в систему Аспект при проектировании: сложность планировщика 0( 1), стабильная работа при большом (миллион и более) количестве фрагментов вычислений, линейный рост накладных расходов на исполнение управляющего оператора при линейном увеличении числа зависимых фрагментов.

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

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

Первая задача состояла в оценке математических ожиданий аддитивных функционалов от траекторий диффузионных процессов и решалась методом Монте-Карло. Результаты измерений на системе с 4 процессорами Intel Xeon Х7350 (16 ядер) и 256 Гбайт RAM для 64 млн. смоделированных траекторий приведены в таблице 1. Видно, что ускорение практически линейное, что

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

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

Характеристика Количество ядер

1 2 4 8 16

Время счёта, с 23805,50 12051,00 5939,00 2990,00 1510,68

Ускорение, раз 1 1,97 4 7,96 15,75

Вторая задача состояла в моделировании взаимодействия короткого лазерного импульса с плазмой и решалась методом «частицы-в-ячейках». Результаты измерений на сервере с 2 процессорами Intel Xeon Е5520 (8 ядер, HT отключена) и 24 Гбайт RAM для 5 шагов моделирования приведены в таблице 2.

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

Характеристика Количество ядер

1 2 4 8

Время счёта, с 21,92 '11,03 6,14 3,48

Ускорение, раз 1 1,99 3,57 6,30

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

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

В приложении А приведены примеры асинхронных программ на различных языках программирования.

В приложении Б приведены допустимые лексемы и грамматика языка программирования Аспект.

В приложении В приведены тексты Аспект-программ.

В приложении Г приведены параметры командной строки для управления транслятором, а также сообщения об ошибках, выдаваемые им при трансляции программ.

В приложении Д приведено описание программного интерфейса (API) исполнительной подсистемы.

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

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

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

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

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

4. На языке Аспект реализованы фрагментированные версии алгоритмов умножения матриц, ИЛ разложения, явной разностной схемы, оценки математических ожиданий аддитивных функционалов от траекторий диффузионных процессов, взаимодействия короткого лазерного импульса с плазмой, на которых продемонстрирована запись типовых схем управления.

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

6. Разработана и реализована система программирования Аспект, основными компонентами которой являются:

- транслятор, обеспечивающий перевод программы с языка Аспект на С++;

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

7. Проведено тестирование системы Аспект на специальных, модельных и прикладных задачах, подтвердившее основные характеристики, заложенные при её проектировании и показавшее высокую эффективность предложенных подходов на выбранном классе задач.

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

Публикации в журналах, входящих в перечень ВАК:

1. Арыков С. Б., Малышкии В. Э. Алгоритмы конструирования асинхронных программ заданной степени непроцедурности методом группировки // Вестн. Новосиб. гос. ун-та. Серия: Информационные технологии. 2009. Т. 7, № 1. С. 3-15.

2. Арыков С. Б. Язык программирования Аспект // Известия Томского политехнического университета. 2008. Т. 313, № 5. С. 89-92.

3. Арыков С. Б., Малышкин В. Э. Система асинхронного параллельного программирования «Аспект» // Вычислительные методы и программирование. 2008. Т. 9, № 1. С. 205-209.

Публикации в трудах международных конференций:

4. Арыков С. Б. Асинхронное программирование численных задач // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)». Челябинск: Изд. ЮУрГУ, 2010. С. 28-39.

5. Arykov S., Malyshkin V. Asynchronous Language and System of Numerical Algorithms Fragmented Programming // Proceedings of the 10th International Conference on Parallel Computing Technologies (PaCT'2009). Berlin: Springer-Verlag, 2009. LNCS 5698. Pp. 1-7.

6. Арыков С. Б. Группировка данных в системе асинхронного параллельного программирования Аспект // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)». Челябинск: Изд. ЮУрГУ, 2009. С. 357-363.

7. Арыков С. Б., Малышкин В. Э. Система асинхронного параллельного программирования «Аспект» // Труды Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)». Челябинск: Изд. ЮУрГУ, 2008. С. 290-295.

Прочие публикации:

8. Арыков С. Б. Представление алгоритма умножения матриц на языке программирования «Аспект» // Сборник трудов VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии». Томск: Томский политехнический университет, 2008. С. 80-81.

9. Арыков С. Б. Архитектура системы асинхронного параллельного программирования «Аспект» // Материалы Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Молодежь и наука: начало XXI века»: в 4 ч. 4.1. Красноярск: Сибирский федеральный университет; Политехнический институт, 2007. С. 6-8.

10. Арыков С. Б. Реализация фрагментированной асинхронной модели вычислений в системе параллельного программирования // Тезисы докладов VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям. Новосибирск: Ин-т выч. техн. СО РАН, 2007. С. 84-85.

11. Арыков С. Б. Некоторые подходы к разработке асинхронного языка программирования «Аспект» // Труды конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2005. С. 13-23.

Арыков С. Б.

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

Автореферат

Подписано в печать 12.11.2010 г. Объем у^ уч.-изд. л.

Формат бумаги 60 • 90 1/16 Тираж 100 экз.

Отпечатано в ЗАО РИЦ «Прайс-курьер»

630128, г. Новосибирск, ул. Кутателадзе, 4г, тел. 330-72-02

Заказ № 595

Введение.

Глава 1. Средства разработки параллельных программ.

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

1.2. Средства разработки асинхронных программ.

1 1.2.1. Проект МАРС.

1.2.2. OpenTS.

1.2.3. Charm-н-.

1.2.4. Граф Плюс.

1.2.5. PLASMA.

1.3. Требования к системе программирования.

1.4. Выводы

Глава 2. Фрагментированное программирование.

2.1. Концепция фрагментированного программирования.

2.1.1. Предпосылки возникновения.

2.1.2. Неформальное определение.

2.2. Асинхронная модель вычислений.

2.2.1. Простая асинхронная модель.

2.2.2. Асинхронная модель со структурными А-блоками

2.2.3. Асинхронная модель с массовыми А-блоками.

2.2.4. Асинхронная модель с управлением на основе строгого частичного порядка.

2.3. Конструирование асинхронных программ.

2.3.1. Формальное определение управляющего оператора

2.3.2. Алгоритмы генерации управляющих операторов

2.4. Выводы .'.

Глава 3. Язык программирования Аспект.

3.1. Ключевые особенности.

3.2. Формальное определение

3.2.1. Структура программы.

3.2.2. Заголовок программы.

3.2.3. Объявления внешнего языка.

3.2.4. Объявление фрагментов данных.

3.2.5. Объявление фрагментов кода.

3.2.6. Объявление данных задачи.

3.2.7. Объявление фрагментов вычислений.

3.2.8. Объявление управления.

3.3. Программирование на языке Аспект.

3.3.1. Распространённые схемы управления.

3.3.2. Разложение матриц.

3.3.3. Вычисление п-то числа Фибоначчи.

3.3.4. Анализ фрагментированного подхода.

3.4. Выводы

Глава 4. Реализация системы программирования Аспект.

4.1. Программная архитектура системы.

4.2. Реализация транслятора.

4.2.1. Лексический анализатор

4.2.2. Синтаксический анализатор.

4.2.3. Генератор внутреннего представления

4.2.4. Генератор кода.

4.2.5. Ограничения реализации.

4.3. Реализация исполнительной подсистемы.

4.3.1. Слой абстрагирования от операционной системы

4.3.2. Функциональные модули.

4.3.3. Интерфейс системных вызовов

4.3.4. Ограничения реализации.

4.4. Порядок работы с системой.

4.4.1. Трансляция Аспект-программы

4.4.2. Окончательная сборка программы.

4.4.3. Отладка программы.

4.5. Выводы

Глава 5. Практические испытания

5.1. Тестовая среда и методика испытаний.

5.2. Тестирование на специальных тестах.

5.2.1. Накладные расходы исполнительной подсистемы

5.2.2. Поддержка большого количества фрагментов

5.2.3. Накладные расходы управляющих операторов.

5.3. Тестирование на модельных задачах.

5.3.1. Умножение матриц.

5.3.2. Разложение матриц.

5.3.3. Явная разностная схема.

5.3.4. Использование специализированных библиотек

5.4. Тестирование на прикладных задачах

5.4.1. Метод Монте-Карло.

5.4.2. Метод частицы-в-ячейках.•.

5.5. Выводы

I

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

Разработка хорошей параллельной программы в настоящее время.остаётся сложной задачей. Параллельная программа должна обладать рядом динамических свойств (динамической настройкой нащоступные ресурсы, динамической балансировкой загрузки, динамическим учётом поведения; численной модели); которые существующими системами программирования в полнот мере не обеспечиваются^а их ручнаяфеализация требует серьёзных знаний теории параллельного программирования, архитектуры ЭВМ; программных особенностей средств разработки. В параллельных программах встречаются специфические ошибки, которые сложно обнаружить и устранить в силу недетерминизма исполнения таких программ. Наконец; перенос параллельной программы, с одного вычислителя на другой часто также сопряжён со значительными

ТРУДНОСТЯМИ:

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

Значительным шагом на этом пути можно считать такие системы, как НРБ, БУМ, трС. Они берут на себя заботу о реализации коммуникаций, син-хронизаций и некоторых других проблемах, однако, в силу излишне жестко заданного управления (что характерно для всех императивных языков), автоматически выявить внутренний параллелизм алгоритма часто не удаётся.

С повсеместным распространением многоядерных процессоров задача разработки параллельной программы ещё более усложняется, поскольку эф) фекгивно распределить доступные ресурсы между крупными взаимодействующими последовательными процессами затруднительно. Это породило множеI ство исследовательских проектов, направленных на поиск более подходящей модели вычислений. Среди российских разработок можно отметить проект МАРС (языки Барс и Поляр), систему НОРМА, систему OpenTS; среди зарубежных — библиотеку PLASMA, системы ALF, Charm++, SMP superscalar и другие.

Одним из новых подходов, альтернативных программированию на основе параллельно-последовательной модели вычислений, является фрагменти-рованное программирование. К его основным преимуществам можно отнести возможность автоматической генерации параллельной программы, возможность автоматически обеспечить программам ряд динамических свойств, лучшую переносимость между вычислителями различной архитектуры, а также возможность выполнить формальный анализ параллельной программы. Этот подход в настоящее время активно развивается, и в существующих проектах (PLASMA, ALF, Charm-H-) реализованы лишь его отдельные элементы. Поэтому дальнейшее развитие средств фрагментированного программирования является актуальной задачей.

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

Цель работы. Целью диссертационной работы является разработка языка и системы фрагментированного параллельного программирования задач численного моделирования.

Для достижения поставленной цели были сформулированы следующие задачи:

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

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

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

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

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

Научная новизна. Научной новизной обладают следующие результаты диссертационной работы, полученные автором лично: I

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

2. Совокупность способов задания управления во фрагментированной программе, включая массовое управление. |

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

• алгоритмы генерации управляющих операторов, поддерживающие массовое управление;

• методика представления асинхронной программы на языке С++.

Практическая значимость. Результаты работы могут лечь в основу широкого спектра средств, разработки фрагментированных параллельных программ и-применяться для решения прикладных задач численного моделирования. Язык Аспект позволяет начать накопление библиотеки, фрагментированных алгоритмов, а возможность замены разработанной исполнительной подсистемы на другую обеспечивает переносимость Аспект-программ;

Система программирования Аспект используется в отделе МО ВВС Института вычислительной математики и математической геофизики СО-РАН для выполнения исследований по. различным проектам; а также в учебном процессе Новосибирского государственного университета и Новосибирского государственного технического университета для обучения студентов параллельному программированию. На защиту выносятся: I I

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

2. Язык фрагментированного программирования Аспект.

3. Система фрагментированного программирования Аспект и алгоритмы её реализации.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались: 1

• на Конференции молодых ученых ИВМиМГ СО РАН (Новосибирск, 2005 и 2006 гг.);

• на VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Новосибирск,

2007 г.);

• на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)» (Санкт-Петербург, 28 января — 1 февраля i

2008 г.);

• на VI Всероссийской конференции студентов, аспирантов и молодых ученых «Молодёжь и современные информационные технологии» (Томск, 26-28 февраля 2008 г.);

• на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)» (Нижний Новгород, 30 марта — 3 апреля

2009 г.);

• на Международной научной конференции «Parallel Computer Technologies i

PaCT-2009)» (Новосибирск, 31 августа — 4 сентября 2009 г.);

• на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (Уфа, 29 марта — 2 апреля 2010 г.);

• на научных семинарах «Математическое и архитектурное обеспечение параллельных вычислений» (отдел МО ВВС Института вычислительной математики и математической геофизики СО РАН), «Архитектура, системное и прикладное программное обеспечение кластерных суперЭВМ» (расширенный семинар ССКЦ, НГУ, Центра Компетенции СО РАН — INTEL), «Системное программирование», «Конструирование и оптимизация программ» (объединённые семинары кафедры программирования НГУ и Института систем информатики имени А.П. Ершова СО РАН).

Публикации. По теме диссертации опубликовано 11 работ, в том числе 3 статьи в рецензируемых журналах и 4 статьи в сборниках трудов международных конференций.

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

Структура и объем диссертации. Диссертационная работа состоит из введения, пята глав, заключения, списка литературы из 125 наименований и пяти приложений. Общий объем работы составляет 195 страниц, из них 151 страница основного текста, включая 13 таблиц и 23 рисунка. Общий объем программного кода составляет 9702 строки.

5.5. Выводы

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

1. Характеристики исполнительной подсистемы, заложенные при её проектировании, подтверждаются результатами практических испытаний.

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

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

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

5. На исследованных задачах система программирования Аспект достигает высокой эффективности.

Заключение

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

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

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

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

4. На языке Аспект реализованы фрагментированные версии алгоритмов

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

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

6. Разработана и реализована система программирования Аспект, основными компонентами которой являются:

• транслятор, обеспечивающий перевод программы с языка Аспект на С++;

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

7. Проведено тестирование системы Аспект на специальных, модельных и прикладных задачах, подтвердившее основные характеристики, залоI женные при её проектировании и показавшее высокую эффективность предложенных подходов на выбранном классе задач.

1. Аветисян А. И., Бабкова В. В., Калугин М. Д. Разработка приложений в среде ParJava // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2008. № 54. С. 139-144.

2. Алексеев Е. Р., Чеснокова О. В., Рудченко Е. A. Scilab: Решение инженерных и математических задач. М.: ALT Linux; БИНОМ. Лаборатория знаний, 2008. 269 с.

3. Андрианов А. Н. Система Норма : Разработка, реализация и использоваIние для решения задач математической физики на параллельных ЭВМ: Докторская диссертация / ИПМ им. М. В. Келдыша. 2001.

4. Андрианов А. Н. Применение языка Норма для решения задач на вложенных сетках // Вычислительные методы и программирование. 2002. Т. 3. С. 1-10.

5. Андрианов А. Н., Ефимкин К. Н., Задыхайло И. Б. Непроцедурный язык для решения задач математической физики // Программирование. 1991. № 2. С. 80-94. !

6. Анисимов В. А. Система параллельного программирования «Иня» // Математическое и архитектурное обеспечение параллельных вычислений. Новосибирск: ВЦ СО АН СССР, 1989. С. 67-73.

7. Арыков С. Б. Некоторые подходы к разработке асинхронного языка программирования «Аспект» // Труды конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2005. С. 13-23.

8. Арыков С. Б. Язык программирования Аспект // Известия Томского политехнического университета. 2008. Т. 313, № 5. С. 89-92.

9. Арыков С. Б. Группировка данных в системе асинхронного параллельного программирования Аспект // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2009)». Челябинск: Изд. ЮУрГУ, 2009. С. 357-363.

10. Арыков С. Б. Асинхронное программирование численных задач // Труды международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)». Челябинск: Изд. ЮУрГУ, 2010. С. 28-39.

11. Арыков С. Б., Малышкин В. Э. Система асинхронного параллельногопрограммирования «Аспект» // Вычислительные методы и программирование. 2008. Т. 9, № 1. С. 205-209. '

12. Арыков С. Б., Малышкин В. Э. Система асинхронного параллельного программирования «Аспект» // Труды Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2008)». Челябинск: Изд. ЮУрГУ, 2008. С. 290-295. '

13. Арыков С. Б., Малышкин В. Э. Алгоритмы конструирования асинхронных программ заданной степени непроцедурности методом группировки // Вестн. Новосиб. гос. ун-та. Серия: Информационные технологии.2009. Т. 7, № 1. С. 3-15.

14. Ахо А., Сети Р., Ульман Д. Компиляторы: принципы, технологии и инструменты. М.: Вильяме, 2003. 768 с. ISBN: 5-8459-0189-8.

15. Ачасова С. М., Бандман О. JI. Корректность параллельных вычислительных процессов. Новосибирск: Наука. Сиб. отд-ние, 1990. 253 е. ISBN: 5-02-029334-2.f

16. Басс Л., Клементе П., Кацман Р. Архитектура программного обеспечения на практике. 2-е изд. СПб.: Питер, 2005. 576 с. ISBN: 5-469-00494-5.

17. Бузин А. Ю. Введение в современный АПЛ. 2-е изд. М.: ВЦ РАН, 1998. 184 с. ISBN: 5-201-14724.

18. Бульонков M. A., Быстров A. В., Дудоров H. H., Котов В. E. Базовый язык параллельного программирования Барс // Программирование. 1986. № 6. С. 32-40.

19. Быстров А. В., Дудоров H. Н., Котов В. Е. О базовом языке // В кн. Языки и системы программирования. Новосибирск: ВЦ СО АН СССР, 1979. С. 85-106.

20. Вальковский В. А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и связь, 1989. 176 с.t

21. Вальковский В. А., Малышкин В. Э. Синтез параллельных программ и систем на вычислительных моделях. Новосибирск: Наука, 1988. 129 с.

22. Васенин В. А., Водомеров А. Н. Формальная модель системы автоматизированного распараллеливания программ // Программирование. 2007. № 4. С. 3-19.

23. Вирт Н. Долой «жирные» программы // Открытые системы. 1996. № 6. С. 26-31.

24. Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

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

26. Воробьёв H. Н. Числа Фибоначчи. Серия «Популярные лекции по математике». 4-е изд. М.: Наука, 1978. 144 с.

27. Востокин С. В. Графическая объектная модель параллельных процессов и ее применение в задачах численного моделирования. Самара: Издательство Самарского научного центра РАН, 2007. 286 с. ISBN: 978-5-93424-284-9.

28. Вшивков В. А., Вшивков К. В., Дудникова Г. И. Алгоритмы решения задачи взаимодействия лазерного импульса с плазмой // Вычислительные технологии. 2001. Т. 6, № 2. С. 47-63.

29. Вшивков В. А., Краева М. А., Малышкин В. Э. Параллельная реализация метода частиц//Программирование. 1997. №2. С. 39-51.

30. Гергель В. П. Теория и практика параллельных вычислений. Москва: Интернет-университет информационных технологий; Бином. Лаборатория знаний, 2007. 423 с. ISBN: 978-5-94774-645-7.

31. Григорьев Ю. Н., Вшивков В. А., Федорук М. П. Численное моделирование методами частиц-в-ячейках. Новосибирск: Издательство СО РАН, 2004. 360 с.

32. Ершов А. П. Введение в теоретическое программирование (беседы о методе). Серия «Популярные лекции по математике». М.: Наука, 1977. 288 с.

33. Касьянов В. Н., Бирюкова Ю. В., Евстигнеев В. А. Функциональный язык Sisal // В кн. Поддержка супервычислений и интернет-ориентированные технологии. Новосибирск: ИСИ СО РАН, 2001. С. 54-67.

34. Касьянов В. Н., Поттосин И. В. Методы построения трансляторов. Новосибирск: Наука, 1986. 344 с.t

35. Коварцев A. H. Автоматизация разработки и тестирования программных средств. Самара: Сам. гос. аэрокосм, ун-т., 1999. 150 с.

36. Коновалов Н. А., Крюков В. А., Сазанов Ю. JI. C-DVM — язык разработки мобильных параллельных программ // Программирование. 1999. № 1. С. 20-28.

37. Котов В. Е. О практической реализации асинхронных параллельных вычислений // В кн. Системное и теоретическое программирование. Новосибирск: ВЦ СО АН СССР, 1972. С. 110-125.

38. Котов В. Е. Параллельное программирование с типами управления // Кибернетика. 1979. № 3. С. 1-13.

39. Котов В. Е. Алгебра регулярных сетей Петри // Кибернетика. 1980. № 5. С. 10-18.

40. Котов В. Е., Марчук А. Г. Некоторые итоги и перспективы развития проекта МАРС // В кн. Актуальные проблемы развития архитектуры и программного обеспечения ЭВМ и вычислительных систем. Новосибирск: ВЦ СО АН СССР, 1983. С. 13-23.

41. Котов В. Е., Нариньяни А. С. Асинхронные вычислительные процессы над памятью // Кибернетика. 1966. № 3. С. 64-71.

42. Краева М. А., Малышкин В. Э. Алгоритмы динамической балансировки загрузки при реализации метода частиц в ячейках на МИМД-мультиком-пьютерах // Программирование. 1999. № 1. С. 47-53.

43. Кутепов В. П., Котляров Д. В., Осипов М. А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах // Известия РАН, Теория и системы управления. 2005. № 1. С. 75-96.

44. Легалов А. И. Функциональный язык для создания архитектурно-независимых параллельных программ // Вычислительные технологии. 2005. Т. 10, № 1. С. 71-89.

45. Лельчук Т. И. Языковая реализация параллельной асинхронной моделивычислений // Кибернетика. 1984. № 5. С. 32-37.t

46. Лельчук Т. И., Марчук А. Г. ПОЛЯР — язык параллельного асинхронного программирования // Программирование. 1983. №4. С. 59-68.

47. Лельчук Т. И., Марчук А. Г. Язык программирования Поляр: описание, использование, реализация, Под ред. В. Б. Котова. Новосибирск: ВЦ СО АН СССР, 1986. 94 с. 1

48. Малышкин В. Э. ОПАЛ язык описания параллельных алгоритмов // В кн. Теоретические вопросы параллельного программирования и многопроцессорные ЭВМ. Новосибирск: ВЦ СО АН СССР, 1983. С. 91-109.

49. Малышкин В. Э., Корнеев В. Д. Параллельное программирование' мультикомпьютеров. Новосибирск: Изд-во НГТУ, 2006. 296 с. ISBN: 5-7782-0702-6.

50. Малышкин В. Э., Цыгулин A. A. ParaGen — генератор параллельных программ, реализующих численные модели // Автометрия. 2003. Т. 39, № 3. С. 124-135.

51. Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. М.: Наука, 1986. 368 с.

52. Марченко М. А. Комплекс программ MONC для распределенных вычисIлений методом Монте-Карло // Сиб. журн. вычисл. математики. 2004. Т. 7, № 1. С. 43-55.

53. Марченко М. А., Михайлов Гг А. Весовые алгоритмы статистического моделирования диффузионных процессов // Журн. вычисл. матем. и мат. физики. 2003. Т. 43, № 4. С. 571-584.

54. Мейерс С. Эффективное использование STL. Библиотека программиста. СПб.: Питер, 2002. 224 с. ISBN: 5-94723-382-7.

55. Мейерс С. Эффективное использование С++. 50 рекомендаций по улучшению ваших программ и проектов. М.: ДМК Пресс, 2006. 240 с. ISBN: 5-469-01213-1.I

56. Минц Г. Е., Тыугу Э. X. Обоснование структурного синтеза программ // Автоматический синтез программ. Таллин: Ин-т кибернетики АН ЭстССР, 1983. С. 5-40.

57. Михайлов Г. А., Войтишек А. В. Численное статистическое моделирование. Методы Монте-Карло. М.: Издательский центр «Академия», 2006. 368 с. ,

58. Непейвода Н. Н., Скопин И. Н. Основания программирования. Москва-Ижевск: Институт компьютерных исследований, 2003. 913 с.1.BN: 5-93972-299-7.i

59. Пешио К. Никлаус Вирт о культуре разработки ПО // Открытые системы. 1998. № 1. С. 41-44.I

60. Серебряков В. А. Лекции по конструированию компиляторов. М.: ВЦ РАН, 1994. 175 с.

61. Скопин И. Н. Множественное структурирование данных // Программирование. 2006. Ш 1. С. 57-72.

62. Страуструп Б. Дизайн и эволюция С++. СПб.: Питер, 2006. 448 с. ISBN: 5-469-01217-4.

63. Торгашёв В. А., Царёв И. В. Средства организации параллельных вычислений и программирования в мультипроцессорах с динамической архитектурой И Программирование. 2001. №4. С. 53-67.

64. Фаддеев Д. К., Фаддеева В. Н. Вычислительные методы линейной алгебры. 2-е изд. М.: Наука; 1963. 656 с.

65. Фаулер М., Скотт К. UML. Основы. СПб.: Символ-Плюс, 2002. 192 с. ISBN: 5-93286-032-4.

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

67. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989. 264 с. ISBN: 5-03-001043-2.

68. Accelerated Library Framework Programmer's Guide and API Reference. URL:http://public.dhe.ibm.com/software/dw/cell/ALFProg GuideAPIv3.1 .pdf (дата обращение: 21.09.2010).

69. Agha G. Actors: A Model of Concurrent Computation In Distributed Systems:

70. Tech. Rep. Technical Report 844, MIT Artificial Intelligence Laboratory: 1985.i

71. Anderson E., Bai Z., Bischof C. et al. LAPACK User's Guide. 3d edition. Philadelphia: SIAM, 1999. 425 pp. ISBN: 0-89871-447-8.

72. Backus J. W., Bauer F. L., Green J. et al. Revised report on the algorithm language ALGOL 60 // Communications of the ACM. 1963. Vol. 6, no. 1. Pp. 1-17.

73. Beguelin A., Dongarra J. J. Graphical development tools for network-basedconcurrent supercomputing // Proceedings of the 1991 ACM/IEEE conferience on Supercomputing (Supercomputing'1991). New York: ACM, 1991. Pp. 435-444.

74. Blume W., Doallo R., Eigenmann R. et al. Parallel Programming with Polaris // Computer. 1996. Vol. 29, no. 12. Pp. 78-82.

75. Buttari A., Langou Ji, Kurzak J., Dongarra J. A class of parallel tiled linear algebra algorithms for multicore architectures // Parallel Computing. 2009. Vol. 35,' no. 1. Pp. 38-53.

76. Chamberlain B. L., Callahan D., Zima H. P. Parallel Programmability andIthe Chapel Language // International Journal of High Performance Computing Applications. 2007. Vol. 21, no. 3. Pp. 291-312.

77. CHARM++ Programming Language Manual. URL: http://charm.cs. uiuc.edu/manuals/html/charm++/ (дата обращения: 15.07.2010).

78. Choi J., Demmel J., Dhillon I. et al. ScaLAPACK: A portable linear algebra library for distributed memory computers — design issues and performance // Computer Physics Communications. 1996. Vol. 97, no. 1-2. P. 1-15.

79. Cierniak M., Li W. Unifying Data and Control Transformations for Distributed Shared-Memory Machines // Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation (PLDI'1995). New York: ACM, 1995. Pp. 205-217.

80. Clint W. C., Petitet A., Dongarra J. Automated Empirical Optimization of Software and the "ATLAS'Troject // Parallel Computing. 2001. Vol. 27, no. 1-2. Pp. 3-35.

81. Cooperman G. TOP-C: Task-oriented parallel С for distributed and sharedimemory // Workshop on wide area networks and high performance computing. Berlin: Springer-Verlag, 1999. Pp. 109-117.i

82. Feautrier P. Parametric Integer Programming // RAIRO Recherche Op'erationnelle. 1988. Vol. 22. Pp. 243-268.

83. The Fortress Language Specification, Version 1.0. URL: http://labs. oracle.com/projects/plrg/Publications/fortress.1.0.pdf(дата обращения: 27.08.2010).

84. Forum H. P. F. High Performance Fortran Language Specification, version 1.0: Tech. Rep. CRPC-TR92225, Rice University: 1993.

85. Genetic ALgorithm Optimized for Portability and Parallelism System. URL: http://garage.cse.msu.edu/software/galopps/ (дата обращения: 17.08.2010).

86. GNU General Public License. URL: http: //www.gnu. org/licenses/gpl. html (дата обращения: 18.08.2010).i

87. Gustavson F. G. New Generalized Matrix Data Structures Lead to a Variety of High-Performance Algorithms // Proceedings of the IFIP TC2/WG2.5 Working Conference on the Architecture of Scientific Software. Deventer: Kluwer, B.V., 2001. Pp. 211-234. i

88. Hall M. W., Anderson J. M., Amarasinghe S. P. et al. Maximizing Multiprocessor Performance with the SUIF Compiler // Computer. 1996. Vol. 29, no. 12. Pp. 84-89.

89. Hoare C. A. Monitors: an operating system structuring concept // Communications of the ACM. 1974. Vol. 17, no. 10. Pp. 549-557.

90. IEEE Std 1003.1, 2004 Edition. URL: http://www.opengroup. org/onlinepubs/009695399/basedefs/pthread.h.html (дата обращения: 30.08.2010).

91. Intel® Cilk Plus. URL: http://www.cilk.com/ (дата обращения: 12.09.2010).

92. Intel® Hyper-Threading Technology (Intel® HT Technology). URL: http:Iwww. intel. com/inf о/hyperthreading/ (дата обращения: 30.08.2010).

93. Intel® Math Kernel Library Reference Manual. URL: http: //software.intel.com/sites/products/documentation/hpc/compilerpro/en-us/cpp/win/mkl/ref тал/index, htm (дата обращения: 17.08.2010).

94. Kale L. V., Krishnan S. CHARM++: A Portable Concurrent Object Oriented System Based On С++ // SIGPLAN Notes. 1993. Vol. 28, no. 10. Pp. 91-108.

95. Kasyanov V. N., Evstigneev V. A. The PROGRESS program manipulation system // Proceedings of the 2nd International Conference on Parallel Computing Technologies (PaCT'1993). Vol. 3. 1993. Pp. 651-656.

96. Kraeva M. A., Malyshkin V. E. Assembly technology for parallel realization of numerical models on MIMD-multicomputers // Future generation computer systems. 2001. Vol. 17, no. 6.! Pp. 755-765.

97. Lamport L. The parallel execution of DO loops // Communications of the ACM. 1973. Vol. 17, no. 2. Pp. 83-93.i

98. Lastovetsky A. Adaptive parallel computing on heterogeneous networks withmpC // Parallel Computing. 2002. Vol. 28, no. 10. Pp. 1369-1407.i

99. Lindsley R. Kernel korner: What's new in the 2.6 Scheduler // Linux Journal. 2004. no. 119. P. 13.

100. Mascagni M., Srinivasan A. Algorithm 806: SPRNG: A Scalable Library for Pseudorandom Number Generation // ACM Transactions on Mathematical Software. 2000. Vol. 26, no. 3. Pp. 436-461.

101. McCool M., Bruce A. Programming using RapidMind on the Cell BE // Proceedings of the 2006 ACM/IEEE conference on Supercomputing (SC'2006).

102. New York: ACM, 2006. P. 222.I

103. Moskovsky A., Roganov V., Abramov S. Parallelism granules aggregation with the T-system // Proceedings of the 9th International Conference on Parallel Computing Technologies (PaCT'2007). LNCS 4671. Berlin: Springer-Verlag, 2007. Pp. 293-302.

104. Moskovsky A., Roganov V., Abramov S., Kuznetsov A. Variable Reassignment in the T++ Parallel Programming Language // Proceedings of the 9th International Conference on Parallel Computing Technologies (PaCT'2007).

105. CS 4671. Berlin: Springer-Verlag, 2007. P. 579-588.i

106. MPI: A Message-Passing Interface Standard. URL: http://www.mcs. anl.gov/research/projects/mpi/mpi-standard/mpi--report-l. 1/1 Impi-report .htm (дата обращения: 18.08.2010).

107. Newton P., Browne J. C. The CODE 2.0 Graphical Parallel Programming Language // Proc. of the Sixth ACM International Conference on Supercomputing. New York: ACM, 1992. Pp. 167-177.

108. OpenMP specifications. URL: http://openmp.org/wp/ openmp-specifications/ (дата обращения: 18.08.2010).

109. Park N., Hong В., Prasanna V. K. Analysis of Memory Hierarchy Performance of Block Data Layout // Proceedings of the 2002 International Conference on Parallel Processing (ICPP'2002). Washington: IEEE Computer Society, 2002. P. 35.

110. PLASjMA. URL: http://icl.cs.ntk.edu/plasma/ (дата обращения: 31.08.2010).

111. POSIX Threads for Win32. URL: http://sourceware.org/ pthreads-win32/ (дата обращения: 30.08.2010).

112. Reinders J. Intel Threading Building Blocks. Sebastopol: O'Reilly Media, 2007. 336 pp. ISBN: 0-596-51480-8.

113. Roy P., Haridi S. Concepts, Techniques, and Models of Computer Programming. Cambridge: MIT Press, 2004. 900 pp. ISBN: 0-262-22069-5.

114. Schloegel K., Karypis G., Kumar V. Parallel static and dynamic multi-constraint graph partitioning // Concurrency and Computation: Practice and Experience. 2002. Vol. 14,' no. 3. Pp. 219-240.

115. SMP superscalar. URL: http://www.bsc.es/plantillaG.php?catid= 385 (дата обращения: 27.08.2010).

116. Task Parallel Library. URL: http://msdn.microsoft.com/en-us/ library/dd460717. aspx (дата обращения: 27.08.2010).

117. Voevodin V. V., Voevodin V. V. V-Ray Technology: a New Approach to the Old Problems. Optimization of the TRFD Perfect Club Benchmark to CRAY Y-MP and CRAY T3D Supercomputers // Proc. of the High Performance Computing Symposium'95. 1995. Pp. 380-385.

118. Yip E. L. FORTRAN Subroutines for Out-of-Core Solutions of Large Complex Linear Systems: Tech. Rep. CR-159142, NASA: November 1979.