Все авторефераты - Беларусь

Архивные справочники

Оптимизация представлений систем булевых функций для снижения сложности и энергопотребления комбинационных схем по специальности л05.13.12 - системы автоматизации проектирования

Автореферат диссертации

Государственное научное учреждение

ОБЪЕДИНЕННЫЙ ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ

НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК БЕЛАРУСИ

УДК 519.714

ЛЕОНЧИК Павел Вацлавович

ОПТИМИЗАЦИЯ ПРЕДСТАВЛЕНИЙ

СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ ДЛЯ СНИЖЕНИЯ

СЛОЖНОСТИ И ЭНЕРГОПОТРЕБЛЕНИЯ

КОМБИНАЦИОННЫХ СХЕМ

Автореферат диссертации

на соискание ученой степени кандидата технических наук

по специальности 05.13.12 - Системы автоматизации проектирования

Минск 2012

Работа выполнена в государственном научном учреждении Объединенный институт проблем информатики Национальной академии наук Беларуси

Научный руководитель:

БИБИЛО Петр Николаевич,

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

Официальные оппоненты:

СОЛОВЬЕВ Валерий Васильевич

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

СЕДУН Андрей Максимович

кандидат технических наук, доцент, проректор по учебной работе Белорусского государственного экономического университета

Оппонирующая организация:

Филиал НТЦ Белмикросистемы ОАО Интеграл

Защита состоится 20 марта 2012 года в 14:30 на заседании совета по защите диссертаций Д 01.04.01 при государственном научном учреждении Объединенный институт проблем информатики Национальной академии наук Беларуси по адресу: 220012, г. Минск, ул. Сурганова, 6. Телефон ученого секретаря: (+375 17) 284 21 68, факс (+375 17) 284 21 75, e-mail: .

С диссертацией можно ознакомиться в библиотеке государственного научного учреждения Объединенный институт проблем информатики Национальной академии наук Беларуси

Автореферат разослан л14 февраля 2012 г.

И.о. ученого секретаря совета по защите диссертаций доктор технических наук

Г.И. Алексеев

ВВЕДЕНИЕ

Синтез логических схем в современных системах автоматизированного проектирования (САПР) проходит в несколько этапов: на первом этапе по исходным описаниям осуществляется высокоуровневый синтез - переход к описаниям схем комбинационной логики и элементов памяти (триггеров), на втором этапе выполняется технологически независимая оптимизация, на третьем этапе проводится реализация (технологическое отображение) оптимизированных представлений в заданный технологический базис, например FPGA (Field Programmable Gate Array). В качестве технологического базиса для заказных сверхбольших интегральных схем (СБИС) используются библиотеки логических элементов либо регулярные структуры типа программируемых логических матриц (ПЛМ).

Важнейшим этапом, влияющим на сложность, быстродействие и другие характеристики получаемых логических схем является центральный этап технологически независимой оптимизации различных форм представлений систем булевых функций - дизъюнктивных нормальных форм (ДНФ), диаграмм двоичного выбора - BDD (Binary Decision Diagrams), а также многоуровневых представлений, получаемых в результате проведения функциональных разложений (декомпозиции).

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Связь работы с крупными научными программами и темами

Диссертационная работа выполнялась в лаборатории логического проектирования Объединенного института проблем информатики НАН Беларуси в рамках тем:

Модели и методы алгоритмического и функционально-логического проектирования управляющих и вычислительных систем на базе сверхбольших интегральных схем (ГКПНИ Инфотех - ИНТ06) - № ГР 20061971; 20062010 гг.
Разработка программного комплекса для решения комбинаторных задач логического проектирования и искусственного интеллекта (ГКПНИ Инфотех - ИНТ28) - № ГР 20062481; 2005-2008 гг.

Разработать программные средства высокоуровневого и логического синтеза параллельных алгоритмов логического управления (ГНТП Микроэлектроника) - № ГР 20067002; 2006-2008 гг.
Разработать методы проектирования, ориентированные на снижение энергопотребления цифровых интегральных микросхем (мероприятие 3.2.) (Программа Союзного государства Космос-НТ) - № ГР 20090369; 2006-2011 гг.

Цель и задачи исследования

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

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

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

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

Положения, выносимые на защиту

На защиту выносятся:

алгоритмы минимизации систем булевых функций с учетом сложности и энергопотребления комбинационных схем из библиотечных КМОП элементов;
алгоритмы минимизации многоуровневых BDD-представлений систем булевых функций, предназначенные для снижения сложности и энергопотребления комбинационных схем из библиотечных КМОП элементов;
метод двухблочной декомпозиции системы булевых функций, представленной в виде BDD, по заданному разбиению множества аргументов и алгоритмы выбора разбиения аргументов;

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

ичный вклад соискателя

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

Апробация результатов диссертации

Основные теоретические и практические результаты работы докладывались на следующих конференциях: 3rd IF AC Workshop on Discrete Event System Design (DESDes'06), September 26-28, 2006, Rydzyna, Poland; Шестой Международной конференции Автоматизация проектирования дискретных систем (Computer-Aided Design of Discrete Devices - CAD DD'07), Минск, 14-15 ноября 2007 г.; Третьей Международной научной конференции Танаевские чтения, Минск, 28 марта 2007 г.; Пятой Международной научно-технической конференции Проблемы проектирования и производства радиоэлектронных средств, Новополоцк, 29-30 мая 2008 г.; Пятой Международной научно-технической конференции Информационные технологии в промышленности (ITP2008), Минск, 22-24 октября 2008 г.; Международной научной конференции Дискретная математика, алгебра и их приложения, Минск, 19-22 октября 2009 г.; Четвертой Всероссийской научно-технической конференции Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 4-8 октября 2010 г.; Седьмой Международной конференции Автоматизация проектирования дискретных систем (Computer-Aided Design of Discrete Devices - CAD DD'10), Минск, 16-17 ноября 2010 г.

Опубликованность результатов

По материалам диссертационной работы опубликовано 16 печатных работ, в том числе: 8 статей (на 3,4 авторских листах) в научных журналах, включенных в Перечень научных изданий Республики Беларусь для опубликования результатов диссертационных исследований, утвержденный ВАК; 6 докладов в сборниках материалов международных конференций, 2 тезиса докладов. Печатные работы соискателя датированы 2006-2011 гг. Содержание опубликованных работ соответствует теме диссертации.

Структура и объем диссертации

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

многоуровневых представлений булевых функций. Основная часть материала диссертации излагается в четырех главах. Основные результаты диссертации формулируются в заключении, за которым идет список использованных источников. Общий объем диссертации составляет 131 страницу, в том числе 26 иллюстраций на 11 страницах, 40 таблиц на 17 страницах и 2 приложение на 7 страницах. Библиографический список включает 158 использованных источников (в том числе 16 авторских) на 13 страницах.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Булевыми называются функции f(x) = f(x1,x2,...,xn) двоичных (булевых)

переменных х1,х2,...,хп,принимающие значения из множества ={0,1}. Булева функция, значения которой определены на всех наборах значений аргументов х1,х2,...,хп называется полностью определенной. юбая полностью

определенная булева функция может быть задана в виде ДНФ, т. е. в форме дизъюнкции элементарных конъюнкций. Задача минимизации ДНФ заключается в поиске такой ДНФ для заданной булевой функции f(xl,x2,...,xn), которая содержала бы минимальное число конъюнкций или

литералов.

Минимизация булевых функций является классической задачей, которая широко известна. Однако до сих пор не утратила актуальности проблема повышения эффективности алгоритмов минимизации булевых функций как в отношении сокращения времени поиска решения, так и улучшения качества этого решения. Дело в том, что минимизация систем булевых функций в классе ДНФ является одним из этапов технологически независимой оптимизации при синтезе структур из библиотечных вентилей (элементов), реализуемых как в БМК, так и в заказных СБИС. При синтезе структур ПЛМ, входящих в состав заказных СБИС, совместная минимизация систем булевых функций позволяет решать задачу сокращения площади ПЛМ. Приведен анализ известных методов минимизации булевых функций, начиная с классических методов Квайна -МакКласки и Блейка - Порецкого и анализ наиболее известных программ минимизации: Espresso, Scherzo, BOOM, MINI и других, указываются их достоинства и недостатки.

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

Шеннона булевой функции f(xl,...,xn) по всем ее переменным х1,...,хп при заданном порядке (перестановке) переменных, по которым проводится разложение. Разложением Шеннона булевой функции f(xl,...,xn) по переменной xi называется представление f(xl,...,xn) в виде

/ \X\->---->Xn)=XiJ \Х1>--->Х-Л>Х+1>--->Хп) V XU \Xl>--->Xi-l>V>Xi+l>--->Xn) ж

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

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

Задача 1 минимизации системы F = {fl{xl,x2,...,xn),...,fm{xl,x2,...,xn)} булевых функций в классе ДНФ заключается в поиске системы ДНФ булевых функций, содержащей минимальное число конъюнкций, на которых заданы ДНФ всех функций системы. Такую систему ДНФ будем называть кратчайшей.

Алгоритм минимизации системы полностью определенных булевых функций состоит из трех этапов.

Поиск всех простых импликант исходной системы булевых функций.
Построение матрицы покрытия и ее сокращение.
Поиск тупиковых систем ДНФ.

На первом этапе для получения всех простых импликант исходной системы булевых функций fi(xl,x2,...,xn) разобьем все переменные исходной

системы на две части: x1,x2,...,xk; xk+1,xk+2,...,xn, где к-nil, если п четно и

к = (п + \)/2, если п нечетно. Сгруппируем все исходные наборы,

соответствующие полным элементарным конъюнкциям ДНФ исходной

системы функций, по классама с^'Х2""'Хкзс?'Х2-"Хк,...,С*1'**-"'Хктак, что в

каждый класс войдут только элементарные конъюнкции, для которых значения одноименных переменных xl,x2,...,xkсовпадают. Назовем переменные

базисома классов,аа аа переменныеаа хк+ъхк+2,...,хпаа -а внутренними переменнымиаа классов.аа Каждыйаа классаа можноаа рассматриватьаа какаа систему

булевых функций ^{хк+1,хк+2,...,хп), i=\,...,m,для которой, применив алгоритм Квайна - МакКласки, получим все импликанты этого класса. Далее производится поиск импликант между классами. Для межклассового поиска новых импликант следует рассматривать только классы, отличающиеся на одну переменную из базиса классов, тем самым сокращая перебор возможных вариантов поиска. Операция склеивания импликант между классами представляет собой операцию обобщенного склеивания импликант по методу Блейка - Порецкого, при этом переменные xl,x2,...,xkиз базиса классов образуют новый класс. Операция обобщенного склеивания импликант между классами производится до тех пор, пока нельзя будет создать ни одного нового класса. После поиска импликант между классами и удаления поглощаемых импликант получим все простые импликанты исходной системы булевых функций.

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

