Title :
Architectural support for parallel reductions in scalable shared-memory multiprocessors
Author :
Garzarán, María Jesus ; Prvulovic, Milos ; Zhang, Ye ; Jula, Alin ; Yu, Hao ; Rauchwerger, Lawrence ; Torrellas, Josep
Author_Institution :
Univ. Zaragoza, Spain
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
Keywords :
parallel architectures; performance evaluation; shared memory systems; architectural changes; architectural support; directory controllers; loop parallelization; parallel reductions; reduction parallelization algorithms; scalable shared-memory multiprocessors; scientific codes; simulations; sparse dynamic applications; speedups; Commutation; Concurrent computing; Delay; Merging; Parallel algorithms; Parallel machines; Parallel processing; Phased arrays; Program processors; Programming profession;
Conference_Titel :
Parallel Architectures and Compilation Techniques, 2001. Proceedings. 2001 International Conference on
Conference_Location :
Barcelona
Print_ISBN :
0-7695-1363-8
DOI :
10.1109/PACT.2001.953304