Информация о готовой работе

Бесплатная студенческая работ № 3846

2Антик М.И. 11_03_91 МИРЭА

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

- 2 -

--- ----мж ж -VV-м n1ж жm1 ж n1 { m1 } ж L-T-- ж --V-м n2 { m2 } n2ж жm2 ж ж L-T-- g1 <<GO(a;g1,n3)>> ж ж<--м ж -Vм 0ж n3 { m3 } g1ж < a >-- ж LT- n4 { m4 } ж 1ж<----м ж ж----мж g2 <<GO((a,b);n5,n3,n1,n1)>> ж --VVм жж n3ж жm3 ж жж n5 { m5 } ж L-T-- жж ж --V-м жж g3 <<GO(a;n5,n3)>> n4ж жm4 ж жж ж L-T-- жж ж10 -Vм 01жж g2L--< ab>---ж 11 LT- ж 00ж----мж --VVм жж n5 жm5 ж жж L-T-- жж -Vм 0 жж g3 < a >---ж LT- 1 ж L

Укажем на некоторые особенности этого алгоритма: Опера- тор перехода (предикатная вершина), помеченный меткой g1, называют ждущим. Оператор, помеченный меткой g2, использует для перехода 4-значный предикат, что не удовлeтворяет выше- указанному ограничению. Поэтому потребуются эквивалентные преобразования алгоритма для того, чтобы удовлетворить этому ограничению. Алогоритмы эквмвалентны, если они преобразуют информа- цию одинаковым образом. Наиболее распространенным приемом эк- вивалентного преобразования алгоритмов и микропрограмм явля- ется включение микроблоков и, соответственно, тактов, в кото- рых не выполняется модификация памяти ОА - "нет операции". Но и это преобразование может быть не эквивалентным - см.при- мер при определении понятия "микроблок"; кроме того, следует учесть различное поведение во времени предикатных переменных типа "РА" и "РВ" - см. раздел "Взаимодействие ОА и УА". ( Запретить модификацию памяти можно, вводя условную синхронизацию ОА, но для этого должна быть изменена микроко- манда, предшествующая добавляемому такту.)

- 3 -

_СХЕМА С АДРЕСНЫМ ПЗУ Начнем рассмотрение с управляющего автомата, структура которого совпадает с канонической структурой автомата Мура. ----м ----м -T--Tм ----м жMUXж q жROMж жжRGжж жROMж a->+0 +-->+ ж S' жж жж S ж ж Y b->+1 ж ж ж===>жж жж=T>ж ж==> ж ж г>ж ж жж жж ж ж +-м жА ж ж ж 2 ж Cжж жж ж ж 1 ж ж LA--- ж L---- -/++--+- ж L---- ж ж H L

Функцию перехода и функцию выхода реализуем в виде ПЗУ. В литературе, рассматривающей микропрограммные устройства уп- равления, УА с такой структурой называют микропрограммным ав- томатом Уилкса. В ПЗУ (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 ----м ----м -T--Tм жMUX+

a->+0 ж C ж ж S ж ж==>жж жж==> b->+1 ж -/TT--Tм ж ж=T>ж жH жж жж ж ж г>жжRGжж=>ж ж ж ж +-->+ж ж+м жА ж ж жж жжS'ж 2 ж ж ж 1 ж Cжж жжж LA--- ж L+--+- L---- ж L---- -/++--+-ж жH' L

_СХЕМА С ЯВНЫМ УКАЗАНИЕМ АЛЬТЕРНАТИВНЫХ АДРЕСОВ

жг

жж ----м -T--Tм ----мA0жж жж жMUXж жжRGжж жROMж==-ж жL>ж0 ж жж жжA ж жA1 ж ----мL=>ж1 ж===>жж жж=>ж ж===- жMUXж ж ж жж жж ж ж==>Y a->+0 ж жА ж Cжж жж ж +м b->+1 ж LA--- -/++--+- L----жH жА +

LA--- ж L

Конвейерный вариант

жг

жж ----м

жж жMUXж жROM ж==>жжRGжж===-ж жж ж ж ж жA1 жж жжA1' ж жL>ж0 жA ж ж==>жж жж====- ----мL=>ж1 ж=>ж ж Y жж жж Y' жMUXж ж ж ж ж==>жж жж==> ж ж ж ж ж ж H жж жж a->+0 ж жА ж ж +-->+ж ж+мH' b->+1 ж LA--- L

жА +

LA--- ж L

Эта схема отличается от предыдущей тем, что, по сущес- тву, тот же способ адресации выполнен с использованием только одного ПЗУ. В этом варианте альтернативные адреса записывают- ся в той же микроинструкции, что и микрокоманда.

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)>>

_СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ АДРЕСА

Последовательный вариант Конвейерный вариант

ж ----м -T--Tм ----мжe ж ----м ----м e -T--Tмж ж жMUXж q жжRGжжq'жROM+- ж жMUXж q'жROM+---->+жRGж+- L>+0 +---->+ж ж+->+ ж Y L>+0 +-->+ ж Y жж жжY' a->+1 ж S жж жжS'ж ж==> a->+1 ж S'ж ж====>жж жж=> b->+2 ж г==>жж жж=>ж ж==м b->+2 ж г>ж ж H жж жж жА ж ж Cжж жж ж жм ж ж ж ж ж +---->+ж жж=м LA--- ж -/++--+- L----ж ж ж ж ж ж ж S жж жж ж ж H L

ж H' ж C жж ж L

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

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 ж=+A жж 0 жm1 0 4 0ж ж ж ж +-+e жж 1 жm0 1 1 xж ж ж>ж ж=+Y ----м -T--Tмжж 2 жm0 2 3 xж ж ж ж ж=+H жMUXж жжRGжж-ж 3 жm5 1 3 xж ж ж ж 0 ж L==>ж0 ж жж ж+--e' 4 жm2 1 1 xж ж A'ж +----+ ж ж жж жж --+

ж ж жROM ж=+A ж ж==>жж жж==>Y' --T

ж ----мж ж ж ж==>ж1 ж жж жж ROM_1 A'ж Y H A eж ж жMUXжL>ж +-+e жА ж Cжж жжмH' --+

L>+0 ж ж ж=+Y LA--- -/++--+-ж 0 жm4 1 2 xж a>+1 ж ж 1 ж=+H ж ж 1 жm3 0 0 1ж b>+2 ж L

жА +

LA--- ж --+

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

_СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ

