Изворни код странице АОР2/Јул 2022

{{tocright}}
'''Јулски рок 2022. године''' одржан је 2. јула и трајао је 90 минута. На испиту је такође био подељен [[#Подсетник|подсетник векторских инструкција са документацијом AVX инструкција са Интеловог званичног сајта]].

== 1. задатак ==
=== Поставка ===
Описати технику оптимизације векторских инструкција која се заснива на дохватању изабраних елемената ('''''Scatter-gather''''') приликом приступа подацима. Дати пример инструкција процесора које омогућавају ову технику и пример програма код кога се јасно види предност коришћења ове технике.

=== Решење ===
Ова техника нам дозвољава да на основу одређене маске изаберемо који елементи неког низа се смештају у векторски регистар, извршимо обраду над тим елементима и на крају их вратимо назад у одговарајући низ. На пример, уколико имамо следећи C код:
<syntaxhighlight lang="c">
for (int i = 0; i < n; ++i) {
    A[K[i]] += C[M[i]];
}
</syntaxhighlight>
он би на неком процесору са оваквим инструкцијама подржаним могао да се преведе у следеће:
<syntaxhighlight lang="asm">
...
LV V1, K
LV V2, M
LVI V3, (A+V1)
LVI V4, (C+V2)
ADDVV V3, V3, V4
SVI V3, (A+V1)
...
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Дата је функција <syntaxhighlight lang="c" inline>int elementsInRange(const unsigned int* input, int n, int min, int max)</syntaxhighlight> која за целобројне елементе низа задатог показивачем <code>input</code> и дужине <code>n</code> пребројава колико има елемената у интервалу <code>[min, max]</code>. Сматрати да је n > 0. Елементи низа су цели бројеви <code>int</code> (32 bit).

Потребно је преправити код тако да има исти резултат извршавања коришћењем векторских инструкција које су дате у прилогу испита.
<syntaxhighlight lang="c">
int elementsInRange(const unsigned int* input, int n, int min, int max) {
    int result = 0;

    for (int i = 0; i < n; i++) {
        if (input[i] >= min && input[i] <= max)
            result = result + 1;
    }

    return result;
}
</syntaxhighlight>

=== Решење ===
Испод је дата тражена имплементација функције као и остатак програма који тестира перформансе и успешност ове реимплементације:
<syntaxhighlight lang="cpp">
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <immintrin.h>

const int N = 65530;
const int MIN = 0;
const int MAX = RAND_MAX / 10;

// Унија за приступ појединачним члановима вектора.
union V256I {
    __m256i v;
    int i[8];
};

// Низови за податке који се прослеђују функцијама.
unsigned int niz1[N];
unsigned int niz2[N];

// Оригинални код из задатка.
int elementsInRangeOriginal(const unsigned int* input, unsigned int n, unsigned int min, unsigned int max) {
    int result = 0;

    for (unsigned int i = 0; i < n; i++) {
        if (input[i] >= min && input[i] <= max)
            result = result + 1;
    }

    return result;
}

// SIMD-оптимизован код.
int elementsInRangeSIMD(const unsigned int* input, unsigned int n, unsigned int min, unsigned int max) {
    unsigned int roundedDownN = (n / 8) * 8;
    // Сви вектори потребни за рад функције.
    V256I resultVector;
    resultVector.v = _mm256_set_epi32(0, 0, 0, 0, 0, 0, 0, 0);
    __m256i minVector = _mm256_set_epi32(min, min, min, min, min, min, min, min);
    __m256i maxVector = _mm256_set_epi32(max, max, max, max, max, max, max, max);
    __m256i zeroVector = _mm256_set_epi32(0, 0, 0, 0, 0, 0, 0, 0);
    for (unsigned int i = 0; i < n; i += 8) {
        __m256i inputVector = _mm256_loadu_si256((__m256i*)(input + i));
        // _mm256_cmpgt_epi32 ће поставити све јединице на места где је испуњен
        // услов.
        __m256i minCompareVector = _mm256_cmpgt_epi32(inputVector, minVector);
        __m256i maxCompareVector = _mm256_cmpgt_epi32(maxVector, inputVector);
        // Остављамо све јединице на месту где су испуњена оба услова, и за
        // минимум и за максимум.
        __m256i blendedVector = _mm256_blendv_epi8(zeroVector, maxCompareVector, minCompareVector);
        // Напомена: све јединице заправо означавају број -1, па у овом вектору
        // чувамо негативне бројаче уместо позитивне.
        resultVector.v = _mm256_add_epi32(resultVector.v, blendedVector);
    }
    int result = 0;
    for (unsigned int i = 0; i < 8; ++i) {
        // Пошто смо изнад додавали негативне бројеве на резултат, овде морамо
        // да обрнемо знак да бисмо израчунали крајњи резултат како треба.
        result -= resultVector.i[i];
    }
    // Урачунавамо све преостале елементе у резултат.
    for (unsigned int i = roundedDownN; i < n; ++i) {
        if (input[i] >= min && input[i] <= max) {
            ++result;
        }
    }
    return result;
}

int main() {
    // Пунимо улазне низове насумичним подацима.
    for (int i = 0; i < N; ++i) {
        unsigned int randomNumber = static_cast<unsigned int>(rand());
        niz1[i] = randomNumber;
        niz2[i] = randomNumber;
    }
    // Меримо време колико је потребно оригиналном коду да се изврши.
    std::chrono::steady_clock::time_point beginOriginal = std::chrono::steady_clock::now();
    int resultOriginal = elementsInRangeOriginal(niz1, N, MIN, MAX);
    std::chrono::steady_clock::time_point endOriginal = std::chrono::steady_clock::now();
    std::cout << "Original: " << std::chrono::duration_cast<std::chrono::microseconds>(endOriginal - beginOriginal).count() << "ms" << std::endl;
    // Меримо време колико је потребно SIMD коду да се изврши.
    std::chrono::steady_clock::time_point beginSIMD = std::chrono::steady_clock::now();
    int resultSIMD = elementsInRangeSIMD(niz2, N, MIN, MAX);
    std::chrono::steady_clock::time_point endSIMD = std::chrono::steady_clock::now();
    std::cout << "SIMD:     " << std::chrono::duration_cast<std::chrono::microseconds>(endSIMD - beginSIMD).count() << "ms" << std::endl;
    // Упоређујемо резултате оригиналног и SIMD кода.
    if (resultOriginal != resultSIMD) {
        std::cerr << "Result mismatch (original: " << resultOriginal << ", SIMD: " << resultSIMD << ")" << std::endl;
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}
</syntaxhighlight>
Решење превести коришћењем команде <code>g++ -march=native fajl.cpp</code>.

== 3. задатак ==
=== Поставка ===
Описати технику коришћења кеша за чување трагова извршавања ('''''Trace cache'''''). Дати пример места у проточној обради где се овај кеш може налазити и образложити одговор. Шта представљају улази и излази и описати по чему се овај кеш разликује од обичне кеш меморије.

=== Решење ===
''Trace cache'' се користи у фази претходног декодовања инструкција, односно у време када се CISC инструкције преводе у RISC инструкције наше микроархитектуре. Он прати на који начин се извршава наш програм, и на основу тога враћа наредне декодоване RISC инструкције за извршавање. Разлика од обичног кеша јесте у томе што може на истој адреси бити више различитих секвенци инструкција (трагова извршавања) у зависности од програмског тока, па се неке инструкције могу преводити и чувати на више места. Због овога је кеш трагова извршавања доста компликованији од кеша за микрооперације, па се не исплати убацивати га у свакој серији неког процесора.

== 4. задатак ==
=== Поставка ===
Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 4.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (''Instruction PreDecode'') који<sup>[sic]</sup> обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра<sup>[sic]</sup> опште намене. Адресе и подаци су величине 16 бита.
[[Датотека:AOR2 organizacija PreDecode.svg|thumb|center|500px|Слика 4.1. — организација процесора]]
<div class="abc-list">
# Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 4.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор. Бит PSWI у PSW се налази на позицији 3, бит PSWC у PSW се налази на позицији 2. У табели 4.1. акције нису оптимизовано написане, већ описно.
# Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 4.1.).
</div>
{| class="wikitable"
|+ Табела 4.1. — део инструкцијског сета процесора
! Асемблерска инструкција
! Акција
! Микро инструкције
|-
| <code>ADDB Rx</code>
|
 AX<sub>15..8</sub> = 0
 AX<sub>7..0</sub> = AX<sub>7..0</sub> + Rx<sub>7..0</sub>
| 
|-
| <code>ENTER immed</code>
|
 PUSH BP
 BP = SP
 SP = SP + immed
| 
|-
| <code>INTD</code>
|
 PSWI = 0
| 
|-
| <code>POPPC</code>
|
 POP PC
| 
|-
| <code>SUB (adr)</code>
|
 AX = AX - MEM[MEM[adr]]
| 
|-
| <code>LOOPZ disp</code>
|
 R12 = R12 - 1
 IF R12 == 0 THEN
     PC = PC + disp
| 
|-
| <code>LD +(Rx)</code>
|
 Rx = Rx - 1
 ACC = MEM[Rx]
| 
|-
| <code>SUBC (adr)</code>
|
 IF PSWC == 1 THEN
     ACC = ACC - MEM[MEM[adr]] - 1
 ELSE
     ACC = ACC - MEM[MEM[adr]]
|}

=== Решење ===
Претпоставља се да се под AX регистром у задатку мисли на акумулатор. Уводимо регистре:
* R16: привремени регистар
* R17: PSW
* R18: вредност 0
* R19: још један привремени регистар
{| class="wikitable"
|+ Решење четвртог задатка.
! Асемблерска инструкција
! Акција
! Микро инструкције
! Коментар
|-
| <code>ADDB Rx</code>
|
 AX<sub>15..8</sub> = 0
 AX<sub>7..0</sub> = AX<sub>7..0</sub> + Rx<sub>7..0</sub>
|
 ADD R0, R0, Rx
 ANDIS R0, R0, #00FF
| Трећа инструкција ажурира PSW како би поставила N и Z битове.
|-
| <code>ENTER immed</code>
|
 PUSH BP
 BP = SP
 SP = SP + immed
|
 ST R14, (R13)0
 ADDI R14, R13, #2
 ADDI R13, R14, #immed
| Како кроз доњи мултиплексер у ST инструкцији пуштамо непосредну вредност, овде би било логично да стоји STI, али се у материјалима не користи тако.
|-
| <code>INTD</code>
|
 PSWI = 0
|
 ANDI R17, R17, #FFF7
| Није постављен S флег јер се не користи PSW излаз из ALU.
|-
| <code>POPPC</code>
|
 POP PC
|
 LD R16, (R13)-1
 ADDI R13, R13, #-1
 BEQZ R18, (R18+R16)
| У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R18 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC, па стога и специфичан начин обележавања (који је еквивалентан са <code>(R16)0</code>).
|-
| <code>SUB (adr)</code>
|
 AX = AX - MEM[MEM[adr]]
|
 LD R16, (R18)adr
 LD R16, (R16)0
 SUBS R0, R0, R16
| Хазард по подацима између прве и друге инструкције.
|-
| <code>LOOPZ disp</code>
|
 R12 = R12 - 1
 IF R12 == 0 THEN
     PC = PC + disp
|
 SUB R12, R12, #1
 BEQZPI R12, (PC)disp
|
|-
| <code>LD +(Rx)</code>
|
 Rx = Rx - 1
 ACC = MEM[Rx]
|
 LDS R0, (Rx)-1
 ADDI Rx, Rx, #-1
| Обрнут редослед инструкција од очекиваног како се не би стварали хазарди инструкцијама након ове.
|-
| <code>SUBC (adr)</code>
|
 IF PSWC == 1 THEN
     ACC = ACC - MEM[MEM[adr]] - 1
 ELSE
     ACC = ACC - MEM[MEM[adr]]
|
 LD R16, (R18)adr
 ANDI R19, R17, #4
 LD R16, (R16)0
 LSRI R19, R19, #2
 ADD R16, R16, R19
 SUBS R0, R0, R16
| Због уведеног регистра R19, овде нема хазарда по подацима. Уколико не бисмо увели R19, не бисмо имали акције да извршавамо између LD инструкција па би на том месту био хазард по подацима.
|}
Користимо укупно седам RISC инструкција у овом сету:
# LD
# ST
# ADD
# SUB
# AND
# LSR
# BEQZ
Ово нам оставља следећи формат инструкције:
{| class="wikitable"
|+ Формат инструкције у четвртом задатку
! 36 !! 35 !! 34 !! 33 !! 32 !! 31 !! 30 !! 29 !! 28 !! 27 !! 26 !! 25 !! 24 !! 23 !! 22 !! 21 !! 20 !! 19 !! 18 !! 17 !! 16 !! 15 !! 14 !! 13 !! 12 !! 11 !! 10 !! 9 !! 8 !! 7 !! 6 !! 5 !! 4 !! 3 !! 2 !! 1 !! 0
|-
| colspan="3" | Код
| colspan="3" | PIS флегови
| colspan="5" | Одредишни регистар
| colspan="5" | Изворишни регистар 1
| colspan="5" | Изворишни регистар 2
| colspan="16" | Непосредна вредност
|}

== Подсетник ==
У подсетнику је била дата документација за следеће инструкције:
* <code>_mm256_loadu_si256</code>
* <code>_mm256_set_epi32</code>
* <code>_mm256_cmpgt_epi32</code>
* <code>_mm256_mul_epi32</code>
* <code>_mm256_storeu_epi32</code>
* <code>_mm256_blendv_epi32</code>
* <code>_mm256_add_epi32</code>
Документација за ове инструкције може се наћи са [https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html званичног Интеловог сајта] и овде неће бити поновљена.

Инструкција <code>_mm256_blendv_epi32</code> која је била дата заправо не постоји, али се уместо ње на исти начин може користити инструкција <code>_mm256_blendv_epi8</code> (видети решење изнад).

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