Article

Grid-enabled parallel divide-and-conquer: theory and practice

Author:

Chun-Hsi HuangAuthors Info & Claims

SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

Pages 865 - 869

https://doi.org/10.1145/508791.508959

Published: 11 March 2002 Publication History

Abstract

This paper presents a general methodology for the communication-efficient parallelization of graph algorithms using the divide-and-conquer approach. The algorithm is communication-free in the conquer stage and uses only a small amount of messages while partitioning the input. Specifically, a practical parallel algorithm with full scalability, based on the BSP model, for finding Hamiltonian paths in tournaments is presented.Experiments have been carried out on two architecturally different systems, which stand for the possible site variety of a computational grid. These include a distributed-memory system: a Solaris cluster of 32 Sun Ultra5 computers on Myrinet network and a distributed shared-memory system: an SGI Origin 2000 with 32 R10000 processors, using MPICH-GM and MPT, respectively. Both implementations are compatible with the grid-enabled MPI implementation, MPICH-G2.

References

[1]

A. Aggarwal, B. Chazelle, L. J. Guibas C. O'Dunlaing, and C. K. Yap. Parallel Computational Geometry. Algorithmica, 3:293-327, 1988.

Digital Library

[2]

Selim G. Akl. Parallel Computation, Models and Methods. Prentice Hall, 1997.

Digital Library

[3]

S. G. Akl. Optimal Parallel Algorithms for Computing Convex Hulls and for Sorting. Computing, 33:1-11, 1984.

Digital Library

[4]

B. A. Chalmers and S. G. Akl. Optimal Parallel Algorithms for a Transportation Problem. In Proceedings of the Canadian Conference on Electrical and Computing Engineering, pages 36.1.1-36.1.6, 1991.

[5]

L. W. Beineke and R. S. Wilson. Selected Topics in Graph Theory. Academic Press, New York/London, 1978.

[6]

I. Foster and C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. Intl J. Supercomputer Applications, 11(2):115-128, 1997.

Digital Library

[7]

A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, 1988.

Digital Library

[8]

Michael T. Goodrich. Communication-Efficient Parallel Sorting. In Proc. 28th ACM Symp. on Theory of Computing, pages 247-256, 1996.

Digital Library

[9]

Chun-Hsi Huang and Xin He. Finding Hamiltonian Paths in Tournaments on Clusters --- A Provably Communication-Efficient Approach. In Proceedings of the 16th ACM Symposium on Applied Computing, Las Vegas, pages 549-553, 2001.

Digital Library

[10]

S. Lakshmivarahan and S. K. Dhall. Analysis and Design of Parallel Algorithms: Arithmetic and Matrix Problems. McGraw-Hill, 1990.

Digital Library

[11]

W. F. McColl. Special Purpose Parallel Computing. In ALCOM Spring School on Parallel Computing, Cambridge International Series on Parallel Computation. Cambridge University Press., 1991.

Digital Library

[12]

Henk Meijer and Selim G. Akl. Optimal Computation of Prefix Sums on a Binary Tree of Processors. International Journal of Parallel Programming, 16(2):127-136, 1987.

Digital Library

[13]

L. Redei. Ein Kombinatorischer Satz. Acta Litt. Sci. Szeged, 7:39-43, 1934.

[14]

J. H. Reif. Synthesis of Parallel Algorithms. Morgan Kaufmann, 1993.

Digital Library

[15]

D. Soroker. Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament. Journal of Algorithms, 9:276-286, 1988.

Digital Library

[16]

Leslie G. Valiant. A Bridging Model for Parallel Computation. Communications of the ACM, 33(8): 103-111, 1990.

Digital Library

Cited By

Huang C(2017)REU Site: Bio-Grid Initiatives for interdisciplinary research and educationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.01.012105(174-182)Online publication date: Jul-2017
https://doi.org/10.1016/j.jpdc.2017.01.012
Huang CPrasad S(2015)REU siteProceedings of the Workshop on Education for High-Performance Computing10.1145/2831425.2831429(1-8)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2831425.2831429

Index Terms

Grid-enabled parallel divide-and-conquer: theory and practice

Recommendations

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 ...
Parallel divide-and-conquer scheme for 2D Delaunay triangulation: Research Articles

This work describes a parallel divide-and-conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub-block triangulations are merged. Finding the affected zone can ...
Parallel Quicksort Using Fetch-And-Add

A parallelization of the Quicksort algorithm that is suitable for execution on a shared memory multiprocessor with an efficient implementation of the fetch-and-add operation is presented. The partitioning phase of Quicksort, which has been considered a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

March 2002

1200 pages

ISBN:1581134452

DOI:10.1145/508791

Conference Chair:
Gary B. Lamont
Air Force Institute of Technology, USA
,
Program Chairs:
Hisham Haddad
Kennesaw State Univ., USA
,
George Papadopoulos
Univ. of Cyprus, Cyprus
,
Publications Chair:
Brajendra Panda
University of Arkansas, USA

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SAC02

Sponsor:

SIGAPP

SAC02: 2002 ACM Symposium on Applied Computing

March 11 - 14, 2002

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
486
Total Downloads

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

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang C(2017)REU Site: Bio-Grid Initiatives for interdisciplinary research and educationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.01.012105(174-182)Online publication date: Jul-2017
https://doi.org/10.1016/j.jpdc.2017.01.012
Huang CPrasad S(2015)REU siteProceedings of the Workshop on Education for High-Performance Computing10.1145/2831425.2831429(1-8)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2831425.2831429

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten