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

{\Large \bf L\o sningsforslag til \O ving 7:}

\Oppgave{

\begin{enumerate}
 \item
  \begin{description}
   \item[Hastighets\o kning :] Forholdet mellom den tiden det tar \aa\
        utf\o re en oppgave sekvensielt p\aa\ en uniprosessor og den tiden det
        tar \aa\ utf\o re den parallelt p\aa\ et $n$-prosessor-system, alts\aa\
        et m\aa l p\aa\ hvor mye raskere det g\aa r \aa\ utf\o re oppgaven
        parallelt.
   \item[Effektivitet :] Forholdet mellom det antallet operasjoner en
        uniprosessor m\aa\ utf\o re for \aa\ gjennomf\o re en beregning og det
        antallet enhetsoperasjoner en $n$-prosessor maksimalt kan utf\o re i
        l\o pet av den tiden $T(n)$ den bruker p\aa\ den samme beregningen,
        og er derfor et m\aa l p\aa\  hvor effektivt regnekapasiteten i
        $n$-prosessoren utnyttes ved den parallelle beregningen.
   \item[Redundans :] M\aa ler hvor mye beregningsbehovet for \aa\ l\o se
        problemet \o ker ved \aa\ utf\o re beregningen i parallell.
   \item[Utnyttelse :] Forventet andel av tiden hver av de $n$ prosessorene
        er opptatt med beregninger.
   \item[Kvalitet :] Produktet av hastighets\o kning, effektivitet og den
        inverse av redundansen. Det er \o nskelig at de to f\o rste er s\aa\
        h\o ye som mulig, mens redundansen er s\aa\ lav som mulig. Kvaliteten
        er h\o y n\aa r dette er oppfylt, og er et slags samlem\aa l p\aa\
        godheten av den parallelle beregningen.
  \end{description}
 \item
  \begin{enumerate}
   \item $S(n)$ antar sitt minimum n\aa r beregningen overhodet ikke
         inneholder noe parallellitet, dvs.\ n\aa r operasjonene m\aa\
         utf\o res sekvensielt Da er tidsforbruket p\aa\ en uniprosessor lik
         tidsforbruket p\aa\ en $n$-prosessor: $T(n)=T(1) \Rightarrow S(n)=1$.

         S(n) antar sitt maksimum n\aa r beregningen kan deles opp i $n$ helt
         uavhengige delberegninger, som hver kan kj\o res p\aa\ en av de $n$
         prosessorene.
         Da er $T(n)= \frac{1}{n} \cdot T(1) \Rightarrow S(n)=n$.
         Alts\aa\ er :
         \[ \underline{1 \leq S(n) \leq n} \]

   \item \[ E(n) = \frac{1}{n} \cdot \frac{T(1)}{T(n)}
                 = \frac{1}{n} \cdot S(n) \]
         \[ \Downarrow \]
         \[ \underline{\frac{1}{n} \leq E(n) \leq 1} \]

   \item \[R(n) = \frac{P(n)}{P(1)} \mbox{\hspace{3ex},\hspace{3ex}}
           U(n) = \frac{P(n)}{n\cdot T(n)} \]
         \[ \Downarrow \]
         \[U(n) = \frac{P(n)}{n\cdot T(n)} = \frac{P(n)}{P(1)}\cdot
                                             \frac{P(1)}{n\cdot T(n)}
                = R(n)\cdot \frac{P(1)}{n\cdot T(n)} \]
         \[ \Downarrow {\scriptstyle (P(1)=T(1))} \]
         \[\underline{U(n)}
           = R(n)\cdot \frac{T(1)}{n\cdot T(n)} = \underline{R(n)\cdot E(n)} \]

   \item \[\underline{Q(n)} = \frac{{T(1)}^3}{n\cdot {T(n)}^2\cdot P(n)}
                = \frac{T(1)}{T(n)}\cdot \frac{T(1)}{n\cdot T(n)}\cdot
                  \frac{T(1)}{P(n)} =\underline{\frac{S(n)\cdot E(n)}{R(n)}} \]

   \item \[ 1 \leq S(n) \leq n \]
         \[ \Downarrow \]
         \[ 1 \leq \frac{T(1)}{T(n)} \leq n \]
         \[ \Downarrow \]
         \[ \frac{1}{n} \leq \frac{T(1)}{n\cdot T(n)} \leq 1 \]
         \[ \Downarrow \]
         \[ \frac{1}{n} \leq E(n) \leq 1 \]
         Totalt antall enhetsoperasjoner kan ikke v\ae re mindre ved den
         parallelle bereg\-ningen enn den sekvensielle : $P(n) \geq P(1)$.
         Dette medf\o rer at
         \[ U(n) = \frac{P(n)}{n\cdot T(n)} \geq \frac{P(1)}{n\cdot T(n)}
                 = E(n) \]
         Den parallelle beregningen medf\o rer totalt $P(n)$ enhetsoperasjoner,
         som hver tar \'{e}n tidsenhet. Dersom disse operasjonene var helt
         uavhengige, ville de kunne utf\o res i l\o pet av $P(n)/n$ tidsenheter
         p\aa\ de $n$ prosessorene. Dersom det er avhengigheter tilstede vil
         tidsforbruket ($T(n)$) ta lengre tid. Alts\aa\ :
         \[ T(n) \geq \frac{P(n)}{n} \]
         \[ \Downarrow\]
         \[ U(n) = \frac{P(n)}{n\cdot T(n)} \leq 1 \]
         Disse tre resultatene viser at :
         \[ \underline{\frac{1}{n} \leq E(n) \leq U(n) \leq 1} \]

   \item \[ P(n) \geq P(1) \Rightarrow R(n) = \frac{P(n)}{P(1)} \geq 1 \]
         \[ E(n) = \frac{T(1)}{n\cdot T(n)} \leq \frac{T(1)}{P(n)}
                 = \frac{P(1)}{P(n)} = \frac{1}{R(n)} \]
         \[ \Downarrow \]
         \[ R(n) \leq \frac{1}{E(n)} \]
         \[ \frac{1}{n} \leq E(n) \leq 1 \Rightarrow
            1 \leq \frac{1}{E(n)} \leq n \]
         Disse tre relasjonene kan sammenfattes i :
         \[ \underline{1 \leq R(n) \leq \frac{1}{E(n)} \leq n} \]

   \item \[ Q(n) = \frac{T(1)}{T(n)}\cdot \frac{T(1)}{n\cdot T(n)}
                   \cdot \frac{T(1)}{P(n)}
                 = \frac{T(1)}{T(n)}\cdot \frac{T(1)}{n\cdot T(n)}
                   \cdot \frac{P(1)}{P(n)} \]
         \[ \Updownarrow \]
         \[ Q(n) = S(n) \cdot E(n) \cdot \frac{1}{R(n)} \]
         Siden $E(n) \leq 1$, $1/R(n) \leq 1$ og $S(n) \leq n$ m\aa\ vi ha
         at :
         \[ \underline{Q(n) \leq S(n) \leq n} \]

  \end{enumerate}
\end{enumerate}

}

