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

Технология компьютерной обработки для повышения производительности памяти

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

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

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

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

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

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

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

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

Потоковые буферы

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

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

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

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

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

Регулярные шаги

В этом шаблоне последовательный доступ к памяти выполняется к блокам, которые являются адресами, разделенными. ^{[3] [12]} В этом случае предварительная выборка вычисляет и использует его для вычисления адреса памяти для предварительной выборки. Например: если равен 4, то адрес для предварительной выборки будет A+4. ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

Неравномерные пространственные шаги

В этом случае дельта между адресами последовательных доступов к памяти является переменной, но все еще следует шаблону. Некоторые конструкции предвыборок ^{[9] [13] [14]} используют это свойство для прогнозирования и предвыборки для будущих доступов.

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

Этот класс предвыборок ищет потоки доступа к памяти, которые повторяются с течением времени. ^{[15] [16]} Например, в этом потоке доступа к памяти: N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ...; поток A, B, C повторяется с течением времени. Другие вариации дизайна пытались обеспечить более эффективные, производительные реализации. ^{[17] [18]}

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

Компьютерные приложения генерируют различные шаблоны доступа. Архитектуры процессора и подсистемы памяти, используемые для выполнения этих приложений, еще больше устраняют неоднозначность шаблонов доступа к памяти, которые они генерируют. Следовательно, эффективность и результативность схем предварительной выборки часто зависят от приложения и архитектур, используемых для их выполнения. ^[19] Недавние исследования ^{[20] [21]} были сосредоточены на создании совместных механизмов для синергетического использования нескольких схем предварительной выборки для лучшего покрытия и точности предварительной выборки.

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

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

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

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

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

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

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

для ( int i = 0 ; i < 1024 ; i ++ ) { array1 [ i ] = 2 * array1 [ i ]; }          

На каждой итерации осуществляется доступ к i-му ^{элементу} массива "array1". Таким образом, система может предварительно выбирать элементы, к которым будет осуществляться доступ в будущих итерациях, вставляя инструкцию "prefetch", как показано ниже:

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

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

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

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

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

Существует три основных показателя для оценки предварительной загрузки кэша ^[3]

Покрытие

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

${\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 цикла для выполнения, а операция 'prefetch' занимает 12 циклов. Это подразумевает, что для того, чтобы предварительно выбранные данные были полезны, система должна запустить итерации prefetch до их использования, чтобы поддерживать своевременность. ${\displaystyle 12/3=4}$

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

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

Ссылки

1. Smith, Alan Jay (1982-09-01). «Кэш-память». ACM Comput. Surv . 14 (3): 473–530. doi :10.1145/356887.356892. ISSN  0360-0300. S2CID  6023466.
2. Ли, Чуньлинь; Сун, Миньян; Ду, Шаофэн; Ван, Сяохай; Чжан, Минь; Ло, Юлонг (2020-09-01). «Адаптивная замена кэша на основе приоритетов и предварительная выборка кэша на основе прогнозирования в среде периферийных вычислений». Журнал сетевых и компьютерных приложений . 165 : 102715. doi : 10.1016/j.jnca.2020.102715. S2CID  219506427.
3. Солихин, Ян (2016). Основы параллельной многоядерной архитектуры . Бока-Ратон, Флорида: CRC Press, Taylor & Francis Group. стр. 163. ISBN 978-1482211184.
4. Baer, ​​Jean-Loup; Chen, Tien-Fu (1991-01-01). Эффективная схема предварительной загрузки на кристалле для снижения штрафа за доступ к данным . Конференция ACM/IEEE по суперкомпьютерам 1991 года. Альбукерке, Нью-Мексико, США: Ассоциация вычислительной техники. стр. 176–186. CiteSeerX 10.1.1.642.703 . doi :10.1145/125826.125932. ISBN  978-0897914598.
5. Кеннеди, Портерфилд, Аллан (1989-01-01). Программные методы улучшения производительности кэша в суперкомпьютерных приложениях (диссертация). Университет Райса. hdl :1911/19069.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
6. Jouppi, Norman P. (1990). "Улучшение производительности кэша с прямым отображением путем добавления небольшого полностью ассоциативного кэша и буферов предварительной выборки". Труды 17-го ежегодного международного симпозиума по архитектуре компьютеров – ISCA 1990. 17-й ежегодный международный симпозиум по архитектуре компьютеров – ISCA 1990. Нью-Йорк, Нью-Йорк, США: Association for Computing Machinery Press. стр. 364–373. CiteSeerX 10.1.1.37.6114 . doi :10.1145/325164.325162. ISBN  0-89791-366-3.
7. Чэнь, Тянь-Фу; Баер, Жан-Лу (1995-05-01). «Эффективная аппаратная предварительная выборка данных для высокопроизводительных процессоров». IEEE Transactions on Computers . 44 (5): 609–623. doi :10.1109/12.381947. ISSN  0018-9340. S2CID  1450745.
8. Палачарла, С.; Кесслер, Р. Э. (1994-01-01). Оценка потоковых буферов как замены вторичного кэша . 21-й ежегодный международный симпозиум по архитектуре компьютеров. Чикаго, Иллинойс, США: IEEE Computer Society Press. стр. 24–33. CiteSeerX 10.1.1.92.3031 . doi :10.1109/ISCA.1994.288164. ISBN  978-0818655104.
9. Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). «Эффективная предварительная выборка оборудования для хранения с использованием таблиц предсказаний с дельта-корреляцией». Журнал параллелизма на уровне инструкций (13): 1–16. CiteSeerX 10.1.1.229.3483 . 
10. Ишии, Ясуо; Инаба, Мэри; Хираки, Кей (2009-06-08). "Соответствие шаблону карты доступа для предварительной выборки кэша данных". Труды 23-й Международной конференции по суперкомпьютерам . ICS 2009. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 499–500. doi :10.1145/1542275.1542349. ISBN 978-1-60558-498-0. S2CID  37841036.
11. Шринат, Сантош; Мутлу, Онур; Ким, Хьесун ; Патт, Йель Н. (февраль 2007 г.). Управляемая обратной связью предварительная выборка: повышение производительности и эффективности использования полосы пропускания аппаратных предварительных выборок. 13-й международный симпозиум IEEE 2007 г. по архитектуре высокопроизводительных компьютеров. стр. 63–74. doi :10.1109/HPCA.2007.346185. ISBN 978-1-4244-0804-7. S2CID  6909725.
12. Kondguli, Sushant; Huang, Michael (ноябрь 2017 г.). T2: Высокоточный и энергоэффективный предвыборщик шагов. Международная конференция IEEE по компьютерному проектированию (ICCD) 2017 г. стр. 373–376. doi :10.1109/ICCD.2017.64. ISBN 978-1-5386-2254-4. S2CID  11055312.
13. Шевгур, Манджунат; Коладия, Сахил; Баласубрамонян, Раджив; Вилкерсон, Крис; Пагсли, Сет Х.; Чишти, Зешан (декабрь 2015 г.). Эффективная предварительная выборка сложных шаблонов адресов. 48-й ежегодный международный симпозиум IEEE/ACM по микроархитектуре (MICRO) 2015 г. стр. 141–152. doi :10.1145/2830772.2830793. ISBN 9781450340342. S2CID  15294463.
14. Ким, Джинчун; Пагсли, Сет Х.; Гратц, Пол В.; Редди, А. Л. Нарасимха; Вилкерсон, Крис; Чишти, Зешан (октябрь 2016 г.). Предварительная выборка на основе достоверности пути. 49-й ежегодный международный симпозиум IEEE/ACM по микроархитектуре (MICRO) 2016 г. стр. 1–12. doi :10.1109/MICRO.2016.7783763. ISBN 978-1-5090-3508-3. S2CID  1097472.
15. Джозеф, Дуг; Грюнвальд, Дирк (1997-05-01). "Предварительная выборка с использованием предсказателей Маркова". Труды 24-го ежегодного международного симпозиума по архитектуре компьютеров . ISCA 1997. ISCA 1997. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 252–263. doi :10.1145/264107.264207. ISBN 978-0-89791-901-2. S2CID  434419.
16. Коллинз, Дж.; Сайр, С.; Колдер, Б.; Туллсен, Д.М. (ноябрь 2002 г.). Упреждающая выборка с использованием кэша указателя. 35-й ежегодный международный симпозиум IEEE/ACM по микроархитектуре, 2002 г. (MICRO-35). Труды. стр. 62–73. doi :10.1109/MICRO.2002.1176239. ISBN 0-7695-1859-1. S2CID  5608519.
17. Джейн, Аканкша; Лин, Кэлвин (2013-12-07). «Линейная адаптация нерегулярных обращений к памяти для улучшения коррелированной предварительной выборки». Труды 46-го ежегодного международного симпозиума IEEE/ACM по микроархитектуре . MICRO-46. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр. 247–259. doi :10.1145/2540708.2540730. ISBN 978-1-4503-2638-4. S2CID  196831.
18. «Практическое применение временных предвыборок: предвыборка MISB – Исследовательские статьи – Исследования Arm – Сообщество Arm». community.arm.com . 24 июня 2019 г. Получено 16.03.2022 .
19. Ким, Джинчун; Теран, Эльвира; Гратц, Пол В.; Хименес, Дэниел А.; Пагсли, Сет Х.; Вилкерсон, Крис (2017-05-12). «Уничтожение счетчика программ: реконструкция поведения программ в иерархии кэша процессора». Уведомления ACM SIGPLAN . 52 (4): 737–749. doi : 10.1145/3093336.3037701 . ISSN  0362-1340.
20. Kondguli, Sushant; Huang, Michael (2018-06-02). «Разделение труда: более эффективный подход к предварительной выборке». Труды 45-го ежегодного международного симпозиума по архитектуре компьютеров . ISCA '18. Лос-Анджелес, Калифорния: IEEE Press. стр. 83–95. doi :10.1109/ISCA.2018.00018. ISBN 978-1-5386-5984-7. S2CID  50777324.
21. Pakalapati, Samuel; Panda, Biswabandan (май 2020 г.). Букет указателей инструкций: предварительная выборка пространственного оборудования на основе классификатора указателей инструкций. 47-й ежегодный международный симпозиум ACM/IEEE по архитектуре компьютеров (ISCA) 2020 г. стр. 118–131. doi : 10.1109/ISCA45697.2020.00021. ISBN 978-1-7281-4661-4. S2CID  218683672.
22. Каллахан, Дэвид; Кеннеди, Кен; Портерфилд, Аллан (1991-01-01). Предварительная загрузка программного обеспечения . Четвертая международная конференция по архитектурной поддержке языков программирования и операционных систем. Санта-Клара, Калифорния, США: Ассоциация вычислительной техники. стр. 40–52. doi :10.1145/106972.106979. ISBN 978-0897913805.
23. Ли, Джэкю и Ким, Хесун и Вудук, Ричард (2012), «Когда предварительная загрузка работает, когда нет и почему» (PDF) , ACM Trans. Archit. Code Optim. , 9 : 1–29, doi :10.1145/2133382.2133384{{citation}}: CS1 maint: multiple names: authors list (link)