Optimizing resource sharing on cooperative execution of algorithms

Alfredo Goldman (1) , Yanik Ngoko (2) , Denis Trystram (3)

1 IME - Instituto de Matemática e Estatística
2 USP - Universidade de São Paulo = University of São Paulo
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation

Solving hard combinatorial problems has always been a challenge. The constant progress in algorithm design and the emergence of powerful large-scale parallel platforms allow to solve a larger number of instances of such problems. As a consequence, many efficient algorithms are available for solving the same problem. However, none of them strictly dominates the others on all the instances. An important problem is to determine an adequate selection of algorithms for solving a given set of instances in order to minimize the total completion time. However, little is known in cooperation between algorithms for an improved global objective. The execution model of algorithms portfolio is a nice framework for studying this question. It consists in executing all the available algorithms concurrently and interrupt them as soon as a solution is found. This model of execution raises however the question of the resources repartition among the algorithms. Interesting directions in this way have been proposed through parallel algorithms portfolio problem. The idea is that it is possible to learn about the resource sharing based on the observation of executions of the algorithms on a set of instances. Parallel algorithms portfolio problems are generally intractable and thus, many heuristics have been proposed to solve them. However, these solutions do not take into account the possibility of sequential algorithms or unknown speed-ups. We propose in this paper a two phases approach for learning resource sharing in the context of a portfolio. The first phase consists in estimating what may be the optimal useful execution workload for each algorithm. This estimation is done through a clustering approach inspired by the resolution of the set cover problem. The second phase consists in minimizing the estimated workload by optimal resource allocation. We propose for this purpose a solution based on dynamic programming. This approach is evaluated experimentally on two settings. In the first setting we simulate the concurrent execution of sequential SAT algorithms. In the second case, we implement a parallel algorithm for CSP based on algorithms portfolio. The experiments clearly exhibit that the proposed approach is suitable for defining an efficient concurrent model of execution.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Alfredo Goldman, Yanik Ngoko, Denis Trystram. Optimizing resource sharing on cooperative execution of algorithms. [Research Report] RR-LIG-021, 2011. ⟨hal-00796872⟩