\underline{Oppgave 1:}

a) • 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å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 ønskede data blir returnert. Innslaget i hurtigbufferen til den prosessoren som ø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ørsler kan genereres samtidig, men blir prosessert sekvensielt av minne-kontrolleren.

[figure: home; only clean; cached; Prosessorer; Hovedlager; pending; ny; ny; les hurtigbuffer; For; Etter]

• 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ørsel først rette dens les-hurtigbuffer transaksjon til hovedlageret, men vil motta en peker til hurtigbufferen som har konsistente data.

[figure: home; gammel; ); (; ny; home; les hurtigbuffer; pending; olds[0]; gammel; ); (; ny; Etter; Hovedlager; (1); pend; -copy; (2); Prosessorer; olds[1]; news; For]

En annen hurtigbuffer-til-hurtigbuffer transaksjon, kalt “prepend”, blir flyttet fra hurtigbuffer A til B. Hurtigbuffer B setter sin bakoverpekende peker til å peke på hurtigbuffer A og returnerer de ø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ølge A i listen.

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

Fordelen med en lenket katalog sammenlignet med en “full-map” katalog er at man sparer plass nå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ære proporsjonal med P. Hvis en “full-map” katalog brukes trengs en bit for å angi om en prosessor har en spesiell blokk i hurtigbufferen. Det totale antall slike bit blir O(MP) = O(P^{2}). På den annen side hvis en lenket katalog blir brukt, trenger hver blokk bare å opprettholde en peker til den første prosessoren som har den respektive blokken. Hver peker trenger O(logP) bit, slik at det totalt trengs O(MlogP) = O(P logP) bit. Dette gjør SCI mer skalerbar enn en “full-map” katalog.

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

\underline{Oppgave 2:}

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

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

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