Un semplice microprocessore - datapath, ALU e register file

Questa nota e la successiva (Un semplice microprocessore - istruzioni, ciclo singolo e cicli multipliIstruzioni a 16 bit: opcode (7 bit) + DR, SA, SB/OP (3 bit ciascuno) oppure formato di salto con offset a 6 bit (AD sinistro + AD destro, relativo al PC e con estensione di segno). Insieme di istruzioni load/store (solo LD e ST accedono ai dati): MOVA, INC, ADD, SUB, ..., LDI, ADI, LD, ST, BRZ, BRN, JMP. Nel computer a ciclo singolo (due memorie separate) il decoder combinatorio ricava MB, MD, RW, MW, PL, JB, BC dai bit 15, 14, 13, 9 dell'istruzione e $FS$ dai bit 12–9; il periodo di clock è la somma dei ritardi lungo il cammino peggiore (9,8 ns nell'esempio). Nel computer a cicli multipli (memoria unica) servono IR, registri interni R8–R15 e un decoder sequenziale: fetch (INF) + uno o più stati di esecuzione.Un semplice microprocessore - istruzioni, ciclo singolo e cicli multipli →) progettano un computer semplificato ma completamente funzionale, mettendo insieme blocchi già visti: registri, sommatori, multiplexer, decoder, memorie, macchine a stati. Per il quadro architetturale generale: 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à 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) →, 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 →.

Un elaboratore è formato da:

• un datapath, capace di eseguire le operazioni usate negli algoritmi (somme, operazioni logiche, ecc.);
• una unità di controllo, che comanda il datapath in base al "programma";
• una memoria, che contiene programma e dati.

Si parte dall'Instruction Set Architecture (ISA), l'interfaccia verso il programmatore (le operazioni di base di cui dispone). Il datapath è definito da un insieme di registri, una lista di microoperazioni e una interfaccia di controllo.

Struttura del datapath

Il datapath generico è costruito con elementi di base: registri, bus, multiplexer, decoder. Elementi:

• register file (registri sorgente e destinazione);
• ALU (circuito combinatorio aritmetico-logico) e shifter; insieme formano la unità funzionale (function unit);
• multiplexer per scegliere gli operandi e il dato in uscita;
• bit di segnalazione (status): V overflow, C carry, N negativo, Z zero.

Le operazioni richiedono un singolo ciclo di clock: per esempio $R_1\leftarrow R_2+R_3$ legge $R_2$ e $R_3$, calcola la somma e la scrive in $R_1$ al fronte di clock successivo.

Register file

Definizione (register file). Un datapath ha tipicamente più di quattro registri (32 o più sono comuni): si realizzano con un register file, memoria veloce che permette un accesso simultaneo a più locazioni. Contiene $2^m\cdot n$ bit, dove $m$ = numero di bit di indirizzo e $n$ = bit di ogni locazione. Qui $m=3$ ($8$ registri $R_0\dots R_7$) e $n=16$. Ha:

• due porte di lettura con indirizzi $AA$ e $BA$ (uscite bus A e bus B);
• una porta di scrittura con indirizzo $DA$, dato D data e abilitazione $RW$ (write).

Esempio. Con $m=3$ e $n=16$ il register file contiene $2^3\cdot16=128$ bit: $8$ registri $R_0\dots R_7$ da $16$ bit.

Il dato sul bus A è anche l'indirizzo della memoria dati (address out), il bus B è il dato da scrivere in memoria (data out). Il secondo operando della unità funzionale passa per un MUX B: con $MB=0$ è il registro (bus B), con $MB=1$ una costante (constant in). All'uscita, un MUX D sceglie con $MD$ tra il risultato $F$ della unità funzionale ($MD=0$) e il dato letto dalla memoria (data in, $MD=1$).

ALU

Definizione (ALU). La ALU (Arithmetic Logic Unit, 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) →) è un circuito combinatorio che esegue un insieme di operazioni aritmetiche e logiche di base, scelte da linee di selezione ($S_2$ = selezione del modo, $S_1S_0$ = operazione, più $C_{in}$). Si progetta dividendola in parte aritmetica e parte logica, poi collegate da un MUX 2-to-1 comandato da $S_2$ ($S_2=0$ aritmetica, $S_2=1$ logica).

Esempio. Con $S_2=1$ e codice $00$ la ALU esegue l'AND: $A=0110$ e $B=0011$ danno $G=0010$.

Formula (parte aritmetica della ALU). Un sommatore ($n$ full adder in cascata, Sommatori binari - half adder, full adder e ripple carryHalf adder (2 ingressi): $S=X\oplus Y$, $C=XY$. Full adder (3 ingressi, con riporto in ingresso $Z$): $S=X\oplus Y\oplus Z$, $C=XY+XZ+YZ=G+PZ$ con $P=X\oplus Y$, $G=XY$; si realizza con due half adder e una OR. Il ripple carry adder a $n$ bit concatena $n$ full adder: il riporto "ondeggia" dal LSB al MSB, quindi il ritardo cresce linearmente con $n$. È un circuito iterativo (gerarchico e regolare). Il moltiplicatore a 2 bit usa 4 AND e 2 half adder.Sommatori binari - half adder, full adder e ripple carry →) con una logica di ingresso su $B$ che produce $Y$ e con riporto in ingresso $C_{in}$: $G=A+Y+C_{in}$.

Esempio. Con $A=0110$, $B=0011$, $Y=\overline B=1100$ e $C_{in}=1$: $G=0110+1100+1=(1)\,0011$, cioè $A-B=3$.

Si ricordi che "tutti 1" è $-1$ in complemento a 2, quindi $A+(-1)=A-1$, e che $A+\overline B+1=A-B$ (Numeri con segno, complemento a 2, sottrazione e overflowSottrazione senza segno: se $M\ge N$ nessun prestito in uscita, altrimenti il risultato $M-N+2^n$ è scorretto. Complemento a 1: $2^n-1-N$ (inversione bit a bit); complemento a 2: $2^n-N=$ complemento a 1 $+1$. Numeri con segno: segno e modulo (due zeri, intervallo simmetrico) oppure complemento a 2 (un solo zero, da $-2^{n-1}$ a $2^{n-1}-1$, MSB di peso $-2^{n-1}$). In complemento a 2 somma e sottrazione sono la stessa addizione: $A-B=A+\overline B+1$, riporto in uscita scartato. Overflow: senza segno $\Leftrightarrow C_{out}=1$ nella somma; con segno $\Leftrightarrow C_{in,MSB}\ne C_{out,MSB}$ (due operandi dello stesso segno con risultato di segno opposto).Numeri con segno, complemento a 2, sottrazione e overflow →). Perché sono possibili solo queste quattro operazioni aritmetiche con due linee: $Y$ vale $0$, $B$, $\overline B$ o $1\dots1$ ed è l'unico ingresso che cambia.

La logica di ingresso può essere un multiplexer, ma conviene una sintesi dedicata. Dalla tabella di verità ($Y_i$ in funzione di $S_1,S_0,B_i$) con la mappa di Karnaugh: $$Y_i=B_i\,S_0+\overline{B_i}\,S_1 .$$ Controllo: $S_1S_0=00\Rightarrow Y_i=0$; $01\Rightarrow Y_i=B_i$; $10\Rightarrow Y_i=\overline{B_i}$; $11\Rightarrow B_i+\overline{B_i}=1$ ✓.

Circuito logico. Per ogni bit un MUX 4-to-1, comandato da un codice a 2 bit, sceglie tra le porte AND, OR, XOR, NOT:

Singolo stadio della ALU = stadio aritmetico + stadio logico + MUX 2-to-1 di uscita.

Funzionalità complessiva (le colonne sono $S_2\,S_1\,S_0\,C_{in}$):

Per la parte logica ($S_2=1$) bastano due bit di codice (00 AND, 01 OR, 10 XOR, 11 NOT) e la colonna $S_1$ è indifferente (X), come nella tabella del corso.

Definizione (bit di stato N, Z, C e V). Dal risultato della unità funzionale: $N$ = bit di segno (MSB del risultato); $Z=1$ se tutti i bit del risultato sono 0 (NOR di tutti i bit); $C$ = riporto in uscita dal sommatore; $V$ = overflow = riporto entrante nel bit di segno XOR riporto uscente (Numeri con segno, complemento a 2, sottrazione e overflowSottrazione senza segno: se $M\ge N$ nessun prestito in uscita, altrimenti il risultato $M-N+2^n$ è scorretto. Complemento a 1: $2^n-1-N$ (inversione bit a bit); complemento a 2: $2^n-N=$ complemento a 1 $+1$. Numeri con segno: segno e modulo (due zeri, intervallo simmetrico) oppure complemento a 2 (un solo zero, da $-2^{n-1}$ a $2^{n-1}-1$, MSB di peso $-2^{n-1}$). In complemento a 2 somma e sottrazione sono la stessa addizione: $A-B=A+\overline B+1$, riporto in uscita scartato. Overflow: senza segno $\Leftrightarrow C_{out}=1$ nella somma; con segno $\Leftrightarrow C_{in,MSB}\ne C_{out,MSB}$ (due operandi dello stesso segno con risultato di segno opposto).Numeri con segno, complemento a 2, sottrazione e overflow →). Esempio a 8 bit: $70+80$ dà $G=10010110$ (150, letto come $-106$) con $V=1$, $C=0$, $N=1$, $Z=0$; $255+1$ dà $G=0$ con $C=1$, $Z=1$, $V=0$, $N=0$.

Esempio. A $4$ bit $0111+0001=1000$: $N=1$, $Z=0$, $C=0$, $V=1$ (overflow in complemento a 2).

Shifter

Di solito lo scorrimento è eseguito da un blocco separato dalla ALU (ma può essere integrato). Shifter a 4 bit con multiplexer: per ogni uscita $H_i$ un MUX 3-to-1 con $S=0$ nessuno shift (passa $B_i$), $S=1$ shift a destra (passa $B_{i+1}$, con ingresso $I_R$ per il bit entrante), $S=2$ shift a sinistra (passa $B_{i-1}$, ingresso $I_L$). Serial output L e R per i bit uscenti.

Barrel shifter a 4 bit: uno shifter con rotazione (i bit che escono da una parte rientrano dall'altra). Ogni uscita è un MUX 4-to-1 le cui ingressi sono i 4 bit dell'operando in ordine ruotato; la selezione $S_1S_0$ determina l'ampiezza della rotazione:

Pregio: lo spostamento di qualsiasi numero di posizioni in un solo ciclo.

Unità funzionale e codici delle microoperazioni

Proprietà (codici FS dell'unità funzionale). L'unità funzionale = ALU + shifter, con un MUX F che sceglie il risultato ($MF$: 0 ALU, 1 shifter). Le microoperazioni possibili sono 15, quindi bastano codici FS a 4 bit invece di far pilotare tutti i 7 segnali di controllo ($MF$, $G_3\dots G_0$, $H_1H_0$) alla unità di controllo: si aggiunge una piccola rete combinatoria che ricava i 7 segnali dal codice $FS$.

Esempio. Le $15$ microoperazioni si codificano con $\lceil\log_2 15\rceil=4$ bit di $FS$ invece di pilotare direttamente $7$ segnali di controllo.

($FS=0111$ ripete il trasferimento di $A$ con $G$ diverso; $FS=1111$ non è usato.)

Control word del datapath

La control word raccoglie tutti i segnali di controllo del datapath: 16 bit.

Codici dei registri: $R_0\dots R_7=000\dots111$.

Esempi di microoperazioni (notazione simbolica e codifica, X = indifferente):

La prima, scritta su 16 bit, è 0010100110010101. Nell'ultima si ottiene lo $0$ con uno XOR di un registro con se stesso ($X\oplus X=0$). Una sequenza di microoperazioni si simula applicando una control word per ciclo: a ogni fronte il register file memorizza il risultato della microoperazione con $RW=1$.

VHDL: una ALU behavioral

library IEEE;
use IEEE.std_logic_1164.all;
use IEEE.numeric_std.all;

entity alu8 is
  port ( A, B : in  std_logic_vector(7 downto 0);
         FS   : in  std_logic_vector(3 downto 0);
         F    : out std_logic_vector(7 downto 0);
         Z    : out std_logic );
end alu8;

architecture beh of alu8 is
  signal r : std_logic_vector(7 downto 0);
begin
  process (A, B, FS)
    variable ua, ub : unsigned(7 downto 0);
  begin
    ua := unsigned(A);  ub := unsigned(B);
    case FS is
      when "0000" => r <= A;
      when "0001" => r <= std_logic_vector(ua + 1);
      when "0010" => r <= std_logic_vector(ua + ub);
      when "0011" => r <= std_logic_vector(ua + ub + 1);
      when "0100" => r <= std_logic_vector(ua + not ub);
      when "0101" => r <= std_logic_vector(ua + not ub + 1);
      when "0110" => r <= std_logic_vector(ua - 1);
      when "0111" => r <= A;
      when "1000" => r <= A and B;
      when "1001" => r <= A or B;
      when "1010" => r <= A xor B;
      when "1011" => r <= not A;
      when "1100" => r <= B;
      when "1101" => r <= '0' & B(7 downto 1);        -- shift a destra
      when "1110" => r <= B(6 downto 0) & '0';        -- shift a sinistra
      when others => r <= (others => '0');
    end case;
  end process;
  F <= r;
  Z <= '1' when r = "00000000" else '0';
end beh;

Il case copre tutti i valori (others): la ALU è puramente combinatoria (VHDL - istruzioni concorrenti, process e testbenchLe istruzioni concorrenti VHDL sono l'assegnazione di segnale, when-else (logica prioritaria, condizioni valutate in ordine) e with-select (logica parallela: tutti i casi coperti da una sola scelta, others obbligatorio). Un process è un'istruzione concorrente il cui corpo è sequenziale (if, case, loop); parte quando cambia un segnale della sensitivity list (per la logica combinatoria: tutti gli ingressi); i segnali si aggiornano alla sospensione e vince l'ultima assegnazione. Un if senza else (o un caso non coperto) crea memoria non voluta. Il testbench è codice di simulazione con entity vuota, DUT istanziato e un process di stimoli con wait.VHDL - istruzioni concorrenti, process e testbench →).

Errori comuni

• Dimenticare che sottrarre significa $A+\overline B+1$ (il $+1$ è il $C_{in}$).
• Scambiare bus A e bus B: il bus A è anche l'indirizzo di memoria, il bus B il dato da scrivere.
• Confondere shift (perde bit) e rotazione (barrel shifter).
• Credere che la ALU sia sequenziale: è combinatoria, il risultato arriva al registro al fronte di clock.
• Scrivere nella control word i codici dei registri con la numerazione sbagliata ($R_1=001$, non $R_0$).