Module placement on BSG-structure and IC layout applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Module placement on BSG-structure and IC layout applications

Full text

Publisher Site , Pdf

Pdf (522 KB)

Source

International Conference on Computer Aided Design archive
Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design table of contents

San Jose, California, United States

Pages: 484 - 491

Year of Publication: 1997

ISBN:0-8186-7597-7

Authors

Shigetoshi Nakatake	Department of Electrical and Electronic Engineering, Tokyo Institute of Technology
Kunihiro Fujiyoshi	School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)
Hiroshi Murata	School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)
Yoji Kajitani	Department of Electrical and Electronic Engineering, Tokyo Institute of Technology

Sponsors

IEEE-CS : Computer Society
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society Washington, DC, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 28, Citation Count: 62

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

A new method of packing the rectangles (modules) is presented with applications to IC layout design. It is based on the bounded-sliceline grid (BSG) structure. The BSG dissects the plane into rooms associated with binary relations ``right-to''and ``above'' such that any two rooms are uniquely in either relation. A packing is obtained through an assignment of modules on the BSG, followed by physical realization BSG-PACK. A simulated annealing searches for a good packing of all packings by changing the assignments. Experiments showed that hundreds of rectangles are easily packed in a small rectangle area (chip) with a quite good quality in area efficiency. A wide adaptability is demonstrated specific to IC layout design. Remarkable examples are: the chip is not necessarily rectangle, L-shaped modules and modules which are allowed to partially overlap each other can be handled.

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	Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
	2	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
	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	W.M.Dai and E.Kuh, "Simultaneous Floorplanning and Global Routing for Hierarchical Building Block Layout", IEEE Trans. on CAD Vol.6 No.5 pp.828-837, 1987.
	5	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]
	6	T.-C. Wang , D. F. Wong, A graph theoretic technique to speed up floorplan area optimization, Proceedings of the 29th ACM/IEEE conference on Design automation, p.62-68, June 08-12, 1992, Anaheim, California, United States
	7	Y. Kajitani, "Order of Channels for Safe Routing and Optimal Compaction of Routing Area", IEEE Trans. on CAD Vol.2 No.4 pp.293-300, 1983.
	8	Larry Stockmeyer, Optimal orientations of cells in slicing floorplan designs, Information and Control, v.57 n.2-3, p.91-101, May/June 1983 [doi>10.1016/S0019-9958(83)80038-2]
	9	H.Matsuda, S.Nakatake and Y.Kajitani, "Optimum Slicing- Structure Floorplanning with Routing Area Included", IEICE Technical Report VLD94-109 Vol.94 No.531 pp.9-14, 1995.
	10	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]
	11	Jack A. Hudson , John A. Wisniewski , Randy C. Peters, Module positioning algorithms for rectilinear macrocell assemblies, Proceedings of the 21st conference on Design automation, p.672-675, June 25-27, 1984, Albuquerque, New Mexico, United States
	12	M. C. Chi, An automatic rectilinear partitioning procedure for standard cells, Proceedings of the 24th ACM/IEEE conference on Design automation, p.50-55, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37895]
	13	Tsu-chang Lee, A bounded 2D contour searching algorithm for floorplan design with arbitrarily shaped rectilinear and soft modules, Proceedings of the 30th international conference on Design automation, p.525-530, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165014]
	14	Shigetoshi Nakatake , Yoji Kajitani, Channel-driven global routing with consistent placement (extended abstract), Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.350-355, November 06-10, 1994, San Jose, California, United States
	15	Y.Shiraishi, M.Kimura, K.Kobayashi, T.Hino, M.Seriuchi, and M.Kusaoke, "A High-Packing Density Module Generator for Bipolar Analog LSIs", Proc. International Conf. on CAD pp.194-197, 1990.

CITED BY 62

	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
	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
	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
	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
	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
	Hung-Ming Chen , Hai Zhou , F. Y. YOung , D. F. Wong , Hannah H. Yang , Naveed Sherwani, Integrated floorplanning and interconnect planning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.354-357, November 07-11, 1999, San Jose, 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
	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
	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
	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
	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
	Shigetoshi Nakatake , Keishi Sakanushi , Yoji Kajitani , Masahiro Kawakita, The channeled-BSG: a universal floorplan for simultaneous place/route with IC applications, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.418-425, November 08-12, 1998, San Jose, California, United States
	Takashi Nojima , Xiaoke Zhu , Yasuhiro Takashima , Shigetoshi Nakatake , Yoji Kajitani, Multi-level placement with circuit schema based clustering in analog IC layouts, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.406-411, January 27-30, 2004, Yokohama, Japan
	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
	Yangdong Deng , Wojciech P. Maly, Interconnect characteristics of 2.5-D system integration scheme, Proceedings of the 2001 international symposium on Physical design, p.171-175, April 01-04, 2001, Sonoma, California, United States
	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
	F. Y. Young , Chris C. N. Chu , W. S. Luk , Y. C. Wong, Floorplan area minimization using Lagrangian relaxation, Proceedings of the 2000 international symposium on Physical design, p.174-179, May 2000, San Diego, California, United States
	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
	F. Y. Young , D. F. Wong, Slicing floorplans with range constraint, Proceedings of the 1999 international symposium on Physical design, p.97-102, April 12-14, 1999, Monterey, California, United States
	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
	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
	Takashi Nojima , Yasuhiro Takashima , Shigetoshi Nakatake , Yoji Kajitani, A device-level placement with multi-directional convex clustering, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	H. Murata , K. Fujiyoshi , M. Kaneko, VLSI/PCB placement with obstacles based on sequence-pair, Proceedings of the 1997 international symposium on Physical design, p.26-31, April 14-16, 1997, Napa Valley, California, United States
	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
	Kunihiro Fujiyoshi , Hiroshi Murata, Arbitrary convex and concave rectilinear block packing using sequence-pair, Proceedings of the 1999 international symposium on Physical design, p.103-110, April 12-14, 1999, Monterey, California, United States
	F. Y. Young , D. F. Wong, Slicing floorplans with pre-placed modules, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.252-258, November 08-12, 1998, San Jose, 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
	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
	Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France
	Dinesh P. Mehta , Naveed Sherwani, On the use of flexible, rectilinear blocks to obtain minimum-area floorplans in mixed block and cell designs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.1, p.82-97, Jan. 2000
	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
	Keishi Sakanushi , Shigetoshi Nakatake , Yoji Kajitani, The multi-BSG: stochastic approach to an optimum packing of convex-rectilinear blocks, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.267-274, November 08-12, 1998, San Jose, California, United States
	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
	Renshen Wang , Evangeline F. Y. Young , Yi Zhu , Fan Chung Graham , Ronald Graham , Chung-Kuan Cheng, 3-D floorplanning using labeled tree and dual sequences, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, 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
	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
	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
	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
	Chang-Tzu Lin , De-Sheng Chen , Yi-Wen Wang, Robust fixed-outline floorplanning through evolutionary search, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.42-44, January 27-30, 2004, Yokohama, Japan
	Maggie Zhiwei Kang , Wayne Wei-Mingi Dai, Arbitrary rectilinear block packing based on sequence pair, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.259-266, November 08-12, 1998, San Jose, 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
	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
	Jason Cong , Tianming Kong , Faming Liang , Jun S. Liu , Wing Hung Wong , Dongmin Xu, Dynamic weighting Monte Carlo for constrained floorplan designs in mixed signal application, Proceedings of the 2000 conference on Asia South Pacific design automation, p.277-282, January 2000, 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
	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
	Amir H. Salek , Jinan Lou , Massoud Pedram, A DSM design flow: putting floorplanning, technology-mapping, and gate-placement together, Proceedings of the 35th annual conference on Design automation, p.128-134, June 15-19, 1998, San Francisco, California, United States
	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
	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
	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
	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
	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
	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
	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
	Jingcao Hu , Yangdong Deng , Radu Marculescu, System-Level Point-to-Point Communication Synthesis Using Floorplanning Information, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.573, January 07-11, 2002
	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
	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
	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
	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
	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
	Yangdong (Steven) Deng , Wojciech Maly, 2.5D system integration: a design driven system implementation schema, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.450-455, January 27-30, 2004, Yokohama, Japan
	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
	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