Esercizi Calcolatori elettronici

Operazione: Z=A*B+C*D

Ipotesi

• A, B, C, D, Z sono vettori di DP;
• I vettori sono lunghi N elementi, e N è memorizzato in R1;
• Gli indirizzi delle basi dei vettori sono a, b ,c , d, z;
• La latenza dei moltiplicatori è 6 cc;
• La latenza dei sommatori è 2 cc;
• I registri F disponibili sono 64;
• S è il fattore di srotolamento;
• Q è N%S.

Loop base ottimizzato

0 DSLA R2, R1, 3
Loop:
1 L.D F2, R2, a-8
2 L.D F4, R2, b-8
3 L.D F8, R2, c-8
4 L.D F10, R2, d-8
5 MUL.D F6, F2, F4 //3 stalli a istruzione 8
6 MUL.D F12, F8, F10 //4 stalli a istruzione 8
7 DSUBI R2, R2, -8
8 ADD.D F12, F6, F12 //stallata (complessivamente) di 4 cc
9 BNEQ R2, loop
10 S.D F12, R2, z

Considerazioni

L'istruzione BNEQ non deve mai eseguire l'abort dell'istruzione che la segue. L'istruzione 10 non è stallata perché la distanza tra l'ADD.D e la S.D è uguale alla latenza del sommatore, cioè 2 cc. Registri F occupati: 12. Core: L.D, L.D, L.D, L.D, MUL.D, MUL.D, ADD, S.D => 8 operazioni. Operazioni di gestione del loop: DSUBI, BNEQ => 2 operazioni. (1cc (10 (4+ ⋅ cc + ⋅ stalli) = 1 + 14 ⋅ cc.

Loop srotolato di un fattore S

Se N non è multiplo intero di S:

DSLL R2, R1, 3 // R2=N*8
ANDI R3, R2, S*8 // R3=(N*8) % (S*8) =Q*8 (solo se S è potenza di 2). R3 dimensione vettore residuo
DSUB R4, R2, R3 // R4 = (N*8) - R3 (multiplo di S). R3 = la dimensione della parte di vettore multiplo di S
BEQ R4, R2, loop2

Loop1:
1. L.D F2, R2, a-8
2. L.D F4, R2, b-8
3. L.D F8, R2, c-8
4. L.D F10, R2, d-8
5. MUL.D F6, F2, F4 // F6=F2*F4
6. MUL.D F12, F8, F10 // F12=F8*F10 +4 stalli
7. DSUBI R2, R2, -8 // R3=R3-8
8. ADD.D F12, F6, F12 // F12=F6+F12
9. BNE R2, R3, loop1
10. S.D F12, R2, z // F12 → Mem[z+R2]

Se N<S il loop non va eseguito

BLT R2 R3 fuori_dal_loop

Loop2:
11. L.D F2, R2, a-8
12. L.D F4, R2, b-8
13. L.D F8, R2, c-8
14. L.D F10, R2, d-8
15. L.D F16, R2, a-2*8
16. L.D F18, R2, b-2*8
17. L.D F22, R2, c-2*8
18. L.D F24, R2, d-2*8

...

19. L.D F(t-2), R2, c-S*8
20. L.D Ft, R2, d-S*8
21. MUL.D F6, F2, F4 // F6=F2*F4
22. MUL.D F12, F8, F10 // F12=F8*F10
23. MUL.D F20, F16, F18 // F20=F16*F18
24. MUL.D F26, F22, F24 // F26=F22+F24 (2*S moltiplicazioni)+(4-S) stalli (in caso S <= 4, altrimenti 0 stalli)

...

25. DSUBI R2, R2, -S*8 // R2=R2-S*8
26. ADD.D F12, F6, F12 // F12=F6+F12
27. ADD.D F26, F20, F26 // F26=F20+F26

...

→28. S.D F2, R2, z+(S-1) *8 R2 + z -8
29. S.D F26, R2, z+(S-2) *8
30. S.D Fq, R2, z
31. BNEQ R2, loop2
32. S.D Fp, R2, zfuori_dal_loop

Registri F occupati: S*12(4cc (10 )++ ⋅ cc per le istruzioni fuori ciclo) per le istruzioni nel primo ciclo[ − ]+(4 ⋅ + ([2 + 8 ⋅ ]stalli nel primo ciclo) cc per le istruzioni nel secondo ciclo) +[ − ] 1( (1 )+ ([5 − ] = 4 + 14 ⋅ + 7 ⋅ − ) ⋅ +stalli nel secondo ciclo)

→Se S < 4 4 + 14*Q + [(N-Q)/S]*(6 + 7*S)
→Se S > 3 4 + 14*Q + (2 + 8*S)*(N-Q)/S

Notiamo che le latenze dei moltiplicatori nel ciclo srotolato si annullano per S>=4.

Supponendo S=4 il ciclo sarà il seguente

DSLL R2, R1, 3 // R2 = N*8
ANDI R3, R2, 4*8 // R3 = (N*8) % (40) = Q*8
DSUB R4, R2, R3 // R4 = (N*8) - R3 (multiplo di S)
BEQ R4, R2, loop2

Loop1:
1. L.D F2, R2, a-8
2. L.D F4, R2, b-8
3. L.D F8, R2, c-8
4. L.D F10, R2, d-8
5. MUL.D F6, F2, F4 // F6=F2*F4
6. MUL.D F12, F8, F10 // F12=F8*F10 +4 stalli
7. DSUBI R2, R2, -8 // R3=R3-8
8. ADD.D F14, F6, F12 // F14=F6+F12
9. BNEQ R2, R4, loop1
10. S.D F14, R2, z // F14 → Mem[z+R2]

BLT R2 R3 fuori_dal_loop2

Loop2:
1. L.D F2, R2, a-8
2. L.D F4, R2, b-8
3. L.D F6, R2, c-8
4. L.D F8, R2, d-8
5. L.D F10, R2, a-2*8
6. L.D F12, R2, b-2*8
7. L.D F14, R2, c-2*8
8. L.D F16, R2, d-2*8
9. L.D F18, R2, a-3*8
10. L.D F20, R2, b-3*8
11. L.D F22, R2, c-3*8
12. L.D F24, R2, d-3*8
13. L.D F26, R2, a-4*8
14. L.D F28, R2, b-4*8
15. L.D F30, R2, c-4*8
16. L.D F0, R2, d-4*8
17. MUL.D F2, F2, F4
18. MUL.D F6, F6, F8
19. MUL.D F10, F10, F12
20. MUL.D F14, F14, F16
21. MUL.D F18, F18, F20
22. MUL.D F22, F22, F24
23. MUL.D F26, F26, F28
24. MUL.D F30, F30, F0
25. DSUBI R2, R2, -4*8
26. ADD.D F2, F2, F6
27. ADD.D F10, F10, F14
28. ADD.D F18, F18, F22
29. ADD.D F26, F26, F30
30. S.D F2, R2, z+3*8
31. S.D F10, R2, z+2*8
32. S.D F18, R2, z+8
33. BNEZ R2, loop2
34. S.D F26, R2, z

La seconda BNEQ (9) e BNZ (33) non devono mai eseguire l'abort delle istruzioni successive. Registri F occupati: 32.

Quindi lo srotolamento del ciclo con un fattore S=4 permette di utilizzare meno dei registri F totali disponibili (64). 34 (= 4 + 14 ⋅ + ⋅ − ) tempo di esecuzione totale 4.

Possiamo ora verificare la convenienza del loop srotolato rispetto a quello non srotolato facendo degli esempi:

• N=7, Q=24 + 14 ⋅ 3 + 34 = 80 operazioni
  1 + 14 ⋅ 7 = 99 operazioni
  Il loop srotolato esegue il ~18% di operazioni in meno
• N=53, Q=14 + 14 ⋅ 1 + 442 = 460 operazioni
  1 + 14 ⋅ 53 = 743 operazioni
  Il loop srotolato esegue il ~38% di operazioni in meno

Caso operazioni in SP

NB: non è ottimale, sarebbe meglio usare “.PS” e fare così i calcoli riferiti a una coppia di elementi del vettore per ogni istruzione

DSLL R2, R1, 3 // R2 = N*8
ANDI R3, R2, S*8 // R3 = (N*8) %(S*8) = Q*8
DSUB R3, R2, R3 // R3 = (N*8) -R3 (multiplo di S)
BEQZ R3, loop2

Loop1:
1. L.S F2, R2, a-8
2. L.S F4, R2, b-8
3. L.S F8, R2, c-8
4. L.S F10, R2, d-8
5. MUL.S F6, F2, F4 // F6=F2*F4
6. MUL.S F12, F8, F10 // F12=F8*F10 +4 stalli
7. DSUBI R2, R2, -8 // R3=R3-8
8. ADD.S F14, F6, F12 // F14=F6+F12
9. BNE R2, R3, loop1
10. S.S F14, R2, z // F14 → Mem[z+R2]

Loop2:
1. L.S F2, R2, a-8
2. L.S F4, R2, b-8
3. L.S F8, R2, c-8
4. L.S F10, R2, d-8
5. L.S F16, R2, a-2*8
6. L.S F18, R2, b-2*8
7. L.S F22, R2, c-2*8
8. L.S F24, R2, d-2*8
9. L.S F30, R2, a-3*8
10. L.S F32, R2, b-3*8
11. L.S F36, R2, c-3*8
12. L.S F38, R2, d-3*8
13. L.S F44, R2, a-4*8
14. L.S F46, R2, b-4*8
15. L.S F50, R2, c-4*8
16. L.S F52, R2, d-4*8
17. L.S F58, R2, a-5*8
18. L.S F60, R2, b-5*8
19. L.S F64, R2, c-5*8
20. L.S F66, R2, d-5*8
21. MUL.S F6, F2, F4
22. MUL.S F12, F8, F10
23. MUL.S F20, F16, F18
24. MUL.S F26, F22, F24
25. MUL.S F34, F30, F32
26. MUL.S F40, F36, F38
27. MUL.S F48, F44, F46
28. MUL.S F54, F50, F52
29. MUL.S F62, F58, F60
30. MUL.S F68, F64, F66
31. DSUBI R2, R2, -5*8
32. ADD.S F12, F6, F12
33. ADD.S F26, F20, F26
34. ADD.S F40, F34, F40
35. ADD.S F54, F48, F54
36. ADD.S F68, F62, F68
37. S.S F14, R2, z+4*8
38. S.S F28, R2, z+3*8
39. S.S F42, R2, z+2*8
40. S.S F56, R2, z+8
41. BNEQ R2, loop2
42. S.S F70, R2, z

L'analisi fatta nel caso di operazioni DP rimane valida nel caso di operazioni SP, l'unico cambiamento sta nei registri occupati: essi passano da 60 a 30.

Combinazione lineare vettori

C = k*A+q*B. k e q sono costanti, mentre A, B e C sono vettori di tipo double aventi la stessa dimensione. Supponiamo da specifica che l'indirizzo di inizio in memoria del vettore A sia scritto nel R2 e l'indirizzo di inizio in memoria del vettore B sia scritto in R3. C va a caricarsi a partire dall'indirizzo di memoria scritto in R4. k e q si trovano rispettivamente in R5 e R6. La dimensione dei vettori è contenuta in R1.

Codice non ottimizzato

//carico in RM il valore contenuto all'indirizzo M[R5+0]
1 LD RM R5 (0) all'indirizzo M[R6+0]
2 LD RN R6 (0) //carico in RN il valore contenuto
//inizio ciclo //carico in RQ il valore contenuto all'indirizzo M[R2+0]
3 LD RT R2 (0) //carico in RT il valore contenuto all'indirizzo M[R3+0]
4 LD RQ R3 (0)
5 DMULT RT RT R5 //eseguo k*A
6 DMULT RQ RQ R6 //eseguo q*B
7 DADD RT RT RQ //eseguo k*A+q*B
8 stallo (vedi Nota Bene 1)
9 stallo (vedi Nota Bene 1)
//memorizzo la somma contenuta in RT all'indirizzo M[R4+0]
10 SD RT R4 (0)
11 DADDI R2 R2 (8) //incremento il valore di R2 di 8
12 DADDI R3 R3 (8) //incremento il valore di R3 di 8
13 DADDI R4 R4 (8) //incremento il valore di R3 di 8
14 DADDI R1 R1 (-1) //decremento il valore dimensione dei vettori
15 BNEZ R1 -12 //se R1 è diverso da zero salta indietro di 10 istruzioni, altrimenti esegue la prossima istruzione
16 <prossima istruzione> //verrà abortita dopo il fetch nel caso di BNEZ verificata
–Loop in cicli di clock: 16*N + 4 1 = 16*N + 3

Nota Bene 1:
DADD RT RT RQ IF ID EX MEM WB WB → se in ingresso alla porta dati memoria
SD RT R4 (0) IF ID EX MEM gestisco EXE/MEM.B o MEM/WB.ALUOUT questa STORE funziona senza stalli, altrimenti:
DADD RT RT RQ IF ID EXE MEM WB
SD RT R4 (0) IF STALLO STALLO ID EX MEM WB

Codice ottimizzato

1 LD RM R5 (0)
2 LD RN R6 (0)
//inizio ciclo
3 LD RT R2 (0)
4 LD RQ R3 (0)
5 DMULT RT RT R5
6 DMULT RQ RQ R6
7 DADD RT RT RQ
8 DADDI R2 R2 (8)
9 DADDI R3 R3 (8)
10 DADDI R4 R4 (8)
11 DADDI R1 R1 (-1)
12 BNEZ R1 -9 //offset di 9 in quanto ho spostato la SD dopo la BNEZ
//memorizzo il valore della somma nell'indirizzo di memoria M[R4+8-8]
13 SD RT R4 (0)

