Parallel Computing on Loosely-coupled platforms
Sponsor: NASA Goddard Space Flight Centre
Participants
Faculty
Summary
Many combinatorial
optimization problems often exhibit degrees of irregularity which make them
challenging to solve on parallel systems. The irregularities in these
problems can typically be traced to the use of control structures, data
representations which are unstructured or become unbalanced, and
communications requirements that are unknown or unpredicatable. Our
researchtowards
developing parallel implementations of a cutting stock optimization algorithm
has demonstrated that efficient solutions on workstation clusters can be
obtained by addressing the problem's irregularities.
Our current research focuses on two problems
- new approaches for solving cutting and packing problems in parallel,
including the use of genetic algorithms
- exploring efficient ways to solve these (and similar branch-and-bound
problems) on peer-to-peer platforms (dynamic networks of computers
connected by a WAN)
Publications
- C. L. Valenzuela and P. Y. Wang, ``VLSI Placement and Area Optimization
Using a Genetic Algorithm to Breed Normalized Postfix Expressions'', in
IEEE Transactions on Evolutionary Computation, August 2002,
390-401.
- C.L. Valenzuela and P.Y. Wang,
Data Set Generation for Non-Slicing Rectangular Placement Problems,
2001.
- C.L. Valenzuela and P.Y. Wang, "Data Set Generation for
Rectangular Placement Problems," CS Technical Report TR 99-05, Full
version appeared in the European Journal of Operational Research,
Vol. 134, No. 2, 2001, pp. 378-391.
- Lisa Nicklas, Robert Atkins, Sanjeev Setia and Pearl Wang, ``Design and
Implementation of a Parallel Solution to the Cutting Stock Problem'', in
Concurrency: Practice & Experience, October 1998. gzipped
postscript
- Lisa Nicklas, Robert Atkins, Sanjeev Setia and Pearl Wang, ``A Parallel
Solution to the Constrained Cutting Stock Problem for a Cluster of
Workstations'', in Proc. of High Perf. Distributed Computing,
August 1996. gzipped
postscript
Links