Graph theoretic technique to speed up floorplan area optimization

Ting Chi Wang, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Pages62-68
Number of pages7
ISBN (Print)0818628227
StatePublished - Dec 1 1992
Externally publishedYes
EventProceedings of the 29th ACM/IEEE Design Automation Conference - Anaheim, CA, USA
Duration: Jun 8 1992Jun 12 1992

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123

Other

OtherProceedings of the 29th ACM/IEEE Design Automation Conference
CityAnaheim, CA, USA
Period6/8/926/12/92

Fingerprint

Data storage equipment
Polynomials

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Wang, T. C., & Wong, D. F. (1992). Graph theoretic technique to speed up floorplan area optimization. In Proceedings - Design Automation Conference (pp. 62-68). (Proceedings - Design Automation Conference). Publ by IEEE.

Graph theoretic technique to speed up floorplan area optimization. / Wang, Ting Chi; Wong, D. F.

Proceedings - Design Automation Conference. Publ by IEEE, 1992. p. 62-68 (Proceedings - Design Automation Conference).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Wang, TC & Wong, DF 1992, Graph theoretic technique to speed up floorplan area optimization. in Proceedings - Design Automation Conference. Proceedings - Design Automation Conference, Publ by IEEE, pp. 62-68, Proceedings of the 29th ACM/IEEE Design Automation Conference, Anaheim, CA, USA, 6/8/92.
Wang TC, Wong DF. Graph theoretic technique to speed up floorplan area optimization. In Proceedings - Design Automation Conference. Publ by IEEE. 1992. p. 62-68. (Proceedings - Design Automation Conference).
Wang, Ting Chi ; Wong, D. F. / Graph theoretic technique to speed up floorplan area optimization. Proceedings - Design Automation Conference. Publ by IEEE, 1992. pp. 62-68 (Proceedings - Design Automation Conference).
@inproceedings{e1e4dac6665540a0954a5e5f00326561,
title = "Graph theoretic technique to speed up floorplan area optimization",
abstract = "A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.",
author = "Wang, {Ting Chi} and Wong, {D. F.}",
year = "1992",
month = "12",
day = "1",
language = "English (US)",
isbn = "0818628227",
series = "Proceedings - Design Automation Conference",
publisher = "Publ by IEEE",
pages = "62--68",
booktitle = "Proceedings - Design Automation Conference",

}

TY - GEN

T1 - Graph theoretic technique to speed up floorplan area optimization

AU - Wang, Ting Chi

AU - Wong, D. F.

PY - 1992/12/1

Y1 - 1992/12/1

N2 - A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.

AB - A well known approach for the floorplan area optimization problem is to first determine a list of all non-redundant implementations of the entire floorplan and then select an optimal floorplan from the list [4,6,9,10,12]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. To effectively reduce both memory usage and running time, we present in this paper two algorithms to optimally reduce the number of implementations for rectangular and L-shaped sub-floorplans. The common key idea of our two algorithms is to reduce the problem to a constrained shortest path problem, which we can solve optimally in polynomial time. Our algorithms are designed specifically for [10] but they can also be applied to other algorithms such as [4,6,12] as well. The experimental results are very encouraging.

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

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

M3 - Conference contribution

AN - SCOPUS:0026994627

SN - 0818628227

T3 - Proceedings - Design Automation Conference

SP - 62

EP - 68

BT - Proceedings - Design Automation Conference

PB - Publ by IEEE

ER -