Assignment_8 Solution

Description

Problem 1 – Dependencies

Suppose we have the following program (a sequence of instructions), with each instruction labeled as

S<num>:

• ₁ : a := 4;

• ₂ : b := 2;

• ₃ : c := 5;

• ₄ : read ( d );

• ₅ : a := b + 3;

• ₆ : b := a – 3;

• ₇ : c := d * b ;

• ₈ : e := a + 6;

• ₉ : print ( c );

• ₁₀ : print ( e );

• 1. Give the statement-level dependence graph for the above program. A node in the statement-level dependence graph represents a statement, an edge represents dependence between the statements (i.e. the nodes). Label each edge as a true data dependence, an anti data dependence, or an output data dependence.

• 2. Assume that each statement takes 1 cycle to execute. What is the execution time of the sequen-tial code? What is the fastest parallel execution time of the program (i.e. the critical path)? You may assume that I/O operations (read and print) can be done in parallel.

Problem 2 – Dependence Analysis

Give the source and sink references, the type (whether a dependence is true, anti, or output), and the distance vectors for all dependences in the following loops.

1. do i = 3, 100

a(i) = a(i – 1) + a(i + 1) – a(i – 2)

enddo

2. do i = 2, 100

a(3 * i) = a(3 * i – 3) + a(3 * i + 3)

enddo

3. do i = 1, 10

a(i) = a(5) + a(i)

enddo

Use a_W (i) and a_R(i) to annotate the write access to a(i) and the read access to a(i) respectively.

Problem 3 – Loop Parallelization

Given the following nested loop:

• ₂ :b (i , j ) = i + j – 1 enddo

enddo

1. Give the statement-level dependence graph. Show the dependence graph for statement instances in a part of the iteration space: i = 2 … 5, j = 2 … 5.

2. In its current form, can any loop be parallelized? If so, which loop(s)? If not, justify your answer.

3. Provide one valid a ne schedule for statements S₁ and S₂ such that p(S₁)= C₁₁*i + C₁₂*j + d₁ and p(S₂)= C₂₁*i + C₂₂*j + d₂ in order to achieve synchronization-free parallelism. There could be many possible solutions for fC₁₁; C₁₂; C₂₁; C₂₂; d₁; d₂g. You only need to provide one feasible solution. (Hint: You can let d₁ = d₂ = 0.)

4. Generate two-level loop code for the a ne schedule you provided. Please use p as outermost loop and i as innermost loop in the transformed loop. Calculate the loop bounds for p and i using Fourier-Motzkin elimination. You might need to calculate the overlapping polyhedron for S₁ and S₂ in order to eliminate the j loop. Please refer to the techniques for code generation in lecture 20 and lecture 21.

2