Genetic Algorithms for VLSI Design, Layout and Test Automation

1156F-7 Genetic algorithms mimic the natural process of evolution, helping engineers optimize their designs by using the principle of "survival of the fittest." VLSI is especially suited to benefit from genetic algorithms - and this comprehensive book shows you how to get the best results, fast. You'll discover how genetic algorithms work and how you can use them in a wide variety of VLSI design, layout, and test automation tasks, including: Circuit partitioning Macro cell routing, including Steiner problems and global routing Standard cell and macro cell placement Circuit segmentation, FPGA mapping and pseudo-exhaustive testing Automatic test generation including compaction, eterministic/genetic test hybrids and integration of finite state machine sequences Peak power estimation You'll find essential insights into problem encoding and fitness functions; coverage of advanced parallel implementations; and much more. Specific experimental results are presented for every application - as are detailed problem descriptions and easy-to-adapt examples. Genetic algorithms are already being incorporated into leading electronic design automation systems. Leverage their full power now - with Genetic Algorithms For VLSI Design, Layout, and Test Automation.

Preface This book describes how genetic algorithms (GAs)can be utilized for developing effcient computer-aided design (CAD)tools for performing VLSI design optimiza- tion,layout generation,and chip testing tasks.It is written primarily for practicing CAD engineers and academic researchers who want to apply GAs and analyze their performance in solving large VLSI/CAD optimization problems. Although GAs were developed over twenty-five years ago, not much research and experimental work have been done to ascertain their capabilities in solving complex and extremely large constrained combinatorial optimization problems that one generally encounters in designing VLSI/CAD tools. Unlike graph theoretic approaches, integer/linear programming, simulated annealing, and a host of other optimization techniques that have been quite successfully deployed as core problem solving methods in various VLSI/CAD tools, GAs are not yet as widely used. We hope that this book will motivate readers to widely apply GAs in developing VLSI/CAD tools. For this purpose, we have carefully selected a few important VLSI design automation problems with unique problem solving features, and we have shown how in each case, various aspects of the GA, namely its chromosome, crossover and mutation operators, etc., can be separately formulated to solve these problems. In order to estimate the e ffectiveness of GAs, we have compared their performance with conventional algorithms. While most of the solution techniques proposed in this book have been developed in an ad hoc and exploratory manner,the basic formulations of the GAs are, nevertheless, applicable to a range of related problems. However, further experimentation is needed to find better settings of GA parameters for each problem. If the empirical study is also combined with insightful mathematical modeling, then we strongly believe that the performance of the genetic-based tools can be further improved and real payoffs of the use of GAs in CAD tools can be demonstrated. The main objectives of this book are: to aggregate various genetic-based research work performed by the authors and their coresearchers at The University of Michigan, Ann Arbor, and the University of Illinois, Urbana,as well as by colleagues at the University of Iowa, Iowa City; to educate readers in the VLSI/CAD community about the merits of GAs by demonstrating some sample solution techniques; to motivate readers to develop improved techniques with appropriate mathematical formulations; and finally, to encourage readers working in other fields of science and engineering to explore the GA as a powerful method for solving problems in their areas of work. We have included sufficient introductory material to enable a reader who is not well-versed in GAs to know how to use them effectively. It is our sincere hope that in the future, GAs will prove to be a general-purpose heuristic method for solving a wider class of engineering and scientific problems. Another purpose of this book is to foster research work on the development of distributed CAD tools that run efficiently on a network of workstations. Originally, Prof.Mazumder's research group was intrigued by the intrinsic parallelism of GAs and the group embarked upon this research work with a view toward developing a suite of VLSI layout tools that can efficiently utilize the distributed resources of a network of workstations loosely connected through a local area network. With the availability of inexpensive personal computers and workstations that can be linked via an Ethernet type network, the CAD tool development environment has dramatically shifted from a single powerful uniprocessor to a cluster of networked desk-top computers. The main goal for developing this suite of distributed layout tools was to demonstrate that GAs are uniquely suited for running concurrently on a number of workstations without requiring much communication overhead. In the rece