Posticipo la SD dopo la BNEZ facendo sì che la BNEZ venga eseguita senza abortire l'istruzione successiva in nessun caso, eliminando così la penalità di salto che abortiva l'istruzione successiva alla BNEZ per le prime N-1 iterazioni.

Loop in cicli di clock: 13*N + 4

Divisione campi indirizzi cache

Si supponga di avere uno spazio di indirizzi 4 GB (significa disporre di indirizzi da 32 bit). (8) = 3
Si supponga di avere parole di 8 byte (gli ultimi bit dell'indirizzo sono sempre 0, 29 bit rimanenti + 000).
2 (32) = 5
Si supponga di avere blocchi che contengono 32 parole ( bit dell'indirizzo servono a specificare la2parola all'interno del blocco).

Composizione dell'indirizzo: 24 bit + 5 bit di indirizzamento + 000 = 32 bit totali.

Scomposizione dell'indirizzo nei vari casi

1) Indirizzamento diretto di una cache ($) avente 64 (2⁶) linee (una linea per ogni blocco)

Sono necessari 6 bit per referenziare la linea.
18 bit + 6 bit per referenziare la linea + 8 bit di indirizzo all'interno del blocco (5 bit di blocco + 000)
 Etichetta
 Selettore di linea
 Indirizzo all'interno del blocco

2) Indirizzamento diretto di una cache ($) di 1 MB (2²⁰ bytes)

(2²⁰)/(2⁸)= 2¹² - Numero linee = dimensione memoria / dimensione blocco ;
12(2¹²) = 12;
- Bit necessari per puntare alla linea = 12
12 bit + 12 bit per referenziare la linea + 8 bit di indirizzo all'interno del blocco (5 bit di blocco + 000)
 Etichetta: coincide con i primi 12 bit (per differenza da 32 – tutti gli altri)
 Selettore di linea
 Indirizzo all'interno del blocco

3) Completamente associativa avente 128 linee (una linea per ogni blocco)

Fatto salvo l'indirizzo all'interno del blocco, tutto il resto è etichetta.
24 bit + 8 bit di indirizzo all'interno del blocco (5 bit di blocco + 000)
 Etichetta: 24 bit più significativi (per differenza 32 - 8)
 Indirizzo all'interno del blocco

4) Cache set associativa di 128 (2⁷) set

Servono 7 bit per puntare al set.
17 bit + 7 bit per referenziare il set + 8 bit di indirizzo all'interno del blocco (5 bit di blocco + 000)
 Etichetta: coincide con i primi 17 bit (per differenza da 32 – tutti gli altri)
 Selettore di linea
 Indirizzo all'interno del blocco

5) Cache set associativa di 2 MB (= 2²¹ byte) a 8 vie

- Numero set = Dimensione memoria / dimensione set == dimensione memoria / (dimensione blocco * numero vie) =
21 8 3 21 11 10(2²¹)/[(2⁸) (2³)] = 2¹⁰= ;
10(2¹⁰) = 10;
- Bit necessari per referenziare la linea = 2
14 bit + 10 bit per referenziare il set + 8 bit di indirizzo all'interno del blocco (5 bit di blocco + 000)
 Etichetta: coincide con i primi 14 bit (per differenza da 32 – tutti gli altri)
 Selettore di linea
 Indirizzo all'interno del blocco

Istruzione ALFA

c. op R1 R2 R3 R4
R1*R2 + M[R2+R3]->M[R4]
IF ID EX(R2+R3) MEM EXE(R1*R2) EXE(SOMMA FINALE) MEM
IF ID EX ME EX EX ME
IF ID EX ME WB
IF ID * * EX ME

