E:2116

Master Thesis Seminar: Parallel and Distributed Search in Constraint Programmin

Date: June 01, 2006 (Thursday) at 10:15

By: Carl Christian Rolf

Abstract
Constraint programming is a growing field of research and is
increasingly interesting to the software industry. It is considered
the leading method of solving discrete optimization problems, such as
scheduling. The biggest issue with optimization problems is that they
often have an exponential time complexity. Both parallelization and
distribution can be used to make more problems solvable in acceptable
time.
In this thesis parallel and distributed extensions to a constraint
solver have been implemented and evaluated. We have used a solver
written entirely in Java, which facilitated fast development. The main
goal of this work was to explore whether such extensions are feasible
with regard to the timeframe and if they are useful from a performance
perspective.
The hardware development, at time of writing, has lately taken a turn
towards processors with several cores. In order to harness the power
of the next generation hardware, parallelization of constraint solvers
are necessary. Further, the internet and improved network technologies
provide a means of achieving high performance at low cost.
The issues that need addressing when parallelizing or distributing a
program are the cost of communication between processes and load
balancing. This thesis focuses on the cost of copying and
serialization of objects in a modern language with automatic
memory management.

Room: E:2116

Last modified Dec 9, 2011 12:59 pm

01059