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 contribution

Abstract

Existing floorplainning algorithms compact blocks to the left ancl 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 he 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 (US)
Title of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Pages412-417
Number of pages6
StatePublished - Dec 1 2005
Event2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Shanghai, China
Duration: Jan 18 2005Jan 21 2005

Publication series

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

Other

Other2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005
CountryChina
CityShanghai
Period1/18/051/21/05

ASJC 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

    Tang, X., Tian, R., & Wong, M. D. F. (2005). Optimal redistribution of white space for wire length minimization. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005 (pp. 412-417). [1466198] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 1).