Уебная САПР комбинационных логических схем на основе методов

многоуровневой  декомпозиции

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

И.В. Коновалов,

А.А. Белов,

Калужский филиал МГТУ им. Н.Э. Баумана, sau@bmstu.kaluga.ru, г. Калуга

Бурное развитие современной интегральной микросхемотехники, особенно программируемых логических интегральных схем (ПЛИС), привело к тому, что широко распространенная алгебраическая методология логического проектирования перестала поспевать за технологическим прогрессом. Изменчивость базиса требует разработки все новых алгебраических методов. В то же время привязка к конкретному логическому базису сильно ограничивает возможности использования формальных методов синтеза.

Методы синтеза комбинационных логических схем (КЛС) можно разделить на две большие группы:

-     методы двухуровневого синтеза, предполагающие прохождение сигнала от входа комбинационной схемы к выходу через два уровня логических элементов (как правило, это элементы «И» и «ИЛИ»);

-     методы многоуровневого синтеза, целью которого является синтез схемы в виде логической сети, удовлетворяющей заданным ограничениям.

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

Кроме того, в качестве конфигурируемых логических блоков (КЛБ) современных ПЛИС типа FPGA (Field Programmable Gate Arrays) используются достаточно крупные логические модули на основе мультиплексоров или программируемых ПЗУ (LUT – Look-Up Tables). В этом случае при проектировании цифровых устройств возникает задача разделения сложной схемы на более простые части (декомпозиция), которые могут быть реализованы на указанных типах КЛБ. Декомпозиционные методы позволяют получать многоуровневые представления логических функций и являются наиболее общими методами логического синтеза цифровых схем.

При большом числе входов (более 5-6) выполнение процедур синтеза становится затруднительным даже для одной логической функции. Применение современной элементной базы (ПЛИС) и современных средств САПР может значительно упростить поставленные задачи. Однако грамотное использование методов декомпозиции в ряде случаев позволяет применить для реализации цифровых устройств менее сложные и дорогие кристаллы ПЛИС.

Можно выделить два основных вида декомпозиции – параллельную и последовательную (по типу соединения разделенных блоков). Критерием разделения является уменьшение общей сложности описания схемы. В качестве абстрактной оценки сложности можно принять величину  (где n и m – число входов и выходов схемы), которая определяет количество бит информации, необходимое для представления логической (числовой) последовательности синтезируемой схемы. Логическая последовательность представляет собой сокращенную форму таблицы истинности с линейно упорядоченными наборами входных комбинаций (от 0 до ). Выходной столбец таблицы истинности записывается в виде строки, содержащей  m-разрядных двоичных чисел. Такой способ задания комбинационных схем является инвариантным по отношению к используемому логическому базису [2]. Для схемы, состоящей из нескольких блоков, суммарная сложность определяется как сумма соответствующих величин, характеризующих каждый из блоков.

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

Параллельная декомпозиция. Исходная сложность схемы определяется выражением (1):

                                           (бит).                                     (1)

Рис. 1. Параллельная декомпозиция логических блоков

После разделения схемы на два блока (рис. 1) сложность будет составлять:

                               (бит)                          (2)

Разделение будем считать целесообразным, если в результате сложность схемы уменьшается:

                                                                         (3)

Из выражения (3) следует, что выделение параллельного блока производится в случае, если k меньше n. Это означает, что  выходов зависят фиктивно от некоторых входов . Фиктивной считается такая входная переменная, изменение которой не приводит к изменению состояний на соответствующих выходах логической схемы.

Таким образом, процедура выделения параллельного блока включает проверку существенной зависимости каждого выхода схемы от каждого из ее входов. Результаты проверки заносятся в специальную таблицу, строки которой отмечены обозначениями выходных сигналов, а столбцы – входных. В случае выявления существенной зависимости какого-либо выхода от некоторого входа, в соответствующей клетке таблицы записывается «1», в противном случае – «0». Выходы схемы, зависящие существенно не от всех входных переменных, следует выделить в отдельный (параллельный) блок. Такое разделение всегда приводит к уменьшению сложности схемы, что следует из оценки, полученной на основании выражения (3).

