Массивно-параллельное программирование на CUDA

Преподаватель: Перепёлкин Евгений Евгеньевич
доктор физико-математических наук, профессор кафедры квантовой статистики и теории поля

Общая информация

Курс предназначен для разработчиков и исследователей, желающих познакомиться с основами программирования графических процессоров (GPU) NVIDIA в целях ускорения решаемых задач. Слушателям будут даны основы программирования с использованием технологии CUDA, приведены сведения о типах памяти GPU, будут рассмотрены библиотеки и инструменты, входящие в комплект разработчика CUDA Toolkit, вопросы отладки, профилирования и оптимизации CUDA-программ. Также будет рассмотрен стандарт параллельного программирования OpenACC и особенности программирования многопроцессорных систем с несколькими GPU.

Приблизительная программа курса

Лекция 1

Проблемы повышения частоты центральных процессоров (CPU) и перехода на низший техпроцесс. Графический процессор как массивно-параллельная архитектура. Тандем CPU-GPU. Задачи, решаемые на GPU: астрофизика, био-информатика (анализ ДНК, секвенирование генома, скручивание белков), молекулярная динамика, ускорительная физика, обработка данных в реальном времени (big data, data-mining, on-line обработка экспериментальных данных), гидрогазодинамика, нефтегазовая промышленность (каротаж скважин), финансовая индустрия (рынок акций, опционы, бонды, капитализация), задачи распознавания (программа «безопасный город», глубокое обучение (deep learning)), компьютерная графика, шоу бизнес и многое другое

Лекция 2

Гибридная модель вычислений. Типы вычислительных архитектур. Архитектура графического процессора (GPU). Высокоскоростное внутреннее соединение NVIDIA NVLink обмена данными между GPUs

Лекция 3

Программная модель CUDA. Гибридная модель программного кода. Понятие потока, блока, сети блоков. Функция – ядро как параллельный код на GPU.

Лекция 4

Иерархия памяти на GPU. Регистры и локальная память. Register spilling. L1 и Read Only Data Cache. Глобальная память и L1, L2. Шаблон работы с глобальной памятью.

Лекция 5

Компиляция кода на GPU. Средства разработки MS Visual Studio, NVIDIA Profiler, NVIDIA Parallel Nsight.
Задача. Простейший алгоритм параллельного вычисления значений функции на GPU. Сравнение времени копирования данных между «host» / «device» и времени вычислений на GPU.

Лекция 6

Compute Capability видеокарты. Объединение запросов при доступе в глобальную память (Coalescing). Использование L1 cash и _ldg при работе с глобальной памятью.
Задача. Пример параллельного алгоритма решения системы линейных алгебраических уравнений (СЛАУ). Оптимизация доступа в глобальную (coalescing, L1 cash, _ldg ) память в алгоритме решения СЛАУ.

Лекция 7

Параллельный алгоритм решения задачи многих тел (N-body) с использованием глобальной памяти.
Задача. Гравитационное и электрическое взаимодействие. Оценка эффективности.

Лекция 8

Pinned-память. Оптимизация копирования данных с «host» на «device» с использованием pinned-памяти.
Задача. Использование pinned-памяти в алгоритме вычисления значений функции (лекция 4) и решения СЛАУ.

Лекция 9

Понятие CUDA-потока (CUDA-Streams). Асинхронное выполнение функции-ядра и асинхронное копирование данных между «host» и «device».
Задача. Пример использование CUDA-потоков и pinned-памяти в алгоритме обработке массивов данных. Оценка времени копирования данных, вычислений на GPU, загрузки шины PCI-E

Лекция 10

Шаблон работы с глобальной памятью. Массивы с выравниванием. Двумерные массивы в глобальной памяти GPU.
Задача. Пример параллельного алгоритма перемножения матриц.

Лекция 11

Разделяемая память (shared memory) и L1-cache. Шаблон работы с разделяемой памятью.
Задача. Параллельный алгоритм решения задачи многих тел (N-body) с использованием разделяемой памяти.

Лекция 12

Оптимизация работы с разделяемой памятью. Понятие банков. Понятие банк- конфликтов.
Задача. Параллельный алгоритм перемножения матриц с использованием разделяемой памяти (оптимизация банк-конфликтов, параллелизм по нитям (TLP), параллелизм по инструкциям (ILP) )

Лекция 13

Разделяемая память.
Задача. Оптимизация алгоритма задачи многих тел (N-body) с использованием разделяемой памяти.

Лекция 14

Статические переменные. Константная память. Текстурная память. Конвейеры текстурной памяти: фильтрация, переадресация. Нормализованные и целочисленные координаты.
Задача. Параллельный алгоритм вычисление свертки функций с использованием текстурной и разделяемой памяти в задачах обработки сигнала (изображения).

