ehammarstrom / eit070 Goto Github PK

Författare:

Emil Hammarström

Adam Thuvesen

Pontus Ovhagen

Koffeindonationer uppskattas.

1. Vad är Moores lag?

   Observation av att antalet transistorer dubblas vartannat år.

   Vad är Murphys lag?

   "Om något kan gå fel kommer det förr eller senare att göra det"

   Lycka till på tentan.

2. Vem är von Neumann?

   Pionjär inom mängdlära, spelteori, kvantfysik och datavetenskap. Grundare till von Neumann-arkitekturen som har använts sedan 1940-talet.

3. Vad gör en kompilator?

   Transformerar källkod till ett annat datorspråk. Detta kan vara maskinkod, eller ett mellanspråk.

4. Vad gör en assemblator?

   Översätter assembler till maskinkod.

5. Ge exempel på ett högnivåspråk?

   Java

6. Vad skiljer ett högnivåspråk från ett maskinspråk?

   Maskinspråk är binärkod som procerssorn direkt kan tolka. Högnivåspråk kan ej tolkas av processorn och har en hög abstraktionsnivå.

7. Görs alla beräkningar (ADD, SUB, ..., AND, OR) i ALU:n?

   Alla integer beräkningar görs av ALU:n, men till flyttal används en FPU (Floating-point-unit).

8. Ge exmpel på indata och utdata till en kontrollenhet.

   In- och utdata för ALU och Kontrollenhet

    Kontrollenhet
    Indata:
    00001   01110001    011
    MOVE    ADDRESS     REGISTER
    Utdata: "Säga till processorn vilken operation och vilka register som skall användas"
   
    ALU
    Indata:
    IN1, IN2, + Eventuella statussignaler
    Utdata:
    UT, + Eventuella statussignaler
   

9. Ge exempel på fördelar med att använda register för att lagra data.

   Accesstiden för registerlagring är flera potenser snabbare. Access av data i processorregister förväntas ta få antal ns, L1 tar ~10ns, L2 10-tal ns, RAM ~100ns (Primärminne), HDD 10-tal ms (Sekundärminne).

10. Om en processor gör fetch och execute, vad görs under fetch? Vad görs under execute? Är det som görs under fetch samma för alla instruktioner?

    Se svar till fråga 25 och 26. Och fetch är detsamma för alla instruktioner.

11. Ge exempel på system där man hittar datorer.

    Apollos vägledningsdator. Industrisammanhang. Algoritmisk börshandel. Dammportar.

12. Vad finns det för olika typer av datorer?

    Smartphone, bärbar dator, persondator, superdator, minidator, servrar?

13. Var kan man hitta processorer?

    Överallt! Microprocessorer överallt, miniräknare, programmerbara styrsystem osv.

14. Vad kännetecknar ett minne som är volatile?

    Flyktigt minne, RAM, återställs/töms när strömtillförseln stryps.

15. Ge exempel på minnen som är volatile.

    RAM (Primärminne) och Processorregister

16. Vad kännetecknar ett minne som är non-volatile?

    Minne som kvarstår, bevaras och kan förflyttas fysiskt utan systemkoppling.

17. Ge exempel på minnen som är non-volatile.

    HDD (Sekundärminne) roterande skivor med magnetisk beläggning.

18. Vid IC tillverkning, vad gör en dicer?

    Skär ut rektangulära chip-skivor ur de stora runda siliconskivorna.

19. Vem grundade Intel?

    Gordon E. Moore och Robert Noyce

    Vem grundade AMD?

    Jerry Sanders III och Edwin Turney

20. Vad är Moores lag?

    Se svar till fråga 1.

21. Vad består en von Neumann-arkitektur av?

    

22. Vad används en kompilator till?

    Se svar till fråga 3.

23. Vad är skillnaden mellan ett högnivåspråk och maskinkod?

    Se svar till fråga 6.

24. Ge exempel på högnivåspråk.

    Se svar till fråga 5.

25. Vad händer under fetch fasen?

    1. Vi hämtar instruktionen där PC pekar
    2. Vi flyttar instruktionen till CPU:n (Instruction Register)
    3. Ökar PC

26. Vad händer under execute fasen?

    1. Avkodar instruktionen till operationer som processorn skall göra med specifierade register.
    2. Vi exekverar den operation som Fetch gav oss. Detta kan vara att hämta data eller göra en beräkning.
    3. Vi lagrar datan i det register eller på den minnesplats Fetch gav oss.

27. Vad är en ALU?

    Arithmetic Logic Unit (Aritmetisk Logisk Enhet) som utför logiska operationer så som AND, OR, ADD och SUB.

28. Varför finns registren i en processor?

    För snabb åtkomst av data samt mellanlagring vid beräkningar.

29. Nämn olika typer av register?

    Data register, Address register (har stack pointern), Generella register, Status register (ex. bool flaggor för jämförelser) osv.

30. Hur många flanker finns det i en klockcykel?

    2 (En flank är en övergång mellan hog och låg signalnivå)

31. Hur många bitar behövs för att lagra ett tal som har värden mellan 0 och 255?

    8 bits

32. Hur många bitar behövs för att lagra en unsigned char?

    1 byte = 8 bits

33. Vilka värden kan en unsigned char ha?

    0-255

34. Hur fungerar 2-komplement?

    Den första biten avgör om talet är positivt eller negativt, 1 negativt, 0 positivt. Om inledande bit är 1 och följande 7 också är 1, dvs. 1111 1111, har vi -1. Detta kan ses som att man har -128 och adderar 0111 1111 (127) vilket blir -1. 0000 0000 blir fortfarande 0. Övre gräns blir 127 och undre -128 för en signed char.

35. Vad är Little Endian?

    En variation av hur vi representerar tal vid lagring i minne.

    Little Endian innebär att du lagrar den minst signifikanta biten först. Om vi har ett ord 0A 0B 0C 0D kan vi lagra detta i minnet som 0D, 0C, 0B, 0A. I Big Endian (American Supersize-Me Endian) hade vi lagrat 0A, 0B, 0C, 0D.

36. Vad gör en kontrollenhet i en processor?

    Se svar 25.3 till fråga 25.

37. Hur lång är en klockperiod i en processor som har en frekvens på 1GHz?

    1/1Ghz = 1ns

38. Om varje instruktion tar 10 klockcykler, hur många instruktioner hinner en processor om frekvensen är 1GHz?

    1Ghz/10 = 0.1G = 100M

39. Hur kan val av algoritm påverka hur snabbt ett program exekverar?

    Vi kan minska antalet instruktioner för att ex. komma åt ett värde i en datastruktur dvs. göra en sökning efter ett värde i en struktur.

40. Hur påverkar läsning och skrivning till minne prestandan hos en processor?

    Enormt, om vi säger att en instruktion tar 10 klockcykler med en 1Ghz processor så tar en instruktion 10ns, jämför detta med att hämta datan först från primärminne, 100ns, och sekundärminne, 10 000 000ns.

41. Vad blir det binära talet 0b101111 decimalt?

    47

42. Vad blir det binära talet 0b101111 hexadecimalt?

    0x2F

43. Vad blir det hexadecimala talet 0xFE1A decimalt?

    65050

44. Vad blir det hexadecimala talet 0xFE1A binärt?

    0b1111111000011010

1. Vad är pipelining?

   Pipelining är när vi kör flera olika instruktioner samtidigt. Exempelvis, om vi har instruktionerna Fetch och Execute så kan vi köra en Fetch och en Execute samtidigt men aldrig 2 Fetch samtidigt.

2. Vilka konflikter kan uppstå i en pipeline?

    Fetch instruction (FI)
    Decode instruction (DI)
    Calculate operand address (CO)
    Fetch operand (FO)
    Execute instruction (EI)
    Write operand (WO)
   

   Strukturella Hazards

   Resursproblem, vi kan ej göra fetch av instruktion och operand samtidigt från minne. Detta kan lösas genom att förskjuta en pipeline med 1 nop, om hämtning görs i register händer inget.

   Vi kan också lösa detta genom att ha ett cacheminne för instruktioner och ett för data (operander).

   Data Hazards

   Om en instruktion gör en beräkning och nästa instruktion är beroende av den instruktionen så får vi ett gammalt värde om vi ej stallar 2 cykler.

    FI  DI  CO  FO  EI  <WO>                (MUL R2, R3)
   
        FI  DI  CO  <FO>  EI  WO            (ADD R1, R2) (FO before WO)
   
            FI  DI  CO  <FO>  EI  WO        (FO collides with WO)
   
                FI  DI  CO  <FO>  EI  WO    (FO after WO, this is OK)
   

   För att minska stalls (penalty) kan forwarding/bypassing användas. Detta innebär att vi kan placera resultatet på ALU:ns ingång direkt.

   

   Vi får nu 1 stall istället:

   

   Vi kan även ändra ordningen på instruktioner för att inte ha efterliggnade registeraccess, se figur

   

   Kontroll Hazards

   Uppstår på grund av hopp (branching).

   Unconditional Branch

   Vi försöker alltid beräkna nästa instruktion i en pipeline, men om vi har ett hopp så skall vi ju inte hämta den nästliggande instruktionen. Detta innebär att vi gör en fetch i onödan och vi måste vänta 2 stalls och en felläsning innan vi vet vilken instruktion som är den vi skall hämta (måste göra en fetch operand på branchen där operanden är hoppaddressen), se figur.

   

   Conditional Branch

   Samma princip gäller här, men här får vi 2 stalls även om vi inte skall hoppa. Vi måste även vänta här på att BEZ branchen har FO rätt address, även om det är nästa.

   

