Почему при умножении массива 2048х2048 наблюдается огромный спад производительности?

Question

Я делаю некоторые тесты умножения матриц, как упоминалось ранее в Почему MATLAB так быстр в умножении матриц?

Теперь у меня есть еще одна проблема, при умножении двух матриц 2048x2048, есть большая разница между C # и другими. Когда я пытаюсь умножить только 2047x2047 матриц, это кажется нормальным. Также добавлены некоторые другие для сравнения.

1024x1024 - 10 секунд.

1027x1027 - 10 секунд.

2047x2047 - 90 секунд.

2048x2048 - 300 секунд.

2049x2049 - 91 секунда. (Обновление)

2500x2500 - 166 секунд

Это разница в три с половиной минуты для случая 2k на 2k.

с использованием 2dim массивов

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

Answer 1

Вероятно, это связано с конфликтами в кеше L2.

Отсутствие кэша на matice1 не является проблемой, поскольку к ним обращаются последовательно. Однако для matice2, если в L2 помещается полный столбец (т. Е. При доступе к matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... и т. Д., Ничего не выселяется), чем проблема с также отсутствует кеш с matice2.

Теперь, чтобы глубже понять, как работают кэши, если адрес вашей переменной в байтах равен X, то строка для нее будет (X >> 6) & (L - 1). Где L - общее количество строк кэша в вашем кэше. L всегда степень 2. Шесть получается из того факта, что 2 ^ 6 == 64 байта - это стандартный размер строки кэша.

Теперь, что это значит? Ну, это означает, что если у меня есть адрес X и адрес Y и (X >> 6) - (Y >> 6) делится на L (т. Е. Некоторая большая степень 2), они будут храниться в одной и той же строке кэша.

Теперь вернемся к вашей проблеме: в чем разница между 2048 и 2049,

когда ваш размер 2048:

если вы возьмете & matice2 [x, k] и & matice2 [y, k], разница (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) будет делиться на 2048 * 4 (размер поплавка). Так что большая сила 2.

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

Если размер равен 2049, то разница составляет 2049 * 4, что не является степенью 2, поэтому у вас будет меньше конфликтов, и ваш столбец будет безопасно помещаться в вашем кэше.

Теперь, чтобы проверить эту теорию, есть пара вещей, которые вы можете сделать:

Выделите ваш массив matice2, как этот matice2 [razmor, 4096], и запустите с razmor = 1024, 1025 или любым другим размером, и вы должны увидеть очень плохую производительность по сравнению с тем, что было раньше. Это потому, что вы принудительно выравниваете все столбцы, чтобы конфликтовать друг с другом.

Затем попробуйте matice2 [razmor, 4097] и запустите его с любым размером, и вы увидите гораздо лучшую производительность.

Answer 2

Вероятно, эффект кеширования. С размерами матрицы, которые имеют большую степень двойки, и размером кеша, который также является степенью двойки, вы можете использовать только небольшую часть кеша L1, что сильно замедляет работу. Умножение наивных матриц обычно ограничивается необходимостью извлечения данных в кеш. Оптимизированные алгоритмы с использованием тайлинга (или алгоритмов, не обращающих внимания на кэш) фокусируются на более эффективном использовании кэша L1.

Если вы рассчитываете другие пары (2 ^ n-1,2 ^ n), я ожидаю, что вы увидите похожие эффекты.

Чтобы объяснить более подробно, во внутреннем цикле, где вы обращаетесь к matice2 [m, k], вполне вероятно, что matice2 [m, k] и matice2 [m + 1, k] смещены друг от друга на 2048 * sizeof (float) и, таким образом, отображается на тот же индекс в кэше L1. С N-way ассоциативным кешем у вас обычно будет 1-8 ячеек для всех этих кешей. Таким образом, почти все эти обращения будут вызывать вытеснение кеша L1 и выборку данных из более медленного кеша или основной памяти.

Answer 3

Это может иметь отношение к размеру вашего кэша процессора.Если 2 строки матрицы матрицы не помещаются, то вы потеряете время на обмен элементов из ОЗУ.Дополнительных 4095 элементов может быть достаточно для предотвращения подгонки строк.

В вашем случае 2 строки для 2047 2-мерных матриц находятся в пределах 16 КБ памяти (при условии 32-битных типов).Например, если у вас есть кэш L1 (ближайший к процессору на шине) объемом 64 КБ, то вы можете поместить в кэш одновременно не менее 4 строк (из 2047 * 32).С более длинными строками, если требуется заполнение, при котором пары строк превышают 16 КБ, все становится грязным.Кроме того, каждый раз, когда вы «пропускаете» кеш, обмен данными из другого кеша или основной памяти приводит к задержкам.

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

Answer 4

Луи Бренди написал два поста в блоге, анализируя именно эту проблему:

Больше сумасшествия кеша и Вычислительная производительность - тематическое исследование для начинающих с некоторыми интересными статистическими данными и попытками объяснить поведение более подробно, оно действительно сводится к ограничениям размера кеша.

Answer 5

Учитывая, что время уменьшается при больших размерах, не будет ли вероятнее конфликтов кэша, особенно с степенями 2 для проблемных размеров матриц?Я не эксперт по вопросам кэширования, но отлично разбираюсь в проблемах производительности, связанных с кэшированием здесь .

Answer 6

Кэширование псевдонимов

Или кэш-очистка , если я могу пометить термин.

Кэши работают, индексируя с битами младшего разряда и маркируя с битами старшего разряда.

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

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

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

Поскольку кэш-память значительно быстрее, чем DRAM (в основном благодаряБыть на фишке) Скорость попаданий - это все.

Answer 7

Когда вы обращаетесь к массиву matice2 по вертикали, он будет выгружен из кеша намного больше. Если вы зеркалируете массив по диагонали, чтобы вы могли получить к нему доступ, используя [k,m] вместо [m,k], код будет выполняться намного быстрее.

Я проверил это на матрицах 1024x1024, и это примерно в два раза быстрее. Для матриц 2048x2048 это примерно в десять раз быстрее.

Answer 8

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

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

Answer 9

Эффективное использование иерархии кеша очень важно.Вы должны убедиться, что многомерные массивы имеют данные в хорошем порядке, чего можно достичь с помощью tiling .Для этого вам нужно сохранить двумерный массив как одномерный массив вместе с механизмом индексации.Проблема с традиционным методом состоит в том, что хотя два соседних элемента массива, которые находятся в одной строке, находятся рядом друг с другом в памяти, два соседних элемента в одном столбце будут разделены W элементами в памяти, где W - количество столбцов.Черепица может привести к разнице в производительности в 10 раз.

Answer 10

Я подозреваю, что это результат того, что называется " Sequential Flooding ". Дело в том, что вы пытаетесь перебрать список объектов, который немного больше размера кэша, поэтому каждый отдельный запрос к списку (массиву) должен выполняться из оперативной памяти, и вы не получите ни одного кэша. удар.

В вашем случае вы перебираете свои массивы по 2048 индексам 2048 раз, но у вас есть место только для 2047 (возможно, из-за некоторых издержек из структуры массива), поэтому каждый раз, когда вы получаете доступ к массиву pos, он должен получить этот массив поз от оперативной памяти. Затем он сохраняется в кеше, но перед повторным использованием сбрасывается. Таким образом, кеш по сути бесполезен, что приводит к гораздо большему времени выполнения.