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

\Oppgave{% Problem 9.10, Hwang

\begin{enumerate}

\item 
\begin{itemize}

\item Alle hurtigbuffere er initielt ugyldige, og alle
hovedlager-blokker er markert ``uncached''.  Den delte listen lages  
i den hurtigbufferen hvor et innslag er endret fra ugyldig til en
vente-tilstand (``pending'').  N{\aa}r en les-hurtigbuffer transaksjon
blir startet av en prosessor og dirigert til minne-kontrolleren, blir
minne-tilstanden endret fra ``uncached'' til ``cached'' og de
{\o}nskede data blir returnert.

Innslaget i hurtigbufferen til den prosessoren som {\o}nsker data,
blir deretter endret fra ``pending''-tilstanden til en
``only-clean''-tilstand.  Oppbyggingen av den delte listen er vist i
figuren under.  Multipple foresp{\o}rsler kan genereres samtidig, men
blir prosessert sekvensielt av minne-kontrolleren.

\begin{figure}[htb]
\center
\input{losn9-fig2.latex}
\end{figure}

\item For senere minne-aksesser er hovedlager-tilstanden ``cached'',
og hurtigbuffer-hodet i den delte listen har sannsynligvis ``dirty''
data.  Som vist i figuren under, vil en ny foresp{\o}rsel f{\o}rst
rette dens les-hurtigbuffer transaksjon til hovedlageret, men vil
motta en peker til hurtigbufferen som har konsistente data.

\begin{figure}[htb]
\center
\input{losn9-fig3.latex}
\end{figure}

En annen hurtigbuffer-til-hurtigbuffer transaksjon, kalt ``prepend'',
blir flyttet fra hurtigbuffer A til B.  Hurtigbuffer B setter sin
bakoverpekende peker til {\aa} peke p{\aa} hurtigbuffer A og
returnerer de {\o}nskede data.  De halv-trukne linjene viser
transaksjoner mellom en prosessor og hovedlager eller en annen
prosessor.  De hel-trukne linjene viser delt liste-pekere.  Etter
transaksjonen blir den innsatte hurtigbufferen A det nye ``hodet'',
og det gamle hodet (B) vil f{\o}lge A i listen.

\end{itemize}


\item 

Sammenlignet med en bakplan-buss, vil en lenket katalog gi st{\o}rre
b{\aa}ndbredde og bedre mulighet for skalering.   Kostnaden reduseres
siden man ikke trenger buss-snusings-kontrollere.  Den tillater et
invaliderings-signal {\aa} bli sendt til spesielle prosessorer i
stedet for {\aa} kringkaste signalet til alle prosessorene.  Det kan
imidlertid ta lengre tid f{\o}r signalet n{\aa}r fram til de riktige
prosessorene.

Fordelen med en lenket katalog sammenlignet med en ``full-map''
katalog er at man sparer plass n{\aa}r katalog informasjonen skal
lagres.  Vi antar at det er $P$ prosessorer i systemet og at det
er $M$ minne-blokker.  $M$ vil typisk v{\ae}re proporsjonal med $P$.
Hvis en ``full-map'' katalog brukes trengs en bit for {\aa} angi om en
prosessor har en spesiell blokk i hurtigbufferen.  Det totale antall
slike bit blir $O(MP) = O(P^2)$.  P{\aa} den annen side hvis en lenket
katalog blir brukt, trenger hver blokk bare {\aa} opprettholde en
peker til den f{\o}rste prosessoren som har den respektive blokken.
Hver peker trenger $O(log P)$ bit, slik at det totalt trengs $O(M log
P) = O(P log P)$ bit.  Dette gj{\o}r SCI mer skalerbar enn en
``full-map'' katalog.

En lenket katalog har ogs{\aa} to ulemper sammenlignet med en
``full-map'' katalog.  For det f{\o}rste vil tiden det tar for {\aa}
sende et ugyldiggj{\o}r-signal til alle prosessorene som har en kopi
av en minne-blokk som ikke lenger skal v{\ae}re gyldig, v{\ae}re
st{\o}rre n{\aa}r antall prosessorer blir stort.   Grunnen til det, er
at i en ``full-map'' katalog kan ugyldiggj{\o}r-signalet sendes i
parallell til alle prosessorene, mens i en lenket katalog m{\aa}
signalet propageres gjennom lenken, noe som tar tid.  For det andre
vil det v{\ae}re vanskeligere {\aa} konstruere protokollen.  P{\aa}
grunn av st{\o}rre forsinkelse, kan ``race'' tilstander lettere
oppst{\aa}.  Dette m{\aa} man ta hensyn til under konstruksjonen av
protokollen.

\end{enumerate}
}

\Oppgave{% Problem 9.17, Hwang

\begin{enumerate}

\item En fin-struktur prosessor har typisk lite minne.  N{\aa}r
stor-skala datamaskiner skal konstrueres, vil fin-struktur
prosessorer passe bedre med fin-struktur programvare for parallellitet
og har ogs{\aa} lavere kostnader sammenlignet med middels-kornete
prosessorer. 

\item I en-prosessor systemer er det bare ett adresserings-rom.  Mange
programmer har blitt utviklet med tanke p{\aa} dette.  Ett enkelt,
globalt adresserings-rom tilbyr en kontinuitet og kan forenkle
system-utviklings-prosessen ettersom programmererne ikke trenger {\aa}
bry seg s{\aa} veldig mye med meldings-overf{\o}rings-mekanismer
p{\aa} individuelle maskiner.  Det forenkler ogs{\aa} oppdeling av
data og dynamisk last-balansering og {\o}ker portabilitet til
programmer mellom maskiner med forskjellig arkitektur.

\item P{\aa} grunn av h{\o}y synkroniserings-kostnad, trenger grovkornet
parallellitet store mengder beregninger, slik som mange iterasjoner,
til hver prosessor.  Dermed blir ikke lav-niv{\aa} parallellitet fullt
utnyttet for individuelle iterasjoner og instruksjoner.  Med tanke
p{\aa} skalerbarhet, n{\aa}r tallet p{\aa} prosessorer {\o}ker, vil
det v{\ae}re viktig {\aa} ta hensyn til slik lav-niv{\aa}
parallellitet for {\aa} redusere beregnings-tiden og {\o}ke ytelsen.
Dette taler for fin-struktur parallellitet i stedet for middels- og
grovkornet parallellitet.
\end{enumerate}
}

\end{document}

