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

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

□□30ВТО45

Копысов Сергей Петрович

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

ЭЛЕМЕНТОВ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Москва - 2006

003067045

Работа выполнена в Институте прикладной механики Уральского отделения РАН

Официальные оппоненты — доктор физико-математических наук,

профессор

Александр Васильевич Лапин

доктор физико-математических наук Ольга Юрьевна Милюкова

доктор физико-математических наук, профессор

Игорь Борисович Петров

Ведущая организация — Институт механики сплошных сред

"Уральского отделения РАН.

Защита состоится 22 марта 2007 г. в

на заседании диссертационного совета Д 002.058.01 в Институте математического моделирования РАН по адресу 125047, г. Москва, Миусская пл., д. 4А.

С диссертацией можно ознакомиться в библиотеке ИММ РАН.

Автореферат разослан

/О

2од?г.

Ученый секретарь диссертационного совета

д.ф.-м.н.

Н.В. Змитренко

Общая характеристика работы

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

Под методами декомпозиции далее понимается совокупность методов и алгоритмов для эффективного параллельного решения задач вычислительной механики, включающих в себя: декомпозицию матрично-векторных вычислений; разделение и распределение вычислительной области/сетки/ нагрузки; функциональную декомпозицию методов решения; декомпозицию программного кода.

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

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

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

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

Главные подходы управления адаптивным процессом, предназначенным для уменьшения погрешности МКЭ, следующие: движение узлов сетки без изменения связности (г-версии); локальное сгущение (перестроение) начальной сетки (к-версии); повышение степени кусочно-полиномиальных базисных функций МКЭ (р-версии) и их комбинации. Каждый из этих способов управления имеет свои достоинства и недостатки, поэтому представляется целесообразным их комбинированное использование. Однако, теоретически обоснованное построение подобной эффективной комбинации (даже для линейных задач) остается еще нерешенной проблемой. На прак-

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

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

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

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

Весьма важным в рамках данной проблемы является и вопрос создания программного обеспечения для реализации адаптивного применения МКЭ при решении больших реальных задач.

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

Разработка программных комплексов для проведения крупномасштаб-

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

На сегодня не вызывает сомнений, что важным обстоятельством при осуществлении декомпозиции алгоритма и программы является необходимость ее проведения путем совместного анализа всех аспектов междисциплинарного построения параллельных алгоритмов, а именно: собственно прикладной задачи; математических моделей и методов; теоретического анализа по построению новых вычислительных алгоритмов, адаптации существующих алгоритмов; объектно-ориентированной технологии проектирования и программирования; архитектуры вычислительной системы.

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

Научная новизна. Построены новые алгоритмы адаптивного МКЭ, которые включают параллельные алгоритмы: формирования и решения систем нелинейных и линейных уравнений, апостериорной оценки погрешности, локального перестроения сетки/повышения порядка аппроксимации элементов и динамической балансировки вычислительной нагрузки.

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

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

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

Предложены и исследованы методы разделения расчетной сетки, динамической балансировки вычислительной нагрузки и перераспределения сеточных объектов для адаптивных схем МКЭ на основе геометрических и графовых моделей расчетной сетки и неоднородной вычислительной системы.

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

Проведены численные исследования методов декомпозиции и адаптивных версий МКЭ для модельных и прикладных задач: упругого деформирования композиционных материалов и определения осредненных характеристик, циклического нагружения конструкций из нелинейного вязко-упругого материала, нормального роста зерен поликристаллического материала, молекулярно-динамического моделирования полимеров.

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

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

Апробация работы. Основные результаты диссертации докладывались: на Всесоюзных и Всероссийских конференциях по динамике и прочности ракетных комплексов (Челябинск, 1987), по реологии и оптимизации процессов переработки полимеров (Ижевск, 1989), по численным методам механики сплошной среды (Абрау-Дюрсо, 1992 ), зимних школах по

механике сплошной среды (Пермь, 1995, 1997), конференциях по численным методам решения задач теории упругости и пластичности (Волгоград, 1995), по математическому моделированию для решения задач в науке и технике, (Ижевск, 1996, 1998), по теории сеточных методов для нелинейных краевых задач (Казань, 1996, 1999, 2001, 2003, 2005), по современным проблемам математического моделирования (Абрау-Дюрсо 1997, 1999), по проблемам построения сеток для решения задач математической физики и теоретическим основам и конструирования численных алгоритмов для решения задач математической физики (Пущино, 2000), по высокопроизводительным вычислениям и их приложениям (Черноголовка, 2000), по построению расчетных сеток (Москва, 2002, 2004), по методам и средствам обработки информации (Москва, 2003), по параллельным вычислениям (Томск, 2005), на съезде по теоретической и прикладной механике (Пермь, 2001), на международных конференциях по горению 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 наименования.

Содержание работы

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

кратко излагается содержание диссертации по главам, представлен обзор основных результатов диссертации.

В первой главе рассматривается ряд способов распараллеливания методов решения прикладных задач, связанных с различными видами декомпозиции полной задачи на ряд одновременно выполняемых подзадач: многофронтальный метод; метод декомпозиции, основанный на механическом взаимодействии подобластей; методы подструктур. Анализируется несколько формулировок методов декомпозиции для выделения их общих и специфических операций.

Рис. 1. Двухуровневое разделение Рис. 2. Зависимость параллельного

для метода подструктур ускорения 5(пр) от числа

подобластей пв

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

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

АЪ А}в V «П - ( Л

Агв1 Агвв ) \ игв ) V ) ' ^

5ввйв = /в, (2)

пр пр

SBB = - ¿BMTW^B, /в = £ /], - ¿BMTtffj,

t=l г=1

здесь 5вв — матрица дополнения Шура; индексы " I" ," В" относятся к внутренним и граничным степеням свободы; пр — число процессоров.

Система уравнений для дополнения Шура формируется на другом уровне расчетной сетки — на ее остове. Разделение дуального графа не определяет балансировку нагрузки при решении данной системы. При разделении сеточной области на подобласти с равным числом элементов и минимальной границей подобластей в крупноблочном методе подструктур вносится разбалансировка, которая связана с разными вычислительными затратами при операциях с матрицами Авв^Мв в подобластях. Количество арифметических операций для нахождения составляющих матриц дополнения Шура на подобласти 0(п^/б) , и при выполнении параллельного алгоритма между подобластями не происходит обменов, тогда имеет смысл выделять по несколько подобластей на один вычислительный узел.

Для сбалансированности вычислительной нагрузки и выравнивания числа обменов использовалось двухуровневое разделение области. Подобласти с разделенной сеткой объединялись в группы так, чтобы выполнялись условия сбалансированности по п/, rij+пв ■ Число групп равнялось числу процессоров. Для этого строился граф Gs(V, E,W), учитывающий связность подобластей, в котором вершинам V соответствовали подобласти из предыдущего разделения сетки, а ребрам Е — связи подобластей (рис. 1). В качестве весов вершин данного графа wv принималось число узлов подобласти nlj или п\ + пгв , а весов ребер we , соединяющих подобласти, пгв — число граничных узлов между подобластями.

С ростом числа подобластей система уравнений для дополнения Шура возрастает. Увеличивается и коммуникационная нагрузка. В тоже время затраты на факторизацию и формирование матрицы граничной жесткости при большом числе подобластей сокращается (рис. 2). Уменьшаются и требования по памяти.

Было проведено сравнение временных затрат, необходимых для формирования и решения системы, для дополнения Шура и в подобластях для задач теории упругости (рис. 3,4). Рассматривалось два варианта хранения, упорядочивания и формирования матриц для внутренних узлов и дополнения Шура: симметричные ленточные матрицы и матрицы, хранящиеся без нулевых элементов, CSR (Compressed Sparce Row). Как показали вычисления, схема хранения оказывает существенное влияние на время вычисления. Отметим, что для ленточных матриц время формирование дополнения Шура составляет порядка 80% с числом подобластей, равным числу процессоров, и в дальнейшем сокращается. Переход на формат CSR

Рис, 3. Конечно-элемфн гная сетка: N = 67549 узлов; М = 353956

Рис. 4. Разделение сетки на ns = 70 подобластей для п,, = 14 процессоров

элементов

для матриц Лви- Агв Лц для одной и той же задачи дал сокращений затрат в 4 раза.

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

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

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

Рассмотрен метод декомпозиции, используемый с методом сопряженных градиентов, основанный на упорядочивании системы (1) без выделения дополнения Шура и параллельном решении блочной системы.

