AOR1/Septembar 2022

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

Ispit u septembarskom roku 2022. godine održan je 16. septembra.

1. zadatak

Postavka

[15p] Posmatra se procesor organizacije sa protočnom obradom dat na slici 1. Svaka faza izvršavanja instrukcije traje jednu periodu signala takta uključujući i fazu 2 u kojoj se čita iz registarskog fajla (Registers) i fazu 5 u kojoj se upisuje u registarski fajl (Registers).

  1. [5p] Objasniti za procesor sa slike 1 šta treba hardverski uraditi da bi se ili kompletno eliminisala ili svela na minimum potreba zaustavljanja instrukcije beqz u protočnoj obradi. Ako je neizbežno zaustavljanje protočne obrade, objasniti zbog čega je to potrebno uraditi i za koliko taktova treba zaustaviti protočnu obradu. Sekvenca instrukcija: 
            add  R1, R2, R3  ;R1=R2+R3
        beqz R1, 50      ;if(R1==0) goto PC+50
  2. [5p] Objasniti za procesor sa slike 1 šta treba hardverski uraditi da bi se ili kompletno eliminisala ili svela na minimum potreba zaustavljanja instrukcije beqz u protočnoj obradi. Ako je neizbežno zaustavljanje protočne obrade, objasniti zbog čega je to potrebno uraditi i za koliko taktova treba zaustaviti protočnu obradu. Sekvenca instrukcija: 
            lw   R1, 0(R2)   ;R1=MEM[R2+0]
        beqz R1, 50      ;if(R1==0) goto PC+50
  3. [5p] Dati procesor treba da podrži i instrukciju uslovnog premeštanja MOVZ RD, RS, RT (if (RS==0) RD=RT). Šta je potrebno izmeniti u procesoru sa slike 1 (nacrtati i objasniti) tako da se i ova instrukcija izvršava u 5 faza kao i ostale instrukcije. Šta je potrebno izmeniti u hardveru za prosleđivanje (tačka b) da bi se prosleđivanje ispravno obavljalo.

Rešenje

  1. Potrebno je uvesti prosleđivanje. Zaustavljanje nije neizbežno - dovoljno je proslediti iz EX faze ADD instrukcije u EX fazu BEQZ instrukcije, jer je Zero jedinica upravo u EX fazi.
  2. Opet, potrebno je prosleđivanje. Ipak, zaustavljanje je neizbežno - LW instrukcija dobija vrednost R1 registra tek u MEM fazi, a BEQZ instrukcija treba registar R1 još u EX fazi. Protočna obrada će se zato zaustaviti na jedan takt.


2. zadatak

Postavka

[15p] Posmatra se sistem sa standardnom protočnom obradom sa slike 1 kod koga postoji hardver za prosleđivanje, a u slučaju kada se u ID fazi detektuje da se radi o instrukciji skoka protočna obrada se zaustavlja sve dok se ne odredi da li je uslov skoka ispunjen i dok se ne sračuna adresa skoka. U slučaju da uslov skoka nije ispunjen nastavlja se izvršavanje započete instrukcije. Izvršava se sledeći programski segment: 

        ADDI R1, R1, #1   ;R1=R1+1
        LW   R2, (R1)0    ;R2=MEM[R1+0]
loop:   ADDI R1, R1, #1   ;R1=R1+1
        LW   R3, (R1)0    ;R3=MEM[R1+0]
        LW   R4, (R1)1    ;R4=MEM[R1+1]
        SUB  R4, R4, R3   ;R4=R4-R3
        BEQZ R4, back     ;if(R4 == 0) goto back
        LW   R4, (R1)1    ;R4=MEM[R1+1]
        SW   R4, (R1)0    ;MEM[R1+0]=R4
        SW   R3, (R1)1    ;MEM[R1+1]=R3
back:   SUBI R2, R2, #1   ;R2=R2-1
        BNEZ R2, loop     ;if(R2 != 0) goto loop
        ADDI R2, R2, #1   ;R2=R2+1
        OR   R2, R2, R2   ;R2=R2 | R2
        ANDI R1, R1, #1   ;R1=R1 & 1

Izgled dela memorije počev od adrese 100h je prikazan na slici 2. Iz memorije se čita i u nju upisuje 32-bitne reč po reč. Početna adresa programa je 1000h, a početna vrednost registra R1 je 100h. Svaka instrukcija zauzima tačno jednu adresu, adresiranje je na nivou 32-bitne reči.

