Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 116 стр.

      Глава 5. Структурный синтез систем
микропрограммного управления (МПУ), заданных
                 моделью НДА

      Если исходный алгоритм работы управляющего автомата (УА)
представлен моделью НДА, то после его детерминизации структуру УА
можно построить на основе использования известных классических методов
структурного синтеза детерминированных конечных автоматов. В
соответствии с этим методом выполняют два основных этапа структурного
синтеза УА: кодирование внутренних состояний УА, представленных в
процессе детерминизации в виде сочетаний частных S-событий НДА, и
построение функций возбуждения и функций выходов для принятой системы
элементов памяти УА. Использование такого классического метода
структурного синтеза УА приводит к тому, что исходная информация об
алгоритме управления, представленная в компактной форме в виде НД СКУ
для S-событий, дважды преобразуется: первый раз при выполнении
детерминизации и второй раз при кодировании внутренних состояний УА,
полученных в результате детерминизации. Такое двойное преобразование
исходной НД СКУ приводит к следующим негативным явлениям:
      а) «Теряется» исходная информация о реализуемом алгоритме
управления, представленном в результате преобразований в виде СКУ для Q-
событий, что затрудняет впоследствии выполнение контрольных и
диагностических процедур на различных этапах как при проектировании УА,
так и при его изготовлении и эксплуатации.
      б) Функции возбуждения элементов памяти, представленные в виде
СКУ для Q-событий, сильно усложняются по сравнению с исходной НД СКУ
для S-событий. Это объясняется тем обстоятельством, что сложность СКУ
для Q-событий, полученных после детерминизации исходного алгоритма
управления, значительно увеличивается по сравнению со сложностью
исходной СКУ для S-событий. Например, для УА, заданного ГСАП (рис.4.6),
сложность булевых функций, определяющих СКУ для Q-событий, примерно
в 5 раз выше сложности булевых функций, представляющих исходную СКУ
для S-событий, если выполнить оценку сложности булевых функций по
Квайну.
      Учитывая отмеченные выше недостатки использования классического
метода синтеза для построения структуры УА, заданного моделью НДА, в
данном разделе будут рассмотрены другие подходы и методы построения
структур УА, заданных моделью НДА, позволяющие в той или иной степени
не только избежать отмеченных выше недостатков использования
классического метода синтеза структур УА, заданных моделью НДА, но и
развить новые более эффективные методы, которые вытекают (следуют) из
достоинств представления управляющих алгоритмов моделью НДА. К числу

                                                                      116