Лекции по программированию

 

 _УПРАВЛЯЮЩИЕ АВТОМАТЫ.
 _ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД
Начнем с рассмотрения простейшего варианта управления, в
котором не участвуют предикатные функции (переменные), т.е. в
микропрограмме переходы только безусловные. В таком случае УА
является автономным синхронным автоматом.
В более общем случае функция переходов УА зависит от
предикатных переменных, но УА должен быть автоматом Мура.
Условимся о некоторых ограничениях, позволяющих упрос-
тить схему на начальных этапах проектирования (от которых
легко впоследствии и отказаться):
- на каждом шаге процесса вычислений ветвление может осу-
ществляться только по одной двузначной предикатной перемен-
ной (т.е. разветвление возможно лишь на два направления);
- начальные значения всех регистров УА являются нулевыми.
Впредь на схемах УА не будем показывать цепей установки на-
чальных значений.
Для реализации в самом общем случае микропрограмм произ-
вольной структуры будем строить УА так, чтобы основным мате-
риальным носителем управляющей (автоматной) компоненты мик-
ропрограммы являлась бы управляющая память (реализованная,
например, в виде ПЗУ). В этом случае структура слова управля-
ющей памяти - МИКРОИНСТРУКЦИЯ - состоит из двух составных
частей: микрокоманды и адресной части.
Адресная часть микроинструкции содержит информацию, поз-
воляющую в следующем такте работы выбрать ( указать ) новый
адрес управляющей памяти. Реализация именно этого момента яв-
ляется основным предметом дальнейшего рассмотрения и опреде-
ляет, в основном, структуру, объем аппаратуры и быстродей-
ствие УА. При этом подлежит рассмотрению реализация следующих
типов переходов как между шагами алгоритма, так, соот-
ветственно, и между микроинструкциями:
- безусловный переход,
- условный переход,
- функциональный переход,
- переход к микроподпрограмме с возвратом.
Будем изучать работу управляющих автоматов различной
структуры, демонстрирующие основные применяемые варианты ад-
ресации микроинструкций, на следующем алгоритме:
- 2 -
---
----¬¦
¦ -VV-¬
n1¦ ¦m1 ¦ n1 { m1 }
¦ L-T--
¦ --V-¬ n2 { m2 }
n2¦ ¦m2 ¦
¦ L-T-- g1 <<GO(a;g1,n3)>>
¦ ¦<--¬
¦ -V¬ 0¦ n3 { m3 }
g1¦ < a >--
¦ LT- n4 { m4 }
¦ 1¦<----¬
¦ ¦----¬¦ g2 <<GO((a,b);n5,n3,n1,n1)>>
¦ --VV¬ ¦¦
n3¦ ¦m3 ¦ ¦¦ n5 { m5 }
¦ L-T-- ¦¦
¦ --V-¬ ¦¦ g3 <<GO(a;n5,n3)>>
n4¦ ¦m4 ¦ ¦¦
¦ L-T-- ¦¦
¦10 -V¬ 01¦¦
g2L--< ab>---¦
11 LT- ¦
00¦----¬¦
--VV¬ ¦¦
n5 ¦m5 ¦ ¦¦
L-T-- ¦¦
-V¬ 0 ¦¦
g3 < a >---¦
LT- 1 ¦
L------
Укажем на некоторые особенности этого алгоритма: Опера-
тор перехода (предикатная вершина), помеченный меткой g1,
называют ждущим. Оператор, помеченный меткой g2, использует
для перехода 4-значный предикат, что не удовлeтворяет выше-
указанному ограничению. Поэтому потребуются эквивалентные
преобразования алгоритма для того, чтобы удовлетворить этому
ограничению.
Алогоритмы эквмвалентны, если они преобразуют информа-
цию одинаковым образом. Наиболее распространенным приемом эк-
вивалентного преобразования алгоритмов и микропрограмм явля-
ется включение микроблоков и, соответственно, тактов, в кото-
рых не выполняется модификация памяти ОА - "нет операции".
Но и это преобразование может быть не эквивалентным - см.при-
мер при определении понятия "микроблок"; кроме того, следует
учесть различное поведение во времени предикатных переменных
типа "РА" и "РВ" - см. раздел "Взаимодействие ОА и УА".
( Запретить модификацию памяти можно, вводя условную
синхронизацию ОА, но для этого должна быть изменена микроко-
манда, предшествующая добавляемому такту.)
- 3 -
 _СХЕМА С АДРЕСНЫМ ПЗУ
Начнем рассмотрение с управляющего автомата, структура
которого совпадает с канонической структурой автомата Мура.
----¬ ----¬ -T--T¬ ----¬
¦MUX¦ q ¦ROM¦ ¦¦RG¦¦ ¦ROM¦
a->+0 +-->+ ¦ S' ¦¦ ¦¦ S ¦ ¦ Y
b->+1 ¦ ¦ ¦===>¦¦ ¦¦=T>¦ ¦==>
¦ ¦ г>¦ ¦ ¦¦ ¦¦ ¦ ¦ +-¬
¦А ¦ ¦ ¦ 2 ¦ C¦¦ ¦¦ ¦ ¦ 1 ¦ ¦
LA--- ¦ L---- -/++--+- ¦ L---- ¦
¦ H L=================- ¦
L-------------------------------
Функцию перехода и функцию выхода реализуем в виде ПЗУ.
В литературе, рассматривающей микропрограммные устройства уп-
равления, УА с такой структурой называют микропрограммным ав-
томатом Уилкса.
В ПЗУ (ROM_1), реализующем функцию выхода, следует раз-
местить микрокоманды; при этом их распределение по определен-
ным адресам совершенно произвольно, за исключением начальной
микрокоманды, которая в силу вышеуказанного ограничения дол-
жна располагаться по нулевому адресу.
ПЗУ (ROM_2), реализующее функцию переходов автомата,
можно трактовать как адресное ПЗУ. Ячеек в адресном ПЗУ в два
раза больше, чем в ПЗУ микрокоманд. Каждой ячейке ПЗУ микро-
команд соответствуют две ячейки в адресном ПЗУ, в которых за-
писываются два альтернативных адреса.
n1 { m1 } S¦ Y H¦ S q¦S'¦
-+----+ ---+--+
n2 { m2 } 0¦m1 x¦ 0 0¦ 1¦
¦ ¦ 0 1¦ 1¦
<<GO(a;d1,n3)>> ¦ ¦ ¦ ¦
1¦m2 0¦ 1 0¦ 2¦
d1 { m0 } ¦ ¦ 1 1¦ 3¦
¦ ¦ ¦ ¦
<<GO(a;d1,n3)>> 2¦m0 0¦ 2 0¦ 2¦
¦ ¦ 2 1¦ 3¦
n3 { m3 } ¦ ¦ ¦ ¦
3¦m3 x¦ 3 0¦ 4¦
n4 { m4 } ¦ ¦ 3 1¦ 4¦
¦ ¦ ¦ ¦
<<GO(a;d2,n1)>> 4¦m4 0¦ 4 0¦ 5¦
¦ ¦ 4 1¦ 0¦
d2 { m0 } ¦ ¦ ¦ ¦
5¦m0 1¦ 5 0¦ 6¦
<<GO(b;n5,n3)>> ¦ ¦ 5 1¦ 4¦
¦ ¦ ¦ ¦
n5 { m5 } 6¦m6 0¦ 6 0¦ 6¦
¦ ¦ 6 1¦ 4¦
<<GO(a;n5,n3)>> -+----- ---+---
Конвейерный вариант схемы с таким же способом адресации
должен программироваться с учетом замечаний, сделанных в раз-
деле "Взаимодействие ОА и УА". Кроме того, ограничения на
расположение микрокоманд в ROM_1 выглядят несколько иначе: по
0-адресу в ROM_1 можно расположить микрокоманду, после кото-
рой безусловно выполняется начальная микрокоманда.
- 4 -
----¬ q ----¬ ----¬ -T--T¬
¦MUX+---------->+ROM¦ ¦ROM¦Y ¦¦RG¦¦ Y'
a->+0 ¦ C ¦ ¦ S ¦ ¦==>¦¦ ¦¦==>
b->+1 ¦ -/TT--T¬ ¦ ¦=T>¦ ¦H ¦¦ ¦¦
¦ ¦ г>¦¦RG¦¦=>¦ ¦ ¦ ¦ +-->+¦ ¦+¬
¦А ¦ ¦ ¦¦ ¦¦S'¦ 2 ¦ ¦ ¦ 1 ¦ C¦¦ ¦¦¦
LA--- ¦ L+--+- L---- ¦ L---- -/++--+-¦
¦H' L===============- ¦
L-------------------------------------
 _СХЕМА С ЯВНЫМ УКАЗАНИЕМ АЛЬТЕРНАТИВНЫХ АДРЕСОВ
г===========================¬
¦г=========================¬¦
¦¦ ----¬ -T--T¬ ----¬A0¦¦
¦¦ ¦MUX¦ ¦¦RG¦¦ ¦ROM¦==-¦
¦L>¦0 ¦ ¦¦ ¦¦A ¦ ¦A1 ¦
----¬L=>¦1 ¦===>¦¦ ¦¦=>¦ ¦===-
¦MUX¦ ¦ ¦ ¦¦ ¦¦ ¦ ¦==>Y
a->+0 ¦ ¦А ¦ C¦¦ ¦¦ ¦ +¬
b->+1 ¦ LA--- -/++--+- L----¦H
¦А +----- ¦
LA--- ¦
L-----------------------------
Конвейерный вариант
г============================¬
¦г==========================¬¦
¦¦ ----¬ -----¬A0 -T--T¬A0'¦¦
¦¦ ¦MUX¦ ¦ROM ¦==>¦¦RG¦¦===-¦
¦¦ ¦ ¦ ¦ ¦A1 ¦¦ ¦¦A1' ¦
¦L>¦0 ¦A ¦ ¦==>¦¦ ¦¦====-
----¬L=>¦1 ¦=>¦ ¦ Y ¦¦ ¦¦ Y'
¦MUX¦ ¦ ¦ ¦ ¦==>¦¦ ¦¦==>
¦ ¦ ¦ ¦ ¦ ¦ H ¦¦ ¦¦
a->+0 ¦ ¦А ¦ ¦ +-->+¦ ¦+¬H'
b->+1 ¦ LA--- L----- -/++--+-¦
¦А +----- C ¦
LA--- ¦
L-----------------------------
Эта схема отличается от предыдущей тем, что, по сущес-
тву, тот же способ адресации выполнен с использованием только
одного ПЗУ. В этом варианте альтернативные адреса записывают-
ся в той же микроинструкции, что и микрокоманда.
n1 { m1 } A¦ Y H A0 A1¦
-+----------+
n2 { m2 } 0¦m1 x 1 1¦
¦ ¦
<<GO(a;d1,n3)>> 1¦m2 0 2 3¦
¦ ¦
d1 { m0 } 2¦m0 0 2 3¦
¦ ¦
<<GO(a;d1,n3)>> 3¦m3 x 4 4¦
¦ ¦
n3 { m3 } 4¦m4 0 5 0¦
¦ ¦
n4 { m4 } 5¦m0 1 6 4¦
¦ ¦
<<GO(a;d2,n1)>> 6¦m5 0 6 4¦
-+-----------
d2 { m0 }
- 5 -
<<GO(b;n5,n3)>>
n5 { m5 }
<<GO(a;n5,n3)>>
 _СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ АДРЕСА
Последовательный вариант Конвейерный вариант
-------------------------¬ --------------------------¬
¦ ----¬ -T--T¬ ----¬¦e ¦ ----¬ ----¬ e -T--T¬¦
¦ ¦MUX¦ q ¦¦RG¦¦q'¦ROM+- ¦ ¦MUX¦ q'¦ROM+---->+¦RG¦+-
L>+0 +---->+¦ ¦+->+ ¦ Y L>+0 +-->+ ¦ Y ¦¦ ¦¦Y'
a->+1 ¦ S ¦¦ ¦¦S'¦ ¦==> a->+1 ¦ S'¦ ¦====>¦¦ ¦¦=>
b->+2 ¦ г==>¦¦ ¦¦=>¦ ¦==¬ b->+2 ¦ г>¦ ¦ H ¦¦ ¦¦
¦А ¦ ¦ C¦¦ ¦¦ ¦ ¦¬ ¦ ¦ ¦ ¦ ¦ +---->+¦ ¦¦=¬
LA--- ¦ -/++--+- L----¦ ¦ ¦ ¦ ¦ ¦ ¦ S ¦¦ ¦¦ ¦
¦ H L================- ¦ ¦А ¦ ¦ ¦ ¦====>¦¦ ¦¦¬¦
L=======================- LA--- ¦ L---- -/++--+-¦¦
¦ H' ¦ C ¦¦
¦ L=================-¦
L=======================-
При этом способе адресации альтернативные адреса отлича-
ются только одним разрядом ( в данном варианте - младшим ),
формируемым входным сигналом. Остальные разряды адреса указы-
ваются вместе с микрокомандой в одной и той же микроинструк-
ции. При безусловном переходе в данном варианте схемы младший
разряд также указывается в микроинструкции. При адресации
одного и того же микроблока различными операторами условного
перехода может возникнуть КОНФЛИКТ АДРЕСАЦИИ. В этом случае
одну и ту же микроинструкцию приходится располагать в различ-
ных ячейках управляющей памяти. Если различные операторы ус-
ловного перехода одними и теми же предикатными значениями
указывают на одни и те же микроблоки, то нет и конфликта ад-
ресации.
Адрес
n1 { m1 } --(0,0),(2,1) S'q'¦ Y H S e¦
----+--------+
n2 { m2 } --(4,0) 0 0 ¦m1 0 4 0¦
¦ ¦
<<GO(a;d1,n3)>>-- 1,x 0 1 ¦m4 1 2 x¦
¦ ¦
d1 { m0 } --(1,0) 1 0 ¦m0 1 1 x¦
¦ ¦
<<GO(a;d1,n3)>>-- 1,x 1 1 ¦m3 0 0 1¦
¦ ¦
n3 { m3 } --(1,1),(3,1) 2 0 ¦m0 2 3 x¦
¦ ¦
n4 { m4 } --(0,1) 2 1 ¦m1 0 4 0¦
¦ ¦
<<GO(a;d2,n1)>>-- 2,x 3 0 ¦m5 1 3 x¦
¦ ¦
d2 { m0 } --(2,0) 3 1 ¦m3 0 0 1¦
¦ ¦
<<GO(b;n5,n3)>>-- 3,x 4 0 ¦m2 1 1 x¦
¦ ¦
n5 { m5 } --(3,0) ----+---------
<<GO(a;n5,n3)>>-- 3,x
Распределять микроинструкции по ячейкам памяти удобно
в следующем порядке:
- 6 -
- связать с различными операторами условного перехода, кон-
фликтующими между собой по адресации, различающиеся между со-
бой старшие разряды адреса;
- распределить микроблоки по ячейкам памяти с учетом назнач-
енных старших разрядов адреса и входных значений;
- оставшимся нераспределенным микроблокам назначить произ-
вольные свободные адреса.
 _СХЕМА С СОКРАЩЕННЫМ ТАКТОМ
Использование этой схемы позволяет при сохранении пре-
имуществ последовательного варианта взаимодействия сократить
наиболее длинные цепи, общие для ОА и УА, до длины цепей кон-
вейерного варианта.
-----------------------------------¬ --T----------T
¦ г==========================¬¦ ROM_0 A'¦ Y H A e¦
¦ ¦ -----¬ ¦¦ --+----------+
¦ ¦ ¦ROM ¦=+A ¦¦ 0 ¦m1 0 4 0¦
¦ ¦ ¦ +-+e ¦¦ 1 ¦m0 1 1 x¦
¦ ¦>¦ ¦=+Y ----¬ -T--T¬¦¦ 2 ¦m0 2 3 x¦
¦ ¦ ¦ ¦=+H ¦MUX¦ ¦¦RG¦¦-¦ 3 ¦m5 1 3 x¦
¦ ¦ ¦ 0 ¦ L==>¦0 ¦ ¦¦ ¦+--e' 4 ¦m2 1 1 x¦
¦ A'¦ +----+ ¦ ¦ ¦¦ ¦¦ --+-----------
¦ ¦ ¦ROM ¦=+A ¦ ¦==>¦¦ ¦¦==>Y' --T----------T
¦ ----¬¦ ¦ ¦ ¦==>¦1 ¦ ¦¦ ¦¦ ROM_1 A'¦ Y H A e¦
¦ ¦MUX¦L>¦ +-+e ¦А ¦ C¦¦ ¦¦¬H' --+----------+
L>+0 ¦ ¦ ¦=+Y LA--- -/++--+-¦ 0 ¦m4 1 2 x¦
a>+1 ¦ ¦ 1 ¦=+H ¦ ¦ 1 ¦m3 0 0 1¦
b>+2 ¦ L----- ¦ ¦ 2 ¦m1 0 4 0¦
¦А +--------------- ¦ 3 ¦m3 0 0 1¦
LA--- ¦ --+----------+
L==============================-
Способ адресации, по существу, такой же, как и в преды-
дущей схеме. Только в рассматриваемой схеме входной сигнал
управляет выбором одного из двух блоков ПЗУ (можно интерпре-
тировать этот сигнал как старший разряд адреса).
 _СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ
----¬ ---¬ 0W- +1
¦MUX+->+M2+--¬ 1W- загрузка
0->+0 ¦->+ ¦ -VTT--T¬ ----¬ Y
a->+1 ¦¦ L--- W¦¦CT¦¦ ¦ROM¦==>
b->+2 ¦¦ ¦¦ ¦¦ ¦ ¦H
¦ ¦¦ ¦¦ ¦¦A ¦ ¦====¬
¦А ¦¦ г==>¦¦ ¦¦=>¦ ¦e ¦
LA---¦ ¦ ¦¦ ¦¦ ¦ +--¬ ¦
¦ ¦ ¦ C¦¦ ¦¦ ¦ ¦=¬¦ ¦
¦ ¦ ¦ -/++--+- L----S¦¦ ¦
¦ ¦ L=================-¦ ¦
¦ L------------------------ ¦
L=============================-
В этой схеме при разветвлении процесса вычислений пара
альтернативных адресов получается следующим образом: один ад-
рес всегда на единицу больше, чем текущий ( т.е. изменяется
"регулярным" образом ), второй адрес - произвольный и содер-
жится вместе с микрокомандой в микроинструкции.
Элементом, "вычисляющим" адрес, является счетчмк, управ-
ляемый сигналом, являющимся входным для УА. При различных
значениях входного сигнала счетчик выполняет две функции: ли-
бо прибавляет единицу к значению, которое хранилось в счетчи-
ке и являлось текущим адресом, либо загружается значением ад-
реса из управляющей памяти.
- 7 -
В схему введен элемент М2, позволяющий инвертировать
значение входного сигнала, что облегчает распределение микро-
инструкций по ячейкам управляющей памяти.
Адрес
n1 { m1 } -- 0 A ¦ Y H e S¦
--+-----------+
n2 { m2 } -- 1 0 ¦m1 x x 1¦
¦ ¦
<<GO(a;d1,n3)>> 1 ¦m2 1 0 3¦
¦ ¦
d1 { m0 } -- 2 2 ¦m0 1 1 2¦
¦ ¦
<<GO(a;d1,n3)>> 3 ¦m3 x x 4¦
¦ ¦
n3 { m3 } -- 3 4 ¦m4 1 0 0¦
¦ ¦
n4 { m4 } -- 4 5 ¦m0 2 0 3¦
¦ ¦
<<GO(a;d2,n1)>> 6 ¦m5 1 1 6¦
¦ ¦
d2 { m0 } -- 5 7 ¦m0 0 1 3¦
--+------------
<<GO(b;n5,n3)>>
n5 { m5 } -- 6
<<GO(a;n5,n3)>>
В схеме для конвейерного варианта взаимодействия регу-
лярное изменение адреса приходится организовывать так, чтобы
не увеличивать число мест конвейера.
г==============================¬
¦г=====================¬ ¦
¦¦ -T--T¬ ----¬¦ ----¬S¦
¦¦ ----¬ ¦¦RG¦¦ ¦MUX¦¦ ¦ROM¦=-
¦L=>¦INC¦=>¦¦ ¦¦>¦0 ¦¦ ¦ ¦Y -T--T¬Y'
¦ L---- C¦¦ ¦¦ ¦ ¦¦ ¦ ¦==>¦¦RG¦¦==>
¦ -/++--+- ¦ ¦¦>¦ ¦ ¦¦ ¦¦
¦ -/TT--T¬ ¦ ¦A ¦ ¦H ¦¦ ¦¦H'
¦ C¦¦RG¦¦ ¦ ¦ ¦ ¦==>¦¦ ¦¦==¬
L=========>¦¦ ¦¦>¦1 ¦ ¦ ¦e ¦¦ ¦¦e'¦
¦¦ ¦¦ ¦А ¦ ¦ +-->+¦ ¦+¬ ¦
----¬ L+--+- LA--- L---- -/++--+-¦ ¦
¦MUX¦ ---¬ ¦ C ¦ ¦
0->+0 +->+M2+----- ¦ ¦
a->+1 ¦->+ ¦ ¦ ¦
b->+2 ¦¦ L--- ¦ ¦
¦А ¦¦ ¦ ¦
LA---L------------------------------ ¦
L===================================-
- 8 -
 _СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И
 _СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ
г============================¬ C
¦г===================¬ ¦ -/TT--T¬H'
¦¦ -T--T¬ ----¬¦ ----¬ ¦ г==>¦¦RG¦¦==¬
¦¦ ----¬ ¦¦RG¦¦ ¦MUX¦¦ ¦ROM¦ ¦ ¦ ->+¦ ¦+-¬¦
¦L>¦INC¦>¦¦ ¦¦>¦0 ¦¦ ¦ ¦S¦H¦e¦ L+--+- ¦¦
¦ L----C¦¦ ¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ -T--T¬Y¦¦ для RG"Y"
¦ -/++--+- ¦ ¦¦>¦ ¦------>¦¦RG¦¦>¦¦
¦ -/TT--T¬ ¦ ¦A ¦ ¦ w c¦¦ ¦¦ ¦¦ 0w-загрузка
¦ C¦¦RG¦¦ ¦ ¦ ¦ ¦ -A-/++--+- ¦¦
L=======>¦¦ ¦¦>¦1 ¦ ¦ ¦k ¦ -T-T¬k'¦¦ 1w-нет загрузки
¦¦ ¦¦ ¦ А ¦ ¦ +----+->+¦T¦+¬ ¦¦
----¬ L+--+- L-A-- L---- -/++-+-¦ ¦¦ k ----¬
¦MUX¦ ---¬ --¬¦ C ¦ ¦¦ L----+ 1 +- CC
0>+0 +->+M2+->+&+- ¦ ¦¦ -----+ ¦
a>+1 ¦->+ ¦->+ ¦ ¦ ¦¦ SYN L----
b>+2 ¦¦ L---¦ L-- ¦ ¦¦
¦А ¦¦e' L--------------------------- ¦¦ где CC -
LA---L-----------------------------------¦ синхронизация ОА
L=======================================-
Эта схема используется только в конвейерном варианте
взаимодействия. Метод вычисления адреса для следующего такта
такой же, как и в схеме с регулярной адресацией. (Другой тер-
мин -"естественный" - употреблен только ради различения самих
схем.) Но в этой схеме, по сравнению с уже рассмотренными,
разряд управляющей памяти с одним и тем же номером (разрядный
срез) в различных микроинструкциях может быть использован
различным образом. Будем различать микроинструкции двух ти-
пов:
- операционные,
- алресации (выбора).
В лданном варианте схемы тип микроинструкции устанавли-
вается разрядом с именем "k". При k=0 выполняется микро-
инструкция операционного типа. Все остальные разряды ячейки
загружаются в регистр микрокоманды и управляют выполнением
микроопераций в ОА. Следующий адрес всегда на единицу больше.
При k=1 выполняется микроинструкция адресации. Все
разряды микроинструкции могут быть использованы для вычисле-
ния следующего адреса. В данном варианте схемы, так же как и
в схеме с регулярной адресацией, один из адресов явно записы-
вается в микроинструкцию, другой альтернативный адрес на еди-
ницу больше текущего.
Адрес A ¦k¦ Y ¦
n1 { m1 } -- 0 ¦ ¦ H¦ e¦ S¦
--¦-+--+--+--+
n2 { m2 } -- 1 0 ¦0¦ m1 ¦
1 ¦0¦ m2 ¦
g1 <<GO(a;g1,n3)>>-- 2 --¦-+--T--T--+
2 ¦1¦ 1¦ 1¦ 2¦
n3 { m3 } -- 3 --¦-+--+--+--+
3 ¦0¦ m3 ¦
n4 { m4 } -- 4 4 ¦0¦ m4 ¦
--¦-+--T--T--+
g2 <<GO(a;g3,n1)>>-- 5 5 ¦1¦ 1¦ 0¦ 0¦
6 ¦1¦ 2¦ 0¦ 3¦
g3 <<GO(b;n5,n3)>>-- 6 --¦-+--+--+--+
7 ¦0¦ m5 ¦
n5 { m5 } -- 7 --¦-+--T--T--+
8 ¦1¦ 1¦ 1¦ 7¦
g4 <<GO(a;n5,n3)>>-- 8 9 ¦1¦ 0¦ 1¦ 3¦
Вместе с этой схемой обычно используется условная син-
хронизация, которая позволяет удлинить такт выполнения микро-
- 9 -
команды в ОА на время выполнения микроинструкций адресации.
SYN -----------¬ -----------¬ -----------¬ -----------¬ -----
L-- L-- L-- L-- L--
| | | | |
k 0 -------- 0 ---------------------------------- 0 ---
--------------------------- 1 -------- 1 ----------------
| | | | |
CC¬ -----------¬ -------------------------------------¬ -----
L-- L-- L--
| | | | |
Y------------------------------------------------------------
-------------------------------------------------------------
 _ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД.
 _ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ
Функциональный переход
При необходимости выполнения нескольких вычислительныых
функций, управление которыми представляется в виде независи-
мых микропрограмм, необходимо организовать независимый вызов
этих микропрограмм.
Начальные адреса микропрограмм, управляющих вычислениями
различных функций, обычно существуют вне управляющей памяти.
В УА достаточно предусмотреть механизм коммутации, позволя-
ющий сделать начальный адрес текущим. Это можно осуществить в
любой из рассмотренных схем. (К механизму коммутации относят-
ся, кроме аппаратуры, специальные разряды управляющей памяти
и специальные микроинструкции.)
- 10 -
г======================¬ C
г======¦==============¬ ¦ -/ TT--T¬H'
¦ ¦ ----¬¦ ----¬ ¦ г==>¦¦RG¦¦==¬
¦ ¦ ¦MUX¦¦ ¦ROM¦ ¦ ¦ ->+¦ ¦+-¬¦
F =¦======¦========>¦0 ¦¦ ¦ ¦ ¦ ¦ ¦ L+--+- ¦¦
¦ ¦ -T--T¬ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
¦ ¦ ¦¦RG¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
¦ L>¦¦ ¦¦=>¦1 ¦¦ ¦ ¦S¦H¦e¦ ¦¦
¦ C¦¦ ¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ -T--T¬Y¦¦ для RG"Y"
¦ -/++--+- ¦ ¦¦>¦ ¦------>¦¦RG¦¦>¦¦
¦ -T--T¬ ¦ ¦A ¦ ¦ ¦¦ ¦¦ ¦¦ 0w-загрузка
¦ ----¬ ¦¦RG¦¦ ¦ ¦ ¦ ¦ w c¦¦ ¦¦ ¦¦
L>¦INC¦=>¦¦ ¦¦T>¦2 ¦ ¦ ¦ -A-/++--+- ¦¦ 1w-нет загр.
L---- C¦¦ ¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
-/++--+-¦ ¦ ¦ ¦ ¦ ¦ ¦¦
г==========- ¦ ¦ ¦ ¦ ¦ ¦¦
¦ -T-----T¬ ¦ ¦ ¦ ¦ --k ¦¦
L>¦¦STACK¦¦=>¦3 ¦ ¦ ¦K ¦ -T--T¬K' ¦¦
L+----A+- ¦ ¦ ¦ ¦===¦>¦¦RG¦¦¬ ¦¦
¦ ¦ А ¦ ¦ ¦ ¦¦ ¦¦¦ ¦¦
¦ L-A-- L---- -/++--+-¦ ¦¦
----¬ ¦ ¦ C ¦ ¦¦
¦MUX¦ ---¬ -¦------¦¬ ¦ ¦¦
0>+0 +->+M2+>+ CS ¦<==================- ¦¦
a>+1 ¦->+ ¦ ¦ ¦ ¦¦
b>+2 ¦¦ L--- L--------- ¦¦ k ----¬
¦А ¦¦e' ¦¦ L-+ 1 +-CC
LA---L---------------------------------------¦ --+ ¦
L===========================================- SYN L----
Переход к микроподпрограмме с возвратом
При реализации достаточно сложных вычислений удобно вос-
пользоваться механизмом микроподпрограмм.
Одна и та же микроподпрограмма может быть вызвана из
разных точек вызывающих микропрограмм. Поэтому при вызове
микроподпрограммы необходимо запомнить адрес, с тем, чтобы
восстановить его при возвращении из микроподпрограммы. Чтобы
запомнить и восстановить адреса возврата от вложенных вызо-
вов, используется безадресная память - стек (stack).
Принцип (дисциплина) работы стека описывается условием
"последний вошел - первым вышел" (Last In - First Out, LIFO).
чтобы описать этот принцип будем считать, что слова, хранящи-
еся в стеке, перенумерованы с помощью первых натуральных чи-
сел 1,2,...,N. Слово с наибольшим номером называют вершиной
стека.
Стек может выполнять следующие действия:
-"чтение" слова с наибольшим номером,
-"выталкивание" (стирание) из памяти слова с наибольшим но-
мером,
-"запись" нового слова с присваиванием ему наибольшего номе-
ра.
При вызове микроподпрограммы выполняется операция "запи-
си" адреса возврата в стек. При возвращении из микроподпрог-
раммы выполняется операция "чтения" адреса возврата, затем -
"выталкивания" его же из стека.
Операция "чтения" без "выталкивания" выполняется при ис-
- 11 -
пользовании стека для организации циклов.
Разряды с именем "К" определяют тип выполняемой микро-
инструкции. В связи с тем, что теперь в схеме существует 4
источника адреса для управляющей памяти, возможны 4 типа бе-
зусловных переходов, кроме того, возможны различные условные
переходы в различных сочетаниях комбинирующие эти источники
адреса и входные переменные.
С помощью комбинационной схемы CS разряды микроинструкции
"К" преобразуются в сигналы управления стеком и мультиплексо-
ром.
 _УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ
В конвейерном варианте для команд переходов по предикат-
ным переменным, зависящих без сдвига от сигналов управления,
приходится добавлять еще один такт для того, чтобы "увидеть"
значение переменной, по которой выполняется ветвление, и выб-
рать нужную МКИ.
Можно построить управляющий автомат, в котором для уско-
рения выполнения программы выполняются следующие действия:
Предварительно выбирается из ПЗУ одна из двух альтернативных
МКИ, соответствующая наиболее вероятному значению переменной
ветвления. Это значение должно храниться в той МКИ, после ко-
торой выполняется ветвление. В конце такта выработанное ре-
альное значение переменной сравнивается с предсказанным, если
они совпадают, то выбранная из ПЗУ МКИ записывается в выход-
ной регистр, если нет, то предыдущий такт продлевается, т.е.
не синхронизируются ОА и RG'МКИ. Микропрограмма будет такой
же как и для последовательного варианта взаимодействия ОА и
УА, но в МКИ добавляются два разряда:
F = { 1, если используется предвосхищение; 0, если нет },
P - наиболее вероятное значение переменной ветвления.
Фрагмент схемы УА, обеспечивающий предвосхищение может
быть таким:
--------------¬ ¦ ¦W
-T--T¬ ¦ -VT---¬ q -A---¬ f
t ¦¦RG¦¦ L-->+MUX+--->+ SS +<----------------------¬
--T--->+¦ ¦+---->+ ¦--->+ +<---------------------¬¦
¦ ¦¦ ¦¦ ¦ ¦¦t ¦ ¦ p ¦¦
¦ -\++--+- L----¦ -\+T---- ¦¦
¦ ¦ ¦ ¦ ¦j ¦¦
L---+----------------- ¦-VT---¬ ------¬ P -T--T¬p¦¦
¦ ¦ ¦MUX¦ ¦ ROM +--->+¦RG¦+--¦
¦ ¦ ¦ ¦ ¦ ¦ F ¦¦ ¦¦f ¦
¦ ¦ ¦ +--->+¦ ¦+---
¦ ¦ ¦ ¦ ¦¦ ¦¦
¦ ¦ ¦ ¦--->¦¦ ¦¦-->
¦ ¦ ¦ ¦ ¦¦ ¦¦
C ¦ ¦ L------ -\A++--+-
----+-------------------+--------------------L------ W
Пусть c=1 в конце такта.
Схема SS это автомат, который может находиться в одном
из двух состояний s0 и s1,
если s0, 0f, то w=1, j=q
если s0, 1f, 0c, то w=0, j=p
если s0, 1f, 1c, p==t, то w=1, j=p
если s0, 1f, 1c, p=/=t, то w=0, j=x, переход в s1
если s1, то w=1, j=q, переход в s0
 2Антик М.И. 11_03_91 МИРЭА
 _АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА
Алгоритмы этого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению с ал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешается изме-
нять любую другую память устройства локально (по частям) или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будем назы-
вать операционным устройством (ОУ).
ОУ можно рассматривать как один синхронный автомат со
сложно структурированной памятью - состоянием: часть памяти
используется для идентификации шага алгоритма, остальная па-
мять используется для запоминания промежуточных данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
алгоритма. Такая модель вычислителя особенно удобна для рас-
чета продолжительности одного такта работы устройства.
Другой удобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один из которых
называется управляющим автоматом (УА), а объединение всех ос-
тальных автоматов называется операционным автоматом (ОА).
УА является исполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритм процедурного
типа. Кроме того, УА инициирует действия отдельных шагов ал-
горитма и участвует в их выполнении.
ОА выполняет все вычисления на отдельных шагах алгоритма
под управлением УА; кроме того, к ОА удобно отнести все вы-
числения предикатных функций, оставив УА только анализ вычис-
ленных предикатных значений.
Прежде чем переходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например, каноническое описание синхронного конечного
автомата может быть интерпретировано (истолковано) как одно-
шаговый алгоритм процедурного типа.
-
-------¬ ¦
¦ ---V--V-----¬
¦ ¦ B=FO(S,A) ¦
¦ ¦ ¦
¦ ¦ S:=FS(S,A)¦
¦ L-----T------
L----------
Исполнитель этого алгоритма состоит только из ОА. На
каждом шаге этого алгоритма изменяется вся память устройства,
поэтому управление памятью не требуется, идентифицировать ша-
ги этого алгоритма не надо.
Например, инкрементор с одноразрядным входом и однораз-
рядным выходом может быть реализацией следующих преобразова-
ний:
-
- p:=1 -
-
---------¬ ¦
¦ ------V-V-------¬
¦ ¦ (p:, b) = a+p ¦
¦ L-------T--------
L-----------
- 2 -
ОА, реализующий инкрементор в целом, будет следующим:
---T-¬
a ------------------+HS¦S+----_b
--T-¬p ¦ ¦ ¦
начальное значен.-+S¦T+--+ ¦P+--¬
+-+ ¦ L--+-- ¦
SYN ---------/C¦ ¦ ¦
-+D¦ ¦ ¦
¦L-+-- ¦
L----------------
Конечно, эта реализация совпадает с реализацией алгоритма ав-
томатного типа, если состояние р1 кодируется 1, а состояние
р0 - 0.
Этот пример показывает,что до начала вычислений может
потребоваться начальная установка памяти. На самом деле это
необходимо было уже в алгоритмах автоматного типа, так как
код начального состояния требует предварительной установ-
ки. Ограничимся здесь обозначением этой проблемы, а решение
ее, связанное прежде всего с корректной синхронизацией ус-
тройства в первом такте его работы, рассмотрим ниже.
При рассмотрении процедуры построения автомата Мура эк-
вивалентного автомату Мили , не обсуждалась простая возмож-
ность ее реализации и на структурном уровне. Например, только
что рассмотренный автомат Мили может быть преобразован в эк-
вивалентный автомат Мура по одному из следующих вариантов:
-T-T¬t---T-¬ ---T-¬ -T-T¬
a --_+¦T¦+_+HS¦S+-_b a -----_+HS¦S+-_+¦T¦+-_b
-/++-+- ¦ ¦ ¦ ¦ ¦ ¦-/++-+-
C ¦ ¦ ¦ C ¦ ¦ ¦ C
-/TT-T¬p¦ ¦ ¦ -/TT-T¬p¦ ¦ ¦
-_+¦T¦+_+ ¦P+¬ -_+¦T¦+_+ ¦P+¬
¦ L+-+- L--+--¦ ¦ L+-+- L--+--¦
L-------------- L--------------
При таких структурных преобразованиях проще истолковы-
вать алгоритмы как процедурные.
- -
- p:=1; t:=0 - - p:=1 -
- -
---------¬ ¦ ---------¬ ¦
¦ ------V-V-------¬ ¦ ------V-V-------¬
¦ ¦t:=a;(p:,b)=t+p¦ ¦ ¦ (p , b):= a+p ¦
¦ L-------T-------- ¦ L-------T--------
L----------- L-----------
БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после
некоторых дополнений может быть использован и для описания
алгоритмов в процедурной форме:
Блок-текст состоит из трех частей:
1)- Описание переменных и начальных значений памяти.
2)- Описания функций и связей. Записываются любые функции и
функциональные связи (в том числе предикатные), не использу-
ющие запоминания. Переменные из левой части операции присва-
ивания таких функциональных описаний используются в блоках
процедуры.
3)- Процедура, состоящая из блоков (микроблоков) операторных
и блоков переходов:
- операторные - в скобках вида {.....},
- перехода - в скобках вида <<...>>;
и те, и другие блоки могут снабжаться метками, стоящими перед
блоком. В блоках перехода используется оператор GO в одной
из двух форм:
GO m - безусловный переход,
GO (P; m0,m1,m2,...) - условный переход.
здесь m0,m1,... - метки блоков,
P - предикатное значение,интерпретируемое оператором GO
- 3 -
как неотрицательное целое число, являющееся порядковым номе-
ром метки в списке меток оператора GO. С этой метки должно
быть продолжено выполнение алгоритма. Блоки условных перехо-
дов эквивалентны предикатным вершинам блок-схемы алгоритма.
На следующем более сложном примере демонстрируется пос-
ледовательность синтеза операционного устройства.
Пример. Вычислитель наибольшего общего делителя (НОД)
двух натуральных чисел (8-разрядных).
1) Разработаем интерфейс вычислителя:
8 ---T-----T--¬
===+=>¦I1¦ НОД ¦ ¦
¦ ¦ ¦ ¦ 8
8 ¦ ¦ ¦D ¦==+==>
===+=>¦I2¦ ¦ ¦
+--+ +--+
----->+rI¦ ¦rO+----->
+--+ ¦ ¦
----->+ C¦ ¦ ¦
L--+-----+---
I1[7..0], I2[7..0] -входные информационные шины.
rI -входной сигнал готовности: если rI=1, то на входах I1,
I2 готовы операнды.
D[7..0] -выходная информационная шина .
rO -выходной сигнал готовности: если rO=1, то готов резуль-
тат на шине D, который сохраняется до появления новых операн-
дов.
2) Математическое обоснование алгоритма вычислений:
Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-
ется в том, что НОД двух натуральных чисел А и В в случае ра-
венства этих чисел совпадает с любым из них, а в случае их
неравенства совпадает с НОД двух других чисел: меньшего и
разности между большим и меньшим. Последовательно, уменьшая
числа, получим два равных числа -значение одного из них и бу-
дет НОД исходных чисел.
3) Блок-схема алгоритма (микропрограмма в содержательном
виде):
- 4 -
-
¦
-------V------¬
m1¦ rO: = 0 ¦
L------T-------
¦-------------------¬
¦¦------¬ ¦
-VVV- ¦ ¦
/ \ 0 ¦ ¦
< rI>------ ¦
\_/ ¦
¦1 ¦
-------V------¬ ¦
¦ rO: = 0 ¦ ¦
¦ ¦ ¦
m2¦ А: = I1 ¦ ¦
¦ ¦ ¦
¦ B: = I2 ¦ ¦
L------T------- ¦
--------------------¬¦ ¦
¦ ------VV------¬ ¦
¦ m3¦ (p,S)=A - B ¦ ¦
¦ L------T------- ¦
¦ -V- m6 ¦
¦ / \ =0 -----------¬¦
¦ z <S==0>--->+ rO:=1;D=A+-
¦ \__/ L-----------
¦ ¦+0
¦ V
¦ 0 / \ 1
¦ --------< p >--------¬
¦ --------V------¬ \_/ --------V------¬
¦m4¦ (x,B:)=-A+B ¦ m5¦ (x,A:)=A - B ¦
¦ L-------T------- L-------T-------
L----------+---------------------
Или в виде блок-текста:
I1[7..0], I2[7..0] --входные шины
D[7..0] --выходная шина
rI, rO --сигналы готовности
A[7..0]:, B[7..0]: --память текущих значений
S[7..0] --разность
z, p --предикатные переменные
z=¬(!/S) --сжатие(свертка) S[7..0] по ИЛИ-НЕ
--можно записать иначе z=(S==0)
D=A
-------------------------------------------------------------------
m1{rO:=0}
g1<<GO(rI;g1,m2)>>
m2{rO:=0; A:=I1; B:=I2}
m3{(p,S)=A-B}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5)>>
m4{(x,B:)=-A+B}
<<GO m3>>
m5{(x,A:)= A-B}
<<GO m3>>
m6{rO:=1}
<<GO g1>>
- 5 -
4) Разработка функциональной схемы операционного автомата.
В ОА должны быть реализованы все переменные с памятью и
без,а также вычислительные операции,используемые в алгоритме.
A г==============================>D
-/TT--T¬ ¦ -------------¬
C¦¦RG¦¦ ¦ ¦ f1=(A-B) ¦
¦¦ ¦¦ ¦ A¦ ¦
I1=====>==>¦¦ ¦¦==- =>¦ f2=(-A+B)¦ --¬
¦¦ ¦¦ ¦ ¦S S¦1¦
¦¦ ¦¦ ¦ ¦> =>+ o--->z
++--+- ¦ ¦ ¦ ¦
B ¦ ¦ L--
-/TT--T¬ ¦ ¦
C¦¦RG¦¦ ¦ +------------>p
¦¦ ¦¦B B¦ ¦
I2=====>=>¦¦ ¦¦> =>¦ ¦ -/TT-T¬
¦¦ ¦¦ ¦ ¦ C¦¦ ¦+>rO
¦¦ ¦¦ ¦ ¦ ¦¦ ¦¦
rI----->++--+- L------------- L+-+-
Кроме того, в ОА необходимо реализовать все информацион-
ные связи, соответствующие микрооперации коммутации, а также
микрооперации запоминания (загрузки, записи) и обнуления.
г==============================================¬
¦ A г======================¦=======>D
¦ -----¬ -/TT--T¬ ¦ -----¬ -------¬ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦ ¦M2*8¦ 1->+cr SM¦ ¦
¦=>+0 ¦ ¦¦ ¦¦ ¦ ¦ ¦ +- ¦ ¦
I1==¦=>+1 ¦======>¦¦ ¦¦==¦==>¦ ¦===>¦I1 ¦ ¦ --¬
¦ + ¦ ¦¦ ¦¦ A ¦ ¦ ¦ ¦ ¦ ¦1¦
¦ ¦А ¦ W¦¦ ¦¦ +- ¦ ¦ S¦=¦>¦ o--->z
¦ LA---- -A++--+- LA---- ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ L--
¦ umA uA uiA ¦ ¦
¦ B ¦ ¦
¦ -----¬ -/TT--T¬ -----¬ ¦ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦M2*8¦ ¦ p+--------->p
L=>¦0 ¦ ¦¦ ¦¦ B ¦ ¦ ¦ ¦
I2====>¦1 ¦======>¦¦ ¦¦=====>¦ ¦===>¦I2 ¦ C
+ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ -/TT-T¬
¦А ¦ W¦¦ ¦¦ +- ¦ ¦ ¦1->+¦T¦+>rO
LA---- -A++--+- LA---- L-------R W¦¦ ¦¦
¦ ¦ ¦ -A-A++-+-
uMB uB uiB urO uwO
5) Формулировка требований к управляющему автомату.
При формировании управляющих сигналов следует обратить
внимание не только на операции, которые необходимо выполнить
на данном шаге, но и на те оперции, которые нельзя выполнять
на этом шаге, это - как правило, операции изменения памяти.
Будем считать, что операция активна, если значение уп-
равляющего сигнала равно 1.
- 6 -
Для управления вычислениями на каждом шаге алгоритма
потребуются следующие управляющие сигналы:
¦umA¦umB¦uwA¦uwB¦uiA¦uiB¦urO¦uwO¦
==+===+===+===+===+===+===+===+===¦
m1¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m2¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ ¦ ¦ 1 ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m3¦ ¦ ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m4¦ ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m5¦ 0 ¦ ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m6¦ ¦ ¦ 0 ¦ ¦ ¦ ¦ 0 ¦ 1 ¦
--¦---+---+---+---+---+---+---+----
В незаполненных клетках сигналы безразличны.
Заметив, что umA = umB , uiB = ¬uiA , окончательно полу-
чаем:
г==============================================¬
¦ A г======================¦=======>D
¦ -----¬ -/TT--T¬ ¦ -----¬ -------¬ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦ ¦M2*8¦ 1->+cr SM¦ ¦
¦=>¦0 ¦ ¦¦ ¦¦ ¦ ¦ ¦ +- ¦ ¦
I1==¦=>¦1 ¦======>¦¦ ¦¦==¦==>¦ ¦===>¦I1 ¦ ¦ --¬
¦ + ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦1¦
¦ ¦А ¦ W¦¦ ¦¦ +- ¦ ¦ S¦=¦>¦ o--->z
¦ LA---- -A++--+- LA---- ¦ ¦ ¦ ¦
¦ L----¬ --- B ------ +- ¦ L--
¦ -----¬¦ ¦-/TT--T¬ ¦ -----¬ ¦ ¦
¦ ¦ MUX¦¦ ¦ C¦¦RG¦¦ ¦ ¦M2*8¦ ¦ p+--------->p
L=>¦0 ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦
I2====>¦1 ¦¦===¦=>+¦ ¦¦==¦==>+ ¦===>¦I2 ¦
+ ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦
¦А ¦¦ ¦ W¦¦ ¦¦ ¦ +- ¦ ¦ ¦ C
LA----¦ ¦-A++--+- ¦ LA---- L------- -/TT-T¬
¦ ¦ ¦ L-¬ ¦ --¬¦ 1->+¦T¦+>rO
¦ ¦ ¦ ¦ +>+ o- R W¦¦ ¦¦
+----- ¦ ¦ ¦ L-- -A-A++-+-
umB uwA uwB uiA urO uwO
---¦--------¦----¦-----¦----------------------¦-¦-----
y1 y2 y3 y4 y5 y6
¦y1¦y2¦y3¦y4¦y5¦y6¦
==+==+==+==+==+==+==¦
m1¦ ¦ ¦ ¦ ¦ 1¦ 0¦
--+--+--+--+--+--+--+
m2¦ 1¦ 1¦ 1¦ ¦ 1¦ 0¦
--+--+--+--+--+--+--+
m3¦ ¦ 0¦ 0¦ 0¦ ¦ 0¦
--+--+--+--+--+--+--+
m4¦ 0¦ 0¦ 1¦ 1¦ ¦ 0¦
--+--+--+--+--+--+--+
m5¦ 0¦ 1¦ 0¦ 0¦ ¦ 0¦
--+--+--+--+--+--+--+
m6¦ ¦ 0¦ ¦ ¦ 0¦ 1¦
--¦--+--+--+--+--+---
- 7 -
Структура вычислителя:
---------------------------------¬
==>¦I1 ¦
¦ ¦
==>¦I2 ОА D¦==>
¦ ¦
---/C rO+-->
¦ ¦ ¦
¦ ¦z p umB uwA uwB uiA urO uwO ¦
¦ LT--T--A---A---A---A---A---A------
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ -V--V--+---+---+---+---+---+-----¬
¦ ¦z p y1 y2 y3 y4 y5 y6 ¦
¦ ¦ ¦
+--/C ¦
¦ УА ¦
-->+rI ¦
L---------------------------------
УА должен выполнять следующий алгоритм автоматного типа,
представленный в виде блок-текста:
m1{xxxx10}
g1<<GO(rI;g1,m2)>>
m2{111x10}
m3{x000x0}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5>>
m4{0011x0}
<<GO m3>>
m5{0100x0}
<<GO m3>>
m6{x0xx01}
<<GO g1>>
 _МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ.
МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ-
ходимое для получения (вычисления) значения одной или более
переменных.
Микрооперация присваивания В=А означает, что переменные
левой части получают значения выражения из правой части.
Всегда разрядность левой части равна разрядности правой час-
ти. При этом биты, расположенные на одной и той же позиции в
левой и правой частях, равны.
Неиспользуемые разряды в левой части и произвольные зна-
чения в правой части микрооперации присваивания обозначаются
(х). Например:
(В[7],x,B[6..0]) = (A[7..0],x)
означает арифметический сдвиг влево на один разряд 8-разряд-
ного числа с присваиванием произвольного значения младшему
разряду и с потерей старшего после знака разряда. А, напри-
мер, микрооперация
(B[7..0],d) = (A[7],A[7..0])
означает арифметический сдвиг вправо на один разряд.
Микрооперация
(p,S[3..0]) = A[3..0] + B[3..0] + q
описывает действие, выполняемое стандартным 4-разрядным сум-
матором, если ( А,В,q ) являются его непосредственными входа-
ми, а ( р,S ) - выходами.
Микрооперация ( : ) - двоеточие - означает запоминание
(изменение значения) в памяти устройства. Переменная типа па-
мять сохраняет свое значение между двумя очередными присва-
иваниями.
- 8 -
Микрооперации всегда входят в состав микрооператоров.
МИКРООПЕРАТОР - набор взаимосвязанных микроопераций (или
одна микрооперация ), выполняемых одновременно и необходимых
для получения одного или более значений. Например:
( e,D:) = R1 + R2 + c
Фрагмент аппаратуры, реализующей этот микрооператор, мог бы
быть, например, таким:
----¬
c ¦MUX¦
-T--T¬ ¦ ¦ ----¬
¦¦T ¦+--->+0 ¦ -----¬ ¦MUX¦ D
L+--+- -->+1 ¦ ¦ SM¦ ¦ ¦ -T--T¬
-->+А +--->+cr ¦ ===>¦0 ¦===>¦¦RG¦¦==>
+---+ ¦ S¦=====>¦1 ¦ L+--+-
R1 ¦MUX¦ ¦ ¦ ===>¦А ¦
-T--T¬ ¦ ¦ ¦ ¦ L----
¦¦RG¦¦===>¦0 ¦===>¦I1 ¦ ----¬
L+--+- ==>¦1 ¦ ¦ ¦ ¦MUX¦
==>¦А ¦ ¦ ¦ ¦ +------------>e
+---+ ¦ p+----->+0 ¦
R2 ¦MUX¦===>¦I2 ¦ --->+1 ¦
-T--T¬ ¦ ¦ L----- --->+А ¦
¦¦RG¦¦===>¦0 ¦ L----
L+--+- ==>¦1 ¦
==>¦А ¦
L----
Имена всех переменных, используемых в этом микрооператоре,
означают выполнение микроопераций коммутации ( транспортиров-
ки ). Значения переменных коммутируются на входы суммматора,
а результат суммирования - в места расположения переменных.
МИКРОБЛОК - набор микрооператоров, выполняемых одновре-
менно ( в одном такте ) и синхронно. В одном микроблоке любо-
му из битов присваивается только одно значение.
Синхронность означает, что во всех микрооператорах одно-
го микроблока используется только "старое" значение памяти.
Например:
{ (p,A):= A + B
(C,r):= A + D }
- и в том, и в другом микрооператоре используется одно и то
же старое значение А.
В то же время в микроблоке:
{ (C,x):= A + D
(x,A)= C + B }
в первом микрооператоре используется новое значение А , а во
втором - старое значение С. Разумеется, эти два действия вы-
полняются одновременнo на двух разных сумматорах.
При реализации микроблока { A:= B ; B:= 0 } обязательна
синхронная реализация В:=0 ( хотя обычно такое действие проще
реализовать асинхронно, но это приводит к ошибке ). Другой
правильный вариант: можно выполнить В:=0 асинхронно, но в
следющем такте.
Всегда предполагается, что предикат вычисляется вместе
(в одном такте) с тем микроблоком, за которым непосредственно
следует его использование.Таким образом, здесь, также как и в
микроблоке, используется старое значение памяти, существовав-
шее перед входом в микроблок. Это связано с особенностями
взаимодействия ОА и УА. Например:
- 9 -
- -
- CT:=(+0)- - CT:=(+0)-
- -
¦ ¦
-----V---¬ -----V---¬
m1¦ CT:=3 ¦ m1¦ CT:=3 ¦
L----T---- L----T----
------->¦ ------->¦
¦ -V- ¦ -V-
¦ / \ =0 ¦ / \ =0
¦ <CT==0>-> ¦ <CT==0>->
¦ \___/ ¦ \___/
¦ ¦+0 ¦ ¦+0
¦ -----V---¬ ¦ -----V---¬
¦m2¦........¦ ¦m2¦........¦
¦ ¦ ¦ ¦ ¦ ¦
¦ ¦CT:=CT-1¦ ¦ ¦CT:=CT-1¦
¦ L----T---- ¦ L----T----
L-------- ¦ -----V---¬
¦m3¦........¦
¦ L----T----
L--------
В первом случае цикл будет выполнен 4 раза; во втором - если
в микроблоке m3 нет операций, модифицирующих СТ, - 3 ра-
за. ( Обратите внимание на начальное значение СТ!)
МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и
интерпретируемый как управляющий,т.е. необходимый для выпол-
нения всех микроопераций одного микроблока. Сигналы, входящие
в микрокоманду, могут принимать участие в микрооперациях и в
качестве информационных.
Микрокомандой также иногда называют слово управляющей
памяти (обычно ПЗУ), являющееся частью УА. Для различения
этих понятий слово управляющей памяти будем называть МИКРО-
ИНСТРУКЦИЕЙ.
МИКРОПРОГРАММА СОДЕРЖАТЕЛЬНАЯ - алгоритм, представленный
в виде микроблоков и предикатных блоков в одной из принятых
форм, например, в виде блок-схемы или блок-текста.
МИКРОПРОГРАММА КОДИРОВАННАЯ - аппаратная форма содержа-
тельной микропрограммы в виде кодов, заполняющих управляющую
память.
 _КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА
В общем случае каноническая структура операционного ав-
томата имеет вид:
-----------------------------------------------------------
- -
- -----------¬ -T------T¬ -----------¬ --------¬ -
-->¦коммутация¦ ¦¦память¦¦ ¦коммутация¦ ¦функции¦---
¦ ¦--->¦¦ ¦¦-->¦ ¦-->¦ ¦
-->¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦--->
L-A--------- -/-++---A--+- L--A-------- L--A-----
- --¬¦CC - - -
- SYN->+&+- - - -
- -+ ¦ - - -
- yC¦L-- - - -
L-------------------------------------------------
сигналы управления
Столь четкого разграничения операций на зоны (память, комму-
тация, функции) может и не быть. Например, такие широко ис-
пользуемые функции как сдвиги либо хорошо совмещаются с
коммутацией, либо интегрируются с регистрами хранения.Также
часто интегрируются с хранением функции инкремента и
- 10 -
декремента (счетчики обычные и реверсивные).
Особо выделим сигнал yС, управляющий доступом синхросиг-
налов в ОА. Такой вариант управления, называемый условной
синхронизацией, позволяет запретить любые изменения памяти ОА
в каком-либо такте. Причем, если рабочим является срез (зад-
ний фронт) сигнала синхронизации, то используется элемент И,
как и показано на рисунке.Если же рабочим является фронт (пе-
редний фронт) сигнала, то используется элемент ИЛИ. (Первый
перепад сигнала синхронизации в новом такте не должен быть
рабочим.)
 _ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА
При проектировании вычислительного устройства основными
являются ограничения на:
1)- время вычисления;
2)- объем аппаратуры, реализующей вычисления;
3)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальным по-
тенциальным параллелизмом (в рамках данной алгоритмической
идеи), и,следовательно, его реализация в виде КС обладает
максимальным быстродействием по сравнению с любыми другими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представление и его реализация являются
статическим отображением входных объектов на выходные: это
исключает возможность работы с объектами, которые "ведут се-
бя" более сложно во времени; невозможно также реализовать
принципиально рекуррентные алгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритм функционального
типа может быть записан, то проектирование устройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом на про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из них в один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменных (входных
и выходных),связанных с выполнением этих операций. Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений - но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простую модель в виде направленного
графа. Вершины графа будут соответствовать операциям, а дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный граф всегда будет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо на аль-
тернативных путях решения.
- 11 -
 _МИНИМИЗАЦИЯ АППАРАТУРЫ
