{'fraction_non_alphanumeric': 0.021545319465081723, 'fraction_numerical': 0.008172362555720654, 'mean_word_length': 4.324110671936759, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Anticipated Dynamic Load Balancing Strategy to Parallelize Constraint Programming Search

This paper presents a parallelization of the Constraint Programming solver OR-Tools, using the parallel framework Bobpp. The principle of the parallelization is to assign one sequential OR-Tools solver per core and to communicate work or nodes using the Bobpp global priority queue. As usual the communication or migration of work between solvers is a kind of Work Stealing. But here we have to deal with a specific over cost. By using OR-Tools, it is possible to record the path from the root of the tree to a node so as to stop the search at a precise node. However, to start the search on a sub-tree, the entire path from the root of the main tree to the root of the sub-tree is to be replayed. This leads to additional costs to the parallel search. This paper presents new strategies using a Work Stealing technique to choose good nodes of the search-space and assigns each sub-tree during the execution of the algorithm in order to reduce the extra costs due to OR-Tools solver. These strategies are tested with problem modeled in OR-Tools for imbalanced search tree, despite the additional costs add by OR-Tools a speed-up of 8.04 must to be reached with N-Queens problem using 12 cores and speed-up of 37.73 with Golomb Ruler problem using 48 cores.