When parallelizing an application, the ideal speedup is the speeding up by the n

Question

When parallelizing an application, the ideal speedup is the speeding up by the number of processors. This is limited by two things: percentage of application that can be parallelized and the cost of communication among processors. Assume 80% of the application is parallelizable

a. What is the speedup with 4 processors, ignoring the cost of communication?

b. What is the speedup with 4 processors if, for every processor added, the communication overhead is 0.5 % (0.005) of the original execution time.

c. What is the speedup with 8 processors if, for every time the number of processors doubled, the communication overhead is increased by 0.5 % (0.005) of the original execution time.

Explanation / Answer

a) The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program. For example, if a program needs 20 hours using a single processor core, and a particular portion of the program which takes one hour to execute cannot be parallelized, while the remaining 19 hours (95%) of execution time can be parallelized, then regardless of how many processors are devoted to a parallelized execution of this program, the minimum execution time cannot be less than that critical one hour. Hence the speedup is limited to at most 20

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.