Extending the BSP model for multi-core and out-of-core computing: 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) 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.