Содержание к диссертации
Введение
I. Методы декомпозиции и параллельные вычисления 16
1.1. Метод разрывания 16
1.2. Методы декомпозиции области для аппроксимированных задач 18
1.2.1. Методы Шварца 21
1.2.2. Метод декомпозиции, основанный на механическом взаимодействии подструктур 24
1.2.3. Многофронтальный метод 25
1.3. Методы подструктур 32
1.3.1. Вычислительные схемы . 35
1.3.2. Двухуровневая декомпозиция в методах подструктур 39
1.3.3. Иерархия подструктур 45
1.4. Параллельные проекционные методы на подпространствах Крылова 48
1.4.1. Метод сопряженных градиентов 51
1.4.2. Сокращение числа обменов 52
1.4.3. Блочная декомпозиция 53
1.4.4. Поэлементная декомпозиция 56
1.4.5. Реберная декомпозиция 62
1.4.6. Совмещение вычислений и обменов 64
1.5. Проектирование параллельных алгоритмов и программ . 65
1.5.1. Декомпозиция 67
1.5.2. Выбор промежуточного программного обеспечения 71
1.5.3. Разделение/распределение/увеличение вычислительной нагрузки процессоров 72
II. Объектно-ориентированная декомпозиция в методе конечных элементов и методе декомпозиции области 75
2.1. Объектно-ориентированное программирование 78
2.1.1. Объектно-ориентированное проектирование 79
2.1.2. Объектно-ориентированная реализация 81
2.2. Объектно-ориентированный подход к геометрии и расчет ным сеткам 82
2.2.1. Модель САЕ-системы 84
2.2.2. Модель геометрического представления 86
2.2.3. Модель конечно-элементной сетки 88
2.2.4. Модель расчетных данных 91
2.2.5. Модель разделенной сетки 94
2.2.6. Модель распределенной сетки 97
2.3. Объектная модель метода конечных элементов 101
2.3.1. Основные шаги и уровни абстракции данных в методе конечных элементов 102
2.3.2. Сравнение программных моделей метода конечных элементов 103
2.3.3. Трехуровневая объектно-ориентированная модель метода конечных элементов 108
2.3.4. Объектная модель адаптивного метода конечных элементов 111
2.4. Объектная модель метода декомпозиции области 115
2.4.1, Метод декомпозиции области, основанный на конечно-
элементной аппроксимации 117
2.4.2. Построение моделей метода декомпозиции области . 118
III. Модель параллельной распределенной системы метода декомпозиции области 123
3.1. Промежуточное программное обеспечение высокопроизво дительных вычислений 123
3.1.1. Параллельные вычисления 125
3.1.2. Распределенные вычисления 128
3.1.3. Сравнение технологий МРІ и CORBA 130
3.2. Вычислительная модель метода декомпозиции области . 134
3.2.1. Распределенные данные 135
3.2.2. Параллельные процессы 135
3.2.3. Балансировка нагрузки 135
3.3. МРІ-реализация метода декомпозиции 136
3.3.1. Реализация объектов в МРІ 136
3.3.2. Распределенные данные . 137
3.3.3. Параллельные процессы 139
3.3.4. Использование прикладных MPI-бйблиотек 141
3.4. CORBA-реализация метода декомпозиции 141
3.4.1. Реализация объектов в CORBA 141
3.4.2. Распределенные данные 143
3.4.3. Параллельные процессы 144
3.5. Технология параллельных распределенных компонентов . 147
3.5.1. Компонентная система 148
3.5.2. Распределенная компонентная система 149
3.5.3. Параллельная компонентная система 150
3.5.4. Интеграция МРІ и CORBA 151
3.5.5. Реализация метода декомпозиции области на основе технологии параллельных распределенных компонентов 152
IV. Балансировка вычислительной нагрузки и разделение конечно-элементной сетки 156
4.1. Технологии балансировки нагрузки 158
4.1.1. Балансировка на уровне сети 159
4.1.2. Балансировка на уровне операционной системы . 160
4.1.3. Балансировка на уровне промежуточного программного обеспечения 162
4.2. Балансировка на уровне пользовательского приложения . 175
4.2.1. Постановка задачи 176
4.2.2. Методы балансировки для сеточных задач 179
4.2.3. Алгоритмы разделения графов 184
4.2.4. Динамическая балансировка нагрузки и перераспределение 190
4.3. Сравнение методов балансировки нагрузки 195
4.3.1. Балансировка нагрузки на уровне операционной системы и промежуточного программного обеспечения 196
4.3.2. Балансировка нагрузки на основе моделируемого отжига. Моделирование роста зерен 199
4.3.3. Балансировка нагрузки в случае адаптивных сеток 209
4.4. Разделение расчетных сеток для неоднородных многопро цессорных вычислительных систем 214
Численные примеры решения задач на основе методов декомпозиции 221
5.1. Параллельное построение неструктурированных сеток . 221
5.1.1. Методы параллельного построения 223
5.1.2. Метод сжатия текущей границы 228
5.1.3. Триангуляция Делоне с ограничениями на плоскости 229
5.1.4. Построение трехмерной сетки многогранников Вороного 237
5.1.5. Разбиение на шестигранные элементы произвольной области 241
5.2. Поэлементная декомпозиция задач на адаптивных сетках . 244
5.2.1. h-версия метода конечных элементов 247
5.2.2. Оценка погрешности и критерий адаптации 248
5.2.3. Адаптивное перестроение сетки 254
5.2.4. Декомпозиция алгоритма и разделение сетки . 263
5.2.5. Численные примеры решения двумерных задач . 265
5.2.6. Структура вычислительных затрат адаптивного алгоритма 279
5.3. Метод декомпозиции р-версии метода конечных элементов 281
5.3.1. Иерархические аппроксимации для шестигранных элементов 281
5.3.2. Адаптивное р-перестроение и оценка погрешности для элементов высокого порядка 292
5.3.3. Методы декомпозиции для вложенных систем . 295
5.3.4. Критерии разделения с адаптивным порядком аппроксимации 303
5.3.5. Примеры решения задач деформирования р-версией метода конечных элементов 306
5.4. Конечно-элементное моделирование нелинейного деформи рования зарядов РДТТ 311
5.4.1. Выбор определяющих соотношений 315
5.4.2. Адаптация сетки для задач с историей деформирования. r-версия метода конечных элементов 318
5.4.3. Параллельное решение нелинейных систем 325
5.4.4. Моделирование процессов деформирования зарядов при немонотонном нагружении 332
5.5. Методы декомпозиции молекулярно-динамических моделей деформирования полимеров 340
5.5.1. Описание модельной системы 343
5.5.2. Схема интегрирования уравнений движения . 344
5.5.3. Вычисление напряжений для ансамбля частиц . 347
5.5.4. Методы декомпозиции молекулярно-динамических моделей 349
5.5.5. Молекулярнс-динамическое моделирование циклического нагружения 354
5.5.6. Молекулярнс-динамическое моделирование объемного модуля упругости 356
5.6. Многомасштабная декомпозиция систем уравнений метода конечных элементов 359
5.6.1. Многомасштабный анализ 360
5.6.2. Алгоритмические особенности вейвлет-преобразованияЗбб
5.6.3. Определение эффективных модулей упругости . 368
Заключение 373
Список литературы
- Метод декомпозиции, основанный на механическом взаимодействии подструктур
- Объектно-ориентированный подход к геометрии и расчет ным сеткам
- Вычислительная модель метода декомпозиции области
- Балансировка на уровне операционной системы
Введение к работе
"Диссертация посвящена разработке современных вычислительных технологий на основе методов декомпозиции и параллельного распределенного промежуточного и прикладного программного обеспечения для адаптивных версий метода конечных элементов.
Под методами декомпозиции далее понимается совокупность методов и алгоритмов для эффективного параллельного решения задач вычислительной механики, включающих в себя: функциональную декомпозицию методов решения; декомпозицию матричногвекторных вычислений; разделение и распределение вычислительной области/сетки/нагрузки; декомпозицию программного кода.
Под параллельными распределенными технологиями здесь понимается последовательность вычислительных алгоритмов, структур распределенных данных и программных реализаций для решения вычислительных задач адаптивным методом конечных элементов на многопроцессорных системах.
Актуальность темы. В настоящее время параллельные вычисления реализуются не только на суперкомпьютерах, но и на многопроцессорных рабочих станциях, двухпроцессорных или многоядерных однопроцессорных персональных компьютерах и вычислительных сетях.
Параллельные вычислительные алгоритмы и их программная реализация должны обладать рядом новых свойств, связанных с обеспечением изменяемого поведения математической модели, адаптивного обеспечения точности вычислений, динамической балансировкой нагрузки процессоров, непрерывной настройкой на доступные вычислительные ресурсы и т.д.
Для минимизации объема вычислительной работы при решении различных дискретных задач, возникающих в рамках МКЭ, в последнее время широко применяются адаптивные итерационные процессы. Сейчас уже общепризнано, что эффективное решение современных прикладных задач практически неосуществимо без использования того или иного адаптивного процесса.
Главные подходы управления адаптивным процессом, предназначенным для уменьшения погрешности МКЭ, следующие: движение узлов сетки без изменения связности (r-версии); локальное сгущение (перестроение) начальной сетки (h-eepcuu); повышение степени кусочно-полиномиальных базисных функций МКЭ (р-версии) и их комбинации.
Использование адаптивных методов конечных элементов неразрывно связано с декомпозицией расчетной области. Основные достоинства адаптивных версии МКЭ реализуется только при наличии быстрых алгоритмов решения соответствующих систем алгебраических уравнений. Среди экономичных алгоритмов наиболее приспособленным к системам МКЭ является метод декомпозиции области (МДО).
Эффективное распараллеливание адаптивных версий МКЭ предполагает параллельное выполнение каждого из этапов решения задачи: построение начальной сетки и ее разделение; параллельное формирование и решение системы уравнений, оценка погрешности, перестроение сетки над данными, распределенными по процессорам параллельной МВС. Локальное уточнение сеточной модели приводит к разбалансировке вычислительной нагрузки, для устранения которой требуется динамически перераспределять сеточные данные. В связи с этим условия и обеспечение сбалансированности загрузки процессоров является наиболее важным моментом в параллельных методах декомпозиции для задач с адаптивным уточнением.
Весьма важным в рамках данной проблемы является и вопрос создания программного обеспечения для реализации адаптивного применения МКЭ при решении больших реальных задач. Однако, увеличение производительности за счет параллельных вычислений существенно усложняет программирование, увеличивает время разработки программного обеспечения и требует специальных знаний. Добиться масштабируемости — увеличения производительности с ростом числа процессоров — становится таким же важным параметром программного обеспечения, как и переносимость.
Разработка программных комплексов для проведения крупномасштабных вычислительных экспериментов на параллельных вычислительных системах представляет собой сложную в теоретическом и практическом плане задачу. Очевидно, что разработка параллельных программных систем практического уровня сложности представляет собой многоступен чатый технологический процесс. Под технологией программирования, подразумеваются все этапы разработки параллельной программы, начиная с анализа и декомпозиции задачи на параллельные процессы и заканчивая вопросами анализа производительности и организации вычислительного эксперимента.
На сегодня не вызывает сомнений, что важным обстоятельством при осуществлении декомпозиции алгоритма и программы является необходимость ее проведения путем совместного анализа всех аспектов междисциплинарного построения параллельных алгоритмов, а именно: собственно прикладной задачи; математических моделей и методов; теоретического анализа по построению новых вычислительных алгоритмов, адаптации существующих алгоритмов; объектно-ориентированной технологии проектирования и программирования; архитектуры вычислительной системы.
Значительное влияние на выработку единой формулировки методов декомпозиции для адаптивных версий МКЭ, применяемой в диссертации, оказали своими трудами следующие ученые О. С. Zienkiewicz, I. Babuska, А.Д. Ляшко, Г. И. Марчук, J. Т. Oden (теория и конструирование конечно-элементных аппроксимаций); С.Г. Михлин, Л.А. Оганесян, СИ. Репин, Е. Stein (априорные и апостериорные оценки погрешности); С. А. Иваненко, В. Д. Лисейкин, В.И. Мажукин, А. Ф. Сидоров, В. Ф. Тишкин, А. В. Фонарев (адаптивные сетки); П.Н. Вабишевич, В.Г. Корнеев, Ю.А. Кузнецов, В.И. Лебедев, Б.Н. Четверушкин, С. Farhat, О. Widlund (методы декомпозиции области); В.В. Воеводин, А.А. Самарский, С. Т. Kelley, Н. van der Vorst (методы решения систем линейных и нелинейных алгебраических уравнений); О.М. Белоцерковский, А.В. Забродин, Б.Н. Четверушкин (прикладные программные системы для вычислительной физики и математики с применением многопроцессорных ЭВМ); М.Ю. Альес, Ю.П. Зезин, В.П. Матвеенко, В.В. Мошев, П. В. Трусов, R. J. Farris (модели и методы решения прикладных задач деформирования вязкоупругих материалов) и др.
Цель и задачи работы состоят в разработке современных вычислительных технологий на основе методов декомпозиции области (МДО) и параллельного распределенного промежуточного и прикладного про граммного обеспечения для адаптивных версий метода конечных элементов. Данный работа направлена на усовершенствование ряда известных алгоритмов МДО и разработку новых высокоэффективных, ускорение скорости его сходимости и сокращение объема вычислительной работы в целом, значительное повышение степени распараллеливаемости вычислений всех шагов процесса адаптивного решения задач.
Научная новизна. Построены новые алгоритмы адаптивного МКЭ, которые включают параллельные алгоритмы: формирования и решения систем нелинейных и линейных уравнений, апостериорной оценки погрешности, локального перестроения сетки/повышения порядка аппроксимации элементов и динамической балансировки вычислительной нагрузки.
Предложены и обоснованы алгоритмы параллельной генерации больших треугольных и трехмерных неструктурированных расчетных сеток на основе разделения геометрии и грубой сетки. Построены новые параллельные алгоритмы перестроения сетки на основе деления элементов по наибольшей стороне и "новейшему узлу".
Построены и исследованы новые алгоритмы декомпозиции с выделением крупноблочного параллелизма (итерационные методы подструктур с числом подобластей большим, чем процессоров), неявные методы декомпозиции, для которых распараллеливание отражает среднезернистость вычислений (блочные матрицы, хранящиеся без нулевых элементов) и мелкозернистость вычислений (уровень отдельных ячеек сетки, элементная схема метода сопряженных и бисоиряженных градиентов с сокращением числа обменов на каждой итерации и совмещением обменов и вычислений).
Предложены и исследованы методы разделения расчетной сетки, динамической балансировки вычислительной нагрузки и перераспределения сеточных объектов для адаптивных схем МКЭ на основе геометрических и графовых моделей расчетной сетки и неоднородной вычислительной системы.
Разработаны вычислительные технологии, которые обеспечивают разработку, реализацию и запуск прикладных расчетных задач метода конечных элементов и метода декомпозиции области. В основе программного комплекса лежат параллельные распределенные объектно-ориентированные модели расчетной сетки, метода конечных элементов и метода декомпозиции области, созданные с помощью технологии параллельных распределенных компонентов. В параллельной модели реализованы классы, обеспечивающие асинхронный вызов методов удаленных объектов класса "подобласть", и модифицирована модель решения, связанная с разделенной областью.
Проведены численные исследования методов декомпозиции и адаптивных версий МКЭ для модельных и прикладных задач: упругого деформирования композиционных материалов и определения осредненных характеристик, циклического нагружения конструкций из нелинейного вяз-коупругого материала, нормального роста зерен поликристаллического материала, молекулярно-динамического моделирования полимеров.
Обоснованность и достоверность результатов следует из аппрок-симационных свойств конечно-элементных пространств, теории итерационных алгоритмов, матричного анализа, корректности постановок задач, выбора адекватных математических моделей для рассматриваемых классов задач и подтверждается всесторонним тестированием численных алгоритмов и хорошим совпадением полученных результатов с теоретическими оценками, расчетными и экспериментальными результатами других авторов.
Теоретическая и практическая ценность работы состоят в том, что разработанные вычислительные технологии позволяют реально автоматизировать процесс построения расчетных моделей и параллельного их выполнения на многопроцессорных системах.
Апробация работы. Основные результаты диссертации докладывались: на Всесоюзных и Всероссийских конференциях по динамике и прочности ракетных комплексов (Челябинск, 1987), по реологии и оптимизации процессов переработки полимеров (Ижевск, 1989), по численным методам механики сплошной среды (Абрау-Дюрсо, 1992 ), зимних школах по механике сплошной среды (Пермь, 1995, 1997), по численным методам решения задач теории упругости и пластичности (Волгоград, 1995), по математическому моделированию для решения задач в науке и технике, (Ижевск, 1996, 1998), по теории сеточных методов для нели нейных краевых задач (Казань, 1996, 1999, 2001, 2003, 2005), по современным проблемам математического моделирования (Абрау-Дюрсо 1997, 1999), по проблемам построения сеток для решения задач математической физики и теоретическим основам и конструирования численных алгоритмов для решения задач математической физики (Пущино, 2000), по высокопроизводительным вычислениям и их приложениям (Черноголовка, 2000), съезде по теоретической и прикладной механике (Пермь, 2001), по построению расчетных сеток (Москва, 2002, 2004), по методам и средствам обработки информации (Москва, 2003), по параллельным вычислениям (Томск, 2005), на международных конференциях по горению 1СОС(93) (Москва, 1993), по конечно-элементным аппроксимациям OFEA-1995, 2001: Optimization Of Finite Element Approximations, (С.-Петербург, 1995, 2001), по математическому моделированию (Дубна, 2002), по итерационным методам и матричным вычислениям (Ростов-на-Дону, 2002), по суперЭВМ и многопроцессорным вычислительным системам (Таганрог, 2002), по методам декомпозиции области: Domain Decomposition Method (Berlin, 2003), параллельной вычислительной гидродинамике: ParCFD (Москва, 2003), по вычислительной механике и современным программным системам (Москва, 2001, Алушта, 2005).
Публикации результатов и личный вклад автора. По теме диссертации опубликовано 52 работы. В совместных работах постановки задач, аналитические выкладки, разработка и реализация вычислительных алгоритмов, интерпретация полученных результатов, включенные в диссертацию, принадлежат автору.
Структура и объем работы. Работа состоит из введения, пяти глав, заключения, списка литературы и содержит 32 таблицы, 203 рисунка. Объем диссертации 404 страницы. Библиографический список включает 274 наименования.
В первой главе рассматривается ряд способов распараллеливания методов решения прикладных задач, связанных с различными видами декомпозиции полной задачи на ряд одновременно выполняемых подзадач: многофронтальный метод, метод декомпозиции, основанный на механическом взаимодействии подобластей, методы подструктур. Анализируется несколько формулировок методов декомпозиции для выделения их общих и специфических операций.
Во второй главе проведен объектно-ориентированный анализ метода конечных элементов и метода декомпозиции области, определены их основные шаги и абстракции данных, которые должны быть отражены в программных моделях. Проанализированы существующие объектно-ориентированные модели этих методов, выделены классы, которые целесообразно использовать для обеспечения гибкости. Построена новая трехуровневая объектно-ориентированная модель метода конечных элементов, которая затем использована при создании модели метода декомпозиции области.
В третьей главе предметом рассмотрения являются различные способы параллельной распределенной реализации объектной модели метода декомпозиции области с помощью технологий MPI и CORBA. Предлагается технология параллельных распределенных компонентов, основанная на компонентной модели CORBA, технологии асинхронного вызова методов AMI, инкапсуляции МР1-ириложений.
В четвертой главе выделяются несколько подходов для достижения балансирования загрузки процессоров для отдельного параллельного приложения. Сравниваются стратегии динамической балансировки нагрузки.
Пятая глава посвящена обсуждению различных вопросов применения методов декомпозиции для решения краевых задач как с точки зрения постановок сеточных задач, так и с точки зрения методов их параллельного решения и результатов расчетов с использованием адаптивных версий МКЭ. Рассматриваются различные варианты декомпозиции и алгоритмы разделения сеточных задач.
Метод декомпозиции, основанный на механическом взаимодействии подструктур
В ряде случаев физические представления позволяют осуществить декомпозицию области и сократить за счет этого размерность задачи. Так, используемый в механике деформируемого твердого тела(МДТТ) принцип Сен-Венана, кинематические и силовые гипотезы могут трактоваться как основа для построения комбинированных методов. Физические представления должны быть использованы при анализе и применении различных методов декомпозиции. Примером может служить диакоптика [1].
По существу большинство практических задач являются, контактными и лишь возможность внесения тех или иных упрощающих предположений позволяет перейти к классическим граничным условиям в перемещениях или напряжениях. Вторая особенность контактных задач состоит в том, что область контакта неизвестна, определяется в процессе решения задачи и является серьезным препятствием для численного решения этих задач и до конца не преодолена и в настоящее время.
Рассматриваемый метод основан на разъединении (декомпозиции) контактирующих тел и рассмотрении их отдельно [25]. Основные системы уравнений образуются путем введения различных способов или удаления связей в конструкциях(подобластях).
Этот подход применим к решению задач на основе декомпозиции контактирующих тел, а методы, базирующиеся на нем, определим как методы декомпозиции контактирующих тел. Для решения задачи выполняется итерационная процедура, основанная на независимом решении обычных задач в подобластях (линейных или нелинейных) с последовательным удовлетворением кинематических и силовых условий контактного взаимодействия (линейных или нелинейных).
Задавая те или иные условия на контактных поверхностях можно получить: 1. Метод распараллеливания решения краевых задач теории упругости с выделением вспомогательных границ при условии идеального контакта на них, т.е. в качестве кинематических условий на границе используются условия взаимного непроникновения, а в качестве силовых — от-сутвие взаимодействия по касательной к границе. Вспомогательные границы определяются из условий эффективного параллельного решения. 2. Метод решения контактных задач с условиями отслоения (односторонний контакт) на тех границах, где возможно отслоение при взаимодействии тел. Здесь указанные условия уже имеют вид равенств и неравенств, при этом не требуется априорного задания площадки контакта. Перемещения границ взаимодействия должны удовлетворять условиям непроникновения тел. Кроме того, считается, что участки нагружения контакта свободны от напряжений. Взаимное скольжение границ исключено.
Вспомогательные границы определяются из условий балансировки нагрузки, т.е. используются стандартные методы разделения. Итерационная процедура будет выполняться до тех пор, пока на границе взаимодействия не будут удовлетворены контактные кинематические и силовые условия. Другой вариант связан с разделением обоих контактирующих тел на равные части и их независимом размещении на МВС.
При наличии универсальной программы, позволяющей при помощи МКЭ решать задачи для отдельного тела, такой подход позволяет углубить стандартизацию алгоритмов декомпозиции составных конструкций, исключить из алгоритма шаги построения и решения уравнений допол-нолнительных систем, вытекающих из условий сопряжения подобластей, снизить требования к оперативной памяти.
Важным моментом при применении классических итерационных методов к МКЭ, является возможность не хранить полностью, собранную матрицу жесткости, а использовать отдельные элементные матрицы. Это позволяет сократить затраты, которые потребовались бы для формирования глобальной матрицы, а также оперативной памяти, которая требуется для ее хранения. Как уже отмечалось, обработка каждой элементной матрицы может происходить относительно независимо, что дает большие возможности для распараллеливания итерационных методов. Однако, тут же следует отметить и ряд особенностей итерационных методов. Дело в том, что скорость сходимости итерационных методов зависит от числа обусловленности матрицы А. Поэтому, для плохо обусловленной системы требуется построение так называемого предобуславливателя — дополнительной матрицы, умножение на которую уменьшает число обусловленности исходной матрицы системы. Однако, само построение такой матрицы достаточно сложный процесс и для матриц, хранящихся поэлементно, составляет непростую задачу.
При использовании прямых методов, как правило, исходная система уравнений разбивается на несколько более простых систем. Такое разбиение достигается путем разложения матрицы А на сомножители-матрицы простого вида. В основном алгоритмы факторизации основываются на исключении Гаусса, а сомножители-матрицы имеют треугольный или диагональный вид. В общем случае прямые методы распараллеливаются гораздо хуже, чем итерационные.
Рассмотрим фронтальный метод, являющийся модификацией метода Гаусса. Факторизация матрицы проводится как последовательность факторизации и исключений плотных подматриц, называемых фронтальными. Метод часто используется для решения систем в МКЭ, но может быть применен и для решения систем общего вида [26].
Объектно-ориентированный подход к геометрии и расчет ным сеткам
При программировании задач, решаемых на неструктурированных сетках, приходится создавать достаточно сложные структуры данных для представления как самой сетки, так и расчетных данных, связанных с ней. Зачастую структуры данных одной программы практически невозможно повторно использовать в другой и требуется заново разрабатывать аналогичный код. Ситуация заметно усложняется при переходе к параллельному программированию на многопроцессорных ВС. Данный раздел посвящен созданию общего представления неструктурированной расчетной сетки в виде объектно-ориентированной программной модели, которая предназначена для параллельных распределенных вычислений в МДО.
В области решения задач конечно-элементного анализа основной проблемой является приведение геометрической модели к расчетной. Сначала по геометрическому описанию тела необходимо построить конечно-элементную сетку, затем нужно доставить расчетные условия и разделить сетку для параллельных распределенных вычислений. Все эти этапы требуется визуализировать. Кроме того, все больше задач моделироваг ния требуют прямого обращения к геометрическим ядрам и функциям из пользовательского параллельного распределенного приложения. В задачах большой размерности также резко возрастает вероятность появления ошибки в исходных данных.
Классический подход для решения уравнений на ЭВМ с массивно параллельной архитектурой основан главным образом на рассмотренных ранее приемах: декомпозиции данных (расчетная область делится на приблизительно равные по числу конечных элементов подобласти, количество которых равно числу процессоров); функциональной декомпозиции, где явное описание геометрических границ имеет определяющие значение (например, решение сопряженных задач).
Поэтому актуальным является построение САЕ системы, включающей в себя кроме обычных функций ряд специфических: подготовка и работа с распределенными данными; дополнительные функции проверки правильности введенных данных; оптимальная передача и визуализация больших объемов данных с возможностью фильтрации ненужной в данный момент информации и др. Это должен быть открытый редактор расчетных моделей, взаимодействующий с системой геометрического моделирования, содержащий различные генераторы и методы перестроения сеток, алгоритмы разделения сеток, а также обеспечивающий задание расчетных данных.
К сожалению, сравнительный анализ внутреннего построения CAD/-САЕ систем затруднен из-за отсутствия публикаций, поэтому на основе внешнего (пользовательского) анализа ряда САЕ систем и общим требованиям к ним [45-47], была разработана структура визуального редактора FEStudio [48-51]. В табл. 2.1, 2.2 отображены логическая и компонентная составляющие визуального редактора, а также перечислены некоторые свойства отдельных компонентов. Деление на уровни отражает принцип декомпозиции сложных задач на более простые компоненты. Каждый уровень допускает ортогональное наращивание функциональности в границах уровней, представляя модули, реализующие новые решения.
Структура визуального редактора представлена логическими составляющими: геометрия, базовая сетка, расчетные данные, разделенная и распределенная сетка. Каждая составляющая содержит компоненты обработки данных, 00 моделирования и визуализации. Модель геометрии определяет базовый уровень, каждый следующий логический уровень зависит от всех предыдущих. Компоненты 00 моделирования являются ядром, на основе которого реализуются компоненты обработки данных и визуализации, поэтому далее основное внимание уделяется вопросам построения 00 моделей геометрии, сеток и расчетных данных, разделенной и распределенной сеток.
За основу геометрической модели выбрана открытая платформонеза-висимая система геометрического моделирования Open CASCADE [52]. Открытая CASE система Open CASCADE предназначена для создания CAD и САЕ комплексов. Она состоит из библиотек 00 компонентов С-Г-+, отвечающих за создание и отображение с помощью окна просмотра, основанного на OpenGL, геометрических моделей плоских и объемных объектов, выполнение различных операций над ними и установку связей между объектами, сохранение данных и обмен данными в стандартных форматах (STEP, IGES, STL).
Open CASCADE предоставляет разработчикам свободный доступ к кодам исходных текстов десятков структур данных ЗО-геометрии — от объемных примитивов до сложного поверхностного моделирования — и включает сотни алгоритмов моделирования (булевы операции, удаление невидимых линий, сглаживание и снятие фасок). В САЕ системе FEStudio уровень геометрии состоит из компонентов Open CASCADE (рис. 2.2). Дополнительно реализована 00 модель воксельного представления, предназначенная для моделирования сверхсложных геометрических тел.
К модели геометрии предъявляются следующие требования: прежде всего — это импорт/экспорт стандартных геометрических файлов, поскольку мы не пишем свою CAD систему, а используем модели, построенные в других средствах геометрического моделирования с учетом всех особенностей, заданных конструктором. В связи с этим необходимо, чтобы объектно-ориентированная модель позволяла использовать геометрические модели, созданные любым методом (т.е. твердотельное моделирование, поверхностное, проволочное или воксельное). В качестве геометрического ядра была выбрана открытая платформонезависимая система геометрического моделирования Open CASCADE, которая дает средства для создания пользовательского приложения с использованием всех своих классов представления и визуализации геометрии.
Вычислительная модель метода декомпозиции области
Для построения вычислительной модели МДО также будем использовать методологию ООП, которая позволяет строить абстрактные модели и описывает, каким образом они могут быть реализованы. В вычислительной модели метода декомпозиции области можно выделить следующие модели [55]: модель МДО; модель распределенных данных в подобластях; модель параллельных вычислительных процессов в подобластях; модель эффективного распределения данных между подобластями (модель балансировки нагрузки).
Модель МДО была рассмотрена в предыдущей главе, поэтому остановимся на модели распределенных данных и параллельных процессов.
Набор однотипных объектов, соответствующих тому или иному сегменту данных декомпозированной задачи определяет распределенные данные. Для МДО разделение данных необходимо не только для эффективной параллельной обработки, но еще и потому, что в реальных больших задачах хранение всех данных на одном вычислительном узле может оказаться невозможным. В алгоритме МДО распределенными данными являются конечно-элементная сетка и система уравнений.
Набор однотипных объектов, выполняющих те или иные методы одновременно, в общем контексте определяет параллельные процессы. Для МДО распараллеливание является достаточно легко формализуемым способом повышения производительности вычислений. В алгоритме МДО распараллеливанию подлежит, не только, формирование и решение систем линейных уравнений на подобластях, но и процессы связанные вводом/выводом, разделения/распределения, перестроения и т.д.
МДО предполагает балансировку нагрузки на уровне пользовательского приложения. Она связана с эффективным распределением данных между подобластями таким образом, чтобы вычислительные затраты на каждом процессоре были примерно равны. В расчетной модели МДО были введены объекты PartitionedDomain и DomainPartitioner, описывающие граф подобластей (Graph) и метод его разбиения (GraphPartitioner) Таким образом, для эффективного распределения данных необходимо разработать систему объектов, унаследованных от GraphPartitioner, которые включают различные методы разбиения графа, а также подобрать для конкретной задачи наиболее приемлемый алгоритм разбиения (см. гл. IV).
Основные описания MPI — процессы: основные операции — различные типы обменов данными между процессами. Процессы выполняют единую инструкцию над своими данными и обмениваются полученными результатами. При необходимости дифференцировать процессы друг от друга в программу вводятся участки кода, соответствующие различным альтернативным вариантам, и в режиме выполнения в каждом из процессов, в зависимости от идентификатора процесса, запускается тот или иной код. Таким образом, MPI-программа представляет собой единый код для всех процессов, который разветвляется в тех местах, где процессы отличаются. Эту технологию целесообразно применять для реализации SIMD-моделей, когда все процессы в программе идентичны и структуры данных достаточно просты.
Стандарт MPI не имеет средств описания объектов, но, как правило, реализованное промежуточное ПО MPI предназначено для разработки на языке С; следовательно, это ПО может быть использовано в рамках языка C++. Таким образом, C++ становится средством реализации объектов в MPI-программах. Традиционные объекты C++ используются в тех участках кода, которые выполняются в рамках одного МР1-процесса.
Рассмотрим способы реализации объектов-данных и объектов-процессов, которые используются в рамках всей системы MPI.
Распределенные данные можно реализовать двумя способами: перемещаемые объекты и распределённые объекты. Первые представляют собой обыкновенные объекты C++, включающие дополнительно методы по передаче своего состояния MPI процесса на другой. Такой подход целесообразно использовать в тех случаях, когда необходимо переместить тот или иной объект с одного узла на другой. При реализации с помощью этого подхода удаленного доступа к объектам, расположенных на других узлах, возникает проблема синхронизации их удаленного состояния с с локальным. Один из вариантов перемещаемых объектов представлен в системе ТРО++ [90,97].
Для примера рассмотрим перемещение объекта NodalLoad, представляющего узловую нагрузку. Для начала введем систему вспомогательных объектов, которая является базой при реализации перемещения объектов. Класс MPI_Channel - шина обмена элементарными данными (потоками байтов, идентификаторами, векторами/матрицами, объектами) между вычислительными узлами. Реализация класса MPI_Channel основана на обменах данными между МРІ-процессами: в функциях передачи элементарных данных вызываются соответствующие функции MPI (send/recv). Класс MovableObj ect — базовый класс для перемещаемых объектов. Его методы — виртуальные функции sendSelf /recvSelf: отправить и получить свое состояние в виде потока байтов через канал обмена данными. При отправке и получении состояния важную роль играет идентификатор, благодаря которому точно определяется адресат. Идентификатор Tag — основной атрибут класса MovableOb j ect.
Балансировка на уровне операционной системы
В настоящее время в стадии разработки находится ряд технологий, построенных на основе MPI и CORBA. Тесты производительности [100] и анализ возможностей проектирования программ приводят к выводу, что наиболее перспективными являются проекты, связанные с развитием стандарта CORBA и его интеграцией с MPI.
Рассмотрим подход для развития технологии CORBA в области компонентного проектирования программ и высокопроизводительных вычислений — технология параллельных распределенных компонентов. Основными ее составляющими являются: компонентная система; распределенная компонентная система; параллельная компонентная система.
В основу технологии положены стандарт компонентной модели CORBA ССМ (CORBA Component Model) [101], а также интерфейс асинхронного вызова методов AMI и интеграция с MPI. Технология параллельных распределенных компонентов реализуется на базе промежуточного ПО ТАО (The АСЕ ORB) [102].
Компонентная система представляет собой объектно-ориентированную модель программной системы.- Компонентная система обеспечивает основные методы работы с программными компонентами: проектирование, установка, управление в режиме реального времени (запуск, отслеживание состояния, остановка). В качестве программных компонентов в данном случае понимаются CORBA-приложения. Сама компонентная система также реализуется в виде CORBA-объектов, т.к. в дальнейшем она используется в составе распределенной компонентной системы.
В настоящий момент для CORBA разрабатывается стандарт компонентной модели ССМ, который описывает весь жизненный цикл программных компонентов: разработка, установка, выполнение. В связи с отсутствием полноценных реализаций ССМ на основе ССМ: Components создана собственная компонентная система.
Компонентная система основывается на ряде стандартных возможностей CORBA: на разработке объектов с помощью IDL и на управлении объектами с помощью сервисов (Implementation Repository, Naming Service). Компонентная система состоит из вспомогательной С-)--)- библиотеки, где реализованы компоненты (объекты ССМ), а также сервиса приложений, позволяющего манипулировать этими компонентами. Объекты ССМ являются обычными объектами CORBA и реализуют ряд функций, которых достаточно для того, чтобы с помощью сервиса приложений запускать и искать их экземпляры. Процесс реализации компонентов состоит из следующих этапов: создание интерфейсов прикладного объекта на языке IDL; создание прикладных объектов CORBA, реализующих интерфейсы, полученные на первом этапе; создание компонента путем наследования от классов библиотеки CCM-Components и прикладного объекта, реализованного на втором этапе.
Прикладной -CORBA-объект с интерфейсом Facet погружается в шаблон Component, который обеспечивает создание экземпляров компонента. Конструктором компонентов выступает фабрика компонентов Ноте. поненты являются обычными CORBA-объектами, то целесообразно интегрировать сервис компонентов со стандартными сервисами CORBA, чтобы использовать инструменты для управления объектами. Сервис Implementation Repository используется для активации компонентов, Naming Service обеспечивает соединение с экземплярами объектов.
Распределенная компонентная система описывает и реализует работу с компонентами, распределенными по МВС. Реализация распределенной системы агрегирует реализацию компонентной системы, позволяя взаимодействовать нескольким компонентным системам, сопоставленным с узлами вычислительной системы.
Основным направлением в развитии распределенной модели является создание описания архитектуры программно-аппаратной среды и специальных служб, которые в режиме реального времени выдают состояние вычислительных узлов и коммуникаций (степень загруженности процессоров, объемы занятой и свободной оперативной памяти, объемы пересылок и т.д.).
Наиболее важной частью вычислительной системы является технология параллельных распределённых вычислений, которая является расширением технологии асинхронного вызова методов AMI и создается на базе ПО ТАО. В ТАО частично реализован интерфейс AMI, в частности событийный механизм, поэтому технология параллельных компонентов в первую очередь основана на этом способе асинхронного вызова методов. В перспективе планируется использовать и механизм опроса. Структура
Component flrom S«r «r Stdt) Facet Qtom Stiver Sidt) параллельного компонента отличается тем. что на клиентской стороне вводится обработчик событий AMI (рис. 3.10). При такой структуре возможны три способа взаимодействия с компонентом: синхронный вызов интерфейса Facet посредством FacetStub; t обработка событий, определенных интерфейсом Event, посредством CORBA-объекта Event; асинхронный вызов интерфейса Facet посредством FacetStub и последующая обработка событий посредством FacetAMIHandler.
Необходимость интеграции промежуточной системы MPI обусловлена ее популярностью в мире параллельных вычислений и большому количеству программного обеспечения, разработанного на ее основе.
Инкапсуляция MPI-кода может быть осуществлена посредством клиентских или серверных CORBA-приложений (рис. 3.11). Первый способ предназначен для инкапсуляции ППП, основанных на технологии MPI. Он заключается в реализации клиентского приложения, содержащего МР1-код, и CORBA-объекта, синхронизирующего набор одновременно запускаемых клиентских приложений. В данном случае общий и распределенный объектно-ориентированный интерфейс к ГТПП реализованы в CORBA-объекте; параллельное поведение не имеет каких-либо объектно-ориентированных описаний и реализовано в клиентских приложениях. Использование этого подхода будет продемонстрировано ниже на примере библиотеки ParMetis. Второй способ предназначен для создания прикладных CORBA-объектов, имеющих параллельное поведение на основе MPI. Можно выделить два варианта реализации этого способа: многократный запуск CORBA-серверов в контексте MPI и выполнение в контексте MPI только методов многократно запущенных CORBA-серверов в контексте MPI.
