andrey

Путь к Файлу: /Организация ЭВМ / Лекции ВМ-91 / Гончаров - Лекция №1.doc

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

2.6.7    Автомат Mealy

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

Пусть outj - Mealy составляющая вывода. Для каждого состояния z, в котором outj может быть активирован, есть булева функция fz,j такая, что

outj – активен в состоянии z     <->     fz,j(in) = 1.

 

Если Mealy вывод outj никогда не активируется в состоянии z, тогда fz,j Гончаров - Лекция №1 0. Если Mealy вывод outj всегда включается в состоянии z, тогда fz,j Гончаров - Лекция №1 1. Для любого Mealy вывода outj мы определяем набор состояний

 

Z'j = {z | fz,j =/= 0}

где outj возможно может быть включен.

Пусть F(z , j) – дизьюктивная нормальная форма fz,j . С помощью F(z , j) мы можем представить себе Mealy вывод outj следующим способом. Пусть z – состояние, представленное в виде прямоугольника - в Z'j ; тогда мы пишем внутри прямоугольника:

outj если F(z , i).

На рисунке 2.42, мы увеличили пример автомата новым выводом Mealy out[3].

Гончаров - Лекция №1

- ряд всех сложных одночленов, встречающихся в дизьюктивных нормальных формах F(z, j). Тогда Mealy выводы outj могут вычисляться за два шага:

Пусть MF(z ,  j) – ряд одночленов в F(z , j), и пусть

1. вычисление всех одночленов т € M U  MF в схеме CM (одночлены M используются для вычисления следующего состояния),

2. для всех Mealy выводов outj, схема O вычисляет бит

 

Гончаров - Лекция №1

 


Схема CM вычисляет одночлены т € M U MF тем же самым способом, что и схема следующих состояний из раздела 2.6.4, т.е., она сперва инвертирует все входы ini а затем вычисляет каждый одночлен т сбалансированным деревом AND-gates. Пусть lfmax и lmax означают максимальную длину всех одночленов в MF и M, соответственно, и пусть lsum означает накопленную длину всех сложных одночленов. Тогда схема CM может генерировать одночлены M' = MF U M со следующей стоимостью и задержкой:

 

ccm     =     σ • Cinv + (lsum - #M' ) * Cand

dcm (MF)    =    dinv + [log lfmax] * Dand dcm (m)    =   Dinv + [log lmax] * Dand .

 

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

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

 

Гончаров - Лекция №1

Число одночленов, требуемое для вычисления Mealy выходов оutj равно

Гончаров - Лекция №1

По аналогии с частотой выводов Мура, мы часто ссылаемся на vj как частоту Mealy выводов outj . Пусть vmax и vsum означают максимальную и накопленную частоту всех выходов оut[ γ - 1 : 0]. Стоимость и задержка схемы О, которая генерирует выходы из сигналов т € MF и S[k - 1 ; 0] может быть оценена как:

C0   =   vsum * (Cand + Cor) - γ*Car d0   =   Dand + [log vmax] * Dor .

Автомат Mealy вычисляет следующее состояние тем же способом, как и автомат Мура, т.е., как представлено в разделе 2.6.4. Единственное различие в том, что

 

Гончаров - Лекция №1

Рисунок 2.43 Реализация автомата Mealy

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

cns   =   ccm + ccn

dns   =   dcm(m) + dcn .

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

 

СMealy      =     Cff(k) + C0 + CNS + Czero(k - 1) + Cmux(k) + Cor

A(out)   =        A(in)+DCM(MF)+D0                                          *

ТMealy   =          max{A(clr , ce) + Dor , A(in) + DNS + Dzero(k - 1)}

                                                           + Dmux + Δ  .

 

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

 

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

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

1. Допустимы не все возможные выходы out € {0,1 }γ; для некоторых значений 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) Гончаров - Лекция №1 {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) имеют накопленную задержку

Гончаров - Лекция №1

Для автомата Мура, такое разделение путей данных и автомата необязательно, так как управляющие сигналы не зависят от текущего состояния. Однако, в автомате 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 схемы следуищих состояний

 

2.7    Выборочные ссылки и дальнейшее чтение

Формальная модель аппаратуры, используемая в этой книге, из [MP95]. Расширенное использование рекурсивных определений в конструкции переключающих (switching) схем – самое общее из области Сложных Булевых Функций; стандартное руководство [Weg87]. Описание Booth recoding на соответствующем уровне детализации из [AТ97] а анализ Booth recoding из [PS98]. Стандартное руководство по компьютерной арифметике - [Kor93, Omo94]. Ранние тексты по компьютерной арифметике с полными доказательствами правильности - [Spa76].


2.8    Упражнения

 

Упражнение 2.1 Пусть т = [n / 2] для любого n > 1. Старшие биты суммы n-битного инкрементера со входами a[n - 1:0], cin и выходом s[n : 0] могут быть выражены как

 

Гончаров - Лекция №1

где cm-1 означает перенос из позиции т - 1 в позицию m. Это предлагается для схемы инкрементера простейшей конструкции на рисунке 2.15; the original problem is reduced to only two half-sized problems. Примените эту конструкцию рекурсивно и получите формулы стоимости и задержки полученной схемы инкрементера CSI .

Упражнение 2.2 Получите формулы стоимости и задержки (n,m)-multiplier (умножителя), который сконструирован в соответствии со школьным методом, используйте сумматоры с цепью переноса, как строительные блоки.        

Упражнение 2.3 В разделе 2.5.4 мы конструировали и анализировали складывающие деревья T(m) для (n.m)-multipliers без Booth recoding. Конструкция была ограничена т удовлетворяющими условиями

3/4 * M <= т <= M    при    M = 2[log m].

Упражнение имеет дело с конструированием дерева T(m) для остальных случаев, т.е., для M/2 < m < 3/4 * M. Нижняя часть дерева – все еще полностью регулярное и сбалансированное 4/2-tree T(M/4) с множеством M/4 пар входов и множеством M/8 4/2-adders вместо листьев. На верхнем уровне, мы теперь имеем множество a 3/2-adders и множество M/4 - a пар входов которые непосредственно питают 4/2-tree T(M/4). Здесь a – решение уравнения

 


Зa + 2 * (М/4-a) = m,

следовательно

a = m - M/2.

Для i = 0,1,..., частичные результаты Si,1 вводятся в дерево справа на лево и на верхнем уровне дерева 3/2-adders размещаются на правосторонней области.

1. Определите число избыточных сумматоров в дереве T(m) и получите формулы для стоимости и задержки.

2. Booth умножитель из раздела 2.5.5 использует модифицированное складывающее дерево T(tn) для суммирования Booth recoded частичных результатов. Расширьте формулы стоимости и задержки для случая M'/2 < m' < 3/4 * M'.

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

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

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

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

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

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



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

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

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