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

Методичка для курсового проектирования по ПТЦА прикладная теория цифровых автоматов 2Антик М. И. 110391 МИРЭА Алгоритмы этого типа являются следующим этапом обобщения горитмами автоматного типа, на каждом шаге, помимо модифика- ции памяти, идентифицирующей шаг алгоритма, разрешается изме- глобально (всю сразу). Устройство-исполнитель алгоритма этого типа будем назы- вать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти мять используется для запоминания промежуточных данных, вы- числяемых в процессе последовательного, по шагам, выполнения чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп- называется управляющим автоматом (УА), а объединение всех ос- УА является исполнителем алгоритма автоматного типа, ко- типа. Кроме того, УА инициирует действия отдельных шагов ал- горитма и участвует в их выполнении. ОА выполняет все вычисления на отдельных шагах алгоритма числения предикатных функций, оставив УА только анализ вычис- дующи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│ │ │ │└─┴─┘ │ └───────────────┘ код начального состояния требует предварительной установ- ки. Ограничимся здесь обозначением этой проблемы, а решение ее, связанное прежде всего с корректной синхронизацией ус- тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк- вивалентного автомату Мили , не обсуждалась простая возмож- что рассмотренный автомат Мили может быть преобразован в эк- ┌┬─┬┐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)- Описание переменных и начальных значений памяти. функциональные связи (в том числе предикатные), не использу- ющие запоминания. Переменные из левой части операции присва- ивания таких функциональных описаний используются в блоках - операторные - в скобках вида {.....}, - перехода - в скобках вида <<...>>; блоком. В блоках перехода используется оператор GO в одной из двух форм: GO m - безусловный переход, GO (P; m0,m1,m2,...) - условный переход. здесь m0,m1,... - метки блоков, P - предикатное значение,интерпретируемое оператором GO - 3 - быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма. На следующем более сложном примере демонстрируется пос- ледовательность синтеза операционного устройства. двух натуральных чисел (8-разрядных). 1) Разработаем интерфейс вычислителя: 8 ┌──┬─────┬──┐ ═══╪═>╡I1│ НОД │ │ │ │ │ │ 8 8 │ │ │D ╞══╪══> ═══╪═>╡I2│ │ │ ├──┤ ├──┤ ─────>┤rI│ │rO├─────> ├──┤ │ │ ─────>┤ C│ │ │ └──┴─────┴──┘ I1[7.. 0], I2[7.. 0] -входные информационные шины. rI -входной сигнал готовности: если rI=1, то на входах I1, тат на шине D, который сохраняется до появления новых операн- дов. Идея алгоритма, следуя Евклиду (IIIв. до р. Х.), заключа- ется в том, что НОД двух натуральных чисел А и В в случае ра- венства этих чисел совпадает с любым из них, а в случае их неравенства совпадает с НОД двух других чисел: меньшего и числа, получим два равных числа -значение одного из них и бу- дет НОД исходных чисел. виде): - 4 - █ │ ┌──────V──────┐ │ rO: = 0 │ └──────┬──────┘ │┌──────────────────┐ ││┌─────┐ │ ─VVV─ │ │ / \ 0 │ │ < rI>─────┘ │ \_/ │ │1 │ ┌──────V──────┐ │ │ rO: = 0 │ │ │ │ │ │ А: = 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 │ │ └───────┬──────┘ └───────┬──────┘ └──────────┴────────────────────┘ Или в виде блок-текста: D[7.. 0] --выходная шина rI, rO --сигналы готовности A[7.. 0]:, B[7.. 0]: --память текущих значений S[7.. 0] --разность z, p --предикатные переменные ┐(!/S) --сжатие(свертка) S[7.. 0] по ИЛИ-НЕ D=A ------------------------------------------------------------------- m1{rO:=0} <<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)>> <<GO m3>> m5{(x,A:)= A-B} <<GO m3>> <<GO g1>> - 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│ ══╬═══╪═══╪═══╪═══╪═══╪═══╪═══╪═══╡ ║ │ │ │ │ │ │ 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 │ ──╫───┼───┼───┼───┼───┼───┼───┼───┤ ║ │ │ 0 │ │ │ │ 0 │ 1 │ ──╨───┴───┴───┴───┴───┴───┴───┴───┘ В незаполненных клетках сигналы безразличны. ┐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│ ══╬══╪══╪══╪══╪══╪══╡ ║ │ │ │ │ 1│ 0│ ──╫──┼──┼──┼──┼──┼──┤ m2║ 1│ 1│ 1│ │ 1│ 0│ ──╫──┼──┼──┼──┼──┼──┤ ║ │ 0│ 0│ 0│ │ 0│ ──╫──┼──┼──┼──┼──┼──┤ m4║ 0│ 0│ 1│ 1│ │ 0│ ──╫──┼──┼──┼──┼──┼──┤ ║ 0│ 1│ 0│ 0│ │ 0│ ──╫──┼──┼──┼──┼──┼──┤ ║ │ 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 │ └────────────────────────────────┘ УА должен выполнять следующий алгоритм автоматного типа, <<GO(rI;g1,m2)>> <<GO(z;g2,m6)>> <<GO(p;m4,m5>> <<GO m3>> m5{0100x0} <<GO m3>> <<GO g1>> МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ- ходимое для получения (вычисления) значения одной или более переменных. Микрооперация присваивания В=А означает, что переменные Всегда разрядность левой части равна разрядности правой час- ти. При этом биты, расположенные на одной и той же позиции в Неиспользуемые разряды в левой части и произвольные зна- ного числа с присваиванием произвольного значения младшему разряду и с потерей старшего после знака разряда. А, напри- мер, микрооперация (B[7.. 0],d) = (A[7],A[7.. 0]) означает арифметический сдвиг вправо на один разряд. Микрооперация описывает действие, выполняемое стандартным 4-разрядным сум- Микрооперация ( : ) - двоеточие - означает запоминание - 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 полняются одновременнo на двух разных сумматорах. При реализации микроблока { A:= B ; B:= 0 } обязательна реализовать асинхронно, но это приводит к ошибке ). Другой следющем такте. (в одном такте) с тем микроблоком, за которым непосредственно следует его использование. Таким образом, здесь, также как и в - 9 - █ █ █ CT:=(╪0)█ █ CT:=(╪0)█ █ █ │ │ ┌────V───┐ ┌────V───┐ │ 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│└─┘ █ █ █ └────────────────────────────────────────────────┘ Столь четкого разграничения операций на зоны (память, комму- тация, функции) может и не быть. Например, такие широко ис- пользуемые функции как сдвиги либо хорошо совмещаются с часто интегрируются с хранением функции инкремента и - 10 - Особо выделим сигнал yС, управляющий доступом синхросиг- ний фронт) сигнала синхронизации, то используется элемент И, как и показано на рисунке. Если же рабочим является фронт (пе- редний фронт) сигнала, то используется элемент ИЛИ. (Первый При проектировании вычислительного устройства основными являются ограничения на: ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ Алгоритм функционального типа обладает максимальным по- тенциальным параллелизмом (в рамках данной алгоритмической идеи), и,следовательно, его реализация в виде КС обладает максимальным быстродействием по сравнению с любыми другими вычислителями. Невозможность реализации вычислителя в виде КС может быть обусловлена следующими причинами: исключает возможность работы с объектами, которые "ведут се- бя" более сложно во времени; невозможно также реализовать принципиально рекуррентные алгоритмы (см.,например,алгоритм Евклида для нахождения НОД). Тем не менее, если формально алгоритм функционального типа может быть записан, то проектирование устройства надо начинать с записи именно такого алгоритма. Минимизация аппаратуры "сложной" КС с переходом на про- "экономией" числа опера- и выходных),связанных с выполнением этих операций. Требуется модулем, если он объединил существенно различные функции. Переход к процедурной реализации и, следовательно, к ного результата - даже при реализации структуры подобной КС. При этом, как ни странно, может уменьшиться время следующих друг за другом вычислений именно за счет дискретизации време- "конвейерных" вычислений - но ного типа. Сопоставим схеме устройства, реализующего алгоритм графа. Вершины графа будут соответствовать операциям, а дуги потоков данных). Заметим, что сигнальный граф всегда будет ациклическим. тернативных путях решения. _МИНИМИЗАЦИЯ АППАРАТУРЫ Может оказаться, что на одном пути в сигнальном графе другом (т. е. совмещение не дает экономии в аппаратуре функци- онального модуля). Возможно также, что проведенная минимиза- ция, сохраняющая минимальное время, не позволяет выполнить более глубокая минимизация,охватывающая параллельные ветви сигнального графа. Минимизация должна быть взаимосвязанной по всем компонентам ОА: по памяти, функциональным модулям и ком- мутации. и сводятся к перебору "правдоподобных" вариантов. "похожие" функции (операции) реализовать на одном функциональном модуле, например, все суммирования выполнять 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], тогда алгоритм и его ре- ализация имеют вид: - 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─ │ <K / \ =K ┌────┐ └──────<J==K>──>┤B:=D├> \__/ └────┘ жен промежуточный регистр (В). дешевы. Такие универсальные ОА входят в микропроцессорные на- боры 582, 583, 584, 588, 589, 1800, 1804 и т. д., которые на- ными. В основе перечисленных универсальных ОА лежит следующая структура: ╔══════════════════╦═══════════════════════════╗ ║ ║ ║ ║ ║ SYN┐ ACC ║ ║ ┌─┬─────┬┐ ║ ─/┬┬──┬┐ ┌─────┐ ║ ║ │ │ RGF ││ ║ C││RG││ │ ALU │ ║ ║ │ │ ││ ║ ││ ││ │ │ ║ ║ │ │ ││ ╚════>╡│ │╞═════>╡ │ ║ ║ │ │ ││ ││ ││ │ ╞═══╩═>DO ╚═══>╡D│ ││ └┴──┴┘ │ │ │ │ ││ T │ │ │ │ ││ ┌┬──┬┐ │ ╞═════>P │ │ ││ ││RG││ │ │ │ │ │╞═════════>╡│ │╞═════>╡ │ │ │ ││ ││ ││ │ │ │А│ ││ C││ ││ ╔═>╡ │ ─o─A┴A┴─────┴┘ ─┬┴┴──┴┘ ║ └──A──┘ ┘ │ ║ SYN┘ ║ ║ │ ║ ║ ║ yW YA DI═════╝ YF ALU - арифметико-логическое устройство - комбинационная схема с небольшим, но универсальным набором арифметических и RG'T' - регистр-фиксатор со статической синхронизацией. RG'АCC' - регистр-аккумулятор с динамической синхрониза- цией. DI,DO - входная и выходная информационные шины. - 14 - yW - разрешение записи в RGF. го,чтобы такая память могла работать в замкнутом информацион- цией. Если передний фронт является рабочим для регистров уп- равляющего автомата и RG'ACC', то на первой фазе синхрониза- ции при SYN=1 информация читается из RGF; при этом RG'T' прозрачен. На следующей фазе синхронизации при SYN=0 информа- ция фиксируется в RG'T', т. е. он закрыт для записи, а запись (если она разрешена) производится в RGF. Фиксируется информа- реднем фронте сигнала. _ВЗАИМОДЕЙСТВИЕ ОА и УА Для исключения гонок при взаимодействии ОА и УА будем может быть представлена в виде: ╔══════════════════════════╗ ║┌────┐ ┌┬──┬┐ ┌────┐ ║ ╚╡ CS │ ││RG││ │CS ╞<╝ │ ╞<═╦═╡│ │╞<══╡ │ ┌───┤ b │ ║ ││ ││ │ c ├<────┐ │ └────┘ ║ └┴──┴┴A─ └────┘ │ │ ┌────┐ ║ └───────────┐ │ │ │CS ╞<═╝ │ │ │┌──┤ a ├<───────────────────┐ │ │ ││ └────┘ │ │ │ ----││----------------------------│-│-│-- УА ││РА┌────┐ ┌┬──┬┐ ┌─────┐│ │ │┐ │└─>┤ CS│ ││RG││ │ CS ├┘ │ ││ └──>┤ ╞════>╡│ │╞═>╡ ├──┘ ││Y │ │ ││ ││ │ ├────┘│ ╔>╡ p │ ││ ││ │ y ╞═╗ ┘ ║ └────┘ └┴──┴┘ └─────┘ ║ ╚════════════════════════════╝ управления, где РА и РВ - предикатные перемнные. Продолжительность такта работы схемы определяется наибо- лее длинными цепями между регистрами. Для данной схемы, кото- рую будем называть последовательной схемой взаимодействия, зададимся (так чаще всего бывает), что такой критической цепью является цепь (CSy,CSa,CSp,RG). Поэтому длительность > ty + ta + tp + trg, где tj- время установления соответствующего компонента цепи. Чтобы сократить длину этой цепи, применяют другой вари- - 15 - ╔══════════════════════════╗ ║┌────┐ ┌┬──┬┐ ┌────┐ ║ ╚╡ CS │ ││RG││ │CS ╞<╝ │ ╞<═╦═╡│ │╞<══╡ │ ┌───────────┤ b │ ║ ││ ││ │ c ├<────┐ │ FF └────┘ ║ └┴──┴┴A─ └────┘ │ │ ┌┬──┬┐ ┌────┐ ║ └───────────┐ │ │┌─┤│RG│╞<══╡ CS ╞<═╝ │ │ ││ ││ ││ │ a ├<───────────────────┐ │ │ ││ └┴──┴┴A─ └────┘ │ │ │ ││ └──────────────────────────┐ │ │ │ ---││----------------------------------│-│-│-│-- УА ││ MK │ │ │ │ ││ PA ┌────┬────┐ ┌┬──┬┐│ │ │ │┐ │└────>┤ CS│ CS │ ││RG│├┘ │ │ ││ │ РВ │ │ │ ││ │├──┘ │ ││Y └─────>┤ │ ╞═══════════>╡│ │├────┘ ││ │ │ │ ││ │├──────┘│ ╔>╡ p │ y │ ││ │╞═╗ ┘ ║ └────┴────┘ └┴──┴┘ ║ ╚═══════════════════════════════╝ При этом варианте взаимодействия такой длинной цепи, как трами RG'FF' (регистр флажков) и RG'MK' (регистр микрокоман- ее можно определить следующим образом: > max( ta,(tp + ty) )+ trg , сдвигом от сигналов управления. Тогда фрагмент микропрограммы << GO(pA;mi,mj)>>, вейерном варианте за один такт выполнен быть не может и дол- mS{...,pA=f(...)} << GO(pA;mi,mj)>> жительности каждого из тактов. Зато во всех остальных случа- ях (при безусловных переходах, при переходах по значению РВ) Пусть устройство, кроме сигнала синхронизации SYN, имеет боты устройства. При Н=0 - нерабочее состояние - можно выпол- нять начальную установку значений памяти устройства. Измене- (асинхронно), но при этом начальный такт работы устройства "Затягивание" асинхронного сигнала Н в синхронный режим происходит с помощью простейшего синхронного автомата с диаграммой: ┌──────────┐ ┌────────┐ V 0H/CONST│ V 1H/SYN│ █▀▀▀█────────┘ █▀▀▀█──────┘ >▌ 0 ▐──────────────>▌ 1 ▐──────┐ █▄▄▄█ 1H/CONST █▄▄▄█ 0H/X │ │ └────────────────────────────┘ У этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов - 16 - D-триггера. выглядит следующим образом (для синхронизации по фронтам): а)-по переднему фронту, б)- по заднему фронту: ┌──┐ ┌──┐ ──┬──────────┤ 1├── CC SYN ──┬──────────┤ &├── CC │ ┌─┬─┐ ┌─┤ │ │ ┌─┬─┐ ┌─┤ │ └─/C│T│ │ └──┘ └─\C│T│ │ └──┘ │ │ ├ │ │ │ ├──┘ ┌─┤D│ │ │ ┌─┤D│ │ │ ├─┤ o──┘ │ ├─┤ o─ ├─oR│ │ ├─oR│ │ H │ └─┴─┘уст. нач. зн. H │ └─┴─┘уст. нач. зн. ──┴─────────────────── ──┴─────────────────── Такая разница в цепях условной синхронизации, как уже объяс- нялось выше, определяется тем, что первый перепад сигнала СС