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

рассматриваемое частное событие S , если оно не найдено, то образуется
новое подмножество частных событий, в которое включается в качестве
первого элемента частное событие S .
Для первого шага построения матрицы включения для S1 имеем только
пустое подмножество частных событий, поэтому для S1 назначают
подмножество m1=[S,0,…,0].
Для второго шага для S2 определяют результат операции пересечения m1 со
второй строкой матрицы совместимости, обозначенной буквой S2 . Если
m1∩S2=, то S2 войдет в т1 , в противном случае образуется новое
подмножество т2=[0,S2,0,...,0].
Для третьего шага для S3 определяют результат операции пересечения т1 и
m2 с третьей строкой матрицы совместимости т1∩S3 и т2∩S3 . Если т1∩S3=
или т2∩S3= , то S3 войдет в т1 (или т2 соответственно). Если результаты
операции пересечения в обоих случаях не равны  , то образуется новое
подмножество т3, ; если же эти результаты в обоих случаях равны  , то
возможно включение в одно из подмножеств т1 или т2 . Последним шагом
для Sn завершится построение матрицы включения, и может быть коррекция
(перераспределение) состава подмножеств несовместимых частных событий
mi , если в процессе построения матрицы включения выявилась возможность
отнести очередное частное событие S в одно из нескольких подмножеств.
Коррекция состава подмножеств mi позволит в дальнейшем при структурном
синтезе полнее использовать кодовые группы для частных событий,
входящих в подмножество mi с учетом того, что с точки зрения минимизации
оборудования наиболее выгодным является разбиение всех частных событий
на равные по числу событий в подмножествах mi .
Проиллюстрируем методику разбиения частных событий на группы
несовместимых событий на примере, когда исходный управляющий
алгоритм представлен НД СКУ для S-событий.
П р и м е р 5.1. Выполнить разбиение частных событий на группы
несовместимых событий для управляющего алгоритма, заданного моделью
НДА на основе НД СКУ для S-событий.
В качестве примера такого управляющего алгоритма для иллюстрации
методики разбиения частных событий на группы несовместимых событий
будем использовать НД СКУ (4-69) из раздела 4.5.3, условно предполагая,
что она получена не по ГСАП, а на основе какого-то другого начального
языка, для которого управляющий алгоритм в явном виде не выявляет
параллельные ветви алгоритма.
Используя результаты детерминизации исходной НД СКУ, представленные в
табл. 4.8, (раздел 4.5.3), построим вспомогательную матрицу совместимости
частных событий, которая будет иметь следующий вид:
                  S1   S2   S3   S4   S5   S6   S7   Sk1 Sk2 Sk3
             S1   0    0    0    1    1    1    1     0   1   1

                                                                       125