High Performance computing (AL-802 (B)) - Important Questions

Explain the OpenMP "parallel for" construct. Discuss data scoping clauses $shared$, $private$ and $reduction$ with examples, and describe common pitfalls such as race conditions and false sharing.

Describe the OpenMP synchronization constructs $critical$, $atomic$, $barrier$ and $flush$. For each construct explain its semantics, typical use-cases and the performance impact compared to lock-free approaches.

State Amdahl's law and use it to compute the theoretical speedup $S(N)$ for a program with parallel fraction $p$ on $N$ processors. Express $S(N)$ using a formula and determine the limit $\lim_{N\to\infty}S(N)$.

State Gustafson's law and derive the scaled speedup for a workload where the parallel portion grows with the number of processors. Compare the implications of Gustafson's law with Amdahl's law for scalability.

Define parallel speedup and parallel efficiency. Given serial time $T_{1}$ and parallel time on $N$ processors $T_{N}$, write formulas for speedup $S(N)$ and efficiency $E(N)$. Compute $S(N)$ and $E(N)$ for $T_{1}=100\,\text{s}$, $T_{8}=18\,\text{s}$.

Explain the difference between strong scaling and weak scaling. Given a problem with baseline size $W$ and times $T_{1}=200\,\text{s}$, $T_{4}=60\,\text{s}$ for the same problem size (strong scaling), and times $T'_{1}=200\,\text{s}$, $T'_{4}=52\,\text{s}$ when the problem size increases proportionally with processors (weak scaling), compute and interpret the efficiency in both cases.

Define the iso-efficiency metric for parallel algorithms. For a parallel algorithm whose total parallel runtime is $T_{P}=\frac{W}{P}+T_{o}(P,W)$ with overhead $T_{o}(P,W)=\alpha\,P\log P$, derive the asymptotic iso-efficiency relation between problem size $W$ and number of processors $P$ to maintain constant efficiency.

Given measured speedup $S(N)$ on $N$ processors, derive a formula to estimate the parallel fraction $p$ assuming Amdahl's model. Use the formula to compute $p$ if $S(8)=5.2$ on $N=8$ processors.

Explain OpenMP loop scheduling clauses $schedule(static)$, $schedule(dynamic)$ and $schedule(guided)$. For a loop with highly variable per-iteration workload, which schedule would you choose and why?

What is false sharing in shared-memory parallel programs? Describe how false sharing arises with an example and list at least three techniques to mitigate it in an OpenMP program.

Describe the OpenMP tasking model. Explain the use of $task$, $taskwait$ and the $depend$ clause with a short code sketch showing producer-consumer task dependencies.