Ресинхронизация схемы: инкрементный подход
Ключевые слова и синонимы
Ресинхронизация с достижением минимальной длительности
Постановка задачи
Ресинхронизация схемы является одной из самых эффективных техник структурной оптимизации для последовательных схем. Она перемещает регистры внутри схемы, не меняя ее функции. Задача ресинхронизации с достижением минимальной длительности стремится минимизировать самую долгую задержку между любыми двумя последовательными регистрами, которая определяет длительность такта.
Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф [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]
| Название | Кол-во | Длительность такта | [math]\displaystyle{ \sum r }[/math] | Кол-во | Время | ASTRA | ||
|---|---|---|---|---|---|---|---|---|
| вентилей | до | после | обновлений | A(s) | B(s) | |||
| s1423 | 490 | 166 | 127 | 808 | 7619 | 0,02 | 0,03 | 0,02 |
| s1494 | 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 |
| s13207 | 2573 | 143 | 82 | 4086 | 28395 | 0,12 | 0,38 | 0,12 |
| s15850 | 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. Экспериментальные результаты
Для завершения разработки алгоритма осталось реализовать проверку [math]\displaystyle{ \neg P3 }[/math]. Из предыдущего обсуждения мы уже знаем, что из [math]\displaystyle{ \neg P3 }[/math] следует, что существует такая вершина u, что [math]\displaystyle{ r[u] - r'[u] \ge r[v] - r'[v] \; }[/math] после каждого увеличения r[v]. Это означает, что [math]\displaystyle{ max_{v \in V} \; r[v] - r'[v] }[/math] не будет увеличиваться. Иначе говоря, существует по меньшей мере одна вершина v, у которой r[v] не будет меняться. До увеличения r[v] имеет место соотношение [math]\displaystyle{ w_{u \rightsquigarrow v} - r[u] + r[v] \le 0 \; }[/math], где [math]\displaystyle{ w_{u \rightsquigarrow v} \ge 0 \; }[/math] – исходное количество регистров на одном пути из u в v, в результате чего неравенство [math]\displaystyle{ r[v] - r[u] \le 1 \; }[/math] остается верным даже после увеличения r[v]. Из этого следует, что будет по меньшей мере i + 1 вершин, у которых r не превышает i для [math]\displaystyle{ 0 \le i \lt |V| \; }[/math]. Иными словами, алгоритм может по-прежнему увеличивать r, и когда какое-либо значение r достигнет |V|, это покажет, что условие P3 удовлетворяется. Таким образом, полный алгоритм имеет следующую форму:
[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{ (\forall \; v \in V: r[v] \lt |V|) }[/math] [math]\displaystyle{ \and \; \exist \; v \in V: t[v] \ge \phi \to r[v], t[v] := r[v] + 1, d[v] }[/math] [math]\displaystyle{ (\exist \; v \in V: r[v] \ge |V|) }[/math] [math]\displaystyle{ \and \; \exist \; v \in V: t[v] \ge \phi \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].
Корректность алгоритма можно легко показать в силу того, что P1 остается инвариантом и из отрицания предикатов следует [math]\displaystyle{ P0 \and P2 \and P3 \; }[/math]. Завершение работы алгоритма гарантируется монотонным возрастанием r и его верхней границей. Следующая теорема задает время выполнения в наихудшем случае.
Теорема 1. Время выполнения данного алгоритма ресинхронизации в наихудшем случае ограничено сверху значением [math]\displaystyle{ O(|V|^2 \; |E|) }[/math].
Время выполнения алгоритма ресинхронизации в наихудшем случае будет актуальным в случае, когда каждое увеличение r приводит к «протягиванию» синхронизации по всей схеме (т.е. по |E| ребрам). Это верно только тогда, когда увеличение r перемещает все регистры в схеме. Однако в таком случае верхняя граница r равна 1, и время выполнения не превышает O(|V| |E|). С другой стороны, если значение r велико, схема разбивается регистрами на несколько меньших фрагментов, в результате чего протягивание, вызванное увеличением одного r, ограничено деревом небольшого размера.
Применение
В базовом алгоритме оптимальность P3 проверяется условием [math]\displaystyle{ r[v] \ge |V| \; }[/math]. Однако в большинстве случаев условие оптимальности можно обнаружить намного раньше. Поскольку при каждом возрастании r[v] должна существовать «вершина-хранитель» u, такая, что после выполнения действия будет верно неравенство [math]\displaystyle{ r[u] - r'[u] \ge r[v] - r'[v] \; }[/math]. Следовательно, если ввести указатель из v на u при увеличении r[v], указатели не смогут образовать цикл согласно [math]\displaystyle{ \neg P3 }[/math]. Фактически указатели образуют лес, в котором корни имеют значение r = 0, а потомок может иметь значение r, не более чем на 1 превышающее значение его предка. Использование цикла указателей как свидетельство верности P3 вместо [math]\displaystyle{ r[v] \ge |V| \; }[/math], можно значительно повысить практическую эффективность алгоритма.
Открытые вопросы
Ресинхронизация обычно используется для оптимизации длительности цикла либо количества регистров в схеме. Описанный алгоритм решает только задачу ресинхронизации с достижением минимальной длительности. Задачу ресинхронизации с достижением минимального количества регистров для заданной длительности цикла решили Лейзерсон и Сакс [1], она представлена в соответствующей статье. Их алгоритм сводит задачу к двойственной проблеме поиска сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать эффективный итеративный алгоритм для решения задачи о минимальном количестве регистров, схожий с алгоритмом Чжоу.
Экспериментальные результаты
Результаты были опубликованы Чжоу [3] по итогам сравнения времени выполнения алгоритма с эффективной эвристикой под названием ASTRA [2]. Результаты прогона на эталонных тестах 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
