CSCI 3320/8325 and CSCI 4350/8356 or permission of instructor.

Credit Hours:

Three credit hours.

Objectives:

The main objective of this course is to obtain a thorough understanding of the various design steps in manufacturing highly integrated circuits. Although the general hardware principles of circuit design will be presented, the course emphasizes the software design principles involved with the physical design process. In particular, algorithms for circuit partitioning, placement, routing, and compaction will be discussed in details.  The rest of the objects can be summarized as follows:

• To introduce students to the basic concepts of VLSI design with an emphasis on algorithmic aspects of circuit layout.
• To present the basic hardware foundations of circuit layout.
• To give an overview of what are the most important problems in the design of VLSI circuits and analyzes various solutions for each problem.
• To cover algorithms used in layout systems today, as well as new algorithmic developments that bear some promise of stimulating the improvement of layout systems in the future.
• At the end of this course, a student should be familiar with the basic terminology in VLSI and the combinatorial algorithms for the various problems in the design process of VLSI circuits.

Evaluation:

Course grade will be based on exams, homework, presentations and individual projects.

• Midterm exam 15%
• Homework 25%
• Presentation 10%
• Project 25%
• Final Exam 25%

Also, standard grading scheme will be used:

95 % and above    A+
90% - 94.9%        A
85% - 89.9%        B+
80% - 84.9%        B
75% - 79.9%        C+
70% - 74.9%        C
65% - 69.9%        D+
60% - 64.9%        D
Below 60%           F

The course introduces the basic concepts of VLSI design automation. A general background of optimization problems and graph algorithms that are related to circuit layout is also presented. The course covers mainly the various algorithms used in the different phases of circuit design process, in particular, circuit partitioning, placement, routing, and compaction.

• General introduction to VLSI circuit layout.
• Presentation of the algorithmic, mathematical and graph theoretical foundations of circuit layout.
• Layout optimization problems.
• Circuit partitioning: definitions, complexities and algorithms.
• Network flow and graph partition circuit partitioning.
• Placement, assignment, and floorplanning.
• Global routing and area routing.
• Planar and non-planar routing.
• Applications of interval graphs in single row routing.
• Graph-based compaction.
• Hierarchical compaction and topological compaction.
• Recent development in graph theoretic approaches for solving problems related to placement and floorplanning.

Text Books:

Naveed Sherwani, Algorithms for VLSI Physical Design, Kluwer Academic Publishers, second edition, 1995.

References:

• Thomas Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, John Wiley & Sons, 1990.

• H. B. Bakoglu, Circuits, Interconnections, and Packing for VLSI, Addison-Wesley, 1990.

• 1.      Douglas A. Pucknell and Kamran Eshraghian, Basic VLSI Design: Systems and Circuits, Prentice-Hall, 1988.

• Angel L. DeCegama, The Technology of Parallel Processing: parallel Processing Architectures and VLSI Hardware, Volume 1, Prentice-Hall, 1989.

• Carver Mead and Lynn Conway, Introduction to VLSI Systems, Addison-Wesley, 1980.

• Hesham Ali and Naveed Sherwani, Introduction to Graph Algorithms, Wiley, 2000.

• Aho, J. Hopcraft and J. Ullman, The Design and Analysis of Algorithms, Addison-Wesley, 1974.

• M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.

• Ronald Gould, Graph Theory, Benjamin/Cummings, 1988.

• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.