АОР1/Септембар 2022 — разлика између измена

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу
(+septembar 2022)
 
м (Formatiranje; Aleksa kaže da je ovo rešenje dobilo maks poena tako da više nije delimično rešeno valjda)
 
(Нису приказане 3 међуизмене другог корисника)
Ред 1: Ред 1:
{{tocright}}
{{tocright}}
{{нерешено}}
'''Испит у септембарском року 2022. године''' одржан је 16. септембра.


== 1. задатак ==
== 1. задатак ==
Ред 7: Ред 7:


<div class="abc-list">
<div class="abc-list">
# '''[5п]''' Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције '''beqz''' у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција:
# '''[5п]''' Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције '''beqz''' у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција: <syntaxhighlight lang="asm">
<syntaxhighlight lang="asm">
         add  R1, R2, R3  ;R1=R2+R3
         add  R1, R2, R3  ;R1=R2+R3
         beqz R1, 50      ;if(R1==0) goto PC+50
         beqz R1, 50      ;if(R1==0) goto PC+50
</syntaxhighlight>
</syntaxhighlight>
# '''[5п]''' Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције '''beqz''' у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција:
# '''[5п]''' Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције '''beqz''' у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција: <syntaxhighlight lang="asm">
<syntaxhighlight lang="asm">
         lw  R1, 0(R2)  ;R1=MEM[R2+0]
         lw  R1, 0(R2)  ;R1=MEM[R2+0]
         beqz R1, 50      ;if(R1==0) goto PC+50
         beqz R1, 50      ;if(R1==0) goto PC+50
Ред 19: Ред 17:
# '''[5п]''' Дати процесор треба да подржи и инструкцију условног премештања <syntaxhighlight inline lang="asm">MOVZ RD, RS, RT</syntaxhighlight> (<syntaxhighlight inline lang="c">if (RS==0) RD=RT</syntaxhighlight>). Шта је потребно изменити у процесору са слике 1 (нацртати и објаснити) тако да се и ова инструкција извршава у 5 фаза као и остале инструкције. Шта је потребно изменити у хардверу за прослеђивање (тачка б) да би се прослеђивање исправно обављало.
# '''[5п]''' Дати процесор треба да подржи и инструкцију условног премештања <syntaxhighlight inline lang="asm">MOVZ RD, RS, RT</syntaxhighlight> (<syntaxhighlight inline lang="c">if (RS==0) RD=RT</syntaxhighlight>). Шта је потребно изменити у процесору са слике 1 (нацртати и објаснити) тако да се и ова инструкција извршава у 5 фаза као и остале инструкције. Шта је потребно изменити у хардверу за прослеђивање (тачка б) да би се прослеђивање исправно обављало.
</div>
</div>
=== Решење ===
<div class="abc-list">
# Потребно је увести прослеђивање. Заустављање није неизбежно - довољно је проследити из EX фазе <code>ADD</code> инструкције у EX фазу <code>BEQZ</code> инструкције, јер је ''Zero'' јединица управо у EX фази.
# Опет, потребно је прослеђивање. Ипак, заустављање је неизбежно - <code>LW</code> инструкција добија вредност R1 регистра тек у МЕМ фази, а <code>BEQZ</code> инструкција треба регистар R1 још у EX фази. Проточна обрада ће се зато зауставити на један такт.
</div>


== 2. задатак ==
== 2. задатак ==
Ред 42: Ред 47:
Изглед дела меморије почев од адресе 100h је приказан на слици 2. Из меморије се чита и у њу уписује 32-битне реч по реч. Почетна адреса програма је 1000h, а почетна вредност регистра R1 је 100h. Свака инструкција заузима тачно једну адресу, адресирање је на нивоу 32-битне речи.
Изглед дела меморије почев од адресе 100h је приказан на слици 2. Из меморије се чита и у њу уписује 32-битне реч по реч. Почетна адреса програма је 1000h, а почетна вредност регистра R1 је 100h. Свака инструкција заузима тачно једну адресу, адресирање је на нивоу 32-битне речи.


<center>
{| class="wikitable" style="margin: 0 auto;"
{| class="wikitable"
|+ style="caption-side: bottom;" | Слика 2. Изглед дела меморије
|+ style="caption-side:bottom;"|Слика 2. Изглед дела меморије
! Адреса
| '''Адреса''' || 100 || 101 || 102 || 103 || 104 || 105 || 106 || 107 || 108 || 109 || 10A || 10B
| 100 || 101 || 102 || 103 || 104 || 105 || 106 || 107 || 108 || 109 || 10A || 10B
|-
|-
| '''Садржај''' || 0 || 5 || 0 || 1 || 0 || 6 || 0 || 2 || 2 || 0 || 1 || 9
! Садржај
| 0   || 5   || 0   || 1   || 0   || 6   || 0   || 2   || 2   || 0   || 1   || 9
|}
|}
</center>


