Предварительная выборка кеша - Cache prefetching

Предварительная выборка кеша - это метод, используемый компьютерными процессорами для повышения производительности за счет выборки инструкций или данных из их исходного хранилища в более медленной памяти в более быструю локальную память до того, как они действительно понадобятся (отсюда и термин «предварительная выборка»).^[1] Большинство современных компьютерных процессоров имеют быстрые и локальные кэш-память в котором предварительно загруженные данные хранятся до тех пор, пока они не потребуются. Источник для операции предварительной выборки обычно основная память. Из-за их конструкции доступ кэш-память обычно намного быстрее, чем доступ основная память, поэтому предварительная выборка данных и последующий доступ к ним из кешей обычно на много порядков быстрее, чем доступ к ним напрямую из основная память. Предварительная загрузка может быть выполнена без блокировки инструкции по управлению кешем.

Данные и предварительная выборка из кэша инструкций

Предварительная выборка из кеша может извлекать данные или инструкции в кеш.

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

• Предварительная загрузка инструкций извлекает инструкции перед их выполнением. Первыми основными микропроцессорами, использовавшими ту или иную форму предварительной выборки команд, были Intel 8086 (шесть байтов) и Motorola 68000 (четыре байта). В последние годы все высокопроизводительные процессоры используют методы предварительной выборки.

Аппаратная и программная предварительная выборка кеша

Предварительная выборка из кэша может выполняться аппаратно или программно.^[2]

• Аппаратная предварительная выборка обычно достигается за счет наличия специального аппаратного механизма в процессоре, который наблюдает за потоком инструкций или данных, запрашиваемых исполняющейся программой, распознает следующие несколько элементов, которые могут потребоваться программе на основе этого потока, и выполняет предварительную выборку в кэш процессора.^[3]

• Программная предварительная выборка обычно выполняется, когда компилятор анализирует код и вставляет дополнительные инструкции «предварительной выборки» в программу во время самой компиляции.^[4]

Методы аппаратной предварительной выборки

Буферы потока

• Потоковые буферы были разработаны на основе концепции «одноблочной опережающей схемы (OBL)», предложенной Алан Джей Смит.^[1]
• Транслировать буферы являются одним из наиболее распространенных методов предварительной выборки на основе оборудования.^[5] Этот метод был первоначально предложен Норман Джуппи в 1990 году^[6] и с тех пор было разработано множество вариаций этого метода.^[7][8][9] Основная идея заключается в том, что промах в кеше адрес (и ${\displaystyle k}$ последующие адреса) извлекаются в отдельный буфер глубины ${\displaystyle k}$. Этот буфер называется буфером потока и отделен от кеша. Затем процессор потребляет данные / инструкции из буфера потока, если адрес, связанный с предварительно выбранными блоками, совпадает с запрошенным адресом, сгенерированным программой, выполняющейся на процессоре. На рисунке ниже показана эта установка:

^[6] Типичная настройка буфера потока, первоначально предложенная Нормалом Джуппи в 1990 г.

• Всякий раз, когда механизм предварительной выборки обнаруживает промах в блоке памяти, скажем, A, он выделяет поток, чтобы начать предварительную выборку блоков, начиная с пропущенного блока. Если буфер потока может содержать 4 блока, тогда мы будем предварительно выбирать A + 1, A + 2, A + 3, A + 4 и удерживать их в выделенном буфере потока. Если затем процессор потребляет A + 1, то он должен быть перемещен «вверх» из буфера потока в кэш процессора. Первая запись буфера потока теперь будет A + 2 и так далее. Этот шаблон предварительной выборки последовательных блоков называется Последовательная предварительная выборка. В основном он используется, когда необходимо выполнить предварительную выборку смежных местоположений. Например, он используется при предварительной загрузке инструкций.
• Этот механизм можно расширить, добавив несколько таких «потоковых буферов», каждый из которых будет поддерживать отдельный поток предварительной выборки. Для каждого нового промаха будет выделен новый буфер потока, и он будет работать аналогично описанному выше.
• Идеальная глубина буфера потока - это то, что можно экспериментировать с различными тестами.^[6] и зависит от остальных микроархитектура участвует.

Другой шаблон инструкций предварительной выборки - предварительная выборка адресов, которые ${\displaystyle s}$ адреса впереди в последовательности. Он в основном используется, когда последовательные блоки, которые должны быть выбраны заранее. ${\displaystyle s}$ адреса отдельно.^[2] Это называется Последовательная предварительная выборка.

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

Предварительная выборка, управляемая компилятором

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

Эти предварительные выборки являются неблокирующими операциями с памятью, то есть эти обращения к памяти не мешают действительному доступу к памяти. Они не изменяют состояние процессора и не вызывают сбои страниц.

Одним из основных преимуществ программной предварительной выборки является то, что она уменьшает количество принудительных промахов кеша.^[2]

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

Рассмотрим цикл for, как показано ниже:

за (int я=0; я<1024; я++) {    array1[я] = 2 * array1[я];}

На каждой итерации i^th осуществляется обращение к элементу массива "array1". Следовательно, мы можем выполнить предварительную выборку элементов, к которым будет осуществляться доступ в будущих итерациях, вставив инструкцию «предварительной выборки», как показано ниже:

за (int я=0; я<1024; я++) {    предварительная выборка (array1 [я + k]);    array1[я] = 2 * array1[я];}

