A Framework for the Design of Parallel Adaptive Libraries on Hard Computational Problems

Abstract. In this work, we present the Adaptive Multi-Selection Frame-work (called AMF). AMF is an API built for helping designers to develop optimized combinations of multiple algorithms solving the same problem in function of the physical architecture and algorithm behavior. AMF of-fers a simple and generic model for developing automatic combination of algorithms. In this model, the user needs to specify the set of algorithms to be combined and a representative benchmark of instances of the prob-lem solved by the algorithms. This generic solution has advantages over many existing solutions for making automatic combination that are spe-cific to a fixed set of algorithms or computational problems. Automatic combinations of algorithms are made in AMF with the multi-selection technique. For each instance of a computational problem, its resolution under multi-selection includes a selection of a subset of candidate al-gorithms followed by a concurrent run of the selected algorithms with a smart resource sharing. The resource sharing is decided according to the physical architecture, the problem instance and the time allowed to compute it. The multi-selection strategy provides excellent results when there is a large variance of execution time per instance. The actual im-plementation of AMF is built for shared memory architectures. However, it can be extended to distributed ones. The AMF principles have been validated in particular on the well-known Constraint Satisfaction Prob-lem