SCHOOL OF ENGINEERING
DIGITAL SYSTEM DESIGN 4 ELEE10007
Exam Date: 21/05/2018 From and To: 14:30 – 16:30 Exam Diet: May 2018 Please read full instructions before commencing writing
Exam paper information
• This paper consists of TWO sections
• Candidates should attempt THREE questions, chosen as follows:
• Section A: ONE question. Attempt the whole section.
• Section B: Attempt TWO out of the THREE questions.
Special instructions
• Students should assume reasonable values for any data not given in a question nor available on a datasheet, and should make any such assumptions clear on their script.
• Students in any doubt as to the interpretation of the wording of a question, should make their own decision, and should state it clearly on their script.
• Please write your name in the space indicated at the right hand side on the front cover of the answer book. Also enter your examination number in the appropriate space on the front cover.
• Write ONLY your examination number on any extra sheets or worksheets used and firmly attach these to the answer book(s).
• This examination will be marked anonymously.
Special items
• MIPS Green Card (2 pages)
Convenor of Board of Examiners: Professor R Cheung External Examiners: Professor J Morrow and Dr Z Durrani
SECTION A Question A1
a) How has the development of the transistor affected computers? What technology did the transistor replace? (2)
b) Prior to the early 1980s, machines were built with more and more
complex instruction sets. The MIPS architecture is a RISC machine.
Why has there been a move to RISC machines away from complex instruction machines? (2)
c) Describe the three main types of hazards in microprocessors. (2)
d) Describe the motivation for pseudo-instructions, and explain the
implementation of the mov $rt, $rs pseudo-instruction in MIPS. (2)
e) Consider two different implementations, M1 and M2, of the same instruction set. There are three classes of instructions (A, B, and C) in the instruction set. M1 has a clock rate of 800 MHz and M2 has a clock rate of 1 GHz. The average number of cycles for each instruction class and their frequencies (for a typical program) are as follows:
Instruction Class
M1 – Cycles/ Instruction class
M2 – Cycles/
Instruction Frequency
class
A
1
2
60%
B
2
3
30%
C
4
4
10%
(i) Calculate the average CPI for machines M1, and M2.
(2) (2)
(3)
(3)
(2)
(ii) Calculate the average MIPS ratings for machines M1, and M2.
(iii) For the machine with the lower MIPS rating, determine which individual instruction class CPI you need to change, and by how much, to have this machine have the same or better performance as the machine with the higher MIPS rating. You can only change the CPI for one of the instruction classes on the slower machine.
(iv) Comment on the relative performance change for the improved processor, stating which of the “Eight Great Ideas in Computer Architecture” this represents.
f) A fundamental problem with some modern computer architectures has been reported widely in the media recently, briefly explain the “Meltdown Vulnerability”.
ELEE10007 Digital System Design 4 – May 2018
SECTION B Question B1
a) Consider a MIPS processor which is composed of multiple pipelined stages.
(i) Using a diagram, explain how pipelining affects the
performance of a processor. (2)
(ii) Again, using diagrams, fully explain the factors affecting the choice of architecture (Harvard or Von Neumann) that a system designer would consider when implementing a pipelined MIPS processor.
(iii) Load/store, and register/memory are two different designs of instruction set architecture. Briefly describe the advantages and disadvantages of each architecture and explain which has been used to implement MIPS.
(4) b) Flynn’s taxonomy is a system for classifying computer architectures.
(i) Explain Flynn’s classifications. In addition to a written
explanation, your answer must include four labelled diagrams showing instruction memory, CPU(s) and data memory. (8)
(ii) Provide one use-case example for a SIMD architecture, and another for a MISD architecture. (2)
ELEE10007 Digital System Design 4 – May 2018
(4)
Question B2
a) Consider a 32-bit MIPS architecture and suppose the programme counter (PC) is currently set to 0x2000 0000. Consider two instructions: branch-on-equal (beq) and jump (j).
(i) Explain the addressing mode for these two instructions. Draw
the diagram that shows their physical implementations and the width of all busses. (4)
(ii) Is it possible to use the jump (j) instruction to set the PC to the address as 0x2020 0000? Is it possible to use the branch-on-
equal (beq) instruction to set the PC to this same address?
Explain the reason for full marks. (4)
b) Considering the following MIPS loop:
LOOP: slt $t2, $0, $t1 beq $t2, $0, DONE
0010 0001 0010 1001 1111 1111 1111 1111 addi $s2, $s2, 2
j LOOP
DONE:
(i) The third instruction is shown as machine code instead of assembly language. Use the MIPS green-card to decode this instruction to the assembly language representation.
(ii) Assume that the register $t1 is initialized to the value 10
(decimal). What is the value in register $s2 assuming $s2 is
initially zero? In your answer you should explain what this (4) MIPS loop is doing.
c) Figure B2c shows a simplified MIPS datapath for a single-cycle CPU with all the necessary connections from the master control unit and ALU control units shown.
The input to the master control unit is the 6-bit opcode field from the instruction. The outputs consist of three 1-bit signals that are used to control multiplexors (RegDst, ALUSrc, and MemtoReg), three signals for controlling reads and writes in the register file and data memory (RegWrite, MemRead, and MemWrite), a 1-bit signal used in determining whether to possibly branch (Branch), and a 2-bit control signal for the ALU (ALUOp).
Use your knowledge of the datapath, and the MIPS greencard to
specify a truth table that could be used to implement the master
controller. Specify this table for three MIPS instructions: set less than
(slt), load word (lw), and branch on not equal (bne). (6)
Continued overleaf
ELEE10007 Digital System Design 4 – May 2018
(2)
Figure B2c
ELEE10007 Digital System Design 4 – May 2018
Question B3 a)
b)
(i) What are the two main aims of a hierarchical system of
computer memory and storage? (2)
(ii) Explain the two forms of locality exploited by a cache memory system and describe a data structure or a software routine
which makes use of each type? (6)
c)
Given a directly mapped cache architecture with the following characteristics:
• Cache size of 32 KiB (remember 1 KiB is 210 bytes)
• Block size of 16 words (64 bytes)
• 32 bit address size
State:
(i) How many blocks are in the cache?
(ii) How many bits are in the cache index section of the address?
(iii) How many bits are in the tag section of the address?
If the cache in QB3b is changed to have 4-way set associativity:
(1) (1) (1)
(i) Define the new address structure with a suitable diagram. (3)
(ii) State which cache you would expect to have a better hit rate
and give a reason why. (2)
(iii) Assume this 4-way set associative system is a level 1 instruction cache with a “least recently used” replacement policy. With the aid of a suitable diagram, describe the structure of the cache. This should include any informational bits required, along with the hardware used to select the correct block and confirm a cache hit.
(4)
ELEE10007 Digital System Design 4 – May 2018
END OF PAPER
M I P S Reference Data CORE INSTRUCTION SET
1
ARITHMETIC CORE INSTRUCTION SET
2
OPCODE / FMT /FT / FUNCT (Hex) 11/8/1/– 11/8/0/– 0/–/–/1a 0/–/–/1b 11/10/–/0
11/11/–/0 11/10/–/y 11/11/–/y
11/10/–/3
11/11/–/3
11/10/–/2
11/11/–/2
11/10/–/1
11/11/–/1
31/–/–/–
35/–/–/–
0 /–/–/10 0 /–/–/12 10 /0/–/0 0/–/–/18 0/–/–/19 0/–/–/3 39/–/–/–
3d/–/–/–
0
0
NAME, MNEMONIC Add add Add Immediate addi Add Imm. Unsigned addiu Add Unsigned addu And and And Immediate andi
Branch On Equal beq Branch On Not Equalbne
Divide
Divide Unsigned
FP Add Single
FP Add
Double
FP Compare Single c.x.s* FP Compare
Double c.x.d*
Lo=R[rs]/R[rt]; Hi=R[rs]%R[rt] R Lo=R[rs]/R[rt]; Hi=R[rs]%R[rt]
Jump
Jump And Link Jump Register
Load Byte Unsigned
Load Halfword Unsigned
Load Linked
Load Upper Imm.
Load Word
Nor
Or
Or Immediate
Set Less Than
Set Less Than Imm.
Set Less Than Imm. Unsigned
Set Less Than Unsig. Shift Left Logical Shift Right Logical
Store Byte
Store Conditional
Store Halfword
Store Word Subtract
Subtract Unsigned
j J jal J jr R
lbu I lhu I
ll I lui I lw I nor R or R ori I slt R slti I
sltiu I sltu R
sll R srl R
sb I sc I
sh I sw I
sub R subu R
PC=JumpAddr R[31]=PC+8;PC=JumpAddr PC=R[rs] R[rt]={24’b0,M[R[rs]
(5) 2hex (5) 3hex
F[fd]=F[fs] – F[ft]
{F[fd],F[fd+1]} = {F[fs],F[fs+1]} –
{F[ft],F[ft+1]} F[rt]=M[R[rs]+SignExtImm] F[rt]=M[R[rs]+SignExtImm];
F[rt+1]=M[R[rs]+SignExtImm+4] R[rd] = Hi
R[rd] = Lo
R[rd] = CR[rs]
{Hi,Lo} = R[rs] * R[rt]
{Hi,Lo} = R[rs] * R[rt]
R[rd] = R[rt] >>> shamt M[R[rs]+SignExtImm] = F[rt] M[R[rs]+SignExtImm] = F[rt]; M[R[rs]+SignExtImm+4] = F[rt+1]
FOR-
MAT OPERATION (in Verilog)
R R[rd] = R[rs] + R[rt]
I R[rt] = R[rs] + SignExtImm I R[rt] = R[rs] + SignExtImm
R R[rd] = R[rs] + R[rt] R R[rd] = R[rs] & R[rt]
I R[rt] = R[rs] & ZeroExtImm
OPCODE / FUNCT (Hex)
(1) 0 / 20hex (1,2) 8hex
(2) 9hex
0 / 21hex
0 / 24hex
(3) chex
FOR- NAME, MNEMONIC MAT
Branch On FP True bc1t FI Branch On FP False bc1f FI
div R
OPERATION if(FPcond)PC=PC+4+BranchAddr (4) if(!FPcond)PC=PC+4+BranchAddr (4)
I if(R[rs]==R[rt]) 4hex
PC=PC+4+BranchAddr (4)
I if(R[rs]!=R[rt]) 5hex PC=PC+4+BranchAddr (4)
FP Divide Single FP Divide
Double
FP Multiply Single FP Multiply Double
FP Subtract Single FP Subtract Double
Load FP Single Load FP
Double
Move From Hi Move From Lo Move From Control Multiply
Multiply Unsigned Shift Right Arith. Store FP Single Store FP
Double
div.s FR div.d FR mul.s FR mul.d FR sub.s FR sub.d FR
F[fd] = F[fs] / F[ft] {F[fd],F[fd+1]} = {F[fs],F[fs+1]} /
{F[ft],F[ft+1]} F[fd] = F[fs] * F[ft]
{F[fd],F[fd+1]} = {F[fs],F[fs+1]} * {F[ft],F[ft+1]}
+SignExtImm](7:0)} (2)
0 / 08hex 24hex
lwc1 ldc1
mfhi mflo mfc0 mult multu sra swc1
sdc1
I
I
R R R R R R I
I
(2) (2)
(6)
(2) (2)
6 5
R[rt]={16’b0,M[R[rs] +SignExtImm](15:0)}
R[rt] = M[R[rs]+SignExtImm] R[rt] = {imm, 16’b0}
R[rt] = M[R[rs]+SignExtImm] R[rd] = ~ (R[rs] | R[rt])
R[rd] = R[rs] | R[rt]
R[rt] = R[rs] | ZeroExtImm
R[rd] = (R[rs] < R[rt]) ? 1 : 0 R[rt] = (R[rs] < SignExtImm)? 1 : R[rt] = (R[rs] < SignExtImm)
? 1 :0
R[rd] = (R[rs] < R[rt]) ? 1 : 0
R[rd] = R[rt] << shamt
R[rd] = R[rt] >> shamt M[R[rs]+SignExtImm](7:0) =
R[rt](7:0) M[R[rs]+SignExtImm] = R[rt]; R[rt] = (atomic) ? 1 : 0 M[R[rs]+SignExtImm](15:0) =
(2) 25hex (2,7) 30hex
fhex
(2) 23hex
0 / 27hex
0 / 25hex
(3) dhex
0 / 2ahex
0 (2) ahex
(2,6)
(6) 0 / 2bhex
FLOATING-POINT INSTRUCTION FORMATS
31 26 25 21 20 16 15 11 10
31 26 25 21 20 16 15
divu add.s
(6)
add.d
FR F[fd ]= F[fs] + F[ft]
FR {F[fd],F[fd+1]} = {F[fs],F[fs+1]} +
{F[ft],F[ft+1]} FR FPcond = (F[fs] op F[ft]) ? 1 : 0
FPcond = ({F[fs],F[fs+1]} op
FR {F[ft],F[ft+1]}) ? 1 : 0
* (x is eq, lt, or le) (op is ==, <, or <=) ( y is 32, 3c, or 3e)
bhex
FR FI
opcode
fmt
ft
fs
fd
funct
opcode
fmt
ft
immediate
0 / 00hex 0 / 02hex
28hex 38hex 29hex
(2) 2bhex (1) 0 / 22hex 0 / 23hex
PSEUDOINSTRUCTION SET
NAME Branch Less Than
Branch Greater Than
Branch Less Than or Equal
Branch Greater Than or Equal
Load Immediate
Move move
BASIC INSTRUCTION FORMATS
M[R[rs]+SignExtImm] = R[rt] R[rd] = R[rs] - R[rt]
R[rd] = R[rs] - R[rt]
REGISTER NAME, NUMBER, USE, CALL CONVENTION
(2) (2,7) R[rt](15:0) (2)
blt bgt ble bge li
MNEMONIC
OPERATION if(R[rs]
if(R[rs]<=R[rt]) PC = Label if(R[rs]>=R[rt]) PC = Label R[rd] = immediate
R[rd] = R[rs]
NAME NUMBER USE
PRESERVED ACROSS A CALL?
$zero 0 The Constant Value 0 N.A.
$at 1 Assembler Temporary No
$v0-$v1 2-3 Values for Function Results No and Expression Evaluation
$a0-$a3 4-7 Arguments No
$t0-$t7 8-15 Temporaries No
$s0-$s7 16-23 Saved Temporaries Yes
$t8-$t9 24-25 Temporaries No
$k0-$k1 26-27 Reserved for OS Kernel No
$gp 28 Global Pointer Yes
$sp 29 Stack Pointer Yes
$fp 30 Frame Pointer Yes
$ra 31 Return Address No
(1) May cause overflow exception
(2) SignExtImm = { 16{immediate[15]}, immediate
(3) ZeroExtImm = { 16{1b’0}, immediate }
(4) BranchAddr = { 14{immediate[15]}, immediate, 2’b0 }
(5) JumpAddr = { PC+4[31:28], address, 2’b0 }
(6) Operands considered unsigned numbers (vs. 2’s comp.)
(7) Atomic test&set pair; R[rt] = 1 if pair atomic, 0 if not atomic
}
31 26 25 21 20 16 15 11 10 6 5 0
R I J
opcode
rs
rt
rd
shamt
funct
opcode
rs
rt
immediate
31 26 25 21 20 16 15
31 26 25
0
0
opcode
address
Copyright 2009 by Elsevier, Inc., All rights reserved. From Patterson and Hennessy, Computer Organization and Design, 4th ed.
MIPS Reference Data Card (“Green Card”) 1. Pull along perforation to separate card 2. Fold bottom side (columns 3 and 4) together
OPCODES, BASE CONVERSION, ASCII SYMBOLS
3
IEEE 754 FLOATING-POINT
STANDARD
(-1)S × (1 + Fraction) × 2(Exponent – Bias) where Single Precision Bias = 127,
Double Precision Bias = 1023.
IEEE Single Precision and Double Precision Formats:
31 30 2322
63 62 5251
MEMORY ALLOCATION
4
IEEE 754 Symbols
S.P. MAX = 255, D.P. MAX = 2047
MIPS opcode (31:26)
(1) MIPS funct (5:0)
(2) MIPS funct (5:0)
Deci- Hexa- ASCII Binary mal deci- Char- mal acter
Deci- Hexa- ASCII mal deci- Char- mal acter
(1) sll add.f sub.f j srl mul.f jal sra div.f
00 0000 0 0 NUL 00 0001 1 1 SOH 00 0010 2 2 STX 00 0011 3 3 ETX
64 40 @ 65 41 A 66 42 B 67 43 C
beq sllv sqrt.f bne abs.f blez srlv mov.f bgtz srav neg.f
00 0100 4 4 EOT 00 0101 5 5 ENQ 00 0110 6 6 ACK 00 0111 7 7 BEL
68 44 D 69 45 E 70 46 F 71 47 G
addi jr addiu jalr slti movz sltiu movn
00 1000 8 8 BS 00 1001 9 9 HT 00 1010 10 a LF 00 1011 11 b VT
72 48 H 73 49 I 74 4a J 75 4b K
andi syscall round.w.f ori break trunc.w.f xori ceil.w.f lui sync floor.w.f
00 1100 00 1101 00 1110 00 1111
12 c FF 13 d CR 14 e SO 15 f SI
76 4c L 77 4d M 78 4e N 79 4f O
mfhi (2) mthi
mflo movz.f mtlo movn.f
01 0000 01 0001 01 0010 01 0011
16 10 DLE 17 11 DC1 18 12 DC2 19 13 DC3
80 50 P 81 51 Q 82 52 R 83 53 S
01 0100 01 0101 01 0110 01 0111
20 14 DC4 21 15 NAK 22 16 SYN 23 17 ETB
84 54 T 85 55 U 86 56 V 87 57 W
mult multu div divu
01 1000
01 1001
01 1010
01 1011 27 1b ESC
24 18 CAN 25 19 EM 26 1a SUB
88 58 X 89 59 Y 90 5a Z 91 5b [
01 1100 01 1101 01 1110 01 1111
28 1c FS 29 1d GS 30 1e RS 31 1f US
92 5c \ 93 5d ] 94 5e ^ 95 5f _
lb add cvt.s.f lh addu cvt.d.f lwl sub
lw subu
10 0000 10 0001 10 0010 10 0011
32 20 Space 33 21 ! 34 22 ” 35 23 #
96 60 ‘ 97 61 a 98 62 b 99 63 c
lbu and cvt.w.f lhu or
lwr xor
nor
10 0100 10 0101 10 0110 10 0111
36 24 $ 37 25 % 38 26 & 39 27 ’
100 64 d 101 65 e 102 66 f 103 67 g
sb
sh
swl slt sw sltu
10 1000 10 1001 10 1010 10 1011
40 28 ( 41 29 ) 42 2a * 43 2b +
104 68 h 105 69 i 106 6a j 107 6b k
swr cache
10 1100 10 1101 10 1110 10 1111
44 2c , 45 2d – 46 2e . 47 2f /
108 6c l 109 6d m 110 6e n 111 6f o
ll tge c.f.f lwc1 tgeu c.un.f lwc2 tlt c.eq.f pref tltu c.ueq.f
11 0000 11 0001 11 0010 11 0011
48 30 0 49 31 1 50 32 2 51 33 3
112 70 p 113 71 q 114 72 r 115 73 s
teq c.olt.f c.ult.f ldc2 tne c.ole.f c.ule.f
ldc1
11 0100 11 0101 11 0110 11 0111
52 34 4 53 35 5 54 36 6 55 37 7
116 74 t 117 75 u 118 76 v 119 77 w
sc c.sf.f
swc1 c.ngle.f
swc2 c.seq.f
c.ngl.f
11 1000 11 1001 11 1010 11 1011
56 38 8 57 39 9 58 3a : 59 3b ;
120 78 x 121 79 y 122 7a z 123 7b {
c.lt.f
sdc1 c.nge.f
sdc2 c.le.f c.ngt.f
11 1100 11 1101 11 1110 11 1111
60 3c < 61 3d = 62 3e > 63 3f ?
124 7c | 125 7d } 126 7e ~ 127 7f DEL
Exponent
Fraction
Object
0
0
±0
0
≠0
± Denorm
1 to MAX – 1
anything
± Fl. Pt. Num.
MAX
0
±∞
MAX
≠0
NaN
S
Exponent
Fraction
S
Exponent
Fraction
…
Argument 6
Argument 5
Saved Registers
Local Variables
Stack
Dynamic Data
Static Data
Text
Reserved
$sp
$gp
pc
7fff fffchex
1000 8000hex 1000 0000hex 0040 0000hex
0hex
STACK FRAME
$fp
$sp
0
0
Higher Memory Addresses
Stack Grows
Lower Memory Addresses
DATA ALIGNMENT
Double Word
Word
Word
Halfword
Halfword
Halfword
Halfword
Byte
Byte
Byte
Byte
Byte
Byte
Byte
Byte
01234567 Value of three least significant bits of byte address (Big Endian)
EXCEPTION CONTROL REGISTERS: CAUSE AND STATUS
31 15 86 2
B D
Interrupt Mask
Exception Code
Pending
Interrupt
15 8
U
M 4
E
L 1
I
E 0
BD = Branch Delay, UM = User Mode, EL = Exception Level, IE =Interrupt Enable
EXCEPTION CODES
SIZE PREFIXES (10x for Disk, Communication; 2x for Memory)
if fmt(25:21)==17ten (11hex) f = d (double)
Copyright 2009 by Elsevier, Inc., All rights reserved. From Patterson and Hennessy, Computer Organization and Design, 4th ed.
Number Name Cause of Exception
Number Name Cause of Exception
0 Int Interrupt (hardware)
9 Bp Breakpoint Exception
4 AdEL Address Error Exception (load or instruction fetch)
10 RI
Reserved Instruction Exception
5 AdES Address Error Exception (store)
11 CpU
Coprocessor Unimplemented
6 IBE
Bus Error on Instruction Fetch
12 Ov
Arithmetic Overflow Exception
7 DBE
Bus Error on Load or Store
13 Tr Trap
8 Sys Syscall Exception
15 FPE Floating Point Exception
PRE- SIZE FIX
PRE- SIZE FIX
PRE- SIZE FIX
PRE- SIZE FIX
103, 210 Kilo-
1015, 250 Peta-
10-3 milli-
10-15 femto-
106, 220 Mega-
1018, 260 Exa-
10-6 micro-
10-18 atto-
109, 230 Giga-
1021, 270 Zetta-
10-9 nano-
10-21 zepto-
1012, 240 Tera-
1024, 280 Yotta-
10-12 pico-
10-24 yocto-
(1) opcode(31:26) == 0
(2) opcode(31:26) == 17ten (11hex); if fmt(25:21)==16ten (10hex) f = s (single);
The symbol for each prefix is just its first letter, except μ is used for micro.
MIPS Reference Data Card (“Green Card”) 1. Pull along perforation to separate card 2. Fold bottom side (columns 3 and 4) together