Стандартные библиотеки и алгоритмы для разработки на GPU Александр Мыльцев (Parallel Compute) 1

Библиотеки для разработки 2

Библиотеки CUDA Toolkit –Thrust : библиотека шаблонов –NPP: обработка изображений и сигналов –CURAND: псевдо- и квазислучайные числа –LIBM: стандартная библиотека математических примитивов –CUSPARSE : линейная алгебра для разреженных матриц –CUBLAS: линейная алгебра для плотных матриц –CUFFT: преобразование Фурье Библиотеки сторонних разработчиков –MAGMA: линейная алгебра –OpenVidia: компьютерное зрение –CULA Tools: линейная алгебра –OpenCurrent: динамика жидких сред –CUSP: решатели разреженных матриц –NAG: вычислительная финансовая система –… 3

Библиотеки 4

CUFFT Быстрое преобразование Фурье 5

Особенности CUFFT Интерфейс подобен FFTW Одно-, двух- и трехмерные вещественные и комплексные преобразования Одинарная и двойная точность Одномерное преобразования до 128 миллионов элементов Потоковое асинхронное вычисление Ненормализованный вывод: IFFT(FFT(A))=len(A)*A 6

Использование CUFFT Шаг 1: выделить память на GPU Шаг 2: создать и настроить преобразование (размер, тип…) Шаг 3: выполнить преобразование столько раз, сколько необходимо, используя указатель из шага 1 Шаг 4: уничтожить преобразование и освободить память на GPU 7

Вызов CUFFT 8

CUBLAS Реализация BLAS –Basic Linear Algebra Subprograms Поддержка всех функций BLAS –Level1 (вектор-вектор): O(N) AXPY: y = alpha.x + y DOT: dot = x.y –Level2 (матрица-вектор): O(N^2) Vector multiplication by a General Matrix : GEMV Triangular solver : TRSV –Level3 (матрица-матрица): O(N^3) General Matrix Multiplication : GEMM Triangular Solver : TRSM 9

Особенности CUBLAS Поддержка 4 типов: –Float, Double, Complex, Double Complex –Префиксы: S, D, C, Z 152 функции: S(37), D(37), C(41), Z(41) Название функций: cublas + BLAS_name Пример: cublasSGEMM –S: одинарной точности –GE: general (общего вида) –M: multiplication (умножение) –M: matrix (матрица) 10

Использование CUBLAS Интерфейс в cublas.h Имена функций (cublasSGEMM) Обработка ошибок –Функции ядра не возвращают ошибок Есть функция для получения последней ошибки –Вспомогательные функции возвращают ошибки Вспомогательные функции: –Выделение памяти, передача данных 11

Вызов CUBLAS 12

CUBLAS в CUDA 4.0 Новый заголовочный файл cublas_v2.h –Новый API Добавлена возможность работы с несколькими GPU Все функции возвращают код ошибки cublasSetKernelStream() переименован в cublasSetStream() 13

CURAND Генерация псевдослучайных чисел Возможность API вызов на хосте для генерации случайных чисел Возможность использовать внутри GPU функций/ядер Равномерные, нормальные и логнормальные распределения одинарной и двойной точности 14

Использование CURAND Создание генератора curandCreateGenerator() Инициализация генератора curandSetPseudoRandomGeneratorSeed() Генерация данных из распределений curandGenerateUniform()/curandGenerateUniformDouble(): Равномерное curandGenerateNormal()/cuRandGenerateNormalDouble(): Гауссово curandGenerateLogNormal/curandGenerateLogNormalDouble(): Лог-нормальное Уничтожение генератора curandDestroyGenerator() 15

Вызов CURAND 16

NPP NVIDIA Performance Primitives Библиотека функций –Оптимизирована –Низкоуровневая –Исполняется на GPU ~350 функций для обработки изображений ~100 функций для обработки сигналов 17

Thrust Библиотека шаблонов для CUDA –Похожа на C++ STL Контейнеры –Управление памятью на хосте и устройстве: thrust::host_vector, thrust::device_vector –Помогает избежать распространенные ошибки Итераторы –Знают, где находятся данные Алгоритмы –Сортировка, редукция, префиксная сумма, и т. д. 18

Алгоритмы 19

Алгоритмы Редукция Префиксная сумма (scan) Битоническая сортировка Свертка Построение гистограмм Поразрядная сортировка … 20

Где найти? Основы работы с технологией CUDA Боресков А. В., Харламов А. А. Курс МГУ по CUDA CUDA SDK + Ссылки на статьи Программа сертификации 21

RANSAC RANdom SAmple Consensus Метод оценки параметров модели на основе случайных выборок Два типа точек: –Инлаеры (или невыбросы) –Аутлаеры (или выбросы) 22

Применение Компьютерное зрение –Сопоставление изображений –Поиск фундаментальной матрицы –Распознавание образов –Определение положения камеры 23

Пример Scipy.org 24

Данные data – исходные данные model – некоторая модель, которая может быть фитирована данными n – минимальное число значений, которое необходимо для фитирования модели k – максимальное количество итераций t – пороговое значение для принадлежности точки к модели d – необходимое количество близких точек, которое необходимо для фитирования модели Алгоритм возвращает параметры модели 25

Псевдокод while iterations < k { maybeinliers = n randomly selected values from data maybemodel = model parameters fitted to maybeinliers alsoinliers = empty set for every point in data not in maybeinliers { if point fits maybemodel with an error smaller than t add point to alsoinliers } if the number of elements in alsoinliers is > d { % Означает, что мы, возможно, нашли одну из хороших моделей % и проверим насколько она хороша bettermodel=model parameters fitted to all points in maybe- and alsoinliers thiserr = a measure of how well model fits these points if thiserr < besterr { bestfit = bettermodel besterr = thiserr } increment iterations } return bestfit 26

Примеры моделей Прямая Параллельные прямые Перпендикулярные прямые Окружность Квадрат … 27

МНК для прямой 28

МНК для окружности Центр координат в арифметическом среднем: Если- центр окружности с радиусом R, то задача минимизировать где Система уравнений: 29

МНК для квадрата Квадрат в полярных координатах: Квадрат в декартовых координатах: Функционал для минимизации: 30

Реализация 1 Каждая нить считает точку всей модели CULA – GPU-accelerated linear algebra library –Применение CULA на малых выборках замедляет вычисления на 2 порядка –При наборах ~ точек – в 1.5 раза медленнее процессора Затраты на пересылку данных, и случайный доступ к общей памяти 31

Реализация 2 Каждая нить считает отдельную модель Быстро работает для небольших N –При больших N GPU может не успеть отработать 32

Пример RANSAC для окружности 33

Брошюра «Вычисления на NVIDIA Tesla» –На последней странице контакты Антона Джораева Вопросы 34