Software & Systems

Программная конвейеризация циклов представляет собой эффективный метод оптимизации циклов, который позволяет использовать параллелизм операций, относящихся к разным итерациям цикла (см.: Lam M.S. Software pipelining: An effective scheduling technique for VLIW machines. Proc. ACM SIGPLAN 1988 Conf. on Programming Language Design and Implemen­tation. 1988.). Идея конвейеризации состоит в построении такого расписания, при котором последовательные итерации запускаются с постоянным интервалом, и в сведении к минимуму этого интервала за счет совмещения выполнения команд из нескольких соседних итераций. Этот интервал называют основным интервалом (Initiation Interval – II).

Задача планирования может быть сведена к некоторой трудной математической проблеме, например, она может быть сформулирована в виде задачи целочисленного линейного программирования (ЦЛП). Задачей ЦЛП является нахождение целочисленного оптимума в задаче линейного программирования. Это хорошо изученная NP-полная задача (см.: Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация. Алгоритмы и сложность. М. 1985). Рассматривают также смешанные ЦЛП-задачи, в которых требуется целочисленность определенных переменных, не обязательно всех; такие проблемы также относят к ЦЛП. Для практического решения ЦЛП-задач разработаны пакеты программ – солверы, среди которых есть как коммерческие, так и свободно доступные в исходных текстах.

Как правило, в работах, где рассматриваются ЦЛП-формулировки проблемы конвейеризации циклов, ставится задача нахождения расписания, требующего минимального числа регистров, среди расписаний с минимальным II. В данной работе рассмотрена задача нахождения расписания цикла с минимальным II при заданных ограничениях на число физических регистров и ресурсы процессора. Таким образом, гарантируется, что при распределении регистров не придется добавлять код для вытеснения некоторых значений из регистров в память (spill-код). Среди расписаний с минимальным II при заданных ограничениях по регистрам и ресурсам ищется расписание с минимальной глубиной конвейеризации (под глубиной понимается число соседних итераций исходного цикла, совмещенных в теле конвейеризованного цикла). Тем самым минимизируется суммарный размер пролога и эпилога цикла. Предполагается, что планируемый код представлен в терминах виртуальных регистров и каждому из них значение присваивается только в одной команде. При этом условии (легко обеспечиваемом путем переименования регистров) ложные зависимости по данным отсутствуют и можно рассматривать только истинные зависимости типа «запись-чтение».

Формулировка задачи планирования линейного участка в виде ЦЛП-задачи

Рассмотрим планирование команд линейного участка: целью данной задачи является составление расписания, которое использует наименьшее число тактов. Естественно было бы ввести целочисленные переменные S1,S2,...,Sn для времени запуска на исполнение команд с номерами 1,2, ...,n и определить переменную T, которая не меньше времени запуска каждой команды. Минимизация T и стала бы целью в формулируемой задаче. Легко задать соблюдение зависимостей между командами, то есть то, что команда, читающая значение регистра, делает это не ранее, чем значение будет записано. Каждая зависимость между командами, представляющая собой тройку вида (w,r,l), где w – команда-производитель; r – потребитель; l – задержка в тактах (латентность), задается неравенством Sw+l≤Sr.

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

Вместо вектора S, задающего время старта каждой команды, вводим бинарную (с элементами 0 и 1) матрицу N, элемент N[i,t] равен 1 тогда и только тогда, когда команда i запускается на такте t или ранее. Назовем N[i,t] выполненностью команды i на такте t.

Используемый далее язык подобен языкам, реально применяемым для описания ЛП- и ЦЛП-задач. На этапе трансляции все выражения с кванторами заменяются последовательностями выражений, в которых вместо i и t подставляются константы. Затем элементы N заменяются переменными, в результате получается обычная формулировка ЦЛП-задачи, состоящая из набора переменных, линейных ограничений и линейной целевой функции.

Листинг 1:

неотрицательная целая константа T

для каждой команды i:

   для каждого t из 1..T:

     бинарные переменные N[i,t]

# Однократное выполнение

для каждой команды i: N[i,T]=1

# Неубывание выполненности

для каждой команды i:

  для каждого t из 2..T:

    N[i,t-1]≤N[i,t]

Соблюдение заданных в листинге 1 ограничений необходимо и достаточно для того, чтобы, во-первых, все команды были выполнены ровно один раз и, во-вторых, если команда выполнена, то она останется выполнена.

УТВЕРЖДЕНИЕ. Зависимость (w,r,l) по данным между командами w (производитель) и r (потребитель) с латентностью l тактов (l < T) соблюдается в расписании тогда и только тогда, когда выполнено два условия.

1)  команда-потребитель запускается не ранее l+1 такта, то есть N[r,l]=0;

