IS1500 Datorteknik och komponenter 9,0 hp

Tillfälleskod	Termin(er)	Period(er)	Föreläsare
51197	HT2024	3	Artur Podobas

Sammanfattning av kursens material inför tentamen.

Föreläsning 1: Inledning

Bakgrund

Moores lag: 2x transistorer varje 18-24 månader.
The power wall: Högre klockfrekvens leder till mer ström & värmeutveckling (Pentium 4).

Idag mer fokus på flerkärniga processorer och specialiserade kretsar - nya utmaningar: parallellprogrammering och hårdvaruspecialisering.

Abstraktionsnivåer i datorsystem:

Ett datorsystem
Mjukvara: Program/operativsystem
Gränssnitt mellan hård- och mjukvara: ISA (instruktionsuppsättning)
Digital hårdvarudesign: Mikroarkitektur, logik och digitala kretsar
Analog hårdvarudesign: Analoga kretsar, komponenter och fysik

Språket C

C är ett imperativt (tillstånd förändras av tilldelningar) lågnivåspråk.

T.ex.

#include <stdio.h>

/* Main function. */
int main(){
    printf("Hello world!\n");
    return 0;
}

Beståndsdelar

Literals: T.ex. 0x01, 3.1415.
Identifiers: Variabel- och funktionsnamn. T.ex. my_variable, min.
Keywords: Inbyggda, reserverade ord. T.ex. if, else, int.
Statements: Avslutas med semikolon. T.ex. int a = 1;.
Expressions: T.ex. a * 2.
Operators: T.ex. +, -, &, <<, ==.

Föreläsning 2: Assembly

Instruktionsuppsättning (ISA)

En ISA (t.ex. x86) fungerar som ett gränssnitt mellan hårdvara och mjukvara, och implementeras av mikroarkitekturen (t.ex. Intel/AMD-processorer).

CISC/RISC

Complex Instruction Set Computers (CISC): Många specialiserade instruktioner av variarande storlek och tidsåtgång (cykler).
Reduced Instruction Set Computers (RISC): Möjliggör enklare hårdvara. Normalt fix storlek och en cykel/instruktion (exkl. minnesåtkomst och cachemissar).

RISC-V: Register

#	Namn	Beskrivning	Sparas av
0	`zero`	Konstant 0.	-
1	`ra`	Returadress.	Caller
2	`sp`	Stackpekare.	Callee
3	`gp`	Global pekare.	-
4	`tp`	Trådpekare.	-
5-7	`t0`-`t2`	Temporär.	Caller
8-9	`s0`,`s1`	Sparade.	Callee
10-17	`a0`-`a7`	Argument/returvärden (`a0`-`a1`).	-
18-27	`s2`-`s11`	Sparade.	Callee
28-31	`t3`-`t6`	Temporära.	Caller

Endianness

Big-endian: Ordets MSB sparas på lägsta adress. T.ex. 1 = 00 00 00 01.
Little-endian: Ordets LSB sparas på lägsta adress. T.ex. 1 = 01 00 00 00.

OBS! RISC-V är litte-endian!

RISC-V: Assembly

Logiska instruktioner

and, or, xor, andi, ori, xori, slli ("<<"), srli (logisk, JS: ">>>"), srai (aritmetisk, JS: ">>")

"NOT" kan utföras med hjälp av xori:

xori t0, t1, 0xffffffff # -1 fungerar ockå

OBS! Immediates i RISC-V teckenförlängs till 12 bitar. Immediatevärdet i den läsbara instruktionen tolkas dock som ett signerat 32-bitarstal, vilket medför att 0xffffffff tolkas som -1, som kan representeras i 12 bitar som 0xFFF, och alltså ryms i instruktionen. Att skriva 0xFFF direkt fungerar dock inte, eftersom detta tolkas som 4095, och därmed inte kan representeras av ett signerat 12-bitarstal.

Tilldela 32-bitarstal

För att tilldela ett 32-bitarsvärde till ett register använder vi två instruktioner:

lui s0, 0x6af02     # De 20 mest signifikanta bitarna (övriga := 0): s0 := 0x6af02000
ori s0, s0, 0x2e7   # De 12 resterande (minst signifikanta) bitarna: s0 := 0x6af022e7

RARS

Exempel:

.data               # Spara i data-delen av minnet
.align 2            # Assemblatorn kommer att se till att följande data är ord-justerad
                    # OBS! 2 = log2(<antal bytes>)
msg:    .space  8   # Reservera 8 bytes och ge denna etiketten "msg"

.text                           # Spara i text-delen av minnet (dvs. maskinkod följer)
main:   la      t1, msg         # Hämta adress för en etikett ("msg")
        addi    t2, zero, 0x27  # t2 := 0x27
        sb      t2, 0(t1)       # Spara en byte (t2) på minnesadress t1 + 0
        addi    t2, zero, 0x18  # t2 := 0x18
        sb      t2, 1(t1)       # Spara en byte (t2) på minnesadress t1 + 1
        li      t2, 0x4b544800  # Load immediate (pseudoinstruktion)
        sw      t2, 4(t1)       # Spara ett ord (i detta fall: 32 bitar) (t2) på minnesadress t1 + 4

        # Resultat (i minnet): | 27 18 00 00 | 00 48 54 4b |

