ECE-1387: CAD for Digital Circuit Synthesis and Layout

Spring 2010

NEWS:

  • You are welcome to come by to pick up your marked exercises & assignment #4.  Please email me to ensure that I'll be around when you come.  (May 2010)

  • Assignment #4 is posted and will be due on May 5, by email to instructor.  (April 13, 2010).

  • Remember to submit your scribe work, comprising 5% of your final grade.  The deadline is May 5, 2010.

  • Exercise #2 is posted (FM partitioning) and will be due on April 14 in class.

  • The guest lecture on April 14 will be by Dr. Vaughn Betz,
    Sr. Director, Altera Corp.

    Dr. Betz will speak about Altera's industrial place and route tools, including how they parallelized their placer to take advantage of modern multi-core microprocessors.  He manages the Altera Toronto Development Centre, responsible for CAD tools, device modeling, architecture, and IP development.  (March 31)

  • The course final paper will be due on May 5th, 5 PM, by email to instructor.  (March 24)

  • Assignment #3 posted (March 18)

  • Lecture #6 notes are posted (March 15)

  • Assignment #2 (AP) is posted, due on March 17, 2010. (March 3) -- see note added on March 10 (below).

  • Notes for lectures #3 and #4 are posted. (Feb 28)

  • Exercise #1 is posted and is due in class on March 3.  (Feb 19)

  • Assignment #1 (routing) is now due on February 17 at 11:59 PM by email to the instructor.  Late submissions will be penalized as noted on the handout.  (Feb 7)

  • Notes for lecture #2 are posted.  (Feb 9)

Basic Information

Instructor: Jason Anderson
    E-mail: janders@eecg.toronto.edu
    Web: http://www.eecg.toronto.edu/~janders
    Tel: 416-946-7285
    Office: EA314 (Engineering Annex)
Instructor's Office hours: Email or phone for an appointment (or drop by my office)
Lectures: Wednesdays from noon-2PM in BA 4164 (Bahen Building)

Overview

The course covers the approaches and algorithms for automatic circuit synthesis, with a concentration on the back-end of the CAD flow.  Topics covered will include: technology mapping, partitioning, placement, routing, timing analysis, and physical synthesis.  The course will include experience with existing CAD tools and building new tools in C.  We will pay special attention to synthesis issues as applied to Field-Programmable Gate Arrays (FPGAs).

This course will interest students whose research falls in the area of CAD and/or VLSI/FPGA architectures.  The course should also be of value to digital circuit designers, and anyone interested in learning about practical applications of combinatorial optimization algorithms.

Course Syllabus

Readings

Information on the Course Paper

Scribe Schedule and Lecture Notes

Lecture Number/Date Scribe Name and Notes (PPT, PDF)
#2 Jan 27 Kit (PPT, PDF) PPT is recommended as there is an animation.
#3 Feb 3 Peter (PDF)
#4 Feb 10 Ivan (PPT, PDF)
#5 Feb 24 Ali
#6 Mar 3 Shikuan (PDF)
#7 Mar 10 Victor
#8 Mar 17 Warren
#9 Mar 24 Bill, Marcel
#10 Mar 31
#11 Apr 7 Cedomir, Eugene
#12 Apr 14 N/A -- guest lecture

Assignments

Graphics package documentation (PDF)
Graphics package source code

Assignment #1 -- Routing (PDF) -- Assigned: Jan 27, 2010; Due: Feb 17, 2010.  Note: Assignment #1 is now due on Feb 17 at 11:59 PM by email to the instructor.  
Test circuits for assignment #1

Assignment #2 -- Analytical Placement (PDF) -- Assigned: March 3, 2010; Due: March 17, 2010
Test circuits for assignment #2
Information on linear system solver (UMFPACK)
Graphical display example (rat's nest of wires) (JPEG)
NOTE: Regarding question #2 on I/O placement, there are some fixed cells(blocks) placed at the same location in the test circuits.  When you vary the I/O placement randomly, you are to assume the same set of fixed locations, and you are allowed to place multiple cells(blocks) at a single fixed location.  

Assignment #3 (PDF) -- Partitioning by branch-and-bound optimization; Assigned: March 18, 2010; Due: Sunday April 4 at 11:59 PM by email to the instructor.
Test circuits for assignment #3

Assignment #4 (PDF) -- Technology mapping; Assigned: April 13, 2010; Due: May 5 at 11:59 PM by email to the instructor.
Test circuits for assignment #4

Exercises

Exercise #1 -- Simulated annealing placement and negotiated congestion routing
Handout (PDF)
VPR instruction manual (PDF)
VPR code (vpr_5.0.2_small.tar)
Circuits (alu4.net ex1010.net spla.net)
Architecture file: k4-n10.xml


Exercise #2 -- FM partitioning
Handout (PDF)
Code and circuits