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

Текст из файла (страница 2)

На Рис. 1.1 изображено исходное возмущение. Карту цветов можно рассматривать таким образом, что синий – то место, где возмущения нет, красный – то место, где возмущение наибольшее.

Рис. 3.2

На Рис. 1.2 изображено перемещение возмущения через 20 шагов. Из рисунка видно, что возмущение размывается.

Рис. 3.3

На Рис. 1.3 показано возмущение через 80 шагов. Как видно из рисунка, возмущение уже очень сильно размыто.

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

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

Рассмотрим теперь схему более высокого порядка аппроксимации.

Если рассматривать уравнение:

(13)

То решение на следующей итерации по времени можно разложить в ряд Тейлора:

(14)

И так как:

(15)

Дифференцируя, получим утверждение:

(16)

Поэтому, мы можем перейти от разложения в ряд Тейлора по времени, к разложению по производным координат:

(17)

Теперь от общих рассуждений, можно перейти к получению схемы Бима-Уорминга[3]. Т.к. в нашем случае собственные числа матрицы A положительные, то можно представить производные по координате как:

(18)

(19)

Далее, подставляя это в разложения, и заменяя переменные, получаем схему Бима-Уорминга:

(20)

Эта схема 2-го порядка точности. При этом данная схема хорошо работает на “гладких” возмущениях, но на более резких возмущениях возникают осцилляции, из-за добавленного для точности квадратичного члена.

Наибольшую точность схема Бима-Уорминга дает, когда число куранта, или , близко к 1.

Шаблон схемы имеет вид:

Рис. 3.4

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

c	0.3
τ	0.1
h	1

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

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

Как и в предыдущем расчете, начальное возмущение такое же, поэтому его приводить не будем. Рассмотрим результаты, которые были получены с помощью новой схемы.

Рис. 3.5

На Рис. 1.4 показано возмущение через 20 шагов. Как видно из рисунка, возмущение размыто гораздо меньше, чем в предыдущем случае, но появились некоторые осцилляции, которые не наблюдаются на практике.

Рис. 3.6

На Рис. 1.5 показано возмущение, через 60 шагов.

Рис. 3.7

На Рис. 1.6 показано возмущение через 80 шагов. Как видно все же возмущение размывается, и осцилляции не исчезают.

Итак, можно сделать вывод, что данная схема обладает меньшей численной вязкостью и не так сильно размывает решение со временем, однако на графиках хорошо заметны нефизичные осцилляции. Это связано с немонотонностью выбранной схемы. Для борьбы с осцилляциями такого рода используются различные подходы по монотонизации и гибридизации схем. Далее рассмотрим один из них.

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

Для уменьшения осцилляций и удаления осцилляций, которые не связаны с физикой задачи мы будем использовать схемы TVD(Total variation diminishing) второго порядка точности. Чтобы определить меру вариации, используется полная вариация системы. Полная вариация системы определяется так[3]:

(21)

И схема будет являться TVD, если

(22)

Т.е. полная вариация системы будет уменьшаться на новом шаге.

Описание схемы:

(23)

здесь и - антидиффузионые потоки:

(24)

(25)

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

(26)

Описание лимитера sweby[3]:

(27)

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

c	0.3
τ	0.1
h	1

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

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

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

Рассмотрим результаты работы алгоритма с выбранной схемой:

Рис. 3.8

На Рис. 1.7 показано возмущение через 10 шагов работы программы.

Рис. 3.9

На Рис. 1.8 показан результат работы программы через 50 шагов.

Рис. 3.10

На Рис. 1.9 изображено возмущение через 80 шагов.

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

Но для начала исследуем последовательный алгоритм. Для того чтобы можно было сравнивать распараллеленный алгоритм. Основным критерием работы параллельной программы является ускорение по сравнению с последовательной, поэтому проведем тестирование последовательной программы путем замера времен работы алгоритма при различных параметрах, чтобы иметь отправную точку для сравнения с параллельной версией программы.

Для этого был проведен анализ зависимости времени работы, из расчета на 1 узел сетки, от размера сетки, ожидается, что это будет прямая, параллельная оси абсцисс. Расчет производился на Ubuntu 12.04, компилятор g++ -O3, процессор Intel Core i5 2.3GHz.

