Оптимизация логики

Процесс в цифровой электронике и проектировании интегральных схем

Логическая оптимизация — это процесс поиска эквивалентного представления указанной логической схемы при одном или нескольких указанных ограничениях. Этот процесс является частью логического синтеза, применяемого в цифровой электронике и проектировании интегральных схем .

Как правило, схема ограничена минимальной площадью чипа, соответствующей предопределенной задержке отклика. Целью логической оптимизации данной схемы является получение наименьшей логической схемы , которая оценивает те же значения, что и исходная. ^[1] Обычно меньшая схема с той же функцией дешевле, ^[2] занимает меньше места, потребляет меньше энергии , имеет меньшую задержку и сводит к минимуму риски неожиданных перекрестных помех , опасность задержки обработки сигнала и другие проблемы, присутствующие на наноуровне металлических структур на интегральной схеме .

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

Мотивация

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

С появлением логического синтеза одной из самых больших проблем, с которой столкнулась отрасль автоматизации электронного проектирования (EDA), стало нахождение наиболее простого схемного представления заданного описания проекта. ^{[nb 1]} В то время как двухуровневая логическая оптимизация уже давно существовала в форме алгоритма Куайна-Маккласки , за которым позже последовал эвристический логический минимизатор Espresso , быстрое улучшение плотности микросхем и широкое принятие языков описания оборудования для описания схем формализовали область логической оптимизации в том виде, в каком она существует сегодня, включая Logic Friday (графический интерфейс), Minilog и ESPRESSO-IISOJS (многозначная логика). ^[3]

Методы

Методы упрощения логических схем в равной степени применимы к минимизации булевых выражений.

Классификация

Сегодня логическая оптимизация делится на различные категории:

На основе схемного представления

Двухуровневая логическая оптимизация

Многоуровневая логическая оптимизация

На основе характеристик схемы

Последовательная логическая оптимизация

Комбинационная логическая оптимизация

По типу исполнения

Графические методы оптимизации

Табличные методы оптимизации

Алгебраические методы оптимизации

Графические методы

Графические методы представляют требуемую логическую функцию диаграммой, представляющей логические переменные и значение функции. Манипулируя диаграммой или проверяя ее, можно устранить много утомительных вычислений. Графические методы минимизации для двухуровневой логики включают:

• Диаграмма Эйлера (также известная как круг Эйлера ) (1768) Леонарда П. Эйлера (1707–1783)
• Диаграмма Венна (1880 г.) Джона Венна (1834–1923)
• Карта Карно (1953) Мориса Карно

Минимизация булевых выражений

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

Для случая, когда булева функция задана схемой (то есть мы хотим найти эквивалентную схему минимально возможного размера), долгое время предполагалось, что задача минимизации неограниченной схемы является -полной по временной сложности , и этот результат был окончательно доказан в 2008 году ^[4] , но существуют эффективные эвристики, такие как карты Карно и алгоритм Куайна-Маккласки , которые облегчают этот процесс. ${\displaystyle \Sigma _{2}^{P}}$

Методы минимизации булевых функций включают в себя:

• Алгоритм Куайна-МакКласки
• Метод Петрика

Оптимальные многоуровневые методы

Методы, которые находят оптимальные схемные представления булевых функций, часто называются в литературе точным синтезом . Из-за вычислительной сложности точный синтез поддается обработке только для небольших булевых функций. Недавние подходы сопоставляют задачу оптимизации с задачей выполнимости булевых функций . ^{[5] [6]} Это позволяет находить оптимальные схемные представления с помощью решателя SAT .

Эвристические методы

Эвристический метод использует установленные правила, которые решают практически полезное подмножество гораздо большего возможного набора проблем. Эвристический метод может не давать теоретически оптимального решения, но если он полезен, то обеспечит большую часть желаемой оптимизации с минимальными усилиями. Примером компьютерной системы, которая использует эвристические методы для логической оптимизации, является Espresso heuristic logic minimumr .

Двухуровневые и многоуровневые представления

В то время как двухуровневое представление схем строго относится к уплощенному виду схемы в терминах SOP ( сумма-произведений ) — что больше применимо к реализации PLA проекта ^{[ требуется разъяснение ]} — многоуровневое представление является более общим видом схемы в терминах произвольно соединенных SOP, POS ( произведение-сумм ), факторизованной формы и т. д. Алгоритмы оптимизации логики обычно работают либо со структурным (SOP, факторизованная форма), либо с функциональным представлением ( бинарные диаграммы решений , алгебраические диаграммы решений ) схемы. В форме суммы-произведений (SOP) вентили И образуют наименьшую единицу и сшиваются вместе с помощью OR, тогда как в форме произведения-сумм (POS) все наоборот. Форма POS требует скобок для группировки терминов OR вместе под вентилями И, потому что OR имеет более низкий приоритет, чем AND. Обе формы — SOP и POS — прекрасно переводятся в логику схемы.

Если у нас есть две функции F ₁ и F ₂ :

${\displaystyle F_{1}=AB+AC+AD,\,}$

