Модификация алгоритма Копперсмита умножения матриц над GF(2)

Черепнев, М.А.

Автор: Черепнев М.А.
Журнал: International Journal of Open Information Technologies
Том: 7
Номер: 10
Год издания: 2019
Издательство: Лаборатория Открытых Информационных Технологий факультета ВМК МГУ им. М.В. Ломоносова
Местоположение издательства: Москва
Первая страница: 9
Последняя страница: 13
Аннотация: В последнее время все чаще требуется применение алгоритмов эффективно работающих с машинными словами и таких, что основная работа может быть произведена в кэше процессора, то есть время на перезапись меньше. Важно отметить, что объем кэша выпускаемых процессоров быстро растет. В данной работе предлагается новая модификация алгоритма Копперсмита для умножения блочных векторов, ширина которых равна длине машинного слова, друг на друга и на квадратные матрицы. Мы рассматриваем случай, когда коэффициенты лежат в поле из двух элементов. Данные алгоритмы относится к числу блочных алгоритмов, в которых операции производятся с машинными словами, то есть с каждым из 64 битов одновременно. Полученные результаты могут быть применены и к булевым матрицам без значительных изменений. Поскольку данные алгоритмы относится к числу алгоритмов с предвычислениями, то эти оценки представляют практический интерес при использовании процессоров с увеличенным размером кэш памяти первого уровня. Рассмотренные в данной статье алгоритмы дают увеличение скорости пропорционально логарифму объема кэша первого уровня. Для применения в задачах, где данные матричные операции являются базовыми (например, задача целой факторизации) это может оказаться существенным.
Добавил в систему: Черепнев Михаил Алексеевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

Модификация алгоритма Копперсмита умножения матриц над GF(2)статья

Прикрепленные файлы