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

Граф-схема алгоритма (ГСА) имеет вид ориентированного графа. При построении графа оперируют пятью типами вершин (рис. 3.3).

Начальная вершина (см.рис. 11.3, а) определяет начало микропрограммы и не имеет входов. Конечная вершина (см. рис. 11.3 б), указывает конец микропрограммы, поэтому имеет только вход.

Рис. 11.3, Разновидности вершин граф-схемы алгоритма: а — начальная; б-конечная; в — операторная; г — условная; д - ждущая

В операторную вершину (см. рис. 11.3, в) вписывают микрооперации, выполняемые в течение одного машинного такта. С вершиной связаны один вход и один выход. Условная* вершина (см. рис. 11.3, г) используется для ветвления вычислительного процесса. Она имеет один вход и два выхода, соответствующие позитивному («Да») и негативному («Нет») исходам проверки условия, записанного в вершине. С помощью ждущей вершины (см. рис. 11.3, д) можно описывать ожидание в работе устройств. В этом случае выход «Да» соответствует снятию причины, вызвавшей ожидание.

Граф-схемы алгоритмов составляются в соответствии со следующими правилами:

1. ГСА должна содержать одну начальную, одну конечную и конечное множество операторных и условных вершин.

2. Каждый выход вершины ГСА соединяется только с одним входом.

3. Входы и выходы различных вершин соединяются дугами, направленными от выхода к входу.

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

5. В каждой операторной вершине записываются микрооперации y соответствующие одной микрокоманде У.

6. В каждой условной вершине записывается один из элементов множества логических условий х.

7. Начальной вершине ставится в соответствие фиктивный оператор у0 а конечной — фиктивный оператор y_k На рис. 11.4 показан пример микропрограммы, записанной на языке ГСА.

Рис. 11.4. Примерг граф-схемы микропрограммы

В примере микрокоманда Y₁ инициирует микрооперации y1 и y6 микрокоманда Y₂ –микрооперацию y₂ ,а Y₃ –микрооперации y₃ , y₄ y₅ и y₇