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

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

Иванов Евгений Геннадьевич

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

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

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

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

ооз

003161558

Работа выполнена в Институте теоретической и прикладной механики им С А Христиановича Сибирского отделения РАН (г Новосибирск)

Научные руководители кандидат физико-математических наук,

старший научный сотрудник Кудрявцев Алексей Николаевич

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

профессор Лисейкин Владимир Дмитриевич

доктор физико-математических наук Попов Владимир Николаевич

Ведущая организация Институт математического моделирования РАН,

г Москва

Защита диссертации состоится « 3 » 2007 г в ^

на заседании диссертационного совета Д 003 046 01 при Институте Вычислительных Технологий СО РАН по адресу пр ак Лаврентьева, 6, 630090, г Новосибирск, Россия

С диссертацией можно ознакомиться в специализированном читальном зале вычислительной математики и информатики ГПНТБ СО РАН

3/0

Автореферат разослан « ^ » О^ЫМ^^^^-

2007 г

Ученый секретарь

диссертационного совета /7 С/

Д 003 046 01, д ф -м н , профессор // /у ^ ^ Чубаров Л Б

, профессор ^/

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

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

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

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

В то же время, использование неструктурированных сеток обычно усложняет численный алгоритм и требует дополнительной памяти для хранения информации о связях ячеек сетки Еще один недостаток неструктурированных сеток, который является причиной дополнительной вычислительной работы, связан с увеличением числа ячеек, граней ячеек и ребер по сравнению с шестигранными сетками Например, тетраэдральная сетка из N узлов имеет примерно 6А*" ячеек, 12N граней, 7Ы ребер, в то время как шестигранная сетка примерно состоит из N ячеек, ЗЫ граней, ЗИ ребер В результате численные алгоритмы, основывающиеся на неструктурированной топологии сетки, являются наиболее трудоемкими в плане количества операций на шаг времени и памяти на узел сетки

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

В настоящее время сетки с размером, превышающим 107 элементов,

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

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

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

Разработки параллельных алгоритмов для решения различных задач ведутся во многих институтах Академии наук Наиболее известные — это работы О М Белоцерковского, Б Н Четверушкина, А В Забродина, Ю А Кузнецова и их учеников Методам разложения расчетной области были посвящены работы Ю А Кузнецова и П Н Вабищевича и др

Целями данной работы являются

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

2 Сравнение и анализ алгоритмов параллельного построения тетраэдральных сеток

3 Исследование методов и критериев декомпозиции расчетной области для достижения наилучшего баланса загрузки процессоров

4 Создание комплекса программ для параллельного построения нес-

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

Научная новизна Фактически проблема параллельного построения сетки возникла совсем недавно По сведениям автора наиболее серьезные работы по параллельной генерации расчетных сеток ведутся только в двух отечественных организациях — в ИММ РАН, где в рамках проекта СТММ под руководством Б Н Четверушкина был создан параллельный генератор тетраэдральных сеток, использующий метод, основанный на грубом начальном разбиении области, и в ИПМ УрО РАН С П Копысовым и др , давшими краткое описание основных методов параллельного построения сеток В представленной работе

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

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

3 Разработан новый алгоритм улучшенного формирования разделяющего контура, играющий ключевую роль в качестве получаемого разбиения

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

5 Разработан новый алгоритм улучшенного формирования разделяющего контура, играющий ключевую роль в качестве получаемого разбиения

6 Составлен параллельный расчетный код, производящий автоматическую генерацию сеток

7 Решен ряд практических задач построения пространственной сетки — в цилиндрической области (как примере объекта простой формы), для компонента коленного протеза и крышки подшипника автомобиля При построении сеток использовалось до 128-ми процессоров Сетка,

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

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

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

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

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

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

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

— Программный комплекс, позволяющий производить автоматическое построение тетраэдральных сеток на многопроцессорных ЭВМ

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

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

— Всемирном конгрессе по вычислительным наукам, компьютерной инженерии и прикладным вычислениям 2007 (WORLDCOMP07), Международная конференция по параллельным и распределенным методам обработки и приложениям (PDPTA 07), Лас Вегас, Невада, США

— Всероссийской конференции «Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления», ВЦ им А А Дородницына РАН, г Москва, Россия,

— Конференции по вычислительной гидродинамике Европейского сообщества по вычислительным методам в прикладных науках (EC-COMAS), Эгмонд аан Зее, Голландия,

— Молодежной конференции «Устойчивость и турбулентность течений гомогенных и гетерогенных жидкостей», ИТПМ им С А Христиановича СО РАН, Новосибирск, Россия,

— IV Международной конференции Научно-технической ассоциации развития образования, базирующегося на интернет-технологиях (IAST-ED), г Гриндельвальд, Швейцария,

— Корейско-японском университетском симпозиуме по инженерным

наукам (ЛБЯМЕ), г Йокогама, Япония,

— Международной конференции Корейского общества прикладной вычислительной аэрогидродинамики, г Тэгу, Южная Корея,

а также на научных семинарах в России и за рубежом, включая

— семинар Института математики им С Л Соболева СО РАН (Новосибирск) «Постановки задач, допускающих распараллеливание на многопроцессорных вычислительных системах» под руководством академика РАН С К Годунова,

— семинар Института математического моделирования РАН (Москва) под руководством чл -корр РАН Б Н Четверушкина,

— семинар «Математическое моделирование в механике» ИТПМ им С А Христиановича СО РАН (Новосибирск) под руководством академика РАН В М Фомина, проф А В Федорова,

— семинар «Информационно-вычислительные технологии», Институт Вычислительных Технологий СО РАН под руководством академика Ю И Шокина, проф В М Ковени

— семинар отдела компьютерных наук, Эрланген-Нюрнберг университет под руководством проф У Рюде — семинар «Аэрогазодинамика» ИТПМ им С А Христиановича СО РАН (Новосибирск) под руководством проф А А Маслова,

