АОР2/Јун 2022

Јунски рок 2022. године одржан је 11. јуна и трајао је 90 минута. На испиту је такође био подељен подсетник векторских инструкција са документацијом AVX инструкција са Интеловог званичног сајта.

1. задатак

Поставка

Описати технику оптимизације векторских инструкција која се заснива на корачању (Stride) приликом приступа подацима. Дати пример програма код кога се јасно види предност коришћења ове технике.

Решење

Техника оптимизације векторских инструкција са корачањем нам дозвољава да у векторски регистар не учитавамо елементе један за другим већ да их учитава са прескоком: ако је прескок n, прво ће се учитати елемент на индексу 0, па n, па 2n и тако док се не напуни вектор. Пример програма где би ово било корисно би могао да буде:

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

који би се превео у векторске инструкције на следећи начин:

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

2. задатак

Поставка

Дата је функција void scale(const unsigned float* input, int n) која реалне елменте^[sic] низа задатог показивачем input и дужине n сразмерно умањује тако да сваки елемент низа буде у опсегу [0, 1]. Сматрати да је n > 0. Елементи низа су реални бројеви float (32 bit). Потребно је преправити код тако да има исти резултат извршавања коришћењем векторских инструкција које су дате у прилогу испита.

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

Решење

Испод је дата тражена имплементација функције као и остатак програма који тестира перформансе и успешност ове реимплементације:

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

Решење превести коришћењем команде g++ -march=native fajl.cpp.

3. задатак

Поставка

Посматра се предвиђање скока коришћењем предиктора са два нивоа. Описати општи рад овог предиктора. Овај предиктор се може јавити у више варијанти у зависности од тога на који начин је имплементиран сваки ниво. Описати те варијанте и назначити од чега зависе.

Решење

У овом предиктору се појављују два концепта:

• Branch History Register (BHR): регистар у коме се чува историја скокова, да ли је требало или није требало да се скочи.
• Pattern History Table (PHT): табела у којој се чувају аутомати стања који предвиђају скокове. Ова табела се адресира коришћењем BHR.

Основне варијације овог предиктора уводе више BHR и више PHT. Уколико уведемо више BHR, један може памтити историју једног (per address) или групе (per set) скокова. Аналогно томе функционише увођење више PHT.

4. задатак

Поставка

Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 4.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (Instruction PreDecode) који^[sic] обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра^[sic] опште намене. Адресе и подаци су величине 16 бита.

Слика 4.1. — организација процесора

1. Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 4.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор. Бит PSWI у PSW се налази на позицији 3, бит PSWC у PSW се налази на позицији 2. У табели 4.1. акције нису оптимизовано написане, већ описно.
2. Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 4.1.).

Табела 4.1. — део инструкцијског сета процесора

Асемблерска инструкција	Акција	Микро инструкције
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]]

Решење

Претпоставља се да се под AX регистром у задатку мисли на акумулатор. Уводимо регистре:

• R16: привремени регистар
• R17: PSW
• R18: вредност 0
• R19: још један привремени регистар

Решење четвртог задатка.

Асемблерска инструкција	Акција	Микро инструкције	Коментар
BSWAP Rx	AX = RX << 8 | RX >> 8	LSRI R16, Rx, #8 LSLI R19, Rx, #8 ADDS R0, R16, R19	Последња инструкција мења PSW како би се ажурирао N бит. Овде не смемо користити R0 за привремено чување вредности за случај да корисник позове BSWAP R0.
ENTER immed	PUSH BP BP = SP SP = SP + immed	ST R14, (R13)0 ADDI R14, R13, #2 ADDI R13, R14, #immed	Како кроз доњи мултиплексер у ST инструкцији пуштамо непосредну вредност, овде би било логично да стоји STI, али се у материјалима не користи тако.
INTE	PSWI = 1	ORI R17, R17, #8	Није постављен S флег јер се не користи PSW излаз из ALU.
LDPC	AX = PC	ADDPI R0, PC, #0
NOT adr	AX = !MEM[adr]	LD R0, (R18)adr XORIS R0, R0, #FFFF	Хазард по подацима. Последња инструкција мења PSW како би се ажурирао N бит.
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	Обрнут редослед инструкција од очекиваног како се не би стварали хазарди инструкцијама након ове.
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	Због уведеног регистра R19, овде нема хазарда по подацима. Уколико не бисмо увели R19, не бисмо имали акције да извршавамо између LD инструкција па би на том месту био хазард по подацима.

Користимо укупно девет RISC инструкција у овом сету:

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

Ово нам оставља следећи формат инструкције:

Формат инструкције у четвртом задатку

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
Код				PIS флегови			Одредишни регистар					Изворишни регистар 1					Изворишни регистар 2					Непосредна вредност

Подсетник

У подсетнику је била дата документација за следеће инструкције:

• _mm256_load_ps
• _mm256_set_ps
• _mm256_cmpgt_ps
• _mm256_mul_ps
• _mm256_storeu_ps
• _mm256_blendv_ps
• _mm256_max_ps

Документација за ове инструкције може се наћи са званичног Интеловог сајта и овде неће бити поновљена.