Determining efficiency in MFLOPS/s of a parallel program

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.