Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Министерство образования и науки Российской Федерации МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (государственный университет) ФАКУЛЬТЕТ ОБЩЕЙ И ПРИКЛАДНОЙ МАТЕМАТИКИ КАФЕДРА ИНФОРМАТИКИ (Специализация 011600 «Прикладные физика и математика»)

Разработка алгоритмов решения систем гиперболических уравнений на графических процессорах.

Выпускная квалификационная работа

студента 973а группы

Дашкевича Антона Дмитриевича

Научный руководитель:

доктор физико-математических наук,

член-корреспондент РАН

Петров И.Б.

Оглавление

1 Введение 2

2 Обзор технологий 3

3 Постановка задачи. 4

3.1 Реализация простейшей схемы. 4

3.2 Реализация улучшенной схемы 8

3.3 Схема TVD2 c лимитером Sweby. 11

4 Распараллеливание последовательного алгоритма решения уравнения переноса с помощью технологии CUDA. 14

4.1 Краткое описание технологии CUDA. 14

4.2 Двумерное уравнение переноса (схема без осцилляций). Реализация на CUDA. 17

5 Уравнение упругости 19

5.1 Постановка задачи 19

5.2 Описание схемы и ограничителя, который используется в расчетах. 20

5.3 Распараллеливание решения 2-х мерной задачи упругости с помощью технологии CUDA. 20

5.4 Распараллеливание решения 2-х мерной задачи упругости с помощью технологии CUDA и использования разделяемой(shared) памяти. 28

5.5 Распараллеливание решения 2-х мерной задачи упругости с помощью технологии CUDA на нескольких GPU 32

5.6 Оптимизация 36

6 Моделирование влияния головной ударной волны Челябинского метеорита на поверхность Земли 36

6.1 Введение 36

6.2 Начальные данные 37

6.3 Постановка задачи 38

6.4 Результаты 40

7 Выводы 44

8 Планы 45

9 Литература 45

1. Введение

Системы уравнений гиперболического типа имеют большое значение при математическом описании моделей для численного решения прикладных физических задач. В том числе, они используются для моделирования некоторых задач распространения динамических волновых возмущений в гетерогенных средах. К таким задачам относятся задачи сейсмостойкости зданий, задачи разведки углеводородов и другие задачи сейсмики [1]. Они имеют важное практическое значение на этапе проектирования и выбора площадок для постройки зданий, мостов, плотин, атомных электростанций, других стратегических объектов и сложных наземных сооружений, а также при разведке и оценке запасов месторождений углеводородов. Решение задач такого типа связано с большими вычислительными затратами. Например, для моделирования некоторых задач распространения волновых возмущений, физические размеры области интегрирования, в такого рода задачах, могут достигать десятков и сотен километров. Для корректного моделирования распространения волновых возмущения в таких областях с учетом всех неоднородностей, размеры которых могут достигать десятков метров и менее, требуют использования численных методов повышенного порядка точности и больших вычислительных сеток. Это влечет за собой увеличение требований к вычислительным ресурсам и возникает задача в использовании параллельных вычислений для обеспечения приемлемого времени расчета.

Одно из перспективных направлений, для уменьшения времени расчетов, является GPU.

В данной работе решаются гиперболические уравнения. Рассмотрено несколько схем, и рассмотрены их преимущества и недостатки. Задача сразу написана для работы на CPU, протестирована, и только потом перенесена для работы на графических процессорах. Рассматривается применение технологии CUDA для моделирования таких задач на графических процессорах.

Мы будем рассматривать 2 задачи:

1. Двумерное уравнение переноса

2. Двумерное уравнение упругости

1. Обзор технологий

На данный момент существуют различные технологии для работы на графических карточках. Основными поставщиками графических устройств являются NVidia и AMD. Каждый предлагает свое решение для разработки приложений на их устройствах. В случае NVidia эта технология называется CUDA. AMD предлагает технологию Stream. Анализ работы различных алгоритмов показывает, что нет критической разницы в производительности при использовании данных технологий. Кроме того, количество документации по CUDA значительно больше, чем по аналогичной технологии от AMD.

Кроме того, для работы в кластерной среде необходимо совместное использование технологий, для работы на графических устройствах с технологией MPI. Обе технологии: CUDA и Stream, можно интегрировать для использования совместно с MPI. Но, для технологии CUDA это сделать гораздо проще, чем для Stream.

Рассмотрим технологию OpenCL, которая изначально создавалась как стандарт не только для работы с GPGPU устройствами, но и для исполнения программ на кластерной среде, с различными подключенными устройствами: NVidia GPU, AMD GPU, SpursEngine (Cell) (IBM, SONY, TOSHIBA), Cpu x86, x64 processors и т.д. Но, на данный момент этот стандарт поддерживается только для NVidia GPU, AMD GPU, AMD CPU,Intel CPU. Под поддержкой имеется ввиду наличие компиляторов, драйверов для работы с устройствами.

