dc.contributor |
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
dc.contributor.author |
Blesa Aguilera, Maria Josep |
dc.contributor.author |
Hernàndez, Lluís |
dc.contributor.author |
Xhafa Xhafa, Fatos |
dc.date |
2000-12 |
dc.identifier.citation |
Blesa, M., Hernàndez, L., Xhafa, F. "Parallel skeletons for tabu search method". 2000. |
dc.identifier.uri |
http://hdl.handle.net/2117/97623 |
dc.language.iso |
eng |
dc.relation |
LSI-00-81-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica |
dc.subject |
Optimization |
dc.subject |
Tabu search |
dc.subject |
Parallelism |
dc.subject |
Generic programming |
dc.subject |
Components |
dc.title |
Parallel skeletons for tabu search method |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
In this paper we present two parallel skeltons for Tabu Search
method --a well known meta-heuristic designed for finding
approximate solution of combinatorial optimization problems.
Our parallel skeletons are designed and implemented using the generic
parallel programming paradigm. The first skeleton is based on
independent runs while the second in the classical master-slave
model. Our starting point is the design and implementation
of a sequential skeleton that is 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 a sequential
implementation of the problem. The skeletons, however, require
from the user a sequential instantiation of tabu search method for the
problem at hand. 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 programming and object oriented programming paradigms. We have
instantiated the two skeletons for the 0-1 Multidimensional Knapsack
problem
and have observed the claimed properties of the skeletons |