Помощь студентам в учебе
ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ ПОЛУЛАГРАНЖЕВОГО МЕТОДА ДЛЯ УРАВНЕНИЯ НЕРАЗРЫВНОСТИ
|
Введение 4
1 Обзор используемых численных методов и программных технологий 9
1.1 Обзор методов численного решения уравнения неразрывности 9
1.2 Обзор основных тенденций в области параллельного программирования 12
2 Полулагранжевый метод для уравнения неразрывности 16
2.1 Постановка задачи 16
2.2 Базовые интегральные тождества 17
2.3 Вычисление интеграла на верхнем слое по времени . . . 18
2.4 Вычисление интеграла на нижнем слое по времени . . . 21
2.5 Учет границы втекания 30
2.6 Численный метод 32
3 Параллельная реализация алгоритма 33
3.1 Последовательная реализация алгоритма 33
3.2 Предварительный анализ возможности распараллеливания алгоритма 34
3.3 Параллельная реализация алгоритма для вычислительных систем с общей памятью 35
3.4 Параллельная реализация алгоритма для вычислительных систем с распределенной памятью 36
3.5 Гибридная параллельная реализация 39
4 Результаты численных экспериментов 40
4.1 Тестовая задача №1 40
4.2 Тестовая задача №2 40
5 Анализ эффективность параллельных алгоритмов
5.1 Аппаратное и программное обеспечение для численных экспериментов
5.2 Анализ производительности OpenMP-версии алгоритма
5.3 Анализ производительности MPI-версии алгоритма
5.4 Анализ производительности гибридной версии алгоритма
Заключение 43
Список использованных источников 45
Приложения 51
Приложение А. Профили численного решения для тестовой задачи №2 51
Приложение Б. Значения нормы численного решения для тестовой задачи №2 52
1 Обзор используемых численных методов и программных технологий 9
1.1 Обзор методов численного решения уравнения неразрывности 9
1.2 Обзор основных тенденций в области параллельного программирования 12
2 Полулагранжевый метод для уравнения неразрывности 16
2.1 Постановка задачи 16
2.2 Базовые интегральные тождества 17
2.3 Вычисление интеграла на верхнем слое по времени . . . 18
2.4 Вычисление интеграла на нижнем слое по времени . . . 21
2.5 Учет границы втекания 30
2.6 Численный метод 32
3 Параллельная реализация алгоритма 33
3.1 Последовательная реализация алгоритма 33
3.2 Предварительный анализ возможности распараллеливания алгоритма 34
3.3 Параллельная реализация алгоритма для вычислительных систем с общей памятью 35
3.4 Параллельная реализация алгоритма для вычислительных систем с распределенной памятью 36
3.5 Гибридная параллельная реализация 39
4 Результаты численных экспериментов 40
4.1 Тестовая задача №1 40
4.2 Тестовая задача №2 40
5 Анализ эффективность параллельных алгоритмов
5.1 Аппаратное и программное обеспечение для численных экспериментов
5.2 Анализ производительности OpenMP-версии алгоритма
5.3 Анализ производительности MPI-версии алгоритма
5.4 Анализ производительности гибридной версии алгоритма
Заключение 43
Список использованных источников 45
Приложения 51
Приложение А. Профили численного решения для тестовой задачи №2 51
Приложение Б. Значения нормы численного решения для тестовой задачи №2 52
В настоящее время параллельное программирование активно применяется для ускорения научных вычислений, что позволяет решать все более широкий круг вычислительноемких задач, требующих большого объема оперативной памяти.
Применение прямых методов численного анализа требует большого объема вычислительных ресурсов. Однопроцессорный компьютер зачастую не может обеспечить требуемый объем оперативной памяти для работы с многомиллионными ячейками расчетных сеток, использование которых необходимо для достижения требуемой точности. Эффективным средством решения ресурсоемких задач является технология параллельных вычислений на распределенных системах кластерного типа. На пути перехода от персонального компьютера к суперкомпьютеру с параллельной архитектурой имеются определенные трудности, которые, во-первых, связаны с необходимостью распараллеливания вычислительного алгоритма, во-вторых, с принципиально более сложным написанием программного кода и недостаточно развитой системой отладки программ на кластере. При этом одним из факторов эффективного использования высокопроизводительной многопроцессорной вы-числительной техники является применение специальных методов математического моделирования. В связи с этим, одной из задач современной науки является развитие технологии математического моделирования, рассматривающей многопроцессорные вычислительные системы (МВС) как основной аппарат для вычислений.
Отметим далее, что за время существования МВС накоплен значительный опыт их использования, и они находятся в массовом доступе. Однако, огромные вычислительные возможности, предоставляемые этими системами, используются недостаточно. Причиной этому является сложность адаптации последовательных алгоритмов и программ к параллельным архитектурам. Поэтому разработка эффективных параллельных алгоритмов решения фундаментальных и прикладных задач, изначально ориентированных на использование МВС является чрезвычайно актуальной проблемой. При этом надо учитывать, что вместе с возможностями, которые предоставляет программистам многопроцессорная вычислительная техника, существует специфические требования к используемым алгоритмам [1]:
• обеспечение равномерного распределения вычислительной нагрузки по процессорам;
• ускорение расчетов при увеличении числа процессоров;
• необходимость синхронизации при остановке (завершении) итераций;
• снижение затрат времени на синхронизацию;
• периодический сбор данных для записи и анализа;
• обмен данными между процессорами для продолжения расчета;
• снижение объема передаваемой информации при обмене;
• снижение числа актов приема-передачи (то есть числа обменов между процессорами);
• уменьшение влияния размера задачи на ускорение;
• обеспечение масштабируемости и переносимости программы.
Выполнение всех этих требований, связанных с применением распределенных вычислений к начально-краевой задачи для уравнения неразрывности является основной целью данной работы.
Уравнение неразрывности входит в состав многих математических моделей сплошной среды (различных моделей движения газовой и гидродинамики), теории волн, электродинамики и даже квантовой механики (в двух последних, обычно используется термин «уравнение непрерывности»).
В то же время при численном интегрировании уравнения неразрывности возникает необходимое для большинства современных методов [2] - [5] условие Куранта-Фридрихса-Леви на шаг по времени, что приводит к проблемам нахождения решения при больших скоростях.
В работе [6] рассмотрен полулагранжевый метод, основанный на точном тождестве пространственных интегралов, области интегрирования которых лежат на соседних слоях по времени. Этот метод приводит к консервативной разностной схема, дающей сходимость численного решения к точному с порядком O 0Т^.
В качестве основной цели исследования выступает разработка и анализ производительности нескольких версия параллельных алгоритмов реализации полулагранжевого метода для уравнения неразрывности с помощью технологий OpenMP и MPI. Для достижения поставленной цели сформулированы следующие задачи исследования:
• разработка параллельных вычислительных алгоритмов решения начально¬краевой задачи для уравнения неразрывности;
• адаптация разработанного алгоритма к многопроцессорным вычислительным системам, которая складывается из выбора методов реализации алгоритма на параллельных ЭВМ, выявления трудно распараллеливаемых блоков, их оптимизации и верификации;
• проведении вычислительных экспериментов на серии тестовых задач для верификации разработанного вычислительного алгоритма;
• оценка производительности разработанных алгоритмов.
для уравнения неразрывности.
В качестве метода исследований используется вычислительный эксперимент, включающий в себя следующие этапы [7]:
• математическая формулировка задачи,
• построение приближенного (численного) метода решения задачи, написание вычислительного алгоритма;
• программирование на ЭВМ вычислительного алгоритма,
• проведение расчетов на ЭВМ,
• анализ полученных численных результатов и уточнение математической модели.
Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы и приложений.
Во введении обосновывается актуальность темы исследования, кратко излагается содержание диссертации, указывается ее научная новизна, и формируются основные результаты работы. В первой главе привидится краткий обзор численных методов решения начально-краевых задач для уравнения неразрывности и излагается обзор основных тенденций в области параллельного программирования. Во второй главе приводится математическая постановка задачи, описание полулагранжевого метода. В третьей главе описаны параллельные вычислительные алгоритмы реализации полулагранжевого метода для вычислительных систем с общей памятью, с распределенной памятью и для гибридных вычислительных систем. В четвертой главе представлены результаты вычислительных экспериментов на тестовых задачах. В пятой главе осуществляется анализ производительности разработанных параллельных алгоритмов.
Основные результаты работы были представлены на следующих научных конференциях:
1. Международная конференция "IX Сибирский конгресс женщин-математиков 17-20 мая 2016 г, г. Красноярск;
2. XVII Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям, 30 октября - 3 ноября 2016 г, г. Новосибирск;
3. XX юбилейная Международная научно-практическая конференция, по-священная памяти генерального конструктора ракетно-космических си¬стем академика Михаила Федоровича Решетнева "Решетневские чтения 9-12 ноября 2016 г., г. Красноярск
Результаты магистерской диссертации опубликованы в работах [34] - [37]. Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований, Правительства Красноярского края, Красноярского краевого фонда поддержки научной и научно-технической деятельности» в рамках научного проекта № 16-41-243029.
Применение прямых методов численного анализа требует большого объема вычислительных ресурсов. Однопроцессорный компьютер зачастую не может обеспечить требуемый объем оперативной памяти для работы с многомиллионными ячейками расчетных сеток, использование которых необходимо для достижения требуемой точности. Эффективным средством решения ресурсоемких задач является технология параллельных вычислений на распределенных системах кластерного типа. На пути перехода от персонального компьютера к суперкомпьютеру с параллельной архитектурой имеются определенные трудности, которые, во-первых, связаны с необходимостью распараллеливания вычислительного алгоритма, во-вторых, с принципиально более сложным написанием программного кода и недостаточно развитой системой отладки программ на кластере. При этом одним из факторов эффективного использования высокопроизводительной многопроцессорной вы-числительной техники является применение специальных методов математического моделирования. В связи с этим, одной из задач современной науки является развитие технологии математического моделирования, рассматривающей многопроцессорные вычислительные системы (МВС) как основной аппарат для вычислений.
Отметим далее, что за время существования МВС накоплен значительный опыт их использования, и они находятся в массовом доступе. Однако, огромные вычислительные возможности, предоставляемые этими системами, используются недостаточно. Причиной этому является сложность адаптации последовательных алгоритмов и программ к параллельным архитектурам. Поэтому разработка эффективных параллельных алгоритмов решения фундаментальных и прикладных задач, изначально ориентированных на использование МВС является чрезвычайно актуальной проблемой. При этом надо учитывать, что вместе с возможностями, которые предоставляет программистам многопроцессорная вычислительная техника, существует специфические требования к используемым алгоритмам [1]:
• обеспечение равномерного распределения вычислительной нагрузки по процессорам;
• ускорение расчетов при увеличении числа процессоров;
• необходимость синхронизации при остановке (завершении) итераций;
• снижение затрат времени на синхронизацию;
• периодический сбор данных для записи и анализа;
• обмен данными между процессорами для продолжения расчета;
• снижение объема передаваемой информации при обмене;
• снижение числа актов приема-передачи (то есть числа обменов между процессорами);
• уменьшение влияния размера задачи на ускорение;
• обеспечение масштабируемости и переносимости программы.
Выполнение всех этих требований, связанных с применением распределенных вычислений к начально-краевой задачи для уравнения неразрывности является основной целью данной работы.
Уравнение неразрывности входит в состав многих математических моделей сплошной среды (различных моделей движения газовой и гидродинамики), теории волн, электродинамики и даже квантовой механики (в двух последних, обычно используется термин «уравнение непрерывности»).
В то же время при численном интегрировании уравнения неразрывности возникает необходимое для большинства современных методов [2] - [5] условие Куранта-Фридрихса-Леви на шаг по времени, что приводит к проблемам нахождения решения при больших скоростях.
В работе [6] рассмотрен полулагранжевый метод, основанный на точном тождестве пространственных интегралов, области интегрирования которых лежат на соседних слоях по времени. Этот метод приводит к консервативной разностной схема, дающей сходимость численного решения к точному с порядком O 0Т^.
В качестве основной цели исследования выступает разработка и анализ производительности нескольких версия параллельных алгоритмов реализации полулагранжевого метода для уравнения неразрывности с помощью технологий OpenMP и MPI. Для достижения поставленной цели сформулированы следующие задачи исследования:
• разработка параллельных вычислительных алгоритмов решения начально¬краевой задачи для уравнения неразрывности;
• адаптация разработанного алгоритма к многопроцессорным вычислительным системам, которая складывается из выбора методов реализации алгоритма на параллельных ЭВМ, выявления трудно распараллеливаемых блоков, их оптимизации и верификации;
• проведении вычислительных экспериментов на серии тестовых задач для верификации разработанного вычислительного алгоритма;
• оценка производительности разработанных алгоритмов.
для уравнения неразрывности.
В качестве метода исследований используется вычислительный эксперимент, включающий в себя следующие этапы [7]:
• математическая формулировка задачи,
• построение приближенного (численного) метода решения задачи, написание вычислительного алгоритма;
• программирование на ЭВМ вычислительного алгоритма,
• проведение расчетов на ЭВМ,
• анализ полученных численных результатов и уточнение математической модели.
Диссертация состоит из введения, пяти глав, заключения, списка используемой литературы и приложений.
Во введении обосновывается актуальность темы исследования, кратко излагается содержание диссертации, указывается ее научная новизна, и формируются основные результаты работы. В первой главе привидится краткий обзор численных методов решения начально-краевых задач для уравнения неразрывности и излагается обзор основных тенденций в области параллельного программирования. Во второй главе приводится математическая постановка задачи, описание полулагранжевого метода. В третьей главе описаны параллельные вычислительные алгоритмы реализации полулагранжевого метода для вычислительных систем с общей памятью, с распределенной памятью и для гибридных вычислительных систем. В четвертой главе представлены результаты вычислительных экспериментов на тестовых задачах. В пятой главе осуществляется анализ производительности разработанных параллельных алгоритмов.
Основные результаты работы были представлены на следующих научных конференциях:
1. Международная конференция "IX Сибирский конгресс женщин-математиков 17-20 мая 2016 г, г. Красноярск;
2. XVII Всероссийская конференция молодых учёных по математическому моделированию и информационным технологиям, 30 октября - 3 ноября 2016 г, г. Новосибирск;
3. XX юбилейная Международная научно-практическая конференция, по-священная памяти генерального конструктора ракетно-космических си¬стем академика Михаила Федоровича Решетнева "Решетневские чтения 9-12 ноября 2016 г., г. Красноярск
Результаты магистерской диссертации опубликованы в работах [34] - [37]. Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований, Правительства Красноярского края, Красноярского краевого фонда поддержки научной и научно-технической деятельности» в рамках научного проекта № 16-41-243029.
В магистерской диссертации получены следующие результаты.
1. Разработан параллельный вычислительный алгоритм решения начально-краевой задачи для уравнения неразрывности;
2. Разработанный алгоритм адаптирован к многопроцессорным вычислительным системам.
3. Проведены вычислительные эксперименты на серии тестовых задач для верификации разработанного вычислительного алгоритма.
4. Оценена производительность разработанных алгоритмов.
В магистерской диссертации для двумерного уравнения неразрывности описан численный метод, основанный на точном тождестве двух пространственных интегралов на соседних слоях по времени. Представленный подход имеет первый порядок сходимости для гладких решений, что полностью подтверждается вычислительными экспериментами.
Также в ходе работы, было разработано три параллельных алгоритма.
1. Для вычислительных систем с общей памятью с использованием технологии OpenMP.
2. Для вычислительных систем с распределенной памятью с использованием технологии MPI.
3. Для гибридных вычислительных систем с использованием объединения технологий MPI и OpenMP.
Данные алгоритмы были реализованы в виде прикладных программ на языке C++. Проведенные исследования производительности параллельных про¬грамм позволяют сделать следующие выводы.
1. Параллельная программа, использующая технологию OpenMP, обладает высокой производительностью (эффективность распараллеливания приближается к 100%). Ускорение вычислений в этом случае равно количеству ядер процессора(прииспользовании8ядервычисленияускоряются в 8 раз). Однако такая программа может применяться только для систем с общей памятью, в том числе на персональных ЭВМ с многоядерными процессорами (например, дву- или четырех ядерные процессоры).
2. Параллельная программа, использующая технологию MPI, обладает так¬же высокой производительностью. Данная программа может быть использована на многопроцессорных вычислительных системах.
3. Гибридная параллельная программа, использующая объединение технологий MPI и OpenMP, обладает меньшей производительностью, чем параллельная программа, использующая только технологию MPI. Данные вид программы может быть использован только на вычислительных системах гибридного типа, в которых применяются многоядерные процессоры.
Полученные результаты имеют практическое значение и могут быть использованы при построении эффективных параллельных алгоритмов.
1. Разработан параллельный вычислительный алгоритм решения начально-краевой задачи для уравнения неразрывности;
2. Разработанный алгоритм адаптирован к многопроцессорным вычислительным системам.
3. Проведены вычислительные эксперименты на серии тестовых задач для верификации разработанного вычислительного алгоритма.
4. Оценена производительность разработанных алгоритмов.
В магистерской диссертации для двумерного уравнения неразрывности описан численный метод, основанный на точном тождестве двух пространственных интегралов на соседних слоях по времени. Представленный подход имеет первый порядок сходимости для гладких решений, что полностью подтверждается вычислительными экспериментами.
Также в ходе работы, было разработано три параллельных алгоритма.
1. Для вычислительных систем с общей памятью с использованием технологии OpenMP.
2. Для вычислительных систем с распределенной памятью с использованием технологии MPI.
3. Для гибридных вычислительных систем с использованием объединения технологий MPI и OpenMP.
Данные алгоритмы были реализованы в виде прикладных программ на языке C++. Проведенные исследования производительности параллельных про¬грамм позволяют сделать следующие выводы.
1. Параллельная программа, использующая технологию OpenMP, обладает высокой производительностью (эффективность распараллеливания приближается к 100%). Ускорение вычислений в этом случае равно количеству ядер процессора(прииспользовании8ядервычисленияускоряются в 8 раз). Однако такая программа может применяться только для систем с общей памятью, в том числе на персональных ЭВМ с многоядерными процессорами (например, дву- или четырех ядерные процессоры).
2. Параллельная программа, использующая технологию MPI, обладает так¬же высокой производительностью. Данная программа может быть использована на многопроцессорных вычислительных системах.
3. Гибридная параллельная программа, использующая объединение технологий MPI и OpenMP, обладает меньшей производительностью, чем параллельная программа, использующая только технологию MPI. Данные вид программы может быть использован только на вычислительных системах гибридного типа, в которых применяются многоядерные процессоры.
Полученные результаты имеют практическое значение и могут быть использованы при построении эффективных параллельных алгоритмов.