IE4756 Computer Architecture
Tutorial 1
Tutor: Lim Wei Quan | [Link]@[Link]
1. Specify a Turing Machine (TM) that treats the input binary string as a little-endian binary integer n
and decrements n by 1 if n > 0, but leaves it unchanged if n = 0.
2. Write a RAM program that finds the maximum of all the input integers and stores it in the next
memory cell after the input.
3. Explain how to translate any PM to some other PM in which each memory node has only 3 fields.
4. Name the benefits and drawbacks of punched cards.
IE4756 Computer Architecture
Tutorial 2
Tutor: Lim Wei Quan | [Link]@[Link]
1. Design one way to encode a Turing Machine (TM) as a binary string.
2. Explain why we separate instruction and data caches.
3. Explain how branch prediction is helpful for loops.
Look up the Wikipedia article on "branch predictor". Focus on the "2-bit saturating counter".
4. Explain why the CPU and not the OS must save the PC before jumping to the interrupt handler.
5. Explain why the return-from-interrupt instruction is necessary if there are read-only CPU flags.
IE4756 Computer Architecture
Tutorial 3
Tutor: Lim Wei Quan | [Link]@[Link]
Part 1
1. Implement a 32-bit slow-adder in Logisim.
2. Implement a 32-bit fast-adder in Logisim.
3. Compare the gate-delays between the two adders.
Part 2
4. Translate the D Flip-Flop with Enable completely to transistors (i.e. implement the multiplexer).
Hint: Use transmission gates just like for the Reset.
5. Use 4 D Flip-Flops with Enable to make a 4-bit counter that increases on each clock rising edge.
6. Use 32 D Flip-Flops with Enable to make a 32-bit register PC, and combine it with a fast-adder with
constant second input 1 to get a program counter that increases on each clock rising edge.
IE4756 Computer Architecture
Tutorial 4
Tutor: Lim Wei Quan | [Link]@[Link]
Part 1
1. What do the following MIPS instructions do?
a) 0x00000000
b) 0x8c82fffc
2. Encode the following MIPS instructions (in hex):
a) sw $1,-4($4)
b) add $3,$1,$4
3. MIPS R-type instructions should have shamt = 0 except for sll, srl, and sra. How many new
instructions can we add to MIPS with opcode 000000 and 3 input registers by using shamt ≠ 0?
Part 2
4. Explain how the recursive eq/lt unit (given in the IE4756-arithmetic-no-adder circuit library) works.
Hint: To compute ( A*B < C*D ) where A, B, C, D are bit strings of equal length and * denotes concatenation,
we can compute ( A < C or ( A = C and B < D ) ).
IE4756 Computer Architecture
Tutorial 5
Tutor: Lim Wei Quan | [Link]@[Link]
Part 1
1. We wish to add branch prediction to a CPU. This would make each branch instruction 3x as fast if
the predictor is correct, but 2x as slow if the predictor is wrong. How accurate must the predictor be to
achieve a speedup of 1.25 if the original CPU spends 40% of time on branches?
2. For a magnetic hard disk that spins at 15,000 RPM with a seek time of 5 ms, how long would it
take to retrieve 100 files each of size 1 MB?
Part 2
3. Which storage media are suitable for the following use cases?
(Choose from: magnetic disk / optical disk / magnetic tape / flash memory)
a) Documents for work?
b) Server data backup?
c) Computer games?
d) Camera storage?
e) Medical scans?
IE4756 Computer Architecture
Quiz 1
Tutor: Lim Wei Quan | [Link]@[Link]
Question 1
(a) [2 marks]
Identify which logic gates are implemented by the two circuits shown (using transmission gates
instead of pull-up and pull-down networks).
(b) [4 marks]
Briefly explain the benefits and drawbacks of these implementations compared to the implementations
given in lecture.
(c) [4 marks]
Construct a circuit with 3 rising-edge-triggered flip-flops (with initial value 0) to represent a 3-bit
pattern that changes on each clock rising edge according to the following state diagram:
000 ← 001
↓ ↑
100 → 010
Label the bits X[1] to X[3], where X[1] is the leftmost bit in the pattern.
Question 2
(a) [4 marks]
Encode the following MIPS instruction to hexadecimal:
sltiu $9, $13, -7
Decode the following MIPS instruction from hexadecimal:
0x008ea823
(b) [6 marks]
Explain how to implement each of the branch instructions BEQ and BNE using the other MIPS
instructions.