Changing a program to parallelize it can help shrink execution time of a program
ID: 3737691 • Letter: C
Question
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.
Evaluate the maximum overall speedup possible by using GPU-10?
c) [15 points] When you talk to the hardware vendor, she suggests using GPU-25 instead of GPU-10. At first glance, GPU-25 would be better since it is 25 times faster than the original CPU. However, GPU-25 is harder to effectively parallelize.
Calculate the fraction of the original code that must be parallelized if using GPU-25 to match the speedup of GPU-10.
d) [15 points] Based on your answers to part b) and c), which GPU model do you recommend and why? Is there any additional information needed for a recommendation?
Explanation / Answer
Amdahl's Law gives therotical maximum theorotical speedup it is very hard to achieve. The actual speed-ups are always less than the speed-up predicted by Amdahl's Law.
Amdahl's Law was first described by Gene Amdahl in his 1967 paper titled "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities". the statement is :
If F is the fraction of a calculation that is sequential, and (1-F) is the fraction that can be parallelised, then the maximum speed-up that can be achieved by using P processors is 1/(F+(1-F)/P).
a] 1/(F+(1-F)/P). this is the maximum overall speedup that can be achieved only by parallelizing the program. where
(1-F) is the fraction that can be parallelised and F is the fraction of a calculation that is sequential .
so in above situation 35% is parrellelism i.e. (1-F) = 0.35
hence f = 0.65
= 1/(F+(1-F)/P)
= 1/(0.65 + (0.35)/P)
B] an engineer in your team proposes to run the software program on a dedicated gpu.He recommends using the gpu10 model which is 10 times faster than the normal CPU the software runs on. GPU-10 can fully use software parallelism.
ans => It is difficult to find a program that can be fully parallel In scientific computing there are some example of program like computing the summation of a set of number. The number can be equally shared on the processors. Thus, each processor will produce a partial sum. However, still at the end only a reduced set of processors will be required to aggregate the partial results. 100% parallelism will also mean all the libraries used in a program are parallel. But as I said, not all tasks can be done in parallel. There are job that can be run only sequentially. if you have a parallel algorithm, it might not work beyond a certain level of parallelism.
C]Gpu25 may faster than gpu10 but it is about hardware parellellism but it is still difficult to achive.
in gpu25 because of increase in GPU hardware Parellelism even when the program is executing in the parallel parts of the code, it is unlikely that all of the processors will be computing all of the time as some of them will likely run out of work to do before others are finished their part of the parallel work. This is called the straggler problem because some of the processors are straggling behind when others have finished their work.
D] by above all answers i will recommend you GPU25 because it is easy to achive hardware parellelism than software parellelism. if you afford to bye hardware parellel system then it is better to buy hardware parellel system.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.