AOR2/Jun 2023

Junski rok 2023. godine održan je 5. juna i trajao je 120 minuta.

1. zadatak

Postavka

[5p] Opisati tehniku optimizacije vektorskih instrukcija koja se zasniva na korišćenju registra maski vektora (Vector mask registers). Na primeru izračunavanja maksimuma korespondentnih elemenata niza (Z[i] = MAX(X[i], Y[i])) prikazati korišćenje ovog registra.

Rešenje

Registar maske vektora služi kako bi se određene operacije nad vektorima izvršile samo nad njihovim određenim članovima, time što na određenim bitovima registra maske stoje nule ili jedinice. Na primer, sledeći kod za računanje maksimuma:

for (int i = 0; i < n; ++i)
    if (X[i] > Y[i])
        Z[i] = X[i];
    else
        Z[i] = Y[i];

bi mogao da se prevede u sledeću sekvencu vektorskih instrukcija:

...
LV V1, X        # Учитавамо део низа X у вектор V1
LV V2, Y        # Учитавамо део низа Y у вектор V2
SGTVS.D V1, V2  # Постављамо регистар маске на 1 на местима где важи X[i] > Y[i]
MOVVV.D V3, V1  # Постављамо елементе V3 на елементе V1 на местима где је маска 1
MVFM V1, VM     # Учитавамо маску у V1
NOTV V1         # Негирамо V1
MVTM V1, VM     # Учитавамо V1 у маску
MOVVV.D V3, V2  # Постављамо елементе V3 на елементе V2 на местима где је маска 1
SV V3, Z        # Уписујемо део низа Z
...

2. zadatak

Postavka

[5p] Posmatra se predviđanje skoka korišćenjem gshare prediktora. Opisati rad ovog prediktora. Uporediti rad ovog prediktora i korelisanog prediktora koji koristi isti broj bita odgovarajućih ulaznih podataka.

Rešenje

gshare prediktor sadrži sledeće elemente:

• Branch History Register (BHR) koji funkcioniše kao shift registar koji čuva globalnu istoriju skokova (da li je uslov ispunjen ili nije),
• Pattern History Table (PHT) koja sadrži automate stanja koji određuju krajnja predviđanja, i
• heš funkciju koja kombinuje BHR i bitove adrese skoka kako bi adresirala PHT.

Za razliku od gshare, korelisani prediktor odvojeno adresira jednu od više PHT pomoću BHR, a zatim jedan od automata u okviru PHT pomoću adrese skoka. Može se primetiti da je korelisani prediktor, zbog svog većeg broja PHT, za iste širine ulaznih podataka dosta skuplji od gshare. Takođe se pokazalo da je većina ulaza u ovakve PHT neiskorišćeno, pa je gshare napravljen kako bi poboljšao ovo iskorišćenje i smanjio cenu proizvodnje korelisanog prediktora.

3. zadatak

Postavka

[10p] 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 3.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.^[sic] — organizacija procesora

1. Napisati sekvencu instrukcija (mikroinstrukcija) ciljne RISC arhitekture u koju se obavlja preslikavanje za deo instrukcijskog seta iz tabele 3.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, registar R12 se koristi kao brojački registar i kao takav ima posebne instrukcije koje ga koriste. U tabeli 3.1. akcije nisu optimizovano napisane, već opisno.
2. Nacrtati format instrukcija ciljne RISC arhitekture (na osnovu instrukcija iz tabele 3.1.).

Tabela 3.1. — deo instrukcijskog seta procesora

Asemblerska instrukcija	Akcija	Mikro instrukcije
SWP Rx	MEM[Rx] ↔ ACC
DEC	ACC = ACC - 1
RTS	POP PC
LOOP disp	R12 = R12 - 1 IF R12 == 0 THEN PC = PC + disp
JMP adr	PC = adr
ADD (adr)	ACC = ACC + MEM[MEM[adr]]
LDB Rx	ACC = 0.Rx7..0
STRLEN adr	ACC = 0 WHILE MEM[adr] != 0 DO ACC = ACC + 1 adr = adr + 1 END WHILE
VECADD adr	R1 = R1 + MEM[adr] R2 = R2 + MEM[adr] R3 = R3 + MEM[adr] R4 = R4 + MEM[adr]
MUL R1	TMP = ACC ACC = 0 FOR X = 0; X < R1; X++ DO ACC = ACC + TMP END FOR

Rešenje

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

• R16: privremeni registar
• R17: vrednost 0
• R18: još jedan privremeni registar

Rešenje trećeg zadatka.

