Solving combinatorial problems using a parallel framework

This paper presents a new IBobpp framework which is an improvement of a high level parallel programming framework called Bobpp to optimize the performance of solving combinatorial problems. The Bobpp parallel computation model is as the majority of parallel models proposed in the context of tree search algorithms with node oriented parallelization, meaning that at every step of the algorithm, each thread gets one node from a unique global pool of non-explored nodes, generates the child nodes, and reinserts them into the pool to be explored later. This classical model has two drawbacks. First, the use of many threads creates a bottleneck problem. Second, grabbing a node causes memory contention problem when many nodes are generated and inserted into the same pool. To solve these problems, IBobpp framework proposes three solutions. The first consists of using multiple pools of nodes shared between all threads. The second solution consists of using a new computation model. The third solution consists of hybridization of the two previous solutions. Preliminary result shows that IBobpp gives a good result using the third solution.