Nothing Special   »   [go: up one dir, main page]

skip to main content
article

H-BSP: A Hierarchical BSP Computation Model

Published: 01 February 2001 Publication History

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.
[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.
[3]
3. D.B. Skillicorn. Architecture-independent parallel computation. IEEE Computer, 23:38-50, 1990.
[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.
[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.
[6]
6. Leslie G. Valiant. A bridging model for parallel computation. Communication of the ACM, 33:103-111, 1990.
[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.
[8]
8. Christoph Kebler and Helmut Seidl. Making FORK practical. In Workshop on Models of Parallel Computation, Universiteit Utrecht, January 1995.
[9]
9. Simon Knee. Program development and performance prediction on BSP machines using opal. Technical report PRG-TR-18-1994, Oxford University, August 1994.
[10]
10. W.F. McColl. BSP Programming. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, May 1994.
[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.
[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.

Cited By

View all

Recommendations

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
Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2001

Author Tags

  1. BSP
  2. analysis
  3. computation model
  4. processor locality
  5. scalable computing

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (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
  • (2018)Multi-MLInternational Journal of Parallel Programming10.1007/s10766-016-0417-645:2(340-361)Online publication date: 28-Dec-2018
  • (2015)Thinking Like a VertexACM Computing Surveys10.1145/281818548:2(1-39)Online publication date: 12-Oct-2015
  • (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
  • (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

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media