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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

214
изменение эффективности с ростом размерности исходных данных при
неизменности числа процессоров.
7.2.2. Пример разработки параллельных алгоритмов для
решения задач распознавания цепочек-образов
Рассмотрим задачу, в которой требуется за один просмотр каждой
последовательности символов идентифицировать наличие хотя бы одной из
искомых цепочек-образов [78]. Выполнение задачи завершается при
обнаружении любой цепочки в любой последовательности. Количество
последовательностей символов (S) равно 10. Длины последовательностей
символов равны 10(2),20(2),30(4),40(2), т.е. две последовательности по 10
символов, две последовательности по 20 символов и т.д. Число процессоров в
системе (Р) равно 6. Входной алфавит Z=[z
1
, ... ,z
9
]. Искомые цепочки-образы:
z
1
z
2
z
2
... z
2
z
1
; z
3
z
2
z
1
; z
3
z
2
z
3
... z
2
z
3
z
1
.
Последовательности символов и результаты поиска цепочек в них –
локализованы (в одном месте). Необходимо выполнить проектирование на
событийном уровне параллельного алгоритма решения этой задачи и его
исследование.
Вначале разработаем алгоритм поиска цепочек в одной
последовательности символов для однопроцессорной системы. Алгоритм
можно записать регулярным выражением на языке РВАС:
r(y)=S
0
(z
1
z
2
{z
2
}z
1
z
3
z
2
z
1
z
3
{z
2
z
3
}z
1
).
Разобьем на части:
S
к1
(y)=S
0
z
1
z
2
{z
2
}z
1
S
к2
(y)=S
0
z
3
z
2
z
1
S
к3
(y)=S
0
z
3
{z
2
z
3
}z
1
Перейдем от РВАС к СКУ и СВФ:
СКУ:
S
к1
=S
1
z
1
S
1
=S
2
z
2
S
к1
z
2
S
2
=S
0
z
1
S
к2
=S
3
z
1
S
3
=S
4
z
2
S
4
=S
0
z
3
S
к3
=S
5
z
1
S
5
=S
0
z
3
S
6
z
3
S
6
=S
5
z
2
S
f
=(S
к1
S
к2
S
к3
S
1
S
2
S
3
S
4
S
5
S
6
S
f
) z
b
СВФ: 
изменение эффективности с ростом размерности исходных данных при
неизменности числа процессоров.


    7.2.2. Пример разработки параллельных алгоритмов для
решения задач распознавания цепочек-образов
     Рассмотрим задачу, в которой требуется за один просмотр каждой
последовательности символов идентифицировать наличие хотя бы одной из
искомых цепочек-образов [78]. Выполнение задачи завершается при
обнаружении любой цепочки в любой последовательности. Количество
последовательностей символов (S) равно 10. Длины последовательностей
символов равны 10(2),20(2),30(4),40(2), т.е. две последовательности по 10
символов, две последовательности по 20 символов и т.д. Число процессоров в
системе (Р) равно 6. Входной алфавит Z=[z1, ... ,z9]. Искомые цепочки-образы:
     z1z2z2 ... z2z1; z3 z2z1; z3z2z3 ... z2z3z1.
     Последовательности символов и результаты поиска цепочек в них –
локализованы (в одном месте). Необходимо выполнить проектирование на
событийном уровне параллельного алгоритма решения этой задачи и его
исследование.
     Вначале разработаем алгоритм поиска цепочек в одной
последовательности символов для однопроцессорной системы. Алгоритм
можно записать регулярным выражением на языке РВАС:
     r(y)=S0(z1z2{z2}z1  z3z2z1  z3{z2z3}z1).
     Разобьем на части:
     Sк1(y)=S0z1z2{z2}z1
     Sк2(y)=S0z3z2z1
     Sк3(y)=S0z3{z2z3}z1
     Перейдем от РВАС к СКУ и СВФ:
     СКУ:
     Sк1=S1z1
     S1=S2z2  Sк1z2
     S2=S0z1
     Sк2=S3z1
     S3=S4z2
     S4=S0z3
     Sк3=S5z1
     S5=S0z3  S6z3
     S6=S5z2
     Sf=(Sк1  Sк2  Sк3  S1  S2  S3  S4  S5  S6  Sf) zb
     СВФ:

                                                                          214

Страницы