автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование алгоритмов синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ

Сибирский физико-технический институт им. Кузнецова при Томском государственном университете

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ СИНТЕЗА МИНИМАЛЬНЫХ ОДНОЯРУСНЫХ КОМБИНАЦИОННЫХ СХЕМ В БАЗИСАХ ПМВ, ПЗУ, ПЛМ

Специальность 05.13.01 "Управление в технических системах"

Автореферат диссертации на соискание учёной степени кандидата технических наук

УДК 519.713.4, 519.718.7

Андреева Людмила Николаевна

?

Томск-2000

Работа выполнена в Сибирском физико-техническом институте при Томском государственном университете

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

доцент Оранов A.M.

Официальные оппоненты: доктор технических наук,

профессор Агибалов Г.П.

кандидат технических наук, доцент Шевелев Ю.П.

Ведущая организация: Томский политехнический университет

г. Томск.

Защита состоится «27» декабря 2000 г. в 14.30 на заседании диссертационного совета Д063.53.03 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина 36.

С диссертацией можно ознакомиться в библиотеке Томского государственного университета.

Автореферат разослан1123 " ноября 2000 г. Ученый секретарь диссертац^онйопб совета, к. ф.-м. н., доцент _ /Р Л/ Б.Е. Тривоженко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Программируемые матрицы вентилей (ПМВ), программируемые логические матрицы (ПЛМ), программируемые постоянные запоминающие устройства (ППЗУ), или просто (ПЗУ) являются разновидностями программируемых (пользователем) логических интегральных схем (ПЛИС) или, другими словами, программируемых логических устройств (ПЛУ) - Programmable Logic Devices (PLD), и находят широкое применение в качестве элементной базы современных устройств логического управления (УЛУ), в том числе простейших из них - комбинационных схем. Минимальные по числу элементов одноярусные комбинационные схемы в базисах ПМВ, ПЗУ, ПЛМ представляют особый интерес в силу их низкой стоимости, малых габаритов, веса, потребляемой мощности и высокого быстродействия. Различают два типа одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ: 1) схемы, не допускающие объединения выходов своих элементов по схеме ИЛИ и 2) схемы, допускающие объединение выходов своих элементов по схеме ИЛИ посредством проводной дизъюнкции или отдельных элементов ИЛИ. Заметим, однако, что в случае использования отдельных элементов ИЛИ схемы второго типа можно считать одноярусными лишь условно. Синтез (построение) одноярусной схемы любого из этих типов обычно осуществляется исходя из системы булевых функций, заданных в дизъюнктивной нормальной форме (ДНФ). Синтезированная (построенная) :хема должна реализовать заданную систему булевых функций (ДНФ). Существующие методы и алгоритмы синтеза одноярусных комбинационных :хем в базисах ПМВ, ПЗУ, ПЛМ в большинстве своем являются весьма шстными и приближенными, т.е. ориентированы на решение довольно узких слассов задач с использованием в синтезе элементов только одного типа либо ПМВ, либо ПЗУ, либо ПЛМ) и не гарантируют минимум числа (атрачиваемых базисных элементов. Вот почему разработка и исследование тгоритмов синтеза минимальных одноярусных комбинационных схем в >азисах ПМВ, ПЗУ, ПЛМ, рассчитанных на решение более широких классов

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

Цель работы -1. Сформулировать абстрактную математическую задачу, как модель широкого класса задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ. 2. Разработать точный алгоритм решения сформулированной абстрактной задачи. 3. Исследовать теоретически и экспериментально свойства сформулированной абстрактной задачи и разработанного алгоритма ее решения и, тем самым, возможность их использования в синтезе минимальных одноярусных комбинационных схем реальной сложности. 4. Указать способы сведения задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ к сформулированной абстрактной задаче.

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

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

исследованы как теоретически (с применением теории Л'Р-полноты), так и экспериментально (на ЭВМ) - установлена сильная МР-трудность задачи кратчайшего допустимого разбиения набора объектов и, следовательно, экспоненциальная сложность предложенного алгоритма ее решения, выделены два полиномиальных частных случая задачи разбиения набора объектов, проведены испытания алгоритма кратчайшего допустимого разбиения на потоке из нескольких десятков задач различной сложности, сделаны выводы и даны рекомендации о возможностях его практического использования. Указаны способы сведения трех сформулированных задач синтеза к задаче кратчайшего допустимого разбиения набора объектов. Кроме того, получены оценки погрешности двух приближенных алгоритмов разбиения набора объектов, используемых в 7-методе для построения начального разбиения.

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

Практическая ценность. Предложенный алгоритм кратчайшего допустимого разбиения набора объектов и реализующая его программа на языке Си могут быть использованы в системах автоматизированного проектирования (САПР) УЛУ для автоматического решения трех сформулированных в диссертации задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ сведением их к задаче кратчайшего допустимого разбиения набора объектов указанными в работе способами.

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

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

Апробация работы. Результаты диссертации по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского государственного университета (ТГУ) и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, в период с 1990 по 1997 гг. они докладывались на всесоюзных или международных конференциях в г.г. Москве и Минске, что подтверждается соответствующими публикациями тезисов докладов и доклада, указанных в конце автореферата. Прохождение отчетности по линии РФФИ и НИР и частичное использование результатов диссертации в учебном процессе при подготовке студентов соответствующих специальностей в ТГУ также можно считать апробацией диссертационной работы.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, приложения и списка цитированной литературы. Объем диссертации составляет страниц текста, набранного в Word 6.0 (Шрифт - Times New Roman Суг, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе, титульный лист - 1 е., оглавление - 2 е., основной текст, включающий 4 рис. и 4 таблицы, - 68 е., библиография из 57 наименований - 6 с.

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

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

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

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

Суть 7-метода применительно к задаче разбиения набора (множества) объектов состоит в следующем. Поиск кратчайшего допустимого разбиения происходит в пространстве всех допустимых разбиений, которое представлено деревом поиска. Вершинам этого дерева сопоставлены подмножества разбиваемого множества, ребрам - допустимые подмножества разбиваемого множества, т.е. классы допустимых разбиений. Корню дерева сопоставлено разбиваемое множество, а листьям дерева - пустое множество. Допустимое разбиение заданного множества соответствует пути в дереве из корня в лист. Всевозможные пути в дереве поиска из корня в листья задают все допустимые разбиения заданного множества. Для того чтобы отыскать кратчайшее допустимое разбиение необходимо найти кратчайший путь в дереве поиска. Процедура обхода дерева поиска представляет собой общий алгоритм поиска с возвращением и сохранением более короткого разбиения. Сокращение обхода дерева поиска происходит с помощью механизмов сокращения перебора (алгоритма перечисления - (р, операции сокращения -функции нижней оценки ^ и множества алгоритмов начального разбиения - р), называемых параметрами метода, которые при подходящем их выборе позволяют выделить часть дерева поиска, содержащую хотя бы один кратчайший путь, а остальную часть дерева поиска не рассматривать. Чем полнее исследованы комбинаторные свойства той или иной задачи разбиения, тем эффективнее могут быть определены параметры Г-метода и тем больше удастся сократить возникающий перебор.

Таким образом, в общих чертах выстраивается основанная на Г-методе технология синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, включающая три основных элемента: 1) оригинальную задачу кратчайшего допустимого разбиения набора объектов, как модель (формальный эквивалент) широкого класса задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ; 2) известный метод сокращенного обхода дерева поиска, как метод решения этой задачи разбиения и 3) оригинальные способы сведения различных задач синтеза к задаче кратчайшего допустимого разбиения набора объектов.

Во второй главе, названной "Технология синтеза минимальных

одноярусных комбинационных схем базисах ПМВ, ПЗУ, ПЛМ", намеченная в первой главе технология описывается детально. Формулируется задача кратчайшего допустимого разбиения набора объектов. В ней разбиваемым множеством является набор объектов Ь{Ь,М,№) с атрибутами ¿, М, N соответственно. Объект в наборе ЦЬ,М,1\[) представляет собой кортеж (набор, вектор, логическую запись) <1,М/,Ыр> значений атрибутов £, М, N соответственно, где / - номер объекта, являющийся его идентификатором, Ми N1 - конечные множества, /=1,...,«, п> 1. Допускающим множеством является набор объектов./(./,(/,V,IV) с атрибутами./, и, V, IV соответственно. Объект в наборе V, IV) представляет собой кортеж <у',М;,уу,^у> значений атрибутов ./, и, V, IV соответственно, где у - номер объекта, являющийся его идентификатором, му, уу, Wj - натуральные числа, у=1,...,/я, т>\. (Поскольку значения /, j атрибутов Ь, У являются идентификаторами объектов в соответствующих наборах объектов ЦЬ,М,Ю, .К-!,и,У,Щ, то использование символов Ь, У для обозначения самих этих наборов объектов вполне корректно.) Пусть также

\fleL3jcJi 1 < и; л | Л/, | < уул | .V, | <> V,). (2.1)

Здесь и далее с целью корректного использования теоретико-множественных

понятий и обозначений значения атрибутов в М, Л', и, V, IV в том числе и одинаковые различаются их номерами. Поскольку значения атрибутов и./ являются идентификаторами объектов в наборах объектов Ь{Ь, М, ¿V), ./(./, и, V, IV), то использование символов £ и У для обозначения самих этих наборов объектов также корректно. Для любого А<^Ь вводится обозначение

¡еЛ /еЛ

и множество А называется ./-допустимым или просто допустимым множеством, если 3]^04\<и,л\О{А,Щ\ЩА\О{А,Щ^). (2.2)

Разбиение К множества (набора объектов) Ь называется ./-допустимым или просто допустимым если каждый блок Л<=Я является допустимым множеством. Допустимое разбиение Я является ./-минимальным или У -кратчайшим или просто кратчайшим, если |/?|<|/Г| для любого допустимого разбиения Я' множества (набора объектов) Ь. В дальнейшем кратчайшее разбиение обозначается через Як.

Ставится следующая задача: для заданных наборов объектов Ц/.,Л/,Л') и ./(./,II,V,IV), удовлетворяющих условию (2.1), найти кратчайшее разбиение множества Ь.

Нетрудно видеть, что задача разбиения является Т-интерпретацией, если положить Х=Ь, /7(/?к)=|/?к| и множество Р определим как совокупность всех допустимых подмножеств в X (где через Иг обозначено допустимое разбиение произвольного множества Ус1). Следовательно, задача разбиения набора объектов может быть решена методом сокращенного обхода дерева поиска, если эффективно определить параметры этого метода, а именно: алгоритм перечисления - (р, операцию сокращения - граничную функцию - /ч, и алгоритмы начального разбиения - рх и рг, что и делается ниже.

Предварительно для каждого 1<=Ь через 57 обозначается число собственных, т.е. не принадлежащих другим множествам в М-={М\,...,Мп) элементов множества М/, и через Ст/ — число собственных, т.е. не принадлежащих другим множествам в Ы={Ыи...,Ы„} элементов множества Л/}_ На множестве кортежей <!Л//|,у(,|М(|,<7/>, /=1,...,и, вводится лексикографический порядок > и объекты в Ь нумеруются в соответствии с этим порядком. Считается, что в любом подмножестве Ус:/, данный порядок сохраняется. Из J удаляется всякий объект _/' для которого ЗA:eJ(м^>«/лvJ^>v7лvv^>v^)vV/e¿(|M/|>Vyv|A'/|>w;). В результате получается неприводимый набор объектов У'сУ. Очевидно, что всякое ./'-кратчайшее разбиение множества Ь является также ^/-кратчайшим разбиением этого множества. Поэтому впредь набор объектов 3 считается неприводимым. На множестве кортежей /=1 ,.,.,/н вводится лексикографический

порядок < и объекты в У нумеруются в соответствии с этим порядком. Для любого /еХ и любого множество В£У)с:У определяется как множество всех тех номеров Ае У, расположенных в порядке возрастания, для которых Ы1 и {1,к} есть допустимое множество. Допустимое множество АсУ называется максимальным допустимым подмножеством в У, если добавление к нему любого 1еУ нарушает его допустимость. Обозначим через щ{У) множество всех максимальных допустимых подмножеств в У, содержащих некоторый фиксированный /е У.

Алгоритмы начального разбиения. В качестве начального разбиения Я0

выберем разбиение с меньшим числом классов среди двух разбиений и Л2 множества Х-Ь на допустимые подмножества, доставляемые следующими быстродействующими приближенными алгоритмами рх и рг , которые являются аналогами одноименных алгоритмов, предложенных авторами метода. В формулировке этих алгоритмов предполагается, что объекты в наборах ЬиЗ упорядочены указанными выше способами.

Алгоритм р\

Шаг 1.А:=Ь, Л,:=0.

Ш аг2. В:=0.

Ш а г 3. Если \В\=ит или не существует 1еА-В и таких, что для С=Ди{/} справедливо |С| <и,л 10(С,М)|<у;л 10(С,/V) |<и>у, то шаг 4; иначе выбирается наименьшее такое /, В:=С и выполняется шаг 3 сначала.

Ш а г 4. Л^^и{В}, А:=А-В. Если А*0, то шаг 2; иначе конец, /?! -результат.

Алгоритм рг

Ш а г 1. к.=\, 1:=п, Л2:=0.

Ш а г 2. Найдем наибольшее для которого существует у е./ такой, что для А={к,к+\,...,ц} справедливо \Л\<и,л| 0(Л,Л/)|<у7л |0(/1,Лг)|<м'у. В случае д<1 найдем (если возможно) наименьшее г, для которого <7<г<1 и существует такой, что для С=А*иВ, где В={г,г+\,...,1} справедливо |С|<г/(л|О(С,А0|<у,л|О(С,ЛГ)\<Щ- Если \А\=и„„ или или \A\--u, и \0{А,М)\=^ и \0(А,Щ=\\/р или такого г не существует, то В:=0 и г~1+\.

Ш а г 3. /?2:=Л2и{{/1и5}}. Если ц<1 и с]+\<г, то к-~д+\, 1:=г-1 и шаг 2; иначе конец, /?2 ~ результат.

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

1. Если для некоторого 1еУ множество А~В^У)^{1) является допустимым, то ср{У)={А} для наименьшего такого /.

2. Если для некоторых 1,кеУ множество А-{1,к}с:У есть максимальное допустимое множество и С=(В/(У)иВк(У))-А есть допустимое множество, то <р(У)={А} для наименьших так!гх I и к.

3. Если для некоторых различных 1,к,р,1е У, таких что ¡еВ^У), ре.Вк{У)

множества А={1,к)сУ и С={/,р} допустимы и любое трехэлементное подмножество из У, включающее / или к недопустимо, то /р(У)={А} для наименьших таких / и к

4. Во всех остальных случаях для наименьшего / из У.

Алгоритм построения множества <р,(У). Пусть УсХ и В/(У)с:У. Алгоритм строит множество (р/{У) для заданного /е У в процессе направленного перебора по дереву, аналогично построению всех максимальных независимых (внутренне устойчивых) множеств в графе (Кристофидес Н.).

Каждая вершина 5 дерева представляет собой три изменяющиеся в процессе перебора множества: А$ - строящееся допустимое подмножество в У; В, - множество всех тех кеВ,(У)-А„ за счет которых множество А, может быть расширено, т.е. всех тех к, для которых А^и{к) есть допустимое множество и которые еще не использовались для расширения множества А С, - множество всех тех квВ^У), для которых А ¿и {к} есть недопустимое множество, т.е. тех к которые нельзя использовать для расширения множества А$.

Шаг 1. *:=1,Л1:={/}, В/.=В,(У), С,:=0, р,:=0.

Ш а г 2. Если ЛЛ=0, то шаг 3. В противном случае выбираем первый по порядку номер ДеД, и полагаем р5:-1, если 0(Ах,М)^М, и 0(А„М)т^ Л^ . Не

изменяя множества Вх строим множества Л5ц:=/1ли{/л}, С5ц, Вщ\=В3-(С5+1и{/;}), полагаем 1, /?5:=0 и выполняем шаг2.

Ш а г 3. Если |Л5|+|С5|=|£;(}0Н"1, то заносим А5 в список максимальных допустимых подмножеств множества У.

Шаг 4. Если 5=1, то конец - построены все максимальные допустимые подмножества в У, содержащие номер /, иначе полагаем А5.\-~АГ {/,-/}, £5-ь=А;.г{4-|}, И в случае и Щ+Щ^ и \0(А^В,,М)\<^ и

для некоторого или В^=0 повторим шаг 4 сначала. В противном случае шаг 2.

Операция сокращения (Т) выделяет некоторое подмножество ^{(р^У)) в множестве <р/(У). Для определена операции Чу введем на множестве всех подмножеств в К не транзитивное и не антисимметричное отношение сс

следующим образом. Пусть Л={гь...,/р}сК, В={ки...,кч}сУ, /2<—</р, к2<—<кч. Тогда Асе Во

[р>длУ/б {1,...,<?}(/,Мк, - М^ |<а-,( л| МК - Л^ !<а,()))] (2.2)

