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

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