Efficient method for irregular array redistribution

Sheng Wen Bai, Chu-Sing Yang

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

Abstract

In many parallel programs, run-time array redistribution is usually required to enhance data locality and reduce remote memory access on the distributed memory multicomputers. In general, array distribution can be classified into regular distribution and irregular distribution according to the distribution fashion. Many methods for performing regular array redistribution have been presented in the literature. However, for the heterogeneous computation environment, irregular array redistributions can be used to adjust data assignment at run-time. In this paper, an Essential Cycle Calculation method for irregular array redistribution will be presented. In the ECC method, a processor first computes the source/destination processor/data sets of array elements in the first essential cycle of the local array it owns. From the source/destination processor/data sets of array elements in the first essential cycle, we can construct packing/unpacking pattern tables. Since each essential cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the ECC method, we have implemented this method on an IBM SP2 parallel machine along with the Sequence method. The cost models for these methods are also presented. The experimental results show that the ECC method greatly outperforms the Sequence method for all test samples.

Original languageEnglish
Title of host publication3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings
PublisherInternational Institute of Informatics and Systemics, IIIS
Pages73-79
Number of pages7
ISBN (Print)9806560485, 9789806560482
Publication statusPublished - 2005 Jan 1
Event3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005 - Austin, TX, United States
Duration: 2005 Jul 242005 Jul 27

Publication series

Name3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings
Volume3

Other

Other3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005
CountryUnited States
CityAustin, TX
Period05-07-2405-07-27

Fingerprint

Data storage equipment
Communication
Costs

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this

Bai, S. W., & Yang, C-S. (2005). Efficient method for irregular array redistribution. In 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings (pp. 73-79). (3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings; Vol. 3). International Institute of Informatics and Systemics, IIIS.
Bai, Sheng Wen ; Yang, Chu-Sing. / Efficient method for irregular array redistribution. 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings. International Institute of Informatics and Systemics, IIIS, 2005. pp. 73-79 (3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings).
@inproceedings{23e7a68153df4bf5b557c54846444097,
title = "Efficient method for irregular array redistribution",
abstract = "In many parallel programs, run-time array redistribution is usually required to enhance data locality and reduce remote memory access on the distributed memory multicomputers. In general, array distribution can be classified into regular distribution and irregular distribution according to the distribution fashion. Many methods for performing regular array redistribution have been presented in the literature. However, for the heterogeneous computation environment, irregular array redistributions can be used to adjust data assignment at run-time. In this paper, an Essential Cycle Calculation method for irregular array redistribution will be presented. In the ECC method, a processor first computes the source/destination processor/data sets of array elements in the first essential cycle of the local array it owns. From the source/destination processor/data sets of array elements in the first essential cycle, we can construct packing/unpacking pattern tables. Since each essential cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the ECC method, we have implemented this method on an IBM SP2 parallel machine along with the Sequence method. The cost models for these methods are also presented. The experimental results show that the ECC method greatly outperforms the Sequence method for all test samples.",
author = "Bai, {Sheng Wen} and Chu-Sing Yang",
year = "2005",
month = "1",
day = "1",
language = "English",
isbn = "9806560485",
series = "3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings",
publisher = "International Institute of Informatics and Systemics, IIIS",
pages = "73--79",
booktitle = "3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings",

}

Bai, SW & Yang, C-S 2005, Efficient method for irregular array redistribution. in 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings. 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings, vol. 3, International Institute of Informatics and Systemics, IIIS, pp. 73-79, 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Austin, TX, United States, 05-07-24.

Efficient method for irregular array redistribution. / Bai, Sheng Wen; Yang, Chu-Sing.

3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings. International Institute of Informatics and Systemics, IIIS, 2005. p. 73-79 (3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings; Vol. 3).

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

TY - GEN

T1 - Efficient method for irregular array redistribution

AU - Bai, Sheng Wen

AU - Yang, Chu-Sing

PY - 2005/1/1

Y1 - 2005/1/1

N2 - In many parallel programs, run-time array redistribution is usually required to enhance data locality and reduce remote memory access on the distributed memory multicomputers. In general, array distribution can be classified into regular distribution and irregular distribution according to the distribution fashion. Many methods for performing regular array redistribution have been presented in the literature. However, for the heterogeneous computation environment, irregular array redistributions can be used to adjust data assignment at run-time. In this paper, an Essential Cycle Calculation method for irregular array redistribution will be presented. In the ECC method, a processor first computes the source/destination processor/data sets of array elements in the first essential cycle of the local array it owns. From the source/destination processor/data sets of array elements in the first essential cycle, we can construct packing/unpacking pattern tables. Since each essential cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the ECC method, we have implemented this method on an IBM SP2 parallel machine along with the Sequence method. The cost models for these methods are also presented. The experimental results show that the ECC method greatly outperforms the Sequence method for all test samples.

AB - In many parallel programs, run-time array redistribution is usually required to enhance data locality and reduce remote memory access on the distributed memory multicomputers. In general, array distribution can be classified into regular distribution and irregular distribution according to the distribution fashion. Many methods for performing regular array redistribution have been presented in the literature. However, for the heterogeneous computation environment, irregular array redistributions can be used to adjust data assignment at run-time. In this paper, an Essential Cycle Calculation method for irregular array redistribution will be presented. In the ECC method, a processor first computes the source/destination processor/data sets of array elements in the first essential cycle of the local array it owns. From the source/destination processor/data sets of array elements in the first essential cycle, we can construct packing/unpacking pattern tables. Since each essential cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the ECC method, we have implemented this method on an IBM SP2 parallel machine along with the Sequence method. The cost models for these methods are also presented. The experimental results show that the ECC method greatly outperforms the Sequence method for all test samples.

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

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

M3 - Conference contribution

AN - SCOPUS:84906970346

SN - 9806560485

SN - 9789806560482

T3 - 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings

SP - 73

EP - 79

BT - 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings

PB - International Institute of Informatics and Systemics, IIIS

ER -

Bai SW, Yang C-S. Efficient method for irregular array redistribution. In 3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings. International Institute of Informatics and Systemics, IIIS. 2005. p. 73-79. (3rd International Conference on Computing, Communications and Control Technologies, CCCT 2005, Proceedings).