15-853: Algorithms in the Real World (Guy Blelloch, Fall 99)

next up previous
Topic 7: VLSI Layout and Routing

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

Topic Outline

  • Introduction
  • The design cycle
  • Design styles (i.e. full custom, standard cell, FPGAs)
  • Global Routing
  • Maze routing
  • Steiner-tree methods
  • Integer programming methods
  • Other physical design problems
  • Partitioning
  • Placement
  • Detailed routing
  • Compaction

    • Scribe Notes

  • VLSI 1 (draft) (Rich Vuduc)
  • VLSI 2 (draft) (Mehul Shah)
  • VLSI 3 + Pattern Matching 1 (draft) (Noah Treuhaft)

    • Readings

  • 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).

    Recommended Text Books

    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

    • Further Readings and Links

  • 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.cmu.edu.