COD Ch.4 — Performance

1aIAS: read a value from address X and write double the value back to X. (Hint: LSH.)

LOAD M(X)      ; AC = M(X)
LSH            ; AC = AC × 2   (shift left one bit)
STOR M(X)      ; M(X) = 2 × M(X)

LSH doubles the accumulator.

1bbigIf IAS memory is increased by 2ⁿ times, what is the new address size? Max n for which instruction size is unchanged?

\begin{aligned} \text{current rows} &= 2^{12} \;\Rightarrow\; \text{address} = 12 \text{ bits} \\ \text{new rows} &= 2^{12} \times 2^{n} = 2^{12+n} \;\Rightarrow\; \text{new address} = (12 + n) \text{ bits} \end{aligned}

An IAS instruction is 20 bits = 8-bit opcode + 12-bit address, with no spare bits. The format stays the same only while the address still fits in 12 bits: $8 + (12 + n) \le 20$ ⇒ n ≤ 0, so max n = 0. Any real increase (n ≥ 1) forces a wider address field and changes the instruction size.

1cExplain how abstraction helps programmers cope with complexity (with a diagram).

2abigCPI: A/B/C/D = 1/2/3/4. Seq1 = 4/3/2/1, Seq2 = 3/1/1/3. Which runs more instructions? Which is faster? CPI of each? Verify.

\begin{aligned} \text{IC}_1 &= 4 + 3 + 2 + 1 = 10 &\qquad \text{IC}_2 &= 3 + 1 + 1 + 3 = 8 \\ \text{Cycles}_1 &= 4 \cdot 1 + 3 \cdot 2 + 2 \cdot 3 + 1 \cdot 4 = 20 &\qquad \text{Cycles}_2 &= 3 \cdot 1 + 1 \cdot 2 + 1 \cdot 3 + 3 \cdot 4 = 20 \\ \text{CPI}_1 &= \tfrac{20}{10} = 2.0 &\qquad \text{CPI}_2 &= \tfrac{20}{8} = 2.5 \end{aligned}

Seq1 executes more instructions (10 vs 8). Same clock ⇒ speed depends on total cycles, and both are 20 cycles → equally fast. Verify: $\text{IC} \times \text{CPI} = \text{cycles} \;\Rightarrow\; 10 \times 2.0 = 20$ and $8 \times 2.5 = 20$ ✓.

2bbigFP = 40% of time, sped up by factor n, overall speedup = 1.66. Find n.

\begin{aligned} \text{Amdahl: Speedup} &= \frac{1}{(1 - F) + \frac{F}{n}}, \quad F = 0.40 \\ 1.66 &= \frac{1}{0.60 + \frac{0.40}{n}} \\ 0.60 + \frac{0.40}{n} &= \frac{1}{1.66} = 0.60241 \\ \frac{0.40}{n} = 0.00241 \;&\Rightarrow\; n = \frac{0.40}{0.00241} \approx 166 \end{aligned}

n ≈ 166. (Sanity: max possible speedup = $\frac{1}{1 - 0.4} = 1.667$ , so reaching 1.66 needs a very large n — hence ~166.)

2cProve that as Speedup_enhanced → ∞, overall speedup is bounded by 1/(1−Fraction_enhanced). Illustrate graphically.

\begin{aligned} \text{Speedup}_{\text{overall}} &= \frac{1}{(1 - F) + \frac{F}{S_{\text{enh}}}} \\ \text{As } S_{\text{enh}} \to \infty, \quad \frac{F}{S_{\text{enh}}} &\to 0 \\ \Rightarrow\; \text{Speedup}_{\text{overall}} &\to \frac{1}{1 - F} \quad \text{(the upper bound)} \end{aligned}

Graph: speedup rises with $S_{\text{enh}}$ but flattens to a horizontal asymptote at $\frac{1}{1 - F}$ — a law of diminishing returns. You can never do better than the un-enhanced fraction allows.

3abigTranslate to MIPS with bne, then to machine code: if (i!=j) h=i+j; else h=i-j; (f..j = $s0..$s4).

h=$s2, i=$s3, j=$s4:

      bne $s3, $s4, Else
      add $s2, $s3, $s4     # h = i + j
      j   Exit
Else: sub $s2, $s3, $s4     # h = i - j
Exit: ...

bne $s3,$s4,Else : 000101 10011 10100 0000000000000010
add $s2,$s3,$s4  : 000000 10011 10100 10010 00000 100000
j   Exit         : 000010 <26-bit word address of Exit>
sub $s2,$s3,$s4  : 000000 10011 10100 10010 00000 100010

bne offset = 2 (add and j lie between bne and Else).

3bAddress of the last word in MIPS-64 (everything similar to MIPS-32).

Scale the MIPS-32 relationship: 64-bit address, word = 8 bytes. Last byte = $2^{64} - 1$ ; last word = $2^{64} - 8$ . (If the word is kept at 4 bytes, last word = $2^{64} - 4$ — state your assumption.)

Autumn 2024 — Fully Solved

Q1 (CO1) — IAS & Abstraction

Q2 (CO3) — Performance & Amdahl

Q3 (CO2) — MIPS