The following Fortran program is to be executed on a uniprocessor and a parallel version is to be executed on a shared-memory MIMD multiprocessor: L1: Do 10 I = 1, 1024

L2: SUM(I) = 0

L3: Do 20 J = 1, I

L4 20 SUM(I) = SUM(I) + J

L5: 10 Continue

Suppose statements 2 and 4 each take two machine cycles, including all CPU and memory-access activities. Ignore the overhead caused by the software loop control (statements L1, L3, and L5) and all other system overhead and resource conflicts.

a) What is the total execution time of the program on a uniprocessor.

b) Divide the I-loop iterations among 32 processors with pre-scheduling as follows: Processor 1 executes the first 32 iterations (I = 1 to 32), processor 2 executes the next 32 iterations (I = 33 to 64), and so on. What is the execution time and speedup factor compared with part (a) (Note that the computational workload dictated by the J-loop is unbalanced among the processors.

c) Modify the given program to facilitate a balanced parallel execution of the computational load over all 32 processors.

d) What is the minimum execution time of the modified balanced program of part (c) when executing on 32 processors? What is the new speedup over the uniprocessor?