Question 1 Architecture MIPS (15 pts)
1.1 (5 pts) Translate the high-level code presented below into MIPS assembly language. Comply with all MIPS conventions. int suite(int n, int k)
{
int r;
if {n = 0)
alsa
r = l;
r = r + k,n + suita(n-1, k+l); return r;
1.4 (8 pts) Translate the machine code into MIPS assembly language code assuming that your program is placed in memory from
the address 0040000016 – The encoding of the MIPS instructions as well as the register table are given in the appendix.
Complete the “Address”, “Binary code”, “Mnemonic code” and “Addressing mode” columns, indicating the addressing mode used for each instruction.
Address Code Binary code Mnemonic code machine
base 16
00400000 2008000f 00000820 20210001 2108fffb lSOOfffd ac28000f 00010880 08100005
Addressing mode
Question 2. Microarchitecture MIPS (7 pts)
2.1 (4pts)ChangetheMIPSdatapathimplementationonecycletoimplementthejrlti(“jumpregisteriflessthanimmidiate”)instruction.
If the content of the register rs is smaller than the extended value imm signed on 32 bits, it is necessary to jump to the address contained in the register rt:
[rs] < Signimm? PC = {rt) : PC= PC + 4
You do not have the right to modify ALU (ALU is that of course notes), but you can modify all the other components and add the others. jrlti rt,rs,7
1111111
opcode
rs rt imm
.:)1;3
ALUControl�.,.
Al.USIC:
-,..Qmlo
f'..nntr.nl f,!emWnt& °"Unit Rr.lnr.h
PCSrc
Fund:
=eueCU< ARDlns1r A1 WE
lndruelion .»i"ttA2. AHlJ Uamory A."\ IJW11
lllll•
1:a11
Vt'03 Re,qister IINnNyr FileWD
a) (3 pts) Complete the controller truth table to incorporate instruction management jr1ti.
Instruction Ops:o
R-type 000000 1 lw 100011 1 sw 101011 0 beq 000100 0 addi 001000 1
RegWrite
RegDst AluSrc Branch MemWrite MemtoReg ALUOp1:o 1 0 0 0 0 10
0 1 0 0 1 00 X 1 0 1 X 00 X 0 1 0 X 01 0 1 0 0 0 00 X X 0 0 X XX
j
jrlti
000100 0
Question 3 (6 pts)
3.1 (2 pts) Write in VHDL an external interface (“entity” part) for the 2 modules presented in figure 1, “modulel” and “module2”..
Rp
modulel 1
r-------,
11
---...---1 M1
____;:iL....__
15
1
l.,1 1.'
Figure 1
1
: modu,ePrincipal : �-------'
--�---' 11
rnodute2
3.2 (4 pts) Write in VHDL a structural module “Mainmodule”, Figure l.
Question 4 (6 pts)
Consider the MIPS version with pipeline seen in class.
Show a pipeline state in the right column of the table when executing each statement in the left column, indicating any "stalls" and "forwarding".
4.1 (3 pts) Suppose this is the implementation of the control random fixes (due to branching) at the EXE stage.
Code
20 lw $s0,0($sp)
24 and $s4, $s0, $sl 28 beq $s4, $0, 11 2C addi $s4,$s4,-1 30 addi $sl,$sl,5
34 j loop
38 11: add $v0, $sl, $0
Oioeline state
IF ID EXE MEM WB
a) (3 pts) Suppose this is the implementation of the control random resolution (due to branching) at the decoding stage (ID)
Code
20 lw $s0,0($sp}
24 and $s4, $s0, $s1 28 beq $s4, $0, 11 2C addi $s4,$s4,-1 30 addi $s1,$sl,5
34 j loop
38 11: add SvO, $s1, $0
State of oioeline
IF ID EXE MEM WB
Question 5 (6 pts)
5.1 (2 pt) Show the temporal behavior of the D-latch and D-flip-flop Q output signal. CU< / _\_.
\_
. ___,,/.v''' \
' ''1
D''
'' '' .
,,
Q
Q
"erre� O(IOt<:h D) ' ' .
.. ' ..
'. . . .'. ..
.
'
: '.
.
.
Uasc�l� � lfhp-flcpt ' ' '.
.
:
.' • 4:
:': :' ' ' ' .
--:·�
'''
'
� ;i1 :': 1
': . :
:
:.
'
1
'
- r· i.. ·r ' ' '
''
:'1 . :
:
''
:
1
1
:
:
'
'
___i_· _/
5.2 (2 pts) Implement the following logical functions using an appropriately sized ROM. F(A,B,C,D) = ABCD +BD +AD
G(A,B,C,D);::: AEBB
5.3 (2 pts) The cache has the following parameters:
• • b - size of a block
• • B - number of blocks
• • S - number of sets
• • N - degree of associativity
• • A- number of bits in the address
Assume that the MIPS processor cache has 16 memory words and the processor is performing a sequence of lw addresses operations (addresses are given in hexadecimal).
40 44 48 4C 70 74 78 7C 80 84 88 SC 90 94 98 9C 04 8C 10 14 18 IC 20
Calculate the miss rate by considering a cache organization with direct correspondence and b = 2 words.
...
M I P S Reference Data CORE INSTRUCTION SET
(D
0 ARITHMETIC CORE INSTRUCTION SET FOR-
@ OPCODE
"'O 1
NAME, MNEMONIC
(Hcx)
Divide Unsigned FPAddSingle FP Add
Double
0/-1-/la
â
1 1 1 1 1 1 1 1 1 1
Add add
R R(rd] = R{rs] + R(rt]
R[rt] = R[rs] + SignExtlmm
1 R[rt] = R(rs] + SignExtlmm R R[rd] .. R[rs] + R[n]
R R[rd] = R[rs] & R[rt]
(1)
(1,2) (2)
(J)
(4)
(4)
(S)
0120i,.,.
add.s FR F[fd]=F[fs]+F{ft]
01-1-/Jb U,J0/-/0
f"'l
CIi
.- /ii e
"'O
Add lmmediatc addi Add Imm. Unsigncd addiu Add Unsigned addu And and And lmmediote andi
beq
81,c,
OJ211,e, 0124i.a C1,cx
¾u
51,cx
21,cx 31,cx
add.d FR c.r.:,• FR c.r.d• FR
(F[fd],F{fd+l]I = (F[fs],F[fs+IJ} +
li/li/-/0 11/10/-/y 11/ll/-ly
] 1 u 1
E
R[rt]"'{ l 6'b0,M[R[rs]
25
3�
1 CIi0 1
231,c.t
Multiply
Shift RightArith.
mult R
....= .!a 1
=1 CIi)1
�.....
0/ 27hcx
sra
R
R[rd)=R[n) >» shamt
E
1
(3
0/ 201,c,
Storc FP
sdel
p.
R[rt] ‘”‘(R{rs) < SignExtlmm)? 1 : 0 (2)
Dl,c,
bi.:.
0/2bi,,..
0/00...x 0 /021,e,
281icx
381,c,
2�
2bi,,..
0/�
I
II
I
11 10
1
Load Linkcd 11
Load Upper Imm. lui LoadWoni lw
Nor nor R Or or R Or lmmcdinte ori
Set LCS111l11111 :slt R
Set Lcss Than Imm. slti 1
Sel Lcss Th1111 Imm. sltiu Unsigm:d
SetLcssThllllUnsig.sltu R Shift Left Logical sll R Shift Righi Logical srl R
Store Byte �b
S1orc Conditional se
Store Halfword sh StorcWord sw 1
R[n] = M[R[rs]+SignExtlmm)
R(n]= fimm, l6'b0}
R(n] "'M[R[rs)+SignExtlmm]
R{rd] = - (R[rs] 1 R[n])
R[rd]=R[rs) 1 R[n]
R[rt] = R[rs] 1 ZcroExtlmm
R[rd)., (R[rs] < R[rt))? 1 : 0
Movc From Hi
R
R(rd] = Hi
R[rd]=Lo R[rd)=CR[rs)
(Hi,Lo) 2 R[rs) • R[rt}
1 1
NAME, MNEMONIC MAT OPERATION
/FMT/FT fFUNCT (Hcx)
Branch On Equal
•(xisé-q,1�,orle) (opis=,<,or<=)(yis32,Je,orJe) FPDividcSingle div.s FR F[fd)""F[fs)/F[ft}
11/10/-/J
Branch On Not Equal bne Jump
Jwnp And Link jal
Jump Register jr
Lood Byte Unsigncd lbu
Load Halfword lhu Unsigncd
PC=PC-+4-+BranchAddr J PC"'JumpAddr
Double
FP Multiply
ll/11/-/J
FOR-
MAT OPERATION (in Vcrilog)
/FUNCT
Divide
dlv R Lo=R[rs)/R(n]; Hi=R[rs]%R[rt}
divu R Lo=R[rs)/R[n]; Hi=R[rs)%R[rt] (6)
11/8/0/-
R[rt) = R[rs] & ZcroExtlmm it{R[rs]=R[n])
FPCompan, Double
PC,.PC+4+BranchAddr if{R[rs]! R[n])
FP Divide
div.d FR
mul.d FR
( F[fd),F{fd+IJ} = {F(fs),F(fs+l]) / {F(ft],F[ft+I)} 11/10/-/2
J R[J 1]=PC+8;PC,.JumpAddr R PC,,,R[rs]
Double
{F[ft],F(ft+l}l
l l/11/-/Z 11/10/-/1 11/11/-/I
(2) 31/-t-/- -
0 /-/-/10 0/-/-/12 10 /0/-/0 0/-/-118 (6) 0/-/-/19 0/-/-/3
-
funct
6 5 0
(5) +SignExtlmm](7.0)) (2)
0/08""" 2¾u
FP Subtract Single FP Subtracl Double LoadFPSingle Load FP
sub. s sub.d lwet
FR FR
F[fd]=F(fs] • F(ft]
(F[fdJ,F{fd+l]l = (F[fs],F[fs+l}l -
R[n]=(24'b0,M[R[rs]
{F[ft],F[ft+1)) F[rt}"'M{R[rs]+SignExtlmm]
+SignExtlmm)( 1 S:O)}
(2)
(2,7)
(2)
)
1,cx
mfhi MoveFromLo mflo R Move From Control mfc0 R
R[n] = (R[rs] < SignExtlmm)
opcode j fmt ft
? 1: 0
(2,6) (6)
FR fs
fd
OPCODE
Branch On FPTruc bclt FI ifl:FPcond)PC=xPC+4+BranchAddr (4) Branch On FP False bel f FI it{!FPcond)PC=PC+4+BrunchAddr(4)
11/8/1/
91,c,
(F[ft],F[ft+l]}
f1,cx
0/25 , dhc hcx
I FLOATING-POINT INSTRUCTION FORMATS
FP Compare Single
FPcond = (F[fs] op F[ft))? 1 : 0 (F(ft],F[ft+l]})? 1 : 0
Store FP Single
swel
M[R[rs]+SignExllmm] .. F(rtJ
( F[fd],F{fd+I]) -= {F[fs],F[fs+l)l •
i
I
I
immcdintc
Ssp
Subtract
Subtroct Unsigncd
:,ub R
R[nl) = R[rs) REGISTER NAME, NUMBER, USE, CALL CONVENTION
BASIC INSTRUCTION FORMATS
1 ni 16 1'
1615
!
Ss0-Ss7 SkO-Skl
R I opcode I
131 opcode 26j2S
rs 1 rt
1 shnmt
funct
31
2615
2120
Stp
rs 21 20 !
rt
il 10 6 5
0
S1,tp
R[ni]"'(R[rs]
M[R[rs}+Si1,’11Extlmm) z R[rt];
R{rt) = (alomic)? 1 : 0 (2,7)
M[R[rs]+SignExtlmm],.. R[rt} (2)
R[rd]=R[rs] – R[rt) (1)
Branch Lcss Than blt Bran�h Grcatcr Th1111 bgt Branch Less Than or Equal ble Branch Grcater Than or Equal bge Load lmmcdiote l1 Movc move
iflR[rsJ<=R[rtJ) PC= Label
M[R[rs]+SignExtlmm](IS:0)"' R[rt}(IS:0) (2)
iflR[mJ:,o,R[rtJ) PC= Label
0/231,c, (4) BrunchAddr = ( 14{immcdiote[l5J), immcdiatc, 2'b0}
NAME NUMBER Szcro 0
1
8-1S 16-23 24-2S 26-27 28 29 30 31
USE PRESERVEDACROSS
subu R
( 1 ) May couse ovcrflow e,i;ccption
(2) SignExtlmm = ( l6{immcdia1c(IS]), immcdiatc} (J) ZcroExtlmm = ( 16( lb'0}, immcdiatc}
R[rd] = R[rs] - R[rt]
ACALL?
(5) JwnpAddr= ( PC+4[31:28), nddrcss, 2'b0}
(6) Operands c;onsidcrcd unsigncd numbers (vs. 2's c:omp.)
(7) Atomic lcst&sct pair; R[rt] = 1 ifpair atomic, 0 ifnot otomic:
SvO-Svl
2-3 4-7
Assembler Tcmporary No Values for Funct1on Rcsults No and Expression Evaluation
Arguments No Tcmporancs No Saved Tcmporurics Ycs Temporancs No Rescrvcd for OS Kemct No Global Pointer Ycs Stack Pointer Ycs Frame Pointer Ycs Retum Addrcss Ycs
!
31
!
li 26 15 21 20 16 15
Sat
The Constant Value 0 N.A.
St0-St7
ft NAME MNEMONIC
immcdintc
21 20
16 .,
o
R[rd] = immediate
J
Copyright 2009 by Elsevier, Inc., Ali rights rcscrvcd. From Pattcrson nnil Hcnnessy, Compuler Organi:ation und Design, 4th cd.
opcodc
addrcss
$ra
JI 2625
0
FPc:ond"'((F[fsJ,F[fs+l]} op
ldct F[rt]=M[R[rs]+SignExtlmm]; (2) 3S/-/-/
(2) 39/-1-/-
FPMultiplySinglc mul.s FR F[fd]=F[fs]•F[ft]
Multiply Unsigncd multu R (Hi,Lo} .. R[rs] • R[rt] M[R(rs]+SignExtlmm)=F[rt]; (2) Jd/-1-1
Double F[rt+l)=M[R[rs]+SignExtlmm+4]
Double M[R[rs)+SignExtlmm+4]=F[rt+I)
Sa0-SaJ
St8-St9
Double Pntclslon Formats: ble.< srlv 1 s 1 Exponcnl 1
S.P. MAX= 255, D.P. MAX= 2047
cvt.w.
C
EXCEPTION CONTROL REGISTERS: CAUSE AND STATUS
IEEE 754 FLOATING-POINT STANDARD
Double Pn:cision Bias = 1023. IEEE Single Preclslon and
IEEE 754 Svmbols
opçode funct funct sll (
Exponcnt Fracuon ObJCCI 00:t0
0 at0 :t Dcnonn
j srl jal sra beq sllv bne
1 toMAX-1 llflything ±FI.Pt. Num. MAX 0 :too MAX ;tO NnN
bgtz St4V
addi jr
addiu jalr
slti movz
sltiu movn MEMORY ALLOCATION
0
6) 62 Exponcnt SZSI andi syscall Ssp ➔ 7flffffcbcx Stack
H=:J
li ]O 1322
Fraction
Fraction
STACKFRAME
Byte Byte
Value ofthrce lcast significanl bits of byte addrcss (Big Endillll)
Byte
Byte
Byte
Byte
B lntc:rrupt Exception Mask Code
1
Highcr Mcmory Addn:sscs
Lower Mcmory Addrcsscs
I
ori break M
xorl sync N0 mfhi
Sfp
Ssp
(2) mthi Q OynajcData mflo movz/ R
Siai Grows
mtlo movn. s 1000 OOIXli.:x Sllltic Data Tcxt
mult
multu °'1cx Rcscrvcd
ck
divu lb add
lh addu lwl sub lw subu lbu and
or
lwr xor sb nor
DATA ALIGNMENT
Word
DoubleWord
Hnlfword Halfword
Word
Halfword
I
I
1 Halfword
I
I
I
u Byte IByte b012J4.S61
C f
)1 IS 6
sh i Penmgu
:,wl
SW
:,wr
cache
11
lwcl
lwc2
prer
ldcl
ldc2
SC
swcl
swc2
sdcl
j sltu k
lntcrrupt M
IS 1 ◄ 1o
slt
mn 0p
80 = Branch Delay, UM = User Mode, EL .. Exception Level, IE eJntc1TUpt Enablc
EXCEPTION CODES
NumbcrNmnc Cause of Exception Numbcr Nmnc
Cause of Excaition Brcrumoint Excaition Rcscrved lnstrucllon Excention Coproccssor Unimnlcmcnlcd Arithmetic Ovcrflow Exccotion
sdc2
c.ngef Il 1101 61
7d
SIZE
tolS, 2S0 Pctn• 10·3 milli- IOIK,2611 Exa- 10-6 micro- 1o2I, 270 Zctta- 10·9 nano- 1024, 280 Yotta• 10·12 pico-
SIZE FIX 10·15 fomto-
tge
tne
0
4
5
lnt lnterrupl (hardware) 9 AdEL Adllress Error Exccpuon 10 (Joad or instruction fctch) AdES Addrcss E1tor Exception li
Bp
RI
CpU
tgeu q tlt r s teq c.o t c.u u c.o V
(store}
6
c.u w 7 DBE BusE1toron 13 Tr Trap
c.s Xy c.n
c.:, zl c.n
8
SIZEP
Sys
Loa d o r S i o n:
Sysc1111 Exccullon 15 FPE Floallnl! Point Excention
PRE- FIX Kilo- Mc!lll- Giga- Tcra-
c.l C
c.ngt. 111111 63 lf ? 127 7( DEL ( 1) opcodc(l l :26) = o
uiJ,210
(2)opcodc(ll:26)= 171m (ll hcx); iffmt(2S:21)=16ia,(10i.,.)/= s (single); if fint(25:21)=171en (l lhcxl/”” d (double)
106,220
1o•IK alto- 10·21
10•24 vocto-
ThC sym1bol tor cach prcfiit 1s ust Ils tirst lcttcr, cxccpt μ is uscd for miero. Copyright 2009 by Elsevier, Inc., Ali rights n:scrvcd. From Pattc:rson and Hcnncssy, Computer Organization and Design. 4th cd.
!BE Bus E1toron 12 Instruction Fctch
109,230 1012. 240
Ov
(-1)5 x (1 + Fruction) x 2(Exponcnt-Bias)
(31 :26) (5:0)
lhu
lui
div
Sgp.+1000 800011cx
“”1110-
wherc Single Pn:cision Bias = 127,
pc -.ooio0000…..
tltu
c.u
RERXES (1011 for Dlsk, Communication: 211 for Memorv)
PRE•