uniroma1.*_main.c.cognome.nome. Sulle postazioni del laboratorio sarà /home/biar/Desktop/cognome.nome/.cognome.nome.zip (zip -r cognome.nome.zip cognome.nome/).cognome.nome.zip.rm -rf cognome.nome).Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.
Tradurre in IA32 la seguente funzione C sub_array definita in E1-sub-array/e1.c che, dati due array di short a e b di lunghezza rispettivamente na e nb, verifica se a è una sottosequenza consecutiva di b. Ad esempio {2,3,4} è sottosequenza di {1,2,3,4,5}, mentre {1,3,4} non lo è. La funzione richiama un’altra funzione is_prefix già fornita in E1-sub-array/e1_main.c.
e1.c
int sub_array(const short *a, unsigned na, const short *b, unsigned nb) {
int i;
for (i=0; i+na <= nb; ++i) {
int res;
is_prefix(a, b+i, na, &res);
if (res) return 1;
}
return 0;
}
Scrivere la soluzione nel file E1-sub-array/e1.s. Usare il file E1-sub-array/e1_eq.c per sviluppare la versione C equivalente e E1-sub-array/e1_main.c come programma di prova. Attenzione all’aritmetica dei puntatori e a tenere res in stack.
Si consideri la seguente funzione in E2-cache/e2.c:
#define STRIDE 64
long f(const short *v, unsigned n){
long x = 0;
unsigned i, j;
for (i=0; i<STRIDE; ++i)
for (j=0; j<n; j+=STRIDE) x += v[i+j];
return x;
}
Scrivere nel file E2-cache/e2_opt.c una versione della funzione semanticamente equivalente che faccia un migliore uso delle cache. Compilare il programma con make ed eseguirlo con ./e2. Il programma riporterà il tempo di esecuzione in millisecondi della versione non ottimizzata e di quella ottimizzata insieme allo speedup ottenuto. Verificare che la versione ottimizzata calcoli lo stesso valore di quella non ottimizzata.
Domanda 1 Si consideri una cache completamente associativa con 4 linee da 16 byte ciascuna e politica di rimpiazzo LRU. Potendo scegliere durante un cold cache miss, selezionare sempre la linea con indice più basso. Data la seguente sequenza di accessi a indirizzi di memoria, qual è il contenuto delle linee di cache alla fine della sequenza: 116, 71, 142, 162, 70, 244, 273, 132, 112 ? (l’ordine è importante)
Domanda 2 Si consideri una cache associativa a 2 vie con 4 linee da 16 byte ciascuna e politica di rimpiazzo LRU. Potendo scegliere durante un cold cache miss, selezionare sempre la linea con indice più basso. Data la seguente sequenza di accessi a indirizzi di memoria, qual è il contenuto delle linee di cache alla fine della sequenza: 72, 199, 131, 77, 138, 115, 40, 250, 208?
Domanda 3 Quale delle seguenti affermazioni è VERA?
Domanda 4 Quale delle seguenti affermazioni è FALSA?
Domanda 5 Data la seguente porzione di codice. Quanti cicli di clock vengono richiesti da una semplice pipeline a 5 stadi (Fetch, Decode, Execute, Memory, Write-Back) per completare tutte le istruzioni assumendo che gli hazard vengano risolti con stalli?
movl $1, %eax
addl %eax, %ecx
addl $2, %edi
incl %esi
addl %esi, %edx
movl $3, %ebx
Domanda 6 Con riferimento alla domanda 5, è possibile ottimizzare il codice riordinando le istruzioni (senza cambiare la semantica) in modo da ridurre il numero di cicli di clock richiesti?
Domanda 7 Quale delle seguenti affermazioni è VERA?
Domanda 8 Quale delle seguenti affermazioni è FALSA?
CMOV è un’istruzione branchlesse1_eq.c
#include "e1.h"
int sub_array(const short *a, unsigned na, const short *b, unsigned nb) {
int i=0, tmp, res=0;
const short* tmp2;
L: tmp = i;
tmp += na;
if (tmp > nb)
goto E;
tmp2 = b + i;
is_prefix(a, tmp2, na, &res);
if (res)
goto E;
i++;
goto L;
E: return res;
}
e1.s
.globl sub_array
sub_array: # int sub_array(const short *a, unsigned na, const short *b, unsigned nb)
pushl %ebx # i
pushl %edi # na
pushl %esi # nb
pushl %ebp # b
subl $20, %esp # 16 byte per i 4 parametri + 4 byte per res
movl 44(%esp), %edi
movl 48(%esp), %ebp
movl 52(%esp), %esi
xorl %ebx, %ebx # i=0;
movl $0, 16(%esp) # res=0
L: movl %ebx, %eax # eax = i;
addl %edi, %eax # eax += na;
cmpl %esi, %eax # if (eax > nb)
jg E # goto E;
movl 40(%esp),%eax # eax = a
movl %eax, (%esp) # primo parametro
leal (%ebp,%ebx,2), %eax # eax = b + i;
movl %eax, 4(%esp) # secondo parametro
movl %edi, 8(%esp) # terzo parametro
leal 16(%esp), %eax # eax = &res
movl %eax, 12(%esp) # quarto parametro
call is_prefix # is_prefix(a, tmp2, na, &res);
cmpl $0, 16(%esp) # if (res)
jne E # goto E;
incl %ebx # i++;
jmp L # goto L;
E: movl 16(%esp), %eax # return res;
addl $20, %esp
popl %ebp
popl %esi
popl %edi
popl %ebx
ret
e2_opt.c
#include "e2.h"
long f_opt(const short *v, unsigned n){
long x = 0;
unsigned i;
for (i=0; i<n; i+=1) x += v[i];
return x;
}
E. Nessuno dei precedenti
Spiegazione:
Indirizzi: 116, 71, 142, 162, 70, 244, 273, 132, 112
Blocchi (indirizzo/12): 7, 4, 8, 10, 4, 15, 17, 8, 7
Cache: (tra parentesi il tempo dall'ultimo accesso a un blocco in cache)
0 1 2 3
7 -> | 7(0) | | | | (cold miss)
4 -> | 7(1) | 4(0) | | | (cold miss)
8 -> | 7(2) | 4(1) | 8(0) | | (cold miss)
10 -> | 7(3) | 4(2) | 8(1) | 10(0) | (cold miss)
4 -> | 7(4) | 4(0) | 8(2) | 10(1) | (hit)
15 -> | 15(0) | 4(1) | 8(3) | 10(2) | (capacity miss, rimpiazzo LRU)
17 -> | 15(1) | 4(2) | 17(0) | 10(3) | (capacity miss, rimpiazzo LRU)
8 -> | 15(2) | 4(3) | 17(1) | 8(0) | (capacity miss, rimpiazzo LRU)
7 -> | 15(3) | 7(0) | 17(2) | 8(1) | (capacity miss, rimpiazzo LRU)
B. 8, 2, 13, 15
Spiegazione:
Indirizzi: 72, 199, 131, 77, 138, 115, 40, 250, 208
Blocchi (indirizzo/12): 4, 12, 8, 4, 8, 7, 2, 15, 13
Cache: (tra parentesi il tempo dall'ultimo accesso a un blocco in cache)
0 1 2 3
4 -> | 4(0) | | | | (cold miss)
12 -> | 4(1) | 12(0) | | | (cold miss)
8 -> | 8(0) | 12(1) | | | (conflict miss)
4 -> | 8(1) | 4(0) | | | (conflict miss)
8 -> | 8(0) | 4(1) | | | (hit)
7 -> | 8(1) | 4(2) | 7(0) | | (cold miss)
2 -> | 8(2) | 2(0) | 7(1) | | (conflict miss)
15 -> | 8(3) | 2(1) | 7(2) | 15(0) | (cold miss)
13 -> | 8(4) | 2(2) | 13(0) | 15(1) | (capacity miss)
D. Con una cache ad accesso diretto non è possibile usare la politica di rimpiazzo LRU
Spiegazione:
Con una cache ad accesso diretta ogni blocco può essere caricato soltanto in una specifica linea di cache. Per tanto ogni volta che avviene un cache miss non è possibile scegliere quale linea di cache rimpiazzare, poiché questa sarà necessariamente l’unica in cui il blocco può essere caricato.
E. La dimensione di una linea di cache è pari alla dimensione di una pagina della memoria virtuale
Spiegazione:
Non c’è alcuna relazione tra la dimensione delle linee di cache e la dimensione delle pagine della memoria virtuale.
A. 16
Spiegazione:
movl $1, %eax F D E M W
stallo * * * * *
stallo * * * * *
stallo * * * * *
addl %eax, %ecx F D E M W
addl $2, %edi F D E M W
incl %esi F D E M W
stallo * * * * *
stallo * * * * *
stallo * * * * *
addl %esi, %edx F D E M W
movl $3, %ebx F D E M W
|<--- 16 cicli --->|
C. Sì è possibile ridurre il numero di cicli di clock a 10, ma non a meno
Spiegazione:
movl $1, %eax F D E M W
incl %esi F D E M W
addl $2, %edi F D E M W
movl $3, %ebx F D E M W
addl %eax, %ecx F D E M W
addl %esi, %edx F D E M W
|<- 10 cicli ->|
E. Nessuna delle precedenti
Spiegazione:
L’affermazione A è falsa perché la tecnica dell’instruction scheduling viene applicata anche dai compilatori. L’affermazione B è falsa perché il piplining permette di aumentare il throughput. L’affermazione C è falsa perché il pipelining non riduce il tempo di esecuzione delle singole istruzioni. L’affermazione D è falsa perché il pipelining viene applicato all’interno dei core e dunque può essere presente tanto sulle architetture single-core quanto su quelle multi-core. Dunque l’affermazione E è vera.
D. La tecnica del pipelining permette di eseguire più processi in parallelo
Spiegazione:
La tecnica del pipelining permette di sovrapporre temporalmente l’esecuzione di istruzioni successive di un processo. Non viene usata per eseguire più processi in parallelo.