Способы описания алгоритмов и микропрограмм

Наиболее наглядно изображать микропрограммы и алгоритмы в виде ориентированного графа, который называют граф-схемой алгоритма (ГСА). Кроме наглядности это дает возможность использовать для анализа и преобразования микропрограмм эффективные методы теории графов. При графическом описании отдельные функции алгоритмов (микрооперации) отображаются в виде условных графических изображений или вершин [3].

Граф микропрограммы состоит из совокупности перечисленных вершин и дуг, соединяющих выходы одних вершин с входами других. Соединение вершин и направление дуг графа определяют исходя из алгоритма операции, описываемого графом, и структуры операционного автомата. Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать следующим условиям:

1. В графе должна быть только одна начальная и одна конечная вершина.

2. В любую вершину графа должен вести, по крайней мере, один путь из начальной вершины.

3. Из каждого выхода любой вершины графа должен существовать, по крайней мере, один путь в конечную вершину.

4. При всех возможных значениях логических условий и используемых слов должен существовать путь из начальной вершины в конечную вершину.

На основе данных микрокоманд и производится разработка графа микропрограммы. Граф микропрограммы представляет собой ориентированный граф, содержащий одну начальную, одну конечную и произвольное множество промежуточных вершин - операторных и условных. Операторная вершина соответствует одной микрокоманде, а условная - проверяемому логическому условию (флагу). При построении графа микропрограммы необходимо руководствоваться следующими правилами:

1. входы и выходы различных вершин соединяются дугами с указанием направления передачи информации;

2. каждый выход соединяется только с одним входом;

3. для любой вершины графа существует, по крайней мере, один путь из нее к конечной вершине.

ГСА называется содержательной (рис. 4.13), если внутри вершин записаны в явном виде микрооперации и логические условия. Если же каждую микрооперацию обозначить символом , a логические условия через , то получится так называемая кодированная ГСА (рис. 4.14). Для правильного восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо знать соответствия между , и содержанием соответствующих микроопераций и логических условий.

Абстрактный синтез микропрограммного автомата по ГСА осуществляется в два этапа: a) получение отмеченной ГСА; b) построение графа автомата или таблиц переходов и выходов. Одну и ту же ГСА можно представлять как автоматом Мили, так и автоматом Мура.

Дата добавления: 2015-07-08