By emerging the multi-core architectures, the efficient exploitation of these architectures becomes a very serious issue. The evolution of these architectures goes towards increasing the number of cores and levels of cache. Since current typical parallel tools such as parallel programming languages are unable to exploit the potential of these processors efficiently so it is needed to provide appropriate tools. One of ways to achieve desired performance on these architectures is a understanding of hardware parameters appropriately and also apply them in software/algorithm design. Bridging computational models such as Multi-BSP, illustrate these parameters and explain adequate methods for designing algorithms on these hardware. One of applicable categories of problems is Branchand-Bound (BaB) that needs to adaption of such models for effective implementing on these systems. In this paper, it has been attempted to make a mapping between BaB run-time tree and the Memory hierarchy Tree (MT) of a multi-core processor. The Multi-BSP model inspired us to introduce the Multi-BaB model. Analogous to Multi-BSP analysis, bounds for communication and synchronization costs have been presented in the paper respecting the BaB algorithms. This work is a step towards making multi-core programming efficient and tries to obtain correct analysis of BaB algorithm behavior on multi-core architectures.

Keywords