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

АКАДЕМИЯ НАУК УКРАИНЫ ИНСТИТУТ КИБЕРНЕТИКИ ИМЕНИ В. М. ГЛУШКОВЛ

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

Джугал Кришна ДАС

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

05.13.05 — элементы и устройства вычислительной техники и систем управления

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

КИЕВ 1993

Р-пЧ |

Работа выполнена на кафедре «Электронные вычислительные машины» Донецкого политехнического института.

Научный руководитель: кандидат технических наук, доцент Баркалов А. А.

Официальные оппоненты: доктор технических наук, профессор Рабинович 3. Л.,; кандидат технических наук Погорелый С. Д.

--В е д-у-щ-ал_о_р_г_а н и з а ц и я : КНИИРИА „ НПО имени

С. П. Королева". , ------

Защита состоится «.1.8...... 199 3 г. в П/ часов

на заседании специализированного совета Д 016.45.02 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу: 252207, Киев, проспект Академика Глушкова, 40.

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

Автореферат разослан «../1?...»............... 199^ г.

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

ГУМЕНЮК-СЫЧЕВСКИИ В. И.

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

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

Постоянно растущая сложность алгоритмов управления, прогресс в области полупроводниковой технологии, элементной базы средств вычислительной техники привели к созданию класса программируемых БИС с матричной структурой. Наиболее универсальна™ представителями класса программируемых БИС, широко применяемых в последние годы при реализации матричных схем микропрограммных автоматов (МПА), являются программируемые логические матрицы (1Ш1). Повышение требований к надежности, быстродействию, стоимости и срокам разработки МПА требуют создания эффективных машинно-ориентированных методов, позволяющих полностью автоматизировать процесс синтеза МПА. В этой связи разработка машинно-ориентированных методов синтеза логических схем ЫПА на программируемых БИС с матричной структурой является актуальной задачей теории и практики вычислительной техники.

Предметом исследования являются задачи структурного синтеза микропрограммных автоматов, функционирование которых описано на языке граф-схем алгоритмов (ГСА), на программируемых БИС с матричной структурой.

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

внедрение разработанных методов и программ в реальную

САПР.

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

Научная новизна работы состоит в следующем: предложена новая структурная схема автомата Ыили - Рй-автомат;

разработаны методы минимизации аппаратурных затрат при синтезе РЯ - автоматов;

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

Практическую ценность работы представляют: разработанные алгоритмы и программы синтеза Рй - автоматов на ГШ, оформленные в пакет прикладных'программ;

выработанные рекомендации по эффективному применению разработанных методов;

Реализация результатов работы: разработанные методы синте-

—за_РД._г автомата реализованы в виде подсистемы в комплексе

средств, автоматизированного синтеза-устройетв-управления_"Си-9СГ и внедрены в учебный процесс ДЛИ.

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на семинарах научного совета АН Украины по проблеме "Кибернетика" (1990, 1991 гг) и на всесоюзном научно-техническом семинаре "Системы автоматизированного проектирования радиоэлектроники" (Тверь, 1991 г).

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы 55 наименований, содержит 82 страницы машинописного текста, 45 рисунков и 30 таблиц.

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

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

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

вания устройства управления.

Математической моделью устройств управления является микропрограммный автомат, задаваемый пятеркой

< А , X , У, 5, Л >

где А- { а,, Дм } - множество внутренних

состояний;

Х-(ХЬ..., ХЛ - множество входных сигналов;

У= { Ц,,..., Цн} - множество выходных сигналов;

8'• А*Х —" А - функция переходов, реализующая отображение Пв £ А*Х —~ А ;

Д • А"Х — У - функция выходов, реализующая отображение

Д, я А*Х —" У (модель Мили) или Дя я А ~* У (модель Ыура).

Функция 5 служит для задания состояния перехода автомата по исходному состоянию а (Ы) и входному сигналу ХШ:

а(О-0(а(*-О, Х(О).' (I)

Функция Я служит для задания выходного сигнала автомата и (О по исходному состоянию и входному сигналу. Для автомата Мили эта функция имеет следующий вид

(*-*),Х(Ш. (2)

Простейшей структурой логической схемы МПА на ШИ является одноуровневая схема, для которой:

V СпН А* Х„ (Ь-Ш/ (3)

0

где Н - количество строк в прямой структурной таблице (ПСТ) МПА; С„ь - булева переменная, равная единице, если и только если в И - й строке ПСТ записан сигнал .

Проанализируем систему функции (3). (Невидно, ее коррект-

ность системе (2) определяется тем, что пара От, Х^ однозначно идентифицирует Ь - ю строку ПСТ. Пусть Й (ат, Хь ) множество пар (а,» соответствующих строкам ПСТ. Пусть существует взаимно однозначное соответствие между множе-

ствами Р (ат, ) и 0 — { 6, ,6Н }, такое, что ат, К), У 0С к бь • Тогда справедливо следующее утверждение:

Для реализации соответствия требуется дополнитель-

ный уровень в схеме автомата. При этом соответствие С(1 порождает схему автомата с I - й структурой. Практический смысл имеет нахождение соответствий (X! , для которых:

1) минимально число допдлнительных переменных, формируемых на выходах ПЛМ;

2) минимально число переменных, поступающих на входы ШЕЛ.

Зададим соответствие Л, между множеством /~(Дт,Х|,) и

-инохествои = (<С, , такое, что

<аи,Х„> ос* <ат,а8> —— В(атМ~аа.

При этом 6Ь - Кат> . тогда (2) и (3) преобразовываются следующим образ ал:

V СпЬ А^, (п«П7). (5)

Поскольку функция у. (^ ) зависит от состояний в момент времени i . к , ¡го структура автомата должна включать два

регистра памяти. Чтобы соответствие СХ, было взаимно одно-значньм, должно выполняться условие

|Р(аи,а,)| -|Р(ат,Х„)| .

Последнее возможно только при условии

прА =лд6; — прД лр4 в, а*} е {<„.., Н}). (б)

Если исходный автомат Мили не удовлетворяет (6), то необходимо произвести эквивалентное преобразование: парам встречающимся в ПСТ I раз, ставится в соответствие I пар

(а„га1) . При этом, в ПСТ необходимо рассмотреть переходы из всех состояний (¿ = I, I ) , что приводит к увеличению длины ПСТ.

Для минимизации длины ПСТ автомата в диссертационной работе разработаны методы, которые подробно рассмотрены в главе 2.

Во второй главе предложен ряд методов и алгоритмов, решающих в совокупности задачу структурного синтеза Ш1А Мили с РЯ -структурой.

Метод синтеза автомата основан на представлении И - й строки ПСТ конъюнкцией

где Ат и Аа - конъюнкции внутренних переменных, соответствующие кодам исходного состояния К(ат) и состояния перехода К (я3) автомата соответственно, записанным в /1-й строке ПСГ. В дальнейшем схему, реализация которой основана на вцэажении (7), будем называть РЯ - автоматом.

Схема

РЯ -автомата содержит две подсхемы: Р -и Я -подсхему и два регистра памяти Я В1 и /?/32 {рисунок) и функционирует следующим образом: в начале такта регистр Я В, содержит код К (ат) исходного состояния 1Я1А. Р - подсхема формирует функции возбуждения памяти , необходимые для перехода МПА в состояние а5*= 6 » задаваемое функцией перехода б . После этого подается сигнал синхронизации, по которому в

яв 1 записывается код состояния перехода,

а в регистр переписывается код К(ат) из регистра

/?0( • Я -подсхема формирует функции уп в У. , представленные СБФ (5).

Предложенный метод применим, если выражение (7) позволяет однозначно идентифицировать любую строку ПСТ. Таким образом, переменные (И" Г^Я ) должны быть ортогональными, что соответствует условию

V РгЪ = 0 а*/, ¿,¿£{1.....н}), (8)

Риоунок. Структура PR - автомата

.в противном случае будет нарушена функция выхода автомата.

Пусть Рт - подтаблица ПСТ, в которой перечислены все переходы из состояния ат 6 А , А (йт ) - множество состояний перехода для состояния Пт 6 А . Для выполнения (8) необходимо и достаточно, чтобы в любой подтаблице Рт не было одинаковых состояний перехода. При этом выполняется условие

| А(ат)| = Нт (т = /ТМ), О)

где Нт - количество строк подтаблицы Рт .

Для. выполнения (8) необходимо преобразовать исходную ПСТ таким образен, чтобы для любой подтаблицы Рт выполнялось условие (9) . Для достижения этой цели автором предлагается методика синтеза, основанная на эквивалентном преобразовании автомата и специальном кодировании состояний полученного автомата.

1. Проанализируем подтаблицы Рт исходной ПСТ. Если состояние Д8е А встречается в столбце состояний перехода подтаблицы Рт I раз (1> /) , то расщепим его на I состояний и поставим ему в соответствие множество Ва — { я{,..., Я» } После анализа всех подтаблиц каждому состоянию Я4 поставим в соответствие множество в,= о в т • Таким образом, состоя-

|п*| * _

0 I эквивалентных состояний. Ее..... М ) , , то В5=Ы

2. Сформулируем модифицированную таблицу переходов ША следующим образом. Анализируется столбец состояний перехода И - й строки исходной ПСТ. Если в нем записано состояние перехода С35 , то оно заменяется элементом множества Ва . Причем замена происходит таким образом, чтобы в подтаблице Рт не было одинаковых элементов множества В3

3. Закодируем состояния 25 £ 65 кодами ) разрядности Я, — М( , где М, • - мощность множества состояний В= $ В5 . При этом кодирование производится таким образом, чтобы дизъюнкция Д8= А5 V А3 V... V А5* , где

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

1,-2" (п = 0,1, ...) . (Ю)

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

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

В работе для устранения неоднозначности при идентификации строк предлагается ввести в структуру ЯД - автомата преобразователь кода'(ПК). РЯ - автомат с ПК называется РДС - автоматом. РЯС - автомат функционирует аналогично РЯ - автомату, но по сигналу синхронизации в регистр Язаписывается не код состояния перехода , а код множества В$ , которому при-надлежит~это~состояние.-------

При использовании ПК функция выхода имает вйд~СВ$• :--

С„ь А* А£5" (Ь-йН), ш)

где А^, - конъюнкция переменных Т; , соответствующая коду К (а, ) множества Вт , записанному в Ь -й строке преобразованной ПСТ.

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

~ Ащ А*Е„ (Ь-/777 ), (12) •

где Е/, - конъюнкция переменных 2$ 6 2 = { } , ко-

дирующих номер перехода из состояния йт в состояние О, . Для такого представления предлагается следующая методика:

1. Поставим в соответствие каждой паре весовую функцию К

ш » равную числу переходов с разными выходньми сигналами из ат в п4 .

2. Каждому переходу (йт, О») поставим в соответствие код перехода, десятичный эквивалент которого равен 0,1, ~ 1 . При этом переходам с одинаковыми выходными сигналами поставим

в соответствие одинаковые коды.

.3. Каждому коду перехода, для которого Кщ > 1 , поставим в соответствие двоичный код разрядности =

= 'тНоуг К .где п=тах(к{) И,} е 1/,..,', Н]),

Ь - номер строки ПСТ, соответствующей переходу. Если Кт , то К„ = 0.

4. Сформируем преобразованную ПСТ автомата Мили, в которую по сравнению с ПСТ введены столбцы Я/, , соответствующий коду перехода, и Е^ , содержащий переменные , принимающие единичное значение в коде /7-го перехода. Если /? - й строке соответствует пустой код, то примем по известному свойству конъюнкции пустого множества переменных 1 .

Во второй главе также разработан метод оптимизации РЯ -автомата при организации памяти на Т - триггерах. Метод основан на введении дополнительных вершин в граф автомата.

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

Избыточность реализации схем на заказных БИС объясняется тем, что переходы из каждого состояния МПА ат определяются множеством логических условий Х(от ) , мощность которого значительно меньше мощности множества X . Для минимизации площади используется метод кодирования логических условий, при котором множество X заменяется множеством Р = { Р,,..., Ра} , причем & Ь .

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

А2 :

ат е А' — Х(а„)Ф ф , ате А* — X (ат) = Ф ,

где X (От) — X - множество логических условий, определяющих переходы из состояния ат . Очевидно, Д* ПА*=0 и А1 и А'-А . Закодируем состояние йт € А' /?< - разрядными двоичными кодами, соответствующими числам 0,... , М, _ 1 ,

где М= ) А1 | . Дан-ный способ кодирования состояний назовем "оптимальное полирование". Обозначим через т ) Ч&СТИЧНЫЙ

код состояний йт €. А . под которьгм пеннмаем часть кода

К (йт) .содержащую Я, = 1пЬ [0Цг М1 разрядов.

Эффективность метода оптимального кодирования состояний определяется отношением

я-

I + 2В,

причем Л тем больше, чем больше отношения я/я, .

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

В дальнейшем рассмотрены методы синтеза РЙ - автоматов с заменой входных переменных. В ходе синтеза оказалось, что при специальном кодировании состояний, ориентированном на уменьшение числа строк ПСТ, одновременное применение оптимального кодирования состояний, минимизирующего М - подсхему, затруднительно, Так как при этом не всегда удается минимизировать аппаратурные затраты. При синтезе РЯ - автомата с преобразователем кода и с использованием кодирования строк подтаблиц использование оптимального кодирования состояний позволяет уменьшить аппаратурные затраты.

В четвертой главе приводятся описание комплекса программ синтеза РЯ - и РУ - автоматов и результаты экспериментальных исследований разработанных методов.

Комплекс программ написан на алгоритмическом языке МоЙи£а-2 и организован в виде подсистемы САПР пСи-90". В

соответствии с ограничениями, принятым в САПР "Си-90", подсистема позволяет синтезировать МПА со следующими параметрами:

число вершин в ГСА < 1000,

количество различных микроопераций < 256,

количество микрокоманд «£ 128,

количество логических условий < 128,

количество строк в ПСТ < 512.

Для оценки эффективности разработанных методов были проведены экспериментальные исследования на совокупности из 60 ГСА различной сложности, собранных в библиотеке САПР "Си-90". Эксперимент заключается в сравнении схем Рй - и РУ -автоматов по аппаратурным затратам.

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

которого аппаратурные затраты в логической схеме РЯ - автомата резко увеличиваются. •

Можно предположить, что Р/3 '- автоматы будут более эффек-тивньми, чем РУ - автоматы, если К > 4 к Й^Ь . Для проверки этой гипотезы была найдена зависимость

^ ши

Проведенные исследования показали, что высказанное предположение является верным. Для сравнения .эффективности применения Рй - автоматов по отношению к РУ - автоматам были найдены различные зависимости, которые подтвердили это предположение.

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

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

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

Результаты экспериментальных исследований подтвердили эффективность разработанных методов и пакета программ, что дает основание рекомендовать подсистему синтеза PR - автоматов на ПЛМ для использования в практике.

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

1. Предложен новый метод многоуровневой реализации автомата Мили, основанный на специальном представлении термов, со--ответствующихjitp окам ИСТ.

2. В рамках этого метода~разра£отан-рядалгоритмов,решад-щих в совокупности задачу синтеза МПА с предложенной структурой/

3. Предложен метод минимизации аппаратурных затрат при синтезе автомата Мили на стандартных мультиплексорах и ПЛМ с использованием метода оптимального кодирования состояний с заменой логических условий.

4. На основе предложенных методов и алгоритмов разработан пакет программ синтеза PR - автомата на IUQM, образующий подсистему САПР "Си-90" и расширяющий ее возможности.

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

Основные результаты диссертацшГопубликованы в следующих ~ ' работах

1. Баркалов A.A., Матвиенко A.B., Дас Д.К. Оптимизация"схемы формирования логических условий при матричной реализации автомата П Микропроцессорные'системы и их применение. - Киев: Ин-т кибернетики им. В.М.Глушкова АН Украины, 1990. - С. 2934.

2. Оптимизация логической схемы автомата Мили па программируемых логических матрицах / Л. А. Баркалов, В. А. Саломатин, К. Е. Стародубов, Д. К. Дас Ц Кибернетика и системный анализ.— 1991.—№ 5.—С. 180—184.

3. Баркалов А. А., Матвиенко А. В., Дас Д. К. Оптимизация логических схем автомата при замене входных переменных // Процессоры и системы обработки сигналов,— Киев: Ин-т кибернетики им. В. М. Глушкова АН Украины,

1991,— С. 51—57.

4. Баркалов А. А., Дас Д. К. Оптимизация логической схемы автомата Мили на ПЛМ // Автоматика и вычисл. техника.— 1991,— № 3,—С. 90—94.

5. Баркалов А. А., Юсифов С. И., Дас Д. К. PR-автоматы: функционирование, оптимизация, выбор метода синтеза,—Киев, Í1991.—26 е.—(Препр. / АН Украины. Ин-т кибернетики им. В. М. Глушкова: 91—65).

6. Оптимизация логической схемы автомата Мили при замене логических условии и специальном кодировании состояний / А. А. Баркалов, В. А. Саломатин, Д. К. Дас, М. Э. Борисова; Донецк, политехи, ин-т.— Донецк, 1992.— 12 е.— Деп. в УкрИНТЭИ 25.05.92. № 718.

7. Баркалоз А. А., Саломатин В. А., Дас Д. К. Минимизация аппаратурных затрат при синтезе автомата Мили на ПЛМ / Донец, политехи, ин-т.— Донецк,

1992,— 8 е.— Д"п. в УкгИНТЭИ 05.06.92. № 808.

8. Оптимизация схемы микропрограммного автомата при замене входных переменных / А. А. Баркалов, В. А. Саломатин, Д. К. Дас, Т. В. Клочко; Донецк, политехи, .ин-т,—Донецк, 1992,— 11 с,—Деп. в УкрИНТЭИ 05.06.92, Ks 827.

9. Структура многоуровневых схем автомата Мили на ПЛМ / А. А. Баркалов, В. А. Саломатин, Д. К. Дас, Манда: Донец, полптенх. ин-т,— Донецк, 1992,— 9 е.— Деп. в УкрИНТЭИ 25.05.92, Jw 719.

Г1одп. в печать 28.18.92. Формат 60Х84'/|б. Бумага типограф. Офсетная печать. Усл. печ. л. 0,93. Уел кр.-отт. ,1,-16. Уч.-изд. л. 0,73. Тираж 120 экз, Заказ 9-7363. 252207, Киев, проспект Академика Глушкова, 40

ДМАПП, 310050, Донецк, ул. Артема, 96