Модель параллелизма данных

Рассмотрим теперь схему программы, соответствующую модели параллелизма данных. Предположим, что в программе имеются блоки двух типов: S_s и S_p (рис. 2.19 а). Алгоритм,

блока S_K может выполняться только в последовательном, режиме одним процессором, а блок S_p допускает разбивку на n независимых модулей S₁..., Sn, каждый из которых может выполняться на отдельном процессоре.

Сеть Петри показана на рисунке 2.19 б. Мы видим, что блок S_s одновременно передает данные и управление модулям S,,..., S_n (это происходит при срабатывании перехода t_t).

Модули выполняются независимо, однако дальнейшие вычисления могут начаться только после завершения выполнения всех модулей (т.е. должны сложиться условия для срабатывания перехода t₂). Таким образом, с помощью сети Петри можно описать нетривиальные особенности параллельного выполнения модулей. С помощью стандартных блок-схем это было бы сделать затруднительно.

На примере данной схемы можно вывести известную формулу Амдала, которая характеризует эффективность параллельных алгоритмов.

Пусть блок S_s требует для своего выполнения времени t, а блок S_p при его вьполнении на одном процессоре -времени t_p. Тогда общее время решения задачи на одном процессоре составит t, =t_s+ t_p. Если же блок S_p выполняется параллельно на п одинаковых процессорах, то время его выполнения в идеальном случае (при равномерной загрузке всех процессоров) составит t_{p /} n, а общее время решения задачи будет t₂=t_s+t_p/n.

Коэффициент ускорения вычислений составит

t_s+t_p I

k = t, lt₂= ^{s p} =------------ -, (2.19)

t_s+t_p/n s + p/n

t_s t_p

где s = ——_; p = — —— _ относительные доли

t_s + t_p t_s + t_p

последовательной и параллельной частей (s + p = 1).

Выражение 2.19 носит название формулы Амдала.