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

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


                                                                     222