Алгоритм многоуровневой оптимизации комбинационных логических схем

И.В. Коновалов,
аспир., ivan-k85@mail.ru
ИПУ РАН, г. Москва

В.Н. Коновалов

ст. препод.,

КФ МГТУ им. Н.Э. Баумана, г. Калуга

Аннотация

Рассматривается алгоритм минимизации логических схем, полученных в результате многоуровневой декомпозиции. Алгоритм основан на анализе схемы, введении недоопределённости в логические последовательности, генерируемые на входах логических элементов и поиске элементов с соответствующими логическими последовательностями, которые можно соединить между собой. Это позволяет сократить соответствующие элементы схемы.

Abstract

An algorithm of minimizing of logical circuits obtained as a result of multilevel decomposition is considered. Algorithm based on circuit analysis, deployment of underdetermined elements in logical orders generated on logical element’s inputs and finding elements with consistent logical orders, which can be connected. This brings removal of appropriate parts of circuit.

Одним из завершающих этапов логического проектирования цифровых схем является покрытие или технологическое отображение (technology mapping) – преобразование технологически независимой схемы, полученной в результате многоуровневой декомпозиции и детализации и состоящей из различных двухвходовых логических блоков, в эквивалентную схему в целевом технологическом базисе [3, 5, 6].

рис. 1. Блок-схема алгоритма многоуровневой оптимизации

Основными критериями оптимизации при многоуровневом синтезе являются:

1) длина критического пути при прохождении сигнала от входа к выходу схемы (максимальная задержка сигнала);

2) площадь кристалла, занимаемая логической сетью. От указанной площади, в конечном итоге, зависит стоимость проектируемой схемы. Причём, при определении площади сети часто учитывается не только площадь логических элементов, но и площадь межсоединений [1, 2]. Это условие ставит не только задачу минимизации количества узлов логической сети (equivalent gate), но и количества связей между ними (slices).

Как правило, оптимизацию комбинационных схем связывают с минимизацией систем булевых функций. Методы решения указанной задачи являются классическими и заключаются в нахождении ДНФ, минимальной по числу литералов (минимальной ДНФ), либо по числу конъюнкций (кратчайшей ДНФ) [2, 4, 7].

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

1) исключение из схемы очевидных избыточных элементов;

2) анализ схемы с учётом логической недоопределённости.

Схема алгоритма приведена на рис. 1

Рассмотрим более подробно выполнение указанных этапов.

Предварительная оптимизация схемы

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

Цепочки инверторов могут образовываться в схемах при покрытии элементами «2И-НЕ», либо «2ИЛИ-НЕ», поскольку для совпадения числовых последовательностей при формальном замещении покрываемых блоков требуется инвертирование входных или выходных последовательностей покрывающих элементов [6].

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

Анализ схемы с учётом логической недоопределённости

В начале второго этапа оптимизации проводится полный анализ схемы, который позволяет получить числовые последовательности на выходах всех элементов и ещё раз убедиться в правильности предшествующих процедур синтеза и первого этапа оптимизации. Далее от выхода к входу выполняется анализ отдельных элементов с учётом возможной логической недоопределённости их входных числовых последовательностей. При таком анализе в поступающие на входы логических элементов числовые последовательности искусственно вводится неопределённость (звёздочки). Если, например, на входы элемента «2ИЛИ» поступают две какие-либо последовательности, то одну из них можно фиксировать, а во вторую ввести звёздочки на тех местах, на которых в первой последовательности стоят логические единицы. Ведь, если на один из входов элемента «2ИЛИ» подаётся единица, то на его выходе будет присутствовать единица независимо от состояния на втором входе.

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

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

Если подходящая числовая последовательность не найдена, то последовательность проанализированного входа фиксируется и неопределённость вводится в последовательность другого входа.

При анализе входов элемента «2И» всё делается точно так же, но звёздочки в анализируемой последовательности вводятся на тех местах, на которых фиксированная последовательность принимает нулевое значение. Аналогичные правила формирования недоопределённых входных последовательностей можно сформулировать и для других логических элементов («2И-НЕ», «2ИЛИ-НЕ» и т.д.).

Однако следует заметить, что при выполнении рассмотренных выше операций, связанных с изменением топологии схемы, нельзя допускать образование петель обратной связи, которые могут превратить комбинационное устройство в конечный автомат с памятью. То есть, если найдена непротиворечивая последовательность у далее стоящего элемента, и он подчинён исследуемому, то эти элементы соединять нельзя.

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

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

рис. 2

