Fault-tolerant Reconfiguration Techniques For Processor Arrays On-chip

The growing integration density of multiprocessor system has significantly increased the chance of faults due to fabrication or power overheating during massively parallel computing. To improve the system reliability, this dissertation investigates the problem of constructing fault-free logical array from the original processor array with faulty elements. The main contents and contributions of this dissertation are indicated below.First, we investigate the fault-tolerant mechanism for two-dimensional(2D) / threedimensional(3D) processor arrays. Di?erent from existing works for 2D/3D processor arrays, we propose enhanced fault-tolerant architecture which considers not only processor faults but also switch faults and link faults. Under the enhanced architecture, switch faults are transformed into link faults, and then faulty links are classified into many categories which are solved one by one.Second, we investigate the problem of constructing maximum fault-free logical arrays. We first prove that the reconfiguration problems are NP-hard under two di?erent constraints. To improve the reconfiguration e?ciency, we propose novel flexible rerouting schemes which relax the limitation on compensation distance, and thus achieve higher harvest in logical array size. We solve a restricted version of the reconfiguration problem by designing e?cient reconfiguration algorithms, and prove that the algorithms produce maximum logical arrays for the restricted problems.Third, we accelerate the fault-tolerant reconfiguration using parallel processing techniques. We design two centralized parallel reconfiguration approaches: the multi-threads algorithm simultaneously constructing multiple logical columns with one thread producing one column, while the divide-and-conquer based parallel algorithm generates each logical column in parallel such that columns of the logical array are produced one by one.We design two distributed parallel reconfiguration algorithms, which uses the PEs of the faulty array to achieve fault-tolerant reconfiguration.Fourth, we investigate the problem of constructing compact logical array, i.e., reducing the interconnection redundancy. We show that constructing compact logical array is NP-hard problem. We develop algorithms to construct compact logical array with given size, and maximum compact array. To evaluate our proposed algorithms, we calculate the lower bound on the length of interconnection networks for 2D/3D arrays. Experimental results show that the obtained arrays are close to the lower bounds, which indicates that our obtained arrays are nearly optimal and the lower bounds are tight.