3. Illustrera hur konflikter uppstår?

   Se svar till fråga 2.

4. Vad kan man göra för att undvika konflikter?

   Se svar till fråga 2.

5. Vad är branch prediction?

   Statisk prediktion Gör ett fast antagande, se figur.

   

   Dynamisk prediktion

   Vi kan göra en kvalificerad gissning för huruvida ett hopp kommer att ske eller ej.

   1-bit: Om vi har gjort ett hopp tidigare kan vi gissa att det kommer att göras igen.

   2-bit: Görs med hjälp av en state machine, se figur nedan.

   

6. Vad är spekulativ exekvering?

   När vi börjar exekvera instruktioner baserat på tidigare nämnd branch prediction.

7. Delayed branching - vad är det? Vinst? Ge exempel.

   Det är när vi beräknar en instruktion som skall göras men ej påverkar branchen efter branch instruktionen. Då slipper vi en eventuell stall efter i det fall då vi inte skulle göra den beräkningen ((un)conditional branch stall). Nu gör vi alltid en beräkning som alltid ska göras, på så sätt får vi inte en (2-3) onödig stall varje gång efter branch.

   Assemblatorn lägger alltid en nyttig beräkning efter branchen med delay. Innan hade vi alltid stalls.

8. Delayed load - vad är det? Vinst? Ge ett exempel.

   När vi använder LOAD och STORE hinner dessa operationer ej utföras på en klockcykel. Detta innebär att om vi försöker LOAD:a ett värde och sedan direkt efter har en instruktion som skall utföra en beräkning med det laddade värde så går detta ej då värdet inte hunnit laddas in. Se figur.

   

9. Ge exempel på en kompilatorteknik som används för att undvika/hantera konflikter i pipelinen.

   Delayed branching, automatisk nop-insättning efter känsliga instruktioner för strukturella- och datakonflikter, som lw (Load Word).

1. Hur lagras information på en hårddisk?

   Lagras med hjälp av sektorer på magnetisk disk.

2. Vad är random access när man talar om minnen?

   Minne lagras random, så att accesstiden uppfattas lika för alla hämtningar.

3. Ge exempel på minne som inte har random access?

   Sekundärminne (Hårddisk)

4. Vad är en minneshierarki?

   

5. Varför uppstår en minneshierarki?

   Avstånd från processor, hastighet, datamängd och pris.

6. Vad kallas principen som gör att cacheminne fungerar?

   Om du skall loopa över instruktioner ett flertal gånger så tjänar man på att lagra dessa i cacheminnet. Om du däremot bara läser in instruktioner sekventiellt utan loop så tjänas inget av cachen.

7. Vad är en cachemiss? Varför uppkommer en cachemiss? Hur hanteras det?

   En cachemiss är när vi ex. vill läsa eller skriva data till L1 cachen men den har inte addressblocket vi söker. För att hantera detta söker man i nästa cachesteg, L2. Sedan L3. Om detta ej fungerar så måste vi antingen hämta block från primärminnet eller göra en direktskrivning/direktläsning.

8. Cacheminnen kan ha olika mappningar - vilka? Hur fungerar varje mappning?

   Direktmappning - Vi söker på cacheline, om vi hittar rätt cacheline då kollar vi om taggen stämmer. Vi lagrar med en direktmappning, det vill säga, cacheline blir 14 least significant bits i primärminnesaddressen och taggen blir 8 most significant bits av primärminnesaddressen.

   Associative mappning - Vi använder nu endast tags, och får göra större sökningar då vi inte har direktmappat minne utan vi slänger in primäraddress som tag (-2 bit för byte target, ges av cpu).

   2-way set associative mappning - Direktmappning fast med ett set om 2 platser.

9. I direktmappning, hur ersätts cacherader vid cachemissar?

   De skrivs över.

10. Vad är en ersättningsalgoritm?

    

11. Vad menas med att cacheminnet ej är konsekvent? Och hur hålls ett cacheminne konsekvent?

    Om vi har en loop där en variabel förändras kommer denna ej ha samma värde i cacheminne som primärminne.

    Såhär gör man,

    

12. Antag ett program som exekverar alla instruktioner i en sekvens (en i taget) och att det finns ett cacheminne för instruktioner där cacherader har storlek 64bytes och varje instruktion kräver 2 bytes. Vad är sannolikheten för att nästa instruktion finns i samma cacherad som förra instruktion?

    1/32

13. Vad är fördelen med paging?

    Ett program består av flera pages och vi laddar inte in hela programmet utan endast de pages som behövs i primärminnet.

14. Vad är nackdelar med paging?

    Sidfel.

15. Vad är fragmentering när vi pratar om paging?

    När massor med småplatser uppstår i primärminnet detta gör att vi ej kan kicka igång stora program.

16. Vad är skillnaden på extern fragmentering och intern fragmentering?

    Extern fragmentering

    Ledigt lagringsutrymme som delas upp i mindre platser som inte ligger jämte varandra.

    Intern fragmentering

    Allokerar lagringsutrymme som ej används. Filer mindre än blocket gör att vi har slösaktig allokering. Kom ihåg att detta kan vara accepterbart i gengäld mot ökad effektivitet och enkelhet.

17. Vad är paging?

    Se svar till fråga 13.

18. Vad är en sida (page) och en ram (page frame)?

    Ett program är indelat i flera pages.

    En page frame är en fixt längd ram i primärminnet som lagrar pages för snabbare access.

19. Om en sida är 2kBytes, kan man säga något om storleken på primärminnet? Kan man säga något om storleken av en ram (page frame)?

    Vi kan ej avgöra primärminnets storlek. Men vi vet att en page frame har samma storlek som en page, för att förhindra intern fragmentering i en page frame.

20. Vad är demand paging?

    Vi laddar endast de sidor som behövs.

21. Vad är så kallad thrashing? När uppkommer det?

    Vi försöker byta ut pages från sekundärminne till primärminne för ofta (Många program igång samtidigt).

22. Vad är skillnaden på paging och virtuellt minne?

    virtuellt minne

    Virtuellt minne är när vi behöver mer minne än vad som finns fysiskt, då allokerar vi en del minne på sekundärminnet för pages.

    paging

    Vi delar upp vårt program i delar.

23. Vad är sidfel?

    När sidan ej finns i primärminnet.

24. Vad händer vid sidfel? Hur hanteras det?

    Vi får en miss i primärminnet och laddar då in sidan från sekundärminnet in i primärminnet i en ram.

1. Vad gör ett operativsystem?

   Programvara som agerar abstraktion mellan maskinvara och applikationer (Tillämpningsprogram).

2. Vad är multitasking?

   Körning av flera processer samtidigt.

3. En användare känner att flera program exekverar samtidigt, hur är det möjligt?

   Schemaläggaren hanterar exekvering, tilldelar körningstid.

4. Vad är ett kontextbyte?

   Ett byte av tråd som exekverar.

5. Hur går det till? Hur vet man om att det ska ske? Vem är inblandad?

   Vi sparar det körande stadiet och sedan laddar vi in det stadie som skall köras. Sedan körs detta stadie, och sparas sedan när vi vill ladda tillbaka det som kördes från första början.

   Det genereras av en extern klocka eller när ett program gör ett systemanrop.

   Schemaläggaren är inblandad.

6. Behövs avbrott för att klara av att göra kontextbyten?

   Ja.

7. Hur fungerar avbrott?

   Vi sparar vår stackpekare och hoppar till en avbrottsstack för att undvika att minnet tar slut för det program som körs.

8. Om man skapar en struktur för att lagra filer, vad vill man uppnå?

   Målet är att vi skall kunna lagra stora filer och nå dem snabbt. (Utnyttja hårddisken maximalt)

9. Om man ska läsa in en fil från en hårddisk, vad påverkar lästiden?

   Läshastighet på hårddisk. Nuvarande användning av hårddisken (Aktivitet). Filsystemsformat. Fragmentering.

1. Vad är skillnaden mellan primärminne och sekundärminne?

   Se svar till fråga Processorn 15, 17.

