Содержание к диссертации
Введение
Глава 1. Обзор методов автоматизации параллельного программирования 13
1.1. Универсальные параллельные языки высокого уровня .14
1.1.1. Языки, использующие параллелизм поданным .14
1.1.2. Языки, использующие параллелизм по управлению 16
1.1.3. Языки, использующие передачу сообщений ...19
1.2. Использование библиотек 22
1.2.1. Библиотеки унификации доступа 22
1.2.2. Высокоуровневые библиотеки 24
1.3. Функциональное программирование 27
1.4. Алгоритмические шаблоны 30
Заключение 34
Глава 2. Численные модели и автоматизация их программирования 35
2.1. Адаптивный многосеточный метод и особенности его параллельной реализации ...36
2.1.1. Математическая модель и ее дискретизация 36
2.1.2. Проблемы создания параллельной программы 43
2.1.3. Параллельная реализация 44
2.2. Метод частиц в ячейках и особенности его параллельной реализации . 47
2.2.1. Математическая модель и ее дискретизация 48
2.2.2. Проблемы создания параллельной программы 59
2.3. Обобщенная схема программы численного моделирования 61
2.3.1. Пространство моделирования 62
2.3.2. Процесс моделирования 63
2.3.3. Идея распараллеливания 64
2.3.4. Параметризация 65
2.4. Принципы сборочной технологии параллельного программирования 65
2.4.1. Двухуровневая система программирования 66
2.4.2. Динамическая балансировка загрузки 67
2.4.3. Требования к представлению массовых алгоритмов для их параллельной реализации 67
Заключение 68
Глава 3. Задача конструирования программы реализующей численный метод . 69
3.1. Идея генератора 70
3.1.1. Выбор параметров 72
3.1.2. Параметризация 73
3.2. Язык периода генерации 73
3.2.1. Структура программы 76
3.2.2. Структура данных 77
3.2.3. Операторы 82
3.2.4. Макроопределения 86
3.3. Язык описания модели 88
3.3.1. Описание вычислительной системы 92
3.3.2. Описание пространства моделирования 94
3.3.3. Описание вычислительного алгоритма 97
3.3.4. Операторы 98
3.3.5. Сервисные функции 100
Глава 4. Генератор ParaGen и конструирование двух программ численного моделирования 103
4.1. Адаптивный Многосеточный метод 103
4.1.1. Скелетон 104
4.1.2, Пространство моделирования 104
4.1.3. Алгоритм 107
4.1.4. Задание начальных условий, значения по умолчанию 109
4.1.5. Вывод данных 113
4.1.6. Поддержка динамической балансировки загрузки 116
4.1.7. Оценка эффективности . 118
4.2. Метод частиц в ячейках 120
4.2.1. Скелетон 120
4.2.2. Пространство моделирования 120
4.2.3. Алгоритм 124
4.2.4. Вычислительная система 127
4.2.5. Оценка эффективности 127
4.3. ParaGen 128
4.3.1. Использование генератора 129
4.3.2. Обработка ошибок 129
4.3.3. Алгоритм работы генератора . 130
4.4. Интерактивная система визуализации процесса моделирования 132
4.5. Динамическая балансировка загрузки процессорных элементов 132
Заключение 135
Заключение.. 136
Список литературы 137
- Языки, использующие параллелизм по управлению
- Метод частиц в ячейках и особенности его параллельной реализации
- Описание пространства моделирования
- Динамическая балансировка загрузки процессорных элементов
Введение к работе
Диссертационная работа посвящена решению задачи автоматизации создания параллельных программ, реализующих численные модели большого размера, для их выполнения на MGVTO мультикомпьютерах. Предлагаемые алгоритмы распараллеливания Адаптивного Многосеточного метода и метода Час-тиц-в-Ячейках основаны на использовании сборочной технологии программирования.
Актуальность темы. Во многих областях науки, таких как изучение поведения плазмы, горения, моделирование полупроводниковых приборов и аэродинамических конструкций, проведение или повторение физических экспериментов невозможно или очень дорого. Поэтому в настоящее время высокопроизводительные ЭВМ часто используются для моделирования природных явлений и сложных технических устройств.
Такие задачи обычно характеризуются большим объемом данных и вычислений, что требует использования именно параллельных суперкомпьютеров. Однако исследователю, занимающемуся физическим или вычислительным аспектом задачи, далеко не просто написать эффективную параллельную программу моделирования физического явления с использованием общепринятых систем программирования.
В отличие от последовательных, параллельные программы моделирования должны обладать рядом динамических свойств (настраиваемость на имеющиеся ресурсы, динамическая балансировка загрузки, устойчивость к сбоям и т.д.) которые сложно реализовать и отладить. Существующие средства разработки не обеспечивают необходимые свойства параллельной программ автоматически, поэтому задача создания системы автоматического конструирования и динамического реконструирования высококачественных параллельных программ численного моделирования является актуальной.
s Цель работы. Создание технологии параллельного программирования и построение программной системы для решения широкого круга задач численного моделирования на прямоугольных сетках, используя сборочную технологию (СТ) и элементы синтеза программ.
Существует большое количество различных подходов к автоматизации параллельного программирования высокого уровня, которые ранжируются от процедурных языков параллельного программирования до автоматического синтеза параллельных программ и от вспомогательных библиотек до введения явных параллельных операторов и типов данных в язык программирования. Разрабатываемый генератор ParaGen занимает в этом списке некоторое промежуточное положение: в нем есть и элементы синтеза программ, и языковые средства программирования. Разработка базируется на простой прагматической идее многократного использования хорошей, профессионально разработанной программы. Эта идея в общем случае не очень продуктивна, но численные модели, будучи очень разными содержательно, часто бывают очень схожими по управляющей структуре и структурам данных реализующих их программ. По этой причине прикладная программа численного моделирования, после сравнительно небольших, специально спланированных, модификаций может быть применена для решения содержательно совсем не похожей задачи.
Эта идея и эксплуатируется генератором.
Берется хорошая программа численного моделирования. Генератор программ должен быть в состоянии утилизировать эту программу, используя разработанную технику параметризации, быть в состоянии правильно ее модифицировать с тем, чтобы ее можно было применять для решения других, сходных по структуре реализующей программы, задач.
Генератор, используя свою библиотеку процедур и фрагменты кода, специфические для вновь решаемой задачи, которые должен предоставить генератору пользователь, собирает необходимую новую программу.
9 В ходе работы над диссертацией были проанализированы имеющиеся инструменты и подходы к решению проблемы автоматизации параллельного программирования. Было показано, что, используя современное системное программное обеспечение, сложно программировать реальные большие задачи моделирования. Языки низкого уровня (типа "С-н-"+MPI) позволяют создавать хорошие параллельные программы, однако создание и поддержка таких программ является весьма трудоемкой задачей, и требуют высокой квалификации программистов. Конструирование параллельных программ по описанию на языках высокого уровня либо на языках спецификации приводит к неприемлемо низкой эффективности программ. В результате анализа существующих подходов был выбран метод конструирования параллельных программ по проблемно-ориентированным параметризованным шаблонам, сочетающий в себе элементы синтеза программ и процедурные средства описания алгоритма. Для обеспечения параметризации, описания параметров и генерации результирующей программы был разработан язык периода генерации (язык параметризации) и семейство языков описания модели. Для апробации идеи, метода и алгоритмов генерации были разработаны генератор ParaGen и два скелетона для решения задач горения и газодинамики и для решения задач моделирования природных явлений в физике бесстолкновительной плазмы методом частиц-в-ячейках (далее метод частиц). Были проведены численные эксперименты для определения эффективности генерируемых программ.
Научная новизна. Основной отличительной чертой предлагаемой технологии является многократное использование результата труда человека взамен автоматического выявления скрытого параллелизма в последовательной программе. Новыми являются подход к конструированию параллельных программ по шаблону, в котором сочетаются элементы синтеза программ и языковые возможности генератора, что позволяет достичь высокой производительности результирующих программ. Разработаны новые архитектура генератора и алгоритмы его реализации, обеспечивающие высокую производительность гене-
10 рируемых программ, а также гибкость и расширяемость генератора за счет добавления новых скелетонов и численных алгоритмов решения типовых задач.
Практическая ценность. Результаты данной работы внедрены в ИВМиМГ СО РАН, Также результаты работы были использованы при разработке параллельной программы моделирования химико-физических процессов в Институте химических технологий университета Карлсруэ (Германия). Разработанная под руководством автора техника генерации по шаблону может быть использована во многих областях, где для решения больших задач требуется численное моделирование. Данный подход позволяет в короткие сроки создавать параллельную программу моделирования и оперативно реконструировать ее при изменении модели или ее параметров. Кроме того, использование иерархической структуры данных и настраиваемость синтаксиса входного языка генератора позволяют описывать алгоритмическую часть модели в традиционной для предметной области нотации или близко к ней.
Апробация работы. Основные результаты диссертационной работы опубликованы в [76, 90, 92], Результаты докладывались: на "Конференции молодых ученых-2001", Новосибирск, 2001; на ''Конференции молодых ученых-2003", Новосибирск, 2003; на ряде студенческих конференций НГТУ; на научных семинарах отдела МО ВВС Института Вычислительной Математики и Математической Геофизики (бывшего Вычислительного Центра) СО РАН. По теме диссертации автором были прочитаны доклады во время научных командировок в Университет Карлсруэ (Германия).
Гранты. Работа по теме диссертации проводилась в соответствии с планами исследований по проекту, поддержанному грантом РФФИ (проект № 02-01-00864), интеграционному гранту СО РАН 148-2003, а также в рамках международного проекта; French - German - Russian Trilateral Project "Complex Hydrodynamics, Modeling and Process Control".
Личный вклад. Выносимые на защиту результаты получены соискателем лично. В опубликованных совместных работах участие автора заключалось
разработке и исследовании алгоритмов и их программной реализации. Постановка и исследование задач осуществлялось совместными усилиями соавторов при непосредственном участии соискателя. Создание и внедрение прикладных разработок осуществлено соискателем лично.
Публикации. По теме диссертации опубликовано 3 работы.
На защиту выносится метод и алгоритмы конструирования параллельных программ по шаблону на основе декларативного описания пространства моделирования и алгоритма вычислений, метаязык PGML периода генерации для параметризации и описания языка определения параметров, а также семейство языков описания численных моделей для задач реализации PIC (Particle-In-Cell) и AM (Adaptive Multiresolution) методов разработанных соискателем.
Структура и объём работы. Диссертационная работа изложена на 162. странице и состоит их введения, четырех глав, заключения и двух приложений. Иллюстративный материал включает 15 рисунков. Список литературы состоит из 93 наименований.
Содержание работы
Во введении обоснована актуальность темы диссертационной работы, сформулирована цель работы и задачи исследования, приведены основные положения, выносимые на защиту, дано краткое изложение по главам.
В первой главе приводится обзор существующих подходов к решению проблемы автоматизированного создания параллельных программ, изложена сущность ключевых задач создания параллельных программ, выявлены особенности этих задач и проанализированы возможные подходы к их решению.
Во второй главе дана характеристика и основные особенности параллельной реализации численных моделей на примере AM и РІС методов. Выявлены основные структуры данных и вычислений параллельных программ моделирования, реализующих эти методы. На базе анализа сформулирована идея автоматизации создания таких программ методом генерации по шаблону.
12 В основе такой автоматизации лежит сходство моделей с точки зрения реализации, несмотря на различия в физической постановке и используемых математических методов.
В третьей главе рассмотрена задача конструирования программы, реализующей численный метод. Также описаны язык параметризации PGML и семейство языков описания модели.
Задача конструирования параллельной программы моделирования состоит в том, чтобы по последовательному, декларативному описанию численной модели построить эффективную параллельную программу, реализующую эту модель. Для решения этой задачи необходимо выбрать класс моделей, параллельные программы, реализующие которые, обладают схожими структурами данных и управления. Для выбранного класса моделей нужно создать скелетон (параметризованную параллельную программу), в котором все фрагменты, не зависящие от модели, уже содержатся, а содержательные фрагменты, необходимые для реализации конкретной модели, описаны максимально близко к принятой в предметной области или традиционной нотации.
В четвертой главе описывается создание скелетонов параллельных программ для AM и РІС метода, а так же описывается реализация генератора ParaGen.
Реализация и использование генератора ParaGen продемонстрирована на примере разработки скелетонов для метода частиц и многосеточного метода и включения соответствующих скелетонов в ParaGen.
В заключении сформулированы основные результаты работы.
Языки, использующие параллелизм по управлению
В модели параллелизма по данным отсутствует понятие процесса и, как следствие, явная передача сообщений или явная синхронизация. В этой модели данные последовательной программы распределяются программистом по процессорам параллельной машины. Последовательная программа преобразуется компилятором в параллельную программу, при этом вычисления распределяются по правилу собственных вычислений: каждый процессор выполняет только вычисления собственных данных, т.е. данных, распределенных на этот процессор.
Модель параллелизма по данным имеет следующие достоинства. Параллелизм по данным является естественным параллелизмом вычислительных задач, поскольку для них характерно вычисление по одним и тем же формулам множества однотипных величин - элементов массивов.
В модели параллелизма по данным сохраняется последовательный стиль программирования. Программист не должен представлять программу в виде взаимодействующих процессов и заниматься низкоуровневым программированием передач сообщений и синхронизации.
Распределение вычисляемых данных между процессорами - это не только самый компактный способ задать распределение работы между процессорами, но и способ повышения локализации данных. Чем меньше данных требуется процессору для выполнения возложенной на него работы, тем быстрее она будет выполнена (лучше используется кэш-память, меньше подкачек с диска страниц виртуальной памяти, меньше пересылок данных с других процессоров).
Обобщение и стандартизация моделей параллелизма по данным привели к созданию в 1993 году стандарта HPF (High Performance Fortran) - расширения языка Фортран 90. Аналогичные расширения были предложены для языка Си и Си++ [34].
Система ориентирована на модель параллелизма по данным и предназначена как для SMP, так и для MTMD архитектуры. HPF содержит директивы для описания способов разбиения массивов данных и распределения их между параллельно работающими процессорами, а также некоторые средства для явного указания параллельности. HPF - язык высокого уровня. На программиста возлагается в основном ответственность за распределение данных, а представление программы в виде системы взаимодействующих процессов осуществляется компилятором. Для повышения эффективности имеется возможность описать явный интерфейс с процедурами, использующими средства более низкого уровня. HPF (версия 1.0) [47] является расширением Фортрана 90, HPF-2 - расширением фортрана 95 [48].
Как уже было сказано выше, прежде всего программист должен распределить данные между процессорами. Это распределение производится в два этапа. Сначала с помощью директивы ALIGN задается соответствие между взаимным расположением элементов нескольких массивов, а затем вся эта группа массивов с помощью директивы DISTRIBUTE отображается на решетку процессоров. Это отображение, например, может осуществляться следующим образом: каждый массив разрезается несколькими гиперплоскостями на секции примерно одинакового объема, каждая из которых будет расположена на своем процессоре; Заданное распределение данных может быть изменено на этапе выполнения программы с помощью операторов REALIGN и REDISTRIBUTE.
В HPF реализуется параллелизм следующих конструкций языка Фортран 90/95: операции над секциями массивов, DO циклы, оператор и конструкция FORALL. Операции над секциями массивов выполняются параллельно в соответствии с распределением данных. Если для их выполнения требуются коммуникации, то они обеспечиваются компилятором.
Оператор.и конструкция FORALL могут рассматриваться как обобщение и расширение операций над секциями массивов.
Многие встроенные функции имеют дело с массивами (например, редукционные функции) и могут выполняться параллельно.
Безусловно, язык HPF намного упрощает написание параллельных программ, однако его реализация требует от компилятора очень высокого интеллекта. Конечно, самая сложная часть работы, которая вызывала проблемы при автоматическом распараллеливании — распределение данных — возлагается теперь на программиста. Но, и с оставшейся частью работы компилятор не всегда способен справиться без дополнительных подсказок программиста. Некоторые такие подсказки были включены в HPF, но все равно оставались серьезные сомнения относительно эффективности HPF-программ.
К сожалению, эти сомнения оказались не напрасными. В течение нескольких лет так не удалось создать компилятора с приемлемой эффективностью. В 1997 году появился проект стандарта HPF2 [48] , в котором существенно расширены возможности программиста по спецификации тех свойств его программы, извлечь которые автоматически на этапе компиляции очень трудно или даже вообще невозможно. Однако и он остался не реализован в полной мере и не получил распространения.
Модель параллелизма по управлению возникла уже давно как модель программирования для мультипроцессоров. На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему потоков, взаимодействующих посредством общих переменных и примитивов синхронизации. Поток (по-английски "thread") - это легковесный процесс, имеющий с другими потоками общие ресурсы, включая общую оперативную память.
Основная идея языков программирования в модели параллелизма по управлению заключалась в следующем. Вместо программирования в терминах потоков предлагалось расширить языки специальными управляющими конструкциями - параллельными циклами и параллельными секциями. Создание и уничтожение потоков, распределение между ними витков параллельных циклов или параллельных секций (например, вызовов процедур) - все это брал на себя компилятор.
Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта ХЗН5). Однако, этот проект [73] тогда не привлек широкого внимания и, фактически, остался только на бумаге. Возможно, что причиной этого было снижение интереса к мультипроцессорам и всеобщее увлечение мультикомпьютерами и HPF.
Однако спустя несколько лет ситуация сильно изменилась. Во-первых, успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры. Во-вторых, широкое развитие получили мультикомпьютеры с DSM (distributed shared memory - распределенная общая память), позволяющие программам на разных узлах взаимодействовать через общие переменные так же, как и на мультипроцессорах (Convex Exemplar, HP 9000 V-class, SGI Origin 2000). В-третьих, не оправдались надежды на то, что HPF станет фактическим стандартом для разработки вычислительных программ.
Метод частиц в ячейках и особенности его параллельной реализации
Основная проблема состоит в том, сетка на которой определены параметры ПМ, представлена в виде набора деревьев с автоматически поддерживаемыми отношениями соседства. При распределении данных между процессорными элементами (ПЭ) необходимо поддерживать отношения соседства через границы блоков путем создания виртуальных листьев для каждой граничной ячейки на всех уровнях разбиения. Созданные при этом виртуальные ячейки фактически будут копиями ячеек расположенных в соседних блоках (часто в соседних ПЭ). В процессе моделирования необходимо обеспечивать синхронизацию дублируемых ячеек, имеющих сложную структуру.
Другая проблема состоит в том, сетка на которой определены параметры ПМ, меняется в процессе моделирования, в одних областях она становится более грубой, в других измельчается, следуя за изменением фронта реакции. При этом зачастую невозможно заранее предсказать характер этих изменений. При моделировании большая часть вычислений на каждом временном шаге приходится на выполнение расчета потоков "в" и "из" ячеек и шаг Рунге Кутта, и вычислительная загрузка ПЭ главным образом зависит от числа обрабатываемых ячеек. Таким образом, первоначально сбалансированная загрузка ПЭ, в результате изменения сетки, может потерять сбалансированное состояние. Следовательно, управляющая структура параллельной программы и стратегия распределения данных между ПЭ должны динамически меняться в процессе моделирования. Кроме того, необходимо обеспечивать поддержку отношений соседства через границы областей, назначенных на обработку разным процессорам при перераспределении данных.
Для разработки параллельной версии программы Кармен - Кармен-П применялась идея сборочной технологии параллельного программирования [57]. ПМ состоит из множества начальных ячеек (атомарных фрагментов) - базовой сетки, организованного в блок в форме параллелепипеда или нескольких смежных блоков (рис. 2.4). Основная идея распараллеливания программы "Кармен" состоит в том, чтобы запустить вычисления для каждой начальной ячейки базовой сетки одновременно, каждая из ячеек может быть независимо разделена для достижения желаемой точности представления дискретизируе-мых функций, порождая дерево. Однако нельзя использовать процедуры построения дерева последовательной программы без изменений, так как теперь отношения соседства и условия создания виртуальных ячеек затрагивают деревья, порожденные смежными начальными ячейками, что приводит к проблеме склеивания.
В ходе начальной настройки параллельной программы блоки разбиваются в соответствии с числом ПЭ. Каждый блок содержит дополнительный (граничный) слой виртуальных ячеек, значения сеточных переменных которых копируются из смежных блоков в ходе синхронизации или перевычисляются в соответствии с граничными условиями в случае, если граница блока - это граница ГГМ.
Для обеспечения прозрачного распределения данных по процессорным элементам в язык описания алгоритма вычислений ParaLang, который подробно будет описан в главах 3,4, введены параллельные циклы для обхода ячеек, позволяющие описывать вычислительный алгоритм в близкой к последовательной форме. Доступ к переменным сетки осуществляется с помощью специально разработанных процедур для каждой сеточной переменной.
Программа позволяет задавать начальные условия и параметры численных экспериментов унифицированным способом. Начальное состояние ПМ может быть задано при использовании специального подмножества языка С, что позволяет избегать перекомпиляции целевой параллельной программы для каждого эксперимента. Программа содержит унифицированную систему для вывода данных, отладочной и служебной информации, а также информацию о состоянии ПМ в ходе моделирования. Эту дополнительную информацию во время выполнения можно отображать с помощью специальной программы визуализации данных, например VISA.
Параллельная программа достигает высокой скорости выполнения, если все ПЭ загружены одинаково, иначе происходит резкий спад производительности. Загрузка ПЭ главным образом зависит от числа ячеек, назначенных ПЭ для обработки. В ходе моделирования некоторые ячейки делятся, некоторые объединяются, поэтому даже первоначально однородно загруженный мульти-компьютер может накапливать дисбаланс, и через несколько итераций по времени потребуется перебалансировка. Таким образом, структура управления программы и распределение данных среди ПЭ должны динамически изменяться в ходе вычислений.
Комплекс процедур балансировки обеспечивает начальное распределение данных среди ПЭ и динамическую перебалансировку загрузки в ходе вычислений, а также контроль дисбаланса и выбор порога перебалансировки. Информация о загрузке каждого ПЭ собирается параллельно с вычислениями, чтобы уменьшать задержки на межпроцессорные связи.
Для визуализации результатов и контроля процесса моделирования используется специальная программа VISA. Она позволяет контролировать любые параметры модели в процессе вычислений, используя интерфейс файловой системы и унифицированный протокол обмена данными с генерируемой параллельной программой. Такая программа обеспечивает визуализацию результатов немедленно после их получения из программы моделирования, сбор данных от всех ПЭ и преобразование их к известному формату для других программ визуализации. Дополнительно VISA позволяет управлять начальными параметрами численного эксперимента и контролировать процесс вычислений.
Программа Кармен-П обладает всеми необходимыми свойствами параллельной программы: настройкой на имеющиеся ресурсы, обработка адаптивной сетки, динамической балансировкой загрузки и т.д. Кроме того, в результате использования сборочной технологии программа может быть легко параметризована.
Задачи, решаемые AM методом, отличаются большим объемом данных и вычислений, что требует использования параллельных компьютеров. Несмотря на высокую степень внутреннего параллелизма, метод является сложным для эффективной параллельной реализации, так как отличается нерегулярной, динамически изменяющейся структурой данных. Параллельная программа должна настраиваться на непредсказуемо изменяемое распределение данных в процессе моделирования.
Описание пространства моделирования
Для получения обобщенной версии программы моделирования предлагается исключить из исходной программы вычислительные формулы (часть программы, описывающая конкретные вычисления) оставив на его месте заглушки позволяющие генератору затем вставить в эти места код нового метода. Структура программы при этом сохраняется, и пользователь может заполнять образовавшиеся пустоты с помощью специального языка или удобного графического представления. Затем следует определить набор параметров пространства моделирования, в очередной раз, исключив детали и сохранив лишь некую базовую структуру ПМ. Часто в качестве параметров ПМ выступают сеточные переменные, их типы и расположение, возможно размерность и какие-либо физические параметры. И, наконец, учитывая выбранные параметры, следует параметризовать процедуры, зависящие от свойств ПМ, например, процедуры се-риализации/десериализации, распределения памяти, синхронизации и т.п. Таким образом, после проделывания этих шагов для готовой параллельной программы (а возможно строя новый скелетон с нуля) получаем универсальную программу моделирования, покрывающую некоторый класс задач моделирования выбором соответствующих параметров при этом обладая эффективностью изначальной вручную написанной параллельной программы [90].
Итак, процесс построения новой реализации параллельной программы состоит из следующих шагов: Разработка исходной программы. Прежде всего, разрабатывается и отлаживается программа численного моделирования. Численная модель гарантированно должна работать, так как отладка модели при ее параллельной реализации одновременно с отладкой самой программы сильно затруднена. Далее работает профессиональный параллельный программист. Его задача — разобрать последовательную программу на семантические фрагменты, собрать из этих заготовленных фрагментов и вновь разработанных необходимых фрагментов и параллельных управляющих структур параллельную программу, реализующую ту же численную модель. Программа должна разрабатываться с учетом ее дальнейшей параметризации, затем она используется как эталон генератора, так как при выборе соответствующих параметров должна быть сгенерирована в точности исходная параллельная программа. Разработка скелетона. Скелетон - это параметризованная параллельная программа. В нем удалены все фрагменты кода, которые характеризуют конкретную модель, а также разработаны способы описания ПМ и других параметров. Свободные позиции содержат описание кода, который должен быть вставлен для реализации другой модели. Скелетон включается в библиотеку генератора, которая может содержать более одного скелетона. Работа с ParaGen. Теперь может быть сконструирована новая параллельная программа. Сначала конечный пользователь (математик, физик, и т.д.) выбирает подходящий скелетон в библиотеке генератора. Для этого каждый скелетон снабжается описанием класса моделей, для решения которых он подходит. Просматривая свободные позиции скелетона, пользователь вставляет в них фрагменты кода, соответствующие проектируемой задаче. Например, вычисления внутри ячейки сетки обычно не включаются в скелетон. Для решения конкретной задачи пользователь должен дать генератору этот фрагмент кода. Обычно это простой последовательный код. Сгенерированная программа будет обладать всеми необходимыми динамическими свойствами, заложенными в скелетон: быть исполнимой на мультикомпьютерах, настраиваемой на доступные ресурсы, обеспечивать динамическую балансировку загрузки.
Выбор параметров модели определяет степень общности скелетона и является сложным, плохо формализуемым процессом, преследующим две диаметрально противоположные цели. С одной стороны, чем больше параметров у модели и чем меньше запрограммированных частей имеет скелетон, тем шире оказывается класс задач, решаемых скелетоном. Однако с увеличением количества параметров увеличивается общность скелетона и соответственно уменьшается эффективность результирующих программ. В предельном случае порождается универсальный язык программирования, позволяющий решить задачу любого класса. Кроме того, модель с большим числом параметров сложно использовать и отлаживать. С другой стороны, чем меньше параметров имеет модель, тем легче ее использовать и тем эффективнее генерируемая программа. Таким образом, выбор параметров должен ограничиваться разумным обобщением исходной программы, при котором сохраняется ее высокая эффективность и прозрачность схемы пространства моделирования и структуры алгоритма."
Со всей очевидностью можно разделить численную модель на две взаимодополняющие части: пространство моделирования и алгоритм вычислений. Кроме того, параллельная программа может обладать дополнительными свойствами, зависящими в первую очередь от вычислителя. Таким образом, у параллельной программы, реализующей численную модель, можно выделить три группы параметров.
Параметрами пространства моделирования могут быть имена, типы и расположение сеточных переменных при сохранении структуры сетки. Структура сетки является основной ее характеристикой для процедур сохранения, синхронизации, обхода узлов и других вспомогательных процедур (например, регулярная прямоугольная, нерегулярная, иерархическая.,.).
Параметрами алгоритма вычисления являются, наполняющие заданную структуру программы, фрагменты кода, с соответствующим синтаксисом и возможно с некоторыми ограничениями, накладываемыми скелетоном. Дополнительные параметры модели могут помочь генератору выбирать наиболее эффективные вспомогательные процедуры из имеющейся библиотеки, например, процедуры визуализации, балансировки, начального распределения и т.п. При описании расширения языка для конкретной модели ее параметры обычно заносятся в единую структуру данных, а при генерации используются при выборе того или иного алгоритма, как параметры циклов и в выражениях. Процесс параметризации заключается в записи текста исходной параллельной программы в виде программы на специальном языке, исполняя которую генератор создает текст результирующей программы на выбранном процедурном языке программирования (например, C++ + MPI) пригодный для компиляции стандартным компилятором. В процессе параметризации определяется набор параметров, которые используются при генерации результирующей программы, а также определяется способ описания выбранных параметров при описании модели. Параметризованная программа, записанная на специальном языке, называется Скелетон. Описание параметризации исходной программы должно быть близко к непараметризованной форме. При этом язык должен позволять сохранять параметры модели во внутренней структуре данных и иметь все необходимые управляющие конструкции, такие как: условия, циклы и выражения.
Динамическая балансировка загрузки процессорных элементов
Разработанный скелетон позволяет работать с любым количеством сеток (групп сеточных переменных), каждая из которых может иметь сдвиги и перекрытия по выбранным осям независимо от других. Кроме того, каждая сетка может иметь любой арифметический тип допустимый языком C++.
Сеточные переменные (такие как значения электромагнитных полей, средняя плотность тока и т.п.) для одной ячейки определяются с помощью оператора @defgrid. Для каждого типа сеточной переменной вводится уникальное имя. Сеточные значения, определенные внутри описания ячейки, пространственно могут находиться в соседних ячейках ПМ. В частности, если сеточные переменные определены в вершинах ячейки, они будут принадлежать и смежным ячейкам.
В случае, когда для дискретизации различных сеточных переменных используются сдвинутые относительно друг друга сетки, сеточные значения могут иметь локальные координаты, отличные от координат вершин ячейки (рис. 2.6). В том числе переменные могут иметь отрицательные локальные координаты.
При описании сеточных переменных задаются тип, имя и область задания переменных группы. Область задания определяется тройками nl, пс, пг для каждого координатного направления. Для оси OX, nl — количество переменных с отрицательной локальной х-координатой, пс - количество переменных груп-. пы, у которых х-координата ровна нулю, пг - количество переменных группы, у которых х-координата строго больше hx. Аналогично определяются тройки для других координатных направлений. В примере на рис. 2.6 область задания группы переменных Вх есть 0,0,0 , 0,1,0 , 0,1,0 . Раздельное задание nl и пг вводится для того, чтобы возможно было задавать алгоритмы с несимметричными шаблонами.
Размером перекрытия сеточной переменной по какой-либо координатной оси назовем количество слоев сеточных значений этой группы, дублируемых в двух соседних по этому координатному направлению ячейках ПМ. В примере на рис. 2.6 размер перекрытия группы переменных Вх по оси X равен нулю, по осям OY и OZ - двум. Заметим, что размер перекрытия равен nl+nc 2+nr.
В процессе генерации для каждой сеточной переменной создается массив указанного типа и специальная функция вида обеспечивающая доступ к сеточной переменной, в этой функции возможен контроль за выходом индексов за границы расчетной области. Функции доступа к сеточным переменным генерируются как inline и не вносят дополнительных накладных расходов на доступ к сеточным переменным.
Кроме задания параметров ячейки для РІС метода необходимо определить набор частиц. В данной реализации скелетона допускается определение нескольких типов частиц с произвольным количеством параметров. Частицы описываются с помощью оператора defparticle в котором определяются имена и тип координатных переменных (первая группа переменных), а также тип и имена дополнительных параметров частиц:
Так как координаты частиц определены явным образом, скелетон в состоянии самостоятельно отслеживать вылет частиц за пределы расчетной области, и распределение части по процессорам. Следует отметить, что существуют задачи, когда множество всех частиц состоит из нескольких подмножеств. Например, множество ионов и электронов, или множество фоновых частиц (с нулевой начальной скоростью), распределенных в ПМ равномерно и активных частиц (с ненулевой начальной скоростью), сосредоточенных в некоторой области. В таком случае можно описать несколько типов частиц.
В процессе генерации для каждой частицы создается структура (в терминах языка C++), описывающая параметры частицы, набор массивов для хранения частиц и набор функций для добавления, удаления частиц.
Для генерации параллельной программы должны быть задан последовательный алгоритм внутри блока ячеек. Как и в описанном ранее скелетоне алгоритм вычислений фиксирован и состоит из шага инициализации, шага по времени и завершающего шага, описываемые с помощью операторов @initstep, Qtimestep и @f inishstep соответственно.
Численный алгоритм записывается для блока ячеек, причем не допускается выполнение различных веток вычислений в зависимости от результатов сравнения индексных переменных с какими либо константами. Такое ограничение позволяет прозрачно распределять данные по процессорам и освобождает пользователя генератора от ручной синхронизации и проверок, какие границы являются связующими. Для описания вычислений на границах области следует использовать цикл @forall позволяющий естественным образом выделять граничные узлы сетки, цикл не будет выполняться в тех блоках ПМ, в которых указанная грань является связующей со смежным блоком.
В этом примере вычисляются значения сеточной переменной Ez на границе с минимальным значением по оси X. При генерации будет создан следующий текст:
Структура хранения частиц в скелетоне скрыта от пользователя и для работы с частицами предусмотрен специальный цикл по всем частицам - @forall, который позволяет независимо от описания модели использовать различные стратегии хранения частиц в блоке: единый массив, массив слоев, отсортированный массив и т.п. Выбор стратегии позволяет оптимизировать результирующую программу моделирования в зависимости от характера задачи. Пример использования цикла по частицам:
