Перегляд вихідного коду сторінки Закон Густавсона — Барсіса

'''Закон Густавсона&nbsp;— Барсіса''' ({{lang-en|Gustafson – Barsis's law}})&nbsp;— оцінка максимально досяжного прискорення виконання [[Паралельні обчислення|паралельної]] програми, в залежності від кількості одночасно виконуваних [[Потік виконання|потоків обчислень]] («процесорів») і частки послідовних обчислень. Аналог [[Закон Амдала|закону Амдала]].

Закон Густавсона&nbsp;— Барсіса виражається формулою:
<math>S_p=g+(1-g)p=p+(1-p)g</math>, де
: g&nbsp;— частка послідовних обчислень в програмі,
: p&nbsp;— кількість процесорів.

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

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

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

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

== Див. також ==
* [[Закон Амдала]]

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

== Посилання ==
* [http://www.intuit.ru/department/calculate/paralltp/2/5.html Оцінка максимально досяжного паралелізму] {{Webarchive|url=https://web.archive.org/web/20130315001710/http://www.intuit.ru/department/calculate/paralltp/2/5.html |date=15 березня 2013 }}. Лекція з курсу «Теорія і практика паралельних обчислень» {{ref-ru}}


{{Паралельні обчислення}}
{{Algorithm-stub}}
{{Compu-prog-stub}}
[[Категорія:Паралельні обчислення]]
[[Категорія:Теоретична інформатика]]