Почему умножение матриц моего Штрассена медленное?
Я написал две программы умножения матриц на C ++: Regular MM (источник), и М.М. Штрассена (источник), оба из которых работают с квадратными матрицами размером 2 ^ k x 2 ^ k (другими словами, квадратные матрицы четного размера).
Результаты просто ужасны. Для матрицы 1024 x 1024, обычная MM занимает 46.381 sec, в то время как ММ Штрассен берет 1484.303 sec (25 minutes !!!!).
Я попытался сделать код максимально простым. Другие примеры MM Штрассена, найденные в Интернете, не сильно отличаются от моего кода. Одна проблема с кодом Штрассена очевидна — у меня нет предельной точки, которая переключается на обычный MM.
Какие другие проблемы ММ код моего Штрассена имеет ???
Спасибо !
Прямые ссылки на источники
http://pastebin.com/HqHtFpq9
http://pastebin.com/USRQ5tuy
Edit1.
Кулак, много полезных советов. Спасибо, что нашли время и поделились знаниями.
Я внес изменения (сохранил весь мой код), добавил точку отсечения.
ММ матрицы 2048х2048, с отсечкой 512 уже дает хорошие результаты.
Обычный ММ: 191,49 с
ММ Штрассена: 112,179 с
Значительное улучшение.
Результаты были получены на доисторическом Lenovo X61 TabletPC с процессором Intel Centrino с использованием Visual Studio 2012.
Я сделаю больше проверок (чтобы убедиться, что получил правильные результаты) и опубликую результаты.
Решение
Одна проблема с кодом Штрассена очевидна — у меня нет предела,
который переключается на обычную ММ.
Справедливо сказать, что повторение до 1 балла является основной проблемой (если не всей). Попытка угадать другие узкие места производительности без решения этой проблемы почти спорна из-за огромного снижения производительности, которое она приносит. (Другими словами, вы сравниваете яблоки с апельсинами.)
Как обсуждалось в комментариях, выравнивание кэша может оказать влияние, но не в этом масштабе. Более того, выравнивание кэша, скорее всего, повредит обычному алгоритму больше, чем алгоритму Штрассена, поскольку последний не обращает внимания на кэш.
void strassen(int **a, int **b, int **c, int tam) {
// trivial case: when the matrix is 1 X 1:
if (tam == 1) {
c[0][0] = a[0][0] * b[0][0];
return;
}
Это слишком мало. Хотя алгоритм Штрассена имеет меньшую сложность, он имеет гораздо большую константу Big-O. Например, у вас есть накладные расходы на вызовы функций вплоть до 1 элемента.
Это аналогично использованию слияния или быстрой сортировки и повторного использования вплоть до одного элемента. Чтобы быть эффективным, вам нужно остановить рекурсию, когда размер станет маленьким, и прибегнуть к классическому алгоритму.
В быстрой сортировке / слиянии вы бы вернулись к низким накладным расходам O(n^2) вставка или выбор сортировки. Здесь вы вернетесь к нормальному O(n^3) матрица умножается.
Порог, к которому вы прибегаете к классическому алгоритму, должен быть настраиваемым порогом, который, вероятно, будет варьироваться в зависимости от аппаратного обеспечения и способности компилятора оптимизировать код.
Для чего-то вроде умножения Штрассена, где преимущество только O(2.8074) по классике O(n^3)Не удивляйтесь, если этот порог окажется очень высоким. (тысячи элементов?)
В некоторых приложениях может быть много алгоритмов, каждый со снижающейся сложностью, но увеличивающий Big-O. В результате несколько алгоритмов становятся оптимальными при разных размерах.
Большое целочисленное умножение — известный пример этого:
- Умножение начальной школы: O (N ^ 2) оптимально для < ~ 100 цифр *
- Каратсуба Умножение: O (N ^ 1,585) быстрее чем выше на ~ 100 цифр *
- Toom-Cook 3-way: O (N ^ 1,465) быстрее чем Карацуба на ~ 3000 цифр *
- БПФ с плавающей точкой: O (> N log (N)) быстрее чем Карацуба / Тоом-3 на ~ 700 цифр *
- Алгоритм Шёнхаге – Штрассена (SSA): O (N log (n) loglog (n)) быстрее, чем FFT ~ миллиард цифр *
- Числово-теоретическое преобразование с фиксированной шириной: O (N log (n) быстрее, чем SSA на несколько миллиардов цифр? *
* Обратите внимание, что эти примерные пороговые значения являются приблизительными и могут сильно различаться — часто более чем в 10 раз.
Другие решения
Таким образом, может быть и больше проблем, но ваша первая проблема заключается в том, что вы используете массивы указателей на массивы. А поскольку вы используете размеры массива, равные степени 2, это особенно сильно сказывается на производительности, когда вы выделяете элементы непрерывно и используете целочисленное деление, чтобы сложить длинный массив чисел в строки.
Во всяком случае, это мое первое предположение о проблеме. Как я уже сказал, их может быть больше, и я добавлю к этому ответу, когда узнаю их.
Редактировать: Это, вероятно, только вносит небольшой вклад в проблему. Проблема, вероятно, одна Лучиан Григоре относится к вовлечению проблемы конкуренции строк кэша с полномочиями двух.
Я проверил, что мое беспокойство справедливо для наивного алгоритма. Время наивного алгоритма сокращается почти на 50%, если массив является смежным. Вот код для этого (с использованием класса SquareMatrix, который зависит от C ++ 11) на pastebin.