Further Improve Circuit Partitioning Using GBAW Logic Perturbation Techniques

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

11 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)451-460
Journal / PublicationIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number3
Publication statusPublished - Jun 2003
Externally publishedYes


Efficient circuit partitioning is becoming more and more important as the size of modern circuits keeps increasing. Conventionally, circuit partitioning is solved without altering the circuit by modeling the circuit as a hypergraph for the ease of applying graph algorithms. However, there is room for further improvement on even optimal hypergraph partitioning results, if logic information can be applied for circuit perturbation. Such logic transformation based partitioning techniques are relatively less addressed. In this paper, we present a powerful multiway partitioning technique which applies efficient logic rewiring techniques for further improvement over already superior hypergraph partitioning results. The approach can integrate with any graph partitioner. We perform experiments on two-, three-, and four-way partitioning for MCNC benchmark circuits whose physical and logical information are both available. Our experimental results show that this partitioning approach is very powerful. For example, it can achieve a further 12.3% reduction in cut size upon already excellent pure graph partitioner (hMetis) results on two-way partitioning with an area penalty of only 0.34%. The outperforming results demonstrate the usefulness of this new partitioning technique.

Research Area(s)

  • Alternative wiring, Partitioning