Calcolatori Elettronici

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Calcolatori Ele ronici

1

tt

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Introduzione al corso 13

Calcolatore — Concetto e modelli 13

Livello layout e circuiti 14

Livello logica — ISA (Instruction set architecture) 15

Perché frequentare questo corso? 15

Citazioni illustri 15

Reti logiche — Reti Combinatorie 16

Livelli hardware 16

Livello di Layout 16

Livello Circuitale 16

Note sul Livello Circuitale 16

Introduzione al livello logico 16

Porta logica 17

Porte logiche che verranno utilizzate principalmente 17

Altre porte logiche 17

Reti combinatorie 17

Rete logica 17

Speci ca e realizzazione di reti combinatorie 17

Espressioni (formule) booleane 18

Come passare da una speci ca all’altra? 19

Funzioni booleane e rappresentazioni canoniche 19

Mintermini 19

Nota su funzioni a più uscite 20

Sintesi di reti logiche combinatorie 20

Sintesi con porte logiche elementari 20

Sempli cazione di reti combinatorie 20

Minimizzazione di reti logiche combinatorie — Cenni 20

Algebra di Boole 21

Assiomi e alcune proprietà dell’Algebra di Boole 21

Condizioni di indi erenza sulle uscite 22

Minimizzazione di reti logiche combinatorie nella pratica 23

Tempo di propagazione — Cenni 23

Tempo di propagazione di reti logiche combinatorie 23

Reti combinatorie di uso comune — Decoder e Multiplexer 24

Decodi catori (decoder) 24

Multiplexer 24

Un’applicazione del multiplexer 25

Esercizi su reti combinatorie 26

Esercizio da tema d’esame 26

Svolgimento 26

2

fi fi

fi ff fi

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Reti logiche — Reti sequenziali 28

Limiti delle reti combinatorie 28

Il «passo base»: memoria-rete combinatoria-memoria 28

Il segnale di clock 28

Reti sincrone e metodologie di temporizzazione 28

Limiti della temporizzazione sensibile ai livelli 28

Metodologia di temporizzazione sensibile ai fronti 28

Flip- op di tipo D 29

Nota sulla simbologia 29

Tempo di set-up, di hold, di propagazione 29

Temporizzazione sensibile ai fronti 30

Un caso particolare 30

Temporizzazione e vincoli temporali 30

Estensione di queste considerazioni a reti complesse 31

Speci ca di una rete sequenziale 31

Due modelli — Moore vs Mealy 31

Mealy vs Moore 32

Sintesi di una rete sequenziale 33

Macchina sequenziale di Moore 33

Macchina sequenziale di Mealy 33

Procedura di sintesi 33

Esempio del semaforo — Moore 34

Tabelle di transizione e delle uscite + formule 34

Realizzazione circuitale 34

Esempio del semaforo — Mealy 35

Realizzazione circuitale 35

Ricapitolando 35

Temporizzazione 35

Mealy vs Moore 36

Esercizi su reti sequenziali 37

Implementazione di contatori 37

Esercizio 1 37

Codi ca degli stati 37

Tabella delle transizioni e delle uscite 37

Macchina sequenziale 38

Contatore modulo k usando il modello di Mealy 38

Diagramma temporale con EN sempre attivo 38

Esercizio 2 — Implementazione di un sommatore sequenziale 38

Ingressi, uscite, automa 38

Codi ca degli stati 39

3

fl

fi

fi fi Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Tabella delle transizioni e delle uscite 39

Full adder 39

Macchina sequenziale per il sommatore a due stati 39

Esercizio 3 — Macchina distributrice del ca 40

Codi ca degli ingressi e dell’uscita 40

Diagramma degli stati 40

Assegnamento degli stati 40

Tabella delle transizioni e delle uscite 41

Schema macchina sequenziale 41

Diagramma degli stati di una macchina che non ruba i soldi 41

Mantenendo il resto per il prossimo ca è 41

Brevi richiami su codi ca binaria dei numeri interi 42

Codi ca binaria 42

Codi ca binaria di numeri naturali 42

Esempio 42

Esempio 42

Codi ca in complemento a due con n bit di interi relativi 42

Esempio — Rappresentazione di 84 (in 8 bit) 42

Somma di numeri in complemento a 2 42

Regole 42

Regola «dei segni» 43

Regola «dei riporti» 43

Esempi 43

Estensione del segno 43

ISA di riferimento — MIPS 44

Dove ci troviamo e i livelli interessanti nella lezione 44

Architettura MIPS 44

I registri del MIPS visibili al programmatore 44

Tipologie di istruzioni 45

Istruzioni aritmetico-logiche 45

Istruzioni aritmetiche 46

Istruzioni logiche 46

