Sample Final Exam
COMP2300/ENGN2219/COMP6300
(Digital Logic Fundamentals)
Q1. Draw the following schematics for an 8-input (8:1) multiplexer.
A. Gate level: as a combination of basic AND, OR, NOT gates. Use as few
gates as possible.
B. Module level: as a combination of 2-input (2:1) multiplexers. Use as few
2-input multiplexers as possible.
Q2. In one of the lectures on digital logic fundamentals, we discussed that
“general purpose” hardware circuits have some key features that distinguish
them from “special purpose” hardware circuits. Discuss briefly with examples.
(Finite State Machines)
Q3. Design an FSM with one input, A, and two outputs, X and Y. X should be
one if A has been one for at least three consecutive cycles. Y should be one if A
has been 1 for at least two cycles altogether (not necessarily consecutively).
Show your state transition diagram, encoded state transition table, next state and
output equations, and schematic.
Q4. Explain with examples the significance of sequencing overhead in
synchronous digital circuits.
(ARM Assembly)
Q5. Convert the following C code into ARM assembly code. Your code
should respect the ARM calling conventions.
Q6. It is well-known that any recursive function has a corresponding iterative
solution. Write an iterative solution for the function above C code implements.
(No marks will be deducted for syntax errors.) Explain the pros and cons of
recursion compared to iteration from a microarchitecture perspective.
C Code
int q(int n) {
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return n + q(n-2);
}
Q7. Consider the following QuAC assembly code. Assume you are
considering the Smith2 branch predictor with the initial state of the counter in
the branch history table is “Strongly Taken.” What is the prediction accuracy of
the Smith2 predictor for the branch instruction (jpz end) inside the loop.
What is the prediction accuracy if the initial state is “Strongly Not Taken?”
@ QuAC Assembly Code
@ Fib number calculator
movl r1, 0x1
movl r2, 0x0
movl r3, 0x19
loop:
cmp r3, rz
jpz end
add r4, r1, r2
mov r1, r2
mov r2, r4
movl r4, 0x1
sub r3, r3, r4
jp loop
end:
nop
(I/O)
Q8. Suppose that I/O device # 1 is the figure below is assigned the memory
address 0x10002000. Show the ARM assembly code for writing the value 20 to
I/O device # 1, and for reading the output value from I/O device # 1.
Q9. Briefly explain the characteristics of following I/O systems.
A. Memory-mapped DMA interrupt-driven I/O
B. Port-mapped programmed polling I/O
Q10. A large server is in production at a bank. We can upgrade the CPU to
make it 25% faster for $5000; or upgrade its solid-state drive for $3000 to make
the drive go 70% faster. It is observed that programs spend 80% of their time
computing (CPU is 100% utilized), and 20% of their time waiting for disk to
respond. Explain an upgrade of which component would offer a greater benefit
for a smaller expense.
(Microarchitecture)
Q11. List all the true and false (anti and output) dependences in the following
assembly code. Suppose instructions can be arbitrarily reordered in a
hypothetical machine. What kind of hazards are possible when executing the
instruction sequence below? Assume the hypothetical machine implements no
mitigating strategies we covered in lectures.
Q12. The following figure shows the execution an instruction sequence on a
CDC 6600 pipelined CPU with a scoreboard. There are several errors in the
figure. List all errors you can find.
Q13. Assume the processor in the above question has a register file with eight
registers. Now consider the corrected cycle-by-cycle diagram for the execution
of the four instructions above. Show the state of the scoreboard when i3 is in
the EX-stage.
1716151413121110987654321
WB… miss …EXD$EX@ISDIRRDEFEi1: LDR r2, [r7,#4]
WBEXISISISDIRRDEFEi2: ADD r4, r2, #1
WBEXISDIRRDEFEi3: ADD r8, r5, #2
WBEXISDIRRDEFEi4: ADD r2, r8, #3
ADD R0, R0, R4
LDR R1, [R0, #16]
ADD R1, R1, #8
STR R1, [R0, #16]
SUB R0, R1, #1
Q14. Discuss in which way the following design philosophies are similar or
different. Discuss the similarities by explaining their key features. If the design
philosophies share no similarity, discuss the differences between them.
A. RISC and VLIW
B. Hardware speculation and statically scheduled in-order superscalars
C. VLIW and hardware speculation
D. Microprogramming vs. hardwired control
Q15. Use a simple multi-cycle pipeline diagram to show the forwarding and
stalls needed to execute the following instructions on the pipelined ARM
processor. Which registers are being written, and which are being read on the
fifth cycle?
ADD R0, R4, R9
SUB R0, R0, R2
LDR R1, [R0, #80]
AND R2, R1, R0
Q16. How many cycles are required to run the following program on the
multicycle ARM processor? What is the CPI of the program? Answer the same
questions for a 5-stage ARM pipelined processor with hazard detection.
MOV R0, #0
MOV R1, #0
MOV R2, #0
LOOP
CMP R2, R0
BEQ L2
ADD R1, R1, R0
ADD R0, R0, #1
B LOOP
L2