[C] Principio di località

[kingbro]

Salve, ho un problema per un esercizio di un esame , 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

[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

[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.