автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Алгоритмические методы и средства синтеза управляющих автоматов с хранимой логикой

ВВЕДЕНИЕ.

1. ОЦЕНКА. СЛОЖНОСТИ УПРАВЛЯЮЩИХ АВТОМАТОВ ДА/ И ВЫБОРА ТИПА УА ПРИМЕНИТЕЛЬНО К УСЛОВИЯМ ПРОЕКТА.•••••••

1.1. Понятие управляющего автомата . II

1.2. Сравнительная оценка способов организации МПА

1.3. Оценка стоимостных затрат на проектирование и производство УА.

1.4. Сравнительная характеристика типов структурной организации УА.

1.5. Методы оптимального выбора типа УА применительно к условиям проектной задачи.

1.6. Выгоды и рекомендации.

2. АНАЛИЗ МЕТОДОВ СИНТЕЗА УА С ХРАНИМОЙ ЛОГИКОЙ.

2.1. Характеристика задачи синтеза УА с хранимой /программируемой/ логикой.

2.2. Распределение микроопераций по полям

2.2.1. Табличные методы распределения микроопераций по полям.

2.2.2. Метод линейного программирования.

2.2.3. Метод ветвей и границ.

3. АЛГОРИТМУ РАСПРЕДЕЛЕНИЯ МИКРООПЕРАЦИЙ ПО

ПОЛЯМ.

3.1. Формальная постановка задачи.

3.2. Алгоритмы распределения микроопераций по полям по принципу временной совместимости

3.2.1. Описание алгоритма "включение-исключение".

3.2.2. Оценка вычислительных затрат на реализацию алгоритма "включение-исключение"

3.3. Алгоритм "вершинное покрытие"'.

3.3.1. Описание алгоритма

3.3.2. Оценка сложности.

3.4. Алгоритм "поиск независимых множеств"

3.4.1. Описание алгоритма.*.

3.4.2. Оценка вычислительных затрат алгоритма поиск независимых вершин"

3.5. Алгоритмы распределения микроопераций по полям по принципу смешанной совместимости.

3.5.1. Формализация задачи.

3.5.2. Описание алгоритма распределения микроопераций по полям по принципу смешанной совместимости . 92 4. ПОДСИСТЕМА АВТОМАТИЗИРОВАННОГО СИНТЕЗА

УПРАВЛЯЮЩИХ АВТОМАТОВ /ПСУА/.

4.1. Обобщенный алгоритм.

4.2. Структура ПСУА.

4.3. Препроцессор ПСУА.

4.3.1. Входной язык подсистемы препроцессора.

4.3.2. Контроль исходных данных.

4.3.3. Блок построения структурной таблицы.

4.3.4. Блок кодирования.

4.4. Блок распределения микроопераций по полям.

