АОР2/К 2021

Колоквијум 2021. године одржан је 15. маја и трајао је 90 минута. Поставка рока доступна је са странице предмета (зипована).

1. задатак

Поставка

Објаснити технику оптимизације рада кеш меморије која користи више банки унутар кеш меморије (Multibanked Caches). Шта је потребно да постоји код процесора и код кеш меморије да би дата техника могла да се примени.

Решење

Кеш меморија са више банки омогућава више истовремених операција над кешом, слично као што се примењује код memory interleaving. На пример, узастопни блокови могу бити смештани у различите банке кеш меморије, тако да ако је једна банка заузета довлачењем једног блока остале банке могу да довлаче блокове непосредно после тог.

2. задатак

Поставка

У процесору се налази L1 Data асоцијативна кеш меморија величине 512KiB, која користи write-through алгоритам за ажурирање садржаја оперативне меморије са no write allocated политиком довлачења. Користи се LRU алгоритам замене. Величина блока кеш меморије је 64B. Дат је програм који исписује за сваки дан месеца маја колика је измерена највиша температура у том месецу.

У матрици temp се налазе реалне вредности типа double (ширине 64 бита) које представљају измерену температуру за мај месец за сваки дан за сваки секунд у дану. Матрица temp има 31 колону (колона 0 – представља податке за 1. мај, колона 1 – представља податке за 2. мај итд.) и 86400 редова података (за сваки секунд у дану). Претпоставити да матрица temp на почетку није учитана у кеш меморију, као и да је прва ћелија матрице temp[0][0] поравната са блоком кеш меморије. Компајлер матрицу смешта по редовима.

for (register int i = 0; i < 31; i = i + 1) {
    register double max = MIN_FLOAT;
    for (register int j = 0; j < 86400; j = j + 1)
        if (max < temp[j][i])
            max = temp[j][i];
    printf("maj %d.:", max);
}

Сматрати да приступ податку који се налази у кеш меморији траје 2 ns, а довлачење целог блока кеш меморије из оперативне меморије траје 50 ns. Уколико је дошло до кеш промашаја, прво се из оперативне меморије учита цео блок у кеш меморију, па се тек онда приступа траженом податку у кеш меморији.

Потребно је оптимизовати дати код тако да се резултат програма не промени, а да се при томе искористе карактеристике дате кеш меморије. Није дозвољено коришћење наменских инструкција за манипулацијом кеш меморије. У програму је доступно за коришћење још 10 регистара опште намене.
Израчунати укупно време које је потребно за приступ подацима матрице temp (анализирати део кода без исписа). Сматрати да услов max < temp[j][i] ће бити испуњен сваки 10 пут. Дати време за дати код, као и време за оптимизовани код (из ставке по а) )

Решење

У оригиналном приступу проблему, ми приступамо низу по колонама, односно сваки приступ колони биће промашај у кешу. Како једна колона има 86400 елемената, а блок је величине 64 бајта, то значи да се за један пролаз довлачи $86400 \cdot 64B = 5400KiB$ , што је свакако више од 512KiB колика је величина наше кеш меморије, и значи да ће сваки приступ temp у оквиру if морати да довлачи један блок кеша и трајати 50ns. Поред тога, сваки десети пут биће извршена линија у оквиру if, додајући додатних 2ns на то време. Време извршавања овог дела кода је онда: $31 \cdot 86400 \cdot \left(t_{miss} + \frac{1}{10} t_{hit}\right) = 134455680ns = 134.45568ms$ .

Један блок кеш меморије нам је 64 бајта, што значи да у њега може да стане 8 double података. Додатно нам је доступно још 10 регистара опште намене. Ово сугерише да је овде оптимално применити блокирање по 8 дана, тако да прво прођемо кроз матрицу одређујући максимуме за првих осам дана, испишемо их, затим за следећих осам дана и тако даље. Овиме постижемо да све максимуме можемо сачувати у регистрима, и да су скоро сви блокови кеш меморије искоришћени до свог максимума.

for (register int i = 0; i < 31; i += 8) {
    register double max[8] = {MIN_FLOAT, MIN_FLOAT, MIN_FLOAT, MIN_FLOAT, MIN_FLOAT, MIN_FLOAT, MIN_FLOAT, MIN_FLOAT};
    for (register int j = 0; j < 86400; ++j) {
        for (register int k = i; k < i + 8 && k < 31; ++k) {
            if (max[k - i] < temp[j][i]) {
                max[k - i] = temp[j][i];
            }
        }
    }
    for (register int j = 0; j < 8; ++j) {
        printf("maj %d.: %lf", i + j, max[j]);
    }
}

На овај начин ће у сваком реду бити 4 промашаја кеша и све остало ће бити поготци, па је време сада: $4 \cdot 86400 \cdot t_{miss} + (31 - 4) \cdot 86400 \cdot t_{hit} + 31 \cdot 86400 \cdot \frac{1}{10} t_{hit} = 22481280ns = 22.48128ms$ .

3. задатак

Поставка

Код хардверске виртуализације^[sic] користи се техника пратеће табела страница (Shadow Page Tables). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити^[sic] све потребне табеле.

Решење

Како хипервизор мора да зна за стање страница госта како би умео да пресликава адресе, уводимо табелу страница која прати табелу страница госта. Сам гост не зна да постоји пратећа табела страница, а хардвер (MMU јединица и TLB) не зна да постоји табела страница госта. Праћење обављамо на више начина:

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

У сваком случају, хипервизор мора такође да хвата промену STP регистра.

