Закон Густавсона — Барсиса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Закон Густафсона (иногда Густавсона) — Барсиса (англ. Gustafson – Barsis's law) — оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов. Аналог закона Амдала.

Закон Густафсона — Барсиса выражается формулой: S_p=g+(1-g)p=p+(1-p)g, где

g — доля последовательных расчётов в программе,
p — количество процессоров.

Данную оценку ускорения называют ускорением масштабирования (англ. scaled speedup), так как данная характеристика показывает, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.

Вывод формулы[править | править вики-текст]

Ускорение выполнения программы по определению равно отношению времени вычисления программы на одном процессоре ко времени вычисления на p процессорах: S_p = \frac{T_1}{T_p}.

Если ввести обозначение для доли последовательных расчётов: g= \frac{\tau(n)}{\tau(n) + \pi(n)/p} (здесь \tau(n) — время последовательной части программы, а \pi(n) — время части программы, которая может быть распараллелена), то ускорение перепишется следующим образом:


S_p = \frac{T_1}{T_p} = \frac{\tau (n) + \pi (n)}{\tau (n) + \pi (n) / p} =
\frac{\tau (n) + \pi (n) / p \cdot p}{\tau (n) + \pi (n) / p} =
\frac{(\tau (n) + \pi (n) / p)(g + (1-g)p)}{\tau (n) + \pi (n) / p},
откуда следует окончательная форма.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Quinn M.J Parallel Programming in C with MPI and OpenMP. — New York: NY: McGraw-Hill, 2004.

Ссылки[править | править вики-текст]