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
  • Floor-planning
  • Placement
  • 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.