UA / Постников А.И. Лаб раб Упр Авт

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

ТЕОРИЯ АВТОМАТОВ

УПРАВЛЯЮЩИЕ АВТОМАТЫ С ПРОГРАММИРУЕМОЙ ЛОГИКОЙ

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

Красноярск 2011

УДК 519.713(075):004.383

Теория автоматов. Управляющие автоматы с программируемой логикой: Методические указания к лабораторным работам для студентов направления подготовки 230100.62 – "Информатика и вычислительная техника" и специальности 230101.65 – "Вычислительные машины, комплексы, системы и сети" / Сост. А.И. Постников; СФУ. Красноярск, 2011.

48 с.

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

Печатается по решению редакционно-издательского совета университета

© СФУ, 2011

Редактор

Подп. в печать ………... Формат …………….. Бумага тип. …….. Офсетная печать. Усл. печ. л. Уч.-изд. л. Тираж …….. экз

Заказ

Издательство СФУ 660074, г.Красноярск, ул. Киренского, 26

1 Управляющие автоматы

Процессор ЦВМ или другое операционное устройство, выполняющее операции над словами информации можно рассматривать как состоящее из

двух блоков или автоматов – опера-
ционного (ОА) и управляющего (УА).
Структура процессора представлена на				D				R
рис. 1.
Процессор выполняет			заданное
множество операций		F над входными
словами	D с целью вычисления резуль-					ОА
татов R. Каждая операция из множества
операций	F возбуждается		соответст-	Y					X
вующей	командой	из	множества
команд K.
						УА
Любая команда, операция или
процедура, выполняемая в операци-
онном автомате, описывается некоторой
микропрограммой и реализуется за не-
						K
сколько тактов, в каждом из которых
выполняется одна или несколько мик-
роопераций.

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

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

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

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

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

Каждая микрооперация инициализируется соответствующей микрокомандой из множества микрокоманд Y, вырабатываемых УА. Каждый управляющий функциональный сигнал поступает в начале некоторого такта на соответствующий вход ОА, вызывая в этом такте выполнение в ОА определенной микрооперации (инвертирование, инкремент или декремент, передача слова, суммирование кодов и др.)

2.Для управления порядком следования микроопераций (порядком выдачи управляющим автоматом микрокоманд Y) используются логические условия Х, принимающие значения 1 или 0. Генерируемая УА последователь-

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

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

Таким образом, УА генерирует последовательность управляющих сигналов Y, предписанную микропрограммой и соответствующую значениям логических условий Х.

УА можно рассматривать как конечный автомат, определяемый: а) множеством двоичных выходных сигналов

Y = {y1, y2, ... , yL},

соответствующих множеству микроопераций операционного блока. При yi = 1 инициируется i-я микрооперация;

б) множествами входных сигналов K и X:

K = {k1, k2, ... , kZ};

X = {x1, x2, ... , xM},

соответствующих задаваемому извне двоичному коду операции, команды (K) и двоичным осведомительным сигналам (Х);

в) множеством подлежащих реализации микропрограмм (каждая микропрограмма инициируется соответствующей командой), устанавливающих в зависимости от значений входных сигналов управляющие сигналы, выдаваемые УА в определенные такты.

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

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

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

Существуют два основных типа управляющих автоматов:

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

тором необходимое множество состояний представляется состояниями k запоминающих элементов.

2. Управляющий автомат с хранимой в памяти логикой (с "запоминаемой или программируемой логикой"). Каждой выполняемой в операционном устройстве операции ставится в соответствие совокупность хранимых в памяти слов — микрокоманд, содержащих каждая информацию о микрооперациях, подлежащих выполнению в течение одного машинного такта, и указание (в общем случае зависящее от значений входных сигналов), какое должно быть выбрано из памяти следующее слово (следующая микрокоманда). Таким образом, в этом случае функции переходов и выходов f и управляющего автомата реализуются хранимой в памяти совокупностью микрокоманд.

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

ляющей памяти").

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

ляющими устройствами (автоматами).

1.2 Принцип управления по хранимой микропрограмме

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

Функция управляющего автомата определяется:

множеством входных осведомительных сигналов Х, отображающих состояние операционного автомата;

множеством выходных (управляющих) сигналов Y, инициирующих выполнение микроопераций, реализуемых операционным автоматом;

