Можно почитать
zealint.ru/fast-matrix-multiplication-results.html.
Позволю себе небольшую цитату из этой записи:
«Во-первых, сначала я написал самую тупую версию, которая умножает строку на столбец в тройном цикле (C [ i ] [ j ] += A [ i ] [ k ] * B [ k ] [ j ], циклы идут в порядке i-j-k). Это и были те самые 800 с. (надо же с чего-то начинать). Здесь же можно поиграть перестановкой циклов местами: самое быстрое получается, если выбрать i-k-j, в этом случае все три матрицы сканируются по строкам. Такая версия уже укладывалась в 3 минуты (что почти в 5 раз быстрее). Можно просто транспонировать вторую матрицу прямо на вводе и поменять местами индексы k и j при обращении к матрице B. Это ещё быстрее (150 с.). Что ещё можно сделать без вмешательства ассемблера? — поменять int (32 бита) на short (16 бит) для входящих матриц и скомпилировать родным для процессора компилятором с опциями максимального ускорения. Это дает 94 секунды. До 55 секунд можно дойти, если развернуть матрицы в массив. Тогда будут получаться записи вида A [ i * n + k ], но все такие умножения нужно либо вынести за внутренний цикл, либо вообще заменить сложением указателей с числом n в нужных местах. В этом случае компилятор оптимизирует гораздо лучше. Все, без ассемблера можно сделать только ещё одну вещь: разбить матрицу на блоки, которые помещаются в кэш, но я решил, что сделаю это сразу на ассемблере.»
