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

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ ( ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ )

На правах рукописи

СИДОРОВ МИХАИЛ ПЕТРОВИЧ

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

Специальность 05.13. 05 - Элементы устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

МОСКВА 1994

Работа выполнена на кафедре Вычислительной техники Московского энергетического института (Технического университета).

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

Потемкин И. С.

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

профессор Ильин а Н.

- кандидат технических наук, доцент Голдобин 0. Я

Ведущее предприятие - научно - исследовательский институт

"Кулон".

Защита состоится "/( " 1994 г. в /6 час.

&0 мин. в аудитории Г-310 на заседании специализированного Совета К-053.16.09 в Московском энергетическом институте.

С диссертацией можно ознакомиться в научно-технической библиотеке МЭИ.

Отзыры на автореферат в двух экземплярах, заверенные печа тью. просим направлять по адресу: 105835, ГСП, Москва. Е-250, ул. Красноказарменная, 14, Ученый Совет МЭИ.

Автореферат разослан " ^ " ОЁ/^^Л 1994 г.

Ученый секретарь

специализированного Совета

К 053.16.09. Л

к. т. н. . доцент (Сычев Ю- а

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

Актуальность работы. Приборы (микросхемы) программируемой матричной логики (ПМЛ) являются одним из видов программируемых логических интегральных схем (ПЛИС). Сочетая в себе широкие возможности настройки на реализацию различных логических функций, высокое быстродействие и весьма невысокую стоимость, эти микросхемы находят широкое применение в качестве базового элемента при проектировании цифровых устройств (ЦУ). Приборы ПМЛ применяются при синтезе ЦУ, выпускающихся небольшими тиражами, где применение заказных БИС и базовых матричных кристаллов (БМК) не выгодно, а применение микропроцессорных наборов в силу многотактного принципа работы не обеспечивает необходимое быстродействие. "Экологической нишей" приборов ПМЛ являются сравнительно небольшие ЦУ типа контроллеров, схем перекодировки, интерфейсных схем, имеющих значительную комбинационную часть.

Широкое использование ПМЛ в качестве базового элемента привело к созданию ряда методов проектирования ЦУ на их основе.

Значительный вклад в развитие методологических основ проектирования ЦУ на программируемых матричных микросхемах внесли отечественные ученые А. Д. Закренекий, С. И. Баранов, С. В. Новиков В. А. Скляров.

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

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

При использовании традиционных методов синтеза сети приборов ПМЛ необходимым этапом является представление комбинационной части устройства в виде единой системы функций алгебры логики (ФАЛ) и дальнейшей ее декомпозиции на подсистемы. В соответствии же с принятой практикой проектирования ЦУ представляется сначала в виде структурной или функциональной схемы, состоящей из ряда блоков. Такое представление несет в себе сведения о направленности и числе связей между блоками в явном виде. Кроме того, такое представление наглядно и понятно разработчику.

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

Целью диссертационной работы является исследование и разработка методики синтеза ЦУ в базе приборов ПЫЛ малой и средней мощности ориентированное на снижение вычислительной сложности задачи синтеза при "хорошем" качестве решения.

Достижение указанной цели предполагает решение следующих задач.

1: Анализ существующих методов синтеза ЦУ на приборах ГШ; анализ математических моделей устройств, используемых в этих ме тодах.

2. Разработка математических моделей объектов.проектирования для решения задачи синтеза на приборах ПМЛ цифровых устройств, представленных структурной схемой.

3. Разработка методов локализации области поиска решения в задаче разбиения схемы ЦУ на фрагменты, покрываемые одним прибором ПМЛ из заданного набора.

4. Разработка методики направленного перебора в задаче реализации ЦУ на приборе НМЛ.

5. Разработка на базе предлагаемых процедур локализации и направленного перебора процедуры синтеза ЦУ в базисе приборов ШЛ малой и средней мощности.

6. Программная реализация разработанных процедур и алгоритмов.

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

Научная новизна состоит в следующем^

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

2. Разработана методика синтеза ЦУ на приборах ПМЛ, ориентированная на сокращение перебора вариантов решения в задаче разбиения схемы ЦУ на фрагменты, покрываемые одним прибором ПЖ Методика использует группу методов сокращения перебора, причем на каждом этапе применяется метод наиболее "дешевый" с точки зрения вычислительной сложности:

- поиск сильносвязанных областей в структуре цифрового устройства;

- метод распространения модифицированной волны;

- метод направленного многовариантного последовательного вложения ( под термином "вложение" понимается реализация частей схемы ЦУ на внутренних структурах (макроячейках и бт^нх врода/вывода) приборов ПМЛ ).

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

4. Предложено в задаче синтеза ЦУ на наборе ПМЛ использовать методы решения неточных переборных задач, применяемые при разработке программ для игры в шахматы.

Практическая ценность и рекомендации по применению. Разработанная методика может служить основой для создания надстройки над программой-редактором. Ориентация на снижение вычислительной сложности задачи привело к тому, что программные средства, созданные на основе разработанной методики, могут быть реализованы на персональной ЭВМ небольшой мощности типа IBM РС/ХГ/АТ аа разумное время.

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

Реализация и внедрение результатов. Предложенная методика синтеза на ПШ1 цифровых устройств внедрена в СКВ "Топаз" г. Москвы, где использовалась при проектировании на приборах ПМЛ схем перекодирования и контроллеров нестандартных устройств. Акт, подтверждающий внедрение, приведен в приложении.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на XIX международной конференции "Информационные средства и технологии" (г.Москва, 1993г.)

Публикации. По теме диссертации опубликованы 2 печатные работы.

Структура и объем Диссертации. Диссертация состоит из введения. четырех глав, заключения, списка литературы ( 65 наименований) и приложения, содержит 4 таблицы, 32 рисунка Основной материал изложен на 130 страницах машинописного текста.

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

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

В первой главе определяются область использования приборов ПМЛ малой и средней мощности.

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

Анализируется применяемая в традиционных методах математическая модель комбинационной части устройства, реализуемая на ГШ, основой которой является система функций алгебры логики РкСХ). где

X - множество входных аргументов, от которых зависят функции системы Рк,

к - число функций в системе.

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

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

В рассматриваемой главе проводится анализ традиционных методов проектирования устройств на приборах ПМЛ. Существующие методы можно разделить на три класса:

- основанные на стандартной декомпозиции Шеннона;

- использующие дизъюнктивно-конъюнктивное разложение;

- комбинационные методы.

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

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

Во второй главе представлены графовые математические модели объектов проектирования - структурной схемы ЦУ; блоков структурной схемы; прибора ПМЛ; фрагмента схемы ЦУ, реализуемого на одном приборе ПМЛ. Кроме того, в данной главе приведена процедура поиска сильносвязанных областей как первый этап локализации области поиска решения в задаче синтеза.

В рассматриваемой главе обосновано применение двухуровневой ММ структурной схемы ЦУ для решения задачи синтеза на приборах ПМЛ.

Первым уровнем является ориентированный гиперграф (ультраграф) НРУ(ХУ,Ш), где ХУ - множество вершин, отображает множество блоков схемы ЦУ; ОУ - множество ориентированных ребер, отображает множество связей между блоками и множество входных и выходных сигналов ЦУ.

Показано, что схему ЦУ целесообразно разделить на комбинационную часть (реализуемую комбинационными блоками) и регистровую часть, состоящую из блоков-регистров. Тогда множество вершин Х-ХТ и ХЬ, где ХГ - подмножество вершин, отражающих блоки-регистры, а ХЬ - подмножество вершин, отражающих комбинационные блоки.

Ультраграф однозначно задается троичной матрицей инциденций гачу - I |гуи11:

г 1, если П1 исходит из х1.

гуи - (• 0, если т входит в х1,

-, если Ш не является инцидентным XI

Для отражения внутренней структуры и функций, реализуемых в блоках структурной схемы ЦУ, служит второй уровень ММ. Для вершин х1 < ХЬ на этом уровне описывается система логических функ ций, реализуемых в отображаемом блоке. Эта система представлена в виде двух матриц - двоичной В и троичной Т.

Показано, что математическую модель части схемы ЦУ, синтезируемого на одном приборе ПМЛ, целесообразно иметь в трех различных видах: подграфа Э; вершины У на уровне ее внутреннего представления как композицию систем ФАЛ, входящих в подграф блоков; подграфа М(А,ТГт), где

А - множество вершин, отображающих макроячейки используемого прибора ПЖ

игп - множество ребер, отображающих множество обратных связей, и множество входов и выходов прибора ПМЛ.

Подграф М(А,1!т) вводится для удобства решения подзадач в задаче синтеза на приборах ПМЛ, а также с учетом необходимости иметь в процессе решения в интерактивном режиме наглядную для разработчика математическую модель.

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

1. Подграфы НРЦХР^.иРО - сильносвязанные области, для' которых мощность множества вершин превышает величину (|ХРН>(5).

2. Подграфы Н1^1(ХИ,иИ) - сильносвязанные области с малой мощностью множества вершин: |ХР1|<6".

3. Псевдоизолированные вершины, не вошедшие в сильносвязанные области, обрисующие множество ХМ.

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

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

- алгоритм поиска начальной вершины;

- процедура распространения модифицированной волны в ультраграфе;

- процедура последовательного вложения;

- процедура дополнения неполных приборов ПМЛ и формирования конечных подграфов из "остатков".

В основу предлагаемой методики легла идея последователь-

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

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

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

Задача синтеза на графовом уровне сводится к построению гомоморфного отображения ультраграфа НУ(Х,Ш в ультраграф НЗ(ХЗ,1£) (см. рис. 1)

НБОСЗ.®) -УНУ(Х.и) такое, что |ХБ| - вш кз, 1-1- • • 1

1 - число вариантов отображений,

^ - число приборов ПМЛ, необходимых для ;)-го отображения, 1ХЗ1 - мощность множества ХЗ.

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

ХЗ множество вершин, являющихся образами 61 ультраграфа НУ(Х,1ЙЛэти подграфы 61 являются математическими моделями части схемы ЦУ, синтезируемой на одном приборе.

Ц§ - множество.ребер, связывающих подграфы Оно отражает связи между приборами набора ПМЛ в синтезируемом варианте устройства.

шшцзц, 6У рь

улыпрагренр ЦУ/Х,0)

ш иг

«36

тэ

рис. I. Гомоморфное отображение ультраграфа НУ(Х,Ч) в

ультраграф Н2(Х5,Й).

Подграфы НР1(ХР1,ЦР1) полученные в результате поиска сильносвязанных областей являются основными зонами для реализации на Них процедуры последовательного вложения. Сильносвязанные области характеризуются минимальным числом внешних связей и максимальным внутренних. Поэтому такая область предпочтительнее для вложения в один прибор ПМЛ.

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

В главе показано, что на графовой математической модели схемы ЦУ для дальнейшей локализации областей поиска решения (до фрагмента, покрываемого одним прибором ШЛ) в задаче синтеза возможно применение модифицированных методов, применяемых для решения задач в конструкторском проектировании (задачи покрытия, компоновки). Одним из таких методов является распространение волны в ультраграфе. Модификация этого метода применяется в качестве второго этапа локализации области поиска решения для определения подграфа, ограниченного внешними характеристиками прибора ПМЛ - числом входов и выходов.

Метод заключается в построении подграфа - окрестности 0(хнв) от какой-то заранее определенной точки (начальной вершины хнв) путем включения в подграф на каждом шаге к всех вершин XI, смежных с уже построенной окрестностью 0к(хнв). Эти вершины XI £ ХЗМк входят во фронт волны Фк(хнв).

В качестве хнв предлагается выбирать вершину-регистр хТ, имеющую максимальное чиоло ребер, являющихся выходными ребрами подграфа НРХ(ХР,ЦР), на котором строится окрестность .

Выходным ребром подграфа считается ребро инцидентное

хотя бы одной вершине, лежащей в подграфе, и одной вне его, и являющееся исходящим и;)- ребром для вершины XI < ХР.

Предлагается при распространении волны в очередной фронт включать не все, а лишь "перспективные" вершины с точки зрения задачи синтеза. Вводится понятие ширины волны <г, которое определяет число вершин включаемых в текущий фронт волны. Задавая параметра пользователь может влиять на быстродействие конечной синтезируемой схемы ЦУ так как "ширина" разрезания в некоторой степени определяет число каскадов в сети ПМЛ.

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

Важное значение'имеют "тупиковые" вершины, т;е. вершины хТ, у которых множество ребер ТГхт является подмножеством внешних ребер подграфа окрестности 0к( хн. в). Под внешним ребром подграфа здесь понимается ребро, одновременно инцидентное хотя бы одной вершине, лежащей в подграфе, так и вершине вне его. Множество внешних ребер подграфа включает в себя подмножество выходных ребер определенное выше.

Для характеристики вершин - кандидатов на включение в текущий фронт вводятся оценки - коэффициенты связанности |0kxi| aki - -,

Ukxi - множество ребер, инцидентных вершине xi и вершинам, принадлежащим построенной окрестности Ок(хнв); lUzxi|

az - -.

PC xi)

Uzxi - множество ребер,' инцидентных вершине xi и вершинам, принадлежащим зонам предпочтительного распространения волны, включенным в окрестность. p(xi) -локальная степень вершины xi

Bzxi - значимость зоны, характеризует ситуацию: входит ли вершина xi в зону предпочтительного распространения волны.

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

На этом этапе графовый уровень математической модели дает направление перебора, а окончательное решение формируется на

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

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

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

После очередного шага производится оценка текущей ситуации (сравнение значений числа входов 1,числа заполненных макроячеек ш и числа термов в макроячейках чз с параметрами прибора I, М, а). I- число независимых входов, М- число макроячеек, д- число термов в макроячейке.

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

Целевой функцией Кц в оценке текущей ситуации служит величина. характеризующая степень заполненности прибора. Кц - а1»1н + а2»шн, 1 ш

1Н--. шн--- нормированные величины,

I М

а1 + а2 - 1;

а1 и а2 - коэффициенты значимости соответствующих параметров 1 и ш. задаются пользователем из анализа схемы ЦУ и необходимых требований к проекту.

р:'с. 2. Бяотс-схпм-1 методики синтеза цнфропого устройства на приборах ГГ.1Л.

Кц < 1. При Кц > 1 она теряет смысл, т. к. в этом случае параметры варианта выйдут за пределы ресурсов прибора

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

шах КЩ 1-1... к, где

к- число подграфов GNt на данной окрестности Ое(хнв).

В данной главе представлена процедура дополнения неполных приборов ГМЛ. основанная на известном "пожарном" алгоритме решения задачи упаковки в контейнеры. Показано, что исходными дополнениями для этой процедуры являются подграфы HLj(XLj.ULj). псевдоизолированные вершины хт, и остатки от сильносвязанных областей - подграфы OPYk(XDk.UOk).

В конце главы представлена доведенная до алгоритма методика последовательного синтеза схемы ЦУ на приборах ПМЛ (см. рис.2).

Четвертая глава посвящена экспериментальному исследованию задачи вложения сильносвязанной части схемы ЦУ в приборы ПМЛ. Здесь представлено описание комплекса программ вложения, информационное обеспечение, входные и выходные данные. Дается краткое описание основных процедур комплекса, их архитектуры и алгоритмов, лежащих в их основе. Приведен пример схемы ЦУ, на котором демонстрируется работа процедур комплекса.

Показана эффективность разработанных процедур и алгоритмов локализации области поиска решения и направления перебора, благодаря чему соеданнь»'программы могут быть реализованы на ПЭВМ малой мощности (IBM PC/XT) и получать "хорошее" решение за приемлемое время.

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

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

В приложении приводятся характеристики приборов ПМЛ средней мощности серии ЕР, дан акт, отражающий внедрение результатов работы.

ЗАКЛЮЧЕНИЕ

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

2. Показано, что задача разбиения схемы ЦУ на фрагменты, покрываемые одним прибором ПМЛ, для строго оптимального решения является "труднор^п'^мой". Исходя из этого, актуальным является разработка методики синтеза, использующей эвристические правила и способы снижения вычислительной сложности задачи.

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

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

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

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

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

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

9. Обоснована необходимость использования интерактивных методов при решении подзадач синтеза ЦУ на приборах ПМЛ .

10. Разработана и доведена до алгоритма методика для автоматизированного синте&а ПУ, основанная на последовательном многовариантном вложэнии, с учетом снижения вычислительной сложнос-

ти задачи.

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

Основное содержание диссертации отражено в следующих публикациях.

1). Потемкин И. С., Сидоров. М. П. Математическая модель реализации цифровых устройств на наборе ПМЛ. // Информационные средства и технологии: Тезисы докладов XIX международной конференции.-М.. 1993.-С. 62-63.

2). Сидоров к. П. Подход к синтезу цифровых электронных устройств на наборе приборов матричной логики как графовая задача -М. ,1993.-7с.-Деп. в Информэлектро 13.10. 93. ЫХ 47ЭТ93.

Типография МЭИ, Красноказарменная, 13.