Floorplan sizing by linear programming approximation

In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can ha...

Full description

Saved in:
Bibliographic Details
Main Authors: Chen, Pinhong, Kuh, Ernest S.
Format: Conference Proceeding
Language:English
Subjects:
Applied computing > Physical sciences and engineering > Engineering
Approximation algorithms
Constraint optimization
Cost function
Functional programming
Hardware > Electronic design automation > Physical design (EDA)
Hardware > Emerging technologies
Hardware > Robustness
Hardware > Very large scale integration design
Linear approximation
Linear programming
Mathematics of computing > Mathematical analysis > Functional analysis > Approximation
Mathematics of computing > Mathematical analysis > Mathematical optimization > Continuous optimization > Linear programming
Permission
Theory of computation > Design and analysis of algorithms > Approximation algorithms analysis
Theory of computation > Design and analysis of algorithms > Mathematical optimization > Continuous optimization > Linear programming
Timing
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we present an approximation algorithm by linear programming (LP) for floorplan sizing problem. Given any topological constraints between blocks, we can formulate it as an LP problem with a cost function for the minimum bounding box area. Unlike slicing structures, this approach can handle any topological constraints as well as soft/hard/preplaced blocks, and timing constraints. Empirically, our method needs few iterations to find the optimum solution and shows one order of improvement over previous methods both in run time and capability to handle a larger problem size even on a very limited computing resource PC.
ISSN:0738-100X
DOI:10.1145/337292.337547