Алгоритмы логического синтеза и оптимизация ресурсов программируемых логических интегральных схем при проектировании в САПР СБИС

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

Введение

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

На помощь разработчикам интегральных схем пришли языки описания аппаратуры, способные описывать абстрактные модели логических схем, а также так называемые «кремниевые компиляторы» — программные пакеты, способные перевести (синтезировать) абстрактные модели в список соединений, состоящих из логических вентилей. На задачу синтеза накладываются ограничения: должны создаваться конечные схемы, способные работать на указанной разработчиком тактовой частоте (необходима оптимизация задержек в схеме). Кроме того, современные синтезаторы должны оптимизировать схемы по используемым компонентам, то есть использовать как можно меньше ресурсов для функциональной реализации интегральной схемы.

В данной статье рассматривается задача логического синтеза и возможные алгоритмы оптимизации количества используемых компонентов для реализации функций, описанных на языке описания аппаратуры SystemVerilog-2005 без преобразования в библиотеки компонентов технологии вендора ПЛИС. Данная статья выступает в роли исследовательских изысканий, которые проводятся в рамках работ по разработке подмодуля логического синтеза в САПР Delta Design Simtera. Данная система автоматизированного проектирования позволяет проектировать, верифицировать и моделировать радиоэлектронные устройства, описанные на языках SystemVerilog-2005 и VHDL-2008 (и их более ранних версиях). В систему заложены инструменты по преобразованию входных данных во внутренние объекты. Под входными данными понимается проект, описанный на синтезируемом подмножестве выбранного языка, под внутренними данными — семантический граф разбора данного проекта.

1. Маршрут разработки проекта ПЛИС. Входные и выходные данные
программного пакета Delta Design Simtera

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

По окончанию работы подмодуля логической верификации система Delta Design Simtera формирует ориентированный ациклический граф, вершинами которого являются выражения и языковые конструкции HDL-языка. Используя абстрактный семантический граф (ASG, abstract semantic graph), представленный в виде ориентированного ациклического графа (DAG, directed acyclic graph), можно реализовать логическую верификацию путем преобразования исходных данных в функциональное идентичное описание на компилируемом ЭВМ языке; например, C# [2]. Запустив преобразованную программу, можно убедиться в работоспособности исходной HDL-программы.

Графический интерфейс САПР Delta Design Simtera представлен на рис. 2.

2. Логический синтез. Составление комбинационных схем

Одной из особенностей HDL-языков является возможность разбиения любой сколько угодно сложной модели на части, подмодули. Синтезируемые подмножества языков предусматривают наличие у подмодулей входных и выходных портов данных. При этом внутреннее содержимое каждого подмодуля может рассматриваться как «черный ящик», влияющий на результаты выходных данных, в зависимости от входных.

Рассмотрим подмодуль S, имеющий L входов и N выходов. На его входы могут быть поданы наборы значений двоичных переменных, а на выходах формируются наборы, компоненты которых также равны 0 или 1. Схема S называется комбинационной, если каждую из N функций ее выходов  можно представить как булеву функцию (БФ) входных переменных . Тогда эта схема будет описываться с помощью системы уравнений следующего вида:

Комбинационную схему часто называют логическим полюсником, а булевы функции — системой собственных функций данного логического полюсника. Синтез комбинационной схемы состоит из нескольких этапов. Сначала составляется выражение вида (1), отображающее физическое воплощение описываемой функции [3]. На втором этапе выражения комбинационной логики реализуются некоторой схемой. На рис. 3 представлен листинг кода логической схемы, описанной на языке SystemVerilog-2005, состоящей из 7 входов и 1 выхода. На рис. 4 представлен результат работы логического синтезатора, построенного на алгоритме составления комбинационной схемы без оптимизации.

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

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

3. Логический синтез. Оптимизация комбинационных схем
за счет минимизации булевых функций

Задача оптимизации ресурсов ПЛИС и СБИС сводится к задаче минимизации булевых функций на этапе синтеза, то есть к созданию логических функций, которым соответствует минимальное количество операций над логическими переменными. Получение множества всех простых импликант булевой функции уже для числа независимых переменных  может потребовать значительного объема памяти и большего времени работы ЭВМ [5].

Любая функция алгебры логики может быть представлена в виде ДНФ, причем не единственным образом. Рассмотрим стандартные алгоритмы получения сокращенной ДНФ булевой функции и проведем оценку их реализации на ЭВМ. Перед этим введем определения.

3.1. Алгоритм Квайна

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

3.2. Алгоритм Мак-Класски

