Generalized basic cycle calculation method for efficient array redistribution

Yeh Ching Chung, Sheng Wen Bai, Ching Hsien Hsu, Chu Sing Yang

研究成果: Paper

摘要

In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t)×P) in the source distribution and lcm(sP, tQ)/(gcd(s, t)×Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables. Based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multi-dimensional array redistributions is also presented.

原文English
頁面640-647
頁數8
出版狀態Published - 1998 十二月 1
事件Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS - Tainan, China
持續時間: 1998 十二月 141998 十二月 16

Other

OtherProceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS
城市Tainan, China
期間98-12-1498-12-16

指紋

Parallel processing systems
Costs

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

引用此文

Chung, Y. C., Bai, S. W., Hsu, C. H., & Yang, C. S. (1998). Generalized basic cycle calculation method for efficient array redistribution. 640-647. 論文發表於 Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .
Chung, Yeh Ching ; Bai, Sheng Wen ; Hsu, Ching Hsien ; Yang, Chu Sing. / Generalized basic cycle calculation method for efficient array redistribution. 論文發表於 Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .8 p.
@conference{d2fe45849988435f818c3f6649fd8829,
title = "Generalized basic cycle calculation method for efficient array redistribution",
abstract = "In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t)×P) in the source distribution and lcm(sP, tQ)/(gcd(s, t)×Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables. Based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multi-dimensional array redistributions is also presented.",
author = "Chung, {Yeh Ching} and Bai, {Sheng Wen} and Hsu, {Ching Hsien} and Yang, {Chu Sing}",
year = "1998",
month = "12",
day = "1",
language = "English",
pages = "640--647",
note = "Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS ; Conference date: 14-12-1998 Through 16-12-1998",

}

Chung, YC, Bai, SW, Hsu, CH & Yang, CS 1998, 'Generalized basic cycle calculation method for efficient array redistribution', 論文發表於 Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, 98-12-14 - 98-12-16 頁 640-647.

Generalized basic cycle calculation method for efficient array redistribution. / Chung, Yeh Ching; Bai, Sheng Wen; Hsu, Ching Hsien; Yang, Chu Sing.

1998. 640-647 論文發表於 Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .

研究成果: Paper

TY - CONF

T1 - Generalized basic cycle calculation method for efficient array redistribution

AU - Chung, Yeh Ching

AU - Bai, Sheng Wen

AU - Hsu, Ching Hsien

AU - Yang, Chu Sing

PY - 1998/12/1

Y1 - 1998/12/1

N2 - In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t)×P) in the source distribution and lcm(sP, tQ)/(gcd(s, t)×Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables. Based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multi-dimensional array redistributions is also presented.

AB - In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t)×P) in the source distribution and lcm(sP, tQ)/(gcd(s, t)×Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables. Based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multi-dimensional array redistributions is also presented.

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

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

M3 - Paper

AN - SCOPUS:0032295678

SP - 640

EP - 647

ER -

Chung YC, Bai SW, Hsu CH, Yang CS. Generalized basic cycle calculation method for efficient array redistribution. 1998. 論文發表於 Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .