Stable Multiway Circuit Partitioning for ECO

Yongseok Cheon, Seokjin Lee, Martin D F Wong

Research output: Contribution to journalConference article

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 (US)
Pages (from-to)718-725
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 26 2003
EventIEEE/ACM International Conference on Computer Aided Design ICCAD 2003: IEEE/ACM Digest of Technical Papers - San Jose, CA, United States
Duration: Nov 9 2003Nov 13 2003

    Fingerprint

Keywords

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

ASJC Scopus subject areas

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

Cite this