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

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

  2) количество коммуникаций для одной ЭЗ мало, что позволит добиться лучшей па-
   раллельности выполнения алгоритма;

  3) коммуникации нижнего уровня независимы и поэтому могут выполняться парал-
   лельно;

  4) некоторые коммуникации верхнего уровня не могут выполняться параллельно, но в
   связи с тем, что их количество в процентном отношении мало, они допустимы в алго-
   ритме;

  5) все ЭЗ нижнего уровня выполняются параллельно, т.к. не зависят друг от друга, а
   также от ЭЗ верхнего уровня.

   На третьем шаге проектирования параллельного алгоритма произведем агломерацию
ЭЗ. Рассмотрим вначале возможные варианты агломерации ЭЗ, которые были получены
при разбиении алгоритма по функциям. Как видно из рис. 3.12, можно провести агломе-
рацию по вертикали или по горизонтали.
   При вертикальной агломерации объединяется в одну задачу отдельная ветвь дерева.
Таким образом, в каждой ЭЗ осуществляется поиск одной конкретной цепочки. Результа-
ты поиска цепочек объединяются в корне дерева. ЭЗ при этом получаются независимыми,
то есть могут работать параллельно. Алгоритм будет достаточно масштабируемым, осо-
бенно хорошие результаты получатся, когда количество групп будет равно количеству
процессоров. Но у такой агломерации есть существенный недостаток. Дело в том, что ЭЗ
нижнего уровня представляет собой конъюнкцию, а конъюнкция является одной из самых
быстрых операций в ЭВМ. Следовательно, выигрыш в производительности при такой аг-



                                         30