# Determining efficiency in MFLOPS/s of a parallel program

I am running some scientific (parallel) code and would like to obtain some performance profiling measurements. I want to obtain the "efficiency" of the code in terms of flops/s over theoretical (peak) performance.

I ran a simple matrix multiplication example (PAPI_flops.c which can be found on the web) and got the measurements using PAPI measurement counts. The HPC system (56 Gb/s interconnect) I used has this cpuinfo:

processor   : 39
vendor_id   : GenuineIntel
cpu family  : 6
model       : 62
model name  : Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz
stepping    : 4
microcode   : 1064
cpu MHz     : 1200.000
cache size  : 25600 KB
physical id : 1
siblings    : 20
core id     : 12
cpu cores   : 10
apicid      : 57
initial apicid  : 57
fpu     : yes
fpu_exception   : yes
cpuid level : 13


Let A and B be 1000x1000 matrices with randomized floats. For a serial process, I get the following metrics after multiplying A by B:

Real_time:  3.340896
Proc_time:  3.344447
Total flpins:   2837232042
MFLOPS:     848.341187


Now, from what I understand, the theoretical peak performance would be #cores x clock x FLOPs/cycle. I believe the above processor can do 4 FLOPs/cycle, so if I were to assume that I had a single-core 2.8 GHz processor, the theoretical performance would be about 11200 MFLOPS. Which would give me about 7% efficiency...

That is an extremely low efficiency rate. 850 MFLOPS seems to be a pretty good and high performance rate to me. Am I doing something wrong here, or is this expected for something as simple as matrix multiplication?

• This "theoretical peak performance" is a myth; it can never be attained, probably not even close. I don't think the field has a single good, accepted solution; maybe try running an algorithm that has been accepted as efficient and compare with that. – Raphael Feb 18 '15 at 8:31
• I think this question may be better at home on Computational Science. – Raphael Feb 18 '15 at 8:32

The factor you miss is that when you do matrix-matrix multiplications, you have to reload data from memory. Since your matrices are big enough that they won't fit into the cache, you access main memory which is incredibly slow compared to a floating point operation. To give you an idea how slow: a floating point multiplication on a typical processor today takes 1.5ns, while loading a floating point number from main memory takes 60-100ns.

In other words, the floating point performance of your chip does not matter for matrices of size 1000-by-1000. It is all about the memory bandwidth and latency.

• It's important to point out that cache aware algorithms can gain efficiency by reusing data that has been brought into cache from memory. This means that the way in which the matrix multiplication is coded can have a huge impact on performance. – Brian Borchers Feb 18 '15 at 16:09
• Sure, you can block it and do much better than the usual triple loop over all $i=1,\ldots,N$ but I don't think we can still make the whole thing be CPU-limited. I think whichever way you do it, it's going to be memory limited, and that problem isn't going to go away anytime soon either. – Wolfgang Bangerth Feb 18 '15 at 23:34
• I agree that the number of floating operations isn't the limiting factor- I was just making the point that a good cache aware algorithm can dramatically improve the performance and that people shouldn't be using the naive algorithm. – Brian Borchers Feb 19 '15 at 1:59
• Yes, definitely correct! :-) – Wolfgang Bangerth Feb 19 '15 at 2:15

For dense matrices or order $n$, the theoretical number of FLOPS required for matrix product is $2n^3$. In your case, since you are multiplying two matrices of order 1000, the number of FLOPS should be, in MFLOPS, 2000. Therefore, the 848.3 MFLOPS performance of your code is less than 50% of the theoretical performance for matrix multiplication.

Scaling $n$, you should see (or at least expect) better performances if you are using a good multiplication algorithm (a recursive, cache-aware algorithm fares much better than the ordinary algorithm relying on the matrix multiplication formula from linear algebra).

However, it's worth noting here that FLOP counting is just a crude estimate of performance: when you use it to evaluate a program's efficiency, you are obviously ignoring a lot of overhead factors affecting program's execution. Therefore, FLOP counting can only capture one specific dimension of a program's efficiency.

• I think this answer completely misses the point that on modern processors counting FLOPS is meaningless since FLOPS are so cheap compared to memory accesses. – Wolfgang Bangerth Feb 18 '15 at 16:10
• I completely agree with Wolfgang, but also aren't your units wrong? The author reported a total of 2.8e9 instructions where $2n^3$ gives 2e9, yet you compare that with flops per second. Besides, that's not at all what theoretical performance means, it is theoretical relative to idealized execution of instructions on the CPU, not the total number of flops required. – Kirill Feb 18 '15 at 21:35

Since Intel Westmere, you cannot use the hardware performance counters to measure flops like we think of them accurately. The counter counts operations issued not executed or retired. Thus, if you need to load some data from memory and there is a stall waiting for it to come back, the instruction may be re-issued many times before it completes. We've seen overcounts as high as 10x on E5-2650 v1 (i.e. SandyBridge), and the same is true for IvyBridge and Haswell. If you want to count flops, you have to count them by hand in your routines instead of using the hardware counters.