|
╨хЇхЁрЄ√ ├ыртэр ╩ЁрЄъюх ёюфхЁцрэшхяЁюшчтхфхэшщ └ЁїшЄхъЄєЁр └ёЄЁюэюьш ┴рэъютёъюх фхыюш ъЁхфшЄютрэшх ┴хчюярёэюёЄ№цшчэхфх Єхы№эюёЄш ┴шюуЁрЇшш ┴шюыюуш ┴шЁцхтюх фхыю ┴єїурыЄхЁш ш рєфшЄ ┬юхээюх фхыю ├хюуЁрЇш ├хюфхчш ├хюыюуш ├Ёрцфрэёър юсюЁюэр ╞штюЄэ√х ╟фюЁют№х ╟хьхы№эюх яЁртю ╚эюёЄЁрээ√х ч√ъшышэутшёЄшър ╚ёъєёёЄтю ╚ёЄюЁшўхёър ышўэюёЄ№ ╚ёЄюЁш ╚ёЄюЁш юЄхўхёЄтхээюуюуюёєфрЁёЄтр ш яЁртр ╚ёЄюЁш яюышЄшўшёъшїєўхэшщ ╚ёЄюЁш Єхїэшъш ╩юья№■ЄхЁэ√х ёхЄш ╩юья№■ЄхЁ√ ▌┬╠ ╩ЁшьшэрышёЄшър шъЁшьшэюыюуш ╩єы№ЄєЁюыюуш ╦шЄхЁрЄєЁр ╦шЄхЁрЄєЁр ч√ъютхфхэшх ╠рЁъхЄшэу ЄютрЁютхфхэшхЁхъырьр ╠рЄхьрЄшър ╠рЄхЁшрыютхфхэшх ╠хфшЎшэр ╠хфшЎшэр чфюЁют№х юЄф√ї ╠хэхфцьхэЄ (ЄхюЁш єяЁртыхэш ш юЁурэшчрЎшш) ╠хЄрыыєЁуш ╠юёътютхфхэшх ╠єч√ър ═рєър ш Єхїэшър ═юЄрЁшрЄ ╬с∙хэшх¤Єшър ёхь№ сЁръ ╧хфруюушър ╧Ёртю ╧ЁюуЁрььшЁютрэшхсрч√ фрээ√ї ╧ЁюуЁрььэюх юсхёяхўхэшх ╧Ёюь√°ыхээюёЄ№ёхы№ёъюх їюч щёЄтю ╧ёшїюыюуш ╨рфшю¤ыхъЄЁюэшъръюья№■ЄхЁ√ ш яхЁшЇшЁшщэ√х єёЄЁющёЄтр ╨хъырьр ╨хышуш ╤хъёюыюуш ╤юЎшюыюуш ╥хюЁш уюёєфрЁёЄтр ш яЁртр ╥хїэюыюуш ╘шчшър ╘шчъєы№ЄєЁр ш ёяюЁЄ ╘шыюёюЇш ╘шэрэёютюх яЁртю ╒шьш - ЁхЇхЁрЄ√ ╒юч щёЄтхээюх яЁртю ╓хээ√щ сєьруш ▌ъюыюушўхёъюх яЁртю ▌ъюыюуш ▌ъюэюьшър ▌ъюэюьшъряЁхфяЁшэшьрЄхы№ёЄтю ▐Ёшфшўхёър яёшїюыюуш |
╠хЄюфшўър фы ъєЁёютюую яЁюхъЄшЁютрэш яю ╧╥╓└ яЁшъырфэр ЄхюЁш ЎшЇЁют√ї ртЄюьрЄютАнтик М.И. 11_03_91 МИРЭА АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА Алгоритмы этого типа являются следующим этапом обобщения описаний ычислительных процессов. Теперь, по сравнению с ал- горитмами автоматного типа, на каждом шаге, помимо модифика- ции памяти, идентифицирующей шаг алгоритма, разрешается изме- нять любую другую память устройства локально (по частям) или глобально (всю сразу). стройство-исполнитель алгоритма этого типа будем назы- ать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации шага алгоритма, остальная па- мять используется для запоминания промежуточных данных, вы- числяемых процессе последовательного, по шагам, ыполнения алгоритма. акая модель вычислителя особенно удобна для рас- чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп- ность заимодействующих синхронных автоматов, один из которых называется управляющим автоматом (УА), а объединение всех ос- тальных автоматов называется операционным автоматом (ОА). УА является исполнителем алгоритма автоматного типа, ко- торый ходит составной частью в любой алгоритм процедурного типа. Кроме того, УА инициирует действия отдельных шагов ал- горитма и участвует в их выполнении. ОА выполняет все ычисления на отдельных шагах алгоритма под управлением УА; кроме того, к ОА удобно отнести все вы- числения предикатных функций, оставив УА только анализ вычис- ленных предикатных значений. Прежде чем переходить к точным терминам, рассмотрим сле- дующиe примеры алгоритмов процедурного типа. Например, каноническое описание синхронного конечного автомата может быть интерпретировано (истолковано) как одно- шаговый алгоритм процедурного типа. █ ┌──────┐ │ ┌──V──V─────┐ B=FO(S,A) │ S:=FS(S,A)│ └─────┬─────┘ └─────────┘ Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, идентифицировать ша- ги этого алгоритма не надо. Например, инкрементор с одноразрядным входом и однораз- рядным ыходом может быть реализацией следующих преобразова- ний: █ █ p:=1 █ █ ┌────────┐ │ ┌─────V─V───────┐ (p:, b) = a+p │ └───────┬───────┘ └──────────┘ ОА, реализующий инкрементор в целом, будет следующим: ┌──┬─┐ a ──────────────────┤HS│S├────b ┌─┬─┐p │ │ │ начальное значен.─┤S│T├──┤ │P├──┐ ├─┤ │ └──┴─┘ │ SYN ─────────/C│ ┌┤D│ │ │ └─┴─┘ │ └───────────────┘ Конечно, эта реализация совпадает с реализацией алгоритма ав- томатного типа, если состояние р1 кодируется 1, а состояние р0 - 0. Этот пример показывает,что до начала вычислений может потребоваться начальная установка памяти. На самом деле это необходимо было уже в алгоритмах автоматного типа, так как код начального состояния требует предварительной установ- ки. Ограничимся здесь обозначением этой проблемы, а решение , связанное прежде всего с корректной синхронизацией ус- тройства первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк- ивалентного автомату Мили , не обсуждалась простая возмож- ность реализации и на структурном уровне. Например, только что рассмотренный автомат Мили может быть преобразован в эк- ивалентный автомат Мура по одному из следующих вариантов: ┌┬─┬┐t┌──┬─┐ ┌──┬─┐ ┌┬─┬┐ a ──┤│T│├┤HS│S├─b a ─────┤HS│S├─┤│T│├─b ─/┴┴─┴┘ │ │ │ ─/┴┴─┴┘ C │ │ │ C C ─/┬┬─┬┐p│ │ │ ─/┬┬─┬┐p│ │ │ ┌┤│T│├┤ │P├┐ ┌┤│T│├┤ │P├┐ │ └┴─┴┘ └──┴─┘│ └┴─┴┘ └──┴─┘│ └─────────────┘ └─────────────┘ При таких структурных преобразованиях проще истолковы- ать алгоритмы как процедурные. █ █ █ p:=1; t:=0 █ █ p:=1 █ █ █ ┌────────┐ │ ┌────────┐ │ │ ┌─────V─V───────┐ ┌─────V─V───────┐ │ │t:=a;(p:,b)=t+p│ (p , b):= a+p │ │ └───────┬───────┘ └───────┬───────┘ └──────────┘ └──────────┘ БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после некоторых дополнений может быть использован и для описания алгоритмов процедурной форме: Блок-текст состоит из трех частей: 1)- Описание переменных и начальных значений памяти. 2)- Описания функций и связей. аписываются любые функции и функциональные связи (в том числе предикатные), не использу- ющие запоминания. Переменные из левой части операции присва- ивания таких функциональных описаний используются в блоках процедуры. 3)- Процедура, состоящая из блоков (микроблоков) операторных и блоков переходов: - операторные - в скобках вида {.....}, - перехода - в скобках ида <<...>>; и те, и другие блоки могут снабжаться метками, стоящими перед блоком. блоках перехода используется оператор GO в одной из двух форм: GO m - безусловный переход, GO (P; m0,m1,m2,...) - условный переход. здесь m0,m1,... - метки блоков, P - предикатное значение,интерпретируемое оператором GO как неотрицательное целое число, являющееся порядковым номе- ром метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма. На следующем более сложном примере демонстрируется пос- ледовательность синтеза операционного устройства. Пример. Вычислитель наибольшего общего делителя (НОД) двух натуральных чисел (8-разрядных). 1) Разработаем интерфейс вычислителя: 8 ┌──┬─────┬──┐ ═══╪═>╡I1│ НОД │ │ 8 8 │ │ │D ╞══╪══> ═══╪═>╡I2│ ├──┤ ├──┤ ─────>┤rI│ rO├─────> ├──┤ │ │ ─────>┤ C│ └──┴─────┴──┘ I1[7..0], I2[7..0] -входные информационные шины. rI -входной сигнал готовности: если rI=1, то на входах I1, I2 готовы операнды. D[7..0] -выходная информационная шина . rO -выходной сигнал готовности: если rO=1, то готов резуль- тат на шине D, который сохраняется до появления новых операн- дов. 2) Математическое обоснование алгоритма вычислений: Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа- тся в том, что НОД двух натуральных чисел А и В в случае ра- нства этих чисел совпадает с любым из них, а случае их неравенства совпадает с НОД двух других чисел: меньшего и разности между большим и меньшим. Последовательно, уменьшая числа, получим два равных числа -значение одного из них и бу- дет НОД исходных чисел. 3) Блок-схема алгоритма (микропрограмма в содержательном иде): █ ┌──────V──────┐ m1│ rO: = 0 │ └──────┬──────┘ ┌──────────────────┐ ┌─────┐ ─VVV─ │ │ / \ 0 │ │ < rI>─────┘ │ \_/ 1 │ ┌──────V──────┐ rO: = 0 │ m2│ А: = I1 │ B: = I2 │ └──────┬──────┘ ┌───────────────────┐│ ┌─────VV──────┐ m3│ (p,S)=A - B │ └──────┬──────┘ ─V─ m6 │ / \ =0 ┌──────────┐│ z <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{xxxx10} g1<<GO(rI;g1,m2)>> m2{111x10} m3{x000x0} <<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)- тип применяемых базовых функций. ОПТИМИЗАЦИЯ АПППАРАТУРЫ ПРИ СОХРАНЕНИИ МИНИМАЛЬНОГО ВРЕМЕНИ Алгоритм функционального типа обладает максимальным по- тенциальным параллелизмом (в рамках данной алгоритмической идеи), и,следовательно, его реализация иде КС обладает максимальным быстродействием по сравнению с любыми другими ычислителями. Невозможность реализации вычислителя в виде КС может быть обусловлена следующими причинами: - слишком велик объем аппаратуры КС; - функциональное представление и го реализация являются статическим отображением входных объектов на выходные: это исключает озможность работы с объектами, которые "ведут се- бя" более сложно во времени; невозможно также реализовать принципиально рекуррентные алгоритмы (см.,например,алгоритм клида для нахождения НОД). Тем не менее, сли формально алгоритм функционального типа может быть записан, то проектирование устройства надо начинать с записи именно такого алгоритма. Минимизация аппаратуры "сложной" КС с переходом на про- цедурный ариант реализации связан с "экономией" числа опера- ционных элементов, т.е. со слиянием некоторых из них в один функциональный модуль, выполняющий эти операции по очереди. акое решение потребует запоминания всех переменных (входных и ыходных),связанных с выполнением этих операций. Требуется также управление памятью, связанной с этим функциональным мо- дулем, а также - может быть - управление самим функциональным модулем, сли он объединил существенно различные функции. Переход к процедурной реализации и, следовательно, к дискретизации ремени неизбежно увеличит время вычисления од- ного результата - даже при реализации структуры подобной КС. При этом, как ни странно, может уменьшиться ремя следующих друг за другом вычислений именно за счет дискретизации време- ни и применения так называемых "конвейерных" вычислений - но об этом речь пойдет в другом курсе. Рассмотрим озможность сокращения аппаратуры без увели- чения ремени решения, достигнутого в алгоритме функциональ- ного типа. Сопоставим схеме устройства, реализующего алгоритм функционального типа, простую модель в иде направленного графа. ршины графа будут соответствовать операциям, а дуги - переменным алгоритма. Назовем такой граф сигнальным (графом потоков данных). Заметим, что сигнальный граф всегда будет ациклическим. Минимальность времени ычислений сохранится, если совме- щать в один функциональный модуль операции, которые располо- жены на одном и том же пути в сигнальном графе, либо на аль- тернативных путях решения. МИНИМИЗАЦИЯ АППАРАТУРЫ Может оказаться, что на одном пути в сигнальном графе расположены операции, плохо или вовсе не совмещаемые друг с другом (т.е. совмещение не дает экономии в аппаратуре функци- онального модуля). Возможно также, что проведенная минимиза- ция, сохраняющая минимальное время, не позволяет выполнить ограничение на объем аппаратуры. В таком случае необходима более глубокая минимизация,охватывающая параллельные ветви сигнального графа. Минимизация должна быть взаимосвязанной по сем компонентам ОА: по памяти, функциональным модулям и ком- мутации. В настоящее время процедуры минимизации не формализованы и сводятся к перебору "правдоподобных" вариантов. Можно предложить следующую последовательность действий: 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├> \__/ └────┘ этом случае, так же, как и в предыдущем, чаще всего не ну- жен промежуточный регистр (В). НИВЕРСАЛЬНЫЙ ОА Использование при проектировании универсальных ОА с за- ранее фиксированной и минимизированной структурой оправдано тем, что такие универсальные ОА изготавливаются промышлен- ностью иде БИС большим тиражом и поэтому они сравнительно дешевы. акие универсальные ОА входят в микропроцессорные на- боры 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 │ └─┴─┘уст. нач. зн. ──┴─────────────────── ──┴─────────────────── акая разница в цепях условной синхронизации, как уже объяс- нялось ыше, определяется тем, что первый перепад сигнала СС не должен быть рабочим. ╦╚╥┼╨└╥╙╨└ 0. ╦■с√х ышЄхЁрЄєЁэ√х шёЄюўэшъш, Ёхъюьхэфютрээ√х яю фшёнЎшяышэх "╬ёэют√ фшёъЁхЄэющ ьрЄхьрЄшъш". 1. ╥юъїхщь ╨. ╬ёэют√ ЎшЇЁютющ ¤ыхъЄЁюэшъш.-╠.: ╠шЁ,'88 2. ╩рурэ ┴.╠. ▌ыхъЄЁюээ√х т√ўшёышЄхы№э√х ьр°шэ√ ш ёшёЄхнь√.-╠.: ▌эхЁуюрЄюьшчфрЄ, 1991 - 340 ё. 3. ╓шЇЁютр ш т√ўшёышЄхы№эр Єхїэшър /яюф Ёхф. ▌.┬.┼тЁхншэютр.-╠.: ╨ш╤,1991.-464ё. 4. ╠рщюЁют ╤.└., ═ютшъют ├.╚. ╤ЄЁєъЄєЁр ¤ыхъЄЁюээ√ї т√нўшёышЄхы№э√ї ьр°шэ.-╦.: ╠р°шэюёЄЁюхэшх, 1979 - 384 ё. 5. ╤рьюЇрыют ╩.├., ╨юьрэъхтшў └.╠., ┬рыєщёъшщ └.╠.а ╧Ёшънырфэр ЄхюЁш ЎшЇЁют√ї ртЄюьрЄют.-╩.: ┬ш∙р °ъ. 1987 - 470 ё. 6. ╤ртхы№хт └.▀. ╧Ёшъырфэр ЄхюЁш ЎшЇЁют√ї ртЄюьрЄют. -╠.: ┬√ё°р °ъюыр, '87 7. ╨рсшэютшў ╟.╦. ╬ёэют√ ЄхюЁшш ¤ыхьхэЄрЁэ√ї ёЄЁєъЄєЁ ▌┬╠. -╠.: ╨ш╤, '82 - 280 ё. 8. ╨рсшэютшў ╟.╦., ╨рьрэрєёърё ┬.└. ╥шяют√х юяхЁрЎшш т т√ўшёышЄхы№э√ї ьр°шэрї. ╩шхт: ╥хїэшър, '80 - 264 ё. 9. ╩рЁЎхт ╠.└. └ЁшЇьхЄшър ЎшЇЁют√ї ьр°шэ. -╠.: ═рєър,'69 - 575 ё. 10. ╩рЁЎхт ╠.└., ┴Ёшъ ┬.└. ┬√ўшёышЄхы№э√х ёшёЄхь√ ш ёшэнїЁюээр рЁшЇьхЄшър. -╠.: ╨ш╤, '81 - 360 ё. 11. ┴рщъют ┬.─., ╤ьюыют ┬.┴. ╤яхЎшрышчшЁютрээ√х яЁюЎхёнёюЁ√: шЄхЁрЎшюээ√х рыуюЁшЄь√ ш ёЄЁєъЄєЁ√. ╠.:╨ш╤,1985 - 288ё. 12. ┴рЁрэют ╤.╚. ш фЁ. ╓шЇЁют√х єёЄЁющёЄтр эр яЁюуЁрььшнЁєхь√ї ┴╚╤ ё ьрЄЁшўэющ ёЄЁєъЄєЁющ.-╠.:╨ш╤,1986-272 ё. 13. ┴рЁрэют ╤.╚. ╤шэЄхч ьшъЁюяЁюуЁрььэ√ї ртЄюьрЄют.а -╦.: ▌эхЁуш , 1979 - 232 ё. 14. ┴рЁрэют ╤.╚., ╤ъы Ёют ┬.└. ╓шЇЁют√х єёЄЁющёЄтр эр яЁюуЁрьььшЁєхь√ї ┴╚╤ ё ьрЄЁшўэющ ёЄЁєъЄєЁющ. -╠.: ╨ш╤ '86 - 272 ё. 15. ╩ышэуьрэ ▌.а ╧ЁюхъЄшЁютрэшх ёяхЎшрышчшЁютрээ√ї ьшъЁюняЁюЎхёёёюЁэ√ї ёшёЄхь.-╠.: ╠шЁ, 1985.- 363 ё. 16. ╧ЁюхъЄшЁютрэшх ЎшЇЁют√ї ёшёЄхь эр ъюьяыхъЄрї ьшъЁюняЁюуЁрььшЁєхь√ї ┴╚╤ /╧юф Ёхф. ┬.├.╩юыхёэшъютр.-╠.: ╨рфшю ш ёт ч№, 1984.- 240 ё. 17. ╠шъ ─ц., ┴Ёшъ ─ц. ╧ЁюхъЄшЁютрэшх ьшъЁюяЁюЎхёёюЁэ√ї єёЄЁющёЄт ё ЁрчЁ фэю-ьюфєы№эющ юЁурэшчрЎшхщ. ╥.1.-╠.: ╠шЁ, 1984.- 253 ё. 18. ╧юЄхьъшэ ╚.╤. ╘єэъЎшюэры№э√х єчы√ ЎшЇЁютющ ртЄюьрЄшнъш. -╠.: ▌эхЁуюрЄюьшчф.,'88 - 320 ё. 19. ╙уЁ■ьют ┼.╧. ╧ЁюхъЄшЁютрэшх ¤ыхьхэЄют ш єчыют ▌┬╠. -╠.:┬╪,1987.-318 ё. 20. ┴єъЁххт ╚.═.,├юЁ ўхт ┬.═.,╠рэёєЁют ┴.╠. ╠шъЁю¤ыхънЄЁюээ√х ёїхь√ ЎшЇЁют√ї єёЄЁющёЄт.-╠.:╨ш╤,1990-416ё. 21. ╧єїры№ёъшщ ├.╚.,═ютюёхы№Ўхтр ╥.▀. ╧ЁюхъЄшЁютрэшх фшёъЁхЄэ√ї єёЄЁющёЄт эр шэЄхуЁры№э√ї ьшъЁюёїхьрї:╤яЁртюўэшъ. -╠.:╨ш╤,1990-304ё. 22. ╪шыю ┬.╦.а ╧юяєы Ёэ√х ЎшЇЁют√х ьшъЁюёїхь√:╤яЁртюўэшъ. -╠:╨ш╤,1987-352ё. 23. ╧Ёшьхэхэшх шэЄхуЁры№э√ї ьшъЁюёїхь т ¤ыхъЄЁюээющ т√нўшёышЄхы№эющ Єхїэшъх:╤яЁртюўэшъ/яюф Ёхф. ┴.═.╘рщчєырхтр, ┴.┬.╥рЁрсЁшэр. -╠:╨ш╤,1986-384ё. 24. ╟ръЁхтёъшщ └.─. ╦юушўхёъшщ ёшэЄхч ърёърфэ√ї ёїхь. -╠.: ═рєър, 1981 - 414 ё. 25. ╘Ёшфьрэ └.,╠хэюэ ╧. ╥хюЁш ш яЁюхъЄшЁютрэшх яхЁхъы■нўрЄхы№э√ї ёїхь. -╠:╠шЁ,1978-580ё. 26. ├шыы └. ┬тхфхэшх т ЄхюЁш■ ъюэхўэ√ї ртЄюьрЄют. -╠.: ═рєър '66 - 272 c. 27. ├шыы └. ╦шэхщэ√х яюёыхфютрЄхы№эюёЄэ√х ьр°шэ√. -╠.: ═рєър '74 - 288 ё. 28. ╩єфЁ тЎхт ┬.┴., └ых°шэ ╤.┬., ╧юфъюычшэ └.╤. ┬тхфхэшх т ЄхюЁш■ ртЄюьрЄют.-╠.: ═рєър '85 - 320 ё. 29. ╠рЁъют └.▀. ┬тхфхэшх т ЄхюЁш■ ъюфшЁютрэш .-╠.: ═рєър '82 - 192 ё. 30. └эухЁ ╤. └ёшэїЁюээ√х яюёыхфютрЄхы№эюёЄэ√х ёїхь√. -╠:═рєър,1977-400ё. 31. └яхЁшюфшўхёъшх ртЄюьрЄ√ /яюф Ёхф. ┬рЁ°ртёъюую ┬.╚. -╠:═рєър,1976,-423ё. 32. └тЄюьрЄэюх єяЁртыхэшх рёшэїЁюээ√ьш яЁюЎхёёрьш т ▌┬╠ ш фшёъЁхЄэ√ї ёшёЄхьрї /яюф Ёхф. ┬рЁ°ртёъюую ┬.╚. -╠:═рнєър,1986,-400ё. _ └эЄшъ ╠.╚.ааааааааааааааааааааааааааааааааааа 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--++----------------------------------+ж ёшэїЁюэшчрЎш ╬└ аа +---------------------------------------+ аааа ▌Єр ёїхьр шёяюы№чєхЄё а Єюы№ъюа та ъюэтхщхЁэюьа трЁшрэЄх тчршьюфхщёЄтш . ╠хЄюф т√ўшёыхэш рфЁхёр фы ёыхфє■∙хуюа ЄръЄр Єръющ цх, ъръ ш т ёїхьх ё Ёхуєы Ёэющ рфЁхёрЎшхщ. (─Ёєующ ЄхЁ- ьшэ -"хёЄхёЄтхээ√щ" - єяюЄЁхсыхэ Єюы№ъю Ёрфш Ёрчышўхэш ёрьшї ёїхь.) ═ю т ¤Єющ ёїхьх, яю ёЁртэхэш■а ёа єцха ЁрёёьюЄЁхээ√ьш, ЁрчЁ ф єяЁрты ■∙хщ ярь Єш ё юфэшь ш Єхь цх эюьхЁюь (ЁрчЁ фэ√щ ёЁхч) т Ёрчышўэ√їа ьшъЁюшэёЄЁєъЎш їа ьюцхЄа с√Є№а шёяюы№чютрэ Ёрчышўэ√ь юсЁрчюь. ┴єфхь ЁрчышўрЄ№ ьшъЁюшэёЄЁєъЎшша фтєїа Єш- яют: а- юяхЁрЎшюээ√х, а- рыЁхёрЎшш (т√сюЁр). аааа ┬ ыфрээюь трЁшрэЄх ёїхь√ Єшя ьшъЁюшэёЄЁєъЎшша єёЄрэртыш- трхЄё ЁрчЁ фюь ё шьхэхьа "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 +---+ аааа ╧хЁхїюф ъ ьшъЁюяюфяЁюуЁрььх ё тючтЁрЄюь аааа ╧Ёш ЁхрышчрЎшш фюёЄрЄюўэю ёыюцэ√ї т√ўшёыхэшщ єфюсэю тюё- яюы№чютрЄ№ё ьхїрэшчьюь ьшъЁюяюфяЁюуЁрьь. аааа ╬фэр ш Єр цх ьшъЁюяюфяЁюуЁрььра ьюцхЄа с√Є№а т√чтрэра шч Ёрчэ√ї Єюўхъ т√ч√тр■∙шїа ьшъЁюяЁюуЁрьь.а ╧ю¤Єюьєа яЁша т√чютх ьшъЁюяюфяЁюуЁрьь√ эхюсїюфшью чряюьэшЄ№ рфЁхё,а ёа Єхь,а ўЄюс√ тюёёЄрэютшЄ№ хую яЁш тючтЁр∙хэшш шч ьшъЁюяюфяЁюуЁрьь√.а ╫Єюс√ чряюьэшЄ№ ш тюёёЄрэютшЄ№ рфЁхёр тючтЁрЄр юЄа тыюцхээ√їа т√чю- тют, шёяюы№чєхЄё схчрфЁхёэр ярь Є№ - ёЄхъ (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 2Антик М.И. 11_03_91 МИРЭА _АЛГОРИТМЫ ПРОЦЕДУРНОГО ТИПА. ОПЕРАЦИОННЫЕ УСТРОЙСТВА Алгоритмы этого типа являются следующим этапом обобщения описаний ычислительных процессов. Теперь, по сравнению с ал- горитмами автоматного типа, на каждом шаге, помимо модифика- ции памяти, идентифицирующей шаг алгоритма, разрешается изме- нять любую другую память устройства локально (по частям) или глобально (всю сразу). стройство-исполнитель алгоритма этого типа будем назы- ать операционным устройством (ОУ). ОУ можно рассматривать как один синхронный автомат со сложно структурированной памятью - состоянием: часть памяти используется для идентификации шага алгоритма, остальная па- мять используется для запоминания промежуточных данных, вы- числяемых процессе последовательного, по шагам, ыполнения алгоритма. акая модель вычислителя особенно удобна для рас- чета продолжительности одного такта работы устройства. Другой удобной моделью вычислителя является совокуп- ность заимодействующих синхронных автоматов, один из которых называется управляющим автоматом (УА), а объединение всех ос- тальных автоматов называется операционным автоматом (ОА). УА является исполнителем алгоритма автоматного типа, ко- торый ходит составной частью в любой алгоритм процедурного типа. Кроме того, УА инициирует действия отдельных шагов ал- горитма и участвует в их выполнении. ОА выполняет все ычисления на отдельных шагах алгоритма под управлением УА; кроме того, к ОА удобно отнести все вы- числения предикатных функций, оставив УА только анализ вычис- ленных предикатных значений. Прежде чем переходить к точным терминам, рассмотрим сле- дующи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 <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>> - 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<<GO(rI;g1,m2)>> m2{111x10} m3{x000x0} <<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 ) - выходами. Микрооперация ( : ) - двоеточие - означает запоминание (изменение значения) в памяти устройства. Переменная типа па- мять сохраняет свое значение между двумя очередными присва- иваниями. - 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 <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С, управляющий доступом синхросиг- налов в ОА. Такой вариант управления, называемый условной синхронизацией, позволяет запретить любые изменения памяти ОА каком-либо такте. Причем, если рабочим является срез (зад- ний фронт) сигнала синхронизации, то используется элемент И, как и показано на рисунке.Если же рабочим является фронт (пе- редний фронт) сигнала, то используется элемент . (Первый перепад сигнала синхронизации в новом такте не должен быть рабочим.) _ОПТИМИЗАЦИЯ ОПЕРАЦИОННОГО АВТОМАТА При проектировании ычислительного устройства основными являются ограничения на: 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─ └┴──┴─┘ ├─ │ └────┘ <K / \ =K J═════════>╡А │ └──────<J==K>─────> └────┘ \__/ (реализация счетчика 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─ <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 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│╞<══╡ 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 │ л └────────────────────────────┘ этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов - 16 - D-триггера. Схема автомата вместе с цепями условной синхронизации ыглядит следующим образом (для синхронизации по фронтам): а)-по переднему фронту, б)- по заднему фронту: ┌──┐ ┌──┐ SYN ──┬──────────┤ 1├── CC SYN ──┬──────────┤ &├── CC │ ┌─┬─┐ ┌─┤ │ ┌─┬─┐ ┌─┤ │ └─/C│T│ │ └──┘ └─\C│T│ │ └──┘ │ │ ├ │ ├──┘ ┌─┤D│ │ │ ┌─┤D│ │ │ ├─┤ o──┘ ├─┤ o─ ├─oR│ │ ├─oR│ │ H │ └─┴─┘уст. нач. зн. H │ └─┴─┘уст. нач. зн. ──┴─────────────────── ──┴─────────────────── акая разница в цепях условной синхронизации, как уже объяс- нялось ыше, определяется тем, что первый перепад сигнала СС не должен быть рабочим. 2Антик М.И. 11_03_91 МИРЭА _УПРАВЛЯЮЩИЕ АВТОМАТЫ. _ОСНОВНЫЕ СПОСОБЫ АДРЕСАЦИИ МИКРОКОМАНД Начнем с рассмотрения простейшего варианта управления, в котором не участвуют предикатные функции (переменные), т.е. в микропрограмме переходы только безусловные. В таком случае УА является автономным синхронным автоматом. В более общем случае функция переходов УА зависит от предикатных переменных, но УА должен быть автоматом Мура. Условимся о некоторых ограничениях, позволяющих упрос- тить схему на начальных этапах проектирования (от которых легко последствии и отказаться): - на каждом шаге процесса ычислений ветвление может осу- ществляться только по одной двузначной предикатной перемен- ной (т.е. разветвление возможно лишь на два направления); - начальные значения всех регистров УА являются нулевыми. предь на схемах УА не будем показывать цепей установки на- чальных значений. Для реализации в самом общем случае микропрограмм произ- ольной структуры будем строить УА так, чтобы основным мате- риальным носителем управляющей (автоматной) компоненты мик- ропрограммы являлась бы управляющая память (реализованная, например, иде ПЗУ). В этом случае структура слова управля- ющей памяти - МИКРОИНСТРУКЦИЯ - состоит из двух составных частей: микрокоманды и адресной части. Адресная часть микроинструкции содержит информацию, поз- оляющую следующем такте работы выбрать ( указать ) новый адрес управляющей памяти. Реализация именно этого момента яв- ляется основным предметом дальнейшего рассмотрения и опреде- ляет, в основном, структуру, объем аппаратуры и быстродей- ствие А. При этом подлежит рассмотрению реализация следующих типов переходов как между шагами алгоритма, так, соот- тственно, и между микроинструкциями: - безусловный переход, - условный переход, - функциональный переход, - переход к микроподпрограмме с озвратом. Будем изучать работу управляющих автоматов различной структуры, демонстрирующие основные применяемые варианты ад- ресации микроинструкций, на следующем алгоритме: - 2 - ███ ┌───┐│ │ ┌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творяет выше- указанному ограничению. Поэтому потребуются эквивалентные преобразования алгоритма для того, чтобы удовлетворить этому ограничению. Алогоритмы эквмвалентны, если они преобразуют информа- цию одинаковым образом. Наиболее распространенным приемом эк- ивалентного преобразования алгоритмов и микропрограмм явля- тся ключение микроблоков и, соответственно, тактов, в кото- рых не ыполняется модификация памяти ОА - "нет операции". Но и это преобразование может быть не эквивалентным - см.при- мер при определении понятия "микроблок"; кроме того, следует учесть различное поведение во времени предикатных переменных типа "РА" и "РВ" - см. раздел "Взаимодействие ОА и А". ( Запретить модификацию памяти можно, вводя условную синхронизацию ОА, но для этого должна быть изменена микроко- манда, предшествующая добавляемому такту.) - 3 - _СХЕМА С АДРЕСНЫМ ПЗУ Начнем рассмотрение с управляющего автомата, структура которого совпадает с канонической структурой автомата Мура. ┌───┐ ┌───┐ ┌┬──┬┐ ┌───┐ 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 можно расположить микрокоманду, после кото- рой безусловно выполняется начальная микрокоманда. - 4 - ┌───┐ 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 } - 5 - <<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 Распределять микроинструкции по ячейкам памяти удобно следующем порядке: - 6 - - связать с различными операторами условного перехода, кон- фликтующими между собой по адресации, различающиеся между со- бой старшие разряды адреса; - распределить микроблоки по ячейкам памяти с учетом назнач- нных старших разрядов адреса и входных значений; - оставшимся нераспределенным микроблокам назначить произ- ольные свободные адреса. _СХЕМА С СОКРАЩЕННЫМ ТАКТОМ Использование этой схемы позволяет при сохранении пре- имуществ последовательного варианта взаимодействия сократить наиболее длинные цепи, общие для ОА и УА, до длины цепей кон- йерного арианта. ┌──────────────────────────────────┐ ──┬──────────┬ ╔══════════════════════════╗│ 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║│ ║ ╚═════════════════╝│ ║ └───────────────────────┘ ╚═════════════════════════════╝ В этой схеме при разветвлении процесса ычислений пара альтернативных адресов получается следующим образом: один ад- рес сегда на единицу больше, чем текущий ( т.е. изменяется "регулярным" образом ), второй адрес - произвольный и содер- жится месте с микрокомандой в микроинструкции. Элементом, "вычисляющим" адрес, является счетчмк, управ- ляемый сигналом, являющимся входным для УА. При различных значениях ходного сигнала счетчик выполняет две функции: ли- бо прибавляет единицу к значению, которое хранилось в счетчи- ке и являлось текущим адресом, либо загружается значением ад- реса из управляющей памяти. - 7 - В схему введен элемент М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──┘└─────────────────────────────┘ ║ ╚═══════════════════════════════════╝ - 8 - _СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И _СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ ╔════════════════════════════╗ C ╔═══════════════════╗ ║ ─/┬┬──┬┐H' ┌┬──┬┐ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗ ┌───┐ RG││ │MUX│║ │ROM│ ║ ║ ┌>┤│ ├─┐║ ╚>╡INC╞>╡│ │╞>╡0 │║ │ S║H║e│ └┴──┴┘ │║ └───┘C││ ││ │ │║ ┌┬──┬┐Y│║ для RG"Y" ─/┴┴──┴┘ │ ╞╩>╡ ▐██████>╡│RG│╞>│║ ─/┬┬──┬┐ │ │A │ │ w c││ ││ │║ 0w-загрузка C││RG││ │ │ │ │ ─A─/┴┴──┴┘ │║ ╚═══════>╡│ │╞>╡1 │ │ │k │ ┌┬─┬┐k'│║ 1w-нет загрузки А │ │ ├────┴─>┤│T│├┐ │║ ┌───┐ └┴──┴┘ └─A─┘ └───┘ ─/┴┴─┴┘│ │║ k ┌───┐ │MUX│ ┌──┐ ┌─┐│ C │ └────┤ 1 ├─ CC 0>┤0 ├─>┤M2├─>┤&├┘ ┌────┤ │ a>┤1 │┌>┤ │┌>┤ │ SYN └───┘ b>┤2 ││ └──┘│ └─┘ А ││e' └──────────────────────────┘ │║ где CC - └A──┘└──────────────────────────────────┘║ синхронизация ОА ╚═══════════════════════════════════════╝ Эта схема используется только в конвейерном варианте заимодействия. Метод вычисления адреса для следующего такта такой же, как и в схеме с регулярной адресацией. (Другой тер- мин -"естественный" - употреблен только ради различения самих схем.) Но в этой схеме, по сравнению с уже рассмотренными, разряд управляющей памяти с одним и тем же номером (разрядный срез) в различных микроинструкциях может быть использован различным образом. Будем различать микроинструкции двух ти- пов: - операционные, - алресации (выбора). В лданном варианте схемы тип микроинструкции устанавли- ается разрядом с именем "k". При k=0 выполняется микро- инструкция операционного типа. Все остальные разряды ячейки загружаются регистр микрокоманды и управляют выполнением микроопераций ОА. Следующий адрес всегда на единицу больше. При k=1 выполняется микроинструкция адресации. Все разряды микроинструкции могут быть использованы для вычисле- ния следующего адреса. В данном варианте схемы, так же как и схеме с регулярной адресацией, один из адресов явно записы- ается микроинструкцию, другой альтернативный адрес на еди- ницу больше текущего. Адрес A ▌k│ Y │ n1 { m1 } -- 0 ▌ │ H│ e│ S│ ──▌─┼──┴──┴──┤ n2 { m2 } -- 1 0 ▌0│ m1 │ 1 ▌0│ m2 │ g1 <<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│ Вместе с этой схемой обычно используется условная син- хронизация, которая позволяет удлинить такт выполнения микро- - 9 - команды ОА на время выполнения микроинструкций адресации. SYN ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──── └─┘ └─┘ └─┘ └─┘ └─┘ | | | | | k 0 ▄▄▄▄▄▄▄▄ 0 ▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄─────▄▄▄▄▄▄▄▄ 0 ▄▄▄ ──────▀▀▀▀▀▀▀▀─────▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀ 1 ▀▀▀▀▀▀▀▀─────▀▀▀ | | | | | CC┐ ┌──────────┐ ┌────────────────────────────────────┐ ┌──── └─┘ └─┘ └─┘ | | | | | Y────▄────────────▄──────────────────────────────────────▄─── ─────▀────────────▀──────────────────────────────────────▀─── _ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД. _ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ Функциональный переход При необходимости ыполнения нескольких ычислительныых функций, управление которыми представляется в виде независи- мых микропрограмм, необходимо организовать независимый вызов этих микропрограмм. Начальные адреса микропрограмм, управляющих вычислениями различных функций, обычно существуют вне управляющей памяти. А достаточно предусмотреть механизм коммутации, позволя- ющий сделать начальный адрес текущим. Это можно осуществить в любой из рассмотренных схем. (К механизму коммутации относят- ся, кроме аппаратуры, специальные разряды управляющей памяти и специальные микроинструкции.) - 10 - ╔══════════════════════╗ C ╔══════║══════════════╗ ║ ─/ ┬┬──┬┐H' ║ ║ ┌───┐║ ┌───┐ ║ ╔══>╡│RG│╞══╗ ║ ║ │MUX│║ │ROM│ ║ ║ ┌>┤│ │├─┐║ F ═║══════║════════>╡0 │║ │ │ ║ ║ │ └┴──┴┘ │║ ║ ║ ┌┬──┬┐ │ │║ │ │ ║ ║ │ │║ ║ ║ ││RG││ │ │║ │ │ ║ ║ │ │║ ║ ╚>╡│ │╞═>╡1 │║ │ │S║H║e│ │║ ║ C││ ││ │ │║ │ │ ║ ║ │ ┌┬──┬┐Y│║ для RG"Y" ║ ─/┴┴──┴┘ │ ╞╩>╡ ▐██████>╡│RG│╞>│║ ║ ┌┬──┬┐ │ │A │ 0w-загрузка ║ ┌───┐ ││RG││ │ │ │ │ w c││ ││ │║ ╚>╡INC╞═>╡│ │╞╦>╡2 │ │ │ ─A─/┴┴──┴┘ │║ 1w-нет загр. └───┘ C││ ││║ │ │ │ │ │ │║ ─/┴┴──┴┘║ ╔══════════╝ │ │ │ │ ┌┬─────┬┐ │ │ │ │ ┌┘k │║ ╚>╡│STACK│╞═>╡3 K │ ┌┬──┬┐K' │║ └┴────A┴┘ │ │ │ ╞═══╧>╡│RG│╞╗ │║ А │ │ │ ││ └─A─┘ └───┘ ─/┴┴──┴┘║ ┌───┐ ║ ║ C MUX│ ┌──┐ ┌╨──────╨┐ 0>┤0 ├─>┤M2├>┤ CS ╞<══════════════════╝ │║ a>┤1 │┌>┤ │ │ │ b>┤2 ││ └──┘ └────────┘ k ┌───┐ │А ││e' └─┤ 1 ├─CC └A──┘└──────────────────────────────────────┘║ ──┤ │ ╚═══════════════════════════════════════════╝ SYN └───┘ Переход к микроподпрограмме с возвратом При реализации достаточно сложных вычислений удобно вос- пользоваться механизмом микроподпрограмм. Одна и та же микроподпрограмма может быть вызвана из разных точек вызывающих микропрограмм. Поэтому при вызове микроподпрограммы необходимо запомнить адрес, с тем, чтобы осстановить го при возвращении из микроподпрограммы. тобы запомнить и восстановить адреса возврата от ложенных вызо- ов, используется безадресная память - стек (stack). Принцип (дисциплина) работы стека описывается условием "последний ошел - первым вышел" (Last In - First Out, LIFO). чтобы описать этот принцип будем считать, что слова, хранящи- ся в стеке, перенумерованы с помощью первых натуральных чи- сел 1,2,...,N. Слово с наибольшим номером называют вершиной стека. Стек может выполнять следующие действия: -"чтение" слова с наибольшим номером, -"выталкивание" (стирание) из памяти слова с наибольшим но- мером, -"запись" нового слова с присваиванием ему наибольшего номе- ра. При вызове микроподпрограммы выполняется операция "запи- си" адреса возврата в стек. При возвращении из микроподпрог- раммы ыполняется операция "чтения" адреса возврата, затем - "выталкивания" го же из стека. Операция "чтения" без "выталкивания" выполняется при ис- - 11 - пользовании стека для организации циклов. Разряды с именем "К" определяют тип выполняемой микро- инструкции. связи с тем, что теперь в схеме существует 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 |
|