Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 51
Текст из файла (страница 51)
Заменим классы Кп Кз, Кэ соответственно внутренннми состоянняии Я, оь, Яь. В результате получим иииимизнровзнный граф переходов (рис. 4.14, б), зздзющий то ие отобрзиньие Х -ь У, что и первоизчзльный граф переходов (рис. 4.14, а). Для иллюстрации проведем три эксперименте. Пусть из вход звтоывтз подеется временная последовзтельиость виде Х(1) = = 011010. В первом и во втором случзях звтомзт задан первоначальным графом переходов (рис. 4.14, а) соответственно с начальными состояниями 8ь и Яэ. В третьем случае звтомзт ззлзи минимизированным графам (рис.
4.14,6) с печальным состоянием Ю,. Определим временные выходные последовательности У(г) для нзидого случая. Таблица 4.6 Результзты всех трех экспериментов сведем з таблицу (тзбл. 4.б). Минимизация объема памяти, например, в 4 раза, экономит только два элемента памяти.
Более актуальным и мощным средством оптимизации всей структуры автомата является абстрактная декомпозиция автоматов, особенно параллельная декомпозиция автоматов. Необходимость поиска ее, с одной стороны, диктуется современными требованиями, предъявляемыми к быстродействию управления (обуславливающими использование параллельного управления объектом). С другой стороны, повышение безотказности автоматного управления требует разбиения автомата на ряд функционально не связанных друг с другом автоматов меньшей размерности, обеспечивающих реализацию полученного автоматного оператора. Поиск параллельной декомпозиции абстрактных автоматов сводится к разлолсекию графа переходов в частичное декарпьаво произведение более простых по числу вершин графов.
Разложить граф С в частичное декартово произведение — значит, найти ГРафЫ Об Э = 1, ..., П, таКИЕ, Чта С С Сзт Х бт Х ... Х С„. Для важнога в вычислительной технике класса автоматов микропрограммного упраалеииз задачу построения параллельной декомпозиции можно решить, используя характерные свойства автоматов этого класса.
При рассмотрении микропрагральнных автоматов элементы, с которых снимается информация, характеризующая ход вычислений, будем относить к цепям обратной связи, включенным в блок 14.4. Абстрактное проектирование аатоматоа 283 памяти автомата. Микропрограммные автоматы обладают специфическим свойством: входной вектор Х остается неизменным от начала до конца работы автомата, пока не выполнится заданная операция.
Используя это свойство, уточним данятие микропрограммного автомата. Предварительно введем несколько понятий. г(унгам Сц называется взвешенный граф, в котором найдется хотя бы одна вершина, через которую проходят все контуры графа, и не существует ни одного пути, не являющегося частью одного из таких контуров. Граф называется приводимым к цунгу, если при введении в него не более одной вершины и инцидентных ей дуг он преобраауется в цунг. Автомат, граф переходов которого приводим к цунгу с инициальной вершиной, соответствующей началу и концу рабаты автомата при любом входном векторе Х, определяющем реализуемую операцию и не изменяющемся в промежуточных состояниях, называется микропрограммным.
В общем случае микропрограммный автомат реализует несколько операций, каждой из которых соответствуег микропрограмма. При построении графа переходов, реализующего эти микропрограммы, будем производить склеивание совместимых состояний. Внутренние состояния Я;, 5.
называются совместимыми, Я; = Ят, если любой входной вектор, подаваемый на вход автомата, который находится в состоянии 5;, не совпадает и не является частью ни одного входного вектора, подаваемого на вход автомата, который находится в состоянии 5,: Хв,, у. Хс,. Подграф 6' = (У', У') графа сг = (У, ГУ) называется двухинциденгпным, если каждой его вершине инцидентны две и толька две группы параллельных дуг, входящих и исходящих, за исключением, быть может, минимального элемента а+ Е У' и максимального элемента о Е У' множества У', причем в вершину а+ могут входить, а из вершины а выходить несколько непараллельных дуг. Последовательности микрокоманд, взвешивающие двухинцидентный подграф, называются микралучам, а число микрокаманд, входящих в последовательность, — его длиной. При синтезе автомата управления, реализующего несколько микропрограмм, производим склеивание совместимых внутренних состояний, учитывая цри этом два ограничения.
Во-первых, склеивание следует начинать с конечных состояний, соответствующих различным операциям. Во-вторых, сначала склеивают те совместимые состояния, в которых на выходе автомата вырабатывается одна и та же микрокоманда. Рассмотрим энькропрогрзиэннзй звтоивт управления процессором ЭВМ для выполнения оперзпий "суммирование" (а+ Ь), "вычитзние" (а — Ь) н "порззрялное слоненке". Графы переходов, костроейные по временным дизгрзыизм, нвебрзнены из рнс. 4,15. Мнкрокомзиды из этом рисунке обозизчены латин- Х 01 Х= 11 ! 1О У / Х 01 ь —— Х 11 ! !.
Х 10 Рис. 4.16 Рис. 4.15 284 Гл. 4. Теория формальных зрамматик и автоматов скими буквемн: а м (ГД); Ь = (НП); с = (В );); 4 = (СВ, ГС, В -+ С); е = (СС, О); Ь = (ГД, СВ, ГА, +1ТЗОД); гп = (ДА, ГД); р = (ДА, ДВ); .= НП,СВ). икрооперзции, являюшнеся элемеитамн микрокоманд, расшифровываются следующим образоьс ДА — дополнение регистра А; ГД вЂ” гашение регистра Д; НЛ вЂ” начало пробега; Д — дополнение регистра В) С — счет регистра В; В 2 — выдача сумыы ~ ГА — гашение регистра А; +1ТЗОД вЂ” плюс 1 в триггер ЗО регистра Д; С вЂ” гашение регистра С; В -+ С вЂ” перелача нз регистра В в регистр С; СС вЂ” счет регистра С; Π— ответ о вмполнениц операции.
Реаулыат проводимых вычислений характеризуется логической переменной ТОД вЂ” аначением триггера нуля регистра Д (иа рис. 4.15 и з дальнейшем ТОД будем обоаначать «). Суммирование (х 01) (Угхг, а) (тгхг, Ы (тгхгт, с) (Тгхг, со (тгхг, е) I Вычитание (х 11) (х!хг,т)(хгхгт, Ы (х|хг, с)(хгхг,о) Перевранное сложение (х 10) (Х)тг а) Ст)тг С) (Х!тг ") (Х!тг Ь) I ~у Произведем скленваняе совместимых состояний. В результате получаем объединенный граф переходов С (рис. 4.16, о). Па етом графе в состояниях Б», о и Яя доопределено отображение х ~ 1' добавлением (Угхг, с), (хгиг, !() и (х газ, е) соответственно (рис. 4 16, б).
После такого склеивания говне ставнях состояний произведем свертывание двухинцидентных подграфов. Под сеерть!еан и ем двухннцидентных подг рафов понимаем замену этого подграфа на вершину, взвешенную соответствующим микролучом. Микролучи имеют следующий внд; А = або, В = !(е, Р = ЬЬ, Е = тЬ, М = раг. В результате свертывания двухинцидентных подграфов получаем граф автомата управления (рис. 4.17, а), в котором нарушена 14.4. Абстрактное нроекпгирооание аотоматое 285 детерминированность: одному состоянию, соответствуюшему вершине, в которую свернут двухинцидентный подграф, соответствует несколько микрокоманд.
Исходный граф переходов (рнс. 4.18, 6) получается как частичное декартово произведение графа С (рис. 4.17, а) и двухинцидент- ного графа, конец которого соединен дугой с его началом, и число вершин равно максимальной длине рассматриваемых микролучей (в данном случае трем). Двухннцидентный граф, конец которого соединен дугой с началом, реализуется в виде счетчика. Таким образом, детерминированность автомата и эквивалентность его функционирования сохраняем, вводя в обратную связь автомата счетчик мнкрокоманд в микролуче, увеличивающий свое значение до числа, равного максимальной длине микролуча (м кс (рис.
4.17, б). При переходе в вершину иО!, соответствующую свернутому двухинцндентному подграфу гх;, на счетчике устанавливаетсн Х О г х-1о — ) Операции ( х„-и ие прививки ческив изизки Рис. 4.18 286 Гл. 4. Теорш Яормалзнмк ерамматик и автоматов число, равное 1„,„, — 1,, где 1; — длина микролуча, взвешивающего этот подграф. При этом Ц состояний счетчика взаимно однозначно сопоставляются микрокомандам, соответствукицнм вер- шине иск,. При каждом переходе в двухинцидентном подграфе к содержимому счетчика прибавляется 1.
Следовательно, совокупность кода вершин иск, и показания счетчика взаимно однозначно определяют выполняемую микрокоманду. Переполнение счетчика указывает на то, что автомат вышел из состояния, соответствующего вершине исз, Такая организация переходов позволяет не возбуждать выходы комбинационной части автомата, идушие в обратную связь в процессе выполнения микролуча, так каи состояние памяти, запоминающей вершину иск,, остается неизменным, а переход счетчика из состояния в состояние происходит автоматически прибавлением единицы либо извне, либо с помощью микрооперации +1Сч1з (прибавление единицы в счетчик микрокоманд), расширяющей множества микроопераций. При использовании последнего способа возбуждается только один выход, идущий в обратную связь.
Дальнейшие преобразования графа переходов произведем, стягивая незацепленные состояния. Два внутренних состояния (две вершины) графа переходов называются неэацепленнмми, если они не входят ни в один из простых путей графа переходов при функционировании синтезируемого автомата. Для предполагаемого преобразования графа переходов построим граф Сз следующим образом. Каждой вершине графа переходов взаимно однозначно сопоставим вершину графа с 'з, пара вершин и„из 1и, у4 иь) графа Сз смежна, если в графе переходов суще- 8 4.4. Абстрактное проектирование автоматов 287 ствует простой путь, проходящий через вершины, соответствуюшие и, и им при функционировании синтезируемого автомата. Построенный таким образом граф Сз будем называть графом эапепленш. С помошью операции раскраски вершин графа разобьем все множество вершин графа зацепления на подмножества, каждое из которых состоит из вершин, соответствующих незацепленным внутренним состояниям синтезируемого автомата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
