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

                              Найдена любая цепочка
                                      sк1∨ sк2∨ sк3

                          sк1=           sк2=            sк3=

                         s1&z1          s4&z2          s5&z1

                             s1=          s4=            s5=

                     s2&z2         s1&z2 s0&z3 s0&z3        s6&z3

                       s2=                                      s6=

                      s0&z1                                 s5&z2
                    Рис. 3.8. Полное функциональное разбиение
  4) при увеличении размерности входных данных возрастает число ЭЗ, а размер Э3 ос-
   тается неизменным, и это обеспечивает масштабируемость алгоритма поиска.

  На втором шаге проектирования параллельного алгоритма определим необходимые
коммуникации между ЭЗ, учитывая что:
  1) входные последовательности и результаты поиска в каждой из них будут храниться
   в одном месте (оперативная память, "винт", и т.п.);

  2) необходимо определить во входных последовательностях любую из трех цепочек, и
   поэтому при обнаружении какой либо цепочки в любой последовательности алгоритм
   завершается.
   Определим необходимые коммуникации при разбиении алгоритма по данным (рис.
3.9). При разбиении входной последовательности на блоки коммуникации будут анало-
гичными (при отсутствии итераций).
     П о с лед о в атель н о с ть 1                   Поиск           Р ез уль тат 1
                                                      …
     П о с лед о в атель н о с ть 10                  Поиск           Р ез уль тат 10
               Рис. 3.9. Коммуникации при разбиении алгоритма по данным
     Определим необходимые коммуникации при разбиении алгоритма по функциям.
При разбиении алгоритма по функциям поиска каждой цепочки коммуникации приведе-
ны на рис. 3.10:




                                            28