Матричні схеми алгоритмів
Граф-схеми алгоритму (ГСА)
Алгоритм функціонування МПУ можна задати і ДСА. ДСА являє собою сукупність вершин і зв'язків між ними і визначає порядок виконання мікрокоманд, що становлять микропрограмму однієї або кілька закінчених операцій. ДСА може інтерпретувати як граф переходів автоматів.
При цьому в якості елементів графа використовуються:
1) початкова і кінцева вершини
2) операційні вершини
3) умовні вершини
де Yi - мікрокоманда (оператор),
Початок виконання прошивки визначається рухом по стрілці від початкової вершини.
Існують правила побудови ДСА. Їх шість:
1. З початкової і з операторних вершин повинен бути тільки один вихід.
2. Всі вершини, крім початкової мають тільки один вхід.
3. Умовна вершина має два виходи. З умовної вершиною ототожнюється деякий логічне умова, при виконанні якого рух з умовною вершини проводиться по стрілці, поміченої нулем, одиницею.
4. Вихід будь-якої вершини повинен з'єднуватися тільки з одним входом інших вершин.
5. З будь-якої вершини в ДСА повинен бути шлях, що веде в кінцеву вершину;
6. Один з виходів умовної вершини може бути з'єднаний з її входом.
В цьому випадку умовну вершину називають поворотною або що чекає. Здійснимо перехід від МСА, наведеної в таблиці 5.1 до ДСА, рис.5.5.
Yi - оператор (мікрокоманда).
yi - сигнал на виході керуючої
Малюнок 5.5 - Граф схема алгоритму
Проаналізуємо граф-схему алгоритму (рис.5.5).
Мікропрограма описує функціонування деякого операційного пристрою.
У першому такті виконується мікрокоманда Y1. У другому такті в залежності від значень деяких ознак v1. v2. v3 буде реалізована одна з микрокоманд Y2. Y3. Y4. Все мікрокоманд виконуються під впливом керуючих сигналів, вироблюваних керуючим пристроєм (керуючої частиною автомата рис.5.5).
Таким чином, керуюча частина автомата повинна забезпечити виконання в операційній частини ті чи інші операції (наприклад, додавання, множення і т.д.).
Як відомо, результатом проведення абстрактного синтезу є граф закону функціонування керуючої частини цифрового пристрою, яку прийнято називати кінцевим автоматом. Отже, якщо буде отримано цей граф, далі можна проводити структурний синтез кінцевого автомата за відомою методикою.
Синтез керуючої частини можна проводити як по схемі автомата Мілі, так і за схемою автомата Мура. Розглянемо автомат Мілі.
В автоматі Мілі вихідні сигнали формуються в процесі переходу автомата з одного стану в інший. Тому новий стан аi. в яке переходить мікропрограмний автомат Мілі, встановлюється після видачі чергового вихідного сигналу і відзначається на ДСА прошивки на стрілці, що виходить з відповідної операторної вершини.