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

2Антик М.И. 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 - 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 ROM ROM Y RG Y a- 0 C S b- 1 - TT T T H г RG А S 2 1 C LA L - L L H L - 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 Конвейерный вариант г г

A0 -T T A0 MUX ROM RG - A1 A1 L 0 A - L 1 Y Y MUX H a- 0 А H b- 1 LA L А C 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 - А L - LA L H C L - 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 связать с различными операторами условного перехода, кон- фликтующими между собой по адресации, различающиеся

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

T T г ROM 0 A Y H A e 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 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 2 m1 0 4 0 А 3 m3 0 0 1 LA L - Способ адресации, по существу, такой же, как и в преды- дущей схеме.

Только в рассматриваемой схеме входной сигнал управляет выбором одного из двух блоков ПЗУ можно интерпре- тировать этот сигнал как старший разряд адреса . СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ 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 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 1 e e А L - LA L MUX C 0- 0 - M2 a- 1 - b-

2 L А LA L L 8 - СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И СОВМЕЩЕННЫМ НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ г C г - TT T H -T T г RG RG MUX ROM L INC 0 S H e L - L C -T T Y для RG Y RG - TT T A w c 0w-загрузка C RG -A L 1 k -T-T k 1w-нет загрузки А - T L - L-A L k MUX

C L 1 - CC 0 0 - M2 a 1 SYN L b 2 L L А e L где CC - LA L синхронизация ОА 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 0 0 1 1 CC L L L Y ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД. ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ Функциональный переход При необходимости выполнения нескольких вычислительныых функций, управление которыми представляется в виде независи- мых микропрограмм, необходимо организовать независимый вызов этих микропрограмм. Начальные адреса микропрограмм, управляющих вычислениями различных функций, обычно существуют вне управляющей

памяти. В УА достаточно предусмотреть механизм коммутации, позволя- ющий сделать начальный адрес текущим. Это можно осуществить в любой из рассмотренных схем. К механизму коммутации относят- ся, кроме аппаратуры, специальные разряды управляющей памяти и специальные микроинструкции 10 - г C г - TT T H г RG MUX ROM F 0 L - -T T RG L 1 S H e C -T T Y для RG Y RG -T T A 0w-загрузка

RG w c L INC T 2 -A 1w-нет загр. L C г - -T T k 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 k А e L- 1 -CC LA L L - SYN L Переход к микроподпрограмме с возвратом При реализации достаточно сложных вычислений удобно вос- пользоваться механизмом микроподпрограмм. Одна и та же микроподпрограмма может быть вызвана из разных точек вызывающих микропрограмм.

Поэтому при вызове микроподпрограммы необходимо запомнить адрес, с тем, чтобы восстановить его при возвращении из микроподпрограммы. Чтобы запомнить и восстановить адреса возврата от вложенных вызо- вов, используется безадресная память - стек stack . Принцип дисциплина работы стека описывается условием последний вошел - первым вышел Last In - First Out, LIFO . чтобы описать этот принцип будем считать, что слова, хранящи- еся в стеке,

перенумерованы с помощью первых натуральных чи- сел 1,2, ,N. Слово с наибольшим номером называют вершиной стека. Стек может выполнять следующие действия - чтение слова с наибольшим номером выталкивание стирание из памяти слова с наибольшим но- мером запись нового слова с присваиванием ему наибольшего номе- ра. При вызове микроподпрограммы выполняется операция запи- си адреса возврата в стек.

При возвращении из микроподпрог- раммы выполняется операция чтения адреса возврата, затем - выталкивания его же из стека. Операция чтения без выталкивания выполняется при ис 11 - пользовании стека для организации циклов. Разряды с именем К определяют тип выполняемой микро- инструкции. В связи с тем, что теперь в схеме существует 4 источника адреса для управляющей памяти, возможны 4 типа бе- зусловных переходов, кроме того, возможны различные условные переходы в различных сочетаниях

