H-BSP: a hierarchical BSP computation model

Hojung Cha, Dongho Lee

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)179-200
Number of pages22
JournalJournal of Supercomputing
Issue number2
Publication statusPublished - 2001 Feb

Bibliographical note

Funding Information:
This work was supported by grant No. 95-0100-19-01-3 from the Basic Research Program of the Korea Science and Engineering Foundation.

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'H-BSP: a hierarchical BSP computation model'. Together they form a unique fingerprint.

Cite this