KockaAdmiralac: 8 * 16 * 8 / 64 = 16

2023-04-11T21:39:59Z

8 * 16 * 8 / 64 = 16

← Старија измена		Верзија на датум 11. април 2023. у 23:39
Ред 78:		Ред 78:

	=== Решење ===		=== Решење ===
	Слика димензија 8x16 стаје цела у кеш меморију величине 512KiB, па пошто је један блок 64B а <code>double</code> тип податка 64 бита значи да ће бити <math>\frac{8 \cdot 16 \cdot 8B}{64B} = 8</math> промашаја.		Слика димензија 8x16 стаје цела у кеш меморију величине 512KiB, па пошто је један блок 64B а <code>double</code> тип податка 64 бита значи да ће бити <math>\frac{8 \cdot 16 \cdot 8B}{64B} = 16</math> промашаја.

	За довољно велике матрице, може се десити да овај алгоритам избаци кеш линије из прва три реда при преласку у следећи и затим мора поново да их довлачи. Техника оптимизације за рад кеш меморије коју овде можемо да применимо јесте ''blocking'', тако да нам у наших 512KiB кеш меморије стану три реда матрице <code>image</code> и један ред матрице <code>edges</code>. То значи да један такав ред може да буде <math>\frac{512KiB}{4 \cdot 8B} = 2^{14}</math> <code>double</code> података дугачак.		За довољно велике матрице, може се десити да овај алгоритам избаци кеш линије из прва три реда при преласку у следећи и затим мора поново да их довлачи. Техника оптимизације за рад кеш меморије коју овде можемо да применимо јесте ''blocking'', тако да нам у наших 512KiB кеш меморије стану три реда матрице <code>image</code> и један ред матрице <code>edges</code>. То значи да један такав ред може да буде <math>\frac{512KiB}{4 \cdot 8B} = 2^{14}</math> <code>double</code> података дугачак.

KockaAdmiralac: Naš kolokvijum od četvrtka

2023-04-11T21:13:55Z

Naš kolokvijum od četvrtka

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

{{tocright}}
'''Први колоквијум 2023. године''' одржан је 6. априла и трајао је 75 минута (након што је професор Захарије померио време за 15 минута).

== 1. задатак ==
=== Поставка ===
Посматра се кеш меморија реализована у техници сет асоцијативног пресликавања са 4 улаза по сету која користи SIDE алгоритам замене. Објаснити овај алгоритам.

Дати садржаје свих улаза ''TAG'' дела кеш меморије после сваког приступа уколико се обављају приступи меморији за исти сет који имају следеће вредности поља Tag: 0, 1, 2, 1, 2, 5, 4, 2, 3, 6, 3.

=== Решење ===
SIDE алгоритам замене садржи један показивач по сету који показује на следећи блок за замену. Лево од тог блока је заштићен сегмент, а десно угрожен. Када се деси ''hit'', уколико се он десио у угроженом сегменту, показивач се поставља десно од места на ком се десио. Када се деси ''miss'', замењује се блок на који показује показивач, а показивач се затим инкрементира.
{| class="wikitable"
|+ Блокови у сету током времена са показивачем.
! ''Tag'' !! 0 !! 1 !! 2 !! 3 !! Резултат
|-
| 0 || 0 || → || || || MISS
|-
| 1 || 0 || 1 || → || || MISS
|-
| 2 || 0 || 1 || 2 || → || MISS
|-
| 1 || 0 || 1 || 2 || → || HIT
|-
| 2 || 0 || 1 || 2 || → || HIT
|-
| 5 || → 0 || 1 || 2 || 5 || MISS
|-
| 4 || 4 || → 1 || 2 || 5 || MISS
|-
| 2 || 4 || 1 || 2 || → 5 || HIT
|-
| 3 || → 4 || 1 || 2 || 3 || MISS
|-
| 6 || 6 || → 1 || 2 || 3 || MISS
|-
| 3 || → 6 || 1 || 2 || 3 || HIT
|}

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

