В А Саломатин, С А Цололо - Оптимизация схемы мпа мура в составе системы на кристалле - страница 1

Страницы:
1  2  3 

Оптимизация схемы МПА Мура в составе системы на кристалле

 

В.А. Саломатин, С.А. Цололо

 

Донецкий национальный технический университет s.solos@gmail.com

 

 

Abstract

 

Salomatin V.A., Tsololo S.A. Optimization of Moore FSM as a part of "system-on-chip". Method of Moore's circuit optimization is proposed. Method based on features of CPLD architecture and Moore's FSM model. The carried out researches have shown that the method reduces hardware expenses up to 30%.

 

 

1. Введение

 

Важным блоком любой цифровой системы является устройство управления (УУ), которое координирует взаимодействие всех блоков системы [1, 2]. На практике УУ часто реализуется с использованием модели микропрограммного автомата (МПА) Мура [3]. В настоящие время прогресс в области микроэлектроники привел к появлению «систем-на-кристалле» (SoC, system-on-chip) [4], функциональные возможности которых достаточны для реализации сложной цифровой системе на одном кристалле [5]. В SoC произвольная логика может реализовываться с использованием макроячеек PAL (programmable array logic), а табличные функции реализуются с помощью блоков памяти (EMB, embedded memory blocks) [6]. Одной из актуальных задач в этом случае является уменьшение аппаратурных затрат в схеме МПА [1]. Решение этой задачи позволяет уменьшить площадь кристалла, занимаемую схемой УУ, при этом возможно увеличение функциональных возможностей системы в рамках одного кристалла [6]. Для решения этой задачи необходимо учитывать как особенности элементного базиса, так и особенности модели МПА. Особенностями PAL является большой коэффициент объединения по входу, который достигает нескольких десятков в реальных CPLD (complex programmable logic devices) [7], и ограниченное число термов (элементарных конъюнкций) в одной макроячейке (порядка восьми) [1]. Особенностями МПА Мура является наличие псевдоэквивалентных состояний [8] и регулярный характер системы микроопераций, что позволяет   реализовать    ее    на   EMB    [6].    Целью исследований,представленных в этой работе, является возможность оптимизации комбинационной схемы автомата Мура за счет использования нескольких источников кода текущего состояния автомата, что возможно благодаря особенностям PAL. Задачей, решаемой в работе, является разработка формализованного метода синтеза микропрограммного автомата Мура, позволяющего оптимизировать число макроячеек PAL в схеме формирования функций возбуждения триггеров памяти автомата. При этом алгоритм управления цифровой системы задан в виде граф-схемы алгоритма (ГСА) [3].

 

 

2. Особенности реализации автомата Мура

 

Пусть алгоритм управления цифровой системы представлен ГСА Г = Г(В,Е),    где     B = {b0,bE} u E1 u E2     —    множество вершин,

Е = {< bq,bt >| bq,bt є В} - множество дуг. Здесь b0- начальная вершина

ГСА, bE- конечная вершина ГСА, Е1 - множество операторных вершин,

Е2 - множество условных вершин. В вершинах bq є E1 записываются

наборы микроопераций   Y(bq) с: Y, где   Y = {y1,...,yN}  - множество

микроопераций операционного автомата цифровой системы [9]. В вершинах bq є E2 записываются элементы множества логических условий

X = {x1,...,yL}. Начальная и конечная вершины ГСА соответствуют состоянию a1 є A = {a1,...,aM}, где A - множество состояний автомата Мура, а каждая вершина bq є E1 соответствует одному из элементов

множества A[3]. Логическая схема МПА Мура задается системой уравнений

