Formulario - architettura degli elaboratori

Struttura del calcolatore

Note: Architettura e organizzazione di un calcolatoreDifferenza tra architettura (ciò che vede il programmatore) e organizzazione (come è realizzata); struttura e funzione; le quattro funzioni e i quattro componenti; macchina di von Neumann e IAS; generazioni tecnologiche e legge di Moore.Architettura e organizzazione di un calcolatore → · Ciclo fetch-executeRegistri PC, IR, MAR e MBR; ciclo dell'istruzione diviso in fetch ed execute; i quattro tipi di operazioni; diagramma degli stati del ciclo con calcolo degli indirizzi degli operandi e controllo delle interruzioni; esempio su una macchina ad accumulatore.Ciclo fetch-execute → · Bus e interconnessioneBus di sistema diviso in linee dati, indirizzi e controllo; ampiezza del bus e spazio di indirizzamento; arbitraggio; bus singolo e gerarchie di bus multipli; temporizzazione sincrona e asincrona; interconnessioni punto a punto.Bus e interconnessione →

• Architettura = attributi visibili al programmatore (istruzioni, indirizzamento, I/O); organizzazione = come sono realizzati. Von Neumann: dati e istruzioni nella stessa memoria, indirizzata per posizione, esecuzione in sequenza. Legge di Moore: i transistor per chip raddoppiano ogni 18-24 mesi (4004 nel 1971: circa 2300; 8086 nel 1978: circa 29 000).

• Fetch: $\text{MAR}\leftarrow\text{PC}$; $\text{MBR}\leftarrow M[\text{MAR}]$; $\text{IR}\leftarrow\text{MBR}$; $\text{PC}\leftarrow\text{PC}+4$ (ARM, MIPS). Poi decodifica ed esecuzione; le interruzioni si controllano tra due istruzioni. Un salto relativo parte dal PC già avanzato.
• Bus: dati a 32 linee $\to$ 4 byte per ciclo; indirizzi a $k$ linee $\to2^k$ locazioni (24 $\to$ 16 M, 32 $\to$ 4 G); controllo; sincrono (clock comune) o asincrono (handshake).

Rappresentazione dell'informazione

Note: Sistemi di numerazione posizionaliNotazione posizionale in base b; conversioni tra base 10, 2, 8 e 16 per interi (divisioni successive) e per parti frazionarie (moltiplicazioni successive); numeri periodici in binario.Sistemi di numerazione posizionali → · Rappresentazione dei numeri interi con segnoInteri con segno su n bit: modulo e segno, complemento a 1, complemento a 2 ed eccesso K; intervalli rappresentabili, calcolo dell'opposto, estensione del segno.Rappresentazione dei numeri interi con segno → · Aritmetica binariaSomma e sottrazione in binario, overflow per senza segno (riporto) e per complemento a 2 (segni), flag del processore, moltiplicazione per somme e scorrimenti, algoritmo di Booth, divisione, shift logici e aritmetici.Aritmetica binaria → · Numeri in virgola mobile IEEE 754Virgola fissa e virgola mobile; formato IEEE 754 a 32 e 64 bit (segno, esponente in eccesso 127, mantissa con 1 implicito); conversioni svolte nei due versi; valori speciali, denormalizzati, intervallo, precisione e arrotondamento.Numeri in virgola mobile IEEE 754 → · Codifiche binarie e informazione non numericaBit, byte e multipli (potenze di 2 e di 10); codici BCD e Gray; caratteri ASCII, Unicode e UTF-8; ordine dei byte (little e big endian); bit di parità e codice di Hamming per rilevare e correggere errori.Codifiche binarie e informazione non numerica →

