|
Лекции по программированию
Лекции по программированию _УПРАВЛЯЮЩИЕ АВТОМАТЫ. _ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД Начнем с рассмотрения простейшего варианта управления, в
котором не участвуют предикатные функции (переменные), т.е. в
микропрограмме переходы только безусловные. В таком случае УА
является автономным синхронным автоматом. В более общем случае функция переходов УА зависит от
предикатных переменных, но УА должен быть автоматом Мура. Условимся о некоторых ограничениях, позволяющих упрос-
тить схему на начальных этапах проектирования (от которых
легко впоследствии и отказаться): - на каждом шаге процесса вычислений ветвление может осу-
ществляться только по одной двузначной предикатной перемен-
ной (т.е. разветвление возможно лишь на два направления); - начальные значения всех регистров УА являются нулевыми.
Впредь на схемах УА не будем показывать цепей установки на-
чальных значений. Для реализации в самом общем случае микропрограмм произ-
вольной структуры будем строить УА так, чтобы основным мате-
риальным носителем управляющей (автоматной) компоненты мик-
ропрограммы являлась бы управляющая память (реализованная,
например, в виде ПЗУ). В этом случае структура слова управля-
ющей памяти - МИКРОИНСТРУКЦИЯ - состоит из двух составных
частей: микрокоманды и адресной части. Адресная часть микроинструкции содержит информацию, поз-
воляющую в следующем такте работы выбрать ( указать ) новый
адрес управляющей памяти. Реализация именно этого момента яв-
ляется основным предметом дальнейшего рассмотрения и опреде-
ляет, в основном, структуру, объем аппаратуры и быстродей-
ствие УА. При этом подлежит рассмотрению реализация следующих
типов переходов как между шагами алгоритма, так, соот-
ветственно, и между микроинструкциями: - безусловный переход, - условный переход, - функциональный переход, - переход к микроподпрограмме с возвратом. Будем изучать работу управляющих автоматов различной
структуры, демонстрирующие основные применяемые варианты ад-
ресации микроинструкций, на следующем алгоритме: - 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
_
|
|
|
