Программная конвейеризация

Программная конвейеризация циклов (англ. 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]

• «Вращающиеся регистры» (иногда англ. modulo renaming) — часть регистрового файла отводится на область вращающихся регистров. Инструкции, использующие некоторый архитектурный регистр из этой области будут обращаться к различным физическим регистрам по мере исполнения итераций (и продвижения вращающейся области). Через какое-то количество итераций, вновь произойдет обращение к исходному физическому регистру. Это позволяет работать с различными итерациями цикла одновременно, и при этом не требуется явных пересылок между регистрами.^[1][3]
• Предикаты и предикатное исполнение инструкций, при котором предикатом работает некоторые специальные предикаты цикла. Эти предикаты позволяют включать и отключать некоторые инструкции цикла в процессе прохождения итераций, тем самым реализуя пролог и эпилог цикла в основном его коде, а также упрощают раскрытие условных операций в теле цикла.^[4][5]
• Аппаратная поддержка циклов, при которой программа дает процессору информацию о размере цикла и о параметрах индексной переменной. Это позволяет сократить накладные расходы на организацию цикла. Также позволяет настроить скорость вращения и размер группы вращающихся регистров.^[6][7]

Примечания

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"

Литература

• Ахо. Компиляторы. Принципы, технологии, инструменты. 2е издание, 2008 год. Глава 10.5