В числе важнейших направлений развития научных исследований в области естественных и технических наук, определенных в реше ниях ХХУ1 съезда КПСС, была поставлена задача "развития научных работ, направленных на совершенствование и эффективное применение в народном хозяйстве электронной вычислительной техники". Развитые и развивающиеся страны также прилагают значительные усилия для постоянной интенсификации работ по совершенствованию и внедрению средств вычислительной техники в различные сферы хозяйственной деятельности.Расширение области применения вычислительной техники (ВТ) в хозяйственной, управленческой и других сферах деятельности пред-. полагает увеличение выпуска средств ВТ, развитие производства но-. вых универсальных и управляющих ЭВМ и'комплексов, повышение эффективности и качества ЭВМ, разработку новейшей технологии их производства и уменьшение затрат времени на проектирование. Решению этих задач в значительной степени содействуют совершенствование теории проектирования и средства автоматизации проектных работ.Уровень автоматизации процесса проектирования определяется . состоянием теории проектирования, в частности уровнем формализации отдельных стадий и возможностью алгоритмизовать и довести до программной реализации процедуры решения проектных задач с учетом наиболее совершенной в настоящий момент времени или перспектив г ной технологии и способов производства объекта. Например, проек-. тирование управляющих автоматов базируется на достаточно разви той теории.автоматов.Однако, приложение этой теории к решению проектных задач в ряде случаев вызывает значительные трудности. Теория позволяет проводить эффективные преобразования и минимизацию абстрактных автоматных моделей обеспечивает формальные инженерные методизш структурного синтеза автоматов с жесткой логикой и методики анализа логических схем. Успехи, достигнутые в развитии двух последних разделов связаны с особенностями элементного базиса при технической реализации устройств на основе дискретных радиокомпо нент или интегральных схем с малой степенью интеграции.Особенности современной технологии производства электронных схем позволили существенно увеличить степень интеграции и обусловили экономическую эффективность производства аппаратуры и осо « бенно средств ВТ, на основе больших интегральных схем (БИС). Проектирование, изготовление и эксплуатация как самих БИС, так и аппаратуры на их основе, поставили перед проектировщиками ряд новых требований, связанных с необходимостью регуляризации структур, спецификой средств настройки, контроля и т.п. Эти требования в свою очередь предопределили выбор удовлетворяющих им классов схем цифровых автоматов и необходимость совершенствования соответствующих таким классам разделов теории и инженерных методик решения проектных задач. В частности, при выборе типа управляющего автомата в настоящее время предпочтение отдается автоматам с хранимой логикой. Методика структурного синтеза таких автоматов существенно отличается от достаточно отработанной методики структурного синтеза УА с жесткой логикой. Известные методы синтеза УА с зфанимой логикой характеризуются большим объемом вычислительных работ и, как будет показано в дальнейшем, относятся к задачам класса NP , что приводит к необходимости совершенствования как самих методов так и реализующих эти методы алгоритмов и определяет актуальность исследовательских работ в этом направлении, Цель работы. Целью диссертационной работы является исследование и разрас5отка алгоритмических методов синтеза УА с хранимой логикой с учетом совместной оптимизации затрат на 1гроектиро вание, производство и эксплуатацию средств ВТ. Совместная оптимизация затрат достигается с помощью совершенствования проектных: методик и средств автоматизации проектных работ с учетом свойств УА, адаптированных к условиям прогрессивной технологии и эксплуатационным требованиям. Выполненные в диссертации исследования относятся к оценке эффективности и сложности различных алгоритмов кодирования микроопераций при различных способах организации УА с хранимой логикой и разработке эффективных с точки зрения вычис^лительных затрат, алгоритмов распределения микроопераций по полям в соответствии с принципами временной, пространственной и смешанной совместимости. Для достижения поставленной цели в диссертации решаются следующие основные задачи.1. Исследование совреме1ШОго состояния проблемы проектирования УА с учетом технологических особенностей их производства и эксплуатационных характеристик.2. Формализация критерия и оценка экономической эффективности суммарных затрат на проектирование и производство различных типов УА.

