Микропрограммный автомат

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

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

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

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

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

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

Блок-схема такой микропрограммы представлена на рис. 2.28.

Рис.2.28 Блок-схема микропрограммы сложения и вычитания

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

Рис. 2.29 Разметка блок-схемы алгоритма

Анализ разметки блок-схемы позволяет найти элементы всех алфавитов для проектирования автоматной модели: X={1;p₁;p-₁;p₂;p-₂}, Y={y₁;y₂;y₃;y₄;y₅;y₆;y₇}, Q={q₀;q₁;q₂;q₃;q₄;q₅;q₆;q₇}. В таблице 2.23 дано описание автомата Мили, используя разметку блок-схемы алгоритма.

Таблица 2.23

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

Таблица 1.93.

2.5. Магазинный автомат.

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

Магазинный автомат - это композиция управляющего автомата и двух магазинов X и F, каждый из которых представляет собой бесконечную в одну сторону последовательность ячеек памяти. Эту последовательность удобно представить в виде вертикальной колоды (cм. рис.2.30).

Рис. 2.30 Структура магазинного автомата.

Управляющий автомат считывает последовательно символы входного слова a и заносит их в магазины X или F. Первый символ заносится непосредственно на ограничитель (дно магазина), а затем ячейки магазинов заполняются последовательно одна за другой. Так как последовательность символов слова a упорядочена синтаксисом соответствующего формального языка и последний символ, заложенный в ячейку памяти магазина, является первым для последующей обработки, то такая организация хранения символов называется стеком. Ее принцип: последним пришел - первым ушел. Символы слова b поступают в операционный автомат для исполнения заданной операции. Принцип работы магазина удобно объяснить на примере моделирования арифметических выражений.

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

шаг 1: считать очередной символ входного слова a:

a) если очередной символ - операнд, то управляющая команда K_x:

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

b) если очередной символ - операция, то перейти к шагу 2;

с) если очередной символ e (пустой символ) и магазин F пуст, то конец иначе перейти к шагу 2b);

шаг2: выполнить анализ очередной операции по правилам арифметики:

a) если очередная операция должна выполняться до операции, символ которой находится в последней ячейке магазина F или магазин F пуст, то управляющая команда K₁:

"занести символ в очередную ячейку магазина F и перейти к шагу 1";

b) если очередная операция должна выполняться после операции, символ которой находится в последней ячейке магазина F (или они равноправны), то управляющая команда K₂:

"выполнить операцию, символ которой находится в последней ячейке магазина F, над двумя операндами, значения которых находятся в последних ячейках магазина X;

удалить символ выполненной операции из магазина F;

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

поместить значение результата вычисления в последнюю ячейку магазина X; поместить символ очередной операции в последнюю ячейку магазина F; повторить шаг 2b);

перейти к шагу 1";

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

Таблица 2.25

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

Рис. 2.31 Блок-схема магазинного автомата.

Эту блок-схему можно реализовать аппаратно в виде автомата Мили или Мура.

Пример 2.3. Пусть дано арифметическое выражение a_*b/c+d_*e/p-re. В таблице 2.26 показана последовательность работы управляющего автомата. Изменения содержимого магазинов X и F выделено курсивом и указаны стрелками

Таблица 2.26

Таблица 1.92 (продолжение).

Дата добавления: 2015-07-26; просмотров: 281; Нарушение авторских прав

Мы поможем в написании ваших работ!