AOR2/K2 2022

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

Drugi kolokvijum 2022. godine održan je 7. maja i trajao je 90 minuta. Postavka roka nije trenutno dostupna sa stranice predmeta.

1. zadatak

Postavka

Objasniti postupak virtuelizacije tehnikom binarnog prevođenja - Binary Translation. Posebno se osvrnuti na to u kom modu rada procesora radi gostujući operativni sistem (Guest OS), u kom programi u gostujućem operativnom sistemu, a u kom program koji obavlja viruelicaiju.^[sic] Objasniti na koji način se obavlja optimizacija rada kod ove tehnike.

2. zadatak

Postavka

Potrebno je optimizovati dati kod transformacijom i ubacivanjem makro funkcije void __builtin_prefetch(const void *addr, char rw, char locality) na odgovarajućim mestima tako da se maksimalno smanji broj promašaja u keš memoriji. Program koristi deo^[sic] jednu in-memory bazu podataka nad kojom se izvršava upit SELECT * FROM T WHERE Atr3>10. Podaci tabele T se smeštaju po koloni gde su svi podaci tipa int. Tabela T ima 20 kolona (Atr1, Atr2, ... Atr20).

/* ... */
int** table = getTable('T');
int rowsCount = getTableRowsCount('T');
int colsCount = getTableRowsCount('T');
/* ... */
std::vector<int*> result;

for (register int i = 0; i < rowsCount; i++) {
    if (table[3][i] > 10) {
        int* resRow = new int[colsCount];
        for (register int j = 0; j < colsCount; j++)
            resRow[j] = table[j][i];
        result.push_back(resRow);
    }
}

Procesor poseduje L1 i L2 keš memoriju. Veličina bloka keš memorije je 64B. Težiti da se koristi što manje prostora u L1 keš memoriji.

Memorijski kontroler i aritmetičko logička jedinica procesora imaju mogućnost rada u paraleli. Smatrati da void prefetch vraća rezultat nakon 5 C++ izraza koji koriste operativnu memoriju. C++ izrazi koji ne koriste operativnu memoriju smatrati da ne utiču značajno u vremenu prilikom izvršavanja operacije void prefetch, tako da takve izraze treba ignorisati. Operator new samo odvoji prostor na heap-u, ali ne učita taj prostor u keš memoriju.

Opis funkcije prefetch

locality	rw	Opis
0	0	Podatak se učitava samo u L1 i namenjen je pretežno za čitanje
0	1	Podatak se učitava samo u L1 i namenjen je pretežno za pisanje
1	0	Podatak se učitava i u L1 i u L2 i namenjen je pretežno za čitanje
1	1	Podatak se učitava i u L1 i u L2 i namenjen je pretežno za pisanje

Rešenje

U datom kodu iteriramo po redovima, kojih ukupno ima $20$, što je deljivo sa dalje navedenom periodom. Kako je perioda prefetch operacije $5$ pristupa memoriji, dovlačimo red koji se nalazi za pet lokacija ispred tekućeg.

Pod pretpostavkom da je veličina int tipa podatka $4B$, tada u jedan blok staje $\frac{64B}{4B} = 16$ podataka, te možemo primeniti sledeće rešenje:

for (register int i = 0; i < rowsCount; i++)
{
    if (table[3][i] > 10)
    {
        int *resRow = new int[colsCount];
        __builtin_prefetch(&resRow[16], 1, 1); // pristup prvom bloku je uvek promasaj -> dovlacimo sledeci
        for (register int j = 0; j < colsCount - 5; j += 5)
        {
            __builtin_prefetch(&table[j + 5], 0, 1); // prvih pet blokova su promasaji -> ostalo hit
            for (register int k = j; k < j + 5; k++)
            {
                resRow[k] = table[k][i]; // izraz koji koristi OM
            }
        }
        for (register int j = colsCount - 5; j < colsCount; j++)
        {
            resRow[j] = table[j][i]; // ostatak je dovucen
        }
        result.push_back(resRow);
    }
}