Parallelism & Multicore

Question 1

(a) Amdahl's Law: with serial fraction $s$, parallel fraction $1-s$ perfectly split over $p$: $S_A(p)=\frac{1}{s+\frac{1-s}{p}}.$ (2 marks derivation)

As $p\to\infty$: $S_A \to 1/s = 1/0.08 = 12.5$. (1 mark)

$S_A(16)=\dfrac{1}{0.08+\frac{0.92}{16}}=\dfrac{1}{0.08+0.0575}=\dfrac{1}{0.1375}=7.2727$. (2 marks)

(b) Gustafson: total scaled work per processor is $s+(1-s)p$, ideal serial time $s+(1-s)p$, parallel time $1$: $S_G(p)=s+(1-s)p = p-s(p-1).$ (3 marks)

$S_G(16)=0.08+0.92\cdot16=0.08+14.72=14.8$. (1 mark)

Modelling assumption: Gustafson fixes time and lets problem size grow with $p$, so the serial part stays constant while parallel work scales up — the serial fraction shrinks relative to total work, avoiding Amdahl's fixed ceiling. (1 mark)

(c) With $s'=0.08$, $R=2\times10^9$:

• Parallel time term: $\frac{N}{pR}(1-s') = \frac{10^9\cdot0.92}{2\times10^9\,p}=\frac{0.46}{p}$ s.
• $T_{\text{serial}}=s'N/R=0.08\cdot10^9/2\times10^9=0.04$ s (constant).
• Coherence: $M(p-1)t_c = 4096(p-1)(120\times10^{-9}) = 4.9152\times10^{-4}(p-1)$ s.

$T(p)=\frac{0.46}{p}+0.04+4.9152\times10^{-4}(p-1).$ (3 marks setup)

Differentiate, ignoring constant terms: $T'(p)=-\frac{0.46}{p^2}+4.9152\times10^{-4}=0 \Rightarrow p^2=\frac{0.46}{4.9152\times10^{-4}}=935.96.$ $p^\*=\sqrt{935.96}=30.59.$ (3 marks)

Round to $p=31$ (check neighbours). $T(31)=0.46/31+0.04+4.9152\times10^{-4}\cdot30 = 0.014839+0.04+0.014746=0.069585$ s. $T(30)=0.015333+0.04+0.014255=0.069588$ s; $T(31)$ slightly lower. Optimum $p\approx31$, $T_{\min}\approx0.0696$ s (≈69.6 ms). (3 marks; accept p=30 or 31 with justification)

(d) False sharing mechanism (2): the per-core statistics array elements sit in the same cache line as the shared counter (or adjacent entries share a line). Even though cores write logically-independent variables, the coherence protocol invalidates the whole line on every write, forcing ping-pong transfers — no true data dependency, pure layout artifact.

Fix (2): pad/align each per-core entry to a full cache line (assume 64 bytes):

struct alignas(64) PerCore { uint64_t stat; char pad[64-sizeof(uint64_t)]; };
PerCore stats[NCORES];  // each in its own line

Effect (1): eliminating false sharing removes the spurious invalidations, so the $M(p-1)t_c$ contention term shrinks toward only the genuinely shared counter's traffic — it does not vanish (the real counter still bounces) but the multiplier on coherence misses drops.

Question 2

(a) (7 marks: correct CAS loop, cap check, return values, atomicity)

bool try_bounded_inc(atomic_uint64 *ctr, uint64 CAP) {
    uint64 cur = atomic_load(ctr);
    for (;;) {
        if (cur >= CAP) return false;         // at cap, refuse
        uint64 next = cur + 1;
        if (CAS(ctr, &cur, next)) return true; // success
        // CAS failed: 'cur' is refreshed to actual value, retry
    }
}

Key points: reload-on-fail (CAS updates cur), cap re-checked each iteration, no lock.

(b) (6 marks) Lock-free: whenever any thread's CAS fails, it failed because another thread's CAS succeeded — so the system as a whole made progress (the counter advanced). Hence at least one thread always completes; no global stall. (3)

Not wait-free: interleaving — Thread A loads cur=5, then before A's CAS, Thread B successfully increments to 6, then Thread C to 7, ... A's CAS keeps failing. In principle other threads can succeed every time just before A, so A retries unboundedly; there is no per-thread step bound. (3)

(c) (4 marks) ABA: a location changes A→B→A between a thread's read and its CAS; the CAS wrongly succeeds because it only sees value equality, missing the intermediate change — dangerous when the value is a pointer/tag whose meaning changed. (2) Immunity here: the counter is monotonically non-decreasing up to CAP; it never revisits a prior value, so no A→B→A sequence can occur. Value equality therefore does imply "unchanged since read." Raw CAS is safe. (2)

(d) (3 marks) Fine-grained CAS: low latency, good when increments are sparse/irregular and threads proceed independently. Barrier BSP: threads compute local partial sums, then one synchronized reduction — better when work is regular, bulk, and per-thread contention on the shared counter would otherwise dominate (avoids the ping-pong of (b)). Favor CAS for irregular/low-contention; favor barrier+reduction for dense/high-contention bulk workloads.

Question 3

(a) (5 marks) Vector iterations $= \lceil 4096/8\rceil = 512$. (1) Ideal speedup with 8 lanes and one FMA/lane/cycle vs scalar one FMA/cycle: 8×. (2) AVX is SIMD (Single Instruction, Multiple Data): one instruction applies the same FMA op across 8 data lanes simultaneously. (2)

(b) (5 marks) For $n=4100$: vector iterations $=\lfloor 4100/8\rfloor = 512$ (covers indices 0..4095); scalar tail $= 4100-4096 = 4$ iterations. (2 for counts)

size_t i = 0;
size_t vend = n - (n % 8);          // 4096
for (; i < vend; i += 8) {          // 512 vector iters
    __m256 vx = _mm256_loadu_ps(&x[i]);
    __m256 vy = _mm256_loadu_ps(&y[i]);
    vy = _mm256_fmadd_ps(_mm256_set1_ps(a), vx, vy);
    _mm256_storeu_ps(&y[i], vy);
}
for (; i < n; ++i)                  // 4 scalar tail iters
    y[i] = a*x[i] + y[i];

(3 for correct main+tail structure)

(c) (6 marks) Effective single-call GPU time $= T_{\text{move}}(\text{in}) + T_{\text{gpu}} + T_{\text{move}}(\text{out}) = 50+3+50 = 103\,\mu s$. (2) CPU AVX $=40\,\mu s < 103\,\mu s$ → offload NOT worthwhile for a single call. (2) For $k$ back-to-back calls reusing resident data (transfer once, or amortized): GPU $=2\cdot50 + k\cdot3 = 100+3k$; CPU $=40k$. Offload wins when $100+3k < 40k \Rightarrow 100 < 37k \Rightarrow k > 2.70$, i.e. $k \ge 3$ calls. (2)

[
  {"claim":"Amdahl S(16) with s=0.08 equals 80/11 approx 7.2727","code":"s=Rational(8,100); SA=1/(s+(1-s)/16); result=(SA==Rational(80,11)) and abs(float(SA)-7.27272727)<1e-6"},
  {"claim":"Gustafson S(16)=14.8","code":"s=Rational(8,100); SG=s+(1-s)*16; result=(SG==Rational(74,5)) and float(SG)==14.8"},
  {"claim":"Optimal continuous p for T(p) is sqrt(0.46/4.9152e-4) approx 30.59","code":"popt=sqrt(Rational(46,100)/Rational(49152,100000000)); result=abs(float(popt)-30.594)<0.01"},
  {"claim":"GPU offload breakeven: k>=3 calls (100+3k<40k)","code":"k=symbols('k'); sol=solve(100+3*k-40*k,k)[0]; result=(abs(float(sol)-Rational(100,37))<1e-9) and (3>float(sol)) and (2<float(sol))"},
  {"claim":"AVX vector iters for n=4100 is 512 and scalar tail is 4","code":"n=4100; result=(n//8==512) and (n%8==4)"}
]