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

En parallell beregning p\aa\ et $n$-prosessorsystem kan karakteriseres ved de
to st\o rrelsene $P(n)$, som er totalt antall enhets-operasjoner som skal
utf\o res, og $T(n)$, som er den totale utf\o relsestiden (i antall
tidsenheter) p\aa\ systemet. For en seriell beregning p\aa\ en uniprosessor
($n=1$), kan en skrive $T(1)=P(1)$, fordi hver enhetsoperasjon trenger \'{e}n
tidsenhet for \aa\ utf\o res.

Generelt gjelder at dersom beregningen inneholder noe parallellitet, er
$T(n) < P(n)$ for $n \geq 2$.

Lee (1980) har foresl\aa tt fem m\aa l p\aa\ ytelsen til en parallell beregning
i forhold til en tilsvarende seriell :

\[ \mbox{Hastighets\o kningen \hspace{3ex}} S(n) = \frac{T(1)}{T(n)}   \]
\[ \mbox{Effektiviteten \hspace{3ex}} E(n) = \frac{T(1)}{n\cdot T(n)}   \]
\[ \mbox{Redundansen \hspace{3ex}} R(n) = \frac{P(n)}{P(1)}   \]
\[ \mbox{Utnyttelsen \hspace{3ex}} U(n) = \frac{P(n)}{n\cdot T(n)}   \]
\[ \mbox{Kvaliteten \hspace{3ex}} Q(n) = \frac{{T(1)}^3}{n\cdot {T(n)}^2\cdot P(n)}
                                                        {\hspace{3ex} .} \]

\begin{enumerate}
 \item Finn fysiske betydninger av de ovennevnte ytelsesm\aa l.

 \item Vis at de f\o lgende relasjoner holder i alle mulige sammenlikninger
       mellom parallelle og serielle beregninger :
  \begin{enumerate}
   \item \[ 1 \leq S(n) \leq n \]
   \item \[ \frac{1}{n} \leq E(n) \leq 1 \]
   \item \[ U(n) = R(n)\cdot E(n) \]
   \item \[ Q(n) = \frac{S(n)\cdot E(n)}{R(n)} \]
   \item \[ \frac{1}{n} \leq E(n) \leq U(n) \leq 1 \]
   \item \[ 1 \leq R(n) \leq \frac{1}{E(n)} \leq n \]
   \item \[ Q(n) \leq S(n) \leq n \]
  \end{enumerate}
\end{enumerate}
}

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

Anta et to-prosessor system (P1 og P2) som benytter private
hurtigbuffere med tilbakeskriving. Se figuren under.  Systemet har
delt minne (hovedlager) og er koblet sammen vha. en felles buss. Hver 
hurtigbuffer har fire blokk-rammer merket 0, 1, 2 og 3. 
\begin{figure}[htb]
\center
\begin{picture}(305,260)(20,560)
\put(170,645){\makebox(0,0)[b]{\smash{Buss}}}
\thicklines
\put( 20,680){\framebox(100,80){}}
\put( 20,740){\line( 1, 0){100}}
\put(120,720){\line(-1, 0){100}}
\put( 20,700){\line( 1, 0){100}}
\put( 70,680){\line( 0,-1){ 40}}
\put( 70,780){\line( 0,-1){ 20}}
\put(220,780){\framebox(100,40){}}
\put( 20,780){\framebox(100,40){}}
\put(220,680){\framebox(100,80){}}
\put(270,680){\line( 0,-1){ 40}}
\put(220,700){\line( 1, 0){100}}
\put(220,720){\line( 1, 0){100}}
\put(220,740){\line( 1, 0){100}}
\put(170,640){\line( 0,-1){ 40}}
\put( 70,560){\framebox(200,40){}}
\put(270,780){\line( 0,-1){ 20}}
\put( 70,795){\makebox(0,0)[b]{\smash{Prosessor 1}}}
%\put( 70,795){\makebox(0,0)[b]{\smash{\SetFigFont{8}{9.6}{rm}Prosessor 1}}}
\put(270,795){\makebox(0,0)[b]{\smash{Prosessor 2}}}
\put( 20,640){\line( 1, 0){300}}
\put(125,745){\makebox(0,0)[lb]{\smash{Hurtig-}}}
\put(325,745){\makebox(0,0)[lb]{\smash{Hurtig-}}}
\put(170,575){\makebox(0,0)[b]{\smash{Hovedlager}}}
\put(325,730){\makebox(0,0)[lb]{\smash{buffer 2}}}
\put(125,730){\makebox(0,0)[lb]{\smash{buffer 1}}}
\put( 70,745){\makebox(0,0)[b]{\smash{0}}}
\put( 70,725){\makebox(0,0)[b]{\smash{1}}}
\put( 70,705){\makebox(0,0)[b]{\smash{2}}}
\put( 70,685){\makebox(0,0)[b]{\smash{3}}}
\put(270,745){\makebox(0,0)[b]{\smash{0}}}
\put(270,725){\makebox(0,0)[b]{\smash{1}}}
\put(270,705){\makebox(0,0)[b]{\smash{2}}}
\put(270,685){\makebox(0,0)[b]{\smash{3}}}
\end{picture}
\end{figure}
Det delte minnet er delt opp i 8 hurtigbuffer blokker 0, 1, ... 7.
For {\aa} opprettholde hurtigbuffer-koherens, benytter systemet en
3-tilstands (RO, RW, og invalid) snuse protokoll basert p{\aa}
skriv-ugyldiggj{\o}r strategien som er beskrevet i Fig. 7.15b i
l{\ae}reboka [Hwang93].

