AOR2/K1 2023

Prvi kolokvijum 2023. godine održan je 6. aprila i trajao je 75 minuta (nakon što je profesor Zaharije pomerio vreme za 15 minuta).

1. zadatak

Postavka

Posmatra se keš memorija realizovana u tehnici set asocijativnog preslikavanja sa 4 ulaza po setu koja koristi SIDE 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.

Rešenje

SIDE algoritam zamene sadrži jedan pokazivač po setu koji pokazuje na sledeći blok za zamenu. Levo od tog bloka je zaštićen segment, a desno ugrožen. Kada se desi hit, ukoliko se on desio u ugroženom segmentu, pokazivač se postavlja desno od mesta na kom se desio. Kada se desi miss, zamenjuje se blok na koji pokazuje pokazivač, a pokazivač se zatim inkrementira.

Blokovi u setu tokom vremena sa pokazivačem.

Tag	0	1	2	3	Rezultat
0	0	→			MISS
1	0	1	→		MISS
2	0	1	2	→	MISS
1	0	1	2	→	HIT
2	0	1	2	→	HIT
5	→ 0	1	2	5	MISS
4	4	→ 1	2	5	MISS
2	4	1	2	→ 5	HIT
3	→ 4	1	2	3	MISS
6	6	→ 1	2	3	MISS
3	→ 6	1	2	3	HIT

2. zadatak

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 korišćenjem Sobelovog filtera pronalazi sve ivice na zadatoj slici. U matrici image se nalaze realne vrednosti tipa double (širine 64 bita) koje predstavljaju boju piksela originalne slike (slika je data kao paleta sivih boja). Matrica edges predstavlja rezultujuću sliku u kojoj su sve ivice obojene belom bojom, dok je ostatak slike crn. Pretpostaviti da nijedna matrica na početku nije učitana u keš memoriju, kao i da su prve ćelije poravnate sa blokom keš memorije. Matrice su smeštene po redovima i istih su dimenzija.

#include <math.h>
void sobel ( double *image, int rows, int columns, double *edges ) {
    int GX[] = { -1, 0, 1, -2, 0, 2, -1, 0, 1 };
    int GY[] = { -1, -2, -1, 0, 0, 0, 1, 2, 1 };

    for ( int row = 1; row < ( rows - 1 ); ++row ) {
        for ( int column = 1; column < ( columns - 1 ); ++column ) {
            double gx = 0;
            double gy = 0;

            for ( int i = 0; i < 3; ++i ) {
                for ( int j = 0; j < 3; ++j ) {
                    int image_row    = row + i - 1;
                    int image_column = column + j - 1;

                    double image_value = image[image_row * columns + image_column];

                    int kernel_index = i * 3 + j;

                    gx += image_value * GX[kernel_index];
                    gy += image_value * GY[kernel_index];
                }
            }

            edges[row * columns + column] = sqrt ( gx * gx + gy * gy );
        }
    }
}

1. Ukoliko se zna da je originalna slika dimezija^[sic] 8x16, naći broj promašaja prilikom pristupa keš memoriji. Uzeti u obzir samo promašaje čiji je uzrok pristup matrici image.
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 manipulacijom keš memorije. U programu je dostupno za korišćenje još 5 registara opšte namene.

Rešenje

Slika dimenzija 8x16 staje cela u keš memoriju veličine 512KiB, pa pošto je jedan blok 64B a double tip podatka 64 bita znači da će biti $\frac{8 \cdot 16 \cdot 8B}{64B} = 16$ promašaja.

Za dovoljno velike matrice, može se desiti da ovaj algoritam izbaci keš linije iz prva tri reda pri prelasku u sledeći i zatim mora ponovo da ih dovlači. Tehnika optimizacije za rad keš memorije koju ovde možemo da primenimo jeste blocking, tako da nam u naših 512KiB keš memorije stanu tri reda matrice image i jedan red matrice edges. To znači da jedan takav red može da bude $\frac{512KiB}{4 \cdot 8B} = 2^{14}$ double podataka dugačak.

Pored toga, možemo da uradimo loop unrolling petlje koja množi sa matricama GX i GY, i time i njih uklonimo, kao i da smestimo neke često korišćene promenljive u registre. Dati kod zatim ispada ovako:

#include <math.h>
const int BLOCK_SIZE = 16384;
void sobel(double *image, const int rows, const int columns, double *edges) {
    for (register int block = 0; block < columns / BLOCK_SIZE; ++block) {
        for (register int row = 1; row < rows - 1; ++row) {
            for (register int column = block * BLOCK_SIZE; column < columns - 1 && column < (block + 1) * BLOCK_SIZE; ++column) {
                const double gx = -1 * image[(row - 1) * columns + (column - 1)] +
                                   1 * image[(row - 1) * columns + (column + 1)] +
                                  -2 * image[(row - 0) * columns + (column - 1)] +
                                   2 * image[(row - 0) * columns + (column + 1)] +
                                  -1 * image[(row + 1) * columns + (column - 1)] +
                                   1 * image[(row + 1) * columns + (column + 1)];
                const double gy = -1 * image[(row - 1) * columns + (column - 1)] +
                                  -2 * image[(row - 1) * columns + (column - 0)] +
                                  -1 * image[(row - 1) * columns + (column + 1)] +
                                   1 * image[(row + 1) * columns + (column - 1)] +
                                   2 * image[(row + 1) * columns + (column - 0)] +
                                   1 * image[(row + 1) * columns + (column + 1)];
                edges[row * columns + column] = sqrt(gx * gx + gy * gy);
            }
        }
    }
}