An effective hop-based detailed router for FPGAs for optimizing track usage and circuit performance

ABSTRACT

We have developed a hop-based complete detailed router ROAD-HOP that uses the Bump & Refit (B&R) approach to route a FPGA circuit in a near-optimal manner. This approach is based on generating a minimum-spanning tree (MST) from the complete pin-to-pin graph of each net with each edge cost based on a combination of its contribution to the net length, channel congestion and potential average "bumping" cost in the channels in which the edge lies. Using the MST, a hop-based routing of each net is performed that attempts to minimize the combination of net length, number of hops and total number of tracks needed in the FPGA. Given each net's global route, a FPGA detailed router can minimize net delays by minimizing the number of hops or equivalently the number of track switchings in complex switchboxes of current FPGAs---hop-based routing can model routing using complex switchboxes. By minimizing the number of hops and total net length, ROAD-HOP minimizes net delay. Note that ROAD-HOP can only be compared to another detailed router and we compare it to the best previous detailed router SEGA for the VPR architecture. We use the output of the VPR global router as input to both ROAD-HOP and SEGA. Our new algorithm achieves significantly better results than SEGA with respect to the number of tracks needed and the circuit speed. Across a number of benchmark circuits, our algorithm needs about 8% fewer tracks than SEGA. Furthermore, the average net delay of the routing generated by our algorithm is 34% less than that of SEGA, and is 52% less for the longest net.

REFERENCES

• 1: Shantanu Dutt , Vinay Verma , Hasan Arslan, A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.664-693, October 2002 [doi>10.1145/605440.605449]
• 2: Shantanu Dutt , Vimalvel Shanmugavel , Steve Trimberger, Efficient incremental rerouting for fault reconfiguration in field programmable gate arrays, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.173-177, November 07-11, 1999, San Jose, California, United States
• 3: E. Rosenberg, "New Iterative Supply/Demand Router with Rip-up and Reroute Strategy", DAC 1987.
• 4: Hasan Arslan , Shantanu Dutt, ROAD: An Order-Impervious Optimal Detailed Router for FPGAs, Proceedings of the 21st International Conference on Computer Design, p.350, October 13-15, 2003
• 5: G. Lemieux and S. Brown, "A Detailed Router for Allocating Wire Segments in FPGAs", ACM/SIGDA Physical Design Workshop, pp.215--226, 1993.
• 6: S. Brown, J. Rose, Z.G. Vranesic, "A Detailed Router for FPGAs", IEEE Transactions on Computer Aided Design, 11(5), pp.620--628, 1992.
• 7: 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
• 8: W.C.Elmore: "The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifiers", J. Applied Physics, 1948, 19, pp.55--63.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
FPGAs, MST, bump and refit paradigm, bumping cost, detailed routing, hop-based routing, switchbox