Arbitrarily shaped rectilinear module placement using the transitive closure graph representation

Jai-Ming Lin, Hsin Lung Chen, Yao Wen Chang

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

Original languageEnglish
Pages (from-to)886-901
Number of pages16
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume10
Issue number6
DOIs
Publication statusPublished - 2002 Dec 1

Fingerprint

Processing

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this

@article{c2533f6cec8e467a9bdf0d700da9473f,
title = "Arbitrarily shaped rectilinear module placement using the transitive closure graph representation",
abstract = "In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.",
author = "Jai-Ming Lin and Chen, {Hsin Lung} and Chang, {Yao Wen}",
year = "2002",
month = "12",
day = "1",
doi = "10.1109/TVLSI.2002.808431",
language = "English",
volume = "10",
pages = "886--901",
journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",
issn = "1063-8210",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "6",

}

Arbitrarily shaped rectilinear module placement using the transitive closure graph representation. / Lin, Jai-Ming; Chen, Hsin Lung; Chang, Yao Wen.

In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 10, No. 6, 01.12.2002, p. 886-901.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Arbitrarily shaped rectilinear module placement using the transitive closure graph representation

AU - Lin, Jai-Ming

AU - Chen, Hsin Lung

AU - Chang, Yao Wen

PY - 2002/12/1

Y1 - 2002/12/1

N2 - In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

AB - In this paper, we deal with arbitrarily shaped rectilinear module placement using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG as well as its induced operations, which makes TCG an ideal representation for floorplanning/placement with arbitrary rectilinear modules. We first partition a rectilinear module into a set of submodules and then derive necessary and sufficient conditions of feasible TCG for the submodules. Unlike most previous works that process each submodule individually and thus need to perform post processing to fix deformed rectilinear modules, our algorithm treats a set of submodules as a whole and thus not only can guarantee the feasibility of each perturbed solution but also can eliminate the need for the postprocessing on deformed modules, implying better solution quality and running time. Experimental results show that our TCG-based algorithm is capable of handling very complex instances; further, it is very efficient and results in better area utilization than previous work.

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

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

U2 - 10.1109/TVLSI.2002.808431

DO - 10.1109/TVLSI.2002.808431

M3 - Article

VL - 10

SP - 886

EP - 901

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

SN - 1063-8210

IS - 6

ER -