AOR2/K1P 2023

Ovaj rok nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Popravni prvi kolokvijum 2023. godine održan je 12. maja i trajao je 90 minuta.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Posmatra se keš memorija realizovana u tehnici set asocijativnog preslikavanja sa 4 ulaza po setu koja koristi SLRU (Segmented LRU) algoritam zamene. Objasniti ovaj algoritam. Dati sadržaje svih ulaza TAG dela keš memorije posle svakog pristupa ukoliko se obavljaju pristupi memoriji za isti set koji imaju sledeće vrednosti polja Tag: 0, 1, 2, 1, 2, 5, 4, 2, 3, 6, 3.

2. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

U procesoru se nalazi L1 Data asocijativna keš memorija veličine 512KiB, koja koristi write-back algoritam za ažuriranje sadržaja operativne memorije sa write allocated politikom dovlačenja. Koristi se LRU algoritam zamene. Veličina bloka keš memorije je 64B.

Dat je program koji implementira Stencil operator. U matrici current se nalaze realne vrednosti tipa double (širine 64 bita). Matrica next predstavlja rezultat operacije. Pretpostaviti da nijedna matrica na početku nije učitana u keš memoriju, kao i da su prve ćelije matrica poravnate sa blokom keš memorije. Matrice su smeštene u memoriji tako što je svaka 2D podmatrica smeštena po vrstama, a podmatrice se nalaze jedna do druge u memoriji.

void stencil ( double *current, double *next, int nx, int ny, int nz, double f ) {
    for (int i = 1; i < (nx - 1); ++i ) {
        for( int j = 1; j < (ny - 1); ++j ) {
            for( int k = 1; k < (nz - 1); ++k ) {
                double ku  = current[index3D ( nx, ny, i    , j    , k + 1)];
                double kd  = current[index3D ( nx, ny, i    , j    , k - 1)];
                double ju  = current[index3D ( nx, ny, i    , j + 1, k    )];
                double jd  = current[index3D ( nx, ny, i    , j - 1, k    )];
                double iu  = current[index3D ( nx, ny, i + 1, j    , k    )];
                double id  = current[index3D ( nx, ny, i - 1, j    , k    )];
                double c   = current[index3D ( nx, ny, i    , j    , k    )];
                double sum = ku + kd + ju + jd + iu + id;

                next[index3D( nx, ny, i, j, k)] = sum * f - c * (1 - f);
            }
        }
    }
}

1. Ukoliko se zna da je originalna slika dimenzija 8x8x8, naći broj promašaja prilikom pristupa keš memoriji. Uzeti u obzir samo promašaje čiji je uzrok pristup matrici current
2. Potrebno je optimizovati dati kod tako da se rezultat programa ne promeni, a da se pri tome iskoriste karakteristike date keš memorije. Nije dozvoljeno korišćenje namenskih instrukcija za manipulaciju keš memorije. U programu je dostupno za korišćenje još 10 registara opšte namene.