Array Operation Synthesis to Optimize HPF Programs on Distributed Memory Machines

Gwan Hwan Hwang, Jenq Kuen Lee, Roy Dz Ching Ju

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

An increasing number of programming languages, such as Fortran 90, HPF, and APL, provide a rich set of intrinsic array functions and array expressions. These constructs, which constitute an important part of data parallel languages, provide excellent opportunities for compiler optimizations. The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time has been shown (A. T. Budd, ACM Trans. Programm. Lang. Syst.6 (July 1984), 297-313; G. H. Hwang et al., in "Proc. of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, 1995," pp. 112-122) to be an effective scheme for optimizing programs on flat shared memory parallel architectures. It remains, however, to be studied how the synthesis scheme can be incorporated into optimizing HPF-like programs on distributed memory machines by taking into account communication costs. In this paper, we propose solutions to address this issue. We first show how to perform array operation synthesis on HPF programs, and we demonstrate its performance benefits on distributed memory machines with real applications. In addition, to prevent a situation we call "synthesis anomaly," we present an optimal solution to guide the array synthesis process on distributed memory machines. Due to the optimal problem being NP-hard, we further develop a practical strategy that compilers can use on distributed memory machines with HPF programs. Our synthesis engine is implemented as a Web-based tool, called Syntool, and experimental results show significant performance improvement over the base codes for HPF code fragments from real appli- cations on parallel machines. Our experiments were performed on three distributed memory machines: an 8-node DEC Alpha Farm, a 16-node IBM SP-2, and a 16-node nCUBE/2.

Original languageEnglish
Pages (from-to)467-500
Number of pages34
JournalJournal of Parallel and Distributed Computing
Volume61
Issue number4
DOIs
Publication statusPublished - 2001 Apr 1

Fingerprint

Distributed Memory
Optimise
Synthesis
Data storage equipment
Vertex of a graph
Parallel programming
Parallel architectures
Compiler Optimization
Parallel Architectures
Communication Cost
Parallel Programming
Computer programming languages
Parallel Machines
Farms
NP-hard Problems
Shared Memory
Computational complexity
Compiler
Web-based
Anomaly

Keywords

  • HPF compiler; array operation synthesis; distributed memory machines; compiler optimization; parallelizing compiler

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this

Array Operation Synthesis to Optimize HPF Programs on Distributed Memory Machines. / Hwang, Gwan Hwan; Lee, Jenq Kuen; Ju, Roy Dz Ching.

In: Journal of Parallel and Distributed Computing, Vol. 61, No. 4, 01.04.2001, p. 467-500.

Research output: Contribution to journalArticle

@article{0926ff75798b4363a5194d7f0c0ad248,
title = "Array Operation Synthesis to Optimize HPF Programs on Distributed Memory Machines",
abstract = "An increasing number of programming languages, such as Fortran 90, HPF, and APL, provide a rich set of intrinsic array functions and array expressions. These constructs, which constitute an important part of data parallel languages, provide excellent opportunities for compiler optimizations. The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time has been shown (A. T. Budd, ACM Trans. Programm. Lang. Syst.6 (July 1984), 297-313; G. H. Hwang et al., in {"}Proc. of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, 1995,{"} pp. 112-122) to be an effective scheme for optimizing programs on flat shared memory parallel architectures. It remains, however, to be studied how the synthesis scheme can be incorporated into optimizing HPF-like programs on distributed memory machines by taking into account communication costs. In this paper, we propose solutions to address this issue. We first show how to perform array operation synthesis on HPF programs, and we demonstrate its performance benefits on distributed memory machines with real applications. In addition, to prevent a situation we call {"}synthesis anomaly,{"} we present an optimal solution to guide the array synthesis process on distributed memory machines. Due to the optimal problem being NP-hard, we further develop a practical strategy that compilers can use on distributed memory machines with HPF programs. Our synthesis engine is implemented as a Web-based tool, called Syntool, and experimental results show significant performance improvement over the base codes for HPF code fragments from real appli- cations on parallel machines. Our experiments were performed on three distributed memory machines: an 8-node DEC Alpha Farm, a 16-node IBM SP-2, and a 16-node nCUBE/2.",
keywords = "HPF compiler; array operation synthesis; distributed memory machines; compiler optimization; parallelizing compiler",
author = "Hwang, {Gwan Hwan} and Lee, {Jenq Kuen} and Ju, {Roy Dz Ching}",
year = "2001",
month = "4",
day = "1",
doi = "10.1006/jpdc.2000.1680",
language = "English",
volume = "61",
pages = "467--500",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "4",

}