v[/l-Д-{¿}л(C=(ДД^0uB)-^^37eУ(¡q<г/7л|O(C,Л^|<vyл|O(C,Л0|<и'>))] (2.3)

и результат применения операции Ч* к множеству 2с.(р,{У) определяется как множество Ч,(2)=Ч/2(Ч>1(2)), где Т)(2)с2 есть множество, содержащее всякое такое множество для которого в Z не существует множества АфВ и А ОС В согласно (2.2), а ^(ЧМ^сТ^ есть множество, содержащее всякое такое множество В&Х¥\(Т), для которого в не существует

множества АфВ и А сев согласно (2.2) или, если такое АеЧ'^Т) существует, топ Вес А согласно (2.3). При этом А (либо В) не включается в Ч/(2).

Граничная функция определяется формулой Го(У)~= тах(к,1,р, г) где к4\У\/и„\ Й\0(У,М)\!шах уД р^\0(У,М}\/шахм>у1

7 б/ у'еУ

и г есть мощность некоторого подмножества попарно несовместимых объектов в У, т.е. таких различных У, для которых {5,/} есть недопустимое множество, определяемая посредством следующего несложного алгоритма.

Алгоритм г

Шаг 1 .А:=У, г.=0.

Ш а г 2. Если /1=0, то конец, г - результат; в противном случае наименьший номер /еА с наименьшим пересечением Аг\В{У), А:=А-(В/(У)и{/}), г.=гН и повторяем шаг 2 сначала.

Доказывается допустимость предложенных значений (выражений) <р и ЧЛ Дается пример построения кратчайшего допустимого разбиения набора объектов, т.е. пример решения задачи разбиения набора объектов Г-методом с предложенными значениями параметров.

Формулируются следующий три задачи синтеза минимальных по числу элементов одноярусных комбинационных схем в различных базисах ПЛИС, отличающиеся базисом или типом схемы, и даются способы их сведения к задаче разбиения набора объектов. В первой задаче требуется реализовать заданную систему И из п> 1 ДНФ £>|,...,Д, минимальной по числу элементов одноярусной комбинационной схемой, не допускающей объединения

выходов своих элементов схеме ИЛИ, в базисе

£={ГШМ1(Л1^1,91),...,Г1ШД5р,//,,^),ПЗУ/1+1(^+1,'/н1),-..,ПЗУт(5т,/т)}, где

0<р<т. Иначе говоря, требуется разбить систему £> на минимальное число подсистем, каждая из которых реализуема хотя бы одним элементом базиса Е. Принимая систему В за набор объектов X, а базис Е - за набор объектов ^ т.е. принимая для 1=1,...,п за объект </,А//,Л'/>, где М/ есть множество букв в £>/; и N1 есть множество конъюнкций в £>/ и принимаяу-й элемент базиса Е для у'=1 ,...,т за объект <у,м7,у/,и'у>, где у,:^, щ=Ц} для у-1 ,...,р и и/=/у,

и>у:=2Т/ для)=р+\,...,т, получаем задачу разбиения набора объектов. Во второй задаче требуется реализовать заданную систему /) из п> 1 ДНФ ..,£)„ минимальной по числу элементов одноярусной комбинационной схемой, не допускающей объединения выходов своих элементов по схеме ИЛИ, в базисе Е из т> 1 настраиваемых ПЛМ/г^, <7,), 7=1,где г, - число двунаправленных шин, которые могут служить, как входами, так и выходами, и Ц] - число промежуточных шин. Иначе говоря, требуется разбить систему О на минимальное число подсистем, каждая из которых реализуема хотя бы одним элементом базиса Е. Принимая систему О за набор объектов Ь, а базис Е - за набор объектов У, т.е. принимая Д для 1=\,...,п за объект </,Л//Д>, где Л/, есть множество букв в £>/, включающее наряду с буквами и номер / ДНФ О/, и N1 есть множество конъюнкций в Д и принимая у-й элемент базиса Е для у'=1,...,/и за объект где и/=я,

получаем задачу разбиения набора объектов. В третьей задача требуется реализовать заданную систему О из п> 1 ДНФ 01,...,0„ минимальной по числу элементов одноярусной комбинационной схемой, допускающей объединение выходов своих элементов схеме ИЛИ, в базисе £={ПЛМ1(5Ь/,,90^--,ПЛМ/5р,^,<7р),ПМВ^ч(5/^1,/'/Н.1),...,ПМВт(5т,/„,)}, где О<р<т. Иначе говоря, требуется разбить множество К всех п различных коньюнкций системы й на минимальное число подмножеств, каждое из которых реализуется хотя бы одним элементом базиса Е. Принимая множество К за набор объектов а базис Е - за набор объектов т.е. принимая К\ для /=1,...,и за объект </,Л/;,Лг/>, где А// есть множество букв в К\ и N1 есть множество ДНФ системы Д содержащих и принимая у-й

элемент базиса Е дляу'=1 ,...,т за объект <у,м;,у/,и'у>, где Vj:=Sj, для

/=1 ,...,р и и/.=(р у^!, 1^:=/,, для получаем задачу разбиения

набора объектов.

Заметим, что условие (2.1), наложенное в задаче разбиения набора объектов на наборы объектов ¿(/,,Л/,Л0 и ./(У,ЦК,(Г) является по существу условием разрешимости как самой задачи разбиения набора объектов, так и всякой сводимой к ней задачи синтеза.

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

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

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

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

Исследуется (с применением теории /УЛ-полноты) сложность задачи разбиения набора объектов, а именно: устанавливается сильная А'Р-грудность задачи кратчайшего допустимого разбиения набора объектов, и выделяются два полиномиальных частных случая задачи разбиения набора объектов в том числе задача, эквивалентная задаче о максимальном

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

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

/>г(/)<(ОРТ(У)-1) м+1, где ОРТ(/) - число классов кратчайшего разбиения Р? индивудуальной задачи /; р\ (/) - число классов разбиения R{, полученного с помощью алгоритма р1; р2(Г) - число классов разбиения R2, полученного с помощью алгоритма р2.0РТ(У) - число классов кратчайшего разбиения Л* ивдивудуальной задачи /;. и= шах иу

jeJ

Для экспериментального исследования алгоритмов разбиения набора объектов был запрограммирован на языке Си алгоритм кратчайшего допустимого разбиения набора объектов, т.е. Г-метод с предложенными выше параметрами, в числе которых и приближенные алгоритмы рь р1 начального разбиения. Для проведения экспериментального исследования программы и, следовательно, названных алгоритмов разбиения были сгенерированы 54 псевдослучайные индивидуальные задачи. Кроме того, по известным из технической документации системам ДНФ, так называемым "benchmarks", были построены еще 9 индивидуальных задач. Это экспериментальное исследование состояло в решении этих 63 задач на ЭВМ РС-ХТ(АС). В ходе эксперимента были выяснены два вопроса. Во-первых, были найдены возможные границы эффективности для каждого из определенных выше параметров Г-метода на примере решенных 63 задач, т.е. показано, что применение параметров не увеличивает время решения задачи и указана та часть дерева поиска, на которой применение той или иной совокупности параметров приводит к его сокращению. Во-вторых, определено отличие поведения приближенных алгоритмов начального разбиения на примерах этих 63 задач от их поведения в худшем случае, установленного полученными выше оценками их погрешности. Результаты эксперимента сведены в таблицу.

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

1. Установленная сильная Л^-трудность задачи кратчайшего допустимого разбиения набора объектов означает и сильную ///"-трудность сводимых к ней задач синтеза одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, так как задача разбиения набора объектов сохраняет основные комбинаторные свойства названных поэтому задач синтеза.

2. Сильная ЛТ-трудность задачи разбиения набора объектов отнюдь не делает безнадежным построение кратчайших допустимых разбиений и, следовательно, минимальных (но числу элементов) одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, так как доля сложных (экспоненциальных) индивидуальных задач (примеров) в множестве всех индивидуальных задач массовой задачи разбиения может быть весьма незначительной. Так в проведенном эксперименте индивидуальными задачами, требующими экспоненциального времени решения, являются, по всей видимости, всего лишь 5 из 63 задач.

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

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

примере проведенного эксперимента эти оценки не достигались. Более того, разбиения, полученные с помощью алгоритма ри отличались от соответствующих кратчайших разбиений не более чем на 1-5 классов, что составляет от 3% до 28%, а разбиения, полученные с помощью алгоритма р1у - не более чем на 1-15 классов, что составляет от 4% до 33%. Таким образом использование алгоритмов ри рх возможно не только в Г-методе для получения начального разбиения, улучшаемого далее в процессе обхода дерева поиска, но и отдельно от него.

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

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

ЗАКЛЮЧЕНИЕ

В данной диссертационной работе получены следующие результаты. Предлагается единая технология (общая теория) решения задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, которая включает три основных элемента:

1) оригинальную задачу кратчайшего допустимого разбиения набора объектов - как общую математическую модель различных задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ;

2) известный метод сокращенного обхода дерева поиска (Г-метод) (авторы: Агибалов Г.П., Беляев В.А.) с подобранными оригинальными параметрами - как метод решения задачи кратчайшего допустимого разбиения набора объектов;

3) оригинальный способ сведения задач синтеза к задаче кратчайшего допустимого разбиения набора объектов.

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

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

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

I. Технология решения задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ, включающая три основных элемента:

1) оригинальную задачу кратчайшего допустимого разбиения набора объектов - как общую математическую модель различных задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ;

2) известный метод сокращенного обхода дерева поиска с подобранными оригинальными параметрами - как метод решения задачи кратчайшего допустимого разбиения набора объектов,

3) оригинальный способ сведения задач синтеза к задаче кратчайшего допустимого разбиения набора объектов.

II. Разработанные по данной технологии алгоритмы синтеза:

1) минимальных одноярусных комбинационных схем, не допускающих объединения выходов своих элементов по схеме ИЛИ, в базисе из нескольких ПЛМ и нескольких ПЗУ, в том числе с несравнимыми наборами значений их параметров;

2) минимальных одноярусных комбинационных схем, не допускающих объединения выходов своих элементов по схеме ИЛИ, в базисе из нескольких настраиваемых ПЛМ, в том числе с несравнимыми наборами значений их параметров;

3) минимальных одноярусных комбинационных схем, допускающих объединение выходов своих элементов по схеме ИЛИ, в базисе из нескольких ПЛМ и нескольких ПМВ, в том числе с несравнимыми наборами значений их параметров.

III. Результаты исследования комбинаторных свойств задачи кратчайшего допустимого разбиения набора объектов и алгоритмов ее решения, а именно:

1) сильная ¿УР-трудность задачи кратчайшего допустимого разбиения набора объектов;

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

3) оценки погрешности двух алгоритмов начального разбиения;

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

По тематике диссертации опубликовано 9 печатных научных работ, в том числе: 5 статей в центральных изданиях, 1 доклад и 4 тезисов докладов в трудах всесоюзных и международных конференций.

1.Андреева Л.Н. Алгоритм синтеза минимальных схем из ПЛМ с заданным числом промежуточных шин// Автоматизация проектирования и конструирования в электронном машиностроении: Тез. докл. науч.-техн. конф. 28-30 апреля 1988 г. -М.: Минвуз РСФСР и МиЭМ - 1988 - С.57-58.

2. Оранов A.M., Андреева Л.Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах// Контроль, измерение, диагностика, ремонт и техническое обслуживание радиоэлектронных систем: Тез. докл. науч.-техн. конф. 23-25 октября 1991 г. - М.: Межведомственный координационный совет по методам и средствам измерений и контроля, МРП СССР, концерн "Гранит", ЦКБ "Мередиан", 1991. - С. 194-195.

3. Оранов A.M., Андреева Л.Н. Алгоритм минимального разбиения системы множеств// Автоматика и вычислительная техника. - 1992. - №2. -С. 37-44.

4. Оранов A.M., Андреева JI.H. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах// Автоматика и вычислительная техника. - 1992. - №5. - С. 57-63.

5. Оранов A.M., Андреева Л.Н. Алгоритм минимального разбиения некоторого набора объектов// Автоматика и вычислительная техника. - 1993. - №2. - С. 27-35.

6. Oranov A.M., Andreeva L.N. Complexity of some subproblems of partitioning objects set problem. - Proceedings of the International Conference "Computer- Aided Design of Discrete Devices" (CAD DD'95), vl, Minsk, 1995, p.48.

7. Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения// Автоматизация проектирования дискретных систем. Материалы второй международной конференции (12-14 ноября 1997 года, Минск. Том 3). - Минск: Институт технической кибернетики H АН Беларуси, 1997. - С. 228-231.

8. Андреева Л.Н., Оранов A.M. О сложности некоторых задач разбиения// Известия РАН. Теория и системы управления. - 1997. - №2. - С. 114-116.

9. Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения// Известия РАН. Теория и системы управления. - 1999. - №1. - С. 89-93.

Из результатов, полученных в соавторстве в диссертацию вошли: значения (выражения) параметров Г-метода для задачи разбиения набора объектов, способы сведения задач синтеза одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ к задаче разбиения набора объектов, теоремы о сложности этой задачи и качестве алгоритмов ее решения /2-9/.

Введение.

1. Обзор методов синтеза одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ.

1.1. Точные методы синтеза и решаемые ими задач.

1.2. Приближенные методы синтеза и решаемые ими задачи.

1.3. Выводы и перспективы.

2. Технология синтеза минимальных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ.

2.1. Постановка задачи разбиения набора объектов.

2.2. Параметры метода.

2.2.1. Алгоритмы начального разбиения.

2.2.2. Алгоритм перечисления допустимых подмножеств.

2.2.3. Операция сокращения.

2.2.4. Граничная функция.

2.2.5. Доказательство допустимости алгоритма перечисления и операции сокращения.

2.3. Пример построения кратчайшего допустимого разбиения набор объектов. 2.4. Способы сведения некоторых задач синтеза схем к задаче разбиения набора объектов.

2.5. Выводы.

3. Комбинаторные свойства задачи разбиения набора объектов и алгоритмов ее решения.

3.1. Сложность задачи разбиения набора объектов.

3.2. Оценки погрешности алгоритмов начального разбиения.

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

3.4. Выводы.

болыпинстве своем являются весьма частными и приближенными, т.е. ориентированы на решение довольно узких классов задач с использованием в синтезе элементов только одного типа (либо ПМВ, либо ПЗУ, либо ПЛМ) и не гарантируют минимум числа затрачиваемых базисных элементов. Вот почему разработка и исследование алгоритмов синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ, расчитанных на решение более широких классов задач, в том числе, с использованием различных базисных элементов представляется актуальной проблемой [46].

Цель работы - 1. Сформулировать абстрактную математическую задачу, как модель широкого класса задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ. 2. Разработать точный алгоритм решения сформулированной абстрактной задачи. 3. Исследовать теоретически и экспериментально свойства сформулированной абстрактной задачи и разработанного алгоритма ее решения и, тем самым, возможность их использования в синтезе минимальных одноярусных комбинационных схем реальной сложности. 4. Указать способы сведения задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ к сформулированной абстрактной задаче.

Методы исследования. Для достижения поставленной цели используются средства и методы дискретной математики (теории множеств, булевой алгебры, математической логики, комбинаторного анализа, теории синтеза управляющих систем), теории реляционных баз данных, теории Д/Р-полноты и языка программирования Си [48].

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

ПМВ, ПЗУ, ПЛМ, обобщающих соответствующие известные задачи. Для этих трех задач сформулирована абстрактная комбинаторная оптимизационная задача кратчайшего допустимого разбиения набора объектов, представляющая собой их единую математическую модель. Проанализированы возможные методы решения сформулированной задачи разбиения набора объектов такие, как метод полного перебора [40], методы 0-1 программирования [41,42], метод ветвей и границ [4,3944] и метод сокращенного обхода дерева поиска [39,40], называемый далее для краткости 7-методом. Выбран 7-метод и осуществлена его оригинальная алгоритмизация применительно к сформулированной задаче разбиения набора объектов. Полученный таким образом оригинальный алгоритм кратчайшего допустимого разбиения набора объектов запрограммирован на языке Си [48]. Свойства сформулированной задачи кратчайшего допустимого разбиения набора объектов и разработанного алгоритма ее решения исследованы как теоретически (с применением теории /УР-полноты), так и экспериментально (на ЭВМ) - установлена сильная А^-трудность задачи кратчайшего допустимого разбиения набора объектов и, следовательно, экспоненциальная сложность предложенного алгоритма ее решения, проведены испытания алгоритма кратчайшего допустимого разбиения на потоке из нескольких десятков задач различной сложности, сделаны выводы и даны рекомендации о возможностях его практического использования. Указаны способы сведения трех сформулированных задач синтеза к задаче кратчайшего допустимого разбиения набора объектов. Кроме того, получены оценки погрешности двух приближенных алгоритмов разбиения набора объектов, используемых в Т~методе для построения начального разбиения.

Практическая ценность. Предложенный алгоритм кратчайшего допустимого разбиения набора объектов и реализующая его программа на языке Си могут быть использованы в системах автоматизированного проектирования (САПР) УЛУ для автоматического решения трех сформулированных в диссертации задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ сведением их к задаче кратчайшего допустимого разбиения набора объектов указанными в работе способами.

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

Апробация работы. Результаты диссертации по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского государственного университета (ТГУ) и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, в период с 1990 по 1997 гг. они докладывались на всесоюзных или международных конференциях в г.г. Москве и Минске, что подтверждается соответствующими публикациями тезисов докладов [49,50,54] и доклада [55]. В целом по теме диссертации опубликовано 9 работ [49-57], из них 5 [51-53,56,57] -статьи в центральной печати. Прохождение отчетности по линии РФФИ и НИР и частичное использование результатов диссертации в учебном процессе при подготовке студентов соответствующих специальностей в ТГУ также можно считать апробацией диссертационной работы.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, приложения и списка цитированной литературы. Объем диссертации составляет страниц hSl текста, набранного в Word 6.0 (Шрифт - Times New Roman Суг, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе, титульный лист - 1 е., оглавление - 2 е., основной текст, включающий 4 рис. и 3 таблицы, -67с., библиография из 57 наименований - 7 с. и приложение - bfc.

Ш. Результаты исследования комбинаторных свойств задачи кратчайшего допустимого разбиения набора объектов и алгоритмов ее решения, а именно:

1) сильная А'Р-трудность задачи кратчайшего допустимого разбиения набора объектов;

2) два полиномиальных частных • случая задачи кратчайшего допустимого разбиения набора объектов, в том числе задача, эквивалентная задаче о максимальном паросочетании в графе;

