Genetic Algorithms for VLSI Design, Layout and Test Automation

Hardcover (Print)
Used and New from Other Sellers
Used and New from Other Sellers
from $18.88
Usually ships in 1-2 business days
(Save 84%)
Other sellers (Hardcover)
  • All (5) from $18.88   
  • New (3) from $104.06   
  • Used (2) from $18.88   
Close
Sort by
Page 1 of 1
Showing All
Note: Marketplace items are not eligible for any BN.com coupons and promotions
$104.06
Seller since 2007

Feedback rating:

(23585)

Condition:

New — never opened or used in original packaging.

Like New — packaging may have been opened. A "Like New" item is suitable to give as a gift.

Very Good — may have minor signs of wear on packaging but item works perfectly and has no damage.

Good — item is in good condition but packaging may have signs of shelf wear/aging or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Acceptable — item is in working order but may show signs of wear such as scratches or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Used — An item that has been opened and may show signs of wear. All specific defects should be noted in the Comments section associated with each item.

Refurbished — A used item that has been renewed or updated and verified to be in proper working condition. Not necessarily completed by the original manufacturer.

New
BRAND NEW

Ships from: Avenel, NJ

Usually ships in 1-2 business days

  • Canadian
  • International
  • Standard, 48 States
  • Standard (AK, HI)
$108.48
Seller since 2010

Feedback rating:

(33)

Condition: New
0130115665 PAPERBACK. NEW. Never used. We do not ship to PO Box/APO/FPO addresses.

Ships from: Cupertino, CA

Usually ships in 1-2 business days

  • Canadian
  • International
  • Standard, 48 States
  • Standard (AK, HI)
  • Express, 48 States
  • Express (AK, HI)
$155.25
Seller since 2014

Feedback rating:

(6)

Condition: New
New

Ships from: Idyllwild, CA

Usually ships in 1-2 business days

  • Canadian
  • International
  • Standard, 48 States
  • Standard (AK, HI)
  • Express, 48 States
  • Express (AK, HI)
Page 1 of 1
Showing All
Close
Sort by

Overview

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.

Read More Show Less

Editorial Reviews

Booknews
Describes how genetic algorithms (GAs) can be utilized for developing efficient computer-aided design (CAD) tools for performing VLSI design optimization, layout generation, and chip testing tasks, such as circuit partitioning, cell routing and placement, peak power estimation, FPGA mapping, and test vector generation. Mazumder (electrical engineering, U. of Michigan) and Rudnick (electrical engineering, U. of Illinois) wrote the book primarily for practicing CAD engineers and academic researchers who want to apply GAs and analyze their performance in solving large VLSI/CAD optimization problems. Annotation c. by Book News, Inc., Portland, Or.
Read More Show Less

Product Details

Meet the Author

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.

Read More Show Less

Read an Excerpt

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 recent past, some existing layout tools have been successfully modified to run efficiently on tightly coupled shared-memory (e.g., Sequent's bus-based Balance) and message-passing (e.g., Intel's hypercube) machines. In order to achieve high speedup, these algorithms require frequent data exchange between two or more processors in a cluster. However, by and large, conventional layout algorithms are not amenable to parallelism on a network of workstations. As VLSI chips are reaching the integration level of one hundred million transistors and more, chip design tasks are becoming extremely complex and computation intensive. New generation CAD tools must be able to run in parallel over a large number of inexpensive computers interconnected together by a local area network. It will therefore be worthwhile to invest an effort in developing genetic-based CAD tools.

Organization of the Book

There are three distinct classes of VLSI problems which the book addresses: (1) the layout class of problems,such as circuit partitioning, placement, and routing; (2) the design class of problems, including power estimation, technology mapping, and netlist partitioning; and, finally, (3) reliable chip testing through efficient test vector generation. All these problems are intractable in the sense that no polynomial time algorithm can guarantee optimal solution of the problems, and they actually belong to the dreadful NP-complete and NP-hard categories. The book is organized as follows.

Chapter 1 provides an introduction to the two basic types of GAs: the simple genetic algorithm and the steady-state algorithm. GA terminology is introduced and genetic operators are discussed. A simple test generation example is used to illustrate the operation of a GA, and then GAs for problems in VLSI Design, Layout, and Test automation are introduced.

Chapter 2 addresses the problem of circuit partitioning. It begins with a review of previous approaches used and then describes a steady-state GA for solving the problem. Experimental results are presented and a hybrid GA that incorporates local optimization is described.

Chapter 3 focuses on automatic placement for standard cells and macro cells. A GA for standard cell placement is described, results are presented, and the genetic approach is compared to simulated annealing. In addition, an algorithm that combines a GA and simulated annealing for macro cell placement is discussed.

