Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

Глава четвертая

ГРАФ-СХЕМЫ АЛГОРИТМОВ

4 -1. Микропрограммы работы дискретных устройств

При описании работы широкого класса дискретных систем автома­ тики, вычислительной техники и телефонии в большинстве случаев оказывается удобным представить эти системы в виде двух частей: операционного устройства и устройства управления. Так, в вычисли­ тельной машине к операционному устройству относят блоки памяти, регистры, сумматоры, каналы передачи информации, шифраторы и дешифраторы, а к устройству управления — ту часть машины, кото­ рая, координируя действия всех перечисленных устройств, определяет последовательность переработки информации. Задачей устройства управления является, таким образом, выработка распределенной во времени последовательности управляющих сигналов, под воздейст­ вием которых в операционном устройстве осуществляется некоторая операция. Иногда целесообразно многоступенчатое представление дискретной системы. Так, в одних случаях, например при. проектиро­ вании центрального устройства управления ЦВМ, арифметическое устройство (АУ) в целом рассматривается как часть операционного устройства, тогда как при проектировании самого АУ в нем выде­ ляется свой автомат управления, а к операционной части АУ отно­ сятся его регистры, сумматор, регистр кодов арифметических опера­ ций и счетчик сдвигов.

Задача синтеза операционных устройств вследствие их регуляр­ ности и большой повторяемости в настоящее время хорошо изучена и не представляет серьезных трудностей. Иначе обстоит дело с уст­ ройством управления, которое является наименее регулярной частью дискретной системы и совершенно не повторяется при переходе от од­ ной системы к другой. В связи с этим проектирование устройства уп­ равления представляет наибольшую сложность и, более того, часто проектирование системы после выбора основных частей операцион­ ного устройства сводится, в основном, к проектированию устройства управления.

Порядок выполнения операций в дискретном устройстве опреде­ ляется микропрограммой, представляющей собор совокупность мик­ роопераций и логическихусловий. Под микрооперацией мы будем понимать элементарный процесс переработки информации в дискрет­ ной системе или какой-либо ее части, происходящий за время одного такта работы автомата (промежуток между двумя последовательными моментами дискретного автоматного времени) [7]. Для выполнения той или иной микрооперации устройство управления должно выраба­ тывать управляющие сигналы, которые будем называть сигналами микроопераций и обозначать строчными буквами с индексами: y lt . . . , уп, . . . , yN. Если в устройстве одновременно реализуется несколько микроопераций, то это множество микроопераций назовем микроко­ мандой и будем обозначать прописной буквой Y с индексами. Так, если Y t = \уп , . . . , уш, . . . , уш ] — микрокоманда, то микроопе-

53

рации уп , . . . , уи,, ■■■, ijtu выполняются одновременно в один и тот же момент автоматного времени. При U — 1 микрокоманда Y, со­ стоит из одной микрооперации. Не исключен случай U = О, когда множество микроопераций, образующих микрокоманду, пусто. Микро­ команду, состоящую из пустого множества микроопераций, будем обо­ значать символом Y 0. Реализация такой микрокоманды равносильна отсутствию выполнения каких-либо элементарных операций. В слу­ чае синхронных дискретных устройств микрокоманду К0 удобно ин­ терпретировать как пропуск такта, когда не поступают никакие сиг­ налы от устройства управления к операционному устройству.

Выполнение микропрограммы состоит в последовательном выпол­ нении отдельных микрокоманд. Эта последовательность определяется

ния. Если в микропрограмме все микрокоманды различны (а если это не так, то их всегда можно перенумеровать), то каждой паре микро­ команд К,-, Yj (не исключен случай і = у) соответствует функция сс,-,-, равенство единице которой разрешает выполнение микрокоманды Y; после завершения выполнения микрокоманды У). Очевидно, что среди множества функций а п , . . . ,- <xiR (R — число различных микроко­ манд в микропрограмме) в каждый момент времени не может быть бо­ лее одной, равной единице. В противном случае процесс реализации микропрограммы не был бы детерминированным, т. е. нельзя было бы с определенностью сказать, какая из микрокоманд будет выполняться в следующий момент времени после микрокоманды Yt.

Для записи микропрограмм работы дискретных устройств будем использовать язьік граф-схем алгоритмов и логических схем алго­ ритмов.

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

Граф-схема алгоритма (ГСА) — ориентированный связный граф, содержащий вершины четырех типов: начальную, конечную, опера­ торную и условную (рис. 4-1).

Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. Начальная и операторные вершины имеют по одному выходу, а условная — два выхода, поме­ ченных символами 1 и 0. Конечная вершина выходов не имеет. ГСА удовлетворяет следующим условиям:

1. Содержит конечное число вершин, каждая из которых принад­ лежит одному из перечисленных выше типов.

2.Имеет одну начальную и одну конечную вершины.

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

4.Каждый выход соединен только с одним входом.

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

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

54

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

8.В каждой условной вершине записывается один из элементов множества X = {хг, . . . , xh . . . , xL), называемого множеством ло­ гических условий. Разрешается в различных условных вершинах за­ пись одинаковых элементов множества X.

9.В каждой операторной вершине записывается оператор (микро­

в различных операторных вершинах одинаковых подмножеств мно­ жества микроопераций.

При большом числе дуг, приходящих на один вход вершины, на­ глядность графического изображения может потеряться, в связи с чем позволим изображать дуги, входящие в вершины, так, как показано на рис. 4-2.

торы Уф, . . . , Y т— все разные, так что операторную вершину можно отождествить с записанным в ней оператором. Начальной вершине

(4-1); х\г= хіг\ х°іг = хіг.

1 Слова «микрокоманда» и «оператор» при описании .ГСА рассматриваются как синонимы. В случае содержательных граф-схем алгоритмов (см. следующий параграф) всегда будем использовать термин «микрокоманда», что чаще встре­ чается в литературе, например в [7].

55

Если между вершинами У,- и Уу имеется несколько (например, Н)

Рис. 4-3. Пример ГСА

тональным (а,-уа;/; О; /г = 1............Т -|- 1) и полным V а,-у= 1 •

Полное ортогональное множество функций называют нормальным [8 ]. Всевозможные наборы значений переменных а^ и. . . , xL обозна­ чим через Др . . . , Д2і.. Определим процесс выполнения ГСА, начи­

ная с оператора У0 (начальный оператор) на произвольной бесконеч­ ной последовательности наборов Дт1, . . . , Amq, . . . следующим об­ разом1:

56