Умножение матриц - это простая задача для всех, кто занимается компьютерными науками. Насколько это может быть сложно 😏 ? Это просто вопрос создания 2D-массивов, заполнения их данными и, наконец, вложенного цикла. Вы были бы удивлены, узнав, что то, как вы реализуете матричное умножение, существенно влияет на прошедшее время.
Код на языке C для умножения матрицы
Вы можете скомпилировать и запустить его, используя следующие команды.
gcc -o matrix MatrixMultiplication.c ./martix
Вот как большинство из нас реализует умножение матриц. Какие изменения мы можем внести? Можем ли мы изменить порядок вложенных циклов? Конечно можем! Нет правила, говорящего, что циклы должны быть в порядке i → j → k (хотя это то, что мы делаем большую часть времени 😄). Вы можете написать цикл следующим образом и все равно получить правильный результат (порядок не имеет значения).
for (int k = 0; k < n; k++) { for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { C[i][j] += A[i][k] * B[k][j]; } } }
Интересный вопрос: повлияет ли это на производительность?
Давайте разберемся!
Эксперимент
Я изменил порядок вложенных циклов и выполнил по три итерации для каждой комбинации. Результаты приведены ниже.
Разве это не потрясающе? Просто изменив порядок вложенных циклов, вы можете сократить время выполнения с 279,78 секунды (худшее) до 34,78 секунды (лучшее). Вложенный цикл порядка [i, k, j] выполняется почти в 8 раз быстрее, чем [k, j, i]. ПОЧЕМУ?
Расположение кеша
Чтобы понять наши результаты, нам нужно знать, как данные на самом деле хранятся и к ним осуществляется доступ. В C двумерные массивы хранятся в ОЗУ в порядке старших строк (в отличие от Фортрана, где двумерные массивы хранятся в порядке старших столбцов). Порядок по строкам просто означает, что последовательные элементы строки располагаются рядом друг с другом в памяти, тогда как в порядке по столбцам последовательные элементы столбца находятся в памяти рядом друг с другом. Следующая диаграмма поможет лучше понять.
Обрабатываемые данные загружаются в кэш из оперативной памяти. Кэш-память считывает данные на одну строку кэша за раз из ОЗУ. Предположим, что размер строки кэша составляет 64 байта, хотя нам нужно получить доступ к переменной целочисленного типа, которая составляет всего 4 байта, кеш должен загрузить все 64 байта.
Строки кэша, к которым ранее осуществлялся доступ, хранятся в кэш-памяти. Когда процессору требуется доступ к некоторым данным, система сначала проверяет, доступен ли этот конкретный фрагмент данных в кэше. Если он доступен, мы называем это попаданием в кеш. Если это не так, это называется промахом в кэше, и данные должны быть загружены из ОЗУ. Попадания в кэш обеспечивают более быстрый доступ к данным (что тривиально, поскольку для загрузки данных из ОЗУ требуется больше времени).
Теперь мы можем легко проанализировать наши результаты. Рассмотрим порядок i, j, k.
Если i = 1, j = 2 и k = 0..n, нам нужно получить доступ ко всей 2-й строке Matrix A и ко всему 3-му столбцу Matrix B. Если вы посмотрите на макет в памяти на диаграмме, станет ясно, что доступ ко второй строке матрицы A обеспечивает хорошую пространственную локальность, поскольку все данные, которые нам нужны, находятся в одной строке кэша. Однако в Матрице B нам нужен доступ к разным строкам кэша для каждого значения столбца, что приведет к более высокому уровню пропусков кеширования.
Аналогично, если мы рассмотрим порядок i, k, j (предположим, что i = 1, k = 2 и j = 0..n)
мы получаем хорошую пространственную локальность во всех трех случаях, что снизило бы частоту промахов кеша.
Мы можем рассчитать частоту промахов кеша, используя следующую команду.
valgrind --tool=cachegrind ./matrix
[Обработка может занять некоторое время, в зависимости от оборудования вашей системы и размера матрицы, проявите терпение 😄 ]
Следующая таблица показывает частоту промахов кэша последнего уровня.
Из этой таблицы очевидно, что существует сильная корреляция между частотой промахов кэша последнего уровня и прошедшим временем. [j, k, i] и [k, j, i], которые имеют наивысшую частоту промахов кэш-памяти 3,6%, также имеют наибольшее время работы ~ 279 секунд. Точно так же [i, k, j] и [k, i, j], которые имеют наименьшую частоту промахов кэша 0,2%, также имеют наименьшее время работы ~ 35 секунд.
Вы можете задаться вопросом, что произойдет, если мы будем использовать флаги оптимизации компилятора. Будет ли он сам позаботиться о местонахождении кеша? Ниже приведены результаты, полученные при компиляции с флагом оптимизации -O3.
Таким образом, очевидно, что вы не можете полагаться на компилятор и должны учитывать пространственную локальность кеша при кодировании.
Вдохновением для этой статьи послужила лекция профессора Чарльза Э. Лейзерсона о проектировании производительности