----м ---м 0W- +1 жMUX+->+M2+--м 1W- загрузка 0->+0 ж->+ ж -VTT--Tм ----м Y a->+1 жж L--- WжжCTжж жROMж==> b->+2 жж жж жж ж жH ж жж жж жжA ж ж====м жА жж г==>жж жж=>ж жe ж LA---ж ж жж жж ж +--м ж ж ж ж Cжж жж ж ж=мж ж ж ж ж -/++--+- L----Sжж ж ж ж L

ж L

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

В схеме для конвейерного варианта взаимодействия регу- лярное изменение адреса приходится организовывать так, чтобы не увеличивать число мест конвейера.

жг

жж -T--Tм ----мж ----мSж жж ----м жжRGжж жMUXжж жROMж=- жL=>жINCж=>жж жж>ж0 жж ж жY -T--TмY' ж L---- Cжж жж ж жж ж ж==>жжRGжж==> ж -/++--+- ж жж>ж ж жж жж ж -/TT--Tм ж жA ж жH жж жжH' ж CжжRGжж ж ж ж ж==>жж жж==м L

жж жж жА ж ж +-->+ж ж+м ж ----м L+--+- LA--- L---- -/++--+-ж ж жMUXж ---м ж C ж ж 0->+0 +->+M2+

a->+1 ж->+ ж ж ж b->+2 жж L--- ж ж жА жж ж ж LA---L

- 8 -

_СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И _СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ

жг

жж -T--Tм ----мж ----м ж г==>жжRGжж==м жж ----м жжRGжж жMUXжж жROMж ж ж ->+ж ж+-мж жL>жINCж>жж жж>ж0 жж ж жSжHжeж L+--+- жж ж L----Cжж жж ж жж ж ж ж ж ж -T--TмYжж для RG"Y" ж -/++--+- ж жж>ж ж

ж -/TT--Tм ж жA ж ж w cжж жж жж 0w-загрузка ж CжжRGжж ж ж ж ж -A-/++--+- жж L

жж жж ж А ж ж +----+->+жTж+м жж ----м L+--+- L-A-- L---- -/++-+-ж жж k ----м жMUXж ---м --мж C ж жж L----+ 1 +- CC 0>+0 +->+M2+->+&+- ж жж

a>+1 ж->+ ж->+ ж ж жж SYN L---- b>+2 жж L---ж L-- ж жж жА жжe' L

LA---L

Эта схема используется только в конвейерном варианте взаимодействия. Метод вычисления адреса для следующего такта такой же, как и в схеме с регулярной адресацией. (Другой тер- мин -"естественный" - употреблен только ради различения самих схем.) Но в этой схеме, по сравнению с уже рассмотренными, разряд управляющей памяти с одним и тем же номером (разрядный срез) в различных микроинструкциях может быть использован различным образом. Будем различать микроинструкции двух ти- пов: - операционные, - алресации (выбора). В лданном варианте схемы тип микроинструкции устанавли- вается разрядом с именем "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 --ж-+--T--T--+ 2 ж1ж 1ж 1ж 2ж n3 { m3 } -- 3 --ж-+--+--+--+ 3 ж0ж m3 ж n4 { m4 } -- 4 4 ж0ж m4 ж --ж-+--T--T--+ 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 --ж-+--T--T--+ 8 ж1ж 1ж 1ж 7ж g4 <<GO(a;n5,n3)>>-- 8 9 ж1ж 0ж 1ж 3ж

Вместе с этой схемой обычно используется условная син- хронизация, которая позволяет удлинить такт выполнения микро- - 9 - команды в ОА на время выполнения микроинструкций адресации.

SYN

L-- L-- L-- L-- L-- | | | | | k 0

| | | | | CCм

L-- L-- L-- | | | | | Y

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

- 10 -

ж ж ----мж ----м ж г==>жжRGжж==м ж ж жMUXжж жROMж ж ж ->+ж ж+-мж F =ж

ж ж -T--Tм ж жж ж ж ж ж ж жж ж ж жжRGжж ж жж ж ж ж ж ж жж ж L>жж жж=>ж1 жж ж жSжHжeж жж ж Cжж жж ж жж ж ж ж ж ж -T--TмYжж для RG"Y" ж -/++--+- ж жж>ж ж

ж -T--Tм ж жA ж ж жж жж жж 0w-загрузка ж ----м жжRGжж ж ж ж ж w cжж жж жж L>жINCж=>жж жжT>ж2 ж ж ж -A-/++--+- жж 1w-нет загр. L---- Cжж жжж ж ж ж ж ж жж -/++--+-ж ж ж ж ж ж жж г

ж -T

L>жжSTACKжж=>ж3 ж ж жK ж -T--TмK' жж L+----A+- ж ж ж ж===ж>жжRGжжм жж ж ж А ж ж ж жж жжж жж ж L-A-- L---- -/++--+-ж жж ----м ж ж C ж жж жMUXж ---м -ж

0>+0 +->+M2+>+ CS ж<

a>+1 ж->+ ж ж ж жж b>+2 жж L--- L

жА жжe' жж L-+ 1 +-CC LA---L

_УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ В конвейерном варианте для команд переходов по предикат- ным переменным, зависящих без сдвига от сигналов управления, приходится добавлять еще один такт для того, чтобы "увидеть" значение переменной, по которой выполняется ветвление, и выб- рать нужную МКИ. Можно построить управляющий автомат, в котором для уско- рения выполнения программы выполняются следующие действия: Предварительно выбирается из ПЗУ одна из двух альтернативных МКИ, соответствующая наиболее вероятному значению переменной ветвления. Это значение должно храниться в той МКИ, после ко- торой выполняется ветвление. В конце такта выработанное ре- альное значение переменной сравнивается с предсказанным, если они совпадают, то выбранная из ПЗУ МКИ записывается в выход- ной регистр, если нет, то предыдущий такт продлевается, т.е. не синхронизируются ОА и RG'МКИ. Микропрограмма будет такой же как и для последовательного варианта взаимодействия ОА и УА, но в МКИ добавляются два разряда: F = { 1, если используется предвосхищение; 0, если нет }, P - наиболее вероятное значение переменной ветвления. Фрагмент схемы УА, обеспечивающий предвосхищение может быть таким:

-T--Tм ж -VT---м q -A---м f t жжRGжж L-->+MUX+--->+ SS +<

--T--->+ж ж+---->+ ж--->+ +<

ж жж жж ж жжt ж ж p жж ж -\++--+- L----ж -\+T---- жж ж ж ж ж жj жж L---+

ж ж жMUXж ж ROM +--->+жRGж+--ж ж ж ж ж ж ж F жж жжf ж ж ж ж +--->+ж ж+--- ж ж ж ж жж жж ж ж ж ж--->жж жж--> ж ж ж ж жж жж C ж ж L

----+

Пусть 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)ж ж L

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

ж ж (p:, b) = a+p ж ж L

- 2 - ОА, реализующий инкрементор в целом, будет следующим: ---T-м a

--T-мp ж ж ж начальное значен.-+SжT+--+ жP+--м +-+ ж L--+-- ж SYN

-+Dж ж ж жL-+-- ж L

Конечно, эта реализация совпадает с реализацией алгоритма ав- томатного типа, если состояние р1 кодируется 1, а состояние р0 - 0. Этот пример показывает,что до начала вычислений может потребоваться начальная установка памяти. На самом деле это необходимо было уже в алгоритмах автоматного типа, так как код начального состояния требует предварительной установ- ки. Ограничимся здесь обозначением этой проблемы, а решение ее, связанное прежде всего с корректной синхронизацией ус- тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк- вивалентного автомату Мили , не обсуждалась простая возмож- ность ее реализации и на структурном уровне. Например, только что рассмотренный автомат Мили может быть преобразован в эк- вивалентный автомат Мура по одному из следующих вариантов: -T-Tмt---T-м ---T-м -T-Tм a --_+жTж+_+HSжS+-_b a

-/++-+- ж ж ж ж ж ж-/++-+- C ж ж ж C ж ж ж C -/TT-Tмpж ж ж -/TT-Tмpж ж ж -_+жTж+_+ жP+м -_+жTж+_+ жP+м ж L+-+- L--+--ж ж L+-+- L--+--ж L

При таких структурных преобразованиях проще истолковы- вать алгоритмы как процедурные. - - - p:=1; t:=0 - - p:=1 - - -

ж жt:=a;(p:,b)=t+pж ж ж (p , b):= a+p ж ж L

БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после некоторых дополнений может быть использован и для описания алгоритмов в процедурной форме: Блок-текст состоит из трех частей: 1)- Описание переменных и начальных значений памяти. 2)- Описания функций и связей. Записываются любые функции и функциональные связи (в том числе предикатные), не использу- ющие запоминания. Переменные из левой части операции присва- ивания таких функциональных описаний используются в блоках процедуры. 3)- Процедура, состоящая из блоков (микроблоков) операторных и блоков переходов: - операторные - в скобках вида {.....}, - перехода - в скобках вида <<...>>; и те, и другие блоки могут снабжаться метками, стоящими перед блоком. В блоках перехода используется оператор GO в одной из двух форм: GO m - безусловный переход, GO (P; m0,m1,m2,...) - условный переход. здесь m0,m1,... - метки блоков, P - предикатное значение,интерпретируемое оператором GO - 3 - как неотрицательное целое число, являющееся порядковым номе- ром метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма.

На следующем более сложном примере демонстрируется пос- ледовательность синтеза операционного устройства. Пример. Вычислитель наибольшего общего делителя (НОД) двух натуральных чисел (8-разрядных). 1) Разработаем интерфейс вычислителя:

8 ---T

===+=>жI1ж НОД ж ж ж ж ж ж 8 8 ж ж жD ж==+==> ===+=>жI2ж ж ж +--+ +--+

+--+ ж ж

L--+

I1[7..0], I2[7..0] -входные информационные шины. rI -входной сигнал готовности: если rI=1, то на входах I1, I2 готовы операнды. D[7..0] -выходная информационная шина . rO -выходной сигнал готовности: если rO=1, то готов резуль- тат на шине D, который сохраняется до появления новых операн- дов. 2) Математическое обоснование алгоритма вычислений: Идея алгоритма, следуя Евклиду (IIIв. до р.Х.), заключа- ется в том, что НОД двух натуральных чисел А и В в случае ра- венства этих чисел совпадает с любым из них, а в случае их неравенства совпадает с НОД двух других чисел: меньшего и разности между большим и меньшим. Последовательно, уменьшая числа, получим два равных числа -значение одного из них и бу- дет НОД исходных чисел. 3) Блок-схема алгоритма (микропрограмма в содержательном виде):

- 4 -

- ж

m1ж rO: = 0 ж L

жж

-VVV- ж ж / \ 0 ж ж < rI>

\_/ ж ж1 ж

ж rO: = 0 ж ж ж ж ж m2ж А: = I1 ж ж ж ж ж ж B: = I2 ж ж L

ж m3ж (p,S)=A - B ж ж ж L

ж -V- m6 ж ж / \ =0

ж z <S==0>--->+ rO:=1;D=A+- ж \__/ L

ж ж+0 ж V ж 0 / \ 1 ж

жm4ж (x,B:)=-A+B ж m5ж (x,A:)=A - B ж ж L

Или в виде блок-текста: 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 г

-/TT--Tм ж

CжжRGжж ж ж f1=(A-B) ж жж жж ж Aж ж I1

жж жж ж жS Sж1ж жж жж ж ж> =>+ o--->z ++--+- ж ж ж ж B ж ж L-- -/TT--Tм ж ж CжжRGжж ж +

жж жжB Bж ж I2

жж жж ж ж Cжж ж+>rO жж жж ж ж жж жж rI

Кроме того, в ОА необходимо реализовать все информацион- ные связи, соответствующие микрооперации коммутации, а также микрооперации запоминания (загрузки, записи) и обнуления.

ж A г

ж ж MUXж CжжRGжж ж жM2*8ж 1->+cr SMж ж ж=>+0 ж жж жж ж ж ж +- ж ж I1==ж=>+1 ж

ж + ж жж жж A ж ж ж ж ж ж1ж ж жА ж Wжж жж +- ж ж Sж=ж>ж o--->z ж LA---- -A++--+- LA---- ж ж ж ж ж ж ж ж ж ж L-- ж umA uA uiA ж ж ж B ж ж ж

ж ж MUXж CжжRGжж жM2*8ж ж p+

L=>ж0 ж жж жж B ж ж ж ж I2====>ж1 ж

+ ж жж жж ж ж ж ж -/TT-Tм жА ж Wжж жж +- ж ж ж1->+жTж+>rO LA---- -A++--+- LA---- L

ж ж ж -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 г

ж ж MUXж CжжRGжж ж жM2*8ж 1->+cr SMж ж ж=>ж0 ж жж жж ж ж ж +- ж ж I1==ж=>ж1 ж

ж + ж жж жж ж ж ж ж ж ж1ж ж жА ж Wжж жж +- ж ж Sж=ж>ж o--->z ж LA---- -A++--+- LA---- ж ж ж ж ж L----м --- B

ж ж MUXжж ж CжжRGжж ж жM2*8ж ж p+

L=>ж0 жж ж жж жж ж ж ж ж ж I2====>ж1 жж===ж=>+ж жж==ж==>+ ж===>жI2 ж + жж ж жж жж ж ж ж ж ж жА жж ж Wжж жж ж +- ж ж ж C LA----ж ж-A++--+- ж LA---- L

ж ж ж L-м ж --мж 1->+жTж+>rO ж ж ж ж +>+ o- R Wжж жж +

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 ж ж LT--T--A---A---A---A---A---A

ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж -V--V--+---+---+---+---+---+

ж жz p y1 y2 y3 y4 y5 y6 ж ж ж ж +--/C ж ж УА ж -->+rI ж L

УА должен выполнять следующий алгоритм автоматного типа, представленный в виде блок-текста: 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--Tм ж ж ----м жжT ж+--->+0 ж

L+--+- -->+1 ж ж SMж ж ж -T--Tм -->+А +--->+cr ж ===>ж0 ж===>жжRGжж==> +---+ ж Sж

R1 жMUXж ж ж ===>жА ж -T--Tм ж ж ж ж L---- жжRGжж===>ж0 ж===>жI1 ж ----м L+--+- ==>ж1 ж ж ж жMUXж ==>жА ж ж ж ж +

+---+ ж p+

R2 жMUXж===>жI2 ж --->+1 ж -T--Tм ж ж L

жжRGжж===>ж0 ж L---- L+--+- ==>ж1 ж ==>жА ж L----

Имена всех переменных, используемых в этом микрооператоре, означают выполнение микроопераций коммутации ( транспортиров- ки ). Значения переменных коммутируются на входы суммматора, а результат суммирования - в места расположения переменных. МИКРОБЛОК - набор микрооператоров, выполняемых одновре- менно ( в одном такте ) и синхронно. В одном микроблоке любо- му из битов присваивается только одно значение. Синхронность означает, что во всех микрооператорах одно- го микроблока используется только "старое" значение памяти. Например: { (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)- - - ж ж

m1ж CT:=3 ж m1ж CT:=3 ж L----T---- L----T----

ж -V- ж -V- ж / \ =0 ж / \ =0 ж <CT==0>-> ж <CT==0>-> ж \___/ ж \___/ ж ж+0 ж ж+0 ж

жm2ж........ж жm2ж........ж ж ж ж ж ж ж ж жCT:=CT-1ж ж жCT:=CT-1ж ж L----T---- ж L----T---- L

жm3ж........ж ж L----T---- L

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

_КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА В общем случае каноническая структура операционного ав- томата имеет вид:

- - -

-->жкоммутацияж жжпамятьжж жкоммутацияж жфункцииж--- ж ж--->жж жж-->ж ж-->ж ж -->ж ж жж жж ж ж ж ж---> L-A

- --мжCC - - - - SYN->+&+- - - - - -+ ж - - - - yCжL-- - - - L

сигналы управления

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

- 11 -

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

ж J:=0 ж -T--T-м ж MUXж

ж ж ..... ж жж ж.ж . ж. ж ж ж B ж ж ж жж ж ж ж ж ж ж==> ж ж B= f(...,A[J])ж жж жK+--->+K ж ж ж ж ж ж жж ж.ж ж. ж ==>ж ж ж ж J:=J+1 ж жж ж.ж ж. ж ж ж ж L

ж -V- L+--+-- +- ж L

ж <K / \ =K J

\__/

(реализация счетчика J не показанa).

- 12 - Запишем этот фрагмент алгоритма иначе так, чтобы нужный бит извлекался за счет сдвига в регистре D. Тогда получим:

---T-- A D ж -T--Tм -T--T-м A[J]

ж J:=0 ж жж жж жж ж.ж ж ж ж ж жж жж жж->ж.ж ж ж B ж D:=A ж жж жж

ж ж ..... ж жж жж жж ж.ж ==>ж ж ж ж ж жж жж S Wжж ж.ж ж ж ж ж B= f(...,D[0])ж L+--+- -v-v++--+-- L

ж ж ж ж ж (D,x):=(x,D) ж ж ж ж ж ж J:=J+1 ж ж L

ж -V- ж <K / \ =K L

\__/

Промежуточный регистр A введен для общности, если потребуется сохранить слово А (чаще всего он и не нужен). Другой пример: фрагмент алгоритма, реализующий регуляр- ную запись отдельных бит слова и его реализация имеют вид: ---T-- -T-TмB[0] ж a

ж J:=0 ж ----м ж -A++-+- L

ж ж ..... ж ж .ж. L

ж ж ж ж .ж. Wжж жж ж ж a=f(...) ж J ==>ж ж -A++-+- ж ж ж ж K+

ж ж B[J]:=a ж ж .ж ж ж ж ж .ж ж ж J:=J+1 ж ж .ж ж L

ж -V- ж <K / \ =K L

\__/

Слово В нельзя реализовать в виде регистра, а только в виде отдельных триггеров. Можно формировать слово с использованием операции сдви- га при обязательном условии D[K..0], тогда алгоритм и его ре- ализация имеют вид:

- 13 -

---T-- ж D B

ж J:=0 ж ж жRGжж жжRGжж L

ж ж ..... ж Sж ж жж Wжж жж ж ж ж -v+--+--+- -v++--+- ж ж a=f(...) ж ж ж ж ж ж (D,x):=(a,D) ж ж ж ж ж ж J:=J+1 ж ж L

ж -V- ж <K / \ =K

\__/ L

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

_УНИВЕРСАЛЬНЫЙ ОА Использование при проектировании универсальных ОА с за- ранее фиксированной и минимизированной структурой оправдано тем, что такие универсальные ОА изготавливаются промышлен- ностью в виде БИС большим тиражом и поэтому они сравнительно дешевы. Такие универсальные ОА входят в микропроцессорные на- боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на- зываются микропрограммируемыми, секционными, разрядно-модуль- ными. В основе перечисленных универсальных ОА лежит следующая структура: г

ж ж ж ж ж SYNм ACC ж ж --T

ж ж ж RGF жж ж CжжRGжж ж ALU ж ж ж ж ж жж ж жж жж ж ж ж ж ж ж жж L====>жж жж

ж ж ж жж жж жж ж ж===ж=>DO L===>жDж жж L+--+- ж ж ж ж жж T ж ж ж ж жж -T--Tм ж ж

ж ж жж жжRGжж ж ж ж ж жж

ж ж жж жж жж ж ж C WжАж жж Cжж жж г=>ж ж -o-A+A+

SYN- ж ж SYN- ж ж ж ж ж ж yW YA DI

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' с началом следующего такта, т.е. на пе- реднем фронте сигнала.

_ВЗАИМОДЕЙСТВИЕ ОА и УА Для исключения гонок при взаимодействии ОА и УА будем проектировать УА как автомат Мура. Схема их взаимодействия может быть представлена в виде: г

Lж CS ж жжRGжж жCS ж<- ж ж<=T=жж жж<==ж ж ----+ b ж ж жж жж ж c +<----м ж L

ж жCS ж<=- ж ж ж---+ a +<

ОА жж L

----жж

УА жжРА

жL->+ CSж жжRGжж ж CS +- ж жж L-->+ ж====>жж жж=>ж +--- жжY РВ ж ж жж жж ж +

г>ж p ж жж жж ж y ж=м - ж L

Отметим, что РА(t)=f(Y(t)) зависит без сдвига от сигналов управления, PB(t+1)=F(Y(t)) зависит со сдвигом от сигналов управления, где РА и РВ - предикатные перемнные. Продолжительность такта работы схемы определяется наибо- лее длинными цепями между регистрами. Для данной схемы, кото- рую будем называть последовательной схемой взаимодействия, зададимся (так чаще всего бывает), что такой критической цепью является цепь (CSy,CSa,CSp,RG). Поэтому длительность такта определяется: Т > ty + ta + tp + trg, где tj- время установления соответствующего компонента цепи. Чтобы сократить длину этой цепи, применяют другой вари- ант взаимодействия автоматов - конвейерный:

- 15 -

Lж CS ж жжRGжж жCS ж<- ж ж<=T=жж жж<==ж ж

ж FF L

ж -T--Tм

ж--+жRGжж<==ж CS ж<=- ж ж жж жж жж ж a +<

жж L+--++A- L

ОА жж L

---жж

УА жж MK ж ж ж ж жж PA

жL---->+ CSж CS ж жжRGж+- ж ж жж ж РВ ж ж ж жж ж+--- ж жжY L

ж ж ж жж ж+

г>ж p ж y ж жж жж=м - ж L----+

При этом варианте взаимодействия такой длинной цепи, как в предыдущем случае, не возникает.Эта цепь разделена регис- трами 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 ж

л ж L

У этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов - 16 - D-триггера. Схема автомата вместе с цепями условной синхронизации выглядит следующим образом (для синхронизации по фронтам): а)-по переднему фронту, б)- по заднему фронту: ---м ---м SYN --T

