Умножение матриц - это простая задача для всех, кто занимается компьютерными науками. Насколько это может быть сложно 😏 ? Это просто вопрос создания 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.

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

Вдохновением для этой статьи послужила лекция профессора Чарльза Э. Лейзерсона о проектировании производительности