Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§4.4. Абстрактное проектирование автоматов_________281

состояний равны друг другу, т. е.

го о \ f aa ~~ "Ь fbb п

-g s -ls ., Sb) =

--------

T i

--------

= 0.

Для того чтобы внутренние состояния автомата были эквива

лентными, одного и того же соответствия X —> У только в этих

состояниях не достаточно, нужно, чтобы и при любом другом воз

можном переходе из этих состояний отображение X -* У было

одним и тем же.

Для проверки этого условия строим таблицу переходов (табл. 4.4). Каждой

строке, столбцу в этой таблице соответствуют те же значения, что в таблице

выходов, и иа пересечении i-й строки с j-м столбцом находится класс условно

эквивалентных состояний, в который переходит автомат из состояния S3 под

воздействием ЛГ|.

Таблица 4.4

56 57

Ку

Кг

к2

К\

кх

к2 Кг

к2

к2 к2 к2 к2

к2 к2

Если класс условно эквивалентных состояний, выделенный иа предыдущем

шаге, ие является классом эквивалентных состояний, то состояниям этого класса

соответствуют различные значения столбцов; это означает, что при дальнейших

переходах отображения X —¥ Y различны для данных состояний.

Каждый класс К\ разбивается на новые классы условно эквивалентных со

стояний, причем в один и тот же класс входят все состояния класса К\ с одинако

выми значениями столбцов: К\ = {Si, S2} Ss}, Ki = (5з, 56}, К2 = {54, 5?}.

Составим по таблице переходов частотную матрицу отношений,

