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}
page revision: 8, last edited: 17 Nov 2006 13:04