Optimization by simulated evolution and its application to cell placement
Kling, Ralph Michael
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/23634
Description
Title
Optimization by simulated evolution and its application to cell placement
Author(s)
Kling, Ralph Michael
Issue Date
1990
Doctoral Committee Chair(s)
Banerjee, Prithviraj
Department of Study
Engineering, Electronics and Electrical
Discipline
Engineering, Electronics and Electrical
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
