Parallelism & Multicore

Question 1

(a) Parallel time $= 200 - 30 = 170$ ms. Parallel fraction $p = \frac{170}{200} = 0.85.$ Serial fraction $s = 0.15$. (2: 1 for parallel time, 1 for fraction)

(b) Amdahl speedup with $N=8$: $S = \frac{1}{s + p/N} = \frac{1}{0.15 + 0.85/8} = \frac{1}{0.15 + 0.10625} = \frac{1}{0.25625} = 3.902\times.$ Runtime $= 200/3.902 = 51.25$ ms (equivalently $30 + 170/8 = 30 + 21.25 = 51.25$ ms). (4: 2 speedup formula/value, 2 runtime)

(c) As $N\to\infty$, $p/N\to 0$: $S_{\max} = \frac{1}{s} = \frac{1}{0.15} = 6.667\times.$ (2)

(d) Require $S = 5$: $5 = \frac{1}{0.15 + 0.85/N} \Rightarrow 0.15 + \frac{0.85}{N} = 0.2 \Rightarrow \frac{0.85}{N} = 0.05 \Rightarrow N = 17.$ Minimum cores $= 17$. (3: 1 setup, 1 algebra, 1 round-up/answer)

(e) Gustafson: scaled speedup $S = s + p\cdot N$ using serial fraction of the scaled workload. Scaled total serial-equivalent time on 1 core $= 30 + 170\times 8 = 30 + 1360 = 1390$ ms; on 8 cores it takes $200$ ms. $S = \frac{1390}{200} = 6.95\times.$ (Equivalently $s + pN = 0.15 + 0.85\times 8 = 6.95$.) Reason: Amdahl fixes problem size (serial part dominates as cores grow), whereas Gustafson grows the problem with the machine, so the serial fraction shrinks and speedup scales nearly linearly. (3: 2 value, 1 explanation)

Question 2

(a) SIMD — one instruction stream applied across many data elements (pixels) in lockstep. (2)

(b) MIMD — independent instruction streams (different code paths) on different data across nodes. (2)

(c) SISD — single instruction stream, single data stream, one operation at a time. (2)

(d)(i) Shared memory — fine-grained, frequent irregular sharing benefits from a single address space with low-latency direct access; message passing would incur huge messaging overhead per share. (3)

(d)(ii) Distributed memory — independent tasks need no data sharing, so 500 machines scale out with no coherence/interconnect bottleneck; shared memory cannot span 500 machines cost-effectively. (3)

Question 3

(a) False sharing. All four counters lie in the same cache line; when one thread writes its counter, the coherence protocol invalidates that line in the other cores' caches even though they access different counters, forcing repeated cache-line ping-ponging. (3)

(b) $64 / 8 = 8$ longs per line. Since $4 \le 8$, all 4 counters fit in — and therefore share — a single 64-byte cache line. (2)

(c) Pad each counter to a full cache line, e.g.

struct alignas(64) PaddedCounter { long value; char pad[56]; };
PaddedCounter counters[4];

Padded struct size $= 8 + 56 = 64$ bytes, so each counter occupies its own line and no false sharing occurs. (4: 2 padding idea/code, 2 size = 64)

(d) Snooping broadcasts every coherence transaction to all cores over a shared bus — bus bandwidth becomes the bottleneck at 128 cores ($O(N)$ traffic per event). Directory-based coherence keeps a directory recording which cores hold each line and sends point-to-point messages only to sharers, avoiding broadcast and scaling to large core counts. (3)

Question 4

(a) CAS(address, expected, new): atomically compares the value at address to expected; if equal it writes new and returns success, else it does nothing and returns failure. The loop retries because another thread may have changed stack.top between the read and the CAS; the CAS only commits if top is still old_top. (3)

(b) Under high contention many threads read the same old_top; only one CAS succeeds, the other 15 fail and re-loop. Wasted retries grow with thread count, so throughput plateaus and can degrade — the atomic memory location becomes a serialization hotspot. (3)

(c) ABA interleaving:

• T1 reads old_top = A.
• T1 is descheduled.
• T2 pops A, pops B, then pushes A back (top = A again), but A's next now differs.
• T1 resumes; CAS sees top still == A, succeeds — but the stack structure changed and T1's new_node.next points to a stale/freed node, corrupting the stack. Mitigation: use a tagged/versioned pointer (add a monotonically increasing counter to the pointer so ABA is detected), or hazard pointers / double-width CAS. (4: 3 interleaving, 1 mitigation)

(d) Spinlock: provides mutual exclusion — one thread enters a critical section at a time (others busy-wait). Barrier: a synchronization point — all threads must arrive before any proceeds past it. (2)

Question 5

(a) $512 / 32 = 16$ floats per register. (2)

(b) $N / 16 = 1{,}048{,}576 / 16 = 65{,}536$ vector add instructions. (3)

(c) Ideal speedup $= N / (N/16) = 16\times$. (2)

(d) Any two: memory bandwidth / load-store overhead limits throughput (memory-bound kernel); data alignment and non-multiple-of-16 tail handling; SIMD width underutilization from branches; power/frequency throttling under AVX-512; loop overhead and dependencies. (3: 1.5 each)

[
  {"claim":"Amdahl speedup on 8 cores = 3.902","code":"s=Rational(15,100); p=Rational(85,100); S=1/(s+p/8); result = abs(float(S)-3.90243902439)<1e-6"},
  {"claim":"Max Amdahl speedup = 6.667","code":"s=Rational(15,100); result = abs(float(1/s)-6.6666666667)<1e-6"},
  {"claim":"Cores needed for 5x speedup = 17","code":"s=Rational(15,100); p=Rational(85,100); N=symbols('N',positive=True); sol=solve(Eq(1/(s+p/N),5),N); import math; result = math.ceil(float(sol[0]))==17"},
  {"claim":"Gustafson scaled speedup = 6.95","code":"s=Rational(15,100); p=Rational(85,100); result = abs(float(s+p*8)-6.95)<1e-9"},
  {"claim":"AVX-512 vector adds needed = 65536 and speedup 16","code":"N=1048576; lanes=512//32; result = (N//lanes==65536) and (N//(N//lanes)==16)"}
]