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

обслуживания «исполнителей». Например, для удаления обнаруженных
цепочек-образов, обеспечения интерфейса пользователя, и т.д. Если же
количество процессоров будет больше оптимального, то будет простаивать
часть процессоров «исполнителей», так как до них задания от
«управляющего» не придут. Это будет происходить из-за того, что первый
«исполнитель» вновь передаст запрос на получение следующего блока
раньше, чем процессор сможет загрузить все «исполнители». Таким образом,
увеличение числа процессоров не будет повышать скорость работы системы.
      Увеличение размера входных данных в общем случае не влияет на
величину оптимального количества процессоров. Если длина блока данных
не изменяется, а увеличивается только их количество, то в алгоритме работы
системы ничего не изменится (увеличится лишь общее время обработки).
Если же увеличивается размер блока, то увеличивается время обработки
этого блока процессором «исполнителем», но и увеличивается суммарное
время передачи блока «исполнителю». Если обеспечить в системе, что эти
два времени будут равны, то она будет работать без простоев.
      Оценим эффективность мультипроцессорной системы при
оптимальном количестве процессоров. Время работы однопроцессорной
системы То:
      То=(Тсчит+Тобраб)n, где Тсчит, Тобраб – время считывания и обработки
одного байта, а n – число байт в последовательности.
      Представим графически работу каждого процессора «исполнителя» в
мультипроцессорной системе во времени без учета взаимодействия с
«управляющим» и «анализатором» (рис.7.14).
        считывание       обработка
                                                             1-ый процессор
                                                                              t

        холостой ход        считывание        обработка
                                                             2-ой процессор
                                                                              t

     Рис.7.14 Загрузка работой во времени процессоров «исполнителей»
      Тогда приближенно время работы многопроцессорной системы Тм:
Тм=Тсчитn+Тобрабn/2
      Эффективность выполнения алгоритма при параллельной реализации
по сравнению с последовательной будет приблизительно равна:
                                 То            2
                           Е=       =
                                 Тм        Тсчит
                                                        +1
                                         Тсчит+Тобраб
     Следует отметить, что полученное выражение показывает
максимальную эффективность в результате того, что ранее были введены

                                                                                  228