Повышение эффективности стандартного алгоритма умножения матриц?

Question

Как повысить эффективность стандартного алгоритма умножения матриц?

Основная операция, включенная в этот подход: C[i][j]+=A[i][p]*B[p][j]

Что можно сделать для повышения эффективности алгоритма?

Answer 1

Возможно, вы захотите взглянуть на использование библиотеки BLAS (подпрограмма базовой линейной алгебры), в частности, Intel предлагает свои MKL здесь , у AMD их ACML здесь , а также есть (с открытым исходным кодом) Goto BLAS здесь .

Ядром (плотной) матрично-матричного умножения будет вызов ?GEMM, где ? указывает тип с плавающей запятой. Например, DGEMM вызовет подпрограмму double.

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

Если вы действительно хотите сами написать код, тогда вы можете рассмотреть следующее:

1. Используйте "векторные" инструкции. SSE, SSE2..4 инструкции широко поддерживаются, некоторые более новые CPU также будут поддерживать AVX инструкции.
2. Развертывание вложенного цикла для максимизации отношения операций с плавающей запятой к операциям загрузки / сохранения.
3. Блочные алгоритмы для обеспечения эффективного использования кэша.
4. Многопоточность.

Эта ссылка может дать вам представление о текущем состоянии вещей:

Высокопроизводительная реализация BLAS уровня 3 - K Goto.

Надеюсь, это поможет.

Answer 2

Ну, есть Алгоритм Штрассена , который, в зависимости от размера вашей матрицы, немного быстрее, чем стандартный алгоритм, который вы перечислили. Конечно, есть еще более быстрые алгоритмы , но они не так просты в реализации.

Стандартный алгоритм O (N ^ 3), Алгоритм Штрассена O (N ^ 2.8), и Медник-Виноград - O (N ^ 2.3)

Answer 3

1. Блокировка кэша - убедитесь, что вы правильно используете и повторно используете значения в кэше
2. Лучший алгоритм - способ умножения матриц "по определению" не является оптимальным, посмотрите алгоритм Штрассена
3. Распараллеливание - если ваша машина имеет более одного ядра и / или процессора, вы можете разделить и победить
4. SIMD - воспользуйтесь SSE векторные инструкции в современных архитектурах процессоров
5. GPGPU - современные графические процессоры оптимизированы для выполнения подобных задач.Посмотрите на CUDA и OpenCL .

Обратите внимание, что использование этих методов не гарантирует лучшую производительность.Требуется много настроек для значительного ускорения.Много денег уходит на то, чтобы понять, как быстро умножить матрицы, чтобы не было недостатка в журнальных статьях на эту тему.

Answer 4

Если вопрос касается многократного умножения матриц - M1 x M2 x ... x Mn - тогда существует другой метод оптимизации, основанный на динамическом программировании, который является своего рода другой игрой в мяч.Обратите внимание, что это не относится к повышению эффективности умножения двух матриц;однако, если вы умножаете три или более матриц попарно, то вы можете оптимизировать на еще более высоком уровне.Просто подумал, что я брошу этот ответ в кучу, чтобы округлить информацию.

Answer 5

Я бы предложил прочитать главу 1 из Голуб и Ван Лоан , в которой рассматривается именно этот вопрос.