Программная конвейеризация | это... Что такое Программная конвейеризация? (original) (raw)

Программная конвейеризация циклов (англ. software pipelining) — это техника, используемая компиляторами, для оптимизации циклов, по аналогии с вычислительным конвейером в микропроцессорах. Является формой внеочередного исполнения с той разницей, что переупорядочивание выполняется не процессором, а компилятором (либо, в случае ручной оптимизации, программистом). Некоторые компьютерные архитектуры, например Intel IA-64[1], имеют явную аппаратную поддержку для упрощения программной конвейеризации циклов.

При конвейеризации цикла в каждый момент времени на исполнении находится код, относящийся к нескольким итерациям цикла, но к различным частям цикла.

Пример

Рассмотрим цикл:

for i = 1 to bignumber A(i) B(i) C(i) end

В этом примере, A(i), B(i), C(i), обозначают инструкции, каждая из которых работает с элементом под номером i, и каждая инструкция зависит от предыдущей. Другими словами, A(i) должна выполнится прежде, чем B(i) будет запущена. Инструкция A может обозначать, к примеру, загрузку элемента из памяти в регистр процессора, B — некоторую арифметическую операцию над элементом на регистре, а C — запись элемента в память. При этом, допустим что, между итерациями цикла с разными значениями i зависимостей нет, то есть инструкцию A(2) можно запустить прежде завершения инструкции A(1).

Без техники конвейеризации цикла операции будут выполняться в такой последовательности:

A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...

Предположим, что каждая инструкция будет требовать 3 тактов для завершения (не будем учитывать стоимость работы самого цикла). Кроме того, предположим, что инструкции планируются на исполнение каждый такт, если у них нет зависимостей от исполняемых инструкций. Без конвейеризации каждая итерация цикла займет по 7 тактов (3 + 3 + 1, поскольку A(i+1) не зависит от C(i)).

Теперь применим конвейеризацию цикла. Последовательность исполнения станет:

A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...

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

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

Аппаратная поддержка

Следующие аппаратные решения упрощают описанную оптимизацию:[2]

Примечания

  1. ↑ 1 2 Itanium processor microarchitecture psu.edu PDF H Sharangpani, K Arora - IEEE Micro, 2000
  2. ↑ M. Lam, "Software pipelining: An effective scheduling technique for VLIW machines", In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (PLDI 88), July 1988 pages 318-328. Also published as ACM SIGPLAN Notices 23(7).
  3. ↑ Ахо, 10.5.12
  4. ↑ The impact of if-conversion and branch prediction on program execution on the intel itanium processor
  5. ↑ Ахо, 10.5.11
  6. ↑ Overlapped loop support in the Cydra-5. Инструкции brtop, next
  7. ↑ Itanium architecture for programmers: understanding 64-bit processors, page 313, 10.4.2 "used in software pipelining include the loop count (ar.lc) register (Section 5.6), the epilog count (ar.ec) register and special branch instructions to construct either counted or while loops using register rotation", 10.4.5 "Branch instructions for Software pipelining .. br.ctop, .. br.cexit.. br.wtop... br.wexit"

Литература