Ресинхронизация схемы: различия между версиями

Перейти к навигации Перейти к поиску
м
нет описания правки
мНет описания правки
Строка 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
   
   
== Ограничения ==
 
В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой
 
P0(r) , 8(U; V) 2 E: w[u; v] + r[v] - r[u] > 0
С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u; v] — r[u] + r[v]. Это количество не будет отрицательным в силу предыдущего ограничения. В случае, когда оно оказывается нулевым, будет иметь место путь с задержкой D[u, v], не имеющий регистров
   
   
  (W[u,v]-l)*f[u,v]
  (W[u,v]-l)*f[u,v]
4551

правка

Навигация