Содержание к диссертации
Введение
1 О корректно и некорректно поставленных задачах 12
1.1 О корректной постановке граничных условий для уравнений мелкой воды 12
1.2 Обзор методов решения некорректных и обратных задач 16
2 Обратная задача о восстановлении граничной функции для уравнений мелкой воды в открытой акватории 26
2.1 Дифференциальная постановка задачи 26
2.1.1 Начально-краевая задача для уравнений мелкой воды . 26
2.1.2 О корректной постановке краевых условий для уравнений мелкой воды 27
2.1.3 Обратная задача о восстановлении граничной функции для уравнений мелкой воды 32
2.2 Слабая постановка задачи. Теорема существования и единственности 33
2.2.1 Функциональные пространства и нормы 33
2.2.2 Доказательство разрешимости задачи 35
2.3 Задача оптимального управления с регуляризацией 42
2.3.1 Задача на минимизацию функционала 42
2.3.2 Поиск граничной функции из пространства 2(1^2) 44
2.3.3 Поиск граничной функции из пространства И-^Г^) . 45
2.3.4 Поиск граничной функции из пространства И^ (Г2) . 46
2.3.5 Сходимость решения регуляризированной задачи оптимального управления к решению обратной задачи 48
2.4 Итерационный численный алгоритм. Теорема о сходимости . 56
3 Численные эксперименты 65
3.1 Численное решение прямой задачи 65
3.1.1 Дискретизация по пространству 65
3.1.2 Численное решение прямой задачи 67
3.2 Численные эксперименты по восстановлению граничной функции по модельным данным наблюдений 70
3.3 Параллельная реализация 84
3.3.1 Оценка потенциального ускорения параллельного алгоритма с использованием технологии МРІ 84
3.3.2 Оценка потенциального ускорения параллельного алгоритма с использованием технологии ОрепМР 88
3.3.3 Исследование ускорения параллельной MPI-программы на высокопроизводительных кластерных системах 91
3.3.4 Сравнение двух реализаций МРІ и стратегий управления памятью 94
3.3.5 Сравнение ускорений параллельных версий программы: ОрепМР, МРІ и их совмещения MPI+ОрепМР 99
Заключение 106
Список литературы
- Обзор методов решения некорректных и обратных задач
- О корректной постановке краевых условий для уравнений мелкой воды
- Поиск граничной функции из пространства И^ (Г2)
- Численные эксперименты по восстановлению граничной функции по модельным данным наблюдений
Введение к работе
Актуальность темы исследования. Описание динамики распространения поверхностных волн в открытых акваториях, связанных с мировым океаном, является актуальной задачей численного моделирования. Широко распространены модели на основе уравнений мелкой воды (Вольцингер Н. Е., Гилл А., Железняк М. П., Каган Б. А., Марчук Г. П., Пелиновский Е. Н., Федотова 3. П., Хакимзянов Г. С, Чубаров Л. Б, Stoker J. J., Whitham G. и др.). Введение в модель открытой границы по морю позволяет учитывать влияние океана на рассматриваемую область, которое обычно описывается граничной функцией в краевом условии (Агошков В. И., Баклановская В.Ф., Quarteroni A., Oliger J., Saleri F. и др.). На практике граничная функция, как правило, неизвестна и ее следует найти вместе с другими неизвестными модели (скоростями и возвышением свободной поверхности). В связи с этим актуальна обратная задача о восстановлении граничной функции с использованием дополнительной информации, полученной в ходе наблюдений за поведением свободной поверхности на границе по морю. При разработке методик решения обратной задачи необходимо учитывать, что данные наблюдений могут быть известны только на части открытой границы или с некоторой погрешностью. Такие задачи в большинстве случаев некорректны, поэтому для их решения с приемлемой точностью необходимо использовать методы решения некорректных задач (Агошков В. П., Алексеев Г. В., Бакушинский А. Б., Вайникко Г. М., Васильев Ф. П., Васин В. В., Иванов В. К., Кабанихин С. И., Лаврентьев М.М., Пененко В. В., Романов В. Г., Тихонов А. Н., Ягола А. Г., Engl Н. V., Klibanov М., Uhlman G., Wang Y.-F., Yang С. и др.).
Численное решение обратной задачи о восстановлении граничной функции требует большого объема вычислений, что делает актуальным создание эффективного параллельного программного обеспечения.
Цель исследования — разработка, исследование и реализация на SMP-узловом кластере итерационного численного алгоритма решения обратной задачи о восстановлении граничной функции для уравнений мелкой воды в открытой акватории.
Для достижения поставленной цели были решены следующие задачи.
-
Доказаны существование и единственность решения обратной задачи о восстановлении граничной функции для уравнений мелкой воды.
-
Некорректная обратная задача сведена к корректно поставленной задаче оптимального управления на минимизацию функционала, включающего стабилизирующий по А. Н. Тихонову функционал.
-
Предложены и обоснованы три вида стабилизирующего по А. Н. Тихонову функционала для задачи минимизации.
-
Построен итерационный численный метод восстановления граничной функции на границе по морю.
-
Доказана теорема о сходимости предложенного итерационного алгоритма к решению исходной обратной задачи в слабом смысле.
-
Разработано эффективное параллельное программное обеспечение для SMP-узлового кластера с использованием технологий MPI, ОрепМР и MPI+OpenMP для численного решения обратной задачи о восстановлении граничной функции.
-
Проведены вычислительные эксперименты для акватории Охотского моря по восстановлению граничной функции по данным наблюдений различного качества — гладким, с наложением белого шума, с пропусками.
Методы исследования. В диссертации используются фундаментальные результаты и методы теории некорректных и обратных задач, оптимального управления и сопряженных уравнений, функционального анализа и уравнений математической физики, теории итерационных методов, вычислительный эксперимент.
На защиту выносятся следующие результаты, соответствующие паспорту специальности 01.01.07 — вычислительная математика.
-
Предложен и реализован итерационный численный алгоритм решения обратной задачи о восстановлении граничной функции для уравнений мелкой воды в открытой акватории по данным наблюдений о возвышении свободной поверхности на границе по морю.
-
Доказана теорема о сходимости предложенного итерационного алгоритма к решению обратной задачи о восстановлении граничной функции.
3. Создан эффективный параллельный программный комплекс для
SMP-узлового кластера с использованием технологий MPI, ОрепМР и
MPI+OpenMP, предназначенный для решения обратной задачи о восстанов
лении граничной функции.
Научная новизна выносимых на защиту результатов заключается в следующем.
-
Для обратной задачи о восстановлении граничной функции для уравнений мелкой воды в открытой акватории впервые разработан, обоснован и численно реализован итерационный метод, позволяющий восстановить граничную функцию по данным наблюдений о возвышении свободной поверхности, заданным с погрешностью или только на части границы по морю.
-
Создан оригинальный программный комплекс, предназначенный для эффективного решения обратной задачи о восстановлении граничной функции на высокопроизводительных системах с общей, распределенной памятью и на SMP-узловом кластере.
Достоверность и обоснованность результатов обеспечивается применением строгих математических доказательств и верификацией построенных алгоритмов на задачах с известными решениями.
Теоретическая и практическая ценность. Теоретическая значимость диссертационной работы состоит в обосновании предлагаемого алгоритма, а также в примененной методике на основе теории оптимального управления и сопряженных уравнений, позволившей восстановить неизвестные данные на всей границе по дополнительной информации с части границы. Практическая ценность работы заключается в возможности применения разработанного программного комплекса при решении широкого класса задач моделирования поверхностных волн в больших открытых акваториях.
Основные положения и результаты диссертации докладывались и обсуждались на научном семинаре ИМФИ СФУ «Компьютерное решение многомерных задач» и на следующих конференциях: Международная конференция, посвященная 90-летию со дня рождения академика Н.Н. Янен-ко (Новосибирск, 2011); Международная конференция «Математические и информационные технологии, MIT-2011» (Сербия, Черногория, 2011); 11th International Conference on Parallel Computing Technologies, PaCT-2011 (Казань, 2011); XII, XIII и XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Новосибирск, 2011, 2012, 2013); Шестая международная конференция «Inverse Problems: Modeling and Simulation» (Турция, 2012); 5th Conference on Numerical Analisis and Applications (Болгария, 2012); Международная конференция «Обратные и некорректные задачи математической физики», посвященная 80-летию со дня рождения академика М.М. Лаврентьева (Новосибирск, 2012); Международная молодежная научная школа-конференция «Теория и численные методы решения обратных и некорректных задач» (Новосибирск, 2012, 2013); Международная конференция «European Numerical Mathematics and Advanced Applications, ENUMATH» (Швейцария, 2013).
Основные результаты диссертации опубликованы в 15 печатных работах, включая (в скобках в числителе указан общий объем этого типа публикаций в печатных листах, в знаменателе — объем принадлежащий лично автору) 4 статьи в периодических изданиях, рекомендованных ВАК (3.4/2.2), 1 статью в международном рецензируемом журнале (1.68/0.8), 10 статей в трудах конференций (5.7/4.0).
Личный вклад. Результаты, составляющие основное содержание диссертации, получены автором самостоятельно. Во всех совместных работах автор участвовал в формулировках постановок задач, совместно осуществлял теоретические исследования по ускорению вычислений, самостоятельно обосновывал итерационные алгоритмы, реализовывал параллельный программный
комплекс, выполнял численные расчеты и осуществлял анализ результатов. Объем и структура работы. Диссертация состоит из введения, трех глав, заключения, списка цитируемой литературы. Общий объем диссертации составляет 123 страницы, включая 26 рисунков, 3 таблицы. Список цитируемой литературы содержит 168 наименований.
Обзор методов решения некорректных и обратных задач
Диссипативные условия считаются допустимыми и обеспечивают наличие некоторой энергетической оценки для решения системы (1.4) [167]. В ряде случаев доказана теорема единственности и существования обобщенного решения системы (1.4), если в каждой точке границы условия являются диссипативными и размерность линейного подпространства P(t, ж, у) является максимально возможной (см., например, [148,163]). В общем случае, если граничные условия диссипативны, то их корректная постановка может быть доказана.
Для квазилинейной задачи (1.1) - (1-2) условие (1.6) можно считать, по-видимому, подобным необходимому условию ее корректной постановки, в то время как для линейного уравнения (1.4) оно является и достаточным [36,41,167].
Если граничные условия не являются диссипативными, то для исследования их корректности может быть применен анализ нормальных колебаний Крейса [161,162]. В этом случае уравнение (1.1) записывается в новых переменных, которые являются гармоническими функциями, а затем исследуются его собственные значения и, далее, проверяются некоторые условия, при которых выполняется априорная оценка (1.3). В работе [161] Х.-О. Крей-сом для линейной начально-краевой задачи гиперболического типа выводятся необходимые и достаточные условия ее корректной постановки (выполнения оценки (1.3)).
При исследовании системы (1.1) анализом нормальных колебаний Крейса можно так же, как и в случае применения энергетического метода, рассмотреть ее линеаризованную модель и установить некоторые необходимые условия корректности для граничного условия. В работе [167] анализ Крейса применен для корректной постановки краевых условий для гидростатической системы уравнений, а также предложены краевые условия для уравне 15 ний мелкой воды, корректность которых может быть доказана с помощью анализа нормальных колебаний Крейса.
В работах [137,138] на примере постановки граничных условий для линейных и нелинейных уравнений мелкой воды показано, что для некоторых не диссипативных граничных условий при рассмотрении слабой формы краевой задачи может быть напрямую доказана априорная оценка вида (1.3), т.е. корректность граничного условия. В работе [137] также приведены некоторые определения допустимых граничных условий, которые задают необходимые условия для доказательства априорной оценки.
Сложности выбора корректного граничного условия для уравнений мелкой воды обсуждаются также в работах [13,36,138,167], где рассмотрены разные подходы к решению данной проблемы для некоторых приливных моделей. Ряд работ посвящен проблеме постановки граничного условия для линейного случая двух независимых переменных [36,41] и трех независимых переменных [41,147,168]. В некоторых краевых задачах можно вывести энергетическую оценку и определить корректное граничное условие (см., например, [137,138,161,167]).
При постановке краевых условий для уравнений мелкой воды в первую очередь необходимо определить их количество (см., например, [13,36]). При этом, как правило, необходимо учитывать, что реальная граница рассматриваемой области часто разделена на два подмножества: «твердая» (линия берега) и «открытая» (граница по морю). В этом случае знак собственного числа матрицы Аn: определяемой (1.7), может зависеть от рассматриваемой части границы (см., например, [13]).
Приведем следующий пример. Пусть уравнение (1.1) описывает модель мелкой воды. Обозначим через Un = U\fi\ + U2TI2 нормальную компоненту вектора скорости U = (u\,U2)- Поскольку собственные числа матрицы Аn для нелинейных уравнений мелкой воды могут зависеть от Un, то их знак может меняться. Тогда при определении количества граничных условий на открытой части границы необходимо учитывать «приходит» ли возмущение в область, т.е. Un 0 (например, приток реки), или же «уходит» из области, т.е. Un 0. Из-за непостоянного знака собственных чисел на открытой части границы количество граничных условий может быть различным в зависимости от того, втекает жидкость в область или утекает из нее. В связи с этим в случаях, когда нам неизвестно втекает или вытекает жидкость через границу, невозможно априори задать корректно граничные условия на открытой части границы.
В работах [13,134,136-138,147,165,167] для некоторых моделей, описывающих распространение поверхностных волн, предлагаются различные допустимые краевые условия для твердых и открытых участков границы области. 1.2 Обзор методов решения некорректных и обратных задач Во многих задачах математической физики для однозначного определения решения должны быть заданы значения ряда входных параметров (вытекающих из свойств среды), начальных и граничных функций. Однако на практике часто возникают ситуации, когда часть параметров или функций неизвестны [9] и их необходимо определить, используя некоторую дополнительную информацию о решении, т.е. решить обратную задачу [1,2,8,57,67, 85]. Такие задачи в ряде случаев некорректны
О корректной постановке краевых условий для уравнений мелкой воды
Среди итерационных методов решения некорректных задач, следуя [1], выделим три группы методов, которые условно назовем методами теории экстремальных задач, итерационными методами теории некорректных задач и методами общей теории итерационных процессов.
К первой группе методов отнесем прямые методы минимизации функционалов (1.9), (1.10) из общей теории решения экстремальных задач [22].
Одними из наиболее эффективных методов для решения класса задач линейной алгебры с неустойчивостью численной реализации, то есть некорректно поставленных, считаются алгоритмы метода сопряженных градиентов. Первым целенаправленно применил итерации для решения некорректно поставленной задачи В.М. Фридман: «методы типа наискорейшего спуска» Фридмана [124] можно трактовать в качестве несколько упрощенных представителей семейства методов сопряженных градиентов [9,126].
Рассмотрим экстремальную задачу (1.10) при А = I. Для отыскания ее приближенного решения и воспользуемся градиентным методом ип = un_i -rnJa(wn_i), п = 1,2,..., (1.15) где щ — начальное приближение, Ja(un-\) = 2аип-\ + 2 А (Аип-\ — /). тп — положительные параметры, которые выбираются способом, подходящим для практической реализации [1,22,67,68]. Например, можно принять тп = (7(1 + п)-/3, С = const 0, 1 /3 1/2. Оценка сходимости метода (1.15) к единственной точке минимума функционала Ja(u) представлена в работах [1,2,22].
В работах М.М. Лаврентьева, О.М. Алифанова, А.Б. Бакушинского, Г.М. Вайникко, В.В. Васина, X. Энгла и других авторов предложены и развиты методы второй группы, так называемые итеративные методы решения некорректных задач [9,14-16, 20, 29, 30, 86, 87,145]. Для этих методов параметром регуляризации является номер итерации, и должно быть сформулировано правило остановки, согласующее число итераций с погрешностью 5 входных данных. Рассмотрим подробнее методы, предложенные в [1,20,57].
В методе (1.18) помимо номера итерации п появляется еще один параметр регуляризации — а. В результате решается некорректная задача как предельный случай корректно поставленной задачи при а — 0. Согласно [1,20,95,107] алгоритмы (1.17), (1.18) в силу приведенных ограничений на г являются сходящимися.
Тогда для сходимости число проводимых итераций в (1.17) и (1.18) не может быть произвольным, а должно согласовываться с погрешностью 5 входных данных [1,20,57]. Например, должно быть п(5) —оо и 5-п(5) — 0 при 5 — 0. Кроме того, в алгоритме (1.18) параметр регуляризации а также нельзя брать сколь угодно малым независимо от значения 5 [1,57].
К третьей группе методов относится множество итерационных процедур, получаемых применением алгоритмов общей теории итерационных процессов [95,97,107] к уравнению (1.16) (или уравнению (1.11)) с симметричным положительно определенным оператором.
Рассмотрим задачу (1.8), когда ядро оператора N(A) = 0, а оператор А А может быть неограниченным. Выберем в регуляризированном уравнении(І.П), соответствующем задаче (1.8), самосопряженный положительно определенный оператор Л [113], порождающий пространство U, непрерывно вложенное в X. При этом выполняется
На основе общей теории итерационных процессов могут быть сформулированы многие другие итерационные алгоритмы для уравнений (1.11) и (1.16). Например, часто используются метод простой итерации и метод минимальных невязок [1,57,68,95,97,107], которые можно записать формально в виде (1.18), но с различным выбором параметра т.
Итерационные алгоритмы рассмотренных трех групп часто совпадают формально, однако идеи выбора параметров, обеспечивающих их устойчивость, различны. Многие подходы к выбору этих параметров, известные из теории некорректных [15,102,113] и экстремальных задач [1,22,95] часто на практике трудно реализуемы.
Рассмотрим еще один вариант выбора параметра г для итерационного процесса вида (1.18). Пусть г = тп_і — переменный параметр и задача (1.8) плотно разрешима (т.е. замыкание R(A) совпадает с Y). Тогда при достаточно малом а — +0 согласно [2,22] параметр тп_і можно выбирать в виде
При решении некорректных задач с наличием свойства плотной разрешимости выбор тп_і по формуле (1.20) является одним из наиболее эффективных [2].
Большое внимание в теории некорректных задач уделяется выбору параметра регуляризации а в задаче (1.10) [20, 57, 102]. Методы его выбора условно подразделяются на априорные и апостериорные.
Первый априорный способ выбора был предложен А.Н. Тихоновым [1, 113,116]. В этом случае задается скорость убывания а: а(5) — 0, 6/а(6) — 0 при 5 — 0. Практическое применение априорных способов выбора параметра регуляризации вызывает большие затруднения, поскольку при решении прикладных задач необходимо найти приближенное решение при фиксированном уровне погрешностей 5 правой части уравнения (1.8).
К апостериорному способу можно отнести обобщенный принцип невязки (ОПН), предложенный и обоснованный А.В. Гончарским, А.С. Леоновым, А.Г. Яголой [43,44,89,117,128-131]. В ОПН строится функция параметра регуляризации а 0, которая удовлетворяет некоторым свойствам и называется обобщенной невязкой. Затем ищется ее корень с использованием известных численных методов отыскания корней монотонных непрерывных функции. ОПН является обобщением принципа невязки В.А. Морозова [102], разработанного для случая точно заданного оператора.
С точки зрения удобства практической реализации выделим также алгоритмы выбора параметра а на основе экстраполяции по Ричардсону и способ выбора а, основанный на классической процедуре экстраполяции по а, предложенные в [99] и [2]. Глава 2
Обратная задача о восстановлении граничной функции для уравнений мелкой воды в открытой акватории
Пусть (г, Л, в) — сферическая система координат с началом в центре Земного шара, где 0 А 27Г, —7г/2 в 7г/2, а г — радиальное расстояние. Здесь Л соответствует географической долготе, увеличивающейся на восток, а в — географической широте, растущей с юга на север. Будем рассматривать вместо географической широты в угол f = в + 7г/2 Є [0; 7г], отсчитываемый от плоскости экватора. Зафиксируем далее г = RE-, где RE — радиус Земли, который в этой модели считается постоянным. Обозначим через Q некоторую область в плоскости (Л, (/?) с кусочно-гладкой границей Г класса С 2 без пересечений и нулевых углов сопряжения участков гладкости. Причем Г=Гі U Г2, где Гі = Гі береговая граница, а Г2 = Г \ Г1 граница по морю, разделенные общими точками. Предположим, не теряя общности, что Гі и Г2 разделены только двумя общими точками 7ь72 Є Г. Обозначим через Хі и Х2 характеристические функции соответствующих участков границы.
Поиск граничной функции из пространства И^ (Г2)
Для того чтобы показать сходимость решения (Фа, da) задач 4.1 - 4.3 к решению задачи (2.31) - (2.32) в слабом смысле (2.91) - (2.92), достаточно перейти к операторной форме (2.86) задач 4.1 - 4.3 и операторной форме (2.90) системы уравнений (2.91) - (2.92) и показать сходимость решения уравнения (2.86) к решению уравнения (2.90).
Поскольку оператор Т = CAB линеен (по построению) и непрерывен, как было показано в доказательстве п. 1 теоремы 4, по Теореме 1 [1, с. 128] для функции da Є X при любом д Є ІУ2(ГО) выполняется неравенство
Для численного решения систем задач 4.1 - 4.3 будем применять итерационные методы, характерные для решения некорректно поставленных задач [20]. А именно, поскольку задача (2.31) - (2.32) некорректна, то для получения хорошего приближения к ее решению в слабом смысле, применим итерационные методы регуляризации. Можно рассмотреть, по крайней мере, два различных итерационных процесса, регуляризирующих решаемую задачу 4 и отличающихся между собой выбором параметров регуляризации.
Зафиксируем достаточно малое а. Зададим некоторое начальное приближение граничной функции da на 1 V Рассмотрим следующие итерационные схемы, состоящие согласно задаче 4 в последовательном решении прямой, сопряженной задач и уточнении граничной функции d на каждой итерации / = 0,1,2...
Здесь и далее при описании итерационных алгоритмов верхний индекс в скобках указывает номер итерации, а 7/ является основным итерационным параметром. Оператор Л = Л , і = 1, 2, 3, где индекс і соответствует номеру 4.і решаемой задачи.
Итерационные процессы 1 и 2, организованные по схемам 1 и 2 соот-ветсвенно, относятся к итерационным методам регуляризации [1,20]. В итерационной схеме 1 параметром регуляризации является номер итерации; регуляризация достигается за счет многократного итерирования. Итерационная схема 2 имеет два параметра регуляризации — номер итерации и значение а. Здесь происходит решение некорректной задачи как предельного случая корректно поставленной задачи (при а — 0), поэтому параметр а выбирается достаточно малым.
Итерационные схемы 1-2, выбранные с точки зрения итерационных методов решения некорректных задач, формально могут быть также получены при применении общей теории итерационных процессов к уравнению (2.86), в частности, при его численном решение методом минимальных невязок.
Параметр 7/ итерационных схем 1-2 может быть выбран методом подбора, тогда 7/ = const для всех /. Для того чтобы повысить скорость сходимости итерационных схем 1-2, можно вычислять 7/ на каждой итерации / в соответствии с методом минимальных невязок [2] следующим образом:
Полученный по формуле (2.95) параметр 7/ используем в п. 4 итерационных схем 1-2. Чтобы избежать большого дополнительного количества вычислений на каждой итерации /, можно один раз вычислить 7о, используя (2.95), и далее, на итерациях с номером / = 1, 2..., положить 7/ = 7о Рассмотрим еще один способ задания параметра 7/ [2], который вычисляется по формуле (1.20). Тогда после решения уравнений из п. 1-3 одной из Итерационных схем 1-2 находим (0
В численных экспериментах при прочих равных условиях (выбор параметра 7, малость параметра а, точность) итерационный процесс по схеме 2, как правило, сходится быстрее, чем первый.
В итерационных схемах 1 и 2 при уточнении граничной функции d сначала в пункте 3 численно решается одно из уравнений (2.78) - (2.80) (с а = 1) задач 4.1 - 4.3 соответственно, а затем проводится собственно итерационное уточнение (пункт 4 в итерационных схемах). Таким образом, в итерационных схемах 1 и 2 способ уточнения функции d зависит от номера решаемой задачи (4.1, 4.2 или 4.3).
При решении задачи 4.1 (уравнение (2.78)) используем решение сопря-женнои задачи с,а для итерационного уточнения аа согласно пункту 4 итерационной схемы 1 или 2.
При решении задачи 4.2 находим решение wa краевой задачи для уравнения (2.79), аппроксимировав производные, например, конечными разностями на неравномерной сетке вдоль границы Г2, и решая систему алгебраических уравнений с трехдиагональной матрицей методом прогонки. Затем ис (0 М) пользуем это решение wa для итерационного уточнения аа согласно пункту 4 итерационной схемы 1 или 2.
При численном решении задачи 4.3 в уравнении (2.80) оператор А1 2 записывается в виде матрицы Л следующим образом.
Аппроксимация производных вдоль границы Г2 из оператора Лв (2.19) (например, конечными разностями на неравномерной сетке) дает матрицу Ан- Если полученная матрица Ah является эрмитовой, то имеет место спектральное разложение Ah = QDQ , где Q — унитарная и D — диагональная матрицы. Тогда Ah = QDl 2Q . В общем случае с помощью QR-алгоритма (см., например, [150]) матрица Ah может быть представлена в форме Шура: Ah = QTQ 7 где Q — унитарная и Т — верхняя треугольная матрицы, тогда А[/2 = QT1/2Q Затем используя дискретную аппроксимацию А1 2, находим, например, методом Гаусса решение wa системы полученных при дискретизации (2.80) алгебраических уравнений. После чего используем найденное wa для итерационного уточнения da согласно пункту 4 итерационной схемы 1 или 2.
Численные эксперименты по восстановлению граничной функции по модельным данным наблюдений
Вторым кластером, на котором проведены серии расчетов, является кластер ТГУ SKIF Cyberia, который содержит 283 двухпроцессорных двухъядерных узла (1132 ядра) IntelXeon5150 2.66 Ггц, с суммарным объемом дисковой памяти 1136 Гб и объемом дискового пространства 22.56 Тб. Все узлы объединены высокопроизводительной сетью передачи данных InfiniBand.
Наконец, эксперименты были частично повторены на высокопроизводительном вычислительном комплексе НГУ, на базе кластера из 64 восьмиядер-ных вычислительных узлов, основанных на блэйд-серверах Hewlett-Packard BL460c. Все вычислительные узлы объединены высокопроизводительной сетью InfiniBand DDR 4х. В кластере используется параллельная файловая система хранения SFS емкостью 24 ТБ, основанная на технологии Lustre. Кластер SKIF Cyberia и HP-кластер ИВЦ НГУ отличаются, в интересующем нас плане, количеством ядер на узел.
Ясно, что потенциальное ускорение параллельной программы зависит от размерности сетки. Исследования зависимости ускорения проводились вплоть до 32 процессов, где на рассматриваемой сетке алгоритм хорошо масштабируем. Каждый вычислительный процесс всегда запускался на отдельном вычислительном ядре. Временные характеристики замерялись средствами MPI каждым процессом в отдельности, за показатель принималось максимальное значение. Все временные характеристики усреднялись по результатам нескольких десятков расчетов, исключая экстремальные значения. Дисперсия измерений, как правило, была незначительна, за исключением некоторых расчетов на кластере ИВМ СО РАН.
На рисунке 3.18 представлена зависимость ускорения вычислений от количества используемых процессов, полученных на кластерах ИВМ СО РАН и SKIF Cyberia для случая декомпозиции расчетной области без перекрытий. Для сравнения представлен график потенциального ускорения согласно оценке (3.7). На эффективность параллельной программы значимо не влияет способ декомпозиции расчетной области. На большом количестве ядер проявляется явное преимущество реализации двухточечных обменов с помощью неблокирующих функций.
Расчеты, проведенные на кластере СКИФ Cyberia показывают классическую картину ускорения, подтверждающую линейный характер его роста с увеличением количества процессоров с эффективностью около единицы (эффективность расчета для 32 узлов). Эксперименты на кластере НГУ подтверждают эти результаты. В экспериментах на кластере ИВМ СО РАН общий тренд ускорения совпадает с теоретическими оценками, однако его рост носит сильно неустойчивый характер, что побудило авторов к дальнейшим исследованиям.
Поскольку время выполнения программы складывается из времени вычислений, времени коммуникаций и дополнительного времени для операций, связанных с распределенностью данных, то были проведены серии расчетов, в которых эти составляющие были измерены отдельно. Во всех обсуждаемых 35 ЗО 25 20 15 10 5 О
Зависимость ускорения вычислений от количества доступных процессоров для различных кластерных систем и способов реализаций двухточечных обменов далее экспериментах тестировался вариант программы, реализующий декомпозицию без теневых граней и неблокирующую схему двухточечных обменов. Сравнение двух реализаций MPI и стратегий управления памятью
На рисунке 3.19 приведены результаты численных экспериментов по замеру времени, затрачиваемого на содержательные вычисления нашего параллельного ПО. Для того чтобы была возможность сравнить результаты расчетов с теоретическими оценками, исследована безразмерная величина ficalk = Ті1 /Ті — отношение времени выполнения вычислений для р процессов к времени выполнения всего алгоритма для одного процесса. Из рисунка видна хорошая согласованность времени, реально затраченного на вычисления с его теоретической оценкой. Немонотонное поведение ficalk для кластера ИВМ СО РАН продиктовало наше дальнейшее исследование, проведенное на подмножестве однородных узлов.
Количество процессов, р (шт.) Рис. 3.19: Исследование для различных кластерных систем времени, затраченного на вычисления в зависимости от количества доступных процессоров
ных реализаций MPI: общеизвестного MPICH2 v.l.2.1pl и OpenMPI v.1.4.1, являющегося «наследником» пакета LAM.
Рассматриваемая задача тестировалась в двух модификациях: со статическим и динамическим (calloc/free) выделением памяти под основные массивы и буферы. Сразу отметим, что вариант со статическим выделением не показал существенного преимущества какого-то одного пакета: расхождения во времени счета и во времени обменов данными во всех опробованных конфигурациях оказались достаточно малы, чтобы не принимать их во внимание.
Напротив, вариант с динамическим выделением памяти показал наличие зависимости от использованного пакета и его настроек. Строго говоря, исследования показали, что обнаруженные различия в поведении задачи зависят даже не от особенностей реализации тех или иных функций MPI в обоих пакетах, а связаны с отличиями в части работы с динамической памятью.
Пакет OpenMPI использует для управления динамической памятью менеджер памяти ptmaUoc, применяя его как для борьбы с фрагментацией, так и для увеличения производительности приложения засчет ускорения работы процедур malloc/free. Одна из настроек, управляющая стратегией выделения / освобождения памяти, называется mpi_leave_pinned: и по умолчанию эта настройка включена. В пакете MPICH2 подобной настройки нет, однако есть возможность управлять стратегией, которой руководствуется системная библиотека glibc при обработке запроса о выделении памяти путем вызова функции mallopt () с соответствующими аргументами.
