Stable Multiway Circuit Partitioning for ECO

Yongseok Cheon, Seokjin Lee, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

2 Citations (Scopus)

Abstract

We propose a new stable multiway partitioning algorithm, where stability is defined as an additional quality of a partitioning solution. The stability of a partitioning algorithm is an important criterion for a partitioning based placement to achieve timing closure through the repetition of the placement procedure. Given a previous partitioning result P* on an original netlist hypergraph H* and a partially modified netlist hypergraph H, a new cost function with similarity factor is defined to produce a new partition P on H which is similar to the original partition P*. The proposed algorithm is the first approach that quantifies the degree of similarity of a current partition to the original partition using similarity cost. Our goal is to build a new partition in a relatively short run time, whose cut quality is not much degraded from that of the original partition P* while it preserves as much of the previous groupings in P* as possible. The proposed partitioner is especially beneficial to engineering change order (ECO) applications, where partial modifications of a netlist are handled by the incremental methodology in a design iteration cycle. Our approach helps ECO placers maximize the incremental capability since the portions to be re-placed are minimized. Experimental results show that the proposed algorithm achieves a high quality partition comparable to a state-of-the-art multilevel partitioner hMetis, while many portions of the groupings in the previous partition are preserved in the current partition. The tradeoff between similarity and cut quality with respect to a varying similarity coefficient is also shown.

Original languageEnglish
Title of host publicationProceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003
Place of PublicationUnited States
PublisherIEEE
Pages718-725
Number of pages8
ISBN (Print)9781581137620
DOIs
Publication statusPublished - Nov 2003
Event2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003 - DoubleTree Hotel, San Jose, United States
Duration: 9 Nov 200313 Nov 2003
https://ieeexplore.ieee.org/xpl/conhome/8895/proceeding (Conference proceedings)

Publication series

NameProceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD
PublisherIEEE
ISSN (Print)1092-3152

Conference

Conference2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003
Country/TerritoryUnited States
CitySan Jose
Period9/11/0313/11/03
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

User-Defined Keywords

  • Engineering change order
  • Incremental partitioning
  • Placement
  • Similarity cost
  • Stable circuit partitioning

Fingerprint

Dive into the research topics of 'Stable Multiway Circuit Partitioning for ECO'. Together they form a unique fingerprint.

Cite this