Для алгоритма характерно, что мет явной зависимости от числа неиз-

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

Вычислительные затраты в MatrixVector, VectorVector определяются типом реализуемых структур данных для блочных матриц. Используется, как правило, два варианта хранения: симметричные ленточные матрицы и матрицы, хранящиеся без нулевых элементов, CSR-формат. Отметим, что матрица Авв сильно разрежена. Применение формата CSR для матриц Abb,Aib,Aii приводит к значительному сокращению затрат. CSR-формат требует Nz чисел с плавающей точкой и Ö{2NZ) целых чисел для хранения матрицы, что значительно меньше по сравнению с ленточной и профильной схемой хранения и сокращает вычислительные затраты примерно на 30%. Однако, надо учитывать, что в данной схеме нет прямой адресации и требуется определенная структура данных, особенно для распределенных параллельных вычислений.

В основе предложенной поэлементной декомпозиции лежит преобразование связности, базирующееся на топологических операциях объединения и разъединения. Главные преимущества поэлементной схемы заключаются в следующем: может быть использована с любыми типами элементов; требования памяти пропорциональны числу элементов в сетке; простота представления и отображения на параллельную МВС.

Согласно принятому разделению, подобласть, находящаяся на процессоре, содержит блоки матриц и векторов для внутренних и граничных узлов. Пусть подобласть fi, связана с конечно-элементной подсеткой %, причем элементы внутри подобласти пронумерованы е = 1 ,М} , а элементы, лежащие на границах подобластей имеют номера е = М} 4- 1,Мгв. Тогда поэлементное представление глобальной матрицы через матрицы, связанные подматрицами на пр процессорах, имеет вид

Пр М »=1 е=1

здесь Af — локальная матрица конечного элементна е, принадлежащая процессору г; С\ — матрица связанности конечных элементов, принадлежащих разным процессорам; М — число конечных элементов. Глобальное

матрично-векторное произведение будет иметь вид

пр м

г=1 е=1

Параллельная схема метода сопряженных градиентов с элементной декомпозицией будет иметь вид

— Инициализация щ — О, fo = / — Ащ, г о = CTCr0, р о = г0

— Построение предобусловливателя Л4

— Итерационное уточнение

256 384

-«КЮуринский - 10000 уринсни

0.006 О.Ш

Рис. 5. Ускорение S(np) и эффективность £{пр) поэлементной декомпозиции

Выполнить fc = 0,1,...

йк = Арк

пр г=1

= -РкНк Ük+l =йк~ OLkVk ?к+1 =Гк+ СИкЧк

Гк+1

Cj^cTfí

к+1

г=1

ек+1 - УМ+l^k+l)

г=1

Если (Щф<£] то Exit

V ЫЬ

Sfc+1

M-'c^cJfU х

¿=1

pk+i = 5^(4+1» »fc+i)

г=1

Рк = Pk+l/Pk Рк+1 = $к+1 + /3fcPfc

увеличить к

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

Пр M "р Aif Пр Мд

Р=1 е=1 р=1 е=1 р=1 e=Mf+l

Совмещение вычислений и обменов в совокупности с уменьшением числа обменов на каждой итерации позволило сократить временные затраты на 15 — 20% . Это относится ко всем рассмотренным методам декомпозиции.

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

В пятом параграфе рассмотрены взаимосвязи между вычислительной структурой алгоритмов МДО и архитектурой многопроцессорной вычислительной системы.

Рассмотрены подходы к разработке параллельных алгоритмов МДО, состоящие из следующих этапов проектирования: декомпозиция, коммуникации, кластеризации и разделение/распределение подобластей.

Проведенный анализ показал, что для построения эффективных параллельных алгоритмов МДО необходимо: придавать алгоритмам специальную форму, позволяющую явно выделить параллельные процессы; выбирать необходимый уровень декомпозиции алгоритма — разделение на крупные подобласти не позволяет равномерно загрузить процессоры, а использование мелких подобластей приводит к росту вычислительных затрат на коммуникации и синхронизацию; обеспечить независимость параллельной структуры данных алгоритма от топологии вычислительной системы для оптимального отображения и переносимость программного обеспечения.

Во второй главе показаны пути максимального сокращения трудоёмкости программной реализации новых методов декомпозиции с одновременным глубоким распараллеливанием вычислений, удобным для реализации на современных ЭВМ; рассмотрен новый подход к созданию программной системы для МДО, отличительной чертой которого являются: прозрачность и возможность доступа ко всем деталям реализации конкретного метода или алгоритма, а также математическая ясность описания нового метода для разработчика и пользователя; открытость, то есть возможность быстрого дополнения системы новыми алгоритмами МДО,

простота использования разработанных методов для практических расчетов.

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

Во втором параграфе предлагаются 00 модели геометрии, сеток и расчетных данных как ядро вычислительной среды. Описывается структура предлагаемого редактора расчетных моделей, представленного логическими составляющими: геометрия, базовая сетка, расчетные данные, разделенная и распределенная сетка. Каждая составляющая содержит компоненты обработки данных, 00 моделирования и визуализации. Модель геометрии определяет базовый уровень, каждый следующий логический уровень зависит от всех предыдущих. Компоненты 00 моделирования являются ядром, на основе которого реализуются компоненты обработки данных и визуализации, поэтому далее основное внимание уделяется вопросам построения 00 моделей геометрии, сеток и расчетных данных, разделенной и распределенной сеток.

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

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

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

В третьей главе предметом рассмотрения являются различные спо-

Рис. G. Объектно-ориентированная модель вычислительной среды собы параллельной распределенной реализации объектной модели метода декомпозиции области с помощью технологий MPI и CORBA. Предлагается технология параллельных распределенных компонентов, основанная на компонентной модели С О ГШ А, технологии асинхронного вызова методов AMI, инкапсуляции MPI-приложений.

В первом параграфе приводится сравнение технологий MPI и CORBA, Технологи и MPI и CORBA обеспечивают коммуникации между процессами, запущенными на разных узлах, но CORBA дополнительно дает высокоуровневый интерфейс для организации обменов, соответствующий концепциям объектно-ориентированного и компонентного программирования: динамическое создание объектов, удаленный вызов методов объекта, пересылка объекта, интерфейс и реализация объекта и др. В плане производи-

тельности системы промежуточного программного обеспечения отличаются незначительно — при одинаковой пропускной способности системы MPI отличаются лучшими показателями латентности.

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

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

В параграфах 3-5 разработана вычислительная среда для конечно-элементного анализа и метода декомпозиции области, которая обеспечивает разработку, реализацию и запуск прикладных расчетных программ. В основе комплекса лежит параллельная распределенная объектно-ориентированная модель метода конечных элементов и метода декомпозиции области, созданная с помощью технологии параллельных распределенных компонентов. Распределенная модель метода декомпозиции построена в соответствии с разделением области на подобласти: удаленными объектами заданы подобласть и узел, перемещаемыми — элементы, узлы, граничные условия, матрицы, векторы. В параллельной модели реализованы классы, обеспечивающие асинхронный вызов методов удаленных объектов класса "подобласть", и модифицирована модель "решения", связанная с разделенной областью. Созданы компоненты метода декомпозиции, описывающие процессы вычислений в подобластях и в области. Комплекс программ ориентирован на проведение междисциплинарных расчетов.

Программное обеспечение МКЭ И МДО, в котором реализованы представленные в первой главе алгоритмы декомпозиции, тщательно протестированы автором, соавторами и его заинтересованными коллегами и заказчиками некоторых проектов.

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

шения балансировки нагрузки.

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

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

я = +<4)

к i Ii

где первое слагаемое соответствует нагрузке, а второе — связям и Wik ~ стоимость обработки г-ой части программы на к -ом процессоре; Vrj — объем данных, посылаемых от процессора г к процессору j , при Уг] — О процессоры не взаимодействуют; Ski — мера стоимости связи процессоров к и I, при Ski = оо процессоры не связаны; ¿¿t = 1, если г -ая часть обрабатывается fc-ым процессором; ц — константа, зависящая от конкретной МВС и характера задачи.

Использование моделируемого отжига для решения задачи разделения сеточных структур (4) позволило явно учитывать структурное устройство МВС, в том числе структуру системных связей между процессорами, а также привязывать критерий декомпозиции к конкретному виду параллельного алгоритма. Достоинством метода также является простота распараллеливания .

Как показали сравнения, недостатком метода является то, что затраты на выполнение алгоритма разделения часто соизмеримы с вычислительными затратами самого приложения. Поэтому алгоритм использовался для улучшения уже полученных результатов, в том числе с помощью других методов.