комбинирующие эти источники адреса и входные переменные. С помощью комбинационной схемы CS разряды микроинструкции К преобразуются в сигналы управления стеком и мультиплексо- ром. УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ В конвейерном варианте для команд переходов по предикат- ным переменным, зависящих без сдвига от сигналов управления, приходится добавлять еще один такт для того, чтобы увидеть

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

В конце такта выработанное ре- альное значение переменной сравнивается с предсказанным, если они совпадают, то выбранная из ПЗУ МКИ записывается в выход- ной регистр, если нет, то предыдущий такт продлевается, т.е. не синхронизируются ОА и RG МКИ. Микропрограмма будет такой же как и для последовательного варианта взаимодействия ОА и УА, но в МКИ добавляются два разряда F 1, если используется предвосхищение 0, если нет ,

P - наиболее вероятное значение переменной ветвления. Фрагмент схемы УА, обеспечивающий предвосхищение может быть таким W -T T -VT q -A f t RG L MUX SS T t p L - T j L -VT P -T T p MUX ROM RG F f C L - A - L 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 L T L Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, идентифицировать ша- ги этого алгоритма не надо. Например, инкрементор с одноразрядным входом и однораз-

рядным выходом может быть реализацией следующих преобразова- ний p 1 V-V p , b a p L T L - 2 - ОА, реализующий инкрементор в целом, будет следующим T- a HS S b T- p начальное значен S T P - L SYN C - D L- L Конечно, эта реализация совпадает с реализацией алгоритма ав- томатного типа, если состояние р1 кодируется 1, а состояние р0 - 0. Этот пример показывает,что до начала вычислений может потребоваться

начальная установка памяти. На самом деле это необходимо было уже в алгоритмах автоматного типа, так как код начального состояния требует предварительной установ- ки. Ограничимся здесь обозначением этой проблемы, а решение ее, связанное прежде всего с корректной синхронизацией ус- тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк- вивалентного автомату

Мили , не обсуждалась простая возмож- ность ее реализации и на структурном уровне. Например, только что рассмотренный автомат Мили может быть преобразован в эк- вивалентный автомат Мура по одному из следующих вариантов -T-T t T- T- -T-T a T HS S - b a HS S - T - b C C C - TT-T p - TT-T p - T P - T P L L L L L L При таких структурных преобразованиях проще истолковы- вать алгоритмы как

процедурные p 1 t 0 p 1 V-V V-V t a p ,b t p p , b a p L T L T L L БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после некоторых дополнений может быть использован и для описания алгоритмов в процедурной форме Блок-текст состоит из трех частей 1 - Описание переменных и начальных значений памяти. 2 - Описания функций и связей. Записываются любые функции и функциональные связи в том числе предикатные

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

GO P m0,m1,m2 условный переход. здесь m0,m1 метки блоков, P - предикатное значение,интерпретируемое оператором GO - 3 - как неотрицательное целое число, являющееся порядковым номе- ром метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма.

На следующем более сложном примере демонстрируется пос- ледовательность синтеза операционного устройства. Пример. Вычислитель наибольшего общего делителя НОД двух натуральных чисел 8-разрядных . 1 Разработаем интерфейс вычислителя 8 T T I1 НОД 8 8 D I2 rI rO C L 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 L T -VVV- 0 rI 1 V rO 0 m2 А I1 B I2 L T VV m3 p,S A - B L T -V- m6 0 z S 0 rO 1 D A - L 0 V 0 1 p V V m4 x,B -A B m5 x,A A - B L T L T 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 г D - TT T C RG f1 A-B A I1 - f2 -A B S S 1 o z - B L - TT T C RG p B B I2 - TT-T C rO rI - L L Кроме того, в ОА необходимо реализовать все информацион- ные связи, соответствующие микрооперации

