2014 · 15 citations · 9 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingAlgorithm AnalysisData ParallelismGraphics Processing Unit ArchitectureGraphics Processing UnitsHardware AccelerationParallel ArchitecturesCarry-save LogicComputational ReproducibilityFilteringFloating-point ArithmeticMany-core ProcessorsMulti-core ComputingMultiply-accumulate UnitsParallel Reduction
On modern multi-core, many-core, and heterogeneous architectures, floating-point computations, especially reductions, may become non-deterministic and thus non-reproducible mainly due to non-associativity of floating-point operations. We introduce a solution to compute eterministic sums of floating-point numbers efficiently and with the best possible accuracy. Our multi-level algorithm consists of two main stages: a filtering stage that uses fast vectorized floating-point expansions; an accumulation stage based on superaccumulators in a high-radix carry-save representation. We present implementations on recent Intel desktop and server processors, on Intel Xeon Phi accelerator, and on AMD and NVIDIA GPUs. We show that the numerical reproducibility and bit-perfect accuracy can be achieved at no additional cost for large sums that have dynamic ranges of up to 90 orders of magnitude by leveraging arithmetic units that are left underused by standard reduction algorithms.
9
Accuracy and stability of numerical algorithms
Choice Reviews Online · 1996 · 2.1K citations
Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre et al. · ACM Transactions on Mathematical Software · 2007 · 915 citations