Optimization by simulated evolution and its application to cell placement

We introduce the new optimization method of Simulated Evolution (SE), which is designed to find near optimal solutions to problems which are hard to solve by standard methods. The new algorithm is discussed in detail and a variety of measurements are taken to evaluate its performance under various conditions. In addition, a theoretical framework is introduced to formally describe the algorithm. A Markov analysis is performed using this mathematical model to analyze convergence properties.The Standard Cell placement problem in the VLSI design area was chosen as a representative problem for applying SE techniques. A new hierarchical placement technique using windowing methods is introduced. A complete placement program has been developed and thoroughly tested on a variety of industrial benchmark circuits. A comparative performance analysis with the most successful Simulated Annealing-based placement program is presented.The SE algorithm has been implemented on several different sequential and parallel computing platforms. An evaluation of the achievable parallelism has been performed in each case. Furthermore, a special purpose coprocessor which speeds up wire length calculations as needed by placement programs has been designed, fabricated and tested.U of I OnlyETDs are only available to UIUC Users without author permissio