IEEE Transactions on Computers

IEEE Transactions on Computers (TC) is a monthly publication that publishes research in such areas as computer organizations and architectures, digital devices, operating systems, and new and important applications and trends.


From the July 2015 issue

Parallel Reproducible Summation

By James Demmel and Hong Diep Nguyen

Featured article thumbnail imageReproducibility, i.e. getting bitwise identical floating point results from multiple runs of the same program, is a property that many users depend on either for debugging or correctness checking in many codes [10]. However, the combination of dynamic scheduling of parallel computing resources, and floating point nonassociativity, makes attaining reproducibility a challenge even for simple reduction operations like computing the sum of a vector of numbers in parallel. We propose a technique for floating point summation that is reproducible independent of the order of summation. Our technique uses Rump’s algorithm for error-free vector transformation [7], and is much more efficient than using (possibly very) high precision arithmetic. Our algorithm reproducibly computes highly accurate results with an absolute error bound of $n \cdot 2^{-28} \cdot macheps \cdot \max _i |v_i|$ at a cost of $7n$ FLOPs and a small constant amount of extra memory usage. Higher accuracies are also possible by increasing the number of error-free transformations. As long as all operations are performed in to-nearest rounding mode, results computed by the proposed algorithms are reproducible for any run on any platform. In particular, our algorithm requires the minimum number of reductions, i.e. one reduction of an array of six double precision floating point numbers per sum, and hence is well suited for massively parallel environments.

YouTube and Youku links feature TC monthly spotlight articles in Chinese.

download PDF View the PDF of this article      csdl View this issue in the digital library     TC Featured Article Youtube video in Chinese  TC on YouTube     TC Featured Article on Youku  TC on Youku


Editorials and Announcements

Announcements


New Essential Set


Editorials


Guest Editorials


Reviewers List


Annual Index


Access Recently Published TC Articles

RSS Subscribe to the RSS feed of latest TC content added to the digital library

Mail Sign up for the Transactions Connection newsletter.


Importance of Coherence Protocols with Network Applications on Multi-Core Processors

 

Automated Generation of Performance and Dependability Models for the Assessment of Wireless Sensor Networks

Computing Now
.