Research On Fast Reconstruction Algorithms For Fault Tolerant Processor Arrays

Currently,the Very Large Scale Integration(VLSI)technologies integrate a large numbers of the processing elements(PEs)array on a single chip to perform large-scale parallel tasks.With the increasing density of VLSI arrays,the probability of PEs malfunction is also increasing during normal operation of the system.The faulty PEs destroy the regular structure of the communication networks,and thus they reduce the processing capabilities of the multiprocessor array.The fault-tolerant reconfiguration techniques become a meaningful research topic to obtain fault-free logical array,which guarantee the system stability and reliability.This paper studies the reconfigurable technology by using degradation strategy for common topological constructs mesh,and the specific work is as follows.Firstly,this paper propose an algorithm to reconfigure logical columns based on the strategy of Shortest partial path first extension.The algorithm extends the partial path with the minimum number of long interconnect,such that the algorithm is most likely to the generate the optimal logical column.As the partial path in optimal logical column is generally extended fast to the end,the proposed algorithm can construct optimal logical column more quickly without computing all PEs path information among related PEs and thus overcome the weakness of the existing dynamic programming algorithm which needs to calculate all fault-free PEs.Secondly,when a logical array was constructed,the processor may fail at any time.The paper consider the reconfiguration problem of the real-time fault in a processor array and quickly construct a maximum logical array under the real-time fault.The previous processing scheme overthrow the original structure of the logical array with real-time fault and construct the logical array in the target array.However,the study found that the program needn't refactor a new logical in the host array to obtain a maximum logical array for certain situations.This paper have designed an effective pretreatment technology that generate an new optimal logical column to replace the original logical column with real-time fault PE.The pretreatment technology does not need to construct the all logical columns,so it can quickly generate a relatively large logical array to small communication latency and reduce power consumption.