WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Российская академия наук

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

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

УДК 519.685

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

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

ПАРАЛЛЕЛЬНЫХ ПРОГРАММ

Специальность 05.13.11 –

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

АВТОРЕФЕРАТ

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

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

Научный руководитель: кандидат физико-математических наук Аветисян Арутюн Ишханович

Официальные оппоненты: доктор физико-математических наук Крюков Виктор Алексеевич кандидат физико-математических наук Суков Сергей Александрович

Ведущая организация: Вычислительный центр им. А.А.Дородницина РАН

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

109004, Москва, ул. Б. Коммунистическая, д.25, Институт системного программирования РАН, конференц-зал (комн. 110).

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

Автореферат разослан « » сентября 2008 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ:

технологии параллельного программирования», г. Новороссийск, 18- сентября 2006.

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

• International Conference on the Methods of Aerophysical Research – Novosibirsk, • 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, • V Всероссийская межвузовская конференция молодых ученых, г. СанктПетербург, 15-18 апреля 2008 г.

программирование» (Лавровские чтения), 20-22 мая 2008 г. Санкт-Петербург Структура и объем диссертации Работа состоит из введения, четырёх глав, заключения и списка литературы.

Общий объем диссертации составляет 90 страниц. Список литературы содержит наименований.

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

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

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

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

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

параллельных программ и инструменты ParJava, поддерживающие эту методологию.

Методологию можно представить в виде процесса, включающего следующие этапы:

1) Реализация последовательной версии разрабатываемой программы.

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

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

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

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

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

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

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

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

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

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

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

Бесполезно решать задачу напрямую, даже с линейными индексными выражениями, так как нахождение зависимостей сводится в итоге к решению системы программирования), что является NP-полной задачей. Тесты для определения зависисмостей можно условно разбить на простые, но не точные, и точные, но сложные. Компромиссным вариантом здесь является Омега-тест, который основан на последовательном применении набора тестов от простого к сложному.

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

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

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

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

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

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