коммутации, а также микрооперации запоминания загрузки, записи и обнуления. г A г D - TT T MUX C RG M2 8 1- cr SM 0 - I1 1 I1 A 1 А W - S o z LA -A - LA L umA uA uiA B - TT T MUX C RG M2 8 p p L 0 B I2 1 I2 C - TT-T А W - 1- T rO LA -A - LA L 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 - TT T MUX C RG M2 8 1- cr SM 0 - I1 1 I1 1 А W - S o z LA -A - LA L B - L - TT T MUX C RG M2 8 p p L 0 I2 1 I2 А W - C LA -A - LA L - TT-T L- 1- T rO o- R W L -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 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 MUX D L - 1 SM -T T А cr 0 RG S 1 L -

R1 MUX А -T T L RG 0 I1 L - 1 MUX А e p 0 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 V V m1 CT 3 m1 CT 3 L T L T -V- -V- 0 0 CT 0 - CT 0 - 0 0 V V m2 m2 CT CT-1 CT CT-1

L T L T L V m3 L T L В первом случае цикл будет выполнен 4 раза во втором - если в микроблоке m3 нет операций, модифицирующих СТ 3 ра- за. Обратите внимание на начальное значение СТ! МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и интерпретируемый как управляющий,т.е. необходимый для выпол- нения всех микроопераций одного микроблока. Сигналы, входящие в микрокоманду, могут принимать участие в микрооперациях и в качестве информационных.

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

управляющую память. КАНОНИЧЕСКАЯ СТРУКТУРА ОПЕРАЦИОННОГО АВТОМАТА В общем случае каноническая структура операционного ав- томата имеет вид -T T - коммутация память коммутация функции L-A A - L A L A - CC SYN yC L L сигналы управления Столь четкого разграничения операций на зоны память, комму- тация, функции может и не быть. Например, такие широко ис- пользуемые функции как сдвиги либо хорошо

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

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

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

велик объем аппаратуры КС - функциональное представление и его реализация являются статическим отображением входных объектов на выходные это исключает возможность работы с объектами, которые ведут се- бя более сложно во времени невозможно также реализовать принципиально рекуррентные алгоритмы см например,алгоритм Евклида для нахождения НОД . Тем не менее, если формально алгоритм функционального типа может быть записан, то проектирование устройства надо начинать с записи именно такого алгоритма.

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

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

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

которые располо- жены на одном и том же пути в сигнальном графе, либо на аль- тернативных путях решения 11 - МИНИМИЗАЦИЯ АППАРАТУРЫ Может оказаться, что на одном пути в сигнальном графе расположены операции, плохо или вовсе не совмещаемые друг с другом т.е. совмещение не дает экономии в аппаратуре функци- онального модуля . Возможно также, что проведенная минимиза- ция, сохраняющая минимальное время, не позволяет выполнить ограничение на объем аппаратуры.

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

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

3 с другим вариантом объединения функциональных модулей и памяти. При реализации ОА - во избежание ошибок -необходимо бук- вально следовать описанию алгоритма, но в то же время, при проектировании самого алгоритма надо представлять себе реали- зацию микроблоков. Реализация одних и тех же вычислений может быть существенно различной по объему аппаратуры. Например, вычисления в цикле потребуют реализации -

T- V A J 0 -T T- MUX L T RG 0 0 f A J V V B B f ,A J K K J J 1 L T -V- L - L K K J А L J K L реализация счетчика J не показанa 12 - Запишем этот фрагмент алгоритма иначе так, чтобы нужный бит извлекался за счет сдвига в регистре D. Тогда получим T A D -T T -T T- A J V RG RG 0 f J 0 B D A . L T K V V x Dn S W . B f ,D 0

L - -v-v L D,x x,D J J 1 L T -V- K K L J K Промежуточный регистр A введен для общности, если потребуется сохранить слово А чаще всего он и не нужен . Другой пример фрагмент алгоритма, реализующий регуляр- ную запись отдельных бит слова и его реализация имеют вид T -T-T B 0 a T T V W J 0 -A L T DC 0 V V -T-T B K L T W a f J -A K

