Reading Assignment:
http://nexus6.cs.ucla.edu/~cheese/survey.html. 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
changes.
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.