Array operation synthesis to optimize HPF programs

Gwan-Hwan Hwang, Jenq Kuen Lee, D. C.R. Ju

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

Abstract

The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time can reduce the redundant data movement, temporary storage usage and loop synchronization overhead on flat shared-memory parallel machines with uniform memory accesses. However, it remains open how the synthesis scheme can be incorporated into optimizing HPF (High-Performance Fortran) programs on distributed-memory machines by taking into account communication costs. In this paper, we propose solutions to address this open problem. We first apply the array operation synthesis (developed for Fortran 90 programs) to HPF programs and demonstrate its performance benefits on distributed-memory machines. In addition, to prevent a situation we call the »synthesis performance anomaly», we derive a cost model and present an optimal solution based on this model to guide the array synthesis process on distributed-memory machines. We also show that the optimal problem is NP-hard. Therefore, we develop a practical heuristic algorithm for compilers to devise a synthesis strategy on distributed-memory machines with HPF programs. Experimental results show a significant performance improvement over the base codes for HPF code fragments from real applications on a DEC Alpha processor farm by incorporating our proposed optimizations.

Original languageEnglish
Title of host publicationSoftware
EditorsK. Pingali
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-8
Number of pages8
ISBN (Electronic)081867623X
DOIs
Publication statusPublished - 1996 Jan 1
Event25th International Conference on Parallel Processing, ICPP 1996 - Ithaca, United States
Duration: 1996 Aug 121996 Aug 16

Publication series

NameProceedings of the International Conference on Parallel Processing
Volume3
ISSN (Print)0190-3918

Other

Other25th International Conference on Parallel Processing, ICPP 1996
CountryUnited States
CityIthaca
Period96/8/1296/8/16

Fingerprint

High Performance
Optimise
Distributed Memory
Synthesis
Data storage equipment
Cost Model
Communication Cost
Parallel Machines
Heuristic algorithms
Shared Memory
Compiler
Heuristic algorithm
Farms
Anomaly
Costs
Consecutive
Computational complexity
Open Problems
Synchronization
Fragment

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Cite this

Hwang, G-H., Lee, J. K., & Ju, D. C. R. (1996). Array operation synthesis to optimize HPF programs. In K. Pingali (Ed.), Software (pp. 1-8). [538553] (Proceedings of the International Conference on Parallel Processing; Vol. 3). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPP.1996.538553

Array operation synthesis to optimize HPF programs. / Hwang, Gwan-Hwan; Lee, Jenq Kuen; Ju, D. C.R.

Software. ed. / K. Pingali. Institute of Electrical and Electronics Engineers Inc., 1996. p. 1-8 538553 (Proceedings of the International Conference on Parallel Processing; Vol. 3).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Hwang, G-H, Lee, JK & Ju, DCR 1996, Array operation synthesis to optimize HPF programs. in K Pingali (ed.), Software., 538553, Proceedings of the International Conference on Parallel Processing, vol. 3, Institute of Electrical and Electronics Engineers Inc., pp. 1-8, 25th International Conference on Parallel Processing, ICPP 1996, Ithaca, United States, 96/8/12. https://doi.org/10.1109/ICPP.1996.538553
Hwang G-H, Lee JK, Ju DCR. Array operation synthesis to optimize HPF programs. In Pingali K, editor, Software. Institute of Electrical and Electronics Engineers Inc. 1996. p. 1-8. 538553. (Proceedings of the International Conference on Parallel Processing). https://doi.org/10.1109/ICPP.1996.538553
Hwang, Gwan-Hwan ; Lee, Jenq Kuen ; Ju, D. C.R. / Array operation synthesis to optimize HPF programs. Software. editor / K. Pingali. Institute of Electrical and Electronics Engineers Inc., 1996. pp. 1-8 (Proceedings of the International Conference on Parallel Processing).
@inproceedings{0b14d9e1f6ea43a9a224d0c5ab324c07,
title = "Array operation synthesis to optimize HPF programs",
abstract = "The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time can reduce the redundant data movement, temporary storage usage and loop synchronization overhead on flat shared-memory parallel machines with uniform memory accesses. However, it remains open how the synthesis scheme can be incorporated into optimizing HPF (High-Performance Fortran) programs on distributed-memory machines by taking into account communication costs. In this paper, we propose solutions to address this open problem. We first apply the array operation synthesis (developed for Fortran 90 programs) to HPF programs and demonstrate its performance benefits on distributed-memory machines. In addition, to prevent a situation we call the »synthesis performance anomaly», we derive a cost model and present an optimal solution based on this model to guide the array synthesis process on distributed-memory machines. We also show that the optimal problem is NP-hard. Therefore, we develop a practical heuristic algorithm for compilers to devise a synthesis strategy on distributed-memory machines with HPF programs. Experimental results show a significant performance improvement over the base codes for HPF code fragments from real applications on a DEC Alpha processor farm by incorporating our proposed optimizations.",
author = "Gwan-Hwan Hwang and Lee, {Jenq Kuen} and Ju, {D. C.R.}",
year = "1996",
month = "1",
day = "1",
doi = "10.1109/ICPP.1996.538553",
language = "English",
series = "Proceedings of the International Conference on Parallel Processing",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1--8",
editor = "K. Pingali",
booktitle = "Software",

}

