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

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

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

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

Итак, мои вопросы связаны с предварительной выборкой данных.

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

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

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

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

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

Изменить: Я попытался воспроизвести таблицу Agner Fog с помощью кода Почему перенос матрицы 512x512 намного медленнее, чем перенос матрицы из 513x513? Я запускал это с 64-разрядным режимом MSVC2013 на Xeon E5 1620 (Ivy Bridge), который имеет L1 32KB 8-way, L2 256 KB 8-way и L3 10MB 20-way. Максимальный размер матрицы для 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 раз.

Ответ 1

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

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

неверно

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

Руководство по оптимизации в разделе 2.2.5.4 учитывает следующие типы prefetcher:

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-based может обрабатывать шаги, превышающие одну строку кеша (потоковые могут иметь дело со всем, что использует последовательные линии кэша, что означает до 64-битного шага (или фактически до 128 байтов, если вы не используете обратите внимание на некоторые дополнительные строки). Чтобы использовать это, убедитесь, что загрузки/сохранения по заданному адресу будут выполняться с помощью stried-доступа - обычно это происходит в циклах, проходящих через массивы. Развертывание цикла компилятора может разбить это на несколько разных потоков шага с большими strides - это будет работать еще лучше (просмотр будет больше), если вы не превысите количество выдающихся отслеживаемых IP-адресов - опять же, это зависит от конкретной реализации.

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