Computer Science Dept., Technion IIT
Winter 2001/2002
URL: http://www.cs.technion.ac.il/~wagner/pub/aav.html
Last update:
January 15, 2002
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 smallscale 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 78 excercices with a mix of theoretical
and simulation (MATLAB) assignments. For more details, see the syllabus
below.
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 leafcell 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
noncomplementary CMOS styles: passgate logic, domino circuits, selfresetting 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 KernighanLin algorithm 

9.1  7  FiducciaMattheyses 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