Reconstruction Of Multi - Core Fault - Tolerant Arrays

At present, tens of billions of processors can be integrated on a single chip to process massive amounts of computing tasks in parallel. However, with increased system integration and application in complex environments, occurrence of defects in the chips during fabrication and post deployment has increased. This makes efficient fault-tolerant technology extremely important to improve the system reliability. For two common topological constructs torus and mesh, this paper studies the reconfigurable technology of multi-system by using redundancy strategy and degradation strategy, and the specific work is as follows.Firstly, this paper studies the problem of whether a torus-connected processor array can be reconfigured by modeling it has a maximum independent set problems. We examine three different distributions redundant processing elements (PEs), and develop the conversion rules of generate contradiction graph. We develop efficient algorithms to construct contradiction graphs from physical arrays with faulty PEs and redundant PEs. Then, we obtained maximum independent set of contradiction graph to evaluate whether the array can be reconstructed successfully. Finally, we propose an efficient algorithm to generate logic arrays based on the produced maximum independent set.Secondly, we consider faults not only on the processing elements (PEs) but also on the switches and links, and develop reconfiguration algorithms to construct as large as possible logical arrays with optimized interconnection length. To deal with the faults on switches and links, an efficient pre-processing technology is designed, in which switch faults are transformed into link faults, and then faulty links are classified into several categories to handle. Then, we propose an efficient algorithm, A-MLA, to produce as many as possible logical columns which are then combined to form a two dimensional processor array. After that, we propose an algorithm A-TMLA to reduce the interconnection length of the logical array obtained by algorithm A-MLA, as short interconnect leads to small communication latency and power consumption.