article

H-BSP: A Hierarchical BSP Computation Model

Authors:

Hojung Cha,

Dongho LeeAuthors Info & Claims

The Journal of Supercomputing, Volume 18, Issue 2

Pages 179 - 200

https://doi.org/10.1023/A:1008113017444

Published: 01 February 2001 Publication History

Publisher Site

Abstract

This paper presents a new parallel computing model, called H-BSP, which adds a hierarchical concept to the BSP(Bulk Synchronous Parallel) computing model. An H-BSP program consists of a number of BSP groups which are dynamically created at run time and executed in a hierarchical fashion. H-BSP allows algorithm designers to develop more efficient algorithms by utilizing processor locality in the program. Based on the distributed memory model, H-BSP provides a group-based programming paradigm and supports Divide & Conquer algorithms efficiently. This paper describes the structure of the H-BSP model, complexity analysis and some examples of H-BSP algorithm. Also presented is the performance characteristics of H-BSP algorithms based on the simulation analysis. Simulation results show that H-BSP takes advantages of processor locality and performs well in low bandwidth networks or in a constant-valence architecture such as 2-dimensional mesh. It is also proved that H-BSP can predict algorithm performance better than BSP, due to its locality-preserving nature.

References

[1]

1. Todd Heywood and Sanjay Ranka. A practical hierarchical model of parallel computation. 1. The model. Journal of Parallel and Distributed Computing, 16:212-232, 1992.

Crossref

Google Scholar

[2]

2. W.F. McColl. General purpose parallel computing. In A. Gibbson and P. Spirakis, eds., Lectures on Parallel Computation, pp. 337-391. Cambridge University Press, Cambridge, UK, 1993.

Digital Library

Google Scholar

[3]

3. D.B. Skillicorn. Architecture-independent parallel computation. IEEE Computer, 23:38-50, 1990.

Digital Library

Google Scholar

[4]

4. D. Culler, R. Karp, D. Patternson, A. Sahay, K. Schauser, E. Santos, R. Subramonian, and T. von Eicken. LogP: Towards a realistic model of parallel computation. In Proceedings of the 4th ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming, 1993, pp. 1-12.

Digital Library

Google Scholar

[5]

5. Susanne E. Hambrusch and Ashfaq A. Khokhar. C<sup>3</sup> : A parallel model for coarse grained machines. Technical report, Purdue University, January 1995.

Google Scholar

[6]

6. Leslie G. Valiant. A bridging model for parallel computation. Communication of the ACM, 33:103-111, 1990.

Digital Library

Google Scholar

[7]

7. Thomas Cheatham, Amr Fahmy, Dan C. Stefanescu, and Leslie G. Valiant. Bulk synchronous parallel computing--a paradigm for transportable software. Technical report TR-36-94, Harvard University, December 1994.

Google Scholar

[8]

8. Christoph Kebler and Helmut Seidl. Making FORK practical. In Workshop on Models of Parallel Computation, Universiteit Utrecht, January 1995.

Google Scholar

[9]

9. Simon Knee. Program development and performance prediction on BSP machines using opal. Technical report PRG-TR-18-1994, Oxford University, August 1994.

Google Scholar

[10]

10. W.F. McColl. BSP Programming. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, May 1994.

Google Scholar

[11]

11. B.A. Wagner. Hyperquicksort: A fast sorting algorithm for hypercubes. In Proceedings of the Second Conference on Hypercube Multiprocessors, 1987, pp. 292-299.

Google Scholar

[12]

12. Todd Heywood and Sanjay Ranka. A practical hierarchical model of parallel computation: Binary tree and FFT algorithms. Journal of Parallel and Distributed Computing, 16:233-249, 1992.

Crossref

Google Scholar

Cited By

View all

Tian ZLindner PNissl MKoch CTannen V(2023)Generalizing Bulk-Synchronous Parallel Processing for Data Science: From Data to Threads and Agent-Based SimulationsProceedings of the ACM on Management of Data10.1145/35892961:2(1-28)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589296
Allombert VGava FTesson J(2018)Multi-MLInternational Journal of Parallel Programming10.1007/s10766-016-0417-645:2(340-361)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10766-016-0417-6
McCune RWeninger TMadey G(2015)Thinking Like a VertexACM Computing Surveys10.1145/281818548:2(1-39)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2818185
Show More Cited By

Index Terms

H-BSP: A Hierarchical BSP Computation Model

Recommendations

Portable and Efficient Parallel Computing Using the BSP Model

The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software ...
MPPs and clusters for scalable computing
ISPAN '96: Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks

This article assess the state-of-the-art technology in massively parallel processors (MPPs) and clusters of workstations (COWs) for scalable parallel computing. We evaluate the IBM SP2, the Intel Paragon, the Cray T3D/T3E, and the ASCI TeraFLOPS system ...
Fully Scalable Fault-Tolerant Simulations for BSP and CGM

In this paper we consider general simulations of algorithms designed for fully operational BSP and CGM machines on machines with faulty processors. The BSP (or CGM) machine is a parallel multicomputer consisting of p processors for which a memory of n ...

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 18, Issue 2

Feb. 1, 2001

104 pages

ISSN:0920-8542

Editor:
Hamid Arabnia
University of Georgia

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tian ZLindner PNissl MKoch CTannen V(2023)Generalizing Bulk-Synchronous Parallel Processing for Data Science: From Data to Threads and Agent-Based SimulationsProceedings of the ACM on Management of Data10.1145/35892961:2(1-28)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589296
Allombert VGava FTesson J(2018)Multi-MLInternational Journal of Parallel Programming10.1007/s10766-016-0417-645:2(340-361)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s10766-016-0417-6
McCune RWeninger TMadey G(2015)Thinking Like a VertexACM Computing Surveys10.1145/281818548:2(1-39)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2818185
Shih WYou YHuang CLee J(2014)Compiler Optimization for Reducing Leakage Power in Multithread BSP ProgramsACM Transactions on Design Automation of Electronic Systems10.1145/266811920:1(1-34)Online publication date: 18-Nov-2014
https://dl.acm.org/doi/10.1145/2668119
Chen RDing XWang PChen HZang BGuan HPlale BRipeanu MCappello FXu D(2014)Computation and communication efficient graph processing with distributed immutable viewProceedings of the 23rd international symposium on High-performance parallel and distributed computing10.1145/2600212.2600233(215-226)Online publication date: 23-Jun-2014
https://dl.acm.org/doi/10.1145/2600212.2600233

Abstract

References

Cited By

Index Terms

Recommendations

Portable and Efficient Parallel Computing Using the BSP Model

MPPs and clusters for scalable computing

Fully Scalable Fault-Tolerant Simulations for BSP and CGM

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations