A Fast Data Structure for HPWL Based on Reusablity Analysis

In the process of solution evaluation for simulated annealing, the computation for wire-length is still a time consuming part, though now the buffer planning and thermal model have taken up a lot of time. And the traditional wire-length model HPWL executes in O(ntimesm) time in which n stands for the number of nets and m is the average number of the modules that the nets connect. In order to reduce the time for HPWL calculation, we propose two new data structures in this paper: "Nets Union" and "Subset Chain" to handle two typical kinds of reusable nets information respectively that are "Complete Overlap" and "Partial Overlap". Then the HPWL calculation can be finished in O(alphantimesbetam),0<alpha,beta<1. And our experiment results show the effectiveness of our algorithm