Точка кроссовера: алгоритм Штрассена

Question

Привет, ребята, я немного искал, и, судя по всему, нет ни одного уместного вопроса. Я хочу знать, какова оптимальная точка пересечения, при которой алгоритм Штрассена должен остановить рекурсию и применить умножение с точки зрения эффективности.

Я знаю, что это тесно связано с конкретной реализацией и оборудованием, но для общего случая должны быть какие-то рекомендации или некоторые экспериментальные результаты.

Поиск в Интернете и опрос некоторых людей, которые склонны думать, что это

n = 64; 

или

 n = 32;

Может ли кто-нибудь подтвердить / отклонить эти результаты?

Answer 1

На моем двухъядерном Mac Pro 2.66 с использованием [моя реализация] [1] кроссовер такой же маленький, как n = 16. На самом деле моя реализация на способ быстрее, чем обычный алгоритм для больших Матрицы - я не уверен, почему - я думаю, что это более кеш-памяти, так как это фокусируется на небольших локализованных данных. На самом деле, я собираюсь опубликовать вопрос об этом.

http://ezekiel.vancouver.wsu.edu/~cs330/lectures/linear_algebra/mm/mm.c

Answer 2

Это должно быть настроено для каждой машины (немного как ATLAS). Оптимизация такого рода окупается за довольно большие матрицы: если вы сами ее кодируете и сравниваете, например, с. реализация поставщика BLAS, то вы найдете довольно большое п.

Требования к памяти для алгоритма Штрассена также есть что взвесить.

Answer 3

После многих испытаний я пришел к выводу, что по крайней мере для моего процессора оптимальная точка пересечения, при которой алгоритм Штрассена равен n = 128.

Мой процессор: Intel Core i5-430M. Кроме того, что интересно для четырехпоточного процессора, моя реализация работала немного лучше для numberOfProcesses = 8, чем numberOfProcesses = 4. Я понятия не имею, как или почему это произошло. Я предполагаю, что из-за большего количества коммуникаций по каналам это приведет к большим издержкам, и, поскольку они не могут работать все одновременно, это определенно будет немного медленнее. Видимо я был не прав. Если кто-нибудь может объяснить это, кстати, пожалуйста, напишите строку, просто для записи.

Спасибо.