KockaAdmiralac: /* Решење */ Ovo je rotiralo u obrnutom smeru, sad rotira u dobrom

2023-04-04T14:53:26Z

Решење: Ovo je rotiralo u obrnutom smeru, sad rotira u dobrom

← Старија измена		Верзија на датум 4. април 2023. у 16:53
Ред 78:		Ред 78:
	const int idx4y = n - x - 1;		const int idx4y = n - x - 1;
	const int tmp = mat[idx1y][idx1x];		const int tmp = mat[idx1y][idx1x];
	mat[idx1y][idx1x] = mat[~~idx2y~~][~~idx2x~~];		mat[idx1y][idx1x] = mat[idx4y][idx4x];
	mat[~~idx2y~~][~~idx2x~~] = mat[idx3y][idx3x];		mat[idx4y][idx4x] = mat[idx3y][idx3x];
	mat[idx3y][idx3x] = mat[~~idx4y~~][~~idx4x~~];		mat[idx3y][idx3x] = mat[idx2y][idx2x];
	mat[~~idx4y~~][~~idx4x~~] = tmp;		mat[idx2y][idx2x] = tmp;
	}		}
	}		}

KockaAdmiralac: K1P 2022, treba još da proverim da li rotateMatrixClockwise zaista radi

2023-04-04T14:28:59Z

K1P 2022, treba još da proverim da li rotateMatrixClockwise zaista radi

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

{{tocright}}
'''Поправни први колоквијум 2022. године''' одржан је 7. маја и трајао је 90 минута. Поставка овог рока у тренутку писања није доступна са странице предмета, али ће вероватно бити у будућности.

== 1. задатак ==
=== Поставка ===
Објаснити технику оптимизације рада кеш меморије хардверским довлачењем унапред (''Hardware Prefetching''). Дати по један пример програма код кога се могу уочити позитивне негативне стране овог приступа.

=== Решење ===
Хардверско довлачење унапред функционише, у својој најједноставнијој варијанти, тако што након довлачења једног блока кеша хардвер (процесор/контролер кеш меморије) сам довуче следећи блок из оперативне меморије у кеш, очекујући да ће процесор следеће искоритити тај блок. У својим компликованијим варијантама, хардвер може да ово спроводи тек након ''n''-тог секвенцијалног довлачења блока из оперативне меморије. У суштини, позитивне стране се могу уочити када је претпоставка да треба довући следећи блок исправна, а негативне када није:
<syntaxhighlight lang="cpp">
// Овде ће се блокови довлачити један за другим, и хардверско довлачење ће нам у томе помоћи.
for (int i = 0; i < n; ++i) {
sum += niz[i];
}

// Овде ће се прво користити један податак из првог блока, затим из неког петог, па деветог...
// хардверско довлачење ће сваки пут довлачити погрешан блок унапред, и то може (али не мора)
// да одмогне.
for (int x = 0; x < nx; ++x) {
for (int y = 0; y < ny; ++y) {
sum += mat[y][x];
}
}
</syntaxhighlight>

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

Величина[sic] података су: <code>sizeof(int)</code> = 32 bit, <code>sizeof(bool) = sizeof(char)</code> = 8 bit, адресе се[sic] су ширине 32 бита.

Потребно је написати функцију <syntaxhighlight lang="cpp" inline>void rotateMatrixClockwise(int** mat, int n)</syntaxhighlight>, која ротира квадратну матрицу у смеру казаљке на сату, где је <code>int** mat</code> показивач на матрицу, а <code>int n</code> величина матрица (<code>n</code> × <code>n</code>) где је <code>n</code> веће од 0 и дељиво је са 16. Приликом писања програма, обратити пажњу на карактеристике кеш меморије и искорити[sic] је тако да приликом извршавања функције буде што мање cache MISS.
{| class="wikitable"
|+ Стање матрице пре ротације.
| 1 || 2 || ⋯ || 15 || 16
|-
| 17 || 18 || ⋯ || 31 || 32
|-
| ⋮ || ⋮ || ⋱ || ⋮ || ⋮
|-
| 225 || 226 || ⋯ || 239 || 240
|-
| 241 || 242 || ⋯ || 255 || 256
|}
{| class="wikitable"
|+ Стање матрице после ротације.
| 241 || 225 || ⋯ || 17 || 1
|-
| 242 || 226 || ⋯ || 18 || 2
|-
| ⋮ || ⋮ || ⋱ || ⋮ || ⋮
|-
| 255 || 239 || ⋯ || 31 || 15
|-
| 256 || 240 || ⋯ || 32 || 16
|}

=== Решење ===
Идеја алгоритма јесте поделити целу матрицу на четири дела, тако да се из горњег левог елементи премештају у горњи десни, из њега у доњи десни, из њега у доњи леви и на крају назад у горњи леви. Сваки од тих делова затим делимо на блокове од 16 × 16 <code>int</code> (сваки од њих заузима 16 блокова кеш меморије), податке копирамо између њих, па пређемо на следећи такав блок. Четири блока од 16 × 16 <code>int</code> заузимају <math>4 \cdot 16 \cdot 16 \cdot 4B = 4KiB</math>, тако да сигурно сви стају у кеш меморију одједном. Са оваквим кеш искоришћењем, повећавање величине блока не би требало да донесе нарочита побољшања у перформансама, јер је кеш већ максимално искоришћен.
<syntaxhighlight lang="cpp">
void rotateMatrixClockwise(int** mat, int n) {
const int nHalf = n >> 1;
for (int blockY = 0; (blockY << 4) < nHalf; ++blockY) {
// Померај тренутног блока по Y оси
const int offsetY = blockY << 4;
for (int blockX = 0; (blockX << 4) < nHalf; ++blockX) {
// Померај тренутног блока по X оси
const int offsetX = blockX << 4;
for (int y = offsetY; y < offsetY + 16 && y < nHalf; ++y) {
for (int x = offsetX; x < offsetX + 16 && x < nHalf; ++x) {
const int idx1x = x;
const int idx1y = y;
const int idx2x = n - y - 1;
const int idx2y = x;
const int idx3x = n - x - 1;
const int idx3y = n - y - 1;
const int idx4x = y;
const int idx4y = n - x - 1;
const int tmp = mat[idx1y][idx1x];
mat[idx1y][idx1x] = mat[idx2y][idx2x];
mat[idx2y][idx2x] = mat[idx3y][idx3x];
mat[idx3y][idx3x] = mat[idx4y][idx4x];
mat[idx4y][idx4x] = tmp;
}
}
}
}
}
</syntaxhighlight>

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

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

KockaAdmiralac: /* Решење */ Ovo je rotiralo u obrnutom smeru, sad rotira u dobrom

KockaAdmiralac: K1P 2022, treba još da proverim da li rotateMatrixClockwise zaista radi