An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution

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

Abstract

We present an 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 solution to the same problem. Another important contribution of the 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
Title of host publicationProceedings - International Conference on Parallel Processing Workshops, ICPPW 2002
EditorsStephan Olariu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages623-631
Number of pages9
ISBN (Electronic)0769516807
DOIs
Publication statusPublished - 2002 Jan 1
EventInternational Conference on Parallel Processing Workshops, ICPPW 2002 - Vancouver, Canada
Duration: 2002 Aug 182002 Aug 21

Publication series

NameProceedings of the International Conference on Parallel Processing Workshops
Volume2002-January
ISSN (Print)1530-2016

Other

OtherInternational Conference on Parallel Processing Workshops, ICPPW 2002
CountryCanada
CityVancouver
Period02/8/1802/8/21

Fingerprint

Parallel Programs
Efficient Algorithms
Linear Diophantine equation
Linear equations
Computing
Communication
Lowest common multiple
Multidimensional Arrays
Subscript
Affine Function
Formal Proof
Experimental Results
Compiler
Alignment
Calculate
Integer
Demonstrate

Keywords

  • Block-Cyclic Distributions
  • Data Parallel Programs
  • Distributed Memory Machines
  • HPF Compiler
  • Parallelizing Compiler

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Cite this

Hwang, G-H. (2002). An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution. In S. Olariu (Ed.), Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002 (pp. 623-631). [1039785] (Proceedings of the International Conference on Parallel Processing Workshops; Vol. 2002-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPPW.2002.1039785

An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution. / Hwang, Gwan-Hwan.

Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002. ed. / Stephan Olariu. Institute of Electrical and Electronics Engineers Inc., 2002. p. 623-631 1039785 (Proceedings of the International Conference on Parallel Processing Workshops; Vol. 2002-January).

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

Hwang, G-H 2002, An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution. in S Olariu (ed.), Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002., 1039785, Proceedings of the International Conference on Parallel Processing Workshops, vol. 2002-January, Institute of Electrical and Electronics Engineers Inc., pp. 623-631, International Conference on Parallel Processing Workshops, ICPPW 2002, Vancouver, Canada, 02/8/18. https://doi.org/10.1109/ICPPW.2002.1039785
Hwang G-H. An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution. In Olariu S, editor, Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002. Institute of Electrical and Electronics Engineers Inc. 2002. p. 623-631. 1039785. (Proceedings of the International Conference on Parallel Processing Workshops). https://doi.org/10.1109/ICPPW.2002.1039785
Hwang, Gwan-Hwan. / An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution. Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002. editor / Stephan Olariu. Institute of Electrical and Electronics Engineers Inc., 2002. pp. 623-631 (Proceedings of the International Conference on Parallel Processing Workshops).
@inproceedings{8bd62e8c41ac45a694d4d17cff12ebf2,
title = "An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution",
abstract = "We present an 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 solution to the same problem. Another important contribution of the 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 = "Gwan-Hwan Hwang",
year = "2002",
month = "1",
day = "1",
doi = "10.1109/ICPPW.2002.1039785",
language = "English",
series = "Proceedings of the International Conference on Parallel Processing Workshops",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "623--631",
editor = "Stephan Olariu",
booktitle = "Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002",

}

TY - GEN

T1 - An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution

AU - Hwang, Gwan-Hwan

PY - 2002/1/1

Y1 - 2002/1/1

N2 - We present an 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 solution to the same problem. Another important contribution of the 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 - We present an 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 solution to the same problem. Another important contribution of the 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=84954518547&partnerID=8YFLogxK

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

U2 - 10.1109/ICPPW.2002.1039785

DO - 10.1109/ICPPW.2002.1039785

M3 - Conference contribution

AN - SCOPUS:84954518547

T3 - Proceedings of the International Conference on Parallel Processing Workshops

SP - 623

EP - 631

BT - Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002

A2 - Olariu, Stephan

PB - Institute of Electrical and Electronics Engineers Inc.

ER -