A statistical approach for parallel optimization with application to VLSI placement

A massively parallel optimization approach based on simple neighborhood search techniques was developed and applied to the problem of VLSI cell placement. Statistical models are developed to analyze the performance of the approach in general, and to derive statistical bounds on the quality of obtainable results. The results of these analyses suggest a simple framework for approximate solution of difficult problems. The approach is inherently parallel, and it can be implemented on any type of parallel computer. It was implemented on a simulated hypercube MIMD machine using Cosmic C on a network of Sun workstations. The method is empirically verified