Mel Breuer: CAD for VLSI

Reading Assignment: This is a paper by Alpert and Kahng entitled Recent Directions in Netlist Partitioning: A Survey. Students need not read (or download) sections 2.6, 3.5, 4.3, 4.4, 4.5, 5 and 6.

Three questions: (pick one and answer it in a one-page essay that you will hand in to Prof. Itti the monday following the talk, at noon in class):

        i. Explain the enhancements (changes) made by FM and
Krishnamurthy to the KL algorithm, and the ramifications of these

        ii. Describe a genetic algorithm approach to solve the
problem of 2-way partitioning of graphs.  In particular, suggest a
crossover scheme and/or a measure of goodness.

        iii. Consider applying a SA approach to solve the 2-way
partitioning problem on a circuit. Discuss the relationship between
the cooling schedule, quality of the final result and run-time.  How
would you go about making trade-offs between these three quantities?

Additional References:

        i. B. Kernighan and S. Lin, An efficient heuristic procedure
for partitioning graphs, Bell Syst. Technical J., 49(2):291-307, 1970.

        ii. S. Kirkpatrick, C. Gelatt and M. Vecchi, Optimization by
simulated annealing, Science, 220:671-680, 1983.

        iii. T. Bui and B. Moon, A fast and stable hybrid genetic
algorithm for the ratio-cut partitioning problem on hypergraphs,
Proc. Design Automation Conf., 664-669, 1994.