График 1.1

На График 1.1 по оси абсцисс отложен характерный размер 2-мерной сетки (т.е. сторона квадрата). По оси ординат отложено время, которое тратит алгоритм на обработку 1 узла сетки. Как видно, с некоторой погрешностью, это можно считать прямой. Это один из признаков, что алгоритм может быть применен для сравнения времен.

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

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

Для того чтобы было легко понимать дальнейшее изложение, введем некоторые понятия.

Введем такое понятие, как графическое устройство или карточка (device). Это понятие важно тем, что внутри этого устройство мы не можем влиять на выделение ресурсов для расчетов. Мы можем только лишь сказать, что делать каждому потоку. Но мы не можем управлять созданием этих потоков, за нас это делает GPU. Потоки в GPU гораздо более легкие, чем в CPU. Поэтому в таких системах количество потоков может быть очень большим.

В технологии CUDA есть такое понятие как хост (host). Этим понятием мы будем обозначать устройство, на котором выполняется последовательный код (например, обычный компьютер). Т.е. обмен данных между хостом и карточкой (between host and device), это будет обозначать перенос данных из общей памяти GPU на память, связанную с CPU (это может быть как оперативная, так и память на жестком диске, если оперативной не хватает).

Существует 6 типов памяти:

1. Регистровая память (register) самая быстрая из всех возможных. Делится поровну между всеми нитями. Здесь содержатся все локальные переменные ядра и промежуточные значения вычислений.

2. Разделяемая память (shared memory) – очень быстрая. Ее размер 40-64Кб на блок. Такая память доступна для всех потоков в данном блоке. Чтение и запись явно управляются программистом.

3. Локальная память (local memory) если регистровая память заканчивается, начинает использоваться более медленная. Эта память ограничена только общей памятью GPU.

4. Константная память (constant memory) достаточно быстрая, но небольшая по объему. Из ядра данные могут только считываться из константной памяти.

5. Глобальная память (global memory) – самая медленная память. С нее копируются данные с хоста и из нее копируются назад.

6. Текстуарная память (texture memory) – является не отдельным видом память и механизмом обращения к глобальной. Используется в основном для обработки графики.

Кроме того, надо понимать, что все потоки или threads, объединены в блоки или blocks. Сколько конкретно потоков будет в одном блоке, и сколько блоков надо использовать, настраивать можно. Потому что нет смысла выделять слишком большое количество ресурсов, просто для того, чтобы они простаивали.

Рис. 4.1 Схематическое описание внутренней структуры графического устройства.

Для более подробного понимания системы, можно обратиться к источникам [5],[6].

Хочется еще вкратце описать процесс работы программы на GPU. Для этого нам нужно обсудить какая память бывает здесь, и какая скорость считывания этой памяти, что напрямую влияет на скорость работы программы.

На самом деле, для начала нам понадобиться 2 вида памяти:

1. Память, которая находится на устройстве, и общая для всех блоков (до 4GB, на современных GPU). Здесь надо сказать, что скорость обмена с этой памятью внутри GPU ~80Gb/s. Скорость копирования из/на эту память, например из оперативной памяти, не превышает 4Gb/s. Последнее ограничение связано с шиной PCI-Express.

2. И память, которая относится к каждому блоку потоков, и доступна, только для потоков текущего блока, зато она еще быстрее. Она носит название разделяемой или shared memory.

Итак, алгоритм работы, это скопировать на общую память данные с помощью CPU, далее провести расчеты на GPU, и скопировать результат обратно. Важно, что обычно узкое место, это как раз копирование данных из CPU в GPU и обратно. Это мы будем стараться избегать, что, как мы увидим позже, создаст другие проблемы.

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

Постановка задачи такая же, как в главе 1.4, просто теперь уже работающая с помощью технологии CUDA. Здесь, и далее, надо сказать что программа для GPU вычислялась на nVidia Tesla s2050. Результаты сравнивались с временем работы программы на CPU, которое находится на локальной машине, а именно 2.3 GHz Intel core i5 и на CPU на сервере: Intel(R) Xeon(R) CPU X5670 2.93GHz.

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

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