3; Анализ и оценка сложности известных методов кодирования микроопераций для УА с хранимой логикой, 4. Разработка эффективных формальных процедур распре деле ния микрооперации по полям по принципу временной, пространст венной и смешанной совместимости.5. Разработка лингвистического и программного обеспечения системы автоматизированного проектирования /САПР/ УА, универ сальной по отношению к типу синтезируемого автомата, В процессе выполнения диссертационной работы использовался математический аппарат теории автоматов, теории множеств,' теории зтрафов и теории языков и грамматик. При разработке программного обеспечения СЖР был использован системный подход и основные положения структурного програглмирования.Научная новизна результатов диссертации» В диссертационной работе предложен обобщенный критерий экономической эффективности суммарных затрат на проектирование, производство и модификацию УА, на основе которого проведен анализ и выработаны рекомендации по перспективности структур УА. Выполнена оценка сложности известных методик кодирования микроопераций и доказана их принадлежность к задачам |\| Н класса, Предложены четыре варианта процедур распределения микроопераций по полям в соответствии с принципами временной, пространственной и смешанной совместимости. Единый методологический подход к фор мализации процедур определяется обобщенной постановкой задачи в терминах теории графов. Процедуры отличаются от известных способом организации перебора вариантов, что обеспечивает их быструю сходимость и, следовательно,^ сокращение вычислительных затрат при решении проектных задач. В работе также предложена и обоснована унифицированная структура САПР средств ВТ на тех стадиях проектных работ, которые выполняются по формальным методикам применительно к достаточно широкогду классу объектов и позволяют осуществлять настройку CAQP на решение конкретной задачи ее исходными данными, Практическая значимость работы. Значимость полученных результатов определяется возможностью использовать рекомендации и формализованную методику при выборе типа УА применительно к конкретным особенностям проектируемых средств ВТ. Разработанное лингвистическое, программное и информационное обеспечение САПР УА позволяет эффективно автоматизировать процесс проектирования УА как с жесткой так и с хранимой логикой. Универсальность СЖР по отношению к типу УА достигнута за счет того, что в состав процессора включены программные модули, реализующие совокупность процедур струтстурного синтеза УА с жесткой логикой, не являющихся предметом исследования в данной работе. Однако включение таких модулей в состав процессора СШР позволило провести оптимизацию структуры лингвистического, программного и информационного обеспечения САПР в целом, существенно расширив при этом ее возможности, Реализация научных результатов. Методика выбора типа УА оценки сложности методов синтеза и алгоритмы расцределения микроопераций по полям включены в состав соответствующих разделов курсов "Теория проектирования ЦВМ" и "Основы автоматизации проектирования ЦВМ" для студентов специальности"вычислительная техника" в Киев оком политехническом институте. Разработанная САПР УА использует ся как подсистема САПР средств ВТ, эксплуатируемой на кафедре вычислительной техники КПИ, Опытная эксплуатация подсистемы проводилась при выполнении работ по заказам промышленности по проектированию спецпроцессоров для предприятий ПО "Электронмаш" (г.Киев), "Аккорд" (г,Черкассы), при решении проектных задач на кафедре. Кроме того САПР УА включена в состав учебной САПР дан выполнения лабораторных работ,курсового и дипломного проектирования. САПР УА реализована на ЭВМ с системным интерфейсом "общая шина" в операционном окружении РАФОС-2. Основной язык программирования "Паскаль". Резидентная часть системы занимает около 12,5 кбайт оперативной памяти инструментальной ЭВМ, Апробация результатов и публикации. Основные положения работы докладывались на научных конференциях профессорско-преподава тельского состава Киевского политехнического института в 19831985 гг. и на республиканском семинаре ИК Ж 7ССР /г.Киев/ в 1985 г. на республиканской конференции "Моделирование и автоматизация процессов проектирования сложных технических систем" ( гор.Одесса ) 1984 г.По теме работы опубликована I статья и две рукописи депонированы в ЖРНИИ НТИ. Структура и объем работы. Диссертационная работа состоит из аннотации, введения, четырех глав и заключения,^ изложенных на стр. машинописного текста. Диссертация вктшчает 48 рисунков, 15 таблиц, список литературы содержащий 115 наименований, приложения на страницах.Во введении обосновывается выбор темы диссертационной работы, ее актуальность, формулируются направления исследований, В первой главе рассматриваются вопросы влияния свойств технологического и производственного характера на процесс формирования проектных решений при разработке 7А. Рассматривается обобщенный критерий экономических затрат на проектирование, производство и модификацию проектных решений,' приводятся рекомендации по выбору типа УА применительно к условиям проекта.Во второй главе формулируется задача синтеза УА с хранимой логикой, анализируются известные методы кодирования микроопераций, приводится асимптотическая оценка их сложности и намечаются пути усовершенствования процесса ее решения.В третьей главе излагается постановка задачи распределения ми1фоопераций по полям в соответствии с гфинципом временной,пространственной и смешанной совместимости. Постановка задачи формализуется в терминах теории зтрафов. На основе формальной модели описаны отличающиеся от известных процедуры распределения микро операций по полям и реализущие эти процедуры алгоритмы. Описание алгоритмов иллюстрируется одним и тем же примером исходных данных,' что позволяет оценить качество полученных результатов распределения, Для кадцого из описанных алгоритмов приводится оценка сложности, определшсщая объем вычислительных работ при проектировании УА заданной размерности, Четвертая глава посвящена описанию струютурной организации САПР УА,' ее лингвистического, программного и информационного обеспечения.В заключении формулируются основные результаты работы, Приложения содержат описание методики синтеза УА с жесткой логикой, используемой в САПР УА и не являющейся предметом исследований, а также листинги программных модулей и протоколы решения тестовых проектных задач.На защиту выносятся следующие основные положения диссертации.1. Методика, выводы и рекомендации, относящиеся к выбору типа УА црименительно к особенностям проектЕгруемых средств ВТ, 2. Оценка сложности известных методик синтеза УА с хранимой логикой.3. Алгоритм распределения микроопераций по полям дая различных способов организации памяти УА с храншлой логикой.4. Структурная организация САПР УА, лингвистическое, программное и информационное обеспечение компонент СШР, реализующих процедуры структурного синтеза УА с жесткой и хранимой логикой, II

ЗАКЛЮЧЕНИЕ

По результатам выполненной работы можно сделать следующие основные выводы.

1. Проведен анализ основных параметров различных типов УА применительно к особенностям современной технологии их производства на основе интегральных схем с высоким уровнем интеграции. Установлены относительные значения быстродействия системы ОА-УА, площади ИС, стоимости проектных работ и производства при различных способах организации УА. В качестве нормализующих величин использовались значения параметров для УА с жесткой логикой.

2. Предложены обобщенный критерий и методика для выбора типа УА с учетом характеристик проектируемых средств ВТ и предполагаемых технологических особенностей их производства.

3. Исследованы-известные методы синтеза УА с хранимой логикой. Установлено, что процедура распределения микроопераций по полям является наиболее трудоемкой стадией процесса синтеза и относится к классу задач с нормально-полиномиальной сложностью NPmiacc), т.е. характеризуется большим объемом вычислительных затрат при проектировании УА и нуждается в улучшении.

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

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

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

1. Материалы ХХУ1 съезда КПСС. - М.'.Политиздат, 1981, - 254 с.

2. Ананьевский С.А., Вузовский О.В., Самофалов К.Г., Шуваева В.Д. Автоматизация проектирования средств дискретной обработки информации. К.: УкрНИИНТИ, 1971. - 38 с.

3. Ахо А., Хлопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979,

4. Ачасова С.М., Бандман О.Л. Матричный метод синтеза комбинационных схем и логических преобразователей конечных автоматов. Изв. АН СССР. Техническая кибернетика, 1975, № 6, с. 991 - 994.

5. Айгнер М. Комбинаторная теория. М.: Мир, 1982. - 556 с.

6. Баранов С.И., Журавина Л.Н. Универсальная автоматизированная система синтеза МПА /УАССМА-ЕС/. Управляющие системы и машины, 1980, № 4, с. 85-86.

7. Баранов С.И. Синтез микропрограммных автоматов /граф-схемы и автоматы/. Л.: 2-е изд. - Л.: Энергия, Ленинградское отд.-ние, 1979. - 232 с.

8. Баранов С.И., Синев В.Н. Программируемые логические матрицы в цифровых системах. Зарубежная радиоэлектроника, 1979 , № I, с. 65 - 82.

9. Баранов С.И., Синев В.Н. Синтез автоматов на программируемых логических матрицах с памятью. Управляющие системы и машины, 1979, № 2, с. 58 64.

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

11. Баркаяов А.А. Микропрограммное устройство управления как композиции автоматов с программируемой и жесткой логикой.-Автоматика и вычислительная техника, 1980, № 4.

12. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.

13. Белчев А.К. Базовая система микроопераций и ее применение.-Кибернетика, 1972, № 2, с. 71-76.

