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

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

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

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

Закон Густафсона — Барсиса выражается формулой: , где

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

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

Отличие от закона Амдала[править | править код]

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

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

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

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

, где

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

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

Литература[править | править код]

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

Ссылки[править | править код]