Язык, который используется в OpenCL, схож с языком, используемым в CUDA. Поэтому переход к стандарту разработки приложений под GPGPU осуществляется легко, если разрабатывать с помощью CUDA. Характеристики, приведенные в [9], говорят, что на данный момент, использование OpenCL на устройствах от NVidia, уступают в производительности программам, использующим технологию CUDA на 13-65%. Хотя, сейчас NVidia активно совершенствует производительность при работе с OpenCL.

Так же для работы с графическими устройствами на данный момент существует технология Direct Compute, опубликованная Microsoft в составе Direct X11, в которой были добавлены, так называемые, шейдеры общего назначения. Хотя технология не кроссплатформенна, все же достаточно актуально, ведь на данный момент большая часть пользователей на данный момент используют Windows. Технология Direct Compute в основном нацелена на решение задач общего назначения, но все же она может быть использована, для работы с графикой, например: рендеринг теней и т.п.

Технология Direct Compute поддерживается основными производителями GPU устройств: NVidia и AMD. На данный момент в этом секторе лидирует AMD, которая, на данный момент лучше интегрирована с Direct Compute и работает “поверх” данной технологии.

В Direct X11 сделана поддержка чисел с двойной точностью. Сравнительный анализ скорости работы данной технологии по сравнению с CUDA и OpenCL пока проведен достаточно слабо.

По состоянию на 13 июня 2013 года, 14 суперкомпьютеров из первых 100 имеют гибридную архитектуру. Среди них суперкомпьютер Titan, который занимает 2-ую строчку в рейтинге. Это говорит о росте популярности проведения расчетов на GPU.

В текущей работе не будет реализовываться алгоритм на OpenCL , на CPU.

По причинам, изложенным выше, для решения поставленной задачи была выбрана технология CUDA.

1. Постановка задачи.

Уравнение переноса – уравнение в частных производных, описывающее перенос сохраняющейся скалярной величины в пространстве. Уравнение переноса имеет вид:

(1)

Уравнение выше имеет характеристику, определяемую уравнением характеристики:

(2)

При этом вдоль характеристики, уравнение превращается в обыкновенное дифференциальное:

(3)

В случае, когда правая часть обнуляется:

(4)

Для одномерного случая оно имеет вид:

(5)

Уравнение переноса – это простой случай гиперболической системы уравнений. При постоянном u, уравнение переноса имеет аналитическое решение:

(6)

где -гладкая, дифференцируемая функция.

В нашем случае решается двумерное уравнение:

(7)

1. Реализация простейшей схемы.

Для моделирования данной задачи в начале, был реализован последовательный алгоритм, который считал на CPU. Последовательный алгоритм необходим для 2-х основных целей:

1. Сравнение расчетов, полученных с помощью CPU и с помощью GPU.

2. Измерение ускорения.

Для постпроцессинга и просмотров результатов расчета используется программа Paraview[2], которая позволяет визуализировать расчет и как результат, легко анализировать полученную информацию.

Для численного решения данной задачи, можно воспользоваться схемой:

(8)

Но она не стабильна, если вместо , взять среднее значение на интервале, т.е. , то мы получим стабильную схему. Схема Лакса[3]:

(9)

Схема имеет первый порядок точности. При этом обладает свойством монотонности: при переходе от n к n+1 она сохраняет монотонный порядок решения.

Для изучения стабильности схемы можно воспользоваться анализом Ньюмана[4]:

(10)

Тогда, при условии: , можно сказать, что схема является безусловно устойчивой, т.е. .

Для моделирования 2-мерной задачи, можно воспользоваться последовательным применением 1-мерной схемы сразу по оси x, т.е. по строчкам, а потом по y, т.е. по столбцам. Это надо делать на каждом шаге по времени.

(11)

(12)

Где - значение функции в точке , при проходе по строкам, аналогично для прохода по столбцам. В данном случаем, при проходе по строкам, остальные строки не имеют значения, аналогично для прохода по столбцам. В результате 2-х проходов, мы перейдем на новый шаг по времени.

Константы в схеме были взяты следующими:

c	0.3
τ	0.1
h	1

Характеристики сетки и количество шагов:

Количество шагов	100
Размер сетки	100x100

Сетка немного специфичная, т.е. для того, чтобы протестировать саму схему, на предмет ее применимости и адекватности физическим явлениям, желательно было выбрать небольшую сетку, на которой, все же, можно было увидеть результат, даже через большое число шагов. На границах сетки выставлены периодические граничные условия. Т.е. правая граница копируется на левую, аналогично с верхней на нижнюю. Аналогично, если бы изначально движения возмущения было бы направлено в обратную сторону.

Изначально скорости переноса в уравнении выбраны таким образом, что вектор направления движения возмущения направлен под , т.е. мы должны видеть что квадрат (начальное возмущение) перемещается по диагонали вверх, вправо.

Вот результаты, которые получились при использовании такой, простейшей схемы:

Рис. 3.1

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов ВКР