B J a J J 1 . L T L -V- K K L J K Слово В нельзя реализовать в виде регистра, а только в виде отдельных триггеров. Можно формировать слово с использованием операции сдви- га при обязательном условии D K 0 , тогда алгоритм и его ре- ализация имеют вид - 13 - T D B V T T -T T J 0 RG RG L T - a V V Dk S W -v - -v - a f D,x a,D J J 1 L T -V- K K L J K B D L В этом случае, так же, как и в предыдущем, чаще всего не ну- жен

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

В основе перечисленных универсальных ОА лежит следующая структура г T SYN ACC T T - TT T RGF C RG ALU L DO L D L - T -T T P RG C W А C г -o-A A - -T - L 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 с началом следующего такта, т.е. на пе- реднем фронте сигнала. ВЗАИМОДЕЙСТВИЕ ОА и УА Для исключения гонок при взаимодействии ОА и УА будем проектировать УА как автомат Мура. Схема их взаимодействия может быть представлена в виде г -T T L CS RG CS - T b c L L A- L L CS - a ОА L УА РА -T T L- CS RG CS - L Y РВ г p y - L L - L L - Отметим, что

РА t f Y t зависит без сдвига от сигналов управления, PB t 1 F Y t зависит со сдвигом от сигналов управления, где РА и РВ - предикатные перемнные. Продолжительность такта работы схемы определяется наибо- лее длинными цепями между регистрами. Для данной схемы, кото- рую будем называть последовательной схемой взаимодействия, зададимся так чаще всего бывает , что такой критической цепью является цепь

CSy,CSa,CSp,RG . Поэтому длительность такта определяется Т ty ta tp trg, где tj- время установления соответствующего компонента цепи. Чтобы сократить длину этой цепи, применяют другой вари- ант взаимодействия автоматов - конвейерный - 15 - г -T T L CS RG CS - T b c FF L L A- L -T T L RG CS - a L A- L ОА L УА MK PA T -T T L CS CS RG -

РВ Y L г p y - L L - 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 1 1H CONST 0H X л L У этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов - 16 - D-триггера. Схема автомата вместе с цепями условной синхронизации выглядит следующим образом для

синхронизации по фронтам а -по переднему фронту, б - по заднему фронту SYN T 1 CC SYN T CC 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 T L Исполнитель этого алгоритма состоит только из ОА. На каждом шаге этого алгоритма изменяется вся память устройства, поэтому управление памятью не требуется, идентифицировать ша- ги этого алгоритма не надо. Например, инкрементор с одноразрядным входом и однораз- рядным выходом может быть реализацией следующих преобразова- ний p 1 V-V p , b a p L T L ОА, реализующий инкрементор в целом, будет следующим

T- a HS S b T- p начальное значен S T P - L SYN C - D L- L Конечно, эта реализация совпадает с реализацией алгоритма ав- томатного типа, если состояние р1 кодируется 1, а состояние р0 - 0. Этот пример показывает,что до начала вычислений может потребоваться начальная установка памяти. На самом деле это необходимо было уже в алгоритмах автоматного типа, так как код начального состояния требует предварительной установ- ки.

Ограничимся здесь обозначением этой проблемы, а решение ее, связанное прежде всего с корректной синхронизацией ус- тройства в первом такте его работы, рассмотрим ниже. При рассмотрении процедуры построения автомата Мура эк- вивалентного автомату Мили , не обсуждалась простая возмож- ность ее реализации и на структурном уровне. Например, только что рассмотренный автомат Мили может быть преобразован в эк- вивалентный автомат

Мура по одному из следующих вариантов -T-T t T- T- -T-T a T HS S - b a HS S - T - b C C C - TT-T p - TT-T p - T P - T P L L L L L L При таких структурных преобразованиях проще истолковы- вать алгоритмы как процедурные p 1 t 0 p 1 V-V V-V t a p ,b t p p , b a p L T L T L L БЛОК-ТЕКСТ. Способ описания автоматного алгоритма после некоторых дополнений может быть

