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

Одним из главных преимуществ 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 раз.