Allocazione dei
registri
Gruppo Bixio, Mosto e Rizzo
Contenuti del seminario
• Approcci software:
– Allocazione locale dei registri
– Allocazione globale dei registri
• Algoritmo di Chow
• Algoritmo di Chaitin
– Grafi con intervalli ciclici
• Un approccio hardware:
– l’allocazione dei registri nell’IA-64
Allocazione dei registri
• L’insieme dei registri della macchina si
suddivide in due gruppi:
– registri dedicati (es.: per la cima
della pila delle aree dati delle
procedure)
– registri generali (equivalenti per
certe operazioni, per altre
specificati dalle istruzioni, come per
la divisione)
Allocazione dei registri
• Consideriamo qui il problema di
assegnare i registri generali alle
variabili di programma
• Il problema e` quello di minimizzare
il traffico tra memoria centrale e i
registri (soprattutto per le macchine
RISC)
Allocazione dei registri
• Due sono le situazioni tipo:
– Allocazione locale (quando il valore
nel registro e` “morto” dopo la fine del
blocco di istruzioni)
– Allocazione globale (quando il valore
nel registro e` “vivo” dopo la fine del
blocco di istruzioni)
• Diversi sono i parametri presi in
considerazione per la scelta degli
algoritmi
Allocazione locale dei
registri
• L’algoritmo classico di Horowitz et al
[1966] riduce il problema a quello della
ricerca di un cammino ottimo in un grafo
orientato aciclico pesato.
• Il grafo rappresenta le interdipendenze
tra le variabili del blocco basico, mentre
i pesi sono la sono le somme dei costi
delle operazioni di load e store [Versione
del 1989 di Wei-Chung, Fisher e
Goodman]
Allocazione locale dei
registri
• In entrata dell’allocatore gli operandi
sono collocati in pseudoregistri del tipo
X={r1,r2,….rm}, in generale in numero
maggiore dei registri fisici.
• Ogni pseudoregistro ha a disposizione
una cella di memoria (riserva) nella
quale si salva il suo valore.
• Uno pseudoregistro e` alloggiato nel
momento in cui il suo valore si trova nel
registro fisico.
Allocazione locale dei
registri
• Per descrivere lo stato degli N
registri,
si
introduce
la
configurazione, un vettore di N
componenti:
Q=<q1,q2,…,qN>
dove
qj
e`
una
coppia
(pseudoregistro, stato)
qj  X  {sporco,pulito}
Allocazione locale dei
registri
r1  Qi-1
(r1 e` colpito)
r1  Qi-1
(r1 e` mancato)
i legge r1
non occorre caricare r1
risulta Qi= Qi-1
scegli un elemento r2 Qi-1
da sloggiare per caricare r1;
se (r2 , sporco)  Qi-1
memorizza r2 nella sua riserva;
carica r1 dalla riserva in r2;
calcola Qi inserendo (r1, pulito) e
togliendo r2 Qi-1
i scrive in r1
non occorre caricare r1
risulta (r1, sporco)  Qi
non occorre caricare r1
risulta Qi = Qi-1
Allocazione locale dei
registri
•Indichiamo con Plettura(i,x) (rispettivamente
Pscrittura (i,x)) la distanza tra l’istruzione i e la
prossima istruzione che legge (risp. che scrive)
lo pseudoregistro x, convenendo che essa sia
infinita se non vi sono altre lettura (scritture) di x.
•Chiaramente uno pseudoregistro x alloggiato
in Qi-1 e` morto se
(Plettura(i-1,x)=)  [Pscrittura(i-1,x)< Plettura(i-1,x)]
cioe` il prossimo accesso o non esiste, o e` in
scrittura.
Allocazione locale dei
registri
• Definiamo poi il Costo(Qi-1,
Qi ) del
cambiamento di configurazione da Qi-1 a Qi ,
consistente nella modifica del contenuto del
registro rj .
• Il costo indica il numero di istruzioni di store o
load necessarie per la modifica. Questa
definizione e’ ragionevole per le macchine
RISC, mentre per altri tipo di macchine i costi
sarebbero da rivedere.
• Il
costo
storico
o
cumulativo
della
configurazione Qi e` la sommatoria dei costi di
tutte le modifiche precedenti.
Grafo delle configurazioni
Criterio detto “il piu` remoto” o di
Belady
• Questo criterio consiste nello sloggiare dalla
configurazione Qi lo (uno) pseudoregistro y che
abbia la lettura piu` lontana nel futuro (o che al
limite sia morto):
y cioe` e` tale che  x  Qi : Plettura (i,y)  Plettura (i,x)
• Lo sloggiamento dell’elemento che ha l’uso
futuro piu` lontano puo` ridurre i mancati (in
lettura) e quindi il numero delle load.
Altri criteri di scelta proposti
• Conviene sempre eliminare un elemento di morti,
rispetto all’elemento di un altro insieme, poiche`
il costo della modifica e` nullo, essendo inutile la
memorizzazione
• Dovendo scegliere tra un elemento sporco x e
uno pulito y, supponendo sia
Plettura(i,x)<Plettura(i,y),
conviene eliminare y.
• Dovendo scegliere tra due elementi sporchi, uno
x sporco_morto e l’altro y o sporco_morto o
sporco_vivo, supponendo che sia
Plettura(i,x)<Plettura(i,y)
conviene sempre eliminare y.
Alcune definizioni
• C= max {Plettura(i,x),x Qi  x e` pulito}
xc sia un elemento per cui Plettura(i,xc)=C
• D= max {Plettura(i,x),x Qi  x e` sporco}
• C= max {Plettura(i,x),x Qi  x e`
sporchi_morti}
xd sia un elemento per cui Plettura (i,xd)=C
• D= max {Plettura(i,x),x Qi  x e`
sporchi_vivi}
REGOLE per la costruzione della
prossima configurazione Qi+1 data Qi
•R1 se  x  morti (se ne sceglie uno
arbitrario se vi sono piu` x), costruisci la
configurazione Qi ottenuta sostituendo a x
lo pseudoregistro yi+1 usato dalla istruzione
(i+1)-esima. La regola esprime il criterio (i)
•R2 se C>D, costruisci la configurazione
Qi+1 i ncui xc e` sostituito da yi+1 . La regola
esprime il criterio (ii) oppure quello di
Belady
•R3 se C>D, si esprime il criterio (iii)
oppure quello di Belady
Algoritmo per costruzione del
grafo delle configurazioni
Sia nodij l’insieme dei nodi per l’istruzione i-esima,
e P un generico nodo
i:=1; crea nodi1 da Q0;
while j<n
do i:=i+1
 P nodij-1
do if colpito then P:=P; inserisce P in nodij;
padre(P):=P endif
if mancato in lettura then crea i nodi
derivati da P con R1,R2 e R3 endif
end do
end do
Allocazione globale dei
registri
• In questo caso prendiamo in
considerazione l’operazione di
allocazione dei registri per un intero
programma o per una procedura
al termine della quale i registri
risultano essere vivi
Alcune definizioni [1]
• il grafo orientato delle interferenze ha come
nodi i punti del programma che assegnano un
valore agli pseudo-registri e elementi, ed ha un
lato tra x e y se esiste un punto p del
programma dove x e y sono entrambi vivi. I due
elementi non possono quindi stare nello stesso
registro, poiche` nel punto p interferiscono.
• dato un grafo non orientato, una coloratura del
grafo e` l'assegnazione di un colore ad ogni
nodo, in modo tale che due nodi adiacenti o
vicini, cioe` collegati da un arco, non abbiano
mai lo stesso colore. Una c-coloratura usa c
colori distinti.
Alcune definizioni [2]
• il numero cromatico di un grafo e` il
minimo numero c per cui esiste una ccoloratura.
• un nodo avente n vicini si dice che ha
grado n; per la sua coloratura e dei vicini
sono necessari n+1 colori. Per noi ogni
colore e` un registro della macchina, e si
tratta di trovare una coloratura del grafo
delle interferenze del programma, con
c N, il numero di registri a disposizione.
Grafo di interferenze e sua
coloratura
Fase 1 del metodo di
Chaitin (1982) [1]
Sia N il numero dei registri (colori) disponibili:
1. Si costruisce il grafo delle interferenze, collegando
con un lato due nodi (pseudoregistri) che siano vivi
nello stesso punto: ossia uno di essi e` vivo nel punto
in cui l’altro e` definito (scritto)
2. Si applica un’ottimizzazioneper eliminare le
copiature inutili. In tale modo si possono assegnare
piu` elementi non interferenti allo stesso registro,
eliminando le istruzioni di copiatura tra di essi
3. Si ricercano nel grafo G i nodi (immediatamente
colorabili) aventi un grado <N, e si eliminano con
tutti i lati uscenti da essi, memorizzando l’ordine
dell’eliminazione, ottenendo un nuovo grafo G’.
Fase 1 del metodo di
Chaitin (1982) [2]
4. if il grafo G’ e` vuoto
then termina con successo
else if il grafo si e` ridotto, cioe` G’ e` incluso in G
then G:=G’; ritorna al passo 3
else termina con l’indicazione che
l’algoritmo e` bloccato
endif
endif
5. Nell’ordine inverso dell’eliminazione, si
riprendono i nodi, assegnando i registri ai nodi
via via che sono ripresi
ALGORITMO di completamento
del metodo di Chaitin [1]
Dato il grado di interferenza corrente, prodotto
dalla fase 1:
1. Si individua, con il criterio illustrato
successivamente, un elemento da sacrificare,
cioe` da tenere in memoria invece che in un
registro
2. Si calcola il nuovo grafo delle interferenze,
modificando quello corrente
3. Si riapplica l’algoritmo precedente al grafo
corrente ottenuto
4. if algoritmo precedente termina bloccato
then ritorna al passo 1 (di questo algoritmo)
endif
ALGORITMO di completamento
del metodo di Chaitin [2]
• Per individuare al passo 1 l’elemento x piu`
conveniente da sacrificare, conviene tenere
in conto due aspetti:
• Il vantaggio v(x), che risulta dalla spillatura
per la coloratura del grafo, e` pari al grado
del nodo x nel grafo corrente; infatti si
risparmiano tanti colori quanti sono i vicini del
nodo.
• Il costo c(x) per l’aggiunta del codice, e`
l’aumento del tempo di calcolo se x e`
sacrificato, approssimativamente uguale alla
somma del numero dei punti in cui l’elemento
e` definito o usato.
Il metodo di Chow: definizioni [1]
• Un intervallo vivo v e` costituito dalla coppia
v=(x,β) dove x e` la definizione di un elemento,
e β={B1,B2,…} e` l’insieme dei blocchi basici nei
quali x e` vivo; ogni blocco Bi e` a sua volta una
sequenza di istruzioni. Il grafo di Chow G={V,E}
ha dunque i nodi c={v1,…}, mentre i lati sono:
E={(v1,v2)|v1=(x1, β1)  v2=(x2, β2)  β2 }
• Ad ogni intervallo (x, β) basta un solo colore
(registro fisico), con l’intesa che in esso x
permanga durante l’intero blocco basico β.
Il metodo di Chow: definizioni [2]
• Dato N, il numero dei registri disponibili,
un nodo (cioe` un intervallo vivo) e`
detto colorabile se esso ha meno di N
vicini, altrimenti
esso e` detto non
colorabile. I nodi del primo insieme
possono essere subito colorati, mentre gli
altri saranno sdoppiati in due nodi, in
modo da facilitarne la coloratura.
Grafo degli intervalli vivi
Algoritmo di Chow [1]
• Dato il grafo di Chow G=(V,e); siano Ncol i nodi
non colorabili e Col quelli colorabili.
While Ncol   do
 cNcol do
