AOR2/Jul 2022

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

Julski rok 2022. godine održan je 2. jula i trajao je 90 minuta. Na ispitu je takođe bio podeljen podsetnik vektorskih instrukcija sa dokumentacijom AVX instrukcija sa Intelovog zvaničnog sajta.

1. zadatak

Postavka

Opisati tehniku optimizacije vektorskih instrukcija koja se zasniva na dohvatanju izabranih elemenata (Scatter-gather) prilikom pristupa podacima. Dati primer instrukcija procesora koje omogućavaju ovu tehniku i primer programa kod koga se jasno vidi prednost korišćenja ove tehnike.

Rešenje

Ova tehnika nam dozvoljava da na osnovu određene maske izaberemo koji elementi nekog niza se smeštaju u vektorski registar, izvršimo obradu nad tim elementima i na kraju ih vratimo nazad u odgovarajući niz. Na primer, ukoliko imamo sledeći C kod: 

for (int i = 0; i < n; ++i) {
    A[K[i]] += C[M[i]];
}

on bi na nekom procesoru sa ovakvim instrukcijama podržanim mogao da se prevede u sledeće: 

...
LV V1, K
LV V2, M
LVI V3, (A+V1)
LVI V4, (C+V2)
ADDVV V3, V3, V4
SVI V3, (A+V1)
...

2. zadatak

Postavka

Data je funkcija int elementsInRange(const unsigned int* input, int n, int min, int max) koja za celobrojne elemente niza zadatog pokazivačem input i dužine n prebrojava koliko ima elemenata u intervalu [min, max]. Smatrati da je n > 0. Elementi niza su celi brojevi int (32 bit).

Potrebno je prepraviti kod tako da ima isti rezultat izvršavanja korišćenjem vektorskih instrukcija koje su date u prilogu ispita. 

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

Rešenje

Ispod je data tražena implementacija funkcije kao i ostatak programa koji testira performanse i uspešnost ove reimplementacije: 

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

Rešenje prevesti korišćenjem komande g++ -march=native fajl.cpp.

3. zadatak

Postavka

Opisati tehniku korišćenja keša za čuvanje tragova izvršavanja (Trace cache). Dati primer mesta u protočnoj obradi gde se ovaj keš može nalaziti i obrazložiti odgovor. Šta predstavljaju ulazi i izlazi i opisati po čemu se ovaj keš razlikuje od obične keš memorije.

Rešenje

Trace cache se koristi u fazi prethodnog dekodovanja instrukcija, odnosno u vreme kada se CISC instrukcije prevode u RISC instrukcije naše mikroarhitekture. On prati na koji način se izvršava naš program, i na osnovu toga vraća naredne dekodovane RISC instrukcije za izvršavanje. Razlika od običnog keša jeste u tome što može na istoj adresi biti više različitih sekvenci instrukcija (tragova izvršavanja) u zavisnosti od programskog toka, pa se neke instrukcije mogu prevoditi i čuvati na više mesta. Zbog ovoga je keš tragova izvršavanja dosta komplikovaniji od keša za mikrooperacije, pa se ne isplati ubacivati ga u svakoj seriji nekog procesora.

4. zadatak

Postavka

Razmatra se računarski sistem u kome se izvršavanje određene instrukcija odvija u 6 faza pomoću izmenjenog procesora sa standardnom protočnom obradom (slika 4.1.). U procesor sa standardom protočnom obradom je dodata kao drugi stepen jedinica PD (Instruction PreDecode) koji[sic] obavlja transformaciju instrukcija zadate arhitekture u instrukcije RISC arhitekture. Smatrati da pristup memoriji traje dva signala takta. Arhitektura procesora definiše 16 registra[sic] opšte namene. Adrese i podaci su veličine 16 bita.

Slika 4.1. — organizacija procesora
  1. Napisati sekvencu instrukcija (mikroinstrukcija) ciljne RISC arhitekture u koju se obavlja preslikavanje za deo instrukcijskog seta iz tabele 4.1. izvorišne CISC arhitekture. Ukoliko je potrebno proširiti broj registara opšte namene u registarskom fajlu, onda treba za svaki dodat registar napisati čemu služi. Registar R13 predstavlja ukazivač na vrh steka (SP) i pokazuje na poslednju slobodnu lokaciju. Stek raste prema višim adresama. Registar R14 predstavlja ukazivač na baznu adresu steka (BP). Registar R0 se koristi kao akumulator. Bit PSWI u PSW se nalazi na poziciji 3, bit PSWC u PSW se nalazi na poziciji 2. U tabeli 4.1. akcije nisu optimizovano napisane, već opisno.
  2. Nacrtati format instrukcija ciljne RISC arhitekture (na osnovu instrukcija iz tabele 4.1.).
