Algorithmic Aspects in VLSI Design (CS 236610-20)


Computer Science Dept., Technion IIT

Winter 2001/2002 
URL: http://www.cs.technion.ac.il/~wagner/pub/aav.html
Last update:  January 15, 2002 

Contents
  1. General
  2. Pre-Requirements
  3. Requirements
  4. Notes to students
  5. Syllabus
  6. Schedule
  7. Lecture Notes
  8. MATLAB examples
  9. Links and References

General 

Teacher: Dr. Israel Wagner
email:   wagner@cs.technion.ac.il
Tel: 972-4-8296331
Reception:  Taub 720 on Wednesday 11:00-12:00,
or by appointment (via phone or email)

This course is about algorithms involved in the design process of VLSI systems. We shall start with CMOS implementation of small logic gates and discuss the problems of circuit synthesis and layout optimization for these small-scale systems. Then we?ll discuss higher level issues: circuit partitioniong, Floorplanning and global routing. The topic of compaction will end the physical design part. The last part of the course will involve highlights of network theory, ASIC design and (maybe) some more advanced topics. The students will have to hand 7-8 excercices with a mix of theoretical and simulation (MATLAB) assignments. For more details, see the syllabus below.
 

Class: Wednesday 8:30-10:30, Taub 004
Pre-requirements
  1. Graph Algorithms
  2. Logic Design ("TECHEN LOGI")
Grading
  1. attending classes 
  2. doing homework. There will be 3-4 excercises, with theoretical and practical (MATLAB) problems.
  3. prseneting a paper to the class
Notes to students
  1. Students should register to the course in order to be graded
  2. A file with background material is in EE library
  3. (3.12.2001) Due to shortening of the semester, there will be no MATLAB assignment.

    4. In order to be graded, a student should:
    1. attend class
    2. submit 3 homework assignments
    3. read a paper or two and presnt the material in class
Syllabus
A preliminary list of topics
  1. introduction
  2. CMOS devices and their applications:
    1. static circuits and polish expressions
    2. dual graphs and dual-Euler cycles
    3. optimal flipping and dynamic programming
    4. Interval graphs, coloring
  3. introduction to MATLAB
  4. circuit partitioning:
    1. Kernighan-Lin algorithm and its variations
    2. simulated annealing/evolution
  5. floorplanning:
    1. slicing vs. non-slicing, duality
    2. polish representation, heuristics.
  6. routing:
    1. classification
    2. maze, steiner, shortest path algorithms
    3. clock routing, H-tree
  7. compaction:
    1. 1D, 2D compaction
    2. heuristics
  8. network theory:
    1. Kirchoff and Ohm laws, Tellegen's theorem
    2. Algorithmic solution to static networks
    3. Rayleigh's principles
    4. random walk and electrical resistance
  9. introduction to ASIC: design flow, tools and challenges
  10. advanced topics
    1. yield estimation
    2. interconnect problems
    3. analog vs. digital circuits: ADC example
 
Preliminary schedule

 
date # topic assignment
24.10 1 course overview
introduction to CMOS devices
31.10 2 implementing logic gates with static CMOS circuits, polish expressions
[introduction to MATLAB]
5.12 3 the leaf-cell layout problem: placement, orientation, routing, compaction
dynamic programming for the optimal flip problem		 ex1: static CMOS circuits
12.12 (Hanuka) 4 generalization of dynamic programming
non-complementary CMOS styles: passgate logic, domino circuits, self-resetting logic
19.12 5 algorithms for the general cell layout problem by means of A* ex2: dynamic programming
26.12 6 the circuit partitioning problem
the Kernighan-Lin algorithm
9.1 7 Fiduccia-Mattheyses partition algorithm
a lower bound on bipartitions (Barnes's bound)		 ex3: partitioning
16.1 8 global placement - mincut method, springs method, Metropolois method
23.1 9 Simulated Annealing ex4: global placement & routing
30.1 10 Students:
1) Dan Guez: "A Clustering Algorithm based on Graph Connectivity"  (by Hartuv & Shamir)
2)Alexander Naslednikov: An Efficient Algorithm for Some MultiRow Layout Problems (by Feldman, Wagner, Wimer)
6.2 11 Students:
1) Gilad Mittelman: An Interactive VLSI CAD Tool for Yield Estimation (by Wagner & Koren)
2) Roman Barsky: "Towards an energy complexity of the computation" (by Alain J. Martin)

Some Preliminary Lecture Notes


Introduction to CMOS (lectures 1,2,3)
Partitioning #2: Fiduccia-Mattheyses, Barnes' lower bound (transcripted by Uri Dekel)
The general placement problem (transcripted by Uri Dekel)
Gate Array placement, Simulated annealing (transcripted by Uri Dekel)
Routing I: channel routing (transcripted by Uri Dekel)

