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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

215
y=S
к1
S
к2
S
к3
y
f
=S
f
Далее выполним разработку параллельного алгоритма в следующей
последовательности.
На первом шаге проектирования параллельного алгоритма
производим разбиение алгоритма по данным и функциям поиска цепочек.
Разбиение по данным. Поскольку задача поиска цепочек в заданной
последовательности символов в своей основе последовательна, то разбить
последовательность символов на части не представляется возможным.
Поэтому данные могут быть разбиты только по числу входных
последовательностей (П
i
) символов. В нашем случае будет 10 задач (рис.7.1).
П 1
10 б
П 2
10 б
П 3
20б
П 4
20 б
П 5
3 0 б
П 6
30 б
П 7
30 б
П 8
30б
П 9
40 б
П 10
4 0 б
Рис. 7.1. Разбиение по данным
На следующем более низком уровне декомпозиции можно разбить
каждую из последовательностей на блоки одинаковой длины (за
исключением возможно последнего блока). И, казалось бы, в предельном
случае минимальный размер блока может достигнуть 1 символа. На самом
деле его длина не может быть выбрана любой, т. к. при выборе произвольной
длины блока возможен случай, при котором часть цепочки окажется в одном
блоке, а другая часть - в другом блоке. Тогда при поиске в каждом из этих
блоков цепочка не будет обнаружена. Если выбирать длину блока в
зависимости от максимальной длины искомой цепочки-образа можно
избежать этого. Максимальная же длина цепочки-образа является
постоянной для конкретного алгоритма поиска и поэтому при определении её
длины не возникает трудностей. Необходимо учесть еще и то, что брать
блоки данных из последовательности нужно с перекрытием, то есть начало
следующего блока должно захватывать часть предыдущего, как показано на
рис 7.2
Блок 1
Блок 1
Блок 2
Блок 3
Последовательность
перекрытия
перекрытия
     y=Sк1  Sк2  Sк3
     yf=Sf
     Далее выполним разработку параллельного алгоритма в следующей
последовательности.
     На первом шаге проектирования параллельного алгоритма
производим разбиение алгоритма по данным и функциям поиска цепочек.
     Разбиение по данным. Поскольку задача поиска цепочек в заданной
последовательности символов в своей основе последовательна, то разбить
последовательность символов на части не представляется возможным.
Поэтому данные могут быть разбиты только по числу входных
последовательностей (Пi) символов. В нашем случае будет 10 задач (рис.7.1).
                     П1     П2      П3     П4     П5
                     10б    10б     20б    20б    30б
                     П6     П7      П8     П9    П 10
                     30б    30б     30б    40б   40б

                      Рис. 7.1. Разбиение по данным
      На следующем более низком уровне декомпозиции можно разбить
каждую из последовательностей на блоки одинаковой длины (за
исключением возможно последнего блока). И, казалось бы, в предельном
случае минимальный размер блока может достигнуть 1 символа. На самом
деле его длина не может быть выбрана любой, т. к. при выборе произвольной
длины блока возможен случай, при котором часть цепочки окажется в одном
блоке, а другая часть - в другом блоке. Тогда при поиске в каждом из этих
блоков цепочка не будет обнаружена. Если выбирать длину блока в
зависимости от максимальной длины искомой цепочки-образа можно
избежать этого. Максимальная же длина цепочки-образа является
постоянной для конкретного алгоритма поиска и поэтому при определении её
длины не возникает трудностей. Необходимо учесть еще и то, что брать
блоки данных из последовательности нужно с перекрытием, то есть начало
следующего блока должно захватывать часть предыдущего, как показано на
рис 7.2
             Последовательность


          Блок 1                                      Блок 3
          Блок 1

                                  Блок 2

                                      Область                Область
                                    перекрытия             перекрытия


                                                                        215

Страницы