IN2060

Cheat Sheet

Formler, begreper og oppsummering

Digitalteknikk og datamaskinarkitektur

eksamenssett.no

Nøkkelformler per tema

Tallsystemer og Boolesk algebra

•Toverkomplement negativt tall: inverter alle biter, legg til 1
•Område n-bits toverkomplement: $-2^{n-1}$ til $2^{n-1}-1$
•De Morgan: $\overline{A \cdot B} = \overline{A} + \overline{B}$ , $\overline{A + B} = \overline{A} \cdot \overline{B}$

Vanlige feil å unngå

Tallsystemer og Boolesk algebra

•Glemme å legge til 1 etter bitinversjon ved toverkomplement – enerkomplement og toverkomplement er ikke det samme.
•Forveksle overflowkrav: overflow oppstår bare når to like-fortegnstall gir et resultat med motsatt fortegn.
•Bruke feil grupperingsstørrelse: heksadesimal krever 4-bits grupper, oktal 3-bits grupper.
•Anvende De Morgans lov feil: husk at operatoren innenfor snues (AND↔OR) og alle termer negeres.

Kombinatorisk logikk

•Bruke feil Gray code-rekkefølge i K-kartet (00, 01, 10, 11 er FEIL – riktig er 00, 01, 11, 10).
•Glemme at K-kart-kanter wrapper – felter i venstre/høyre og øvre/nedre kant er naboer.
•Lage grupper som ikke er potenser av 2 (f.eks. gruppe av 3 er ugyldig).
•Overse don't-care-felter som ville gjort en gruppe større og dermed enklere.

Sekvensiell logikk og flip-flops

•Forveksle D-latch (nivå-trigget, transparent) og D-flip-flop (kant-trigget). Eksamen tester denne distinksjonen.
•Glemme at SR-latch-tilstanden $S=R=1$ er forbudt – ikke bare udefinert, men kan føre til uforutsigbar oscillasjon.

Eksamenstips

Tallsystemer og Boolesk algebra

