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

Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф <math>G = (V, E) \;</math>, представляющий схему – в котором каждая вершина <math>v \in V \;</math> представляет вентиль, а каждое ребро <math>e \in E \;</math> – передачу сигнала от одного вентиля к другому – с задержкой <math>d: V \to \mathbb{R}^+ \;</math> и номерами регистров <math>w: E \to \mathbb{N} \;</math>. Целью задачи нахождения минимальной площади является перемещение регистров <math>w': E \to \mathbb{N} \;</math>, такое, что количество регистров в схеме минимально в пределах заданной длительности такта <math>\varphi \;</math>. Задача нахождения минимальной длительности ищет решение с минимальной длительностью такта.

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

С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u, v] — r[u] + r[v]. Это количество не будет отрицательным в силу предыдущего ограничения. В случае, когда оно оказывается нулевым, будет иметь место путь с задержкой D[u, v], на котором не имеется регистров.

 

 

Таким образом, для ресинхронизации схемы с длительностью такта <math>\varphi \;</math> должно удовлетворяться следующее ограничение: