AOR2/K2 2022

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.

Rešenje

Virtuelizacija tehnikom binarnog prevođenja funkcioniše tako što hipervizor u pozadini prevodi instrukcije koje izvršava gostujući operativni sistem u instrukcije koje postižu istovetan rezultat ali tako da se mogu izvršiti iz korisničkog režima. Prilikom primene ove tehnike, naš hipervizor radi u kernel režimu rada, ceo gostujući operativni sistem se izvršava u korisničkom režimu, kao i korisnički programi unutar njega, s tim što će se korisnički programi izvršavati neometano jer svakako koriste instrukcije dostupne samo u korisničkom režimu rada.

Ova tehnika primenjena na jednostavan način može dosta da pogorša performanse virtuelizovanog sistema, pa se zato primenjuju različite optimizacije, na primer optimizacija keširanjem (već prevedene instrukcije se čuvaju i kada se naiđe na njih ponovo ne moraju se ponovo prevoditi).

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);
    }
}