This paper presents a multilevel hypergraph partitioning method that balances constraints on not only the cell area but also the wire weight with a partition-based global placement algorithm that maximizes the wire de...This paper presents a multilevel hypergraph partitioning method that balances constraints on not only the cell area but also the wire weight with a partition-based global placement algorithm that maximizes the wire density uniformity to control chemical-mechanical polishing （CMP） variations. The multilevel partitioning alternately uses two FM variants in the refinement stage to give a more uniform wire distribution. The global placement is based on a top-down recursive bisection framework. The partitioning algorithm is used in the bisectioning to impact the wire density uniformity. Tests show that, with a 10% constraint, the partitioning produces solutions with more balanced edge weights that are 837% better than from hMetis, 1039.1% better than MLPart, and 762.9% better than FM in terms of imbalance proportion and that this global placement algorithm improves ROOSTER with a more uniform wire distribution by 3.1% on average with an increased wire length of only 3.0%.展开更多
基金Supported by the National Natural Science Foundation of China(Nos. 60876026 and 60833004)
文摘This paper presents a multilevel hypergraph partitioning method that balances constraints on not only the cell area but also the wire weight with a partition-based global placement algorithm that maximizes the wire density uniformity to control chemical-mechanical polishing （CMP） variations. The multilevel partitioning alternately uses two FM variants in the refinement stage to give a more uniform wire distribution. The global placement is based on a top-down recursive bisection framework. The partitioning algorithm is used in the bisectioning to impact the wire density uniformity. Tests show that, with a 10% constraint, the partitioning produces solutions with more balanced edge weights that are 837% better than from hMetis, 1039.1% better than MLPart, and 762.9% better than FM in terms of imbalance proportion and that this global placement algorithm improves ROOSTER with a more uniform wire distribution by 3.1% on average with an increased wire length of only 3.0%.
