уравнений. Линеаризация (в определенных рамках) позволяет исполь-
зовать данные методы и для нелинейных систем. Программные ре-
шения задач линейной алгебры в поле действительных чисел разра-
батываются очень давно (например, [4]). Свою реализацию стандарта
BLAS имеет и платформа NVIDIA CUDA — cuBLAS [5].
Для матриц с элементами в конечных числовых полях задача при-
ведения к ступенчатому виду встречается весьма часто, например в те-
ории чисел при реализации современных алгоритмов факторизации —
разложении больших чисел на множители (алгоритмов непрерывных
дробей, квадратичного решета и решета числового поля). В крипто-
графии подобные методы необходимы при определении начального
заполнения линейного регистра сдвига и в других задачах. Для обра-
ботки матриц с элементами из GF(2) существует несколько общедо-
ступных программных решений, рассмотренных, например, в работах
[7, 8, 10, 11]. Все указанные решения используют для вычислений
один или несколько центральных процессоров. В данной работе пред-
ставлена авторская реализация на платформе NVIDIA CUDA метода
“четырех русских” приведения матрицы с элементами из GF(2) к сту-
пенчатому виду по строкам. Данная платформа хорошо зарекомендо-
вала себя при решении подобных вычислительных задач, обладающих
большим потенциалом для применения высокопараллельных алгорит-
мов.
Первая попытка реализации указанного метода на данной плат-
форме была предпринята в [14], но результаты не были представле-
ны. Автору известна единственная успешная работа [6], связанная с
решением рассматриваемой задачи, однако реализация, рассматривае-
мая в данной статье, обладает значительно лучшей производительно-
стью, позволяя обработать матрицу порядка
2
17
за 138 с на видеокарте
GeForce GTX 580.
Реализация метода.
Платформа NVIDIA CUDA предоставляет на-
бор инструментов для написания высокопараллельных программ для
исполнения на современных видеокартах NVIDIA. Программы могут
быть написаны как на C-подобном языке, так и на ассемблере. Крат-
ко сформулируем основные понятия и принципы устройства данной
системы; детальное описание платформы дано в [12].
Графический процессор (ГП) обладает собственными вычисли-
тельными блоками, построенными по архитектуре SIMT (Single
Instruction–Multiple Threads), и памятью, имеющей несколько обла-
стей и способов доступа. Его работа осуществляется параллельно с
работой центрального процессора (ЦП). Подпрограмма для выпол-
нения на ГП называется
ядром
и выполняется много раз каждым из
потоков, число которых задается
конфигурацией выполнения
. Потоки
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2013. № 1
51
