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 language | English |
---|---|
Title of host publication | ASP-DAC '05 |
Subtitle of host publication | Proceedings of the 2005 Asia and South Pacific Design Automation Conference |
Place of Publication | United States |
Publisher | Association for Computing Machinery (ACM) |
Pages | 412-417 |
Number of pages | 6 |
ISBN (Electronic) | 9780780387379 |
ISBN (Print) | 0780387368, 9780780387362 |
DOIs | |
Publication status | Published - Jan 2005 |
Event | 10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Hotel Equatorial, Shanghai, China Duration: 18 Jan 2005 → 21 Jan 2005 https://www.aspdac.com/aspdac2005/ (Conference website) |
Publication series
Name | Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC |
---|
Conference
Conference | 10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 |
---|---|
Country/Territory | China |
City | Shanghai |
Period | 18/01/05 → 21/01/05 |
Internet address |
|
Scopus Subject Areas
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering