• Jun Shirako, David M. Peixotto, Vivek Sarkar, and William N. Scherer III
  • IPDPS '09: Proceedings of the 2009 IEEE International Symposium on Parallel&Distributed Processing
  • 2009-05-25
  • pdf
  • bibtex

Abstract

A reduction is a computation in which a common operation, such as a sum, is to be performed across multiple pieces of data, each supplied by a separate task. We introduce phaser accumulators, a new reduction construct that meshes seamlessly with phasers to support dynamic parallelism in a phased (iterative) setting. By separating reduction computations into the parts of sending data, performing the computation itself, and retrieving the result, we enable overlap of communication and computation in a manner analogous to that of split-phase barriers. Additionally, this separation enables exploration of implementation strategies that differ as to when the reduction itself is performed: eagerly when the data is supplied, or lazily when a synchronization point is reached.

We implement accumulators as extensions to phasers in the Habanero dialect of the X10 programming language. Performance evaluations of the EPCC Syncbench, Spectral-norm, and CG benchmarks on AMD Opteron, Intel Xeon, and Sun UltraSPARC T2 multicore SMPs show superior performance and scalability over OpenMP reductions (on two platforms) and X10 code (on three platforms) written with atomic blocks, with improvements of up to 2.5x on the Opteron and 14.9x on the UltraSPARC T2 relative to OpenMP and 16.5x on the Opteron, 26.3x on the Xeon and 94.8x on the UltraSPARC T2 relative to X10 atomic blocks. To the best of our knowledge, no prior reduction construct supports the dynamic parallelism and asynchronous capabilities of phaser accumulators.

Bibtex

@inproceedings{ShirakoAccumulators, author = {Shirako, J. and Peixotto, D. M. and Sarkar, V. and Scherer, W. N.}, title = {Phaser accumulators: A new reduction construct for dynamic parallelism}, booktitle = {IPDPS 09: Proceedings of the 2009 IEEE International Symposium on Parallel\&Distributed Processing}, year = {2009}, isbn = {978-1-4244-3751-1}, pages = {1--12}, doi = {http://dx.doi.org/10.1109/IPDPS.2009.5161071}, publisher = {IEEE Computer Society}, address = {Washington, DC, USA}, }