4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 6: | Строка 6: | ||
Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф <math>G = (V, E) \;</math>, представляющий схему – в котором каждая вершина <math>v \in V \;</math> представляет вентиль, а каждое ребро <math>e \in E \;</math> – передачу сигнала от одного вентиля к другому – с | Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф <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] | Чтобы гарантировать, что новые регистры – это перемещенные старые, метка <math>r: V \to \mathbb{Z} \;</math> используется для обозначения того, сколько регистров перемещены из исходящих ребер каждой вершины на входящие. Используя эту нотацию, можно вычислить новое количество регистров ребра (u, v) по формуле | ||
w'[u, v] = w[u, v] + r[v] - r[u]. | |||
Строка 27: | Строка 29: | ||
С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u, v] | С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u, v] - r[u] + r[v]. Это количество не будет отрицательным в силу предыдущего ограничения. В случае, когда оно оказывается нулевым, будет иметь место путь с задержкой D[u, v], на котором не имеется регистров. Таким образом, для ресинхронизации схемы с длительностью такта <math>\varphi \;</math> должно удовлетворяться следующее ограничение: | ||
Таким образом, для ресинхронизации схемы с длительностью такта <math>\varphi \;</math> должно удовлетворяться следующее ограничение: | |||
<math>P1(r) \triangleq \forall u, v \in V: D[u, v] > \phi \implies W[u, v] + r[v] - r[u] \ge 1 \;</math>. | <math>P1(r) \triangleq \forall u, v \in V: D[u, v] > \phi \implies W[u, v] + r[v] - r[u] \ge 1 \;</math>. |
правка