Для большинства задач вычислительной механики естественными объектами для балансировки нагрузки являются компоненты вычислительной сетки: конечные элементы или объемы; узлы; грани и ребра. Геометрические и топологические свойства сеток гарантируют, что хорошее разделение для них существует. Объекты вычислительной сетки обычно имеют ограниченное число соседей, что уменьшает влияние разрезов сетки. Сет-

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

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

Эффективность параллельного алгоритма для элементного и узлового

разделения можно оценить как

1 1

£в{Пр)= 1 + о{п1'\-Е^) + пр{1с11РУ £П{Пр) = 1 + пр{и/гру

Двойственность между двумя разделениями показывает, что асимптотические затраты являются фактически теми же самыми, изменяются только константы. Оптимальный выбор из двух графов разделения определяется формулировкой и реализацией используемых алгоритмов метода декомпозиции. Во многом это связано с различной алгоритмической реализацией основных этапов МКЭ или другого сеточного метода: хранения, формирования, решения СЛАУ и других. Например, для узлового, реберного и поэлементного подходов необходимо строить свои графы.

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

В третьем параграфе выполнено сравнение алгоритмов динамической балансировки нагрузки, которое проводилось по трем параметрам: числу разрезанных ребер \ЕС\ (рис. 7) , дисбалансу вычислительной нагрузки А\У (рис. 8) и числу пересылаемых конечных элементов ДМ (рис. 9). Первые два параметра характеризуют качество разделения сетки. Дисбаланс отвечает за равномерность вычислительной нагрузки во время вычислений, а число общих ребер — определяет объем межпроцессорных обменов. От третьего параметра зависит время выполнения перераспределения сетки.

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

В четвертом параграфе рассмотрена оценка эффективности параллельного выполнения алгоритмов разделения в случае неоднородной вычислительной среды.

| - -- - 1.ГМ.,о) 1.ЕМ1НСИС) • » Яп>р(п| I

| —— - — ■ SFl.lv.! — 5ГС|иослс> |

__,,

1 1

Рис. 7. Изменение числа разрезанных ребер по шагам перестроения

л/

Рис. 8. Изменение разбалансированности процессоров

6,0 [ \ --(ДН',)тах

4.0 , \ -(А^От.п

Рис. 9. Зависимость числа Рис. 10. Изменение относительной

перераспределяемых конечных разбалансировки по шагам

элементов от шага перестроения перестроения IV* — 0.2

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

Щ = МрИ, + /1сСг + МтУг, (5)

где И; — относительная производительность процессора г; С; — относительная скорость обмена сообщениями; V, — относительный объем оперативной памяти; Мт ~~ константы. Вершинам графа вычислительной системы Ср ставился в соответствие вес, равный производительности процессора.

В отличии от всех рассмотренных выше случаев разделим нагрузку на процессоры неравномерно. Для этого находится неоднородное распределение частей сетки по процессорам по соотношениям Мг- = ич ■ М, где М, М{ — число конечных элементов в сетке и на г -ом процессоре; и)1 — вес

загрузки вычислительного узла.

Алгоритм стартует с начальной грубой равномерно распределенной сетки. Выполняется адаптация сетки согласно критерию адаптации. Находится дисбаланс нагрузки

Wi ■ М

Если АИ^г > 0 , то процессор перегружен. В случае ДТУ^ < 0, процессор недогружен. Балансировка нагрузки выполнялась после каждого шага перестроения сетки (рис. 10).

Эффективность выполнения определялась как коэффициент полезной загрузки, с которым используется пиковая производительность неоднородной МВС

*"<">> ~ ^»(.ац,)'"1 <7)

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

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

Рассматривается новый подход, соединяющий построение и разделение сетки в отдельную задачу. Традиционно эти две задачи решаются независимо с вводом/выводом и накладными расходами на пересылку данных, которые порой превышают 80% полного времени построения, разделения и размещения большой сетки на распределенной памяти параллельной системы. Рассматриваемый подход минимизирует ввод/вывод и накладные расходы пересылок данных, устраняя избыточные операции. Результаты показывают, что такой подход работает в несколько раз быстрее, чем традиционный подход построения, разделения и распределения неструктурированных сеток.

Сформулированы требования, предъявляемые к методу (программно-

му обеспечению) параллельного построения сетки. Методы параллельного построения неструктурированных сеток разделены по нескольким критериям: методы с разделением геометрии области; методы с разделением грубой сетки и т.д.

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

Как показали вычислительные эксперименты по построению больших сеток, более приемлимым является алгоритм параллельного построения сетки на основе разделения грубой сетки: первоначально строится достаточно грубая сетка с минимальным представлением геометрии; сетка разделяется на заданное количество подсеток и распределяется на вычислительных узлах; каждая подсетка регулярно или адаптивно измельчается. Тем самым, все последующие вычисления хорошо сбалансированы.

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

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

Рассмотрим построение сетки(диаграммы) Вороного в R3 с ограничениями. Пусть в пространстве задана область О. с R3 . Для определения области П используется задание ее границы Г = /ъ/2, • • •,/jVb > гДе fi — ориентированная грань. Для задания границы области использовался разработанный редактор расчетных моделей.

Для заданного множества узлов Р = {рьрг, ■ ■ ■ ,Pn} {Pi £ Q , Pi £ Г ,

n

Vi — 1 ,N) необходимо построить диаграмму Вороного V = (J Mi, где

г=1

M.i(F, V, Е) — многогранник Вороного (MB) точки р*, определяемый множеством граней F , вершин V и ребер Е. Многогранник M.i представляет собой область в R3 , все точки которой расположены по отношению к pi ближе, чем к любому другому узлу pj

Mi = {x£ R3,d{x,Pi) < d(x,pj)}, i,j = 1,2,...N, здесь d — расстояние между узлами. Все многогранники выпуклы и объ-

единение их совпадает со всей Р13 .

При построении диаграммы Вороного для заданного множества Р и ориентированной границы Г на этапе предобработки производится построение трехмерного двоичного дерева (ЗБ-дерева). Заданное множество узлов Р делится на подобласти по числу процессоров с использованием геометрических алгоритмов разделения. Если в построении принимают участие пр процессоров, то построение МВ на каждом процессоре выполняется только для Ы/Пр узлов. Затем в основном цикле производится последовательное построение многогранников Вороного. Для каждого узла р1 € Р за один основной цикл алгоритма строится один М{. Основной цикл состоит из пяти шагов:

Шаг 1. Для каждого рг определяется множество то ближайших соседей р' = {р1,р2, ■ ■ ■ ,Рт} (0 < т < ./V) и множество остальных Р — Р С\Р' , здесь Р" = р'1,р2,- ■ • для (к = 1... то ,

3 = 1 ...Ы - т - 1).

Шаг 2. Формируется "временный" многогранник М . Для этого производится построение и учет то плоскостей Н¡^ , перпендикулярных \PiiPk] и проходящих через их середины.

Шаг 3. Определяется расстояние до наиболее удаленной вершины "вре-

n

менного" многогранника ¿тах = тах с! , и;), где VI — вершины

М.' , ЛГ„ — число вершин М.', отбрасываются те точки множества Р', для которых й(рир'{)/2 > ¿тэ.х .

Шаг 4- После учета всех т ближайших соседей добавляются Нг] , для которых й{рг,р'■) < 2с1тах , при этом йтах уменьшается по ходу построения.

Шаг 5. Учитываются /8, в — I... Лгг . В результате М. достраивается до Мг .

На Шагах 1 и 4 для нахождения узлов, удовлетворяющих неравенствам, решается задача регионального поиска в сфере переменного радиуса с использованием трехмерного двоичного дерева. В качестве критерия выбора пути для поиска используется сравнение расстояний (1{рг,р^), з = 1,2... N при з Ф г. При построении многогранников производится учет информации о ранее построенных соседних МВ. После построения всех N многогранников формируется общая структура данных. Динамическая структура данных содержит координаты вершин, имена ребер и граней МВ и

построена с учетом возможности перестроения при движении отдельных узлов множества, добавления и удаления узлов.

На предобработку требуется время 0(N log N). Общая трудоемкость метода в худшем случае равна 0(N3/np), это несколько выше чем в известных алгоритмах, однако, как показывают измерения, в среднем для случайного распределения узлов и распределения по шаблону трудоемкость не превосходит 0(N1-25/пр). Преимуществом метода при параллельной реализации является малая доля операций, не поддающихся распараллеливанию по сравнению с другими методами и, как результат, высокая эффективность алгоритма £{пр) и 99%.

В худшем случае затраты памяти на хранение данных составляет 0(N2), однако, в рассмотренных случаях на хранение данных требовалось памяти O(N).

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

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

а = фа*,

где ф — имеют такой же вид и порядок, как и в представлении аппроксимации перемещений при решении основной задачи.

Для нахождения оценки погрешности

\\E4=a-ah (8)

использовалась сопряженная аппроксимация напряжений а и а , которая

Решвине СЛАУ

■ Роидвние СЛАУ основной системы ■ ЯСрвШнОСТи

о свтии О Вр&ф <Алвс1 и пдаест®<«н»*

■ Нов« разделение свтт Я пгрерадтрйО® с^тки

100% —-Щ ■ ■■■■■■■'■"

75% -----------

50%------------

25%-------------

0% 11Ч1Ч1Ч1

1 2 3 <1 5 5 7 8 9 10 11 12 13 Шаги перестроения

Рис. 11. Схема параллельного Рис. 12. Структура

адаптивного МКЭ вычислительных затрат

приводит к решению системы уравнений с тремя правыми частями: м

ва'к * Л, С? = ]Гс;ГС£Се, / к = 1,2,3 (9)

е=1 Ж*

где каждой к -ой компоненте напряжений, соответствует своя правая часть; гре — функция формы элемента; Сс — элементная матрица Грамма, составленная из скалярных произведений системы базисных функций т/^, ..., Ф^ стк* — неизвестные узловые значения напряжений; Се — матрица связности; Д — вектор правой части: м

Л= / (Ю)

е=1

Полученная система уравнений формируется и решается на основе поэлементной декомпозиции. Параллельное решение трех систем (9) заменялось решением одной системы с тремя правыми частями и объдинением пересылок.

Таким образом, применение теории сопряженной аппроксимации свелось к системе алгебраических уравнений (9), порядок которой совпадает

Рис. 13- Разделение сетки на пр — 512 : слева — исходной; справа —

адаптивной

с порядком исходной системы, используемой для получения значений искомых' перемстнений, и связало с большими вычислительными затратами на формирование и решение СЛАУ.

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

77=^100%, = ЕЛ2. (11)

Критерий перестроения конечного элемента е имел вид

£ = II^IU П2,

здесь энергетическая норма конечно-элементного решения;

- норма погрешности, определяемая по (8).

Условие адаптации формулируется следующим образом. Конечный элемент перестраивается, когда критерий перестроения превышает допустимую величину. Далее: полагалось, что зада.!! список элементов для адаптации и все операции перестроения выполняются па уровне отдельных ко-

нечных элементов.

Отметим только некоторые свойства локального перестроения при делении элементов: 1. Построение конформной сетки выполняется практически автоматически с небольшим разростанием области перестроения. Некоторые теоретические оценки показывают, что построение конформной триангуляции получается за конечное число шагов согласования. 2. В перестроении используется минимальный набор шаблонов. 3. История перестроения может быть сохранена или быстро восстановлена и использована для обратного перестроения. Построение грубой сетки ограничено начальной триангуляцией. 4. Шаг сетки явно не задается, но может быть получен из оценки погрешности и в дальнейшем использован при локальном делении элементов. Кроме того, как показано, при делении конечных элементов углы в триангуляции ограничены. 5. Более очевидным является использование таких методов для изотропного адаптивного перестроения или в комбинации с другими методами для получения анизотропных сеток.

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

Базисные функции для р-версии в случае одного измерения имеют вид

Фг{з) = ^{ 1+5г5), г = 0,1 (13)

и

\ ¿р 2 Ь^{х)йх, г = 2,р, Ьр(х) = [(х2 - 1)3 ,

(14)

где в — локальная координата, — 1 < в < 1; .зг — локальная координата г-го узла, в, = — 1,1; Ьр{х) — полиномы Лежандра. Для прямоугольных элементов и конечных элементов в виде прямоугольных параллелепипедов базисные функции получаются перемножением соответствующих одномерных функций вида (13) и (14). Тогда аппроксимация перемещений в шестигранном конечном элементе запишется как обычная линейная комбинация функций формы

8 12 р б р-2 р-т

+ Е Е ФТп'ь?П1+

■и=1 е=1 п=2 /=1 тп=2 п=2

р—4 р— 1 р—1 — т

+ Е Е Е Ф1тп ■ с1гпп\

1 = 2 771=2 71=2

где ищ , а™' , , с1тП{ — неизвестные параметры, причем только ищ

имеют физический смысл — это узловые перемещения; фу , ф™ , фуп ,

■ф1тпп — функции формы для узлов, ребер, гранен и внутренних степеней свободы; р — порядок аппроксимации.

Рассмотрено влияние формы элемента и порядка аппроксимации па точность решения. Для практического применения важно, чтобы элемент сохранял точность вычислений, имея форму, отличную от правильного куба (см. рис. 14, 15). Результаты расчетов показывают, что при использовании элементов неправильной формы первого порядка (И-всрсия) погрешность вычислений значительно возрастает с увеличением отношения сторон шестигранного элемента. С другой стороны, наблюдается, что с повышением порядка элементов точность повышается и приближается к решению, полученному с помощью элементов правильной формы.

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

Для р -версии МКЭ рассмотрено два типа перестроения. В первом слу-

Рис, 14. Адаптивное повышение порядка {ртах = 6)

Рис, 15. Разделение шестигранной сетки для р-версии на пр = 32 подобласти

чае повышение порядка происходит однородно на всей рассматриваемой сеточной области Г2. Во втором — порядок аппроксимации р повышается локально на уровне отдельного конечного элемента. Во многом выбор способа уточнения решения и перестроения обусловлен возможностями оценки погрешности: во всей области; локальных зонах или отдельных конечных элементах, узлах, ребрах и граней.

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

Системы уравнений для р-версии МКЭ имеют специальную структуру — это так называемые вложенные системы. Если введена последовательность р иерархических пространств, то иерархическая конечно-элементная формулировка приводит к р+1 системе линейных алгебраических уравнений. Такой подход обладает рядом преимуществ: нет необходимости переформировывать полностью глобальную матрицу жесткости и достаточно просто локально использовать аппроксимацию более высокого порядка. Однако, процесс решения может быть очень дорогостоящим, если не использовать эффективные алгоритмы решения подобных систем.

Для вершины графа, представляющей собой конечный элемент, задается вес Юу(р), где р — тип элемента или его порядок аппроксимации. В случае, когда под вершиной графа понимается узел конечно-элементной сетки, имеем и)у(п), где п — номер узла сетки. Ребра обозначают связи между конечными элементами или между узлами сетки, или между узлами и элементами конечно-элементной сетки. Реберные веса , ги^(гг), п), таким образом, обозначают коммуникационные расходы на эти связи.

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

= + (15)

и на основе межэлементных, межузловых и элементно-узловых связей в расчетной сетке — оценку коммуникационной нагрузки

= ХрШЕ(Р) + ХпМЕ(п) + ХР,ПЪ)Е(Р,П), (16)

здесь Хр > Хп , Хр,п , £р , £п — переменные, принимающие значение 0 или 1 в зависимости от вида обменов, которые преобладают: между элементами, узлами или смешанные.

Данное представление вычислительной нагрузки (15). (16) позволяет учесть выполнение основных операций в р-версии МКЭ при различной декомпозиции операций: так, формирование матриц жесткости подобластей выполнялось суммированием матриц отдельных конечных элементов при элементном вкладе в (15), а параллельное решение системы блочным МСГ без хранения нулевых элементов, с учетом вкладов узлов (второе слагаемое

Веса элементов, узлов и их отношений задавались с помощью констант Wy(p) , Wy(n), Wg(p), wlg(n) , wg(p,n) (вычислительные затраты для элемента порядка р, вычислительные затраты, связанные с узлом п (например, степени свободы для р > 6) расчетной сетки, объем пересылаемой информации при обменах между элементами, узлами и элементами и узлами конечно-элементной сетки, соответственно) и определялись в тестовых запусках программы, в том числе, и в случае динамической балансировки нагрузки.

Для задачи деформирования области, представленной на рис. 14, было выполнено шесть шагов р-перестроения сеточной модели (ртах = 6). Сетка разделялась на пр = 32 подобласти на основе описанной выше модели вычислительной нагрузки и взвешенного графа для р -версии МКЭ. Относительная погрешность на начальной сетке составляла г) = 17.13% . Далее выполнялось адаптивное уточнение решения с неоднородным повышением порядка. Относительная погрешность полученного решения г/ = 0.57%. На последнем шаге адаптивного перестроения сеточная модель содержала М = 7772, N = 77856, а при однородном повышении порядка система уравнений содержала бы уже N = 894651 неизвестных.

В четвертом параграфе рассмотрены задачи квазистатического циклического нагружения конструкций из нелинейно вязкоупругих материалов.

Определяющие соотношения включают элементы незатухающей и затухающей памяти, отражающих, соответственно, эффекты накопленных микроструктурных повреждений и наследственной механики. Для моделирования эффекта Маллинза использованы соотношения Фарриса: девиатор напряжений Sij определяется как

в (15)).

t

- 9 6,1 j. 1 _ 611

Slj~ ^[\ыР\ еу + [ IMI

I Л(4-г)е;,.(г); (17)

о

t

1/р

£//||оо = sup £//(т); (18)

O^T^t

.о

среднее напряжение записывается в виде

aI=3K0ei + D(eII)ne3qa', (19)

где iio,p,m,B,Ko,D,q,n — константы; R(t — т) — функция сдвиговой релаксации; е^-(т) — производная девиатора деформаций по времени т; — первый и второй инвариант тензора деформаций. Адаптация сетки для задач с историей деформирования выполнялась на основе r-версии МКЭ и равнораспределение весовой функции, которое записывается в виде

к+± fc+5 _ ¿^ееМ(г) II ЕЛ

.хк

хг1 = (1 -0)4 + -Г5 = "„"", , (20)

здесь , — текущие и новые координаты узла г; /3 — параметр

релаксации 0 < (3 < 1; где М(г) — множество конечных элементов, в которые входит узел г, — координаты их центров тяжести. Релаксационный параметр определяется следующим образом

= ппп(Д Д.) = ^ = ^ _

Дх еем(г) тах (/еД;)

1,2,3

где 5е — площадь, 1ск — длина ребра к конечного элемента е,

Построен параллельный метод решения нелинейных систем, имеющий два итерационных процесса: итерационный цикл по Ньютону; второй определяется итерационным приближением, связанным с решением СЛАУ стабилизированным методом бисопряженных градиентов (МБСГСТ).

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

м

АцЫЩ = Щи)°еиГ

е=1

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

и ^ + (21)

где Je —элементная матрица жесткости; е^ — вектор, содержащий неноль

при ] -ом равным единице; /г вычислялось по

}г = е(||и*|| + £),

где 6 = 10-э ■ Соотношение (21) использовалось далее при параллельном решении системы линейных уравнений итерационным .методом бисопря-женпых градиентов.

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

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

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

Более эффективным для практической реализации методом оказался метод декомпозиции по силам, который может быть использован для моделирования как больших, так и малых систем. Несмотря на простоту реализации, как и для декомпозиции частиц, метод декомпозиции сил уменьшает вычислительные затраты и делает их пропорциональными /у/п^). Метод декомпозиции сил является геометрически независимым, что позволяет достигнуть лучшей балансировки нагрузки, чем при использовании метода декомпозиции области.

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

Отдельный раздел посвящен численным результатам. Рассматривается

задача вейвлет-осреднения на примере задачи теории упругости композиционного материала. Там же проводится сравнение с результатами метода асимптотического осреднения.

В заключении приведены основные результаты исследований, изложенных в диссертации.

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

Построены новые алгоритмы адаптивного МКЭ с перестроением сетки и повышением порядка аппроксимациии, которые включают параллельные алгоритмы: формирования и решения систем нелинейных и линейных уравнений, апостериорной оценки погрешности, локального перестроения сетки/повышения порядка аппроксимации элементов и динамической балансировки вычислительной нагрузки. Исследована их эффективность и структура вычислительных затрат.

Предложены и обоснованы алгоритмы параллельной генерации больших треугольных и трехмерных неструктурированных расчетных сеток на основе разделения геометрии и грубой сетки, сокращающие затраты на передачу данных между последовательным построением сетки и параллельным приложением со статической балансировкой нагрузки процессоров. Рассматриваемый подход минимизирует ввод/вывод и накладные расходы пересылок данных, устраняя избыточные операции. Результаты показывают, что такой подход работает в несколько раз быстрее, чем традиционный подход построения, разделения и распределения неструктурированных сеток. Построены новые параллельные алгоритмы перестроения сетки на основе деления элементов по наибольшей стороне и "новейшему узлу". Исследовано влияние алгоритма перестроения на изменение шага сетки и внутренних углов в треугольных ячейках сетки.

Предложены и исследованы методы: разделения расчетной сетки, динамической балансировки вычислительной нагрузки и перераспределения сеточных объектов для адаптивных схем МКЭ на основе геометрических и графовых моделей расчетной сетки и неоднородной вычислительной системы. Проведено сравнение алгоритмов балансировки на различных уровнях взаимодействия с приложением.

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

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

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

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

Работа выполнялась при поддержке Российского фонда фундаментальных исследований (проекты № 06-07-89015, 03-07-90002, 02-07-90265, 99-0790455, 98-01-00480).

Публикации по теме диссертации

[1] Алъес М. Ю., Копысов С. П. Конечноэлементный метод расчета напряженно-деформированного состояния двигателей летательных аппаратов с учетом физической нелинейности наполнителя // Изв. вузов. Авиационная техника. — 1990.— № 3.— С. 3-6.

[2] Липанов А. М., Алъес М. Ю., Копысов С. П. Расчет напряженно-деформированного состояния зарядов РДТТ с учетом физической нелинейности топлива // Вопросы оборонной техники. — 1990. — Т. 18.

[3] Липанов А. М., Алъес М. Ю., Копысов С. П. Численный анализ методом конечных элементов нелинейной вязкоупругости при больших деформациях // Методы выч. эксп. в инж. практ. / ИМИ. — Т. 3.— Ижевск: Изд-во ИМИ, 1992. - С. 100-105.

[4] Estimation of influence of nonlinear behaviour of SRP at complex loading / M. Y. Alies, S. P. Kopyssov, А. K. Novikov, S. L. Ustyuzhanin // Int. conf. on combustion (ICOC(93)).— Moscow-St.Petersburg, Russia: IAM, 1993. - 21-26 June. - Pp. 280-294.

[5] Альес M. Ю., Копысов С. П., Варнавский А. И. Моделирование структуры материала многогранниками Вороного // Применение математического моделирования для решения задач в науке и технике.— Ижевск: Изд-во ИПМ УрО РАН, 1996. - С. 32-43.

[6] Альес М. Ю., Копысов С. П., Новиков А. К. Построение и отображение плоских конечно-элементных сеток на параллельной вычислительной системе // Применение математического моделирования для решения задач в науке и технике. — Ижевск: Изд-во ИПМ УрО РАН, 1996.-С. 118-126.

[7] Копысов С. П., Альес М. Ю., Устюжанин С. Л. Сравнение способов уточнения в методе конечных элементов // Применение математического моделирования для решения задач в науке и технике. — Ижевск: Изд-во ИПМ УрО РАН, 1996. - С. 222-228.

[8] Альес М. Ю., Копысов С. П., Варнавский А. И. Реализация алгоритма Метрополиса на параллельной вычислительной системе // Матем. моделирование.— 1997. — Т. 9, № 2.— С. 97-101.

[9] Альес М. 10., Копысов С. П., Новиков А. К. Построение и адаптация конечно-элементной сетки при решении эллиптической задачи второго порядка // Матем. моделирование. — 1997.— Т. 9, № 2.— С. 43-45.

[10] Лукин О. Л., Копысов С. П., Альес М. Ю. Молекулярно-динамическое моделирование полимеров на параллельной вычислительной системе // Материалы Всероссийской научной школы-конференции по математическому моделированию, геометрии и алгебре. — Казань: Изд-во Казан, мат. об-ва, 1997.- С. 100-108.

[11] Альес М. Ю., Копысов С. П., Новиков А. К. Параллельное построение плоских конечно-элементных сеток // Матем. моделирование. — 1998. - Т. 10, № 5. - С. 71-76.

[12] Альес М. Ю., Варнавский А. И., Копысов С. П. Моделирование роста зерен методом Монте-Карло на изотропных решетках / / Инженерно-физический журнал. — 1999.— Т. 72, № 1,— С. 66-70.

[13] Kopyssov S.. Novikov A. Parallel Adaptive Mesh Refinement with Load Balancing for Finite Element Method // Lecture Notes in Computer Science.- 2001.- Vol. 2127.- Pp. 266-267.

[14] Kopyssov S. P., Ustyshanin S. L. Domain decomposition based on mechanical contact of substructures // International Conference OFEA'2001 «Optimization of Finite Element Approximations & Splines and Wavelets » (June 25-29, 2001).— St. Petersburg, Russia: 2001.— Pp. 77-78.

[15] Параллельное адаптивное уточнение в методе конечных элементов при решении задач деформирования / М. Ю. Альес, С. П. Копысов, А. К. Новиков, С. Л. Устюжанин // Труды VIII Всероссийского съезда по теоретической и прикладной механике ( 23 - 29 августа 2001 г., Пермь). - Пермь: ИМСС УрО РАН, 2001.- С. 40.

[16] Альес М. Ю., Копысов С. П., Новиков А. К. Параллельные схемы метода сопряженных градиентов // Труды Математического центра имени Н. И. Лобачевского. «Численные методы решения линейных и нелинейных краевых задач». — Т. 13. — Казань: Изд-во ДАС, 2001. — С. 170-180.

[17] Методы декомпозиции для решения задач деформирования с динамическим перестроением сеточных моделей / С. П. Копысов, М. Ю. Альес, А. К. Новиков, С. Л. Устюжанин // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения» (30.10.-2.11.2000, г. Черноголовка). — Черноголовка: Изд-во МГУ, 2001.- С. 119-123.

[18] Рынков В. Н., Красноперое И. В., Копысов С. П. Промежуточное программное обеспечение для высокопроизводительных вычислений // Вычислительные методы и программирование. — 2001.— Т. 2, № 2.— С. 117-132.

[19] Рынков В. #., Красноперое И. В., Копысов С. П. Построение ВС на основе параллельных распределенных компонентов // Труды третьей Всероссийской молодежной школы «Суперкомпьютерные вычислительно-информационные технологии в физических и химических исследованиях» (31 октября-1 ноября 2001 г.). — Черноголовка: ИПХФ РАН, 2001.-С. 84-88.

[20] Kopyssov S. P., Rychkov V. N., Ponomarev А. В. The integration CAD systems and unstructured mesh generations // Proceedings at

the workshop «Grid generation: theory and applications». — Moskow: Dorodnicyn Computing Centre RAS, 2002,- Pp. 218-229.

[21] Novikov A. N., Kopyssov S. P. Parallel element-by-element conjugate gradient method with decreased communications costs // The International Summer School «Iterative Methods and Matrix Computations» Editor Gene H. Golub, Lev A. Krukier, (2-9 June 2002).- Rostov-on-Don, Russia: 2002,- Pp. 450-454.

[22] Копысов С. П. Программное обеспечение динамической балансировки нагрузки // Материалы Международной конф. «СуперЭВМ и многопроцессорные вычислительные системы», (26-30 июня 2002).— Таганрог: ТРТУ, 2002,- С. 157-160.

[23] Копысов С. П., Михайлова Г. В., Новиков А. К. r-версия метода конечных элементов в задачах теории упругости // Материалы Международной науч-техн. конф., посвященной 50-летию ИжГТУ (19-22 фев. 2002г.).- Ижевск: Изд-во ИжГТУ, 2002,- С. 97-107.

[24] Копысов С. П., Новиков А. К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Матем. моделирование.— 2002. — Т. 14, № 9. — С. 91-96.

[25] Kopyssov S. P., Novikov А. К. Parallel Adaptive Mesh Refinement with Load Balancing on Heterogeneous Cluster // Parallel and Distributed Computing Practices. — 2002,— Vol. 5, no. 4.

[26] Рынков В. H., Красноперое И. В., Копысов С. П. Обьектно-ориентированная параллельная распределенная система для конечно-элементного анализа // Матем. моделирование.— 2002.— Т. 14, №9.-С. 81-86.

[27] Рынков В. Н., Красноперое И. В., Копысов С. П. Программное обеспечение МВС на основе параллельных распределенных компонентов CORBA // Материалы Международной конф. «СуперЭВМ и многопроцессорные вычислительные системы», (26-30 июня 2002).— Таганрог: ТРТУ, 2002.- С. 195-200.

[28] Копысов С. П. Динамическая балансировка нагрузки для параллельного распределенного МДО // Методы и средства обработки информации. - М.: МГУ, 2003. - С. 222-227.

[29] Копысов С. П., Красноперое И. В. Численное интегрирование в р-версии мкэ // Труды Математического центра имени Н. И. Лобачевского. «Численные методы решения линейных и нелинейных краевых задач», — Т. 20.— Казань: Изд-во Казанского мат. общества, 2003.— С. 161-169.

[30] Копысов С. П., Красноперое И. В., Рынков В. Н. Объектно-ориентированный метод декомпозиции области // Вычислительные методы и программирование, — 2003.— Т. 4, № 1.— С. 176-193.

[31] Копысов С. П., Красноперое И. В., Рынков В. Н. Реализация объектно-ориентированной модели метода декомпозиции области на основе параллельных распределенных компонентов CORJBA // Вычислительные методы и программирование. — 2003.— Т. 4, № 1.— С. 194-206.

[32] Копысов С. П., Новиков А. К. Сравнение способов перестроения треугольных конечно-элементных сеток // Труды Математического центра имени Н. И. Лобачевского. «Численные методы решения линейных и нелинейных краевых задач». — Т. 20.— Казань: Изд-во Казанского мат. общества, 2003.— С. 161-169.

[33] Копысов С. П., Сагдеева Ю. А. Многомасштабный анализ на основе МКЭ и вейвлет-преобразования // Труды Математического центра имени Н. И. Лобачевского. «Численные методы решения линейных и нелинейных краевых задач». — Т. 20. — Казань: Изд-во Казанского мат. общества, 2003,- С. 181-190.

[34] Object-oriented software for domain decomposition methods with local adaptive refinement / S. P. Kopyssov, I. V. Krasnoperov, A. K. Novikov, V. N. Rychkov // Parallel Computational Fluid Dynamics / Ed. by B. Chetverushkin, A. Ecer, J. Periaux et al. — Elsevier, 2004.— Pp. 425432.

[35] Копысов С. П. Оптимальное разделение области для параллельного метода подструктур // Материалы Всерос. семинара «Сеточные методы для краевых задач». — Казань: КГУ, 2004.— С. 121-125.

[36] Копысов С. П., Красноперое И. В. Адаптивное решение задач в р-версии метода конечных элементов // Прикладная геометрия, построение сеток и высокопроизводительные вычисления / Под ред. Ю. Г. Евтушенко, М. К. Керимов, В. А. Гаранжа. — М.: ВЦ РАН, 2004.-Т. 2,-С. 85-95.

[37] Копысов С. П., Новиков А. К. Параллельное адаптивное перестроение треугольной конечно-элементной сетки // Прикладная геометрия, построение сеток и высокопроизводительные вычисления / Под ред. Ю. Г. Евтушенко, М. К. Керимов, В. А. Гаранжа. — М.: ВЦ РАН,

2004,- Т. 1.— С. 167-178.

[38] Копысов С. П., Пономарев А. В., Рынков В. Н. Открытое визуальное окружение для взаимодействия с геометрическими ядрами, генерации/перестроения/разделения сеток и построения расчетных моделей // Прикладная геометрия, построение сеток и высокопроизводительные вычисления / Под ред. Ю. Г. Евтушенко, М. К. Керимов, В. А. Гаранжа. - М.: ВЦ РАН, 2004. - Т. 2. - С. 154-164.

[39] Parallel Distributed Object-Oriented Framework for Domain Decomposition / S. P. Kopyssov, I. V. Krasnopyorov, A. K. Novikov, V. N. Rytchkov // Lecture Notes in Computational Science and Engineering. — 2004. — Vol. 40. - Pp. 605-614.

[40] Копысов С. П., Варнавский А. И. Моделировние движения межзерен-ных границ поликристалического материала (Часть 1. Модель движения) // Вестник Томского государственного университета, — 2004.— № 32. - С. 50-58.

[41] Копысов С. П., Варнавский А. И. Моделировние движения межзерен-ных границ поликристалического материала (Часть 2. Результаты моделирования двухмерного роста зерен) / / Вестник Томского государственного университета. — 2004. — № 32. — С. 59-63.

[42] Параллельная распределенная объектно-ориентированная модель метода декомпозиции области / С. П. Копысов, И. В. Красноперов, А. К. Новиков, В. Н. Рычков // Проблемы термогазодинамики и прочности механических систем. — Ижевск: Изд-во ИПМ УрО РАН,

2005.-С. 124-140.

[43] Копысов, С. П. Совместное использование систем промежуточного программного обеспечения CORBA и MPI / С. П. Копысов, И. В. Красноперов, В. Н. Рычков // Материалы XIV Международной конференции по вычислительной механике и современным программным системам (25-31 мая 2005 г., Алушта, Крым). — М.: Вузовская книга, 2005.- С. 239-241.

[44] Копысов С. П., Сагдеева Ю. А. Вычислительные особенности и реализация вейвлет-осреднения в задачах многомасштабного анализа //

Вычислительные методы и программирование. — 2005. — Т. 6. № 1. — С. 5-12.

[45] Копысов С. П., Новиков А. К. Свидетельство об официальной регистрации программы для ЭВМ № 2005611347. Зарегистрировано в Реестре программ для ЭВМ 6 июня 2005 г.

[46] Копысов С. П., Сагдеева Ю. А. Вейвлет-осреднение в задачах теории упругости композитных материалов // Проблемы термогазодинамики и прочности механических систем. — Ижевск: Изд-во ИПМ УрО РАН, 2005.- С. 108-123.

[47] Копысов С. П., Новиков А. К. Динамическая балансировка вычислительной нагрузки параллельных сеточных методов // Материалы Всерос. семинара «Сеточные методы для краевых задач».— Казань: КГУ, 2005.- С. 137-140.

[48] Копысов С. П., Сагдеева Ю. А. Определение эффективного коэффициента теплопроводности с помощью вейвлет-осреднения // Материаловедение и обработка материалов. — Ижевск: Изд-во ИПМ УрО РАН, 2005.- С. 243-250.

[49] Расчетные неструктурированные сетки для распределенных вычислений / С. П. Копысов, А. Б. Пономарев, В. Н. Рычков, С. Н. Зубцов-ский // Сибирская школа-семинар по параллельным вычислениям / Под ред. А. В. Старченко. — Изд-во Том. ун-та, 2005.— С. 19-25.

[50] Копысов С. П., Красноперое И. В., Рычков В. Н. Совместное использование систем промежуточного программного обеспечения CORBA и MPI // Программирование. - 2006. - Т. 32, № 5. - С. 276-283.

[51] Kopyssov S. P., Novikov A. К. Parallel adaptive mesh refinement with load balancing on heterogeneous cluster // Algorithms and Tools for Parallel Computing On Heterogeneous Clusters / Ed. by F. Desprez, E. Fleury, A. Kalinov, A. Lastovetsky. — New York: Nova Science Publishers, 2006. — 10 p.

[52] Копысов С. П., Новиков А. К., Пономарев А. Б. Методы параллельного построения неструктурированных сеток // Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления / Под ред. Ю. Г. Евтушенко, М. К. Керимов, В. А. Гаранжа. — М.: ВЦ РАН, 2006.- С. 125-130.

Подписано в печать 27.11.2006 г. Формат 60 х 84/16. Усл. печ. л. 2,4. Тираж 100 экз. Заказ № 10

Типография ИПМ УрО РАН, 426067 г. Ижевск, ул. Т. Барамзиной, 34.

Введение

Список обозначений

I. Методы декомпозиции и параллельные вычисления

1.1. Метод разрывания

1.2. Методы декомпозиции области для аппроксимированных задач

1.2.1. Методы Шварца.

1.2.2. Метод декомпозиции, основанный на механическом взаимодействии подструктур.

1.2.3. Многофронтальный метод.

1.3. Методы подструктур

1.3.1. Вычислительные схемы.

1.3.2. Двухуровневая декомпозиция в методах подструктур

1.3.3. Иерархия подструктур.

1.4. Параллельные проекционные методы на подпространствах Крылова.

1.4.1. Метод сопряженных градиентов.

1.4.2. Сокращение числа обменов.

1.4.3. Блочная декомпозиция.

1.4.4. Поэлементная декомпозиция

1.4.5. Реберная декомпозиция.

1.4.6. Совмещение вычислений и обменов

1.5. Проектирование параллельных алгоритмов и программ

1.5.1. Декомпозиция.

1.5.2. Выбор промежуточного программного обеспечения

1.5.3. Разделение/распределение/увеличение вычислительной нагрузки процессоров.

И. Объектно-ориентированная декомпозиция в методе конечных элементов и методе декомпозиции области

2.1. Объектно-ориентированное программирование.

2.1.1. Объектно-ориентированное проектирование.

2.1.2. Объектно-ориентированная реализация.

2.2. Объектно-ориентированный подход к геометрии и расчетным сеткам

2.2.1. Модель CAE-системы.

2.2.2. Модель геометрического представления.

2.2.3. Модель конечно-элементной сетки.

2.2.4. Модель расчетных данных

2.2.5. Модель разделенной сетки

2.2.6. Модель распределенной сетки.

2.3. Объектная модель метода конечных элементов.

2.3.1. Основные шаги и уровни абстракции данных в методе конечных элементов

2.3.2. Сравнение программных моделей метода конечных элементов.

2.3.3. Трехуровневая объектно-ориентированная модель метода конечных элементов

2.3.4. Объектная модель адаптивного метода конечных элементов

2.4. Объектная модель метода декомпозиции области.

2.4.1, Метод декомпозиции области, основанный на конечно-элементной аппроксимации.

2.4.2. Построение моделей метода декомпозиции области

III. Модель параллельной распределенной системы метода декомпозиции области

3.1. Промежуточное программное обеспечение высокопроизводительных вычислений

3.1.1. Параллельные вычисления.

3.1.2. Распределенные вычисления.

3.1.3. Сравнение технологий MPI и CORBA.

3.2. Вычислительная модель метода декомпозиции области

3.2.1. Распределенные данные.

3.2.2. Параллельные процессы.

3.2.3. Балансировка нагрузки.

3.3. MPI-реализация метода декомпозиции.

3.3.1. Реализация объектов в MPI.

3.3.2. Распределенные данные.

3.3.3. Параллельные процессы.

3.3.4. Использование прикладных MPI-бйблиотек.

3.4. CORBA-реализация метода декомпозиции.

3.4.1. Реализация объектов в CORBA.

3.4.2. Распределенные данные.

3.4.3. Параллельные процессы.

3.5. Технология параллельных распределенных компонентов

3.5.1. Компонентная система

3.5.2. Распределенная компонентная система

3.5.3. Параллельная компонентная система.

3.5.4. Интеграция MPI и CORBA.

3.5.5. Реализация метода декомпозиции области на основе технологии параллельных распределенных компонентов

IV. Балансировка вычислительной нагрузки и разделение конечно-элементной сетки

4.1. Технологии балансировки нагрузки

4.1.1. Балансировка на уровне сети.

4.1.2. Балансировка на уровне операционной системы

4.1.3. Балансировка на уровне промежуточного программного обеспечения.

4.2. Балансировка на уровне пользовательского приложения

4.2.1. Постановка задачи.

4.2.2. Методы балансировки для сеточных задач.

4.2.3. Алгоритмы разделения графов.

4.2.4. Динамическая балансировка нагрузки и перераспределение

4.3. Сравнение методов балансировки нагрузки.

4.3.1. Балансировка нагрузки на уровне операционной системы и промежуточного программного обеспечения

4.3.2. Балансировка нагрузки на основе моделируемого отжига. Моделирование роста зерен.

4.3.3. Балансировка нагрузки в случае адаптивных сеток 209 4.4. Разделение расчетных сеток для неоднородных многопроцессорных вычислительных систем.

Численные примеры решения задач на основе методов декомпозиции

5.1. Параллельное построение неструктурированных сеток

5.1.1. Методы параллельного построения.

5.1.2. Метод сжатия текущей границы.

5.1.3. Триангуляция Делоне с ограничениями на плоскости

5.1.4. Построение трехмерной сетки многогранников Вороного

5.1.5. Разбиение на шестигранные элементы произвольной области.

5.2. Поэлементная декомпозиция задач на адаптивных сетках

5.2.1. h-версия метода конечных элементов

5.2.2. Оценка погрешности и критерий адаптации

5.2.3. Адаптивное перестроение сетки.

5.2.4. Декомпозиция алгоритма и разделение сетки

5.2.5. Численные примеры решения двумерных задач

5.2.6. Структура вычислительных затрат адаптивного алгоритма

5.3. Метод декомпозиции р-версии метода конечных элементов

5.3.1. Иерархические аппроксимации для шестигранных элементов

5.3.2. Адаптивное р-перестроение и оценка погрешности для элементов высокого порядка.

5.3.3. Методы декомпозиции для вложенных систем

5.3.4. Критерии разделения с адаптивным порядком аппроксимации

5.3.5. Примеры решения задач деформирования р-версией метода конечных элементов.

5.4. Конечно-элементное моделирование нелинейного деформирования зарядов РДТТ.

5.4.1. Выбор определяющих соотношений.

5.4.2. Адаптация сетки для задач с историей деформирования. r-версия метода конечных элементов.

5.4.3. Параллельное решение нелинейных систем.

5.4.4. Моделирование процессов деформирования зарядов при немонотонном нагружении.

5.5. Методы декомпозиции молекулярно-динамических моделей деформирования полимеров.

5.5.1. Описание модельной системы.

5.5.2. Схема интегрирования уравнений движения

5.5.3. Вычисление напряжений для ансамбля частиц

5.5.4. Методы декомпозиции молекулярно-динам ических моделей

5.5.5. Молекулярно-динамическое моделирование циклического нагружения.

5.5.6. Молекулярно-динамическое моделирование объемного модуля упругости

5.6. Многомасштабная декомпозиция систем уравнений метода конечных элементов.

5.6.1. Многомасштабный анализ.

5.6.2. Алгоритмические особенности вейвлет-преобразованияЗбб

5.6.3. Определение эффективных модулей упругости

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

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

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

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

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

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

Главные подходы управления адаптивным процессом, предназначенным для уменьшения погрешности МКЭ, следующие: движение узлов сетки без изменения связности (г-версии); локальное сгущение (перестроение) начальной сетки (h-eepcuu); повышение степени кусочно-полиномиальных базисных функций МКЭ (р-версии) и их комбинации.

Использование адаптивных методов конечных элементов неразрывно связано с декомпозицией расчетной области. Основные достоинства адаптивных версии МКЭ реализуется только при наличии быстрых алгоритмов решения соответствующих систем алгебраических уравнений. Среди экономичных алгоритмов наиболее приспособленным к системам МКЭ является метод декомпозиции области (МДО).

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

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

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

На сегодня не вызывает сомнений, что важным обстоятельством при осуществлении декомпозиции алгоритма и программы является необходимость ее проведения путем совместного анализа всех аспектов междисциплинарного построения параллельных алгоритмов, а именно: собственно прикладной задачи; математических моделей и методов; теоретического анализа по построению новых вычислительных алгоритмов, адаптации существующих алгоритмов; объектно-ориентированной технологии проектирования и программирования; архитектуры вычислительной системы.

Значительное влияние на выработку единой формулировки методов декомпозиции для адаптивных версий МКЭ, применяемой в диссертации, оказали своими трудами следующие ученые О. С. Zienkiewicz, I. Babuska, А.Д. Ляшко, Г.И. Марчук, J. Т. Oden (теория и конструирование конечно-элементных аппроксимаций); С.Г. Михлин, JI.A. Оганесян, С.И. Репин, Е. 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 наименования.

Результаты исследования зависимости решения (а именно, поля перемещений в плоском случае по координатам х и у) от степени усечения h даны в табл. 5.10. В ней представлена относительная погрешность реь зультатов для сеток 32 х 32, 64 х 64 и сеток, получающихся после одного шага осреднения. Использовались следующие схемы усечения: отбрасывались элементы, лежащие вне главной диагонали на расстоянии большем, чем h (h равна 1/3, 1/2 или 2/3 ширины ленты) и меньшие по модулю чем атах/1000, где атах — максимальный элемент соответствующей матрицы. Из приведенных результатов видно, что чем меньше шаг

Заключение

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

Построены новые алгоритмы адаптивного МКЭ с перестроением сетки и повышением порядка аппроксимациии, которые включает параллельные алгоритмы: формирования и решения систем нелинейных и линейных уравнений, апостериорной оценки погрешности, локального перестроения сетки/повышения порядка аппроксимации элементов и динамической балансировки вычислительной нагрузки. Исследована их эффективность и структура вычислительных затрат.

Предложены и обоснованы алгоритмы параллельной генерации больших треугольных и трехмерных неструктурированных расчетных сеток на основе разделения геометрии и грубой сетки сокращающие затраты на передачу данных между последовательным построением сетки и параллельным приложением со статической балансировкой нагрузки процессоров. Рассматриваемый подход минимизирует ввод/вывод и накладные расходы пересылок данных, устраняя избыточные операции. Результаты показывают, что такой подход в несколько раз работает быстрее, чем традиционный подход построения, разделения и распределения неструктурированных сеток. Построены новые параллельные алгоритмы перестроения сетки, на основе деления элементов по наибольшей стороне и "новейшему узлу". Исследовано влияние алгоритма перестроения на изменения шага сетки и внутренних углов в треугольных ячейках сетки.

Предложены и исследованы методы разделения расчетной сетки, динамической балансировки вычислительной нагрузки и перераспределения сеточных объектов для адаптивных схем МКЭ на основе геометрических и графовых моделей расчетной сетки и неоднородной вычислительной системы. Проведены сравнение алгоритмов балансировки на различных уровнях взаимодействия с приложением.

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

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

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

1. Крон, Г. Исследование сложных систем по частям - диакоптика / Г. Крон. - М.: Наука, 1972. - 544 с.

2. Агошков, В. И. Операторы Пуанкаре-Стеклова и методы разделения области в вариационных задачах / В. И. Агошков, В. И. Лебедев // Вычислительные процессы и системы / Под ред. Г. И. Марчука. — Вып. 2. М.: Наука, 1985. - С. 173-227.

3. Агошков, В. И. Методы разбиения области в задачах математической физики / В. И. Агошков If Вычислительные процессы и системы / Под ред. Г. И. Марчука.— Вып. 8.— М.: Наука, 1991.— С. 4-50.

4. Кузнецов, Ю. А. Итерационные методы в подпространствах / Ю. А. Кузнецов. М.: Наука, 1984. - 134 с.

5. Видлунд, О. Б. Итерационные методы разбиения на подструктуры. Общий эллиптический случай. / О. Б. Видлунд // Вычислительные процессы и системы / Под ред. Г. И. Марчука. — Вып. 6. — М.: Наука, 1988.-С. 94-121.

6. Самарский, А. А. Аддитивные схемы для задач математической физики / А. А. Самарский, П. Н. Вабищевич. — М.: Наука, 1999. — 319 с.

7. Пржеминицкий, А. Н. Матричный метод исследования конструкций на основе подструктр / А. Н. Пржеминицкий // Ракет, техника и космонавтика. — 1963. — № 1. — С. 165-174.

8. Мейснер, К. Алгоритм многосвязного объединения для метода жест-костей структурного анализа / К. Мейснер j j Ракет, техника и космонавтика. 1968. — № 11. - С. 176-177.

9. Метод суиерэлементов в расчетах инженерных сооружений / В. А. Постнов, С. А. Дмитриев, Б. К. Елтышев, Л. А. Родионов. — Л.: Судостроение, 1979. — 287 с.

10. Вороненок, Е. -Я. Метод редуцированных элементов для расчета конструкций / Е. Я. Вороненок, О. М. Палий, С. В. Сочинский. — Л.: Судостроение, 1990. — 224 с.

11. Соболев, С. Л. Алгоритм Шварца в теории упругости / С. Л. Соболев // ДАН СССР. 1936. - Т. 4, № 6. - С. 235-238.

12. Хокни, Р. Численное моделирование методом частиц / Р. Хокни, Д. Иствуд. М.: Мир, 1987. - 400 с.

13. Канторович, Л. В. Приближенные методы высшего анализа / Л. В. Канторович, В. И. Крылов, — Л.: Физматгиз, 1962.— 708 с.

14. Калик, К. К вопросу о сходимости алгоритмов типа Шварца / К. Калик // Изв. Вузов. Математика. — 1959.— Т. 8, № 1.

15. Никольский, Е. Н. Алгоритм Шварца в задаче теории упругости в напряжениях / E. Н. Никольский // ДАН СССР. 1960. - Т. 135, X» 3. — С. 549-552.

16. Цвик, Л. Б. Обобщение алгоритма Шварца на случай областей, сопряженных без налегания / Л. Б. Цвик // ДАН СССР. — 1975. — Т. 224, № 2. С. 309-312.

17. Методы декомпозиции для решения задач деформирования с динамическим перестроением сеточных моделей / С. П. Копысов, М. Ю. Альес, А. К. Новиков, С. Л. Устюжанин // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и