Floorplan sizing by linear programming approximation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Floorplan sizing by linear programming approximation

Full text

Pdf (66 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 37th Annual Design Automation Conference table of contents

Los Angeles, California, United States

Pages: 468 - 471

Year of Publication: 2000

ISBN:1-58113-187-9

Authors

Pinhong Chen	EECS Dept., Univ. of California at Berkeley, Berkeley, CA
Ernest S. Kuh	EECS Dept., Univ. of California at Berkeley, Berkeley, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 23, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/337292.337547 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
	2	T. S. Mob, T. S. Chang, and S.L.Hakimi. "Globally optimal floorplanning for a layout problem". IEEE Trans. on Circuit and Systems - I: Fundamental Theory and Applications, Vol.43:pp.713-720, Sep. 1996.
	3	Temo Chen , Michael K. H. Fan, On convex formulation of the floorplan area minimization problem, Proceedings of the 1998 international symposium on Physical design, p.124-128, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274553]
	4	K. Wang and W.K. Chen. "Floorplan Area Optimization using Network Analogous Approach". In Proc. oflEEE International Symposium on Circuits and Systems, pages 167-170, 1995.
	5	Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
	6	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	7	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982

CITED BY 5

	Xiaoping Tang , D. F. Wong, Floorplanning with alignment and performance constraints, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Krishnan Srinivasan , Karam S. Chatha , Goran Konjevod, Linear-programming-based techniques for synthesis of network-on-chip architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.4, p.407-420, April 2006
	Krishnan Srinivasan , Karam S. Chatha, A low complexity heuristic for design of custom network-on-chip architectures, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Ou He , Sheqin Dong , Jinian Bian , Satoshi Goto , Chung-Kuan Cheng, A novel fixed-outline floorplanner with zero deadspace for hierarchical design, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Xin Li , Yuchun Ma , Xianlong Hong, A novel thermal optimization flow using incremental floorplanning for 3D ICs, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan