Files in this item



application/pdf9114300.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


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.
Issue Date:1990
Rights Information:Copyright 1990 Kling, Ralph Michael
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9114300
OCLC Identifier:(UMI)AAI9114300

This item appears in the following Collection(s)

Item Statistics