What is "good" parallel scaling?

Question

I often hear the phrase "good" or "bad" parallel scaling/efficiency. What exactly do people mean when they say that?

For example, let $p = 1,\ldots 16$ be the number of processing elements, and A and B be parallel algorithms and consider weak parallel scaling.

If the efficiency of $A$ decreases linearly from $100\%$ (at $p=1$) to $30\%$ (at $p=16$), and the efficiency of B drops from $100\%$ (at $p=1$) to $20\%$ (at $p=2$), but stays constant at $20\%$ for $p=2,4,8,16$, which has better parallel scaling?

I have not seen this put in concrete terms before.

Thanks!

Answer 1

Good is a relative term, and it will depend on the nature of the problem, the nature of the algorithm, and properties of the hardware involved. The only absolute reference point is ideal scaling (100% efficiency).

You can claim your scaling is good if it is better than what anyone else has achieved for the same problem, or if it's "close" to ideal for large numbers of processors. For example, in this paper (disclaimer: citing my own work because it's what I'm most familiar with) we achieved about 95% efficiency weak scaling from 1 to 65K processes and claimed that was good. It was nothing exceptional given the algorithms and hardware involved, but we did avoid making any major mistakes that would have ruined the efficiency.

Both examples you give seem very poor for most problem domains. In the second example, you actually have anti-scaling -- when running with 2 or 4 processes at 20% efficiency, wall clock time will actually be greater than for a serial run. That's definitely bad scaling!

Answer 2

As mentioned already, there's no absolute definition for good scaling. All you can really have is some sense of whether or not the scalability your code achieves is better, worse or in line with whichever other codes doing the same sort of computation do achieve in similar environments.

Now, some computing centres sometimes (try to) enforce some rules to make sure their computing resources are used (not too in)effectively. For example, I remember of one of them for which, in order to be granted access, you had to propose a scalability curve for a typical use case of you code. From that, you would only be allowed to run up to a number of processes for which the parallel effectiveness of the code would be over 75%. This magic 75% efficiency threshold wouldn't mean that your code's scalability would be good when above, but simply that it would just be too bad below...

Answer 3

If you are looking for a general criterion, maybe linear scaling would be the 'ideal' scaling. Hence, I would say that the closer to a straight line your scaling is, the better it is.

Answer 4

For simplicity, let's assume A and B are solving the same problem. The speedup for alg B at 16 processor cores is about 4 whereas for A it is 3.

For general information, weak scaling means the amount of work per core is held constant so generally some aspect of problem size is increased in proportion to the number of processors. In this example, as the problem size and number of processors are increased, the amount of useful work done by each processor in both A and B decreases.

Alg A is "better" in the sense that time to solution for number of cores from 1 to 16 is always better than Alg B. Of course if the efficiency trends would continue then Alg B would be the 'better' choice at 18 cores and above. In fact, Alg B if scaling truly had a floor at 0.2, it might be very attractive for very large problems.

As other answers have pointed out, and efficiency of order 0.2 or 0.3 is generally considered poor though. My personal opinion is that time to solution is what matters and the best algorithm is the one that gets me the answer soonest within the constraint of available computational power. The question would be more interesting if there was a crossing in performance say if Alg A dropped to 10 % efficiency at 16 cores. There are simulation codes that have different parallel algorithms to choose from that are 'better' for different architectures or even different numbers of available cores. Parallelism always has a cost in communication and often enough also in greater numbers of floating point operations.