Parallelism & Multicore

Question 1 (12 marks)

(a) Normalize total serial-execution time to $T(1)=1$. Split into serial fraction $s=1-p$ and parallel fraction $p$. On $n$ cores the parallel part takes $p/n$, serial part unchanged: $T(n) = (1-p) + \frac{p}{n}, \qquad S(n) = \frac{1}{(1-p) + \frac{p}{n}}$

• Normalization statement (1), split into $(1-p)+p/n$ (1), reciprocal form (1).

(b) With $p=0.9$, $n=8$: $S(8) = \frac{1}{0.1 + 0.9/8} = \frac{1}{0.1 + 0.1125} = \frac{1}{0.2125} \approx 4.7059$ As $n\to\infty$: $S_\infty = 1/(1-p) = 1/0.1 = 10$.

• $S(8)\approx 4.71$ (2), $S_\infty = 10$ (1).

(c) Gustafson assumes the parallel work scales with $n$ (fixed time, grow problem). Normalize scaled parallel run to $s + p = 1$ where $p$ is now measured on $n$ cores; the equivalent serial time is $s + p\cdot n$: $S_s(n) = \frac{s + p\,n}{s + p} = s + p\,n = (1-p) + p\,n$ For $p=0.9$, $n=8$: $S_s = 0.1 + 0.9\times 8 = 0.1 + 7.2 = 7.3$.

• Scaled-workload assumption (1), derivation $s+pn$ (2), value $7.3$ (1).

(d) Amdahl fixes the problem size — the serial part becomes an ever-larger share of a shrinking total, capping speedup at $1/(1-p)$. Gustafson fixes the time budget and grows the problem, so the serial fraction shrinks relatively and speedup grows ~linearly. Same $p$, different assumption about what stays constant.

• Any correct fixed-size vs scaled-size explanation (2).

Question 2 (8 marks)

(a) (4, 1 each)

• SISD — classic single-core scalar CPU.
• SIMD — vector unit / GPU lane group / AVX; one instruction over many data.
• MISD — rare; systolic arrays / fault-tolerant lockstep pipelines cited as the nearest example.
• MIMD — multicore CPU, cluster; independent instruction streams over independent data.

(b) (4)

• ILP: parallelism within a single instruction stream — independent instructions issued/executed together. Mechanism: superscalar out-of-order execution / pipelining (2).
• TLP: parallelism across multiple threads/streams. Mechanism: multicore, SMT/hyper-threading (2).

Question 3 (14 marks)

(a) (5)

acquire(lock):
    while CAS(&lock, 0, 1) != 0:
        ;              // spin: succeeded only if old value was 0
release(lock):
    store(&lock, 0)    // atomic store

• CAS in loop (2), correct expected=0/new=1 (1), checks returned old value (1), release stores 0 (1).

(b) A plain if(lock==0) lock=1 has a race: two threads can both read 0 before either writes 1, so both enter the critical section. The read and write are not atomic — a context switch/interleaving between them breaks mutual exclusion. (3)

(c) Test-and-test-and-set: (4)

acquire(lock):
    do {
        while (load(&lock) != 0) ;   // spin on cached read only
    } while (CAS(&lock, 0, 1) != 0); // attempt only when it looks free

Benefit: the inner spin reads a cached copy in Shared state, generating no bus/coherence traffic while the lock is held; only when it appears free does a thread issue the write-generating CAS (RFO). This drastically cuts invalidation storms on many-core systems.

• TTAS structure (2), cached-read/coherence explanation (2).

(d) ABA: a value read as A, changed to B and back to A, so CAS wrongly succeeds thinking nothing changed. Mitigation: version/generation counter (tagged pointer) or hazard pointers. (2)

Question 4 (10 marks)

(a) Both a and b sit on the same 64-byte cache line. Each write invalidates the whole line in the other core's cache (MESI), forcing ping-pong ownership transfers even though the threads use different variables — this is false sharing. (3)

(b) (4)

struct Counters {
    alignas(64) int64_t a;
    alignas(64) int64_t b;
};

Each counter is padded/aligned to its own 64-byte line. Memory cost: 64 bytes per counter instead of 8 → 56 bytes wasted padding each. (code 2, cost 2)

(c) Assumption: worst case one invalidation per increment. Total increments $= 2\times10^7$; wasted $= 2\times10^7 \times 100 = 2\times10^9$ cycles. (assumption 1, arithmetic 2)

Question 5 (10 marks)

(a) Snooping broadcasts every coherence transaction on a shared bus/interconnect; bus bandwidth and every cache's snoop capacity become the bottleneck as core count grows — $O(n)$ traffic per miss. A directory keeps, per memory line, a record of which caches hold a copy and its state (e.g., sharer bitmap/pointers + state Modified/Shared/Invalid/owner). Coherence messages are sent point-to-point only to relevant caches, avoiding broadcast. (scaling problem 2, directory tracks sharers+state 2, point-to-point 1)

(b) NUMA = Non-Uniform Memory Access: memory is partitioned among nodes, and a core accesses its local node's memory faster than remote nodes'. First-touch: a page is physically placed on the node of the thread that first writes/touches it, so allocating and initializing data on the thread that will use it keeps accesses local and fast. (NUMA def 1.5, first-touch 1.5)

(c) Large NUMA systems have many nodes/cores; snooping can't scale across the interconnect, so directory-based coherence is the natural mechanism to keep the distributed memory coherent. (2)

Question 6 (6 marks)

(a) 256/32 = 8 float32; 256/64 = 4 float64. (1 each)

(b) SIMD executes one instruction lock-step across all lanes, but a data-dependent branch means different lanes want different control paths — you can't take two paths simultaneously. Technique: masking/predication — compute both sides (or the taken side) for all lanes and use a mask to select/blend results per lane, keeping lanes in lock-step. (divergence problem 2, masking/predication 2)

[
  {"claim":"Amdahl S(8) with p=0.9 approx 4.7059","code":"p=Rational(9,10); n=8; S=1/((1-p)+p/n); result = abs(float(S)-4.70588235)<1e-6"},
  {"claim":"Amdahl max speedup = 10","code":"p=Rational(9,10); result = 1/(1-p)==10"},
  {"claim":"Gustafson scaled speedup n=8 = 7.3","code":"p=Rational(9,10); n=8; Ss=(1-p)+p*n; result = float(Ss)==7.3"},
  {"claim":"False sharing wasted cycles = 2e9","code":"result = 2*10**7*100 == 2000000000"},
  {"claim":"AVX2 holds 8 float32 and 4 float64","code":"result = (256//32==8) and (256//64==4)"}
]