Алгоритм перемножения матриц

Перемножение матриц на CUDA

Структура программы на CUDA

Средства для написания и компиляции программ на CUDA

Компиляторы, поддерживающие CUDA, существуют и для Windows, и для UNIX-подобных операционных систем, таких как Linux. Мы разраба­тывали программы на CUDA как Windows-приложе­ния, используя компью­тер следующей программно-аппаратной конфигу­ра­ции.

· AMD Athlon X2 4000+ (2100 MHz)

3 GB DDR2 (667 MHz)

· NVIDIA GeForce 8800 GTX (частота скалярных процессоров 1350 MHz)

768 MB 384-bit GDDR3 (1800 MHz)

· Microsoft Windows XP + Service Pack 2

· CPU Driver AMD 1.3.2.0053 (09/2007)

· GPU Driver NVIDIA Forceware 177.84 (08/2008)

· Microsoft.NET Framework 3.5

· Microsoft DirectX 9.0c (4.09.0000.0904, 08/2007)

· NVIDIA CUDA 2.0 (Toolkit + SDK)

· Microsoft 32-bit C/C++ compiler 14.0 (в составе Visual Studio 2005)

Проект с кодом CUDA открывается и компилируется как обычный проект в Microsoft Visual Studio 2005. При сборке проекта возможны 4 выбо­ра конфигурации: Release,Debug,EmuRelease, EmuDebug. Выбор конфигу­рации EmuDebug позволяет запускать проект в отладочном режиме.

Вычислительные ядра для GPU выглядят как обычные функции языка C, со следующими ограничениями:

· могут обращаться только к памяти GPU, но не к оперативной памяти компьютера;

· не возвращают никакого значения (тип возвращаемого значения – только void);

· допускают только фиксированное количество аргументов;

· не допускают рекурсивного вызова;

· не могут включать статических переменных.

Аргументы этих функций автоматически копируются из оперативной памяти компьютера в память GPU.

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

Одним из главных преимуществ GPU шейдерной модели 4.0 является то, что для них возможно программируемое управление отдельными блоками «вычислителей», что во многих задачах позволяет оптимизировать использо­вание вычислительных возможностей графического процессора. Хорошим примером этого является реализация алгоритма перемножения матриц.

Математически задача перемножения двух матриц A и B формули­руется следующим образом:

,

где

.

Рис. 9.3. Схема программы на графическом процессоре шейдерной модели 4.0

Для того, чтобы умножение было возможным, необходимо чтобы ширина матрицы A (равная n) совпадала с высотой матрицы B (тоже равной n). При этом получится, что у результирующей матрицы C высота совпадает с высотой матрицы A, а ширина – с шириной матрицы B. Этот принцип очень наглядно иллюстрируется умножением матрицы на вектор:

.

Метод распараллеливания умножения матриц на GPU SM4 заключает­ся в следующем.

· Исходные матрицы A и B разбиваются на блоки, с тем, чтобы каждый из мультипроцессоров вычислял произведение одного из блоков матрицы A на один из блоков матрицы B. Пусть, для простоты, эти блоки будут кубическими.

· Размер блоков (Block_Size) выбирается таким образом, чтобы два перемно­жаемых блока целиком помещались в разделяемую память мульти­процес­сора (Parallel Data Cash на рис. 9.2).

· В ходе исполнения программы на каждом мультипроцессоре исполняются одна или две «связки» потоков, а каждый поток исполняется на одном конкретном «вычислителе». Потокам внутри «связки» нужно поста­вить в соответствие двухмерные номера – значения индексов i и k в диапазо­не от 1 до Block_Size.

· Внутри отдельного потока запрограммировать суммирование

.

при фиксированных индексах (i, k), как это показано на рис. 9.4.

Рис. 9.4. Схема перемножения матриц на GPU шейдерной модели 4.0

На рис. 9.4 каждая матрица Csub равна произведению двух прямоуголь­ных блоков: блока матрицы A размерами (wA, Block_Size), индексы строк которого совпадают с индексами строк матрицы Csub, и блока матрицы B размерами (Block_Size, wA), индексы столбцов которого совпадают с индексами столбцов матрицы Csub. Окончательно, матрица Csub вычисляет­ся как сумма произведений квадратных блоков, показанных на рис. 9.4, по следующему принципу:

,

где n = wA / Block_Size – количество блоков, приходящееся на ширину матри­цы A и равную ей высоту матрицы B.

Для расчета каждого из этих произведений сначала в разделяемую память загружаются два соответствующих блока из глобальной памяти, а затем каждый поток «связки» вычисляет один элемент произведения. При этом происходит накопление суммы результатов , которая затем сохра­няется в глобальной памяти.

Отметим, что рассмотренный алгоритм перемножения матриц на GPU SM4 не является самым быстрым из возможных. Тем не менее, он хорошо иллюстрирует принципы управления вычислительными потоками и оптимизации использования памяти при программировании GPU SM4. В частности, разбиение матриц на блоки позволило задействовать быструю разделяемую память, сокращая число выборок из глобальной памяти до n = wA / Block_Size раз.

Дата добавления: 2014-12-07