Floorplanning with alignment and performance constraints

Xiaoping Tang, D. F. Wong

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

46 Citations (Scopus)


In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floor-planning, which is different from traditional well-researched minarea floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

Original languageEnglish
Title of host publication39th ACM/IEEE Design Automation Conference - Proceedings 2002
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)9781581134612, 1581134614
Publication statusPublished - Jun 2002
Event39th ACM/IEEE Design Automation Conference, DAC 2002 - New Orleans, United States
Duration: 10 Jun 200214 Jun 2002
https://www.dac.com/About/Conference-Archive/39th-DAC-2002 (Conference website)
https://www.dac.com/portals/0/documents/archive/2005-01/39thfinal.pdf (Conference program)
https://dl.acm.org/doi/proceedings/10.1145/513918 (Conference proceedings)
https://ieeexplore.ieee.org/xpl/conhome/7910/proceeding (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)0738-100X


Conference39th ACM/IEEE Design Automation Conference, DAC 2002
Country/TerritoryUnited States
CityNew Orleans
Internet address

Scopus Subject Areas

  • Hardware and Architecture
  • Control and Systems Engineering

User-Defined Keywords

  • Floorplanning
  • Longest common subsequence
  • Sequence pair


Dive into the research topics of 'Floorplanning with alignment and performance constraints'. Together they form a unique fingerprint.

Cite this