Segmented alignment: An enhanced model to align data parallel programs of HPF

Gwan-Hwan Hwang, Cheng Wei Chen, Jenq Kuen Lee, Roy Dz-Ching Ju

Research output: Contribution to journalArticle

Abstract

In this paper, we propose a new automatic data alignment model called segmented alignment. The conventional data alignment model, such as that used in High-Performance Fortran (HPF), aligns arrays with the whole index domain. The principle of our proposed segmented alignment is to allow alignment relations within delimited index domains. We first provide motivating examples to illustrate how code fragments of HPF with EOSHIFT or CSHIFT operations, or produced by synthesis operations can benefit from our enhanced alignment scheme. Second, we show that this new model can be implemented in HPF-like languages by adding WHEN and IN constructs to them. In addition, we show that the new proposed schemes for WHEN and IN constructs can be emulated using standard HPF syntax. Finally, we address issues related to automatic data alignment for the new proposed model, and present an algorithm to automatically align programs using our segmented alignment scheme. Since the optimal algorithm to do this is NP-hard. a practical heuristic is also given. Our experiments were performed on a DEC Alpha Farm with HPF environments. Our experiments confirm our theory that our proposed alignment scheme can significantly enhance not only the performance of HPF code fragments with EOSHIFT or CSHIFT operations, but also that of codes produced by synthesis operations.

Original languageEnglish
Pages (from-to)17-41
Number of pages25
JournalJournal of Supercomputing
Volume25
Issue number1
DOIs
Publication statusPublished - 2003 May 1

Fingerprint

Parallel Programs
Alignment
High Performance
Model
Fragment
Synthesis
Optimal Algorithm
Farms
Experiment
NP-complete problem
Experiments
Heuristics

Keywords

  • Automatic array alignment
  • Compiler optimization
  • Distributed-memory machines
  • HPF compilers
  • Parallelizing compiler
  • Segmented alignment

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture

Cite this

Segmented alignment : An enhanced model to align data parallel programs of HPF. / Hwang, Gwan-Hwan; Chen, Cheng Wei; Lee, Jenq Kuen; Dz-Ching Ju, Roy.

In: Journal of Supercomputing, Vol. 25, No. 1, 01.05.2003, p. 17-41.

Research output: Contribution to journalArticle

Hwang, Gwan-Hwan ; Chen, Cheng Wei ; Lee, Jenq Kuen ; Dz-Ching Ju, Roy. / Segmented alignment : An enhanced model to align data parallel programs of HPF. In: Journal of Supercomputing. 2003 ; Vol. 25, No. 1. pp. 17-41.
@article{dbbd38c9903c4dcb911e22799a3c1c7c,
title = "Segmented alignment: An enhanced model to align data parallel programs of HPF",
abstract = "In this paper, we propose a new automatic data alignment model called segmented alignment. The conventional data alignment model, such as that used in High-Performance Fortran (HPF), aligns arrays with the whole index domain. The principle of our proposed segmented alignment is to allow alignment relations within delimited index domains. We first provide motivating examples to illustrate how code fragments of HPF with EOSHIFT or CSHIFT operations, or produced by synthesis operations can benefit from our enhanced alignment scheme. Second, we show that this new model can be implemented in HPF-like languages by adding WHEN and IN constructs to them. In addition, we show that the new proposed schemes for WHEN and IN constructs can be emulated using standard HPF syntax. Finally, we address issues related to automatic data alignment for the new proposed model, and present an algorithm to automatically align programs using our segmented alignment scheme. Since the optimal algorithm to do this is NP-hard. a practical heuristic is also given. Our experiments were performed on a DEC Alpha Farm with HPF environments. Our experiments confirm our theory that our proposed alignment scheme can significantly enhance not only the performance of HPF code fragments with EOSHIFT or CSHIFT operations, but also that of codes produced by synthesis operations.",
keywords = "Automatic array alignment, Compiler optimization, Distributed-memory machines, HPF compilers, Parallelizing compiler, Segmented alignment",
author = "Gwan-Hwan Hwang and Chen, {Cheng Wei} and Lee, {Jenq Kuen} and {Dz-Ching Ju}, Roy",
year = "2003",
month = "5",
day = "1",
doi = "10.1023/A:1022852522319",
language = "English",
volume = "25",
pages = "17--41",
journal = "Journal of Supercomputing",
issn = "0920-8542",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Segmented alignment

T2 - An enhanced model to align data parallel programs of HPF

AU - Hwang, Gwan-Hwan

AU - Chen, Cheng Wei

AU - Lee, Jenq Kuen

AU - Dz-Ching Ju, Roy

PY - 2003/5/1

Y1 - 2003/5/1

N2 - In this paper, we propose a new automatic data alignment model called segmented alignment. The conventional data alignment model, such as that used in High-Performance Fortran (HPF), aligns arrays with the whole index domain. The principle of our proposed segmented alignment is to allow alignment relations within delimited index domains. We first provide motivating examples to illustrate how code fragments of HPF with EOSHIFT or CSHIFT operations, or produced by synthesis operations can benefit from our enhanced alignment scheme. Second, we show that this new model can be implemented in HPF-like languages by adding WHEN and IN constructs to them. In addition, we show that the new proposed schemes for WHEN and IN constructs can be emulated using standard HPF syntax. Finally, we address issues related to automatic data alignment for the new proposed model, and present an algorithm to automatically align programs using our segmented alignment scheme. Since the optimal algorithm to do this is NP-hard. a practical heuristic is also given. Our experiments were performed on a DEC Alpha Farm with HPF environments. Our experiments confirm our theory that our proposed alignment scheme can significantly enhance not only the performance of HPF code fragments with EOSHIFT or CSHIFT operations, but also that of codes produced by synthesis operations.

AB - In this paper, we propose a new automatic data alignment model called segmented alignment. The conventional data alignment model, such as that used in High-Performance Fortran (HPF), aligns arrays with the whole index domain. The principle of our proposed segmented alignment is to allow alignment relations within delimited index domains. We first provide motivating examples to illustrate how code fragments of HPF with EOSHIFT or CSHIFT operations, or produced by synthesis operations can benefit from our enhanced alignment scheme. Second, we show that this new model can be implemented in HPF-like languages by adding WHEN and IN constructs to them. In addition, we show that the new proposed schemes for WHEN and IN constructs can be emulated using standard HPF syntax. Finally, we address issues related to automatic data alignment for the new proposed model, and present an algorithm to automatically align programs using our segmented alignment scheme. Since the optimal algorithm to do this is NP-hard. a practical heuristic is also given. Our experiments were performed on a DEC Alpha Farm with HPF environments. Our experiments confirm our theory that our proposed alignment scheme can significantly enhance not only the performance of HPF code fragments with EOSHIFT or CSHIFT operations, but also that of codes produced by synthesis operations.

KW - Automatic array alignment

KW - Compiler optimization

KW - Distributed-memory machines

KW - HPF compilers

KW - Parallelizing compiler

KW - Segmented alignment

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

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

U2 - 10.1023/A:1022852522319

DO - 10.1023/A:1022852522319

M3 - Article

AN - SCOPUS:0038682000

VL - 25

SP - 17

EP - 41

JO - Journal of Supercomputing

JF - Journal of Supercomputing

SN - 0920-8542

IS - 1

ER -