\documentstyle[a4,oving,block]{article-n}

\begin{document}
\HodeLosn{3}
\Oppgave{% Gammel 1.1,  Hwang&Briggs: 1.2, s.50

\noindent Fordeling 1:

\noindent
Tid med $1$ prosessor: $T_1 = 1 $.\newline
Tid med $n$ prosessorer:

\[ T_n = \sum_{i=1}^{n} f_{i} \cdot d_{i}
= \frac{\sum_{i=1}^{n}\frac{1}{i}}{n}\]
Hastighets{\o}kningen blir dermed:
\[ \underline{S} = \frac{T_{1}}{T_{n}} =
\frac{n}{\sum_{i=1}^{n}\frac{1}{i}} \leq \underline{\frac{n}{ln~n}}\] 

\noindent Fordeling 2:

\noindent
Tid med $1$ prosessor: $T_{1}=1$.\newline
Tid med $n$ prosessorer:
\[ T_{n}= \sum_{i=1}^{n} f_{i} \cdot d_{i}
= \sum_{i=1}^{n} { {\frac{i}{\sum_{j=1}^{n}j}} {\frac{1}{i}} }
= \sum_{i=1}^{n} {\frac{1}{\sum_{j=1}^{n}j}}
= \frac {2}{n+1} \]
Hastighets\o kningen blir dermed:
\[ \underline{S} = \frac{T_{1}}{T_{n}} = \underline{\frac{n+1}{2}} \]

\noindent Fordeling 3:

\noindent
Tid med $1$ prosessor: $T_{1}=1$.\newline
Tid med $n$ prosessorer:
\[  T_{n}= \sum_{i=1}^{n} f_{i} \cdot d_{i}
= \sum_{i=1}^{n} { {\frac{n-i+1}{\sum_{j=1}^{n}j}} {\frac{1}{i}} }
= \sum_{i=1}^{n}{{\frac{n-i+1}{i}} {\frac{2}{n(n+1)}}}
= \frac{2}{n}\sum_{i=1}^{n}\frac{1}{i} - \frac{2}{n+1} \]
Hastighets\o kningen blir dermed:
\[ \underline{S} = \frac{T_{1}}{T_{n}}
= \frac{1}{\frac{2}{n}\sum_{i=1}^{n}\frac{1}{i} - \frac{2}{n+1}}
\leq \frac{1}{ {\frac{2}{n} \ln n} - \frac{2}{n+1} } \approx 
\underline{\frac{n}{2 \ln n - 2}} \]
\newpage
Plottet under viser hastighets{\o}kning ({\em Speedup}) som funksjon av antall
prosessorer.


%\begin{center}
%\mbox{\psfig{figure=lf3-fig1.ps,height=8cm}}
%\end{center}
% Plottet over er laget vha. gnuplot paa foelgende maate:
%  gnuplot>set logscale xy
%  gnuplot>set yrange [1:10000]
%  gnuplot>log2(x) = log(x)/log(2)
%  gnuplot>ln(x) = log(x)
%  gnuplot>set terminal postscript portrait
%  gnuplot>set output "/home/pil/b/almli/somjob/ovinger/lf3-fig1.ps"
%  gnuplot>plot [n=1:1024] n,(n+1)/2,n/ln(n),log2(n),n/(2*ln(n)-2)}


\Oppgave{% Problem 3.7, Hwang

\begin{enumerate}

\item 

\[ C_0 = 2 * 1024 + 2 * \frac{1024 *1025}{2} = \underline{1051648} \]

\item

``Tregeste prosessor'' er prosessor \#32, siden denne har flest
addisjoner pr. I-verdi:
\[ C_1 = 2 * 32 + 2 * 32 * 992 + 2 * \frac{32 * 33}{2} = 64608
\] 

\[ Speedup = \frac{T_1}{T_{32}} = \frac{1051648}{64608} \approx \underline{16.3} \]

\item 

For {\aa} balansere lasten, deler vi den ytterste l{\o}kken opp i 64
deler, slik at hver f{\aa}r 16 iterasjoner. Slik kan prosessor 1
f{\aa} f{\o}rste og siste gruppe, prosessor 2 f{\aa} andre og nest
siste gruppe og s{\aa} videre.   Vi f{\aa}r dermed den modifiserte
koden: 

\begin{tabbing}
mmmmmmmm\= mmmmmm\= mmmm\= mm\= mm\= \kill  \\
\> DOALL $\ell$ = 1, 32 \\
\> \> DO 10 I = ($\ell$-1) $\times$ 16 + 1, $\ell$ $\times$ 16 \\
\> \> \> SUM(I) = 0 \\
\> \> \> DO 20 J = 1, I\\
20 \> \> \> \> SUM(I) = SUM(I) + J\\
10 \> \> \> CONTINUE\\
\> \> DO 30 I = (64 - $\ell$) $\times$ 16 + 1, (64 - $\ell$ + 1) $\times$ 16 \\
\> \> \> SUM(I) = 0\\
\> \> \> DO 40 J = 1, I\\
40 \> \> \> \> SUM(I) = SUM(I) + J \\
30 \> \> \> CONTINUE\\
\> ENDALL\\
\end{tabbing}

\newpage
\item 

Vi ser bort i fra ``overhead'' fra kontrol-flyt.  Antall sykler som
trengs for beregning for en prosessor $\ell, 1 \leq \ell \leq 32$, blir da:

\begin{eqnarray}
C_2 & = & \sum_{i =(\ell-1) \times 16 + 1}^{\ell \times 16} (2 \times i + 1) + \sum_{i = (64-\ell) \times 16 + 1}^{(64 - \ell + 1) \times 16} (2 \times i + 1) \nonumber \\ 
& = & \{ [ (\ell - 1) \times 16 + 2 + \ell \times 16 + 1 ] + \nonumber \\
& & [(64 - \ell) \times 16 + 2 + (64 - \ell + 1) \times 16 + 1] \} \times 16 \nonumber \\
& = & 2054 \times 16 = 32,684. \nonumber 
\end{eqnarray}

Hastighets{\o}kningen sammenlignet med en-prosessor tilfellet blir da

\[ Speedup = \frac{1051684}{32864} = 32. \]
\end{enumerate}
\end{document}

Prosessor $k$ utf{\o}rer addisjoner med I-l{\o}kkeverdi fra
$f(k-1)$ til $f(k)$ hvor $f(k) = 128 \sqrt{2 k}$.

$f(k)$ ble funnet slik:

\begin{quote}

Antall addisjoner til sammen kan ses p{\aa} som en trekant med areal,
$A$, hvor grunn\-linjen er I-l{\o}kken, og h{\o}yden, $h(i)$, $i = 1,
... , l$ er antall addisjoner for den spesielle I-verdien.  Arealet,
$A$, blir da  \[ A = \frac{h(l) * (h(1) + h(l))}{2} \]

Dette arealet skal deles likt mellom de $n = 32$ prosessorene, slik at
hvert areal blir p{\aa} $A / n$ addisjoner.  Hvert areal blir da et
{\em trapes} med h{\o}yde $h(f(k))$ og $h(f(k-1))$, hvor $k = 1, 2,
... n$. Vi f{\aa}r derfor 
\[ \frac{A}{n} = \frac{(f(k) - f(k-1))(h(f(k)) + h(f(k-1))}{2} \] 
Siden $h(x) = x$ f{\aa}r vi ligningen 
\[ \frac{A}{n} = \frac{(f(k) - f(k-1))(f(k) + f(k-1))}{2} \]
Vi f{\aa}r n{\aa} ligningen 
\[ {f(k)}^2 = \frac{2A}{n} + {f(k-1)}^2 \]
$f(1) = \sqrt{\frac{2A}{n}}$, $f(2) = \sqrt{\frac{4A}{n}}$, osv og $f(k) =
\sqrt{\frac{2A \times k}{n}}$, for $k = 1, 2,... n$.  Setter inn for
$A$ og $n$ og f{\aa}r
\[ f(k) = \sqrt{\frac{2 * 1024 * 1025 \times k}{2 * 32}} \approx 4 *
32 \sqrt{2 k} = \underline{128\sqrt{2k}}\]
\end{quote}

\item 

``Tregeste prosessor'' er prosessor \#1, siden denne har flest
I-verdier {\aa} beregne for, fra $I = 1$ til $I = 128 \sqrt{2} \approx
181$. Antall sykler blir da
\[ \#sykler = 2 * 181 + 2 * \frac{181 * 182}{2} = \underline{33304} \]

Hastighets{\o}kningen sammenlignet med en-prosessor tilfellet blir da
\[ Speedup = \frac{T_1}{T_{32b}} = \frac{1051684}{33304} \approx \underline{31.6} \]
\end{enumerate}

}

\end{document}
