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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

217
3) функции, соответствующие операциям при вычислении правой
части уравнения НДСКУ.
Разбиение алгоритма по функциям поиска каждой цепочки приведено
на рис.7.3.
П о и с к
ц е п о ч к и
1
П о и с к
ц е п о ч к и
3
П о и с к
ц е п о ч к и
2
Рис. 7.3. Разбиение по функциям поиска цепочек
На следующем уровне функцию поиска отдельной цепочки можно
разбить по функциям вычисления уравнений НД СКУ. Например, поиск
цепочки 1 состоит в вычислении следующих уравнений: S
к1
=S
1
z
1
;
S
1
=S
2
z
2
S
1
z
2
; S
2
=S
0
z
1
и соответствующее разбиение приведено на рис.7.4.
У р а в н е н и е
д л я
S
к 1
У р а в н е н и е
д л я
S
2
У р а в н е н и е
д л я
S
1
Рис.7.4. Разбиение по функциям вычисления уравнений
Далее, на следующем уровне иерархии, возможно разбиение
вычислений правых частей уравнений. Например, уравнение для S
1
можно
разбить на функции: конъюнкции, дизъюнкции и присвоения (рис.7.5).
z
2
&
S
3
z
2
&
S
1
S
1
=
Рис.7.5. Разбиение правой части для S
1
В конечном итоге полное функциональное разбиение будет
представлять собой дерево (рис.7.6), корнем которого будет определение
вхождения какой-либо цепочки во входную последовательность, а далее
соответственно по ярусам – нахождение конкретной цепочки, затем
вычисление уравнений НД СКУ для этой цепочки и затем вычисление их
правых частей. На рисунке не приведено разбиение по функциям при
вычислении уравнения S
f
, т.к. при практической реализации алгоритма
достаточно проверять входной сигнал на равенство "bottom", и в случае
обнаружения конца последовательности завершать алгоритм поиска. Из
рассмотрения этого дерева хорошо видно, что на нижнем уровне
выполняется операция конъюнкции, затем дизъюнкции и затем присвоения.
Таким образом, в результате разбиения алгоритма по функциям получаются
следующие элементарные задачи: 
      3)    функции, соответствующие операциям при вычислении правой
части уравнения НДСКУ.
      Разбиение алгоритма по функциям поиска каждой цепочки приведено
на рис.7.3.
                  Поиск          Поиск                Поиск
                 цепочки        цепочки              цепочки
                    1              2                    3

              Рис. 7.3. Разбиение по функциям поиска цепочек
      На следующем уровне функцию поиска отдельной цепочки можно
разбить по функциям вычисления уравнений НД СКУ. Например, поиск
цепочки 1 состоит в вычислении следующих уравнений: Sк1=S1z1;
S1=S2z2S1z2; S2=S0z1 и соответствующее разбиение приведено на рис.7.4.
          У р ав нени е       У р ав нени е            У р авн ени е
            д л я S к1           для S1                   для S2

          Рис.7.4. Разбиение по функциям вычисления уравнений
     Далее, на следующем уровне иерархии, возможно разбиение
вычислений правых частей уравнений. Например, уравнение для S1 можно
разбить на функции: конъюнкции, дизъюнкции и присвоения (рис.7.5).
                                       S1=

                                       

                               z2&S3         z2&S1

                   Рис.7.5. Разбиение правой части для S1
      В конечном итоге полное функциональное разбиение будет
представлять собой дерево (рис.7.6), корнем которого будет определение
вхождения какой-либо цепочки во входную последовательность, а далее
соответственно по ярусам – нахождение конкретной цепочки, затем
вычисление уравнений НД СКУ для этой цепочки и затем вычисление их
правых частей. На рисунке не приведено разбиение по функциям при
вычислении уравнения Sf, т.к. при практической реализации алгоритма
достаточно проверять входной сигнал на равенство "bottom", и в случае
обнаружения конца последовательности завершать алгоритм поиска. Из
рассмотрения этого дерева хорошо видно, что на нижнем уровне
выполняется операция конъюнкции, затем дизъюнкции и затем присвоения.
Таким образом, в результате разбиения алгоритма по функциям получаются
следующие элементарные задачи:



                                                                          217

Страницы