2. Om du skall föreslå ett sätt att lagra filer på ett sekundärminne, vilka avvägningar gör du (och vilka parametrar avgör)?

   Cluster skall ligga så nära varandra som möjligt. Vi bör ha en ordentlig datastruktur för att inte behöva lägga ner tid att söka efter våra cluster. Små cluster kan ge mindre fragmentering.

3. Varför behövs cacheminnen?

   För att effektivisera processorns exekveringstid. Hämtningar är processorns svaga länk.

4. Vad är en minneshierarki?

   Se svar till Minne fråga 4.

5. Vilken princip gör att cacheminnen fungerar?

   Se svar till Minne fråga 6.

6. Vad är en cacherad?

   En cacherad innehåller tag, cacheline och data.

7. På vilka sätt kan man bygga ett cacheminne?

   Vi kan ha ett cacheminne till data och ett till instruktioner. Eller så har vi ett unified cacheminne.

8. Vilka paramterar måste man bestämma om man har ett cacheminne av storlek N bytes som ska användas till ett primärminne med storlek M bytes?

   Tag, cacheline, Valid bit.

9. Vad gör en tag?

   Identifierar en cacherad.

10. Varför har man flera nivåer i ett cachesystem?

    För att kunna lagra det man använde absolut senaste och om det inte är absolut senaste så finns det i en nivå upp. Och vi har flera nivåer då vi vill ha små och snabba cacheminnen närmst processorn. Så vi baserar cachestorlek på lokalitetsprincip.

11. Varför har man I-cache och D-cache?

    För att minimera stalls i pipeline. FO, FI och WO, WI kan göras samtidigt.

12. Vad är TLB?

    Translation Look-Aside Buffer.

    Det är i princip en cache för endast pages. Används för att minimera tiden för att hitta en page location.

13. Måste man ha en skrivstrategi?

Ja.

14. Varför används paging?

    För att dela upp ett program i flera sidor, detta tillåter oss att använda primärminnet för att köra program.

15. Var lagrar man sidtabellen?

    I det virtuella minnet.

16. Hur många instruktioner är aktiva i en pipeline med 6-steg?

    6

17. Hur påverkas kontrollenheten av pipelining?

    ..

18. Vilka problem kan uppkomma med pipelining?

    Se svar till Pipelining fråga 2.

19. Ge exempel på hur dessa problem uppkommer.

    Se svar till Pipelining fråga 2.

20. Hur löser man dessa problem?

    Se svar till Pipelining fråga 2.

21. Hur kan kompilatorn förhindra dessa problem?

    Automatic nopping eller ändring av instruktionsordning.

22. Vad är en LOAD & STORE arkitektur?

    RISC är ett exempel på en LOAD, STORE arkitektur. Det bygger på att man läser och skriver mellan register och minne.

1. Vad är superscalar?

   En arkitektur som tillåter att mer än en instruktion initieras samtidigt. De exekveras oberoende av varandra.

2. Vad är superscalar pipelining?

   Det ger oss möjligheten att initiera flera instruktioner samtidigt i samma pipeline-steg. Det är möjligt att initiera flera instruktioner i samma klockcykel.

3. Vad är skillnaden mellan en superscalar processor och en very long instruction word processor?

   VLIW använder kompilatorn för att detektera parallelism.

   Superscalar använder hårdvaran för att detektera parallelism.

4. Vad är skillnaden mellan en tråd och en process?

   Tråd: Delar resurser

   Process: Mer oberoende

5. Vad är skillnaden mellan en process och en processor?

   Ett program är en del av en process som exekveras på en processor.

6. Hur klassificerar Flynn arkitekturer?

   

7. Vad hindrar en processor med 4 cores att exekvera ett program 4 gånger snabbare än en processor med 1 core?

   Programmet är ej optimerat för parallelism.

8. Vad menas med Amdahls lag?

   

9. Vilka konflikter uppkommer i en superscalar processor?

   Man behöver mycket hårdvara för att detektera möjlig parallelism. Hög effektförbrukning på grund av hårdvara.

   Begränsat instruktionsfönster, det gör att det blir svårare att hitta instruktioner som har möjlighet att exekveras parallellt.

10. Vad är in-order och out-of order issue/completion?

    In-order issue with in-order completion

    Vi gör en beräkning under samma cykel då vi får ett svar för en av våra beroende operander.

    In-order issue with out-of order completion

    Ingen kontroll över när en beräkning färdigställs.

    Out-of order issue with out-of order completion

    Ingen kontroll, allt ballar ur.

11. Varför används register renaming?

    Optimering för att kunna lägga instrukioner i en annan ordning.

12. Vad är multithreading?