Восстановление времени - Retiming

Восстановление синхронизации - это метод перемещения структурного расположения защелок или регистров в цифровой схеме для улучшения ее характеристик, площади и / или мощности таким образом, чтобы сохранить ее функциональное поведение на ее выходах. Ретиминг был впервые описан Чарльзом Э. Лейзерсоном и Джеймсом Б. Саксом в 1983 году.

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

Формальное описание

Первоначальная формулировка проблемы восстановления синхронизации, описанная Лейзерсоном и Саксом, выглядит следующим образом. Учитывая ориентированный граф , вершины которого представляют логические элементы или элементы комбинационной задержки в схеме, предположим, что существует направленное ребро между двумя элементами, которые связаны напрямую или через один или несколько регистров. Пусть вес каждого ребра равен количеству регистров, присутствующих на ребре в исходной схеме. Позвольте быть задержкой распространения через вершину . Целью восстановления синхронизации является вычисление целочисленного значения запаздывания для каждой вершины таким образом, чтобы восстановленный вес каждого ребра был неотрицательным. Есть доказательство того, что это сохраняет функциональность вывода. ${\ Displaystyle G: = (V, E)}$ ${\ Displaystyle е: = (и, v)}$ ${\ Displaystyle ш (е)}$ ${\ displaystyle e}$ ${\ displaystyle d (v)}$ ${\ displaystyle v}$ ${\ Displaystyle г (v)}$ ${\ displaystyle w_ {r} (e): = w (e) + r (v) -r (u)}$

Минимизация периода времени с помощью сетевого потока

Чаще всего используется повторная синхронизация для минимизации периода времени . Простым методом оптимизации периода тактов является поиск минимально возможного периода (например, с использованием двоичного поиска ).

Возможность тактового периода можно проверить одним из нескольких способов. Приведенная ниже линейная программа возможна тогда и только тогда, когда это допустимый тактовый период. Пусть будет минимальным количеством регистров на любом пути от до (если такой путь существует), и это максимальная задержка на любом пути от до с регистрами W (u, v). Двойником этой программы является проблема обращения с минимальными затратами , которая может быть эффективно решена как сетевая проблема. Ограничения этого подхода вытекают из перечисления и размера и матриц. ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ Displaystyle W (и, v)}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ Displaystyle D (и, v)}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle W}$ ${\ displaystyle D}$

Дано	${\ Displaystyle ш (е), W (и, v), D (и, v)}$ и целевой период часов ${\ displaystyle T}$
найти	${\ Displaystyle г (v): от V \ до \ mathbb {Z}}$
Такой, что
	${\ Displaystyle г (и) -r (v)}$	${\ Displaystyle \ Leq ш (е)}$
	${\ Displaystyle г (и) -r (v)}$	${\ Displaystyle \ Leq W (и, v) -1}$ если ${\ Displaystyle D (и, v)> Т}$

Минимизация периода времени с помощью MILP

В качестве альтернативы, возможность тактового периода может быть выражена как линейная программа со смешанными целыми числами (MILP). Решение будет существовать, и будет возвращена действительная функция задержки , если и только если период допустим. ${\ displaystyle T}$ ${\ Displaystyle г (v)}$

Дано	${\ Displaystyle ш (е), d (v)}$ и целевой период часов ${\ displaystyle T}$
найти	${\ Displaystyle г (v): от V \ до \ mathbb {Z}}$ и ${\ Displaystyle R (v): V \ to {\ mathcal {R}}}$
Такой, что
	${\ Displaystyle r (v) -R (V)}$	${\ Displaystyle \ leq -d (v) / T}$
	${\ Displaystyle R (v) -r (v)}$	${\ displaystyle \ leq 1}$
	${\ Displaystyle г (и) -r (v)}$	${\ Displaystyle \ Leq ш (е)}$
	${\ Displaystyle R (u) -R (v)}$	${\ Displaystyle \ Leq ш (е) -d (v) / Т}$

Другие составы и расширения

Альтернативные формулировки позволяют минимизировать счетчик регистров и минимизировать счетчик регистров при ограничении задержки. В первоначальный документ включены расширения, которые позволяют рассматривать разделение по разветвлению и более общую модель задержки. Последующая работа была направлена на включение задержек регистров, моделей задержки, зависящих от нагрузки, и ограничений удержания.

Проблемы

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

Альтернативы

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

Смотрите также

Ноты

^ Чарльз Э. Лейзерсон, Флавио М. Роуз, Джеймс Б. Сакс (1983). «Оптимизация синхронной схемы путем восстановления синхронизации». Третья конференция Caltech по очень крупномасштабной интеграции . Springer: 87–116. DOI : 10.1007 / 978-3-642-95432-0_7 .CS1 maint: несколько имен: список авторов ( ссылка )
^ Чарльз Э. Лейзерсон, Джеймс Б. Сакс (июнь 1991 г.). «Восстановление синхронизации синхронных схем». Алгоритмика . Springer. 6 (1): 5–35. DOI : 10.1007 / BF01759032 .
^ ^a ^b К. Н. Лалгуди, М.К. Папаэфтимиу, Повторная синхронизация схем, запускаемых фронтом, в рамках общих моделей задержки , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol.16, no.12, pp.1393-1408, декабрь 1997.
^ MC Papaefthymiou, Асимптотически эффективное восстановление синхронизации при ограничениях установки и удержания , Международная конференция IEEE / ACM по автоматизированному проектированию, 1998.

Ссылки

Лейзерсон, 1С. E .; Saxe, JB (1983). «Оптимизация синхронных систем». Журнал СБИС и компьютерных систем . 1 (1): 41–67.

внешние ссылки

[1] Чарльз Э. Лейзерсон, Флавио М. Роуз, Джеймс Б. Сакс (1983). «Оптимизация синхронной схемы путем восстановления синхронизации». Третья конференция Caltech по очень крупномасштабной интеграции . Springer: 87–116. DOI : 10.1007 / 978-3-642-95432-0_7 .CS1 maint: несколько имен: список авторов ( ссылка )

[one-2] Чарльз Э. Лейзерсон, Джеймс Б. Сакс (июнь 1991 г.). «Восстановление синхронизации синхронных схем». Алгоритмика . Springer. 6 (1): 5–35. DOI : 10.1007 / BF01759032 .

[two-3] К. Н. Лалгуди, М.К. Папаэфтимиу, Повторная синхронизация схем, запускаемых фронтом, в рамках общих моделей задержки , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol.16, no.12, pp.1393-1408, декабрь 1997.

[three-4] MC Papaefthymiou, Асимптотически эффективное восстановление синхронизации при ограничениях установки и удержания , Международная конференция IEEE / ACM по автоматизированному проектированию, 1998.

Languages

In other projects