CS294-3: Algorithms in the Real World (Guy Blelloch, Fall 97)

#

Topic 7: VLSI Layout and Routing

[ Topics |
Scribe Notes |
Readings |
Text Books |
Links ]

VLSI 1 (draft) (Rich Vuduc)
VLSI 2 (draft) (Mehul Shah)
VLSI 3 + Pattern Matching 1 (draft) (Noah Treuhaft)
N. Sherwani,
Algorithms for VLSI Physical Design Automation
Kluwer, 1995.
**Chapter 1** (VLSI Physical Design)
**Chapter 6** (Global Routing)
Both chapters were handed out in class. Note that the chapters I handed
out are from the first edition of the book (1993) since that is what
I have. Feel free to track down the corresponding chapters from the second
edition (1995).
**Primary**
N. Sherwani,
Algorithms for VLSI Physical Design Automation, Second Edition
Kluwer, 1995.
M. Sarrafzadeh and C. K. Wong.
An Introduction to VLSI Physical Design.
McGraw-Hill, 1996.
**Others** (alphabetic order)
P. Banerjee.
Parallel Algorithms for VLSI Computer-Aided Design
Prentice Hall, 1994.
A. B. Kahng and G. Robins.
On Optimal Interconnections for VLSI
Kluwer Academic Publishers, 1995.
B. Korte, L Lovasz, H. J. Promel, and A. Schrijver (eds.).
Paths, flows, and VLSI-layout.
Springer Verlag, 1990.
T. Lengauer,
Combinatorial algorithms for integrated circuit layout,
Wiley 1990.
M. Pecht and Y. T. Wong (editors).
Advanced Routing of Electronic Modules
CRC Press, 1995.
M. Sarrafzadeh and D.T. Lee (editors).
Algorithmic Aspects of VLSI Layout (Lecture
Notes Series on Computing, Vol 2)
World Scientific, 1994.
### Benchmarks

FPGA Benchmark Information
**General links**
University of Idaho's Links
to VLSI information.
The use of combinatorial algorithms in
VLSI routing problems
A good page of
algorithms
used in VLSI CAD (University of Virginia).
**Real World**
Focus Report: Floorplanners and Physical Design Tools
Industrial CAD Sites
on the Web.
**Courses**
Physical Design for VLSI Systems from Iowa State.
**Steiner Trees**
The Steiner tree page from UVA.
**Channel Routing**
Necessary and Sufficient Conditions for the Routability of
Classical Channels by Patrick Groeneveld.

Back to the Algorithms in the Real World home page.

Guy Blelloch,
guyb@cs.berkeley.edu.