MICROELECTRONIC SYSTEMS NEWS



FILENUMBER: 7015
BEGIN_KEYWORDS
Text Parallel Algorithms VLSI CAD Banerjee
END_KEYWORDS
DATE: july 1994
TITLE: Text on Parallel Algorithms For VLSI CAD by Banerjee


Text on Parallel Algorithms For VLSI CAD by Banerjee


Parallel Algorithms For VLSI Computer-Aided Design

AUTHOR: Prithviraj Banerjee

YEAR: 1994

PUBLISHER: Prentice Hall

ADDRESS OF PUBLISHER: Prentice-Hall Inc
                      Englewoods Cliffs, NJ-07632
                      1-800-223-1360 PRICE: $60.00

ORDER NUMBER: 01583-4

ISBN NUMBER: 0-13-015835-6

ABOUT THE BOOK:

Parallel computing is becoming an increasing cost  effective  and
affordable  means for providing enormous computing power.  Works-
tations are currently using parallel processing  technology,  and
will  use it even more in the future. It is widely believed while
it is relatively easy  to  build  massively  parallel  processing
(MPP)  machines  whose peak performance will be GFLOPS, it is not
always easy  to  harness  the  computational  power  effectively.
Therein  lies  the  challenge: design of good parallel algorithms
that can efficiently use the hardware resources to get  the  max-
imum performance.

This book discusses the use of parallel  processing  for  solving
problems  in  a  growing application area whose computational re-
quirements are enormous: VLSI CAD  applications.  While  numerous
books  exist  on  general  parallel algorithms for regular matrix
problems or graph theory problems, they are mostly theoretical in
nature.  This  book  discusses  PRACTICAL parallel algorithms for
shared memory MIMD,  message  passing  MIMD,  and  SIMD  parallel
machines.

The first two chapters of the book provide a  detailed  introduc-
tion  to  the  field  of parallel computing: architectures, algo-
rithms, and programming and  forms  the  groundwork  for  writing
parallel  programs  for parallel machines. The remaining chapters
(3-9) deal with different CAD applications,  placement,  routing,
layout verification and analysis, circuit simulation, logic simu-
lation, test generation and fault simulation, and logic synthesis
and verification.

For each CAD application, the problem is first clearly  formulat-
ed,  then different sequential approaches for solving the problem
are discussed. Subsequently, for each approach, the corresponding
shared  memory MIMD, message passing MIMD and SIMD parallel algo-
rithms are presented. Actual experimental results  obtained  with
these parallel algorithms on real parallel machines are reported.
The advantages and disadvantages of choosing each  of  these  ap-
proaches  are  discussed with results of case studies on specific
applications.

Each chapter ends with a complete bibliography of the  area;  the
book has over 400 references in the field.

PROSPECTIVE BUYERS OF BOOK:

1) Professors and graduate students in electrical engineering and
computer  science,  who  are  knowledgeable in VLSI CAD area, but
wish to learn about parallel processing to accelerate own  appli-
cations, or to look at potential research areas, since there is a
detailed bibliography.

2) Professors and graduate students in electrical engineering and
computer  science,  who are knowledgeable about the parallel pro-
cessing area, but who currently solve toy problems, but  wish  to
learn  about  exciting  new  application area which is related to
person's field.

3) Graduate level courses can be taught on this book's  topic  at
many universities.

4) Engineers in VLSI CAD companies, who wish to learn how to  use
parallel processing technology for their applications.

5) Engineers in parallel computer companies,  trying  to  develop
useful  software for marketing parallel machines, or to benchmark
machines, or redesign parallel machines.

OUTLINE OF BOOK:

Chapter 1: INTRODUCTION. Provides an introduction to VLSI CAD, an
introduction  to  parallel  processing,  and gives an overview of
book.

Chapter 2: PARALLEL ARCHITECTURES AND PROGRAMMING.   Provides  an
introduction  to  shared  memory  MIMD, message passing MIMD, and
SIMD parallel architectures, and parallel programming.  Describes
actual parallel programming of three simple applications for each
machine type.

Chapter 3: PLACEMENT AND FLOORPLANNING.  Provides an introduction
to  placement  and  floorplanning  problems.  Describes different
sequential approaches to problems, such as pairwise  interchange,
simulated  annealing,  simulated  evolution,  genetic algorithms,
hierarchical decomposition.  For each approach,  describe  shared
memory MIMD, message passing MIMD and SIMD parallel algorithms.

Chapter 4: DETAILED AND GLOBAL ROUTING.  Provides an introduction
to  detailed  and  global  routing problems.  Describes different
sequential approaches to detailed routing problems, such as  maze
routing,  channel  routing,  to global routing approaches such as
graph expansion, iterative improvement, and hierarchical decompo-
sition.  For  each approach, describe shared memory MIMD, message
passing MIMD and SIMD parallel algorithms.

