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

I f ( ! , / / / /

^ V ' / . - -■/

РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение

Институт Вычислительной Математики и Математической Геофизики

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

Краева Марина Анатольевна

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

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

систем и сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор технических наук, профессор В.Э.Малышкин

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

ВВЕДЕНИЕ.................................................................................................................6

ГЛАВА 1 .МЕТОД ЧАСТИЦ В ЯЧЕЙКАХ И ОСОБЕННОСТИ ЕГО ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ.....................................................................14

Введение.................................................................................................................14

1.1 Применение PIC в физике плазмы..............................................................15

1.2 Математическая модель и ее дискретизация.........................................25

1.3 Проблемы создания параллельной программы......................................28

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

ГЛАВА 2.0Б30Р ПАРАЛЛЕЛЬНЫХ РЕАЛИЗАЦИЙ МЕТОДА ЧАСТИЦ В ЯЧЕЙКАХ.............................................................................................................32

Введение.................................................................................................................32

2.1 Две основных стратегии распределения данных между ПЭ...............32

2.2 Иерархическая декомпозиция...................................................................42

2.3 Две реализации PIC на архитектуре гиперкуб........................................43

2.4 Реализация PIC алгоритма на МВК "Сибирь".........................................44

2.5 Реализация на мультитранспьютерной системе...................................46

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

ГЛАВА З.ЗАДАЧА КОНСТРУИРОВАНИЯ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ PIC............................................................................................50

Введение .................................................................................................................50

3.1 Линеаризация массовых алгоритмов и сборочная технология программирования.................................................................................................51

3.1.1 Линеаризация массовых алгоритмов.....................................................51

3.1.2 Отображение алгоритма на ресурсы мулътикомпъютера...............54

3.1.3 Сборочная технология.............................................................................55

3.2 Линеаризация PIC алгоритма....................................................................56

3.3 Выполнение линеаризованного PIC алгоритма на двумерной решетке процессоров............................................................................................59

3.4 Выполнение линеаризованного PIC алгоритма на гиперкубе............61

3.5 Определение атомарного фрагмента вычислений................................62

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

ГЛАВА 4.ДИНАМИЧЕСКАЯ БАЛАНСИРОВКА ЗАГРУЗКИ ПРОЦЕССОРНЫХ ЭЛЕМЕНТОВ......................................................................65

Введение.................................................................................................................65

4.1 Алгоритм начальной балансировки загрузки ПЭ при реализации метода частиц в ячейках на линейке ПЭ.........................................................67

4.2 Централизованный алгоритм динамической балансировки загрузки процессорных элементов при реализации метода частиц в ячейках на линейке ПЭ.............................................................................................................74

4.3 Определение порога разрешенного дисбаланса BP...............................75

-44.4 Балансировка загрузки ПЭ при реализации метода частиц в ячейках

на решетке ПЭ........................................................................................................77

4.5 Использование виртуальных слоев ПМ..................................................78

4.6 Децентрализованный алгоритм динамической балансировки загрузки ПЭ для задач с неизменяемым количеством частиц.....................80

4.7 Специализированный децентрализованный алгоритм........................82

4.8 Диффузионные алгоритмы балансировки загрузки...............................82

4.8.1 Основной диффузионный алгоритм балансировки загрузки...............82

4.8.2 Диффузионный алгоритм балансировки загрузки при реализации PIC метода на линейке процессоров.........................................................................85

4.9 Сравнение работы различных алгоритмов динамической балансировки загрузки ПЭ..................................................................................91

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

ГЛАВА 5.СРЕДСТВА АВТОМАТИЧЕСКОГО КОНСТРУИРОВАНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ PIC МЕТОД.........95

Введение.................................................................................................................95

5.1 Решение двух задач физики плазмы.........................................................97

5.1.1 Расширение облака плотной плазмы в замагниченном фоне.............97

5.1.2 Задача о взаимодействии лазерного импульса с плазмой...................98

5.2 Реализации PIC на ряде мультикомпьютеров в сборочном стиле......99

5.2.1 Реализация PIC для мулътикомпъютера Parsytec PowerXplorer.....100

5.2.2 Реализация на мулътикомпъютере МВС-100.....................................101

5.2.3 Реализация PIC на гиперкубе Intel iPSC/860.......................................102

5.2.4 Использование библиотеки MPI для организации взаимодействия процессов (реализация для мулътикомпъютеров SiliconGraphics Power-Challenge, JBMSP2, Cray J90, Cray ТЗЕ)........................................................103

5.2.5 Реализация динамической балансировки загрузки ПЭ.......................105

5.3 Иерархия классов при реализации PIC на языке С++..........................106

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

5.5 Интерактивная система визуализации процесса сборки параллельной программы..................................................................................115

5.6 Интерактивная система визуализации процесса моделирования ..122 Заключение..........................................................................................................124

ЗАКЛЮЧЕНИЕ.....................................................................................................126

СПИСОК ЛИТЕРАТУРЫ...................................................................................128

ПРИЛОЖЕНИЕ А. ЗАГОЛОВОЧНЫЙ ФАЙЛ ДЛЯ ПРОГРАММЫ, МОДЕЛИРУЮЩЕЙ РАЗЛЕТ ОБЛАКА ПЛАЗМЫ В ЗАМАГНИЧЕННОМ ФОНЕ.......................................................................................................................136

Определение некоторых функций....................................................................139

ВВЕДЕНИЕ

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

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

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

Примером такой задачи является метод частиц в ячейках (Particles-In-Cell method- PIC), который имеет многочисленные приложения в тех областях, где решение проблемы конечно-разностными методами невозможно ввиду ее большой размерности. Несмотря на высокую степень внутреннего параллелизма, метод является сложным для эффективной параллельной реализации, так как отличается нерегулярной, динамически изменяющейся структурой данных. Параллельная программа, реализующая PIC, должна настраиваться на непредсказуемо изменяемое распределение частиц в пространстве в процессе моделирования.

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

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

1) разработаны методы распараллеливания PIC на основе сборочной технологии создания параллельных программ;

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

