2010 · 12 citations · 9 references
Mathematical ProgrammingEngineeringMeasurementAccuracy And PrecisionAnalysis Of AlgorithmComputational ComplexityEmpirical AlgorithmicsParallel MetaheuristicsCalibrationUncertainty QuantificationParallel Complexity TheoryApproximate ComputingParallel ComputingCombinatorial OptimizationRelaxed Time ConstraintSummation AlgorithmsApproximation TheoryStatisticsAccuracy Versus TimeComputer EngineeringComputer ScienceAlgorithms EquivalentTemporal ComplexityParallel ProgrammingTime Perception
In this article, we focus on numerical algorithms for which, in practice, parallelism and accuracy do not cohabit well. In order to increase parallelism, expressions are reparsed, implicitly using mathematical laws like associativity, and this reduces the accuracy. Our approach consists in focusing on summation algorithms and in performing an exhaustive study: we generate all the algorithms equivalent to the original one and compatible with our relaxed time constraint. Next we compute the worst errors which may arise during their evaluation, for several relevant sets of data. Our main conclusion is that relaxing very slightly the time constraints by choosing algorithms whose critical paths are a bit longer than the optimal makes it possible to strongly optimize the accuracy.
9