Reconfiguration Algorithm For VLSI Arrays Base On The Flexible Routing Strategy

With the rapid development of the integration industry,processing elements are becoming more and more integrated on a single chip.This trend is irreversible.However,this brings up a host of thorny issues.On the one hand,due to the high integration degree,the chip is faced with a serious heating problem in the working process,resulting in a certain number of processing elements cannot work normally,which leads to the reliability of the processor array circuit is not satisfactory.On the other hand,impurities can cause a certain number of processing elements to fail during the manufacturing process.In aerospace,marine,military and other fields,chips often need to work in extremely harsh environments.Due to the limitations of environment and other factors,once the processing element in the chip fails,the staff is often unable to timely maintenance.Therefore,the chip needs to have a certain degree of self-repair ability,and requires the processor array to be reconfigurable under the support of the algorithm.As we all know,reducing the interconnection length between processing elements is helpful to reduce the communication cost,energy consumption and delay of the chip for the reconstructed target array.Although some optimization algorithms have been proposed by experts to reduce the long interconnect in the target array so as to reduce the interconnection redundancy,these algorithms cannot guarantee the effect when the size of the target array is increased.Therefore,this thesis proposes an efficient and high-performance subarray reconfiguration algorithm based on the strategy of flexible routing through in-depth analysis of the structural characteristics of processor arrays,which aims to reduce interconnection redundancy while increasing the size of target arrays.Firstly,the algorithm determines the location of the bottleneck row by analyzing the number of faulty processing elements in the physical rows of the original physical array under the constraints of low bypass and column rerouting.Secondly,the algorithm assigns the processing elements that do not have faults in the bottleneck row to the fault adjacency elements in their upper and lower adjacent rows,and removes the bottleneck row.Finally,the algorithm transforms the reconfiguration problem of local optimal logical columns into solving the shortest path problem,so that the subarray reconfiguration problem can be solved in polynomial time,thus ensuring the superiority of the target array in size and number of long interconnects.Whether it is random fault distribution model or cluster fault distribution model,simulation experiments show that the proposed algorithm achieves better performance than the existing algorithm.The experimental results show that for a physical array with a size of 16×16 and a failure rate of 30%,in the case of random faults,the proposed algorithm improves the performance of the harvest rate and interconnection redundancy by 17.25% and 18.51%,respectively,compared with the existing algorithms.In addition,for the 128×128 physical array,when the size and number of cluster fault areas are 16×16 and 24 respectively,the performance improvement of the proposed algorithm in terms of harvest rate and interconnection redundancy reaches 6.24% and 11.32%,respectively,compared with the existing algorithms.