TCG: A transitive closure graph-based representation for non-slicing floorplans

J. M. Lin, Y. W. Chang

Research output: Contribution to journalConference article

182 Citations (Scopus)

Abstract

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

Original languageEnglish
Pages (from-to)764-769
Number of pages6
JournalProceedings - Design Automation Conference
Publication statusPublished - 2001 Jan 1
Event38th Design Automation Conference - Las Vegas, NV, United States
Duration: 2001 Jun 182001 Jun 22

Fingerprint

Costs

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering

Cite this

@article{2c3a051efe484da794696209753c5502,
title = "TCG: A transitive closure graph-based representation for non-slicing floorplans",
abstract = "In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.",
author = "Lin, {J. M.} and Chang, {Y. W.}",
year = "2001",
month = "1",
day = "1",
language = "English",
pages = "764--769",
journal = "Proceedings - Design Automation Conference",
issn = "0738-100X",

}

TCG : A transitive closure graph-based representation for non-slicing floorplans. / Lin, J. M.; Chang, Y. W.

In: Proceedings - Design Automation Conference, 01.01.2001, p. 764-769.

Research output: Contribution to journalConference article

TY - JOUR

T1 - TCG

T2 - A transitive closure graph-based representation for non-slicing floorplans

AU - Lin, J. M.

AU - Chang, Y. W.

PY - 2001/1/1

Y1 - 2001/1/1

N2 - In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

AB - In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

UR - http://www.scopus.com/inward/record.url?scp=0034855935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034855935&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0034855935

SP - 764

EP - 769

JO - Proceedings - Design Automation Conference

JF - Proceedings - Design Automation Conference

SN - 0738-100X

ER -