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 language | English (US) |
---|---|
Pages (from-to) | 179-199 |
Number of pages | 21 |
Journal | Integration, the VLSI Journal |
Volume | 15 |
Issue number | 2 |
DOIs | |
State | Published - Oct 1993 |
Externally published | Yes |
Keywords
- Floorplan design
- constrained shortest path
- floorplan area optimization
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Electrical and Electronic Engineering