AOR2/Jun 2022

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

Junski rok 2022. godine održan je 11. juna 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 koračanju (Stride) prilikom pristupa podacima. Dati primer programa kod koga se jasno vidi prednost korišćenja ove tehnike.

Rešenje

Tehnika optimizacije vektorskih instrukcija sa koračanjem nam dozvoljava da u vektorski registar ne učitavamo elemente jedan za drugim već da ih učitava sa preskokom: ako je preskok n, prvo će se učitati element na indeksu 0, pa n, pa 2n i tako dok se ne napuni vektor. Primer programa gde bi ovo bilo korisno bi mogao da bude: 

for (int i = 0; i < n; ++i) {
    b[i] = a[i * 2] + a[i * 2 + 1];
}

koji bi se preveo u vektorske instrukcije na sledeći način: 

...
ADD R1, #a, 1
LVWS V1, a, #2
LVWS V2, (R1), #2
ADDV V3, V1, V2
SV V3, b
...

2. zadatak

Postavka

Data je funkcija void scale(const unsigned float* input, int n) koja realne elmente[sic] niza zadatog pokazivačem input i dužine n srazmerno umanjuje tako da svaki element niza bude u opsegu [0, 1]. Smatrati da je n > 0. Elementi niza su realni brojevi float (32 bit). Potrebno je prepraviti kod tako da ima isti rezultat izvršavanja korišćenjem vektorskih instrukcija koje su date u prilogu ispita. 

void scale(const unsigned float* input, int n) {
    unsigned float max = input[0];

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

    for (int i = 0; i < n; i++) {
        input[i] = input[i] / max;
    }
}

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>
#define N 65530

// Унија за приступ појединачним члановима вектора.
union V256 {
    __m256 v;
    float f[8];
};

// Напомена: битно је да се ови низови нађу на адреси која је поравната на
// 32 бита, иначе ће `_mm256_load_ps` бацити грешку.
// Овим редом су поређани како би евентуална прекорачења граница низа у SIMD
// имплементацији била ухваћена током провере једнакости низова.
float niz2[N];
float niz1[N];

// Оригинални код из задатка.
void scaleOriginal(float* input, int n) {
    float max = input[0];

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

    for (int i = 0; i < n; i++) {
        input[i] = input[i] / max;
    }
}

// SIMD-оптимизован код.
void scaleSIMD(float* input, int n) {
    if (n < 8) {
        // За мање од 8 елемената нема потребе ништа да паралелизујемо.
        scaleOriginal(input, n);
    } else {
        int roundedDownN = (n / 8) * 8;
        // Рачунамо максимуме осам-по-осам елемената низа.
        V256 maxVector;
        maxVector.v = _mm256_load_ps(input);
        for (int i = 8; i < roundedDownN; i += 8) {
            __m256 inputVector = _mm256_load_ps(input + i);
            maxVector.v = _mm256_max_ps(maxVector.v, inputVector);
        }
        // За извучене максимуме рачунамо који је од њих осам је прави максимум.
        float max = maxVector.f[0];
        for (int i = 1; i < 8; ++i) {
            if (maxVector.f[i] > max) {
                max = maxVector.f[i];
            }
        }
        // За преостале чланове низа такође рачунамо максимум.
        for (int i = roundedDownN; i < n; ++i) {
            if (input[i] > max) {
                max = input[i];
            }
        }
        // Како је на овом року дата документација за векторску инструкцију
        // множења, а не и за векторску инструкцију дељења, дељење максимумом
        // сводимо на множење са реципрочном вредношћу.
        float inverseMax = 1 / max;
        __m256 inverseMaxVector = _mm256_set_ps(inverseMax, inverseMax, inverseMax, inverseMax, inverseMax, inverseMax, inverseMax, inverseMax);
        for (int i = 0; i < roundedDownN; i += 8) {
            __m256 inputVector = _mm256_load_ps(input + i);
            __m256 multipliedVector = _mm256_mul_ps(inputVector, inverseMaxVector);
            _mm256_storeu_ps(input + i, multipliedVector);
        }
        // Процесирамо преостале елементе.
        for (int i = roundedDownN; i < n; ++i) {
            input[i] = input[i] / max;
        }
    }
}

