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

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




                                             37