\documentstyle[a4,oving,block]{article-n}
\begin{document}
\Hode{3}
\Oppgave{% Forutsetninger i Hwang&Briggs kap. 1.3.4:

Hastighets{\o}kningen ved {\aa} bruke $n$ prosessorer i stedet for 1
for {\aa} l{\o}se et beregningsproblem, er gitt ved:
	\[S = \frac{T_1}{T_n}\]
hvor $T_n$ er gjennomsnittstiden for {\aa} l{\o}se et problem p{\aa}
en $n$-prosessor maskin.  $T_n$ er gitt ved:
	\[T_n = \sum_{i=1}^{n} f_i \times d_i\]
hvor $f_i$ er sannsynligheten for at problemet l{\o}ses ved {\aa}
fordele arbeidet likt p{\aa} $i$ prosessorer, og $d_i = 1/i$ er
gjennomsnittlig arbeid pr. prosessor ved bruk av $i$ prosessorer p{\aa}
denne m{\aa}ten.

Utf{\o}r beregningen n\aa r $f_i$ er:
\[ f_i = 1/n \mbox{\hspace{13mm} $i=1, 2, \ldots ,n$ ,}\]
og 
\[ f_i = {i \over \sum_{j=1}^{n} j} \mbox{\hspace{13mm} $i=1, 2, \ldots ,n$ ,}\]\\
og n\aa r den er
\[ f_i = {n-i+1 \over \sum_{j=1}^{n} j} \mbox{\hspace{10mm} $i=1, 2, \ldots ,n$ .}\]
\vspace*{2ex}

I det f{\o}rste tilfellet er det jevn fordeling av arbeid p{\aa}
prosessorene. I det andre tilfellet er det antatt st{\o}rst
sannsynlighet for at oppgaven blir tilordnet et st\o rre antall
prosessorer, mens det i det tredje tilfellet antas st{\o}rst
sannsynlighet for at oppgaven kj\o res p\aa\ et mindre antall
prosessorer.  

Plott estimatene for hastighets{\o}kningen.

{\bf Hint:} Bruk gnuplot til {\aa} plotte disse kurvene.  Programmet er enkelt
{\aa} bruke.  Det er lagt ut et hjelpe-eksempel p{\aa} filen {\tt
$\sim$dam/45214/ovinger/gnuplot}.  Se ogs{\aa} manualsidene p{\aa} Sun
og Info-sidene i Emacs for mer informasjon. 
}

\newpage
\Oppgave{% Problem 3.7, Hwang

Det f{\o}lgende FORTRAN-programmet skal utf{\o}res p{\aa} en
en-prosessor maskin.  En parallell versjon skal utf{\o}res p{\aa} en
delt-minne (Eng: shared-memory) multiprosessor.

\begin{tabbing}
mmmmmmmm\= mmmmmm\= mmmm\= mm\= mm\= \kill  \\
\> L1: \> \> DO 10 I = 1, 1024\\
\> L2: \> \> \> SUM(I) = 0\\
\> L3: \> \> \> DO 20 J = 1, I\\
\> L4: \> 20 \> \> \> SUM(I) = SUM(I) + I\\
\> L5: \> 10 \> CONTINUE\\
\end{tabbing}

Anta at setningene L2 og L4 tar to maskin-sykler hver.  \'{E}n
maskin-sykel inkluderer b{\aa}de CPU-aktivitet og minne-aktivitet.  Se
bort i fra ``overhead'' p.g.a. l{\o}kkekontroll (setningene L1, L3 og
L5) og andre faktorer, som f.eks. system ``overhead'' og
ressurs-konflikter.

\begin{enumerate}

\item Hva er den totale utf{\o}relsestiden til programmet p{\aa} en
en-prosessor maskin? 

\item Fordel I-l{\o}kken blant 32 prosessorer med ``prescheduling''
p{\aa} denne m{\aa}ten:

\begin{quote}

Prosessor 1 utf{\o}rer de f{\o}rste 32 instruksjonene ($I = 1$ til $32$),
prosessor 2 utf{\o}rer de neste 32 iterasjonene ($I = 33$ til $64$),
osv. 
\end{quote}

Hva er utf{\o}relsestiden og hastighets{\o}kningen sammenlignet med
oppgaven i a)? (Merk at arbeidsmengden p.g.a. av J-l{\o}kken {\bf ikke}
er balansert p{\aa} de forskjellige prosessorene).

\item Modifiser programmet slik at lasten balanseres over alle de
32 prosessorene.  Med en balansert last mener vi at alle prosessorene
skal utf{\o}re et likt antall addisjoner med hensyn til begge
l{\o}kker.

\item Hva er den korteste utf{\o}relsestiden vi kan f{\aa} med
programmet som ble lagd i oppgave c)?  Hva blir hastighets{\o}kningen
sammenlignet med en-prosessor tilfellet?

\end{enumerate}
}

\end{document}