ж --T-м --+ ж ж --T-м --+ ж L-/CжTж ж L--- L-\CжTж ж L--- ж ж + ж ж ж +--- --+Dж ж ж --+Dж ж ж +-+ o--- ж +-+ o- +-oRж ж +-oRж ж H ж L-+--уст. нач. зн. H ж L-+--уст. нач. зн. --+

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

Антик М.И. 11_03_91 МИРЭА

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

ж ---V--V

ж ж B=FO(S,A) ж ж ж ж ж ж S:=FS(S,A)ж ж L

ж ж (p:, b) = a+p ж ж L

ОА, реализующий инкрементор в целом, будет следующим: ---T-м a

--T-мp ж ж ж начальное значен.-+SжT+--+ жP+--м +-+ ж L--+-- ж SYN

-+Dж ж ж жL-+-- ж L

-/++-+- ж ж ж ж ж ж-/++-+- C ж ж ж C ж ж ж C -/TT-Tмpж ж ж -/TT-Tмpж ж ж -_+жTж+_+ жP+м -_+жTж+_+ жP+м ж L+-+- L--+--ж ж L+-+- L--+--ж L

При таких структурных преобразованиях проще истолковы- вать алгоритмы как процедурные. - - - p:=1; t:=0 - - p:=1 - - -

ж жt:=a;(p:,b)=t+pж ж ж (p , b):= a+p ж ж L

БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после некоторых дополнений может быть использован и для описания алгоритмов в процедурной форме: Блок-текст состоит из трех частей: 1)- Описание переменных и начальных значений памяти. 2)- Описания функций и связей. Записываются любые функции и функциональные связи (в том числе предикатные), не использу- ющие запоминания. Переменные из левой части операции присва- ивания таких функциональных описаний используются в блоках процедуры. 3)- Процедура, состоящая из блоков (микроблоков) операторных и блоков переходов: - операторные - в скобках вида {.....}, - перехода - в скобках вида <<...>>; и те, и другие блоки могут снабжаться метками, стоящими перед блоком. В блоках перехода используется оператор GO в одной из двух форм: GO m - безусловный переход, GO (P; m0,m1,m2,...) - условный переход. здесь m0,m1,... - метки блоков, P - предикатное значение,интерпретируемое оператором GO как неотрицательное целое число, являющееся порядковым номе- ром метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма.

8 ---T

===+=>жI1ж НОД ж ж ж ж ж ж 8 8 ж ж жD ж==+==> ===+=>жI2ж ж ж +--+ +--+

+--+ ж ж

L--+

m1ж rO: = 0 ж L

жж

-VVV- ж ж / \ 0 ж ж < rI>

\_/ ж ж1 ж

ж rO: = 0 ж ж ж ж ж m2ж А: = I1 ж ж ж ж ж ж B: = I2 ж ж L

ж m3ж (p,S)=A - B ж ж ж L

ж -V- m6 ж ж / \ =0

ж z <S==0>--->+ rO:=1;D=A+- ж \__/ L

ж ж+0 ж V ж 0 / \ 1 ж

жm4ж (x,B:)=-A+B ж m5ж (x,A:)=A - B ж ж L

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 г

-/TT--Tм ж

CжжRGжж ж ж f1=(A-B) ж жж жж ж Aж ж I1

жж жж ж жS Sж1ж жж жж ж ж> =>+ o--->z ++--+- ж ж ж ж B ж ж L-- -/TT--Tм ж ж CжжRGжж ж +

жж жжB Bж ж I2

жж жж ж ж Cжж ж+>rO жж жж ж ж жж жж rI

