I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and the parallel part takes y-x seconds. Can I then safely assume that it is the same percentage of the time that is parallel for different number of CPU:s or will that vary with different number of CPU:s?
$\begingroup$
$\endgroup$
0
asked Feb 24, 2018 at 11:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
You can never assume anything.
There are plenty of cases where your work, or a percentage of your work, can be split up into k independent tasks. If you have k processors, then each one can handle one task. If you have k+1 processors, then one will be unused. So it's not just a matter of "percentage of work that can be parallelised", it's also a a matter of "how many parallel tasks can be performed".
There are plenty of cases where work can be parallelised, but work needs to be done to prepare for this. Let's say it takes time t to prepare for one parallel execution, independent of the amount of work. So with two processors, that preparation takes 2t. With 100 processors, it takes 100t. If the amount of work is fixed, there will be a point where more processors add more preparation time than the savings you get.
There are plenty of cases where there is a simple sequential solution, and a more complex and slower parallel solution. The total time using one processor and the sequential solution may be x. To use k processors may save y of the sequential time, but add f (k) sequential time for preparation, and use g (k, y) in total parallel time where g (k, y) >> y.
-
$\begingroup$ Are you sure that the Berkeley professor is wrong when he gives us these assumptions? "Assume that your observations about 4 cores can be applied to 16 cores." $\endgroup$ Commented Feb 24, 2018 at 16:51
-
$\begingroup$ If your professor says you are allowed to make those assumptions, then they probably have a particular scenario in mind where that applies. But in the general case, that assumption does not hold. $\endgroup$ Commented Feb 24, 2018 at 17:30
-
1$\begingroup$ @NiklasRosencrantz Professors are wrong all the time. That said, the quote you give is a simplifying assumption, though, for the purpose of the exercise. That already suggests that the statement is probably not true. $\endgroup$– RaphaelCommented Feb 24, 2018 at 18:58
-
$\begingroup$ @NiklasRosencrantz You should have given the quote and the reference in your question; how were we to know that you were working of a simplifying problem statement and not your own ideas? $\endgroup$– RaphaelCommented Feb 24, 2018 at 18:58
-
$\begingroup$ @Raphael This is my final exam before a B.Sc. in comp sci. I don't yet have that level where I could glance a problem and know it. $\endgroup$ Commented Feb 24, 2018 at 22:55