Chapter 5: LAYOUT VERIFICATION AND ANALYSIS.  Provides an  intro-
duction to design rule checking, netlist extraction and parameter
extraction problems. Describes different sequential approaches to
problems,  such  as data decomposition, functional decomposition,
hierarchical decomposition. For each  approach,  describe  shared
memory MIMD, message passing MIMD and SIMD parallel algorithms.

Chapter 6: CIRCUIT SIMULATION.  Provides an introduction  to  the
circuit  simulation problem, and presents different approaches to
solve the problem such as direct  methods,  nonlinear  relaxation
methods  and  waveform  relaxation  methods.  For  each approach,
describe shared memory MIMD, message passing MIMD and SIMD paral-
lel algorithms.

Chapter 7: LOGIC AND BEHAVIORAL SIMULATION.  Provides  an  intro-
duction  to the logic simulation problem and outlines various ap-
proaches to parallel logic simulation such as  data  parallelism,
functional  parallelism,  circuit  parallelism,  synchronous  and
asynchronous event driven simulation, conservative and optimistic
asynchronous parallel event driven simulation. Provides an intro-
duction to behavioral simulation using VHDL,  and  discusses  ap-
proaches  to  parallelize  behavioral  simulation.   For each ap-
proach, describe shared memory MIMD,  message  passing  MIMD  and
SIMD parallel algorithms.

Chapter 8: TEST GENERATION AND FAULT SIMULATION.  Provides an in-
troduction  to  the  test generation problem and outlines various
approaches to parallelism, such as fault  parallelism,  heuristic
parallelism,  AND-parallel,  OR-parallel and circuit parallel ap-
proaches. Provides introduction to the fault simulation  problem,
and outlines various parallelism approaches, such as fault paral-
lel, input pattern parallel, and circuit parallel.  For each  ap-
proach,  describe  shared  memory  MIMD, message passing MIMD and
SIMD parallel allgorithms.

Chapter 9: LOGIC SYNTHESIS AND VERIFICATION.  Provides an  intro-
duction  to  the logic synthesis problem and outlines various ap-
proaches to parallelism,  such  as  circuit  parallel,  two-level
minimization,  multilevel  minimization using tranduction and MIS
approaches. Provides introduction to the logic verification prob-
lem, and outlines various parallelism approaches, such as tautol-
ogy checking,  and  implicit  enumeration.   For  each  approach,
describe shared memory MIMD, message passing MIMD and SIMD paral-
lel allgorithms.

Chapter 10: CONCLUSIONS AND FUTURE DIRECTIONS.  Summarizes  state
of  the  art  in parallel CAD. Identifies the problems facing the
field, and points to some promising solutions. Gives overview  of
ProperCAD project on portable, parallel algorithms for CAD.

ABOUT THE AUTHOR:

Prithviraj Banerjee received his B.Tech.  degree  in  Electronics
and Electrical Engineering from the Indian Institute of Technolo-
gy, Kharagpur, India, in August 1981, and the M.S. and  Ph.D  de-
grees  in  Electrical Engineering from the University of Illinois
at Urbana-Champaign in December 1982 and December 1984.

He is currently Professor of Electrical and Computer Engineering,
and  Director  of  Computational  Science  and Engineering at the
University of Illinois  at  Urbana-Champaign.  His  research  in-
terests  are  in  parallel algorithms for VLSI design automation,
and distributed memory parallel architectures, is the  author  of
over  140  papers  in  these  areas.   He has supervised 10 Ph.D.
theses so far. He has been working  on  parallel  algorithms  for
numerous  VLSI  design  automation  applications  for the last 10
years.

Dr. Banerjee was the recipient of the  President  of  India  Gold
Medal  from  the  Indian  Institute  of Technology, Kharagpur, in
1981, the IBM Young Faculty Development Award in  1986,  the  Na-
tional  Science  Foundation's  Presidential  Young Investigators'
Award in 1987, the IEEE Senior Membership  in  1990,  the  Senior
Xerox  Research  Award  in 1992, and the University Scholar award
from the University of Illinois in 1993.

Dr. Banerjee has served on the program and organizing  committees
of numerous conferences such as International Parallel Processing
Symposia, the International Symposia  on  Computer  Architecture,
the  International  Symposium  on  VLSI  Design,  and  the  Fault
Tolerant Computing Symposia. He is also the editor  of  the  IEEE
Transactions  on  VLSI  Systems,  and the Journal of Parallel and
Distributed Computing.

Return to MSN Home Page