45214 Datamaskinarkitektur - Øvinger 1995

Oppgave 1

For et hurtigbuffer- ( cache-) system skal det foretas en vurdering av styringsstrategiene gjennomskriving med blokkallokering ved skriv ( write-through-with-write-allocate, WTWA) og skriv tilbake (write-back, WB) mot hverandre.

Anta ingen gjennomlesing (dvs. ved en sidefeil får ikke CPU'en sine data før hele blokken er lest inn i hurtigbufferet). Hver blokk består av b ord, som kan overføres mellom hovedlageret og hurtigbufferet i løpet av b+c-1 tidsenheter, der c er hovedlagerets syklustid oppgitt i antall ganger hurtigbufferets syklustid. Hurtigbufferets treffrate h antas uavhengig av strategien. Sannsynligheten for at en lagerreferanse er en skriv betegnes med , og sannsynligheten for at en blokk som skal erstattes har blitt modifisert (kun interessant i forbindelse med WB-strategien) betegnes med . Normalt er .

1. Finn forventningsverdien av den tiden det tar å\ betjene en referanse, uttrykt ved de ovennevnte stø relsene, for begge de to strategiene.

2. Oppgitt: og . Hvordan går det med betjeningstiden med de to strategiene når
   1. ?
   2. ?

3. Finn et generelt uttrykk som viser når WTWA er bedre enn WB som en funksjon av h og b. Anta at c=10 og som over.

Oppgave 2

Du skal se på utførelsen av to programmer som utføres samtidig av to prosessorer med delt minne. Anta at A, B, C, D er satt til 0 fra starten av og at Print-setningen skriver begge argumenter udelelig, i samme sykel. Ut-data fra programmene blir en 4-tuppel, dvs. verdiene til de 4 variablene i rekkefølge, enten ADBC eller BCAD. Vi har følgende to program, med tilsammen 6 setninger:

1. List opp alle utførelses-rekkefølger bestående av 6 setninger som vil beholde rekkefølgen av setningene i hvert enkelt program.

2. Anta at program-rekkefølgen blir beholdt, og at alle minne-aksesser er atomiske, dvs. en skrive-operasjon utført av én prosessor ses umiddelbart av alle de andre prosessorene. List alle mulige 4-tuppel av ut-data kombinasjoner.

3. Anta at program-rekkefølgen blir beholdt, men at minne-aksesser ikke er atomiske, dvs. en skrive-operasjon utført av én prosessor kan bli bufret slik at enkelte andre prosessorer ikke nødvendigvis vil kunne observere oppdateringen umiddelbart. List alle mulige 4-tuppel av ut-data kombinasjoner.