Поиск первого покрытия.
Поиск покрытий подматриц.

На первом шаге производится поиск первого покрытия матрицы М с помощью быстрого (минимаксного) алгоритма. На втором этапе, разбив матрицу М на подматрицы и пытаясь найти меньшее (по мощности) столбцовое покрытие каждой подматрицы в отдельности, будем улучшать общее столбцовое покрытие матрицы М. Очевидно, если Хт - покрытие матрицы М, то любая подматрица W матрицы М будет содержать покрытие Xw с: Хт. Улучшаяаа покрытиеаа Xw,аа улучшаемаа иаа покрытиеаа Хт.аа Алгоритмаа поиска

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

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

В третьей главе предлагается алгоритм оптимизации многоуровневых представлений системы ДНФ полностью определенных булевых функций на основе построения BDD, метод декомпозиции системы полностью

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

Рассматриваются BDD для системы функций, при этом последовательность переменных, по которой ведутся разложения, одинакова для всех функций системы.

Задача 2. Задана система F(xl,...,xД)=(f1(xl,...,xn),...,fm(xl,...,xД)) ДНФ полностью определенных булевых функций. Требуется построить BDD минимальной сложности для системы F функций.

Решение задачи 2 разбивается на два этапа.

Этап 1. Выбор последовательности (перестановки) переменных х1,...,хп, по

которой ведется разложение Шеннона.

Этап 2. Построение BDD по заданной перестановке переменных разложения.

Предложенный алгоритм выбора последовательности (перестановки) переменных состоит в последовательном применении трех эвристик. Каждая эвристика применяется поочередно до тех пор, пока не даст уменьшения сложности BDD. Для каждой из рассматриваемых промежуточных перестановок подсчитывается сложность BDD. Эвристика 1 - перестановка одного аргумента xt с правым соседом. Эвристика 2 - попарная перестановка. Очередная перестановка отличается от предыдущей переменой мест только двух аргументов. Эвристика 3 - локонная перестановка. Окно представляет собой четыре последовательно расположенных аргумента <x-,x-+1,x-+2,x-+3>, внутри которого производятся все перестановки четырех аргументов. Затем окно перемещается на один аргумент вправо - получается новое окноа (xi+1,xi+2,xi+3,xi+4), внутри которого опять осуществляются все

перестановки.

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

Разбиение множестваа Xа на попарно непересекающиеся блоки

(подмножества) Y ,7 ,...,Yqпроизводится по следующему правилу: если п > 20, то разбиваем X на q блоков Yl,Y2,...,Yq, таких, что Y1а = 3, i=2, 3, ..., q,

где

-а мощностьаа блок Y1,а 3 < Г1 < 5,а еслиаа п < 20,а тоа разбиение

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

системы F. Если Ък <а 2й, то разбиваема Xаа на два блокаа Y\Y2, причем

-п-Ъ

= 3 . Если Зк>2", то разбиение на блоки осуществляется так же,

как при п > 20. Затем происходит построение коэффициентов разложения

Шеннона для функций системы F по переменным блока Y1а /=1, 2, ..., q-\ и сравнение их на равенство приближенным алгоритмом. После этого строятся

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

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

Обозначим через щ вероятность появления единичного значения сигнала

