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

Закон Густавсона — Барсіса (англ. Gustafson – Barsis's law) — оцінка максимально досяжного прискорення виконання паралельної програми, в залежності від кількості одночасно виконуваних потоків обчислень («процесорів») і частки послідовних обчислень. Аналог закону Амдала.

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

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

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

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

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

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

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

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

Див. також

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

Література

• Quinn M.J. Parallel Programming in C with MPI and OpenMP. — New York : NY: McGraw-Hill, 2004.
• Базилевич Р., Кутельмах Р., Кузь Б. Алгоритмічне забезпечення для розпаралелювання задачі комівояжера великої розмірності // Інформаційні технології та комп’ютерна інженерія. Тези доповідей Міжнародної науково-практичної конференції. м. Вінниця, 19-21 травня 2010 року. — Вінниця: ВНТУ, 2010.

Посилання

• Оцінка максимально досяжного паралелізму [ 15 березня 2013 у Wayback Machine.]. Лекція з курсу «Теорія і практика паралельних обчислень» (рос.)