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

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

ВВЕДЕНИЕ 2
ГЛАВА 1. РАЗБИЕНИЕ НА СИМПЛЕКСЫ В МЕТОДЕ КОНЕЧНЫХ ЭЛЕМЕНТОВ 6
1.1 Метод конечных элементов 6
1.2 Типы конечных элементов 12
1.2.1 Одномерные элементы 13
1.2.2 Двумерные элементы 13
1.2.3 Трехмерные элементы 14
1.3 Разбиение области на элементы 15
1.3.1 Нумерация узлов 19
1.4. Линейные интерполяционные полиномы 20
1.4.1 Одномерный симплекс-элементы 22
1.4.2 Двумерный симплекс-элемент 23
1.4.3 Трехмерный симплекс-элемент 26
ГЛАВА 2. РАЗРАБОТКА ПАРАЛЛЕЛЬНОГО АЛГОРИТМА ПОСТРОЕНИЯ СИМПЛИЦИАЛЬНОГО ПОДРАЗДЕЛЕНИЯ ЦИЛИНДРИЧЕСКОЙ ОБЛАСТИ 29
2.1 Адаптивный алгоритм построения симплициального подразделения 29
2.2 Параллельный адаптивный алгоритм построения симплициального подразделения 32

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ РАЗРАБОТАННОГО АЛГОРИТМА И АНАЛИЗ ЕГО ЭФФЕКТИВНОСТИ 35
3.1 Реализация алгоритма 36
3.1.1 Разбиение элементов на симплексы. 43
3.2 Апробация и тестовые данные 49

ЗАКЛЮЧЕНИЕ 52
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 54
ПРИЛОЖЕНИЕ 5

Цель выпускной квалификационной работы является разработка и программная реализация параллельного алгоритма построения симплициального подразделения цилиндрической области с использованием технологии MPI.
Поставленная цель достигается решением следующих задач:
1) Обзор методов построения симплициального подразделения цилиндрической области;
2) Разработка параллельного алгоритма построения симплициального подразделения цилиндрической области;
3) Программная реализация параллельного алгоритма построения симплициального подразделения цилиндрической области с использованием технологии MPI;
4) Оценка эффективности разработанного параллельного алгоритма на основе проведения вычислительных экспериментов.
Выпускная квалификационная работа состоит из: введения, трех глав, список использованной литературы, приложения

