Arhitektura računara/Jul 2024

Izvor: SI Wiki
< Архитектура рачунара
Datum izmene: 12. jul 2024. u 20:46; autor: D3f4ult (razgovor | doprinosi) (→‎Решење)
(razl) ← Starija izmena | Trenutna verzija (razl) | Novija izmena → (razl)
Pređi na navigaciju Pređi na pretragu

1. zadatak

Postavka

[5p] U posmatranom računarskom sistemu procesor postoji samo jedna linija po kojoj ulazno/izlazni uređaji mogu procesoru da šalju zahteve za prekid, dok linija za slanje signala potvrde ne postoji. U datom sistemu postoje 3 ulazno/izlazna uređaja UI2, UI1 i UI0, pri čemu UI2 ima najviši, a UI0 najniži prioritet. Periferija zahtev za prekidom generiše kao nivo i ne postoji kontroler prekida.

  1. Nacrtati kako ta 3 ulazno/izlazna uređaja treba povezati pomoću te linije na procesor radi slanja zahteva za prekid.
  2. Objasniti kako se realizuje skok na odgovarajuću prekidnu rutinu svakog od 3 ulazno/izlazna uređaja.

Rešenje

  1. Zadatak 1
  2. Pošto ne postoji linija za signal potvrde, skok na odgovarajuću prekidnu rutinu se realizuje poliranjem u zajedničkoj prekidnoj rutini. Zbog datih prioriteta ulazno/izlaznih uređaja, prvo treba da ispitujemo najprioritetniji uređaj (UI2), pa onda po prioritetima sve do najmanje prioritetnog (UI0 u ovom slučaju). Kod izgleda ovako:
     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. zadatak

Postavka

[5p] Hapisati optimalnu sekvencu instrukcija neophodnih za sračunavanje izraza: 

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

Na raspolaranju je procesor kod koga aritmetičke, logičke i pomeračke instrukcije imaju format: OS reg, reg, reg/imm gde je OS kod operacije, odredišni operand i prvi operand moraju biti u registru (reg), dok drugi može biti ili u registru ili dat neposredno (reg/imm). Instrukcija LOAD ima format: LOAD reg, mem gde je prvim operandom dat odredišni registar (reg), a drugim izvorište. Instrukcija STORE ima format: STORE reg, mem gde je prvim operandom dat izvorišni registar (reg), a drugim odredište. A, V, S, D, i I su globalne promenljive koje odgovaraju simboličkim oznakama adresa memorijskih lokacija u kojima se nalaze operandi. Sadržaj memorijskih lokacija označenih adresama A, B, S i D treba da ostane nepromenjen, sadržaj odgovarajućih registara je dozvoljeno menjati. Na raspolaganju stoji 8 registara opšte namene. Pretpostaviti da su svi podaci i adrese iste dužine koja je jednaka adresibilnoj jedinici.

Rešenje

      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. zadatak

Postavka

[5p] Napisati optimalnu sekvencu instrukcija koja odgovara sledećoj standardnoj bibliotečkoj S funkciji koja pronalazi prvo pojavljivanje karaktera c u nizu karaktera str: 

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

Funkcija kao rezultat vraća pokazivač na prvo pojavljivanje karaktera c u nizu karaktera str ili 0 ukoliko se karakter c ne pojavljuje u nizu karaktera str. Formati instrukcija i podataka su kao u zadatku 2. Na raspolaganju stoje i složene instrukcije.

Rešenje

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

Realizacija nepostojećih instrukcija (bez ovoga se zadatak ne priznaje sa punim brojem poena): 

    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. zadatak

Postavka

[15p] U računarskom sistemu se nalazi jednoadresni procesor, memorija i periferija PER0 i periferija PER1 sa pridruženim kontrolerom sa direktnim pristupom memoriji DMA. Sve komponente računara su povezane sistemskom magistralom sa 16 bitnom adresnom i 16 bitnom magistralom podataka. Adresiranje je na nivou 16 bitnih reči. Ulazno-izlazni adresni prostor i memorijski adresni prostor su razdvojeni. Adrese relevantnih registara su: 

   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

U upravljačkim registrima bit 4 je Start kojim se dozvoljava početak operacije, bit 0 određuje tip prenosa podataka (1 - ulaz (input), 0 - izlaz (output)), bit 1 je Enable kojim se dozvoljava prekid, a u statusnim registrima bit 8 je Ready koji signalizira spremnost kontrolera periferije. Bit 2 upravljačkog registra DMA kontrolera zadaje režim rada (0-blokovski (burst), 1-ciklus po ciklus (cycle stealing)).

Periferija PER0 šalje niz šesnaestobitnih podataka koji je potrebno smestiti počev od lokacija 1000h. Veličina niza je 100h. Nakon prijema potrebno je formirati rezultujući niz koji ne sadrži duplikate. Moguće je da se neka vrednost pojavljuje više puta u okviru niza, pa je u rezultujućem nizu potrebno zadržati samo jednu njenu pojavu. Formiranje rezultujućeg niza realizovati funkcjiom int removeDuplicates(int* arr, int size) koja kao parametre ima adresu početka niza i njegovu veličinu, dok joj je povratna vrednost veličina rezultujućeg niza. Rezultujući niz se smešta počev od lokacije na koju ukazuje parametar arr. U implementaciji funkcije dozvoljeno je koristiti samo prostor na steku. Nakon formiranja rezultujućeg niza potrebno ga je proslediti periferiji PER1.

Potrebno je napisati glavni program, funkciju removeDuplicates i odgovarajuće prekidne rutine kojima se obavlja opisani prenos podataka. Ulaz sa periferije PER0 realizovati tehnikom programiranog ulaza sa prekidom, dok slanje na PER1 korišćenjem DMA kontrolera u blokovskom režimu.

Procesor ima registre SP i BP kao i dodatni pomoćni registar RX čija se prethodna vrednost ne čuva prilikom izvršavanja funkcije (postoje instrukcije LDRX i STRX za prenos vrednosti između akumulatora i registra RX). Registri BP i RX se mogu koristiti za registarsko indirektno adresiranje. Funkcija lokalne promenljive alocira na steku. Smatrati da je tip int širine 16 bita.

Dozvoljeno je koristiti dodatne promenljive, ali njihove nazive treba pisati opisno i semantički ispravno. Obavezno je pisanje konciznih komentara nad semantičkim celinama u okviru glavnog programa i prekidne rutine.

Napomena: Na ispitu nisu dozvoljena nikakva pomoćna sredstva, ni kalkulatori, ni literatura. Ispit traje 120 minuta. Student je dužan da piše čitko i uredno.

Rešenje

;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
Preuzeto iz „https://siwiki.rs/w/index.php?title=Архитектура_рачунара/Јул_2024&oldid=7734”