Синтез многорежимных автоматов

Разработка и освоение отечественной промышленностью БИС опе­ративной и постоянной памяти позволяет решать задачи создания блоков памяти путем объединения нескольких БИС. Адресация и управление в та­ких блоках не сводятся только к задачам дешифрации. Наиболее сложный узел, обеспечивающий комплексное функционирование блока памяти, – это автомат управления. В том случае, когда в блоке кроме кристаллов ПЗУ используются кристаллы ОЗУ, необходимо формировать несколько раз­личных временных диаграмм (рис. 76). На этом рисунке цифры по оси абсцисс обозна­чают номер выходных сигналов управления, а по оси ординат – длительность сигналов в относительных единицах.

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

Известные методы проектирования однорежимных микропрограмм­ных автоматов (МПА) основаны на использовании элементов задержки (встроенных мультивиб­раторов) в логических цепях автомата или на применении автоматов Мили, Мура. Оптимизация МПА производится за счет функционально-временного со­вмещения операторов, минимиза­ции булевых функций или специального кодирования. Отсутствуют методики оптимизации на уровне составления самих граф-схем алгоритмов функционирования МПА, хотя оптимизация наибо­лее эффектив­на на самых ранних этапах проектирования МПА.

Рассмотрим один из возможных подходов к решению данной про­блемы примени­тельно к поставленной задаче. Проанализируем временные диаграммы рис. 76. Реализацию каждого временного интервала можно осуществить путем включения и выключения триггеров с кодовыми вхо­дами, соответствующими микрооперациям С₁, С₂,..., С _k.

Рис. 76

В основу проектирования МПА положим модель В.М. Глушкова [9], расширенную в работах [16, 23] за счет явного выделения блока формирования логических условий α. В данном случае введем α ₁,..., α_m – набор логических условий, отмечающих окончание соответствующего временного интервала, формирование которых осуществим с помощью счетчика временных тактов (Сч 2) и комбинационной схемы (КСхЗ) на рис. 77.

Рис. 77

Обозначим через а₁, а₂,..., а _n состояния МПА. Желательно так составить граф-схемы алгоритма для всех режимов, чтобы они содержали минимальное число различных α_i (т.е. min m), а одни и те же сигналы C _j принадлежали бы одним и тем же состояниям a _S (t). В этом случае не пот­ребуется дополнительных схем ИЛИ, объединяющих сигналы C _j от разных a _S (t) и a _p (t), p ≠ s, сокращается глубина логических схем, возможно сокращение числа состояний МПА, следовательно, может быть повы­шено быстродействие. В связи с тем, что генерация временных интервалов на­чинается включением счетчика (Сч 2), каждому α_i в граф-схеме алгоритма необ­ходимо соотнести пустой оператор перед α_i, соответствующий независимому состоянию МПА. Число таких состояний после оптимизации МПА должно со­ответствовать максимальному числу одновременно используемых α_i в одном режиме Р (Р = 1, 2,..., Р).

Для микрооперации C _j обозначим в режиме P: t_{i 0}(P) – момент ее включения; t_{i 1}(P) – момент ее выключения. В некоторых режимах P: t_{i 0}(P) = 0, тогда время выключения определяется по условию

min t_{i 1}(P) ≤ t_{i 1}(P) ≤ max t_{i 0}(P).

Микрооперациям с t_{i 0}(P) ≠ 0 будет предшествовать момент времени включения задержки t_αi (P) по условию α_i и время пропусков тактов t_ei (P), где e – символ пустого оператора. Например, для С₆ в режиме запишем

t ₆₀(1) = tα ₆(1) + t _e6(1); t ₆₀(1) + 0,4 ≤ t ₆₁(1) ≤ 2.

Очевидно, что для сигналов большой длительности через tα_i (P) и t_ei (P) будет оп­ределяться момент выключения C _j (P).

Таким образом, для моментов включения при всех режимах P Î {1, …, P } и для каждого типа микрооперации i Î {1, 2,..., I } условие оп­ределяется выражениями

t_{i 0}(P) = 0 или t_{i 0} = t_αi (P) + t_ei (P),

а для моментов выключения

min t_{i 1}(P) ≤ t_{i 1}(P) ≤ max t_{i 1}(P) или t_{i 1}(P) = t_αi (P) + t_ei (P) + t_{i 0}(P).

Подставив в последнее уравнение t_{i 0}(P) = 0 для соответствующих t_i получим систему неравенств вида:

(6)

где i ≠ j, j = 1, 2, …, I; P = 1, 2,..., P.

Заметим, что t_i (P) и t_i (P + k) окажутся приписанными одному и тому же состоя­нию либо при k = 0, либо в том случае, если

(7)

где Δ t – длительность такта синхронизации в автомате; 2 ⁿ – максимально допустимое число состояний МПА.

Введем двоичные переменные δ_ik (P), которые принимают значения 1 для заданного i, P; если i ≠ k, условие (7) выполняется, в противном случае δ_ik (P) = 0. Тогда целевую функцию оптимизации можно записать в виде

. (8)

Таким образом, задача составления граф-схемы с оптимальным со­вмещением од­ноименных операций и минимальным числом различных α_i (за счет передвижения начала или конца микрооперации в заданных до­пустимых границах) свелась к за­даче целочисленного программирования с булевыми переменными: необходимо максимизировать выражение (8) при ограничениях (6).

Решением задачи оптимизации для рассматриваемого примера явля­ется система граф-схем алгоритмов. Как видно из рис. 78, полученные по формализованной методике граф-схемы отличаются малым числом логи­ческих условий и однознач­ной привязкой как операций проверки логиче­ских условий, так и одноименных микроопераций к одним и тем же со­стояниям МПА.

Дальнейший этап синтеза многорежимных автоматов связан с полу­чением обоб­щенного графа МПА. Для этого разметим граф-схемы (рис. 78, режим 1) и затем на граф состояний (рис. 79) перенесем все перехо­ды из состояний α_i в α_j, кото­рые имеются хотя бы в одном из режимов Р. После получения графа МПА следует перейти к составлению булевых функций выходов и переходов МПА и к синтезу МПА.

Наиболее эффективная реализация МПА для рассматриваемого слу­чая связана с использованием счетчика в качестве МПА [25] для реализа­ции последовательно­сти состояний 1, 2,..., 7 и пропуска такта (отметим это особо) в переходах 2, 4, 6 путем отключения сигналов тактовой частоты от входов памяти МПА и переклю­чения на устройство выработки логических условий α. Тогда комбинационная схема формирования переходов в МПА существенно упрощается, так как требуется формировать единственную выходную функцию f ₀ переключения генераторов тактовых сигналов. Реализация автомата такого типа приводит к экономии оборудования и существенному повышению его быстродействия.

В реальных системах управления и контроля необходимо генерировать многоканальную последовательность временных интервалов длительностью от 0,2 мкс до 25 мс в каждом из каналов управления исполнитель­ными устройствами. Конструирование таких многопрограммных, много­канальных формирователей на структурах взаи­мосвязанных микропро­граммных автоматов [25] позволяет исключить наборное поле (набор реги­стров, ПЗУ), схему цифрового компаратора, а для формирования интервалов времени, неравных произведению длительности

Рис. 78

Рис. 79

периода задающего генератора и числа 2 ⁿ, следует применить схемы «И» на 2–3 входа, где n – целое число.