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

Перейти к навигацииПерейти к поиску

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

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

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

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

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

Способы реализации

Существуют аппаратные, программные и комбинированные методы реализации предвыборки кода[2][3]. Основным критерием классификации методов является природа реализации анализа кода, определяющего какие именно части кода будут заблаговременно подкачиваться[4]. Например, если предвыборка кода реализована в виде оптимизации компилятора, которая проставляет в нужных местах инструкции предварительной подкачки, то метод относится к программным.

Аппаратные

Предвыборка следующей строки

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

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

Предвыборка заданной строки

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

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

Предвыборка несостоявшегося перехода[6]

Предвыборка с помощью предсказателя Маркова[8]

С помощью предсказателя Маркова можно осуществить предвыборку кода.

Примечания

  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. Дата обращения: 29 июня 2013. Архивировано 30 июня 2013 года.
  4. ↑ Chi-Keung Luk, Todd C. Mowry. Cooperative Prefetching: Compiler and Hardware Support for Effective Instruction Prefetching in Modern Processors // 31st International Symposium on Microarchitecture. — 1998.
  5. ↑ A. J. Smith. Sequential Program Prefetching in Memory Hierarchies // IEEE Computer Society Press Los Alamitos, CA, USA. — 1978. — Т. 11, № 12. — С. 7—21.
  6. ↑ 1 2 3 4 Jim Pierce , Trevor Mudge. Wrong-Path Instruction Prefetching // Technical Report CSE-222-94. — 1994. — С. 165—175. Архивировано 30 июня 2013 года.
  7. ↑ 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.
  8. ↑ Doug Joseph, Dirk Grunwald. Prefetching using Markov Predictors // In Proceedings of the 24th Annual International Symposium on Computer Architecture. — 1997. Архивировано 30 июня 2013 года.

Ссылки

  • Halstead, Robert; Ward, Stephen. Computation Structures (неопр.). — MIT Press, 1989. — С. 812. — ISBN 0-262-23139-5.
  • David Callahan, Ken Kennedy, Allan Porterfield. Software prefetching // ACM, 4th Conference on Architectural Support of Programming Languages & Operating Systems. — 1991. — С. 40—52. Архивировано 30 июня 2013 года.
  • Chi-Keung Luk, Todd C. Mowry. Compiler-based prefetching for recursive data structures // ACM, 7th Conference on Architectural Support of Programming Languages & Operating Systems. — 1996. — С. 222—233. Архивировано 30 июня 2013 года.