andrey

Путь к Файлу: /Организация ЭВМ / Лекции ВМ-91 / Глава 2_6_Управляющий автомат (Петренко Чех).doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   andrey
Добавлен:   13.01.2015
Размер:   4.0 МБ
СКАЧАТЬ

2.6 Управляющий автомат

 

2.6.1 Ограниченное состояние преобразователей

         Ограниченное состояние преобразователей (датчиков, приемников) это ограниченный автомат, который производит выходное значение при каждом следующем шаге (переходе).  Формально, ограниченное состояние преобразователя точно определяется  6-ю параметрами ( Z, In, Out, z0, δ, η), где Z – ограниченное число состояний;  z0 Î Z и называется начальным состоянием. In это ограниченный набор входных воздействий (символов, знаков), Out это ограниченный набор выходных значений,  δ : Z ´ In® Z – функция перехода, а      η : Z ´ In® Out функция выхода.

         Такой автомат работает последовательно шаг за шагом, подчиняясь следующим правилам :

         · Старт автомата начинается из вершины  z0.

         · Если автомат находится в состоянии z и на него воздействует входное значение in, то он вырабатывает выходное значение  (определяемое функцией)       η (z, in) и переходит в состояние (определяемое функцией)  δ ( z, in).

 

Если выходная функция не зависит от входных воздействий in, то есть если она может быть записана как  η : Z ® Out, то такой автомат называется автоматом Мура. В противном случае автоматом Мили.

         Очевидно, что вход автомата, управляющего некоторыми  частями компьютера (или вычислительного устройства), представляет собой конечное число s входных линий in[s-1 : 0], и будет выдавать значения на конечном числе g выходных линий out[g-1 : 0]. Условно у нас есть In = {0,1}s и Out = {0,1}g.

         Обычно, на практике автомат представляют, как показано на рис. 2.39, на котором приведен пример автомата Мура с тремя состояниями z0, z1 и z2, с набором входных значений In = {0,1}2 и набором выходных значений Out = {0,1}3. Автомат представлен в виде (направленного) графа (V,E) c обозначенными (нумерованными) ребрами и вершинами.

         Набор вершин V графа - это состояния автомата.  Изображаются с помощью прямоугольников, где начальное состояние – прямоугольник нарисованный двойной линией. Для любой пары вершин (z’, z), в наборе ребер Е (дуг) есть ребро выходящее из z’ в z, если δ (z’, in) =  z какого-то входного значения in, то есть если возможен переход из состояния z’ в состояние z. Ребро (z’, z) отмечено всеми возможными входными значениями, при которых автомат из состояния z’ переходит в состояние z. Для автомата Мура, внутри прямоугольных вершин  записываются выходные сигналы которые активируются при переходе автомата в эту вершину (или состояние).

         Преобразователи играют важную роль в управлении вычислительными устройствами. Поэтому, мы точно узнаем две важных характеристики; их цену и задержку, которая может быть легко  определена если автомат представлен в виде графа. Для более детального рассмотрения смотрите пример [MP95].

 

 

 

 

 

2.6.2 Кодирование состояний

         Допустим k = #Z это число состояний автомата. Тогда состояния могут быть пронумерованы от 0 до k-1, и можно переименовать состояния числами от 0 до k-1:    Z = {0, …, k-1}.

         Текущее состояние z всегда кодируется в регистре выходов S[k-1 : 0] и удовлетворяет условию  Глава 2_6_Управляющий автомат (Петренко Чех) для всех i. Это значит, что если автомат в i-ом состоянии, разряд Si включен, а все остальные разряды Sj для которых j ¹ i выключены. Начальному состоянию всегда присваивается нулевой номер. Очевидно что цена сохранения состояния будет k×Cff .

 

2.6.3 Образование выходных значений

            Для каждого выходного сигнала out Î Out, определен набор состояний

Zi = {z Î Z | outi активных в состоянии z}, в которых он вырабатывается. Тогда сигнал outi можно приблизительно вычислить так outj  = Глава 2_6_Управляющий автомат (Петренко Чех).

Часто можно обращаться к основанию νj = #Zj , как к частоте выходных сигналов outj; νmax и νsum обозначают максимум и сумму всех оснований νj: νmax =  max { νj |  0 ≤ j ≤ g }, νsum =Глава 2_6_Управляющий автомат (Петренко Чех).

