Fac-simile compito esonerati 2017-18
Parte 2
#include <unistd.h> // fork
#include <stdlib.h> // exit, atoi
#include <stdio.h> // printf, fprintf, perror
#include <signal.h> // kill
int main(int argc, char* argv[]) {
pid_t prev_pid = -1, pid;
int n, i, res, status, sum = 0;
if (argc < 3) {
fprintf(stderr, "usage: chain <n> <cmd> <args>\n");
exit(1);
}
// converte argv[1] da stringa a intero
n = atoi(argv[1]);
// lancia n processi
for (i=0; i<n; ++i) {
pid = fork();
if (pid == -1) {
perror("fork error");
exit(1);
}
// se siamo nel processo figlio
if (pid == 0) {
// se non è il primo processo creato
if (prev_pid != -1) {
// uccide il processo precedentemente creato
res = kill(prev_pid, SIGKILL);
if (res == -1)
perror("cannot kill previous process");
}
// trasforma processo figlio nell'eseguibile argv[2]
execvp(argv[2], argv+2);
// se arrivo qui execvp è fallita
perror("cannot exec process");
exit(1);
}
prev_pid = pid;
}
// attende la terminazione di ciascun processo precedentemente lanciato
for (i=0; i<n; ++i) {
res = wait(&status);
if (res == -1) {
perror("error in wait");
exit(1);
}
if (WIFEXITED(status))
sum += WEXITSTATUS(status);
}
return sum;
}
Parte 3
void blur(const int* in, int* out, int n, int d) {
int i, j;
for (i=0; i<d; ++i)
out[i] = in[i];
for (i=d; i<n-d; ++i) {
int sum = 0;
for (j=i-d; j<i+1+d; ++j) sum += in[j];
out[i] = sum/(d+1+d);
}
for (i=n-d; i<n; ++i)
out[i] = in[i];
}
#include <stdlib.h>
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;
}
a. Quante richieste di accesso a memoria vengono effettuate dalla funzione blur?
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.