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

• Main Authors: Vinay Verma, Shantanu Dutt
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 2001
• Subjects: Orca
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.1843; http://www.ece.uic.edu/~dutt/././papers/iccad01.ps

Incremental physical CAD is encountered frequently in the socalled 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. As far as routing is concerned, in order to capitalize on the enormous resources and time already spent on routing the circuit, and to meet time-to-market requirements, it is desirable to re-route only the ECO-affected portion of the circuit, while minimizing any routing changes in the much larger unaffected part of the circuit. Incremental re-routing also needs to be fast and to effectively use available routing resources. In this paper, we develop a complete incremental routing methodology for FPGAs using a novel approach called bump and refit (B&R); B&R was initially proposed in [4] in the much simpler context of extending some nets by a segment (for the purpose of fault tolerance) for FPGAs with simple i-to-i switchboxes. Here we significantly extend this concept to global and detailed incremental routing for FPGAs with complex switchboxes such as those in Lucent's ORCA and Xilinx's Virtex series. We also introduce new concepts such as B&R cost estimation during global routing, and determination of the optimal subnet set to bump for each bumped net, which we obtain using an efficient dynamic programming formulation. The basic B&R idea in our algorithms is to re-arrange some portions of some existing nets on other tracks within their current channels to find valid routings for the incrementally changed circuit without requiring any extra routing resources (i.e., completely unused tracks), and with little effect on the electrical properties of existing nets. We have