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

5.1.2. Методика разбиения частных событий на группы
несовместимых событий для управляющего алгоритма,
заданного моделью НДА

В том случае, если из исходного управляющего алгоритма, заданного
моделью НДА, не следует в явном виде разбиение частных событий,
представляющих управляющий алгоритм, на группы несовместимых
событий и требуется преобразовать такой алгоритм к виду,
соответствующему обобщенной структуре с параллельными ветвями
(рис.5.1), то для решения этой задачи необходимо использовать специальные
процедуры, позволяющие разбить частные события на группы
несовместимых событий. К числу таких процедур относятся процедура
детерминизации исходного управляющего алгоритма и процедура
построения матрицы включения частных событий в группы несовместимых
событий, которая строится на основе использования вспомогательной
матрицы совместимости частных S-событий.
Как следует из главы 2 в результате детерминизации исходного
управляющего алгоритма, представленного в виде НД СКУ для частных S-
событий, получают все полные а-события, определенные в виде сочетаний
частных S-событий, одновременное существование которых для исходного
управляющего алгоритма возможно.
По полученным а-событиям, учитывая вхождение в них частных S-событий,
все множество последних разбивают на группы, в каждой из которых все
частные события должны быть несовместимыми. Отметим, что под
несовместимыми частными событиями понимаются события, которые не
входят совместно ни в одно из полных a-событий. Число таких групп
несовместимых частных событий должно быть не менее максимального
числа частных событий, входящих в отдельные полные a-события.
При решении задачи распределения частных событий на группы
несовместимых событий необходимо руководствоваться двумя условиями:
                   mi  m j  , i  j , i, j  1, H
                                                                 (5.3)
                   m1  m2  ... mH  n
где тi - подмножество частных событий, входящих в i-ю группу
несовместимых частных событий,
Н- число всех групп несовместимых частных событий;
п - число всех частных S-событий, представленных в исходном управляющем
алгоритме.
Первое условие (5.3) обеспечивает требование несовместимости частных
событий, входящих в любые пары из Н групп. Второе условие обеспечивает
включение каждого из всех п частных событий в какую-либо из H групп.
Такой способ размещения частных событий, входящих в исходный
управляющий алгоритм, аналогичен способу размещения кодов

                                                                         123