АОР2/К 2021 - Историја измена

KockaAdmiralac: Male ispravke // Edit via Wikitext Extension for VSCode

2023-05-20T19:44:33Z

Male ispravke // Edit via Wikitext Extension for VSCode

← Старија измена		Верзија на датум 20. мај 2023. у 21:44
Ред 52:		Ред 52:
	== 3. задатак ==		== 3. задатак ==
	=== Поставка ===		=== Поставка ===
	Код хардверске виртуализације користи се техника пратеће табела страница (''Shadow Page Tables''). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити све потребне табеле.		Код хардверске виртуализације<sup>[sic]</sup> користи се техника пратеће табела страница (''Shadow Page Tables''). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити<sup>[sic]</sup> све потребне табеле.

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

KockaAdmiralac: Treći zadatak // Edit via Wikitext Extension for VSCode

2023-05-11T20:27:08Z

Treći zadatak // Edit via Wikitext Extension for VSCode

← Старија измена		Верзија на датум 11. мај 2023. у 22:27
Ред 51:		Ред 51:

	== 3. задатак ==		== 3. задатак ==
	~~{{делимично решено}}~~
	=== Поставка ===		=== Поставка ===
	Код хардверске виртуализације користи се техника пратеће табела страница (''Shadow Page Tables''). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити све потребне табеле.		Код хардверске виртуализације користи се техника пратеће табела страница (''Shadow Page Tables''). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити све потребне табеле.

	=== Решење ===		=== Решење ===
			Како хипервизор мора да зна за стање страница госта како би умео да пресликава адресе, уводимо табелу страница која прати табелу страница госта. Праћење обављамо на више начина:
			# Хипервизор означи регион са табелом страница тако да госту забрани писање у њега, па те грешке хвата и обрађује, ажурирајући обе табеле у процесу.
			# Хипервизор хвата грешке у превођењу адресе госта и приликом њихове обраде ажурира пратећу табелу (ово означава да је у госту додато ново мапирање), као и ''INVLPG'' инструкцију (ово означава да је у госту уклоњено мапирање).
			# Техником паравиртуелизације гостујући оперативни систем обавести хипервизора да је додао или уклонио мапирање.
			У сваком случају, хипервизор мора такође да хвата промену STP регистра.

	== 4. задатак ==		== 4. задатак ==

KockaAdmiralac: /* Решење */ Dohvatanje sledećeg studenta, provera granica niza

2023-04-04T19:59:56Z

Решење: Dohvatanje sledećeg studenta, provera granica niza

← Старија измена		Верзија на датум 4. април 2023. у 21:59
Ред 172:		Ред 172:
	Student* pronadjiStudentaPoIndeksu(Student** list, int n, const char gggg[], const char bbbb[]) {		Student* pronadjiStudentaPoIndeksu(Student** list, int n, const char gggg[], const char bbbb[]) {
	// Дохватање броја индекса и године првог студента.		// Дохватање броја индекса и године првог студента.
	prefetch(&(list[0]->id));		if (n != 0)
			prefetch(&(list[0]->id));
	for (int i = 0; i < n; i++) {		for (int i = 0; i < n; i++) {
	// Дохватање статуса активности тренутног студента.		// Дохватање статуса активности тренутног студента.
Ред 180:		Ред 181:
	indeks_ok &= list[i]->gggg[j] == gggg[j];		indeks_ok &= list[i]->gggg[j] == gggg[j];
	// Дохватање броја индекса и године следећег студента.		// Дохватање броја индекса и године следећег студента.
	prefetch(&(list[i]->id));		if (i != n - 1)
			prefetch(&(list[i + 1]->id));
	for (int j = 0; j < 4 && indeks_ok; j++)		for (int j = 0; j < 4 && indeks_ok; j++)
	indeks_ok &= list[i]->bbbb[j] == bbbb[j];		indeks_ok &= list[i]->bbbb[j] == bbbb[j];

KockaAdmiralac: /* Решење */ 7 -> 8

2023-04-04T19:51:25Z

Решење: 7 -> 8

← Старија измена		Верзија на датум 4. април 2023. у 21:51
Ред 43:		Ред 43:
	}		}
	}		}
	for (register int j = 0; j < 7; ++j) {		for (register int j = 0; j < 8; ++j) {
	printf("maj %d.: %lf", i + j, max[j]);		printf("maj %d.: %lf", i + j, max[j]);
	}		}

KockaAdmiralac: K 2021, bez trećeg zadatka

2023-04-04T19:36:17Z

K 2021, bez trećeg zadatka

Нова страница

