Читайте данную работу прямо на сайте или скачайте

Скачайте в формате документа WORD


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

нтик М.И. 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