New graph-based algorithms for partitioning VLSI circuits

Christopher J. Augeri, Hesham H. Ali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations


When designing a circuit, it may be too large to fit on a single layer of a chip, on a single chip, or on a single board. Regardless of the design level, the same objectives remain. Normally, it is desirable to minimize the number of layers, chips, or boards, along with minimizing the delay. Additional constraints, such as the number of interconnections and power consumption, must often be considered. We have developed two k-way bounded partitioning algorithms; one is evolutionary-based, while the other is a hierarchical graph center-based approach. The algorithms are implemented and compared with known partitioning algorithms. Since VLSI circuits can be naturally modeled by graphs, experiments were conducted by partitioning graphs from various graph families against both simulated and real-world partitioning criteria. A direct result of this research is a high-level abstract graph-partitioning model. This model allows one to specify mathematical evaluation metrics and control parameters, permitting inter-domain comparison of algorithms and allowing one to identify the particular scenarios they are best applicable to.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Symposium on Circuits and Systems
StatePublished - 2004
Event2004 IEEE International Symposium on Circuits and Systems - Proceedings - Vancouver, BC, Canada
Duration: May 23 2004May 26 2004


Other2004 IEEE International Symposium on Circuits and Systems - Proceedings
CityVancouver, BC

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Electrical and Electronic Engineering


Dive into the research topics of 'New graph-based algorithms for partitioning VLSI circuits'. Together they form a unique fingerprint.

Cite this