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

Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф <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>.

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

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

!  

!  

Для завершения разработки алгоритма осталось реализовать проверку :P3. Из предыдущего обсуждения мы уже знаем, что из :P3 следует, что существует такая вершина u, что r[u] — r0[u] > r[v] — r0[v] после каждого увеличения r[v]. Это означает, что maxv2V r[v] — r0[v] не будет увеличиваться. Иначе говоря, существует по меньшей мере одна вершина v, у которой r[v] не будет меняться. До увеличения r[v] имеет место соотношение wu^v — r[u] + r[v] < 0, где wu^v > 0 – исходное количество регистров на одной пути из u в v, в результате чего неравенство r[v] — r[u] < 1 остается верным даже после увеличения r[v]. Из этого следует, что будет по меньшей мере i + 1 вершин, у которых r не превышает i для 0 < i < jVj. Иными словами, алгоритм может по-прежнему увеличивать r, и когда какое-либо значение r достигнет j Vj, это показывает, что условие P3 удовлетворяется. Таким образом, полный алгоритм имеет следующую форму: r, t,<j) := 0,d,oo; dofP1g

-> r[v] := r[u] -w[u,v] odfP0 Л P1 Л P2 Л P3g :

'''Теорема 1. Время выполнения данного алгоритма ресинхронизации в наихудшем случае ограничено сверху значением O(j Vj2 jEj).'''

Время выполнения алгоритма ресинхронизации в наихудшем случае будет актуальным в случае, когда каждое увеличение r приводит к «протягиванию» синхронизации по всей схеме (т.е. по |E| ребрам). Это верно только тогда, когда увеличение r перемещает все регистры в схеме. Однако в таком случае верхняя граница r равна 1, и время выполнения не превышает O(jVjjEj). С другой стороны, если значение r велико, схема разбивается регистрами на несколько меньших фрагментов, в результате чего протягивание, вызванное увеличением одного r, ограничено деревом небольшого размер.

Следовательно, если ввести указатель из v к u при увеличении r[v], указатели не смогут образовать цикл согласно :P3. Фактически указатели образуют лес, в котором корни имеют значение r = 0, а потомок может иметь значение r, не более чем на 1 превышающее значение его предка. Использование цикла указателей как свидетельство верности P3 вместо r[v] > |V|, можно значительно повысить практическую эффективность алгоритма.

Ресинхронизация нередко используется для оптимизации длительности цикла либо количества регистров в схеме. Описанный алгоритм решает только задачу ресинхронизации с достижением минимальной длительности. Задачу ресинхронизации с достижением минимального количества регистров для заданной длительности цикла решили Лейзерсон и Сакс [1], она представлена в соответствующей статье. Их алгоритм сводит задачу к двойственной проблеме поиска сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать эффективный итеративный алгоритм для решения задачи о минимальном количестве регистров, схожий с алгоритмом Чжоу.

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