if(Alocal(I, J) < -1)
Plocal(I, J) = my_rank
P.REPLACE_LocalMatrix(Plocal)
Plocal = GetLocalView(P, local_graph)
4) Данный этап, подразумевает, что нам известно какие грани должны будут созданы и кто будет их «owner». Здесь нам необходимо найти подходящий глобальный ID, такой чтобы они были пронумерованы, и не пропускали ни одну из граней, и удостовериться что ID(глобальное) не повторится. Так как используется подход, основанный на сканировании суммы, то новые владельцы начинаются с наибольшей ID, найденного до разбиения и имеющего наибольший идентификатор, основываясь на его положении в локальном узле.
Ввиду того, что может потребоваться доступ к «ghost» узлам, то для этого заново будем идентифицировать матрицу и синхронизировать информацию с процессами.
Листинг 3.4. Находимподходящий глобальный ID.
local_node_counter = 0
for I in rows of Alocal
for J in rows of Alocal
if(Alocal(I, J) < -1) //need remesh!
if(Plocal(I, J) == my_rank) //we own the node
local_node_counter= local_node_counter+1
use scan sum to determine new_id_local_start
new_id = new_id_local_start
for I in rows of Alocal
for J in rows of Alocal
if(Alocal(I,J) < -1) //need remesh!
if(Plocal(I,J) == my_rank) //we own the node
IdMatrix_local(I, J) = new_id
new_id = new_id + 1
IdMatrix.ADD_LocalMatrix(IdMatrix_local)
IdMatrix_local = GetLocalView(IdMatrix,local_graph)
5) На этом этапе, все необходимые сведения собраны, и есть необходимо создать новые узлы на гранях локально. Создадим их с глобальным ID, выполним интерполяцию координат и назначим «owner» данные из краевых вершин.
Листинг 3.5. Создать новые узлы на гранях локально.
// необходимо начинать идентификаторы с 1, но не с 0!
for I in rows of IdMatrix_local
for J in rows of IdMatrix_local
if(IdMatrix_local(I, J) > 0)
generate new node in the middle of edge I, J
interpolate from I and J
assign global id = IdMatrix_local(I, J)
assigin node_rank = Plocal(I, J)
6) Здесь, создаем новые элементы, используя вновь созданный узлы. Которые будем адресовать в следующий раздел. Для того что бы гарантировать правильно разбиение.
Для этого в цикле перебираем элементы и для каждого из них, собираем данные, связанные с каждой из граней. И если новый узел будет связан с любой из граней, то локальное изменение будет необходимо. За это отвечают вспомогательные функции. Следует заметить, что возможно потребуется создание новых узлов, это зависит от поставленной задачи. Хотя возможно хватит и единственного присвоения глобального ID.[7]
Листинг 3.6. Создаем новые элементы, используя вновь созданные узлы из предыдущего пункта.
loop on elements
if any elemental edge is splitted
gather newly created nodes
split element (see next section)
interpolate elemental data
Данный алгоритм является оптимальным, по причине того что зависит от конкретных структур данных, которые относительно легко могут быть введены в широком диапазоне вычислительных кодов.
Как только заканчивается алгоритм, нагрузка может быть не сбалансированной и для решения этой проблемы необходимо применять некоторые действия. Но в нашем случае это не столь критично.
Еще можно отметить, что при уточнении, возможно, что шаблоны между разными областями могут измениться. Например: рассмотрим Рисунок. 3.1, предположим, что исходная сетка, состоящая из треугольников 1,2 и 3 и эти треугольники принадлежат процессам 1, 2 и 3 соответственно. Процесс 1 принадлежит узлу a, и при этом процесс 3 владеет узлами b и с. Вышло, так что не один узел не принадлежит процессу 2. [9]
Рисунок. 3.1. Пример сетки, где будет необходимо перерасчет шаблона связи.
Для того, что бы выполнить операцию сборки, принято собирать узловые данные на владельце, который будет суммировать различные значения и распространять на другие узлы. Для этого необходимо, чтобы 1 процессор собрал данные, относящиеся к узлу процессора 2 и данные относящиеся к узлу b из процесса 2 и 3. Процессу 2 не нужно собирать узловые данные совсем, так как он не является «owner». Именно поэтому не рассматриваем его на этом этапе.
Теперь же давайте предположим, что элемент 2 уточняется и новый узел должен быть делить ребро ab. Из ходя из нашего алгоритма новым владельцем может стать либо 1, либо 2 процесс. В качестве примера, будем «owner» 2 процессор. Что может привести к неправильному маркированию. Из чего следует что пройдется пересчитывать связи между областями. С данной ситуацией нужно вести себя осторожнее и следить за «чистотой» сетки.
3.1.1 Разбиение элементов на симплексы.
В данной части будет описан пример элементарного разбиения, для того что бы гарантировать получение правильную сетку.
Основная идея, заключается в том, что за 6 шагов алгоритм должен получить достаточное разбиение, что бы однозначно определить разбиение области при дополнительных ограничениях. Для наглядности используем практический пример. Рассмотрим 2 тетраэдра, показанных на рисунке 3.2 и 3.3.
Рисунок. 3.2. Пример сетки, где будет необходимо перерасчет шаблона связи.
Они имеют глобальные ID 1,2,3,4 и 2,5,3,4 соответственно, которые разбиты с помощью добавления нового узлов 6 и 7. На рисунке 4.1 показано правильное разбиение грани (2, 7), которая находится на стороне 2 3 4. На рисунке 3.3 с другой стороны, узлы 6 и 7 добавлены в двух тетраэдрах, но самый правый край (3, 6) входит в уточняемую сетку, в то время когда ребро (2, 7) создается в соседней тетраэдрах. Из этого следует, что рассматривая сторону 2 3 4, то видим что разбиение произошло не правильно, и сетка получилась так же не правилам.
Рисунок. 3.3. Пример сетки, где будет необходимо перерасчет шаблона связи.
Такая ошибка может возникать, когда два узла, добавленные на два ребра соответственно, образуют новую сторону, а 3 ребро не имеет угла.
Обычно, алгоритм будет делиться некоторой информацией между элементами, которые разделяют лицо стороны, что разбиение выполняется так же для них одинаково. Это довольно просто сделать в скалярном варианте алгоритма, но не в параллельном.
Рисунок 3.4. Операция сворачивания для грани(a, b), слева направо: по центру края; край устремился к a; край устремился к б.
Имеет смысл, избегать такой ситуации основываясь исключительно на локальных данных, все грани должны быть равномерно разбиты. И необходимо указывать те грани, которые разбивать не следует.
Листинг 3.7.Условия для выполнения правильного разбиения.
if(edge is not splitted)
if(GID(I) < GID(J) )
collapse_towards = LID(I)
else
collapse_towards = LID(J)
else
collapse_towards = edge_id
Пример этой ситуации изображен на рис (3). Учитывая сторону abc, предположим, что ребра (b, c) и (c, a) разделены. Если ребро (а, б) правильно разбиты, то треугольник разделен на четыре меньших. В противном случае, есть два возможных исхода, которые можно наблюдать на рисунке, и соответствуют ситуации определили в качестве неправильного ребра (а, б) по отношению к a и к b, соответственно.
Если будем применять такой алгоритм на примере на рис (2), таким образом, то краю (2,3) тегом "2", получат новые грани на своих сторонах, иметь новые ребра связанные с 2, а не 3.
На практике, общая схема разбиения тетраэдров записывается на вспомогательный массив размером 6 (число ребер элемента) меткой, которая определяет для каждого ребра локальный узел, подходящий для использования при разбиении. Число меньше 4, указывает над узлом, к которому новые края на окружающих сторонах должны быть ориентированы. В количестве, превышающем 4, с другой стороны, будет указывать над новым узлом для использования в уточнении, что соответствует нашей уникальной грани. Таблица (3) показывает различные вариации для построения ребра, после чего их пронумеровываем. Например, первая грань имеет ID = 0, что соответствует локальному идентификатору (0,1) и второму (0,2) и так далее. Когда связываем с первой гранью либо значение 0, либо 1, тогда край не должен быть разделен.
Так как имеется 3 возможных варианта построение грани имеем всего 6 сторон то, общее число возможных комбинаций 3*6 = 729, которые необходимо рассматривать в качестве потенциальных моделей разбиения.
Совокупность таких комбинаций рассмотрим в данном псевдо коде 3.7:
Листинг 3.7.Вспомогательный массив из 6 элементов для упрощения разбиения.
#define an array with the LIDs associated to each edge
edge_id[0] = 4;
edge_id[1] = 5;
edge_id[2] = 6;
edge_id[3] = 7;
edge_id[4] = 8;
edge_id[5] = 9;
edge_counter = 0
for LID1=0 to 2:
for LID2=1 to 3:
obtain GID1, GID2 associated to the nodes with LID1, LID2
if(edge is not splitted)
if(GID1 < GID2)
edge_id[edge_counter] = LID1
else
edge_id[edge_counter] = LID2
else
do nothing (already set before the loop)
edge_counter = edge_counter + 1
По непосредственного применения такой алгоритм в двух тетраэдров на рис (3.3), таким образом, появится возможность построить таблицу (3.2) и табл. (3.3). Окончательный результат будет связан с верхним левым тетраэдром по списку граней (EDGE) 0 0 0 1 8 9 и одним справа 0 0 6 2 4 9. Этой информации достаточно, для разбиения на 2 тетраэдра. Если же посмотреть на нижний правый угол то увидим, что выбран другой режим разбиения.
Таблица 3.1
Определение граней тетраэдра и список возможных исход
index ребра
id ребра
локальный id1
локальный id2
варианты
1
2
3
4
5
4
5
6
7
8
9
1
1
2
1
2
3
2
3
3
1
1
2
1
2
3
2
3
3
4
5
6
7
8
9
Таблица 3.2
Глобальный ID верхнего левого тетраэдра:1 2 3 4, ID: 0 0 0 1 8 9
index ребра
лок.id1
лок.id2
new лок.id
глоб.id1
глоб.id2
new глоб.id
Условия выбора
1
2
3
4
5
1
1
2
1
2
3
2
3
3
1
8
9
1
1
1
2
2
3
2
3
4
3
4
4
1
1
1
2
6
7
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
добавляем новый 6 узел, ребро 8
добавляем новый 7 узел, ребро 9
Таблица (3.4) показывает, индексы, полученные в данной ситуации, и точки которые не должны были получиться при нашей стратегии. Конечный образец разбиения 0 2 6 2 4 9, не совпадает с правильный, но правильную картину показывает список edgeId.
Таблица 3.3
Глобальный ID верхнего правого тетраэдра:2 5 3 4, ID: 0 0 6 2 4 9
index ребра
лок.id1
лок.id2
new лок.id
глоб.id1
глоб.id2
new глоб.id
Условия выбора
4
5
6
7
8
9
1
1
2
1
2
3
2
3
3
2
4
9
2
2
2
5
5
3
5
3
4
3
4
4
2
2
6
3
4
7
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
ребро не разбивается и Гid1<Гid2
добавляем новый 6 узел, ребро 8
добавляем новый 7 узел, ребро 9
Пользователь должен определить вспомогательный вектор размером 10, которое содержит в первых четырех позициях в ГИД из узлов тетраэдров должны быть разделены. Позиции между 4 и 9 соответствуют краям элемента (заказать как в таблице (1)). Их значение должно быть -1, если ребро не должны быть разделены или GID узла для вставки.
Таблица 3.4
Гобальный ID нижнего правого тетраэдра:2 5 3 4, ID: 0 2 6 2 4 9
index ребра
лок.id1
лок.id2
new лок.id
глоб.id1
глоб.id2
new глоб.id
соответствие критериям
4
5
6
7
8
9
1
1
2
1
2
3
2
3
3
2
6
2
4
9
2
2
2
5
5
3
5
3
4
3
4
4
2
3
6
3
4
7
Да
Не соответствует критериям!
Да
Да
Да
Да
3.2 Апробация и тестовые данные
После завершения разработки параллельного адаптивного алгоритма, необходимо убедиться, что он эффективнее последовательного варранта. И работает правильно. Для этого было визуализированы грубая начальная сетка (Рисунок 3.5) и сетка после применения адаптивного алгоритма на определенное количество итераций (Рисунок 3.6).
Рисунок 3.5 Создаем грубую сетку, с разным показанием точности.
Рисунок 3.6 Результат после работы некоторого числа итераций алгоритма.
Из представленного рисунка 3.5 видно, как изменяется размер и структура сетки, при изменении начальной точности. Соответственно чем точнее должен быть результат, тем более мелкую сетку изначально мы должны задать. Но это не совсем правильный подход, так как уменьшение сетки повсеместно, значительно увеличит время выполнения алгоритма.
Лучше применять крупную сеть и используя адаптивный алгоритм, добиться заданной точности в необходимых местах. Результат вычислений можно посмотреть в таблице 3.5 и их визуализацию на рисунке 3.7.
Таблица 3.5
Время выполнения алгоритма на разном количестве вычислительных узлов.
Рисунок 3.7 Время выполнения алгоритма на разных вычислительных узлах, с разным показателем уточнения.
В заключение данной части выпускной квалификационной работы, необходимо отметить, что была проделана работа, по созданию рабочей программы на основе параллельного адаптивного алгоритма из 2 части. Были учтены некоторые «подводные камни», например возможность неправильного разбиения на более мелкие детали тетраэдров. Данная реализация показала себя наилучшим образом, как и предполагалось в начале данной квалификационной работы. И можно сделать вывод исходя из графика и таблицы данных, что параллельная реализация эффективнее последовательной. Наблюдается увеличение скорости выполнения алгоритма примерно в 1.7 раз.
ЗАКЛЮЧЕНИЕ
Эффективная работа алгоритмов разбиения на симплексы методом конечных элементов, является одним из важных направлений деятельности современной науки и инженерии, и заслуживает особого внимания. Данный алгоритм позволяет эффективно решать самые разнообразные задачи математической физики и техники. И так как данная тематика весьма популярна, имеет смысл ускорить работу алгоритмов разбиения. Для этого и была использована технология MPI, что и позволило уменьшить время, затраченное на выполнения методов.
В данной выпускной квалификационной работе были выполнены, разработка и программная реализация параллельного алгоритма построения симплициального подразделения цилиндрической области с использованием технологии MPI.
Поставленная цель повлекла за собой решение следующих задач:
1) Обзор метода конечных элементов, симплексов, адаптивного алгоритма;
Была проведена исследовательская работа, в результате которой было изучены методы конечных элементов, типы конечных элементов: одномерные, двумерные, трехмерные. Так же было изучено симплексное разбиение и нумерация всех узлов, линейные интерполяционные полиномы: одномерные, двумерные, трехмерные.
2) Разработка параллельного алгоритма построения симплициального подразделения цилиндрической области;
Был изучен последовательный адаптивный алгоритм построения симплициального подразделения , на его основе был разработан параллельный алгоритм. В словесном варианте и в виде схемы, так же был представлен граф информационных зависимостей для параллельного случая.
3) Программная реализация параллельного алгоритма построения симплициального подразделения цилиндрической области с использованием технологии MPI;
Для решения данной задачи, был сделан полный разбор процесса реализации параллельного алгоритма, все записано в виде псевдо кода. Были обнаружены недостатки параллельного алгоритма, когда в некоторых местах сетки возникало избыточное разбиение. Что приводит к увеличению времени выполнения программы.
4) Оценка эффективности разработанного параллельного алгоритма на основе проведения вычислительных экспериментов.
После того как был реализован параллельный алгоритм построения симплициального подразделения цилиндрической области. Производилось тестирование алгоритма, результаты которого представлены в виде таблицы и графика. Исходя из этих данных, можно сделать вывод, что параллельная реализация эффективнее последовательной. Наблюдается увеличение скорости выполнения алгоритма примерно в 1.7 раз.
В результате выполнения выпускной квалификационной работы были решены все поставленные задачи. Результатом проделанной работы является создание приложения, реализующего разбиение цилиндрической области на симплексы, а также проведение различных тестовых заданий, которые смогли показать эффективность работы приложения в рамках данной выпускной квалификационной работы
При выполнении выпускной квалификационной работы был выполнен весь необходимый перечень и объем работ.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
[1] Сьярле Ф. Метод конечных элементов для эллиптических задач. М., 1980.
[2] www.parallel.ru
[3] Корнеев В.В. Параллельные вычислительные системы. М., 1999.
[4] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.
[5]Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming. International Technical Support Organization. IBM.
[6] Сегерлинд Л. Применение метода конечных элементов, изд-во «Мир», М., 1979.
[7] Зенкевич О., Метод конечных элементов в технике, изд-во «Мир», М., 1975.
[8] Стренг Г., Фикс Дж. Теория метода конечных элементов. – М.:Мир, 1977.
[9] Обэн. Ж.П. Приближенное решение эллиптических кравевых задач. –М.:Мир, 1977.
[10] Марчук Г.И. Методы вычислительной математики. – М.: Наука, 1977.