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

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

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

• 1 Данные по сравнению с предварительной выборкой из кэша инструкций
• 2 Аппаратная и программная предварительная выборка кеша
• 3 Методы аппаратной предварительной выборки
  • 3.1 Потоковые буферы
• 4 Методы предварительной выборки программного обеспечения
  • 4.1 Предварительная выборка, управляемая компилятором
• 5 Сравнение аппаратной и программной предварительной выборки
• 6 Метрики предварительной выборки кеша
  • 6.1 Покрытие
  • 6.2 Точность
  • 6.3 Своевременность
• 7 См. Также
• 8 Ссылки

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

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

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

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

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

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

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

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

Типичная настройка буфера потока, первоначально предложенная Normal Jouppi в 1990 году

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Покрытие

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

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

где, $Общее\; количество\; промахов\; кэша\; =\; (промахи\; кэша\; устранены\; упреждающей\; выборкой)\; +\; (промахи\; кэша\; не\; устраняется\; предварительной\; выборкой)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Общее\; количество\; промахов\; в\; кэше\}\}\; =\; (\{\backslash \; text\; \{Промахи\; в\; кэше\; устраняются\; предварительной\; выборкой\}\})\; +\; (\{\backslash \; text\; \{Промахи\; в\; кэше\; не\; устраняются\; предварительной\; выборкой\}\})\}$

Точность

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

$Точность\; предварительной\; выборки\; =\; Промахи\; из\; кэша,\; устраненные\; предварительной\; выборкой\; (Бесполезные\; предварительные\; выборки\; из\; кеша)\; +\; (Промахи\; из\; кеша,\; устраненные\; предварительной\; выборкой)\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Prefetch\; Accuracy\}\}\; =\; \{\backslash \; frac\; \{\backslash \; text\; \{Промахи\; в\; кэше,\; устраненные\; предварительной\; выборкой\}\}\; \{(\{\backslash \; text\; \{Бесполезные\; предварительные\; выборки\; из\; кэша\}\})\; +\; (\{\backslash \; text\; \{Промахи\; в\; кэше,\; устраненные\; предварительной\; выборкой\})\}\}\}$

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

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

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

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

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