Area minimization for hierarchical floorplans Academic Article uri icon

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.

published proceedings

  • Algorithmica

author list (cited authors)

  • Pan, P., Shi, W., & Liu, C. L.

citation count

  • 12

complete list of authors

  • Pan, Peichen||Shi, Weiping||Liu, CL

publication date

  • January 1996