ECE/CS 5740/6740 - CAD of Digital Circuits and Systems
CAD of Digital Circuits - Fundamental CAD Techniques for Physical Design Automation
M, W, F, 2:00 - 2:50, WEB L 122
Office: MEB 4512 (East side Penthouse on the fourth floor)
Tel: 587-7617, Email: my last name at ece.utah.edu
Office hours: Thursday 2:30pm - 4pm; or by appointment.
Note: These are tentative, for the first week of class.
Course Objective and Organization
The objective of the course is to study fundamental CAD techniques for
Physical Design Automation. Topics will cover the broad range of
physical design techniques: Circuit Partitioning, Floor-planning,
Detailed Placement, Global and Detailed Routing, and (time-permitting)
some coverage of contemporary research issues in physical design ---
integrating placement and routing, analyzing routing congestion,
Roughly, the course can be divided into 2 parts:
CAD modeling and optimization techniques for physical design;
Applications of these concepts to physical design.
In the 1st part, we will cover:
Basic Graph Theoretical concepts of graph traversal, graph covering,
coloring, matching and flow network problems.
Mathematical programming and optimization, and their relationship to
graph theoretical formulation of CAD problems.
In the 2nd part, we will make use of these techniques to Physical
Design problems of:
- Kernighan-Lin, Fiduccia-Mattheyses, Simulated Annealing
- Floorplan models, graph-techniques, analytical techniques
- Cost functions and estimations, partitioning-based,
annealing-based, analytical and numerical techniques
[Time permitting] Some advanced concepts in co-ordinated
place-n-route, modeling thermal constraints, CAD for lithography
- Grid routing, global routing, detailed channel routing,
Homeworks will constitute 50% of the grade. HW will also include
Final Project will constitute 50% of the grade. Each student will
have to complete an individual final project. The project will
constitute a study and implementation of a physical design
We will use the following text: VLSI Physical Design: From Graph
Partitioning to Timing Closure by Andrew B. Kahng, Jens
Lienig, Igor L. Markov, Jin Hu . ISBN 978-90-481-9590-9
Prof. Igor Markov has setup a website with all the presentation
slides and teaching materials for this book.
Another reference book: VLSI Physical Design automation by Sadiq
Sait and Habib Youssef, IEEE Press.
You may also find some material in the library and on the web
related to graph theory, basic graph algorithms and integer linear
Class Mailing List
I will be setting up a class mailing list soon.
Lecture Notes and Slides
In addition to the above materials, I may be uploading some extra
reading material over here.
01/06: Intro to the Course and organization, graph theory intro
01/08: Graph theory fundamentals: Connectivity, Cliques, Spans
01/10: Minimum Spanning Tree (Prim's algorithm) + Intro to Network-Flow
01/13: Formalization of Min-Cut/Max-Flow problems, Augmeting path
approach, Ford/Fulkerson algorithm
1/15: Assignment/Matching problem
1/17: Intro to Mathematical Optimization
1/22: Solving Linear Programs Lawrence Schlitt's
tutorial on Simplex
1/24: Max-Flow/Min-Cut MILP modeling, LP Duality
1/27: MILP Constraint modeling for floorplanning: bounds and
1/29: Floorplanning using MILP (some modules with fixed
orientation, others allowed rotation), graph-theoretic models of
1/31: Floorplanning completed.
2/3: Chapter 2, Partitioning intro, KL, FM and Simulated
2/3 - 2/10: Partitioning algorithms.
2/12: Chapter 4, wire-length estimation.
2/14: Wire-length estimation and Force directed method.
2/19: Force Directed Method completed. Please read this awesome
review paper by Shaookar and Mazumdar on
placement. Section 2 covers the placement problem using Force
directed method. Please study their algorithm (sec 2.2) and compare
with the one given in the book. We solved the same example in
2/21: Review of Simulated Annealing based Standard Cell placer:
2/24: Quadratic optimization-based placement. The approach of
GORDIAN , paper published in IEEE
TCAD 91. Another related paper asks the question:
Analytical Placement: A Linear or a Quadratic Objective
function? by the same authors, DAC 1991.
2/26: Introduction to Global routing, Ch 5 in the textbook. The
Gcells, and the ggrid. Congestion and obstacle modeling.
2/28: Maze routing, Lee's algorithm and it's
variations. Line-search algorithms.
3/3: Dijkstra's algorithm and it's application to global routing.
3/5: The A* search and basic ideas of Rip-up and Re-route.
3/7: Steiner Trees and FLUTE. Slides from Prof. Chu emailed to
3/8 - 3/16: Spring break
3/17: Review of the Boxrouter and Sidewinder paper
3/19: Channel routing, HCG, Zones and VCGs. Left-Edge algorithm
from the textbook. Also reviewed the bookshelf benchmark format.
3/21: The Dogleg Channel router
and the Yoshimura-Kuh channel router.
3/24: The YK router, a good set of slides can be download from
Prof. D. Pan's website .
3/26: Covered channel routing models for crossing minimization
using the VCG modification and the minimum feedback edge-set
Prof. S.K. Lim. Also covered channel routing by sorting. A good
description of sorting-based routing implementations is given
my recent paper , whereas here is the original paper titled:
Channel routing by sorting .
3/28: The greedy channel router, and its application to switchbox
routing (given in the textbook). Then moving on to over the cell
routing and area routing.
4/7: Conclude clock-tree routing and introduce timing closure.
4/9: Timing-driven placement: static timing analysis, false
paths. Chapter 8 in the textbook.
4/11: Timing budgets: the zero-slack algorithm for timing budgets
on nets. Here is the original paper on the
4/14: The quadratic assignment problem for placement, here is the
4/16: Placement using quadratic programming with linear
constraints: integrating partitioning and timing budgets in placements.
4/18: Lagrange relaxation + applications. Here is a good tutorial
paper on largrangian
4/21: We initiated discussions on complementary slackness and
Here are a set of notes on this topic that are very
accessible. This topic is employed in the "GRIP: Global Routing via
get the paper and slide set from here , and also look at the
For the week 01/06-01/10: Read Chapter 1 in the textbook.
For the week 02/21 - 2/28: Read the VLSI cell placement chapter
in the book and the paper by Shahookar and Mazumdar on
HW 1 is assigned, due Feb 7. Download from
HW 2 is assigned, due March 7. Download from
HW 3 is assigned, due April 14. Download from
Solutions to HW 3 , if you
want to take a look.
HW 4 is assigned, due April 30. Download from
Final project submission instructions can be
downloaded from here . Due
Wed May 7.
Options for Class Projects
Here is a description of potential
class project topics.
Software, tools, benchmarks
for Capo/Metaplacer and FastRoute/FLUTE tools. Download, compile,
play with the examples, learn the format and your project can use
these packages in your code.
Download LPSolve - an
integer-linear program solver (executable compiled on LINUX machines)
and some sample .lp files:
Hypergraph Partitioning --- hMeTis
Please visit the
hMeTiS website , and download the corresponding tar'ed package. Go
through the manual, and run 'shmetis 13207P.hgr 2 5' to perform a
FM-based bi-partition. Study the .hgr file format and the usage of the
shmetis partitioning program.
Utility packages - arrays, lists, symbol tables - for your projects
Packages: tar'ed and
gzipped here .
If you need some logic synthesis: The ABC tool from Alan Mishchencko, UCB
Go to Alan's website for the ABC synthesis tool and get the ABC
tool. This is the most advanced logic synthesis tool (techniques)
freely available. Link to
Alan's Website is here.