KockaAdmiralac: K1 2022

2023-04-04T12:05:31Z

K1 2022

Нова страница

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

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

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

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

Величина података су <code>sizeof(int)</code> = 32 bit, <code>sizeof(bool) = sizeof(char)</code> = 8 bit, адресе се<sup>[sic]</sup> су ширине 32 бита. Програм се извршава на процесору који поседује кеш меморију чија је величина блока 64 бита. Остале карактерситике<sup>[sic]</sup> кеш меморије нису доступне.
<div class="abc-list">
# Трансформисати методу <code>communicationUntilCount</code> коришћењем ''Loop fusion'' начина оптимизације кода.
# Преправити решење под а) предлагањем нове структуре података прилагођене за бољу искоришћеност кеш меморије не мењајући потпис методе <code>communicationUntilCount</code>.
# Преправити решење под а) предлагањем нове структуре података прилагођене за бољу искоришћеност кеш меморије при чему је дозвољено мењање потписа методе <code>communicationUntilCount</code>.
</div>
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

=== Решење ===
Након ''Loop fusion'' добијамо следећи код:
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>
<code>Log</code> структуру података можемо преуредити на следећи начин, тако што податке који нису релевантни за дату методу одвојимо у нову структуру која не мора бити чувана заједно са осталим подацима:
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>
На овај начин, уместо четири блока кеша (један за <code>from</code> и <code>to</code> показиваче, један за <code>time</code>, и два за сваку <code>PC</code> структуру) регуларно довлачимо два блока по логу (један за <code>fromIP</code> и <code>toIP</code> и један за <code>time</code>).

Уколико би нам било дозвољено преуређивање потписа методе, могли бисмо да одвојимо <code>fromIP</code>, <code>toIP</code> и <code>time</code> у одвојене низове који се прослеђују као одвојени аргументи:
<syntaxhighlight lang="cpp">
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;
}
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:АОР2]]

АОР2/К1 2022 - Историја измена

KockaAdmiralac: K1 2022