Level 1 — RecognitionParallelism & Multicore

Parallelism & Multicore

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Difficulty Level: 1 (Recognition) Time Limit: 20 minutes Total Marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. A single processor executing one instruction stream on one data stream is classified under Flynn's taxonomy as:

(a) SIMD
(b) MISD
(c) SISD
(d) MIMD

Q2. A GPU applying the same operation to many data elements simultaneously best matches which Flynn category?

(a) SISD
(b) SIMD
(c) MIMD
(d) MISD

Q3. Instruction-level parallelism (ILP) is primarily exploited by:

(a) The operating system scheduler across cores
(b) Hardware pipelining and superscalar execution within a core
(c) Manually spawning OS threads
(d) Distributed message passing

Q4. Amdahl's Law with serial fraction $s$ gives the maximum speedup on $N$ processors as:

(a) $N(1-s)$
(b) $\dfrac{1}{s + \frac{1-s}{N}}$
(c) $s + N(1-s)$
(d) $\dfrac{N}{s}$

Q5. Gustafson's Law differs from Amdahl's Law mainly because it assumes:

(a) The problem size stays fixed as processors increase
(b) The problem size scales with the number of processors
(c) There is no serial fraction
(d) Communication cost is zero

Q6. In a shared-memory system, processors communicate primarily through:

(a) Explicit message passing
(b) A common address space
(c) Disk files
(d) Network sockets only

Q7. A directory-based cache coherence protocol is preferred over snooping mainly because:

(a) It uses less memory
(b) It scales better by avoiding broadcast on a shared bus
(c) It is simpler to implement
(d) It removes the need for coherence entirely

Q8. In a NUMA architecture, the key property is that:

(a) All memory has identical access latency
(b) Memory access time depends on which node holds the data relative to the accessing core
(c) There is only one physical memory bank
(d) Caches are disabled

Q9. A Compare-And-Swap (CAS) operation:

(a) Always writes the new value unconditionally
(b) Atomically writes only if the current value matches the expected value
(c) Requires the OS to disable interrupts
(d) Works only on single-core systems

Q10. False sharing occurs when:

(a) Two threads write to the same variable
(b) Two threads write to different variables that reside on the same cache line
(c) A cache line is never evicted
(d) A lock is held too long

Q11. AVX, SSE, and NEON are examples of:

(a) Cache coherence protocols
(b) SIMD/vector instruction set extensions
(c) Synchronization primitives
(d) NUMA node interconnects

Q12. Compared with multicore, a "manycore" design typically features:

(a) Fewer, more powerful cores
(b) Many simpler, lower-power cores optimized for throughput
(c) No caches
(d) A single execution thread

Section B — Matching (1 mark each, 6 marks)

Q13. Match each term (13a–13f) to the best description (i–vi).

Term		Description
13a. Barrier		(i) Ensures mutual exclusion for a critical section
13b. Lock/Mutex		(ii) All threads wait until every thread reaches a point
13c. Thread-level parallelism		(iii) CPU + GPU + accelerators cooperating on one workload
13d. Heterogeneous computing		(iv) Multiple independent instruction streams run concurrently
13e. Distributed memory		(v) Each node has private memory; communication via messages
13f. Atomic operation		(vi) Executes indivisibly with no observable intermediate state

Section C — True/False WITH Justification (2 marks each: 1 T/F + 1 justification, 12 marks)

State True or False and give a one-line justification.

Q14. According to Amdahl's Law, if 20% of a program is serial, the maximum possible speedup is bounded by 5, no matter how many processors are used.

Q15. In SIMD execution, each processing element may execute a completely different instruction on its data element at the same time.

Q16. Adding more cores always guarantees a proportional reduction in a program's total execution time.

Q17. False sharing can be reduced by padding data structures so that variables used by different threads fall on separate cache lines.

Q18. A spinlock keeps a waiting thread busy repeatedly checking a lock variable instead of sleeping.

Q19. In a shared-memory MIMD system, no synchronization is needed because all cores see the same memory.

End of paper.

Answer keyMark scheme & solutions

Section A (1 mark each)

Q1 — (c) SISD. One instruction stream, one data stream = classic uniprocessor. (1)

Q2 — (b) SIMD. One instruction broadcast to many data lanes (data-parallel). (1)

Q3 — (b) Hardware pipelining and superscalar execution within a core. ILP overlaps independent instructions inside one core; TLP is the OS/thread-level one. (1)

Q4 — (b) $\frac{1}{s + \frac{1-s}{N}}$ . Serial part $s$ unaffected; parallel part $(1-s)$ divided by $N$ . (1)

Q5 — (b) The problem size scales with the number of processors. Gustafson assumes scaled workloads (weak scaling), giving near-linear speedup. (1)

Q6 — (b) A common address space. Defining feature of shared memory. (1)

Q7 — (b) It scales better by avoiding broadcast on a shared bus. A directory tracks sharers, sending point-to-point messages instead of bus broadcasts. (1)

Q8 — (b) Memory access time depends on which node holds the data. "Non-Uniform Memory Access" = latency varies by locality. (1)

Q9 — (b) Atomically writes only if the current value matches the expected value. CAS(expected, new): compare then conditionally swap, indivisibly. (1)

Q10 — (b) Two threads write to different variables on the same cache line. Coherence traffic bounces the line though logically no data is shared. (1)

Q11 — (b) SIMD/vector instruction set extensions. SSE/AVX (x86), NEON (ARM). (1)

Q12 — (b) Many simpler, lower-power cores optimized for throughput. Manycore trades single-thread strength for parallel throughput. (1)

Section B (1 mark each)

Q13: 13a→(ii), 13b→(i), 13c→(iv), 13d→(iii), 13e→(v), 13f→(vi). (6 × 1)

Section C (2 marks each: 1 verdict + 1 justification)

Q14 — True. Max speedup $= 1/s = 1/0.20 = 5$ as $N\to\infty$ ; serial part sets the ceiling. (T =1, justification =1)

Q15 — False. SIMD applies the same single instruction to all lanes; differing instructions per element would be MIMD. (1+1)

Q16 — False. Serial fractions, synchronization, and communication overhead limit gains (Amdahl); scaling is not automatically proportional. (1+1)

Q17 — True. Padding/alignment places contended variables on distinct cache lines, eliminating false coherence invalidations. (1+1)

Q18 — True. A spinlock busy-waits (spins) polling the lock, avoiding context-switch cost but wasting CPU cycles. (1+1)

Q19 — False. Shared memory still requires synchronization (locks, atomics, barriers) to avoid race conditions on concurrent updates. (1+1)

Marks Summary

Section A: 12
Section B: 6
Section C: 12
Total: 30

[
  {"claim": "Amdahl max speedup with s=0.2 is 5 as N->infinity", "code": "s=Rational(1,5); limit_val=limit(1/(s+(1-s)/n), n, oo); result = (limit_val == 5)"},
  {"claim": "Amdahl speedup formula with s=0.2, N=8 equals 1/(0.2+0.8/8)", "code": "s=Rational(1,5); N=8; sp=1/(s+(1-s)/N); result = (sp == Rational(1, s+(1-s)/N).q and simplify(sp - Rational(10,3))==0)"},
  {"claim": "Amdahl speedup s=0.2 N=8 simplifies to 10/3", "code": "s=Rational(1,5); N=8; sp=1/(s+(1-s)/N); result = (simplify(sp - Rational(10,3)) == 0)"},
  {"claim": "Q4 formula reduces to N when s=0 (fully parallel ideal)", "code": "N=symbols('N', positive=True); expr=1/(0 + (1-0)/N); result = (simplify(expr - N) == 0)"}
]