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

Чтобы гарантировать, что новые регистры – это перемещенные старые, метка <math>r: V \to \mathbb{Z} \;</math> используется для обозначения того, сколько регистров перемещены из исходящих ребер каждой вершины на входящие. Используя эту нотацию, можно вычислить новое количество регистров ребра (u, v) по формуле w'[u, v] = w[u, v] + r[v] — r[u].

Эту же нотацию можно расширить с ребер на пути. Однако между любыми двумя вершинами u и v может существовать более одного пути. Среди всех этих путей путь с минимальным количеством регистров будет определять, сколько регистров могут быть перемещены от u и v. Обозначим это количество за W[u, v] для любых <math>u, v \in V \;</math>, то есть

 

<math>W[u, v] = min_{p: u \rightsquigarrow v} \sum_{(x, y) \in p} w[x, y] \;</math>.