On-line incremental routing for interconnect fault tolerance in FPGAs minus the router

In this paper we present a Fault Tolerant (FT) technique for programmable interconnect on Field Programmable Gate Arrays (FPGAs). Our on-line strategy uses incremental reconfiguration capabilities of FPGAs to avoid faults, and the main advantage of our technique is that it does not require a router at the time FT reconfiguration is performed. Our algorithm generates precompiled FT partial configurations that can be downloaded when faults occur. Since the precompiled partial configurations are stored on a net by net basis, the required storage space and the download time is minimal. We have implemented our technique on the ORCA series FPGAs available from Lucent Technologies, and we demonstrate our technique on a FPGA based, on-line Adaptive Computing System (ACS) implemented with the ORCA FPGAs. Our worst case data indicates we can determine an average of seven alternates per signal net and for most circuits up to ten