Построение отмеченной граф-схемы алгоритма микропрограммного
Граф-схема алгоритма содержит всю необходимую информацию для определения количества состояний памяти МПУ и их размещение. Решение поставленной задачи осуществляется путем построения так называемой отмеченной граф-схемы алгоритма. Отмеченной называется такая ГСА, на которой условным знаком (крестиком, звездочкой) показаны состояния синтезируемого МПУ, при достижении которых часть алгоритма, описываемая цепочкой операторных и условных вершин, находящихся между начальной вершиной и отметкой некоторого состояния, будет реализовано.
Рассмотрим методику построения отмеченной ГСА МПУ на примере автомата Мили.
Отличительной особенностью МПУ Мили является то, что выходные сигналы формируются в моменты перехода из состояния в состояние. При этом во время одного перехода может быть сформирована только одна микрокоманда (т.е. одна или несколько микроопераций, выполняемых одновременно).
Отсюда следует, что при размещении отметок состояний на граф-схеме алгоритма максимальное расстояние между двумя соседними отметками должно быть таким, чтобы в любой соединяющей их последовательной цепочке вершин содержалось не более одной операторной вершины.
Общим требованием при синтезе ДУ является обеспечение их возврата в исходное состояние после выполнения алгоритма. Из этого следует, что при проведении отметок ГСА необходимо одной общей отметкой обозначать как начало, так и конец ГСА.
Отметка состояний МПУ Мили производится по следующим правилам:
1)
Входы вершин, непосредственно следующих за операторными, отмечаются символами
Y 0, Y 1, Y 2, …, Yк.
Отметим, что каждое состояние
Yj определяется состоянием элементов памяти автомата
Yj = Yj (y 1, y 2, …, yi, …, yn).
2) Символом Y0 отмечается вход вершины, следующей за начальной, а также вход конечной вершины.
3)
Входы всех вершин, непосредственно следующих за операторными, отмечаются символами
Y 1, Y 2, …, Yк.
При этом для отметки входа вершины используется только одни символ, независимо от того, сколько выходов условных или операторных вершин к нему сходятся.
4) Для отметки входов различных вершин используются различные символы, т.е. на отмеченной ГСА повторяется только символ Y 0.
5) Если к отмечаемому входу подходят выходы несколько условных и операторных вершин, то отметка Yi ставится ниже стрелок, подходящих от операторных вершин, и выше стрелок, подходящих от условных вершин. Таким образом, стрелки, подходящие от условных вершин, минуют данную отметку Yi (подходят после отметки).
Такое размещение отметок по ГСА позволяет исключить переходы между отметками ГСА, которые не содержат ни одной операторной вершины (не имеют выходов), и следовательно, увеличить быстродействие проектируемого МПУ.
Пример 5.2 На рисунке 5.11 приведена отмеченная граф-схема алгоритма. Размещение отметок на ГСА произведено по приведенным правилам. Отметим, что приведенная граф-схема содержит 6 вершин, однако для выполнения отметок состояний понадобилось всего 3 символа – Y 0, Y 1, Y 2. Это еще раз подчеркивает особенность МПУ Мили, заключающуюся в том, что при переходе в одно и то же состояние могут быть сформированы различные выходные сигналы в зависимости от значений сигналов логических условий. Напомним, что на ГСА символы условных вершин обозначают входы МПУ. В данном случае входов три – х 3, х 2, х 1. Символы операторных вершин обозначают микрокоманды (команды управления) – т.е. выходы МПУ.
Команды управления (выходы) содержат несколько разрядов, число которых следует из условий на проектирование МПУ.
В рассматриваемом МПУ всего различных команд управления – четыре Z 1 – Z 4, их разрядность равна 3 – z 3, z 2, z 1.
Запись операторной вершины содержит символ микрокоманды Zi и те ее разряды, которые в этой команде принимают единичное значение.
Таким образом, для примера 2 команды управления при базе z 3, z 2, z 1 равны:
Z 1 (z 2 z 1) = 011; Z 3 (z 3 z 2 z 1) = 111;
Z 2 (z 2) = 010; Z 4 (z 3) = 100.
2014-02-13
832
