Ресинхронизация схемы
Ключевые слова и синонимы
Ресинхронизация с достижением минимальной длительности; ресинхронизация с достижением минимальной площади
Постановка задачи
Ресинхронизация схемы является одной из самых эффективных техник структурной оптимизации для последовательных схем. Она перемещает регистры внутри схемы, не меняя ее функции. Помимо минимизации длительности такта, ресинхронизация может использоваться для минимизации количества регистров схемы. Эта задача также называется задачей ресинхронизации с достижением минимальной площади. Лейзерсон и Сакс [3] инициировали исследование ресинхронизации и предложили алгоритмы для нахождения минимальной длительности и минимальной площади. Оба алгоритма будут представлены далее.
Формальное определение задачи выглядит следующим образом. Пусть дан ориентированный граф [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{ \varphi \; }[/math]. Задача нахождения минимальной длительности ищет решение с минимальной длительностью такта.
Нотация
Чтобы гарантировать, что новые регистры – это перемещенные старые, метка [math]\displaystyle{ r: V \to \mathbb{Z} \; }[/math] используется для обозначения того, сколько регистров перемещены из исходящих ребер каждой вершины на входящие. Используя эту нотацию, можно вычислить новое количество регистров ребра (u, v) по формуле w'[u, v] = w[u, v] + r[v] — r[u].
Эту же нотацию можно расширить с ребер на пути. Однако между любыми двумя вершинами u и v может существовать более одного пути. Среди всех этих путей путь с минимальным количеством регистров будет определять, сколько регистров могут быть перемещены от u и v. Обозначим это количество за W[u, v] для любых [math]\displaystyle{ u, v \in V \; }[/math], то есть
[math]\displaystyle{ W[u, v] \triangleq min_{p: u \rightsquigarrow v} \sum_{(x, y) \in p} w[x, y] \; }[/math].
Обозначим максимальную задержку по всем путям из u в v с минимальным количеством регистров за D[u, v], то есть
[math]\displaystyle{ D[u, v] \triangleq max_{w[p: u \rightsquigarrow v] = W[u, v]} \sum_{x \in p} d[x] \; }[/math].
Ограничения
В силу данной нотации допустимая ресинхронизация r не должна иметь отрицательного количества регистров по какому-либо ребру. Подобное условие допустимости задается формулой
[math]\displaystyle{ P0(r) \triangleq \forall (u, v) \in E: w[u, v] + r[v] - r[u] \ge 0 \; }[/math].
С другой стороны, при наличии ресинхронизации r минимальное количество регистров между двумя любыми вершинами u и v задается формулой W[u, v] — r[u] + r[v]. Это количество не будет отрицательным в силу предыдущего ограничения. В случае, когда оно оказывается нулевым, будет иметь место путь с задержкой D[u, v], на котором не имеется регистров.
Таким образом, для ресинхронизации схемы с длительностью такта [math]\displaystyle{ \varphi \; }[/math] должно удовлетворяться следующее ограничение:
[math]\displaystyle{ P1(r) \triangleq \forall u, v \in V: D[u, v] \gt \phi \implies W[u, v] + r[v] - r[u] \ge 1 \; }[/math].
Основные результаты
Целью задачи ресинхронизации с минимальной площадью является минимизация общего количества регистров схемы, которое задается формулой [math]\displaystyle{ \sum_{(u, v)\in E} w'[u, v] \; }[/math]. Выражая w'[u, v] через r, получаем формулировку цели
[math]\displaystyle{ \sum_{v \in V} (in[v] - out[v]) \ast r[v] + \sum_{(u, v) \in E} w[u, v] \; }[/math],
где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы:
Минимизировать [math]\displaystyle{ \sum_{v \in V} (in[v] - out[v]) * r[v] }[/math] так, чтобы выполнялись неравенства
[math]\displaystyle{ w[u, v] + r[v] - r[u] \ge 0 \; \; \forall (u, v) \in E }[/math]
[math]\displaystyle{ W[u, v] + r[v] - r[u] \ge 1 \; \; \forall u, v \in V: D[u, v] \gt \phi }[/math]
[math]\displaystyle{ r[v] \in \mathbb{Z} \; \; \forall v \in V }[/math]
Поскольку в ограничения входят только разностные неравенства с целочисленными константными термами, решение ослабленной линейной программы (без целочисленных ограничений) даст только целочисленные решения. И более того, можно показать, что эта задача является двойственной к задаче нахождения потока с минимальной стоимостью в сети и, таким образом, имеет эффективное решение.
Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети.
Минимизировать [math]\displaystyle{ \sum_{(u, v) \in E} w[u, v] * f[u, v] + \sum_{D[u, v] \gt \phi} (W[u, v] - 1) * f[u, v] }[/math] так, чтобы выполнялись соотношения
[math]\displaystyle{ in[v] + \sum_{(v, w) \in E \vee D[u, v] \gt \phi} f[v, w] = out[v] + \sum_{(u, v) \in E \; \; D[u, v] \gt \phi} f[u, v] \; \; \forall v \in V }[/math]
[math]\displaystyle{ f[u, v] \ge 0 \; \; \forall (u, v) \in E \; \; D[u, v] \gt \phi }[/math]
На базе этой теоремы можно показать, что граф сети представляет собой плотный граф, к которому необходимо добавить новое ребро (u, v) для любой пары вершин u, v, такой, что [math]\displaystyle{ D[u, v] \gt \phi \; }[/math] .
В системе могут быть избыточные ограничения. Например, если [math]\displaystyle{ W[u, w] = W[u, v] + w[v, w] \; }[/math] и [math]\displaystyle{ D[u, v] \gt \phi \; }[/math], то ограничение [math]\displaystyle{ W[u, w] + r[w] - r[u] \ge 1 \; }[/math] является избыточным, поскольку уже имеются [math]\displaystyle{ W[u, v] + r[v] - r[u] \ge 1 \; }[/math] и [math]\displaystyle{ w[v, w] + r[w] - r[v] \ge 0 \; }[/math]. Однако проверить все ограничения на наличие избыточных и устранить их может быть непросто.
Для построения потока в сети с минимальной стоимостью необходимо вначале вычислить обе матрицы, W и D. Поскольку W[u, v] – кратчайший путь из u в v относительно w, вычисление W можно выполнить при помощи алгоритма нахождения кратчайших путей между всеми парами – например, алгоритма Флойда-Уоршелла [1]. Далее, если упорядоченная пара (w[x, y], - d[x]) используется в качестве веса ребра для каждой пары [math]\displaystyle{ (x, y) \in E \; }[/math], алгоритм нахождения кратчайших путей между всеми парами можно также использовать для вычисления W и D. Алгоритм будет присваивать веса при помощи покомпонентного сложения и затем сравнивать их посредством лексикографической сортировки.
Первый алгоритм Лейзерсона и Сакса [3] для ресинхронизации с минимальной длительностью был также основан на использовании матриц W и D. Этот алгоритм основывался на том, что ограничения в целочисленной линейной программе для ресинхронизации с минимальной длительности можно эффективно проверять при помощи алгоритма нахождения кратчайших путей Беллмана-Форда [1], поскольку представляют собой просто разностные неравенства. Это позволяет выполнять проверку применимости для любой заданной длительности такта [math]\displaystyle{ \varphi \; }[/math]. После этого бинарным поиском по диапазону возможных длительностей можно найти оптимальную длительность такта. Проверку применимости можно выполнить за время [math]\displaystyle{ O(|V|^3) \; }[/math]; таким образом, общее время выполнения такого алгоритма составит [math]\displaystyle{ O(|V|^3 \; log \; |V|) }[/math].
В своем втором алгоритме авторы избавились от построения матриц W и D, однако по-прежнему использовали проверку применимости длительности такта во время бинарного поиска. Однако проверка применимости в этот раз выполняется при помощи инкрементной ресинхронизации и работает следующим образом. Начиная с r = 0 алгоритм вычисляет время прибытия в каждую вершину при помощи вычисления самых длинных путей в ориентированном ациклическом графе. Для каждой вершины v, время прибытия в которую превышает заданную длительность [math]\displaystyle{ \varphi \; }[/math], значение r[v] увеличивается на единицу. Процесс вычисления времени прибытия и увеличения r повторяется |V| — 1 раз. Если после этого какое-либо время прибытия остается большим, чем [math]\displaystyle{ \varphi \; }[/math], то длительность является неприменимой. Проверку применимости можно выполнить за время O(|V| |E|), а полное время выполнения ресинхронизации с минимальной длительностью составляет O(|V| |E| log |V|).
Применение
Шеной и Руделл [7] реализовали алгоритмы ресинхронизации Лейзерсона и Сакса для нахождения минимального периода и минимальной площади с некоторыми изменениями ради повышения эффективности. Для задачи ресинхронизации с минимальной длительностью они реализовали второй алгоритм, а для поиска неприменимости на более раннем этапе ввели указатель от одной вершины к другой в случае, если между ними требуется наличие хотя бы одного регистра. Цикл, сформированный указателями, свидетельствует о неприменимости данной длительности. В задаче ресинхронизации с минимальной длительностью они устранили некоторую избыточность ограничений и использовали алгоритм масштабирования стоимости Голдберга-Тарьяна [2] для вычисления потока с минимальной стоимостью.
Открытые вопросы
Как можно понять из упомянутого второго алгоритма ресинхронизации с минимальной длительностью и из алгоритма Чжоу [8] в статье Ресинхронизация схемы: инкрементный подход, инкрементное вычисление самых длинных комбинационных путей (т.е. путей, на которых не имеется регистров) оказывается эффективнее построения плотного графа (при помощи матриц W и D). Однако алгоритм ресинхронизации с нахождением минимальной площади по-прежнему основывается на поиске сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать более эффективный алгоритм на базе инкрементной ресинхронизации для решения задачи о минимальной площади.
Экспериментальные результаты
Сапатнекар и Деокар [6], а также Пэн [5] предложили использовать непрерывную ресинхронизацию в качестве эффективной аппроксимации ресинхронизации с минимальной продолжительностью и сообщили о получении экспериментальных результатов. Махешвари и Сапатнекар [4] также предложили некоторые эффективные улучшения для алгоритма ресинхронизации с нахождением минимальной площади, сопроводив их экспериментальными результатами.
См. также
Литература
1. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
2. Goldberg, A.V., Tarjan, R.E.: Solving minimum cost flow problem by successive approximation. In: Proc. ACM Symposium on the Theory of Computing, pp. 7-18 (1987). Full paper in: Math. Oper. Res. 15,430^66(1990)
3. Leiserson, C.E., Saxe, J.B.: Retiming synchronous circuitry. Algorithmica6,5-35(1991)
4. Maheshwari, N., Sapatnekar, S.S.: Efficient retiming of large circuits, IEEE Transactions on Very Large-Scale Integrated Systems. 6,74-83(1998)
5. Pan, P.: Continuous retiming: Algorithms and applications. In: Proc. Intl. Conf. Comput. Design, pp. 116-121. IEEE Press, Los Almitos(1997)
6. Sapatnekar, S.S., Deokar, R.B.: Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE Trans. Comput. Aided Des. 15,1237-1248 (1996)
7. Shenoy, N., Rudell, R.: Efficient implementation of retiming. In Proc. Intl. Conf. Computer-Aided Design, pp. 226-233. IEEE Press, Los Almitos (1994)
8. Zhou, H.: Deriving a new efficient algorithm for min-period retiming. In Asia and South Pacific Design Automation Conference, Shanghai, China, Jan. ACM Press, New York (2005)