Последовательная декомпозиция. При последовательной декомпозиции полученная схема может быть представлена в виде рис. 2, соответствующего l-кратной разделительной декомпозиции системы логических функций, описывающих рассматриваемый блок [1,7].

 

Рис. 2. Последовательная декомпозиция

Сложность схемы после разделения не должна быть больше исходной:

                                                                          (4)

В данном случае критерий разделения блоков несколько меняется – сложность описания схемы не должна возрастать. Выражение (4) имеет физический смысл лишь при . Указанное условие является критерием разделения блоков [1], и означает, что число состояний на выходе блока 1 (рис. 2), равное , по крайней мере в два раза меньше, чем число состояний на его входах, равное . Это говорит о том, что среди всевозможных комбинаций состояний входов блока 1 существуют такие группы наборов, которые дают одну и ту же комбинацию выходных сигналов. Такие комбинации наборов состояний входов считаются неразличимыми блоком 1 (в противном случае – различимые комбинации). Очевидно, что если два каких-либо входных набора неразличимы блоком 1, то они неразличимы и всем комбинационным устройством.

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

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

 

 

Рис. 3. Параллельно-последовательная декомпозиция

Эти два блока целесообразно объединить в один параллельно-последовательный блок, поскольку сложность схемы при этом не изменится, а количество блоков уменьшится (рис. 4).

 

Рис. 4. Объединение блоков при параллельно-последовательной декомпозиции

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

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

На завершающем этапе логического проектирования производится детализация – деление схемы до элементов малой сложности (вплоть до двухвходовых блоков), соизмеримой со сложностью заданных для покрытия логических элементов. Современные микроэлектронные технологии в качестве одного из вариантов реализации коммутируемых логических блоков микросхем программируемой логики позволяют использовать цепочки полевых транзисторов с каналами p- и n-типа, на которых реализуются простые логические вентили (SLC – Simple Logic Cells). Для использования такого технологического базиса декомпозированную схему необходимо поделить до блоков малой сложности, соизмеримой со сложностью заданных для покрытия логических элементов (как правило, это двухвходовые элементы «И-НЕ», либо «ИЛИ-НЕ»). При детализации используются в основном те же алгоритмы, что и при декомпозиции, но не требуется уменьшения сложности схемы.

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

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

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

Основные идеи описанной выше методики синтеза комбинационных логических схем были предложены доцентом кафедры ЭВМ Калужского филиала МВТУ имени Н.Э. Баумана Юрием Павловичем Голубевым более двадцати лет назад. После смерти автора использование и развитие этой методики прекратилось, а значительная часть материалов оказалась неопубликованной. Лишь сравнительно недавно была издана монография [2] и практические разработки были возобновлены и продолжены учениками и последователями Ю.П. Голубева.

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

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

-     проведение параллельной и последовательной декомпозиции схемы;

-     проведение детализации схемы до уровня двухвходовых блоков;

-     анализ синтезированной схемы на соответствие исходному описанию;

-     трансляция схемы в описание на языке VHDL, что дает возможность интегрироваться в специализированные пакеты программ (например, WebPACK ISE) с целью получения файлов для «прошивки» микросхем программируемой логики и практической реализации спроектированного цифрового устройства.

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

В качестве тестового примера для оценки эффективности работы программного пакета Decomposer были использованы различные схемы двоично-десятичных сумматоров, работающих с числами в D-кодах. Для сравнения рассматриваемые схемы была описаны на языке VHDL и синтезированы с использованием программного пакета Decomposer. Оценка проводилась на основе отчетов программы WebPACK ISE по количеству использованных внутренних ресурсов ПЛИС.

 

Рис. 5. Главное окно программы Decomposer

