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

       DRIVE_REMOTE             Удаленное (сетевое) устройство
       DRIVE_CDROM              Устройство чтения CD-ROM
       DRIVE_RAMDISK            Электронный диск (RAM)
3.2   Разработка алгоритма и рекомендации по его реализации для многопроцессор-
                                        ной системы
     На втором этапе начнем разработку параллельного алгоритма, используя в качест-
ве основы для его проектирования алгоритм для однопроцессорной системы.
     На первом шаге выполним декомпозицию алгоритма по данным и по функциям.
При этом будем учитывать то, что эти два типа декомпозиции редко используются по от-
дельности, и чаще всего применяется их комбинация.
     Разбиение по данным. На первом (верхнем) уровне можно выполнить разбиение
данных по числу просматриваемых входных последовательностей символов (Пi). В нашем
случае будет 10 таких задач (рис. 3.3).
                        П1       П2       П3       П4     П5
                        10б      10б      20б      20б    30б
                        П6          П7       П8       П9    П10
                        30б        30б       30б     40б    40б
                               Рис. 3.3. Разбиение по данным
      На следующем более низком уровне декомпозиции можно разбить каждую последо-
вательностей на блоки одинаковой длины (за исключением возможно последнего блока).
И, казалось бы, в предельном случае минимальный размер блока может достигнуть 1
символа. На самом деле его длина не может быть выбрана любой, т. к. при выборе произ-
вольной длины блока возможен случай, при котором часть цепочки окажется в одном
блоке, а другая часть - в другом блоке. Тогда при поиске в каждом из этих блоков цепочка
не будет обнаружена. Если выбирать длину блока в зависимости от максимальной длины
искомой цепочки-образа можно избежать этого. Максимальная же длина цепочки-образа
является постоянной для конкретного алгоритма поиска и поэтому при определении её
длины не возникает трудностей. Необходимо учесть еще и то, что брать блоки данных из
последовательности нужно с перекрытием, то есть начало следующего блока должно за-
хватывать часть предыдущего, как показано на рис 3.4
               Последовательность


            Блок 1                                            Блок 3


                                       Блок 2

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

                                        Рис. 3.4




                                          25