Parallelism & Multicore

Q1. (6 marks) Four categories (1 mark each = 4):

• SISD — Single Instruction, Single Data
• SIMD — Single Instruction, Multiple Data
• MIMD — Multiple Instruction, Multiple Data
• MISD — Multiple Instruction, Single Data

Examples (1 mark each = 2):

• SIMD example: GPUs / vector processors / AVX-SSE units (any valid). Why: one instruction applied across many data lanes.
• MIMD example: multicore CPUs / clusters. Why: independent cores execute different instruction streams on different data.

Q2. (6 marks)

• ILP (1) = parallelism within a single instruction stream — independent instructions executed simultaneously (1). Technique: pipelining / superscalar execution / out-of-order execution (1).
• TLP (1) = parallelism across multiple threads/streams running concurrently (1). Technique: multithreading (SMT/hyperthreading) / multicore execution (1).

Q3. (6 marks) Amdahl's Law: $S = \dfrac{1}{(1-p) + \frac{p}{N}}$, with $p = 0.8$, serial fraction $1-p = 0.2$.

(a) $N=4$: $S = \dfrac{1}{0.2 + \frac{0.8}{4}} = \dfrac{1}{0.2 + 0.2} = \dfrac{1}{0.4} = 2.5$ (3 marks: setup 1, substitution 1, answer 1)

(b) $N=\infty$: $\frac{p}{N} \to 0$, so $S = \dfrac{1}{0.2} = 5$ (3 marks)

Q4. (5 marks) Gustafson's Law (3): scaled speedup $S = N - s(N-1)$ (equivalently $S = s + N(1-s)$), where $s$ is the serial fraction and $N$ is the number of processors. Why credited: it assumes the problem size grows with the number of processors (fixed time, scaled workload) (2), whereas Amdahl's Law assumes a fixed problem size — bounding speedup by the serial portion.

Q5. (6 marks)

• Shared memory (1): all processors access a single common address space (1). Advantage: easy communication via shared variables / simpler programming model (1).
• Distributed memory (1): each processor has its own private memory; communication via message passing (1). Advantage: scales to many nodes / no memory contention bottleneck (1).

Q6. (4 marks) Snooping requires every coherence transaction to be broadcast on a shared bus, which does not scale as the number of cores grows (bus saturation / bandwidth limits) (2). Directory-based protocols keep a directory tracking which caches hold each block, sending point-to-point messages only to relevant caches — this reduces traffic and scales to large core counts / distributed interconnects (2).

Q7. (4 marks) NUMA = Non-Uniform Memory Access (1). It is a shared-memory design where memory is physically distributed among processors/nodes (1). "Non-uniform" refers to memory access latency depending on location: accessing local memory is faster than accessing remote memory attached to another node (2).

Q8. (5 marks) CAS atomically compares the value at a memory location to an expected value; if equal, it writes a new value and reports success (2). Pseudocode (3):

CAS(addr, expected, new):
    atomically:
        if *addr == expected:
            *addr = new
            return true      // success
        else:
            return false     // value changed

Q9. (4 marks) False sharing (3): occurs when two threads modify different variables that happen to reside on the same cache line; the coherence protocol invalidates/ping-pongs the whole line between cores even though there is no true data dependency, degrading performance. Mitigation (1): pad/align data so independent variables occupy separate cache lines (or reorganize data layout).

Q10. (4 marks) Gustafson's Law: $S = N - s(N-1)$ with $N=16$, $s=0.05$. $S = 16 - 0.05 \times 15 = 16 - 0.75 = 15.25$ (setup 2, answer 2).

[
  {"claim":"Amdahl speedup with p=0.8, N=4 equals 2.5","code":"p=Rational(8,10); N=4; S=1/((1-p)+p/N); result = (S==Rational(5,2))"},
  {"claim":"Amdahl speedup with p=0.8, N->inf equals 5","code":"p=Rational(8,10); S=1/(1-p); result = (S==5)"},
  {"claim":"Gustafson scaled speedup with N=16, s=0.05 equals 15.25","code":"N=16; s=Rational(5,100); S=N - s*(N-1); result = (S==Rational(61,4))"},
  {"claim":"Gustafson forms N-s(N-1) and s+N(1-s) are equal","code":"N,s=symbols('N s'); result = simplify((N - s*(N-1)) - (s + N*(1-s)))==0"}
]