ж A г

ж ж MUXж CжжRGжж ж жM2*8ж 1->+cr SMж ж ж=>+0 ж жж жж ж ж ж +- ж ж I1==ж=>+1 ж

ж + ж жж жж A ж ж ж ж ж ж1ж ж жА ж Wжж жж +- ж ж Sж=ж>ж o--->z ж LA---- -A++--+- LA---- ж ж ж ж ж ж ж ж ж ж L-- ж umA uA uiA ж ж ж B ж ж ж

ж ж MUXж CжжRGжж жM2*8ж ж p+

L=>ж0 ж жж жж B ж ж ж ж I2====>ж1 ж

+ ж жж жж ж ж ж ж -/TT-Tм жА ж Wжж жж +- ж ж ж1->+жTж+>rO LA---- -A++--+- LA---- L

ж ж ж -A-A++-+- uMB uB uiB urO uwO

В незаполненных клетках сигналы безразличны. Заметив, что umA = umB , uiB = мuiA , окончательно полу- чаем: г

ж A г

ж ж MUXж CжжRGжж ж жM2*8ж 1->+cr SMж ж ж=>ж0 ж жж жж ж ж ж +- ж ж I1==ж=>ж1 ж

ж + ж жж жж ж ж ж ж ж ж1ж ж жА ж Wжж жж +- ж ж Sж=ж>ж o--->z ж LA---- -A++--+- LA---- ж ж ж ж ж L----м --- B

ж ж MUXжж ж CжжRGжж ж жM2*8ж ж p+

L=>ж0 жж ж жж жж ж ж ж ж ж I2====>ж1 жж===ж=>+ж жж==ж==>+ ж===>жI2 ж + жж ж жж жж ж ж ж ж ж жА жж ж Wжж жж ж +- ж ж ж C LA----ж ж-A++--+- ж LA---- L

ж ж ж L-м ж --мж 1->+жTж+>rO ж ж ж ж +>+ o- R Wжж жж +

umB uwA uwB uiA urO uwO ---ж

y1 y2 y3 y4 y5 y6

==>жI1 ж ж ж ==>жI2 ОА Dж==> ж ж ---/C rO+--> ж ж ж ж жz p umB uwA uwB uiA urO uwO ж ж LT--T--A---A---A---A---A---A

ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж ж -V--V--+---+---+---+---+---+

ж жz p y1 y2 y3 y4 y5 y6 ж ж ж ж +--/C ж ж УА ж -->+rI ж L

