Title: A probabilistic analysis of fault tolerance for switch block array in FPGAs

Authors: Jing Huang, Mehdi B. Tahoori, Fabrizio Lombardi

Addresses: Department of Electrical and Computer Engineering, Northeastern University, Boston, MA 02115, USA. ' Department of Electrical and Computer Engineering, Northeastern University, Boston, MA 02115, USA. ' Department of Electrical and Computer Engineering, Northeastern University, Boston, MA 02115, USA

Abstract: This paper presents a new approach for the evaluation of FPGA routing resources in the presence of faulty switches and wires. Switch stuck-open (switch permanently off) and stuck-closed faults (switch permanently on) as well as wire faults are addressed. This study is directly related to fault tolerance of the interconnect for testing and reconfiguration at manufacturing and run-time application. Signal routing in the presence of faulty resources is analysed at switch block and switch block array levels. Probabilistic routing (routability) is used as figure of merit for evaluating the programmable interconnect resources of FPGA architectures. The proposed approach is based on finding a permutation (one-to-one mapping) between the input and output endpoints. A probabilistic approach is also presented to evaluate fault tolerant routing for the entire FPGA by connecting switch blocks in chains as required for testing and to account for the I/O pin restrictions of an FPGA chip. The results are reported for various commercial and academic FPGA architectures.

Keywords: FPGA routing; fault tolerance; testing; switch block arrays; faulty switches; faulty wires; interconnect; routability; reconfigurable architectures.

DOI: 10.1504/IJES.2005.009954

International Journal of Embedded Systems, 2005 Vol.1 No.3/4, pp.250 - 262

Published online: 05 Jun 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article