Reconfiguration Algorithm For VLSI Arrays With Network Flow And Dynamic Programming

In recent years,with the advanced techniques in the domain of very large scale integration(VLSI),massive amounts of processing elements(PEs)are integrated on a single chip or wafer,which has benefit of processing an enormous amount of information in parallel.However,as the number of PEs in a chip(wafer)increases,the probability of defects occurred during the fabrication process also increases.Moreover,it is almost impossible to guarantee that all of the PEs in the system will be fault-free throughout its working lifetime.The stability and the reliability of the system is definitely affected by these faults.Therefore,fault-tolerant techniques must be employed in VLSI processor arrays to reconfigure the system to maintain the dependability and the operability.The VLSI processor array with mesh-connected structure is widely used in military,aerospace and graphics processing because of its simple,regularity structure and easy implementation.At present,there are two main fault-tolerant technologies for mesh-connected processor arrays,namely redundancy approach and degradation approach.Based on the idea of degradation approach,the main contents and contributions of this dissertation are indicated below.Firstly,in two-dimensional processor array,the problem of accelerating the reconfiguration for high performance target arrays is studied.On the basis of the existing work,an improved method is proposed to accelerate the speed of reconfiguration.In this paper,first,a new network model is constructed by using an efficient data structure to represent entity nodes,which make the number of nodes in the new model less than half of the previous model.Second,based on the new network model and the idea of network flow,a reconfiguration algorithm which can find multiple independent shortest paths in one traversal is proposed,which greatly reduces the time of the reconfiguration.Finally,the experimental data show that the proposed algorithm has shorter running time than the existing network flow algorithm on the premise of ensuring the same high performance target array.Secondly,in three-dimensional processor array,the problem of reducing the total length of interconnection in target array is investigated.We aim at the optimization of the total length of interconnection for the target array which is constructed with flexible routing strategy.In this paper,an algorithm based on dynamic programming is proposed.The algorithm optimizes the local logic plane one by one from right to left,and then combines the optimized local logic planes to get the final optimized logical sub-array.Finally,the comparison experiment shows that the algorithm has fewer interconnection length and better performance than the previous algorithm.