Рассмотрим случай, когда у свернутого графа цикла есть контуры, но удаление одной дуги делает этот граф бесконтурным. Будем считать, что эта дуга соответствует циклически порожденной out-in зависимости, и эту дугу будем называть обратной.
Обозначим рассматриваемую обратную дугу (y0, x0). Таким образом, данные на какой-то начальной итерации поступают на обработку сначала в элементарный процессор x0, затем проходят обработку, двигаясь по некоторой цепочке процессоров, после чего, на какой-то из последующих итераций, по дуге (y0, x0) опять приходят в процессор x0.
Может так случиться, что процессор x0, выполняющий бинарную операцию, по обратной дуге (y0, x0) получает аргумент после того, как уже пришел другой аргумент этой операции.
Пример 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 приведем ниже для более общего случая.
Один оператор присваивания. Индексы со сдвигами
Обратные дуги
Поскольку оператор в теле цикла один, все обратные дуги выходят из одной вершины (соответствующей генератору), которую обозначим y0. Удалим из свернутого графа рассматриваемого цикла обратные дуги (y0,xi). Найдем в полученном бесконтурном графе множество всех путей из xi в y0 .
Обозначим для i-ого пути сдвиг в вершине xi через ai – это число итераций, через которое используются данные, передаваемые по обратной дуге. Время прохождения данных по этому пути равно количеству дуг bi . Для каждого пути с номером i должно выполняться неравенство
ai *T >= bi .
Из этого неравенства вытекает, что в качестве T можно взять величину
T = ] maxi {bi / ai } [
Здесь ]x[ означает наименьшее целое число, которое не меньше числа x.
Для тех обратных дуг, для которых отношение bi / ai меньше величины T, следует установить соответствующие значения буферов ai *T - bi .
Пример 290.
DO 99 I = 2, N
99 X(I) = X(I-1) + Y(I)* (A(I)+X(I-2))
Свернутый граф рассматриваемого цикла содержит две обратных дуги. Для одной из них отношение bi / ai равно 1, а для другой 3/2. Таким образом, T = 2 и на каждой обратной дуге данные должны задерживаться в буфере на один такт.
Дата: 2018-12-21, просмотров: 471.