[C] Principio di località

[kingbro]

Salve, ho un problema per un esercizio di un esame :muro: , volevo sapere se qualcuno sapeva discutere la (buona o cattiva) località spaziale e temporale esibita dal seguente frammento di programma C, distinguendo fra località spaziale istruzioni, temporale istruzioni, spaziale dati e temporale dati:

int main() {
int a[1000] = {…};
int b[1000][1000] = {…};
int c[1000];
int i,j;
for (i = 0; i < 1000; i++) {
c[i] = 0;
for (j = 0; j < 1000; j++) {
c[i] = c[i] + a[i] * b[j][j];
}
}
}

[^TiGeRShArK^]

int main() {
int a[1000] = {…};
int b[1000][1000] = {…};
int c[1000];
int i,j;
for (i = 0; i < 1000; i++) {
c[i] = 0;
for (j = 0; j < 1000; j++) {
c[i] = c[i] + a[i] * b[j][j];
}
}
}

ora quantomeno è un pò + leggibile :D

[71104]

b è una matrice da 1000x1000, cioè un milione di elementi, di cui però ne usi solamente 1000 (quelli della diagonale); io a sto punto avrei fatto un array da 1000x1 :Prrr:

[PGI-Bis]

Non conosco la località delle istruzioni per cui dico la mia solo relativamente ai dati.

Quei cicli sfruttano la località temporale per c e a

Se scambiassimo il ciclo interno col ciclo esterno:

for(int j = 0; j < 1000; j++) {
for(int i = 0; i < 1000; i++) {
c[i] = 0;
c[i] = c[i] + a[i] * b[j][j];
}
}

sfrutteremmo la località spaziale per c ed a e la località temporale per b. Se la cache non fosse in grado di tenere in memoria i 2000 + 1 elementi, potremmo computare su una frazione di 1000 per i usando un fattore di blocco:

for(int j = 0; j < 1000; j++) {
for(int ii = 0; ii < 1000; ii += B) {
for(int i = ii; i < min(ii + B, 1000); i++) {
c[i] = 0;
c[i] = c[i] + a[i] * b[j][j];
}
}
}

Questo riduce il numero di cache miss di un fattore B ma, ripeto, bisogna avere un'idea di quanto grande sia la cache per sapere se sia utile o inutile.

Per le istruzioni non saprei che dire. E tieni conto che anche quello che ho detto va preso coi molloni. :fagiano: