Extending the BSP model for multi-core and out-of-core computing: MBSP

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We present an extension of the bulk-synchronous parallel (BSP) model to abstract and model parallelism in the presence of multiple memory hierarchies and multiple cores. We call the new model MBSP for multi-memory BSP. The BSP model has been used to model internal memory parallel computers; MBSP retains the properties of BSP and in addition can abstract not only traditional external memory-supported parallelism (e.g. that uses another level of slower memory) but also multi-level cache-based memory hierarchies such as those present in multi-core systems. Present day multi-core systems are limited parallelism architectures with fast inter-core communication but limited fast memory availability. Abstracting the programming requirements of such architectures in a useful and usable manner is the objective of introducing MBSP. We propose multi-core program and algorithm design that measures resource utilization through a septuplet (p,l,g,m,L,G,M) in which (p,l,g) are the BSP parameters for modeling processor component size and interprocessor communication through latency-based and throughput-based cost mechanisms, and (m,L,G,M) are the new parameters that abstract additional memory hierarchies. Each processor component is attached to a memory of size M, and there are also m memory-units accessing a slower memory of unlimited size of latency-based and throughput-based cost (L,G). A deterministic sorting algorithm is described on this model that is potentially both usable and useful.

Original languageEnglish (US)
Pages (from-to)90-102
Number of pages13
JournalParallel Computing
StatePublished - Jan 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


  • Bulk-synchronous parallel
  • Cost model
  • External memory
  • Multi-core
  • Parallel computing


Dive into the research topics of 'Extending the BSP model for multi-core and out-of-core computing: MBSP'. Together they form a unique fingerprint.

Cite this