In this talk, we present benchmarks obtained by the execution of several applications written with the BOB environment on sequential and parallel machines. This environment has the double goal of allowing on the one hand the Combinatorial Optimization community to implement their applications without worrying about the architecture of the machines and benefiting the advantages provided by parallelism. On the other hand, BOB offers to the community of Parallelism a set of benchmark composed by efficient algorithms of Combinatorial Optimization for its parallelization methods and/or tools.

To achieve this double goal, the BOB library is founded on the notion of global priority queue which makes the parallelization methods independent from the applications, and vice-versa. We describe for this global priority queue different implementation models according to the architecture of machines (serial, parallel with shared or distributed memory). Recent developments have shown that priority queue is not the only data structure needed for space search. Some applications need specific Priority queue operation semantics e.g. data structures other than simple priority queue, such as search structure.

We show how this particular case, could be implemented and which conceptual changes must be made in BOB.

A description a the BOB Library could be reached at

The bob team could also be reached by email at bobteam@prism.uvsq.fr.

This is joint work with Catherine Roucairol.

Back to Workshop Schedule

1996-1997 Mathematics in High Performance Computing