for (i = max(l,p+2); i = min(100,100+p); i++) { X[i,i-p-l] = X[i,i-p-l] + Y[i-l,i-p-l];/*s1*/ X[101+p,100] = X[101+p,100] + Y[101+p-l,100];

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

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

Если программа принадлежит к классу задач, сводящихся к системе линейных алгебраических уравнений с полной матрицей, то массив, в котором хранится матрица системы, разбивается на блоки. При этом у смежных блоков возникают так называемые теневые грани, размер которых определяется алгоритмом решения задачи и определяет фактический объем передаваемых в сети сообщений. Очевидно, что в случае, когда по всем индексам взаимосвязи между элементами массива однородны, то оптимальнее всего разбивать массив по всем его размерностям, так как с увеличением количества плоскостей разбиения суммарный объем передаваемых данных снижается. Так, при обработке трехмерного массива с N элементами уже при использовании 128 вычислителей, в случае одномерного разбиения и толщины теневой грани в один элемент объем передаваемых данных равен 254N2, в случае двумерного разбиения – 44N2, а в случае трехмерного разбиения – 26N2. Однако, в случае неоднородных зависимостей по различным индексам может выясниться, что разбиения по некоторым индексам приводят к дополнительным обменам. Так как это обусловлено спецификой конкретной решаемой задачи, оно не может быть оценено заранее.

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

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

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

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

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

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

В MPI определено несколько видов посылки и приема сообщений:

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

В качестве примера рассмотрим программу, в которой процесс отправляет данные (массив buf0) соседнему процессу с помощью функции MPI_Issend, а тот, в свою очередь, получает данные, используя функцию MPI_Irecv. На рисунке схематически показана передача данных из массива buf0 процесса P0 в массив buf процесса P1.

При вызове MPI_Issend (момент времени на рисунке 1) будут инициализированы необходимые структуры данных, доступ к буферу buf0 будет передан сетевому процессору (процесс NP0 ), который будет выполнять передачу Временная ось Рисунок 1 Схема процесса неблокирующего обмена сообщения, а процесс P0 продолжит выполнять свою программу. Таким образом, выполнение операции MPI_Issend в процессе P0 закончится в момент времени t1s. До тех пор пока процессу P0 не потребуется снова использовать массив buf0, он может выполняться параллельно с передачей данных. Как только процессу P потребуется поместить новые данные в buf0, он должен вызвать функцию MPI_Wait, которая обеспечит доступ к массиву buf0, как только процесс NP этого момента, буфер buf0 будет свободен, и его можно будет снова использовать в процессе P0. Следовательно, как показано на рисунке 1, вызов MPI_Wait заблокирует процесс P0 до момента, а вызов MPI_Wait2 не приведет к блокировке процесса P0.

Для приема сообщения, процесс P1 вызывает функцию MPI_Irecv (в момент времени которая инициализирует структуры данных, после чего выполнение процесса P1 будет продолжено, а прием сообщения будет осуществлять сетевой процесс NP1, записывающий данные в массив buf1 процесса P1. Выполнение операции MPI_Irecv в процессе P1 закончится в момент времени. Момент времени, когда процесс NP1 получит все данные из сети, на рисунке обозначен через Как только процессу P1 понадобятся данные из принимающего буфера (buf1), он вызовет функцию MPI_Wait (MPI_Wait4). Если бы функция MPI_Wait была вызвана до момента t 2, (вызов MPI_Wait3), процесс заблокировался бы до момента Сетевые процессоры могут одновременно обслуживать и посылку, и прием данных. Время, потраченное на запрос (разрешение) на передачу данных от процесса NP0 к процессу NP1 определяется латентностью сети (L).

Как видно из схемы на рисунке 1 необходимо добиться, чтобы во время передачи данных сетевым процессором (промежуток между моментами времени t2 для отправителя и время между t1 и t 2 для получателя) вычислитель был занят обработкой данных, а не простаивал в ожидании окончания пересылки.

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

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

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

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

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

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

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

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

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

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

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

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

Вначале граф потока управления G=(N, E) разбивается на подграфы G.

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

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

• DE(G) - множество переменных, которые «мертвы» на каждой • RO(G) - множество переменных, предназначенных только-для-чтения консервативный анализ потока данных.

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

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

Определив эти базовые множества, мы можем определить DE(G) и RO(G):

Ячейка памяти l «живая» в состоянии S, если существует путь из S в другое состояние S такой, что l use[S] и для каждого S на этом пути ldef[S]. Ячейка l является элементом DE(G), если l «мертвая» во всех операторах сохранения контрольных точек в G.

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

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

Анализ «живых» переменных обычно выражается в виде уравнений потоков данных, по одному на каждое состояние в программе. Мы дадим уравнение потока данных, которое позволит нам определить DE(G) и RO(G) для каждого подграфа G в программе. Каждое из этих уравнений может быть решено обычным итеративным методом.

Для достижения нашей цели уравнение потока данных характеризуем его функцией обновления. Такая функция ассоциируется с каждым состоянием S.

Определим in[S] как множество мертвых переменных в точке непосредственно перед блоком S, а out[S] – такое же множество в точке, непосредственно следующей за блоком S.

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

где out[S] = S DEAD[S] – это пересечение множества мертвых переменных для всех состояний S, которые являются преемниками S в G, а FS – это функция обновления, которая в нашем случае равна FS = out[S] gen[S] – use[S] и свидетельствует о переменных, которые мертвы непосредственно перед S и тех переменных, которые стали мертвыми после S, плюс о тех, в которые производилась запись в состоянии S, минус любые ячейки, с которых происходило чтение в S.

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

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

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

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

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

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

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

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

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

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

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

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

Тестирование производилось на кластере ИСП РАН, на 16ти 4-ядерных процессорах Intel(R) Xeon(R) CPU X5355 @ 2.66GHz Myrinet Express 2000. При тестировании производительности (рисунок 5) использовались начальные данные рабочей задачи, но вычислялись только первая секунда жизни торнадо. Пунктиром показано линейное ускорение, которое является теоретическим пределом ускорения для параллельной задачи. В данном случае изображен график ускорения для программы с двумерным разбиением массива по процессорам. Реализован вариант с трехмерным рабиением, но такой вариант разбиения для данной программы оказался не самым оптимальным, в виду неоднородности вычислений по оси Z.

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

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

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

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

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

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

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

2008, т.20, номер 8, стр. 28- 2. А.И.Аветисян, B.B. Бабкова и А.Ю.Губарь. «Возникновение торнадо:

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

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

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

5. A.Yu. Gubar, A.I. 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. V.M. Fomin. – Novosibirsk: Publ. House “Parallel”, 2007. – 250 p; pp135-140.

6. Victor P. Ivannikov, 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. A.I. 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-Taiwan Symposium Pereslavl-Zalesskii (Russia), September 2-3, 2007, LNCS, v. 4671/2007, pp 487- 495.



 


Похожие работы:

«АЙРАПЕТОВ ДАВИД АЛЬБЕРТОВИЧ АЛГОРИТМЫ И ПРОГРАММНЫЙ КОМПЛЕКС АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ПРОЦЕССОМ ПРОЕКТИРОВАНИЯ СИСТЕМ УПРАВЛЕНИЯ СЛОЖНЫМИ ТЕХНОЛОГИЧЕСКИМИ ОБЪЕКТАМИ Специальность: 05.13.01 Системный анализ, управление и обработка информации (промышленность) АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Калининград – 2013 2 Работа выполнена на кафедре Системы управления и вычислительная техника в Федеральном государственном бюджетном...»

«НАЗАРЕНКО КИРИЛЛ МИХАЙЛОВИЧ МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И МЕТОДЫ ОЦЕНИВАНИЯ РИСКОВ ИНВЕСТИРОВАНИЯ В ФИНАНСОВЫЕ АКТИВЫ С ВЫСОКОЙ ВОЛАТИЛЬНОСТЬЮ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2009 Работа выполнена в ГОУ ВПО Московском государственном технологическом университете СТАНКИН Научный руководитель : доктор...»

«ПЛЕШКОВА ЮЛИЯ АЛЕКСАНДРОВНА МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭФФЕКТИВНЫХ СИСТЕМ ПЕРЕДАЧИ ОПТИЧЕСКОГО СИГНАЛА НАСЕКОМЫМ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата технических наук Тамбов – 2014 2 Работа выполнена на кафедре прикладной математики и информатики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования...»

«Скворцова Мария Ивановна МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ В ИССЛЕДОВАНИЯХ СВЯЗИ МЕЖДУ СТРУКТУРОЙ И СВОЙСТВАМИ ОРГАНИЧЕСКИХ СОЕДИНЕНИЙ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва – 2007 1 Работа выполнена в Московской государственной академии тонкой химической технологии (МИТХТ) им. М. В. Ломоносова ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор...»

«Шека Андрей Сергеевич Модели, алгоритмы и программный комплекс для обеспечения интеллектуального эксперимента 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург – 2014 Работа выполнена на кафедре алгебры и дискретной математики ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б. Н. Ельцина Научный руководитель : Попов...»

«Аленин Артём Алефтинович РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ СКРЫТОЙ ПЕРЕДАЧИ ИНФОРМАЦИИ В АУДИОФАЙЛАХ Специальность: 05.13.15 Вычислительные машины, комплексы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Самара – 2011 Работа выполнена на кафедре информатики и вычислительной техники Федерального государственного образовательного бюджетного учреждения высшего профессионального образования Поволжский государственный...»

«Авдюшенко Александр Юрьевич НОВЫЕ ЧИСЛЕННЫЕ МОДЕЛИ ГИДРОДИНАМИКИ ТУРБОМАШИН 05.13.18 — Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Новосибирск — 2014 Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте вычислительных технологий Сибирского отделения Российской академии наук, г. Новосибирск. Научный руководитель : доктор...»

«ЧЕКИНА Александра Валерьевна ГЕНЕТИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ТЕХНИЧЕСКОЙ ДОКУМЕНТАЦИИ В ПРОЕКТНЫХ РЕПОЗИТОРИЯХ САПР 05.13.12 – Системы автоматизации проектирования (промышленность) Автореферат диссертации на соискание ученой степени кандидата технических наук Ульяновск – 2012 Работа выполнена на кафедре Информационные системы в Ульяновском государственном техническом университете. Научный руководитель : доктор технических наук, профессор Ярушкина Надежда Глебовна Официальные...»

«Нигматулин Равиль Михайлович УСТОЙЧИВОСТЬ СТАЦИОНАРНОГО УРОВНЯ ЧИСЛЕННОСТИ ПОПУЛЯЦИИ В ДИСКРЕТНОЙ МОДЕЛИ ПИЕЛОУ С ДВУМЯ ЗАПАЗДЫВАНИЯМИ 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук ЧЕЛЯБИНСК – 2008 Работа выполнена на кафедре математического анализа ГОУ ВПО Челябинский государственный педагогический университет. Научный руководитель : доктор...»

«Мосягина Елизавета Николаевна ОПТИМАЛЬНОЕ ПОВЕДЕНИЕ ПЕРИОДИЧЕСКИ НЕСТАЦИОНАРНЫХ АВТОМАТНЫХ МОДЕЛЕЙ В НЕЧЕТКО ЗАДАННЫХ УСЛОВИЯХ 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Санкт-Петербург 2012 Работа выполнена на кафедре статистического моделирования математико - механического факультета Санкт-Петербургского...»

«КАПЫШ АЛЕКСАНДР СЕРГЕЕВИЧ ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ РАССУЖДЕНИЙ ПО ПРЕЦЕДЕНТАМ (НА ПРИМЕРЕ ЗАДАЧИ УПРАВЛЕНИЯ ВОДОХОЗЯЙСТВЕННОЙ СИСТЕМОЙ) 05.13.01 – Системный анализ, управление и обработка информации (промышленность) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Волгоград – 2011 Работа выполнена в Волгоградском государственном техническом университете. Научный руководитель : доктор технических наук,...»

«Трифонов Сергей Владимирович ОПТИМИЗАЦИЯ РАБОТЫ МАЛОМОЩНОЙ БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ НА БАЗЕ ЕЁ ИМИТАЦИОННОЙ МОДЕЛИ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 2 Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета) Научный руководитель : кандидат...»

«Лапшин Виктор Александрович Математические модели динамики срочной структуры процентных ставок, учитывающие качественные свойства рынка 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена в Московском государственном...»

«Заборовский Никита Владимирович РАСЧЕТНАЯ МОДЕЛЬ ДЛЯ НАХОЖДЕНИЯ СОСТОЯНИЙ ГОНОК В МНОГОПОТОЧНЫХ АЛГОРИТМАХ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва - 2011 Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета) Научный руководитель : доктор физико-математических наук,...»

«Гудков Кирилл Сергеевич МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ УПРАВЛЕНИЯ ОБРАБОТКОЙ ИНФОРМАЦИИ В КОРПОРАТИВНЫХ АВТОМАТИЗИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 Работа выполнена на кафедре управляющих и информационных систем Московского физико-технического института (государственного университета)...»

«Скидин Антон Сергеевич Разработка эффективных методов кодирования для повышения пропускной способности современных линий волоконно-оптической связи Специальность 05.13.17 – Теоретические основы информатики АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Красноярск – 2011 Работа выполнена в Учреждении Российской академии наук Институте вычислительных технологий Сибирского отделения РАН, г. Новосибирск. Научный руководитель : доктор...»

«ЕФИМОВА Ольга Евгеньевна РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ПРОЦЕССА ФОРМИРОВАНИЯ ПРОИЗВОДСТВЕННОЙ ПРОГРАММЫ МУНИЦИПАЛЬНЫХ УНИТАРНЫХ ПРЕДПРИЯТИЙ Специальность 05.13.10 – Управление в социальных и экономических системах АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Воронеж – 2009 Работа выполнена в государственном образовательном учреждении высшего профессионального образования Воронежском государственном архитектурно-строительном университете...»

«Левина Алла Борисовна СПЛАЙН-ВЭЙВЛЕТЫ И ИХ НЕКОТОРЫЕ ПРИМЕНЕНИЯ 05.13.18 математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учной степени е кандидата физико-математических наук Санкт-Петербург 2009 Работа выполнена на кафедре параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета Научный руководитель : доктор...»

«Филиппов Алексей Александрович ФОРМИРОВАНИЕ НАВИГАЦИОННОЙ СТРУКТУРЫ ЭЛЕКТРОННОГО АРХИВА ТЕХНИЧЕСКИХ ДОКУМЕНТОВ НА ОСНОВЕ ОНТОЛОГИЧЕСКИХ МОДЕЛЕЙ Специальность 05.13.12 – Системы автоматизации проектирования (промышленность) Автореферат диссертации на соискание ученой степени кандидата технических наук Ульяновск – 2013 Работа выполнена на кафедре Информационные системы в Ульяновском государственном техническом университете. Научный руководитель : кандидат технических наук,...»

«Тясто Сергей Александрович МОДЕЛИРОВАНИЕ, СТРУКТУРНЫЙ АНАЛИЗ И СИНТЕЗ ТЕХНИЧЕСКИХ СИСТЕМ С ЦЕЛЬ Ю ПОВЫШЕНИЯ ИХ ЭФФЕКТИВНОСТИ Специальность: 05.13.01 – Системный анализ, управление и обработка информации (технические системы) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2012 г Работа выполнена в ФБГОУ ВПО Московском государственном технологическом университете СТАНКИН. Научный руководитель : Симанженков Константин Александрович,...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.