On the complexity of switch programming in fault-tolerant configurable chips Academic Article uri icon


  • Given a programmable chip (such as a WSI systolic array, or a field programmable gate array (FPGA)) made of equally-like configurable logic blocks (cells), the problem of programming the interconnect resources (consisting of switches) has been well studied in the literature. This process can be used for fault tolerance by logically reconfiguring the fault free cells of the array into a new array as well as to customize the FPGA by configuring it to perform the desired functions. Once the desired logical configuration has been achieved (as in the presence of faulty cells), the (programmable) switches in the interconnect resources of the array must be programmed to implement the target topology on the physical array. In this paper, we study the problem of minimizing the programming time (or cost) required for implementing this step. We show that current techniques are not likely to lead to cost optimal polynomial time algorithms, because the underlying covering problems are NPC-complete in the strong sense. The NPC-completeness is also extended to grid arrays. 2000 IEEE.

published proceedings

  • Proceedings IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems

author list (cited authors)

  • Shi, W., Kumar, K., & Lombardi, F.

citation count

  • 1

complete list of authors

  • Shi, W||Kumar, K||Lombardi, F

publication date

  • January 2000