Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays

Fast reconfiguration is one of the main challenges in fault tolerant VLSI arrays. In these arrays, there are some invalid processing elements (PEs) that are fault-free but cannot be used to form a target array. These invalid PEs lead to backtracking in reconfiguration. This paper proposes a non-backtracking reconfiguration (NBR) algorithm for three-dimensional degradable VLSI array with faults. The proposed algorithm accelerates the reconfiguration without loss of harvest, by eliminating the backtracking operation that frequently occurs in the existing algorithm (named as BGPR) cited in this paper. Initially, the invalid PEs are identified in the preprocessing for the host array. Then NBR algorithm constructs each logical plane from bottom to top in the host array, and updates the set of the invalid PEs in the host array after a logical plane is constructed. Experimental results show that the NBR algorithm is more scalable than the BGPR algorithm, and thus it can reconfigure large host arrays much faster. In addition, the runtime of NBR algorithm tends to decrease, rather than increase as did in BGPR algorithm, with the increasing fault density.