1. Changing a program to parallelize it can help shrink execution time of a prog

Question

1.    Changing a program to parallelize it can help shrink execution time of a program significantly. Suppose that you’re analyzing a hypothetical software program written such that 35% is parallelizable.

a) [10 points] What is the theoretical maximum overall speedup that can be achieved only by parallelizing the program?

b) [10 points] An engineer in your team proposes to run the software program on a dedicated Graphical Processing Unit (GPU). He recommends using the GPU-10 model which is 10 times faster than the normal CPU the software runs on. GPU-10 can fully exploit the available software parallelism.

Explanation / Answer

Solution :-

Parallelizing a program reduces the execution time of the program. Some programs and softwares contain some part sequential and rest is parallelized. So the execution time is reduced for the execution of parallel part of program.

Given that a hypothetical software is 35% parallelized and 65% is sequential.

(a) By the Amdahl law if the sequential part is X, and parallelized part is 1-X then the speedup on n processors is

= 1/(X+(1-X)/n)

So we have parallelized part is 35% and sequential part is 65% then X= .65 and 1-X = .35

so speedup on single processor is

= 1/(.65+(.35))

=1/1

=1

So if only part of program is parallelized and executing on single processor then there is no theoretical speedup. The program execution takes same time on single processor whether parallelized or not.

(b) Now if for the same case if 10 processors used in place of single. Then the speedup by the Amdahl law is as follows-

= 1/(.65+(.35)/10)

= 1.459

So by the Amdahl law the speedup factor is 1.459 calculated. It means theortically the program runs 1.45 times faster on 10 processors if the 35% part of program is parallelized.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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