МИКРОПРОГРАММИРОВАНИЕ. ОПРЕДЕЛЕНИЯ. МИКРООПЕРАЦИЯ - базисное (элементарное) действие, необ- ходимое для получения (вычисления) значения одной или более переменных. Микрооперация присваивания В=А означает, что переменные левой части получают значения выражения из правой части. Всегда разрядность левой части равна разрядности правой час- ти. При этом биты, расположенные на одной и той же позиции в левой и правой частях, равны. Неиспользуемые разряды в левой части и произвольные зна- чения в правой части микрооперации присваивания обозначаются (х). Например: (В[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--Tм ж ж ----м жжT ж+--->+0 ж

L+--+- -->+1 ж ж SMж ж ж -T--Tм -->+А +--->+cr ж ===>ж0 ж===>жжRGжж==> +---+ ж Sж

R1 жMUXж ж ж ===>жА ж -T--Tм ж ж ж ж L---- жжRGжж===>ж0 ж===>жI1 ж ----м L+--+- ==>ж1 ж ж ж жMUXж ==>жА ж ж ж ж +

+---+ ж p+

R2 жMUXж===>жI2 ж --->+1 ж -T--Tм ж ж L

жжRGжж===>ж0 ж L---- L+--+- ==>ж1 ж ==>жА ж L----

m1ж CT:=3 ж m1ж CT:=3 ж L----T---- L----T----

ж -V- ж -V- ж / \ =0 ж / \ =0 ж <CT==0>-> ж <CT==0>-> ж \___/ ж \___/ ж ж+0 ж ж+0 ж

жm2ж........ж жm2ж........ж ж ж ж ж ж ж ж жCT:=CT-1ж ж жCT:=CT-1ж ж L----T---- ж L----T---- L

жm3ж........ж ж L----T---- L

- - -

-->жкоммутацияж жжпамятьжж жкоммутацияж жфункцииж--- ж ж--->жж жж-->ж ж-->ж ж -->ж ж жж жж ж ж ж ж---> L-A

- --мжCC - - - - SYN->+&+- - - - - -+ ж - - - - yCжL-- - - - L

сигналы управления

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

ж J:=0 ж -T--T-м ж MUXж

ж -V- L+--+-- +- ж L

ж <K / \ =K J

\__/

(реализация счетчика J не показанa). Запишем этот фрагмент алгоритма иначе так, чтобы нужный бит извлекался за счет сдвига в регистре D. Тогда получим: ---T-- A D ж -T--Tм -T--T-м A[J]

ж J:=0 ж жж жж жж ж.ж ж ж ж ж жж жж жж->ж.ж ж ж B ж D:=A ж жж жж

ж ж ..... ж жж жж жж ж.ж ==>ж ж ж ж ж жж жж S Wжж ж.ж ж ж ж ж B= f(...,D[0])ж L+--+- -v-v++--+-- L

ж ж ж ж ж (D,x):=(x,D) ж ж ж ж ж ж J:=J+1 ж ж L

ж -V- ж <K / \ =K L

\__/

ж J:=0 ж ----м ж -A++-+- L

ж ж ..... ж ж .ж. L

ж ж ж ж .ж. Wжж жж ж ж a=f(...) ж J ==>ж ж -A++-+- ж ж ж ж K+

ж ж B[J]:=a ж ж .ж ж ж ж ж .ж ж ж J:=J+1 ж ж .ж ж L

ж -V- ж <K / \ =K L

\__/

ж J:=0 ж ж жRGжж жжRGжж L

ж ж ..... ж Sж ж жж Wжж жж ж ж ж -v+--+--+- -v++--+- ж ж a=f(...) ж ж ж ж ж ж (D,x):=(a,D) ж ж ж ж ж ж J:=J+1 ж ж L

ж -V- ж <K / \ =K

\__/ L

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

УНИВЕРСАЛЬНЫЙ ОА Использование при проектировании универсальных ОА с за- ранее фиксированной и минимизированной структурой оправдано тем, что такие универсальные ОА изготавливаются промышлен- ностью в виде БИС большим тиражом и поэтому они сравнительно дешевы. Такие универсальные ОА входят в микропроцессорные на- боры 582, 583, 584, 588, 589, 1800, 1804 и т.д., которые на- зываются микропрограммируемыми, секционными, разрядно-модуль- ными. В основе перечисленных универсальных ОА лежит следующая структура: г

ж ж ж ж ж SYNм ACC ж ж --T

ж ж ж RGF жж ж CжжRGжж ж ALU ж ж ж ж ж жж ж жж жж ж ж ж ж ж ж жж L====>жж жж

ж ж ж жж жж жж ж ж===ж=>DO L===>жDж жж L+--+- ж ж ж ж жж T ж ж ж ж жж -T--Tм ж ж

ж ж жж жжRGжж ж ж ж ж жж

ж ж жж жж жж ж ж C WжАж жж Cжж жж г=>ж ж -o-A+A+

SYN- ж ж SYN- ж ж ж ж ж ж yW YA DI

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' с началом следующего такта, т.е. на пе- реднем фронте сигнала. ВЗАИМОДЕЙСТВИЕ ОА и УА Для исключения гонок при взаимодействии ОА и УА будем проектировать УА как автомат Мура. Схема их взаимодействия может быть представлена в виде: г

Lж CS ж жжRGжж жCS ж<- ж ж<=T=жж жж<==ж ж ----+ b ж ж жж жж ж c +<----м ж L

ж жCS ж<=- ж ж ж---+ a +<

ОА жж L

----жж

УА жжРА

жL->+ CSж жжRGжж ж CS +- ж жж L-->+ ж====>жж жж=>ж +--- жжY РВ ж ж жж жж ж +

г>ж p ж жж жж ж y ж=м - ж L

Lж CS ж жжRGжж жCS ж<- ж ж<=T=жж жж<==ж ж

ж FF L

ж -T--Tм

ж--+жRGжж<==ж CS ж<=- ж ж жж жж жж ж a +<

жж L+--++A- L

ОА жж L

---жж

УА жж MK ж ж ж ж жж PA

жL---->+ CSж CS ж жжRGж+- ж ж жж ж РВ ж ж ж жж ж+--- ж жжY L

ж ж ж жж ж+

г>ж p ж y ж жж жж=м - ж L----+

НАЧАЛЬНАЯ ИНИЦИАЛИЗАЦИЯ СИНХРОННОЙ СХЕМЫ Пусть устройство, кроме сигнала синхронизации SYN, имеет еще один сигнал Н, обозначающий начало и конец синхронной ра- боты устройства. При Н=0 - нерабочее состояние - можно выпол- нять начальную установку значений памяти устройства. Измене- ние значения Н с 0 на 1 происходит в случайный момент времени (асинхронно), но при этом начальный такт работы устройства должен быть полным. "Затягивание" асинхронного сигнала Н в синхронный режим происходит с помощью простейшего синхронного автомата с диаграммой:

V 0H/CONSTж V 1H/SYNж

>ж 0 ж

л ж L

У этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов D-триггера. Схема автомата вместе с цепями условной синхронизации выглядит следующим образом (для синхронизации по фронтам): а)-по переднему фронту, б)- по заднему фронту: ---м ---м SYN --T

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

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 } ж L-T-- ж --V-м n2 { m2 } n2ж жm2 ж ж L-T-- g1 <<GO(a;g1,n3)>> ж ж<--м ж -Vм 0ж n3 { m3 } g1ж < a >-- ж LT- n4 { m4 } ж 1ж<----м ж ж----мж g2 <<GO((a,b);n5,n3,n1,n1)>> ж --VVм жж n3ж жm3 ж жж n5 { m5 } ж L-T-- жж ж --V-м жж g3 <<GO(a;n5,n3)>> n4ж жm4 ж жж ж L-T-- жж ж10 -Vм 01жж g2L--< ab>---ж 11 LT- ж 00ж----мж --VVм жж n5 жm5 ж жж L-T-- жж -Vм 0 жж g3 < a >---ж LT- 1 ж L

СХЕМА С АДРЕСНЫМ ПЗУ Начнем рассмотрение с управляющего автомата, структура которого совпадает с канонической структурой автомата Мура. ----м ----м -T--Tм ----м жMUXж q жROMж жжRGжж жROMж a->+0 +-->+ ж S' жж жж S ж ж Y b->+1 ж ж ж===>жж жж=T>ж ж==> ж ж г>ж ж жж жж ж ж +-м жА ж ж ж 2 ж Cжж жж ж ж 1 ж ж LA--- ж L---- -/++--+- ж L---- ж ж H L

----м q ----м ----м -T--Tм жMUX+

СХЕМА С ЯВНЫМ УКАЗАНИЕМ АЛЬТЕРНАТИВНЫХ АДРЕСОВ

жг

LA--- ж L

Конвейерный вариант

жг

жж ----м

жА +

LA--- ж L

n1 { m1 } Aж Y H A0 A1ж -+

d2 { m0 }

<<GO(b;n5,n3)>>

n5 { m5 }

<<GO(a;n5,n3)>> СХЕМА С ЧАСТИЧНОЙ ЗАПИСЬЮ АДРЕСА

Последовательный вариант Конвейерный вариант

ж H' ж C жж ж L

n1 { m1 } --(0,0),(2,1) S'q'ж Y H S eж ----+

<<GO(a;n5,n3)>>-- 3,x

Распределять микроинструкции по ячейкам памяти удобно в следующем порядке: - связать с различными операторами условного перехода, кон- фликтующими между собой по адресации, различающиеся между со- бой старшие разряды адреса; - распределить микроблоки по ячейкам памяти с учетом назнач- енных старших разрядов адреса и входных значений; - оставшимся нераспределенным микроблокам назначить произ- вольные свободные адреса. СХЕМА С СОКРАЩЕННЫМ ТАКТОМ Использование этой схемы позволяет при сохранении пре- имуществ последовательного варианта взаимодействия сократить наиболее длинные цепи, общие для ОА и УА, до длины цепей кон- вейерного варианта.

ж г

ж ж

ж ж жROM ж=+A ж ж==>жж жж==>Y' --T

ж ----мж ж ж ж==>ж1 ж жж жж ROM_1 A'ж Y H A eж ж жMUXжL>ж +-+e жА ж Cжж жжмH' --+

L>+0 ж ж ж=+Y LA--- -/++--+-ж 0 жm4 1 2 xж a>+1 ж ж 1 ж=+H ж ж 1 жm3 0 0 1ж b>+2 ж L

