Граф - схемы микропрограммных автоматов

Для описания микропрограмм необходимо знать и задавать последовательности микрокоманд и функции перехода, определяющие порядок выполнения микрокоманд. Для описание микропрограмм обычно используется язык граф-схем алгоритмов (ГСА).

Граф-схема алгоритма (ГСА) - ориентированный связный граф, содержащий одну начальную вершину (А₀), одну конечную (А_к) и произвольное количество условных (P={p₁, ..., p_F}) и операторных (А={A₁, ..., A_G}) вершин.

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторная вершины имеют по одному выходу, а условная - два выхода, помеченных символами 0 и 1. Конечная вершина выходов не имеет.

ГСА удовлетворяет следующим условиям:

1 Входы и выходы вершин соединяются друг с другом с помощью дуг направленных всегда от выхода ко входу.

2 Каждый выход соединён точно с одним входом.

3 Любой вход соединяется по крайней мере с одним выходом.

4 Любая вершина графа лежит по крайней мере на одном пути из начальной вершины к конечной вершине.

5 Один из выходов условной вершины может соединяться с её входом, что недопустимо для операторной вершины. Такие условные вершины называются возвратными вершинами.

6 В каждой условной вершине записывается один из элементов множества X={x₁, ..., x_l, ..., x_L}, называемого множеством логических условий. Разрешается в различных условных вершинах запись одинаковых элементов множества X.

7 В каждой операторной вершине записывается оператор ( микрокоманда) Y_t - подмножество множества Y={y₁, ..., y_n, ..., y_N}, называемого множеством микроопераций Y_t=(y_t1, ..., y_tu, ..., y_tU); y_tnÎY, u=1, ..., U.

При U=0, Y_t=Æ (пусто), что допустимо. Разрешается также запись в различных операторных вершинах одинаковых подмножеств множества микроопераций.

При большом количестве дуг, приходящих на один вход вершины, ГСА выглядит неаккуратно, поэтому разрешается изображать дуги, входящие в вершины, так, как показано на рис.69.

Пример ГСА, содержащего 6 условных и 7 операторных вершин приведён на рис.70.

Предположим, что в операторных вершинах ГСА записаны операторы Y_t, ... , Y_T - все разные, так что операторную вершину можно отождествить с записанным в ней оператором (в вершине A_i записан оператор Y_i. В таком случае вместо обозначения A_i для операторной вершины можно использовать символы Y_i).

Начальной вершине поставим в соответствие оператор Y₀, а конечной - оператор Y_k=Y_T+1. Пусть в ГСА имеется путь из вершины Y_i (i=0, 1, ... , T) в вершину Y_j (j=1, ... , T, T+1) вида

, (A)

проходящий только через условные вершины p_i1, ... , p_iR; где l_ir Î {0,1} - символ, приписанный выходу условной вершины p_ir, через который проходит путь (A). Каждому такому пути соответствует элементарная конъюнкция , где x_ir - логическое условие, записанное в условной вершине p_ir; .

Если между вершинам Y_i и Y_j имеется несколько (например H) путей, проходящих через условные вершины, то a_ij равно дизъюнкции элементарных конъюнкций, соответствующих всем путям, то есть

- конъюнкция, соответствующая h - му пути из Y_i в Y_j.

Таким образом, a_ij - функция перехода от оператора (микрокоманды) Y_i к оператору (микрокоманде) Y_j.

Всевозможные наборы значений переменных обозначим через . Определим процесс выполнения ГСА, начиная с оператора Y₀ (начальный оператор), на произвольной бесконечной последовательности наборов D_m1, ..., D_mg, ... следующим образом:

Выписываем оператор Y₀.

ШАГ 1 Придаём переменным значения из набора D_m1. Из множества функций перехода a₀₁, ... , a_0Т выбираем функцию a_0i1 (i₁Î{1, ... , T}), такую, что a_0i1(D_m1) = 1. В строчку рядом с Y₀ записываем Y_i1

Y₀ Y_i1.

ШАГ 2 Придаём переменным значения из набора D_m2. Из множества функций перехода a_i11, ... , a_i1Т выбираем функцию a_i1i2 (i₂Î{1, ... , T}), такую, что a_i1i2(D_m2) = 1. В сточку рядом с Y_i1 записываем Y_i2

Y₀ Y_i1 Y_i2 и т. д.

Пусть перед некоторым q - м шагом имеем строчку операторов

Y₀ Y_i1 Y_i2 ... .

Если на наборе D_mq некоторая функция перехода равна единице (i_qÎ{1, ... , T}), то в выписанную строчку операторов добавляем . Если оказывается, что ( ) = 1, то в сточку вслед за записываем Y_T+1(конечный оператор), и процесс выполнения ГСА завершается.

Строчка Y₀ Y_i1 Y_i2 ... называется значением ГСА на последовательности наборов D_m1, D_m2, ... , , . Процедура выполнения ГСА на заданной последовательности наборов переменных может прекратиться в двух случаях:

- исчерпаны все наборы (заключительным в значении ГСА стоит оператор );

- достигнута конечная вершина (заключительным в значении ГСА стоит конечный оператор Y_T+1).

Например, значение ГСА на по рис.70 на последовательности наборов

Рассмотрим процедуру выполнения ГСА на произвольной последовательности наборов при наличии возвратных условных вершин на примере фрагмента ГСА, приведенного на рис. 71.

Между операторами Y₁ и Y₃ имеется бесчисленное множество путей, в связи с чем :

Так как логические условия, соответствующие всем путям, начиная со второго, равны нулю, a₁₃ фактически определяется первым путём.

В связи с этим в дальнейшем учитываются лишь те пути через возвратные вершины, которые проходят через выход, не соединённый с её входом. Таким образом, на рис.71 имеется лишь один путь вида

из вершины Y₁ в вершину Y₃. Тогда,

Пусть в процессе выполнения ГСА на некоторой последовательности наборов выполнился оператор Y₁, после чего в этой последовательности стоят наборы значений переменных x_i

101,

111.

Из выражений (С) видно, что ни одна функция перехода из оператора Y₁ на наборе 101 не равна единице, поэтому в строку рядом с Y₁ записывается пустой оператор Y₀ :

...Y₁Y₀ и

выполняется переход к следующему набору (111), на котором проверяется значение функции перехода из того же оператора Y₁. На наборе 111 a₁₃=1, а поэтому рядом с Y₀ записывается оператор Y₃:

... Y₁Y₀Y₃...

Если бы и на этом наборе ни одна из функций перехода не была бы равна единице, то рядом с Y₀ был бы записан ещё один пустой оператор Y₀ и так до тех пор, пока на каком-то наборе не появилось значение некоторой функции перехода, равной единице.

Такое выполнение ГСА соответствует тому, что при значениях переменных, при которых ни одна функция перехода из последнего выполненного оператора не равна единице, управляющее устройство не выдаёт сигналов на выполнение микроопераций в операционном блоке (выполняется микрокоманда Y₀) и тем самым реализуется ожидание в работе устройства.