использован и для описания алгоритмов в процедурной форме Блок-текст состоит из трех частей 1 - Описание переменных и начальных значений памяти. 2 - Описания функций и связей. Записываются любые функции и функциональные связи в том числе предикатные , не использу- ющие запоминания. Переменные из левой части операции присва- ивания таких функциональных описаний используются в блоках процедуры. 3 - Процедура, состоящая из блоков микроблоков операторных

и блоков переходов - операторные - в скобках вида перехода - в скобках вида и те, и другие блоки могут снабжаться метками, стоящими перед блоком. В блоках перехода используется оператор GO в одной из двух форм GO m - безусловный переход, GO P m0,m1,m2 условный переход. здесь m0,m1 метки блоков, P - предикатное значение,интерпретируемое оператором

GO как неотрицательное целое число, являющееся порядковым номе- ром метки в списке меток оператора GO. С этой метки должно быть продолжено выполнение алгоритма. Блоки условных перехо- дов эквивалентны предикатным вершинам блок-схемы алгоритма. На следующем более сложном примере демонстрируется пос- ледовательность синтеза операционного устройства. Пример. Вычислитель наибольшего общего делителя НОД двух натуральных чисел 8-разрядных .

1 Разработаем интерфейс вычислителя 8 T T I1 НОД 8 8 D I2 rI rO C L 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 L T -VVV- 0 rI 1 V rO 0 m2 А I1 B I2 L T VV m3 p,S A - B L T -V- m6 0 z S 0 rO 1 D A - L 0 V 0 1 p V V m4 x,B -A B m5 x,A A - B L T L T 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 4 Разработка функциональной схемы операционного автома- та. В ОА должны быть реализованы все переменные с памятью и без,а также вычислительные операции,используемые

в алгоритме. A г D - TT T C RG f1 A-B A I1 - f2 -A B S S 1 o z - B L - TT T C RG p B B I2 - TT-T C rO rI - L L Кроме того, в ОА необходимо реализовать все информацион- ные связи, соответствующие микрооперации коммутации, а также микрооперации запоминания загрузки, записи и обнуления. г A г D - TT T MUX C RG M2 8 1- cr SM 0 - I1 1 I1 A 1

А W - S o z LA -A - LA L umA uA uiA B - TT T MUX C RG M2 8 p p L 0 B I2 1 I2 C - TT-T А W - 1- T rO LA -A - LA L 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 - TT T MUX C RG M2 8 1- cr SM 0 - I1 1 I1 1

А W - S o z LA -A - LA L B - L - TT T MUX C RG M2 8 p p L 0 I2 1 I2 А W - C LA -A - LA L - TT-T L- 1- T rO o- R W L -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 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 - выходами. Микрооперация - двоеточие - означает запоминание изменение значения в памяти устройства. Переменная типа па- мять сохраняет свое значение между двумя очередными присва- иваниями. Микрооперации всегда входят в состав микрооператоров. МИКРООПЕРАТОР - набор взаимосвязанных микроопераций или одна микрооперация , выполняемых одновременно

и необходимых для получения одного или более значений. Например e,D R1 R2 c Фрагмент аппаратуры, реализующей этот микрооператор, мог бы быть, например, таким c MUX -T T T 0 MUX D L - 1 SM -T T А cr 0 RG S 1 L - R1 MUX А -T T L RG 0 I1 L - 1 MUX А e p 0 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 асинхронно, но в следющем такте. Всегда предполагается, что предикат вычисляется вместе в одном такте с тем микроблоком, за которым непосредственно следует его использование.Таким образом, здесь, также как и в микроблоке, используется старое значение памяти, существовав- шее перед входом в микроблок.

Это связано с особенностями взаимодействия ОА и УА. Например CT 0 CT 0 V V m1 CT 3 m1 CT 3 L T L T -V- -V- 0 0 CT 0 - CT 0 - 0 0 V V m2 m2 CT CT-1 CT CT-1 L T L T L V m3 L T L В первом случае цикл будет выполнен 4 раза во втором - если в микроблоке m3 нет операций, модифицирующих СТ 3 ра- за. Обратите внимание на начальное значение

СТ! МИКРОКОМАНДА - набор сигналов, поступающий из УА в ОА и интерпретируемый как управляющий,т.е. необходимый для выпол- нения всех микроопераций одного микроблока. Сигналы, входящие в микрокоманду, могут принимать участие в микрооперациях и в качестве информационных. Микрокомандой также иногда называют слово управляющей памяти обычно ПЗУ , являющееся частью УА. Для различения этих понятий слово управляющей памяти будем называть

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

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

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

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

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

сложно во времени невозможно также реализовать принципиально рекуррентные алгоритмы см например,алгоритм Евклида для нахождения НОД . Тем не менее, если формально алгоритм функционального типа может быть записан, то проектирование устройства надо начинать с записи именно такого алгоритма. Минимизация аппаратуры сложной КС с переходом на про- цедурный вариант реализации связан с экономией числа опера- ционных элементов, т.е. со слиянием некоторых из них в один функциональный модуль, выполняющий

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

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

- переменным алгоритма. Назовем такой граф сигнальным графом потоков данных . Заметим, что сигнальный граф всегда будет ациклическим. Минимальность времени вычислений сохранится, если совме- щать в один функциональный модуль операции, которые располо- жены на одном и том же пути в сигнальном графе, либо на аль- тернативных путях решения. МИНИМИЗАЦИЯ АППАРАТУРЫ Может оказаться, что на одном пути в сигнальном графе расположены операции,

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

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

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

Реализация одних и тех же вычислений может быть существенно различной по объему аппаратуры. Например, вычисления в цикле потребуют реализации -T- V A J 0 -T T- MUX L T RG 0 0 f A J V V B B f ,A J K K J J 1 L T -V- L - L K K J А L J K L реализация счетчика J не показанa . Запишем этот фрагмент алгоритма иначе так, чтобы нужный бит извлекался за счет сдвига

в регистре D. Тогда получим T A D -T T -T T- A J V RG RG 0 f J 0 B D A . L T K V V x Dn S W . B f ,D 0 L - -v-v L D,x x,D J J 1 L T -V- K K L J K Промежуточный регистр A введен для общности, если потребуется сохранить слово А чаще всего он и не нужен . Другой пример фрагмент алгоритма, реализующий регуляр- ную запись отдельных

бит слова и его реализация имеют вид T -T-T B 0 a T T V W J 0 -A L T DC 0 V V -T-T B K L T W a f J -A K B J a J J 1 . L T L -V- K K L J K Слово В нельзя реализовать в виде регистра, а только в виде отдельных триггеров. Можно формировать слово с использованием операции сдви- га при обязательном условии D K 0 , тогда алгоритм и его ре- ализация имеют вид

T D B V T T -T T J 0 RG RG L T - a V V Dk S W -v - -v - a f D,x a,D J J 1 L T -V- K K L J K B D L В этом случае, так же, как и в предыдущем, чаще всего не ну- жен промежуточный регистр В . УНИВЕРСАЛЬНЫЙ ОА Использование при проектировании универсальных ОА с за- ранее фиксированной и минимизированной структурой оправдано тем, что такие универсальные ОА изготавливаются промышлен- ностью в виде БИС большим тиражом и поэтому они сравнительно дешевы.

Такие универсальные ОА входят в микропроцессорные на- боры 582, 583, 584, 588, 589, 1800, 1804 и т.д которые на- зываются микропрограммируемыми, секционными, разрядно-модуль- ными. В основе перечисленных универсальных ОА лежит следующая структура г T SYN ACC T T - TT T RGF C RG ALU L DO L D L - T -T T P RG C W А C г -o-A A - -T - L 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 с началом следующего такта, т.е. на пе- реднем фронте сигнала. ВЗАИМОДЕЙСТВИЕ ОА и УА Для исключения гонок при взаимодействии ОА и УА будем проектировать УА как автомат Мура. Схема их взаимодействия может быть представлена в виде г -T T L CS RG CS - T b c L L A- L L CS - a ОА L УА