MATLAB examples


directory of MATLAB examples
 
Links and References
  1. Conferences
    1. Design Automation Conference (DAC)
    2. International Conference on Computer Aided Design (ICCAD)
    3. International Symposium On Low Power Electronics And Design (ISLPED)

      4.  
  2. Books
    1. N. Weste, K. Eshragian, Principles of CMOS VLSI Design - A Systems Perspective, Addison-Wesley 1993.
    2. C. A. Desoer, E. S. Kuh: Basic Circuit Theory, McGraw-Hill 1969
    3. T. Lengauer: Combinatorial Algorithms for Integrated Circuit Layout, John Wiley 1990.
    4. V. Litovski, M. Zwolinski: VLSI Circuit Simulation and Optimization, Chpman & Hall 1997
    5. N. Shrwani: Algorithms for VLSI Physical Design Automation, Kluwer 1995.
    6. J. Ullman: Computational Aspects of VLSI, CS Press, 1984
    7. M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1965.
    8. P. J. M. Van Laarhoven, E. H. L. Aarts, Simulated Annealing : Theory and Applications.

      9.  
  3. Papers (those with [*] are to be presented by students)
    1. Bar-Yehuda, R., J. A. Feldman, R. Y. Pinter, and S. Wimer."Depth first search and dynamic programming algorithms for efficient cmos cell generation." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 8(7), 1989
    2. [*] J. A. Feldman, I. A. Wagner, S. Wimer, "An Efficient Algorithm for Some MultiRow Layout Problems",

      3. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, August 1993.
    3. C. M. Fiduccia, R. M. Mattheyses, "A linear time heuristic for improving network partitions",

      4. DAC 1982.
    4. B. W. Kernighan, S. Lin, "An efficient heuristic procedure for partitioning graphs",

      5. Bell Systems Technical Journal, 49(2):291-307, 1970.
    5. [*] E. R. Barnes, "An algorithm for partitioning the nodes of a graph",

      6. SIAM Journal of Algebraic and Discrete Methods, 3(4):541-550, 1982.
    6. [*] B. Hajek, "Cooling schedules for optimal annealing",

      7. Mathematics of operations research,13(2):311-329, 1988.
    7. [*] Gregory B. Sorkin, "Efficient Simulated Annealing on Fractal Energy Landscapes",

      8. Algorithmica 6(3):367-418 (1991).
    8. [*] I. A. Wagner, I. Koren, "An Interactive VLSI CAD Tool for Yield Estimation",

      9. IEEE Transactions on Semiconductor Manufacturing, MAY 1995.
    9. [*] C. J. Alpert and A. B. Kahng, " A General Framework for Vertex Orderings, With Applications to Circuit Clustering", IEEE Transactions on VLSI Systems, 4(2), 1996, pp. 240-246
    10. [*] bTung-Yang Ho, Ting-Yi Sung, Lih-Hsing Hsu, Chang-Hsiung Tsai, Jeng-Yan Hwang: "The Recognition of Double Euler Trails in Series-Parallel Networks."  Journal of Algorithms 28(2): 216-257 (1998)
    11. [*] Robert L. Maziasz, John P. Hayes, "Layout optimization of static CMOS function cells," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 9-7, July 1990. p. 708-719.
    12. [*] E. Hartuv, R. Shamir, "A Clustering Algorithm based on Graph Connectivity. ", Information Processing Letters, 76 (2000) pp. 175-181.
    13. A. Thompson, P. Layzell,. (1999), "Analysis of unconventional evolved electronics", Communications of the ACM, 42(4): 71-9.
    14. [*] A. Thompson, P. Layzell, R. S. Zebulum, "Explorations in Design Space: Unconventional electronics design through artificial evolution", IEEE Trans. Evol. Comp., 3(3):167-196, 1999.

      15.  
  4. Tools / Sites
    1. MATLAB at MathWorks: http://www.mathworks.com/products/matlab/
    2. MathPages on "Generating the Monotone Boolean Functions"
    3. Mike Trick's  Tutorial on Dynamic Programming
    4. Animated CMOS Circuit Simulator (a JAVA applet)
    5. A compendium of NP optimization problems
    6. Steiner Trees
    7. eedesign.com - EE design tools
Back to top

Research Topics in VLSI

  1. ADC design and analysis
    1. pipeline SNR error analysis (see DAC paper)
  2. CAD tools for analog & mixed signal (AMS) VLSI
    1. automatic simplifications of large circuits
    2. power minimization methods (software and hardware)
  3. Visulization in VLSI
    1. Current flow map
    2. CMOS ckt: 3D version of the CMOS Java animated simulator
  4. Evolvable hardware
    1. adaptive ADC
    2. adaptive line driver
Back to top