Problem 3 – Loop Parallelization do i = 2, 100 do j = 2, 100 S1: a(i, j) = b(i-1

Question

Problem 3 – Loop Parallelization

do i = 2, 100

do j = 2, 100

S1: a(i, j) = b(i-1, j-1) + 1

S2: b(i, j) = a(i, j-1) - 1

enddo

enddo

1. Give the statement-level dependence graph with distance vectors

2. In its current form, can any loop level be parallelized? If so, use the doall parallel construct, or a statement like, e.g., c(k, 1:100) = d(k, 1:100), to show the resulting (partially) parallelized loop.

3. Extra-credit question (10 pts): Can you give (and justify) the maximum parallelism (the number of statement instances that can be executed at the same time)?

Explanation / Answer

1.s1 = a(2:N, 2:N) = b(1:N,1:N) +1

S2 = b(2:N,2:N) = a(2:N,1:N) -1

a>b in S1 and in S2 it is > so the distance vector is (>,<)

2 No parallelization is possible as there are loop carried dependencies at both loop levels

3.yes we can maximize the parellism by interchanging the loops where both dependencies are carried by the outer loop which results in parallelization in the innermost loop.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.