закодированной граф-схемой микропрограммы (ГСМ), задающей порядок следования управляющих сигналов Y в зависимости от значений осведомительных сигналов Х.

ГСМ строится с использованием вершин четырѐх типов (рис. 2) и дуг, связывающих вершины.

Начало	Оператор	Условие
			Конец
а	б	в	г

Рис. 2. Вершины ГСМ: начальная (а), операторная (б), условная (в) конечная (г)

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

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

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

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

ГСМ считается корректной, если выполняются следующие условия:

ГСМ содержит конечное число вершин, каждая из которых принадлежит к перечисленным типам;

имеет одну начальную и одну конечную вершины;

выходы и входы вершин соединяются с помощью дуг, направленных от выхода ко входу;

каждый выход соединѐн с одним входом;

из любой вершины существует хотя бы один путь к конечной;

один из выходов условной вершины может соединяться с еѐ входом, что недопустимо для операторной вершины;

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

УА;

в каждой операторной вершине записывается оператор (микрокоманда из множества микрокоманд).

ГСМ делят на содержательные и закодированные. В содержательной ГСМ в условных и операторных вершинах записываются условия и операторы. Пример содержательной ГСМ представлен на рис. 3.

Закодированная ГСМ отличается от содержательной тем, что в услов-

ных и операторных вершинах записываются символы х1, ... , хN и у1, ... , уM, отождествляемые с осведомительными и управляющими сигналами УА.

На рис. 4 представлена закодированная ГСМ, полученная на основе содержательной ГСМ рис. 5.3.

Начало

Начало

RgA: = 0

y1

0

0

A > 0

1

x1

1

y2

y3

RgA: = RgA+1

RgA: = RgA

Конец

Конец

Рис. 3. Содержательная ГСМ

Рис. 4. Закодированная ГСМ

Функционирование управляющего автомата (УА) сводится к генерированию последовательности управляющих сигналов Y, предписанной микропрограммой, и соответствующей последовательности осведомительных сигналов Х.

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

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

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

Способ адресации микрокоманд задаѐт правило определения адреса следующей микрокоманды. Существуют два способа определения адреса следующей микрокоманды – принудительная адресация и естественная адресация.

Процедура построения УА с хранимой логикой по имеющейся ГСМ заключается в следующем.

1.Выбирают способ адресации и формат микрокоманд, причем стремятся сократить число двоичных разрядов в формате микрокоманды, что, как правило, позволяет уменьшить объем оборудования ПЗУ.

2.Производят разметку ГСМ в соответствии с правилами, которые определяются выбранным способом адресации.

3.Составляют кодированную микропрограмму в виде таблицы, строки которой соответствуют отметкам на ГСМ.

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

ипринципиальную схемы автомата.

Выполнив эти этапы, переходят к технической реализации УА. Исходными данными для проектирования УА являются:

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

микропрограмма или набор исходных микропрограмм управления работой операционного автомата (объекта);

система логических и запоминающих элементов;

критерии оценки качества разработки.

При проектировании универсального МПА решаются задачи:

оптимизация микропрограммы с учетом конкретных особенностей реализации МПА;

выбор способа кодирования МК;

определение структуры и формата МК;

размещение программы в ПЗУ – микропрограммирование;

построение логической схемы МПА.

1.3Классы микроопераций и способы их кодирования

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

Микрооперации, выполняемые ОА, подразделяют на следующие классы.

1.Микрооперация установки – присваивание слову значения константы.

2.Микрооперация инвертирования – обеспечение изменения значения слова на инверсное.

3.Микрооперация передачи – присваивание слову значения другого

слова.

4.Микрооперация сдвига – изменение положения разрядов слова по отношению к начальному.

5.Микрооперация счѐта – обеспечение изменения значения слова на единицу.

6.Микрооперация сложения – присваивание слову значение суммы слагаемых.

7.Бинарные логические микрооперации – присваивание слову значения,

получаемого поразрядным применением операций конъюнкции, дизъюнкции

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

8.Комбинированные микрооперации – это микрооперации, не принадле-

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

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

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

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

Кодирование микроопераций в микрокоманде может выполняться по одному из 3-х вариантов:

1)горизонтальное кодирование;

2)вертикальное (максимальное) кодирование;

3)смешанное кодирование.

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

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

nw = log2 M .

(1)

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

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

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

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

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

1.4 УА с принудительной адресацией

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