Abstract:

High-efficient fault-tolerant techniques are essential for improving the reliability of multiprocessor systems. It is well known that torus is an important interconnection network for multiprocessor arrays, but no work has been reported on the faulty tolerance of torus-connected processor arrays. In our work, reconfiguring a torus-connected processor array is modeled to be a maximum independent set problem. The nodes on the contradiction graph represent alternatives of the fault processing elements (PEs), and the edge denotes that different alternatives cannot coexist. Three different distributions of redundant PEs are discussed, and three algorithms are proposed to construct contradiction graphs, solve maximum independent set, and generate logic arrays based on the produced maximum independent set. Simulation results show that, the cross distribution and one-row-one-column distribution perform well in reconfiguration for smaller arrays and smaller fault densities. In addition, the reconfiguration ability of the three proposed distribution patterns decreases as the fault density and array size increase, thus other spare distribution patterns should be investigated, or more spare PEs should be integrated. Moreover, torus arrays outperform mesh arrays in terms of fault-tolerance performance.

Key words: torus-connected processor array;reconfiguration algorithm;fault-tolerance;contradiction graph