Введение к работе
Актуальность проблемы. Программируемые матрицы вентилей (ПМВ), программируемые логические матрицы (ПЛМ), программируемые постоянные запоминающие устройства (ПЛЗУ), или просто (ПЗУ) являются разновидностями программируемых (пользователем) логических интегральных схем (ПЛИС) или, другими словами, программируемых логических устройств (ПЛУ) - Programmable Logic Devices (PLD), и находят широкое применение в качестве элементной базы современных устройств логического управления (УЛУ), в том числе простейших из них - комбинационных схем. Минимальные по числу элементов одноярусные комбинационные схемы в базисах ПМВ, ПЗУ, ПЛМ представляют особый интерес в силу их низкой стоимости, малых габаритов, веса, потребляемой мощности и высокого быстродействия. Различают два типа одноярусных комбинационных схем в базисах ПМВ, ПЗУ, ПЛМ: 1) схемы, не допускающие объединения выходоп своих элементов по схеме ИЛИ и 2) схемы, допускающие объединение выходов своих элементов по схеме ИЛИ посредством проводной дизъюнкции или отдельных элементов ИЛИ. Заметим, однако, что в случае использования отдельных элементов ИЛИ схемы второго типа можно считать одноярусными лишь условно. Синтез (построение) одноярусной схемы любого из этих типов обычно осуществляется исходя из системы булевых функций, заданных в дизъюнктивной нормальной форме (ДНФ). Синтезированная (построенная) :хема должна реализовать заданную систему булевых функций (ДНФ). Существующие методы и алгоритмы синтеза одноярусных комбинационных :хем в базисах ПМВ, ПЗУ, ПЛМ в большинстве своем являются весьма тстными и приближенными, т.е. ориентированы на решение довольно узких слассов задач с использованием в синтезе элементов только одного типа либо ПМВ, либо ПЗУ, либо ПЛМ) и не гарантируют минимум числа іатрачнваемьіх базисных элементов. Вот почему разработка и исследование иігоритмов синтеза минимальных одноярусных комбинационных схем в >азисах ПМВ, ПЗУ, ПЛМ, рассчитанных на решение более широких классов
задач, в том числе, с использованием различных базисных элементов представляется актуальной проблемой.
Цель работы - 1. Сформулировать абстрактную математическую задачу, как модель широкого класса задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ. 2. Разработать точный алгоритм решения сформулированной абстрактной задачи. 3. Исследовать теоретически и экспериментально свойства сформулированной абстрактной задачи и разработанного алгоритма ее решения и, тем самым, возможность их использования в синтезе минимальных одноярусных комбинационных схем реальной сложности. 4. Указать способы сведения задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ к сформулированной абстрактной задаче.
Методы исследования. Для достижения поставленной цели используются средства и методы дискретной математики (теории множеств, булевой алгебры, математической логики, комбинаторного анализа, теории синтеза управляющих систем), теории реляционных баз данных, теории NP-полноты и языка программирования Си.
Научная новизна. Впервые сформулированы три задачи синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ, обобщающих соответствующие известные задачи. Для этих трех задач сформулирована абстрактная комбинаторная оптимизационная задача кратчайшего допустимого разбиения набора объектов, представляющая собой их единую математическую модель. Проанализированы возможные методы решения сформулированной задачи разбиения набора объектов такие, как метод полного перебора, методы 0-1 программирования, метод ветвей и границ и метод сокращенного обхода дерева поиска (авторы: Агибалов Г.П., Беляев В.А.), называемый далее для краткости Г-методом. Выбран Г-метод и осуществлена его оригинальная алгоритмизация применительно к сформулированной задаче разбиения набора объектов. Полученный таким образом оригинальный алгоритм кратчайшего допустимого разбиения набора объектов запрограммирован на языке Си. Свойства сформулированной задачи кратчайшего допустимого разбиения набора объектов и разработанного алгоритма ее решения
исследованы как теоретически (с применением теории jW-полноты), так и экспериментально (на ЭВМ) - установлена сильная W-трудность задачи кратчайшего допустимого разбиения набора объектов и, следовательно, экспоненциальная сложность предложенного алгоритма ее решения, выделены два полиномиальных частных случая задачи разбиения набора объектов, проведены испытания алгоритма кратчайшего допустимого разбиения на потоке из нескольких десятков задач различной сложности, сделаны выводы и даны рекомендации о возможностях его практического использования. Указаны способы сведения трех сформулированных задач синтеза к задаче кратчайшего допустимого разбиения набора объектов. Кроме того, получены оценки погрешности двух приближенных алгоритмов разбиения набора объектов, используемых в Г-методе для построения начального разбиения.
Обоснованность полученных в диссертации результатов состоит в том, что все они базируются на теоремах и утверждениях доказываемых с использованием аппарата дискретной математики (теории множеств, булевой алгебры, математической логики, комбинаторного анализа, теории синтеза управляющих систем), теории реляционных баз данных, теории ЛТ'-полноты, при этом некоторые из них еще и подтверждены экспериментально.
Практическая ценность. Предложенный алгоритм кратчайшего допустимого разбиения набора объектов и реализующая его программа на языке Си могут быть использованы в системах автоматизированного проектирования (САПР) УЛУ для автоматического решения трех сформулированных в диссертации задач синтеза минимальных одноярусных комбинационных схем в различных базисах ПМВ, ПЗУ, ПЛМ сведением их к задаче кратчайшего допустимого разбиения набора объектов указанными в работе способами.
Реализация полученных результатов. Работа выполнена при финансовой поддержке РФФИ (грант 95-01-00705) и ее результаты отражены в соответствующих отчетах. Кроме того, они реализованы в составе экспериментальной распределенной САПР, в которой задача кратчайшего допустимого разбиения набора объектов решается на удаленном компьютере высокой производительности, а сведение той или
иной задачи синтеза к задаче разбиения набора объектов и преобразование полученного от удаленного компьютера кратчайшего допустимого разбиения набора объектов в схему осуществляется на местном компьютере меньшей производительности. Результаты испытаний в составе этой САПР программы кратчайшего допустимого разбиения набора объектов показали ее пригодность для решения задач синтеза реальной сложности.
Апробация работы. Результаты диссертации по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского государственного университета (ТГУ) и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, в период с 1990 по 1997 гг. они докладывались на всесоюзных или международных конференциях в г.г. Москве и Минске, что подтверждается соответствующими публикациями тезисов докладов и доклада, указанных в конце автореферата. Прохождение отчетности по линии РФФИ и НИР и частичное использование результатов диссертации в учебном процессе при подготовке студентов соответствующих специальностей в ТГУ также можно считать апробацией диссертационной работы.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, приложения и списка цитированной литературы. Объем диссертации составляет страниц SJ текста, набранного в Word 6.0 (Шрифт - Times New Roman Суг, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе, титульный лист - 1 с, оглавление - 2 с, основной текст, включающий 4 рис. и 4 таблицы, - 68 с, библиография из 57 наименований - 6 с.