Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев презентация

Содержание

1. Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев
2. Цель: выбрать оптимальные способы распараллеливания метода
3. Примеры функций ядра: Рис 1. График функции ядра Аппроксимация интегральным представлением
4. Аппроксимация частицами
5. Дифференциальные уравнения движения вязкой, несжимаемой жидкости
6. Моделирование содержимого трюма нефтеналивного танкера Танкер перевозит
7. Подходы распараллеливания на системы с распределённой памятью
8. Ортогональное рекуррентное деление пополам Рис. 2. Положение
9. Кривая делящая пространство Рис. 3. Peano-Hilbert кривая.
10. Пример применения методов ORB и SFC* Рис.
11. Подходы распараллеливания на системы с распределённой памятью
12. Частицы, пересылаемые между вычислительными узлами подобласть А
13. Минимизация количества пересылок а) б) Рис. 7.
14. Минимизация количества пересылок а) б) Рис. 8.
15. Подходы распараллеливания на системы с общей памятью
16. Метод моделирования сетки для алгоритма поиска соседей
17. Пример сортировки частиц по индексу массив ячеек
18. Пространственное хэширование Будем использовать след. ф-ю хэширования:
19. Пространственное хэширование x y z
20. Оптимизация пространственного хэширования x y
21. Сравнение различных подходов Рис. 16. Пример результатов
22. Обзор литературы Biddiscombe J. Efficient parallelization strategy

Цель: выбрать оптимальные способы распараллеливания метода SPH для систем с общей и распределённой памятью. Задачи: провести обзор литературы по подходам к распараллеливанию метода SPH; реализовать распараллеливание метода SPH на

Главная
Образование
Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев

Слайд 1МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
КЕМЕРОВСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Математический факультет
Кафедра ЮНЕСКО по новым информационным технологиям

план работы

Распараллеливание метода SPH

аспиранта
Кузнецова Арсения Владимировича

Научный руководитель:
доктор физ.-мат. наук
К.Е. Афанасьев

Слайд 2
Цель: выбрать оптимальные способы распараллеливания метода SPH для систем с общей

и распределённой памятью.

Задачи:
провести обзор литературы по подходам к распараллеливанию метода SPH;
реализовать распараллеливание метода SPH на системы с общей памятью;
реализовать распараллеливание метода SPH на системы с распределённой памятью.

Слайд 3

Примеры функций ядра:
Рис 1. График функции ядра
Аппроксимация интегральным представлением

Слайд 4Аппроксимация частицами

Слайд 5Дифференциальные уравнения движения вязкой, несжимаемой жидкости

Слайд 6Моделирование содержимого трюма нефтеналивного танкера
Танкер перевозит 80 тыс. тонн нефти. В

дипломной работе удалось провести моделирование с использованием 65 тыс. частиц SPH. При такой массе моделируемой жидкости и количестве частиц, масса частицы составит 1,23 тонны.

Рис. 1. Танкер «MINERVA ASTRA», грузоподъёмностью 81 тыс.т. нефти.

Слайд 7Подходы распараллеливания на системы с распределённой памятью
Равномерное распределение нагрузки между узлами

кластера
Ортогональное рекуррентное деление пополам (ORB)
Кривая, заполняющая пространство (кривые Пеано) (SFC)

Слайд 8Ортогональное рекуррентное деление пополам
Рис. 2. Положение границ разделяющих подобласти и распределение

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

а)

б)

Слайд 9Кривая делящая пространство
Рис. 3. Peano-Hilbert кривая.
Рис. 4. Пример декомпозиции области решения,

на пять вычислительных узлов.

Слайд 10Пример применения методов ORB и SFC*
Рис. 5. Пример применения методов ORB(а)

и SFC(б), цветовая гамма соответствует распределению по вычислительным узлам.

а)

б)

*Пример был опубликован в работе:
Wagner S., Streinmetz M., Bode A., Brehm M. High performance computing in science and engineering. B.: Springer-Verlag. 2007. P. 715.

