Abstract. Nowadays, the evolution of multi-core architectures goes towards increasing the number of cores and levels of cache. Meanwhile, current typical parallel programming models are unable to exploit the potential of these processors eciently. In order to achieve desired performance on these hardwares we need to understand architectural parameters appropriately and also apply them in algorithm design. Computational models such as Multi-BSP, illustrate these parameters and explain adequate methods for designing algorithms on multi-cores. One of the most applicable categories of problems is Divide-and-Conquer (DaC) that needs to be adapted by such model for implementing on these systems. In this paper, we have attempted to make a mapping between DaC tree and the Memory Hierarchy (MH) of multi-core processor. Multi-BSP model inspired us to introduce Multi-DaC programming model. Analogous to Multi-BSP analysis, lower bounds for communication and synchronization costs have been presented in the paper respecting DaC algorithms. The skeletal programming on multi-DaC model complements the effort and hides hardware complexity from implementation of programs and present a simplied programming with high performance. This work is a step towards making multi-core programming easy and tries to obtain correct analysis of DaC algorithm behavior on multi-core architectures.

Keywords