Просмотр кода страницы Закон Густавсона — Барсиса

'''Закон Густафсона''' (иногда '''Густавсона''') '''— Барсиса''' ({{lang-en|Gustafson – Barsis's law}}) — оценка максимально достижимого ускорения выполнения [[Параллельные вычисления|параллельной]] программы, в зависимости от количества одновременно выполняемых [[Поток выполнения|потоков вычислений]] («процессоров») и доли последовательных расчётов. Аналог [[Закон Амдала|закона Амдала]]: Джон Густафсон ({{lang-en|[[:en:John L. Gustafson|John L. Gustafson]]}}) и  Эдвин Барсис ({{lang-en2|Edwin H. Barsis}}) представили статью «Переоценка закона Амдала» в 1988 году.
[[Файл:Иллюстрация закона Амдала.png|альт=Иллюстрация закона Амдала|мини|301x301пкс|Закон Амдала предполагает, что объем задачи остается неизменным. Задача слева обрабатывается одним потоком, задача справа — тремя. Сравнивается время выполнения. ]]
Закон Густафсона — Барсиса выражается формулой:
<math>S_n=s+(1-s)n=n+(1-n)s</math>, где
: s — доля последовательных расчётов в программе,
: n — количество процессоров.

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

== Отличие от закона Амдала ==
[[Файл:Иллюстрация закона Густафсона.png|альт=Иллюстрация закона Густафсона|мини|315x315пкс|Закон Густафсона предполагает, что время, отведенное на выполнение задачи, остается неизменным. Слева работает один поток, справа — три. Объем выполненной работы увеличен. Сравнивается объем вычислений.]]
При оценке ускорения параллельного выполнения [[закон Амдала]] предполагает, что ''объем задачи остается постоянным''. Величина ускорения по закону Амдала показывает, ''во сколько раз меньше'' времени потребуется параллельной программе для выполнения. Однако величину ускорения можно рассматривать и как ''увеличение объема'' выполненной задачи ''за постоянный промежуток времени''. Закон Густафсона появился именно из этого предположения. 

== Вывод формулы ==
'''Ускорение масштабирования''' определяется как отношение объема вычислений, выполненных с использованием многопоточности, к объему вычислений, выполненных последовательно за один и тот же промежуток времени. 

<math>S_n = \frac{p \cdot n + s}{p + s} = \frac{n(p + s)}{p + s} + \frac{s - s \cdot n}{p+s} = n + (1-n)\frac{s}{p + s} = n + (1 - n)s</math>, где
: s — доля последовательных расчётов в программе,
: p — доля параллельных расчётов в программе,
: n — количество процессоров.

== См. также ==
* [[Закон Амдала]]

== Литература ==
* {{книга|автор=Quinn M.J|заглавие=Parallel Programming in C with MPI and OpenMP|место=New York|издательство=NY: McGraw-Hill|год=2004}}

== Ссылки ==
* [http://www.intuit.ru/studies/courses/1156/190/lecture/4944?page=5 Оценка максимально достижимого параллелизма]. Лекция из курса «Теория и практика параллельных вычислений» на сайте [[Интуит.ру|Института дистанционного обучения ИНТУИТ]].
* [https://web.archive.org/web/20170809122232/https://impact.asu.edu/~mcn/cse520fa08/AmdahlsLawRevisted.pdf Reevaluating Amdahl's law. John. L. Gustafson.] 

{{Параллельные вычисления}}

[[Категория:Параллельные вычисления]]
[[Категория:Научные законы]]