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

摘要：

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

关键词：重构、VLSI阵列、容错、算法

所属期刊栏目：38

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目61302127;中国博士后科学基金项目2015M570228;智能计算及软件新技术天津市重点实验室开放基金;天津市科技支撑计划重点项目14ZCZDGX00033

在线出版日期：2017-08-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：540-547