FormularioArchitettura degli Elaboratori: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Struttura del calcolatore

Architettura e organizzazione di un calcolatore

Definizione (architettura e organizzazione)

	Architettura	Organizzazione
Che cos'è	gli attributi visibili al programmatore, che influenzano l'esecuzione logica di un programma	le unità operative e le loro connessioni che realizzano l'architettura
Esempi	insieme delle istruzioni, numero di bit per i dati, modalità di indirizzamento, meccanismi di I/O	segnali di controllo, tecnologia della memoria, interfacce con le periferiche, circuiti usati
Domanda tipo	c'è un'istruzione di moltiplicazione?	la moltiplicazione è fatta da un circuito dedicato o da somme ripetute?

Definizione (macchina di von Neumann). I primi calcolatori (ENIAC, 1946) si programmavano cambiando i collegamenti: programma cablato. L'idea di von Neumann è un hardware generico che esegue operazioni diverse a seconda dei segnali di controllo ricevuti, e di scrivere questi comandi come istruzioni memorizzate in memoria insieme ai dati (programma memorizzato).

Caratteristiche:

1. dati e istruzioni nella stessa memoria, scrivibile e leggibile;
2. la memoria è indirizzata per posizione, indipendentemente dal contenuto;
3. le istruzioni si eseguono in sequenza, salvo salti espliciti.

Legge di Moore: il numero di transistor integrabili su un chip raddoppia a intervalli regolari (circa ogni 18–24 mesi). Componenti più piccoli e vicini significano segnali che percorrono distanze minori (sono limitati dalla velocità della luce), quindi clock più alti, consumi minori per operazione e costo minore.

Ciclo fetch-execute

Definizione (ciclo fetch-execute)

1. Fetch (prelievo): $\text{MAR} \leftarrow \text{PC}$; la memoria legge; $\text{MBR} \leftarrow M[\text{MAR}]$; $\text{IR} \leftarrow \text{MBR}$; $\text{PC} \leftarrow \text{PC} +$ lunghezza dell'istruzione (in ARM e MIPS: $+4$ byte).
2. Execute (esecuzione): l'unità di controllo decodifica l'IR e svolge l'azione.

Bus e interconnessione

Proprietà (ampiezza delle linee del bus)

Linee	Cosa trasportano	Effetto della loro ampiezza
dati	i dati e le istruzioni trasferiti	con 32 linee si trasferiscono 4 byte per ciclo; con un bus da 8 bit una parola da 32 bit richiede 4 trasferimenti
indirizzi	la sorgente o la destinazione del dato (cella di memoria o porta di I/O)	con $k$ linee si indirizzano $2^k$ locazioni: 24 linee → 16 M locazioni, 32 linee → 4 G
controllo	comandi e temporizzazione	—

Definizione (temporizzazione sincrona e asincrona del bus)

• Sincrona: un clock comune scandisce gli eventi; ogni operazione dura un numero intero di cicli. Semplice, ma tutti si adeguano al dispositivo più lento.
• Asincrona: un evento segue il precedente tramite segnali di handshake (es. il master alza "lettura", lo slave risponde "dato pronto"). Dispositivi lenti e veloci convivono.

II. Rappresentazione dell'informazione

Sistemi di numerazione posizionali

Definizione (notazione posizionale in base $b$). In base $b$ si usano le cifre $0, \dots, b-1$ e ogni cifra pesa una potenza di $b$ che dipende dalla posizione:

$$(c_{n-1} \dots c_1 c_0 , c_{-1} \dots c_{-m})_b = \sum_{i=-m}^{n-1} c_i \, b^i$$

Proprietà (conversione della parte intera per divisioni successive). Divisioni successive per $b$: i resti, letti dall'ultimo al primo, sono le cifre da sinistra a destra. Funziona perché $N = q \cdot b + c_0$: il primo resto è la cifra meno significativa.

Proprietà (conversione della parte frazionaria per moltiplicazioni successive). Moltiplicazioni successive per $b$: a ogni passo la parte intera del prodotto è la cifra successiva dopo la virgola, e si prosegue con la sola parte frazionaria.

Proprietà (conversione tra basi potenze di 2). Poiché $8 = 2^3$ e $16 = 2^4$, ogni cifra ottale corrisponde a 3 bit e ogni cifra esadecimale a 4 bit. Si raggruppano i bit a partire dalla virgola (a sinistra per la parte intera, a destra per la frazionaria), completando con zeri.

