Сравнительный анализ некоторых методов композиции вычислительных подобластей студент: Данилин Александр научный руководитель: Илюшин Александр Иванович

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

Цель работы Реализовать метод приграничных полуполюс, сравнить результаты его работы с результатами работы метода приграничных полос.

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

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

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

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

Сопряжение на внутренней границе представляет из себя итерационный процесс пересчёта приграничных полуполюс: 1. В точках внутренней границы ищется полусумма потоков в граничащих подобластях. 2. Полуполосы пересчитываются с граничным условием второго рода на внутренней границе равным найденной полусумме потоков. 3. В точках внутренней границы ищется полусумма значений в граничащих подобластях, если она меньше допустимой ошибки, выход из цикла. 4. Иначе полуполюсы пересчитываются с граничным условием первого рода на внутренней границе равным найденной полусумме значений. Алгоритм сопряжения

Схема для уравнения теплопроводности. Двумерный случай. Схема переменных направлений: Реализация

Зависимость ширины распространения возмущений от коэффициента теплопроводности и шага по времени Реализация Для нахождения ширины распространения возмущений считалась следующая задача: нулевые начальные условия, на границе слева, сверху и снизу – ноль, справа – подогревание единицей. В таблице представлены размеры полосы (в шагах по икс), в точках которой температура больше error = 0.01: Сетка 500x300

Реализация Начальные условия Граничные условия Эксперимент по сравнению аналитического, последовательного и параллельного решений. Проверка правильности решателя и последовательной программы. Аналитическое решение Следующие результаты для коэффициента 10, момента времени 0.1 (1000 шагов по ).

Реализация Аналитическое решение

Реализация Счёт всей области на одном вычислительном узле

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

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

Реализация Аналитическое решение

Реализация Точность Сетка 501x шагов по времени Доля приграничной полосы 10% Максимум погрешности параллельного счёта с коррекцией, относительно счёта всей области

Реализация Начальные условия Граничные условия Эксперимент по сравнению последовательного и параллельного решений. Следующие результаты для коэффициента 10, момента времени 0.01 (1000 шагов по ).

Реализация Счёт всей области на одном вычислительном узле

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

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

Реализация Счёт всей области на одном вычислительном узле

Реализация Алгоритм приграничных полос

Реализация Точность Максимум погрешности параллельного счёта с коррекцией, относительно счёта всей области Доля приграничной полосы 10% Сетка 501x шагов по времени

Реализация Начальные условия: всюду 0.5 Граничные условия: слева – 0 справа – 1 сверху и снизу – 0.5 Эксперимент с разными коэффициентами теплопроводности. Коэффициенты: слева – 0.1 справа – 10

Реализация Алгоритм полуполюс с разными коэффициентами. Правый больше левого в сто раз.

Реализация Точность Доля приграничной полосы 10% Сетка 501x шагов по времени Слева охлаждение только начало распространяться, а справа тепло перешло уже за середину области.

Выводы Теоретическое сравнение методов декомпозиции на примере двух подобластей За 100% берётся время независимого счёта подобластей без коррекции значений внутренней границы. Niter – среднее количество итераций пересчёта полуполюс. В экспериментах Niter ~ 1.5 (в условиях слабого изменения решения вблизи внутренней границы Niter < 1). Метод Шварца в предположении сходимости с одной итерации. Доля приграничной полосы (пересечения подобластей) 10%.

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

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

Спасибо за внимание