DADD Rt R2 R3 (dove Rt è un registro che può essere modificato perché non contiene valori significativi al momento dell'esecuzione della mia istruzione CISC)
MULT Rq R1 R2 (dove Rq è un registro che può essere modificato perché non contiene valori significativi al momento dell'esecuzione della mia istruzione CISC) Rq = R1*R2
LOAD Rt Rt Im(0) Rt = M[R2 +R3]
DADD Rq Rq Rt Rq = R1*R2 + M[R2+R3]
SD Rq R4 Im(0)
CC 1 2 3 4 5 6 7 8 9
DADD IF ID EX MEM WB
1MULT IF ID EX MEM WB
2LOAD 3 IF ID EX MEM WB
DADD IF ID * EX MEM WB
4STORE IF * ID EX MEM

Seconda versione

DADD Rt R2 R3 (dove Rt è un registro che può essere modificato perché non contiene valori significativi al momento dell'esecuzione della mia istruzione CISC)
LOAD Rt Rt Im(0) Rt = M[R2 +R3]
MULT Rq R1 R2 (dove Rq è un registro che può essere modificato perché non contiene valori significativi al momento dell'esecuzione della mia istruzione CISC) Rq = R1*R2
DADD Rq Rq Rt Rq = R1*R2 + M[R2+R3]
SD Rq R4 Im(0)
CC 1 2 3 4 5 6 7 8
DADD IF ID EX MEM WB
1LOAD IF ID EX MEM WB
2MULT IF ID EX MEM WB
3DADD IF ID EX MEM WB
4 (ID/EXE.A E (OPERANDO 1ID/EXE.B EX/MEM.ALUOUT; CONTENGONO OPERANDO 2: DATI MEM/WB.LMD) SCADUTI!!!)
STORE IF ID EX MEM
5 →X: 6 bit codice operativo 0-5
→5 bit registri 6-10 R1
→5 bit registri 11-15 R2
→5 bit registri 16-20 R3
→5 bit registri 21-25 R4
→6 bit immediato 26-31

1.IFMem[PC]→IF/ID.IRIf(EX/MEM.Opcode == branch||EX/MEM.Opcode == jump & EX/MEM.Cond){EX/MEM.AluOut→Mem[PC]}Else{Mem[PC] = PC+4}2.IDistruzione beta:R1 R2 R3 R4R1*R2 + M[R2+R3]->M[R4]IF/ID.IR→ID/EX.IR →Regs[IF/ID.IR ] ID/EX.A (R3-> A)6-10 →ID/EX.BRegs[IF/ID.IR ] (R2-> B)11-15 →ID/EX.CRegs[IF/ID.IR ] * (R1-> C)16-20(MEGLIO RITARDARE (A) )→ID/EX.D*Regs[IF/ID.IR ] (R4-> D)21-25(MEGLIO POSTICIPARE IN EX2, PER EVITARE HW AGGIUNTIVO E RISCHI DI DATO SCADUTO)3.EX (SOMMA CON ALU (PER LASCIARE IMMUTATA LA LOGICA DI INGRESSO ALLA MEMORIA), MOLTIPLICAZIONE CON MOLTIPLICATORE AGGIUNTIVO)ID/EX.IR→ EX/MEM.IRID/EX.D→EX/MEM.D * (DA RIMUOVERE SE LA CARICA DI R4 AVVIENE IN EX2)ID/EX.A+ID/EX.B→EX/MEM.ALUOUT (CON L’ALU)ID/EX.B*ID/EX.C→EX/MEM.B ** (CON MOLTIPLICATORE AGGIUNTIVO) (B MEGLIO RITARDARE AL PROSSIMO CC),→ID/EX.C)QUI FACCIO (A: Regs[IF/ID.IR ]16-204.MEMEX/MEM.D→MEM/WB.D * (DA RIMUOVERE SE LA CARICA DI R4 AVVIENE IN EX2)EX/MEM.IR→MEM/WB.IRM[EX/MEM.ALUOUT]→MEM/WB.LMDEX/MEM.B→MEM/WB.B * (DIVENTA INUTILE SE RITARDO QUI B)(RITARDATA QUI: ID/EX.B*ID/EX.C→EX/MEM.B5.EX2 (EVENTUALMENTE LA SOMMA VIENE ESEGUITA CON UN SOMMATORE AGGIUNTIVO INVECE CHE CONL’ALU) →MEM/WB.IR2MEM/WB.IR *Propagare mem/wb.d –> xxx/D *** (DA RIMUOVERE SE LA CARICA DI R4 AVVIENE IN EX2)MEM/WB.LMD+ MEM/WB.B→EX/MEM.ALUOUT ****(IN ALTERNATIVA: MEM/WB.LMD+ MEM/WB.B→SOMMATORE AGGIUNTIVO_OUT)→ID/EX.D*Regs[IF/ID.IR ] (R4-> D)21-256.MEM2EX/MEM.ALUOUT→Mem[xxx.D] * (OPPURE EX/MEM.ALUOUT→Mem[ID/EX.D]) *→Mem[ID/EX.D(IN ALTERNATIVA: SOMMATORE AGGIUNTIVO_OUT )IF ID EXE MEM EXE2 MEM2IF ID EXE MEM WBIF ID * EXE MEM WBIF * ID EX MEM WBLA MIA ISTRUZIONE