ЛАБОРАТОРНАЯ РАБОТА № 4 СИНТЕЗ УПРАВЛЯЮЩИХ АВТОМАТОВ С ЖЕСТКОЙ ЛОГИКОЙ 4.1. Цель работы Разработка графа микропрограммы вычислительной процедуры машинной операции для заданной системы микрокоманд. Синтез управляющего автомата для реализации микропрограммы. Функции операционного и управляющего автоматов Граф микропрограммы Вычислительное устройство с программным управлением всегда можно представить в виде композиции двух устройств - управляющего (УА) и операционного (ОА) автоматов (рис. 4.1). ОА состоит из регистров для приема и хранения информации, поступающей извне, и арифметико-логического устройства (АЛУ) для преобразования информации под действием управляющих микрокоманд Ym (m=1, ...,M) с одновременным формированием для управляющего блока признаков или осведомительных сигналов X={xk} (k=1, ...,K).
Рис. 4.1. Вычислительное устройство с программным управлением Алгоритм выполнения некоторой процедуры (операции) преобразования информации, представленный в форме последовательности микрокоманд, образует микропрограмму этой процедуры (операции). Исходными данными для синтеза УА являются: схема операционного автомата с функциями, определенными в виде списка реализуемых микрокоманд, и содержательная граф-схема алгоритма или, используя введенное выше определение, граф микропрограммы этой операции. На рис. 4.2,а представлена структурная схема операционного автомата, включающая АЛУ комбинационного типа с регистром флагов F, регистровое запоминающее устройство из 4 регистров общего назначения (РОН) и аккумулятора Асс, который наделен преимущественными функциями при выполнении арифметических и логических микрокоманд. В процессе выполнения каждой микрокоманды комбинационное АЛУ взаимодействует с регистрами, являющимися обычно источниками и приемниками операндов. С целью упрощения схемы мультиплексирования регистрового ЗУ с внутренней магистралью ОА выбран такой его вариант, когда один и тот же регистр ЗУ является как источником, так и приемником информации. Регистры РОН выполнены на обычных триггерах- защёлках, которые являются прозрачными для входных информационных сигналов при активном уровне синхросигнала СLK. С целью разрыва порочной петли «регистр РОН - комбинационное АЛУ - регистр РОН», введён специальный буферный регистр Z (один для всех) с противофазной (относительно регистров РОН) синхронизацией. Режимы работы и состояния основных узлов операционного устройства приведены в таблице 4.1. Таблица 4.1 Сигнал Режимы работы или состояния
СLK РОН Буфер Z Acc и F АЛУ
1
Хранение Переход в новое состояние (прозрачен для выходных сигналов РОН)
Хранение
Выполнение микрокоманды Ym
------
------ Переключение в новое состояние, запись результатов микрокоманды
------
0 Переключение в новое состояние, запись результатов микрокоманды
Хранение
Хранение
------
В табл. 4.2 приведены список микрокоманд, реализуемых ОА, их соответствие управляющим микрокомандам Ym, а также дополнительная информация по установке флагов по результатам каждой микрокоманды. Список включает 52 микрокоманды, которые можно разбить на 3 группы: микрокоманды пересылки, двоичной арифметики, логической обработки, сдвига и вращения. На основе данных микрокоманд и будет проводиться разработка графа микропрограммы. Граф микропрограммы представляет собой ориентированный граф, содержащий одну начальную, одну конечную и произвольное множество промежуточных вершин - операторных и условных. Операторная вершина соответствует одной микрокоманде, а условная - проверяемому логическому условию (флагу). При построении графа микропрограммы необходимо руководствоваться следующими правилами: Входы и выходы различных вершин соединяются дугами с указанием направления передачи информации. Каждый выход соединяется только с одним входом. Для любой вершины графа существует по крайней мере один путь из нее к конечной вершине. Рассмотрим пример на построение графа микропрограммы для задачи подсчета числа нулей в байте. В микропрограмме приняты следующие условия: Входные параметры: исследуемый байт находится в регистре R1, а с помощью регистра R4 организован счетчик цикла. Выходные параметры: результат (число нулей) помещается в аккумулятор Acc. Граф микропрограммы с необходимыми комментариями приведен на рис. 4.4. Исполнение микропрограммы начинается при выполнении логического условия ПУСК=1, которое реализуется воздействием на УА одноименным командным сигналом.
Рис. 4.2. Структура операционного (а) и управляющего (б) автоматов Имея в своем распоряжении граф микропрограммы можно приступить к синтезу управляющего автомата, оговорив предварительно его тип, а также некоторые ограничения в реализации подобных схем на лабораторном стенде УМ11М. Существуют два типа управляющих автоматов: УА с жесткой или схемной логикой. УА с логикой, хранимой в памяти (с программируемой логикой). В соответствии с целью данной работы ограничимся рассмотрением УА с жесткой логикой, функционирование которых задается , как правило, моделями автоматов Мили или Мура. Управление таким сложным объектом, каким является операционное устройство универсального назначения (рис.4.2,а), предо пределяет и сложную схему УА, что противоречит целям проведения лабораторного занятия.
Рис. 4.3. Временные диаграммы работы ОУ с управляющим автоматом типа Мили (а) и Мура (б) Список микрокоманд (МК), реализуемых в ОА Таблица 4.1 Выходной сигнал в УА Мнемокод МК Содержание Влияние на флаги F
Y1(Y4 MOV A, R (Acc) ( (R); (R): R1, R2, R3, R4
Y5(Y8 MOV R, A (R) ( (Acc) Не
Y9 MOV A, data 8 (Acc) ( data 8 влияет
Y10(Y13 MOV R, data 8 (R) ( data 8
Y14(Y17 ADD R (Acc) ( (Acc)+(R)
Y18(Y21 ADC R (Acc) ( (Acc)+(R)+CF Влияет
Y22(Y25 SUB R (Acc) ( (Acc)-(R) на все
Y26(Y29 SBB R (Acc) ( (Acc)-(R)-CF флаги
Y30, Y31 CMP R (Acc)-(R); (R): R1, R2
Y32, Y33 DEC R (R) ( (R)-1; (R): R3, R4 Влияет на все
Y34, Y35 INC R (R) ( (R)+1; (R): R3, R4 флаги, кроме CF
Y36(Y39 AND R (Acc) ( (Acc)((R) Влияет на все
Y40(Y43 OR R (Acc) ( (Acc)((R) флаги,
Y44(Y47 XOR R (Acc) ( (Acc)((R) OF=CF=0
Y48 RCL
Только на
Y49 RCR
флаг CF
Y50 SAR
Все флаги
Y51 SAL
Все флаги )*
Y52 CLC CF=0 CF=0
*) OF=1, если произошло изменение старшего бита Acc На рис. 4.2,б представлена одна из возможных декомпозиций УА, включающая три составные части: дешифратор кода вычислительной процедуры, собственно управляющий автомат, генерирующий последовательность управляющих сигналов для микрокоманды Ym, Таблица 4.2 Флаги условий CF ZF SF OF
сигналы условий {xk} x1 x2 x3 x4
Рис. 4.4. Граф микропрограммы подсчета числа нулей в байте и формирователь микроинструкций FM для управления отдельными узлами операционного устройства (точнее, настройки ОА на выполнение заданной микрокоманды Ym): . (4.1) Такой формирователь легче всего представить в виде памяти, содержание ячеек которой соответствует правой части соотношения (4.1). Адрес ячейки памяти определяется номером микрокоманды Ym. Объектом синтеза в лабораторной работе представляется среднее звено (рис. 4.2,б) применительно к реализации простых вычислительных процедур. 4.3. Синтез управляющего автомата Процесс синтеза схемы УА включает следующие этапы: [6] Кодированное представление графа микропрограммы или получение граф-схемы алгоритма (ГСА) работы УА. Разметка ГСА для определения состояний УА, функционирующего в соответствии с моделью автомата Мили (Мура). Построение графа автомата Мили (Мура). Составление структурной таблицы автомата и кодирование его состояний. Построение структурной схемы автомата. Построение комбинационной части автомата. Содержание данных этапов рассмотрим на примере графа микропрограммы рис. 4.4.
Рис. 4.5. ГСА работы УА (а) и соответствующий ей граф автомата Мили (б) 4.3.1. Граф-схема алгоритма (ГСА) ГСА определяет закон функционирования УА в процессе реализации микропрограммы в операционном устройстве. ГСА получается из графа микропрограммы путем замены микрокоманд, указанных в операторных вершинах, соответствующими им управляющими сигналами Ym (табл. 4.2), и замены флагов условий в условных вершинах соответствующими им сигналами xk из табл. 4.3 (сигнал ПУСК также относится к множеству X={xk}). Полученная таким образом ГСА представлена на рис. 4.5, a. 4.3.2. Интерпретация ГСА автоматами Мили и Мура Функционирование автомата Мили задается двумя функциями - функцией перехода и выхода (: ; . (4.2) где - множество состояний автомата; ; - начальное состояние автомата; - состояние (вектор) множества из управляющих сигналов в этот же момент времени. В каждый момент времени t это множество Y(t) представляется каким-либо одним сигналом Ym, инициирующим выполнение соответствующей микрокоманды. Необходимый набор состояний автомата определяется путем разметки ГСА по следующим правилам [Л. 6]: символом a1 отмечается вход вершины, следующей за начальной, а также вход конечной вершины; входы вершин, следующих за операторными, отмечаются символами a2,a3,...аm, при этом входам различных вершин даются различные символы. Если отметкам a1, ..., am (рис. 4.5,а) поставить в соответствие вершины графа и соединить их дугами, число и направление которых определяется всевозможными переходами между одноименными отметками ГСА, то получим граф автомата Мили (рис. 4.5,б). Каждый переход может включать произвольное число условных вершин, но не более одной операторной. Каждая дуга помечается символом xk (без инверсии, если путь проходит через выход условной вершины, отмеченный символом "1") и выходным сигналом Ym, если путь проходит через операторную вершину. Работа автомата по выполнению микропрограммы является циклической, поэтому рассмотрим его функционирование в течение одного машинного такта, совпадающего с одним тактом синхронизации сигнала СLK. Развертка ГСА по тактам исполнения с отметками автомата Мили приведена на рис. 4.6, а временная диаграмма работы – на рис. 4.3,а.
Рис. 4.6. Граф автомата Мура, интерпретирующий ГСА рис.4.5, а В начале машинного такта (положительный фронт сигнала СLK) автомат переходит в новое состояние A(i) и ,на основе выработанных в предыдущих тактах осведомительных сигналов X(i), формирует с некоторой задержкой микрокоманду Ym. Изменение состояния автомата в начале такта приведет и к изменению сигналов возбуждения триггеров ((i) памяти автомата, однако истинные значения сигналов возбуждения установятся в конце такта, когда в операционном устройстве будут установлены в регистре F новые значения признаков по результатам выполнения микрокоманды Ym (отрицательный фронт сигнала СLK). Регистр флагов F операционного устройства выполнен на триггерах с динамическим управлением, поэтому флаги условий X(i) остаются неизменными в течение времени исполнения микрокоманды, что является обязательным условием правильного (корректного) функционирования автомата Мили. ГСА может быть также интерпретирована и автоматом Мура, которому свойственен следующий закон функционирования: ; . (4.3) Поскольку в автомате Мура выходные сигналы связаны только с состояниями автомата, то каждой операторной вершине графа ГСА следует поставить в соответствие одно из состояний a2, a3, ... . Символом ai помечаются начальная и конечная вершины. На ГСА рис. 4.5,а символы состояний a1, ..., a8 обозначены цифрами 1, 2, ..., 8 в кружках при соответствующих вершинах. Граф автомата Мура, интерпретирующий ГСА рис. 4.5,а, представлен на рис. 4.7. В отличие от графа автомата Мили, в графе автомата Мура выходные сигналы помещаются внутри кружка вместе с состоянием aj. В общем случае автомат Мура имеет большее число состояний, чем автомат Мили, поэтому его реализация требует больших аппаратных затрат.
Рис. 4.7. Развертка ГСА по тактам исполнения Особенности взаимодействия управляющего автомата Мура с операционным устройством отражены на временной диаграмме рис. 4.3,б. 4.3.3. Кодирование состояний автомата Количество триггеров, требуемых для организации памяти управляющего автомата, определяется ближайшим сверху целым от двоичного логарифма числа состояний M, т.е.: . (4.4) Каждому состоянию aj (т.е. вершине графа автомата) должна соответствовать одна определенная комбинация значений Q1, ..., QR. Различают два подхода к кодированию состояний автомата: случайное и экономичное (существует еще понятие противогоночного кодирования, которое актуально для асинхронных автоматов и здесь не рассматривается). Экономичное кодирование, как правило, приводит к уменьшению сложности комбинационной части, которая формирует выходные сигналы управления и сигналы возбуждения элементов памяти автомата. Существует много способов экономичного кодирования, однако в большинстве случаев они весьма трудоемки в практическом использовании и требуют специальных знаний из области теории графов и автоматов [6]. Характерной особенностью этих методов является стремление минимизировать либо число переключений элементов памяти на всех переходах графа автомата, либо обеспечить условия, при которых каждое изменение состояния автомата вызывалось бы действием как можно меньшего числа сигналов возбуждения элементов памяти. Из простых способов, относящихся к классу экономичного кодирования, отметим два: способ соседнего кодирования и кодирование с ослабленной зависимостью от входных сигналов [Л. 6,7]. При соседнем кодировании любые два смежных состояния в графе автомата кодируются наборами Q1, ..., QR, отличающимися состояниями лишь одного элемента (в теории кодирования такие кодовые комбинации характеризуются минимальным кодовым расстоянием d=1). Обычно для реализации соседнего кодирования граф автомата накладывают на карту Карно соответствующего ранга, как это показано на рис. 4.8 применительно к графу рис. 4.5, б. Рис. 4.8. Применение соседнего кодирования для состояний графа автомата Мили рис.4.5,б (переход «3(4» не удовлетворяет требованиям соседнего кодирования) Соседнее кодирование, требования к которому сформулированы в работе [6], не всегда возможно. На рис. 4.9 показаны два графа, не допускающие соседнего кодирования. Кодирование с ослабленной зависимостью от входных переменных группы X={xk} предусматривает размещение подмножества состояний автомата A(am), образованного всевозможными переходами из состояния am , расположение в одном столбце или строке карт Карно. Рис. 4.9 Графы, не допускающие соседнее кодирование Рис. 4.10. Комбинированный способ кодирования состояний автомата Мура, изображенного на рис. 4.7 На рис. 4.10 показан один из возможных вариантов использования данного способа для автомата Мура. Здесь подмножество A(a5)((6,7) и A(a7)((5,8) расположены в одной строке. Остальные переходы удовлетворяют соседнему кодированию. 4.3.4. Составление структурной таблицы автомата Структурная таблица автомата представляет собой граф структурного (в отличие от абстрактного) автомата, заданный в виде списка. В табл. 4.4 приведена прямая структурная таблица автомата Мили, построенная на основе графа рис. 4.5,б с кодировкой состояний на рис. 4.8. В качестве элемента памяти выбран синхронный RS- триггер. Табл. 4.4 носит название прямой структурной таблицы, в которой в графе ИСХОДНЫЕ СОСТОЯНИЯ перечисляются все состояния автомата, начиная с первого (в обратной таблице указанное последовательное перечисление состояний производится в графе СОСТОЯНИЯ ПЕРЕХОДОВ). Переход автомата из состояния am в aS контролируется частной функцией перехода Fi(am,aS)=amX(am,aS), которая и определяет значения выходных сигналов Yi и функций возбуждения для i-го перехода. Аналитические выражения для определения функций Yi и (i записываются на основе объединения по ИЛИ соответствующих функций переходов (в данной таблице отсутствуют одинаковые выходные сигналы для разных функций перехода). Таблица 4.3 № перехода Исходные состояния Состояния переходов Функции перехо-дов Выход-ные сигналы Сигналы возбужде-ния
am Q1 Q2 Q3 aS Q1 Q2 Q3 Fi(am, aS) Yi(am, aS) (i(am, aS)
В табл. 4.5 приведен список выражений для искомых функций. Прямая структурная таблица автомата Мура подобна табл. 4.4 за тем лишь исключением, что в ней будет отсутствовать столбец ВЫХОДНЫЕ СИГНАЛЫ Yi(am,aS), которые войдут в расширенный столбец ИСХОДНЫЕ СОСТОЯНИЯ с обозначением am/Yi, так.как. для автомата Мура выходной сигнал есть функция только состояния (см. выражение (4.3)). 4.3.5. Построение схемы управляющего автомата Структурная схема управляющего автомата Мили включает три составные части (рис. 4.11): регистр состояний (состоит из триггеров, которые были выбраны перед составлением структурной таблицы), дешифратор состояний и комбинационная часть, предназначенная для реализации выражений для выходных сигналов управления и сигналов возбуждения (табл. 4.5). Схема управляющего автомата Мура отличается от схемы рис. 4.11 тем, что ее комбинационная часть как бы содержит две половины (рис. 4.12): КС-( и КС-Y (иногда последняя вырождается просто в схему трансляции выходов дешифратора состояний). Рис. 4.11 Структурная схема управляющего автомата Мили Замечание. В связи с выбранным принципом взаимодействия управляющего и операционного автоматов, триггеры, которые используются в УА, должны тактироваться положительным фронтом синхросигнала СLK, в противном случае сигнал СLK, поступающий на УА, должен предварительно инвертироваться. 4.4. Подготовка к работе, выполнение и содержание отчета Ознакомиться с содержанием лабораторной работы и индивидуальным заданием к ней. В соответствии с индивидуальным заданием выполнить следующие этапы синтеза управляющего автомата: разработать граф микропрограммы вычислительной процедуры; построить ГСА работы управляющего автомата и соответствующий ему граф автомата Мили (Мура); произвести кодирование состояний автомата и составить структурную таблицу; определить логические выражения для выходных сигналов управления и сигналов возбуждения триггера; построить структурную схему автомата. 3. Преобразовать логические выражения для комбинационной части автомата к виду, соответствующему выбранному типу логических элементов. 4. Построить схему управляющего автомата.
Рис. 4.12 Структурная схема управляющего автомата Мура 5. Собрать схему автомата и произвести ее исследование на предмет правильности интерпретации автоматом граф- схемы алгоритма ГСА. Результатом исследования должна стать временная диаграмма, интерпретирующая ГСА в тактах управляющего автомата для нескольких комбинаций признаков из множества X, как это показано на рис. 4.13. Отчет должен содержать этапы синтеза УА, его схему и временные диаграммы исследования его работы.
Рис. 4.13 Временная диаграмма интерпретации ГСА рис.4.5,а автоматом Мили 4.5. Индивидуальные задания к работе Индивидуальное задания к работе определяется функцией, микропрограмму выполнения которой надо реализовать на рассмотренном операционном устройстве (рис. 4.2) под управлением спроектированного управляющего автомата. Считать, что операнды функции находятся в регистрах РОН, а результат вычислений помещается в аккумулятор. *) ПОЯСНЕНИЯ к заданию 2 и 3: В регистрах РОН находятся маски D и T, выбранные следующим образом: маска D предназначена для селективного сброса битов в тех разрядах регистра РОН с вектором входных переменных X={x7, x6, ..., x0}, номера которых соответствуют отсутствующим переменным в исходном терме; Таблица 4.5 № задания Функция или процедура Тип триггера Тип автомата
1 2
T D Мили
3 4 )* T D Мура
5 6 )* T D Мили
7 8 Подсчитать число «1» в байте D Мура
9 10
D Мили
11 12
D Мура
маска Т включает «1» в позициях, которые соответствуют переменным без инверсии в исходном терме и «0» в остальных позициях. Процедура вычисления заканчивается проверкой соотношения:
В задании 3 маска D выбирается так же, а маска T включает «1» в позициях, соответствующих инверсным переменным, а в остальных - нули. Процедура заканчивается проверкой соотношения:
ЛИТЕРАТУРА 1. Каган Б.М. Электронные вычислительные машины и системы: Учебное пособие для вузов. – М.: Энергоатомиздат, 1991.-592 с: ил. 2. Угрюмов Е. П. Проектирование элементов и узлов ЭВМ: Учеб. пособие для вузов. – М.: Высшая Школа, 1987.-318 с.: ил. 3. Потемкин И. С. Функциональные узлы цифровой автоматики. – М.: Энергоатомиздат, 1988.-320 с.: ил. 4. Зельдин Е. А. Цифровые интегральные микросхемы в информационно-измерительной аппаратуре. – Л.: Энергоатомиздат, 1986.-280 с.: ил. 5. Пухальский Г.И., Новосельцева Т. Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. -М.: Радио и связь, 1990.-304 с.: ил. 6. Цифровые ЭВМ: Практикум / К.Г.Самофалов, В.И.Корнейчук, В.П.Тарасенко; Под общ. ред. К.Г.Самофалова. - К.: Выща шк.,1990.-225с.:Ил Скляров В. А. Синтез автоматов на матричных БИС / Под. Ред. С. И. Баранова. – Минск: Наука и техника, 1984.-288 с.: ил. 8. . Угрюмов Е. П. Цифровая схемотехника.- СПб.: БХВ – Санкт-Петербург, 2000. – 528 с.: ил. Работа подготовил доцент кафедры ВТ НГТУ В. А. Афанасьев. Редакция 2002г.
