4551
правка
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 20: | Строка 20: | ||
<math>D[u, v] \triangleq max_{w[p: u \rightsquigarrow v] = W[u, v]} \sum_{x \in p} d[x] \;</math>. | <math>D[u, v] \triangleq max_{w[p: u \rightsquigarrow v] = W[u, v]} \sum_{x \in p} d[x] \;</math>. | ||
== Ограничения == | |||
В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой | |||
<math>P0(r) \triangleq \forall (u, v) \in E: w[u, v] + r[v] - r[u] \ge 0 \;</math>. | |||
С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u, v] — r[u] + r[v]. Это количество не будет отрицательным в силу предыдущего ограничения. В случае, когда оно оказывается нулевым, будет иметь место путь с задержкой D[u, v], на котором не имеется регистров. | |||
Таким образом, для ресинхронизации схемы с длительностью такта <math>\varphi \;</math> должно удовлетворяться следующее ограничение: | |||
<math>P1(r) \triangleq \forall u, v \in V: D[u, v] > \phi \to W[u, v] + r[v] - r[u] \ge 1 \;</math>. | |||
== Основные результаты == | == Основные результаты == | ||
Строка 34: | Строка 48: | ||
Minimize У^ w[u;v] * f[u;v] (u;v)2E | Minimize У^ w[u;v] * f[u;v] (u;v)2E | ||
(W[u,v]-l)*f[u,v] | (W[u,v]-l)*f[u,v] |
правка