Алгоритм динамического программирования для оптимизации дерева буферизации по числу буферов и инверторов

Раздел находится в стадии актуализации

Вставка буферных элементов в цифровых схемах необходима для контроля задержек в межсоединениях, которые играют доминирующую роль в производительности современных субмикронных СБИС. Синтез деревьев буферизации и их укладка на кристалле осложнены дефицитом свободного места после размещения основных логических вентилей, а также ограничениями потребляемой мощности. Использование инверторов в качестве буферных элементов, как правило, более эффективно с точки зрения площади, потребляемой мощности и временны́х характеристик. Однако необходимо соблюдать четность инверторов в дереве на пути до любого приемника для сохранения логики работы схемы. Для этого применяются различные эвристические методы, комбинирующие использование инверторов и буферов, но оптимальность получаемых решений исследована недостаточно. В работе представлен алгоритм для оптимизации заданного буферного дерева, основанный на динамическом программировании и заменяющий максимально возможное число буферов на инверторы. Алгоритм имеет линейную временну́ю и пространственную сложности и достаточно прост в реализации. Проведен статистический анализ эффективности найденных оптимальных решений в сравнении с результатами известной простой эвристики. Установлено, что наибольшая эффективность достигается в случаях, когда конечные приемники сигнала подключены только к листьям буферного дерева: доля буферов снижается в среднем в 1,7 раза, максимум – примерно в 3 раза по сравнению с эвристическим решением.
Малинаускас Костас Костович
Национальный исследовательский университет «МИЭТ», Россия, 124498, г. Москва, г. Зеленоград, пл. Шокина, 1

124498, г. Москва, г. Зеленоград, площадь Шокина, дом 1, МИЭТ, ауд. 7231

+7 (499) 734-62-05
magazine@miee.ru