2)  для любого такта t, начиная с l+1, выполненность команды-потребителя не больше выполненности команды-производителя на l тактов ранее, N[r,t]≤N[w,t-l].

Утверждение очевидно, включим его условия в формулировку задачи (листинг 2). Условия l

Листинг 2. Соблюдение зависимостей:

для каждой зависимости (w,r,l):

  N[r,l]=0

  для каждого t из l+1 .. T: N[r,t]≤N[w,t-l]

Листинг 3:

# S(i,t)=1 <==> команда i запущена на такте t

макро S(i,t) = если t=1: N[i,1]

                иначе:      N[i,t]-N[i,t-1]

для каждого вида ресурса r:

 для каждого такта t из 1..T:

   ( сумма по всем командам i

       сумма по тактам tp из 1..t

     UseRes[i,t-tp,r] * S(i,tp) )≤AllRes[r]

Использованы константы: UseRes[i,k,r] – количество единиц ресурса вида r, требующегося команде i на такте k с начала исполнения, и AllRes[r] – общее количество этого ресурса; S(i,t)=1, только если команда i запускается на такте t, в противном случае S(i,t)=0. Следовательно, UseRes[i,t-tp,r]* S(i,tp) – потребность в ресурсе r на такте t команды i, запущенной на такте tp. Просуммировав по командам и возможным тактам запуска, получаем полную потребность в ресурсе r на такте t. Так как все UseRes и AllRes – константы, а любое S – либо переменная, либо разность двух переменных, полученные неравенства – линейные.

При подсчете регистров необходимо учесть, что обычно у линейного участка есть входные и выходные значения. Для того чтобы от них избавиться, дополним линейный участок командами START и FINISH: START пусть создает все входные значения исходного линейного участка, а FINISH потребляет все выходные значения.

УТВЕРЖДЕНИЕ. В линейном участке без входных и выходных значений количество регистров, занятых на такте t, оценивается сверху выражением:

сумма по всем командам i ((W[i]-R[i])*N[i,t]),

где W[i] и R[i] – число зависимостей, в которых команда i выступает соответственно производителем и потребителем.

Для обоснования утверждения заметим, что, по определению N:

сумма по всем командам i ((W[i]-R[i])*N[i,t])==сумма по командам i, запущенным на тактах 1 .. t (W[i]-R[i]),

а каждая команда i, запускаясь, закрывает ровно R[i] зависимостей, освобождая занятые ими регистры, и открывает W[i] зависимостей. Это доказывает утверждение. Заметим, что получена именно оценка сверху, а не точное число регистров, поскольку не учтено, что один результат некоторой команды может быть использован несколькими командами. Сформулировать необходимое и достаточное условие для зависимостей, определенных как тройки (производитель, потребитель, латентность), невозможно, поскольку есть команды с несколькими выходными регистрами. Таким образом, пока можно задать только достаточное условие корректности расписания по числу используемых регистров (листинг 4), константой AllReg обозначим количество доступных физических регистров.

Листинг 4. Ограничение на число регистров, достаточное условие:

для каждого t из 1..T:

  ( сумма по всем командам i

        ((W[i]-R[i]) * N[i,t]))≤AllReg

Задача ЦЛП для планирования линейного участка в целом построена. А что же оптимизируется? Если целевая функция не задана, то процесс решения прерывается при нахождении любой допустимой точки. Однако можно задать целевую функцию, которая обеспечивает использование наименьшего числа регистров, заменив константу AllReg на минимизируемую переменную (ограничив ее сверху реальным количеством регистров).

Подобный подход к планированию линейных участков вполне работоспособен, но непрактичен из-за дороговизны решения ЦЛП-задач.

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

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

Как при планировании линейного участка, ищем расписание для фиксированного количества тактов T (в алгоритмах планирования по модулю обычно обозначаемого II). Значения T перебираем в порядке возрастания. Для каждого T формулируем и решаем ЦЛП-задачу, в которой T служит константой (листинг 5).

Листинг 5:

неотрицательная целая константа T

для каждой команды i:

  для каждого t из 1..T:

    неотрицательные целые переменные N[i,t]

для каждой команды i:

  для каждого t из 2..T: N[i,t-1] ≤ N[i,t]

для каждой команды i: N[i,T] ≤ N[i,1] + 1

Снова определили N – матрицу выполненности команд, но элементы N уже не обязательно 0 или 1, так как теперь команды могут быть выполнены произвольное неотрицательное число раз. Будем считать, что N[i,t] – количество запусков (включая исполнение в прологе) с номером i до t-го такта включительно некоторой фиксированной (например первой) итерации конвейеризованного цикла. При этом вопрос “Для какой именно итерации цикла определено N?” пока не очень важен, поскольку во все выражения войдут только разности элементов N. Первое приведенное ограничение задает неубывание выполненности. Второе ограничение запрещает выполнение более одного экземпляра команды за одну итерацию цикла.

