Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2007 | Published
Book Section - Chapter Open

Optimistic Parallelization of Floating-Point Accumulation

Abstract

Floating-point arithmetic is notoriously non-associative due to the limited precision representation which demands intermediate values be rounded to fit in the available precision. The resulting cyclic dependency in floating-point accumulation inhibits parallelization of the computation, including efficient use of pipelining. In practice, however, we observe that floating-point operations are "mostly" associative. This observation can be exploited to parallelize floating-point accumulation using a form of optimistic concurrency. In this scheme, we first compute an optimistic associative approximation to the sum and then relax the computation by iteratively propagating errors until the correct sum is obtained. We map this computation to a network of 16 statically-scheduled, pipelined, double-precision floating-point adders on the Virtex-4 LX160 (-12) device where each floating-point adder runs at 296 MHz and has a pipeline depth of 10. On this 16 PE design, we demonstrate an average speedup of 6× with randomly generated data and 3-7× with summations extracted from Conjugate Gradient benchmarks.

Additional Information

© 2007 IEEE. Issue Date: 25-27 June 2007; Date of Current Version: 16 July 2007. This work was supported in part by DARPA under grant FA8750-05-C-0011 and the NSF CAREER program under grant CCR-0133102. Authors benefited from discussions with Jon Ramirez; these discussions and his implementation helped identify many important issues which the work here addresses.

Attached Files

Published - Kapre2007p907318Th_Ieee_Symposium_On_Computer_Arithmetic_Proceedings.pdf

Files

Kapre2007p907318Th_Ieee_Symposium_On_Computer_Arithmetic_Proceedings.pdf
Files (396.9 kB)

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024