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

   Рис.7.10. Коммуникации для разбиения по данным и функционального
                        разбиения по цепочкам

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


          Sк1=S1&z1            Sк2=S3&z1              Sк3=S5&z1

         S1=S2&z2 S1&z2        S3=S4&z2         S5=S0&z3 S6&z3

          S2=S0&z1             S4=S0&z3                S6=S5&z2

    Рис. 7.11. Коммуникации для максимального разбиения по данным и
                  максимального разбиения по функциям

      Полученная при декомпозиции в качестве элементарной задачи
конъюнкция требует для своего выполнения два входных параметра. Этими
входами являются событие si и входной сигнал zj, которые и определяют
коммуникации в алгоритме. Поэтому более детальное рассмотрение
коммуникаций по событиям и по входному сигналу в мультипроцессорной
системе приводит к следующим выводам.
      Вывод 1. В предельном случае (наихудшем) входной сигнал может
потребоваться сразу для всех ЭЗ, поэтому для него разумно организовать
глобальную коммуникацию. В то же время, используемое событие в каждой
ЭЗ своё и поэтому для передачи событий лучше подойдет локальная
коммуникация.
      Вывод 2. И для входных сигналов и для событий коммуникация
получается структурированной. Для входных сигналов это будет дерево, где
корнем является входной сигнал, а ветвями - все Э3. Для событий структура
коммуникаций будет представлять собой дерево, в корне которого будут
события, определяющие наличие какой-либо цепочки во входной
последовательности, далее события, определяющие наличие конкретной
цепочки, и наконец, события определяющие текущее состояние поиска этой
цепочки.
      Вывод 3. Т.к. при выполнении алгоритма поиска цепочки-образы не
могут быть изменены, то коммуникации будут статическими.
      Вывод 4. Если организовать мультипроцессорную систему, на которой
будет выполняться алгоритм, таким образом, что интервалы времени между
поступлениями очередных входных сигналов будут равны, то возможна
использование синхронных коммуникаций. В противном случае необходимы
асинхронные коммуникации.


                                                                       220