Minimum delay placement with influence of nets and hierarchical clustering

This paper proposes a minimum delay placement employing a new net weighting method. A new factor to express the influence of a net on critical paths is incorporated in the conventional weight using slack allocation. This influence is defined for each net as the number of critical paths passing through it. An algorithm to calculate the influence is presented whose time complexity is O(n+b), where n is the number of nets and b is the number of blocks respectively. This net weighting method has been applied to the min-cut placement based on hierarchical clustering. The program has decreased the longest path delay by 21% for a benchmark containing 13141 blocks as compared with the case using only slack allocation