Area minimization for hierarchical floorplans
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
In this paper we study the area-minimization problem for hierarchical floorplans. We settle an open problem on the complexity of the area-minimization problem for hierarchical floorplans by showing it to be NP-complete (even for balanced hierarchical floorplans). We then present a new algorithm for determining the nonredundant realizations of a wheel. The algorithm has time cost O(k2 log k) and space cost O(k2) if each block in a wheel has at most k realizations. Based on the new algorithm for a wheel, we design a new pseudopolynomial area-minimization algorithm for hierarchical floorplans of order-5. The time and space costs of the algorithm are O((nM)2 log(nM)) and O(n2M), respectively, where n is the number of basic blocks and M is an upper bound on the dimensions of the realizations of the basic blocks. The area-minimization algorithm was implemented. Experimental results show that it is very fast.
