Faster and more accurate wiring evaluation in interconnect-centric floorplanning

H. M. Chen, D. F. Wong, W. K. Mak, H. H. Yang

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)62-67
Number of pages6
JournalProceedings of the IEEE Great Lakes Symposium on VLSI
StatePublished - 2001
Externally publishedYes
Event11th Great Lakes Sysmposium on VLSI (GLSVLSI 2001) - West Lafayette, IN, United States
Duration: Mar 22 2001Mar 23 2001

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Faster and more accurate wiring evaluation in interconnect-centric floorplanning'. Together they form a unique fingerprint.

Cite this