4551
правка
Ресинхронизация схемы: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) м (→Ограничения) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
== Основные результаты == | == Основные результаты == | ||
Целью задачи ресинхронизации с минимальной площадью является минимизация общего количества регистров схемы, которое задается формулой | Целью задачи ресинхронизации с минимальной площадью является минимизация общего количества регистров схемы, которое задается формулой <math>\sum_{(u, v)\in E} w'[u, v] \;</math>. Выражая w'[u, v] через r, получаем формулировку цели | ||
<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 | |||