Проектирование параллельных алгоритмов в задачах идентификации. Вашкевич Н.П - 20 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

20
3 Применение методики для задач идентификации
Рассмотрим решение задачи, в которой требуется за один просмотр каждой входной
последовательности символов, заканчивающейся "bottom", идентифицировать наличие
хотя бы одной из искомых цепочек-образов. Количество последовательностей символов
(S) равно 10. Длины последовательностей символов равны 10(2),20(2),30(4),40(2), т.е. две
последовательности по 10 символов, две последовательности по 20 символов и т.д. Число
процессоров в системе (Р) равно 4. Входной алфавит 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
. Хранение входных последовательностей сим-
волов и результатов поиска цепочек в них производится в одном источнике и одном при-
емнике. Необходимо выполнить проектирование на событийном уровне параллельного
алгоритма решения этой задачи и его исследование. Для разработки параллельного алго-
ритма рекомендуется выполнить следующие этапы проектирования.
3.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
0
∨s
к1
∨s
к2
∨s
к3
∨s
1
∨s
2
∨s
3
∨s
4
∨s
5
∨s
6
∨s
f
)&bottom
СВФ:
y=s
к1
∨s
к2
∨s
к3
y
f
=s
f
.
Чтобы убедиться в правильности алгоритма, необходима его отладка с использова-
нием тестирования. Для этого удобно использовать систему отладки и моделирования па-
раллельных алгоритмов "СОМПА" (смотри раздел 4). “СОМПА” позволяет эффективно
довести алгоритм до работоспособного состояния. Какие преимущества дает использова-
ние этой системы? В окне стандартного редактора для приложений ОС WINDOWS вво-
дится алгоритм на РВАС. По нажатию кнопки выполняется преобразование с языка РВАС
на НДСКУ, при этом выявляются синтаксические ошибки в РВАС, которые сразу же
можно отредактировать. Этот процесс повторяется до устранения всех синтаксических 
                    3 Применение методики для задач идентификации
      Рассмотрим решение задачи, в которой требуется за один просмотр каждой входной
последовательности символов, заканчивающейся "bottom", идентифицировать наличие
хотя бы одной из искомых цепочек-образов. Количество последовательностей символов
(S) равно 10. Длины последовательностей символов равны 10(2),20(2),30(4),40(2), т.е. две
последовательности по 10 символов, две последовательности по 20 символов и т.д. Число
процессоров в системе (Р) равно 4. Входной алфавит Z=(z1, ... ,z9). Искомые цепочки-
образы: z1z2z2 ... z2z1; z3z2z1; z3z2z3 ... z2z3z1. Хранение входных последовательностей сим-
волов и результатов поиска цепочек в них производится в одном источнике и одном при-
емнике. Необходимо выполнить проектирование на событийном уровне параллельного
алгоритма решения этой задачи и его исследование. Для разработки параллельного алго-
ритма рекомендуется выполнить следующие этапы проектирования.
 3.1    Разработка алгоритма и рекомендации по его реализации для однопроцессор-
                                           ной системы
      На первом этапе разработаем для однопроцессорной системы алгоритм поиска це-
почек в одной последовательности символов. Алгоритм поиска любой из трех цепочек-
образов можно записать регулярным выражением на языке РВАС:
    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∨s1z2
   s2=s0z1
   sк2=s3z1
   s3=s4z2
   s4=s0z3
   sк3=s5z1
   s5=s0z3∨s6z3
   s6=s5z2
   sf=(s0∨sк1∨sк2∨sк3∨s1∨s2∨s3∨s4∨s5∨s6∨sf)&bottom
   СВФ:
   y=sк1∨sк2∨sк3
   yf=sf.
      Чтобы убедиться в правильности алгоритма, необходима его отладка с использова-
нием тестирования. Для этого удобно использовать систему отладки и моделирования па-
раллельных алгоритмов "СОМПА" (смотри раздел 4). “СОМПА” позволяет эффективно
довести алгоритм до работоспособного состояния. Какие преимущества дает использова-
ние этой системы? В окне стандартного редактора для приложений ОС WINDOWS вво-
дится алгоритм на РВАС. По нажатию кнопки выполняется преобразование с языка РВАС
на НДСКУ, при этом выявляются синтаксические ошибки в РВАС, которые сразу же
можно отредактировать. Этот процесс повторяется до устранения всех синтаксических


                                             20

Страницы