Summer 2025 Final — Solved

Full marks 30. Q1 arithmetic, Q2 pipelining, Q3 cache — the standard skeleton. Try each part before revealing.

Q1 — Arithmetic CO3

1abig(a) Devise the multiplication algorithm to multiply two n-bit integers. Estimate its time and space complexity. [4]

Algorithm (sequential shift-add). Product ← 0. Repeat

n

times:

for i = 1 to n:
    if (Multiplier LSB == 1):
        Product = Product + Multiplicand
    shift Multiplicand LEFT by 1
    shift Multiplier RIGHT by 1

Multiplying an

n

-bit by an

m

-bit number gives an

(n+m)

-bit product.
Time complexity:

n

iterations, each an add + shifts ⇒

O(n)

steps. Space complexity: registers for multiplicand, multiplier and a

2n

-bit product ⇒

O(n)

Full hardware & a worked trace: Multiplication →

1bsmall(b) Explain overflow and how it can be detected during addition and subtraction. [3]

Overflow = the true result doesn't fit in

n

bits. Detect it by the sign of the result: it's wrong when

Op	A	B	Overflow if result
A+B	≥0	≥0	<0
A+B	<0	<0	≥0
A−B	≥0	<0	<0
A−B	<0	≥0	≥0

Addition overflows only when operands share a sign; subtraction only when they differ.

1csmall(c) Diagram the IEEE single- and double-precision floating-point formats. [3]

Single precision (32 bits), bias 127:

Double precision (64 bits), bias 1023:

\text{value} = (-1)^S \times (1.\text{fraction}) \times 2^{(\text{Exp}-\text{bias})}

Q2 — Pipelining CO3

2abig(a) Explain and exemplify a structural hazard, then discuss its solution. [4]

2bbig(b) 5-stage pipeline (IF,ID,EX,MEM,WB); each stage 3 ns except MEM = 4 ns; 1000 instructions. (i) speedup vs single-cycle (ii) throughput increase (iii) latency decrease. [6]

\Sigma = 3+3+3+4+3 = 16\ \text{ns},\quad t_c = \max = 4\ \text{ns},\quad k=5,\ n=1000

(i) Speedup. Non-pipelined $= 1000\times16 = 16000$ ns; pipelined $= (5+999)\times4 = 4016$ ns.

\text{Speedup} = 16000/4016 \approx \boxed{3.98\times}

(ii) Throughput. Steady-state throughput = one instruction per clock: non-pipelined $1/16$ ns⁻¹ → pipelined $1/4$ ns⁻¹ = 4× the throughput (overall, using totals, ≈ 3.98×).

(iii) Latency. Single-instruction latency = non-pipelined 16 ns vs pipelined $5\times4 = 20$ ns. There is no decrease — latency actually rises by 4 ns. Pipelining trades slightly worse latency for much higher throughput.

Q3 — Memory & Cache CO3

3abig(a) Diagram a direct-mapped cache with capacity 4096 bytes and block size 16 bytes, 32-bit address. [4]

Block = 16 B = 4 words ⇒ offset =

\log_2 16 = 4

bits (2 byte + 2 block-word). Lines =

4096/16 = 256

⇒ index =

\log_2 256 = 8

bits. Tag =

32 - 8 - 4 = 20

bits.

Address split for a 4 KB, 16-byte-block direct-mapped cache.

256 lines, each = valid + 20-bit tag + 128-bit data. Index picks the line; tag confirms the block.

3bsmall(b) How many total bits are required for the cache in Q3(a)? [3]

Data per line = 4 words × 32 = 128 bits. Per line = valid 1 + tag 20 + data 128 = 149.

\text{Total} = 256 \times 149 = \boxed{38{,}144\ \text{bits}} \;=\; 37.25\ \text{Kibits}

3csmall(c) A cache has 2^n entries. How many degrees of associativity are possible? Which n-values give direct-mapped or fully associative? [3]

Possible associativities are

1, 2, 4, \ldots, 2^n

-way ⇒

n+1

configurations.
The extremes are configurations, not n-values: 1-way = direct-mapped (each set = 1 line); $2^n$ -way = fully associative (one set holds all lines). Any n ≥ 0 supports both extremes; only n = 0 (a single-line cache) makes direct-mapped and fully associative coincide.

Associativity →