Chapter 4 discusses problems encountered in macro cell routing. It begins by addressing the Steiner problem in a graph. Previous approaches are reviewed, a GA to solve the problem is described, experimental results are presented, and comparisons are made to previous work. Finally,the GA for the Steiner problem in a graph is applied to the macro cell routing problem and results are presented to demonstrate the effectiveness of this approach.

Chapter 5 describes a GA for FPG technology mapping, which is a key phase of logic synthesis and involves partitioning the circuit into a number of subcircuits that are not necessarily disjoint. Application of circuit partitioning to pseudo-exhaustive testing is also addressed, and experimental results are given for FPGA technology mapping.

Chapter 6 discusses the problem of automatic test generation. A GA framework for test generation is presented and results of experiments to evaluate various GA parameters are given. Integration of GA s with deterministic algorithms and incorporation of problem-specific knowledge into a GA are discussed. The chapter concludes by describing how the GA framework can be applied to the problem of test sequence compaction.

Chapter 7 deals with power estimation for VLSI circuits. In particular, it describes a GA for estimating the peak power dissipation in a circuit. The peak power estimates provide a tight lower bound on the actual peak power and are significantly more accurate than previous approaches. The actual sequences of vectors that achieve these bounds are also generated by the GA. The effects of the delay model used on the quality of the results are also discussed.

Chapter 8 explores parallel implementations of GAs for standard cell placement and test generation. The migration operator for parallel GAs is introduced in this chapter. GAs that require little communication between processors and are therefore suitable for a network of workstations are described. Experimental results are presented to illustrate the effects of various communication patterns. Very good speedups are achieved, as demonstrated for several benchmark circuits.

Chapter 9 concludes the book by giving guidelines for devising a GA to solve a new problem in the area of VLSI design, layout, and test automation or in another domain of science and engineering. Problem encoding, fitness function,type of GA, and GA parameters are addressed, and the genetic approach is compared to conventional approaches.

Applicability of the Book

This book is intended for design engineers and researchers in the fields of VLSI and CAD. The book introduces the main concepts of GAs in a simple and easily understandable way that may encourage first time users to learn various aspects of GAs quickly from the first chapter and then go on to study the detailed applications in other chapters more carefully. This book also provides college and university students a systematic exposure to a wide spectrum of design, physical layout, and chip testing problems that form integral parts of digital testing and CAD for VLSI system design courses. The breadth and depth of issues presented justifies using this book as a state-of-the-art reference source in the above courses. The book also includes a chapter on parallel implementations of GAs for layout and test generation. The parallel GAs demonstrate how uniprocessor algorithms can be accelerated linearly with the number of loosely connected computer workstations deployed. Different communication structures that have been used in message passing between different processes are compared.

To Readers

This book presents a number of VLSI/CAD applications of GAs that have primarily originated from research work performed at the universities where we are teaching. The book is being published nine years after we first started working in this field and reported work in international conferences and archival journals. Meanwhile, many other researchers have been inspired by some of the early success stories and subsequently applied GAs very successfully to a large number of VLSI/CAD problems. In order to contain the size of the book, we have had to exclude much of the excellent work done by others. Therefore, we would like to ask readers to search the following Internet sites for comprehensive listings of publications on GAs and evolution theory that not only refer to other key papers pertaining to VLSI/CAD problems but also include important papers illustrating the use of GAs in solving problems in various other fields of engineering, science, business, etc.:

http://www.dai.ed.ac.uk/groups/evalg http://www.bioele.nuee.nagoya-u.ac.jp/wsc1/papers http://www-illigal.ge.uiuc.edu/

Read More Show Less

Table of Contents

Preface
1 Introduction 1
2 Partitioning 37
3 Standard Cell and Macro Cell Placement 69
4 Macro Cell Routing 107
5 FPGA Technology Mapping 140
6 Automatic Test Generation 158
7 Peak Power Estimation 227
8 Parallel Implementations 252
9 Conclusion 295
Glossary 305
Bibliography 314
Index 332
About the Authors 336
Read More Show Less

Preface

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 recent past, some existing layout tools have been successfully modified to run efficiently on tightly coupled shared-memory (e.g., Sequent's bus-based Balance) and message-passing (e.g., Intel's hypercube) machines. In order to achieve high speedup, these algorithms require frequent data exchange between two or more processors in a cluster. However, by and large, conventional layout algorithms are not amenable to parallelism on a network of workstations. As VLSI chips are reaching the integration level of one hundred million transistors and more, chip design tasks are becoming extremely complex and computation intensive. New generation CAD tools must be able to run in parallel over a large number of inexpensive computers interconnected together by a local area network. It will therefore be worthwhile to invest an effort in developing genetic-based CAD tools.

Organization of the Book

There are three distinct classes of VLSI problems which the book addresses: (1) the layout class of problems,such as circuit partitioning, placement, and routing; (2) the design class of problems, including power estimation, technology mapping, and netlist partitioning; and, finally, (3) reliable chip testing through efficient test vector generation. All these problems are intractable in the sense that no polynomial time algorithm can guarantee optimal solution of the problems, and they actually belong to the dreadful NP-complete and NP-hard categories. The book is organized as follows.

Chapter 1 provides an introduction to the two basic types of GAs: the simple genetic algorithm and the steady-state algorithm. GA terminology is introduced and genetic operators are discussed. A simple test generation example is used to illustrate the operation of a GA, and then GAs for problems in VLSI Design, Layout, and Test automation are introduced.

Chapter 2 addresses the problem of circuit partitioning. It begins with a review of previous approaches used and then describes a steady-state GA for solving the problem. Experimental results are presented and a hybrid GA that incorporates local optimization is described.

Chapter 3 focuses on automatic placement for standard cells and macro cells. A GA for standard cell placement is described, results are presented, and the genetic approach is compared to simulated annealing. In addition, an algorithm that combines a GA and simulated annealing for macro cell placement is discussed.

Chapter 4 discusses problems encountered in macro cell routing. It begins by addressing the Steiner problem in a graph. Previous approaches are reviewed, a GA to solve the problem is described, experimental results are presented, and comparisons are made to previous work. Finally,the GA for the Steiner problem in a graph is applied to the macro cell routing problem and results are presented to demonstrate the effectiveness of this approach.

Chapter 5 describes a GA for FPG technology mapping, which is a key phase of logic synthesis and involves partitioning the circuit into a number of subcircuits that are not necessarily disjoint. Application of circuit partitioning to pseudo-exhaustive testing is also addressed, and experimental results are given for FPGA technology mapping.

Chapter 6 discusses the problem of automatic test generation. A GA framework for test generation is presented and results of experiments to evaluate various GA parameters are given. Integration of GA s with deterministic algorithms and incorporation of problem-specific knowledge into a GA are discussed. The chapter concludes by describing how the GA framework can be applied to the problem of test sequence compaction.

Chapter 7 deals with power estimation for VLSI circuits. In particular, it describes a GA for estimating the peak power dissipation in a circuit. The peak power estimates provide a tight lower bound on the actual peak power and are significantly more accurate than previous approaches. The actual sequences of vectors that achieve these bounds are also generated by the GA. The effects of the delay model used on the quality of the results are also discussed.

Chapter 8 explores parallel implementations of GAs for standard cell placement and test generation. The migration operator for parallel GAs is introduced in this chapter. GAs that require little communication between processors and are therefore suitable for a network of workstations are described. Experimental results are presented to illustrate the effects of various communication patterns. Very good speedups are achieved, as demonstrated for several benchmark circuits.

Chapter 9 concludes the book by giving guidelines for devising a GA to solve a new problem in the area of VLSI design, layout, and test automation or in another domain of science and engineering. Problem encoding, fitness function,type of GA, and GA parameters are addressed, and the genetic approach is compared to conventional approaches.

Applicability of the Book

This book is intended for design engineers and researchers in the fields of VLSI and CAD. The book introduces the main concepts of GAs in a simple and easily understandable way that may encourage first time users to learn various aspects of GAs quickly from the first chapter and then go on to study the detailed applications in other chapters more carefully. This book also provides college and university students a systematic exposure to a wide spectrum of design, physical layout, and chip testing problems that form integral parts of digital testing and CAD for VLSI system design courses. The breadth and depth of issues presented justifies using this book as a state-of-the-art reference source in the above courses. The book also includes a chapter on parallel implementations of GAs for layout and test generation. The parallel GAs demonstrate how uniprocessor algorithms can be accelerated linearly with the number of loosely connected computer workstations deployed. Different communication structures that have been used in message passing between different processes are compared.

To Readers

This book presents a number of VLSI/CAD applications of GAs that have primarily originated from research work performed at the universities where we are teaching. The book is being published nine years after we first started working in this field and reported work in international conferences and archival journals. Meanwhile, many other researchers have been inspired by some of the early success stories and subsequently applied GAs very successfully to a large number of VLSI/CAD problems. In order to contain the size of the book, we have had to exclude much of the excellent work done by others. Therefore, we would like to ask readers to search the following Internet sites for comprehensive listings of publications on GAs and evolution theory that not only refer to other key papers pertaining to VLSI/CAD problems but also include important papers illustrating the use of GAs in solving problems in various other fields of engineering, science, business, etc.:

http://www.dai.ed.ac.uk/groups/evalg http://www.bioele.nuee.nagoya-u.ac.jp/wsc1/papers http://www-illigal.ge.uiuc.edu/

Read More Show Less

Introduction

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 recent past, some existing layout tools have been successfully modified to run efficiently on tightly coupled shared-memory (e.g., Sequent's bus-based Balance) and message-passing (e.g., Intel's hypercube) machines. In order to achieve high speedup, these algorithms require frequent data exchange between two or more processors in a cluster. However, by and large, conventional layout algorithms are not amenable to parallelism on a network of workstations. As VLSI chips are reaching the integration level of one hundred million transistors and more, chip design tasks are becoming extremely complex and computation intensive. New generation CAD tools must be able to run in parallel over a large number of inexpensive computers interconnected together by a local area network. It will therefore be worthwhile to invest an effort in developing genetic-based CAD tools.

Organization of the Book

There are three distinct classes of VLSI problems which the book addresses: (1) the layout class of problems,such as circuit partitioning, placement, and routing; (2) the design class of problems, including power estimation, technology mapping, and netlist partitioning; and, finally, (3) reliable chip testing through efficient test vector generation. All these problems are intractable in the sense that no polynomial time algorithm can guarantee optimal solution of the problems, and they actually belong to the dreadful NP-complete and NP-hard categories. The book is organized as follows.

Chapter 1 provides an introduction to the two basic types of GAs: the simple genetic algorithm and the steady-state algorithm. GA terminology is introduced and genetic operators are discussed. A simple test generation example is used to illustrate the operation of a GA, and then GAs for problems in VLSI Design, Layout, and Test automation are introduced.

Chapter 2 addresses the problem of circuit partitioning. It begins with a review of previous approaches used and then describes a steady-state GA for solving the problem. Experimental results are presented and a hybrid GA that incorporates local optimization is described.

Chapter 3 focuses on automatic placement for standard cells and macro cells. A GA for standard cell placement is described, results are presented, and the genetic approach is compared to simulated annealing. In addition, an algorithm that combines a GA and simulated annealing for macro cell placement is discussed.

Chapter 4 discusses problems encountered in macro cell routing. It begins by addressing the Steiner problem in a graph. Previous approaches are reviewed, a GA to solve the problem is described, experimental results are presented, and comparisons are made to previous work. Finally,the GA for the Steiner problem in a graph is applied to the macro cell routing problem and results are presented to demonstrate the effectiveness of this approach.

Chapter 5 describes a GA for FPG technology mapping, which is a key phase of logic synthesis and involves partitioning the circuit into a number of subcircuits that are not necessarily disjoint. Application of circuit partitioning to pseudo-exhaustive testing is also addressed, and experimental results are given for FPGA technology mapping.

Chapter 6 discusses the problem of automatic test generation. A GA framework for test generation is presented and results of experiments to evaluate various GA parameters are given. Integration of GA s with deterministic algorithms and incorporation of problem-specific knowledge into a GA are discussed. The chapter concludes by describing how the GA framework can be applied to the problem of test sequence compaction.

Chapter 7 deals with power estimation for VLSI circuits. In particular, it describes a GA for estimating the peak power dissipation in a circuit. The peak power estimates provide a tight lower bound on the actual peak power and are significantly more accurate than previous approaches. The actual sequences of vectors that achieve these bounds are also generated by the GA. The effects of the delay model used on the quality of the results are also discussed.

Chapter 8 explores parallel implementations of GAs for standard cell placement and test generation. The migration operator for parallel GAs is introduced in this chapter. GAs that require little communication between processors and are therefore suitable for a network of workstations are described. Experimental results are presented to illustrate the effects of various communication patterns. Very good speedups are achieved, as demonstrated for several benchmark circuits.

Chapter 9 concludes the book by giving guidelines for devising a GA to solve a new problem in the area of VLSI design, layout, and test automation or in another domain of science and engineering. Problem encoding, fitness function,type of GA, and GA parameters are addressed, and the genetic approach is compared to conventional approaches.

Applicability of the Book

This book is intended for design engineers and researchers in the fields of VLSI and CAD. The book introduces the main concepts of GAs in a simple and easily understandable way that may encourage first time users to learn various aspects of GAs quickly from the first chapter and then go on to study the detailed applications in other chapters more carefully. This book also provides college and university students a systematic exposure to a wide spectrum of design, physical layout, and chip testing problems that form integral parts of digital testing and CAD for VLSI system design courses. The breadth and depth of issues presented justifies using this book as a state-of-the-art reference source in the above courses. The book also includes a chapter on parallel implementations of GAs for layout and test generation. The parallel GAs demonstrate how uniprocessor algorithms can be accelerated linearly with the number of loosely connected computer workstations deployed. Different communication structures that have been used in message passing between different processes are compared.

To Readers

This book presents a number of VLSI/CAD applications of GAs that have primarily originated from research work performed at the universities where we are teaching. The book is being published nine years after we first started working in this field and reported work in international conferences and archival journals. Meanwhile, many other researchers have been inspired by some of the early success stories and subsequently applied GAs very successfully to a large number of VLSI/CAD problems. In order to contain the size of the book, we have had to exclude much of the excellent work done by others.

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)