IEICE TRANSACTIONS on Information
Minimizing the Number of Empty Rooms on Floorplan by Dissection Line Merge
Summary :
This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n-
- Publication
- IEICE TRANSACTIONS on Information Vol.E88-D No.7 pp.1389-1396
- Publication Date
- 2005/07/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietisy/e88-d.7.1389
- Type of Manuscript
- Special Section PAPER (Special Section on Recent Advances in Circuits and Systems--Part 1)
- Category
- Programmable Logic, VLSI, CAD and Layout
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chikaaki KODAMA, Kunihiro FUJIYOSHI, "Minimizing the Number of Empty Rooms on Floorplan by Dissection Line Merge" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 7, pp. 1389-1396, July 2005, doi: 10.1093/ietisy/e88-d.7.1389.
Abstract: This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n-
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.7.1389/_p
Copy
@ARTICLE{e88-d_7_1389,
author={Chikaaki KODAMA, Kunihiro FUJIYOSHI, },
journal={IEICE TRANSACTIONS on Information},
title={Minimizing the Number of Empty Rooms on Floorplan by Dissection Line Merge},
year={2005},
volume={E88-D},
number={7},
pages={1389-1396},
abstract={This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n-
keywords={},
doi={10.1093/ietisy/e88-d.7.1389},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Minimizing the Number of Empty Rooms on Floorplan by Dissection Line Merge
T2 - IEICE TRANSACTIONS on Information
SP - 1389
EP - 1396
AU - Chikaaki KODAMA
AU - Kunihiro FUJIYOSHI
PY - 2005
DO - 10.1093/ietisy/e88-d.7.1389
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2005
AB - This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n-
ER -
English
