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

• Introduction of MBSP a new model of multi-core and out-of-core computing.
• Comparison of MBSP to other models of computation multi-core or out-of-core.
• Justification of design choices in selecting parameter set of MBSP.
• Analysis of a parallel deterministic regular oversampling sorting algorithm.
• Design and analysis of a sorting algorithm under MBSP.

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)(p,l,g,m,L,G,M) in which (p,l,g)(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)(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)(L,G). A deterministic sorting algorithm is described on this model that is potentially both usable and useful.