The MALLBA project is an effort to develop, in an integrated way, a library of skeletons for combinatorial optimization (including exact, heuristic and hybrid methods) that can deal with parallelism in a user-friendly and, at the same time, efficient manner. Its three target environments are sequential computers, LANs of workstations and WANs. The main features of MALLBA are:
- Integration of all the skeletons under the same design principles.
- Facility to switch from sequential to parallel optimization engines. By providing sequential implementations users obtain parallel implementations.
- Cooperation between engines makes possible to provide more powerful hybrid engines.
- Ready to use on commodity machines.
- Flexible and extensible software architecture. New skeletons can easily be added, alternative communication layers can be used, etc.
Mallba skeletons are based on the separation of two concepts: the concrete problem to be solved and the general resolution method to be used. They can be seen as generic templates that just need to be instantiated with the features of a problem in order to solve it. All features related to the selected generic resolution method and its interaction with the concrete problem are implemented by the skeleton. While the particular features related to the problem must be given by the user, the knowledge to parallelize the execution of the resolution method is implemented in the skeleton, so that users do not need to deal with parallelism issues.
The design of the Mallba library focuses on easy to use skeletons and general and efficient implementations. To achieve both objectives, the C++ programming language was selected due to its high level, modularity, flexibility and efficiency features. We have reduced to a minimum the use of inheritance and virtual methods in order to provide better efficiency and ease of use. To instantiate most problems, a basic knowledge of C++ is enough, and only sequential code without side effects is needed.
Skeletons are implemented by a set of required and provided C++ classes that represent an abstraction of the entities participating in the resolution method. The provided classes implement internal aspects of the skeleton in a problem-independent way. The required classes specify information and behavior related to the problem. This conceptual separation allows us to define required classes with a fixed interface but without any implementation, so that provided classes can use required classes in a generic way.
More specifically, each skeleton includes the Problem and Solution required classes, that encapsulate the problem-dependent entities needed by the resolution method. The Problem class abstracts the features of the problem that are relevant to the selected optimization method. The Solution class abstracts the features of the feasible solutions that are relevant to the selected resolution method. Depending on the skeleton, other classes may be required. On the other hand, each skeleton offers two provided classes: Solver and SetUpParams. The former abstracts the selected resolution method. The later contains the setup parameters needed to perform the execution (e.g. number of iterations, number of independent runs, parameters guiding the search, etc.). The Solver class provides methods to run the resolution scheme and methods to consult its progress or change its state. The only information the solver needs is an instance of the problem to solve and the setup parameters. In order to enable an skeleton to have different solver engines, the Solver class defines a unique interface and provides several subclasses that provide different sequential and parallel implementations (Solver_Seq, Solver_Lan and Solver_Wan). In Fig. 1 is shown the common design of Mallba skeletons.
The implementation of each skeleton is contained in three files:
- <skeleton>.hh: The file containing the definition of all classes (provides and requires).
- <skeleton>.pro.cc: The file containing the source code of the classes needed for the internal implementation of the method.
- <skeleton>.req.cc: The source file where all the required classes will be implemented.
In additional, the user must configure the method parameters in the file <skeleton>.cfg.
There are several basic steps to building and installing the Mallba Library:
1. Download the source file (download)
2. You need to have installed MPICH (you can get it from MPICH site)
3. Unpack the source
4. Change to the toplevel directory
5. Configure the Mallba Library by editing the environment file.
6. Build the Mallba Library by running
After the installation, the Mallba directory has the following content :
-rw-r--r-- 1 user users 378 sep 24 09:39 Makefile drwxr-xr-x 4 user users 4096 sep 24 09:48 ProblemInstances
-rw-r--r-- 1 user users 345 sep 24 16:29 environment
drwxr-xr-x 2 user users 4096 sep 24 16:43 inc
drwxr-xr-x 2 user users 4096 sep 24 17:49 lib
drwxr-xr-x 5 user users 4096 sep 24 09:41 rep
drwxr-xr-x 2 user users 4096 sep 24 17:49 src
The /ProblemInstances directory containing the instances for the problems and the /rep directory containing the implementation of the skeletons and the example problems.