Computer Engineering Department
CMPE361: Computer Organization
Final Exam (Sample)
Duration: 120 minutes
ID:
NAME:
SIGNATURE:
QUESTIONS POINTS
Q1 25/
Q2 25/
Q3 25/
Q4 25/
TOTAL 100/
Academic Honesty Statement
I do hereby attest and affirm that my anwers to the questions are my work alone and
that I did not solicit or receive assistance from any other person. I understand that during
the exam, I am not permitted to use any class notes, textbook, or external resources. I
am also aware that I am not permitted to use any electronic devices.
1
Computer Engineering Department
2
Computer Engineering Department
Q1: [25 points] Single-Cycle Processor
A. Datapath Signals [6 points]
1. Which instructions would malfunction for each of the following signal values? Why?
(a) RegWrite=0 :
(b) ALUOp1=0 :
(c) MemWrite=0:
2. Which instructions would malfunction for each of the following signal values? Why?
(a) RegWrite=1 :
(b) ALUOp1=1 :
(c) MemWrite=1:
3
Computer Engineering Department
B, Given the following single-cycle MIPS processor design and the decoder truth table,
Decoder truth table
Figure 7.11 Complete single-cycle MIPS processor
JRSig
Instruction opcode RegWrite RegDst ALUSrc Branch MemWrite MemtoReg ALUOp
R-type 000000 1 1 0 0 0 0 10
Copyright © 2013 Elsevier Inc. All rights reserved. 12
lw 100011 1 0 1 0 0 1 00
sw 101011 0 X 1 0 1 X 00
beq 000100 0 X 0 1 0 X 01
jr 001000
a. Update the figure to indicate the changes to the datapath for njr instruction (jr rs: jump register,
PC = [rs]). Hint: You need another multiplexor just before the PC block, controlled by the new
signal JRSig. [6 points]
b. Update the truth table given above for the njr instruction, using the new column (JRSig) and new
row (jr). [13 points]
4
Computer Engineering Department
Q2: [25 points] Pipelined Processor
Consider the pipelined MIPS processer with five stages (such as Fetch, Decode, Execute, Memory, and
Writeback) without a hazard unit and the assembly language program below. Assume that the processor can
execute add,addi, sub, and or, lw, sw and j instructions. At the first cycle it starts to fetch the first instruction
of the program.
addi $t0, $0, 5
addi $t1, $0, 7
addi $t2, $0, 9
addi $t0, $t1, 5
loop: add $s1, $t0, $0
addi $s2, $t0, -1
sub $s3, $t1, $t0
j loop
a) Complete the following table showing cycle wise instruction execution sequence, as done for the first
instruction. [5 points]
Cycle No.
Instruction 1 2 3 4 5 6 7 8 9
addi $t0, $0, 5 Fetch Decode Exect. Memory WriteReg
addi $t1, $0,7
addi $t2, $0, 9
addi $t0, $t1, 5
Add $s1, $t0, $0
addi $s2, $t0, -1
b) What will be the values in decimal of the registers $t0, $t1, $s1, $s2, $s3 at the end of cycle 5, 6, 7, 8, 9, in the
course of instruction execution. Use X if the value of a register in unknown. [20 points]
Cycle No.
5 6 7 8 9
$t0
$t1
$t2
$s1
5
Computer Engineering Department
Q3: [25 points] Hazzard and Performance
a) Consider the pipelined MIPS processer with five stages and a hazard unit and the four consecutive assembly
language instruction below.
add $s0, $t1, $t2
sub $s1, $t1, $t2
add $s2, $s0, $s1
sub $s2, $s2, $s0
Suppose in the current cycle the forth instruction is in Fetch stage and the value of $t1 and $t2 remains
4 and 9 respectively until the current cycle. What will be the value of datapath signals SrcAE and SrcBE
(in decimal), also the signals StallF, StallD, BranchD, ForwardAD and ForwardBD signals in the same
current and next cycles? [18 points]
SrcAE SrcBE StallF StallD ForwardAD ForwardBD
current cycle
(4th instruction is
in Fetch Stage)
next cycle
(4th instruction is
in Decode Stage)
6
Computer Engineering Department
b) Suppose a benchmark program with 120 billion instructions has 25% loads, 15% stores, 10% branches, 5%
jumps, and the remaining are R-type instructions. Also assume that 40% of loads are used by the next
instruction, 10% of branches mis-predicted, all jumps flush next instruction.
i. Compute the average number of Cycles Per Instruction (CPI). [5 points]
ii. How much time it will take to execute the program with a pipelined processor with Time for critical
path (cycle time) 450 ps? [2 points]
7
Computer Engineering Department
Q4: [25 points] Memory
Assume a sequence of memory addresses in hexadecimal were referred to by lw instructions, in a 16
word cache architecture case, using least recently used (LRU) replacement algorithm in case of
conflicts.
A. Enter the memory addresses 40 48 70 74 78 7C 80 88 94 9C 0 8 14 1C 20 into the direct mapped cache
blocks, with block size b= 1 word. Hint: In case of conflict write the memory addresses consecutively in the
cache block. For example, memory address 9C (…10011100) and 1C (…00011100)maps to cache block 0111,
written as “9C 1C”. [9 points]
(a) direct mapped cache, b = 1 word, 16 Sets
Cache Memory Addresses mapped to this
Address cache address
1111
1110
1101
1100
1011
1010
1001
1000
0111
0110
0101
0100
0011
0010
0001
0000
