On handling arbitrary rectilinear shape constraint

Xiaoping Tang, Martin D F Wong

Research output: Contribution to conferencePaperpeer-review


Non-rectangular (rectilinear) shape occurs very often in deep submicron floorplanning. Most previous algorithms are designed to handle only convex rectilinear blocks. However, handling concave rectilinear shape is necessary since a simple "U" shape is concave. A few works could address concave rectilinear block explicitly. In [2], a necessary and sufficient condition of feasible sequence pair is proposed for arbitrary rectilinear shape in terms of constraint graph. However, no constraint is imposed on sequence pair representation itself. The search for feasible sequence pair mainly depends on the simulated annealing, which implies unnecessary inefficiency. In many cases, it takes very long time or even is unable to find the feasible placement. Furthermore, it takes O(n3) runtime to evaluate each sequence pair, which leaves much space for improvement. In this paper, we propose a new method to handle arbitrary rectilinear shape constraint based on sequence pair representation. We explore the topological property of feasible sequence pair, and use it to eliminate lots of infeasible sequence pairs, which implies speeding up the convergence of simulated annealing process. The evaluation of a sequence pair is based on longest common subsequence computation, and achieves significantly faster runtime (O(mn log log n) time where m is the number of rectilinear-shape constraints, n is the number of rectangular blocks/subblocks). The algorithm can handle fixed-frame floorplanning and min-area floorplanning as well.

Original languageEnglish (US)
Number of pages4
StatePublished - 2004
EventProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004 - Yokohama, Japan
Duration: Jan 27 2004Jan 30 2004


OtherProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004

ASJC Scopus subject areas

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


Dive into the research topics of 'On handling arbitrary rectilinear shape constraint'. Together they form a unique fingerprint.

Cite this