Advanced Hypergraph Partitioning Heuristics with VLSI Layout Applications

Anthony Vannelli
Department of Electrical and Computer Engineering
University of Waterloo

The circuit layout problem that arises in modern Very Large Scale Integrated (VLSI) circuit design is a very key problem with the ever increasing size of circuits that contain over 100 million transistors and reaching .1 submicron designs. Hypergraph partitioning is a key problem that circuit designers must address that leads to better layouts which minimize wirelengths, circuit area and delays. Hypergraph partitioning is an NP-hard problem. This talk will introduce current state of the art techniques that yield excellent partitioning results. In particular, we focus on (i) new efficient eigenvector approaches to obtain good partitions and (ii) metaheuristic node interchange techniques to reduce the number of cuts further. Numerical results on large-scale circuit layout problems are also reported.