{{tocright}}
'''Колоквијум 2021. године''' одржан је 15. маја и трајао је 90 минута. Поставка рока доступна је [https://rti.etf.bg.ac.rs/rti/ir3ar2/rokovi/aor2_21.zip са странице предмета] (зипована).

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

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

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

У матрици <code>temp</code> се налазе реалне вредности типа <code>double</code> (ширине 64 бита) које представљају измерену температуру за мај месец за сваки дан за сваки секунд у дану. Матрица <code>temp</code> има 31 колону (колона 0 – представља податке за 1. мај, колона 1 – представља податке за 2. мај итд.) и 86400 редова података (за сваки секунд у дану). Претпоставити да матрица <code>temp</code> на почетку није учитана у кеш меморију, као и да је прва ћелија матрице <code>temp[0][0]</code> поравната са блоком кеш меморије. Компајлер матрицу смешта по редовима.
<syntaxhighlight lang="c">
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);
}
</syntaxhighlight>
Сматрати да приступ податку који се налази у кеш меморији траје 2 ns, а довлачење целог блока кеш меморије из оперативне меморије траје 50 ns. Уколико је дошло до кеш промашаја, прво се из оперативне меморије учита цео блок у кеш меморију, па се тек онда приступа траженом податку у кеш меморији.
<div class="abc-list">
# Потребно је оптимизовати дати код тако да се резултат програма не промени, а да се при томе искористе карактеристике дате кеш меморије. Није дозвољено коришћење наменских инструкција за манипулацијом кеш меморије. У програму је доступно за коришћење још 10 регистара опште намене.
# Израчунати укупно време које је потребно за приступ подацима матрице <code>temp</code> (анализирати део кода без исписа). Сматрати да услов <code>max < temp[j][i]</code> ће бити испуњен сваки 10 пут. Дати време за дати код, као и време за оптимизовани код (из ставке по а) )
</div>

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

Један блок кеш меморије нам је 64 бајта, што значи да у њега може да стане 8 <code>double</code> података. Додатно нам је доступно још 10 регистара опште намене. Ово сугерише да је овде оптимално применити блокирање по 8 дана, тако да прво прођемо кроз матрицу одређујући максимуме за првих осам дана, испишемо их, затим за следећих осам дана и тако даље. Овиме постижемо да све максимуме можемо сачувати у регистрима, и да су скоро сви блокови кеш меморије искоришћени до свог максимума.
<syntaxhighlight lang="c">
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 < 7; ++j) {
printf("maj %d.: %lf", i + j, max[j]);
}
}
</syntaxhighlight>
На овај начин ће у сваком реду бити 4 промашаја кеша и све остало ће бити поготци, па је време сада: <math>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</math>.

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Код хардверске виртуализације користи се техника пратеће табела страница (''Shadow Page Tables''). Описати ову технику. Дати пример пресликавања једне виртуелне адресе госта у физичку адресу домаћина и потпунити све потребне табеле.

=== Решење ===

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

Величина<sup>[sic]</sup> података су: <code>sizeof(int) = sizeof(float)</code> = 32 bit; <code>sizeof(bool)</code> = sizeof(char)</code> = 8 bit, адресе се<sup>[sic]</sup> су ширине 32 бита. Програм се извршава на процесору који поседује кеш меморију чија је величина блока 128 бита. Остале карактерситике<sup>[sic]</sup> кеш меморије нису доступне.
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>
<div class="abc-list">
# Предложити нову структуру <code>Student</code>, тако да се дата метода <code>pronadjiStudentaPoIndeksu</code> ефикасније извршава.
# Није могуће изменити структуру <code>Student</code>. Потребно је оптимизовати дату методу <code>pronadjiStudentaPoIndeksu</code> трансформацијом и убацивањем инструкције <code>prefetch</code> на одговарајућим местима тако да не постоји ни један промашај у кеш меморији. Претпоставити да је резултат инструкције <code>prefetch</code> видљив након извршених 5 редова датог кода (<code>prefetch</code> писати у засебно у новом реду).
# Трансформисати методу <code>pronadjiStudentaPoIndeksu</code> коришћењем ''Loop fusion'' начина оптимизације кода.
</div>

=== Решење ===
Нова структура <code>Student</code> може да изгледа овако:
<syntaxhighlight lang="cpp">
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;
};
</syntaxhighlight>
Уколико не бисмо могли да преуредимо структуру, <code>prefetch</code> инструкције бисмо могли да убацимо на следећи начин:
<syntaxhighlight lang="cpp">
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[]) {
// Дохватање броја индекса и године првог студента.
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];
// Дохватање броја индекса и године следећег студента.
prefetch(&(list[i]->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;
}
</syntaxhighlight>
Са друге стране, трансформација коришћењем ''Loop fusion'' би изгледала овако:
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:АОР2]]