WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

«Оптимизация представлений систем булевых функций для снижения сложности и энергопотребления комбинационных схем» по специальности «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: lipn@newman.bas-net.by.

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

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


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


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


ВВЕДЕНИЕ

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

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

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

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

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

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

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

1


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

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

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

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

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

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

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

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

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

2


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

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

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

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

Основные теоретические и практические результаты работы докладывались на следующих конференциях: 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 гг. Содержание опубликованных работ соответствует теме диссертации.

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

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

3


многоуровневых представлений булевых функций. Основная часть материала диссертации излагается в четырех главах. Основные результаты диссертации формулируются в заключении, за которым идет список использованных источников. Общий объем диссертации составляет 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, понимается граф, задающий разложение

4


Шеннона булевой функции 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)} булевых функций в классе ДНФ заключается в поиске системы ДНФ булевых функций, содержащей минимальное число конъюнкций, на которых заданы ДНФ всех функций системы. Такую систему ДНФ будем называть кратчайшей.

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

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

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

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

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

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

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

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

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

5


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

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

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

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

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

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

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

6


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

Рассматриваются 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,

где

Yi

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

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

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


Yl

-п-Ъ

Y2

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

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

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

7


коэффициенты разложения Шеннона по переменным блока 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. Построение разложение Шеннона

8


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 было возможно меньшим.

9


Процедура выбор разбиения 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 находит лучшее решение, чем программа

10


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

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

Имя

схемы

n

m

Программа Espresso

Программа Tie

к

ґ,с

к

ґ,с

тах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п + т)хк, где п - число входов схемы ПЛМ; т - число

11


выходов; к - промежуточных шин (число элементарных конъюнкций в реализуемой системе ДНФ булевых функций). Программа 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, выступающей в качестве предварительного этапа синтеза

12


комбинационных схем, реализуемых в составе БМК или 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.

13


VHDL-

описание

логической

схемы


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


Spice-описание

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

схемы



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

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

сигналов


Система

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

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

(AccuSim, Mentor Graphics)


Библиотека

Spice-описаний

логических

элементов


ї

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

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

(Average)

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

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

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


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

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

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

ш


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

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

14


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

ЗАКЛЮЧЕНИЕ

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

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

15


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

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

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

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

16


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

Статьи

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

17


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.

18


РЭЗЮМЕ

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

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

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

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

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

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

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

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

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

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

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

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

19


РЕЗЮМЕ

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

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

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

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

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

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

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

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

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

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

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

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

20


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.

21

 



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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