views:

3258

answers:

7

Hi,

I've been asked to measure the performance of a fortran program that solves differential equations on a multi-CPU system. My employer insists that I measure FLOP/s (Floating operations per second) and compare the results with benchmarks (LINPACK) but I am not convinced that it's the way to go, simply because no one can explain to me what a FLOP is.

I did some research on what exactly a FLOP is and I got some pretty contradicting answers. One of the most popular answers I got was '1 FLOP = An addition and a multiplication operation'. Is that true? If so, again, physically, what exactly does that mean?

Whatever method I end up using, it has to be scalable. Some of versions of the code solve systems with multi-million unknowns and takes days to execute.

What would be some other, effective, ways of measuring performance in my case (summary of my case being 'fortran code that does a whole lot of arithmetic calculations over and over again for days on several hundred CPUs)?

Thanks,

-C.

+1  A: 

A FLOPS is, as you said, a floating-point operation per second. As an example, if you take exactly one second for an operation (such as adding, subtracting, multiplying or dividing two values and returning the result), your performance is simply 1 FLOPS. A recent CPU will easily achieve several GigaFLOPS, i.e. several billion floating-point operations per second.

Sören Kuklau
A: 

Your employer is right.
The only way to measure effectiveness of your Fortran program (or of any other program, btw) is to test it against standard benchmarks, if they exist.

And, about FLOPs, it stands for "floating point operations per second" - see the definition on Wikipedia.

friol
+14  A: 

It's a pretty decent measure of performance, as long as you understand exactly what it measures.

FLOPS is, as the name implies FLoating point OPerations per Second, exactly what constitutes a FLOP might vary by CPU. (Some CPU's can perform addition and multiplication as one operation, others can't, for example). That means that as a performance measure, it is fairly close to the hardware, which means that 1) you have to know your hardware to compute the ideal FLOPS on the given architecture, and you have to know your algorithm and implementation to figure out how many floating point ops it actually consists of.

In any case, it's a useful tool for examining how well you utilize the CPU. If you know the CPU's theoretical peak performance in FLOPS, you can work out how efficiently you use the CPU's floating point units, which are often one of the hard to utilize efficiently. A program which runs 30% of the FLOPS the CPU is capable of, has room for optimization. One which runs at 70% is probably not going to get much more efficient unless you change the basic algorithm. For math-heavy algorithms like yours, that is pretty much the standard way to measure performance. You could simply measure how long a program takes to run, but that varies wildly depending on CPU. But if your program has a 50% CPU utilization (relative to the peak FLOPS count), that is a somewhat more constant value (it'll still vary between radically different CPU architectures, but it's a lot more consistent than execution time).

But knowing that "My CPU is capable of X GFLOPS, and I'm only actually achieving a throughput of, say, 20% of that" is very valuable information in high-performance software. It means that something other than the floating point ops is holding you back, and preventing the FP units from working efficiently. And since the FP units constitute the bulk of the work, that means your software has a problem.

It's easy to measure "My program runs in X minutes", and if you feel that is unacceptable then sure, you can go "I wonder if I can chop 30% off that", but you don't know if that is possible unless you work out exactly how much work is being done, and exactly what the CPU is capable of at peak. How much time do you want to spend optimizing this, if you don't even know whether the CPU is fundamentally capable of running any more instructions per second?

It's very easy to prevent the CPU's FP unit from being utilized efficiently, by having too many dependencies between FP ops, or by having too many branches or similar preventing efficient scheduling. And if that is what is holding your implementation back, you need to know that. You need to know that "I'm not getting the FP throughput that should be possible, so clearly other parts of my code are preventing FP instructions from being available when the CPU is ready to issue one".

Why do you need other ways to measure performance? What's wrong with just working out the FLOPS count as your boss asked you to? ;)

jalf
Thanks for the help! I didn't know CPU architectures had set FLOP rate values.
caglarozdag
Well, they don't. What they do have is clear limits on how long each type of instruction takes, and how often one can be issued (and how many of them can run in parallel). From that, you can derive the theoretical peak FLOPS.
jalf
And per jalf's last comment, keep in mind that getting peak FLOPS out of a CPU is very hard, because it implies that your computation is structured in such a way as to get full FP issue every cycle. This is not always the case with real applications, but it does give you an idea of how much potential performance improvement you can get if your code is compute-limited. If you want more on how FLOPS are measured for supercomputers, look at the way Top500.org does it: http://www.top500.org/faq. They explain their benchmarks on that page.
tgamblin
@caglarozdag: as @tgamblin says, you can generally forget about reaching peak FLOPS on any CPU. It just won't happen. In most applications I've seen, you should pat yourself on the back if you reach 50% of the CPU's theoretical peak FLOPS. Maybe you'll be able to hit 70% but then you really should consider yourself lucky. But if you're running at 10% (which will be the case surprisingly often), there's probably some room for improvement.
jalf
A: 

I don't think measuring FLOPS will be very useful.

The number of FLOPS achieved will tell you how busy your algorithm is keeping the CPU, but won't tell you how well your algorithm itself is performing.

You may find two different algorithms which cause the processor to perform the same number of FLOPS but one provides you with the desired result in half the time.

I think you'd be better off looking at a much 'higher level' statistic such as the number of differential equations solved per unit of time (that is, after all, the purpose of your algorithm).

On the other hand, measuring the number of FLOPS achieved may help you to improve your algorithm as it will tell you how busy you are keeping the CPU.

