Матричное умножение: малая разница в размере матрицы, большая разница в таймингах

Ответ 1

Здесь мое дикое предположение: кеш

Возможно, вы можете поместить 2 строки 2000 double в кеш. Что меньше, чем 32kb кеш L1. (оставляя место другим необходимым вещам)

Но когда вы увеличиваете его до 2048, он использует кеш целиком (и вы проливаете некоторые, потому что вам нужно место для других вещей)

Предполагая, что политика кэша - LRU, пролитие кеша только маленьким битом приведет к тому, что вся строка будет повторно очищена и перезагружена в кеш L1.

Другая возможность - ассоциативность кэша из-за силы-двух. Хотя я думаю, что процессор является 2-полосной ассоциацией L1, поэтому я не думаю, что это важно в этом случае. (но я все равно брошу идею)

Возможное объяснение 2: Недостатки кэша конфликтов из-за супер-выравнивания в кэше L2.

Ваш массив B повторяется в столбце. Таким образом, доступ выполняется. Общий размер данных 2k x 2k составляет около 32 МБ на матрицу. Это намного больше, чем ваш кэш L2.

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

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

Ответ 2

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

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

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

  ...Tag... | ...Index... | Offset_within_Cache_Line

(Иногда индексом и тегом являются хэши, например, несколько XOR других битов в биты среднего диапазона, которые являются индексом. Гораздо реже, иногда индекс и, реже, тег, такие вещи, как вывод строки кэша адрес по модулю простого числа.Эти более сложные индексные расчеты - это попытки борьбы с проблемой резонанса, которые я объясняю здесь. Все страдают от какой-то формы резонанса, но простейшие схемы извлечения битового поля подвергаются резонансу по общим схемам доступа, как вы уже нашли. )

Итак, типичные значения... Есть много разных моделей "Opteron Dual Core", и я ничего здесь не вижу, чтобы указать, какой из них у вас есть. Выбрав одно из них, самое последнее руководство, которое я вижу на веб-сайте AMD, Руководство для разработчиков Bios и Kernel (BKDG) для моделей AMD 15h 00h-0Fh, 12 марта 2012 г..

(Семейство 15h = семейство бульдозеров, самый последний высокопроизводительный процессор - BKDG упоминает двойное ядро, хотя я не знаю номер продукта, который именно вы описываете. Но, во всяком случае, та же идея резонанса относится к все процессоры, это просто, что параметры, такие как размер кеша и ассоциативность, могут немного отличаться.)

Из стр .33:

Процессор AMD Family 15h содержит 16-килобайтный 4-тактный прогнозируемый L1 кэш данных с двумя 128-битными портами. Это кеш-запись, которая поддерживает до двух 128 байтовых нагрузок за цикл. Он разделен на 16 банки, каждый по 16 байт. [...] Только одна загрузка может быть выполнена из заданный банк кеша L1 за один цикл.

Подводя итог:

• 64-байтная строка кэша = > 6 смещенных битов в строке кэша

• 16KB/4-way = > резонанс составляет 4 КБ.

  т.е. биты адреса 0-5 являются смещением строки кэша.

• Кэш-линии 16 КБ/64В = > 2 ^ 14/2 ^ 6 = 2 ^ 8 = 256 строк кэша в кеше.
  (Исправление: я изначально просчитал это как 128. Я исправил все зависимости.)

• 4-сторонняя ассоциативная = > 256/4 = 64 индекса в массиве кеша. я (Intel) называют эти "наборы".

  то есть. вы можете считать, что кеш представляет собой массив из 32 записей или наборов, каждая запись, содержащая 4 строки кэша, объявляет их теги. (Это сложнее, чем это, но это хорошо).

(Кстати, термины "set" и "way" имеют различные определения.)

• имеется 6 индексных битов, бит 6-11 в простейшей схеме.

  Это означает, что любые строки кэша, которые имеют одинаковые значения в битах индекса, бит 6-11, будут сопоставляться с одним и тем же набором кеша.

Теперь посмотрите на свою программу.

C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

Loop k - самый внутренний цикл. Базовый тип - double, 8 байтов. Если размерность = 2048, то есть 2K, то последующие элементы B[dimension*k+j], к которым обращается цикл, будут 2048 * 8 = 16K байтов. Все они будут сопоставляться с одним и тем же набором кеша 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 (Store To Load Forwarding buffers) может сравниваться только с использованием небольшого битового поля и получения ложных совпадений.

(На самом деле, если вы думаете об этом, резонанс в кеше подобен aliasing, связанный с использованием битовых полей. Резонанс вызван несколькими строками кэша, сопоставляющими один и тот же набор, а не с разбросанным адом. на неполных битах адреса.)

В целом, моя рекомендация по настройке:

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

• После этого используйте VTune или OProf. Или Cachegrind. Или...

• Еще лучше, используйте хорошо настроенную библиотечную процедуру для умножения матрицы.

Ответ 3

Существует несколько возможных объяснений. Одно из возможных объяснений - это то, что предлагает Mystical: исчерпание ограниченного ресурса (либо кэша, либо TLB). Другой вероятной возможностью является ложный псевдоним, который может возникать, когда последовательные обращения к памяти разделяются кратным некоторой мощности двух (часто 4 КБ).

Вы можете начать сужать то, что на работе, затягивая время/измерение ^ 3 для диапазона значений. Если вы взорвали кеш или исчерпали доступ TLB, вы увидите более или менее плоскую секцию, за которой следует резкое повышение между 2000 и 2048 годами, а затем еще один плоский раздел. Если вы видите стойки, связанные с псевдонимом, вы увидите более или менее плоский график с узким шипом вверх на 2048.

Конечно, это имеет диагностическую силу, но это не является окончательным. Если вы хотите окончательно узнать, что является источником замедления, вам нужно узнать о счетчиках производительности, которые могут окончательно ответить на этот вопрос.

Ответ 4

Я знаю, что это вааай слишком старо, но я укушу. Он (как было сказано) - проблема с кешем, которая вызывает замедление вокруг полномочий двух. Но есть и другая проблема: он слишком медленный. Если вы посмотрите на свой цикл вычисления.

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];

Внутренний цикл изменяется на 1 на каждую итерацию, а это означает, что вы получаете доступ всего лишь в 1 раз от последнего элемента, который вы использовали A , но целое "измерение" удваивается от последнего элемента B. Это не выгодно для кеширования элементов B.

Если вы измените это на:

for(i = 0; i < dimension; i++)
    for(j = 0; j < dimension; j++)
        for(k = 0; k < dimension; k++)
            C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k];

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

Не умножайте матрицы по определению, а, скорее, строками

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

$ diff a.c b.c
42c42
<               C[dimension*i+j] += A[dimension*i+k] * B[dimension*k+j];
---
>               C[dimension*i+k] += A[dimension*i+j] * B[dimension*j+k];
$ make a
cc     a.c   -o a
$ make b
cc     b.c   -o b
$ ./a 1024

secs:88.732918
$ ./b 1024

secs:12.116630

В качестве бонуса (и что делает это связано с этим вопросом) заключается в том, что этот цикл не страдает от предыдущей проблемы.

Если вы уже все это знали, я извиняюсь!

Ответ 5

Несколько ответов упомянули проблемы с кэшем L2.

Фактически вы можете проверить это с помощью моделирования кэша. Valgrind cachegrind может сделать это.

valgrind --tool=cachegrind --cache-sim=yes your_executable

Установите параметры командной строки , чтобы они соответствовали вашим параметрам L2 процессора.

Протестируйте его с разными размерами матрицы, вы, вероятно, увидите внезапное увеличение коэффициента пропускания L2.