Student ID:
Question 1 Digital Logic and K-Map (12 marks)
Gray code, named after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, refer to the following table, Gray code of 5 (0111) differs with Gray code of 4 (0110) at G0 only, and differs with Gray code of 6 (0101) at G1 only. Note Gray code only applies to unsigned, i.e. non-negative, integers.
Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
a) Complete the following table of the 4-bit Gray code. (3 marks)
__
Sequence number
Unsigned Binary Representation B3B2B1B0
4-bit Gray code
G3G2G1G0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
2
0
0
1
0
0
0
1
1
3
0
0
1
1
0
0
1
0
4
0
1
0
0
0
1
1
0
5
0
1
0
1
0
1
1
1
6
0
1
1
0
0
1
0
1
7
0
1
1
1
0
1
0
0
8
1
0
0
0
1
1
0
0
9
1
0
0
1
1
1
0
1
10
1
0
1
0
1
1
1
1
11
1
0
1
1
1
1
1
0
12
1
1
0
0
1
0
1
0
13
1
1
0
1
1
0
1
1
14
1
1
1
0
1
0
0
1
15
1
1
1
1
1
0
0
0
b) A 4-bit Gray code generator takes the sequence number (represented in 4-bit unsigned binary format) and generates the corresponding 4-bit Gray code. For example, given 0111 (sequence number 7), the circuit generates Gray code 0100. Assume inputs are B3B2B1B0 and output are G3G2G1G0 (where B0 and G0 are least significant bit).
Draw K-map for output G1 and then use it to derive the simplest sum-of-product logic expression of G1 (eae cice he g f 1 i he K-map). (5 marks)
G1 = ____________________________
2
Answer:
B3B2\B1B0 00 01 11 10
00 0 0
01 00 11 00 10 0 0
𝐺 𝐵1𝐵2𝐵1𝐵2 𝐵1⨁𝐵2;
c) Build the 4-bit Gray code generator with exclusive-OR (XOR) gate only. Draw the circuit. You can use as many as XOR gates as needed. (4 marks)
Symbolic diagram of XOR gate
Answer:
G0=𝐵1⨁𝐵0 G1=𝐵2⨁𝐵1 G2=𝐵3⨁𝐵2 G3=B3
Student ID:
__
1
1
1 11
1
1
1
A
B
Out
0
0
0
0
1
1
1
0
1
1
1
0
3
Student ID:
Question 2 Understanding MIPS Program (7 marks)
Read the following recursive MIPS procedure and answer questions. For simplicity, you may assume initial values in $a0 and $a1 are always unsigned integers.
__
1)
2)
3)
4)
5)
6)
7)
8)
9)
10) sw $ra, 0($sp)
11) sub $a0, $a0, $a1
12) jal procedure
13) lw $ra, 0($sp)
14) addi $sp, $sp, 4
15) addi $v0, $v0, 1
16) jr $ra
procedure:
slt $t0, $a0, $a1
beq $t0, $zero, label
addi $v0, $zero, 0
jr $ra
label:
addi $sp, $sp, -4
a) If register $a0 holds the integer 5, and register $a1 holds the integer 2 before calling procedure. What will be the value in $v0 when the procedure returns? Write a single value only. (2 marks)
Answer: 2
b) What is the return value in $v0 with respect to the initial values in $a0 and $a1? Explain in a single sentence only. (3 marks)
Answer: $v0 holds the quotient of integer division of $a0 (dividend) by $a (divisor)
c) If add $v1,$a0,$zero is added to line 5, what is the return value in $v1 with respect to the initial values in $a0 and $a1? Explain in a single sentence only. (2 marks)
Answer: $v1 holds the remainder of integer division $a0 (dividend) by $a1 (divisor)
4
Student ID:
Question 3 MIPS Programming (10 marks)
A palindrome is a word that will be the same no matter you spell it from the left to the right or from the right to the left. For example he d ee i a aide. The d cee he he hand is not a palindrome. Any single letter word is considered to be a palindrome, for example the d a, i a aide.
The C++ function palindrome()is shown below:
bool palindrome(char* word, int length) {
int i=0;
int j=length-1;
while (i
Sign bit=1
Exponent=0
Significand = 10 000 0000
-11*0.1 * 2-14= -2-1-14=-2-15
Sign
Exponent
Significand
8
Student ID:
c) Ecdig NAN ad , how many distinct numbers can be represented by the 16float standard? Note: +0 and -0 are considered to be a single number, +1.5 and -1.5 on the other hand are two numbers. Justify your answer or show your calculation briefly. (2 marks)
Answer:
For each exponent value in the normalized range, we have 2*210 different numbers (including ve,+ve),
We have 25-2=30 exponent numbers in the normalized range
30*211
For the exponent value 0, we have 2*210 -1 different numbers ( includes all the ve,+ve numbers, counting -0,+0 as a single number).
For the exponent value 31, e hae 0 ae, a he be ae eihe NAN for that exponent value.
Therefore in total it can represent 30*211+ 2*210 -1=31*211 -1 = (25-1)*211-1=216-211-1distinct numbers.
Alternatively: a total of 216 distinct numbers can be represented, but we wasted exponent 255 which could represent 211 numbers and represents no number when exponent=255, in addition when exponent and significant are both 0, we only represent 1 number instead of 2, so the total distinct numbers could be represented are 216-211-1
d) How many distinct integers can be represented by the 16float standard? Note: +0 and -0 are considered to be a single integer, +1 and -1 on the other hand are two distinct integers. Justify your answer or show your calculation briefly. (2 marks)
Answer:
There is 1 integer 0 for exponent=0 (+0, -0 same integer)
For exponents=1 to 14, the real exponent after subtracting the bias 15 will be negative, so no integers could be represented.
For exponent = 15, we have the integers ± 1×20 (igificad =00) => 2 integers
For exponent = 16, we have the integers ±1.0×21 (igificad =00)
±1.1×21 (igificad =10) => 4 integers
For exponent = 17, we have the integers ±1.00×22 (igificad =000) ±1.01×22 (igificad =010)
__
9
±1.10×22 (igificad =100)
±1.11×22 (igificad =110) => 8 integers
The number of distinct integers continues to double until exponent=25, At exponent=25, we have 2*210 integers
At exponent=26, we still have 2*210 integers
:: : :
At exponent 30, we still have 2*210 integers
In total we have 1+2+4+8+16++211+(30-25) 211 = 1+2+4++211+5*211
=212-1+5*211 = 7*211-1
Student ID:
__
10
Student ID:
Question 5 Computer Arithmetic (12 marks)
a) Given the unsigned multiplicand 00101 and the multiplier 10011, compute the product with the
refined version of the multiplication hardware (5-bit) shown below. (6 marks)
__
Fill as many rows below as needed to produce the product. Eai he eai i he Aci c. Hi: Oeai ca be no operation, addition, ad shift right, hich ca he same meaning as in lecture notes.
Iteration
Multiplicand (M)
Product (P)
Action
0
00101
00000 10011
Initial State
1
00101 10011
00010 11001
1: addition
shift right
2
00111 11001
00011 11100
1: addition
Shift right
3
00011 11100
00001 11110
0: no operation
Shift right
4
00001 11110
00000 11111
0: no operation
Shift right
5
00101 11111
00010 11111
1: addition
Shift right
6
Final result is 5 x 19 = 95
11
Student ID: __ b) Given unsigned dividend 11001, and divisor 00110, compute the division result (quotient and
remainder) with the refined version of the division hardware (5-bit) shown below. (6 marks)
Fill as many rows below as eeded dce he e. Eai he eai i he Aci column. Hi: Oeai ca be subtraction, shift left, set LSB 0, shift left, set LSB 1, undo ad adjust remainder, hich ca he ae eaig a i ece e. LSB = least significant bit.
Iteration 0
1
Divisor (D)
Remainder (R) 00000 11001 00001 10010 11011 10010 00001 10010 00011 00100 11101 00100 00011 00100 00110 01000 00000 01000 00000 10001
11010 00001 00000 10001 00001 00010
Action Initial State Shift left subtraction undo
Shift left, set LSB0 subtraction undo
Shift left, set LSB0 Subtraction Shift left, set LSB1
subtraction undo
Shift left, set LSB0
2 00110 3
4
12
Student ID:
__
5
11011 00010
00001 00010
00010 00100
subtraction
Undo
Shift left, set LSB0
6
00001 00100
Adjust reminder
13
Student ID:
Question 6 Single-Cycle Datapath and Control (15 marks)
Refer to the single-cycle implementation given below and answer questions.
__
a) Suppose the processor fetches the instruction 0x08C02001 from the Instruction memory (at address 0x8FFFFFF8). Derive the value held in the Program Counter register after this instruction has finished execution. Refer to Appendix if needed.
Your answer should be in hexadecimal format and show your calculation steps. (5 marks)
PC = _______________________________ 0x83008004
Answer:
Machine code of instruction is 0000 1000 1100 0000 0010 0000 0000 0001 opcode is 000010 = 2, it is a jump instruction.
Pseudodirect addressing is used to calculate next PC value (jump/target address) Bits 31-28 of the jump/target address = first 4 bits from Program Counter
= first four bits from (8FFFFFF8 + 4) = first four bits from 8FFFFFFC
= 1000
Bits 27-0 of the jump/target address = shift the const field of the J instruction by 2 bits
= shift-left-2-bits (00 1100 0000 0010 0000 0000 0001)
= 00 1100 0000 0010 0000 0000 0001 00 Jump/target address = concatenating the above
= 1000 0011 0000 0000 1000 0000 0000 0100
14
Student ID:
b) Fill in the table below with values in various places of data path when executing the instruction. Your answer should be in hexdecimal format. If the value can not be determined, state deeied. (6 a)
A
0x8FFFFFF8
B
0x08C02001
F
Undetermined
G
0x00000000
K
Undetermined
N
Undetermined
c) Write the control signal values for executing the instruction. A d cae c iga i eeeed b a . If he iga i a d cae, i cideed cec (i.e. 0 , 1 ae bh icec). (4 a)
Question 7 Multi-Cycle Datapath and Control (16 marks)
Consider implementing an imaginary MIPS R-type instruction: or memory (orm). The instruction syntax, format and explanation are shown below:
orm $rd, $rs, $rt # Reg[$rd] = mem[Reg[$rs]] or Reg[$rt]
The instruction is similar to logical or instruction, except that it takes the first operand from the memory, whose address is stored in register $rs.
a) Make necessary changes to the multi-cycle datapath below to support orm. (4 marks) Rules/Hints:
1. No modification to the main functional units. No new control signals. You can only add wires, and/or expand existing multiplexers.
2. You may assume the ALU control module recognizes the instruction (from its func field) and supply the necessary control signal to the ALU.
3. With assumption that memory access or ALU operations take one clock cycle to finish each, the orm instruction takes 5 cycles to finish in the modified multi-cycle datatpath.
RegDst
Branch
MemRead
MemtoReg
ALUOp1
ALUOp2
MemWrite
ALUSrc
RegWrite
Jump
x
x
0
x
x
x
0
x
0
1
Field
op
rs
rt
rd
shamt
Func
Bits
31-26
25-21
20-16
15-11
10-6
5-0
15
__
b) Specify the operations done in cycle 3 to cycle 5 in the table below. (6 marks)
Student ID:
__
Cycle
Operations
Cycle 1
– Instruction fetch – PC=PC+4
Cycle 2
– Decode instruction
– Read rs and rt
– Calculate the branch target (for possible beq)
Cycle 3
Cycle 4
Cycle 5
16
Student ID:
c) Complete the finite state machine (FSM) diagram with the orm instruction. Remember to fill all the control signals that you have modified in part (a). (6 marks)
Note: To iif , i cae ead he eiig iee, d eed update the corresponding control signals in the given states.
MemRead ALUSrcA=0 IorD = 0 IRWrite ALUSrcB = 01 ALUOp = 00 PCWrite PCSrc = 00
IF
Start
ALUSrcA = 1 ALUSrcB = 00 ALUOp = 01 PCWriteCond PCSrc = 01
__
ID
Op = BEQ
Op = R-type
Op = LW/SW
ALUSrcA = 0 ALUSrcB = 11 ALUOp = 00
RegDst = 1 RegWrite MemtoReg = 0
Op = ORM
ALUSrcA = 1 ALUSrcB = 00 ALUOp = 10
ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00
MemWrite IorD = 1
Op = SW Op = LW
MemRead IorD = 1
RegDst = 0 RegWrite MemtoReg = 1
17
a)
b)
Student ID:
__
Cycle
Operations
Cycle 1
– Fetch
– PC=PC+4
Cycle 2
– Decode
– Read rs and rt
– Calculate the branch target (for possible beq)
Cycle 3
– Do a memory read: MDR = Mem[Reg[rs]] (memory read takes one cycle)
Cycle 4
– Send the content of MDR to the ALU as the second operand
– Calculate Mem[Reg[rs]] or Reg[rt] (ALU operations take one
cycle)
Cycle 5
– Write back the result (ALUOut) to the rd register
c)
18
19
Student ID:
__
Student ID:
Question 8 Pipeline and Performance (15 marks)
a) Consider a program with 2500 instructions. With the following instruction mix:
Given the cycle times and the CPI per instruction type in the table below for three processor design alternatives, calculate the average CPI in executing the program and the program execution time for each of the three alternatives (1 ns =10-9 second). Assume there is no hazard in the pipeline for the calculation. Show all your steps. (6 marks)
__
Instruction class
R-type
Load
Store
Branch
Jump
Instruction proportion
40%
20%
10%
20%
10%
Processor Designs
Cycle time
CPI per instruction type
R-type
Load
Store
Branch
Jump
Single-cycle
10ns
1
1
1
1
1
5-stage multi-cycle
2ns
4
5
4
3
3
5-stage pipelined
2ns (assume no stalls)
5
5
5
5
5
Answer:
i) Single-cycle implementation
CPI = 1
Time = 2500 * 1 * 10 ns = 25 μs
ii) 5-stage multi-cycle implementation
CPI = (0.4*4 + 0.2*5 + 0.1*4 + 0.2*3 + 0.1*3) = 3.9
Time = 2500*3.9*2 ns = 19.5 μs
iii) 5-stage pipelining implementation
CPI = (4+2500)/2500 = 1.0016
Time = 2500*1.0016*2 ns = 5.008 μs
2 marks for each alternative, 1 mark for CPI, 1 mark for execution time
20
Student ID:
b) The following sequence of instructions is executed in a basic five-stage (IF, ID, EXE, MEM, WB) pipelined processor.
Assumption:
1. No structural hazards.
2. Full set of forwarding hardware is available, from any stage to any stage (provided it
does not violate the timing consistency).
3. Write BUB if stall is needed.
Be i a eae f h fi he abe. The a idicae hee a fadig ah used. (9 marks)
Show how the instructions below would progress through pipeline. Draw forwarding path among stages if used.
1
2
3
4
5
6
7
Instruction 1
IF
ID
E
M
WB
Instruction 2
BU B
IF
ID
E
M
WB
1
2
3
4
5
6
7
8
9
10
11
12
or $8, $1, $4
IF
ID
E
M
WB
and $7, $8, $4
IF
ID
E
M
WB
lw $8, 4($7)
IF
ID
E
M
WB
add $1, $2, $8
BU B
IF
ID
E
M
WB
sw $1, 4($7)
IF
ID
E
M
WB
Proper pipeline is 5 marks, 1 mark for each instruction 4 forwarding paths, 1 mark each
21
__
Question 9 Memory and Cache (5 Marks)
During the execution of a program, the CPU generates the following list of 32-bit memory addresses to access:
0xA0000004, 0xD0000030, 0xA000004C, 0xD0000038
Assume the memory is divided into blocks of 16 bytes in size. A direct-mapped cache with four 16-byte blocks is used. The cache contains no data before the first memory access (at address 0xA0000004). Fill out the following table. The first row has been done for you. (5 marks)
Answer:
Student ID:
__
Memory (byte) address being referenced
Block address
Cache block assigned
Hit or Miss in cache
0xA0000004
0xA000000
0xA000000 mod 4 = 002
Miss
0xD0000030
0xA000004C
0xD0000038
Memory (byte) address being referenced
Block address
Cache block assigned
Hit or Miss in cache
0xA0000004
0xA000000
0xA000000 mod 4 = 002
Miss
0xD0000030
0xD000003
0xD000003 mod 4 = 112
Miss
0xA000004C
0xA000004
0xA000004 mod 4 = 002
Miss
0xD0000038
0xD000003
0xD000003 mod 4 = 112
Hit
1 marks each miss, 2 marks for hit
—— End of Exam Paper ——
22
Student ID:
Aed 1: MIPS c 1
__
23
Student ID:
Aed 2: MIPS c 2
__
24
Student ID:
——–Draft paper 1——–
__
25
Student ID:
——–Draft paper 2——–
__
26