A loop parallelization algorithm for HPF compilers | SpringerLink
Skip to main content
Springer Nature Link
Log in

A loop parallelization algorithm for HPF compilers

  • Conference paper
  • First Online:
Languages and Compilers for Parallel Computing (LCPC 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1033))

  • 126 Accesses

Abstract

This paper presents a formalized loop parallelization algorithm for effectively extracting parallelism from data to be allocated to processors with array decomposition directives, in languages such as High Performance Fortran (HPF). We define a communication dependence vector that shows data dependence among processors, and use it in our algorithm to formalize and unify the detection of vector prefetch communication and vector pipeline communication for loop parallelization. The paper also presents a method, based on our algorithm for generating vector communications. We implemented the algorithm in our HPF compiler and carried out experiments with two applications on an IBM RS/6000 Scalable POWERparallel System.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. High Performance Fortran Forum, High Performance Fortran Language Specification, Version 1.0, Technical Report, Rice University, CRPC-TR92225, 1992

    Google Scholar 

  2. Darema F., George D., Norton V., and Pfister G.: A Single Program Multiple Data Computational Model for EPEX/FORTRAN, Parallel Computing, Vol. 7, pp. 11–24, 1988

    Article  Google Scholar 

  3. C. W. Tseng: An Optimizing Fortran D Compiler for MIMD Distributed-Memory Machines, PhD thesis, Rice University, CRPC-TR93291, 1993

    Google Scholar 

  4. Stanford SUIF Compiler Group: SUIF: A Parallelizing and Optimizing Research Compiler, Technical Report, Stanford University, CSL-TR-94-620, 1994

    Google Scholar 

  5. H. P. Zima, H. J. Bast, and M. Gerndt: SUPERB: A Tool for Semiautomatic MIMD/SIMD Parallelization, Parallel Computing, Vol. 6, pp. 1–18, 1988

    Article  Google Scholar 

  6. Z. Bozkus, A. Choudhary, G. Fox, T. Haupt, S. Ranka: Fortran90D/HPF Compiler for Distributed Memory MIMD Computers: Design, Implementation, and Performance Results, Proceedings of Supercomputing '93, pp. 351–360, 1993

    Google Scholar 

  7. P. Banerjee, J. A. Chandy, M. Gupta, J. G. Holm, A. Lain, D. J. Palermo, S. Ramaswamy: The PARADIGM Compiler for Distributed-Memory Message Passing Multicomputers, In Proceedings of the First International Workshop on Parallel Processing, pp. 322–330, 1994

    Google Scholar 

  8. S. Hiranandani, K. Kennedy, and C. W. Tseng: Compiling Fortran D for MIMD Distributed-Memory Machines, Communications of the ACM, Vol. 35, pp. 66–80, 1992

    Article  Google Scholar 

  9. V. Balasundaram, G. Fox, K. Kennedy, and U. Kremer: An Interactive Environment for Data Partitioning and Distribution, In Proceedings of the 5th Distributed Memory Computing Conference, pp. 1160–1170, 1990

    Google Scholar 

  10. M. Gerndt: Updating Distributed Variables in Local Computations, Concurrency: Practice & Experience, Vol. 2, No. 3, pp. 171–193, 1990

    Google Scholar 

  11. A. Rogers and K. Pingali: Process Decomposition through Locality of Reference, Conference on Programming Language Design and Implementation, pp. 69–80, 1989

    Google Scholar 

  12. M. E. Wolfe and M. S. Lam: A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, Vol. 2, No. 4, pp. 452–471, 1991

    Article  Google Scholar 

  13. G. Goff, K. Kennedy, and C. W. Tseng: Practical Dependence Testing, Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, pp. 15–29, 1991

    Google Scholar 

  14. M. J. Wolfe: Optimizing Supercompilers for Supercomputers, The MIT Press, 1989

    Google Scholar 

  15. D. Callahan and K. Kennedy: Compiling Programs for Distributed-Memory Multiprocessors, Journal of Supercomputing, Vol. 2, pp. 151–169, 1988

    Article  Google Scholar 

  16. S. Hiranandani, K. Kennedy, and C. W. Tseng: Evaluating Compiler Optimizations for Fortran D, Journal of Parallel and Distributed Computing, Vol. 21, pp. 27–45, 1994

    Article  Google Scholar 

  17. D. J. Palermo, E. Su, J. A. Chandy, P. Banerjee: Communication Optimizations used in the PARADIGM Compiler for Distributed-Memory Multicomputers, In Proceedings of the 23rd International Conference on Parallel Processing, pp. II:1–10, 1994

    Google Scholar 

  18. IBM AIX Parallel Environment — Parallel Programming Subroutine Reference Release 2.0, SH26-7228-01, IBM Corporation, 1994

    Google Scholar 

  19. IBM AIX Parallel Environment — Operation and Use Release 2.0, SH26-7230-01, IBM Corporation, 1994

    Google Scholar 

  20. R. K. Sato and P. N. Swarztrauber: BenchMarking the Connection Machine 2, Proceedings of Supercomputing '88, 1988

    Google Scholar 

  21. J. Li and M. Chen: Compiling Communication Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, Vol. 2, No. 3, pp. 361–376, 1991

    Article  Google Scholar 

  22. Applied Parallel Research: xHPF: User's Guide (Version 2.0), 1995

    Google Scholar 

  23. T. Brandes: ADAPTOR Language Reference Manual Version 2.0, German National Research Center for Computer Science, 1994

    Google Scholar 

  24. S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and A.W. Lim: An Overview of a Compiler for Scalable Parallel Machines, Proceedings of the 6th Workshop on Languages and Compilers for Parallel Computing, 1993

    Google Scholar 

  25. J. M. Anderson and M. S. Lam: Global Optimizations for Parallelism and Locality on Scalable Parallel Machines, Conference on Programming Language Design and Implementation, 1993

    Google Scholar 

  26. A. W. Lim and M. S. Lam: Communication-Free Parallelization via Affine Transformation, Proceedings of the 7th Workshop on Languages and Compilers for Parallel Computing, 1994

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Tokyo Research Laboratory, IBM Japan Ltd., 1623-14 Shimotsuruma, Yamato, 242, Kanagawa, Japan

    Kazuaki Ishizaki & Hideaki Komatsu

Authors
  1. Kazuaki Ishizaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hideaki Komatsu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Chua-Huang Huang Ponnuswamy Sadayappan Utpal Banerjee David Gelernter Alex Nicolau David Padua

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ishizaki, K., Komatsu, H. (1996). A loop parallelization algorithm for HPF compilers. In: Huang, CH., Sadayappan, P., Banerjee, U., Gelernter, D., Nicolau, A., Padua, D. (eds) Languages and Compilers for Parallel Computing. LCPC 1995. Lecture Notes in Computer Science, vol 1033. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014199

Download citation

  • DOI: https://doi.org/10.1007/BFb0014199

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60765-6

  • Online ISBN: 978-3-540-49446-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation