Архитектура рачунара/Јул 2024

Извор: SI Wiki
< Архитектура рачунара
Датум измене: 12. јул 2024. у 20:46; аутор: D3f4ult (разговор | доприноси) (→‎Решење)
(разл) ← Старија измена | Тренутна верзија (разл) | Новија измена → (разл)
Пређи на навигацију Пређи на претрагу

1. задатак

Поставка

[5п] У посматраном рачунарском систему процесор постоји само једна линија по којој улазно/излазни уређаји могу процесору да шаљу захтеве за прекид, док линија за слање сигнала потврде не постоји. У датом систему постоје 3 улазно/излазна уређаја UI2, UI1 и UI0, при чему UI2 има највиши, а UI0 најнижи приоритет. Периферија захтев за прекидом генерише као ниво и не постоји контролер прекида.

  1. Нацртати како та 3 улазно/излазна уређаја треба повезати помоћу те линије на процесор ради слања захтева за прекид.
  2. Објаснити како се реализује скок на одговарајућу прекидну рутину сваког од 3 улазно/излазна уређаја.

Решење

  1. Задатак 1
  2. Пошто не постоји линија за сигнал потврде, скок на одговарајућу прекидну рутину се реализује полирањем у заједничкој прекидној рутини. Због датих приоритета улазно/излазних уређаја, прво треба да испитујемо најприоритетнији уређај (UI2), па онда по приоритетима све до најмање приоритетног (UI0 у овом случају). Код изгледа овако:
     PUSH R1
     PUSH R2
     LOAD R1, #2 ; ucitavamo broj ulaza najprioritetnijeg
UI2: LOAD R2, statusRegUI2
     TST R2, #readyUI2
     JZ UI1
     LOAD R2, controlRegUI2
     TST R2, #enableUI2
     JZ UI1
     TST R2, #startUI2
     JZ UI1
     JMP TBL
UI1: DEC R1 ; smanjujemo broj ulaza
     LOAD R2, statusRegUI1
     TST R2, #readyUI1
     JZ UI0
     LOAD R2, controlRegUI1
     TST R2, #enableUI1
     JZ UI0
     TST R2, #startUI1
     JZ UI0
     JMP TBL
UI0: DEC R1
     LOAD R2, statusRegUI0
     TST R2, #readyUI0
     JZ end
     LOAD R2, controlRegUI0
     TST R2, #enableUI0
     JZ end
     TST R2, #startUI0
     JZ end
TBL: SHL R1
     ADD R1, tbladr
     MOV R2, (R1)
     JADR (R2)
end: POP R2
     POP R1
     RTI

2. задатак

Поставка

[5п] Haписати оптималну секвенцу инструкција неопходних за срачунавање израза: 

int *a, *b, *c, d, i;
...
for(i = 0; i < d; i += 1)
    c[i] = a[i] + b[i];
...

На располаrању је процесор код кога аритметичке, логичке и померачке инструкције имају формат: ОС reg, reg, reg/imm где је ОС код операције, одредишни операнд и први операнд морају бити у регистру (reg), док други може бити или у регистру или дат непосредно (reg/imm). Инструкција LOAD има формат: LOAD reg, mem где је првим операндом дат одредишни регистар (reg), a другим извориште. Инструкцијa STORE има формат: STORE reg, mem где је првим операндом дат изворишни регистар (reg), a другим одредиште. А, В, С, D, и I су глобалне променљиве које одговарају симболичким ознакама адреса меморијских локација у којима се налазе операнди. Садржај меморијских локација означених адресама A, B, С и D треба да остане непромењен, садржај одговарајућих регистара је дозвољено мењати. На располагању стоји 8 регистара опште намене. Претпоставити да су сви подаци и адресе исте дужине која је једнака адресибилној јединици.

Решење

      LOAD Ra, a
      LOAD Rb, b
      LOAD Rc, c
      LOAD Rd, d
      ...
      XOR Ri, Ri, Ri ; clear Ri
loop: STORE Ri, i
      SUB R0, Ri, Rd
      JGE end
      LOAD RtempA, (Ra, Ri)0
      LOAD RtempB, (Rb, Ri)0
      ADD R0, RtempA, RtempB
      STORE R0, (Rc, Ri)0
      ADD Ri, Ri, #1
      JMP loop

end:  ...

3. задатак

Поставка

[5п] Написати оптималну секвенцу инструкција која одговара следећој стандардној библиотечкој С функцији која проналази прво појављивање карактера c у низу карактера str: 

char *strchr(const char *str, char c)

Функција као резултат враћа показивач на прво појављивање карактера c у низу карактера str или 0 уколико се карактер c не појављује у низу карактера str. Формати инструкција и података су као у задатку 2. На располагању стоје и сложене инструкције.

Решење

strchr:
     PUSH BP
     MOV BP, SP
     PUSH R1
     PUSH R2
     PUSH R3
     LOAD R1, (BP)2 ; str
     LOAD R2, (BP)3 ; c
     XOR R0, R0, R0 ; clear R0
     ;strlen(str)
     ;LOCC len, addr, char
     LOAD R3, #maxValue
     LOCC R3, R1, '\0'
     SUB R1, R1, #1
     LOAD R3, (BP)2
     SUB R3, R1, R3 ; R3 = strlen(str)
     LOAD R1, (BP)2
     LOCC R3, R1, R2
     JNZ end ; c not found in str
     MOV R0, R1
end: POP R3
     POP R2
     POP R1
     POP BP
     RTS

Реализација непостојећих инструкција (без овога се задатак не признаје са пуним бројем поена): 

    PUSH BP -> STORE BP, -(SP)
    POP BP -> LOAD BP, (SP)+
    MOV BP, SP -> ADD BP, SP, #0
    LOAD R3, #maxValue -> ADD R3, R0, #maxValue ; R0 = 0

4. задатак

Поставка

[15п] У рачунарском систему се налази једноадресни процесор, меморија и периферија PER0 и периферија PER1 са придруженим контролером са директним приступом меморији DMA. Све компоненте рачунара су повезане системском магистралом са 16 битном адресном и 16 битном магистралом података. Адресирање је на нивоу 16 битних речи. Улазно-излазни адресни простор и меморијски адресни простор су раздвојени. Адресе релевантних регистара су: 

   PER0_CONTROL   F000h   DMA_PER1_CONTROL   F110h
   PER0_STATUS    F001h   DMA_PER1_STATUS    F111h
   PER0_DATA      F002h   DMA_PER1_DATA      F112h
   PER1_CONTROL   F100h   DMA_PER1_ADDR      F113h
   PER1_STATUS    F101h   DMA_PER1_COUNT     F114h
   PER1_DATA      F102h

У управљачким регистрима бит 4 је Start којим се дозвољава почетак операције, бит 0 одређује тип преноса података (1 - улаз (input), 0 - излаз (output)), бит 1 је Enable којим се дозвољава прекид, а у статусним регистрима бит 8 је Ready који сигнализира спремност контролера периферије. Бит 2 управљачког регистра DMA контролера задаје режим рада (0-блоковски (burst), 1-циклус по циклус (cycle stealing)).

Периферија PER0 шаље низ шеснаестобитних података који је потребно сместити почев од локација 1000h. Величина низа је 100h. Након пријема потребно је формирати резултујући низ који не садржи дупликате. Могуће је да се нека вредност појављује више пута у оквиру низа, па је у резултујућем низу потребно задржати само једну њену појаву. Формирање резултујућег низа реализовати функцјиом int removeDuplicates(int* arr, int size) која као параметре има адресу почетка низа и његову величину, док јој је повратна вредност величина резултујућег низа. Резултујући низ се смешта почев од локације на коју указује параметар arr. У имплементацији функције дозвољено је користити само простор на стеку. Након формирања резултујућег низа потребно га је проследити периферији PER1.

Потребно је написати главни програм, функцију removeDuplicates и одговарајуће прекидне рутине којима се обавља описани пренос података. Улаз са периферије PER0 реализовати техником програмираног улаза са прекидом, док слање на PER1 коришћењем DMA контролера у блоковском режиму.

Процесор има регистре SP и BP као и додатни помоћни регистар RX чија се претходна вредност не чува приликом извршавања функције (постоје инструкције LDRX и STRX за пренос вредности између акумулатора и регистра RX). Регистри BP и RX се могу користити за регистарско индиректно адресирање. Функција локалне променљиве алоцира на стеку. Сматрати да је тип int ширине 16 бита.

Дозвољено је користити додатне променљиве, али њихове називе треба писати описно и семантички исправно. Обавезно је писање концизних коментара над семантичким целинама у оквиру главног програма и прекидне рутине.

Напомена: На испиту нису дозвољена никаква помоћна средства, ни калкулатори, ни литература. Испит траје 120 минута. Студент је дужан да пише читко и уредно.

Решење

;glavni program
;inicijalizacija 

LD #1000h
ST MemAddr
LD #100h
ST MemCnt
LD #1
ST semPER0
LD #13h ; 0001 0011
OUT F000h ; ukljucivanje PER0

wait_per0: LD semPER0
           CMP #0
           JNZ wait_per0

