A search-based bump-and-refit approach to incremental routing for ECO applications in FPGAs

ABSTRACT

Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct logical and/or technological problems in the circuit. Incremental routing is a significant part of an incremental physical design methodology. Typically after an ECO process, a small portion of the circuit netlist is changed, and in order to capitalize on the enormous resources and time already spent on routing the circuit it is desirable to reroute only the ECO-affected portion of the circuit, while minimizing any routing changes in the much larger unaffected part. Incremental rerouting also needs to be fast and to effectively use available routing resources. In this article, we develop a complete incremental routing methodology for FPGAs using a novel approach called bump and refit (B&R). The basic B&R idea (which was originally proposed in Dutt et al. [1999] in the much simpler context of extending some nets by a segment for the purpose of fault tolerance) in our algorithms is to rearrange some portions of some existing nets on other tracks within their current channels in order to find valid routings for the new/modified nets without requiring any extra routing resources and with little effect on the electrical properties of existing nets. Here we significantly extend the B&R concept to global and detailed incremental routing for FPGAs with complex switchboxes (SBox's) such as those in Lucent's ORCA and Xilinx's Virtex series. We introduce new concepts such as a B&R cost in global routing and the optimal subnet set to relocate for each bumped net (determined using an efficient dynamic programming formulation). We developed optimal and near-optimal algorithms (called Subsec_B&R and Subnet_B&R, respectively) to find incremental routing solutions using the B&R paradigm in complex FPGAs (e.g., Lucent&apos;s ORCA FPGA) with <i>i</i>-to-<i>j</i> SBox's, as well as an optimal version Fullnet_B&R for the VPR architecture from the University of Toronto using the simpler <i>i</i>-to-<i>i</i> SBox&apos;s. We compared our algorithms (simply called B&R when no distinction needs to be made between our versions) to two recent incremental routing techniques, Standard (Std) and Rip-up&Reroute (R&R), and to Lucent's A_PAR routing tool and the University of Toronto's VPR router used in complete rerouting modes. Experimental results for the ORCA show that B&R is 10 to 20 times faster than complete rerouting using A_PAR, and that B&R is also nearly 27&percnt; faster and yields new nets with nearly 10&percnt; smaller lengths compared to previous incremental routers. Furthermore, B&R routers do not change either the lengths or topologies of existing nets, a significant advantage in ECO applications, in contrast to R&R which increases the length of ripped-up nets by an average of 8.75 to 13.6&percnt;. Experimental results for the VPR architecture are dominated by the significantly larger (in many cases, orders of magnitude more) number of nets left unrouted by Std and R&R compared to B&R, which highlights the much greater efficacy of B&R-based incremental routing. However, B&R is significantly slower than the other two incremental routers, although on an absolute scale it is quite fast for two of four cases we simulated; in one case, it is about 25 times faster than VPR used in the full rerouting mode. The relative slowness of B&R for the VPR architecture arises from the fact that we used <i>i</i>-to-<i>i</i> SBox&apos;s which forces each net to be routed on the same track, thus causing significantly more bumpings and searches for rearranged solutions compared to <i>i</i>-to-<i>j</i> SBox&apos;s where a net can be routed on different interconnected tracks to minimize the amount of bumpings (as we did for the ORCA). Since modern FPGAs generally have the latter type of SBox&apos;s, B&R would be fast as well as very effective on them.

REFERENCES

• 1: Arslan, H. and Dutt, S. 2002. An order-impervious optimal detailed router for FPGAs: depth-first search and optimality-preserving speedup methods. Technical Report, University of Illinois at Chicago, Dec. Available at www.ece.uic.edu/∼dutt/papers/bandrspdup.pdf.
• 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: 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 [doi>10.1145/332357.332379]
• 4: Jason Cong , Jie Fang , Kei-Yong Khoo, An implicit connection graph maze routing algorithm for ECO routing, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.163-167, November 07-11, 1999, San Jose, California, United States
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: 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
• 7: Emmert, J. M. and Bhatia, D. 1998. Incremental routing in FPGAs. In Proceedings of the IEEE International ASIC Conference and Exhibit.
• 8: Fran Hanchek , Shantanu Dutt, Methodologies for Tolerating Cell and Interconnect Faults in FPGAs, IEEE Transactions on Computers, v.47 n.1, p.15-33, January 1998 [doi>10.1109/12.656073]
• 9: Lemieux, G. and Brown, S. 1993. Detailed router for allocating wire segments in FPGAs. In Proceedings of the ACM Physical Design Workshop (April), 215--226.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Bump-and-refit (B&R) paradigm, ECO (engineering change order), bumping cost, detailed routing, dynamic programming, field programmable gate arrays, global routing, incremental routing, switchbox