Arbitrary convex and concave rectilinear module packing using TCG

Jai Ming Lin, Hsin Lung Chen, Yao Wen Chang

研究成果: Conference article

5 引文 (Scopus)

摘要

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.

原文English
文章編號998251
頁(從 - 到)69-75
頁數7
期刊Proceedings -Design, Automation and Test in Europe, DATE
DOIs
出版狀態Published - 2002 十二月 1
事件2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Paris, France
持續時間: 2002 三月 42002 三月 8

指紋

Processing
Planning

All Science Journal Classification (ASJC) codes

  • Engineering(all)

引用此文

@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 = "Lin, {Jai Ming} 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.

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

研究成果: Conference 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 -