Ottimizzazione statica del codice
per processori pipelined
Canella Matteo & Miglioli Filippo
Lo scopo
Scopo dell’esperienza è quello di ottimizzare
staticamente il codice di un programma in
linguaggio assembly DLX. Per fare questo si è
utilizzato il simulatore WinDLX, che permette la
visualizzazione della pipeline, dei registri interni,
della memoria e dello stato di esecuzione delle
singole istruzioni.
I programmi test
Per l’esercitazione sono stati implementati due programmi.
Il primo, più semplice, esegue una moltiplicazione di due
numeri mediante somme parziali. Il secondo realizza
l’ordinamento di un vettore di interi in memoria.
Il primo programma
È riportata a fianco la
schematizzazione in
metalinguaggio del primo
programma. Le variabili
A e B sono i due
moltiplicandi. C viene
utilizzata come variabile
di supporto nella quale
viene memorizzato il
risultato parziale. Viene
sommato A a se stesso B
volte.
C = 0;
WHILE B > 0 DO
C = C + A;
B = B – 1;
END_WHILE
END.
r
Il primo programma
Vediamo ora come è stato
realizzato in assembly.
LB R2, 0(R1)
;LEGGI A
LB R3, -15(R1) ;LEGGI B
I due operandi vengono
memorizzati in due
locazioni di memoria
successive, la prima delle
quali puntata dal registro
R1. Il risultato
dell’operazione viene
riscritto sulla locazione
puntata da R1.
LB R4,#0
BEQZ R3, FINE
LOOP:
ADD R4,R2,R4
SUBUI R3,R3,#1
BNEZ R3,LOOP
SB 0(R1),R4
FINE:
TRAP 0
Simulazione primo programma
In figura vediamo il clock cycle diagram della parte del programma
interessata da stalli. Si notano due stalli.
1° Stallo: Il branch è condizionato dal valore del
registro R3. Tale valore è caricato nel registro dalla
memoria mediante l’istruzione LB. Il processore
ritarda il decode del branch (stallando la pipeline)
perché il valore di R3 è disponibile solo dopo
l’accesso in memoria dell’istruzione LB. Non è
necessario attendere il Write Back perché è presente
un feedback che rende il dato subito disponibile.
2° Stallo: il branch necessita del valore di R3, che però è
disponibile solo dopo la fase di Execute dell’istruzione
precedente (SUBUI). Il processore quindi introduce un ciclo
di stallo. Anche in questo caso viene utilizzato il meccanismo
del feedback, non occorre attendere il WB sui registri.
Si nota inoltre un ciclo perso dopo il branch, questo perché il
simulatore usa una politica “Predict Untaken”, cioè esegue il fetch
dell’istruzione successiva prima di sapere se il salto verrà fatto.
Simulazione primo programma
Sono stati inseriti nelle
locazioni di memorie
0x000000ff e 0x000000f0
gli operandi, nell’esempio
3 e 4. Come si vede, il
risultato (0x0c) viene
memorizzato nella
locazione 0x000000ff.
L’esecuzione di questo codice richiede
25 Clock Cycles.
Ottimizzazione primo programma
LB R3, -15(R1)
1° Stallo: il primo conflitto è
stato risolto invertendo le due
istruzioni di lettura in memoria
(LB) in modo tale che il registro
R3 sia pronto per l’istruzione di
branch.
LB R2, 0(R1)
LB R4,#0
BEQZ R3, FINE
LOOP:
SUBUI R3,R3,#1
ADD R4,R2,R4
BNEZ R3,LOOP
2° Stallo: è stato risolto
spostando il decremento di R3
sopra l’ADD.
SB 0(R1),R4
FINE:
TRAP 0
Ottimizzazione primo programma
Vediamo che sono stati risolti tutti i conflitti. L’unico ciclo perso rimane quello
dopo il branch. Questo problema non si può risolvere se non utilizzando una
politica “branch delayed”, non supportata dal simulatore WinDLX.
L’esecuzione di questo codice richiede
21 Clock Cycles.
Il secondo programma
A lato è riportata la schematizzazione
in metalinguaggio. Scopo del
programma è ordinare un vettore di
interi (A) contenuto in memoria a
partire dalla locazione “INIZ” e di
lunghezza “LUNG”.
FOR I = INIZ TO (INIZ + LUNG - 1)
FOR J = I + 1 TO (INIZ + LUNG)
IF A[I] > A[J] THEN
SOS = A[J];
A[J] = A[I];
A[I] = SOS;
END_IF;
Il secondo programma
R1 punta alla prima
locazione di memoria
(corrispondente alla
variabile INIZ in
metalinguaggio). R4
punta alla locazione di
memoria successiva. R2
contiene la lunghezza del
vettore (LUNG). Il
programma esegue dei
confronti (SLEU) e degli
scambi (utilizzando due
locazioni di supporto)
fino ad ordinare l’intero
vettore.
LOOP:
LOOP1:
LB R8,0(R1)
;R1 PUNTATORE ALLA PRIMA LOCAZIONE
SUBI R4,R1,#15
;R4 PUNTA ALLA LOCAZIONE SUCCESSIVA R1
SUBI R7,R2,#1
;R7 È IL CONTATORE DEL LOOP SECONDARIO
LB R9,0(R4)
SLEU R5,R8,R9
;R8 E’ MINORE UGUALE DI R9?
BNEZ R5,DOPO
;SE SI’ SALTA A “DOPO”
SB 0(R10),R8
;SCAMBIO R8 CON R9 SE R8 È MAGGIORE DI R9
SB 8(R10),R9
;LA LOCAZIONE PUNTATA DA R10 E LA SUCCESSIVA
LB R9,0(R10)
;SERVONO COME SUPPORTI PER LO SCAMBIO
LB R8,8(R10)
SB 0(R1),R8
;SCRITTURA IN MEMORIA DEI DATI SCAMBIATI.
SB 0(R4),R9
DOPO:
SUBI R4,R4,#15
SUBI R7,R7,#1
BNEZ R7,LOOP1
SUBI R1,R1,#15
SUBI R2,R2,#1
;R2 È LA DIMENSIONE DELL'ARRAY, SERVE COME
SUBI R11,R2,#1
;CONTATORE
BNEZ R11,LOOP
TRAP 0
Simulazione secondo programma
Senza l’ottimizzazione, il programma viene eseguito in 188 cicli di clock
1° Stallo: L’istruzione di confronto
SLEU aspetta che venga caricata
nel registro R9 il contenuto della
locazione puntata da R4. Questo
causa uno stallo nella pipeline.
2° Stallo: Il branch condizionato
aspetta R5, contenente il risultato
del confronto. Notiamo due cicli di
stallo: il primo è causato
dall’istruzione precedente (SLEU),
il secondo è quello relativo
all’istruzione branch.
Ottimizzazione secondo programma
Soluzione 1° stallo: l’istruzione SUBI
R7,R7,#1 che veniva eseguita alla fine
ciclo interno LOOP1, appena prima del
branch, viene spostata all’inizio del ciclo,
in modo da porsi tra le due istruzioni che
provocavano lo stallo. E’ possibile fare
questo spostamento in quanto è
indifferente eseguire il decremento del
contatore all’inizio o alla fine del loop.
LOOP:
LB R8,0(R1)
SUBI R4,R1,#15
SUBI R7,R2,#1
LOOP1:
LB R9,0(R4)
SUBI R7,R7,#1
SLEU R5,R8,R9
BNEZ R5,DOPO
SB 0(R10),R8
SB 8(R10),R9
LB R9,0(R10)
LB R8,8(R10)
SB 0(R1),R8
SB 0(R4),R9
L’esecuzione richiede così
168 clock cycle.
DOPO:
SUBI R4,R4,#15
SUBI R7,R7,#1
BNEZ R7,LOOP1
SUBI R1,R1,#15
SUBI R2,R2,#1
SUBI R11,R2,#1
BNEZ R11,LOOP
TRAP 0
Ottimizzazione secondo programma
Soluzione 2° stallo: lo spostamento del
puntatore alla memoria R4 verso la cella
successiva che veniva fatto alla fine del ciclo
interno, può essere spostato all’inizio di esso.
Viene cioè messo tra le due istruzioni che
provocavano lo stallo.
E’ necessario modificare l’offset di accesso
alla cella puntata dal registro R4
nell’istruzione che riscrive in memoria i dati
cambiati. Questo perché ho decrementato R4
prima di usarlo.
LOOP:
LB R8,0(R1)
SUBI R4,R1,#15
SUBI R7,R2,#1
LOOP1:
LB R9,0(R4)
SUBI R7,R7,#1
SLEU R5,R8,R9
SUBI R4,R4,#15
BNEZ R5,DOPO
SB 0(R10),R8
SB 8(R10),R9
LB R9,0(R10)
LB R8,8(R10)
SB 0(R1),R8
SB 15(R4),R9
L’esecuzione richiede così
158 clock cycle
DOPO:
SUBI R4,R4,#15
BNEZ R7,LOOP1
SUBI R1,R1,#15
SUBI R2,R2,#1
SUBI R11,R2,#1
BNEZ R11,LOOP
TRAP 0
Simulazione secondo programma
3° Stallo: nello scambio delle due celle di memoria, l’istruzione di
scrittura SB che venga scritto il contenuto del registro R8 dall’istruzione
precedente. Questo provoca uno stallo.
4° Stallo: il branch aspetta la fine dell’istruzione di decremento del
registro R8, provocando uno stallo nella pipeline
Ottimizzazione secondo programma
LOOP:
Soluzione 3° stallo: Vengono
scambiate le due istruzioni di
scrittura in memoria (SB) dei
registri scambiati (R8, R9).
LB R8,0(R1)
SUBI R4,R1,#15
SUBI R7,R2,#1
LOOP1:
LB R9,0(R4)
SUBI R7,R7,#1
SLEU R5,R8,R9
SUBI R4,R4,#15
BNEZ R5,DOPO
SB 0(R10),R8
SB 8(R10),R9
LB R9,0(R10)
LB R8,8(R10)
Il programma impiega così
151 cicli di clock
SB 15(R4),R9
0(R1),R8
SB 0(R1),R8
15(R4),R9
DOPO:
BNEZ R7,LOOP1
SUBI R1,R1,#15
SUBI R2,R2,#1
SUBI R11,R2,#1
BNEZ R11,LOOP
TRAP 0
Ottimizzazione secondo programma
LOOP:
Soluzione 4° stallo: sposto il
decremento del puntatore R1
prima del branch.
LB R8,0(R1)
SUBI R4,R1,#15
SUBI R7,R2,#1
LOOP1:
LB R9,0(R4)
SUBI R7,R7,#1
SLEU R5,R8,R9
SUBI R4,R4,#15
BNEZ R5,DOPO
SB 8(R10),R9
SB 0(R10),R8
LB R9,0(R10)
LB R8,8(R10)
Ho risolto così tutti gli stalli. Il
programma ottimizzato viene
eseguito in 147 cicli di clock, cioè
41 cicli in meno della versione
non ottimizzata.
SB 15(R4),R9
SB 0(R1),R8
DOPO:
BNEZ R7,LOOP1
SUBI R1,R1,#15
SUBI R2,R2,#1
SUBI R11,R2,#1
SUBI R1,R1,#15
BNEZ R11,LOOP
TRAP 0
Simulazione secondo programmma
Vediamo a lato l’effetto
dell’ordinamento in memoria.
Il vettore parte dall’indirizzo
0xff e occupa 5 posizioni.
Vediamo che il vettore
[7,1,5,3,2] diventa [1,2,3,5,7],
ordinato.