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

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

Закон Амдала предполагает, что объем задачи остается неизменным. Задача слева обрабатывается одним потоком, задача справа — тремя. Сравнивается время выполнения.

Закон Густафсона — Барсиса выражается формулой: $S_{n}=s+(1-s)n=n+(1-n)s$, где

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

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

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

Отличие от закона Амдала

Закон Густафсона предполагает, что время, отведенное на выполнение задачи, остается неизменным. Слева работает один поток, справа — три. Объем выполненной работы увеличен. Сравнивается объем вычислений.

При оценке ускорения параллельного выполнения закон Амдала предполагает, что объем задачи остается постоянным. Величина ускорения по закону Амдала показывает, во сколько раз меньше времени потребуется параллельной программе для выполнения. Однако величину ускорения можно рассматривать и как увеличение объема выполненной задачи за постоянный промежуток времени. Закон Густафсона появился именно из этого предположения.

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

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

$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$, где

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

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

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

См. также

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

Литература

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

Ссылки

• Оценка максимально достижимого параллелизма. Лекция из курса «Теория и практика параллельных вычислений» на сайте Института дистанционного обучения ИНТУИТ.
• Reevaluating Amdahl's law. John. L. Gustafson.