Факультет прикладной математики и физики Кафедра вычислительной математики и программирования МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (национальный исследовательский университет) (национальный исследовательский университет) Выполнил: Семенов С.А. Руководитель: Ревизников Д.Л. Лекция 5 « Критерии применимости параллельных вычислений. Примеры применения параллельных вычислений »

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 2 Московский авиационный институт (национальный исследовательский университет ) Введение Критерии применимости параллельных вычислений Капли дождя на воде Движение дымных частиц Волнение океана

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 3 Московский авиационный институт (национальный исследовательский университет ) Зависимость ускорения и эффективности работы параллельной программы от количества процессоров :

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 4 Московский авиационный институт (национальный исследовательский университет ) Уровни параллелизма

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 5 Московский авиационный институт (национальный исследовательский университет ) Метрики параллелизма

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 6 Московский авиационный институт (национальный исследовательский университет ) Ускорение

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 7 Московский авиационный институт (национальный исследовательский университет ) Закон Амдала

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 8 Московский авиационный институт (национальный исследовательский университет ) Эффективность

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 9 Московский авиационный институт (национальный исследовательский университет ) Практические ограничения ускорения

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 10 Московский авиационный институт (национальный исследовательский университет ) Закон Густафсона

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 11 Московский авиационный институт (национальный исследовательский университет ) Эффективность

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 12 Московский авиационный институт (национальный исследовательский университет ) Cuda raindrop

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 13 Московский авиационный институт (национальный исследовательский университет ) Cuda ocean

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 14 Московский авиационный институт (национальный исследовательский университет ) Cuda smoke particles

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 15 Московский авиационный институт (национальный исследовательский университет ) Решение дифф. уравнений на CUDA на примере задач аэро-гидродинамики Вычислительные задачи аэро- гидродинамики Моделирование турбулентных течений ВМиК МГУ, кафедра мат. физики Пасконов В.М., Березин С.Б.

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 16 Московский авиационный институт (национальный исследовательский университет ) Турбулентность Моделирование турбулентности Прямое численное моделирование (DNS) Моделирование крупномасштабных вихрей (LES) Осредненные уравнения Навье-Стокса (RANS) все масштабы турбулентности очень затратный

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 17 Московский авиационный институт (национальный исследовательский университет ) Постановка задачи Течение вязкой несжимаемой жидкости в 3D канале –Канал заполнен и находится в однородной среде –Произвольные начальные и граничные условия –Неизвестные величины – скорость и температура

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 18 Московский авиационный институт (национальный исследовательский университет ) Основные уравнения Полная система уравнений Навье- Стокса в безразмерных величинах –Уравнение неразрывности –Уравнения движения (Навье-Стокса) –Уравнение энергии

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 19 Московский авиационный институт (национальный исследовательский университет ) Обозначения Плотность Скорость Температура Давление z Уравнение состояния – газовая постоянная

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 20 Московский авиационный институт (национальный исследовательский университет ) Уравнение неразрывности Используется при выводе остальных уравнений (движения и энергии) Проверка точности текущего решения

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 21 Московский авиационный институт (национальный исследовательский университет ) Уравнения Навье-Стокса Второй закон Ньютона: Вязкая жидкость: f – массовые силы (сила тяжести) – тензор вязких напряжений p – давление Невязкая жидкость:

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 22 Московский авиационный институт (национальный исследовательский университет ) Безразмерные уравнения Параметры подобия –Число Рейнольдса –Число Прандтля Уравнение состояния для идеального газа/жидкости: – характерная скорость, размер – динамическая вязкость среды – коэффициент теплопроводности – удельная теплоемкость

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 23 Московский авиационный институт (национальный исследовательский университет ) Уравнения движения Безразмерная форма: –Не рассматриваем массовые силы –Уравнение состояния

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 24 Московский авиационный институт (национальный исследовательский университет ) Уравнение энергии Первый закон термодинамики для объема V: Диссипативная функция:

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 25 Московский авиационный институт (национальный исследовательский университет ) Финальные уравнения 4 нелинейных уравнения 4 неизвестные величины: –Компоненты скорости: u, v, w –Температура: T

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 26 Московский авиационный институт (национальный исследовательский университет ) Численный метод Расщепление по координатам XYZ

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 27 Московский авиационный институт (национальный исследовательский университет ) Уравнение диффузии 3 дробных шага – X, Y, Z Неявная конечно-разностная схема

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 28 Московский авиационный институт (национальный исследовательский университет ) Уравнения Навье-Стокса Уравнение для X-компоненты скорости –+ итерации по нелинейности X Y Z

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 29 Московский авиационный институт (национальный исследовательский университет ) Шаг по времени (n-1) time step Splitting by X Splitting by Y Splitting by Z Updating non-linear parameters Global iterations (n) time step (n+1) time step

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 30 Московский авиационный институт (национальный исследовательский университет ) Дробный шаг Линейное PDEs N time layer u: x-velocityv: y-velocityw: z-velocityT: temperature N + 1 time layer Sweep Solves many tridiagonal systems independently Next layer Previous layer

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 31 Московский авиационный институт (национальный исследовательский университет ) Дробный шаг Нелинейное PDEs N time layer u: x-velocityv: y-velocityw: z-velocityT: temperature N + ½ time layer N + 1 time layer Update Copy Sweep Solves many tridiagonal systems independently Local iterations Next layer Previous layer

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 32 Московский авиационный институт (национальный исследовательский университет ) Стадии алгоритма Решение большого количества трехдиагональных СЛАУ Вычисление диссипации в каждой ячейке сетки Обновление нелинейных параметров

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 33 Московский авиационный институт (национальный исследовательский университет ) Особенности метода Большой объем обрабатываемых данных Высокая арифметическая интенсивность Легко распараллеливается

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 34 Московский авиационный институт (национальный исследовательский университет ) Реализация на CUDA Все данные хранятся в памяти GPU –4 скалярных 3D массива для каждой переменной (u, v, w, T) –3 дополнительных 3D массива ~1GB для сетки 192^3 в double

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 35 Московский авиационный институт (национальный исследовательский университет ) Решение трехдиагональных СЛАУ Каждая нить решает ровно одну трех диагональную СЛАУ –На каждом шаге N^2 независимых систем Расщепление XРасщепление YРасщепление Z

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 36 Московский авиационный институт (национальный исследовательский университет ) Метод прогонки Необходимо 2 дополнительных массива –хранение: локальная память Прямой ход –вычисление a[i], b[i] Обратный ход –x[i] = a[i+1] * x[i+1] + b[i+1]

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 37 Московский авиационный институт (национальный исследовательский университет ) Проблемы реализации Каждая нить последовательно читает и пишет столбец 3D массива –Коэффициенты и правая часть Y, Z – прогонки coalesced X – прогонка uncoalesced!

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 38 Московский авиационный институт (национальный исследовательский университет ) Оптимизация прогонки X – прогонка –Транспонируем входные массивы и запускаем Y-прогонку общая производительность всех прогонок

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 39 Московский авиационный институт (национальный исследовательский университет ) Расчет диссипации Расчет частных производных по трем направлениям –Локальный доступ к памяти Каждая нить обрабатывает столбец данных –Переиспользование расчитанных производных Использование разделяемой памяти (?)

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 40 Московский авиационный институт (национальный исследовательский университет ) Оптимизация диссипации Рефакторинг кода –Предварительный расчет некоторых констант, избавление от лишних if C++ шаблоны для X, Y, Z-диссипации –Уменьшение числа регистров, нет лишних обращений к памяти

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 41 Московский авиационный институт (национальный исследовательский университет ) Нелинейные итерации Необходимо посчитать полусумму двух 3D массивов Каждая нить считает сразу для столбца данных – N^2 нитей –Все чтения/записи coalesced Оптимальный выбор размера блока 80% от пиковой пропускной способности на Tesla C1060

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 42 Московский авиационный институт (национальный исследовательский университет ) Тест производительности Тестовые данные –Сетка 128^3, 192^3 –8 нелинейных итераций Сравнение CPU и GPU –Абсолютное время работы

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 43 Московский авиационный институт (национальный исследовательский университет ) Тест – float time steps/sec 20x 7x 9x

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 44 Московский авиационный институт (национальный исследовательский университет ) Тест – double time steps/sec 10x 4x 5x

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 45 Московский авиационный институт (национальный исследовательский университет ) Тест – float time steps/sec 28x 8x 11x

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 46 Московский авиационный институт (национальный исследовательский университет ) Тест – double time steps/sec 13x 4x 5x

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 47 Московский авиационный институт (национальный исследовательский университет ) Визуализация Векторное поле скоростей uv w T Срез вдоль Х

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 48 Московский авиационный институт (национальный исследовательский университет ) Решение краевых задач, системы линейных алгебраических уравнений Основное: –Решение 1D/2D задачи диффузии Дополнительное: –Решение СЛАУ с треугольной разряженной матрицей

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 49 Московский авиационный институт (национальный исследовательский университет ) Задача диффузии Уравнение теплопроводности: - коэффициент теплопроводности –Постоянный: –Линейный: –Нелинейный:

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 50 Московский авиационный институт (национальный исследовательский университет ) Постановка 1D задачи Область определения – отрезок Уравнение теплопроводности на Начальные условия: Граничные условия:

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 51 Московский авиационный институт (национальный исследовательский университет ) Методы решения Метод конечных разностей явные схемынеявные схемы На каждом шаге необходимо решать трех диагональную СЛАУ

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 52 Московский авиационный институт (национальный исследовательский университет ) Постановка 2D задачи Область определения: Уравнение теплопроводности: Начальные и граничные условия (W,0) (0,H) (0,0) (W,H)

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 53 Московский авиационный институт (национальный исследовательский университет ) Метод по-координатного расщепления Временной шаг разбивается на два дробных для каждого фикс. y для каждого фикс. x

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 54 Московский авиационный институт (национальный исследовательский университет ) Пример разностной аппроксимации Расщепление по X: Независимые трехдиагональные СЛАУ для каждого j = 0.. N_y –Легко параллелится

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 55 Московский авиационный институт (национальный исследовательский университет ) Трехдиагональные СЛАУ Прямые методы: –Метод прогонки Оптимальный по числу операций, но последовательный –Метод редукции Параллельный, но больше операций

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 56 Московский авиационный институт (национальный исследовательский университет ) Итерационные методы Якоби, Гаусса-Зейделя GMRES, CG Преобуславливатель (preconditioner)

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 57 Московский авиационный институт (национальный исследовательский университет ) Начальные значения Верхне-треугольная разряженная матрица NxN Число ненулевых элементов = NNZ X X X X X X X X X X X X X X X X X XX X X XX X

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 58 Московский авиационный институт (национальный исследовательский университет ) Пример матрицы N=5 NNZ=7 Data Indices Ptr024567

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 59 Московский авиационный институт (национальный исследовательский университет ) Решение уравнения Пуассона

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 60 Московский авиационный институт (национальный исследовательский университет ) Решение краевой задачи Для поиска коэффициентов Фурье можно воспользоваться библиотекой cuFFT. Формулу (*) можно распараллелить (*)

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 61 Московский авиационный институт (национальный исследовательский университет ) Метод Рунге - Кутта Lz Lx Ly

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 62 Московский авиационный институт (национальный исследовательский университет ) Разностная схема

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 63 Московский авиационный институт (национальный исследовательский университет ) Параметры

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 64 Московский авиационный институт (национальный исследовательский университет ) Рекомендуемые параметры Число частиц N от 100,000 до 1,000,000 Шаг по времени τ ~ сек. Параметры частицы, например, углерод 12 C 6+ –заряд Z = 6, q = Zq e, q e = Кл –масса m = 12 a.m.u, 1 a.m.u. = кг Размеры поучка –Разброс в поперечном сечении ± 5 см. Например, 2σ x = 2σ z = 5 см –Разброс в продольном направлении ± 10 см. Например, 2σ y = 10 см Число шагов по времени NT = T/ τ, где T = m/(2πq) – период обращения

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 65 Московский авиационный институт (национальный исследовательский университет ) Выводы Высокая эффективность Tesla в задачах аэро-гидродинамики Программная модель CUDA – удобное средство утилизации ресурсов GPU Применение GPU открывает новые возможности для исследования

Факультет прикладной математики и физики Кафедра Вычислительной математики и программирования 66 Московский авиационный институт (национальный исследовательский университет ) Вопросы