14. Берж К. Теория графов и ее применение. Изд-во Иностранная литература, 1962.

15. Бузовский О.В., Мухаммед М.И. Распределение микроопераций по полям по принципу смешанной совместимости. К.: 1985,8 с. Рукопись деп. в УкрНИИНТИ, инв. J& 272-Д85.

16. Бузовский О.В., Мухаммед М.И. Алгоритмы распределения микроопераций по полям по принципу временной совместимости. -К.: 1985. 10 с. Рукопись деп. в УкрНИИНТИ инв. JS 271-Д85.

17. Гринис В.А., Канапяцкас П.Н., Карчяускас Э.К. Система автоматизации микропрограммирования. Технол. программирования микропроцессорной техники. - Таллин, 1975, с. 45 -SEL

18. Глушков В.М., Капитнова Ю.В., Летичевский А.А. Автоматизация проектирования электронных вычислительных машин. К.: Наук, думка, 1975. - 288 с.

19. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. - 476 с.

20. Глушков В.М. Теория автоматов и вопросы проектирования структуры цифровых машин. Кибернетика, 1963, № I,с. 3 II.

21. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

22. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. - 368 с.

23. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. - 247 с.

24. Дроздов Е.А. Оптимизация цифровых автоматов. М.: Сов.радио, 1975. 352 с.

25. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. -М.: Наука, 1970, cl 100 120.

26. Зелковиц М., Шоу А., Гэннон Дд, Принципы разработки программного обеспечения. М.: Мир, 1982. - 368 с.

27. Каган Б.М. Электронные вычислительные машины и системы. -М.: Энергия, 1979. 528 с.

28. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. 2-е изд. М.: Энергия, 1978. - 407 с.

29. Капитонова Ю.В., Алексеенко В.Г., Мищенко А.Г. Реализация устройства управления на основе больших стандартных схем. -Кибернетика, 1979, № 3, с. 29-35.

30. Кнут Д. Искусство программирования для ЭВМ. т. I. Основные алгоритмы. М.: Мир, 1976.

31. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. М.: Мир, 1977.

32. Коффрон Дд. Технические средства микропроцессорных систем: Практический курс. М.: Мир, 1983. - 344 с.

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

34. Майоров С.А., Новиков Г.И. Структура электронных вычисли/ .утельных машин. Л.: Машиностроение, 1979. - 384 с.

35. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. Л.: Машиностроение, 1974. - 432 с.

36. Мелихов А.Н. Ориентированные графы и конечные автоматы. -М.: Наука, 1971. 416 с.

37. Мищенко А.Т. Преобразование микропрограмм. Кибернетика,f1967, В 6, с. 7 13.

38. Мухаммед М.И. Препроцессор САПР управляющих автоматов. Вестник Киевского политехнического института, серия "Автоматика и электроприборостроение", вып. 22. К., 1985,с. 38 40.

39. Никитин А.С. Оптимизация операторных программ при совмещении операций и распределения памяти и модулей. Кибернетика, 1970, JS 4, с. 66 - 72.

40. Овсенян Г.Е., Оганян Г.А. Программируемые логические матрицы в электронных вычислительных машинах. Управляющие системы и машины, 1976, № I, с. 46 - 48.

41. Оре 0. Теория графов. 2-е изд., - М.: - Наука, 1980. -336 с.

42. Палагин А.В., Египко Е.М. Устройство вычерчивания графов для ЦВМ. Сборник "Опыт использования ЦВМ". - К.: Днепр, ИИТ, 1965.

43. Палагин А.В. и др. Мультипроцессорная система. А.С. 3688/24, решение от 26.06.1984 г.

44. Палагин А.В., Денисенко Е.М., Рокитский А.Г. Проектирование системы адресации МПУУ. Управляющие системы и машины,4, 1983.

45. Палагин А.В., Иванов В.А., Сыров В.В. Автоматная модель программируемых устройств управления ЭВМ. Препринт 78-32, - К.: ИК АН УССР, 1978.

