Abstract:
|
In this paper we present two parallel skeletons for Tabu Search method -- a well known meta-heuristic for approximately solving combinatorial optimization problems. Our parallel skeletons are designed and
implemented using the generic parallel programming paradigm. The first
skeleton is based on independent runs model with search strategies
while the second is a master-slave model with neighborhood
partition. Our starting point to obtain these skeletons was the design
and implementation of a sequential skeleton that was used later as
basis for the two parallel skeletons. Both skeletons provide the user
with the followings: (a) permit to obtain parallel implementations of
tabu search method for concrete combinatorial optimization problems
from existing sequential implementations; (b) there is no need for the
user to know neither parallel programming nor communication libraries;
(c) the parallel implementation for a concrete problem is obtained
automatically from the existing sequential implementation of the
problem. The skeletons are implemented in C++ using MPI as a
communication library and offer several properties such as a
genericity, flexibility, component reuse, robustness and time savings,
mainly due to the generic and object oriented programming
paradigms. We have instantiated the two skeletons for the 0-1
Multidimensional Knapsack problem and report extensive experimental
results. |