Приведение плотных матриц с элементами из GF(2) к ступенчатому виду на платформе NVIDIA CUDA - page 7

Рис. 2. Схема реализации
стремится минимизировать число ситуаций, где используется такая
поддержка, поскольку она более требовательна к и без того занятой
полосе пропускания глобальной памяти.
Таблица кодов Грея вычисляется заранее на хосте для максималь-
ного поддерживаемого
k
и хранится в константной памяти. Используя
рефлективное свойство кодов Грея, хранится только половина табли-
цы, а построение комбинаций осуществляется в два параллельных
прохода. Такой метод оказывается на 10–40% быстрее генерации в
один полный проход. Комбинации хранятся (как и в реализации метода
Гаусса) в общей памяти, обращение к которой на чтение осуществля-
ется через текстуру. Хотя коды Грея могут быть относительно легко
вычислены самим ядром, использование готовых таблиц оказывается
быстрее. Для всех поддерживаемых
k
компилируются варианты ядра
с полностью развернутым циклом.
Итоговая схема реализации алгоритма приведена на рис. 2.
Анализ результатов.
Тестирование проводилось на машине с про-
цессором Core i7 920 и видеокартой GeForce GTX 580 под управле-
нием ОС Linux. Видеокарта на данной системе не использовалась для
вывода изображения, что значительно уменьшило разброс значений
между несколькими прогонами. Для сравнения была использована би-
блиотека M4RI [8] версии 20110715, собранная с поддержкой много-
поточности, которая широко применяется и обладает максимальной
производительностью на ЦП для большинства практических случаев
[9]. Тестировались две реализации алгоритма приведения матрицы к
ступенчатому виду: метод “четырех русских” (m4ri) c автоматическим
56
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2013. № 1
1,2,3,4,5,6 8,9,10,11
Powered by FlippingBook