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

• Published in: ACM Transactions on Design Automation of Electronic Systems
• Main Authors: Dutt, Shantanu, Verma, Vinay, Arslan, Hasan
• Format: Article in Journal/Newspaper
• Language: English
• Published: Association for Computing Machinery (ACM) 2002
• Subjects: Orca
• Online Access: http://dx.doi.org/10.1145/605440.605449; https://dl.acm.org/doi/pdf/10.1145/605440.605449

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's ORCA FPGA) with i-to-j SBox's, as well as an optimal version Fullnet_B&R for ...