Slika 2. Izgled dela memorije
Adresa 100 101 102 103 104 105 106 107 108 109 10A 10B
Sadržaj 0 5 0 1 0 6 0 2 2 0 1 9
  1. Prikazati tabelarno šta se dešava u kojoj fazi za prvih 13 instrukcija datog programa koje se izvrše.
  2. Prikazati tabelarno šta se dešava u kojoj fazi za prvih 13 instrukcija datog programa koje se izvrše u slučaju da postoji keš za predikciju skoka sa 4 asocijativnih ulaza i 2 bita za predikciju skoka po ulazu. Predikcija 11 označava jaku predikciju da će biti skoka, 10 slabu predikciju da će biti skoka, 00 označava jaku predikciju da neće biti skoka, a 01 slabu predikciju da neće biti skoka. Keš za predikciju skoka dozvoljava i čitanje i upis u istom taktu. Izgled keš memorije za predikciju pre izvršavanja datog programskog segmenta prikazan je na slici 3.
  3. Dati tabelarno prikaz keš memorije za predikciju 13 instrukcija datog programa i skicirati šemu za predviđanje koja je korišćena u tački b).
Slika 3. Izgled keš memorije za predikciju.
ulaz PC Next PC Predikcija
0 100F 100A 11
1 1006 100A 10
2 1014 1002 11
3 100B 1002 10

Rešenje

Rešenje a

Instrukcija 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
ADDI R1, R1, #1 IF ID EX MEM WB
LW R2, (R1)0 IF ID EX MEM WB
ADDI R1, R1, #1 IF ID EX MEM WB
LW R3, (R1)0 IF ID EX MEM WB
LW R4, (R1)1 IF ID EX MEM WB
SUB R4, R4, R3 IF ID stall EX MEM WB
BEQZ R4, back IF stall ID* EX MEM WB
LW R4, (R1)1 IF stall* ID EX MEM WB
SW R4, (R1)0 IF ID EX MEM WB
SW R3, (R1)1 IF ID EX MEM WB
SUBI R2, R2, #1 IF ID EX MEM WB
BNEZ R2, loop IF ID* EX MEM WB
ADDI R2, R2, #1 IF stall* idle idle idle
ADDI R1, R1, #1 IF ID EX MEM WB

Prosleđivanja:

  • Takt 3 EX -> Takt 4 EX
  • Takt 4 MEM -> Takt 5 EX
  • Takt 5 EX -> Takt 6 EX
  • Takt 6 MEM -> Takt 7 EX
  • Takt 8 MEM -> Takt 9 EX
  • Takt 8 WB -> Takt 9 EX
  • Takt 9 EX -> Takt 10 EX
  • Takt 13 MEM -> Takt 14 MEM
  • Takt 15 EX -> Takt 16 EX

Vrednosti registara:

  • R1 = 100, 101, 102, 103
  • R2 = 5, 4
  • R3 = 0
  • R4 = 1, 1, 1
Izmenjena memorija
Adresa 100 101 102 103 104 105 106 107 108 109 10A 10B
Sadržaj 0 5 1 0 0 6 0 2 2 0 1 9

Rešenje b

Prosleđivanja, vrednosti registara i izmene na memoriji su (očekivano) iste.

Instrukcija 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
ADDI R1, R1, #1 IF ID EX MEM WB
LW R2, (R1)0 IF ID EX MEM WB
ADDI R1, R1, #1 IF ID EX MEM WB
LW R3, (R1)0 IF ID EX MEM WB
LW R4, (R1)1 IF ID EX MEM WB
SUB R4, R4, R3 IF ID stall EX MEM WB
BEQZ R4, back IF stall ID EX MEM WB
SUBI R2, R2, #1 IF ID idle idle idle
BNEZ R2, loop IF idle idle idle idle
LW R4, (R1)1 IF ID EX MEM WB
SW R4, (R1)0 IF ID EX MEM WB
SW R3, (R1)1 IF ID EX MEM WB
SUBI R2, R2, #1 IF ID EX MEM WB
BNEZ R2, loop IF ID EX MEM WB
ADDI R1, R1, #1 IF ID EX MEM WB

Rešenje c

Izgled keš memorije za predikciju nakon izvršavanja 13 instrukcija.
ulaz PC Next PC Predikcija
0 100F 100A 11
1 1006 100A, 1007 10, 00
2 1014 1002 11
3 100B 1002, 1002 10, 11
Preuzeto iz „https://siwiki.rs/w/index.php?title=АОР1/Септембар_2022&oldid=5470”