A proper model for the partitioning of electrical circuits

D. G. Schweikert, Brian W. Kernighan

Research output: Contribution to journalConference article

107 Scopus citations

Abstract

Partitioning algorithms for electrical circuits are often based on the heuristic manipulation of a simple element-toelement interconnection matrix. However, the element-to-element interconnection matrix does not properly represent an electrical interconnection, or "net", among more than two elements. This paper expands on several aspects of the discrepancy: i) its source, 2) the circumstances under which it is likely to be significant, and its magnitude for typical circuits, and 3) the comparative difficulty and expense of using a more appropriate representation. A physically correct "net-cut" model is presented. This model is computationally straightforward and is easily adapted to the typical heuristic solution strategies. The "net-cut" model is coupled with the Kernighan-Lin partitioning algorithm [3]; using the same algorithm, comparisons with the "edge-cut" model demonstrate that the correct model reduces net-cuts by 19 to 50% for four digital logic circuits.

Original languageEnglish (US)
Pages (from-to)57-62
Number of pages6
JournalProceedings - Design Automation Conference
DOIs
StatePublished - Jun 26 1972
Externally publishedYes
Event9th Design Automation Workshop, DAC 1972 - Dallas, United States
Duration: Jun 26 1972Jun 28 1972

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation

Fingerprint Dive into the research topics of 'A proper model for the partitioning of electrical circuits'. Together they form a unique fingerprint.

  • Cite this