Chris Roberts
FLOPS shows you how far your current implementation is from an optimal implementation *of the same algorithm*. Yes, if you know of a more efficient algorithm, you should use that, but hopefully you're already using the best known algorithm, and then FLOPS matters in optimizing that. Yes, it's useful
jalf
+1  A: 

"compare the results with benchmarks" and do what?

FLOPS means you need

1) FLOPs per some unit of work.

2) time for that unit of work.

Let's say you have some input file that does 1,000 iterations through some loop. The loop is a handy unit of work. It gets executed 1,000 times. It takes an hour.

The loop has some adds and multiplies and a few divides and a square root. You can count adds, multiplies and divides. You can count this in the source, looking for +, * and /. You can find the assembler-language output from the compiler, and count them there, too. You may get different numbers. Which one is right? Ask your boss.

You can count the square roots, but you don't know what it really does in terms of multiplies and adds. So, you'll have to do something like benchmark multiply vs. square root to get a sense of how long a square root takes.

Now you know the FLOPS in your loop. And you know the time to run it 1,000 times. You know FLOPS per second.

Then you look at LINPACK and find you're slower. Now what? Your program isn't LINPACK, and it's slower than LINPACK. Odds are really good that your code will be slower. Unless your code was written and optimized over the same number of years a LINPACK, you'll be slower.

Here's the other part. Your processor has some defined FLOPS rating against various benchmarks. Your algorithm is not one of those benchmarks, so you fall short of the benchmarks. Is this bad? Or is this the obvious consequence of not being a benchmark?

What's the actionable outcome going to be?

Measurement against some benchmark code base is only going to tell you that you're algorithm isn't the benchmark algorithm. It's a foregone conclusion that you'll be different; usually slower.

Obviously, the result of measuring against LINPACK will be (a) you're different and therefore (b) you need to optimize.

Measurement is only really valuable when done against yourself. Not some hypothetical instruction mix, but your own instruction mix. Measure your own performance. Make a change. See if your performance -- compared with yourself -- get better or worse.

FLOPS don't matter. What matters is time per unit of work. You'll never match the design parameters of your hardware because you're not running the benchmark that your hardware designers expected.

LINPACK doesn't matter. What matters is your code base and the changes you're making to change performance.

S.Lott
I believe LINPACK solves a matrix system (a somewhat arbitrary problem the developers of LINPACK chose at the time) and its a coincidence that our algorithm has essentially the same purpose. I think my boss realizes it's going to be slower than LINPACK, just wants to see how much slower.
caglarozdag
FLOPS is very useful for one specific purpose: That of measuring utilization of the CPU's FP unit. And since that is generally fairly hard to utilize efficiently, FLOPS is useful info for HPC stuff. It tells you your program's structure prevents efficient utilization of the most vital CPU resource.
jalf
+7  A: 

I'd just like to add a couple of finer points:

  • division is special. Since most processors can do an addition, comparison, or multiplication in a single cycle, those are all counted as one flop. But division always takes longer. How much longer depends on the processor, but there's sort of a defacto standard in the HPC community to count one division as 4 flops.

  • If a processor has a fused multiply-add instruction that does a multiplication and an addition in a single instruction -- generally A += B * C -- that counts as 2 operations.

  • Always be careful in distinguishing between single-precision flops and double-precision flops. A processor that is capable of so many single-precision gigaflops may only be capable of a small fraction of that many double-precision gigaflops. The AMD Athlon and Phenom processors can generally do half as many double-precision flops as single precision. The ATI Firestream processors can generally do 1/5th as many double-precision flops as single precision. If someone is trying to sell you a processor or a software package and they just quote flops without saying which, you should call them on it.

  • The terms megaflop, gigaflop, teraflop, etc. are in common use. These refer to factors of 1000, not 1024. E.g., 1 megaflop = 1,000,000 flop/sec not 1,048,576. Just as with disk drive sizes, there is some confusion on this.

Die in Sente
Thanks for the useful info!
caglarozdag
A: 

I would just try to make it go as fast as possible, and that requires finding out where it is spending time, especially if there are function calls that could be avoided.

I do this by the simple method of just interrupting it a few times while it is running, and seeing what it is doing. Here are the kinds of things I find:

  • Much of the time it is in the process of computing the derivative and/or Jacobian. Much of this time can go into math function calls such as exp(), log(), and sqrt(). Often these are repeated with identical arguments and can be memo-ized. (Massive speedup.)

  • Much of the time is spent calculating derivatives too many times because the integration tolerances are tighter than necessary. (Faster)

  • If an implicit integration algorithm (such as DLSODE Gear) is being used because the equations are thought to be stiff, chances are they are not, and something like Runge-Kutta could be used. (DVERK). (Faster still)

  • Possibly a matrix-exponent algorithm could be used if the model is linear (DGPADM). This is a big win both for performance and precision, and is immune to stiffness. (Way faster)

  • Higher up the call-stack, it could be that the same integrations are being performed repeatedly with slightly different parameters, so as to determine a forward or central-difference gradient of the solution with respect to those parameters. If the differential equations are themselves differentiable, it may be possible to get those gradients analytically, or by augmenting the equations with sensitivity equations. This is not only much faster, but much more precise, which can speed things up still higher up the stack.

You can look at each level of the stack as an opportunity to find things to optimize, and the speedups will compound. Then when you go to multi-cpu, assuming it is parallelizable, that should provide its own multiplicative factor.

So back to FLOPs. You could try to maximize FLOPs / second, but it can also be much more useful to minimze FLOPs / run, by optimizing at all levels of the stack. In any case, just measuring them tells you almost nothing.

Mike Dunlavey