\newpage
\Oppgave{% Problem 7.3, s. 396,  Hwang

\begin{enumerate}

\item Avbildningene er vist i figuren under:

\begin{figure}[htb]
\center
\input{losn7-fig1.latex}
\end{figure}

\item Hurtigbuffer-koherens, direkteavbildet:

\begin{table}[htb]
\begin{center}
\begin{tabular}{|r|c|c|c|c|c|c|c|c|c|c|c|} \hline
   	& \multicolumn{5}{c|}{Hurtigbuffer 1} & \multicolumn{5}{c|}{Hurtigbuffer 2} & Buss- \\ \cline{2-11}
Sykel	& 0	& 1	& 2 	& 3	& Hva?	& 0	& 1	& 2	& 3	& Hva?	& tilstand \\ \hline\hline
 1	&   	&	&	&	& Arb	&	&	&	&	& Arb	& Contention \\ \hline
 2	& RO 0 	&	&	&	& BF 0	&	&	&	&	& Wait	& Busy \\ \hline
 3	& CPU 0	&	&	&	&	&	&	& RO 2	&	& BF 2	& Busy \\ \hline
 4	& RW 0	&	&	&	& Hit	&	&	& CPU 2	&	&	& Idle \\ \hline
 5 	& RW 0	&	&	&	& Hit	&	&	& RW 2	&	& Hit	& Idle\\ \hline
 6	&	&	&	&	& Arb	&	&	&	&	& Arb	& Contention \\ \hline
 7	&	& RW 1	&	&	& BF 1	&	&	&	&	& Wait	& Busy \\ \hline
 8 	&  	& CPU 1	&	&	&  	& 	&	&	&	& Wait	& Idle\\ \hline
 9	& INV 0	&	&	&	& WB 0	& 	&	&	&	&	& Busy\\ \hline
10	&	& RW 1	&	&	& Hit	& RO 0	&	&	&	& BF 0	& Busy\\ \hline
11  	& RO 4	& 	&	&	& BF 4	& CPU 0	&	&	&	&	& Busy \\ \hline
12 	& CPU 4	&	&	&	& 	& RO 0	&	&	&	& Hit	& Idle \\ \hline
13	& 	&	&	&	& Arb	&	&	&	&	& Arb	& Contention\\ \hline
14	&	&	&	& RO 3	& BF 3	&	&	&	& 	& Wait	& Busy\\ \hline
15	&	&	&	& CPU 3	& 	&	&	&	& RW 7	& BF 7	& Busy\\ \hline
16	&	&	&	& RO 3	& Hit	&	& 	&	& CPU 7	& 	& Hit\\ \hline
17	&	&	&	& 	& Arb 	&	& 	&	&	& Arb	& Contention \\ \hline
18	&	&	&	&	& WB 1	&	& 	&	&	& Wait	& Busy\\ \hline
19	&	& RO 5	&	&	& BF 5	&	& 	&	&	& Wait	& Busy\\ \hline
20	&	& CPU 5	&	&	&	&	& RO 5	&	& 	& BF 5	& Busy\\ \hline
21	&	& RW 5	&	&	& Hit	&	& CPU 5	&	&	&	& Idle\\ \hline
22	&	& RW 5	&	&	& Hit	&	& INV 5	&	& 	& 	& Busy\\ \hline
23	&	&	&	&	& WB 5	& 	&	&	&	& 	& Busy\\ \hline
24	&	&	&	&	&	&	& RO 5	&	&	& BF 5	& Busy\\ \hline
25	&	&	&	&	&	&	& CPU 5	&	& 	&	& Idle\\ \hline
26	&	&	&	&	&	&	& RO 5	&	&	& Hit	& Idle\\ \hline
27	&	&	&	&	&	&	&	& 	& RW 7	& Hit	& Idle\\ \hline
28	&	&	&	&	&	&	&	&	& RW 7	& Hit	& Idle\\ \hline
29	&	&	&	&	&	& RO 0	&	&	&	& Hit	& Idle\\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{itemize}
\item Blank: ingen endring eller tom blokk.
\item RO n: Read only, block \#n
\item RW n: Read/write, block \#n
\item INV n: Invalidate block \#n
\item BF n: Fetch block \#n
\item WB n: Write back block \#n
\item Arb : Arbitrate
\end{itemize}

\newpage
\item Hurtigbuffer-koherens, 2-veis sett-assosiativ, LRU erstatnings-strategi:
\begin{table}[htb]
\begin{center}
\begin{tabular}{|r|c|c|c|c|c|c|c|c|c|c|c|} \hline
 	& \multicolumn{5}{c|}{Hurtigbuffer 1} & \multicolumn{5}{c|}{Hurtigbuffer 2} & Buss- \\ \cline{2-11}
Sykel	& 0 	& 1 	& 2 	& 3 	& Hva? 	& 0 	& 1 	& 2 	& 3 	& Hva? 	& tilstand\\ \hline \hline
 1	&   	&	&	&	& Arb	&	&	&	&	& Arb	& Contention \\ \hline
 2	& RO 0 	&	&	&	& BF 0	&	&	&	&	& Wait	& Busy \\ \hline
 3	& CPU 0	&	&	&	&	&	&	& RO 2	&	& BF 2	& Busy \\ \hline
 4	& RW 0	&	&	&	& Hit	&	&	& CPU 2	&	&	& Idle \\ \hline
 5 	& RW 0	&	&	&	& Hit	&	&	& RW 2	&	& Hit	& Idle\\ \hline
 6	&	&	&	&	& Arb	&	&	&	&	& Arb	& Contention \\ \hline
 7	&	& RW 1	&	&	& BF 1	&	&	&	&	& Wait	& Busy \\ \hline
 8 	&  	& CPU 1	&	&	&  	& 	&	&	&	& Wait	& Idle\\ \hline
 9	& INV 0	&	&	&	& WB 0	& 	&	&	&	&	& Busy\\ \hline
10	&	& RW 1	&	&	& Hit	& RO 0	&	&	&	& BF 0	& Busy\\ \hline
11  	&   	& 	& RO 4	&	& BF 4	& CPU 0	&	&	&	&	& Busy \\ \hline
12 	& 	&	& CPU 4	&	& 	& RO 0	&	&	&	& Hit	& Idle \\ \hline
13	& 	&	&	&	& Arb	&	&	&	&	& Arb	& Contention\\ \hline
14	&	&	&	& RO 3	& BF 3	&	&	&	& 	& Wait	& Busy\\ \hline
15	&	&	&	& CPU 3	& 	&	&	&	& RW 7	& BF 7	& Busy\\ \hline
16	&	&	&	& RO 3	& Hit	&	& 	&	& CPU 7	& 	& Hit\\ \hline
17	&	&	&	& 	& Arb 	&	& 	&	&	& Arb	& Contention \\ \hline
18	&	& RO 5	&	&	& BF 5	&	& 	&	&	& Wait	& Busy\\ \hline
19	&	& CPU 5	&	&	&	&	& RO 5	&	& 	& BF 5	& Busy\\ \hline
20	&	& RW 5	&	&	& Hit	&	& CPU 5	&	&	&	& Idle\\ \hline
21	&	& RW 5	&	&	& Hit	&	& INV 5	&	& 	& 	& Busy\\ \hline
22	&	&	&	&	& WB 5	& 	&	&	&	& 	& Busy\\ \hline
23	&	&	&	&	&	&	& RO 5	&	&	& BF 5	& Busy\\ \hline
24	&	&	&	&	&	&	& CPU 5	&	& 	&	& Idle\\ \hline
25	&	&	&	&	&	&	& RO 5	&	&	& Hit	& Idle\\ \hline
26	&	&	&	&	&	&	&	& 	& RW 7	& Hit	& Idle\\ \hline
27	&	&	&	&	&	&	&	&	& RW 7	& Hit	& Idle\\ \hline
28	&	&	&	&	&	& RO 0	&	&	&	& Hit	& Idle\\ \hline
\end{tabular}
\end{center}
\end{table}

\end{enumerate}
}


\end{document}
