АОР2/К1 2023

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

1. задатак

Поставка

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

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

Решење

SIDE алгоритам замене садржи један показивач по сету који показује на следећи блок за замену. Лево од тог блока је заштићен сегмент, а десно угрожен. Када се деси hit, уколико се он десио у угроженом сегменту, показивач се поставља десно од места на ком се десио. Када се деси miss, замењује се блок на који показује показивач, а показивач се затим инкрементира.

Блокови у сету током времена са показивачем.

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.

Дат је програм који коришћењем Собеловог филтера проналази све ивице на задатој слици. У матрици image се налазе реалне вредности типа double (ширине 64 бита) које представљају боју пиксела оригиналне слике (слика је дата као палета сивих боја). Матрица edges представља резултујућу слику у којој су све ивице обојене белом бојом, док је остатак слике црн. Претпоставити да ниједна матрица на почетку није учитана у кеш меморију, као и да су прве ћелије поравнате са блоком кеш меморије. Матрице су смештене по редовима и истих су димензија.

#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 );
        }
    }
}

1. Уколико се зна да је оригинална слика димезија^[sic] 8x16, наћи број промашаја приликом приступа кеш меморији. Узети у обзир само промашаје чији је узрок приступ матрици image.
2. Потребно је оптимизовати дати код тако да се резултат програма не промени, а да се при томе искористе карактеристике дате кеш меморије. Није дозвољено коришћење наменских инструкција за манипулацијом кеш меморије. У програму је доступно за коришћење још 5 регистара опште намене.

Решење

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

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

Поред тога, можемо да урадимо loop unrolling петље која множи са матрицама GX и GY, и тиме и њих уклонимо, као и да сместимо неке често коришћене променљиве у регистре. Дати код затим испада овако:

#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);
            }
        }
    }
}