Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)
| Сдавался/использовался | 1998г. |
| Загрузить архив: | |
| Файл: hai-0652.zip (51kb [zip], Скачиваний: 69) скачать |
Антик М.И. 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) Математическое обоснование алгоритма вычислений:
Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа-
ется в том, что НОД двух натуральных чисел А и В в случае ра-
венства этих чисел совпадает с любым из них, ав случаеих
неравенства совпадает с НОД двухдругих чисел:меньшегои
разности между большим и меньшим.Последовательно,уменьшая
числа, получим два равных числа -значение одного из них и бу-
дет НОД исходных чисел.
3) Блок-схема алгоритма (микропрограмма в содержательном
виде):
█
│
┌──────V──────┐
m1│rO: = 0 │
└──────┬──────┘
│┌──────────────────┐
││┌─────┐ │
─VVV─ │ │
/ 0 │ │
< rI>─────┘ │
_/ │
│1 │
┌──────V──────┐│
│rO: = 0 ││
│ ││
m2│ А: = I1 ││
│ ││
│ B: = I2 ││
└──────┬──────┘│
┌───────────────────┐│ │
│ ┌─────VV──────┐│
│ m3│ (p,S)=A - B ││
│ └──────┬──────┘│
│ ─V─ m6 │
│ / =0 ┌──────────┐│
│ z
│ __/ └──────────┘
│ │╪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<
m2{rO:=0; A:=I1; B:=I2}
m3{(p,S)=A-B}
<
g2<
m4{(x,B:)=-A+B}
<
m5{(x,A:)= A-B}
<
m6{rO:=1}
<
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├──>
││ │
││zp umB uwA uwB uiA urO uwO │
│ └┬──┬──A───A───A───A───A───A─────┘
│ ││ │ │ │ │ │ │
│ ││ │ │ │ │ │ │
│ ┌V──V──┴───┴───┴───┴───┴───┴─────┐
││zp y1y2y3 y4y5y6 │
││ │
┴──/C │
│ УА │
──>┤rI │
└────────────────────────────────┘
УА должен выполнять следующий алгоритм автоматного типа,
представленный в виде блок-текста:
m1{xxxx10}
g1<
m2{111x10}
m3{x000x0}
<
g2<
m4{0011x0}
<
m5{0100x0}
<
m6{x0xx01}
<
МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ.
МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ-
ходимое для получения (вычисления) значения однойили более
переменных.
Микрооперация присваивания В=А означает, что переменные
левой части получают значениявыраженияиз правойчасти.
Всегда разрядность левой части равна разрядности правойчас-
ти. При этом биты, расположенные на одной и той же позициив
левой и правой частях, равны.
Неиспользуемые разряды в левой части и произвольные зна-
чения в правой части микрооперации присваиванияобозначаются
(х). Например:
(В[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
│
│ ___/ │ ___/
│ │╪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)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальным по-
тенциальным параллелизмом (врамках даннойалгоритмической
идеи), и,следовательно, его реализацияв видеКСобладает
максимальным быстродействием по сравнениюс любымидругими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представлениеиего реализацияявляются
статическим отображением входных объектовна выходные:это
исключает возможность работы с объектами, которые "ведутсе-
бя" более сложно во времени;невозможнотакже реализовать
принципиально рекуррентныеалгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, еслиформальноалгоритм функционального
типа может быть записан, топроектированиеустройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом напро-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из нихводин
функциональный модуль, выполняющий эти операциипо очереди.
Такое решение потребует запоминания всех переменных(входных
и выходных),связанных с выполнением этих операций.Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурнойреализациии,следовательно,к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшитьсявремя следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений -но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритмефункциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простуюмодель ввиденаправленного
графа. Вершины графа будут соответствовать операциям, адуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальныйграф всегдабудет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которыерасполо-
жены на одном и том же пути в сигнальном графе, либо нааль-
тернативных путях решения.
МИНИМИЗАЦИЯ АППАРАТУРЫ
Может оказаться, что на одном путивсигнальном графе
расположены операции, плохо или вовсе не совмещаемыедругс
другом (т.е. совмещение не дает экономии в аппаратуре функци-
онального модуля). Возможно также, что проведеннаяминимиза-
ция, сохраняющая минимальное время,не позволяетвыполнить
ограничение на объем аппаратуры. Втаком случаенеобходима
более глубокая минимизация,охватывающая параллельныеветви
сигнального графа. Минимизация должна быть взаимосвязанной по
всем компонентам ОА: по памяти, функциональным модулям и ком-
мутации.
В настоящее время процедуры минимизации не формализованы
и сводятся к перебору "правдоподобных" вариантов.
Можно предложить следующую последовательность действий:
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─ └┴──┴─┘ ├─ │ └────┘
│
└──────
__/
(реализация счетчика J не показанa).
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре D. Тогда получим:
───┬── AD
│ ┌┬──┬┐ ┌┬──┬─┐ 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─
│ └────── __/ Промежуточный регистр 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─ │ └────── __/ Слово В нельзя реализовать в виде регистра, а тольковвиде отдельных триггеров. Можно
формировать слово с использованием операции
сдви- га при обязательном условии 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─ │ └────── __/ └────┘ В этом случае, так же, как и в предыдущем, чаще всего
нену- жен промежуточный регистр (В).
УНИВЕРСАЛЬНЫЙОА Использование
при проектировании универсальных ОА с
за- ранее фиксированной и минимизированнойструктурой
оправдано тем, что такие универсальныеОА
изготавливаютсяпромышлен- ностью в виде БИС большим тиражом и поэтому онисравнительно дешевы. Такие универсальные ОА входят в микропроцессорные
на- боры 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 происходит в случайный момент
времени (асинхронно), но при этом начальныйтакт
работыустройства должен быть полным. "Затягивание"
асинхронногосигналаНв синхронный режим происходит с помощью простейшего
синхронного автомата с диаграммой:
┌──────────┐
┌────────┐
V0H/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
< │ │<──┐ │ ┌V┐ 0│ n3 { m3 } g1│< a
>─┘ │ └┬┘ n4 { m4 } │
1│<────┐ │
│┌───┐│ g2
< │┌─VV┐││ n3│
│m3 │
││ n5
{ m5 } │└─┬─┘││ │┌─V─┐││ g3 < 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│
<
1│m2 0│ 1
0│ 2│ d1 { m0 } │ │ 1 1│ 3│
│ │ ││
<
│ │ 2 1│ 3│ n3 { m3 } │ │ ││
3│m3 x│ 3
0│ 4│ n4 { m4 } │ │ 3 1│ 4│
│ │ ││
<
│ │ 4 1│ 0│ d2 { m0 } │ │ ││
5│m0 1│ 5
0│ 6│
<
│ │ ││ n5 { m5 } 6│m6
0│ 6 0│ 6│
│ │ 6 1│ 4│
< Конвейерный
вариант схемы с таким же способом
адресации должен программироваться с учетом замечаний, сделанных в
раз- деле "Взаимодействие ОА и УА".Кроме
того,ограниченияна расположение микрокоманд в 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
x1
1│ │ │ <
│ │ d1 { m0
}
2│m0 023│ │ │ <
│ │ n3 { m3
}
4│m4 050│
│ │ n4 { m4
} 5│m0 16
4│
│ │ <
─┴──────────┘ d2 { m0
} < n5 { m5
} < СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ
АДРЕСА Последовательный
вариант Конвейерный вариант ┌────────────────────────┐
┌─────────────────────────┐ │
┌───┐
┌┬──┬┐┌───┐│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│
│ │
< │ │ d1 { m0
} --(1,0) 1 0 │m0 1 1
x│
│ │ <
│ │ n3 { m3
} --(1,1),(3,1) 2 0 │m0 2 3 x│
│ │ n4 { m4
} --(0,1) 2 1 │m1 0 4
0│
│ │ <
│ │ d2 { m0
} --(2,0) 3 1 │m3 0 0
1│
│ │ <
│ │ n5 { m5
} --(3,0)
────┴────────┘ < Распределятьмикроинструкциипо
ячейкампамятиудобно в следующем порядке: - связать с
различными операторами условного перехода,
кон- фликтующими между собой по адресации, различающиеся между
со- бой старшие разряды адреса; - распределить
микроблоки по ячейкам памяти с учетом назнач- енных старших разрядов адреса и входных значений; - оставшимся
нераспределенным микроблокам
назначитьпроиз- вольные свободные адреса.
СХЕМА С СОКРАЩЕННЫМ ТАКТОМ Использование
этой схемы позволяет присохранениипре- имуществ последовательного варианта взаимодействиясократить наиболее длинные цепи, общие для ОА и УА, до длины цепей
кон- вейерного варианта. ┌──────────────────────────────────┐
──┬──────────┬ │
╔══════════════════════════╗│ ROM_0
A'│ YHA e│ │
║ ┌────┐ ║│ ──┼──────────┼ │
║ │ROM ╞═╬A ║│ 0 │m104
0│ │
║ │
├─╫e
║│ 1 │m011
x│ │
╠>╡
╞═╬Y
┌───┐
┌┬──┬┐║│ 2 │m023
x│ │ ║
│ ╞═╬H│MUX│
││RG│╞╝│ 3 │m513
x│ │
║ │ 0│
╚══>╡0
│ │││├─┘e' 4 │m211
x│ │
A'║ ├────┤ │
│ ││││
──┴──────────┘ │
║ │ROM ╞═╬A│
╞══>╡│
│╞══>Y'
──┬──────────┬ │ ┌───┐║
│ │
╠══>╡1
│ ││││ ROM_1
A'│ YHA e│ │ │MUX│╚>╡ ├─╫e│А
│C│││╞╗H'
──┼──────────┼ └>┤0
││ ╞═╬Y└A──┘ ─/┴┴──┴┘║0 │m412
x│ a>┤1
││ 1╞═╬H │
║1
│m300 1│ b>┤2
│
└────┘ │ ║2 │m104
0│ │А
├──────────────┘║3 │m300
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
│ YHe
S│
──┼───────────┤ n2 { m2 }
-- 1 0 │m1x
x1│
│ │
<
│ │ d1 { m0
} -- 2 2 │m01
12│
│ │ <
│ │ n3 { m3
} -- 3 4 │m41
00│
│ │ n4 { m4
} -- 4 5 │m02
03│
│ │ <
│ │ d2 { m0
} -- 5 7 │m00
13│
──┴───────────┘ < n5 { m5
} -- 6 < В схеме для
конвейерного варианта
взаимодействиярегу- лярное изменение адреса приходится организовывать
так,чтобы не увеличивать число мест конвейера.
╔══════════════════════════════╗
║╔═════════════════════╗ ║
║║ ┌┬──┬┐
┌───┐║
┌───┐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──┘└──────────────────────────────────┘║
синхронизация ОА
╚═══════════════════════════════════════╝ Эта схема
используетсятольков
конвейерномварианте взаимодействия. Метод вычисления адреса для
следующеготакта такой же, как и в схеме с регулярной адресацией. (Другой
тер- мин -"естественный" - употреблен только ради
различения самих схем.) Но в этой схеме, по сравнениюс
ужерассмотренными, разряд управляющей памяти с одним и тем же номером
(разрядный срез) в различных
микроинструкцияхможетбыть
использован различным образом. Будем различать микроинструкциидвух
ти- пов: - операционные, - алресации
(выбора). В лданном
варианте схемы тип микроинструкции
устанавли- вается разрядом с именем
"k".Приk=0
выполняетсямикро- инструкция операционного типа. Все остальныеразряды
ячейки загружаются в регистр
микрокомандыиуправляют выполнением микроопераций в ОА. Следующий адрес всегда на единицу
больше. Приk=1
выполняетсямикроинструкцияадресации.
Все разряды микроинструкции могут быть использованы длявычисле- ния следующего адреса. В данном варианте схемы, так же
каки в схеме с регулярной адресацией, один из адресов явно
записы- вается в микроинструкцию, другой альтернативный адрес на
еди- ницу больше текущего.
Адрес A
▌k│ Y │ n1 { m1 }
-- 0
▌ │ H│ e│ S│
──▌─┼──┴──┴──┤ n2 { m2 }
-- 1 0
▌0│m1 │ 1
▌0│m2 │ g1 <
2 ▌1│ 1│ 1│ 2│ n3 { m3 }
-- 3
──▌─┼──┴──┴──┤ 3
▌0│m3 │ n4 { m4 }
-- 4 4
▌0│m4 │
──▌─┼──┬──┬──┤ g2 <
6
▌1│ 2│ 0│ 3│ g3 <
7 ▌0│m5 │ n5 { m5 }
-- 7
──▌─┼──┬──┬──┤ 8 ▌1│ 1│
1│ 7│ g4 < Вместе с этой
схемой обычно используетсяусловнаясин- хронизация, которая позволяет удлинить такт выполнения
микро- команды в ОА на время выполнения микроинструкций
адресации. 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 └───┘ Переход к
микроподпрограмме с возвратом При реализации
достаточно сложных вычислений удобно вос- пользоваться механизмом микроподпрограмм. Одна и та же
микроподпрограммаможетбыть
вызванаиз разных точек вызывающих
микропрограмм.Поэтомупри
вызове микроподпрограммы необходимо запомнить адрес,с
тем,чтобы восстановить его при возвращении из
микроподпрограммы.Чтобы запомнить и восстановить адреса возврата отвложенных
вызо- вов, используется безадресная память - стек (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, еслиs0, еслиs0, еслиs0, еслиs1, тоw=1, j=q, переход вs0