Calcolatori Elettronici

Calcolatori elettronici

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

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

Indice del corso

• 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
• Specifica e realizzazione di reti combinatorie 17
• Espressioni (formule) booleane 18
• Come passare da una specifica 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
• Semplificazione 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 indifferenza 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
• Decodificatori (decoder) 24
• Multiplexer 24
• Un’applicazione del multiplexer 25
• Esercizi su reti combinatorie 26
• Esercizio da tema d’esame 26
• Svolgimento 26

2fi fifi ff fi

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

Reti sequenziali

• 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-flop 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
• Specifica 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
• Codifica 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
• Codifica degli stati 39

3flfifi 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 caffè 40
• Codifica 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 caffè 41
• Brevi richiami su codifica binaria dei numeri interi 42
• Codifica binaria 42
• Codifica binaria di numeri naturali 42
• Esempio 42
• Esempio 42
• Codifica 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

• 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

4fifififi 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
• Codifica delle istruzioni immediate 54
• Indirizzamento immediato 54
• Codifica delle istruzioni di trasferimento 54
• Indirizzamento tramite base o spiazzamento 54
• Codifica 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

• 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

5fififi

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 overflow 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

• CPU a singolo ciclo 71
• Schema del processore (e memoria) 71
• Temporizzazione 72
• Progettazione Datapath — Caso MIPS 72
• Codifica delle istruzioni viste 72
• Note sulla codifica 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
• Semplificazione segnale di controllo per beq — senza j 78
• Semplificazione 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

• 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’efficienza 86

6fi fifi fi ffi fl à

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

• Il caso MIPS 86
• Assunzione fondamentale 86
• Conseguenza 86
• Specifica progressiva del datapath 86
• I ciclo — Prelievo dell’istruzione 87
• II ciclo — Decodifica 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 finiti 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 ed esercizi

• CPU Multiciclo — Esercizi 99
• Prima tipologia — Valutazione delle Prestazioni 99
• Esercizio 1 99
• Esercizio 2 101
• Controllo multi-ciclo «usuale» 101
• Soluzione più efficiente 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, offset(r2) 105
• Modifica al DataPath 105
• Esercizio 5 — Appello CALC-A dell’8 aprile 2009 106
• Prima analisi — Passi fondamentali exchange r1, r2, offset 106
• Formato 107
• Idea di base 107

7fi fi ù ffi fi à ff fffi

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

• Modifica al datapath exchange r1, r2, offset 107
• Esercizio 6 — Appello CALC-A del 25 marzo 2009 108
• Formato 108
• Idea di base 108
• Modifica al datapath 108

CPU multiciclo e gestione delle eccezioni

• CPU multiciclo — Gestione delle eccezioni 109
• Eccezioni 109
• Gestione delle eccezioni 109
• Modifiche al datapath 109
• Identificazione delle due tipologie di eccezioni 110
• Modifiche al diagramma degli stati finiti 110

Tecniche pipeline

• 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 grafica 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 regime» 125
• Tempo medio di esecuzione, throughput e CPI 126
• Pipeline ideale 126
• Pipeline in presenza di stalli (vedremo) 126

8fifififi fi ù fifi ff

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

Tecniche pipeline ed esercizi

• 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

Gestione delle criticità e delle eccezioni

• 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 fino a questo punto 133
• Influenza 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 file 142
• Unità di rilevazione criticità gestisce solo criticità «carica-e-usa» 142
• Quadro riassuntivo [ fino ad ora ] 143
• Il ruolo del compilatore 143
• Esempio tipico 144
• Criticità sul controllo 145
• Tecnica 1 — Salto ritardato 145

9fl à 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 effettuato» 147
• Esempio — Verifica + 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’overflow aritmetico ] 150

Esercizi su pipeline, criticità e prestazioni

• 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 e memorie cache

• Gerarchie di memorie — Memorie Cache 160
• Semplice classificazione 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àà fifi à à à à à 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 — Offset 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

11ff à

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 fisici che oggi conosciamo sono stati preceduti da calcolatori teorici, come la macchina di Turing, che hanno permesso di sviluppare le macchine che conosciamo oggigiorno. Ci sono stati sforzi indipendenti per dare una modellizzazione matema