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

Закон Густавсона — Барсіса (Шаблон:Lang-en) — оцінка максимально досяжного прискорення виконання паралельної програми, в залежності від кількості одночасно виконуваних потоків обчислень («процесорів») і частки послідовних обчислень. Аналог закону Амдала.

Закон Густавсона — Барсіса виражається формулою: $S_p=g+(1-g)p=p+(1-p)g$, де

g — частка послідовних обчислень в програмі,

p — кількість процесорів.

Дану оцінку прискорення називають прискоренням масштабування (Шаблон:Lang-en), через те, що дана характеристика показує, наскільки ефективно можуть бути організовані паралельні обчислення при збільшенні складності обчислювальних задач.

Виведення формули

Прискорення виконання програми по визначенню рівне відношенню часу обчислень програми на одному процесорі до часу обчислення на $p$ процесорах: $S_p=\frac{T_1}{T_p}$.

Якщо ввести визначення для долі послідовних розрахунків: $g=\frac{\tau (n)}{\tau (n)+\pi (n)/p}$ (тут $\tau (n)$ — час виконання послідовної частини програми, а $\pi (n)$ — час виконання частини програми, яка може бути розпаралелена), то набуде такого вигляду:

$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},$ звідси слідує кінцева форма.

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Книга

Посилання

• Оцінка максимально досяжного паралелізму Шаблон:Webarchive. Лекція з курсу «Теорія і практика паралельних обчислень» Шаблон:Ref-ru

Шаблон:Паралельні обчислення Шаблон:Algorithm-stub Шаблон:Compu-prog-stub