Здесь шаг предварительной выборки, ${\displaystyle k}$ зависит от двух факторов: штраф за промах в кэше и время, необходимое для выполнения одной итерации за петля. Например, если на выполнение одной итерации цикла требуется 7 циклов, а штраф за промах в кэше составляет 49 циклов, то мы должны иметь ${\displaystyle k=49/7=7}$ - это означает, что мы предварительно выбираем 7 элементов. На первой итерации i будет 0, поэтому мы предварительно выбираем 7-й элемент. Теперь, при таком расположении, первые 7 обращений (i = 0-> 6) все равно будут пропущены (в упрощенном предположении, что каждый элемент array1 находится в отдельной строке кэша).

Сравнение аппаратной и программной предварительной выборки

• Для предварительной загрузки программного обеспечения требуется программист или компилятор вмешательство, аппаратная предварительная выборка требует специальных аппаратных механизмов.^[2]
• Программная предварительная выборка хорошо работает только с циклами, в которых есть регулярный доступ к массиву, поскольку программист должен вручную кодировать инструкции предварительной выборки. В то время как аппаратные программы предварительной выборки работают динамически в зависимости от поведения программы на время выполнения.^[2]
• Аппаратная предварительная выборка также снижает нагрузку на ЦП по сравнению с программной предварительной выборкой.^[10]

Метрики предварительной выборки кеша

Есть три основных показателя, позволяющих судить о предварительной выборке из кеша.^[2]

Покрытие

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

${\displaystyle Coverage={\frac {\text{Cache Misses eliminated by Prefetching}}{\text{Total Cache Misses}}}}$,

куда, ${\displaystyle {\text{Total Cache Misses}}=({\text{Cache misses eliminated by prefetching}})+({\text{Cache misses not eliminated by prefetching}})}$

Точность

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

${\displaystyle {\text{Prefetch Accuracy}}={\frac {\text{Cache Misses eliminated by prefetching}}{({\text{Useless Cache Prefetches}})+({\text{Cache Misses eliminated by prefetching}})}}}$

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

Своевременность

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

Рассмотрим цикл for, в котором каждая итерация занимает 3 цикла, а операция предварительной выборки - 12 циклов. Это означает, что для того, чтобы предварительно выбранные данные были полезны, мы должны запустить предварительную выборку. ${\displaystyle 12/3=4}$ итераций до его использования для поддержания своевременности.

Смотрите также

• Очередь ввода предварительной выборки
• Предварительная загрузка ссылок
• Prefetcher
• Инструкция по управлению кешем

Рекомендации

1. Смит, Алан Джей (1982-09-01). «Кэш-память». ACM Comput. Surv. 14 (3): 473–530. Дои:10.1145/356887.356892. ISSN  0360-0300.
2. Солихин, Ян (2016). Основы параллельной многоядерной архитектуры. Бока-Ратон, Флорида: CRC Press, Taylor & Francis Group. п. 163. ISBN  978-1482211184.
3. Баер, Жан-Лу; Чен, Тянь-Фу (1991-01-01). Эффективная схема предварительной загрузки на кристалле для снижения штрафа за доступ к данным. 1991 Конференция ACM / IEEE по суперкомпьютерам. Альбукерке, Нью-Мексико, США: ACM. С. 176–186. CiteSeerX  10.1.1.642.703. Дои:10.1145/125826.125932. ISBN  978-0897914598.
4. Кеннеди, Портерфилд, Аллан (01.01.1989). Программные методы повышения производительности кеш-памяти суперкомпьютерных приложений (Тезис). Университет Райса. HDL:1911/19069.
5. Миттал, Спарш (01.08.2016). «Обзор последних методов предварительной выборки для кэшей процессора». ACM Comput. Surv. 49 (2): 35:1–35:35. Дои:10.1145/2907071. ISSN  0360-0300.
6. Джуппи, Норман П. (1990). Повышение производительности кэша с прямым отображением за счет добавления небольшого полностью ассоциативного кэша и буферов предварительной выборки. Нью-Йорк, Нью-Йорк, США: ACM Press. CiteSeerX  10.1.1.37.6114. Дои:10.1145/325164.325162. ISBN  0-89791-366-3.
7. Чен, Тянь-Фу; Баер, Жан-Лу (1995-05-01). «Эффективная аппаратная предварительная выборка данных для высокопроизводительных процессоров». Транзакции IEEE на компьютерах. 44 (5): 609–623. Дои:10.1109/12.381947. ISSN  0018-9340. S2CID  1450745.
8. Palacharla, S .; Кесслер, Р. Э. (1994-01-01). Оценка потоковых буферов в качестве замены вторичного кэша. 21-й ежегодный международный симпозиум по компьютерной архитектуре. Чикаго, Иллинойс, США: Пресса компьютерного общества IEEE. С. 24–33. CiteSeerX  10.1.1.92.3031. Дои:10.1109 / ISCA.1994.288164. ISBN  978-0818655104.
9. Grannaes, Мариус; Джаре, Магнус; Натвиг, Лассе (2011). «Аппаратная предварительная выборка с эффективным использованием хранилища с использованием таблиц прогнозирования с дельта-корреляцией». Журнал параллелизма на уровне инструкций (13): 1–16. CiteSeerX  10.1.1.229.3483.
10. Каллахан, Дэвид; Кеннеди, Кен; Портерфилд, Аллан (1 января 1991). Предварительная загрузка программного обеспечения. Четвертая международная конференция по архитектурной поддержке языков программирования и операционных систем. Санта-Клара, Калифорния, США: ACM. С. 40–52. Дои:10.1145/106972.106979. ISBN  978-0897913805.