Rappresentazione dei numeri interi con segno

Definizione (modulo e segno). Il bit più significativo è il segno (0 = positivo, 1 = negativo), gli altri $n-1$ bit sono il modulo.

Definizione (complemento a 1). Il negativo $-x$ si ottiene invertendo tutti i bit di $x$.

Definizione (complemento a 2). È la rappresentazione usata da tutti i processori. Il bit più significativo ha peso negativo:

$$x = -c_{n-1}\, 2^{n-1} + \sum_{i=0}^{n-2} c_i \, 2^i$$

Equivalentemente: un negativo $-x$ è rappresentato dal numero senza segno $2^n - x$.

Proprietà (opposto in complemento a 2). Opposto (vale in entrambi i versi): si invertono tutti i bit e si somma 1.

$$+20 = 0001\,0100 \ \xrightarrow{\text{inverto}}\ 1110\,1011 \ \xrightarrow{+1}\ 1110\,1100 = -20$$

Proprietà (estensione del segno). Per passare da $n$ a $m > n$ bit si replica il bit di segno a sinistra: $-20$ su 8 bit $1110\,1100$ diventa su 16 bit $1111\,1111\,1110\,1100$; $+20$ diventa $0000\,0000\,0001\,0100$. Serve per esempio quando il processore carica un byte con segno in un registro a 32 bit.

Definizione (rappresentazione in eccesso K). Si memorizza $x + K$ come intero senza segno; di solito $K = 2^{n-1}$ o $2^{n-1}-1$.

Aritmetica binaria

Definizione (somma binaria). In colonna come in base 10, con le regole $0+0=0$, $0+1=1$, $1+1=0$ con riporto 1, $1+1+1 = 1$ con riporto 1.

Formula (sottrazione in complemento a 2). $a - b = a + (-b)$: si calcola l'opposto di $b$ (inverti i bit, +1; vedi 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 →) e si somma. In hardware: si invertono i bit di $b$ e si porta a 1 il riporto in ingresso del sommatore, così non serve un sottrattore.

Proprietà (overflow con e senza segno). Il risultato non sta negli $n$ bit. La regola dipende da come si interpretano i bit:

Interpretazione	Overflow quando	Bit che lo segnala
senza segno	esce un riporto dal MSB nella somma (nella sottrazione: manca il prestito)	C (carry)
complemento a 2	due operandi dello stesso segno danno un risultato di segno opposto	V (overflow)

Sommando due numeri di segno diverso non c'è mai overflow in complemento a 2. Equivalente: $V =$ riporto entrante nel MSB $\oplus$ riporto uscente dal MSB.

Proprietà (algoritmo di Booth). Si esaminano le coppie $(Q_0, Q_{-1})$ con $Q_{-1}$ inizialmente 0:

$Q_0\,Q_{-1}$	Azione
1 0	$A \leftarrow A - M$
0 1	$A \leftarrow A + M$
0 0, 1 1	niente

poi scorrimento aritmetico a destra di A, Q, $Q_{-1}$. Una sequenza di 1 consecutivi nel moltiplicatore costa una sottrazione all'inizio e una somma alla fine invece di una somma per bit.

Definizione (divisione senza segno). Senza segno, come in colonna: a ogni passo si prova a sottrarre il divisore dal resto parziale; se il risultato è $\ge 0$ il bit del quoziente è 1, altrimenti è 0 e si ripristina il resto. Esempio $13 : 3$: $1101 : 11$ → quoziente $100 = 4$, resto $1$.

Definizione (scorrimenti logici, aritmetici e rotazioni)

Operazione	Effetto	Esempio su 8 bit
shift logico a sinistra di $k$	moltiplica per $2^k$ (se non c'è overflow)	$0000\,0101 \ll 2 = 0001\,0100$ (5 → 20)
shift logico a destra di $k$	divide per $2^k$ un senza segno (entra 0)	$1111\,0000 \gg 1 = 0111\,1000$ (240 → 120)
shift aritmetico a destra di $k$	divide per $2^k$ un numero in complemento a 2 (entra il bit di segno), arrotondando verso $-\infty$	$1111\,0000 \gg 1 = 1111\,1000$ (−16 → −8)
rotazione	i bit che escono rientrano dall'altro lato	$1000\,0001 \to 0000\,0011$ (a sinistra)

Numeri in virgola mobile IEEE 754

Definizione (normalizzazione). Un numero si normalizza spostando la virgola finché resta una sola cifra 1 a sinistra: $1101{,}01 = 1{,}10101 \cdot 2^3$; $0{,}00101 = 1{,}01 \cdot 2^{-3}$.

Formula (valore di un numero IEEE 754)

$$x = (-1)^S \cdot 1{,}M \cdot 2^{\,E - \text{bias}}$$

Formato	Bit	Segno $S$	Esponente $E$	Mantissa $M$	Bias	Cifre decimali
singola precisione	32	1	8	23	127	≈ 7
doppia precisione	64	1	11	52	1023	≈ 16

Proprietà (valori speciali IEEE 754)

Esponente $E$	Mantissa $M$	Significato
$0$	$0$	$\pm 0$
$0$	$\neq 0$	denormalizzato: $(-1)^S \cdot 0{,}M \cdot 2^{-126}$
$1 \dots 254$	qualsiasi	normalizzato
$255$ (tutti 1)	$0$	$\pm\infty$ (es. $1/0$, overflow)
$255$	$\neq 0$	NaN (es. $0/0$, $\sqrt{-1}$)

Formula (massimo e minimo normalizzato in singola precisione)

• Massimo normalizzato: $(2 - 2^{-23}) \cdot 2^{127} \approx 3{,}4 \cdot 10^{38}$.
• Minimo normalizzato positivo: $2^{-126} \approx 1{,}18 \cdot 10^{-38}$.

Formula (distanza tra float consecutivi)

• Distanza tra due float consecutivi con esponente $e$: $2^{e-23}$. Vicino a 1 è $2^{-23} \approx 1{,}2 \cdot 10^{-7}$ (epsilon di macchinadistanza tra 1 e il float successivo); vicino a $2^{24} \approx 1{,}7 \cdot 10^7$ è 2: da lì in poi non tutti gli interi sono rappresentabili.

Codifiche binarie e informazione non numerica

Formula (bit per codificare $N$ oggetti)

• Con $n$ bit si codificano $2^n$ oggetti distinti; per $N$ oggetti servono $\lceil \log_2 N \rceil$ bit (26 lettere → 5 bit).

Formula (bit di indirizzo di una memoria). Per memorie e indirizzi si usano le potenze di 2 (spesso scritte K, M, G). Conti tipici: $16\ \text{MB} = 2^4 \cdot 2^{20} = 2^{24}$ byte, quindi servono 24 bit di indirizzo se ogni byte ha il suo indirizzo; $4\ \text{GB} = 2^{32}$ byte → 32 bit.

Definizione (codice BCD). BCD (Binary Coded Decimal): ogni cifra decimale su 4 bit. $259 = 0010\,0101\,1001_{\text{BCD}}$ (in binario puro sarebbe $1\,0000\,0011$). Spreca 6 configurazioni su 16 ma evita le conversioni: si usa in display e calcolatrici.

Formula (codice Gray). Codice Gray: due numeri consecutivi differiscono per un solo bit. Si ottiene da $b$ binario come $g = b \oplus (b \gg 1)$.

Definizione (ASCII, Unicode e UTF-8)

• ASCII: 7 bit, 128 simboli. '0'–'9' = 48–57 (0x30–0x39), 'A' = 65 (0x41), 'a' = 97 (0x61). Maiuscola e minuscola differiscono solo per il bit 5 (valore 32); la cifra $d$ ha codice $48 + d$.
• Unicode: assegna un numero (code point) a ogni carattere di tutte le scritture, da U+0000 a U+10FFFF.
• UTF-8: codifica i code point in 1–4 byte; i caratteri ASCII restano su 1 byte identico. 'è' = U+00E8 → 2 byte C3 A8.

Definizione (little e big endian). Una parola di 4 byte occupa 4 indirizzi consecutivi. Per 0x12345678 all'indirizzo 100:

Indirizzo	100	101	102	103
Big endian (byte più significativo all'indirizzo minore)	12	34	56	78
Little endian (byte meno significativo all'indirizzo minore)	78	56	34	12

Definizione (bit di parità). Bit di parità ($k = 1$): si sceglie il bit in modo che il numero totale di 1 sia pari. Rileva un numero dispari di errori, non li corregge. Dati $1011\,0010$ (quattro 1) → parità 0.

Formula (bit di controllo del codice di Hamming). Codice di Hamming (correzione di un errore singolo, SEC). Servono $k$ bit di controllo con

$$2^k - 1 \ge m + k$$

perché la sindrome di $k$ bit deve distinguere "nessun errore" e ciascuna delle $m + k$ posizioni.

Definizione (sindrome di Hamming)

3. In lettura si ricalcolano i bit di controllo dai dati letti e si fa lo XOR con quelli memorizzati: la sindrome. Se è $0$ non ci sono errori; altrimenti il suo valore è la posizione del bit sbagliato, che si inverte.

III. Reti logiche

Algebra di Boole e porte logiche

Definizione (porte AND, OR, NAND, NOR, XOR e XNOR)

$A$	$B$	AND $AB$	OR $A+B$	NAND $\overline{AB}$	NOR $\overline{A+B}$	XOR $A \oplus B$	XNOR $\overline{A\oplus B}$
0	0	0	0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

Proprietà (algebra di Boole e De Morgan)

Proprietà	Forma AND	Forma OR
identità	$A \cdot 1 = A$	$A + 0 = A$
elemento nullo	$A \cdot 0 = 0$	$A + 1 = 1$
idempotenza	$AA = A$	$A + A = A$
complemento	$A\overline{A} = 0$	$A + \overline{A} = 1$
commutativa	$AB = BA$	$A + B = B + A$
associativa	$(AB)C = A(BC)$	$(A+B)+C = A+(B+C)$
distributiva	$A(B + C) = AB + AC$	$A + BC = (A+B)(A+C)$
assorbimento	$A(A + B) = A$	$A + AB = A$
De Morgan	$\overline{AB} = \overline{A} + \overline{B}$	$\overline{A+B} = \overline{A}\,\overline{B}$

Proprietà (completezza della NAND). {AND, OR, NOT} basta per scrivere qualsiasi funzione (vedi le forme canoniche in 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 →). Anche la sola NAND basta, e così la sola NOR:

• NOT: $\overline{A} = \overline{AA}$ (NAND con gli ingressi uniti);
• AND: $AB = \overline{\overline{AB}}$ (NAND seguita da un NOT fatto con NAND);
• OR: $A + B = \overline{\overline{A}\,\overline{B}}$ (De Morgan: NAND degli ingressi negati).

Reti combinatorie e mappe di Karnaugh

Definizione (mintermine, SOP, maxtermine e POS)

• Mintermine: prodotto (AND) di tutte le variabili, dirette o negate, che vale 1 su una sola riga. Per la riga $A=0, B=1, C=1$ è $\overline{A}BC$ ($m_3$, dal numero binario 011).
• Somma di prodotti (SOP): OR dei mintermini delle righe in cui $F = 1$.
• Maxtermine: somma (OR) che vale 0 su una sola riga: per $A=0,B=1,C=1$ è $A + \overline{B} + \overline{C}$.
• Prodotto di somme (POS): AND dei maxtermini delle righe in cui $F = 0$.

Definizione (mappa di Karnaugh e regole di raggruppamento). La tabella di verità disposta in una griglia in cui righe e colonne seguono il codice Gray (00, 01, 11, 10): due celle adiacenti differiscono per una sola variabile, e sono adiacenti anche i bordi opposti (la mappa "si chiude" a cilindro e a toro).

Regole:

1. si raggruppano gli 1 in rettangoli di 1, 2, 4, 8, … celle adiacenti (potenze di 2);
2. gruppi più grandi possibile e meno gruppi possibile; un 1 può stare in più gruppi;
3. ogni gruppo dà un prodotto con le sole variabili che non cambiano nel gruppo; un gruppo di $2^k$ celle elimina $k$ variabili.

Proprietà (condizioni di indifferenza e POS). Se alcune combinazioni di ingresso non possono presentarsi (es. i codici 1010–1111 in BCD), in quelle celle si mette una X (don't care) e si usa come 1 o 0, a seconda di cosa allarga i gruppi.

Per la forma POS si raggruppano gli 0 nello stesso modo e si scrive il prodotto di somme (variabile negata se nel gruppo vale 1).

Proprietà (ritardo di una SOP). Una SOP si realizza con due livelli di porte (AND poi OR): il ritardo è di circa due porte, qualsiasi sia la funzione. Semplificare riduce il numero di porte e di ingressi, cioè area e consumo. Con molte variabili (più di 5–6) le mappe diventano scomode e si usano algoritmi (Quine-McCluskey, strumenti di sintesi).

Circuiti combinatori notevoli

Formula (multiplexer 2:1). Sceglie uno tra $2^n$ ingressi dati in base a $n$ ingressi di selezione. MUX 2:1:

$$Y = \overline{S}\,I_0 + S\,I_1$$

Formula (multiplexer 4:1). MUX 4:1 con selezione $S_1S_0$: $Y = \overline{S_1}\,\overline{S_0} I_0 + \overline{S_1}S_0 I_1 + S_1\overline{S_0} I_2 + S_1 S_0 I_3$. Con un MUX a $2^n$ ingressi si realizza qualsiasi funzione di $n$ variabili, mettendo sugli ingressi dati i valori della tabella di verità. Un MUX a 32 bit sono 32 MUX in parallelo con la stessa selezione: nel datapath sceglie per esempio se il secondo operando dell'ALU è un registro o una costante.

Definizione (decoder ed encoder)

• Decoder $n \to 2^n$: attiva una sola delle $2^n$ uscite, quella il cui numero è l'ingresso. Decoder 2→4: $D_0 = \overline{A_1}\,\overline{A_0}$, $D_1 = \overline{A_1}A_0$, $D_2 = A_1\overline{A_0}$, $D_3 = A_1A_0$. Usi: selezionare la cella di memoria o il chip dall'indirizzo, il registro di destinazione dal campo dell'istruzione.
• Encoder $2^n \to n$: l'inverso, dà il numero dell'unico ingresso attivo. L'encoder con priorità dà il numero dell'ingresso attivo più importante (usato per scegliere tra più richieste di interrupt).

Formula (semisommatore). Semisommatore (half adder): somma due bit.

$$S = A \oplus B \qquad C = AB$$

Formula (sommatore completo)

$$S = A \oplus B \oplus C_{in} \qquad C_{out} = AB + C_{in}(A \oplus B) = AB + AC_{in} + BC_{in}$$

Formula (ritardo del sommatore a propagazione del riporto). Sommatore a propagazione del riporto (ripple carry) a $n$ bit: $n$ full adder in cascata, il $C_{out}$ di ognuno è il $C_{in}$ del successivo. Il bit $i$ è corretto solo quando è arrivato il riporto dal bit $i-1$: il ritardo cresce linearmente con $n$ (circa $2n$ porte). Se una porta ritarda 20 ps, a 32 bit servono circa $64 \cdot 20 = 1280$ ps, cioè più di un ciclo di un clock a 1 GHz.

Definizione (anticipo del riporto). Anticipo del riporto (carry lookahead): si definiscono per ogni bit $g_i = A_iB_i$ (il bit genera un riporto) e $p_i = A_i + B_i$ (lo propaga), e si calcolano i riporti direttamente dagli ingressi:

$$c_1 = g_0 + p_0c_0, \quad c_2 = g_1 + p_1g_0 + p_1p_0c_0, \quad \dots$$

Proprietà (sommatore-sottrattore). Un solo sommatore fa anche la sottrazione in complemento a 2 (vedi 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 →): ogni bit di $B$ passa per una XOR con il segnale $\text{SUB}$, che è anche il riporto iniziale.

• $\text{SUB} = 0$: $B \oplus 0 = B$, $c_0 = 0$ → $A + B$.
• $\text{SUB} = 1$: $B \oplus 1 = \overline{B}$, $c_0 = 1$ → $A + \overline{B} + 1 = A - B$.

Formula (overflow in complemento a 2). Overflow (complemento a 2): $V = c_n \oplus c_{n-1}$, XOR tra il riporto che entra e quello che esce dal bit di segno.

Formula (comparatore di uguaglianza). Uguaglianza di due numeri di $n$ bit: $E = \overline{(A_0 \oplus B_0) + (A_1 \oplus B_1) + \dots}$, cioè NOR delle XOR bit a bit. Il confronto di ordine si fa di solito con una sottrazione guardando i flag N, Z, C, V.

Latch e flip-flop

Definizione (latch SR). Due porte NOR incrociate: $Q = \overline{R + \overline{Q}}$, $\overline{Q} = \overline{S + Q}$.

$S$	$R$	$Q_{t+1}$	Effetto
0	0	$Q_t$	mantiene lo stato (memoria)
1	0	1	set
0	1	0	reset
1	1	—	proibito: entrambe le uscite a 0, e al ritorno a 00 lo stato è imprevedibile

Definizione (latch D). Latch D (data): un solo ingresso, $S = D$ e $R = \overline{D}$, così lo stato proibito non può presentarsi.

Definizione (flip-flop D master-slave). Cambia stato solo sul fronte del clock (di salita o di discesa). Realizzazione master-slave: due latch D in cascata con clock opposti.

• $C = 1$: il master è trasparente e segue $D$; lo slave è bloccato.
• Quando $C$ scende: il master si blocca e lo slave copia il suo valore.

Risultato: $Q$ prende il valore che $D$ aveva all'istante del fronte, e resta fermo per tutto il ciclo.

$$Q_{t+1} = D_t$$

Formula (flip-flop JK). Il JK è un SR in cui la combinazione 11 fa commutare lo stato invece di essere proibita: $Q_{t+1} = J\overline{Q_t} + \overline{K}Q_t$.

Formula (flip-flop T). Il flip-flop T (toggle) è un JK con $J = K = T$: se $T = 1$ commuta a ogni fronte, se $T = 0$ mantiene. $Q_{t+1} = T \oplus Q_t$. È la base dei 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 →.

Formula (periodo minimo di clock). In un sistema sincrono tutti i flip-flop ricevono lo stesso clock. Tra due flip-flop c'è una rete combinatoria: il segnale deve attraversarla prima del fronte successivo.

$$T_{clock} \ge t_{clk \to Q} + t_{combinatoria,\max} + t_{setup}$$

Reti sequenziali e automi a stati finiti

Definizione (rete sequenziale sincrona). Una rete sequenziale sincrona è fatta di:

• un registro di stato di $k$ flip-flop D (vedi 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 →), che può ricordare fino a $2^k$ stati;
• una rete combinatoria di stato prossimo: dagli ingressi $X$ e dallo stato attuale $S$ calcola $S' = \delta(S, X)$;
• una rete combinatoria di uscita $Z$.

A ogni fronte del clock lo stato diventa $S'$. Il comportamento si descrive con un automa a stati finiti (diagramma degli stati: un nodo per stato, un arco per ogni transizione etichettato con l'ingresso).

Definizione (automi di Moore e di Mealy)

Tipo	Uscita	Conseguenza
Moore	dipende solo dallo stato: $Z = \lambda(S)$	uscita stabile per tutto il ciclo, cambia solo dopo il fronte
Mealy	dipende da stato e ingressi: $Z = \lambda(S, X)$	di solito servono meno stati, ma l'uscita risente subito degli ingressi

Proprietà (procedimento di sintesi)

1. Diagramma degli stati dalla specifica.
2. Tabella degli stati (stato attuale, ingresso → stato prossimo, uscita).
3. Codifica degli stati in binario ($k = \lceil \log_2 N \rceil$ flip-flop per $N$ stati).
4. Tabella di verità delle funzioni di stato prossimo e di uscita, semplificazione con le 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 →.
5. Disegno: flip-flop + reti combinatorie.

Formula (riconoscitore di due 1 consecutivi)

$$Q_1' = X(Q_1 + Q_0) \qquad Q_0' = X\,\overline{Q_1}\,\overline{Q_0} \qquad Z = Q_1$$

Registri e contatori

Definizione (registro parallelo con Load). $n$ flip-flop D (vedi 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 →) con lo stesso clock memorizzano una parola di $n$ bit. Per caricare solo quando serve si aggiunge un segnale Load: davanti a ogni flip-flop un multiplexerMultiplexer, 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 → sceglie tra il nuovo dato (Load = 1) e il valore attuale $Q$ (Load = 0). PC, IR, MAR, MBR sono registri di questo tipo.

Definizione (registro a scorrimento). L'uscita di ogni flip-flop è l'ingresso del successivo: a ogni fronte il contenuto scorre di una posizione.

Definizione (contatore asincrono ripple). Contatore asincrono (ripple): flip-flop T con $T = 1$; il clock del primo è il clock del sistema, quello di ognuno dei successivi è l'uscita del precedente. Semplice, ma i bit cambiano uno dopo l'altro: per un attimo compaiono valori intermedi sbagliati, e il ritardo cresce con il numero di bit.

Formula (contatore sincrono). Contatore sincrono: tutti i flip-flop hanno lo stesso clock. Il bit $i$ commuta quando tutti i bit meno significativi valgono 1:

$$T_0 = 1, \quad T_1 = Q_0, \quad T_2 = Q_1Q_0, \quad T_3 = Q_2Q_1Q_0$$

Proprietà (contatore modulo N). Per contare da 0 a $N-1$ si riporta a zero il contatore quando arriva a $N - 1$ (sincrono) o si progetta come automa (vedi 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 →).

Formula (frequenza del bit $Q_i$ di un contatore). Usi: contatore di programma (il PC è un registro con incremento), divisori di frequenza (il bit $Q_i$ di un contatore binario ha frequenza $f_{clock}/2^{i+1}$), temporizzatori.

IV. Architettura del processore

Struttura interna della CPU e registri

Proprietà (numero di registri e bit nell'istruzione). Più registri significa meno accessi alla memoria, ma più bit nell'istruzione per indicarli (con 16 registri servono 4 bit per operando, con 32 ne servono 5) e più stato da salvare a ogni chiamata o interruzione. Le architetture RISC ne hanno tipicamente 16–32 (vedi 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 →); ARM a 32 bit ne ha 16, MIPS 32.

Formula (ampiezza dei registri e spazio di indirizzamento). Ampiezza: i registri per gli indirizzi devono contenere un indirizzo intero: con registri a 32 bit si indirizzano $2^{32}$ byte = 4 GB, a 64 bit $2^{64}$.

Definizione (parola di stato PSW). Contenuto tipico della PSW:

• flag: N (segno, bit più significativo del risultato), Z (zero), C (riporto), V (overflow) — vedi 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 →;
• abilitazione delle interruzioni;
• bit di supervisore (modo privilegiato): indica se la CPU sta eseguendo codice del sistema operativo. Solo in questo modo sono permesse le istruzioni privilegiate (gestione della memoria, I/O, modifica della PSW stessa); un programma utente che le tenta provoca un'eccezione.

Instruction Set Architecture

Definizione (ISA). L'insieme delle istruzioni (ISA, Instruction Set Architecture) è il confine tra hardware e software: è tutto ciò che un programma in linguaggio macchina può usare. Due processori con la stessa ISA eseguono lo stesso codice, anche se sono organizzati in modo diverso (vedi 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 →).

Definizione (istruzioni a 0, 1, 2 e 3 indirizzi). Quanti operandi espliciti ha un'istruzione aritmetica. Esempio: $Y = (A - B) / (C + D \cdot E)$, variabili in memoria.

Definizione (architettura load/store). In ARM e MIPS solo le istruzioni di load e store accedono alla memoria; tutte le operazioni aritmetiche e logiche lavorano tra registri. Lo stesso calcolo in ARM (variabili già caricate in r1–r5):

SUB r0, r1, r2      @ r0 = A - B
MUL r6, r4, r5      @ r6 = D * E
ADD r6, r6, r3      @ r6 = C + D*E
SDIV r0, r0, r6     @ r0 = Y (SDIV esiste solo nelle versioni più recenti dell'ISA)

Formato delle istruzioni e modalità di indirizzamento

Definizione (modalità di indirizzamento). L'indirizzo effettivo (EA) è l'indirizzo in memoria dell'operando. Notazione: $A$ = campo indirizzo dell'istruzione, $R$ = registro indicato, $(X)$ = contenuto di $X$.

Modalità	Operando	Pro	Contro
immediato	$A$ stesso	nessun accesso alla memoria	valore limitato dai bit del campo
diretto	$(A)$, EA = $A$	semplice	spazio di indirizzamento limitato dal campo
indiretto	$((A))$, EA = $(A)$	spazio ampio	due accessi alla memoria
a registro	$(R)$	veloce, pochi bit	pochi registri
indiretto a registro	$((R))$, EA = $(R)$	spazio ampio, un solo accesso	serve caricare prima il registro
con spiazzamento (base + offset)	EA = $(R) + A$	flessibile	somma in più
relativo al PC	EA = $(\text{PC}) + A$	codice rilocabile, salti corti	portata limitata
indicizzato e scalato	EA = $(R_b) + (R_i) \cdot s + A$	accesso ad array con elementi di $s$ byte	più complesso
a pila	operando in cima allo stack, implicito	istruzioni corte	accesso solo alla cima

Formula (indice scalato). Indice scalato (es. Pentium): il fattore $s \in \{1, 2, 4, 8\}$ permette di scorrere in modo uniforme array di byte, mezze parole, parole, doppie parole. In ARM: LDR r0, [r1, r2, LSL #2] legge l'elemento r2 di un array di parole che inizia a r1.

Definizione (formato fisso e variabile)

• Formato fisso (RISC: tutte le istruzioni di 32 bit): decodifica semplice e veloce, adatto alla 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 →.
• Formato variabile (x86: da 1 a 15 byte): codice compatto, decodifica complessa.

Definizione (formati MIPS R, I e J)

Formato	Campi (bit)	Uso
R	op (6) · rs (5) · rt (5) · rd (5) · shamt (5) · funct (6)	operazioni tra registri: add $1, $2, $3
I	op (6) · rs (5) · rt (5) · immediato (16)	immediati, load/store, salti condizionati: lw $8, 0x1200($9)
J	op (6) · indirizzo (26)	salto incondizionato

Definizione (formato ARM delle istruzioni di elaborazione dati)

cond (4)	00	I (1)	opcode (4)	S (1)	Rn (4)	Rd (4)	operando 2 (12)

• cond: condizione di esecuzione (tutte le istruzioni ARM a 32 bit possono essere condizionate, vedi 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 →).
• S: se 1 l'istruzione aggiorna i flag.
• Rn, Rd: 4 bit perché i registri sono 16.
• operando 2: un registro eventualmente scalato, oppure (I = 1) una costante di 8 bit ruotata a destra di un numero pari di posizioni (4 bit di rotazione × 2). Per questo MOV r0, #0xFF000000 è codificabile (0xFF ruotato) ma MOV r0, #0x101 no.

Architetture RISC e CISC

Definizione (CISC). Negli anni '70 i linguaggi ad alto livello si allontanavano dal linguaggio macchina (divario semantico). La risposta CISC (Complex Instruction Set Computer, es. VAX, x86): molte istruzioni, molte modalità di indirizzamento, istruzioni che fanno direttamente operazioni da linguaggio ad alto livello (copie di stringhe, chiamate di procedura con salvataggio del contesto). Obiettivi: compilatori più semplici, programmi più corti, più funzioni in microcodice (vedi 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 →).

Definizione (architettura RISC). Reduced Instruction Set Computer (es. MIPS, ARM, RISC-V):

1. un'istruzione per ciclo (a regime, in 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 →);
2. operazioni registro-registro, solo load e store accedono alla memoria (architettura load/store);
3. poche modalità di indirizzamento semplici;
4. formato fisso (32 bit) e pochi formati, decodifica semplice;
5. molti registri (16–32 o più);
6. unità di controllo cablata;
7. il lavoro di ottimizzazione passa al compilatore (allocazione dei registri, riordino delle istruzioni).

Definizione (allocazione dei registri con colorazione di un grafo). Soluzione software: il compilatore assegna le variabili ai registri fisici. Costruisce un grafo in cui ogni nodo è una variabile (o valore temporaneo) e un arco collega due variabili vive contemporaneamente. Assegnare $k$ registri = colorare il grafo con $k$ colori in modo che nodi adiacenti abbiano colori diversi. Le variabili che non si riescono a colorare vengono tenute in memoria (spill).

L'architettura ARM

Definizione (registri ARM a 32 bit). 16 registri da 32 bit visibili, r0–r15:

Registro	Nome	Uso
r0–r3		argomenti e valore di ritorno delle funzioni, temporanei
r4–r11		variabili; vanno preservati dalle funzioni chiamate
r12	IP	temporaneo
r13	SP	stack pointer
r14	LR	link register: indirizzo di ritorno dopo BL
r15	PC	program counter

Definizione (registro di stato CPSR). CPSR (Current Program Status Register): flag N, Z, C, V nei bit 31–28 (vedi 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 →), bit di disabilitazione delle interruzioni, bit del modo corrente.