SIMD-эксплуатация реализации алгоритма Петерсона и Моникса Ланцоша над полем с двумя элементами
(Этот вопрос, вероятно, заигрывает с правилом "без рекомендаций по программному обеспечению"; я понимаю, почему оно может быть закрыто).
В своей работе F_2 Lanczos вновь, Петерсон и Монико дают версию алгоритма Ланцоша для нахождения подпространства ядра линейного отображения над Z/2Z. Если мое беглое прочтение их статьи верно (независимо от того, является ли это вопросом, явно не являющимся вопросом для SO), представленный алгоритм требует ряда итераций, которые масштабируются обратно пропорционально размеру слова используемой машины. Авторы реализовали алгоритм доказательства концепции с 64-битным размером слова.
Существует ли общедоступная реализация этого алгоритма, использующая широкие слова SIMD для (потенциально значительного) ускорения?
1 ответ
Существующая реализация была бы рекомендацией программного обеспечения. Более интересный вопрос: "Можно ли использовать SIMD для ускорения работы этого алгоритма?" С моего взгляда на бумагу кажется, что SIMD - это именно то, что они описывают ("Мы разделим 64-битное машинное слово x на восемь подслов..., где каждое... - 8-битное слово"), так что если Авторская реализация где-то общедоступна, ответ - "да", потому что они уже используют ее. Если бы этот алгоритм был написан на C/C++ или что-то в этом роде, оптимизирующий компилятор, вероятно, очень хорошо справился бы с его векторизацией с помощью SIMD, даже не указав вручную, как разбивать регистры (это можно проверить, посмотрев сборку). Возможно, было бы предпочтительнее реализовать язык высокого уровня, не разбивая регистры вручную, потому что тогда компилятор мог бы оптимизировать его под любой размер слова целевой машины.