EFFECTIVE HEURISTIC ALGORITHMS FOR VLSI CIRCUIT PARTITION

The paper studies the multiway graph-partition problem for VLSI circui t partition. Given a graph representing a VLSI circuit, the graph vert ices are partitioned into mutually exclusive subsets to minimise the t otal weights for edges crossing the subsets under the constraint that the vertex weights are evenly distributed among the subsets. Simulated annealing and tabu search are adapted to solve this problem based on a special neighbourhood design. A new general optimisation paradigm, c alled stochastic probe, is then proposed to integrate the advantages o f the above two approaches. Extensive experimental study shows that al l three new algorithms produce significantly better solutions than the LPK algorithm reported by Lee, Park and Kim, and that the stochastic probe algorithm always produces the best solution among all the four a lgorithms with a running time comparable with that for the LPK algorit hm.