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

• Андреева, Людмила Николаевна
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Андреева, Людмила Николаевна

Введение.

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

Список литературы диссертационного исследования кандидат технических наук Андреева, Людмила Николаевна, 2000 год

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.