Files in this item
|(no description provided)|
|Title:||Optimization by simulated evolution and its application to cell placement|
|Author(s):||Kling, Ralph Michael|
|Doctoral Committee Chair(s):||Banerjee, Prithviraj|
|Department / Program:||Engineering, Electronics and Electrical|
|Discipline:||Engineering, Electronics and Electrical|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|Subject(s):||Engineering, Electronics and Electrical|
|Abstract:||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.
|Rights Information:||Copyright 1990 Kling, Ralph Michael|
|Date Available in IDEALS:||2011-05-07|
|Identifier in Online Catalog:||AAI9114300|
This item appears in the following Collection(s)
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois