Технологическое отображение последовательной схемы: различия между версиями

На рис. 6 изображены итерации вычисления меток для схемы на рис. 1 (1) в предположении, что целевая продолжительность цикла ф = 1 и вершины оцениваются в порядке i, x, y, z, o. В таблице отражены как текущая метка, так и соответствующий разрез для каждой вершины. В данном примере после первой итерации ни одна из меток не меняется, и выполнение процедуры завершается.

Можно показать, что процедура разметки остановится после не более чем n(n - 1) итераций [ ]. Следующая лемма связывает метки и отображение:

Лемма 2. N имеет отображение с продолжительностью цикла ' в том и только том случае, если процедура разметки возвращает значение «успех».

После того успешного вычисления меток для всех вершин можно построить отображение, начиная с первичных выходов. В каждой вершине v процедура выбирает разрез, реализующий метку вершины, а затем переходит к выбору разреза для u, если ud входит в состав разреза, выбранного для v. На ребре, идущем из таблицы LUT для u к LUT для v, добавляется d триггеров. Для схемы на рис. 1 (1) сгенерированное отображение, основанное на метках, найденных на рис. 6, представляет собой сеть на рис. 2 (2).

Для получения отображения с целевой продолжительностью цикла ' таблица LUT для v может быть ресинхронизирована на \l{v)l<p~\ — 1. Для схемы на рис. 1 (1) окончательное отображение после ресинхронизации представлено на рис. 2 (3).