Восстановление синхронизации - это метод перемещения структурного расположения защелок или регистров в цифровой схеме для улучшения ее производительности, площади и / или характеристик мощности таким образом, чтобы сохранить ее функциональное поведение на ее выходах. Ретиминг был впервые описан Чарльзом Э. Лейзерсоном и Джеймсом Б. Саксом в 1983 году. [1]
Этот метод использует ориентированный граф, в котором вершины представляют собой асинхронные комбинационные блоки, а направленные ребра представляют собой серию регистров или защелок (количество регистров или защелок может быть нулевым). Каждая вершина имеет значение, соответствующее задержке в комбинационной схеме, которую она представляет. После этого можно попытаться оптимизировать схему, перемещая регистры с выхода на вход и наоборот - очень похоже на нажатие пузыря . Можно использовать две операции: удаление регистра с каждого входа вершины при добавлении регистра ко всем выходам и, наоборот, добавление регистра к каждому входу вершины и удаление регистра со всех выходов. Во всех случаях, если правила соблюдаются, схема будет иметь такое же функциональное поведение, как и до восстановления синхронизации.
Формальное описание
Первоначальная формулировка проблемы восстановления синхронизации, описанная Лейзерсоном и Саксом, выглядит следующим образом. Учитывая ориентированный граф чьи вершины представляют логические элементы или элементы комбинационной задержки в схеме, предположим, что существует направленное ребромежду двумя элементами, которые связаны напрямую или через один или несколько регистров. Пусть вес каждого ребра быть количеством регистров, присутствующих вдоль края в исходной схеме. Позволять- задержка распространения через вершину. Целью повторной синхронизации является вычисление целочисленного значения запаздывания. для каждой вершины такой, что восстановленный вес каждого ребра неотрицательно. Есть доказательство того, что это сохраняет функциональность вывода. [2]
Минимизация периода времени с помощью сетевого потока
Чаще всего используется повторная синхронизация, чтобы минимизировать период времени . Простым методом оптимизации периода тактов является поиск минимально возможного периода (например, с использованием двоичного поиска ).
Возможность часового периода можно проверить одним из нескольких способов. Приведенная ниже линейная программа возможна тогда и только тогда, когда- допустимый тактовый период. Позволять быть минимальным количеством регистров на любом пути от к (если такой путь существует), и максимальная задержка на любом пути от к с регистрами W (u, v). Двойником этой программы является проблема обращения с минимальными затратами , которая может быть эффективно решена как сетевая проблема. Ограничения этого подхода связаны с перечислением и размером а также матрицы.
Дано | и целевой тактовый период | |
Находить | ||
Такой, что | ||
если |
Минимизация периода времени с помощью MILP
В качестве альтернативы, осуществимость периода часов может быть выражена как смешанная целочисленная линейная программа (MILP). Решение будет и действительная функция задержки. будет возвращен тогда и только тогда, когда срок осуществим.
Дано | и целевой тактовый период | |
Находить | а также | |
Такой, что | ||
Другие составы и расширения
Альтернативные формулировки позволяют минимизировать счетчик регистров и минимизировать счетчик регистров при ограничении задержки. Первоначальный документ включает расширения, которые позволяют рассматривать разделение по разветвлению и более общую модель задержки. Последующая работа была направлена на включение задержек регистров, [3] моделей задержки, зависимых от нагрузки, [3] и ограничений удержания. [4]
Проблемы
Ретиминг нашел промышленное применение, хотя и эпизодически. Его основной недостаток состоит в том, что кодирование состояния схемы нарушается, что значительно затрудняет отладку, тестирование и проверку. Некоторые изменения времени могут также потребовать сложной логики инициализации, чтобы схема запускалась в идентичном начальном состоянии. Наконец, изменения в топологии схемы имеют последствия для других этапов логического и физического синтеза, которые затрудняют завершение проекта .
Альтернативы
Планирование смещения часов - это связанный метод оптимизации последовательных схем. В то время как повторная синхронизация перемещает структурное положение регистров, планирование смещения часов перемещает их временное положение, планируя время прибытия тактовых сигналов. Нижняя граница достижимого минимального периода тактовой частоты обоих методов - это максимальное среднее время цикла (т. Е. Общая комбинационная задержка на любом пути, деленная на количество регистров вдоль него).
Смотрите также
Заметки
- ^ Чарльз Э. Лейзерсон, Флавио М. Роуз, Джеймс Б. Сакс (1983). «Оптимизация синхронной схемы путем восстановления синхронизации». Третья конференция Калифорнийского технологического института по очень крупномасштабной интеграции . 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 .; Сакс, Дж. Б. (1983). «Оптимизация синхронных систем». Журнал СБИС и компьютерных систем . 1 (1): 41–67.