Arbitrary convex and concave rectilinear module packing using TCG

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

Research output: Contribution to journalConference article

5 Citations (Scopus)

Abstract

Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/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 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 of the post processing 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
Article number998251
Pages (from-to)69-75
Number of pages7
JournalProceedings -Design, Automation and Test in Europe, DATE
DOIs
Publication statusPublished - 2002 Dec 1
Event2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Paris, France
Duration: 2002 Mar 42002 Mar 8

Fingerprint

Processing
Planning

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this

@article{32fd79c3fb5b4237888fd32cb6598bd7,
title = "Arbitrary convex and concave rectilinear module packing using TCG",
abstract = "Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/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 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 of the post processing 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/DATE.2002.998251",
language = "English",
pages = "69--75",
journal = "Proceedings -Design, Automation and Test in Europe, DATE",
issn = "1530-1591",

}

Arbitrary convex and concave rectilinear module packing using TCG. / Lin, Jai-Ming; Chen, Hsin Lung; Chang, Yao Wen.

In: Proceedings -Design, Automation and Test in Europe, DATE, 01.12.2002, p. 69-75.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Arbitrary convex and concave rectilinear module packing using TCG

AU - Lin, Jai-Ming

AU - Chen, Hsin Lung

AU - Chang, Yao Wen

PY - 2002/12/1

Y1 - 2002/12/1

N2 - Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/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 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 of the post processing 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 - Deals with arbitrary convex and concave rectilinear module packing using the transitive closure graph (TCG) representation. The geometric meanings of modules are transparent to TCG and its induced operations, which makes TCG an ideal representation for floor-planning/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 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 of the post processing 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=0013359369&partnerID=8YFLogxK

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

U2 - 10.1109/DATE.2002.998251

DO - 10.1109/DATE.2002.998251

M3 - Conference article

AN - SCOPUS:0013359369

SP - 69

EP - 75

JO - Proceedings -Design, Automation and Test in Europe, DATE

JF - Proceedings -Design, Automation and Test in Europe, DATE

SN - 1530-1591

M1 - 998251

ER -