FAST-SP

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

FAST-SP: a fast algorithm for block placement based on sequence pair

Full text

Pdf (227 KB)

Source

Asia and South Pacific Design Automation Conference archive
Proceedings of the 2001 Asia and South Pacific Design Automation Conference table of contents

Yokohama, Japan

Pages: 521 - 526

Year of Publication: 2001

ISBN:0-7803-6634-4

Authors

Xiaoping Tang	University of Texas at Austin Austin, TX
D. F. Wong	University of Texas at Austin Austin, TX

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IPSJ : Information Processing Society of Japan
IEEE HK CAS : IEEE HK CAS and Comm. Joint Chapter
IEICE : Inst of Electronics, Info & Communication Engineers

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 23, Citation Count: 37

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	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/370155.370523 What is a DOI?

ABSTRACT

In this paper we present FAST-SP which is a fast block placement algorithm based on the sequence-pair placement representation. FAST-SP has two significant improvements over previous sequence-pair based placement algorithms: 1) FAST-SP translates each sequence pair to its corresponding block placement in O(n log log n) time based on a fast longest common subsequence computation. This is much faster than the traditional O(n2) method by first constructing horizontal and vertical constraint graphs and then performing longest path computations. As a result, FAST-SP can examine more sequence pairs and obtain a better placement solution in less runtime. 2) FAST-SP can handle placement constraints such as pre-placed constraint, range constraint, and boundary constraint. No previous sequence-pair based algorithms can handle range constraint and boundary constraint. Fast evaluation in O(n log log n) time is still valid in the presence of placement constraints and a novel cost function which unifies the evaluation of feasible and infeasible sequence pairs is used. We have implemented FAST-SP and obtained excellent experimental results. For all MCNC benchmark block placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O-tree and B*-tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm2) was obtained by a B*-tree based algorithm using 4752 seconds, and FAST-SP obtained a better result (36.5 mm2) in 31 seconds.

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	Semiconductor Industry Association. National Technology Roadmap for Semiconductors, 1997.
	2	Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
	3	Majid Sarrafzadeh , M. Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
	4	Jeff Parkhurst , Naveed Sherwani , Sury Maturi , Dana Ahrams , Eli Chiprout, SRC physical design top ten problem, Proceedings of the 1999 international symposium on Physical design, p.55-58, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300022]
	5	H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. "VLSI module placement based on rectangle-packing by the sequence pair", IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 15:12, pp. 1518- 1524, 1996.
	6	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 [doi>10.1145/267665.267675]
	7	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]
	8	Jin Xu , Pei-ning Guo , Chung-Kuan Cheng, Rectilinear block placement using sequence-pair, Proceedings of the 1998 international symposium on Physical design, p.173-178, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274561]
	9	Maggie Zhi-Wei Kang , Wayne Wei-Ming Dai, Topology constrained rectilinear block packing for layout reuse, Proceedings of the 1998 international symposium on Physical design, p.179-186, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274562]
	10	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 [doi>10.1145/299996.300034]
	11	Florin Balasa , Koen Lampaert, Module placement for analog layout using the sequence-pair representation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.274-279, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309930]
	12	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]
	13	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]
	14	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]
	15	T. Takahashi. "An algorithm for finding a maximum-weight decreasing sequence in a permutation, motivated by rectangle packing problem ", Technical Report of IEICE, VLD96, vol. VLD96, No. 201, pp. 31-35, 1996.
	16	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 [doi>10.1145/343647.343713]
	17	P. Van Emde Boas, R. Kaas, and Z. Zijlstra. "Design and implementation of an efficient priority queue", Mathematical Systems Theory 10, pp. 99-127, 1977.
	18	D.B. Johnson. "A priority queue in which initialization and queue operations take O(log log D) time", Mathematical Systems Theory 15, pp. 295-309, 1982.
	19	Y.W. Chang. Personal communication.

CITED BY 37

	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 , 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
	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
	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
	Jill H. Y. Law , Evangeline F. Y. Young, Multi-bend bus driven floorplanning, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	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
	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
	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
	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
	Jingcao Hu , Youngsoo Shin , Nagu Dhanwada , Radu Marculescu, Architecting voltage islands in core-based system-on-a-chip designs, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, 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
	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
	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
	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
	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
	Rong Liu , Sheqin Dong , Xianlong Hong, Fixed-outline floorplanning based on common subsequence, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, 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
	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
	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
	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
	Lei Cheng , Liang Deng , Martin D. F. Wong, Floorplanning for 3-D VLSI design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Dongku Kang , Hunsoo Choo , Khurram Muhammad , Kaushik Roy, Layout-driven architecture synthesis for high-speed digital filters, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.2, p.203-207, February 2006
	Hui Kong , Tan Yan , Martin D. F. Wong , Muhammet Mustafa Ozdal, Optimal bus sequencing for escape routing in dense PCBs, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Yu Xia , Malgorzata Chrzanowska-Jeske , Benyi Wang , Marcin Jeske, Using a Distributed Rectangle Bin-Packing Approach for Core-based SoC Test Scheduling with Power Constraints, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.100, November 09-13, 2003
	Fan Mo , Robert K. Brayton, A simultaneous bus orientation and bused pin flipping algorithm, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	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
	De-Sheng Chen , Chang-Tzu Lin , Yi-Wen Wang , Ching-Hwa Cheng, Fixed-outline floorplanning using robust evolutionary search, Engineering Applications of Artificial Intelligence, v.20 n.6, p.821-830, September, 2007
	A. J. Pfeiffer , T. Mukherjee , S. Hauan, Simultaneous design and placement of multiplexed chemical processing systems on microchips, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.229-236, November 07-11, 2004
	Hua Xiang , Xiaoping Tang , Martin D. F. Wong, Bus-Driven Floorplanning, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.66, November 09-13, 2003
	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
	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
	Jens Egeblad , David Pisinger, Heuristic approaches for the two- and three-dimensional knapsack packing problem, Computers and Operations Research, v.36 n.4, p.1026-1049, April, 2009
	Linfu Xiao , Evangeline F. Y. Young, Analog placement with common centroid and 1-D symmetry constraints, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Qiang Ma , Evangeline F. Y. Young, Network flow-based power optimization under timing constraints in MSV-driven floorplanning, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Yaoguang Wei , Sheqin Dong , Xianlong Hong, APWL-Y: An accurate and efficient wirelength estimation technique for hexagon/triangle placement, Integration, the VLSI Journal, v.40 n.4, p.406-419, July, 2007