— семинар «Механика вязкой жидкости и турбулентность» ИТПМ им С А Христиановича СО РАН (Новосибирск) под руководством проф В В Козлова,

— семинар Института индустриальной математики им Фраунгофера (отдел высокопроизводительных вычислений), г Кайзераслаутерн, Германия,

— семинар факультета математики Технического университета г Кайзерслаутерн, Германия,

— семинар компании БКТЕНЕ (Национальный институт исследований по информатике и автоматике, Франция),

— семинар компании ЖЩЕСА (приложения вычислительной механики, Бельгия), г Брюссель, под руководством проф Шарля Хирша

Публикации По теме диссертации опубликовано 12 работ, в том числе (в скобках в числителе указан общий объем этого типа публикаций, в знаменателе - объем, принадлежащий лично автору), 1 статья в издании рекомендованном ВАК для представления результатов докторских диссертаций (10/10 печ л), 1 - в международных рецензируемых журналах (10/0 5 печ л), 2 - в трудах всероссийских конференций (0 9/0 5 печ л), 6 - в трудах

международных конференций (4 6/2 6 печ л ), 2 - в других печатных международных изданиях (20/1 3 печ л )

Благодарности Автор выражает благодарность научному руководителю к ф -м н АН Кудрявцеву за постоянное внимание и ценную помощь, академику РАН С К Годунову за проявленный интерес к работе и ряд важных замечаний, члену-корреспонденту РАН Б Н Четверушкину за обсуждение результатов и тематики параллельного построения сеток, к ф -м н В А Гараноюе за полезные замечания по улучшению алгоритма, а также Димитару Стоянову, Роберту Циллиху, Олегу Илиеву Отдельная благодарность Францу-Йозефу Пфройндту, благодаря которому стало возможным появление этой работы

Диссертационная работа выполнена при поддержке DAAD (Немецкая служба академических обменов) в рамках программы «Sandwich PhD гп Industrial Mathematics» при сотрудничестве Института теоретической и прикладной механики им CA Христиановича СО РАН (г Новосибирск), Института индустриальной математики им Фраунгофера (Fraunhofer ITWM, Германия) и Технического университета г Кайзерслаутерна (Германия)

Структура и объем работы Диссертационная работа состоит из введения, пяти глав, сорока семи параграфов, заключения, списка литературы, содержит 45 рисунков и одну таблицу Объем работы 115 страниц Библиографический список включает 149 наименований

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

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

Во второй главе, посвященной параллелизации и методам декомпозиции расчетной области, дано объяснение причин

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

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

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

1. Сбалансированное разделение объекта на непересекающиеся подобласти;

(a) вычисление центра масс и тензора инерции для установки режущей плоскости,

(b) сглаживание контура поперечного сечения для последующего проецирования,

(c) проецирование контурных узлов на плоскость для дальнейшей триангуляции,

2. Построение двумерной ограниченной триангуляции Делоне внутри спроецированного контура;

3. Возвращение контурных узлов триангуляции на исходные позиции;

4. Построение замкнутой и совместимой поверхностной сетки для каждой подобласти;

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

Блок-схема алгоритма параллельного генератора сеток изображена на рисунке 1

Рис. 1. Блок-схема параллельного генератора сеток

В четвёртой главе обсуждается программная реализация предложенных алгоритмов Приводятся принятые в работе модель параллельных вычислений (модель обмена сообщениями) и модель программирования (одна программа — много данных) Описываются используемые свободно распространяемые программные пакеты для двумерной (Triangle) и трехмерной (TetGen) триангуляций, подключаемые в качестве библиотек к разработанному расчетному коду

Приводится организация межпроцессорных коммуникаций на основе библиотеки MPI (Message Passing Interface), а также краткое описание используемых процедур пакета LAPACK (Linear Algebra Package) Уделено внимание описанию программы решения задач механики деформируемого твердого тела DDFEM (Domain Decomposition Finite Element Method) и ее интеграции с параллельным генератором сеток

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

Были построены сетки с различным количеством элементов ( 3 105 , 4 106 и 3 1 107 ) В первом случае построение сетки на одном процессоре занимало 15 — 18 секунд, во втором — несколько минут В обоих этих примерах время построения было уменьшено в несколько десятков раз за счет использования разработанного параллельного генератора сеток На рисунке 4 дан график ускорения построения пространственной сетки для 4 106 Здесь ускорение — это отношение времени работы на одном процессоре ко времени работы на N процессорах

Наиболее показательным является третий случай, где было построено 30953355 тетраэдральных элементов Построение такой сетки обычным последовательным образом на одном процессоре (Xeon 2 4 GHz / 4Gb RAM) оказывается невозможным после получаса работы триангулятор выдает ошибку о переполнении памяти Зато параллельный генератор выполняет построение этой сетки на восьми процессорах не более чем за четыре минуты (237 17 секунд)

Особое внимание уделено оценке и контролю качества поверхностной и пространственной сеток На рисунке 5 даны результаты сравнения качества пространственной сетки, построенной параллельным (справа) и последовательным (слева) образом Здесь показано распределение тетраэдральных элементов по качеству — единице соответствуют правильные тетраэдры, с ухудшением формы тетраэдра значение коэффициента уменьшается

Проведен анализ вычислительного времени и оценки трудоемкости, а также суммарной площади интерфейсов, определяющей объем впоследствии пересылаемых данных Разработанный параллельный генератор был использован для численного исследования напряженно-деформированного состояния крышки подшипника под влиянием сил, действующих на нее в двигателе, с помощью кода DDFEM, разработанного в Институте индустриальной математики им Фраунгофера На рисунке 6 приведены результаты расчетов нагрузки (вверху) и деформации (внизу) При этом решение показано на недеформированной (слева) и деформированной (справа) сетке, где множитель деформации 436 812 был использован для лучшего зрительного восприятия изменения формы крышки подшипника

Уровень разложения / Кол-во процессоров

3 8

4 -16

5 -32

6 -64

7 -

128

Рис. 2. Априорная декомпозиция крышки подшипника для 128-ми

процессоров.

Рис. 3. Декомпозиция и параллельное построение пространственной сетки крышки подшипника на 32-х процессорах (показано разными цветами).

Рис. 4. Ускорение времени построения объёмной сетки для крышки подшипника (показано красным) без времени разделения. Более 4 ООО ООО тетраэдральных элементов.

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

Рис. 6. Нагрузка крышки подшипника на недеформированпой и деформированной сетке; смещение узлов сетки крышки подшипника на недеформированпой и деформированной сетке. (Множитель деформации

436.812).

В конце главы отмечены преимущества разработанного алгоритма и перспективы его развития

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

— В отличие от сложных алгоритмов, используемых в других методах построения сеток, предложенный алгоритм состоит из последовательности простых шагов

— Параллелизация основывается на геометрическом разделении области на подобласти, что является естественным процессом

— Алгоритм позволяет использование проверенных и хорошо отлаженных последовательных двумерных и трехмерных триангуляторов, которые широко доступны Таким образом, параллельный генератор сеток может быть легко реализован и / или модифицирован

— Алгоритмом достигается 100% вторичного использования программного кода, а также полностью устраняется необходимость коммуникации и синхронизации процессов

— Несмотря на все преобразования и декомпозицию, сохраняет неизменной исходную поверхностную сетку

— Генерирует почти плоские интерфейсы, те границы раздела с малыми возмущениями между подобластями, что немаловажно для размера площади интерфейса

— Использует критерий декомпозиции, который минимизирует площадь интерфейса и чувствителен как к форме объекта, так и к разрешению сетки

Основные результаты работы

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

2 Исследованы различные методы априорной декомпозиции трех-

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

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

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

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

Список основных работ по теме диссертации

публикации в издании, рекомендованном ВАК

1 Ivanov Е G Automatic Parallel Generation of Three-Dimensional Unstructured Grids for Computational Mechanics // Вычислительные технологии - 2006 - T11 - № 1 - С 3-17

публикации в международных рецензируемых журналах

2 Ivanov Е G , Andra Н , Kudryavtsev А N Domain Decomposition Approach for Automatic Parallel Generation of Tetrahedral Grids // Comput Meth m Applied Mathematics - 2006 - V 6 - № 2 - P 178-193

публикации в трудах всероссийских конференций

3 Ivanov Е G , Andra Н , Kudryavtsev А N Automatic Parallel Gener-

ation of Tetrahedral Grids by Using a Domain Decomposition Approach // Труды Конференции «Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления», Москва, Россия - 2006 - С 115-124

4 Иванов Е Г Автоматическое параллельное генерирование трехмерных неструктурированных сеток / / Труды X конференции «Устойчивость и турбулентность течений гомогенных и гетерогенных жидкостей», Новосибирск - 2005 - С 79-82

публикации в трудах международных конференций

5 Ivanov Е G , Gluchshenko О N , Andra Н , Kudryavtsev А N Efficient parallel algorithm and software for automatic generation of 3D computational tetrahedral meshes // Proceedings of the 2007 World Congress m Computer Science, Computer Engineering and Applied Computing, PDP-TA 07 - International Conference on Parallel and Distributed Processing Techniques and Applications), Las Vegas, Nevada, USA, 2007 - P 285-292

6 Ivanov E G , Andra H , Kudryavtsev A N Domain Decomposition Approach for Automatic Parallel Generation of Three-Dimensional Unstructured Grids // Proc «European Conference on CFD (ECCOMAS CFD 06)», Egmond aan Zee, The Netherlands - 2006 - Paper No 295

7 Ivanov E G , Song D J Implementation of Preprocessor for CSCM code by using Graphic User Interface // Proc Conf «Korean Society of Computational Fluids Engineering», Daegu, South Korea - 2003 - P 69-75

8 Juraeva M , Ivanov E G , Song D J Teaching Computational Fluid Dynamics via Internet // Proc 4th IASTED Intern Conference on Web-Based Education, Grmdelwald, Switzerland - 2005 - Paper No 461-016

9 Ivanov E G , Lim S , Song D J Implementation of Preprocessor for CSCM Navier - Stokes code by using Graphic User Interface // Joint Symposium between Sister Universities m Mechanical Engineering (JSSME), Yokohama, Japan - 2004 - P 75-91

10 Ivanov E G , Juraeva M , Song D J Implementation of Full Web-based Graphic User Interface Processor for CFD software // Proc Conference of «Korean Society of Computational Fluids Engineering», South Korea -2004 - P 121-125

другие печатные издания

11 Ivanov E G , Andra H , Kudryavtsev A N Domain Decomposition Approach for Automatic Parallel Generation of Tetrahedral Grids / / Eraunhofer ITWM Bencht - 2006 - № 87

12 Ivanov E G , Gluchshenko О N , Andra H , Kudryavtsev A N Parallel Software Tool for Decomposing and Meshmg of 3D Structures // Eraunhofer ITWM Bencht - 2007 - № 110

Подписано к печати 2 октября 2007 г Тираж 100 экз Заказ № 616 Отпечатано "Документ-Сервис", 630090, Новосибирск, Институтская 4/1, тел 335-66-00

Введение

I. Основные понятия и принципы построения расчётных сеток

1.1. Классы расчётных сеток.

1.2. Неструктурированные расчётные сетки.

1.3. Методы построения неструктурированных расчётных сеток 17 1.3.1. Методы построения, основывающиеся на критерии

Делоне. i 1.4. Триангуляция Делоне.

1.4.1. История появления триангуляции Делоне.

1.5. Существование двумерной и трёхмерной триангуляции

