АОР2/К2 2022

Други колоквијум 2022. године одржан је 7. маја и трајао је 90 минута. Поставка рока није тренутно доступна са странице предмета.

1. задатак

Поставка

Објаснити поступак виртуелизације техником бинарног превођења - Binary Translation. Посебно се осврнути на то у ком моду рада процесора ради гостујући оперативни систем (Guest OS), у ком програми у гостујућем оперативном систему, а у ком програм који обавља вируелицаију.^[sic] Објаснити на који начин се обавља оптимизација рада код ове технике.

Решење

Виртуелизација техником бинарног превођења функционише тако што хипервизор у позадини преводи инструкције које извршава гостујући оперативни систем у инструкције које постижу истоветан резултат али тако да се могу извршити из корисничког режима. Приликом примене ове технике, наш хипервизор ради у кернел режиму рада, цео гостујући оперативни систем се извршава у корисничком режиму, као и кориснички програми унутар њега, с тим што ће се кориснички програми извршавати неометано јер свакако користе инструкције доступне само у корисничком режиму рада.

Ова техника примењена на једноставан начин може доста да погорша перформансе виртуелизованог система, па се зато примењују различите оптимизације, на пример оптимизација кеширањем (већ преведене инструкције се чувају и када се наиђе на њих поново не морају се поново преводити).

2. задатак

Поставка

Потребно је оптимизовати дати код трансформацијом и убацивањем макро функције void __builtin_prefetch(const void *addr, char rw, char locality) на одговарајућим местима тако да се максимално смањи број промашаја у кеш меморији. Програм користи део^[sic] једну in-memory базу података над којом се извршава упит SELECT * FROM T WHERE Atr3>10. Подаци табеле T се смештају по колони где су сви подаци типа int. Табела T има 20 колона (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);
    }
}

Процесор поседује L1 и L2 кеш меморију. Величина блока кеш меморије је 64B. Тежити да се користи што мање простора у L1 кеш меморији.

Меморијски контролер и аритметичко логичка јединица процесора имају могућност рада у паралели. Сматрати да void prefetch враћа резултат након 5 C++ израза који користе оперативну меморију. C++ изрази који не користе оперативну меморију сматрати да не утичу значајно у времену приликом извршавања операције void prefetch, тако да такве изразе треба игнорисати. Оператор new само одвоји простор на heap-у, али не учита тај простор у кеш меморију.

Опис функције prefetch

locality	rw	Опис
0	0	Податак се учитава само у L1 и намењен је претежно за читање
0	1	Податак се учитава само у L1 и намењен је претежно за писање
1	0	Податак се учитава и у L1 и у L2 и намењен је претежно за читање
1	1	Податак се учитава и у L1 и у L2 и намењен је претежно за писање

Решење

У датом коду итерирамо по редовима, којих укупно има $20$, што је дељиво са даље наведеном периодом. Како је периода prefetch операције $5$ приступа меморији, довлачимо ред који се налази за пет локација испред текућег.

Под претпоставком да је величина int типа податка $4B$, тада у један блок стаје $\frac{64B}{4B} = 16$ података, те можемо применити следеће решење:

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