Optimal redistribution of white space for wire length minimization

Xiaoping Tang, Ruiqi Tian, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

37 Citations (Scopus)

Abstract

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good to meet other objectives such as minimizing total wire length which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. In this paper, we first show that the problem can be formulated as linear programming. Thereafter, instead of using the general but slow linear programming, we propose an efficient min-cost flow based approach to solve it. Our approach guarantees to obtain the minimum of total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. We also show that the approach can be easily extended to handle constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient in that it finishes in less than 0.4 seconds for all MCNC benchmarks of block placement. It is also very effective. Experimental results show we can improve 4.2% of wire length even on very compact floorplans. Thus it provides an ideal way of post-floorplanning (refine floorplanning).

Original languageEnglish
Title of host publicationASP-DAC '05
Subtitle of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Pages412-417
Number of pages6
ISBN (Electronic)9780780387379
ISBN (Print)0780387368, 9780780387362
DOIs
Publication statusPublished - Jan 2005
Event10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Hotel Equatorial, Shanghai, China
Duration: 18 Jan 200521 Jan 2005
https://www.aspdac.com/aspdac2005/ (Conference website)

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Country/TerritoryChina
CityShanghai
Period18/01/0521/01/05
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Optimal redistribution of white space for wire length minimization'. Together they form a unique fingerprint.

Cite this