Homework
Slides and Handouts
Useful Links
VLSI CAD Class Videos
Course Info
3 credits, Spring Semester 2008
Course web page: http://ece.iut.ac.ir/faculty/kia/Courses/VlsiCad
Class mailing list: NEW: Follow these instructions to subscribe (If you choose to receive the daily digest, then you will not receive individual messages as they are posted: instead they will be aggregated into a single message and sent to you at the end of the day).
Class: Sun, Tue 9:30-11:00am - Location: Mojtame 18
Mid-term Exam: date TBD, open notes, open book, and in class
Final Exam: 1387/04/04, 8:00-11:00am, open notes, open book.
Course Description:
Basic graph algorithms (e.g., shortest path, spanning tree). Partitioning, placement and routing. Algorithms for logic/high-level synthesis. Testing basics.
Who should take this course?
Graduate students and senior undergraduates. Knowledge of C/C++ programming is highly recommended. Knowledge of algorithms is NOT necessary.
Textbook (none required)
| [Sait99] | Sadiq M. Sait, Habib Youssef, "VLSI Physical Design Automation: Theory and Practice", World Scientific Publishing Company; 1st edition (November 15, 1999), ISBN: 9810238835. |
| [Mic94] | G. De Micheli, “Synthesis and Optimization of Digital Circuits”, McGraw-Hill, 1994. |
| [CLR90] | T. H. Cormen, C. E. Leiserson, R. L. Rivest, “Introduction to Algorithms”, MIT Press, 1990. |
| [Sar96] | M. Sarrafzadeh, C. K. Wong, “An Introduction to VLSI Physical Design”, McGraw-Hill, 1996. |
| [She99] | N. Sherwani, “Algorithms For VLSI Physical Design Automation”, Kluwer Academic Publishers, 3rd edition, 1999. |
Administrative
Please check the "Announcements" link regularly.
Grading:
- 30% Homework
- 10% presentations / papers
- 10% quizzes
- 20% Midterm - open book
- 30% Final exam.
Personnel:
| Instructor |
Kiarash Bazargan
|
||||||||
| TA | Mohammad Tahghighi | ||||||||
|
Course Outline / Approximate Schedule
| Week # | Lecture topics | Book Chapters |
| 1 |
Introduction EDA industry roadmap Design methodologies |
[Ger99] Ch 1-2 [She99] Ch 1 |
| 2-4 (2½ weeks) |
Algorithms Time complexity Problem tractability Deterministic algorithm classes Graph algorithms DFS, BFS Dijkstra's algorithm Minimum spanning tree- Prim |
[Ger99] Ch 3-5, [Sar96] Ch 1, [CLR90] Ch 23-25 |
| 4-6 (2½ weeks) |
Partitioning Kerlighan-Lin Fiduccia-Mattheyses hMetis |
[Ger99] Sec. 7.5 [Sar96] Ch 2 |
| 7-9 (2½ weeks) + Midterm |
Floorplanning Slicing floorplan sizing Wong-Liu's simulated annealing alg |
[Ger99] Ch 8 [Sar96] Ch 2 |
| 10-11 (1½ weeks) |
Placement Simulated annealing Force-directed Partitioning-based Recent placement algorithms |
|
| 11-13 |
Routing Global routing Steiner-tree Maze-routing Detailed routing: Channel routing Vertical/Horizontal constraint graphs Left-edge algorithm Greedy channel routing FPGA routing |
[Ger99] Ch 9 [She99] Ch 8-9 |
| 14-15 |
High-level Synthesis Scheduling |
[Mic94] Ch 4-5 |