Search code examples
linuxoperating-systemcpucpu-architectureparallelism-amdahl

How accurate is amdahl's law?


In computer architecture, Amdahl's law gives the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved.

Slatency is the theoretical speedup in latency of the execution of the whole task;

s is the speedup in latency of the execution of the part of the task that benefits from the improvement of the resources of the system;

p is the percentage of the execution time of the whole task concerning the part that benefits from the improvement of the resources of the system before the improvement.

Slatency = 1/[(1-p) + (p/s)]

It is all theoretical and it had me thinking, when is it inapplicable. And how accurate it is for estimating CPU performance ?


Solution

  • Often when you want to tune some part of a program, you make a microbenchmark to test just that in isolation.

    That doesn't always reflect how it will behave when run as part of the full program. (i.e. with other work between executions of the part you're tuning, instead of in a tight loop.)

    e.g. if you found sin(x) calculations were expensive and replaced them a lookup table, that might win in a microbenchmark, because a small-enough table stays hot in cache when called back-to-back with no other work in between. Similarly, microbenchmarks measure performance with branch-prediction primed, and with no code-cache pressure (which can make loop unrolling look better than it is).

    But that just means your estimate of s is wrong for the function as part of the whole program, not that Amdahl's law is inaccurate. That's just a case of using it wrong.


    However, this does lead to a real answer to your question:

    Speeding up one part of a program in a way that leads to more cache or TLB misses, branch mispredictions, etc. in other parts of the program does violate Amdahl's law.