Процедуру многоуровневой оптимизации удобно рассмотреть на примере схемы мультиплексора 2/1, характеризуемого числовой последовательностью 0011  0101 и представляющего собой наиболее общий вариант трёхвходового логического блока, выделяемого из схемы в процессе детализации [3]. Один из вариантов схемы рассматриваемого мультиплексора представлен на рис.2.

Проведём полный анализ сххемы [5].

Проведём повторный анализ блока D, но на этот раз зафиксируем последовательность, поступающую с выхода блока A, и построим последовательность C*, которая не нарушит выходную последовательность схемы.

Поскольку блок D выполняет операцию «ИЛИ», то наличие двух логических единиц в последовательности A позволяет соответствующие элементы последовательности C* заменить на звёздочки. Выходная последовательность схемы при этом не изменится:

Последовательность C* среди последовательностей, формируемых на выходах элементов рассматриваемой схемы, обнаружить не удалось, поэтому, одноуровневая оптимизация схемы оказывается невозможной. Однако, проведём повторный анализ теперь уже для блока C с учётом введённых в схему изменений. Для этого зафиксируем поступающую на его вход последовательность 20 и попытаемся подобрать последовательность B**, которая не нарушит построенной выше последовательности C*. При выполнении указанной процедуры следует учесть, что блок C выполняет операцию «И», и наличие логических нулей в последовательности 20 позволяет соответствующие элементы последовательности B** заменить на звёздочки. Кроме того, звёздочкой можно заменить и восьмой элемент рассматриваемой последовательности, поскольку на этом месте в последовательности C* также находится символ «*»:

Полученная таким образом числовая последовательность B** не противоречит инверсии входной переменной 40 (1111  0000). Следовательно, блок B из схемы можно исключить, а на нижний (младший) вход блока C подать инвертированную входную переменную 40. Чтобы не вводить в схему лишний инвертор, можно соответствующим образом преобразовать числовую последовательность блока C – 0010. Такое преобразование соответствует инвертированию его младшей входной переменной [6]. Оптимизированная схема мультиплексора 2/1 представлена на рис. 3. Повторный анализ полученной схемы позволяет сделать вывод о том, что процедура двухуровневой оптимизации не нарушила логику работы синтезируемой схемы.

рис. 3

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

Предлагаемый алгоритм многоуровневой оптимизации имеет несколько преимуществ по сравнению с уже существующими. Опишем вкратце особенности рассматриваемого алгоритма, а также отметим все его преимущества:

· алгоритм не привязан к конкретному логическому базису, что даёт возможность проведения процедуры оптимизации на различных этапах синтеза: на этапе детализации (предварительная оптимизация), а затем на этапе покрытия (окончательная оптимизация);

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

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

Литература

1. Бибило П.Н., Леончик П.В. Исследование эффективности логической минимизации в процессе синтеза комбинационных схем // Информатика. – 2007. – № 1. – С. 22–29.

2. Закревский А.Д., Торопов Н.Р. Минимизация булевых функций многих переменных в классе ДНФ – итеративный метод и программная реализация // Прикладная дискретная математика. – 2009. – № 1. – С. 5–14.

3. Детализация комбинационных логических схем для покрытия простыми логическими элементами / Коновалов В.Н., Белов А.А., Коновалов И.В. [и др.] // Труды МГТУ № 594. Методы исследования и проектирования сложных технических систем: сборник статей. – М.: Изд. МГТУ им. Н.Э. Баумана, 2007. – С. 103–113.

4. Леончик П.В. Минимизация систем булевых функций в классе дизъюнктивных нормальных форм // Информатика. – 2006. – № 1. – С. 88–96.

5. Логический синтез комбинационных схем на основе методов декомпозиции / Коновалов В.Н., Коновалов И.В., Белов А.А. [и др.] // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. – Тула: Издательство ТулГУ, 2006. – Вып. 3: Системы управления. – Т. 1. – С. 231–233.

6. Подход к покрытию комбинационных схем двухвходовыми логическими элементами / Коновалов В.Н., Белов А.А., Коновалов И.В. [и др.] // Труды МГТУ № 594. Методы исследования и проектирования сложных технических систем: сборник статей. – М.: Изд. МГТУ им. Н.Э. Баумана, 2007. – С. 114–122.

7. Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А. Метод минимизации системы полностью определённых булевых функций // Информатика. – 2008. – № 2. – С. 102–110.

8. Угрюмов Е.П. Цифровая схемотехника: учеб. пособие для вузов. – 2-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2004. – 800 с.