ECE 556 Design Automation of Digital Systems

Final Examination Information

Date: December 22, 2004
Time: 12:25 - 2:25 PM
Location: 3534 EH

Rules: 

a. Closed book examination
b. Two single-side, letter-size "fact sheet" are allowed during exam. 

Coverage:

(Review materials, covered in the midterm)
Combinatorial algorithms, bin-packing problem (Appendix A, lecture notes)
Graph theory, shortest path algorithm (lecture notes)
Circuit paritioning: Kernighan-Lin, Fiduccia Mattheyses, Simulated Annealing
  (Section 2.1-2.4)
Floor planning, slicing structure, Polish expression, bounding curve, 
  Simulated annealing, mathematical programming method 
  (Section 3.1-3.2, 3.3.2, 3.3.3)

(New materials)
Placement (Chapter 4)
  Wire length estimate, 
  Criteria: total wire length, maximum cut, maximum density, 
  Linear placement 
  Min-cut placement, terminal propagation
  Simulated annealing placement
  Force-directed placement
  Genetic algorithm for placement

Grid Routing (Chapter 5)

  Maze router: 
    Lee algorithm
    Aker's Weighted cell array
    Hadlock's detour number

  Line search algorithms
    Mikami-Tabuchi's algorithm
    Hightower's algorithm
  
  Ordering of routing nets
 
  Minimum rectilinear Steiner tree (MRST)

Global Routing (Chapter 6)

   Sequential global routing
   Steiner tree heuristic

Channel Routing (Chapter 7)

   Horizontal and vertical constraint graph
   zone representation
   left edge algorithm, constrained left edge algorithm
   Dogleg algorithm
   Yoshimura and Kuh algorihtm
     net merging heuristics
   Greedy channel router
   switchbox routing