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

Jai-Ming Lin, Yao Wen Chang

Research output: Contribution to journalArticle

40 Citations (Scopus)

Abstract

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
Volume23
Issue number6
DOIs
Publication statusPublished - 2004 Jun 1

Fingerprint

Costs
Experiments

All Science Journal Classification (ASJC) codes

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

Cite this

@article{0963ac5eafe94002b6834c9f867f7290,
title = "TCG-S: Orthogonal coupling of P*-admissible representations for general floorplans",
abstract = "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.",
author = "Jai-Ming Lin and Chang, {Yao Wen}",
year = "2004",
month = "6",
day = "1",
doi = "10.1109/TCAD.2004.828114",
language = "English",
volume = "23",
pages = "968--980",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

TCG-S : Orthogonal coupling of P*-admissible representations for general floorplans. / Lin, Jai-Ming; Chang, Yao Wen.

In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 23, No. 6, 01.06.2004, p. 968-980.

Research output: Contribution to journalArticle

TY - JOUR

T1 - TCG-S

T2 - Orthogonal coupling of P*-admissible representations for general floorplans

AU - Lin, Jai-Ming

AU - Chang, Yao Wen

PY - 2004/6/1

Y1 - 2004/6/1

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/TCAD.2004.828114

DO - 10.1109/TCAD.2004.828114

M3 - Article

AN - SCOPUS:2942546060

VL - 23

SP - 968

EP - 980

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

IS - 6

ER -