5-Loop-Parallelism

Question 1

What is loop parallelism?

Answer 1

Parallelizing loops by distributing iterations across multiple threads

Question 2

What are the three types of loop dependencies?

Answer 2

Flow dependencies (RAW - read after write), Anti-dependencies (WAR - write after read), Output dependencies (WAW - write after write)

Question 3

How do you identify loop dependencies?

Answer 3

Check if variables are read/written in different iterations in conflicting orders

Question 4

What is the solution for flow dependencies?

Answer 4

Use temporary arrays to break the read-after-write dependency

Question 5

What happens in the incorrect parallel shift example?

Answer 5

for(i=0; i<n-1; i++) a[i] = a[i+1]; - threads overwrite values before others read them

Question 6

What is the correct solution for parallel array shifting?

Answer 6

Use a temporary array: copy to temp first, then shift from temp

Question 7

What is the Gauss-Seidel method?

Answer 7

Iterative numerical method where each element is updated using neighbors: a[i] = 0.5*(a[i-1] + a[i+1])

Question 8

Why is standard Gauss-Seidel not parallelizable?

Answer 8

Each update depends on the previous update in the loop

Question 9

What is red-black Gauss-Seidel?

Answer 9

Modified version where even indices are updated first, then odd indices, removing dependencies within each phase

Question 10

How does red-black ordering remove dependencies?

Answer 10

Even elements depend on odd neighbors, odd elements depend on even neighbors - separating by parity breaks this cycle

Question 11

What are the two phases in red-black Gauss-Seidel?

Answer 11

Phase 1: update all even indices, Phase 2: update all odd indices

Question 12

What is the key insight for parallelizing dependent algorithms?

Answer 12

Sometimes a small algorithm change can remove dependencies while preserving correctness

Question 13

What are the limitations of the dependency removal approach?

Answer 13

May require more iterations to converge, but each iteration is now parallelizable

Question 14

What is the general strategy for handling loop dependencies?

Answer 14

1) Identify dependencies, 2) Try to remove them with algorithm changes, 3) Use synchronization if removal impossible, 4) Consider if parallelization is worth the overhead