A Search-Based Bump-and-Refit Approach to Incremental Routing for ECO Applications in FPGAs

• Main Authors: Shantanu Dutt, Vinay Verma, Hasan Arslan
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2002
• Subjects: Orca
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.2292; http://www.cs.ucla.edu/~mrivero/PAPER/p664-dutt.pdf

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 nearoptimal 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's ORCA FPGA) with i-to- j SBox's, as well as an optimal version Fullnet B&R for the VPR architecture from the University of Toronto using the simpler i-to-i SBox'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% faster and yields new nets w.