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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

128
8) Поскольку S
k
1
∩m
1
= и S
k
1
∩m
2
, S
k
1
∩m
3
, то S
k
1
войдет в m
1
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
k
1
S
k
2
S
k
3
m
1
=
1 1 1 0 0 0 0 1 0 0
m
2
=
0 0 0 1 1 0 0 0 0 0
m
3
=
0 0 0 0 0 1 1 0 0 0
9) Поскольку S
k
2
∩m
1
, S
k
2
∩m
3
, а S
k
2
∩m
2
= , то S
k
2
не войдет ни в m
1
,
ни в m
3
, а войдет m
2
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
k
1
S
k
2
S
k
3
m
1
=
1 1 1 0 0 0 0 1 0 0
m
2
=
0 0 0 1 1 0 0 0 1 0
m
3
=
0 0 0 0 0 1 1 0 0 0
10) Поскольку S
k
3
∩m
1
, S
k
3
∩m
2
, а S
k
3
∩m
3
= , то S
k
3
не войдет ни в m
1
,
ни в m
2
, а войдет m
3
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
k
1
S
k
2
S
k
3
m
1
=
1 1 1 0 0 0 0 1 0 0
m
2
=
0 0 0 1 1 0 0 0 1 0
m
3
=
0 0 0 0 0 1 1 0 0 1
11) Поскольку события S
0
и S
8
не совместимы ни с одним из частных событий
исходного управляющего алгоритма (в полные события a
0
и a
25
включаются
только по одному событию S
0
и S
8
соответственно), то они могут войти в
любое из подмножеств m
1
, m
2
, m
3
, либо образовать новое подмножество m
4
.
Таким образом в результате построения матрицы включения получили
следующие группы несовместимых частных событий:
];,[
];,,[
];,,[
];,,,[
804
3
763
2
542
1
3211
SSm
SSSm
SSSm
SSSSm
k
k
k
(5.4)
Полученное в рассмотренном примере разбиение частных событий на
группы несовместимых частных событий полностью соответствует
размещению этих событий на ГСАП, представленным на рис. 4.6. 
8) Поскольку Sk1∩m1= и Sk1∩m2 , Sk1∩m3 , то Sk1 войдет в m1
                  S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
            m 1= 1    1    1   0    0   0   0     1    0   0
            m 2= 0    0    0   1    1   0   0     0    0   0
            m 3= 0    0    0   0    0   1   1     0    0   0

9) Поскольку Sk2∩m1 , Sk2∩m3 , а Sk2∩m2= , то Sk2 не войдет ни в m1 ,
ни в m3 , а войдет m2
                    S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
               m 1= 1  1    1  0     0   0   0     1    0    0
               m 2= 0  0    0  1     1   0   0     0    1    0
               m 3= 0  0    0  0     0   1   1     0    0    0

10) Поскольку Sk3∩m1 , Sk3∩m2 , а Sk3∩m3= , то Sk3 не войдет ни в m1 ,
ни в m2 , а войдет m3
                    S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
               m 1= 1  1    1   0   0     0  0    1     0    0
               m 2= 0  0    0   1   1     0  0    0     1    0
               m 3= 0  0    0   0   0     1  1    0     0    1

11) Поскольку события S0 и S8 не совместимы ни с одним из частных событий
исходного управляющего алгоритма (в полные события a0 и a25 включаются
только по одному событию S0 и S8 соответственно), то они могут войти в
любое из подмножеств m1 , m2 , m3 , либо образовать новое подмножество m4 .
      Таким образом в результате построения матрицы включения получили
следующие группы несовместимых частных событий:
                      m1  [ S1 , S 2 , S 3 , S k1 ];
                      m 2  [ S 4 , S 5 , S k2 ];
                                                                    (5.4)
                      m3  [ S 6 , S 7 , S k3 ];
                      m 4  [ S 0 , S 8 ];
Полученное в рассмотренном примере разбиение частных событий на
группы несовместимых частных событий полностью соответствует
размещению этих событий на ГСАП, представленным на рис. 4.6.




                                                                             128

Страницы