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 language | English |
|---|---|
| Article number | 998251 |
| Pages (from-to) | 69-75 |
| Number of pages | 7 |
| Journal | Proceedings -Design, Automation and Test in Europe, DATE |
| DOIs | |
| Publication status | Published - 2002 Dec 1 |
| Event | 2002 Design, Automation and Test in Europe Conference and Exhibition, DATE 2002 - Paris, France Duration: 2002 Mar 4 → 2002 Mar 8 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Engineering(all)
Cite this
}
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 journal › 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 -