АОР2/Јун 2023
Јунски рок 2023. године одржан је 5. јуна и трајао је 120 минута.
1. задатак
Поставка
[5п] Описати технику оптимизације векторских инструкција која се заснива на коришћењу регистра маски вектора (Vector mask registers). На примеру израчунавања максимума кореспондентних елемената низа (Z[i] = MAX(X[i], Y[i])) приказати коришћење овог регистра.
Решење
Регистар маске вектора служи како би се одређене операције над векторима извршиле само над њиховим одређеним члановима, тиме што на одређеним битовима регистра маске стоје нуле или јединице. На пример, следећи код за рачунање максимума:
for (int i = 0; i < n; ++i)
if (X[i] > Y[i])
Z[i] = X[i];
else
Z[i] = Y[i];
би могао да се преведе у следећу секвенцу векторских инструкција:
...
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. задатак
Поставка
[5п] Посматра се предвиђање скока коришћењем gshare предиктора. Описати рад овог предиктора. Упоредити рад овог предиктора и корелисаног предиктора који користи исти број бита одговарајућих улазних података.
Решење
gshare предиктор садржи следеће елементе:
- Branch History Register (BHR) који функционише као shift регистар који чува глобалну историју скокова (да ли је услов испуњен или није),
- Pattern History Table (PHT) која садржи аутомате стања који одређују крајња предвиђања, и
- хеш функцију која комбинује BHR и битове адресе скока како би адресирала PHT.
За разлику од gshare, корелисани предиктор одвојено адресира једну од више PHT помоћу BHR, а затим један од аутомата у оквиру PHT помоћу адресе скока. Може се приметити да је корелисани предиктор, због свог већег броја PHT, за исте ширине улазних података доста скупљи од gshare. Такође се показало да је већина улаза у овакве PHT неискоришћено, па је gshare направљен како би побољшао ово искоришћење и смањио цену производње корелисаног предиктора.
3. задатак
Поставка
[10п] Разматра се рачунарски систем у коме се извршавање одређене инструкција одвија у 6 фаза помоћу измењеног процесора са стандардном проточном обрадом (слика 3.1.). У процесор са стандардом проточном обрадом је додата као други степен јединица PD (Instruction PreDecode) који[sic] обавља трансформацију инструкција задате архитектуре у инструкције RISC архитектуре. Сматрати да приступ меморији траје два сигнала такта. Архитектура процесора дефинише 16 регистра[sic] опште намене. Адресе и подаци су величине 16 бита.
- Написати секвенцу инструкција (микроинструкција) циљне RISC архитектуре у коју се обавља пресликавање за део инструкцијског сета из табеле 3.1. изворишне CISC архитектуре. Уколико је потребно проширити број регистара опште намене у регистарском фајлу, онда треба за сваки додат регистар написати чему служи. Регистар R13 представља указивач на врх стека (SP) и показује на последњу слободну локацију. Стек расте према вишим адресама. Регистар R14 представља указивач на базну адресу стека (BP). Регистар R0 се користи као акумулатор, регистар R12 се користи као бројачки регистар и као такав има посебне инструкције које га користе. У табели 3.1. акције нису оптимизовано написане, већ описно.
- Нацртати формат инструкција циљне RISC архитектуре (на основу инструкција из табеле 3.1.).
| Асемблерска инструкција | Акција | Микро инструкције |
|---|---|---|
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
|
Решење
Претпоставља се да се под AX регистром у задатку мисли на акумулатор. Уводимо регистре:
- R16: привремени регистар
- R17: вредност 0
- R18: још један привремени регистар
| Асемблерска инструкција | Акција | Микро инструкције | Коментар |
|---|---|---|---|
SWP Rx
|
MEM[Rx] ↔ ACC |
LD R0, (Rx)0 ADDIS R16, R0, #0 ST R16, (Rx)0 |
Уколико би после ове секвенце микроинструкција дошла микроинструкција која користи меморију, то би био хазард по подацима. |
DEC
|
ACC = ACC - 1 |
ADDIS R0, R0, #-1 | |
RTS
|
POP PC |
LD R16, (R13)-1 ADDI R13, R13, #-1 BEQZ R17, (R17+R16) |
У последњој инструкцији се кроз горњи мултиплексер пропушта вредност R17 (0), која се користи и као услов скока, а кроз доњи вредност R16, која садржи жељену вредност PC, па стога и специфичан начин обележавања (који је еквивалентан са (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 |
Дешава се хазард по подацима између прве и друге и између друге и треће микроинструкције. |
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 ADDI R0, R0, #1 BNEZPI R16, (PC)-3 * len(mInst) ADDIS R0, R0, #-1 |
За ову ставку је речено на колоквијуму да може да се претпостави како PC броји микроинструкције уместо инструкције. Главне идеје су да се уклони хазард тиме што радимо ADD инструкцију испод LD, да се акумулатор користи уместо неког новог регистра за чување adr (јер се свакако увећава сваке итерације) и да након петље која обухвата другу, трећу и четврту микроинструкцију морамо смањити акумулатор за један, јер нам је претходна петља ефективно била do-while уместо 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 |
Разлог из ког ова секвенца микроинструкција може изгледати чудно јесте избегавање хазарда по подацима. Са учитавањем првог податка почиње се већ у првој микроинструкцији, али како у међувремену треба обавити чување adr у новом привременом регистру и започињање новог учитавања, она се не сабира са регистром R1 до четврте микроинструкције (када је та вредност и даље доступна у одговарајућем регистру). Након тога се логика понавља неколико пута: започели смо учитавање наредног податка, а док се тај податак учитава ми радимо сабирање претходно учитаног податка са одговарајућим регистром. Како је до девете микроинструкције завршено учитавање и последњег податка, можемо извршити последње сабирање.
|
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 |
Идеја јесте да R16 користимо као претходну вредност акумулатора и R18 као бројач итерација који почиње од R1 и завршава се са 0. Уколико би нам провера за R18 == 0 била на врху, наша петља би се састојала из четири микроинструкције: провере, сабирања, декрементирања и безусловног скока. Уместо тога, проверу стављамо на дно па се наша петља састоји од три микроинструкције (резултујући у мањем укупном броју извршених микроинструкција), али због тога што смо опет ефективно направили do-while петљу ефекат последње итерације морамо да поништимо на крају. Као и за STRLEN, за ову ставку може да се претпостави како PC броји микроинструкције уместо инструкције. (На колоквијуму је накнадно речено да је податак у R1 означен, али то у овом решењу није узето у обзир јер такво коришћење и нема смисла.)
|
Користимо укупно седам RISC инструкција у овом сету:
- LD
- ST
- ADD
- SUB
- AND
- BEQZ
- BNEZ
Ово нам оставља следећи формат инструкције:
| 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 | Непосредна вредност | |||||||||||||||||||||||||||||||