Классификация и организация вычислительных систем. Михайлов Б.М - 21 стр.

вверху соответствует номеру ветви, при выполнении которой получен данный
результат, а цифра внизу означает порядковый номер результата, полученного при
реализации данной ветви программы. На одном ярусе размещаются независимые
ветви задачи, не связанные друг с другом, т. е. результаты решения какой-либо ветви
данного яруса не являются входными данными для другой ветви этого же яруса.
      Изображенная на рис. 1.2 программа содержит 9 ветвей, расположенных на 3
ярусах. На примере этой, в общем, достаточно простой программы, можно выявить
преимущества вычислительной системы, включающей несколько обрабатывающих
устройств, и проблемы, которые при этом возникают.
      Примем, что длина i-й ветви представляется числом временных единиц ti, ко-
торые требуются для ее исполнения. Тогда нетрудно подсчитать, что для исполнения
всей программы на 1 процессоре потребуется время Т1:
                     9

              T   (10  20  15  30  55  10  15  25  15)  195
                1
                    i 1

      Если представить, что программа выполняется двумя обрабатывающими
устройствами (процессорами), работающими независимо друг от друга, то время
решения задачи сократится. Однако это время, как нетрудно видеть, будет различным
в зависимости от последовательности выполнения независимых ветвей.
      Рассмотрим, например, такой вариант выполнения программы, представленной
на рис. 5.2: пусть процессор 1 выполняет ветви 1-3-4-6-7-9, а процессор 2 выполняет
ветви 2-5-8. На рис. 1.3 представлены временные диаграммы выполнения
процессорами ветвей программы.




       Рисунок 1.3 - Разложение ветвей программы по двум процессорам


      Нетрудно подсчитать, что процессор 1 затрачивает 105, а процессор 2 — 100
единиц времени. При этом имеются два промежутка времени, когда один из
процессоров вынужденно простаивает — П1 длительностью 10 единиц и П2