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

Российская академия наук Институт системного программирования РАН

УДК 519 685

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

□03446341

Бабкова Варвара Вадимовна

МЕТОДОЛОГИЯ ПОДДЕРЖКИ РАЗРАБОТКИ ЭФФЕКТИВНЫХ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

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

АВТОРЕФЕРАТ

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

Москва 2008

2 2 СЕН 2003

003446341

Работа выполнена в Институте системного программирования РАН

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

Аветисян Арутюн Ишханович

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

Крюков Виктор Алексеевич

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

Ведущая организация

Вычислительный центр им. А.А.Дородницина

РАН

Защита диссертации состоится « 10 » октября 2008 г в 15 часов на заседании диссертационного совета Д 002 087 01 при Институте системного программирования РАН по адресу

109004, Москва, ул Б Коммунистическая, д 25,

Институт системного программирования РАН, конференц-зал (коми 110)

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

Автореферат разослан <</\ » сентября 2008 г

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

/Прохоров С П /

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

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

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

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

Конечно, наиболее кардинальным решением было бы создание нового языка высокого уровня, который обеспечил бы возможность разрабатывать параллельные программы с помощью оптимизирующих компиляторов Но, к сожалению, исследования по высокоуровневым языкам параллельного программирования, проводившиеся, начиная с 1988 года, не увенчались успехом Разрабатываемые языки HPF (и его Java-ncpaisi HPJavä), Cilk, UPC (и его Java-версия Titanium) и другие - не сумели решить поставленных перед ними задач Основная причина неудачи в том, что, несмотря на значительные усилия, до сих пор не удалось разработать компиляторные технологии, позволяющие генерировать эффективный параллельный код Отметим также, что надежды, связанные с созданием языков нового поколения XI О, Chapel, Fortress, даже, несмотря на то, что эти языки

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

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

Цель диссертационной работы.

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

Научная новизна

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

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

• Разработан и реализован в среде Раг1а\'а механизм оптимальной организации контрольных точек

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

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

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

По теме диссертации опубликовано семь работ [1-7], в том числе две - в изданиях по перечню ВАК

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

• Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ технологии параллельного программирования», г Новороссийск, 18-23 сентября 2006

• Международный научно-практический Семинар и Молодежная школа «Высокопроизводительные Параллельные Вычисления на Кластерных Системах» 12-17 декабря 2006 года

• International Conférence on the Methods of Aerophysical Research - Novosibirsk, 2007

• Sixth International Conférence on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia

• MTPP 2007 Parallel Computing Technologies Firbt Russian-Taiwan Symposium Pereslavl-Zalessku (Russia), September 2-3,2007

• V Всероссийская межвузовская конференция молодых ученых, г Санкт-Петербург .15-18 апреля 2008 г

• Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), 20-22 мая 2008 г Санкт-Петербург

Структура и объем диссертации

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

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

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

В первой главе приводится обзор существующих инструментальных средств, таких как TAU (Университет штата Орегон и Исследовательский центр Juelich из Лос-Аламоса) и Paradyn (Университет штата Висконсин), поддерживающих реализацию, отладку и доводку параллельных программ Как правило, эти системы предоставляют программисту наборы таких инструментов для анализа

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

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

В настоящее время разрабатывается большое количество параллельных приложений Анализ публикаций о масштабируемости приложенийх в журналах «Математическое моделирование» и «Computer Physics Communications» за 20052007 годы, показал, что в большинстве параллельных программ математической физики обеспечивается масштабируемость до 30 вычислителей

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

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

2) Оценка максимального потенциально достижимого ускорения по доле последовательных вычислений в программе

3) Обеспечение возможности параллельного выполнения гнезд циклов

а Исследование гнезд циклов на возможность параллельного выполнения (вычисление вектора направлений и вектора расстояний между итерациями гнезда циклов с помощью Омега-теста) Ь Преобразование гнезд циклов к виду, допускающему параллельное выполнение (устранение зависимостей по данным между итерациями)

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

5) Выбор операций обмена данными

6) Оценка границ области масштабируемости и времени счета на реальных данных

7) В случае необходимости, использование механизма контрольных точек

Инструментальные средства среды Раг^а позволяют увязать перечисленные

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

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

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

Таким образом, чтобы получить масштабируемую программу, надо, в первую очередь, свести к минимуму долю вычислений, которые не могут выполняться параллельно Согласно закону Амдаля, если /- доля последовательных вычислений и, если параллельная программа выполняется на р-вычислителях без накладных расходов на коммуникации или распараллеливание, максимально достижимое ускорение (независимо от числа используемых вычислителей) при/=50% не белее 2, а при/=1% не более 50 Следовательно, приступая к распараллеливанию программы, необходимо оценить и по возможности минимизировать/ При этом надо учитывать следующее 1) если аппаратура целевой вычислительной системы или используемая версия MPI не поддерживает параллельный ввод/вывод, то операторы ввода/вывода входят в/, 2) если цикл не распараллеливается, то он входит в/

