Предварительная выборка данных на L1 и L2

Question

В руководстве Агнера Фога " Оптимизация программного обеспечения на C++" в разделе 9.10 "Конфликты Кахче в больших структурах данных" он описывает проблему транспонирования матрицы, когда ширина матрицы равна чему-то, называемому критическим шагом. В его тесте стоимость для матрицы в L1 на 40% больше, когда ширина равна критическому шагу. Если матрица еще больше и подходит только для L2, стоимость составляет 600%! Это хорошо подытожено в Таблице 9.1 в его тексте. Это существенно то же самое, что наблюдалось в разделе Почему транспонирование матрицы 512x512 намного медленнее, чем транспонирование матрицы 513x513?

Позже он пишет:

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

Так что мои вопросы связаны с предварительной загрузкой данных.

Из его комментария я делаю вывод, что L1 может предварительно выбирать более одной строки кэша за раз. Сколько он может предварительно выбрать?

Из того, что я понимаю, попытка написать код для предварительной выборки данных (например, с помощью _mm_prefetch) редко бывает полезной. Единственный пример, который я прочитал, - это " Примеры предварительной выборки"? и это только улучшение O(10%) (на некоторых машинах). Агнер позже объясняет это:

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

Итак, как ЦП решает, какие данные предварительно выбирать, и существуют ли способы помочь ЦП сделать лучший выбор для предварительной выборки (например, "регулярные шаблоны с фиксированными шагами")?

Изменить: на основе комментария Лиора позвольте мне добавить к моим вопросам и сделать его более интересным. Почему критический шаг оказывает гораздо большее влияние на L2 по сравнению с L1?

Редактировать: Я пытался воспроизвести таблицу Агнера Фога, используя код в Почему транспонирование матрицы 512x512 намного медленнее, чем транспонирование матрицы 513x513? Я запускал это с 64-разрядным режимом выпуска MSVC2013 на Xeon E5 1620 (Ivy Bridge), который имеет 8-канальный L1 32 КБ, 8-канальный L2 256 КБ и 20-канальный L3 10 МБ. Максимальный размер матрицы для L1 составляет около 90x90, 256x256 для L3 и 1619 для L3.

Matrix Size  Average Time
64x64        0.004251 0.004472 0.004412 (three times)
65x65        0.004422 0.004442 0.004632 (three times)
128x128      0.0409
129x129      0.0169
256x256      0.219   //max L2 matrix size
257x257      0.0692
512x512      2.701
513x513      0.649
1024x1024    12.8
1025x1025    10.1

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

Answer 1

Это утверждение:

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

это неверно

На самом деле, сборщики L2 часто сильнее и агрессивнее, чем сборщики L1. Это зависит от конкретной машины, которую вы используете, но предварительный выбор Intel L2, например, может инициировать 2 предварительных выборки для каждого запроса, в то время как L1 обычно ограничен (есть несколько типов предварительных выборок, которые могут сосуществовать в L1, но они, вероятно, конкурировать на более ограниченном BW, чем L2 имеет в своем распоряжении, поэтому, вероятно, будет меньше предварительных выборок, выходящих из L1.

Руководство по оптимизации в разделе 2.2.5.4 содержит следующие типы средств предварительной выборки:

Two hardware prefetchers load data to the L1 DCache:
- Data cache unit (DCU) prefetcher: This prefetcher, also known as the streaming prefetcher, is triggered by an ascending access to very recently loaded data. The processor assumes that this access is part of a streaming algorithm and automatically fetches the next line.
- Instruction pointer (IP)-based stride prefetcher: This prefetcher keeps track of individual load instructions. If a load instruction is detected to have a regular stride, then a prefetch is sent to the next address which is the sum of the current address and the stride. This prefetcher can prefetch forward or backward and can detect strides of up to 2K bytes.

 Data Prefetch to the L2 and Last Level Cache - 
 - Spatial Prefetcher: This prefetcher strives to complete every cache line fetched to  the L2 cache with the pair line that completes it to a 128-byte aligned chunk.
 - Streamer: This prefetcher monitors read requests from the L1 cache for ascending and descending sequences of addresses. Monitored read requests include L1 DCache requests initiated by load and store operations and by the hardware prefetchers, and L1 ICache requests for code fetch. When a forward or backward stream of requests is detected, the anticipated cache lines are prefetched. Prefetched cache lines must be in the same 4K page. 

И чуть дальше:

... The streamer may issue two prefetch requests on every L2 lookup. The streamer can run up to 20 lines ahead of the load request.

Из вышеперечисленного только IP-адреса могут обрабатывать шаги, превышающие одну строку кэша (потоковые могут обрабатывать все, что использует последовательные строки кэша, то есть до 64-байтовых шагов (или фактически до 128 байтов, если вы не возражаете против некоторых дополнительных линии). Чтобы использовать это, убедитесь, что загрузка / хранение по заданному адресу будет выполнять пошаговый доступ - это обычно имеет место уже в циклах, проходящих по массивам. Развертывание цикла компилятором может разделить это на несколько разных потоков шага с большими шагами - что будет работать еще лучше (предвидение будет больше), если вы не превысите количество ожидающих отслеживаемых IP-адресов - опять же, это зависит от точной реализации.

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