определив при этом умножение как К{ X К{ — 1, К{ х Kj = 0

(t ф j). Тогда внутренние состояния попадают в один и тот же

класс при разбиении классов, полученных на предыдущем шаге,

если собственные и взаимные частоты этих состояний равны друг

другу, т. е.

— (S., St) = 0.

После получения классов Кг, К'2, К2 опять строим таблицу переходов и т. д.

до тех пор, пока каждый класс условно эквивалентных состояний, выделенный

иа предыдущем шаге, ие станет неизменным.

Построим таблицу переходов (табл. 4.5), учитывая разбиение класса К2.

Таблица 4.5

5, s2

53 54

56 5т

Кг

Кг к?

Кг

Ki Ki

к\

Анализируя эту таблицу, делаем вывод, что все состояния каждого из выде

ленных классов “ведут себя дружно”: переходят под воздействием X в один и

282

Гл. 4. Теория формальных грамматик и автоматов

тот же класс, что обуславливает получение иа выходе одного и того же значения

У для всех состояний класса при одном переходе. Следовательно, все состояния

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

Заменим классы К\, К2, К'{ соответственно внутренними состояниями 50,

Sb, Sc. В результате получим минимизированный граф переходов (рис. 4.14,6),

задающий то же отображение X -► У, что и первоначальный граф переходов

(рис. 4.14, а). Для иллюстрации проведем три эксперимента.

Пусть иа вход автомата подается временная последовательность вида X(t) =

= 011010. В первом и во втором случаях автомат задай первоначальным графом

переходов (рис. 4.14, а) соответственно с начальными состояниями 5i и 52. В

третьем случае автомат задай минимизированным графом (рис. 4.14,6) с на

чальным состоянием Определим временные выходные последовательности

У(t) для каждого случая.

Таблица 4.6

t l

X(t) 0

1 0

бмач — S i

S(t + 1)

5т

5 6

У(0

0 1

5ЖМ = S 2

S (t-l-l)

5т 5 s

У(0

0 1

S(t + 1)

5»

5с

5»

У(0

0 1

Результаты всех трех экспериментов сведем в таблицу (табл. 4.6).

Минимизация объема памяти, например, в 4 раза, экономит

только два элемента памяти. Более актуальным и мощным сред

ством оптимизации всей структуры автомата является абстракт

ная декомпозиция автоматов, особенно параллельная декомпо

зиция автоматов. Необходимость поиска ее, с одной стороны,

диктуется современными требованиями, предъявляемыми к бы

стродействию управления (обусловливающими использование па

раллельного управления объектом). С другой стороны, повышение

безотказности автоматного управления требует разбиения авто

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

меньшей размерности, обеспечивающих реализацию полученного

автоматного оператора.

Поиск параллельной декомпозиции абстрактных автоматов сво

дится к разложению графа переходов в частичное декартово

произведение более простых по числу вершин графов. Разло

жить граф G в частичное декартово произведение — значит, найти

графы Gi, г = 1, ..., п, такие, что G С G\ х G2 х . • • х Gn.

Для важного в вычислительной технике класса автоматов ми

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

декомпозиции можно решить, используя характерные свойства ав

томатов этого класса.

При рассмотрении микропрограммных автоматов элементы, с

которых снимается информация, характеризующая ход вычисле

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

§4.4. Абстрактное проектирование автоматов

283

памяти автомата. Микропрограммные автоматы обладают специ

фическим свойством: входной вектор X остается неизменным от

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

операция. Используя это свойство, уточним понятие микропро

граммного автомата.

Предварительно введем несколько понятий. Цунгом Gn на

зывается взвешенный граф, в котором найдется хотя бы одна вер

шина, через которую проходят все контуры графа, и не существует

ни одного пути, не являющегося частью одного из таких контуров.

Граф называется приводимым к цунгу, если при введении в

него не более одной вершины и инцидентных ей дуг он преобра

зуется в цунг.

Автомат, граф переходов которого приводим к цунгу с иници

альной вершиной, соответствующей началу и концу работы авто

мата при любом входном векторе X , определяющем реализуемую

операцию и не изменяющемся в промежуточных состояниях, на

зывается микропрограммным. В общем случае микропрограмм

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

соответствует микропрограмма. При построении графа переходов,

реализующего эти микропрограммы, будем производить склеива

ние совместимых состояний.

Внутренние состояния Si, Sj называются совместимыми,

Si = Sj, если любой входной вектор, подаваемый на вход автомата,

который находится в состоянии 5,-, не совпадает и не является

частью ни одного входного вектора, подаваемого на вход автомата,

который находится в состоянии Sj: Xs, 0 X s} ■

Подграф G' = (V7, U') графа G = (V, U) называется двухинци-

дентным, если каждой его вершине инцидентны две и только две

группы параллельных дуг, входящих и исходящих, за исключе

нием, быть может, минимального элемента v+ € V' и максималь

ного элемента v~ € V' множества V', причем в вершину v+ могут

входить, а из вершины v~ выходить несколько непараллельных

дуг. Последовательности микрокоманд, взвешивающие двухинци-

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

входящих в последовательность, — его длиной.

При синтезе автомата управления, реализующего несколько

микропрограмм, производим склеивание совместимых внутрен

них состояний, учитывая при этом два ограничения. Во-первых,

склеивание следует начинать с конечных состояний, соответствую

щих различным операциям. Во-вторых, сначала склеивают те со

вместимые состояния, в которых на выходе автомата вырабаты

вается одна и та же микрокоманда.

Рассмотрим микропрограммный автомат управления процессором ЭВМ для

выполнения операций “суммирование” (а + о), “вычитание” (а — Ь) и “пораз

рядное сложение”. Графы переходов, построенные по временным диаграммам,

Изображены на рис. 4.15. Микрокоманды иа этом рисунке обоэиачены латин

284

Гл. 4. Теория формальных грамматик и автоматов

скими буквами: а = {ГД}\ Ь = {НП}; с = d = {СВ, ГС, В -> С};

е = {СС, О}; к = {ГД, СВ, ГА, +1Г30Д}; m = {ДА, ГД}\р = {ДА, ДВ}-

г = {НП, СВ}.

Микрооперации, являющиеся элементами микрокоманд, расшифровывают

ся следующим образом: ДА — дополнение регистра А \Г Д — гашение регистра

Д; НП — начало пробега; Д В — дополнение регистра В; СВ — счет регистра

В] В 53 — выдача суммы ГА — гашение регистра А\ +1Т30Д — плюс

1 в триггер 30 регистра Д \Г С — гашение регистра С\ В С — передача

из регистра В в регистр С; СС — счет регистра С; О — ответ о выполнении

операции.

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

ТОД — значением триггера нуля регистра Д (иа рис. 4.15 и в дальнейшем

ТОД будем обозначать 7 ).

Суммирование (* = 01)

(XjXj, a) (ifjX* М <*1*2? > с> Л (*1*2' е>

( * , х 27 , с)

O TjJt* е)

( j ? ! ^ , к) (jCj^jtj. b) (3fi3t2, с ) (jf1Jt2, d)

--------

» ( § )

--------

.......................

Вычитание (x= 11)

( x f o m) (jc1x2Y. b) c) <-*1*2’

О —

(X j x24, b)

(x,x2, c)

(x^j, e)

(x,x2, a) (XyX2, г) (ХуХ}, с) (xfa, d)

Поразрядное сложение (x = 10)

(Xj3f2. a) (XjX2, с) (х,У2. rf) (х,лГ2, M

----

*■©

----

- — * 0

Рис 4.15

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

объединенный граф переходов G (рис. 4.16, а). На этом графе в состояниях Sf,

Sa и Sp доопределено отображение X —¥ Y добавлением с), (Х1Х2, d) и

(Х1Х2, е) соответственно (рис. 4.16,6). После такого склеивания совместимых со

стояний произведем свертывание двухинцидеитных подграфов. Под свертыва

нием двухинцидеитных подграфов понимаем аамену этого подграфа иа вершину,

взвешенную соответствующим микролучом. Микролучи имеют следующий вид:

А = abc, В = de, D = kb, Е = mb, М = par.

В результате свертывания двухинцидеитных подграфов полу

чаем граф автомата управления (рис. 4.17, а), в котором нарушена

§4.4. Абстрактное проектирование автоматов

_________285

детерминированность: одному состоянию, соответствующему вер

шине, в которую свернут двухинцидентный подграф, соответствует

несколько микрокоманд.

Исходный граф переходов (рис. 4.16, б) получается как частич

ное декартово произведение графа G (рис. 4.17, а) и двухинцидент-

d) (х,хг, е)

Рис. 4.16

ного графа, конец которого соединен дугой с его началом, и число

вершин равно максимальной длине рассматриваемых микролучей

(в данном случае трем). Двухинцидентный граф, конец которого

соединен дугой с началом, реализуется в виде счетчика.

Таким образом, детерминированность автомата и эквивалент

ность его функционирования сохраняем, вводя в обратную связь

автомата счетчик микрокоманд в микролуче, увеличивающий свое

значение до числа, равного максимальной длине микролуча /макс

(рис. 4.17,б).

При переходе в вершину van соответствующую свернутому

двухинцидентному подграфу G,, на счетчике устанавливается

286

Гл. 4. Теория формальных грамматик и автоматов

число, равное /макс - f,, где /, — длина микролуча, взвешиваю

щего этот подграф. При этом Ц состояний счетчика взаимно од

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

Операции {;

Счетчик

микрокоманд в

микрояуче

Память,

фиксирующая

вершину в гра

фе переходов

Комбинаци

онная часть

'Микрооперации

Рис. 4.17

Логические признаки

шине VGi • При каждом переходе в двухинцидентном подграфе к

содержимому счетчика прибавляется 1. Следовательно, совокуп

ность кода вершин vat и показания счетчика взаимно однозначно

определяют выполняемую микрокоманду. Переполнение счетчика

указывает на то, что автомат вышел из состояния, соответствую

щего вершине vg{-

Такая организация переходов позволяет не возбуждать выходы

комбинационной части автомата, идущие в обратную связь в про

цессе выполнения микролуча, так как состояние памяти, запо

минающей вершину VQi, остается неизменным, а переход счет

чика из состояния в состояние происходит автоматически при

бавлением единйцы либо извне, либо с помощью микрооперации

+1 Счц (прибавление единицы в счетчик микрокоманд), расши

ряющей множества микроопераций. При использовании послед

него способа возбуждается только один выход, идущий в обратную

связь.

Дальнейшие преобразования графа переходов произведем, стя

гивая незацепленные состояния. Два внутренних состояния (две

вершины) графа переходов называются неэацепленными, если они

не входят ни в один из простых путей графа переходов при функ

ционировании синтезируемого автомата.

Для предполагаемого преобразования графа переходов постро

им граф Gz следующим образом. Каждой вершине графа переходов

взаимно однозначно сопоставим вершину графа G3; пара вершин

va, vb (va ф Vj,) графа G3 смежна, если в графе переходов суще-

§4.4. Абстрактное проектирование автоматов

287

ствует простой путь, проходящий через вершины, соответствую

щие v0 и Vj,, при функционировании синтезируемого автомата.

Построенный таким образом граф Gz будем называть графом за

цепления.

С помощью операции раскраски вершин графа разобьем все

множество вершин графа зацепления на подмножества, каждое

из которых состоит из вершин, соответствующих незацепленным

внутренним состояниям синтезируемого автомата.

Граф зацепления и его раскраска для автомата, изображенного

на рис. 4.17, а, приведены на рис. 4.18, а. В результате раскраски

Х= 01

/-> Х = 10

х =11

\S>

*{=*

Комбинационная

часть

Счетчик

микрокоманд

влуче

Память,

фиксирующая

краску

выполняемого

луча

Память,

фиксирующая

вершину в

графе

переходов

:}У

Логические

признаки

Рис. 4.18

288

Гл. 4. Теория формальных грамматик и автоматов

графа зацепления имеем следующие подмножества состояний, ка

ждое из которых состоит из незацепленных между собой состоя

ний:

Vi = {Ss,S22,S'}, Vn = {S„,SC}, Vhi = {s„}, Fiv = {57}-

Из каждого подмножества Vi (i = I, ..., IV) выбираем по одному элементу,

например, Sf, 5М, 57, 5^; из выбранных элементов образуем подмножество

V31 = {5«, SM, Sv, Sy}. Далее, снова из каждого подмножества К выбираем

по одному из оставшихся элементов и снова образуем из иих подмножество. Вы

борку осуществляем до тех пор, пока каждое из подмножеств V; не преобразуется

в пустое множество. Образованные в результате этой выборки подмножества и

являются подмножествами, состоящими из зацепленных состояний. В данном

случае они имеют следующий вид:

Vu = {£*, 3Й, Sv, Sy}, V32 = {З’гз, = {S,}.

Каждое подмножество, состоящее из зацепленных состояний,

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

микролучей, соответствующих объединяемым вершинам (в част

ном случае микролуч может состоять из одной микрокоманды).

Такую замену будем называть стягиванием зацепленных состоя

ний. В результате стягивания зацепленных состояний графа пе

реходов (рис. 4.17, а) получаем граф переходов G„ (рис. 4.18,5).

Стягивания зацепленных состояний также нарушают детермини

рованность автомата. Детерминированность синтезируемого авто

мата и его эквивалентность сохраняем, введя в обратную связь эле

мент памяти, в котором будет фиксироваться краска, соответствую

щая микролучу, выполняемому в данный момент (рис. 4.18,в).

Тогда совокупность кода вершины окончательного графа перехо

дов, краска и показания счетчика микрокоманд в микролуче вза

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

зультате такого преобразования граф переходов можно предста

вить в виде частичного декартова произведения соответствующих

графов (рис. 4.18, в), что упрощает процесс кодирования внутрен

них состояний и практически уменьшает аппаратурные затраты

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

Если контуры в графе переходов, соответствующем реализуе

мым микропрограммам, отсутствуют, то целесообразно разложить

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

красок. При этом проводят свертывание двухинцидеитных под

графов в каждом графе переходов, соответствующем реализуемой

операции, с последующим склеиванием совместимых состояний.

Если граф переходов является деревом, то в обратной связи ав

томата оставляют только счетчик. При этом граф переходов реали

зуется счетчиком при условии запоминания или наличия значений

логических переменных, характеризующих вычисления. Началь

ному внутреннему состоянию автомата сопоставляется начальный

код на счетчике, например код 0. Внутренние состояния, в кото

рые автомат переходит из состояния 5,-, имеющего код

А, кодиру

ются как А + 1. Смена кодов происходит прибавлением единицы

§ 4.4. Абстрактное проектирование автоматов

289

в счетчик при каждом переходе. Тогда при наличии разветвления

некоторые внутренние состояния будут иметь одинаковые коды.

Детерминированность автомата при этом не нарушается благодаря

хранению логических признаков, характеризующих проводимые

вычисления. Показания счетчика и значения логических пере

менных однозначно определяют нужную микрокоманду. Данное

утверждение справедливо, так как граф переходов является дере

вом, т. е. не содержит циклов. В конце выполнения операции

происходит гашение счетчиков.

При представлении графа переходов, соответствующего авто

мату управления одной операцией, в виде частичного декартова

произведения производят следующие преобразования:

1) склеивание псевдоэквивалентных состояний;

2) свертывание двухинцидентных подграфов, причем в резуль

тате изменения последовательности применения этих преобразо

ваний возникает несколько эквивалентных вариантов.

Рассмотрим граф переходов управления операцией деления (см. рис. 4.11).

Стягивая двухинцндеитные подграфы, получаем граф переходов G (рис., 4.19, а).

Вершинам этого графа соответствуют следующие микролучи: S\ — а; 5„ —

Рис. 4.19

bcdcdcdc, Sb — dc; Sd — dc; Se — dc; Sf — hk; S4 — efg; S23 — т. Сле

довательно, для восстановления эквивалентного функционирования необходим

счетчик на 8 состояний.

Вершины, соответствующие состояниям 5 / и S4 в графе переходов

(рис. 4.19,а), можно склеить при иалнчни запоминания признака ро; детерми

нированность автомата при этом ие нарушается. Окончательно имеем граф пе

реходов G, изображенный на рис. 4.19,5. Состояния счетчика, признак ро и код

вершины графа переходов (рис. 4.19,6) однозиачио определяют выполняемую

микрокоманду.

Внутренние состояния называются псевдоэквивалентными, если в них

реализуется одна и та же микрокоманда. Для графа переходов Ga (см. рис. 4.11)

имеем следующие множества псевдоэквивалентных состояний: Мс = {5з, Ss,

St, Sg, Su, S13 , Su, Si7}; M i = {5<, 5*, Sw, Su, Su, Sie}.

В результате склеивания псевдоэквивалентных состояний (рис. 4.20, а) на

рушается детерминированность автомата. Детерминированность и эквивалент

ность функционирования автомата восстанавливаем введением счетчика при ор

ганизации цикла переменной длины. На рис. 4.20,5 приведена программа

10 В. А. Горбатов

290 Гл. 4. Теория формальных грамматик и автоматов

работы счетчиков; в рассматриваемом автомате к = 7. Внешний цикл реали

зуется счетчиком длины цикла СчДЦ.

Внутренний цикл реализуется счетчиком числа циклов СчЦ. Признак у,

который восстанавливает детерминированность автомата, вычисляется в блоке,

включающем эти счетчики (рис. 4.20,в). В том же блоке вычисляется и при-

Рис. 4.20

знак окончания операции /3 (как сигнал переполнения счетчика СчДЦ, причем

начальное состояние этого счетчика равно 2).

После восстановления детерминированности автомата производим склеива

ние двухинцидеитных подграфов (рис. 4.21, а, 6). Для восстановления детерми

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

подграфов введем еще два счетчика, имеющих три и два состояния соответ

ственно.