Данные вычитаемой строки используются на этом шаге много-
кратно, поэтому важно выбрать оптимальный способ их хранения. Из
всех видов памяти и способов доступа, предоставляемых платформой
CUDA, глобальная память имеет слишком большую латентность, по-
этому для рассмотрения остаются общий, константный и текстурный
разделы памяти. Автором были реализованы все три подхода и было
установлено, что они не имеют существенных отличий по скорости
выполнения. Было выбрано использование текстуры, поскольку такая
реализация проще всего расширяется до метода “четырех русских”,
который будет рассмотрен далее.
Другим важным параметром, влияющим на производительность,
является конфигурация запуска ядра вычитания строк. Очевидно, что
данное ядро является ограниченным по памяти. Для выбора опти-
мальных конфигураций используется предварительный тест произ-
водительности на случайных данных, перебирающий все возможные
конфигурации запуска с числом потоков, кратным половине ворпа для
матриц разного размера. Результаты калибровки согласуются с резуль-
татами теоретических расчетов занятости блоков ГП по [13]. Данный
тест также определяет оптимальную форму блока для необходимого
числа потоков в нем и учитывает особенности формы самой обрабаты-
ваемой матрицы. Это позволяет увеличить производительность в 1,5–2
раза по сравнению с ручным выбором конфигурации. Время работы
калибровки в результаты работы авторской реализации не включено,
поскольку ее необходимо провести всего один раз для конкретной ви-
деокарты.
Метод “четырех русских” для обращения
(
англ
. M4RI) является
относительно простым расширением метода Гаусса. Алгоритм был
представлен в [1] и детально рассмотрен в [3]. Его основную идею
можно пояснить с помощью рис. 1.
После того как был найден и установлен на место ведущий эле-
мент (шаг 1), делается попытка привести к каноническому виду по
строкам подматрицу из
l
∙
k
строк, начиная с текущей, где
l
и
k
—
параметры алгоритма (шаг 2). При этом формируется единичная ма-
трица размера
k
×
k
с использованием обычного метода Гаусса. Если
данная операция успешна, то формируется полный набор из всех
2
k
линейных комбинаций данных строк, что можно эффективно сделать
с использованием кодов Грея (шаг 3). После этого проводится обнуле-
ние сразу
k
столбцов оставшейся части матрицы за один проход (шаг
4).
В [3] предлагаются значения параметров
l
= 3
и
k
= log
2
m
для
матрицы размера
m
×
n
; следовательно, вероятность успеха на шаге
54
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2013. № 1