жА +

LA--- ж --+

ж L

В этой схеме при разветвлении процесса вычислений пара альтернативных адресов получается следующим образом: один ад- рес всегда на единицу больше, чем текущий ( т.е. изменяется "регулярным" образом ), второй адрес - произвольный и содер- жится вместе с микрокомандой в микроинструкции. Элементом, "вычисляющим" адрес, является счетчмк, управ- ляемый сигналом, являющимся входным для УА. При различных значениях входного сигнала счетчик выполняет две функции: ли- бо прибавляет единицу к значению, которое хранилось в счетчи- ке и являлось текущим адресом, либо загружается значением ад- реса из управляющей памяти. В схему введен элемент М2, позволяющий инвертировать значение входного сигнала, что облегчает распределение микро- инструкций по ячейкам управляющей памяти. Адрес

n1 { m1 } -- 0 A ж Y H e Sж --+

<<GO(b;n5,n3)>>

n5 { m5 } -- 6

<<GO(a;n5,n3)>>

жг

жж жж жА ж ж +-->+ж ж+м ж ----м L+--+- LA--- L---- -/++--+-ж ж жMUXж ---м ж C ж ж 0->+0 +->+M2+

a->+1 ж->+ ж ж ж b->+2 жж L--- ж ж жА жж ж ж LA---L

СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ

жг

ж -/TT--Tм ж жA ж ж w cжж жж жж 0w-загрузка ж CжжRGжж ж ж ж ж -A-/++--+- жж L

жж жж ж А ж ж +----+->+жTж+м жж ----м L+--+- L-A-- L---- -/++-+-ж жж k ----м жMUXж ---м --мж C ж жж L----+ 1 +- CC 0>+0 +->+M2+->+&+- ж жж

a>+1 ж->+ ж->+ ж ж жж SYN L---- b>+2 жж L---ж L-- ж жж жА жжe' L

LA---L

SYN

L-- L-- L-- L-- L-- | | | | | k 0

| | | | | CCм

L-- L-- L-- | | | | | Y

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

ж ж ----мж ----м ж г==>жжRGжж==м ж ж жMUXжж жROMж ж ж ->+ж ж+-мж F =ж

ж -T

0>+0 +->+M2+>+ CS ж<

a>+1 ж->+ ж ж ж жж b>+2 жж L--- L

жА жжe' жж L-+ 1 +-CC LA---L

Переход к микроподпрограмме с возвратом При реализации достаточно сложных вычислений удобно вос- пользоваться механизмом микроподпрограмм. Одна и та же микроподпрограмма может быть вызвана из разных точек вызывающих микропрограмм. Поэтому при вызове микроподпрограммы необходимо запомнить адрес, с тем, чтобы восстановить его при возвращении из микроподпрограммы. Чтобы запомнить и восстановить адреса возврата от вложенных вызо- вов, используется безадресная память - стек (stack). Принцип (дисциплина) работы стека описывается условием "последний вошел - первым вышел" (Last In - First Out, LIFO). чтобы описать этот принцип будем считать, что слова, хранящи- еся в стеке, перенумерованы с помощью первых натуральных чи- сел 1,2,...,N. Слово с наибольшим номером называют вершиной стека. Стек может выполнять следующие действия: -"чтение" слова с наибольшим номером, -"выталкивание" (стирание) из памяти слова с наибольшим но- мером, -"запись" нового слова с присваиванием ему наибольшего номе- ра. При вызове микроподпрограммы выполняется операция "запи- си" адреса возврата в стек. При возвращении из микроподпрог- раммы выполняется операция "чтения" адреса возврата, затем - "выталкивания" его же из стека. Операция "чтения" без "выталкивания" выполняется при ис- пользовании стека для организации циклов. Разряды с именем "К" определяют тип выполняемой микро- инструкции. В связи с тем, что теперь в схеме существует 4 источника адреса для управляющей памяти, возможны 4 типа бе- зусловных переходов, кроме того, возможны различные условные переходы в различных сочетаниях комбинирующие эти источники адреса и входные переменные. С помощью комбинационной схемы CS разряды микроинструкции "К" преобразуются в сигналы управления стеком и мультиплексо- ром. УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ В конвейерном варианте для команд переходов по предикат- ным переменным, зависящих без сдвига от сигналов управления, приходится добавлять еще один такт для того, чтобы "увидеть" значение переменной, по которой выполняется ветвление, и выб- рать нужную МКИ. Можно построить управляющий автомат, в котором для уско- рения выполнения программы выполняются следующие действия: Предварительно выбирается из ПЗУ одна из двух альтернативных МКИ, соответствующая наиболее вероятному значению переменной ветвления. Это значение должно храниться в той МКИ, после ко- торой выполняется ветвление. В конце такта выработанное ре- альное значение переменной сравнивается с предсказанным, если они совпадают, то выбранная из ПЗУ МКИ записывается в выход- ной регистр, если нет, то предыдущий такт продлевается, т.е. не синхронизируются ОА и RG'МКИ. Микропрограмма будет такой же как и для последовательного варианта взаимодействия ОА и УА, но в МКИ добавляются два разряда: F = { 1, если используется предвосхищение; 0, если нет }, P - наиболее вероятное значение переменной ветвления. Фрагмент схемы УА, обеспечивающий предвосхищение может быть таким:

-T--Tм ж -VT---м q -A---м f t жжRGжж L-->+MUX+--->+ SS +<

--T--->+ж ж+---->+ ж--->+ +<

ж жж жж ж жжt ж ж p жж ж -\++--+- L----ж -\+T---- жж ж ж ж ж жj жж L---+

ж ж жMUXж ж ROM +--->+жRGж+--ж ж ж ж ж ж ж F жж жжf ж ж ж ж +--->+ж ж+--- ж ж ж ж жж жж ж ж ж ж--->жж жж--> ж ж ж ж жж жж C ж ж L

----+

Вы можете приобрести готовую работу

Альтернатива - заказ совершенно новой работы?

Вы можете запросить данные о готовой работе и получить ее в сокращенном виде для ознакомления. Если готовая работа не подходит, то закажите новую работуэто лучший вариант, так как при этом могут быть учтены самые различные особенности, применена более актуальная информация и аналитические данные

Blog

Информация о готовой работе

Бесплатная студенческая работ № 3846

Вы можете приобрести готовую работу

Альтернатива - заказ совершенно новой работы?