Архитектура рачунара/Јул 2024
1. задатак
Поставка
[5п] У посматраном рачунарском систему процесор постоји само једна линија по којој улазно/излазни уређаји могу процесору да шаљу захтеве за прекид, док линија за слање сигнала потврде не постоји. У датом систему постоје 3 улазно/излазна уређаја UI2, UI1 и UI0, при чему UI2 има највиши, а UI0 најнижи приоритет. Периферија захтев за прекидом генерише као ниво и не постоји контролер прекида.
- Нацртати како та 3 улазно/излазна уређаја треба повезати помоћу те линије на процесор ради слања захтева за прекид.
- Објаснити како се реализује скок на одговарајућу прекидну рутину сваког од 3 улазно/излазна уређаја.
Решење
- Пошто не постоји линија за сигнал потврде, скок на одговарајућу прекидну рутину се реализује полирањем у заједничкој прекидној рутини. Због датих приоритета улазно/излазних уређаја, прво треба да испитујемо најприоритетнији уређај (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