Аноним

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

Материал из WEGA
м
Строка 35: Строка 35:


== Основные результаты ==
== Основные результаты ==
Целью задачи ресинхронизации с минимальной площадью является минимизация общего количества регистров схемы, которое задается формулой P(u; v)2E w0[u; v]. Выражая w0[u; v] через r, получаем формулировку цели
Целью задачи ресинхронизации с минимальной площадью является минимизация общего количества регистров схемы, которое задается формулой <math>\sum_{(u, v)\in E} w'[u, v] \;</math>. Выражая w'[u, v] через r, получаем формулировку цели
X(in[v] out[v]) * r[v] +   X  w[u;v] v2V (u;v)2E
 
<math>\sum_{v \in V} (in[v] - out[v]) \ast r[v] + \sum_{(u, v) \in E} w[u, v] \;</math>,
 
где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы:
где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы:
минимизировать (IN[V] — out[v]) * r[v] v2V s:t: w[u; v] + r[v] - r[u] > 0    8(u;v)2E W[u; v] + r[v] - r[u] > 1 8U; v 2 V: D[u; v] > ф r[v] 2 Z    8v 2 V
 
Минимизировать (IN[V] — out[v]) * r[v] v2V s:t: w[u; v] + r[v] - r[u] > 0    8(u;v)2E W[u; v] + r[v] - r[u] > 1 8U; v 2 V: D[u; v] > ф r[v] 2 Z    8v 2 V




4551

правка