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

Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф <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>t: V \to \mathbb{R}^+ \;</math> будет представлять выходное время прибытия каждого вентиля – иначе говоря, максимальную задержку вентиля при взгляде из любого предшествующего регистра. Для того чтобы t было не меньше комбинационной задержки, должно выполняться условие

В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой  

Ресинхронизация с достижением минимальной длительности представляет собой решение задачи <math>\langle r, t \rangle \;</math>, удовлетворяющее следующему условию оптимальности:

<math>P3 \triangleq \forall r', t': P(r', t') \implies max(t) \le max(t') \;</math>, где <math>max(t) \triangleq max_{v \in V} t[v] \;</math>.

Однако подобная ASAP-операция может ускорить r[u] даже в случае w[u, v] - r[u] + r[v] = 0 для ребра (u, v). Это означает, что P0 может быть уже не инвариантом. Однако перемещение P0 из инварианта в цель цикла не составит проблемы, поскольку для этого в цикл можно добавить одну команду:

   <math>\exist (u, v) \in E: r[u] - r[v] = w[u, v]</math>

   <math>\neg P3 \and \exist v \in V: t[v] \ge \phi</math>

   <math>\exist (u, v) \in E: r[u] - r[v] > w[u, v]</math>

   <math>od \{ P0 \and P1 \and P2 \and P3 \} \;</math>.

! Кол-во вентилей

! Кол-во обновлений

!  

!  

Для завершения разработки алгоритма осталось реализовать проверку <math>\neg P3</math>. Из предыдущего обсуждения мы уже знаем, что из <math>\neg P3</math> следует, что существует такая вершина u, что <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math> после каждого увеличения r[v]. Это означает, что <math>max_{v \in V} \; r[v] - r'[v]</math> не будет увеличиваться. Иначе говоря, существует по меньшей мере одна вершина v, у которой r[v] не будет меняться. До увеличения r[v] имеет место соотношение <math>w_{u \rightsquigarrow v} - r[u] + r[v] \le 0 \;</math>, где <math>w_{u \rightsquigarrow v} \ge 0 \;</math> – исходное количество регистров на одной пути из u в v, в результате чего неравенство <math>r[v] - r[u] \le 1 \;</math> остается верным даже после увеличения r[v]. Из этого следует, что будет по меньшей мере i + 1 вершин, у которых r не превышает i для <math>0 \le i < |V| \;</math>. Иными словами, алгоритм может по-прежнему увеличивать r, и когда какое-либо значение r достигнет |V|, это покажет, что условие P3 удовлетворяется. Таким образом, полный алгоритм имеет следующую форму:

   <math>\exist (u, v) \in E: r[u] - r[v] = w[u, v]</math>

   <math>\exist (u, v) \in E: r[u] - r[v] > w[u, v]</math>

В базовом алгоритме оптимальность P3 проверяется условием <math>r[v] \ge |V| \;</math>. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство <math>r[u] - r'[u] \ge r[v] - r'[v] \;</math>.  

Результаты были опубликованы Чжоу [3] по итогам сравнения времени выполнения алгоритма с эффективной эвристикой под названием ASTRA [ ]. Результаты прогона на эталонных тестах ISCAS89 представлены в таблице 1 из работы [3]; столбцы A и B таблицы отражают время выполнения двух этапов ASTRA.