Почему при умножении массива 2048x2048 по сравнению с умножением 2047x2047 достигается огромное снижение производительности?

127

Я провожу сравнительный анализ умножения матриц, как упоминалось ранее в статье Почему 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;
   }
 }
волк
источник
23
Это был бы отличный вопрос на экзамене для продвинутого уровня программирования на C или класса дизайна ОС ;-)
Дана Разумная
Вы пробовали тестировать как многомерные [,], так и зубчатые [] [] массивы, а также 32- и 64-битные массивы? Я тестировал только несколько раз, но зазубренность казалась более соответствующей вашим результатам, но зазубренные 64-битные были высокими, я не знаю, есть ли в jit какие-либо эвристики, которые применимы к этой ситуации, или его кеш связан с ранее предложенным. Если вам нужно решение GPGPU, есть research.microsoft.com/en-us/projects/accelerator. который должен быть конкурентоспособным со временем в вашем другом посте.
Крис
Несколько наивный вопрос, а сколько операций (сложение / умножение) задействовано в умножении двух квадратных матриц?
Nick T
такая

Ответы:

61

Вероятно, это связано с конфликтами в вашем кэше 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 (размер поплавка). Итак, большая степень двойки.

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

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

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

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

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

zviadm
источник
Вы сделали ошибку в последних двух абзацах? Обе попытки одинаковы. :)
Xeo
Ассоциативность кеша также играет роль.
Бен Джексон
20

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

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

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

Джонатан Мур
источник
+1. Кажется вероятным. Следует быть осторожным с ассоциативностью кеша.
Macke
16

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

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

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

Дана Разумная
источник
2
но очень маловероятно, что у него 16,7 МБ кеш-памяти процессора
Марино Шимич
Я обновил результаты с 2049x2049 - 91 секунда. Если это была "проблема с кешем", разве это не должно быть больше 300 секунд?
Wolf
@Marino, ответ был обновлен с учетом этого.
Dana the Sane
1
Мне кажется, что ни одно из этих объяснений не может адекватно описать новые детали, касающиеся различных и редких размеров, которые вызывают проблему, а другие промежуточные не затронуты.
Кен Рокот
2
Я не думаю, что это объяснение правильное. Проблема заключается в том, что емкость кеша не используется полностью из-за конфликтов строк кеша при размере, равном 2. Кроме того, операционная система не имеет ничего общего с кешами, потому что не ОС решает, что кэшировать, а что удалять, это все. в оборудовании. ОС имеет какое-то отношение к выравниванию данных, но в данном случае все дело в том, как C # решает выделить данные и как представить 2D-массив в памяти, ОС не имеет к этому никакого отношения.
zviadm
10

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

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

Кристиан Ханг-Хикс
источник
5

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


источник
Раздел 5 ссылки на ассоциативность кеша, кажется, применим в частности.
Dana the Sane
4

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

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

Guffa
источник
Это не объясняет, почему 2049 год быстрее 2048 года.
Macke
@Macke: Это потому, что он проходит некоторые ограничения в кешировании памяти, так что пропусков кеша намного больше.
Guffa
Почему голос против? Если вы не скажете то, что считаете неправильным, это не улучшит ответ.
Guffa
Еще один отрицательный голос без каких-либо объяснений ... Неужели в моем ответе слишком мало «вероятно», «догадываться» и «следует», как в ответах, которые получают больше всего положительных голосов ...?
Гуффа
4

Псевдоним кеша

Или кеширование , если можно назвать термин.

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

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

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

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

Поскольку кеш намного быстрее, чем DRAM (в основном благодаря тому, что он находится на кристалле), скорость обращения - это все.

DigitalRoss
источник
2

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

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

Дэвид Хеффернан
источник
1
Я знаю о BLAS, но задача заключалась не в том, чтобы сделать его максимально быстрым, а в написании и тестировании на разных языках. Для меня это очень странная проблема, и мне действительно любопытно, почему результаты такие же.
Wolf
3
@Wolf Мне было бы трудно понять, занимает ли то, что должно занять секунду, 90 или 300 секунд.
Дэвид Хеффернан
4
Лучший способ узнать, как что-то работает, - написать это самому и посмотреть, как можно улучшить свою реализацию; это (надеюсь) то, что делает Вольф.
Каллум Роджерс
@ Каллум Роджерс, согласен. Так я узнал о важности размеров буфера при копировании файлов.
Келли С. Френч
1

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

Арлен
источник
Хм, но массив, объявленный как 2D (float [,] matice = new float [rozmer, rozmer];), всегда размещается в ОЗУ только как одномерный массив, и вычисления строк / шагов выполняются под капотом. Так почему же объявление его как 1D и выполнение ручных вычислений ряда / шага было быстрее? Вы имеете в виду, что sol'n выделяет большой массив как массив меньших плиток, каждая из которых может поместиться в кеш, а большой массив - нет?
Eric M
1
Если ваша библиотека или какой-либо другой инструмент, который вы используете, выполняет мозаику, то в этом нет необходимости. Но если бы вы использовали традиционный 2D-массив, скажем, в C / C ++, то тайлинг повысил бы производительность.
Арлен
0

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

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

Automatico
источник
1
Неправильно. 2049 быстрее, чем 2048, что опровергает ваше утверждение.
Macke
@Macke: Это вполне возможно. Но есть небольшая вероятность, что политика кеширования, используемая в его процессоре, все же может сделать это решение. Это маловероятно, но немыслимо.
Automatico