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?


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$ – Niklas R. Feb 24 '18 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$ – user1118321 Feb 24 '18 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$ – Raphael Feb 24 '18 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$ – Raphael Feb 24 '18 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$ – Niklas R. Feb 24 '18 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.