Предвыборка кода

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В компьютерной архитектуре, предвыборкой кода (англ. instruction prefetch) называют технологию, используемую в микропроцессоре для увеличения скорости исполнения программ, уменьшая время, в течение которого процессор находится в состоянии ожидания[en] из-за отсутствия инструкций для исполнения.

Современные микропроцессоры гораздо быстрее чем память, в следствии чего инструкции исполняемой программы не могут считывыться достаточно быстро, чтобы обеспечить непрерывность работы процессора[1]. Добавление кэша может обеспечить более быстрый доступ к необходимым инструкциям.

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

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

Первыми серийными микропроцессорами, использующими предвыборку кода, были Intel 8086 (6 байт) и Motorola 68000 (4 байта).

Способы реализации[править | править исходный текст]

Существуют аппаратные, программные и комбинированные методы реализации предвыборки кода[2][3]:

Аппаратные[править | править исходный текст]

Предвыборка следующей строки[править | править исходный текст]

Метод был предложен в в 1978 году[4] и, как следует из названия, заключается в подкачке следующей или нескольких следующих строк в кэш инструкций. В данном случае, под текущей строкой кэша инструкций, понимают строку кэша, содержащую инструкцию, которая исполняется в данный момент. При реализации данного метода наибольшее значение имеет выбор оптимального расстояния подкачки[5] — расстояния от конца текущей строки до последней подгружаемой. Если расстояние подкачки выбрать слишком маленьким, то код не будет успевать подгружаться в кэш инструкций и процессор будет входить в состояние ожидания из-за отсутствия кода. Если выбрать расстояние слишком большим, то отрицательный эффект от "загрязнения" кэша (то есть вытеснения из кэша слишком большого количества полезных данных) может перевесить положительный эффект от предвыборки.

Метод показывает свою эффективность на последовательных участках кода, однако он ничего не предлагает для предвыборки кода, который который должен начать исполняться после команды перехода или вызова процедуры. Несмотря на свои очевидные недостатки, метод прост в реализации, требует минимального количества дополнительной аппаратуры в процессоре[5] и уменьшает количество блокировок по отсутствию кода на 20-50 %[6][2].

Предвыборка заданной строки[править | править исходный текст]

Технология была предложена в 1992 году[6]. Этот метод, в отличии от предвыборки следующей строки, призван обеспечить подкачку кода, на который переходит управление программы в результате исполнения операции перехода. Для этого добавляется аппаратная таблица, в которую заносится каждая уже исполненная операция перехода с её результатом (адресом перехода). Метод основывается на предположении: если однажды, на какой либо операции передачи управления, был вычислен определённый адрес перехода, то велика вероятность того, что при повторном исполнении той же операции будет вычислен тот же адрес.

Данный подход не способен предотвратить промахи в кэш холодного старта, так как, для того чтобы воспользоваться таблицей при обработке какой-либо операции перехода, необходимо предварительно, хотя бы один раз, исполнить эту операцию. Кроме того, метод требует значительного количества дополнительной аппаратуры в процессоре[5].

Предвыборка несостоявшегося перехода[5][править | править исходный текст]

Предвыборка с помощью предсказателя Маркова[7][править | править исходный текст]

Примечания[править | править исходный текст]

  1. Abdel-Hameed Badawy, Aneesh Aggarwal, Donald Yeung, Chau-Wen Tseng The Efficacy of Software Prefetching and Locality Optimizations on Future Memory Systems // The Journal of Instruction-Level Parallelism. — 2004. — Т. 6. Архивировано из первоисточника 30 июня 2013.
  2. 1 2 Галазин А.Б. Методы оптимизации доступа к подсистеме памяти на этапе компиляции для микропроцессорных систем с архитектурой широкого командного слова. — 2008.
  3. C A Moritz, Yao Guo, and SSA group. An Introduction to Prefetching. Архивировано из первоисточника 30 июня 2013.
  4. A. J. Smith Sequential Program Prefetching in Memory Hierarchies // IEEE Computer Society Press Los Alamitos, CA, USA. — 1978. — Т. 11. — № 12. — С. 7-21.
  5. 1 2 3 4 Jim Pierce , Trevor Mudge Wrong-Path Instruction Prefetching // Technical Report CSE-222-94. — 1994. — С. 165--175. Архивировано из первоисточника 30 июня 2013.
  6. 1 2 J. E. Smith, W.-C. Hsu Prefetching in supercomputer instruction caches // Supercomputing '92 Proceedings of the 1992 ACM/IEEE conference on Supercomputing. — 1992. — С. 588-597.
  7. Doug Joseph, Dirk Grunwald Prefetching using Markov Predictors // In Proceedings of the 24th Annual International Symposium on Computer Architecture. — 1997. Архивировано из первоисточника 30 июня 2013.

Ссылки[править | править исходный текст]