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

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

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

Р Г Б О-; ' 1 5 ДЕК'й>э

ПОПОВ Дмитрий Иванович

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

05.13.12- Системы автоматизации проектирования .

Автореферат диссертации на соискание учёной степени кандидата технических наук

Таганрог -1996

Работа выполнена в Таганрогском Государственном радиотехнич«

университете, г- Таганрог.

Академик Международной академии информатизации, Академик академии наук и искусств (США), доктор технических наук, профессор, Ю.М.Вишняков

ОФИЦИАЛЬНЫЕ ОППОЦЕНТЫ - Заслуженный деятель науки

РФ Академик академии проблем качества РФ, доктор технических наук, . профессор Ю.О.Чернышев

кандидат технических цаук, профессор К-К.Лебедев

Ц ХУЧНЫЙ РУКОВОДИТЕЛЬ - •

ИДУЩАЯ ОРГАНИЗАЦИЯ -

Таганрогский научно-исследовательский щетитугрвязи •

Защита состоится

[т£т. в/^

_ на заседании

ииализировашкл о совета Д(Й>3.13.02по зайдете диссертаций при Таган дам Государственном радиотехническом университете по адресу: 347945, f. Таганрог, пер. Некрасовский, 44, ауд*Д-406

С диссертацией можно ознакомиться в библиотеке Таганрогского Г дарственного радиотех|Н1ческогр университета.

Автореферат разослан "ocb " 199 Ь г.

Ученый секретарь специализированного совета кандидат технических наук, доцент

А.Н. Целью

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

Актуальность проблемы. Разработка программных средств, и методов (ысокоуровневого синтеза цифровых сйстем представляет одну из важней-иих проблем при построении современных САПР цифровых.устройств.. Се- , одня основной тенденцией развития САПР СБИС является постепенное гипо«/йтд[тг»1 ^пйплтп гтлрьтгшлоашкг ио Клттрр пигпктш Так,

[едавно автоматизированное проектирование позволяло решать задачи рассировки и размещения, то теперь назрела необходимость в автоматиза-(ии проектирования цифровых систем исходй из поведенческого описания фоекта СБИС. В этом смысле возможна аналогия с развитием языков про-раммирования высокого уровня. На ранних Этапах развития систем про-раммирования приходилось составлять программы в машинных кодах, озже появились первые ассемблеры, за ними алгоритмические языки, а те-ерь уже существуют системы визуального программирования. При этом опросы преобразования исходных программ в машинные коды полностью ереложены на компьютер. Так же и в области проектирования СБИС повег енческое описание является первоначальным по отношению ко всем другим гапам проектирования, а задача дальнейшей обработки и преобразования роекта цифровой системы, получения конечного представления кристалла БИС может быть решена с использованием соответствующих автоматизи-ованных систем. Разработка таких систем автоматизированного проекти-ования представляет больйюй интерес и позволит значительно Уменьшить ремя проектирования СБИС. -

Поскольку теоретические вопросы сопровождения проекта СБИС при * груктурном и логическом проектировании достаточно хорошо изучены и хледованы, то задача обработки поведенческого описания может быть ¡.едена к задаче преобразования такого представления в структурное и ло-1ческое. Эта задача носит название высокоуровневого синтеза, в настоящее >емя она является актуальной и не до конца проработанной.

С другой стороны, нельзя полностью исключать разработчика из пропса проектирования. Должна существовать возможность его воздействия I любом из этапов проектирования, потому что интуиция и опыт разработка значительно влияют на качество получаемых результатов. Следова-льно, возникает необходимость в некоторых средствах взаимодействия жду автоматизированной системой и пользойателем. Поэтому любая ком-[ексная САПР как сложная система должна иметь языковую природу ин->рмационных связей между отдельными подсистемами, объектами юектирования и коллективами разработчиков и пользователей САПР. :о обуславливает необходимость разработки* таких языковых лнгвистических) средств и принципов проектирования САПР СБИС, ЧТО

также является актуальным. Лингвистические средства должны позволять разработчику представить объект проектирования ш любом из. уромкй, в также иметь возможность осуществлять взаимодейстык рюяМШЯ уромий между собой. ;

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

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

Для достижения этой цели поставлены следующие задачи-.

1. Исспедовать способы описания цифровых систем на различных этапах проектирования.

2. Разработать методы построения структурного представления цифрот вой системы на основании алгоритмического описания функционирования цифрового устройства.

3. Исследовать способы представления микропрограммных автоматов (МПА) и разработать обобщенную модель МПА, язык описания цифровых устройств в этой модели и методы структурного синтеза на основании обобщенной модели ,МПА.

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

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

Практическая значимость работы. Поставленная цель достигнута разработкой подсистем автоматизированного проектирования, позволяющих значительно ускорить процесс разработки цифровых систем. Программные подсистемы проектирования МПА, конечных автоматов, минимизации булевых функций; структурного проектирования и синтеза структурного представления цифровой системы на основании поведенческой спецификации могут быт*, интегрированы в единую САПР СБИС. Разработана структура такой САПР и технология сопровождения проекта СБИС на всех: уровнях проектирования. Кроме этого, разработаны основные принципы лйнгвистн-ческого взаимодействия таких подсистем с другими известными САПР. Б качестве Исходного представления цифровых систем в пред лагаемых подсистемах автоматизированного проектирования используются специально

вработанные языки описания проектов на различных уровнях, но это не :ключает возможности использования подмножества языка УЬШЬ для про-ггирования СБИС. В качестве САПР самого ниэкнего уровня для решения дач верификации и моделирования, а также трассировки и размещения ис-эльзуется известная система РСАЭ, которая, при необходимости, может ыть заменена на любую другую популярную САПР. С помощью разрабо-шных подсистс:.: можно проектировать цифровые системы различной южности.

Научная новизна работы состоит в следующем:

1) разработан метод поблочного синтеза структурного представления ифровой системы на основании поведенческого описания;

2) разработано представление и введено , понятие обобщенного микро-рограммного автомата (МПА) для синтеза цифровых систем, а также пред-эжены методы его приведения к стандартным МПА;

3) разработаны оригинальные лингвистические средства и принципы ^провождения проекта СБИС, начиная с уровня поведенческого описания.

Внедрение результатов работы.

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

Отдельные родсистемы переданы для использовния в ОКБ Миус"(г.Таганрог) и НИИ МВС(г/Гага1фог). •

Разработанные программные подсистемы и материалы диссертацион-ых исследований используются в учебном процессе на кафедре МОП ЭВМ аганрогского государственного радиотехнического университета в курсе абораторных работ и лекций по дисциплине "Системы автоматиздрован-ого проектирования". г ,

Подсистемы структурного проектирования были использованы при роектировании и моделировании БИС "Нечепсого процессора", разрабо-анного на кафедре МОП ЭВМ в рамках научно-технических программ Университеты России" и "Технология и материалы микроэлектроники".

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

I. Метол поблочного синтеза структурного представления цифровой си ЗЬмы. заданной:» виде поведенческого описания алгоритма ее работы. " 2. Метол структурного синтеза цифровых систем, представленных в ви расширенны* микропрограммных автоматов.

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

4. Алгоритмы и программные модули для автоматизации решения зада1 сквозного проектирования цифровых систем.

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

Апробация результатов работы. Основные результаты диссертацион чоА работы неоднократно докладывались и обсуждались на научных семи «арах и конфераиадЙЕ !П>ТУ. НИИ МВС и в других организациях, в ton щеле на следующих научны* конференциях:

• Всесоюзная иэл^о-Техничахкаи конференция "Применение кодов Фи ■Зоначи в системах обработки и отображения информации" (г.Винница 1990г.):

• Международная научно-техннчгская конференция "Актуальные про блемы фундаментальных наук" (р.Москаа, 1991г.);

• Научно-техническая конференция посвященная дню Радио (г.Ростов 1992г.);

• Региональная конференция студентов, аспирантов и молодых специа листов Северного Кавказа (г. Таганрог, 1993г.);

• II, III Всероссийские научные конференции студентов и аспиранту (Г.Таганрог. 1994. 1996 гг.):

• XXXVIII, XXXIX, ХХХХ научно-технические конференции профес сорско-преподавательского состава ТРТУ (г.Таганрог, 1993-1995 гг.);

• Цсероссийскаи научно-техническая конференция с международные^ .! .:аием,; Компьютерные технологии в инженерной и*управленческой дея v г; «юсти" (г.Таганрог, 1996). " ■ '

ИуОликцшш, По. материалам диссертации опубликовано 14 печатные работ, материалы диссертации использовались в трех р/'-.описных. отчета; по НИР ГКВШ, получен сертификат из Государственного фонда алгоритме« и программ.

Структура " объем работы. Диссертация состоит из введения, четыре? глав с выводами заключения, списка литературы и приложений. Работа из ложена на 172 страницах машинописного текста и содержит 42 рисунка Список литературы « оставляет 121 наименование.

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

Во введении обосновывается актуальность темы диссертационной рабо-ы. формулируются цели и задачи исследования, приводится краткий обзор 1Ш ературы по методам проектирования цифровых систем.

» - ... _____________-%г________________тг____

а первой ¿¡шве на иьниишши 1-дпа1раммм 1 амъьи! исгематизированы основные задачи проектирования, исследована техно-югия разработки цифровых систем, предложена структура автоматизиро-¡анной системы поддержки сквозного проектирования СБИС.

В основу представления У-диаграммы Гайского-Кана положен следую-ций принцип: любая цифровая электронная система может быть представ-гена в рамках трех различных моделей или областей - поведенческой, :труктурной и физической (геометрической). В пределах каждой области (лементы цифровой системы могут быть представлены на различных уров-1ях абстракции. Уровни обозначаются точками на осях У-диаграммы (рис.

и

Поведенческая . ^____ ^ 1 / Структурная

область \ • ^^ ' 1 / *, область

р Устройств!, процессоры, память

Функциональная спецификяцняЧР&^к ^^,,

. ЛД ^^ 5а Модули, подсистемы •

АлгоритмвО!^ зь

И ^ Регистры, АЛУ, мультиплексоры

Регистровые передячн^^™ ^

Булевы функции, конечные автоматы

Дифференциальные уравнения

5Ь1 Вентили, триггеры Транзисторы, контакты

Физическая (геометрическая) область

Прямоугольные/многоугольные группы, маски

Стандартные ячейки, топология Макроячейки, плайы кристалла . Укрупненные планы модулей м блоков Кристалл, интегральная схема, печатная плата

Рис. 1. ¥-диаграмма Гайского-Кана и отображение этапов синтеза и оптимизации: 1 - системный синтез; 2 - высокоуровневый синтез; 3 - синтез и оптимизацц! на уровне регис1ровых передач; 4 - отображение на технологический базис; 5 - логический синтез и оптимизация

Показывается, что основные задачи проектирования СБИС: "синтез", 'анализ", "оптимизация", "детализация", "абстрактизация", "генерация" и 'извлечение структуры" могут быть отображены на У-диаграмме, как пересоды с одной оси на другую или продвижение по одной из осей. Так. под :интезом понимается переход от поведенческой области в структурную, под шализом - переход в обратном направлении. Переход от структурного П :тавления к физическому (геометрическому) будем называть генерацией, с5-

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

Далее в главе исследуются задачи синтеза и оптимизации, которые пред ставлены на рисунке 1, приводится анализ существующих систем автомат? зированного проектирования СБИС и эти средства также отображаются г У-диаграмму. В конце главы разрабатывается концепция и структура интс грированной системы автоматизации высокоуровневого синтеза цифровых устройств (рис.2). -

Рис. 2. Структура н состав интегрированной системы автоматизации высокоуровневого синтеза цифровых устройств.

• Начальное описание цифровой системы может быть представлено на языке поведенческого описания. С помощью методов высокоуровневого синтеза, рассматриваемых в главе 4, это описание разбивается на три части: микропрограммный автомат, абстрактный автомат и потоки перемещения данных. Каждая из указанных частей может служить самостоятельным входом для пользователя при разработке цифровых систем. В этом случае интерфейсом между пользователем и системой будут- служить соответствующие языки описания. На рисунке 2 возможны^ точки входа и управления проектированием пользователем показаны прямоугольником о стрелкой в точку входа.

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

-------—----------------------- —---- -----------------Ола nti/> n I ■ ППОТТ/*1У1Т1_

UllHCtlníí?l MCI ЛЗШЛС ¡rt/intipUUDlA JL^ww л u .vuu^jíiim.in .ж

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

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

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

S|l:10)

R|l:10

S|3:7|

10_5Ф ií )*"~°В2 iK-o

V Т Т/ |R|1:51 Т/ [

:

S[l:5¡

Register R[I:¡0], Sil: 10], V¡5:1¡; Bit Vector B1.B2; dock Г;

{BIA1) R<=S;

{B2&Ti k¡l:S]<=S¡3;7], V<=S¡1:S);

Рис. 3. Пример описания межрегистровых передач.

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

микропрограммным автоматом будем понимать МПА, содержащий ря вершин с дополнительными возможностями и различным предназначение« К числу таких вершин отк;сем вершины логической проверки условий, вь полнсния булевых операций н вызова-вспомогательного МПА. Каждая д< полнительчая ьершина может быть представлена совокупность] стандартных вершин МПЛ, что показывается во второй главе. Введение л ких вершин позволяет уменьшить общий объем вершин в МПА и знач! тельно облегчит разработку сложных цифровых устройств. Приведе следующий пример. Пусть у разрабатываемого цифрового устройси имеется две трехразрядные входные величины А и Б. Тогда вершина лоп ческой проверки А >В будет выглядеть, как показано на рисунке 4(а), а < реализация с помощью стандартных вершин и вершины- булевой операци "исключающее ИЛИ" приведена на рисунке 4(6). Заметим лишь, что верни на булевой операции "исключающее ИЛИ" сама является обобщенной, п< этому реальная схема МПА будет еще больше за счет замелы трех так» вершин, встречающихся на рис.4(б), на совокупность стандартных.

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

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

Пусть Z = {(й0а,а2...ая.|) | а, e{0,l}]- множество двоичных л-разрядных наборов. На Z задана некоторая БФ/следующим образом: О, г eR0;

/(/■) = • 1, reR,; -, reS,

где Rq, R¡ и S - непересекающиеся подмножества Z. На множестве двоичных наборов S функция не определена.

Для представления БФ в виде ДНФ используется алфавит булевых переменных Х- .

Введем некоторые базисные определения. Под разметкой М'г будем по-, нимать некоторый способ размегки r-разрядов набора (а^а^-.а,^) eZ, здесь г - будем называть рангом разметки, а индекс i представляет номер разметки ранга г, причем i = 1,2,3,... С[- сочетание из г элементов по п . Cobo- г купность всех разметок назовем разметочным-множеством Л/. Очевидно, «тто |М\~2". Например, для трехмерного куба Z множество М имеет вид: М = [М„. М\. M?. М]. М\. М]. М\. Л/,'| , или обозначая через символ "плюс" (Ч')

отмеченные разряды, а символом '-' неотмеченные разряды, получим следующее множество: '

М = {е, + - -, - + -, - - +, + + + -+,- + +,+ + + },

гдее - М0- соогветствует пустой разметке.

Каждой разметке М\ можно поставить в соответствие совокупность элементарных конъюнкций или, пользуясь Геометрической интерпретацией, множество интервалов/,(А/,') ранга г п-мерного куба Z. Так разметке М\ соответствует множество интервалов:

/3(М{)= {^(MIX^ÍA/JX/KM]),/^^)} = {í0x„í0xI,x()x1,Vl}.

Опираясь на изложепаые понятия, сформулируем процедуру поиска максимальных допустимых интервалов:

1. Положить L~0, - количество найденных максимальных допустимых интервалов.

,2. Повюрить для рангов г = 1,2,....п пункты 3,4,5,6.

3. Сформировать множество разметок ранга г:

.. мг = {м;|« = 1,2,... с}.

4. Для каждой разметки M'r, i=I, 2,...,С сформировать множество интервалов 1Г(Ю= {'/(Ю\У = 1Д. -2'}. "

5. Проверить на исглниость систему условий:

[/:(м:)пя,*0; (1)

При выполнении системы (1) в список максимальных интервалов включается 1'г{М'г)= Г,, которому ^ответствует элементарная конъюнкция К1 и увеличивается количество найденных интервалов Ь: Ь=1+1.

6. Проверить условие асинхронного останова процесса минимизации

[)ТПЯ, = Л,. (2)

При выполнении условия (2) закончить минимизацию с Сок.ДНФ

и|=0

Опишем дальнейшие преобразования по поиску совместного минимального представления систем БФ.

Пусть /•= {/2......]],} - система булевых функций, каждая из которых

представлена в виде СДНФ после этапа ассоциативной минимизации. /={//,/>, ..., /„} - множество минимальных интервалов каждой функции, причем, /, = /(/,)={*;,*;,...,*;'} и /до=*;.

, [0,4 йА Тогда Г'тН

Введем функцию минимизации ()=()(I), которая является критерием для оптимизации представления СБФ. В качестве такой функции зачастую выбирают количество переменных (символов), входящих в множество /. В общем случае, оценка ыожет быть любой.

Пусть ^ = = ' количество всех элементарных конъюнкций, а

Я(к) - это ранг интервала к.

Положим А,В*0 - непустые множество интервалов, а - интервал.

[А,айЛ

Определим оператор замещения Ощ(А,а,В) = \

[А\<\)В,аеА

Сформируем следующее множество минимальных интервалов:

■ >1

Далее осуществляем операции по поиску

(Уа4 еА)(^с А)и (5)

(V/;'(a,) * 0)/, = Chg(lt,at,p)j = u

Операции (3), (4) повторяются для всех элементов множества А, пока оно не перестанет изменятся.

Для автоматизации задач логического и структурного синтеза разработан языка структурного описания схем (ЯСТОС). Во второй главе обосновывается необходимость разработки такого языка и приводятся синтаксические диаграммы ЯСТОС, а также технология проектирования цифровых схем с использованием ЯСТОС. Очевидно, что язык позволит значительно ускорить ввод структурного представления для последующей обработки проекта СБИС. Кроме того, ЯСТОС является средством взаимодействия различных подсистем интегрированной системы автоматизации высокоуровневого синтеза (рис.1.). Примеры структурного описания на языке ЯСТОС и соответствующие им цифровые схемы приведены на рис. 5.

Следует отметить, что ЯСТОС позволяет описывать иерархические схемы, в которых одни сложные элементы являются частью других. Для эле^ ментов самого нижнего уровня иерархии существует так называемая библиотека примитивов.'позже в эту библиотеку могут быть включены и другие элементы более высокого уровня иерархии для последующего их использования в различных проектах СБИС.

В четвертой главе описан метод поблочного синтеза структурного представления цифровой системы на основании алгоритмического (поведенческого) описания. Под алгоритмическим описанием будем понимать описание модели работы БИС на основании шести стандартных конструкций:

1. Множество {Xi,X2,... Xk} операций, и операторов по преобразованию данных;

2. Последовательность действий. BEGIN А; В; END.

3. Условие с двумя вариантами действий

IF <условие> THEN A ELSE В\

4. Условие с одним вариантом действий •

IF <условие> THEN А;

5. Цикл с предусловием

WHILE <условие> DO Л;

6. Цикл с постусловием

REPEAT A UNTIL <условие> ;

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

можно ввести еще ряд-дополнительных, например выбор варианта, безусловный переход и т.п. '

Нетрудно, видеть, что описанные конструкции являются универсальными и имеют аналоги в любом алгоритмическом языке программирования высокого уровня. С этой точки зрения можно говорить об универсальности алгоритмического представления БИС на основании стандартных конструкций.

=0=

SYMBOL DTtIG; l.\rLT D.C; OUTPUT QtSQ; LOCAL LI.LiLl.U: С

BEGIN

LI*NANDfC,D): L2=NANP(Lt,Ct; L3*NAND{L2,L4): p U=NAND<U,LI); Q*NOT<L3); NQ=N07(L4); E.\D;

On

w

L.3

NQ

SYMBOL МЗШП;«ГЕГИСТГ l.\PVTC,DO.Dl,DLD3;tHHJ>OPMAU ВХО.'Ш OVTrUTQO.QI.Q2,QS,nQO.NQI,H(HHQ<: BEGIN

(QO.HQil -DTKKUDCX):

IQI.NQI) 'DTKKIDI, CI; (Q2JVQ2J*DTKIGID2,CI; (Q3.HQ3) *DTRtG(Dl,Cj;

END;

6)

MODULE TEST; tNPlJT &,Fl,Fl,AQ,A t.Al.AJ; OUTPUT QC.QLQi QJ. LOCAL UJ.l,L2,U.NLHHLIJWL2,NlXf; . BEGIN

t*AND(FI,F2l;

<LO,Ll,L2,U,NU,NLl,NL2,NL3)*K31illll9(S,AO,AI.A2,A3); <Q0,ai,Q2.Q3l4!SSSKrtllF,Lt,LI,Uj(SJiLiMI^HNU); END.

ТОГ"

Tjn~

откю

С

D2

откю

DI

1»1«Ю

DO

OTRIC

-Q3 -NQ3

-Q2 -NQ2

_QI -NQI

-QO

-NQO

-QO . Ql - Ql ' 1'

Рис. 5. Описание на ЯСТ0С иерархического проект TEST: а - D-триггер; б - регистр; в - проект TEST. 5

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

Q

1

обходимо производить какие либо проверки "над входными данными. Управляющее состояние соответствует каждому блоку операций или операторов по преобразованию данных. В управляющем состоянии при построении структурной модели должен вырабатывания сигнал для инициализации необходимых действий. Анализ поведенческого описания разбивается на три части, анализ условий, выбор необходимых блоков операций в зависимости от результату» проверки условий и, наконец, соиствснко выполнение этих операций. Выделим эгп три части в структурные блоки и назовем их блок анализа условий (БДУ), блок управления (БУ) и блок операций (БО). При синтаксическом анализе условных операций в исходном алгоритмическом описании можно выделить два события: условие истинно и условие ложно. БУ анализирует событие и переходит в новое состояние, при необходимости выдавая управляющие сигналы для БО. Таким образом, информация об истинности условных операций является выходной для БАУ и входной для управляющего автомата БУ. Каждое условие в алгоритмическом описании можно представить двумя абстрактными буквами, несущими семантическую нагрузку истинности и ложности условия соответственно. Такие пары букв образуют выходной алфавит автомата БАУ и входной алфавит автомата БУ. Синтаксический анализ алгоритмического описания выделяет возможные связи между входными данными, участвующими в условных операциях. Эти связи по возможности оптимизируются. В качестве математической модели БАУ может выступать граф-схема алгоритма (ГСА) работы. Действительно, основными операциями БАУ являются операции проверки условия и выдачи управляющих сигналов. Этим же характеризуются цифровые устройства, разработанные на основе ГСА. Поэтому выбор ГСА как реализации алгоритма работы БАУ является не случайным. Элементный базис структурной реализации БАУ может состоять из набора компараторов, счетчиков, регистров и других комбинационных устройств. Математической моделью БУ может выступать абстрактный автомат. Взаимосвязь управляющего автомата БАУ на основе ГСА, абстрактного автомата БУ и комбинационного БО позволяет получить структурное представление цифровой системы на основании поведенческого (алгоритмического) описания. Возникает вопрос о необходимости согласования работы этих двух блоков. Возможны два режима взаимодействия БАУ и БУ: асинхронный и синхронный режимы.

Пусть А~{А1, Л2, ... ,Л„) - множество всевозможных условий в алгоритмическом описании, К',выходной алфавит ЗУ и

входной алфавит БУ, Вас = {В1. В2...., В„)»выходной алфавит БУ и входной для БО. Если И; в - функции, отображающие работу БАУ и БУ, то совмест-

ное функционирование БАУ и БУ в асинхронном режиме можно описать как систему:

К = С(У).

При синхронном режиме работы БАУ и БУ мощность множества вы* ходного алфавита БУ увеличивается на количество условий, содержащихся в алгоритмическом описании. С их помощью БУ как бы запрашивает проверку условия в определенный момент времени. Пусть Вг «{В^.В^

подмножество выходного алфавита БУ при синхронном режиме работы, являющееся одновременно подмножеством входного алфавита БАУ. Тогда выходной алфавит БУ В = В' 1)5«, |В1=|ВЯ(.|+1Вс1=ш+л, |ВС|=Ии совместное функционирование БАУ и БУ описывается так: У = ДЛВ');

•В = С(Г); В=ВЧ)ВЖ.

БО представляется графом прохождения данных. Вершины графа являются операциями, такими как присваивание, сложение и пр., а также переменными, участвующими в этих операциях. Операции предварительно пронумеровывают и ставят им в соответствие инициализирующие сигналы, используемые на этапе синтеза блока управления. Дуги указывают последовательность передачи данных. Следует отметить, что граф может быть несвязным или разбитым на отдельные подграфы. Вершины, соответствующие операциям, будем изображать квадратами. К каждой такой вершине для на-. глядности пририсуем дугу, взвешенную именем сигнала, инициализирующего эту операцию. Предварительно все сложные операции должны быть приведены к более простому виду. Для этого должна существовать своего 1 рода таблица макроподстановок, которая описывала бы каждую сложную операцию как последовательное выполнение элементарных операций. Под элементарной операцией будем понимать такую операцию, которую можно реализовать за один временной такт. К таким операциям можно отнести операции простого присваивания, когда данные из одного регистра передаются непосредственно во второй, простые арифметические и логические операции, используемые в правой части операций присваивания, в которых переменная, стоящая в левой части операции присваивания не совпадает ни с одной переменной, стоящей в правой части. Например, операцию х=х-у можно разбить на две, включив дополнительную переменную <; ¡¡=х-у;

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

могут выступать, например, сумматоры, счетчики и т.п. или просто линии передачи данных, открываемые по нужному сигналу, подведенному к соответствующей квадратной вершине.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. На основании Y-диаграммы Гайского-Кана исследованы и систематизированы основные этапы проектирования, задачи синтеза цифровых систем и проведен ан?лиз существующих средств автоматизированного проектирования. Показана необходимость разработки средств и истодов высокоуровневого синтеза, основанных на поведенческом описании проекта цифровых систем. .

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

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

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

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

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

6. Разработан метод поблочного синтеза структурного представления цифровой на основании поведенческого описания. Показаны способы разбиения поведенческого описания цифровой системы на три Стандартные час- • ти - абстрактный автомат, микропрограммный автомат и регистровые передачи данных и приведен пример разработки цифрового устройства методом поблочного синтеза. Универсальность метода поблочного'синтеза для различных языков поведенческого описания позволяет значительно расширить класс проектируемых устройств и область применения метода.

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

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

1 •

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Основное содержание диссертации опубликовано в 17 работах, в том числе: V

1. Будников Е.В., Горин A.C., Попов Д.И. Язык граф-схем в пользовательском интерфейсе интегрированной САПР PROJECT-CAD

//Материалы XXXIX научно-техн. конференции. Тезисы докладов.-Таганрог: ТРТУ, 1993.- С.100-10!.

?.. Вишняков Ю.М., Мелихов А Н., Попов Д.И., и др. Инструментальные средства поддержки процесса проектирования СБИС в САПР/ Отчет по НИР по проекту 83.108 (заключительный) - Таганрог. 1994.

3. Вишняков Ю М , Попов Д.И. Ассоциативная параллельная минимизация булевых функций //Материалы междунар. конф. "Актуальные проблемы фундаментальных наук". Тезисы док гадов т.2. Сек!щя высш.магем.- M : Издательство МГТУ, 1991. -С.^9-4!.

4. Вишняков Ю.М., Попов Д.И., Моргачев Р.В. АРМ разработчика помехоустойчивых цифровых устройств// Материалы всесоюзной научной конф. "Применение кодов Фибоначи в системах обработки и отображения информации".-Еиннкца: ВПИ, 1990.

5. Вишняков Ю.М., Селянккн В.В., Попов Д.И., Моргачев Р.В. Язык описания цифровых схем //Материалы областной НТК, посвященной дню Радир. Тезисы докладов.- Ростов-на-Дону, 1 °92. - С.42.

6. Вишняков Ю.М., Попов Д.И. Азтомазированный обучающий мо-д)ль. Ассоциативная минимизация булевых функций Per.номер ОФАП 143.7000.233 ГОСФАП 50910000328,1991

7. Попов Д.И. Возможности интеграции PROJECT CAD к общепринятым мировым стандартам САПР// Сборник научных трудов молодых ученых,- ТаганропТРТУ, 1995,- С.79-83.

S1. Попов Д.И. Классификация задач и технология проектирования СБИС// Материалы Ill-Всероссийской научн.конференции студентов и аспирантов "Тсхнич.кибернетика, радиоэлектроника и сист.управ."Тезисы док.-Таганрог:ТРТУ,1996,- С.99-100. Попов Д.И. Перспективы развития ИИС PROJECT-CAD// Материалы ХХХХ научно-техн. конференций- Тг.ганропТРТУ, 1995.- С.89-90. . '"

10. Попов Д.И. Функциональное АРМ разработчика помехоустойчивых дискретнцх устройств //Материалы IX региональной студенческой конференции. Тезисы док.-Таганрог:ТРТИ, 1990. - С.92-93,

И Попов Д.И., Моргачев Р.В., Евмеркин М.Н. Об РДЧРМ способе покрытия цифровой схемы библиотечными элементами ЕМК'/ Материалы XXXIX научно-техн. конференции. Тезисы докладов,-Та.анропТРТУ, 1993.-С. 101-102.

Соискатель

->

ОП ТРТУ. Зак. 50 5 Ткр. 6 О 199* г.