46. Палагин А.В., Белицкий Р.И. К решению основной задачи эмуляции. Управляющие системы и машины, Js 3, 1980.

47. Петренко А.И. Основы автоматизации проектирования. К.: Техн1ка, 1982. - 295 с.

48. Петренко А.И., Семенков О.П. Основы построения систем автоматизированного проектирования. 2-е изд. - К.: Вшца школа, 1985. - 294 с.

49. Пийль Е.И. Размещение микропрограмм в управляющей памяти. Процессы и устройства управления в сетях связи. М.; 1982, с. 20 - 30.

50. Поттосин Ю.В. Методы минимизации числа состояний дискретного автомата. Автоматика и телемеханика, 1971, $ 8.

51. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. - 384 с.

52. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. - 455 с.

53. Сыров В.В. Алгоритм уменьшения объема двухуровневой микропрограммной памяти. Мини- и микро ЭВМ в АСУТП и науч. эксперим., - К, 1981, с. 55 - 61.

54. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. М.: Советское радио, 1974. - 200 с. .

55. Фридман А., Менон П. Теория и проектирование схем. М.: Мир, 1978. - 580 с.

56. Хассон С. Микропрограммное управление. М.: Мир, 1974.

57. Хоуп Г. Проектирование цифровых вычислительных устройств на интегральных схемах. М.: Мир, 1984.

58. Чу Я. Организация ЭВМ и микропрограммирование. М.: Мир, т. I., 1975, - 592 с.

59. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980. - 400 с.

60. Лазарев В.Г., Пийль Е.И., Турута Е.Н. Построение программируемых управляющих устройств. - М.: Энергоатомиздат, 1984. - 192 с.

61. Автоматизация проектирования ВС. Языки, моделирование и базы данных /Под ред. Брейер. М.: Мир, 1979.

62. Автоматизированное проектирование цифровых устройств/ Под ред. С.С. Бадулина. М.: Радио и связь, 1981. - 240 с.

63. Методы параллельного микропрограммирования / Под ред. О.Л. Бандман. Новосибирск: Наука, 1981.67,, ABDO Jr Rodriguez. Analyse de 1 -rarchitecture Interne du mlcroprocesseur MC 6809, Master's Report ENSIMAG, 1981.

64. Agerwala T. Microprogram optimization; A survey. IEEE Trans. Comput., 1976, C-25, No 10, p. 962 - 973.

65. Aho A. etr. The design and analysis of computer algorithms. -Reading:: Addison Wesley, 1974.

66. Auguln M., etr. An,algorithm for designing multiple boolean function;, application mo PLAS. Digit., process., 1978, v. 4, No 3 - 4, p. 215 - 230.

67. Baer J.L., Koyama B. On the minimization of the width of the control memory of microprogrammed Processors. IEEE Trans. Comput., 1979, С - 28, No 4, p. 310 - 316.

68. Biswas N.N. Introduction to logic and switching theory. -New York: Gordon and Breach, 1975.

69. Brown D.W. Synthesizer SMS. - ACM/IEEE 18 th Des. Autom. Cof. Proc., - Nashvillen: IEEE, 1981, p. 301 - 305.

