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

      Предлагаемый в данном разделе язык ОСАП базируется на
расширении синтаксиса известных языков ГСА и ЛСА, а также на
использовании модели НДА и стандартного языка СКУ для описания всех
частных событий. Основные идеи рассматриваемого языка ОСАП изложены
в работах автора в [2, 16-19]. Выбор такого базиса для языка ОСАП вытекает
из следующих предпосылок. Использование модели НДА позволяет
описывать параллельные ветви алгоритма в виде частных СКУ независимо
друг от друга на основе обычных ГСА или ЛСА, а взаимодействие
параллельных ветвей и их синхронизацию можно учитывать при построении
общей НД СКУ путем надлежащей формализации событий, определяющих
выход алгоритмического процесса за вершину объединения ветвей и
коррекции частных событий СКУ, полученных для каждой параллельной
ветви.
      Применение НД СКУ для формализации взаимодействия параллельных
ветвей, а при необходимости и детерминированной СКУ позволяет снять
многие ограничения на виды и условия взаимодействия параллельных
ветвей, отмеченные в ряде работ. Например, в [43] конечные члены каждой
параллельной ветви формализуемого алгоритма должны оканчиваться
одновременно; в [39] алгоритмы не должны содержать циклы; в [40]
ограничиваются рассмотрением параллельных ветвей, представленных двумя
частными видами ГСА; в [41] предлагаемый язык характеризуется
ограниченными       возможностями      по    организации     взаимодействия
параллельных ветвей.
      Предлагаемый язык ОСАП, обладая сравнительно широкими
выразительными возможностями, позволяет также использовать многие
результаты по синтезу цифровых автоматов, полученные до настоящего
времени, например, в [26, 42] и др.
      Дальнейшее изложение основных положений языка ОСАП будем вести
на основе использования языка ГСА в связи с его большей наглядностью по
сравнению с языком ЛСА. Учитывая это обстоятельство будем сокращенно
обозначать язык ОСАП на основе языка ГСА через ГСАП.
        4.5.2. Основные конструкции, вводимые в язык ГСАП
      Для описания параллельных ветвей алгоритма и их взаимодействия в
язык ГСА вводятся дополнительные вершины, указывающие места
разветвления и объединения параллельных ветвей: разветвители и
соединители.
      Разветвителю в ГСАП будет соответствовать разветвительная вершина
(рис. 4.4) обозначаемая буквой F , которая имеет один вход и n выходов,  -
номер вершины.




                                                                          98