Sample 1 – Final Exam
Reference 1: MIPS instruction reference
1 / 12
1. Short answer questions (choose any 5 questions from the following 7 questions; 4 points each,
20 points in total)
1) What is the difference between Princeton architecture (also called von Neumann
architecture) and Harvard architecture? These two architectures can support general-purpose
algorithms and are equivalent to Turing machines for the computing tasks that can be
completed. What is the name of this property?
2) Assume that the 32-bit integer variable a is stored in the register $s0, and the first address of
the 32-bit integer array b is stored in the register $t0. Please convert the C language code
"a=b[5];" into a MIPS assembly instruction. Which addressing modes are used in this
instruction (choose from the following options: i. Register addressing; ii. Immediate
addressing; iii. PC-relative addressing; iv. Base-offset addressing; v. Pseudo-direct
addressing)? In the procedure call of the MIPS program, if the register usage is in line with
the MIPS standards, should the register $s0 be maintained by the calling process or the called
process? What about the register $t0?
3) What are the control hazards of the pipeline? In the 5-stage MIPS pipelined processor
learned in class, if the branch is decided in the EX stage, is it possible to adjust the
forwarding method so that the beq instruction does not need to be stalled? If possible,
please briefly describe the forwarding method; if not possible, write a technique that can
further use the stalled cycle.
4) The execution time of a program satisfies the equation: execution time = number of
instructions × _______ × _______ (please fill in the blanks and write on the answer sheet).
In a pipelined processor, the execution time of a program can be further reduced through
instruction-level parallelism. Among instruction-level parallel technologies, which parts on
the right side of the equation do the superpipelining and the multiple-issue technology
mainly affect, respectively? Write down the corresponding reasons.
5) In general, which of the contemporary SRAM and DRAM has a larger capacity, and which
one has a faster read and write speed? Where are they located in the memory hierarchy
shown in the figure below (answer ①, ②, or ③)? What is the fundamental principle of
hierarchical memory design?
2 / 12
6) What are the cache mapping methods (write three types)? What are the three types of
cache misses? If the cache capacity and cache line size keep unchanged and the associativity
of the cache is increased, how will these three types of cache misses change (decrease,
increase, or irrelevant)?
7) What are the advantages of the bus structure over the scattered connections of the computer
components? What are the typical peripherals (write at least two)? The communication
methods between peripherals and CPU include polling and ______. (Please fill in the blank
and write on the answer sheet)
3 / 12
2. Analysis and calculation
1) (Memory, 15 points) The following memory system is used for a 32-bit processor:
L1 Main
CPU
Cache Memory
i. Assume that the L1 cache is a 4-way set associative cache. The cache line size is 4 words,
and the tag for a cache line is 24 bits. What is the maximum capacity of the cache in KB?
ii. Assume that the miss rate and the access latency of the L1 cache are 10% and 1ns,
respectively, and the access latency of the main memory is 200ns. To reduce the average
memory access time (AMAT) by 90%, an L2 cache with 5ns access latency is inserted
between the L1 cache and Main Memory. 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.)
iii. For the memory system in question i, assume that the L1 cache does not initially load any
contents from the main memory. Now loop to read the following data in the main memory:
Addr 0：0x302E0A00
Addr 1：0x302E0A04
Addr 2：0x01C24B00
Addr 3：0x2A623D03
Addr 4：0x713CD40A
Addr 5：0x5D41E600
The first-in first-out (FIFO) replacement strategy is adopted. Which addresses do cache
misses occur when accessing? Give the type of these misses.
4 / 12
2) (MIPS assembler, 15 points) Here is a MIPS assembler section and the corresponding C
program:
Address Assembly code Note Instruction name
0x00400000 sll $s2, $a0, 2 I1
0x00400004 add $s2, $a1, $s2 I2
0x00400008 addi $s1, $a1, 8 I3
0x0040000c add $s0, $a1, $zero I4
0x00400010 sll $s5, $a0, 2 I5
0x00400014 add $s5, $a2, $s5 I6
0x00400018 addi $s4, $a2, 8 I7
0x0040001c add $s3, $a2, $zero I8
0x00400020 loop: slt $t0, $s2, $s0 #while I9
0x00400024 bne $t0, $zero, exit I10
0x00400028 slt $t0, $s0, $s1 #if I11
0x0040002c bne $t0, $zero, else I12
0x00400030 lw $t1, -4($s0) I13
0x00400034 lw $t2, -8($s0) I14
0x00400038 add $t2, $t2, $t1 I15
0x0040003c sw $t2, 0($s0) I16
0x00400040 lw $t3, -4($s3) I17
0x00400044 I18
0x00400048 sw $t2, 0($s3) I19
0x0040004c j endif I20
0x00400050 else: addi $t0, $zero, 5 # else I21
0x00400054 sw $t0, 0($s0) I22
0x00400058 addi $t3, $zero, 2 I23
0x0040005c sw $t3, 0($s3) I24
0x00400060 endif: addi $s0, $s0, 4 # A = A + 4 I25
0x00400064 addi $s3, $s3, 4 # B = B + 4 I26
0x00400068 j loop I27
0x0040006c exit: addi $s3, $s3, -4 while end I28
5 / 12
0x00400070 lw $v0, 0($s3) Return value I29
Among them, $a0 stores n, $a1 stores the first address of array A, $a2 stores the first address of array
B, and set n=5. The C language code corresponding to this assembly code is as follows:
int i = 0;
while(i<=n)
{
if(i>=2)
A[i] = A[i-1] + A[i - 2];
B[i] = B[i-1] + A[i];
else
A[i] = 5;
B[i] = 2;
i = i + 1;
}
return B[n];
Please answer the following questions:
i. Please write the assembly instruction I18 on the answer sheet according to the C language
code. What is its instruction type (R, I, J)?
ii. Write down the value of $v0 after the execution of the program, expressed in decimal.
iii. Write down the addressing mode of the instruction I19, and write down the detailed [15:0]
bits of I19, expressed in hexadecimal.
iv. How long does it take for this assembly code to execute on a 1GHz single-cycle processor?
6 / 12
3) (Single-cycle processor, 15 points) Consider the following MIPS single-cycle processor. It
can execute a subset of MIPS ISA including 9 instructions (add, sub, addi, and, or, beq, lw,
sw, j).
i. Please list the detailed values of the following control signals when executing the
“beq” and “lw” instructions: PCSrc1, PCSrc2, ExtOp, RegWr, RegDst, ALUSrc,
MemWr, MemtoReg. The value of each control signal can be either 0, 1, or x (don’t
care). For the don’t care signal, x must be written.
ii. Currently, the data in RF are as follows (in decimal): $0=0, $1=10, $2=20, ......,
$31=310. The value of PC is 0x0000008C. The data value at the address 0x0000008C
in the instruction memory is 101011 10110 01011 1111 1111 1110 0000. The data in
the data memory are all zero.
a) Please give the function of this instruction (first write in the form of add $rd, $rs, $rt
or lw $rt, imm($rs), then change the general notations of the registers and the
immediate to a specific digital number, and finally explain the function in words)
b) If Instruction[31:26] is incorrectly read and sent to Control Unit as all zero, what is
the result of the ALU output in decimal when executing the incorrect instruction?
c) When finishing the execution of the incorrect instruction in the previous question,
which registers and which address in the memory have their value changed? Write
down the changed values
7 / 12
iii. 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
100ps 40ps 20ps 10ps 40ps 60ps 20ps 10ps 10ps 10ps
a) Please calculate the delay when executing “add” and “beq” instruction.
b) Please calculate the maximum clock frequency of this single-cycle processor with
correct execution.
iv. The processor needs to execute the tasks whose instruction proportion is as follows.
Someone found that 50% of “lw” instructions have an immediate of 0, i.e., lw $rt
0($rs), and 50% of “sw” instructions have an immediate of 0, i.e., sw $rt 0($rs). Thus,
an optimization method is proposed: the “lw” and “sw” instruction is no longer
supported, and “lr” and “sr” instruction is added with function R[rt]=MEM[R[rs]] and
MEM[R[rs]]=R[rt] respectively. For the rest 50% “lw” and “sw” instructions which
need the immediate offset, they can be split into an “addi” and a “lr” (“sr”).
add addi sub and or lw sw beq j
20% 5% 10% 5% 5% 30% 10% 10% 5%
a) “lr” and “sr” instructions do not require ALU operation. Therefore, modify the
“assign Addr = Result” logic in the origin implementation to “assign ___ = ___”.
Please fill in the blank and write on the answer sheet.
b) With the modification, does the total execution time on the tasks increase or decrease
compared with the original processor? How much does it increase or decrease?
8 / 12
4) (Pipelined processor, 15 points) In a MIPS pipelined processor, assume that the ALU
operation is completed in two cycles. Thus, it is a 6-stage pipelined processor containing
IF, ID, EX1, EX2, MEM, and WB stages. ALU obtains two operands in the EX1 stage, and
writes the result to the EX2/MEM register at the end of the EX2 stage. For the execution of
the following instruction sequence on this processor:
I1: add $t0, $t0, $t1
I2: add $t2, $t2, $t3
I3: add $t5, $t1, $t3
I4: lw $t4, 0($t0)
I5: addi $t3, $t4, 1
I6: add $t1, $t2, $t3
The processor supports “write first, then read” in hardware, i.e., the data written to the RF
can be read in the same cycle. Please answer the following questions.
i. In the third clock cycle CC3, which registers in RF is read and written?
ii. Assume that the processor does not support the forwarding and hardware stalling
functions. To ensure the correct execution, insert minimum nop instructions in the
instruction sequence, and write down the new sequence (the origin instructions can be
replaced by the index I1-I6). Calculate the clock cycles to execute the above
instructions.
iii. Assume that the processor supports the data forwarding function from EX2/MEM,
MEM/WB and MDR to ALU inputs (i.e., EX1 inputs), but does not support the
hardware stalling function. To ensure the correct execution, insert minimum nop
9 / 12
instructions in the instruction sequence, and write down the new sequence. (the origin
instructions can be replaced by the index I1-I6). Calculate the clock cycles for the
execution of the above instructions.
iv. Based on question iii, if there are errors in the forwarding from MEM/WB to the ALU
inputs, which instructions are affected in the execution of the above instructions?
10 / 12
3. Design (20 points)
The following figure is the diagram of a 5-stage MIPS pipelined processor, which supports: (1)
hazard detection and data forwarding; (2) interrupt and exception handling based on the cause register.
The hazard unit is not presented in the figure.
Comp unit at the ID stage compares whether the two inputs are equal. If equal, the Comp unit outputs
‘1’; otherwise, it outputs ‘0’. Using this unit, a custom R-type instruction “bezr” with the format of
bezr $rs, $rt is implemented. The function of “bezr” is to compare whether the rs register is equal to
0. If equal, the PC register jumps to the target address in the rt register; otherwise, it not jump.
For simplicity, the implementation of other branch and jump instructions including “beq”, “j’, “jal”
is not considered in this question. The write operation of the cause register in exception handling is
not considered.
Add
Instruction Memory Read Address
Please answer the following questions.
i. In the design of the pipelined processor, which method is adopted to handle the data hazards
if the data forwarding is not supported?
ii. Please describe the logic for the output signal B1 of the Forwarding Unit.B using if/else
statements with the input, output and control signals in the figure.
iii. Forwarding Unit.A is utilized for the forwarding of “bezr”. Which forwarding paths should
be added to implement “bezr”? Please describe the logic for the output signal A1 of the
11 / 12
CP
？
Branch
ID/EX
EX/MEM
Con-
trol
IF/ID
RegWr Comp Exception ALU.excep MEM/WB
4 Bad Unit
A1 01 0 Op
Read B1
Addr1 DR ate aa d 1 00 Data MemtoReg R Ade da rd 2 Regs 0 11 0 B2 ALU AM dde rm eso sry Read 1 Write Addr Read 1 Data
Data 2 00 Write Data 0
Write Data 01
10 0 ALUOp
Imm RegDst MemRead MemWr
16 Extend 32 0
1
EX/MEM.RegWrAddr
ID/EX.Rt EX/MEM.RegWr
IF/ID.Rs ID/EX.Rs For Uw na ir t.d Bing MEM/WB.RegWrAddr
MEM/WB.RegWr
Forwarding
Unit.A EX/MEM.RegWrAddr B1B2
EX/MEM.RegWr
A1
Forwarding Unit.A using if/else statements with the input, output and control signals in the
figure.
iv. The Exception Unit in the figure generates the control signals for exception handling. In this
design, the cause register is utilized for exception handling. When the exception signals
(BadOp and ALU.exep) are raised, the CPU should jump to the entry address of the
exception handler program, i.e., 0x80000180. Note that the normal program execution will
not be continued. When the exception program is completed, there is no need to resume the
original program execution. Please describe which control signals are required to be
generated, and analyze their functions.
v. An additional interrupt signal IRQ is provided to the Exception Unit, such that the hardware
interrupts can be handled. Note that a jump instruction is executed after the interrupt handler
program, i.e., the address in 31st register is read and the processor jumps to the interrupted
address for normal program execution. Assume that the instructions already in the pipeline
still need to be executed. Please describe which control signals are required to be generated,
which datapaths are required to be added, and analyze their functions.
12 / 12
