AOR2/K 2021
Kolokvijum 2021. godine održan je 15. maja i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (zipovana).
1. zadatak
Postavka
Objasniti tehniku optimizacije rada keš memorije koja koristi više banki unutar keš memorije (Multibanked Caches). Šta je potrebno da postoji kod procesora i kod keš memorije da bi data tehnika mogla da se primeni.
Rešenje
Keš memorija sa više banki omogućava više istovremenih operacija nad kešom, slično kao što se primenjuje kod memory interleaving. Na primer, uzastopni blokovi mogu biti smeštani u različite banke keš memorije, tako da ako je jedna banka zauzeta dovlačenjem jednog bloka ostale banke mogu da dovlače blokove neposredno posle tog.
2. zadatak
Postavka
U procesoru se nalazi L1 Data asocijativna keš memorija veličine 512KiB, koja koristi write-through algoritam za ažuriranje sadržaja operativne memorije sa no write allocated politikom dovlačenja. Koristi se LRU algoritam zamene. Veličina bloka keš memorije je 64B. Dat je program koji ispisuje za svaki dan meseca maja kolika je izmerena najviša temperatura u tom mesecu.
U matrici temp se nalaze realne vrednosti tipa double (širine 64 bita) koje predstavljaju izmerenu temperaturu za maj mesec za svaki dan za svaki sekund u danu. Matrica temp ima 31 kolonu (kolona 0 – predstavlja podatke za 1. maj, kolona 1 – predstavlja podatke za 2. maj itd.) i 86400 redova podataka (za svaki sekund u danu). Pretpostaviti da matrica temp na početku nije učitana u keš memoriju, kao i da je prva ćelija matrice temp[0][0] poravnata sa blokom keš memorije. Kompajler matricu smešta po redovima.
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);
}
Smatrati da pristup podatku koji se nalazi u keš memoriji traje 2 ns, a dovlačenje celog bloka keš memorije iz operativne memorije traje 50 ns. Ukoliko je došlo do keš promašaja, prvo se iz operativne memorije učita ceo blok u keš memoriju, pa se tek onda pristupa traženom podatku u keš memoriji.
- Potrebno je optimizovati dati kod tako da se rezultat programa ne promeni, a da se pri tome iskoriste karakteristike date keš memorije. Nije dozvoljeno korišćenje namenskih instrukcija za manipulacijom keš memorije. U programu je dostupno za korišćenje još 10 registara opšte namene.
- Izračunati ukupno vreme koje je potrebno za pristup podacima matrice
temp(analizirati deo koda bez ispisa). Smatrati da uslovmax < temp[j][i]će biti ispunjen svaki 10 put. Dati vreme za dati kod, kao i vreme za optimizovani kod (iz stavke po a) )
Rešenje
U originalnom pristupu problemu, mi pristupamo nizu po kolonama, odnosno svaki pristup koloni biće promašaj u kešu. Kako jedna kolona ima 86400 elemenata, a blok je veličine 64 bajta, to znači da se za jedan prolaz dovlači , što je svakako više od 512KiB kolika je veličina naše keš memorije, i znači da će svaki pristup temp u okviru if morati da dovlači jedan blok keša i trajati 50ns. Pored toga, svaki deseti put biće izvršena linija u okviru if, dodajući dodatnih 2ns na to vreme. Vreme izvršavanja ovog dela koda je onda: .
Jedan blok keš memorije nam je 64 bajta, što znači da u njega može da stane 8 double podataka. Dodatno nam je dostupno još 10 registara opšte namene. Ovo sugeriše da je ovde optimalno primeniti blokiranje po 8 dana, tako da prvo prođemo kroz matricu određujući maksimume za prvih osam dana, ispišemo ih, zatim za sledećih osam dana i tako dalje. Ovime postižemo da sve maksimume možemo sačuvati u registrima, i da su skoro svi blokovi keš memorije iskorišćeni do svog maksimuma.
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]);
}
}
Na ovaj način će u svakom redu biti 4 promašaja keša i sve ostalo će biti pogotci, pa je vreme sada: .
3. zadatak
Postavka
Kod hardverske virtualizacije[sic] koristi se tehnika prateće tabela stranica (Shadow Page Tables). Opisati ovu tehniku. Dati primer preslikavanja jedne virtuelne adrese gosta u fizičku adresu domaćina i potpuniti[sic] sve potrebne tabele.
Rešenje
Kako hipervizor mora da zna za stanje stranica gosta kako bi umeo da preslikava adrese, uvodimo tabelu stranica koja prati tabelu stranica gosta. Sam gost ne zna da postoji prateća tabela stranica, a hardver (MMU jedinica i TLB) ne zna da postoji tabela stranica gosta. Praćenje obavljamo na više načina:
- Hipervizor označi region sa tabelom stranica tako da gostu zabrani pisanje u njega, pa te greške hvata i obrađuje, ažurirajući obe tabele u procesu.
- Hipervizor hvata greške u prevođenju adrese gosta i prilikom njihove obrade ažurira prateću tabelu (ovo označava da je u gostu dodato novo mapiranje), kao i INVLPG instrukciju (ovo označava da je u gostu uklonjeno mapiranje).
- Tehnikom paravirtuelizacije gostujući operativni sistem obavesti hipervizora da je dodao ili uklonio mapiranje.
U svakom slučaju, hipervizor mora takođe da hvata promenu STP registra.
4. zadatak
Postavka
Potrebno je delove datog programa optimizovati. Program učitava niz studenata i smešta ih u memoriju. Smatrati da je početna adresa niza za čuvanje studenata poravnata sa blokom keša. Nad nizom primenjuje metoda Student* pronadjiStudentaPoIndeksu(Student* list, int n, char[] gggg, char[] bbbb). Metoda vraća pokazivač na aktivnog studenta koji ima indeks gggg/bbbb, parametar list je pokazivač na listu studenata; n predstavlja broj studenata u listi; gggg i bbbb su nizovi dužine 4 karaktera.
Veličina[sic] podataka su: sizeof(int) = sizeof(float) = 32 bit; sizeof(bool) = sizeof(char) = 8 bit, adrese se[sic] su širine 32 bita. Program se izvršava na procesoru koji poseduje keš memoriju čija je veličina bloka 128 bita. Ostale karaktersitike[sic] keš memorije nisu dostupne.
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;
}
- Predložiti novu strukturu
Student, tako da se data metodapronadjiStudentaPoIndeksuefikasnije izvršava. - Nije moguće izmeniti strukturu
Student. Potrebno je optimizovati datu metodupronadjiStudentaPoIndeksutransformacijom i ubacivanjem instrukcijeprefetchna odgovarajućim mestima tako da ne postoji ni jedan promašaj u keš memoriji. Pretpostaviti da je rezultat instrukcijeprefetchvidljiv nakon izvršenih 5 redova datog koda (prefetchpisati u zasebno u novom redu). - Transformisati metodu
pronadjiStudentaPoIndeksukorišćenjem Loop fusion načina optimizacije koda.
Rešenje
Nova struktura Student može da izgleda ovako:
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;
};
Ukoliko ne bismo mogli da preuredimo strukturu, prefetch instrukcije bismo mogli da ubacimo na sledeći način:
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;
}
Sa druge strane, transformacija korišćenjem Loop fusion bi izgledala ovako:
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;
}