Solving optimization problems by parallel recombinative simulated annealing on a parallel computer-an application to standard cell placement in VLSI design

摘要

In this paper, parallel recombinative simulated annealing (PRSA), a hybrid method with features of simulated annealing and genetic algorithms, is examined. PRSA inherits the global convergence property from simulated annealing and the parallelism property from genetic algorithms. PRSA was implemented on a monoprocessor system as well as on a transputer. The algorithm, its parallel implementation, and its application to an NP-hard problem, namely standard cell placement in very large scale integration (VLSI) chip design, are described. PRSA was run for a large range of test cases. Since its performance depends on many parameters, the effects of parameter variations are studied in detail. Some important parameters are migration of individuals to other transputer nodes and selection strategies for constructing new populations. In comparison with simulated annealing and genetic algorithms, PRSA was found to produce better solutions.