Graph-based techniques to speed up floorplan area optimization

Ting Chi Wang, D. F. Wong

Research output: Contribution to journalArticlepeer-review

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 [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 (US)
Pages (from-to)179-199
Number of pages21
JournalIntegration, the VLSI Journal
Volume15
Issue number2
DOIs
StatePublished - Oct 1993
Externally publishedYes

Keywords

  • Floorplan design
  • constrained shortest path
  • floorplan area optimization

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering

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

Cite this