Typtenta.fm

Kungl Tekniska Högskolan
Inst f Mikroelektronik och Informationsteknik
Typtentamen i
2G1510 Datorteknik fortsättningskurs
tisdag 2002-12-24, kl 14:00–18:00
Allmän information enligt KTH:s interna föreskrift 26/98
Examinator och ansvarig lärare: Fredrik Lundevall, telefon 08–790 4147.
Tentamensuppgifterna behöver inte återlämnas när du lämnar in din skrivning.
Inga hjälpmedel förutom miniräknare. Miniräknare får ej innehålla informationmed anknytning till kursen. Överträdelse härav betraktas som fusk.
Resultatet meddelas senast 13 januari 2003.
Information om rättning och betyg
För godkänt (betyg 3) krävs minst 8 poäng på uppgift 1 och minst 16 poäng
totalt. För betyg 4 (5) krävs dessutom minst 21 (26) poäng totalt.
Varje deluppgift ger 1 poäng om svaret är komplett och korrekt.
Skrivningar i cacheminnen
När cacheminnesuppslagning ska göras i denna uppgift delas adressen upp på följande sätt. Cacheminnena i denna uppgift är direktmappade och använder 32-bits adresser. Byte-adresseringanvänds, men endast 32-bits (4-bytes) referenser görs. De två minst signifikanta bitarna i adressenär alltid noll.
I var och en av deluppgifterna nedan antas cacheminne och skrivbuffert först vara tomma, varefter
nedanstående referenser görs i angiven ordning.
I var och en av deluppgifterna nedan ska du ange vilka referenser som medför läsning frånprimärminnet och vilka referenser som medför skrivning till primärminnet. Svaren behöver intemotiveras.
Vid läsning från primärminnet läses alltid ett helt block. Vid genomskrivning skrivs så lite som möjligt,det vill säga ett ord. Vid återskrivning skrivs alltid hela block.
Om indelning i delblock krävs så blir det lite extra att skriva. I så fall ska du ange dels attdelblocksindelning krävs, dels storleken på delblocken, och dessutom efter varje referens värdenapå giltigbitarna för varje delblock. Glöm inte att ange vilken giltigbit som är vilken! a) Cacheminnet i datorn "Konsonant" är av genomskrivningstyp, med platsreservation vid skrivmiss (allocate-on-write-miss) och hämtning vid skrivmiss (fetch-on-write).
b) Cacheminnet i datorn "Morfem" är av genomskrivningstyp, utan platsreservation vid skrivmiss (no allocate-on-write-miss). "Write-around" tillämpas, så att cacheminnet är opåverkat avskrivmissar.
Cacheminnet i datorn "Frikativa" är av genomskrivningstyp. "Write-validate" tillämpas, det vill
säga platsreservation vid skrivmiss (allocate-on-write-miss) utan hämtning vid skrivmiss
(no fetch-on-write).
d) Cacheminnet i datorn "Vokal" är av återskrivningstyp, med platsreservation vid skrivmiss (allocate-on-write-miss) och hämtning vid skrivmiss (fetch-on-write).
e) Förklara hur en skrivbuffert fungerar. Bör ett cacheminne av genomskrivningstyp kombineras Prestanda
En datortillverkare säljer bland annat de modeller som beskrivs i följande tabell.
Processorerna har olika uppbyggnad, men vi antar för enkelhets skull att de alla utför en instruktionper klockcykel när inga missar inträffar i förstanivåfickminnena. Förutsätt att programmet endast använder instruktioner som finns i alla processorerna.
Primärminnet innehåller all information som behövs — vi bortser alltså från sidfel.
50 procent av alla instruktioner använder minnet (som LOAD eller STORE i en Risc-dator).
a) Beräkna CPI-talen för de olika datorerna. Motivera kort.
b) Beräkna antal utförda instruktioner per sekund för de olika datorerna. Motivera kort.
Är MIPS-talen lämpliga jämförelsetal för de olika datorerna? Motivera.
d) Ett andranivåcacheminne förbättrar en komponent av medelåtkomsttiden. Vilken komponent? e) En processor med dynamisk instruktionsschemaläggning kan utföra oberoende instruktioner medan en cacheminnesmiss behandlas. Kan någonting motsvarande göras när processorn ärstatiskt schemalagd? Diskutera.
I många datorer finns samtidigt flera processer med separata virtuella adressrum. Översättningenfrån virtuell till fysisk adress beskrivs i en sidtabell. En TLB är ett cacheminne för information frånsidtabeller. Vid TLB-miss i en Risc-dator görs ett felavbrott, och en operativsystemsrutin sköter läsning avsidtabeller och uppdatering av TLB:n. Räkna upp och förklara de uppgifter som måste utföras avdenna rutin.
g) Datorn "Perugia" refererar förstanivåcacheminne och TLB samtidigt, i samma klockcykel. Har "Perugia" virtuellt eller fysiskt adresserat förstanivåcacheminne? Motivera utförligt.
h) I datorn "Monaco" måste förstanivåcacheminnet tömmas vid varje processbyte. Har "Monaco" virtuellt eller fysiskt adresserat förstanivåcacheminne? Motivera.
Statisk schemaläggning
Betrakta nedanstående DLX-program. Alla operander är 32 bit stora (= 4 bytes). Vid körning inträffar inga felavbrott.
Att en instruktion startas (instruction issue) innebär att beräkningen påbörjas. Alla operandvärdenoch andra nödvändiga resurser måste finnas tillgängliga för att en instruktion ska kunna startas. DLXstartar en instruktion varje klockcykel, med en begränsning: Om en LW-instruktion startas i cykel i, så kan det laddade värdet bara användas av instruktioner
som startas i cykel i+2 eller senare.
En oberoende LW- eller SW-instruktion kan dock startas i cykel i+1.
a) Ange alla beroenden i programmet.
b) Ange i vilken cykel varje instruktion startas när programmet körs på DLX.
Schemalägg programmet, det vill säga ändra instruktionernas ordning så att DLX kan köraprogrammet så snabbt som möjligt. Endast ordningen får ändras, inte registernummer ellernågot annat. Visa i vilken cykel varje instruktion startar när det schemalagda programmet körspå DLX.
"Gazpacho" är en snabbare processor för DLX-program. Om "Gazpacho" och DLX kör sammaprogram så blir resultaten identiska. "Gazpacho" har tre funktionsenheter: "Gazpacho" startar tre instruktioner varje klockcykel, om instruktionerna är oberoende och använderolika funktionsenheter. Beroenden kan fördröja starten av en eller flera instruktioner om det krävs föratt programmet ska leverera rätt resultat. Instruktionerna startas alltid i den ordning de står iprogrammet.
Även för "Gazpacho" gäller att om en LW-instruktion startas i cykel i, så kan det laddade ordet bara
användas av instruktioner som startas i cykel i+2 eller senare. En oberoende LW- eller
SW-instruktion kan dock startas i cykel i+1.
d) Ange i vilken cykel varje instruktion startas, när det ursprungliga DLX-programmet (utan några ändringar) körs på "Gazpacho".
e) Schemalägg programmet, det vill säga ändra instruktionernas ordning så att "Gazpacho" kan köra programmet så snabbt som möjligt. Endast ordningen får ändras, inte registernummer eller
något annat. Ange dels den nya ordningen på formen "i1, i3, i2, ." eller liknande, och dels i
vilken cykel varje instruktion startar när det modifierade programmet körs på "Gazpacho".
Inom vilka gränser kan en instruktion flyttas när en kompilator gör globalinstruktionsschemaläggning? Vilka gränser gäller för lokal instruktionsschemaläggning? Dynamisk schemaläggning
Tomasulos algoritm består av två delar: bokningsenheterna (reservation stations) ochresultatbussen (the Common Data Bus).
a) Bokningsenheterna infördes för att effektivisera programkörningen utan att dubblera funktionsenheterna (multiplikator, adderare, .). Effektiviseringen innebär att olika villkor gällerför start (issue) av en instruktion, beroende på om datorn har bokningsenheter eller ej. Vilkaolika villkor, och varför? b) Vid någon viss tidpunkt lägger multiplikatorn ut ett resultat på resultatbussen. Vilka enheter läser En programslinga av nedanstående typ ska köras på en dator som använder Tomasulosalgoritm.
FOR i := 1 TO 10 DO Variabeln sum är av typen REAL, det vill säga flyttal. Antag att kompilatorn placerat variabelnsum i ett visst flyttalsregister. Hur förändras innehållet i detta register under körningens gång?Motivera. d) Påverkas svaret på föregående deluppgift av fickminnesmissar? Påverkas svaret av avbrott Prefetching
Tre sätt att med maskinvara och/eller programvara minska den tid ett program ägnar åtdataminnesreferenser är ickeblockerande läsning i cacheminnet (non-blocking load), maskinvarustyrd förbeställning (hardware prefetching), samt programvarustyrd förbeställning (software prefetching).
Jämför dessa metoder med avseende på hur de påverkar: a) andel missar i fickminnet (miss rate), b) antal läsningar och skrivningar i underliggande minne per tidsenhet (memory bandwidth), antal exekverade instruktioner (number of executed instructions), samt d) genomsnittlig miss-penalty (average miss penalty).
Hopplöshet
a) För 1-bits hoppgissning behövs ett minne. Föreslå lämplig ordlängd och lämplig totalstorlek hos detta minne. Motivera. Förklara också hur minnet kopplas in i processorn.
b) Förklara hur 2-bits hoppgissning fungerar och på vilket sätt den kan vara bättre än 1-bits.
Förklara skillnaden mellan statisk och dynamisk hoppgissning.
d) Förklara hur och varför korrelerad dynamisk hoppgissning fungerar.
e) Definiera begreppet "precisa felavbrott". Förklara varför precisa felavbrott kan försämra

Source: http://www.ict.kth.se/courses/IS1201/extentor/typtenta.pdf