Программная конвейеризация циклов (англ. software pipelining) — это техника, используемая компиляторами для оптимизации циклов по аналогии с вычислительным конвейером в микропроцессорах. Является формой внеочередного исполнения с той разницей, что переупорядочивание выполняется не процессором, а компилятором (либо, в случае ручной оптимизации, программистом). Некоторые компьютерные архитектуры, например Intel IA-64, имеют явную аппаратную поддержку для упрощения программной конвейеризации циклов.
При конвейеризации цикла в каждый момент времени на исполнении находится код, относящийся к нескольким итерациям цикла, но к различным частям цикла.
Рассмотрим цикл:
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) ...Предположим, что каждая инструкция будет требовать три такта для завершения (не будем учитывать стоимость работы самого цикла). Кроме того, предположим, что инструкции планируются на исполнение каждый такт, если у них нет зависимостей от исполняемых инструкций. Без конвейеризации каждая итерация цикла займет по 9 тактов, 3 такта для А(1), 3 такта для B(1), 3 такта для С(1).
Теперь применим конвейеризацию цикла. Последовательность исполнения станет:
A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...В данном случае инструкции будут уходить на исполнение каждый такт, и каждые три итерации будут исполняться за 9 тактов, что даст среднее в 3 такта на итерацию.
В этом примере конвейеризация использовалась вместе с раскруткой цикла. Но в более общем случае, раскрутка может воспрепятствовать наилучшей работе конвейеризованного цикла. Такое может происходить в циклах, имеющий длительно исполняющиеся операции (например, деление или математические функции). Подобные циклы конвейеризуются для сокрытия задержки длительных операций.
Следующие аппаратные решения упрощают описанную оптимизацию: