Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
нтик М.И. 11_03_91 МИРЭА
АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ СТРОЙСТВА
Алгоритмы этого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению с ал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешается изме-
нять любую другую память стройства локально (по частям)а или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будема назы-
вать операционным стройством (ОУ).
ОУ можно рассматривать как одина синхронный автомата со
сложно структурированной памятью - состоянием:а часть памяти
используется для идентификации шага алгоритма, остальная па-
мять используется для запоминания промежуточныха данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
лгоритма. Такая модель вычислителя особенно добна для рас-
чета продолжительности одного такта работы стройства.
Другой удобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один из которых
называется правляющим автоматом (УА), объединение всех ос-
тальных автоматов называется операционным автоматом (о).
у является исполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритма процедурного
типа. Кроме того, у инициирует действия отдельных шагова ал-
горитма и частвует в их выполнении.
о выполняет все вычисления на отдельных шагах алгоритма
под правлением А; кроме того, к о добно отнести всеа вы-
числения предикатных функций, оставив у только анализ вычис-
ленных предикатных значений.
Прежде чем переходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например, каноническое описание синхронного конечного
втомата может быть интерпретировано (истолковано) кака одно-
шаговый алгоритм процедурного типа.
█
┌──────┐а │
а ┌──V──V─────┐
│ B=FO(S,A) │
│ │
│ S:=FS(S,A)│
а └─────┬─────┘
└─────────┘
Исполнитель этого алгоритма состоита только иза о. На
каждом шаге этого алгоритма изменяется вся память устройства,
поэтому правление памятью не требуется, идентифицировать ша-
ги этого алгоритма не надо.
Например, инкрементор с одноразрядным входом иа однораз-
рядным выходом может быть реализацией следующиха преобразова-
ний:
█
█ p:=1 █
█
┌────────┐ │
┌─────V─V───────┐
│ (p:, b) = a+p │
└───────┬───────┘
└──────────┘
о, реализующий инкрементор в целом, будет следующим:
┌──┬─┐
a ──────────────────┤HS│S├────b
┌─┬─┐p │ │
начальное значен.─┤S│T├──┤а │P├──┐
├─┤ └──┴─┘а │
SYN ─────────/C│ │ │
┌┤D│ │ │
│└─┴─┘ │
└───────────────┘
Конечно, эта реализация совпадает с реализацией алгоритма ав-
томатного типа, если состояние р1 кодируется 1, состояние
р0 - 0.
Этот пример показывает,что до начал вычисленийа может
потребоваться начальная становка памяти. На самома делеа это
необходимо было же в алгоритмах автоматного типа, така как
код начального состояния требуета предварительной станов-
ки. Ограничимся здесь обозначением этой проблемы, решение
ее, связанное прежде всего са корректнойа синхронизацией с-
тройства в первом такте его работы, рассмотрим ниже.
При рассмотрении процедуры построения автомата Мур эк-
вивалентного автомату Мили, не обсуждалась простая возмож-
ность ее реализации и на структурном ровне. Например, только
что рассмотренный автомат Мили может быть преобразована в эк-
вивалентный автомат Мура по одному из следующих вариантов:
┌┬─┬┐t┌──┬─┐ ┌──┬─┐а ┌┬─┬┐
a ──┤│T│├┤HS│S├─b a ─────┤HS│S├─┤│T│├─b
─/┴┴─┴┘ │ │ │ │─/┴┴─┴┘
C │ │ C │ │ C
─/┬┬─┬┐p │ │ ─/┬┬─┬┐p │ │
┌┤│T│├┤а │P├┐ ┌┤│T│├┤а │P├┐
│ └┴─┴┘ └──┴─┘│ │ └┴─┴┘ └──┴─┘│
└─────────────┘ └─────────────┘
При таких структурных преобразованияха проще истолковы-
вать алгоритмы как процедурные.
█ █
█ p:=1; t:=0 █ █ p:=1 █
█ █
┌────────┐ │ ┌────────┐ │
┌─────V─V───────┐ ┌─────V─V───────┐
│t:=a;(p:,b)=t+p│ │ (p, b):= a+p │
└───────┬───────┘ └───────┬───────┘
└──────────┘ └──────────┘
БЛОК-ТЕКСТ. Способ описания автоматного алгоритм после
некоторых дополнений может быть использована иа для описания
лгоритмов в процедурной форме:
Блок-текст состоит из трех частей:
1)- Описание переменных и начальных значений памяти.
2)- Описания функций и связей. Записываются любые функцииа и
функциональные связи (в том числе предикатные), не использу-
ющие запоминания. Переменные из левой части операции присва-
ивания таких функциональных описаний используются ва блоках
процедуры.
3)- Процедура, состоящая из блоков (микроблоков) операторных
и блоков переходов:
- операторные - в скобках вид {.....},
- переход - в скобках вид <<...>>;
и те, и другие блоки могут снабжаться метками, стоящими перед
блоком. В блоках перехода используется оператора GOа в одной
из двух форм:
GO m - безусловный переход,
GO (P; m0,m1,m2,...) - словный переход.
здесь m0,m1,... - метки блоков,
P - предикатное значение,интерпретируемое оператором GO
как неотрицательное целое число, являющееся порядковыма номе-
ром метки в списке меток оператора GO. Са этойа метки должно
быть продолжено выполнение алгоритма. Блоки словныха перехо-
дов эквивалентны предикатным вершинам блок-схемы алгоритма.
На следующем более сложном примере демонстрируется пос-
ледовательность синтеза операционного стройства.
Пример. Вычислитель наибольшего общего делителя (НОД)
двух натуральных чисел (8-разрядных).
1) Разработаем интерфейс вычислителя:
8а ┌──┬─────┬──┐
═══╪═>╡I1│ НОД │
│ 8
8а │ │D ╞══╪══>
═══╪═>╡I2│ │
├──┤ ├──┤
─────>┤rI│ │rO├─────>
├──┤ │
─────>┤ C│ │
└──┴─────┴──┘
I1[7..0], I2[7..0] -входные информационные шины.
rI -входной сигнал готовности: если rI=1, то н входаха I1,
I2 готовы операнды.
D[7..0] -выходная информационная шина.
rO -выходной сигнал готовности: если rO=1, то готова резуль-
тат на шине D, который сохраняется до появления новых операн-
дов.
2) Математическое обоснование алгоритма вычислений:
Идея алгоритма, следуя Евклиду (в. до р.Х.), заключа-
ется в том, что НОД двух натуральных чисел А и В в случае ра-
венства этих чисел совпадает с любым из них, ва случае их
неравенства совпадает с НОД двуха другиха чисел:а меньшего и
разности между большим и меньшим. Последовательно, меньшая
числа, получим два равных числа -значение одного из них и бу-
дет НОД исходных чисел.
3) Блок-схема алгоритма (микропрограмма в содержательном
виде):
█
│
┌──────V──────┐
m1 rO: = 0 │
└──────┬──────┘
│┌──────────────────┐
││┌─────┐ │
── │ │
/ \ 0 │ │
< rI>─────┘ │
\_/ │
│1 │
┌──────V──────┐ │
rO: = 0 │ │
│ │ │
m2а А: = I1 │ │
│ │ │
а B: = I2 │ │
└──────┬──────┘ │
┌───────────────────┐│ │
│ ┌─────VV──────┐ │
│ m3│ (p,S)=A - B │ │
│ └──────┬──────┘ │
│ ─V─ m6 │
│ /а \ =0а ┌──────────┐│
│ z <S==0>───>┤ rO:=1;D=A├┘
│ \__/ └──────────┘
│ │╪0
│ V
│ 0 / \ 1
│ ┌───────< p >────────┐
┌───────V──────┐ \_/ ┌───────V──────┐
│m4 (x,B:)=-A+B а m5│ (x,A:)=A - B │
└───────┬──────┘ └───────┬──────┘
└──────────┴────────────────────┘
Или в виде блок-текста:
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
─/┬┬──┬┐а ║ ┌────────────┐
C││RG│ ║ f1=(A-B) │
│ │ ║ A│ │
I1═════> ══>╡ │╞══╝а ═>╡ f2=(-A+B)│ ┌─┐
│ ││ │ │S S│1│
│ ││ │ ╞> ═>┤ o───>z
┴┴──┴┘ │ │ │ │
B │ │ └─┘
─/┬┬──┬┐ │ │
C││RG││ │ ├────────────>p
│ ││B B│ │
I2═════> ═>╡ │╞> ═>╡ │ ─/┬┬─┬┐
│ ││ │ │ C││ │├>rO
│ ││ │ │ ││ ││
rI─────> ┴┴──┴┘ └────────────┘ └┴─┴┘
Кроме того, в о необходимо реализовать все информацион-
ные связи, соответствующие микрооперации коммутации, также
микрооперации запоминания (загрузки, записи) и обнуления.
╔══════════════════════════════════════════════╗
║ A ╔══════════════════════║═══════>D
║а ┌────┐ ─/┬┬──┬┐а ║ ┌────┐ ┌──────┐ ║
║а │ MUX│ C││RG│ ║ │M2*8│ 1─>┤crа SM│ ║
╠═>┤0 │ │ │ ║ │ │ ├─ │ ║
I1══║═>┤1 ╞══════>╡ │╞══╩══>╡ ╞═══>╡I1 │ ║ ┌─┐
║а ├ │ │ │ A │ │ │ │ ║ │1│
║а │ │ W│ ││ ├─ │ │ S╞═╩>╡ o───>z
║а └A───┘ ─A┴┴──┴┘ └A───┘ │ а │ │
║ │ │ │ │ а └─┘
║а umA uA uiA │ │
║ B │ │
║а ┌────┐ ─/┬┬──┬┐ ┌────┐ │ │
║а │ MUX│ C││RG││ │M2*8│ │ p├─────────>p
╚═>╡0 │ │ ││ B │ │ │ │
I2════>╡1 ╞══════>╡ │╞═════>╡ ╞═══>╡I2 C
├ │ │ ││ │ │ │ │ ─/┬┬─┬┐
│ │ W│ ││ ├─ │ │1─>┤│T│├>rO
└A───┘ ─A┴┴──┴┘ └A───┘ └──────┘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
║а ┌────┐ ─/┬┬──┬┐а ║ ┌────┐ ┌──────┐ ║
║а │ MUX│ C││RG│ ║ │M2*8│ 1─>┤crа SM│ ║
╠═>╡0 │ │ │ ║ │ │ ├─ │ ║
I1══║═>╡1 ╞══════>╡ │╞══╩══>╡ ╞═══>╡I1 │ ║ ┌─┐
║а ├ │ │ ││ │ │ │ │ ║ │1│
║а │ │ W│ ││ ├─ │ │ S╞═╩>╡ o───>z
║а └A───┘ ─A┴┴──┴┘ └A───┘ │ а │ │
║ └────┐ ┌─┘а B ┌────┘ ├─ а └─┘
║а ┌────┐а │─/┬┬──┬┐а а ┌────┐ │ │
║а │ MUX│а │ C││RG│ а │M2*8│ │ p├─────────>p
╚═>╡0 │а │ │ а │ │ │ │
I2════>╡1 ╞│═══│═>┤ │╞══│══>┤ ╞═══>╡I2 │
├ │а │ │ а │ │ │ а│
│ │а │ W│ │ а ├─ │ │ а C
└A───┘а │─A┴┴──┴┘а а └A───┘ └──────┘а ─/┬┬─┬┐
│ │ └─┐ │ ┌─┐│ 1─>┤│T│├>rO
│ а │ ├>┤ o┘ R W││ ││
├────┘ а │ │ └─┘ ─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 │
└┬──┬──A───A───A───A───A───A─────┘
а а а а │
а а а а │
┌V──V──┴───┴───┴───┴───┴───┴─────┐
│zа pа y1а y2а y3а y4а y5а y6 │
│ │
┴──/C │
│ У │
──>┤rI │
└────────────────────────────────┘
у должен выполнять следующий алгоритм автоматного типа,
представленный в виде блок-текста:
m1{10}
g1<<GO(rI;g1,m2)>>
m2{x10}
m3{xx0}
<<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 │├───>┤0а │ ┌────┐ │MUX│ D
└┴──┴┘ ──>┤1а │ SM│ │ ┌┬──┬┐
──>┤ ├───>┤crа ═══>╡0а ╞═══>╡│RG│╞══>
├───┤ а S╞═════>╡1а │ └┴──┴┘
R1 │MUX│ │ ═══>╡ │
┌┬──┬┐ а │ │ │ └───┘
││RG│╞═══>╡0а ╞═══>╡I1а │ ┌───┐
└┴──┴┘ ══>╡1а │ │ │ │MUX│
══>╡ │ │ │ а ├────────────>e
├───┤ а p├─────>┤0а │
R2 │MUX╞═══>╡I2 а ───>┤1а │
┌┬──┬┐ а │ └────┘а ───>┤ │
││RG│╞═══>╡0а │ └───┘
└┴──┴┘ ══>╡1а │
══>╡ │
└───┘
Имена всех переменных, используемыха ва этома микрооператоре,
означают выполнение микроопераций коммутации ( транспортиров-
ки ). Значения переменныха коммутируются на входы суатора,
результат суммирования - в места расположения переменных.
МИКРОБЛОК - набор микрооператоров, выполняемыха одновре-
менно ( в одном такте ) и синхронно. В одном микроблоке любо-
му из битов присваивается только одно значение.
Синхронность означает, что во всех микрооператорах одно-
го микроблока используется только "старое" значение памяти.
Например:
{ (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а │
└────┬───┘ └────┬───┘
┌──────>│ ┌──────>│
│ ─V─ │ ─V─
│ / \ =0 │ / \ =0
│ <CT==0>─> │ <CT==0>─>
│ \/ │ \/
│ │╪0 │ │╪0
┌────V───┐ ┌────V───┐
│m2│........│ │m2│........│
│ │ │ │
│CT:=CT-1│ │CT:=CT-1│
└────┬───┘ └────┬───┘
└───────┘ ┌────V───┐
│m3│........│
└────┬───┘
└───────┘
В первом случае цикл будет выполнен 4 раза; во втором -а если
в микроблоке m3 нет операций, модифицирующиха СТ, -а 3а ра-
за. ( Обратите внимание на начальное значение СТ!)
МИКРОКОМАНДА - набор сигналов, поступающий из у в О и
интерпретируемый как правляющий,т.е. необходимый для выпол-
нения всех микроопераций одного микроблока. Сигналы, входящие
в микрокоманду, могут принимать частие в микрооперациях и в
качестве информационных.
Микрокомандой также иногд называюта слово управляющей
памяти (обычно ПЗУ), являющееся частьюа УА. Для различения
этих понятий слово правляющей памяти будема называть МИКРО-
ИНСТРУКЦИЕЙ.
МИКРОПРОГРАММА СОДЕРЖАТЕЛЬНАЯ - алгоритм, представленный
в виде микроблоков и предикатных блоков ва одной иза принятых
форм, например, в виде блок-схемы или блок-текста.
МИКРОПРОГРАММА КОДИРОВАННАЯ - аппаратная форм содержа-
тельной микропрограммы в виде кодов, заполняющиха правляющую
память.
КАНОНИЧЕСКЯа СТРУКТУР ОПЕРАЦИОННГо АВТОМАТА
В общем случае каноническая структура операционного ав-
томата имеет вид:
███████████████████████████████████████████████████████████
█ █
█а ┌──────────┐ ┌┬──────┬┐ ┌──────────┐ ┌───────┐а █
██>╡коммутация│ ││память│а │коммутация │функции▐███
│ ▐███>╡│ │▐██>╡ ▐██>╡ │
██>╡ │ ││ │а │ │ ▐███>
└─A────────┘ ─/─┴┴───A──┴┘ └──A───────┘ └──A────┘
█ ┌─┐│CC █ █ █
█ SYN─>┤&├┘ █ █ █
█ ┌┤ │ █ █ █
█ yC│└─┘ █ █ █
└────────────────────────────────────────────────┘
сигналы правления
Столь четкого разграничения операций на зоны (память, комму-
тация, функции) может и не быть. Например, такие широко ис-
пользуемые функцииа как сдвиги либо хорошо совмещаются с
коммутацией, либо интегрируются са регистрамиа хранения.Также
часто интегрируются са хранением функции инкремент и
декремента (счетчики обычные и реверсивные).
Особо выделим сигнал yС, правляющий доступом синхросиг-
налов в о. Такойа варианта правления, называемыйа условной
синхронизацией, позволяет запретить любые изменения памяти о
в каком-либо такте. Причем, если рабочим является среза (зад-
ний фронт) сигнала синхронизации, то используется элемента И,
как и показано на рисунке.Если же рабочим является фронт (пе-
редний фронт) сигнала, то используется элемента ИЛИ.а (Первый
перепад сигнала синхронизации в новом такте неа должена быть
рабочим.)
ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА
При проектировании вычислительного стройств основными
являются ограничения на:
1)- время вычисления;
2)- объем аппаратуры, реализующей вычисления;
3)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ РАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальныма по-
тенциальным параллелизмом (ва рамкаха данной алгоритмической
идеи), и,следовательно, его реализация ва виде Са обладает
максимальным быстродействием по сравнению c любыми другими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представление и его реализация являются
статическим отображением входных объектова н выходные:а это
исключает возможность работы с объектами, которые "ведута се-
бя" более сложно во времени;а невозможно такжеа реализовать
принципиально рекуррентные алгоритмы (см.,например, лгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритма функционального
типа может быть записан, то проектирование стройств надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом н про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из ниха ва один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменныха (входных
и выходных),связанных с выполнением этих операций. Требуется
также правление памятью, связанной с этим функциональным мо-
дулем, также - может быть - правление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно величит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может меньшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений -а но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры беза увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме стройства, реализующего алгоритм
функционального типа, простую модель ва виде направленного
графа. Вершины графа будут соответствовать операциям, дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный графа всегд будет
циклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо н аль-
тернативных путях решения.
МИНИМИЗАЦИЯ АППАРАТУРЫ
Может оказаться, что на одном пути ва сигнальнома графе
расположены операции, плохо или вовсе не совмещаемые друга с
другом (т.е. совмещение не дает экономии в аппаратуре функци-
онального модуля). Возможно также, что проведенная минимиза-
ция, сохраняющая минимальное время, неа позволяета выполнить
ограничение на объем аппаратуры. Ва такома случае необходима
более глубокая минимизация,охватывающая параллельные ветви
сигнального графа. Минимизация должна быть взаимосвязанной по
всем компонентам о: по памяти, функциональным модулям и ком-
мутации.
В настоящее время процедуры минимизации не формализованы
и сводятся к перебору "правдоподобных" вариантов.
Можно предложить следующую последовательность действий:
1)- все "похожие" функцииа (операции)а реализовать на одном
функциональном модуле, например, все суммирования выполнять
на одном сумматоре;
2)-скорректировать алгоритм так, чтобы в одном микроблоке не
выполнялось более одной операции на одном и тома же функци-
ональном модуле;
3)- минимизировать память автомата, т.е. число запоминаемых
промежуточных переменных;
Выполнение этих этапов может привести к сложнениюа ком-
мутации, значит, и к величению этой компоненты в аппарату-
ре о. Если ограничение по объему аппаратуры все еще наруше-
но, то повторить этапы 1 - 3 с другима вариантома объединения
функциональных модулей и памяти.
При реализации о - во избежание ошибок -необходимо бук-
вально следовать описанию алгоритма, но в то жеа время, при
проектировании самого алгоритма надо представлять себе реали-
зацию микроблоков. Реализация одних и тех же вычислений может
быть существенно различной по объемуа аппаратуры.
Например, вычисления в цикле потребуют реализации:
─┬─
│
┌───────V───────┐ A ┌────┐
│ J:=0 │ ┌┬──┬─┐ │ MUX│ ┌────┐
└───────┬───────┘ ││RG│0├───>┤0 │ │ fа │
┌──────┐а │ │ │.│. │. │A[J] │ │
│ ┌────V──V───────┐ │ │.│. │. ├────>┤ │
│ │ ..... │ │ │.│. │. │ │ │ B
│ │ │ │ │ │ │ │ │ ╞══>
│ │ B= f(...,A[J])│ │ │K├───>┤K │ │ │
│ │ │ │ │.│ │. ══>╡ │
│ │ J:=J+1 │ │ │.│ │. │ │ │
│ └───────┬───────┘ │ │.│ │. │ │ │
│ ─V─ └┴──┴─┘ ├─ │ └────┘
│ <K /а \ =K J═════════>╡ │
└──────<J==K>─────> └────┘
\__/
(реализация счетчика J не показанa).
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре D. Тогда получим:
───┬── A D
│ ┌┬──┬┐ а┌┬──┬─┐ A[J] ┌─────┐
┌───────V───────┐ ││RG││ ││RG│0├─────>┤а fа │
│ J:=0 │ │ ││ │ │.│ │ │
│ │ │ ││ ││->│.│ │ B
│ D:=A │ │ │╞══════>╡ │.│ ╞══>
└───────┬───────┘ │ ││ │ │ │ │ │
┌──────┐а │ │ ││ │ │K├ │ │
│ ┌────V──V───────┐ │ │ x ──>┤Dn │.│ │ │
│ │ ..... │ │ ││ │ │. ══>╡ │
│ │ │ │ ││ S W│ │.│ │ │
│ │ B= f(...,D[0])│ └┴──┴┘ ─v─v┴┴──┴─┘ └─────┘
│ │ │
│ │ (D,x):=(x,D)а │
│ │ │
│ │ J:=J+1 │
│ └───────┬───────┘
│ ─V─
│ <K /а \ =K
└──────<J==K>─────>
\__/
Промежуточный регистр A введен для общности, если потребуется
сохранить слово А (чаще всего он и не нужен).
Другой пример: фрагмент алгоритма, реализующий регуляр-
ную запись отдельных бит слова и его реализация имеют вид:
───┬── ┌┬─┬┐B[0]
│ a ────────────┬─────>┤│T│├────>
┌───────V───────┐ │ W││ ││
│ J:=0 │ ┌───┐ │ ─A┴┴─┴┘
└───────┬───────┘ │DC │ ┌──┼─────┘| |
┌──────┐а │ 0├─┘а │ | |
│ ┌────V──V───────┐ .│. │ ┌┬─┬┐B[K]
│ │ ..... │ .│. └─────>┤│T│├────>
│ │ │ .│. W││ ││
│ а a=f(...) │ J ══>╡ │ ─A┴┴─┴┘
│ │ │ K├──────────┘
│ а B[J]:=a │ .│
│ │ │ .│
│ │ J:=J+1 │ .│
│ └───────┬───────┘ └───┘
│ ─V─
│ <K /а \ =K
└──────<J==K>─────>
\__/
Слово В нельзя реализовать в виде регистра, только ва виде
отдельных триггеров.
Можно формировать слово с использованием операцииа сдви-
га при обязательном словии D[K..0], тогда алгоритм и его ре-
лизация имеют вид:
───┬──
│ D B
┌───────V───────┐ ┌──┬──┬┐ ┌┬──┬┐
│ J:=0 │ │RG││ ││RG││
└───────┬───────┘ │->││ │ ││
┌──────┐а │ aа │╞═════>╡ ││
│ ┌────V──V───────┐ ──>┤Dk ││ │ ││
│ │ ..... │ S ││ W│ ││
│ │ │ ─v┴──┴──┴┘ ─v┴┴──┴┘
│ а a=f(...) │
│ │ │
│ │ (D,x):=(a,D)а │
│ │ │
│ │ J:=J+1 │
│ └───────┬───────┘
│ ─V─
│ <K /а \ =K ┌────┐
└──────<J==K>──>┤B:=D├>
\__/ └────┘
В этом случае, так же, как и в предыдущем, чаще всего не ну-
жен промежуточный регистр (В).
УНИВЕРСАЛЬЫй о
Использование при проектировании ниверсальных о c за-
ранее фиксированной и минимизированной структуройа оправдано
тем, что такие ниверсальные О изготавливаются промышлен-
ностью в виде БИС большим тиражом и поэтому они сравнительно
дешевы. Такие ниверсальные о входят в микропроцессорные на-
боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на-
зываются микропрограммируемыми, секционными, разрядно-модуль-
ными.
В основе перечисленных ниверсальных о лежита следующая
структура:
╔══════════════════╦═══════════════════════════╗
║ ║ ║
║ ║ SYN┐а ACC ║
║ ┌─┬─────┬┐ ║ ─/┬┬──┬┐ ┌─────┐ ║
║ │ │ RGF ││ ║ C││RG││ │ ALU ║
║ │ │ ││ ║ │ ││ │ а ║
║ │ │ ││ ╚════>╡ │╞═════>╡ а ║
║ │ │ ││ │ ││ │ ╞═══╩═>DO
╚═══>╡D│ ││ └┴──┴┘ │ │
│ │ ││ T │ │
│ │ ││ ┌┬──┬┐ │ ╞═════>P
│ │ ││ ││RG││ │ а│
│ │ │╞═════════>╡ │╞═════>╡ │
│ │ ││ │ ││ │ │
C W│ ││ C│ │а ╔═>╡ │
─o─A┴A┴─────┴┘ ─┬┴┴──┴┘ ║а └──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' с началом следующего такта, т.е. н пе-
реднем фронте сигнала.
ВЗАИМОДЕЙСТИе О и А
Для исключения гонок при взаимодействии О иа У будем
проектировать у как автомат Мура. Схем иха взаимодействия
может быть представлена в виде:
╔══════════════════════════╗
║┌────┐ ┌┬──┬┐ ┌────┐ ║
╚╡ CS │ ││RG│а │CSа ╞<╝
│ ╞<═╦═╡ │╞<══╡ │
┌───┤а b ║ │ │а │ cа ├<────┐
а └────┘а ║ └┴──┴┴A─ └────┘ │
а ┌────┐а ║ └───────────┐ │
а │CSа ╞<═╝ │ │
│┌──┤ aа ├<───────────────────┐ │ │
О │ └────┘ │ │ │
----││----------------------------│-│-│-У ││РА┌────┐ ┌┬──┬┐а ┌─────┐│ │ │┐
│└─>┤а CS│ ││RG│ │ CSа ├┘ │ ││
└──>┤ ╞════>╡ │╞═>╡ ├──┘ ││Y
РВ │ │ │ │ │ ├────┘│
╔>╡а p │ │ │ yа ╞═╗ ┘
║ └────┘ └┴──┴┘а └─────┘ ║
╚════════════════════════════╝
Отметим, что РА(t)=f(Y(t)) зависит без сдвиг ота сигналов
правления,
PB(t+1)=F(Y(t)) зависит со сдвигома ота сигналов
правления,
где РА и РВ - предикатные перемнные.
Продолжительность такта работы схемы определяется наибо-
лее длинными цепями между регистрами. Для данной схемы, кото-
рую будем называть последовательной схемой взаимодействия,
зададимся (так чащеа всего бывает), что такой критической
цепью является цепь (CSy,CSa,CSp,RG). Поэтому длительность
такта определяется:
Т > ty + ta + tp + trg,
где tj- время становления соответствующего компонента цепи.
Чтобы сократить длину этой цепи, применяют другойа вари-
нт взаимодействия автоматов - конвейерный:
╔══════════════════════════╗
║┌────┐ ┌┬──┬┐ ┌────┐ ║
╚╡ CS │ ││RG│а │CSа ╞<╝
│ ╞<═╦═╡ │╞<══╡ │
┌───────────┤а b ║ │ │а │ cа ├<────┐
│ FF └────┘а ║ └┴──┴┴A─ └────┘ │
┌┬──┬┐ ┌────┐а ║ └───────────┐ │
│┌─┤│RG│╞<══╡ CS ╞<═╝ │ │
││ │ │а a ├<───────────────────┐ │ │
││ └┴──┴┴A─ └────┘ │ │ │
о ││ └──────────────────────────┐ │ │ │
---││----------------------------------│-│-│-│-УА ││ MKа │ │ │ │
│ PA ┌────┬────┐ ┌┬──┬┐│ │ │ │┐
│└────>┤а CS│ CS │ ││RG│├┘ │ │ ││
РВ │ │ │ │ │├──┘ │ ││Y
└─────>┤ │ ╞═══════════>╡ │├────┘ ││
│ │ │ │ │├──────┘│
╔>╡а p y │ │ │╞═╗ ┘
║ └────┴────┘ └┴──┴┘ ║
╚═══════════════════════════════╝
При этом варианте взаимодействия такой длинной цепи, как
в предыдущем случае, не возникает.Эта цепь разделен регис-
трами 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 │
л │
└────────────────────────────┘
У этого автомата простейшей является функция переходов, так
кака диаграмм автомат совпадаета са диаграммойа переходов
D-триггера.
Схема автомата вместе са цепями словнойа синхронизации
выглядит следующим образом (для синхронизации по фронтам):
)-по переднему фронту, б)- по заднему фронту:
┌──┐ ┌──┐
SYN ──┬──────────┤ 1├── CC SYN ──┬──────────┤ &├── CC
│ ┌─┬─┐а ┌─┤а │ │ ┌─┬─┐а ┌─┤а │
└─/C│T │ └──┘ └─\C│T │ └──┘
│ │ ├а │ │ │ ├──┘
┌─┤D│ │ ┌─┤D│ │
│ ├─┤ o──┘ │ ├─┤ o─
├─oR│ │ ├─oR│ │
Hа │ └─┴─┘уст. нач. зн. Hа │ └─┴─┘уст. нач. зн.
──┴─────────────────── ──┴───────────────────
Такая разница в цепях словной синхронизации, как же объяс-
нялось выше, определяется тем, что первый перепад сигнал СС
не должен быть рабочим.
нтик М.И. 11_03_91 МИРЭА
УПРАВЛЯЮЩИЕ АВТОМАТЫ.
ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД
Начнем с рассмотрения простейшего варианта управления, в
котором не частвуют предикатные функции (переменные), т.е. в
микропрограмме переходы только безусловные. В таком случае А
является автономным синхронным автоматом.
В более общем случае функция переходова У зависита от
предикатных переменных, но у должен быть автоматом Мура.
словимся о некоторых ограничениях, позволяющиха прос-
тить схему на начальныха этапаха проектирования (ота которых
легко впоследствии и отказаться):
- на каждом шаге процесса вычислений ветвление можета осу-
ществляться только по одной двузначной предикатнойа перемен-
ной (т.е. разветвление возможно лишь на два направления);
- начальные значения всех регистрова У являются нулевыми.
Впредь на схемах у не будем показывать цепей становкиа на-
чальных значений.
Для реализации в самом общем случае микропрограмм произ-
вольной структуры будем строить у так, чтобы основныма мате-
риальным носителем правляющей (автоматной)а компоненты мик-
ропрограммы являлась бы управляющая память (реализованная,
например, в виде ПЗУ). В этом случае структура слова управля-
ющей памяти - МИКРОИНСТРУКЦИЯ -а состоита иза двуха составных
частей: микрокоманды и адресной части.
Адресная часть микроинструкции содержит информацию, поз-
воляющую в следующем такте работы выбрать ( казать )а новый
дрес правляющей памяти. Реализация именно этого момента яв-
ляется основным предметом дальнейшего рассмотрения и опреде-
ляет, в основном, структуру, объема аппаратуры и быстродей-
ствие А. При этом подлежит рассмотрению реализация следующих
типова переходова кака междуа шагами алгоритма, так, соот-
ветственно, и между микроинструкциями:
- безусловный переход,
- словный переход,
- функциональный переход,
- переход к микроподпрограмме с возвратом.
Будем изучать работу правляющиха автоматова различной
структуры, демонстрирующие основные применяемые варианты ад-
ресации микроинструкций, на следующем алгоритме:
███
┌───┐│
┌VV─┐
n1 │m1 │ n1 { m1 }
└─┬─┘
┌─V─┐ n2 { m2 }
n2 │m2 │
└─┬─┘ g1 <<GO(a;g1,n3)>>
│ │<──┐
┌V┐ 0│ n3 { m3 }
g1 < a >─┘
└┬┘ n4 { m4 }
а 1│<────┐
│ │┌───┐│ g2 <<GO((a,b);n5,n3,n1,n1)>>
┌─VV┐а ││
n3 │m3 ││ n5 { m5 }
└─┬─┘а ││
┌─V─┐а ││ g3 <<GO(a;n5,n3)>>
n4 │m4 ││
└─┬─┘а ││
│10 ┌V┐ 01││
g2└──< ab>──┘│
11 └┬┘ │
00│┌───┐│
┌─VV┐а ││
n5 │m5 ││
└─┬─┘а ││
┌V┐ 0 ││
g3 < a >──┘│
└┬┘ 1а │
└─────┘
кажем на некоторые особенности этого алгоритма:а Опера-
тор переход (предикатная вершина), помеченный меткой g1,
называют ждущим. Оператор, помеченный меткойа g2, использует
для перехода 4-значный предикат, что не довлeтворяета выше-
указанномуа ограничению. Поэтому потребуются эквивалентные
преобразования алгоритма для того, чтобы удовлетворить этому
ограничению.
Алогоритмы эквмвалентны, если они преобразуют информа-
цию одинаковым образом. Наиболее распространенным приемом эк-
вивалентного преобразования алгоритмов и микропрограмма явля-
ется включение микроблоков и, соответственно, тактов, в кото-
рых не выполняется модификация памяти о -а "нета операции".
Но и это преобразование может быть не эквивалентным - см.при-
мер при определении понятия "микроблок"; кроме того, следует
учесть различное поведение во времени предикатныха переменных
типа "РА" и "РВ" - см. раздел "Взаимодействие о и А".
( Запретить модификацию памяти можно, вводя словную
синхронизацию о, но для этого должна быть изменен микроко-
манда, предшествующая добавляемому такту.)
СХЕМА С АДРЕСНЫМ ПЗУ
Начнем рассмотрение с правляющего автомата, структура
которого совпадает с канонической структурой автомата Мура.
┌───┐ ┌───┐ ┌┬──┬┐ ┌───┐
│MUX│ q │ROM│ ││RG│а │ROM│
a─>┤0а ├──>┤ │ S' │ ││ S Y
b─>┤1а а ╞═══>╡ │╞═╦>╡ ╞══>
а │ ╔>╡ │ │ ││ ║ ├─┐
а │ ║ │ 2 C│ ││ ║ │ 1 │ │
└A──┘ ║ └───┘а ─/┴┴──┴┘ ║ └───┘ │
│ Hа ╚═════════════════╝ │
└──────────────────────────────┘
Функцию перехода и функцию выхода реализуем в видеа ПЗУ.
В литературе, рассматривающей микропрограммные стройства уп-
равления, у с такой структурой называют микропрограммным ав-
томатом илкса.
В ПЗУ (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а ┌───┐ ┌───┐ ┌┬──┬┐
│MUX├──────────>┤ROMа │ROM│Yа ││RG│ Y'
a─>┤0а C а │ S ╞══>╡ │╞══>
b─>┤1а │ ─/┬┬──┬┐а а ╞═╦>╡ │Hа │ ││
а │ ╔>╡│RG│╞═>╡а а│ ║ ├──>┤ │├┐
а │ ║ │ ││S'│ 2 │ ║ │ 1 C│ │││
└A──┘ ║ └┴──┴┘а └───┘ ║ └───┘ ─/┴┴──┴┘│
│H'а ╚═══════════════╝ │
└────────────────────────────────────┘
СХЕМА С ЯВНЫМ КАЗАНИМа АЛЬТЕРНАТИВНЫХ АДРЕСОВ
╔═══════════════════════════╗
║╔═════════════════════════╗║
║║ ┌───┐ ┌┬──┬┐а ┌───┐A0║║
║║ │MUX│ ││RG│ │ROM╞══╝║
║╚>╡0а │ │ ││A │A1 ║
┌───┐╚═>╡1а ╞═══>╡ │╞═>╡ ╞═══╝
│MUXа │ │ │ ╞══>Y
a─>┤0а а а C│ │ а ├┐
b─>┤1а └A──┘а ─/┴┴──┴┘а └───┘│H
а ├────┘ │
└A──┘ │
└────────────────────────────┘
Конвейерный вариант
╔════════════════════════════╗
║╔══════════════════════════╗║
║║ ┌───┐а ┌────┐A0 ┌┬──┬┐A0'║║
║║ │MUX │ROM ╞══>╡│RG│╞═══╝║
║║ а │ │A1 │ ││A1' ║
║╚>╡0а │A │ ╞══>╡ │╞════╝
┌───┐╚═>╡1а ╞═>╡ │ Y │ │ Y'
│MUXа │ ╞══>╡ │╞══>
а а │ │ H │ ││
a─>┤0а а │ ├──>┤ │├┐H'
b─>┤1а └A──┘а └────┘ ─/┴┴──┴┘│
а ├────┘ C │
└A──┘ │
└────────────────────────────┘
Эта схема отличается от предыдущей тем, что, по сущес-
тву, тот же способ адресации выполнен с использованием только
одного ПЗУ. В этом варианте альтернативные адреса записывают-
ся в той же микроинструкции, что и микрокоманда.
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)>>
СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ АДРЕСА
Последовательный вариант Конвейерный вариант
┌────────────────────────┐ ┌─────────────────────────┐
│ ┌───┐ ┌┬──┬┐а ┌───┐│e │ ┌───┐ ┌───┐ e ┌┬──┬┐│
│ │MUX qа ││RG││q'│ROM├┘ │ │MUX│ q'│ROM├────>┤│RG│├┘
└>┤0а ├────>┤ │├─>┤ Y └>┤0а ├──>┤ │ Y │ ││Y'
a─>┤1а Sа │ ││S'а ╞══> a─>┤1а │ S'а ╞════>╡ │╞═>
b─>┤2а │ ╔══>╡ │╞═>╡ ╞══╗ b─>┤2а │ ╔>╡ │ H │ ││
│ ║а C│ │ а ╞╗ ║ а │ ║ а ├────>┤ │╞═╗
└A──┘ ║ ─/┴┴──┴┘а └───┘║ ║ │ ║ │ S │ ││ ║
║ Hа ╚════════════════╝ ║ │ ║ а ╞════>╡ │╞╗║
╚═══════════════════════╝ └A──┘ ║ └───┘ ─/┴┴──┴┘║║
║ H' ║ C ║║
║ ╚═════════════════╝║
╚═══════════════════════╝
При этом способе адресации альтернативные адреса отлича-
ются только одним разрядом ( в данном варианте -а младшима ),
формируемым входным сигналом. Остальные разряды адреса указы-
ваются вместе с микрокомандой в одной и той же микроинструк-
ции. При безусловном переходе в данном варианте схемы младший
разряд также казывается ва микроинструкции. При адресации
одного и того же микроблока различными операторами словного
перехода может возникнуть КОНФЛИКТ АДРЕСАЦИИ. Ва этома случае
одну и ту же микроинструкцию приходится располагать в различ-
ных ячейках правляющей памяти. Если различные операторы с-
ловного перехода одними иа теми же предикатнымиа значениями
указывают на одни и те же микроблоки, то нет и конфликт ад-
ресации.
Адрес
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
Распределять микроинструкции по ячейкама памяти добно
в следующем порядке:
- связать с различными операторами словного перехода, кон-
фликтующими между собой по адресации, различающиеся между со-
бой старшие разряды адреса;
- распределить микроблоки по ячейкам памяти с четом назнач-
енных старших разрядов адреса и входных значений;
- оставшимся нераспределенным микроблокама назначить произ-
вольные свободные адреса.
СХЕМА С СОКРАЩЕННЫМ ТАКТОМ
Использование этой схемы позволяет при сохранении пре-
имуществ последовательного варианта взаимодействия сократить
наиболее длинные цепи, общие для о и А, до длины цепей кон-
вейерного варианта.
┌──────────────────────────────────┐ ──┬──────────┬
│ ╔══════════════════════════╗│ ROM_0а A'│ Yа Hа A e│
│ ║ ┌────┐ ║│ ──┼──────────┼
│ ║ │ROM ╞═╬A ║│ 0 │m1а 0а 4 0│
│ ║ │ ├─╫e ║│ 1 │m0а 1а 1 x│
│ ╠>╡ ╞═╬Yа ┌───┐ ┌┬──┬┐║│ 2 │m0а 2а 3 x│
│ ║ │ ╞═╬Hа │MUXа ││RG│╞╝│ 3 │m5а 1а 3 x│
│ ║ │ 0а │ ╚══>╡0а а │ │├─┘e' 4 │m2а 1а 1 x│
│ A'║ ├────┤ а а │ ││ ──┴──────────┘
│ ║ │ROM ╞═╬Aа а ╞══>╡ │╞══>Y' ──┬──────────┬
│ ┌───┐║ │ │ ╠══>╡1а а │ ││ ROM_1а A'│ Yа Hа A e│
│ │MUX│╚>╡ ├─╫eа а C│ │╞╗H' ──┼──────────┼
└>┤0а │ ╞═╬Yа └A──┘ ─/┴┴──┴┘║ 0 │m4а 1а 2 x│
a>┤1а │ 1а ╞═╬H │ ║ 1 │m3а 0а 0 1│
b>┤2а └────┘ │ ║ 2 │m1а 0а 4 0│
а ├──────────────┘ ║ 3 │m3а 0а 0 1│
└A──┘ ║ ──┴──────────┴
╚══════════════════════════════╝
Способ адресации, по существу, такой же, как и ва преды-
дущей схеме. Только в рассматриваемой схемеа входной сигнал
управляет выбором одного из двух блоков ПЗУ (можно интерпре-
тировать этот сигнал как старший разряд адреса).
СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ
┌───┐а ┌──┐ 0W- +1
│MUX├─>┤M2├──┐ 1W- загрузка
0─>┤0а │┌>┤а │ ─V┬┬──┬┐а ┌───┐ Y
a─>┤1а ││ └──┘а W││CT│ │ROM╞══>
b─>┤2а ││ │ │ а │H
а ││ │ ││A ╞════╗
а ││ ╔══>╡ │╞═>╡ │e ║
└A──┘│ ║ │ │ а ├──┐ ║
║ │ ║а C│ │ а ╞═╗│ ║
║ │ ║ ─/┴┴──┴┘а └───┘S║│ ║
║ │ ╚═════════════════╝│ ║
║ └───────────────────────┘ ║
╚═════════════════════════════╝
В этой схеме при разветвлении процесс вычислений пара
альтернативных адресов получается следующим образом: один ад-
рес всегда на единицу больше, чем текущий (а т.е. изменяется
"регулярным" образом ), второй адрес - произвольный и содер-
жится вместе с микрокомандой в микроинструкции.
Элементом, "вычисляющим" адрес, является счетчмк, прав-
ляемый сигналом, являющимся входныма для УА. При различных
значениях входного сигнала счетчик выполняет две функции: ли-
бо прибавляет единицу к значению, которое хранилось в счетчи-
ке и являлось текущим адресом, либо загружается значением ад-
реса из правляющей памяти.
В схему введен элемента М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)>>
В схеме для конвейерного вариант взаимодействия регу-
лярное изменение адреса приходится организовывать так, чтобы
не величивать число мест конвейера.
╔══════════════════════════════╗
║╔═════════════════════╗ ║
║║ а┌┬──┬┐ ┌───┐║ ┌───┐S║
║║а ┌───┐а ││RG││ │MUX│║ │ROM╞═╝
║╚═>╡INC╞═>╡ │╞>╡0а │║ │Yа ┌┬──┬┐Y'
║ └───┘ C│ ││ │║ а ╞══>╡│RG│╞══>
║ ─/┴┴──┴┘ ╞╩>╡ а │ ││
║ ─/┬┬──┬┐ │A │Hа │ ││H'
║ C││RG││ а ╞══>╡ │╞══╗
╚═════════>╡ │╞>╡1а а │eа │ ││e'║
│ ││ а а ├──>┤ │├┐ ║
┌───┐а └┴──┴┘ └A──┘а └───┘ ─/┴┴──┴┘│ ║
│MUX ┌──┐ │ C │ ║
0─>┤0а ├─>┤M2├────┘ │ ║
a─>┤1а │┌>┤а │ │ ║
b─>┤2а ││ └──┘ │ ║
а ││ │ ║
└A──┘└─────────────────────────────┘ ║
╚═══════════════════════════════════╝
СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И
СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ
╔════════════════════════════╗ C
║╔═══════════════════╗ ║ ─/┬┬──┬┐H'
║║ ┌┬──┬┐ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗
║║ ┌───┐ ││RG││ │MUX│║ │ROM│ ║ ║ ┌>┤ │├─┐║
║╚>╡INC╞>╡ │╞>╡0а │║ │S║H║e│ └┴──┴┘ │║
║а └───┘C│ ││ │║ │ ║ ║ │ ┌┬──┬┐Y│║а для RG"Y"
║ ─/┴┴──┴┘ ╞╩>╡ ▐██████>╡│RG│╞>│║
║ ─/┬┬──┬┐ │A │ w c│ ││ │║а 0w-загрузка
║ C││RG││ а а ─A─/┴┴──┴┘ │║
╚═══════>╡ │╞>╡1а а │k ┌┬─┬┐k'│║а 1w-нет загрузки
│ ││ │ А ├────┴─>┤│T│├┐ │║
┌───┐а └┴──┴┘ └─A─┘а └───┘ ─/┴┴─┴┘│ │║а k ┌───┐
│MUX ┌──┐а ┌─┐│ C │ │║а └────┤ 1 ├─ CC
0>┤0а ├─>┤M2├─>┤&├┘ │ │║а ┌────┤ │
a>┤1а │┌>┤а │┌>┤ │ │ │║а SYNа └───┘
b>┤2а ││ └──┘│ └─┘ │ │║
││e' └──────────────────────────┘ │║а где CC -
└A──┘└──────────────────────────────────┘║ синхронизация о
╚═══════════════════════════════════════╝
Эта схема используется только ва конвейернома варианте
взаимодействия. Метод вычисления адреса для следующего такта
такой же, как и в схеме с регулярной адресацией. (Другой тер-
мин -"естественный" - потреблен только ради различения самих
схем.) Но в этой схеме, по сравнению c же рассмотренными,
разряд правляющей памяти с одним и тем же номером (разрядный
срез) в различныха микроинструкцияха можета быть использован
различным образом. Будем различать микроинструкции двуха ти-
пов:
- операционные,
- алресации (выбора).
В лданном варианте схемы тип микроинструкцииа устанавли-
вается разрядом с именема "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 ──▌─┼──┬──┬──┤
2 ▌1│ 1│ 1│ 2│
n3 { m3 } -- 3 ──▌─┼──┴──┴──┤
3 ▌0 m3 │
n4 { m4 } -- 4 4 ▌0 m4 │
──▌─┼──┬──┬──┤
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 ──▌─┼──┬──┬──┤
8 ▌1│ 1│ 1│ 7│
g4 <<GO(a;n5,n3)>>-- 8 9 ▌1│ 0│ 1│ 3│
Вместе с этой схемой обычно используется словная син-
хронизация, которая позволяет длинить такт выполнения микро-
команды в о на время выполнения микроинструкций адресации.
SYN ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌────
└─┘ └─┘ └─┘ └─┘ └─┘
| | | | |
k 0 ▄▄▄▄▄▄▄▄ 0 ▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄ 0 ▄▄▄
──────▀▀▀▀▀▀▀▀─────▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀─────▀▀▀
| | | | |
CC┐ ┌──────────┐ ┌────────────────────────────────────┐ ┌────
└─┘ └─┘ └─┘
| | | | |
Y────▄────────────▄──────────────────────────────────────▄───
─────▀────────────▀──────────────────────────────────────▀───
ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД.
ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ
Функциональный переход
При необходимости выполнения несколькиха вычислительныых
функций, правление которыми представляется в виде независи-
мых микропрограмм, необходимо организовать независимый вызов
этих микропрограмм.
Начальные адреса микропрограмм, правляющих вычислениями
различных функций, обычно существуют вне правляющей памяти.
В у достаточно предусмотреть механизма коммутации, позволя-
ющий сделать начальный адрес текущим. Это можно осуществить в
любой из рассмотренных схем. (К механизму коммутации относят-
ся, кроме аппаратуры, специальные разряды управляющей памяти
и специальные микроинструкции.)
╔══════════════════════╗ C
╔══════║══════════════╗ ║а ─/ ┬┬──┬┐H'
║ ║ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗
║ ║ │MUX│║ │ROM│ ║ ║ ┌>┤ │├─┐║
F ═║══════║════════>╡0а │║ │ ║ ║ │ └┴──┴┘ │║
║ ║ ┌┬──┬┐а а │║ │ ║ ║ │ │║
║ ║ ││RG│ а │║ │ ║ ║ │ │║
║ ╚>╡ │╞═>╡1а │║ │S║H║e│ │║
║ C│ │ а │║ │ ║ ║ │ ┌┬──┬┐Y│║ для RG"Y"
║ ─/┴┴──┴┘а а ╞╩>╡ ▐██████>╡│RG│╞>│║
║ ┌┬──┬┐а а │A │ │ ││ │║ 0w-загрузка
║ ┌───┐а ││RG│ а а │ w c│ ││ │║
╚>╡INC╞═>╡ │╞╦>╡2а │ а ─A─/┴┴──┴┘ │║ 1w-нет загр.
└───┘ C│ ││║ а │ │ │║
─/┴┴──┴┘║ а │ │ │║
╔══════════╝ а а │ │ │║
║ ┌┬─────┬┐а а а ┌┘k │║
╚>╡│STACK│╞═>╡3а а │Kа │ ┌┬──┬┐K' │║
└┴────A┴┘а а а ╞═══╧>╡│RG│╞╗а │║
║ │ А а │ │ ││║а │║
║ └─A─┘а └───┘ ─/┴┴──┴┘║а │║
┌───┐ ║ ║ C ║а │║
│MUX ┌──┐ ┌╨──────╨┐ ║а │║
0>┤0а ├─>┤M2├>┤а CS ╞<══════════════════╝а │║
a>┤1а │┌>┤а │ │ │ │║
b>┤2а ││ └──┘ └────────┘ │║ k ┌───┐
││e' │║ └─┤ 1 ├─CC
└A──┘└──────────────────────────────────────┘║ ──┤ │
╚═══════════════════════════════════════════╝ SYN └───┘
Переход к микроподпрограмме с возвратом
При реализации достаточно сложных вычислений добно вос-
пользоваться механизмом микроподпрограмм.
Одна и та же микроподпрограмм можета быть вызван из
разных точек вызывающиха микропрограмм. Поэтому приа вызове
микроподпрограммы необходимо запомнить адрес, c тем, чтобы
восстановить его при возвращении из микроподпрограммы. Чтобы
запомнить и восстановить адреса возврата ота вложенныха вызо-
вов, используется безадресная память - стек (stack).
Принцип (дисциплина) работы стека описывается словием
"последний вошел - первым вышел" (Last In - First Out, LIFO).
чтобы описать этот принцип будем считать, что слова, хранящи-
еся в стеке, перенумерованы с помощью первых натуральныха чи-
сел 1,2,...,N. Слово с наибольшим номерома называюта вершиной
стека.
Стек может выполнять следующие действия:
-"чтение" слова с наибольшим номером,
-"выталкивание" (стирание) из памяти слова с наибольшима номером,
-"запись" нового слова с присваиванием ему наибольшего номера.
При вызове микроподпрограммы выполняется операция "запи-
си" адреса возврата в стек. При возвращении иза микроподпрог-
раммы выполняется операция "чтения" адреса возврата, затема -
"выталкивания" его же из стека.
Операция "чтения" без "выталкивания" выполняется при ис-
пользовании стека для организации циклов.
Разряды с именем "К" определяют типа выполняемой микро-
инструкции. В связи с тем, что теперь ва схемеа существуета 4
источника адреса для правляющей памяти, возможны 4 тип бе-
зусловных переходов, кроме того, возможны различные словные
переходы в различных сочетаниях комбинирующие этиа источники
дреса и входные переменные.
С помощью комбинационной схемы CS разряды микроинструкции
"К" преобразуются в сигналы правления стеком и мультиплексо-
ром.
УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ
В конвейерном варианте для команд переходов по предикат-
ным переменным, зависящих без сдвига от сигналова правления,
приходится добавлять еще один такт для того, чтобы "увидеть"
значение переменной, по которой выполняется ветвление, и выб-
рать нужную МКИ.
Можно построить правляющий автомат, в котором для ско-
рения выполнения программы выполняются следующие действия:
Предварительно выбирается из ПЗУ одна из двуха альтернативных
МКИ, соответствующая наиболее вероятному значению переменной
ветвления. Это значение должно храниться в той МКИ, после ко-
торой выполняется ветвление. В конце такт выработанноеа ре-
льное значение переменной сравнивается с предсказанным, если
они совпадают, то выбранная из ПЗУ МКИ записывается ва выход-
ной регистр, если нет, то предыдущий такт продлевается, т.е.
не синхронизируются о и RG'МКИ. Микропрограмм будета такой
же как и для последовательного варианта взаимодействия О и
УА, но в МКИ добавляются два разряда:
F = { 1, если используется предвосхищение; 0, если нет },
P - наиболее вероятное значение переменной ветвления.
Фрагмент схемы УА, обеспечивающий предвосхищение может
быть таким:
──────────────┐а │ │W
┌┬──┬┐ │ ─V┬───┐ qа ┌A───┐а f
t ││RG││ └──>┤MUX├───>┤ SS ├<──────────────────────┐
──┬───>┤ │├────>┤ │┌──>┤ ├<─────────────────────┐│
│ │ ││ а ││tа │ p ││
─\┴┴──┴┘ └───┘│ ─\┴┬───┘ ││
│ │ │j ││
└───┼────────────────┘а │─V┬───┐ ┌─────┐ Pа ┌┬──┬┐p││
│ │MUXа │ ROM ├───>┤│RG│├─┘│
│ а │ │ Fа │ ││f │
│ │ │ ├───>┤ │├──┘
│ │ │ │ ││
│ │ │ ▐███>│ │▐██>
│ │ │ │ │ ││
C │ │ └─────┘ ─\A┴┴──┴┘
────┴───────────────────┴───────────────────┘└────── 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