Ф = Ф(Т,Х), (1) Y = Y(T), (2) где Т = {T1,...,TR} - множество внутренних переменных, кодирующих состояния am є A, R =] log2 M[; Ф = {D1DR } - множество функций возбуждения памяти состояний. Системы (1)-(2) формируются на основе прямой структурной таблицы (ПСТ) со столбцами:   am   - текущее

состояние; K(am)- код состояния am є A; as - состояние перехода; K(as) - код состояния as є A; Xh- конъюнкция некоторых элементов множества X (или их отрицаний), определяющая переход < am,as >; Фh -набор функций возбуждения памяти МПА, принимающих единичное состояние для переключения памяти из K(am) в K(as); h = 1,...,Н1(Г) -

номер строки таблицы. В столбце am записывается набор микроопераций

Y(am) <z Y, формируемых в состоянии am є A. Естественно, что Y(am) = Y(bq), где вершина bq є E1 отмечена состоянием am є A.

Как правило, число переходов Н1 (Г) больше числа переходов Н2 (Г)

эквивалентного автомата Мили [3]. Это приводит к увеличению числа PAL в схеме МПА Мура по сравнению с этим показателем эквивалентного автомата Мили. Параметр Н1(Г) можно уменьшить, благодаря наличию псевдоэквивалентных состояний (ПЭС) МПА Мура [10]. Состояния am, as є A называется ПЭС, если выходы соответствующих им вершин соединены с выходом одной и той же вершины ГСА Г. Пусть ПA = {B1,...,BI}- разбиение множества А на классы ПЭС (I < M). Поставим в соответствие классу Bi єП A двоичный код K(Bi) разрядности R1 =] log2 I[ и используем переменные Tr є т для такого кодирования, где т = R1. В этом случае МПА Мура представляется в виде структуры U1 (рис. 1)


 

 

 

 

 

 

 

 

т


Ф


 

 

RG

Т

CFMO

Y

 

 

 

 

 

-------- p

Start

 

 

 

 

Clock

TC

 

 

 

 

Рисунок 1 - Структурная схема МПА Мура U1

 

В МПА U1 схема СС формирует функции

Ф = Ф(т,Х), (3) а схема формирования микроопераций CFMO реализует систему (2). Регистр RG представляет собой память состояний, по сигналу Start в RG заносится нулевой код начального состояния a1 є A , по сигналу Clock

происходит смена кодов в регистре. Преобразователь кодов состояний TC реализует систему функций

т = т(т), (4) при этом код K(Bi) формируется на основе кода K(am) , где am є Bi.

В [10] показано, что для МПА U1 число переходов уменьшается до Н2(Г). Недостатком МПА U1 является наличие схемы TC, которая требует дополнительных ресурсов. Отметим, что схема СС реализуется на PAL, асхемы TC и CFMO - на блоках памяти EMB. В настоящей работе предлагается метод синтеза МПА Мура, позволяющий уменьшить аппаратурные затраты в схеме TC (при определенных условиях этот блок может не использоваться вообще). Предлагаемый метод основан на следующих особенностях SoC, основанных на технологии CPLD [1, 7]:

-       коэффициент объединения по входу макроячейки PAL значительно превосходит максимально возможное число букв в термах системы (1), определяемое L + R ;

-       число выходов EMB может меняться в некотором диапазоне (как правило, 1, 2, 4, 8).

 

 

3. Основная идея предлагаемого метода

 

Используем идею оптимального кодирования состояний МПА Мура [10], смысл которой заключается в таком кодировании ПЭС, чтобы максимально возможное число классов Bx єПA соответствовали одному обобщенному интервалу R-мерного булева пространства. Представим множество ПA в виде ПA B иПC, где BxєПB, если

|B>| > 1, (5)
и
BxєПC в противном случае. Очевидно, что схема TC должна
формировать только коды классов
Bx є ПB. Закодируем состояния am є A
оптимальным образом [10]. Представим множество П B в виде
П
B = ПD и ПE, где Bx є ПD, если коды am є B входят один обобщенный
интервал пространства кодирования. Теперь преобразованию подлежат
только коды состояний
  am є       E), где                                        E) cz A  - множество

состояний, входящих в классы ПE. Для кодирования классов BxєПE достаточно

 

 

переменных, образующих множество Z, где

Пусть tF - фиксированное число выходов блока EMB и пусть q -число слов в блоке при tF = 1. При реализации схемы CFMO автомата U1 параметр tF определяется следующим образом:

tF =]q/M[. (7) При этом интегрально блоки EMB схемы CFMO имеют

ts =]N/tF[-tF. (8) выходов. Очевидно, что At выходов могут не использоваться для представления микроопераций, где

At = ts - N. (9) Эти выходы можно использовать для представления переменных zr є Z. Рассмотрим случай, когда выполняется условие

(10)

в виде

В   этом   случае   множество   П E   необходимо представить

П


E


ПF иПG. Множество ПF включает nF классов, где

% = 2At -1, (11) коды которых хранятся вместе с микрооперациями и представляются переменными zr є Z, где |Z| = At. Множество ПG включает

nG =1 - nC - nD - nF (12) классов,    где    nC =|П c|,    nD =|П d|.    Для    кодирования классов

Bi є ПG достаточно

R3 =]l0g2(nG + 1)[ (13)

переменных, образующих множество т, где |т| = R3.

В этом случае для интерпретации ГСА Г предлагается автомат Мура


U 2 (рис. 2)

TC


ь


т

Рисунок 2 - Структурная схема МПА Мура U 2

 

Автомат U2 имеет ряд отличий от автомата U1 :

-          схема СС формирует систему функций

Ф = Ф t,Z,X ); (14)

-          вместо схемы CFMO используется схема CMOC, реализующая систему функций (2) и систему функций

Z = Z(T) (15)

для представления кодов классов Bx є П F;

-          преобразователь кодов ТС формирует коды классов Bx є ^ ;

- переменные Tr є T представляют состояния am є А(ПC) и классы Bi є ПD, где А(ПC) - множество состояний, входящих в классы Bi єП с.

При этом число входов в макроячейках PAL схемы СС увеличивается от L + R1 (автомат U1) до L + R + At + R3 (автомат U2). Однако это не

Страницы:
1  2  3 


Похожие статьи

В А Саломатин, С А Цололо - Оптимизация схемы мпа мура в составе системы на кристалле