WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |
Российская академия наук

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

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

УДК 519.685 Бабкова Варвара Вадимовна МЕТОДОЛОГИЯ ПОДДЕРЖКИ РАЗРАБОТКИ ЭФФЕКТИВНЫХ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

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

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

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

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

Защита диссертации состоится « 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, 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, • V Всероссийская межвузовская конференция молодых ученых, г. СанктПетербург, 15-18 апреля 2008 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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». Во многих случаях проблему удается решить при помощи сравнительно простых преобразований: изменение порядка циклов в гнезде, слияние и расщепление циклов, замена индекса и др.

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»