Solving optimization problems by parallel recombinative simulated annealing on a parallel computer-an application to...

Area of Science:

• Computer Science
• Artificial Intelligence
• Optimization Algorithms

Background:

• Standard cell placement in Very Large Scale Integration (VLSI) chip design is an NP-hard problem.
• Existing methods like simulated annealing and genetic algorithms have limitations in solving such complex optimization tasks.

Purpose of the Study:

• To introduce and evaluate Parallel Recombinative Simulated Annealing (PRSA), a novel hybrid optimization algorithm.
• To assess PRSA's performance against established algorithms for VLSI standard cell placement.

Main Methods:

• PRSA integrates global convergence from simulated annealing and parallelism from genetic algorithms.
• The algorithm was implemented on both monoprocessor and transputer systems.
• Extensive testing involved analyzing the impact of parameter variations, including individual migration and population selection strategies.

Main Results:

• PRSA demonstrated superior performance in producing better solutions compared to standard simulated annealing and genetic algorithms.
• The study detailed the effects of various parameters on PRSA's effectiveness.
• Successful application to the NP-hard problem of VLSI standard cell placement was achieved.

Conclusions:

• PRSA offers a promising hybrid approach for tackling complex optimization problems.
• The parallel implementation enhances efficiency and solution quality.
• Further research into parameter tuning can optimize PRSA for specific applications.