New performance-driven FPGA routing algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New performance-driven FPGA routing algorithms

Full text

Pdf (359 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 32nd annual ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 562 - 567

Year of Publication: 1995

ISBN:0-89791-725-1

Authors

Michael J. Alexander	Department of Computer Science, University of Virginia, Charlottesville, VA
Gabriel Robins	Department of Computer Science, University of Virginia, Charlottesville, VA

Sponsors

EDAC : Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 28, Citation Count: 26

Additional Information:

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/217474.217589 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	Michael J. Alexander , James P. Cohoon , Joseph L. Ganley , Gabriel Robins, An architecture-independent approach to FPGA routing based on multi-weighted graphs, Proceedings of the conference on European design automation, p.259-264, September 19-23, 1994, Grenoble, France
	2	M. J. ALEXANDER AND G. ROBINS, A New Approach to FPGA Routing Based on Multi-Weighted Graphs, in Proc. ACM/SIGDA Intl. Workshop on Field- Programmable Gate Arrays, Berkeley, CA, February 1994.
	3	Stephen D. Brown , Robert J. Francis , Jonathan Rose , Zvonko G. Vranesic, Field-programmable gate arrays, Kluwer Academic Publishers, Norwell, MA, 1992
	4	Yao-Wen Chang , Shashidhar Thakur , Kai Zhu , D. F. Wong, A new global routing algorithm for FPGAs, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.356-361, November 06-10, 1994, San Jose, California, United States
	5	Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
	6	E. W. DIJKSTRA, A Note on Two Problems in Connection With Graphs, Numerische Mathematik, 1 (1959), pp. 269-271.
	7	J. L. GANLEY, private communication, April, 1994.
	8	J. GRIFFITH, G. ROBINS, J. S. SALOWE, AND T. ZHANG, Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time, IEEE Trans. Computer- Aided Design, 13 (1994), pp. 1351-1365.
	9	F. K. HWANG, D. S. RICHARDS, AND P. WINTER, The Steiner Tree Problem, North-Holland, 1992.
	10	A. B. KAHNG AND G. ROBINS, A New Class of Iterative Steiner Tree Heuristics With Good Performance, IEEE Trans. Computer-Aided Design, 11 (1992), pp. 893-902.
	11	A. B. KAHNG AND G. ROBINS, On Optimal Interconnections for VLSI, Kluwer Academic Publishers, Boston, MA, 1995.
	12	L. Kou, G. MARKOWSKY, AND g. BERMAN, A Fast Algorithm for Steiner Trees, Acta Informatica, 15 (1981), pp. 141-145.
	13	G. G. LEMIEUX AND S. D. BROWN, A Detailed Routing Algorithm for Allocating Wire Segments in Field- Programmable Gate Arrays, in Proc. ACM/SIGDA Physical Design Workshop, Lake Arrowhead, CA, April 1993.
	14	S. K. RAO, P. SADAYAPPAN, F. K. HWANG, AND P. W. SHOR, The Rectilinear Steiner Arborescence Problem, Algorithmica, (1992), pp. 277-288.
	15	Yachyang Sun , Ting-Chi Wang , C. K. Wong , C. L. Liu, Routing for symmetric FPGAs and FPICs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.486-490, November 07-11, 1993, Santa Clara, California, United States
	16	Stephen M. Trimberger, Field-Programmable Gate Array Technology, Kluwer Academic Publishers, Norwell, MA, 1994
	17	Yu-Liang Wu , Douglas Chang, On the NP-completeness of regular 2-D FPGA routing architectures and a novel solution, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.362-366, November 06-10, 1994, San Jose, California, United States
	18	Y.-L. Wu AND M. MAREK-SADOWSKA, An Efficient Router for 2-D Field Programmable Gate Arrays, in European Design and Test Conf., 1994, pp. 412-416.
	19	XILINX, The Programmable Gate Array Data Book, Xilinx, Inc., San Jose, California, 1994.
	20	A. Z. ZELIKOVSKY, An 11,/6 Approximation Algorithm for the Network Steiner Problem, Algorithmica, 9 (1993), pp. 463-470.

CITED BY 26

	Yao-Wen Chang , D. F. Wong , C. K. Wong, Universal switch-module design for symmetric-array-based FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.80-86, February 11-13, 1996, Monterey, California, United States
	Yao-Wen Chang , D. F. Wong , C. K. Wong, Universal switch modules for FPGA design, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.80-101, Jan. 1996
	Yao-Wen Chang , Kai Zhu , D. F. Wong, Timing-driven routing for symmetrical array-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.433-450, July 2000
	Clarissa Cook , Dale A. Schoenfeld , Roger L. Wainwright, Finding rural postman tours, Proceedings of the 1998 ACM symposium on Applied Computing, p.318-326, February 27-March 01, 1998, Atlanta, Georgia, United States
	Yao-Wen Chang , Yu-Tsang Chang, An architecture-driven metric for simultaneous placement and global routing for FPGAs, Proceedings of the 37th conference on Design automation, p.567-572, June 05-09, 2000, Los Angeles, California, United States
	Guy G. F. Lemieux , Stephen D. Brown , Daniel Vranesic, On two-step routing for FPGAS, Proceedings of the 1997 international symposium on Physical design, p.60-66, April 14-16, 1997, Napa Valley, California, United States
	Heather L. Christensen , Roger L. Wainwright , Dale A. Schoenefeld, A hybrid algorithm for the point to multipoint routing problem, Proceedings of the 1997 ACM symposium on Applied computing, p.263-268, April 1997, San Jose, California, United States
	Nak-Woong Eum , Taewhan Kim , Chong-Min Kyung, An accurate evaluation of routing density for symmetrical FPGAs, Proceedings of the 11th Great Lakes symposium on VLSI, p.51-55, March 2001, West Lafayette, Indiana, United States
	Hongbing Fan , Jiping Liu , Yu-Liang Wu , Chak-Chung Cheung, On optimum switch box designs for 2-D FPGAs, Proceedings of the 38th conference on Design automation, p.203-208, June 2001, Las Vegas, Nevada, United States
	Nak Woong Eum , Taewhan Kim , Chong Min Kyung, A router for symmetrical FPGAs based on exact routing density evaluation, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Hongbing Fan , Jiping Liu , Yu Liang Wu, General models for optimum arbitrary-dimension FPGA switch box designs, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	Pablo Galiasso , Roger L. Wainwright, A hybrid genetic algorithm for the point to multipoint routing problem with single split paths, Proceedings of the 2001 ACM symposium on Applied computing, p.327-332, March 2001, Las Vegas, Nevada, United States
	Hongbing Fan , Jiping Liu , Yu-Liang Wu, General Models and a Reduction Design Technique for FPGA Switch Box Designs, IEEE Transactions on Computers, v.52 n.1, p.21-30, January 2003
	CeRA: A Router for Symmetrical FPGAs Based on Exact Routing Density Evaluation, IEEE Transactions on Computers, v.53 n.7, p.829-842, July 2004
	Stephen Brown , Muhammad Khellah , Zvonko Vranesic, Minimizing FPGA Interconnect Delays, IEEE Design & Test, v.13 n.4, p.16-23, December 1996
	Jiping Liu , Hongbing Fan , Yu-Liang Wu, On improving FPGA routability applying multi-level switch boxes, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Jai-Ming Lin , Song-Ra Pan , Yao-Wen Chang, Graph matching-based algorithms for array-based FPGA segmentation design and routing, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Siva Nageswara Rao Borra , Annamalai Muthukaruppan , S. Suresh , V. Kamakoti, A novel approach to the placement and routing problems for field programmable gate arrays, Applied Soft Computing, v.7 n.1, p.455-470, January, 2007
	Yajun Ran , M. Marek-Sadowska, An integrated design flow for a via-configurable gate array, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.582-589, November 07-11, 2004
	Seokjin Lee , Yongseok Cheon , Martin D. F. Wong, A Min-Cost Flow Based Detailed Router for FPGAs, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.388, November 09-13, 2003
	Le-Chin Eugene Liu , C. Sechen, Multi-layer chip-level global routing using an efficient graph-based Steiner tree heuristic, Proceedings of the 1997 European conference on Design and Test, p.311, March 17-20, 1997
	Srilata Raman , C. L. Liu , L. G Jones, A Timing-Constrained Incremental Routing Algorithm for Symmetrical FPGAs, Proceedings of the 1996 European conference on Design and Test, p.170, March 11-14, 1996
	M. S. Zahrani , M. J. Loomes , J. A. Malcolm , A. Z. M. Dayem Ullah , K. Steinhöfel , A. A. Albrecht, Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing, Computers and Operations Research, v.35 n.6, p.2049-2070, June, 2008
	Keith So, Enforcing long-path timing closure for FPGA routing with path searches on clamped lexicographic spirals, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Kanupriya Gulati , Sunil P. Khatri, Improving FPGA routability using network coding, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
	Mu-Huan Chiang , Gregory T. Byrd, Adaptive aggregation tree transformation for energy-efficient query processing in sensor networks, International Journal of Sensor Networks, v.6 n.1, p.51-64, August 2009