Почему в массиве 2048×2048 против 2047×2047 массив умножается?

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

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

1024×1024 – 10 секунд.

1027×1027 – 10 секунд.

2047×2047 – 90 секунд.

2048×2048 – 300 секунд.

2049×2049 – 91 секунд. (Обновить)

2500×2500 – 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; } } 

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

Недостатки кэша на matice1 не являются проблемой, потому что к ним обращаются последовательно. Однако для matic2, если полный столбец соответствует 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 – ваш размер:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кэширование

Или сбой в кэше , если я смогу использовать термин.

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

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

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

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

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

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

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

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

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

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

Давайте будем гением компьютера.