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

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

Предварительная выборка из кэша — это метод, используемый компьютерными процессорами для повышения производительности выполнения путем извлечения инструкций или данных из исходного хранилища в более медленной памяти в более быструю локальную память до того, как они действительно потребуются (отсюда и термин «предварительная выборка»). ^{[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, Н, О, А, Б, С, ...; потоки A,B,C повторяются со временем. Другие варианты конструкции пытались обеспечить более эффективные и производительные реализации. ^{[17] [18]}

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

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

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

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

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

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

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

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

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

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

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

for ( int i = 0 ; i < 1024 ; i ++ ) { prefetch ( array1 [ i + k ]); массив1 [ я ] = 2 * массив1 [ я ]; }               

Здесь шаг предварительной выборки зависит от двух факторов: штрафа за промах в кэше и времени, необходимого для выполнения одной итерации цикла for . Например, если для выполнения одной итерации цикла требуется 7 тактов, а штраф за промах в кэше составляет 49 тактов, то так и должно быть - это означает, что система должна выполнить предварительную выборку на 7 элементов вперед. На первой итерации i будет 0, поэтому система предварительно выбирает 7-й элемент. Теперь, при таком расположении, первые 7 обращений (i=0->6) по-прежнему будут промахами (при упрощающем предположении, что каждый элемент массива1 находится в отдельной строке кэша). ${\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 цикла, а операция предварительной выборки — 12 тактов. Это означает, что для того, чтобы предварительно выбранные данные были полезными, система должна запускать итерации предварительной выборки до их использования, чтобы обеспечить своевременность. ${\displaystyle 12/3=4}$

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

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

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

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