Ierarhia de memorii

Urmatoarele exemple testeaza timpul efectuarii unei operatii pe un vector :

1) Consideram inmultirea unui vector de dimensiune foarte mare cu un scalar, in mai multi pasi. In pasul 1 accesam fiecare element din vector unul dupa altul si facem operatia, la pasul 2 accesam elementele din 2 in 2 cu revenire (intai consideram pozitiile impare apoi cele pare) si facem operatiile, si asa mai departe cu un pas de lungime maxima = lungimea vectorului, asa incat la final accesam doar prima pozitie din vector, reincarcam vectorul si accesam a doua pozitie.... pana la final.

Ceea ce se observa este ca, teoretic, timpii calculatii corespunzatori fiecarui pas cresc treptat, pana ajung sa se stabilizeze. Timpii cresc cu atata cat ii ia incarcarii in memoria cache a vectorului.

In programul C, s-a folosit functia gettimeofday pentru aflarea orei exacte, pana la microsecunde (care este si ordinul de marime cu care se incarca datele specific cache-ului L2). Dupa fiecare pas, se face diferenta t2-t1 si se afiseaza aceasta valoare /cam la 10.000 pasi/ (pentru a nu se scrie pe ecran prea multe valori).

#include "stdio.h"

#include "sys/time.h"

#include "time.h"

#include "stdlib.h"

int main() {

int pas = 1, n = 100000, i, *v, scalar = 4;

v = (int *)malloc(n*sizeof(int));

for (i=0; i<=n-1; i++)

v[i] = i%10;

struct timeval tv;

time_t t1, t2;

do {

gettimeofday(&tv, NULL);

t1 = tv.tv_usec;

int j;

for(j=0; j<=pas-1; j++)

for(i=j; i<=n-1; i+=pas)

v[i] *= scalar;

gettimeofday(&tv, NULL);

t2 = tv.tv_usec;

if(pas%10000==1)

printf("pasul %d:\t t1=%d t2=%d\t t2-t1=%ld\n", pas, t1,t2, t2-t1);

pas++;

} while (pas<=n-1);

return 0;

}

2) Al doilea exemplu e asemanator, doar ca nu se mai folosesc pasii anteriori, ci se variaza dimensiunea vectorului a.i. sa ocupe intre 1M la inceput -> 12 M , cu un `pas` de 0.5M .

Ceea ce ar trebui sa se observe este scaderea performantei la modul urmator:

#include "stdio.h"

#include "sys/time.h"

#include "time.h"

#include "stdlib.h"

#define MAX 3145728 // 12MB

#define pas_dim 131072 // 0.5MB

// pt cache L2

int main() {

long int n = 32768, *v; // 2^20/32

int i, scalar = 4;

v = (long int *)malloc(MAX*sizeof(long int));

for (i=0; i<=MAX-1; i++)

v[i] = i%10;

struct timeval tv;

time_t t1, t2;

do {

gettimeofday(&tv, NULL);

t1 = tv.tv_usec;

for(i=0; i<=n-1; i++)

v[i] *= scalar;

gettimeofday(&tv, NULL);

t2 = tv.tv_usec;

n = n+pas_dim;

printf("dim %ld:\t t1=%d t2=%d\t (t2-t1)/n*1000=%lf\n", n, t1,t2, (t2-t1)/(double)n);

} while (n<=MAX-1);

return 0;

}