Solving hard instances of FPGA routing with a congestion-optimal restrained-norm path search space

ABSTRACT

The negotiated congestion mechanism forms the basis of most published FPGA routers today, with many routers projecting congestion and any other requirements onto a scalar search space to evaluate candidate paths. In this paper, we study the numerical stability of these scalar projections as the number of iterations increase. We show that in these scalar search spaces the norm of path costs increase exponentially with the number of iterations, leading to floating-point absorption and representation problems in computer arithmetic. We propose a novel two-component totally-ordered monoid space for path candidate evaluation, that guarantees the A* search finds a path with minimum congestion cost, and has linear norm growth with respect to the number of iterations. We demonstrate the efficacy of our new algorithm by testing on hard open routing problems in the FPGA Place and Route Challenge. The router successfully found 18 new routing solutions to instances that were previously unroutable, reducing the lowest track count to route 20 standard FPGA routing benchmarks by 10.2%.

REFERENCES

• 1: Vaughn Betz. The "FPGA Place and Route Challenge". http://www.eecg.toronto.edu/~vaughn/challenge/challenge.html.
• 2: 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
• 3: Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
• 4: 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]
• 5: 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
• 6: R. Fung , V. Betz , W. Chow, Simultaneous short-path and long-path timing optimization for FPGAs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.838-845, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382691]
• 7: P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determiniation of minimum cost paths. IEEE Trans. Syst. Sci. Cybernetics, 4:100--107, 1968.
• 8: 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 [doi>10.1145/369691.369776]
• 9: 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 [doi>10.1109/ICCAD.2003.13]
• 10: Seokjin Lee and Martin D. F. Wong. Timing-driven routing for FPGAs based on Lagrangian relaxation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(4):506--511, April 2003.
• 11: 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 [doi>10.1145/611817.611828]
• 12: 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 [doi>10.1145/267665.267682]
• 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: 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 [doi>10.1145/296399.296450]
• 15: Steven W. Oldridge and Steven J. E. Wilton. Placement and routing for FPGA architectures supporting wide shallow memories. In Proceedings of the 2003 IEEE International Conference on Field Programmable Technology, pages 154--161, 2003.
• 16: 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 [doi>10.1145/258305.258324]
• 17: 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 [doi>10.1145/611817.611829]
• 18: Steven J. E. Wilton, A crosstalk-aware timing-driven router for FPGAs, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.21-28, February 2001, Monterey, California, United States [doi>10.1145/360276.360292]
• 19: 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 [doi>10.1145/258305.258322]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Experimentation

Keywords:
FPGA, negotiated congestion, routability-driven routing