В среде ParJava реализован инструмент "Speed-up", который, используя временной профиль последоватечьной программы (строится инструментом "Profiler"), оценивает / и строит для этой программы график зависимости потенциально достижимого ускорения от количества вычислителей По умолчанию предполагается, что все циклы могут быть распараллелены, при этом пользователь имеет возможность отметить циклы, которые он не собирается распараллеливать В случае, если потенциально достижимое ускорение удовлетворительно, переходим к следующему этапу

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

итерациями Для этого в среде ParJava реализован Омега-тест (инструмент «Loop Analyzer») Для определения зависимостей существует большое количество тестов Бесполезно решать задачу напрямую, даже с линейными индексными выражениями, так как нахождение зависимостей сводится в итоге к решению системы диофантовых уравнений (или задаче целочисленного линейного программирования), что является NP-тюпюй задачей Тесты для определения зависисмостей можно условно разбить на простые, но не точные, и точные, но сложные Компромиссным вариантом здесь является Омега-тест, который основан на последовательном применении набора тестов от простого к сложному

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

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

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

В качестве примера рассмотрим цикл

for (1 = 1, 1 <= 100, i++)

for(j = 1, j <=100, :++) {

x[i,:] = x[i,:] + yu - i,]], /*sl*/

Y[x,;j] = Y [x, j ] + X [x, j - 1], /*s2*/ }

Распределение данных по вычислителям для таких задач можно построить с помощью инструмента среды ParJava «DataDistr», который использует методы целочисленного программирования Для приведенного примера этот инструмент выдаст следующую модификацию цикла с распределением независимых данных по вычислителям

Х[1,100] = Х[1,100] + Y [0,10 0] , /*sl*/

for (р = -99, р <= 98; р++) {

if (р >= 0)

Y [р+1,1] = Х[р+1,0] + Y [р+1,1] , /*s2*/

for (i = max (1 ,p+2) , i <= mxn(100,100+p), i++) { X[l,l-p-1] = X [l,l-p-1] + Y[1-1,1-p-l];/*sl*/ Y[x,x-p] = X[x,x-p-l] + Y[x,x-p], /*s2*/

}

if (p <= -1)

X[101+p,100] = X[101+p,100] + Y[101+p-l,100],

/ * si * /

}

Y [100,1] = X[100,0] + Y [100 ,1] , / * s2 * /

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

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

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

Если программа принадлежит к классу задач, сводящихся к системе линейных алгебраических уравнений с полной матрицей, то массив, в котором хранится матрица системы, разбивается на блоки При этом у смежных блоков возникают так называемые теневые грани, размер которых определяется алгоритмом решения задачи и определяет фактический объем передаваемых в сети сообщений Очевидно, что в случае, когда по всем индексам взаимосвязи между элементами массива однородны, то оптимальнее всего разбивать массив по всем его размерностям, так как с увеличением количества плоскостей разбиения суммарный объем передаваемых данных снижается Так, при обработке трехмерного массива с Л? элементами уже при использовании 128 вычислителей, в случае одномерного разбиения и толщины теневой грани в один элемент объем передаваемых данных равен 254А^, в случае двумерного разбиения - 4АЫ2, а в случае трехмерного разбиения - 26Л'~ Однако, в случае неоднородных зависимостей по различным индексам может выясниться, что разбиения по некоторым индексам приводят к дополнительным обменам Так как это обусловлено спецификой конкретной решаемой задачи, оно не может быть оценено заранее

В предлагаемой методологии с помощью инструмента среды Раиска "КейисПог,¡" строится так называемый «скелет» программы, в котором сохранены доля последовательных вычислений, объем пересылок и время счета тела цикла Такой «скелет» программы позволяет быстро переделывать и интерпретировать ее, что, в частности, позволяет оценить объем пересылаемых данных по разным направлениям

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

В тривиальных случаях даже использование стандартных коммуникационных функций (send, receive) позволяет достичь достаточного уровня масштабируемости Однако, в большинстве случаев это невозможно, так как приводит к большим накладным расходам на коммуникации, а это в соответствии с законом Амдаля существенно уменьшает масштабируемость

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

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

В качестве примера рассмотрим программу, в которой процесс отправляет данные (массив bufD) соседнему процессу с помощью функции MPI_Issend, а тот, в свою очередь, получает данные, используя функцию MPI_Irecv На рисунке 1 схематически показана передача данных из массива bufD процесса РО в массив bufl процесса Р1

