Очевидным является хранение матрицы в построчном формате с
использованием одного бита на элемент. Это позволяет совершать
многие операции с числом элементов строки, равным числу бит в
слове, за одну инструкцию. Для архитектуры CUDA оптимальным
является выбор 32-битного слова.
Поиск ведущей строки.
Выбранный формат хранения имеет свой
недостаток: неэффективный доступ к памяти при поиске ведущей
строки, так как элементы одного столбца матрицы хранятся в би-
тах далеких друг от друга слов. Для преодоления этого недостатка
используется параллельный поиск:
n
потоков считывают элементы
последовательных строк и каждый поток, считавший ненулевой эле-
мент, обновляет ячейку общей памяти атомарной операцией записи.
Если ненулевых элементов не было найдено, процесс повторяется для
следующих
n
строк. Строки между ведущей и первой, содержащей
ненулевой элемент, исключаются из операции вычитания строк. По-
скольку алгоритм использует барьеры, число потоков параллельного
поиска ограничено сверху максимальным числом потоков на блок, что
для современных ГП составляет 512 или 1024 [12]. Этого оказыва-
ется достаточно (увеличение числа потоков свыше примерно 300 не
дает дополнительного ускорения). Применение параллельного поиска
уменьшает общее время вычислений для сильно разреженных матриц
(плотностью меньше
1
/
1000
), где эта операция является преобладаю-
щей по времени (на два порядка). Для плотных матриц параллельный
поиск замедляет работу (до 10%), и более удачным является ограни-
чение числа потоков поиска размером ворпа как минимальной испол-
няемой единицы. Использование атомарных операций над общей па-
мятью требует устройств, поддерживающих CUDA capability 1.2 [12],
а для устройств с меньшими возможностями используется однопоточ-
ный поиск. Использование глобальной памяти для размещения общей
ячейки делает работу алгоритма неприемлемо медленной.
Если найденная строка не является первой, то ее необходимо об-
менять местами с первой. Для ускорения этой операции часто исполь-
зуется индексный массив строк, но для реализации на CUDA оказы-
вается быстрее обменять само содержимое строк, отказавшись от ис-
пользования дополнительной индексации. Это связано с относительно
редкой необходимостью в этой операции для плотных матриц и не-
возможностью сделать полностью совмещенным доступ к индексам
из ядра вычитания строк.
Вычитание ведущей строки.
Сам по себе алгоритм вычитания ве-
дущей строки при выбранном формате хранения матрицы тривиален,
однако его реализация критически важна, так как для плотных ма-
триц его время работы составляет подавляющую часть всего времени
вычислений.
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2013. № 1
53
