Оптимизированное умножение матриц в C

Получение этого права может быть нетривиальным. Одна оптимизация, которая имеет особое значение для больших матриц, - это мозаичное умножение, чтобы хранить данные в кеше. Однажды я измерил 12-кратную разницу в производительности при этом, но я специально выбрал размер матрицы, которая потребляла кратные объемы моего кеша (около 1997 года, поэтому кеш был маленьким).

Существует много литературы по предмет. Отправной точкой является:

http://en.wikipedia.org/wiki/Loop_tiling

Для более глубокого изучения могут быть полезны следующие ссылки, особенно книги Банерджи:

[Ban93] Банерджи, Утпал, Преобразования петель для реструктурирующих компиляторов: основы, Kluwer Academic Publishers, Norwell, MA, 1993.

[Ban94] Банерджи, Утпал, Loop Parallelization, Kluwer Academic Publishers, Norwell, MA, 1994.

[BGS93] Бэкон, Дэвид Ф., Сьюзан Л. Грэм и Оливер Шарп, Преобразования компилятора для высокопроизводительных вычислений, Отдел компьютерных наук, Калифорнийский университет, Беркли, Калифорния, Технический отчет № UCB / CSD-93 -781.

[LRW91] Лам, Моника С., Эдвард Э. Ротберг и Майкл Э. Вольф. Производительность кэша и оптимизация заблокированных алгоритмов, на 4-й Международной конференции по архитектурной поддержке языков программирования, состоявшейся в Санта-Кларе, Калифорния, апрель 1991 г., 63-74.

[LW91] Лам, Моника С. и Майкл Э. Вольф. Теория преобразования цикла и алгоритм для максимального увеличения параллелизма, В IEEE Transactions on Parallel and Distributed Systems, 1991, 2 (4): 452-471.

[PW86] Падуя, Дэвид А., Майкл Дж. Вулф, Advanced Compiler Optimizations for Supercomputers, In Communications of the ACM, 29 (12): 1184-1201, 1986.

[Wolfe89] Вулф, Майкл Дж. Оптимизация суперкомпиляторов для суперкомпьютеров, MIT Press, Кембридж, Массачусетс, 1989.

[Wolfe96] Вулф, Майкл Дж., Высокопроизводительные компиляторы для параллельных вычислений, Аддисон-Уэсли, Калифорния, 1996.

ВНИМАНИЕ: у вас есть ОШИБКА во второй реализации

for (f = 0; f < i; f++) {
    for (co = 0; co < i; co++) {
        MatrixB[f][co] = MatrixB[co][f];
    }
}

Когда вы делаете f = 0, c = 1

        MatrixB[0][1] = MatrixB[1][0];

вы перезаписываете MatrixB [0] [1] и теряете это значение! Когда цикл достигает f = 1, c = 0

        MatrixB[1][0] = MatrixB[0][1];

, скопированное значение будет тем же, что уже было.

Как и вы, я использовал только определенные вами классы ( Component , Container и т. Д.) Косвенно, то есть в уже производной форме (каждый System.Windows. Forms.Control происходит от Component и т. Д.). Так что мне больше нечего добавить. При добавлении свойств в настраиваемые элементы управления я почти всегда использую многие из классов DefaultValueAttribute , DesignerSerializationVisibilityAttribute и другие классы * Attribute . Но это'

Насколько большие улучшения вы получите, будет зависеть от:

1. размера кэша
2. размера строки кэша
3. степени ассоциативности кэша

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

Просто попробуйте (но это будет иметь значение только для больших матриц): отделите логику сложения от логики умножения во внутреннем цикле следующим образом:

for (k = 0; k < i; k++)
{
    int sums[i];//I know this size declaration is illegal in C. consider 
            //this pseudo-code.
    for (l = 0; l < i; l++)
        sums[l] = MatrixA[j][l]*MatrixB[k][l];

    int suma = 0;
    for(int s = 0; s < i; s++)
       suma += sums[s];
}

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

Это это просто моя логика.

Не могли бы вы опубликовать данные, сравнивающие ваши 2 подхода для различных размеров матриц? Возможно, ваши ожидания нереалистичны, и ваша вторая версия работает быстрее, но вы еще не провели измерения.

Не забудьте при измерении времени выполнения включить время транспонирования матрицы B.

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

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

То, что каждый программист должен знать о памяти (pdf ссылка) Ульриха Дреппера, имеет много хороших идей об эффективности использования памяти, но, в частности, он использует умножение матриц как пример того, как знание о памяти и использование этих знаний может ускорить этот процесс. Посмотрите приложение A.1 в его статье и прочтите раздел 6.2.1. Из таблицы 6.2 в статье видно, что для матрицы 1000x1000 он может получить время работы в 10% от наивной реализации.

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