Алгоритм является усовершенствованием алгоритма Квайна, в котором буквенные значения заменяются двоичными этикетками. При этом логической переменной ставится в соответствие единица, а переменной с отрицанием – ноль. Например, конъюнкция  записывается в виде двоичной этикетки  (младший бит — самый крайний, справа). Дальнейшие действия выполняются уже с двоичными числами, что упрощает программную реализацию. В позиции, на которой произошло склеивание, вместо отсутствующей переменной ставится черточка. Данный метод может быть реализован на ЭВМ, а комбинаторная сложность и объем занимаемой памяти зависит от входной функции. При этом объем памяти можно оценить как [6].

3.3. Карты Карно

Преимуществом карт Карно является то, что они отражают все минитермы рассматриваемых функций. Карты Карно успешно решают задачи минимизации функций с числом переменных не более 5–6. Алгоритм решения минимизации булевых функций получает одну из тупиковых ДНФ, при этом не обязательно кратчайшую. При небольшом количестве независимых переменных возможной погрешностью можно пренебречь, однако с ростом числа переменных может весьма существенно возрастать и погрешность решения. В [7] показано, что две тупиковые ДНФ могут различаться по длине в  раз. Это означает, что для функции 40 переменных две тупиковые ДНФ могут различаться более чем в миллион раз.

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

3.4. Алгоритм получения простых импликант
на основе разбиения по кодам разности

Путем попарного сравнения и склеивания минитермов ранга  получаются минитермы ранга . Минитермы ранга , участвующие в склеивании, помечаются. Множество минитермов ранга  разбиваются на классы, при этом в каждом классе присутствуют термы с одинаковыми кодами разности. Далее каждый из классов рассматривается независимо от других, и для каждого из подклассов выполняются описываемые выше действия. Операция повторяется, пока склеивание возможно. Рассмотрение классов следует осуществлять в порядке возрастания кодов разности. Объем памяти, необходимый для реализации предлагаемого алгоритма будет равен . Таким образом, предложенный метод обладает существенно более высоким быстродействием и требует существенно меньше памяти, чем ранее рассмотренные методы [8].

4. Логический синтез. Алгоритм взаимодействия синтезатора с компилятором

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

1. Компилятор должен уметь находить ошибки использования присваиваний к переменным в разных сигнальных доменах и предупреждать об этом разработчика,
2. Компилятор должен формировать список повторяющихся функций. Например, если два выходных порта реализуют одну и ту же функциональность, но при этом из разных частей или из разных сигнальных доменов, то имеет смысл выделять такого рода закономерности, чтобы не проводить по ним синтез несколько раз,
3. Компилятор должен формировать выражения для составления синтезатором комбинационных схем,
4. Логический синтезатор на основе сформированных выражений должен составлять неоптимизированную комбинационную схему, а также булевы функции по заданным переменным,
5. Логический синтезатор должен обладать функционалом для минимизации булевых функций.

Заключение

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

Литература

1. Варганов А. В. Роль лексического и синтаксического анализа в маршруте разработки проекта ПЛИС / А. В. Варганов, Н. М. Малышев // Математика, информационные технологии, приложения: сборник трудов Межвузовской научной конференции молодых ученых и студентов, Воронеж, 26 апреля 2021 г. – Воронеж : Научная книга, 2021. – С. 25–32.
2. Малышев Н. М. Цифровое моделирование. Формирование семантического графа для кодогенерации и автодополнения кода / Н. М. Малышев // Наноиндустрия. – 2021. – Т. 14, №S7 (107). – С. 365–367.
3. Баранов С. И. Цифровые устройства на программируемых БИС с матричной структурой / С. И. Баранов, В. А. Скляров – М.: Радио и связь, 1986. – 272 с.: ил.
4. Программный комплекс MICEL высокоуровневого проектирования и логического синтеза параллельных алгоритмов логического управления / П. Н. Бибило, С. Н. Кардаш, Н. А. Кириенко, Д. А. Кочанов, П. В. Леончик, Д. Я. Новиков, В. И. Романов, Д. И. Черемисинов // Управляющие системы и машины. – 2009. – №5. – С. 81–88.
5. Лузин С. Ю. Минимизация булевых функций на основе синтеза распределения термов по индексам / C. Ю. Лузин // Сб. науч. трудов учебных институтов связи. – 1996. –  Вып. 162. – С. 27–30.
6. Горбатов В. А. Частотная матрица отношений и применения / В. А. Горбатов // Труды МЭИ. Вычислительная техника. – 1964. – Т. 53. – С. 5–30.
7. Васильев Ю. Л. О сравнении сложности тупиковых и минимальных дизъюнктивных нормальных форм / Ю. Л. Васильев // Проблемы кибернетики. – М., ФИЗМАТГИЗ, 1963. – С. 5–62.
8. Лузин С. Ю. Синтез логических схем промышленной робототехники / Лузин С. Ю., Добжинский Б. Н. // Межвуз.сб.: Электромеханические элементы работотехнических систем. – Ленинград, ЛИАП, 1985. – Вып. 178. – С. 143–150.