Stanford InfoLab Publication Server

Multi-way VLSI Circuit Partitioning Based on Dual Net Representation

Cong, J. and Labio, W. and Shivakumar, N. (1994) Multi-way VLSI Circuit Partitioning Based on Dual Net Representation. In: IEEE International Conference on Computer-Aided Design (ICCAD 1994), November 6-10, 1994, San Jose, CA.




We study the area-balanced multi-way partitioning problem of VLSI circuits based on a new dual netlist representation named the hybrid dual netlist (HDN). Given a netlist, we first compute a K-way partition of the nets based on the HDN representation, and then transform a K-way net partition into a K-way module partitioning solution. The main contribution of our work is the formulation and solution of the K-way module contention (K-MC) problem, which determines the best assignment of the modules in contention to partitions, while maintaining user-specified area requirements, when we transform the net partition into a module partition. Under a natural definition of binding factor between nets and modules, and preference function between partitions and modules, we show that the K-MC problem can be reduced to a min-cost max-flow problem. We present efficient solutions to the K-MC problem based on network flow computation. Extensive experimental results show that our algorithm consistently outperforms the conventional K-FM partitioning algorithm by a significant margin.

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:49
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:05 Feb 2009 15:21

Download statistics

Repository Staff Only: item control page