Первоисточник: Баркалов А.А., Зеленёва И.Я., Бойков В.А. Синтез управляющего автомата по вертикализованной граф-схеме алгоритма. // Управляющие системы и машины, 2006, №3. – С. 62 - 66

УДК 681.3

Синтез управляющего автомата по вертикализованной

граф-схеме алгоритма

Баркалов А.А., Зеленёва И.Я., Бойков В.А.

Введение

Любая цифровая система (операционное устройство) может быть представлена как композиция управляющего (УА) и операционного (ОА) автоматов [1]. Последние достижения в области интегральной схемотехники привели к появлению «систем-на-кристалле» [3], позволяющих реализовать сложные операционные устройства на одном кристалле. Как правило, произвольная логика систем на кристалле реализуется по технологии FPGA ( field programmable gate array ), для которых характерно использование логических элементов табличного типа (LUT, look - up table ), имеющих 3-5 входов [5,7]. Такое ограничение на число входов вызывает необходимость функциональной декомпозиции булевых функций, задающих закон функционирования УА [4]. Для улучшения качества схемы (уменьшения числа LUT и увеличения быстродействия) целесообразно уменьшить число аргументов, от которых зависит функция. В настоящей работе предлагается метод, позволяющий решить эту задачу при реализации УА как микропрограммного автомата Мили [1, 2]. Метод основан на вертикализации исходной граф-схемы алгоритма (ГСА), при котором каждая операторная вершина включает не более одной микрооперации [2].

Основные положения и базовые схемы автомата Мили

