Optimizing resource sharing on cooperative execution of algorithms

Abstract : 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.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00796872
Contributor : Grégory Mounié <>
Submitted on : Friday, March 15, 2013 - 2:02:00 PM
Last modification on : Wednesday, March 13, 2019 - 3:02:07 PM
Long-term archiving on : Sunday, June 16, 2013 - 4:10:25 AM

File

RR-LIG-021.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00796872, version 1

Collections

Citation

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

Share

Metrics

Record views

426

Files downloads

304