В выше приведенном примере, подмножества Z0 = {z1, z2}, Z1 = {z0, z2}, Z2 = {z1}, и 2 параметра имеют значение νmax = 2 и νsum = 5.

         Каждый выходной сигнал outj может появится от только от νj-входного «дерева ИЛИ» с ценой (νj-1)۰Сor и задержкой [log νj]۰Dor. Таким образом в результате полного обхода (круга, цепочки) О появляются все выходные сигналы со следующими ценами и задержками:  Со = Глава 2_6_Управляющий автомат (Петренко Чех)= ( νsum - g)۰ Cor  ,

Do =  max { [log νj] | 1 ≤ j ≤ g }۰ Dor = [log νj] ۰ Dor .

 

2.6.4 Вычисление следующего состояния

         Для каждой дуги (z, z’) Î Е, от функции перехода δ, мы получим логическую функцию δz, z точно определяющую то входное значение в результате которого произойдет переход из состояния  z в состояние z’:

δz, z’ (in[s-1 : 0] )=1 ↔ δ(z, in[s-1 : 0] )= z’ .

         Пусть D(z, z’) дизъюнктивная нормальная форма δz, z. Если переход из z в z’ имеет место для всех входных in, то δz, z ≡ 1 и дизъюнктивная нормальная форма δz, z будет состоять из пустого одночлена m=1. Автомат на рис. 2.39 включает следующие дизъюнктивные нормальные формы :

            D(z0, z1) = Глава 2_6_Управляющий автомат (Петренко Чех), D(z0, z2) = Глава 2_6_Управляющий автомат (Петренко Чех), D(z2, z0) = 1, D(z1, z1) = Глава 2_6_Управляющий автомат (Петренко Чех),

  D(z1, z2) = Глава 2_6_Управляющий автомат (Петренко Чех).

 

 

 

 

Глава 2_6_Управляющий автомат (Петренко Чех)

         Пусть М(z, z’) набор одночленов в D(z, z’) и пусть  М = Глава 2_6_Управляющий автомат (Петренко Чех) набор всех непустых одночленов встречающихся  в дизъюнктивных формах     D(z, z’). Следующий вектор состояния может быть вычислен за три шага:

1. находим Глава 2_6_Управляющий автомат (Петренко Чех) для каждого входного сигнала inj,

2. вычисляем все одночлены mÎ M,

3. затем вычисляем для всех z между 1 и k-1 бит

N[z] = V(z’, z)ÎE S z’ ٨ VmÎM(z’, z) m =

        = V(z’, z)ÎE VmÎM(z’, z) (S z’ ٨ m).

Вершина, которую мы еще не вычислили N[0]. Для каждого одночлена m, его длина l(m) определяет число символьных констант в m; lmax и lsum определяют максимум и сумму всех l(m):  lmax = max{ l(m)| mÎ M},  lsum = Глава 2_6_Управляющий автомат (Петренко Чех).

