Authors: Maria Jesus Garzaran, Milos Prvulovic, Ye Zhang, Alin Jula, Hao Yu, Lawrence Rauchwerger, Josep Torrellas

Venue: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques (PACT)
DOI: 10.1109/PACT.2001.953304
Link to Publication

Abstract:
Reductions are important and time-consuming operations in many scientific codes. Effective parallelization of reductions is a critical transformation for loop parallelization, especially for sparse, dynamic applications. Unfortunately, conventional reduction parallelization algorithms are not scalable. In this paper, we present new architectural support that significantly speeds up parallel reduction and makes it scalable in shared-memory multiprocessors. The required architectural changes are mostly confined to the directory controllers. Experimental results based on simulations show that the proposed support is very effective. While conventional software-only reduction parallelization delivers average speedups of only 2.7 for 16 processors, our scheme delivers average speedups of 7.6. 

@inproceedings{Garzaran-asfpri-2001, 
 author = {M. J. {Garzaran} and M. {Prvulovic} and  {Ye Zhang} and A. {Jula} and  {Hao Yu} and L. {Rauchwerger} and J. {Torrellas}}, 
 booktitle = {Proceedings 2001 International Conference on Parallel Architectures and Compilation Techniques}, 
 doi = {10.1109/PACT.2001.953304}, 
 number = {}, 
 pages = {243-254}, 
 title = {Architectural support for parallel reductions in scalable shared-memory multiprocessors}, 
 volume = {}, 
 year = {2001} 
}