Пусть ГСА Г содержит К операторных вершин, образующих множество О(Г)={О 1 , О 2 , …, О К }. В вершинах Оk O (Г) записываются функции y n Y , отождествляемые с микрооперациями Y={ y 1 , …, y N } OA . Назовем набор микроопераций Y( Ok ) Y , записанный в вершине Ok O (Г), микрокомандой. Отметим, что в разных операторных вершинах могут быть записаны одинаковые микрокоманды. В условных вершинах ГСА Г записываются элементы множества логических условий Х={ x 1 ,…, x L }. Пусть ГСА Г отмечена состояниями автомата Мили [1], образующими множество внутренних состояний А={ a1 , …, aM }. Закодируем состояния am A двоичными кодами K ( am ) разрядности R=] log 2 M [, используя для кодирования внутренние переменные из множества Т={ T1 , …, TR }. Отмеченная таким образом граф-схема алгоритма является основой для формирования прямой структурной таблицы (ПСТ) (табл.1) со столбцами [1]: am , K ( am ), aS , K ( aS ), Xh , Yh , Фh , h . Здесь am A , K ( am ) – соответственно, исходное состояние МПА и его код; aS A , K ( aS ) – соответственно, состояние перехода и его код; Xh – входной сигнал, определяющий переход < am , aS > и равный конъюнкции некоторых элементов множества Х; Yh Y – микрокоманда, формируемая на переходе < am , aS >; Фh Ф – набор функций возбуждения памяти МПА, принимающих единичное значение для переключения памяти из K( am ) в K ( aS ), Ф={ , …, } – множество функций возбуждения памяти; как правило, память МПА реализуется с использованием D-триггеров; h {1, …, H } – номер перехода МПА.

Отмеченная ГСА Г 1 (рис.1) содержит К=7 операторных вершин и Q =5 различных микрокоманд: Y 1 = Y ( O 1 )= Y ( O 6 )={ y 1 , y 4 , y 7 }, Y 2 = Y ( O 2 )= = Y ( O 7 )={ y 2 , y 5 }, Y 3 = Y ( O 3 )={ y 3 , y 6 , y 7 }, Y 4 = Y ( O 4 )={ y 1 , y 5 }, Y 5 = Y ( O 5 )={ y 2 , y 5 }. Автомат Мили S(Г 1 ), интерпретирующий ГСА Г 1 , имеет М=5 состояний, L=3 логических условий, N=7 микроопераций: А={ a 1 , …, a 5 }, X ={ x 1 , x 2 , x 3 }, Y ={ y 1 , …, y 7 }. Закодируем состояния а m A следующим образом: K( a 1 )=000, …, K ( a 5 )=100. Отметим, что для кодирования использовано R=3 двоичные переменные: Т={ T 1 , T 2 , T 3 }; Ф={ D 1 , D 2 , D 3 }.

Фрагмент ПСТ для состояния a 1 (табл.1) включает 2 строки, а ПСТ в целом имеет H=8 строк. Прямая структурная таблица является основой для формирования систем функций

Ф=Ф(Т, Х), (1)

Y=Y(T, X), (2)

термы которых определяются как конъюнкция

F h = ( h = ). (3)

Здесь - конъюнкция внутренних переменных или их инверсий, соответствующая коду K( a m ) исходного состояния a m A из h -й строки ПСТ. Например, из табл.1 имеем: F 1 = , F 2 = , y 1 = F 1 , D 3 = F 1 F 2 .

Система (1) – (2) является основой для синтеза одноуровневой схемы МПА, называемой Р-автоматом Мили (рис.2,а). Здесь Р-подсхема формирует функции (1) – (2), а регистр RG реализует память МПА. Одноуровневая схема обладает максимальным быстродействием среди возможных реализаций автомата Мили, но t 1 = R + N функций зависят от аргументов Х и Т, что увеличивает число LUT -элементов по сравнению с другими решениями в силу большого числа функций и их аргументов.

Одним из методов уменьшения числа выходов Р-подсхемы является кодирование полей совместимых микроопераций [2]. При этом множество Y разбивается на I классов Y 1 , …, Y I микроопераций, причем у n , y m I Y i , если и только если эти микрооперации не встречаются вместе в микрокомандах Y q Y . Микрооперации y n Y i ставится в соответствие двоичный код K( y n ) разрядности r i =] log 2 (| Y i |+1)[ и кодирующие переменные образуют множество Z={ z 1 , …, z R 1 }, где

R 1 = . (4)

Микрооперации y n Y i формируются дешифратором DC i ( i =1, …, I ), совокупность этих дешифраторов составляет D -подсхему. Такой подход порождает PD-автомат (рис.2,б), где Р-подсхема реализует функции (1) и

Z=Z(T, X), (5)

а D-подсхема реализует функции

Y=Y(Z). (6)

В этом случае число выходов Р-подсхемы уменьшается до t 2 = R + R 1 < t 1 .

Для ГСА Г 1 Y 1 ={ y 1 , y 2 , y 3 }, Y 2 ={ y 4 , y 5 , y 6 }, Y 3 ={ y 7 }, r 1 =r 2 =2, r 3 =1, R 1 =5, Z ={ z 1 , …, z 5 }. Для реализации D-подсхемы требуется I=3 дешифратора.

В настоящей работе предлагается метод синтеза двухуровневой схемы МПА Мили, позволяющий уменьшить число выходов Р-подсхемы до t 3 = R + R 2 , где R 2 < R 1 .

Основная идея метода

Поставим в соответствие каждой вершине О k О(Г) последовательность вершин = < O k 1 , …, O k Nk >, где N k – число микроопераций в микрокоманде Y ( O k ). Каждая вершина O k n последовательности содержит только одну микрооперацию y m Y ( O k ) и соответствует одному классу разбиения множества Y( O k ) ( k = ). Назовем полученную в результате таких преобразований ГСА вертикализованной ГСА (ВГСА) и обозначим ее V (Г).

На рис.3 приведен фрагмент ВГСА V (Г 1 ), назначение сигнала y 0 будет пояснено далее.

Очевидно, все микрооперации ВГСА V(Г) являются попарно совместимыми. Отметим, что микрооперация y n Y может входить в разные микрокоманды Y q Y . Чтобы подчеркнуть этот факт, обозначим через y q n микрооперацию y n Y q ( q =1, …, Q ). Поставим в соответствие каждой микрокоманде Y q Y двоичный код разрядности R 2 = ] log 2 Q [, используя для кодирования элементы множества Z. Пусть N 0 = max ( N 1 , …, N K ), поставим в соответствие j-й компоненте последовательности двоичный код К( y n q ) разрядности R 3 =] log 2 N 0 [. Таким образом

y n q = pr j (j= , k= ) , (7)

где pr j - это j -я проекция кортежа (т.е. j -я компонента последовательности ).

Используем для кодирования элементы множества , | |= R 3 . В этом случае код С(y n q ) микрооперации y n Y определяется конкатенацией

С (y n q )=K(Y q )*K(y n q ), (8)

где * – знак конкатенации. В настоящей работе предлагается реализовать автомат Мили как РD V -автомат (рис.4), основанный на представлении (8).

Автомат функционирует следующим образом. Пусть в момент времени t ( t =0, 1, …) P -подсхема сформировала функции возбуждения регистра RG (Ф) и регистра микрокоманд RMI ( ). Пусть в RG находится код K( a m ), а RMI – код K ( Y q ). Счетчик микроопераций СМО обнулен, что соответствует первой микрооперации y n q из последовательности .

Микрооперации y n Y формируются D -подсхемой в виде

Y=Y(Z, ). (9)

Если выход последовательности не достигнут, то преобразователь кода СС формирует сигнал y 0 :

y 0 =f(Z, ). (10)

Если y 0 =1, то в момент времени t+1 содержимое СМО увеличивается на единицу, что соответствует режиму естественной адресации элементов последовательности [2]. В этом случае содержимое регистров RG и RMI не меняется, т.е. P D V -автомат не изменяет состояния. Если выход последовательности достигнут, то y 0 =0. При этом запускается операционный автомат, который выполняет микрооперации y n Y q и формирует новые значения логических условий Х. Теперь Р-подсхема формирует функции Ф и , по которым в RG заносится код состояния перехода К(a S ), а в RMI – код очередной микрокоманды. Функционирование продолжается аналогично до перехода МПА в конечное состояние a 1 A . Регистр RY служит для запоминания компонент последовательности (k=1, …, K ), чтобы они могли параллельно выполняться ОА. Индекс R в Y R подчеркивает, что микрооперации y n Y формируются на выходах регистра. Для синхронизации триггеров RY используется возможность локальной синхронизации, присущая всем современным FPGA [3,7]. Отметим, что регистр RY является обязательным элементом любой системы <УА, ОА>, в которой УА реализован с использованием модели Мили [1].

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

Метод синтеза PD V -автомата и пример его применения

В настоящей работе предлагается метод синтеза PD V -автомата, иллюстрируемый на примере МПА Мили S 1 . Метод синтеза включает следующие этапы.

1. Формирование отмеченной ГСА и ПСТ Р-автомата . Этот этап

выполняется по известной методике [1, 2].

2. Формирование последовательностей микроопераций . Этот этап выполняется тривиально: множеству Y( O k ) ставится в соответствие кортеж над множеством Y ( O k ) [2]. При этом условимся, что первой компонентой кортежа является микрооперация y n Y ( O k ) с наименьшим индексом, второй компонентой – микрооперация y m Y ( O k ) с наименьшим индексом в множестве Y ( O k ) / { y n } и так далее. При таком подходе число попарно различных кортежей совпадает с числом микрокоманд Q. Условимся, кортеж, соответствующий микрокоманде Y q Y , обозначать как (q=1, …, Q ). Пусть B={ } – множество сформированных последовательностей.

Для нашего примера В={ }, где , , , , , Q =5. Отметим, что элементы множества В содержат М 0 =12 различных компонент, что соответствует числу выходов D-подсхемы. В общем случае

М 0 = . (11)

3. Кодирование микроопераций . Из закона функционирования PD V -автомата следует, что если y n q = pr i , а y q m = pr i +1 , то

K(y q m )=K(y q n ) + 1, (12)

где i =1, …, | Y q |-1, q =1, …, Q . Условие (12) можно удовлетворить, если первой компоненте последовательности присвоить код разрядности R 3 , десятичный эквивалент которого равен нулю, код следующей компоненты соответствует единице, затем двойке и т.д.

Для нашего примера N 0 =3, R 3 =2, , коды микроопераций приведены в табл.2.

•  Кодирование микрокоманд . Этот этап выполняется тривиально.

Пусть в нашем случае К( Y 1 )=001, …, K ( Y 5 )=101.

•  Формирование ПСТ PD V -автомата . Эта таблица является основой

для формирования системы функций (1) и системы

(Т, Х), (13)

формирующей в RMI коды микрокоманд. Таблица формируется путем замены столбца Y h исходной ПСТ столбцом , содержащим переменные , равные единице в коде К(Y q ) микрокоманды, записанной в h-й строке исходной ПСТ ( h = ).

Для PD V -автомата S 1 фрагмент ПСТ приведен в табл.3. Очевидно, ПСТ Р-автомата Мили и эквивалентного PD V -автомата содержат одинаковое число строк. Из табл.3 имеем, например, , .

•  Формирование таблицы дешифратора микроопераций. Эта таблица

является основной для синтеза D-подсхемы и включает столбцы Y q , K ( Y q ), K ( y q n ), y n . Первые два столбца образуют код С(y q n ), соответствующий (8).

Для нашего примера эта таблица имеет M 0 =12 строк (табл.4).

•  Формирование функции y 0 . Функция (10) задает закон

функционирования преобразователя кодов СС. В нашем случае она представлена картой Карно (рис.5). В этой карте знаком «*» отмечены неиспользуемые коды микрокоманд и их компонент. Из рис.5 следует, что y 0 = .

8. Синтез логической схемы PD V -автомата . Этот этап сводится к реализации систем функций (1), (10), (13) на FPGA , а также реализации регистров RMI, RG , RY и счетчика СМО на триггерах, входящих в состав FPGA . В настоящее время имеются эффективные методы решения этих задач [3, 4, 6, 7], которые выходят за рамки данной статьи.

Заключение

Предложенный в работе метод синтеза МПА Мили по вертикализованной ГСА позволяет уменьшить число выходных функций, зависящих от логических условий и внутренних переменных автомата. При этом для реализации системы микроопераций используются только один дешифратор, а число сигналов обратной связи и строк прямой структурной таблицы PD V -автомата совпадает с соответствующими параметрами эквивалентного автомата Мили. Недостатком метода является уменьшение быстродействия по сравнению с известными методами двухуровневой реализации микропрограммных автоматов. Однако предложенный в работе метод запуска операционного автомата после формирования всех микроопераций каждой микрокоманды позволяет уменьшить этот недостаток. Проведенные авторами исследования показывают, что предложенный метод позволяет на 17-24% уменьшить число LUT-элементов в схеме МПА по сравнению с известными методами синтеза, основанными на кодировании полей совместимых микроопераций.

Литература