АОР2/К1 2022

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

1. задатак

Поставка

Објаснити технику оптимизације рада кеш меморије која користи предвиђање пута (Way Prediction). Шта је потребно да постоји код процесора и код кеш меморије да би дата техника могла да се примени.

Решење

Way Prediction подразумева да је наша кеш меморија сет-асоцијативна. Стога, блок се у кеш меморији може пронаћи у једној од више банки кеша, а тачан податак ће бити пропуштен кроз један мултиплексер када се одреди у којој банци се он налази. Оно што нам Way Prediction омогућава јесте да ми кроз тај мултиплексер пропустимо податак из једне банке за коју смо претходно одредили да се у њој највероватније налази податак. Са довољно добрим алгоритмом предвиђања, губици при погрешном предвиђању бивају надјачани добицима при тачном.

2. задатак

Поставка

Потребно је делове датог програма оптимизовати. Програм учитава низ логова (Log[]) и смешта их у меморију. Сматрати да је почетна адреса низа за чување логова поравната са блоком кеша. Над низом примењује се метода int communicationUntilCount(const Log[] logs, int n, const char[] IP, int time). Метода враћа број логова у којој учествује рачунар са задатом IP адресом до задатог времена (int time). Низ логова дужине n (int n) је задат параметром const Log[] logs.

Величина података су sizeof(int) = 32 bit, sizeof(bool) = sizeof(char) = 8 bit, адресе се^[sic] су ширине 32 бита. Програм се извршава на процесору који поседује кеш меморију чија је величина блока 64 бита. Остале карактерситике^[sic] кеш меморије нису доступне.

1. Трансформисати методу communicationUntilCount коришћењем Loop fusion начина оптимизације кода.
2. Преправити решење под а) предлагањем нове структуре података прилагођене за бољу искоришћеност кеш меморије не мењајући потпис методе communicationUntilCount.
3. Преправити решење под а) предлагањем нове структуре података прилагођене за бољу искоришћеност кеш меморије при чему је дозвољено мењање потписа методе communicationUntilCount.

struct PC {
    char IP[4];
    char* hostname;
};

struct Log {
    int code;
    char type;
    PC* from;
    PC* to;
    char severity;
    int time;
};

int communicationUntilCount(const Log logs[], int n, const char IP[], int time) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        bool ok = logs[i].time < time;
        for (int j = 0; j < 3 && ok; j++) {
            ok &= logs[i].from->IP[j] == IP[j];
        }
        if (ok) {
            cnt++;
        }
    }
    for (int i = 0; i < n; i++) {
        bool ok = logs[i].time < time;
        for (int j = 0; j < 3; j++) {
            ok &= logs[i].to->IP[j] == IP[j];
        }
        if (ok) {
            cnt++;
        }
    }
    return cnt;
}

Решење

Након Loop fusion добијамо следећи код:

struct PC {
    char IP[4];
    char* hostname;
};

struct Log {
    int code;
    char type;
    PC* from;
    PC* to;
    char severity;
    int time;
};

int communicationUntilCount(const Log logs[], int n, const char IP[], int time) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        bool ok = logs[i].time < time;
        for (int j = 0; j < 3 && ok; j++) {
            // Претпоставка: from и to никада неће бити исти (јер то нема много смисла).
            ok &= (logs[i].from->IP[j] == IP[j]) | (logs[i].to->IP[j] == IP[j]);
        }
        if (ok) {
            cnt++;
        }
    }
    return cnt;
}

Log структуру података можемо преуредити на следећи начин, тако што податке који нису релевантни за дату методу одвојимо у нову структуру која не мора бити чувана заједно са осталим подацима:

struct LogMisc {
    int code;
    char type;
    char severity;
    char* fromHostname;
    char* toHostname;
};

struct Log {
    // B0: 4 * 8 = 32bit
    char fromIP[4];
    // B0: 4 * 8 = 32bit
    char toIP[4];
    // B1: 32bit
    int time;
    // B1: 32bit
    LogMisc* misc;
};

int communicationUntilCount(const Log logs[], int n, const char IP[], int time) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        bool ok = logs[i].time < time;
        for (int j = 0; j < 3 && ok; j++) {
            ok &= (logs[i].fromIP[j] == IP[j]) | (logs[i].toIP[j] == IP[j]);
        }
        if (ok) {
            cnt++;
        }
    }
    return cnt;
}

На овај начин, уместо четири блока кеша (један за from и to показиваче, један за time, и два за сваку PC структуру) регуларно довлачимо два блока по логу (један за fromIP и toIP и један за time).

Уколико би нам било дозвољено преуређивање потписа методе, могли бисмо да одвојимо fromIP, toIP и time у одвојене низове који се прослеђују као одвојени аргументи:

int communicationUntilCount(const char fromIPs[], const char toIPs[], const int times[], const char IP[], int n, int time) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        bool ok = times[i] < time;
        for (int j = 0; j < 3 && ok; j++) {
            ok &= (fromIPs[(i << 2) + j] == IP[j]) | (toIPs[(i << 2) + j] == IP[j]);
        }
        if (ok) {
            cnt++;
        }
    }
    return cnt;
}