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

      Итоговая оценка полученных коммуникаций между ЭЗ дает
следующие результаты:
      1) система      коммуникаций      является   структурированной     и
упорядоченной, что обеспечит в дальнейшем масштабируемость алгоритма;
      2) количество коммуникаций для одной ЭЗ мало, что позволит
добиться лучшей параллельности выполнения алгоритма;
      3) коммуникации нижнего уровня независимы и поэтому могут
выполняться параллельно;
      4) некоторые коммуникации верхнего уровня не могут выполняться
параллельно, но в связи с тем, что их количество в процентном отношении
мало, они допустимы в алгоритме;
      5) все ЭЗ нижнего уровня выполняются параллельно, т.к. не зависят
друг от друга, а также от ЭЗ верхнего уровня.
      На третьем шаге проектирования параллельного алгоритма
произведем объединение ЭЗ. Рассмотрим вначале возможные варианты
объединения ЭЗ, которые были получены при разбиении алгоритма по
функциям. Как видно из рис. 7.11, можно провести объединение по
вертикали или по горизонтали.
      Для вертикального способа объединяются в одну задачу отдельные
ветви дерева. Таким образом, в каждой ЭЗ осуществляется поиск одной
конкретной цепочки. Результаты поиска цепочек объединяются в корне
дерева. ЭЗ при этом получаются независимыми, то есть могут работать
параллельно. Алгоритм будет достаточно масштабируемым, особенно
хорошие результаты получатся, когда количество групп будет равно
количеству процессоров. Но у такого объединения есть существенный
недостаток. Дело в том, что ЭЗ нижнего уровня представляет собой
конъюнкцию, а конъюнкция является одной из самых быстрых операций в
ЭВМ. Следовательно, выигрыш в производительности при таком
объединении будет незначительным из-за того, что время, затрачиваемое на
пересылку входного сигнала в каждую из ЭЗ, будет значительно
превосходить время обработки этого сигнала (конъюнкции).
      Для горизонтального способа в одну ЭЗ объединяется нижний уровень
дерева, т.е. все возможные конъюнкции. Это соответствует поиску
подцепочки. Вышележащие уровни объединяются в другую ЭЗ, которая
будет получать информацию об обнаружении подцепочки, о принадлежности
этой подцепочки конкретному образу, анализировать ее и по завершении
просмотра входных последовательностей выдавать окончательный результат
поиска. При таком объединении ЭЗ нижнего уровня выполняются
последовательно, что сужает параллелизм. Основным достоинством такого
объединения является возможность разбиения ЭЗ нижнего уровня по
данным. Т.е. одна ЭЗ будет представлять собой поиск всех возможных
цепочек в первой последовательности, другая - во второй и так далее.


                                                                       221