Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

Таким образом, для определения производной от графа по событию необходимо:

а) построить модель,, определяемую заданным событием;

б) найти частотную матрицу отношений, соответствую­ щую этой модели;

в) вычисляя по частотной матрице отношений значения

GM fa, fij и fjj, соответствуют количеству весов вершины Щ, количеству общих весов вершин щ и ѵ} и количеству весов вершины Vj соответственно.

Вычислим, например,

дЮ

четной длины в графе ———= <Ѵ, С/>.

д о і

11

12

Граф -— представлен на рис. 1-6.

О о

döM

Событие в графе —— задает матрицу вида

до

Действуя согласно алгоритму нахождения производной от графа, находим, что

Введенное понятие производной от графа по событию является эффективным средством снижения трудоемкости при синтезе минимальных управляющих автоматов. Понятие производной от графа характеризует однородность компо­ нент графа относительно заданного события и может ха­ рактеризовать Степень отдаления принимаемых решений от минимального решения при синтезе управляющих автоматов.

§ 1-3. Выбор алгоритма, реализующего заданный оператор А

При синтезе устройства ЦВМ обычно задают реализуе­ мый оператор в виде функций, связками в которой являются связки классической математики, например, «+»,, «—», «X», «:». Заданный оператор может быть реализован многими ал­ горитмами. Каждый алгоритм порождает свою композицию операционного и управляющего автоматов.

Следуя В. М. Глушкову [1], напомним, что каждый алго­ ритм можно рассматривать как взаимодействие пары автома­ тов: операционного и управляющего.

13

причем каждый канал может находиться в одном из двух со­ стояний: нулевом или единичном. Состояния входных кана­ лов хі, Х2 ... хп, выходов каналов обратной связи zi+, z2+ ... zs+, входов каналов обратной связи Z\~, z2~ ... zs~ и выходных ка­ налов у 1, у2 ... ут будем характеризовать соответственно век­ торами X, Z+, Zr и Y.

Отображение XZ+~> Z~Y будем называть автоматным, а устройство, реализующее его — автоматом.

Одной из основных характеристик автомата является объем его памяти.

Состояния каналов обратной связи автомата будем назы­ вать внутренними состояниями автомата.

Число внутренних состояний автомата называется объе­ мом памяти автомата.

Как известно, результатом выполнения любого алгорит­ ма является некоторое преобразование информации, при этом акты алгоритма реализуются операционным автоматом, а управляющий автомат осуществляет управление операцион­ ным автоматом согласно алгоритму.

Операционный автомат обладает практически бесконеч­ ным объемом памяти, например, объем памяти регистра дли­ ной в 30 разрядов превышает один миллиард.

В силу того, что объем памяти операционного автомата является практически бесконечным, формализация синтеза операционных автоматов затруднительна, и их синтез прак­ тически осуществляется на основе опыта, а в .случае сложных операционных автоматов —с использованием программного моделирования.

Объем памяти управляющего автомата является практи- . чески конечным, и при их синтезе применяется теория циф­ ровых автоматов.

Рассмотрим взаимодействие этой ' пары автоматов (рис. 1-7). На вход операционного автомата (канал 1) посту­ пает преобразуемая информация, с выхода операционного автомата (канал 2) снимаются результаты преобразований, по каналу 3 поступают управляющие воздействия согласно реализуемому алгоритму, по каналу 4 на вход управляющего автомата поступают значения логических переменных, ха­ рактеризующих преобразуемую информацию, по каналу 5

14

подается сигнал начала данного преобразования, по каналу 6 — сигнал его окончания. Каналы 1, 2 называются информа­ ционными, каналы 3 — 6 — управляющими.

Рассмотрим, например, выполнение арифметическим уст­ ройством (АУ) ЦВМ операции сложения. В данном случае операционным автоматом является арифметическое устрой-

Рис. 1-7

ство, т. е. регистры, сумматор и связи между ними, а управ­ ляющим автоматом — устройство управления АУ. При вы­ полнении алгоритма сложения по каналу 1 из запоминающе­ го устройства (ЗУ) >ЦВМ в соответствующие регистры АУ записываются первое и второе слагаемые, по каналу 5 из центрального устройства управления (ЦУУ) машины посту­ пает код операции («Сложение»), по каналу 3 из управляю­ щего устройства АУ согласно выбранному алгоритму сложе­ ния посылаются управляющие сигналы: сдвиг ре­ гистров, возбуждение соответствующих шин в сумматоре, запись суммы в регистр результата и др.; по каналу 4 посту­ пают значения логических переменных, например, содержа­ ния знаковых разрядов в сумматоре с целью обнаружения нарушения нормализации, определяющего ход дальнейшего управления. По каналу 6 в ЦУУ машины передается сигнал об окончании выполнения операции.

Цифровую вычислительную машину как сложный преоб­ разователь информации целесообразно рассматривать как композицию пар автоматов операционного и управляющего, представляя аналогично арифметическому устройству каждое устройство (устройство ввода, устройство вывода, ЗУ, ЦУУ) как пару или как несколько пар операционного и управляю­ щего автоматов.

15

Синтез устройства вычислительной техники производит­ ся по известным в теории автоматов этапам:

а) этапа алгоритмического синтеза; б) этапа абстрактного синтеза,

в) этапа кодирования внутренних состояний, г) этапа структурного синтеза.

На этапе алгоритмического синтеза заданный оператор А оформляется в виде алгоритма, исходя из удовлетворения заданных требований, в качестве которых могут служить простота выполнения операций, быстродействие, максималь­ ное уменьшение аппаратурных затрат и др. Поиск оптималь­ ного алгоритма по заданному оператору А можно предста­ вить в виде дерева, каждая висячая вершина которого' соот­ ветствует определенному алгоритму, т. е. определенной ком-

Рис. 1-8

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

Пусть, например, необходимо синтезировать арифмети­ ческое устройство, реализующее четырехместную операцию суммирования. В зависимости от выбора алгоритма, реали­ зующего это задание А, получаем определенную блок-схему синтезируемого устройства, характеризующуюся аппаратур­ ными затратами и быстродействием. В данном случае можно предложить, например, три варианта алгоритма: ^

1-й вариант. Суммируем два первых числа, к полученной сумме прибавляем третье число и к вновь полученной сумме прибавляем последнее четвертое число. Этот вариант алго­ ритма характеризуется временем выполнения операции Ті и

16