Википедия

Закон Густавсона — Барсиса: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м дополнение
исправление (вывод формулы был неверен), иллюстрация, источники
Строка 1:
'''Закон Густафсона''' (иногда '''Густавсона''') '''— Барсиса''' ({{lang-en|Gustafson – Barsis's law}}) — оценка максимально достижимого ускорения выполнения [[Параллельные вычисления|параллельной]] программы, в зависимости от количества одновременно выполняемых [[Поток выполнения|потоков вычислений]] («процессоров») и доли последовательных расчётов. Аналог [[Закон Амдала|закона Амдала]]: Джон Густафсон ({{lang-en|[[:en:John L. Gustafson|John L. Gustafson]]}}) и Эдвин Барсис ({{lang-en2|Edwin H. Barsis}}) представили статью «Переоценка закона Амдала» в 1988 году.
[[Файл:Иллюстрация закона Амдала.png|альт=Иллюстрация закона Амдала|мини|301x301пкс|Закон Амдала предполагает, что объем задачи остается неизменным. Задача слева обрабатывается одним потоком, задача справа — тремя. Сравнивается время выполнения. ]]
 
Закон Густафсона — Барсиса выражается формулой:
<math>S_pS_n=gs+(1-gs)pn=pn+(1-pn)gs</math>, где
: gs — доля последовательных расчётов в программе,
: pn — количество процессоров.
 
Данную оценку ускорения называют '''ускорением масштабирования''' ({{lang-en|scaled speedup}}), так как данная характеристика показывает, насколько эффективно могут быть организованы параллельные вычисления при увеличении сложности решаемых задач.
 
== Отличие от закона Амдала ==
[[Файл:Иллюстрация закона Густафсона.png|альт=Иллюстрация закона Густафсона|мини|315x315пкс|Закон Густафсона предполагает, что время, отведенное на выполнение задачи, остается неизменным. Слева работает один поток, справа — три. Объем выполненной работы увеличен. Сравнивается объем вычислений.]]
При оценке ускорения параллельного выполнения [[закон Амдала]] предполагает, что ''объем задачи остается постоянным''. Величина ускорения по закону Амдала показывает, ''во сколько раз меньше'' времени потребуется параллельной программе для выполнения. Однако величину ускорения можно рассматривать и как ''увеличение объема'' выполненной задачи ''за постоянный промежуток времени''. Закон Густафсона появился именно из этого предположения.
 
== Вывод формулы ==
'''Ускорение масштабирования''' определяется как отношение объема вычислений, выполенных с использованием многопоточности, к объему вычислений, выполненных последовательно за один и тот же промежуток времени.
Ускорение выполнения программы по определению равно отношению времени вычисления программы на одном процессоре ко времени вычисления на <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> — время последовательной части программы, а <math>\pi(n)</math> — время части программы, которая может быть распараллелена),
то ускорение перепишется следующим образом:
 
<math>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</math>, где
<math>
: s — доля последовательных расчётов в программе,
S_p = \frac{T_1}{T_p} = \frac{\tau (n) + \pi (n)}{\tau (n) + \pi (n) / p} =
: p — доля параллельных рассчётов в программе,
\frac{\tau (n) + \pi (n) / p \cdot p}{\tau (n) + \pi (n) / p} =
: n — количество процессоров.
\frac{(\tau (n) + \pi (n) / p)(g + (1-g)p)}{\tau (n) + \pi (n) / p},
</math>
откуда следует окончательная форма.
 
== См. также ==
Строка 30 ⟶ 28 :
== Ссылки ==
* [http://www.intuit.ru/studies/courses/1156/190/lecture/4944?page=5 Оценка максимально достижимого параллелизма]. Лекция из курса «Теория и практика параллельных вычислений» на сайте [[Интуит.ру|Института дистанционного обучения ИНТУИТ]].
* [http://impact.asu.edu/~mcn/cse520fa08/AmdahlsLawRevisted.pdf Reevaluating Amdahl's law. John. L. Gustafson.]
 
{{Параллельные вычисления}}
Источник — https://ru.wikipedia.org/wiki/Закон_Густавсона_—_Барсиса