Q1. What do you mean by dependency graph? Describe WAW, RAW and WAR dependencies.
Q2. Write down a parallel algorithm for the odd-even transposition sort, to sort an array of n elements on linear array having n processors. Describe the cost of algorithm.
Q3. Describe the temporal, data and control parallelism with illustrations.
Q4. For the given sequence of instructions:
a) S1: A = B + C
b) S2: B = A + E
c) S3: D = A * F
d) S4: G = I / F + A
e) S5: H = B – D
f) S6 if D = 3
g) S7 K= G * 2 + I
Construct the dependence graph and apply Bernstein’s condition to show the sets of instructions that can be executed in parallel.
Q5. Calculate the speedup in execution of the given computation: A × B + C
With chaining and without chaining, on a vector processor with two pipeline functional units, one for floating point multiply and other for add, which are seven phases and six phases long correspondingly. Let us assume that A, B and C are three vectors each of 64 elements.
Q6. What do you mean by Systolic Array Processors? How it is distinct than SIMD and pipelined processors?