1.6. Обзор работ по построению неструктурированных расчётных сеток.

II. Параллелизация и методы декомпозиции расчётной области 30 2.1. Необходимость параллелизации построения расчётной сетки 2.2. Параллельные вычисления.

2.3. Апостериорный метод разделения расчётной области

2.4. Априорный метод разделения расчётной области.

2.4.1. Виды и критерии декомпозиции расчётных областей

2.5. Обзор работ по параллельным вычислениям.

III. Алгоритм параллельного построения расчётной сетки

3.1. Постановка задачи и цели алгоритма.

3.2. Описание алгоритма и его главных шагов.

3.3. Установка разделяющих плоскостей и балансировка загрузки.

3.3.1. Эволюция алгоритма сбалансированного разделения

3.3.2. Ориентация поверхностных треугольников.

3.3.3. Метод сравнения объёмов, заключённых поверхностной триангуляцией.

3.3.4. Метод инерциальной бисекции.

3.4. Формирование разделяющего контура.

3.4.1. Прямой контур методом дробления треугольников

3.4.2. Улучшенная техника построения ломаного контура из поверхностных рёбер.

3.5. Построение интерфейса и его триангуляции Делоне

3.6. Разделение объекта вдоль контура рёбер.

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

3.8. Параллельное построение пространственной сетки.

IV. Программное обеспечение параллельного генератора

I сеток

4.1. Параллельная реализация программы.

4.1.1. Архитектура вычислительной системы и модель параллельных вычислений

4.1.2. Модель параллельного генератора сеток.

4.2. Программные пакеты 2D и 3D триангуляций.

4.2.1. Двумерная триангуляция. Пакет Triangle.

4.2.2. Трёхмерная триангуляция. Пакет TetGen.

4.3. Решение задач линейной алгебры. Пакет LAPACK. 4.4. Интеграция параллельного генератора сеток с DDFEM

4.4.1. DDFEM - параллельная программа, решающая задачи упругости.

4.4.2. DDFEM и параллельный генератор сеток.

V. Анализ результатов расчётов практических задач

5.1. Построение расчётной пространственной сетки компонента коленного протеза.

5.2. Построение расчётной пространственной сетки крышки подшипника.

5.3. Оценка качества расчётной сетки.

5.3.1. Качество поверхностной триангуляции.

5.3.2. Качество тетраэдральной сетки.

5.4. Вычислительные затраты и сокращение времени вычисления 95 5.4.1. Эффект суперлинейного ускорения.

5.5. Оценка суммарной площади поверхностей сопряжения

5.6. Преимущества разработанного алгоритма.

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

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

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

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

Использование неструктурированных сеток усложняет численный алгоритм необходимостью обработки данных, которые требуют наличия специальной программы для нумерации узлов, рёбер, граней, ячеек сетки, и дополнительной памяти для хранения информации о связях ячеек сетки. Ещё один недостаток неструктурированных сеток, который является причиной дополнительной вычислительной работы, связан с увеличением числа ячеек, граней ячеек и рёбер по сравнению с шестигранными сетками. Например, тетраэдральная сетка из N узлов имеет примерно 6УУ ячеек, 12ЛГ граней, 7УУ рёбер, в то время как шестигранная сетка примерно состоит из N ячеек, ЗN граней, ЗУУ рёбер. В результате численные алгоритмы, основывающиеся на неструктурированной топологии сетки, являются наиболее трудоёмкими в плане количества операций на шаг времени и памяти на узел сетки.

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

Сетки размером, превышающим 107 элементов уже становятся обычными для промышленного моделирования в вычислительной электродинамике [99,100] и вычислительной аэрогидродинамике [101,102, 103,104,105]. Ожидается, что в скором будущем будут требоваться сетки, превышающие 108 — 109 элементов [106].

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

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

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

• Долгое время вычисления. Параллельные вычисления позволяют значительно сократить время построения сетки. Это особенно полезно, когда требуется частое пересчитывание сетки.

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

Целями данной работы являются:

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

2. Сравнение и анализ алгоритмов параллельного построения тетраэдральных конечноэлементных сеток;

3. Исследование методов и критериев декомпозиции расчётной области для достижения наилучшего баланса загрузки процессоров;

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

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

Диссертационная работа состоит из введения, пяти глав, сорока семи параграфов, заключения, списка литературы, содержит 45 рисунков и одну таблицу. Объём работы 115 страниц. Библиографический список включает 149 наименований.

1. Разработай новый алгоритм автоматического иараллельного

иостроеиия трёхмерных неструктурированных тетраэдральных

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

сохраняющий исходную иоверхностную сетку. 2. Исследованы различные методы анриорной декомиозиции

трёхмерных расчётных областей (вдоль одного наиравлення,

рекурсивное разложение, сверхразложение) и критерии разделения

(делеиие равноудалёпиыми нлоскостями, равенство объёмов

иодобластей, равенство моментов инерции нодобластей). Было

иоказаио, что из рассмотренных методов рекурсивное разделение

плоскостью но критерию равенства инерции даёт наилучший

результат, так как минимизирует нлощадь иоверхностн соиряжения

и чувствительно как к форме объекта, так н к разрешению расчётной

сеткн. 3. Создан нрограммный комплекс на основе предложенного алгоритма,

включающий свободио распростраияемые пакеты (Triangle, Tet-

Gen), который является полностью автоматическим и может быть

использован с различными программами, решающими уравнения

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

расчётных сеток, ностроеиных параллельным и последовательным

образом, нолучена оценка суммарной площади поверхностей

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

пространственной сетки при изменении количества узлов сетки

и количества нроцессоров (нодобластей). Показано, что разлнчия в

качестве являются незначительными, время ностроення сокращается

в десятки раз, а при малом количестве процессоров достигается

эффективность более 100%. 5. Разработанный алгоритм построения прострапствеппых сеток был

применён при решеиии практических задач — исследования

