AOR2/K1P 2022

Popravni prvi kolokvijum 2022. godine održan je 7. maja i trajao je 90 minuta. Postavka ovog roka u trenutku pisanja nije dostupna sa stranice predmeta, ali će verovatno biti u budućnosti.

1. zadatak

Postavka

Objasniti tehniku optimizacije rada keš memorije hardverskim dovlačenjem unapred (Hardware Prefetching). Dati po jedan primer programa kod koga se mogu uočiti pozitivne negativne strane ovog pristupa.

Rešenje

Hardversko dovlačenje unapred funkcioniše, u svojoj najjednostavnijoj varijanti, tako što nakon dovlačenja jednog bloka keša hardver (procesor/kontroler keš memorije) sam dovuče sledeći blok iz operativne memorije u keš, očekujući da će procesor sledeće iskorititi taj blok. U svojim komplikovanijim varijantama, hardver može da ovo sprovodi tek nakon n-tog sekvencijalnog dovlačenja bloka iz operativne memorije. U suštini, pozitivne strane se mogu uočiti kada je pretpostavka da treba dovući sledeći blok ispravna, a negativne kada nije:

// Овде ће се блокови довлачити један за другим, и хардверско довлачење ће нам у томе помоћи.
for (int i = 0; i < n; ++i) {
    sum += niz[i];
}

// Овде ће се прво користити један податак из првог блока, затим из неког петог, па деветог...
// хардверско довлачење ће сваки пут довлачити погрешан блок унапред, и то може (али не мора)
// да одмогне.
for (int x = 0; x < nx; ++x) {
    for (int y = 0; y < ny; ++y) {
        sum += mat[y][x];
    }
}

2. zadatak

Postavka

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

Veličina^[sic] podataka su: sizeof(int) = 32 bit, sizeof(bool) = sizeof(char) = 8 bit, adrese se^[sic] su širine 32 bita.

Potrebno je napisati funkciju void rotateMatrixClockwise(int** mat, int n), koja rotira kvadratnu matricu u smeru kazaljke na satu, gde je int** mat pokazivač na matricu, a int n veličina matrica (n × n) gde je n veće od 0 i deljivo je sa 16. Prilikom pisanja programa, obratiti pažnju na karakteristike keš memorije i iskoriti^[sic] je tako da prilikom izvršavanja funkcije bude što manje cache MISS.

Stanje matrice pre rotacije.

1	2	⋯	15	16
17	18	⋯	31	32
⋮	⋮	⋱	⋮	⋮
225	226	⋯	239	240
241	242	⋯	255	256

Stanje matrice posle rotacije.

241	225	⋯	17	1
242	226	⋯	18	2
⋮	⋮	⋱	⋮	⋮
255	239	⋯	31	15
256	240	⋯	32	16

Rešenje

Ideja algoritma jeste podeliti celu matricu na četiri dela, tako da se iz gornjeg levog elementi premeštaju u gornji desni, iz njega u donji desni, iz njega u donji levi i na kraju nazad u gornji levi. Svaki od tih delova zatim delimo na blokove od 16 × 16 int (svaki od njih zauzima 16 blokova keš memorije), podatke kopiramo između njih, pa pređemo na sledeći takav blok. Četiri bloka od 16 × 16 int zauzimaju $4 \cdot 16 \cdot 16 \cdot 4B = 4KiB$, tako da sigurno svi staju u keš memoriju odjednom. Sa ovakvim keš iskorišćenjem, povećavanje veličine bloka ne bi trebalo da donese naročita poboljšanja u performansama, jer je keš već maksimalno iskorišćen.

void rotateMatrixClockwise(int** mat, int n) {
    const int nHalf = n >> 1;
    for (int blockY = 0; (blockY << 4) < nHalf; ++blockY) {
        // Померај тренутног блока по Y оси
        const int offsetY = blockY << 4;
        for (int blockX = 0; (blockX << 4) < nHalf; ++blockX) {
            // Померај тренутног блока по X оси
            const int offsetX = blockX << 4;
            for (int y = offsetY; y < offsetY + 16 && y < nHalf; ++y) {
                for (int x = offsetX; x < offsetX + 16 && x < nHalf; ++x) {
                    const int idx1x = x;
                    const int idx1y = y;
                    const int idx2x = n - y - 1;
                    const int idx2y = x;
                    const int idx3x = n - x - 1;
                    const int idx3y = n - y - 1;
                    const int idx4x = y;
                    const int idx4y = n - x - 1;
                    const int tmp = mat[idx1y][idx1x];
                    mat[idx1y][idx1x] = mat[idx4y][idx4x];
                    mat[idx4y][idx4x] = mat[idx3y][idx3x];
                    mat[idx3y][idx3x] = mat[idx2y][idx2x];
                    mat[idx2y][idx2x] = tmp;
                }
            }
        }
    }
}