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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

97
k
cc
p
ek
n
ke
m
AAxAAxxA ......
0
.
Учитывая отмеченные замечания по определению выражения для
частного входного сигнала
ji
X
,
, для заданного фрагмента ЛСА получим:
первый путь -
xxX
mji,
к оператору перехода
n
A
;
второй путь -
pmji
xxX
,
к оператору перехода
ε
A
;
третий путь -
pmji
xxX
,
к оператору перехода
k
A
;
четвертый путь -
xxX
mji,
к оператору перехода
A
.
Если в ЛСА имеется безусловный переход, например для фрагмента
ЛСА
p
kk
AA
...
, то путь от исходного оператора
A
до конечного в
конце пути определится концом стрелки безусловного перехода. В данном
случае
1
,
ji
X
.
3) Пункты 2, 4 и 5 алгоритма полностью совпадают.
П р и м е р 4.7. Построить прямую таблицу переходов автомата Мура и
соответствующую СКУ для ЛСА, эквивалентной ГСА, представленной на
рис. 4.3.
Учитывая условия по введению в ЛСА пустого оператора, там где
имеются петли из логических переменных (логических условий), получим
следующую скорректированную ЛСА:
3
3
3
2
2
1
1
2
2
2
3
1
1
0
0
)()()()()( yAxxyAyAyAyA
k
e
e
k
0 1 2 3 4
)()()(
5
3
3
45
2
1
4
4
3
1
k
k
yAyAyyAx
5 7 6
(4.61)
Разметив операторы ЛСА (4.61) таким же образом, как и в ГСА на рис.
4.3., дальнейший ход решения поставленной задачи с учетом замечаний по
определению всех путей из исходных операторов и соответствующих
выражений для
ji
X
,
полностью совпадает с решением аналогичной задачи на
основе ГСА.
4.5. Язык операторных схем алгоритмов с
параллельными ветвями (ОСАП)
4.5.1. Общие сведения о языке ОСАП
Возможность формального описания параллельно выполняемых во
времени ветвей алгоритма значительно способствует увеличению
выразительных средств любого начального языка. Однако параллельные
алгоритмы обладают большим разнообразием по сравнению с обычными, что
существенно затрудняет осмысливание и правильный учет всех факторов,
связанных с параллельно протекающими процессами и их взаимодействием. 
A0 xm e x  k An  k A ...  e x p c A ... c Ak .
     Учитывая отмеченные замечания по определению выражения для
частного входного сигнала X i , j , для заданного фрагмента ЛСА получим:
       первый путь                    - X i, j  xm x        к оператору перехода An ;
       второй путь                    - X i , j  xm x p      к оператору перехода Aε ;
       третий путь                    - X i, j  xm x p       к оператору перехода Ak ;
       четвертый путь                 - X i, j  xm x        к оператору перехода A .
     Если в ЛСА имеется безусловный переход, например для фрагмента
ЛСА A   k ...  k A p , то путь от исходного оператора A до конечного в
конце пути определится концом стрелки безусловного перехода. В данном
случае X i , j  1 .
      3) Пункты 2, 4 и 5 алгоритма полностью совпадают.
      П р и м е р 4.7. Построить прямую таблицу переходов автомата Мура и
соответствующую СКУ для ЛСА, эквивалентной ГСА, представленной на
рис. 4.3.
      Учитывая условия по введению в ЛСА пустого оператора, там где
имеются петли из логических переменных (логических условий), получим
следующую скорректированную ЛСА:
A0 ( y0 ) A1 ( y1 )  3 A2 ( y 2 )  k  2 Ae ( ye )  k x1 1 x2  2 A3 ( y3 )  3
0        1            2                   3                           4
                                                                                        (4.61)
1 x3  4 A4 ( y1 y 2 ) 5  4 A3 ( y3 ) 5 Ak ( y k )
             5                    7           6
       Разметив операторы ЛСА (4.61) таким же образом, как и в ГСА на рис.
4.3., дальнейший ход решения поставленной задачи с учетом замечаний по
определению всех путей из исходных операторов и соответствующих
выражений для X i , j полностью совпадает с решением аналогичной задачи на
основе ГСА.
             4.5. Язык операторных схем алгоритмов с
                  параллельными ветвями (ОСАП)
                       4.5.1. Общие сведения о языке ОСАП
       Возможность формального описания параллельно выполняемых во
времени ветвей алгоритма значительно способствует увеличению
выразительных средств любого начального языка. Однако параллельные
алгоритмы обладают большим разнообразием по сравнению с обычными, что
существенно затрудняет осмысливание и правильный учет всех факторов,
связанных с параллельно протекающими процессами и их взаимодействием.


                                                                                                 97

Страницы