Graph-based techniques to speed up floorplan area optimization

Ting-Chi Wang*, D. F. Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


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 [1-7]. For large floorplans, this approach may fail due to insufficient memory space available to store the implementations of sub-floorplans generated during the computation. An effective method to reduce memory usage is as follows: During the computation, whenever the set of non-redundant implementations of a sub-floorplan exceeds a certain predefined size, we only retain a subset of the implementations that can best approximate the original set. In this paper, we present two algorithms to optimally select implementations for rectangular and L-shaped sub-floorplans. Our algorithms can be applied to existing floorplan area optimization algorithms such as [3-7] to improve their performances. The common key idea of our two algorithms is to reduce the problem of optimally selecting a subset of implementations to a constrained shortest path problem, which we can solve optimally in polynomial time. We have incorporated the two algorithms into [7] and obtained very encouraging experimental results.

Original languageEnglish
Pages (from-to)179-199
Number of pages21
JournalIntegration, the VLSI Journal
Issue number2
Publication statusPublished - Oct 1993

Scopus Subject Areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

User-Defined Keywords

  • constrained shortest path
  • floorplan area optimization
  • Floorplan design


Dive into the research topics of 'Graph-based techniques to speed up floorplan area optimization'. Together they form a unique fingerprint.

Cite this