70. Cragon H.G. The economics of programmable system components.- Proc. 13 th Annu. Workshop On Microprogramming (MICRO 13$- New York: IEEE, i980, p. 122 125.

71. Das S.R.j Banerji D.K., Chattopadhyay A. On control memory minimization in microprogrammed digital computer. IEEE Trans. Comput., 1973, С - 22, No 9, p. 845 - 848.

72. Dasgupta S. The organization of microprogram stores. -Comput. Surveys, 1979» vol. 11, No 1, p. 39 65.

73. Dervisoglu B.I, Sholl H.A. Theory and design of mixed-mode sequential machines. IEEE Trans. Comput., 1980, C - 29» No 7, p. 639 - 647.

74. Ditzlnger A., Belster J. Word reduction in microprogrammed controllers by state dependent processing of the inputs. -Microprocessing and Microprogramming, 1982, No 9, p. 161 -173.

75. Eastman C.M. Database facilities for engineering design. -Proc. IEEE, 1981, No 10, p. 1249 1263.

76. Guttag K.M. Compressing control ROM for VLSI microprogrammed microprocessors. MICRO-13» 1980. - New York: IEEE,p. 115 121.

77. Grasselli A., Montanari U. On the minimisation of read only memories in microprogrammed digital computers. IEEE Trans Comput., 1970, C - 19, No 11» p., 1111 - 1114.

78. Hansen; I., Lesczcylowski J. On fundamentals of computer aided design of firmware. MICRO-13, 1981, p. 3 - 12.

79. Hozjajenok J. The use of Petri net models and FPLAs in programmable hardwired system design. Microprocessors and Thier Appl. 5 th EUROMICRO Symp. - Amsterdam e.a., 1979,p. 259 269.

80. Hughes J.K., Michtom J.I. A structured approach to programming. Englewood Cliffs:. Print ice-Hall, 1977.

81. Hura G.S. A petri net approach to minimize ROM in microprogrammed digital computers. Comput. and Elect. Eng., 1981, vol 8, No 4, p. 245 - 248.

82. Martinez-Carballldo J.F., Powers M.V. General microprogram width reduction using generator sets. SIGMICR0 Newslett., 1981, vol 12, No 4, p. 144 - 153.

83. Mathialagan A., Biswas N.N. Bit steering of polyphase micro-commands. Int. J. Electronics, 1982, vol 53» No 1, p.63-66.

84. Mathlalagan A., Biswas N.N. Bit steering In the minimization of control memory in microprogrammed digital computers. -IEEE Trans. Comput.,. 1981, С 30, No 2, p. 144 - 147.

85. Montangero C. An approach to the optimal specification of read only memories in microprogrammed computers. IEEE Trans. Comput., 1974, С - 23, No 4,. p. 375 - 389.

86. M6800 Applications Manual. Phoenix: Motorola Semiconductor Products, 1975.

87. Obrebska M. Efficiency and performance comparison of different design methodologies for control parts of microprocessors. Microprocess. and Microprogramming, 1982, No 10, p. 163 - 178.

88. Papachristou C.A. A scheme for implementing microprogramadreccing with programmable logic arrays. Digit. Process, 1979, vol 5, No 3 - 4, p. 235 - 256.

89. Peuto B.L., Shustek. Current issue in the architecture of microprocessors. Computer, 1977, vol 10, No 2, p. 2o - 25.

90. Рос K.D. Heuristics for the global optimization of microprograms. SIG-MICRO Newslett., 1980, vol 11, No 3 - 4, p. 13-22.

91. Srimanl P.K., Slnha B.P. Some studies on microprogram optimization. Proc. 13 th Annu. Workshop on Microprogramming (MICRO-13). - New York: ACM, IEEE, 1980, p. 30 - 37.

92. Robertson E.L. Microcode bit optimisation is NP hard. -SIG-MICRO Newel.,. 1977, vol 8, No 2, p. 40 - 43.

93. Robertson E.L. Microcode bit optimization is NP Complete. - IEEE Trans. Comput., 1979, С - 28, No 4, p. 316 - 319.

94. Schwartz S.J. An algorithm for minimizing read only memo-rlez for machine control. Proc. 9 th Annu. Symp. Switching and Automata Theory, 1968, p. 28 - 33.

95. Wilkes M.V. The best way to design an automatic calculating machine. proc. Manchester Univ. Comput. Languge Conf., 1951, p. 16 - 18.

96. Yayasri Т., Basu D. An approach to organized microinstruction which minimizes the width of control store words. -IEEE Trans. Comput., 1976, С -25, No 5, p. 754 759.

97. Wilkes M.V. The growth of Interest in microprogramming, a literature survey. Comput. Surveys, 1969, vol 1, No 10, p. 139 - 145.