Рассмотрены новые подходы к построению высокоэффективных параллельных алгоритмов для численного решения краевых задач. В качестве базового алгоритма выбрана Универсальная Многосеточная Технология - односеточный вариант метода Зейделя, позволяющий решать широкий класс прикладных задач с вычислительными усилиями близкими к оптимальным. Исследованы два подхода к распараллеливанию вычислений, основанных на комбинированном и чисто геометрическом построении предобуславливателя. Показаны преимущества данных подходов по сравнению с традиционными методами построения параллельных алгоритмов и получены оценки эффективности параллелизма. Ключевые слова: параллельные вычисления, краевые задачи, многосеточные методы.
x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 ентов высокого порядка [1]. Именно решение подобных СЛАУ требует наибольших вычислительных усилий по сравнению с остальными этапами вычислительного эксперимента.
Простейший способ построения параллельных алгоритмов основан на блочных
предобуславливателях. Перепишем задачу (
Положим, что используемая многопроцессорная система состоит из достаточного количества отдельных вычислительных устройств (процессоров), соединенных между собой некоторой коммутационной сетью. Далее не будут рассматриваться существующие или перспективные архитектуры многопроцессорных систем и способы обменов данными между отдельными процессорами, а также задержки связанные с коммуникационной сетью. Основной целью данной работы является формулировка новых подходов к построению высокоэффективных параллельных алгоритмов для численного решения краевых задач на структурированных сетках. Для решения данной задачи необходимо переформулировать задачу об итерационном решении СЛАУ таким образом, чтобы выделить достаточно большое количество независимых подзадач, которые можно решать параллельно на многопроцессорной системе с минимальными обменами данных.
Реализация параллельного алгоритма для решения СЛАУ (
В общем случае матрицу можно построить алгебраическими методами (т.е. без
привлечения информации о вычислительной сетке), но применительно к задаче (
Если исходная СЛАУ состоит из уравнений, то количество блоков на диагонали
матрицу лежит в пределах от 2 до и итерационный метод (
Следуя [2], введем следующие меры параллелизма:
Определение 1. Ускорением параллельного алгоритма называется отношение времени
выполнения алгоритма на одном процессоре к времени выполнения алгоритма в системе из
процессоров
Определение 2. Эффективностью параллельного алгоритма называется величина
На первый взгляд может показаться, что для метода Якоби ожидается и
(полный параллелизм), однако в действительности этого не происходит. Если
используется достаточно большое количество процессоров , то возрастают издержки, связанные с
обменами данных. Кроме того, скорость сходимости последовательного метода Якоби
невелика. Как следует из (
Определения 1 и 2 характеризуют ускорение и эффективность параллельного алгоритма и представляют теоретический интерес, в то время как определения 3 и 4 позволяют оценить уменьшение времени счета параллельного алгоритма по сравнению с наилучшим последовательным, т.е. являются теми мерами параллелизма, которые представляют при решении практических задач. За можно выбрать время выполнения наиболее распространенного варианта многосеточных методов V-цикла [4].
Однако и многосеточные методы не позволили построить эффективный параллельный алгоритм для численного решения краевых задач. Как следует из рис. 4, количество узлов на грубых сетках уменьшается со скоростью геометрической прогрессии, поэтому по мере перехода к более грубым сеткам возрастают издержки, связанные с обменом данными. Количество узлов на самых грубых сетках может быть меньше количества используемых процессоров, поэтому часть процессоров будет неизбежно простаивать при выполнении сглаживающих итераций на самых грубых сетках. Все это приводит к снижению эффективности параллельного многосеточного алгоритма.
Оптимальная скорость сходимости классических многосеточных методов обусловлена оптимальной адаптацией их компонент к решаемой задаче. Долгое время не удавалось построить универсальный (робастный) многосеточный алгоритм, предназначенный для решения широкого класса (не)линейных краевых задач. В 90-е годы такой алгоритм был разработан и получил название Универсальная Многосеточная Технология (УМТ) [5]. В основе УМТ лежит применение основного многосеточного принципа (об аппроксимации длинноволновых компонент ошибки на грубых сетках) в односеточных алгоритмах. Использование только одной сетки для отыскания поправки позволило минимизировать количество проблемно-зависимых компонент технологии, снизить требования к выбору сглаживающей процедуры и избежать простоя процессоров в параллельном исполнении. Как следствие скорость сходимости УМТ лишь близка к оптимальной, т.е. для решения разностных краевых задач необходимо выполнять арифметических операций, где есть количество узлов сетки. Для наглядности и простоты описания УМТ используют традиционную терминологию, принятую в многосеточных методах, однако этого можно избежать, поскольку УМТ является односеточным алгоритмом [5].
Отличительной особенностью параллельной УМТ является построение матрицы в (
Целью данной статьи является описание, теоретическое обоснование и экспериментальная иллюстрация преимуществ параллельной УМТ по сравнению с другими методами построения параллельных алгоритмов для численного решения краевых задач на структурированных сетках. 2. Основные компоненты УМТ
В УМТ самая мелкая сетка состоит из двух множеств точек рые, если сетка является равномерной, заданы соотношениями: и
, котоТочки и могут быть как узлами сетки, так и гранями контрольных объемов при аппроксимации краевой задачи интегро-интерполяционным методом [8]. Сетка , построенная при , показана на рис. 5.
G f(0;1)
x f1
x f2
x f3
x f4
x f5
x f6
x f7
x f8
G v(0;1) x v
1
x v
2
x v
3
x v
4
x v
5
x v
6
x v
7
x v
8
x v
9
Рис. 5. Вычислительная сетка для аппроксимации интегро-интерполяционным методом.
Грубые сетки в УМТ строят не удвоением шага, а утроением, как показано на рис. 6. При
этом грубые сетки , и не имеют общих узлов, поэтому сглаживающие итерации можно
проводить параллельно вне зависимости от используемого итерационного метода. Самая
мелкая сетка образует нулевой сеточный уровень, а три грубые сетки , и образуют
первый сеточный уровень. Фактически при помощи грубых сеток , и можно построить
блочный предобуславливатель в (
Процесс построения еще более грубых сеток осуществляется рекуррентным образом,
полученная таким образом иерархия сеток получила название многосеточной структуры (рис. 7).
Самые грубые сетки состоят из нескольких узлов и образуют уровень .
Аппроксимация краевых задач на многосеточной структуре осуществляется при помощи
интегро-интерполяционного метода, результирующая СЛАУ имеет вид (
Рассмотрим параллельную УМТ с (первая глубина), т.е. в трехмерном случае необходимо процессоров. На уровнях источником параллелизма является многосеточная структура (т.е. предобуславливающую матрицу строят геометрическим методом), а на уровнях (в данном случае это самая мелкая сетка) предобуславливающую матрицу строят алгебраическим методом.
Распределение сеток первого уровня и их подсеток среди процессоров и схема распараллеливания вычислений при показана на рис. 8 и 9. В этом случае исходная задача естественным образом распадается на 27 независимых задач, почти одинакового размера, которые могут быть решены параллельно без обмена данными. Почти одинаковый размер задач позволяет добиться почти равномерной загрузки процессоров. Более того, на сетках уровней возможно проведение дополнительных многосеточных итераций, который позволят еще уменьшить объем пересылаемых данных по сравнению с объемом вычислительной работы.
При выполнении сглаживающих итераций на самой мелкой сетке ( ) необходимо искусственно сгруппировать неизвестные в 27 блоков для построения блочно-диагонального предобуславливателя . Другими словами, на самой мелкой сетке матрицу можно построить алгебраическими методами. Данное обстоятельство приводит к необходимости использования следующих мер параллелизма: Самая мелкая сетка
G 10 x f1 x f2 x f3 x4f x f5 x f6 x f7 x f8 x f9
G 10 x v1 x v2 x v3 x 4v x v5 x v6 x v7 x v8 x v9 x v10 G 11 Определение 5. Ускорением параллельного сглаживания на сетках уровня l по отношению к последовательному сглаживанию на тех же сетках называется величина где есть время выполнения последовательного сглаживания (и оператора перехода) на одном процессоре, а – время выполнения параллельного сглаживания (и оператора перехода) на системе из процессоров. Определение 6. Эффективностью параллельного сглаживания на сетках уровня по отношению к последовательному сглаживанию на тех же сетках называется величина Передача данных Теоретическая оценка ускорения и эффективности параллельной УМТ может быть получена при допущении, что на всех уровнях выполнено одинаковое количество сглаживающих итераций, а на грубых сетках ( ) УМТ обладает полным параллелизмом. Из определений 1 и 2 непосредственно следует, что для параллелизма первой глубины ( ) справедливо Из полученной оценки следует, что эффективность параллельной УМТ зависит исключительно от эффективности параллельных сглаживающих итераций на самой мелкой сетке ( ), т.е. от совершенства предобуславливателя , построенного алгебраическими методами. При этом итоговая эффективность параллельной УМТ будет больше, чем эффективность параллельных сглаживающих итераций на самой мелкой сетке.
Самая мелкая сетка
1
2
3
4
5
1
2
3
4
5
(
Несколько иначе выглядят характеристики УМТ при использовании мер параллелизма, данных в определениях 3 и 4. Сравнение времени счета с последовательным V-циклом приводит к следующей оценке (5) Поскольку , то при и , т.е. проигрыш во времени счета последовательному V-циклу будет возрастать с увеличением количества узлов.
Для вычислительного эксперимента воспользуемся первой краевой задачей для
трехмерного уравнения Пуассона в единичном кубе, которая имеет точное решение .
Вычислительная сетка состоит из 2453 = 14 706 125 узлов (L+=3). Распараллеливание
многосеточных итераций УМТ осуществлено при помощи технологии OpenMP с привлечением 27 ядер.
На каждой сетке выполнены четыре сглаживающие итерации, на сетках уровней
выполнены две многосеточные итерации . Согласно результатам вычислительного
эксперимента эффективность распараллеливания сглаживающей процедуры на самой мелкой сетке и на
сетках уровней составила и соответственно. Эффективность
параллельной УМТ составила 0.92, в то же время, согласно оценке (
Таким образом, построение предобуславливателя геометрическими методами на грубых сетках и алгебраическими на мелких позволяет построить достаточно эффективный параллельный алгоритм для численного решения задач на структурированных сетках. Распараллеливание вычислений на грубых сетках не зависит от выбора сглаживающей процедуры. 4. Вычислительный эксперимент
Очевидные преимущества построения предобуславливателя геометрическими методами
можно использовать в другом подходе к построению параллельной УМТ, основанном на
редукции к независимым задачам. Положим, что краевая задача (
В качестве примера редукции исходной разностной задачи к совокупности независимых задач меньшей размерности, рассмотрим уравнение Пуассона в единичном кубе. Положим, что точное решение имеет вид которое однозначно определяет правую часть f (x, y ,z) и однородные граничные условия Дирихле. Параметр предназначен для иллюстрации влияния погрешности аппроксимации производных на точность численного решения. Поведение функции при различных значениях показаны на рис. 10.
Для численного решения первой краевой задачи для уравнения Пуассона построена равномерная сетка 451×451×451, которая порождает пятиуровневую многосеточную структуру. Для аппроксимации уравнения Пуассона использована схема шестого порядка аппроксимации, основанная на аппроксимациях Паде. Однако в вычислительном эксперименте вместо разностной краевой задачи на сетке 451×451×451 решены 729 разностных задач на сетках ≈ 50×50×50. Поскольку аналитическое решение краевой задачи известно, то погрешность численного решения определим как где и
есть точное и численное решение соответственно. В качестве сглаживателя использован метод Зейделя с блочным упорядочением неизвестных, на каждой сетке выполнено три сглаживающие итерации, всего выполнено двадцать многосеточных итераций. Коррекция решения проводилась после пяти многосеточных итераций. Вычисления производились на системе с общей памятью, включающей 4 процессора AMD Opteron 6176 и объемом RAM 128 Gb.
Рис. 10. Поведение функции при различных значениях k.
Результаты вычислительного эксперимента показаны на рис. 11. При бóльших значениях параметра наблюдается рост погрешности численного решения, связанный с увеличением абсолютных величин частных производных, входящих в главный член погрешности аппроксимации. Редукция приводит к уменьшению времени счета приблизительно в раз, где есть номер сеточного уровня с самыми мелкими сетками, используемый для отыскания поправки в многосеточных итерациях. Оценка минимальной эффективности параллелизма в данном случае основана на предположении, что время выполнения сглаживающих итераций пропорционально количеству узлов. Поскольку общее количество узлов сеток одного уровня есть , , то время выполнения сглаживающих итераций в последовательном алгоритме есть где есть коэффициент пропорциональности. Уровень l* состоит из сеток, имеющих разное количество узлов, что является причиной уменьшения эффектности параллелизма.
Рис. 11. Зависимость погрешности численного решения при различных значениях k. Одна из сеток уровня
имеет максимальное количество узлов, которое можно оценить как Поэтому время выполнения независимых задач на процессорах будет различным. Максимальное время выполнения сглаживающих итераций в параллельной УМТ ожидается на той сетке уровня , которая состоит из наибольшего количества узлов, и составит откуда нетрудно получить оценку минимальной эффективности параллелизма, основанного на редукции к независимым задачам В рассмотренном случае ,
, следует ожидать, что E > Emin=90%. 5. Выводы Литература
Если вычислительная сетка является структурированной, то возможно построить метод численного решения широкого класса прикладных задач, который будет высокоэффективен не только в последовательном, но и в многопроцессорном исполнении. Использование топологии вычислительной сетки позволяет строить предобуславливатель геометрическими методами, которые существенно превосходят алгебраические методы по возможности эффективного распараллеливания вычислений. 8. Самарский А.А. Теория разностных схем: Учеб. пособие. М.: Наука. Физматлит, 1983.
616 с. 9. Мартыненко С.И. Многосеточная технология: теория и приложения. М.: ФИЗМАТЛИТ, 2015. 208 с. New approaches for construction of highly efficient parallel algorithms for numerical solution of the boundary value problems on structured grids
V.M. Volokhov, S.I. Martynenko, P.D. Toktaliev, L.S Yanovskiy The Institute of Problems of Chemical Physics of the Russian Academy of Sciences New approaches for development of high efficient parallel algorithms for numerical solving boundary value problems have been considered. Robust Multigrid Technique (single grid variant of Seidel method for solving a large class of applied problems with close-to-optimal computational efforts) is taken as a basic algorithm. Two approaches for parallelisation of computations based on combined and purely geometric preconditioning have been studied. Advantages of these approaches over traditional methods of constructing parallel algorithms and estimations of parallelism efficiency are given.
Keywords: parallel computing, boundary value problems, multigrid methods.