next up previous
Next: A Graph Problem Up: Examples of Optimization Previous: Examples of Optimization

Graph Partitioning

In designing computer chips, there are a number of connected elements. If there are too many elements to fit on one chip, they need to be partitioned onto (for example) two chips. Since wires between chips are expensive, the number of connections between chips should be minimized. Since silicon area is also expensive, the number of elements on each chip should be about the same.

This is an example of a graph partitioning problem. If we consider the elements as vertices and the wires as edges, the problem is to partition the graph into two equal sets while minimizing the number of edges between each set. This is known to be an NP-hard problem.

This was the application to which simulated annealing was first applied (see the paper by Kirkpatrick et al.)



Paul Coddington, Northeast Parallel Architectures Center at Syracuse University, paulc@npac.syr.edu