РА -T T L- CS RG CS - L Y РВ г p y - L L - L L - Отметим, что РА t f Y t зависит без сдвига от сигналов управления, PB t 1 F Y t зависит со сдвигом от сигналов управления, где РА и РВ - предикатные перемнные. Продолжительность такта работы схемы определяется наибо- лее длинными цепями между регистрами. Для данной схемы, кото- рую будем называть последовательной схемой взаимодействия,

зададимся так чаще всего бывает , что такой критической цепью является цепь CSy,CSa,CSp,RG . Поэтому длительность такта определяется Т ty ta tp trg, где tj- время установления соответствующего компонента цепи. Чтобы сократить длину этой цепи, применяют другой вари- ант взаимодействия автоматов - конвейерный г -T T L CS RG CS - T b c FF L L A- L -T T L RG CS - a

L A- L ОА L УА MK PA T -T T L CS CS RG - РВ Y L г p y - L L - 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 1 1H CONST 0H X л L У этого автомата простейшей является функция переходов, так как диаграмма автомата совпадает с диаграммой переходов

D-триггера. Схема автомата вместе с цепями условной синхронизации выглядит следующим образом для синхронизации по фронтам а -по переднему фронту, б - по заднему фронту SYN T 1 CC SYN T CC T- T- L- C T L L- C T L D D - o - o- -oR -oR H L- уст. нач. зн. H L- уст. нач. зн. Такая разница в цепях условной синхронизации, как уже объяс- нялось выше, определяется тем, что первый перепад сигнала

СС не должен быть рабочим. ЛИТЕРАТУРА 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 Укажем на некоторые особенности этого алгоритма

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

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

СХЕМА С АДРЕСНЫМ ПЗУ Начнем рассмотрение с управляющего автомата, структура которого совпадает с канонической структурой автомата Мура. -T T MUX q ROM RG ROM a- 0 S S Y b- 1 T г - А 2 C 1 LA L L H L - 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 можно расположить микрокоманду, после кото- рой безусловно выполняется начальная микрокоманда. q -T T MUX ROM

ROM Y RG Y a- 0 C S b- 1 - TT T T H г RG А S 2 1 C LA L - L L H L - 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 Конвейерный вариант г г A0 -T T A0 MUX ROM RG - A1 A1 L 0 A - L 1 Y Y MUX H a-

0 А H b- 1 LA L А C 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 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 - А L - LA L H C L - 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 Распределять микроинструкции по ячейкам памяти удобно в следующем порядке - связать с различными операторами условного перехода, кон- фликтующими между собой по адресации, различающиеся между со- бой старшие разряды адреса - распределить микроблоки по ячейкам памяти с учетом назнач- енных старших разрядов адреса и

входных значений - оставшимся нераспределенным микроблокам назначить произ- вольные свободные адреса. СХЕМА С СОКРАЩЕННЫМ ТАКТОМ Использование этой схемы позволяет при сохранении пре- имуществ последовательного варианта взаимодействия сократить наиболее длинные цепи, общие для ОА и УА, до длины цепей кон- вейерного варианта. T T г ROM 0 A Y H A e 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 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 2 m1 0 4 0 А 3 m3 0 0 1 LA L - Способ адресации, по существу, такой же, как и в преды- дущей схеме. Только в рассматриваемой схеме входной сигнал управляет выбором одного из двух блоков

ПЗУ можно интерпре- тировать этот сигнал как старший разряд адреса . СХЕМА С РЕГУЛЯРНОЙ АДРЕСАЦИЕЙ 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 L - В этой схеме при разветвлении процесса вычислений пара альтернативных адресов получается следующим образом один ад- рес всегда на единицу больше, чем текущий т.е. изменяется регулярным образом , второй

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

М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 1 e e А L - LA L MUX C 0- 0 - M2 a- 1 - b- 2 L А LA L L - СХЕМА С ЕСТЕСТВЕННОЙ АДРЕСАЦИЕЙ И СОВМЕЩЕННЫМ

НАЗНАЧЕНИЕМ РАЗРЯДОВ ЯЧЕЙКИ ПЗУ г C г - TT T H -T T г RG RG MUX ROM L INC 0 S H e L - L C -T T Y для RG Y RG - TT T A w c 0w-загрузка C RG -A L 1 k -T-T k 1w-нет загрузки А - T L - L-A L k MUX C L 1 - CC 0 0 - M2 a 1 SYN L b 2 L L А e L где CC - LA L синхронизация ОА 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 Вместе с этой схемой обычно используется условная син- хронизация, которая позволяет удлинить такт выполнения микро- команды в ОА на время выполнения микроинструкций адресации. SYN L L L L L k 0 0 0 1 1 CC L L L Y ФУНКЦИОНАЛЬНЫЙ ПЕРЕХОД. ПЕРЕХОД НА МИКРОПОДПРОГРАММУ С ВОЗВРАТОМ Функциональный переход

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

К механизму коммутации относят- ся, кроме аппаратуры, специальные разряды управляющей памяти и специальные микроинструкции. г C г - TT T H г RG MUX ROM F 0 L - -T T RG L 1 S H e C -T T Y для RG Y RG -T T A 0w-загрузка RG w c L INC T 2 -A 1w-нет загр. L C г - -T T k 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 k А e L- 1 -CC LA L L - SYN L Переход к микроподпрограмме с возвратом При реализации достаточно сложных вычислений удобно вос- пользоваться механизмом микроподпрограмм. Одна и та же микроподпрограмма может быть вызвана из разных точек вызывающих микропрограмм. Поэтому при вызове микроподпрограммы необходимо запомнить адрес, с тем, чтобы восстановить его при возвращении из микроподпрограммы. Чтобы запомнить и восстановить адреса возврата от вложенных вызо-

вов, используется безадресная память - стек stack . Принцип дисциплина работы стека описывается условием последний вошел - первым вышел Last In - First Out, LIFO . чтобы описать этот принцип будем считать, что слова, хранящи- еся в стеке, перенумерованы с помощью первых натуральных чи- сел 1,2, ,N. Слово с наибольшим номером называют вершиной стека.

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

циклов. Разряды с именем К определяют тип выполняемой микро- инструкции. В связи с тем, что теперь в схеме существует 4 источника адреса для управляющей памяти, возможны 4 типа бе- зусловных переходов, кроме того, возможны различные условные переходы в различных сочетаниях комбинирующие эти источники адреса и входные переменные. С помощью комбинационной схемы CS разряды микроинструкции

К преобразуются в сигналы управления стеком и мультиплексо- ром. УПРАВЛЕНИЕ С ПРЕДВОСХИЩЕНИЕМ В конвейерном варианте для команд переходов по предикат- ным переменным, зависящих без сдвига от сигналов управления, приходится добавлять еще один такт для того, чтобы увидеть значение переменной, по которой выполняется ветвление, и выб- рать нужную МКИ. Можно построить управляющий автомат, в котором для уско- рения выполнения программы выполняются

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

т.е. не синхронизируются ОА и RG МКИ. Микропрограмма будет такой же как и для последовательного варианта взаимодействия ОА и УА, но в МКИ добавляются два разряда F 1, если используется предвосхищение 0, если нет , P - наиболее вероятное значение переменной ветвления. Фрагмент схемы УА, обеспечивающий предвосхищение может быть таким

W -T T -VT q -A f t RG L MUX SS T t p L - T j L -VT P -T T p MUX ROM RG F f C L - A - L 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