Разработка приложений в среде ParJava

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Литература
1. Foster I., Kesselman C., Tuecke S. The Anatomy of the Grid: Enabling Scalable Virtual Organizations // International J. of Supercomputer Applications and High Performance Computing. — 2001. — T. 15. — № 3. — Р. 200−222.
2. Радченко Г. И., Соколинский Л. Б. CAEBeans: иерархические системы структурированных проблемно-ориентированных оболочек над инженерными пакетами // Тр. Всерос. науч. конф. «Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ». — Новороссийск, 2007. — C. 54−57.
3. Дорохов В. А., Маковецкий А. Н., Соколинский Л. Б. Разработка проблемно-ориентированной GRID-оболочки для решения задачи овализации труб при закалке // Тр. междунар. науч. конф. «Параллельные вычислительные технологии». — СПб, 2008. — 520 c.
4. Радченко Г. И., Соколинский Л. Б., Шамакина А. В. Разработка компонентно-ориентированных CAEBean-оболочек для пакета ANSYS CFX // Тр. междунар. науч. конф. «Параллельные вычислительные технологии». — СПб, 2008. — C. 438−443.
5. Насибулина Р. С. [и др.] Методы организации программных интерфейсов к инженерным пакетам в среде GPE // Тр. междунар. науч. конф. «Параллельные вычислительные технологии». — СПб, 2008. — C. 537.
Радченко Глеб Игоревич — Южно-Уральский государственный университет,
аспирант, gleb. radchenko@gmail. com
Соколинский Леонид Борисович — Южно-Уральский государственный университет,
д.ф. -м. н, профессор, sokolinsky@acm. org
УДК 519. 685
РАЗРАБОТКА ПРИЛОЖЕНИЙ В СРЕДЕ PARJAVA А. И. Аветисян, В. В. Бабкова, М.Д. Калугин
Статья посвящена вопросам разработки и настройки масштабируемых параллельных программ в рамках интегрированной среды ParJava. Рассмотрены основные трудности разработки и инструменты среды, помогающие их решать.
Ключевые слова: разработка масштабируемых параллельных приложений, высокопродуктивные кластерные вычисления.
Введение
При расчете сложных технологических систем объем вычислений настолько велик, что возникает необходимость в выполнении программ на высокопроизводительных вычислительных системах. Кластеры являются одним из распространенных типов таких систем.
Существует много инструментальных систем, таких как TAU [1] (Университет штата Орегон и Исследовательский центр Juelich из Лос-Аламоса) и Paradyn [2] (Университет штата Висконсин), которые поддерживают реализацию, отладку и доводку параллельных программ. Как правило, эти системы предоставляют программисту наборы таких инструментов для анализа параллельных программ, как профилировщик, трассировщик, инструменты для моделирования работы программы, визуализатор и др. Эти системы являются наборами различных инструментов, нацеленных на поддержку разработки параллельных программ. Однако в них не рассматриваются вопросы организации комплексного использования набора инструментов в рамках единой методологии, позволяющей разрабатывать параллельные программы гарантированного качества с использованием таких инструментов.
В настоящей работе, в отличие от рассмотренных систем, предложена итерационная модель процесса разработки параллельных программ в рамках интегрированной среды ParJava [3]. При этом не только использовались уже реализованные инструменты, но были разработаны новые (поддержка контрольных точек, Омега-тест, выявление возможности распараллеливания без обменов и др.).
Технологический процесс использования среды включает следующие этапы:
1. реализация последовательной версии разрабатываемой программы-
2. оценка максимального потенциально достижимого ускорения по доле последовательных вычислений в программе-
3. обеспечение возможности параллельного выполнения гнезд циклов:
a. исследование гнезд циклов на возможность параллельного выполнения (вычисление вектора направлений и вектора расстояний между итерациями гнезда циклов с помощью Омега-теста) —
b. преобразование гнезд циклов к виду, допускающему параллельное выполнение (устранение зависимостей по данным между итерациями) —
4. распределение данных по узлам вычислительной сети-
5. выбор операций обмена данными-
6. оценка границ области масштабируемости и времени счета на реальных данных-
7. использование механизма контрольных точек в случае необходимости. Инструментальные средства среды ParJava позволяют увязать перечисленные
этапы в единый технологический процесс, обеспечивающий итеративную разработку параллельной программы: если после очередного этапа выясняется невозможность достижения необходимого качества (масштабируемости), следует вернуться на предыдущий этап и скорректировать его результаты. Например, если после этапа 2 выяснится, что минимально возможная доля последовательных вычислений слишком велика, необходимо вернуться на этап 1 и, в связи со сказанным ранее, изменить последовательный алгоритм.
Отметим, что, вообще говоря, итеративная разработка предполагает достаточно большое число итераций, что может привести к большим накладным расходам по времени разработки и ресурсам. Итеративная разработка реальных программ, предлагаемая в данной работе, возможна благодаря тому, что большая часть процесса выполняется на инструментальном компьютере, в том числе за счет использования инструментов, базирующихся на интерпретаторе параллельных программ.
Определение распараллеливаемой части программы
Чтобы получить масштабируемую программу, надо свести к минимуму последовательную часть программы, так как даже небольшая доля последовательных вычислений существенно сокращает область масштабируемости параллельной программы (закон Амдала).
В ParJava реализован инструмент «Профилировщик», на котором вычисляется временной профиль последовательной программы. Временной профиль позволяет оценить потенциально достижимое ускорение.
Цикл распараллеливаем тогда, когда нет зависимостей между итерациями. Зависимость между двумя итерациями возникает тогда, когда они ссылаются на один и тот же элемент массива, причем как минимум одно из них ссылается по записи. Для выявления таких зависимостей в общем случае составляется система уравнений и неравенств относительно индексов и выясняется, имеет ли эта система решения. Уравнения возникают из условия равенства индексных выражений, а неравенства показывают границы изменения индексов, в пределах которых происходят обращения в программе.
Для определения зависимостей существует большое количество тестов. Прямое решение задачи требует значительных временных затрат даже в случае линейных ин-
дексных выражений, так как нахождение зависимостей сводится в итоге к решению системы диофантовых уравнений (или задаче целочисленного линейного программирования), т. е. к NP-полной задаче. Тесты для определения зависимостей можно условно разбить на простые, но не точные, и точные, но сложные. Компромиссным вариантом здесь является Омега-тест, который основан на последовательном применении набора тестов по мере увеличения сложности решения.
Следует отметить, что зависимости могут существовать как внутри одной итерации, так и между итерациями одного цикла. При распараллеливании цикла зависимости внутри итерации мало влияют на вид параллельного алгоритма, тогда как наличие зависимостей между итерациями не позволяет выполнять витки циклов в произвольном порядке, т. е. параллельно на нескольких процессорах.
В среде ParJava зависимости по данным можно проверить при помощи инструмента Loop Analyzer, в который на данный момент включены тесты расстояний и Омега-тест.
Если циклы имеют зависимости между итерациями, существуют способы так их преобразовать, чтобы эти зависимости оказались внутри итераций. Самый надежный и простой способ обойти зависимости — это использование дополнительных буферов для хранения копий массивов, однако он хорош до той поры, пока объем используемой памяти не критичен. Чтобы получить более эффективный вариант программы, применяют композицию примитивных преобразований, которые меняют индексное пространство гнезда циклов [4].
На данный момент в ParJava не реализовано инструментов аффинных преобразований циклов, так как только сам пользователь может определить, в какой последовательности применить эти преобразования, чтобы выявить параллелизм программы. Каждое преобразование гнезда циклов можно выразить через последовательность примитивных аффинных преобразований, каждое из которых соответствует внесению простого изменения в циклы на уровне исходного кода. Существует семь примитивных преобразований, самые значительные из которых — перестановка и скашивание [5]. Если удается так распределить данные по процессорам, что на каждый процессор попадают все данные, которые используются на этом процессоре, то процессоры могут работать независимо друг от друга. В этом случае синхронизации (пересылок данных) не требуется. В ParJava есть инструмент «Независимое распараллеливание», который определяет такие случаи и строит требуемое разбиение массива и его распределение по процессорам, используя известный алгоритм в [6].
Оптимизация пересылки данных в программе
При выполнении большей части программ возникает ситуация, когда данные, вычисляемые на одном процессоре, требуются на другом. В этом случае процессор, использующий данные, требует их у процессора, вычисляющего данные, и возникает не только обмен данными, но и синхронизация. Реализуя синхронизации в программе, необходимо учитывать временные затраты, которые они привносят. Поэтому после определения распараллеливаемого кода в программе возникает вторая проблема — каким образом распараллеливать последовательный код. Это задача оптимального распределения данных и реализации обменов.
Для сокращения времени на моделирование и эксперименты можно реализовать модельный пример программы, сохранив размер последовательной части, размер пересылок и время счета цикла. Такой модельный пример можно быстро переделывать и интерпретировать при помощи инструмента среды ParJava «Интерпретатор», чтобы лучше оценить, какого наибольшего ускорения можно добиться.
Для анализа происходящих в программе пересылок необходимо воспользоваться встроенным в ParJava анализатором трасс. Иллюстрация трасс программы может пока-
зать места разбалансировки и узкие места в программе, что поможет программисту выбрать операции пересылок и их оптимальное расположение в коде.
Рис. 1. Пример использования блокирующих и неблокирующих пересылок
Рис. 2. Получение выигрыша во времени при использовании неблокирующих
коммуникаций
Проиллюстрировать важность оптимального выбора операций пересылок может модельный пример (рис. 1). В программе, обрабатывающей массив данных, заменили блокирующие операции Send и Recv на неблокирующие. Схематично процесс пересылок и счета на временной прямой изображен на рис. 2. Совмещение процесса пересылки и счета центральных точек массива дало возможность получить выигрыш во времени. В результате такой замены можно получить большой рост ускорения всей параллельной программы, что демонстрирует график на рис. 3. Варьируя на модельном примере время счета и время пересылок путем изменения объема пересылаемых данных, можно посмотреть, какого ускорения можно в итоге добиться, а затем перенести изменения на большую программу.
30 25
и 20
Е
а
(D
? 15 ы
о
^ 10
5 0
0 4 8 12 16 20 24 28
процессоры
-ж-блокирующий send
-Я-неблокирующий send
— -и- * Амдалеьа кривая для этой программы
Рис. 3. Сравнение масштабируемости программы с блокирующими и неблокирующими пересылками
Выбрав методы пересылок и реализовав их в настоящей программе, необходимо произвести оценку ее масштабируемости для выбора оптимального количества процессоров. Для этого используется инструмент среды ParJava «Интерпретатор».
Результаты применения ParJava для разработки прикладной программы моделирования интенсивных атмосферных вихрей
Одним из приложений, разработанных в среде ParJava, является параллельная программа моделирования интенсивных атмосферных вихрей (ИАВ), построенная на теории мезомасштабных вихрей по В. Н. Николаевскому (программа разработана в Институте системного программирования РАН в сотрудничестве с Институтом физики Земли РАН) [7, 8]. ИАВ описываются нелинейной системой уравнений смешанного типа, численное решение такой системы в трехмерной сжимаемой сухоадиабатической атмосфере требует очень большого объема вычислений.

J'-
— - у & gt- f f р'- *
V. нт л т — - -г'-
г
1
Было рассчитано несколько вариантов развития торнадо с учетом силы Кориоли-са, в том числе был произведен расчет первых 5 минут развития торнадо, имеющего диаметр 1600 м и высоту 2000 м (он описывался трехмерным массивом размера 320×320×200). На фрагменте кластера МСЦ РАН (64 двухпроцессорных Power 2,2 GHz, 4 GB) вычисления потребовали 96 часов времени счета без учета накладных расходов на организацию контрольных точек. Результаты расчетов подтвердили теорию В .Н. Николаевского и получили признание у специалистов [9].
Заключение
Разработка приложения показала, что среда ParJava обеспечивает быстрое прото-типирование и модификацию параллельных программ, что важно при использовании высокопроизводительных вычислений для расчетов сложных технологических систем. В этом случае после выполнения одной-двух серий вычислений по программе в нее вносятся существенные изменения (по существу, программа полностью изменяется). Среда ParJava позволяет сократить время на проектировании и реализацию эффективной параллельной версии программы на основе исходного последовательного алгоритма. Эта среда активно используется в ИСП РАН, ВЦ им. А. А. Дородницына РАН, МСЦ РАН и в учебном процессе ВМК МГУ и ФУПМ МФТИ.
Литература
1. Shende S., Malony A.D. Integration and Application of the TAU Performance System in Parallel Java Environments // Proceedings of the Joint ACM Java Grande ISCOPE Conference. — June, 2001. — Р. 87−96.
2. Сайт The Paradyn project. — Режим доступа http: //www. paradyn. org/index. html, свободный.
3. Иванников В. П. [и др.] Оценка динамических характеристик параллельной программы на модели // Программирование. — 2006. — № 4. — P. 21−37.
4. Pugh W. The Omega Test: a fast and practical integer programming algorithm for dependence analysis. -ACM, 1991.
5. Bacon D.F., Graham S.L., Sharp O.J. Compiler Transformations for High-Performance Computing // ACM Computing Surveys. — 1994. — Vol. 26. — № 4.
6. Aho A.V. [et al]. Compilers: Principles, Techniques, & amp- Tools. — 2nd ed. — Pearson Education Inc., 2007. — 1000 p.
7. Аветисян А. И., Бабкова В. В., Гайсарян С. С., Губарь А. Ю. Рождение торнадо в теории мезомасштабной турбулентности по Николаевскому. Трехмерная численная модель в ParJava // Математическое моделирование. — 2008. — Т. 20. — № 8.- С. 28−40.
8. Аветисян А. И., Бабкова В. В., Губарь А. Ю Возникновение торнадо: трехмерная численная модель в мезомасштабной теории турбулентности по В. Н. Николаевскому // ДАН. Геофизика. — 2007. — Т. 419. — № 4. — С. 547−552.
9. Avetisyan A.I. [et al]. Intensive Atmospheric Vortices Modeling Using High Performance Cluster Systems // PaCT-2007. — LNCS, 2007. — Р. 487−495.
Аветисян Арутюн Ишханович Бабкова Варвара Вадимовна Калугин Михаил Дмитриевич
Институт системного программирования РАН, ученый секретарь, к.ф. -м.н., arut@ispras. ru Институт системного программирования РАН, м.н.с., barbara@ispras. ru
Институт системного программирования РАН, стажер-исследователь, shaman@ispras. ru

ПоказатьСвернуть
Заполнить форму текущей работой