Рассмотрим случай, когда у свернутого графа цикла есть контуры, но удаление одной дуги делает этот граф бесконтурным. Будем считать, что эта дуга соответствует циклически порожденной out-in зависимости, и эту дугу будем называть обратной.

Обозначим рассматриваемую обратную дугу (y₀, x₀). Таким образом, данные на какой-то начальной итерации поступают на обработку сначала в элементарный процессор x₀, затем проходят обработку, двигаясь по некоторой цепочке процессоров, после чего, на какой-то из последующих итераций, по дуге (y₀, x₀) опять приходят в процессор x₀. 

Может так случиться, что процессор x₀, выполняющий бинарную операцию, по обратной дуге (y₀, x₀) получает аргумент после того, как уже пришел другой аргумент этой операции.   

Пример 289.

DO 99 I = 2, N

99   X(I) = Y(I)+Z(I)*X(I-1)

Свернутый граф этого рекуррентного цикла будет иметь следующий вид :

            1       

X(1)            *            +                X(I)

Z(I)             Y(I) 

Рис. 79. Конфликт в подаче данных при обратной связи.

В этом примере при I = 3 мультипликативный процессор должен вычислять произведение X(2) и Z(3), но аддитивный процессор не успел вычислить X(2), как сумму Y(2) и (X(1)*Z(2)) . 

В рассмотренной ситуации данные следует подавать на конвейер через несколько тактов. Количество тактов, через которые подаются данные, обозначим символом T. По аналогии с программной конвейеризацией будем эту величину называть интервалом инициализации итераций [89]. Тогда время выполнения цикла с N итерациями на конвейере равно T*N+L, где L – некоторая константа (равная длительности выполнения одной итерации цикла). Поэтому, чем меньше величина T , тем эффективнее работает конвейер. Алгоритм вычисления величины T приведем ниже для более общего случая. 

Один оператор присваивания. Индексы со сдвигами
Обратные дуги

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

Обозначим для i-ого пути сдвиг в вершине x_i через a_i – это число итераций, через которое используются данные, передаваемые по обратной дуге. Время прохождения данных по этому пути равно количеству дуг b_i . Для каждого пути с номером i должно выполняться неравенство

 a_i *T >= b_i .     

Из этого неравенства вытекает, что в качестве T можно взять величину

                                          T = ] max_i {b_i / a_i } [

Здесь ]x[ означает наименьшее целое число, которое не меньше числа x.

Для тех обратных дуг, для которых отношение b_i / a_i меньше величины T, следует установить соответствующие значения буферов a_i *T - b_i .

Пример 290.

DO 99 I = 2, N

99   X(I) = X(I-1) + Y(I)* (A(I)+X(I-2))

Свернутый граф рассматриваемого цикла содержит две обратных дуги. Для одной из них отношение b_i / a_i равно 1, а для другой 3/2. Таким образом, T = 2 и на каждой обратной дуге данные должны задерживаться в буфере на один такт.