Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

H-BSP: A Hierarchical BSP Computation Model

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Reference

  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.

    Google Scholar 

  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.

    Google Scholar 

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

    Google Scholar 

  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. Susanne E. Hambrusch and Ashfaq A. Khokhar. C 3: A parallel model for coarse grained machines. Technical report, Purdue University, January 1995.

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

    Google Scholar 

  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. Christoph Kebler and Helmut Seidl. Making FORK practical. In Workshop on Models of Parallel Computation, Universiteit Utrecht, January 1995.

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

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

  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. 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.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Kwangwoon University, Seoul, 139-701, Korea

    Hojung Cha & Dongho Lee

Authors
  1. Hojung Cha
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dongho Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cha, H., Lee, D. H-BSP: A Hierarchical BSP Computation Model. The Journal of Supercomputing 18, 179–200 (2001). https://doi.org/10.1023/A:1008113017444

Download citation

  • Issue Date:

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

Search

Navigation