##
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

### Instructor

Priyank Kalla
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,
thermal-issues, etc.
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:

Partitioning
- Kernighan-Lin, Fiduccia-Mattheyses, Simulated Annealing

Floor-planning
- Floorplan models, graph-techniques, analytical techniques

Placement
- Cost functions and estimations, partitioning-based,
annealing-based, analytical and numerical techniques

Routing
- Grid routing, global routing, detailed channel routing,
over-the-cell routing

[Time permitting] Some advanced concepts in co-ordinated
place-n-route, modeling thermal constraints, CAD for lithography
issues, etc.
### Grading

Homeworks will constitute 50% of the grade. HW will also include
programming assignments.
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
automation technique.
No exams.
## Textbook

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
programming.
### 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/20: Holiday
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
rotation constraints
1/29: Floorplanning using MILP (some modules with fixed
orientation, others allowed rotation), graph-theoretic models of
floorplans.
1/31: Floorplanning completed.
2/3: Chapter 2, Partitioning intro, KL, FM and Simulated
annealing.
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
VLSI cell
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
class.
2/21: Review of Simulated Annealing based Standard Cell placer:
Timberwolf.
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
the class.
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
problem. Paper
by
Prof. S.K. Lim. Also covered channel routing by sorting. A good
description of sorting-based routing implementations is given
in
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
zero-slack algorithm.
4/14: The quadratic assignment problem for placement, here is the
problem
formulation.
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
relaxation techniques.
4/21: We initiated discussions on complementary slackness and
duality theory.
Here are a set of notes on this topic that are very
accessible. This topic is employed in the "GRIP: Global Routing via
Integer Programming",
get the paper and slide set from here , and also look at the
summary slides.
### Reading Assignments

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
VLSI cell
placement review.
### Homeworks

HW 1 is assigned, due Feb 7. Download from
here .
HW 2 is assigned, due March 7. Download from
here .
HW 3 is assigned, due April 14. Download from
here .
Solutions to HW 3 , if you
want to take a look.
HW 4 is assigned, due April 30. Download from
here .
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

Download instructions
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.
### Linear Program

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.