3-Data-Parallel-Problems

Question 1

What is vector addition in mathematical terms?

Answer 1

c = a + b where c_i = a_i + b_i for i = 1 to n

Question 2

What is the serial implementation of vector addition?

Answer 2

for(i=0; i<n; i++) c[i] = a[i] + b[i];

Question 3

How does OpenMP parallelize vector addition?

Answer 3

Add #pragma omp parallel for before the loop

Question 4

What is the fork-join construct in OpenMP?

Answer 4

Main thread spawns worker threads (fork), threads execute loop in parallel, then join back to main thread

Question 5

What are the limitations of #pragma omp parallel for?

Answer 5

Requires known loop trip count at start, constant start/end/stride, no break statements, no while/do-while loops

Question 6

What is a data parallel problem?

Answer 6

Problems where the same operation is applied to multiple data elements independently

Question 7

What is an embarrassingly parallel problem?

Answer 7

A data parallel problem that is straightforward to parallelize with minimal overhead

Question 8

What is the Mandelbrot set used for benchmarking?

Answer 8

Computational intensity and visualization - each pixel calculated independently

Question 9

What is the problem with parallelizing the outer loop in Mandelbrot?

Answer 9

Shared variable i gets updated by multiple threads, causing skipped pixels and distorted images

Question 10

What are the solutions for the Mandelbrot parallelization problem?

Answer 10

1) Declare i inside the loop (private to each thread), 2) Use OpenMP’s private(i) clause

Question 11

What is the collapse clause in OpenMP?

Answer 11

Combines nested loops into a single loop for better load balancing: #pragma omp parallel for collapse(2)

Question 12

What is non-determinism in parallel programs?

Answer 12

Results that differ between program runs due to thread scheduling and interleaving

Question 13

What causes non-determinism in the incorrect Mandelbrot implementation?

Answer 13

Thread scheduler determines order of i increments, causing different pixel calculation orders

Question 14

Why might non-determinism sometimes be acceptable?

Answer 14

Some algorithms tolerate small non-deterministic errors (e.g. in science/engineering) if results are still valid

Question 15

What is the trade-off with enforcing determinism?

Answer 15

Additional synchronization overhead may reduce performance

Question 16

What are the three main types of loop dependencies?

Answer 16

Flow dependencies (read after write), anti-dependencies (write after read), output dependencies (write after write)

Question 17

What is the solution for flow dependencies in loops?

Answer 17

Use temporary arrays or change algorithm to remove dependency

Question 18

What is red-black Gauss-Seidel?

Answer 18

Modified Gauss-Seidel where even elements are updated first, then odd elements, removing dependencies within each phase

Question 19

What is the key insight of red-black Gauss-Seidel?

Answer 19

Dependencies only exist between even and odd elements, not within the same parity group