Asemblerska instrukcija	Akcija	Mikro instrukcije	Komentar
SWP Rx	MEM[Rx] ↔ ACC	LD R0, (Rx)0 ADDIS R16, R0, #0 ST R16, (Rx)0	Ukoliko bi posle ove sekvence mikroinstrukcija došla mikroinstrukcija koja koristi memoriju, to bi bio hazard po podacima.
DEC	ACC = ACC - 1	ADDIS R0, R0, #-1
RTS	POP PC	LD R16, (R13)-1 ADDI R13, R13, #-1 BEQZ R17, (R17+R16)	U poslednjoj instrukciji se kroz gornji multiplekser propušta vrednost R17 (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).
LOOP disp	R12 = R12 - 1 IF R12 == 0 THEN PC = PC + disp	SUB R12, R12, #1 BEQZPI R12, (PC)disp
JMP adr	PC = adr	BEQZI R17, (R17)adr
ADD (adr)	ACC = ACC + MEM[MEM[adr]]	LD R16, (R17)adr LD R16, (R16)0 ADDS R0, R0, R16	Dešava se hazard po podacima između prve i druge i između druge i treće mikroinstrukcije.
LDB Rx	ACC = 0.Rx7..0	ANDIS R0, RX, #00FF
STRLEN adr	ACC = 0 WHILE MEM[adr] != 0 DO ACC = ACC + 1 adr = adr + 1 END WHILE	ADDI R0, R17, #0 LD R16, (R0)adr ADDIS R0, R0, #1 BNEZPI R16, (PC)-3 * len(mInst) ADDI R0, R0, #-1	Za ovu stavku je rečeno na kolokvijumu da može da se pretpostavi kako PC broji mikroinstrukcije umesto instrukcije. Glavne ideje su da se ukloni hazard time što radimo ADD instrukciju ispod LD, da se akumulator koristi umesto nekog novog registra za čuvanje adr (jer se svakako uvećava svake iteracije) i da nakon petlje koja obuhvata drugu, treću i četvrtu mikroinstrukciju moramo smanjiti akumulator za jedan, jer nam je prethodna petlja efektivno bila do-while umesto while.
VECADD adr	R1 = R1 + MEM[adr] R2 = R2 + MEM[adr] R3 = R3 + MEM[adr] R4 = R4 + MEM[adr]	LD R16, (R17)adr ADDI R18, R17, #adr LD R16, (R18)1 ADD R1, R1, R16 LD R16, (R18)2 ADD R2, R2, R16 LD R16, (R18)3 ADD R3, R3, R16 ADD R4, R4, R16	Razlog iz kog ova sekvenca mikroinstrukcija može izgledati čudno jeste izbegavanje hazarda po podacima. Sa učitavanjem prvog podatka počinje se već u prvoj mikroinstrukciji, ali kako u međuvremenu treba obaviti čuvanje adr u novom privremenom registru i započinjanje novog učitavanja, ona se ne sabira sa registrom R1 do četvrte mikroinstrukcije (kada je ta vrednost i dalje dostupna u odgovarajućem registru). Nakon toga se logika ponavlja nekoliko puta: započeli smo učitavanje narednog podatka, a dok se taj podatak učitava mi radimo sabiranje prethodno učitanog podatka sa odgovarajućim registrom. Kako je do devete mikroinstrukcije završeno učitavanje i poslednjeg podatka, možemo izvršiti poslednje sabiranje.
MUL R1	TMP = ACC ACC = 0 FOR X = 0; X < R1; X++ DO ACC = ACC + TMP END FOR	ADDI R16, R0, #0 ADDIS R0, R17, #0 ADDI R18, R1, #0 ADDS R0, R0, R16 ADDI R18, R18, #-1 BNEZPI R18, (PC)-3 * len(mInst) SUB R0, R0, R16	Ideja jeste da R16 koristimo kao prethodnu vrednost akumulatora i R18 kao brojač iteracija koji počinje od R1 i završava se sa 0. Ukoliko bi nam provera za R18 == 0 bila na vrhu, naša petlja bi se sastojala iz četiri mikroinstrukcije: provere, sabiranja, dekrementiranja i bezuslovnog skoka. Umesto toga, proveru stavljamo na dno pa se naša petlja sastoji od tri mikroinstrukcije (rezultujući u manjem ukupnom broju izvršenih mikroinstrukcija), ali zbog toga što smo opet efektivno napravili do-while petlju efekat poslednje iteracije moramo da poništimo na kraju. Kao i za STRLEN, za ovu stavku može da se pretpostavi kako PC broji mikroinstrukcije umesto instrukcije. (Na kolokvijumu je naknadno rečeno da je podatak u R1 označen, ali to u ovom rešenju nije uzeto u obzir jer takvo korišćenje i nema smisla.)

Koristimo ukupno sedam RISC instrukcija u ovom setu:

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

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