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

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


                                         31