4. задатак

Поставка

Потребно је делове датог програма оптимизовати. Програм учитава низ студената и смешта их у меморију. Сматрати да је почетна адреса низа за чување студената поравната са блоком кеша. Над низом примењује метода Student* pronadjiStudentaPoIndeksu(Student* list, int n, char[] gggg, char[] bbbb). Метода враћа показивач на активног студента који има индекс gggg/bbbb, параметар list је показивач на листу студената; n представља број студената у листи; gggg и bbbb су низови дужине 4 карактера.

Величина^[sic] података су: sizeof(int) = sizeof(float) = 32 bit; sizeof(bool) = sizeof(char) = 8 bit, адресе се^[sic] су ширине 32 бита. Програм се извршава на процесору који поседује кеш меморију чија је величина блока 128 бита. Остале карактерситике^[sic] кеш меморије нису доступне.

struct Student {
    int id;
    int jmbg;
    char gggg[4];
    char bbbb[4];
    char pol;
    char* Ime;
    char* Prezime;
    int godinaStudija;
    float prosek;
    bool isActive;
    char polozenoIspita;
    char nivoStudija;
};

void procitajStudente(Student** studenti, int* n);

Student* pronadjiStudentaPoIndeksu(Student** list, int n, const char gggg[], const char bbbb[]) {
    for (int i = 0; i < n; i++) {
        bool indeks_ok = true;
        for (int j = 0; j < 4 && indeks_ok; j++)
            indeks_ok = indeks_ok && list[i]->gggg[j] == gggg[j];
        for (int j = 0; j < 4 && indeks_ok; j++)
            indeks_ok = indeks_ok && list[i]->bbbb[j] == bbbb[j];
        if (indeks_ok && list[i]->isActive)
            return list[i];
    }
    return 0;
}

int main() {
    int n;
    Student** studenti;
    procitajStudente(studenti, &n);
    // ...
    Student* s = pronadjiStudentaPoIndeksu(studenti, n, "2000", "0001");
    // ...
    return 0;
}

Предложити нову структуру Student, тако да се дата метода pronadjiStudentaPoIndeksu ефикасније извршава.
Није могуће изменити структуру Student. Потребно је оптимизовати дату методу pronadjiStudentaPoIndeksu трансформацијом и убацивањем инструкције prefetch на одговарајућим местима тако да не постоји ни један промашај у кеш меморији. Претпоставити да је резултат инструкције prefetch видљив након извршених 5 редова датог кода (prefetch писати у засебно у новом реду).
Трансформисати методу pronadjiStudentaPoIndeksu коришћењем Loop fusion начина оптимизације кода.

Решење

Нова структура Student може да изгледа овако:

struct StudentMisc {
    int id;
    int jmbg;
    char pol;
    char* Ime;
    char* Prezime;
    int godinaStudija;
    float prosek;
    char polozenoIspita;
    char nivoStudija;
};

// Укупно: један студент = 1 блок кеша
struct Student {
    // 4B
    char gggg[4];
    // 4B
    char bbbb[4];
    // 1B
    bool isActive;
    // 3B padding овде
    // 4B
    StudentMisc* misc;
};

Уколико не бисмо могли да преуредимо структуру, prefetch инструкције бисмо могли да убацимо на следећи начин:

struct Student {
    // B0: 4B
    int id;
    // B0: 4B
    int jmbg;
    // B0: 4B
    char gggg[4];
    // B0: 4B
    char bbbb[4];
    // B1: 1B
    char pol;
    // B1: 3B padding
    // B1: 4B
    char* Ime;
    // B1: 4B
    char* Prezime;
    // B1: 4B
    int godinaStudija;
    // B2: 4B
    float prosek;
    // B2: 1B
    bool isActive;
    // B2: 3B padding
    // B2: 1B
    char polozenoIspita;
    // B2: 3B padding
    // B2: 1B
    char nivoStudija;
    // B2: 3B padding
};

Student* pronadjiStudentaPoIndeksu(Student** list, int n, const char gggg[], const char bbbb[]) {
    // Дохватање броја индекса и године првог студента.
    if (n != 0)
        prefetch(&(list[0]->id));
    for (int i = 0; i < n; i++) {
        // Дохватање статуса активности тренутног студента.
        prefetch(&(list[i]->prosek));
        bool indeks_ok = true;
        for (int j = 0; j < 4 && indeks_ok; j++)
            indeks_ok &= list[i]->gggg[j] == gggg[j];
        // Дохватање броја индекса и године следећег студента.
        if (i != n - 1)
            prefetch(&(list[i + 1]->id));
        for (int j = 0; j < 4 && indeks_ok; j++)
            indeks_ok &= list[i]->bbbb[j] == bbbb[j];
        if (indeks_ok && list[i]->isActive)
            return list[i];
    }
    return 0;
}

Са друге стране, трансформација коришћењем Loop fusion би изгледала овако:

Student* pronadjiStudentaPoIndeksu(Student** list, int n, const char gggg[], const char bbbb[]) {
    for (int i = 0; i < n; i++) {
        bool indeks_ok = list[i]->isActive;
        for (int j = 0; j < 4 && indeks_ok; j++) {
            indeks_ok &= list[i]->gggg[j] == gggg[j];
            indeks_ok &= list[i]->bbbb[j] == bbbb[j];
        }
        if (indeks_ok) {
            return list[i];
        }
    }
    return 0;
}

АОР2/К 2021

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Мени за навигацију

АОР2/К 2021

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

Мени за навигацију

Претрага