Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Area minimization for hierarchical floorplans

  • Published:
Algorithmica Aims and scope Submit manuscript

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 costO(k 2 logk) and space cost0(k 2) if each block in a wheel has at mostk 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 are0((nM)2log(nM) and0(n 2 M), respectively, wheren is the number of basic blocks andM 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. -H. Chen and I. G. Tollis, Area optimization of spiral floorplans,J. Circuits Systems Comput.,3 (2) (1993), 833–857.

    Google Scholar 

  2. K. Chong and S. Sahni, Optimal realizations of floorplans,IEEE Trans. Computer-Aided Design,12 (1993), 793–801.

    Article  Google Scholar 

  3. W. -M. Dai and E. S. Kuh, Simultaneous floor planning and global routing for hierarchical building block layout,IEEE Trans. Computer-Aided Design,6 (1987), 828–837.

    Article  Google Scholar 

  4. H. Edelsbrunner and E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms,ACM Trans. Graphics,9 (1990), 66–104.

    Article  Google Scholar 

  5. M. L. Fredman, How good is the information theory bound in sorting?,Theoret. Comput. Sci.,1 (1976), 355–361.

    Article  Google Scholar 

  6. M. R. Garey and D. S. Johnson,Computers and Intractability, a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

    Google Scholar 

  7. O. H. Ibarra and C. E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems,J. Assoc. Comput. Mach.,22 (1975), 463–468.

    Google Scholar 

  8. T. Lengauer,Combinatorial Algorithms for Integrated Circuit Layout, Wiley, New York, 1990.

    Google Scholar 

  9. T. Lengauer and R. Muller, The complexity of floorplanning based on binary circuit partitions, Technical Report 46, Department of Mathematics and Computer Science, University of Paderborn, Paderborn, 1988.

    Google Scholar 

  10. T. Lengauer and R. Muller, Robust and accurate hierarchical floorplanning with integrated global wiring,IEEE Trans. Computer-Aided Design,12 (1993), 802–809.

    Article  Google Scholar 

  11. R. H. J. M. Otten, Automatic floorplan design,Proc. 19th ACM/IEEE Design Automation Conf., 1982, pp. 261–267.

  12. R. H. J. M. Otten, Graphs in floorplan design,Internat. J. Circuit Theory Appl.,16 (1988), 391–410.

    Google Scholar 

  13. P. Pan and C. L. Liu, Area minimization for floorplans,IEEE Trans. on Computer-Aided Design,14(1) (1995), 123–132.

    Article  Google Scholar 

  14. L. Stockmeyer, Optimal orientations of cells in slicing floorplan designs,Inform. and Control,59 (1983), 91–101.

    Article  Google Scholar 

  15. K. J. Supowit and E. A. Slutz, Placement algorithms for custom VLSI,Comput. Aided Design,16 (1984), 45–50.

    Google Scholar 

  16. T. -C. Wang and D. F. Wong, Optimal floorplan area optimization,IEEE Trans. Computer-Aided Design,11 (1992), 992–1002.

    Google Scholar 

  17. T. -C. Wang and D. F. Wong, A note on the complexity of Stockmeyer's floorplan optimization technique, inAlgorithmic Aspects of VLSI Layout (edited by M. Sarrafzadeh and D. T. Lee), World Scientific, Singapore, 1992, pp. 309–320.

    Google Scholar 

  18. S. Wimer, I. Koren, and I. Cederbaum, Optimal aspect ratios of building blocks in VLSI,IEEE Trans. Computer-Aided Design,8 (1989), 139–145.

    Article  Google Scholar 

  19. D. F. Wong and P. S. Sakhamuri, Efficient floorplan area optimization,Proc. 26th ACM/IEEE Design Automation Conf., 1989, pp. 586–589.

  20. K. H. Yeap and M. Sarrafzadeh, An integrated algorithm for optimal floorplan sizing and enumeration,European Design Automation Conf., 1993, pp. 29–33.

  21. G. Zimmermann, A new area and shape function estimation technique for VLSI layouts,Proc. 25th ACM/IEEE Design Automation Conf., 1988, pp. 60–65.

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, Clarkson University, 13699, Potsdam, NY, USA

    Peichen Pan

  2. Department of Computer Science, University of North Texas, 76203, Denton, TX, USA

    Weiping Shi

  3. Department of Computer Science, University of Illinois at Urbana-Champaign, 61801, Urbana, IL, USA

    C. L. Liu

Authors
  1. Peichen Pan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Weiping Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. L. Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by C. K. Wong.

The research of Peichen Pan and C. L. Liu was partially supported by the NSF under Grant MIP-9222408. The research of Weiping Shi was partially supported by the NSF under Grant MIP-9309120.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pan, P., Shi, W. & Liu, C.L. Area minimization for hierarchical floorplans. Algorithmica 15, 550–571 (1996). https://doi.org/10.1007/BF01940881

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01940881

Key words

Search

Navigation