A constructive multi-way circuit partitioning algorithm based on minimum degree ordering

Ankara : The Department of Computer Engineering and Information Science and the Institute of Engineering and Science of Bilkent Univ., 1994.Thesis (Master's) -- Bilkent University, 1994.Includes bibliographical references leaves 52-54.Circuit partitioning has many important applications in VLSI. Circuit partitioning problem can be most properly modeled as hypergraph partitioning. In this work, we propose a novel k-v/ay hypergraph partitioning heuristic using the Minimum Degree (MD) ordering which is a well-known heuristic for reducing the amount of fills in the factorization of symmetric sparse matrices. The proposed algorithm operates on the dual graph of the given hypergraph. The algorithm grows node-clusters on the dual graph which induce cell-clusters with locally minimum net-cut sizes. The quotient graph concept, widely used in MD ordering, is exploited for the sake of efficient implementation. The proposed algorithm outperforms well-known heuristics, such as Kernighan-Lin (KL) based algorithms and Simulated Annealing, in terms of solution quality on various VLSI benchmark circuits. A nice property of the proposed algorithm is that its execution time reduces with increasing k as opposed to the existing iterative heuristics. It is even faster than the fast KL-based algorithms on the partitioning of the benchmark circuits for k > 16.Çatalyürek, Ümit VM.S