РАЗДЕЛ 2
РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ
МИКРОПРОГРАММНЫХ АВТОМАТОВ
2.1. Оптимизация автомата Мили с кодированием наборов микроопераций
2.1.1. Структурная организация и функционирование автомата
Используем метод кодирования наборов фрагмента переменных, предложенный в п.
1.4, для минимизации аппаратурных затрат в схеме PY-автомата Мили (рис. 1.9)
[19]. При этом под переменными будем понимать множество микроопераций Y.
Разделим множество Y на две части. Одна часть, образующая так называемый
фрагмент микроопераций (ФМО), формируется YF-подсхемой аналогично PY-автомату;
вторая часть формируется непосредственно P-подсхемой устройства (рис. 2.1).
Назовем структуру, изображенную на рис. 2.1, PYF-автоматом.
Здесь YF-подсхема формирует подмножество микроопераций Y1НY, входящих во
фрагмент микроопераций. P-подсхема формирует код I набора МО, входящих в ФМО, а
также подмножество микроопераций Y2, формируемых унитарно. В целом PYF-автомат
реализует следующие системы функций:
D = D (T, X), (2.1)
I = I (T, X), (2.2)
Y1 = Y1 (I), (2.3)
Y2 = Y2 (T, X), (2.4)
причем Y1ИY2=Y и Y1ЗY2= Ж. Отметим, что система (2.2) отличается от первой
части системы (1.16), поскольку количество и кодирование наборов микроопераций
в PY- и PYF-автоматах в общем случае различны. В остальном PYF-автомат
функционирует аналогично PY-автомату.
Определим аналитические характеристики логической схемы PYF-автомата, на
которых в дальнейшем построим метод синтеза данного устройства.
Пусть в структуре на рис. 1.9 наборы микроопераций закодированы двоичными
кодами разрядности R0, и подсхема Y формирует N микроопераций, входящих в W
наборов.
Пусть также в структуре на рис. 2.1 мощность множества Y1 составляет N1
микроопераций, множества Y2 – R2 микроопераций. Разрядность кода набора ФМО I
обозначим через R1. Таким образом, общее число выходов P-подсхемы PYF-автомата
будет равно R1+R2. Обозначим число наборов микроопераций во фрагменте через
W1.
Дополнительно примем, что в обеих структурах P-подсхема анализирует L
логических условий и R разрядов кода состояния автомата.
Определим выраженные в битах информационные емкости логических схем PY- и
PYF-автоматов. Считая, что P-подсхема реализуется на ПЛМ, используем матричное
представление P-подсхемы для определения ее информационной емкости [73]:
VПЛМ = V”И” + V”ИЛИ”. (2.5)
С учетом (2.5), емкость P-подсхемы PY-автомата определяется как
, (2.6)
где QPY – число внутренних термов ПЛМ P-подсхемы.
Аналогично для PYF-автомата
, (2.7)
где QPYF – число внутренних термов P-подсхемы PYF-автомата. Отметим, что в
общем случае Q№Q1, поскольку системы функций, формируемые P-подсхемами,
различны.
Информационная емкость ПЗУ Y-подсхемы PY-автомата составляет
(2.8)
бит, а емкость ПЗУ YF-подсхемы PYF-автомата равна
. (2.9)
Поскольку в общем случае базис ПЗУ дешевле базиса программируемой логики,
приведем единицу емкости ПЛМ в стоимостное соответствие с единицей емкости ПЗУ
с помощью специального коэффициента K. Тогда полная информационная емкость
логической схемы PY-автомата определяется как
, (2.10)
а в случае PYF-автомата
. (2.11)
Определим эффективность E(PYF) использования PYF-автомата как отношение
функций (2.10) и (2.11):
. (2.12)
Таким образом, критерием целесообразности применения PYF-автомата по сравнению
с PY-автоматом будем считать значение эффективности E(PYF)>1. Отметим, что
значения аргументов формулы (2.12) могут быть получены лишь в результате
полного синтеза обеих структур автоматов, а сама формула (2.12) справедлива
лишь при реализации P-подсхем в базисе ПЛМ.
Примем следующее допущение. Если число выходов ПЛМ P-подсхемы не изменилось
при переходе от PY- к PYF-автомату, то не изменилась и информационная емкость
ПЛМ (число входов ПЛМ в обеих структурах является одинаковым). Тогда в качестве
эффективности PYF-автомата по отношению к PY-автомату будем рассматривать
величину EROM(PYF), равную отношению информационной емкости Y-подсхемы к
емкости YF-подсхемы при неизменном числе выходов P-подсхемы. С учетом (2.8) и
(2.9) имеем:
. (2.13)
Полагая, что выигрыш имеет место при EROM(PYF) > 1, получаем следующую систему,
определяющую целесообразность применения PYF-автомата:
Здесь (2.14) указывает на равенство числа выходов P-подсхемы PYF-автомата по
сравнению с PY-автоматом; неравенство (2.15) вытекает из формулы (2.13) для
значения EROM(PYF)>1.
Данную систему можно записать следующим образом:
Очевидно, что при W1=2 для кодирования наборов требуется R1=]log2W1[=1
переменных. Следовательно, минимальное число наборов во фрагменте W1(min)=2 и
R1(min)=1. При W1=1 микрооперации, формируемые автоматом, являются константами.
Подставив в (2.16) значение R1=R1(min)=1, получим:
N1(min) = N + 1 – R0. (2.18)
Таким образом, минимальное число микроопераций, которые должны быть включены
во фрагмент, определяется формулой (2.18) и является ограниченной величиной.
Если во фрагмент включить количество МО, меньшее N1(min), оставшиеся МО будут
вынуждены формироваться непосредственно P-подсхемой. Следовательно, величина R2
в формуле (2.14) будет расти при сохранении значения R1, и число выходов
P-подсхемы PYF-автомата будет больше, чем в случае PY-автомата, что нарушает
сделанное нами допущение.
Поясним сказанное. Пусть PY-автомат формирует N=8 микроопераций, образующих
W=9 наборов Y1-Y9 (таблица 2.1), что приводит к емкости ПЗУ, равной 8*24=128
бит.
Таблица 2.1
Содержимое ПЗУ Y-подсхемы
Yi
R0
y1
y2
y3
y4
y5
y6
y7
y8
Y1
0 0 0 0
0
Y2
0 0 0 1
1
Y3
0 0 1 0
0
Y4
0 0 1 1
1