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

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

Чтобы гарантировать, что новые регистры – это перемещенные старые, метка r: V ! Z используется для обозначения того, сколько регистров перемещены из исходящих ребер каждой вершины на входящие. Используя эту нотацию, можно вычислить новое количество регистров ребра (u, v) по формуле

Кроме того, чтобы избежать явного перечисления путей при поиске самого длинного пути, еще одна метка t: V ! R+ будет представлять выходное время прибытия каждого вентиля – иначе говоря, максимальную задержку вентиля при взгляде из любого предшествующего регистра. Чтобы t было не меньше комбинационной задержки, для него должно выполняться условие

8(U;V) 2 E: w0[u;v] =0 ) t[v] > t[u] + d[v] :

В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой P0(r) , 8(U;V) 2 E: w[u;v] + r[v] - r[u] > 0:

P1(t) ,8v2 V: t[v] > d[v] P2(r;t) ,8(U;V) 2E: r[u] - r[v] =w[u;v]

=► t[v] - t[u] > d[v] :

P3 , 8r0; t0: P(r0; t0) ) max(t) < max(t0) ; where max(t) , maxt[v] :

Далее будет обсуждаться только допустимая ресинхронизация (r0, t0), поэтому для упрощения изложения условие на диапазон P(r0, t0) часто будет опущено; значение будет очевидно из контекста.

Разработка алгоритма заключается в построении процедуры, такой, что ее выполнение завершится через конечное число шагов, а при завершении она будет удовлетворять заданному предикату. В случае задачи ресинхронизации с минимальной длительностью должен удовлетворяться предикат P0 Л P1 Л P2 Л P3. Этот предикат также называется постусловием. Можно утверждать, что любой нетривиальный алгоритм будет содержать по меньшей мере один цикл; в противном случае продолжительность обработки пропорциональна просто длине текста. Следовательно, некоторая часть постусловий будет итеративно удовлетворяться в цикле, тогда как оставшаяся часть будет изначально удовлетворяться в процессе инициализации и оставаться инвариантной во время выполнения цикла.

r;t :=0;d :

r; t := 0;d dofP0 API}

:P2 ! update t

:P3 ! update r odfP0 Л P1 Л P2 A P3g :

9(u; V) 2 E: r[u] - r[v] = w[u; v] A t[v] - t[u] < d[v]

!t[v]:=t[u] + d[v]:

Вторая подзадача не так проста. Если :P3, иначе говоря, если существует другая допустимая ресинхронизация hr0, t0i, такая, что max(t) > max(t0), тогда на любой вершине v, для которой выполняется t[v] = max(t), должно иметь место соотношение t0[v] < t[v]. Для этих вершин известно следующее свойство:

8v2 V: t0[v] < t[v]

=> (9u 2 V: r[u] - r[v] > r0[u] - r0[v]) ;

что означает, что если время прибытия вершины v меньше при другой ресинхронизации hr0, t0i, тогда должна существовать вершина u, такая, что r0 обеспечивает больше регистров между u и v. Фактически одной такой вершиной u является начальная вершина самого длинного комбинационного пути к v, дающего задержку t[v].

Поскольку во время выполнения этой операции регистры перемещаются, предикат P2 может перестать выполняться. Однако первая команда восстановит статус кво. Эта команда увеличивает t для некоторых вершин; некоторые из них даже могут превысить значение max(t) до перемещения регистра. Аналогичное рассуждение для hr0; t0i показывает, что их значения r также подвергаются увеличению. Таким образом, для реализации данного «насколько возможно быстрого» (As-Soon-As-Possible, ASAP) увеличения r необходимо сделать моментальный снимок max(t), пока предикат P2 еще актуален. Физически такой моментальный снимок записывает один такт применимой длительности ф и может быть реализован при помощи добавления к циклу еще одной команды:

P2 Л ф > max(t) ! ф := max(t) :

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

9(U; V) 2 E: r[u] — r[v] > w[u; v]

-> r[v] := r[u] — w[u;v] :

Для завершения разработки алгоритма осталось реализовать проверку :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.