Может оказаться, что на одном пути в сигнальном графе
расположены операции, плохо или вовсе не совмещаемые друг с
другом (т.е. совмещение не дает экономии в аппаратуре функци-
онального модуля). Возможно также, что проведенная минимиза-
ция, сохраняющая минимальное время, не позволяет выполнить
ограничение на объем аппаратуры. В таком случае необходима
более глубокая минимизация,охватывающая параллельные ветви
сигнального графа. Минимизация должна быть взаимосвязанной по
всем компонентам ОА: по памяти, функциональным модулям и ком-
мутации.
В настоящее время процедуры минимизации не формализованы
и сводятся к перебору "правдоподобных" вариантов.
Можно предложить следующую последовательность действий:
1)- все "похожие" функции (операции) реализовать на одном
функциональном модуле, например, все суммирования выполнять
на одном сумматоре;
2)-скорректировать алгоритм так, чтобы в одном микроблоке не
выполнялось более одной операции на одном и том же функци-
ональном модуле;
3)- минимизировать память автомата, т.е. число запоминаемых
промежуточных переменных;
Выполнение этих этапов может привести к усложнению ком-
мутации, а значит, и к увеличению этой компоненты в аппарату-
ре ОА. Если ограничение по объему аппаратуры все еще наруше-
но, то повторить этапы 1 - 3 с другим вариантом объединения
функциональных модулей и памяти.
При реализации ОА - во избежание ошибок -необходимо бук-
вально следовать описанию алгоритма, но в то же время, при
проектировании самого алгоритма надо представлять себе реали-
зацию микроблоков. Реализация одних и тех же вычислений может
быть существенно различной по объему аппаратуры.
Например, вычисления в цикле потребуют реализации:
-T-
¦
--------V-------¬ A -----¬
¦ J:=0 ¦ -T--T-¬ ¦ MUX¦ -----¬
L-------T-------- ¦¦RG¦0+--->+0 ¦ ¦ f ¦
-------¬ ¦ ¦¦ ¦.¦ . ¦. ¦A[J] ¦ ¦
¦ -----V--V-------¬ ¦¦ ¦.¦ . ¦. +---->+ ¦
¦ ¦ ..... ¦ ¦¦ ¦.¦ . ¦. ¦ ¦ ¦ B
¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦==>
¦ ¦ B= f(...,A[J])¦ ¦¦ ¦K+--->+K ¦ ¦ ¦
¦ ¦ ¦ ¦¦ ¦.¦ ¦. ¦ ==>¦ ¦
¦ ¦ J:=J+1 ¦ ¦¦ ¦.¦ ¦. ¦ ¦ ¦
¦ L-------T-------- ¦¦ ¦.¦ ¦. ¦ ¦ ¦
¦ -V- L+--+-- +- ¦ L-----
¦ <K / \ =K J=========>¦А ¦
L------<J==K>-----> L-----
\__/
(реализация счетчика J не показанa).
- 12 -
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре D. Тогда получим:
---T-- A D
¦ -T--T¬ -T--T-¬ A[J] ------¬
--------V-------¬ ¦¦RG¦¦ ¦¦RG¦0+----->+ f ¦
¦ J:=0 ¦ ¦¦ ¦¦ ¦¦ ¦.¦ ¦ ¦
¦ ¦ ¦¦ ¦¦ ¦¦->¦.¦ ¦ ¦ B
¦ D:=A ¦ ¦¦ ¦¦======>¦¦ ¦.¦ ¦ ¦==>
L-------T-------- ¦¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦
-------¬ ¦ ¦¦ ¦¦ ¦¦ ¦K+ ¦ ¦
¦ -----V--V-------¬ ¦¦ ¦¦ x -->+Dn ¦.¦ ¦ ¦
¦ ¦ ..... ¦ ¦¦ ¦¦ ¦¦ ¦.¦ ==>¦ ¦
¦ ¦ ¦ ¦¦ ¦¦ S W¦¦ ¦.¦ ¦ ¦
¦ ¦ B= f(...,D[0])¦ L+--+- -v-v++--+-- L------
¦ ¦ ¦
¦ ¦ (D,x):=(x,D) ¦
¦ ¦ ¦
¦ ¦ J:=J+1 ¦
¦ L-------T--------
¦ -V-
¦ <K / \ =K
L------<J==K>----->
\__/
Промежуточный регистр A введен для общности, если потребуется
сохранить слово А (чаще всего он и не нужен).
Другой пример: фрагмент алгоритма, реализующий регуляр-
ную запись отдельных бит слова и его реализация имеют вид:
---T-- -T-T¬B[0]
¦ a ------------T----->+¦T¦+---->
--------V-------¬ ¦ W¦¦ ¦¦
¦ J:=0 ¦ ----¬ ¦ -A++-+-
L-------T-------- ¦DC ¦ ---+------| |
-------¬ ¦ ¦ 0+-- ¦ | |
¦ -----V--V-------¬ ¦ .¦. ¦ -T-T¬B[K]
¦ ¦ ..... ¦ ¦ .¦. L----->+¦T¦+---->
¦ ¦ ¦ ¦ .¦. W¦¦ ¦¦
¦ ¦ a=f(...) ¦ J ==>¦ ¦ -A++-+-
¦ ¦ ¦ ¦ K+-----------
¦ ¦ B[J]:=a ¦ ¦ .¦
¦ ¦ ¦ ¦ .¦
¦ ¦ J:=J+1 ¦ ¦ .¦
¦ L-------T-------- L----
¦ -V-
¦ <K / \ =K
L------<J==K>----->
\__/
Слово В нельзя реализовать в виде регистра, а только в виде
отдельных триггеров.
Можно формировать слово с использованием операции сдви-
га при обязательном условии D[K..0], тогда алгоритм и его ре-
ализация имеют вид:
- 13 -
---T--
¦ D B
--------V-------¬ ---T--T¬ -T--T¬
¦ J:=0 ¦ ¦ ¦RG¦¦ ¦¦RG¦¦
L-------T-------- ¦ ¦->¦¦ ¦¦ ¦¦
-------¬ ¦ a ¦ ¦ ¦¦=====>¦¦ ¦¦
¦ -----V--V-------¬ -->+Dk¦ ¦¦ ¦¦ ¦¦
¦ ¦ ..... ¦ S¦ ¦ ¦¦ W¦¦ ¦¦
¦ ¦ ¦ -v+--+--+- -v++--+-
¦ ¦ a=f(...) ¦
¦ ¦ ¦
¦ ¦ (D,x):=(a,D) ¦
¦ ¦ ¦
¦ ¦ J:=J+1 ¦
¦ L-------T--------
¦ -V-
¦ <K / \ =K -----¬
L------<J==K>-->+B:=D+>
\__/ L-----
В этом случае, так же, как и в предыдущем, чаще всего не ну-
жен промежуточный регистр (В).
 _УНИВЕРСАЛЬНЫЙ ОА
Использование при проектировании универсальных ОА с за-
ранее фиксированной и минимизированной структурой оправдано
тем, что такие универсальные ОА изготавливаются промышлен-
ностью в виде БИС большим тиражом и поэтому они сравнительно
дешевы. Такие универсальные ОА входят в микропроцессорные на-
боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на-
зываются микропрограммируемыми, секционными, разрядно-модуль-
ными.
В основе перечисленных универсальных ОА лежит следующая
структура:
г==================T===========================¬
¦ ¦ ¦
¦ ¦ SYN¬ ACC ¦
¦ --T-----T¬ ¦ -/TT--T¬ ------¬ ¦
¦ ¦ ¦ RGF ¦¦ ¦ C¦¦RG¦¦ ¦ ALU ¦ ¦
¦ ¦ ¦ ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦
¦ ¦ ¦ ¦¦ L====>¦¦ ¦¦=====>¦ ¦ ¦
¦ ¦ ¦ ¦¦ ¦¦ ¦¦ ¦ ¦===¦=>DO
L===>¦D¦ ¦¦ L+--+- ¦ ¦
¦ ¦ ¦¦ T ¦ ¦
¦ ¦ ¦¦ -T--T¬ ¦ ¦=====>P
¦ ¦ ¦¦ ¦¦RG¦¦ ¦ ¦
¦ ¦ ¦¦=========>¦¦ ¦¦=====>¦ ¦
¦ ¦ ¦¦ ¦¦ ¦¦ ¦ ¦
C W¦А¦ ¦¦ C¦¦ ¦¦ г=>¦ ¦
-o-A+A+-----+- -T++--+- ¦ L--A---
SYN- ¦ ¦ SYN- ¦ ¦
¦ ¦ ¦ ¦
yW YA DI=====- YF
ALU - арифметико-логическое устройство - комбинационная
схема с небольшим, но универсальным набором арифметических и
логических операций.
RGF - регистровый файл - адресуемая память RAM со стати-
ческой синхронизацией при записи.
RG'T' - регистр-фиксатор со статической синхронизацией.
RG'АCC' - регистр-аккумулятор с динамической синхрониза-
цией.
DI,DO - входная и выходная информационные шины.
- 14 -
Р - предикатные сигналы (флажки).
YF - сигналы управления выбором функции.
YA - адрес чтения и/или записи RGF.
yW - разрешение записи в RGF.
Память сравнительно большого объема, какой является RGF,
дешевле реализовать со статической синхронизацией. Для то-
го,чтобы такая память могла работать в замкнутом информацион-
ном кольце и при этом не возникали бы гонки, добавляется еше
один промежуточный регистр RG'T' со статической синхрониза-
цией. Если передний фронт является рабочим для регистров уп-
равляющего автомата и RG'ACC', то на первой фазе синхрониза-
ции при SYN=1 информация читается из RGF; при этом RG'T'
прозрачен. На следующей фазе синхронизации при SYN=0 информа-
ция фиксируется в RG'T', т.е. он закрыт для записи, а запись
(если она разрешена) производится в RGF. Фиксируется информа-
ция в RGF и RG'ACC' с началом следующего такта, т.е. на пе-
реднем фронте сигнала.
 _ВЗАИМОДЕЙСТВИЕ ОА и УА
Для исключения гонок при взаимодействии ОА и УА будем
проектировать УА как автомат Мура. Схема их взаимодействия
может быть представлена в виде:
г==========================¬
¦-----¬ -T--T¬ -----¬ ¦
L¦ CS ¦ ¦¦RG¦¦ ¦CS ¦<-
¦ ¦<=T=¦¦ ¦¦<==¦ ¦
----+ b ¦ ¦ ¦¦ ¦¦ ¦ c +<----¬
¦ L----- ¦ L+--++A- L----- ¦
¦ -----¬ ¦ L-----------¬ ¦
¦ ¦CS ¦<=- ¦ ¦
¦---+ a +<-------------------¬ ¦ ¦
ОА ¦¦ L----- ¦ ¦ ¦
----¦¦----------------------------¦-¦-¦--
УА ¦¦РА-----¬ -T--T¬ ------¬¦ ¦ ¦¬
¦L->+ CS¦ ¦¦RG¦¦ ¦ CS +- ¦ ¦¦
L-->+ ¦====>¦¦ ¦¦=>¦ +--- ¦¦Y
РВ ¦ ¦ ¦¦ ¦¦ ¦ +-----¦
г>¦ p ¦ ¦¦ ¦¦ ¦ y ¦=¬ -
¦ L----- L+--+- L------ ¦
L============================-
Отметим, что РА(t)=f(Y(t)) зависит без сдвига от сигналов
управления,
PB(t+1)=F(Y(t)) зависит со сдвигом от сигналов
управления,
где РА и РВ - предикатные перемнные.
Продолжительность такта работы схемы определяется наибо-
лее длинными цепями между регистрами. Для данной схемы, кото-
рую будем называть последовательной схемой взаимодействия,
зададимся (так чаще всего бывает), что такой критической
цепью является цепь (CSy,CSa,CSp,RG). Поэтому длительность
такта определяется:
Т > ty + ta + tp + trg,
где tj- время установления соответствующего компонента цепи.
Чтобы сократить длину этой цепи, применяют другой вари-
ант взаимодействия автоматов - конвейерный:
- 15 -
г==========================¬
¦-----¬ -T--T¬ -----¬ ¦
L¦ CS ¦ ¦¦RG¦¦ ¦CS ¦<-
¦ ¦<=T=¦¦ ¦¦<==¦ ¦
------------+ b ¦ ¦ ¦¦ ¦¦ ¦ c +<----¬
¦ FF L----- ¦ L+--++A- L----- ¦
¦ -T--T¬ -----¬ ¦ L-----------¬ ¦
¦--+¦RG¦¦<==¦ CS ¦<=- ¦ ¦
¦¦ ¦¦ ¦¦ ¦ a +<-------------------¬ ¦ ¦
¦¦ L+--++A- L----- ¦ ¦ ¦
ОА ¦¦ L--------------------------¬ ¦ ¦ ¦
---¦¦----------------------------------¦-¦-¦-¦--
УА ¦¦ MK ¦ ¦ ¦ ¦
¦¦ PA -----T----¬ -T--T¬¦ ¦ ¦ ¦¬
¦L---->+ CS¦ CS ¦ ¦¦RG¦+- ¦ ¦ ¦¦
¦ РВ ¦ ¦ ¦ ¦¦ ¦+--- ¦ ¦¦Y
L----->+ ¦ ¦===========>¦¦ ¦+----- ¦¦
¦ ¦ ¦ ¦¦ ¦+-------¦
г>¦ p ¦ y ¦ ¦¦ ¦¦=¬ -
¦ L----+----- L+--+- ¦
L===============================-
При этом варианте взаимодействия такой длинной цепи, как
в предыдущем случае, не возникает.Эта цепь разделена регис-
трами RG'FF' (регистр флажков) и RG'MK' (регистр микрокоман-
ды) на две цепи. Продолжительность такта становится меньше и
ее можно определить следующим образом:
T > max( ta,(tp + ty) )+ trg ,
При конвейерном варианте взаимодействия
PA(t+1)=f(Y(t)), т.е. и эти значения стали зависить со
сдвигом от сигналов управления. Тогда фрагмент микропрограммы
mS{...;pA=f(...)}
<< GO(pA;mi,mj)>>,
выполняемый в последовательной схеме за один такт, в кон-
вейерном варианте за один такт выполнен быть не может и дол-
жен быть модифицирован следующим образом:
mS{...,pA=f(...)}
mS'{нет операции}
<< GO(pA;mi,mj)>>
Таким образом, время выполнения этого фрагмента не только не
уменьшилось, но даже возросло несмотря на уменьшение продол-
жительности каждого из тактов. Зато во всех остальных случа-
ях (при безусловных переходах, при переходах по значению РВ)
время выполнения микропрограммы уменьшается.
 _НАЧАЛЬНАЯ ИНИЦИАЛИЗАЦИЯ СИНХРОННОЙ СХЕМЫ
Пусть устройство, кроме сигнала синхронизации SYN, имеет
еще один сигнал Н, обозначающий начало и конец синхронной ра-
боты устройства. При Н=0 - нерабочее состояние - можно выпол-
нять начальную установку значений памяти устройства. Измене-
ние значения Н с 0 на 1 происходит в случайный момент времени
(асинхронно), но при этом начальный такт работы устройства
должен быть полным. "Затягивание" асинхронного сигнала Н в
синхронный режим происходит с помощью простейшего синхронного
автомата с диаграммой:
-----------¬ ---------¬
V 0H/CONST¦ V 1H/SYN¦
-------------- ------------
>¦ 0 ¦-------------->¦ 1 ¦------¬
----- 1H/CONST ----- 0H/X ¦
л ¦
L-----------------------------
У этого автомата простейшей является функция переходов, так
как диаграмма автомата совпадает с диаграммой переходов
- 16 -
D-триггера.
Схема автомата вместе с цепями условной синхронизации
выглядит следующим образом (для синхронизации по фронтам):
а)-по переднему фронту, б)- по заднему фронту:
---¬ ---¬
SYN --T----------+ 1+-- CC SYN --T----------+ &+-- CC
¦ --T-¬ --+ ¦ ¦ --T-¬ --+ ¦
L-/C¦T¦ ¦ L--- L-\C¦T¦ ¦ L---
¦ ¦ + ¦ ¦ ¦ +---
--+D¦ ¦ ¦ --+D¦ ¦
¦ +-+ o--- ¦ +-+ o-
+-oR¦ ¦ +-oR¦ ¦
H ¦ L-+--уст. нач. зн. H ¦ L-+--уст. нач. зн.
--+------------------- --+-------------------
Такая разница в цепях условной синхронизации, как уже объяс-
нялось выше, определяется тем, что первый перепад сигнала СС
не должен быть рабочим.
Антик М.И. 11_03_91 МИРЭА
АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА
Алгоритмы этого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению с ал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешается изме-
нять любую другую память устройства локально (по частям) или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будем назы-
вать операционным устройством (ОУ).
ОУ можно рассматривать как один синхронный автомат со
сложно структурированной памятью - состоянием: часть памяти
используется для идентификации шага алгоритма, остальная па-
мять используется для запоминания промежуточных данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
алгоритма. Такая модель вычислителя особенно удобна для рас-
чета продолжительности одного такта работы устройства.
Другой удобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один из которых
называется управляющим автоматом (УА), а объединение всех ос-
тальных автоматов называется операционным автоматом (ОА).
УА является исполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритм процедурного
типа. Кроме того, УА инициирует действия отдельных шагов ал-
горитма и участвует в их выполнении.
ОА выполняет все вычисления на отдельных шагах алгоритма
под управлением УА; кроме того, к ОА удобно отнести все вы-
числения предикатных функций, оставив УА только анализ вычис-
ленных предикатных значений.
Прежде чем переходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например, каноническое описание синхронного конечного
автомата может быть интерпретировано (истолковано) как одно-
шаговый алгоритм процедурного типа.
-
-------¬ ¦
¦ ---V--V-----¬
¦ ¦ B=FO(S,A) ¦
¦ ¦ ¦
¦ ¦ S:=FS(S,A)¦
¦ L-----T------
L----------
Исполнитель этого алгоритма состоит только из ОА. На
каждом шаге этого алгоритма изменяется вся память устройства,
поэтому управление памятью не требуется, идентифицировать ша-
ги этого алгоритма не надо.
Например, инкрементор с одноразрядным входом и однораз-
рядным выходом может быть реализацией следующих преобразова-
ний:
-
- p:=1 -
-
---------¬ ¦
¦ ------V-V-------¬
¦ ¦ (p:, b) = a+p ¦
¦ L-------T--------
L-----------
ОА, реализующий инкрементор в целом, будет следующим:
---T-¬
a ------------------+HS¦S+----_b
--T-¬p ¦ ¦ ¦
начальное значен.-+S¦T+--+ ¦P+--¬
+-+ ¦ L--+-- ¦
SYN ---------/C¦ ¦ ¦
-+D¦ ¦ ¦
¦L-+-- ¦
L----------------
Конечно, эта реализация совпадает с реализацией алгоритма ав-
томатного типа, если состояние р1 кодируется 1, а состояние
р0 - 0.
Этот пример показывает,что до начала вычислений может
потребоваться начальная установка памяти. На самом деле это
необходимо было уже в алгоритмах автоматного типа, так как
код начального состояния требует предварительной установ-
ки. Ограничимся здесь обозначением этой проблемы, а решение
ее, связанное прежде всего с корректной синхронизацией ус-
тройства в первом такте его работы, рассмотрим ниже.
При рассмотрении процедуры построения автомата Мура эк-
вивалентного автомату Мили , не обсуждалась простая возмож-
ность ее реализации и на структурном уровне. Например, только
что рассмотренный автомат Мили может быть преобразован в эк-
вивалентный автомат Мура по одному из следующих вариантов:
-T-T¬t---T-¬ ---T-¬ -T-T¬
a --_+¦T¦+_+HS¦S+-_b a -----_+HS¦S+-_+¦T¦+-_b
-/++-+- ¦ ¦ ¦ ¦ ¦ ¦-/++-+-
C ¦ ¦ ¦ C ¦ ¦ ¦ C
-/TT-T¬p¦ ¦ ¦ -/TT-T¬p¦ ¦ ¦
-_+¦T¦+_+ ¦P+¬ -_+¦T¦+_+ ¦P+¬
¦ L+-+- L--+--¦ ¦ L+-+- L--+--¦
L-------------- L--------------
При таких структурных преобразованиях проще истолковы-
вать алгоритмы как процедурные.
- -
- p:=1; t:=0 - - p:=1 -
- -
---------¬ ¦ ---------¬ ¦
¦ ------V-V-------¬ ¦ ------V-V-------¬
¦ ¦t:=a;(p:,b)=t+p¦ ¦ ¦ (p , b):= a+p ¦
¦ L-------T-------- ¦ L-------T--------
L----------- L-----------
БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после
некоторых дополнений может быть использован и для описания
алгоритмов в процедурной форме:
Блок-текст состоит из трех частей:
1)- Описание переменных и начальных значений памяти.
2)- Описания функций и связей. Записываются любые функции и
функциональные связи (в том числе предикатные), не использу-
ющие запоминания. Переменные из левой части операции присва-
ивания таких функциональных описаний используются в блоках
процедуры.
3)- Процедура, состоящая из блоков (микроблоков) операторных
и блоков переходов:
- операторные - в скобках вида {.....},
- перехода - в скобках вида <<...>>;
и те, и другие блоки могут снабжаться метками, стоящими перед
блоком. В блоках перехода используется оператор GO в одной
из двух форм:
GO m - безусловный переход,
GO (P; m0,m1,m2,...) - условный переход.
здесь m0,m1,... - метки блоков,
P - предикатное значение,интерпретируемое оператором GO
как неотрицательное целое число, являющееся порядковым номе-
ром метки в списке меток оператора GO. С этой метки должно
быть продолжено выполнение алгоритма. Блоки условных перехо-
дов эквивалентны предикатным вершинам блок-схемы алгоритма.
На следующем более сложном примере демонстрируется пос-
ледовательность синтеза операционного устройства.
Пример. Вычислитель наибольшего общего делителя (НОД)
двух натуральных чисел (8-разрядных).
1) Разработаем интерфейс вычислителя:
8 ---T-----T--¬
===+=>¦I1¦ НОД ¦ ¦
¦ ¦ ¦ ¦ 8
8 ¦ ¦ ¦D ¦==+==>
===+=>¦I2¦ ¦ ¦
+--+ +--+
----->+rI¦ ¦rO+----->
+--+ ¦ ¦
----->+ C¦ ¦ ¦
L--+-----+---
I1[7..0], I2[7..0] -входные информационные шины.
rI -входной сигнал готовности: если rI=1, то на входах I1,
I2 готовы операнды.
D[7..0] -выходная информационная шина .
rO -выходной сигнал готовности: если rO=1, то готов резуль-
тат на шине D, который сохраняется до появления новых операн-
дов.
2) Математическое обоснование алгоритма вычислений:
Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-
ется в том, что НОД двух натуральных чисел А и В в случае ра-
венства этих чисел совпадает с любым из них, а в случае их
неравенства совпадает с НОД двух других чисел: меньшего и
разности между большим и меньшим. Последовательно, уменьшая
числа, получим два равных числа -значение одного из них и бу-
дет НОД исходных чисел.
3) Блок-схема алгоритма (микропрограмма в содержательном
виде):
-
¦
-------V------¬
m1¦ rO: = 0 ¦
L------T-------
¦-------------------¬
¦¦------¬ ¦
-VVV- ¦ ¦
/ \ 0 ¦ ¦
< rI>------ ¦
\_/ ¦
¦1 ¦
-------V------¬ ¦
¦ rO: = 0 ¦ ¦
¦ ¦ ¦
m2¦ А: = I1 ¦ ¦
¦ ¦ ¦
¦ B: = I2 ¦ ¦
L------T------- ¦
--------------------¬¦ ¦
¦ ------VV------¬ ¦
¦ m3¦ (p,S)=A - B ¦ ¦
¦ L------T------- ¦
¦ -V- m6 ¦
¦ / \ =0 -----------¬¦
¦ z <S==0>--->+ rO:=1;D=A+-
¦ \__/ L-----------
¦ ¦+0
¦ V
¦ 0 / \ 1
¦ --------< p >--------¬
¦ --------V------¬ \_/ --------V------¬
¦m4¦ (x,B:)=-A+B ¦ m5¦ (x,A:)=A - B ¦
¦ L-------T------- L-------T-------
L----------+---------------------
Или в виде блок-текста:
I1[7..0], I2[7..0] --входные шины
D[7..0] --выходная шина
rI, rO --сигналы готовности
A[7..0]:, B[7..0]: --память текущих значений
S[7..0] --разность
z, p --предикатные переменные
z=¬(!/S) --сжатие(свертка) S[7..0] по ИЛИ-НЕ
--можно записать иначе z=(S==0)
D=A
-------------------------------------------
m1{rO:=0}
g1<<GO(rI;g1,m2)>>
m2{rO:=0; A:=I1; B:=I2}
m3{(p,S)=A-B}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5)>>
m4{(x,B:)=-A+B}
<<GO m3>>
m5{(x,A:)= A-B}
<<GO m3>>
m6{rO:=1}
<<GO g1>>
4) Разработка функциональной схемы операционного автома-
та.
В ОА должны быть реализованы все переменные с памятью и
без,а также вычислительные операции,используемые в алгоритме.
A г==============================>D
-/TT--T¬ ¦ -------------¬
C¦¦RG¦¦ ¦ ¦ f1=(A-B) ¦
¦¦ ¦¦ ¦ A¦ ¦
I1=====> ==>¦¦ ¦¦==- =>¦ f2=(-A+B)¦ --¬
¦¦ ¦¦ ¦ ¦S S¦1¦
¦¦ ¦¦ ¦ ¦> =>+ o--->z
++--+- ¦ ¦ ¦ ¦
B ¦ ¦ L--
-/TT--T¬ ¦ ¦
C¦¦RG¦¦ ¦ +------------>p
¦¦ ¦¦B B¦ ¦
I2=====> =>¦¦ ¦¦> =>¦ ¦ -/TT-T¬
¦¦ ¦¦ ¦ ¦ C¦¦ ¦+>rO
¦¦ ¦¦ ¦ ¦ ¦¦ ¦¦
rI-----> ++--+- L------------- L+-+-
Кроме того, в ОА необходимо реализовать все информацион-
ные связи, соответствующие микрооперации коммутации, а также
микрооперации запоминания (загрузки, записи) и обнуления.
г==============================================¬
¦ A г======================¦=======>D
¦ -----¬ -/TT--T¬ ¦ -----¬ -------¬ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦ ¦M2*8¦ 1->+cr SM¦ ¦
¦=>+0 ¦ ¦¦ ¦¦ ¦ ¦ ¦ +- ¦ ¦
I1==¦=>+1 ¦======>¦¦ ¦¦==¦==>¦ ¦===>¦I1 ¦ ¦ --¬
¦ + ¦ ¦¦ ¦¦ A ¦ ¦ ¦ ¦ ¦ ¦1¦
¦ ¦А ¦ W¦¦ ¦¦ +- ¦ ¦ S¦=¦>¦ o--->z
¦ LA---- -A++--+- LA---- ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ L--
¦ umA uA uiA ¦ ¦
¦ B ¦ ¦
¦ -----¬ -/TT--T¬ -----¬ ¦ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦M2*8¦ ¦ p+--------->p
L=>¦0 ¦ ¦¦ ¦¦ B ¦ ¦ ¦ ¦
I2====>¦1 ¦======>¦¦ ¦¦=====>¦ ¦===>¦I2 ¦ C
+ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ -/TT-T¬
¦А ¦ W¦¦ ¦¦ +- ¦ ¦ ¦1->+¦T¦+>rO
LA---- -A++--+- LA---- L-------R W¦¦ ¦¦
¦ ¦ ¦ -A-A++-+-
uMB uB uiB urO uwO
5) Формулировка требований к управляющему автомату.
При формировании управляющих сигналов следует обратить
внимание не только на операции, которые необходимо выполнить
на данном шаге, но и на те оперции, которые нельзя выполнять
на этом шаге, это - как правило, операции изменения памяти.
Будем считать, что операция активна, если значение уп-
равляющего сигнала равно 1.
Для управления вычислениями на каждом шаге алгоритма
потребуются следующие управляющие сигналы:
¦umA¦umB¦uwA¦uwB¦uiA¦uiB¦urO¦uwO¦
==+===+===+===+===+===+===+===+===¦
m1¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m2¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ ¦ ¦ 1 ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m3¦ ¦ ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m4¦ ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m5¦ 0 ¦ ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ ¦ 0 ¦
--+---+---+---+---+---+---+---+---+
m6¦ ¦ ¦ 0 ¦ ¦ ¦ ¦ 0 ¦ 1 ¦
--¦---+---+---+---+---+---+---+----
В незаполненных клетках сигналы безразличны.
Заметив, что umA = umB , uiB = ¬uiA , окончательно полу-
чаем:
г==============================================¬
¦ A г======================¦=======>D
¦ -----¬ -/TT--T¬ ¦ -----¬ -------¬ ¦
¦ ¦ MUX¦ C¦¦RG¦¦ ¦ ¦M2*8¦ 1->+cr SM¦ ¦
¦=>¦0 ¦ ¦¦ ¦¦ ¦ ¦ ¦ +- ¦ ¦
I1==¦=>¦1 ¦======>¦¦ ¦¦==¦==>¦ ¦===>¦I1 ¦ ¦ --¬
¦ + ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦1¦
¦ ¦А ¦ W¦¦ ¦¦ +- ¦ ¦ S¦=¦>¦ o--->z
¦ LA---- -A++--+- LA---- ¦ ¦ ¦ ¦
¦ L----¬ --- B ------ +- ¦ L--
¦ -----¬¦ ¦-/TT--T¬ ¦ -----¬ ¦ ¦
¦ ¦ MUX¦¦ ¦ C¦¦RG¦¦ ¦ ¦M2*8¦ ¦ p+--------->p
L=>¦0 ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦
I2====>¦1 ¦¦===¦=>+¦ ¦¦==¦==>+ ¦===>¦I2 ¦
+ ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦ ¦
¦А ¦¦ ¦ W¦¦ ¦¦ ¦ +- ¦ ¦ ¦ C
LA----¦ ¦-A++--+- ¦ LA---- L------- -/TT-T¬
¦ ¦ ¦ L-¬ ¦ --¬¦ 1->+¦T¦+>rO
¦ ¦ ¦ ¦ +>+ o- R W¦¦ ¦¦
+----- ¦ ¦ ¦ L-- -A-A++-+-
umB uwA uwB uiA urO uwO
---¦--------¦----¦-----¦----------------------¦-¦-----
y1 y2 y3 y4 y5 y6
¦y1¦y2¦y3¦y4¦y5¦y6¦
==+==+==+==+==+==+==¦
m1¦ ¦ ¦ ¦ ¦ 1¦ 0¦
--+--+--+--+--+--+--+
m2¦ 1¦ 1¦ 1¦ ¦ 1¦ 0¦
--+--+--+--+--+--+--+
m3¦ ¦ 0¦ 0¦ 0¦ ¦ 0¦
--+--+--+--+--+--+--+
m4¦ 0¦ 0¦ 1¦ 1¦ ¦ 0¦
--+--+--+--+--+--+--+
m5¦ 0¦ 1¦ 0¦ 0¦ ¦ 0¦
--+--+--+--+--+--+--+
m6¦ ¦ 0¦ ¦ ¦ 0¦ 1¦
--¦--+--+--+--+--+---
Структура вычислителя:
---------------------------------¬
==>¦I1 ¦
¦ ¦
==>¦I2 ОА D¦==>
¦ ¦
---/C rO+-->
¦ ¦ ¦
¦ ¦z p umB uwA uwB uiA urO uwO ¦
¦ LT--T--A---A---A---A---A---A------
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
¦ -V--V--+---+---+---+---+---+-----¬
¦ ¦z p y1 y2 y3 y4 y5 y6 ¦
¦ ¦ ¦
+--/C ¦
¦ УА ¦
-->+rI ¦
L---------------------------------
УА должен выполнять следующий алгоритм автоматного типа,
представленный в виде блок-текста:
m1{xxxx10}
g1<<GO(rI;g1,m2)>>
m2{111x10}
m3{x000x0}
<<GO(z;g2,m6)>>
g2<<GO(p;m4,m5>>
m4{0011x0}
<<GO m3>>
m5{0100x0}
<<GO m3>>
m6{x0xx01}
<<GO g1>>
МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ.
МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ-
ходимое для получения (вычисления) значения одной или более
переменных.
Микрооперация присваивания В=А означает, что переменные
левой части получают значения выражения из правой части.
Всегда разрядность левой части равна разрядности правой час-
ти. При этом биты, расположенные на одной и той же позиции в
левой и правой частях, равны.
Неиспользуемые разряды в левой части и произвольные зна-
чения в правой части микрооперации присваивания обозначаются
(х). Например:
(В[7],x,B[6..0]) = (A[7..0],x)
означает арифметический сдвиг влево на один разряд 8-разряд-
ного числа с присваиванием произвольного значения младшему
разряду и с потерей старшего после знака разряда. А, напри-
мер, микрооперация
(B[7..0],d) = (A[7],A[7..0])
означает арифметический сдвиг вправо на один разряд.
Микрооперация
(p,S[3..0]) = A[3..0] + B[3..0] + q
описывает действие, выполняемое стандартным 4-разрядным сум-
матором, если ( А,В,q ) являются его непосредственными входа-
ми, а ( р,S ) - выходами.
Микрооперация ( : ) - двоеточие - означает запоминание
(изменение значения) в памяти устройства. Переменная типа па-
мять сохраняет свое значение между двумя очередными присва-
иваниями.
Микрооперации всегда входят в состав микрооператоров.
МИКРООПЕРАТОР - набор взаимосвязанных микроопераций (или
одна микрооперация ), выполняемых одновременно и необходимых
для получения одного или более значений. Например:
( e,D:) = R1 + R2 + c
Фрагмент аппаратуры, реализующей этот микрооператор, мог бы
быть, например, таким:
----¬
c ¦MUX¦
-T--T¬ ¦ ¦ ----¬
¦¦T ¦+--->+0 ¦ -----¬ ¦MUX¦ D
L+--+- -->+1 ¦ ¦ SM¦ ¦ ¦ -T--T¬
-->+А +--->+cr ¦ ===>¦0 ¦===>¦¦RG¦¦==>
+---+ ¦ S¦=====>¦1 ¦ L+--+-
R1 ¦MUX¦ ¦ ¦ ===>¦А ¦
-T--T¬ ¦ ¦ ¦ ¦ L----
¦¦RG¦¦===>¦0 ¦===>¦I1 ¦ ----¬
L+--+- ==>¦1 ¦ ¦ ¦ ¦MUX¦
==>¦А ¦ ¦ ¦ ¦ +------------>e
+---+ ¦ p+----->+0 ¦
R2 ¦MUX¦===>¦I2 ¦ --->+1 ¦
-T--T¬ ¦ ¦ L----- --->+А ¦
¦¦RG¦¦===>¦0 ¦ L----
L+--+- ==>¦1 ¦
==>¦А ¦
L----
Имена всех переменных, используемых в этом микрооператоре,
означают выполнение микроопераций коммутации ( транспортиров-
ки ). Значения переменных коммутируются на входы суммматора,
а результат суммирования - в места расположения переменных.
МИКРОБЛОК - набор микрооператоров, выполняемых одновре-
менно ( в одном такте ) и синхронно. В одном микроблоке любо-
му из битов присваивается только одно значение.
Синхронность означает, что во всех микрооператорах одно-
го микроблока используется только "старое" значение памяти.
Например:
{ (p,A):= A + B
(C,r):= A + D }
- и в том, и в другом микрооператоре используется одно и то
же старое значение А.
В то же время в микроблоке:
{ (C,x):= A + D
(x,A)= C + B }
в первом микрооператоре используется новое значение А , а во
втором - старое значение С. Разумеется, эти два действия вы-
полняются одновременнo на двух разных сумматорах.
При реализации микроблока { A:= B ; B:= 0 } обязательна
синхронная реализация В:=0 ( хотя обычно такое действие проще
реализовать асинхронно, но это приводит к ошибке ). Другой
правильный вариант: можно выполнить В:=0 асинхронно, но в
следющем такте.
Всегда предполагается, что предикат вычисляется вместе
(в одном такте) с тем микроблоком, за которым непосредственно
следует его использование.Таким образом, здесь, также как и в
микроблоке, используется старое значение памяти, существовав-
шее перед входом в микроблок. Это связано с особенностями
взаимодействия ОА и УА. Например:
- -
- CT:=(+0)- - CT:=(+0)-
- -
¦ ¦
-----V---¬ -----V---¬
m1¦ CT:=3 ¦ m1¦ CT:=3 ¦
L----T---- L----T----
------->¦ ------->¦
¦ -V- ¦ -V-
¦ / \ =0 ¦ / \ =0
¦ <CT==0>-> ¦ <CT==0>->
¦ \___/ ¦ \___/
¦ ¦+0 ¦ ¦+0
¦ -----V---¬ ¦ -----V---¬
¦m2¦........¦ ¦m2¦........¦
¦ ¦ ¦ ¦ ¦ ¦
¦ ¦CT:=CT-1¦ ¦ ¦CT:=CT-1¦
¦ L----T---- ¦ L----T----
L-------- ¦ -----V---¬
¦m3¦........¦
¦ L----T----
L--------
В первом случае цикл будет выполнен 4 раза; во втором - если
в микроблоке m3 нет операций, модифицирующих СТ, - 3 ра-
за. ( Обратите внимание на начальное значение СТ!)
МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и
интерпретируемый как управляющий,т.е. необходимый для выпол-
нения всех микроопераций одного микроблока. Сигналы, входящие
в микрокоманду, могут принимать участие в микрооперациях и в
качестве информационных.
Микрокомандой также иногда называют слово управляющей
памяти (обычно ПЗУ), являющееся частью УА. Для различения
этих понятий слово управляющей памяти будем называть МИКРО-
ИНСТРУКЦИЕЙ.
МИКРОПРОГРАММА СОДЕРЖАТЕЛЬНАЯ - алгоритм, представленный
в виде микроблоков и предикатных блоков в одной из принятых
форм, например, в виде блок-схемы или блок-текста.
МИКРОПРОГРАММА КОДИРОВАННАЯ - аппаратная форма содержа-
тельной микропрограммы в виде кодов, заполняющих управляющую
память.
КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА
В общем случае каноническая структура операционного ав-
томата имеет вид:
-----------------------------------------------------------
- -
- -----------¬ -T------T¬ -----------¬ --------¬ -
-->¦коммутация¦ ¦¦память¦¦ ¦коммутация¦ ¦функции¦---
¦ ¦--->¦¦ ¦¦-->¦ ¦-->¦ ¦
-->¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦--->
L-A--------- -/-++---A--+- L--A-------- L--A-----
- --¬¦CC - - -
- SYN->+&+- - - -
- -+ ¦ - - -
- yC¦L-- - - -
L-------------------------------------------------
сигналы управления
Столь четкого разграничения операций на зоны (память, комму-
тация, функции) может и не быть. Например, такие широко ис-
пользуемые функции как сдвиги либо хорошо совмещаются с
коммутацией, либо интегрируются с регистрами хранения.Также
часто интегрируются с хранением функции инкремента и
декремента (счетчики обычные и реверсивные).
Особо выделим сигнал yС, управляющий доступом синхросиг-
налов в ОА. Такой вариант управления, называемый условной
синхронизацией, позволяет запретить любые изменения памяти ОА
в каком-либо такте. Причем, если рабочим является срез (зад-
ний фронт) сигнала синхронизации, то используется элемент И,
как и показано на рисунке.Если же рабочим является фронт (пе-
редний фронт) сигнала, то используется элемент ИЛИ. (Первый
перепад сигнала синхронизации в новом такте не должен быть
рабочим.)
ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА
При проектировании вычислительного устройства основными
являются ограничения на:
1)- время вычисления;
2)- объем аппаратуры, реализующей вычисления;
3)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальным по-
тенциальным параллелизмом (в рамках данной алгоритмической
идеи), и,следовательно, его реализация в виде КС обладает
максимальным быстродействием по сравнению с любыми другими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представление и его реализация являются
статическим отображением входных объектов на выходные: это
исключает возможность работы с объектами, которые "ведут се-
бя" более сложно во времени; невозможно также реализовать
принципиально рекуррентные алгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритм функционального
типа может быть записан, то проектирование устройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом на про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из них в один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменных (входных
и выходных),связанных с выполнением этих операций. Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений - но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простую модель в виде направленного
графа. Вершины графа будут соответствовать операциям, а дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный граф всегда будет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо на аль-
тернативных путях решения.
МИНИМИЗАЦИЯ АППАРАТУРЫ
Может оказаться, что на одном пути в сигнальном графе
расположены операции, плохо или вовсе не совмещаемые друг с
другом (т.е. совмещение не дает экономии в аппаратуре функци-
онального модуля). Возможно также, что проведенная минимиза-
ция, сохраняющая минимальное время, не позволяет выполнить
ограничение на объем аппаратуры. В таком случае необходима
более глубокая минимизация,охватывающая параллельные ветви
сигнального графа. Минимизация должна быть взаимосвязанной по
всем компонентам ОА: по памяти, функциональным модулям и ком-
мутации.
В настоящее время процедуры минимизации не формализованы
и сводятся к перебору "правдоподобных" вариантов.
Можно предложить следующую последовательность действий:
1)- все "похожие" функции (операции) реализовать на одном
функциональном модуле, например, все суммирования выполнять
на одном сумматоре;
2)-скорректировать алгоритм так, чтобы в одном микроблоке не
выполнялось более одной операции на одном и том же функци-
ональном модуле;
3)- минимизировать память автомата, т.е. число запоминаемых
промежуточных переменных;
Выполнение этих этапов может привести к усложнению ком-
мутации, а значит, и к увеличению этой компоненты в аппарату-
ре ОА. Если ограничение по объему аппаратуры все еще наруше-
но, то повторить этапы 1 - 3 с другим вариантом объединения
функциональных модулей и памяти.
При реализации ОА - во избежание ошибок -необходимо бук-
вально следовать описанию алгоритма, но в то же время, при
проектировании самого алгоритма надо представлять себе реали-
зацию микроблоков. Реализация одних и тех же вычислений может
быть существенно различной по объему аппаратуры.
Например, вычисления в цикле потребуют реализации:
-T-
¦
--------V-------¬ A -----¬
¦ J:=0 ¦ -T--T-¬ ¦ MUX¦ -----¬
L-------T-------- ¦¦RG¦0+--->+0 ¦ ¦ f ¦
-------¬ ¦ ¦¦ ¦.¦ . ¦. ¦A[J] ¦ ¦
¦ -----V--V-------¬ ¦¦ ¦.¦ . ¦. +---->+ ¦
¦ ¦ ..... ¦ ¦¦ ¦.¦ . ¦. ¦ ¦ ¦ B
¦ ¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦==>
¦ ¦ B= f(...,A[J])¦ ¦¦ ¦K+--->+K ¦ ¦ ¦
¦ ¦ ¦ ¦¦ ¦.¦ ¦. ¦ ==>¦ ¦
¦ ¦ J:=J+1 ¦ ¦¦ ¦.¦ ¦. ¦ ¦ ¦
¦ L-------T-------- ¦¦ ¦.¦ ¦. ¦ ¦ ¦
¦ -V- L+--+-- +- ¦ L-----
¦ <K / \ =K J=========>¦А ¦
L------<J==K>-----> L-----
\__/
(реализация счетчика J не показанa).
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре D. Тогда получим:
---T-- A D
¦ -T--T¬ -T--T-¬ A[J] ------¬
--------V-------¬ ¦¦RG¦¦ ¦¦RG¦0+----->+ f ¦
¦ J:=0 ¦ ¦¦ ¦¦ ¦¦ ¦.¦ ¦ ¦
¦ ¦ ¦¦ ¦¦ ¦¦->¦.¦ ¦ ¦ B
¦ D:=A ¦ ¦¦ ¦¦======>¦¦ ¦.¦ ¦ ¦==>
L-------T-------- ¦¦ ¦¦ ¦¦ ¦ ¦ ¦ ¦
-------¬ ¦ ¦¦ ¦¦ ¦¦ ¦K+ ¦ ¦
¦ -----V--V-------¬ ¦¦ ¦¦ x -->+Dn ¦.¦ ¦ ¦
¦ ¦ ..... ¦ ¦¦ ¦¦ ¦¦ ¦.¦ ==>¦ ¦
¦ ¦ ¦ ¦¦ ¦¦ S W¦¦ ¦.¦ ¦ ¦
¦ ¦ B= f(...,D[0])¦ L+--+- -v-v++--+-- L------
¦ ¦ ¦
¦ ¦ (D,x):=(x,D) ¦
¦ ¦ ¦
¦ ¦ J:=J+1 ¦
¦ L-------T--------
¦ -V-
¦ <K / \ =K
L------<J==K>----->
\__/
Промежуточный регистр A введен для общности, если потребуется
сохранить слово А (чаще всего он и не нужен).
Другой пример: фрагмент алгоритма, реализующий регуляр-
ную запись отдельных бит слова и его реализация имеют вид:
---T-- -T-T¬B[0]
¦ a ------------T----->+¦T¦+---->
--------V-------¬ ¦ W¦¦ ¦¦
¦ J:=0 ¦ ----¬ ¦ -A++-+-
L-------T-------- ¦DC ¦ ---+------| |
-------¬ ¦ ¦ 0+-- ¦ | |
¦ -----V--V-------¬ ¦ .¦. ¦ -T-T¬B[K]
¦ ¦ ..... ¦ ¦ .¦. L----->+¦T¦+---->
¦ ¦ ¦ ¦ .¦. W¦¦ ¦¦
¦ ¦ a=f(...) ¦ J ==>¦ ¦ -A++-+-
¦ ¦ ¦ ¦ K+-----------
¦ ¦ B[J]:=a ¦ ¦ .¦
¦ ¦ ¦ ¦ .¦
¦ ¦ J:=J+1 ¦ ¦ .¦
¦ L-------T-------- L----
¦ -V-
¦ <K / \ =K
L------<J==K>----->
\__/
Слово В нельзя реализовать в виде регистра, а только в виде
отдельных триггеров.
Можно формировать слово с использованием операции сдви-
га при обязательном условии D[K..0], тогда алгоритм и его ре-
ализация имеют вид:
---T--
¦ D B
--------V-------¬ ---T--T¬ -T--T¬
¦ J:=0 ¦ ¦ ¦RG¦¦ ¦¦RG¦¦
L-------T-------- ¦ ¦->¦¦ ¦¦ ¦¦
-------¬ ¦ a ¦ ¦ ¦¦=====>¦¦ ¦¦
¦ -----V--V-------¬ -->+Dk¦ ¦¦ ¦¦ ¦¦
¦ ¦ ..... ¦ S¦ ¦ ¦¦ W¦¦ ¦¦
¦ ¦ ¦ -v+--+--+- -v++--+-
¦ ¦ a=f(...) ¦
¦ ¦ ¦
¦ ¦ (D,x):=(a,D) ¦
¦ ¦ ¦
¦ ¦ J:=J+1 ¦
¦ L-------T--------
¦ -V-
¦ <K / \ =K -----¬
L------<J==K>-->+B:=D+>
\__/ L-----
В этом случае, так же, как и в предыдущем, чаще всего не ну-
жен промежуточный регистр (В).
УНИВЕРСАЛЬНЫЙ ОА
Использование при проектировании универсальных ОА с за-
ранее фиксированной и минимизированной структурой оправдано
тем, что такие универсальные ОА изготавливаются промышлен-
ностью в виде БИС большим тиражом и поэтому они сравнительно
дешевы. Такие универсальные ОА входят в микропроцессорные на-
боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на-
зываются микропрограммируемыми, секционными, разрядно-модуль-
ными.
В основе перечисленных универсальных ОА лежит следующая
структура:
г==================T===========================¬
¦ ¦ ¦
¦ ¦ SYN¬ ACC ¦
¦ --T-----T¬ ¦ -/TT--T¬ ------¬ ¦
¦ ¦ ¦ RGF ¦¦ ¦ C¦¦RG¦¦ ¦ ALU ¦ ¦
¦ ¦ ¦ ¦¦ ¦ ¦¦ ¦¦ ¦ ¦ ¦
¦ ¦ ¦ ¦¦ L====>¦¦ ¦¦=====>¦ ¦ ¦
¦ ¦ ¦ ¦¦ ¦¦ ¦¦ ¦ ¦===¦=>DO
L===>¦D¦ ¦¦ L+--+- ¦ ¦
¦ ¦ ¦¦ T ¦ ¦
¦ ¦ ¦¦ -T--T¬ ¦ ¦=====>P
¦ ¦ ¦¦ ¦¦RG¦¦ ¦ ¦
¦ ¦ ¦¦=========>¦¦ ¦¦=====>¦ ¦
¦ ¦ ¦¦ ¦¦ ¦¦ ¦ ¦
C W¦А¦ ¦¦ C¦¦ ¦¦ г=>¦ ¦
-o-A+A+-----+- -T++--+- ¦ L--A---
SYN- ¦ ¦ SYN- ¦ ¦
¦ ¦ ¦ ¦
yW YA DI=====- YF
ALU - арифметико-логическое устройство - комбинационная
схема с небольшим, но универсальным набором арифметических и
логических операций.
RGF - регистровый файл - адресуемая память RAM со стати-
ческой синхронизацией при записи.
RG'T' - регистр-фиксатор со статической синхронизацией.
RG'АCC' - регистр-аккумулятор с динамической синхрониза-
цией.
DI,DO - входная и выходная информационные шины.
Р - предикатные сигналы (флажки).
YF - сигналы управления выбором функции.
YA - адрес чтения и/или записи RGF.
yW - разрешение записи в RGF.
Память сравнительно большого объема, какой является RGF,
дешевле реализовать со статической синхронизацией. Для то-
го,чтобы такая память могла работать в замкнутом информацион-
ном кольце и при этом не возникали бы гонки, добавляется еше
один промежуточный регистр RG'T' со статической синхрониза-
цией. Если передний фронт является рабочим для регистров уп-
равляющего автомата и RG'ACC', то на первой фазе синхрониза-
ции при SYN=1 информация читается из RGF; при этом RG'T'
прозрачен. На следующей фазе синхронизации при SYN=0 информа-
ция фиксируется в RG'T', т.е. он закрыт для записи, а запись
(если она разрешена) производится в RGF. Фиксируется информа-
ция в RGF и RG'ACC' с началом следующего такта, т.е. на пе-
реднем фронте сигнала.
ВЗАИМОДЕЙСТВИЕ ОА и УА
Для исключения гонок при взаимодействии ОА и УА будем
проектировать УА как автомат Мура. Схема их взаимодействия
может быть представлена в виде:
г==========================¬
¦-----¬ -T--T¬ -----¬ ¦
L¦ CS ¦ ¦¦RG¦¦ ¦CS ¦<-
¦ ¦<=T=¦¦ ¦¦<==¦ ¦
----+ b ¦ ¦ ¦¦ ¦¦ ¦ c +<----¬
¦ L----- ¦ L+--++A- L----- ¦
¦ -----¬ ¦ L-----------¬ ¦
¦ ¦CS ¦<=- ¦ ¦
¦---+ a +<-------------------¬ ¦ ¦
ОА ¦¦ L----- ¦ ¦ ¦
----¦¦----------------------------¦-¦-¦--
УА ¦¦РА-----¬ -T--T¬ ------¬¦ ¦ ¦¬
¦L->+ CS¦ ¦¦RG¦¦ ¦ CS +- ¦ ¦¦
L-->+ ¦====>¦¦ ¦¦=>¦ +--- ¦¦Y
РВ ¦ ¦ ¦¦ ¦¦ ¦ +-----¦
г>¦ p ¦ ¦¦ ¦¦ ¦ y ¦=¬ -
¦ L----- L+--+- L------ ¦
L============================-
Отметим, что РА(t)=f(Y(t)) зависит без сдвига от сигналов
управления,
PB(t+1)=F(Y(t)) зависит со сдвигом от сигналов
управления,
где РА и РВ - предикатные перемнные.
Продолжительность такта работы схемы определяется наибо-
лее длинными цепями между регистрами. Для данной схемы, кото-
рую будем называть последовательной схемой взаимодействия,
зададимся (так чаще всего бывает), что такой критической
цепью является цепь (CSy,CSa,CSp,RG). Поэтому длительность
такта определяется:
Т > ty + ta + tp + trg,
где tj- время установления соответствующего компонента цепи.
Чтобы сократить длину этой цепи, применяют другой вари-
ант взаимодействия автоматов - конвейерный:
г==========================¬
¦-----¬ -T--T¬ -----¬ ¦
L¦ CS ¦ ¦¦RG¦¦ ¦CS ¦<-
¦ ¦<=T=¦¦ ¦¦<==¦ ¦
------------+ b ¦ ¦ ¦¦ ¦¦ ¦ c +<----¬
¦ FF L----- ¦ L+--++A- L----- ¦
¦ -T--T¬ -----¬ ¦ L-----------¬ ¦
¦--+¦RG¦¦<==¦ CS ¦<=- ¦ ¦
¦¦ ¦¦ ¦¦ ¦ a +<-------------------¬ ¦ ¦
¦¦ L+--++A- L----- ¦ ¦ ¦
ОА ¦¦ L--------------------------¬ ¦ ¦ ¦
---¦¦----------------------------------¦-¦-¦-¦--
УА ¦¦ MK ¦ ¦ ¦ ¦
¦¦ PA -----T----¬ -T--T¬¦ ¦ ¦ ¦¬
¦L---->+ CS¦ CS ¦ ¦¦RG¦+- ¦ ¦ ¦¦
¦ РВ ¦ ¦ ¦ ¦¦ ¦+--- ¦ ¦¦Y
L----->+ ¦ ¦===========>¦¦ ¦+----- ¦¦
¦ ¦ ¦ ¦¦ ¦+-------¦
г>¦ p ¦ y ¦ ¦¦ ¦¦=¬ -
¦ L----+----- L+--+- ¦
L===============================-
При этом варианте взаимодействия такой длинной цепи, как
в предыдущем случае, не возникает.Эта цепь разделена регис-
трами RG'FF' (регистр флажков) и RG'MK' (регистр микрокоман-
ды) на две цепи. Продолжительность такта становится меньше и
ее можно определить следующим образом:
T > max( ta,(tp + ty) )+ trg ,
При конвейерном варианте взаимодействия
PA(t+1)=f(Y(t)), т.е. и эти значения стали зависить со
сдвигом от сигналов управления. Тогда фрагмент микропрограммы
mS{...;pA=f(...)}
<< GO(pA;mi,mj)>>,
выполняемый в последовательной схеме за один такт, в кон-
вейерном варианте за один такт выполнен быть не может и дол-
жен быть модифицирован следующим образом:
mS{...,pA=f(...)}
mS'{нет операции}
<< GO(pA;mi,mj)>>
Таким образом, время выполнения этого фрагмента не только не
уменьшилось, но даже возросло несмотря на уменьшение продол-
жительности каждого из тактов. Зато во всех остальных случа-
ях (при безусловных переходах, при переходах по значению РВ)
время выполнения микропрограммы уменьшается.
НАЧАЛЬНАЯ ИНИЦИАЛИЗАЦИЯ СИНХРОННОЙ СХЕМЫ
Пусть устройство, кроме сигнала синхронизации SYN, имеет
еще один сигнал Н, обозначающий начало и конец синхронной ра-
боты устройства. При Н=0 - нерабочее состояние - можно выпол-
нять начальную установку значений памяти устройства. Измене-
ние значения Н с 0 на 1 происходит в случайный момент времени
(асинхронно), но при этом начальный такт работы устройства
должен быть полным. "Затягивание" асинхронного сигнала Н в
синхронный режим происходит с помощью простейшего синхронного
автомата с диаграммой:
-----------¬ ---------¬
V 0H/CONST¦ V 1H/SYN¦
-------------- ------------
>¦ 0 ¦-------------->¦ 1 ¦------¬
----- 1H/CONST ----- 0H/X ¦
л ¦
L-----------------------------
У этого автомата простейшей является функция переходов, так
как диаграмма автомата совпадает с диаграммой переходов
D-триггера.
Схема автомата вместе с цепями условной синхронизации
выглядит следующим образом (для синхронизации по фронтам):
а)-по переднему фронту, б)- по заднему фронту:
---¬ ---¬
SYN --T----------+ 1+-- CC SYN --T----------+ &+-- CC
¦ --T-¬ --+ ¦ ¦ --T-¬ --+ ¦
L-/C¦T¦ ¦ L--- L-\C¦T¦ ¦ L---
¦ ¦ + ¦ ¦ ¦ +---
--+D¦ ¦ ¦ --+D¦ ¦
¦ +-+ o--- ¦ +-+ o-
+-oR¦ ¦ +-oR¦ ¦
H ¦ L-+--уст. нач. зн. H ¦ L-+--уст. нач. зн.
--+------------------- --+-------------------
Такая разница в цепях условной синхронизации, как уже объяс-
нялось выше, определяется тем, что первый перепад сигнала СС
не должен быть рабочим.
_
ЛИТЕРАТУРА
0. Любые литературные источники, рекомендованные по дис-
циплине "Основы дискретной математики".
1. Токхейм Р. Основы цифровой электроники.-М.: Мир,'88
2. Каган Б.М. Электронные вычислительные машины и систе-
мы.-М.: Энергоатомиздат, 1991 - 340 с.
3. Цифровая и вычислительная техника /под ред. Э.В.Евре-
инова.-М.: РиС,1991.-464с.
4. Майоров С.А., Новиков Г.И. Структура электронных вы-
числительных машин.-Л.: Машиностроение, 1979 - 384 с.
5. Самофалов К.Г., Романкевич А.М., Валуйский А.М. Прик-
ладная теория цифровых автоматов.-К.: Вища шк. 1987 - 470 с.
6. Савельев А.Я. Прикладная теория цифровых автоматов.
-М.: Высшая школа, '87
7. Рабинович З.Л. Основы теории элементарных структур
ЭВМ. -М.: РиС, '82 - 280 с.
8. Рабинович З.Л., Раманаускас В.А. Типовые операции в
вычислительных машинах. Киев: Техника, '80 - 264 с.
9. Карцев М.А. Арифметика цифровых машин. -М.: Наука,'69
- 575 с.
10. Карцев М.А., Брик В.А. Вычислительные системы и син-
хронная арифметика. -М.: РиС, '81 - 360 с.
11. Байков В.Д., Смолов В.Б. Специализированные процес-
соры: итерационные алгоритмы и структуры. М.:РиС,1985 - 288с.
12. Баранов С.И. и др. Цифровые устройства на программи-
руемых БИС с матричной структурой.-М.:РиС,1986-272 с.
13. Баранов С.И. Синтез микропрограммных автоматов. -Л.:
Энергия, 1979 - 232 с.
14. Баранов С.И., Скляров В.А. Цифровые устройства на
программмируемых БИС с матричной структурой. -М.: РиС '86 -
272 с.
15. Клингман Э. Проектирование специализированных микро-
процесссорных систем.-М.: Мир, 1985.- 363 с.
16. Проектирование цифровых систем на комплектах микро-
программируемых БИС /Под ред. В.Г.Колесникова.-М.: Радио и
связь, 1984.- 240 с.
17. Мик Дж., Брик Дж. Проектирование микропроцессорных
устройств с разрядно-модульной организацией. Т.1.-М.: Мир,
1984.- 253 с.
18. Потемкин И.С. Функциональные узлы цифровой автомати-
ки. -М.: Энергоатомизд.,'88 - 320 с.
19. Угрюмов Е.П. Проектирование элементов и узлов ЭВМ.
-М.:ВШ,1987.-318 с.
20. Букреев И.Н.,Горячев В.Н.,Мансуров Б.М. Микроэлек-
тронные схемы цифровых устройств.-М.:РиС,1990-416с.
21. Пухальский Г.И.,Новосельцева Т.Я. Проектирование
дискретных устройств на интегральных микросхемах:Справочник.
-М.:РиС,1990-304с.
22. Шило В.Л. Популярные цифровые микросхемы:Справочник.
-М:РиС,1987-352с.
23. Применение интегральных микросхем в электронной вы-
числительной технике:Справочник/под ред. Б.Н.Файзулаева,
Б.В.Тарабрина. -М:РиС,1986-384с.
24. Закревский А.Д. Логический синтез каскадных схем.
-М.: Наука, 1981 - 414 с.
25. Фридман А.,Менон П. Теория и проектирование переклю-
чательных схем. -М:Мир,1978-580с.
26. Гилл А. Введение в теорию конечных автоматов. -М.:
Наука '66 - 272 c.
27. Гилл А. Линейные последовательностные машины. -М.:
Наука '74 - 288 с.
28. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение
в теорию автоматов.-М.: Наука '85 - 320 с.
29. Марков А.Я. Введение в теорию кодирования.-М.: Наука
'82 - 192 с.
30. Ангер С. Асинхронные последовательностные схемы.
-М:Наука,1977-400с.
31. Апериодические автоматы /под ред. Варшавского В.И.
-М:Наука,1976,-423с.
32. Автоматное управление асинхронными процессами в ЭВМ и
дискретных системах /под ред. Варшавского В.И. -М:На-
ука,1986,-400с.
_
Антик М.И. 11_03_91 МИРЭА
УПРАВЛЯЮЩИЕ АВТОМАТЫ.
ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД
Начнем с рассмотрения простейшего варианта управления, в
котором не участвуют предикатные функции (переменные), т.е. в
микропрограмме переходы только безусловные. В таком случае УА
является автономным синхронным автоматом.
В более общем случае функция переходов УА зависит от
предикатных переменных, но УА должен быть автоматом Мура.
Условимся о некоторых ограничениях, позволяющих упрос-
тить схему на начальных этапах проектирования (от которых
легко впоследствии и отказаться):
- на каждом шаге процесса вычислений ветвление может осу-
ществляться только по одной двузначной предикатной перемен-
ной (т.е. разветвление возможно лишь на два направления);
- начальные значения всех регистров УА являются нулевыми.
Впредь на схемах УА не будем показывать цепей установки на-
чальных значений.
Для реализации в самом общем случае микропрограмм произ-
вольной структуры будем строить УА так, чтобы основным мате-
риальным носителем управляющей (автоматной) компоненты мик-
ропрограммы являлась бы управляющая память (реализованная,
например, в виде ПЗУ). В этом случае структура слова управля-
ющей памяти - МИКРОИНСТРУКЦИЯ - состоит из двух составных
частей: микрокоманды и адресной части.
Адресная часть микроинструкции содержит информацию, поз-
воляющую в следующем такте работы выбрать ( указать ) новый
адрес управляющей памяти. Реализация именно этого момента яв-
ляется основным предметом дальнейшего рассмотрения и опреде-
ляет, в основном, структуру, объем аппаратуры и быстродей-
ствие УА. При этом подлежит рассмотрению реализация следующих
типов переходов как между шагами алгоритма, так, соот-
ветственно, и между микроинструкциями:
- безусловный переход,
- условный переход,
- функциональный переход,
- переход к микроподпрограмме с возвратом.
Будем изучать работу управляющих автоматов различной
структуры, демонстрирующие основные применяемые варианты ад-
ресации микроинструкций, на следующем алгоритме:
---
----¬¦
¦ -VV-¬
n1¦ ¦m1 ¦ n1 { m1 }
¦ L-T--
¦ --V-¬ n2 { m2 }
n2¦ ¦m2 ¦
¦ L-T-- g1 <<GO(a;g1,n3)>>
¦ ¦<--¬
¦ -V¬ 0¦ n3 { m3 }
g1¦ < a >--
¦ LT- n4 { m4 }
¦ 1¦<----¬
¦ ¦----¬¦ g2 <<GO((a,b);n5,n3,n1,n1)>>
¦ --VV¬ ¦¦
n3¦ ¦m3 ¦ ¦¦ n5 { m5 }
¦ L-T-- ¦¦
¦ --V-¬ ¦¦ g3 <<GO(a;n5,n3)>>
n4¦ ¦m4 ¦ ¦¦
¦ L-T-- ¦¦
¦10 -V¬ 01¦¦
g2L--< ab>---¦
11 LT- ¦
00¦----¬¦
--VV¬ ¦¦
n5 ¦m5 ¦ ¦¦
L-T-- ¦¦
-V¬ 0 ¦¦
g3 < a >---¦
LT- 1 ¦
L------
Укажем на некоторые особенности этого алгоритма: Опера-
тор перехода (предикатная вершина), помеченный меткой g1,
называют ждущим. Оператор, помеченный меткой g2, использует
для перехода 4-значный предикат, что не удовлeтворяет выше-
указанному ограничению. Поэтому потребуются эквивалентные
преобразования алгоритма для того, чтобы удовлетворить этому
ограничению.
Алогоритмы эквмвалентны, если они преобразуют информа-
цию одинаковым образом. Наиболее распространенным приемом эк-
вивалентного преобразования алгоритмов и микропрограмм явля-
ется включение микроблоков и, соответственно, тактов, в кото-
рых не выполняется модификация памяти ОА - "нет операции".
Но и это преобразование может быть не эквивалентным - см.при-
мер при определении понятия "микроблок"; кроме того, следует
учесть различное поведение во времени предикатных переменных
типа "РА" и "РВ" - см. раздел "Взаимодействие ОА и УА".
( Запретить модификацию памяти можно, вводя условную
синхронизацию ОА, но для этого должна быть изменена микроко-
манда, предшествующая добавляемому такту.)
СХЕМА С АДРЕСНЫМ ПЗУ
Начнем рассмотрение с управляющего автомата, структура
которого совпадает с канонической структурой автомата Мура.
----¬ ----¬ -T--T¬ ----¬
¦MUX¦ q ¦ROM¦ ¦¦RG¦¦ ¦ROM¦
a->+0 +-->+ ¦ S' ¦¦ ¦¦ S ¦ ¦ Y
b->+1 ¦ ¦ ¦===>¦¦ ¦¦=T>¦ ¦==>
¦ ¦ г>¦ ¦ ¦¦ ¦¦ ¦ ¦ +-¬
¦А ¦ ¦ ¦ 2 ¦ C¦¦ ¦¦ ¦ ¦ 1 ¦ ¦
LA--- ¦ L---- -/++--+- ¦ L---- ¦
¦ H L=================- ¦
L-------------------------------
Функцию перехода и функцию выхода реализуем в виде ПЗУ.
В литературе, рассматривающей микропрограммные устройства уп-
равления, УА с такой структурой называют микропрограммным ав-
томатом Уилкса.
В ПЗУ (ROM_1), реализующем функцию выхода, следует раз-
местить микрокоманды; при этом их распределение по определен-
ным адресам совершенно произвольно, за исключением начальной
микрокоманды, которая в силу вышеуказанного ограничения дол-
жна располагаться по нулевому адресу.
ПЗУ (ROM_2), реализующее функцию переходов автомата,
можно трактовать как адресное ПЗУ. Ячеек в адресном ПЗУ в два
раза больше, чем в ПЗУ микрокоманд. Каждой ячейке ПЗУ микро-
команд соответствуют две ячейки в адресном ПЗУ, в которых за-
писываются два альтернативных адреса.
n1 { m1 } S¦ Y H¦ S q¦S'¦
-+----+ ---+--+
n2 { m2 } 0¦m1 x¦ 0 0¦ 1¦
¦ ¦ 0 1¦ 1¦
<<GO(a;d1,n3)>> ¦ ¦ ¦ ¦
1¦m2 0¦ 1 0¦ 2¦
d1 { m0 } ¦ ¦ 1 1¦ 3¦
¦ ¦ ¦ ¦
<<GO(a;d1,n3)>> 2¦m0 0¦ 2 0¦ 2¦
¦ ¦ 2 1¦ 3¦
n3 { m3 } ¦ ¦ ¦ ¦
3¦m3 x¦ 3 0¦ 4¦
n4 { m4 } ¦ ¦ 3 1¦ 4¦
¦ ¦ ¦ ¦
<<GO(a;d2,n1)>> 4¦m4 0¦ 4 0¦ 5¦
¦ ¦ 4 1¦ 0¦
d2 { m0 } ¦ ¦ ¦ ¦
5¦m0 1¦ 5 0¦ 6¦
<<GO(b;n5,n3)>> ¦ ¦ 5 1¦ 4¦
¦ ¦ ¦ ¦
n5 { m5 } 6¦m6 0¦ 6 0¦ 6¦
¦ ¦ 6 1¦ 4¦
<<GO(a;n5,n3)>> -+----- ---+---
Конвейерный вариант схемы с таким же способом адресации
должен программироваться с учетом замечаний, сделанных в раз-
деле "Взаимодействие ОА и УА". Кроме того, ограничения на
расположение микрокоманд в ROM_1 выглядят несколько иначе: по
0-адресу в ROM_1 можно расположить микрокоманду, после кото-
рой безусловно выполняется начальная микрокоманда.
----¬ q ----¬ ----¬ -T--T¬
¦MUX+---------->+ROM¦ ¦ROM¦Y ¦¦RG¦¦ Y'
a->+0 ¦ C ¦ ¦ S ¦ ¦==>¦¦ ¦¦==>
b->+1 ¦ -/TT--T¬ ¦ ¦=T>¦ ¦H ¦¦ ¦¦
¦ ¦ г>¦¦RG¦¦=>¦ ¦ ¦ ¦ +-->+¦ ¦+¬
¦А ¦ ¦ ¦¦ ¦¦S'¦ 2 ¦ ¦ ¦ 1 ¦ C¦¦ ¦¦¦
LA--- ¦ L+--+- L---- ¦ L---- -/++--+-¦
¦H' L===============- ¦
L-------------------------------------
СХЕМА С ЯВНЫМ УКАЗАНИЕМ АЛЬТЕРНАТИВНЫХ АДРЕСОВ
г===========================¬
¦г=========================¬¦
¦¦ ----¬ -T--T¬ ----¬A0¦¦
¦¦ ¦MUX¦ ¦¦RG¦¦ ¦ROM¦==-¦
¦L>¦0 ¦ ¦¦ ¦¦A ¦ ¦A1 ¦
----¬L=>¦1 ¦===>¦¦ ¦¦=>¦ ¦===-
¦MUX¦ ¦ ¦ ¦¦ ¦¦ ¦ ¦==>Y
a->+0 ¦ ¦А ¦ C¦¦ ¦¦ ¦ +¬
b->+1 ¦ LA--- -/++--+- L----¦H
¦А +----- ¦
LA--- ¦
L-----------------------------
Конвейерный вариант
г============================¬
¦г==========================¬¦
¦¦ ----¬ -----¬A0 -T--T¬A0'¦¦
¦¦ ¦MUX¦ ¦ROM ¦==>¦¦RG¦¦===-¦
¦¦ ¦ ¦ ¦ ¦A1 ¦¦ ¦¦A1' ¦
¦L>¦0 ¦A ¦ ¦==>¦¦ ¦¦====-
----¬L=>¦1 ¦=>¦ ¦ Y ¦¦ ¦¦ Y'
¦MUX¦ ¦ ¦ ¦ ¦==>¦¦ ¦¦==>
¦ ¦ ¦ ¦ ¦ ¦ H ¦¦ ¦¦
a->+0 ¦ ¦А ¦ ¦ +-->+¦ ¦+¬H'
b->+1 ¦ LA--- L----- -/++--+-¦
¦А +----- C ¦
LA--- ¦
L-----------------------------
Эта схема отличается от предыдущей тем, что, по сущес-
тву, тот же способ адресации выполнен с использованием только
одного ПЗУ. В этом варианте альтернативные адреса записывают-
ся в той же микроинструкции, что и микрокоманда.
n1 { m1 } A¦ Y H A0 A1¦
-+----------+
n2 { m2 } 0¦m1 x 1 1¦
¦ ¦
<<GO(a;d1,n3)>> 1¦m2 0 2 3¦
¦ ¦
d1 { m0 } 2¦m0 0 2 3¦
¦ ¦
<<GO(a;d1,n3)>> 3¦m3 x 4 4¦
¦ ¦
n3 { m3 } 4¦m4 0 5 0¦
¦ ¦
n4 { m4 } 5¦m0 1 6 4¦
¦ ¦
<<GO(a;d2,n1)>> 6¦m5 0 6 4¦
-+-----------
d2 { m0 }
<<GO(b;n5,n3)>>
n5 { m5 }
<<GO(a;n5,n3)>>
СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ АДРЕСА
Последовательный вариант Конвейерный вариант
-------------------------¬ --------------------------¬
¦ ----¬ -T--T¬ ----¬¦e ¦ ----¬ ----¬ e -T--T¬¦
¦ ¦MUX¦ q ¦¦RG¦¦q'¦ROM+- ¦ ¦MUX¦ q'¦ROM+---->+¦RG¦+-
L>+0 +---->+¦ ¦+->+ ¦ Y L>+0 +-->+ ¦ Y ¦¦ ¦¦Y'
a->+1 ¦ S ¦¦ ¦¦S'¦ ¦==> a->+1 ¦ S'¦ ¦====>¦¦ ¦¦=>
b->+2 ¦ г==>¦¦ ¦¦=>¦ ¦==¬ b->+2 ¦ г>¦ ¦ H ¦¦ ¦¦
¦А ¦ ¦ C¦¦ ¦¦ ¦ ¦¬ ¦ ¦ ¦ ¦ ¦ +---->+¦ ¦¦=¬
LA--- ¦ -/++--+- L----¦ ¦ ¦ ¦ ¦ ¦ ¦ S ¦¦ ¦¦ ¦
¦ H L================- ¦ ¦А ¦ ¦ ¦ ¦====>¦¦ ¦¦¬¦
L=======================- LA--- ¦ L---- -/++--+-¦¦
¦ H' ¦ C ¦¦
¦ L=================-¦
L=======================-
При этом способе адресации альтернативные адреса отлича-
ются только одним разрядом ( в данном варианте - младшим ),
формируемым входным сигналом. Остальные разряды адреса указы-
ваются вместе с микрокомандой в одной и той же микроинструк-
ции. При безусловном переходе в данном варианте схемы младший
разряд также указывается в микроинструкции. При адресации
одного и того же микроблока различными операторами условного
перехода может возникнуть КОНФЛИКТ АДРЕСАЦИИ. В этом случае
одну и ту же микроинструкцию приходится располагать в различ-
ных ячейках управляющей памяти. Если различные операторы ус-
ловного перехода одними и теми же предикатными значениями
указывают на одни и те же микроблоки, то нет и конфликта ад-
ресации.
Адрес
n1 { m1 } --(0,0),(2,1) S'q'¦ Y H S e¦
----+--------+
n2 { m2 } --(4,0) 0 0 ¦m1 0 4 0¦
¦ ¦
<<GO(a;d1,n3)>>-- 1,x 0 1 ¦m4 1 2 x¦
¦ ¦
d1 { m0 } --(1,0) 1 0 ¦m0 1 1 x¦
¦ ¦
<<GO(a;d1,n3)>>-- 1,x 1 1 ¦m3 0 0 1¦
¦ ¦
n3 { m3 } --(1,1),(3,1) 2 0 ¦m0 2 3 x¦
¦ ¦
n4 { m4 } --(0,1) 2 1 ¦m1 0 4 0¦
¦ ¦
<<GO(a;d2,n1)>>-- 2,x 3 0 ¦m5 1 3 x¦
¦ ¦
d2 { m0 } --(2,0) 3 1 ¦m3 0 0 1¦
¦ ¦
<<GO(b;n5,n3)>>-- 3,x 4 0 ¦m2 1 1 x¦
¦ ¦
n5 { m5 } --(3,0) ----+---------
<<GO(a;n5,n3)>>-- 3,x
Распределять микроинструкции по ячейкам памяти удобно
в следующем порядке:
- связать с различными операторами условного перехода, кон-
фликтующими между собой по адресации, различающиеся между со-
бой старшие разряды адреса;
- распределить микроблоки по ячейкам памяти с учетом назнач-
енных старших разрядов адреса и входных значений;
- оставшимся нераспределенным микроблокам назначить произ-
вольные свободные адреса.
СХЕМА С СОКРАЩЕННЫМ ТАКТОМ
Использование этой схемы позволяет при сохранении пре-
имуществ последовательного варианта взаимодействия сократить
наиболее длинные цепи, общие для ОА и УА, до длины цепей кон-
вейерного варианта.
-----------------------------------¬ --T----------T
¦ г==========================¬¦ ROM_0 A'¦ Y H A e¦
¦ ¦ -----¬ ¦¦ --+----------+
¦ ¦ ¦ROM ¦=+A ¦¦ 0 ¦m1 0 4 0¦
¦ ¦ ¦ +-+e ¦¦ 1 ¦m0 1 1 x¦
¦ ¦>¦ ¦=+Y ----¬ -T--T¬¦¦ 2 ¦m0 2 3 x¦
¦ ¦ ¦ ¦=+H ¦MUX¦ ¦¦RG¦¦-¦ 3 ¦m5 1 3 x¦
¦ ¦ ¦ 0 ¦ L==>¦0 ¦ ¦¦ ¦+--e' 4 ¦m2 1 1 x¦
¦ A'¦ +----+ ¦ ¦ ¦¦ ¦¦ --+-----------
¦ ¦ ¦ROM ¦=+A ¦ ¦==>¦¦ ¦¦==>Y' --T----------T
¦ ----¬¦ ¦ ¦ ¦==>¦1 ¦ ¦¦ ¦¦ ROM_1 A'¦ Y H A e¦
¦ ¦MUX¦L>¦ +-+e ¦А ¦ C¦¦ ¦¦¬H' --+----------+
L>+0 ¦ ¦ ¦=+Y LA--- -/++--+-¦ 0 ¦m4 1 2 x¦
a>+1 ¦ ¦ 1 ¦=+H ¦ ¦ 1 ¦m3 0 0 1¦
b>+2 ¦ L----- ¦ ¦ 2 ¦m1 0 4 0¦
¦А +--------------- ¦ 3 ¦m3 0 0 1¦
LA--- ¦ --+----------+
L==============================-
Способ адресации, по существу, такой же, как и в преды-
дущей схеме. Только в рассматриваемой схеме входной сигнал
управляет выбором одного из двух блоков ПЗУ (можно интерпре-
тировать этот сигнал как старший разряд адреса).
СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ
----¬ ---¬ 0W- +1
¦MUX+->+M2+--¬ 1W- загрузка
0->+0 ¦->+ ¦ -VTT--T¬ ----¬ Y
a->+1 ¦¦ L--- W¦¦CT¦¦ ¦ROM¦==>
b->+2 ¦¦ ¦¦ ¦¦ ¦ ¦H
¦ ¦¦ ¦¦ ¦¦A ¦ ¦====¬
¦А ¦¦ г==>¦¦ ¦¦=>¦ ¦e ¦
LA---¦ ¦ ¦¦ ¦¦ ¦ +--¬ ¦
¦ ¦ ¦ C¦¦ ¦¦ ¦ ¦=¬¦ ¦
¦ ¦ ¦ -/++--+- L----S¦¦ ¦
¦ ¦ L=================-¦ ¦
¦ L------------------------ ¦
L=============================-
В этой схеме при разветвлении процесса вычислений пара
альтернативных адресов получается следующим образом: один ад-
рес всегда на единицу больше, чем текущий ( т.е. изменяется
"регулярным" образом ), второй адрес - произвольный и содер-
жится вместе с микрокомандой в микроинструкции.
Элементом, "вычисляющим" адрес, является счетчмк, управ-
ляемый сигналом, являющимся входным для УА. При различных
значениях входного сигнала счетчик выполняет две функции: ли-
бо прибавляет единицу к значению, которое хранилось в счетчи-
ке и являлось текущим адресом, либо загружается значением ад-
реса из управляющей памяти.
В схему введен элемент М2, позволяющий инвертировать
значение входного сигнала, что облегчает распределение микро-
инструкций по ячейкам управляющей памяти.
Адрес
n1 { m1 } -- 0 A ¦ Y H e S¦
--+-----------+
n2 { m2 } -- 1 0 ¦m1 x x 1¦
¦ ¦
<<GO(a;d1,n3)>> 1 ¦m2 1 0 3¦
¦ ¦
d1 { m0 } -- 2 2 ¦m0 1 1 2¦
¦ ¦
<<GO(a;d1,n3)>> 3 ¦m3 x x 4¦
¦ ¦
n3 { m3 } -- 3 4 ¦m4 1 0 0¦
¦ ¦
n4 { m4 } -- 4 5 ¦m0 2 0 3¦
¦ ¦
<<GO(a;d2,n1)>> 6 ¦m5 1 1 6¦
¦ ¦
d2 { m0 } -- 5 7 ¦m0 0 1 3¦
--+------------
<<GO(b;n5,n3)>>
n5 { m5 } -- 6
<<GO(a;n5,n3)>>
В схеме для конвейерного варианта взаимодействия регу-
лярное изменение адреса приходится организовывать так, чтобы
не увеличивать число мест конвейера.
г==============================¬
¦г=====================¬ ¦
¦¦ -T--T¬ ----¬¦ ----¬S¦
¦¦ ----¬ ¦¦RG¦¦ ¦MUX¦¦ ¦ROM¦=-
¦L=>¦INC¦=>¦¦ ¦¦>¦0 ¦¦ ¦ ¦Y -T--T¬Y'
¦ L---- C¦¦ ¦¦ ¦ ¦¦ ¦ ¦==>¦¦RG¦¦==>
¦ -/++--+- ¦ ¦¦>¦ ¦ ¦¦ ¦¦
¦ -/TT--T¬ ¦ ¦A ¦ ¦H ¦¦ ¦¦H'
¦ C¦¦RG¦¦ ¦ ¦ ¦ ¦==>¦¦ ¦¦==¬
L=========>¦¦ ¦¦>¦1 ¦ ¦ ¦e ¦¦ ¦¦e'¦
¦¦ ¦¦ ¦А ¦ ¦ +-->+¦ ¦+¬ ¦
----¬ L+--+- LA--- L---- -/++--+-¦ ¦
¦MUX¦ ---¬ ¦ C ¦ ¦
0->+0 +->+M2+----- ¦ ¦
a->+1 ¦->+ ¦ ¦ ¦
b->+2 ¦¦ L--- ¦ ¦
¦А ¦¦ ¦ ¦
LA---L------------------------------ ¦
L===================================-
СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И
СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ
г============================¬ C
¦г===================¬ ¦ -/TT--T¬H'
¦¦ -T--T¬ ----¬¦ ----¬ ¦ г==>¦¦RG¦¦==¬
¦¦ ----¬ ¦¦RG¦¦ ¦MUX¦¦ ¦ROM¦ ¦ ¦ ->+¦ ¦+-¬¦
¦L>¦INC¦>¦¦ ¦¦>¦0 ¦¦ ¦ ¦S¦H¦e¦ L+--+- ¦¦
¦ L----C¦¦ ¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ -T--T¬Y¦¦ для RG"Y"
¦ -/++--+- ¦ ¦¦>¦ ¦------>¦¦RG¦¦>¦¦
¦ -/TT--T¬ ¦ ¦A ¦ ¦ w c¦¦ ¦¦ ¦¦ 0w-загрузка
¦ C¦¦RG¦¦ ¦ ¦ ¦ ¦ -A-/++--+- ¦¦
L=======>¦¦ ¦¦>¦1 ¦ ¦ ¦k ¦ -T-T¬k'¦¦ 1w-нет загрузки
¦¦ ¦¦ ¦ А ¦ ¦ +----+->+¦T¦+¬ ¦¦
----¬ L+--+- L-A-- L---- -/++-+-¦ ¦¦ k ----¬
¦MUX¦ ---¬ --¬¦ C ¦ ¦¦ L----+ 1 +- CC
0>+0 +->+M2+->+&+- ¦ ¦¦ -----+ ¦
a>+1 ¦->+ ¦->+ ¦ ¦ ¦¦ SYN L----
b>+2 ¦¦ L---¦ L-- ¦ ¦¦
¦А ¦¦e' L--------------------------- ¦¦ где CC -
LA---L-----------------------------------¦ синхронизация ОА
L=======================================-
Эта схема используется только в конвейерном варианте
взаимодействия. Метод вычисления адреса для следующего такта
такой же, как и в схеме с регулярной адресацией. (Другой тер-
мин -"естественный" - употреблен только ради различения самих
схем.) Но в этой схеме, по сравнению с уже рассмотренными,
разряд управляющей памяти с одним и тем же номером (разрядный
срез) в различных микроинструкциях может быть использован
различным образом. Будем различать микроинструкции двух ти-
пов:
- операционные,
- алресации (выбора).
В лданном варианте схемы тип микроинструкции устанавли-
вается разрядом с именем "k". При k=0 выполняется микро-
инструкция операционного типа. Все остальные разряды ячейки
загружаются в регистр микрокоманды и управляют выполнением
микроопераций в ОА. Следующий адрес всегда на единицу больше.
При k=1 выполняется микроинструкция адресации. Все
разряды микроинструкции могут быть использованы для вычисле-
ния следующего адреса. В данном варианте схемы, так же как и
в схеме с регулярной адресацией, один из адресов явно записы-
вается в микроинструкцию, другой альтернативный адрес на еди-
ницу больше текущего.
Адрес A ¦k¦ Y ¦
n1 { m1 } -- 0 ¦ ¦ H¦ e¦ S¦
--¦-+--+--+--+
n2 { m2 } -- 1 0 ¦0¦ m1 ¦
1 ¦0¦ m2 ¦
g1 <<GO(a;g1,n3)>>-- 2 --¦-+--T--T--+
2 ¦1¦ 1¦ 1¦ 2¦
n3 { m3 } -- 3 --¦-+--+--+--+
3 ¦0¦ m3 ¦
n4 { m4 } -- 4 4 ¦0¦ m4 ¦
--¦-+--T--T--+
g2 <<GO(a;g3,n1)>>-- 5 5 ¦1¦ 1¦ 0¦ 0¦
6 ¦1¦ 2¦ 0¦ 3¦
g3 <<GO(b;n5,n3)>>-- 6 --¦-+--+--+--+
7 ¦0¦ m5 ¦
n5 { m5 } -- 7 --¦-+--T--T--+
8 ¦1¦ 1¦ 1¦ 7¦
g4 <<GO(a;n5,n3)>>-- 8 9 ¦1¦ 0¦ 1¦ 3¦
Вместе с этой схемой обычно используется условная син-
хронизация, которая позволяет удлинить такт выполнения микро-
команды в ОА на время выполнения микроинструкций адресации.
SYN -----------¬ -----------¬ -----------¬ -----------¬ -----
L-- L-- L-- L-- L--
| | | | |
k 0 -------- 0 ---------------------------------- 0 ---
--------------------------- 1 -------- 1 ----------------
| | | | |
CC¬ -----------¬ -------------------------------------¬ -----
L-- L-- L--
| | | | |
Y------------------------------------------------------------
-------------------------------------------------------------
ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД.
ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ
Функциональный переход
При необходимости выполнения нескольких вычислительныых
функций, управление которыми представляется в виде независи-
мых микропрограмм, необходимо организовать независимый вызов
этих микропрограмм.
Начальные адреса микропрограмм, управляющих вычислениями
различных функций, обычно существуют вне управляющей памяти.
В УА достаточно предусмотреть механизм коммутации, позволя-
ющий сделать начальный адрес текущим. Это можно осуществить в
любой из рассмотренных схем. (К механизму коммутации относят-
ся, кроме аппаратуры, специальные разряды управляющей памяти
и специальные микроинструкции.)
г======================¬ C
г======¦==============¬ ¦ -/ TT--T¬H'
¦ ¦ ----¬¦ ----¬ ¦ г==>¦¦RG¦¦==¬
¦ ¦ ¦MUX¦¦ ¦ROM¦ ¦ ¦ ->+¦ ¦+-¬¦
F =¦======¦========>¦0 ¦¦ ¦ ¦ ¦ ¦ ¦ L+--+- ¦¦
¦ ¦ -T--T¬ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
¦ ¦ ¦¦RG¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
¦ L>¦¦ ¦¦=>¦1 ¦¦ ¦ ¦S¦H¦e¦ ¦¦
¦ C¦¦ ¦¦ ¦ ¦¦ ¦ ¦ ¦ ¦ ¦ -T--T¬Y¦¦ для RG"Y"
¦ -/++--+- ¦ ¦¦>¦ ¦------>¦¦RG¦¦>¦¦
¦ -T--T¬ ¦ ¦A ¦ ¦ ¦¦ ¦¦ ¦¦ 0w-загрузка
¦ ----¬ ¦¦RG¦¦ ¦ ¦ ¦ ¦ w c¦¦ ¦¦ ¦¦
L>¦INC¦=>¦¦ ¦¦T>¦2 ¦ ¦ ¦ -A-/++--+- ¦¦ 1w-нет загр.
L---- C¦¦ ¦¦¦ ¦ ¦ ¦ ¦ ¦ ¦¦
-/++--+-¦ ¦ ¦ ¦ ¦ ¦ ¦¦
г==========- ¦ ¦ ¦ ¦ ¦ ¦¦
¦ -T-----T¬ ¦ ¦ ¦ ¦ --k ¦¦
L>¦¦STACK¦¦=>¦3 ¦ ¦ ¦K ¦ -T--T¬K' ¦¦
L+----A+- ¦ ¦ ¦ ¦===¦>¦¦RG¦¦¬ ¦¦
¦ ¦ А ¦ ¦ ¦ ¦¦ ¦¦¦ ¦¦
¦ L-A-- L---- -/++--+-¦ ¦¦
----¬ ¦ ¦ C ¦ ¦¦
¦MUX¦ ---¬ -¦------¦¬ ¦ ¦¦
0>+0 +->+M2+>+ CS ¦<==================- ¦¦
a>+1 ¦->+ ¦ ¦ ¦ ¦¦
b>+2 ¦¦ L--- L--------- ¦¦ k ----¬
¦А ¦¦e' ¦¦ L-+ 1 +-CC
LA---L---------------------------------------¦ --+ ¦
L===========================================- SYN L----
Переход к микроподпрограмме с возвратом
При реализации достаточно сложных вычислений удобно вос-
пользоваться механизмом микроподпрограмм.
Одна и та же микроподпрограмма может быть вызвана из
разных точек вызывающих микропрограмм. Поэтому при вызове
микроподпрограммы необходимо запомнить адрес, с тем, чтобы
восстановить его при возвращении из микроподпрограммы. Чтобы
запомнить и восстановить адреса возврата от вложенных вызо-
вов, используется безадресная память - стек (stack).
Принцип (дисциплина) работы стека описывается условием
"последний вошел - первым вышел" (Last In - First Out, LIFO).
чтобы описать этот принцип будем считать, что слова, хранящи-
еся в стеке, перенумерованы с помощью первых натуральных чи-
сел 1,2,...,N. Слово с наибольшим номером называют вершиной
стека.
Стек может выполнять следующие действия:
-"чтение" слова с наибольшим номером,
-"выталкивание" (стирание) из памяти слова с наибольшим но-
мером,
-"запись" нового слова с присваиванием ему наибольшего номе-
ра.
При вызове микроподпрограммы выполняется операция "запи-
си" адреса возврата в стек. При возвращении из микроподпрог-
раммы выполняется операция "чтения" адреса возврата, затем -
"выталкивания" его же из стека.
Операция "чтения" без "выталкивания" выполняется при ис-
пользовании стека для организации циклов.
Разряды с именем "К" определяют тип выполняемой микро-
инструкции. В связи с тем, что теперь в схеме существует 4
источника адреса для управляющей памяти, возможны 4 типа бе-
зусловных переходов, кроме того, возможны различные условные
переходы в различных сочетаниях комбинирующие эти источники
адреса и входные переменные.
С помощью комбинационной схемы CS разряды микроинструкции
"К" преобразуются в сигналы управления стеком и мультиплексо-
ром.
УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ
В конвейерном варианте для команд переходов по предикат-
ным переменным, зависящих без сдвига от сигналов управления,
приходится добавлять еще один такт для того, чтобы "увидеть"
значение переменной, по которой выполняется ветвление, и выб-
рать нужную МКИ.
Можно построить управляющий автомат, в котором для уско-
рения выполнения программы выполняются следующие действия:
Предварительно выбирается из ПЗУ одна из двух альтернативных
МКИ, соответствующая наиболее вероятному значению переменной
ветвления. Это значение должно храниться в той МКИ, после ко-
торой выполняется ветвление. В конце такта выработанное ре-
альное значение переменной сравнивается с предсказанным, если
они совпадают, то выбранная из ПЗУ МКИ записывается в выход-
ной регистр, если нет, то предыдущий такт продлевается, т.е.
не синхронизируются ОА и RG'МКИ. Микропрограмма будет такой
же как и для последовательного варианта взаимодействия ОА и
УА, но в МКИ добавляются два разряда:
F = { 1, если используется предвосхищение; 0, если нет },
P - наиболее вероятное значение переменной ветвления.
Фрагмент схемы УА, обеспечивающий предвосхищение может
быть таким:
--------------¬ ¦ ¦W
-T--T¬ ¦ -VT---¬ q -A---¬ f
t ¦¦RG¦¦ L-->+MUX+--->+ SS +<----------------------¬
--T--->+¦ ¦+---->+ ¦--->+ +<---------------------¬¦
¦ ¦¦ ¦¦ ¦ ¦¦t ¦ ¦ p ¦¦
¦ -\++--+- L----¦ -\+T---- ¦¦
¦ ¦ ¦ ¦ ¦j ¦¦
L---+----------------- ¦-VT---¬ ------¬ P -T--T¬p¦¦
¦ ¦ ¦MUX¦ ¦ ROM +--->+¦RG¦+--¦
¦ ¦ ¦ ¦ ¦ ¦ F ¦¦ ¦¦f ¦
¦ ¦ ¦ +--->+¦ ¦+---
¦ ¦ ¦ ¦ ¦¦ ¦¦
¦ ¦ ¦ ¦--->¦¦ ¦¦-->
¦ ¦ ¦ ¦ ¦¦ ¦¦
C ¦ ¦ L------ -\A++--+-
----+-------------------+--------------------L------ W
Пусть c=1 в конце такта.
Схема SS это автомат, который может находиться в одном
из двух состояний s0 и s1,
если s0, 0f, то w=1, j=q
если s0, 1f, 0c, то w=0, j=p
если s0, 1f, 1c, p==t, то w=1, j=p
если s0, 1f, 1c, p=/=t, то w=0, j=x, переход в s1
если s1, то w=1, j=q, переход в s0
_