АОР2/К2 2022

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Други колоквијум 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);
    }
}