stop:   j       stop            # Evig loop i slutet

Föreläsning 3: Maskinkod

Bytes, nibbles och ord

En byte = 8 bitar
En nibble = 1/2 ord
Ett ord = beror på processor (normalt 32/64 bitar)

Two's complement

Första biten anger tecken (+/-).
-1 representeras som 0b111...1 (beroende på storlek).
Binär addition och subtraktion fungerar som vanligt.
För ett positivt tal X: negativt(X) = ~X + 1

Teckenförlängning:

För att teckenförlänga ett binärt tal, kopiera teckenbiten (msb) åt vänster tills talet är av önskat antal bitar.

Exempel: 6 = 1010 (4 bitar) = 1111 1010 (8 bitar)

RISC-V: Typer av instruktioner

Register-instruktioner (R)

Har tre registeroperander: två källor och ett mål.

31...25	24...20	19...15	14...12	11...7	6...0
funct7	rs2	rs1	funct3	rd	opcode

funct3/7 avgör vilket specifik operation som utförs.
rs2/rs1 är källregistren.
rd är målregistret.
opcode anger vilket format instruktionen är i.

Immediate-instruktioner (I)

Har två registeroperatander och en immediate.

31...20	19...15	14...12	11...7	6...0
imm	rs1	funct3	rd	opcode

imm är ett 12-bitars immediatevärde.

T.ex. lw t0, 8(s1) kodas som 000000001000 01001 010 00101 0000011

Shift immediate-instruktioner

Shift immediate-instruktionerna (srli, slli & srai) ser lite annorlunda ut:

31...25	24...20	19...15	14...12	11...7	6...0
imm_11:5	shamt	rs1	funct3	rd	opcode

imm_11:5 avgör shift-beteende (aritmetiskt eller logiskt) - funct3 är identiskt för båda typerna av right-shift.
shamt anger antalet shift-steg.

Store-instruktioner (S)

Instruktioner som arbetar med två register och en immediateoperand, t.ex. sw (store word).

31...25	24...20	19...15	14...12	11...7	6...0
imm_11:5	rs2	rs1	funct3	imm_4:0	opcode

imm är ett immediatevärde (för sw: förskjutning, i bytes).

Branch-instruktioner (B)

Instruktioner med två register och en immediateoperand.

31	30...25	24...20	19...15	14...12	11...8	7	6...0
imm₁₂	imm_10:5	rs2	rs1	funct3	imm_4:1	imm₁₁	opcode

imm anger målets position relativt pc (notera att imm₀ saknas - denna antas =0).
funct3 avgör typ av branch (t.ex. beq, bne).

Upper immediate-instruktioner (U)

Instruktioner med ett register och ett stort (20-bitars) immediatevärde. I vårt fall: lui.

31...12	11...7	6...0
imm	rd	opcode

Jump-instruktioner (J)

Instruktioner med ett register och ett stort (20-bitars) immediatevärde.

31	30...21	20	19...12	11...7	6...0
imm₂₀	imm_10:1	imm₁₁	imm_19:12	rd	opcode

imm anger målets position relativt programräknaren (notera att imm₀ saknas - denna antas =0).
rd anger vart returadressen (pc före hoppet + 4) skall sparas.

Obs! jalr (jump and link-register) är en I-instruktion, och använder inte pc-relativ adressering. Istället hoppar vi till imm (12 bitar, teckenförlängt till 32 bitar) + rs1.

Stack-minne

En stack (hög) är en minnespartition som används för att spara variabler och fler argument. Läsning/skrivning sker på adressen i sp enligt principen LIFO (last in, first out).

Läs/skriv-makron kan definieras som följer (i RARS):

.macro PUSH(%reg)
    addi    sp, sp, -4
    sw      %reg, 0(sp)
.end_macro

.macro POP(%reg)
    lw      %reg, 0(sp)
    addi    sp, sp, 4
.end_macro

Föreläsning 4: C

Pointer-aritmetik

int arr[] = {0, 1, 2, 3, 4};
printf("arr[1] : %d\n", arr[1]);
printf("arr[1] : %d\n", *(arr + 1));

Föreläsning 5: I/O-system (1/2)

Memory mapped I/O - särskilda bitar av minnet används för I/O-enheter.

Bussar

En buss (flera parallella ledningar) är ett delat nätverk varigenom processorn kan kommunicera med minne och I/O-enheter.

Tre linjer:

Adress: Adressen där data läses/skrivs.
Data: Data som lästs, eller som ska skrivas.
Kontroll: T.ex. handskakningssignaler.

Varje I/O-enhet har ett eget adressomfång. Dessa är alltid unika och överlappar ej. När en enhet inte kommunicerar är dess buss-utgångar avstängda med hög impedans (uppnås med en tri-state gate).

Synkron buss

Dataöverföring på en synkron buss synkroniseras med en bussklocka. En läsoperation kan ske på följande vis:

En kontrollsignal indikerar att vi vill läsa. Processorn lägger adressen på bussen.
Alla enheter läser adressen; endast en enhet svarar genom att lägga fram data.

Asynkron buss

Asynkrona bussar saknar klocka. Istället används ett handskakningsprotokoll mellan deltagande parter. En läsoperation kan ske på följande vis:

Ledaren lägger adressen på bussen. Andra enheter avkodar informationen.
Ledaren sätter "ledare redo".
Följaren lägger data på bussen och signalerar "följare redo" (dvs. data redo).
Ledaren läser data och sätter "ledare redo" till LOW.
När följaren ser att "ledare redo" sjunker kan den sluta skicka data. "Följare redo" sätts till LOW.

Direkt minnesåtkomst (DMA)

För att undvika att processorn hålls upptagen av dataöverföring mellan I/O-enheter, särskilt då ordvis överföring av stora mängder data är ineffektivt, används DMA.

DMA tillåter överföringar av data mellan olika delar av minnet, utan att ständigt inblanda processorn.
Processorn skickar en DMA-förfrågan (vilken adress och mängd data som skall överföras).
En DMA-kontroller genomför överföringen - processorn kan göra annat under tiden.
DMA-kontrollern kan utfärda en interrupt-förfrågan (IRQ) när överföringen är färdig.

Föreläsning 6: I/O-system (2/2)

Parallell/seriell kommunikation

Parallell: Flera linor.
Seriell: Synkront (t.ex. SPI, I2C) eller asynkront (t.ex. UART).

Undantag och avbrott

Ett undantag (exception) kan orsakas av ett fel (t.ex. ogiltig instruktion), avbrott (interrupt - en speciell sorts undantag - t.ex. ett knapptryck) eller mjukvaruavbrott (t.ex. systemanrop).

Undantag hanteras av undantagshanteraren (på adress 0x00000000):

Processorn sparar nuvarande pc i mepc och undantagsorsaken i mcause.
Processorn inaktiverar avbrott i mstatus.
Processorn hoppar till adressen mtvec (undantagshanteraren, = 0x00000000).
Undantagshanteraren sparar register på stacken, undersöker orsaken och anropar avbrottshanteraren, och återställer sparade register.
Undantagshanteraren hoppar till mepc (eller mepc + 4 vid mjukvaruavbrott).

Externa avbrott hanteras normalt av en PLIC. I denna kurs behandlas dock alla avbrott som lokala, och hanteras därför av CLINT.

I ARM används olika undantagshanterare beroende på orsak - detta kallas för en undantagsvektor.

Aktivera avbrott

