Введение к работе
Актуальность работы. Приборы (микросхемы) программируемой матричной логики (ПМЛ) являются одним из видов программируемых логических интегральных схем (ПЛИС). Сочетая в себе широкие возможности настройки на реализацию различных логических функций, высокое быстродействие и весьма невысокую стоимость, эти микросхемы находят широкое применение в качестве базового элемента при проектировании цифровых устройств (ЦУ). Приборы ПМЛ применяются при синтезе ЦУ, выпускающихся небольшими тиражами, где применение заказных БИС и базовых матричных кристаллов (БМК) не выгодно, а применение микропроцессорных наборов в силу многотактного принципа работы не обеспечивает необходимое быстродействие. "Экологической нишей" приборов ПМЛ являются сравнительно небольшие ЦУ типа контроллеров, схем перекодировки, интерфейсных схем, имеющих значительную комбинационную часть.
Широкое использование ПМЛ в качестве базового элемента привело к созданию ряда методов проектирования ЦУ на их основе.
Значительный вклад в развитие методологических основ проектирования ЦУ на программируемых матричных микросхемах внесли отечественные ученые А. Д. Закревский, СИ. Баранов, С. В. Новиков, В. А. Скляров.
Традиционно математической основой методов проектирования устройств на ПМЛ является преобразование логических функций в базисе дизъюнктивной нормальной формы (ДНФ). Синтез ЦУ, размеры которого (число входов, выходов, реализуемых термов в комбинационной части устройства, триггеров регистровой части ) не превышают ресурсов одного прибора ПМЛ, выбранного для реализации, является тривиальной задачей, эффективные методы решения которой хорошо разработаны. В том гке случае, когда ресурсы прибора ПМЛ меньше, чем объем проектируемого ЦУ, возникает необходимость решения задачи наилучшего разбиения всей схемы цифрового устройства на фрагменты, покрываемые одним прибором ПМЛ из набора, выбранного для реализации ( называемая еще .задачей о синтезе сети приборов ПМЛ ). Это сложная многокритериальная задача. Для строго оптимального ее решения требуется поліцій перебор всех вариантов, что обуславливает невозможность получения такс-
го решения за разумное время. Вычислительная сложность задачи синтеза сети приборов ІШЛ привела к отказу от гарантии получения строго оптимального решения. Поэтому все существующие методы проектирования ЦУ на приборах ПМЛ основаны на различных эвристических приемах, позволяющих сделать поиск близкой к оптимальной реализации ЦУ на базисе приборов ПШ2 более направленным.
При использовании традиционных методов синтеза сети прибот ров ПМЛ необходимым этапом является представление комбинационной части устройства в виде единой системы функций алгебры логики (ФАЛ) и дальнейшей ее декомпозиции на подсистемы. В соответствии же с принятой практикой проектирования ЦУ представляется сначала в виде структурной или функциональной схемы, состоящей из ряда блоков. Такое представление несет в себе сведения о направленности и числе связей между блоками в явном виде. Кроме то-го, такое представление наглядно и понятно разработчику.
В связи с этим становится актуальной задача разработки методики , основанной на альтернативных подходах , позволяющих использовать структурные особенности схемы ЦУ и облегчающей эффективное участие эксперта-разработчика непосредственно в процессе синтеза в интерактивном режиме. Необходимым условием для разрабатываемой методики должно служить усиленное внимание к снижению вычислительной сложности поставленной задачи.
Целью диссертационной работы является исследование и разработка методики синтеза ЦУ в базе приборов ПЫЛ малой и средней мощности ориентированное на снижение вычислительной сложности задачи синтеза при "хорошем" качестве решения.
Достижение указанной цели предполагает решение следующих задач.
1: Анализ существующих методов синтеза ЦУ на приборах ГіЮі; анализ математических моделей устройств, используемых в этих ме тодах.
-
Разработка математических моделей объектов.проектирования для решения задачи синтеза на приборах ПМЛ цифровых устройств, представленных структурной схемой.
-
Разработка методов локализации области поиска решения в задаче разбиения схемы ЦУ на фрагменты, покрываемые одним прибором ПМЛ из заданного набора.
-
Разработка методики направленного перебора в задаче реализации ЦУ на приборе НМЛ.
-
Разработка на базе предлагаемых процедур локализации и направленного перебора процедуры синтеза ЦУ в базисе приборов ПМЛ малой и средней мощности.
-
Программная реализация разработанных процедур и алгоритмов.
Методы исследования. При проведении исследований в настоящей работе использовался аппарат алгебры логики, теории графов, теории множеств, теории матриц и теории структурного программирования.
Научная новизна состоит в следующем^
-
Предложена двухуровневая математическая модель, не использовавшаяся ранее при проектировании цифровых устройств на приборах ПМЛ, - ориентированный гиперграф (ультраграф).
-
Разработана методика синтеза ЦУ на приборах ПМЛ, ориентированная на сокращение перебора вариантов решения в задаче разбиения схемы ЦУ на фрагменты, покрываемые одним прибором ПМЛ. Методика использует группу методов сокращения перебора, причем на каждом этапе применяется метод наиболее "дешевый" с точки зрения вычислительной сложности:
поиск сильносвязанных областей в структуре цифрового устройства;
метод распространения модифицированной волны;
метод направленного многовариантного последовательного вложения ( под термином "вложение" понимается реализация частей схемы ЦУ на внутренних структурах (макроячейках и гіяпичк врода/вьшода) приборов ПМЛ ).
-
При решении задачи синтеза в основу предложено положить принцип гомоморфного отображения графов. Это позволяет использовать опыт, накопленный при решении задач на графах. К таким задачам относится ряд задач, решаемых на этапе конструкторского проектирования.
-
Предложено в задаче синтеза ЦУ на наборе ПМЛ использовать методы решения неточных переборных задач, применяемые при разработке? программ для игры в шахматы.
Практическая ценность и рекомендации по применению. Разработанная методика может служить основой для создания надстройки над программой-редактором. Ориентация на снижение вычислительной сложности задачи привело к тому, что программные средства, созданные на основе разработанной методики, могут быть реализованы на персональной ЭШ небольшой мощности типа IBM PC/XT/AT за разумное время.
Разработанный комплекс программ синтеза на языке Pascal 5.5 не является законченным коммерческим продуктом, однако может служить ядром для пакета синтеза на наборе ПМЛ малой и средней мощности. Кроме того, будучи дополнен интеллектуальным пользовательским интерфейсом, комплекс программ синтеза может быть реко мендован для использования в учебном процессе для проведения лабораторных и курсовых работ по проектированию цифровых устройств.
Реализация и внедрение результатов. Предложенная методика синтеза на ПМЛ цифровых устройств внедрена в СКВ "Топаз" г. Москвы, где использовалась при проектировании на приборах ПШ схем перекодирования и контроллеров нестандартных устройств. Акт, подтверждающий внедрение, приведен в приложении.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на XIX международной конференции "Информационные средства и технологии" (г.Москва, 1993г.)
Публикации. По теме диссертации опубликованы 2 печатные работы.
Структура и объем диссертации, диссертация состоит из введения, четырех глав, заключения, списка литературы ( 65 наименований) и приложения, содержит 4 таблицы, 32 рисунка Основной материал изложен на 130 страницах машинописного текста.