f

При вызове MPI_Issend (момент времени на рисунке 1) будут инициализированы необходимые структуры данных, доступ к буферу bufO будет передан сетевому процессору (процесс NP0 ), который будет выполнять передачу

Рисунок 1 Схема процесса неблокирующего обмена

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

1 . До тех пор пока процессу РО не потребуется снова использовать массив bufO, он может выполняться параллельно с передачей данных. Как только процессу РО потребуется поместить новые данные в ЬиГО, он должен вызвать функцию MPI Wait, которая обеспечит доступ к массиву bufO, как только процесс NP0

f

закончит передачу данных в сеть, и буфер освободится (момент 2 ). Начиная с

этого момента, буфер ЬиГО будет свободен, и его можно будет снова использовать в процессе РО Следовательно, как показано на рисунке 1, вызов МР1 ДОал.1:1

заблокирует процесс РО до момента 2 , а вызов МР1_Иал.12 не приведет к блокировке процесса РО

Для приема сообщения, процесс Р1 вызывает функцию МР1_1гес^ (в момент

времени и ), которая инициализирует структуры данных, после чего выполнение процесса Р1 будет продолжено, а прием сообщения будет осуществлять сетевой процесс №1, записывающий данные в массив ЬиП процесса Р1 Выполнение

операции МР1_1гесу в процессе Р1 закончится в момент времени 1 Момент

времени, когда процесс №1 получит все данные из сети, на рисунке обозначен ?

через 2 Как только процессу Р1 понадобятся данные из принимающего буфера (ЬиП), он вызовет функцию МР1_Иал^ (МР1_Юаз^4) Если бы функция МР1_Юал^

была вызвана до момента 2, (вызов МР1_тЛа1£3), процесс заблокировался бы до момента 2

Сетевые процессоры могут одновременно обслуживать и посылку, и прием данных Время, потраченное на запрос (разрешение) на передачу данных от процесса №0 к процессу ЫР] определяется латентностью сети (Ь)

Как видно из схемы на рисунке 1 необходимо добиться, чтобы во время

передачи данных сетевым процессором (промежуток между моментами времени ^

и ¿2 для отправителя и время между и ¿2 Для получателя) вычислитель был /

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

В предлагаемой методологии строится «скелет» программы и проводятся его

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

Проиллюстрировать важность оптимального выбора операции пересылок можно на следующем «скелете» программы (рисунок 2 а) Если в рассматриваемом «скелете» заменить блокирующие операции Send и Recv на неблокирующие и установить соответствующую операцию Wait после гнезда циклов, получится «скелет», представленный на рисунке 26 На рисунке 3 приведены графики ускорения «скелетов» программ, представленных на рисунках 2а и 26 Пунктирная линия, идущая под 45 градусов к осям, обозначает идеальное ускорение, при котором последовательная часть равна нулю Вспомогательная пунктирная медиана - это вспомогательная линия, позволяющая судить о качестве масштабируемости

//sending

Send

Recv

//calculating

for (i = beg_i, i < end_i, i++) for (j =0, j <N, j++)

ВМШ-ЦАМЫ).

(а)

Рисунок 2 Схематичное изображение алгоритмов с блокирующими и неблокирующими пересылками

Если график масштабируемости выше этой линии, то масштабируемость удовлетворительная, если ниже - не удовлетворительная Как видно из графика,

//sending

ISend

IRecv

//calculating

for (l = bcg_i + I, i < end_i -1, i++) for 0 = 0,} < N, ]++) B[i]Ij] = f(A[i][j]), //waiting

WaitO.

//calculating last columns if (my id '=0)

for(j=0,j<N; j++) B[0][j] = f(tempL[j]), if (myid != proc_size -1) for (j = 0; J < N, J++) B[N-lJlj] = f(tempR[j]),

(6)

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

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

Сравнение на модельном примере

"•^"блокирующий send -•^-неблокирующий send • " Амдалева кривая для этой программы

Рисунок 3 Сравнение масштабируемости параллельных программ, использующих блокирующие и неблокирующие пересылки

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

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

На следующем этапе необходимо проинтерпретировать полученную программу на реальных данных, для того, чтобы оценить, какое количество вычислителей будет оптимальным для счета Для этого используется инструмент среды Par Java «Inerpreten

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

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

Применение интерпретатора позволяет достаточно точно оценивать ускорение программы Ошибка на реальных приложениях не превосходила 10% и в среднем составила -5%

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

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