3) оценки погрешности двух алгоритмов начального разбиения;

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

ЗАКЛЮЧЕНИЕ

В данной диссертационной работе получены следующие результаты.

Дан обзор известных задач и методов [1-38] синтеза одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, направленных на построение схем с возможно меньшим числом элементов. Из обзора видно, что все такие задачи синтеза являются по существу задачами разбиения одного множества (набора) объектов на допустимые по отношению к объектам другого множества классы. При этом в роли разбиваемого множества объектов выступает либо исходная система ДНФ, либо множество ее конъюнкций, а в роли допускающего множества объектов - базисные элементы и критерием качества разбиения является число классов в нем (чем оно меньше, тем лучше разбиение). Все это указывает на возможность представления всех указанных задач синтеза (при условии их более глубокой формализации) в виде одной абстрактной задачи разбиения набора объектов, разработки алгоритма решения этой задачи и таким образом - любой из указанных задач синтеза. Эта возможность реализована в диссертации в виде единой технологии (общей теории) решения задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ. Технология включает три основных элемента:

1) оригинальную задачу кратчайшего допустимого разбиения набора объектов - как общую математическую модель различных задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ;

2) известный метод сокращенного обхода дерева поиска (У-метод) [39,40] с подобранными оригинальными параметрами - как метод решения задачи кратчайшего/допустимого разбиения набора объектов;

3) оригинальный способ сведения задач синтеза к задаче кратчайшего допустимого разбиения набора объектов.

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

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

I. Технология решения задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ, включающая три основных элемента:

1) оригинальную задачу кратчайшего допустимого разбиения набора объектов - как общую математическую модель различных задач синтеза минимальных одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ; *

2) известный метод сокращенного обхода дерева поиска с подобранными оригинальными параметрами - как метод решения задачи кратчайшего допустимого разбиения набора объектов,

3) оригинальный способ сведения задач синтеза к задаче кратчайшего допустимого разбиения набора объектов.

П. Разработанные по данной технологии алгоритмы синтеза:

1-70I

1) минимальных одноярусных комбинационных схем, не допускающих объединения выходов своих элементов по схеме ИЛИ, в базисе из нескольких ПЛМ и нескольких ПЗУ, в том числе с несравнимыми наборами значений их параметров;

2) минимальных одноярусных комбинационных схем, не допускающих объединения выходов своих элементов по схеме ИЛИ, в базисе из нескольких настраиваемых ПЛМ, в том числе с несравнимыми наборами значений их параметров;

3) минимальных одноярусных комбинационных схем, допускающих объединение выходов своих элементов по схеме ИЛИ, в базисе из нескольких ПЛМ и нескольких ПМВ, в том числе с несравнимыми наборами значений их параметров.

1. Соловьев B.B. Проектирование функциональных узлов цифровых систем на программируемых логических устройствах. - Мн.: ПКООО "Бестпринт", 1996. - 252 е.

2. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. М.: Радио и связь, 1986.-272 с.

3. Баранов С.И., Баркалов A.A. Применение программируемых логических матриц в цифровой технике // Зарубежная радиоэлектроника. -1982. N6. - С. 67-79.

4. Закревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981.-414с.

5. Закревский А.Д., Матричный аппарат логического анализа и синтеза дискретных устройств из ПЛМ . Докл. АН СССР - 1977. - N 11.-е. 991-994.

6. Дудкин A.A. Алгоритмы минимального разбиения множества булевых векторов // Алгоритмы решения логико-комбинаторных задач. Минск: ИТК АН БССР, 1980. - С. 10-21.

7. Дудкин A.A. Разбиение множества строк булевой матрицы // Автоматизация логического проектирования дискретных устройств. -Минск: ИТК АН БСС^, 1980. Вып. 2 - С. 95-98.

8. Дудкин A.A. Модификация задачи о группировании аргументов // Алгоритмы логического проектирования. Минск: ИТК АН БССР, 1983.-С. 143-147.

9. Дудкин A.A. Матричный метод синтеза одноярусных сетей в базисе программируемых логических матриц // Автоматизацияпроектирования микропроцессорных устройств. Минск: ИТК АН БССР, 1986.-С. 100-107.

10. Ю.Закревский А.Д., Бибило П.Н., Дудкин A.A. Пакет программ синтеза комбинационных схем в базисе ПЛМ // УСиМ. 1985. - N 1. - С. 27-29.

11. Дудкин A.A. Логический синтез одноярусных комбинационных схем в базисе ПЛМ // Теория и методы автоматизации проектирования. -Минск: НТК АН БССР, 1984. -Вып. 4 С. 135-140.

