article

A Divide-and-Conquer Algorithm for Irregular Redistribution in Parallelizing Compilers

Authors:

Hui Wang,

Minyi Guo,

Daming WeiAuthors Info & Claims

The Journal of Supercomputing, Volume 29, Issue 2

Pages 157 - 170

https://doi.org/10.1023/B:SUPE.0000026848.34971.27

Published: 01 August 2004 Publication History

Publisher Site

Abstract

In order to achieve higher load balancing, it is necessary to solve irregular block redistribution problems, which are different from regular block-cyclic redistribution. High Performance Fortran version 2 (HPF-2) provides irregular distribution functionalities, such as GEN_BLOCK and INDIRECT. This paper is devoted to develop an efficient algorithm that attempts to obtain near optimal scheduling while satisfying the conditions of minimal message size of total steps and the minimal number of steps for irregular array redistribution. The algorithm intends to decrease the computation costs by dividing the whole block into sub-blocks and solving the sub-problems accordingly, and then merging them together to get final results. Simulation results show that our algorithm has comparable performance with a relocation algorithm developed previously (H. Yook and M. Park. Proceedings of the IASTED International Conference Parallel and Distributed Computing and Systems, Nov. 3–6, MIT, Boston, USA, 1999).

References

[1]

1. M. Guo and I. Nakata. A framework for efficient data redistribution on distributed memory multicomputers. The Journal of Supercomputing, 20(3):243-265, 2001.

Digital Library

Google Scholar

[2]

2. M. Guo, I. Nakata, and Y. Yamashita. Contention-free communication scheduling for array redistribution, Proceedings of the International Conference on Parallel and Distributed Systems, Dec. 1998, pp. 658-667.

Digital Library

Google Scholar

[3]

3. High performance fortran forum. High Performance Fortran Language Specification version 2.0, Rice University, Houston, TX, Jan. 1997.

Digital Library

Google Scholar

[4]

4. E.T. Kalns and L. M. Ni. Processor mapping techniques toward efficient data redistribution. IEEE Transactions on Parallel and Distributed Systems, 6(12): 1234-1247, 1995.

Digital Library

Google Scholar

[5]

5. S. D. Kaushik, C.-H. Huang, and P. Sadayappan. Efficient index set generation for compiling HPF array statements on distributed-memory machines. Journal of Parallel and Distributed Computing, 38(2):237 247, 1996.

Digital Library

Google Scholar

[6]

6. M. Leair, D. Miles, V. Schuster, and M. Wolfe, Euro-Par99 Parallel Processing 5th International Euro-Par Conference, Toulouse, France, Aug. 31 Sept. 3, 1999, Proceedings, Springer-Verlag LNCS 1999.

Google Scholar

[7]

7. S. Lee, H. Yook, M. Koo, and M. Park, Processor reordering algorithms toward efficient GEN_BLOCK redistribution. Proceedings of the 2001 ACM Symposium on Applied Computing, Las Vegas, Nevada, USA, 2001, pp. 539-543.

Digital Library

Google Scholar

[8]

8. Y. W. Lim, P. B. Bhat, and V. Prasanna. Efficient algorithms for block-cyclic redistribution of arrays. IEEE Symposium on Parallel and Distributed Processing, Oct. 1996.

Digital Library

Google Scholar

[9]

9. Y. Pan and J. Shang. Efficient and scalable parallelization of time-dependent Maxwell equations solver using high performance Fortran, The 4th IEEE International Conferenee on Algorithms & Architectures for Parallel Processing, Hong Kong, Dec. 11-13, 2000, pp. 520-531.

Google Scholar

[10]

10. N. Park, V. K. Prasanna, and C. S. Raghavendra. Efficient algorithms for block-cyclic array redistribution between processor sets. IEEE Transactions on Parallel and Distributed Systems, 10(12): 1217-1239, 1999.

Digital Library

Google Scholar

[11]

11. PGHPF, a High Performance Fortran compiler, http://www.pgroup.com/products/pghpfindex.htm.

Google Scholar

[12]

12. S. Ramaswamy, B. Simons, and P. Banerjee. Optimizations for efficient array redistribution on distributed memory multicomputers. Journal of Parallel and Distributed Computing, 38:217-228, 1996.

Digital Library

Google Scholar

[13]

13. R. Thakur, A. Choudhary, and G. Fox. Runtime array redistribution in HPF programs. Proceedings Scalable High Performance Computing Conference, May 1994, pp. 309-316.

Crossref

Google Scholar

[14]

14. H. Yook and M. Park. Scheduling GEN_BLOCK array redistribution, Proeeedings of the IASTED International Conference Parallel and Distributed Computing and Systems, Nov. 3-6, 1999, MIT, Boston, USA.

Google Scholar

Cited By

View all

Hsu CCuzzocrea AChen S(2011)CADProceedings of the 4th international conference on Data management in grid and peer-to-peer systems10.5555/2040132.2040147(120-134)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.5555/2040132.2040147
Yu C(2007)On the complexity of the max-edge-coloring problem with its variantsProceedings of the First international conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies10.5555/2399256.2399288(350-361)Online publication date: 7-Apr-2007
https://dl.acm.org/doi/10.5555/2399256.2399288
Chen SHsu C(2007)ISOProceedings of the 9th international conference on Parallel Computing Technologies10.5555/2392094.2392149(507-515)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.5555/2392094.2392149
Show More Cited By

Index Terms

A Divide-and-Conquer Algorithm for Irregular Redistribution in Parallelizing Compilers
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Scheduling

Recommendations

Message Scheduling for Irregular Data Redistribution in Parallelizing Compilers

In parallelizing compilers on distributed memory systems, distributions of irregular sized array blocks are provided for load balancing and irregular problems. The irregular data redistribution is different from the regular block-cyclic redistribution. ...
Parallelizing compilers: implementation and effectiveness
Divide-and-conquer programming on MIMD computers
IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

We have developed a programming template to implement divide and conquer algorithms on MIMD computers. The template is based on the parallel divide and conquer function of Z.G. Mou and P. Hudak (1988). We explore the programmability and performance of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Supercomputing

The Journal of Supercomputing Volume 29, Issue 2

August 2004

101 pages

ISSN:0920-8542

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 August 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hsu CCuzzocrea AChen S(2011)CADProceedings of the 4th international conference on Data management in grid and peer-to-peer systems10.5555/2040132.2040147(120-134)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.5555/2040132.2040147
Yu C(2007)On the complexity of the max-edge-coloring problem with its variantsProceedings of the First international conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies10.5555/2399256.2399288(350-361)Online publication date: 7-Apr-2007
https://dl.acm.org/doi/10.5555/2399256.2399288
Chen SHsu C(2007)ISOProceedings of the 9th international conference on Parallel Computing Technologies10.5555/2392094.2392149(507-515)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.5555/2392094.2392149
Hsu CChen SLan C(2007)Scheduling contention-free irregular redistributions in parallelizing compilersThe Journal of Supercomputing10.1007/s11227-006-0024-140:3(229-247)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1007/s11227-006-0024-1
Hsu CChen MYang CLi K(2006)Optimizing Communications of Dynamic Data Redistribution on Symmetrical Matrices in Parallelizing CompilersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2006.16217:11(1226-1241)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TPDS.2006.162
Hsu CLan CChen S(2006)Optimizing scheduling stability for runtime data alignmentProceedings of the 2006 international conference on Emerging Directions in Embedded and Ubiquitous Computing10.1007/11807964_83(825-835)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1007/11807964_83
Hsu C(2005)Sparse Matrix Block-Cyclic Realignment on Distributed Memory MachinesThe Journal of Supercomputing10.1007/s11227-005-0247-633:3(175-196)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1007/s11227-005-0247-6
Hsu CChen SLan CYang CLi K(2005)Scheduling convex bipartite communications toward efficient GEN_BLOCK transformationsProceedings of the Third international conference on Parallel and Distributed Processing and Applications10.1007/11576235_44(419-424)Online publication date: 2-Nov-2005
https://dl.acm.org/doi/10.1007/11576235_44
Yu KChen CHsu CYu CLiang C(2005)Contention-Free communication scheduling for irregular data redistribution in parallelizing compilersProceedings of the 6th international conference on Advanced Parallel Processing Technologies10.1007/11573937_13(101-110)Online publication date: 27-Oct-2005
https://dl.acm.org/doi/10.1007/11573937_13
Yu CHsu CYu KLiang CChen C(2005)Irregular redistribution scheduling by partitioning messagesProceedings of the 10th Asia-Pacific conference on Advances in Computer Systems Architecture10.1007/11572961_24(295-309)Online publication date: 24-Oct-2005
https://dl.acm.org/doi/10.1007/11572961_24
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Message Scheduling for Irregular Data Redistribution in Parallelizing Compilers

Parallelizing compilers: implementation and effectiveness

Divide-and-conquer programming on MIMD computers

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations