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

Предварительная выборка из кэша - это метод, используемый компьютерными процессорами для повышения производительности выполнения путем извлечения инструкций или данных из их исходного хранилища в более медленной памяти в более быструю локальную память до того, как они действительно понадобятся (отсюда и термин «предварительная выборка»). ^[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] и зависит от остальной части задействованной микроархитектуры .

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

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

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

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

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

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

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

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

для  ( int  я = 0 ;  я < 1024 ;  я ++ )  {  массив1 [ я ]  =  2  *  массив1 [ я ]; }

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

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

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

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

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

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

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

Покрытие [ править ]

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

${\ displaystyle Coverage = {\ frac {\ text {Промахи кеша, устраненные с помощью предварительной выборки}} {\ text {Всего промахов кеша}}}}$ ,

где, ${\text{Total Cache Misses}}=({\text{Cache misses eliminated by prefetching}})+({\text{Cache misses not eliminated by prefetching}})$

Точность [ править ]

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

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

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

Своевременность [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b Смит, Алан Джей (1 сентября 1982 г.). «Кэш-память». ACM Comput. Surv . 14 (3): 473–530. DOI : 10.1145 / 356887.356892 . ISSN 0360-0300 .
^ Б с д е е Solihin, Ян (2016). Основы параллельной многоядерной архитектуры . Бока-Ратон, Флорида: CRC Press, Taylor & Francis Group. п. 163. ISBN. 978-1482211184.
^ Баер, Жан-Лу; Чен, Тянь-Фу (1991-01-01). Эффективная схема предварительной загрузки на кристалле для снижения штрафа за доступ к данным . 1991 Конференция ACM / IEEE по суперкомпьютерам. Альбукерке, Нью-Мексико, США: ACM. С. 176–186. CiteSeerX 10.1.1.642.703 . DOI : 10.1145 / 125826.125932 . ISBN 978-0897914598.
^ Кеннеди, Porterfield, Аллан (1989-01-01). Программные методы повышения производительности кеш-памяти суперкомпьютерных приложений (Диссертация). Университет Райса. hdl : 1911/19069 .
^ Миттал, Спарш (2016-08-01). «Обзор последних методов предварительной выборки для кеш-памяти процессора» . ACM Comput. Surv . 49 (2): 35: 1–35: 35. DOI : 10.1145 / 2907071 . ISSN 0360-0300 .
^ a b c Джуппи, Норман П. (1990). Повышение производительности кэша с прямым отображением за счет добавления небольшого полностью ассоциативного кэша и буферов предварительной выборки . Нью-Йорк, Нью-Йорк, США: ACM Press. CiteSeerX 10.1.1.37.6114 . DOI : 10.1145 / 325164.325162 . ISBN 0-89791-366-3.
^ Чен, Тянь-Фу; Баер, Жан-Лу (1995-05-01). «Эффективная аппаратная предварительная выборка данных для высокопроизводительных процессоров». Транзакции IEEE на компьютерах . 44 (5): 609–623. DOI : 10.1109 / 12.381947 . ISSN 0018-9340 . S2CID 1450745 .
^ Палачарла, S .; Кесслер, RE (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.
^ Grannaes, Marius; Джаре, Магнус; Натвиг, Лассе (2011). «Аппаратная предварительная выборка для эффективного хранения с использованием таблиц прогнозирования с дельта-корреляцией». Журнал параллелизма на уровне инструкций (13): 1–16. CiteSeerX 10.1.1.229.3483 .
^ Каллахан, Дэвид; Кеннеди, Кен; Портерфилд, Аллан (1 января 1991). Предварительная загрузка программного обеспечения . Четвертая международная конференция по архитектурной поддержке языков программирования и операционных систем. Санта-Клара, Калифорния, США: ACM. С. 40–52. DOI : 10.1145 / 106972.106979 . ISBN 978-0897913805.

[:3-1] Смит, Алан Джей (1 сентября 1982 г.). «Кэш-память». ACM Comput. Surv . 14 (3): 473–530. DOI : 10.1145 / 356887.356892 . ISSN 0360-0300 .

[:2-2] Б с д е е Solihin, Ян (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 . DOI : 10.1145 / 125826.125932 . ISBN 978-0897914598.

[4] Кеннеди, Porterfield, Аллан (1989-01-01). Программные методы повышения производительности кеш-памяти суперкомпьютерных приложений (Диссертация). Университет Райса. hdl : 1911/19069 .

[5] Миттал, Спарш (2016-08-01). «Обзор последних методов предварительной выборки для кеш-памяти процессора» . ACM Comput. Surv . 49 (2): 35: 1–35: 35. DOI : 10.1145 / 2907071 . ISSN 0360-0300 .

[:1-6] Джуппи, Норман П. (1990). Повышение производительности кэша с прямым отображением за счет добавления небольшого полностью ассоциативного кэша и буферов предварительной выборки . Нью-Йорк, Нью-Йорк, США: ACM Press. CiteSeerX 10.1.1.37.6114 . DOI : 10.1145 / 325164.325162 . ISBN 0-89791-366-3.

[7] Чен, Тянь-Фу; Баер, Жан-Лу (1995-05-01). «Эффективная аппаратная предварительная выборка данных для высокопроизводительных процессоров». Транзакции IEEE на компьютерах . 44 (5): 609–623. DOI : 10.1109 / 12.381947 . ISSN 0018-9340 . S2CID 1450745 .

[8] Палачарла, S .; Кесслер, RE (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; Джаре, Магнус; Натвиг, Лассе (2011). «Аппаратная предварительная выборка для эффективного хранения с использованием таблиц прогнозирования с дельта-корреляцией». Журнал параллелизма на уровне инструкций (13): 1–16. CiteSeerX 10.1.1.229.3483 .

[10] Каллахан, Дэвид; Кеннеди, Кен; Портерфилд, Аллан (1 января 1991). Предварительная загрузка программного обеспечения . Четвертая международная конференция по архитектурной поддержке языков программирования и операционных систем. Санта-Клара, Калифорния, США: ACM. С. 40–52. DOI : 10.1145 / 106972.106979 . ISBN 978-0897913805.

[1]