Листинг 6:

макро N(i,t) =

    если t<1: N(i,t+T)-1  # Рекурсивное

    если t>T: N(i,t-T)+1  #   определение

    иначе:      N[i,t]

макро S(i,t)=N(i,t)-N(i,t-1)

для каждой команды i: N(i,0)≥0

Определение макроса N(i,t) в листинге 6 упрощает формулируемые ограничения и отражает тот факт, что описывается периодический процесс с периодом T. Заметим, что специальных ограничений, требующих выполнения каждой команды, не требуется: просуммировав S(i,t) по t от 1 до T, получаем ровно единицу. Ограничение N(i,0)≥0 указывает, что до первой итерации цикла (в прологе цикла) каждая команда может быть выполнена неотрицательное число раз. Рассмотрим ограничения по ресурсам (листинг 7).

Листинг 7:

для каждого вида ресурса r:

  для каждого t из 1..T:

    (сумма по всем командам i

        сумма по tp из t-М .. t

          UseRes[i,t-tp,r]*S(i,tp))≤AllRes[r]

Заметим, что внутреннее суммирование по tp начинается не с первого такта, как в случае с линейным участком, а с такта t-M, где M – константа, ограничивающая сверху время, через которое запущенная команда может потребовать ресурсы. Можно определить M как максимальное x, такое что UseRes[i,x,r]≠0 хотя бы для одной команды i и ресурса r. Заметим также, что M может быть больше T, то есть для одного такта суммируются потребности в ресурсах нескольких копий одной и той же команды, относящихся к разным итерациям.

Ограничение на соблюдение зависимостей (листинг 8) содержательно отличается от соответствующего ограничения для линейного участка только тем, что учитываются дистанции зависимостей. Дистанция зависимости (для простого цикла) – неотрицательное целое число, определяющее номер итерации, к которой относится команда-потребитель относительно итерации команды-производителя: 0 – текущая итерация, 1 – следующая и т.д.

Листинг 8:

для каждой зависимости (w,r,l,d):

  для каждого t из 1..T: N(r,t)-d≤N(w,t-l)

Действительно, дистанция d определяет, на сколько команд-потребителей в данной зависимости может быть выполнено больше, чем команд-произво­дителей. Переформулируем достаточное условие корректности числа использованных регистров (листинг 9).

Листинг 9:

для каждого t из 1..T:

  DistSum+(сумма по всем командам i

                ((W[i]-R[i])*N[i,t]))≤AllReg

Отличие только в добавлении константы DistSum, отражающей начальную потребность в регистрах, равную сумме дистанций по всем зависимостям. Изменение числа занятых регистров вычисляется как и в случае с линейным участком. Напомним, что N[i,t], по определению, – число запусков i-й команды, каждый из которых меняет число занятых регистров на W[i]-R[i]. Важно отметить, что расписание для конвейеризованного цикла может потребовать выделения более одного физического регистра под один виртуальный регистр. Действительно, потребность в физических регистрах зависимости (w, r, l, d) на t-м такте равна (N(w,t)+d)–N(r,t), и если специально не ограничивать это выражение, оно может быть больше 1.

Несколько неочевидно, что выражение в последнем ограничении зависит только от разностей элементов N, но это так, поскольку сумма по i всех R[i] равна сумме всех W[i] – это просто общее число зависимостей, подсчитанное разными способами.

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

УТВЕРЖДЕНИЕ. В сформулированной задаче конвейеризации цикла выбор любой из следующих минимизируемых целевых функций, для любого k (сумма всех элементов N, сумма выполненностей на такте k, максимум N, максимум выполненностей на такте k) гарантирует, что оптимальное решение будет описывать порядок исполнения первой итерации конвейеризованного цикла.

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

Можно заметить, что использование минимизируемой целевой функции "сумма выполненностей на такте T" позволяет получить расписание с минимальной длиной пролога цикла, а минимизируемая целевая функция "максимум выполненностей на такте T" дает расписание с минимальной глубиной конвейеризации. Определением последней целевой функции завершаем ЦЛП-формулировку задачи конвейеризации цикла (листинг 10).

Листинг 10. Минимальная глубина конвейеризации:

неотрицательная целая переменная ConvDepth

цель: минимизация ConvDepth

для каждой команды i: N[i,T]≤ConvDepth

Точный метод подсчета регистров

