Reply

Performance: Understanding Amdahl's Law

At 11:44 PM on Nov 8, 2006, R.J. Lorimer wrote:

Scaling Up

Where I work we recently rolled out a product to be in a highly-concurrent production environment for the first time. Obviously we had several concerns. Was our testing good enough? Did we migrate data properly? And perhaps most important to this discussion: Is the application going to perform well?

We took several precautions before release to try to discover the practical and theoretical limits of our application performance through load testing and extensive profiling, but as with any release you can only do so much, and you always feel you may have missed something. Thankfully, the product rolled out and so far we seem to be running well within the acceptable limits of the hardware and user expectations.

The idea of performance for us (and for most server-based enterprise applications) is really how well our application scales. A large variable for our team is how big the user base could be when we roll out. We had some idea, but there were several indications to believe that our estimates were rough at best. Because of that, we needed to know how well we could grow our application should the need arise. This is where the little mathematical gem Amdahl's Law comes in.

Geeky Stuff

Amdahl's law (for the scope of this tip) calculates the magnitude of theoretical speed improvements that can be achieved for a given process by having more concurrent processors available(or parallelism). Say, for instance, that the number of processors was denoted by 'N'. To calculate the improvements with Amdahl's law, we need one other value, typically referred to as the 'sequential' or 'serial' fraction (and usually denoted by 'F'). Given those two values, the formula is:

1 / (F+(1-F)/N)

The 'sequential' fraction of a process (F) is how much of the process cannot be done in parallel to all other processes of the same application. Consider, for instance, time spent in a synchronized block that all processors must lock on (such as a synchronized collection, like a Vector). As a very simple example, consider this code:

public void method() {
 int value1 = complexComputationA();
 synchronized(lock) {
  int value2 = globalComputation(value1);
 }
 int value3 = complexComputationB(value2);
}

In this code, complexComputationA and complexComputationB are fully parallel (assuming they don't do anything requiring synchronization and non-CPU resources internally). By parallel I mean that 10 CPUs could work on complexComputationA at the same time independent of each other, getting 10 invocations of that method done 10x as fast as one CPU could. On the other hand, retrieving the lock for the synchronization (context switching) and executing the globalComputation is serial or sequential in nature because only one CPU can run it at a time; all of the other CPUs will be waiting on the lock.

Of course, application monitors/locks are not the only place where sequential processing is forced; also consider for example limited I/O resources (file locks, etc), as well as remote system communication (DB table and row locks).

All that being said, calculating the sequential percentage of your program is difficult. Indeed, while I would have liked to have those numbers for our application, it wasn't practical. Aside from the high-level complexity of our program, there are several components working outside our realm of understanding and control (such as the application server, web server, and database). All of these things make the exact usage of Amdahl's law (in parallel computing) very difficult. It's not common to apply Amdahl's law directly anyway; instead it's really a matter of understanding what it means about points of contention, and applying those rules in your application architecture and deployment.

Applying Some Numbers

When you begin applying values to Amdahl's law, you will quickly discover that even small degrees of sequential code dramatically impact the value of multiple processors. Let's list some numbers:

F (Percent of Sequential Code)	N (Processors)	Improvement (as a factor)
10% (.1)	5	3.57
10% (.1)	10	5.26
10% (.1)	20	6.90
10% (.1)	100	9.17
10% (.1)	100,000	9.99 (~10)
25% (.25)	5	2.50
25% (.25)	10	3.08
25% (.25)	20	3.48
25% (.25)	100	3.88
25% (.25)	100,000	3.99 (~4)
40% (.40)	5	1.92
40% (.40)	10	2.17
40% (.40)	20	2.33
40% (.40)	100	2.46
40% (.40)	100,000	2.50

As you can see, the amount of serial code you have has a dramatic effect on the ability to scale your program by throwing processors at it. There are a few things to realize from this:

1. Reduction of single-resource contention is generally a very good thing for scalability
2. As the amount of sequential code increases, the maximum advantage can be achieved with fewer and fewer processors - in other words, highly serial code is improved less and less for each processor that is added to it.
3. These factors are maximum or ideal numbers; in reality because of the context-switching costs and other various overhead, in practice, it is not likely these numbers will be achieved.

Real-World Application

Once you have a grasp for the importance of managing contention, you can begin to apply this knowledge to the options you may have. For instance, it is common to have multiple application servers running on the same database. While the database contention is the same (because we only have one DB, and hence one lock in the way), the multiple servers mean that we'll have split contention across the CPUs.

So, let's imagine we have two servers with 2 CPUs each. The application code (running on each server) has 10% contention in it (call this F1), and the database has 5% contention in it (call this F2). With all of this, we can calculate our total sequential percentage based on the number of servers:

F = F1/2 + F2
F1/2 =.1 / 2= .05 
(since F1 is aggregated across each server, the total 
contention on that lock is divided by the number of servers)
F = .05 + .05 = .1 (10%)

So while a single server on the database would have 15% contention, adding an extra server (and distributing part of the contention) effectively reduced the contention to 10% for the application. This is just an example of how understanding Amdahl's law can help you answer how your application will respond to topology changes and application layout changes.

While understanding this law is just a piece of the puzzle, it can help you see the big picture of the application.