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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

126
S
2
0 0 0 1 0 1 1 0 0 0
S
3
0 0 0 1 1 1 1 0 1 1
S
4
1 1 1 0 0 1 1 0 0 0
S
5
1 0 1 0 0 1 1 1 0 1
S
6
1 1 1 1 1 0 0 1 1 0
S
7
1 1 1 1 1 0 0 1 1 0
S
k
1
0 0 0 0 1 1 1 0 1 1
S
k
2
1 0 1 0 0 1 1 1 0 1
S
k
3
1 0 1 0 1 0 0 1 1 0
Рис. 5.7. Матрица совместимости частных событий
исходного управляющего алгоритма
На рис. 5.7 не представлены события S
0
и S
8
, которые для данного исходного
управляющего алгоритма не входят ни в одну из совокупностей из трех
частных событий, определяющих a-событие.
Построение матрицы включения частных событий в группы
несовместимых событий будет содержать следующие шаги:
1) Для частного события S
1
подмножество частных несовместимых событий
пусто, поэтому для S
1
назначаем первое подмножество т
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 0 0 0 0 0 0 0 0 0
2) Поскольку S
2
∩m
1
= (здесь и в дальнейшем под первой буквой операции
пересечения понимается номер строки матрицы совместимости, отмеченный
буквой S
2
), то S
2
включается в 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 0 0 0 0 0 0 0 0
3) Поскольку S
3
∩m
1
= , то S
3
включается в 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 0 0 0
4) Поскольку S
4
∩m
1
, то S
4
не включается в m
1
и образуется подмножество
m
2
, в которое войдет S
4
в качестве первого элемента
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 0 0 0
m
2
=
0 0 0 1 0 0 0 0 0 0
5) Поскольку S
5
∩m
1
, a S
5
∩m
2
, то S
5
не войдет в m
1
, а войдет в 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
             S2     0   0   0    1   0    1    1     0   0   0
             S3     0   0   0    1   1    1    1     0   1   1
             S4     1   1   1    0   0    1    1     0   0   0
             S5     1   0   1    0   0    1    1     1   0   1
             S6     1   1   1    1   1    0    0     1   1   0
             S7     1   1   1    1   1    0    0     1   1   0
             Sk 1   0   0   0    0   1    1    1     0   1   1
             Sk 2   1   0   1    0   0    1    1     1   0   1
             Sk 3   1   0   1    0   1    0    0     1   1   0

         Рис. 5.7. Матрица совместимости частных событий
                 исходного управляющего алгоритма

На рис. 5.7 не представлены события S0 и S8 , которые для данного исходного
управляющего алгоритма не входят ни в одну из совокупностей из трех
частных событий, определяющих a-событие.
     Построение матрицы включения частных событий в группы
несовместимых событий будет содержать следующие шаги:
1) Для частного события S1 подмножество частных несовместимых событий
пусто, поэтому для S1 назначаем первое подмножество т1 , включающее пока
один элемент
                    S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
             m1 = 1      0   0    0   0   0   0   0    0    0

2) Поскольку S2∩m1= (здесь и в дальнейшем под первой буквой операции
пересечения понимается номер строки матрицы совместимости, отмеченный
буквой S2), то S2 включается в m1
                     S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
              m1 = 1     1    0   0  0  0    0   0    0   0

3) Поскольку S3∩m1= , то S3 включается в m1
                  S1 S2 S3 S4 S5 S6             S7   Sk1 Sk2 Sk3
            m1=    1    1    1   0   0    0     0     0   0   0

4) Поскольку S4∩m1 , то S4 не включается в m1 и образуется подмножество
m2 , в которое войдет S4 в качестве первого элемента
                    S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
              m 1= 1     1    1    0   0    0   0    0  0   0
              m 2= 0     0    0    1   0    0   0    0  0   0

5) Поскольку S5∩m1 , a S5∩m2 , то S5 не войдет в m1 , а войдет в m2
                  S1 S2 S3 S4 S5 S6 S7 Sk1 Sk2 Sk3
                                                                          126

Страницы