Computing RecII

В случае, если мы имеем граф зависимостей без циклов, то RecII = 0 и MII следует находить исходя из ResII. В случае графа с циклами (т.е. имеется loop carried dependency), то надо решить задачу Cyclic Graph Scheduling.

Рассмотрим, пример кода:

for k = 1 to N do
    y[k] = (x[k-3] + 1)^2 + a;
    x[k] = y[k] + b;
    z[k] = (z[k-1] - 2)^3 + d;
end

Operation	Latency
+,-	9
*, ^2	2

Граф зависимостей:

Алгоритм: Оптимальные циклы с двойными весами

(1)

\begin{align} w(G) = \max _{C \in C(G)} \frac {\sum_{(v _{i}, u _{j}) \in C} l _{ij} }{\sum _{(v _{i}, u _{j}) \in C} d _{ij} } \end{align}