PathFinder

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

PathFinder: a negotiation-based performance-driven router for FPGAs

Full text

Pdf (76 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays table of contents

Monterey, California, United States

Pages: 111 - 117

Year of Publication: 1995

ISBN:0-89791-743-X

Authors

Larry McMurchie	Dept. of Computer Science and Engineering, University of Washington, Seattle, WA
Carl Ebeling	Dept. of Computer Science and Engineering, University of Washington, Seattle, WA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 62, Citation Count: 79

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

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

ABSTRACT

Routing FPGAs is a challenging problem because of the relative scarcity of routing resources, both wires and connection points. This can lead either to slow implementations caused by long wiring paths that avoid congestion or a failure to route all signals. This paper presents PathFinder, a router that balances the goals of performance and routability. PathFinder uses an iterative algorithm that converges to a solution in which all signals are routed while achieving close to the optimal performance allowed by the placement. Routability is achieved by forcing signals to negotiate for a resource and thereby determine which signal needs the resource most. Delay is minimized by allowing the more critical signals a greater say in this negotiation. Because PathFinder requires only a directed graph to describe the architecture of routing resources, it adapts readily to a wide variety of FPGA architectures such as Triptych, Xilinx 3000 and mesh-connected arrays of FPGAs. The results of routing ISCAS benchmarks on the Triptych FPGA architecture show an average increase of only 4.5% in critical path delay over the optimum delay for a placement. Routes of ISCAS benchmarks on the Xilinx 3000 architecture show a greater completion rate than commercial tools, as well as 11% faster implementations.

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.

	Alexander94	M. Alexander, "A Unified New Approach to FPGA Routing Based on Multi-Weighted Graphs," 2rid International ACM/SIGDA Workshop on Field- Programmable Gate Arrays, February 1994.
	Brown92	S. Brown, J. Rose, and Z. Vranesic, "A Detailed Router for Field-Programmable Gate Arrays," IEEE Transactions on Computer-Aided Design, vol. 11, no. 5, May 1992, pp. 620-628.
	Cohn91	J. Cohn, D. Garrod, R. Rutenbar, and L. Carley, "KOAN/ANAGRAM II: New Tools for Device- Level Analog Placement and Routing," IEEE Journal of Solid-State Circuits, vol. 26, March 1991, pp. 330-342.
	Dees81	William A. Dees, Jr. , Robert J. Smith, II, Performance of interconnection rip-up and reroute strategies, Proceedings of the 18th conference on Design automation, p.382-390, June 29-July 01, 1981, Nashville, Tennessee, United States
	Frankle92	J. Frankle, Iterative and adaptive slack allocation for performance-driven layout and FPGA routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.536-542, June 08-12, 1992, Anaheim, California, United States
	Hauck92	S. Hauck, G. Borriello and C. Ebeling, "TRIPTYCH: An FPGA Architecture with Integrated Logic and Routing," in Prec. of the 1992 Conference on Advanced Research in VLSI and Parallel Systems, March 1992, pp. 26-43.
	Hill91	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 [doi>10.1145/127601.127662]
	Linsker84	Ralph Linsker, An iterative-improvement penalty-function-driven wire routing system, IBM Journal of Research and Development, v.28 n.5, p.613-624, September 1984
	Nair87	R. Nair, "A Simple Yet Effective Technique for Global Wiring," IEEE Transactions on Computer- Aided Design, vol. CAD-6, no. 6, March 1987, pp. 165-172.
	Takahashi80	H. Takahashi and A. Matsuyama, "An Approximate Solution for the Problem in Graphs," Japonica, vol. 24, 1980, pp. 573-577.
	Xilinx93	Xilinx, Inc., Xact Development System, 1993.

CITED BY 79

	Darren C. Cronquist , Larry McMurchie, Emerald: an architecture-driven tool compiler for FPGAs, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.144-150, February 11-13, 1996, Monterey, California, United States
	Yanheng Zhang , Yue Xu , Chris Chu, FastRoute3.0: a fast and high quality global router based on virtual capacity, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Pak K. Chan , Martine D. F. Schlag, New parallelization and convergence results for NC: a negotiation-based FPGA router, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.165-174, February 10-11, 2000, Monterey, California, United States
	Rajeev Jayaraman, Physical design for FPGAs, Proceedings of the 2001 international symposium on Physical design, p.214-221, April 01-04, 2001, Sonoma, California, United States
	Deshanand P. Singh , Stephen D. Brown, Incremental placement for layout driven optimizations on FPGAs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.752-759, November 10-14, 2002, San Jose, California
	Ken Eguro , Scott Hauck, Armada: timing-driven pipeline-aware routing for FPGAs, Proceedings of the internation symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA
	Ken Eguro , Scott Hauck, Enhancing timing-driven FPGA placement for pipelined netlists, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Stephen Brown , Muhammad Khellah , Zvonko Vranesic, Minimizing FPGA Interconnect Delays, IEEE Design & Test, v.13 n.4, p.16-23, December 1996
	Jason Cong , Min Xie , Yan Zhang, An enhanced multilevel routing system, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.51-58, November 10-14, 2002, San Jose, California
	Akshay Sharma , Carl Ebeling , Scott Hauck, PipeRoute: a pipelining-aware router for FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Akshay Sharma , Katherine Compton , Carl Ebeling , Scott Hauck, Exploration of pipelined FPGA interconnect structures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
	Shawn Phillips , Scott Hauck, Automatic layout of domain-specific reconfigurable subsystems for system-on-a-chip, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing routability estimation methods for FPGAs, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	Deshanand P. Singh , Stephen D. Brown, The case for registered routing switches in field programmable gate arrays, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.161-169, February 2001, Monterey, California, United States
	Mark Holland , Scott Hauck, Improving performance and robustness of domain-specific CPLDs, Proceedings of the internation symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA
	Shenghua Liu , Guoqiang Chen , Tom Tong Jing , Lei He , Robi Dutta , Xian-Long Hong, Diffusion-driven congestion reduction for substrate topological routing, Proceedings of the 2009 international symposium on Physical design, March 29-April 01, 2009, San Diego, California, USA
	Quang Dinh , Deming Chen , Martin D.F. Wong, A routing approach to reduce glitches in low power FPGAs, Proceedings of the 2009 international symposium on Physical design, March 29-April 01, 2009, San Diego, California, USA
	Marrakchi Zied , Mrabet Hayder , Amouri Emna , Mehrez Habib, Efficient tree topology for FPGA interconnect network, Proceedings of the 18th ACM Great Lakes symposium on VLSI, May 04-06, 2008, Orlando, Florida, USA
	Ping-Hung Yuh , Chia-Lin Yang , Yao-Wen Chang, BioRoute: a network-flow based routing algorithm for digital microfluidic biochips, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Jhih-Rong Gao , Pei-Ci Wu , Ting-Chi Wang, A new global router for modern designs, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
	Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, November 09-13, 2003
	Shankar Balachandran , Parivallal Kannan , Dinesh Bhatia, On Routing Demand and Congestion Estimation for FPGAs, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.639, January 07-11, 2002
	Sudip K. Nag , Rob A. Rutenbar, Performance-driven simultaneous place and route for island-style FPGAs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.332-338, November 05-09, 1995, San Jose, California, United States
	Deshanand P. Singh , Stephen D. Brown, Integrated retiming and placement for field programmable gate arrays, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA
	Fred Ma , John P. Knight , Calvin Plett, Physical resource binding for a Coarse-Grain reconfigurable array using evolutionary algorithms, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.13 n.5, p.553-563, May 2005
	Stephen Friedman , Allan Carroll , Brian Van Essen , Benjamin Ylvisaker , Carl Ebeling , Scott Hauck, SPR: an architecture-adaptive CGRA mapping tool, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	Hayder Mrabet , Zied Marrakchi , Pierre Souillot , Habib Mehrez, Performances improvement of FPGA using novel multilevel hierarchical interconnection structure, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Chin-Hsiung Hsu , Huang-Yu Chen , Yao-Wen Chang, Multi-layer global routing considering via and wire capacities, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	Chandra Mulpuri , Scott Hauck, Runtime and quality tradeoffs in FPGA placement and routing, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.29-36, February 2001, Monterey, California, United States
	Ke-Ren Dai , Wen-Hao Liu , Yih-Lang Li, Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Fei Su , William Hwang , Krishnendu Chakrabarty, Droplet routing in the synthesis of digital microfluidic biochips, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	K. K. Lee , Martin D. F. Wong, LRoute: a delay minimal router for hierarchical CPLDs, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.12-20, February 2001, Monterey, California, United States
	William Swartz, Issues in global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Joey Y. Lin , Ashok Jagannathan , Jason Cong, Placement-driven technology mapping for LUT-based FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Seokjin Lee , Hua Xiang , D. F. Wong , Richard Y. Sun, Wire type assignment for FPGA routing, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Seokjin Lee , D. F. Wong, Timing-driven routing for FPGAs based on Lagrangian relaxation, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	Keith So, Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search space, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Randy Huang , John Wawrzynek , André DeHon, Stochastic, spatial routing for hypergraphs, trees, and meshes, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	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
	Muhammet Mustafa Ozdal , Martin D. F. Wong, Archer: a history-driven global routing algorithm, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Narendra V. Shenoy , Jamil Kawa , Raul Camposano, Design automation for mask programmable fabrics, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Yen-Jung Chang , Yu-Ting Lee , Ting-Chi Wang, NTHU-Route 2.0: a fast and stable global router, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California
	R. Huang , R. Vemuri, Analysis and evaluation of a hybrid interconnect structure for FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.595-601, November 07-11, 2004
	Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing interconnect estimation methods for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.4, p.381-385, April 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
	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
	Yohei Matsumoto , Masakazu Hioki , Takashi Kawanami , Toshiyuki Tsutsumi , Tadashi Nakagawa , Toshihiro Sekigawa , Hanpei Koike, Performance and yield enhancement of FPGAs with within-die variation using multiple configurations, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
	Catherine Dezan , Ciprian Teodorov , Loïc Lagadec , Michael Leuchtenburg , Teng Wang , Pritish Narayanan , Andras Moritz, Towards a framework for designing applications onto hybrid nano/CMOS fabrics, Microelectronics Journal, v.40 n.4-5, p.656-664, April, 2009
	Huang-Yu Chen , Chin-Hsiung Hsu , Yao-Wen Chang, High-performance global routing with fast overflow reduction, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan
	Gi-Joon Nam , Fadi Aloul , Karem Sakallah , Rob Rutenbar, A comparative study of two Boolean formulations of FPGA detailed routing constraints, Proceedings of the 2001 international symposium on Physical design, p.222-227, April 01-04, 2001, Sonoma, California, United States
	Raphael Rubin , André DeHon, Design of FPGA interconnect for multilevel metalization, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	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
	Guang-Ming Wu , Jai-Ming Lin , Yao-Wen Chang, Performance-driven placement for dynamically reconfigurable FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.628-642, October 2002
	André DeHon , Raphael Rubin, Design of FPGA interconnect for multilevel metallization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.10, p.1038-1050, October 2004
	Yohei Matsumoto , Masakazu Hioki , Takashi Kawanami , Hanpei Koike , Toshiyuki Tsutsumi , Tadashi Nakagawa , Toshihiro Sekigawa, Suppression of Intrinsic Delay Variation in FPGAs using Multiple Configurations, ACM Transactions on Reconfigurable Technology and Systems (TRETS), v.1 n.1, p.1-31, March 2008
	Anupam Chattopadhyay , Xiaolin Chen , Harold Ishebabi , Rainer Leupers , Gerd Ascheid , Heinrich Meyr, High-level modelling and exploration of coarse-grained re-configurable architectures, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	Gi-Joon Nam , Fadi Aloul , Karem A. Sakallah , Rob A. Rutenbar, A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints, IEEE Transactions on Computers, v.53 n.6, p.688-696, June 2004
	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
	Jason Cong , Jie Fang , Kei-Yong Khoo, DUNE: a multi-layer gridless routing system with wire planning, Proceedings of the 2000 international symposium on Physical design, p.12-18, May 2000, San Diego, California, United States
	Raphael Rubin , André DeHon, Choose-your-own-adventure routing: lightweight load-time defect avoidance, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	Jason Luu , Ian Kuon , Peter Jamieson , Ted Campbell , Andy Ye , Wei Mark Fang , Jonathan Rose, VPR 5.0: FPGA cad and architecture exploration tools with single-driver routing, heterogeneity and process scaling, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	Sungjoon Jung , Tag Gon Kim, Configuration Sharing to Reduce Reconfiguration Overhead Using Static Partial Reconfiguration, IEICE - Transactions on Information and Systems, v.E91-D n.11, p.2675-2684, November 2008
	Jarrod A. Roy , Igor L. Markov, High-performance routing at the nanometer scale, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Steven Balensiefer , Lucas Kregor-Stickles , Mark Oskin, An Evaluation Framework and Instruction Set Architecture for Ion-Trap Based Quantum Micro-Architectures, ACM SIGARCH Computer Architecture News, v.33 n.2, p.186-196, May 2005
	Yan Lin , Lei He, Stochastic physical synthesis for FPGAs with pre-routing interconnect uncertainty and process variation, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
	A. Chattopadhyay , H. Ishebabi , X. Chen , Z. Rakosi , K. Karuri , D. Kammler , R. Leupers , G. Ascheid , H. Meyr, Prefabrication and postfabrication architecture exploration for partially reconfigurable VLIW processors, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.4, p.1-31, July 2008
	Pierre Palatin , Yves Lhuillier , Olivier Temam, CAPSULE: Hardware-Assisted Parallel Execution of Component-Based Programs, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.247-258, December 09-13, 2006
	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
	Michael D. Moffitt , Jarrod A. Roy , Igor L. Markov, The coming of age of (academic) global routing, Proceedings of the 2008 international symposium on Physical design, April 13-16, 2008, Portland, Oregon, USA
	Ali Jahanian , Morteza Saheb Zamani, Using metro-on-chip in physical design flow for congestion and routability improvement, Microelectronics Journal, v.39 n.2, p.261-274, February, 2008
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: architecture and implementation of a hybrid and robust global router, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Minsik Cho , Katrina Lu , Kun Yuan , David Z. Pan, BoxRouter 2.0: A hybrid and robust global router with layer assignment for routability, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.2, p.1-21, March 2009
	Yan Lin , Lei He , Mike Hutton, Stochastic physical synthesis considering prerouting interconnect uncertainty and process variation for FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.2, p.124-133, February 2008
	Kingshuk Karuri , Anupam Chattopadhyay , Xiaolin Chen , David Kammler , Ling Hao , Rainer Leupers , Heinrich Meyr , Gerd Ascheid, A design flow for architecture exploration and implementation of partially reconfigurable processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.10, p.1281-1294, October 2008
	Olivier Coudert , Jason Cong , Sharad Malik , Majid Sarrafzadeh, Incremental CAD, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
	André DeHon, Design of programmable interconnect for sublithographic programmable logic arrays, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA
	André Dehon, Nanowire-based programmable architectures, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.1 n.2, p.109-162, July 2005
	Jason Cong , Majid Sarrafzadeh, Incremental physical design, Proceedings of the 2000 international symposium on Physical design, p.84-92, May 2000, San Diego, California, United States
	Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002