Question

Homework #5 Due: Wednesday, Sept. 23 at 5 PM 5. There is a "paradigm shift" making parallel programming conceptually different from sequential programming. A simple example is summing an array x containing n elements. Sequential Algorithm: Algorithm sum = 0; for (i = 0; i < n; i++) { sum = sum + x[i]; } // end for Parallel Pair-Wise Summation a) How long would each algorithm take? b) How many processors does the pair-wise summation algorithm utilize? We can categorize sources of overhead in parallel programs that limit speedup as follows: interprocess communication/interaction - processors need to communicate data (i.e., intermediate results) idle processors - processors can be idle for a variety of reasons: > load imbalance - a processor is assigned less work than others so it sits idle waiting of others to finish synchronization - processor need to to coordinate their operations (e.g., barrier synchronization) so processors done sooner must wait for others to complete > non-parallelizable computation/task - some serial component that cannot be done in parallel. Amdahl's law applies here. parallelization overhead - additional costs in the parallel solution that are not in the sequential computation c) Which of these can you identify in the above "parallel pair-wise summation" algorithm?

          Homework #5
Due: Wednesday, Sept. 23 at 5 PM
5. There is a "paradigm shift" making parallel programming conceptually different from sequential
programming. A simple example is summing an array x containing n elements.
Sequential Algorithm:
Algorithm
sum = 0;
for (i = 0; i < n; i++) {
sum = sum + x[i];
} // end for
Parallel Pair-Wise Summation
a) How long would each algorithm take?
b) How many processors does the pair-wise summation algorithm utilize?
We can categorize sources of overhead in parallel programs that limit speedup as follows:
interprocess communication/interaction - processors need to communicate data (i.e., intermediate results)
idle processors - processors can be idle for a variety of reasons:
> load imbalance - a processor is assigned less work than others so it sits idle waiting of others to
finish
synchronization - processor need to to coordinate their operations (e.g., barrier synchronization) so
processors done sooner must wait for others to complete
> non-parallelizable computation/task - some serial component that cannot be done in parallel.
Amdahl's law applies here.
parallelization overhead - additional costs in the parallel solution that are not in the sequential computation
c) Which of these can you identify in the above "parallel pair-wise summation" algorithm?

Homework #5
Due: Wednesday, Sept. 23 at 5 PM
5. There is a "paradigm shift" making parallel programming conceptually different from sequential
programming. A simple example is summing an array x containing n elements.
Sequential Algorithm:
Algorithm
sum = 0;
for (i = 0; i < n; i++)
sum = sum + x[i];
// end for
Parallel Pair-Wise Summation
a) How long would each algorithm take?
b) How many processors does the pair-wise summation algorithm utilize?
We can categorize sources of overhead in parallel programs that limit speedup as follows:
interprocess communication/interaction - processors need to communicate data (i.e., intermediate results)
idle processors - processors can be idle for a variety of reasons:
> load imbalance - a processor is assigned less work than others so it sits idle waiting of others to
finish
synchronization - processor need to to coordinate their operations (e.g., barrier synchronization) so
processors done sooner must wait for others to complete
> non-parallelizable computation/task - some serial component that cannot be done in parallel.
Amdahl's law applies here.
parallelization overhead - additional costs in the parallel solution that are not in the sequential computation
c) Which of these can you identify in the above "parallel pair-wise summation" algorithm?

Added by Carlos P.

Question

Please give Ace some feedback