WikiDer > Повторная синхронизация

Retiming

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

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

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

Первоначальная формулировка проблемы восстановления синхронизации, описанная Лейзерсоном и Саксом, выглядит следующим образом. Учитывая ориентированный граф чьи вершины представляют логические ворота или комбинационные элементы задержки в цепи, предположим, что есть направленный край между двумя элементами, которые связаны напрямую или через один или несколько регистров. Пусть масса каждого края быть количеством регистров, присутствующих вдоль края в исходной схеме. Позволять быть Задержка распространения через вершину . Целью восстановления синхронизации является вычисление целого числа отставание ценить для каждой вершины такой, что восстановленный вес каждого ребра неотрицательно. Есть доказательство того, что это сохраняет функциональность вывода.[2]

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

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

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

Данный и целевой период часов
Находить
Такой, что
если

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

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

Данный и целевой период часов
Находить и
Такой, что

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

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

Проблемы

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

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

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

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

Примечания

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

Рекомендации

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

внешняя ссылка