An efficient algorithm for communication set generation of data parallel programs with block-cyclic distribution

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Data parallel programming languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. In this paper, we present a new algorithm for computing the communication sets in array section movements with block-cyclic (cyclic (k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed. We use formal proof and experimental results to show that it is more efficient than previous solutions to the same problem. Another important contribution of this paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer. We demonstrate it by thorough complexity analyses and extensive experimental results.

Original languageEnglish
Pages (from-to)473-501
Number of pages29
JournalParallel Computing
Volume30
Issue number4
DOIs
Publication statusPublished - 2004 Apr 1

Fingerprint

Parallel Programs
Efficient Algorithms
Linear Diophantine equation
Linear equations
Communication
Parallel programming
Lowest common multiple
Multidimensional Arrays
Subscript
Computer programming languages
Affine Function
Formal Proof
Parallel Programming
Experimental Results
Distributed Memory
Compiler
Programming Languages
Data storage equipment
Alignment
High Performance

Keywords

  • Block-cyclic distributions
  • Data parallel programs
  • Distributed memory machines
  • HPF compiler
  • Parallelizing compiler

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Cite this

An efficient algorithm for communication set generation of data parallel programs with block-cyclic distribution. / Hwang, Gwan Hwan.

In: Parallel Computing, Vol. 30, No. 4, 01.04.2004, p. 473-501.

Research output: Contribution to journalArticle

@article{690a1c4949664654a2b0883391c77dd6,
title = "An efficient algorithm for communication set generation of data parallel programs with block-cyclic distribution",
abstract = "Data parallel programming languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. In this paper, we present a new algorithm for computing the communication sets in array section movements with block-cyclic (cyclic (k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed. We use formal proof and experimental results to show that it is more efficient than previous solutions to the same problem. Another important contribution of this paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer. We demonstrate it by thorough complexity analyses and extensive experimental results.",
keywords = "Block-cyclic distributions, Data parallel programs, Distributed memory machines, HPF compiler, Parallelizing compiler",
author = "Hwang, {Gwan Hwan}",
year = "2004",
month = "4",
day = "1",
doi = "10.1016/j.parco.2004.02.001",
language = "English",
volume = "30",
pages = "473--501",
journal = "Parallel Computing",
issn = "0167-8191",
publisher = "Elsevier",
number = "4",

}

TY - JOUR

T1 - An efficient algorithm for communication set generation of data parallel programs with block-cyclic distribution

AU - Hwang, Gwan Hwan

PY - 2004/4/1

Y1 - 2004/4/1

N2 - Data parallel programming languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. In this paper, we present a new algorithm for computing the communication sets in array section movements with block-cyclic (cyclic (k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed. We use formal proof and experimental results to show that it is more efficient than previous solutions to the same problem. Another important contribution of this paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer. We demonstrate it by thorough complexity analyses and extensive experimental results.

AB - Data parallel programming languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. In this paper, we present a new algorithm for computing the communication sets in array section movements with block-cyclic (cyclic (k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed. We use formal proof and experimental results to show that it is more efficient than previous solutions to the same problem. Another important contribution of this paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer. We demonstrate it by thorough complexity analyses and extensive experimental results.

KW - Block-cyclic distributions

KW - Data parallel programs

KW - Distributed memory machines

KW - HPF compiler

KW - Parallelizing compiler

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

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

U2 - 10.1016/j.parco.2004.02.001

DO - 10.1016/j.parco.2004.02.001

M3 - Article

AN - SCOPUS:2442694369

VL - 30

SP - 473

EP - 501

JO - Parallel Computing

JF - Parallel Computing

SN - 0167-8191

IS - 4

ER -