Слайд 11Подходы распараллеливания на системы с распределённой памятью
Минимизация объема данных пересылаемых между

узлами кластера
Минимизация кол-ва частиц находящихся в областях удовлетворяющих условию (где точка принадлежащая границе между подобластями).

Слайд 12Частицы, пересылаемые между вычислительными узлами
подобласть А
подобласть А
подобласть Б
подобласть Б
частицы находящиеся в

около граничной области

пересылка данных о частицах на соседний вычислительный узел

Рис. 6. Определение частиц, требующих пересылки данных

Слайд 13Минимизация количества пересылок
а)
б)
Рис. 7. Пример сокращения частиц требующих пересылки данных, для

ORB метода декомпозиции пространства. Необходимо передать 18 частиц (а), или 11 частиц (б). Красная линия – граница подобластей.

Слайд 14Минимизация количества пересылок
а)
б)
Рис. 8. Пример сокращения частиц требующих пересылки данных, для

ORB метода декомпозиции пространства. Необходимо передать 14 частиц (а), или 7 частиц (б). Красная линия – граница подобластей.

Слайд 15Подходы распараллеливания на системы с общей памятью
Минимизация пересылок данных между оперативной

памятью и кэшем CPU
Группировка пространственно близко расположенных частиц в памяти
Работа с ссылками на объекты, а не с самими объектами
Группировка в структуры только данных, использующихся совместно
Параллельная обработка подзадач
Параллельное создание сетки для алгоритма поиска соседей
Параллельное выполнение поиска соседей
Параллельный расчёт сил, скорости, позиции

Слайд 16Метод моделирования сетки для алгоритма поиска соседей
Равномерная сетка (массив списков ссылок

на частицы)
последовательная генерация сетки
пространственно близкие частицы не сгруппированы в памяти
Сортировка частиц по индексу
Для каждой частицы рассчитываем индекс ячейки
соответствующий её координатам

где , - кол-во ячеек по оси Ox и Oy соответственно.
По данному индексу отсортируем массив частиц.

Слайд 17Пример сортировки частиц по индексу
массив ячеек сетки
таблица соответствия
массив частиц
Рис. 11. Организация

хранения данных о частицах

Таблица соответствия сортируется в соответствии с SFC на каждом временном шаге.
Массив частиц сортируется в соответствии с SFC на каждом сотом шаге по вр.
Используется либо параллельная сортировка, либо сортировка вставкой.
В качестве SFC можно выбрать, например, Morthon кривую.

Рис. 12. Иллюстрация упорядоченности частиц в оперативной памяти.

а)

б)

Слайд 18Пространственное хэширование
Будем использовать след. ф-ю хэширования:

где

- простые, большие числа, - размер хэш таблицы.

хэш таблица

массив частиц

Рис. 13. Модель организации данных для пространственного хэширования.

Слайд 19Пространственное хэширование

x
y
z
хэш таблица
массив частиц
Рис. 14. Модель организации данных для пространственного хэширования.

С обработкой коллизий.

резервный массив

Слайд 20Оптимизация пространственного хэширования

x
y
z
хэш таблица
массив частиц
Рис. 15. Модель организации данных для пространственного

хэширования.

резервный массив

таблица используемых частиц

таблица
частиц

размер m

размер l

размер n

размер l

m – фиксированный пользователем размер
хеш-таблицы,
l – кол-во заполненных ячеек,
n – кол-во частиц.

Слайд 21Сравнение различных подходов
Рис. 16. Пример результатов замеров времени для различных алгоритмов

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

Слайд 22Обзор литературы
Biddiscombe J. Efficient parallelization strategy for the SPH method. B.:

Future and Emerging Technologies FP7-ICT European project, 2010. 46 p.

Springel V. The cosmological simulation code GADGET-2. B.: Mon. Not. R. Astron. Soc. №364. 2005, P. 1105–1134.

Fleissner F., Eberhard P. Load Balanced Parallel Simulation of Particle-Fluid DEM-SPH Systems with Moving Boundaries B.: Advances in Parallel Computing. №15. 2008, P. 37-44