<div class="abc-list">
<div class="abc-list">
Ред 57: Ред 62:
</div>
</div>


<center>
{| class="wikitable" style="margin: 0 auto;"
{| class="wikitable"
|+ style="caption-side: bottom;" | Слика 3. Изглед кеш меморије за предикцију.
|+ style="caption-side:bottom;"|Слика 3. Изглед кеш меморије за предикцију.
! улаз !! PC || Next PC || Предикција
! улаз !! PC || Next PC || Предикција
|-
|-
Ред 70: Ред 74:
| 3 || 100B || 1002 || 10
| 3 || 100B || 1002 || 10
|}
|}
</center>
 
=== Решење ===
==== Решење а ====
{| class="wikitable"
! Инструкција      !!  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<sup>*</sup> || EX  || MEM || WB
|-
| LW  R4, (R1)1    ||    ||    ||    ||    ||    ||    ||    ||    || IF  ||stall<sup>*</sup>|| 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<sup>*</sup>  || EX  || MEM || WB
|-
| ADDI R2, R2, #1  ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    || IF  ||stall<sup>*</sup>||idle ||idle ||idle
|-
| ADDI R1, R1, #1  ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    ||    || IF  || ID  || EX  || MEM || WB
|}
Прослеђивања:
* Такт 3 EX    -> Такт 4  EX
* Такт 4 MEM  -> Такт 5  EX
* Такт 5 EX    -> Такт 6  EX
* Такт 6 MEM  -> Такт 7  EX
* Такт 8 MEM  -> Такт 9  EX
* Такт 8 WB    -> Такт 9  EX
* Такт 9 EX    -> Такт 10 EX
* Такт 13 MEM  -> Такт 14 MEM
* Такт 15 EX  -> Такт 16 EX
 
Вредности регистара:
* R1 = 100, 101, 102, 103
* R2 = 5, 4
* R3 = 0
* R4 = 1, 1, 1
 
{| class="wikitable" style="margin: 0 auto;"
|+ style="caption-side: bottom;" | Измењена меморија
| '''Адреса''' || 100 || 101 || 102 || 103 || 104 || 105 || 106 || 107 || 108 || 109 || 10A || 10B
|-
| '''Садржај''' || 0 || 5 || <span style="color: red;">1</span> || <span style="color: red;">0</span> || 0 || 6 || 0 || 2 || 2 || 0 || 1 || 9
|}
 
==== Решење б ====
Прослеђивања, вредности регистара и измене на меморији су (очекивано) исте.
{| class="wikitable"
! Инструкција      !!  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
|}
 
==== Решење ц ====
{| class="wikitable" style="margin: 0 auto;"
|+ style="caption-side: bottom;" | Изглед кеш меморије за предикцију након извршавања 13 инструкција.
! улаз !! PC || Next PC || Предикција
|-
| 0 || 100F || 100A || 11
|-
| 1 || 1006 || 100A, 1007 || 10, 00
|-
| 2 || 1014 || 1002 || 11
|-
| 3 || 100B || 1002, 1002 || 10, 11
|}


[[Категорија:АОР1]]
[[Категорија:АОР1]]
[[Категорија:Рокови]]
[[Категорија:Рокови]]

Тренутна верзија на датум 9. фебруар 2023. у 12:35

Испит у септембарском року 2022. године одржан је 16. септембра.

1. задатак

Поставка

[15п] Посматра се процесор организације са проточном обрадом дат на слици 1. Свака фаза извршавања инструкције траје једну периоду сигнала такта укључујући и фазу 2 у којој се чита из регистарског фајла (Registers) и фазу 5 у којој се уписује у регистарски фајл (Registers).

  1. [5п] Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције beqz у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција: 
            add  R1, R2, R3  ;R1=R2+R3
        beqz R1, 50      ;if(R1==0) goto PC+50
  2. [5п] Објаснити за процесор са слике 1 шта треба хардверски урадити да би се или комплетно елиминисала или свела на минимум потреба заустављања инструкције beqz у проточној обради. Ако је неизбежно заустављање проточне обраде, објаснити због чега је то потребно урадити и за колико тактова треба зауставити проточну обраду. Секвенца инструкција: 
            lw   R1, 0(R2)   ;R1=MEM[R2+0]
        beqz R1, 50      ;if(R1==0) goto PC+50
  3. [5п] Дати процесор треба да подржи и инструкцију условног премештања MOVZ RD, RS, RT (if (RS==0) RD=RT). Шта је потребно изменити у процесору са слике 1 (нацртати и објаснити) тако да се и ова инструкција извршава у 5 фаза као и остале инструкције. Шта је потребно изменити у хардверу за прослеђивање (тачка б) да би се прослеђивање исправно обављало.

