Architectural support for parallel reductions in scalable shared-memory multiprocessors

María Jesús Garzarán; Milos Prvulovic; Ye Zhang; Alin Jula; Hao Yu; Lawrence Rauchwerger; Josep Torrellas

doi:10.1109/PACT.2001.953304

Architectural support for parallel reductions in scalable shared-memory multiprocessors

María Jesús Garzarán, Milos Prvulovic, Ye Zhang, Alin Jula, Hao Yu, Lawrence Rauchwerger, Josep Torrellas

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	243-254
Number of pages	12
Journal	Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
DOIs	https://doi.org/10.1109/PACT.2001.953304
State	Published - 2001

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture

Online availability

10.1109/PACT.2001.953304

Library availability

Discover UIUC Full Text

Cite this

@article{659818d12f534308b13cd004df1f8113,

title = "Architectural support for parallel reductions in scalable shared-memory multiprocessors",

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.",

author = "Garzar{\'a}n, {Mar{\'i}a Jes{\'u}s} and Milos Prvulovic and Ye Zhang and Alin Jula and Hao Yu and Lawrence Rauchwerger and Josep Torrellas",

year = "2001",

doi = "10.1109/PACT.2001.953304",

language = "English (US)",

pages = "243--254",

journal = "Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT",

issn = "1089-795X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Architectural support for parallel reductions in scalable shared-memory multiprocessors

AU - Garzarán, María Jesús

AU - Prvulovic, Milos

AU - Zhang, Ye

AU - Jula, Alin

AU - Yu, Hao

AU - Rauchwerger, Lawrence

AU - Torrellas, Josep

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0035177716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035177716&partnerID=8YFLogxK

U2 - 10.1109/PACT.2001.953304

DO - 10.1109/PACT.2001.953304

M3 - Article

AN - SCOPUS:0035177716

SN - 1089-795X

SP - 243

EP - 254

JO - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

JF - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

ER -

Architectural support for parallel reductions in scalable shared-memory multiprocessors

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this