Sample 2 – Final Exam
Reference 1：MIPS instruction reference
1 / 17
1. Short answer questions (choose any 5 questions from the following 7 questions; 4
points each, 20 points in total)
1) In an assembly program, the next instruction to be executed is beq $s0, $s1, -10.
The address of the instruction is 0x1000_0000, and the value stored in register
$s0 in the register file is 0 now. If the value stored in register $s1 is 0, what is the
value of the PC register after the instruction is executed? If the value stored in
register $s1 is 1, what is the value of the PC register after the instruction is
executed?
2) What are CISC and RISC? Please briefly describe the most significant
differences between them. Between CISC and RISC, which does X86 belong to?
Which does ARM belong to?
3) Why can superscalar and very long instruction word (VLIW) potentially improve
the CPU performance? What are the core differences between their
implementations?
4) A 5-stage pipelined MIPS CPU with a data forwarding unit (for handling data
dependencies, load-use hazards, and load-store hazards) has a clock cycle of T.
How long will the following instructions take at least to execute? Using this
example, please describe the reason why the actual throughput of a pipelined
CPU is less than 1 (list at least two reasons).
lw $s2, 0($s1)
addi $s2, $s2, 1
add $s0, $s1, $s2
lw $s3, 0($s1)
sw $s3, 4($s1)
5) Why could a memory hierarchy structure achieve large capacity, high speed, and
low cost at the same time? Please list all three types of cache misses.
6) What are the differences between DRAM and SRAM in terms of cell structure,
storage density, and CPU access latency? Where are they in the memory
hierarchy of a general-purpose computer respectively?
7) What is the function of a bus in a computer system? What are the advantages of
using a bus over using point-to-point connections between the CPU and each of
the peripherals?
2 / 17
2. Analysis and calculation
1) (MIPS assembler，15 points) Here is a MIPS assembler section and the
corresponding C program:
Address Code Annotation Inst. Number
0x00400000 sll $s0 $a0 2 $s0=4n I1
(n is the parameter)
0x00400004 addi $t0 $zero 0 int i = 0 I2
0x00400008 loop: bne $t0 $zero else #if I3
0x0040000c sw $zero 0($a1) I4
0x00400010 lw $s3 0($a3) I5
0x00400014 sw $s3 0($a2) I6
0x00400018 j endif I7
0x0040001c else: add $t2 $t0 $a2 I8
0x00400020 lw $s2 -4($t2) I9
0x00400024 Question i I10
0x00400028 add $t3 $t3 $a3 I11
0x0040002c lw $s3 -4($t3) I12
0x00400030 sub $s1 $s3 $s2 I13
0x00400034 add $t1 $t0 $a1 I14
0x00400038 sw $s1 0($t1) I15
0x0040003c lw $s3 0($t3) I16
0x00400040 sub $s2 $s3 $s1 I17
0x00400044 sw $s2 0($t2) I18
0x00400048 endif: addi $t0 $t0 4 I19
0x0040004c slt $t4 $t0 $s0 I20
0x00400050 bne $t4 $zero loop #while I21
0x00400054 addi $v0 $s1 0 I22
0x00400058 addi $v1 $s2 0 I23
$a0 stores n; $a1 stores the address of array A; $a2 stores the address
of array B; $a3 stores the address of array C. Assume that n=4, array C[10]
= {1, -1, 1, -1, 1, -1, 1, -1, 1, -1}.
int i = 0;
do {
if(i == 0) {
A[0] = 0;
B[0] = C[0];
}
else {
A[i] = C[(i << 1) – 1] – B[i – 1];
B[i] = C[i << 1] – A[i];
}
i = i + 1;
}while(i < n);
i. (4 points) Please write the assemble instruction I10 according to the C
3 / 17
language code (please write it on the answer sheet). What is its instruction
format type (R-type instruction, type I instruction, or J-type instruction)?
ii. (4 points) Please figure out the addressing mode of instruction I21, and the
value of the [15:0] bit field of the instruction in hexadecimal (according to
instruction definition in Reference 1).
iii. (4 points) What are the values of registers $v0 and $v1 after the program
execution ends (in decimal)?
iv. (3 points) How long does it take to execute the entire program on a 1GHz
single-cycle processor? Please give reasons.
2) (Memory, 15 points) For a 32-bit processor, the following memory system is
used:
L1 Main
CPU
cache Memory
i. (5 points) Assume that the size of the L1 cache is 128KB and the size of a
cache line is 32B, where 1B = 8bits, 1KB = 1024B. For such a 4-way set
associate cache, how many bits are required at least for the tag of the L1
cache?
ii. (5 points) Assume that the hit rate and the access latency of the L1 cache are
90% and 2ns, respectively, and the access latency of the main memory is
300ns. What is the average access latency of this memory system?
iii. (5 points) In the following figure, to further reduce the access latency, based
on ii., an L2 cache with 6ns access latency is inserted between L1 cache and
Main Memory. If we expect a 90% reduction of the average access time
compared with question ii., what is the minimum L2 cache hit rate?
(NOTICE: The L2 cache hit rate is defined under the condition that misses
occur at the L1 cache.)
L1 L2 Main
CPU
cache cache Memory
4 / 17
3) (Single-cycle processor, 15 points) Consider the following MIPS single-cycle
processor. It can execute a subset of MIPS ISA including 8 instructions (add, sub,
and, or, beq, lw, sw, j). Please refer to Supplementary Figure 1 on Page 13 for
a larger view of the same figure.
i. (2 points) Please list the detailed values of the following control signals
when executing “add” and “lw” instructions: PCSrc1, PCSrc2, ExtOp,
RegWr, RegDst, ALUSrc, MemWr, and MemtoReg. The value of each
control signal can be either 0, 1, or x (don’t care).
ii. (6 points) Currently, the data in RF are as follows (in decimal): $0=0,
$1=101, $2=102, ......, $31=131. The value of PC is 0x00000088. The data
at address 0x00000088 in the instruction memory are 000100 01011 10110
1111 1111 1100 1101. The data in the data memory are all zero.
a) (2 points) Please give the assembly notation of the current instruction
(e.g., add $rd, $rs, $rt), and replace the general notations of registers and
immediate (e.g., $rd, $rs, $rt, Imm) with a specific one (e.g., add $1, $2,
$3). Please analyze the detailed function of this instruction.
b) (2 points) If Instruction[31:26] is incorrectly read as 100011, what is the
Result of ALU output in the above figure when executing the incorrect
instruction? Please give your answer in decimal.
c) (2 points) When finishing the execution of the incorrect instruction in
5 / 17
the previous question, which registers and which address in the memory
have their value changed? Please give the values after the change.
iii. (7 points) Assume that the delay of each hardware unit is as follows, and
the delay not listed in the table can be ignored:
Memory Setup time Immediate Control Clk-to-Q of Setup time of All MUX in
RF read Adder ALU
read/write of RF extension unit PC register PC register the figure
120ps 40ps 20ps 10ps 40ps 60ps 20ps 10ps 10ps 10ps
a) (3 points) Please calculate the length of the critical path when executing
“sub”, “beq”, and “sw” instruction in this single-cycle processor.
b) (2 points) Please calculate the maximum clock frequency of this single-
cycle processor while ensuring the correct execution.
c) (2 points) Now use an optimization method for this single-cycle processor,
which can skip ALU operation when executing “sw” and “lw” instruction,
and send the two inputs for original ALU operation directly to the
memory. The address for memory access is calculated inside the memory
without affecting the memory access delay (120 ps). Meanwhile, the
execution of the other instructions is not changed. For an ISA with
instruction proportion as follows, please calculate the speed-up ratio after
using this optimization.
Instruction proportion: add 30%, sub 20%, beq 10%, lw 20%, sw 10%,
j 10%
4) (Multi-cycle processor, 15 points) Below it shows a multi-cycle MIPS processor,
which is able to execute 9 instructions (add, sub, and, or, slt, beq, lw, sw, j) of the
MIPS instruction set. Please refer to Supplementary Figure 2 on page 14 for a
larger view of the same figure.
6 / 17
i. (5 points) Please analyze the executing process of R-type instructions, fill
in the blank (i.e. the underline part) of the table. Note: Please write the
answer and corresponding blank number on the answer sheet.
Step R-type instructions Control signals
Instruction fetch IR <= (1) ALUSrcA = (5)
(IF) PC <= PC + 4 ALUSrcB = (6)
Instruction decode A <= Reg[IR[25:21]]
\
& RF read (ID) B <= (2)
ALU operation ALUSrcA = (7)
ALUOut <= A op B
(EX) ALUSrcB = (8)
(9) = 1
Write back to RF
(3) <= (4) (10) = 1
(WB)
RegWrite = 1
ii. (4 points) Consider only the six steps and corresponding delays during MIPS
instruction execution shown in the following table. Also, the first two states
of all instructions are IF and ID. Please draw the state-transition diagrams
of five instructions (R-type, lw, sw, beq, j), where only the step type (e.g., IF)
is needed in each state. What is the shortest clock cycle of the multi-cycle
7 / 17
processor? What are the delays of the five instructions (R-type, lw, sw, beq,
j) for a single execution?
Instruction ALU operation & Write Jump
Instructio Memory
decode & branch instruction back instruction
Step n fetch access
RF read completion to RF completion
(IF) (MEM)
(ID) (EX) (WB) (J)
Delay
250 100 120 250 40 20
(ps)
iii. (6 points) Consider only the following testing instruction set, which shows
the proportion of different types of instructions. Given the following two
multi-cycle processors, please calculate their CPI and the average execution
time per instruction.
Multi-cycle processor 1: EX state and MEM state are merged.
Multi-cycle processor 2: EX state and WB state are merged.
(Please pay attention to the change of clock cycle.)
Instruction type R-type lw sw beq j
Proportion 40% 20% 10% 25% 5%
8 / 17
1. Design (20 points+8 points for bonus)
The following MIPS assemble program is to find the maximum value in a linked list.
When the program starts running, the address of the linked list head is stored in $a0. The
final result is stored in $v0.
I1: add $t0, $a0, $0 # $t0 is initialized to the linked list head
I2: add $t1, $0, $0 # $t1 is the register to store the maximum value
I3: beq $t0, $0, I9 # Judge if it is the end of the linked list
I4: lw $t2, 0($t0) # Read the node data to $t2
I5: bgt $t1, $t2, I7 # If the value of $t1 is larger than that of $t2, no update
I6: add $t1, $t2, $0 # The value of $t1 is updated to the value of $t2
I7: lw $t0, 4($t0) # Read the address of the next node
I8: j I3 # Jump to beq
I9: add $v0, $t1, $0 # Return the result
The format for the linked list node is:
data (the data of the current node) next (the address of the next node)
4 bytes 4 bytes
The linked list stored in the memory is as follows:
Assume that the above instruction sequence is executed on the following five-stage
MIPS processor including IF, ID, EX, MEM and WB. From the following figure, it is
observed that the judgement of the branch instructions (beq, bgt) and the
corresponding PC update are executed in the ID stage in advance (pay attention to
this!!!). No branch prediction or delay slot technologies are supported here. In this
processor, the register file supports write-before-read operations (i.e., the written data can
be read in the same cycle). Please answer the following questions. You may refer to the
Supplementary Figure 3 on Page 15 for a larger view of the same figure.
9 / 17
1. (3 points) Please analyze the difference of impact on the pipeline stall by the
branch instruction judgment and PC update: (1) executed in the ID stage, and (2)
executed in the EX stage.
2. (5 points) During the 4th clock cycle when the instruction starts running:
Time (clock cycle)
Instruction
sequence
i. (1 point) In this clock cycle, which hazard between which two
instructions does Forwarding Unit A solve?
ii. (2 points) According to the input signal of Forwarding Unit A in the
figure of the pipelined processor structure, write down the generation
logic for the control signal forwardA1 of MUX A1.
Reference format: if (…) {forwardA1 = …}
Note: When the control signals of A1 and A2 are 0, the MUX outputs are
the input data at the left input terminals; when the control signal is 1,
the outputs are the input data at the right input terminals.
iii. (2 points) In this clock cycle, what are the control signals of MUX A1
10 / 17
and MUX A2 controlled by Forwarding Unit A?
Note: When the control signals of A1 and A2 are 0, the MUX outputs are
the input data at the left input terminals; when the control signal is 1,
the outputs are the input data at the right input terminals.
3. (6 points) In order to ensure the correct execution of the MIPS assemble program
for finding the maximum value of the linked list on the pipelined processor, a
hazard detection unit is required to stall the pipeline at the place where a data
hazard or control hazard is detected.
i. (2 points) Please analyze whether the stall is required between the
instruction I4 and the instruction I5 or not. If yes, please analyze how
many clock cycles are required to be stalled. If no, give the reason.
ii. (4 points) Please indicate where and how many cycles are required to be
stalled when executing the assemble program that finds the maximum
node value of the linked list, and calculate the clock cycle number
required to execute the assemble program. Note that the warm-up clock
cycles of the pipeline should be considered.
4. (6 points) Xiaoming tries to improve the performance of the pipelined processor.
The adopted method is the static branch prediction. Specifically, all branch
instructions are predicted not to branch. After the correct branch result is obtained
in the ID stage, if a branch is required, the wrong instruction should be flushed
and the correct target address is written into the PC.
i. (4 points) With this static branch prediction, please indicate where and
how many cycles are required to be stalled when executing the assemble
program that finds the maximum value of the linked list, and calculate
the clock cycle number required to execute the assemble program. Note
that the warm-up clock cycles of the pipeline should be considered.
ii. (2 points) Assume that, during this static branch prediction, the flush
signal does not work correctly. As a result, the wrong instructions are not
flushed when the prediction is wrong, so the wrong instructions are
executed. Please analyze the changes of $t1 during execution.
Hint: you may use this reference format: In the Xth clock cycle, the value
stored in $t1 is updated to Y.
11 / 17
5. (Bonus: 8 points) Bob wants to make some modification to the original pipelined
processor (but without static branch prediction) to support a customized
instruction [addjump $rd, $rs, $rt] . “addjump” is an R-type instruction that
computes $rs + $rd, writes this result to $rd, and then jumps to the address equal
to this result. Compared with the “add” instruction, the “addjump” additionally
takes the result as the next PC for jump address, which is equivalent to the
integration of “$rd=$rs+$rt” and “PC=$rs+$rt”.
To support such an “addjump” instruction in the pipelined processor, Bob adds
an extra data path to the EX stage. The ALU result is routed to an extra MUX
before PC. This MUX is controlled by the control signal Is_addj, as shown in the
top left corner in the figure below. You may refer to the Supplementary Figure
4 on Page 16 for a larger view of the same figure.
i. (3 points) Please write down the correct values of the following control
signals generated by the “Control” unit at ID stage: Is_addj, Jump,
Branch, RegWr, MemRead, MemWr.
ii. (5 points) Please calculate how many cycles do the following
instructions need to be executed on the modified pipelined processor.
Please also show the value of the register $v0 after the program
execution ends. Note that the warm-up clock cycles of the pipeline
should be considered. The detailed analysis is required rather than just
12 / 17
give simple numbers as answers.
0x00 add $t0, $0, $0
0x04 addi $t1, $0, 4
0x08 addi $t0, $t0, 4
0x0C addjump $t1, $t0, $t1
0x10 add $v0, $t0, $t1
13 / 17
Supplementary Figure 1: the single-cycle processor part in Analysis and calculation
14 / 17
Supplementary Figure 2: the multi-cycle processor part in Analysis and calculation
15 / 17
Supplementary Figure 3: the pipelined processor in Design (question 1-4)
16 / 17
Supplementary Figure 4: the pipelined processor in Design (question 5)
17 / 17
