Теория и практика параллельных вычислений


Оценка максимально достижимого параллелизма - часть 2


Однако для большого ряда задач доля f=f(n) является убывающей функцией от n, и в этом случае ускорение для фиксированного числа процессоров может быть увеличено за счет увеличения вычислительной сложности решаемой задачи. Данное замечание может быть сформулировано как утверждение, что ускорение Sp=Sp(n) является возрастающей функцией от параметра n (данное утверждение часто именуется эффект Амдаля). Так, например, для учебного примера вычисления суммы значений при использовании фиксированного числа процессоров p суммируемый набор данных может быть разделен на блоки размера n/p, для которых сначала параллельно могут быть вычислены частные суммы, а далее эти суммы можно сложить при помощи каскадной схемы. Длительность последовательной части выполняемых операций (минимально возможное время параллельного исполнения) в этом случае составляет

Tp=(n/p)+log2p,

что приводит к оценке доли последовательных расчетов как величины

f=(1/p)+log2p/n.

Как следует из полученного выражения, доля последовательных расчетов f убывает с ростом n и в предельном случае мы получаемом идеальную оценку максимально возможного ускорения S*=p.

2. Закон Густавсона – Барсиса. Оценим максимально достижимое ускорение исходя из имеющейся доли последовательных расчетов в выполняемых параллельных вычислениях:

где ?(n) и (n) есть времена последовательной и параллельной частей выполняемых вычислений соответственно, т.е.

T1=?(n)+(n), Tp = ?(n)+(n)/p.

С учетом введенной величины g можно получить

?(n)=g·(?(n)+(n)/p), (n)=(1-g)p·(?(n)+(n)/p),

что позволяет построить оценку для ускорения

которая после упрощения приводится к виду закона Густавсона – Барсиса (Gustafson – Barsis's law) (см. [63]):

Sp = g+(1–g)p = p+(1–p)g.

Применительно к учебному примеру суммирования значений при использовании p процессоров время параллельного выполнения, как уже отмечалось выше, составляет

Tp = (n/p)+log2p,

что соответствует последовательной доле

За счет увеличения числа суммируемых значений величина g может быть пренебрежимо малой, обеспечивая получение идеального возможного ускорения Sp=p.




Начало  Назад  Вперед



Книжный магазин