Article

On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems

Authors:

E. Gutiérrez,

Oscar G. Plata,

Emilio L. ZapataAuthors Info & Claims

Euro-Par '99: Proceedings of the 5th International Euro-Par Conference on Parallel Processing

Pages 422 - 429

Published: 31 August 1999 Publication History

Abstract

This paper presents a new parallelization method for reductions of arrays with subscripted subscripts on scalable shared-memory multiprocessors. The mapping of computations is based on the conflict-free write distribution of the reduction vector across the processors. The proposed method is general, scalable, and easy to implement on a compiler. A performance evaluation and comparison with other existing techniques is presented. From the experimental results, the proposed method is a clear alternative to the array expansion and privatized buffer methods, usual on state-of-the-art parallelizing compilers, like Polaris or SUIF.

References

[1]

R. Asenjo, E. Gutierrez, Y. Lin, D. Padua, B. Pottengerg and E. Zapata, On the Automatic Parallelization of Sparse and Irregular Fortran Codes , TR-1512 , Univ. of Illinois at Urbana-Champaign, Ctr. for Supercomputing R&D., Dec. 1996.

Google Scholar

[2]

W. Blume, R. Doallo, R. Eigemann, et. al., Parallel Programming with Polaris , IEEE Computer, 29(12):78-82, Dec. 1996.

Crossref

Google Scholar

[3]

I. Foster, R. Schreiber and P. Havlak, HPF-2, Scope of Activities and Motivating Applications, Tech. Rep. CRPC-TR94492 , Rice Univ., Nov. 1994.

Google Scholar

[4]

M.W. Hall, J.M. Anderson, S.P. Amarasinghe, et. al., Maximizing Multiprocessor Performance with the SUIF Compiler IEEE Computer, 29(12), Dec. 1996.

Crossref

Google Scholar

[5]

H. Han and C.-W. Tseng, Improving Compiler and Run-Time Support for Irregular Reductions , 11th Workshop on Languages and Compilers for Parallel Computing, Chapel Hill, NC, Aug. 1998.

Crossref

Google Scholar

[6]

High Performance Fortran Language Specification, Version 2.0 . High Performance Fortran Forum, Oct. 1996.

Google Scholar

[7]

Y. Lin and D. Padua, On the Automatic Parallelization of Sparse and Irregular Fortran Programs , 4th Workshop on Languages, Compilers and Runtime Systems for Scalable Computers, Pittsburgh, PA, May 1998.

Crossref

Google Scholar

[8]

OpenMP: A Proposed Industry Standard API for Shared Memory Programming , OpenMP Architecture Review Board, http://www.openmp.org, 1997.

Google Scholar

[9]

R. Ponnusamy, J. Saltz, A. Choudhary, S. Hwang and G. Fox, Runtime Support and Compilation Methods for User-Specified Data Distributions , IEEE Trans. on Parallel and Distributed Systems, 6(8):815-831, Jun. 1995.

Crossref

Google Scholar

[10]

B. Pottenger and R. Eigenmann, Idiom Recognition in the Polaris Parallelizing Compiler , 9th ACM Int'l Conf. on Supercomputing, Barcelona, Spain, pp. 444-448, Jul. 1995.

Crossref

Google Scholar

[11]

Silicon Graphics, Inc. MIPSpro Automatic Parallelization . SGI, Inc. 1998.

Google Scholar

Cited By

View all

Gutiérrez ERomero SRomero LPlata OZapata E(2005)Parallel techniques in irregular codesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2004.11.00565:4(424-436)Online publication date: 1-Apr-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2004.11.005
Gutiérrez EPlata OZapata E(2002)On improving the performance of data partitioning oriented parallel irregular reductionsProceedings of the 10th Euromicro conference on Parallel, distributed and network-based processing10.5555/1895489.1895546(445-452)Online publication date: 9-Jan-2002
https://dl.acm.org/doi/10.5555/1895489.1895546
Gutiérrez EPlata OZapata E(2001)Balanced, locality-based parallel irregular reductionsProceedings of the 14th international conference on Languages and compilers for parallel computing10.5555/1769331.1769342(162-176)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.5555/1769331.1769342
Show More Cited By

On Automatic Parallelization of Irregular Reductions on Scalable Shared Memory Systems
1. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

Optimizing irregular shared-memory applications for distributed-memory systems
PPoPP '06: Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming

In prior work, we have proposed techniques to extend the ease of shared-memory parallel programming to distributed-memory platforms by automatic translation of OpenMP programs to MPI. In the case of irregular applications, the performance of this ...
A compiler method for the parallel execution of irregular reductions in scalable shared memory multiprocessors
ICS '00: Proceedings of the 14th international conference on Supercomputing

This paper presents a new parallelization method for reductions of arrays with subscripted subscripts on scalable shared memory multiprocessors. The mapping of computations is based on grouping reduction loop iterations into sets that are further ...
Distributed memory code generation for mixed Irregular/Regular computations
PPoPP 2015: Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Many applications feature a mix of irregular and regular computational structures. For example, codes using adaptive mesh refinement (AMR) typically use a collection of regular blocks, where the number of blocks and the relationship between blocks is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Euro-Par '99: Proceedings of the 5th International Euro-Par Conference on Parallel Processing

August 1999

1488 pages

ISBN:3540664432

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 31 August 1999

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gutiérrez ERomero SRomero LPlata OZapata E(2005)Parallel techniques in irregular codesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2004.11.00565:4(424-436)Online publication date: 1-Apr-2005
https://dl.acm.org/doi/10.1016/j.jpdc.2004.11.005
Gutiérrez EPlata OZapata E(2002)On improving the performance of data partitioning oriented parallel irregular reductionsProceedings of the 10th Euromicro conference on Parallel, distributed and network-based processing10.5555/1895489.1895546(445-452)Online publication date: 9-Jan-2002
https://dl.acm.org/doi/10.5555/1895489.1895546
Gutiérrez EPlata OZapata E(2001)Balanced, locality-based parallel irregular reductionsProceedings of the 14th international conference on Languages and compilers for parallel computing10.5555/1769331.1769342(162-176)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.5555/1769331.1769342
Gutiérrez EPlata OZapata ESlocomb C(2001)Improving parallel irregular reductions using partial array expansionProceedings of the 2001 ACM/IEEE conference on Supercomputing10.1145/582034.582072(38-38)Online publication date: 10-Nov-2001
https://dl.acm.org/doi/10.1145/582034.582072

Abstract

References

Cited By

Recommendations

Optimizing irregular shared-memory applications for distributed-memory systems

A compiler method for the parallel execution of irregular reductions in scalable shared memory multiprocessors

Distributed memory code generation for mixed Irregular/Regular computations

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations