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

Практически можно отметить два варианта исходных управляющих
алгоритмов, представленных моделью НДА, для которых все частные
события можно разбить на группы несовместимых событий. Для первого
варианта все частные события, представленные в исходном управляющем
алгоритме, в явном виде разбиты на группы несовместимых частных
событий, что соответствует представлению исходного управляющего
алгоритма на языке ГСАП.
      Для второго варианта, в отличие от первого, частные события,
представленные в исходном управляющем алгоритме в явном виде не
разбиты на группы несовместимых событий, и для того чтобы разбить их на
такие группы необходимо выполнить над моделью НДА управляющего
алгоритма некоторые процедуры. К числу таких процедур относятся:
детерминизация НДА, представляющего исходный управляющий алгоритм и
построение матрицы совместимости частных событий и матрицы включения,
на основе которых могут быть получены группы несовместимых частных
событий. Такие процедуры над моделью НДА управляющего алгоритма
будут рассмотрены в последующем разделе.
В данном разделе рассмотрим методику преобразования исходного
управляющего алгоритма, представленного в виде графа рис. 5.1, в
соответствии с которой структуру УА можно представить в виде композиции
из нескольких п/А, каждый из которых реализует одну из групп
несовместимых частных событий.
В дальнейшем будем рассматривать структуру УА, состоящей из n
параллельно работающих п/А , названных в пособии рабочими п/А, каждый
из которых реализует одну из параллельных ветвей алгоритма управления и
одного п/А, названного главным п/А, который реализует последовательную
компоненту алгоритма управления и осуществляет взаимодействие его
параллельных ветвей.
В связи с тем, что параллельные ветви алгоритма управления реализуются
отдельными п/А независимо друг от друга, то в каждую i-ую ветвь алгоритма
управления вводится дополнительная операторная вершина (событие S 0i ),
которая будет играть роль начальной вершины в i-ой ветви. Тогда ГСА для
любого i-го рабочего п/А будет иметь вид (рис. 5.2).




                                                                      119