• Base $b$: $(c_{n-1}\dots c_0,c_{-1}\dots c_{-m})_b=\sum_{i=-m}^{n-1}c_ib^i$. Con $n$ cifre si scrivono $b^n$ numeri; per $N$ valori servono $\lceil\log_2N\rceil$ bit. Parte intera: divisioni per $b$ con resti letti dal basso; frazione: moltiplicazioni per $b$ (una frazione è finita in base 2 solo se $\frac{k}{2^j}$). Ottale = 3 bit, esadecimale = 4 bit, raggruppando dalla virgola.
• Con $n$ bit: modulo e segno $\pm(2^{n-1}-1)$, due zeri; complemento a 1: $-x$ = bit invertiti, due zeri; complemento a 2: $x=-c_{n-1}2^{n-1}+\sum_{i=0}^{n-2}c_i2^i$, intervallo $[-2^{n-1},2^{n-1}-1]$, un solo zero, $-x=2^n-x$ (inverti e somma 1); eccesso $K$: si memorizza $x+K$. Estensione del segno: si replica il MSB.

• Somma e sottrazione: $a-b=a+\overline b+1$, riporto uscente scartato. Overflow senza segno: $C=1$; in complemento a 2 $V=c_n\oplus c_{n-1}$ (operandi dello stesso segno, risultato di segno opposto; segni diversi: mai overflow). Shift: logico a sinistra $\times2^k$; logico a destra $\div2^k$ (senza segno); aritmetico a destra replica il segno (complemento a 2).
• Moltiplicazione: $n$ bit $\times\,n$ bit $\to2n$ bit; senza segno: se $Q_0=1$ si somma $M$ ad $A$ e si scorre $C,A,Q$ a destra. Booth: $(Q_0,Q_{-1})=10\Rightarrow A\leftarrow A-M$, $01\Rightarrow A\leftarrow A+M$, $00,11\Rightarrow$ niente, poi shift aritmetico a destra. Divisione: si sottrae il divisore dal resto parziale e si ripristina se il resto è negativo.
• IEEE 754: $x=(-1)^S\cdot1{,}M\cdot2^{E-\text{bias}}$. Singola 1+8+23 bit, bias 127; doppia 1+11+52, bias 1023. $E=0$: $\pm0$ ($M=0$) o denormalizzato $0{,}M\cdot2^{-126}$; $E=255$: $\pm\infty$ ($M=0$) o NaN. Massimo $\approx3{,}4\cdot10^{38}$, minimo normalizzato $2^{-126}$, $\varepsilon=2^{-23}$, distanza tra float consecutivi $2^{e-23}$. Esempio $-12{,}375=1{,}100011\cdot2^3$: $E=130$, C1460000. Arrotondamento al più vicino, pari in caso di parità; somma non associativa ($2^{24}+1=2^{24}$); prodotto: $E_1+E_2-127$.
• Codici: BCD 4 bit per cifra; Gray $g=b\oplus(b\gg1)$; ASCII 7 bit ('0'=48, 'A'=65, 'a'=97); UTF-8 1-4 byte; little endian per x86 e ARM. Ki $=2^{10}$, Mi $=2^{20}$, Gi $=2^{30}$.
• Hamming SEC con $m$ dati e $k$ controlli: $2^k-1\ge m+k$ ($m=8,16,32,64\to k=4,5,6,7$); controlli in posizione $2^j$, $C_{2^j}$ = XOR dei dati con il bit $j$ a 1; sindrome $=0$ nessun errore, altrimenti è la posizione da invertire. SEC-DED: parità globale in più. Parità: rileva un numero dispari di errori.

Reti logiche

Note: Algebra di Boole e porte logicheVariabili booleane, operatori AND, OR, NOT e derivati (NAND, NOR, XOR, XNOR) con tabelle di verità; assiomi e teoremi dell'algebra di Boole, De Morgan; porte logiche e completezza di NAND e NOR; semplificazione algebrica con esempio.Algebra di Boole e porte logiche → · Reti combinatorie e mappe di KarnaughRete combinatoria (uscite funzione dei soli ingressi attuali); mintermini e maxtermini, forme canoniche SOP e POS; mappe di Karnaugh a 3 e 4 variabili con esempi svolti; condizioni di indifferenza; costo e ritardo di una rete a due livelli.Reti combinatorie e mappe di Karnaugh → · Circuiti combinatori notevoliMultiplexer, decodificatore e codificatore; semisommatore e sommatore completo; sommatore a propagazione del riporto e suo ritardo, idea dell'anticipo del riporto; sommatore-sottrattore in complemento a 2 con rilevazione dell'overflow; comparatore.Circuiti combinatori notevoli → · Latch e flip-flopReti sequenziali e retroazione; latch SR con porte NOR e stato proibito; latch SR e D abilitati dal clock; flip-flop D master-slave sensibile al fronte; flip-flop JK e T; tempi di setup e hold; clock e periodo minimo.Latch e flip-flop → · Reti sequenziali e automi a stati finitiModello di una rete sequenziale sincrona (stato in flip-flop, logica di stato prossimo e di uscita); automi di Moore e di Mealy; procedimento di sintesi con esempio svolto di un riconoscitore della sequenza 11.Reti sequenziali e automi a stati finiti → · Registri e contatoriRegistro parallelo a n bit con caricamento abilitato; banco dei registri con due porte di lettura e una di scrittura; registri a scorrimento; contatori sincroni e asincroni (ripple), contatore modulo N con esempio svolto.Registri e contatori →

• Boole: $A+\overline AB=A+B$, assorbimento $A+AB=A$, distributive doppie, De Morgan $\overline{AB}=\overline A+\overline B$, $\overline{A+B}=\overline A\,\overline B$. Completezza di NAND e NOR: $\overline A=\overline{AA}$, $AB=\overline{\overline{AB}}$, $A+B=\overline{\overline A\,\overline B}$. XOR $=A\overline B+\overline AB$.
• Mintermine (AND di tutte le variabili, vale 1 su una riga); SOP = OR dei mintermini con $F=1$; maxtermine (OR, vale 0 su una riga); POS = AND dei maxtermini con $F=0$. Karnaugh: righe e colonne in Gray, gruppi di $2^k$ uni che eliminano $k$ variabili; indifferenze (X) usate come 0 o 1.

• MUX 2:1 $Y=\overline S\,I_0+S\,I_1$; decoder $n\to2^n$; semisommatore $S=A\oplus B$, $C=AB$; sommatore completo $S=A\oplus B\oplus C_{in}$, $C_{out}=AB+C_{in}(A\oplus B)$; ripple carry lineare ($\sim2n$ porte); anticipo del riporto $g_i=A_iB_i$, $p_i=A_i+B_i$, $c_1=g_0+p_0c_0$; sommatore-sottrattore: XOR di $B$ con SUB, che è anche il riporto iniziale.
• Latch SR: $00$ mantiene, $10$ set, $01$ reset, $11$ proibito. Latch D: $C=1$ trasparente, $C=0$ mantiene. Flip-flop D: $Q_{t+1}=D_t$ sul fronte. JK: $Q_{t+1}=J\overline{Q_t}+\overline KQ_t$; T: $Q_{t+1}=T\oplus Q_t$. Periodo minimo $T_{clock}\ge t_{clk\to Q}+t_{comb,\max}+t_{setup}$ ($50+800+30=880$ ps, circa 1,14 GHz).
• Automa a stati finiti: $S'=\delta(S,X)$, Moore $Z=\lambda(S)$, Mealy $Z=\lambda(S,X)$; $k=\lceil\log_2N\rceil$ flip-flop. Contatore sincrono: $T_0=1$, $T_1=Q_0$, $T_2=Q_1Q_0$, $T_3=Q_2Q_1Q_0$; $Q_i$ ha frequenza $\frac f{2^{i+1}}$. Registro a scorrimento: scorrimento $=\times2$ o $\div2$.

Architettura del processore