Avbrott måste aktiveras både på I/O-enheten och globalt (bit #3 i mstatus). Varje avbrottstyp som skall hanteras måste också accepteras av processorn (bit #<exception cause no.> i mie).

Föreläsning 7: Kombinationslogik

Logiska grindar

Negation: NOT
Konjunktion: AND ("alla") och NAND ("inte alla").
Disjunktion: OR ("minst en"), XOR ("udda antal") och NOR ("ingen").
Ekvivalens: XNOR ("lika")
BUF: Logiskt ekvivalent med en ledning. Av betydelse endast ur ett analogiskt perspektiv.

Boolesk algebra

AND: \(AB\) eller \(A\cdot B\)
OR: \(A+B\)
NOT: \(\overline A\) eller \(A'\)

De Morgans lagar:

\[\overline{AB}=\overline{A}+\overline{B}\quad\text{och}\quad\overline{A+B}=\overline{A}\cdot\overline{B}\]

Sum-of-products-form: t.ex. \(Y=\bar A\bar R\)

Product-of-sums-form: t.ex. \(Y=(A+\bar R)(\bar A+R)(\bar A+\bar R)\)

Kombinationskretsar

Kombinationskretsar påverkas enbart av aktuell inmatning.

Problem:

Instabila kretsar: T.ex. ringoscillatorer (Obs: sekventiella, inte kombinatoriska!).

Otillåtna värden ("X"): T.ex. en ledning mottar 0 och 1 samtidigt (contention).

Tristate: Har hög impedans ("Z") om "utmatning aktiv"-signalen inte är aktiv. Används i bussar för att undvika contention.

Multiplexrar och avkodare

En multiplexer tar 2+ bitar som indata och ger 1 bit utdata. Kontrollsignalen S avgör vilken som släpps igenom.

En avkodare har N ingångar och 2^N utgångar. Varje möjlig kombination av indata motsvaras av en utgång.

Aritmetik

Adderare

En halvadderare har en carry out-signal.
En heladderare tar dessutom in en carry in-signal.

Carry propagate adder (CPA)

En carry propagate adder beräknar summan av två N-bitarstal. Tre vanliga implementationer:

Ripple-carry: Enkel men långsam. Består av flera seriekopplade heladderare.
Carry-lookahead: Snabbare (delar upp beräkningen i block).
- Använder generera (G) och fortplanta (P)-signaler för att beskriva hur \(C_\text{out}\) bestäms för ett block.
- Kolumn \(i\) i adderaren genererar en carryout om \(C_i=A_iB_i+(A_i+B_i)C_{i-1}=G_i+P_iC_{i-1}\)
- Varje enskilt block är en ripple-carry-adderare, men med extra logik för att snabbt avgöra carryout-biten. Denna logik kan utföras parallellt, och additionen kan därför utföras snabbare än i en ripple-carry.
Prefix-adderare: Snabbast. Används i moderna datorer.

Subtraktion:
Subtraktion utförs enkelt med en CPA genom att invertera signal B och låta C_in = 1.

Timing

Fördröjningar mäts alltid mellan in- och utdatasignalernas respektive 50%-punkter.

Fortplantningstid (\(t_\text{pd}\)): Den maximala tiden från att någon input ändras, tills att ändringen nått alla outputs (oavsett om de behöver ändras eller ej).

Kontamineringstid (\(t_\text{cd}\)): Den minsta tiden från att någon input ändras, tills att någon output ändras.

Glitchar

En glitch inträffar när en indataförändring orsakar flera förändringar i utdata, t.ex. att utdata förändras från \(1\rightarrow0\rightarrow1\).

Föreläsning 8: Sekventiell logik

Sekventiella kretsar påverkas av både aktuella och tidigare indata.

En mikroprocessor består av klockade state elements (uppdateras vid rising edge) och kombinatorisk logik, och är därför i sig en synkron sekventiell krets.

Bistabilitet:
Bistabila kretsar har två stabila tillstånd, och kan alltså lagra 1 bit.

SR-vippa (SR latch)

Två ingångar: SET (\(S\)) och RESET (\(R\))

Om \(S=0\), \(R=0\) minns kretsen det tidigare värdet.
Om \(S=1\) eller \(R=1\) ändras tillståndet till \(Q=1\) resp. \(Q=0\).

Problem:

Om \(S=1\) och \(R=1\) blir både \(Q\) och \(\overline Q\) noll.
Blandar vad som uppdateras och när - en utmaning i större kretsar.

D latch

Två ingångar: \(D\) och \(\text{CLK}\)

Tillståndet ändras för att matcha \(D\) när vippan är transparent (\(\text{CLK}=1\)):

\(\text{CLK}\)	\(D\)	\(Q\)	\(\overline Q\)
0	?	\(Q_\text{pre}\)	\({\overline Q}_\text{pre}\)
1	0	0	1
1	1	1	0

Flip-flops

Flip-flops är edge-triggered (till skillnad från SR/D-latches, som är level-triggered).

D-vippa (D flip-flop)

Består av två sammankopplade D-latches ("ledare" och "följare").

\(\overline{\text{CLK}}\): \(D_\text{in}\) släpps igenom av ledaren.
\(\text{CLK}\): Ledaren låses och följaren släpper igenom den nu låsta signalen.

Beteende: När \(\text{CLK}\) går från LOW till HIGH kopieras \(D\) till \(Q\).

Resettable/enabled flip-flops

En nollställbar flip-flop sätts till 0 när \(\text{RESET}\)-signalen är aktiv.

En synkront nollställbar flip-flop kan endast nollställas i samband med en stigande klocksignal.
En asynkront nollställbar flip-flop kan nollställas obereonde av klockan.

En aktiverad flip-flop tillåts endast skifta läge om (utöver \(\text{CLK}\)) även \(\text{EN}\)-signalen är aktiv.

Register

Ett \(N\)-bitars register består av \(N\) stycken flip-flops med gemensam klocka. Register kan, likt enskilda flip-flops, ha \(\text{EN}\)- och \(\text{RESET}\)-signaler.

Output enable (OE)- register:
Består av ett register med en tristate-buffer på utgången. Om \(\text{OE}=0\) är \(Q=\text{Z}\) (flytande), annars är \(Q=Q_\text{register}\).

Registerfil

Tillåter adressering av data genom att kombinera flera register:

En avkodare väljer (beroende på adressen \(\text{A3}\)) vilket register som, om även \(\text{WE3}\), data på \(\text{WD3}\) skall skrivas till.
En multiplexer väljer (beroende på adresserna \(\text{RD1},\text{RD2}\)) från vilka två register som data skall läsas till \(\text{RD1},\text{RD2}\).
De ingående registren har alla en gemensam klocka.

Synkrona sekventiella kretsar

Kombinationslogik kombineras med minst ett register.
Kretsens tillstånd ändras enligt en klocka, som är gemensam för alla ingående komponenter.
Varje cyklisk väg innehåller minst ett register.
En synkron sekventiell krets kan definieras som en FSM (finit tillståndsmaskin):
- Mealy-maskin: Utdata kan vara direkt beroende av indata (Mealy-maskin).
- Moore-maskin: Utdata beror endast på tillståndet (dvs. ej direkt på indata).

Hur snabbt kan vi köra en krets?

Klockperioden måste vara längre än värsta-fallsfördröjningen i kretsen:

\[\text{delay}=t_\text{prop}+t_\text{combinational}+t_\text{setup}+t_\text{skew}\]

\(t_\text{prop}\) är tiden det tar för signalen att färdas genom registret
\(t_\text{combinational}\) är den längsta tidsåtgången för kombinationslogiken
\(t_\text{setup}\) är nödvändig tid före klocksignalens stigning.
\(t_\text{skew}\) är clock skew-kompensation (klocksignaler når olika tillståndselement olika snabbt)

Ett race kan uppstå om värdena hos olika tillståndselement beror på den relativa hastigheten hos kretsens logiska element.

Föreläsning 9: ALU och encykelprocessor

ALU (aritmetisk logisk enhet)

Utför aritmetiska/logiska operationer på två N-bitarsvärden \(A\) och \(B\). Vilken operation som utförs beror på ingångssignalen \(F\).

En ALU kan också ge statusflaggor såsom overflow, nollflagga, etc.

Data path (i encykelprocessorer)

Arkitekturellt tillstånd:
- Programräknare (ett 32-bitarsregister som adderas med 4 varje klockcykel)
- 32 inbyggda register
Instruktions- och dataminne
Register, ALU och multiplexrar

Läsning från registerfilen, instruktionsminnet och dataminnet sker kombinationellt - oberoende av klockcykel. När adressen ändras, gör även data på läsporten det direkt efter kretsens fortplantningstid. Skrivning av register/dataminne sker dock vid stigande klocksignal.

Kontrollenhet (i encykelprocessor)

Läser nuvarande instruktion från datapath, och talar, utgåendes från denna information, om för datapath hur en instruktion utförs, det vill säga väljer t.ex. multiplexer-port och om skrivning skall aktiveras i minnet (sw-instruktioner).
En kontrollenhet kan t.ex. delas upp i en huvuddel och en ALU-avkodare.

Styr följande kontrollsignaler:

ImmSrc: hur immediate-värdet skall tolkas (dess bitar är utspridda på olika sätt i olika instruktioner)
ALUSrc: varifrån värden till ALU:n skall hämtas ifrån (2 register eller 1 register + immediate)
ALUControl: vilket ALU-operation som skall utföras
RegWrite: huruvida data skall skrivas till registerfilen
MemWrite: huruvida data skall skrivas till minnet
ResultSrc: varifrån resultatet, som ev. sedansparas i registret, ska hämtas ifrån (minnets läsport eller direkt från ALU:en)
Branch: Om en branch skall genomföras

Prestanda

Det största problemet med en encykelsdesign är den långa kritiska vägen, då vissa instruktioner tar lång tid. I och med synkron logik kommer klockhastigheten att begränsas av detta.

Föreläsning 10: Pipeline-processorer

Begrepp

Processing system: Ett system som behandlar data.
Token: En datapunkt som hanteras av systemet och leder till utdata.
Latens: Tidsåtgång för att hantera en token.
Throughput: Antalet tokens som kan behandlas per tidsenhet.

Parallellism och pipelining

Exempel: En fabrik med två maskiner, som sköter två olika processer.

Sekventiell hantering: En token i taget, sekventiellt. Någon maskin "vilar" alltid.
Parallell hantering (spatial parallellism): Lägg till ytterligare par maskiner för att öka produktionstakten. 50% av maskinerna nyttjas i taget.
Pipelining (temporal parallellism): Endast två maskiner - men processerna schemaläggs så att den långsammaste processen pågår konstant, och går direkt från en token till nästa. Den andra maskinen påbörjar sitt arbete när den första är färdig.
- Särskilda "pipeline-register" placeras mellan olika "block" av kombinationslogik. Registren förhindrar att tokens från olika pipeline-steg påverkar varandra.
- Minimerar väntetid.
- Throughput avgörs av den maskinen som tar längst tid.
- Instruktioner/cykel förbättras inte (minskar t.o.m. lite) - men den kritiska vägen (och därmed cykelperioden) blir kortare.
- Datapath kan delas in i steg: hämta (F), avkoda (D), beräkna (E), läsa/skriva minne (M) och spara i register (W).
  - Obs! För att beräkningsresultatetet skall sparas i det register som angavs i den aktuella instruktionen (och inte i något angivet av efterföljande instruktioner) måste registernumret (adressen) vidarebefordras till detta steg.
  - Ytterligare problem: Programräknaren (PC) förändras oförutsägbart av branch-instruktioner.

Data- och kontrollfaror

Om det finns inbördes beroenden mellan instruktioner i en sekvens uppstår en datafara (om pipeline då fylls kan resultat bli oväntat).

DATA: Read after write (RAW): En instruktion försöker läsa ett register som ännu inte skrivits till.
- Möjlig lösning: Forwarning. Beräkningsresultatet vidarebefordras direkt till beräkningssteget (E) för nästa instruktion.
  - Det beräknade värdet vidarebefordras av en hazard unit.
  - Fungerar ej om nödvändig data inte är tillgänglig ännu. Data hämtad med lw t.ex. inte tillgänglig förrän steg 4 (M).
- Alternativt: Stalling tills forwarding är möjligt. Leder till <1 instruktioner/cykel.
  - Exekveringen pausas tills resultatet från den tidigare instruktionen är tillgängligt.
KONTROLL: Anta branch ej tagen: Om en branch tas upptäcks detta först i minnes-steget - pipeline måste då spolas.
- Möjlig lösning: Flytta branch-adressberäkning till avkodningssteget och hantera beq redan där.
  - Kan leda till nya datafaror (om operander inte är tillgängliga i avkodningssteget) - löses med forwarding eller stalling.

Antalet pipeline-steg

Många steg ger en kortare kritisk väg (möjliggör högre klockfrekvens).
Problem: Högre strömförbrukning, mer hårdvara (register) och dyrare branch mispredictions.

Hur minimera branch mispredictions?

Statiska branch predictors förutspår vid kompilering om en branch kommer att tas.
Dynamiska branch predictors använder en branch target buffer (information om hur tidigare branch-instruktioner fallit ut).
- 1-bit: Antar att utfallet är lika nästa gång. För loopar ger detta fel i första och sista iterationen.
- 2-bit: 4 tillstånd (starkt tagen, tagen, ej tagen, starkt ej tagen). Fel endast i slutet av en loop.

Föreläsning 11: Minneshierarki

Instruktions- och dataminne

Vi antog tidigare att varje minnesåtkomst tar 1 cykel - detta är sant endast för små minnen eller långsamma processorer. Normalt kommer tidsåtgången motsvara mer än 1 klockcykel.

RAM (Random Access Memory): Volatilt (strömavbrott = dataförlust) och konstant läs/skrivtid.
ROM (Read-Only Memory): Icke-volatilt. Obs: Idag ofta skrivbart.

Minnesteknologi:

SRAM (statiskt RAM): Enkel integrerad krets. Snabbt men dyrt.
DRAM (dynamiskt RAM): Kondensatorer. Laddning tappas snabbt & måste därför ständigt "uppdateras". En transistor per bit - billigare, men långsammare, än SRAM.
- SDRAM (synkront DRAM): Data överförs i bursts (följer en klocka).
  - DDR (double data rate) - Dataöverföring både vid stigande och fallande klocksignal.
Flashminne (EEPROM, SSD) & magnetiska diskar (HDD).

Vi behöver alltså hitta sätt att optimera prestanda utan stora kostnader.

Temporal/spatial närhet

Temporal närhet: Minne som tidigare använts tenderar att användas igen.
Spatial närhet: Minne på närliggande adresser tenderar att användas.

\[\text{AMAT}=t_\text{cache}+\text{MR}_\text{cache}\left(t_\text{MM}+\text{MR}_\text{MM}\cdot t_\text{VM}\right)\]

Caching

Två sorters cacheminnen: instruktions- resp. datacache (kombineras ibland).

Cacheträff: Efterfrågad data finns i cache.
Cachemiss: Finns ej i cache - data hämtas från huvudminnet.

För att nå en hög träffrekvens utnyttjar vi temporal och spatial närhet.

Kapacitet (C): Totala mängd data som ryms i cachen.
Antal set (S): Hur många set cachen har. Varje sådant består av ett eller flera block.
Blockstorlek (b): Kapacitet hos ett datablock.
Antal block (B): Totalt antal block. Minst lika med antalet set (\(B=N\cdot S\)).
- När data hämtas från minnet, hämtas ett helt block (cacherad) åt gången.
Associativitetsgrad (N): \(N=\frac BS\). Antal block per set.

Varje adress är bunden till ett set, och data kan sparas i vilket helst av dess \(N\) block.

Direct-mapped cache

I en direct-mapped cache är \(S=B\), dvs. ett block per set (\(N=1\)).

En minnesadress kan då delas in i olika fält, t.ex.:

Tagg	Set (index)	Byte offset
11...111	101	00

Tagg: Början av adressen. Unikt för varje adress inom ett set - lagras i början av varje block, omedelbart efter valid-biten.
Index: Vilket set (rad) i cacheminnet adressen tillhör.
Byte offset: Anger byte# inuti blocket.

Om ingen konflikt uppstår i mappingen, och cachen är tom i början av ett program, inträffar cachemissar endast de gånger nytt minne behöver hämtas.

Om data behöver hämtas från två olika adresser som delar set inträffar en kollision. Om två sådana adresser läses om vartannat kan missfrekvensen nå 100%.

N-vägs set-associativ cache

Reducerar antalet kollisioner genom att låta varje set bestå av \(N\) st block.

Nackdel: Långsammare och kräver mer hårdvara. Adressens tagg behöver jämföras med alla taggar (\(N\) stycken) som sparats i dess motsvarande set.

Lägst missfrekvens fås med ett fully associative cache (\(N=B,S=1\)).

Varje block ser ut som följer:

Giltig?	Tagg	Data
<1 bit>	<28 bitar>	<32 bitar>

Ersättningspolicy

Direct mapped cache: Om ett set är upptaget måste data bytas ut.
N-vägs set-associativ cache: (förutsatt \(N>1\))
- Least recently used (LRU): Enkelt att implementera för \(N=2\) genom att lägga till en "används"-bit.
- Pseudo-LRU (för \(N>2\)): Ett set delas upp i två grupper - ett slumpmässigt block i den minst nyligen använda gruppen ersätts.
- FIFO
- Slumpmässig ersättning

Flernivå-cache

Processorer kan ha flera cacheminnen: T.ex. L1 (snabbare), L2 och L3 (större).

Skriv-policy

Write-through: Data skrivs till huvudminnet samtidigt.
Write-back: En "dirty"-bit sätts vid skrivning. Data skrivs tillbaka när cacheblocket behövs för ny data.

Virtuellt minne

Långsamt (använder hårddisken), men stort och tillåter bättre minnessäkerhet (varje process har ett eget minnesutrymme).

Det virtuella minnet är indelat i virtuella pages (vanligtvis 4 KiB stora). Dessa kan finnas i det fysiska minnet (DRAM) eller på hårddisken (i swap-utrymmet). När ett program använder virtuellt minne, översätts den virtuella adressen till en fysisk adress. Om processorn försöker komma åt virtuellt minne som inte finns i det fysiska minnet inträffar en page fault, och operativsystemet hämtar data från hårddisken.

Det fysiska minnet fungerar som en fullständigt associativ cache (\(N=B\)) för det virtuella minnet.

Översättningen görs av en memory management unit (MMU):
Till hjälp finns ett page-tabell, som översätter VPN (virtuellt page number) till PPN (fysiskt PN). Page offset behöver inte översättas.
- Varje rad i page-tabellen består av en valid-bit, ett PPN och ett VPN.
- Page-tabellen lagras i det fysiska (RAM-) minnet.
- Operativsystemet ansvarar för att uppdatera page-tabellen, samt för att flytta data mellan minne och disk.
I hårdvara finns även en translation lookaside buffer (TLB), som cachar nyligen använda pages.

Minnessäkerhet: Varje process tilldelas en egen virtuell adressrymd.

Som skriv-policy används write-back. Att ersätta en fysisk page i minnet kallas för paging. Virtuellt minne använder en LRU-liknance policy där använd-bitarna regelbundet nollställs.

Föreläsning 12: Parallellism, samtidighet, uppsnabbning och ILP

Multiprocessor: Ett datorsystem med två eller fler processorer.
- Flerkärnig processor: En multiprocessor där alla processorer (kärnor) är integrerade i samma krets.
Kluster: Flera datorer sammanlänkade via ett LAN - kan betraktas som en multiprocessor.

Parallellism eller samtidighet?

Parallellism: Att utföra flera saker parallellt (hårdvaruperspektiv).
Samtidighet: Att hantera/"jonglera" flera saker samtidigt (mjukvaruperspektiv).

		Mjukvara
		Sekventiellt	Samtidigt
Hårdvara	Seriell	Matrismultiplikation, enkärnig processor (en process)	Linux, enkärnig processor (många processer)
Hårdvara	Parallell	Matrismultiplikation, flerkärnig processor (en process)	Linux, flerkärnig processor (många processer)

Speedup vid parallellisering

\[\text{Speedup}=\frac{T_\text{före}}{T_\text{efter}}\]

Superlinjär speedup: Felmätning eller en cache-effekt.
Idealt (linjärt): \(\text{Speedup}\propto\text{antal processorer}\)

Fara: Relativ speedup mäter bara samma program. Verklig speedup jämför istället med det bästa kända sekventiella programmet.

Amdahls lag

Att förbättra prestandan hos ett subsystem är mödan värd endast om subsystemet påverkar en stor del av den totala prestandan.

Exekveringstiden \(T_\text{före}\) kan delas upp i två delar, beroende på vilka delar som förbättras av parallellisering:

\[T_\text{före}=T_\text{förbättringsbar}+T_\text{konstant}\]

Speedup kan då beräknas enligt Amdahls lag:

\[\text{Speedup}=\frac{T_\text{före}}{T_\text{efter}}=\frac{T_\text{före}}{\frac{T_\text{förbättringsbar}}N+T_\text{konstant}}\]

där \(N\) är förbättringsfaktorn.

Om den parallelliseringsbara andelen \(p\) är känd:

\[\text{Speedup}=\frac1{\frac pN+(1-p)}\]

Stark skalning: Mät speedup utan att förändra problemstorlek.
Svag skalning: Mät speedup när problemstorleken växer proportionellt med antalet processorer (Gustafsons lag).

Parallellism

Datanivå-parallellism (DLP): Flera dataobjekt kan behandlas simultant. T.ex. flera bönder klipper flera får.
Uppgiftsnivå-parallellism (TLP): Flera olika uppgifter kan utföras samtidigt och parallellt. T.ex. flera bönder arbetar samtidigt, med olika uppgifter.

SISD, SIMD, MIMD

		Dataströmmar
		En	Flera
Instruktionsströmmar	En	SISD (t.ex. i386)	SIMD (t.ex. SSE-instruktioner)
Instruktionsströmmar	Flera	MISD (t.ex. redundans i flygdator)	MIMD (t.ex. flerkäriga processorer)

Grafikprocessorer är både SIMD och MIMD.

Instruktionsnivå-parallellism (ILP)

Kan förbättra prestanda utan att involvera programmeraren.

Två vägar: pipelines och multiple issue.

Multiple issue

Utfärda flera instruktioner i varje cykel. Utmaning: beroenden och data-/kontrollfaror.

Statiskt: Kompilatorn planerar instruktionsordningen. T.ex. VLIW (Very Long Instruction Word)
- VLIW (Very Long Instruction Word): Använder issue-paket (~flera sammanslagna instruktioner).
  - Kräver flera registerportar, läsning av flera instruktioner i taget och extra ALU:er.
  - För att undvika faror infogar ibland kompilatorn en no-op (no operation).
Dynamiskt: S.k. superskalära processorer utfärdar instruktioner dynamiskt. En superskalär processor består av flera uppsättningar av datapath-hårdvara.
1. En batch instruktioner hämtas och avkodas i ordning.
2. Reserveringsstationer (RS) buffrar operander till de funktionella enheterna. Databeroenden hanteras dynamiskt.
3. Funktionella enheter (FU) (t.ex. heltalsenhet, load/store-enhet) exekverar instruktionerna.
4. Resultat skickas tillbaka till en RS (vid behov), och till commit-enheten.
5. Commitenheten (CU) genomför ändringar i registret, med hänsyn till den önskade ordningen (s.k. in-order commit).

Out-of-order-exekvering

Vissa superskalära processorar kan ändra exekveringsordningen (s.k. out-of-order-processorer).

WAR-beroenden:
Om ett WAR (write after read)-beroende finns mellan två instruktioner, uppstår en fara om vi utan vidare ändrar ordningen (skrivning måste ske efter läsning!).

Lösning: Register renaming
Processorn skriver till ett renaming register istället - faran undviks. Processorn håller koll på det omdöpta registret.

VLIW-processorer är ofta mer energieffektiva än superskalära out-of-order-processorer (mindre hårdvara + kompilatorn gör jobbet).

Föreläsning 13: SIMD, MIMD och parallellprogrammering

Subword-parallellism & multimediatillägg

Subword-parallellism: (SIMD) En instruktion opererar parallellt på flera ord - t.ex. vektorinstruktioner i SSE.

Flertrådning

En process består av en eller flera trådar som körs samtidigt/parallellt.

Flertrådade processorer

I en flertrådad processor delar flera hårdvarutrådar på de funktionella enheterna. Processorn innehåller hårdvara för flera parallella funktionella tillstånd, vilket tillåter en annan tråd att utfärda instruktioner när en första hamnar i en stall.

Flertrådning förbättrar inte prestandan hos de enskilda trådarna, då ILP inte förbättras. Däremot förbättras processorns totala throughput, eftersom processortid kan nyttjas mer effektivt genom flera trådar.

Syftet med flertrådning är att göra latens mindre märkbar samt undvika stalls till följd av cache-missar.

Grovkornig flertrådning: Byter tråd endast vid kostsamma stalls, t.ex. L3-cachemissar.
Finkornig flertrådning: Byter tråd varje cykel -- nyttjar resurserna bättre.

Simultan flertrådning (SMT)

Kombinerar flertrådning med en multiple-issue, dynamiskt schemalagd pipeline. Kan täcka de luckor som multiple-issue inte kan fylla, genom att lägga till instruktioner från andra hårdvarutrådar.

Exempel: Intels Hyper-Threading.

MIMD, flerkärnighet och kluster

En shared memory multiprocessor (SMP) har en gemensam adressrymd för samtliga processorer. Processorerna kommunicerar via delat minne. En SMP är nästan alltid detsamma som en flerkärning processor.

Uniform memory access (UMA)-multiprocessor: Samma latens vid minnesåtkomst från samtliga processorer.
Nonuniform memory access (NUMA)-multiprocessor: Minne kan partitioneras mellan processorer. Kan ge olika latens.

Cache coherence

Cache coherencency problem: De enskilda kärnornas lokala cacheminnen kan innehålla olika värden för samma minnesadress.

Cache coherence kan säkerställas med ett write invalidate-protokoll, t.ex. snooping-protokollet:

När en kärna skriver till en minnesadress görs motsvarande cache-data på övriga kärnor ogiltig.

Om två kärnor har motsvarande cache lines, och de samtidigt modifierar olika delar av den, kommer cache coherence-protokollet att ogiltig-markera båda cache-linjerna, trots att kärnorna egentligen inte är intresserade av samma data.

Programmering med trådar och delade variabler

Semafor

En semafor är en icke-negativ global heltalsvariabel som enbart kan förändras genom två operationer:

\(P(s)\) dekrementerar \(s\) så snart som det är möjligt och returnerar därefter.
\(V(s)\) inkrementerar \(s\).

Mutex

En mutex är en sorts binär semafor med det initala värdet 1, som används för att säkerställa att en delad resurs används av högst en tråd åt gången. \(P\) = "lås", \(V\) = "lås upp".

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

volatile int counter = 0;
sem_t *mutex;

void *count(void *data){
    int i;
    int max = *((int*) data);
    for(i = 0; i < max; i++){
        sem_wait(mutex); // P
        counter++;
        sem_post(mutex); // V
    }
    pthread_exit(NULL);
}

int main(){
    pthread_t tid1, tid2;
    int max1 = 400000;
    int max2 = 600000;

    mutex = sem_open("/semaphore", O_CREAT, 0777, 1); // skapa en semafor

    // Semaforen tas bort när alla trådar som öppnat den anropar `sem_close`.
    sem_unlink("/sempahore");

    // Starta två trådar
    phtread_create(&tid1, NULL, count, &max1);
    pthread_create(&tid2, NULL, count, &max2);

    // Vänta på att båda avslutas
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    printf("counter = %d\n", counter);

    // Stäng semaforen
    sem_close(mutex);

    // Semaforen tas nu bort eftersom ingen tråd längre håller den öppen

    pthread_exit(NULL); // Låt andra trådar fortsätta?
}