•De tre første oppgavene er faste: (1) desimal → 8-bits binær, (2) oktal/heks/negativ desimal → 8-bits binær (ofte 2'er-komplement), (3) en «bitoppløsning»-oppgave. Sistnevnte spør enten hvor mange ulike verdier $n$ bit gir ( $2^n$ ), største positive 2'er-komplement-tall ( $2^{n-1}-1$ ), eller minimum antall bit for å uttrykke $k$ verdier ( $\lceil\log_2 k\rceil$ ).

•Absorpsjon:

A + AB = A

•Konsensusteorem:

A + \overline{A}B = A + B

•Binær → heks: grupper 4 biter fra høyre

•Binær → oktal: grupper 3 biter fra høyre

Kombinatorisk logikk

•SOP: summer AND-termer for rader med utgang = 1
•POS: multipliser OR-termer for rader med utgang = 0
•Full adder: $S = A \oplus B \oplus C_{in}$ , $C_{out} = AB + C_{in}(A \oplus B)$
•MUX 4-til-1: $Y = \overline{S_1}\overline{S_0}D_0 + \overline{S_1}S_0 D_1 + S_1\overline{S_0}D_2 + S_1 S_0 D_3$
•Carry generate: $G_i = A_i B_i$ ; Carry propagate: $P_i = A_i \oplus B_i$
•K-kart-grupperinger: størrelse $2^k$ , wrap rundt kanter, eliminer variabler som veksler

Sekvensiell logikk og flip-flops

•SR-latch forbudt tilstand: $S=1, R=1$
•D-flip-flop: lagrer $D$ på stigende klokkeflank
•Minimum klokkperiode: $T_{min} = t_{pcq} + t_{comb} + t_{setup}$
•Maks klokkefrekvens: $f_{max} = 1 / T_{min}$
•Hold-tidsbetingelse: $t_{pcq} + t_{comb\_min} \geq t_{hold}$
•Skiftregister: $Q_i \to D_{i+1}$ for hver flip-flop

Tilstandsmaskiner (FSM)

•Moore: $\text{utgang} = f(\text{nåværende tilstand})$
•Mealy: $\text{utgang} = f(\text{nåværende tilstand, inngang})$
•Antall flip-floper ved binær koding: $\lceil \log_2 n \rceil$ for $n$ tilstander
•Antall flip-floper ved one-hot koding: $n$ (én per tilstand)
•FSM-implementasjon: tilstandskoding → neste-tilstand-logikk → utgangslogikk

Digitale byggeblokker

•Subtraksjon: $A - B = A + \overline{B} + 1$ (toverkomplement)
•n-bits binær teller: teller fra 0 til $2^n - 1$
•Tri-state buffer: utgang = Z (høyimpedans) når output-enable = 0
•SRAM: flip-flop-basert, rask, ikke-destruktiv lesing → brukes i cache
•DRAM: kondensatorbasert, tettere, trenger refresh → brukes i DRAM-moduler

Prosessorarkitektur

•PC-inkrementering: $\text{PC} \leftarrow \text{PC} + 4$ (32-bits instruksjoner, byte-adressert)
•Enkeltyklus CPI = 1 (men lang klokkperiode)
•Gjennomsnittlig CPI flersyklus $\displaystyle = \sum_i \text{frekvens}_i \times \text{sykluser}_i$
•ISA-grensesnitt: registerfil, instruksjonsformat, adresseringsmoduser, minnemodell

ARM assembly-programmering

•ARM RISC: kun LDR/STR aksesserer minne; ALU-ops bruker bare registre
•LDR Rd, [Rn, #offset]: Rd = Minne[Rn + offset]
•STR Rd, [Rn, #offset]: Minne[Rn + offset] = Rd
•BL subroutine: PC = subroutine, LR = returadresse (neste instruksjon)
•PUSH {Rx, LR} / POP {Rx, PC} — standard subrutineprolog/epilog
•CMP R0, R1: beregner R0 - R1, setter N/Z/C/V flagg, forkaster resultat

Pipelining

•Ideell pipeline-CPI = 1
•Faktisk CPI = 1 + stall-sykluser per instruksjon
•Ytelse: $T = N \times \text{CPI} \times t_{clk}$
•Speedup pipelining: $S \approx k$ (antall pipeline-stadier) for lange programmer
•Load-use hazard: alltid 1 stall-syklus (forwarding kan ikke hjelpe her)
•RAW-hazard løst med forwarding: resultat rutes fra EX/MEM til EX-inngang

Cache og minnehierarki

• $\text{AMAT} = t_{hit} + (1-h) \times t_{miss\_penalty}$
•Adressedekomposisjon: tag = $w - s - b$ , index = $s$ , offset = $b$ biter
•Antall sett = $2^s$ , linjer per sett = $E$ , blokkstørrelse = $2^b$ bytes
•Total cache-kapasitet = $2^s \times E \times 2^b$ bytes
•Konfliktmiss: to adresser mapper til samme sett, tvinger hverandre ut
•LRU: bytt ut linjen med lengst tid siden sist bruk

Virtuelt minne

•Virtuell adresse = VPN || offset; Fysisk adresse = PPN || offset
•Offset-størrelse = $\log_2(\text{sidestørrelse})$ biter
•VPN-størrelse = virtuell adressebredde $-$ offset-størrelse
•Page fault: valid bit = 0 i sidetabellen → OS laster inn siden fra disk
•TLB: fullt assosiativ cache for VPN→PPN-oversettelser

Maskinvare–programvare-grensesnitt

•ARM AAPCS: argumenter i R0–R3, returverdi i R0
•Callee-saved: R4–R11 (MÅ bevares av kallee)
•Caller-saved: R0–R3, R12 (kallee behøver ikke bevare)
•Memory-mapped I/O: LDR/STR til I/O-registeradresser
•Interrupt: asynkront signal → lagre PC → hopp til ISR → gjenopprett PC

Digital simulering med VHDL/HDL

•VHDL-struktur: ENTITY (grensesnitt) + ARCHITECTURE (oppførsel)
•Concurrent signal assignment: y <= a AND b;
•Synkron flip-flop: if rising_edge(clk) then q <= d; end if;
•Asynkron reset: sjekk reset FØR rising_edge(clk) i process
•Testbench: ingen porter, instansierer DUT, bruker wait for N ns;
•std_logic: '0', '1', 'Z' (høyimpedans), 'X' (udefinert)

•Beregne maksimal frekvens uten å inkludere setup-tid i klokkperioden.

•Tro at synkron design er tregere enn asynkron – synkron er som regel mer forutsigbar og er industristandard.

Tilstandsmaskiner (FSM)

•Forveksle Moore og Mealy: i Mealy skrives utgangen på pilen (avhenger av inngang), i Moore skrives utgangen i noden (avhenger bare av tilstand).
•Glemme overganger for alle mulige innganger fra hver tilstand – en fullstendig FSM har alltid én overgang per (tilstand, inngang)-par.
•Bruke feil antall flip-floper ved tilstandskoding – binær koding krever bare $\lceil \log_2 n \rceil$ flip-floper.
•Glemme starttilstand og reset-logikk i implementasjonen.

Digitale byggeblokker

•Glemme carry-in = 1 ved subtraksjon – uten carry-in = 1 er resultatet enerkomplement, ikke toverkomplement.
•Tro at SRAM og DRAM er like – SRAM er mye raskere men dyrere; DRAM er tettere men trenger periodisk refresh.
•Koble to tri-state buffere til bussen uten å sikre at aldri mer enn én er aktiv – gir kortslutning.

Prosessorarkitektur

•Forveksle CPI og klokkperiode: enkeltyklusprosessor har CPI=1 men lang klokkperiode; pipelining reduserer effektiv CPI.
•Glemme PC-oppdatering (PC+4) i fetch-steget.
•Tro at kontrollenhet og ALU er det samme – kontrollenheten genererer kontrollsignalene til ALU og MUX-er; ALU utfører beregningene.

ARM assembly-programmering

•Bruke aritmetiske instruksjoner direkte på minne – ARM tillater IKKE dette (load/store-arkitektur).
•Glemme S-suffikset (f.eks. SUBS, ADDS) for å sette flagg – uten S endres ikke CPSR.
•Forveksle pre-increment [Rn, #4]! og post-increment [Rn], #4 – pre oppdaterer Rn FØR minneaksess, post ETTER.
•Glemme at CMP setter flagg basert på subtraksjon – BLT hopper hvis N != V (fortegnsmessig).

Pipelining

•Tro at forwarding eliminerer alle datahazarder – load-use hazard krever alltid én stall-syklus uavhengig av forwarding.
•Glemme at kontrollhazarder koster flush-sykluser, ikke stall-sykluser fra neste-tilstand-logikk.
•Beregne pipeline-speedup som eksakt $k$ – speedup er bare $k$ for uendelig lange programmer; startup-kost reduserer dette.
•Forveksle hazard-deteksjonsenhet (identifiserer problemet) og forwarding-enhet (løser problemet).

Cache og minnehierarki

•Forveksle index og tag: index velger SETT, tag identifiserer BLOKK innen settet.
•Glemme offset-feltets rolle: offsetet velger byte innen en cache-blokk – en cache-miss laster inn HELE blokken.
•Beregne AMAT med riktig formel men glemme å inkludere hit-tid i resultatet.
•Tro at høyere assosiativitet alltid er bedre – det øker hardware-kompleksitet og kan øke hit-tid.

Virtuelt minne

•Endre offset ved adresseoversettelse – offsetet kopieres UENDRET fra virtuell til fysisk adresse.
•Glemme at valid bit = 0 gir page fault – page fault håndteres av OS, cache-miss av hardware.
•Forveksle TLB-miss (manglende oversettelse) og page fault (siden er ikke i DRAM).
•Glemme at sidetabellen er én per prosess – kontekstbytte krever skifte av sidetabellpeker.

Maskinvare–programvare-grensesnitt

•Glemme at R4–R11 er callee-saved og MÅ PUSHes i subrutinen hvis de brukes.
•Forveksle interrupt (asynkront, fra hardware) og exception (synkront, fra CPU).
•Glemme at stakken vokser nedover på ARM – SP dekrementeres ved PUSH, inkrementeres ved POP.

Digital simulering med VHDL/HDL

•Glemme sensitivitetslisten i process – manglende signaler gir feil simuleringsoppførsel (ikke syntaksfeil).
•Bruke tilordning (:=) for signaler – signaler bruker <=; variabel bruker :=.
•Skrive asynkron reset etter rising_edge-sjekken – reset SKAL sjekkes FØRST (høyere prioritet).
•Forveksle concurrent statement (alltid aktiv) og process (utføres sekvensielt ved signal-endring).

•Toverkomplement er ekstremt hyppig. Øv på konvertering begge veier og sjekk alltid med tilbakekonvertering.

•«Største positive 8-bits 2'er-komplement-tall»

= 127

; antall ulike verdier med 12 bit

= 4096

; minimum bit for 500 verdier

= 9

(

2^9=512

). Disse småoppgavene er gratispoeng – ikke rot med

2^n

vs.

2^n-1

•Heksadesimale adresser brukes gjennomgående i cache- og minneoppgaver – bli komfortabel med heks ↔ binær konvertering.

Kombinatorisk logikk

•To faste flervalgsoppgaver hvert år: avles funksjonsuttrykk fra et portdiagram (pass på rekkefølgen NOT/AND/OR og De Morgan), og forenkle et uttrykk maksimalt (bruk absorpsjon, $A+\overline{A}B=A+B$ og konsensusteorem aktivt).
•K-kart opp til 4 variabler er standard pensum. Øv på å lese av forenklede uttrykk raskt.
•For adder-oppgaver: ripple-carry er treg men enkel og bruker færrest porter; carry-lookahead/prefiksadder har propageringstid på formen $K_1 + K_2\log_2(\text{antall bit})$ og blir spurt om i ytelsessammenheng.
•Adder, dekoder, multiplekser, shifter og LUT/ROM dukker opp som «digitale byggeblokker» – se egen seksjon for disse.

Sekvensiell logikk og flip-flops

•Den tyngst vektede enkeltoppgaven (12 poeng hvert år) er bølgeform-oppgaven: tre kretser med clk og inngang s, der du skal matche utgangene a/b/c/d til riktige tidsforløp (u1–u6). Det avgjørende er å SKILLE latch (transparent når enable er høy) fra flip-flop (oppdaterer kun på klokkeflank) – tegn signalet steg for steg.
•Propageringsforsinkelse + kritisk sti + maks klokkefrekvens er en fast regneoppgave (ofte koblet til en VHDL-fulladder/ripple-carry): tell portnivåer langs lengste sti, legg til registertillegg, og bruk $f_{max} = 1/T_{krit}$ .
•Timing-beregninger (setup, hold, max frekvens) er standardoppgaver – lær formelen $T_{min} = t_{pcq} + t_{comb} + t_{setup}$ utenat.
•Skille mellom asynkron reset (reset kan skje når som helst) og synkron reset (reset skjer bare på klokkeflank) – begge varianter brukes i VHDL.

Tilstandsmaskiner (FSM)

•FSM-oppgaver kombinerer ofte diagram, tilstandstabell og implementasjon – øv på hele kjeden.
•Tegn alltid tilstandsdiagrammet FØR du fyller ut tilstandstabellen – det er lettere å se overgangene visuelt.
•Sekvensgjenkjenner-FSMer er klassiske eksamensoppgaver – øv på «101»-, «110»- og «1100»-varianter.

Digitale byggeblokker

•Denne seksjonen er undervurdert i pensumvektingen, men HØY på eksamen: ALU-resultat + flagg, oppslagstabell (LUT) som logisk funksjon, 2-4 dekoder og shifter (SLL/SRL/SRA/ROL/ROR) dukker opp omtrent hvert år.
•ALU-oppgave: regn ut Result for gitt kontrollbit (AND/OR/ADD/SUB), forkast carry-ut ved gitt bitbredde, og avgjør hvilke av N/Z/C/V som settes – øv på alle fire flaggene.
•LUT/dekoder: hver utgang er en minterm. Lær å gjenkjenne uttrykk som xnor, nand og «not (A or B)» og plassere dem på riktig $Y_i$ .
•ROM som kombinatorisk sannhetstabell – en $n$ -bit adresse gir $2^n$ kombinasjoner; «prikk = logisk 1» avleses direkte.

Prosessorarkitektur

•Garantert oppgave: tell klokkesykler for samme program på single-cycle (CPI=1), multi-cycle (gitt fast CPI, ofte 4) og 5-stegs pipeline (N+4+staller). Øv på varianten der frekvensene er ulike og du må regne faktisk kjøretid i ns.
•Skill ARKITEKTUR (ISA – hvilke instruksjoner finnes, registre) fra MIKROARKITEKTUR (hvordan ISA implementeres – antall pipeline-steg, klokke). Maskinkode kompilert for én ARM-mikroarkitektur kjører på alle med samme arkitektur.
•Konseptuelle flervalg går igjen: pipeline har effektiv CPI nær 1; multi-cycle har ikke hazards; pipeline er typisk raskere enn multi-cycle.
•Koble prosessorarkitektur til pipelining: pipeline-stadiene (IF, ID, EX, MEM, WB) korresponderer direkte med trinnene her.

ARM assembly-programmering

•Branch Target Address er en garantert flervalgsoppgave: bruk $imm24 = (\text{mål} - \text{hopp} - 8)/4$ . Husk $-8$ (PC peker to instruksjoner frem) og at bakoverhopp gir negativ verdi.
•Maskinkode-dekoding er fast: lær instruksjonsformatene (cond, opcode, S-bit, I-bit, $R_d$ , $R_n$ , Src2) slik at du kan oversette bitmønster til f.eks. ADD/ADDS/ANDEQ + riktige registre.
•Oversettelse C ↔ assembler går begge veier: enten fyll inn manglende instruksjoner i en løkke/if-else, eller velg hvilken C-funksjon en assemblersnutt tilsvarer. CMP + betinget hopp (BLT/BNE/BEQ) er kjernen.
•Funksjonskallkonvensjon: callee MÅ lagre R4–R11 og LR hvis de brukes; R0–R3 er caller-saved. Eksamen spør konkret «hvilke registre må F lagre på stacken?» – sjekk hvilke R4+-registre funksjonen skriver til.
•Loopstrukturer med SUBS + BNE og retur via MOV PC, LR er standardmønsteret – forstå dette i søvne.

Pipelining

•Den faste eksamensoppgaven: gitt en kort kodesekvens og en 5-stegs pipeline UTEN hazard-håndtering (skriv i første halvdel, les i andre halvdel av syklusen) – angi registeraktivitet (leser/skriver/begge/ingen) og hvilken hazard (data/control/ingen) per klokkesyklus. Tegn alltid pipeline-skjemaet (instruksjon × syklus) først.
•Pass på halv-syklus-regelen: når registerfilen skrives i FØRSTE halvdel og leses i ANDRE halvdel, er et resultat tilgjengelig allerede i WB-syklusen til den skrivende instruksjonen – det fjerner én hazard sammenlignet med naiv timing.
•Branch prediction-spørsmål er konseptuelle: formålet er å forutsi branch-utfall og redusere pipeline-staller; miss-prediction penalty = antall instruksjoner som må flushes.
•Skille tydelig mellom datahazard (RAW) og kontrollhazard (branch) i svarene dine.

Cache og minnehierarki

•Cache er det tyngst vektede minnetemaet (ofte 16–24 poeng). Tre faste oppgavetyper: (1) regn adressebredde + antall sett + tag-biter, (2) tell bom/treff over en gitt adressesekvens og finn treffrate (og konvergens ved uendelig gjentakelse), (3) AMAT med ett eller to cache-nivåer.
•Adressedekomposisjon: blokk $= \lfloor \text{adresse}/\text{blokkstørrelse} \rfloor$ , sett $= \text{blokk} \bmod (\text{antall sett})$ . Før en settabell mens du går gjennom sekvensen.
•To-nivå AMAT: $t_{L1} + (1-h_{L1})[t_{L2} + (1-h_{L2})t_{mem}]$ . Pass på at L2-miss-straffen kun gjelder andelen som bommer i L1.
•Set-assosiativ vs. direkte-mappet: LRU kaster ut blokken det er lengst siden ble brukt. Flere veier i settet reduserer konfliktmiss; større blokk utnytter spatial lokalitet.

Virtuelt minne

•Den faste eksamensoppgaven er ren bit-telling: gitt virtuelt adresserom, fysisk minne og sidestørrelse, finn antall bit i fysisk adresse, VPN og PPN. Offset = $\log_2(\text{sidestørrelse})$ og er likt virtuelt/fysisk.
•Konseptuelle flervalg er garantert: sidetabellen ligger i hovedminnet, TLB er vanligvis fullt assosiativ, og virtuelt minne lar programmer bruke samme adresser uten konflikt – også når virtuelt = fysisk størrelse.
•Skill TLB-miss (manglende oversettelse, slå opp i sidetabell) fra page fault (siden ikke i DRAM, OS henter fra disk).
•Sideutskiftingsalgoritmer (LRU vs. FIFO) dukker opp i oppgaver med en sekvens av sideaksesser – trace-oppgaver.

Maskinvare–programvare-grensesnitt

•Kallkonvensjoner kobles direkte til ARM assembly-seksjonen – forstå registertildelingen (R0–R3 argumenter, R0 retur).
•Interrupt-mekanismen kan beskrives trinn for trinn – lær de seks stegene utenat.
•Forholdet mellom C-kode og tilsvarende assembly-kode er gjerne en eksplisitt eksamensoppgave.

Digital simulering med VHDL/HDL

•VHDL/HDL er HØY på eksamen (10–14 poeng hvert år), tyngre enn pensumvektingen antyder. Den vanligste formen er å LESE ferdig kode og klassifisere: er kretsen kombinatorisk eller sekvensiell? Er kodestilen dataflow, structural eller behavioral/RTL? Hvilken type adder (half adder, full adder, ripple-carry, carry-lookahead/prefiks) eller testbench/simuleringsmodul beskriver den?
•Kjenne igjen mønstre: dataflow = concurrent signaltilordninger ( $\le$ ); structural = port map / component-instansiering (evt. for…generate); behavioral/RTL = process med if/case. En entity uten porter er en testbench/simuleringsmodul.
•Komponent-matching: en `for i in 0 to 7 generate` av en fulladder med carry-kjeding er en ripple-carry adder; en simuleringsmodul kan instansiere to implementasjoner og sammenligne dem med assert.
•Lær standardmønstrene utenat: concurrent assignment, if/case i process, og synkron flip-flop med asynkron reset (reset sjekkes FØR rising_edge).
•std_logic-oppløsning ved konflikt: '1' mot '0' gir 'X'; en sterk driver ('0'/'1') overstyrer en svak ('L'/'H').