До сих пор использовалось только достаточное условие корректности расписания по числу использованных физических регистров, так как не учитывалось, что значение, выработанное одной командой и использованное несколькими, требует только одного регистра для своего хранения. Это означает, что полученные расписания хоть и корректны, но в случае дефицита регистров не обязательно оптимальны. Для того чтобы сформулировать необходимое и достаточное условие, следует дополнить граф зависимостей информацией о виртуальных регистрах, представив зависимость как пятерку: (w,r,l,d,vr), где vr – виртуальный регистр. При этом считаем, что каждый виртуальный регистр используется только один раз, то есть существует ровно одна команда, которая его записывает (служит производителем в зависимостях по этому регистру). Выполнение этого требования легко обеспечить переименованием регистров.

Можно попытаться исправить формулировку достаточного условия, считая, что если K зависимостей разделяют один виртуальный регистр, то в каждой зависимости сначала захватывается (производителем), а потом освобождается (потребителем) не один регистр, а 1/K регистра. Это несложно реализовать, снабдив все зависимости соответствующими "весами", используемыми для расчета констант W[i] и R[i]. К сожалению, эта формулировка дает необходимое условие, но не достаточное: два разных наполовину освобожденных регистра – это два занятых регистра, а не один. Полученная формулировка не бесполезна, так как не требует введения дополнительных переменных и легко проверяется. Это позволяет быстрее получать отрицательные результаты, что может ускорить перебор по значениям T. Тем не менее, сформулируем необходимое и достаточное условие.

Как упоминалось ранее, для зависимости (w,r,l,d,vr) требуется (N(w,t)+d)–N(r,t) физических регистров на такте t. Это разность числа всех произведенных и потребленных значений регистра vr до такта t включительно. Можно показать, что на такте t потребность виртуального регистра vr в физических регистрах равна максимуму потребностей всех зависимостей по регистру vr. Запишем это формально (листинг 11).

Листинг 11. Необходимое и достаточное условие достаточности регистров:

для каждого t из 1..T:

  для каждого виртуального регистра vr:

   неотрицательные целые переменные RegFor[vr,t]

для каждой зависимости (w,r,l,d,vr):

  для каждого t из 1..T:

    (N(w,t)+d)-N(r,t)≤RegFor[vr,t]

для каждого t из 1..T:

  сумма по всем vr: RegFor[vr,t]≤AllReg

Важно отметить, что, во-первых, формулировка для линейного участка получается просто исключением всех дистанций; во-вторых, переменные RegFor не обязательно определять целыми; в-третьих, полученная формулировка содержит примерно вдвое больше переменных, чем раньше (количество переменных N[i,t] и RegFor[vr,t] одного порядка), в результате потребуется больше времени на решение ЦЛП-задачи. Поэтому оправдан гибридный подход, когда потребность в регистрах на каждом такте рассчитывается как сумма по-старому рассчитанной потребности зависимостей с уникальными виртуальными регистрами и суммы значений RegFor по тем виртуальным регистрам, которые читаются несколькими командами.

В заключение кратко охарактеризуем полученные результаты. Реализация описываемого подхода подключена к компилятору gcc как альтернатива эвристическому алгоритму SMS. Расчеты производились для целевой архитектуры MIPS, точнее для RM7000 с сокращенным числом регистров, для того чтобы дефицит регистров проявил различия между разными методами их учета.

Для решения задач ЦЛП использовались свободно доступные солверы: GLPK (см.: http://www.gnu. org/software/glpk) с настройками: по умолчанию и с использованием алгоритмов, основанных на отсечениях, пакеты lp_solve и cbc (из проекта COIN-OR).

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

Далее сравнивались формулировки с разными минимизируемыми целевыми функциями: глубина конвейеризации, длина пролога, и сложная целевая функция, равная сумме удвоенной глубины конвейеризации, длины эпилога, деленной на общее число команд, и максимума потребностей зависимостей в физических регистрах.

Как и ожидалось, минимизация длины пролога – самая дешевая целевая функция, но вообще отличия не слишком велики. Важно отметить закономерность, проявляющуюся для всех солверов, формулировок и тестовых примеров: в большинстве случаев отрицательные результаты получаются быстро, исключение – количество тактов на 1-2 меньше минимально достаточного, когда солверу может потребоваться значительное время. При этом решение для минимального числа тактов, для которого оно существует, находится существенно быстрее (исключением может быть солвер GLPK с настройками на использование отсечений). Это означает, что в практических целях оправдан запуск солвера без использования дорогих настроек и ограниченный небольшим временем – если расписания не нашлось быстро, значит его, скорее всего, и нет для данного числа тактов.

Среди солверов предпочтительнее других выглядит cbc. Настройка GLPK на использование отсечений иногда полезна для получения отрицательного результата, но часто вредит при получении положительных результатов.

Автор выражают глубокую благодарность всем разработчикам компилятора gcc и пакетов для решения ЦЛП-задач: GLPK, lp_solve, cbc/clp из проекта COIN-OR.