Anta at den samme klokken driver prosessorene og minne-bussen.  I
l{\o}pet av en sykel kan begge prosessorene sp{\o}rre om aksess for
bussen (bus request).  Hvis det oppst{\aa}r en simultan foresp{\o}rsel
fra de to prosessorene, vil P1 bli gitt aksess, mens P2 m{\aa} vente.

I alle tilfelle vil bussen tillate bare \'{e}n aksess pr.
transaksjonssykel.  N{\aa}r en buss-foresp{\o}rsel f{\o}rst er gitt,
m{\aa} transaksjonen fullf{\o}res f{\o}r neste foresp{\o}rsel
tillates.  S{\aa} lenge det ikke er buss-konflikt (Eng: contention),
vil minne-aksess fra hver prosessor trenge en eller to sykler for
{\aa} fullf{\o}res.   

\begin{itemize}

\item Lese-treff (read-hit) i hurtigbuffer trenger \'{e}n sykel og ikke
buss-aksess. 

\item Lese-bom (read-miss) i hurtigbuffer trenger to sykler (uten
buss-konflikt): \'{e}n for blokk-henting og \'{e}n for CPU lesing fra
hurtigbuffer.

\item Skrive-treff (write-hit) trenger \'{e}n sykel for CPU skriving
og buss-invalidering samtidig.

\item Skrive-bom (write-miss) trenger to sykler: \'{e}n for blokk-henting
og buss-invalidering, og \'{e}n for CPU skriving.

\item Utskifting av en modifisert (dirty) blokk trenger en sykel for {\aa}
oppdatere minnet via bussen.

\item Hvis det snakk om buss-konflikt, trengs en ekstra sykel for
buss-arbitrering i alle tilfeller ovenfor, untatt for lese-treff.

\end{itemize}

\begin{enumerate}

\item Vis hvordan {\aa}tte hurtigbuffer blokker avbildes til fire
hurtigbuffer blokker vha. en direkte-avbildet hurtigbuffer
organisering. Vi ogs{\aa} hvordan {\aa}tte hurtigbuffer blokker
avbildes ved bruk av en to-veis sett-asossiativ hurtigbuffer
organisering.  

\item Anta f{\o}lgende asynkrone sekvenser av minne-aksess
hendelser, hvor \em{tall} er skriving og resten er lesing.

\hspace*{1cm}Prosessor \#1: 0, \em{0}, 0, \em{1}, 1, 4, 3, 3, 5, \em{5}, 5 \\
\hspace*{1cm}Prosessor \#2: 2, \em{2}, 0, 0, \em{7}, 5, 5, 5, \em{7}, 7, 0

Spor (Eng: trace) utf{\o}relsen av de to sekvensene p{\aa} de to
prosessorene.  Begge hurtigbufferene er tomme fra starten av. Anta en
direkte-avbildet organisering av begge hurtigbuffere. Vis tilstanden
(RO eller RW) til hver valid blokk og merk hurtigbuffer-bom og
buss-tilstand (busy/idle) for blokk-sporingen for hver sykel.  Anta at
prosessorene starter samtidig, med f{\o}rste aksess i sykel 1. Beregn
treff-raten for hurtigbuffer 1 og 2.

\item Utf{\o}r beregningene i a) ogs{\aa} for en to-veis
sett-assosiativ hurtigbuffer-organisering med en LRU
erstatnings-strategi. 

\end{enumerate}
}


\end{document}