Tabela 4.1. — deo instrukcijskog seta procesora
Asemblerska instrukcija Akcija Mikro instrukcije
ADDB Rx 
AX15..8 = 0
AX7..0 = AX7..0 + Rx7..0
ENTER immed 
PUSH BP
BP = SP
SP = SP + immed
INTD 
PSWI = 0
POPPC 
POP PC
SUB (adr) 
AX = AX - MEM[MEM[adr]]
LOOPZ disp 
R12 = R12 - 1
IF R12 == 0 THEN
    PC = PC + disp
LD +(Rx) 
Rx = Rx - 1
ACC = MEM[Rx]
SUBC (adr) 
IF PSWC == 1 THEN
    ACC = ACC - MEM[MEM[adr]] - 1
ELSE
    ACC = ACC - MEM[MEM[adr]]

Rešenje

Pretpostavlja se da se pod AX registrom u zadatku misli na akumulator. Uvodimo registre:

  • R16: privremeni registar
  • R17: PSW
  • R18: vrednost 0
  • R19: još jedan privremeni registar
Rešenje četvrtog zadatka.
Asemblerska instrukcija Akcija Mikro instrukcije Komentar
ADDB Rx 
AX15..8 = 0
AX7..0 = AX7..0 + Rx7..0

ADD R0, R0, Rx
ANDIS R0, R0, #00FF
Treća instrukcija ažurira PSW kako bi postavila N i Z bitove.
ENTER immed 
PUSH BP
BP = SP
SP = SP + immed

ST R14, (R13)0
ADDI R14, R13, #2
ADDI R13, R14, #immed
Kako kroz donji multiplekser u ST instrukciji puštamo neposrednu vrednost, ovde bi bilo logično da stoji STI, ali se u materijalima ne koristi tako.
INTD 
PSWI = 0

ANDI R17, R17, #FFF7
Nije postavljen S fleg jer se ne koristi PSW izlaz iz ALU.
POPPC 
POP PC

LD R16, (R13)-1
ADDI R13, R13, #-1
BEQZ R18, (R18+R16)
U poslednjoj instrukciji se kroz gornji multiplekser propušta vrednost R18 (0), koja se koristi i kao uslov skoka, a kroz donji vrednost R16, koja sadrži željenu vrednost PC, pa stoga i specifičan način obeležavanja (koji je ekvivalentan sa (R16)0).
SUB (adr) 
AX = AX - MEM[MEM[adr]]

LD R16, (R18)adr
LD R16, (R16)0
SUBS R0, R0, R16
Hazard po podacima između prve i druge instrukcije.
LOOPZ disp 
R12 = R12 - 1
IF R12 == 0 THEN
    PC = PC + disp

SUB R12, R12, #1
BEQZPI R12, (PC)disp
LD +(Rx) 
Rx = Rx - 1
ACC = MEM[Rx]

LDS R0, (Rx)-1
ADDI Rx, Rx, #-1
Obrnut redosled instrukcija od očekivanog kako se ne bi stvarali hazardi instrukcijama nakon ove.
SUBC (adr) 
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
Zbog uvedenog registra R19, ovde nema hazarda po podacima. Ukoliko ne bismo uveli R19, ne bismo imali akcije da izvršavamo između LD instrukcija pa bi na tom mestu bio hazard po podacima.

Koristimo ukupno sedam RISC instrukcija u ovom setu:

  1. LD
  2. ST
  3. ADD
  4. SUB
  5. AND
  6. LSR
  7. BEQZ

Ovo nam ostavlja sledeći format instrukcije:

Format instrukcije u četvrtom zadatku
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
Kod PIS flegovi Odredišni registar Izvorišni registar 1 Izvorišni registar 2 Neposredna vrednost

Podsetnik

U podsetniku je bila data dokumentacija za sledeće instrukcije:

  • _mm256_loadu_si256
  • _mm256_set_epi32
  • _mm256_cmpgt_epi32
  • _mm256_mul_epi32
  • _mm256_storeu_epi32
  • _mm256_blendv_epi32
  • _mm256_add_epi32

Dokumentacija za ove instrukcije može se naći sa zvaničnog Intelovog sajta i ovde neće biti ponovljena.

Instrukcija _mm256_blendv_epi32 koja je bila data zapravo ne postoji, ali se umesto nje na isti način može koristiti instrukcija _mm256_blendv_epi8 (videti rešenje iznad).

Preuzeto iz „https://siwiki.rs/w/index.php?title=АОР2/Јул_2022&oldid=6225”