Faster and more accurate wiring evaluation in interconnect-centric floorplanning

In deep submicron (DSM) era, the communication between different components is increasing significantly. It is not uncommon to see floorplanning problems with a relatively small number of blocks (e.g., 50) but has a large number of nets (e.g. 20K). Since existing floorplanning algorithms use simulated annelaing which needs to examine a large number of floorplans, the increasing number of nets has made interconnect-centric floorplanning computaionally very expensive. Moreover, there is almost no systematic way to resolve the congestion problem in such magnitude of number of nets in a given floorplan. In this paper, we present a simple yet effective idea to significantly reduce the runtime of interconnect-centric florplanning algorithms. Our idea is to group common nets between two blocks into a single net. This faster wiring evaluation technique is very effective. We also present a more accurate global router for wiring evaluation based on Lagrangian Relaxation. The new router helps further congestion reduction while doing interconnect planning in floorplanning. We have incorporated our algorithms into [2] and observed dramatic improvement in runtime. For a 33-block 15K-net problem, we reduced runtime from over 23 hours to less than 50 minutes.