Ресинхронизация схемы: инкрементный подход
Ключевые слова и синонимы
Ресинхронизация с достижением минимальной длительности
Постановка задачи
Ресинхронизация схемы является одной из самых эффективных техник структурной оптимизации для последовательных схем. Она перемещает регистры внутри схемы, не меняя ее функции. Задача ресинхронизации с достижением минимальной длительности стремится минимизировать самую долгую задержку между любыми двумя последовательными регистрами, которая определяет длительность такта.
Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф [math]\displaystyle{ G = (V, E) \; }[/math], представляющий схему – в котором каждая вершина [math]\displaystyle{ v \in V \; }[/math] представляет вентиль, а каждое ребро [math]\displaystyle{ e \in E \; }[/math] – передачу сигнала от одного вентиля к другому – с задержками [math]\displaystyle{ d: V \to \mathbb{R}^+ \; }[/math] и количествами регистров [math]\displaystyle{ w: E \to \mathbb{N} \; }[/math]. Целью задачи ресинхронизации с нахождением минимальной площади является перемещение регистров [math]\displaystyle{ w': E \to \mathbb{N} \; }[/math], такое, что максимальная задержка между любыми двумя последовательными регистрами оказывается минимальной.
Нотация
Чтобы гарантировать, что новые регистры – это перемещенные старые, метка [math]\displaystyle{ r: V \to \mathbb{Z} \; }[/math] используется для обозначения того, сколько регистров перемещены из исходящих ребер каждой вершины на входящие. Используя эту нотацию, можно вычислить новое количество регистров ребра (u, v) по формуле
[math]\displaystyle{ w'[u, v] = w[u, v] + r[v] - r[u] \; }[/math].
Кроме того, чтобы избежать явного перечисления путей при поиске самого длинного пути, еще одна метка [math]\displaystyle{ t: V \to \mathbb{R}^+ \; }[/math] будет представлять выходное время прибытия каждого вентиля – иначе говоря, максимальную задержку вентиля при взгляде из любого предшествующего регистра. Для того чтобы t было не меньше комбинационной задержки, должно выполняться условие
[math]\displaystyle{ \forall (u, v) \in E: w'[u, v] = 0 \Rightarrow t[v] \ge t[u] + d[v] \; }[/math].
Ограничения и цель
В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой
[math]\displaystyle{ P0(r) \triangleq \forall (u, v) \in E: w[u, v] + r[v] - r[u] \ge 0 \; }[/math].
Как уже было установлено, условия, согласно которым t является допустимым временем прибытия, задаются следующими двумя предикатами.
[math]\displaystyle{ P1(t) \triangleq \forall v \in V: t[v] \ge d[v] \; }[/math],
[math]\displaystyle{ P2(r, t) \triangleq \forall u, v \in E: r[u] - r[v] = w[u, v] \implies t[v] - t[u] \ge d[v] \; }[/math].
Предикат P обозначает конъюнкцию двух вышеупомянутых условий:
[math]\displaystyle{ P(r, t) \triangleq P0(r) \and P1(t) \and P2(r, t) \; }[/math].
Ресинхронизация с достижением минимальной длительности представляет собой решение задачи [math]\displaystyle{ \langle r, t \rangle \; }[/math], удовлетворяющее следующему условию оптимальности:
[math]\displaystyle{ P3 \triangleq \forall r', t': P(r', t') \implies max(t) \le max(t') \; }[/math], где [math]\displaystyle{ max(t) \triangleq max_{v \in V} t[v] \; }[/math].
Далее будет обсуждаться только допустимая ресинхронизация (r', t'), поэтому для упрощения изложения условие на диапазон P(r', t') часто будет опущено; значение будет очевидно из контекста.
Основные результаты
В данном разделе будет показано, как разработать эффективный алгоритм для решения задачи ресинхронизации с минимальной длительностью. В отличие от обычного стиля изложения, когда представлен только финальный продукт, т.е. алгоритм, но не идеи по его разработке, далее будет изложен поэтапный процесс, приводящий в конечном итоге к созданию алгоритма.
Разработка алгоритма заключается в построении процедуры, такой, что ее выполнение завершится через конечное число шагов, а при завершении она будет удовлетворять заданному предикату. В случае задачи ресинхронизации с минимальной длительностью должен удовлетворяться предикат [math]\displaystyle{ P0 \and P1 \and P2 \and P3 \; }[/math]. Этот предикат также называется постусловием. Можно утверждать, что любой нетривиальный алгоритм будет содержать по меньшей мере один цикл; в противном случае продолжительность обработки пропорциональна просто длине текста. Следовательно, некоторая часть постусловий будет итеративно удовлетворяться в цикле, тогда как оставшаяся часть будет изначально удовлетворяться в процессе инициализации и оставаться инвариантной во время выполнения цикла.
Первое решение, которое необходимо принять, касается разбиения постусловий на возможные инварианты цикла и его цель. Из четырех конъюнктивных членов предикат P3 задает условие оптимальности и является самым сложным из всех. Следовательно, он будет рассматриваться как цель при выполнении цикла. С другой стороны, предикаты P0 и P1 легко могут быть удовлетворены при помощи простой инициализации:
r, t := 0, d.
Основываясь на этих соображениях, мы планируем разработать алгоритм согласно следующей схеме.
r, t := 0, d
do [math]\displaystyle{ \{ P0 \and P1 \} \; }[/math]
[math]\displaystyle{ \neg P2 \to update \; t }[/math]
[math]\displaystyle{ \neg P3 \to update \; r }[/math]
od [math]\displaystyle{ \{ P0 \and P1 \and P2 \and P3 \} \; }[/math].
Первую команду цикла можно переписать в виде [math]\displaystyle{ \exist (u, v) \in E: r[u] - r[v] = w[u, v] \and t[v] - t[u] \lt d[v] \to t[v] := t[u] + d[v] \; }[/math].
Фактически это релаксация алгоритма Беллмана-Форда для вычисления самых длинных путей.
Вторая команда не так проста. Если [math]\displaystyle{ \neg P3 \; }[/math], иначе говоря, если существует другая допустимая ресинхронизация [math]\displaystyle{ \langle r', t' \rangle \; }[/math], такая, что max(t) > max(t'), тогда на любой вершине v, для которой выполняется t[v] = max(t), должно выполняться соотношение t'[v] < t[v]. Для этих вершин известно следующее свойство:
[math]\displaystyle{ \forall v \in V: t'[v] \lt t[v] =\gt (\exist u \in V: r[u] - r[v] \gt r'[u] - r'[v]) \; }[/math],
что означает, что если время прибытия вершины v меньше при другой ресинхронизации [math]\displaystyle{ \langle r', t' \rangle \; }[/math], тогда должна существовать вершина u, такая, что r' обеспечивает больше регистров между u и v. Фактически одной такой вершиной u является начальная вершина самого длинного комбинационного пути к v, дающего задержку t[v].
Для сокращения длительности цикла переменную r необходимо изменить, сделав ее ближе к r'. Следует отметить, что в контексте ресинхронизации важны не абсолютные значения r, но их разности. Если [math]\displaystyle{ \langle r, t \rangle \; }[/math] является решением задачи ресинхронизации, то [math]\displaystyle{ \langle r + c, t \rangle \; }[/math], где [math]\displaystyle{ c \in \mathbb{Z} \; }[/math] – произвольная константа, также будет являться решением. Следовательно, r может быть сделана «ближе» к r' за счет размещения большего количества регистров между u и v, то есть либо за счет уменьшения r[u], либо за счет увеличения r[v]. Отметим, что v можно легко определить из соотношения t[v] = max(t). Независимо от того, какое значение (r[v] или r[u]) выбрано для изменения, изменение должно быть единичным, поскольку r не следует чрезмерно корректировать. Таким образом, после корректировки будут по-прежнему выполняться соотношения [math]\displaystyle{ r[v] - r[u] \le r'[v] - r'[u] \; }[/math] или, что эквивалентно, [math]\displaystyle{ r[v] - r'[v] \le r[u] - r'[u] \; }[/math]. Поскольку v легко определить, выберем для увеличения r[v]. Время прибытия t[v] можно незамедлительно уменьшить до d[v]. Это позволяет уточнить вторую команду:
[math]\displaystyle{ \neg P3 \and P2 \and \exist v \in V: t[v] = max(t) \to r[v], t[v] :=r[v] + 1, d[v] \; }[/math].
Поскольку во время выполнения этой операции регистры перемещаются, предикат P2 может перестать выполняться. Однако первая команда восстановит статус кво. Эта команда увеличивает t для некоторых вершин; некоторые из них даже могут превысить значение max(t) до перемещения регистра. Аналогичное рассуждение для [math]\displaystyle{ \langle r, t \rangle \; }[/math] показывает, что их значения r также подвергаются увеличению. Таким образом, для реализации данного «насколько возможно быстрого» (As-Soon-As-Possible, ASAP) увеличения r необходимо сделать моментальный снимок max(t), пока предикат P2 еще актуален. Физически такой моментальный снимок записывает один такт применимой длительности [math]\displaystyle{ \phi \; }[/math] и может быть реализован при помощи добавления к циклу еще одной команды:
[math]\displaystyle{ P2 \and \phi \gt max(t) \to \phi := max(t) \; }[/math].
Однако подобная ASAP-операция может ускорить r[u] даже в случае w[u, v] - r[u] + r[v] = 0 для ребра (u, v). Это означает, что P0 может быть уже не инвариантом. Однако перемещение P0 из инварианта в цель цикла не составит проблемы, поскольку для этого в цикл можно добавить одну команду:
[math]\displaystyle{ \exist (u, v) \in E: r[u] - r[v] \gt w[u, v] \to r[v] := r[u] - w[u, v] \; }[/math].
После объединения всех нововведений алгоритм приобретает следующую форму.
[math]\displaystyle{ r, t, \phi := 0, d, \infty \; }[/math] do {P1} [math]\displaystyle{ \exist (u, v) \in E: r[u] - r[v] = w[u, v] }[/math] [math]\displaystyle{ \and \; t[v] - t[u] \lt d[v] \to t[v] := t[u] + d[v] }[/math] [math]\displaystyle{ \neg P3 \and \exist v \in V: t[v] \ge \phi }[/math] [math]\displaystyle{ \to r[v], t[v] := r[v] + 1, d[v] }[/math] [math]\displaystyle{ P0 \and P2 \and \phi \gt max(t) \to \phi := max(t) }[/math] [math]\displaystyle{ \exist (u, v) \in E: r[u] - r[v] \gt w[u, v] }[/math] [math]\displaystyle{ \to r[v] := r[u] - w[u, v] }[/math] [math]\displaystyle{ od \{ P0 \and P1 \and P2 \and P3 \} \; }[/math].
Название Кол-во вентилей Длительность такта E' Кол-во обновлений Время ASTRA
До После A(s) B(s)
s1423 490 166 127 808 7619 0.02 0.03 0.02
s1 494 558 89 88 628 7765 0.02 0.01 0.01
s9234 2027 89 81 2215 76943 0.12 0.11 0.09
s9234.1 2027 89 81 2164 77644 0.16 0.11 0.10
s1 3207 2573 143 82 4086 28395 0.12 0.38 0.12
s1 5850 3448 186 77 12038 99314 0.36 0.43 0.17
s35932 12204 109 100 16373 108459 0.28 0.24 0.65
s38417 8709 110 56 9834 155489 0.58 0.89 0.64
s38584 11448 191 163 19692 155637 0.41 0.50 0.67
s38584.1 11448 191 183 9416 114940 0.48 0.55 0.78
Таблица 1. Экспериментальные результаты
Для завершения разработки алгоритма осталось реализовать проверку :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
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] (8v2 V: r[v] < jVj)
A 9v 2 V: t[v] >ф^ r[v]; t[v] := r[v] + 1;d[v] (9v2 V:r[v] > jVj)
A 9v 2 V: t[v] > ф ! r[v]; t[v] := r[v] + 1;d[v] P0 A P2 А ф > max(t) ! ф := max(t) 9(u; v) 2 E: r[u] — r[v] > w[u; v]
-> r[v] := r[u] -w[u,v] odfP0 Л P1 Л P2 Л P3g :
Корректность алгоритма можно легко показать в силу того, что P1 остается инвариантом и из отрицания предикатов следует P0 Л P2 Л P3. Завершение работы алгоритма гарантируется монотонным возрастанием r и его верхней границей. Следующая теорема задает время выполнения в наихудшем случае.
Теорема 1. Время выполнения данного алгоритма ресинхронизации в наихудшем случае ограничено сверху значением O(j Vj2 jEj).
Время выполнения алгоритма ресинхронизации в наихудшем случае будет актуальным в случае, когда каждое увеличение r приводит к «протягиванию» синхронизации по всей схеме (т.е. по |E| ребрам). Это верно только тогда, когда увеличение r перемещает все регистры в схеме. Однако в таком случае верхняя граница r равна 1, и время выполнения не превышает O(jVjjEj). С другой стороны, если значение r велико, схема разбивается регистрами на несколько меньших фрагментов, в результате чего протягивание, вызванное увеличением одного r, ограничено деревом небольшого размер.
Применение
В базовом алгоритме оптимальность P3 проверяется условием r[v] > j Vj. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство r[u] — r0[u] > r[v] — r0 [v].
Следовательно, если ввести указатель из v к u при увеличении r[v], указатели не смогут образовать цикл согласно :P3. Фактически указатели образуют лес, в котором корни имеют значение r = 0, а потомок может иметь значение r, не более чем на 1 превышающее значение его предка. Использование цикла указателей как свидетельство верности P3 вместо r[v] > |V|, можно значительно повысить практическую эффективность алгоритма.
Открытые вопросы
Ресинхронизация нередко используется для оптимизации длительности цикла либо количества регистров в схеме. Описанный алгоритм решает только задачу ресинхронизации с достижением минимальной длительности. Задачу ресинхронизации с достижением минимального количества регистров для заданной длительности цикла решили Лейзерсон и Сакс [1], она представлена в соответствующей статье. Их алгоритм сводит задачу к двойственной проблеме поиска сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать эффективный итеративный алгоритм для решения задачи о минимальном количестве регистров, схожий с алгоритмом Чжоу.
Экспериментальные результаты
Результаты были опубликованы Чжоу [3] по итогам сравнения времени выполнения алгоритма с эффективной эвристикой под названием ASTRA [ ]. Результаты прогона на эталонных тестах ISCAS89 представлены в таблице 1 из работы [3]; столбцы A и B таблицы отражают время выполнения двух этапов ASTRA.
См. также
Литература
1. Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. Algorithmica6,5-35(1991)
2. Sapatnekar, S.S., Deokar, R.B.: Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE Transactions on Computer Aided Design 15,1237-1248 (1996)
3. Zhou, H.: Deriving a new efficient algorithm for min-period retiming. In: Asia and South Pacific Design Automation Conference, Shanghai, China, January 2005
