АОР2/К1П 2023

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Поправни први колоквијум 2023. године одржан је 12. маја и трајао је 90 минута.

1. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

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

2. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

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

Дат је програм који имплементира Stencil оператор. У матрици current се налазе реалне вредности типа double (ширине 64 бита). Матрица next представља резултат операције. Претпоставити да ниједна матрица на почетку није учитана у кеш меморију, као и да су прве ћелије матрица поравнате са блоком кеш меморије. Матрице су смештене у меморији тако што је свака 2D подматрица смештена по врстама, а подматрице се налазе једна до друге у меморији.

void stencil ( double *current, double *next, int nx, int ny, int nz, double f ) {
    for (int i = 1; i < (nx - 1); ++i ) {
        for( int j = 1; j < (ny - 1); ++j ) {
            for( int k = 1; k < (nz - 1); ++k ) {
                double ku  = current[index3D ( nx, ny, i    , j    , k + 1)];
                double kd  = current[index3D ( nx, ny, i    , j    , k - 1)];
                double ju  = current[index3D ( nx, ny, i    , j + 1, k    )];
                double jd  = current[index3D ( nx, ny, i    , j - 1, k    )];
                double iu  = current[index3D ( nx, ny, i + 1, j    , k    )];
                double id  = current[index3D ( nx, ny, i - 1, j    , k    )];
                double c   = current[index3D ( nx, ny, i    , j    , k    )];
                double sum = ku + kd + ju + jd + iu + id;

                next[index3D( nx, ny, i, j, k)] = sum * f - c * (1 - f);
            }
        }
    }
}

1. Уколико се зна да је оригинална слика димензија 8x8x8, наћи број промашаја приликом приступа кеш меморији. Узети у обзир само промашаје чији је узрок приступ матрици current
2. Потребно је оптимизовати дати код тако да се резултат програма не промени, а да се при томе искористе карактеристике дате кеш меморије. Није дозвољено коришћење наменских инструкција за манипулацију кеш меморије. У програму је доступно за коришћење још 10 регистара опште намене.