if #vicini_colorati(c)  N --numero dei vicini
colorati di c in G;
then  sdoppia c=(x,β) in due nodi c e n, tra di
loro spartendo (vedi dopo) i blocchi basici c,
ossia ponendo:
c:=(x,β); n:=(x,β), con β= β  β
ALGORITMO DI CHOWN [2]
if #vicini(c) < N
then Col:= Col  {n}
else Ncol:= Ncol  {n}
endif
end do
 uCol do
if #vicini (u) > N
then Col:= Col - {u}
else NCol:= Ncol  {u}
endif
end do
ALGORITMO DI CHOWN [3]
c:=primo (Ncol)
Ncol:= Ncol – {c}
Colora c se possibile, altrimenti si
generera` poi il codice di spillatura
per c;
end do
 uCol do
colora u
end do
Algoritmo di sdoppiamento degli
intervalli vivi colorabili
•Per il nodo v=(x, β) da sdoppiare spartisci I blocchi
β=(B1,B2…) tra il nuovo nodo creato n ed il vecchio
v. La cardinalita` di β e` indicata da #blocchi(v)
lista:=<B1>
while (lista   and #vicini_colorati(n)< N and #blocchi(v) >1) do
blocco:=testa(lista)
if blocco v. β
then sposta blocco da v a n
if blocco ha un successore
then inserisce in testa a lista il blocco successore di
blocco
else inserisci in coda a lista i due blocchi successori di
blocco
endif
endif
end do
Considerazioni
• Se l’algoritmo non riesce a ridurre il numero di
vicini colorati del nodo v, esso non viene
colorato, ma viene tolto dal grafo, generando il
codice di spillatura.
• Sono due le situazioni in cui si deve spillare:
(i) Un intervallo n=(x,{B1,B2,…}) e` il risultato di
uno sdoppiamento: si inserisce l’istruzione “load
r,x” in ogni punto del programma da cui si entra
in Bi prima di esservi definita. Si inserisce
l’istruzione “store r,x” all’uscita di ogni blocco Bi
dove x sia viva.
(ii) Un intervallo n=(x,{B1,B2,…}) non puo` essere
colorato perche` ha troppi vicini, ne` puo`
essere ulteriormente sdoppiato.
Grafi degli intervalli Ciclici
Grafi degli intervalli ciclici
• L’approccio relativo a questo tipo
di grafo e` stato progettato per
disegnare strutture che facilitassero
la scelta degli intervalli da colorare
con lo stesso colore, e di quelli da
spillare.
• Nella figura successiva, vediamo un
esempio
di
rappresentazione
tramite grafi di intervalli ciclici
Colorare grafi degli
intervalli ciclici
Sono 2 i problemi principali:
 Trovare la colorazione minima di un grafo degli intervalli
ciclici: dare un insieme di intervalli rappresentati come un
grafo degli intervalli ciclici G, trovare il minimo
assegnamento di un registro (colore) per l’intervallo in G,
in modo tale da intervalli “accavallati” siano assegnati in
differenti registri.
 Trovare una k-colorazione di un grafo con intervallo
ciclico con il minimo costo di spillatura: dare un insieme
di intervalli vivi rappresentati attraverso un grafo degli
intervalli ciclici G e un insieme di k registri, trovare un
assegnamento dei k registri per gli intervalli in G.
Introdurre il codice di spillatura quando necessario, e
tenere il costo di spillatura al minimo.
Definizioni [1]
1. L’ampiezza di un grafo degli intervalli
ciclici G al tempo t, indicata come
width(G,t), e` il numero di intervalli che
coprono t.
2. La massima ampiezza di un grafo degli
intervalli ciclici G, indicata come
Wmax(G), e` il massimo tra le width(G,t)
per tutto t coperto tramite alcuni
intervalli di G. La minima ampiezza si
indica
con
Wmin(G)
ed
indica
esattamente il contrario.
Definizioni [2]
3. Preso G grafo di intervalli che non
contiene
intervalli
ciclici,
la
colorazioni ottimale di G avviene
con Wmax(G) colori.
4. Se G contiene intervalli ciclici,
allora la colorazione ottimale di G
avviene con Wmax (G)  K  Wmin (G)
Colorazione minima di un
grafo: the fat cover algoritm
• La chiave per questo algoritmo consiste
nell’osservazione che i fat spots del grafo
degli intervalli sono le locazioni piu`
importanti, e che possiamo
iterativamente ridurre la massima
ampiezza della porzione non colorata
del grafo trovando un insieme non
sovrapposto di intervalli che copre tutto
il fat spots e colorando tutto questo
intervallo con lo stesso colore.
Esempio [1]
Esempio [2]
Esempio [3]
Trovare una k-colorazione di
un grafo degli intervali ciclici
• Si usa un nuovo approccio per
l’allocazione dei registri ponendo dei
vincoli: solo k registri sono disponibili e il
numero minimo di registri richiesti da
colorare sono k' con k'>k
• 3 concetti base:
– separazione della fase di spillatura da quello
di colorazione
– scelta dell’intervallo da spillare
– register floats
Intervalli camaleonti, register float e
register spills
• Da uno studio attento della struttura di
un grafo degli intervalli ciclici, si puo`
vedere che esiste un grosso vincoli che
rendono un grafo non colorabile in k
registri. Se un grafo G ha un tempo ti,
dove ci sono piu` di k intervalli che
coprono ti, allora e` impossibile allocare
un colore differente da quelli ce ci sono
gia` nell’intervallo relativo a ti.
Esempio
Ridurre l’ampiezza di un grafo
degli intervalli ciclici
• Il fatto di cercare di ridurre l’ampiezza di un
grafo comporta l’introduzione di registri per la
spillatura. Comunque vogliamo un approccio
che porti a minimizzare il numero di questi
registri.
• Esiste un algoritmo, chiamato algoritmo sweep
and split, che si basa sulla rappresentazione dei
grafi degli intervalli ciclici. Come il fat cover
algorithm, lo sweep and split trae vantaggio
dalle informazioni disponibili nella
rappresentazione degli intervalli.
Esempio [1] con k=3
Esempio [2]
Esempio [3]
Esempio [4]
Esempio [5]
Un approccio hardware: L’IA-64
• L’insieme delle istruzioni dell’Itanium sono
progettate
per
permettere
al
compilatore di comunicare informazioni
al
processore
per
gestire
risorse
caratteristiche. Sebbene alcune risorse
possono
essere
staticamente
schedulate, l’architettura dell’Itanium
non richiede che il codice sia scritto per
una specifica implementazione di una
micro-architettura per essere funzionale.
Registri dell’IA-64
• 128 registri generali a 64 bit usati per
contenere interi e computazioni per dati
multimediali.
• 128 registri floating point a 82 bit che
sono usati per computazioni con floating
point. Alcuni sono solo read only, e
leggono solo +0.0 e +1.0.
•I
restanti
registri
sono
utilizzati
principalmente per la predizione (in
sistemi pipeline come questo)
Registri dell’IA-64
• Il problema grosso che si pone questo nuovo
tipo di processore consiste nella gestione del
numero cosi` elevato di registri. Piu` che altro,
consiste in una gestione intelligente di questi
registri, in modo da non avere conflitti o
rallentamenti.
• Convenzioni riguardanti le chiamate di
procedure richiedono che il chiamante e il
chiamato salvino i registri che possono essere
sovrascritti
durante
l’esecuzione
delle
procedure. Per effettuare queste operazioni e`
dedicato
un
sottoinsieme
dei
registri
dell’Itanium, chiamati register stack.
Register Stack
• Il register stack e` implementato per la
ridenominazione dei registri al fine di evitare il
side-effect derivante dalle chiamate di
procedure e ritorno dalle procedure.
L’implementazione di questo meccanismo di
ridenominazione non e` pero` visibile ai
programmi applicativi.
• Una parte di questi registri comprende quelli
chiamata statici o globali (da r0 a r31), che non
fanno parte dello stack register, mentre gli
stacked register sono numerati sopra r32 fino ad
un massimo di r127.
Register Stack Engine (RSE)
• L’RSE muove il contenuto dei registri fisici
tra il file dei registri generale e la
memoria senza l’intervento esplicito di
un programma.
• I frame del register stack sono mappati
dentro un insieme di registri fisici che
operano come un buffer circolare
contenente
i
frame
creati
piu`
recentemente. L’RSE toglie e mette in
questi registri fisici a/da un backing store
in memoria.
Register Stack Engine (RSE)
FINE