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

 _УПРАВЛЯЮЩИЕ АВТОМАТЫ.

 _ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД

Начнем с рассмотрения простейшего варианта управления, в

котором не участвуют предикатные функции (переменные), т.е. в

микропрограмме переходы только безусловные. В таком случае УА

является автономным синхронным автоматом.

В более общем случае функция переходов УА зависит от

предикатных переменных, но УА должен быть автоматом Мура.

Условимся о некоторых ограничениях, позволяющих упрос-

тить схему на начальных этапах проектирования (от которых

легко впоследствии и отказаться):

- на каждом шаге процесса вычислений ветвление может осу-

ществляться только по одной двузначной предикатной перемен-

ной (т.е. разветвление возможно лишь на два направления);

- начальные значения всех регистров УА являются нулевыми.

Впредь на схемах УА не будем показывать цепей установки на-

чальных значений.

Для реализации в самом общем случае микропрограмм произ-

вольной структуры будем строить УА так, чтобы основным мате-

риальным носителем управляющей (автоматной) компоненты мик-

ропрограммы являлась бы управляющая память (реализованная,

например, в виде ПЗУ). В этом случае структура слова управля-

ющей памяти - МИКРОИНСТРУКЦИЯ - состоит из двух составных

частей: микрокоманды и адресной части.

Адресная часть микроинструкции содержит информацию, поз-

воляющую в следующем такте работы выбрать ( указать ) новый

адрес управляющей памяти. Реализация именно этого момента яв-

ляется основным предметом дальнейшего рассмотрения и опреде-

ляет, в основном, структуру, объем аппаратуры и быстродей-

ствие УА. При этом подлежит рассмотрению реализация следующих

типов переходов как между шагами алгоритма, так, соот-

ветственно, и между микроинструкциями:

- безусловный переход,

- условный переход,

- функциональный переход,

- переход к микроподпрограмме с возвратом.

Будем изучать работу управляющих автоматов различной

структуры, демонстрирующие основные применяемые варианты ад-

ресации микроинструкций, на следующем алгоритме:

- 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

_