Реферат: Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

_АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА
Алгоритмы этого типа являются следующим этапом обобщения
описаний вычислительных процессов. Теперь, по сравнению с ал-
горитмами автоматного типа, на каждом шаге, помимо модифика-
ции памяти, идентифицирующей шаг алгоритма, разрешается изме-
нять любую другую память устройства локально (по частям) или
глобально (всю сразу).
Устройство-исполнитель алгоритма этого типа будем назы-
вать операционным устройством (ОУ).
ОУ можно рассматривать как один синхронный автомат со
сложно структурированной памятью - состоянием: часть памяти
используется для идентификации шага алгоритма, остальная па-
мять используется для запоминания промежуточных данных, вы-
числяемых в процессе последовательного, по шагам, выполнения
алгоритма. Такая модель вычислителя особенно удобна для рас-
чета продолжительности одного такта работы устройства.
Другой удобной моделью вычислителя является совокуп-
ность взаимодействующих синхронных автоматов, один из которых
называется управляющим автоматом (УА), а объединение всех ос-
тальных автоматов называется операционным автоматом (ОА).
УА является исполнителем алгоритма автоматного типа, ко-
торый входит составной частью в любой алгоритм процедурного
типа. Кроме того, УА инициирует действия отдельных шагов ал-
горитма и участвует в их выполнении.
ОА выполняет все вычисления на отдельных шагах алгоритма
под управлением УА; кроме того, к ОА удобно отнести все вы-
числения предикатных функций, оставив УА только анализ вычис-
ленных предикатных значений.
Прежде чем переходить к точным терминам, рассмотрим сле-
дующиe примеры алгоритмов процедурного типа.
Например, каноническое описание синхронного конечного
автомата может быть интерпретировано (истолковано) как одно-
шаговый алгоритм процедурного типа.

?
???????? ?
? ???V??V??????
? ? B=FO(S,A) ?
? ? ?
? ? S:=FS(S,A)?
? ?????????????
???????????

Исполнитель этого алгоритма состоит только из ОА. На
каждом шаге этого алгоритма изменяется вся память устройства,
поэтому управление памятью не требуется, идентифицировать ша-
ги этого алгоритма не надо.
Например, инкрементор с одноразрядным входом и однораз-
рядным выходом может быть реализацией следующих преобразова-
ний:
?
? p:=1 ?
?
?????????? ?
? ??????V?V????????
? ? (p:, b) = a+p ?
? ?????????????????
????????????

- 2 -
ОА, реализующий инкрементор в целом, будет следующим:
??????
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

- 3 -
как неотрицательное целое число, являющееся порядковым номе-
ром метки в списке меток оператора 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) Блок-схема алгоритма (микропрограмма в содержательном
виде):

- 4 -

?
?
???????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 ???>? 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<>
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}
<>

- 5 -

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.

- 6 -
Для управления вычислениями на каждом шаге алгоритма
потребуются следующие управляющие сигналы:

?umA?umB?uwA?uwB?uiA?uiB?urO?uwO?
???????????????????????????????????
m1? ? ? ? ? ? ? 1 ? 0 ?
???????????????????????????????????
m2? 1 ? 1 ? 1 ? 1 ? ? ? 1 ? 0 ?
???????????????????????????????????
m3? ? ? 0 ? 0 ? 0 ? 1 ? ? 0 ?
???????????????????????????????????
m4? ? 0 ? 0 ? 1 ? 1 ? 0 ? ? 0 ?
???????????????????????????????????
m5? 0 ? ? 1 ? 0 ? 0 ? 1 ? ? 0 ?
???????????????????????????????????
m6? ? ? 0 ? ? ? ? 0 ? 1 ?
???????????????????????????????????

В незаполненных клетках сигналы безразличны.
Заметив, что umA = umB, uiB = ?uiA, окончательно полу-
чаем:
????????????????????????????????????????????????
? A ???????????????????????????????>D
? ?????? ?/?????? ? ?????? ???????? ?
? ? 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?
?????????????????????

- 7 -

Структура вычислителя:
??????????????????????????????????
??>?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{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 ) - выходами.
Микрооперация ( : ) - двоеточие - означает запоминание
(изменение значения) в памяти устройства. Переменная типа па-
мять сохраняет свое значение между двумя очередными присва-
иваниями.

- 8 -
Микрооперации всегда входят в состав микрооператоров.
МИКРООПЕРАТОР - набор взаимосвязанных микроопераций (или
одна микрооперация ), выполняемых одновременно и необходимых
для получения одного или более значений. Например:
( 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 асинхронно, но в
следющем такте.
Всегда предполагается, что предикат вычисляется вместе
(в одном такте) с тем микроблоком, за которым непосредственно
следует его использование.Таким образом, здесь, также как и в
микроблоке, используется старое значение памяти, существовав-
шее перед входом в микроблок. Это связано с особенностями
взаимодействия ОА и УА. Например:

- 9 -

? ?
? 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???? ? ? ?
??????????????????????????????????????????????????
сигналы управления

Столь четкого разграничения операций на зоны (память, комму-
тация, функции) может и не быть. Например, такие широко ис-
пользуемые функции как сдвиги либо хорошо совмещаются с
коммутацией, либо интегрируются с регистрами хранения.Также
часто интегрируются с хранением функции инкремента и

- 10 -
декремента (счетчики обычные и реверсивные).
Особо выделим сигнал yС, управляющий доступом синхросиг-
налов в ОА. Такой вариант управления, называемый условной
синхронизацией, позволяет запретить любые изменения памяти ОА
в каком-либо такте. Причем, если рабочим является срез (зад-
ний фронт) сигнала синхронизации, то используется элемент И,
как и показано на рисунке.Если же рабочим является фронт (пе-
редний фронт) сигнала, то используется элемент ИЛИ. (Первый
перепад сигнала синхронизации в новом такте не должен быть
рабочим.)

_ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА
При проектировании вычислительного устройства основными
являются ограничения на:
1)- время вычисления;
2)- объем аппаратуры, реализующей вычисления;
3)- тип применяемых базовых функций.
ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ
Алгоритм функционального типа обладает максимальным по-
тенциальным параллелизмом (в рамках данной алгоритмической
идеи), и,следовательно, его реализация в виде КС обладает
максимальным быстродействием по сравнению с любыми другими
вычислителями. Невозможность реализации вычислителя в виде КС
может быть обусловлена следующими причинами:
- слишком велик объем аппаратуры КС;
- функциональное представление и его реализация являются
статическим отображением входных объектов на выходные: это
исключает возможность работы с объектами, которые "ведут се-
бя" более сложно во времени; невозможно также реализовать
принципиально рекуррентные алгоритмы (см.,например,алгоритм
Евклида для нахождения НОД).
Тем не менее, если формально алгоритм функционального
типа может быть записан, то проектирование устройства надо
начинать с записи именно такого алгоритма.
Минимизация аппаратуры "сложной" КС с переходом на про-
цедурный вариант реализации связан с "экономией" числа опера-
ционных элементов, т.е. со слиянием некоторых из них в один
функциональный модуль, выполняющий эти операции по очереди.
Такое решение потребует запоминания всех переменных (входных
и выходных),связанных с выполнением этих операций. Требуется
также управление памятью, связанной с этим функциональным мо-
дулем, а также - может быть - управление самим функциональным
модулем, если он объединил существенно различные функции.
Переход к процедурной реализации и, следовательно, к
дискретизации времени неизбежно увеличит время вычисления од-
ного результата - даже при реализации структуры подобной КС.
При этом, как ни странно, может уменьшиться время следующих
друг за другом вычислений именно за счет дискретизации време-
ни и применения так называемых "конвейерных" вычислений - но
об этом речь пойдет в другом курсе.
Рассмотрим возможность сокращения аппаратуры без увели-
чения времени решения, достигнутого в алгоритме функциональ-
ного типа. Сопоставим схеме устройства, реализующего алгоритм
функционального типа, простую модель в виде направленного
графа. Вершины графа будут соответствовать операциям, а дуги
- переменным алгоритма. Назовем такой граф сигнальным (графом
потоков данных). Заметим, что сигнальный граф всегда будет
ациклическим.
Минимальность времени вычислений сохранится, если совме-
щать в один функциональный модуль операции, которые располо-
жены на одном и том же пути в сигнальном графе, либо на аль-
тернативных путях решения.

- 11 -

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

- 12 -
Запишем этот фрагмент алгоритма иначе так, чтобы нужный
бит извлекался за счет сдвига в регистре 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?
? ????????????>
\__/

Промежуточный регистр 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], тогда алгоритм и его ре-
ализация имеют вид:

- 13 -

??????
? 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?
? ?????????>?B:=D?>
\__/ ??????

В этом случае, так же, как и в предыдущем, чаще всего не ну-
жен промежуточный регистр (В).

_УНИВЕРСАЛЬНЫЙ ОА
Использование при проектировании универсальных ОА с за-
ранее фиксированной и минимизированной структурой оправдано
тем, что такие универсальные ОА изготавливаются промышлен-
ностью в виде БИС большим тиражом и поэтому они сравнительно
дешевы. Такие универсальные ОА входят в микропроцессорные на-
боры 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 - входная и выходная информационные шины.

- 14 -
Р - предикатные сигналы (флажки).
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- время установления соответствующего компонента цепи.
Чтобы сократить длину этой цепи, применяют другой вари-
ант взаимодействия автоматов - конвейерный:

- 15 -

????????????????????????????
??????? ?????? ?????? ?
?? CS ? ??RG?? ?CS ? ? ? ????????????? b ? ? ?? ?? ? c ? ? FF ?????? ? ??????A? ?????? ?
? ?????? ?????? ? ????????????? ?
?????RG?? ?? ?? ?? ? 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 ?
л ?
??????????????????????????????
У этого автомата простейшей является функция переходов, так
как диаграмма автомата совпадает с диаграммой переходов

- 16 -
D-триггера.
Схема автомата вместе с цепями условной синхронизации
выглядит следующим образом (для синхронизации по фронтам):
а)-по переднему фронту, б)- по заднему фронту:
???? ????
SYN ?????????????? 1??? CC SYN ?????????????? &??? CC
? ????? ??? ? ? ????? ??? ?
??/C?T? ? ???? ??\C?T? ? ????
? ? ? ? ? ? ????
???D? ? ? ???D? ?
? ??? o??? ? ??? o?
??oR? ? ??oR? ?
H ? ?????уст. нач. зн. H ? ?????уст. нач. зн.
?????????????????????? ??????????????????????

Такая разница в цепях условной синхронизации, как уже объяс-
нялось выше, определяется тем, что первый перепад сигнала СС
не должен быть рабочим.