TCG-S: Orthogonal coupling of P*-admissible representations for general floorplans

Jai Ming Lin, Yao Wen Chang

Research output: Contribution to journalArticlepeer-review

40 Citations (Scopus)


In this paper, we extend the concept of the P-admissible floorplan representation to that of the P*-admissible one. A P*-admissible representation can model the most general floorplans. Each of the currently existing P*-admissible representations, sequence pair (SP), bounded-slicing grid, and transitive closure graph (TCG), has its strengths as well as weaknesses. We show the equivalence of the two most promising P*-admissible representations, TCG and SP, and integrate TCG with a packing sequence (part of SP) into a representation, called TCG-S. TCG-S combines the advantages of SP and TCG and at the same time eliminates their disadvantages. With the property of SP, a fast packing scheme is possible. Inherited nice properties from TCG, the geometric relations among modules are transparent to TCG-S (implying faster convergence to a desired solution), placement with position constraints becomes much easier, and incremental update for cost evaluation can be realized. These nice properties make TCG-S a superior representation which exhibits an elegant solution structure to facilitate the search for a desired floorplan/placement. Extensive experiments show that TCG-S results in the best area utilization, wirelength optimization, convergence speed, and stability among existing works and is very flexible in handling placement with special constraints.

Original languageEnglish
Pages (from-to)968-980
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
Publication statusPublished - 2004 Jun 1

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'TCG-S: Orthogonal coupling of P*-admissible representations for general floorplans'. Together they form a unique fingerprint.

Cite this