Optimistic Parallelization of Floating-Point Accumulation
Nachiket Kapre and André DeHon
Proceedings of the IEEE
Symposium on Computer Arithmetic, pp. 205--213 (Arith18, June 25--27, 2007)
Floating-point arithmetic is notoriously nonassociative
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 296MHz 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.
© 2007 IEEE. Authors/employers may reproduce or authorize others to reproduce The Work, material extracted verbatim from the Work, or derivative works to
the extent permissible under United States law for works authored by U.S. Government employees, and for the author's personal use or for
company or organizational use, provided that the source and any IEEE copyright notice are indicated, the copies are not used in any way that
implies IEEE endorsement of a product or service of any employer, and the copies themselves are not offered for sale.
(IEEE
Copyright)
|
