## 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 language | English (US) |
---|---|

Pages (from-to) | 718-725 |

Number of pages | 8 |

Journal | IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers |

State | Published - Dec 26 2003 |

Event | IEEE/ACM International Conference on Computer Aided Design ICCAD 2003: IEEE/ACM Digest of Technical Papers - San Jose, CA, United States Duration: Nov 9 2003 → Nov 13 2003 |

## 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