изменение времени

Ретайминг — это метод изменения структурного расположения защелок или регистров в цифровой схеме для улучшения ее производительности, площади и/или характеристик мощности таким образом, чтобы сохранить ее функциональное поведение на выходах. Изменение времени было впервые описано Чарльзом Лейзерсоном и Джеймсом Саксом в 1983 году. ^[1]

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

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

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

Минимизация периода тактирования с сетевым потоком

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

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

Данный	$w(e),W(u,v),D(u,v)$ и целевой период часов $T$
Находить	$r(v):V\to \mathbb {Z}$
Такой, что
	$r(u)-r(v)$	$\leq w(e)$
	$r(u)-r(v)$	$\leq W(u,v)-1$ если $D(u,v)>T$

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

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

Данный	$w(e),d(v)$ и целевой период часов $T$
Находить	$r(v):V\to \mathbb {Z}$ и $R(v):V\to {\mathcal {R}}$
Такой, что
	$r(v)-R(V)$	$\leq -d(v)/T$
	$R(v)-r(v)$	$\leq 1$
	$r(u)-r(v)$	$\leq w(e)$
	$R(u)-R(v)$	$\leq w(e)-d(v)/T$

Другие формулировки и расширения

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

Проблемы

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

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

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

См. также

Примечания

^ Чарльз Э. Лейзерсон, Флавио М. Роуз, Джеймс Б. Сакс (1983). «Оптимизация синхронной схемы путем изменения времени». Третья конференция Калифорнийского технологического института по очень крупномасштабной интеграции . Спрингер: 87–116. дои : 10.1007/978-3-642-95432-0_7 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Чарльз Э. ЛейзерсонДжеймс Б. Сакс (июнь 1991 г.). «Восстановление синхронной схемы». Алгоритмика . 6 (1). Спрингер: 5–35. дои : 10.1007/BF01759032 . S2CID 18674287 .
^ Jump up to: Перейти обратно: ^а ^б К. Н. Лалгуди, М. К. Папаефтимиу, Повторная синхронизация схем, запускаемых по фронту, в соответствии с общими моделями задержки , Транзакции IEEE по автоматизированному проектированию интегральных схем и систем , том 16, № 12, стр. 1393-1408, декабрь 1997 г.
^ MC Papaefthymiou, Асимптотически эффективное восстановление времени при ограничениях на установку и удержание , Международная конференция IEEE/ACM по автоматизированному проектированию, 1998.

Ссылки

Лейзерсон, 1С. Э.; Сакс, JB (1983). «Оптимизация синхронных систем». Журнал СБИС и компьютерных систем . 1 (1): 41–67. {{cite journal}}: CS1 maint: числовые имена: список авторов ( ссылка )

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

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

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

[two-3] Jump up to: Перейти обратно: ^а ^б К. Н. Лалгуди, М. К. Папаефтимиу, Повторная синхронизация схем, запускаемых по фронту, в соответствии с общими моделями задержки , Транзакции IEEE по автоматизированному проектированию интегральных схем и систем , том 16, № 12, стр. 1393-1408, декабрь 1997 г.

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

[1]

[2]

[3]

[4]