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

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

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

Пример

Рассмотрим следующий цикл:

for i = 1 to n
    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 такта на итерацию.

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

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

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

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