Талтыкина (1235576), страница 7
Текст из файла (страница 7)
Модуль vector.f90 описывает структуру типа block и определяет списоктаких структур как массив указателей. В файле data.f90 хранятся данныеи переменные для работы мозаично-скелетонного метода. Модуль kernel.f90предназначен для расчёта коэффициентов матрицы. Интегралы рассчитываются численно в модуле integ.f90. Модуль right.f90 находит правую частьаппроксимирующей СЛАУ.
Алгоритм GMRES находится в одноимённом модуле. Три этапа мозаично-скелетонного метода описаны соответственно в модулях cube_tree.f90, block.f90 и cross.f90. Модуль devision.f90 является вспомогательным к cube_tree.f90, в нём рассчитывается, сколько точек попало награницу среза, сделанного по включению.
Модуль main.f90 является точкойвхода в программу, именно из него вызываются все функции из дополнительных модулей.Далее на рисунке 3.1 представлены результаты работы программногообеспечения. В данном случае отыскиваются плотности для задачи дифракции. Сначала выводится информация о количестве точек дискретизации (вданном случае 1032), о волновом наборе (kred и kvk) и количестве блоков матрицы (10678).
Модуль cross.f90, реализующий алгоритм неполной крестовойаппроксимации, выводит для каждой из четырёх СЛАУ мозаичный ранг ифактор сжатия. После вывода строки «GMRES starts» запускается GMRES,за 39 итераций процесс сходится с заданной точностью 10−6 . После этоговыводится время аппроксимации и расчёта списка блоков, время матричновекторного умножения, время работы GMRES и всей программы.Для запуска параллельной версии используется PBS (Portable BatchSystem – система пакетной обработки заданий) скрипт. Фактически, PBSскрипт представляет собой bash скрипт, в котором указывается, сколько ядервычислительного кластера используется, сколько оперативной памяти приэтом выделяется и тд. Также указывается ядра кластера, на которых будетвыполняться программа.
Пример PBS скрипта для программы, выполняю42щей численное решение краевых задач для уравнения Гельмгольца и задачдифракции приведен на следующем листинге.Рисунок 3.1 – Результат работы программы43#PBS −k oe#PBS −r n#PBS −l nodes =1:ppn=16#PBS −q vl_mars#PBS −N d i f r a c t i o n _ p a r a l l e l _ 1 6##!/ b i n / she x p o r t OMP_NUM_THREADS=16cd /home/ t a l t y k i n a /masha/ h e l m h o l t z / s r c / D i f _ p a r a l l e l./ densityПервая строка задаёт имена файлов для потока вывода с пометкой «o»и для вывода ошибок с пометкой «e». Опция «#PBS -r n» говорит отом, что задача не будет перезапускаться самостоятельно.
Выражение«#PBS -l nodes=1:ppn=8» задаёт, сколько ядер и узлов будет использовано. В данном случае используется один узел с 8 ядрами. Опция «#PBS-q vl_mercury » определяет имя очереди узлов, на котором будет запущено задание. Имя задания определяется с помощью опции «#PBS -Ndifraction_parallel_1». Количество OpenMP потоков задаётся в параметрахexport «OMP_NUM_THREADS=1». Указание на то, что используется bashскрипт определяется командной «##!/bin/sh». Далее идут команды оболочки bash «cd /home/taltykina/masha/helmholtz/src/Dif_parallel» для переходав нужную директорию и «./density» для запуска программы.3.4Численные экспериментыПример 1. Рассматриваются задачи 1 и 2, где Γ – единичная сфера с центром в начале координат. Граничные условия:() () = exp(3 ), ∈ Γ,(3.1)волновые числа 1 = 1, 2 = 14, 3 = 30.В качестве тестовых задач для вычислительных экспериментов выбирались трёхмерные задачи Дирихле для уравнения Гельмгольца с известнымиточными решениями [5].
Каждая задача решалась дважды: без использова44ния мозаично-скелетонного метода в GMRES и с его применением.Для примеров 1, 2 и 3 блоки «дальней» зоны аппроксимировались с точностью = 10−6 для 1 = 1 и 2 = 14 и с точностью = 10−5 для 3 = 30.Точность GMRES составляла 10−8 для 1 = 1 и 2 = 14, а для 3 = 30 онаравнялась 10−7 . Количество точек дискретизации изменялось от 1000 до128000, уровень дерева кластеров варьировался от 4 до 6.Для проверки правильности работы алгоритма сравнивались приближённые решения интегральных уравнений и исходных задач из примера 1, полученные с применением мозаично-скелетонного метода в GMRES, с их известными аналитическими решениями [9]. На рисунке 3.2 приведены графики погрешностей приближённых решений (плотностей) интегральных уравнений взависимости от числа узловых точек для волновых чисел из примера 1.Погрешности вычислены в норме пространства сеточных функций [9]∑︁⃦ ℎ ⃦2⃦ ⃦ −1/2 = * ,(Γ)ℎ, =1где * – комплексно сопряжённое к число,¯ ¯= 3/22 ∫︁(︀)︀exp −2 , ̸= , =¯2 ¯+.2 3/2 2 1/20Согласно рисунку 3.2 при удвоении количества точек дискретизации погрешность падает в два раза.
Здесь и далее погрешности решений, полученных сиспользованием быстрого метода и без его использования, практически совпадают.На рисунке 3.3 приведены погрешности решений краевых задач из примера 1, вычисленные в норме пространств сеточных функций ℎ0 (Ω() ). Сплошными линиями обозначены погрешности для , штриховыми – для . Видно, что и в этом случае погрешности решений при удвоении количества точекдискретизации уменьшаются в два раза. Это значит, что метод имеет второйпорядок точности относительно ℎ2 ∼ −1 , где – порядок СЛАУ.Далее рассмотрены зависимости времени, необходимого для приближённого решения СЛАУ, от порядка систем для разных волновых чисел. Сравни45Рисунок 3.2 – Погрешности решений интегральных уравнений (1.15) изпримера 1вая результаты вычислительных экспериментов, приведённых на рисунке 3.4,можно заметить, что применение мозаично-скелетонного метода приводит ксущественному уменьшению времени решения. В исходном методе при удвоении количества точек дискретизации время возрастает в 4 раза, т.е.
еговычислительная сложность имеет оценку ( 2 ). Использование мозаичноскелетонного метода позволяет понизить эту сложность до почти линейной,и при удвоении порядка СЛАУ время возрастает лишь в 2.5-3 раза. Здесь идалее время измеряется в секундах.Вычислим теперь мозаичный ранг (2.11) и фактор сжатия для задач изпримера 1. Их значения приведены в таблицах 3.1 и 3.2.
Фактор сжатия задаётся следующей формулой:=mem(() )100,mem()где mem(() ) – объём памяти, необходимой для хранения матрицы в малоранговом формате, mem() – объём памяти для хранения исходной матрицы.46Рисунок 3.3 – Погрешности решений задач 1 (сплошная линия) и 2(пунктирная линия) из примера 1Вычислительные эксперименты показали, что с ростом числа узловых точекмозаичный ранг растёт как (ln3 ( )), а фактор сжатия, начиная с некоторого , уменьшается как (ln3 ( )/ ).
Это значит, что эффективностьприменения мозаично-скелетонного метода с ростом существенно возрастает.Таблица 3.1 – Мозаичный ранг для задач из примера 1k∖M11430998204239988150 15974 32598498.8 813.4 1057.8 1321.9 1601.1 1935.7499.0 1021.0 1541.1 1935.0 2287.1 2685.3499.0 1021.0 1924.1 2480.5 2925.8 3409.0638862312.83113.83897.71279402844.93682.64508.9На рисунке 3.5 представлены графики зависимостей времени решенияСЛАУ от количества задействованных ядер кластера. Видно, что при удвоении числа ядер время решения СЛАУ и работы всей программы уменьшаетсяв среднем в 1.5 раза.Результаты вычислительных экспериментов показали, что мозаично47Рисунок 3.4 – Время решения СЛАУ для примера 1 с использованиеммозаично-скелетонного метода (пунктирная линия) и без его использования(сплошная линия)Таблица 3.2 – Фактор сжатия для задач из примера 1.k∖M11430998 2042100.0 79.7100.0 100.0100.0 100.0399852.977.196.38150 15974 32598 63886 12794032.4 20.111.97.24.547.5 28.616.59.85.860.9 36.620.912.27.1скелетонный метод даёт существенное ускорение в работе программы длязадач из примера 1.
Для = 30 время решения СЛАУ уменьшается почти в200 раз.Пример 2. Рассматриваются внутренние задачи Дирихле для эллипсоида с полуосями (0.75, 1, 0.5) и центром в точке (0, 0, 0), граничные условияимеют вид () = exp(3 ), ∈ Γ,волновые числа те же, что и в примере 1.Правильность работы алгоритма проверялась путём сравнения прибли48Рисунок 3.5 – Время решения СЛАУ для примера 1 при распараллеливании.Порядок СЛАУ – 63886 (сплошная линия) и 127940 (пунктирная линия)жённых решений внутренних задач Дирихле из примера 2 с их точными решениями. Графики погрешностей, обозначенные сплошными линиями, приведены на рисунке 3.6.
Видно, что с ростом количества точек дискретизациипогрешности решений уменьшаются пропорционально ℎ2 .На рисунке 3.7 представлены затраты времени на решение СЛАУ дляпримера 2 с использованием мозаично-скелетонного метода и без его использования. Видно, что, как и в примере 1, мозаично-скелетонный метод позволяет значительно уменьшить время вычисления приближённых решенийинтегральных уравнений. Для волнового числа = 30 оно уменьшается более, чем в 300 раз. При этом сложность алгоритма возрастает с ростом стой же скоростью, что и в примере 1.Значения мозаичного ранга и фактора сжатия для примера 2 в зависимости от количества точек дискретизации для разных волновых чисел приведены в таблицах 3.3 и 3.4.
С увеличением числа узловых точек фактор сжатияуменьшается с той же скоростью, что и в примере 1, а эффективность методарастёт.49Рисунок 3.6 – Погрешности решений задач 1 из примера 2 (сплошнаялиния) и задач 2 из примера 3 (пунктирная линия)Таблица 3.3 – Мозаичный ранг для задач из примера 2k∖M114301032482.4516.0516.02096 40108022739.4 988.1 1259.9920.7 1286.5 1633.6983.4 1387.9 1765.8160331560.21982.52119.8321201921.62378.82496.8641392360.92845.22933.41284962889.03399.43428.5Таблица 3.4 – Фактор сжатия для задач из примера 2k∖M11430103293.5100.0100.0209670.687.993.8401049.364.269.28022 16033 32120 64139 12849631.4 19.512.07.44.540.7 24.714.88.95.344.0 26.415.69.25.3Результаты работы параллельного варианта программы для примера 2приведены на рисунке 3.8.
Как и в примере 1, при удвоении числа ядер времярешения СЛАУ уменьшается в среднем в 1.5 раза.Вычислительные эксперименты показали, что и для примера 2 предпочтительнее осуществлять матрично-векторное умножение в GMRES с использо50Рисунок 3.7 – Время решения СЛАУ для примера 2 с использованиеммозаично-скелетонного метода (пунктирная линия) и без его использования(сплошная линия)ванием мозаично-скелетонного метода.Пример 3. Рассматриваются внешние задачи Дирихле для эллипсоида сполуосями (0.75, 1, 0.5) и центром в точке (0, 0, 0), граничные условия имеют вид () = exp ( | − 0 |)/| − 0 |,волновые числа те же, что и в примере 1, 0 = (0.375, 0.5, 0.25).На рисунке 3.6 приведены графики погрешностей решений внешних задач Дирихле из примера 3, обозначенные пунктирными линиями. Видно, чтопогрешности решений этих задач близки к погрешностям решений задач стеми же волновыми числами из примера 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
