АОР2/К1П 2022

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

1. задатак

Поставка

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

Решење

Хардверско довлачење унапред функционише, у својој најједноставнијој варијанти, тако што након довлачења једног блока кеша хардвер (процесор/контролер кеш меморије) сам довуче следећи блок из оперативне меморије у кеш, очекујући да ће процесор следеће искоритити тај блок. У својим компликованијим варијантама, хардвер може да ово спроводи тек након n-тог секвенцијалног довлачења блока из оперативне меморије. У суштини, позитивне стране се могу уочити када је претпоставка да треба довући следећи блок исправна, а негативне када није:

// Овде ће се блокови довлачити један за другим, и хардверско довлачење ће нам у томе помоћи.
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];
    }
}

2. задатак

Поставка

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

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

Потребно је написати функцију void rotateMatrixClockwise(int** mat, int n), која ротира квадратну матрицу у смеру казаљке на сату, где је int** mat показивач на матрицу, а int n величина матрица (n × n) где је n веће од 0 и дељиво је са 16. Приликом писања програма, обратити пажњу на карактеристике кеш меморије и искорити^[sic] је тако да приликом извршавања функције буде што мање cache MISS.

Стање матрице пре ротације.

1	2	⋯	15	16
17	18	⋯	31	32
⋮	⋮	⋱	⋮	⋮
225	226	⋯	239	240
241	242	⋯	255	256

Стање матрице после ротације.

241	225	⋯	17	1
242	226	⋯	18	2
⋮	⋮	⋱	⋮	⋮
255	239	⋯	31	15
256	240	⋯	32	16

Решење

Идеја алгоритма јесте поделити целу матрицу на четири дела, тако да се из горњег левог елементи премештају у горњи десни, из њега у доњи десни, из њега у доњи леви и на крају назад у горњи леви. Сваки од тих делова затим делимо на блокове од 16 × 16 int (сваки од њих заузима 16 блокова кеш меморије), податке копирамо између њих, па пређемо на следећи такав блок. Четири блока од 16 × 16 int заузимају $4 \cdot 16 \cdot 16 \cdot 4B = 4KiB$, тако да сигурно сви стају у кеш меморију одједном. Са оваквим кеш искоришћењем, повећавање величине блока не би требало да донесе нарочита побољшања у перформансама, јер је кеш већ максимално искоришћен.

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[idx4y][idx4x];
                    mat[idx4y][idx4x] = mat[idx3y][idx3x];
                    mat[idx3y][idx3x] = mat[idx2y][idx2x];
                    mat[idx2y][idx2x] = tmp;
                }
            }
        }
    }
}