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

большую размерность (длинные искомые цепочки, их большое количество,
много файлов большой длины, внутри которых осуществляется поиск), и
есть возможность использования многопроцессорной системы, то имеет
смысл с точки зрения повышения производительности системы поиска
произвести дальнейшее распараллеливание алгоритма.
        7.2. Разработка алгоритмов решения задач
распознавания цепочек-образов для многопроцессорной
                      реализации
    7.2.1. Общие сведения           о   методике     проектирования
параллельных алгоритмов
      Одна из важных тенденций развития современной вычислительной
техники состоит в расширенном внедрении многопроцессорных архитектур.
Микропроцессоры позволили получить процессорное время по номинальной
цене, а их малые габариты делают вполне обоснованной постановку вопроса
об их комплексировании в единой системе в количестве десятков, сотен и
более. Одним из ключевых факторов способствующих использованию таких
систем будет наличие параллельных алгоритмов.
      Один из возможных подходов к разработке параллельного алгоритма
для решения какой-либо задачи, в том числе задач идентификации
базируется на методике, приведенной в [59] и состоит из следующих этапов
проектирования:
      - разбиение исходной задачи на элементарные задачи;
      - определение всех необходимых взаимодействий (коммуникаций)
         между элементарными задачами;
      - объединение элементарных задач (агломерация) в соответствие с
         определенной стратегией, учитывающей в том числе число
         процессоров в системе;
      - распределение полученных при агломерации задач на заданное
         число процессоров;
      - оценка полученного алгоритма (или алгоритмов, если их получено
         несколько) на масштабируемость (при увеличении объема исходных
         данных и/или изменении числа процессоров в мультипроцессорной
         системе).
     Разбиение задачи на элементарные подзадачи.
      На этом этапе проектирования определяется максимально возможный
параллелизм при решении задачи. Для этого производится разбиение данных
(исходных, промежуточных), используемых в задаче, а также операций
выполняемых над ними на элементарные части (не допускающие
дальнейшего разбиения) без учета числа процессоров в многопроцессорной
системе.

                                                                       206