Решење

  1. Потребно је увести прослеђивање. Заустављање није неизбежно - довољно је проследити из EX фазе ADD инструкције у EX фазу BEQZ инструкције, јер је Zero јединица управо у EX фази.
  2. Опет, потребно је прослеђивање. Ипак, заустављање је неизбежно - LW инструкција добија вредност R1 регистра тек у МЕМ фази, а BEQZ инструкција треба регистар R1 још у EX фази. Проточна обрада ће се зато зауставити на један такт.


2. задатак

Поставка

[15п] Посматра се систем са стандардном проточном обрадом са слике 1 код кога постоји хардвер за прослеђивање, а у случају када се у ID фази детектује да се ради о инструкцији скока проточна обрада се зауставља све док се не одреди да ли је услов скока испуњен и док се не срачуна адреса скока. У случају да услов скока није испуњен наставља се извршавање започете инструкције. Извршава се следећи програмски сегмент: 

        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

Изглед дела меморије почев од адресе 100h је приказан на слици 2. Из меморије се чита и у њу уписује 32-битне реч по реч. Почетна адреса програма је 1000h, а почетна вредност регистра R1 је 100h. Свака инструкција заузима тачно једну адресу, адресирање је на нивоу 32-битне речи.

Слика 2. Изглед дела меморије
Адреса 100 101 102 103 104 105 106 107 108 109 10A 10B
Садржај 0 5 0 1 0 6 0 2 2 0 1 9
  1. Приказати табеларно шта се дешава у којој фази за првих 13 инструкција датог програма које се изврше.
  2. Приказати табеларно шта се дешава у којој фази за првих 13 инструкција датог програма које се изврше у случају да постоји кеш за предикцију скока са 4 асоцијативних улаза и 2 бита за предикцију скока по улазу. Предикција 11 означава јаку предикцију да ће бити скока, 10 слабу предикцију да ће бити скока, 00 означава јаку предикцију да неће бити скока, а 01 слабу предикцију да неће бити скока. Кеш за предикцију скока дозвољава и читање и упис у истом такту. Изглед кеш меморије за предикцију пре извршавања датог програмског сегмента приказан је на слици 3.
  3. Дати табеларно приказ кеш меморије за предикцију 13 инструкција датог програма и скицирати шему за предвиђање која је коришћена у тачки b).
Слика 3. Изглед кеш меморије за предикцију.
улаз PC Next PC Предикција
0 100F 100A 11
1 1006 100A 10
2 1014 1002 11
3 100B 1002 10

Решење

Решење а

Инструкција 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

Прослеђивања:

  • Такт 3 EX -> Такт 4 EX
  • Такт 4 MEM -> Такт 5 EX
  • Такт 5 EX -> Такт 6 EX
  • Такт 6 MEM -> Такт 7 EX
  • Такт 8 MEM -> Такт 9 EX
  • Такт 8 WB -> Такт 9 EX
  • Такт 9 EX -> Такт 10 EX
  • Такт 13 MEM -> Такт 14 MEM
  • Такт 15 EX -> Такт 16 EX

Вредности регистара:

  • R1 = 100, 101, 102, 103
  • R2 = 5, 4
  • R3 = 0
  • R4 = 1, 1, 1
Измењена меморија
Адреса 100 101 102 103 104 105 106 107 108 109 10A 10B
Садржај 0 5 1 0 0 6 0 2 2 0 1 9

Решење б

Прослеђивања, вредности регистара и измене на меморији су (очекивано) исте.

Инструкција 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

Решење ц

Изглед кеш меморије за предикцију након извршавања 13 инструкција.
улаз PC Next PC Предикција
0 100F 100A 11
1 1006 100A, 1007 10, 00
2 1014 1002 11
3 100B 1002, 1002 10, 11
Преузето из „https://siwiki.rs/w/index.php?title=АОР1/Септембар_2022&oldid=5470”