Leibson's Law

Sam Williams, a PhD student working under UC Berkeley’s Professor and Processor Guru Dave Patterson, gave a polished Hot Chips talk on a metric that allows undergrads (and, in my mind, overly busy design engineers) to determine when they’ve sufficiently optimized software to run on multicore parallel processors. Note that this model is about optimization, not writing correct parallel programs. "If you can't write a correct parallel program," said Williams, "you shouldn't be worried about optimizing it." 

William's concept is called the “Roofline Model” and I thought about summarizing it here, but I’d need a blog entry the length of the presentation to do it. So go get a copy yourself on Williams’ Web page.

Essentially, the Roofline model tries to pair information about a multicore processors maximum FLOPS performance with information about the “arithmetic intensity” of the problem at hand. The arithmetic intensity is simply the number of FLOPS needed divided by the number of bytes that must be transferred to solve the problem. It’s a measure of the problem’s balance between computation and data movement. Different problems have different algorithmic intensities.

Together, the maximum available FLOPS performance and the performance of the processor at different algorithmic intensities creates a maximum-performance curve. No amount of program optimization can exceed this curve. Once you hit this curve, there’s no point in trying to optimize further because you can’t get any more performance out of the processor. Here’s a curve for an 8-processor multicore system based on Intel’s Xeon processor.

The curve shows the maximum achievable performance in the upper curve. It also shows what’s achievable if you start to omit certain optimizations such as the use of SIMD instructions and heavy use of instruction-level parallelism. Using this model and an estimation of a program’s arithmetic intensity, you can quickly determine the expected performance from this multicore processing system, as shown below.

I recommend this paper to you.