Fast evaluation of sequence pair in block placement by longest common subsequence computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Fast evaluation of sequence pair in block placement by longest common subsequence computation

Full text

Publisher Site , Pdf

Pdf (131 KB)

Source

Design, Automation, and Test in Europe archive
Proceedings of the conference on Design, automation and test in Europe table of contents

Paris, France

Pages: 106 - 111

Year of Publication: 2000

ISBN:1-58113-244-1

Authors

Xiaoping Tang	Department of Computer Sciences, University of Texas at Austin
Ruiqi Tian	Department of Computer Sciences, University of Texas at Austin and Motorola Computational Technology Lab, Austin, Texas
D. F. Wong	Motorola Computational Technology Lab, Austin, Texas

Sponsors

EDAA : European Design Automation Association
SIGDA: ACM Special Interest Group on Design Automation
ECSI :
RAS : RAS
EDAC : Electronic Design Automation Consortium
IEEE-CS : Computer Society
IFIP : International Federation for Information Processing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 44, Citation Count: 18

Additional Information:

references cited by 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/343647.343713 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	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.
	2	Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1997.
	3	Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1995
	4	Majid Sarrafzadeh , M. Sarrafzadeh , C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill Higher Education, 1996
	5	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]
	6	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]
	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. Takahashi, "An Algorithm for Finding a Maximum- Weight Decreasing Sequence in a Permutation, Motivated by Rectangle Packing Problem ", Technical Report oflEICE, VLD96, vol. VLD96, No. 201, pp. 31-35, 1996.
	9	James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
	10	James A. McHugh, Algorithmic graph theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	11	S. Kirkpatrick, C.D. Gelatt, and M.R Vecchi, " Optimization by simulated annealing". Science, vol. 220, pp. 671-680, 1983.

CITED BY 18

	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
	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
	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
	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
	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
	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
	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
	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
	Tan Yan , Qing Dong , Yasuhiro Takashima , Yoji Kajitani, How does partitioning matter for 3D floorplanning?, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA
	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
	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
	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
	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
	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
	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
	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

Collaborative Colleagues:

Xiaoping Tang: colleagues

Ruiqi Tian: colleagues

D. F. Wong: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player