3) разработаны и реализованы централизованные и децентрализованные алгоритмы динамической балансировки загрузки мультикомпьютера;

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

-85) Разработана параллельная реализация метода частиц в ячейках в применении к решению задачи разлета облака плазмы для мультикомпьютеров Parsytec PowerXplorer, МВС-100, SiliconGraphics Power-Challenge, IBM SP2, Cray J90, Cray T3D, Intel iPSC/860 hypercube. С помощью разработанных программ проведены многочисленные численные эксперименты для изучения

• поведения облака плазмы в замагниченном фоне (при однородном и неоднородном магнитном поле);

• свойств электромагнитного пучка, используемого в лазере при моделировании взаимодействия лазерного импульса с плазмой.

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

Основные результаты диссертационной работы опубликованы в [3-10, 33]. Результаты докладывались на: Международной конференции «Параллельные вычисления и математическое моделирование», РФЯЦ ВНИИЭФ, Саров, 1996; 11-й Всероссийской конференции «Теоретические основы и конструирование численных алгоритмов решения задач математической физики», Пущино, 1996; Международной конференции «High-Performance Computing and Networking», Вена, Австрия, 1997; 6-м Международном семинаре "Распределенная обработка информации" РОИ'98, Новосибирск, 1998; 3-м Сибирском конгрессе INPRIM'98, Новосибирск, 1998; XV Международной школе-семинаре «Информационные технологии в задачах математического моделирования», Новосибирск, 1998; на научных семинарах отдела МО ВВС Института Вычислительной Математики и Математической Геофизики (бывшего Вычислительного Центра) СО РАН.

Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы из 60 названий.

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

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

Однако наличие двух различных типов данных (частиц и вычислительной сетки для задания электромагнитных полей) усложняет создание эффективной параллельной программы. Любая частица в конкретный момент времени связана с близлежащими узлами вычислительной сетки. Закон распределения частиц в пространстве моделирования зависит от конкретной задачи и не описывается исходными уравнениями. Более того, частицы изменяют свое местоположение в процессе моделирования. Для того, чтобы создать эффективную параллельную программу, реализующую PIC, необходимо учитывать непредсказуемо изменяемое распределение частиц в пространстве в процессе моделирования.

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

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

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

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

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

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

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

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

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

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

алгоритмов. Выбор алгоритма динамической балансировки при реализации PIC метода зависит от параметров вычислительной системы.

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

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

Используя идею сборки программы из ато