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

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

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

Для сокращения длительности цикла переменную r необходимо изменить, сделав ее ближе к r0. Следует отметить, что в контексте ресинхронизации важны не абсолютные значения r, но их разности. Если hr, ti является решением задачи ресинхронизации, то hr + c; ti, где c 2 Z – произвольная константа, также будет являться решением. Следовательно, r может быть сделана «ближе» к r0 за счет размещения большего количества регистров между u и v, то есть либо за счет уменьшения r[u], либо за счет увеличения r[v]. Отметим, что v можно легко определить из t [v] = max(t). Независимо от того, какое значение (r[v] или r[u]) выбрано для изменения, изменение должно быть единичным, поскольку r не следует чрезмерно корректировать. Таким образом, после корректировки будут по-прежнему выполняться соотношения r[v] — r[u] < r0[v] — r0[u] или, что эквивалентно, r[v] — r0[v] < r[u] — r0[u]. Поскольку v легко определить, выберем для увеличения r[v]. Время прибытия t[v] можно незамедлительно уменьшить до d[v]. Это позволяет уточнить второе условие: