'

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

Понравилась презентация – покажи это...





Слайд 0

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Математический факультет Кафедра ЮНЕСКО по новым информационным технологиям    план работы Распараллеливание метода SPH аспиранта Кузнецова Арсения Владимировича Научный руководитель: доктор физ.-мат. наук К.Е. Афанасьев


Слайд 1

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


Слайд 2

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


Слайд 3

Аппроксимация частицами 4


Слайд 4

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


Слайд 5

Моделирование содержимого трюма нефтеналивного танкера 6 Танкер перевозит 80 тыс. тонн нефти. В дипломной работе удалось провести моделирование с использованием 65 тыс. частиц SPH. При такой массе моделируемой жидкости и количестве частиц, масса частицы составит 1,23 тонны. Рис. 1. Танкер «MINERVA ASTRA», грузоподъёмностью 81 тыс.т. нефти.


Слайд 6

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


Слайд 7

Ортогональное рекуррентное деление пополам 8 Рис. 2. Положение границ разделяющих подобласти и распределение нагрузки по вычислительным узлам, до балансировки нагрузки (а), после балансировки (б). а) б)


Слайд 8

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


Слайд 9

Пример применения методов ORB и SFC* 10 Рис. 5. Пример применения методов ORB(а) и SFC(б), цветовая гамма соответствует распределению по вычислительным узлам. а) б) *Пример был опубликован в работе: Wagner S., Streinmetz M., Bode A., Brehm M. High performance computing in science and engineering. B.: Springer-Verlag. 2007. P. 715.


Слайд 10

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


Слайд 11

Частицы, пересылаемые между вычислительными узлами 12 подобласть А подобласть А подобласть Б подобласть Б частицы находящиеся в около граничной области пересылка данных о частицах на соседний вычислительный узел Рис. 6. Определение частиц, требующих пересылки данных


Слайд 12

Минимизация количества пересылок 13 а) б) Рис. 7. Пример сокращения частиц требующих пересылки данных, для ORB метода декомпозиции пространства. Необходимо передать 18 частиц (а), или 11 частиц (б). Красная линия – граница подобластей.


Слайд 13

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


Слайд 14

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


Слайд 15

Метод моделирования сетки для алгоритма поиска соседей Равномерная сетка (массив списков ссылок на частицы) последовательная генерация сетки пространственно близкие частицы не сгруппированы в памяти Сортировка частиц по индексу Для каждой частицы рассчитываем индекс ячейки соответствующий её координатам где , - кол-во ячеек по оси Ox и Oy соответственно. По данному индексу отсортируем массив частиц. 16


Слайд 16

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


Слайд 17

Пространственное хэширование Будем использовать след. ф-ю хэширования: где - простые, большие числа, - размер хэш таблицы. 18 x y z хэш таблица массив частиц Рис. 13. Модель организации данных для пространственного хэширования.


Слайд 18

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


Слайд 19

Оптимизация пространственного хэширования 20 x y z хэш таблица массив частиц Рис. 15. Модель организации данных для пространственного хэширования. резервный массив таблица используемых частиц таблица частиц размер m размер l размер n размер n размер l m – фиксированный пользователем размер хеш-таблицы, l – кол-во заполненных ячеек, n – кол-во частиц.


Слайд 20

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


Слайд 21

Обзор литературы 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


×

HTML:





Ссылка: