Объединение граф-схем алгоритмов

26 ОБЪЕДИНЕНИЕ ГРАФ-СХЕМ АЛГОРИТМОВ

26.1 Алгоритм построения объединенной ГСА

При описании работы сложной системы целесообразно построить несколько ГСА, каждая из которых описывает часть общего поведения системы (частные ГСА).

Например, при проектировании устройства управления арифметическим устройством более просто построить отдельные частные ГСА алгоритмов сложения, вычитания, умножения, деления и. т. д.

Ясно, что в частных ГСА некоторые операторные и условные вершины будут одинаковыми, и если для каждой ГСА синтезировать отдельный управляющий автомат (ЦА), то результат синтеза будет не оптимальным.

Более выгодно построить на основе нескольких частных ГСА одну общую объединенную ГСА.

Второй подход, как правило, позволить минимизировать суммарное число операторных и условных вершин и упростить схему ЦА.

Имеющиеся оценки сложности реализации микропрограммного автомата Мура показывают, что сложность схемы автомата Мура, состоящего из пяти подсхем (схемы изменения состояний, памяти, дешифратора состояний, схемы выработки управляющих сигналов и схемы анализа осведомительных сигналов) зависит от числа состояний автомата S, числа ребер (переходов) L и количества условных вершин р на ГСА и общего числа М управляющих сигналов.

Сложность комбинационной части автомата Мура определяется следующей формулой:

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

Для построения объединенной ГСА (ОГСА) используется алгоритм, основанный на применении матричных схем алгоритмов (МСА).

Если внутри отдельных частных ГСА встречаются одинаковые операторные вершины, то перед началом объединения они должны быть переобозначены. Между различными ГСА_P и ГСА_q могут быть одинаковые операторные вершины.