in Scalable Shared-Memory Multiprocessors

Reductions are important and time-consuming opera-tions in many scientific codes. Effective parallelization of reductions is a critical transformation for loop paralleliza-tion, especially for sparse, dynamic applications. Unfortu-nately, conventional reduction parallelization algorithms are not scalable. In this paper, we present new architectural support that significantly speeds-up parallel reduction and makes it scal-able in shared-memory multiprocessors. The required ar-chitectural 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 deliv-ers average speedups of only 2.7 for 16 processors, our scheme delivers average speedups of 7.6.