Algorithms and methodologies for the synthesis, analysis, and verification of digital systems.  Topics include: modeling languages (VHDL, Verilog, …) and hardware compilers. Silicon compilation. High-level synthesis, logic synthesis, and layout synthesis.  Logic and circuit simulation.  Placement and routing algorithms.   Introduction to digital testing.  A major part of this course includes the integration of CAD tools into complete design automation systems.

tudents shall be able to demonstrate:

1. An understanding of the VLSI CAD process and methodologies.
2. An understanding of what CAD tools available for digital design and where they are used.
3. An understanding of different design capture methods and the tools that support them
4. A knowledge of synthesis algorithms, and the underlying strengths and weaknesses of the tools
5. An understanding of algorithms for VLSI placement, routing, and floorplanning

Professor Haidar M. Harmanani

haidar@lau.edu.lb • http://vlsi.byblos.lau.edu.lb • http://harmanani.github.io

Office Hours:

Block A • Room 810

Tuesday, Thursday • 3:00pm – 4:30pm • 8:00pm – 9:30pm or by appointment

August 28, 2016: Fall classes begin

October 4, 2016:  Last day for early withdrawal (WI)

October 26, 2016: Deadline for Incomplete grades

November 3, 2016: Midterm Examination

November 9, 2016: Last day for withdrawal from courses (WP/WF)

December 8, 2016: Fall classes end

Lecture 1: Course Introduction and Design Methodologies

Lecture 2: Algorithmic Techniques for VLSI Design Automation

Lecture 3: General-purpose Methods for Combinatorial Optimization

Lecture 4: High-Level Synthesis (Scheduling)

Lecture 5: High-Level Synthesis (Allocation)

Lecture 6: Netlist and System Partitioning

Lecture 7: Chip Planning and Floorplanning

Lecture 8: Placement Additional Notes

Lecture 9: Routing

Lecture 10: Simulation

Lecture 11: Logic Synthesis

Additional Notes: VLSI Testing

Additional Notes: SOC and NOC Design and Test

Course Project I: A Mini High-Level Synthesis System

Sample Input Files: Sample Data Flow Graphs for testing the project

Final Report Template

The objectives of the project are to initiate students into research by converting the theoretical description of one or more algorithms into a functioning implementation while making a minor contribution.  The following should be handed over upon the termination of the project:

• A short report (5 to 10 pages) documenting the program. It consists of a description of the main data structures and procedures (using pseudo-code), a motivation of the choices made, an analysis of the time complexity, and a presentation of some results;
• A listing of all the code written with sufficient comment to make the code easily understandable;
• The program itself (delivered e.g. by email) such that it can be tested.

Please check the CADathlon Contest website for projects selection and references

All students are expected to take exams during the scheduled time slots. With the permission of the instructor, you may be allowed to take an exam at an alternate time. However, you must request this rescheduling at least 2 weeks prior to the exam date. Exceptions will naturally be made for sudden problems such as serious illnesses/injury. Since the exam schedule is being published at the beginning of the semester, scheduling conflicts (e.g., job interviews, GREs, etc.) are not legitimate reasons to miss an exam.

Midterm Exam

The midterm exam is scheduled for November 3, 2016: Midterm Examination. The midterm exam will be a closed book exam. In principle, all topics discussed in class (whether on the lecture notes or not) and in the assigned readings are a legitimate source for exam questions.

Final Exam

The final will be comprehensive, with roughly 1/3 of the material devoted to material covered prior to the midterm.  The exam will be on May 15, 2015 from 8:00 am - 11:00 am.

Midterm Grades

Final Grades

Course Grades

Code

 Codes of Partitioning Algorithms

1. High-Level Synthesis: Tutorial 1, Tutorial 2, Tutorial 3, Force-Directed Scheduling, and Facet
2.  R. Rajaraman and D. F. Wong, "Optimal Clustering for Delay Minimization", IEEE Trans. on Computer-Aided Design, 14(1), pp 1074-1085, 1992.
3.  J. Cong and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs", IEEE Trans. on Computer-Aided Design, 13(1), pp 1-12, 1994.
4.  G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Domain", IEEE Trans. on VLSI, 7(1), pp 69-79, 1999.
5.  B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits", Bell System Technical Journal", pp 291-307, 1970.
6.  C. M. Fiduccia and R. M. Mattheyses. "A linear-time heuristic for improving network partitions", Proceedings of the Design Automation Conference, pp 174-181, 1982.
7.  L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", IEEE Trans. on Computer-Aided Design, 11(9), pp 1074-1085, 1992.
8.  H. Yang and D. F. Wong, "Efficient Network Flow Based Min-cut Balanced Partitioning", IEEE Trans. on Computer-Aided Design, 15(12), pp 1533-1540, 1996.
9.  L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs", 57(2-3), Information and Control, pp 91-101, 1984.
10.  D. F. Wong and C. L. Liu, "Floorplan design of VLSI circuits", Algorithmica, 4(1), pp 263-291, 1989.
11.  S. Sutanthavibul, E. Shragowitz, and J. Rosen, "An analytical approach to floorplan design and optimization", IEEE Trans. on Computer-Aided Design, 10(6), pp 761-769, 1991.
12.  H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair", IEEE Trans. on Computer-Aided Design, 15(12), pp 1518-1524, 1996.
13.  M. Breuer, "A Class of Min-cut Placement Algorithms", Proceedings of the Design Automation Conference, pp 284-290, 1977.
14.  A. Dunlop and B. Kernighan, "A Procedure For Placement Of Standard-cell VLSI Circuits", IEEE Trans. on Computer-Aided Design, 4(1), pp 92-98, 1985.
15.  J. Kleinhaus, G. Sigl, F. Johannes, K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on Computer-Aided Design, 10(3), pp 356-365, 1991.
16.  W. J. Sun and C. Sechen, "Efficient and Effective Placement for Very Large Circuits", IEEE Trans. on Computer-Aided Design, 14(3), pp 349-359, 1995.
17.  J. M. Ho, G. Vijayan, and C. K. Wong, "New algorithms for the rectilinear Steiner tree problem", 9(2), IEEE Trans. on Computer-Aided Design, pp 185-193, 1990.
18.  A.B. Kahng and G. Robins, "A new class of iterative Steiner tree heuristics with good performance", IEEE Trans. on Computer-Aided Design, 11(7), pp 893-902, 1992.
19.  M. Borah, R. Owens, and M. Irwin, "An Edge-based Heuristic for Steiner Routing", IEEE Trans. on Computer-Aided Design, 13(12), pp 1563-1568, 1994.
20.  J. Cong, A.B. Kahng, G. Robins, M. Sarrafzadeh, and C.K. Wong, "Provably good performance-driven global routing", IEEE Trans. on Computer-Aided Design, 11(6), pp 739-752, 1992.
21.  J. Cong, K.-S. Leung, and D. Zhou, "Performance-Driven Interconnect Design Based on Distributed RC Delay Model", UCLA CSD Tech Report #9200043, 1992.
22.  K. Boese, A. B. Kahng, B. McCoy, and G. Robins, "Near-optimal critical sink routing tree constructions", IEEE Trans. on Computer-Aided Design, 14(12), pp 1417-1436, 1995.