Istruzioni MIPS di shift 47

Shift a sinistra di n posizioni 47

Shift a destra di n posizioni 48

Istruzioni di trasferimento dati 48

Load word (lw) 49

Store word (sw) 49

Istruzioni di controllo 49

Salti incondizionati — j, jr e jal 49

4

fi

fi

fi

fi fi ff ff è

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Salti condizionati — beq e bne 50

Istruzione set on less than (slt) 51

Caratteristiche dell’architettura 51

LOAD-STORE 51

Registri general-purpose 51

RISC 52

Linguaggio macchina — formati delle istruzioni del MIPS 52

I tre formati delle istruzioni MIPS 52

Formato-R (register) — per istruzioni aritmetiche e logiche 53

Formato-I (immediate) 53

Codi ca delle istruzioni immediate 54

Indirizzamento immediato 54

Codi ca delle istruzioni di trasferimento 54

Indirizzamento tramite base o spiazzamento 54

Codi ca delle istruzioni di salto condizionato 54

Indirizzamento relativo al Program-Counter (PC-relative) 55

Esempio di indirizzamento PC-relative 55

Similarità fra formati 55

Formato-J (jump) — per istruzioni di salto incondizionato j e jal 56

Indirizzamento pseudo-diretto (per i salti incondizionati) 56

Indirizzamento pseudo-diretto (per i salti incondizionati) — schema 56

Schema riassuntivo — I 5 modi di indirizzamento del MIPS 57

Esercizi su ISA MIPS 58

Esercizio 1 58

Esercizio 2 58

Esercizio 3 — Appello 9 settembre 2011 58

Nota 59

Livello organizzazione — schemi di base ALU e Register File 60

Dove ci troviamo 60

Organizzazione del calcolatore secondo il modello di Von Neumann 60

Schema processore e memoria 60

Datapath — Due aspetti 60

Registro 61

Implementazione 61

ALU — Arithmetic Logic Unit 61

Operazione di somma 62

Una soluzione ad hoc 62

Una soluzione basata sulla tecnica di decomposizione 63

Full adder 63

Sommatore a n bit con n full-adder 63

5

fi

fi

fi Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Aggiunta delle operazioni logiche di AND e OR 63

Aggiunta di NOR e sottrazione 64

Aggiunta di slt e over ow detection 65

Aggiunta del bit di zero 67

Modalità di interconnessione 68

Interconnessione tramite bus singolo 68

Interconnessione con bus specializzati 69

Interconnessione con multiplexer 69

Decoder per la selezione della destinazione 70

Il Register File 70

Register File per il MIPS 70

CPU a singolo ciclo 71

Schema del processore (e memoria) 71

Temporizzazione 72

Progettazione Datapath — Caso MIPS 72

Codi ca delle istruzioni viste 72

Note sulla codi ca utili per la progettazione 73

Consideriamo inizialmente solo le istruzioni aritmetiche — ad esempio, add 73

Integrazione della lw e sw 74

Integrazione della beq 75

Integrazione della j 76

Progettazione unità di controllo 77

Il controllo (combinatorio) della ALU 77

Sempli cazione segnale di controllo per beq — senza j 78

Sempli cazione segnale di controllo per beq e j + CONTROLLO 79

Progetto e realizzazione dell’unit di controllo principale 80

Prestazioni del processore singolo ciclo 81

Esercizi su CPU a singolo ciclo 83

Esercizio 1 83

Soluzione 83

Esercizio 2— Tema d’esame CALC-A del 14 aprile 2010 84

Caso 1 84

Caso 2 84

Caso 3 84

Processore multiciclo 85

Svantaggi del processore a singolo ciclo 85

Dal processore a singolo ciclo al processore multiciclo 85

Vantaggi del processore multiciclo 85

Realizzazione di un processore multiciclo — Concetti fondamentali 85

Linee guida per l’e cienza 86

6

fi fi

fi fi ffi fl à

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Il caso MIPS 86

Assunzione fondamentale 86

Conseguenza 86

Speci ca progressiva del datapath 86

I ciclo — Prelievo dell’istruzione 87

II ciclo — Decodi ca e caricamento registri 88

III ciclo 89

IV ciclo 91

Memorizza parola (sw) 91

Carica parola (lw) 92

V ciclo — Completamento lettura da memoria (lw) 92

Realizzazione Unit di Controllo con macchina a stati niti di Moore 94

Illustrazione esecuzione istruzioni 94

Esecuzione in una CPU multiciclo di una istruzione di Tipo-R 94

Esecuzione in una CPU multiciclo di una istruzione lw 95

Esecuzione in una CPU multiciclo di una istruzione beq 96

Prestazioni 96

Espressione dei CPI 97