компонента коленного протеза и напряжённо-деформированного сос тояння крышки нодшипника автомобиля (с иснользованием 128

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

расчётных сеток достигал 10^ — 10^ элементов. Построение сеток

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

крайне затрудннтельным.

1. Thacker W.C. A brief review of techniques for geneational grids // 1.t. J. Numer. Meth. Engng. - 1980. - V. 15. - №9. - P. 1335-1341.

2. Ho-Le. Finite element mesh generation methods: a review and classification. // Computer Aided Design. 1988. - V. 20. - P. 27-38.

3. Shephard M.S.,Grice K.R., Lot J.A., Schroeder W.J. Trends in automatic three-dimensional mesh generation. // Comput. Strict. 1988. - V. 30. -№1/2 - P. 421-429.

4. Baker T.J. Mesh adaptation strategies for problems in fluid dynamics. // Finite Elements Anal. Design 1995. - V. 25. - P. 243-273.

5. Field D.A. The legacy of automatic mesh generation from solid modeling. // Сотр. Aided Geom. Design 1995. - V. 12. - P. 651-673.

6. Carey G.F. Computational Grids. Generation, Adaptation, and Solution Strategies, Taylor and Francis, London, 1997.

7. George P.L., Borouchaki H. Delaunay Triangulation and Meshing Editions Hermes, Paris, 1992.

8. Krugljakova L.V.,Neledova A.V., Tishkin V.F., Filatov A.Yu. Unstructured adaptive grids for problems of mathematical physics. // Math. Modeling. 1998. - V. 10. - №3 - P. 93-116.

9. Thompson J.F., Weatherill N.P. Aspects of numerical grid generation: curent science and art. // AIAA Paper 93-3539 1993.

10. Скворцов A.B. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование 2002. - Т. 3. -С. 14-39.

11. Dirichlet G.L. Ueber die reduction der positiven quadratischen formen-mit drei understimmten ganzen zahlen. // Z. Angew Math. Mech 1850.- V. 40. m - P. 209-227.

12. Voronoi G. Nouvelles applications des paramétres continus a la théorie des formes quadratiques. Recherches sur les parallélloédres primitifs // Journal Reine angew. Math.- 1908. V. 134.

13. Green P., Sibson R. Computing Dirichlet tesselation in the plane. // Comput. Journal 1978. - V. 21. - №3 - P. 168-173.

14. Lawson C.L. Software for Cl surface interpolation. // Math. Soft., 3, J. Rice ed., Academic Press, New York. 1977.

15. Hermeline F. Une méthode automatique de maillage en dimension n. // Thèse, Université Paris VI, Paris.

16. Bowyer A. Computing Dirichlet tesselation // The Comp. J. -1981. V. 24. - №2 - P. 162-167.

17. Watson D.F. Computing the n-dimensional Delaunay Tesselation with applications to Voronoi polytopes // Computer Journal 1981. - V. 24.- M P. 167-172.

18. Avis D., Bhattacharya B.K. Algorithms for computing d-dimensional Voronoi diagrams and their duals, // Advances in computing research -1983. V.l. - P. 159-188.

19. Schoenhardt E. Uber die Zerlegung von Dreieckspolyedern in Tetraeder // Mathematische Annalen 1928. - V.98. - P. 309-312.

20. Bagemihl F. On Indecomposable Polyhedra // American Mathematical Monthly 1948. - V.55. - P. 411-413.

21. Chazelle B. Convex Partition of Polyhedra: A Lower Bound and Worst-case Optimal Algorithm // SIAM Journal on Computing 1984. - V.13.- №. P. 488-507.

22. Rambau J. On a Generalization of Schoenhardt's Polyhedron // MSRI Preprint 2003. - V.13.

23. Ruppert J., Seidel R. On the difficulty of triangulating three-dimensional non-convex polyhedra // Discrete and Computational Geometry 1992. - V.7. - P. 227-254.

24. Shewchuk J.R. Constrained Delaunay tetrahedralizations and provably good boundary recovery // 11th International Meshing Roundtable -2002. P. 193-204.

25. Pebay P. A Priori Delaunay-Conformity // 7th International Meshing Roundtable 1998.

26. Murphy M., Mount D.M., Gable C.W. A point-placement strategy for conforming Delaunay tetrahedralization // Proceedings of the 11th Annual Simposium on Discrete Algorithms 2002. - P. 67-74.

27. Cohen-Steiner D., de Verdiere E. Yvinec M. Conforming Delaunay triangulations in 3D // Proceedings of the 18th Annual Simposium on Computational Geometry 2002.

28. Si H., Gaertner K. An algorithm for three-dimensional constrained Delaunay Tetrahedralizations // Proceedings of the 4th International Conference on Engineering Computational Technology 2004.

29. Liseikin V.D. Grid Generation Methods Springer-Verlag Berlin Heidelberg - 1999.

30. Avis C.L. Properties of n-dimensional triangulations. // Comp. Aided Geom. Design 1986. - V.2. - P. 231-246.

31. Henle M. A combinatorial Introduction to Topology. W.H. Freeman, San Francisco.

32. Steinitz E. Polyeder and Raumeintailungen. // Enzykl. Mathematischen Wiss. 1922. - V.3. - P. 163.

33. Klee V. The number of vertices of a convex polytope. // Can. Math -1964. V.16. - P. 37.

34. Lee K.D. On finding k-nearest neighbours in the plane. // Tech. Report 76-2216. University of Illinois, Urbana, IL 1976.

35. Delaunay B.N. Sur la sphere vide. // Bull. Acad. Sei. USSR VII: Class. Sei. Mat. Nat. 1934. - V.3. - P. 793-800.

36. Delaunay B.N. Peterburg School of Number Theory. // Acad. Sci. USSR, Moscow 1947.

37. Brostow W., Dussault J.P., Fox B.L. Construction of Voronoi polyhedra. // J. Comput. Phys. 1978. - V.29. - P. 81-92.

38. Finney J.L. A procedure for the construction of Voronoi polyhedra. // J. Comput. Phys. 1979. - V.32. - P. 137-143.

39. Tanemura M., Ogawa T., Ogita N. A new algorithm for three-dimensional Voronoi tesselation. // J. Comput. Phys. 1983. - V.51. - P. 191-207.

40. Sloan S.W., Houlsby G.T. An implementation of Watson's algorithm for computing 2D Delaunay triangulations. // Advances Engng. Software -1984. V.6. - № - P. 192-197.

41. Fortune S. A sweepline algorithm for Voronoi diagrams. // AT&T Bell Laboratory Report, Murray Hill, NJ 1984.

42. Zhou J.M., Ke-Ran, Ke-Ding, Quing-Hua. Computing constrained triangulations and Delaunay triangulation: a new algorithm. // IEEE Transactions on Magnetics 1990 - V.26. - №2 - P. 692-694.

43. Edelsbrunner H. Algorithms in combinatorial geometry. Springer, Berlin, Heidelberg.

44. Du D.-Z., Hwang F. Computing in Euclidian Geometry. World scientific, Singapore.

45. Okabe A., Boots B., Sugihara K. Spatial Tesselations Concepts and Applications of Voronoi Diagrams. Wiley, New York.

46. Preparata F.P., Shamos M.I. Computational Geometry: An Introduction. Springer, New York.

47. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. // ACM Trans. Graphics 1985 - V.4 - P. 74-123

48. Baker T.J. Three-dimensional mesh generation by triangulation of arbitrary point sets. // AI A A Paper 87-1124-CP.

49. Baker T.J. Automatic mesh generation for complex three-dimensional region using a constrained Delaunay triangulation. // Eng. Comput. -1989 V.5. - P. 161-175.

50. Sibson R. Locally equiangular triangulations. // Comput. J. 1978. -V.21. - №3 - P. 243-245.

51. Lee B.E., Schachter B.J. Two algorithms for constructing a Delaunay triangulation. // Int. J. Comput. Inform. Sci. 1980 - V.9. - №3 - P. 219241.

52. Holmes D.J., Snyder D.D. The generation of unstructured triangular meshes using Delaunay triangulation. //In Sengupta S., Hauser J., Eise-man P.R., Thompson J.F. (eds.) Numerical Grid Generation in Computational Fluid Dynamics. 1988 - P. 643-652.

53. Ruppert J. Results on Triangulation and High Quality Mesh Generation. // PhD thesis, University of California, Berkeley. 1992.

54. Chew P. Mesh generation, curved surfaces and guaranteed quality triangles. // Technical Report, IMA, Workshop on Modeling, Mesh Generation and Adaptive Numerical Methods for Partial Differential Equations, University of Minnesota, Minneapolis. 1993.

55. Rebay S. Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm. // J. Comput. Phys. -1993 V.106. - P. 125-138.

56. Baker T.J. Triangulations, mesh generation and point placement strategies. //In Caughey D. (ed.). Computing the future. Wiley. New York. -199. P. 1-15.

57. Anderson W.K. A grid generation and flow solution method for the Euler equations in unstructured grids. //J. Comput. Phys. 1994 - V.110. -P. 23-38.

58. Lee D.T., Lin A.K. Generalized Delaunay triangulation for planar graphs 11 Discrete Comput. Geometry 1986 - V.l. - P. 201-217.

59. Chew L.P. Constrained Delaunay triangulation. // Algorithmica 1989- V.4. P. 97-108.

60. Cline A.K., Renka R.L. A constrained two-dimensional triangulaton and the solution of closcst node problems in the presence of barriers // SIAM J. Numer. Anal. 1990 - P. 1305-1321.

61. George P.L., Hecht F., Saltel E. Automatic 3D mesh generation with prescribed meshed boundaries // IEEE Trans. Magn. 1990 - V.26 - № 2- P. 771-774.

62. Weatherill N.P. The integrity of geometrical boundaries in the two-dimensional Delaunay triangulation // Commun. Appl. Numer. Meth. Fluids 1990. - V.8 - P. 101-109.

63. George P.L., Hermeline F. Delaunay's mesh of convex polyhedron in dimension d: application for arbitrary polyhedra // Int. J. Numer. Meth. Engng. 1992. - V.33 - № 2 - P. 975-995.

64. Field D.A., Nehl T.W. Stitching together tetrahedral meshes //In Field D.A., Komkov V.(eds.): Geometric Aspects of Industrial Design. SIAM Philadelphia, Chapter 3 1992. - P. 25-38.

65. Hazlewood C. Approximating constrained tetrahedrizaton // Comput. Aided Geometric Design 1993. - V.10 - P. 67-87.

66. Weatherill N.P., Hassan O. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints // Int. J. Numer. Meth. Engng. 1994. - V.37 - P. 2005-2039.

67. Cavendis J.C., Field D.A., Frey W.H. An approach to automatic three-dimensional finite element mesh generation // Int. J. Numer. Meth. Engng. 1992. - V.21 - P. 329-347.

68. Shcnton D.N., Cendes Z.J. Three-dimensional finite element mesh generation using Delaunay tessellation // IEEE Trans. Magnetics MAG-21- 1985. P. 2535-2538.

69. Perronet A. A generator of tetrahedral finite elements for multimaterial objects or fluids //In Sengupta S., Hauser J., Eiseman P.R., Thompson J.F. (eds.) Numerical Grid Generation in Computational Fluid Dynamics. 1988 - P. 719-728.

70. DeFloriani L. Surface representations on triangular grids // The Visual Computer V.3. - 1987 - P. 27-50.

71. Schneiders R., Bunten R. Automatic generation of hexahedral finite ele-merit meshes // Commun. Appl. Num. Meth. V.12. - 1995 - P. 693.

72. Peraire J., Vahdati M., Morgan H., Zienkiewicz O.C. Adaptive remeshing for compressible flow computations // AIAA Paper 88-0032 1987.

73. Lohner R. Generation of three-dimensional unstructured grids by the advancing fron method // AIAA Paper 88-0515 1988.

74. Merriam M. An efficient advancing front algorithm for Delaunay triangulation // Technical Report, AIAA Paper 91-0792 1991.

75. Mavriplis D.J. An advancing front Delaunay triangulation algorithm designed for robustness // AIAA Paper 93-0671 1993.

76. Muller J.D., Roe P.L., Deconinck H. A frontal approach for internal node generation in Delaunay triangulations // Int. J. Numer. Meth. Fluids -1993. V.17. - № 3. - P. 241-256.

77. Markum D.L., Weatherill N.P. Unstructured grid generation using iterative point insertion and local reconnection // AIAA Journal 1995. -V.33. - № 9. - P. 1619-1625.

78. Lohner R. Matching semi-structured and unstructured grids for Navier-Stokes calculations // AIAA Paper 933348-CP 1993.

79. Pirzadeh S. Recent progress in unstructured grid generation // AIAA Paper 92-0445 1992.

80. Parthasarathy V., Kallinderis Y. Directional viscous multigrid using adaptive prismatic meshes // AIAA Journal 1995. - V.33. - № 1. -P. 69-78.

81. Peraire J., Peiro J., Formaggia L., Morgan K., Zienkiewicz O.C. Finite element Euler computations in three dimensions // AIAA Paper 88-0033 1988.

82. Lohner R., Parikh P. 3-dimensional grid generation by the advancing front method // Int. J. Numer. Meth. Fluids 1995. - V.8. - P. 11351149.

83. Weatherill N.P., Marchant M.F., Hassan O., Marcum D.L. Adaptive in-viscid flow solutions for aerospace geometries on efficiently generated unstructured tetrahedral meshes // AIAA Paper 93-3390 1993.

84. Powell K.G., Roe P.L., Quirk J.J. Adaptive mesh algorithms for computational fluid dynamics //In Hussaini M.Y., Kumar A., Salas M.D. (eds.): Algorithmic Trends in Computational Fluid Dynamics. Springer, New York 1992. - P. 301-337.

85. Holmes D.G., Lamson S.H. Adaptive triangular meshes for compressible flow solutions //In Hauser J., Taylor C. (eds.): Numerical Grid Generation in Computational Fluid Dynamics. Pineridge, Swansea. 1986. -P. 413.

86. Mavriplis D.J. Adaptive mesh generation for viscous flows using Delau-nay triangulation // J. Comput. Phys. V.90 - 1990 - P. 271-291.

87. Muller J.D. Quality estimates and stretched meshes based on Delaunay triangulation // AIAA Journal 1994 - V.32. - P. 2372-2379.

88. Pirzadeh S. Structured background grids for generation of unstructured grids by advancing front method // AIAA Journal V.31 - № 2 - 1993 -P. 257-265.

89. Pirzadeh S. Viscous unstructured three-dimensional grids by the advancing-layers method // AIAA Paper 94-0417 1994.

90. Darve E., Lohner R. Advanced Structured-Unstructured Solver for Electromagnetic Scattering from Multimaterial Objects // AIAA-97-0863 -1997.

91. Morgan K., Brooks P.J., Hassan O., Weatherill N.P. Parallel Processing for the Simulations of Problems Involving Scattering of Electromagnetic Waves //in Proc. Symp. Advances in Computational Mechanics (L. Demkowicz and J.N. Reddy eds) 1997.

92. Baum J.D., Luo H., Lohner R. Numerical Simulation of a Blast Inside a Boeing 747 // AIAA-93-3091 1993.

93. Baum J.D., Luo H., Lohner R. Numerical Simulation of a Blast in the World Trade Center // AIAA-95-0085 1995.

94. Jou W. Comments on the Feasibility of LES for Commercial Airplane Wings // AIAA-98-2801 1998.

95. Mavriplis D.J., Pirzadeh S. Large-Scale Parallel Unstructured Mesh Computations for 3-D High Lift Analysis // ICASE Rep. 99-9 1999.

96. Lohner R., Cebral J.R. Parallel Advancing Front Grid Generation // Proceedings, 8th International Meshing Roundtable 1999 - P. 67-74.

97. Lohner R. Three-Dimensional Fluid-Structure Interaction Using a Finite Element Solver and Adaptive Remeshing // Comp. Sys. In Eng. 1990 - V.l. - № 2 - P. 257-272.

98. Mestreau E., Lohner R., S. Aita TGV Tunnel-Entry Simulations Using a Finite Element Code with Automatic Remeshing // AIAA-96-0798 -1996.

99. Mestreau E., Lohner R. Airbag Simulations Using Fluid/Structure Coupling // AIAA-96-0798 1996.

100. Baum J.D., Luo H., Lohner R., Yang C.,Pelessone D., Charman C. A Coupled Fluid/Structure Modeling of Shock Interaction with a Truck // AIAA-96-0795 1996.

101. Lohner R., Yang C., Cebral J., Baum J.D., Luo H., Pelessone D., Char-man C. Fluid-Structure-Thermal Interaction Using a Loose Coupling Algorithm and Adaptive Unstructured Grids // AIAA-98-2419 1998.

102. Hassan O., Bayne L.B., Morgan K., Weatherill N.P. An Adaptive Unstructured Mesh Method for Transient Flows Involving Moving Boundaries // 5th US Congress on Computational Mechanics 1999 - P. 662674.

103. Baum J.D., Luo H., R. Lohner The Numerical Simulation of Strongly Unsteady Flows With Hundreds of Moving Bodies // AIAA-98-0788 -1998.

104. Baum J.D., Luo H., Mestreau E., L5hner R., Pelessone D., Charman C. A coupled CFD/CSD Methodology for Modeling Weapon Detonation and Fragmentation // AIAA-99-0794 1999.

105. Simon H. Partitioning of unstructured problems for parallel processing // Сотр. Systems in Eng. 1991 - V.2. - P. 135-148.

106. Farhat C., Lesoinne M. Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics // Int. J. Numer. Meth. Engng 1993 - V.36. - P. 745-764.

107. Galtier J., George P.L. Prepartitioning as a Way to Mesh Subdomains in Parallel // 5th International Meshing Roundtable, Sandia National Laboratories 1996 - P. 107-122.

108. Белоцерковский O.M. Математическое моделирование на суперкомпьютерах (опыт и тенденции) / / Журн. вычисл. математики и матем. физики. 2000. - Т. 40. - № 8. - С. 11731188.

109. Четверушкин Б.Н. Кинетически-согласованные схемы в газовой динамике: новая модель вязкого газа, алгоритмы, параллельная реализация, приложения М.: Изд. МГУ, 1999. - 232с.

110. Четверушкин Б.Н. Кинетические схемы и высокопроизводительные многопроцессорные вычисления в газовой динамике / / Вычислительные технологии. Новосибирск. Изд. СО РАН. -2002. - Т. 7. - т.

111. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100 // Proc. of the Int. Conf. on Parallel ComputingTechnologies (PaCT 95). Lecture Notes in Computer Science. 1995. -Vol. 964. - P. 342-356.

112. Chetverushkin B.N., Gasilov V.A., Polyakov S.V., Iakobovski M.V., Kar-tasheva E.L., Boldarev A.S., Minkin A.S. Data Structures and Mesh Processing in Parallel CFD Project GIMM // Proc. ParCo2005 2005.

113. Verhoeven N.A., Weatherill N.P., Morgan К. Dynamic load balancing in a 2D parallel Delaunay mesh generator // Proceedings of the Parallel CFD Conference 1995.

114. Topping B.H.V., Cheng B. Parallel and distributed adaptive quadrilateral mesh generation // Computers and Structures 1999 - V.73. - P. 519536.

115. Laemer L., Burghardt M. Parallel generation of triangular and quadrilateral meshes // Advances in Engineering Software 2000 - V.31. -P. 929-936.

116. Lohner R., Camberos J., Merriam M. Parallel Unstructured Grid Generation // Сотр. Meth. Appl. Mcch. Eng. 1992 - V.95. - P. 343-357.

117. Chew L.P.,Chrisochoides N., Sukup F. Parallel Constrained Delaunay Meshing // Proc. Workshop on Trends in Unstructured Mesh Generation- 1997.

118. Chrisochoides N.,Nave D. Simultaneous mesh generation and partitioning for Delaunay meshes // Mathematics and Computers in Simulation- 2000 V.54. - P. 321-339.

119. Okunsanya Т., Peraire P. 3-D Parallel Unstructured Mesh Generation // Proc. Joint ASME/ASCE/SES Summer Meeting 1997.

120. Lohner R. Three-Dimensional Parallel Unstructured Grid Generation // Int. J. Num. Meth. Eng. 1995 - V.38. - P. 905-925.

121. Said R., Weatherill N.R, Morgan K.,Verhoeven N.A. Distributed Parallel Delaunay Mesh Generation // Comp. Meth. Appl. Mech. Eng. 1999 -V.177- P. 109-125.

122. Chrisochoides N. A Survey of Parallel Mesh Generation Methods // Brown University, Providence RI 2005.

123. Hoppe H., DeRose T., Duchamp T., McDonald J., Stuetzle W. Mesh optimization // ACM SIGGRAPH 1993 - P.19-26.

124. Snir M., Otto S., Huss-Lederman S., Walker D., Dongarra J. MPI: Complete Reference. London: MIT Press, 1996. - 350 p.

125. Shewchuk J. R. TViangle: Engineering a 2d quality mesh generator and Delaunay triangulator // Proceedings first workshop on Applied Computational Geometry 1996. - P. 124-133.

126. Si H., Gaertner K. Meshing Piecewise Linear Complexes by Constrained Delaunay Tetrahedralizations // Proceeding of the 14th International Meshing Roundtable 2005.

127. Shewchuk J. R. Tetrahedral mesh generation by Delaunay refinement // Proceeding of the 14th Annual Simposium on Computational Geometry- 1998. P. 86-95.

128. Chew P.L. Guaranteed-Quality Delaunay meshing in 3D // Proceeding of the 13th Annual ACM Simposium on Computational Geometry 1997.- P. 391-393.

129. Edelsbrunner H., Guoy D. An experimental Study of Sliver Exudation // Engineering with Computers 2002. - V.18. - P. 229-240.

130. Cheng S.W., Dey T.K., Edelsbrunner H., Facello M.A., Teng S.H. Sliver Exudation // Proceeding of the 15th Annual Simposium on Computational Geometry 1999.

131. Miller G.L., Talmor D., Teng S.-H., Walkington N., Wang H. A Delaunay Based Numerical Method for Three Dimensions: Generation, Formulation, and Partition // Proceeding of the 27th Annual ACM Simposium on the Theory of Computing 1999. - P. 683-692.

132. METIS: Multilevel Partitioning Algorithms, http://www-users.cs.umn.edu/ karypis/metis/

133. PETSc: Portable, Extensible Toolkit for Scientific Computation, http://www-unix.mcs.anl.gov/petsc/petsc-2/

134. H. Andrä, D. Stoyanov Error indicators in the parallel finite element solver for linear elasticity DDFEM // Berichte des Fraunhofer ITWM №83(2006)

135. PERMAS: Numerical Simulation with Finite Elements, http://www.intes.de

136. GeoDict: Interactive Microstructure Generator, http://wwws.geodict.com