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

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

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

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

p — количество процессоров.

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

Вывод формулы

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

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

<math> 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}, </math> откуда следует окончательная форма.

См. также

• Закон Амдала

Литература

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

Ссылки

• [www.intuit.ru/studies/courses/1156/190/lecture/4944?page=5 Оценка максимально достижимого параллелизма]. Лекция из курса «Теория и практика параллельных вычислений» на сайте Института дистанционного обучения ИНТУИТ.

Отрывок, характеризующий Закон Густавсона — Барсиса

– Да, Москва будет сдана! Она будет искупительницей! – кричал один.
– Он враг человечества! – кричал другой. – Позвольте мне говорить… Господа, вы меня давите…


В это время быстрыми шагами перед расступившейся толпой дворян, в генеральском мундире, с лентой через плечо, с своим высунутым подбородком и быстрыми глазами, вошел граф Растопчин.
– Государь император сейчас будет, – сказал Растопчин, – я только что оттуда. Я полагаю, что в том положении, в котором мы находимся, судить много нечего. Государь удостоил собрать нас и купечество, – сказал граф Растопчин. – Оттуда польются миллионы (он указал на залу купцов), а наше дело выставить ополчение и не щадить себя… Это меньшее, что мы можем сделать!
Начались совещания между одними вельможами, сидевшими за столом. Все совещание прошло больше чем тихо. Оно даже казалось грустно, когда, после всего прежнего шума, поодиночке были слышны старые голоса, говорившие один: «согласен», другой для разнообразия: «и я того же мнения», и т. д.
Было велено секретарю писать постановление московского дворянства о том, что москвичи, подобно смолянам, жертвуют по десять человек с тысячи и полное обмундирование. Господа заседавшие встали, как бы облегченные, загремели стульями и пошли по зале разминать ноги, забирая кое кого под руку и разговаривая.
– Государь! Государь! – вдруг разнеслось по залам, и вся толпа бросилась к выходу.
По широкому ходу, между стеной дворян, государь прошел в залу. На всех лицах выражалось почтительное и испуганное любопытство. Пьер стоял довольно далеко и не мог вполне расслышать речи государя. Он понял только, по тому, что он слышал, что государь говорил об опасности, в которой находилось государство, и о надеждах, которые он возлагал на московское дворянство. Государю отвечал другой голос, сообщавший о только что состоявшемся постановлении дворянства.