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

w'[u, v] = w[u, v] + r[v] - r[u].

где in[v] – полустепень захода, а out[v] – полустепень исхода вершины v. Поскольку второй терм является константой, задачу можно переформулировать в виде следующей целочисленной линейной программы:

Поскольку в ограничения входят только разностные неравенства с целочисленными константными термами, решение ослабленной линейной программы (без целочисленных ограничений) даст только целочисленные решения. И более того, можно показать, что эта задача является двойственной к задаче нахождения потока с минимальной стоимостью в сети и, таким образом, имеет эффективное решение.

'''Теорема 1. Целочисленная линейная программа для задачи ресинхронизации с минимальной площадью является двойственной к задаче нахождения потока с минимальной стоимостью в сети.'''

<math>in[v] + \sum_{(v, w) \in E \vee D[u, v] > \phi} f[v, w] = out[v] + \sum_{(u, v) \in E \; \; D[u, v] > \phi} f[u, v] \; \; \forall v \in V</math>

Для построения потока в сети с минимальной стоимостью необходимо вначале вычислить обе матрицы, W и D. Поскольку W[u, v] – кратчайший путь из u в v относительно w, вычисление W можно выполнить при помощи алгоритма нахождения кратчайших путей между всеми парами – например, алгоритма Флойда-Уоршелла [1]. Далее, если упорядоченная пара (w[x, y], - d[x]) используется в качестве веса ребра для каждой пары <math>(x, y) \in E \;</math>, алгоритм нахождения кратчайших путей между всеми парами можно также использовать для вычисления W и D. Алгоритм будет присваивать веса при помощи покомпонентного сложения и затем сравнивать их посредством лексикографической сортировки.

Первый алгоритм Лейзерсона и Сакса [3] для ресинхронизации с минимальной длительностью был также основан на использовании матриц W и D. Этот алгоритм основывался на том, что ограничения в целочисленной линейной программе для ресинхронизации с минимальной длительности можно эффективно проверять при помощи алгоритма нахождения кратчайших путей Беллмана-Форда [1], поскольку представляют собой просто разностные неравенства. Это позволяет выполнять проверку применимости для любой заданной длительности такта <math>\varphi \;</math>. После этого бинарным поиском по диапазону возможных длительностей можно найти оптимальную длительность такта. Проверку применимости можно выполнить за время <math>O(|V|^3) \;</math>; таким образом, общее время выполнения такого алгоритма составит <math>O(|V|^3 \; log \; |V|)</math>.

В своем втором алгоритме авторы избавились от построения матриц W и D, однако по-прежнему использовали проверку применимости длительности такта во время бинарного поиска. Однако проверка применимости в этот раз выполняется при помощи инкрементной ресинхронизации и работает следующим образом. Начиная с r = 0 алгоритм вычисляет время прибытия в каждую вершину при помощи вычисления самых длинных путей в ориентированном [[ациклический граф|ациклическом графе]]. Для каждой вершины v, время прибытия в которую превышает заданную длительность <math>\varphi \;</math>, значение r[v] увеличивается на единицу. Процесс вычисления времени прибытия и увеличения r повторяется |V| — 1 раз. Если после этого какое-либо время прибытия остается большим, чем <math>\varphi \;</math>, то длительность является неприменимой. Проверку применимости можно выполнить за время O(|V| |E|), а полное время выполнения ресинхронизации с минимальной длительностью составляет O(|V| |E| log |V|).

Как можно понять из упомянутого второго алгоритма ресинхронизации с минимальной длительностью и из алгоритма Чжоу [8] в статье [[Ресинхронизация схемы: инкрементный подход]], инкрементное вычисление самых длинных комбинационных путей (т.е. путей, на которых не имеется регистров) оказывается эффективнее построения плотного графа (при помощи матриц W и D). Однако алгоритм ресинхронизации с нахождением минимальной площади по-прежнему основывается на поиске сетевого потока с минимальной стоимостью в плотном графе. Остается открытым любопытный вопрос – можно ли разработать более эффективный алгоритм на базе инкрементной ресинхронизации для решения задачи о минимальной площади.