Stochastic, spatial routing for hypergraphs, trees, and meshes

ABSTRACT

FPGA place and route is time consuming, often serving as the major obstacle inhibiting a fast edit-compile-test loop in prototyping and development and the major obstacle preventing late-bound hardware and design mapping for reconfigurable systems. Previous work showed that hardware-assisted routing can accelerate fanout-free routing on Fat-Trees by three orders of magnitude with modest modifications to the network itself. In this paper, we show how these techniques can be applied to any FPGA and how they can be implemented on top of LUT networks in cases where modification of the FPGA itself is not justified. We further show how to accommodate fanout and how to achieve comparable route quality to software-based methods. For a tree network, we estimate an FPGA implementation of our routing logic could route the Toronto Place and Route Benchmarks at least two orders of magnitude faster than a software Pathfinder while achieving within 3% of the aggregate quality. Preliminary results on small mesh benchmarks achieve within one track of vpr-fast.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: V. Betz. http://www.eecg.toronto.edu/~vaughn/vpr/vpr.htmlVPR and T-VPack: Versatile Packing, Placement and Routing for FPGAs. http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html, March 27 1999. Version 4.30.
• 3: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 4: V. Betz and J. Rose. Place-and-Route Challenge. http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html, 1999.
• 5: C. R. Carroll. A Smart Memory Array Processor for Two Layer Path Finding. In Proceedings of the Second Caltech Conference on Very Large Scale Integration, pages 165--195, January 1981.
• 6: P. K. Chan , M. D. F. Schlag, Acceleration of an FPGA router, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.175, April 16-18, 1997
• 7: 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 [doi>10.1145/329166.329201]
• 8: André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
• 9: André DeHon , Randy Huang , John Wawrzynek, Hardware-Assisted Fast Routing, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.205, September 22-24, 2002
• 10: Stephan W. Gehring , Stefan H.-M. Ludwig, Fast integrated tools for circuit design with FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.133-139, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275133]
• 11: A. Iosupovici. A Class of Array Architectures for Hardware Grid Routers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 5(2):245--255, April 1986.
• 12: C. Y. Lee. An Algorithm for Path Connectios and Its Applications. IRE Transactions on Electronic Computers, EC-10:346--365, 1961.
• 13: Larry McMurchie , Carl Ebeling, PathFinder: a negotiation-based performance-driven router for FPGAs, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.111-117, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201328]
• 14: T. Ryan and E. Rogers. An ISMA Lee Router Accelerator. IEEE Design and Test of Computers, pages 38--45, October 1987.
• 15: Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
• 16: R. Tessier. http://www.ecs.umass.edu/ece/tessier/fpd98.pdf. Negotiated A* Routing for FPGAs. In Proceedings of the 5th Canadian Workshop on Field Programmable Devices, June 1998.
• 17: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]
• 18: T. Watanabe, H. Kitazawa, and Y. Sugiyama. A Parallel Adaptable Routing Algorithm and its Implementation on a Two-Dimensional Array Processor. IEEE Transactions on Computer-Aided Design, 6(2):241--250, March 1987.
• 19: Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Linear Feedback Shift Registers in Virtex Devices, January 2001. XAPP 210 \urllinkhttp://www.xilinx.com/xapp/xapp210.pdf.
• 20: Xilinx, Inc., 2100 Logic Drive, San Jose, CA 95124. Xilinx Virtex-II 1.5V Platform FPGAs Data Sheet , September 2002. DS031 http://www.xilinx.com/partinfo/ds031.pdf.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
  C.4 PERFORMANCE OF SYSTEMS

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
FPGA, detail routing, reconfigurable computing, spatial routing