Note: Struttura interna della CPU e registriComponenti interni della CPU (ALU, unità di controllo, banco dei registri, bus interno); registri visibili all'utente e registri di controllo e stato; flag e parola di stato (PSW) con bit di supervisore; quanti registri conviene avere; segmentazione della memoria.Struttura interna della CPU e registri → · Instruction Set ArchitectureChe cosa definisce un insieme di istruzioni; elementi di un'istruzione; tipi di operandi e di operazioni; macchine a 0, 1, 2 e 3 indirizzi con lo stesso calcolo svolto in ciascuna; architetture load/store.Instruction Set Architecture → · Formato delle istruzioni e modalità di indirizzamentoModalità di indirizzamento (immediato, diretto, indiretto, a registro, indiretto a registro, con spiazzamento, relativo al PC, indicizzato e scalato, a pila) con indirizzo effettivo ed esempi; formati fissi e variabili; i formati R, I e J di MIPS e il formato a 32 bit di ARM con il calcolo dei campi.Formato delle istruzioni e modalità di indirizzamento → · Architetture RISC e CISCMotivazioni del CISC (divario semantico) e dati sull'esecuzione dei programmi; caratteristiche delle architetture RISC; finestre di registri; allocazione dei registri con colorazione di un grafo; confronto e situazione attuale (MIPS, ARM, x86).Architetture RISC e CISC → · L'architettura ARMARM a 32 bit come caso di studio: registri r0-r15 con SP, LR e PC, registro di stato CPSR con flag NZCV, modi del processore, architettura load/store, istruzioni condizionate, secondo operando flessibile, Thumb; differenze principali con ARMv8 a 64 bit.L'architettura ARM →

• Numero di indirizzi per $Y=\frac{A-B}{C+D\cdot E}$: 3 (SUB, MUL, ADD, DIV), 2 (la destinazione coincide col primo operando), 1 (accumulatore), 0 (pila con PUSH e POP). Meno indirizzi: istruzioni più corte ma più numerose.
• Registri: più registri riducono gli accessi alla memoria ma servono più bit per indicarli ($2^5=32$) e più stato da salvare. PSW (CPSR in ARM): flag N, Z, C, V, interruzioni, bit di supervisore.
• RISC: un'istruzione per ciclo a regime, solo load e store accedono alla memoria, formato fisso, molti registri, controllo cablato; CISC: istruzioni complesse e di lunghezza variabile, microprogrammato. MIPS: formato R op(6) rs(5) rt(5) rd(5) shamt(5) funct(6); I op(6) rs(5) rt(5) immediato(16); J op(6) indirizzo(26).
• ARM (A32, 32 bit): r0-r3 argomenti e ritorno, r4-r11 variabili preservate, r12 IP, r13 SP, r14 LR, r15 PC (letto vale istruzione $+8$); CPSR con N, Z, C, V nei bit 31-28; little endian, load/store. Formato elaborazione dati: cond(4), 00, I(1), opcode(4), S(1), Rn(4), Rd(4), operando 2 (12); costante immediata di 8 bit ruotata di un numero pari di posizioni.

Programmazione assembly ARM

Note: Istruzioni ARM di elaborazione datiIstruzioni aritmetiche (ADD, SUB, RSB, ADC), logiche (AND, ORR, EOR, BIC, MVN), di spostamento (MOV), moltiplicazione (MUL, MLA); secondo operando immediato o registro scalato con LSL, LSR, ASR, ROR; aggiornamento dei flag con S, CMP e TST; esempi di traduzione di espressioni C.Istruzioni ARM di elaborazione dati → · Istruzioni ARM di accesso alla memoriaLDR e STR per parole, byte e mezze parole con e senza segno; modalità di indirizzamento con offset immediato o registro scalato, pre-indicizzata con write-back e post-indicizzata, con esempi di indirizzo effettivo; caricamento di indirizzi e costanti; LDM e STM.Istruzioni ARM di accesso alla memoria → · Strutture di controllo in assembly ARMSalti B e condizionati, codici di condizione con e senza segno; traduzione di if, if-else, while, for e do-while da C ad ARM; esecuzione condizionata per eliminare salti brevi; switch con tabella di salto.Strutture di controllo in assembly ARM → · Stack e chiamata di funzioni in ARMChiamata con BL e ritorno con BX LR; convenzione di chiamata AAPCS (argomenti in r0-r3, risultato in r0, registri da preservare r4-r11); stack discendente pieno con PUSH e POP; record di attivazione; funzioni foglia e non foglia; esempio ricorsivo del fattoriale con evoluzione dello stack.Stack e chiamata di funzioni in ARM → · Array e strutture dati in assembly ARMArray in memoria e calcolo dell'indirizzo di un elemento; scorrimento con indice o con puntatore; esempi svolti (somma, massimo, copia); stringhe terminate da zero e calcolo della lunghezza; matrici per righe; struct con offset dei campi e allineamento.Array e strutture dati in assembly ARM → · Dal programma C all'eseguibile ARMCatena di traduzione compilatore, assemblatore, linker e loader; file oggetto, tabella dei simboli e rilocazione; collegamento statico e dinamico; organizzazione della memoria di un processo; chiamare funzioni assembly da C e viceversa, con esempio.Dal programma C all'eseguibile ARM →

