COD Ch.4 — Performance

1abig(a) Devise the division algorithm to divide an n-bit integer by another n-bit integer. Estimate time and space complexity. [4]

Restoring division. Remainder ← Dividend (in the low half). Repeat

n+1

times:

Remainder = Remainder − Divisor
if (Remainder < 0):
    Remainder = Remainder + Divisor   # restore
    shift Quotient left, set new bit = 0
else:
    shift Quotient left, set new bit = 1
shift Divisor right by 1

In MIPS, Lo = quotient, Hi = remainder.
Time:

n+1

iterations of subtract/shift ⇒

O(n)

. Space: remainder, divisor and quotient registers ⇒

O(n)

.

Division →

1bsmall(b) Explain overflow and underflow in floating-point arithmetic. [3]

In floating point the exponent has a limited range.

Overflow — the exponent is too large to represent (magnitude bigger than the largest normalized number). Result → $\pm\infty$ .
Underflow — a non-zero result's exponent is too small (too negative) to represent, so it rounds toward 0 (or to a denormal). Precision is lost.

Overflow = exponent too big; underflow = exponent too small (result too close to 0).

1cbig(c) Calculate the representation of −6.375 in IEEE 754 single precision. [3]

Step 1 — integer & fraction to binary. $6 = 110_2$ ; $0.375 = 0.25 + 0.125 = 0.011_2$ . So $6.375 = 110.011_2$ .

Step 2 — normalize to $1.f \times 2^e$ : $110.011_2 = 1.10011_2 \times 2^{2}$ ⇒ $e = 2$ .

Step 3 — fields. Sign $S = 1$ (negative). Stored exponent $= e + 127 = 129 = 10000001_2$ . Fraction = the bits after the point, padded to 23: 10011 + 18 zeros.

−6.375 packed into 32 bits.

\mathtt{1\ 10000001\ 10011000000000000000000}

= 0xC0CC0000(check: nibbles 1100 0000 1100 1100 0000 … = C0CC0000).

IEEE 754 →

2abig(a) Define pipelining and pipeline rate. Name the MIPS-32 pipeline stages and describe each. [4]

Pipelining overlaps the execution of multiple instructions by splitting each into stages that use separate hardware, so several instructions run in different stages at once.
Pipeline rate = the rate at which instructions complete in steady state — one per clock cycle, so the rate equals the (pipelined) clock frequency

1/t_c

.

Stage	Operation
IF	Instruction Fetch — read the instruction at PC; PC ← PC + 4.
ID	Instruction Decode — decode opcode; read source registers.
EX	Execute — ALU computes result or memory address.
MEM	Memory — read/write data memory (loads/stores).
WB	Write Back — write the result into the register file.

Stages & datapath →

2bbig(b) 5-stage pipeline, each stage 2 ns except MEM = 3 ns, 2000 instructions: (i) total pipelined time (ii) speedup (iii) single-instruction latency both ways (iv) throughput both ways. [6]

\Sigma = 2+2+2+3+2 = 11\ \text{ns},\quad t_c=\max=3\ \text{ns},\quad k=5,\ n=2000

(i) Pipelined total $=(5+2000-1)\times3 = 2004\times3 = \boxed{6012\ \text{ns}}$ .

(ii) Non-pipelined $=2000\times11 = 22000$ ns ⇒ Speedup $= 22000/6012 \approx \boxed{3.66\times}$ .

(iii) Latency: non-pipelined $=11$ ns; pipelined $=5\times3 = 15$ ns. Pipelining raises latency 11 → 15 ns.

(iv) Throughput: non-pipelined $\approx 1/11\text{ns} = 90.9$ M/s; pipelined $\approx 1/3\text{ns} = 333.3$ M/s. ≈ 3.7× more.

Interactive timing calculator →

3asmall(a) Explain the principle of locality for memory access. [3]

3bbig(b) Total bits for a direct-mapped cache with 64 KB of data and 8-word (32-byte) blocks, 32-bit address? [4]

Block = 32 B =

2^5

⇒ lines =

64\text{KB}/32\text{B} = 2^{11} = 2048

. block offset = 3, byte offset = 2, index = 11, tag =

32-11-3-2 = 16

.

\text{bits/line} = 1 + 16 + (8\times32=256) = 273 \;\Rightarrow\; 2048\times273 = \boxed{559{,}104\ \text{bits}}

559,104 bits = 546 Kibits.

Total-bits calculator →

3csmall(c) A direct-mapped cache has m blocks and memory has n blocks. Find the index size. [3]

The index selects one of the

m

cache lines, so

\text{index size} = \log_2 m \ \text{bits}

(and, for completeness, tag =

\log_2 n - \log_2 m = \log_2(n/m)

bits). index = log₂ m.

Autumn 2025 Final — Solved

Q1 — Arithmetic CO3

Q2 — Pipelining CO3

Q3 — Memory & Cache CO3