WikiSort.ru - Не сортированное

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

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

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

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

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

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

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

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

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

${\displaystyle 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.