Для реализации рассматриваемых схем были выбраны три различных семейства ПЛИС фирмы Xilinx, отличающиеся между собой принципами организации внутренней структуры – Spartan3 типа FPGA (Field Programmable Gate Arrays), CoolRunner и xc9500xl типа CPLD (Complex Programmable Logic Devices).

Функциональные блоки ПЛИС типа CPLD содержат в своей основе программируемую матрицу элементов «И», вырабатывающую конъюнктивные термы из поступающих на ее входы переменных, группу элементов «ИЛИ», между которыми распределяются выработанные термы, и некоторые другие элементы, расширяющие функциональные возможности рассматриваемых микросхем. Такие функциональные блоки реализуют двухуровневую логику, описываемую логическими функциями в дизъюнктивно-нормальной форме (ДНФ). Кристаллы ПЛИС CoolRunner отличаются кроме того целым рядом архитектурных усовершенствований, обеспечивающих повышение эффективности процесса логического синтеза реализуемых проектов.

Во внутренней структуре ПЛИС типа FPGA размещается множество регулярно расположенных идентичных конфигурируемых логических блоков (КЛБ), между которыми проходят трассировочные каналы. В качестве КЛБ могут использоваться простые логические вентили («И-НЕ», «ИЛИ-НЕ» и т. п.), логические модули на основе мультиплексоров или программируемых ПЗУ (LUT – Look-Up Tables). Такие структуры хорошо приспособлены для реализации многоуровневых логических схем.

Результаты проведенных исследований показывают, что в ряде случаев экономия используемых ресурсов ПЛИС может достигать 50 и более процентов [6]. Разница особенно заметна для «нетривиальных» схем, которые не могут быть сведены синтезатором программы WebPACK ISE к простой комбинации библиотечных блоков. Это позволяет сделать вывод об эффективности применения программного пакета Decomposer и методов многоуровневой декомпозиции для реализации спроектированных цифровых устройств на микросхемах программируемой логики.

Программный пакет Decomposer позволяет проводить полный цикл автоматизированного проектирования цифровых устройств от исходного описания до физической реализации спроектированной схемы на ПЛИС. Пакет внедрен в учебный процесс в Калужском филиале МГТУ им. Н.Э. Баумана и используется при подготовке высококвалифицированных инженерных кадров. Авторами получено свидетельство № 2007611828 об официальной регистрации пакета в Реестре программ для ЭВМ.

 

Литература

 

1. Бибило П.Н., Енин С.В. Синтез комбинационных схем методами функциональной декомпозиции / Под ред. А.Д. Закревского. – Мн.: Наука и техника, 1987. – 189 с.

2. Голубев Ю.П. Автоматизация проектирования преобразователей дискретной информации. – Калуга: Издательство «Гриф», 2003. – 652 с.

3. Коновалов В.Н., Коновалов И.В. Проблемы синтеза комбинационных схем // Материалы Всероссийской НТК «Прогрессивные технологии, конструкции и системы в приборо- и машиностроении», том 1, Москва, изд. МГТУ им. Н.Э. Баумана, 2004, стр. 300-305.

4. Коновалов В.Н., Белов А.А., Коновалов И.В., Нежельский П.Н. Проблемы автоматизированного синтеза комбинационных схем и конечных автоматов // Труды V Российской НТК «Новые информационные технологии в системах связи и управления», часть 2. – Калуга, 2006, стр. 188-190.

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

6. Коновалов В.Н., Белов А.А., Коновалов И.В., Нежельский П.Н. Анализ эффективности реализации цифровых устройств на микросхемах программируемой логики // Труды VI Российской НТК «Новые информационные технологии в системах связи и управления», часть 2. – Калуга, Издательство научной литературы Н.Ф. Бочкаревой, 2007, стр. 399-401.

7. Чебурахин И.Ф. Синтез дискретных управляющих систем и математическое моделирование: теория, алгоритмы, программы. – М.: Издательство физико-математической литературы, 2004. – 248 с.