Parallel Crystal Growth, a new parallel extension of Simulated Annealing (SA), is presented. Sub-problems - the crystals - are solved in parallel, and iteratively merged into bigger crystals. The essential novelty is that processors spend time in a specific sub-problem, only as long as it is worthwhile, by locally computed merging criteria. Intra crystal search, is not repeated. Only inter-crystal exploration is done after merging. Whole problem terminationis similarly determined. This leads to controlled speedup super-linearity, as demonstrated by experimental results with the PVM implementation.
展开▼