; priprema argumenata za poziv funkcije
LD #1000h
PUSH
LD #100h
PUSH
JSR removeDuplicates
;cuvamo novu velicinu niza na lokaciju NewMemCnt
ST NewMemCnt
; ciscenje steka
POP 
POP

LD #1000h
OUT F113h
LD NewMemCnt
OUT F114h
LD #1h
ST semDMA
LD #10h ; 0001 0000
OUT F100h ; ukljucivanje PER1
LD #12h ; 0001 0010
OUT F110h ; ukljucivanje DMA

wait_dma: LD semDMA
          CMP #0
          JNZ wait_dma

LD #0h
OUT F100h
HALT

;prekidne rutine
PER0: PUSH
      IN F002h
      ST (MemAddr)
      LD MemAddr
      INC
      ST MemAddr
      LD MemCnt
      DEC
      ST MemCnt
      JNZ end0
      LOAD #0h
      OUT F000h
      ST semPER0
end0: POP
      RTI

DMA: PUSH
     LD #0h
     OUT F110h
     ST semDMA
     POP
     RTI
    
;prekidne rutine kraj


;potprogram removeDuplicates
;int removeDuplicates(int* arr, int size);

;   stek
;|  size   |+3
;|  arr    |+2
;|  retPC  |+1
;|  BP     | 0<---SP
;| remElem |-1
;|  i      |-2
;|  curEl  |-3
;|  j      |-4

removeDuplicates:
         LD BP
         PUSH 
         LD SP
         ST BP
         ;rezervisanje prostora na steku za 4 lokalne promenljive
         SUB #4
         ST SP
         AND #0h
         ST (BP)-1
         ST (BP)-2
outLoop: LD (BP)-2
         CMP (BP)+3
         JGE endFun
         ;ucitavanje elementa
         ADD (BP)+2
         STRX
         LD (RX)0 ; trenutni element
         ST (BP)-3
         LD (BP)-2 
         ST (BP)-4 ; postavljamo da je i = j
inLoop:  CMP (BP)-2 ; poredimo i sa j
         JGE endIn
         LD (BP)-4
         ADD (BP)+2
         STRX
         LD (RX)0 ; arr[j]
         CMP (BP)-3 ; arr[i] == arr[j]
         JNZ skipFun
         LD (BP)+2
         ADD (BP)-4
         PUSH ; lokacija u nizu odakle se pomera
         LD (BP)+3
         SUB (BP)-4
         PUSH ; koliko elemenata treba da se pomeri
         JSR moveElements
         POP
         POP
         ;povecaj broj izbacenih elemenata
         LD (BP)-1
         INC
         ST (BP)-1
         ; j++
skipFun: LD (BP)-4
         INC
         ST (BP)-4
         JMP inLoop
         ;i++
endIn:   LD (BP)-2
         INC
         ST (BP)-2
         JMP outLoop
         ;priprema nove velicine niza
endFun:  LD (BP)+3
         SUB (BP)-1
         STRX
         ;ciscenje lokalnih promenljivih
         LD SP
         ADD #4
         ST SP
         POP
         ST BP
         ;vracanje rezultata u akumulator
         LDRX
         RTS


;potprogram moveElements
;void moveElements(int* arr, int size);

;   stek
;|  size   |+3
;|  arr    |+2
;|  retPC  |+1
;|  BP     | 0 <---SP
;|  cnt    |-1
;|  curEl  |-2

moveElements:
        LD BP
        PUSH
        LD SP
        ST BP
        ;rezervisanje prostora na steku za 2 lokalne promenljive
        SUB #2
        ST SP
        AND #0
        ST (BP)-1
mvLoop: LD (BP)+3
        CMP #0
        JZ endMov
        ;arr++
        LD (BP)+2
        INC
        ST (BP)+2
        ;arr[cnt]
        ADD (BP)-1
        STRX
        LD (RX)0
        ST (BP)-2 ; curEl = arr[cnt]
        LD (BP)+2
        DEC
        ADD (BP)-1
        STRX ; arr+cnt-1
        LD (BP)-2
        ST (RX)0 arr[cnt-1] = arr[cnt]
        ; cnt++
        LD (BP)-1
        INC 
        ST (BP)-1
        ;size--
        LD (BP)+3
        DEC
        ST (BP)+3
        JMP mvLoop
endMov: LD SP
        ; ciscenje lokalnih promenljivih
        ADD #2
        ST SP
        POP
        ST BP
        RTS
Преузето из „https://siwiki.rs/w/index.php?title=Архитектура_рачунара/Јул_2024&oldid=7734”