Пользователь указывает в программе место сохранения данных с помощью директивы ЕХСЬиВЕ_НЕЫЕ С помощью этих директив компилятор может выполнять анализ потока данных В контрольной точке 1 (рисунок 4) не сохраняются данные, которые будут обновлены до своего использования («мертвые» переменные) В контрольной точке 2 не сохраняются данные, которые используются только дчя чтения до этой контротьной точки Результатом будет значитетьное уменьшение размеров сохраняемых данных в контрольной точке и уменьшение накладных расходов на сохранение

Контрольная точка I

Контрольная точка 2

Рисунок 4 Контрольные точки

Вначале граф потока управления G=(N, Е) разбивается на подграфы G' Корнем каждого подграфа G' является директива EXCLUDE_HERE Подграф включает все пути, достижимые из этой директивы, не проходящие через другую директиву EXCLUDE_HERE

Для каждого подграфа вычисляются 2 множества переменных

• DE(G') - множество переменных, которые «мертвы» на каждой директиве EXCLUDE_HERE в G'

• RO(G') - множество переменных, предназначенных только-для-чтения по всему подграфу G'

Для нахождения двух множеств DE(G') и RO(G') используется консервативный анализ потока данных

В каждом состоянии S в программе вычисляются множествя def[S] и use[S], характеризующие доступ к памяти

• use[S] - множество переменных, которые могут быть использованы вдоль некоторого пути в графе

• def[S] - множество переменных, которым присваиваются значения до их использования вдоль некоторого пути в графе, начинающегося в S, или множество определений переменных

Определив эти базовые множества, мы можем определить DE(G') и RO(G') Ячейка памяти 1 «живая» в состоянии S, если существует путь из S в другое состояние S' такой, что 1 euse[S'] и для каждого S" на этом пути lgdef[S"] Ячейка 1 является элементом DE(G'), если 1 «мертвая» во всех операторах сохранения контрольных точек в G'

Ячейка памяти 1 является ячейкой только-для-чтения в операторе S, если 1 £use[S] Поэтому le RO(G') тогда и только тогда, когда lggen[S] для всех S в G'

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

Анализ «живых» переменных обычно выражается в виде уравнении потоков данных, по одному на каждое состояние в программе Мы дадим уравнение потока данных, которое позволит нам определить ВЕ(С) и Ю(О') для каждого подграфа С в программе Каждое из этих уравнеыш может быть решено обычным итеративным методом

Для достижения нашей цели уравнение потока данных характеризуем его функцией обновления Такая функция ассоциируется с каждым состоянием в Определим т[8] как множество мертвых переменных в точке непосредственно перед блоком Б, а оШ[8] - такое же множество в точке, непосредственно следующей за бтоком Э

Вычисляем множество мертвых переменных в направлении обратном графу потока управления Система уравнений выглядит следующим образом оШ[8] = пБ' 1п[8'] хпИ = РБ,

где ои![8] = пв' ВЕАО[8'] - это пересечение множества мертвых переменных для всех состояний 8', которые являются преемниками Б в в, а ББ - это функция обновления, которая в нашем случае равна Б8 - ощ[8] и gen[S] - иБе[8] и свидетельствует о переменных, которые мертвы непосредственно перед 8 и тех переменных, которые стали мертвыми после в, плюс о тех, в которые производилась запись в состоянии Б, минус любые ячейки, с которых происходило чтение в 8

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

Глава 4 посвящена применению разработанной методологии поддержки разработки параллельных программ на примере создания программы моделирования интенсивных атмосферных вихрей (ИАВ)

Возможность развития ИАВ (торнадо, ураганов) за счет начальной энергии мезовихрей впервые была ранее показана численно и были представлены результаты численного моделирования осесимметричного вихря в одномерной несжимаемой нестратифицированной атмосфере В Институте физики Земли РАН была реализована численная модель развития торнадо в трехмерной сжимаемой сухоадиабатической атмосфере Большой объем вычислений для получения численного решения задач подобного типа потребовал реализации программы на высокопроизводительных вычислительных кластерах

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

является сильно нелинейной системой смешанного типа Программа разрабатывалась в Институте системного программирования РАН в сотрудничестве с Институтом физики Земли РАН с использованием среды ParJava и предназначена для выпочнения на кластерных вычислительных системах

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

Параллельная программа была реализовала в среде ParJava с использованием библиотеки MPI Инструменты среды ParJava позволили провести анализ параллельной программы и оптимизировать ее код

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

После инициализации программа сохраняет нулевой стой данных и начинает выполнять свой основной цикл по времени На одну итерацию по времени 4 раза вызывается функция Layer, которая вычисляет значения основных массивов в цикле по X, по У, по Z, и, если на данной итерации надо делать сохранение данных, то 3 раза вызывается функция Eplus

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

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

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

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

Тестирование производилось на кластере ИСП РАН, на 16ти 4-ядерных процессорах Intel(R) Xeon(R) CPU Х5355 @ 2 66GHz Myrmet Express 2000 При тестировании производительности (рисунок 5) использовались начальные данные

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

количество процессоров

Блокирующие пересылки Оптимизированные блокирующие пересылки * 1 Оптимизированные неблокирующие пересылки - - Амдалева кривая

Рисунок 5 График ускорения.

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

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

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

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

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

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

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

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

1 Аветисян А И, Бабкова В , Гайсарян С С , Губарь А Ю Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому Трехмерная численная модель в Раг1ауа // Журнал «Математическое моделирование» 2008, т 20, номер 8 , стр 28-40

2 А И Аветисян, В В Бабкова и А Ю Губарь «Возникновение торнадо трехмерная численная модель в мезомасштабной теории турбулентности по В Н Николаевскому»// «ДАН / Геофизика», том 419, №4, с 547-552

3 Аветисян А И, Бабкова В В , Губарь А 10 «Моделирование интенсивных атмосферных вихрей в среде ParJava » // Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ технологии параллельного программирования», г Новороссийск, 18-23 сентября 2006 стр 109-112

4 А И Аветисян, С С Гайсарян, А Ю Губарь, В В Бабкова «Моделирование интенсивных атмосферных вихрей в среде ParJava" // Международный научно-практический Семинар и Молодежная шкота «Высокопроизводительные Параллельные Вычисления на Кластерных Системах» 12-17 декабря 2006 года стр 16-20

5 A Yu Gubar, AI Avetisyan, and V V Babkova, "Numerical modelling of 3D tornado arising in the mesovortice turbulence theory of Nikolaevskiy" //International Conference on the Methods of Aerophysical Research Proc Pt III /Ed VM Fomm -Novosibirsk Publ House "Parallel", 2007 -250p,ppl35-140

6 Victor P Ivanmkov, Arutyun I Avetisyan, Varvara V Babkova, Alexander Yu Gubar "Tornado arising modeling using high performance cluster systems" // Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia, pp 56-59

7 AI Avetisyan, V V Babkova, S S Gaissaryan, A Yu Gubar "Intensive Atmospheric Vortices Modeling Using High Performance Cluster Systems" // MTPP 2007 Parallel Computing Technologies First Russian-Tanvan Symposium Pereslavl-Zalesskn (Russia), September 2-3, 2007, LNCS, v 4671/2007, pp 487495

Подписано в печать 05 09 2008 г Печать трафаретная

Заказ № 693 Тираж 75 экз

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

1. Введение.

2. Современное состояние технологий разработки параллельных программ.'.

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

Par Java.

3.1. Методология.

3.2. Оценка максимального потенциально достижимого ускорения.

3.3. Исследование гнезд циклов на возможность параллельного выполнения.

3.4. Преобразование гнезд циклов к виду, допускающему параллельное выполнение.

3.5. Распределение данных по узлам вычислительной сети.

3.6. Выбор операций обмена данными.

3.7. Оценка границ области масштабируемости и времени счета на реальных данных.

4. Механизм контрольных точек.

5. Программа моделирования интенсивных атмосферных вихрей.

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

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

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

Конечно, наиболее кардинальным решением было бы создание нового языка высокого уровня, который обеспечил бы возможность разрабатывать параллельные программы с помощью оптимизирующих компиляторов. Но, к сожалению, исследования по высокоуровневым языкам параллельного программирования, проводившиеся, начиная с 1988 года, не увенчались успехом. Ни один из разработанных языков: HPF (и его Java-версия HPJava), С ilk, UPC (и его Java- версия Titanium) и ряд других менее известных языков, — не сумел решить поставленных перед ним задач. Основная причина неудачи в том, что, несмотря на значительные усилия, до сих пор не удалось разработать компиляторные технологии, позволяющие генерировать эффективный параллельный код. Отметим также, что надежды, связанные с созданием языков нового поколения XI0, Chapel, Fortress, даже, несмотря на то, что эти языки требуют более детально описывать структуру параллельной вычислительной среды, пока не оправдываются.

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

Цель диссертационной работы. В ИСП РАН разрабатывается интегрированная инструментальная среда ParJava поддерживающая разработку параллельных программ. Целью диссертационной работы является исследование и создание методологии поддержки разработки параллельных программ и реализация ее в рамках среды ParJava, которая разрабатывается в Институте системного программирования РАН. Также целью диссертационной работы является реализация и апробирование методологии и соответствующих инструментальных средств на классе численных приложений, связанных с решением сильно нелинейных многокомпонентных трехмерных систем уравнений в частных производных смешанного типа.

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

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

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

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

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

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

По теме диссертации опубликовано семь работ [1-7], в том числе две — в изданиях по перечню ВАК.

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

• Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ: технологии параллельного программирования», г. Новороссийск, 18-23 сентября 2006.

• Международный научно-практический Семинар и Молодежная школа «Высокопроизводительные Параллельные Вычисления на Кластерных Системах» 12-17 декабря 2006 года.

• International Conference on the Methods of Aerophysical Research -Novosibirsk, 2007.

• Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia

• MTPP 2007 Parallel Computing Technologies First Russian-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3, 2007

• V Всероссийская межвузовская конференция молодых ученых, г. Санкт-Петербург , 15-18 апреля 2008 г .

• Международная научная конференция «Космос, астрономия и программирование» (Лавровские чтения), 20-22 мая 2008 г. Санкт-Петербург

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

В первом разделе приводится обзор существующих инструментальных средств, таких как TAU (Университет штата Орегон и Исследовательский центр Juelich из Лос-Аламоса) и Paradyn (Университет штата Висконсин), поддерживающих реализацию, отладку и доводку параллельных программ. Как правило, эти системы предоставляют программисту наборы таких инструментов для анализа параллельных программ как профилировщик, трассировщик, инструменты для моделирования работы программы, визуализатор и др. Эти системы являются наборами различных инструментов, нацеленных на поддержку разработки параллельных программ. Однако в них не рассматриваются вопросы организации технологического процесса, позволяющего разрабатывать параллельные программы гарантированного качества, опираясь на их инструменты. Кроме того, разработанные в рамках этих систем инструментальные средства, как правило, базируются на использовании целевой аппаратуры, что связано со значительными накладными расходами, как по времени разработки, так и по используемым ресурсам.

В настоящее время разрабатывается большое количество параллельных приложений. Анализ масштабируемости приложений, опубликованных в журналах «Математическое моделирование» и «Computer Physics Communications» за 2005-2007 годы и приводимый в первом же разделе, показал, что в большинстве параллельных программ математической физики обеспечивается масштабируемость до 30 вычислителей.

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

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

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

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

Раздел 4 посвящен программе моделирования интенсивных атмосферных вихрей (ИАВ), как пример применения разработанного технологического процесса и инструментария на практике.

Возможность развития ИАВ (торнадо, ураганов) за счет начальной энергии мезовихрей впервые была ранее показана численно и были представлены результаты численного моделирования осесимметричного вихря в одномерной несжимаемой нестратифицированной атмосфере. В Институте физики Земли была реализована численная модель развития торнадо в трехмерной сжимаемой сухоадиабатической атмосфере. Большой объем вычислений для получения численного решения задач подобного типа потребовал реализации программы на высокопроизводительных вычислительных кластерах.

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

Параллельная программа была реализована в среде ParJava с использованием библиотеки MPI. Инструменты среды ParJava позволили провести анализ параллельной программы и оптимизировать ее код.

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

Раздел 5 содержит выводы и направления дальнейших исследований.

6. Заключение

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

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

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

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

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

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

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

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

1. Аветисян А.И., Бабкова В., Гайсарян С.С., Губарь А.Ю. Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому. Трехмерная численная модель в Par Java. // Журнал «Математическое моделирование». (Принято к печати)

2. А.И.Аветисян, В.В. Бабкова и А.Ю.Губарь. «Возникновение торнадо: трехмерная численная модель в мезомасштабной теории турбулентности по В.Н.Николаевскому»// «ДАН / Геофизика» , том 419, №4, с. 547-552.

3. Victor P. Ivannikov, Arutyun I. Avetisyan, Varvara V. Babkova, Alexander Yu. Gubar "Tornado arising modeling using high performance cluster systems" //

4. Sixth International Conference on Computer Science and Information Technologies (CSIT'2007), 24-28 September, Yerevan, Armenia

5. J.C. Adams, W.S. Brainard, J.T. Martin, B.T. Smith, J.L. Wagener. Fortran 95 Handbook. Complete ISO/ANSI Reference. Scientific and Engineering Computation Series. MIT Press, Cambridge, Massachusetts, 1997

6. B. Carpenter, G. Fox, H.K. Lee, S.B.Lim. Translation Schemes for the HPJava Parallel Programming Language // LNCS v. 2624, 2003, pp. 177-192

7. R.D. Blumofe, C.F. Joerg, B.C. Kuszmaul, C.E. Leiserson, K.H. Randall, Y. Zhou. Cillc: An Efficient Multithreaded Runtime System. // Proc of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), 1995, pp. 207-216

8. W. Chen, C. Iancu, K. Yelick. Communication Optimizations for Fine-grained UPC Applications //14th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2005.

9. B.L. Chamberlain, D. Callahan, H.P. Zima. Parallel Programmability and the Chapel Language // International Journal of High Performance Computing Applications, August 2007, 21(3): 291-312.

10. E. Allen, D. Chase, J. Hallett et al The Fortress Language Specification (Version 1.0) / cSun Microsystems, Inc., March 31, 2008 (262 pages)

11. А.Б.Горшков. «Алгоритм распараллеливания при численном решении двумерных стационарных уравнений Навье-Стокса с использованием неявной итерационной схемы» «Математическое моделирование», 2005, т. 17, № 11, с. 67-71.

12. И.В.Шариков, Д.М. Хрупов, С.Т. Суржиков. «Использование параллельных вычислений при численном моделировании взаимодействия воздушной лазерной плазмы с поверхностью» // «Математическое моделирование» 2006, т. 18,№8, с. 12-24.

13. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jaffrey D. Ullman. Compilers: principles, techniques, and tools. -2nd ed., Pearson Education Inc., 2007, c.836.

14. Jeremy Kepner, David Koester "HPCS Application Analysis and Assessment"// http://www.highproductivity.org/kepner-HPCS.htm21.http://www.totalviewtech.com/index.htm22.http://www.allinea.com/?page=48

15. В.П. Иванников, А.И. Аветисян, С.С. Гайсарян, В. А. Падарян. Прогнозирование производительности MPl-программ на основе моделей. // Журнал «Автоматика и телемеханика», 2007, N5, с. 8-17.

16. Хргиан А.Х. Физика атмосферы. М: Изд-во Московского Университета, 1986. С.240.

17. Nikolaevskiy V.N. Angular Momentum in Geophysical Turbulence: Continuum. Spatial Averaging Method . Dordrecht: Kluwer (Springer). 2003. P. 245.

18. Арсеньев C.A., Губарь А.Ю., Николаевский B.H. Самоорганизация торнадо и ураганов в атмосферных течениях с мезомасштабными вихрями. // ДАН, 2004, т.396, № 4, с.541-546.

19. Хаин А.П., Сутырин Г.Г. Тропические циклоны и их взаимодействие с океаном. Д.: Гидрометеоиздат, 1983. С.272.

20. Емцев Б.Т. Техническая гидромеханика. М.: Машиностроение, 1978. С.463.

21. Флетчер К. Вычислительные методы в динамике жидкостей (2т). М.: Мир, 1991. С.504, С.522.

22. Gilbert Anthony. Tornado With a Measured Intensity of T3 at Hill Head, Hampshire, 5, November 1999. // J.Meteorol. 2000. 25, N254. c.361-367.

23. Васильев B.A, Романовский Ю.М, Яхно В.Г. Автоволновые процессы. М.: Наука, 1987. С.240.

24. Е. S. Posmentier//Geophys. J. R.astr. Soc. (1967), 13, pp.487 501. 33.Sameer S. Shende, Allen D. Malony. The TAU Parallel Performance System //

25. The International Journal of High Performance Computing Applications,Volume 20, No. 2, Summer 2006, pp. 287-311

26. The Vampir System http://www.vampir.eu/index.html

27. The Cache Performance and Optimizations of Blocked Algorithms. Monica S. Lam, Edward E. Rothberg and Michael E. Wolf, Computer Systems Laboratory, Stanford University, CA 94305.

28. Самарский A.A., Гулин A.B. Численные методы. M.: Наука, 1989, 432 с.

29. Victor Ivannikov, Serguei Gaissaiyan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference. LNCS 2840. Sept. 2003, Venice, pp. 491-494.

30. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Analyzing Dynamic Properties of Parallel Program in ParJava Environment. // Proc. of the conf. Computer science and Information technologies. Sept. 2003, Yerevan, pp. 19-23.

31. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Estimating Scalability of a Parallel Program in ParJava Environment. // Russian -Indian Intern. Workshop on HPC, June 2003, Moscow, pp 29-30.

32. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Development of Scalable Parallel Programs in ParJava Environment. // Parallel CFD 2003, May 2003, Moscow, pp. 291 293.

33. А.И. Аветисян, С.С. Гайсарян, В.А. Падарян. Эффективный обмен данными на сетях JavaVM. // Тезисы докладов, XLIV Научная конференция МФТИ, Современные проблемы фундаментальных и прикладных наук, 4.VII. Ноябрь 2001, Москва Долгопрудный, стр. 29.

34. А.И. Аветисян, И.В. Арапов, С.С. Гайсарян, В.А. Падарян. Параллельное программирование с распределением по данным в системе ParJava. // Вычислительные методы и программирование. 2001 г., Москва, т. 2, №1. стр. 129-146.

35. А.И. Аветисян, В. А. Падарян. Библиотека интерфейсов и классов, расширяющих язык Java средствами разработки параллельных программ в модели SPMD. // Труды института системного программирования, 2001, Москва, т.2, стр. 49-64.

36. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Using symbolic execution of a parallel program to estimate its scalability. // «Parallel and Distributed Processing Techniques and Applications», Las Vegas. 2003.

37. Barton P. Miller etc, The Paradyn Parallel Performance Measurement Tools // Computer, Volume 28 , Issue 11 (November 1995) Pages: 37 46

38. Sabri Pllana, Thomas Fahringer, Performance Prophet: A Performance Modeling and Prediction Tool for Parallel and Distributed Programs // Parallel Processing, 2005. ICPP 2005 Workshops. International Conference Workshops 14-17 June 2005 Page(s): 509-516

39. D. A. Grove and P.D. Coddington, Communication Benchmarking and Performance Modelling of MPI Programs on Cluster Computers// Proceedings of the 18th International Parallel and Distributed Processing Symposium (1PDPS'04)

40. PGI CDK, Cluster Development Kit. Linux cluster development tools for 32-bit and 64-bit processor-based systems. http://www.pgroup.com/products/cdkindex.htm

41. Douglas Miles, Brent Leback and David Norton , Optimizing Application Performance on x64 Processor-based Systems with PGI Compilers and Tools// http://www.pgroup.com/lit/pgiarticletuning.pdf

42. PGHPF Compiler User's Guide, http://www.pgroup.eom/doc/p.ghpf u,g/hp(ug.htm

43. David F. Bacon, Susan L. Graham, Oliver J. Sharp Compiler Transformations for High-Performance Computing// ACM Computing Surveys, Vol. 26, No. 4, December 1994

44. Message Passing Interface http:/Avww-unix.mcs.anl.gov/mpi/

45. MPI: The Message Passing Interface http://parallel.ru/tcch/techdev/mpi.html

46. MPI Implementation List, http://www.lam-mpi.org/mpi/implementations/

47. Myricom home page, http://www.myri.com/

48. R. Baldoni. J.M. Hellary. M. Raynal, "Direct Dependency-Based Determination of Consistent Global Checkpoints". 1998.

49. K. Mani Chandy, Leslie Lamport. "Distributed Snapshots: Determining Global States of Distributed Systems". ACM Transactions on Computer Systems Vol.3, No. 1, February 1985.

50. Babaoglu and K. Marzullo. "Consistent global states of distributed systems: Fundamental Concepts and mechanisms". Distributed Systems, Ed. S. Mullender, Addison Wesley pp.55-96 1993.

51. Y.M. Wang, P.Y. Chung, I,J. Lin and W.K. Fuchs. "Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems". In IEEE Transactions on Parallel and Distributed Systems, 6(5): 546-554, May 1995.

52. D.L. Russel. "State restoration in systems of communicating processes". In IEEE Transactions on Software Engineering, SE-6(2): 183-194, Mar. 1980.

53. D.Briatico A. Ciuffoltti, and L. Simoncini. "A distributed domino-effect free recovery algorithm. "In Proceeings of the IEEE International Symposium on Reliability, Distributed Software,a nd Databases, pp.207-215, Dec. 1984.

54. R. Neitzer, J. Xu. Necessary and sufficient conditions for consistent global snapshots. IEEE Transactions on Parallel and Distributed Systems. 6(2): 165-169, February 1995.

55. N. Nevis. W.K.Fuchs. "Coordinated Checkpointing Without Direct Coordination". 1998.

56. Sung E. Choi. Steven J. Deitz. "Compiler Support for Automatic Checkpointing."In Proceedings of the Sixteenth Annual International Symposium on High Performance Computing Systems and Applications, 2002.

57. L. Lamport. Time, clocks and ordering events in distributed systems. Communications of the ACM, 21(7):558-565, July 1978.

58. D.Briatico A. Ciuffoltti, and L. Simoncini. "A distributed domino-effect free recovery algorithm. "In Proceeings of the IEEE International Symposium on Reliability, Distributed Software,a nd Databases, pp.207-215, Dec. 1984.

59. Y.M. Wang, A.Lowry and W.K. Fuchs, "Consistent Global Checkpoints Based on Direct Dependency Tracking."Information Processing Letters, 50:223-230. 1994.

60. P.Cremonesi and C. Gennaro "Integrated Performance Models for SPMD Applications and MIMD Architectures."In IEEE Transactions on Parallel and Distributed Systems, vol. 12 No. 13, Dec. 2002

61. J. Hellary, A. Mostefaoui, R. Netzer, and M.Raynal. "Preventing useless checkpoints in distributed computations."In 16th IEEE Symposium of Reliable Distributed Systems, October 1997