${\displaystyle F_{2}=A'B+A'C+A'E.\,}$

Приведенное выше двухуровневое представление использует шесть терминов продукта и 24 транзистора в КМОП-представлении.

Функционально эквивалентное представление в многоуровневом представлении может быть:

П = В + С.​

Ф ₁ = АП + АД .

Ф ₂ = А'П + А'Е .

Хотя количество уровней здесь равно 3, общее количество терминов произведения и литералов уменьшается ^{[ квантифицировать ]} из-за совместного использования термина B + C.

Аналогично мы различаем комбинационные схемы и последовательные схемы . Комбинационные схемы выдают свои выходы только на основе текущих входов. Они могут быть представлены булевыми отношениями . Некоторые примеры — приоритетные кодеры , двоичные декодеры , мультиплексоры , демультиплексоры .

Последовательные схемы производят свой выход на основе как текущих, так и прошлых входов, в зависимости от тактового сигнала, чтобы отличать предыдущие входы от текущих входов. Они могут быть представлены конечными автоматами. Некоторые примеры — триггеры и счетчики .

Пример

Оригинальный и упрощенный пример схемы

Хотя существует множество способов минимизировать схему, это пример, который минимизирует (или упрощает) булеву функцию. Булева функция, выполняемая схемой, напрямую связана с алгебраическим выражением, из которого реализована функция. ^[7] Рассмотрим схему, используемую для представления . Очевидно, что в этом утверждении используются два отрицания, две конъюнкции и дизъюнкция. Это означает, что для построения схемы понадобятся два инвертора , два вентиля И и вентиль ИЛИ . ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)}$

Схема может быть упрощена (минимизирована) путем применения законов булевой алгебры или использования интуиции. Поскольку пример утверждает, что является истинным, когда является ложным, и наоборот, можно сделать вывод, что это просто означает . С точки зрения логических вентилей неравенство просто означает вентиль XOR (исключающее ИЛИ). Следовательно, . Тогда две схемы, показанные ниже, эквивалентны, что можно проверить с помощью таблицы истинности : ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\neq B}$ ${\displaystyle (A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B}$

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

• Диаграмма бинарных решений (BDD)
• Неважно состояние
• Главный импликант
• Сложность схемы — по оценке сложности схемы
• Состав функции
• Разложение функции
• Недоиспользование ворот
• Логическая избыточность
• Гарвардская минимизирующая диаграмма (Викиверситет) (Викибуки)

Примечания

1. Размер списка соединений можно использовать для измерения простоты.

Ссылки

1. Максфилд, Клайв «Макс» (2008-01-01). «Глава 5: «Традиционные» потоки проектирования». В Максфилд, Клайв «Макс» (ред.). ПЛИС . Мгновенный доступ. Берлингтон: Newnes / Elsevier Inc. стр. 75–106. doi :10.1016/B978-0-7506-8974-8.00005-3. ISBN 978-0-7506-8974-8. Получено 2021-10-04 .
2. Баласанян, Сейран; Агагулян, Мане; Вуттке, Хайнц-Дитрих; Хенке, Карстен (2018-05-16). "Цифровая электроника" (PDF) . Бакалавр встраиваемых систем - годовая группа. Tempus. DesIRE. Архивировано (PDF) из оригинала 2021-10-04 . Получено 2021-10-04 .(101 страница)
3. Теобальд, М.; Новик, СМ (ноябрь 1998 г.). «Быстрые эвристические и точные алгоритмы для минимизации двухуровневой логики без рисков». Труды IEEE по автоматизированному проектированию интегральных схем и систем . 17 (11): 1130–1147. doi :10.1109/43.736186.
4. Бухфюрер, Дэвид; Уманс, Кристофер (январь 2011 г.). «Сложность минимизации булевой формулы» (PDF) . Журнал компьютерных и системных наук (JCSS) . 77 (1). Кафедра компьютерных наук, Калифорнийский технологический институт , Пасадена, Калифорния, США: Elsevier Inc .: 142–153. doi :10.1016/j.jcss.2010.06.011.Это расширенная версия доклада конференции: Бухфюрер, Дэвид; Уманс, Кристофер (2008). "Сложность минимизации булевых формул". Труды по автоматам, языкам и программированию (PDF) . Конспект лекций по информатике (LNCS). Том 5125. Берлин / Гейдельберг, Германия: Springer-Verlag . С. 24–35. doi :10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Архивировано (PDF) из оригинала 2018-01-14 . Получено 2018-01-14 . {{cite book}}: |work=проигнорировано ( помощь )
5. Хаасвейк, Уинстон. «Точный синтез на основе SAT: кодировки, топологические семейства и параллелизм» (PDF) . EPFL . Получено 2022-12-07 .
6. Хаасвейк, Уинстон. «Точный синтез на основе SAT для многоуровневых логических сетей» (PDF) . EPFL . Получено 2022-12-07 .
7. Mano, M. Morris; Kime, Charles R. (2014). Logic and Computer Design Fundamentals (4-е новое международное изд.). Pearson Education Limited . стр. 54. ISBN 978-1-292-02468-4.

Дальнейшее чтение

• Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). Анализ и проектирование последовательных цифровых систем. Macmillan Press . ISBN 0-33319266-4.(146 страниц)
• Де Микели, Джованни (1994). Синтез и оптимизация цифровых схем . McGraw-Hill . ISBN 0-07-016333-2.(Примечание. Главы 7–9 охватывают комбинаторную двухуровневую, комбинаторную многоуровневую и, соответственно, последовательную оптимизацию схем.)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Логический синтез и алгоритмы проверки . Springer Science & Business Media . ISBN 978-0-387-31005-3.
• Кохави, Цви; Джа, Нирадж К. (2009). «4–6». Теория коммутации и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-85748-2.
• Рутенбар, Роб А. Многоуровневая минимизация, часть I: модели и методы (PDF) (слайды лекции). Университет Карнеги-Меллона (CMU). Лекция 7. Архивировано (PDF) из оригинала 15.01.2018 . Получено 15.01.2018 ; Rutenbar, Rob A. Многоуровневая минимизация, часть II: извлечение куба/коядра (PDF) (слайды лекции). Carnegie Mellon University (CMU). Лекция 8. Архивировано (PDF) из оригинала 2018-01-15 . Получено 2018-01-15 .