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 |
---|---|
Title of host publication | Proceedings of The IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003 |
Place of Publication | United States |
Publisher | IEEE |
Pages | 718-725 |
Number of pages | 8 |
ISBN (Print) | 9781581137620 |
DOIs | |
Publication status | Published - Nov 2003 |
Event | 2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003 - DoubleTree Hotel, San Jose, United States Duration: 9 Nov 2003 → 13 Nov 2003 https://ieeexplore.ieee.org/xpl/conhome/8895/proceeding (Conference proceedings) |
Publication series
Name | Proceedings of the IEEE/ACM international conference on Computer-aided design, ICCAD |
---|---|
Publisher | IEEE |
ISSN (Print) | 1092-3152 |
Conference
Conference | 2003 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2003 |
---|---|
Country/Territory | United States |
City | San Jose |
Period | 9/11/03 → 13/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