Segmented channel routing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Segmented channel routing

Full text

Pdf (683 KB)

Source

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

Orlando, Florida, United States

Pages: 567 - 572

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Jonathan Greene	Actel Corporation, Sunnyvale, CA
Vwani Roychowdhury	Information Systems Lab., Stanford University, Stanford, CA
Sinan Kaptanoglu	Actel Corporation, Sunnyvale, CA
Abbas El Gamal	Information Systems Lab., Stanford University, Stanford, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 21, Citation Count: 18

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

ABSTRACT

Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins of the gates or joined end-to-end to form longer segments by programmable switches. The segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general problem is NP-complete, but it can be adequately solved in practice. Experiments indicate that a segmented channel with judiciously chosen segment lengths may near the efficiency of a conventional channel.

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	M. Lorenzetti and D. S. Baeder. "Routing." Chapter 5 in Physical Design Automation of VLSI Systems, B. Preas and M. Lorertzetti, eds. Benjamint~ummings, 1988.
	2	H. Hsieh, et al. "A Second Generation User Programmable Gate Array." Proc. Custom Integrated Circuits Conf., May 1987, pp. 515- 521.
	3	A. El Gamal, L Greene, L Reyneri, E. Rogoyski, K. EI-Ayat, and A. Mohsen. "An Architecture for Electrically Configurable Gate Arrays." IEEE J. Solid-State Circuits, Vol. 24, No. 2, April, 1989, pp. 394-398.
	4	E. Hamdy, et al. Dielectric Based Antifuse for Logic and Memory ICs. IEDM Tech. Digest, San Francisco, CA, 1988, pp. 786-789.
	5	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805069]
	6	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	7	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979

CITED BY 18

	Surendra Burman , Chandar Kamalanathan , Naveed Sherwani, New channel segmentation model and associated routing algorithm for high performance FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.22-25, November 1992, Santa Clara, California, United States
	Kai Zhu , D. F. Wong, On channel segmentation design for row-based FPGAs, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.26-29, November 1992, Santa Clara, California, United States
	Kai Zhu , D. F. Wong, Switch bound allocation for maximizing routability in timing-driven routing of FPGAs, Proceedings of the 31st annual conference on Design automation, p.165-170, June 06-10, 1994, San Diego, California, United States
	Massoud Pedram , Bahman S. Nobandegani , Bryan T. Preas, Architecture and routability analysis for row-based FPGAs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.230-235, November 07-11, 1993, Santa Clara, California, United States
	Cheng-Hsing Yang , Sao-Jie Chen , Jan-Ming Ho , Chia-Chun Tsai, Efficient routability check algorithms for segmented channel routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.735-747, July 2000
	Tong Liu , Wei Kang Huang , Fabrizio Lombardi, Testing of uncustomized segmented channel field programmable gate arrays, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.125-131, February 12-14, 1995, Monterey, California, United States
	Kai Zhu , D. F. Wong , Yao-Wen Chang, Switch module design with application to two-dimensional segmentation design, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.480-485, November 07-11, 1993, Santa Clara, California, United States
	Gi-Joon Nam , Karem A. Sakallah , Rob A. Rutenbar, Satisfiability-based layout revisited: detailed routing of complex FPGAs via search-based Boolean SAT, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.167-175, February 21-23, 1999, Monterey, California, United States
	Stephen Trimberger, Effects of FPGA architecture on FPGA routing, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.574-578, June 12-16, 1995, San Francisco, California, United States
	Vaughn Betz , Jonathan Rose, FPGA routing architecture: segmentation and buffering to optimize speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.59-68, February 21-23, 1999, Monterey, California, United States
	Dwight D. Hill, A CAD system for the design of field programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.187-192, June 17-22, 1991, San Francisco, California, United States
	R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.119-125, February 09-11, 1997, Monterey, California, United States
	Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for row-based FPGAs, Proceedings of the 31st annual conference on Design automation, p.301-307, June 06-10, 1994, San Diego, California, United States
	Jonathan Rose , Dwight Hill, Architectural and physical design challenges for one-million gate FPGAs and beyond, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.129-132, February 09-11, 1997, Monterey, California, United States
	Sudip Nag , Kaushik Roy, On Routability for FPGAs under Faulty Conditions, IEEE Transactions on Computers, v.44 n.11, p.1296-1305, November 1995
	M. Palczewski, Plane parallel a maze router and its application to FPGAs, Proceedings of the 29th ACM/IEEE conference on Design automation, p.691-697, June 08-12, 1992, Anaheim, California, United States
	Sancho Salcedo-Sanz , Yong Xu , Xin Yao, Meta-Heuristic Algorithms for FPGA Segmented Channel Routing Problems with Non-standard Cost Functions, Genetic Programming and Evolvable Machines, v.6 n.4, p.359-379, December 2005
	Ian Kuon , Russell Tessier , Jonathan Rose, FPGA Architecture: Survey and Challenges, Foundations and Trends® in Electronic Design Automation, v.2 n.2, p.135-253, February 2008