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

      8) Завершать обработку последовательности, для чего учитывать
количество поступивших сигналов «конец работы». Когда их число станет
равным числу занятых «исполнителей» (это число в принципе может быть
меньше общего числа «исполнителей»), переходить к обработке следующей
последовательности (см. п. 3).
      Для процессора «исполнителя»:
      1) читать очередной символ и осуществлять переходы в алгоритме;
      2) если обрабатываемый блок закончился, и нет итерации, передать
«управляющему» сигнал завершения обработки блока, иначе запросить блок,
следующий в обрабатываемой последовательности за предыдущим.
      3) если возникло состояние алгоритма «цепочка найдена», то передать
сообщение «управляющему» об обнаружении цепочки (возможен вариант
алгоритма, когда информация о найденных цепочках будет храниться у
«исполнителя» до завершения обработки всех блоков, а затем пакетом
передаваться «управляющему»);
      Этот алгоритм можно усовершенствовать. При большом количестве
цепочек-образов и достаточном количестве «исполнителей» возможно
разделение алгоритма работы «управляющего» процессора на алгоритмы
двух процессоров: «управляющего» и «анализатора». На «управляющего»
будут возлагаться функции загрузки блоков последовательности, а на
«анализатор» - прием сообщений от «исполнителей» и их обработка. По
окончании обработки всех последовательностей «управляющий» получает от
«анализатора» результаты. Добавление «анализатора» в
мультипроцессорную систему целесообразно в том случае, когда объем
оперативной памяти, как общей, так и процессоров мал по сравнению с
длинами обрабатываемых последовательностей. В этом случае
«управляющий» процессор будет тратить много времени на распределение
блоков между рабочими процессорами. Архитектура такой системы
приведена на рис.7.13.



                     Источник
                последовательностей



                 Управляющий                     Анализатор
                   процессор




          Рабочий                     Общая            Рабочий
         процессор                    память          процессор


                                                                      224