12. Дудкин A.A., Поттосин Ю.В., Синичка A.A., Черемисинова Л.Д. Комплекс программ синтеза комбинационных схем в базисе ПЛМ // Материалы по математическому обеспечению ЭВМ. Минск: ИТК АН БССР, 1988. = 67 с. ■

13. Automated PL A Synthesis of the Combinatorial Logic of a DDL Description / Dietmeyer D.L., Doshi М.Н./У IEEE Proc. E- 1990,- E. 137, N 3,- P.213-225. *

14. Баранов С.И., Синев B.H. Программируемые логические матрицы в цифровых системах // Зарубежная радиоэлектроника. -1979. N 1. - С. 65-82.

15. Скляров В. А. Синтез автоматов на матричных БИС. Минск: Наука и техника, 1984. - 287 с.

16. Баранов С.И., Песчанский В.А., Синев В.Н. Одноуровневая реализация микропрограммных автоматов на ПЛМ. Изв. АН СССР . Сер. техническая кибернетика, 1983 -N 5. - С. 41-49.

17. Баранов С.И., Журавина Л.Н., Кожина В.Б., Левин И.С., Межин H.H., Песчанский В.А. Система автоматизации логического проектирования дискретных устройств. Автоматизация проектирования. - М.: Машиностроение, 1986. - Вып. 1-е. 32-45.

18. Шнейдер A.A., Кардаш С.Н. Алгоритм синтеза одноярусных комбинационных схем из ПЛМ // АВТ. 1987. - N 5. - С. 62-67.

19. Шнейдер A.A., Кардаш С.Н. Использование дизъюнктивных разложений при реализации булевых функций в базисе ПЛМ // УСиМ. -1991.-^5.-С. 14-21.

20. Дудкин А.А.Синтез комбинационных схем из ПЛМ в САПР СБИС // Проблемы построения САПР СБИС. Минск: ИЖ АН БССР, 1990. -С. 117-123.

21. Палагин A.B., Баркалов A.A., Юсифов С.И., С'тародубов К.Е., Швец А.Г. Реализация микропрограммных автоматов на ПЛИС // УСиМ. -1991. N 8. - с. 18-22.

22. Булатова И.Р., Друзина МП., Галковский A.B., Скурыдин И.Д., Соловьев В.В. Метод синтеза одноуровневых схем устройств логического управления на ПЛМ и ПЗУ. Ред. ж. Изв. АН БССР. Сер.физ.-тех.н. Минск, 1989. - 27 с. - ДЕП. в ВИНИТИ от 06.12.89. N7246-B89.

23. Бутов A.A. Использование программируемых логически матриц при синтезе комбинационных схем // Автоматизация логического проектирования дискретных устройств. Минск: ИТК АН БССР, 1980. - Вып. 2-С. 72-73.

24. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

25. Бабушкин В.И., Васькин П.И. Реализациа систем булевых функций на программируемых логических матрицах // Известия вузов. Приборостроение, 1981. N 6. - С. 42- 45.

26. Новиков C.B. Теория регулярных структур. Мн.: Университетское, 1987.-208 с.

27. Бибило П.Н., Гольдберг Е.И., Каркоцкая И.П., Чигирь Н.П. Система логического проектирования дискретных устройств на программируемых матричных БИС. Минск: Ин-т техн. кибернетики АН БССР, 1987.-82 с.

28. Антонов Ю.А., Бибило П.Н., Гольдберг Е.И., Каркоцкая И.П., Чигирь Н.П. Система логического проектирования цифровых устройств на программируемых матричных БИС // Микропроцессорные средства и системы. -1989. N 3. - С. 22-24.

29. Бякин Б.Н., Дьяченко Ю.Г. Реализация цифровых автоматов схемой из базовых ПЛМ. Моск. инж.-физ. ин-т. М., 1984, 34 с. ДЕП N1553-85 от 28.12.85.

30. Бибило П.Н. Анализ и классификация декомпозиционных методов синтеза комбинационных схем на ПЛМ и ПЗУ // АВТ. 1990. - N 1. -С. 95.-ДЕПN5431-В89.

31. Бибило П.Н. Синтез комбинационных ПЛМ-структур для СБИС. -Мн.: Навука i тэхнша, 1992. 232 с.

32. Holland J.H. Adaptation in natural and Artificial Systems. A Bradford Book The MIT Press Cambridge, Massachusetts London England, 1994. -21 lp.

33. Goldberg D.E. Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley Publishing Company, Inc., 1989. - 412p.

34. Soldek J., Yanushkevich S. Genetic Algorithms in Logic Design// Proceedings of the International Conference on Computer-Aided Design of Discrete Dcviccs (CAD'95), v2, Minsk-Szeczcin, 1995. P. 17-25.

35. Агибалов Г.П., Беляев В.А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Томск, ун-та, 1981. 125 с.

36. Агибалов Г.П., Беляев В.А. Метод сокращенного обхода дерева поиска и его применение в синтезе интегральных схем/7 Управляющие системы и машины. 1977. - №6. = С. 99-103.

37. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. -М.: Наука, 1969. 368 с.

38. Рейнгольд, Нивергелът Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

39. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

40. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977. 383 с.

41. Агибалов Г.П. Дискретные автоматы на полурешетках. Томск: Йзд-во Томск, ун-та, 1993. - 227 с.46.3акревский А.Д. Комбинаторика логического проектирования // АВТ. 1990. - N 2. - С. 68-79.

42. Крисгофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.

43. Берри Р., Микина В. Язык Си: введение для программистов. М.: Финансы и статистика, 1988. -191 с.

44. Андреева Л.Н., Оранов A.M. О сложности некоторых задач разбиения// Известия РАН. Теория и системы управления. 1997. -№2.-С. 114-116.

45. Андреева Л.Н., Оранов A.M. Оценки погрешности двух приближенных алгоритмов разбиения// Известия РАН. Теория1 и системы управления. 1999. - №1. - С. 89-93.