Accurate Algorithms

The inner product is one of the most elementary algebraic operations and the basis for a large number of numerical applications and computations that are performed using binary floating-point arithmetic on computers. Depending on the condition of the input data, straight forward implementations of the inner product are very inaccurate and of limited use for verified computations. To overcome this issue, many algorithms have been developed in the past with different strengths and weaknesses. This project introduces new algorithms for summation and inner product computation, that make use of the FMA instruction, which will be part of upcoming state of the art computer instruction sets. The proposed algorithms scale well for vector lengths of about elements and more.

Contents:

• Introduction
• Binary floating-point arithmetic
  • Notation and encoding
  • Rounding
  • Fast exponent extraction
• The Fused-Multiply-Add operation
  • Specification
  • Hardware realization
  • Software and compiler support
  • Performance
• Accurate summation
  • Previous work
  • BucketSum
  • Benchmark
• Accurate inner product
  • Previous work
  • Algorithms based upon TwoProductFMA
  • Benchmark
• Conclusion
• Glossary
• References
• Appendix
  • Test system information
  • FMA test cases
  • FMA benchmark program
  • Bucket visualizations