which the application was running s

which the application was running simultaneously on all nine computers. The remaining
time, the application had to run on a single computer.
a. Calculate the effective speedup under the aforementioned condition as compared
to executing the program on a single computer. Also calculate a, the percentage of
code that has been parallelized (programmed or compiled so as to use the cluster
mode) in the preceding program.
b. Suppose that we are able to effectively use 17 computers rather than 9 computers
on the parallelized portion of the code. Calculate the effective speedup that is
achieved.
17.15 The following FORTRAN program is to be executed on a computer, and a parallel
version is to be executed on a 32-computer cluster.
L1: DO 10 I = 1, 1024
L2: SUM(I) = 0
L3: DO 20 J = 1, I
L4: 20 SUM(I) = SUM(I) + I
L5: 10 CONTINUE
Suppose lines 2 and 4 each take two machine cycle times, including all processor
and memory-access activities. Ignore the overhead caused by the software
loop control statements (lines 1, 3, 5) and all other system overhead and resource
conflicts.
a. What is the total execution time (in machine cycle times) of the program on a
single computer?
b. Divide the I-loop iterations among the 32 computers as follows: Computer 1 executes
the first 32 iterations (I = 1 to 32), processor 2 executes the next 32 iterations,
and so on. What are the execution time and speedup factor compared with
part (a)? (Note that the computational workload, dictated by the J-loop, is unbalanced
among the computers.)
c. Explain how to modify the parallelizing to facilitate a balanced parallel execution
of all the computational workload over 32 computers. By a balanced load is meant
an equal number of additions assigned to each computer with respect to both
loops.
d. What is the minimum execution time resulting from the parallel execution on
32 computers? What is the resulting speedup over a single computer?
17.16 Consider the following two versions of a program to add two vectors:
L1: DO 10 I = 1, N DOALL K = 1, M
L2: A(I) = B(I) + C(I) DO 10 I = L(K - 1) + 1, KL
L3: 10 CONTINUE A(I) = B(I) + C(I)
L4: SUM = 0 10 CONTINUE
L5: DO 20 J = 1, N SUM(K) = 0
L6: SUM = SUM + A(J) DO 20 J = 1, L
L7: 20 CONTINUE SUM(K) = SUM(K) + A(L(K - 1) + J)
20 CONTINUE
ENDALL
a. The program on the left executes on a uniprocessor. Suppose each line of code
L2, L4, and L6 takes one processor clock cycle to execute. For simplicity, ignore
the time required for the other lines of code. Initially all arrays are already loaded
in main memory and the short program fragment is in the instruction cache. How
many clock cycles are required to execute this program?
17.9 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 663
b. The program on the right is written to execute on a multiprocessor with M processors.
We partition the looping operations into M sections with L = N>M elements
per section. DOALL declares that all M sections are executed in parallel. The
result of this program is to produce M partial sums. Assume that k clock cycles are
needed for each interprocessor communication operation via the shared memory
and that therefore the addition of each partial sum requires k cycles. An l-level
binary adder tree can merge all the partial sums, where l = log2M. How many
cycles are needed to produce the final sum?
c. Suppose N = 220 elements in the array and M = 256. What is the speedup
achieved by using the multiprocessor? Assume k = 200. What percentage is this
of the theoretical speedup of a factor of 256?