Решение двумерных краевых задач параллельным методом конечных элементов

Автореферат

Хорошилов А. В.

На главную

Введение

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

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

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

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

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

Суть метода конечных элементов (МКЭ)

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

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

Возможности распараллеливания МКЭ

Рассмотрим в качестве примера простую каркасную конструкцию, приведенную на рисунке 1.

Рисунок 1 – Простая каркасная конструкция

Каждый конечный элемент i может быть описан системой линейных уравнений A[i].x* == B[i]. Где A[i] – матрица жесткости i конечного элемента. Вычисление компонент матриц жесткости для каждого из элементов независимо и может быть выполнено параллельно.

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

Цель работы

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

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

Обзор существующих алгоритмов решения СЛАУ ленточной структуры

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

1. Метод исключения Гаусса без выбора главного элемента;

2. Метод исключения Гаусса с выбором главного элемента;

3. Метод прогонки;

4. Метод циклической редукции;

5. Метод простой итерации;

6. Метод Зейделя;

7. Метод Divide and Conquer;

8. Single-Separator approach;

9. Double-Separator approach.

Промежуточные результаты работы

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

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

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

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

Рисунок 2 - Ускорение как обоснование выбора одного из алгоритмов 

для системы с низкой латентностью каналов связи

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

Рисунок 3 - Ускорение как обоснование выбора одного из алгоритмов 

для системы с низкой латентностью каналов связи

Исходные даные

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

Ленточная система линейных алгебраических уравнений

имеет матрицу коэффициентов  такую, что:

 если выполняется одно из условий или , где

s  - ширина верхней полуленты;

r  - ширина нижней полуленты (см. рис. 1)

Рисунок 1 – Структура ленточной матрицы

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

.

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

Необходимо исследовать потенциал алгоритма Divide and Conquer (D&C) для ускорения нахождения решения СЛАУ ленточной структуры, получить теоретические оценки сложности и подтвердить их экспериментальными данными, исследовать применимость метода D&C для нахождения Решения двумерных краевых задач методом конечных элементов (МКЭ) и исследовать перспективы оптимизации D&C для использования в МКЭ.

 Краткое описание алгоритма D&C (Divide and Conquer)

В данном алгоритме матрица коэффициентов , вектора  и разбиваются на блоки шириной  построчно как показано на рисунке 2.

Рисунок 2 – Разбиение матрицы

Алгоритм состоит из 3-х шагов:

-    Факторизация;

-    Формирование и решение редуцированной системы;

-    Обратный ход.

Рисунок 3 – Результат факторизации матрицы

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

На шаге формирования редуцированной системы строится новая трехдиагональная СЛАУ с матрицей размерностью . Сложность коммуникаций на данном шаге составит , если считать, что .

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

Направление исследований алгоритма D&C и научная новизна

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

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

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

Выводы

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

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

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

На момент написания автореферата работа не является законченной. Планируемое время окончания работы - 01/2007.

Литература

1. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. М. Мир, 2001, 430с.

2. Arbenz P. Stable scalable solvers for Non-symmetric Narrow-banded Linear systems, Zurich, 1997.

3. Arbenz P., Gander W. A survey of direct parallel algorithms for banded linear systems, Zurich, 1994.

4. Таненбаум Э. Современные операционные системы. 2-е изд. – СПб.: Питер 2002. – 1040 с.: ил.

5. Гергель В.П., Стронгин, Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем.   Учебное пособие – Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 с.

6. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002.

7. Foster I. Designing and Building Parallel Programs. — Addison Wesley.

8. Быстрицкий В.Д. Представление разреженных матриц.http://alglib.sources.ru/articles/zeromatr.php,

9. Действия над разреженными матрицами http://alglib.sources.ru/sparse/.

 На главную