Periodo di clock nei processori multiciclo 97

Confronto fra prestazioni di processori 97

Relazione fra le prestazioni di 2 processori 97

Annotazioni 98

CPU Multiciclo — Esercizi 99

Prima tipologia — Valutazione delle Prestazioni 99

Esercizio 1 99

Esercizio 2 101

Controllo multi-ciclo «usuale» 101

Soluzione pi e ciente 101

Confronto prestazioni 102

Seconda tipologia — Implementazione di istruzioni nuove 102

Esercizio 3 102

Una prima soluzione 103

Una seconda soluzione 104

Esercizio 4 — Appello CALC-B del 13 luglio 2005 105

Formato di addmem r1, o set(r2) 105

Modi ca al DataPath 105

Esercizio 5 — Appello CALC-A dell’8 aprile 2009 106

Prima analisi — Passi fondamentali exchange r1, r2, o set 106

Formato 107

Idea di base 107

7

fi fi ù ffi fi à ff ff

fi

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Modi ca al datapath exchange r1, r2, o set 107

Esercizio 6 — Appello CALC-A del 25 marzo 2009 108

Formato 108

Idea di base 108

Modi ca al datapath 108

CPU multiciclo — Gestione delle eccezioni 109

Eccezioni 109

Gestione delle eccezioni 109

Modi che al datapath 109

Identi cazione delle due tipologie di eccezioni 110

Modi che al diagramma degli stati niti 110

Tecniche pipeline — Elementi di base 112

Esecuzione delle istruzioni MIPS con multiciclo — Rivisitazione 112

Verso la pipeline 113

Pipeline — Esecuzione delle istruzioni 114

Esecuzione di un’istruzione [ con 4 stadi ] 114

Stadi e registri interstadio 115

Il datapath 116

Prestazioni e suddivisione in stadi 116

5 Stadi di pipeline 117

Problematica 117

Primo stadio — Instruction Fetch 117

Secondo stadio — Instruction Decode 118

Terzo stadio — Execute 119

Quarto stadio — Memory Access 119

Quinto stadio — Write Back 120

Datapath complessivo 121

Il controllo 121

L’idea di base in astratto 121

Il caso MIPS a 5 stadi 122

Diagrammi di rappresentazione e prestazioni nel caso ideale 123

Diagrammi di rappresentazione gra ca della Pipeline 123

Diagramma della pipeline «a pi cicli di clock» — Esempio riferito al MIPS 123

Diagramma della pipeline «a singolo ciclo di clock» 124

Prestazioni per processore con pipeline 124

Esempio 125

La situazione «a regine» 125

Tempo medio di esecuzione, throughput e CPI 126

Pipeline ideale 126

Pipeline in presenza di stalli (vedremo) 126

8

fi

fi

fi

fi fi ù fi

fi ff

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Tecniche Pipeline (elementi di base) — Esercizi 127

Esercizio — Confronto prestazioni pipeline vs. multiciclo 127

Soluzione 127

Tempo medio di CPU nel caso di controllo multi-ciclo 127

Pipeline ideale e confronto prestazioni 127

Appello 3 luglio 2006 — Esercizio 1 [5 punti] 127

Soluzione 128

Tecniche pipeline — Gestione delle criticità e delle eccezioni 130

Pipeline — I problemi 130

Criticità strutturali e stallo 130

Caso 1 — Unità funzionali contese 130

Caso 2 — Più cicli di clock per istruzione 130

Esempio 130

Caso 3 — Miss di cache 131

Esempio 131

Stallo — Concetti generali 131

Realizzazione circuitale 132

Esempio caso 2 — Stallo di due cicli con S=O (istruzione I2) 133

Organizzazione hardware no a questo punto 133

In uenza degli stalli sulle prestazioni 133

Criticità sui dati 134

Tecnica 1 — Gestione dipendenze via software 134

Tecnica 2 — Gestione dipendenze con stallo 134

Realizzazione circuitale 135

Tecnica 3 — Propagazione dei dati 135

Realizzazione circuitale 136

Propagazione in generale 137

Esempio 137

Esempio con pipeline a 6 stadi 138

Il quadro «globale» 138

L’esempio del MIPS 138

Controllo del primo ingresso della ALU — «rs» 140

Unità di gestione criticità MIPS — I compiti 140

Clock in controfase nel register le 142

Unit di rilevazione criticit gestisce solo criticit «carica-e-usa» 142

Quadro riassuntivo [ no ad ora ] 143

Il ruolo del compilatore 143

Esempio tipico 144

Criticità sul controllo 145

Tecnica 1 — Salto ritardato 145

9

fl à fi à

fi fi à

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Esempio — Un solo slot 146

Tecnica 2 — Stallo nella pipeline 147

Tecnica 3 — Predizione di «salto non e ettuato» 147

Esempio — Veri ca + Calcolo indirizzo nel terzo stadio 147

Esempio — Salto eseguito nel terzo stadio 148

Stallo ritardato vs Stallo 148

Tecniche di predizione complesse 148

Gestione delle eccezioni nel caso di controllo con pipeline 148

Gestione delle eccezioni interne 149

Realizzazione 149

Esempio del MIPS [ per la gestione dell’over ow aritmetico ] 150

Esercizi su Pipeline, criticità e prestazioni 151

Esercizio 4, Tema d’esame CALC-B 22 settembre 2005 – Una sola memoria cache per dati e istruzioni 151

Esercizio 1 CALC-B del 23 giugno 2009 [ questo tipo di esercizio c’è sempre, impara a farlo ] 151

Esercizio 152

Esercizio 1, Tema d’esame 2022 153

Esercizio — Criticit sui dati e riordinamento delle operazioni 154

Variante Esercizio 2 — Tema d’esame CALC-B 14 apr 2010 154

Propagazione solo verso E 155

Propagazione verso E+M 155

Esercizio – Criticit sui salti, stallo e propagazione 156

Esercizio – Condizionale e riordino delle istruzioni 156

Esercizio – Cicli e riordino delle istruzioni 157

Esercizio — Prestazioni con criticit sui salti e stallo 158

Esercizio — Salto ritardato e calcolo prestazioni 158

Esercizio — Predizione di «salto non eseguito» e prestazioni 158

Confronto prestazioni pipeline vs. multiciclo — Speedup 159

Gerarchie di memorie — Memorie Cache 160

Semplice classi cazione delle memorie 160

Memorie non volatili 160

Memorie volatili 160

Il principio di localit 160

Localit spaziale 160

Localit temporale 160

L’idea di base 160

Hit e miss 160

Parametri che determinano prestazioni della memoria cache 161

Frequenza di hit (hit rate) e Frequenza di miss (miss rate) 161

Tempo di hit 161

Tempo di miss [ e penalit di miss ] 161

10

à

à fi

fi à à à à à ff fl

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Tempo medio di accesso alla memoria — Average Memory Access Time 161

Esempio 161

Organizzazione della cache 161

Il problema del piazzamento del blocco 161

Cache completamente associativa 162

Caso generale —Blocchi [ memoria centrale e cache ] di byte 163

Organizzazione 163

Esempio 163

Cache a corrispondenza diretta — Direct mapped 164

Esempio 165

Cache set-associativa a n vie 167

Nota — O set di parola e di byte 167

Una visione di insieme — Diversi gradi di associativit 167

Una visione di insieme — Indirizzi 168

Il problema della sostituzione del blocco 168

Il problema della coerenza dei dati 169

Lettura e scrittura in cache 169

Lettura [ non genera inconsistenze ] 169

Scrittura [ con write-through ] 169

Scrittura [ con write-back ] 170

Trasferimento da dispositivo a memoria DRAM 170

Trasferimento da memoria DRAM a dispositivo 170

Prestazioni — Valutazione qualitativa 171

Impatto della cache su prestazioni 171

Cache multilivello 171

Esempio — Intel Core i7 172

Gerarchia di memorie 172

Appendice 172

Memorie — Forma 172

Esempio 172

Memorie a sola lettura vs. Volatili 172

Memorie a sola lettura 172

Memorie volatili 173

Alcuni valori di riferimento [ solo indicativi ] 173

Esempio: schema con 256 blocchi di 16 parole [ ciascuna di 4 byte ] 173

Cache set-associativa a 4 vie [ 256 insiemi ] con blocchi di 1 parola 174

Esercizi su Memoria cache 175

Esercizio 1, Tema Esame 30.08.2010 175

Esercizio 2, Tema Esame 30.08.2010 175

Pipeline 175

11

ff à

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

Multiciclo 175

Confronto 175

Esercizio 2, Tema Esame 29.06.2010 176

E 176

E + M 176

Nota 176

Esercizio 4 176

Solo cache L1 176

Cache L1 + L2 176

12

Martina Contestabile Ingegneria Informatica — II anno A.A. 2021/22

INTRODUZIONE AL CORSO

Calcolatore — Concetto e modelli

Il calcolatore è un esecutore universale di programmi, ovvero

algoritmi espressi in linguaggio di programmazione. I calcolatori

sici che oggi conosciamo sono stati preceduti da calcolatori

teorici, come la macchina di Turing, che hanno permesso di

sviluppare le macchine che conosciamo oggi giorno. Ci sono stati

sforzi indipendenti per dare una modellizzazione matema