Genetic Algorithms for VLSI Design, Layout and Test Automation

by Mazumder, Pinaki; Rudnick, Elizabeth

• ISBN13: 9780130115669
• ISBN10: 0130115665
• Edition: 1st
• Format: Paperback
• Copyright: 1998-12-10
• Publisher: PEARSO

Summary

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.

Author Biography

PINAKI MAZUMDER is Professor in the Department of Electrical Engineering and Computer Science at The University of Michigan, Ann Arbor. He has worked for over six years at AT&T Bell Laboratories (USA), NTT (Japan), and BEL (India). He has coauthored a book entitled Testing and Testable Design of High-Density Random-Access Memories and has published over 100 archival papers on VLSI testing, physical design automation, and high-speed circuit design.

ELIZABETH M. RUDNICK is Assistant Professor at the Center for Reliable and High-Performance Computing and the Department of Electrical and Computer Engineering, University of Illinois, Urbana. She has worked at Motorola, Sunrise Test Systems, and AMD, specializing in design verification, test generation, and electronic design automation.

Table of Contents

Preface	xi
Introduction	1	(36)
Introduction to GA Terminology	3	(2)
The Simple GA	5	(2)
The Steady-State Algorithm	7	(2)
Genetic Operators	9	(7)
Selection	9	(1)
Crossover	10	(2)
Mutation	12	(1)
Fitness Scaling	13	(1)
Inversion	14	(2)
GA Example	16	(2)
GAs for VLSI Design, Layout, and Test Automation	18	(19)
Partitioning	20	(2)
Automatic Placement	22	(4)
Automatic Routing	26	(4)
Technology Mapping for FPGAs	30	(2)
Automatic Test Generation	32	(2)
Power Estimation	34	(3)
Partitioning	37	(32)
Problem Description	38	(8)
Partitioning Algorithms	41	(1)
Taxonomy of Partitioning Algorithms	42	(4)
Circuit Partitioning by Genetic Algorithm	46	(14)
Incorporation and Duplicate Check	52	(1)
Mutation	53	(2)
Genetic Multiway Partitioning	55	(1)
Evaluation	56	(2)
Results	58	(2)
Hybrid Genetic Algorithm for Ratio-Cut Partitioning	60	(7)
Genetic Encoding	61	(1)
Selection, Crossover, and Mutation	61	(1)
Local Improvement	62	(2)
Preprocessing	64	(1)
Weighted DFS Reordering (WDFR)	64	(1)
Time Complexity	65	(1)
Results	65	(1)
Comparison of GA with Other Methods	66	(1)
Conclusion	67	(2)
Standard Cell and Macro Cell Placement	69	(38)
Standard Cell Placement	71	(14)
GASP Algorithm	72	(4)
Crossover Operators	76	(2)
Optimizing the Genetic Algorithm	78	(2)
Comparison with Simulated Annealing	80	(1)
Experimental Results	81	(4)
Macro Cell Placement	85	(22)
Unified Algorithm	87	(3)
Application to Macro Cell Placement	90	(8)
Experimental Results	98	(6)
Limitations and Enhancements	104	(3)
Macro Cell Routing	107	(33)
The Steiner Problem in a Graph	109	(26)
Problem Definition	110	(1)
Description of the Algorithm	111	(7)
Experimental Method	118	(3)
Results	121	(13)
Summary and Conclusion	134	(1)
Macro Cell Global Routing	135	(5)
Routing Phase I: Applying the GA for the SPG	135	(1)
Routing Phase II: Minimizing Layout Area	136	(1)
Experimental Results	137	(1)
Summary and Conclusion	138	(2)
FPGA Technology Mapping	140	(18)
Problem Description	141	(2)
Circuit Segmentation and FPGA Mapping	143	(7)
TLU-Based FPGA Architecture	143	(3)
Mapping Using Circuit Segmentation	146	(4)
Circuit Segmentation for Pseudo-Exhaustive Testing	150	(1)
Experimental Results	151	(5)
Results for FPGA Technology Mapping	151	(3)
Experimental Results of Segmentation for PET	154	(2)
Summary	156	(2)
Automatic Test Generation	158	(69)
Problem Description	160	(5)
Test Generation in a GA Framework	165	(13)
Encoding Alphabet	167	(1)
GA Parameters	168	(1)
Fitness Function	168	(3)
An Implementation	171	(3)
Evaluation of GA Parameters	174	(4)
Test Generation for Test Application Time Reduction	178	(6)
Deterministic/Genetic Test Generator Hybrids	184	(15)
GA-HITEC Hybrid	186	(4)
ALT-TEST Hybrid	190	(9)
Use of Finite State Machine Sequences	199	(13)
Algorithm Overview	201	(5)
Single Time Frame Mode	206	(1)
Test Generation Procedure	207	(3)
Experimental Results	210	(2)
Dynamic Test Sequence Compaction	212	(12)
Overview	214	(4)
Experimental Results	218	(6)
Conclusions	224	(3)
Peak Power Estimation	227	(25)
Problem Description	229	(5)
Adding Delay Models to the Problem	232	(2)
Application of Genetic Algorithms to Peak Power Estimation	234	(1)
Estimation of Peak Single-Cycle and n-Cycle Powers	235	(2)
Resolving the Problem of State Reachability	236	(1)
Peak Sustainable Power Estimation	237	(2)
Experimental Results	239	(10)
Summary	249	(3)
Parallel Implementations	252	(43)
Wolverines: Standard Cell Placement on a Network of Workstations	254	(26)
Standard Cell Placement Using the Genetic Algorithm	255	(3)
Analysis of Serial Algorithm	258	(1)
Distributed Placement Algorithm	259	(5)
Experimental Results	264	(16)
Conclusions	280	(1)
Parallel Genetic Algorithms for Automatic Test Generation	280	(15)
Sequential GA-Based ATG	281	(3)
Parallel GA-Based ATG	284	(4)
Experimental Results	288	(5)
Conclusions	293	(2)
Conclusion	295	(10)
Problem Encoding	296	(1)
Fitness Function	297	(1)
Type of GA	298	(1)
GA Parameters	298	(2)
Genetic Algorithms vs. Conventional Algorithms	300	(1)
Concluding Remarks	301	(4)
Glossary	305	(9)
Bibliography	314	(18)
Index	332	(4)
About the Authors	336

Excerpts

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