An O-tree representation of non-slicing floorplan and its applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An O-tree representation of non-slicing floorplan and its applications

Full text

Pdf (732 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 36th annual ACM/IEEE Design Automation Conference table of contents

New Orleans, Louisiana, United States

Pages: 268 - 273

Year of Publication: 1999

ISBN:1-58133-109-7

Authors

Pei-Ning Guo	Mentor Graphics Corp., 1001 Ridder Park Drive, San Jose, CA
Chung-Kuan Cheng	Mentor Graphics Corp., 1001 Ridder Park Drive, San Jose, CA
Takeshi Yoshimura	NEC Corp., 4-1-1 Miyazaki, Miyanae-Ku, Kawasaki 216, Japan

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 62, Citation Count: 79

Additional Information:

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/309847.309928 What is a DOI?

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	Kenneth Keeler , Jeffery Westbrook, Short encodings of planar graphs and maps, Discrete Applied Mathematics, v.58 n.3, p.239-252, April 7, 1995 [doi>10.1016/0166-218X(93)E0150-W]
	2	Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
	3	Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
	4	Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
	5	Hidetoshi Onodera , Yo Taniguchi , Keikichi Tamaru, Branch-and-bound placement for building block layout, Proceedings of the 28th conference on ACM/IEEE design automation, p.433-439, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127708]
	6	Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
	7	P. Pan and C.L. Liu, Area Minimization for Floorplans, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp. 123-132, January 1995
	8	B. T. Preas , W. M. vanCleemput, Placement algorithms for arbitrarily shaped blocks, Proceedings of the 16th Conference on Design automation, p.474-480, June 25-27, 1979, San Diego, CA, United States
	9	T. Takahashi, An Algorithm for Finding a Maximum-Weight Decreasing Sequence in a Permutation, Motivated by Rectangle Packing Problem, IEICE, vol. VLD96, pp. 31-35, 1996
	10	Ting-chi Wang , D. F. Wong, An optimal algorithm for floorplan area optimization, Proceedings of the 27th ACM/IEEE conference on Design automation, p.180-186, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123253]
	11	D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
	12	Jin Xu , Pei-Ning Guo , Chung-Kuan Cheng, Cluster refinement for block placement, Proceedings of the 34th annual conference on Design automation, p.762-765, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266366]

CITED BY 79

	Hsun-Cheng Lee , Yao-Wen Chang , Jer-Ming Hsu , Hannah H. Yang, Multilevel floorplanning/placement for large-scale modules using B*-trees, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Yingxin Pang , Chung-Kuan Cheng , Koen Lampaert , Weize Xie, Rectilinear block packing using O-tree representation, Proceedings of the 2001 international symposium on Physical design, p.156-161, April 01-04, 2001, Sonoma, California, United States
	Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan
	Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States
	Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States
	Sheqin Dong , Shuo Zhou , Xianlong Hong , Chungkuan Cheng , Jun Gu , Yici Cai, An optimum placement search algorithm based on extended corner block list, Journal of Computer Science and Technology, v.17 n.6, p.699-707, November 2002
	Hung-Ming Chen , D. F. Wong , Wai-Kei Mak , Hannah H. Yang, Faster and more accurate wiring evaluation in interconnect-centric floorplanning, Proceedings of the 11th Great Lakes symposium on VLSI, p.62-67, March 2001, West Lafayette, Indiana, United States
	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
	Shuo Zhou , Sheqin Dong , Chung-Kuan Cheng , Jun Gu, ECBL: an extended corner block list with solution space including optimum placement, Proceedings of the 2001 international symposium on Physical design, p.150-155, April 01-04, 2001, Sonoma, California, United States
	Jianbang Lai , Ming-Shiun Lin , Ting-Chi Wang , Li-C. Wang, Module placement with boundary constraints using the sequence-pair representation, Proceedings of the 2001 conference on Asia South Pacific design automation, p.515-520, January 2001, Yokohama, Japan
	Faran Rafiq , Malgorzata Chrzanowska-Jeske , Hannah Honghua Yang , Naveed Sherwani, Integrated floorplanning with buffer/channel insertion for bus-based microprocessor designs, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	M. Lai , D. Wong, Slicing tree is a complete floorplan representation, Proceedings of the conference on Design, automation and test in Europe, p.228-232, March 2001, Munich, Germany
	Sheqin Dong , Xianlong Hong , Youliang Wu , Yizhou Lin , Jun Gu, VLSI block placement using less flexibility first principles, Proceedings of the 2001 conference on Asia South Pacific design automation, p.601-604, January 2001, Yokohama, Japan
	Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Ronald Graham, Revisiting floorplan representations, Proceedings of the 2001 international symposium on Physical design, p.138-143, April 01-04, 2001, Sonoma, California, United States
	Jun Yuan , Sheqin Dong , Xianlong Hong , Yuliang Wu, LFF algorithm for heterogeneous FPGA floorplanning, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Yingxin Pang , Florin Balasa , Koen Lampaert , Chung-Kuan Cheng, Block placement with symmetry constraints based on the O-tree non-slicing representation, Proceedings of the 37th conference on Design automation, p.464-467, June 05-09, 2000, Los Angeles, California, United States
	En-Cheng Liu , Ming-Shiun Lin , Jianbang Lai , Ting-Chi Wang, Slicing floorplan design with boundary-constrained modules, Proceedings of the 2001 international symposium on Physical design, p.124-129, April 01-04, 2001, Sonoma, California, United States
	Yuchun Ma , Sheqin Dong , Xianiong Hong , Yici Cai , Chung-Kuan Cheng , Jun Gu, VLSI floorplanning with boundary constraints based on corner block list, Proceedings of the 2001 conference on Asia South Pacific design automation, p.509-514, January 2001, Yokohama, Japan
	Yingxin Pang , Chung-Kuan Cheng , Takeshi Yoshimura, An enhanced perturbing algorithm for floorplan design using the O-tree representation, Proceedings of the 2000 international symposium on Physical design, p.168-173, May 2000, San Diego, California, United States
	Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States
	Shigetoshi Nakatake , Yukiko Kubo , Yoji Kajitani, Consistent floorplanning with super hierarchical constraints, Proceedings of the 2001 international symposium on Physical design, p.144-149, April 01-04, 2001, Sonoma, California, United States
	Florin Balasa, Modeling non-slicing floorplans with binary trees, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Oluf Faroe , David Pisinger , Martin Zachariasen, Local search for final placement in VLSI design, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Guang-Ming Wu , Yun-Chih Chang , Yao-Wen Chang, Rectilinear block placement using B*-trees, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.188-202, April 2003
	Florin Balasa , Sarat C. Maruvada , Karthik Krishnamoorthy, Efficient solution space exploration based on segment trees in analog placement with symmetry constraints, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.497-502, November 10-14, 2002, San Jose, California
	Evangeline F. Y. Young , Chris C. N. Chu , Cien Shen, Twin binary sequences: a non-redundant representation for general non-slicing floorplan, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Jai-Ming Lin , Yao-Wen Chang , Shih-Ping Lin, Corner sequence: a P-admissible floorplan representation with a worst case linear-time packing scheme, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.4, p.679-686, August 2003
	Xiaoping Tang , Martin D. F. Wong, On handling arbitrary rectilinear shape constraint, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.38-41, January 27-30, 2004, Yokohama, Japan
	Taraneh Taghavi , Soheil Ghiasi , Abhishek Ranjan , Salil Raje , Majid Sarrafzadeh, Innovate or perish: FPGA physical design, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Yuchun Ma , Xianlong Hong , Sheqin Dong , Yici Cai , Chung-Kuan Cheng , Jun Gu, Floorplanning with abutment constraints and L-shpaed/T-shaped blocks baed on corner block list, Proceedings of the 38th conference on Design automation, p.770-775, June 2001, Las Vegas, Nevada, United States
	T. Serdar , C. Sechen, Automatic datapath tile placement and routing, Proceedings of the conference on Design, automation and test in Europe, p.552-559, March 2001, Munich, Germany
	Bo Yao , Hongyu Chen , Chung-Kuan Cheng , Ronald Graham, Floorplan representations: Complexity and connections, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.1, p.55-80, January 2003
	Mario R. Casu , Luca Macchiarulo, Floorplanning for throughput, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Yuchun Ma , Xianlong Hong , Sheqin Dong , Yici Cai , Chung-Kuan Cheng , Jun Gu, Stairway compaction using corner block list and its applications with rectilinear blocks, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.2, p.199-211, April 2004
	Xuliang Zhang , Yoji Kajitani, Space-planning: placement of modules with controlled empty area by single-sequence, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.25-30, January 27-30, 2004, Yokohama, Japan
	Jason Cong , Gabriele Nataneli , Michail Romesis , Joseph R. Shinnerl, An area-optimality study of floorplanning, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	Jai-Ming Lin , Yao-Wen Chang, TCG-S: orthogonal coupling of P*-admissible representations for general floorplans, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Maharaj Mukherjee , Kanad Chakraborty, A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation, Information Processing Letters, v.83 n.1, p.41-48, 16 July 2002
	Ning FU , Shigetoshi Nakatake , Yasuhiro Takashima , Yoji Kajitani, Abstraction and optimization of consistent floorplanning with pillar block constraints, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.19-24, January 27-30, 2004, Yokohama, Japan
	SheQin Dong , XianLong Hong , YuLiang Wu , Jun Gu, Deterministic VLSI block placement algorithm using less flexibility first principle, Journal of Computer Science and Technology, v.18 n.6, p.739-746, November 2003
	Yong Zhan , Yan Feng , Sachin S. Sapatnekar, A fixed-die floorplanning algorithm using an analytical approach, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Song Chen , Xian-Long Hong , She-Qin Dong , Yu-Chun Ma , Chung-Kuan Cheng , Jun Gu, Fast evaluation of bounded slice-line grid, Journal of Computer Science and Technology, v.19 n.6, p.973-980, November 2004
	Tung-Chieh Chen , Yao-Wen Chang, Modern floorplanning based on fast simulated annealing, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Chih-Yang Peng , Wen-Chang Chao , Yao-Wen Chang , Jyh-Herng Wang, Simultaneous block and I/O buffer floorplanning for flip-chip design, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Jen-Yi Wuu , Tung-Chieh Chen , Yao-Wen Chang, SoC test scheduling using the B-tree based floorplanning technique, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Jai-Ming Lin , Guang-Ming Wu , Yao-Wen Chang , Jen-Hui Chuang, Placement with symmetry constraints for analog layout design using TCG-S, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Jason Cong , Michail Romesis , Joseph R. Shinnerl, Fast floorplanning by look-ahead enabled recursive bipartitioning, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Xiaoping Tang , Ruiqi Tian , Martin D. F. Wong, Optimal redistribution of white space for wire length minimization, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Jing Li , Tan Yan , Bo Yang , Juebang Yu , Chunhui Li, A packing algorithm for non-manhattan hexagon/triangle placement design by using an adaptive o-tree representation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Sheqin Dong , Xianlong Hong , Xin Qi , Ruijie Wang , Song Chen , Jun Gu, VLSI module placement with pre-placed modules and considering congestion using solution space smoothing, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Florin Balasa , Sarat C. Maruvada , Karthik Krishnamoorthy, Using red-black interval trees in device-level analog placement with symmetry constraints, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Chen-Wei Liu , Yao-Wen Chang, Floorplan and power/ground network co-synthesis for fast design convergence, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Hayward H. Chan , Saurabh N. Adya , Igor L. Markov, Are floorplan representations important in digital design?, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	Changwen Zhuang , Keishi Sakanushi , Liyan Jin , Yoji Kajitani, An extended representation of Q-sequence for optimizing channel-adjacency and routing-cost, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Jia Wang , Hai Zhou, Interconnect estimation without packing via ACG floorplans, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Renshen Wang , Sheqin Dong , Xianlong Hong, An improved P-admissible floorplan representation based on Corner Block List, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Hayward H. Chan , Igor L. Markov, Practical slicing and non-slicing block-packing without simulated annealing, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Fei Su , Krishnendu Chakrabarty, Module placement for fault-tolerant microfluidics-based biochips, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.682-710, July 2006
	Song Chen , Takeshi Yoshimura, A stable fixed-outline floorplanning method, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Wenqi Huang , Duanbing Chen , Ruchu Xu, A new heuristic algorithm for rectangle packing, Computers and Operations Research, v.34 n.11, p.3270-3280, November, 2007
	Yiu-Cheong Tam , Evangeline F. Y. Young , Chris Chu, Analog placement with symmetry and other placement constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Tan Yan , Hiroshi Murata, Fast wire length estimation by net bundling for block placement, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	D. Chatterjee , T. W. Manikas, Power-density aware floorplanning for reducing maximum on-chip temperature, Proceedings of the 18th conference on Proceedings of the 18th IASTED International Conference: modelling and simulation, p.319-324, May 30-June 01, 2007, Montreal, Canada
	Chuan Lin , Hai Zhou , Chris Chu, A revisit to floorplan optimization by Lagrangian relaxation, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang, Temporal floorplanning using the T-tree formulation, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.300-305, November 07-11, 2004
	J. Cong , Jie Wei , Yan Zhang, A thermal-driven floorplanning algorithm for 3D ICs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.306-313, November 07-11, 2004
	Tung-Chieh Chen , Yao-Wen Chang , Shyh-Chang Lin, IMF: interconnect-driven multilevel floorplanning for large-scale building-module designs, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.159-164, November 06-10, 2005, San Jose, CA
	Florin Balasa, Device-level placement for analog layout: an opportunity for non-slicing topological representations, Proceedings of the 2001 conference on Asia South Pacific design automation, p.281-286, January 2001, Yokohama, Japan
	Wing Seung Yuen , Fung Yu Young, Slicing floorplan with clustering constraints, Proceedings of the 2001 conference on Asia South Pacific design automation, p.503-508, January 2001, Yokohama, Japan
	I-Min Liu , Hung-Ming Chen , Tan-Li Chou , Adnan Aziz , D. F. Wong, Integrated power supply planning and floorplanning, Proceedings of the 2001 conference on Asia South Pacific design automation, p.589-594, January 2001, Yokohama, Japan
	Maogang Wang , Abhishek Ranjan , Salil Raje, Multi-Million Gate FPGA Physical Design Challenges, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.891, November 09-13, 2003
	Peter G. Sassone , Sung K. Lim, A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.74, November 09-13, 2003
	Shiyou Zhao , Kaushik oy , Cheng-Kok Koh, Power Supply Noise Aware Floorplanning and Decoupling Capacitance Placement, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.489, January 07-11, 2002
	Yuchun Ma , Xianlong Hong , Sheqin Dong , Yici Cai , Chung-Kuan Cheng , Jun Gu, Stairway Compaction using Corner Block List and Its Applications with Rectilinear Blocks, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.387, January 07-11, 2002
	Jill H. Y. Law , Evangeline F. Y. Young, Multi-bend bus driven floorplanning, Integration, the VLSI Journal, v.41 n.2, p.306-316, February, 2008
	Chao-Hung Lu , Hung-Ming Chen , Chien-Nan Jimmy Liu, Effective decap insertion in area-array SoC floorplan design, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-20, September 2008
	Jia Wang , Hai Zhou, Exploring adjacency in floorplanning, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Martin Strasser , Michael Eick , Helmut Gräb , Ulf Schlichtmann , Frank M. Johannes, Deterministic analog circuit placement using hierarchically bounded enumeration and enhanced shape functions, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California