TY - GEN
T1 - Improving compiler and run-time support for irregular reductions using local writes
AU - Han, Hwansoo
AU - Tseng, Chau Wen
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - Current compilers for distributed-memory multiprocessors parallelize irregular reductions either by generating calls to sophisticated run-time systems (CHAOS) or by relying on replicated buffers and the shared-memory interface supported by software DSMs (TreadMarks). We introduce LocalWrite, a new technique for parallelizing irregular reductions based on the owner-computes rule. It eliminates the need for buffers or synchronized writes, but may replicate computation. We investigate the impact of connectivity (node/edge ratio), locality (accesses to local data) and adaptivity (edge modifications) on their relative performance. LocalWrite improves performance by 50{150% compared to using replicated buffers, and can match or exceed gather/scatter for applications with low locality or high adaptivity.
AB - Current compilers for distributed-memory multiprocessors parallelize irregular reductions either by generating calls to sophisticated run-time systems (CHAOS) or by relying on replicated buffers and the shared-memory interface supported by software DSMs (TreadMarks). We introduce LocalWrite, a new technique for parallelizing irregular reductions based on the owner-computes rule. It eliminates the need for buffers or synchronized writes, but may replicate computation. We investigate the impact of connectivity (node/edge ratio), locality (accesses to local data) and adaptivity (edge modifications) on their relative performance. LocalWrite improves performance by 50{150% compared to using replicated buffers, and can match or exceed gather/scatter for applications with low locality or high adaptivity.
UR - https://www.scopus.com/pages/publications/84947939650
U2 - 10.1007/3-540-48319-5_12
DO - 10.1007/3-540-48319-5_12
M3 - Conference contribution
AN - SCOPUS:84947939650
SN - 3540664262
SN - 9783540664260
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 181
EP - 196
BT - Languages and Compilers for Parallel Computing - 11th International Workshop, LCPC 1998, Proceedings
A2 - Chatterjee, Siddhartha
A2 - Prins, Jan F.
A2 - Carter, Larry
A2 - Ferrante, Jeanne
A2 - Li, Zhiyuan
A2 - Sehr, David
A2 - Yew, Pen-Chung
PB - Springer Verlag
T2 - 11th International Workshop on Languages and Compilers for Parallel Computing, LCPC 1998
Y2 - 7 August 1998 through 9 August 1998
ER -