х- на входе логической схемы реализующей BDD, через S{ обозначим число литералов переменной xi в многоуровневом представлении системы функций, соответствующем BDD. Пусть

Ki =aixSi, если л.<0,5; Ki =(\-ai)xSi, если at >0,5.

Назовем Ki оценкой энергетического качества переменной х в BDD-представлении. Если вероятность щ близка к 0,5, то такие переменные будут

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

Задача 3. Для векторной булевой функции f(x), представленной в виде

BDD, и заданного разбиения Y/Z множества переменных X построить функциональное разложение (провести декомпозицию векторной функции) вида

f(x)=f(yz) = g(h(y\z),

гдеаа h(y) = (h1(y),...,hp(y)).а Приа этома требуется минимизироватьа числоаа р компонент векторной функции h(y) и представить ее в виде системы ДНФ, а векторную функцию g(h(y),z) представить в виде BDD. Этап 1. Построение разложение Шеннона

f(y,Z) = УУ2-Уг/* (=0v УУ-Уг* (Ю v... v yxy2...yj . (z)

------- --------------------------- ЧZ0а ЧZiаа Ч Z2r-i

векторной функции f(x) по подмножеству аргументов Y

Коэффициент разложения f *(z) Ч это векторная функция, полученная в

результате подстановки в функцию f(y,z) вместо переменных вектора у вектора у.,=\,...,2г-\,их.значений. Сгруппировав в один класс (множество) дизъюнктивных членов разложения с одинаковыми коэффициентами f(z), получим разложение вида

/O^a/jGO v Q2f2(z) v ... v QJk{z).

Так как по BDD легко строятся кратчайшие разложения Шеннона компонентных функций, то возникает задача построения кратчайшего разложения Шеннона векторной функции по кратчайшим разложениям Шеннона компонентных функций. Данная задача сводится к задаче нахождения минимального дизъюнктивного базиса для системы ДНФ S. Систему ДНФ S

образуют ДНФ Q-(y), входящие в кратчайшие разложения Шеннона компонентных функций fj(x) векторной функции f (x) = (f1(x),...,fm(xy), т.е.

т к1

S =U (U Ql (УУ) ж Минимальным дизъюнктивныма базисома системыа ДНФаа S

называется минимальная по мощности система попарно ортогональных ДНФ D={Dl(y),...,Dk(y)} такая, что каждая ДНФа Q/(y)eSа равна дизъюнкции

некоторого подмножества ДНФ системы S. Нахождение минимального дизъюнктивного базиса D сводится к выполнению операций перемножения,

инверсирования и сравнения на равенство ДНФ QJ (у) системы S.

Этап 2. Определение минимального числа промежуточных функций ht,i = \,...,p и их построение кодированием ДНФ минимального дизъюнктивного базиса булевыми либо троичными кодами, совместная минимизация промежуточных функций в классе ДНФ.

Этап 3. Построение выходной векторной функции g с учетом

дизъюнктивного расщепления ДНФ QJq на базисные ДНФ D\y),...,Dk(y).

Выбор разбиения Y/Z переменных. Целью декомпозиции является уменьшение числа переменных (аргументов), от которых зависят функции. Поэтому при поиске разбиения при декомпозиции обычно стремятся к тому, чтобы числа г переменных, от которых зависят функции h, и числа р. +{п Ч г)

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

Процедура выбор разбиения YIZ включена в алгоритм поиска перестановки переменных х,, по которой строится BDD. Для построенной BDD разрез ищется от середины BDD в полосе вверх на [и/4] уровней BDD и вниз на \п 14] уровней BDD от середины BDD. Середина BDD - это разрез на уровне переменной хк, где к = \п 12~]. Для первой перестановки для каждого разреза из

указанной полосы оценивается по формулам суммарное число переменных h и выбирается разрез, который приводит к меньшему числу функций h, а если таких разрезов несколько, то выбирается тот разрез (разбиение YIZ), который ближе к середине BDD. Для всех последующих перестановок ищется свой лучший разрез, который сравнивается с лучшим из уже найденных разрезов. Сравнение разрезов осуществляется следующим образом: разрез считается лучшим, если он обеспечивает меньшее число различных коэффициентов разложения Шеннона (критерий 1), попадающих в данный разрез. Если эти параметры равны, то выбирается, разрез, который ближе к середине BDD (критерий 2), если же эти параметры (мощности множеств Y) одинаковы, то предпочтение отдается тому разрезу, который совершается в BDD, имеющей меньшее число вершин - различных коэффициентов разложения по всем переменным (критерий 3).

Четвертая глава посвящена экспериментальным исследованиям разработанных программ на основе предложенных алгоритмов. Приводятся результаты экспериментов на сериях стандартных примеров Benchmark и случайно сгенерированных примерах. Экспериментально исследуются эффективность предложенных алгоритмов для синтеза комбинационных схем в базисе библиотеки элементов отечественных заказных СБИС, БМК, структур FPGA и ПЛМ. На рисунке 1 приводится схема проведения экспериментальных исследований для синтеза схем из библиотечных элементов.

Матричные представления систем функций sf-описания
	Программы оптимизации представлений систем функций		Оптимизированные представления систем функций


				ч	'
	VHDL описания			конвертор

		'
огические схемы из библиотечных элементов
	1		Библиотека логических элементов
	Синтезатор Leonardo

Рисунок 1. - Организация экспериментов

Приводятся результаты экспериментальных исследований программ минимизации булевых функций в классе ДНФ. На основе предложенного алгоритма разработана программа Tie на языке Си. Для сравнения эффективности решений, полученных программой Tie, использовалась всемирно известная программа Espresso. Для 11 из 30 примеров серии Benchmark (таблица 1) программа Tie находит лучшее решение, чем программа

Espresso, в большинстве случаев затрачивая на его поиск меньшее время. В таблице 1 используются следующие обозначения: п - число переменных; т -число функций в системе; к - число конъюнкций, полученных в результате работы программ Espresso и Tie; kmin - число конъюнкций в точном решении; t -время (с), затраченное на поиск решения.

Таблица 1 - Сравнение эффективности программ минимизации ДНФ Tie и Espresso

Имя схемы	n	m		Программа Espresso		Программа Tie
Имя схемы	n	m		к	,с	к	,с
тах512	9	6	133	145	0,12	134	0,388
max 1024	10	6	259	274	0,57	263	0,239
ех5	8	63	65	74	0,09	66	1,164
z5xpl	7	10	63	65	0,03	63	0,014
z9sym	9	1	84	86	0,07	84	0,198
dist	8	5	120	123	0,06	120	0,026
mlp4	8	8	121	128	0,06	125	0,035

В примерах серии Benchmark существует несколько примеров, для которых до сих пор не найдены точные решения (таблица 2). Целью эксперимента было нахождение как можно лучших решений для таких примеров. Результаты сравнивались с программой ZDDSCG, которой были получены лучшие решения для сложных примеров. Для примера test4 лучшее решение было найдено программой BCU.

Таблица 2 - Поиск наилучших решений минимизации систем ДНФ для сложных примеров из серии Benchmark

Имя схемы	Матрица покрытия		Программа ZDD SCG		Программа Tie
Имя схемы	V	w	к	t с	к	t,c
ехЮЮ	1471	25203	239	1355.56	237	105
test2	7122	106949	865	88956.0	854	1191
test3	3543	40680	436	8167.62	433	1143
test4	1516	6139	96/94	592.71	92	49

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

Были проведены эксперименты влияния различных видов минимизации ДНФ на сложность схем ПЛМ, заказных СБИС и БМК (таблица 3). Сложность схемы SEMKв библиотеке проектирования БМК подсчитывалась как сумма

площадей входящих в данную схему элементов. Площадь ПЛМ, вычислялась по формуле SnjlM=(2п + т)хк, где п - число входов схемы ПЛМ; т - число

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

Таблица 3 - Реализация схем на ПЛМ и заказных СБИС

Имя схемы	синтез схем без оптимизации		синтез схем с оптимизацией
			на Г	[ЛМ	на заказных СБИС
			Тог	TieC	Тог	TieC	TieL	TieR
	плм	иБМК	V плм	плм	иБМК	иБМК	^БМК	^БМК
addm4	12480	2128	5252	4914	948	999	872	817
Ь12	16809	149	1872	1599	148	244	154	148
inO	5535	1281	4428	4387	1035	929	986	957
intb	24568	3396	23643	23273	3355	3542	3336	3359
m2	3072	552	1536	1504	650	604	657	415
mlp4	5400	1374	3144	2904	768	719	665	631
mp2d	5166	303	1512	1260	159	210	155	157

Анализируя результаты экспериментов, можно сделать вывод, что логическая минимизация позволяет значительно уменьшить сложность схем ПЛМ и БМК, однако для этого желательно использовать программы минимизации по различным критериям: для минимизации площади ПЛМ нужна совместная минимизация по критерию минимальности числа конъюнкций, для схем заказных СБИС и БМК- раздельная минимизация по критерию минимальности числа литералов.

Алгоритм построения BDD был программно реализован в программе OPTBDD, которая была подвергнута обширному экспериментальному исследованию. Сравнение предложенного алгоритма с алгоритмом из статьи (Felt, Е. Dynamic variable reordering for BDD minimization. Design Automation Conference, 1993) дано в таблице 4.

Таблица 4 - Сравнение эффективности программ оптимизации BDD

Имя схемы	п	т	к	Программа Felt		Программа ОРТ BDD
Имя схемы	п	т	к	BDD	,с	BDD	,с
А1и4	14	8	1028	141	21.65	735	20.06
Арех2	39	3	1035	739	38.53	333	843.80
АрехЗ	54	50	280	1129	87.23	997	83.37
Е64	65	65	65	865	183.80	128	399.19
Misex3	14	14	1848	523	22.88	581	142.62
ТаЫеЗ	14	14	175	798	40.21	747	11.01
ТаЫе5	17	15	158	689	28.15	708	8.98

Были проведены эксперименты по сравнению эффективности применения оптимизации BDD, выступающей в качестве предварительного этапа синтеза

комбинационных схем, реализуемых в составе БМК или FPGA (таблица 5). Площадь полученных логических схем FPGA подсчитывалась в числе программируемых элементов LUT (Look Up Table), имеющих 4 входа.

Таблица 5 - Влияние BDD-оптимизации на сложность схем БМК и FPGA

Имя схемы	n	m	к	Синтез схем БМК		Синтез схем FPGA
				поПЛМ	по BDD	поПЛМ	по BDD
				^БМК	^БМК	LUT	LUT
Ь12	15	9	431	192	160	25	23
Ь2	16	17	110	2474	1682	476	318
inO	15	11	135	2067	1036	141	195
tial	14	8	640	4505	2389	652	478
Intb	15	7	664	5810	2269	423	391
Inl	16	17	110	2862	1711	392	297
Vtxl	27	6	110	175	349	28	99
X9dn	27	7	120	198	370	31	90
soar	83	94	529	1705	2043	312	347

Результаты экспериментов показали, что оптимизация многоуровневых представлений систем полностью определенных булевых функций с помощью BDD приводит к сокращению сложности схем при синтезе в базисе БМК. Однако применение BDD в качестве предварительного этапа оптимизации схем FPGA оказалась полезным только в половине примеров схем.

Результаты экспериментов по минимизации булевых функций с учетом энергопотребления приведены в таблице 6. Жирным шрифтом выделены лучшие значения энергопотребления (тока).

Таблица 6 - Результаты исследования программ оптимизации ДНФ и BDD с учетом энергопотребления

Имя схемы	Минимизация ДНФ Average (ток),		BDD-оптимизация Average (ток),
Имя схемы	Tie	Tie Energy	OPT BDD	Bdd Energy
z9sym	0.541	0.541	0.308	0.267
mlp4	0.535	0.517	0.693	0.638
inO	0.985	1.026	1.111	1.244
life	0.276	0.276	0.313	0.294
Ы2	0.559	0.483	0.251	0.251
tms	0.712	0.707	0.667	0.665
brl	0.180	0.134	0.329	0.469
br2	0.051	0.051	0.077	0.115
gary	0.985	1.026	0.065	0.052
m3	0.975	1.077	0.952	0.967
max 1024	1.702	1.634	1.323	1.326
tial	4.512	5.442	3.257	3.440

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

VHDL-

описание

логической

схемы

Конвертер VHDL - Spice

Spice-описание

транзисторной

схемы

Последовательность

наборов входных

сигналов

Система

схемотехнического

моделирования

(AccuSim, Mentor Graphics)

Библиотека

Spice-описаний

логических

элементов

Среднее значение тока,

потребляемого схемой

(Average)

Рисунок 2. - Оценка энергопотребления логической схемы

Анализируя полученные экспериментальные результаты (таблица 6), можно сделать следующие выводы. По системам ДНФ, полученным с помощью программы лэнергетической минимизация систем функций, получаются схемы, характеризующиеся более низким энергопотреблением. Однако, если схема является более сложной, т. е. содержит значительно больше (примерно на 15%) логических элементов, то и энергопотребление этой схемы будет, как правило, большим. Для программ оптимизации BDD справедлив тот же вывод, т. е. если схема содержит больше (примерно на 10%) элементов, то и энергопотребление ее будет большим, несмотря на усилия лэнергетической оптимизации. Если же сложность схемы, полученной с помощью лэнергетической BDD-оптимизации, незначительно превышает сложность схемы после традиционной BDD-оптимизации, то энергопотребление ее будет, как правило, меньшим.

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

ж минимизация BDD

S декомпозиция совместная

декомпозиция раздельная
минимизация ДНФ

z9symаа m3 mlp4а garyа addm4а inO in2 max 1024аа soarа In1 Ь2аа tialа Intb

Рисунок 3. - Влияние видов оптимизации на сложность схем

Разработанные программы были включены в следующие системы автоматизированного проектирования, разработанные в ОИПИ НАН Беларуси: CLTT, MICEL, Logic, ELS. В систему CLTT, предназначенную для сквозного проектирования функциональных блоков заказных СБИС на базе программируемых макроэлементов трех типов - ПЛМ, РМОП-схем и ПЗУ, были включены разработанные модули совместной и раздельной минимизации булевых функций в классе ДНФ. Система MICEL, предназначена для выполнения заказного проектирования устройств логического управления с использованием логических элементов из библиотеки проектирования БМК и заказных СБИС. Система MICEL интегрирована по входным данным с синтезатором логических схем Leonardo и имеет в своем составе оптимизационные блоки, которые отсутствуют в Leonardo - это прежде всего минимизация и декомпозиция систем частичных булевых функций. В систему MICEL включена разработанная программа OPTBDD. Программные комплексы LOGIC и LOGIC-2 предназначены для обеспечения проведения булевых вычислений и интерактивного решения логико-комбинаторных задач. В них включен модуль, который выполняет задачу поиска всех простых импликант заданной системы булевых функций. В программный комплекс ЭЛС автоматизации проектирования логических схем в библиотечном базисе, оптимизированных по энергопотреблению, включены два модуля: оптимизация двухуровневых представлений и оптимизация многоуровневых представлений булевых функций по критерию сложности и энергопотребления.

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертации

Разработаны алгоритмы минимизации систем полностью и частично определенных булевых функций в классе ДНФ [1-А, 2-А, 9-А, 16-А], ориентированные на проектирование ПЛМ-структур и синтез схем с пониженным энергопотреблением из библиотечных КМОП элементов заказных СБИС. Алгоритмы минимизации отличаются от известных использованием предложенной процедуры построения простых импликант на основе оценки их прогнозного влияния на энергопотребление схемной реализации результирующей системы ДНФ.
Разработан алгоритм решения задачи покрытия [3-А, 11-А], ориентированный на разреженные булевы матрицы и отличающийся от известных алгоритмов новыми эвристиками, которые позволяют сократить перебор при обходе дерева поиска кратчайшего покрытия.
Разработан алгоритм построения и оптимизации многоуровневых представлений булевых функций на основе диаграмм двоичного выбора (BDD) [5-А, 10-А], ориентированный на синтез комбинационных схем с пониженным энергопотреблением из библиотечных КМОП элементов. Предложен и экспериментально обоснован эвристический алгоритм упорядочения множества

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

Разработан метод двух блочной декомпозиции булевых функций [6-А, 7-А, 8-А, 12-А, 13-А, 14-А, 15-А], заданных диаграммой двоичного выбора. Отличительной особенностью метода является то, что для одного из блоков сохраняется представление в виде BDD, а функции другого блока задаются в виде ДНФ. Предложен алгоритм выбора разбиения аргументов, применимый, в отличие от известных, при совместной и раздельной декомпозиции с несколькими промежуточными функциями. Эффективность алгоритмов решения задач выбора разбиения аргументов достигается за счет применения аппарата BDD и отказа от использования традиционных матричных и табличных форм представления систем функций.
Разработаны и экспериментально исследованы программы, реализующие предложенные алгоритмы. Результаты экспериментов показали, что применение разработанных программ при логическом проектировании позволяет уменьшить сложность логических схем в различных технологических базисах (ПЛМ, БМК, заказные СБИС, FPGA) и уменьшить энергопотребление заказных СБИС. Дополнительный учет переключательной активности входных сигналов позволяет снижать до 20% энергопотребление логических схем, синтезируемых в библиотеке проектирования заказных СБИС, выполненных по КМОП-технологии. Программы оптимизации представлений систем функций включены в системы автоматизированного проектирования логических схем [4-А], разработанные в ОИПИ НАЛ Беларуси.

Рекомендации по практическому использованию результатов

Разработанные программы оптимизации двухуровневых и многоуровневых описаний систем булевых функций вошли в состав разработанных в ОИПИ НАЛ Беларуси программных средств автоматизированного проектирования дискретных устройств и цифровых СБИС: в систему CLTT, предназначенную для сквозного проектирования заказных СБИС на базе программируемых макроэлементов; в программный комплекс MICEL, предназначенный для схемной реализации устройств логического управления с использованием логических элементов из библиотеки проектирования БМК и заказных СБИС; в программный комплекс ЭЛС автоматизации проектирования логических схем в библиотечном базисе, оптимизированных по энергопотреблению; в программный комплекс LOGIC, обеспечивающий интерактивное решение логико-комбинаторных задач и проведение экспериментов. Разработанные программы могут быть использованы в проектных организациях для уменьшения сложности функциональных описаний комбинационной логики при проектировании цифровой аппаратуры на программируемых логических интегральных схемах и на заказных цифровых СБИС. Программные комплексы LOGIC, LOGIC-2 могут быть использованы в учебном процессе в вузах при подготовке специалистов-проектировщиков электронных цифровых схем.

СПИСОК ПУБЛИКАЦИЙ СОИСКАТЕЛЯ

Статьи

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

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

3-А. Леончик, П.В. Алгоритм покрытия разреженных булевых матриц / П.В Леончик // Информатика. - 2007. - № 2. - С. 53-61.

4-А. Бибило, П.Н. Программный комплекс MICEL высокоуровневого и логического синтеза параллельных алгоритмов логического управления / П.Н. Бибило, С.Н. Кардаш, Н.А. Кириенко, Д.А. Кочанов, П.В. Леончик, Д.Я. Новиков, В.И. Романов, Д.И. Черемисинов // Управляющие системы и машины. 2009. - № 5. - С. 81-88.

5-А. Бибило, П.Н. Алгоритм построения диаграммы двоичного выбора для системы полностью определенных булевых функций / П.Н. Бибило, П.В. Леончик // Управляющие системы и машины. 2009. - № 6. - С. 42-49.

6-А. Бибило, П.Н. Экспериментальное исследование влияния процедуры BDD-оптимизации на энергопотребление комбинационных КМОП-схем / П.Н. Бибило, П.В. Леончик // Автоматика и вычислительная техника. - 2010. -№5.-С. 72-78.

7-А. Бибило, П.Н. Декомпозиция систем булевых функций, заданных диаграммами двоичного выбора / П.Н. Бибило, П.В. Леончик // Известия РАН. Теория и системы управления. - 2011. - № 4. - С. 86-101.

8-А. Бибило, П.Н. Использование диаграмм двоичного выбора при декомпозиции программируемых логических матриц / П.Н. Бибило, П.В. Леончик // Автоматика и вычислительная техника. -2011.-№5.-С. 26-36.

Материалы конференций

9-А. Bibilo, P. The influence of the logic minimization on the complexity of circuits realized as a part of Gate Arrays and custom VLSI / P. Bibilo, P. Liavonchyk // Proc. of 3rd IF AC Workshop on Discrete Event System Design (DESDes'06). Rydzyna, 26-28 September 2006 / University of Zielona Gora, 2006 - P. 185-190.

10-A. Бибило, П.Н. Оптимизация многоуровневых представлений систем булевых функций на основе диаграмм двоичного выбора / П.Н. Бибило, П.В. Леончик // Автоматизация проектирования дискретных систем (Computer-Aided Design of Discrete Devices - CAD DD'07): материалы Шестой Междунар. конф., Минск, 14-15 ноября 2007 г.: в 2 т. / ОИПИ НАН Беларуси. - Минск, 2007.-Т. 2.-С. 162-169.

11-А. Леончик, П.В. Алгоритм покрытия булевой матрицы / П.В. Леончик //а Танаевскиеа чтения:аа докладыа Третьейа Междунар.а научн.а конф.,а Минск,

28 марта 2007 г. / ОИПИ НАН Беларуси; науч.ред. B.C. Гордон. - Минск, 2007 -С. 99-103.

12-А. Бибило, П.Н. Декомпозиция булевых функций, заданных диаграммами двоичного выбора / П.Н. Бибило, П.В. Леончик // Проблемы проектирования и производства радиоэлектронных средств: сборник материалов V Междунар. научн. - техн. конф.: в 3-х т., Новополоцк, 29-30 мая 2008 г. / ПТУ; под общ. ред. СВ. Абламейко, М.Л. Хейфица - Новополоцк, 2008 - Т. III. Информатика. - С. 68-71.

13-А. Бибило, П.Н. Декомпозиция булевых функций, заданных диаграммой двоичного выбора / П.Н. Бибило, П.В. Леончик // Проблемы разработки перспективных микро- наноэлектронных систем-2010 (МЭС-2010): сборник трудов IV Всероссийской науч.-техн. конф., Подмосковье, 04-08 октября 2010 г.; под. общ. ред. академика РАН А.Л. Стемпковского - М.: ИППМ РАН, 2010. - С. 2-7.

14-А. Бибило, П.Н. Использование диаграмм двоичного выбора при декомпозиции программируемых логических матриц / П.Н. Бибило, П.В. Леончик // Автоматизация проектирования дискретных систем (CAD DD'10): материалы Седьмой Междунар. конф., Минск, 16-17 ноября 2010 г. / ОИПИ НАН Беларуси.-Минск, 2010.-С. 171-181.

Тезисы докладов

15-А. Бибило, П.Н. Декомпозиция булевых функций, заданных диаграммами двоичного выбора /П.Н. Бибило, П.В. Леончик // Дискретная математика, алгебра и их приложения: тезисы докладов междунар. науч. конф., Минск, 19-22 октября 2009 г. /Институт математики НАН Беларуси, 2009. -С. 82-83.

16-А. Леончик, П.В. Минимизация систем булевых функций в классе ДНФ с дублированием / П.В Леончик // Информационные технологии в промышленности (ITP2008): тезисы докладов Пятой Междунар. научн. - техн. конф., Минск, 22-24 октября 2008 г. / ОИПИ НАН Беларуси; науч. редактор Е.В. Владимиров - Минск, 2008 - С. 218-219.

РЭЗЮМЕ

явончык Павел Вацлававч

АПТЫМВАЦЫЯ ПРАДСТАУЛЕННЯУ

С1СТЭМ БУЛЕВЫХ ФУНКЦЫЙ ДЛЯ ЗН1ЖЭННЯ

СКЛАДАНАСЦI ЭНЕРГАСПАЖЫВАННЯ

КАМБШАЦЫЙНЫХ СХЕМ

Ключавыя словъг. Булева функцыя, дыз'юнктыуная нармальная форма, дыяграма двайковага выбару, дэкампазщыя, лагчная схема, энергаспажыванне.

Мэтай працы з'яуляецца распрацоука алгарытмау праграм аптьмзаць двухузроуневых шматузроуневых уяуленняу сстзм булевых функцый.

Аб'ектам даследавання з'яуляюцца прадстауленн сстзм булевых функцый у выглядзе дыз'юнктыуных формау (ДНФ), дыяграм двайковага выбару, пабудаваных на аснове раскладання Шэнана, прадстаулення у выглядзе функцыянальных раскладанняу (суперпазцьй).

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

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

Прапанаваныя алгарытмы праграмна рзалзавань уключаны у склад распрацаваных у АП НАН Беларус сстзм аутаматызаванага праектавання дыскрэтных прыладау чбавьх ЗВС.

Распрацаваныя праграмы могуць быць выкарыстаны у праектных арганзацьях для памяншэння складанасц функцыянальных апсанняу камбнацьйнай логк пры праектаванн чбавай апаратуры на праграмуемых лагчньх нтзгральньх схемах на заказных чбавьх ЗВС. Распрацаваныя праграмныя сродк могуць быць выкарыстаны у навучальным працэсе у ВНУ пры падрыхтоуцы спецьялстау-праекцроушчькау электронных чбавьх схем.

РЕЗЮМЕ

еончик Павел Вацлавович

ОПТИМИЗАЦИЯ ПРЕДСТАВЛЕНИЙ

СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ ДЛЯ СНИЖЕНИЯ

СЛОЖНОСТИ И ЭНЕРГОПОТРЕБЛЕНИЯ

КОМБИНАЦИОННЫХ СХЕМ

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

Целью работы является разработка алгоритмов и программ оптимизации двухуровневых и многоуровневых представлений систем булевых функций.

Объектом исследования являются представления систем булевых функций в виде дизъюнктивных форм (ДНФ), диаграмм двоичного выбора, построенных на основе разложения Шеннона, и представления в виде функциональных разложений (суперпозиций).

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

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

Предложенные алгоритмы программно реализованы и включены в состав разработанных в ОИПИ НАЛ Беларуси систем автоматизированного проектирования дискретных устройств и цифровых СБИС.

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

SUMMARY

Pavel Liavonchyk

OPTIMIZATION OF REPRESENTATIONS OF

SYSTEMS OF BOOLEAN FUNCTIONS TO REDUCE

THE COMPLEXITY AND POWER

CONSUMPTION OF COMBINATION CIRCUITS

Key words: Boolean function, disjunctive normal form, binary decision diagram, decomposition, logic circuit, power consumption.

The aim of the dissertation is the development of algorithms and programs for optimization of two-level and multi-level representations of Boolean function systems.

The object of the dissertation is representations of Boolean function systems in the form of sum of products, binary decision diagrams constructed on the basis of Shannon expansion, and representations in the form of functional decomposition (superpositions).

The methods for optimization of Boolean functions representations at the stage of technologically independent optimization in the process of synthesis of combination circuits are studied in the dissertation. The algorithms of the optimization of the two-level Boolean functions representations with regard for the complexity and power consumption of the logic circuits under design, have been developed. A new algorithm to search for a set of all prime implicants is suggested, which allows increasing the dimension of the problems being solved and reducing the computation time. An algorithm to solve the cover problem intended for sparse Boolean arrays is given.

An algorithm for optimization of multi-level representations of DNF systems of completely specified Boolean functions on the basis of construction of binary decision diagrams, as well as a method for decomposition of completely specified Boolean functions systems by a two-block partition of the set of arguments, and an algorithm to choose the arguments partition are suggested. The developed algorithms are aimed at minimizing the complexity of logic circuits in different technological bases and at reducing power consumption of logic circuits of custom VLSI (very large-scale integration).

The suggested algorithms have been implemented in software and included into the systems of computer-aided design of discrete field and digital VLSI which have been developed in the United Institute of Problems of Informatics of the National Academy of Sciences of Belarus.

The developed software can be used by design organizations to minimize the complexity of functional descriptions of combination logic in the process of designing of digital equipment in the programmable logic integrated circuits and in custom digital VLSI. The developed software can be applied in the studying process at universities to train designers of electronic digital circuits.

Все авторефераты - Беларусь

Архивные справочники

Blog

Автореферат диссертации