Дат је програм који коришћењем Собеловог филтера проналази све ивице на задатој слици. У матрици <code>image</code> се налазе реалне вредности типа <code>double</code> (ширине 64 бита) које представљају боју пиксела оригиналне слике (слика је дата као палета сивих боја). Матрица <code>edges</code> представља резултујућу слику у којој су све ивице обојене белом бојом, док је остатак слике црн. Претпоставити да ниједна матрица на почетку није учитана у кеш меморију, као и да су прве ћелије поравнате са блоком кеш меморије. Матрице су смештене по редовима и истих су димензија.
<syntaxhighlight lang="c">
#include <math.h>
void sobel ( double *image, int rows, int columns, double *edges ) {
int GX[] = { -1, 0, 1, -2, 0, 2, -1, 0, 1 };
int GY[] = { -1, -2, -1, 0, 0, 0, 1, 2, 1 };

for ( int row = 1; row < ( rows - 1 ); ++row ) {
for ( int column = 1; column < ( columns - 1 ); ++column ) {
double gx = 0;
double gy = 0;

for ( int i = 0; i < 3; ++i ) {
for ( int j = 0; j < 3; ++j ) {
int image_row = row + i - 1;
int image_column = column + j - 1;

double image_value = image[image_row * columns + image_column];

int kernel_index = i * 3 + j;

gx += image_value * GX[kernel_index];
gy += image_value * GY[kernel_index];
}
}

edges[row * columns + column] = sqrt ( gx * gx + gy * gy );
}
}
}
</syntaxhighlight>
<div class="abc-list">
# Уколико се зна да је оригинална слика димезија<sup>[sic]</sup> 8x16, наћи број промашаја приликом приступа кеш меморији. Узети у обзир само промашаје чији је узрок приступ матрици <code>image</code>.
# Потребно је оптимизовати дати код тако да се резултат програма не промени, а да се при томе искористе карактеристике дате кеш меморије. Није дозвољено коришћење наменских инструкција за манипулацијом кеш меморије. У програму је доступно за коришћење још 5 регистара опште намене.
</div>

=== Решење ===
Слика димензија 8x16 стаје цела у кеш меморију величине 512KiB, па пошто је један блок 64B а <code>double</code> тип податка 64 бита значи да ће бити <math>\frac{8 \cdot 16 \cdot 8B}{64B} = 8</math> промашаја.

За довољно велике матрице, може се десити да овај алгоритам избаци кеш линије из прва три реда при преласку у следећи и затим мора поново да их довлачи. Техника оптимизације за рад кеш меморије коју овде можемо да применимо јесте ''blocking'', тако да нам у наших 512KiB кеш меморије стану три реда матрице <code>image</code> и један ред матрице <code>edges</code>. То значи да један такав ред може да буде <math>\frac{512KiB}{4 \cdot 8B} = 2^{14}</math> <code>double</code> података дугачак.

Поред тога, можемо да урадимо ''loop unrolling'' петље која множи са матрицама <code>GX</code> и <code>GY</code>, и тиме и њих уклонимо, као и да сместимо неке често коришћене променљиве у регистре. Дати код затим испада овако:
<syntaxhighlight lang="c">
#include <math.h>
const int BLOCK_SIZE = 16384;
void sobel(double *image, const int rows, const int columns, double *edges) {
for (register int block = 0; block < columns / BLOCK_SIZE; ++block) {
for (register int row = 1; row < rows - 1; ++row) {
for (register int column = block * BLOCK_SIZE; column < columns - 1 && column < (block + 1) * BLOCK_SIZE; ++column) {
const double gx = -1 * image[(row - 1) * columns + (column - 1)] +
1 * image[(row - 1) * columns + (column + 1)] +
-2 * image[(row - 0) * columns + (column - 1)] +
2 * image[(row - 0) * columns + (column + 1)] +
-1 * image[(row + 1) * columns + (column - 1)] +
1 * image[(row + 1) * columns + (column + 1)];
const double gy = -1 * image[(row - 1) * columns + (column - 1)] +
-2 * image[(row - 1) * columns + (column - 0)] +
-1 * image[(row - 1) * columns + (column + 1)] +
1 * image[(row + 1) * columns + (column - 1)] +
2 * image[(row + 1) * columns + (column - 0)] +
1 * image[(row + 1) * columns + (column + 1)];
edges[row * columns + column] = sqrt(gx * gx + gy * gy);
}
}
}
}
</syntaxhighlight>

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

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

KockaAdmiralac: 8 * 16 * 8 / 64 = 16

KockaAdmiralac: Naš kolokvijum od četvrtka