Ihmsen M., Akinci N., Becker M., Teschner M. A parallel SPH implementation on multi-core CPUs B.: Computer Graphics Forum. №30. 2011, P. 99-112

Скачать презентацию

Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев презентация

Содержание

Слайд 1МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
КЕМЕРОВСКИЙ

Слайд 2
Цель: выбрать оптимальные способы распараллеливания метода SPH для систем с общей

Слайд 3

Примеры функций ядра:
Рис 1. График функции ядра
Аппроксимация интегральным представлением

Слайд 4Аппроксимация частицами

Слайд 5Дифференциальные уравнения движения вязкой, несжимаемой жидкости

Слайд 6Моделирование содержимого трюма нефтеналивного танкера
Танкер перевозит 80 тыс. тонн нефти. В

Слайд 7Подходы распараллеливания на системы с распределённой памятью
Равномерное распределение нагрузки между узлами

Слайд 8Ортогональное рекуррентное деление пополам
Рис. 2. Положение границ разделяющих подобласти и распределение

Слайд 9Кривая делящая пространство
Рис. 3. Peano-Hilbert кривая.
Рис. 4. Пример декомпозиции области решения,

Слайд 10Пример применения методов ORB и SFC*
Рис. 5. Пример применения методов ORB(а)

Слайд 11Подходы распараллеливания на системы с распределённой памятью
Минимизация объема данных пересылаемых между

Слайд 12Частицы, пересылаемые между вычислительными узлами
подобласть А
подобласть А
подобласть Б
подобласть Б
частицы находящиеся в

Слайд 13Минимизация количества пересылок
а)
б)
Рис. 7. Пример сокращения частиц требующих пересылки данных, для

Слайд 14Минимизация количества пересылок
а)
б)
Рис. 8. Пример сокращения частиц требующих пересылки данных, для

Слайд 15Подходы распараллеливания на системы с общей памятью
Минимизация пересылок данных между оперативной

Слайд 16Метод моделирования сетки для алгоритма поиска соседей
Равномерная сетка (массив списков ссылок

Слайд 17Пример сортировки частиц по индексу
массив ячеек сетки
таблица соответствия
массив частиц
Рис. 11. Организация

Слайд 18Пространственное хэширование
Будем использовать след. ф-ю хэширования:

где

Слайд 19Пространственное хэширование

x
y
z
хэш таблица
массив частиц
Рис. 14. Модель организации данных для пространственного хэширования.

Слайд 20Оптимизация пространственного хэширования

x
y
z
хэш таблица
массив частиц
Рис. 15. Модель организации данных для пространственного

Слайд 21Сравнение различных подходов
Рис. 16. Пример результатов замеров времени для различных алгоритмов

Слайд 22Обзор литературы
Biddiscombe J. Efficient parallelization strategy for the SPH method. B.:

Обратная связь

Что такое ThePresentation.ru?

Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев презентация

Содержание

Слайд 1МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯКЕМЕРОВСКИЙ

Слайд 2Цель: выбрать оптимальные способы распараллеливания метода SPH для систем с общей

Слайд 3Примеры функций ядра:Рис 1. График функции ядраАппроксимация интегральным представлением

Слайд 4Аппроксимация частицами

Слайд 5Дифференциальные уравнения движения вязкой, несжимаемой жидкости

Слайд 6Моделирование содержимого трюма нефтеналивного танкераТанкер перевозит 80 тыс. тонн нефти. В

Слайд 7Подходы распараллеливания на системы с распределённой памятьюРавномерное распределение нагрузки между узлами

Слайд 8Ортогональное рекуррентное деление пополамРис. 2. Положение границ разделяющих подобласти и распределение

Слайд 9Кривая делящая пространствоРис. 3. Peano-Hilbert кривая.Рис. 4. Пример декомпозиции области решения,

Слайд 10Пример применения методов ORB и SFC*Рис. 5. Пример применения методов ORB(а)

Слайд 11Подходы распараллеливания на системы с распределённой памятьюМинимизация объема данных пересылаемых между

Слайд 12Частицы, пересылаемые между вычислительными узламиподобласть Аподобласть Аподобласть Бподобласть Бчастицы находящиеся в

Слайд 13Минимизация количества пересылока)б)Рис. 7. Пример сокращения частиц требующих пересылки данных, для

Слайд 14Минимизация количества пересылока)б)Рис. 8. Пример сокращения частиц требующих пересылки данных, для

Слайд 15Подходы распараллеливания на системы с общей памятьюМинимизация пересылок данных между оперативной

Слайд 16Метод моделирования сетки для алгоритма поиска соседейРавномерная сетка (массив списков ссылок

Слайд 17Пример сортировки частиц по индексумассив ячеек сеткитаблица соответствиямассив частицРис. 11. Организация

Слайд 18Пространственное хэшированиеБудем использовать след. ф-ю хэширования:где

Слайд 19Пространственное хэшированиеxyzхэш таблицамассив частицРис. 14. Модель организации данных для пространственного хэширования.

Слайд 20Оптимизация пространственного хэшированияxyzхэш таблицамассив частицРис. 15. Модель организации данных для пространственного

Слайд 21Сравнение различных подходовРис. 16. Пример результатов замеров времени для различных алгоритмов

Слайд 22Обзор литературыBiddiscombe J. Efficient parallelization strategy for the SPH method. B.:

Похожие презентации

Обратная связь

Что такое ThePresentation.ru?

Слайд 1МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
КЕМЕРОВСКИЙ

Слайд 2
Цель: выбрать оптимальные способы распараллеливания метода SPH для систем с общей

Слайд 3

Примеры функций ядра:
Рис 1. График функции ядра
Аппроксимация интегральным представлением

Слайд 6Моделирование содержимого трюма нефтеналивного танкера
Танкер перевозит 80 тыс. тонн нефти. В

Слайд 7Подходы распараллеливания на системы с распределённой памятью
Равномерное распределение нагрузки между узлами

Слайд 8Ортогональное рекуррентное деление пополам
Рис. 2. Положение границ разделяющих подобласти и распределение

Слайд 9Кривая делящая пространство
Рис. 3. Peano-Hilbert кривая.
Рис. 4. Пример декомпозиции области решения,

Слайд 10Пример применения методов ORB и SFC*
Рис. 5. Пример применения методов ORB(а)

Слайд 11Подходы распараллеливания на системы с распределённой памятью
Минимизация объема данных пересылаемых между

Слайд 12Частицы, пересылаемые между вычислительными узлами
подобласть А
подобласть А
подобласть Б
подобласть Б
частицы находящиеся в

Слайд 13Минимизация количества пересылок
а)
б)
Рис. 7. Пример сокращения частиц требующих пересылки данных, для

Слайд 14Минимизация количества пересылок
а)
б)
Рис. 8. Пример сокращения частиц требующих пересылки данных, для

Слайд 15Подходы распараллеливания на системы с общей памятью
Минимизация пересылок данных между оперативной

Слайд 16Метод моделирования сетки для алгоритма поиска соседей
Равномерная сетка (массив списков ссылок

Слайд 17Пример сортировки частиц по индексу
массив ячеек сетки
таблица соответствия
массив частиц
Рис. 11. Организация

Слайд 18Пространственное хэширование
Будем использовать след. ф-ю хэширования:

где

Слайд 19Пространственное хэширование

x
y
z
хэш таблица
массив частиц
Рис. 14. Модель организации данных для пространственного хэширования.

Слайд 20Оптимизация пространственного хэширования

x
y
z
хэш таблица
массив частиц
Рис. 15. Модель организации данных для пространственного

Слайд 21Сравнение различных подходов
Рис. 16. Пример результатов замеров времени для различных алгоритмов

Слайд 22Обзор литературы
Biddiscombe J. Efficient parallelization strategy for the SPH method. B.: