argomenti della lezione

di che si tratta:

limitazioni delle FSM
microprogrammazione: origini, interpreti microprogrammati
controllo microprogrammato: architettura, vantaggi
codifica delle microistruzioni
datapath microprogrammato
stesura di microprogrammi
esempi:
- architettura microprogrammata
- codifica delle microstruzioni
- microprogramma per il calcolo del GCD

limitazioni delle FSM

i modelli FSM catturano bene gli aspetti di flusso del controllo e decisionali degli algoritmi, tuttavia mancano di gerarchia; ciò è fonte di limitazioni severe quando si tratta di sistemi di controllo complessi

esplosione degli stati

la dimensione dello spazio degli stati di una FSM prodotto è il prodotto delle dimensioni degli spazi degli stati delle FSM componenti; peggio ancora, se queste hanno condizioni di transizione indipendenti, la numerosità delle condizioni nella FSM prodotto cresce esponenzialmente

gestione delle eccezioni

le eccezioni sono condizioni che richiedono transizione a uno stato di gestione delle eccezioni qualunque sia lo stato corrente della macchina; l'aggiunta di transizioni per la gestione delle eccezioni a un dato diagramma di transizioni spesso offusca il corso principale del controllo

flessibilità a tempo di esecuzione

il flusso del controllo cablato definito da una FSM può essere modificato solo rimpiazzando l'implementazione della FSM con un'altra; la motivazione per una maggiore flessibilità del modello è collegata a quella per una maggiore flessibilità dell'hardware

l'idea della microprogrammazione

un controllo più flessibile si realizza con la sua microprogrammazione

la schedule fissa della FSM è rimpiazzata da quella, variabile, determinata da un microprogramma, costituito da microistruzioni, ciascuna delle quali è tradotta in segnali di controllo del datapath

la prima idea di microprogrammazione fu proposta da Maurice Wilkes, nel 1951, ma trovò ampia applicazione a partire dagli anni '60, per divenire dominante nel decennio successivo con la diffusione delle architetture CISC (Complex Instruction-Set Computer)

in questa idea, il microprogramma è un interprete, residente in una piccola memoria di controllo
il microinterprete preleva dalla memoria principale istruzioni macchina (qui viste come istruzioni di livello più alto) e trasforma ciascuna di esse in una sequenza di istruzioni di livello più basso (microistruzioni, appunto), detta microroutine
- la microarchitettura di un processore CISC aqcuista così l'aspetto di un "processore nel processore", con un microprogramma fisso che durante ogni ciclo macchina preleva un'istruzione ed esegue la microroutine determinata dalla decodifica del codice operativo dell'istruzione prelevata

architettura del controllo microprogrammato

a partire dagli anni '80 le architetture RISC (Reduced Instruction-Set Computer) hanno conteso il campo a quelle CISC, per divenire quindi dominanti

la microprogrammazione è tuttora una tecnica molto utile a dare più flessibilità al progetto hardware

Schaumont, Figura 6.3 - in contrasto con il controllo basato su FSM,
la microprogrammazione usa uno schema di controllo flessibile

Schaumont, Figure 6.3 - In contrast to FSM-based control, microprogramming uses a flexible control scheme

CSAR (Control Store Address Register): l'analogo del Program Counter convenzionale

ciclo di clock determinato dal cammino critico nell'architettura microprogrammata

vantaggi del controllo microprogrammato

il controllo microprogrammato risolve i problemi delle FSM:

scala facilmente con la complessità, per esempio con CSAR da 12 bit si può indirizzare una memoria di controllo da 4K istruzioni, mentre una FSM con 4K stati sarebbe estremamente complessa
con piccole aggiunte all'architettura in figura 6.3 si può realizzare un controllo gerarchico, per esempio, aggiungendo un registro o una pila per il salvataggio e ripristino di CSAR, si possono definire microistruzioni di chiamata e rientro a/da microsottoprogramma
le eccezioni possono essere gestite facilmente dalla logica di indirizzo, che alimenterebbe CSAR con l'indirizzo predefinito di una microroutine di gestione delle eccezioni
è evidente il vantaggio di flessibilità hardware, per modificare il controllo del datapath basta riscrivere la memoria di controllo

codifica di microistruzioni: campo indirizzo

Schaumont, Figura 6.4 - esempio di formato di una parola di
microistruzione da 32 bit

Schaumont, Figure 6.4 - Sample format for a 32-bit
micro-instruction word

la definizione di formato e codifica delle microistruzioni è guidata da considerazioni di progetto; ecco un esempio di codifica

ipotesi: micro-istruzioni da 32 bit, metà per il comando al datapath, l'altra metà per l'indirizzo della prossima micro-istruzione; cominciamo da quest'ultimo
12 bit per il campo indirizzo → memoria di controllo per max. 4K microistruzioni
4 bit per il campo next: seleziona la modalità di calcolo del prossimo indirizzo da caricare in CSAR, opzioni:
- incremento di 1 (default)
- salto incondizionato
- salti condizionati

codifica di microistruzioni: campo comando

il formato in figura 6.4 non è ottimale, poiché il campo indirizzo è usato solo per istruzioni di salto: può avere altri usi con altre istruzioni

Schaumont, Figura 6.5 - esempio di codifiche verticale e
orizzontale

Schaumont, Figure 6.5 - Example of vertical versus horizontal
micro-programming

un altro risparmio di spazio o tempo si ha con l'alternativa per il campo comando:

codifica orizzontale : un bit distinto per ogni bit di controllo del datapath
codifica verticale : la più breve codifica del controllo del datapath

spesso si ha una soluzione mista, e.g. la codifica nel campo next:

Schaumont, Figura 6.6 - codifica di CSAR

Schaumont, Figure 6.6 - CSAR encoding

datapath microprogrammato

il datapath di una macchina microprogrammata consiste di tre elementi:

unità funzionali di calcolo
unità di memoria (banco di registri)
gruppi di linee (bus) di comunicazione

a ciascuno di questi elementi possono corrispondere alcuni bit di controllo nella codifica della microistruzione, per esempio:

unità di calcolo multifunzione: bit di selezione di funzione
unità di memoria: bit di indirizzo e bit di comando lettura/scrittura
bus di comunicazione: bit di controllo sorgente/destinazione

inoltre il datapath può generare flag di stato per il controllore microprogrammato

esempio di architettura microprogrammata

ecco un esempio di controllo microprogrammato di un datapath che include: una ALU con registro a scorrimento, un banco di otto registri, un registro accumulatore e una porta di input

codifica mista orizzontale/verticale: globalmente orizzontale, poiché ogni unità nel datapath usa una porzione distinta della parola di controllo, codifica verticale dei segnali di controllo di ciascuna unità nella sua porzione

Schaumont, Figura 6.7 - un datapath microprogrammato

Schaumont, Figure 6.7 - A micro-programmed datapath

lo shifter genera anche bit di esito usati dal controllore microprogrammato per salti condizionati

campi della parola di controllo:

Nxt, Address: usati dal controllore microprogrammato, gli altri campi sono usati dal datapath
ALU: si possono codificare fino a 16 operazioni
SBUS: selezione di un operando sorgente per la ALU, fra gli otto regisri del banco e la porta di input, l'altro operando sorgente è l'accumulatore
Dest: selezione della destinazione per l'operazione di ALU e shifter, fra i registri del banco e l'accumulatore
Shifter: selezione della funzione di scorrimento, fino a otto funzioni

il datapath preleva ed esegue una microistruzione ogni ciclo di clock

esempio di codifica delle microistruzioni (1)

la tabella 6.1 presenta un esempio di codifica di microistruzioni per l'architettura vista (prima parte):

Field	Width	Encoding

SBUS	4	Selects the operand that will drive the S-Bus
		0000	R0	0101	R5
		0001	R1	0110	R6
		0010	R2	0111	R7
		0011	R3	1000	Input
		0100	R4	1001	Address/Constant
ALU	4	Selects the operation performed by the ALU
		0000	ACC	0110	ACC \| S-Bus
		0001	S-Bus	0111	not S-Bus
		0010	ACC + S-Bus	1000	ACC + 1
		0011	ACC – S-Bus	1001	S-Bus – 1
		0100	S-Bus – ACC	1010	0
		0101	ACC & S-Bus	1011	1

esempio di codifica delle microistruzioni (2)

tabella 6.1 (seconda parte):

Field	Width	Encoding

Shifter	3	Selects the function of the programmable shifter
		000	logical SHL(ALU)	100	arith SHL(ALU)
		001	logical SHR(ALU)	101	arith SHR(ALU)
		010	rotate left ALU	111	ALU
		011	rotate right ALU
Dest	4	Selects the target that will store S-Bus
		0000	R0	0101	R5
		0001	R1	0110	R6
		0010	R2	0111	R7
		0011	R3	1000	ACC
		0100	R4	1111	unconnected
Nxt	4	Selects next-value for CSAR
		0000	CSAR + 1	1010	cf ? CSAR + 1 : Address
		0001	Address	0100	zf ? Address : CSAR + 1
		0010	cf ? Address : CSAR + 1	1100	zf ? CSAR + 1 : Address

stesura di microprogrammi

con la codifica definita in tabella 6.1, una microistruzione si forma selezionando una funzione per ciascuno dei moduli nel datapath e un indirizzo per il campo Address (con un opportuno valore di indifferenza per esso qualora Nxt sia nullo)

a mo' di esempio, vediamo come una istruzione RTL, quale ACC ← R2, si traduce in una microistruzione

Schaumont, Figura 6.8 - formazione di microistruzioni da
istruzioni RTL

Schaumont, Figure 6.8 - Forming micro-instructions from register-transfer instructions

l'operando sorgente è in R2: SBUS = 0010
la ALU passa l'input S-Bus all'output: ALU = 0001
lo shifter inoltra l'output dell'ALU senza modifiche: Shifter = 111
l'output dello shifter aggiorna l'accumulatore: Dest = 1000
nessun salto né trasferimento di controllo è dovuto a questa istruzione, dunque CSAR ha l'incremento di default, perciò Nxt = 0000 e Address ha un valore d'indifferenza, e.g. nullo

esempio di microprogramma per il calcolo del GCD

strutture di controllo complesse, quali cicli e strutture if-then-else, possono esprimersi come combinazione (o sequenza) di istruzioni RTL

a titolo di esempio, sviluppiamo un microprogramma che calcola il GCD di due numeri in input usando l'algoritmo di Euclide

il microprogramma è scritto in una notazione RTL simbolica immediatamente traducibile in microistruzioni in modo simile all'esempio precedente

Command Field		\|\|	Jump Field

	IN → R0
	IN → ACC
Lcheck:	(R0 – ACC)	\|\|	JUMP_IF_Z Ldone
	(R0 – ACC) << 1	\|\|	JUMP_IF_C Lsmall
	(R0 – ACC) → R0	\|\|	JUMP Lcheck
Lsmall:	ACC – R0 → ACC	\|\|	JUMP Lcheck
Ldone:			JUMP Ldone

Schaumont, Listing 6.1 - Micro-program to evaluate a GCD

Microprogrammazione: architetture e controllo

Lezione 06 di Sistemi dedicati

Docente: Giuseppe Scollo

Università di Catania
Dipartimento di Matematica e Informatica
Corso di Laurea Magistrale in Informatica, AA 2016-17

Indice