Solving the Table Maker's Dilemma on Current SIMD Architectures

Correctly-rounded implementations of some elementary functions are recommended by the IEEE 754-2008 standard, which aims at ensuring portable and predictable floating-point computations. Such implementations require the solving of the Table Maker's Dilemma which implies a huge amount of computation time. These computations are embarrassingly and massively parallel, but present control flow divergence which limits performance at the SIMD parallelism level, whose share in the overall performance of current and forthcoming HPC architectures is increasing. In this paper, we show that efficiently solving the Table Maker's Dilemma on various multi-core and many-core SIMD architectures (CPUs, GPUs, Intel Xeon Phi) requires to jointly handle divergence at the algorithmic, programming and hardware levels in order to scale with the number of SIMD lanes. Depending on the architecture, the performance gains can reach 10.5x over divergent code, or be constrained by different limits that we detail.