Вы определенно получаете то, что я называю кешем резонанс .Это похоже на псевдоним , но не совсем то же самое.Позвольте мне объяснить.
Кэши - это аппаратные структуры данных, которые извлекают одну часть адреса и используют ее в качестве индекса в таблице, в отличие от программного массива.(На самом деле мы называем их массивами аппаратно.) Массив кэша содержит строки данных кэша и теги - иногда одна такая запись на индекс в массиве (прямое отображение), иногда несколько таких (ассоциативность N-way set).Вторая часть адреса извлекается и сравнивается с тегом, хранящимся в массиве.Вместе индекс и тег однозначно идентифицируют адрес памяти строки кэша.Наконец, остальные биты адреса указывают, какие байты в строке кэша адресованы, а также размер доступа.
Обычно индекс и тег являются простыми битовыми полями.Таким образом, адрес памяти выглядит как
...Tag... | ...Index... | Offset_within_Cache_Line
(Иногда индекс и тег - это хэши, например, несколько XOR других битов в битах среднего диапазона, которые являются индексом. Гораздо большередко, иногда индекс, и реже тег, это такие вещи, как взятие адреса строки кэша по модулю простого числа. Эти более сложные вычисления индекса являются попытками борьбы с проблемой резонанса, которую я объясняю здесь. Все страдают некоторой формой резонанса,но самые простые схемы извлечения битового поля испытывают резонанс на общих шаблонах доступа, как вы уже нашли.)
Итак, типичные значения ... есть много разных моделей "Opteron Dual Core", и я ничего не вижуздесь, который указывает, какой у вас есть.Наугад выбирая одно из них, самое последнее руководство, которое я вижу на веб-сайте AMD, Руководство для разработчиков BIOS и ядра (BKDG) для моделей семейства AMD 15h 00h-0Fh , 12 марта 2012 г.
(Семейство 15h = семейство Bulldozer, самый последний высокопроизводительный процессор - BKDG упоминает о двухъядерном процессоре, хотя я не знаю номер продукта, который именно то, что вы описываете. Но, в любом случае, одна и та же идея резонанса применима ко всем процессорам, этоПросто такие параметры, как размер кэша и ассоциативность, могут немного отличаться.)
Начиная с стр.33:
Процессор AMD Family 15h содержит 16-Кбайт, 4-стороннийпрогнозируемый кэш данных L1 с двумя 128-битными портами.Это сквозной кэш, который поддерживает до двух загрузок по 128 байт за цикл.Он разделен на 16 банков, каждый по 16 байт.[...] Только одна загрузка может быть выполнена из данного банка кэша L1 за один цикл.
Подводя итог:
64строка байтового кэша => 6 смещенных битов в строке кэша
16KB / 4-way => резонанс равен 4KB.
Т.е. биты адреса 0-5 - это кэшсмещение строки.
16 КБ / 64B строк кэша => 2 ^ 14/2 ^ 6 = 2 ^ 8 = 256 строк кэша в кэше.
(Исправление:Первоначально я просчитал это как 128. Я исправил все зависимости.)
4-сторонняя ассоциативность => 256/4 = 64 индекса в массиве кэша.Я (Intel) называю эти «наборы».
, т. Е. Вы можете рассматривать кеш как массив из 32 записей или наборов, каждая запись содержит 4 строки кэша и свои теги.(Это сложнее, чем это, но ничего страшного).
(Кстати, термины «набор» и «путь» имеют различные определения .)
в самой простой схеме есть 6 битов индекса, биты 6-11.
Это означает, что любые строки кэша, которые имеют точно такие же значения в битах индекса, битах6-11, отобразится на тот же набор кеша.
Теперь посмотрите на вашу программу.
C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];
Петля k является самой внутренней петлей. Базовый тип - двойной, 8 байтов. Если размерность = 2048, то есть 2 КБ, то последовательные элементы B[dimension*k+j], к которым обращается цикл, будут на расстоянии 2048 * 8 = 16 Кбайт. Все они будут отображаться в один и тот же набор кеша L1 - у них у всех будет одинаковый индекс в кеше. Это означает, что вместо 256 кеш-строк в кеше, доступных для использования, будет только 4 - «4-сторонняя ассоциативность» кеша.
т.е. вы, вероятно, будете получать пропуск кеша каждые 4 итерации в этом цикле Не хорошо.
(На самом деле, все немного сложнее. Но вышеизложенное - хорошее первое понимание. Адреса записей B, упомянутых выше, являются виртуальными адресами. Так что могут быть немного другие физические адреса. Более того, у Bulldozer есть способ Предиктивный кэш, возможно, использующий биты виртуальных адресов, так что ему не нужно ждать преобразования виртуальных адресов в физические. Но, в любом случае: ваш код имеет «резонанс» 16K. Кэш данных L1 имеет резонанс 16K. . Не хорошо.)]
Если вы немного измените размер, например, до 2048 + 1 адреса массива B будут распределены по всем наборам кэша. И вы получите значительно меньше промахов кэша.
Это довольно распространенная оптимизация для заполнения ваших массивов, например чтобы изменить 2048 на 2049, чтобы избежать этого резонанса. Но «блокировка кеша - еще более важная оптимизация. http://suif.stanford.edu/papers/lam-asplos91.pdf
Помимо резонанса строки кэша, здесь происходят и другие вещи. Например, кэш L1 имеет 16 банков, каждый по 16 байт. При измерении = 2048 последовательные доступы B во внутреннем цикле всегда будут идти в один и тот же банк. Таким образом, они не могут идти параллельно - и если доступ A случится в том же банке, вы проиграете.
Я не думаю, глядя на это, что он такой же большой, как резонанс кеша.
И, да, возможно, может появиться псевдоним. Например. STLF (буферы пересылки с сохранением для загрузки) могут сравнивать только с использованием небольшого битового поля и получать ложные совпадения.
(На самом деле, если подумать, резонанс в кеше подобен псевдониму, связанному с использованием битовых полей. Резонанс вызывается несколькими строками кэша, отображающими один и тот же набор, а не разбросанными по областям. на неполных адресных битах.)
В целом моя рекомендация по тюнингу:
Попробуйте заблокировать кеш без дальнейшего анализа. Я говорю это потому, что блокировка кэша проста, и вполне вероятно, что это все, что вам нужно сделать.
После этого используйте VTune или OProf. Или Кашегринд. Или ...
Еще лучше: используйте хорошо настроенную библиотечную процедуру для умножения матриц.