Вычисление одночленов сделает с ценой и задержкой следующее:

         CCM = σCin ν + (lsum - #M)Cand ;   DCM = Din ν + [log lmax]Dand .

    Для каждой вершины z, пусть

                            fanin(z) = Глава 2_6_Управляющий автомат (Петренко Чех)

                            faninmax = max { fanin(z) | 1 ≤ z ≤ k-1}

                            faninsum = Глава 2_6_Управляющий автомат (Петренко Чех),

сигнал следующего состояния N[k-1: 1] может вырабатываться со следующей ценой и задержкой:   CCN = faninsum(Cand + Cor) – (k-1)Cor

                DCN = [log(faninmax)]Dor +Dand .

Таким образом, цепь NS вычисляет значения сигналов следующего состояния, отдельно для каждой линии из состояния разрядов S [k-1 : 0] и входных значений in[s-1 : 0], цена и задержка будет CNS = CCM  + CCN ,  DNS = DCM  + DCN .

 

 

 

         Таблица 2.7 суммирует все параметры которые определяются спецификой автомата в порядке определения цены и задержки по двум цепочкам O и NS.

Параметр

Значение

s

# входы inj автомата

γ

# выходные сигналы outj автомата

k

# состояния автомата

νmax, νsum

максимальна/ суммарная частота всех выходов

#M

# одночлен m Î M (непустой)

lmax, lsum

максимальная/ суммарная длина всех m Î MSz

fanmax, fansum

максимальная/ суммарная fanin состояний z ≠ z0

 

2.6.5 Автомат Мура

 

Глава 2_6_Управляющий автомат (Петренко Чех)

 

         Рисунок 2.40 показывает прямую реализацию автомата Мура с “clock” разрешающим сигналом ce и сигналом сброса (сигналом очистки) clr. Автомат “is clocked” когда хотя бы один из сигналов ce и clr активен. При старте вычислений, сигнал сброса (очистки) clr активен. Это запускает модель 0k-11, т. е. код инициализации начального состояния 0 в регистр S. До тех пор пока не подается сигнал clr, следующее состояние N вычисляется цепочкой NS и блоком проверки нуля. Если нет сигналов следующего состояния N[k-1 : 1], то активируется выход блока проверки нуля и включается сигнал состояния N[0].

         Эта конструкция обладает большим преимуществом, потому что она работает даже если функция перехода полностью точно не определена, т. е. если δ(z,in) не определена для некоторых состояний z и входных in. Это происходит в случае если входные in коды инструкция и вычислительное устройство управляется попытками выполнить неопределенную (называемую незаконной) инструкцию.

В автомате Мура на рис. 2.39, функция перехода не определена для z1 и      in =(10). Рассмотрим случай, что автомат в состоянии z1 и на входе (10). Если все следующие сигналы состояния, включая сигнал N[0] вычисляются согласно уравнению (2.5) предыдущего раздела, тогда следующее состояние будет 0k. Таким образом, автомат зависает и может быть перезапущен только включением сигнала «сброс» clr. Тем не  менее, в конструкции представленной здесь, автомат самостоятельно падает назад в начальное состояние. Таким образом, переход δ(z1,10) = z0 косвенно определен в этом автомате.

Пусть A(in) и A(clr, ce) обозначают накапливаемую задержку входных сигналов и сигналов clr и ce. Цена, задержка и циклическое время этой реализации, тогда могут быть выражены как

CMoore = Cff(k) + CO + CNS + Czero(k-1) + Cmux(k) + Cor

A(out) = DO

TMoore = max {A(clr, ce) + Dor, A(in) + DNS + Dzero(k-1)} + Dmux + Δ.

 

2.6.6 Предвычисление управляющих сигналов

 

Глава 2_6_Управляющий автомат (Петренко Чех)

 

            В предыдущей конструкции автомата Мура требовалось время DO с того момента как переключатся регистры, до того как выходные сигналы станут действительными. Поэтому управляющие сигналы, в конструкции показанной на рис. 2.41, заранее вычисляются и включаются в отдельном регистре Rout. Это увеличивает время полного цикла автомата DO, но выходные сигналы out[g-1 : 0] действительны без дополнительной задержки. Цена, задержка и время цикла автомата тогда будет:

CpMoore = Cff(k) + CO + CNS + Czero(k-1) + Cmux(k) + Cff(g) + Cor

A(out) = 0

TpMoore = max {A(clr, ce) + Dor, A(in) + DNS + Dzero(k-1)} + Dmux + DO + Δ.

         Это будет наш вариант конструкции автомата Мура. Вариант не вполне очевидный. Для формальной оценки разных реализаций управляющего автомата, смотрите [MP95].

 

2.6.7 Автомат Мили

Рассмотрим автомат Мили с входных сигналов in[s-1:0] и выходных сигналов out[g-1:0]. В общем не все выходные составляющие out[j] зависят от двух текущих значений: от состояния и входных сигналов in[s-1:0]. Назовем  составляющей Мили, если она зависит от текущего состояния и входного значения; иначе назовем out[j] составляющей Мура.

         Пусть outj будет составляющей Мили на выходе. То для каждого состояния z в котором может появится outj, есть логическая функция fz,j такая, что outj  появляется в состоянии z↔ fz,j(in) = 1. Если составляющая Мили никогда не появляется в состоянии z, то fz,j(in) ≡ 0. Если составляющая Мили outj всегда появляется на в состоянии z, тогда fz,j(in) ≡ 1. Для любой выходной составляющей Мили определяем набор состояний Zj’ = {z | fz,j(in) ≠ 0}, где outj может по возможности включиться.

         Пусть F(z, j) дизъюнктивная нормальная форма fz,j. С помощью F(z, j) мы можем визуализировать выходы Мили outj следующим образом. Пусть z состояние изображенное в виде прямоугольника - в Zj’, тода запишем внутри прямоугольника outj если  F(z, j). На рис. 2.42 дополненный пример автомата с новыми выходами Мили out[3].

 

Глава 2_6_Управляющий автомат (Петренко Чех)

 

         Пусть MF(z, j) набор одночленов в F(z, j) и пусть MF = Глава 2_6_Управляющий автомат (Петренко Чех) будет набором всех непустых одночленов встречающихся в дизъюнктивной нормальной форме F(z, j). Тогда выходы Мили могут быть вычислены за два шага:

         1. Вычисление всех одночленов mÎM Глава 2_6_Управляющий автомат (Петренко Чех)MF в цепочке CM (одночлены из M используются для вычисления следующего состояния),

         2. И для любого выхода Мили outj, цепочка О вычисляет бит

outj = Глава 2_6_Управляющий автомат (Петренко Чех).

         Цепочка CM вычисляет одночлены mÎM Глава 2_6_Управляющий автомат (Петренко Чех)MF так же, как цепочка из подраздела 2.6.4 следующее состояние, т. е. их первые инверты все входы ini и тогда каждый одночлен m вычисляется по сбалансированному дереву со входами «И». Пусть lfmax и lmax определяют max длину всех одночленов в MF и M, собственно, и пусть lsum определяет суммарную длину всех непустых одночленов. Цепочка CM может тогда генерировать одночлены M' = M Глава 2_6_Управляющий автомат (Петренко Чех)MF со следующей ценой и задержкой: 

                   CCM = σ۰Cinν+(lsum - #M’) ۰Cand

                   DCM(MF) = Dinν + [log lfmax]۰ Dand

                   DCM(M) = Dinν + [log lmax]۰ Dand.

Цепочка CM часть цепочки NS которая выполняет функцию перехода в автомате.

         Так как составляющие выхода Мура по-прежнему вычисляются как в автомате Мура, то удерживается

                            Глава 2_6_Управляющий автомат (Петренко Чех)

Число одночленов нужных для вычисления выходов Мили outj равно  

νj =Глава 2_6_Управляющий автомат (Петренко Чех)

По аналогии частоты повторения выходов Мура, часто будем ссылаться на νj как на частоту повторений выходов Мили outj. Пусть νmax и νsum определяют максимальную и суммарную частоту всех выходов out[g-1 : 0]. Цена и задержка цепочки О которая генерирует выходы из сигналов mÎ MF и S [k-1 : 0] может быть оценена как:

                   C= νsum۰(Cand + Cor) - g۰Cor

                   DO  = Dand + [log νmax]۰Dor .

Автомат Мили вычисляет следующее состояние тем же образом что и автомат Мура, т. е. как описано в части 2.6.4. Единственная разница в том что в автомате Мили, цепочка CM генерирует одночлены требуемые функцией перехода также как если они требуются функцией выхода. Таким образом цена и задержка следующего состояния в цепочке NS может теперь быть выражена

CNS = CCM  + CCN ,  DNS = DCM(M) + DCN .

         Пусть A(in) и A(clr, ce) означают накопленную задержку входных сигналов in и сигналов clr и ce. Автомат Мили (рис. 2.43) тогда может быть реализован со следующей ценой и задержкой:

         CMealy = Cff(k) + CO + CNS + Czero(k-1) + Cmux(k) + Cor

A(out) = A(in) + DCM(MF) + DO

TMealy = max {A(clr, ce) + Dor, A(in) + DNS + Dzero(k-1)} + Dmux + Δ.

 

Глава 2_6_Управляющий автомат (Петренко Чех)

 

 

 

 

 

 

 

 

2.6.8 Взаимодействие с линиями данных

         В процессоре все построено по этому шаблону, состоит из управляющего автомата и линий данных ( т. е. остального железа). По такому сценарию, входы автомата in кодируют обычно операцию которую нужно выполнить; они обеспечиваются по линиям данных DP. Выходы out автомата управляют линиями данных; эти управляющие сигналы по меньшей мере включают все clock сигналы активации, выходные сигналы включения, и сигналы записи компонент (составляющих) в DP.

         Взаимодействие между управляющим автоматом и линиями данных должно быть тщательно определено по двум причинам:

         1. Не все из возможных выходов outÎ{0,1}g допустимы; для некоторых значений out, функциональность линий данных и всего аппаратного обеспечения может быть не определена. Для примера, если несколько буферов с третьим состоянием соединяются с одной шиной, самое большее один буфер может быть включен для предотвращения конфликтов при обращении к шине.

2. Сигналы in, обеспечиваемые путями данных, обычно зависят от текущих сигналов управления out; с другой стороны, выход out автомата может зависеть от текущего in. Таким образом, после синхронизации, аппаратура не всегда снова входит в стабильное состояние, т.е., некоторые управляющие сигналы могут быть нестабильными. Однако, стабильность управляющих сигналов критична для определения поведения конструкций.

Допустимые управляющие сигналы

Функциональность комбинационных схем хорошо определена [Weg87]. Однако, структура аппаратных средств процессора H более сложна; схемы также включают триггеры, регистры, RAM, буферы с тремя состояниями. Эти компоненты требуют управляющих сигналов, которые предоставляет управляющий автомат.

Управляющие сигналы определены для каждого значения out € Out модифицированных аппаратных средств H(out). В модифицированных аппаратных средствах буфер с третьим состоянием с активным сигналом разрешения en = 1 работает подобно клапану, который пропускает входные сигналы на свой выход. Буфер с тремя состояниями с неактивным сигналом разрешения en = 0 работает подобно отсутствию соединения между входом и его выходом. Как следствие, составляющие и комбинационные схемы H (out) могут иметь открытые входы с неопределенным входным значением.

Значение out € Out управляющих сигналов называется допустимым, если выполняются следующие условия:

 

• Буферы с тремя состояниями используются в путях данных, но не в управляющем автомате.

• В модифицированных аппаратных средствах H(out) комбинационные схемы и основные компоненты могут иметь открытые входы с неопределенным значением. Несмотря на эти открытые входы, каждый вход регистра с активным сигналом разрешения синхронизации или RAM с активным сигналом записи, имеет значение (0,1}.

• В модифицированных аппаратных средствах H (out) любая передача между регистром и RAM – одного из четырех типов, изображенных на рисунке 2.3.

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

Стабильные управляющие сигналы

Для сохранения хорошо определенными функциональных возможностей всех аппаратных средств (управляющий автомат и пути данных DP), пути данных и схема О разделяются на p частей каждое, DP(1),...,DP(p) и O(1),..., O(p) так, что

• Схема O(i) получает входы in(i) Глава 2_6_Управляющий автомат (Петренко Чех) {in0 ,..., inσ-1}; эти входы напрямую берутся из регистров или они предоставляются схемами DP(j), с j<i .

• Схема O(i) генерирует выходные сигналы out(i) С (out0 ,..., outγ-1}. Эти сигналы управляют только путями данных DP(i).

Схема NS может получать входы из любой части путей данных и из любой выходной схемы O(i).

Все аппаратное обеспечение, которое использует общий сигнал синхронизации, работает в цикле. Пусть управляющий автомат генерирует только допустимые управляющие сигналы out. Тогда просто следует индукцией по p, что управляющие сигналы out(i) снова стабилизируются после синхронизации аппаратуры, и что функциональность аппаратных средств хорошо определена (для каждого такта). Управляющие сигналы out(i) имеют накопленную задержку

Глава 2_6_Управляющий автомат (Петренко Чех)

Для автомата Мура, такое разделение путей данных и автомата необязательно, так как управляющие сигналы не зависят от текущего состояния. Однако, в автомате Mealy, разделение необходимо. Сигналы out(1) тогда формируются составляющими выхода Мура.

 

Параметры автомата Mealy

Выходные сигналы автомата Mealy имеют тенденцию быть на временно критичном пути. Таким образом, это необходимо для хорошей оценки производительности, чтобы обеспечить накопленную задержку каждой выходной схемы O(i) соответственно накопленной задержкой каждого подмножества out(i) выходных сигналов:

AO(i) = A(out(i)).

Пусть vmax(i) означает максимальную частоту всех выходных сигналов в out(i), и пусть lfmax(i) означает максимальную длину одночленов в дизьюктивных нормальных формах F(z , j), с j € out(i). Таким образом:

А(out(0)     =       A(in(i)) + DCM(MF , i) + DO(i)

DO(i)    =       Dand +  [log vmax(i)] * Dar

DCM(MF , i) =       Dinv + [log lfmax(i)] * Dand

Таблица 2.8 обобщает все параметры, которые могут быть определены из спецификации автомата, для определения стоимости и задержки автомата Mealy.


Таблица 2.8 Параметры управляющего автомата Mealy с p выходными уровнями O(1) ,..., O(p).

Символ

Значение

 

σ

 

# входные сигналы inj автомата

 

γ

 

# выходные сигналы outj автомата

 

k

 

# состояния автомата

 

fansum

 

накопленный  коэф. разветвления по входу всех состояний z =/= z0

 

fanmax

 

максимальный коэф. разветвления по входу всех состояний z =/= z0

 

#M'

 

# одночлены т € M' = MF U M автомата

 

lsum

 

Накопленная длина всех одночленов т € M'

 

lfmax(i) , lmax

 

Максимальная длина одночленов выходного уровня O(i) и одночленов т € M схемы следующих состояний

 

vsum

 

Накопленная частота всех управляющих сигналов

 

vmax(i)

 

Максимальная частота сигналов out(i) уровня O(i)

 

Aclr , ce

 

Накопленная задержка сигналов очистки и синхронизации

 

Ain(i) ,

Ain

 

Накопленная задержка входов in(i) схемы O(i) и входов in схемы следуищих состояний

 

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика