Genetic
Algorithms for VLSI Design, Layout & Test Automation
(Hardcover)
by Pinaki Mazumder,
Elizabeth
Rudnick
To learn about the
book, go
to Amazon.com at the following web-site:
http://www.amazon.com/o/ASIN/0130115665/
Look
Inside This Book
Browse Sample
Pages:
Front Cover | Table of Contents | Excerpt | Index | Back Cover
Editorial
Reviews
From the
Inside Flap
Preface
This book 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. 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
effectiveness 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 co-researchers 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
From the Back Cover
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, deterministic/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.
About the Author
PINAKI MAZUMDER is
Professor in the Department
of Electrical Engineering and Computer Science at The University of
Michigan,
ELIZABETH M. RUDNICK is
Assistant Professor at
the Center for Reliable and High-Performance Computing and the
Department of
Electrical and Computer Engineering,
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.