section2_3.tex

{ %section2_3
	\subsection{Метод Густавсона-Барсиса}
	\parПри оценке эффективности распараллеливания некоторой программы, работающей фиксированное время, скорость выполнения можно выразить следующим образом: $\left.V(p)\right|_{t=const}\;=\;\frac {w(p)}t$, где $w(p)$ – это общее количество УЕР, которые программа успевает выполнить за время $t$ при использовании $p$ процессоров. Тогда выражение~\eqref{parallelAcceleration:equation} для параллельного ускорения примет вид:
	\begin{equation}
		\label{GustavsonAcceleration:equation}
		\left.S(p)\right|_{t=const}\;=\;\frac{V(p)}{V(1)}\;=\;\frac{w(p)}t\;:\;\frac{w(1)}t\;=\;\frac{w(p)}{w(1)}.
	\end{equation}
	\parЗапишем количество работы $w(1)$ следующим образом:
	\begin{equation}
		\label{GustavsonWork:equation}
		w(1)\;=\;w(1)\;+\;(k\;\cdot\;w(1)\;-\;k\;\cdot\;w(1))\;=\;k\;\cdot\;w(1)\;+\;(1\;-\;k)\;\cdot\;w(1),
	\end{equation}
	где $k\in\lbrack0,1)$ – это уже упомянутый ранее коэффициент распараллеленности программы. Тогда первое слагаемое можно считать количеством работы, которая идеально распараллеливается, а второе – количество работы, которую распараллелить не удается при добавлении процессоров (ядер).
	\parПри использовании $p$ процессоров количество выполненной работы $w(p)$ очевидно станет больше, при этом оно  будет состоять из двух слагаемых: 
	\begin{itemize}
		\itemколичество нераспараллеленных условных единиц работы $(1-k)\cdot w(1)$, которое не изменится по сравнению с формулой~\eqref{GustavsonWork:equation}.
		\itemколичество распараллеленных УЕР, объём которых увеличиться в $p$ раз по сравнению с формулой~\eqref{GustavnsonWork:equation}, т.к. в работе будет задействовано $p$ процессоров вместо одного.
	\end{itemize}
	\parУчитывая сказанное, получим следующее выражение для $w(p)$:
	\par$w(p)\;=\;p\;\cdot\;k\;\cdot\;w(1)\;+\;(1\;-\;k)\;\cdot\;w(1),$ тогда с учетом формулы~\eqref{GustavsonAcceleration:equation} получим: $\;\frac{w(p)}{w(1)}=\;\frac{p\cdot k\cdot w(1)+(1-k)\cdot w(1)}{w(1)}$, что позволяет записать:
	\begin{equation}
		\left.S(p)\right|_{t=const}\;=\;S_{GB}(p)\;=\;p\;\cdot\;k\;+\;1\;-\;k
	\end{equation}
	\parПриведённое выражение называется \textbf{законом Густавсона-Барсиса}, который Джон Густавсон и Эдвин Барсис сформулировали в 1988 году. 
	\par
}