7

Are there benchmarks for how many multiplications of various integer types compared to floating point types can be achieved per second on modern CPUs?

I'm trying to get some hint if it would be worth to make a c implementation of an integer arithmetics algorithm. I.e. would there be speed gains to be had on modern CPUs compared to iterative floating point arithmetic methods.

For those curious about the algorithm: This answer inspired me to write a question which lead to the idea of doing matrix monomials over integer vectors to approximate roots of polynomials over more complicated fields. For example finding integer roots of quaternions representing 3 dimensional rotations. "Which operation if I apply it N times becomes this rotation?" The simplest solution is probably a rotation.

Community
  • 1
mathreadler
  • 380
  • 4
  • 15
  • 1
    FPUs are now really fast, especially if your compiler can generate vectorized instructions (SSE, AVX etc...), in many cases floating point operations cost virtually nothing, but so many things are involved that nothing replaces practical implementation (implement both, use a stopwatch to compare). – BrunoLevy Jun 10 '16 at 20:12
  • You indicate below that you have some specific algorithm in mind. It would be interesting to know which. – Carl Christian Jun 11 '16 at 00:06

1 Answers1

4

In general, the answers is no.

Modern CPU's excel at problems which have high arithmetic intensity and are implemented using floating point arithmetic.

A few figures will help explain the discrepancy.

On the Haswell chip the MULPS instructions performs 8 single precision floating point multiplications. The latency is 5 CPU cycles and the reciprocal throughput is 0.5. This means that your have to wait 5 cycles for first instruction to complete, but if you have a stream of independent operands, then you can eventually retire 2 instruction pr. cycle. This yields a peak rate of 16 single precision multiplications pr. cycle. In comparison the IMUL instruction multiplies a single pair of 32 bit integers. The latency is 3 cycles and the reciprocal throughput is 1. If you have a stream of independent operands, then the peak rate is 1 multiplication pr. cycle.

Achieving the peak flop rate it only possible for a few very specialized types of computations, such as doing inner products on vectors which fit in the L1 cache on a single core. Matrix-matrix multiply, the kernel for all blocked implementations of Gaussian elimination frequently achieves 70-80% of the theoretical peak on the Top500 computers.

Sparse arithmetic typically has a very low arithmetic intensity and is incompatible with modern computer architecture. Computers on the Top500 list execute the sparse benchmark (Conjugate Gradient) at about 2% of the peak flop rate. The best computer on the list does does less than 20%.

You can make some sparse algorithms run at a high fraction of the peak flop rate, but it requires extremely aggressive optimizations which are tailored to the specific task at hand. Attempting to boost the computational speed with integer computations will just lower the arithmetic intensity even further.

It is possible to increase the accuracy of, say, double precision floating point calculations by clever algorithms which return the result, as if it had been computed using a smaller unit round off error, and then rounded to double precision. If extreme accuracy is required, then this approach is far more likely to be successful.

Carl Christian
  • 1,391
  • 11
  • 16
  • 4
    Your conclusions may be correct but I don't think it is fair to compare an SSE floating point multiply instruction with a scalar integer instruction. I would have found it much more interesting (and fairer) if you had compared comparable AVX2 vector floating point and integer multiply instructions on the Haswell architecture. – Bill Greene Jun 10 '16 at 21:32
  • I was wondering if there existed some integer counterpart for the SSE / vector instructions. This was not thought for an algorithm related to huge sparse matrices, but all data will rather be within 1kB so will probably hit on tiniest cache all the time and in extreme cases even registries could suffice. Sparse matrix operation performance depend mostly on wise vectorization choices, memory layout and locality. If you have locality in memory for operations which you decide to perform consecutively you will still hit the cache a lot. Anyway thanks for the answer. – mathreadler Jun 10 '16 at 21:47
  • @BillGreene: You do have a good point, but say we run SSE integer multiplications. To cover the same representable range as single precision we will need several dependent integer multiplications and additions. We will be hit by the full latency every time. I really do not see a good way out of this. – Carl Christian Jun 11 '16 at 00:04
  • If that is what one needs for capability in the algorithm, then one would probably not consider integer arithmetic to start with. – mathreadler Jun 11 '16 at 12:52