New parallelization and convergence results for NC: a negotiation-based FPGA router

ABSTRACT

The negotiation-based routing paradigm has been used successfully in a number of FPGA routers. In this paper, we report several new findings related to the negotiation-based routing paradigm. We examine in-depth the convergence of the negotiation-based routing algorithm. We illustrate that the negotiation-based algorithm can be parallelized. Finally, we demonstrate that a negotiation-based parallel FPGA router can perform well in terms of delay and speedup with practical FPGA circuits.

REFERENCES

• 1: 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]
• 2: 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]
• 3: R. Tessier, "Negotiated A* routing for FPGAs," in Proceedings of the Fifth Canadian Workshop on Field- Programmable Devices, (Quebec, Canada), June 1998.
• 4: 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
• 5: P. K. Chan, M. Schlag, C. Ebeling, and L. McMurchie, "Data-parallel FPGA router," submitted for publication.
• 6: J. Rose, "Parallel global routing for standard cells," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 9, pp. 1085-1095, Oct. 1990.
• 7: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 8: W. Richard Stevens, UNIX network programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 9: 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
• 10: A. T. Ferrucci, M. H. Martin, T. Geocaris, M. Schlag, and P. K. Chan, "ACME: A Field-Programmable Gate Arrays implementation of a self-adapting and scalable connectionist network," in Proceedings of the 2 nd International ACM/SIGDA Workshop on Field-Programmable Gate Arrays, (Berkeley, California, USA), Feb. 1994.
• 11: Pak K. Chan , M. J. Boyd , S. Goren , K. Klenk , V. Kodavati , R. Kundu , M. Margolese , J. Sun , K. Suzuki , E. Thorne , X. Wang , J. Xu , M. Zhu, Reducing Compilation Time of Zhong's FPGA-Based SAT Solver, Proceedings of the Seventh Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.308, April 21-23, 1999
• 12: XILINX: The Programmable Gate Array Data Book. 2100 Logic Drive, San Jose, CA 95124, 1993.
• 13: C. Kenneth Miller, Multicast Networking and Applications, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 14: S. Pakin, M. Lauria, M. Buchanan, K. Hane, L. Giannini, J. Prusakova, and A. Chien, Fast Message (FM) 2.0. University of Illinois at Urbana-Champaign, 1304 W. Springfield, Urbana, IL 61801, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Performance, Theory