EAMTA 2006 - Bahia Blanca - Marcelo Johann

LIST OF EXERCICES

1-The algorithms/tools called Kernighan-Lin, Fiduccia-Mattheyses and hMetis solve which problem in VLSI CAD?

2-What is the difference between the meta-heuristic methods called Simulated Annealing and Threshold Accepting?

3-FastPlace is an Analytical Placement tool that solves a linear system of equations which minimizes a system of forces. What is the modeling and action it introduces for cell spreading and local refinement?

4-Cite applications in VLSI CAD for the graph problems of: a) shortest path, b) longest path, c) coloring, d) maximum clique, e) clique partitioning.

5-Write three examples of file formats that you can create as: a) input for a placement tool and output for a placement tool containing b) relative and c) absolute placements.

6-Draw two placement positions for a multi-pin network and show that different estimation methods will judge them in different ways.

7-Construct and Ordered BDD for a function you specify in a truth table of 4 variables.

8-What are the two major disadvantages of the Maze Router algorithm and how they are addressed today so that it is still widely used for routing?