TY - JOUR

T1 - Array Operation Synthesis to Optimize HPF Programs on Distributed Memory Machines

AU - Hwang, Gwan Hwan

AU - Lee, Jenq Kuen

AU - Ju, Roy Dz Ching

PY - 2001/4/1

Y1 - 2001/4/1

N2 - An increasing number of programming languages, such as Fortran 90, HPF, and APL, provide a rich set of intrinsic array functions and array expressions. These constructs, which constitute an important part of data parallel languages, provide excellent opportunities for compiler optimizations. The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time has been shown (A. T. Budd, ACM Trans. Programm. Lang. Syst.6 (July 1984), 297-313; G. H. Hwang et al., in "Proc. of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, 1995," pp. 112-122) to be an effective scheme for optimizing programs on flat shared memory parallel architectures. It remains, however, to be studied how the synthesis scheme can be incorporated into optimizing HPF-like programs on distributed memory machines by taking into account communication costs. In this paper, we propose solutions to address this issue. We first show how to perform array operation synthesis on HPF programs, and we demonstrate its performance benefits on distributed memory machines with real applications. In addition, to prevent a situation we call "synthesis anomaly," we present an optimal solution to guide the array synthesis process on distributed memory machines. Due to the optimal problem being NP-hard, we further develop a practical strategy that compilers can use on distributed memory machines with HPF programs. Our synthesis engine is implemented as a Web-based tool, called Syntool, and experimental results show significant performance improvement over the base codes for HPF code fragments from real appli- cations on parallel machines. Our experiments were performed on three distributed memory machines: an 8-node DEC Alpha Farm, a 16-node IBM SP-2, and a 16-node nCUBE/2.

AB - An increasing number of programming languages, such as Fortran 90, HPF, and APL, provide a rich set of intrinsic array functions and array expressions. These constructs, which constitute an important part of data parallel languages, provide excellent opportunities for compiler optimizations. The synthesis of consecutive array operations or array expressions into a composite access function of the source arrays at compile time has been shown (A. T. Budd, ACM Trans. Programm. Lang. Syst.6 (July 1984), 297-313; G. H. Hwang et al., in "Proc. of ACM SIGPLAN Conference on Principles and Practice of Parallel Programming, 1995," pp. 112-122) to be an effective scheme for optimizing programs on flat shared memory parallel architectures. It remains, however, to be studied how the synthesis scheme can be incorporated into optimizing HPF-like programs on distributed memory machines by taking into account communication costs. In this paper, we propose solutions to address this issue. We first show how to perform array operation synthesis on HPF programs, and we demonstrate its performance benefits on distributed memory machines with real applications. In addition, to prevent a situation we call "synthesis anomaly," we present an optimal solution to guide the array synthesis process on distributed memory machines. Due to the optimal problem being NP-hard, we further develop a practical strategy that compilers can use on distributed memory machines with HPF programs. Our synthesis engine is implemented as a Web-based tool, called Syntool, and experimental results show significant performance improvement over the base codes for HPF code fragments from real appli- cations on parallel machines. Our experiments were performed on three distributed memory machines: an 8-node DEC Alpha Farm, a 16-node IBM SP-2, and a 16-node nCUBE/2.

KW - HPF compiler; array operation synthesis; distributed memory machines; compiler optimization; parallelizing compiler

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

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

U2 - 10.1006/jpdc.2000.1680

DO - 10.1006/jpdc.2000.1680

M3 - Article

AN - SCOPUS:0038194616

VL - 61

SP - 467

EP - 500

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 4

ER -