TCG

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

TCG: a transitive closure graph-based representation for non-slicing floorplans

Full text

Pdf (142 KB)

Source

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

Las Vegas, Nevada, United States

Pages: 764 - 769

Year of Publication: 2001

ISBN:1-58113-297-2

Authors

Jai-Ming Lin	Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan
Yao-Wen Chang	Department of Computer and Information Science, National Chiao Tung University, Hsinchu 300, Taiwan

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): 10, Downloads (12 Months): 60, Citation Count: 41

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

ABSTRACT

In this paper, we propose a transitive closure graph-based representation for general floorplans, called TCG, and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operations, facilitating the convergence to a desired solution. All these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.

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	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 [doi>10.1145/337292.337541]
	2	Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
	3	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
	4	S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing," Science, vol. 220, no. 4598, pp.671-680, May, 1983.
	5	E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976.
	6	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
	7	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
	8	T. Ohtsuki, N. Suzigama, and H. Hawanishi, "An optimization technique for intergrated circuit layout design," Proc. ICCST, Kyoto, pp. 67-68, 1970.
	9	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]
	10	Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
	11	P. Pan and C.-L. Liu, "Area minimization for floorplans," IEEE TCAD, pp. 123- 132, Jan. 1995.
	12	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 [doi>10.1145/332357.332395]
	13	Sadiq M. Sait , Habib Youssef, VISI Physical Design Automation: Theory and Practice, McGraw-Hill, Inc., New York, NY, 1994
	14	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 [doi>10.1145/370155.370523]
	15	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]
	16	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

CITED BY 42

	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
	Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	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
	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
	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
	Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang , Hsin-Lung Chen, Temporal floorplanning using 3D-subTCG, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.725-730, January 27-30, 2004, Yokohama, Japan
	Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA
	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
	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
	S. N. Adya , I. L. Markov, Combinatorial techniques for mixed-size placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.58-90, January 2005
	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
	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
	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
	Jason Cong , Ashok Jagannathan , Yuchun Ma , Glenn Reinman , Jie Wei , Yan Zhang, An automated design flow for 3D microarchitecture evaluation, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	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
	Jason Cong , Ashok Jagannathan , Glenn Reinman , Michail Romesis, Microarchitecture evaluation with physical planning, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	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
	Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Jill H.Y. Law , Evangeline F.Y. Young , Royce L.S. Ching, Block alignment in 3D floorplan using layered TCG, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, 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
	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
	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
	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
	Pingqiang Zhou , Yuchun Ma , Zhouyuan Li , Robert P. Dick , Li Shang , Hai Zhou , Xianlong Hong , Qiang Zhou, 3D-STAF: scalable temperature and leakage aware floorplanning for three-dimensional integrated circuits, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	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
	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
	Tilen Ma , Evangeline F. Y. Young, TCG-based multi-bend bus driven floorplanning, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang, Temporal floorplanning using the three-dimensional transitive closure subGraph, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.4, p.37-es, September 2007
	Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang, Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.3 n.3, p.13-es, November 2007
	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
	Hsin-Chen Chen , Yi-Lin Chuang , Yao-Wen Chang , Yung-Chung Chang, Constraint graph-based macro placement for modern mixed-size circuit designs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Hsin-Chen Chen , Yi-Lin Chuang , Yao-Wen Chang , Yung-Chung Chang, Constraint graph-based macro placement for modern mixed-size circuit designs, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Chiu-Wing Sham , Evangeline F. Y. Young, Block flipping and white space distribution for wirelength minimization, Integration, the VLSI Journal, v.42 n.2, p.246-253, February, 2009
	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
	Jia Wang , Hai Zhou, Linear constraint graph for floorplan optimization with soft blocks, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Loïc Lagadec , Bernard Pottier , Damien Picard, Toolset for nano-reconfigurable computing, Microelectronics Journal, v.40 n.4-5, p.665-672, April, 2009
	Kunihiro Fujiyoshi , Hidenori Kawai , Keisuke Ishihara, A tree based novel representation for 3D-block packing, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.5, p.759-764, May 2009