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

микроопераций в полях операционной части микрокоманд, который основан
на построении матрицы включения при использовании вспомогательной
матрицы совместимости микроопераций [2, 21, 47].
В нашем случае вспомогательная матрица совместимости частных S-
событий, строится на основе учета вхождения частных событий в полные a-
события и будет иметь вид (рис. 5), где ,=0, если S и S несовместимы;
,=1, если S и S совместимы.

                     S1      S2            S            Sn
               S1     0     1,2    …     1,    …     1,n
               S2    2,1    0      …     2,    …     2,n

               S    ,1   ,2    …     ,    …     ,n

               Sn    n,1   n,2    …     n,    …      0

             Рис. 5.5. Матрица совместимости частных событий
В матрице включения (рис. 5.6) после завершения ее построения каждая i-я
строка будет содержать подмножество тi частных несовместимых событий,
размещаемых в одной группе, а каждый столбец матрицы должен включать
только одно частное событие, это следует из условий (5.3), где Pi,=1, если
Smi; Pi,=0, если Smi.
                     S1      S2            S            Sn
               m1    P1,1   P1,2    …     P1,    …     P1,n
               m2    P2,1   P2,2    …     P2,    …     P2,n

               mi    Pi,1   Pi,2    …     Pi,    …     Pi,n

              mH     PH,1   PH,2    …     PH,    …     PH,n
      Рис. 5.6. Матрица включения частных событий в группы
                     несовместимых событий

Матрица включения строится постепенно по шагам, число которых равно
числу всех частных событий п. При этом для облегчения решения задачи на
каждом шаге используется вспомогательная матрица совместимости частных
событий (см. рис. 5.5).
На каждом шаге построения матрицы включения для очередного частного
события, например, инициируемого S , отыскивается такое подмножество
частных событий, для которого рассматриваемое частное событие S ни с
одним из частных событие этого подмножества не совместимо. Если такое
подмножество частных событий найдено, то в него включается

                                                                          124