Лекция 15

Режим фильтрации в текстурной памяти. Вычисления конечно-разностных производных.
Задача. Интерполяция конечно-разностной функции при переходе из одной системы координат в другую.

Лекция 16

Алгоритм параллельной редукции с использованием разделяемой памяти. Оптимизация алгоритма редукции (ветвления в варпах (warps), банк-конфликты (bank-conflict), развертка циклов).
Задача. Параллельное суммирование рядов на GPU.

Лекция 17

Свободные параллельные библиотеки на GPU. Библиотека линейной алгебры CUBLAS. Библиотека быстрого преобразования Фурье CUFFT.
Задача. Задача о нахождении электрического поля, создаваемого плотность электрического заряда. Уравнение Пуассона. Быстрое преобразование Фурье.

Лекция 18

Свободные параллельные библиотеки на GPU. Библиотека генератора псевдо-случайных чисел CURAND. Библиотека для работы с разряженными матрицами CUSPARS. Библиотека шаблонов STL – Thrust. Библиотека примитивов NPP.
Задача. Задача вычисления интеграла методом Монте-Карло.

Лекция 19

Параллельный алгоритм решения системы нелинейных алгебраических уравнений. Непрерывный аналог метода Ньютона. Понятие производной Фреше. Оптимизация доступа в память.
Задача. Реализация алгоритма решения СНАУ

Лекция 20

Уравнения гидрогазодинамики (Навье-Стокса). Параллельный алгоритм численного моделирования течения несжимаемой жидкости на GPU. Схема расщепления, метод прогонки, оптимизация доступа в глобальную память. Оценка производительности.

Лекция 21

Задача трассировки лучей (Ray Tracing). Текстурная память. Компьютерная графика. Создание фотореалистичных изображений. Алгоритмы Boundary Volume Hierarchy (BVH) и kd-деревьев. Оценка эффективности алгоритмов.

Лекция 22

Использование метода трассировки лучей (Ray Tracing) в ускорительной физике при оценке потерь частиц пучка на структурных элементах установки (триангуляционный подход). Оптимизация, использование разделяемой памяти.

Лекция 23

Стандарт OpenMP. Основные директивы OpenMP. Использование OpenMP при распараллеливании на центральном процессоре (CPU): обработка данных, перемножение матриц, задача многих тел.

Лекция 24

Стандарт OpenACC для кросс-платформенных приложений. Описание стандарта OpenACC. Основные директивы OpenACC. Процесс компиляции приложения в OpenACC (оценка эффективности распараллеливания).
Задача. Сравнение эффективности параллельных реализаций на CPU OpenMP, на GPU OpenACC и на GPU CUDA: обработка данных, перемножение матриц, задача многих тел.

Лекция 25

Задача электростатики. Постановка задачи, численный метод и параллельный алгоритм реализации на GPU. 3D- моделирование распределения электрического поля банчера, инфлектора, дуантов, дефлектора в циклотроне.

Лекция 26

Задача магнитостатики. Постановка задачи, численный метод и параллельный алгоритм реализации на GPU. Моделирование распределения магнитного поля на примере установки ATLAS LHC CERN.

Лекция 27

Метод массивно-параллельной архитектуры GPU в задачах моделирования динамики пучка в ускорительной физике.
Задача. Параллельные алгоритмы трассировки частиц, оценки потерь частиц, оценки эффекта пространственного заряда пучка.

Лекция 28

Примеры оптимизация параметров циклотрона: AVF RIKEN Cyclotron (Japan).

Лекция 29

Примеры оптимизация параметров циклотронов: VINCY Cyclotron (Serbia), Custom Cyclotron (USA)

Лекция 30

Коллективные методы ускорения (В.И. Векслер). Постановка задачи, численные методы. Учѐт собственного электрического и магнитного поля пучка. Параллельный алгоритм на GPU для моделирования коллективных методов ускорения частиц на установке CUSP.

Лекция 31

Уравнение Кардара-Паризи-Жанга. Скейленговая гипотеза. Скейленговая функция и скейлинговый параметр. TASEP (Total Asymmetric Exclusion Process). Параллельный алгоритм на GPU оценки скейленговой функции и скейленгового параметра для TASEP.

Лекция 32

Вычисления в режиме Multi-GPU. Использование нескольких графических процессоров GPU на одном узле. Обмен данными между GPU (Direct 2.0). Использование интерфейсов NVLink и PCI-E. Унифицированное адресное пространство (Unified Virtual Addressing). Оптимизация нагрузки между GPU.

Лекция 33

Распараллеливание нейро-сетевых алгоритмов. Обучение нейро-сети на GPU.
Глубокое обучение (Deep Learning). Библиотеки, алгоритмы. Задача распознавания образов.