最短路径段优先扩展的容错重构算法

Shortest Partial Path First Algorithm for Reconfiguring Processor Array with Faults

当今超大规模集成电路(VLSI)技术把大量的处理器单元(PEs)集成在单一芯片上.随着VLSI阵列密度的增加,系统运行期间PEs发生故障的概率也在增加.这些发生故障的PEs会破坏已有的网络通讯结构,为了保证系统的稳定性和可靠性,获得无故障逻辑阵列的重构技术成为有意义的研究课题.提出一个最短路径段优先扩展的逻辑列重构算法,该算法优先扩展最有可能生成最优逻辑列的路径段,即总是选择当前长连接数最少的路径段进行扩展,从而确保生成的逻辑列为最优逻辑列.由于最优逻辑列上的路径段往往可以被率先扩展到终点,因此算法能够更加快速地构造出最优逻辑列,并不需要计算相关区域所有PEs的路径信息,从而克服了现有的动态规划算法需要计算所有无故障PEs的弱点.实验结果表明在故障率为10%的128×128的主阵列上,其运行时间可以提高35.3%.

Currently,the Very Large Scalelntegration （VLSI） technologiesintegrate a large numbers of the proeessingelements （PEs） array on a single chip. With the increasingdensity of VLSI arrays, the probability of PEs malfunction is also increasingduringuormalop- erationofthesystem. The faulty PEs destroythe regular structure of the communication networks,and thusthey reduce the processing capabilities of the multiprocessorarray. The fault-tolerant recortfiguration techniques become a meaningful research topic to obtain fault- free logical array, which guarantee the system stability and reliability. In this paper, we propose analgorithm to re, configure logical col- unmsbased on the strategyof 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 constructoptimal logical columnmore quickly without cornputing all PEspath inforrnationamongrelatedPEs andthus overeome the weakness of the existing dynamic programming algorithm which needs to calculate all fault-free PEs. Experimental results show that the computation time can be improved about more than 35.3% in 128 × 128 host array with faults density of 10%.