AOR2/K1 2022

Prvi kolokvijum 2022. godine održan je 31. marta i trajao je 90 minuta. Postavka ovog roka u trenutku pisanja nije dostupna sa stranice predmeta, ali će verovatno biti u budućnosti.

1. zadatak

Postavka

Objasniti tehniku optimizacije rada keš memorije koja koristi predviđanje puta (Way Prediction). Šta je potrebno da postoji kod procesora i kod keš memorije da bi data tehnika mogla da se primeni.

Rešenje

Way Prediction podrazumeva da je naša keš memorija set-asocijativna. Stoga, blok se u keš memoriji može pronaći u jednoj od više banki keša, a tačan podatak će biti propušten kroz jedan multiplekser kada se odredi u kojoj banci se on nalazi. Ono što nam Way Prediction omogućava jeste da mi kroz taj multiplekser propustimo podatak iz jedne banke za koju smo prethodno odredili da se u njoj najverovatnije nalazi podatak. Sa dovoljno dobrim algoritmom predviđanja, gubici pri pogrešnom predviđanju bivaju nadjačani dobicima pri tačnom.

2. zadatak

Postavka

Potrebno je delove datog programa optimizovati. Program učitava niz logova (Log[]) i smešta ih u memoriju. Smatrati da je početna adresa niza za čuvanje logova poravnata sa blokom keša. Nad nizom primenjuje se metoda int communicationUntilCount(const Log[] logs, int n, const char[] IP, int time). Metoda vraća broj logova u kojoj učestvuje računar sa zadatom IP adresom do zadatog vremena (int time). Niz logova dužine n (int n) je zadat parametrom const Log[] logs.

Veličina podataka su sizeof(int) = 32 bit, sizeof(bool) = sizeof(char) = 8 bit, adrese se^[sic] su širine 32 bita. Program se izvršava na procesoru koji poseduje keš memoriju čija je veličina bloka 64 bita. Ostale karaktersitike^[sic] keš memorije nisu dostupne.

1. Transformisati metodu communicationUntilCount korišćenjem Loop fusion načina optimizacije koda.
2. Prepraviti rešenje pod a) predlaganjem nove strukture podataka prilagođene za bolju iskorišćenost keš memorije ne menjajući potpis metode communicationUntilCount.
3. Prepraviti rešenje pod a) predlaganjem nove strukture podataka prilagođene za bolju iskorišćenost keš memorije pri čemu je dozvoljeno menjanje potpisa metode 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;
}

Rešenje

Nakon Loop fusion dobijamo sledeći kod:

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 strukturu podataka možemo preurediti na sledeći način, tako što podatke koji nisu relevantni za datu metodu odvojimo u novu strukturu koja ne mora biti čuvana zajedno sa ostalim podacima:

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

Na ovaj način, umesto četiri bloka keša (jedan za from i to pokazivače, jedan za time, i dva za svaku PC strukturu) regularno dovlačimo dva bloka po logu (jedan za fromIP i toIP i jedan za time).

Ukoliko bi nam bilo dozvoljeno preuređivanje potpisa metode, mogli bismo da odvojimo fromIP, toIP i time u odvojene nizove koji se prosleđuju kao odvojeni argumenti:

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