• Forma OP{cond}{S} Rd, Rn, Operando2: il suffisso S aggiorna i flag. Moltiplicazioni per costante: ADD r0,r1,r1,LSL #2 $=5r_1$; RSB r0,r1,r1,LSL #3 $=7r_1$. Bit 3 di r0: ORR r0,r0,#8 imposta, BIC r0,r0,#8 azzera, EOR r0,r0,#8 inverte.
• Indirizzamento della memoria con r1=0x1000, r2=3: [r1,#8] $\to$ 0x1008; [r1,r2,LSL #2] $\to$ 0x100C; pre-indicizzato [r1,#4]! accede e poi aggiorna r1; post-indicizzato [r1],#4 accede a r1 e poi lo aggiorna. LDR r0,=etichetta carica l'indirizzo.

• Costrutti: if-else con CMP, BNE, B fine oppure esecuzione condizionata (ADDEQ, SUBNE); ciclo for all'indietro con SUBS r0,r0,#1 e BNE ciclo; massimo CMP r0,r1 e MOVLT r0,r1. I confronti tra indirizzi usano BHS/BLO.
• Funzioni (AAPCS): argomenti in r0-r3 (caller-saved), risultato in r0, r4-r11 callee-saved, stack discendente pieno e allineato a 8 byte; PUSH {r4,lr} $=$ STMDB sp!,{r4,lr} e POP {r4,pc} ritorna. Una funzione non foglia salva lr. Fattoriale ricorsivo: 8 byte di stack per livello.
• Array: elemento $i$ a $\text{base}+i\cdot s$; LDR r3,[r1,r2,LSL #2]. Matrice per righe: $(i,j)\to\text{base}+(i\cdot C+j)\cdot4$. Stringa: byte terminati da 0. Struttura con campi allineati: {char; int; int} ha offset 0, 4, 8 e dimensione 12.
• Dal C all'eseguibile: preprocessore, compilatore (.s), assemblatore (.o), linker (simboli esterni e rilocazione), loader. Memoria di un processo dal basso: testo, dati statici, heap (cresce in alto), stack (cresce in basso).

Organizzazione del processore

Note: Unità aritmetico-logica (ALU)Ruolo dell'ALU, ingressi, uscite e flag; ALU a 1 bit con AND, OR e sommatore selezionati da un multiplexer; estensione a 32 bit, sottrazione, confronto set-less-than e rilevazione dello zero e dell'overflow; tabella dei segnali di controllo; unità di moltiplicazione e virgola mobile.Unità aritmetico-logica (ALU) → · Datapath e microarchitetturaMicroarchitettura come realizzazione dell'ISA; elementi del datapath (PC, memoria istruzioni e dati, banco dei registri, ALU, estensione del segno, multiplexer); percorso di un'istruzione aritmetica, di una load, di una store e di un salto; datapath a ciclo singolo e suo periodo di clock; datapath multiciclo.Datapath e microarchitettura → · Unità di controlloCompiti dell'unità di controllo e micro-operazioni; segnali di controllo del datapath con tabella per le classi di istruzioni; controllo cablato (combinatorio o a stati finiti) e controllo microprogrammato (memoria di controllo, microistruzioni orizzontali e verticali); confronto.Unità di controllo →

• ALU a $n$ bit: $n$ ALU a 1 bit con riporti in cascata; sottrazione con Binvert e $c_0=1$; $Z=\overline{r_{n-1}+\dots+r_0}$; $V=c_n\oplus c_{n-1}$. In ARM, dopo una sottrazione, $C=1$ significa nessun prestito ($a\ge b$ senza segno).
• Datapath: PC, memoria istruzioni, sommatore PC$+4$, banco dei registri, estensione del segno, ALU, memoria dati, multiplexer (ALUSrc, MemtoReg, RegDst, PCSrc). Salto: se Zero, PC $\leftarrow$ PC$+4+4\cdot$offset.
• Ciclo singolo: periodo = istruzione più lenta; con memoria 200 ps, registri 100 ps, ALU 200 ps: aritmetica 600, load 800, store 700, salto 500 ps, periodo 800 ps (1,25 GHz). Multiciclo: clock dettato dal passo più lento (200 ps): aritmetica 4 cicli, load 5, store 4, salto 3.

• Unità di controllo: cablata (veloce, RISC) o microprogrammata (memoria di controllo, microistruzioni orizzontali o verticali; CISC).

Gerarchia delle memorie

Note: Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località → · Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache → · Memoria principale a semiconduttoreCella di memoria e operazioni; RAM dinamica (condensatore, refresh) e statica (flip-flop), confronto; ROM, PROM, EPROM, EEPROM e flash; organizzazione dei chip e dei moduli con calcolo di linee di indirizzo e numero di chip; DRAM sincrona e DDR; errori e codici di correzione.Memoria principale a semiconduttore → · Memoria esterna - dischi, RAID e memorie otticheDisco magnetico (piatti, facce, tracce, settori, cilindri); tempo di accesso come somma di posizionamento, latenza rotazionale e trasferimento, con formule ed esempio; algoritmi di scheduling FCFS, SSTF e ascensore; livelli RAID da 0 a 6; SSD; CD, DVD e nastri.Memoria esterna - dischi, RAID e memorie ottiche → · Memoria virtualeIndirizzi virtuali e fisici, pagine e frame; traduzione con la tabella delle pagine e calcolo dei campi; page fault e sostituzione delle pagine; TLB e tempo di accesso effettivo; protezione e condivisione; confronto con la cache.Memoria virtuale →

• Località temporale e spaziale. Tempo medio con hit rate $h$: $T_{medio}=hT_1+(1-h)(T_1+T_2)=T_1+(1-h)T_2$ ($T_1=1$ ns, $T_2=100$ ns, $h=0{,}95\to6$ ns); due livelli $T_{L1}+m_{L1}(T_{L2}+m_{L2}T_{mem})$.

• Cache con blocchi di $K=2^w$ parole e $m$ linee: diretta linea $=\text{blocco}\bmod m$ (tag, linea, parola); completa (tag confrontato con tutte); a $n$ vie $v=\frac mn$ insiemi, insieme $=\text{blocco}\bmod v$. $\text{linee}=\frac CK$, $\text{insiemi}=\frac{\text{linee}}n$, parola $=\log_2K$, set $=\log_2(\text{insiemi})$, etichetta $=\text{bit}-\text{set}-\text{parola}$ (24 bit, $2^{14}$ linee, blocchi da 4 B: tag 8, linea 14, parola 2). Rimpiazzo LRU, FIFO, LFU, casuale; write-through o write-back (bit sporco, si riscrive l'intero blocco); miss obbligatori, di capacità, di conflitto.
• RAM: DRAM (condensatore, refresh, lettura distruttiva) e SRAM (flip-flop, cache). Chip $N\times b$: $\log_2N$ linee di indirizzo; 1 MB con chip $256\mathrm K\times1$: 8 chip per banco, 4 banchi, 32 chip, decoder 2$\to$4 sui 2 bit alti.
• Disco: $T_{accesso}=T_{seek}+T_{latenza}+T_{trasf}$, $T_{latenza}=\frac{T_{giro}}2$, $T_{trasf}=\frac DN\,T_{giro}$ (7200 giri/min: $T_{giro}=8{,}33$ ms, latenza $4{,}17$ ms; 64 KB su tracce da 256 KB: $2{,}08$ ms; con seek 8,5 ms $T=14{,}75$ ms). Scheduling FCFS, SSTF, ascensore. RAID 0 striping, 1 mirroring, 3 e 4 parità dedicata, 5 parità distribuita, 6 doppia ridondanza.

• Memoria virtuale: indirizzo = numero di pagina + offset ($\log_2$ pagina, invariato); virtuali 32 bit, fisici 30 bit, pagine da 4 KB: offset 12, pagina 20, frame 18 bit. Tabella delle pagine (validità, frame, protezione, riferimento, sporco): 0x00403A7C con frame 0x1F2 $\to$ 0x1F2A7C; $2^{20}$ voci da 4 B $=4$ MB, quindi più livelli. TLB: cache delle traduzioni ($0{,}98\cdot101+0{,}02\cdot201=103$ ns contro 200 ns). Page fault = miss, con write-back.

Sistemi di input/output

Note: Moduli di input-output e input-output programmatoPerché servono i moduli di I/O; funzioni del modulo (controllo, comunicazione, buffer, errori) e registri di stato, controllo e dati; I/O mappato in memoria e isolato con esempi; I/O programmato con attesa attiva e suo costo; confronto delle tre tecniche.Moduli di input-output e input-output programmato → · InterruptClassi di interruzioni; I/O guidato da interrupt; sequenza hardware e software di gestione con salvataggio del contesto sullo stack; identificazione della sorgente (linee multiple, polling, daisy chain, vettore); priorità e interruzioni annidate; eccezioni e modi in ARM.Interrupt → · Accesso diretto alla memoria (DMA)Modulo DMA e informazioni che riceve dalla CPU; trasferimento a blocco con un solo interrupt finale; furto di cicli e modalità a burst, punti in cui la CPU può essere sospesa; configurazioni del bus; canali e processori di I/O; confronto quantitativo con l'I/O a interrupt.Accesso diretto alla memoria (DMA) →

• I/O mappato in memoria (stesse load/store, consuma indirizzi) o isolato (IN, OUT). Programmato: polling del registro di stato (attesa attiva: con $10^9$ istruzioni/s e 1000 caratteri/s circa un milione di istruzioni per carattere), poi trasferimento.
• Interrupt: la CPU finisce l'istruzione, salva PC e PSW sullo stack ($SP=T\to T-2$, più $m$ registri), carica nel PC l'indirizzo della routine, poi ripristina; priorità con polling, daisy chain o arbitraggio. ARM: modi IRQ, FIQ, Supervisor, ritorno SUBS pc, lr, #4.
• DMA: la CPU programma indirizzo iniziale e numero di parole, il modulo trasferisce una parola alla volta (indirizzo $+1$, contatore $-1$) e invia un solo interrupt; furto di cicli o burst. 4 KB = 1024 parole: interrupt $\approx205\,000$ cicli, DMA $\approx300$ cicli.

Tecniche avanzate di progettazione

Note: PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline → · Hazard nella pipelineHazard strutturali, sui dati e sul controllo; dipendenze RAW, WAR e WAW; stalli e bolle con diagrammi; data forwarding (bypass) e caso load-use; riordino delle istruzioni da parte del compilatore e dell'hardware; costo dei salti.Hazard nella pipeline → · Branch predictionTecniche per gli hazard sul controllo: stallo, flussi multipli, prelievo anticipato del bersaglio, loop buffer, salto ritardato; predizione statica e dinamica con bit di storia, predittore a 1 e a 2 bit con esempio su un ciclo, tabella dei bersagli (BTB); costo di una predizione errata.Branch prediction → · Processori superscalari e multicoreParallelismo a livello di istruzione: processori superscalari, esecuzione fuori ordine, ridenominazione dei registri contro WAR e WAW, speculazione; limiti dell'ILP e della frequenza (consumo); multithreading, multicore e coerenza delle cache; acceleratori.Processori superscalari e multicore →

• Pipeline a 5 stadi: IF, ID, EX, MEM, WB, con registri di pipeline tra gli stadi. $\tau=\max_i\tau_i+d$, $T_k=(k+n-1)\,\tau$, $S_k=\frac{nk}{k+n-1}\to k$ ($k=5$, $n=100$: $S\approx4{,}8$). Stadi 200, 100, 200, 200, 100 ps con $d=20$: $\tau=220$ ps, $S=\frac{800}{220}\approx3{,}6$. Con stalli: $S=\frac k{1+\text{stalli per istruzione}}$. La latenza della singola istruzione non diminuisce.

• Hazard strutturali (cache separate, banco registri scritto nella prima metà del ciclo e letto nella seconda). Hazard sui dati: RAW (J legge ciò che I scrive), WAR, WAW; senza forwarding lw seguita da add dipendente costa 2 stalli; con forwarding nessuno stallo per le aritmetiche, 1 stallo nel load-use. Riordino statico o dinamico.
• Hazard di controllo: un salto preso butta 2 istruzioni; con 15% condizionati (60% presi) e 1% incondizionati: stalli $=0{,}01\cdot2+0{,}15\cdot0{,}6\cdot2=0{,}2$, $S=\frac5{1{,}2}\approx4{,}17$. Predizione statica (sempre non preso, per direzione) o dinamica: 1 bit (due errori per ciclo), 2 bit (si cambia dopo due errori consecutivi); ciclo con 9 presi e 1 non preso: 80% con 1 bit, 90% con 2 bit; BTB; il delay slot è sempre eseguito.
• Superscalare: più istruzioni per ciclo (CPI limite $\frac1n$), esecuzione fuori ordine con ritiro in ordine, ridenominazione dei registri contro WAR e WAW; multicore e coerenza delle cache (MESI); power wall $P\propto CV^2f$.

Valutazione delle prestazioni

Note: Prestazioni di un calcolatoreTempo di risposta e throughput; equazione del tempo di CPU con numero di istruzioni, CPI e clock, esempi svolti; CPI medio per classi di istruzioni; MIPS e MFLOPS e loro limiti; legge di Amdahl con esempi; benchmark e media geometrica; come hardware e software influenzano ciascun fattore.Prestazioni di un calcolatore →

• Prestazioni $=\frac1T$; $T_{CPU}=N_{istr}\cdot CPI\cdot T_{clock}=\frac{N_{istr}\cdot CPI}f$, $CPI=\sum_iF_i\cdot CPI_i$ (aritmetiche 50% a 1, load 20% a 5, store 10% a 3, salti 20% a 2: $CPI=2{,}2$). $\text{MIPS}=\frac f{CPI\cdot10^6}$, non confrontabile tra ISA diverse; $10^9$ istruzioni, $CPI=1{,}5$, 2 GHz: $0{,}75$ s.
• Legge di Amdahl: $S=\frac1{(1-F)+F/s}$ ($F=0{,}4$, $s=10$: $1{,}56$, limite $1{,}67$; $F=0{,}9$ su 8 core: $S\approx4{,}7$, limite 10). Benchmark SPEC: media geometrica dei rapporti.