int main() {
    // Пунимо улазне низове насумичним подацима.
    for (int i = 0; i < N; ++i) {
        float randomNumber = static_cast<float>(rand());
        niz1[i] = randomNumber;
        niz2[i] = randomNumber;
    }
    // Меримо време колико је потребно оригиналном коду да се изврши.
    std::chrono::steady_clock::time_point beginOriginal = std::chrono::steady_clock::now();
    scaleOriginal(niz1, N);
    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();
    scaleSIMD(niz2, N);
    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 кода.
    for (int i = 0; i < N; ++i) {
        if (abs(niz1[i] - niz2[i]) > 0.0001) {
            std::cerr << "Mismatch at index " << i << " (original: " << niz1[i] << ", SIMD: " << niz2[i] << ")" << std::endl;
            return EXIT_FAILURE;
        }
    }
    return EXIT_SUCCESS;
}

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

3. zadatak

Postavka

Posmatra se predviđanje skoka korišćenjem prediktora sa dva nivoa. Opisati opšti rad ovog prediktora. Ovaj prediktor se može javiti u više varijanti u zavisnosti od toga na koji način je implementiran svaki nivo. Opisati te varijante i naznačiti od čega zavise.

Rešenje

U ovom prediktoru se pojavljuju dva koncepta:

  • Branch History Register (BHR): registar u kome se čuva istorija skokova, da li je trebalo ili nije trebalo da se skoči.
  • Pattern History Table (PHT): tabela u kojoj se čuvaju automati stanja koji predviđaju skokove. Ova tabela se adresira korišćenjem BHR.

Osnovne varijacije ovog prediktora uvode više BHR i više PHT. Ukoliko uvedemo više BHR, jedan može pamtiti istoriju jednog (per address) ili grupe (per set) skokova. Analogno tome funkcioniše uvođenje više PHT.

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
BSWAP Rx 
AX = RX << 8 | RX >> 8
ENTER immed 
PUSH BP
BP = SP
SP = SP + immed
INTE 
PSWI = 1
LDPC 
AX = PC
NOT adr 
AX = !MEM[adr]
LOOPNZ disp 
R12 = R12 - 1
IF R12 != 0 THEN
    PC = PC + disp
ST -(Rx) 
Rx = Rx - 1
MEM[Rx] = ACC
ADDC (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
BSWAP Rx 
AX = RX << 8 | RX >> 8

LSRI R16, Rx, #8
LSLI R19, Rx, #8
ADDS R0, R16, R19
Poslednja instrukcija menja PSW kako bi se ažurirao N bit. Ovde ne smemo koristiti R0 za privremeno čuvanje vrednosti za slučaj da korisnik pozove BSWAP R0.
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.
INTE 
PSWI = 1

ORI R17, R17, #8
Nije postavljen S fleg jer se ne koristi PSW izlaz iz ALU.
LDPC 
AX = PC

ADDPI R0, PC, #0
NOT adr 
AX = !MEM[adr]

LD R0, (R18)adr
XORIS R0, R0, #FFFF
Hazard po podacima. Poslednja instrukcija menja PSW kako bi se ažurirao N bit.
LOOPNZ disp 
R12 = R12 - 1
IF R12 != 0 THEN
    PC = PC + disp

ADDI R12, R12, #-1
BNEZPI R12, PC, #disp
ST -(Rx) 
Rx = Rx - 1
MEM[Rx] = ACC

ST R0, (Rx)-1
ADDI Rx, Rx, #-1
Obrnut redosled instrukcija od očekivanog kako se ne bi stvarali hazardi instrukcijama nakon ove.
ADDC (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
ADDS 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 devet RISC instrukcija u ovom setu:

  1. LD
  2. ST
  3. ADD
  4. AND
  5. OR
  6. XOR
  7. LSL
  8. LSR
  9. BNEZ

Ovo nam ostavlja sledeći format instrukcije:

Format instrukcije u četvrtom zadatku
37 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_load_ps
  • _mm256_set_ps
  • _mm256_cmpgt_ps
  • _mm256_mul_ps
  • _mm256_storeu_ps
  • _mm256_blendv_ps
  • _mm256_max_ps

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

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