TY - GEN

T1 - Array operation synthesis to optimize HPF programs

AU - Hwang, Gwan-Hwan

AU - Lee, Jenq Kuen

AU - Ju, D. C.R.

PY - 1996/1/1

Y1 - 1996/1/1

N2 - The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time can reduce the redundant data movement, temporary storage usage and loop synchronization overhead on flat shared-memory parallel machines with uniform memory accesses. However, it remains open how the synthesis scheme can be incorporated into optimizing HPF (High-Performance Fortran) programs on distributed-memory machines by taking into account communication costs. In this paper, we propose solutions to address this open problem. We first apply the array operation synthesis (developed for Fortran 90 programs) to HPF programs and demonstrate its performance benefits on distributed-memory machines. In addition, to prevent a situation we call the »synthesis performance anomaly», we derive a cost model and present an optimal solution based on this model to guide the array synthesis process on distributed-memory machines. We also show that the optimal problem is NP-hard. Therefore, we develop a practical heuristic algorithm for compilers to devise a synthesis strategy on distributed-memory machines with HPF programs. Experimental results show a significant performance improvement over the base codes for HPF code fragments from real applications on a DEC Alpha processor farm by incorporating our proposed optimizations.

AB - The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time can reduce the redundant data movement, temporary storage usage and loop synchronization overhead on flat shared-memory parallel machines with uniform memory accesses. However, it remains open how the synthesis scheme can be incorporated into optimizing HPF (High-Performance Fortran) programs on distributed-memory machines by taking into account communication costs. In this paper, we propose solutions to address this open problem. We first apply the array operation synthesis (developed for Fortran 90 programs) to HPF programs and demonstrate its performance benefits on distributed-memory machines. In addition, to prevent a situation we call the »synthesis performance anomaly», we derive a cost model and present an optimal solution based on this model to guide the array synthesis process on distributed-memory machines. We also show that the optimal problem is NP-hard. Therefore, we develop a practical heuristic algorithm for compilers to devise a synthesis strategy on distributed-memory machines with HPF programs. Experimental results show a significant performance improvement over the base codes for HPF code fragments from real applications on a DEC Alpha processor farm by incorporating our proposed optimizations.

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

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

U2 - 10.1109/ICPP.1996.538553

DO - 10.1109/ICPP.1996.538553

M3 - Conference contribution

AN - SCOPUS:0005293335

T3 - Proceedings of the International Conference on Parallel Processing

SP - 1

EP - 8

BT - Software

A2 - Pingali, K.

PB - Institute of Electrical and Electronics Engineers Inc.

ER -