Additions:
L'accesso a "in" è locale, "spazzando" un intorno di raggio d=3 intorno a ciascun in[i] per i compreso tra d e n-d-1. Quando si entra nel ciclo for alla riga 5, la prima linea di cache contiene i primi 64 byte di "in", cioè i primi 16 elementi. Quando i raggiunge 16-4 = 12, l'ultima iterazione del for interno alla riga 7 "tocca" la cella in[16] portando il secondo blocco di "in" nella terza linea di cache. Quando i raggiunge 32-4, l'ultima iterazione del for interno alla riga 7 "tocca" la cella in[16], rimpiazzando (se non ci sono altre linee libere) la prima linea che non verrà più acceduta in futuro. Si noti come la sequenza di blocchi di "in" acceduti tocca sempre blocchi consecutivi e al più torna indietro di un blocco. Potendo sempre tenere due blocchi consecutivi in cache, si avrà un comportamento rispetto ai cache miss del tutto analogo a quello di una scansione puramente sequenziale.
Deletions:
L'accesso a "in" è locale, "spazzando" un intorno di raggio d=3 intorno a ciascun in[i] per i compreso tra d e n-d-1. Quando si entra nel ciclo for alla riga 5, la prima linea di cache contiene i primi 64 byte di "in", cioè i primi 16 elementi. Quando i raggiunge 16-4 = 12, l'ultima iterazione del for interno alla riga 7 "tocca" la cella
in[16] portando il secondo blocco di "in" nella terza linea di cache. Quando i raggiunge 32-4, l'ultima iterazione del for interno alla riga 7 "tocca" la cella in[16], rimpiazzando (se non ci sono altre linee libere) la prima linea che non verrà più acceduta in futuro. Si noti come la sequenza di blocchi di "in" acceduti tocca sempre blocchi consecutivi e al più torna indietro di un blocco. Potendo sempre tenere due blocchi consecutivi in cache, si avrà un comportamento rispetto ai cache miss del tutto analogo a quello di una scansione puramente sequenziale.
Additions:
a. Quante richieste di accesso a memoria vengono effettuate dalla funzione blur?
Deletions:
a. Quante richieste di accesso a memoria vengono effettuate dal programma?
Additions:
%%(c;blur.c)
void blur(const int* in, int* out, int n, int d) {
int i, j;
for (i=0; i
out[i] = in[i];
for (i=d; i
int sum = 0;
for (j=i-d; j
out[i] = sum/(d+1+d);
for (i=n-d; i
out[i] = in[i];
#include
int main() {
int* in = malloc(1024*sizeof(int));
int* out = malloc(1024*sizeof(int));
blur(in, out, 1024, 3);
free(in);
free(out);
return 0;
Additions:
Avendo almeno tre linee ed essendo la cache completamente associativa è possibile tenere i blocchi di "out" in una linea e due blocchi consecutivi di "in" in altre due.
L'accesso a "in" è locale, "spazzando" un intorno di raggio d=3 intorno a ciascun in[i] per i compreso tra d e n-d-1. Quando si entra nel ciclo for alla riga 5, la prima linea di cache contiene i primi 64 byte di "in", cioè i primi 16 elementi. Quando i raggiunge 16-4 = 12, l'ultima iterazione del for interno alla riga 7 "tocca" la cella
in[16] portando il secondo blocco di "in" nella terza linea di cache. Quando i raggiunge 32-4, l'ultima iterazione del for interno alla riga 7 "tocca" la cella in[16], rimpiazzando (se non ci sono altre linee libere) la prima linea che non verrà più acceduta in futuro. Si noti come la sequenza di blocchi di "in" acceduti tocca sempre blocchi consecutivi e al più torna indietro di un blocco. Potendo sempre tenere due blocchi consecutivi in cache, si avrà un comportamento rispetto ai cache miss del tutto analogo a quello di una scansione puramente sequenziale.
Aumentando il denominatore nel calcolo del punto b, il numero di miss diminuirebbe.
Deletions:
Avendo almeno tre linee ed essendo la cache completamente associativa
è possibile tenere i blocchi di "out" in una linea e due blocchi
consecutivi di "in" in altre due.
L'accesso a "in" è locale, "spazzando" un intorno di raggio d=3
intorno a ciascun in[i] per i compreso tra d e n-d-1. Quando si entra
nel ciclo for alla riga 5, la prima linea di cache contiene i primi
64 byte di "in", cioè i primi 16 elementi. Quando i raggiunge 16-4 = 12,
l'ultima iterazione del for interno alla riga 7 "tocca" la cella
in[16] portando il secondo blocco di "in" nella terza linea di cache.
Quando i raggiunge 32-4, l'ultima iterazione del for interno alla
riga 7 "tocca" la cella in[16], rimpiazzando (se non ci sono altre
linee libere) la prima linea che non verrà più acceduta in futuro.
Si noti come la sequenza di blocchi di "in" acceduti tocca
sempre blocchi consecutivi e al più torna indietro di un blocco.
Potendo sempre tenere due blocchi consecutivi in cache, si avrà un
comportamento rispetto ai cache miss del tutto analogo a quello di una
scansione puramente sequenziale.
Aumentando il denominatore nel calcolo del punto b, il numero di miss
diminuirebbe.
Additions:
==Parte 3==
a. Quante richieste di accesso a memoria vengono effettuate dal programma?
su out:
- riga 4: d
- riga 8: n-2d
- riga 11: d
- totale: n = 1024
su in:
- riga 4: d
- riga 7: (n-2d)*(2d+1)
- riga 11: d
- totale: 2d+(n-2d)*(2d+1) = 6 + (1024-6)*7 = 7132
b. Quanti cache miss si hanno?
Avendo almeno tre linee ed essendo la cache completamente associativa
è possibile tenere i blocchi di "out" in una linea e due blocchi
consecutivi di "in" in altre due.
L'accesso a "in" è locale, "spazzando" un intorno di raggio d=3
intorno a ciascun in[i] per i compreso tra d e n-d-1. Quando si entra
nel ciclo for alla riga 5, la prima linea di cache contiene i primi
64 byte di "in", cioè i primi 16 elementi. Quando i raggiunge 16-4 = 12,
l'ultima iterazione del for interno alla riga 7 "tocca" la cella
in[16] portando il secondo blocco di "in" nella terza linea di cache.
Quando i raggiunge 32-4, l'ultima iterazione del for interno alla
riga 7 "tocca" la cella in[16], rimpiazzando (se non ci sono altre
linee libere) la prima linea che non verrà più acceduta in futuro.
Si noti come la sequenza di blocchi di "in" acceduti tocca
sempre blocchi consecutivi e al più torna indietro di un blocco.
Potendo sempre tenere due blocchi consecutivi in cache, si avrà un
comportamento rispetto ai cache miss del tutto analogo a quello di una
scansione puramente sequenziale.
Si ha quindi:
su out:
- 1024*sizeof(int)/64 = 4096/64 = 64
su in:
- 1024*sizeof(int)/64 = 4096/64 = 64
In totale si hanno quindi 128 cache miss.
c. Cambierebbe qualcosa se le linee di cache fossero più grandi?
Aumentando il denominatore nel calcolo del punto b, il numero di miss
diminuirebbe.
Additions:
// trasforma processo figlio nell'eseguibile argv[2]
// se arrivo qui execvp è fallita
Deletions:
// lancia eseguibile argv[2]